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:	Desarrollo de una mejora al algoritmo K-means orientada al paradigma de Big Data
Authors:	Diaz Lorenzo, Alber%774604
Issue Date:	2018-10-11
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 de datos más usados en la actualidad, dada la sencillez y fácil interpretación de sus resultados. El algoritmo está estructurado en cuatro fases: inicialización, clasificación, cálculo de centroides y convergencia. Prácticamente todas las mejoras realizadas al algoritmo están enfocadas a una fase en particular; sin embargo, de acuerdo a la literatura especializada, no se ha propuesto la integración de mejoras de distintas fases. En este sentido, en este trabajo se propone H-Kmeans, una mejora híbrida que permite procesar, de manera optimizada, una instancia dada mediante composición de mejoras de diferentes fases. Para validar H-Kmeans se realizaron un conjunto de experimentos con instancias reales reconocidas por la comunidad científica internacional. Se seleccionaron 2 mejoras en las fases de inicialización, clasificación y convergencia, respectivamente. H-Kmeans permitió realizar 19 configuraciones para procesar las instancias seleccionadas. Los resultados obtenidos mostraron que con la combinación de mejoras se obtienen mejores resultados que procesando las instancias con las mejoras individuales o con K-means. Es necesario aclarar que al realizar mejoras a K-means se suele sacrificar la calidad de los resultados para lograr un menor tiempo de procesamiento; en muchos de los resultados obtenidos con H-Kmeans incluso se mejora la calidad de los resultados. Para la instancia 3D road network, con 434,874 objetos en 4 dimensiones, se obtuvo una reducción de tiempo del 82% con una ganancia de calidad del 47%. Para la instancia Household power consumption, con 2,049,280 objetos en 4 dimensiones, se obtuvo una reducción de tiempo del 97.3% con una ganancia de calidad del 2.3%. Aunque aumente el tamaño de la instancia los resultados del procesamiento siguen siendo excelentes, esto valida la utilización de la mejora H-Kmeans para el procesamiento de instancias dentro del paradigma de Big Data
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