PaperlayerView exact revision on arXiv

Source-linked AI summary

Evaluation Metrics for Unsupervised Learning Algorithms

Julio-Omar Palacio-Niño, Fernando Berzal

arXiv:1905.05667v2cs.LGstat.ML

TL;DR

Assessing clustering quality is difficult because no clustering function can satisfy three desirable axioms simultaneously. The report surveys evaluation criteria, metrics, and hyperparameter adjustment; it concludes that practical algorithms trade off the axioms and that evaluation can be biased when its metrics match the algorithm’s objective.

  • Problem

    Clustering quality is difficult to assess, and no clustering function can simultaneously satisfy scale invariance, richness, and consistency.

    Source: B. An Impossibility Theorem for… · p. 2, §VII · p. 9

  • Method

    The report surveys clustering evaluation criteria and metrics, discusses the impossibility theorem, and describes hyperparameter adjustment techniques.

    Source: §I · p. 1

  • Results

    Practical clustering algorithms can satisfy two of the three axioms by relaxing the third, while internal validation metrics can yield unfair results when they match the algorithm’s optimization metric.

    Source: B. An Impossibility Theorem for… · p. 2, §IV · p. 3

  • Takeaways & Limitations

    Evaluation techniques should be considered in relation to the clustering problem and the algorithm used, with care when internal metrics duplicate its optimization objective.

    Source: §I · p. 1, §IV · p. 3

    Internal validation can be counterproductive or unfair when it uses the same metrics that the clustering algorithm optimizes.

    Source: §IV · p. 3

Abstract

from arXiv · show

Determining the quality of the results obtained by clustering techniques is a key issue in unsupervised machine learning. Many authors have discussed the desirable features of good clustering algorithms. However, Jon Kleinberg established an impossibility theorem for clustering. As a consequence, a wealth of studies have proposed techniques to evaluate the quality of clustering results depending on the characteristics of the clustering problem and the algorithmic technique employed to cluster data.

I. INTRODUCTION

The report surveys clustering evaluation and frames its difficulty through the ambiguity of “cluster” and limits on desirable clustering properties. It presents scale invariance, richness, and consistency as criteria for good clustering.

I. INTRODUCTION

  • The report covers desirable clustering features, Kleinberg’s impossibility theorem, evaluation criteria, proposed metrics, and hyperparameter adjustment.Source: §I · p. 1

II. FORMAL LIMITATIONS OF CLUSTERING

  • Because “cluster” cannot be precisely defined, many clustering algorithms have been proposed.Source: §II · p. 1

A. Desirable Features of Clustering

1) Scale Invariance:

  • Scale invariance requires clustering results to remain unchanged when all distances are multiplied by a positive constant.Source: 1) Scale Invariance · p. 1

2) Richness:

  • Richness requires that every possible partition of the input points can be produced by the clustering process.Source: 2) Richness · p. 1

3) Consistency:

  • Consistency requires unchanged clustering when within-cluster distances decrease and/or between-cluster distances increase.Source: 3) Consistency · p. 1

B. An Impossibility Theorem for Clustering

Kleinberg’s theorem shows that no clustering function can satisfy scale invariance, richness, and consistency together, so practical algorithms trade off these properties. The report also outlines evaluation approaches for different clustering questions and settings.

B. An Impossibility Theorem for Clustering

III. METHODS FOR CLUSTER EVALUATION

  • Clustering evaluation is difficult, and the measurement often depends on the algorithm used to produce the clustering.Source: §III · p. 2
  • Evaluation considers clustering tendency, cluster count, quality without external information, comparison with external information, and comparison between clusterings.Source: §III · p. 2
  • The taxonomy includes internal and external validation, while the report maps initial evaluation questions to these approaches according to whether external information is used.Source: §III · p. 2, Figure 1 · p. 2

A. Null Hypothesis Testing

Null-hypothesis testing assesses whether data exhibit non-random structure, though the randomness model must be chosen. Internal validation evaluates cluster structure using input data without external information, but its metrics can bias assessment when they match the algorithm’s objective.

A. Null Hypothesis Testing

  • Null-hypothesis testing treats randomness as the null and interprets its rejection as evidence that the data are significantly unlikely to be random.Source: A. Null Hypothesis Testing · p. 3
  • The randomness hypothesis can use random-plot, random-label, or random-position assumptions, and Monte Carlo analysis or bootstrapping can assess clustering tendency.Source: A. Null Hypothesis Testing · p. 3

IV. INTERNAL VALIDATION

  • Internal validation evaluates clustering structure from the input data without external information, combining cohesion and separation measures.Source: §IV · p. 3, Figure 2 · p. 3
  • Internal metrics may be counterproductive or yield unfair validation when they match the metric optimized by the clustering algorithm.Source: §IV · p. 3
  • Partitional algorithms commonly use proximity, cohesion, separation, or silhouette metrics, whereas hierarchical algorithms commonly use the cophenetic coefficient.Source: §IV · p. 3, Figure 3 · p. 3

A. Partitional Methods

Partitional validation measures assess within-cluster cohesion, between-cluster separation, or both, using measures such as dispersion scores, combined indices, silhouette, and proximity-matrix comparisons.

A. Partitional Methods

  • Internal validation can sum cluster-level values for cohesion, separation, or both, often weighting clusters by size.Cohesion is intra-cluster and separation is inter-cluster; both can use proximity functions, including distances from examples to centroids or medoids.Source: A. Partitional Methods · pp. 3–4
  • SSE is equivalent to cohesion under squared Euclidean distance; low values indicate quality, but it favors SSE-optimizing algorithms and is suboptimal for density-based clusters.The cohesion calculation uses examples, a cluster representative, and the cluster’s number of examples.Source: A. Partitional Methods · p. 4
  • SSB values indicate good quality when high, but SSB favors algorithms that maximize separation between cluster centroids.SSB is based on maximizing distance between clusters.Source: A. Partitional Methods · p. 4
  • CH combines internal and between-cluster dispersion, Dunn uses a distance ratio, and Xie-Beni combines compaction and separation and can also be applied to hard clustering.The Xie-Beni score was designed for fuzzy clustering.Source: A. Partitional Methods · p. 4
  • Silhouette calculation uses each point’s average within-cluster distance a(i), its minimum average distance to another cluster b(i), and then averages point scores globally.Positive scores indicate separation, negative scores indicate overlapping clusters, and zero indicates uniform distribution throughout Euclidean space.Source: A. Partitional Methods · p. 5
  • Silhouette computation has complexity O(dn^2), making it impractical for huge datasets, and cohesion/separation metrics perform poorly for density-based clustering.Source: A. Partitional Methods · p. 5
  • Proximity-matrix validation compares the observed matrix with a cluster-reordered block-diagonal ideal, but constructing the matrix costs O(n^2), requiring sampling for large datasets.High correlation indicates that examples in the same cluster are close, though this may not suit density-based clusters.Source: A. Partitional Methods · p. 5

B. Hierarchical Methods

The report describes internal validation techniques proposed and tested for hierarchical clustering, with better results reported for algorithms such as SLINK.

B. Hierarchical Methods

  • Hierarchical validation techniques have been proposed and tested, and reportedly obtain better results with hierarchical algorithms such as SLINK.Source: B. Hierarchical Methods · p. 5

1) Cophenetic Correlation Coefficient (CPCC):

Cophenetic correlation evaluates hierarchical clustering by relating dendrogram merge proximities to the input proximity matrix.

1) Cophenetic Correlation Coefficient (CPCC):

2) Hubert Statistic:

The Hubert statistic evaluates hierarchical clustering using concordant and discordant example pairs.

2) Hubert Statistic:

  • The Hubert statistic defines concordant and discordant pairs of examples and uses their counts, S+ and S−, in its coefficient.Source: 2) Hubert Statistic · p. 6
  • The Hubert statistic ranges from −1 to 1 and has mainly been used to compare hierarchical clustering results.Source: 2) Hubert Statistic · p. 6
  • A higher Hubert γ value corresponds to a better clustering of data.Source: 2) Hubert Statistic · p. 6

V. EXTERNAL VALIDATION

External validation uses additional information, such as class labels, to compare algorithm-produced clusters with a reference partition. Its methods include pair-based comparisons represented through a contingency matrix.

  • External validation adds information such as class labels to assess clusters, and can also be applied when synthetic data are generated from a real data set.Source: §V · p. 6
  • The taxonomy classifies external metrics by clustering approach and uses them to compare algorithm-produced clusters C with an externally provided partition P.Source: §V · p. 6, Figure 4 · p. 6
  • A contingency matrix compares C and P through TP, FP, FN, and TN, counting pairs placed together or apart in each partition.Source: §V · pp. 6–7
  • The same-cluster pair counts are m1 = TP + FP for C and m2 = TP + FN for P.Source: §V · p. 7

A. Matching Sets

External validation measures compare detected clusters with a reference partition through matching-set measures or pair-to-pair correlation measures.

A. Matching Sets

  • Matching-set methods compare each detected cluster with its natural correspondence in the reference partition, using precision, recall, F-measure, or purity.F-measure combines precision and recall through a weighted harmonic mean; precision and recall are often combined with an unweighted harmonic mean when α = 1.Source: A. Matching Sets · p. 7

B. Peer-to-peer Correlation

  • Peer-to-peer correlation measures compare two partitions under equal conditions, with examples including Jaccard, Rand, Folkes and Mallows, and Hubert coefficients.The Rand coefficient is measured against the total data set and is equivalent to accuracy in supervised learning.Source: B. Peer-to-peer Correlation · pp. 7–8

C. Measures Based on Information Theory

Information-theory measures evaluate clustering through uncertainty and information shared with a reference partition. Hyperparameter tuning addresses parameter choices, including the number of clusters, that validation metrics alone cannot determine.

C. Measures Based on Information Theory

VI. HYPERPARAMETER TUNING

  • External validation can assess correspondence to underlying categories but cannot determine the right cluster count, such as the dendrogram cut level in hierarchical clustering.Source: §VI · p. 8
  • When the algorithm excludes the number of clusters, the suggested procedure selects parameter values from the middle of the range where the cluster count remains constant; when it includes that parameter, runs across cluster counts and initial conditions are scored with a chosen validation metric.Source: §VI · p. 8
  • A validation plot across cluster counts may reveal a “knee” or “elbow,” while automated tuning strategies can help with large parameter spaces that cannot be searched systematically.Source: §VI · p. 8
  • Grid search may require exponentially many configurations, random search samples configurations non-exhaustively, and smart search includes Bayesian or evolutionary optimization.Source: §VI · pp. 8–9

VII. CONCLUSION

The conclusion frames clustering quality as difficult to determine because desirable axioms cannot all be satisfied together. It distinguishes internal and external validation and points to hyperparameter tuning as a way to seek suitable algorithm settings.

  • Kleinberg’s theorem shows no clustering algorithm can simultaneously satisfy scale invariance, richness, and consistency, so practical algorithms must trade off desirable properties.Source: §VII · p. 9
  • Internal metrics use no external information and assess cohesion, separation, proximity structure, or a hierarchical dendrogram; external metrics use outside information and include matching, correlation, and information-theory indices.Source: §VII · p. 9
  • External validation can compare different clustering algorithms or different parameter settings of the same algorithm.Source: §VII · p. 9
  • Hyperparameter tuning seeks a suitable parameter configuration and can be used to determine the optimal number of clusters for a particular problem.Source: §VII · p. 9
Loading 1905.05667v2…