📊 statistics

Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios

This paper proposes Depth-Based Local Center Clustering (DLCC), a flexible framework that utilizes local data depth to identify centers and form clusters of varying shapes, thereby addressing the limitations of traditional methods in handling multimodal and non-convex data structures.

Original authors: Siyi Wang, Alexandre Leblanc, Paul D. McNicholas

Published 2026-01-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Siyi Wang, Alexandre Leblanc, Paul D. McNicholas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant box of mixed-up marbles. Some are red, some are blue, some are green, and they are scattered in all sorts of patterns: some are in tight little balls, some are in long winding snakes, and some are mixed right next to each other. Your job is to sort them into piles based on which ones "belong" together. This is what data scientists call clustering.

For decades, scientists have built different machines to sort these marbles. Some machines look for the "center" of a pile (like finding the middle of a circle). Others look for areas where the marbles are packed tightly together (like finding a crowded room). But here's the problem: real-world data is messy. A machine designed to find perfect circles often fails when the marbles are in a snake shape. A machine designed for crowded rooms might get confused if the crowd is spread out unevenly.

This paper introduces a new, smarter sorting machine called DLCC (Depth-Based Local Center Clustering). Here is how it works, using simple analogies:

1. The Problem with "Global" Rules

Most old methods try to look at the entire box of marbles at once and apply one rule to everyone.

The "Center" Problem: Imagine trying to find the center of a donut. If you just look for the middle point, you end up in the empty hole, not on the dough. Similarly, if a cluster is shaped like a ring, a "center-based" method fails.
The "Density" Problem: Imagine a crowd where some people are standing shoulder-to-shoulder, and others are spread out in a park. A method that looks for "crowded" spots might miss the people in the park entirely.

2. The DLCC Solution: "Local Neighborhoods"

DLCC doesn't look at the whole box at once. Instead, it acts like a detective who walks around the box and asks, "Who are your neighbors?"

The "Mirror" Trick (Data Depth): To figure out who is central, DLCC uses a clever trick. Imagine you pick one marble and hold up a mirror behind it. You look at the reflection of all the other marbles. If your marble is right in the middle of the reflection, it's a "deep" or "central" point. If it's on the edge, it's "shallow."
Local Centers: DLCC does this for every single marble in its own little neighborhood. It asks, "In this specific small group, who is the most central?" These central points are called "Local Centers."
- Analogy: Think of a city. A "Global Center" might be the city hall. But a "Local Center" is the most popular coffee shop in a specific neighborhood. DLCC finds the coffee shops, not just the city hall.

3. Grouping the Coffee Shops

Once DLCC has found all these local "coffee shops" (Local Centers), it needs to group them into actual clusters. It uses two different strategies, like two different ways of organizing a party:

The "Min" Strategy (The Conservative Host): This is for when you have groups that are roughly the same size and don't overlap too much. It groups the coffee shops that are very similar to each other. It's strict and keeps things neat.
The "Max" Strategy (The Connect-the-Dots Host): This is for messy situations where groups are weird shapes (like snakes) or very different sizes. It connects coffee shops if there is any path of similarity between them, even if they are far apart. This allows it to find those winding snake-shaped clusters that other methods miss.

4. The Final Cleanup

Sometimes, after grouping the coffee shops, there are still a few marbles left over that didn't fit perfectly. DLCC doesn't just guess. It uses a "classification" step (like a smart assistant) to look at the marbles that were successfully sorted and asks, "Based on who your neighbors are, which pile do you belong to?"

Why is this special?

The paper claims that DLCC is a "Swiss Army Knife" for clustering.

It handles shapes: It can find round piles, snake piles, and ring piles.
It handles sizes: It can sort a pile of 10 marbles and a pile of 10,000 marbles at the same time.
It handles overlap: It can tell the difference between two groups that are touching each other.

The Catch (Limitations)

The paper is honest about its limits:

It's computationally heavy: Because it has to check the "neighborhood" of every single marble against every other marble, it takes a lot of time and computer power if you have millions of marbles. It's great for thousands, but might struggle with billions.
It needs a human touch: You still have to tell the machine a few settings (like how big a "neighborhood" should be). It's not fully automatic yet.
The "Manifold" issue: If the data is shaped like a very thin, twisting wire (a 1D line in a 3D space), the "local neighborhood" idea can get confused, because the wire might look like a solid block from a close-up view.

Summary

In short, DLCC is a new way to sort data that stops trying to force everything into a perfect circle or a perfect crowd. Instead, it looks at small, local neighborhoods to find the "heart" of the data, then connects those hearts to form groups. It's flexible, robust, and works well on messy, real-world data, though it requires a bit of computing power and human guidance to get the settings right.

Technical Summary: Depth-Based Local Center Clustering (DLCC)

Problem Statement
Cluster analysis is fundamental to data science, yet existing methods often struggle with the diversity of real-world data distributions. Traditional approaches generally fall into two categories, each with specific limitations:

Center-based methods (e.g., k-means) assume a single representative point per cluster and spherical shapes, making them sensitive to outliers and initialization while failing to model non-convex geometries.
Density-based methods (e.g., DBSCAN, Mean Shift) handle arbitrary shapes but rely on density estimation or fixed thresholds, which can be unstable in high-dimensional spaces or when clusters have varying densities.
Graph-based methods often face computational prohibitions on large-scale data or remain sensitive to distance metric choices.

A core limitation across these paradigms is the definition of "exemplars" (representative points). Most methods tie exemplars to distance or density criteria that may not generalize across different dimensionalities and geometries. Furthermore, while statistical data depth offers a robust, center-outward ordering of multivariate data, it has historically been used only as an auxiliary tool (e.g., for initialization) rather than as the primary mechanism for identifying local structure and multimodality. Standard depth functions also fail to capture multimodal characteristics directly.

Methodology: The DLCC Framework
The paper proposes Depth-Based Local Center Clustering (DLCC), a framework that leverages statistical data depth to define local centers and construct similarity measures without relying on global distance metrics or density estimates.

Depth-Based Similarity Matrix:
Instead of using Euclidean distance, DLCC constructs a similarity matrix $S$ based on Spatial Depth (SD). To localize the depth concept, the method defines a reflected dataset $X_{Ri}$ for each observation $x_i$ , consisting of the original sample $X$ and the reflection of all points through $x_i$ . Since $x_i$ is the center of symmetry for $X_{Ri}$ , its depth is maximal (1). The depth of any other point $x_j$ relative to $X_{Ri}$ , denoted $D(x_j | X_{Ri})$ , serves as a measure of similarity between $x_j$ and $x_i$ .
- Efficiency: The authors introduce a matrix-based implementation to compute these depths efficiently, reducing redundant calculations by precomputing unit vector sums and norms, though the theoretical complexity remains $O(n^3)$ .
Local Center Identification:
For each point $x_i$ , a neighborhood $N_i$ of size $s$ is defined by its $s-1$ nearest neighbors based on the depth-based similarity. Within each neighborhood, the point with the highest local rank (deepest point) is identified as a local center.
- Filtering: Not all local centers are useful. The method filters candidates based on two criteria: (1) the center must be central within its neighborhood (rank $\le 2$ ), and (2) it must appear frequently across different neighborhoods (frequency $f > 1$ ). A stability criterion, Average Neighbor-Induced Depth (AND), is used to further select robust centers.
Grouping Strategies:
The filtered local centers are grouped into clusters using two distinct strategies to handle different data geometries:
- Min Strategy: Groups centers conservatively based on mutual neighborhood overlap. This is suitable for balanced, well-separated, or overlapping convex clusters.
- Max Strategy: Groups centers via connectivity chains where neighborhood similarity exceeds a threshold $\delta$ . This strategy is designed for non-convex structures and highly unbalanced cluster sizes. It includes a mechanism to segregate "everywhere non-convex" regions (e.g., spirals) by identifying isolated local centers.
Cluster Formation and Classification:
Once groups of local centers are formed, temporary clusters are created using the unique neighbors of each group. Points are assigned scores based on their similarity to the group's centers versus other groups. Ambiguous or unassigned points are then classified using built-in classifiers (k-Nearest Neighbors or Random Forests) trained on the temporary cluster labels, ensuring robust assignment without additional hyperparameter tuning.

Key Contributions

Novel Framework: DLCC is the first method to place data depth at the core of both exemplar identification and similarity construction, directly addressing multimodality.
Efficient Computation: The paper develops a matrix-based implementation for constructing depth-based similarity matrices under spatial depth, significantly accelerating computation compared to naive implementations.
Flexible Grouping: The dual-strategy approach (Min/Max) allows the framework to adapt to varying cluster shapes (convex vs. non-convex) and density distributions.
Comprehensive Evaluation: The authors provide a complete end-to-end procedure, including parameter selection guidelines (using the CVDD index and visualization) and extensive empirical evaluations.

Experimental Results
The authors evaluated DLCC on 12 synthetic datasets and 13 real-world benchmarks (including high-dimensional image and microarray data).

Performance: DLCC achieved perfect recovery on 7 synthetic datasets and consistently ranked in the top three across all real-world benchmarks. It demonstrated superior performance in handling non-convex shapes, varying densities, and class imbalance compared to competitors like LW-k-means, EKM, R-MDPC, and ACLR.
Limitations Observed: The method struggled with "manifold-like" structures where local neighborhoods are inherently non-convex (e.g., the "Atom" dataset and spiral structures in "Blend"). In these cases, the assumption that local centers reside in approximately convex neighborhoods failed.
Scalability: While effective for datasets up to $\sim 10^4$ observations, the $O(n^3)$ complexity of constructing the similarity matrix remains a bottleneck for very large-scale data.

Significance and Claims
The paper claims that DLCC offers a flexible alternative to traditional clustering by overcoming the rigid assumptions of center-based methods and the instability of density-based methods in high dimensions. By utilizing data depth to define local geometry, DLCC enhances data analysis capabilities across a wide range of scenarios without requiring a predefined number of clusters or strict distributional assumptions. The authors position DLCC as a robust tool for exploratory data analysis, particularly where cluster shapes are complex or unknown, while acknowledging that future work is needed to improve scalability and automate parameter selection.