Density Based Initial Center Optimization Algorithm

Shengli Sun, Zhigao Zheng, Yu ZhangAdvances 2013 · DOI

Abstract

K-Means is a widely utilized clustering algorithm, yet its performance is frequently hampered by sensitivity to initial cluster centers and noise, often converging to local minima. While density-based algorithms like DBSCAN handle noise well, they struggle with high-dimensional data and varying densities. Grid-based methods offer speed but can compromise accuracy. This paper proposes the Density Based Initial Center Optimization (DBICO) algorithm, a hybrid approach that leverages grid-based partitioning and density-based sensitivity to optimize initial centroid selection. By dividing the dataset into cells, merging them via a "Fuzzy Ratio," and filtering noise, DBICO provides stable starting points for K-Means. Experimental results on synthetic and logistics trajectory data demonstrate that DBICO improves clustering quality and reduces iteration counts compared to standard random initialization.

Introduction

Clustering is a fundamental task in data mining, with K-Means being the most popular choice due to its simplicity and efficiency. However, K-Means relies on a distance-based judgment that makes it highly sensitive to the initial placement of centroids. A poor initial selection can lead the algorithm to converge on a suboptimal local minimum, resulting in clusters that do not accurately represent the underlying data distribution. Furthermore, K-Means is susceptible to noise; outliers can significantly shift centroids away from dense data regions.

To address these limitations, we introduce DBICO. This algorithm acts as a pre-processing stage that identifies robust initial centers by combining the computational efficiency of grid-based methods with the noise-robustness of density-based approaches.

Methodology

The DBICO algorithm follows a four-step process to prepare the dataset for K-Means clustering:

  1. Grid Partitioning: The data space is divided into $m$ discrete "cubes" or grid cells. This discretization allows for rapid density estimation across the feature space.
  2. Merging via Fuzzy Ratio: Adjacent cubes are evaluated for merging. We introduce a "Fuzzy Ratio" metric that compares the density of a potential merged region against the product of the densities of the individual cubes. This allows the algorithm to identify continuous regions of high density even when the density is not perfectly uniform.
  3. Noise Filtering: To mitigate the impact of outliers, DBICO applies a density threshold. Following a heuristic rule where the least dense $n - n^{3/8}$ cubes are flagged, the algorithm effectively prunes noise before the clustering process begins.
  4. Initial Center Selection: Instead of random sampling, the centroids of the densest remaining merged cubes are selected as the initial starting points for the K-Means algorithm.

By the time the actual K-Means algorithm starts, it already has a highly accurate "map" of where the clusters should be, significantly reducing the number of iterations required for convergence.

Experimental Evaluation

The performance of DBICO was validated using both synthetic simulation data and real-world logistics data.

Datasets

  • Simulation Dataset: A large-scale synthetic set containing 16,497 points, designed to test the algorithm's scalability and ability to handle multiple distinct clusters.
  • Logistics Trajectory Data: 3,613 GPS sample points from a logistics company. This dataset is characterized by continuous trajectories where identifying key nodes (e.g., warehouses or delivery hubs) is essential.

Results and Discussion

Comparative analysis against standard K-Means revealed significant improvements in both stability and quality. While standard K-Means produced varying results across multiple runs due to random initialization, DBICO's centers remained remarkably consistent.

Optimized cluster centers using the DBICO algorithm on a simulation dataset.

As shown in the simulation results, DBICO accurately identifies the centers of dense regions, effectively ignoring the sparse noise points that might otherwise distort the clusters. In the logistics application, the algorithm successfully extracted meaningful hub locations from messy GPS data, a task where traditional density-based methods often fail by over-merging trajectory points into a single cluster.

GPS trajectory data from a logistics company used for real-world validation.

Conclusion

The DBICO algorithm provides a robust solution to the initialization problem in K-Means clustering. By integrating grid-based partitioning with density-based merging and noise removal, it offers a reliable and high-quality starting point for the clustering process. The use of the Fuzzy Ratio and heuristic parameter settings ($k \approx n^{3/8}$) reduces the need for manual tuning while ensuring stability across different datasets. Future work will explore the application of DBICO to higher-dimensional data and real-time streaming environments.

Summary updated

Abstract

Means is the most popular clustering algorithm with the convergence to one of numerous local minima, which results in much sensitivity to initial representatives and noise point because of its distance based judgment. Density-based clustering algorithm is not sensitive to outliers and noise data, but it's difficult to present the high dimensional data as well as the changes of the data density. Grid-based method is fast, but may reduce the quality and accuracy of the cluster. However, this paper proposes a novel density based initial center optimization algorithm (DBICO) to choose the initial center, which by means of the local optimality and sensitivity of density-based clustering algorithm and grid-based method. The core idea is to divide the dataset into several cubes and merge some cubes, delete the noise points according to the density, calculate the initial center point and then clustering the dataset. Doing this can reduce the number of iterations, and avoid the disadvantages of the K-Means algorithm results differ due to the different initial points. Theoretic analysis and experimental demonstrations show that the algorithms this paper proposed outperforms existing algorithms in clustering quality, and it was proved fruitful applications in the logistics.
BibTeX
@inproceedings{sun2013density,
  author = {Shengli Sun and Zhigao Zheng and Yu Zhang},
  title = {{Density Based Initial Center Optimization Algorithm}},
  booktitle = {Advances},
  year = {2013},
  doi = {10.2991/icsecs-13.2013.19},
}
Figure