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.086819

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

Received: 26 Jan 2017
Accepted: 25 Apr 2017
Published online: 28 Sep 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article