Naive Bayes, ou como a matemática permite filtrar spam

Oi Neste artigo, falarei sobre o classificador bayesiano como uma das opções para filtrar emails de spam. Vamos analisar a teoria, corrigi-la com a prática e, no final, darei meu esboço do código na minha amada linguagem R. Vou tentar expor o mais levemente possível com expressões e formulações. Vamos começar!

Nenhuma fórmula em lugar algum, bem, uma breve teoria

O classificador bayesiano pertence à categoria de aprendizado de máquina. O ponto principal é o seguinte: o sistema que enfrenta a tarefa de determinar se a próxima letra é spam foi treinado previamente por um certo número de letras que sabem exatamente onde "spam" e "onde não é spam". Já ficou claro que isso é ensinar com um professor, onde desempenhamos o papel de professor. O classificador bayesiano apresenta um documento (no nosso caso, uma carta) na forma de um conjunto de palavras que supostamente não dependem uma da outra (e essa ingenuidade se segue daqui).

É necessário calcular a nota de cada turma (spam / não spam) e escolher a que for máxima. Para fazer isso, use a seguinte fórmula:

$$ $$arg \ max [P (Q_k) \ prod_ {i = 1} ^ nP (x_i | Q_k)]$$

$$$P (Q_k) = \ cfrac {\ text {número de documentos da classe $ Q_k $}} {\ text {número total de documentos}}$
$$$P (x_i | Q_k) = \ cfrac {\ alpha + N_ {ik}} {\ alpha M + N_k}$- ocorrência de palavras $$$x_i$no documento da classe $$$Q_k$(com suavização) *
$$$N_k$- o número de palavras incluídas no documento da turma $$$Q_k$
M - o número de palavras do conjunto de treinamento
$$$N_ {ik}$- o número de ocorrências da palavra $$$x_i$no documento da classe $$$Q_k$
$$$\ alpha$- parâmetro para suavização

Quando o volume do texto é muito grande, você precisa trabalhar com números muito pequenos. Para evitar isso, você pode converter a fórmula de acordo com a propriedade logaritmo **:

$$ $$\ log {ab} = \ log {a} + \ log {b}$$

Substitua e obtenha:

$$ $$arg \ max [\ log {P (Q_k)} + \ sum_ {i = 1} ^ n \ log {P (x_i | Q_k)}]$$

* Durante os cálculos, você pode encontrar uma palavra que não estava no estágio de treinamento do sistema. Isso pode levar a avaliação a zero e o documento não pode ser atribuído a nenhuma das categorias (spam / não spam). Não importa como você queira, você não ensina ao seu sistema todas as palavras possíveis. Para fazer isso, é necessário aplicar suavização, ou melhor, fazer pequenas correções em todas as probabilidades de entrada de palavras no documento. O parâmetro 0 <α≤1 é selecionado (se α = 1, então isso é suavização de Laplace)

** O logaritmo é uma função monotonicamente crescente. Como pode ser visto na primeira fórmula - estamos procurando o máximo. O logaritmo da função atingirá o pico no mesmo ponto (abscissa) que a própria função. Isso simplifica o cálculo, porque apenas o valor numérico é alterado.

Da teoria à prática

Deixe nosso sistema aprender com as seguintes cartas, conhecidas antecipadamente onde "spam" e "onde não é spam" (exemplo de treinamento):

Spam

• “Cupons a um preço baixo”
• “Promoção! Compre uma barra de chocolate e ganhe um telefone de presente »

Não é spam:

• "A reunião será realizada amanhã"
• "Compre um quilo de maçãs e uma barra de chocolate"

Atribuição: determine a qual categoria a seguinte letra pertence:

• “A loja tem uma montanha de maçãs. Compre sete quilos e uma barra de chocolate ”

Solução:

Nós fazemos uma mesa. Removemos todas as “palavras de parada”, calculamos as probabilidades, tomamos o parâmetro para suavização como um.



Classificação para a categoria Spam:

$$ $$\ frac {2} {4} \ cdot \ frac {2} {23} \ cdot \ frac {2} {23} \ cdot \ frac {1} {23} \ cdot \ frac {1} {23} \ cdot \ frac {1} {23} \ cdot \ frac {1} {23} \ cdot \ frac {1} {23} \ approx0,00000000058587 (\ text {ou 5.87E-10})$$

Classificação para a categoria "Não spam":

$$ $$\ frac {2} {4} \ cdot \ frac {2} {21} \ cdot \ frac {2} {21} \ cdot \ frac {2} {21} \ cdot \ frac {2} {21} \ cdot \ frac {1} {21} \ cdot \ frac {1} {21} \ cdot \ frac {1} {21} \ approx0,00000000444 (\ text {ou 4.44E-9})$$

Resposta: a classificação "Não é spam" é mais do que a classificação "Spam". Portanto, a carta de verificação não é spam!

Calculamos o mesmo com a ajuda de uma função transformada pela propriedade do logaritmo:
Classificação para a categoria Spam:

$$ $$\ log {\ frac {2} {4}} + \ log {\ frac {2} {23}} + \ log {\ frac {2} {23}} + \ log {\ frac {1} {23 }} + \ log {\ frac {1} {23}} + \ log {\ frac {1} {23}} + \ log {\ frac {1} {23}} + \ log {\ frac {1} {23}} \ aproximadamente $ 21,2$$

Classificação para a categoria "Não spam":

$$ $$\ log {\ frac {2} {4}} + \ log {\ frac {2} {21}} + \ log {\ frac {2} {21}} + \ log {\ frac {2} {21 }} + \ log {\ frac {2} {21}} + \ log {\ frac {1} {21}} + \ log {\ frac {1} {21}} + \ log {\ frac {1} {21}} \ aproximadamente $ 19,2$$

Resposta: semelhante à resposta anterior. E-mail de verificação - sem spam!

Implementação da linguagem de programação R

Ele comentou quase todas as ações, porque sei quantas vezes não quero entender o código de outra pessoa, por isso espero que a leitura da minha não lhe cause dificuldades. (oh como eu espero)


Muito obrigado pelo seu tempo lendo meu artigo. Espero que você tenha aprendido algo novo para si mesmo ou simplesmente tenha esclarecido momentos que não estão claros para você. Boa sorte

Fontes:

1. Um artigo muito bom sobre o classificador ingênuo de Bayes
2. Conhecimento derivado do Wiki: aqui , aqui e aqui
3. Palestras sobre Data Mining Chubukova I.A.