Method and apparatus for quantum clustering

• US 7,653,646 B2
• Filed: 05/14/2002
• Issued: 01/26/2010
• Est. Priority Date: 05/14/2001
• Status: Active Grant

• Current Assignee: Ramot at Tel Aviv University Limited (Tel Aviv University)
• Original Assignee: Ramot at Tel Aviv University Limited (Tel Aviv University)
• Inventors: Horn, David, Axel, Inon, Gottlieb, Assaf
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/474,508
• Publication Number:
  US 20040117403A1
• Time in Patent Office: 2,814 Days
• Field of Search: 707 1- 8, 707/100, 707/101, 707/102, 324/306, 708/400, 709/201, 712/14, 382/260
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of determining clusters of data within a dataset, the dataset is represented by a plurality of multidimensional data entries, the method comprises (a) spanning a space, represented by a plurality of points; (b) determining a density function over the space;(c) associating a potential to the density function; (d) locating a plurality of local minima of the potential; and (e) for each of the plurality of local minima, attributing at least one of the points; thereby determining clusters of data within the dataset.

Claims

1. A method of determining clusters of data within a dataset, the dataset is represented by a plurality of multidimensional data entries, the method comprising:

(a) spanning a space, represented by a plurality of points;

(b) determining a density function over said space;

(c) associating a potential to said density function, such that said density function corresponds to an eigenstate of an operator which includes the potential;

(d) locating a plurality of local minima of said potential by evaluating, using a data processor, said potential in a plurality of evaluation points, thereby providing a plurality of potential values, and selecting minimal values of said potential values; and

(e) for each of said plurality of local minima, attributing at least one of said points;

thereby determining clusters of data within the dataset.

2. The method of claim 1, wherein said spanning of said space is by defining, for each of said plurality of points, a multidimensional coordinate respectfully representing one multidimensional data entry.

3. The method of claim 1, wherein said density function and said potential are each independently positive quantities.

4. The method of claim 1, wherein said determining said density function is by assigning a set of kernels, one for each of said plurality of points and summing over said set of kernels.

5. The method of claim 4, wherein each of said kernels is substantially localized at one of said plurality of points, and characterized by a width, σ

.

6. The method of claim 5, wherein said associating said potential is by constructing a physical analog quantum mechanical model over said space, said model having a Hamiltonian which includes said potential.

7. The method of claim 6, wherein said Hamiltonian equals −

0.5σ

²∇

²+V(x), where said V is said potential and said x is a set of coordinates of said space.

8. The method of claim 6, wherein said density function is a ground state of said Hamiltonian.

9. The method of claim 5, wherein said potential equals E+(σ

²∇

²ψ

)/2ψ

, wherein said ψ

is said density function and said E is calculated in accordance with the formula E=−

min [(σ

²∇

²ψ

_./2ψ

].

10. The method of claim 5, wherein said width σ

, is selected so that a number of clusters is stable under sufficiently small variation of said σ

.

11. The method of claim 5, further comprising iteratively merging each cluster into a single point, increasing said width and repeating said steps (a) to (e), thereby defining a dendrogram of clusters.

12. The method of claim 5, further comprising:

(f) merging each cluster into a single point;

(g) increasing said width; and

(h) repeating said steps (b) to (e).

13. The method of claim 12, further comprising iteratively repeating said steps (g) to (h), thereby defining a dendrogram of clusters.

14. The method of claim 4, wherein said kernels have equal weights.

15. The method of claim 4, wherein each of said kernels has a predetermined weight.

16. The method of claim 4, wherein said kernels are Gaussians.

17. The method of claim 1, wherein each of said set of kernels represents a Hilbert space state.

18. The method of claim 1, wherein said associating said potential is by constructing a physical analog quantum mechanical model over said space, said model having a Hamiltonian which includes said potential.

19. The method of claim 18, wherein said density function is a ground state of said Hamiltonian.

20. The method of claim 1, wherein said associating said potential is by determining an operator in manner that said density function is an eigenfunction of said operator with an eigenvalue, E, said operator includes said potential.

21. The method of claim 20, wherein said eigenvalue, E, is selected so that a minimal value of said potential is substantially zero.

22. The method of claim 20, wherein said operator further includes at least one additional term.

23. The method of claim 22, wherein said at least one additional term includes a kinetic term.

24. The method of claim 23, wherein said kinetic term comprises a Laplacian.

25. The method of claim 1, wherein each of said evaluation points respectively corresponds to one data entry.

26. The method of claim 1, wherein said attributing at least one of said points is by visual means.

27. The method of claim 1, wherein said attributing at least one of said points is by a dynamically descending said at least one points of said space in a direction of a gradient of said potential, into said plurality of local minima.

28. The method of claim 1, wherein said spanning a space is by eliminating at least one dimension from the dataset.

29. The method of claim 28, wherein said eliminating is by constructing a correlation matrix from the dataset, calculating a set of eigenvalues of said correlation matrix, and selecting a subset of said set of eigenvalues.

30. The method of claim 29, wherein said subset includes largest eigenvalues of said set of eigenvalues.

31. The method of claim 29, wherein said correlation matrix is an autocorrelation matrix.

32. The method of claim 29, wherein said correlation matrix is a covariance matrix.

33. The method of claim 29, further comprising diagonalizing and normalizing said correlation matrix to a unitary diagonal correlation matrix.

34. The method of claim 1, wherein the dataset has a matrix form, hence the dataset is a dataset-matrix, M.

35. The method of claim 34, wherein said spanning a space is by truncating said dataset-matrix, so as to construct a truncated space having a reduced dimensionality.

36. The method of claim 35, wherein said truncating is by constructing a transformation matrix from said dataset-matrix, calculating a set of eigenvalues of said transformation matrix, and selecting a subset of said set of eigenvalues, thereby constructing said truncated space.

37. The method of claim 36, wherein said subset includes largest eigenvalues of said set of eigenvalues.

38. The method of claim 36, wherein said constructing said transformation matrix is by multiplying said dataset-matrix by a first matrix from the left and by a second matrix from the fight, each of said first and second matrices being respectively formed from an orthonormal set of vectors.

39. The method of claim 38, further comprising projecting each point in said truncated space onto a unit sphere in said truncated space.

40. The method of claim 36, wherein said first matrix diagonalizes MM^T and said second matrix diagonalizes M^TM, where M^T is a transpose representation of said dataset-matrix, M.

41. A method of determining clusters of biological data within a dataset, the dataset is represented by a multidimensional dataset-matrix, M, the method comprising:

truncating the dataset-matrix, M, so as to construct a truncated space having a reduced dimensionality, said truncated space is represented by a plurality of points, each representing one biological entry; and

using a data processor for partitioning said plurality of points, into a plurality of clusters;

thereby determining clusters of determining clusters of biological data within the dataset.

42. The method of claim 41, wherein each biological entry is characterized by a plurality of expressed genes, expressed proteins, antibodies, physiological parameters, biochemical parameters.

43. The method of claim 41, wherein each biological entry is selected from the group consisting of a sample, a cell and a tissue.

44. The method of claim 41, wherein each biological entry corresponds to one subject at one time.

45. The method of claim 41, wherein said truncating is by constructing a transformation matrix from the dataset-matrix, calculating a set of eigenvalues of said transformation matrix, and selecting a subset of said set of eigenvalues, thereby constructing said truncated space.

46. The method of claim 45, wherein said subset includes largest eigenvalues of said set of eigenvalues.

47. The method of claim 45, wherein said constructing said transformation matrix is by multiplying the dataset-matrix by a first matrix from the left and by a second matrix from the right, each of said first and second matrices being respectively formed from an orthonormal set of vectors.

48. The method of claim 47, further comprising projection each point in said truncated space onto a unit sphere in said truncated space.

49. The method of claim 45, wherein said first matrix diagonalizes MM^T and said second matrix diagonalizes M^TM, where M^T is a transpose representation of said dataset-matrix, M.

50. The method of claim 41, wherein said partitioning comprising:

(a) determining a density function over said truncated space;

(b) associating a potential to said density function;

(c) locating a plurality of local minima of said potential; and

(d) for each of said plurality of local minima, attributing at least one of said points;

thereby partitioning said plurality of points, into a plurality of clusters.

51. A method of determining clusters of data within a dataset, the dataset is represented by a plurality of multidimensional data entries, the method comprising:

(a) spanning a space, represented by a plurality of points;

(b) determining a density function over said space by assigning a set of kernels, one for each of said plurality of points and summing over said set of kernels;

(c) associating a potential to said density function;

(d) using a data processor for locating a plurality of local minima of said potential;

and

(e) for each of said plurality of local minima, attributing at least one of said points;

thereby determining clusters of data within the dataset.

52. A method of determining clusters of data within a dataset, the dataset is represented by a plurality of multidimensional data entries, the method comprising:

(a) spanning a space, represented by a plurality of points;

(b) determining a density function over said space;

(c) associating a potential to said density function by determining an operator in manner that said density function is an eigenfunction of said operator with an eigenvalue, E, said operator includes said potential;

(d) using a data processor for locating a plurality of local minima of said potential; and

(e) for each of said plurality of local minima, attributing at least one of said points;

thereby determining clusters of data within the dataset.

53. A method of determining clusters of data within a dataset, the dataset is represented by a plurality of multidimensional data entries, the method comprising:

(a) spanning a space, represented by a plurality of points, by eliminating at least one dimension from the dataset;

(b) determining a density function over said space;

(c) associating a potential to said density function;

(d) using a data processor for locating a plurality of local minima of said potential; and

(e) for each of said plurality of local minima, attributing at least one of said points;

thereby determining clusters of data within the dataset.