Defesa de Tese de Doutorado de Augusto Pizano Vieira Beltrão, 04/09/25, 10h, por videoconferência
Link para defesa: meet.google.com/wvm-gbcg-szi
Algoritmos de Otimização Aplicados ao Problema do Comitê de Agrupamentos
Resumo:
A evolução computacional observada nas últimas décadas, aliada ao surgimento de inúmeras aplicações reais em Medicina, Estatística, Marketing, dentre outras, cuja resolução remete a problemas de agrupamento de difícil solução, têm motivado a pesquisa e desenvolvimento de diversos algoritmos de agrupamento. Todavia, de acordo com o algoritmo adotado, com a estrutura da base de dados associada à aplicação, por exemplo, com presença de grupos esféricos, além de restrições específicas do problema, podem ser produzidas diferentes partições, com diferentes níveis de qualidade – à luz de índices de validação.
Por sua vez, uma boa alternativa para melhorar a qualidade da partição produzida, diz respeito ao uso do Comitê de Agrupamentos (CA), que combina diferentes partições de uma base de dados – obtidas a partir de diferentes algoritmos ou por um por um mesmo algoritmo, variando-se um de seus parâmetros -, produzindo uma única partição consenso. De acordo com a literatura, tal partição é menos sensível a ruídos nos dados e de melhor qualidade, segundo diversos índices de validação, quando comparada às partições base inicialmente usadas na combinação.
Nesta tese, tendo por base a aplicação de CA, foram propostos dois algoritmos genéticos, denominados BRKGA-CE e GA-CE, que fazem uso de três diferentes estratégias para geração das partições base e incorporam uma nova função consenso, responsável pela determinação da partição consenso. Para avaliar esses algoritmos, foram realizados dois experimentos, em que, no primeiro, foram utilizadas 20 bases de dados e seis algoritmos relevantes da literatura – contemplando um total de 18 variantes -, aplicando-se dois conhecidos índices de validação externa, utilizados na literatura de comitê – Normalized Mutual Information (NMI) e Adjusted Rand Index (AR). No primeiro experimento, verificou-se que as soluções produzidas pelos dois algoritmos estavam constantemente entre as melhores, considerando as 3 estratégias de geração de comitê, frente aos principais algoritmos da literatura, ratificando a sua eficácia quanto à produção de partições de boa qualidade. No segundo experimento, os resultados do BRKGA-CE foram comparados com os resultados de um trabalho da literatura, baseado no uso de um algoritmo genético (AG), além de outros algoritmos. Nesta comparação foi considerado um conjunto diferente de partições base, geradas conforme o referido trabalho da literatura.
Abstract:
The computational evolution observed in recent decades, combined with the emergence of numerous real applications in Medicine, Statistics, Marketing, among others, where the resolution refers to clustering problems with difficult solutions, has motivated the research and development of various clustering algorithms. However, depending on the adopted algorithm and the structure of the dataset associated with the application, for example, with the presence of spherical groups, as well as specific problem constraints, different partitions can be produced with varying levels of quality-according to validation indices.
In turn, a good alternative to improve the quality of the produced partition is the use of the Cluster Ensemble (CE), which combines different partitions of a dataset – obtained from different algorithms or from the same algorithm by varying one of its parameters – producing a single consensus partition. According to the literature, this partition is less sensitive to noise in the data and of better quality, according to various validation indices, when compared to the initial base partitions used in the combination.
In this thesis, based on the application of CE, two genetic algorithms were proposed, named BRKGA-CE and GA-CE, which use three different strategies for generating base partitions and incorporate a new consensus function, responsible for determining the consensus partition. To evaluate these algorithms, two experiments were conducted. In the first, 20 datasets and six relevant algorithms from the literature were used – covering a total of 18 variants – applying two well-known external validation indices used in cluster ensemble literature: Normalized Mutual Information (NMI) and Adjusted Rand Index (AR). In the first experiment, it was found that the solutions produced by the two algorithms were consistently among the best, considering the three committee generation strategies, compared to the main algorithms in the literature, confirming their effectiveness in producing high-quality partitions. In the second experiment, the results of BRKGA-CE were compared with the results of a study from the literature, based on the use of a genetic algorithm (GA), as well as other algorithms. In this comparison, a different set of base partitions was considered, generated according to the aforementioned study.
Banca examinadora:
Prof. Luiz Satoru Ochi, UFF – Presidente
Prof. Igor Machado Coelho, UFF
Prof. Fábio Protti, UFF
Prof. José André de Moura Brito, IBGE
Prof. Gustavo Silva Semaan, UFF
Prof. Gustavo da Silva Ferreira, IBGE
Prof. Nelson Maculan Filho, UFRJ
Prof. Marcone Jamilson Freitas Souza, UFOP