Hi there,
I have about ~1 million compounds to cluster. While calculating the fingerprints were relatively fast using Canvas on a desktop computer, I found clustering (by K-Means) very slow. For example, clustering them into 128 clusters took ~10 hrs, and I wonder if this would increase exponentially as I increase the number of clusters.
So are there alternative/faster methods to cluster a library of compounds into arbitrary number of clusters?
Thanks!
Dear Yun
The Schrödinger cheminformatics program Canvas performs clustering based on fingerprints or properties.
Best
K-means clustering has polynomial complexity both with respect to the number of objects and to the number of clusters needed. One way to improve the performance would be to split the 1M set into 2 clusters. Then these smaller clusters can be split into 2 clusters each. The resulting 4 clusters should be small enough to be clustered into any number of clusters relatively quickly. The total time of this hierarchical clustering would be significantly shorter than if you'd cluster 1M into a required large number of clusters.
You can try with bisecting K-mean clustering algorithm for reducing the runtime.
DataWarrior at openmolecules.org has several tools to cluster compounds for you, and can be done with several different molecular descriptors.
Clustering of data forms the basis of many modeling and pattern classification algorithms. The purpose of clustering is to find natural groupings of data in a large data set. The clustering algorithms can be classified into several categories such as: partitioning clustering, hierarchical clustering, density based clustering, grid based clustering, and model based clustering.
The k-means approach is the poular sine itis characterized by its simplicity of implementation. But, it may converge to local minima in the case of poor initializations because they are based on the minimization of nonlinear criterion. Furthermore, their performances degrade in the case of the presence of outliers in the data to be classified. In addition, it assumes that the number of sub-models is a priori known. To overcome these problems, other algorithms are proposed such as Chiu's algorithm,. The Chiu's algorithm for data classification allows us to reduce the effect of outliers. Moreover, it does not need any initialization. In addition, it is able to automatically generate the number of sub-models. A modification of this approach was proposed to allow the number of sub-models to be estimated as the data are classified. This modified approach uses a hierarchical classification method called single-linkage. The idea of this method consists in defining a distance between two disjoint local sets. These sets are then fused if a given criterion is verified. It should be noted that the number of sub-models is critically dependent on a parameter supplied by the user. In fact, a small value of this parameter would produce a large number of sub-models. However, if the parameter has a too large value, it could give a single sub-linear model. Another method was introduced which exploits a statistical classification approach based on a Gaussian mixture model. In fact, its performance degrades when the data of different sub-models do not form classes quite distant in the regression space. In addition, the equipartition of different models can favorite some models over others in decision making. It assumes that the number of sub-models and the orders are known a priori. Finally, the method proposed which is based on unsupervised classification algorithm which is combined with regression techniques in order to separate the data according to their respective sub-models and thus estimate their parameters. The classification uses the principle of the k-nearest neighbors algorithm. In fact, each nearest neighbor of a given vector provides information on the allocation of this vector. This approach requires the knowledge of the orders of the system. In addition, a single adjustment parameter must be provided by the user. This study allows us to identify the main drawbacks of the main existing methods, which can be summarized as follows:
- Most of them are based on the optimization of nonlinear criteria. Consequently, they may converge to local minima in the case of poor initializations.
- Their performances degrade in the case of the presence of outliers in the data to be classified.
- Most of them assume that the number of sub-models is known a priori.
To overcome these problems, we recommend the use of density-based spatial clustering of applications with noise (DBSCAN) algorithm, which is a pioneer algorithm of density-based clustering. This choice is justified by the fact that the algorithm automatically generates the number of models. In addition, it is characterized by its robustness to the classification of noisy measurements and the containing outliers.
- Badges
- Science topic
- Similar topics
- Social Psychology
- Attitude