Revisiting probabilistic models for clustering with pair-wise constraints

ABSTRACT

We revisit recently proposed algorithms for probabilistic clustering with pair-wise constraints between data points. We evaluate and compare existing techniques in terms of robustness to misspecified constraints. We show that the technique that strictly enforces the given constraints, namely the chunklet model, produces poor results even under a small number of misspecified constraints. We further show that methods that penalize constraint violation are more robust to misspecified constraints but have undesirable local behaviors. Based on this evaluation, we propose a new learning technique, extending the chunklet model to allow soft constraints represented by an intuitive measure of confidence in the constraint.

REFERENCES

• 1: Adrian Barbu , Song-Chun Zhu, Graph Partition by Swendsen-Wang Cuts, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.320, October 13-16, 2003
• 2: Sugato Basu , Mikhail Bilenko , Raymond J. Mooney, A probabilistic framework for semi-supervised clustering, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014062]
• 3: Kamvar, S. D., Klein, D., & Manning, C. D. (2003). Spectral learning. IJCAI.
• 4: Brian Kulis , Sugato Basu , Inderjit Dhillon , Raymond Mooney, Semi-supervised graph clustering: a kernel approach, Proceedings of the 22nd international conference on Machine learning, p.457-464, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102409]
• 5: Tilman Lange , Martin H. C. Law , Anil K. Jain , Joachim M. Buhmann, Learning with Constrained and Unlabelled Data, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.731-738, June 20-26, 2005 [doi>10.1109/CVPR.2005.210]
• 6: Lu, Z., & Leen, T. K. (2004). Semi-supervised learning with penalized probabilistic clustering. NIPS.
• 7: Newman, D., Hettich, S., Blake, C., & Merz, C. (1998). UCI repository of machine learning databases.
• 8: Shental, N., Bar-Hillel, A., Hertz, T., & Weinshall, D. (2003). Computing gaussian mixture models with em using equivalence constraints. NIPS. MIT Press.
• 9: Strehl, A., Ghosh, J., & Mooney, R. J. (2000). Impact of similarity measures on web-page clustering. AAAI.
• 10: Swendsen, R. H., & Wang, J.-S. (1987). Nonuniversal critical dynamics in monte carlo simulations. Phys. Rev. Lett., 58, 86--88.
• 11: Kiri Wagstaff , Claire Cardie, Clustering with Instance-level Constraints, Proceedings of the Seventeenth International Conference on Machine Learning, p.1103-1110, June 29-July 02, 2000
• 12: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 13: Yu, S. X., & Shi, J. (2001). Grouping with bias. NIPS.