nips nips2005 nips2005-127 nips2005-127-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Brendan J. Frey, Delbert Dueck
Abstract: Clustering is a fundamental problem in machine learning and has been approached in many ways. Two general and quite different approaches include iteratively fitting a mixture model (e.g., using EM) and linking together pairs of training cases that have high affinity (e.g., using spectral methods). Pair-wise clustering algorithms need not compute sufficient statistics and avoid poor solutions by directly placing similar examples in the same cluster. However, many applications require that each cluster of data be accurately described by a prototype or model, so affinity-based clustering – and its benefits – cannot be directly realized. We describe a technique called “affinity propagation”, which combines the advantages of both approaches. The method learns a mixture model of the data by recursively propagating affinity messages. We demonstrate affinity propagation on the problems of clustering image patches for image segmentation and learning mixtures of gene expression models from microarray data. We find that affinity propagation obtains better solutions than mixtures of Gaussians, the K-medoids algorithm, spectral clustering and hierarchical clustering, and is both able to find a pre-specified number of clusters and is able to automatically determine the number of clusters. Interestingly, affinity propagation can be viewed as belief propagation in a graphical model that accounts for pairwise training case likelihood functions and the identification of cluster centers. 1
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12] CM Bishop. Neural Networks for Pattern Recognition. Oxford University Press, NY, 1995. KA Heller, Z Ghahramani. Bayesian hierarchical clustering. ICML, 2005. M Meila, J Shi. Learning segmentation by random walks. NIPS 14, 2001. J Shi, J Malik. Normalized cuts and image segmentation. Proc CVPR, 731-737, 1997. A Ng, M Jordan, Y Weiss. On spectral clustering: Analysis and an algorithm. NIPS 14, 2001. N Shental A Zomet T Hertz Y Weiss. Pairwise clustering and graphical models NIPS 16 2003. R Rosales, BJ Frey. Learning generative models of affinity matrices. Proc UAI, 2003. M Charikar, S Guha, A Tardos, DB Shmoys. A constant-factor approximation algorithm for the k-median problem. J Comp and Sys Sci, 65:1, 129-149, 2002. J Malik et al.. Contour and texture analysis for image segmentation. IJCV 43:1, 2001. FR Kschischang, BJ Frey, H-A Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans Info Theory 47:2, 498-519, 2001. BJ Frey, QD Morris, M Robinson, TR Hughes. Finding novel transcripts in high-resolution genome-wide microarray data using the GenRate model. Proc RECOMB 2005, 2005. D. D. Shoemaker et al. Experimental annotation of the human genome using microarray technology. Nature 409, 922-927, 2001.