Method and apparatus for clustering data

• US 6,021,383 A
• Filed: 10/07/1996
• Issued: 02/01/2000
• Est. Priority Date: 10/07/1996
• Status: Expired due to Fees

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Domany, Eytan, Blatt, Marcelo, Wiseman, Shai
• Primary Examiner(s): SHAH, KAMINI S
• Application Number:
  US08/725,960
• Time in Patent Office: 1,212 Days
• Field of Search: 364/554, 364/580, 364/551.01, 364/489, 364/490, 364/578, 382/225, 382/181, 382/228, 395/119, 395/127, 395/611-613, 395/21-24, 395/742, 395/553, 324/307, 324/309, 702/181, 702/182
• US Class Current: 702/181
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 18/232 Non-hierarchical techniques
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

A method and apparatus for partitioning a data set for clustering, based on the physical properties of an inhomogeneous ferromagnet. No assumption is made regarding the underlying distribution of the data. A Potts spin is assigned to each data point and an interaction between neighboring points is introduced, whose strength is a decreasing function of the distance between the neighbors. This magnetic system exhibits three phases. At very low temperatures it is completely ordered; i.e. all spins are aligned. At very high temperatures the system does not exhibit any ordering and in an intermediate regime clusters of relatively strongly coupled spins become ordered, whereas different clusters remain uncorrelated. This intermediate phase is identified by a jump in the order parameters. The spin--spin correlation function is used to partition the spins and the corresponding data points into clusters.

Claims

1. A method for analyzing signals containing a data set which is representative of a plurality of physical phenomena, to identify and distinguish among said physical phenomena by determining clusters of data points within said data set, said method comprising:

(1) constructing a physical analog Potts-spin model of the data set by

(a) associating a Potts-spin variable s_i =1, 2 . . . q to each data point v_i,

(b) identifying neighbors of each point v_i according to a selected criterion,

(c) determining the Hamiltonian '"'"'H and determining the interaction J_ij between neighboring points v_i and v_j,

(2) locating a super-paramagnetic phase of the data set using the Monte Carlo procedure to determine susceptibility χ

(T) by

(a) determining the thermal average magnetization (m) for different temperatures,

(b) identifying the presence of a super-paramagnetic phase using susceptibility χ

,

(3) determining the spin--spin correlation G_if for all neighboring points v_i and v_j,

(4) constructing data clusters using the spin--spin correlation G_ij within the super-paramagnetic phase located in step (2) to partition the data set, and

(5) identifying said physical phenomena based on said data clusters.

2. The method of claim 1 wherein the Monte Carlo procedure is carried out using the Swendsen-Wang technique.

3. The method of claim 1 including the further step of displaying the partitioned data set.

4. The method of claim 1 including the further step of recording the partitioned data set in a recording medium.

5. The method according to claim 1 wherein said data set comprises data which are representative of at least one of the group consisting of objects, patterns, characters, sounds, images, processes and signals representative thereof.

7. The apparatus of claim 1 wherein the Monte Carlo procedure is carried out using the Swendsen-Wang technique.

6. Apparatus for analyzing signals containing a data set which is representative of a plurality of physical phenomena, to identify and distinguish among said physical phenomena by determining clusters of data points within said data set, said apparatus comprising:

(1) means for constructing a physical analog Potts-spin model of the data set including

(a) means for associating a Potts-spin variable s_i =1, 2 . . . q to each data point v_i,

(b) means for identifying neighbors of each point v_i according to a selected criterion,

(c) means for determining the Hamiltonian '"'"'H and determining the interaction J_ij between neighboring points v_i and v_j,

(2) means for locating a super-paramagnetic phase of the data set using the Monte Carlo procedure to determine susceptibility χ

(T) including;

(a) means for determining the thermal average magnetization (m) for different temperatures,

(b) means for identifying the presence of a super-paramagnetic phase using susceptibility, χ

,

(3) means for determining the spin--spin correlation G_ij for all neighboring points v_i and v_j,

(4) means for constructing data using the spin--spin correlation G_ij within the located super-paramagnetic phase to partition the data set, and

(5) means for identifying said physical phenomena based on said data clusters.

8. The apparatus of claim 6 including means for digitally storing the partitioned data set as clusters of data.

9. The apparatus of claim 6 including means for displaying the partitioned data set.

10. The apparatus of claim 6 including means for recording the partitioned data set in a recording medium.

11. The apparatus of claim 10 including means for printing the partitioned data set on a print receiving medium.

12. Apparatus according to claim 6 wherein said data set comprises data which are representative of at least one of the group consisting of objects, patterns, characters, sounds, images, processes and signals representative thereof.

13. A method for recognizing a plurality of physical objects or phenomena represented collectively by a data set which comprises data points defined by a plurality of parametric values, by sorting said data points into clusters of data points, comprising:

(1) constructing a physical analog Potts-spin model of the data set by

(a) associating a Potts-spin variable s_i =1, 2 . . . q to each data point v_i,

(b) identifying neighbors of each point v_i according to a selected criterion,

(c) determining the Hamiltonian H and determining the interaction J_ij between neighboring points v_i and v_j,

(2) locating a super-paramagnetic phase of the data set using the Monte Carlo procedure to determine susceptibility χ

(T) by

(a) determining the thermal average magnetization (m) for different temperatures,

(b) identifying the presence of a super-paramagnetic phase using susceptibility χ

,

(3) determining the spin--spin correlation G_ij for all neighboring points v_i and v_j,

(4) constructing data clusters using the spin--spin correction G_ij within the super-paramagnetic phase located in step (2) to partition the data set; and

(5) identifying said physical phenomena based on said data clusters.

14. The method according to claim 13 wherein said data set comprises data which are representative of at least one of the group consisting of objects, patterns, characters, sounds, images, processes and signals representative thereof.

15. An apparatus for recognizing a plurality of physical objects or phenomena represented collectively by a data set which comprises data points defined by a plurality of parametric values, by sorting said data points into clusters of data points, said apparatus comprising:

(1) means for constructing a physical analog Potts-spin model of the data set by

(a) associating a Potts-spin variable s_i =1, 2 . . . q to each data point v_i,

(b) identifying neighbors of each point v_i according to a selected criterion,

(c) determining the Hamiltonian H and determining the interaction J_ij, between neighboring points v_i and v_j,

(2) means for locating a super-paramagnetic phase of the data set using the Monte Carlo procedure to determine susceptibility C(T) by

(a) determining the thermal average magnetization (m) for different temperatures,

(b) identifying the presence of a super-paramagnetic phase using susceptibility χ

,

(3) means for determining the spin--spin correlation G_ij for all neighboring points v_i and v_j,

(4) means for constructing data clusters using the spin--spin correction G_ij within the super-paramagnetic phase located in step (2) to partition the data set; and

(5) means for identifying said physical phenomena based on said data clusters.

16. Apparatus according to claim 15 wherein said data set comprises data which are representative of at least one of the group consisting of objects, patterns, characters, sounds, images, processes and signals representative thereof.