Nuevos métodos para clustering basado en algoritmos evolutivos

Abstract

La presente tesis doctoral aborda el estudio de la solución del problema de agrupamiento. La solución a este problema busca dividir un conjunto de datos en grupos, donde los elementos dentro de cada grupo sean similares entre sí y diferentes con los elementos de otros grupos. El tipo de agrupamiento en el que se enfoca este trabajo es la agrupación basada en particiones, siendo el algoritmo K-means uno de los algoritmos precursores en resolver este problema. Concretamente, el agrupamiento o análisis de grupos es una técnica de aprendizaje no supervisado utilizada en el campo de la minería de datos y la inteligencia artificial. Tiene una gran relevancia debido a su aplicación en una amplia variedad de campos de la ciencia como la segmentación de imágenes, procesamiento digital de voz, recuperación de documentos, aplicaciones en internet, y actualmente, continúa el incremento en diferentes dominios de aplicación cada vez más diversos tales como la astronomía, geología, geofísica, paleoecología y medicina. Desde el punto de vista de la teoría de la complejidad computacional, la dificultad del problema de agrupación está al ser considerado del tipo NP-difícil, es un problema no convexo que suele contar con muchos óptimos locales por lo que al ser solucionado por un algoritmo a menudo termina dentro de uno de ellos. La finalidad es obtener una solución óptima que garantice una agrupación de calidad en función de determinados criterios que se fijen. Para su resolución se han diseñado muchos y diferentes enfoques de algoritmos, entre los que se encuentran los algoritmos bio-inspirados y dentro de estos, los algoritmos genéticos, que son modelos computacionales que simulan el fenómeno de evolución natural para resolver problemas en diferentes dominios incluyendo la agrupación. En esta tesis, en primer lugar, se ha realizado una exhaustiva revisión de los algoritmos genéticos que resuelven el problema de agrupamiento, centrándonos en los algoritmos genéticos que emplean un único objetivo, lo que ha permitido llevar a cabo un estudio pormenorizado con una taxonomía de las diferentes propuestas que representan el estado del arte. Como complemento, se ha desarrollado una herramienta de software llamada LEAC que cuenta con la implementación de todas las propuestas previas estudiadas y que se ha puesto disponible para la comunidad científica. La finalidad es posibilitar el acceso a todos estos modelos y que puedan ser utilizados directamente sin un amplio conocimiento de los mismos dentro de un mismo marco de trabajo. Además, su diseño modular, facilita en gran medida el diseño de nuevas propuestas gracias a todos los operadores de cruce y mutación, los operadores de selección, los métodos de inicialización, los tipos de codificaciones y las medidas de rendimiento que tiene disponible para su utilización directa en nuevas propuestas. Con el objetivo de analizar las diferentes propuestas existentes, se ha llevado a cabo un exhaustivo estudio experimental que ha incluido a todas las propuestas previas, una gran cantidad de conjuntos de datos y de índices de desempeño que miden tanto lo compacto que son los grupos que se han formado como la separación que existe entre ellos, esas son dos de las medidas más ampliamente utilizadas en estos entornos. Además, toda la información relativa a datos, algoritmos y comandos utilizados para la ejecución de las propuestas está disponible para facilitar una reproducción de los resultados. Finalmente, se han desarrollado dos nuevas propuestas de algoritmos genéticos que abordan este problema con codificaciones optimizadas y operadores especializados que han resultado ser altamente competitivas con respecto a las propuestas previas, obteniendo soluciones optimizadas que mejoran el rendimiento de estas propuestas previas.

This doctoral thesis deals with the study of clustering. To solve this problem is necessary to divide a data set into groups, where the elements within each group are similar to each other and different from the elements of other groups. The type of clustering in which this work focuses is partitional clustering where the K-means algorithm appears as one of the precursor algorithms in solving this problem. Specifically, clustering or group analysis is an unsupervised learning technique used in the field of data mining and artificial intelligence. It has great relevance due to its application in a wide variety of fields of science such as image segmentation, digital voice processing, document retrieval, and Internet applications. Currently, it continues to increase in diverse application domains such as astronomy, geology, geophysics, paleoecology, and medicine. From the point of view of computational complexity theory, the difficulty of clustering problems is classified as the NP-hard type. It is a non-convex problem that usually has many local optimums, so that, algorithms often find one of these local optimums. The purpose is to obtain an optimal solution that guarantees a quality grouping based on some criterio fixed. For its resolution, many different algorithm approaches have been designed, among which we find the bio-inspired algorithms where are the genetic algorithms. These algorithms are computational models that simulate the process of natural evolution to solve problems in different domains, including clustering. In this thesis, first, an exhaustive review of the genetic algorithms that solve the clustering problem has been carried out. With the focus on the genetic algorithms that use a single objective, it has been carried out a detailed study with a taxonomy of the different proposals that represent the state of the art. As a complement, a software tool called LEAC has been developed that includes the implementation of all the previous proposals studied and that has been made available to the scientific community. The purpose is to enable access to all these models so that they can be used directly without extensive knowledge within the same framework. In addition, its modular design greatly facilitates the design of new proposals thanks to all the crossover and mutation operators, selection operators, initialization methods, encoding types, and performance measures that are available for use directly in new proposals. To analyze the different existing proposals, it has been carried out an exhaustive experimental study including all the previous algorithms, a large number of data sets, and performance measures that analyze both compactness and separation, two criteria widely used in these environments. In addition, all the information related to data, algorithms, and execution commands is available to facilitate the reproduction of the results. Finally, two new genetic algorithm proposals have been developed that solve the clustering problem. They use optimized encodings and specialized operators and are highly competitive with respect to previous proposals. Concretely, they obtain optimized solutions that improve the performance of previous proposals.