Descoberta de Conhecimento:
Centroid-Based Document Classification:
Analysis & Experimental Results
Autores: Eui-Hong (Sam) Han e George Karypis
Ano de publicação: 2000
Edimar Manica
Fahad Kalil
2009
Roteiro
• Objetivo
• Pré-processamento
o Remoção de Stopwords
o Stemming
• Conceitos
o Poderação de Termos (TF-IDF)
o Cosine Function
o Centroid Vector
o Modelo Vetorial (Vector-Space Model)
• Funcionamento
• Experimentos e Comparativo
• Conclusões
Objetivo
• Dado um conjunto de treinamento
o Doc1 {termo1, termo2, ..., termon} -> Classe 1
o Doc2 {termo1, termo2, ..., termon} -> Classe 2
o Doc3 {termo1, termo2, ..., termon} -> Classe 2
o Doc4 {termo1, termo2, ..., termon} -> Classe 1
• Classificar um novo documento com base em seus termos
o Doc5 {termo1, termo2, ..., termon} -> Classe ?
•
Considerando que um documento pertence a apenas uma
classe
Pré-processamento do documento
• Objetivo
o Limpeza dos dados
• Remoção de stopwords
o Remover
palavras que não são significantes
para representar o documento (palavras comuns)
o Remoção realizada através de uma stop-list
o Ex: A Varig Log pediu a impugnação dos votos das
empresas ...
• Stemming
o O usuário consulta uma palavra e um documento
relevante contém apenas formas variantes desta palavra
o Consulta: como comer com saúde
o Documento: comendo com saúde
Pré-processamento do documento
• Stemming (continuação)
o Stem = radical
o Palavra
Radical
comendo
com
comer
com
o
Algoritmo utilizado: Porter's suffix-stripping
 Remoção de sufixos
 Baseia-se em regras que são aplicadas
determinadas condições são satisfeitas
 Ex: Regra de Redução de plural
 sses -> ss
stresses -> stress
 ies -> i
ponies -> poni
s
-> nada
cats
-> cat
se
Conceitos
• Poderação de Termos
o Em um documento alguns termos são mais importantes
que outros (tem um peso maior)
o TF-IDF (Term Frequency Times Inverse Document Frequency)
 Objetivo:
 Beneficiar termos que ocorrem bastante no
documento e em poucos documentos
 Atribui ao termo t uma importância no documento d
que é:
 Alta se t ocorrer muitas vezes em um número
pequeno de documentos
 Menor se t ocorrer poucas vezes no documento OU
muitas vezes na coleção
 Muito baixa se t ocorrer em quase todos os
documentos
Conceitos
•
Poderação de Termos (continuação)
o
TF-IDF (Term Frequency Times Inverse Document Frequency)
TF
TF:
IDF
freqt,d = número de ocorrências do termo t no documento.
maxt = número de ocorrência do termo mais frequente em d.
(Isso para não beneficiar documentos longos)
IDF:
N = número de documentos na coleção
nt = número de ocorrências do termo t na coleção
TF-IDF
Exemplo
Termo (t): best
Freq. de t no Doc1: 14
Freq. de t na coleção: 14+0+17=31
Freq. do termo que mais ocorre no Doc1: 27 (car)
Nº docs na coleção: 3
Wt,doc1 = (14/27) * log2 3/31 = -1,75
Centróides
• Um centróide representa uma classe
• É a média dos pesos dos vários termos presentes nos
documentos de uma mesma classe do conjunto de
treinamento.
Centróides
Classe A
Classe B
Classe B
Classe A

(
3
,
4
,
9
)
d1

(
20
,
15
,
0
)
d2
d  (22,20,2)

(
1
,
2
,
7
)
d
3
4
Centróides
– Calculando o centróide da classe A
Classe A
Classe B
Classe B
Classe A
d  (3,4,9)

(
20
,
15
,
0
)
d

(
22
,
20
,
2
)
d
d  (1,2,7)
1
2
3
4
3 1 4  2 9  7

(
,
,
)

(
2
,
3
,
8
)
CA 2 2 2
Centróides
– Calculando o centróide da classe B
Classe A
Classe B
Classe B
Classe A
d  (3,4,9)
d  (20,16,0)
d  (22,20,2)

(
1
,
2
,
7
)
d
1
2
3
4
20  22 16  20 0  2

(
,
,
)

(
21
,
18
,
1
)
CB
2
2
2
Cosine Function - Idéia
• Documentos que estão próximos no espaço vetorial tem
conteúdo similar
• Similaridade computada usando o co-seno do ângulo entre os
documentos
Cosine Function - Idéia
•
O comprimento dos valores não é levado em consideração,
apenas suas direções.
•
Consultas e
documentos.
centróides
são
considerados
pseudo-
Cosine Function - Cálculo
A B
(a1 b1)  (a 2  b2)    (an  bn)
sim( A, B)  cos( ) 

2
2
2
2
2
2
| A|| B |
a1  a 2  a n  b1 b 2 b n
Cosine Function - Cálculo
A B
(a1 b1)  (a 2  b2)    (an  bn)
sim( A, B)  cos( ) 

2
2
2
2
2
2
| A|| B |
a1  a 2  a n  b1 b 2 b n
• O vetor de um documento j é definido por:

d
j
 ( w1,dj , w2,dj ,, wn,dj )
• O vetor de um centróide k é definido por:

c
k
 (w1,ck , w2,ck ,, wn,ck)
Cosine Function - Cálculo
A B
(a1 b1)  (a 2  b2)    (an  bn)
sim( A, B)  cos( ) 

2
2
2
2
2
2
| A|| B |
a1  a 2  a n  b1 b 2 b n

(
4
,
1
,
8
)
c1
d1  (2,5,8)
sim(d 1 , c1) 
(2 * 4)  (5 *1)  (8 * 8)
2
2
5 8 *
2
2
2
4
1  8
2
2
 0,89
Modelo proposto
• Centroid-Based Document Classifier
Baseado no modelo espaço-vetorial, que parte da
premissa de que o significado de um documento pode ser
representado pelos termos presentes nele.
O modelo representa documentos como um vetor de
termos (1) onde o termo no vetor é um valor não-negativo
denotando a não ocorrência, ocorrência única ou múltipla de
um termo i em um documento d.
dtf  tf1, tf 2 ,...,tf n 
(1)
Tendo um conjunto S de documentos e sua representação na
forma de vetores, são utilizadas as funções Cosine e de definição
dos centróides.
Funcionamento
Passos necessários:
Treinamento:
- Cálculo do TF-IDF;
- Cálculo dos centróides;
Novos documentos:
- Cálculo do TF-IDF;
- Similaridade entre o novo documento e todos os centróides
gerados no treinamento, usando Cosine Function.
Funcionamento
Exemplo didático!
- 4 documentos de treino;
- 1 novo documento;
- 2 classes
Experimentos
- Comparativo entre outros algoritmos
classificadores
17 de 23
documentos
classificados
corretamente
- Foram usados 80% dos
documentos para treino e
20% como conjunto de teste.
Comparativo
Centroid-based X Naive Bayes
-Melhor que o classificador Naive Bayes pela forma como é computada
a similaridade entre um documento teste e uma classe.
-Naive Bayes usa a regra Bayes, assumindo que quando condicionado
em cada classe, a ocorrência de diferentes termos é independente.
Porém, na realidade isso não acontece freqüentemente.
-Dependência entre termos pode ser vista pela freqüência com que
aparecem juntos em documentos da mesma classe.
Considerações Finais
VANTAGENS
- Algoritmo com complexidade linear e melhores resultados que o
Naive Bayes (que é um dos melhores).
- A essência do algoritmo está na sua forma de calcular a similaridade
entre um documento de teste e o centróide da classe.
- É levada em conta a similaridade, freqüência e dependência entre os
termos presentes no documento com os documentos da classe.
DESVANTAGEM
- O algoritmo determina que um documento só pode pertencer a uma
classe específica.