An Indicator for the Number of Clusters: Using a Linear Map to Simplex Structure
- 1.6k Downloads
The problem of clustering data can be formulated as a graph partitioning problem. In this setting, spectral methods for obtaining optimal solutions have received a lot of attention recently. We describe Perron Cluster Cluster Analysis (PCCA) and establish a connection to spectral graph partitioning. We show that in our approach a clustering can be efficiently computed by mapping the eigenvector data onto a simplex. To deal with the prevalent problem of noisy and possibly overlapping data we introduce the Min-chi indicator which helps in confirming the existence of a partition of the data and in selecting the number of clusters with quite favorable performance. Furthermore, if no hard partition exists in the data, the Min-chi can guide in selecting the number of modes in a mixture model. We close with showing results on simulated data generated by a mixture of Gaussians.
KeywordsMixture Model Spectral Cluster Simplex Algorithm Stochastic Matrix Hard Partition
Unable to display preview. Download preview PDF.
- HASTIE, T., TIBSHIRANI, R. and FRIEDMAN, J. (2001): The Elements of Statistical Learning. Springer, Berlin.Google Scholar
- JAIN, A.K. and DUBES, R.C. (1988): Algorithms for clustering data. Prentice Hall, Engelwood Cliffs.Google Scholar
- KANNAN, R., VEMPALA, S. and VETTA, A. (1999): On Clusterings: Good, Bad and Spectral. Proceedings of IEEE Foundations of Computer Science.Google Scholar
- MCLACHLAN, G.J. and BASFORD, K.E. (1988): Mixture Models: Inference and Applications to Clustering. Marcel Dekker, Inc., New York, Basel.Google Scholar
- NG, A. Y., JORDAN, M. and WEISS, J (2002): On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems 14.Google Scholar
- SHI, J. and MALIK, J. (2000): Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905.Google Scholar
- WEBER, M. (2004): Clustering by using a simplex structure. Technical report, ZR-04-03, Zuse Institute Berlin.Google Scholar
- WEBER, M. and GALLIAT, T (2002): Characterization of transition states in conformational dynamics using Fuzzy sets. Technical Report 02-12, Zuse Institute Berlin (ZIB).Google Scholar