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:	Mejora de un algoritmo de agrupamiento mediante el paradigma de programación paralela
Authors:	Salgado Antunez, Nancy%1032455
Issue Date:	2023-05-22
Publisher:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Centro Nacional de Investigación y Desarrollo Tecnológico
Description:	K-Means es uno de los algoritmos de agrupamiento más utilizados debido a su fácil implementación e interpretación de sus resultados. El problema de agrupamiento de K-Means es del tipo NP-Hard, lo cual justifica el uso de métodos heurísticos para su solución. En consecuencia, su estudio continúa siendo relevante y vigente. A la fecha se han propuesto implementaciones paralelas del algoritmo K-Means estándar, algunas sobre un dominio especifico y muy pocas variantes de propósito general. Sin embargo, estas aún están limitadas para la solución de grandes datasets. En contraste se propone un nuevo enfoque de solución el cual consistió en seleccionar una variante secuencial campeona del algoritmo K-Means, la cual se rediseñó e implementó de forma paralela y distribuida. Al nuevo algoritmo se le denominó Hybrid O-K-Means (HOK-Means). Para esta propuesta, se analizaron variantes del algoritmo K-Means y se seleccionó una altamente eficiente, denominada O-K-Means, la cual mostró tener buen desempeño en tiempo y mínima reducción en la calidad de la solución. Para validar los resultados de HOK-Means, se diseñaron e implementaron diversos experimentos, solucionando tanto datasets reales como sintéticos de gran tamaño. Con base en los resultados se mostró que en el mejor de los casos para los datasets con un indicador de tamaño ndk mayor a 16 millones, se logra un speedup (Sp) de hasta 22.14x más rápido que O-K-Means, logrando una eficiencia paralela (Ep) de 0.92. En el peor de los casos, se obtuvo un Sp de 1.7x, para datasets pequeños. Es importante destacar que se resolvieron grandes datasets de hasta 102,464,000 objetos y hasta 70 dimensiones. Finalmente, con base en los resultados obtenidos, es posible afirmar que esta investigación aporta beneficios a distintos usuarios, principalmente a quienes busquen solucionar grandes conjuntos de datos como los que se presentan en Big Data aprovechando todos los recursos disponibles de una red de computadoras.
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