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 having a multi-distance tri-point arbitration learning tool cause the multi-distance tri-point arbitration learning tool to perform corresponding functions, the functions comprising:
reading, by the multi-distance tri-point arbitration learning tool, 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, wherein the data set comprises data points corresponding to features extracted from electronic communications associated with a service such that each feature of each of the electronic communications is represented by a data point;
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 x i and x j by iteratively applying a rule set to the K per-distance tri-point arbitration similarities S D1 -S DK , wherein the rule set comprises:
i) a first rule to increase a level of similarity when the multi-distance tri-point similarity S and a per-distance tri-point similarity S D indicate that the pair of data points x i and x j are similar;
ii) a second rule to increase a level of dissimilarity when the multi-distance tri-point similarity S and the per-distance tri-point similarity S D indicate that the pair of data points x i and x j are dissimilar; and
iii) a third rule to adjust a level of similarity towards neutral when one of the multi-distance tri-point similarity S and the per-distance tri-point similarity S D indicate that the pair of data points x i and x j are similar and the other indicate that the pair of data points x i and x j are dissimilar;
clustering the data points in the data set into n clusters based on the similarity matrix S, where n is not determined prior to the clustering, wherein at least one of the n clusters is based upon data points of features indicative of an anomalous electronic communication attempting to access the service;
evaluating the n clusters to detect the at least one cluster comprising data points of features indicative of the anomalous electronic communication attempting to access the service; and
upon detecting that the at least one cluster comprising data points of features is indicative of the anomalous electronic communication attempting to access the service, executing an action to block the anomalous electronic communication from accessing the service.
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 pair-wise 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 S 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 multi-distance 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 x i and x j by:
determining that the data points x i and x j are similar when a dominating number of the K per-distance tri-point arbitration similarities S D1 -S DK indicate that the data points x i and x j are similar; and
determining that the data points x i and x j are dissimilar when a dominating number of the K per-distance tri-point arbitration similarities S D1 -S DK indicate that the data points x i and x j 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 the arbiter point a based on the following relationship, where p is the distance between points x 1 and x 2 using the respective distance function:
S
D
(
x
1
,
x
2
❘
a
)
=
min
{
ρ
D
(
x
1
,
a
)
,
ρ
D
(
x
2
,
a
)
}
-
ρ
D
(
x
1
,
x
2
)
max
{
ρ
D
(
x
1
,
x
2
)
,
min
{
ρ
D
(
x
1
,
a
)
,
ρ
D
(
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 the data set such that each feature of each of the electronic communications is represented by a data point, where each pair-wise multi-distance 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 multi-distance similarities in the similarity matrix S′;
clustering the data points in the data set into n′ clusters based on the multi-distance 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 having a multi-distance tri-point arbitration learning tool, comprising:
a processor connected to memory; and
a multi-distance tri-point arbitration learning tool stored on a non-transitory computer readable medium and configured with instructions that when executed by the processor cause the processor to:
read, by the multi-distance tri-point arbitration learning tool, 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, wherein the data set comprises data points corresponding to features extracted from electronic communications associated with a service such that each feature of each of the electronic communications is represented by a data point;
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 x i and x j by iteratively applying a rule set to the K per-distance tri-point arbitration similarities S D1 -S DK wherein the rule set comprises:
i) a first rule to increase a level of similarity when the multi-distance tri-point similarity S and a per-distance tri-point similarity S D indicate that the pair of data points x i and x j are similar;
ii) a second rule to increase a level of dissimilarity when the multi-distance tri-point similarity S and the per-distance tri-point similarity S D indicate that the pair of data points x i and x j are dissimilar; and
iii) a third rule to adjust a level of similarity towards neutral when one of the multi-distance tri-point similarity S and the per-distance tri-point similarity S D indicate that the pair of data points x i and x j are similar and the other indicate that the pair of data points x i and x j are dissimilar;
cluster the data points in the data set into n clusters based on the similarity matrix S, where n is not determined prior to the clustering, wherein at least one of the n clusters is based upon data points of features indicative of an anomalous electronic communication attempting to access the service;
evaluate the n clusters to detect the at least one cluster comprising data points of features indicative of the anomalous electronic communication attempting to access the service; and
upon detecting that the at least one cluster comprising data points of features is indicative of the anomalous electronic communication attempting to access the service, execute an action to block the anomalous electronic communication from accessing the service.
10. The computing system of claim 9 , where the multi-distance tri-point arbitration learning tool 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 pair-wise multi-distance similarity as recorded in the pair-wise 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 tri-point arbitration learning tool is configured to cause the processor to cluster the data set by:
iteratively partitioning the multi-distance 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 tri-point arbitration learning tool is configured to cause the processor to iteratively cluster the data set by, starting with the multi-distance 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 a multi-distance tri-point arbitration learning tool associated with a processor:
reading, by the multi-distance tri-point arbitration learning tool, 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, wherein the data set comprises data points corresponding to features extracted from electronic communications associated with a service such that each feature of each of the electronic communications is represented by a data point;
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 x i and x j by iteratively applying a rule set to the K per-distance tri-point arbitration similarities S D1 -S DK , wherein the rule set comprises:
i) a first rule to increase a level of similarity when the multi-distance tri-point similarity S and a per-distance tri-point similarity S D indicate that the pair of data points x i and x j are similar;
ii) a second rule to increase a level of dissimilarity when the multi-distance tri-point similarity S and the per-distance tri-point similarity S D indicate that the pair of data points x i and x j are dissimilar; and
iii) a third rule to adjust a level of similarity towards neutral when one of the multi-distance tri-point similarity S and the per-distance tri-point similarity S D indicate that the pair of data points x i and x j are similar and the other indicate that the pair of data points x i and x j are dissimilar;
clustering the data points in the data set into n clusters based on the multi-distance similarity matrix S, where n is not determined prior to the clustering, wherein at least one of the n clusters is based upon data points of features indicative of an anomalous electronic communication attempting to access the service;
evaluating the n clusters to detect the at least one cluster comprising data points of features indicative of the anomalous electronic communication attempting to access the service; and
upon detecting that the at least one cluster comprising data points of features is indicative of the anomalous electronic communication attempting to access the service, executing an action to block the anomalous electronic communication from accessing the service.
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 pair-wise 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 multi-distance 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 multi-distance similarity matrix S 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 multi-distance 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 x i and x j by:
determining that the data points x i and x j are similar when a dominating number of the K per-distance tri-point arbitration similarities S D1 -S DK , indicate that the data points x i and x j are similar; and
determining that the data points x i and x j are dissimilar when a dominating number of the K per-distance tri-point arbitration similarities S D1 -S DK , indicate that the data points x i and x j 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 the arbiter point a based on the following relationship, where p is the distance between the data points x i and x j using the respective distance function:
S
D
(
x
1
,
x
2
❘
a
)
=
min
{
ρ
D
(
x
1
,
a
)
,
ρ
D
(
x
2
,
a
)
}
-
ρ
D
(
x
1
,
x
2
)
max
{
ρ
D
(
x
1
,
x
2
)
,
min
{
ρ
D
(
x
1
,
a
)
,
ρ
D
(
x
2
,
a
)
}
}
.