Model selection for cluster data analysis

Abstract

A model selection method is provided for choosing the number of clusters, or more generally the parameters of a clustering algorithm. The algorithm is based on comparing the similarity between pairs of clustering runs on sub-samples or other perturbations of the data. High pairwise similarities show that the clustering represents a stable pattern in the data. The method is applicable to any clustering algorithm, and can also detect lack of structure. We show results on artificial and real data using a hierarchical clustering algorithm.

1 . A method for clustering data in a dataset comprising: 
 selecting a plurality of granularity levels k;    applying a clustering algorithm to a sub-sample of the dataset so that k clusters are produced;    for each k, selecting a plurality of sub-samples of the dataset;    selecting a plurality of pairs of sub-samples calculating a similarity between the plurality of pairs;    determining a distribution of the similarity between the plurality of pairs;    comparing the distributions for all k; and    selecting as the optimum granularity level, the k corresponding to the tightest distribution.    
   
   
       2 . The method of  claim 1 , wherein the clustering algorithm is A k-means algorithm.  
   
   
       3 . The method of  claim 1 , wherein the clustering algorithm is hierarchical clustering.  
   
   
       4 . The method of  claim 1 , wherein the step of selecting the highest granularity level comprises selecting a number of clusters for which there is a transition from a distribution that is peaked near 1 to a wide distribution.  
   
   
       5 . The method of  claim 1 , further comprising, after determining the distribution, calculating a cumulative distribution function for each granularity level, wherein the step of selecting the highest granularity level comprises identifying an increase in the area under the cumulative distribution function.  
   
   
       6 . The method of  claim 1 , wherein the data comprises gene expression coefficients.  
   
   
       7 . A method for analysis of data in a dataset comprising: 
 selecting a plurality of granularity levels in a clustering algorithm;    for each granularity level: 
 inducing a perturbation in the data;  
 selecting a plurality of pairs of perturbations;  
 computing a pairwise similarity for each plurality of pairs;  
 determining a distribution of the pairwise similarity;  
   selecting the highest granularity level having the tightest distribution.    
   
   
       8 . The method of  claim 7 , wherein the step of inducing comprises grouping the data into a plurality of sub-samples.  
   
   
       9 . The method of  claim 8  wherein the step of grouping comprises applying a k-means clustering algorithm to the data.  
   
   
       10 . The method of  claim 8  wherein the step of grouping comprises applying a hierarchical clustering algorithm to the data.  
   
   
       11 . The method of  claim 7 , wherein the step of inducing a perturbation comprises initialization of the k-means algorithm.  
   
   
       12 . The method of  claim 7 , wherein the step of inducing a perturbation comprises adding random noise to the data.  
   
   
       13 . The method of  claim 7 , wherein the step of selecting the highest granularity level comprises selecting a number of clusters for which there is a transition from a distribution that is peaked near 1 to a wide distribution.  
   
   
       14 . The method of  claim 7 , further comprising, after determining the distribution, calculating a cumulative distribution function for each granularity level, wherein the step of selecting the highest granularity level comprises identifying an increase in the area under the cumulative distribution function.  
   
   
       15 . The method of  claim 7 , wherein the data comprises gene expression coefficients.  
   
   
       16 . A method for clustering data comprising a plurality of structured patterns, the method comprising: 
 (a) selecting a clustering algorithm based on a dissimilarity measure between pairs of structured patterns;    (b) randomly assigning class labels to the structured patterns;    (c) defining a plurality of cluster centers by averaging structured patterns within each labeled class;    (d) measuring dissimilarity between each structured pattern and its corresponding cluster center by measuring a residual of a fit of one structured pattern onto another structured pattern;    (e) reassigning structured patterns to the labeled class with the most similar cluster center; and    (f) repeating steps (c) through (e) until assignment of structured patterns to the labeled classes remains constant.    
   
   
       17 . The method of  claim 16 , wherein step (d) comprises using a fit that is invariant with respect to affine transformations.  
   
   
       18 . The method of  claim 17 , wherein the affine transformations comprise a combination of translation, scaling and rotation.  
   
   
       19 . The method of  claim 16 , further comprising calculating an average structured pattern, wherein the residual is an average residual of the fit of each structured pattern to the average structured pattern.  
   
   
       20 . The method of  claim 16 , wherein step (d) comprises measuring a Euclidean distance and a residual of a fit of one structured pattern onto another structured pattern.  
   
   
       21 . The method of  claim 16 , further comprising, after step (c), clustering the cluster centers.  
   
   
       22 . The method of  claim 16 , wherein the clustering algorithm is a k-means algorithm.  
   
   
       23 . The method of  claim 16 , wherein the structured patterns are temporal profiles.  
   
   
       24 . The method of  claim 23 , wherein the temporal profiles are gene expression profiles.  
   
   
       25 . A method for clustering patterns in a dataset comprising: 
 selecting a plurality of granularity levels k;    selecting a clustering algorithm adapted for producing a number of cluster centers equal to k and for assigning patterns to clusters corresponding to the cluster centers;    for each granularity level k: 
 (a) inducing perturbations in the dataset to generate a modified dataset;  
 (b) applying the clustering algorithm to the at least one modified dataset to produce k clusters under each of the perturbations;  
 (c) creating a new dataset comprising the cluster centers identified in step (b);  
 (d) applying the clustering algorithm to the new dataset using the same value of k clusters;  
 (e) determining the stability of the clusterings at each granularity level k by measuring dissimilarity between data in the new dataset and the cluster center for the cluster into which the data was assigned;  
   measuring fit of the data to the cluster centers for all k; and    selecting as the optimum granularity level the k corresponding to the best fit.    
   
   
       26 . The method of  claim 25 , wherein the perturbations comprise a combination of one or more of sub-sampling the dataset, changing initialization of the clustering algorithm, and adding noise to the dataset.  
   
   
       27 . The method of  claim 25 , wherein the dataset comprises gene expression profiles.