PaperlayerView exact revision on arXiv

Source-linked AI summary

Adjusting for Chance Clustering Comparison Measures

Simone Romano, Nguyen Xuan Vinh, James Bailey, Karin Verspoor

arXiv:1512.01286v1stat.ML

TL;DR

The paper asks when ARI and AMI are most appropriate and seeks to bridge their pair-counting and information-theoretic foundations. It analytically computes statistics for generalized Tsallis-entropy measures and uses them to derive adjusted measures and application guidelines. The resulting guidance favors ARI for large equal-sized reference clusters and AMI for unbalanced references containing small clusters.

  • Problem

    ARI and AMI are popular adjusted clustering measures, but their best application scenarios lack clear guidelines.

  • Method

    The paper analytically computes expected values and variances for generalized measures under random fixed-marginal partitions, then constructs baseline- and selection-bias adjustments.

  • Results

    The generalized framework links ARI and AMI as special cases and yields adjusted measures that correct chance baselines and reduce selection bias.

  • Takeaways & Limitations

    Use ARI when the reference clustering has large equal-sized clusters, and AMI when it is unbalanced and contains small clusters.

  • Takeaways & Limitations

    The analytical standardization formula has complexity quadratic in c and linear in r under the paper's chosen conditioning.

Abstract

from arXiv · show

Adjusted for chance measures are widely used to compare partitions/clusterings of the same data set. In particular, the Adjusted Rand Index (ARI) based on pair-counting, and the Adjusted Mutual Information (AMI) based on Shannon information theory are very popular in the clustering community. Nonetheless it is an open problem as to what are the best application scenarios for each measure and guidelines in the literature for their usage are sparse, with the result that users often resort to using both. Generalized Information Theoretic (IT) measures based on the Tsallis entropy have been shown to link pair-counting and Shannon IT measures. In this paper, we aim to bridge the gap between adjustment of measures based on pair-counting and measures based on information theory. We solve the key technical challenge of analytically computing the expected value and variance of generalized IT measures. This allows us to propose adjustments of generalized IT measures, which reduce to well known adjusted clustering comparison measures as special cases. Using the theory of generalized IT measures, we are able to propose the following guidelines for using ARI and AMI as external validation indices: ARI should be used when the reference clustering has large equal sized clusters; AMI should be used when the reference clustering is unbalanced and there exist small clusters.

1. Introduction

The paper addresses sparse guidance on when to use ARI or AMI by connecting pair-counting and information-theoretic clustering measures. It develops generalized adjusted measures and analytical tools to support application-specific recommendations.

  • Motivation: ARI and AMI are widely used for external validation, but their best application scenarios remain an open problem with few established guidelines.Both measures have interpretable adjusted baselines: 0 for random independent partitions and 1 for identical partitions.
  • Motivation: Selection bias can favor partitions with many clusters, while statistical standardization has mainly been applied to information-theoretic measures.The bias depends on the similarity measure, the number of clusters, and their relative sizes.
  • Approach: The paper connects adjusted pair-counting and information-theoretic measures through generalized Tsallis q-entropy measures.This framework also extends statistical adjustment by standardization to a broader class, including pair-counting measures.
  • Approach: The authors develop analytical methods for the expected value and variance of generalized information-theoretic measures under random clusterings.The technique applies to a broader family Lφ, while family Nφ measures receive large-N expected-value approximations.
  • Contributions: The paper proposes generalized adjusted measures that correct both chance baselines and selection bias while including established measures as special cases.The contribution is explicitly framed as a generalization of prior analytical adjustments for pair-counting and Shannon mutual-information measures.

2. Comparing Partitions

The paper compares pair-counting and information-theoretic approaches for partitions, then introduces generalized Tsallis-entropy measures linking the two. Normalization alone does not ensure a zero chance baseline, motivating analytical adjustment.

  • Partition representation: Partitions U and V divide the same N objects into r and c disjoint clusters, respectively.Their cluster sizes form the marginal quantities used in contingency-table-based comparisons.
  • Pair-counting measures: Pair-counting measures classify object pairs as agreeing or disagreeing within the two partitions and use counts k11, k00, k10, and k01.These counts support similarity measures such as the Rand Index and distance measures such as the Mirkin index.
  • Information-theoretic measures: Information-theoretic measures compare empirical distributions associated with U, V, and their joint partition using entropy and mutual information.Mutual information can be expressed through marginal, joint, and conditional Shannon entropies.
  • Generalized measures: Generalized Tsallis q-entropy measures extend Shannon information and recover pair-counting relationships for particular q values.When q = 2, generalized variation of information, the Mirkin index, and the Rand Index are linearly related.
  • Normalization and chance adjustment: Normalized generalized mutual information reaches 1 for identical partitions but does not have a constant zero baseline for random independent partitions.In simulations with N = 100 and V containing six sets, NMIq showed differing average values as U varied from 2 to 10 sets.
  • Normalization and chance adjustment: Analytical expected values under independent fixed-marginal partitions can be subtracted to adjust generalized measures for chance.This strategy extends adjusted pair-counting and Shannon information measures through the permutation or hypergeometric model.

3. Baseline Adjustment

The paper derives chance-adjusted generalized information-theoretic measures under the permutation model, analytically extending adjustments for pair-counting and Shannon measures. These adjustments recover ARI and AMI as special cases and produce a near-zero baseline for independent random partitions.

  • Chance model: The permutation model fixes the number of objects and both partitions’ marginals while treating the partitions as independently generated.This is the null model used to compute expected similarity or distance values for baseline adjustment.
  • Generalized measure families: Lφ contains similarity measures expressible as linear combinations of bounded functions of contingency-table cell counts, including the narrower pair-counting family L.The framework is broad enough to include generalized information-theoretic measures and previously studied pair-counting adjustments.
  • Analytical adjustment: The expected value of any Lφ measure can be computed exactly under random partitions, extending earlier results for pair-counting measures and enabling adjustments for generalized IT measures.The result is based on the hypergeometric distribution of contingency-table cells under the permutation model.
  • Adjusted measures: AMIq and AVIq use expected values under the null model to normalize generalized mutual information and variation of information against their attainable ranges.AVIq converts a distance into a similarity measure, while NVIq preserves distance properties and satisfies AVIq = 1 − NVIq.
  • Special cases: AMI2 equals ARI, while the limit of AMIq as q →1 equals Shannon AMI; thus the generalized family links pair-counting and information-theoretic measures.ARI is also connected to other partition-comparison measures and Cohen’s κ statistics.
  • Computational complexity: O(N · max {r, c}) is the computational complexity of AMIq, avoiding the O(N!) cost of enumerating all contingency tables under permutations.The reduction follows from computing expected values using properties of the contingency-table cells rather than generating every table.
  • Baseline experiments: Adjusted generalized IT measures remain close to 0 with negligible variation for independent random partitions, including when the number or relative size of clusters varies.AMIq achieves the desired constant random-partition baseline, unlike NMIq when cluster sizes vary.
  • Large-sample approximation: For large N, expected values for the broader Nφ family can be approximated from contingency-table marginals, and the approximation improves when N is large relative to the table size.The generalized framework includes measures such as the Jaccard coefficient that are outside Lφ.

4. Application scenarios for AMIq

The paper uses generalized Tsallis q-entropy measures to identify when different q values, including AMI and ARI, are better suited for validating clustering solutions. Small q favors pure and unbalanced solutions, whereas big q favors balanced solutions and is recommended for large equal-sized reference clusters.

  • The paper asks which q in AMIq best validates a clustering solution against a reference ground truth clustering.This choice also identifies application scenarios for AMI and ARI.
  • The expected generalized entropy of jointly random partitions is well approximated by its limit when N is large relative to the contingency-table cells.For Figure 5, the approximation is already good at N = 1000 in the reported setting.
  • Use AMIq with small q: Small q makes q-entropy vary over a larger range and biases AMIq toward pure, unbalanced clustering solutions.The paper characterizes AMI0.5 and AMI1 = AMI as examples of this regime.
  • Use AMIq with big q: Big q is less biased toward pure clusters and prefers balanced clustering solutions.The paper identifies AMI2.5 and AMI2 = ARI as examples of this regime.
  • Use AMIq with small q: For an unbalanced reference with small clusters, the paper advises AMI0.5 or AMI1 = AMI because small-cluster identification must be precise.In the example, the reference cluster sizes are [10, 10, 10, 70], and the solution with many pure clusters is preferred.
  • Use AMIq with big q: For a reference with big equal-sized clusters, the paper advises AMI2.5 or AMI2 = ARI because precise solution clusters are less crucial.The example uses four reference clusters of size 25 and favors the solution whose clusters identify more elements from particular reference clusters.

5. Standardization of Clustering Comparison Measures

The paper standardizes generalized information-theoretic measures by analytically deriving their expected values and variances under random partitions. The resulting measures connect adjusted and standardized clustering comparisons, reduce selection bias, and support independence testing.

  • Analytical standardization: Analytical standardization computes expected values and variances for measures in Lφ, including generalized information-theoretic measures.The approach extends earlier analytical adjustments for pair-counting and Shannon mutual-information measures.
  • Analytical standardization: SMIq and SVIq standardize generalized mutual information and variation of information using their deviation from the random-partition mean relative to standard deviation.The standardized measures quantify how many standard deviations the observed measure lies from its expected value.
  • Special cases: SMI2 equals SVI2 and SRI, while the q → 1 limits recover Shannon-based standardized mutual information and variation of information.These special cases connect the generalized framework to established standardized measures.
  • Computational complexity: SMIq has computational complexity O(N3c · max {c, r}), quadratic in c and linear in r under the paper’s conditioning choice.A symmetric alternative has complexity O(N3r · max {r, c}).
  • Statistical inference: SMIq provides a non-parametric independence test for MIq, with an upper-bound p-value of 1/(1+(SMIq(U,V))^2).For SMIq = 4.46, the associated p-value is smaller than 0.05.
  • Selection-bias experiments: Across random-partition experiments, SMIq produced close-to-uniform selection probabilities for q = 1.001, 2, and 3, unlike NMIq’s bias toward ten-set partitions.AMIq reduced bias particularly at q = 2, where AMI2 = ARI has nearly constant variance.
  • Selection-bias experiments: As N grows, generalized measures’ variances tend to zero; with large N relative to contingency-table cells, AMIq may suffice and be more efficient than SMIq.SMIq is most useful for selection-bias correction when N is small and for independence testing.

6. Conclusion

The paper derives generalized adjusted and standardized clustering measures and uses them to recommend scenarios for ARI, AMI, and SMIq. These recommendations depend on reference-cluster balance, cluster size, and the number of objects.

  • Guidelines: ARI is recommended when the reference clustering has large, equal-sized clusters.AMI is recommended when the reference clustering is unbalanced and contains small clusters.
  • Guidelines: AMI is recommended when the reference clustering is unbalanced and contains small clusters.The guideline is presented as an application scenario for external validation.
  • Guidelines: Standardized SMIq can correct selection bias among candidate clusterings when the number of objects is small.It can also be used to test independence between two partitions.

Appendix A. Theorem Proofs

For q = 2, generalized variation of information, the Mirkin index, and the Rand index are linearly related.

  • Theorem proofs: For q = 2, VI2(U, V) is linearly related to the Mirkin index and the Rand index.The appendix states the relationship as VI2(U,V) = 1/N2 MK(U,V) = N−1/N (1 − RI(U,V)).

Proof

The proof derives expected values and variances for generalized information-theoretic measures under a fixed-marginal hypergeometric permutation model. These results support standardized measures whose limiting and special-case forms recover established clustering comparison indices.

  • Computational complexity: The computational complexities are O(N · max {r, c}) for AMIq and O(N3c · max {c, r}) for SVIq.The first result uses iterative hypergeometric probability computation, whereas the standardized variation-of-information calculation requires higher-order summations.
  • Expected values: Theorem 3 establishes the expected-value behavior of generalized measures under the hypergeometric model of random partitions.The expectation is computed by summing cellwise terms over contingency tables generated by permutations, with each cell count modeled hypergeometrically.
  • Variances: Theorem 4 derives variance expressions for generalized measures using hypergeometric cell-count distributions and fixed partition marginals.The variance proof handles dependencies between contingency-table cells through conditional hypergeometric distributions and covariance bounds.
  • Special cases: The standardized generalized measures connect continuously to Shannon-based measures at q→1 and to pair-counting measures at q=2.Specifically, AMIq and AVIq converge to AMI and AVI as q→1, while AMI2 = AVI2 = ARI; the standardized counterparts satisfy analogous identities.
  • Asymptotic behavior: lim N→+∞ Var(Hq(U, V )) = lim N→+∞ Var(MIq(U, V )) = lim N→+∞ Var(VIq(U, V )) = 0.The result follows from the vanishing variance of normalized hypergeometric cell counts as the number of records grows.
Loading 1512.01286v1…