Centroid detection for clustering

• US 9,280,593 B1
• Filed: 07/24/2013
• Issued: 03/08/2016
• Est. Priority Date: 07/24/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dykstra, Aaron James, Chakravarthy, Diwakar, Dai, Siyang
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/949,526
• Time in Patent Office: 958 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• 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 for categorizing data points, comprising:

identifying a first number of centroids indicating how many centroids are to be used in evaluating a dataset;

selecting a location for the identified first number of centroids within the dataset;

performing a clustering procedure, comprising;

repeating a second number of times;

assigning, to data points within the dataset, a cluster based at least in part on a centroid location;

determining a center point of at least one cluster of the data points; and

moving the centroid location to the center point of its respective cluster;

adjusting the first number of centroids in the dataset and repeating the clustering procedure based at least in part on the movement of at least one centroid location by a delta amount; and

identifying at least one final centroid location.

2. The computer-implemented method of claim 1, wherein the final centroid location is identified when the movement of all of the centroid locations is less than a delta amount.

3. The computer-implemented method of claim 1, wherein the centroid locations are initially selected randomly.

4. The computer-implemented method of claim 1, wherein the center point is determined based at least in part on a meta-clustering technique.

5. The computer-implemented method of claim 1, wherein the delta identifies a confidence interval associated with the final centroid location.

6. The computer-implemented method of claim 1, wherein adjusting the first number of centroids in the dataset results in a new location of the identified first number of centroids.

7. The computer-implemented method of claim 6, wherein the new location of the identified first number of centroids is different from a previous location of the identified first number of centroids.

8. A computer-implemented method of categorizing data points, comprising:

selecting a number of centroids;

assigning, to data points, a cluster based at least in part on a location of the centroid;

determining a center point of the cluster of data points;

determining a difference between the location of the centroid and the center point of the cluster;

adjusting the number of centroids based at least in part on the difference between the location of the centroid and the center point of the cluster; and

identifying a final a centroid location based at least in part on the difference between the location of the centroid and the center point of the cluster.

9. The computer-implemented method of claim 8, wherein the data points are assigned to the cluster based at least in part on a vector distance from the centroid location.

10. The computer-implemented method of claim 8, wherein the cluster'"'"'s center point along an axis of a dataset is determined to be a mean average of all of that cluster'"'"'s data points along that axis.

11. The computer-implemented method of claim 8, wherein the cluster'"'"'s center point along an axis of a dataset is determined to be a median of all of that cluster'"'"'s data points along that axis.

12. The computer-implemented method of claim 8, wherein the number of centroids is adjusted by adding or removing one or more centroid locations.

13. The computer-implemented method of claim 8, further comprising, reporting a confidence level for a centroid location based at least in part on the difference between the location of the centroid and the center point of the cluster.

14. The computer-implemented method of claim 8, further comprising, causing the final centroid locations to be displayed to a device associated with a user.

15. The computer-implemented method of claim 8, wherein the cluster assignment is repeated a number of times.

16. The computer-implemented method of claim 15, wherein the number of times that the cluster assignment is repeated is chosen to provide an optimization level.