Agrupamento de gráfico espectral e número ótimo de estimativa de clusters

Ideas Lab Blocked Desbloquear Seguir Seguindo 1 de janeiro

Este post explica o funcionamento do algoritmo de agrupamento de grafos espectrais e, em seguida, analisa uma variante denominada clustering de gráfico auto-ajustado . Essa adaptação tem a vantagem de fornecer uma estimativa para o número ideal de clusters e também para a medida de similaridade entre os pontos de dados. Em seguida, forneceremos uma implementação para a computação heurística eigengap do número ótimo de clusters em um conjunto de dados baseado na maior distância entre valores autógenos consecutivos do laplaciano de dados de entrada.

Agora vamos começar apresentando algumas noções básicas de teoria de grafos.

Matriz de Adjacência (A)

Dado um grafo com n vértices e m nós, a matriz de adjacência é uma matriz quadrada n * n com a propriedade:

A [i] [j] = 1 se houver uma aresta entre o nó i e o nó j, 0 caso contrário

Como A é simétrico, seus vetores próprios são reais e ortogonais (o produto escalar é 0).

Matriz de grau (D)

A matriz de graus é uma matriz diagonal * n com a propriedade

d [i] [i] = o número de arestas adjacentes no nó i ou o grau do nó i

d [i] [j] = 0

Matriz laplaciana (L)

A matriz laplaciana é uma matriz * n definida como: L = D-A

Seus valores eigen são números reais positivos e os vetores eigen são reais e ortogonais (o produto de ponto dos 2 vetores é 0)

Condutância

Uma medida da conectividade de um grupo com o restante da rede em relação à densidade do grupo (o número de arestas que apontam para fora do cluster dividido pela soma dos graus dos nós no cluster). Quanto menor a condutância, melhor o cluster.

Calculando os valores eigen eigen vetores de A com x (vetor n dimensional com os valores dos nós): A * x = lambda * x

O espectro de uma matriz representando o grafo G é um conjunto de autovetores xi do gráfico ordenado pelos correspondentes valores eigen lambda i.

Agora que introduzimos os blocos de construção mais importantes da teoria dos grafos, estamos prontos para resumir as etapas de agrupamento espectral:

  1. Calcule a matriz Laplaciana L do gráfico de entrada G
  2. Calcule os valores eigen (lambda) e vetores próprios (x) tais que

L * x = lambda * x

3. Selecione n autovetores correspondentes aos maiores autovalores e redefina o espaço de entrada como um subespaço dimensional

4. Encontrar clusters neste subespaço usando vários algoritmos de clustering, como k-means

Também é possível usar, em vez da matriz de adjacência definida acima, uma matriz de afinidade que determina quão próximos ou semelhantes são 2 pontos em nosso espaço. Conforme definido na implementação do sklearn:

 similaridade = np.exp (-beta * distance / distance.std ()) 

Um bom recurso demonstrando a criação da matriz de afinidade é este vídeo do youtube.

O cluster espectral e a propagação de afinidade foram implementados em python. Este caderno de jupiter mostra uma rápida demonstração do seu uso.

 clustering = SpectralClustering (n_clusters = nb_clusters, assign_labels = "discretizar", random_state = 0) .fit (X) 
y_pred = clustering.labels_
plt.title (resultados de cluster espectrais f ')
plt.scatter (X [:, 0], X [:, 1], s = 50, c = y_pred);

A aglomeração espectral é uma técnica conhecida por ter um bom desempenho, particularmente no caso de clusters não-gaussianos, onde os algoritmos de cluster mais comuns, como o K-Means, não dão bons resultados. No entanto, ele precisa receber o número esperado de clusters e um parâmetro para o limite de similaridade.

Aglomeração espectral auto-ajustável

A idéia por trás do agrupamento espectral de auto-ajuste é determinar o número ideal de agrupamentos e também a métrica de similaridade ?i usada no cálculo da matriz de afinidade.

Como explicado neste artigo, a matriz de afinidade é definida como

onde d (si, sj) é alguma função de distância, freqüentemente apenas a distância euclidiana entre os vetores si e sj. ? é o parâmetro de escala e é uma medida da similaridade entre os pontos. Geralmente é selecionado manualmente. Ele também pode ser configurado automaticamente executando o clustering várias vezes com valores diferentes e selecionando aquele que produz o cluster menos distorcido. Este artigo sugere calcular um parâmetro de escalonamento local ?i para cada ponto de dados si em vez de um único parâmetro de escalonamento. O artigo propõe analisar a vizinhança de cada ponto si e assim definir: ?i = d (si, sK) onde sK é o vizinho K do ponto si. Isso é ilustrado na figura abaixo, tirada do artigo original, para um valor de K = 7.

A matriz de afinidade com escala local pode ser implementada da seguinte forma:

Uma segunda maneira de estimar o número de clusters é analisar os autovalores (o maior autovalor de L será um autovalor repetido de magnitude 1 com multiplicidade igual ao número de grupos C. Isso implica que se poderia estimar C contando o número de autovalores igualando 1).

Como mostrado no papel:

Outro tipo de análise pode ser realizado nos autovetores, mas não está no escopo deste post.

Eigengap heurística para encontrar o número ideal de clusters

Este artigo Um tutorial sobre cluster espectral – Ulrike von Luxburg propõe uma abordagem baseada na teoria das perturbações e na teoria dos grafos espectrais para calcular o número ideal de agrupamentos. A heurística de Eigengap sugere que o número de clusters k é geralmente dado pelo valor de k que maximiza o eigengap (diferença entre autovalores consecutivos). Quanto maior esse eigengap, mais próximos os autovetores do caso ideal e, portanto, melhores trabalhos de agrupamento espectral.

O código base para este post pode ser encontrado no Github .

Recursos

  1. https://www.youtube.com/watch?v=P-LEH-AFovE
  2. https://papers.nips.cc/paper/2619-self-tuning-spectral-clustering.pdf
  3. http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf