DelTriC: A Novel Clustering Method with Accurate Outlier

AI summary

Overview

Research area: Unsupervised machine learning, specifically clustering and anomaly (outlier) detection on high-dimensional data.

Technical level: Intermediate. The paper is readable without deep math background, but the algorithm description uses geometry and statistics notation (Delaunay triangulation, z-scores, Median Absolute Deviation, geodesic distance) and several appendices that derive a theoretical motivation.

Scope (one sentence): The paper introduces DelTriC, a clustering algorithm that triangulates a 2-D projection of the data, then evaluates and prunes the triangulation in the original high-dimensional space to produce clusters and to flag outliers.

What This Paper Is About

Clustering algorithms tend to trade speed against accuracy: centroid methods such as k-means only handle convex, blob-like clusters and need the number of clusters given in advance, while density methods such as DBSCAN and HDBSCAN handle irregular shapes but are sensitive to parameters and become slow or unreliable in high dimensions. A common workaround, reducing dimensionality before clustering, can hide structure that only exists in the full-dimensional representation — including outliers that end up sitting inside a cluster after projection.

The paper's goal is an algorithm that keeps the speed of working in a 2-D projection while making the actual clustering decisions using distances measured in the original high-dimensional space, and that detects outliers as a by-product rather than as an afterthought.

Key Contributions

1. The DelTriC algorithm (Delaunay Triangulation Clustering), which combines PCA or UMAP projection, Delaunay triangulation, statistical edge pruning, centroid-based merging, and anomaly detection into one pipeline. It decouples neighborhood construction (done in the 2-D proxy) from decision-making (done in the original space).

2. A back-projection mechanism, which the authors describe as the principal innovation: triangles are built in the low-dimensional projection, but edge lengths and triangle sizes are re-measured in the original high-dimensional space, so spurious connections that appear short only because of projection compression can still be removed.

3. Median/MAD normalization inside the edge-pruning step. Triangle sizes are standardized using the median and Median Absolute Deviation, then thresholded with a mean-plus-sigma rule, θ = μ + σ_f · σ. The authors state that this particular combination has not previously been applied in this context.

4. An integrated anomaly-handling stage: clusters whose size is at or below τ (typically τ = 2 or 3) are treated as anomalies, then scored against each cluster via S(C_j | A) = (μ/n) Σ_{p∈A} Σ_{q∈C_j} 1/d_pq and merged only if the score exceeds a sensitivity threshold δ; otherwise points keep label −1.

Main Findings

• Synthetic clustering is competitive, and strongest in high dimensions. On synthetic data (n_points of 500, 5000, 10000; dimensions 5, 20, 50; scored with ARI | NMI), DelTriC reached 0.81 | 0.82 at n = 10000 and dim = 50, versus 0.70 | 0.71 for DBSCAN and 0.70 | 0.72 for HDBSCAN, and 0.73 | 0.77 versus 0.57 | 0.63 (DBSCAN) and 0.61 | 0.66 (HDBSCAN) at n = 5000, dim = 50. KMeans beat the others on some small-sample, high-dimension cases (0.85 | 0.85 at 500 points and dim = 50).

• Anomaly detection on synthetic data is the clearest win. Reported F1 scores for the anomaly class show DelTriC at 0.42–0.82 across all nine synthetic benchmarks, against 0.14–0.34 for DBSCAN and 0.16–0.35 for HDBSCAN. The largest gap appears at n = 5000, dim = 50: 0.82 (DelTriC) versus 0.30 (DBSCAN) and 0.35 (HDBSCAN).

• On real-world data, DelTriC is broadly comparable to density-based methods. Across AG News, CIFAR-10, CLINC, DBPedia-14, Emotion, MNIST, PBMC and PBMC Louvain, DelTriC was statistically close to DBSCAN and HDBSCAN. Examples: CIFAR-10 0.73 | 0.76 for DelTriC versus 0.72 | 0.76 (DBSCAN) and 0.71 | 0.75 (HDBSCAN); MNIST 0.83 | 0.83 versus 0.85 | 0.84 (DBSCAN) and 0.78 | 0.80 (HDBSCAN); PBMC 0.49 | 0.56 versus 0.52 | 0.60 (DBSCAN) and 0.51 | 0.63 (HDBSCAN).

• KMeans is strong where clusters are already blob-like. The authors note that KMeans scores well on AG News (0.63 | 0.59) and DBPedia-14 (0.74 | 0.81), which they interpret as evidence that those embedding spaces contain relatively well-separated, blob-like clusters where advanced methods mainly add the convenience of not needing the cluster count.

• Anomaly counts explain part of the ranking. Anomaly counts on real-world data vary widely by method — for example MNIST: 286 (DBSCAN), 291 (DelTriC), 922 (HDBSCAN); Emotion: 485, 263, 519. The paper states that detecting fewer anomalies mechanically yields higher ARI/NMI on datasets where anomalies are unlabeled, and that HDBSCAN often performs worse because it labels a large share of the data as anomalous.

• DelTriC is more stable under anomaly enrichment. On MNIST variants with anomalies injected, DBSCAN and HDBSCAN degraded noticeably relative to the baseline (ARI ≈ 0.8) — for example DBSCAN at 0.56 | 0.72 on rotated images while DelTriC reached 0.75 | 0.76 — whereas DelTriC stayed comparatively stable.

• Anomaly-detection precision and recall remain low overall. The paper attributes this to CLIP embeddings being largely invariant to the applied transformations and to natural anomalies present in MNIST before enrichment. DelTriC still outperformed HDBSCAN on most transformation types; on the News20 outlier task, DelTriC had precision 0.57, recall 0.17, F1 0.27, while HDBSCAN had 0.45 | 0.23 | 0.31 and DBSCAN 0.48 | 0.24 | 0.32.

• Ablation supports keeping all components. The ablation (on CIFAR-10, DBpedia-14 and MNIST) found that disabling back-projection slightly improved ARI/NMI on MNIST but that the difference is not statistically significant; on CIFAR-10 and especially DBpedia-14, every ablated variant was markedly worse, which the authors read as evidence that all components are needed. The complete Table 9 values are not included in the provided text.

• Pruning degrades when manifolds nearly touch. A controlled demo with average intra-manifold edge length of 0.88 shows DelTriC still works at inter-manifold distance ε ≈ 1.0, but progressively retains inter-manifold edges as ε shrinks.

• Reported complexity: approximately O(d²n) + O(n log n) in its default form, comprising O(d²n) for PCA (worst case, not optimized), O(dn²) for UMAP (worst case, not optimized), O(n log n) for 2-D Delaunay triangulation, and O(d · n) for back-projection and triangle filtering. Quantitative runtime comparisons are referenced to Appendix H, which is not part of the provided text.

Methodology in Plain English

1. Project. Take the high-dimensional dataset and flatten it to two dimensions using PCA or UMAP. This is only used as an index of "who is next to whom" — not as the space where decisions are made.

2. Triangulate. Connect the 2-D points with a Delaunay triangulation, which links each point to its natural neighbors and produces a mesh of triangles.

3. Measure back in the original space. For every triangle, compute its edge lengths both in the projection and in the original high-dimensional data. A triangle's size is the longest of its edges (sum or shortest mutual distance are noted as alternatives).

4. Prune. Normalize triangle sizes with the median and MAD to get z-scores, set a cutoff θ = μ + σ_f · σ from the mean and standard deviation of those z-scores, and keep a triangle only if both its original-space and projection z-scores are at or below θ. Discarded triangles remove their edges; whatever connected components remain are the initial clusters. The double condition is what lets the method preserve the manifold while still exposing oversized triangles that signal anomalous points.

5. Merge conservatively. Pick one representative point per cluster (the member nearest the projected mean), triangulate the representatives, prune again, and merge clusters still connected by surviving edges. The paper reports that this step typically merges only a few closely related subclusters rather than aggressively collapsing clusters.

6. Handle anomalies. Clusters with at most τ members (typically 2 or 3) are treated as anomalies. Each anomaly is scored against each cluster using distances that combine the original and projected spaces, scaled by α = median(s_proj)/median(s); it is absorbed into the best-scoring cluster only if that score exceeds δ. Unmerged points are labeled −1.

7. Test. Synthetic data are built from sklearn.datasets.make_blobs with Gaussian blobs, plus one irregular "snake" cluster generated from a sinusoid (about 20% of points), plus uniformly scattered anomalies labeled −1; blob spread is scaled as cluster_std = overlap × sqrt(n_dim) × 2.0. Real-world data span text (DBPedia-14, Emotion, AG News, News20, CLINC OOS) with all-MiniLM-L6-v2 embeddings, images (CIFAR-10, MNIST) with CLIP (ViT-B/32), and one numerical dataset (PBMC). Hyperparameters were tuned with Optuna using the Tree-structured Parzen Estimator rather than fixed grids; clustering is scored with ARI and NMI and anomaly detection with F1 on the anomaly class.

A discrepancy worth noting: the real-world section names the five compared methods as DelTriC, HDBSCAN, KMeans, MiniBatchKMeans and Spectral Clustering, but Tables 5 and 6 report columns for DBSCAN, DelTriC, HDBSCAN, KMeans and Spectral Clustering. The provided text does not reconcile this.

Why This Matters

Clustering is usually evaluated with the cluster-count assumption already fixed or with outliers excluded from the benchmark, so papers that combine clustering quality with honest outlier detection address a real gap. The paper argues that none of the existing triangulation-based methods it reviews (nDTAg, Qiu & Li's descending clustering, Adaptive DPC-DG, DTSCAN) explicitly targets anomaly-detection quality alongside clustering, which is why the authors do not run a direct numerical comparison against them — they state such a comparison would be misleading.

Real-world applications:

• Document and news organization: clustering text embeddings (AG News, DBPedia-14, News20, CLINC OOS) while surfacing documents that do not belong to any topic, which is exactly the "outlier title" scenario tested on News20.
• Image dataset curation: grouping CIFAR-10 or MNIST-style image embeddings while separating corrupted or transformed images (blur, occlusion, noise, rotation).
• Single-cell and biomedical analysis: the PBMC dataset tests use case is clustering cell populations while flagging unusual cells.
• Anomaly triage in embedded and streaming settings: the O(d²n) + O(n log n) profile and the option of a fast 2-D triangulation suggest use where HDBSCAN's overhead is prohibitive.

Industry relevance: the practical appeal is the ability to keep the speed of a 2-D projection while making separation decisions with full-dimensional distances, and to get outlier labels without a separate detection pipeline. The back-projection idea is also presented as potentially useful outside clustering.

Future Directions

1. Lift the 2-D constraint. The authors note that DelTriC is restricted to a 2-D UMAP projection (with possible extension to 3 dimensions), whereas DBSCAN and HDBSCAN were given 10-dimensional UMAP projections; they acknowledge that some datasets have 2-D manifolds for which a 10-D projection may actually reconstruct structure less faithfully.

2. Fix pruning degradation. Appendix C shows the pruning step progressively fails to remove inter-manifold edges once manifolds are closer than typical intra-manifold point distances; a principled fix is left open.

3. Push back-projection beyond clustering. The conclusion explicitly suggests the back-projection technique may have applications outside the clustering domain.

4. **Build better benchmarks

Authors’ abstract

The paper introduces DelTriC (Delaunay Triangulation Clustering), a clustering algorithm which integrates PCA/UMAP-based projection, Delaunay triangulation, and a novel back-projection mechanism to form clusters in the original high-dimensional space. DelTriC decouples neighborhood construction from decision-making by first triangulating in a low-dimensional proxy to index local adjacency, and then back-projecting to the original space to perform robust edge pruning, merging, and anomaly detection. DelTriC can outperform traditional methods such as k-means, DBSCAN, and HDBSCAN in many scenarios; it is both scalable and accurate, and it also significantly improves outlier detection.