Centroid detection for clustering

• US 9,727,633 B1
• Filed: 02/19/2016
• Issued: 08/08/2017
• Est. Priority Date: 07/24/2013
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Chakravarthy, Diwakar, Dai, Siyang, Dykstra, Aaron James
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US15/048,904
• Time in Patent Office: 536 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A method of categorizing data points is described which, when combined with a clustering algorithm, provides groupings of data points that have an improved confidence interval. The method can be used to find an optimal number of groupings for a dataset, which in turn allows a user to categorize a group of data points for processing. In some examples, a dataset containing a number of data points may be accessed. Additionally, in some aspects, groupings of data points within the dataset may be grouped based at least in part on similarities between the data. Further, a number of groupings of data points may be adjusted so that the distance between the data points within one or more groupings of data points may fit within a confidence level.

Claims

1. A computer-implemented method, comprising:

accessing a dataset containing a number of data points;

forming, based at least in part on similarities between the data points, a first number of clusters of the data points, a cluster of the clusters containing a portion of the data points;

determining a stability of the cluster based at least in part on a change to a center of the cluster between iterations of clustering the data points, the center determined based at least in part on the portion of the data points;

determining that the cluster is unstable based at least in part on the change to the center of the cluster falling outside a range, the range being based at least in part on a confidence level; and

forming, based at least in part on the cluster being unstable, a second number of modified clusters of the data points.

2. The computer-implemented method of claim 1, wherein the change to the center is based at least in part on additional data points assigned to the cluster relative to a previous iteration for clustering the data points.

3. The computer-implemented method of claim 1, wherein forming the second number of modified clusters comprises determining an adjustment to the first number of clusters.

4. The computer-implemented method of claim 3, wherein the adjustment comprises a predefined increment or a predefined decrement.

5. The computer-implemented method of claim 3, wherein the adjustment is determined based at least in part on the change to the center of the cluster, and wherein the change to the center is based at least in part on additional data points assigned to the cluster relative to a previous iteration for clustering the data points.

6. The computer-implemented method of claim 1, wherein the change to the center is based at least in part on additional data points assigned to the cluster between the iterations.

7. The computer-implemented method of claim 1, further comprising:

providing the first number of clusters and the second number of modified clusters to a computing device for presentation at a user interface of the computing device.

8. The computer-implemented method of claim 1, further comprising:

reporting that the cluster is unstable to a computing device.

9. The computer-implemented method of claim 1, wherein the center represents a centroid of the data points.

10. The computer-implemented method of claim 9, wherein the location of the centroid is randomly set, and wherein the portion of the data points is assigned to the cluster based at least in part on proximities of the portion of the data points to the location of the centroid.

11. A system, comprising:

at least one memory that stores computer-executable instructions; and

at least one processor configured to access the at least one memory, wherein the at least one processor is configured to execute the computer-executable instructions to collectively at least;

generate a number of clusters of data points based at least in part on similarities between the data points;

determine, based at least in part on respective data points clustered in a cluster of the clusters, a change to the cluster between iterations of generating the clusters, the change being to one or more of;

a center of the cluster or a composition of the cluster;

determine that the cluster is unstable based at least in part on a determination that the change to the cluster falls outside a range, the range being based at least in part on a confidence level; and

generate an adjusted number of clusters of the data points based at least in part on the cluster being unstable.

12. The system of claim 11, wherein determining that the cluster is unstable comprises:

determining a stability of the cluster based at least in part on the portion of the data points; and

comparing the stability of the cluster to the confidence level.

13. The system of claim 12, wherein the data points relate to consumers, and wherein the at least one processor is further configured to execute the computer-executable instructions to collectively at least perform an action directed to one or more of the data points based at least in part on attributes of other data points within a same cluster of data points.

14. The system of claim 13, wherein the data points are defined based at least in part on at least one of income, age, political views, geographic location, or purchase history.

15. The system of claim 13, wherein the action performed is to provide advertisements that are directed at a particular cluster of the consumers.

16. The system of claim 13, wherein the attributes of other data points within the same cluster are purchases made by the consumers.

17. The system of claim 11, wherein the at least one processor is further configured to execute the computer-executable instructions to collectively at least perform an action with relation to a data point within the cluster based at least in part on prior actions performed on particular data points within the cluster.

18. One or more computer-readable media storing computer-executable instructions that, when executed by one or more computer systems, configure the one or more computer systems to perform operations comprising:

generating, in an iteration, a number of clusters based at least in part on a dataset;

determining whether respective stabilities of the clusters are above a confidence level, a cluster of the clusters determined to be unstable based at least in part on a change to a composition of the cluster between iterations of generating the clusters;

determining an adjustment to the number of clusters based at least in part one or more of the respective stabilities being below the confidence level;

generating new clusters based at least in part on the dataset and the adjustment to the number of clusters; and

storing the dataset within a computer storage device based at least in part on the new clusters.

19. The one or more computer-readable media of claim 18, wherein the clusters are generated based at least in part on a k means clustering.

20. The one or more computer-readable media of claim 18, wherein the change is determined based on a comparison of the composition of the cluster from one iteration to a next iteration of cluster generation.