Method and apparatus for quantum clustering

• US 20040117403A1
• Filed: 10/22/2003
• Published: 06/17/2004
• 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: Gottlieb, Assaf, Horn, David, Axel, Inon
• Granted Patent: US 7,653,646 B2
• Time in Patent Office: Days
• US Class Current: 707/104.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;

(d) 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.

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 set of kernels represents a Hilbert space state.

6. 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, σ

.

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

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

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

10. 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.

11. The method of claim 10, wherein said density function is a ground state of said Hamiltonian.

12. The method of claim 6, whereon 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.

13. The method of claim 12, 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.

14. The method of claim 12, wherein said density function is a ground state of said Hamiltonian.

15. 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.

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

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

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

19. The method of claim 18, wherein said kinetic term comprises a Laplacian.

20. The method of claim 6, 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 ψ

].

21. The method of claim 1, wherein said locating said plurality of local minima of said potential is by evaluating said potential in a plurality of evaluation points, thereby providing a plurality of potential values, and selecting minimal values of said potential values.

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

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

24. 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.

25. The method of claim 6, wherein said width σ

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

.

26. The method of claim 6, 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.

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

28. The method of claim 27, 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.

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

30. The method of claim 28, wherein said correlation matrix is an autocorrelation matrix.

31. The method of claim 28, wherein said correlation matrix is a covariance matrix.

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

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

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

35. The method of claim 34, 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.

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

37. The method of claim 35, 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 right, each of said first and second matrices being respectively formed from an orthonormal set of vectors.

38. The method of claim 35, 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.

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

40. The method of claim 6, further comprising:

(f) merging each cluster into a single point;

(g) increasing said width; and

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

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

42. An apparatus for determining clusters of data within a dataset, the dataset is represented by a plurality of multidimensional data entries, the apparatus comprising:

a space spanning unit for spanning a space, represented by a plurality of points;

a density function determinator for determining a density function over said space;

a potential associator for associating a potential to said density function;

a locator for locating a plurality of local minima of said potential; and

a cluster builder for attributing, for each of said plurality of local minima, at least one of said points.

43. The apparatus of claim 42, wherein each of said plurality of points has a multidimensional coordinate respectfully representing one multidimensional data entry.

44. The apparatus of claim 42, wherein said density function and said potential are each independently positive quantities.

45. The apparatus of claim 42, wherein said density function is a sum of a set of kernels, one said kernel for each of said plurality of points.

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

47. The apparatus of claim 45, wherein each of said kernels is substantially localized at one of said plurality of points, and characterized by a width, σ

.

48. The apparatus of claim 45, wherein said kernels have equal weights.

49. The apparatus of claim 45, wherein each of said kernels has a predetermined weight.

50. The apparatus of claim 45, wherein said kernels are Gaussians.

51. The apparatus of claim 42, wherein said potential associator includes a model-constructor for constructing a physical analog quantum mechanical model over said space, said model having a Hamiltonian which includes said potential.

52. The apparatus of claim 51, wherein said density function is a ground state of said Hamiltonian.

53. The apparatus of claim 47, wherein said potential associator includes a model constructor for constructing a physical analog quantum mechanical model over said space, said model having a Hamiltonian which includes said potential.

54. The apparatus of claim 53, 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.

55. The apparatus of claim 53, wherein said density function is a ground state of said Hamiltonian.

56. The apparatus of claim 42, wherein said potential associator includes an operator determinator for determining an operator in manner that said density function is an eigenfunction of said operator with an eigenvalue, E, said operator includes said potential.

57. The apparatus of claim 56, wherein said operator determinator operable to select said eigenvalue, E, so that a minimal value of said potential is substantially zero.

58. The apparatus of claim 56, wherein said operator determinator operable to include in said operator at least one additional term.

59. The apparatus of claim 58, wherein said at least one additional term includes a kinetic term.

60. The apparatus of claim 59, wherein said kinetic term comprises a Laplacian.

61. The apparatus of claim 47, 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 ψ

].

62. The apparatus of claim 42, wherein said locator is operable to evaluate said potential in a plurality of evaluation points, thereby to provide a plurality of potential values, and further wherein said locator is operable to select minimal values of said potential values.

63. The apparatus of claim 62, wherein each of said evaluation points respectively corresponds to one data entry.

64. The apparatus of claim 42, wherein said cluster builder includes electronic-calculating functionality to dynamically descent one point of said space in a direction of a gradient of said potential into said plurality of local minima.

65. The apparatus of claim 47, wherein said density function determinator is operable to select said width σ

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

.

66. The apparatus of claim 42, wherein said space spanning unit includes a dimension eliminator for eliminating at least one dimension from the dataset.

67. The apparatus of claim 66, wherein said dimension eliminator includes:

a matrix constructor for constructing a correlation matrix from the dataset;

electronic-calculating functionality for calculating a set of eigenvalues of said correlation matrix; and

an eigenvalues selector for selecting a subset of said set of eigenvalues.

68. The apparatus of claim 67, wherein said eigenvalues selector is operable to select largest eigenvalues of said set of eigenvalues.

69. The apparatus of claim 67, wherein said correlation matrix is an autocorrelation matrix.

70. The apparatus of claim 67, wherein said correlation matrix is a covariance matrix.

71. The apparatus of claim 67, wherein said dimension eliminator further comprises electronic-calculating functionality for diagonalizing and for normalizing said correlation matrix to a unitary diagonal correlation matrix.

72. The apparatus of claim 42, wherein the dataset has a matrix form, hence the dataset is a dataset-matrix, M.

73. The apparatus of claim 72, wherein said space spanning unit includes a matrix truncating unit for truncating said dataset-matrix, so as to construct a truncated space having a reduced dimensionality.

74. The apparatus of claim 73, wherein said matrix truncating unit includes:

a matrix constructor for constructing a transformation matrix from said dataset-matrix;

electronic-calculating functionality for calculating a set of eigenvalues of said transformation matrix; and

an eigenvalues selector for selecting a subset of said set of eigenvalues.

75. The apparatus of claim 74, wherein said eigenvalues selector is operable to select largest eigenvalues of said set of eigenvalues.

76. The apparatus of claim 74, wherein said matrix constructor includes;

electronic-calculating functionality for forming a first matrix and a second matrix from an orthonormal set of vectors;

a matrix multiplier for multiplying said dataset-matrix by said first matrix from the left and by said second matrix from the right.

77. The apparatus of claim 76, 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.

78. The apparatus of claim 76, wherein said matrix constructor further includes a projector for projection each point in said truncated space onto a unit sphere in said truncated space.

79. The apparatus of claim 42, further comprising an iterating unit for defining a dendrogram of clusters by performing a sequence of iterations.

80. The apparatus of claim 79, wherein said iterating unit includes a width initiator for selecting an initial value of said σ

, and a merging unit for merging each cluster into a single point.

81. 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

partitioning said plurality of points, into a plurality of clusters;

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

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

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

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

85. The method of claim 81, 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.

86. The method of claim 85, wherein said subset includes largest eigenvalues of said set of eigenvalues.

87. The method of claim 85, 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.

88. The method of claim 85, 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.

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

90. The method of claim 81, 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.

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

92. The method of claim 90, 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.

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

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

.

95. The method of claim 92, wherein said kernels have equal weights.

96. The method of claim 92, wherein each of said kernels has a predetermined weight.

97. The method of claim 92, wherein said kernels are Gaussians.

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

99. The method of claim 98, wherein said density function is a ground state of said Hamiltonian.

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

101. The method of claim 100, wherein said Hamiltonian equals −

0.5σ

²∇

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

102. The method of claim 100, wherein said density function is a ground state of said Hamiltonian.

103. The method of claim 90, 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.

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

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

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

107. The method of claim 106, wherein said kinetic term comprises a Laplacian.

108. The method of claim 94, 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ψ

].

109. The method of claim 90, wherein said locating said plurality of local minima of said potential is by evaluating said potential in a plurality of evaluation points, thereby providing a plurality of potential values, and selecting minimal values of said potential values.

110. The method of claim 109, wherein each of said evaluation points is respectively one point of said truncated space.

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

112. The method of claim 90, 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.

113. The method of claim 94, wherein said width σ

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

.

114. The method of claim 94, further comprising:

(e) merging each cluster into a single point;

(f) increasing said width; and

(g) repeating said steps (a) to (d).

115. The method of claim 114, further comprising iteratively repeating said steps (e) to (g), thereby defining a dendrogram of clusters.

116. An apparatus for determining clusters of biological data within a dataset, the dataset is represented by a multidimensional dataset-matrix, M, the apparatus comprising:

a matrix truncating unit for 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

a partitioning unit for partitioning said plurality of points, into a plurality of clusters.

117. The method of claim 116, wherein each biological entry is characterized by a plurality of genes, promoters, proteins, antibodies, physiological parameters and biochemical parameters.

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

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

120. The apparatus of claim 116, wherein said matrix truncating unit includes:

a matrix constructor for constructing a transformation matrix from said dataset-matrix;

electronic-calculating functionality for calculating a set of eigenvalues of said transformation matrix; and

an eigenvalues selector for selecting a subset of said set of eigenvalues.

121. The apparatus of claim 120, wherein said matrix constructor includes;

electronic-calculating functionality for forming a first matrix and a second matrix from an orthonormal set of vectors;

a matrix multiplier for multiplying said dataset-matrix by said first matrix from the left and by said second matrix from the right.

122. The apparatus of claim 121, 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.

123. The apparatus of claim 121, wherein said matrix constructor further includes a projector for projection each point in said truncated space onto a unit sphere in said truncated space.

124. The apparatus of claim 120, wherein said eigenvalues selector is operable to select largest eigenvalues of said set of eigenvalues.

125. The apparatus of claim 116, wherein said partitioning unit comprises:

a density function determinator for determining a density function over said truncated space;

a potential associator for associating a potential to said density function;

a locator for locating a plurality of local minima of said potential; and

a cluster builder for attributing, for each of said plurality of local minima, at least one of said points.

126. The apparatus of claim 125, wherein said density function and said potential are each independently positive quantities.

127. The apparatus of claim 125, wherein said density function is a sum of a set of kernels, one said kernel for each of said plurality of points.

128. The apparatus of claim 127, wherein each of said set of kernels represents a Hilbert space state.

129. The apparatus of claim 127, wherein each of said kernels is substantially localized at one of said plurality of points, and characterized by a width, σ

.

130. The apparatus of claim 127, wherein said kernels have equal weights.

131. The apparatus of claim 127, wherein each of said kernels has a predetermined weight.

132. The apparatus of claim 127, wherein said kernels are Gaussians.

133. The apparatus of claim 125, wherein said potential associator includes a model-constructor for constructing a physical analog quantum mechanical model over said truncated space, said model having a Hamiltonian which includes said potential.

134. The apparatus of claim 133, wherein said density function is a ground state of said Hamiltonian.

135. The apparatus of claim 129, wherein said potential associator includes a model constructor for constructing a physical analog quantum mechanical model over said truncated space, said model having a Hamiltonian which includes said potential.

136. The apparatus of claim 135, wherein said Hamiltonian equals −

0.5σ

²∇

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

137. The apparatus of claim 135, wherein said density function is a ground state of said Hamiltonian.

138. The apparatus of claim 125, wherein said potential associator includes an operator determinator for determining an operator in manner that said density function is an eigenfunction of said operator with an eigenvalue, E, said operator includes said potential.

139. The apparatus of claim 138, wherein said operator determinator operable to select said eigenvalue, E, so that a minimal value of said potential is substantially zero.

140. The apparatus of claim 138, wherein said operator determinator operable to include in said operator at least one additional term.

141. The apparatus of claim 140, wherein said at least one additional term includes a kinetic term.

142. The apparatus of claim 141, wherein said kinetic term comprises a Laplacian.

143. The apparatus of claim 129, 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ψ

].

144. The apparatus of claim 125, wherein said locator is operable to evaluate said potential in a plurality of evaluation points, thereby to provide a plurality of potential values, and further wherein said locator is operable to select minimal values of said potential values.

145. The apparatus of claim 144, wherein each of said evaluation points is respectively one point of said truncated space.

146. The apparatus of claim 125, wherein said cluster builder includes electronic-calculating functionality to dynamically descent at least one points of said truncated space in a direction of a gradient of said potential into said plurality of local minima.

147. The apparatus of claim 129, wherein said density function determinator is operable to select said width σ

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

.

148. The apparatus of claim 125, further comprising an iterating unit for defining a dendrogram of clusters by performing a sequence of iterations.

149. The apparatus of claim 149, wherein said iterating unit includes a width initiator for selecting an initial value of said width and a merging unit for merging each cluster into a single point.