Number of clusters estimation

Patent metadata

Field	Value
Publication number	US-9424337-B2
Application number	US-201414196299-A
Country	US
Kind code	B2
Filing date	Mar 4, 2014
Priority date	Jul 9, 2013
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

A method of determining a number of clusters for a dataset is provided. Centroid locations for a defined number of clusters are determined using a clustering algorithm. Boundaries for each of the defined clusters are defined. A reference distribution that includes a plurality of data points is created. The plurality of data points are within the defined boundary of at least one cluster of the defined clusters. Second centroid locations for the defined number of clusters are determined using the clustering algorithm and the reference distribution. A gap statistic for the defined number of clusters based on a comparison between a first residual sum of squares and a second residual sum of squares is computed. The processing is repeated for a next number of clusters to create. An estimated best number of clusters for the received data is determined by comparing the gap statistic computed for each iteration of the number of clusters.

First claim

What is claimed is:

1. A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
receive data to cluster;
define a number of clusters to create;
(a) determine centroid locations for the defined number of clusters using a clustering algorithm and the received data to define clusters;
(b) define boundaries for each of the defined clusters by
determining an eigenvector and an eigenvalue for each dimension of each cluster of the defined clusters using principal components analysis;
determining a length for each dimension of each cluster as a proportion of the determined eigenvalue for the respective dimension; and
defining the boundaries for each cluster of the defined clusters as a box with a center of the box as the determined centroid location of the respective cluster, a first boundary point for each dimension defined as the center plus the determined length of the respective dimension aligned with the determined eigenvector of the respective dimension, and a second boundary point for each dimension defined as the center minus the determined length of the respective dimension aligned with the eigenvector of the respective dimension;

(c) create a reference distribution that includes a plurality of data points, wherein the plurality of data points are within the defined boundary of at least one cluster of the defined clusters;
(d) determine second centroid locations for the defined number of clusters using the clustering algorithm and the created reference distribution to define second clusters;
(e) compute a gap statistic for the defined number of clusters based on a comparison between a first residual sum of squares computed for the defined clusters and a second residual sum of squares computed for the defined second clusters;
(f) repeat (a) to (e) with a next number of clusters to create as the defined number of clusters; and
(g) determine an estimated best number of clusters for the received data by comparing the gap statistic computed for each iteration of (e).

2. The computer-readable medium of claim 1 , wherein the gap statistic for the defined number of clusters is computed using gap(k)=log (W k *)−log(W k ), where

W
k

=

∑

j
=
1

k

⁢

∑

i
=
1

n
j

⁢



x

i
,
j

-

c
j



2

is the first residual sum of squares computed for the defined clusters, and

W
k
*

=

∑

j
=
1

k

⁢

∑

i
=
1

n
j
*

⁢



x

i
,
j

*

-

c
j
*



2

is the second residual sum of squares computed for the defined second clusters, where k is the defined number of clusters, n j is the number of data points in cluster j of the defined clusters, x i,j is the ith data point in cluster j of the defined clusters, c j is the centroid location of cluster j of the defined clusters, n j * is the number of data points in cluster j of the defined second clusters, x i,j * is the ith data point in cluster j of the defined second clusters, and c j * is the centroid location of cluster j of the defined second clusters.

3. The computer-readable medium of claim 2 , wherein (c) and (d) are repeated a plurality of times and wherein

W
k
*

=

1
B

⁢

∑

b
=
1

B

⁢

∑

j
=
1

k

⁢

∑

i
=
1

n
j
*

⁢



x

i
,
j

*

-

c
j
*



2

Assignees

• Sas Inst Inc

Inventors

• Hall Patrick
• Kaynar Kabul Ilknur
• Sarle Warren
• Silva Jorge

Classifications

• G06F18/23211

  with adaptive number of clusters · CPC title

• G06F16/285 Primary

  Clustering or classification · CPC title

• G06F17/30598 Primary

  Physics · mapped topic

• G06K9/6222

  Physics · mapped topic