# US 2021/0173869 A1 · Percentile linkage clustering

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

- Number: US 2021/0173869 A1
- Document ID: US20210173869A1
- Status: Published application
- Kind: A1
- Application number: 16/623,096
- Filed: 2018-08-30
- Published: 2021-06-10
- Earliest claimed: 2018-08-30
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Feng Li; Xuerui Wang
- Web page: https://patentgrep.com/patent/US20210173869A1

## CPC

- G06Q 30/0277: {Online advertisement}
- G06F 16/358: Browsing; Visualisation therefor
- G06F 16/906: Clustering; Classification
- G06F 16/953: Querying, e.g. by the use of web search engines
- G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
- G06V 10/7625: {Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms}
- G06V 10/763: {Non-hierarchical techniques, e.g. based on statistics of modelling distributions}
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06F 18/2321: using statistics or function optimisation, e.g. modelling of probability density functions
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for clustering data elements. In one aspect, a method includes determining a respective linkage value for each of multiple cluster pairs, where each cluster pair includes a respective first cluster and a respective second cluster. Determining a linkage value for a cluster pair includes determining a set of pairwise similarity values for the cluster pair. Each pairwise similarity value defines a similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair. The linkage value for the cluster pair is assigned as a given percentile of the set of pairwise similarity values, wherein the given percentile is greater than 0 and less than 100. A cluster pair is merged based on the linkage values of the cluster pairs.

## Claims

### Claim 1

A method implemented by a data processing apparatus, the method comprising, at each of one or more iterations:
obtaining data defining a current clustering a plurality of data elements, wherein the current clustering defines an assignment of each of the data elements to a respective cluster, and wherein each cluster represents a respective group of one or more data elements;
determining a respective linkage value for each of a plurality of cluster pairs, wherein each cluster pair comprises a respective first cluster defined by the current clustering and a respective second cluster defined by the current clustering, wherein determining a linkage value for a cluster pair comprises:
determining a set of pairwise similarity values for the cluster pair, wherein each pairwise similarity value defines a similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair; and
assigning, as the linkage value for the cluster pair, a given percentile of the set of pairwise similarity values, wherein the given percentile is greater than 0 and less than 100;
identifying a particular cluster pair to be merged based on the linkage values for the plurality of cluster pairs; and
updating the data defining the current clustering by merging the identified cluster pair.

### Claim 2 (depends on 1)

The method of claim 1, wherein at a first iteration of the one or more iterations, the clustering defines an assignment of each of the data elements to a different respective cluster.

### Claim 3 (depends on 1)

The method of claim 1, wherein identifying a particular cluster pair to be merged based on the linkage values for the plurality of cluster pairs comprises:
identifying a particular cluster pair with a highest linkage value.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
determining the highest linkage value is greater than a predetermined threshold linkage value.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
outputting the data defining the current clustering after a final iteration of the one or more iterations.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining a set of pairwise similarity values for the cluster pair, wherein each pairwise similarity value defines a similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair, comprises:
accessing a data store comprising pre-computed pairwise similarity values defining respective similarity measures between each pair of data elements of the plurality of data elements.

### Claim 7 (depends on 1)

The method of claim 1, wherein the data elements are keywords.

### Claim 8 (depends on 1)

The method of claim 1, wherein the similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair, characterizes a similarity between: (i) a particular set of search results obtained in response to providing the particular data element as a query to a search engine, and (ii) a given set of search results obtained in response to providing the given data element as a query to the search engine.

### Claim 9 (depends on 7)

The method of claim 7, further comprising, after a final iteration of the one or more iterations:
receiving a digital component request including a specific keyword;
determining that a particular digital component is eligible for transmission in response to the digital component request, including:
determining the particular digital component has distribution parameters which specify a keyword cluster which includes the specific keyword, wherein the keyword cluster is a cluster defined by the current clustering at the final iteration of the one or more iterations; and
transmitting the particular digital component in response to the digital component request.

### Claim 10

A system, comprising:
a data processing apparatus;
a memory in data communication with the data processing apparatus and storing instructions that cause the data processing apparatus to perform operations comprising, at each of one or more iterations:
obtaining data defining a current clustering a plurality of data elements, wherein the current clustering defines an assignment of each of the data elements to a respective cluster, and wherein each cluster represents a respective group of one or more data elements;
determining a respective linkage value for each of a plurality of cluster pairs, wherein each cluster pair comprises a respective first cluster defined by the current clustering and a respective second cluster defined by the current clustering, wherein determining a linkage value for a cluster pair comprises:
determining a set of pairwise similarity values for the cluster pair, wherein each pairwise similarity value defines a similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair; and
assigning, as the linkage value for the cluster pair, a given percentile of the set of pairwise similarity values, wherein the given percentile is greater than 0 and less than 100;
identifying a particular cluster pair to be merged based on the linkage values for the plurality of cluster pairs; and
updating the data defining the current clustering by merging the identified cluster pair.

### Claim 11 (depends on 10)

The system of claim 10, wherein at a first iteration of the one or more iterations, the clustering defines an assignment of each of the data elements to a different respective cluster.

### Claim 12 (depends on 10)

The system of claim 10, wherein identifying a particular cluster pair to be merged based on the linkage values for the plurality of cluster pairs comprises:
identifying a particular cluster pair with a highest linkage value.

### Claim 13 (depends on 12)

The system of claim 12, wherein the operations further comprise:
determining the highest linkage value is greater than a predetermined threshold linkage value.

### Claim 14 (depends on 10)

The system of claim 10, wherein the operations further comprise:
outputting the data defining the current clustering after a final iteration of the one or more iterations.

### Claim 15

One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising, at each of one or more iterations:
obtaining data defining a current clustering a plurality of data elements, wherein the current clustering defines an assignment of each of the data elements to a respective cluster, and wherein each cluster represents a respective group of one or more data elements;
determining a respective linkage value for each of a plurality of cluster pairs, wherein each cluster pair comprises a respective first cluster defined by the current clustering and a respective second cluster defined by the current clustering, wherein determining a linkage value for a cluster pair comprises:
determining a set of pairwise similarity values for the cluster pair, wherein each pairwise similarity value defines a similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair; and
assigning, as the linkage value for the cluster pair, a given percentile of the set of pairwise similarity values, wherein the given percentile is greater than 0 and less than 100;
identifying a particular cluster pair to be merged based on the linkage values for the plurality of cluster pairs; and
updating the data defining the current clustering by merging the identified cluster pair.

### Claim 16 (depends on 15)

The non-transitory media of claim 15, wherein at a first iteration of the one or more iterations, the clustering defines an assignment of each of the data elements to a different respective cluster.

### Claim 17 (depends on 15)

The non-transitory media of claim 15, wherein identifying a particular cluster pair to be merged based on the linkage values for the plurality of cluster pairs comprises:
identifying a particular cluster pair with a highest linkage value.

### Claim 18 (depends on 17)

The non-transitory media of claim 17, wherein the operations further comprise:
determining the highest linkage value is greater than a predetermined threshold linkage value.

### Claim 19 (depends on 15)

The non-transitory media of claim 15, wherein the operations further comprise:
outputting the data defining the current clustering after a final iteration of the one or more iterations.

### Claim 20 (depends on 15)

The non-transitory media of claim 15, wherein determining a set of pairwise similarity values for the cluster pair, wherein each pairwise similarity value defines a similarity measure between: (i) a particular data element from the first cluster of the cluster pair, and (ii) a given data element from the second cluster of the cluster pair, comprises:
accessing a data store comprising pre-computed pairwise similarity values defining respective similarity measures between each pair of data elements of the plurality of data elements.
