Improvement to the K-Means Algorithm Through a Heuristics Based on a Bee Honeycomb Structure

Authors

  • Joaquín Pérez Centro Nacional de Investigación y Desarrollo Tecnológico
  • Adriana Mexicano Centro Nacional de Investigación y Desarrollo Tecnológico
  • Rodolfo Pazos Instituto Tecnológico de Cd. Madero
  • René Santaolaya Centro Nacional de Investigación y Desarrollo Tecnológico
  • Miguel Hidalgo Centro Nacional de Investigación y Desarrollo Tecnológico
  • Alejandra Moreno Centro Nacional de Investigación y Desarrollo Tecnológico
  • Nelva Almanza Centro Nacional de Investigación y Desarrollo Tecnológico

Keywords:

Combinatorial Optimization, K-Means, Biologically Inspired Computing

Abstract

The object clustering problem, according to their similarity measures, can be formulated as a combinatorial optimization problem. The K-Means algorithm has been widely used for solving such problem; however, its computational cost is very high. In this work a new heuristics is proposed for reducing the computational complexity in the classification step of the algorithm, based on a honeycomb structure, which the algorithm builds when clusters are visualized in a two-dimensional space. In particular it has been observed that
an object can only change membership to neighboring clusters. The heuristics consists of performing distance calculations only with respect to centroids of neighboring clusters, which reduces the number of calculations. For assessing the performance of this heuristics, a set of experiments was carried out that involved 2,500, 10,000 and 40,000 objects uniformly distributed in a two dimensional space, as well as real-world instances of 3,100 and 245,057 objects with 2 and 3 dimensions. The results were encouraging, since the calculation time was reduced as much as 65% on average, with respect to the standard K-Means algorithm for the synthetic instances, and up to 62% on average for the real-world instances, while the quality was reduced on average by 0.05% and 2.5%, respectively.

Downloads

Download data is not yet available.

Downloads

Published

2013-04-01

How to Cite

Joaquín Pérez, Adriana Mexicano, Rodolfo Pazos, René Santaolaya, Miguel Hidalgo, Alejandra Moreno, & Nelva Almanza. (2013). Improvement to the K-Means Algorithm Through a Heuristics Based on a Bee Honeycomb Structure. Journal of Network and Innovative Computing, 1, 7. Retrieved from https://cspub-jnic.org/index.php/jnic/article/view/22

Issue

Vol. 1 (2013)

Section

Original Article

License

You are free to:

  1. Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
  2. Adapt — remix, transform, and build upon the material for any purpose, even commercially.
  3. The licensor cannot revoke these freedoms as long as you follow the license terms.

Under the following terms:

  1. Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  2. No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.

Notices:

You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .

No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.