An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data

Liping Jing*, Kwok Po NG, Joshua Zhexue Huang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

456 Citations (Scopus)

Abstract

This paper presents a new k-means type algorithm for clustering high-dimensional objects in subspaces. In high-dimensional data, dusters of objects often exist in subspaces rather than in the entire space. For example, in text clustering, clusters of documents of different topics are categorized by different subsets of terms or keywords. The keywords for one cluster may not occur in the documents of other clusters. This is a data sparsity problem faced in clustering high-dimensional data. In the new algorithm, we extend the k-means clustering process to calculate a weight for each dimension in each cluster and use the weight values to identify the subsets of important dimensions that categorize different clusters. This is achieved by including the weight entropy in the objective function that is minimized in the k-means clustering process. An additional step is added to the k-means clustering process to automatically compute the weights of all dimensions in each cluster. The experiments on both synthetic and real data have shown that the new algorithm can generate better clustering results than other subspace clustering algorithms. The new algorithm is also scalable to large data sets.

Original languageEnglish
Pages (from-to)1026-1041
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume19
Issue number8
DOIs
Publication statusPublished - Aug 2007

Scopus Subject Areas

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

User-Defined Keywords

  • High-dimensional data
  • K-means clustering
  • Subspace clustering
  • Text clustering
  • Variable weighting

Fingerprint

Dive into the research topics of 'An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data'. Together they form a unique fingerprint.

Cite this