Data clustering employing mapping and merging

Abstract

A data-clustering method generates data clusters for a set of data points. A region of interest containing the data points and a center matrix for the region of interest are defined, where the center matrix includes an array of center points defining centers of overlapping circles. The data points are mapped to corresponding circles based on near center points. Pairs of overlapping circles are merged based on relative numbers of data points lying in overlap regions of the pairs of overlapping circles compared to total numbers of data points within the corresponding circles. Circles belonging to the one or more data clusters are identified based on merged pairs of overlapping circles, and data points belonging to the one or more data clusters are identified based on the corresponding circles. The method may be performed by a computer having a heterogeneous architecture with parallel processors.

The invention claimed is: 
     
       1. A computer-implemented method for generating one or more data clusters for a set of data points, wherein the computer includes a central processing unit (CPU), a plurality of parallel processing units and a system memory shared by the CPU and the parallel processing units, the method comprising:
 (a) the CPU defining a region of interest containing the data points by:
 (a1) identifying smallest and largest coordinate values of the data points to identify an initial region of interest containing the data points; and 
 (a2) if the initial region of interest is not equilateral, then increasing the size of the initial region of interest in one or more dimensions to define an equilateral region of interest containing the data points; 
 
 (b) the CPU defining a center matrix for the region of interest, wherein the center matrix comprises an array of center points defining centers of overlapping circles; 
 (c) the parallel processing units mapping the data points to corresponding circles based on near center points; 
 (d) the CPU determining whether to merge adjacent pairs of overlapping circles based on the mapped data points; 
 (e) the CPU identifying circles belonging to the one or more data clusters based on merged pairs of overlapping circles; and 
 (f) the CPU identifying data points belonging to the one or more data clusters based on the identified circles. 
 
     
     
       2. The method of  claim 1 , wherein:
 the circles have radii of identical length such that each data point is located within either a single circle or the overlap region between two or more circles. 
 
     
     
       3. The method of  claim 1 , wherein step (c) comprises:
 (c1) calculating a distance from each data point to each center point; and 
 (c2) if the distance between a data point and a center point is determined to be less than or equal to the radius of the circle corresponding to the center point, then determining that the data point is located within the circle; otherwise, determining that the data point is not located within the circle. 
 
     
     
       4. The method of  claim 1 , wherein the computer determines whether to merge adjacent pairs of overlapping circles based on relative numbers of data points lying in overlap regions of the adjacent pairs of overlapping circles compared to total numbers of data points within the corresponding circles. 
     
     
       5. The method of  claim 4 , wherein step (d) comprises, for two overlapping circles that share an overlap region:
 (d1) generating overlap metrics relating the number of data points in the overlap region to the total number of data points in each corresponding overlapping circle; and 
 (d2) determining whether to merge the two overlapping circles into a merged pair based on the overlap metrics. 
 
     
     
       6. The method of  claim 1 , wherein step (e) comprises traversing a relation graph of the merged pairs of overlapping circles to identify one or more circles belonging to each different data cluster. 
     
     
       7. A computer system for generating one or more data clusters for a set of data points, the computer system comprising:
 a central processing unit (CPU); 
 a plurality of parallel processing units; and 
 system memory shared by the CPU and the parallel processing units, wherein the computer system implements a data-clustering algorithm by:
 (a) the CPU defining a region of interest containing the data points; 
 (b) the CPU defining a center matrix for the region of interest, wherein the center matrix comprises an array of center points defining centers of overlapping circles; 
 (c) the parallel processing units mapping the data points to corresponding circles based on near center points; 
 (d) the CPU determining whether to merge adjacent pairs of overlapping circles based on the mapped data points; 
 (e) the CPU identifying circles belonging to the one or more data clusters based on merged pairs of overlapping circles; and 
 (f) the CPU identifying data points belonging to the one or more data clusters based on the identified circles, wherein the parallel processing unites map the data points by: 
 (c1) calculating a distance from each data point to each center point; and 
 (c2) if the distance between a data point and a center point is less than or equal to the radius of the circle corresponding to the center point, then determining that the data point is located within the circle, otherwise, determining that the data point is not located within the circle. 
 
 
     
     
       8. The computer system of  claim 7 , wherein the parallel processing units are graphics processing units. 
     
     
       9. The computer system of  claim 7 , wherein the computer system is configured to define the region of interest by normalizing the coordinate values of the data points to be relative to a point within the region of interest. 
     
     
       10. The computer system of  claim 7 , wherein:
 the circles have radii of identical length such that each data point is located within either a single circle or the overlap region between two or more circles. 
 
     
     
       11. A computer system for generating one or more data clusters for a set of data points, the computer system comprising:
 a central processing unit (CPU); 
 a plurality of parallel processing units; and 
 system memory shared by the CPU and the parallel processing units, wherein the computer system implements a data-clustering algorithm by:
 (a) the CPU defining a region of interest containing the data points; 
 (b) the CPU defining a center matrix for the region of interest, wherein the center matrix comprises an array of center points defining centers of overlapping circles; 
 (c) the parallel processing units mapping the data points to corresponding circles based on near center points; 
 (d) the CPU determining whether to merge adjacent pairs of overlapping circles based on relative numbers of data points lying in overlap regions of the adjacent pairs of overlapping circles compared to total numbers of data points within the corresponding circles; 
 (e) the CPU identifying circles belonging to the one or more data clusters based on merged pairs of overlapping circles; and 
 (f) the CPU identifying data points belonging to the one or more data clusters based on the identified circles. 
 
 
     
     
       12. The computer system of  claim 11 , wherein, for two overlapping circles that share an overlap region, the computer system is configured to determine whether to merge pairs of overlapping circles by:
 (d1) generating overlap metrics relating the number of data points in the overlap region to the total number of data points in each corresponding overlapping circle; and 
 (d2) determining whether to merge the two overlapping circles into a merged pair based on the overlap metrics. 
 
     
     
       13. A computer system for generating one or more data clusters for a set of data points, the computer system comprising:
 a central processing unit (CPU); 
 a plurality of parallel processing units; and 
 system memory shared by the CPU and the parallel processing units, wherein the computer system implements a data-clustering algorithm by:
 (a) the CPU defining a region of interest containing the data points; 
 (b) the CPU defining a center matrix for the region of interest, wherein the center matrix comprises an array of center points defining centers of overlapping circles; 
 (c) the parallel processing units mapping the data points to corresponding circles based on near center points; 
 (d) the CPU determining whether to merge adjacent pairs of overlapping circles based on the mapped data points; 
 (e) the CPU identifying circles belonging to the one or more data clusters based on merged pairs of overlapping circles; and 
 (f) the CPU identifying data points belonging to the one or more data clusters based on the identified circles by traversing a relation graph of the merged pairs of overlapping circles to identify one or more circles belonging to each different data cluster.