Pith. sign in

REVIEW 6 minor 48 references

External clustering validation is better framed as a homogeneity–parsimony trade-off than as a scalar score.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 09:20 UTC pith:FOFLE5GB

load-bearing objection A clean two-objective clustering-validation framework with a genuinely useful parsimony score, but the title overreaches once ground-truth classes have meaningful substructure.

arxiv 2607.20799 v1 pith:FOFLE5GB submitted 2026-07-22 cs.LG cs.ITmath.ITstat.ME

External Clustering Validation by the Homogeneity-Parsimony Trade-off

Andreas Tiffeau-Mayer This is my paper
classification cs.LG cs.ITmath.ITstat.ME
keywords external clustering validationhomogeneityparsimonyinformation bottleneckPareto optimalityconditional entropygeneralized entropiesROC curve
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

External clustering validation usually condenses how well a clustering matches known classes into a single scalar, hiding the tension between not mixing classes and not splitting them. This paper argues that the right evaluation is a two-objective trade-off, and defines normalized homogeneity and parsimony scores that each range from 0 to 1. The central mathematical result is a proof that splitting clusters always raises homogeneity and always lowers parsimony, so the trade-off curve is monotone and can identify Pareto-optimal clusterings. The same construction, using generalized entropies, recovers normalized purity and inverse purity for set matching and specificity and sensitivity for pair counting, so the homogeneity–parsimony curve is a direct analogue of the ROC curve. A reader cares because this replaces single-number comparisons with a curve that separates 'does the clustering recover classes' from 'does it fragment them unnecessarily'.

Core claim

The paper claims that external clustering validation is fundamentally a two-objective Pareto problem, and it supplies the normalized scores h = 1 − H(C|K)/H(C) and p = 1 − H(K|C)/(log N − H(C)) that make this trade-off explicit. Theorem 1 states that if one clustering is a refinement of another, homogeneity never decreases and parsimony never increases; the proof rewrites h as normalized mutual information I(C,K)/H(C) and p as (log N − H(C,K))/(log N − H(C)), so the data-processing inequality and monotonicity of joint entropy give the result. Replacing Shannon entropy with a conditional min-entropy turns the scores into chance-corrected purity and inverse purity, and replacing it with Tsalli

What carries the argument

The load-bearing objects are the two conditional entropies H(C|K) and H(K|C), normalized by their maximal values over all clusterings of the same objects. Homogeneity h = 1 − H(C|K)/H(C) measures how well clusters predict class labels; parsimony p = 1 − H(K|C)/(log N − H(C)) measures how little each class is fragmented into multiple clusters. The monotonicity theorem follows from two rewritings: h = I(C,K)/H(C), which makes refinement raise h via the data-processing inequality, and p = (log N − H(C,K))/(log N − H(C)), which makes refinement lower p because joint entropy cannot decrease when a partition is refined. The same normalized-complement template, applied to min-entropy and Tsallis co

Load-bearing premise

The framework assumes classes capture all meaningful structure, so any further subdivision represents unnecessary complexity; if the ground-truth labels contain meaningful substructure, parsimony will penalize clusterings that a practitioner would consider useful.

What would settle it

Take a dataset with known two-level labels, compute h and p for a clustering that splits each class into its subtypes and for one that keeps each class intact, then ask domain experts which clustering is more useful; if the subtype-splitting clustering is preferred despite its lower parsimony, the load-bearing assumption fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Pareto-optimal clusterings can be read directly from the trade-off curve; any clustering strictly below the frontier is dominated by another with both higher homogeneity and higher parsimony.
  • In the pair-counting formulation, the homogeneity–parsimony curve is exactly an ROC curve, so the area under it is a scalar summary with the same interpretation as AUC; uninformative features trace the diagonal.
  • For feature selection, the correct comparison is homogeneity at equal parsimony rather than at equal threshold, which can reverse naive conclusions about which features help.
  • The Q-measure, a weighted harmonic mean of h and p, provides a scalarization that assigns zero to fully fragmented clusterings, unlike the V-measure.
  • Adjusted mutual information can stay near its optimum across a wide range of k-means clusterings, while the trade-off curve reveals that homogeneity is rising and parsimony falling over the same range.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the monotone trade-off is taken as the right evaluation geometry, many existing scalar metrics could be re-plotted as points or curves in the (p, h) plane, making their implicit weighting between fragmentation and mixing explicit.
  • The exact identity between pair-based parsimony and TPR suggests that a clustering's ROC curve could inherit confidence intervals and significance tests from binary classification methodology, which the paper does not develop.
  • Because the parsimony normalization depends on N, comparing trade-off curves across datasets of different sizes requires care; a size-invariant version of parsimony would be a natural follow-up.
  • The assumption that all fragmentation beyond the reference classes is waste means the framework will systematically penalize useful substructure discovery (e.g., disease subtypes within a cohort); applying it in such settings requires a hierarchical or multi-resolution extension.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper proposes a two-objective external clustering validation framework based on homogeneity h(C,K) and parsimony p(C,K), defined as normalized complements of conditional entropies. Theorem 1 states that under cluster refinement h is nondecreasing and p is nonincreasing. The authors extend the pair of scores to set-matching (normalized purity and inverse purity) and pair-counting (specificity and sensitivity, i.e., TNR and TPR) via min-entropy and Tsallis collision entropy, and illustrate the trade-off curves on feature selection and MNIST. A scalar Q-measure is introduced in the appendix.

Significance. The central derivations are sound and elegant. Theorem 1 follows cleanly from the data-processing inequality and joint-entropy monotonicity; the pair-counting equalities in Section V C and Appendix C are exact given the Furuichi conditional Tsallis estimator; and the set-matching normalization bounds in Appendix B are correct. The unification of purity/inverse-purity and TNR/TPR under one information-theoretic umbrella is a useful conceptual contribution, and the open-source Python package strengthens reproducibility. The main limitation—that parsimony penalizes useful subdivision when reference classes are not at the finest meaningful resolution—is explicitly acknowledged in Sections II and VII and does not undermine the mathematical claims.

minor comments (6)
  1. [Abstract and Section II] The scope assumption that 'classes are considered to capture all meaningful structure' is load-bearing for the interpretation of p as 'unnecessary fragmentation'. It is stated in Section II and repeated in Section VII, but the abstract and title present the framework as a general external-validation tool. Please move the assumption (or a paraphrase) into the abstract and Introduction so that users with hierarchical or subtype labels are not misled. No technical change is needed.
  2. [Appendix B] In the proof of the inverse-purity bound, the claim that inverse purity is monotonic under refinement is used without proof. A one-line argument suffices: for a refinement K' of K, every new cluster k' is contained in some parent cluster k, so P(k'|c) <= P(k|c), hence max_{k'} P(k'|c) <= max_k P(k|c), and the fully fragmented clustering attains the minimum.
  3. [Figure 4] Figure 4A caption says 'Two labeled classes' while the text (Section VI A) says three classes with means at (-3.5,0),(0,0),(3.5,0). Please correct the caption.
  4. [Section VI A / Figure 4F] For the uninformative feature, the pair-based curve is the anti-diagonal TPR = 1 - TNR when plotted with specificity on the x-axis, not the usual ROC diagonal. The text 'follows the diagonal' should be clarified to avoid confusion with the standard ROC baseline.
  5. [Section VII] The statement 'the full range from 0 to 1 is attainable for clusterings of a given class distribution' is stronger than demonstrated. The extremes are attainable, but arbitrary intermediate values are not shown and in finite samples may be impossible. Please weaken the claim or provide a construction.
  6. [Section III B] Equation (16) would be clearer if the normalization log N - H(C) were explicitly identified as the maximum of H(K|C) over hard clusterings, attained by the singleton clustering; the text states this, but repeating it near the equation would improve readability.

Circularity Check

1 steps flagged

The h/p monotonicity theorem is self-contained, but the claimed unification of set-matching and ROC metrics is built in by choosing generalized-entropy definitions that recover those metrics.

specific steps
  1. self definitional [Section V.A, paragraphs 2 and 3; Section V.B, Eqs. (26)-(28)]
    "Rather than employing a universal definition, we adopt in each case the formulation that most directly recovers the evaluation criteria commonly used in the respective frameworks. ... This particular conditional entropy definition is chosen because it links the negative exponential of the conditional entropies (Eqs. 5 and 6) to the so-called purity score and its counterpart, inverse purity."

    The generalized conditional entropies are not independently motivated; they are selected specifically so that simple transformations reproduce purity/inverse-purity and, after normalization, TNR/TPR. Thus the paper's claim to 'derive' set-matching and pair-based counterparts is a restatement of the input criteria in entropy notation, not an independent derivation. Equation (27), e^{-H_infty(C|K)} = purity, is an identity by construction: the entropy definition was chosen to make it true. The same applies to the pair-counting normalization, where the adopted Tsallis/estimator formulation is chosen to recover FP/FN and hence TNR/TPR. The unification is therefore reverse-engineered rather than derived from a common first principle.

full rationale

The main contribution, Theorem 1 (monotonicity of h and p under refinement), is mathematically self-contained: h is rewritten as I(C,K)/H(C) and uses the data-processing inequality, while p is rewritten as a normalized negative joint entropy and uses monotonicity of joint entropy under refinement. No fitted parameters, no prior results, and no self-citations are load-bearing there. The self-citations in the paper [27,43,44] are peripheral (an entropy estimator and ongoing applications). The core h/p definitions also do not reduce to the IB framework except as motivation. The circular component is localized to Section V: the paper explicitly says it adopts the entropy formulation that 'most directly recovers the evaluation criteria commonly used', and then presents purity/inverse-purity and TNR/TPR as derived counterparts. That is a construction-by-definition rather than an independent derivation, so the claimed 'unification' is partly circular. However, this does not undermine the independent monotonicity result or the illustrative applications, so a score of 4 is appropriate rather than a higher score. The Discussion's acknowledgment of the substructure assumption is a scope limitation, not a circularity.

Axiom & Free-Parameter Ledger

1 free parameters · 6 axioms · 0 invented entities

The main scores h and p are parameter-free functions of the contingency table and the class distribution; the only free parameter is the user-chosen β in the appendix scalarization. The two generalized-entropy bridges are ad hoc constructions chosen to reproduce known set-matching and pair-counting metrics, plus standard information-theoretic inequalities. No new physical or mathematical entities are introduced.

free parameters (1)
  • β (Q-measure weight)
    User-chosen weight in the Q-measure scalarization (Appendix D); not fitted to data and not needed for the main scores.
axioms (6)
  • standard math Data-processing inequality
    Used in the proof of h monotonicity (Section IV A, Eq. 18) to conclude I(C,K') ≥ I(C,K) when K = f(K').
  • standard math Joint entropy H(C,K) is non-decreasing under refinement
    Used to prove p monotonicity (Section IV A, Eq. 19) via H(C,K') ≥ H(C,K).
  • domain assumption Classes capture all meaningful structure
    Stated in Section II; without it, fragmentation can be informative and the parsimony criterion penalizes valid substructure.
  • ad hoc to paper Arithmetic-averaged conditional min-entropy is the relevant generalization
    Selected in Section V B specifically so that e^{-H∞} equals purity/inverse purity; not derived from an operational principle.
  • ad hoc to paper Furuichi conditional Tsallis entropy (chain-rule preserving) is the relevant generalization
    Selected in Section V C / Appendix C so that collision entropy recovers pair counts and TNR/TPR.
  • standard math Unbiased Simpson estimator for collision entropy
    Used in Eq. 34 to connect finite-sample pair counts to conditional Tsallis entropies.

pith-pipeline@v1.3.0-alltime-deepseek · 13980 in / 14326 out tokens · 140609 ms · 2026-08-01T09:20:05.499775+00:00 · methodology

0 comments
read the original abstract

Scalar metrics are often used to evaluate clusterings against known classes, but they can obscure a fundamental trade-off: clusterings should be informative about class labels while avoiding unnecessary fragmentation. Here we describe normalized scores of cluster homogeneity and parsimony that quantify this trade-off. These scores build on the information bottleneck principle, modified to not reward lossy compression. We show by example and mathematical proof that our definitions of these scores have the intuitive property of varying monotonically under cluster refinement in contrast to related proposals. Extending the information-theoretic framework beyond Shannon entropies, we furthermore derive set-matching and pair-based counterparts of the homogeneity and parsimony scores. These unify commonly used evaluation criteria and show that, in the pair-based setting, the homogeneity-parsimony trade-off recovers the receiver operating characteristic of binary classifiers. We demonstrate the framework's utility for feature selection and algorithm comparison, illustrating how considering scores jointly can clarify clustering operating points and identify Pareto-optimal solutions.

Figures

Figures reproduced from arXiv: 2607.20799 by Andreas Tiffeau-Mayer.

Figure 1
Figure 1. Figure 1: shows an example. Clusterings Kc and Kd are refinements of clustering Kb and have higher ho￾mogeneity and equal or lower parsimony, respectively. In contrast, the completeness score of the maximally fragmented clustering Kd is non-zero, and the complete￾ness of clusterings Kc and Kd exceeds the value assigned to the substantially simpler clustering Kb. The assign￾ment of a non-zero completeness score to ma… view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Illustration of three external clustering-evaluation frameworks and their corresponding normalized trade-off scores. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 2 linked inside Pith

  1. [1]

    W. M. Rand, Journal of the American Statistical Asso- ciation66, 846 (1971)

    1971

  2. [2]

    Strehl and J

    A. Strehl and J. Ghosh, Journal of Machine Learning Research3, 583 (2002)

    2002

  3. [3]

    Meilă, inLearning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003

    M. Meilă, inLearning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings(Springer, 2003) pp. 10 173–187

    2003

  4. [4]

    B. E. Dom, inProceedings of the Eighteenth conference on Uncertainty in artificial intelligence(2002) pp. 137– 145

    2002

  5. [5]

    Rosenberg and J

    A. Rosenberg and J. Hirschberg, inProceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL)(2007) pp. 410–420

    2007

  6. [6]

    E.B.FowlkesandC.L.Mallows,JournaloftheAmerican statistical association78, 553 (1983)

    1983

  7. [7]

    Hubert and P

    L. Hubert and P. Arabie, Journal of classification2, 193 (1985)

    1985

  8. [8]

    N. X. Vinh, J. Epps, and J. Bailey, inProceedings of the 26th annual international conference on machine learn- ing(2009) pp. 1073–1080

    2009

  9. [9]

    Romano, N

    S. Romano, N. X. Vinh, J. Bailey, and K. Verspoor, Jour- nal of Machine Learning Research17, 1 (2016)

    2016

  10. [10]

    D. L. Wallace, Journal of the American Statistical Asso- ciation78, 569 (1983)

    1983

  11. [11]

    Tishby, F

    N. Tishby, F. C. Pereira, and W. Bialek, inProc. of the 37-th Annual Allerton Conference on Communication, Control and Computing(1999) pp. 368–377

    1999

  12. [12]

    Still and W

    S. Still and W. Bialek, Neural Computation16, 2483 (2004)

    2004

  13. [13]

    Slonim, G

    N. Slonim, G. S. Atwal, G. Tkačik, and W. Bialek, Pro- ceedings of the National Academy of Sciences102, 18297 (2005)

    2005

  14. [14]

    D. J. Strouse and D. J. Schwab, Neural computation29, 1611 (2017)

    2017

  15. [15]

    A. K. Tan, M. Tegmark, and I. L. Chuang, Entropy24, 771 (2022), arXiv:2204.02489

    Pith/arXiv arXiv 2022

  16. [16]

    Zhao and G

    Y. Zhao and G. Karypis,Criterion Functions for Docu- ment Clustering: Experiments and Analysis, Tech. Rep. TR 01-040 (Department of Computer Science, University of Minnesota, 2001)

    2001

  17. [17]

    Amigó, J

    E. Amigó, J. Gonzalo, J. Artiles, and F. Verdejo, Infor- mation Retrieval12, 461 (2009)

    2009

  18. [18]

    Akaike, inInternational encyclopedia of statistical sci- ence(Springer, 2025) pp

    H. Akaike, inInternational encyclopedia of statistical sci- ence(Springer, 2025) pp. 41–42

    2025

  19. [19]

    Rissanen, Automatica14, 465 (1978)

    J. Rissanen, Automatica14, 465 (1978)

    1978

  20. [20]

    Meilˇ a, inProceedings of the 22nd International Con- ference on Machine Learning (ICML ’05)(ACM Press,

    M. Meilˇ a, inProceedings of the 22nd International Con- ference on Machine Learning (ICML ’05)(ACM Press,

  21. [21]

    T. M. Cover and J. A. Thomas,Elements of Information Theory(Wiley, Hoboken, NJ, 2005)

    2005

  22. [22]

    Furuichi, Journal of Mathematical Physics47(2006)

    S. Furuichi, Journal of Mathematical Physics47(2006)

    2006

  23. [23]

    Amari and A

    S.-i. Amari and A. Ohara, Entropy13, 1170 (2011)

    2011

  24. [24]

    Tsallis, Journal of statistical physics52, 479 (1988)

    C. Tsallis, Journal of statistical physics52, 479 (1988)

    1988

  25. [25]

    Havrda and F

    J. Havrda and F. Charvát, Kybernetika3, 30 (1967)

    1967

  26. [26]

    E. H. Simpson, Nature163, 688 (1949)

    1949

  27. [27]

    A.Tiffeau-Mayer,PhysicalReviewE109,064411(2024)

    2024

  28. [28]

    D. M. Witten and R. Tibshirani, Journal of the American Statistical Association105, 713 (2010)

    2010

  29. [29]

    P. A. Jaskowiak, R. J. Campello, and I. G. Costa, BMC bioinformatics15, S2 (2014)

    2014

  30. [30]

    LeCun, L

    Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, Pro- ceedings of the IEEE86, 2278 (1998)

    1998

  31. [31]

    in the wild

    and agglomerative clustering using Ward’s linkage [32]. In agglomerative clustering, we varied the distance threshold for merging clusters, as in the previous subsec- tion. Ink-means, thenumberofclusterskiscontrolledby a user-defined parameter. The homogeneity–parsimony analysis demonstrates that agglomerative clustering out- performs k-means on this data...

  32. [32]

    Steinhauset al., Bull

    H. Steinhauset al., Bull. Acad. Polon. Sci1, 801 (1956)

    1956

  33. [33]

    J. H. Ward Jr, Journal of the American statistical asso- ciation58, 236 (1963)

    1963

  34. [34]

    Rényi, inProceedings of the Fourth Berkeley Sympo- sium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, Vol

    A. Rényi, inProceedings of the Fourth Berkeley Sympo- sium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, Vol. 4 (Uni- versity of California Press, 1961) pp. 547–562

    1961

  35. [35]

    Nemenman, F

    I. Nemenman, F. Shafee, and W. Bialek, Advances in neural information processing systems14(2001)

    2001

  36. [36]

    Grassberger, arXiv preprint physics/0307138 (2003)

    P. Grassberger, arXiv preprint physics/0307138 (2003)

    Pith/arXiv arXiv 2003

  37. [37]

    J. C. Bezdek,Pattern recognition with fuzzy objective function algorithms(Springer Science & Business Media, 2013)

    2013

  38. [38]

    Lancichinetti and S

    A. Lancichinetti and S. Fortunato, Physical Review E—Statistical, Nonlinear, and Soft Matter Physics80, 016118 (2009)

    2009

  39. [39]

    Ben-Hur, A

    A. Ben-Hur, A. Elisseeff, and I. Guyon, inBiocomputing 2002(World Scientific, 2001) pp. 6–17

    2002

  40. [40]

    Tibshirani, G

    R. Tibshirani, G. Walther, and T. Hastie, Journal of the royal statistical society: series b (statistical methodol- ogy)63, 411 (2001)

    2001

  41. [41]

    P. J. Rousseeuw, Journal of computational and applied mathematics20, 53 (1987)

    1987

  42. [42]

    D. L. Davies and D. W. Bouldin, IEEE Transactions on Pattern Analysis and Machine IntelligencePAMI-1, 224 (1979)

    1979

  43. [43]

    M. E. Newman, G. T. Cantwell, and J.-G. Young, Phys- ical Review E101, 042304 (2020)

    2020

  44. [44]

    C. T. Turner, A. Tiffeau-Mayer, J. Rosenheim, A. Chan- dran, R. Saxena, P. Zhang, J. Jiang, M. Berkeley, F. Pang, I. Uddin,et al., Nature Communications17 (2026)

    2026

  45. [45]

    Tiffeau-Mayer, Github repository,https://github

    A. Tiffeau-Mayer, Github repository,https://github. com/qimmuno/clustereval(2026). Appendix A: The parsimonious information bottleneck Lagrangian In the following, we compare the Lagrangian formula- tion of the Parsimonious Information Bottleneck (PIB), which penalizesH(K|C), with that of the Deterministic IB (DIB). Recall that any multi-objective optimiz...

    2026

  46. [46]

    At orderα= 2, the Tsallis entropy is equal to T2(Z) = 1− X z P(z) 2,(C3) whichisalsocalledGini-Simpson diversity index

    Tsallis entropy definition The Tsallisq-entropy [22, 24, 25] is defined as Tα(Z) = 1 α−1 1− X z P(z) α ! .(C1) It is a monotone transformation of the Rényi entropy Tα(Z) = 1−exp (1−α)H α(Z) α−1 ,(C2) and as such an alternative one-parameter generalization of the Shannon entropy. At orderα= 2, the Tsallis entropy is equal to T2(Z) = 1− X z P(z) 2,(C3) whic...

  47. [47]

    The associated Rényi entropy of order2(also calledcollision entropy) is related toκviaH 2(Z) =−logκ(Z)

    Coincidence probabilities determine pair counts The Tsallis collision entropy is the complement of the coincidence probabilityκ(Z), κ(Z) = X z P(z) 2 = 1−T 2(Z).(C6) This quantity measures the probability that two indepen- dent draws from the distribution are identical.κis also known as Simpson’s index in ecology [26]. The associated Rényi entropy of orde...

  48. [48]

    Normalization and equivalence to TNR/TPR The maximal number of false positive pairs is attained when all objects are assigned to a single cluster. In that case every negative pair is predicted positive, hence max ˜K FP = FP + TN.(C12) Similarly, the maximal number of false negative pairs is attained when each object forms its own singleton clus- ter. In t...