Clustering espectral

Abstract

El clustering espectral es una técnica de clustering que tiene sus orígenes en la teoría de grafos. Este método asocia conjuntos de datos a los nodos de un grafo e identifica agrupaciones de nodos en este grafo basándose en las aristas que los conectan. Nuestro primer objetivo del trabajo consiste en presentar los diferentes tipos de grafos que podemos construir partiendo de nuestro conjunto de datos. Puesto que este método utiliza información de los autovalores de determinadas matrices construidas a partir del grafo, el segundo de los objetivos planteados es aprender a construir estas matrices y a interpretar su espectro. A lo largo del segundo capítulo estudiaremos diferentes algoritmos que nos permiten utilizar los autovectores asociados a estas matrices para asignar nuestros datos a clusters. La elección de la matriz que usemos a la hora de calcular estos autovalores nos llevará a diferentes algoritmos de clustering espectral. En el tercer capítulo introduciremos una interpretación en términos de probabilidad y procesos estocásticos del funcionamiento de estos algoritmos. Finalmente, concluiremos en el cuarto capítulo con la implementación práctica del clustering espectral, tanto a datos generados de manera sintética como a datos reales. Estos últimos nos permitirán presentar una aplicación real del clustering espectral al reconocimento facial.

Spectral clustering is a clustering technique that has its origins in graph theory. This method associates data sets to the nodes of a graph and identifies groups of nodes in this graph based on the edges that connect them. Our first objective is to present the different types of graphs we can construct from our data set. Since this method uses information from the eigenvalues of certain matrices constructed from the graph, the second objective is to learn how to construct these matrices and how to interpret their spectrum. In the second chapter we will study different algorithms that allow us to use the eigenvectors associated with these matrices to assign our data to clusters. The choice of the matrix we use when calculating these eigenvalues will lead us to different spectral clustering algorithms. In the third chapter we will introduce an interpretation in terms of probability and stochastic processes of how these algorithms work. Finally, we will conclude in the fourth chapter with the practical implementation of spectral clustering, both to synthetically generated data and to real data. The latter will allow us to present a real application of spectral clustering to face recognition.