Slides - Universidade Federal de Uberlândia

Report
Métodos de
Agrupamentos
baseados em Grafos
Lucas Batista Leite de Souza
Mestrado 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
d
a
0
3
3,1
1
b
3
0
1
1
c
3,1
1
0
3
d
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|).
CHAMALEON
G. 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=4
Eps=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,3
Número de pontos representantes = 10
Imagens Retiradas de [2]
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
Imagens Retiradas de [4]
Medidas de Similaridade entre
clusters
• O uso da proximidade absoluta como medida de similaridade pode levar
algoritmos a unirem clusters de maneira errada.
• Exemplo:
Imagens Retiradas de [3]
•
•
•
•
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.
Medidas de Similaridade entre
clusters
• Interconectividade Absoluta: Também conhecida
agregação de similaridade entre dois clusters.
por
• 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.
Medidas de Similaridade entre
clusters
• O uso da interconectividade absoluta como medida de similaridade pode
levar algoritmos a unirem clusters de maneira errada.
• Exemplo:
Imagens Retiradas de [3]
• 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
Imagens Retiradas de [3]
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 Kvizinhos 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.
a
b
c
d
a
0
3
4
1
b
3
0
1
1
c
4
1
0
3
d
1
1
3
0
Grafo KNN
K=1
Modelando os dados
Imagens Retiradas de [3]
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.
Imagens Retiradas de [3]
• 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
similaridade:
considera
duas
medidas
de
• 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.
Modelando a similaridade entre
clusters
• 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).
Modelando a similaridade entre
clusters
• 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:
Modelando a similaridade entre
clusters
• Interconectividade Relativa (RI):
• Exemplo: Considere os dois clusters a seguir:
Cluster A
Cluster B
Modelando a similaridade entre
clusters
• 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
Modelando a similaridade entre
clusters
• Assim, a interconectividade absoluta é calculada:
|EC(A,B)| = 1+ 0,9 + 0,95 + 1,1 = 3,95
Modelando a similaridade entre
clusters
• 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
Modelando a similaridade entre
clusters
• 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).
Modelando a similaridade entre
clusters
• 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).
Modelando a similaridade entre
clusters
• 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
Modelando a similaridade entre
clusters
• Proximidade Relativa (RC):
• Exemplo: Considere os dois clusters a seguir:
Cluster A
Cluster B
Modelando a similaridade entre
clusters
• 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
Modelando a similaridade entre
clusters
• Assim, a proximidade absoluta é calculada:
SEC(A,B) = (1+ 0,9 + 0,95 + 1,1)/4 = 0,9875
Modelando a similaridade entre
clusters
• 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
Modelando a similaridade entre
clusters
• 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
Imagens Retiradas de [2]
• 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
Imagens Retiradas de [2]
NR = Número Real
de Clusters
NE= Número
Encontrado de
Clusters
NR = 5 NE = 6
NR = 2 NE = 2
K=10 (nº de
vizinhos mais
próximos)
α=2
NR = 9 NE = 11
NR = 8 NE = 8
CURE
NR = 9 NE = 11
NR = 8 NE = 8
Número de clusters especificado(k)=11
α=0,3
Número de pontos representantes = 10
Número de clusters especificado(k)=8
α=0,3
Número de pontos representantes = 10
Imagens Retiradas de [2]
DBSCAN
MinPts=4
Eps=3
MinPts=4
Eps=0,4
NR = 2 NE = Muitos!
NR = 5 NE = Muitos!
Imagens Retiradas de [2]
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
A tabela a seguir mostra a similaridade média do
coseno em cada seção e entre todos os documentos
(Jornal Los Angeles Times)
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
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 pontos
2: If dois pontos, p e q, não estão entre os k vizinhos mais próximos um do
outro then
3: similaridadeSNN(p, q) = 0
4: else
5: similaridadeSNN(p, q) = número de vizinhos compartilhados
6: 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=20
T=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).

similar documents