Identification of pattern similarities by unsupervised cluster analysis

Abstract

A method is provided for unsupervised clustering of data to identify pattern similarities. A clustering algorithm randomly divides the data into k different subsets and measures the similarity between pairs of datapoints within the subsets, assigning a score to the pairs based on similarity, with the greatest similarity giving the highest correlation score. A distribution of the scores is plotted for each k. The highest value of k that has a distribution that remains concentrated near the highest correlation score corresponds to the number of classes having pattern similarities.

1 . A non-transitory machine-readable medium comprising a plurality of instructions that in response to being executed result in a computing system executing a process for unsupervised classification of data in a dataset according to pattern similarities, comprising:
 a clustering function to randomly assign k class labels to the data and partition the dataset in k subsets, wherein k has a range with a minimum number of two;   a compare function to, for each value of k beginning with the minimum value of k for each pair of subsets, compute a correlation score on the intersection between the pair of subsets, wherein the correlation score comprises a similarity measure between the pair of subsets and the greatest similarity has the highest score; and   a histogram function to generate a distribution of the correlation scores for each value of k, wherein the distribution comprising the highest value of k that remains concentrated near the highest correlation score corresponds to an optimal granularity level for clustering of the data according to pattern similarities within the dataset, and to generate an output corresponding to clustered data for display or storage in a storage medium.   
     
     
         2 . The non-transitory machine-readable medium of  claim 1 , wherein the clustering function comprises a k-means algorithm. 
     
     
         3 . The non-transitory machine-readable medium of  claim 1 , wherein the clustering function comprises a hierarchical clustering algorithm. 
     
     
         4 . The non-transitory machine-readable medium of  claim 1 , wherein the optimal granularity level comprises a number of clusters for which there is a transition from a distribution that is peaked near a correlation score of “1” to a distribution that corresponds to random data. 
     
     
         5 . The non-transitory machine-readable medium of  claim 1 , wherein the similarity measure is obtained by measuring a residual of a fit of one cluster onto another cluster, wherein the residual fit comprises using a fit that is invariant with respect to affine transformations, wherein the affine transformations comprise a combination of translation, scaling and rotation. 
     
     
         6 . The non-transitory machine-readable medium of  claim 1 , wherein the dataset comprises gene expression data and the pattern similarities comprise co-regulation patterns. 
     
     
         7 . A non-transitory machine-readable medium comprising a plurality of instructions that in response to being executed result in a computing system separating classes within a dataset without supervision, wherein the computing system:
 selects a plurality of granularity levels k, and for each granularity level k:
 (a) induces perturbations in the dataset to generate a modified dataset; 
 (b) applies a clustering algorithm to the at least one modified dataset to produce k clusters under each of the perturbations; 
 (c) creates a data subset comprising the clusters identified in step (b); 
 (d) applies the clustering algorithm to the data subset using the same value of k clusters; 
 (e) determines the stability of the clusterings at each granularity level k by measuring dissimilarity between data in the data subset and a cluster center for the cluster into which the data was assigned; 
   measures fit of the data to the cluster centers for all k granularity levels, wherein the fit comprises using a fit that is invariant with respect to affine transformations, wherein the affine transformations comprise a combination of translation, scaling and rotation;   selects from among the plurality of granularity levels an optimum granularity level k corresponding to the best fit;   generates an output comprising the dataset clustered into a plurality of subsets corresponding to the optimal granularity level k; and   displays a graph showing the dataset clustered into the plurality of subsets, wherein the subsets correspond to classes.   
     
     
         8 . The non-transitory machine-readable medium of  claim 7 , 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. 
     
     
         9 . The non-transitory machine-readable medium of  claim 7 , further comprising, prior to selecting a plurality of granularity levels, ranking the data according to one or more quality criteria and selecting a pre-determined fraction of top ranked data. 
     
     
         10 . The non-transitory machine-readable medium of  claim 7 , wherein the clustering algorithm is a k-means algorithm. 
     
     
         11 . The non-transitory machine-readable medium of  claim 7 , wherein the clustering algorithm if hierarchical clustering. 
     
     
         12 . The non-transitory machine-readable medium of  claim 7 , wherein the optimal granularity level comprises a number of clusters for which there is a transition from a distribution that is peaked near a correlation score of “1” to a distribution that corresponds to random data. 
     
     
         13 . The non-transitory machine-readable medium of  claim 7 , wherein the similarity is obtained by measuring a residual of a fit of one cluster onto another cluster, wherein the residual fit comprises using a fit that is invariant with respect to affine transformations, wherein the affine transformations comprise a combination of translation, scaling and rotation. 
     
     
         14 . A non-transitory machine-readable medium comprising a plurality of instructions that in response to being executed result in a computing system determining without supervision an optimal number of classes within a dataset, wherein each class has pattern similarities, wherein the computing system:
 selects a range of granularity levels k, the range having a minimum of two;   applies a clustering algorithm to the dataset for that k clusters are produced;   for each value of k, selects a plurality of subsets of the dataset, wherein each sub-sample comprises a fixed fraction of the dataset;   selects a plurality of pairs of subsets;   calculates a similarity between each pair of the plurality of pairs of subsets;   determines a distribution of the similarities within the plurality of pairs of subsets;   compares distributions of the similarities for all k granularity levels;   selects from among the plurality of granularity levels an optimal granularity level k whose distribution of the similarities has the highest correlation score among correlation scores for all distributions of similarities;   generates an output comprising the dataset clustered into an optimal number of subsets corresponding to the optimal k; and   displays a graph of the clustered dataset showing pattern similarities according to the optimal number of subsets.   
     
     
         15 . The non-transitory machine-readable medium of  claim 14 , wherein the clustering algorithm is a k-means algorithm. 
     
     
         16 . The non-transitory machine-readable medium of  claim 14 , wherein the clustering algorithm if hierarchical clustering. 
     
     
         17 . The non-transitory machine-readable medium of  claim 14 , wherein the optimal granularity level comprises a number of clusters for which there is a transition from a distribution that is peaked near a correlation score of “1” to a distribution that corresponds to random data. 
     
     
         18 . The non-transitory machine-readable medium of  claim 14 , wherein the similarity is obtained by measuring a residual of a fit of one cluster onto another cluster, wherein the residual fit comprises using a fit that is invariant with respect to affine transformations, wherein the affine transformations comprise a combination of translation, scaling and rotation.