Categorização de Documentos
Mariana Lara Neves
Flávia Barros
Fred Freitas
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
Aplicações
Recomendação
Classificação


Hierarquias
Pastas
Filtragem
Jornal personalizado
Roteamento
…
CIn/UFPE
4
Categorização de Documentos
Documentos
Classe 2
Classe 3
CIn/UFPE
Classe 1
5
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
6
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
7
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
8
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
9
Bases de Conhecimento em
Linguagens Específicas
Podem ser usadas linguagens mais específicas,
baseadas em presença de palavras-chave e/ou
n-gramas



CIn/UFPE
(gold (&n (reserv ! medal ! jewlry))
significa detectar a palavra ‘gold’,
mas ignorar as sentenças ‘gold reserv’, ‘gold
medal’ e ‘gold jewlry’.
10
Prós e Contras de Classificadores
Baseados em Conhecimento
PRÓS:
Melhor desempenho
 Em especial, em sistemas
integrados a extratores
Vantagens
de
soluções
declarativas
 Melhor legibilidade
 Conhecimento pode ser
comunicado
entre
agentes
 Extensibildade
CIn/UFPE
CONTRAS:
Requerem um extensivo
esforço para criar bases de
conhecimentos
 Processo custoso e lento
Pouco reuso
 Exceto em ontologias
 Normalmente,
todo o
processo de engenharia
de
conhecimento
é
repetido a cada novo
domínio
11
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
12
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
13
Categorização por Aprendizado
Dados:



Uma descrição de instância, xX,
Uma linguagem de instância ou espaço de
instância X.
Um conjunto fixo de categorias:
C={c1, c2,…cn}
Determinar:


CIn/UFPE
A categoria de x: c(x)C,
c(x) é uma função de categorização
 domínio X
 imagem C.
14
Aprendizado para Categorização
Um exemplo de treinamento é um par <x, c(x)>
 xX, uma instância
 c(x) sua categoria para uma função de
categorização, c.
Dado um conjunto de exemplos de treinamento,
D
Achar uma hipotética função de categorização,
h(x), such that:
  x, c( x)   D : h( x)  c( x)
CIn/UFPE
Consistência
15
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!!
16
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
17
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”...
Pré-Processamento
CIn/UFPE
-
18
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
19
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
20
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
Outros modelos:

CIn/UFPE
Booleano Estendido, Difuso, Semântica
Latente, Probabilístico, etc…
21
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
22
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
d
0.5
Brasil
Olimpíadas
23
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
24
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
25
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
26
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
27
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
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 (ou Agrupamento):

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
Prós e Contras de Classificadores
Baseados em Aprendizado
PRÓS:
Facilidade
Economia da engenharia de
conhecimento
Melhor desempenho
 Em especial, em sistemas
integrados a extratores
Vantagens
de
soluções
declarativas
 Melhor legibilidade
 Conhecimento pode ser
comunicado
entre
agentes
CIn/UFPE
CONTRAS:
Requerem um esforço para
anotar
os
corpi
de
treinamento
Dificuldades
de
incluir
conhecimento a priori nos
algoritmos de aprendizado
Não-extensível
Difícil de estabelecer uma
boa tendência (bias) para o
algoritmo
 Qualquer critério usada
para selecionar hipóteses
geradas pelo algoritmo
33
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.
34
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
35
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.
36