Fast graph-based relaxed clustering for large data sets using minimal enclosing ball

Pengjiang Qian, Fu Lai Korris Chung, Shitong Wang, Zhaohong Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

42 Citations (Scopus)

Abstract

Although graph-based relaxed clustering (GRC) is one of the spectral clustering algorithms with straightforwardness and self-adaptability, it is sensitive to the parameters of the adopted similarity measure and also has high time complexity O(N3) which severely weakens its usefulness for large data sets. In order to overcome these shortcomings, after introducing certain constraints for GRC, an enhanced version of GRC [constrained GRC (CGRC)] is proposed to increase the robustness of GRC to the parameters of the adopted similarity measure, and accordingly, a novel algorithm called fast GRC (FGRC) based on CGRC is developed in this paper by using the core-set-based minimal enclosing ball approximation. A distinctive advantage of FGRC is that its asymptotic time complexity is linear with the data set size N. At the same time, FGRC also inherits the straightforwardness and self-adaptability from GRC, making the proposed FGRC a fast and effective clustering algorithm for large data sets. The advantages of FGRC are validated by various benchmarking and real data sets.
Original languageEnglish
Article number6145713
Pages (from-to)672-687
Number of pages16
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume42
Issue number3
DOIs
Publication statusPublished - 8 Feb 2012

Keywords

  • Clustering
  • large data sets
  • minimal enclosing ball (MEB)
  • time complexity

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this