Locally linear metric adaptation for semi-supervised clustering

ABSTRACT

Many supervised and unsupervised learning algorithms are very sensitive to the choice of an appropriate distance metric. While classification tasks can make use of class label information for metric learning, such information is generally unavailable in conventional clustering tasks. Some recent research sought to address a variant of the conventional clustering problem called semi-supervised clustering, which performs clustering in the presence of some background knowledge or supervisory information expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semi-supervised clustering mostly perform global metric learning through a linear transformation. In this paper, we propose a new metric learning method which performs nonlinear transformation globally but linear transformation locally. In particular, we formulate the learning problem as an optimization problem and present two methods for solving it. Through some toy data sets, we show empirically that our locally linear metric adaptation (LLMA) method can handle some difficult cases that cannot be handled satisfactorily by previous methods. We also demonstrate the effectiveness of our method on some real data sets.

REFERENCES

• 1: Bar-Hillel, A., Hertz, T., Shental, N., & Weinshall, D. (2003). Learning distance functions using equivalence relations. Proceedings of the Twentieth International Conference on Machine Learning (pp. 11--18). Washington, DC, USA.
• 2: Sugato Basu , Arindam Banerjee , Raymond J. Mooney, Semi-supervised Clustering by Seeding, Proceedings of the Nineteenth International Conference on Machine Learning, p.27-34, July 08-12, 2002
• 3: Cheung, K., Yeung, D., & Chin, R. (2002). On deformable models for visual pattern recognition. Pattern Recognition, 35, 1507--1526.
• 4: Carlotta Domeniconi , Jing Peng , Dimitrios Gunopulos, Locally Adaptive Metric Nearest-Neighbor Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1281-1285, September 2002 [doi>10.1109/TPAMI.2002.1033219]
• 5: Friedman, J. (1994). Flexible metric nearest neighbor classification (Technical Report). Department of Statistics, Stanford University, Stanford, CA, USA.
• 6: Fukunaga, K., & Hostetler, L. (1973). Optimization of knearest neighbor density estimates. IEEE Transactions on Information Theory, 19, 320--326.
• 7: Trevor Hastie , Robert Tibshirani, Discriminant Adaptive Nearest Neighbor Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.6, p.607-616, June 1996 [doi>10.1109/34.506411]
• 8: Dan Klein , Sepandar D. Kamvar , Christopher D. Manning, From Instance-level Constraints to Space-Level Constraints: Making the Most of Prior Knowledge in Data Clustering, Proceedings of the Nineteenth International Conference on Machine Learning, p.307-314, July 08-12, 2002
• 9: Kwok, J., & Tsang, I. (2003). Learning with idealized kernels. Proceedings of the Twentieth International Conference on Machine Learning (pp. 400--407). Washington, DC, USA.
• 10: David G. Lowe, Similarity metric learning for a variable-kernel classifier, Neural Computation, v.7 n.1, p.72-85, Jan. 1995 [doi>10.1162/neco.1995.7.1.72]
• 11: Jing Peng , Douglas R. Heisterkamp , H. K. Dai, Adaptive Kernel Metric Nearest Neighbor Classification, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 3, p.30033, August 11-15, 2002
• 12: Poggio, T., & Girosi, F. (1990). Networks for approximation and learning. Proceedings of the IEEE, 78, 1481--1497.
• 13: Rand, W. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66, 846--850.
• 14: Roweis, S., & Saul, L. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.
• 15: Shental, N., Bar-Hillel, A., Hertz, T., & Weinshall, D. (2004). Computing Gaussian mixture models with EM using equivalence constraints. In Advances in neural information processing systems 16. Cambridge, MA, USA: MIT Press. To appear.
• 16: Janne Sinkkonen , Samuel Kaski, Clustering based on conditional distributions in an auxiliary space, Neural Computation, v.14 n.1, p.217-239, January 2002 [doi>10.1162/089976602753284509]
• 17: 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
• 18: 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
• 19: Webb, A. (1995). Multidimensional scaling by iterative majorization using radial basis functions. Pattern Recognition, 28, 753--759.
• 20: Xing, E., Ng, A., Jordan, M., & Russell, S. (2003). Distance metric learning, with application to clustering with side-information. In S. Becker, S. Thrun and K. Obermayer (Eds.), Advances in neural information processing systems 15, 505--512. Cambridge, MA, USA: MIT Press.
• 21: Zhang, Z., Kwok, J., & Yeung, D. (2003). Parametric distance metric learning with label information. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (pp. 1450--1452). Acapulco, Mexico.