Average Sensitivity of Hierarchical Clustering

TL;DR — We design hierarchical clustering algorithms that are stable against perturbations in the training data.

Abstract

Hierarchical clustering is one of the most popular methods used to extract cluster structures in a dataset. However, if the hierarchical clustering algorithm is sensitive to a small perturbation to the dataset, then the credibility and replicability of the output hierarchical clustering are compromised. To address this issue, we consider the average sensitivity of hierarchical clustering algorithms, which measures the change in the output hierarchical clustering upon deletion of a random data point from the dataset. Then, we propose a divisive hierarchical clustering algorithm with which we can tune the average sensitivity. Experimental results on benchmark and real-world datasets confirm that the proposed method is stable against the deletion of a few data points, while existing algorithms are not.