Weighted clustering: Towards solving the user's dilemma

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. (c) 2021 Elsevier Ltd. All rights reserved.

Automated summary

This paper addresses the long-standing challenge in cluster analysis of selecting an appropriate clustering algorithm for a specific task by introducing new properties to delineate core differences between common clustering paradigms. The properties provide formal understanding of advantages of center-based approaches for some applications and insight into when different clustering paradigms should be used. By considering how algorithms are sensitive to changes in element frequencies, the properties bridge the gap between theory and practice in cluster analysis.