Recuperação Inteligente de Informação
Agrupamento de Texto
CIn-UFPE
1
2
Roteiro da Aula
Definição Geral
Clustering de texto
Cluster não-hierárquico
Cluster hierárquico
CIn-UFPE
3
Agrupamento de Objetos
Clustering
Objetivos

Particionar exemplos não classificados em
subconjuntos disjuntos (clusters), de modo que
 Exemplos em um mesmo cluster são muito
similares
 Exemplos em clusters diferentes são muito
diferentes

Descobrir novas categorias de maneira nãosupervisionada
 i.e., sem conhecer as de categorias previamente
CIn-UFPE
4
Exemplo de Clustering
.
..
.
.
. .
. .
.
. .
. . .
.
CIn-UFPE
5
Clustering de Texto
Técnicas convencionais de Clustering têm sido
diretamente aplicadas a texto, tipicamente


representando os textos como vetores de pesos com TF/IDF
usando a medida de similaridade do co-seno.
Algumas aplicações:



Durante a recuperação, adicionar outros documentos no
mesmo cluster para melhorar a cobertura
Organizar os resultados da busca em clusters, para melhorar
a organização da apresentação dos resultados ao usuário
 E.g., folders do Vivisimo
Criação automática de taxonomias hierarquizadas de
documentos para browsing
 e.g., Yahoo & DMOZ
CIn-UFPE
6
CIn-UFPE
7
CIn-UFPE
8
CIn-UFPE
9
Clustering Não-Hierárquico
O número de clusters desejados deve ser informado

Parâmetro = K
Algoritmo Geral:



Escolhe aleatoriamente k instancias (documentos) como
sementes, uma para cada cluster
Constrói os clusters iniciais com base nessas sementes
 Medindo a similaridade entre vetores
Iterações
 realoca instancias em clusters diferentes, a fim de
melhorar o clustering geral
 Para quando nenhum cluster é mais modificado, ou
quando atinge um número fixo de iterações
CIn-UFPE
10
Algoritmo K-Means
Assume que instâncias são vetores de valores reais
(não-binários)
Cria clusters baseado em centróides (centros de
gravidade), ou média dos pontos em um cluster, c:


1
μ(c) 
x

| c | xc
A Realocação de instâncias a outros clusters é
baseada na distância entre o vetor que representante
a instância e o centróide atual do cluster
CIn-UFPE
Algoritmo K-Means
11
Medidas de Distância
Distância Euclidiana (L2 norma):
m
 
2
L2 ( x , y )   ( xi  yi )
i 1
L1 norma:
m
 
L1 ( x, y )   xi  yi
i 1
Similaridade com co-seno (transformada em uma
distancia subtraindo-a de 1):

x
1 
x 

y

y
CIn-UFPE
12
Algoritmo K-Means
Seja d a distância medida entre instâncias
Selecione aleatoriamente k instâncias {s1,
s2,… sk} como sementes
Até o processo convergir (ou outro critério de
parada for satisfeito), faça:

Para cada instância xi
 Aloque xi no cluster cj tal que d (xi, sj) é mínima.
 Atualize as sementes como sendo os centróides de
cada cluster

Para cada cluster cj
 sj = (cj)
CIn-UFPE
13
Exemplo do K Means (K=2)
Pegue as semenstes
Realoque clusters
Compute centróides
Realoque clusters
x
x
x
x
Compute centróides
Realoque clusters
Convergiu!
CIn-UFPE
Algoritmo K-Means
14
Escolha das Sementes
Resultados podem variar com a escolha
aleatória das sementes


Algumas sementes podem resultar em taxas
baixas de convergência
Ou convergência para clusters sub-optimais
Devemos selecionar sementes


com base em uma heurística
ou usando resultados de outro método
CIn-UFPE
Clustering Hierárquico
CIn-UFPE
15
16
Clustering Hierárquico
Constrói uma árvore (taxonomia hierárquica dendograma) a partir de um conjunto de exemplos
não etiquetados
animal
vertebrado
peixe reptil anfíbio mamífero
invertebrado
helmito inseto crustáceo
Aplicações recursivas de um algoritmo de clustering
padrão podem produzir um clustering hierárquico
CIn-UFPE
Clustering Hierárquico
17
Aglomerativo vs. Divisivo
Métodos Aglomerativos (bottom-up)


Iniciam com cada exemplo sendo um cluster e
Iterativamente combinam os clusters para formar
cluster maiores
Métodos Divisivos (particionais, top-down)

Inicialmente, separam todos os exemplos em
clusters.
CIn-UFPE
18
Clustering Hierárquico Aglomerativo
Algoritmo:


Inicia com cada instância em um clusters
separado
Até restar apenas um cluster
 Repetidamente, une os dois clusters ci and cj que
são mais semelhantes, criando um cluster ci  cj
 Utiliza uma função para determinar a similaridade
entre duas instâncias/clusters

E.g., Co-seno entre vetores de documentos
O histórico das junções forma uma árvore
binária (ou hierarquia).
CIn-UFPE
19
Clustering Hierárquico Aglomerativo
Similaridade entre Clusters
Como computar a similaridade entre dois
clusters (sim(x,y)) que podem conter mais de
uma instância?
Três possibilidades:



Single Link: Similaridade entre os dois membros
mais similares
Complete Link: Similaridade entre os dois
membros menos similares
Group Average: Similaridade média entre todos os
membros do cluster
CIn-UFPE
Clustering Hierárquico Aglomerativo
20
Single Link
Similaridade entre os dois membros mais
similares:
sim(ci ,c j )  max sim( x, y)
xci , yc j
Pode resultar em clusters longos e finos,
devido ao efeito “cadeia”

Isso é apropriado em alguns casos, como por
exemplo clustering islands.
CIn-UFPE
Clustering Hierárquico Aglomerativo
Exemplo de Single Link
21
CIn-UFPE
Clustering Hierárquico Aglomerativo
22
Complete Link
Similaridade entre os dois membros menos
similares:
sim(ci ,c j )  min sim( x, y )
xci , yc j
Cria clusters mais more densos e esféricos,
que são, em geral, preferíveis
CIn-UFPE
Clustering Hierárquico Aglomerativo
Exemplo de Complete Link
23
CIn-UFPE
24
Clustering Hierárquico Aglomerativo
Similaridade entre Clusters
Depois de unir ci e cj, a similaridade entre o
cluster resultante e outro cluster qualquer ck
pode ser dada por:

Single Link:
sim((ci  c j ), ck )  max(sim(ci , ck ), sim(c j , ck ))

Complete Link:
sim((ci  c j ), ck )  min(sim(ci , ck ), sim(c j , ck ))
CIn-UFPE
Clustering Hierárquico Aglomerativo
Similaridade Group Average entre Clusters
25
Mede a similaridade entre dois clusters com
base na similaridade média entre todos os
pares com o cluster que foi unido
 
1
sim(ci , c j ) 
sim( x, y)


ci  c j ( ci  c j  1) x(ci c j ) y(ci c j ): y  x
“Compromisso” entre single e complete link.
CIn-UFPE
Clustering Hierárquico Aglomerativo
Similaridade Group Average entre Clusters
26
Assume co-seno como função de similaridade
e vetores normalizados
Sempre mantém a soma dos vetores em cada
cluster 

s (c j )   x

xc j
Compute similaridade entre clusters em
tempo constante:
sim(ci , c j ) 




(s (ci )  s (c j ))  (s (ci )  s (c j ))  (| ci |  | ci |)
(| ci |  | ci |)(| ci |  | ci | 1)
CIn-UFPE
27
Clustering Hierárquico Divisivo
Aplicação de k-Means de forma interativa



Inicialmente, divida todos os objetos em dois
clusters usando k-Means
Aplique k-Means nos clusters formados para gerar
subclusters
Repita até atingir critério de parada
CIn-UFPE
28
Próxima aula
Lucene
CIn-UFPE