A Hybrid Approach to Data Clustering Analysis with K-Means and Enhanced Ant-Based Template Mechanism

Data clustering algorithms play an important role in effective analysis and organization of massive amounts of information. The K-means algorithm is the most commonly used partitional data clustering algorithm because of its simplicity in implementation and its high convergence rate. However, it suffers from the inability to always converge to the global optima, depending on how the data items are distributed initially. Ant-based Template Mechanism (Ant_TM) is another frequently used clustering algorithm, but it exhibits two major weaknesses in convergence rate and data purity of clustering results. In this paper, we first present a modification to the original Ant_TM to encourage formation of new cluster regions that enables the clustering result to move away from local optima. Second, we present two hybrid clustering algorithms based on the enhanced Ant-based Template Mechanism (Ant_TM) and the K-means algorithms. The rationale is that the integration of the K-means algorithm can speed up the convergence process and provide a perturbance to break free from local optimum clustering. We conduct experiments to compare the performance of our hybrid algorithms, against the enhanced Ant TM and the K-means algorithm, as well as the PSO+K and GA. The result shows that our algorithms outperform the original Ant_TM, K-means, and PSO+K, and is competitive against the GA in terms of the more compact and better separated clusters.