Qual é a diferença entre os autovetores da matriz de afinidade e os autovetores laplacianos do gráfico no contexto do agrupamento espectral?

8

No agrupamento espectral, é prática padrão resolver o problema do vetor próprio

euv=λv

onde é o gráfico Laplaciano, é o vetor próprio relacionado ao valor próprio .euvλ

Minha pergunta: por que se preocupar em pegar o gráfico Laplaciano? Eu não poderia simplesmente resolver o problema do vetor próprio para o próprio gráfico (matriz de afinidade), como o cara fez neste vídeo ?

PS: Fiz a mesma pergunta no CrossValidated, mas acho que esse é um canal mais apropriado. Perdoe-me se eu estiver errado.

machine-learning clustering graphs felipeduque
fonte
Link do vídeo está quebrado :(
wcochran 22/04

Respostas:

4

O conceito é o mesmo, mas você está ficando confuso com o tipo de dados. Clustering espectral como Ng et al. O explicação é sobre o agrupamento de dados padrão, enquanto a matriz laplaciana é uma matriz derivada de gráfico usada na teoria algébrica de grafos.

Portanto, o ponto é que sempre que você codifica a semelhança de seus objetos em uma matriz, essa matriz pode ser usada para agrupamento espectral.

Se você tiver dados padrão, ou seja, uma matriz de recurso de amostra, poderá encontrar a proximidade ou afinidade ou o que quiser chamá-lo como matriz e aplicar agrupamento espectral.

Se você tiver um gráfico, essa afinidade seria algo como matriz de adjacência, matriz de distância ou matriz de Laplacialn e resolver a função própria para essa matriz fornece o resultado correspondente.

O ponto sobre o uso de Laplaciano em vez de adjacência é manter a chamada matriz de afinidade positiva semi-definida (e a matriz Laplaciana normalizada é uma escolha melhor, pois fornece valores próprios normalizados entre 0 e 2 e revela a estrutura do gráfico muito melhor).

Portanto, a longa história é que, desde que você tenha uma matriz contendo a afinidade de seus dados, poderá usar o agrupamento espectral em geral. A diferença está nos detalhes (ig propriedade do Laplaciano normalizado que acabei de mencionar)

Kasra Manshaei
fonte
Sim, acho que estou um pouco confuso. Ainda não está claro para mim. Se eu tiver dados padrão (sem afinidade), posso transformá-lo em uma matriz de afinidade A tomando a distância em pares entre as amostras de dados. Agora, se vejo A como um gráfico, posso pegar o Laplaciano e resolver os vetores próprios e obter uma solução; se não vejo A como um gráfico, poderia simplesmente resolver os vetores próprios da matriz (PCA) e obter uma solução. Qual é a diferença?
Felipeduque 13/12/2015
Eu li sua pergunta novamente. A resposta são as propriedades (por exemplo, a que mencionei na minha resposta). A matriz laplaciana fornece uma melhor decomposição. No entanto, você pode, exclusivamente, executar a função própria para quaisquer matrizes relacionadas à similaridade e obter alguns resultados diferentes apenas em detalhes. Por exemplo, sobre o PCA que você mencionou: O PCA pega a matriz de covariância para capturar onde a variação é alta, mas, em geral, o conceito segue a mesma direção que as outras técnicas de decomposição espectral. Eu vou corrigir minha resposta assim que eu vejo algumas frases "Saturday Night";)
Kasra Manshaei