ACCELERATED DISCRETE DISTRIBUTION CLUSTERING UNDER WASSERSTEIN DISTANCE

• US 20170083608A1
• Filed: 09/30/2016
• Published: 03/23/2017
• Est. Priority Date: 11/19/2012
• Status: Active Grant

• Current Assignee: Penn State Research Foundation
• Original Assignee: Penn State Research Foundation
• Inventors: Ye, Jianbo, Li, Jia, Wang, James Z.
• Granted Patent: US 10,013,477 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

Computationally efficient accelerated D2-clustering algorithms are disclosed for clustering discrete distributions under the Wasserstein distance with improved scalability. Three first-order methods include subgradient descent method with re-parametrization, alternating direction method of multipliers (ADMM), and a modified version of Bregman ADMM. The effects of the hyper-parameters on robustness, convergence, and speed of optimization are thoroughly examined. A parallel algorithm for the modified Bregman ADMM method is tested in a multi-core environment with adequate scaling efficiency subject to hundreds of CPUs, demonstrating the effectiveness of AD2-clustering.

Claims

1. A method of clustering complex data objects, comprising the steps of:

a) performing an initial segmentation of the data objects;

b) performing a series of discrete distribution (D2) clustering operations on the data objects using a scalable method to optimize a set of Wassersrtein centroids within each segment;

c) combining the centroids determined in step b) into one data set and performing a segmentation of this data set;

d) iteratively repeating steps b) and c) at higher levels in a hierarchy, if necessary, until a single segmentation is achieved, the number of centroids is reduced to an acceptable level, or another stopping criterion is satisfied; and

wherein the D2 clustering operations are performed by parallel processors or a single processor in sequence.

2. The method of claim 1, wherein the method to optimize the set of Wassersrtein centroids is a subgradient descent method with re-parametrization.

3. The method of claim 1, wherein the method used to optimize the set of Wassersrtein centroids is an alternating direction method of multipliers (ADMM).

4. The method of claim 1, wherein the method to optimize the set of Wassersrtein centroids s is a Bregman alternating direction method of multipliers (ADMM) approach.

5. The method of claim 1, wherein the objects to be clustered are mathematically represented as bags of weighted vectors.

6. The method of claim 1, wherein the objects to be clustered are mathematically represented as a histogram.

7. The method of claim 1, wherein the segmentation of the data points is based upon adjacency.

8. The method of claim 1, wherein a master processor performs the initial data segmentation step and 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 1, wherein the series of discrete distribution (D2) clustering operations are performed by physically separate parallel processors or separate cores of an integrated device.

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

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

12. The method of claim 1, wherein the data points are associated with images or video.

13. The method of claim 1, wherein the data points are associated with a biological process or genetic sequence.