Incremental Density-Based Clustering with Grid Partitioning (Student Abstract)

Jeong-Hun Kim, Tserenpurev Chuluunsaikhan, Jong-Hyeok Choi, Aziz NasridinovAAAI 2023 · DOI

TL;DR

This paper introduces iDBSCAN, a novel incremental clustering method that significantly speeds up DBSCAN's cluster updates by intelligently partitioning the data space into grids. By localizing potential cluster changes to specific grid regions, iDBSCAN achieves up to 163.3 times faster updates than traditional DBSCAN, making it more practical for dynamic datasets.

What Problem Does This Paper Address?

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a powerful algorithm for finding arbitrarily shaped clusters and identifying outliers. However, a major drawback of DBSCAN is its computational inefficiency when new data points are added. To update clusters, DBSCAN typically needs to re-evaluate a significant portion of the dataset, often performing re-clustering from scratch. This becomes a bottleneck in applications where data streams in continuously. Existing incremental approaches often sacrifice accuracy for speed or still incur substantial computational costs in worst-case scenarios. This paper aims to bridge this gap by developing an incremental DBSCAN that maintains accuracy while drastically reducing the time required for cluster updates.

Methods

The core of iDBSCAN lies in its grid partitioning strategy. The data space is divided into a grid, and a spatial index is built. This allows for efficient e-range queries by focusing only on objects within grids adjacent to a target object.

The update process is broken down into three steps:

  1. Grid Partitioning: The data space is divided into grids. The grid length is carefully chosen to be related to the clustering parameter $\epsilon$. Each grid is assigned a unique key.
  2. Update Localization: When a new data point ($X_p$) arrives, the algorithm identifies the grid it belongs to ($G_p$) and its neighboring grids within a certain range (defined by $\epsilon$ and the grid size). This set of neighboring grids, denoted as $N_g$, is crucial for limiting the search space. Further pruning is done by calculating minimum and maximum distances between grids to ensure only relevant grids are considered.
  3. Cluster Update: The algorithm then efficiently updates clusters by performing e-range queries only within the localized grid regions ($G_p$ and $N_g$). This significantly reduces the number of objects that need to be examined. Label propagation is also optimized by restricting it to these localized regions, rather than the entire dataset.

Datasets

The authors evaluated iDBSCAN on three synthetic datasets generated using the scikit-learn Python library:

  • Circles: Datasets with 10k and 30k points.
  • Blobs: Datasets with varying dimensions (d=3 and d=5).
  • Moons: Datasets with different noise levels ($\eta=0.1$ and $\eta=0.2$).

These datasets were chosen to represent various shapes, scales, and noise levels. The evaluation involved performing DBSCAN on 90% of the data and then incrementally updating the clusters with the remaining 10% of the data.

Key Insights and Ideas

  • Grid Partitioning as a Spatial Index: The paper demonstrates that a simple grid partitioning can serve as an effective spatial index to accelerate density-based clustering operations.
  • Localized Updates are Key: The most significant insight is that cluster updates in DBSCAN are often localized. By identifying and focusing on the relevant grid regions, the computational burden of e-range queries and label propagation can be dramatically reduced.
  • Balancing Accuracy and Speed: iDBSCAN successfully achieves a substantial speedup without compromising the accuracy of the clustering results, a common trade-off in many incremental algorithms.

Key Results

The experimental results show that iDBSCAN significantly outperforms standard DBSCAN in terms of cluster update performance.

  • Speedup: iDBSCAN achieved cluster update performance up to 163.3 times faster than DBSCAN.
  • Quantitative Metrics: Table 1 shows that iDBSCAN consistently achieved high clustering accuracy (ACC) comparable to DBSCAN across all tested synthetic datasets, while drastically reducing the running time (RT) and mean update time (MUT). For example, on the "circles (n=30k)" dataset, iDBSCAN's RT was 8.30 seconds compared to DBSCAN's 924.00 seconds.

Limitations and Future Work

Limitations: * The paper focuses on incremental updates due to new data insertion. The performance on large-scale deletions or significant data distribution shifts is not explicitly discussed. * The current implementation is for student abstract, and further optimization might be possible.

Future Work: The authors plan to expand the proposed method to handle simultaneous updates for large transactions, suggesting a direction for handling more complex dynamic data scenarios.

Summary updated

BibTeX
@inproceedings{kim2023incremental,
  author = {Jeong-Hun Kim and Tserenpurev Chuluunsaikhan and Jong-Hyeok Choi and Aziz Nasridinov},
  title = {{Incremental Density-Based Clustering with Grid Partitioning (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.26981},
}
Figure