Probability-One Homotopy Maps for Tracking Constrained Clustering Solutions
David R. Easterling, Mahmud Shahriar Hossain, Layne T. Watson, Naren Ramakrishnan · 2013
semisupervised learning Abstract. Modern machine learning problems typically have multiple criteria, but there is currently no systematic mathematical theory to guide the design of formulations and exploration of alternatives. Homotopy methods are a promising approach to characterize solution spaces by smoothly tracking solutions from one formulation (typically an “easy” problem) to another (typically a “hard ” problem). New results in constructing homotopy maps for constrained clustering problems are here presented, which combine quadratic loss functions with discrete evaluations of constraint violations are presented. These maps balance requirements of locality in clusters as well as those of discrete must-link and must-notlink constraints. Experimental results demonstrate advantages in tracking solutions compared to stateof-the-art constrained clustering algorithms.