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:	Caracterización de dos mejoras del estado del arte del algoritmo K-Means orientadas a la solución de grandes instancias
Authors:	Moreno Calderon, Carlos Fernando%1000864
Issue Date:	2022-06-16
Publisher:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Centro Nacional de Investigación y Desarrollo Tecnológico
Description:	En esta investigación se aborda el problema de evaluación de algoritmos. En particular la evaluación de variantes del algoritmo K-Means para resolver grandes instancias. Desde el surgimiento de la familia de algoritmos K-Means, se han realizado diversos estudios para mejorar algunas de sus etapas y con ello reducir el costo computacional. Se ha observado en la literatura especializada que las variantes propuestas obtienen mejores resultados en cuanto a tiempo o calidad de solución frente al algoritmo estándar o incluso frente a otras variantes. Sin embargo, el diseño de experimentos que aplican abarca pocas instancias, y con ello surge la incertidumbre sobre la eficiencia y eficacia que podrían tener estas variantes al resolver otro tipo de instancias. En este trabajo de investigación, se propone la aplicación de dos variantes prometedoras en la solución de diferentes tipos de instancias, mayormente sobre instancias grandes. La variante Fahim cuya propuesta es ampliamente citada y reconocida por la exclusión de cálculos de distancia de centroides a objetos, lo cual genera un ahorro en el costo computacional. La variante O-K-Means es una propuesta relevante que genera menor costo computacional por realizar la convergencia del algoritmo cuando el total de objetos que cambian de grupo en una iteración es menor a un umbral definido. Esta propuesta se validó realizando pruebas de ejecución con el algoritmo K-Means estándar. Como referencia se implementó el algoritmo propuesto por Lloyd en 1982. Además de implementar las variantes Fahim y O-K-Means. Se realizó un diseño de experimentos donde se usaron 37 conjuntos de datos reales de repositorios reconocidos, 23 instancias fueron clasificadas como pequeñas y 14 como instancias grandes. Se realizaron comparaciones de tiempo y calidad de solución con respecto al algoritmo K-Means estándar. Los resultados obtenidos muestran que la variante Fahim es dominante al resolver instancias grandes mejorando la calidad hasta un 0.71% en el mejor de los casos. La variante O-K-Means demostró ser dominante con las instancias grandes al resolverlas en menor tiempo hasta un 93.57% en el mejor de los casos. Finalmente, se considera que esta investigación aporta beneficios a investigadores o usuarios que buscan resolver instancias similares a las que se usaron en esta investigación, ofreciéndoles una caracterización de la variante que se adecue mejor a sus necesidades.
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