Filtros Bayesianos – parte 1

Eu perguntei se alguem ia ler, e uns gatos pingados no twitter me disseram que sim, então vou escrever 🙂
Vou falar hoje sobre a possiblidade de classificaçnao de conteudo usando os filtros bayesianos.
Primeiramente gostaria de dizer que ele eh facil de implementar, veja definicao dele abaixo:

Pr(A |B) =Pr(B|A) x Pr(A)/Pr(B)

Bem, se voce nao fechou o browser apos o que leu acima quer dizer que estamos prontos para ver isso, juntos, ja que tanto quanto voce eu gosto do assunto, mas nao sou expert nele, e essas coisas eu aprendi pelo prazer de ver como funcionam(e saber que realmente funcionam).
Quem ja tomou uma cerveja comigo sabe que apos um certo numero de garragas/latinhas eu começo a divagar sempre sobre um assunto recorrente, algoritmos, algoritmos, algoritmos…(sim eu sou nerd e falo de programacao quando bebo)
E aqui temos um exemplo muito bonito de um algoritmo que apesar de simples, cumpre sua missão. Sua dificuldade esta no entendimento da teoria matematima que nele se encerra.

Uma das tarefas que os seres humanos mais praticam é classificar aquilo com que tem contato. Classificamos livros(romance, ficção, auto-ajuda…), música(rock, metal, punk, industrial, classica…)e tudo o mais que vemos pela frente, ate algoritmos, através dos padrões de projeto. Fazemos isso para facilitar nossa vida, afinal, categorizamos nossos gostos e podemos dar atenção a aquilo que nos interessa, sem nos perder no mar de informação que é gerado e apresentado diariamente.

Inicialmente, criamos o habito de classificar de acordo com o feeling, fazendo com que por exemplo, ao olharmos para uma pessoa tenhamos certeza de que ela não é uma pessoa legal, baseado numa sensação criada por um gesto, uma fala ou alguma outra coisa significante que ja notamos em alguem que pertencia a categoria dos “não legais”.
Depois, se a gente começa a ficar mais interessado em classificar as coisas, e sempre ficamos, passamos a usar um esquema de pontos: O burger King é melhor que o Mac Donald’s por que nele os lanches tem sabor(1 pt), tem o mesmo tamanho apresentado na foto(mais 1 ponto), o atendimento é melhor(outro ponto) e assim vai. Quanto mais pontos com relação ao outro, melhor.

Veja que nos dois apresentados acima temos situações onde a interação humana com o objeto classificado foi necessaria.
Porém, existem coisas que podem ser automatizadas e que podem ajudar nos humanos a resolver problema do dia-a-dia que de outra forma tomariam muito do nosso tempo.

Uma forma de automatizar essa classificação é através dos filtros bayesianos.
Como primeiro exemplo, vamos usar o classico de descobrir se uma mensagem é spam ou não.

Uma mensagem de e-mail é spam a partir do momento que ela é indesejada, correto. Ela é uma mensagem não solicitada que aparece na nossa caixa de e-mail e faz a gente perder um tempo batendo o olho e sacando que ela é spam ou abrindo ela para ver se tem algo importante ali. No final das contas, se fosse uma por dia, vá lá, a gente suportava, mas são muitas e fazem a leitura de e-mail ser uma tarefa penosa… fazem a gente perder tempo com coisas que não nos interessam de forma alguma.
Ai vem a sacada, podemos olhar as mensagem e classifica-las em spam e candidatas a leitura, logo, a gente pode escrever algo que ajude a fazer isso automaticamente.

Esse é um filtro que precisa ser treinado e para treinar vamos precisar de exemplos.

Vamos pegar cem e-mails que são spam, que a gente leu e confirmou que eram, e vamos pegar outros 100 que são bons para leitura.
No total temos entao 200 emails com 50% em cada categoria. A boa e a ruin(spam).

vejamos algumas palavras que apareceram em cada uma das categorias

ruim:

  • venda
  • viagra
  • remedio
  • cirurgia
  • ajuda
  • vagas
  • curso
  • assinatura
  • faculdade
  • promoção

bom:

  • venda
  • curso
  • assinatura
  • php
  • evento
  • faculdade
  • promoção

Ok, temos algumas palavras que ocorreram em cada uma das categorias que queremos classificar os e-mail que a gente recebe.
O proximo passo é ver quanto elas aparecem em cada uma das categorias. O quanto elas aparecem em cada categoria é a base para a avaliação da probabilidade de uma mensagem estar em uma categoria ou outra.

ruim (100 emails):                            Pr(palavra | ruim)

  • venda        40 ocorrências    0.4
  • viagra          60                        0.6
  • remedio      70                        0.7
  • cirurgia      30                        0.3
  • ajuda          20                        0.2
  • vagas          40                        0.4
  • curso          30                        0.3
  • assinatura 10                        0.1
  • faculdade   5                         0.05
  • promoção  50                       0.5

bom(100 ocorrências):                    Pr(palavra | bom)

  • venda        30 ocorrências    0.3
  • curso               40                    0.4
  • assinatura      10                    0.1
  • php                  50                    0.5
  • evento            40                    0.4
  • faculdade      30                    0.3
  • promoção      15                    0.15

A terceira coluna representa uma porcentagem de ocorrências das palavras em cada categoria.
Logo, podemos dizer que a palavras venda tem 40% de chance de estar num e-mail ruim(spam) e 30% de chance de estar em um e-mail bom. E isso ja nos diz algumas coisas. Diz que só a palavra venda, nessa amostragem de e-mail, não é uma boa candidata a indicar em que categoria o e-mail esta.

A avaliação que fizemos até aqui diz qual a probabilidade de uma palavra estar em uma categoria, logo, ela nos diz uma parte da equação, que é Pr(B|A). Probablidade de B(palavra) em A(categoria). Isso se chama probabilidade condicional. A probabilidade da palavra viagra na categoria ruim é de 60% e de php na categoria bom é de 50%.
Relembrando que:
Pr(A |B) =Pr(B|A) x Pr(A)/Pr(B)
resolvendo uma parte:
Sendo 100 a probabilidade da categoria (100 emails na categoria ruim, por exemplo)
e 200 a probabilidade do documento(total de email’s)
Pr(A | B) = pr(B|A) X 100 / 200


Digamos que chegou um e-mail na conta e dentro dele tinha somente uma palavra: viagra
Calculando a chance de ser um e-mail ruim

Pr(ruim | viagra) = 0.6 X 100 / 200
Pr(ruim | viagra) = 0.3

Calculando a chance de ser um bom e-mail, digno de leitura 🙂
Viagra não aparece na categoria “bom”, logo, temos 0% de change desse e-mail ser bom.

Então, que tal tirar esse e-mail da sua caixa de entrada, automaticamente, por que ele não vale seu tempo de atenção?!

Vamos avaliar outro caso: Outro e-mail, algum que tenha chegado com mais palavras, digamos: faculdade, curso, promoção e php. Aqui vai.

Pr(ruim| faculdade & curso & promoção & php) = 0.05 * 0.3 * 0.5  * 100 / 200=  0.00375
Pr(bom | faculdade & curso & promoção & php) = 0.3 * 0.4 * 0.15 * 0.5 * 100 / 200 = 0.0045


Pois é, esse e-mail pode aparecer na sua caixa de entrada, se olharmos o resultado ele esta mais para bom do que ruim.

Algumas observações devem ser feita nesse ponto.
Esta é uma demonstração do teorema de Bayes, mas na implementação existem outras considerações que devemos fazer que não foram incluidas aqui, como o fato de uma palavra, no inicio do treinamento do algoritmo poder ter ocorrido somente uma vez na categoria ruim e isso não poder indicar, de forma alguma, que ela representa somente mensagens ruins. Outro fato seria que o ideal é que um resultado da avaliação de uma categoria para outra tenham uma certa “distância” entre si, para poder garantir que realmente pertence a uma categoria, caso contrario, ainda pode haver dúvidas quanto a classificação. Mais um fato é que esse algoritmo tem se mostrado eficiente para qualificações, mas nao numa amostra tão pequena quanto a usada aqui.

Esse artigo tem continuação, na qual irei codificar o algoritmo na linguagem php, com cobertura das observações feitas acima. O artigo ja esta sendo escrito e vai ser postado, com certeza ate o fim dessa mesma semana pós Latinoware.

Algumas referências usadas aqui:

Livro Inteligência coletiva – toby Segaran (Alta Books)

Matematico Thomas Bayes

Teorema

Probablidade

Probabilidade Condicional

4 thoughts on “Filtros Bayesianos – parte 1

  1. Fala Ivo, tranquilo?? É cara, esses seus filtros ae são loucura mesmo hsauhusahsa
    ahh eu sou aquele cara que vc converso na palestra do jose wilker sobre o adobe flex.. ^^
    vlww

  2. Owww Ivo, dei também mais uma olhada no seu blog e vi que ta faltando alguma coisa de flex ae ein 😀
    vlwww

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s