Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/4161Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Moreno Calderon, Carlos Fernando%1000864 | - |
| dc.creator | Moreno Calderon, Carlos Fernando%1000864 | - |
| dc.date.accessioned | 2022-07-08T19:37:33Z | - |
| dc.date.available | 2022-07-08T19:37:33Z | - |
| dc.date.issued | 2022-06-16 | - |
| dc.identifier.uri | https://rinacional.tecnm.mx/jspui/handle/TecNM/4161 | - |
| dc.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. | es_MX |
| dc.language.iso | spa | es_MX |
| dc.publisher | Tecnológico Nacional de México | es_MX |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0 | es_MX |
| dc.subject | info:eu-repo/classification/cti/7 | es_MX |
| dc.title | Caracterización de dos mejoras del estado del arte del algoritmo K-Means orientadas a la solución de grandes instancias | es_MX |
| dc.type | info:eu-repo/semantics/masterThesis | es_MX |
| dc.contributor.director | Perez Ortega, Joaquin%7939 | - |
| dc.contributor.director | Hernandez Perez, Maria Yasmin%277696 | - |
| dc.folio | 22-0098 | es_MX |
| dc.rights.access | info:eu-repo/semantics/openAccess | es_MX |
| dc.publisher.tecnm | Centro Nacional de Investigación y Desarrollo Tecnológico | es_MX |
| Appears in Collections: | Tesis de Maestría en Computación | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| MC_Carlos_Fernando_Moreno_Calderon_2022.pdf | Tesis | 2.08 MB | Adobe PDF | View/Open |
| MC_Carlos_Fernando_Moreno_Calderon_2022.PDF Restricted Access | Cesión de derechos | 371.78 kB | Adobe PDF | View/Open Request a copy |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
