A parallel k‐means clustering algorithm based on redundance elimination and extreme points optimization employing MapReduce. (23rd March 2017)

• Record Type: Journal Article
• Authors: Tang, Zhuo; Liu, Kunkun; Xiao, Jinbo; Yang, Li; Xiao, Zheng
• Other Names: Li Gang guestEditor.; Niu Wenjia guestEditor.; Batten Lynn guestEditor.; Liu Jiqiang guestEditor.; Li Kenli guestEditor.; Wang Lipo guestEditor.; Liu Yong guestEditor.
• Is Part Of: Concurrency and computation. Volume 29:Number 20(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-03-23
• Subjects: clustering algorithms -- extreme point -- k‐means -- MapReduce -- redundant distance; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4109
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: When facing massive statistical data, the k ‐means algorithm is very difficult to satisfy the need of data processing as it lacks an effective parallel mechanism. This paper proposes an improved k ‐means algorithm (IMR‐KCA) to conduct clustering analysis based on medical data employing MapReduce computing framework. Through analyzing the defects of vast redundancy in the traditional k ‐means algorithms, a selection model is firstly proposed to simplify the computations with multiple clustering centers. Based on several proposed theorems, we prove the correctness of this selection model. Second, this paper provides a method to calculate the distances from extreme points to central points, and the original Euclidean distance is replaced with Manhattan distance. For this simplification, a group of theorems are proposed to prove the correctness. Next, we provide a group of implementation algorithms to complete the parallelism of the clustering computation employing the MapReduce framework. Finally, the experimental results illustrate that IMR‐KCA is more reliable and efficient than the direct parallelization of the traditional clustering algorithms based on MapReduce. Copyright © 2017 John Wiley & Sons, Ltd.