On the Discrepancy between Kleinberg’s Clustering Axioms and k-Means Clustering Algorithm Behavior

Machine Learning - Tập 112 - Trang 2501-2553 - 2023
Mieczysław Alojzy Kłopotek1, Robert Albert Kłopotek2
1Institute of Computer Science, Polish Academy of Sciences, Warszawa, Poland
2Faculty of Mathematics and Natural Sciences, Stefan Cardinal Wyszyński University in Warsaw, Warszawa, Poland

Tóm tắt

This paper performs an investigation of Kleinberg’s axioms (from both an intuitive and formal standpoint) as they relate to the well-known k-mean clustering method. The axioms, as well as a novel variations thereof, are analyzed in Euclidean space. A few natural properties are proposed, resulting in k-means satisfying the intuition behind Kleinberg’s axioms (or, rather, a small, and natural variation on that intuition). In particular, two variations of Kleinberg’s consistency property are proposed, called centric consistency and motion consistency. It is shown that these variations of consistency are satisfied by k-means.

Tài liệu tham khảo