Multi-distance clustering

Patent metadata

Field	Value
Publication number	US-2016283533-A1
Application number	US-201514669792-A
Country	US
Kind code	A1
Filing date	Mar 26, 2015
Priority date	Mar 26, 2015
Publication date	Sep 29, 2016
Grant date	—

Abstract

Systems, methods, and other embodiments associated with multi-distance clustering are described. In one embodiment, a method includes reading a multi-distance similarity matrix S that records pair-wise multi-distance similarities between respective pairs of data points in a data set. Each pair-wise similarity is based on distances between a pair of data points calculated using K different distance functions, where K is greater than one. The method includes clustering the data points in the data set into n clusters based on the similarity matrix S. The number of clusters n is not determined prior to the clustering.

First claim

What is claimed is:

1 . A non-transitory computer storage medium storing computer-executable instructions that when executed by a computer cause the computer to perform corresponding functions, the functions comprising:
reading a multi-distance similarity matrix S that records pair-wise multi-distance similarities between respective pairs of data points in a data set, where each pair-wise similarity is based on distances between a pair of data points calculated using K different distance functions, where K is greater than one; clustering the data points in the data set into n clusters based on the similarity matrix S; and where n is not determined prior to the clustering.

2 . The non-transitory computer storage medium of claim 1 , where the functions comprise clustering the data points in the data set by, until no un-clustered data points remain:
selecting a pair of data points having a relatively large multi-distance similarity as recorded in the similarity matrix S; and creating a cluster that includes the selected pair of data points by adding data points to the cluster that are similar to any point in the cluster.

3 . The non-transitory computer storage medium of claim 1 , where the functions comprise clustering the data set by:
iteratively partitioning the similarity matrix S into n sub-matrices using spectral theory, where each sub-matrix corresponds to a cluster; and ceasing partitioning when all sub-matrices are mutually dissimilar.

4 . The non-transitory computer storage medium of claim 1 , where the functions comprise iteratively clustering the data set by, starting with the similarity matrix as a sub-matrix:
clustering the sub-matrix by:
using an objective function to compute a Laplacian matrix of the sub-matrix;
computing eigenvalues and corresponding eigenvectors for the Laplacian matrix and ordering the eigenvalues in ascending order such that the first eigenvalue is equal to zero;
identifying m eigenvalues that are equal to zero; and
when m is greater than one, partitioning the sub-matrix into m sub-matrices based on the second through the m th eigenvectors; and
clustering each of the resulting m sub-matrices.

5 . The non-transitory computer storage medium of claim 4 , where the functions comprise, when a sub-matrix has a single eigenvalue equal to zero:
partitioning indices of the sub-matrix into two sub-matrices based on the second eigenvector, such that one of the two sub-matrices contains data vectors with indices corresponding to elements of the second eigenvector that indicate similarity and the other of the two sub-matrices contains data vectors with indices corresponding to elements of the second eigenvector that indicate dissimilarity; determining a cross-cluster similarity between the two sub-matrices; retaining the two sub-matrices when the cross-cluster similarity indicates dissimilarity; and discarding the two sub-matrices when the cross-cluster similarity indicates that the two sub-matrices are similar.

6 . The non-transitory computer storage medium of claim 1 , where the functions comprise computing each pairwise similarity in the similarity matrix S by:
using a K different distance functions D 1 -D K , calculating K per-distance tri-point arbitration similarities S D1 -S DK between a pair of data points x i and x j with respect to an arbiter point a; and computing a multi-distance tri-point arbitration similarity S between the data points by:
determining that the data points are similar when a dominating number of the K per-distance tri-point arbitration similarities indicate that the data points are similar; and
determining that the data points are dissimilar when a dominating number of the K per-distance tri-point arbitration similarities indicate that the data points are dissimilar.

7 . The non-transitory computer storage medium of claim 6 , where the functions comprise computing the per-distance tri-point similarity between points x 1 and x 2 with respect to arbiter a based on the following relationship, where ρ is the distance between points using the respective distance function:

S
D



(

x
1

,

x
2


a

)



=



min




{

ρ


(

x
1

,
a

)

,



ρ


(

x
2

,
a

)

}

-

ρ


(

x
1

,

x
2

)

max




{

p


(

x
1

,

x
2

)

,

min


Assignees

• Oracle Int Corp

Inventors

• Urmanov Aleksey M
• Wood Alan Paul
• Bougaev Anton A

Classifications

• G06F16/285 Primary

  Clustering or classification · CPC title

• G06F17/30598

  Physics · mapped topic

• G06F17/30324 Primary

  Physics · mapped topic