Meta-analysis of clustering problem instances and techniques in machine learning
Data
2022-02-11
Autores
Fernandes, Luiz Henrique dos Santos 
Tipo
Tese de doutorado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
A seleção do algoritmo mais efetivo a ser aplicado em determinada instância, baseado nas características desta, é um problema que vem sendo estudado na área de meta-aprendizado. Nesta abordagem, o propósito é estabelecer uma relação entre os atributos dos problemas e o desempenho de um conjunto de algoritmos que podem ser utilizados para resolvê-los. Meta-aprendizado vem sendo empregado em diversos problemas de Aprendizado de Máquina, como classificação, regressão, otimização e agrupamento de dados, por exemplo. Agrupamento de dados, ou data clustering, é um problema exigido em várias aplicações, desde segmentação de mercado até análise de dados baseados no genoma. No entanto, a definição de um agrupamento, ou cluster, não é única. Existem vários algoritmos com diferentes vieses que encontram diferentes tipos de estruturas nos dados. Por exemplo, pode-se maximizar a separabilidade do clusters ou encontrar regiões densas no espaço para definição dos clusters. A finalidade da presente pesquisa é avaliar objetivamente o desempenho de algoritmos de agrupamento em Aprendizado de Máquina e analisar o impacto da escolha de instâncias de teste por meio de uma abordagem baseada em um framework de espaço de instâncias que foi aplicado com sucesso em problemas de classificação e regressão. Durante o estudo, foram abordados diversos aspectos interessantes do problema de agrupamento que possibilitam a exploração das propriedades e limitações das instâncias de teste. Foi proposta, também, uma metodologia para geração de novas instâncias de teste para problemas de agrupamento, no intuito de preencher e diversificar o espaço de instâncias. Com isso, pôde-se analisar e compreender as relações das instâncias com o desempenho dos diversos algoritmos de agrupamento de dados disponíveis atualmente, de forma a revelar as forças e fraquezas dos algoritmos em relação ao grau de dificuldade inerente às variadas instâncias do problema de agrupamento de dados.
The selection of the most effective algorithm to be applied in a given instance, based on its characteristics, is a problem that has been studied in the meta-learning area. In this approach, the purpose is to establish a relationship between the features of the problems and the performance of a pool of algorithms that can be used to solve them. Meta-learning has been used in several Machine Learning problems, such as classification, regression, optimization and data clustering, for example. Data clustering is a required problem in many applications, from market data segmentation to genome-based data analysis. However, the definition of a cluster is not unique. There are several algorithms with different biases that find different types of structures in the data. For instance, one can maximize the separability of the clusters or find dense regions in space to define the clusters. The purpose of this research is to objectively evaluate the performance of clustering algorithms in Machine Learning and analyze the impact of the choice of test instances through an approach based on an instance space framework that was successfully applied in classification and regression problems. During the study, several interesting aspects of the clustering problem were addressed that enable the exploration of the properties and limitations of test instances. A methodology for generating new test instances for clustering problems was also proposed, in order to fill and diversify the instance space. With this, it was possible to analyze and understand the relationships of instances with the performance of the various data clustering algorithms currently available, for the purpose of to reveal the strengths and weaknesses of the algorithms in relation to the degree of difficulty inherent in the various instances of the clustering problem.
The selection of the most effective algorithm to be applied in a given instance, based on its characteristics, is a problem that has been studied in the meta-learning area. In this approach, the purpose is to establish a relationship between the features of the problems and the performance of a pool of algorithms that can be used to solve them. Meta-learning has been used in several Machine Learning problems, such as classification, regression, optimization and data clustering, for example. Data clustering is a required problem in many applications, from market data segmentation to genome-based data analysis. However, the definition of a cluster is not unique. There are several algorithms with different biases that find different types of structures in the data. For instance, one can maximize the separability of the clusters or find dense regions in space to define the clusters. The purpose of this research is to objectively evaluate the performance of clustering algorithms in Machine Learning and analyze the impact of the choice of test instances through an approach based on an instance space framework that was successfully applied in classification and regression problems. During the study, several interesting aspects of the clustering problem were addressed that enable the exploration of the properties and limitations of test instances. A methodology for generating new test instances for clustering problems was also proposed, in order to fill and diversify the instance space. With this, it was possible to analyze and understand the relationships of instances with the performance of the various data clustering algorithms currently available, for the purpose of to reveal the strengths and weaknesses of the algorithms in relation to the degree of difficulty inherent in the various instances of the clustering problem.
Descrição
Citação
FERNANDES, Luiz Henrique dos Santos. Meta-analysis of Clustering Problem Instances and Techniques in Machine Learning. 2022. 155f. Thesis of Doctor of Science – Instituto Tecnológico de Aeronáutica and Universidade Federal de São Paulo, São José dos Campos.