Filtragem de spam bayesiana

A filtragem de spam Bayesiana (referindo-se ao teorema de Bayes ) é uma detecção técnica estatística de spam baseada no classificador Naive Bayes .

Os filtros bayesianos funcionam correlacionando a presença de certos elementos (geralmente palavras, às vezes outras coisas) em uma mensagem e se eles geralmente aparecem em mensagens indesejadas ( spam ) ou legítimas ( ham ) para calcular a probabilidade de que essa mensagem seja spam.

A filtragem de spam bayesiana é uma técnica poderosa para lidar com e-mail de spam. Ele se adapta aos hábitos de envio de cada um e produz uma taxa de falsos positivos baixa o suficiente para ser aceitável.

Histórico

O primeiro programa de filtragem de e-mail a usar Bayes foi o programa iFile de Jason Rennie, lançado em 1996. Esse programa era usado para classificar mensagens em pastas . A primeira publicação acadêmica sobre filtragem de spam Bayesiana foi feita por Sahami et al. em 1998. Em 2002, os princípios da filtragem Bayesiana foram trazidos à atenção de um público mais amplo em um artigo de Paul Graham .

Variações da técnica básica foram implementadas em diversos trabalhos de pesquisa e produtos de software . Muitos agentes de e-mail modernos implementam filtros de spam bayesianos . Os usuários também podem instalar software de terceiros especializado neste trabalho. Também é possível implementar este tipo de filtros em servidores usando software especializado, como DSPAM  (en) , SpamAssassin , SpamBayes  (en) , Altospam , Bogofilter , OutClock , Spamihilator ou mesmo ASSP  (en) , e esta característica é, por vezes integrados com o próprio servidor de e-mail.

Processar

Certas palavras têm maior probabilidade de aparecer em spam e e-mails legítimos. Por exemplo, a maioria das pessoas frequentemente encontrará a palavra “  Viagra  ” em seus e-mails de spam, mas raramente a encontrará em seus e-mails legítimos. O filtro não conhece essas probabilidades com antecedência, por isso é preciso uma curva de aprendizado para avaliá-las. O aprendizado é de responsabilidade do usuário, que deve indicar manualmente se a mensagem é spam ou não. Para cada palavra de cada mensagem "aprendida", o filtro ajustará as probabilidades de encontrar essa palavra em spam ou e-mail legítimo e armazenará em seu banco de dados. Por exemplo, é muito provável que os filtros bayesianos tenham uma alta probabilidade de enviar spam para a palavra "Viagra", mas uma probabilidade muito baixa para palavras encontradas em e-mails legítimos, como nomes de amigos e parentes do usuário.

Após o treinamento, as probabilidades de palavras (também chamadas de funções de verossimilhança ) são usadas para calcular a probabilidade de uma mensagem (todas essas palavras) ser spam. Cada palavra na mensagem, ou pelo menos cada palavra “interessante” na mensagem, contribui para a probabilidade de a mensagem ser spam. Esta contribuição é calculada usando o teorema de Bayes . Depois de concluído o cálculo de toda a mensagem, comparamos sua probabilidade de ser spam com um valor arbitrário (95% por exemplo) para marcar ou não a mensagem como spam.

Como acontece com qualquer outra técnica de filtragem de spam, as mensagens marcadas como spam podem ser movidas automaticamente para uma pasta “lixo” ou mesmo excluídas no local. Alguns softwares implementam mecanismos de quarentena que definem um intervalo de tempo durante o qual o usuário tem a oportunidade de revisar a decisão do software.

O aprendizado inicial pode freqüentemente ser refinado se alguma vez forem identificadas más decisões de software ( falsos positivos ou falsos negativos ). Isso permite que o software se adapte à natureza em evolução do spam.

Alguns filtros de spam combinam os resultados da filtragem de spam Bayesiana com outros métodos heurísticos (regras predefinidas em relação ao conteúdo da mensagem, exame do envelope da mensagem,  etc. ), o que leva a uma filtragem ainda mais precisa, às vezes em detrimento da adaptabilidade.

Fundamentos matemáticos

Os filtros de spam bayesianos são baseados no teorema de Bayes . O teorema de Bayes é usado várias vezes no contexto de spam:

• uma primeira vez, para calcular a probabilidade de que a mensagem seja spam, sabendo que uma determinada palavra aparece nesta mensagem;
• uma segunda vez, para calcular a probabilidade de a mensagem ser spam, considerando todas as suas palavras, ou um subconjunto significativo de suas palavras;
• às vezes, uma terceira vez, para lidar com palavras raras.

Calcule a probabilidade de uma mensagem contendo uma determinada palavra ser spam

Suponha que a mensagem suspeita contenha a palavra "  Réplica  ". Em 2009, a maioria das pessoas acostumadas a receber e-mail sabe que é provável que essa mensagem seja spam, especificamente uma tentativa de vender marcas de relógios falsas famosas. O software de detecção de spam ignora esses fatos, no entanto, tudo o que pode fazer é calcular as probabilidades.

A fórmula que o software usa para determinar essa probabilidade é derivada do teorema de Bayes . Estes, em sua forma mais geral, são:

P(S|M)=P(M|S)⋅P(S)P(M|S)⋅P(S)+P(M|H)⋅P(H){\ displaystyle P (S | M) = {\ frac {P (M | S) \ cdot P (S)} {P (M | S) \ cdot P (S) + P (M | H) \ cdot P (H)}}}

ou :

• P(S|M){\ displaystyle P (S | M)}é a probabilidade de a mensagem ser spam, sabendo que a palavra "  Replica  " está lá;
• P(S){\ displaystyle P (S)} é a probabilidade absoluta de que qualquer mensagem seja spam;
• P(M|S){\ displaystyle P (M | S)}é a probabilidade de que "  Replica  " apareça em mensagens de spam;
• P(H){\ displaystyle P (H)}é a probabilidade absoluta de que qualquer mensagem não seja spam (ou seja, “  ham  ”);
• P(M|H){\ displaystyle P (M | H)}é a probabilidade de que "  Replica  " apareça nas mensagens do ham .

(Prova: teorema de Bayes # Outros escritos do teorema de Bayes )

Spamicity

Estatísticas recentes mostram que a probabilidade atual de qualquer mensagem ser spam é de pelo menos 80%:

P(S)=0,8;P(H)=0,2{\ estilo de exibição P (S) = 0,8; P (H) = 0,2}

A maioria dos softwares de detecção de spam Bayesian considera que não existe a priori razão que uma mensagem recebida é spam em vez de presunto , e considera os dois casos de ter probabilidades iguais de 50%:

P(S)=0,5;P(H)=0,5{\ displaystyle P (S) = 0,5; P (H) = 0,5}

Os filtros que fazem essa suposição são considerados "imparciais", o que significa que não influenciam na correspondência recebida. Esta suposição torna possível simplificar a fórmula geral:

P(S|M)=P(M|S)P(M|S)+P(M|H){\ displaystyle P (S | M) = {\ frac {P (M | S)} {P (M | S) + P (M | H)}}}

Essa quantidade é chamada de espamicidade da palavra "  Réplica  " e pode ser calculada. O número que aparece nesta fórmula é aproximado pela frequência de mensagens contendo "  Réplica  " entre as mensagens identificadas como spam durante a fase de aprendizagem. Da mesma forma, é aproximado pela frequência de mensagens contendo "  réplica  " entre as mensagens identificadas como ham durante a fase de aprendizado. Para que essas aproximações sejam realistas, o conjunto de mensagens “aprendidas” deve ser suficientemente grande e representativo. Além disso, é recomendado que o conjunto de mensagens usado para treinamento esteja de acordo com a suposição de 50% sobre a divisão entre mensagens de spam e inocentes, ou seja, o corpus de spam e o corpus de spam. Ham têm aproximadamente o mesmo tamanho. P(M|S){\ displaystyle P (M | S)}P(M|H){\ displaystyle P (M | H)}

Obviamente, determinar se uma mensagem é spam ou não com base apenas na presença da palavra "  Réplica  " pode levar ao erro. É por isso que o software anti-spam tenta considerar várias palavras e combinar seu spam para determinar a probabilidade geral de sendo spam.

Combine as probabilidades individuais

O software de filtragem de spam bayesiano assume ingenuamente que as palavras na mensagem são eventos independentes . Isso é errado em línguas naturais como o francês, onde a probabilidade de encontrar um adjetivo, por exemplo, é influenciada pela probabilidade de ter um nome. De qualquer forma, com essa suposição, podemos deduzir outra fórmula do teorema de Bayes  :

p=p1p2⋯pNÃOp1p2⋯pNÃO+(1-p1)(1-p2)⋯(1-pNÃO){\ displaystyle p = {\ frac {p_ {1} p_ {2} \ cdots p_ {N}} {p_ {1} p_ {2} \ cdots p_ {N} + (1-p_ {1}) (1 -p_ {2}) \ cdots (1-p_ {N})}}}

ou :

• p{\ displaystyle p} é a probabilidade de a mensagem suspeita ser spam;
• p1{\ displaystyle p_ {1}}é a probabilidade de ser spam, sabendo que contém uma primeira palavra (por exemplo "  Réplica  ");P(S|M1){\ displaystyle P (S | M_ {1})}
• p2{\ displaystyle p_ {2}}é a probabilidade de ser spam, sabendo que contém uma segunda palavra (por exemplo, "  relógios  ");P(S|M2){\ displaystyle P (S | M_ {2})}
• etc.
• pNÃO{\ displaystyle p_ {N}}é a probabilidade de ser spam, sabendo que contém uma enésima palavra (por exemplo, "  casa  ").P(S|MNÃO){\ displaystyle P (S | M_ {N})}NÃO{\ displaystyle N}

(Demonstração: Combinando probabilidades no site MathPages)

Essas suposições tornam o software de filtragem bayesiana um processo de classificação bayesiano ingênuo .

O resultado geralmente é comparado a um determinado limite para decidir se a mensagem é spam ou não. Se estiver abaixo desse limite, a mensagem é considerada provavelmente legítima. Caso contrário, é considerado provavelmente ilegítimo. p{\ displaystyle p}p{\ displaystyle p}

Outra expressão da fórmula para combinar as probabilidades individuais

Freqüentemente, não é calculado diretamente usando a fórmula acima, porque tende a produzir sopas aritméticas ( underflows aritméticos ), uma vez implementado em um programa de computador. Em vez disso, podemos usar logaritmos reescrevendo a fórmula original assim: p{\ displaystyle p}

1p-1=(1-p1)(1-p2)...(1-pnão)p1p2...pnão{\ displaystyle {\ frac {1} {p}} - 1 = {\ frac {(1-p_ {1}) (1-p_ {2}) \ dots (1-p_ {n})} {p_ { 1} p_ {2} \ dots p_ {n}}}}

Tomando o logaritmo de ambos os lados da igualdade:

em⁡(1p-1)=∑eu=1NÃO[em⁡(1-peu)-em⁡peu]{\ displaystyle \ ln \ left ({\ frac {1} {p}} - 1 \ right) = \ sum _ {i = 1} ^ {N} \ left [\ ln (1-p_ {i}) - \ ln p_ {i} \ right]}

Vamos posar . Então, η=∑eu=1NÃO[em⁡(1-peu)-em⁡peu]{\ displaystyle \ eta = \ sum _ {i = 1} ^ {N} \ left [\ ln (1-p_ {i}) - \ ln p_ {i} \ right]}

1p-1=eη{\ displaystyle {\ frac {1} {p}} - 1 = e ^ {\ eta}}

Isso dá a expressão alternativa da fórmula para calcular a probabilidade combinada:

p=11+eη{\ displaystyle p = {\ frac {1} {1 + e ^ {\ eta}}}}

Lide com palavras raras

No caso em que a palavra "  Réplica  " nunca foi encontrada durante a fase de aprendizado, o numerador e o denominador são ambos zero, tanto na fórmula geral de cálculo da probabilidade quanto uma mensagem contendo esta palavra é spam apenas na fórmula de cálculo a espamicidade dessa palavra. O software de filtragem de correio pode decidir rejeitar tais palavras para as quais nenhuma informação está disponível.

De forma mais geral, palavras que foram encontradas apenas um pequeno número de vezes durante a fase de aprendizagem são problemáticas, porque seria um erro confiar cegamente nas informações que elas fornecem. Uma solução simples é deixar essas palavras de lado também.

Aplicando o teorema de Bayes novamente e assumindo que a classificação entre spam e correio legítimo é uma variável aleatória que obedece à lei beta , outro software decide usar uma probabilidade corrigida:

P′(S|M)=s⋅P(S)+não⋅P(S|M)s+não{\ displaystyle P '(S | M) = {\ frac {s \ cdot P (S) + n \ cdot P (S | M)} {s + n}}}

ou :

• P′(S|M){\ displaystyle P '(S | M)} é a probabilidade corrigida de que a mensagem seja spam, sabendo que contém uma determinada palavra;
• s{\ displaystyle s}é a força que damos às informações sobre spam ambiente;
• P(S){\ displaystyle P (S)} é a probabilidade de uma mensagem recebida ser spam;
• não{\ displaystyle n} é o número de ocorrências desta palavra durante a fase de aprendizagem;
• P(S|M){\ displaystyle P (S | M)} é a espamicidade da palavra.

(Demonstração: no artigo Uma abordagem estatística para o problema do spam )

A probabilidade corrigida é usada em vez de espamicidade na fórmula que combina as probabilidades de cada palavra.

P(S){\ displaystyle P (S)}pode novamente ser considerado igual a , para evitar que um filtro seja muito suspeito. é um bom valor para , o que significa que são necessárias mais de três mensagens para ter mais confiança no valor do spam do que nas informações de spam do ambiente. 0,5{\ displaystyle 0,5}3{\ displaystyle 3}s{\ displaystyle s}

Esta fórmula pode ser estendida para o caso em que é zero (e a espamicidade não está definida), e dá neste caso . não{\ displaystyle n}P(S){\ displaystyle P (S)}

Outras heurísticas

Palavras neutras como "le", "la", "un" (em francês) ou seus equivalentes em outras línguas são geralmente ignoradas.

De modo mais geral, a maioria dos softwares de filtragem bayesiana simplesmente ignora qualquer palavra cuja espamicidade seja próxima a 0,5, porque isso não contribui para uma boa decisão. As palavras levadas em consideração são aquelas cuja spamicidade é próxima a 0,0 (sinais distintivos de mensagens legítimas) ou próxima a 1,0 (sinais distintivos de mensagens ilegítimas). Um método pode ser manter apenas as dez palavras para as quais o valor absoluto é o maior. |0,5-peu|{\ displaystyle | 0,5-pI |}

Alguns softwares levam em consideração o fato de que uma determinada palavra aparece mais de uma vez na mensagem examinada, outros não.

Alguns softwares usam padrões (grupos de palavras) em vez de palavras isoladas em linguagem natural. Por exemplo, para um pop- up de quatro palavras, eles calculam a espamicidade de "Viagra é bom para", em vez de calcular a espamicidade de "Viagra", "é", "bom" e "para" Este método oferece mais sensibilidade ao contexto e elimina melhor o ruído bayesiano , mas requer um banco de dados maior.

Métodos mistos

Existem outras maneiras de combinar probabilidades individuais para palavras diferentes do que a abordagem “ingênua”. Esses métodos diferem do método ingênuo nas suposições feitas sobre os dados de entrada. Essas diferentes suposições resultam em fórmulas radicalmente diferentes para combinar as probabilidades individuais.

Por exemplo, se assumirmos que as probabilidades individuais seguem uma lei de χ² com graus de liberdade, podemos usar a fórmula: 2⋅NÃO{\ displaystyle 2 \ cdot N}

p=VS-1(-2em⁡(p1p2⋯pNÃO),2NÃO){\ displaystyle p = C ^ {- 1} (- 2 \ ln (p_ {1} p_ {2} \ cdots p_ {N}), 2N)}

onde é o inverso da função χ². VS-1{\ displaystyle C ^ {- 1}}

Probabilidades individuais também podem ser combinadas com técnicas de discriminação markoviana .

Discussão

Benefícios

Uma das principais vantagens do filtro Bayesiano é que ele se adapta ao seu usuário.

O spam que um usuário recebe geralmente está relacionado à sua atividade na Internet. Por exemplo, ao navegar na web, ele pode ter sido colocado inadvertidamente em uma lista de e-mails (apresentada como uma "carta comercial") que ele considerará spam. Na maioria das vezes, todas as mensagens enviadas para essa lista contêm palavras comuns, como o nome da lista e o endereço de e-mail do remetente. O filtro bayesiano detectará essas semelhanças e dará a elas uma alta probabilidade.

Da mesma forma, emails legítimos recebidos por vários usuários tendem a ser diferentes. Por exemplo, em um ambiente profissional, o nome da empresa em que se trabalha, bem como os nomes de clientes e fornecedores, são freqüentemente mencionados. O filtro atribuirá uma probabilidade baixa aos e-mails que contenham esses nomes.

As probabilidades podem mudar com o tempo, por meio do aprendizado contínuo, sempre que o filtro classifica incorretamente uma mensagem. Como resultado, um filtro Bayesiano costuma ser mais preciso do que as regras predefinidas.

Os filtros bayesianos são particularmente bons para evitar falsos positivos, ou seja, classificar mensagens legítimas como spam. Por exemplo, se o e-mail contiver a palavra "Nigéria", que costuma aparecer no tipo de spam nigeriano , um conjunto de regras predefinido irá rejeitá-lo automaticamente. Um filtro Bayesiano marcaria a palavra "Nigéria" como uma característica de spam, mas também levaria em consideração outras palavras importantes, como nome do cônjuge ou nomes de amigos, que geralmente são sinais de e-mail legítimo e terão precedência. A presença de a palavra “Nigéria”.

Desvantagens

O envenenamento bayesiano é uma técnica usada por spammers para tentar degradar a eficácia dos filtros de spam Bayesianos. Consiste em colocar no correio uma grande quantidade de texto inócuo (de sites de notícias ou literatura, por exemplo), ou salada textual (sequências aleatórias de palavras que parecem coerentes, mas não significam nada), para abafar o texto indesejado e enganar o filtro.

Os spammers também podem transformar palavras que geralmente só aparecem em spam. Assim, "Viagra" será transformado, por exemplo, em "Viaagra" ou "V! Agra". A leitura ainda é possível para o destinatário, mas cada uma dessas palavras transformadas só será encontrada mais raramente, o que penaliza a aprendizagem pelo filtro Bayesiano. Na prática, essa técnica funciona muito mal, porque as próprias palavras derivadas acabam sendo reconhecidas pelo filtro.

Outra técnica usada por spammers para tentar enganar o filtro Bayesiano é substituir texto por imagens. Todo o texto, ou parte dele, é substituído por uma imagem onde esse mesmo texto é "desenhado". O filtro de spam geralmente não consegue analisar esta imagem que contém palavras sensíveis como "Viagra". No entanto, muitos usuários desativam a exibição de imagens por motivos de segurança, fazendo com que os spammers alcancem menos seus alvos. Além disso, o tamanho de uma imagem é maior do que o texto equivalente e os remetentes de spam precisam de mais largura de banda para enviar mensagens contendo imagens. Alguns filtros tendem a decidir que uma mensagem é spam quando ela tem muito conteúdo gráfico. Por fim, uma solução provavelmente mais eficiente foi proposta pelo Google e utilizada pelo sistema de e-mail do Gmail  : processar qualquer imagem média ou grande por reconhecimento óptico de caracteres para analisar o texto nela contido.

Notas e referências

1. (em) Jason Rennie, "  ifile  " [texto]1996(acessado em 23 de abril de 2020 )
2. (in) Jason DM Rennie, "  ifile: An Application of Machine Learning to E-Mail Filtering  " [PDF] , Boston, MA EUA, KDD-2000 Text Mining Workshop2000(acessado em 23 de abril de 2020 )
3. (in) Mr. Sahami, S. Dumais, D. Heckerman, E. Horvitz, A Bayesian Approach to Filtering Junk E-Mail , AAAI'98 Workshop on Learning for Text Categorization ,1998.
4. (en) Paul Graham , "  A Plan for Spam  " [html] ,2002(acessado em 23 de abril de 2020 ) .
5. (in) Dylan Mors e Dermot Harnett, "  State of Spam, a mensal postponement, postponement # 33  " (em 23 de março de 2019 no Internet Archive ) .
6. (en) Gary Robinson, “  Uma abordagem estatística para o problema do spam  ” , Linux Journal ,1 ° de março de 2003( leia online , consultado em 23 de abril de 2020 ).
7. (in) Trevor Stone, "  Parametrization of Naïve Bayes for Spam Filtering  ", outono de 2003
8. (en) Software de Processo, Introdução à Filtragem Bayesiana
9. (em) "  Combinar probabilidades  " no site MathPages.
10. (in) Brian Burton, "  SpamProbe - Bayesian Spam Filtering Tweaks  " ,2003.
11. (em) Jonathan A. Zdziarski, "  Redução de Ruído Bayesian: Contextual Logic Symmetry Utilizando Padrão Consistência Analysis  " ( Arquivo • wikiwix • Archive.is • Google • ? O que fazer ) ,2004.
12. (in) "O  Gmail usa a tecnologia inovadora do Google para manter o spam fora de sua caixa de entrada  »

Veja também

Artigos relacionados

• Inferência bayesiana
• Filtragem colaborativa
• Anti spam

links externos

• (in) filtra spam Bayesian Guide: 1 st  parte , 2 de parte .
• (pt) Explicação detalhada das fórmulas de Paul Graham por Tim Peters
• (in) Blog de Gary Robinson sobre spam
• Base matemática da aprendizagem estatística

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">