CLUSTERING WITHOUT A METRIC

We describe a methodology for clustering data in which a distance metric or similarity function is not used. Instead, clusterings are optimized based on their intended function: the accurate prediction of properties of the data. The resulting clustering methodology is applicable, without further ad hoc assumptions or transformations of the data 1) when features are heterogeneous (both discrete and continuous) and not combinable, 2) where some data points have missing feature values, and 3) where some features are irrelevant, i.e., have large variance but little correlation with other features. Further, it provides an integral measure of the quality of the resulting clustering. We have implemented a clustering program, RIFFLE, in line with this approach, and experiments with synthetic and real data show that the clustering is, in many respects, superior to traditional methods.