# US 2012/0254183 A1 · Method and System for Clustering Data Points

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

- Number: US 2012/0254183 A1
- Document ID: US20120254183A1
- Status: Published application
- Kind: A1
- Application number: 13/128,333
- Filed: 2009-11-10
- Published: 2012-10-04
- Earliest claimed: 2008-11-10
- Assignees: Google Inc.
- Inventors: Nir Ailon; Edo Liberty; Harishabd Khalsa
- Web page: https://patentgrep.com/patent/US20120254183A1

## CPC

- G06F 16/355: Creation or modification of classes or clusters
- G06F 16/285: {Clustering or classification}
- G06F 16/40: of multimedia data, e.g. slideshows comprising image and additional audio data (retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70)
- G06F 16/90: Details of database functions independent of the retrieved data types
- G06F 16/906: Clustering; Classification
- G06F 18/23211: with adaptive number of clusters
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods for clustering a group of data points based on a measure of similarity between each pair of data points in the group are provided. A pairwise similarity function can be estimated for each pair of data points in the group. A clustering algorithm can be executed to create clusters and associate data points with the clusters using the pairwise similarity function. The algorithm can be iterated multiple times until a stopping condition is reached in order to reduce variance in the output of the algorithm. The pairwise similarity function for each pair of data points can be updated between iterations of the algorithm and the results of each iteration can be aggregated. The data in each data point associated with a cluster can be consolidated into a consolidated data point.

## Claims

### Claim 1

A computer-implemented method for generating a cluster of data points from a set of data points, the method comprising the steps of:
selecting, by a computer, a first data point from the set of data points;
providing, by the computer, for a first cluster;
associating, by the computer, the first data point with the first cluster;
evaluating, by the computer, a similarity function comprising a value measuring a similarity of the first data point and each remaining data point in the set of data points to determine if each remaining data point is similar to the first data point;
associating, by the computer, each remaining data point that is determined to be similar to the first data point with the first cluster; and
consolidating, by the computer, data stored in data points associated with the first cluster to create a consolidated data point.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein the first data point is randomly selected.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, further comprising the step of outputting, by the computer, the consolidated data point.

### Claim 4

A computer program product comprising:
a computer-readable medium having computer-readable program code embodied therein for grouping a set of data points, the computer-readable program code in the computer program product comprising:
computer-readable program code for estimating a similarity function for each pair of data points in the set of data points, the similarity function comprising a value corresponding to a similarity between each respective pair of data points in the set of data points; and
computer-readable program code for executing an algorithm for grouping the set of data points for at least one iteration, wherein the algorithm comprises the steps of:
selecting a first data point from the set of data points;
providing for a first cluster;
associating the first data point with the first cluster;
evaluating a similarity function comprising a value measuring a similarity of the first data point and each remaining data point in the set of data points to determine if each remaining data point is similar to the first data point;
associating each remaining data point that is determined to be similar to the first data point with the first cluster; and
updating each respective similarity function.

### Claim 5 (depends on 4)

The computer program product of claim 4, further comprising:
computer readable program code for counting a number of iterations of the algorithm; and
computer-readable program code for terminating the execution of the algorithm based on the number of iterations of the algorithm.

### Claim 6 (depends on 4)

The computer program product of claim 4, wherein each respective similarity function is updated based on whether the data points corresponding to each respective similarity function are in the same cluster.

### Claim 7 (depends on 4)

The computer program product of claim 4, further comprising:
computer-readable program code for counting a number of iterations of the algorithm;
computer-readable program code for counting a number of iterations of the algorithm for which the first data point and a second data point are both associated with the first cluster.

### Claim 8 (depends on 7)

The computer program product of claim 7, wherein each respective similarity function is updated based on a ratio of the number of iterations of the algorithm for which the first data point and the second data point are both associated with the first cluster to the number of iterations of the algorithm.

### Claim 9 (depends on 4)

The computer program product of claim 4, wherein the first data point is selected using at least one of a random process and a pseudo-random process.

### Claim 10

A system for generating a cluster of data points from a set of data points, the system comprising:
a clustering module for executing an algorithm for grouping the set of data points for at least one iteration, wherein the algorithm comprises the steps of:
selecting a first data point from the set of data points;
providing for a first cluster;
associating the first data point with the first cluster;
evaluating a similarity function comprising a value measuring a similarity of the first data point and each remaining data point in the set of data points to determine if each remaining data point is similar to the first data point; and
associating each remaining data point that is determined to be similar to the first data point with the first cluster;
a similarity updating module for updating each respective similarity function.

### Claim 11 (depends on 10)

The system of claim 10, further comprising a similarity estimating module for estimating a similarity function for each pair of data points in the set of data points.

### Claim 12 (depends on 10)

The system of claim 10, wherein each respective similarity function is updated based on whether the data corresponding to each respective similarity function are in the same cluster.

### Claim 13 (depends on 12)

The system of claim 12, further comprising:
a first counter for counting a number of iterations of the algorithm; and
a second counter for counting a number of iterations of the algorithm for which the first data point and a second data point are both associated with the first cluster.

### Claim 14 (depends on 13)

The system of claim 13, wherein each respective similarity function is updated based on a ratio of the second counter to the first counter.

### Claim 15 (depends on 10)

The system of claim 10, wherein the first data point is selected using at least one of a random process and a pseudo-random process.

### Claim 16

A computer-implemented method for generating clusters of data points from a set of data points, the method comprising the steps of:
(a) selecting, by a computer, a data point from the set of data points;
(b) providing, by the computer, for a cluster;
(c) associating, by the computer, the selected data point with the cluster;
(d) evaluating, by the computer, a similarity function comprising a value measuring a similarity of the selected data point and each remaining data point in the set of data points to determine if each remaining data point is similar to the selected data point;
(e) associating, by the computer, each remaining data point that is determined to be similar to the selected data point with the cluster;
(f) determining, by the computer, whether there are any data points in the set of data points that have not been associated with a cluster; and
(g) based on a determination that there is at least one data point remaining in the set of data points that has not been associated with a cluster, repeating steps (a) through (f) using only the data points that have not been associated with a cluster until all of the data points originally in the set of data points have been associated with a cluster.

### Claim 17 (depends on 16)

The computer-implemented method of claim 16, wherein the selected data point is selected randomly or pseudo-randomly.

### Claim 18 (depends on 16)

The computer-implemented method of claim 16, further comprising the step of:
(h) repeating steps (a) through (g) until a stopping point is reached.

### Claim 19 (depends on 18)

The computer-implemented method of claim 18, wherein the stopping point is based on a measure of transitivity of the data points.

### Claim 20 (depends on 16)

The computer-implemented method of claim 16, further comprising the steps of:
(h) repeating steps (a) through (g) for a number of iterations; and
(i) aggregating the results of each execution of steps (a) through (h).

### Claim 21 (depends on 16)

The computer-implemented method of claim 16, wherein each data point comprises a pairwise similarity function for each other data point in the set of data points, each pairwise similarity function comprising a measure of similarity between the data point and the other data point.

### Claim 22 (depends on 21)

The computer-implemented method of claim 21, further comprising the step of:
(h) updating, by the computer, the pairwise similarity function for a pair of data points to reflect that the pair of data points are similar if the pair of data points are associated with the same cluster.

### Claim 23 (depends on 22)

The computer-implemented method of claim 22, wherein the updated pairwise similarity function is used for successive iterations of steps (a) through (g).

### Claim 24 (depends on 16)

The computer-implemented method of claim 16, further comprising the steps of:
repeating steps (a) through (g) for a number of iterations;
determining, by the computer, for one of the data points, a number of iterations that the one data point was associated with the same cluster as each other data point;
determining, by the computer, for the one data point and each other data point, a ratio of the number of iterations that the data point was associated with the same cluster as the other data point to the number of iterations of steps (a) through (g); and
updating, by the computer, for the data point and each other data point, a similarity function for the pair of data points based on the ratio.

### Claim 25 (depends on 24)

The computer-implemented method of claim 24, further comprising the step of repeating steps (a) through (g) using the updated similarity function.
