Dynamic quantum clustering: A method for visual exploration of structures in data

A given set of data points in some feature space may be associated with a Schrödinger equation whose potential is determined by the data. This is known to lead to good clustering solutions. Here we extend this approach into a full-fledged dynamical scheme using a time-dependent Schrödinger equation. Moreover, we approximate this Hamiltonian formalism by a truncated calculation within a set of Gaussian wave functions (coherent states) centered around the original points. This allows for analytic evaluation of the time evolution of all such states opening up the possibility of exploration of relationships among data points through observation of varying dynamical distances among points and convergence of points into clusters. This formalism may be further supplemented by preprocessing such as dimensional reduction through singular-value decomposition or feature filtering.

Figure 1

(Color online) This is a plot of the quantum potential function for the two-dimensional problem of the Ripley’s crab data where the coordinates of the data points are chosen to be given by the second and third principal components. The four known classes of data points are shown (online only) in different colors proceeding counterclockwise from the upper right-hand corner (blue, green, yellow, and red) and they are placed upon the potential surface at their original locations.

Figure 2

(Color online) The left-hand plot shows three-dimensional distribution of the original data points before quantum evolution. The middle plot shows the same distribution after quantum evolution. The right-hand plot shows the results of an additional iteration of DQC. The values of parameters used to construct the Hamiltonian and evolution operator are $\sigma =0.07$ and $m=0.2$. Colors indicate the expert classification of data into four classes unknown to the clustering algorithm. Note that small modifications of the parameters lead to the same results. The first species of crabs (male and female) are designated by the blue and red points in the upper left- and right-hand corners, respectively, and the second by the green and orange points in the lower left- and right-hand corners.

Figure 3

(Color online) A plot of Euclidean distance of each point $i$ from the first data point. Again, the left-hand plot shows the distances for the initial distribution of points. The middle plot shows the same distances after quantum evolution. The right-hand plot shows results after another iteration of DQC. The numbering of the data points is ordered according to the expert classification of these points into four classes containing 50 instances each. The colors of the points are, from left to right, red—open diamond, blue—filled diamonds, yellow—open squares, and green—filled squares.

Figure 4

(Color online) A plot of the first three principal components for a large data set comprising $35213$ points in 20 dimensions before and after DQC evolution. The potential was determined from the full data set and evolved using a subset of 1200 points whose Gaussians serve as an essentially linear set of independent states. Three stages of DQC development are shown. In this plot the colors have no significance; the important thing is that they make the clusters more obvious. The coloring was decided upon by selecting the most obvious clusters from the evolved data and assigning colors to them. The dark blue points (these are the darkest points) correspond to points that we did not bother to assign to clusters. The purpose of coloring is to be able to look at the points in the original data, discern those that belong to common structures, and follow their dynamic distances under DQC evolution.

Figure 5

(Color online) The left-hand picture is the raw data from the Affymetrix Chip plotted for principal components 2, 3, and 4. Clearly, without the coloring it would be hard to identify clusters. The darkest (blue) points are somewhat close to one another but the remaining points are spread out enough so classification is difficult. The right-hand picture is the same data after DQC evolution using $\sigma =0.2$ and a mass $m=0.01$. The different classes are shown as blue (darkest), red (next darkest gray), green (next darkest), and orange (lightest gray).

Figure 6

(Color online) The left-hand plot is the Golub data after one stage of SVD-entropy-based filtering but before DQC evolution. The right-hand plot is the same data after DQC evolution.

Figure 7

(Color online) The left-hand plot is the data after three stages of SVD-entropy-based filtering but before DQC evolution. The right-hand plot is the same data after DQC evolution.

Figure 8

(Color online) The left-hand plot is what the starting data look like if one first removes the blue points and does one stage of SVD-entropy-based filtering. The right-hand plot is what the data look like after three stages of filtering.

Figure 9

(Color online) The left-hand plot is what the starting data look like if one first removes the blue points and does five stages of SVD-entropy-based filtering. The right-hand plot is what happens after one stage of DQC evolution. The bottom plot is the final result after iterating the DQC evolution step two more times. At this point the clusters are trivially extracted with the red points clustered in the left-hand side of the plot and the yellow in the lower right-hand corner and the greens in the upper right-hand corner.