Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> This paper introduces the problem of combining multiple partitionings of a set of objects into a single consolidated clustering without accessing the features or algorithms that determined these partitionings. We first identify several application scenarios for the resultant 'knowledge reuse' framework that we call cluster ensembles. The cluster ensemble problem is then formalized as a combinatorial optimization problem in terms of shared mutual information. In addition to a direct maximization approach, we propose three effective and efficient techniques for obtaining high-quality combiners (consensus functions). The first combiner induces a similarity measure from the partitionings and then reclusters the objects. The second combiner is based on hypergraph partitioning. The third one collapses groups of clusters into meta-clusters which then compete for each object to determine the combined clustering. Due to the low computational costs of our techniques, it is quite feasible to use a supra-consensus function that evaluates all three approaches against the objective function and picks the best solution for a given situation. We evaluate the effectiveness of cluster ensembles in three qualitatively different application scenarios: (i) where the original clusters were formed based on non-identical sets of features, (ii) where the original clustering algorithms worked on non-identical sets of objects, and (iii) where a common data-set is used and the main purpose of combining multiple clusterings is to improve the quality and robustness of the solution. Promising results are obtained in all three situations for synthetic as well as real data-sets. <s> BIB001 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> We introduce a general technique for making statistical inference from clustering tools applied to gene expression microarray data. The approach utilizes an analysis of variance model to achieve normalization and estimate differential expression of genes across multiple conditions. Statistical inference is based on the application of a randomization technique, bootstrapping. Bootstrapping has previously been used to obtain confidence intervals for estimates of differential expression for individual genes. Here we apply bootstrapping to assess the stability of results from a cluster analysis. We illustrate the technique with a publicly available data set and draw conclusions about the reliability of clustering results in light of variation in the data. The bootstrapping procedure relies on experimental replication. We discuss the implications of replication and good design in microarray experiments. <s> BIB002 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> We introduce a method for validation of results obtained by clustering analysis of data. The method is based on resampling the available data. A figure of merit that measures the stability of clustering solutions against resampling is introduced. Clusters which are stable against resampling give rise to local maxima of this figure of merit. This is presented first for a one-dimensional data set, for which an analytic approximation for the figure of merit is derived and compared with numerical measurements. Next, the applicability of the method is demonstrated for higher dimensional data, including gene microarray expression data. <s> BIB003 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> We present a method for visually and quantitatively assessing the presence of structure in clustered data. The method exploits measurements of the stability of clustering solutions obtained by perturbing the data set. Stability is characterized by the distribution of pairwise similarities between clusterings obtained from sub samples of the data. High pairwise similarities indicate a stable clustering pattern. The method can be used with any clustering algorithm; it provides a means of rationally defining an optimum number of clusters, and can also detect the lack of structure in data. We show results on artificial and microarray data using a hierarchical clustering algorithm. <s> BIB004 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> BackgroundA potential benefit of profiling of tissue samples using microarrays is the generation of molecular fingerprints that will define subtypes of disease. Hierarchical clustering has been the primary analytical tool used to define disease subtypes from microarray experiments in cancer settings. Assessing cluster reliability poses a major complication in analyzing output from clustering procedures. While most work has focused on estimating the number of clusters in a dataset, the question of stability of individual-level clusters has not been addressed.ResultsWe address this problem by developing cluster stability scores using subsampling techniques. These scores exploit the redundancy in biologically discriminatory information on the chip. Our approach is generic and can be used with any clustering method. We propose procedures for calculating cluster stability scores for situations involving both known and unknown numbers of clusters. We also develop cluster-size adjusted stability scores. The method is illustrated by application to data three cancer studies; one involving childhood cancers, the second involving B-cell lymphoma, and the final is from a malignant melanoma study.AvailabilityCode implementing the proposed analytic method can be obtained at the second author's website. <s> BIB005 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set. The criterion, called variation of information (VI), measures the amount of information lost and gained in changing from clustering \({\cal C}\) to clustering \({\cal C}'\). The criterion makes no assumptions about how the clusterings were generated and applies to both soft and hard clusterings. The basic properties of VI are presented and discussed from the point of view of comparing clusterings. In particular, the VI is positive, symmetric and obeys the triangle inequality. Thus, surprisingly enough, it is a true metric on the space of clusterings. <s> BIB006 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> Data clustering describes a set of frequently employed techniques in exploratory data analysis to extract "natural" group structure in data. Such groupings need to be validated to separate the signal in the data from spurious structure. In this context, finding an appropriate number of clusters is a particularly important model selection question. We introduce a measure of cluster stability to assess the validity of a cluster model. This stability measure quantifies the reproducibility of clustering solutions on a second sample, and it can be interpreted as a classification risk with regard to class labels produced by a clustering algorithm. The preferred number of clusters is determined by minimizing this classification risk as a function of the number of clusters. Convincing results are achieved on simulated as well as gene expression data sets. Comparisons to other methods demonstrate the competitive performance of our method and its suitability as a general validation tool for clustering solutions in real-world problems. <s> BIB007 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> We introduce an approach for validating clustering results based on partition stability under a nearest-neighbor resampling. The approach is relatively robust, efficient, and avoids conceptual problems of other common validation strategies. Encouraging results compared to those of subsampling-based consensus clustering are presented for simulated data and (tumor) gene expression benchmark data sets. The proposed method is discussed in view of future applications to unsupervised learning from sample data <s> BIB008 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> Background ::: Cluster analysis has been widely applied for investigating structure in bio-molecular data. A drawback of most clustering algorithms is that they cannot automatically detect the "natural" number of clusters underlying the data, and in many cases we have no enough "a priori" biological knowledge to evaluate both the number of clusters as well as their validity. Recently several methods based on the concept of stability have been proposed to estimate the "optimal" number of clusters, but despite their successful application to the analysis of complex bio-molecular data, the assessment of the statistical significance of the discovered clustering solutions and the detection of multiple structures simultaneously present in high-dimensional bio-molecular data are still major problems. <s> BIB009 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> BackgroundThe unsupervised discovery of structures (i.e. clusterings) underlying data is a central issue in several branches of bioinformatics. Methods based on the concept of stability have been recently proposed to assess the reliability of a clustering procedure and to estimate the “optimal” number of clusters in bio-molecular data. A major problem with stability-based methods is the detection of multi-level structures (e.g. hierarchical functional classes of genes), and the assessment of their statistical significance. In this context, a chi-square based statistical test of hypothesis has been proposed; however, to assure the correctness of this technique some assumptions about the distribution of the data are needed.ResultsTo assess the statistical significance and to discover multi-level structures in bio-molecular data, a new method based on Bernstein's inequality is proposed. This approach makes no assumptions about the distribution of the data, thus assuring a reliable application to a large range of bioinformatics problems. Results with synthetic and DNA microarray data show the effectiveness of the proposed method.ConclusionsThe Bernstein test, due to its loose assumptions, is more sensitive than the chi-square test to the detection of multiple structures simultaneously present in the data. Nevertheless it is less selective, that is subject to more false positives, but adding independence assumptions, a more selective variant of the Bernstein inequality-based test is also presented. The proposed methods can be applied to discover multiple structures and to assess their significance in different types of bio-molecular data. <s> BIB010 </s> Clustering Stability: An Overview <s> Clustering stability: definition and implementation <s> Estimating the true number of clusters in a data set is one of the major challenges in cluster analysis. Yet in certain domains,knowing the true number of clusters is of high importance. For example, in medical research, detecting the true number of groups and sub-groups of cancer would be of utmost importance for their effective treatment. In this paper we propose a novel method to estimate the number of clusters in a micro array data set based on the consensus clustering approach. Although the main objective of consensus clustering is to discover a robust and high quality cluster structure in a data set, closer inspection of the set of clusterings obtained can often give valuable information about the appropriate number of clusters present. More specifically, the set off clusterings obtained when the specified number of clusters coincides with the true number of clusters tends to be less diverse.To quantify this diversity we develop a novel index, namely the Consensus Index (CI), which is built upon a suitable clustering similarity measure such as the well known Adjusted Rand Index (ARI)or our recently developed, information theoretic based index, namely the Adjusted Mutual Information (AMI). Our experiments on both synthetic and real microarray data sets indicate that the CI is a useful indicator for determining the appropriate number of clusters. <s> BIB011
A clustering of a data set S = {X 1 , . . . , X n } is a function that assigns labels to all points of S, that is C K : S → {1, . . . , K}. Here K denotes the number of clusters. A clustering algorithm is a procedure that takes a set S of points as input and outputs a clustering of S. The clustering algorithms considered in this paper take an additional parameter as input, namely the number K of clusters they are supposed to construct. We analyze clustering stability in a statistical setup. The data set S is assumed to consist of n data points X 1 , . . . , X n that have been drawn independently from some unknown underlying distribution P on some space X . The final goal is to use these sample points to construct a good partition of the underlying space X . For some theoretical results it will be easier to ignore sampling effects and directly work on the underlying space X endowed with the probability distribution P . This can be considered as the case of having "infinitely many" data points. We sometimes call this the limit case for n → ∞. Assume we agree on a way to compute distances d(C, C ) between different clusterings C and C (see below for details). Then, for a fixed probability distribution P , a fixed number K of clusters and a fixed sample size n, the instability of a clustering algorithm is defined as the expected distance between two clusterings The expectation is taken with respect to the drawing of the two samples. In practice, a large variety of methods has been devised to compute stability scores and use them for model selection. On a very general level they works as follows: Given: a set S of data points, a clustering algorithm A that takes the number k of clusters as input (1) For k = 2, . . . , kmax Cluster the data set S b with algorithm A into k clusters to obtain clustering C b (c) For b, b = 1, . . . , bmax: Compute pairwise distances d(C b , C b ) between these clusterings (using one of the distance functions described below) (d) Compute instability as the mean distance between clusterings C b : (2) Choose the parameter k that gives the best stability, in the simplest case as follows: (see below for more options). This scheme gives a very rough overview of how clustering stability can be used for model selection. In practice, many details have to be taken into account, and they will be discussed in the next section. Finally, we want to mention an approach that is vaguely related to clustering stability, namely the ensemble method BIB001 . Here, an ensemble of algorithms is applied to one fixed data set. Then a final clustering is built from the results of the individual algorithms. We are not going to discuss this approach in our paper. Generating perturbed versions of the data set. To be able to evaluate the stability of a fixed clustering algorithm we need to run the clustering algorithm several times on slightly different data sets. To this end we need to generate perturbed versions of the original data set. In practice, the following schemes have been used: • Draw a random subsample of the original data set without replacement BIB003 BIB004  BIB007 ). • Add random noise to the original data points (Bittner et al., 2000, Möller and BIB008 . • If the original data set is high-dimensional, use different random projections in low-dimensional spaces, and then cluster the low-dimensional data sets BIB005 . • If we work in a model-based framework, sample data from the model BIB002 ). • Draw a random sample of the original data with replacement. This approach has not been reported in the literature yet, but it avoids the problem of setting the size of the subsample. For good reasons, this kind of sampling is the standard in the bootstrap literature  and might also have advantages in the stability setting. This scheme requires that the algorithm can deal with weighted data points (because some data points will occur several times in the sample). In all cases, there is a trade-off that has to be treated carefully. If we change the data set too much (for example, the subsample is too small, or the noise too large), then we might destroy the structure we want to discover by clustering. If we change the data set too little, then the clustering algorithm will always obtain the same results, and we will observe trivial stability. It is hard to quantify this trade-off in practice. Which clusterings to compare? Different protocols are used to compare the clusterings on the different data sets S b . • Compare the clustering of the original data set with the clusterings obtained on subsamples BIB003 ). • Compare clusterings of overlapping subsamples on the data points where both clusterings are defined. BIB004 . • Compare clusterings of disjoint subsamples  Dudoit, 2001, Lange et al., 2004) . Here we first need to apply an extension operator to extend each clustering to the domain of the other clustering. Distances between clusterings. If two clusterings are defined on the same data points, then it is straightforward to compute a distance score between these clusterings based on any of the well-known clustering distances such as the Rand index, Jaccard index, Hamming distance, minimal matching distance, Variation of Information distance BIB006 . All these distances count, in some way or the other, points or pairs of points on which the two clusterings agree or disagree. The most convenient choice from a theoretical point of view is the minimal matching distance. For two clusterings C, C of the same data set of n points it is defined as where the minimum is taken over all permutations π of the K labels. Intuitively, the minimal matching distance measures the same quantity as the 0-1-loss used in supervised classification. For a stability study involving the adjusted Rand index or an adjusted mutual information index see BIB011 . If two clusterings are defined on different data sets one has two choices. If the two data sets have a big overlap one can use a restriction operator to restrict the clusterings to the points that are contained in both data sets. On this restricted set one can then compute a standard distance between the two clusterings. The other possibility is to use an extension operator to extend both clusterings from their domain to the domain of the other clustering. Then one can compute a standard distance between the two clusterings as they are now both defined on the joint domain. For center-based clusterings, as constructed by the K-means algorithm, a natural extension operator exists. Namely, to a new data point we simply assign the label of the closest cluster center. A more general scheme to extend an existing clustering to new data points is to train a classifier on the old data points and use its predictions as labels on the new data points. However, in the context of clustering stability it is not obvious what kind of bias we introduce with this approach. Stability scores and their normalization. The stability protocol outlined above results in a set of distance values In most approaches, one summarizes these values by taking their mean: Note that the mean is the simplest summary statistic one can compute based on the distance values d(C b , C b ). A different approach is to use the area under the cumulative distribution function of the distance values as the stability score, see BIB004 or BIB009 for details. In principle one could also come up with more elaborate statistics based on distance values. To the best of our knowledge, such concepts have not been used so far. The simplest way to select the number K of clusters is to minimize the instability: This approach has been suggested in BIB003 . However, an important fact to note is that Instab(k, n) trivially scales with k, regardless of what the underlying data structure is. For example, in the top left plot in Figure 2 .1 we can see that even for a completely unclustered data set, Instab(n, k) increases with k. When using stability for model selection, one should correct for the trivial scaling of Instab, otherwise it might be meaningless to take the minimum afterwards. There exist several different normalization protocols: • Normalization using a reference null distribution  Dudoit, 2001, Bertoni and BIB009 . One repeatedly samples data sets from some reference null distribution. Such a distribution is defined on the same domain as the data points, but does not possess any cluster structure. In simple cases one can use the uniform distribution on the data domain as null distribution. A more practical approach is to scramble the individual dimensions of the existing data points and use the "scrambled points" as null distribution (see  Dudoit, 2001, Bertoni and BIB009 for details). Once we have drawn several data sets from the null distribution, we cluster them using our clustering algorithm and compute the corresponding stability score Instab null as above. The normalized stability is then defined as Instab norm := Instab/ Instab null . • Normalization by random labels BIB007 . First, we cluster each of the data sets S b as in the protocol above to obtain the clusterings C b . Then, we randomly permute these labels. That is, we assign the label to data point X i that belonged to X π(i) , where π is a permutation of {1, . . . , n}. This leads to a permuted clustering C b, perm . We then compute the stability score Instab as above, and similarly we compute Instab perm for the permuted clusterings. The normalized stability is then defined as Instab norm := Instab/ Instab perm . Once we computed the normalized stability scores Instab norm we can choose the number of clusters that has smallest normalized instability, that is This approach has been taken for example in BIB004 , BIB007 . Selecting K based on statistical tests. A second approach to select the final number of clusters is to use a statistical test. Similarly to the normalization considered above, the idea is to compute stability scores not only on the actual data set, but also on "null data sets" drawn from some reference null distribution. Then one tests whether, for a given parameter k, the stability on the actual data is significantly larger than the one computed on the null data. If there are several values k for which this is the case, then one selects the one that is most significant. The most well-known implementation of such a procedure uses bootstrap methods  . Other authors use a χ 2 -test BIB009 or a test based on the Bernstein inequality BIB010 . To summarize, there are many different implementations for selecting the number K of clusters based on stability scores. Until now, there does not exist any convincing empirical study that thoroughly compares all these approaches on a variety of data sets. In my opinion, even fundamental issues such as the normalization have not been investigated in enough detail. For example, in my experience normalization often has no effect whatsoever (but I did not conduct a thorough study either). To put stability-based model selection on a firm ground it would be crucial to compare the different approaches with each other in an extensive case study.