Method for Clustering Samples with Weakly Supervised Kernel Mean Shift Matrices

• US 20100332425A1
• Filed: 06/30/2009
• Published: 12/30/2010
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Tuzel, Cuneyt Oncel, Porikli, Fatih
• Granted Patent: US 8,296,248 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

A method clusters samples using a mean shift procedure. A kernel matrix is determined from the samples in a first dimension. A constraint matrix and a scaling matrix are determined from a constraint set. The kernel matrix is projected to a feature space having a second dimension using the constraint matrix, wherein the second dimension is higher than the first dimension. Then, the samples are clustered according to the kernel matrix.

Claims

1. A method for clustering samples using a mean shift procedure, comprising the a computer system for performing steps of the method, comprising the steps of:

determining a kernel matrix from the samples in a first dimension;

determining a constraint matrix and a scaling matrix from a constraint set;

projecting the kernel matrix to a feature space having a second dimension using the constraint matrix, wherein the second dimension is higher than the first dimension;

clustering the samples according to the kernel matrix.

2. The method of claim 1, further comprising:

determining a center of each cluster.

3. The method of claim 1, wherein the constraint set specifies pairs of samples to be clustered into the same cluster.

4. The method of claim 1, wherein the constraint set specifies pairs of samples to be clustered into different clusters.

5. The method of claim 1, wherein the clustering uses soft similarity constraints.

6. The method of claim 1, wherein the projecting is explicitly defined with a mapping function φ

of the samples.

7. The method of claim 1, wherein the kernel function is a symmetric matrix of inner products and the projecting is implicit.

8. The method of claim 1, wherein the projecting is orthogonal to the constraint vectors in the feature space.

9. The method of claim 1, wherein the projecting scales the samples along the constraint vectors in the feature space.

10. The method of claim 1, wherein the projecting preserves distances between the samples while satisfying the constraint set.

12. The method of claim 1, wherein the kernel matrix approximated by a low rank decomposition of the kernel matrix.

13. The method of claim 1, wherein the projecting operates directly on the kernel matrix according to the constraint matrix.

14. The method of claim 1, wherein the clustering uses an arbitrary distance metric.

15. The method of claim 1, wherein the clustering uses soft dissimilarity constraints.

11. The method of 1, wherein the samples lie on arbitrary manifolds.