1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Morelos
4. Centro Nacional de Investigación y Desarrollo Tecnológico
5. Tesis CENIDET
6. Tesis de Maestría
7. Tesis de Maestría en Computación

Title:	Incremento de la Eficiencia del Algoritmo K-means Mediante la Mejora de la Heurística Early Classification
Authors:	Lopez Caballero, Vitervo%512773
Issue Date:	2015-03-06
Publisher:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Centro Nacional de Investigación y Desarrollo Tecnológico
Description:	El algoritmo de agrupamiento K-means se ha aplicado en varios dominios debido a su facilidad de implementación computacional. Sin embargo, una de sus limitaciones es su alta complejidad computacional. Por esta razón, en esta investigación se propuso una nueva meta-heurística a la que se le denominó Nmeans, la cual permite reducir la complejidad de K-means de manera importante. Como resultado de observar las ejecuciones del algoritmo K-means se determinó que algunos grupos permanecen constantes porque ya no intercambian objetos con otros grupos. Con base en este conocimiento se desarrolló una nueva heurística a la que se denominó grupos estables. En dicha heurística se descartan los objetos asignados a un grupo estable en las iteraciones posteriores. En la meta-heurística N-means que se desarrolló en esta investigación se integran las heurísticas Early Classification y grupos estables. Para validar N-means, se realizaron experimentos con instancias reconocidas por la comunidad científica. Se reportan los resultados promedio de 30 ejecuciones de cada instancia variando los parámetros de k=100, 200, 400 y 800. Se contrastaron los resultados de los algoritmos K-means, Early Classification y N-means. En esta investigación se obtuvieron importantes resultados, entre los cuales se destacan los siguientes: a) para una instancia sintética de 40,000 objetos, Nmeans redujo el tiempo de ejecución en 75.5% y una disminución de la calidad de agrupamiento a -1.52%, Early Classification redujo el tiempo de ejecución en 67.7% y una disminución de la calidad de agrupamiento a -1.31%; b) con una instancia real de 245,057 objetos, N-means redujo el tiempo de ejecución en 64% y una disminución de la calidad a -4.56%, Early Classification redujo el tiempo de ejecución en 49% y una disminución de la calidad a -4.11%. Finalmente se considera que las mejoras al algoritmo K-means posibilitarán la solución de instancias grandes como las que emergen en el paradigma Big Data.
metadata.dc.type:	info:eu-repo/semantics/masterThesis
Appears in Collections:	Tesis de Maestría en Computación

This item is protected by original copyright View License

This item is licensed under a Creative Commons License