Scaling up synchronization-inspired partitioning clustering

Wenhao Ying, Fu Lai Korris Chung, Shitong Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

Based on the extensive Kuramoto model, synchronization-inspired partitioning clustering algorithm was recently proposed and is attracting more and more attentions, due to the fact that it simulates the synchronization phenomena in clustering where each data object is regarded as a phase oscillator and the dynamic behavior of the objects is simulated over time. In order to circumvent the serious difficulty that its existing version can only be effectively carried out on considerably small/medium datasets, a novel scalable synchronization-inspired partitioning clustering algorithm termed LSSPC, based on the center-constrained minimal enclosing ball and the reduced set density estimator, is proposed for large dataset applications. LSSPC first condenses a large scale dataset into its reduced dataset by using a fast minimal-enclosing-ball based approximation for the reduced set density estimator, thus achieving an asymptotic time complexity that is linear in the size of dataset and a space complexity that is independent of this size. Then it carries out clustering adaptively on the obtained reduced dataset by using Sync with the Davies-Bouldin clustering criterion and a new order parameter which can help us observe the degree of local synchronization. Finally, it finishes clustering by using the proposed algorithm CRD on the remaining objects in the large dataset, which can capture the outliers and isolated clusters effectively. The effectiveness of the proposed clustering algorithm LSSPC for large datasets is theoretically analyzed and experimentally verified by running on artificial and real datasets.
Original languageEnglish
Article number6678517
Pages (from-to)2045-2057
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number8
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • KDE based density estimation
  • large datasets
  • minimal enclosing ball
  • reduced set
  • synchronization- inspired partitioning clustering

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this