MULTI-DISTANCE CLUSTERING
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.
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
{
p
(
x
1
,
a
)
,
ρ
(
x
2
,
a
)
}
}
8 . The non-transitory computer storage medium of claim 1 , where the functions further comprise:
reading, from an electronic data structure, a different 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−1 different distance functions, such that a given distance function has not been used to calculate the pair-wise similarities in the similarity matrix;
clustering the data points in the data set into n′ clusters based on the similarity matrix S′; and
comparing the n clusters and the n′ clusters and when the n clusters and the n′ clusters are similar, determining that the given distance function is not relevant to clustering for the data set.
9 . A computing system, comprising:
a processor;
multi-distance clustering logic configured to cause the processor to:
read 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;
cluster 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.
10 . The computing system of claim 9 , where the multi-distance clustering logic is configured to cause the processor to cluster 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.
11 . The computing system of claim 9 , where the multi-distance clustering logic is configured to cause the processor to cluster 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.
12 . The computing system of claim 11 where the multi-distance clustering logic is configured to cause the processor to iteratively cluster 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
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;
when the cross-cluster similarity indicates dissimilarity retaining the two sub-matrices; and
clustering each of the resulting m sub-matrices.
13 . A computer-implemented method comprising, with a processor:
reading, from an electronic data structure, 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.
14 . The computer-implemented method of claim 13 , further comprising, with the processor, 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.
15 . The computer-implemented method of claim 13 , further comprising, with the processor, 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.
16 . The computer-implemented method of claim 13 , further comprising, with the processor, 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.
17 . The computer-implemented method of claim 16 , further comprising, with the processor, 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.
18 . The computer-implemented method of claim 13 , further comprising, with the processor, 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.
19 . The computer-implemented method of claim 18 , further comprising, with the processor, 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
{
p
(
x
1
,
a
)
,
ρ
(
x
2
,
a
)
}
}
20 . The computer-implemented method of claim 13 , further comprising, with the processor:
reading, from an electronic data structure, a different 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−1 different distance functions, such that a given distance function has not been used to calculate the pair-wise similarities in the similarity matrix;
clustering the data points in the data set into n′ clusters based on the similarity matrix S′; and
comparing the n clusters and the n′ clusters and when the n clusters and the n′ clusters are similar, determining that the given distance function is not relevant to clustering for the data set.