On Pairwise Clustering with Side Information
This work addresses clustering problems where similarity functions are not fully known, which is incremental for machine learning applications involving limited data or side-information.
The paper tackles pairwise clustering as a transductive prediction problem where the similarity function is hidden and only a random sample of pairwise similarities is available, possibly with side-information, and it provides tight bounds on misclassifications with two algorithms, SACA and RGCA, offering trade-offs in runtime and performance.
Pairwise clustering, in general, partitions a set of items via a known similarity function. In our treatment, clustering is modeled as a transductive prediction problem. Thus rather than beginning with a known similarity function, the function instead is hidden and the learner only receives a random sample consisting of a subset of the pairwise similarities. An additional set of pairwise side-information may be given to the learner, which then determines the inductive bias of our algorithms. We measure performance not based on the recovery of the hidden similarity function, but instead on how well we classify each item. We give tight bounds on the number of misclassifications. We provide two algorithms. The first algorithm SACA is a simple agglomerative clustering algorithm which runs in near linear time, and which serves as a baseline for our analyses. Whereas the second algorithm, RGCA, enables the incorporation of side-information which may lead to improved bounds at the cost of a longer running time.