Iterative centroid-based clustering algorithms, such as $k$-means and MacQueen's algorithm, are foundational tools in unsupervised learning. However, they suffer from a notorious Achilles' heel: their dependence on initial centroid placement. Standard stochastic initialization strategies, even sophisticated ones like $k$-means++, rely heavily on geometric distance. While distance-based seeding helps spread centroids out, it remains highly vulnerable to outliers and frequently gets trapped in suboptimal local minima when dealing with complex, real-world data distributions.
To resolve this, a prominent research direction focuses on density-aware initialization. The core intuition is simple: instead of placing initial centroids blindly across a geometric space, algorithms should leverage the underlying density distribution of the data. By seeding clusters within high-density regions while maintaining spatial separation, these techniques provide a deterministic, robust, and accelerated path to convergence.
The Geometry of Density Peaks and Gaps
The most intuitive way to understand density-based initialization is through the lens of "local density peaks." A ideal cluster center is a point that sits at the heart of a high-density region but is far away from other, even denser regions.
This mechanism was formalized by Rashid Mehmood et al. in their work on Clustering by fast search and merge of local density peaks for gene expression microarray data. The authors map out the data by calculating two metrics for every point: its local density and its distance to the nearest neighbor with a higher density. Points that exhibit both high local density and a large distance to a denser neighbor are identified as natural cluster seeds.
Similarly, the authors of the Adaptive micro partition and hierarchical merging for accurate mixed data clustering (AMPHM) framework utilize "density gaps." By ensuring that a selected point possesses a high local density while remaining significantly distant from any point with a higher density, the initialization phase isolates representative structures. This prevents the boundary errors common in top-down partitioning and ensures that the initial micro-clusters maintain high purity.
Low Density High Density Peak (Seed 1)
. .
* * * *
. .
* * * * *
* * * *
|
| Large Distance Gap
|
Low Density High Density Peak (Seed 2)
. .
* * * *
. .
* * * * *
* * * *
Safeguarding Against Outliers via Density Weighting
Why does purely distance-based seeding fail in noisy environments? Consider an outlier—a single data point sitting far away from the rest of the dataset. Because distance-based algorithms like $k$-means++ select seeds with a probability proportional to their squared distance from existing centers, they are mathematically drawn to these isolated noise points. Seeding a centroid on an outlier inevitably leads to poor cluster boundaries and empty clusters.
Density-aware initialization solves this by incorporating a density-based weighting factor. For instance, Bin Wang et al. developed GDD-K-Means Text Clustering Algorithm Based on Grid Filtering Distance and Density of Outliers, which explicitly requires initial centers to be both distant from existing centers and located within high-density regions. Weighting the selection process by local density prevents the accidental selection of outliers, resulting in more consistent and distinct cluster boundaries.
This balancing act can also be integrated directly into classical probabilistic frameworks. Arwin B. Tiangco et al. demonstrate this in Enhanced MacQueen's Algorithm for Identifying Diverse Crime Patterns in the City of Manila, where they inject a density-based weighting factor into the probability distribution of centroid selection.
Conversely, density awareness can be used to ensure prototype diversity in deep learning. Yaxin Hou takes an inverse approach in Samples Are Not Equal: A Sample Selection Approach for Deep Clustering, weighting sample contributions inversely to their local density during prototype initialization. This ensures that low-density, diverse data points are not entirely drowned out by massive, redundant clusters, preventing the model from converging to a biased local optimum.
Scaling Up: Spatial Partitioning and Neighborhood Searches
Calculating exact pairwise densities for millions of data points is computationally expensive. To make density-based initialization practical for big data, researchers rely on spatial partitioning structures like trees and recursive grids to approximate density distributions efficiently.
One prominent method is recursive space splitting. In Density Estimation via Discrepancy Based Adaptive Sequential Partition, Dangna Li et al. use a greedy binary partition of the data space to locate high-density regions. The centers of these dense partitions are then harvested as initial centroids, providing a highly representative starting point that yields lower-error outcomes than standard stochastic seeding. Similarly, Zhuohui Ren leverages spatial data structures in Application of Dynamic Clustering Alogirthm in Medical Surveillance, using KD-trees to partition the data space and ensure that initial centers accurately reflect the underlying data density.
+-----------------+-----------------+
| | * * * * * |
| | * Seed 1 * |
| | * * * * * |
+-----------------+-----------------+
| * * * * | |
| * Seed 2 * | |
| * * * * | |
+-----------------+-----------------+
Spatial Partitioning via Trees isolates dense cells
Trees can also balance density with spatial scale. Chenglin Fan et al. explore this in k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy. Their initialization strategy scores potential centers by multiplying the number of data points in a tree's subtree by the spatial scale of its corresponding level. This allows the algorithm to remain robust when processing imbalanced datasets, capturing small, dense clusters that traditional sampling techniques routinely miss.
Finally, instead of counting points in fixed partitions, one can look at the inverse problem: how much space is required to enclose a certain amount of data? Jianqing Fan et al. introduce this perspective in A provable initialization and robust clustering method for general mixture models. Their strategy identifies potential cluster centers by locating regions where the neighborhood radius required to encompass a specific fraction of points is minimized. By prioritizing these dense cores, they provide starting centroids that mathematically guarantee convergence, even in the presence of heavy-tailed noise.