nips nips2010 nips2010-230 nips2010-230-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hairong Liu, Longin J. Latecki, Shuicheng Yan
Abstract: In this paper, we regard clustering as ensembles of k-ary affinity relations and clusters correspond to subsets of objects with maximal average affinity relations. The average affinity relation of a cluster is relaxed and well approximated by a constrained homogenous function. We present an efficient procedure to solve this optimization problem, and show that the underlying clusters can be robustly revealed by using priors systematically constructed from the data. Our method can automatically select some points to form clusters, leaving other points un-grouped; thus it is inherently robust to large numbers of outliers, which has seriously limited the applicability of classical methods. Our method also provides a unified solution to clustering from k-ary affinity relations with k ≥ 2, that is, it applies to both graph-based and hypergraph-based clustering problems. Both theoretical analysis and experimental results show the superiority of our method over classical solutions to the clustering problem, especially when there exists a large number of outliers.
[1] A. Jain, M. Murty, and P. Flynn, “Data clustering: a review,” ACM Computing Surveys, vol. 31, no. 3, pp. 264–323, 1999.
[2] T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu, “An efficient k-means clustering algorithm: Analysis and implementation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp. 881–892, 2002.
[3] A. Ng, M. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” in Advances in Neural Information Processing Systems, vol. 2, 2002, pp. 849–856.
[4] I. Dhillon, Y. Guan, and B. Kulis, “Kernel k-means: spectral clustering and normalized cuts,” in Proceedings of the tenth ACM International Conference on Knowledge Discovery and Data Mining, 2004, pp. 551–556.
[5] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888–905, 2000.
[6] B. Frey and D. Dueck, “Clustering by passing messages between data points,” Science, vol. 315, no. 5814, pp. 972–976, 2007.
[7] J. Zien, M. Schlag, and P. Chan, “Multilevel spectral hypergraph partitioning with arbitrary vertex sizes,” IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 18, no. 9, pp. 1389–1399, 1999.
[8] J. Rodriguez, “On the Laplacian spectrum and walk-regular hypergraphs,” Linear and Multilinear Algebra, vol. 51, no. 3, pp. 285–297, 2003.
[9] S. Agarwal, J. Lim, L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie, “Beyond pairwise clustering,” in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, 2005, pp. 838–845.
[10] D. Zhou, J. Huang, and B. Scholkopf, “Learning with hypergraphs: Clustering, classification, and embedding,” in Advances in Neural Information Processing Systems, vol. 19, 2007, pp. 1601–1608.
[11] A. Shashua, R. Zass, and T. Hazan, “Multi-way clustering using super-symmetric non-negative tensor factorization,” in European Conference on Computer Vision, 2006, pp. 595–608.
[12] S. Bulo and M. Pelillo, “A game-theoretic approach to hypergraph clustering,” in Advances in Neural Information Processing Systems, 2009.
[13] M. Pavan and M. Pelillo, “Dominant sets and pairwise clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 167–172, 2007.
[14] H. Kuhn and A. Tucker, “Nonlinear programming,” ACM SIGMAP Bulletin, pp. 6–18, 1982.
[15] P. Belhumeur and D. Kriegman, “What is the set of images of an object under all possible illumination conditions?” International Journal of Computer Vision, vol. 28, no. 3, pp. 245– 260, 1998.
[16] K. Lee, J. Ho, and D. Kriegman, “Acquiring linear subspaces for face recognition under variable lighting,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 5, pp. 684–698, 2005.
[17] L. Latecki, R. Lakamper, and T. Eckhardt, “Shape descriptors for non-rigid shapes with a single closed contour,” in IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, 2000, pp. 65–72. 9