Classificação de Texto
Baseada na aula de Henrique Borges e Ícaro Medeiros
Alterada por Flávia Barros
Roteiro
• Definição e conceitos básicos
• Técnicas de construção de classificadores
– Manual
– Automática
• Aplicações
• Avaliação/Comparação de classificadores
• Conclusão
Classificação de Texto
• Objetivo
– Classificar documentos de acordo com classes pré-definidas
• E.g., Email a ser classificado como SPAM ou NÃO-SPAM
• A classificação de documentos visa:
– Melhorar a organização da base de documentos
– Facilitar a busca e a visualização de documentos
• E.g., Hierarquias do Yahoo
– Evitar retornar documentos irrelevantes e/ou indesejáveis para
o usuário
– Entre outras...
Classificação de Texto
Algumas aplicações...
• Classificação e indexação de documentos
– Ex.: Categorização de páginas Web
• Sistemas de recomendação e filtragem
– Ex.: Filtros de spam
• Sistemas de extração de informação
– Ex.: Extração em referências bibliográficas
• etc…
Classificação de Texto
Documentos
Classe 2
Classe 3
Classe 1
Classificação x RI
• O problema de RI pode ser visto como um problema de
classificação
– RI = Classificação “binária” entre documentos relevantes ou
não relevantes
• Contudo, as duas áreas apresentam particularidades que
merecem a divisão
Classificação de Texto
• A tarefa de classificar documentos pode ser realizada de
forma
– Manual
• Realizada por um especialista
– Automática
• Realizada por um sistema automático de classificação
• Problema!
– Como construir o classificador?
Classificação manual
•
Realizada por um especialista
–
Vantagens
• Alta precisão na classificação
– Desvantagens
• Tarefa demorada e trabalhosa
Classificação automática
• É necessário construir um sistema que fará a
classificação automática dos documentos
automaticamente
– Vantagens
• Rapidez na classificação
– Desvantagens
• Dificuldades na construção do sistema
• Perda de precisão na classificação
Classificação Automática
• Abordagens para construção do classificador
– Construção manual
• Engenharia do Conhecimento
– Construção automática
• Aprendizagem de máquina
Construção manual do classificador
• Engenharia do conhecimento
– Um especialista no domínio da aplicação propõe regras para
classificar os documentos
– O sistema é implementado pelo engenheiro do conhecimento
– Dependendo do sistema, meta-informações podem ser
consideradas
• como localização das palavras no texo (título, autor, ...)
• Abordagem dominante até a década de 80
– Sistemas Especialistas
Construção manual do classificador
• Componentes básicos:
– Base de Conhecimento com regras de classificação
– Máquina de Inferência
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
Testes
e
Validação
Construção manual do classificador
• Preparação de Documentos
– Como em RI, podemos
• excluir stopwords
• usar stemming e
• redução de dimensionalidade
– Normalmente esses procedimentos melhoram a precisão e
facilitam a criação de regras de classificação
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)
Construção manual do classificador
• Vantagens
– Execução rápida do classificador
• Desvantagens
– Necessário um especialista para codificar as regras
– Muito trabalho para criar, atualizar e manter a base de regras
Construção automática do classificador
• Abordagem dominante a partir da década de 90
• Baseada em Aprendizagem de Máquina
Construção automática do classificador
• Classes são mais simples de serem definidas através de
exemplos
• Exemplos são facilmente obtidos
– Especialista:
• "Essas 20 emails são Spam, essas 50 não."
• Necessidade de atualizar ou modificar freqüentemente o
classificador
– Usuário:
• "Agora eu quero trabalhar no domínio de produtos eletrônicos."
• Solução: Aprendizagem de Máquina
Construção automática do classificador
• Aprendizagem de Máquina
– Um processo indutivo e geral que
• automaticamente constrói um classificador por aprendizagem
• usando um conjunto predefinido de categorias e suas
características.
– Ou seja
• o algoritmo "analisa" um conjunto de treinamento e "aprende" o
que diferencia uma categoria das outras
Passos da construção automática
Textos
Etiquetados
Corpus de
treinamento
Classificador
Representação
Redução da
dimensionalidade
Representação
dos documentos
(e.g. lista de termos)
Seleção ou extração
de características
Validação
Treinamento
Ajuste de
parâmetros
Indução do
classificador
Passos da construção automática
• Textos devem ser representados através de
características apropriadas
• Representação de Textos
– Listas de termos que ocorrem no texto
• Pode-se excluir stopwords, usar stemming...
• Abordagens
– Bag of Words (com TF-IDF)
– Características relevantes do domínio
– Características lingüísticas
CIn/UFPE
20
Passos da construção automática
• Quando o vocabulário da base é muito grande, o
algoritmo de aprendizagem poderá perder em
desempenho.
• Redução de dimensionalidade
– Seleção ou Extração das características mais relevantes
– Isso melhora significativamente a eficácia e a eficiência do
aprendizado
Passos da construção automática
• Fase de Treinamento
– Usa-se uma técnica/algoritmo de Aprendizagem de Máquina
• KNN
• Classificador Linear (Rocchio, etc)
• Naive Bayes
• Árvores de Decisão
• Redes Neurais
• Sopport Vector Machine (SVM)
Passos da construção automática
• Validação e Ajuste de Parâmetros
– Alguns classificadores precisam de parâmetros de entrada
escolhidos empiricamente:
• Um inteiro (K) para KNN
• Número de nós numa Rede Neural
– Parte dos documentos são separados para o algoritmo
automaticamente ajustar seus parâmetros, testando a precisão,
por exemplo
Passos da construção automática
• Testes
– Por fim, os classificadores são avaliados
• se necessário, ajustes são realizados, reiniciando o ciclo
Passos da construção automática
• Exemplo usando KNN
– Durante o treinamento, o classificador simplesmente armazena
todos os exemplos
• Num formato apropriado para facilitar a comparação entre
documentos
• Cada documento é um vetor
Construção automática do classificador
• Exemplo usando KNN
– Na classificação, escolher os K documentos do conjunto de
treinamento mais similares a entrada
• Medidas de distância: cosseno, distância euclidiana, entre
outras
– Atribuir à entrada uma classe baseada nas classes dos
documentos recuperados
• Exemplos a seguir
KNN - Maioria
Com k=1 : Classe +
Com k=5 : Classe
-
KNN - Ponderada
Avaliação de Classificadores
Avaliação de Classificadores
• Como em RI, as avaliações são feitas experimentalmente
• Corpus de documentos são geralmente divididos em:
– Conjunto de Treinamento
• Para o algoritmo aprender
– Conjunto de Validação
• Para permitir ajuste de parâmetros do sistema
– Conjunto de Teste
• Para avaliar a eficácia
Avaliação de Classificadores
• Nomenclatura em inglês:
– Tp = True positive
• Num. de exemplos corretamente classificados como positivos
– Fp = False positive
• Num. de exemplos erroneamente classificados como positivos
– Tn = True negative
• Num. de exemplos corretamente classificados como negativos
– Fn = False negative
• Num. de exemplos erroneamente classificados como negativos
Avaliação de Classificadores
• Medidas (para uma classe):
– Precisão e cobertura
– Taxa de erro
– Acurácia
• Uma média dá a efetividade geral do classificador
• Vale para as abordagens de engenharia do conhecimento
e aprendizagem de máquina
Avaliação de Classificadores
• Matriz de Confusão (Confusion Matrix)
– Número de classificações corretas em oposição às classificações
preditas para cada classe
• Seja Ci uma dada classe i
Predito →
Real ↓
Classe Ci Classe ~Ci
Erro por
classe
Classe Ci
Tp
Fn
Fn/(Tp+Fn)
Classe ~Ci
Fp
Tn
Fp/(Fp+Tn)
Avaliação de Classificadores
• Precisão para a classe Ci
– Porcentagem de exemplos corretamente classificados como
positivos
– Tp / (Tp + Fp)
• Cobertura para a classe Ci
– Porcentagem de exemplos corretamente classificados como
positivos em relação ao total de instâncias da classe
• i.e., total de exemplos da classe Ci
– Tp / (Tp + Fn)
Avaliação de Classificadores
• # total de exemplos é dado por
– N = Tp + Tn + Fp + Fn
• Precisão total = acurácia
• número de exemplos classificados corretamente /total de exemplos
da amostra
• (Tp + Tn) / N
• Erro total
– (Fp + Fn) / N
Avaliação de Classificadores
• Micromédia
– Somam-se as decisões individuais para calcular precisão e
cobertura para uma classe (média local)
– Pode não ser uma boa medida quando há classes majoritárias
(muitas instâncias positivas)
Avaliação de Classificadores
• Macromédia
– Precisão e cobertura são calculadas em relação a todas as classes
(média global)
– É melhor quando as classes são desbalanceadas
Próxima aula
• Extração de informação