Aplicação de Técnicas de Aprendizagem de Máquina na Classificação de Mensagens de Newsgroups

Guarapuava 2018 ENUNCIADO Este trabalho será desenvolvido para obtenção de nota na disciplina SIOPESEMI10A – Tópicos Especiais em Computação I, ofertada no 1º período de 2018. O objetivo da atividade é aplicar o conhecimento adquirido durante à disciplina na construção de classificadores para a categorização de texto. O trabalho consiste em realizar o pré-processamento de um conjunto de dados conhecido como “20NewsGroup”, que contém aproximadamente 20. mensagens de textos retiradas de grupos de notícias. Após o pré-processamento dos textos deverá ser realizado experimentos para a construção de classificadores de textos utilizando algoritmos de aprendizagem de máquina disponíveis no Weka. Tabela 2. Valores de precisão por classe para o NaïveBayesMultinomial com 9092 atributos. Tabela 3. Porcentagens de instâncias classificadas corretamente e incorretamente para 5000 atributos.

Tabela 4. PRÉ-PROCESSAMENTO DE TEXTOS. Tokenização. Remoção de stopwords. Normalização. Indexação. Curva ROC. Estatísticas do Weka. Validação Cruzada. Classificação de Mensagens Newsgroup. RECURSOS DISPONÍVEIS PARA O EXPERIMENTO. SMO. IBK. J48. APLICAÇÃO DOS ALGORITMOS DE CLASSIFICAÇÃO. Experimento com X instâncias de treinamento e X atributos. A categorização de textos, também chamada de classificação de textos, é a tarefa de classificar automaticamente um conjunto de documentos e categorias (ou classes) a partir de um conjunto de classes pré-definidas [2]. Dentre as aplicações da categorização de texto estão [3]: filtragem de e-mails, tomada de decisões, entre outras. O objetivo deste trabalho é entender o processo de aprendizagem de máquina para a classificação de textos, aplicar filtros para extração e seleção de atributos, utilizar diferentes técnicas de aprendizagem de máquina e avaliar os resultados obtidos utilizando algumas medidas de desempenho.

Categorização de Textos A finalidade da categorização de textos é atribuir categorias ou classes a documentos textuais [2], sendo possível cada documento pertencer a múltiplas categorias ou a nenhuma. A tarefa de classificação corresponde a atribuir um valor booleano para cada dupla ⟨𝑑𝑗 |𝑐𝑖 ⟩ ∈ 𝐷 × 𝐶 , onde 𝐷 = {𝑑1 , 𝑑2 , 𝑑3 , … , 𝑑𝑚 } é o um conjunto de documentos, e 𝐶 = {𝑐1 , 𝑐2 , 𝑐3 , … , 𝑐𝑛 } é um conjunto fixo de classes. PRÉ-PROCESSAMENTO DE TEXTOS O pré-processamento é uma das etapas mais importante no processo de Classificação de Textos [3]. Katharina e Martin (2004) afirmam que o tempo investido no pré-processamento dos dados equivale entre 50% e 80% do tempo total da tarefa de classificação, isto evidencia a importância desta fase. Dentre as tarefas mais comuns para o pré-processamento de textos estão [3]: • Tokenização e remoção de caracteres especiais (delimitadores) • Remoção de stopwords • Normalização • Indexação • Calculo do peso de um termo • Aplicação de um limiar (Threshold) 2.

Tokenização A tokenização é o processo de extração de tokens do documento a ser manipulado, no qual um token é uma sequência não vazia de caracteres, tendo como delimitadores o espaço em branco e sinais de pontuação. Nesta fase também deve ocorrer a remoção de caracteres especiais e números, quando estes não representam relevância para o processo de discriminação. Os documentos de textos precisam ser representados em um formato adequado para a construção do classificador. Existem dois tipos de representação de documentos textuais mais utilizados: • Booleano (ou Binomial): o conjunto de textos é representado por uma matriz incidente de termos e documentos, onde os termos são geralmente são palavras. Na matriz de incidência, as linhas representam todos os termos presentes nos textos e as colunas identificam os próprios documentos.

Uma célula Cij na matriz recebe o valor de 1 quando o termo i está presente no documento j e 0 caso contrário. • Espaço vetorial (ou Multinominal): cada texto documento é representado por um vetor e os termos representam dimensões no espaço Euclidiano. Fator TF-IDF: é definido como o produto de TF e IDF, sendo calculado para analisar a frequência da ocorrência de um termo e a importância do termo para descrever um tipo de documento. O cálculo é efetuado por: Uma observação interessante resulta de perceber que, ainda quando superficialmente parece que esta técnica é contraditória ao fator IF-IDF elas não apresentariam problema nenhum, pelo fato de que o IF-IDF considera o aspecto da frequência no documento particular. SELEÇÃO DE ATRIBUTOS Considerando as abordagens para representação dos textos e a quantidade de dados cresce exponencialmente de acordo com a dimensão dos termos, a maldição da dimensionalidade e um dos problemas que atinge a tarefa de classificação de textos.

Por isso, é necessária a redução do espaço de termos para que a tarefa de classificação possa ser computacionalmente realizável. Esta tarefa é conhecida no contexto de classificação de textos como redução do espaço de termos e é realizada antes do processo indução dos classificadores [2]. CLASSIFICADORES DE TEXTOS Segundo [14], dentre os métodos de aprendizagem de máquina mais comuns aplicados na categorização de textos estão: • Árvores de decisão • Naïve Bayes • K-Vizinhos mais próximos • Máquina de vetores de suporte Vários trabalhos comparam os diferentes métodos, porém não é possível afirmar qual é o melhor método para classificar textos. A seguir, uma breve descrição destes métodos. Árvores de decisão Árvores de decisão são modelos estatísticos que utilizam um treinamento supervisionado para a classificação e previsão de dados.

Em outras palavras, em sua construção é utilizado um conjunto de treinamento formado por entradas e saídas. Estas últimas são as classes. Veja a equação abaixo: Acima: • P (c | x) é a probabilidade posterior da classe (c, alvo) dada preditor (x, atributos). • P (c) é a probabilidade original da classe. • P (x | c) é a probabilidade que representa a probabilidade de preditor dada a classe. • P (x) é a probabilidade original do preditor. K- Nearest Neighbors O algoritmo IBK é um algoritmo de aprendizagem baseado em instâncias (IBL – instance-based learning) [Aha et al. Os novos exemplos são então mapeados no mesmo espaço e preditos como pertencentes a uma categoria baseados em qual o lado do espaço eles são colocados. Em outras palavras, o que uma SVM faz é encontrar uma linha de separação, mais comumente chamada de hiperplano entre dados de duas classes.

Essa linha busca maximizar a distância entre os pontos mais próximos em relação a cada uma das classes, ver imagem: Essa distância entre o hiperplano e o primeiro ponto de cada classe costuma ser chamada de margem. A SVM coloca em primeiro lugar a classificação das classes, definindo assim cada ponto pertencente a cada uma das classes, e em seguida maximiza a margem. Ou seja, ela primeiro classifica as classes corretamente e depois em função dessa restrição define a distância entre as margens. As principais medidas de avaliação da aprendizagem supervisionada são: • TP-Rate: proporção entre os documentos classificados corretamente como positivos e o total de instâncias positivas. • FP-Rate: porcentagem entre as instâncias classificadas incorretamente como negativas e o total de instâncias negativas.

• Acurácia: porcentagem de amostras positivas e negativas classificadas corretamente sobre a soma de amostras positivas e negativas. • Sensitividade (Recall): porcentagem de amostras positivas classificadas corretamente sobre o total de amostras positivas. • Precisão: porcentagem de amostras positivas classificadas corretamente sobre o total de amostras classificadas como positivas. Concordância dos valores de Kappa [18]. VALOR DE KAPPA 0 CONCORDÂNCIA Pobre 0-0,20 21-0,40 Ligeira Considerável 0,41-0,60 Moderada 0,61-0,80 Substancial 0,81-1 Excelente 2. Validação Cruzada Uma das questões diretamente relacionadas ao bom desempenho dos classificadores está na escolha do conjunto de treinamento e teste a ser utilizada. Entretanto, os conjuntos de dados nem sempre possuem estas divisões. Principalmente para estes casos, o método de validação cruzada (cross-validation) pode ser utilizado para avaliar o desempenho dos classificadores [2]. tar. gz 1.

Os textos não contem mensagens duplicadas (cross-posts) e alguns cabeçalhos (headers) caraterísticos de newsgroups foram removidos (Xref, Newsgroups, Path, Followup-To, Date), restando apenas From e Subject. Algumas categorias estão fortemente relacionadas e, portanto, mais difíceis de discriminar. A Figura 2. Hardware e Sistema Operacional A configuração do hardware utilizado foi Aspire 515-51G-58VH, processador Intel core i5-7200U 2. GHz com Turbo Boost up to 3. GHz, memória RAM de 8GB DDR4, placa de vídeo Nvidia GEFORCE 940MX. O Sistema Operacional utilizado foi o Windows 10 Home Single Language de 64 bits. PREPARAÇÃO DO DATASET A preparação do dataset foi realizada utilizando os recursos para categorização de textos disponíveis no Weka. Filtro em Python para remoção de headers Após a implementação ocorreu o seguinte erro, apresentado na Figura 5.

Erro ocorrido para a remoção de headers. Figura 5. Erro ocorrido para a remoção de headers 3. Aplicação de Filtros para extração das características A manipulação do dataset no Weka é realiza através de arquivos do tipo ARFF ou XRFF. Outros parâmetros também podem ser preenchidos, como o charSet. Figura 7. Configuração do TextDirectoryLoader 3. O resultado do carregamento do diretório é mostrado na Figura 8. Resultado da aplicação do filtro TextDirectoryLoader, onde conjunto de mensagens é dividido inicialmente em dois atributos: text e @@class@@) que representam, respectivamente o conteúdo das mensagens e a classe à qual cada mensagens pertence. Figura 10. Configuração do filtro StringToWordVector 1. IDFTransform e TFTransform: a opção True permite realizar o cálculo do peso TF-IDF para cada termo. Em particular: 𝑇𝐹𝑖𝑗 é peso de cada termo wi (i = 1 até 2500) em cada documento dj (j = 1 até 1828); 𝐼𝐷𝐹𝑖 é o peso que depende da distribuição de cada termo em todos os documentos.

É interessante notar que de acordo o TF-IDF aqueles termos que aparecem frequentemente em poucos documentos ganham mais valor para representa-os (ex. normalizeDocLength: define se as frequências de palavra para um documento (instância) devem ser normalizada ou não. outputWordCounts: selecionar True para contar a frequência de cada palavra na mensagem e não apenas a presença ou ausência (valores booleanos 0 ou 1). Foi habilitado 1 para calcular o fator TF-IDF. periodicprunnig: especificar a periodicidade (% do conjunto de dados de entrada) em que o dicionário deve ser podado3. Não foi considerada podas periódicas por não possui recursos de memória suficiente para esta função. Foi utilizado o valor 10000, devido à limitação de memória, porém seria importante investigar melhor forma de definir este valor.

O resultado da aplicação deste filtro é um conjunto de dados com 18828 instâncias e 10201 atributos. Após esta primeira filtragem, alguns atributos foram removidos utilizando a Weka → filters → unsupervisioned → attribute → Remove, o qual é possível especificar um intervalo de índices para remoção. Como os atributos estavam ordenados, foi possível excluir os atributos com números através desta função, conforme Figura 11. Configuração do filtro Remove. Neste trabalho foram testados dois métodos: 2 e Ganho de Informação. Como a diferença no resultado obtido entre os dois método foi considerada estatisticamente insignificante (menos de 0,2) optou-se por utilizar apenas o conjunto de atributos selecionados pelo ganho de informação. Para a realização desta etapa foi utilizado o filtro acessível em: Weka → filters → supervisioned → attribute → AttributeSelection, conforme Figura 12.

Seleção do filtro AttributeSelection. Figura 12. GainRatioAttributeEval: a. DoNotCheckCapabilities = "False"; b. MissingMerge = "True". InfoGainAttributeEval: a. BinarizeNumericAttributes = "False"; b. Figura 15. Configuração do NaïveBayesMultinomial 3. NaïveBayes O algoritmo NaïveBayes é acessível em: weka → classifiers → bayes → NaiveBayes. O algoritmo possui alguns parâmetros, foi testado o useKernelEstimetion com true (Figura 16. Configuração do NaïveBayes). • buildCalibrationModels - Se deve ajustar os modelos de calibração às saídas do SVM (para estimativas de probabilidade apropriadas); • numFolds - O número de dobras para validação cruzada usada para gerar dados de treinamento para modelos de calibração (-1 significa usar dados de treinamento); • randomSeed - Semente numérica aleatória para a validação cruzada; • c - O parâmetro de complexidade C; • numDecimalPlaces - O número de casas decimais a serem usadas para a saída de números no modelo; • batchSize - O número preferencial de instâncias a serem processadas se a previsão em lote estiver sendo executada.

Mais ou menos instâncias podem ser fornecidas, mas isso dá às implementações a chance de especificar um tamanho de lote preferencial; • kernel - O kernel a ser usado; • checksTurnedOff - Desativa as verificações demoradas - use com cautela; • debug - Se definido como true, o classificador pode gerar informações adicionais para o console; • filterType - Determina como / se os dados serão transformados; • toleranceParameter - O parâmetro de tolerância (não deve ser alterado); • calibrador - O método de calibração a ser usado; • doNotCheckCapabilities - Se definido, os recursos do classificador não serão verificados antes da criação do classificador (use com cuidado para reduzir o tempo de execução); • epsilon - O epsilon para erro de arredondamento (não deve ser alterado).

Figura 17. Configuração do SMO 3. IBK O algoritmo IBK é acessível em: weka → classifiers → lazy → IBK. Resumo das estatísticas do classificador Naïve Bayes Multinomial 2. Naïve Bayes: Os resultados da aplicação deste algoritmo são apresentados na Figura 21. Resumo das estatísticas do classificador Naïve Bayes para 9446 atributos. Figura 21. Resumo das estatísticas do classificador Naïve Bayes 3. Resumo das estatísticas do classificador IBK com K=3 4 Comparativos dos Resultados Neste capítulo será realizada a análise e discussão dos resultados obtidos com os experimentos para categorização de mensagens do 20NewsGroups. Análise dos resultados para 9446 atributos A quantidade de instâncias classificadas corretamente foi de 99,9681%, é importante notar que a estatística Kappa está 0,9997 de acordo com a Tabela 1, assim é possível dar continuidade nas avaliações e analisar as outras medidas até concluir se foi obtido ou não obtivemos um bom classificador.

Os resultados das medidas de avaliação de cada classe estão apresentados na Tabela 2, e a representação gráfica na sequência. Tabela 2. Estatísticas Kappa obtidas Classificador Naïve Bayes Multinomial Naïve Bayes SMO IBK com K=1 IBK com K=3 Estatística Kappa Concordância 0,9375 0,9081 0,9965 0,9997 0,6783 Excelente Excelente Excelente Excelente Substancial 5 Considerações Finais Para a elaboração deste trabalho foi realizado um estudo sobre a aplicabilidade de algumas técnicas de aprendizado na classificação de textos. ª Edição. McGraw-Hill, 1997. ISBN: 0070428077. SEBASTIANI, F; Machine learning in automated text categorization, ACM Computing Surveys, vol. no. KORDE, C. MAHENDER, C. N. Text Classification and Classifiers: A Survey, International Journal of Artificial Intelligence & Applications (IJAIA), Vol. No. A. Feature Selection for Text Classification Based on Gini Coefficient of Inequality, Workshop and Conference Proceedings 10: 76-85 The Fourth Workshop on Feature Selection in Data Mining, 2010.

AGGARWAL, C. C. C. NIGAM, K. A comparison of event models for naive bayes text classification. AAAI-98 workshop on learning for text categorization 752, 41-48, 1998. SHAKHNAROVICH, G. DARRELL, T. BARLETT, P. SCHOLKOPF, B. SCHUURMANS, D. Introduction to Large Margin Classifiers, chapter 1, pages 1–28. MANNING, C. An introduction to ROC analysis. Pattern Recognition Letters 27 (2006) 861–874, 2006 [17] M. SOKOLOVA, N. JAPKOWICZ E S. SZPAKOWICZ, Beyond Accuracy, F-score and ROC: A Family of Discriminant Measures for Performance Evaluation, In: 19th Australian Joint Conference on Artificial Intelligence: Advances in Artificial Intelligence, Hobart, Australia, 2006.