Ensemble Clustering with VisuMap

A common question by data clustering is: How stable is the clustering results? It often happens that some data points are classified by an algorithm to a common cluster, but when you run the algorithm again on the same data with slightly different initialization conditions these data points might be classified into different clusters. This phenom seems to be a consequence of the nondeterministic behavior of the algorithm, but it is rather a manifestation of the clustering structure among the data. From certain point of view, these unstable data points tells us actually more interesting information about data than those stable data points.


One way to answer the stability question is using the boosting method (also called ensemble clustering) where we aggregate the results of multiple runs of a clustering algorithm. One of the simplest aggregation method is as following: we classify two points to a common cluster (i.e. assign the same color to two points in a map) if all runs classified the two points to a common cluster. 


To visualize the ensemble clustering let us consider a sample as by the following picture. Th picture shows how the k-Mean algorithm clustered a data set in three different runs (i.e. with different random initialization.) When we look closely at these three maps, we can notice, as marked in the circles, that the boundary between two clusters varies among the three maps. This means that data points in this region are unstable. But each individual one of the three maps does not tell us this information; and even with all three maps displayed together, it is rather hard to find these unstable points by visual comparisons.

Now, when we aggregate the three maps with the simple aggregation method mentioned above, we get a  map as show in the following picture. We can recognize easily that, as circled in 3 regions, that there are 3 unstable regions: data points in these regions have different colors than those major clusters. We also notice here easily that there are some stable boundaries between some clusters.

Although this kind of ensemble clustering is fairly simple to implement with the scripting interface of VisuMap, it lacked a simple friendly user interface for this service. The new release of VisuMap,  the version 3.5.881, resolved this problem with a new utility, called cluster manager, that offers the services to capture, store and explore clustering results. And especially, the cluster manager makes it very straightforward to do ensemble clustering. As illustrated in the following screenshot, the user just need to select the clustering results, called named coloring, then choose an appropriate context menu to compose the aggregated clustering:

VisuMap for Flow Cytometry

I have just uploaded a 10 minutes video that demonstrates the basic steps to use VisuMap to explore flow cytometry data:

Notice that VisuMap version 3.5.881 is needed to perform demonstrated tasks. The sample datasets, i.e. FCS files, used in this video are downloaded from the web site FowRepository.

New VisuMap release with multi-band spectrum view

I have just released VisuMap 3.5.879. Worth mentioning in this release is the spectrum band view to visualize large tables. The spectrum band view displays a table as multiple bands of spectrums with one spectrum for each data row or data column.  The spectrum band view is relatively simple to implement and to understand, it is amazingly effective to capture the value distribution of variables and to compare large number of variables. The following picture shows a scenario how VisuMap goes about exploring a large data table with the spectrum band view:

In this example, the data set  is a 4000x1700 number table. Each of the 4000 rows represents a compound with about 1700 physical and chemical features. On the top left side the data set is displayed in a PCA map with one dot for each compound (5 clusters are discernible.)  On the top right side, the data set is displayed as a heat map with one line for each data row. We have selected about 60 features from the heat map and shown them in a spectrum band view at the lower right side. The spectrum band shows each feature as vertical spectrum. We see that most features are more or less Gaussian distributed; some features are discrete as their spectrum comprise only isolated bars.

The spectrum band also helps to answer a frequently asked question in data analysis, namely: if the value of  one feature is in certain range, how will the values of other features be distributed? We can do this very simply with the spectrum map as illustrated in the following picture:

In above picture we have displayed 8 features in a spectrum band with 8 horizontal spectrums. We have selected with the mouse point a small section in the first feature, the spectrum band view immediately shows the density curve (i.e. the distribution) of the other features of selected objects.

Furthermore, with the spectrum band view we can record a series of selections, then repeatedly replay the selection in animation as shown in the following video clip:

On Mean Shift and K-Means Clustering

Mean shift and K-Means algorithm are two similar clustering algorithms; both of them extract information from data with some kind of mean vector operations. Whereas the K-Mean algorithm has been widely popular, the mean shift algorithm has found only limited applications (e.g. for image segmentation.) In this note I'll briefly compare these two algorithms and show a way, with VisuMap software, to combine them to get much better clustering tools.

The mean shift clustering algorithm has two main drawbacks. Firstly, the algorithm is pretty calculation intensive; it requires in general O(kN²) operations (which are mainly calculations of Euclidean distance,) where N is the number of data points and k is the number of average iteration steps for each data point. Secondly, the mean shift algorithm relies on sufficient high data density with clear gradient to locate the cluster centers. In particular, the main shift algorithm often fails to find appropriate clusters for so called data outliers, or those data points locating between natural clusters. The second issue normally manifests itself in some small uncertain clusters together with the wanted major clusters.

The K-Means algorithm does not have the above two problems. The K-Means algorithm normally requires only O(kN) operations, so that K-Means algorithm can be applied to relatively large dataset. However, K-Means has two significant limitations. Firstly, K-Means algorithm requires that the number of clusters to be pre-determined. In practise, it is often difficult to find the right cluster number, so that we often just pick a sufficiently large cluster number. This will result in situations that some natural clusters will be represented by multiple clusters fund by the K-Means algorithm. We have discussed this issue in a previous blog entry. Secondly, the K-Means algorithm is in general incapable to find non-convex clusters (as clusters of K-Means algorithm form a voronoi segmentation of the data space.) The second limitation makes the K-Means algorithm inadequate for complex non-linear data.

Fortunately, there is simple way to overcome the mentioned problems of the two algorithms: we simply combine them together. That is, as illustrated in the following picture, we first apply the K-Means algorithm on a dataset; then apply the mean shift algorithm on the cluster centers found by the K-Means algorithm. The mean shift clustering step can be done quickly as  its input data (which are the cluster centers of the K-Mean algorithm ) is much smaller than the original dataset. We don't have to know the right cluster number for the K-Means algorithm: a number that is significantly larger than the number of natural clusters will be good enough for the task. The mean shift step will merge appropriate cluster centers to match the natural clusters. Since the clusters of the K-Means algorithm are normally located in high density sites, the mean shift step will normally not produce small uncertain clusters.

Furthermore, the above combination is also capable to find non-convex clusters. The following video clip demonstrates a such case with the VisuMap software.

The following is a series of maps for a data set from flow cytometry. The data set contains 500 000 data points that has 12 numeric attributes for 500 000 cells. The first map is a typical bi-variate map in flow cytometry analysis; The second map is a PCA map produced with VisuMap; The third map is a PCA map colored with K-Mean and Mean Shift algorithm. We see that the colored PCA map reveals much more details and sub-populations. It took about 2 minutes to produce the colored PCA map, whereas more than 10 hours with mean-shift algorithm alone.