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

Resumen

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.