Weighted clustering: Towards solving the user's dilemma. (December 2021) - Ackerman, Margareta; Ben-David, Shai; Brânzei, Simina; Loker, David
Highlights: Properties that help solve the clustering users dilemma. Weighted properties formally differentiate clustering methods. A formal classification highlights advantages of center-based clustering techniques. Abstract: This paper makes a major step towards addressing a long-standing challenge in cluster analysis, known as the user's dilemma, which is the problem of selecting an appropriate clustering algorithm for a specific task. A formal approach for addressing this challenge relies on the identification of succinct, user-friendly properties that capture formal differences amongst clustering techniques. While helpful for gaining insight into the nature of clustering paradigms, there is a theory-practice gap that has so far limited the utility of this approach: Formal properties typically highlight advantages of classical linkage-based algorithms, while practical experience shows that center-based methods are preferable for many applications. We present simple new properties that delineate core differences between common clustering paradigms and overcome this theory-practice gap. The properties we present give a formal understanding of the advantages of center-based approaches for some applications and insight into when different clustering paradigms should be used. These properties address how sensitive algorithms are to changes in element frequencies, which we capture in a generalized setting where every element is associated with a real-valued weight. To complement extensive formal analysis, we discuss how these properties can be applied in practice.