Categorização de Textos
(modificada)
Mariana Lara Neves
Flávia Barros
CIn/UFPE
CIn/UFPE
1
Roteiro
Introdução
Categorização de Documentos
Preparação de Dados
Construção Manual do Classificador
Construção Automática do Classificador
Comparação das Abordagens
Referências
CIn/UFPE
2
Categorização de Documentos
Definição:

atribuição de uma ou mais classes prédefinidas aos documentos
Objetivos:


CIn/UFPE
Organizar os documentos
Facilitar a sua busca automática
3
Categorização de Documentos
Documentos
Classe 2
Classe 3
CIn/UFPE
Classe 1
4
Categorização de Documentos
Classificação Manual:

Leitura dos documentos por um especialista
Construção Manual do Classificador:

Sistemas baseados em conhecimento
 Base de Regras escrita manualmente
Construção Automática do Classificador:

CIn/UFPE
Algoritmos de aprendizagem automática
5
Construção do Classificador
Conjunto de treinamento:


Aquisição do conhecimento ou Treinamento do
algoritmo
Ajuste do sistema
Conjunto de teste:


CIn/UFPE
Diferente do conjunto de treinamento
Avaliação do desempenho do sistema
6
Construção Manual do Classificador
Sistema baseado em Conhecimento:


Base de conhecimento
Máquina de Inferência (ex.: JEOPS)
Aquisição
do
Conhecimento
Formulação
da Base de
Conhecimento
Construção
da Base de
Conhecimento
Nível de
Conhecimento
Nível Lógico
Nível de
Implementação
CIn/UFPE
Testes
e
Validação
7
Construção Manual do Classificador
Base de Conhecimento:

Regras de Produção
Exemplo:

Regras para o reconhecimento de um bloco de
citação em uma página de publicação
(CitationFinder)
SE houver uma cadeia de Autores
E houver uma cadeia de Intervalo de Páginas
E houver uma cadeia de Trabalho Impresso
E houver uma cadeia de Data
ENTÃO o texto é uma citação (chance 1.0)
CIn/UFPE
8
Montar regras com fator de certeza
associado
Montar regras com fator de certeza (F.C.) associado
 Objetivo: melhorar a precisão do sistema
Se evidência1 Então ex.positivo com F.C.% de chance
O F.C. é calculado pelo do Teorema de Bayes
 P(ex.pos | evidência1) =
P(ex.pos & evidência1) / P(evidência1)
 Onde:
 P(ex.pos | evidência1) é a probabilidade de um exemplo ser
positivo dado que a evidência1 ocorreu
 P(ex.pos & evidência1) é a quantidade de ocorrência
simultânea
 P(evidência1) quantidade de ocorrências de evidência1 no
corpus

CIn/UFPE
9
Montar regras com fator de certeza
associado
Contar se quiser estimar com precisão!!!
Exemplo
 P(spam | “promoção” no subject ) =
P(número de emails que são spam e têm a
palavra “promoção” no subject) / P(número de
emails que têm a palavra “promoção” no subject)
CIn/UFPE
10
Utilizar as regras com fator de
certeza associado
Quando a máquina de inferência dispara regras com a mesma
conclusão, ela deve combinar os F.C. associados
O objetivo é calcular a probabilidade final de uma dada página ser
positiva

P-atual = P-anterior + P-nova * (1 - P-anterior)
Por exemplo:
 Se evidência1 Então ex.positivo com 90%
 Se evidência2 Então ex.positivo com 85%

P-atual = 0,9 + 0,85 * (1 - 0,90)
Quando a máquina de inferência pára, teremos a probabilidade final
de um exemplo ser positivo
Em JEOPS, pode-se implementar a probabilidade acumulada no
objeto
CIn/UFPE
11
Utilizar as regras com fator de
certeza associado
A probabilidade final é comparada a um limiar
 Se P-final >= limiar Então exemplo positivo
Cada classificador poderá usar um limiar diferente
 O limiar é calculado “iterativamente” com base na
F-measure para o corpus de treinamento
1.
2.
3.
4.
5.
CIn/UFPE
Escolher um limiar inicial (p. ex. = 60%)
Calcular erro (ex. F-measure)
Aumentar o limiar em 0.5 e recalcular erro
Repetir passo 3 até o erro começar a piorar
Escolher para o sistema o limiar que apresentou menor erro
12
Construção Automática do
Classificador
Criados automaticamente através da
apresentação dos exemplos ao algoritmo
de treinamento.
Dados de
treinamento
Classificador
Dados
classificados
Comparador
Ajuste dos resultados pelo desenvolvedor
CIn/UFPE
13
Construção Automática do
Classificador
Documentos
Representação Inicial
Conhecimento
Adicional
Categorização
CIn/UFPE
Indução
Redução da Dimensão
ou
Seleção de Termos
Representação Final
14
Construção Automática do
Classificador
Representação Inicial dos Documentos

CIn/UFPE
Utiliza pré-processamento com as mesmas
técnicas de recuperação de informação!!
15
Pré-Processamento dos
Documentos
Objetivo

Criar uma representação computacional do documento
seguindo algum modelo
Fases


Operações sobre o texto
Criação da representação
Doc original
Operações de Texto
Doc : www.filosofia.com
Doc : www.filosofia.com
“Se o desonesto soubesse a
vantagem de ser honesto,
ele seria honesto ao menos
por desonestidade.”
desonesto / soubesse /
vantagem / honesto /
seria / honesto /
menos/desonestidade/
socrates
Sócrates
Pré-Processamento
CIn/UFPE
Representação
Doc : www.filosofia.com
honesto
2
desonesto
1
soubesse
1
vantagem
1
seria
1
menos
1
desonestidade
1
socrates
1
16
Pré-Processamento:
Operações sobre o texto
Análise léxica

Converte uma cadeia de caracteres em uma
cadeia de palavras/termos
Eliminação de stopwords

Palavras consideradas irrelevantes
 Ex.: artigos, pronomes, alguns verbos,
“WWW”...
 www.cin.ufpe.br/~compint/aulas-IAS\ias\stoplist
Pré-Processamento
CIn/UFPE
-
17
Pré-Processamento:
Operações sobre o texto
Stemming

Redução de uma palavra ao seu radical
 Geralmente, apenas eliminação de sufixos

Possibilita casamento entre variações de uma
mesma palavra
Term
engineering
engineered
engineer
CIn/UFPE
Stem
engineer
engineer
engineer
Regras de redução:
ed -> 0
ing -> 0
18
Pré-Processamento:
Representação do Documento
Texto Completo

Difícil (caro) de manipular computacionalmente
Dado um documento, identificar os conceitos que
melhor descrevem o seu conteúdo
Representar o documento como um Centróide


Lista de termos com pesos associados ou não
Problema: perda da semântica
Centróide
“Se o desonesto soubesse a vantagem
de ser honesto, ele seria honesto
ao menos por desonestidade.”
Sócrates
CIn/UFPE
honesto
desonesto
soubesse
vantagem
seria
menos
desonestidade
socrates
2
1
1
1
1
1
1
1
19
Modelos de Representação de
Documentos
Modelo Booleano


Centróide sem pesos associados
A representação indica apenas se o termo está ou não
presente no documento
Modelo Espaço Vetorial

Centróide com pesos associados (ex. número de vezes
que a palavra aparece no texto)
Outros modelos:

CIn/UFPE
Booleano Estendido, Difuso, Semântica Latente,
Probabilístico, etc…
20
Modelo Booleano:
sem pesos associados
Simples de implementar e usar, porém de baixo desempenho
Documentos e consultas representados como vetores binários
de tamanho n (e.g., D = {1,0,1,1,1})


Cada posiçao corresponde a um termo usado na indexação dos
documentos sendo considerados
Consulta: termos conectados por AND, OR e NOT
Relevância “binária”:


O documento é considerado relevante sse seu “casamento” com
a consulta é verdadeiro
Não é possível ordenar os documentos recuperados
Base de Documentos
k1k2
Documentos apresentados
ao usuário
Consulta: k1  k2  k3
k3
CIn/UFPE
21
Modelo Espaço Vetorial:
com pesos associados
Consultas (q) e Documentos (d) são representados como
vetores em um espaço n-dimensional
 Onde n é o número total de termos usados para indexar os
documentos sendo considerados
Relevância: co-seno do ângulo entre q e d

Quanto maior o co-seno, maior é a relevância de d para q
Ordenação: dada pelo co-seno do ângulo entre q e d
Consulta q :
Brasil Olimpíadas Sidney
Documento d :
Brasil em Sidney 2000
O Brasil não foi bem no quadra
das medalhas da Olimpíada de
Sidney 2000 ...
CIn/UFPE
Sidney
Representação de q
Brasil
0.4
Olimpíadas 0.3
Sidney
0.3
q
0.4
Representação de d
Brasil
0.5
Olimpíadas 0.3
Sidney
0.2
0.3
Olimpíadas
d
0.5
Brasil
22
Representação do Documento com
Pesos
Centróide

Pesos associadas aos termos como indicação de
relevância:
 Freqüência de ocorrência do termo no documento
 TF-IDF = Term Frequency x Inverse Document
Frequency
 D  TF(w): freqüência da palavra w no doc.
 DF(w): freqüência de w em D
TFIDF( )  TF ( )  log

 DF ( )  D = total de documentos
 TF-IDF também considera palavras com baixa
ocorrência na base de documentos como melhores
discriminantes
CIn/UFPE
23
Representação do Documento com
Pesos
Centróide

Limitar tamanho do centróide em 50
mantendo apenas termos com maior peso
 Aumenta a eficiência do sistema
 Estudos mostram que isso não altera muito o
seu poder de representação do centróide
CIn/UFPE
24
Representação do Documento com
Pesos
Enriquecendo a representação:

Considerar formatação do texto como
indicação da importância dos termos
 título, início, negrito,...

Adicionar informação sobre a localização do
termo no documento
Representação de documentos usada pelo Google
Doc :xxx
word : z - hit hit hit hit
word : y - hit hit hit ...
word : w - hit
CIn/UFPE
hit: 1bit capitalization; 3bit font size; 12 bit position
25
Redução da Dimensão da
Representação Inicial
Objetivo:

Reduzir o tamanho dos centróides para diminuir o
risco de super-especialização do classificador gerado
(overfitting)
Abordagens:


Seleção de um subconjunto de termos
Indução Construtiva
Tipos de Redução:


CIn/UFPE
Global: considera um conjunto de termos para todas
as classes
Local: considera um conjunto de termos para cada
classes
26
Seleção dos Termos
Cada termo recebe uma “relevância”, que é
usada para ordenar a lista de termos
Os “n” primeiros termos mais relevantes são
utilizados para treinar o algoritmo
Várias técnicas:


Freqüência de ocorrência nos documentos
(redução global)
Outras (redução local)
 Entropia, Coeficiente de Correlação, 2 , ...
CIn/UFPE
27
Seleção dos Termos: Entropia
(mutual information)
A relevância do termo Wi para a classe Cj é medida
pela diferença de entropia dessa classe antes e
depois do uso desse termo na sua predição
c
H   P(C j )  log2 P(C j )
(incerteza inicial)
j 1
c
H '   P(C j | Wi )  log2 P(C j | Wi )
(incerteza final)
j 1
E  H ' H
CIn/UFPE
(qtd. de incerteza removida)
28
Seleção dos Termos:
Coeficiente de Correlação
Coeficiente de Correlação entre o termo t e a classe Cj :
( N r   N n  N r   N n )  N
C
( N r   N r  )  ( N n  N n )  ( N r   N n )  ( N r   N n )
Nr+ = documentos relevantes para Cj que contêm o termo t
Nr- = documentos relevantes para Cj que não contêm t
Nn+ = documentos não relevantes para Cj que contêm t
Nn- = documentos não relevantes para Cj que não contêm t
χ2:mede a dependência entre um termo t e a classe Cj
 2  C2
CIn/UFPE
29
Indução Construtiva
Objetivo:

Obter novos termos (pela combinação dos termos
originais) que maximizem a precisão dos resultados
Clustering:

Técnica usada para agrupar termos originais de acordo
com o grau de relacionamento semântico entre eles
 O relacionamento pode ser dado, por exemplo, pela co-
ocorrência dos termos no conjunto de treinamento


CIn/UFPE
Cada cluster gerado passa a ser usado como um novo
“termo”
Assim, termos redundantes são removidos
30
Construção Automática de
Classificadores
Abordagem Simbólica:


Árvores de Decisão
Indução de Regras
Abordagem Numérica:



CIn/UFPE
Aprendizagem Bayesiana
Redes Neurais Artificiais
Aprendizagem Baseada em Instâncias
31
Comparação das Abordagens
Tempo de
Trein.
Tempo de
Class.
Sistema
Extens.
Interp. do
Resul
Repr. do
Conhec.
Regras
Manuais
Lento
Rápido
Sim
Sim
Simb.
(regras)
Árvores de
Decisão
Rápido
Rápido
Não
Razoável
Simb.
(árvore)
Indução de
Regras
Rápido
Rápido
Não
Sim
Simb.
(regras)
Apr. Bas.
Instâncias
-
Lento
Não
Não
Num.
(distân.)
Aprendiz.
Bayesiana
Rápido
Rápido
Não
Não
Num.
(probab.)
Redes
Neurais
Lento
Rápido
Não
Não
Num.
(pesos)
CIn/UFPE
32
Avaliação
A avaliação baseia-se na noção de matriz de
confusão
Exemplos
classe 1
...
Exemplos
classe n
CIn/UFPE
Classificados
como classe 1
k
...
Classificados
como classe n
j
...
h
l
33
Avaliação
Cobertura: total de documentos relevantes
retornados sobre o número total dos relevantes
existentes
Precisão: documentos relevantes retornados
sobre o número total de retornados
Todos os Documentos
Documentos Relevantes
Documentos Retornados
Relevantes Retornados
CIn/UFPE
34
Avaliação
F-measure: média gemétrica das medidas anteriores
F = 2 * cobertura * precisão
cobertura + precisão
É a mais usada em recuperação de informação e
pode ser usada em categorização quando há
duas classes
CIn/UFPE
35
Avaliaçã: exemplo
Exemplo:
 total de páginas do corpus = 200
 total de páginas positivas do corpus = 170
 total de páginas negativas do corpus = 30
 total de páginas positivas classificadas corretamente como
positivas = 130
 total de páginas negativas classificadas como positivas = 20
 total geral de páginas classificadas como positivas = 150
Precisão = 130 / 150 = 0,87
Cobertura = 130 / 170 = 0,76
F-measure = (2 * 0,87 * 0,76) / (0,87 + 0,76)
= 1,32 / 1,63 = 0,81
CIn/UFPE
36
Validação
Teste do sistema num corpus conhecido e
etiquetado manualmente

Sabe-se a relevância de um documento em relação
a uma Consulta
TREC, Reuters, ...
CIn/UFPE
37
Referências
Categorização de Documentos:


Sebastiani, F. A Tutorial on Automated Text Categorization. Analia
Amandi and Alejandro Zunino (eds.), Proceedings of ASAI-99, 1st
Argentinian Symposium on Artificial Intelligence, Buenos Aires,
AR, pp. 7-35. 1999.
Moulinier, I. A Framework for Comparing Text Categorization
Approaches. AAAI Spring Symposium on Machine Learning and
Information Access, Stanford University, March 1996.
Sistemas Baseados em Conhecimento:


CIn/UFPE
Hayes, P. J. & Weinstein, S. P. Construe-TIS: A System for
Content-Based Indexing of a Database of News Stories. Second
Annual Conference on Innovative Applications of Artificial
Intelligence, pp. 48-64. 1990.
Neves, M. L. CitationFinder: Um Sistema de Meta-busca e
Classificação de Páginas de Publicações na Web. Tese de
Mestrado, Centro de Informática, UFPE, Fevereiro de 2001.
38
Referências
Aprendizagem de Máquina:

Aprendizagem Bayesiana (Naive Bayes):
McCallum, A. K.; Nigam, K.; Rennie, J. & Seymore, K. Automating the
Construction of Internet Portals with Machine Learning. Information
Retrieval Journal, volume 3, pages 127-163. 2000.

Redes Neurais:
Wiener, E.; Pedersen, J. O. & Weigend, A. S. A Neural Network
Approach to Topic Spotting. In Proceedings of the 4th Symposium on
Document Analysis and Information Retrieval (SDAIR 95), pages 317332, Las Vegas, NV, USA, April 24-26. 1995.

Aprendizagem Baseada em Instâncias:
Masand, B; Linoff, G. & Waltz, D. Classifying News Stories using
Memory Based Reasoning. Proceedings of SIGIR-92, 15th ACM
International Conference on Research and Development in
Information Retrieval, pp. 59-65, Denmark. 1992.
CIn/UFPE
39
Referências
Aprendizagem de Máquina (cont.):
Árvores de Decisão:

Lewis, D. D. & Ringuette, M. A Comparison of Two Learning Algorithms for
Text Categorization. In Third Annual Symposium on Document Analysis and
Information Retrieval, pp. 81-93. 1994.
Indução de Regras:

Apté, C.; Damerau, F. & Weiss, S. Automated Learning of Decision Rules for
Text Categorization. ACM Transactions on Information Systems, Vol. 12, No.
3, July 1994, pages 233-151. 1994.
Seleção de Termos:

Ng, H. T.; Goh, W. B. & Low, K. L. Feature Selection, Perceptron learning and
a Usability Case Study for Text Categorization. Proceedings of SIGIR-97, 20th
ACM International Conference on Research and Development in Information
Retrieval, pp. 67-73, Philadelphia, PA, USA. 1997.

CIn/UFPE
Maron, M. E. Automatic Indexing: An Experimental Inquiry. Journal of ACM,
8: 404-417. 1961.
40