A general framework for efficient clustering of large datasets based on activity detection

Xin Jin, Sangkyum Kim, Jiawei Han, Liangliang Cao, Zhijun Yin

Research output: Contribution to journalArticle

Abstract

Data clustering is one of the most popular data mining techniques with broad applications. K-Means is one of the most popular clustering algorithms, due to its high efficiency/effectiveness and wide implementation in many commercial/noncommercial softwares. Performing efficient clustering on large dataset is especially useful; however, conducting K-Means clustering on large data suffers heavy computation burden which originates from the numerous distance calculations between the patterns and the centers. This paper proposes framework General Activity Detection (GAD) for fast clustering on large-scale data based on center activity detection. Within this framework, we design a set of algorithms for different scenarios: (i) exact GAD algorithm, E-GAD, which is much faster than K-Means and gets the same clustering result; (ii) approximate GAD algorithms with different assumptions, which are faster than E-GAD, while achieving different degrees of approximation; and (iii) GAD based algorithms to handle the large clusters problem which appears in many large-scale clustering applications. The framework provides a general solution to exploit activity detection for fast clustering in both exact and approximate scenarios, and our proposed algorithms within the framework can achieve very high speed. We have conducted extensive experiments on several datasets from various real world applications, including data compression, image clustering, and bioinformatics. By measuring the clustering quality and CPU time, the experiment results show the effectiveness and high efficiency of our proposed algorithms.

Original languageEnglish (US)
Pages (from-to)11-29
Number of pages19
JournalStatistical Analysis and Data Mining
Volume4
Issue number1
DOIs
StatePublished - Feb 1 2011

Keywords

  • Activity detection
  • Clustering
  • Hierarchical clustering
  • K-Means
  • Kd-tree

ASJC Scopus subject areas

  • Analysis
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A general framework for efficient clustering of large datasets based on activity detection'. Together they form a unique fingerprint.

  • Cite this