Int. J. of Space-Based and Situated Computing   »   2017 Vol.7, No.2

 

 

Title: Acceleration of the K-means algorithm by removing stable items

 

Authors: Adriana Mexicano; Ricardo Rodriguez Jorge; Pascual Montes; Joaquín Pérez

 

Addresses:
Technological Institute of Ciudad Victoria, Ciudad Victoria, Tamaulipas, Mexico
Technological Institute of Ciudad Victoria, Ciudad Victoria, Tamaulipas, Mexico
Technological Institute of Ciudad Victoria, Ciudad Victoria, Tamaulipas, Mexico
Technological Institute of Ciudad Victoria, Ciudad Victoria, Tamaulipas, Mexico

 

Abstract: This work presents an approach for enhancing the K-means algorithm in the classification phase. The approach consists in a heuristic, which at each time that an object remains in the same group, between the current and the previous iteration, it is identified as stable and it is removed from computations in the classification phase in the current and subsequent iterations. This approach helps to reduce the execution time of the standard version. It can be useful in big data applications. For evaluating computational results, both the standard and the proposal were implemented and executed using three synthetic and seven well-known real instances. After testing both versions, it was possible to validate that the proposed approach spends less time than the standard one. The best result was obtained for the transactions instance when it was grouped into 200 clusters, achieving a time reduction of 90.1% with a reduction in quality of 3.97%.

 

Keywords: K-means; time reduction; accelerating; classification phase; grouping; pattern recognition; improvement; stable objects; unsupervised learning; heuristic.

 

DOI: 10.1504/IJSSC.2017.10008032

 

Int. J. of Space-Based and Situated Computing, 2017 Vol.7, No.2, pp.72 - 81

 

Submission date: 16 Jan 2017
Date of acceptance: 25 Apr 2017
Available online: 25 Sep 2017

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article