Clustering de Texto
Recuperação Inteligente de Informação
Roteiro





Introdução
Representação de Textos
Algoritmos de Clusteting
Avaliação
Conclusões
Clustering (Agrupamento)

Particionar objetos em clusters de forma que:
Objetos dentro de um cluster são similares
 Objetos de clusters diferentes são diferentes


Descobrir novas categorias de objetos de uma
maneira não-supervisionada

Classes não são fornecidas a priori
Tipos de Clustering

Flat X Hierárquicos

Hard X Fuzzy

Incremental X Não-Incremental
Clustering (Agrupamento) de Texto

Objetivo:


Encontrar clusters em bases de documentos de
texto
Usos:



Gerar interfaces para resultados de engenhos de
busca
Criar diretórios de documentos
Reordenar resultados de busca
Clustering de Texto
Textos
Corpus
Redução da
dimensionalidade
Representação
Representação
dos documentos
(e.g. lista de termos)
Seleção ou extração
de características
Cluster B
Textos
Etiquetagem
Clustering
Cluster A
Textos
Cluster C
Textos
Representação de Textos

Abordagem Clássica: TF-IDF

Cada documento representado como um ponto
em um espaço de tamanho T (tamanho do
vocabulário)
di = (di1,...,diT)
dij = tfij * log(idfj)
Representação de Textos

Observação: muitos trabalhos usam
somente termo TF
di = (di1,...,diT)
dij = tfij
Representação de Textos

Similaridade medida através de Cosseno
 
 
sim(c , d )  cos(c , d )
Representação de Textos

Redução de dimensionalidade

Aplica-se operadores de stemming e eliminação
de stopwords

Seleção de Atributos
 Selecionam

termos mais relevantes do vocabulário
Extração de Atributos
 Criam
novos atributos a partir da combinação dos
atributos existentes
Representação de Textos

Seleção de Atributos

Document Frequency: seleciona termos mais
frequentes da base

Term Frequency Variance: seleciona termos onde
valor de TF apresenta maior variação
Representação de Textos

Seleção de Atributos

Term Strength: probabilidade de um termo ocorrer
em um documento dado que ocorre em um
documento similar

Seleção supervisionada:


(1) Aplica algoritmo de clustering e considera clusters
como labels de classes;
(2) Usa Information Gain, Chi-Square, etc... para
selecionar atributos
Algoritmo k-Means

Encontra de forma interativa os centróides dos
clusters
d1
Centróide A
Centróide A
d2
Algoritmo k-Means

Clusters definidos com base nos centróides (centro
de gravidade, ou o ponto médio dos cluster:


1
c
d

i

| C | di C

Alocação dos objetos nos clusters feita com base na
similaridade com o centróide
 
 
sim(c , d )  cos(c , d )
Algoritmo k-Means




Passo 1: Defina k centróides iniciais, escolhendo k
documentos aleatórios da base;
Passo 2: Aloque cada documento para o cluster
correspondente ao centróide mais similar;
Passo 3: Recalcule os centróides dos clusters.
Passo 4: Repita passo 2 e 3 até atingir um critério de
parada

e.g. até um número máximo de iterações ou até não ocorrer
alterações nos centróides
Algoritmo k-Means

Observações:




Define uma partição flat
Converge para mínimos locais
É necessário realizar várias execuções com inicializações
diferentes
Necessidade de se definir parâmetro k
Algoritmos Hierárquicos

Geram uma partição onde os clusters são organizados
em uma hierarquia

Em clustering de texto, permite ao usuário ter diferentes
visões dos documentos
Algoritmos Hierárquicos Divisivos


Passo 1: Inicie alocando todos os documentos em um
cluster;
Passo 2: A partir da estrutura existente de grupos,
selecione um cluster para particionar;



Em geral, o maior cluster, ou o cluster menos homogêneo
Passo 3: Particione o grupo em dois ou mais subgrupos;
Passo 4: Repita os passos 2 e 3 até que um critério de
parada seja verificado

e.g., até atingir um número desejado de grupos
Algoritmos Hierárquicos Divisivos

Bi-Secting k-Means


Uso do algoritmo k-Means na etapa de divisão dos
clusters
Clusters são sucessivamente particionais em 2 subclusters
Algoritmos Hierárquicos
Aglomerativos



Passo 1: Inicie alocando cada documento como um
cluster diferente;
Passo 2: Selecionar o par de clusters mais similares entre
si e os agrupe em um cluster mais geral;
Passo 3: Repita o passo 2 até a verificação de um critério
de parada

e.g., até que todos os documentos sejam agrupados em um
único cluster
Algoritmos Hierárquicos
Aglomerativos

Algoritmos variam conforme a maneira de medir
similaridade entre dois clusters

Single-Link: definida como a máxima similaridade entre os
membros dos clusters

Complete-Link: definida como a mínima similaridade entre os
membros dos clusters

Average-Link: definida como a média da similaridade entre os
membros dos clusters
Algoritmos Hierárquicos
Aglomerativos

Single-Link

Complete-Link

Average-Link
Algoritmos Hierárquicos

Observações:



Os algoritmos particionais são menos custosos que os
aglomerativos e, em geral, funcionam melhor para clustering
de texto
Dentre os aglomerativos, o Average-Link funciona melhor
para clustereing de texto
Desempenho pode ser melhorado combinando as duas
técnicas
Algoritmos Incrementais

A cada novo objeto, atualiza a estrutura de grupos sem
precisar reiniciar o processo de clustering

Ideal em contextos onde os documentos são recebidos de
forma constante e a uma taxa alta

Exemplos de algoritmos:

Single-Pass, COBWEB, Redes ART,...
Single-Pass




Passo 1: Inicie a partição dos documentos com um conjunto
vazio de clusters;
Passo 2: Dado um documento, encontre o cluster existente
de maior similaridade média com o documento recebido;
Passo 3: Se a similaridade for abaixo de um limiar, então
crie um novo cluster com o documento. Caso contrário,
apenas inclua o documento no cluster mais similar;
Passo 4: Volte para o passo 2 a cada novo documento
recebido.
Single-Pass

Observações:


Se o valor do limiar for excessivamente alto, serão criados
poucos clusters com um número alto de documentos
heterogêneos entre si.
Por outro lado, se o valor do limiar for muito baixo, então o
algoritmo poderá criar um número muito alto de clusters
pouco representativos.
Avaliação de Clustering

Avaliação Interna

Mede homogeneidade e separação entre os clusters
gerados
 
1
H (C ) 
sim(c , di )

| C | di C
 
S (C1 , C2 )  sim(c1 , c2 )
Avaliação de Clustering

Avaliação Externa

Mede a similaridade entre os clusters criados e classes de
documentos conhecidas a priori

Seja: P1,...,Pm as classes de documentos conhecidas
Seja: C1,....,Ck os clusters gerados

Avaliação de Clustering

Calcula F-Measure para cada para de classe e cluster

Pri,j = Precision(Pi,Cj) = Nij/Nj



Rei,j = Recall(Pi,Cj) = Nij/Ni


Nij = número de documentos de Pj que estão em Cj
Nj = número de documentos em Cj
Ni = número de documentos da classe Pi
Fi,j = F-Measure(Pi,Cj) = (2* Pri,j*Rei,j)/(Pri,j + Rei,j)
Avaliação de Clustering

A qualidade de um cluster é medida como a máxima FMeasure obtida considerando as classes conhecidas


Qualidade(Cj) = Maxi Fi,j
A qualidade final dos clusters é a média dos valores de
pureza ponderados pelo tamanho dos clusters

j Nj/N * Qualidade(Cj)

N = número total de documentos
Avaliação de Clustering
Pr1,azul = 2/6 = 0.33
Re1,azul = 2/8 = 0.25
F1,azul = 0.28
C2
C1
Pr1,verm = 4/6 = 0.66
Re1,verm = 4/6 = 0.66
F1, verm = 0.66
Qualidade(C1) = max (F1,azul, F1,verm) =
= 0.66
Avaliação de Clustering
Pr2,azul = 6/8 = 0.75
Re2,azul = 6/8 = 0.75
F2,azul = 0.75
C2
C1
Pr2,verm = 2/8 = 0.25
Re2,verm = 2/6 = 0.33
F2, verm = 0.28
Qualidade(C2) = max (F2,azul, F2,verm) =
= 0.75
Avaliação de Clustering
Qualidade Média = 6/14*0.66 + 8/14*0.75 = 0.71
C2
C1
Conclusões

Tendências





Características linguísticas para representação de textos
Combinação de algoritmos de clustering
Algoritmos incrementais
Eficiência de algoritmos
Etiquetagem de clustering