# US 2018/0322363 A1 · Multi-distance clustering

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0322363 A1
- Document ID: US20180322363A1
- Status: Published application
- Kind: A1
- Application number: 16/037,116
- Filed: 2018-07-17
- Published: 2018-11-08
- Earliest claimed: 2015-03-26
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Aleksey M. URMANOV; Alan Paul WOOD; Anton A. BOUGAEV
- Web page: https://patentgrep.com/patent/US20180322363A1

## CPC

- G06N 20/00: Machine learning
- G06F 15/76: Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16)
- G06F 16/906: Clustering; Classification
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
- G06F 18/23213: with fixed number of clusters, e.g. K-means clustering
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06F 2216/03: Data mining
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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, wherein the data set comprises data points corresponding to features extracted from electronic communications associated with a service;
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;
evaluating the n clusters to detect a cluster comprising data points of features indicative of anomalous electronic communication attempting to access the service; and
executing an action to block the anomalous electronic communication from accessing the service.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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 mth eigenvectors; and
clustering each of the resulting m sub-matrices.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 1)

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 D1-DK, calculating K per-distance tri-point arbitration similarities SD1-SDK between a pair of data points xi and xj 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.

### Claim 7 (depends on 6)

The non-transitory computer storage medium of claim 6, where the functions comprise computing the per-distance tri-point similarity between points x1 and x2 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


{
ρ
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
)
}
}

### Claim 8 (depends on 1)

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.

### Claim 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, wherein the data set comprises data points corresponding to features extracted from electronic communications associated with a service;
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;
evaluate the n clusters to detect a cluster comprising data points of features indicative of anomalous electronic communication attempting to access the service; and
execute an action to block the anomalous electronic communication from accessing the service.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 9)

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.

### Claim 12 (depends on 11)

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 mth 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.

### Claim 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, wherein the data set comprises data points corresponding to features extracted from electronic communications associated with a service;
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;
evaluating the n clusters to detect a cluster comprising data points of features indicative of anomalous electronic communication attempting to access the service; and
executing an action to block the anomalous electronic communication from accessing the service.

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 13)

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.

### Claim 16 (depends on 13)

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 mth eigenvectors; and
clustering each of the resulting m sub-matrices.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 13)

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 D1-DK, calculating K per-distance tri-point arbitration similarities SD1-SDK between a pair of data points xi and xj 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.

### Claim 19 (depends on 18)

The computer-implemented method of claim 18, further comprising, with the processor, computing the per-distance tri-point similarity between points x1 and x2 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


{
ρ
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
)
}
}

### Claim 20 (depends on 13)

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 D1-DK, calculating K per-distance tri-point arbitration similarities SD1-SDK between a pair of data points xi and xj with respect to an arbiter point a; and
computing a multi-distance tri-point arbitration similarity S between the data points by iteratively applying a rule set to the K per-distance tri-point arbitration similarities SD1-SDK, 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 SD indicate that the pair of data points 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 SD indicate that the pair of data points 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 SD indicate that the pair of data points are similar and the other indicate that the pair of data points are dissimilar.
