Universidade Federal do Rio Grande do Sul - UFRGSPrograma de Pós-Graduação em ComputaçãoMestrado em Ciência da ComputaçãoDisciplina: Aprendizagem de MáquinaProfessor: Paulo EngelAluno: Mauricio Volkweis Astiazara

Classificador de Documentos Naïve Bayes

Este trabalho irá aplicar o método estatístico de classificador bayesiano ingênuo (naïve bayes) na classificação de documentos por assunto. O objetivo é verificar a eficácia do método através da prática, embora ele possua relaxamentos em relação ao classificador bayesiano ótimo. Os documentos serão páginas web, focadas em determinado assunto. As páginas são lidas on-line e sumarizadas pelos totais de ocorrências de cada palavra única no texto. Os documento podem ou não ser classificadas pelo usuário. Os documentos classificados pelo usuário serão utilizados para treinamento da aplicação. Depois do treinamento, a aplicação poderá classificar automaticamente novos documentos adquiridos.

Devido à necessidade de realização de contagens, totalizações e outros dados estatísticos, foi adotado o uso de um banco de dados relacionais para armazenar os dados da aplicação, como por exemplo, os dados dos documento adquiridos. Os bancos de dados relacionais são baseados na teoria dos conjuntos e geram facilmente este tipo de informação. Além disso são mais escalonáveis e robustos em relação ao uso de arquivos texto. O banco de dados utilizado foi o MySQL da Sun Microsystems. Optou-se pela implementação na linguagem de programação C-Sharp. Ela possui uma sintaxe semelhante às linguagens Java e C++.

Inicialmente foi realizada uma modelagem conceitual da aplicação com o objetivo de levantar quais a entidades necessárias para a implementação. O diagrama de classes abaixo o resultado desta modelagem. A notação utilizada é a UML.

A tarefa de treinamento foi implementada utilizando-se parte do processamento no banco de dados e parte no programa. Abaixo está o código-fonte que calcula a probabilidade a priori e a verossimilhança para uma determinada classe.

private void CalcularProbabilidadeAPriori() { string sql; sql = "select " + "(select count(*) from documento where classificacao = ?p1)" + " / (select count(*) from documento)"; _probabilidadeAPriori = Convert.ToDouble( Sistema.Instancia.Conexao.ExecutarScalar(sql, _id)); sql = "update classificacao set probabilidade_a_priori = ?p1 where id = ?p2"; Sistema.Instancia.Conexao.ExecutarSemRetorno(sql, _probabilidadeAPriori, _id); }

private void CalcularProbabilidadeDasPalavras() { string sql;

sql = "delete from palavra_de_classificacao where classificacao = ?p1"; Sistema.Instancia.Conexao.ExecutarSemRetorno(sql, _id);

double n; sql = "select count(palavra) " + "from v_palavra_por_classificacao " + "where classificacao = ?p1"; n = Convert.ToDouble( Sistema.Instancia.Conexao.ExecutarScalar(sql, _id));

double vocabulary; sql = "select count(*) from v_palavra_classificada"; vocabulary = Convert.ToDouble( Sistema.Instancia.Conexao.ExecutarScalar(sql)); double total = n + vocabulary;

sql = "insert into palavra_de_classificacao " + "(classificacao, palavra, ocorrencias, verossimilhanca) " + "select classificacao.id, v_palavra_classificada.palavra, " + "coalesce(v_palavra_por_classificacao.ocorrencias, 0) as ocorrencias, " + "coalesce(v_palavra_por_classificacao.ocorrencias, 1) / ?p1 " + "from v_palavra_classificada " + "inner join classificacao " + "left outer join v_palavra_por_classificacao " + "on v_palavra_por_classificacao.palavra = v_palavra_classificada.palavra " + "and v_palavra_por_classificacao.classificacao = classificacao.id " + "where classificacao.id = ?p2"; Sistema.Instancia.Conexao.ExecutarSemRetorno(sql, total, _id); }

A função que classifica um documento não faz uso intenso do banco de dados, sendo a maior parte do processamento realizado no programa. Na primeira versão ocorreu um problema devido a representação de números muito próximos a zero, que a partir de determinado valor eram transformados em zero, levando a resultados errôneos. Posteriormente isto foi solucionado pela substituição das multiplicações das probabilidades pela soma dos logaritmos das probabilidades. Abaixo está o código-fonte da função que indica “o quanto” um documento pertence a determinada classe.

public double Classificar(Documento pDocumento) { double probabilidade = 0; PalavraDeClassificacao palavraDeClassificacao = new PalavraDeClassificacao(this); foreach (PalavraDeDocumento palavraDeDocumento in pDocumento.Palavras) { if (palavraDeClassificacao.Buscar(palavraDeDocumento.Palavra)) { probabilidade = probabilidade + Math.Log(palavraDeClassificacao.Verossimilhanca); } }

probabilidade = Math.Log(this.ProbabilidadeAPriori) + probabilidade;

return probabilidade; }

Para utilização da aplicação foram cadastradas duas classificações alvo: “Algoritmos Genéticos” e “Redes Neurais Artificiais”. Também foi cadastrada uma classificação “Outros” para ser aplicada a qualquer documento que não fosse das classificações alvo. Adquiriu-se então da Internet, 20 documentos cujo assunto é Algoritmos Genéticos e 20 sobre Redes Neurais Artificiais e 30 de outros assuntos. Todos estes 70 documentos foram classificados manualmente para então serem usados como dados de treinamento.

Após essa tarefa, foi executada a rotina de treinamento. Para testar a classificação automática da aplicação, mais cinco documentos foram adquiridos, mas não receberam classificação manual. Destes documentos, dois eram sobre Algoritmos Genéticos e dois sobre Redes Neurais Artificiais. Também foi adquirido um documento que é uma notícia do canal de TV BBC. O objetivo era verificar se a aplicação além de classificar corretamente os documentos das classes alvo, perceberia que um documento não é de nenhuma das classes de interesse. O método funcionou corretamente em todos os dados de teste, verificando que apesar dos relaxamentos que o naïve bayes utiliza, ainda assim possui uma boa eficácia.