Title: Weighted Clustering

Abstract:
Clustering is a central unsupervised learning task with a wide variety
of applications. However, in spite of its popularity, it lacks a
unified theoretical foundation. Recently, there has been work aimed at
developing such a theory. We discuss recent advances in clustering
theory, with an emphasis on a recent framework for clustering
algorithm selection.

Faced with a concrete clustering task, a user needs to choose an
appropriate clustering algorithm.
Clustering algorithms vary widely in their input-output behaviour;
consequently, understanding these differences is essential for making
this choice. Studying clustering in a weighted setting leads to an
elegant classification that highlights fundamental differences between
popular clustering techniques.

Weighted clustering is a natural generalization of the common
clustering framework, where every element is associated with a
real-valued weight. We introduce three fundamental categories that
describe how an algorithm can respond to weights, and study well-known
clustering methods with respect to these categories. Among the
algorithms studied, we observe a positive correlation between an
algorithm's popularity and its weight-sensitivity.

Joint work with Shai Ben-David, Simina Branzei, and David Loker.