US 12,743,460 B1Granted

Computationally efficient data set clustering using partitioning and iterative refinement

AssigneeAmazon Technologies, Inc.

InventorsGanesh Ramesh Panaskar, Sankalp Verma, Rishi Bhasin

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and methods are disclosed for implementation of a scalable and efficient scaling algorithm for clustering data objects within a data set, as well as implementation of the algorithm to control content generation and selection. A data set can be initially divided randomly into subsets. A base clustering algorithm, such as k-means clustering, can be applied in parallel to each subset to identify a set of local centroids representative of local clusters within each subset. The local centroids can be aggregated from across subsets and the base clustering algorithm can be applied to the aggregated local centroids to result in global clusters. Data objects associated with each global cluster (such as by being clustered within a local cluster corresponding to a global cluster) represent a global clustering of the data set. These global clusters can form the basis for additional iterations of local and global clustering, further refining global clustering.

Claims20

Dependent claims

A system for clustering a data set including a plurality of vectors, each vector associated with a content item and representing quantitative attributes of the content item as a multidimensional value, the system comprising:

a data store storing the plurality of vectors;
and
a processor in communication with the data store and configured with computer-executable instructions to:
divide the plurality of vectors into multiple partitions, each partition including a subset of vectors from the plurality of vectors;
for each iteration of multiple iterations:
apply a clustering algorithm to each partition of the multiple partitions to identify a set of local centroids for each partition, each local centroid of the set of local centroids clustering a subset of vectors of a partition;
apply the clustering algorithm to an aggregation of the sets of local centroids from the multiple partitions to identify a set of global centroids, each global centroid of the set of global centroids clustering a subset of local centroids from the aggregation;
update the multiple partitions based on the set of global centroids, wherein each partition of the multiple partitions is updated to include vectors associated with a distinct global centroid of the set of global centroids, and wherein a vector is associated with a particular global centroid of the set of global centroids when the vector is clustered within a local centroid that is clustered within the particular global centroid;
and
subsequent to a final iteration of the multiple iterations, output labels for individual vectors of the plurality of vectors, the labels reflective of the partition of the multiple partitions that includes an individual vector.

7 more elements

A computer-implemented method comprising:

obtaining information identifying a plurality of vectors, each vector representing a multidimensional value;
dividing the plurality of vectors into multiple partitions, each partition including a subset of vectors from the plurality of vectors;
applying a first clustering algorithm to each partition of the multiple partitions to identify a set of local centroids for each partition, each local centroid of the set of local centroids clustering a subset of vectors of a partition;
applying a second clustering algorithm to an aggregation of the sets of local centroids from the multiple partitions to identify a set of global clusters, each global cluster of the set of global clusters clustering a subset of local centroids from the aggregation;
updating the multiple partitions based on the set of global clusters, wherein each partition of the multiple partition is updated to include vectors associated with a distinct global cluster of the set of global clusters, and wherein a vector is associated with a particular global cluster of the set of global clusters when the vector is clustered within a local centroid that is clustered within the particular global cluster;
and
outputting labels for individual vectors of the plurality of vectors, the labels reflective of the partition of the multiple partitions that includes an individual vector.

4 more elements

One or more computer-readable non-transitory media including computer executable instructions that, when executed by a computing system, cause the computing system to:

obtain information identifying a plurality of vectors, each vector representing a multidimensional value;
divide the plurality of vectors into multiple partitions, each partition including a subset of vectors from the plurality of vectors;
apply a first clustering algorithm to each partition of the multiple partitions to identify a set of local centroids for each partition, each local centroid of the set of local centroids clustering a subset of vectors of a partition;
apply a second clustering algorithm to an aggregation of the sets of local centroids from the multiple partitions to identify a set of global clusters, each global cluster of the set of global clusters clustering a subset of local centroids from the aggregation;
update the multiple partitions based on the set of global clusters, wherein each partition of the multiple partition is updated to include vectors associated with a distinct global cluster of the set of global clusters, and wherein a vector is associated with a particular global cluster of the set of global clusters when the vector is clustered within a local centroid that is clustered within the particular global cluster;
and
output labels for individual vectors of the plurality of vectors, the labels reflective of the partition of the multiple partitions that includes an individual vector.

4 more elements

Dependencies are inferred from the claim text.