Agrupamento de dados com restrições

Mestrado em Engenharia Informática

As técnicas de agrupamento de dados (classificação não supervisionada) são úteis em vários problemas de análise exploratória de dados, tomada de decisão, estruturação de documentos e segmentação de imagem, entre outros. O seu objectivo consiste na divisão de um conjunto de dados em vários grupos, em que dados semelhantes são colocados no mesmo grupo e dados dissemelhantes em grupos diferentes. A combinação de agrupamentos de dados surgiu na última década com o intuito de melhorar a robustez e qualidade do agrupamento de dados, reutilizar soluções e agrupar dados de forma distribuída. O agrupamento de dados com restrições tem como objectivo incorporar conhecimento a priori no processo de agrupamento de dados, com o intuito de aumentar a qualidade do agrupamento de dados e, simultaneamente, encontrar soluções apropriadas a tarefas ou interesses específicos. Nesta dissertação, são estudados vários tipos de restrições usadas no agrupamento de dados, assim como os principais algoritmos de agrupamento de dados com restrições. São também desenvolvidas formas de combinar vários agrupamentos de dados usando restrições num agrupamento de dados final. Com o propósito de comparar os algoritmos de agrupamento com restrições e de avaliar os métodos de combinação de agrupamentos de dados com restrições propostos, são realizados dois estudos comparativos usando conjuntos de dados de referência.

Data clustering techniques (unsupervised classi cation) are useful in several problems of exploratory analysis, decision-making, documents structuring, image segmentation, among others. Its purpose is to partition a data set into several clusters, in which similar data is placed in the same cluster and dissimilar data in di erent clusters. Cluster ensemble methods appeared in the last decade aiming to improve clustering robustness and quality, reuse clustering solutions and cluster data in a distributed way. Constrained data clustering incorporates a priori knowledge in the clustering process, in order to improve data clustering quality and, simultaneously, nd appropriated solutions to speci c tasks or interests. In this dissertation, several types of constraints related to data clustering are studied, as well as the main constrained data clustering algorithms. We also developed new methods to combine several data clusterings using restrictions, into a nal data clustering. With the purpose of comparing the constrained data clustering algorithms and evaluating the proposed constrained cluster ensemble methods, two comparative studies are carried out using benchmark datasets.