Algoritmo jerárquico aglomerativo paralelo para la agrupación clustering

RESUMEN En esta tesis de investigación se trabajó con la disminución de la complejidad del método de Ward de n4 a n3, mediante programación paralela, mejorando los tiempos de proceso sin disminuir la calidad de agrupación. El método de Ward es uno de los diversos métodos jerárquicos de análisis de cluster, el cual utiliza el criterio de la suma de error al cuadrado. El método de Ward es importante para la agrupación debido a que es capaz de agrupar objetos similares, aunque estén dispersos en el espacio de búsqueda, una de sus aplicaciones ha sido el análisis de la resistividad en rocas, análisis de yacimiento por presencia o ausencia de ciertos taxones, actividades que financian los préstamos, datos meteorológicos, etc. El método de Ward realiza una búsqueda exhaustiva entre los objetos, lo que lo hace un problema combinatorio, con una complejidad de n4 debido a esto lo hace complicado para agrupar gran cantidad de objetos. La programación paralela utiliza múltiples procesadores disponibles para resolver un problema. Se distingue de la programación secuencial en que varias operaciones pueden ocurrir simultáneamente. Con la implementación de este algoritmo con programación paralelase logró el objetivo principal que es disminuir la complejidad del método. Dando como resultado un mejor tiempo de solución, y con la agrupación igual a las instancias de prueba que se obtuvieron de la literatura, con datos reales y de prueba. Con esta mejora en la disminución de la complejidad se pueden resolver problemas con mayor número de objetos en menor tiempo.

Abstract In this research thesis, we worked with the reduction of the complexity of Ward's method from n4to n3, through parallel programming, improving process times without reducing the quality of grouping. Ward’s method is one of several hierarchical methods of cluster analysis, which uses the criterion of the sum of squared error. Ward's method is important for grouping because it is capable of grouping similar objects even though they are scattered in the search space, one of its applications has been the analysis of resistivity in rocks, reservoir analysis by presence or absence of certain taxa, activities that finance loans, weather data, etc. Ward's method performs an exhaustive search between the objects, which makes it a combinatorial problem, with a complexity of n4 due to this it makes it difficult to group large amounts of objects. “Parallel programming is the use of multiple computational resources to solve a problem”. It is distinguished from sequential programming in that several operations can occur simultaneously. With the implementation of this algorithm with parallel programming, the main objective was achieved, which is to reduce the complexity of the method. Resulting in a better solution time, and with the grouping equal to the test instances that were obtained from the literature, with real and test data. With this improvement in the reduction of complexity, problems with a greater number of objects can be solved in less time.