Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/7742| Title: | Estudio e Implementación de las Mejoras más Relevantes del Algoritmo K-means y su Análisis Comparativo |
| Authors: | Moreno Cruz, Jonathan Isai%622421 |
| Issue Date: | 2016-10-20 |
| Publisher: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Centro Nacional de Investigación y Desarrollo Tecnológico |
| Description: | El problema general de la comparación de algoritmos ha sido ampliamente cuestionado, esto, debido a la influencia de enfoques como el teorema no free luch, el cual señala que no existe un algoritmo que domine en la solución de todas las instancias de un problema NP. Con este conocimiento, se plantea la cuestión de decidir cuándo un algoritmo es mejor que otro. Desde la publicación del algoritmo K-means, se han propuesto numerosas mejoras que lo optimizan, sin embargo, no se ha encontrado un mecanismo sistematizado ni herramientas para la comparación de mejoras a K-means en igualdad de condiciones que permitan determinar los casos y características en que una mejora es dominante. En la literatura especializada, existen estudios comparativos del algoritmo K-means, donde, el método clásico de comparación consiste ehn resolver una instancia de prueba con el algoritmo K-menas y la mejora propuesta. Por otra parte, cuando se compara respecto a otras mejoras, se observa la ausencia de elementos importantes que permitan a los investigadores realizar estudios similares, además, existe evidencia de casos en que algunas mejoras se benefician al resolver un determinado tipo de instancia. En este trabajo, se propone una metodología para la comparación de algoritmos con base experimental y rigor estadístico, la cual, se validó mediante un análisis comparativo de tres de las más relevantes mejoras del algoritmo K-means en su fase de clasificación, a saber: Early Classification, Enhanced K-means y Pattern Reduction. Los resultados obtenidos muestran que en términos de calidad las mejoras dominantes son: Enhanced K-means y Early Classification con 33 y 28 casos, respectivamente. Por otra parte, en términos de eficiencia, es destacable la superioridad de la mejora Pattern Reduction, sin embargo, ésta presentó pérdidas de calidad de hasta 23%. Esta investigación proporcionará beneficios importantes a los investigadores que requieran comparar diferentes algoritmos heurísticos y a la comunidad científica en general, esto, debido a que los principios de este trabajo pueden aplicarse a otros dominios del conocimiento. |
| metadata.dc.type: | info:eu-repo/semantics/masterThesis |
| Appears in Collections: | Tesis de Maestría en Computación |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| MC_Jonathan_Isai_Moreno_Cruz_2016.pdf | Tesis | 23.89 MB | Adobe PDF | View/Open |
| MC_Jonathan_Isai_Moreno_Cruz_2016_c.pdf Restricted Access | Cesión de derechos | 234.02 kB | Adobe PDF | View/Open Request a copy |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
