# US 9,519,705 B2 · Method and apparatus for selecting clusterings to classify a data set

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

- Number: US 9,519,705 B2
- Document ID: US9519705B2
- Status: Granted
- Kind: B2
- Application number: 13/979,196
- Filed: 2012-01-23
- Published: 2014-01-02
- Granted: 2016-12-13
- Earliest claimed: 2011-01-25
- Assignees: President and Fellows of Harvard College
- Applicants: Gary King; Justin Grimmer
- Inventors: Gary King; Justin Grimmer
- Web page: https://patentgrep.com/patent/US9519705B2

## CPC

- G06F 16/35: Clustering; Classification
- G06F 16/355: Creation or modification of classes or clusters
- G06F 18/23: Clustering techniques
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In a computer assisted clustering method, a clustering space is generated from fixed basis partitions that embed the entire space of all possible clusterings. A lower dimensional clustering space is fu-reated from the space of all possible clusterings by isometrically embedding the space of all possible clusterings in a lower dimensional Euclidean space. This lower dimensional space is then sampled based on the number of documents in the corpus. Partitions are then developed based on the samples that tessellate the space. Finally, using clusterings representative of these tessellations, a two-dimensional representation for users to explore is created.

## Claims

### Claim 1

A method for selecting clusterings to classify a data set, the method implemented in a data processor having a memory and a display and comprising:
a) using the data processor to create a lower dimensional space of all possible clusterings and storing the space in the memory, each clustering being associated with an allocation of objects to be clustered and corresponding to a point in the lower dimensional space;
b) using the data processor to sample the stored lower dimensional space based on a number of objects in the data set;
c) using the data processor to build partitions based on the samples that tessellate the lower-dimensional space of all possible clusterings, the clusterings being tessellated based on similarities among the objects in the associated allocations;
d) using the data processor to select partitions and determine remaining point locations in the lower dimensional space;
e) using the data processor to project the points of the lower dimensional space to a two dimensional array of points; and
f) displaying, on the display, points in the two-dimensional array.

### Claim 2 (depends on 1)

The method of claim 1 wherein step (a) comprises using the data processor to embed a space of all possible clusterings into a lower dimensional Euclidean space.

### Claim 3 (depends on 2)

The method of claim 2 wherein step (b) comprises using the data processor to randomly sample the lower dimensional Euclidean space.

### Claim 4 (depends on 2)

The method of claim 2 wherein step (b) comprises using the data processor to sample the lower dimensional Euclidean space by selecting at least some partitions of interest to a user.

### Claim 5 (depends on 1)

The method of claim 1 wherein step (c) comprises using the data processor to find a partition that is approximately the closest partition to each sample generated in step (b).

### Claim 6 (depends on 5)

The method of claim 5 wherein the objects are documents and step (c) comprises using the data processor to score pairs of documents and to select the smallest scores.

### Claim 7 (depends on 6)

The method of claim 6 further comprising using the data processor to sequentially add coordinates with small scores while maintaining pairings necessary to ensure that only a single partition is selected.

### Claim 8 (depends on 1)

The method of claim 1 wherein step (d) comprises using the processor to select a subset of “landmark” points, to embed the selected points using a conventional multi-dimensional scaling algorithm and, using the embedded points, to triangulate the location of the remaining points.

### Claim 9 (depends on 1)

The method of claim 1 wherein step (e) comprises using the data processor to create a two-dimensional grid of points equal to the number of clusterings sampled and to select the closest points to each point on the grid.

### Claim 10 (depends on 1)

The method of claim 1 wherein the data processor has a mechanism for selecting a point on the display and step (e) comprises displaying clusters in a clustering corresponding to the selected point.

### Claim 11

Apparatus for selecting clusterings to classify a data set comprising a data processor having a display and a memory with a software program therein that controls the data processor to perform the following steps:
a) creating a lower dimensional space of all possible clusterings and storing the space in the memory, each clustering being associated with an allocation of objects to be clustered and corresponding to a point in the lower dimensional space;
b) sampling the stored lower dimensional space based on a number of objects in the data set;
c) building partitions based on the samples that tessellate the lower-dimensional space of all possible clusterings, the clusterings being tessellated based on similarities among the objects in the associated allocations;
d) selecting partitions and determine remaining point locations in the lower dimensional space;
e) projecting the points of the lower dimensional space to a two-dimensional array of points; and
f) displaying, on the display, points in the two-dimensional array.

### Claim 12 (depends on 11)

The apparatus of claim 11 wherein step (a) comprises embedding a space of all possible clusterings into a lower dimensional Euclidean space.

### Claim 13 (depends on 12)

The apparatus of claim 12 wherein step (b) comprises randomly sampling the lower dimensional Euclidean space.

### Claim 14 (depends on 12)

The apparatus of claim 12 wherein step (b) comprises sampling the lower dimensional Euclidean space by selecting at least some partitions of interest to a user.

### Claim 15 (depends on 11)

The apparatus of claim 11 wherein step (c) comprises finding a partition that is approximately the closest partition to each sample generated in step (b).

### Claim 16 (depends on 15)

The apparatus of claim 15 wherein the objects are documents and step (c) comprises using the data processor to score pairs of documents and to select the smallest scores.

### Claim 17 (depends on 16)

The apparatus of claim 16 further comprising sequentially adding coordinates with small scores while maintaining pairings necessary to ensure that only a single partition is selected.

### Claim 18 (depends on 11)

The apparatus of claim 11 wherein step (d) comprises selecting a subset of “landmark” points, embedding the selected points using a conventional multi-dimensional scaling algorithm and, using the embedded points, to triangulate the location of the remaining points.

### Claim 19 (depends on 11)

The apparatus of claim 11 wherein step (e) comprises creating a two-dimensional grid of points equal to the number of clusterings sampled and selecting the closest points to each point on the grid.

### Claim 20 (depends on 11)

The apparatus of claim 11 wherein the data processor has a mechanism for selecting a point on the display and step (e) comprises displaying clusters in a clustering corresponding to the selected point.