An Improved K-means Algorithm based on Mapreduce and Grid

Li Ma, Lei Gu, Bo Li, Yue Ma, Jin WangInternational Journal of Grid and Distributed Computing 2015 · DOI

TL;DR

This paper presents an improved K-means clustering algorithm that addresses the traditional algorithm's sensitivity to initial cluster centers and noise. By leveraging a grid-based approach for initial center selection and noise removal, and integrating with the MapReduce framework for parallel processing, the proposed method achieves more stable and accurate clustering, especially for large datasets.

What Problem Does This Paper Address?

The K-means clustering algorithm, while popular for its simplicity and speed, suffers from several key limitations. Firstly, determining the optimal number of clusters (K) is often a manual and heuristic process. Secondly, the random selection of initial cluster centers can lead to unstable and suboptimal clustering results, requiring multiple runs to find a good solution. Thirdly, K-means is highly susceptible to noise points, which can significantly degrade the quality of the clusters. Finally, its scalability to very large datasets can be a bottleneck. This paper aims to tackle these issues by proposing a more robust and efficient K-means variant.

Methods

The authors introduce a multi-stage improvement to the K-means algorithm:

  1. Grid-based Data Partitioning and Noise Removal: The dataset is first divided into a grid. Data points are assigned to grids based on their attribute values. The number of points in each grid is counted, and grids with fewer points than a defined "noise-point threshold" are identified as containing noise and their points are removed. This step helps to pre-process the data and reduce the impact of outliers.
  2. DBSCAN for K Determination: The grid centers of the remaining data points are then used as input for the DBSCAN algorithm. DBSCAN, a density-based clustering algorithm, is employed here to automatically determine the optimal number of clusters, K.
  3. Grid-based Initial Center Selection: To overcome the random initialization problem, the algorithm selects M grids (where M > K) with the highest data point density. From these M grids, K points that are farthest from each other are chosen as the initial cluster centers. This ensures a more informed and spread-out initial placement of centroids.
  4. MapReduce Parallelization: To handle large datasets efficiently, the improved K-means algorithm is parallelized using the MapReduce framework. This involves designing Map and Reduce functions for both the initial center generation and the core K-means iterative steps, enabling distributed processing across multiple nodes.

Datasets

The primary dataset used for evaluation in this paper is the UCI Iris dataset. This is a well-known benchmark dataset in machine learning, containing 150 instances with four attributes, each belonging to one of three classes. The authors mention using this dataset to test the accuracy and stability of their improved algorithm compared to the traditional K-means. For the parallelization experiments, they used datasets of varying sizes: 50,000, 100,000, 200,000, and 400,000 data points.

Key Insights and Ideas

  • Grid-based pre-processing is effective for noise reduction and initial center selection: By partitioning data into a grid and setting a noise threshold, the algorithm effectively filters out outliers before clustering. Selecting initial centers from dense grid regions and ensuring they are far apart leads to more stable and potentially better initializations than random selection.
  • DBSCAN can reliably determine K: Using DBSCAN on grid centers to determine K is a novel approach that automates a critical parameter selection step in K-means.
  • MapReduce significantly boosts scalability: The parallelization of the improved K-means algorithm using MapReduce demonstrates substantial improvements in processing time for large datasets, highlighting its suitability for big data scenarios.
  • Improved stability and accuracy: The combination of these techniques leads to a K-means algorithm that is less sensitive to initial conditions and noise, resulting in more consistent and accurate clustering results.

Key Results

  • Improved Accuracy: The improved K-means algorithm achieved a higher accuracy rate (up to 91.33%) compared to the traditional K-means algorithm (maximum 90%) on the Iris dataset.
  • Reduced Objective Function (J): The improved algorithm consistently resulted in a lower objective function value (e.g., 77.9443) compared to the traditional K-means (e.g., 106.1, 99.10), indicating better cluster quality.
  • Noise Removal: The algorithm successfully identified and removed 26 noise points from the Iris dataset.
  • Scalability and Speedup: The parallelized algorithm showed good scalability. For instance, processing a dataset of 40,000 data points, the iteration time decreased from 5 minutes 26 seconds with one node to 2 minutes 5 seconds with three nodes, demonstrating significant speedup.

Limitations and Future Work

  • Grid Size and Noise Threshold Tuning: The paper acknowledges that the "grid size" and "noise-point threshold" are parameters that need to be set, and their optimal values might depend on the specific dataset. Further research could explore adaptive methods for setting these parameters.
  • Computational Overhead of Grid Creation: While effective, the initial grid creation and assignment step adds some computational overhead, which might be a consideration for extremely high-dimensional datasets.
  • Future Work: The authors suggest that their parallelized algorithm offers high efficiency and good scalability, implying that further exploration of its performance on even larger and more complex datasets would be beneficial. They also highlight the success of their method in determining K and handling noise, which could be extended to other clustering algorithms.

Summary updated

Abstract

The traditional K-means clustering algorithm is difficult to initialize the number of clusters K, and the initial cluster centers are selected randomly, this makes the clustering results very unstable. Meanwhile, algorithms are susceptible to noise points. To solve the problems, the traditional K-means algorithm is improved. The improved method is divided into the same grid in space, according to the size of the data point property value and assigns it to the corresponding grid. And count the number of data points in each grid. Selecting M(M>K) grids, comprising the maximum number of data points, and calculate the central point. These M central points as input data, and then to determine the k value based on the clustering results. In the M points, find K points farthest from each other and those K center points as the initial cluster center of K-means clustering algorithm. At the same time, the maximum value in M must be included in K. If the number of data in the grid less than the threshold, then these points will be considered as noise points and be removed. In order to make the improved algorithm can adapt to handle large data. We will parallel the improved k-mean algorithm and combined with the MapReduce framework. Theoretical analysis and experimental results show that the improved algorithm compared to the traditional K-means clustering algorithm has high quality results, less iteration and has good stability. Parallelized algorithm has a very high efficiency in data processing, and has good scalability and speedup.
BibTeX
@article{ma2015improved,
  author = {Li Ma and Lei Gu and Bo Li and Yue Ma and Jin Wang},
  title = {{An Improved K-means Algorithm based on Mapreduce and Grid}},
  journal = {International Journal of Grid and Distributed Computing},
  year = {2015},
  doi = {10.14257/ijgdc.2015.8.1.18},
}
Figure