Normalised clustering accuracy: An asymmetric external cluster validity measure

Overview

• There is no single best clustering algorithm that works for all tasks
• Clustering algorithms are traditionally evaluated using internal or external validity measures
• Internal measures quantify aspects of the obtained partitions, but their validity is questionable
• External measures compare algorithm outputs to ground truth groupings, but commonly used scores have issues

Plain English Explanation

Clustering is a way of grouping similar things together, like grouping customers by their shopping habits. But there's no one perfect way to do this clustering. Clustering algorithms are often evaluated using internal or external measures.

Internal measures look at things like how tight the clusters are or how separated the points are. But these measures don't always match up with what experts think are good clusters. External measures compare the clustering results to what experts say the groups should be. But the common scores used for this, like normalized mutual information, have some issues.

For example, they don't always identify the worst-case scenarios correctly, and they're not easy to interpret. This can make it hard to really understand how well a clustering algorithm is performing on different datasets. To fix this, the authors propose a new measure that is normalized, scales well, and accounts for imbalances in cluster sizes.

Technical Explanation

The paper argues that the commonly used partition similarity scores, such as normalized mutual information, Fowlkes-Mallows, and adjusted Rand index, have some shortcomings. In particular, they do not correctly identify the worst-case scenarios, and they are not easily interpretable.

To address these issues, the authors propose and analyze a new measure: a version of the optimal set-matching accuracy. This new measure is normalized, monotonic with respect to a similarity relation, scale-invariant, and corrected for imbalanced cluster sizes (though it is not symmetric nor adjusted for chance).

The paper provides a detailed mathematical formulation of this new validity measure and demonstrates its properties through theoretical analysis and empirical evaluation on benchmark datasets. The results show that this new measure can provide a more comprehensive and interpretable assessment of clustering algorithm performance compared to the classical partition similarity scores.

Critical Analysis

The paper identifies valid concerns with the existing clustering evaluation measures and proposes a novel approach to address these limitations. The new measure seems to have desirable theoretical properties, such as being normalized, monotonic, and accounting for imbalanced cluster sizes.

However, the paper does not provide a comprehensive comparison of this new measure against other recently proposed clustering evaluation metrics that may also aim to address some of the same issues. A more thorough comparative analysis would help strengthen the case for adopting this new measure.

Additionally, the paper focuses on the mathematical properties of the measure and does not delve deeply into the practical implications and interpretability for domain experts who use clustering algorithms. Further research into how this new measure resonates with and aids practitioners would be valuable.

Conclusion

This paper presents a new validity measure for evaluating clustering algorithms that aims to address some shortcomings of commonly used partition similarity scores. The proposed measure has desirable theoretical properties and could potentially provide a more comprehensive and interpretable assessment of clustering performance.

While the paper makes a compelling case for this new measure, further comparative analysis and exploration of its practical applications would help strengthen the contribution and facilitate wider adoption by the research community and practitioners working on clustering-related problems.