[2A5-GS-2] Machine learning

[2A5-GS-2-02] Average Sensitivity of Hierarchical Clustering

〇Satoshi Hara¹, Koh Takeuchi², Yuichi Yoshida³ (1. Osaka University, 2. Kyoto University, 3. National Institute of Informatics)

Keywords:Clustering, Stability

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 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.