cvpr cvpr2013 cvpr2013-93 cvpr2013-93-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Shmuel Asafi, Daniel Cohen-Or
Abstract: In this paper, we introduce a new approach to constrained clustering which treats the constraints as features. Our method augments the original feature space with additional dimensions, each of which derived from a given Cannot-link constraints. The specified Cannot-link pair gets extreme coordinates values, and the rest of the points get coordinate values that express their spatial influence from the specified constrained pair. After augmenting all the new features, a standard unconstrained clustering algorithm can be performed, like k-means or spectral clustering. We demonstrate the efficacy of our method for active semi-supervised learning applied to image segmentation and compare it to alternative methods. We also evaluate the performance of our method on the four most commonly evaluated datasets from the UCI machine learning repository.
[1] K. Wagstaff and C. Cardie, Clustering with Instance-level Constraints, The Seventeenth International Conference on Machine Learning, 2000.
[2] D. Klein, S. D. Kamvar and C. D. Manning. From instancelevel constraints to space-level constraints: Making the most of prior knowledge in data clustering, The Nineteenth International Conference on Machine Learning, 2002.
[3] Z. Li, J. Liu and X. Tang Constrained Clustering via Spectral Regularization, CVPR 2009.
[4] I. Davidson and S. S. Ravi Clustering With Constraints: Feasibility Issues and the k-Means Algorithm, Fifth SIAM International Conference, 2005.
[5] K. Wagstaff and C. Cardie Clustering with Instance-level Constraints Seventeenth International Conference on Machine Learning, 2000
[6] I. Davidson and S. S. Ravi Agglomerative Hierarchical Clus- tering with Constraints: Theoretical and Empirical Results, Lecture Notes in Computer Science, 2005.
[7] I. Davidson and S. S. Ravi emphUsing Instance-Level Constraints in Agglomerative Hierarchical Clustering: Theoretical and Empirical Results, Data Mining and Knowledge Discovery, 2009.
[8] K. Wagstaff, C. Cardie, S. Rogers and S. Schroedl Constrained K-means Clustering with Background Knowledge, Eighteenth International Conference on Machine Learning, 2001.
[9] E. P. Xing, A. Y. Ng, M. I. Jordan and S. Russell Distance Metric Learning, with Application to Clustering with SideInformation, Advances in Neural Information Processing Systems 15, 2002.
[10] S.C.H. Hoi, W.Liu and S. Chang Semi-Supervised Distance Metric Learning for Collaborative Image Retrieval, CVPR 2008.
[11] A. Bar-Hillel, T. Hertz, N. Shental and D. Weinshall Learning Distance Functions using Equivalence Relations, Twentieth International Conference on Machine Learning, 2003.
[12] S. D. Kamvar, D. Klein, C. D. Manning Spectral Learning, IJCAI 2003.
[13] A. Sharma, E. Lavante and R. Horaud Learning Shape Segmentation Using Constrained Spectral Clustering and Probabilistic Label Transfer, Eleventh European Conference on Computer Vision, 2010.
[14] Z. Lu and M. A. Carreira-Perpinan Constrained Spectral Clustering through Afnity Propagation, CVPR 2008.
[15] X. Wang, B. Qian and I. Davidson On Constrained Spectral Clustering and Its Applications, Cornell University Library, 2012.
[16] Q. Xu, M. desJardins, K. Wagstaff Constrained Spectral Clustering under a Local Proximity Structure Assumption, FLAIRS-05, 2005.
[17] X. Wang and I. Davidson Active Spectral Clustering, ICDM 2010.
[18] Y. Wang, S. Asafi, O. van Kaick, H. Zhang and D. Cohen-Or Active Co-Analysis of a Set of Shapes, Sigraph Asia, 2013.
[19] S. Lafon and A. B. Lee Diffusion Maps and CoarseGraining: A Unified Framework for Dimensionality Reduction, Graph Partitioning, and Data Set Parameterization, IEEE Trans. on Pattern Analysis and Machine Intelligence 28(9): 1393-1403, 2006.
[20] B. Nadler, S. Lafon, R. R. Coifman and I. G. Kevrekidis Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators, Advances in Neural Information Processing Systems 18, 2005.
[21] M. Liu, O. Tuzel, S. Ramalingam, and R. Chellappa Entropy Rate Superpixel Segmentation, IEEE Conference on Computer Vision and Pattern Recognition (CVPR 11) , Colorado Spring, 2011.
[22] D. Martin and C. Fowlkes and D. Tal and J. Malik A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics, Proc. 8th Int’l Conf. Computer Vision (ICCV), 2001.
[23] A. Asuncion and D. Newman. UCI machine learning repository, 2007.
[24] K. Y. Yeung and W. L. Ruzzo Details of the Adjusted Rand index and Clustering algorithms, 2001 .
[25] J.V. Davis, B. Kulis, P. Jain, S. Sra and I.S. Dhillon Information-theoretic metric learning, ICML, 2007.
[26] P. He, X. Xu, and L. Chen Constrained Clustering with Local Constraint Propagation, Computer Vision ECCV, 2012.
[27] Z. Lu, H.S. Ip Constrained Spectral Clustering via Exhaustive and Efficient Constraint Propagation, Computer Vision ECCV, 2010. 111666334199