Massive clustering of discrete distributions

• US 9,720,998 B2
• Filed: 11/15/2013
• Issued: 08/01/2017
• Est. Priority Date: 11/19/2012
• Status: Active Grant

• Current Assignee: Penn State Research Foundation (Pennsylvania State University)
• Original Assignee: Penn State Research Foundation (Pennsylvania State University)
• Inventors: Wang, James Z., Li, Jia, Zhang, Yu
• Primary Examiner(s): Thomas, Ashish K
• Assistant Examiner(s): Mahmood, Rezwanul
• Application Number:
  US14/081,525
• Publication Number:
  US 20140143251A1
• Time in Patent Office: 1,355 Days
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

The trend of analyzing big data in artificial intelligence requires more scalable machine learning algorithms, among which clustering is a fundamental and arguably the most widely applied method. To extend the applications of regular vector-based clustering algorithms, the Discrete Distribution (D2) clustering algorithm has been developed for clustering bags of weighted vectors which are well adopted in many emerging machine learning applications. The high computational complexity of D2-clustering limits its impact in solving massive learning problems. Here we present a parallel D2-clustering algorithm with substantially improved scalability. We develop a hierarchical structure for parallel computing in order to achieve a balance between the individual-node computation and the integration process of the algorithm. The parallel algorithm achieves significant speed-up with minor accuracy loss.

Claims

1. A method of determining similarities in still or moving images utilizing a hierarchical structure including a base level and higher levels, the method comprising the steps of:

a) performing an initial segmentation of data objects in the base level into a plurality of segments using a master processor, each object being representative of a different image or video, the data objects included in the base level of the hierarchy being original data objects and a data set of the base level;

b) performing a discrete distribution (D2) clustering on each of the segments on one or more slave processors to determine a group of clusters within the segment, each of the clusters corresponding to a local centroid;

c) combining the local centroids within all of the segments determined in step b) into one global data set of local centroids and performing an initial segmentation of this global data set of local centroids into a plurality of segments using the master processor, the global data set of local centroids representing a higher level of the hierarchy, a size of the data set of the higher level being smaller than a size of data set of the previous level;

d) iteratively repeating steps b) and c) at higher levels in the hierarchy until a single segmentation of the data objects is achieved, the number of centroids is reduced to a predefined number, or a predefined threshold based on distances of the data objects to the centroids is satisfied; and

e) outputting information regarding the way in which the data objects are clustered in terms of similarity.

2. The method of claim 1, wherein the initial segmentation of the data objects is based upon adjacency.

3. The method of claim 1, wherein the D2 clustering operations are performed by parallel slave processors.

4. The method of claim 1, wherein the D2 clustering operations are performed by the slave processors in sequence.

5. The method of claim 1, including the steps of:

assigning different cluster labels to the data objects within each segment; and

optimizing the cluster labels of each data object to determine the local centroids.

6. The method of claim 1, including the step of imposing one or more constraints on the centroids passed to each level in the hierarchy.

7. The method of claim 1, wherein the cluster centroids passed to successively higher levels are weighted to maintain equal contributions from each original data object.

8. The method of claim 1, wherein the master processor distributes the data segments to different parallel slave processors to perform the D2-clustering at each level in the hierarchy.

9. The method of claim 8, including the use of synchronized Message Passing Interface (MPI) and MapReduce techniques to perform message passing and data transmission between the master and slave processors.

10. The method of claim 1, wherein the objects to be clustered are mathematically represented by discrete distributions or bags of weighted vectors.

11. The method of claim 1, wherein the series of discrete distribution (D2) clustering operations are performed by physically separate parallel processors or separate cores of an integrated device.

12. The method of claim 1, the step of performing an initial segmentation in a) or c) comprising:

a) performing an initial clustering of the data objects or data set using a constrained discrete distribution (D2) clustering algorithm to divide the data into segments;

b) performing a series of constrained D2 clustering operations on one or more of the segments to divide the data into additional segments, if necessary; and

c) iteratively repeating step b), if necessary, until the size of each segment is reduced to an acceptable level, the number of segments increased to an acceptable level, or another stopping criterion is satisfied.

13. The method of claim 12, wherein the constraint includes a fixed weighting scheme on the support vectors of the discrete distributions that are the cluster centroids.

14. The method of claim 5, wherein the step of optimizing the cluster labels comprises iteration of updating the clusters based on nearest centroids from each data object and updating the centroids based on the updated clusters.

15. The method of claim 1, including the steps of assigning, at the master processor, each centroid as a cluster label to the data object in the corresponding cluster, the label propagating to all descendent in the previous levels.

16. The method of claim 1, wherein the combination of the local centroids of all of the segments in a hierarchical level is different from a set of centroids obtained if a D2-clustering is directly performed on all data of the data set in the hierarchical level.

17. A method of determining similarities in a biological process or genetic sequence utilizing a hierarchical structure including a base level and higher levels, the method comprising the steps of:

a)) performing a segmentation of data objects in the base level into a plurality of segments using a master processor, each data object being representative of a different biological process or genetic sequence, the data objects included in the base level of the hierarchy being original data objects and a data set of the base level;

b) performing a discrete distribution (D2) clustering on each of the segments on one or more slave processors to determine a group of dusters within each of the segments, each of the clusters corresponding to a local centroid;

c) combining the local centroids within all of the segments determined in step b) into one global data set of local centroids and performing a segmentation of this global data set of local centroids into a plurality of segments using the master processor, the global data set of local centroids representing a higher level of the hierarchy, a size of the data set of the higher level being smaller than a size of the data set of the previous level;

d) iteratively repeating steps b) and c) at higher levels in the hierarchy until a single segmentation of the data objects is achieved, the number of centroids is reduced to a predefined number, or a predefined threshold based on distances of the data objects to the centroids is satisfied; and

e) outputting information regarding the way in which the data objects are clustered in terms of similarity.