Journal
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS
Volume 42, Issue 3, Pages 672-687Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSMCB.2011.2172604
Keywords
Clustering; large data sets; minimal enclosing ball (MEB); time complexity
Categories
Funding
- Hong Kong Polytechnic University [1-ZV5V, G-U296]
- National Science Foundation of China [61170122, 60903100]
- Natural Science Foundation of Jiangsu Province [BK2009067, 2011NSFJS]
- Fundamental Research Funds for the Central Universities [JUSRP21128, JUSRP211A34, JUDCF09034]
- Postgraduate Student's Creative Research Funds of Jiangsu Province
- Research Fund of 2011 Jiangsu 333 Plan
Ask authors/readers for more resources
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(N-3) 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available