Métodos espectrais para particionamento de dados e aplicações

Abstract

Atualmente temos uma grande quantidade de dados disponíveis e é uma tarefa muito difícil interpretá-los. Desta maneira, classificar esses dados em um pequeno número de grupos baseado em suas afinidades pode ajudar a obter informações valiosas sobre eles. Este é o objetivo dos algoritmos de clusterização (particionamento), que buscam dividir dados em um determinado número de clusters (grupos) de forma que dados que possuam mais afinidade fiquem no mesmo cluster e dados com menos afinidade fiquem em clusters diferentes. Nesta dissertação trabalhamos com métodos espectrais para particionamento de dados, que usam ingredientes de álgebra linear e teoria espectral de grafos. Em nossa primeira contribuição apresentamos os resultados que obtivemos em duas aplicações das técnicas espectrais. A primeira aplicação está relacionada ao mercado financeiro, onde apresentamos uma estratégia em que clusterizamos um conjunto de ações e utilizamos critérios relacionados ao factor investing para montar portfólios. A segunda aplicação está relacionada à pandemia da COVID-19, onde obtivemos uma classificação do estado do Rio Grande do Sul em três clusters (regiões) de risco, alto risco, médio risco e baixo risco. Terminamos apresentando um novo algoritmo de clusterização espectral, mais especificamente desenvolvemos uma nova medida de similaridade. A nossa medida apresenta uma série de vantagens: (1) o usuário não precisa definir nenhum parâmetro para utilizar a medida, tornando-a fácil de aplicar; (2) a medida é invariante sob translações e expansões; (3) a medida apresentou bom desempenho em conjuntos de dados sintéticos e, em situações reais, apresentou desempenho similar a outros métodos existentes, que precisam de pelo menos um parâmetro de escala definido pelo usuário para serem utilizados.

Nowadays we have a large amount of data available and it is a very difficult task to interpret it. In this way, classifying this data into a small number of groups based on their affinities can help to obtain valuable insight about them. This is the aim of clustering (partitioning) algorithms, which seek to split data into a certain number of clusters (groups) so that data with more affinity lie in the same cluster and data with less affinity lie in different clusters. In this dissertation we work with spectral methods for data partitioning, which use ingredients from linear algebra and spectral graph theory. In our first contribution we present the results we obtained in two applications of spectral techniques. The first application is related to the financial market, where we present a strategy in which we cluster a set of stocks and use criteria related to the factor investing to build portfolios. The second application is related to the COVID-19 pandemic, where we obtained a classification of the state of Rio Grande do Sul in three clusters (regions) of risk, high risk, medium risk and low risk. We finish presenting a new spectral clustering algorithm, more specifically, we developed a new similarity measure. Our measure has a number of advantages: (1) the user does not need to define any parameters to use the measure, making it easy to apply; (2) the measure is invariant under translations and expansions; (3) the measure performed well in synthetic data sets and, in real situations, it performed similarly to other existing methods, which need at least one user-defined scale parameter to be used.