Nuevos métodos para clustering basado en algoritmos evolutivos

Résumé

1. Introducción o motivación de la tesis: 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, de forma que todos los objetos que estén dentro de un grupo mantengan más similitud entre sí y sean más diferentes con los objetos perteneciente a otros grupos [15]. El tipo de agrupamiento en el que se enfoca este trabajo es el agrupamiento basado en particiones, siendo el algoritmo K-means [22] uno de los algoritmos precursores en resolver este problema. La agrupación es una tarea de la minería de datos catalogada como una técnica de análisis exploratoria no supervisada, donde los objetos pueden no estar previamente etiquetados o clasificados por un experto [29, 31]. Este hecho ha convertido la tarea de agrupamiento en una tarea muy relevante debido a que actualmente se producen cantidades masivas de datos, siendo complejo etiquetar los ejemplos por un experto. En este contexto, la agrupación es reconocida ampliamente como una de las tareas fundamentales dentro del aprendizaje automático. Además, tiene aplicación en una amplia variedad de campos de la ciencia como la segmentación de imágenes [30], procesamiento digital de voz, recuperación de documentos [17], aplicaciones en internet [4], y continua el incremento en diferentes dominios de aplicación cada vez más diversos tales como la astronomía [2], geología [8], geofísica [5], paleoecología [10] y medicina [26]. Otro aspecto importante de la agrupación basada en particiones es por la naturaleza del problema. Se trata de un problema no convexo que suele contar con muchos óptimos locales por lo que la solución de los algoritmos a menudo termina dentro de uno de ellos, considerado como un problema de tipo NP-complejo o NP-difícil (en inglés a esta clase de problemas se les conoce como NP-hard) [7, 20]. Esto motiva su estudio por el hecho de que es posible encontrar mejoras en su solución, siendo así el problema de agrupación un área prometedora de investigación. El problema de agrupación basado en particiones puede ser visto como un problema de optimización [25], al utilizar una medida de validez de agrupamiento o también llamado índice de validez de agrupamiento (CVI) [24], con la finalidad de obtener una solución óptima que garantice una agrupación de calidad en función de determinados criterios que se fijen como: compactibilidad (qué tan similares son los objetos dentro del mismo grupo), separación (qué tan diferentes son los grupos entre sí) [108-27] y conectividad (qué patrones vecinos comparten el mismo grupo) [12]. Determina el CVI apropiado también resulta en un problema difícil como se ver en varios estudios realizados [1, 3, 18, 19, 21, 27, 28, 29, 32]. En este contexto, una variedad de algoritmos meta-heurísticos bio-inspirados se puede encontrar para resolver el problema de agrupación basado en particiones [6, 11, 14, 16, 25]. Esta tesis se centra en los Algoritmos Evolutivos (EAs,del inglés Evolutionary Algorithm). Concretamente, en los Algoritmos Genéticos (AGs) que realizan búsquedas estocásticas basadas en el principio de los sistemas genéticos naturales [9, 13, 23]. Durante las últimas décadas y en la actualidad, los AGs se han aplicado a muchos problemas NP-difícil con muy buenos resultados, por lo que se considera relevante seguir realizando avances en esta área [27]. 2.Contenido de la investigación: A continuación se describe el contenido de la investigación ubicando los diferentes temas en su capítulo correspondiente: En el capítulo El problema de agrupamiento, de manera didáctica se define el problema de agrupamiento y los principales enfoques que han resuelto el problema, además se incluyendo una descripción de los diferentes algoritmos bio-inspirados que se han utilizado para resolver este problema. El capítulo Algoritmos genéticos para agrupación, se lleva a cabo una revisión a profundidad de las diferentes propuestas de AGs mono-objetivos que resuelven el problema de agrupamiento. Identificados los AGs, se analizó cada uno de ellos en dos niveles de abstracción. El primero fue la descomposición en sus características particulares para clasificar los componentes que conforman a los AGs. El segundo fue la composición del AG diferenciando como primer nivel de clasificación los que necesitan conocer el número de grupos y los que también intentan determinar este valor. Finalmente, incluye una taxonomía para poder clasificar las diferentes propuestas existentes como las nuevas. El capítulo Estudio experimental de los algoritmos genéticos para agrupación proporciona un estudio experimental de los AGs para agrupación que nos permite evaluar la capacidad de los diferentes algoritmos para resolver el problema de agrupación. Se muestra una discusión de los resultados obtenidos que permite determinar las ventajas e inconvenientes de las diferentes propuestas y los componentes que resultan más beneficiosos para resolver el problema. Toda la información de este estudio, algoritmos, conjunto de datos y resultados están disponibles en http://www.uco.es/kdis/a-survey-of-evolutionary-algorithm-for-clustering-taxonomy-and-empirical-analysis/ El capítulo GAMK: Un algoritmo genético para agrupación con número de grupos conocido propone un nuevo AG para resolver el problema de agrupamiento cuando el número de grupos es conocido. Los principales componentes que forman el algoritmo son descritos y se lleva a cabo un estudio experimental que permite evaluar el rendimiento de esta nueva propuesta y compararlo con las propuestas ya existentes. El capítulo GASGO: Un algoritmo genético para agrupación con número de grupos desconocido propone un nuevo AG para resolver el problema de agrupamiento cuando el número de grupos es desconocido. Los principales componentes que forman el algoritmo son descritos y se lleva a cabo un estudio experimental que permite evaluar el rendimiento de esta nueva propuesta y compararlo con las propuestas ya existentes. Además, un estudio específico de la estimación del número de grupos en estos algoritmos se lleva a cabo, debido a que se considera un factor muy importante en el diseño de estas propuestas. El capítulo LEAC: Como complemento para la investigación, se ha desarrollado una librería de algoritmos evolutivos para agrupamiento, se describe la arquitectura y principal funcionalidad de la librería de AGs llamada LEAC. 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 estos dentro de un mismo marco de trabajo. Además, su diseño modular, facilita en gran medida la implementación de nuevas propuestas gracias a que están disponibles una gran variedad operadores de cruce y mutación, operadores de selección, métodos de inicialización, tipos de codificaciones y CVIs para medir el rendimiento. La biblioteca está disponible en https://github.com/kdis-lab/LEAC 3.Conclusión: Se han cubierto satisfactoriamente todos los objetivos que se plantearon con las tesis. A continuación, se detallan las principales conclusiones: 1. Se ha llevado a cabo una revisión exhaustiva de los AGs mono-objetivo, al realizar una descripción detallada de las principales características de los algoritmos más relevantes publicados hasta la fecha para resolver el problema del agrupamiento basado en particiones 2. Se ha propuesto una taxonomía específica que considera todas las particularidades de los AGs, basada en las características más relevantes, permite una fácil clasificación de todas las propuestas desarrolladas hasta la fecha y además incluir cualquier nueva propuesta que se desarrolle. 3. Se ha llevado a cabo un estudio experimental exhaustivo que analiza la capacidad de los AGs para resolver problemas de agrupamiento. El estudio ha considerado bajo el mismo escenario, 22 AGs, 22 CVIs y 94 conjuntos de datos utilizando. 4. Se ha diseñado y desarrollado una nueva propuesta de un AG que trabaja en un entorno en el que se conoce el número de grupos (GAMK). Esta propuesta emplea nuevos operadores genéticos que se han desarrollado específicamente para lograr una búsqueda más eficiente. En un exhaustivo estudio con todas las propuestas previas muestra un excelente rendimiento logrando superar a los métodos previo. 5. Se ha diseñado y desarrollado una nueva propuesta de un AG que trabaja en un entorno en el que no se conoce el número de grupos (GASGO). Esta propuesta emplea nuevos operadores genéticos que se han desarrollado específicamente para lograr una búsqueda más eficiente junto con la representación seleccionada. En un exhaustivo estudio con todas las propuestas previas muestra un excelente rendimiento logrando superar a los métodos previo. 6. Se ha desarrollado una librería con todos los AGs especificados en este trabajo, incluidas las propuestas desarrolladas. La biblioteca, LEAC, se ha puesto a disposición de la comunidad científica. Publicaciones asociadas a la tesis Con la finalidad de promover los resultados obtenidos de la investigación realizada en esta tesis, se han realizado las siguientes publicaciones, las cuales cubren los diferentes objetivos que se plantearon: ¿ Robles-Berumen, H., Zafra, A., Ventura, S. A Survey of Genetic Algorithms for Clustering: Taxonomy and Empirical Analysis enviada a Swarm and Evolutionary Computation. ¿ Robles-Berumen, H., Zafra, A., Ventura, S. Una nueva propuesta basada en Algoritmos Genéticos para resolver problemas de Agrupamiento. XI Congreso científico de personal investigador en formación. Universidad de Córdoba, Mayo, 2023. ¿ Robles-Berumen, H., Zafra, A., Ventura, S. A Novel Genetic Algorithm with Specialized Genetic Operators for Clustering. The 18th International Conference on Hybrid Artificial Intelligence Systems (HAIS 2023), Salamanca, Septiembre, 2023. ¿ Robles-Berumen, H., Zafra, A., Fardoun, H., Ventura, S. LEAC: An efficient library for clustering with evolutionary algorithms. Knowl. Based Syst. 179: 117-119 (2019). Cubriría el trabajo desarrollado en el sexto punto que se ha planteado en las conclusiones. 4. Bibliografía: [1] Arbelaitz, O., Gurrutxaga, I., Muguerza, J., Pérez, J. M., and nigo Perona, I. (2013). An extensive comparative study of cluster validity indices. Pattern Recognition, 46(1):243 ¿256. [2] Banerjee, P., Chattopadhyay, T., and Chattopadhyay, A. K. (2023). Comparison among different clustering and classification techniques: Astronomical data-dependent study. New Astronomy, 100:101973. [3] Calinski, T. and Harabasz, J. (1974). A dendrite method for cluster analysis. ¿ Communications in Statistics, 3(1):1¿27. [4] Chawla, S. (2016). Application of genetic algorithm and back propagation neural network for effective personalize web search-based on clustered query sessions. Int. J. Appl. Evol. Comput., 7(1):33¿49. [5] Delforge, D., Watlet, A., Kaufmann, O., Van Camp, M., and Vanclooster, M. (2021). Time-series clustering approaches for subsurface zonation and hydrofacies detection using a real time-lapse electrical resistivity dataset. Journal of Applied Geophysics, 184:104203. [6 ] Ezugwu, A. E., Ikotun, A. M., Oyelade, O. O., Abualigah, L., Agushaka, J. O., Eke, C. I., and Akinyelu, A. A. (2022). A comprehensive survey of clustering algorithms: State-ofthe-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 110:104743. [7] Falkenauer, E. (1998). Genetic Algorithms and Grouping Problems. John Wiley & Sons, Inc., New York, NY, USA. [8] Ghezelbash, R., Maghsoudi, A., and Carranza, E. J. M. (2020). Optimization of geochemical anomaly detection using a novel genetic k-means clustering (gkmc) algorithm. Computers and Geosciences, 134:104335. [9] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition. [10] Göhring, A., Mauder, M., Vohberger, M., Nehlich, O., von Carnap-Bornheim, C., Hilberg, V., Kröger, P., and Grupe, G. (2018). Palaeobiodiversity research based on stable isotopes: Correction of the sea spray effect on bone carbonate 13c and 18o by gaussian mixture model clustering. Palaeogeography, Palaeoclimatology, Palaeoecology, 490:673 ¿ 686. [11] Hancer, E. and Karaboga, D. (2017). A comprehensive survey of traditional, merge-split and evolutionary approaches proposed for determination of cluster number. Swarm and Evolutionary Computation, 32:49 ¿ 67. [12] Handl, J. and Knowles, J. (2007). An evolutionary approach to multiobjective clustering. IEEE Transactions on Evolutionary Computation, 11(1):56¿76. [13] Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA. [14] Hruschka, E. R., Campello, R. J. G. B., Freitas, A. A., and de Carvalho, A. C. P. L. F. (2009). A survey of evolutionary algorithms for clustering. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 39(2):133¿155. [15] Jain, A. K., Murty, M. N., and Flynn, P. J. (1999). Data clustering: A review. ACM Comput. Surv., 31(3):264¿323. [16] Kayaalp, F. and Erdogmus, P. (2020). Benchmarking the clustering performances of evolutionary algorithms: A case study on varying data size. IRBM, 41(5):267 ¿ 275. [17] Kim, H., Kim, H. K., and Cho, S. (2020). Improving spherical k-means for document clustering: Fast initialization, sparse centroid projection, and efficient cluster labeling. Expert Systems with Applications, 150:113288. [18] Lee, S. H., Jeong, Y. S., Kim, J. Y., and Jeong, M. K. (2018). A new clustering validity index for arbitrary shape of clusters. Pattern Recognition Letters, 112:263 ¿ 269. [19] Liu, Y., Li, Z., Xiong, H., Gao, X., and Wu, J. (2010). Understanding of internal clustering validation measures. In 2010 IEEE International Conference on Data Mining, pages 911¿916. [20] Liu, Y., Peng, J., Chen, K., and Zhang, Y. (2006). An improved hybrid genetic clustering algorithm. In Antoniou, G., Potamias, G., Spyropoulos, C., and Plexousakis, D., editors, Advances in Artificial Intelligence, pages 192¿202, Berlin, Heidelberg. Springer Berlin Heidelberg. [21] Luna-Romera, J. M., Martínez-Ballesteros, M., García-Gutiérrez, J., and Riquelme, J. C. (2019). External clustering validity index based on chi-squared statistical test. Information Sciences, 487:1¿17. [22] MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, pages 281¿297. [23] Michalewicz, Z. (1992). Genetic Algorithms + Data Structures = Evolution Programs. Springer, Berlin. [25] Nanda, S. J. and Panda, G. (2014). A survey on nature inspired metaheuristic algorithms for partitional clustering. Swarm and Evolutionary Computation, 16:1¿18. [26] Poczeta, K., Kubus, L., and Yastrebov, A. (2020). Multidimensional medical data ¿ modeling based on fuzzy cognitive maps and k-means clustering. Procedia Computer Science, 176:118 ¿ 127. Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 24th International Conference KES2020. [27] Rezaei, M. and Fränti, P. (2020). Can the number of clusters be determined by external indices? IEEE Access, 8:89239¿89257. [28] Rojas-Thomas, J., Santos, M., Mora, M., and Duro, N. (2019). Performance analysis of clustering internal validation indexes with asymmetric clusters. IEEE Latin America Transactions, 17(05):807¿814. [29] Saitta, S., Raphael, B., and Smith, I. F. C. (2008). A comprehensive validity index for clustering. Intell. Data Anal., 12(6):529¿548. [30] Wu, C. and Kang, Z. (2020). Robust entropy-based symmetric regularized picture fuzzy clustering for image segmentation. Digital Signal Processing, page 102905. [31] Xu, R. and Wunsch, D., I. (2005). Survey of clustering algorithms. Neural Networks, IEEE Transactions on, 16(3):645¿678. [32] Zhu, E. and Ma, R. (2018). An effective partitional clustering algorithm based on new clustering validity index. Applied Soft Computing, 71:608 ¿ 621.