Constrained Clustering: Taxonomy, New Optimization Models, and Hybridizations with Singular Problems of Machine Learning

Abstract

In the golden era of information, vast amounts of data are available to perform analysis on and extract valuable insight from. The area of science devoted to this problem is known as Knowledge Discovery in Databases; particularly, it is its branch of Data Science where this thesis is framed in. Specifically, this thesis focuses on clustering techniques that are capable of including relational information into the clustering process. This type of information does not fit into the classic supervised and unsupervised learning paradigms. However, the Semi- Supervised Learning (SSL) paradigm does provide us with the tools to perform clustering in the presence of relational information. This task is known as Constrained Clustering (CC). Four objectives shape this thesis: 1. A comprehensive study in the area of CC, from an SSL standpoint. The goal of this objective is to produce the first comprehensive analysis of the CC state-of-the-art, including a standardization of the experimental procedures and a ranking of all CC methods proposed so far. 2. The development of metaheuristic-based proposals for the CC problem, from both single-objective and multi-objective optimization perspectives. Two metaheuristicbased methods are designed to achieve this objective. Both are first proposed in this thesis and have been specifically designed to obtain quality solutions for the CC problem. An empirical study compares both methods against the state-of-the art in their specific areas, demonstrating their superiority. 3. The proposal of hybrid models for the CC problem. Motivated by the high quality results that hybrid methods usually obtain in the field of CC, this thesis introduces a new hybrid model that combines the two broadest categories in the area: partitional CC and constrained distance metric learning. This proposal also includes a procedure to automatically determine the relevance of the pieces that make up the set of relational information. The empirical study carried out provides evidence of the proposal being superior to the state-of-the-art. 4. Finally, motivated by the existence of real-world problems where multiple types of background knowledge are available, this thesis tackles the issue of combining relational and monotonicity information. This combination gives rise to the monotonic constrained clustering paradigm. The suitability of the problem is proved, and a baseline algorithm is proposed. The experimental study shows the superiority of monotonic constrained clustering algorithm over both purely constrained and purely monotonic clustering algorithms. This finding is backed by positive results in a classic set of benchmarks and a real-world monotonic constrained clustering problem. The four objectives have been successfully addressed, and the thesis has made significant contributions to the field of CC from the point of view of SSL. The comprehensive study carried out in the first objective provides a solid basis for understanding the state-of-the-art in CC and enables the standardization of experimental procedures, which is crucial for a scientifically sound comparison of different methods. The development of metaheuristicbased proposals in the second objective provides new and efficient techniques to solve the CC problem, while the proposed hybrid models in the third objective demonstrate the potential of combining different approaches to further improve the quality of the results. Finally, the proposed monotonic constrained clustering paradigm in the fourth objective addresses the problem of combining multiple types of background knowledge and achieves superior results over purely constrained and purely monotonic clustering algorithms.

La edad de oro de la información trae consigo la generación de enormes cantidades de datos, disponibles para ser analizados con el fin de extraer de ellos información valiosa. El área de la ciencia que se encarga de esta tarea se conoce como extracción de conocimiento en bases de datos (Knowledge Discovery in Databases - KDD). En concreto, esta tesis se centra en las técnicas de clustering que son capaces de considerar información relacional. Este tipo de información no encaja en los paradigmas supervisado y no supervisado considerados clásicos en el aprendizaje automático. Sin embargo, el paradigma de aprendizaje semisupervisado (Semi-Supervised Learning - SSL) nos proporciona las herramientas necesarias para aplicar técnicas de clustering en presencia de dicha información relacional. Esta tarea se conoce como agrupamiento restringido o clustering con restricciones (Constrained Clustering - CC). Esta tesis aborda los siguientes cuatro objetivos: 1. El primero consiste en un estudio exhaustivo en el área del CC desde el punto de vista del SSL. Su finalidad es realizar el primer análisis exhaustivo del estado del arte en CC que incluya una estandarización de los procedimientos experimentales y una clasificación de todos los métodos de CC propuestos hasta ahora. 2. El segundo aborda el desarrollo de propuestas basadas en metaheurísticas para el CC, incluyendo técnicas de optimización tanto monoobjetivo como multiobjetivo. Para plantear este objetivo se han diseñado dos métodos. Ambos se proponen por primera vez en esta tesis y han sido diseñados específicamente para el CC. Un estudio empírico compara ambos métodos con el estado del arte en sus respectivas áreas y demuestra su superioridad. 3. El tercer objetivo tiene como finalidad investigar modelos híbridos para el CC. Motivada por la ya demostrada capacidad de dichos modelos para obtener resultados de calidad en el ámbito del CC, esta tesis incorpora un nuevo modelo híbrido que combina las dos categorías más amplias en el área: el CC particional y el aprendizaje métrico de distancias con restricciones. Esta propuesta también incluye un procedimiento para determinar automáticamente la relevancia de los elementos que conforman el conjunto de información relacional. El estudio empírico realizado proporciona evidencia de que nuestra propuesta es superior al estado del arte. 4. Por último, motivada por la existencia de problemas para los que están disponibles múltiples tipos de información incompleta (como la información relacional), esta tesis plantea cómo combinar información relacional y de monotonicidad. Dicha combinación da lugar al paradigma del clustering monotónico con restricciones. Tras demostrar la relevancia del problema que se aborda, se propone un algoritmo básico para resolver el mismo. El estudio experimental muestra la superioridad de este algoritmo sobre otros que solo son capaces de considerar información relacional o de monotonicidad por separado. Los hallazgos relacionados con este objetivo están respaldados por resultados positivos en baterías de pruebas estándar y en un caso de aplicación específico. La tesis aborda los cuatro objetivos descritos con éxito. De esta manera, quedan suficientemente demostradas sus aportaciones en su campo de estudio. La revisión de la literatura llevada a cabo en el primer objetivo proporciona una base sólida para comprender el estado del arte en el CC. Permite la estandarización de los procedimientos experimentales, lo que es crucial para una posterior comparación científicamente fundamentada de diferentes métodos. El desarrollo de propuestas basadas en metaheurísticas en el segundo objetivo proporciona nuevas técnicas eficientes para resolver el CC, mientras que los modelos híbridos propuestos en el tercer objetivo demuestran el potencial de combinar diferentes enfoques para mejorar aún más la calidad de los resultados. Finalmente, el paradigma del clustering monotónico restringido, propuesto en el cuarto objetivo, aborda la combinación de múltiples tipos de información incompleta, logrando resultados superiores a los obtenidos con modelos anteriores.