Mechanism for unsupervised clustering

• US 7,809,726 B2
• Filed: 03/03/2003
• Issued: 10/05/2010
• Est. Priority Date: 03/04/2002
• Status: Expired due to Fees

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Flanagan, Adrian
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): LOVEL, KIMBERLY M
• Application Number:
  US10/506,634
• Publication Number:
  US 20050102301A1
• Time in Patent Office: 2,773 Days
• Field of Search: 707 1- 10, 707/100.S, 707/737, 706 10- 20, 706/29
• US Class Current: 707/737
• CPC Class Codes: G06F 18/2321 using statistics or function optimisation, e.g. modelling of probability density functions

Abstract

A computer-implemented method for determining cluster centers in a first data structure, wherein the first data structure comprises a lattice structure of weight vectors that create an approximate representation of a plurality of input data points. The method can include performing a first iterative process for iteratively updating the weight vectors such that they move toward cluster centers; performing a second iterative process for iteratively updating a second data structure utilizing results of the iterative updating of the first data structure; and determining the weight vectors that correspond to cluster centers of the input data points on the basis of the second data structure.

Claims

1. A method, comprising:

determining, by an apparatus, cluster centers in a first data structure, wherein the first data structure comprises a lattice structure of weight vectors that create an approximate representation of a plurality of input data points, and wherein a plurality of the weight vectors represents a single non-linear cluster;

performing, by the apparatus, a first iterative process with iterations each including determining a winner weight for each data point and then updating each weight vector corresponding to the winner weight with a first neighborhood function and a corresponding first coefficient updated in a second iterative process such that the weight vectors move toward the cluster centers;

performing, by the apparatus, the second iterative process with iterations each including updating said corresponding first coefficient in a second data structure by utilizing a second neighborhood function and the winner weight determined in the first iterative process; and

determining by the apparatus, based on the second data structure, several sets of weight vectors in said lattice structure such that in each set, the weight vectors correspond to the same cluster centers of the input data points,

wherein the first coefficient is limited to a range, the first neighborhood function gives only positive values, and the second neighborhood function gives negative values in a distance range between 0 and 1.

2. The method according to claim 1,

wherein the winner weight vector for each data point is determined on the basis of the distance between the data point and the weight vectors, and

each iteration in the first iterative process further includes calculating a next value for each weight vector on the basis of the current value of the weight vector and the first neighborhood function of the distance on the lattice structure between the weight vector and the winner weight vector, and

wherein each iteration in the second iterative process further includes calculating a next value of each of the first coefficients based on:

the current value of the each first coefficient, and a combination of

a first coefficient of the winner weight vector,

the second neighborhood function of the distance on the lattice structure between the weight vector and the winner weight vector, and

an adjustment factor for adjusting convergence speed between iterations.

3. The method according to claim 2, wherein the combination is or comprises multiplication.

4. The method according claim 2, wherein the second neighborhood function is not monotonous.

5. The method according to claim 2, wherein the second neighborhood function gives negative values within 0and −

0.4 in a distance range between 0.1 and 1 .

6. The method according to claim 2, wherein the second neighborhood function depends on a number of prior iterations.

7. The method according to claim 2, wherein the first data structure is or comprises a self-organizing map.

8. The method according to claim 7, further comprising:

estimating an upper limit K for a number of clusters in the self-organizing map;

defining a coefficient vector Θ

i=(θ

_i,1, θ

_i,2, . . . θ

_i,K) for each weight vector i in the self-organizing map, the coefficient vector comprising K second coefficients θ

_i,1, each of which represents a weighting between the weight vector i and a label l; and

assigning cluster label l to weight vector i if;

l =arg max θ

_i,k, 1≦

k≦

K.

9. The method according to claim 8, wherein each iteration in the second iterative process comprises calculating a next value of each second coefficient based on the current value of the second coefficient and a combination of

a coefficient of the winner weight vector,

a third neighborhood function of distance, and

an adjustment factor for adjusting convergence speed between iterations.

10. The method according to claim 1, wherein the determining the weight vectors that correspond to cluster centers comprises selecting local maxima in the second data structure.

11. The method according to claim 1, wherein the input data points represent real-world quantities.

12. A computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors causes an apparatus to perform at least the following:

determining cluster centers in a first data structure, wherein the first data structure comprises a lattice structure of weight vectors that create an approximate representation of a plurality of input data points; and

wherein a plurality of the weight vectors represents a single non-linear cluster;

performing a first iterative process with iterations each including determining a winner weight for each data point and then updating each weight vector corresponding to the winner weight with a first neighborhood function and a corresponding first coefficient updated in a second iterative process such that the weight vectors move toward the cluster centers;

performing the second iterative process with iterations each including updating said corresponding first coefficient in a second data structure by utilizing a second neighborhood function and the winner weight determined in the first iterative process; and

determining, based on the second data structure, several sets of weight vectors in said lattice structure such that in each set, the weight vectors correspond to the same cluster centers of the input data points,

wherein the first coefficient is limited to a range, the first neighborhood function gives only positive values, and the second neighborhood function gives negative values in a distance range between 0 and 1.

13. A computer-readable storage medium according to claim 12, wherein the winner weight vector for each data point is determined on the basis of the distance between the data point and the weight vectors, and

each iteration in the first iterative process further includes calculating a next value for each weight vector on the basis of the current value of the weight vector and the first neighborhood function of the distance on the lattice structure between the weight vector and the winner weight vector, and

wherein each iteration in the second iterative process further includes calculating a next value of each of the first coefficients based on:

the current value of the each first coefficient, and

a combination of a first coefficient of the winner weight vector,

the second neighborhood function of the distance on the lattice structure between the weight vector and the winner weight vector, and

an adjustment factor for adjusting convergence speed between iterations.

14. An apparatus, comprising:

at least one processor; and

at least one memory including computer program code,

wherein the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following;

determine cluster centers in a first data structure, wherein the first data structure comprises a lattice structure of weight vectors that create an approximate representation of a plurality of input data points; and

wherein a plurality of the weight vectors represents a single non-linear cluster;

perform a first iterative process with iterations each including determining a winner weight for each data point and then updating each weight vector corresponding to the winner weight with a first neighborhood function and a corresponding first coefficient updated in a second iterative process such that the weight vectors move toward the cluster centers;

perform the second iterative process with iterations each including updating said corresponding first coefficient in a second data structure by utilizing a second neighborhood function and the winner weight determined in the first iterative process; and

determine, based on the second data structure, several sets of weight vectors in said lattice structure such that in each set, the weight vectors correspond to the same cluster centers of the input data points,

wherein the first coefficient is limited to a range, the first neighborhood function gives only positive values, and the second neighborhood function gives negative values in a distance range between 0 and 1.

15. The apparatus of claim 14, wherein the apparatus is further caused to:

determine the winner weight vector for each data point on the basis of the distance between the data point and the weight vectors;

calculate a next value for each weight vector on the basis of the current value of the weight vector and the first neighborhood function of the distance on the lattice structure between the weight vector and the winner weight vector; and

calculate a next value of each of the first coefficients based on;

the current value of the each first coefficient, and

a combination of a first coefficient of the winner weight vector,

the second neighborhood function of the distance on the lattice structure between the weight vector and the winner weight vector, and

an adjustment factor for adjusting convergence speed between iterations.

16. The apparatus of claim 15, wherein the apparatus is further caused to determine the weight vectors that correspond to cluster centers by selecting local maxima in the second data structure.

17. The apparatus of claim 15, wherein the combination is or comprises multiplication.

18. The apparatus of claim 15, wherein the second neighborhood function is not monotonous.

19. The apparatus of claim 15, wherein the second neighborhood function gives negative values within 0 and −

0.4 in a distance range between 0.1 and 1.

20. The apparatus of claim 15, wherein the second neighborhood function depends on a number of prior iterations.

21. The apparatus of claim 15, wherein the input data points represent real-world quantities.

22. The apparatus of claim 15, wherein the first data structure is or comprises a self-organizing map.

23. The apparatus of claim 15, wherein the apparatus is further caused to:

estimate an upper limit K for a number of clusters in the self-organizing map;

define a coefficient vector Θ

i=(θ

_i,1, θ

_i,2, . . . θ

_i,K) for each weight vector i in the self-organizing map, the coefficient vector comprising K second coefficients θ

_i,1, each of which represents a weighting between the weight vector i and a label l; and

assign cluster label l to weight vector i if;

l =arg max θ

_i,k, 1≦

k≦

K.

24. The apparatus of claim 15, wherein the wherein the apparatus is further caused in each iteration in the second iterative process to calculate a next value of each second coefficient based on the current value of the second coefficient and a combination of

a coefficient of the winner weight vector,

a third neighborhood function of distance, and

an adjustment factor for adjusting convergence speed between iterations.