Dados não tem componentes ou atributos - são atômicos
O que é importante é a relação entre os dados (relacionais) ou dados são nós de um grafo (sem estrutura interna) e o importante são as arestas que ligam estes nós
monopartido - só há um tipo de dado e relações entre eles. Pessoas, e uma aresta se elas já se encontraram fisicamente.
Bipartido - há 2 tipos de dados e só há relação entre um tipo e outro (e não entre nos do mesmo tipo). Pessoas e produtos, e uma aresta entre pessoas e produtos se a pessoa comprou o produto ou nao. Há poucos algoritmos para grafos bi-partidos
simétrico ou nao direcionado: arestas nao direcionadas
assimetrico ou direcionado: ex paginas web, se uma aponta para outra
A maioria dos algoritmos é para grafo simétricos/não direcionados.
0/1 : a aresta existe ou nao existe (pagina web)
valorado: aresta tem um valor associado (0 se nao existe). Exemplo numero de emails que uma pessoa mandou para outra)
para arestas valorados, a medida pode significar uma noção de similaridade - quanto maior o número mais parecidos/juntos os dados. Ex: numero de emails enviados
ou pode significar uma medida de distancia ou dissimilaridade - quanto maior o número, menos parecidos menos juntos devem ser os dados.
Alguns algoritmos assumem uma medida de similaridade outros de distancia - é preciso ficar atento a isso.
normalmente se os dados são “originais” as medidas são de similaridade (emails trocados, estrelas na avaliação do produto, etc).
grafos 0/1 é uma medida de similaridade
para converter: dist = \frac{1}{sim} ou dist = \max(sim) - sim ou dist= e^{\frac{-sim}{\sigma}}
os dados originais podem ser assimétricos (uma pagina aponta para outra) mas o algoritmos pode pedir uma medida simétrica. Conversões usuais:
s_{ij} = \frac{a_{ij}+a_{ji}}{2}
s_{ij} = \sqrt{a_{ij} a_{ji}}
Calcule as distancias entre todos os pares de pontos - um grafo simétrico, completo com medida de dissimilaridade. (incomum)
Determine para cada ponto os k vizinhos mais próximos e compute uma similaridade baseado na distancia ate este vizinho (ou similaridade = 1). Para os outros pontos (nao vizinhos) a similaridade é 0 (k-NN grafo)
Determine para cada ponto, os vizinhos que estão a uma distancia menor que \epsilon e compute uma similaridade baseado na distancia ate este vizinho. Para os outros pontos (nao vizinhos) a similaridade é 0 (\epsilon-neighborhood grafo)
Mutual knn graph - para cada ponto, a esta conectado a b se tanto a esta entre os k- vizinhos de b como b esta entre os k-vizinhos de a.
Algoritmos que nao criam “pontos novos”(media dos pontos do cluster) Não da para criar “pontos novos” num grafo.
k-medoids funciona em grafos pois não “cria” centros no espaço. Usa dissimilaridade mas pode ser usado com similaridade. Grafos simetricos
clusterização hierárquica (single, average e complete linkage) só usa a distancia entre pontos e portanto pode ser usada em grafos (Ward nao funciona pois ele usa o “centro”do cluster novo) . Grafos simetricos
Arvore geradora minima (minimum spanning tree) é uma arvore de menor soma das distancias que passa por todos os nós do grafo https://en.wikipedia.org/wiki/Minimum_spanning_tree
determine a MSF e remova os k maiores arestas da MST - sobram k clusters https://www.researchgate.net/publication/322634343_Minimum_spanning_tree_release_under_differential_privacy_constraints/figures?lo=1
variações usam a distribuição das distancias no MST para cortar apenas arestas com distancias “grandes” (outliers)
similaridade simétrica.
Cortes no grafo que minimizam a soma da similaridade das arestas contadas
S(i,j) é a similaridade entre i e j (=S(j,i).
o custo de separar um conjunto de nós A é \sum S(i,j) onde i \in A e k \notin A
o volume de um conjunto de nós A é vol(A) = \sum S(i,j) i e j \in A.
Duas definições de clusterização espectral:
mincut: minimize cut(A_1,A_2, \ldots A_k) = \frac{1}{2} \sum_i^k custo(A_i)
mincut pode gerar clusters de tamanho muito diferentes
normalized cut = Ncut = minimize \sum_i^k \frac{custo(A_i)}{vol(A_i)}
normalized cut gera clusters de tamanho mais balanceado (tamanho medido por vol()
Mincut e Ncut são problemas difíceis de resolver. mas há aproximação a solução usando “autovetores do Laplaciano do grafo”
https://en.wikipedia.org/wiki/Laplacian_matrix
Laplaciano -> mincut -> L = D - A
Laplaciano normalizado -> nCut -> L = I - D^{-1/2} A D^{-1/2}
Laplaciano random walk -> ??? -> L = I - D^{-1} A
Tutorial https://people.csail.mit.edu/dsontag/courses/ml14/notes/Luxburg07_tutorial_spectral_clustering.pdf
https://towardsdatascience.com/spectral-clustering-for-beginners-d08b7d25b4d8
https://towardsdatascience.com/spectral-clustering-aba2640c0d5b
Autovetores de um grafo são padroes (valores nos vertices) que se repetem (multiplicados por uma constante - autovalor) considerando o grafo como uma rede de transmissão.
se os grafo é desconectado (por exemplo em 2 componentes) os
Voce pode usar isso para escolher o k - k autovalores devem ser aprox 0 se há k componentes no grafo.
escolher os k menores autovetores (que corresponde aos k menores autovalores).
Cada dimensão dos autovetores corresponde a 1 ponto dos dados. Voce quer clusterizar as **dimensões* dos autovetores. (quem sao os pontos em cada componente “desconectado” do grafo.
para pontos no espaco:
converte os pontos para 1 grafo usando ao NN-graph
computa os k menores autovetores do Laplaciano
monte uma matriz de dados com os autovetores (de pe) - cada dado o valor dos autovetores num mesmo nó -
Clusterize essa matriz usando k-means - cada clusteres das dimensões dos autovetores são os clusteres dos pontos de dados originais.
https://rdrr.io/cran/kernlab/man/specc.html em R
https://www.rdocumentation.org/packages/kknn/versions/1.3.1/topics/specClust em R (varios laplacianos)
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html sklearn