Automatic depth-based local center clustering via $β$-integrated local depth and adaptive grouping

1. Introduction

• Clustering partitions unlabeled data into meaningful, interpretable groups and supports analysis when little or no prior knowledge is available.Applications include representation learning, pattern recognition, image analysis, and other natural sciences.Source: §1 · p. 1
• Methods from K-means and hierarchical clustering to graph-based and manifold-learning approaches often require parameter tuning or careful model selection.The passage notes this challenge as real-world data become larger and more heterogeneous.Source: §1 · p. 1
• Model and parameter selection often involve rerunning an algorithm with different settings and choosing a result according to a criterion.The supplied passage gives only a truncated example of such a criterion.Source: §1 · p. 1

1 INTRODUCTION 2

• Methods that automatically estimate cluster count and deliver high-quality results without parameter selection remain relatively limited.The introduction notes parameter-selection criteria such as the cited width measure for Kmeans and BIC for model-based clustering.Source: §1 · p. 2

1.1. Literature review

• Density-based methods handle arbitrary cluster shapes and sizes without specifying K, but typically require neighborhood or density settings; mean-shift also depends on bandwidth.NN-RMS and NN-blurring mean-shift use kNN density estimates rather than fixed bandwidths, but still require density-estimation parameters.Source: §1.1 · p. 2
• FINCH builds a parameter-free hierarchy by merging mutually closest groups or path-connected groups, but users must choose the final granularity or evaluate it post hoc.Source: §1.1 · p. 2
• Spectral methods include eigengap selection, John et al.’s multimodality-gap spectrum method, and Fan et al.’s affinity selection, which still requires K.The eigengap heuristic is less reliable for non-Gaussian structures; John et al. add a density-aware kernel and GMM on eigenvectors, while Fan et al. select affinity and hyperparameters from candidates but require the cluster count.Source: §1.1 · p. 2
• Objective-based methods accept split or merge operations that improve an objective, but their criteria generally work best for convex clusters and lack broad, efficient generality.X-means optimizes BIC but needs a cluster-count range; U-Kmeans maximizes entropy, while K∗means [24] uses minimum description length and can estimate K on large data with UMAP [25].Source: §1.1 · p. 2

1.2. Motivation and contribution

• DLCC [26] handles varied clustering challenges but requires a neighborhood size and similarity threshold, motivating a method that avoids parameter tuning and assumptions about cluster size or number.The paper identifies three linked challenges: defining exemplars without a fixed neighborhood size, measuring similarity between their point groups, and automatically determining the number of clusters or when to stop merging.Source: §1.2 · p. 3
• β-ILD [27] enables parameter-free exemplar selection across neighborhood sizes, with a representativeness ranking favoring points often central in larger neighborhoods.The ranking may also support centroid initialization in other clustering methods.Source: §1.2 · p. 3
• Inspired by PaLD, group-level local similarity (GLS) measures similarity between disjoint point groups, assigning zero to completely separated groups and remaining invariant under rotation, dilation, and shift.Source: §1.2 · p. 3
• A-DLCC adaptively merges groups using reachability in absorption or bonding modes, a depth-graph contact null-model test, and final reconsideration of small groups.The same agglomeration rule covers connected-shape and well-separated scenarios.Source: §1.2 · p. 3

• Section 5 reports satisfactory, interpretable A-DLCC results across synthetic and real datasets, and Section 6 concludes the paper and outlines future directions.Source: §2 · p. 4

2.1. Local depth and integrated local depth

• Depth generalizes median-, quantile-, and rank-like ordering to higher dimensions, while local-depth methods can use depth to define clustering exemplars.Earlier clustering work also used depth as an auxiliary tool for refining partitions.Source: §2.1 · p. 4
• For β-LD, reflect the data about x0 to form a centrally symmetric set, select the ⌈nβ⌉ highest-depth observations as its β-neighborhood, then evaluate x0 relative to those neighbors.Source: §2.1 · p. 4
• β-ILD integrates local-depth values over β ∈ (0, 1], capturing both local and global data structure without fixing a single β.Source: §2.1 · p. 4

2 PRELIMINARIES 5

• Spatial depth, computable in O(nd) time per point, supports A-DLCC’s repeated local-depth calculations across locality levels; the β-level weighting is uniform from β0 to 1.β0 is set to a small positive value to keep local depth well-defined for sample sizes larger than nβ0 and avoid instability in very small neighborhoods.Source: §2 · p. 5

2.2. DLCC algorithm

• DLCC builds a symmetric depth-similarity matrix, selects neighborhood-deepest points as local-center candidates, groups centers, assigns temporary clusters, and classifies points left unlabeled.A-DLCC modifies local-center definition and grouping and temporary-cluster construction to eliminate predefined parameters.Source: §2.2 · p. 5

2.3. Summary of notations

• The notation summary defines dataset dimensions, locality levels and depths, neighborhoods, local centers, depth-based similarities, groups, and reachable similarity.Table 1 and its accompanying text provide the symbols used in subsequent sections.Source: Table 1 · p. 6, §2.3 · p. 6

3. β-integrated local depth-based point representativeness

• β-ILD smooths local-depth fluctuations, while frequency ranks points by how often they emerge as locally deep across points and locality levels.Points consistently selected at larger locality levels receive higher frequency, yielding a natural representativeness ranking.Source: §3 · p. 7

3.1. Possible Application

• Restricting Kmedoids medoid candidates to locally deep points yields results comparable to using all cluster points.Table 2 compares the variants across five datasets; the passage reports comparability but provides no specific ARI values.Source: Table 2 · p. 7, §3.1 · p. 8
• Kmedoids initialization selects locally deep exemplars in frequency order while excluding candidates inside previously selected exemplars’ empirical β-neighborhoods; updates choose medoids by depth.Updates can select from all cluster members or restrict candidates to locally deep exemplars.Source: §3.1 · p. 8

3.2. Local centers for A-DLCC

• A local center is a locally deep point with a well-defined self centrality level that is most often locally deepest in neighborhoods it belongs to at that level.Source: §3.2 · p. 9

4.1. Group-level local similarity

• GLS is a symmetric local-similarity measure for disjoint assigned groups, and remains invariant under rotation, dilation, and translation when input similarities preserve ordinal relationships.Source: §4.1 · pp. 9–10

4.2. Adaptive grouping strategy

• Reachability and group-specific background levels set merge thresholds, adjusted for disruption so each group judges a pairwise merge from its own perspective.Source: §4.2 · pp. 11–12

4.2.1. Isolated local centers and cells without a boundary

• If local centers have no neighbors at the data-derived locality level, A-DLCC skips merging; groups without their own boundary may also be set aside and their centers demoted.Source: §4.2.1 · p. 12

4.2.2. Absorption and bonding

• Adjacent groups with one-sided reachability may undergo absorption, while mutual peers may bond; bonding must not create a weaker internal link than either group already tolerates.Source: §4.2.2 · pp. 12–13

4.2.3. Community-level contact

• A merge generally requires contact exceeding the configuration-model expectation for group size, tested between initial groups to avoid the modularity resolution limit.Source: §4.2.3 · pp. 13–14

4.2.4. Iteration and reconsideration of small groups

• Accepted merges form connected components and repeat until stable; afterward, small clusters merge only if connectivity, size, and community-contact checks pass, otherwise they remain.Absorption and bonding are decided pair by pair from the same quantities, so both can occur in one dataset.Source: §4.2.4 · p. 14

4.3. Temporary clusters

• Temporary clusters use parameter-free retained points, while singleton center groups add the eligible non-center point maximizing frequency-weighted depth to make the definition applicable.Source: §4.3 · pp. 15–16
• Temporary-cluster updates adapt the original DLCC min strategy [26], scoring points by their similarity to centers within a group versus centers outside it.The score uses the same score function and normalizes the difference between the two maximum similarities by the larger maximum.Source: §4.3 · p. 16
• Rather than specify a neighborhood size, the procedure requires each output temporary cluster to retain at least half its initial size.Singleton local-center groups are supplemented with a locally deep point having the highest Df(z | Gs) value.Source: §4.3 · p. 16
• Most points are correctly clustered, while ambiguous points—typically near cluster boundaries—remain unlabeled for later classification.Figure 4 illustrates bonding fragments of interlocked shapes in Bainba and absorption of less representative local centers in the Normal example.Source: Figure 4 · p. 16, §4.3 · pp. 16–17

5.1. Synthetic data

• On four synthetic datasets, A-DLCC performs similarly to DLCC without parameter tuning, but merges the shapes joined by Agg’s wider bridge and neither method fully separates Blend’s spirals.The wider bridge yields comparable reachable similarities and small disruption on both sides, so the bond is accepted; a local center can also form within a bridge when its neighborhood contains a balanced mix of points.Source: §5.1 · p. 17, Figure 5 · p. 17

5.2. Real data

• The real-data evaluation covers eight datasets, including six widely used UCI clustering benchmarks and Yale-B face images and Optidigits handwritten digits.Yale-B contains 2,000 images of 10 individuals, compressed to 30 × 20 pixels.Source: §5.2 · pp. 17–18

5.2.1. External Metrics

• Clustering performance is evaluated using ARI, NMI, and purity; ARI has expected value 0 under random assignment and value 1 under perfect agreement.ARI penalizes over- and under-segmentation; NMI may not penalize over-segmentation as strongly as ARI, while purity tends to favor over-segmentation.Source: §5.2.1 · p. 18

5.2.2. Comparison algorithms and experimental setup

• Comparisons include tuned-parameter DLCC as a reference and NN-RMS, Spectrum, FINCH, and U-Kmeans, with methods’ parameter choices and best-result selection specified.For random methods, the best of 10 runs is reported; “best” means highest ARI, which may not yield the best NMI or purity. A-DLCC’s temporary-cluster construction needs no tuning, while its final classifier uses fixed settings and random-forest results average 100 seeds.Source: §5.2.2 · pp. 18–19

5.2.3. Evaluation

• A-DLCC matches or exceeds other automatic methods in estimated cluster number and accuracy on real datasets except Seg, performs comparably to tuned DLCC, and reaches purity 1.000 on Yale-B.Temporary clusters generally perform strongly before the final classification step.Source: §5.2.3 · p. 19, Table 4 · p. 20
• Across real datasets, A-DLCC’s local centers generally align with cluster centers or visually separated groups, including small groups, while Seg’s overlapping central groups are joined.Temporary-clustering unlabelled points tend to lie near overlap regions and boundaries; the results are visually coherent under tSNE, and local-center definition does not assume balanced cluster sizes.Source: §5.2.3 · p. 19

5.3. A case study on Anuran Calls

• On Anuran Calls, A-DLCC significantly outperforms competitors in ARI and NMI and has the highest purity, with ARI above 0.9 despite estimating 16 clusters.Spectrum misses the smallest species; NN-RMS and FINCH achieve high purity but lower ARI because they over-split the largest species. A-DLCC recovers the two largest species almost perfectly, while its small-species separation is supported by low background similarity and contacts weaker than the null expectation.Source: §5.3 · p. 21

6 CONCLUSIONS AND FUTURE DIRECTIONS 22

• A-DLCC recovers dominant and smaller structures, even when larger species are split into multiple clusters and smaller species are partly grouped together.The split clusters correspond to visually separated groups in the t-SNE embedding.Source: §6 · p. 22
• The ARI remains high because the large classes are pure and the splits affect comparatively few observations.Source: §6 · p. 22
• In high-dimensional, complex datasets, A-DLCC may estimate more clusters by identifying small groups unlike any major cluster as separate clusters.The passage describes this tendency as a consequence of the method’s fully automatic design, without strong assumptions about data structure or cluster size.Source: §6 · p. 22

• A-DLCC requires no tuning parameters, adapts to a wide range of clustering scenarios, and outperformed tested automatic methods on real high-dimensional data with balanced and unbalanced clusters.Source: §6 · p. 22

• On complex high-dimensional data, A-DLCC may overestimate cluster counts when structure is ambiguous or contains small, weakly connected groups; ground-truth labels may also be arbitrary.Such labels may not reflect structures visible in the data.Source: §6 · p. 24
• A-DLCC’s results should be meaningful and interpretable without prior knowledge of cluster count; ambiguous small groups may indicate outliers or class overlap and guide further analysis.The authors note that these groups may warrant manual inspection or domain-specific analysis.Source: §6 · p. 24
• Considering all neighborhood sizes makes β-ILD cost O(n^2), while constructing G has worst-case O(n^3); faster local-depth estimation remains an open challenge.The original DLCC had O(n^3) complexity, and A-DLCC can be even more demanding.Source: §6 · p. 24
• Although merging uses interpretable quantities uniformly, threshold (10) and slack q remain heuristic, motivating a principled objective function or internal criterion.No universally accepted objective performs well across convex and non-convex cluster shapes and varying dimensionalities; such a criterion could support more principled model selection.Source: §6 · p. 24