Characterization of Linkage-Based Clustering

Speaker: Rita Ackerman, University of Waterloo

Clustering is a central unsupervised learning task with a wide varietyof applications. Not surprisingly,there exist many clustering algorithms. However, unlike classificationtasks, in clustering,different algorithms may yield dramatically different outputs for thesame input sets. A major challengeis to develop tools that may help select the more suitable algorithmfor a given clustering task.We propose to address this problem by distilling abstract propertiesof clustering functions that distinguish between the types ofinput-output behaviors of different clustering paradigms. In this talkwe make a step in this direction by providing such property basedcharacterization forthe class of linkage based clustering algorithms.

Linkage-based clustering is one the most commonly used and widelystudied clustering paradigms.It includes popular algorithms like Single Linkage and enjoys simpleefficient algorithms.On top of their potential merits for helping users decide when aresuch algorithms appropriatefor their data, our results can be viewed as a convincing proof ofconcept for the research ontaxonomizing clustering paradigms by their abstract properties.