Abstract
This paper presents I-PACE (Improved Probabilistic Ant based Clustering for Distributed databases), an enhanced swarm-intelligence algorithm designed to address the challenges of clustering data in distributed environments. By introducing data-item weighting based on query relevance and implementing "familial pheromone trails" to reduce inter-agent interference, I-PACE achieves faster convergence and higher cluster quality than traditional methods. Experimental results on synthetic and real-world datasets demonstrate that I-PACE consistently outperforms k-means, hierarchical clustering, and the original PACE algorithm in terms of accuracy and error reduction.
Introduction
Clustering data across distributed sites, such as global banking branches, is a critical task in modern data mining. Centralizing data for analysis is often impractical due to bandwidth constraints and privacy regulations. While decentralized "ant-based" clustering—inspired by biological sorting behaviors—offers a solution, existing models like PACE (Probabilistic Ant based Clustering for Distributed databases) suffer from slow convergence and a lack of nuance in data prioritization. I-PACE addresses these flaws by incorporating query-driven weights and familial odor models to optimize the clustering process.
Methodology
The I-PACE algorithm utilizes software agents that mimic ant behavior to organize data items into clusters. The architecture integrates several key innovations to improve efficiency and accuracy:
- Introduction of Weights ($d_w$): Data items are weighted based on their "hit ratio" relative to user keywords. Ants prioritize high-weight items, accelerating the discovery of relevant patterns.
- Familial Pheromone Trails: An "Ant Odor Identification Model" allows different ant families to follow distinct pheromone trails. This prevents the "smudging" of heterogeneous data types and leads to cleaner, more distinct clusters.
- Dynamic Radius of Perception: The visual range of agents is adjusted dynamically based on local data density and weight, allowing for more efficient searching.
- Parallelization: The system performs intra-zone clustering simultaneously across distributed sites, with inter-zone clustering commencing as soon as local zones are ready.
Experimental Results
The performance of I-PACE was evaluated using four datasets: the synthetic Square1 dataset and three real-world benchmarks from the UCI Machine Learning Repository (Iris, Wine Recognition, and Yeast). These provide varying levels of complexity and feature overlap to test the algorithm's robustness.
I-PACE was benchmarked against k-means, Average Link (hierarchical), and the original PACE algorithm. As shown in the comparative results, I-PACE consistently achieved superior scores in F-Measure, Dunn Index, and Rand Index across nearly all test cases.
Key findings from the evaluation include:
- Accuracy: I-PACE consistently outperformed its predecessors. For instance, on the Iris dataset, I-PACE reduced the percentage of errors to 1%, compared to 1.78% for PACE and 4.67% for k-means.
- Stability: The lower standard deviations observed with I-PACE indicate higher reliability and stability across multiple runs compared to traditional methods.
Conclusion
I-PACE represents a significant advancement in distributed data clustering by making the process query-aware and reducing agent interference through familial odors. While the algorithm shows clear benefits in speed and accuracy, future work will focus on optimizing the memory overhead associated with maintaining individual data weights and exploring scalability limits in extremely large-scale distributed systems.
Summary updated