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:
- 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.
- 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.
- 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.
- 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.
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.
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