Métodos de Agrupamentos baseados em Grafos

Métodos de Agrupamentos baseados em GrafosLucas Batista Leite de SouzaMestrado em Ciência da Computação Universidade Federal de Uberlândia

Agenda• 1- Introdução• 2- Noções da Teoria dos Grafos.• 3- Algoritmo CHAMALEON• 4- Algoritmo Jarvis-Patrick (talvez)

Introdução• Os algoritmos de agrupamento baseado em grafos representam os

dados e sua proximidade através de um grafo G(V,E), onde V = {v1,v2,...,vn} é o conjunto de vértices e E é o conjunto de arestas.

• Cada vértice representa um elemento do conjunto de dados e a existência de uma aresta conectando dois vértices é feita com base na proximidade entre os dois objetos.

• A maneira mais simples de estabelecer as ligações entre os vértices é conectar cada vértice aos (n-1) vértices restantes, onde o peso da aresta indica a similaridade entre os dois objetos que a mesma conecta.

• Um cluster é definido como um subgrafo conexo do grafo inicial.

Exemplo:• Considere um banco de dados com 4 objetos (a, b, c, d).• Foi construída a matriz de similaridade para os quatro

objetos.• A medida de similaridade pode variar dependendo do problema.

• O grafo para esses dados pode ser construído em seguida.

a b c da 0 3 3,1 1

b 3 0 1 1c 3,1 1 0 3d 1 1 3 0

Exemplo:• Um algoritmo de clusterização baseado em grafos poderia

achar dois subgrafos colocados abaixo. • Cada subgrafo corresponde a um cluster.

Cluster C1

Cluster C2

Noções da Teoria dos Grafos• A Teoria dos Grafos oferece uma maneira de lidar com a divisão dos

vértices de um grafo em grupos distintos.

• O particionamento de grafos consiste em dividir o conjunto de vértices V em dois subconjuntos S e (V-S). Essa divisão é chamada corte.

• No exemplo abaixo o corte é composto pelas arestas a, b e c.

Noções da Teoria dos Grafos• A busca pelo corte mínimo em um grafo depende da escolha da

função a ser minimizada.

• No caso das arestas do grafo possuírem peso, o tamanho do corte é dado pela soma dos pesos das arestas que conectam vértices em subconjuntos diferentes. • A função a ser minimizada nesse caso é soma dos pesos das arestas.

• No exemplo abaixo o tamanho do corte mínimo é 2+2+2=6.

Noções da Teoria dos Grafos• Essa abordagem que procura minimizar a soma do peso das arestas

do corte favorece cortes que produzem conjuntos de vértices unitários (i.e. |S| = 1 ou |V-S| = 1).• Isso não é interessante para a clusterização, afinal não queremos clusters

unitários.

• Uma alternativa é usar uma variação do corte mínimo que busque balancear a cardinalidade dos conjuntos S e (V-S). • Essa abordagem é mais interessante para os propósitos da clusterização.

• Encontrar essa versão balanceada do corte é NP-completo, porém diversas heurísticas foram desenvolvidas para buscar uma aproximação desse corte em tempo polinomial [3].• Ex.: Método baseado na matriz Laplaciana do grafo. Detalhes sobre esse

método se encontram em [3].

Noções da Teoria dos Grafos• Por que particionar o grafo usando o corte mínimo?• Estamos considerando que quanto maior o peso da aresta, maior

a similaridade entre os objetos que ela conecta. Assim, o corte mínimo separa objetos pouco similares em dois conjuntos distintos.

Noções da Teoria dos Grafos• Grafo Esparso• Informalmente: Um grafo é dito esparso se ele possui “poucas”

arestas. • Formalmente: Um grafo esparso é um grafo G(V,E), no qual |E|=

O(|V|).

CHAMALEONG. Karypis et al. (1999)

Algoritmo de Clusterização Hierárquico com Modelagem Dinâmica

Motivação• A maior parte dos algoritmos de clusterização encontra clusters de

acordo com um modelo estático (global).• Muitas vezes o modelo pode não capturar adequadamente as

características dos clusters. • A maior parte desses algoritmos não funciona bem quando

existem clusters de diversas formas, densidades e tamanhos. • Por exemplo: • O algoritmo K-Means assume que os clusters serão

globulares. Mas e se existirem clusters com vários formatos?• O algoritmo DBSCAN não produz resultados confiáveis

quando os clusters apresentam densidades muito diferentes entre si.

Motivação• O exemplo abaixo mostra que o DBSCAN não foi capaz de

agrupar corretamente os dados presentes na grande elipse (intuitivamente a grande elipse constitui um único cluster).

MinPts=4Eps=0,4

Imagens Retiradas de [2]

Motivação

• O exemplo abaixo mostra que o CURE não foi capaz de encontrar corretamente os clusters.

Número de clusters especificado(k)=11α=0,3Número de pontos representantes = 10


Motivação• Em suma: A maior parte dos algoritmos se baseia em um modelo

estático e não usa informações sobre a natureza de clusters individuais para fazer o merge.

• Outro problema é que alguns desses algoritmos consideram apenas uma das duas medidas de similaridade colocadas abaixo, o que pode levar a merges incorretos de clusters.• Interconectividade Absoluta.• Proximidade Absoluta.

Medidas de Similaridade entre clusters

• Proximidade Absoluta: Consiste em calcular a distância entre os dois clusters. • Uma maneira de fazer isso é calcular a distância entre todos os

pares de pontos dos dois clusters, onde cada ponto pertence a um cluster diferente. Algumas possibilidades:• Considerar que a distância entre dois clusters é a distância

mínima entre todos os pares de dados (distância do vizinho mais próximo).

• Considerar que a distância entre dois clusters é a distância máxima entre todos os pares de dados (distância do vizinho mais distante).

• Considerar que a distância entre dois clusters é a média das distâncias entre todos os pares de dados (distância média).

Medidas de Similaridade entre clusters• Exemplos:

Abordagem Distância Mínima

Abordagem Distância Máxima

Abordagem Distância Média



• O uso da proximidade absoluta como medida de similaridade pode levar algoritmos a unirem clusters de maneira errada.

• Exemplo:

• Considere que estejamos usando a distância do vizinho mais próximo.• Qual dos dois pares de clusters mergear?• Intuitivamente iríamos mergear o par (b).• Porém, um algoritmo que se baseia apenas na proximidade absoluta, irá

mergear equivocadamente o par (a), visto que d1 < d2.



• Interconectividade Absoluta: Também conhecida por agregação de similaridade entre dois clusters.• Nesse caso, dois pontos a e b possuem uma conexão (aresta) caso

a similaridade entre eles exceda algum limite mínimo.• A interconectividade absoluta entre dois clusters é dada pela

soma dos pesos das arestas entre pares de dados, um de cada cluster.

• A ideia é que sub-clusters pertencentes a um mesmo cluster tenham alta interconectividade.

• Em geral a interconectividade entre pares de clusters formados por muitos elementos é alta, por isso muitos algoritmos utilizam alguma forma de normalização desse valor.

Medidas de Similaridade entre clusters• Exemplo:

• Considere que os pontos em vermelho constituam um cluster.• Considere que os pontos em preto constituam outro cluster.• Nesse caso a interconectividade absoluta entre os dois clusters

seria 5+9+6 = 20.


• O uso da interconectividade absoluta como medida de similaridade pode levar algoritmos a unirem clusters de maneira errada.

• Exemplo:

• Suponha que a interconectividade entre os elementos dos clusters verde e azul seja maior que a interconectividade entre os elementos dos clusters azul e vermelho.

• Qual par de clusters devemos mergear?• Intuitivamente iríamos mergear o par azul-vermelho.• Porém, um algoritmo que se baseia apenas na interconectividade

absoluta, irá mergear equivocadamente o par verde-azul.


Overview

• CHAMALEON é um algoritmo de clusterização hierárquico aglomerativo que trata essas dificuldades.

• A ideia central é que dois clusters devem ser mergeados apenas se o cluster resultante é similar aos dois clusters originais.

• Nos dois exemplo anteriores, caso observássemos as características do cluster resultante, em relação aos dois clusters originais, iríamos realizar o merge esperado.

Características-chave• Proximidade e Interconectividade possuem limitações quando usadas como

única medida de similaridade.

• CHAMALEON determina o par de clusters mais similares levando em conta tando a proximidade, quanto a interconectividade entre os clusters.

• Além disso, para medir o grau de interconetividade e proximidade entre cada par de clusters, o algoritmo leva em consideração caractéristicas internas de cada um dos clusters. Esse fator é o que torna o modelo dinâmico.

• O algoritmo pode ser aplicado à dados que contém clusters com características bem variadas (formas, tamanhos, densidades), uma vez que se baseia apenas em características do par de clusters e não em um modelo global.

Funcionamento Geral

• O algoritmo modela os dados em um grafo esparso, onde os nós representam os dados e as arestas a similaridade entre eles.• O algoritmo é formado por duas fases:• 1: Utiliza um algoritmo de particionamento de grafos

para dividir o grafo esparso em pequenos sub-clusters;• 2: Os sub-clusters são combinados de forma a

encontrar os clusters reais.

Funcionamento Geral


Modelando os dados• A partir da matriz de similaridade, os dados do conjunto são

modelados em um grafo esparso, chamado Grafo dos K-vizinhos mais próximos ou Grafo KNN.

• Cada vértice corresponde à um objeto e é ligado aos seus K-vizinhos mais similares.

• O peso da aresta representa a similaridade entre os dois objetos que a mesma conecta.

Modelando os dados• Exemplo:• Considere a matriz de similaridade entre quatro objetos: a, b, c, d.• Considere K=1.

• Ou seja, cada objeto será ligado ao seu vizinho mais próximo.• O vizinho mais próximo do a é o c, pois a similaridade entre ambos é 4.• O vizinho mais próximo do b é o a, pois a similaridade entre ambos é 3.• O vizinho mais próximo do c é o a, pois a similaridade entre ambos é 4.• O vizinho mais próximo do d é o c, pois a similaridade entre ambos é 3.

Grafo KNNK=1

a b c d

a 0 3 4 1

b 3 0 1 1

c 4 1 0 3

d 1 1 3 0

Modelando os dados


Modelando os dados• Razões para usar o Grafo KNN:

• Objetos que são pouco similares entre si não estão conectados no Grafo KNN;

• Captura o conceito de vizinhança dinamicamente;

• Melhora a eficiência computacional (menos arestas para processar).

Particionamento do Grafo KNN• As medidas de similaridade utilizadas pelo Chamaleon (que serão explicadas

posteriormente) apresentam resultados confiáveis apenas quando aplicadas a clusters com um número razoável de elementos.

• Por isso, o Grafo KNN deve ser dividido em sub-clusters com um número razoável de elementos que permita a modelagem dinâmica do algoritmo.

• CHAMALEON encontra os sub-clusters aplicando um algoritmo de particionamento de grafos que divide o grafo inicial em muitas partições de modo que a soma do peso das arestas que ligam as partições (arestas de corte) seja minimizada.• Encontrar um particionamento de corte mínimo significa minimizar a similaridade

entre os clusters.• Idealmente, um objeto deve ter maior similaridade com objetos do seu próprio

cluster do que de outros clusters.

• CHAMALEON utiliza o algoritmo METIS para o particionamento.

Particionamento do Grafo KNN• O objetivo do algoritmo METIS é dividir o Grafo KNN em vários

subgrafos. • Idealmente cada subgrafo gerado deve corresponder a um

sub-cluster de um cluster real.

Particionamento do Grafo KNN• Algoritmo METIS:• Entrada:• Um grafo G esparso (por exemplo um Grafo KNN).• Um parâmetro T que indica o tamanho máximo para os subgrafos que

serão obtidos. • Saída:• Um conjunto de componentes distintos (subgrafos).

• Funcionamento:• Os sub-clusters iniciais são obtidos a partir de um único cluster formado

por todos os dados do Grafo KNN.• Repetidamente o maior cluster é dividido.• Esse processo chega ao fim quando o maior cluster possuir tamanho

menor que T.• O valor de T deve ser grande o suficiente para permitir o cálculo das

medidas de similaridade usadas pelo CHAMALEON.

Particionamento do Grafo KNN• Exemplos de particionamentos realizados pelo METIS na

primeira iteração, para dois conjuntos diferentes de dados.

• Mais informações sobre o algoritmo METIS em [5].


Particionamento do Grafo KNN

• Ao final desse algoritmo temos um grande número de subgrafos de tamanho aproximadamente igual, e bem conectados (com pontos muito similares uns aos outros).

• O objetivo é que cada partição (subgrafo) contenha na sua maioria pontos pertencentes à um único cluster real.

Modelando a similaridade entre clusters

• A similaridade entre dois clusters é determinada de maneira dinâmica.

• CHAMALEON considera duas medidas de similaridade: • Interconectividade relativa (RI)• Proximidade relativa (RC)

• Dois clusters são unidos caso apresentem alta interconectividade e seus elementos estejam próximos, o que é traduzido em altos valores de RI e RC.


• Interconectividade Relativa (RI):• A ideia é juntar clusters apenas se os pontos no cluster

resultante estão quase tão fortemente conectados uns aos outros assim como estão os pontos nos clusters originais.

• A interconectividade absoluta entre dois clusters Ci e Cj (|EC(Ci,Cj)|) é definida como a soma dos pesos das arestas (do grafo KNN) que ligam os dois clusters.• Essas arestas estavam no Grafo KNN original mas foram removidas

devido à execução do METIS.

• A interconectividade interna de um cluster Ci (|EC(Ci)|)é obtida através da soma dos pesos das arestas que cruzam o corte mínimo que divida o cluster em duas partes aproximadamente iguais (bisseção mínima).


• Interconectividade Relativa (RI):• Para obter a Interconectividade Relativa entre os clusters Ci e Cj

(RI(Ci,Cj)), deve-se normalizar a interconectividade absoluta (|EC(Ci,Cj)|), em relação à interconectividade interna dos clusters Ci (|EC(Ci)|) e Cj (|EC(Cj)|). Assim, chega-se a equação:


• Interconectividade Relativa (RI):• Exemplo: Considere os dois clusters a seguir:

Cluster A Cluster B


• Primeiramente iremos calcular a interconectividade absoluta entre os clusters.• Considere que no Grafo KNN (antes da execução do METIS) existiam as

seguintes arestas que permitam conectar pontos azuis a pontos vermelhos:• aresta b-e, com peso 1• aresta b-h, com peso 0,9• aresta d-h, com peso 0,95• aresta d-i, com peso 1,1


• Assim, a interconectividade absoluta é calculada:

|EC(A,B)| = 1+ 0,9 + 0,95 + 1,1 = 3,95


• Agora devemos calcular a interconectividade interna dos clusters A e B.• Deve-se achar o corte mínimo de cada um dos grafos.• Esse corte deverá “dividir” cada um dos grafos em conjuntos com o

mesmo número de elementos (versão balanceada do corte).• |EC(A)| = 2 + 3 = 5• |EC(B)| = 3 + 5 = 8


• Aplicando a fórmula para o cálculo de RI, temos:

RI(A,B) = 3,95/((5+8)/2) = 3,95/6,5 = 0,61

• O uso da interconectividade relativa permite que o CHAMALEON possa se adaptar a variadas formas de clusters bem como variações no grau de interconectividade dos clusters.

Modelando a similaridade entre clusters• Interpretação da Equação para cálculo de RI:• Melhor Cenário Possível:

• RI(Ci,Cj) próximo a 1: o cluster resultante da união de Ci e Cj seria quase tão conectado quanto os dois clusters originais (numerador ≅denominador).

• Pior Cenário Possível:• RI(Ci,Cj) próximo a 0: o cluster resultante da união de Ci e Cj seria

bem menos conectado que os clusters originais (numerador muito menor que o denominador).


• Proximidade Relativa (RI):• A ideia é juntar clusters apenas se os pontos no cluster

resultante estão quase tão próximos uns aos outros assim como estão os pontos nos clusters originais.

• A proximidade absoluta entre dois clusters Ci e Cj (SEC(Ci,Cj)) é definida como a média dos pesos das arestas (do Grafo KNN) que ligam os dois clusters.• Essa é uma boa estratégia para calcular a similaridade entre os

clusters, pois no Grafo KNN vértices pouco similares não estão conectados.

• A proximidade interna de um cluster Ci (SEC(Ci)) é obtida através da média dos pesos das arestas que cruzam o corte mínimo que divida o cluster em duas partes aproximadamente iguais (bisseção mínima).


• Proximidade Relativa (RC):• Para obter a Proximidade Relativa entre os clusters Ci e Cj (RC(Ci,Cj)), deve-

se normalizar a proximidade absoluta (SEC(Ci,Cj)), em relação à proximidade interna dos clusters Ci (SEC(Ci)) e Cj (SEC(Cj)).

• Assim, chega-se a equação:

• |Ci| é o número de elementos no cluster Ci.• |Cj| é o número de elementos no cluster Cj.• Observe, pelo denominador da equação, que é dada uma maior

importância para o cluster com mais elementos


• Proximidade Relativa (RC):• Exemplo: Considere os dois clusters a seguir:

Cluster A Cluster B


• Primeiramente iremos calcular a proximidade absoluta entre os clusters.• Considere que no Grafo KNN (antes da execução do METIS) existiam as

seguintes arestas que permitam conectar pontos azuis a pontos vermelhos:• aresta b-e, com peso 1• aresta b-h, com peso 0,9• aresta d-h, com peso 0,95• aresta d-i, com peso 1,1


• Assim, a proximidade absoluta é calculada:

SEC(A,B) = (1+ 0,9 + 0,95 + 1,1)/4 = 0,9875


• Agora devemos calcular a proximidade interna dos clusters A e B.• Deve-se achar o corte mínimo de cada um dos grafos.• Esse corte deverá “dividir” cada um dos grafos em conjuntos com o

mesmo número de elementos (versão balanceada do corte).• SEC(A) = (2 + 3)/2 = 2,5• SEC(B) = (3 + 5)/2 = 4


• Aplicando a fórmula para o cálculo de RC, temos:

RC(A,B) = 0,9875 /[ (4/(4+6))*2,5 + (6/(4+6))*4 ] = 0,9875/(1 + 2,4) = 0,29

Modelando a similaridade entre clusters• Interpretação da Equação para cálculo de RC:• Melhor Cenário Possível:

• RC(Ci,Cj) próximo a 1: os objetos no cluster resultante da união de Ci e Cj estariam quase tão próximos uns aos outros quanto os dados nos clusters originais (numerador denominador).≅

• Pior Cenário Possível:• RC(Ci,Cj) próximo a 0: os objetos no cluster resultante da união de Ci

e Cj estariam bem menos próximos uns aos outros do que os dados nos clusters originais (numerador muito menor que o denominador).

União dos sub-clusters

• Após a geração dos sub-clusters, o próximo passo é a união desses sub-clusters.

• CHAMALEON seleciona dois clusters para união com base nas medidas de similaridade RI e RC.

União dos sub-clusters• Primeira abordagem possível: Una apenas aqueles pares de

clusters cuja proximidade e interconectividade relativa estão acima de thresholds TRI and TRC especificados pelo usuário.

• Assim, para cada cluster Ci, o algoritmo verifica se algum cluster Cj adjacente obedece a restrição dada pela equação acima.

• Se mais de um cluster obedecer a essa restrição, Ci é unido ao cluster com o qual possuir maior interconectividade absoluta.

• O algoritmo pára quando nenhum cluster satisfizer a condição imposta pela equação.

Exemplo:• Considere que RI(A,B) = 0,8 e RC(A,B) = 0,6.• Considere também que RI(A,C) = 0,5 e RC(A,C) = 0,7.• TRI = 0,7 e TRC = 0,6• O cluster A deve ser unido ao cluster B ou ao C?• RI(A,B) ≥ 0,7 e RC(A,B) ≥ 0,6 -> OK!• RI(A,C) < 0,7 e RC(A,C) ≥ 0,6 -> Não atende à restrição.

• Resposta: O cluster A deve ser unido ao cluster B.

União dos sub-clusters• Segunda abordagem possível: Use uma função para combinar

a proximidade e a interconectividades relativas, e selecione para mergear o par de clusters que maximize essa função.• α > 1: importância maior para a proximidade relativa (RC)• α < 1: importância maior para a interconectividade relativa

(RI)• α = 1: importância igual para as duas métricas

Recapitulando todos os passos• Algoritmo CHAMALEON:• Entrada:• O conjunto de dados (objetos).• Um parâmetro K que indica quantos vizinhos estamos considerando.• Um parâmetro T que será repassado ao METIS.• Os thresholds TRI and TRC caso deseje usar a primeira abordagem para união

dos sub-clusters.• O parâmetro α caso deseje usar a segunda abordagem para união dos sub-

clusters.• Saída:• Um conjunto de clusters (componentes conexos).

• Funcionamento:• Construa o Grafo KNN;• Particione o Grafo KNN usando o algoritmo METIS e obtenha sub-clusters dos

cluster reais;• Una os sub-clusters considerando a interconectividade relativa (RI) e a

proximidade relativa (RC), obtendo assim, os clusters reais.

Complexidade

• A complexidade de tempo é O(m²), onde m é o número de objetos presentes.• O(m²) é o tempo necessário para descobrir os k

vizinhos mais próximos de todos os objetos.

Ponto positivo

• CHAMALEON pode efetivamente encontrar clusters reais em um conjunto de dados, mesmo que estes tenham diferentes densidades, formas e tamanhos.

• Não é necessário especificar o número de clusters.

Pontos negativos• CHAMALEON assume que os grupos de objetos produzidos pelo

particionamento do Grafo KNN são sub-clusters, i.e., que a maioria dos pontos em uma mesma partição pertence ao mesmo cluster real. Caso isso não aconteça, o algoritmo de clusterização só irá compor erros, uma vez que ele nunca irá separar objetos que foram colocados na mesma partição.

• Para alta dimensionalidade, os algoritmos de particionamento (ex.: METIS) não produzem sub-clusters. Assim, o CHAMALEON não é indicado para alta dimensionalidade.

• Parâmetros de difícil calibração: k, T, α, TRI, TRC.

• Complexidade Quadrática.

Resultados

• Esses dados representam clusters difíceis de serem encontrados, pois contém variadas formas, distâncias, orientação e densidades. Os dados também contém vários ruídos e artefatos especiais.

• (a): 8000 pontos – 5 clusters reais• (b): 6000 pontos – 2 clusters reais• (c): 10000 pontos – 9 clusters reais• (d): 8000 pontos – 8 clusters reais


CHAMALEON

K=10 (nº de vizinhos mais próximos) α=2

NR = 5 NE = 6

NR = Número Real de Clusters NE= Número Encontrado de Clusters

NR = 2 NE = 2

NR = 9 NE = 11 NR = 8 NE = 8 NR = 9 NE = 11


CURE



NR = 9 NE = 11

NR = 8 NE = 8


DBSCAN

MinPts=4Eps=0,4

MinPts=4Eps=3

NR = 5 NE = Muitos!

NR = 2 NE = Muitos!


Jarvis-Patrick R.A. Jarvis e E.A Patrick (1973)

Similaridade baseada no número de vizinhos compartilhados

Motivação

• Em alguns casos, técnicas de clusterização que se baseiam em abordagens tradicionais de similaridade e densidade não produzem os resultados desejados na clusterização.

Motivação

• Problemas com a similaridade tradicional em dados de alta dimensionalidade (muitos atributos).

• Em espaços de alta dimensionalidade, é usual que a similaridade seja baixa.

• Exemplo: Considere um conjunto de artigos de jornal. Cada artigo pertence à uma seção específica do jornal: Diversão, Economia, Política, Tempo e Clima, Nacional, Esportes.

Motivação

• Esses documentos podem ser vistos como vetores de alta dimensionalidade, onde cada componente do vetor (atributo) guarda o número de vezes que cada palavra do vocabulário ocorre no documento.

• Resumindo:• p1,p2, p3, ... : vocabulário (palavras)• Um documento = vetor (n1,n2,...,nk)• ni = número de vezes que a palavra i aparece no

documento

Motivação

• A medida de similaridade do coseno é muitas vezes usadas para medir a similaridade entre esses documentos.• Medida de similaridade entre os documentos

d1,d2= cos(d1,d2) = d1.d2

|d1| |d2|

Motivação

Seção Similaridade Média do Coseno

Diversão 0,032

Economia 0,030

Política 0,030

Tempo e Clima 0,021

Nacional 0,027

Esportes 0,036

Todas as seções 0,014

A tabela a seguir mostra a similaridade média do coseno em cada seção e entre todos os documentos

(Jornal Los Angeles Times)

Motivação• A similaridade entre documentos de uma mesma classe é baixa• Uma consequência disso é que para 20% dos documentos

analisados, o vizinho mais próximo é de outra classe (outra seção).

• Em geral, se a similaridade direta é pequena, então ela se torna uma guia não-confiável para algoritmos de clusterização hierárquicos aglomerativos, onde os pontos mais próximos são colocados juntos no mesmo cluster e não serão separados depois disso.

• Porém, para a grande maioria dos documentos, a maior parte dos vizinhos mais próximos de um objeto pertence a mesma classe. Esse fato pode ser usado para definir uma nova medida de similaridade que seja mais adequada para a clusterização desses tipos de objetos.

Motivação• Problemas com diferenças na Densidade• A menor densidade do cluster da esquerda é refletida em uma distância

média maior entre os pontos do cluster.

• Mesmo que o cluster da esquerda seja um cluster real, as técnicas de clusterização tradicionais terão mais dificuldades em encontrar esse cluster.

• “As estrelas em uma galáxia formam um cluster válido, tanto quanto os planetas em um sistema solar, mesmo que os planetas em um sistemas solar estejam consideravelmente mais perto uns dos outros”.

Shared Nearst Neighbor Similarity

• Ideia central: “Se dois pontos são similares a muitos dos mesmos pontos, então eles são similares uns aos outros, mesmo que uma medida direta de similaridade não indique isso.”

• Leva em consideração o contexto dos objetos na definição de uma medida de similaridade.

Shared Nearst Neighbor Similarity• Considere dois objetos p e q:• p está na lista dos k vizinhos mais próximos de q• q está lista dos k vizinhos mais próximos de p.• A similaridade SNN entre p e q é o número de vizinhos mais próximos

compartilhados entre os dois objetos.• Exemplo:• Cada um dos pontos rosa (i e j) tem oito vizinhos mais próximos (k=8),

incluindo um ao outro.• Desses oito vizinhos, os pontos azuis são compartilhados.• Assim, similaridade SNN entre os pontos i e j é 4.

Shared Nearst Neighbor Similarity• Pseudocódigo para calcular a similaridade SNN entre todos os

objetos:

1: Encontre os k vizinhos mais próximos de todos os pontos2: If dois pontos, p e q, não estão entre os k vizinhos mais próximos um do outro then3: similaridadeSNN(p, q) = 04: else5: similaridadeSNN(p, q) = número de vizinhos compartilhados6: end if

Shared Nearst Neighbor Similarity• Grafo de similaridade SNN: o peso de cada aresta é a

similaridade SNN entre o par de vértices que ela conecta.• Como a maioria dos pares de objetos tem similaridade

SNN zero, esse grafo é bem esparso.• Exemplo:

Similaridade SNN versus Similaridade Direta• A similaridade SNN é útil para tratar os problemas expostos

anteriormente e que são inerentes às medidas de similaridade diretas.

• Similaridade SNN leva em consideração o contexto de um objeto ao usar o número de vizinhos compartilhados.• Com isso, ela trata o caso em que dois objetos estão

relativamente próximos uns aos outros e pertencem à classes (seções) diferentes. Nesse caso, em geral, esses dois objetos não compartilham muitos vizinhos, e assim a similaridade SNN entre ambos é pequena (os dois serão colocados em clusters distintos).

Similaridade SNN versus Similaridade Direta• Similaridade SNN trata o problema da presença de clusters

com densidades variadas presentes nos dados.• A similaridade SNN entre um par de objetos depende

apenas do número de vizinhos mais próximos que os dois objetos compartilham, e não de quão longe os vizinhos estão de cada objeto.

• Assim, a similaridade SNN faz um “dimensionamento” automático em relação à densidade dos pontos.

Jarvis-Patrick • Utiliza o conceito de similaridade SNN ao invés da similaridade direta.• Entrada:• O conjunto de dados (objetos).• Um parâmetro K que indica quantos vizinhos estamos considerando.• Um threshold T usado para esparsar o grafo.

• Saída:• Um conjunto de clusters (componentes conexos).

• Funcionamento:1: Construa o grafo de similaridade SNN.

Lembrando que nesse grafo o peso de cada aresta representa a similaridade SNN entre os dois objetos que ela conecta.2: Remova do grafo todos as arestas que possuem peso menor do que um threshold T especificado pelo usuário.

Não é interessante manter no grafo a conexão entre dois objetos que possuem similaridade SNN baixa.3: Encontre os componentes conexos (clusters) do grafo obtido ao final da etapa 2.

Exemplo:• Dado um banco de dados contendo oito objetos, foi calculada

a similaridade SNN entre todos os pares de objetos.• Em seguida foi construído o Grafo de similaridade SNN.• O peso de cada aresta representa a similaridade SNN entre os

objetos que ela conecta.• A não-existência de uma aresta entre um par de objetos significa

que a similaridade SNN entre ambos é zero.

Grafo de similaridade SNN

Exemplo:• O threshold T especificado pelo usuário é 3.• Devemos eliminar todas as arestas com peso menor que 3.

Jarvis-Patrick

K=20T=10 Os ruídos estão marcados com um “x”

Complexidade • A complexidade de tempo é O(m²), onde m é o número de

objetos presentes.• O(m²) é o tempo necessário para descobrir os k vizinhos mais

próximos de todos os objetos.• Para dados com baixa dimensionalidade pode-se reduzir esse

tempo para O(mlogm), usando uma estrutura de dados chamada k-d tree.

Pontos positivos• Como Jarvis-Patrick é baseado na noção de similaridade SNN, ele é bom

para lidar com ruídos e outliers.• Observe que em geral, os ruídos e outliers não estarão nas listas de k

vizinhos mais próximos dos objetos e sendo assim, a similaridades SNN desses objetos com os demais será pequena e os mesmos serão desconsiderados pelo algoritmo (não irão fazer parte de nenhum cluster).

• É capaz de lidar com clusters com diferentes tamanhos, formas e densidades.

• Funciona bem para dados com alta dimensionalidade (ao contrário do CHAMALEON).

• Não é necessário especificar o número de clusters.

Pontos negativos• Jarvis-Patrick define um cluster como um componente conexo no

grafo resultante da etapa 2 do algoritmo.• Assim, o fato de um conjunto de objetos ser dividido em dois

clusters ou deixados em apenas um, pode depender de uma única aresta. Assim, Jarvis-Patrick pode ser considerado frágil: ele pode dividir clusters reais ou juntar dois clusters que deveriam permanecer separados.

• Encontrar os parâmetros apropriados (k e o valor de threshold T usado para eliminar arestas) pode ser desafiador.

• Complexidade Quadrática.

Outros algoritmos• Existem diversos outros algoritmos de clusterização baseados

em grafos.• 1- Minimum Spanning Tree (MST) Clustering• Se baseia em encontrar os clusters particionando a árvore

geradora mínima do conjunto de dados.• 2- SNN Density-Based Clustering• É uma adaptação do DBSCAN, que usa como medida de

similaridade a similaridade SNN.

Referências Bibliográficas• [1] P-Ning Tan, M. Steinbach,V. Kumar: Introduction to Data Mining (2006).

• [2] George Karypis , Eui-Hong (Sam) Han , Vipin Kumar, CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling (1999)

• [3] Tatyana. B. S. Oliveira. Clusterização de dados utilizando técnicas de redes complexas e computação bioinspirada. Dissertação de Mestrado, ICMC-USP (2008).

• [4] S. de Amo. Slides da disciplina Mineração de Dados. Mestrado em Ciência da Computação (2012).

• [5] George Karypis, Vipin Kumar. Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0 (1995)

• [6] R.A. Jarvis, E.A. Patrick. Clustering Using a Similarity Measure Based on Shared Near Neighbors. IEEE Transactions on Computers, C22, 1025-1034 (1973).

Documents

Métodos de Agrupamentos baseados em Grafos