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