Synchronization clustering based on central force optimization and its extension for large-scale datasets

摘要

Although research on clustering methods has been active in recent years, not only must most current clustering methods pre-set the number of clusters or other user-specific parameters but they also perform on large-scale datasets inefficiently. In this paper, we study the clustering problem by exploring the metaphor of gravitational kinematics based on Central Force Optimization (CFO). However, different from the global synchronization of CFO, we propose a new algorithm G-Sync by simulating the partial synchronization phenomenon. Specifically, we view each data object as a probe and simulate the dynamic interaction behaviour of data objects in the gravitational field. As time evolves, similar data objects will naturally come into partial synchronization and form distinct clusters measured by the proposed degree of local synchronization, and the dynamic interaction behaviour of the data objects is continually simulated over time. By introducing the Davies–Bouldin (DB) index, G-Sync can determine clusters of arbitrary size, shape and density. Moreover, pre-setting the number of clusters to be found is not required. The algorithm is further extended for handling large-scale datasets with the scalable S-G-Sync algorithm, which is based on fast kernel density estimation (FastKDE). S-G-Sync initially condenses a large-scale dataset quickly into its reduced dataset, followed by adaptive clustering on the reduced dataset using G-Sync. Finally, the Clustering on Remaining Objects (CRO) algorithm is proposed to cluster the remaining objects in the large-scale dataset and to capture outlier and singleton clusters effectively. The effectiveness of the G-Sync and S-G-Sync algorithms is theoretically analysed and experimentally verified on synthetic and real-world datasets.