Boosting Margin Based Distance Functions for Clustering
Tomer Hertz - Hebrew University, Jerusalem Israel Aharon Bar-Hillel - Hebrew University, Jerusalem Israel Daphna Weinshall - Hebrew University, Jerusalem Israel
The performance of graph based clustering methods critically depends on the quality of the distance function used to compute similarities between pairs of neighboring nodes. In this paper we learndistance functions by training binary classifiers with margins. Theclassifiers are defined over the product space of pairs of points and aretrained to distinguish whether two points come from the same class or not. The signed margin is used as the distance value. Our main contribution is a distance learning method DistBoost, which combines boosting hypotheses over the product space with a weak learner based on partitioning the original feature space. Each weak hypothesis is a Gaussian mixture model computed using a semi-supervised constrained EM algorithm, which is trained using both unlabeled and labeled data. We also consider SVM and decision trees boosting as margin based classifiers in the product space. We experimentally compare the margin based distance functions with other existing metric learning methods, and with existing techniques for the directincorporation of constraints into various clustering algorithms. Clustering performance is measured on some benchmark databases from the UCI repository, a sample from the MNIST database, and a data set of color images of animals. In most cases the DistBoostalgorithm significantly and robustly outperformed its competitors.