A Distributed Framework for Trimmed Kernel k-Means Clustering

Nikolaos Tsapanos, Anastasios Tefas, Nikolaos Nikolaidis, Ioannis Pitas

Research output: Contribution to journalArticle (Academic Journal)peer-review

30 Citations (Scopus)
344 Downloads (Pure)

Abstract

Data clustering is an unsupervised learning task that has found many applications in various scientific fields. The goal is to find subgroups of closely related data samples (clusters) in a set of unlabeled data. Kernel k-Means is a state of the art clustering algorithm. However, in contrast to clustering algorithms that can work using only a limited percentage of the data at a time, Kernel k-Means is a global clustering algorithm. It requires the computation of the kernel matrix, which takes O(n2d) time and O(n2) space in memory. As datasets grow larger, the application of Kernel k-Means becomes infeasible on a single computer, a fact that strongly suggests a distributed approach. In this paper, we present such an approach to the Kernel k-Means clustering algorithm, in order to make its application to a large number of samples feasible and, thus, achieve high performance clustering results on very big datasets. Our distributed approach follows the MapReduce programming model and consists of 3 stages, the kernel matrix computation, a novel matrix trimming method and the Kernel k-Means clustering algorithm.
Original languageEnglish
Pages (from-to)2685–2698
Number of pages14
JournalPattern Recognition
Volume48
Issue number8
DOIs
Publication statusPublished - 27 Feb 2015

Keywords

  • Data clustering
  • Face clustering
  • Kernel k-Means
  • Distributed computing

Fingerprint Dive into the research topics of 'A Distributed Framework for Trimmed Kernel <i>k</i>-Means Clustering'. Together they form a unique fingerprint.

Cite this