Veuillez utiliser cette adresse pour citer ce document :
https://rinacional.tecnm.mx/jspui/handle/TecNM/4161
Titre: | Caracterización de dos mejoras del estado del arte del algoritmo K-Means orientadas a la solución de grandes instancias |
Auteur(s): | Moreno Calderon, Carlos Fernando%1000864 |
Date de publication: | 2022-06-16 |
Editeur: | 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 |
Collection(s) : | Tesis de Maestría en Computación |
Fichier(s) constituant ce document :
Fichier | Description | Taille | Format | |
---|---|---|---|---|
MC_Carlos_Fernando_Moreno_Calderon_2022.pdf | Tesis | 2.08 MB | Adobe PDF | Voir/Ouvrir |
MC_Carlos_Fernando_Moreno_Calderon_2022.PDF Accès limité | Cesión de derechos | 371.78 kB | Adobe PDF | Voir/Ouvrir Demander une copie |
Ce document est protégé par copyright |
Ce document est autorisé sous une licence de type Licence Creative Commons