An adaptive evolutionary multi-objective clustering based on the properties of the bases partitions

Abstract

Resumo: Oagrupamento de dados evolutivo multiobjetivo (AEM) é uma técnica moderna de agrupamento de dados em que os conceitos gerais de otimização evolutiva de multiobjetivos são aplicados no problema de agrupamento. O projeto e definição de algoritmos de agrupamento de dados é um problema difícil, no qual a escolha das funções objetivo e definição dos parâmetros de configuração ainda são desafios. Neste estudo, visando compreender esse campo, mapeamos e analisamos as abordagens existentes e avaliamos suas principais características. Esta análise demostrou que, em geral, a escolha das funções objetivo considera apenas as propriedades de agrupamento desejadas, e a maioria das abordagens AEM presentes na literatura não considera aspectos de otimização multiobjetivo, como a direção de busca, em seu projeto. Visando apoiar uma melhor escolha e definição dos objetivos nas abordagens AEM, neste manuscrito propomos uma análise da admissibilidade dos critérios de agrupamento para examinar a direção de busca e avaliar seu potencial em encontrar resultados ótimos. Para tanto, consideramos os fundamentos associados a avaliação de uma função heurística para analisar os critérios de agrupamento de dados e demonstrar como eles podem influenciar a otimização. Como resultado, apresentamos uma análise detalhada das principais funções objetivo encontradas na literatura e avaliamos como a inicialização interfere na sua admissibilidade. Além disso, observamos alguns problemas no projeto de algoritmos estabelecidos, os quais não consideram como a estratégia de inicialização pode impactar na busca em termos das funções objetivo aplicadas. Podendo limitar ou piorar os resultados encontrados na inicialização. Para tratar esta questão propomos o AEMOC(Adaptive Evolutionary Multi-objective Clustering approach based on data properties). Essa abordagem considera a propriedades das partições base para determinar se a otimização é necessária ou não. Para isso, propomos uma métrica para medir o grau de separação dos dados, que estima a qualidade relativa da população inicial gerada pelo agrupamento de árvores geradoras mínimas. Além disso, esta avaliação permite definir uma seleção offline de funções objetivas e configurações de parâmetros do algoritmo multiobjetivo. O AEMOC apresentou resultados promissores considerando um conjunto diversificado de conjuntos de dados artificiais e reais, considerando dois aspectos: obteve sucesso na definição da qualidade relativa das partições de base e forneceu melhores resultados de agrupamento do que as abordagens AEM de referência.

Abstract: Evolutionary multi-objective clustering (EMOC) is a modern clustering technique in which the general concepts of evolutionary multi-objective optimization are applied to the clustering problem. The design and definition of the clustering are difficult problems in which the choice of the objective functions and parameter setting of the algorithms are still challenges. In our study, aiming to understand this field, we mapped and analyzed the existing approaches and evaluated their main characteristics. This analysis showed that many different objective functions and initialization strategies have been applied in EMOC approaches. In general, the choice of the objective functions only considers the desired clustering properties, and most EMOC approaches present in the literature do not consider aspects of multi-objective optimization, such as the search direction, in their design. Aiming to support a better choice and definition of the objectives in the EMOC approaches, we introduce an analysis of the clustering criteria admissibility to examine the search direction and evaluate their potential for finding optimal results. We consider the fundamentals of the evaluation of a heuristic function to analyze the clustering criteria and demonstrate how they can influence the optimization. As a result, this study provides a detailed analysis of the main objective functions found in the literature and evaluates how the initialization interferes with their admissibility. Besides that, we observed some issues in the design of established algorithms that do not consider the impact of the initialization strategy on the search when determined objective functions are applied. This aspect can limit the clustering or worsen the results found in the initialization. To amend this matter, in this manuscript, we propose the AEMOC (adaptive evolutionary multi-objective clustering approach based on data properties). This approach considers the properties of the base partitions to determine whether optimization is required or not. For that, we propose a metric to measure the data separation degree that estimates the relative quality of the initial population generated by minimum spanning tree clustering. Furthermore, this evaluation makes it possible to define an offline selection of objective functions and parameter settings for the multi-objective algorithm. AEMOC presented promising results considering a diverse set of artificial and real-life datasets, considering two aspects: it succeeded in the definition of the relative quality of the base partitions, and it provided better clustering results than reference EMOC approaches.