| Journal: | Computación y sistemas |
| Database: | |
| System number: | 000560157 |
| ISSN: | 1405-5546 |
| Authors: | Pérez Ortega, Joaquín1 Hidalgo Reyes, Miguel1 Castro Sánchez, Noé Alejandro1 Pazos Rangel, Rodolfo2 Díaz Parra, Ocotlán3 Olivares Peregrino, Víctor1 Almanza Ortega, Nelva1 |
| Institutions: | 1Centro Nacional de Investigación y Desarrollo Tecnológico, Cuernavaca. México 2Instituto Tecnológico de Ciudad Madero, Ciudad Madero, Tamaulipas. México 3Universidad Autónoma del Estado de Hidalgo, Pachuca de Soto. México |
| Year: | 2018 |
| Season: | Abr-Jun |
| Volumen: | 22 |
| Number: | 2 |
| Pages: | 607-619 |
| Country: | México |
| Language: | Español |
| Document type: | Artículo |
| Spanish abstract | Con la presencia cada vez mayor de Big Data surge la necesidad de agrupar grandes instancias. Estas instancias presentan un número de objetos de naturaleza multidimensional, los cuales requieren agruparse en cientos o miles de grupos. En este artículo se presenta una mejora al algoritmo K-means, la cual está orientada a la solución eficiente de instancias con un gran número de grupos y de dimensiones. A dicha mejor heurística se le denomina Honeycomb (HC) y está basada en la relación entre el número de dimensiones y el número de centroides que conforman una vecindad, permitiendo reducir el número de cálculos de distancias objeto-centroide para cada objeto. La heurística se validó resolviendo un conjunto de instancias sintéticas obteniendo reducciones del tiempo de ejecución de hasta un 90 % y con disminución de la calidad menor al 1 %, respecto a K-means estándar. Para instancias reales de baja y alta dimensionalidad, HC obtuvo una reducción del tiempo de ejecución entre 84.74 % y 95.44 % y con una reducción de la calidad entre el 1.07 % y 1.62 %, respectivamente. Los resultados experimentales son alentadores porque esta heurística beneficiaría a aquellos dominios que requieren instancias con valores cada vez mayores de objetos, dimensiones y grupos. |
| English abstract | With the increasing presence of Big Data there arises the need to group large instances. These instances present a number of objects with multidimensional features, which require to be grouped in hundreds or thousands of clusters. This article presents a new improvement to the K-means algorithm, which is oriented to the efficient solution of instances with a large number of clusters and dimensions. This heuristic is called Honeycomb (HC) and it is based on the relationship between the number of dimensions and the number of centroids that form a neighborhood. That is, the heuristic allows the reduction of the number of distance calculations for each object. The heuristic was validated by solving a set of synthetic instances obtaining reductions in execution time of up to 90 % and a quality reduction of less than 1 %, with respect to standard K-means. For real instances of low and high dimensionality, HC obtained a reduction of execution time between 84.74 % and 95.44 % with a quality reduction between 1.07 % and 1.62 %, respectively. The experimental results are encouraging because this heuristic would benefit those domains that require instances with a continuous increase of the number of objects, dimensions and clusters. |
| Disciplines: | Ciencias de la computación |
| Keyword: | Algoritmo K-means, Complejidad computacional, Heurística, Inteligencia artificial |
| Keyword: | K-means algorithm, Computational complexity, Heuristic, Artificial intelligence |
| Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
