在 R 中使用 DISCO 指数快速、低内存开销地评估基于密度的聚类结果

arXiv cs.LG 论文

摘要

一篇介绍 discoCVI R 包 0.2.0 版本的预印本。该包通过单链接合并树,以线性内存精确计算基于密度的聚类的 DISCO 聚类有效性指数,相比上一版本提速 23–138 倍,相比 Python 参考实现提速 3–9 倍,并能在约 50 秒内完成对 100,000 个点的评分。

arXiv:2611.25114v1 Announce Type: new Abstract: DISCO is a recent internal cluster validity index for density-based clustering that, unlike earlier indices, also evaluates the quality of noise labels. The discoCVI package makes DISCO available in R. This article describes the design of the package and a typical workflow, in which DISCO is used to compare clusterings and to choose the parameters of HDBSCAN without ground truth, followed by the implementation introduced in version 0.2.0. DISCO is defined through density-connectivity distances between all pairs of points, so direct implementations store several n-by-n matrices. We show that every quantity DISCO needs can be read off the single-linkage merge tree of the mutual-reachability minimum spanning tree, so that the index can be computed exactly with memory that grows linearly with the number of points, while the running time remains quadratic as in the original definition. The implementation is tested against the previous version, agrees with the original Python implementation to within $3 \times 10^{-13}$, and corrects the score of singleton clusters to match the published definition. In benchmarks, discoCVI is 23 to 138 times faster than its previous version for 500 to 4,000 points and 3 to 9 times faster than the Python reference for 500 to 8,000 points, using a fraction of the memory of both, and it scores 100,000 points in about 50 seconds with less than 200 MB of memory.
查看原文
查看缓存全文

缓存时间: 2026/11/20 09:15

# Fast and Memory-Light Evaluation of Density-Based Clusterings with the DISCO Index in R
Source: [https://arxiv.org/html/2611.25114](https://arxiv.org/html/2611.25114)
November 2026 Preprint\.

###### Abstract

DISCO is a recent internal cluster validity index for density\-based clustering that, unlike earlier indices, also evaluates the quality of noise labels\. The discoCVI package makes DISCO available in R\. This article describes the design of the package and a typical workflow, in which DISCO is used to compare clusterings and to choose the parameters of HDBSCAN without ground truth, followed by the implementation introduced in version 0\.2\.0\. DISCO is defined through density\-connectivity distances between all pairs of points, so direct implementations store several n\-by\-n matrices\. We show that every quantity DISCO needs can be read off the single\-linkage merge tree of the mutual\-reachability minimum spanning tree, so that the index can be computed exactly with memory that grows linearly with the number of points, while the running time remains quadratic as in the original definition\. The implementation is tested against the previous version, agrees with the original Python implementation to within3×10−133\\times 10^\{\-13\}, and corrects the score of singleton clusters to match the published definition\. In benchmarks, discoCVI is 23 to 138 times faster than its previous version for 500 to 4,000 points and 3 to 9 times faster than the Python reference for 500 to 8,000 points, using a fraction of the memory of both, and it scores 100,000 points in about 50 seconds with less than 200 MB of memory\.

## 1Introduction

Clustering without ground truth needs internal cluster validity indices \(CVIs\), which score a partition using only the data and the labels\. They are used to compare the output of different algorithms and, above all, to choose the parameters of a clustering algorithm when no labelled data exist\. For density\-based algorithms such as DBSCAN\([Ester et al\., 1996](https://arxiv.org/html/2611.25114#bib.bib3)\)and HDBSCAN\([Campello et al\., 2013](https://arxiv.org/html/2611.25114#bib.bib4)\), which find clusters of arbitrary shape and label low\-density points as noise, classical indices such as the silhouette coefficient\([Rousseeuw, 1987](https://arxiv.org/html/2611.25114#bib.bib6)\)are a poor fit: they favour convex clusters and have no notion of noise\. Density\-based indices such as DBCV\([Moulavi et al\., 2014](https://arxiv.org/html/2611.25114#bib.bib5)\)address the first problem, and the recent DISCO index\([Beer et al\., 2026](https://arxiv.org/html/2611.25114#bib.bib1)\)also addresses the second: it scores every point labelled as noise according to whether it really lies in a sparse region far from all clusters\.

Existing software\.Several CRAN packages provide internal validity indices:[cluster](https://cran.r-project.org/package=cluster)computes the silhouette coefficient,[clusterCrit](https://cran.r-project.org/package=clusterCrit)and[fpc](https://cran.r-project.org/package=fpc)offer a wide range of classical indices \([fpc](https://cran.r-project.org/package=fpc)also implements the density\-based index CDbw\), and[DBCVindex](https://cran.r-project.org/package=DBCVindex)implements DBCV\([Chicco et al\., 2025](https://arxiv.org/html/2611.25114#bib.bib8)\)\. None of them evaluates noise labels\. The original DISCO implementation is written in Python and is not distributed as a package\.[discoCVI](https://cran.r-project.org/package=discoCVI)\([Entezari, 2026](https://arxiv.org/html/2611.25114#bib.bib18)\)makes DISCO available in R; its first release translated the reference implementation line by line\.

The gap\.DISCO is defined through the density\-connectivity distance \(dc\-distance\)\([Beer et al\., 2023](https://arxiv.org/html/2611.25114#bib.bib2)\)between every pair of points\. Both the reference implementation and[discoCVI](https://cran.r-project.org/package=discoCVI)0\.1\.1 therefore build the full matrices of mutual\-reachability distances and dc\-distances\. Time and memory grow quadratically with the number of pointsnn: version 0\.1\.1 needs about 19 seconds and 1\.2 GB to score 4,000 points, and a few thousand points more exhaust a laptop\. Because an index is usually evaluated for many candidate clusterings, this cost is multiplied by the size of the search, which matters for running time and also for the energy use of the analysis\([Strubell et al\., 2019](https://arxiv.org/html/2611.25114#bib.bib21);[Schwartz et al\., 2020](https://arxiv.org/html/2611.25114#bib.bib22);[Lannelongue et al\., 2021](https://arxiv.org/html/2611.25114#bib.bib23)\)\.

This article\.We describe the design of[discoCVI](https://cran.r-project.org/package=discoCVI)and a typical workflow, and then the implementation introduced in version 0\.2\.0, which computes DISCO exactly without anyn×nn\\times nmatrix\. We show that this is possible because the dc\-distance between two points equals the height at which they are merged in the single\-linkage tree of the mutual\-reachability graph, so that all per\-cluster sums and minima of dc\-distances can be accumulated in one pass over that tree\. We report tests against the previous version and against the original Python implementation, and a benchmark of time, memory and energy\.

## 2The DISCO index

We follow the notation of[Beer et al\. \(2026\)](https://arxiv.org/html/2611.25114#bib.bib1)\. LetX=\{x1,…,xn\}⊂ℝpX=\\\{x\_\{1\},\\dots,x\_\{n\}\\\}\\subset\\mathbb\{R\}^\{p\}and let a clustering𝒞=\{C1,…,CK\}\\mathcal\{C\}=\\\{C\_\{1\},\\dots,C\_\{K\}\\\}consist of disjoint clusters, with the remaining pointsN=X∖⋃iCiN=X\\setminus\\bigcup\_\{i\}C\_\{i\}labelled as noise; for a cluster pointxx,C^x\\hat\{C\}\_\{x\}denotes its cluster\.

Distances\.For a parameterμ\\mu\(min\_pointsin the package, default 5\), the core distanceκ⁡\(x\)\\kappa\(x\)is the Euclidean distance fromxxto itsμ\\mu\-th nearest neighbour, wherexxcounts as its own first neighbour, as in the reference implementation; equivalently, it is the distance to the\(μ−1\)\(\\mu\-1\)\-th nearest*other*point, andμ≥2\\mu\\geq 2is required\. The mutual\-reachability distance\([Campello et al\., 2013](https://arxiv.org/html/2611.25114#bib.bib4)\)is

dm​\(x,y\)=max⁡\{κ⁡\(x\),κ⁡\(y\),∥x−y∥\},d\_\{m\}\(x,y\)=\\max\\\{\\kappa\(x\),\\kappa\(y\),\\lVert x\-y\\rVert\\\},and the dc\-distance\([Beer et al\., 2023](https://arxiv.org/html/2611.25114#bib.bib2)\)is the minimax path distance in the complete graph weighted bydmd\_\{m\}, that is, the smallest possible value of the largest edge on a path fromxxtoyy, withdd​c​\(x,x\)=0d\_\{dc\}\(x,x\)=0\. It equals the largest edge on the path betweenxxandyyin any minimum spanning tree \(MST\) of that graph\([Hu, 1961](https://arxiv.org/html/2611.25114#bib.bib9)\); in particular it does not depend on how ties between equal edge weights are broken when the MST is built\.

DISCO score\.DISCO is defined pointwise, and the score of a clustering is the mean of the pointwise scores,

ρ⁡\(X\)=1n​∑x∈Xρ⁡\(x\),ρ⁡\(x\)=\{ρcluster​\(x\)if​x∈Ci​for some​i,ρnoise​\(x\)if​x∈N\.\\rho\(X\)=\\frac\{1\}\{n\}\\sum\_\{x\\in X\}\\rho\(x\),\\qquad\\rho\(x\)=\\begin\{cases\}\\rho\_\{\\text\{cluster\}\}\(x\)&\\text\{if \}x\\in C\_\{i\}\\text\{ for some \}i,\\\\ \\rho\_\{\\text\{noise\}\}\(x\)&\\text\{if \}x\\in N\.\\end\{cases\}
Cluster points\.Withd¯d​c​\(x,C\)\\bar\{d\}\_\{dc\}\(x,C\)the mean dc\-distance fromxxto the points ofCC, a cluster point receives

ρcluster​\(x\)=minCi≠C^x⁡d¯d​c​\(x,Ci\)−d¯d​c​\(x,C^x\)max⁡\{d¯d​c​\(x,Ci\),d¯d​c​\(x,C^x\)\}\.\\rho\_\{\\text\{cluster\}\}\(x\)=\\min\_\{C\_\{i\}\\neq\\hat\{C\}\_\{x\}\}\\frac\{\\bar\{d\}\_\{dc\}\(x,C\_\{i\}\)\-\\bar\{d\}\_\{dc\}\(x,\\hat\{C\}\_\{x\}\)\}\{\\max\\\{\\bar\{d\}\_\{dc\}\(x,C\_\{i\}\),\\bar\{d\}\_\{dc\}\(x,\\hat\{C\}\_\{x\}\)\\\}\}\.For fixeda≥0a\\geq 0the functionb↦\(b−a\)/max⁡\{a,b\}b\\mapsto\(b\-a\)/\\max\\\{a,b\\\}is non\-decreasing, so the minimum is attained at the closest cluster, andρcluster\\rho\_\{\\text\{cluster\}\}is the silhouette coefficient computed on dc\-distances:

ρcluster​\(x\)=b⁡\(x\)−a⁡\(x\)max⁡\{a⁡\(x\),b⁡\(x\)\},\\displaystyle\\rho\_\{\\text\{cluster\}\}\(x\)=\\frac\{b\(x\)\-a\(x\)\}\{\\max\\\{a\(x\),b\(x\)\\\}\},a⁡\(x\)=1\|C^x\|−1​∑y∈C^x∖\{x\}dd​c​\(x,y\),b⁡\(x\)=minCi≠C^x⁡1\|Ci\|​∑y∈Cidd​c​\(x,y\)\.\\displaystyle a\(x\)=\\frac\{1\}\{\|\\hat\{C\}\_\{x\}\|\-1\}\\sum\_\{y\\in\\hat\{C\}\_\{x\}\\setminus\\\{x\\\}\}d\_\{dc\}\(x,y\),\\qquad b\(x\)=\\min\_\{C\_\{i\}\\neq\\hat\{C\}\_\{x\}\}\\frac\{1\}\{\|C\_\{i\}\|\}\\sum\_\{y\\in C\_\{i\}\}d\_\{dc\}\(x,y\)\.As in the reference implementation, which uses the silhouette function of scikit\-learn\([Pedregosa et al\., 2011](https://arxiv.org/html/2611.25114#bib.bib17)\), the within\-cluster meana⁡\(x\)a\(x\)is taken over the*other*members ofC^x\\hat\{C\}\_\{x\}\.

Noise points\.With the core\-distance threshold of a clusterκ⁡\(C\)=maxy∈C⁡κ⁡\(y\)\\kappa\(C\)=\\max\_\{y\\in C\}\\kappa\(y\)andmC​\(x\)=miny∈C⁡dd​c​\(x,y\)m\_\{C\}\(x\)=\\min\_\{y\\in C\}d\_\{dc\}\(x,y\), a noise point receives the minimum of two scores,

ρsparse​\(x\)=minC∈𝒞⁡κ⁡\(x\)−κ⁡\(C\)max⁡\{κ⁡\(x\),κ⁡\(C\)\},ρfar​\(x\)=minC∈𝒞⁡mC​\(x\)−κ​\(C\)max⁡\{mC​\(x\),κ⁡\(C\)\},\\rho\_\{\\text\{sparse\}\}\(x\)=\\min\_\{C\\in\\mathcal\{C\}\}\\frac\{\\kappa\(x\)\-\\kappa\(C\)\}\{\\max\\\{\\kappa\(x\),\\kappa\(C\)\\\}\},\\qquad\\rho\_\{\\text\{far\}\}\(x\)=\\min\_\{C\\in\\mathcal\{C\}\}\\frac\{m\_\{C\}\(x\)\-\\kappa\(C\)\}\{\\max\\\{m\_\{C\}\(x\),\\kappa\(C\)\\\}\},ρnoise​\(x\)=min⁡\{ρsparse​\(x\),ρfar​\(x\)\}\.\\rho\_\{\\text\{noise\}\}\(x\)=\\min\\\{\\rho\_\{\\text\{sparse\}\}\(x\),\\rho\_\{\\text\{far\}\}\(x\)\\\}\.ρsparse\\rho\_\{\\text\{sparse\}\}is positive ifxxis sparser than every cluster, andρfar\\rho\_\{\\text\{far\}\}is positive ifxxis not density\-connected to any cluster\.

Edge cases\([Beer et al\., 2026](https://arxiv.org/html/2611.25114#bib.bib1), Section 3\.1\)\. \(i\) If all points are noise, every score is−1\-1\. \(ii\) If there is a single cluster and no noise, every score is00\. \(iii\) Points in singleton clusters score00\. \(iv\) If there is a single cluster plus noise, the cluster points are compared with the closest noise point instead of the \(non\-existent\) closest cluster, i\.e\.b⁡\(x\)b\(x\)is replaced byminy∈N⁡dd​c​\(x,y\)\\min\_\{y\\in N\}d\_\{dc\}\(x,y\)\. \(v\) If a denominator is zero, for example when more thanμ\\muduplicate points have core distance00, the corresponding fraction is set to00\.

## 3Package design

Intended users\.[discoCVI](https://cran.r-project.org/package=discoCVI)is written for data analysts who cluster data with a density\-based method, for example with[dbscan](https://cran.r-project.org/package=dbscan)\([Hahsler et al\., 2019](https://arxiv.org/html/2611.25114#bib.bib7)\), and need to judge or tune the result without ground truth\. Using the package requires no knowledge of how DISCO is computed: one function returns a score, and a second returns one score per point\.

Interface\.The package exports five functions with plain numeric inputs and outputs:

- •disco\_score\(X, labels, min\_points = 5\)returns the DISCO score of a clustering, a single number in\[−1,1\]\[\-1,1\];
- •disco\_samples\(X, labels, min\_points = 5\)returns the pointwise scoresρ⁡\(x\)\\rho\(x\);
- •p\_cluster\(\)andp\_noise\(\)return the two components of the score for cluster points and noise points \(p\_noise\(\)returnsρsparse\\rho\_\{\\text\{sparse\}\}andρfar\\rho\_\{\\text\{far\}\}separately\);
- •compute\_dc\_distances\(X, min\_points = 5\)returns the dc\-distance matrix, which is useful for analysing small datasets or comparing many labellings of the same data\.

Xis a numeric matrix or data frame andlabelsan integer vector in which\-1marks noise\. The function names, the argumentmin\_pointsand the noise label\-1are those of the reference Python implementation, which itself follows the conventions of scikit\-learn, so that code and results carry over between the two languages\.

Design choices\.The functions return plain numeric vectors \(or a list of two vectors forp\_noise\(\)\) rather than objects of an S3, S4 or R6 class\. A validity index produces numbers that users typically put into a data frame, average, plot, or pass tosapply\(\)over a grid of parameters, and a class would add no information while making these operations less direct\. The package is deliberately agnostic to the clustering algorithm: it accepts labels from DBSCAN, HDBSCAN, OPTICS,kk\-means or any other source, and therefore lists[dbscan](https://cran.r-project.org/package=dbscan)only as a suggested package\. The only dependencies are[FNN](https://cran.r-project.org/package=FNN)\([Beygelzimer et al\., 2024](https://arxiv.org/html/2611.25114#bib.bib19)\), for the nearest\-neighbour search that defines the core distances, and[Rcpp](https://cran.r-project.org/package=Rcpp)\([Eddelbuettel and François, 2011](https://arxiv.org/html/2611.25114#bib.bib16)\), for the compiled spanning\-tree step\. The computation is deterministic and single\-threaded; this keeps resource use predictable and lets users parallelise over candidate clusterings, which is where parallelism pays off in a parameter search\. Inputs are validated, with informative errors for empty data, mismatched lengths ofXandlabels, andmin\_points < 2\.

Documentation and tests\.Every exported function has a help page with an example, a vignette \(vignette\("discoCVI"\)\) walks through the workflow of the next section, and the test suite checks the values of all exported functions \(see the implementation section\)\. Bugs and feature requests can be reported on GitHub \([https://github\.com/aminentezari/discoCVI/issues](https://github.com/aminentezari/discoCVI/issues)\)\.

## 4A typical workflow

We illustrate the workflow with two interleaving half\-moons and 40 points of uniform noise\.

```
library(discoCVI)
library(dbscan)

set.seed(42)
moons <- function(n, sd = 0.08) {
  t1 <- runif(n / 2, 0, pi); t2 <- runif(n / 2, 0, pi)
  rbind(cbind(cos(t1), sin(t1)), cbind(1 - cos(t2), 0.5 - sin(t2))) +
    matrix(rnorm(2 * n, sd = sd), ncol = 2)
}
X <- rbind(moons(600), cbind(runif(40, -1.5, 2.5), runif(40, -1, 1.5)))
```

Scoring a clustering\.We cluster the data with HDBSCAN\. Since[dbscan](https://cran.r-project.org/package=dbscan)labels noise as0and DISCO expects\-1, the labels are converted first; passing them unchanged would silently treat all noise points as one extra cluster\.

```
labels <- hdbscan(X, minPts = 10)$cluster
labels[labels == 0] <- -1L
table(labels)
```

```
#> labels
#>  -1   1   2
#>  32 304 304
```

```
disco_score(X, kmeans(X, centers = 2, nstart = 10)$cluster)
```

DISCO rates the HDBSCAN result, which follows the moons and separates the scattered points as noise, higher than thekk\-means partition, which cuts across the moons\.

DISCO is considerably stricter than the silhouette coefficient: values close to 1 are rare, and good clusterings typically score well below what the silhouette would suggest\. Its rules of thumb therefore do not apply, and DISCO is best used, as here, to compare clusterings of the same data\.

Choosing a parameter\.Because DISCO needs no ground truth, it can be used to select the parameter of the clustering algorithm\.

```
score_minpts <- function(m) {
  lab <- hdbscan(X, minPts = m)$cluster
  lab[lab == 0] <- -1L
  disco_score(X, lab)
}
grid <- c(3, 5, 10, 20, 50)
round(sapply(grid, score_minpts), 3)
```

```
#> [1] -0.213  0.445  0.444  0.442  0.365
```

Themin\_pointsargument ofdisco\_score\(\)is a different parameter: it is the neighbourhood size DISCO uses to measure density \(default 5, as in the original paper\) and need not equal theminPtsof the clustering\. HereminPtsvalues from 5 to 20 give almost the same score, so the choice of 10 above is not critical, whereasminPts = 3is clearly worse\.

Inspecting points\.Pointwise scores show where a clustering is convincing and where it is not \(Figure[1](https://arxiv.org/html/2611.25114#S4.F1)\)\. For noise points,p\_noise\(\)shows which noise labels are least convincing, that is, which points lie in a dense region or are density\-connected to a cluster\.

```
s  <- disco_samples(X, labels)
nz <- p_noise(X, labels)
noise <- data.frame(point = which(labels == -1),
                    p_sparse = nz$p_sparse, p_far = nz$p_far)
head(noise[order(pmin(noise$p_sparse, noise$p_far)), ], 3)
```

```
#>    point     p_sparse        p_far
#> 1    117 -0.025553586 -0.025553586
#> 31   638 -0.005671184 -0.005671184
#> 2    347  0.025974304  0.025974304
```

For these points the two components coincide: this happens when the dc\-distance from a noise point to the closest cluster equals its own core distance, so that both scores compare the same quantities\.

Figure 1:Pointwise DISCO scores of the HDBSCAN clustering\. Colours run from red \(score−1\-1\) through yellow \(00\) to blue \(\+1\+1\), so light\-blue points are well placed and yellowish points are borderline; crosses mark points labelled as noise\.
## 5Implementation: DISCO without an n\-by\-n matrix

### 5\.1Key observation

Sort then−1n\-1edges of the MST by increasing weight and add them one at a time, merging the two groups of points they connect \(Kruskal order\([Kruskal, 1956](https://arxiv.org/html/2611.25114#bib.bib12)\)\)\. This produces the single\-linkage dendrogram of the mutual\-reachability graph\([Gower and Ross, 1969](https://arxiv.org/html/2611.25114#bib.bib10)\): a binary tree whosennleaves are the points and whosen−1n\-1internal nodes are the merges, each with heightwvw\_\{v\}equal to the weight of the corresponding edge\.

Lemma\.For two pointsx≠yx\\neq y,dd​c​\(x,y\)=wvd\_\{dc\}\(x,y\)=w\_\{v\}, wherevvis the lowest common ancestor ofxxandyyin the merge tree\.

*Proof\.*The MST path betweenxxandyyis unique, andxxandyyend up in the same group exactly when the last edge of that path is added\. Since edges are added in increasing order, this is the largest edge on the path, which isdd​c​\(x,y\)d\_\{dc\}\(x,y\), and it is the edge that createsvv\.□\\square

Now fix a pointxxand letv1,…,vrv\_\{1\},\\dots,v\_\{r\}be its ancestors, from its parent up to the root, andsks\_\{k\}the child ofvkv\_\{k\}that does*not*containxx\. The sets of leaves belows1,…,srs\_\{1\},\\dots,s\_\{r\}partitionX∖\{x\}X\\setminus\\\{x\\\}, and by the Lemma every point belowsks\_\{k\}is at dc\-distance exactlywvkw\_\{v\_\{k\}\}fromxx\. As in the definition, the MST and the merge tree are built over allnnpoints, noise included; noise points only affect which leaves are counted\. WritingcC​\(s\)c\_\{C\}\(s\)for the number of points of clusterCCbelow nodess, we obtain

SC​\(x\)=∑y∈Cdd​c​\(x,y\)=∑k=1rwvk​cC​\(sk\),mC​\(x\)=min⁡\{wvk:cC​\(sk\)\>0\}\.S\_\{C\}\(x\)=\\sum\_\{y\\in C\}d\_\{dc\}\(x,y\)=\\sum\_\{k=1\}^\{r\}w\_\{v\_\{k\}\}\\,c\_\{C\}\(s\_\{k\}\),\\qquad m\_\{C\}\(x\)=\\min\\\{w\_\{v\_\{k\}\}:c\_\{C\}\(s\_\{k\}\)\>0\\\}\.Both quantities satisfy a simple recursion from the root down: for a nodeuuwith parentvvand siblingss,

SC​\(u\)=SC​\(v\)\+wv​cC​\(s\),mC​\(u\)=\{min⁡\{mC​\(v\),wv\}if​cC​\(s\)\>0,mC​\(v\)otherwise,S\_\{C\}\(u\)=S\_\{C\}\(v\)\+w\_\{v\}\\,c\_\{C\}\(s\),\\qquad m\_\{C\}\(u\)=\\begin\{cases\}\\min\\\{m\_\{C\}\(v\),w\_\{v\}\\\}&\\text\{if \}c\_\{C\}\(s\)\>0,\\\\ m\_\{C\}\(v\)&\\text\{otherwise,\}\\end\{cases\}withSC​\(root\)=0S\_\{C\}\(\\text\{root\}\)=0andmC​\(root\)=∞m\_\{C\}\(\\text\{root\}\)=\\infty\. The same recursion with the number of noise points belowssgives the dc\-distance to the closest noise point, needed in the one\-cluster case\. Sincedd​c​\(x,x\)=0d\_\{dc\}\(x,x\)=0,a⁡\(x\)=SC​\(x\)/\(\|C\|−1\)a\(x\)=S\_\{C\}\(x\)/\(\|C\|\-1\)andb⁡\(x\)b\(x\)follows fromSC′​\(x\)/\|C′\|S\_\{C^\{\\prime\}\}\(x\)/\|C^\{\\prime\}\|; the noise scores usemC​\(x\)m\_\{C\}\(x\)and the core distances\. Every term of DISCO is therefore available without forming a single dc\-distance explicitly\.

### 5\.2Algorithm and complexity

The complete procedure is summarised below; internal nodes of the merge tree are numberedn\+1,…,2​n−1n\+1,\\dots,2n\-1in the order in which they are created, so that every parent has a larger number than its children\.

```
Input : X (n x p), labels (clusters 1..K, noise -1), mu >= 2
Output: pointwise DISCO scores rho(x_1), ..., rho(x_n)

 1  handle edge cases (i) all noise and (ii) one cluster without noise
 2  kappa  <- core distances (distance to the (mu-1)-th other point)
 3  E      <- Prim MST of d_m, computing d_m(x_i, x_j) when needed
 4  sort E by weight; build the merge tree with union-find:
        each edge (i, j, w) creates node v with children
        root(i), root(j) and height w_v = w
 5  bottom-up (v = n+1, ..., 2n-1):
        c_C(v) <- c_C(left) + c_C(right)   for every cluster C
        z(v)   <- z(left)   + z(right)       (number of noise points)
 6  top-down (v = 2n-1, ..., n+1), for both children u of v, sibling s:
        S_C(u) <- S_C(v) + w_v * c_C(s)
        m_C(u) <- min(m_C(v), w_v)  if c_C(s) > 0, else m_C(v)
        m_N(u) <- min(m_N(v), w_v)  if z(s)   > 0, else m_N(v)
 7  cluster points: a = S_own / (|own| - 1),
        b = min_C S_C / |C|   (or m_N in the one-cluster case (iv)),
        rho = (b - a) / max(a, b);  singleton clusters -> 0      (iii)
 8  noise points: rho = min(rho_sparse(kappa), rho_far(m_C, kappa))
 9  set fractions with a zero denominator to 0                    (v)
```

Step 2 uses[FNN](https://cran.r-project.org/package=FNN)\. Step 3 is Prim’s algorithm\([Prim, 1957](https://arxiv.org/html/2611.25114#bib.bib11)\)written in C\+\+ via[Rcpp](https://cran.r-project.org/package=Rcpp); it evaluatesdm​\(xi,xj\)d\_\{m\}\(x\_\{i\},x\_\{j\}\)on the fly and needsO⁡\(n2​p\)O\(n^\{2\}p\)time andO⁡\(n\)O\(n\)memory\. Step 4 uses union by size\([Tarjan, 1975](https://arxiv.org/html/2611.25114#bib.bib13)\)and takesO⁡\(n​log⁡n\)O\(n\\log n\)time\. Steps 5 and 6 are written in R with vectorised operations onK×\(2​n−1\)K\\times\(2n\-1\)matrices and takeO⁡\(n​K\)O\(nK\)time and memory\.[Beer et al\. \(2026\)](https://arxiv.org/html/2611.25114#bib.bib1)state an overall complexity ofO⁡\(n2\)O\(n^\{2\}\)for DISCO, which this algorithm does not change: the running time is still dominated by the spanning tree\. What changes is the memory, which drops fromO⁡\(n2\)O\(n^\{2\}\)toO⁡\(n⁡\(p\+K\)\)O\(n\(p\+K\)\), and the constant factor, since non×nn\\times nmatrix has to be allocated, filled or traversed\. The result is exact: the only differences to a matrix\-based computation come from adding the same distances in a different order\.

### 5\.3Changes in version 0\.2\.0 and testing

disco\_score\(\)anddisco\_samples\(\)use the merge\-tree algorithm\.compute\_dc\_distances\(\), which by definition returns ann×nn\\times nmatrix, no longer builds the mutual\-reachability matrix and fills the dc\-distance matrix block by block in Kruskal order instead of running a breadth\-first search from every point, andp\_cluster\(\)is vectorised as a single matrix product\. The interface is unchanged\.

Tests\.The test suite contains the functions of version 0\.1\.1 as a reference, with a single change: points in singleton clusters score00, as explained below, so that both versions follow the published definition\. It compares the values returned by all exported functions over random configurations: one to eight dimensions,μ\\mufrom 2 to 10, with and without noise, singleton clusters, one cluster plus noise, mostly\-noise labellings and random labels\. All agree to within10−1010^\{\-10\}; observed differences are of the order of10−1510^\{\-15\}\.

Singleton clusters\.The DISCO definition assigns score00to points in singleton clusters\([Beer et al\., 2026](https://arxiv.org/html/2611.25114#bib.bib1), Section 3\.1\), as does the silhouette function of scikit\-learn used by the reference implementation\. Version 0\.1\.1 seta⁡\(x\)=0a\(x\)=0for such points and therefore returned11\. Version 0\.2\.0 follows the definition; labellings without singleton clusters are unaffected\.

## 6Performance

### 6\.1Comparison with the previous version

Setup\.We compared[discoCVI](https://cran.r-project.org/package=discoCVI)0\.1\.1 \(from CRAN\) and 0\.2\.0 on synthetic data: three Gaussian clusters in two dimensions plus 5% uniform noise, labelled with the generating labels so that only DISCO is measured, withnnfrom 500 to 100,000 andμ=5\\mu=5\. Version 0\.1\.1 was run up ton=4,000n=4\{,\}000, beyond which it does not fit comfortably in memory\. Every measurement was a separateRscriptprocess\. Peak memory is the maximum resident set size of the process \(reported by/usr/bin/time \-l\), which includes R itself \(about 67 MB\) and the C\+\+ code\. Energy was measured with CodeCarbon\([Courty et al\., 2026](https://arxiv.org/html/2611.25114#bib.bib20)\)around the whole process, and the median energy of a baseline process that generates the data without computing DISCO was subtracted\. Each configuration was run five times in random order, after a warm\-up; we report medians\. Both versions returned identical scores for everynn\. The machine was a 2023 MacBook Pro with an Apple M2 Pro chip and 16 GB of memory, running macOS 27, R 4\.5\.3,[FNN](https://cran.r-project.org/package=FNN)1\.1\.4\.1,[Rcpp](https://cran.r-project.org/package=Rcpp)1\.1\.2 and CodeCarbon 3\.2\.8 \(Python 3\.10\), using a single thread\.

Table 1:Median DISCO computation time, peak memory of the R process, and energy above the baseline, over five runs\. Version 0\.1\.1 was not run beyond 4,000 points\.Time\.Version 0\.2\.0 is 23 times faster atn=500n=500and 138 times faster atn=4,000n=4\{,\}000\(Table[1](https://arxiv.org/html/2611.25114#S6.T1), Figure[2](https://arxiv.org/html/2611.25114#S6.F2)\)\. Both versions scale roughly quadratically; fitted log\-log slopes are 2\.1 for version 0\.1\.1 \(500 to 4,000 points\) and 1\.9 for version 0\.2\.0 \(8,000 to 100,000 points\)\. The gain is a much smaller constant, not a lower complexity class: 100,000 points take about 50 seconds\.

Figure 2:Time to compute the DISCO score as a function of the number of points \(log\-log scale\)\. Points are medians and bars the range over five runs\.Memory\.The memory of version 0\.1\.1 grows rapidly, from 118 MB atn=500n=500to 1,222 MB atn=4,000n=4\{,\}000\. Version 0\.2\.0 stays within about 30 MB of R’s own footprint up ton=8,000n=8\{,\}000and needs 198 MB in total atn=100,000n=100\{,\}000\(Figure[3](https://arxiv.org/html/2611.25114#S6.F3)\)\.

Figure 3:Peak memory \(maximum resident set size\) of the whole R process; the dashed line marks the memory used by R itself\. Points are medians and bars the range over five runs\.Energy\.Atn=4,000n=4\{,\}000, one evaluation used 44\.9 mWh with version 0\.1\.1 and 0\.26 mWh with version 0\.2\.0 \(Figure[4](https://arxiv.org/html/2611.25114#S6.F4)\)\. For long runs the average power was similar for both versions \(about 8 W\), so the energy saving follows the time saving\. For the same energy budget of about 45 mWh, version 0\.1\.1 scores 4,000 points and version 0\.2\.0 scores 64,000\. Energy values for runs shorter than a fraction of a second are close to the resolution of software\-based measurement and should be read as indicative only\.

Figure 4:Energy per DISCO evaluation measured with CodeCarbon, minus the baseline process \(log\-log scale\)\. The dashed line marks the energy of version 0\.1\.1 at 4,000 points, which version 0\.2\.0 reaches only at 64,000 points\.
### 6\.2Comparison with the reference implementation

We also ran the original Python implementation of[Beer et al\. \(2026\)](https://arxiv.org/html/2611.25114#bib.bib1)and[discoCVI](https://cran.r-project.org/package=discoCVI)0\.2\.0 on the same data files \(the same generator as above, withnnfrom 500 to 8,000, plus one dataset of 500 points that contains a singleton cluster\), each in its own process, three times per dataset\. Only the DISCO computation was timed; peak memory is again the maximum resident set size of the whole process\. The reference code uses three functions from scikit\-learn, whose compiled dependencies could not be loaded on macOS 27; we replaced them by NumPy implementations of the same formulas, which agreed with scikit\-learn to within3×10−153\\times 10^\{\-15\}on test data on a system where scikit\-learn runs\. All code specific to DISCO was the authors’ original\.

Table 2:Original Python implementation versus discoCVI 0\.2\.0 on identical data: median time of the DISCO computation, peak memory of the whole process, and the largest absolute difference between the pointwise scores\.The pointwise scores of the two implementations agree to within3×10−133\\times 10^\{\-13\}on every dataset \(Table[2](https://arxiv.org/html/2611.25114#S6.T2)\), including the dataset with a singleton cluster \(7×10−147\\times 10^\{\-14\}\), which confirms the correction described above\.[discoCVI](https://cran.r-project.org/package=discoCVI)is 2\.9 times faster atn=500n=500and 8\.7 times faster atn=8,000n=8\{,\}000\. The memory of the Python implementation grows withn2n^\{2\}and reaches 1\.1 GB atn=8,000n=8\{,\}000, whereas[discoCVI](https://cran.r-project.org/package=discoCVI)needs 96 MB, most of which is R itself\.

### 6\.3Limitations

The running time is quadratic innn, so very large datasets \(several hundred thousand points\) remain slow even though memory is no longer a constraint\. The package uses a single thread\. DISCO is defined for any dissimilarity\([Beer et al\., 2026](https://arxiv.org/html/2611.25114#bib.bib1)\), whereas[discoCVI](https://cran.r-project.org/package=discoCVI)currently supports Euclidean distances on numeric data; since the merge\-tree passes need only the spanning tree, other dissimilarities would only require a different spanning\-tree step\. The benchmarks were run on one machine with synthetic two\-dimensional data, and energy was measured in software, so absolute numbers depend on hardware; the comparisons are nevertheless paired \(same data, same machine, interleaved runs\), and the equality of the scores is verified by the test suite rather than by the benchmarks alone\.

## 7Discussion

The merge\-tree formulation removes the memory barrier of DISCO and makes the index practical for datasets of tens of thousands of points on a laptop, with results that match both the previous version and the original implementation\. In parameter searches the savings multiply: scoring 20 candidate clusterings of 4,000 points takes about six minutes and 0\.9 Wh with version 0\.1\.1, and about three seconds and 5 mWh with version 0\.2\.0\.

The remaining cost is the quadratic minimum spanning tree\. In low dimensions, dual\-tree Borůvka algorithms compute the Euclidean MST in close toO⁡\(n​log⁡n\)O\(n\\log n\)time\([March et al\., 2010](https://arxiv.org/html/2611.25114#bib.bib14)\)and are used to accelerate HDBSCAN\([McInnes and Healy, 2017](https://arxiv.org/html/2611.25114#bib.bib15)\); the same idea applies to mutual\-reachability distances and would combine directly with the merge\-tree passes described here\. When DISCO is computed for an HDBSCAN result with the same value ofμ\\mu, the spanning tree built by the clustering itself could also be reused\. Both are planned for future versions\.

## 8Summary

[discoCVI](https://cran.r-project.org/package=discoCVI)provides the DISCO index in R through a small interface of plain functions that works with labels from any clustering algorithm\. Since version 0\.2\.0 it computes DISCO exactly from the merge tree of the mutual\-reachability minimum spanning tree, without storing anyn×nn\\times nmatrix\. It agrees with the original Python implementation, follows the published definition for singleton clusters, is up to two orders of magnitude faster than its previous version and up to nine times faster than the reference implementation, and scores 100,000 points in under a minute with less than 200 MB of memory\. The package is available from CRAN; the benchmark scripts and data are in its source repository at[https://github\.com/aminentezari/discoCVI](https://github.com/aminentezari/discoCVI)\.

## Acknowledgements

The author thanks Anna Beer, Lena Krieger and Pascal Weber for the original Python implementation of DISCO, and Davide Chicco for supervising the development of version 0\.1 of[discoCVI](https://cran.r-project.org/package=discoCVI)\.

## References

- A\. Beer, A\. Draganov, E\. Hohma, P\. Jahn, C\. M\. M\. Frey, and I\. AssentConnecting the dots – density\-connectivity distance unifies DBSCAN, k\-center and spectral clustering\.InProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 80–92\.External Links:[Document](https://dx.doi.org/10.1145/3580305.3599283)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p3.1),[§2](https://arxiv.org/html/2611.25114#S2.p2.2)\.
- Beeret al\.\(2026\)A\. Beer, L\. Krieger, P\. Weber, M\. Ritzert, I\. Assent, and C\. PlantInternal evaluation of density\-based clusterings with noise\.InThe Fourteenth International Conference on Learning Representations \(ICLR\),External Links:[Link](https://openreview.net/forum?id=izbBFuHtAX)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p1.1),[§2](https://arxiv.org/html/2611.25114#S2.p1.1),[§2](https://arxiv.org/html/2611.25114#S2.p6.1),[§5\.2](https://arxiv.org/html/2611.25114#S5.SS2.p3.1),[§5\.3](https://arxiv.org/html/2611.25114#S5.SS3.p3.1),[§6\.2](https://arxiv.org/html/2611.25114#S6.SS2.p1.1),[§6\.3](https://arxiv.org/html/2611.25114#S6.SS3.p1.1)\.
- Beygelzimeret al\.\(2024\)A\. Beygelzimer, S\. Kakadet, J\. Langford, S\. Arya, D\. Mount, and S\. LiFNN: fast nearest neighbor search algorithms and applications\.Note:R package version 1\.1\.4\.1External Links:[Document](https://dx.doi.org/10.32614/CRAN.package.FNN),[Link](https://cran.r-project.org/package=FNN)Cited by:[§3](https://arxiv.org/html/2611.25114#S3.p5.1)\.
- Campelloet al\.\(2013\)R\. J\. G\. B\. Campello, D\. Moulavi, and J\. SanderDensity\-based clustering based on hierarchical density estimates\.InAdvances in Knowledge Discovery and Data Mining \(PAKDD\),Lecture Notes in Computer Science, Vol\.7819,pp\. 160–172\.External Links:[Document](https://dx.doi.org/10.1007/978-3-642-37456-2%5F14)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p1.1),[§2](https://arxiv.org/html/2611.25114#S2.p2.1)\.
- Chiccoet al\.\(2025\)D\. Chicco, G\. Sabino, L\. Oneto, and G\. JurmanThe DBCV index is more informative than DCSI, CDbw, and VIASCKDE indices for unsupervised clustering internal assessment of concave\-shaped and density\-based clusters\.PeerJ Computer Science11,pp\. e3095\.External Links:[Document](https://dx.doi.org/10.7717/peerj-cs.3095)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p2.1)\.
- Courtyet al\.\(2026\)B\. Courty, V\. Schmidt, S\. Luccioni,et al\.CodeCarbon: estimate and track carbon emissions from machine learning computing\.Note:Python package version 3\.2\.8External Links:[Document](https://dx.doi.org/10.5281/zenodo.20584960),[Link](https://github.com/mlco2/codecarbon)Cited by:[§6\.1](https://arxiv.org/html/2611.25114#S6.SS1.p1.1)\.
- Eddelbuettel and François \(2011\)D\. Eddelbuettel and R\. FrançoisRcpp: seamless R and C\+\+ integration\.Journal of Statistical Software40\(8\),pp\. 1–18\.External Links:[Document](https://dx.doi.org/10.18637/jss.v040.i08)Cited by:[§3](https://arxiv.org/html/2611.25114#S3.p5.1)\.
- Entezari \(2026\)A\. EntezaridiscoCVI: implementation of the DISCO metric for internal clustering evaluation\.Note:R package version 0\.2\.1External Links:[Link](https://cran.r-project.org/package=discoCVI)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p2.1)\.
- Esteret al\.\(1996\)M\. Ester, H\. Kriegel, J\. Sander, and X\. XuA density\-based algorithm for discovering clusters in large spatial databases with noise\.InProceedings of the Second International Conference on Knowledge Discovery and Data Mining \(KDD\),pp\. 226–231\.External Links:[Link](https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p1.1)\.
- Gower and Ross \(1969\)J\. C\. Gower and G\. J\. S\. RossMinimum spanning trees and single linkage cluster analysis\.Journal of the Royal Statistical Society\. Series C \(Applied Statistics\)18\(1\),pp\. 54–64\.External Links:[Document](https://dx.doi.org/10.2307/2346439)Cited by:[§5\.1](https://arxiv.org/html/2611.25114#S5.SS1.p1.1)\.
- Hahsleret al\.\(2019\)M\. Hahsler, M\. Piekenbrock, and D\. Dorandbscan: fast density\-based clustering with R\.Journal of Statistical Software91\(1\),pp\. 1–30\.External Links:[Document](https://dx.doi.org/10.18637/jss.v091.i01)Cited by:[§3](https://arxiv.org/html/2611.25114#S3.p1.1)\.
- Hu \(1961\)T\. C\. HuThe maximum capacity route problem\.Operations Research9\(6\),pp\. 898–900\.External Links:[Document](https://dx.doi.org/10.1287/opre.9.6.898)Cited by:[§2](https://arxiv.org/html/2611.25114#S2.p2.2)\.
- Kruskal \(1956\)J\. B\. KruskalOn the shortest spanning subtree of a graph and the traveling salesman problem\.Proceedings of the American Mathematical Society7\(1\),pp\. 48–50\.External Links:[Document](https://dx.doi.org/10.1090/S0002-9939-1956-0078686-7)Cited by:[§5\.1](https://arxiv.org/html/2611.25114#S5.SS1.p1.1)\.
- Lannelongueet al\.\(2021\)L\. Lannelongue, J\. Grealey, and M\. InouyeGreen algorithms: quantifying the carbon footprint of computation\.Advanced Science8\(12\),pp\. 2100707\.External Links:[Document](https://dx.doi.org/10.1002/advs.202100707)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p3.1)\.
- Marchet al\.\(2010\)W\. B\. March, P\. Ram, and A\. G\. GrayFast Euclidean minimum spanning tree: algorithm, analysis, and applications\.InProceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 603–612\.External Links:[Document](https://dx.doi.org/10.1145/1835804.1835882)Cited by:[§7](https://arxiv.org/html/2611.25114#S7.p2.1)\.
- McInnes and Healy \(2017\)L\. McInnes and J\. HealyAccelerated hierarchical density based clustering\.In2017 IEEE International Conference on Data Mining Workshops \(ICDMW\),pp\. 33–42\.External Links:[Document](https://dx.doi.org/10.1109/ICDMW.2017.12)Cited by:[§7](https://arxiv.org/html/2611.25114#S7.p2.1)\.
- Moulaviet al\.\(2014\)D\. Moulavi, P\. A\. Jaskowiak, R\. J\. G\. B\. Campello, A\. Zimek, and J\. SanderDensity\-based clustering validation\.InProceedings of the 2014 SIAM International Conference on Data Mining,pp\. 839–847\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611973440.96)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p1.1)\.
- Pedregosaet al\.\(2011\)F\. Pedregosa, G\. Varoquaux, A\. Gramfort,et al\.Scikit\-learn: machine learning in Python\.Journal of Machine Learning Research12,pp\. 2825–2830\.External Links:[Link](https://jmlr.org/papers/v12/pedregosa11a.html)Cited by:[§2](https://arxiv.org/html/2611.25114#S2.p4.3)\.
- Prim \(1957\)R\. C\. PrimShortest connection networks and some generalizations\.Bell System Technical Journal36\(6\),pp\. 1389–1401\.External Links:[Document](https://dx.doi.org/10.1002/j.1538-7305.1957.tb01515.x)Cited by:[§5\.2](https://arxiv.org/html/2611.25114#S5.SS2.p3.1)\.
- Rousseeuw \(1987\)P\. J\. RousseeuwSilhouettes: a graphical aid to the interpretation and validation of cluster analysis\.Journal of Computational and Applied Mathematics20,pp\. 53–65\.External Links:[Document](https://dx.doi.org/10.1016/0377-0427%2887%2990125-7)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p1.1)\.
- Schwartzet al\.\(2020\)R\. Schwartz, J\. Dodge, N\. A\. Smith, and O\. EtzioniGreen AI\.Communications of the ACM63\(12\),pp\. 54–63\.External Links:[Document](https://dx.doi.org/10.1145/3381831)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p3.1)\.
- Strubellet al\.\(2019\)E\. Strubell, A\. Ganesh, and A\. McCallumEnergy and policy considerations for deep learning in NLP\.InProceedings of the 57th Annual Meeting of the Association for Computational Linguistics,pp\. 3645–3650\.External Links:[Document](https://dx.doi.org/10.18653/v1/P19-1355)Cited by:[§1](https://arxiv.org/html/2611.25114#S1.p3.1)\.
- Tarjan \(1975\)R\. E\. TarjanEfficiency of a good but not linear set union algorithm\.Journal of the ACM22\(2\),pp\. 215–225\.External Links:[Document](https://dx.doi.org/10.1145/321879.321884)Cited by:[§5\.2](https://arxiv.org/html/2611.25114#S5.SS2.p3.1)\.

相似文章

谱聚类层次与密度聚类层次的拓扑等价性

arXiv cs.LG

这篇 arXiv 论文证明了在何种条件下,基于扩散距离构建的谱单链接层次聚类在合并高度的单调重标度意义下,与密度聚类树拓扑等价,并给出了一个关于有限样本 k-NN 图的结果。

Flash-GMM:一种用于可扩展软聚类的内存高效内核

Hugging Face Daily Papers

Flash-GMM 引入了一个用于高斯混合模型的融合Triton内核,实现了20倍加速,并能在单个GPU上训练比之前大100倍的数据集,使软聚类成为近似最近邻搜索中k-means的可行替代方案。