Unsupervised Learning of Distance Metrics Using Predictability

Abhishek Gupta
The Wharton School, University of Pennsylvania

Distance-based learning methods, like clustering and SVMs, are
dependent on good distance metrics.  We do unsupervised metric
learning in the context of clustering.  We seek transformations of
data which give clean and well separated clusters where clean clusters
are those for which membership can be accurately predicted.  The
transformation (hence distance metric) is obtained by minimizing the
blur ratio, which is defined as the ratio of the within cluster
variance divided by the total data variance in the transformed space.
For minimization we propose an iterative procedure, Clustering
Predictions of Cluster Membership (CPCM).  CPCM alternately (a)
predicts cluster memberships (e.g., using linear regression) and (b)
clusters these predictions (e.g., using k-means). With linear
regression and k-means, this algorithm is guaranteed to converge to a
fixed point.  The resulting clusters are invariant to linear
transformations of original features, and tend to eliminate noise
features by driving their weights to zero.  Some statistical
properties of blur-ratio will also be discussed.