pith. sign in

arxiv: 2606.05230 · v1 · pith:NVNMP4W3new · submitted 2026-06-02 · 📊 stat.ML · cs.LG· eess.SP

Central Description Length (CDL) Clustering Validation Index

Mahdi Shamsi , Soosan Beheshti This is my paper

Pith reviewed 2026-06-28 07:51 UTC · model grok-4.3

classification 📊 stat.ML cs.LGeess.SP
keywords clustering validation indexdescription lengthnon-convex clusterscluster number selectionadjusted rand indexunsupervised learningsynthetic benchmarksimage embeddings
0
0 comments X

The pith

The Central Description Length index ranks cluster partitions by a probabilistic upper bound on the description length of true centers computed from observed compactness, estimated centers, and covariances.

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

Selecting the right number of clusters and the best grouping without labels is a routine problem when analyzing sensor, image, or process data. Most existing validation indices rely on Euclidean compactness and separation, which works well only for round, evenly dense groups. The paper defines CDL-CVI as a single quantity that bounds how much information is required to describe the hidden true centers once the data, assignments, centers, and covariances are known. This bound is computed solely from observable quantities and can be applied to the output of any clustering method. On synthetic data with non-convex and irregular shapes, the index selected the reference number of clusters more frequently and produced higher agreement with ground-truth labels than the tested alternatives, all without a kernel transformation step.

Core claim

The Central Description Length clustering validation index uses the observed within-cluster compactness, the estimated cluster centers, and the estimated cluster covariances to compute a probabilistic upper bound on the description length associated with the unobservable true cluster centers. The bound condenses intra-cluster compactness and centroid displacement into a single computable quantity evaluated on the partition produced by any clustering algorithm. The implementation uses only the data, the partition, the estimated centers, and the estimated covariances and does not require ground-truth labels.

What carries the argument

The Central Description Length (CDL) index: a probabilistic upper bound on the description length of true cluster centers derived from within-cluster compactness and estimated parameters.

If this is right

  • CDL-CVI selects the reference number of clusters more often than conventional indices on non-convex synthetic benchmarks.
  • It produces partitions with higher Adjusted Rand Index values than the tested CVIs on the same data.
  • It achieves these results without an additional kernel preprocessing stage.
  • On frozen unsupervised embeddings of MNIST, CIFAR-10, and STL-10 it returns cluster counts close to the reference class numbers for K-means, DBSCAN, and spectral clustering.

Where Pith is reading between the lines

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

  • The same bound construction could be applied to other unsupervised partitioning tasks where a description-length proxy for model quality is useful.
  • It may reduce reliance on hand-tuned distance measures when cluster shapes are unknown in advance.
  • The approach could be tested on streaming or incrementally arriving data to check whether the bound remains stable under partial observations.

Load-bearing premise

The probabilistic upper bound on description length computed from observed within-cluster compactness, estimated centers, and estimated covariances serves as a valid proxy for partition quality across arbitrary cluster shapes.

What would settle it

A collection of non-convex clusters in which the CDL score assigns a higher value to a demonstrably poor partition than to the reference partition even though the bound is calculated correctly from the observed quantities.

Figures

Figures reproduced from arXiv: 2606.05230 by Mahdi Shamsi, Soosan Beheshti.

Figure 1
Figure 1. Figure 1: sketches the clustering procedure for a single data point. A point x(i) that lies in the [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example of the x(i) with the associated µx(i) and σx(i) [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of true centers and estimated centers for [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: CDL-CVI for selection of hyperparameter ϵ in DBSCAN are correctly recovered and a small number of points are flagged as outliers. The Silhouette and Dunn indices choose ϵ values of 0.45 and 0.47 respectively. Figure 5b shows the DBSCAN partition at ϵ = 0.45 (the result for ϵ = 0.47 is almost identical): DBSCAN now breaks each ring into many small dense subclusters. Figure 5c shows the DBSCAN partition at ϵ… view at source ↗
Figure 5
Figure 5. Figure 5: CVI ϵ parameters tuning results in DBSCAN clustering 10 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Benchmark datasets. (a) Aggregation, (b) D31, (c) Jain’s Toy, (d) Path-Based, (e) S15. [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Path-based dataset with DBSCAN clustering and validation-index-based hyperparameter [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
read the original abstract

Selecting a clustering algorithm and its hyperparameters without labels is a common difficulty in engineering machine learning pipelines that work with unsupervised analysis of sensor, image, or process data. Clustering validation indices (CVIs) provide internal scores for ranking candidate clusterings, but most popular CVIs are built from Euclidean compactness and separation terms and so tend to favour compact, convex partitions. Their performance is known to degrade on non convex, irregular, or variable density data, where kernel transformations or alternative distance measures are typically used at the cost of additional tuning and computation. This paper introduces the Central Description Length (CDL) clustering validation index. CDL uses the observed within cluster compactness, the estimated cluster centers, and the estimated cluster covariances to compute a probabilistic upper bound on the description length associated with the unobservable true cluster centers. The bound condenses intra cluster compactness and centroid displacement into a single computable quantity and is evaluated on the partition produced by any clustering algorithm. The implementation uses only observable quantities (the data, the partition, the estimated centers, and the estimated covariances) and does not use ground truth labels. On synthetic benchmarks with non convex and arbitrary shape clusters, CDL-CVI selected the reference number of clusters more often and reached higher Adjusted Rand Index (ARI) values than the conventional CVIs we tested, without an additional kernel preprocessing stage. On image benchmarks (MNIST, CIFAR-10, STL-10) clustered from frozen unsupervised embeddings, CDL-CVI returned cluster numbers close to the reference class counts across K-means, DBSCAN, and spectral clustering in the reported trials.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces the Central Description Length (CDL) clustering validation index, which computes a probabilistic upper bound on the description length of unobservable true cluster centers from observed within-cluster compactness, estimated centers, and estimated covariances. This bound is used to score partitions produced by any clustering algorithm. The manuscript reports that on synthetic benchmarks with non-convex and arbitrary-shape clusters, CDL-CVI more frequently recovers the reference number of clusters and yields higher ARI than tested conventional CVIs, without kernel preprocessing; similar behavior is shown on MNIST, CIFAR-10, and STL-10 embeddings clustered with K-means, DBSCAN, and spectral methods.

Significance. If the bound remains a reliable quality proxy outside elliptical regimes, CDL would address a documented weakness of compactness-separation CVIs on irregular data and reduce the need for kernel tuning. The use of only observable quantities is a practical strength.

major comments (2)
  1. [Derivation of the CDL bound (likely §3) and synthetic benchmark results] The central performance claim (superior recovery of reference K and higher ARI on non-convex synthetic data) rests on the assertion that the probabilistic upper bound remains a valid proxy for partition quality when clusters deviate from elliptical geometry. Because the bound is constructed from estimated covariances and compactness, its derivation necessarily invokes second-moment or Gaussian modeling of latent centers; the manuscript must show explicitly (in the section deriving the bound) that the ordering of the bound is preserved under non-convex level sets, or provide a counter-example test.
  2. [Experimental protocol and results section] Table or figure reporting the synthetic non-convex results: the claim that CDL-CVI outperforms conventional CVIs is load-bearing, yet the abstract supplies no protocol details on cluster generation, number of trials, or how covariance estimates are obtained for irregular shapes. Without these, it is impossible to rule out that the reported advantage arises from post-hoc hyper-parameter choices or from the synthetic data still being approximately elliptical.
minor comments (2)
  1. [Abstract] The abstract states that CDL 'does not use ground truth labels' and 'uses only observable quantities'; this is already clear from the definition and could be shortened.
  2. [Notation and abstract] Notation for the bound (e.g., symbols for compactness, center displacement, and covariance) should be introduced once and used consistently; several conventional CVIs are mentioned but not named in the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on the CDL bound derivation and experimental protocol. We address each point below and will revise the manuscript accordingly to improve clarity and reproducibility while preserving the core contributions.

read point-by-point responses

  1. Referee: The central performance claim (superior recovery of reference K and higher ARI on non-convex synthetic data) rests on the assertion that the probabilistic upper bound remains a valid proxy for partition quality when clusters deviate from elliptical geometry. Because the bound is constructed from estimated covariances and compactness, its derivation necessarily invokes second-moment or Gaussian modeling of latent centers; the manuscript must show explicitly (in the section deriving the bound) that the ordering of the bound is preserved under non-convex level sets, or provide a counter-example test.

    Authors: The CDL bound is an information-theoretic upper bound on the description length of latent centers, constructed solely from observable quantities (compactness, estimated centers, and sample covariances). While covariance estimation requires finite second moments, the bound does not model cluster shapes as elliptical or Gaussian; it penalizes deviations in compactness and centroid displacement in a shape-agnostic manner. The relative ordering is therefore preserved for non-convex clusters because poorer partitions increase the bound regardless of geometry. We will revise §3 to include an explicit argument (based on the bound's monotonicity properties) showing why the ordering holds under non-convex level sets. The existing synthetic benchmarks with arbitrary shapes already provide supporting evidence rather than requiring a counter-example. revision: partial

  2. Referee: Table or figure reporting the synthetic non-convex results: the claim that CDL-CVI outperforms conventional CVIs is load-bearing, yet the abstract supplies no protocol details on cluster generation, number of trials, or how covariance estimates are obtained for irregular shapes. Without these, it is impossible to rule out that the reported advantage arises from post-hoc hyper-parameter choices or from the synthetic data still being approximately elliptical.

    Authors: We agree that the experimental protocol requires more detail for reproducibility. In the revised manuscript we will expand the results section with: (i) explicit description of synthetic data generation using non-convex generators (two-moons, concentric circles, and anisotropic blobs with additive noise to produce irregular shapes); (ii) the number of independent trials (50 per configuration); and (iii) covariance estimation via the sample covariance matrix computed directly from points assigned to each cluster. These additions will confirm that the data deviates from elliptical forms and that reported gains do not stem from hidden tuning. revision: yes

Circularity Check

0 steps flagged

No circularity: CDL-CVI is a directly defined index from observables

full rationale

The paper defines CDL-CVI explicitly as a computable probabilistic upper bound constructed from the partition, within-cluster compactness, estimated centers, and estimated covariances produced by any clustering algorithm. This is a standard definitional construction for an internal validation index and does not reduce to its inputs by construction, via fitted parameters renamed as predictions, or through self-citation chains. No uniqueness theorems, ansatzes, or prior self-referential results are invoked as load-bearing steps. Empirical superiority on benchmarks is presented as an independent test of the defined quantity rather than a derivation that assumes the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The method presupposes that estimated covariances from the partition are sufficient to bound true center description length, but this is not formalized here.

pith-pipeline@v0.9.1-grok · 5824 in / 1163 out tokens · 21621 ms · 2026-06-28T07:51:05.170764+00:00 · methodology

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

43 extracted references · 1 canonical work pages

  1. [1]

    Jain A K 2010 Data clustering: 50 years beyond K-meansPattern recognition letters31 651–666

    2010

  2. [2]

    Liu Y, Li Z, Xiong H, Gao X and Wu J 2010 Understanding of internal clustering validation measures2010 IEEE international conference on data mining(IEEE) pp 911–916

    2010

  3. [3]

    Bandyapadhyay S, Fomin F V, Golovach P A, Lochet W, Purohit N and Simonov K 2023 How to find a good explanation for clustering?Artificial Intelligence322103948

    2023

  4. [4]

    Li F, Qian Y, Wang J, Dang C and Jing L 2019 Clustering ensemble based on sample’s stabilityArtificial Intelligence27337–55

    2019

  5. [5]

    Hassan B A, Tayfor N B, Hassan A A, Ahmed A M, Rashid T A and Abdalla N N 2024 From A-to-Z review of clustering validation indicesNeurocomputing601128198

    2024

  6. [6]

    Arbelaitz O, Gurrutxaga I and Muguerza J 2013 An extensive comparative study of cluster validity indicesPattern Recognition46243–256

    2013

  7. [7]

    Gurrutxaga I, Muguerza J, Arbelaitz O, P´ erez J M and Mart´ ın J I 2011 Towards a standard methodology to evaluate internal cluster validity indicesPattern Recognition Letters32 505–515

    2011

  8. [8]

    Rousseeuw P J 1987 Silhouettes: a graphical aid to the interpretation and validation of cluster analysisJournal of computational and applied mathematics2053–65

    1987

  9. [9]

    Davies D L and Bouldin D W 1979 A cluster separation measureIEEE Transactions on Pattern Analysis and Machine IntelligencePAMI-1224–227

    1979

  10. [10]

    Xie X L and Beni G 1991 A validity measure for fuzzy clusteringIEEE Transactions on Pattern Analysis & Machine Intelligence13841–847

    1991

  11. [11]

    Dunn J C 1973 A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clustersJournal of Cybernetics332–57

    1973

  12. [12]

    Cali´ nski T and Harabasz J 1974 A dendrite method for cluster analysisCommunications in Statistics-theory and Methods31–27

    1974

  13. [13]

    Rahman F and Beheshti S 2018 Kernel K-MACE clustering2018 52nd Asilomar Conference on Signals, Systems, and Computers(IEEE) pp 2002–2006

    2018

  14. [14]

    Moulavi D, Jaskowiak P A, Campello R J, Zimek A and Sander J 2014 Density-based clustering validationProceedings of the 2014 SIAM international conference on data mining (SIAM) pp 839–847

    2014

  15. [15]

    Cheng D, Zhu Q, Huang J, Wu Q and Yang L 2018 A novel cluster validity index based on local coresIEEE transactions on neural networks and learning systems30985–999

    2018

  16. [16]

    Khan G A, Hu J, Li T, Diallo B and Du S 2023 Multi-view subspace clustering for learning joint representation via low-rank sparse representationApplied Intelligence5322511–22530

    2023

  17. [17]

    Diallo B, Hu J, Li T, Khan G A, Liang X and Wang H 2023 Auto-attention mechanism for multi-view deep embedding clusteringPattern Recognition143109764

    2023

  18. [18]

    Li Y, Hu P, Liu Z, Peng D, Zhou J T and Peng X 2021 Contrastive clusteringProceedings of the AAAI conference on artificial intelligencevol 35 pp 8547–8555 15 IOP PublishingJournalvv(yyyy) aaaaaa Authoret al

    2021

  19. [19]

    Khan G A, Khan J, Anwar T, Al-Huda Z, Diallo B and Ahmad N 2024 Complementary incomplete weighted concept factorization methods for multi-view clusteringKnowledge and Information Systems667469–7494

    2024

  20. [20]

    Beheshti S and Shamsi M 2025ϵ-Confidence Approximately Correct (ϵ-CoAC) learnability and hyperparameter selection in linear regression modelingIEEE AccessIn press

  21. [21]

    Beheshti S and Dahleh M A 2005 A new information-theoretic approach to signal denoising and best basis selectionIEEE Transactions on Signal Processing533613–3624

    2005

  22. [22]

    Fakhrzadeh A and Beheshti S 2007 Minimum noiseless description length (MNDL) thresholding2007 IEEE Symposium on Computational Intelligence in Image and Signal Processing(IEEE) pp 146–150

    2007

  23. [23]

    Gr¨ unwald P D 2007The minimum description length principle(MIT press)

  24. [24]

    Beheshti S, Nidoy E and Rahman F 2020 K-MACE and kernel K-MACE clusteringIEEE Access817390–17403

    2020

  25. [25]

    Beheshti S and Sedghizadeh S 2018 Number of source signal estimation by the mean squared eigenvalue errorIEEE Transactions on Signal Processing665694–5704

    2018

  26. [26]

    Shamsi M and Beheshti S 2023 Relative entropy (RE)-based LTI system modeling equipped with simultaneous time delay estimation and online modelingIEEE Access11113885–113899

    2023

  27. [27]

    Beheshti S and Bommanahally V 2025 Minimum mismatch modeling (3M) hyperparameter selection in autoregressive moving average (ARMA) modelingIEEE Access13133681–133693

    2025

  28. [28]

    Bayati K, Umapathy K and Beheshti S 2025 Reliable truncation parameter selection and model order estimation for stochastic subspace identificationJournal of the Franklin Institute 107766 ISSN 0016-0032

    2025

  29. [29]

    Shahbaba M and Beheshti S 2014 MACE-means clusteringSignal Processing105216–225

    2014

  30. [30]

    Shamsi M, Rahman F and Beheshti S 2019 Correct number of clusters (CNC) description length in arbitrary shape clustering2019 16th Canadian Workshop on Information Theory (CWIT)(IEEE) pp 1–4

    2019

  31. [31]

    Cover T M 1999Elements of information theory(John Wiley & Sons)

  32. [32]

    Rodrigues M R and Eldar Y C 2021Information-theoretic methods in data science (Cambridge University Press)

  33. [33]

    Motallebi H, Nasihatkon R and Jamshidi M 2022 A local mean-based distance measure for spectral clusteringPattern Analysis and Applications25351–359

    2022

  34. [34]

    Lee S H, Jeong Y S, Kim J Y and Jeong M K 2018 A new clustering validity index for arbitrary shape of clustersPattern Recognition Letters112263–269

    2018

  35. [35]

    Khan K, Rehman S U, Aziz K, Fong S and Sarasvady S 2014 DBSCAN: Past, present and futureThe fifth international conference on the applications of digital information and web technologies (ICADIWT 2014)(IEEE) pp 232–238

    2014

  36. [36]

    LeCun Y, Cortes C and Burges C J C 1998 The MNIST database of handwritten digits http://yann.lecun.com/exdb/mnist/accessed: 2025-08-22

    1998

  37. [37]

    Krizhevsky A and Hinton G 2009 Learning multiple layers of features from tiny images Technical report University of Toronto

    2009

  38. [38]

    Coates A, Ng A and Lee H 2011 An analysis of single-layer networks in unsupervised feature learningProceedings of the fourteenth international conference on artificial intelligence and statistics(JMLR Workshop and Conference Proceedings) pp 215–223

    2011

  39. [39]

    Chen P Y and Huang J J 2019 A hybrid autoencoder network for unsupervised image clusteringAlgorithms12122

    2019

  40. [40]

    Xie J, Girshick R and Farhadi A 2016 Unsupervised deep embedding for clustering analysis International conference on machine learning(PMLR) pp 478–487 16 IOP PublishingJournalvv(yyyy) aaaaaa Authoret al

    2016

  41. [41]

    Sarasti S 2024 MNISTVaehttps://huggingface.co/sebastiansarasti/MNISTVaeaccessed: 2025-08-22

    2024

  42. [42]

    Chen T, Kornblith S, Norouzi M and Hinton G 2020 A simple framework for contrastive learning of visual representationsInternational conference on machine learning(PmLR) pp 1597–1607

    2020

  43. [43]

    The full algebra of the variance expressions is given in [24]; the notation here follows the CDL-CVI formulation used in this paper

    Chen T, Kornblith S, Swersky K, Norouzi M and Hinton G 2020 Big Self-Supervised Models are Strong Semi-Supervised LearnersarXiv preprint arXiv:2006.10029 A Derivation of CDL-CVI Bounds This appendix summarizes the derivation that relates the observable cluster compactnessy KΘ to the unobservable Average Central Errorz KΘ. The full algebra of the variance ...

    work page arXiv 2020