Selecting Clustering Algorithms Based on Their Weight Sensitivity

Editor: One of the most prominent challenges in clustering is “the user’s dilemma, ” which is the problem of selecting an appropriate clustering algorithm for a specific task. A formal approach for addressing this problem relies on the identification of succinct, user-friendly properties that formally capture when certain clustering methods are preferred over others. So far, these properties focused on advantages of classical Linkage-Based algorithms, failing to identify when other clustering paradigms, such as popular center-based methods, are preferable. We present surprisingly simple new properties that delineate the differences between common clustering paradigms, which clearly and formally demonstrates advan-tages of center-based approaches for some applications. These properties address how sen-sitive algorithms are to changes in element frequencies, which we capture in a generalized setting where every element is associated with a real-valued weight. 1