#!/usr/bin/env python
# coding: utf-8

# # Naive Bayes
# 
# Um classificador na aprendizagem de máquina supervisionada tem como objetivo prever uma classe para uma entrada de acordo com dados de treinamento. O classificador Naive Bayes utiliza o teorema de Bayes para classificar um exemplo de teste, que é definido por um conjunto de características, com a classe mais provável para o exemplo.
# 
# Dado que um exemplo de entrada é definido por um vetor de características: [$x_1$, $x_2$, ..., $x_n$], e que um problema tem um conjunto $C$ de possíveis classes, o classificador precisa encontrar uma resposta $R$ definida por:
# 
# $$R = argmax_{(c \in C)} P(c | x_1, x_2, ..., x_n)$$
# 
# Ou seja, ele precisa encontrar a classe $c$ que tenha a maior probabilidade dadas as características do exemplo de teste.

# Utilizando o teorema de Bayes podemos reescrever a expressão $P(c | x_1, x_2, ..., x_n)$ da seguinte forma:
# 
# $$P(c | x_1, x_2, ..., x_n) = \frac{ P(x_1, x_2, ..., x_n | c)P(c)}{ P(x_1, x_2, ..., x_n)}$$
# 
# Substituindo na fórmula para encontrar R, temos:
# 
# $$R = argmax_{(c \in C)}  \frac{ P(x_1, x_2, ..., x_n | c)P(c)}{ P(x_1, x_2, ..., x_n)}$$
# 
# 
# Como $ P(x_1, x_2, ..., x_n)$ é constante para um dado exemplo de teste, então, para maximizar $P(c | x_1, x_2, ..., x_n)$, basta maximizar o numerador $P(x_1, x_2, ..., x_n | c)P(c)$.

# ## Classificando
# 
# A seguir aplicaremos o classificador Naive Bayes num problema de detecção de Spam. Um e-mail recebido pode ser Spam ou pode não ser Spam, assim os dados de treinamento para esse problema trazem mensagens que foram classificadas como Spam ou não Spam. O código abaixo define duas listas, uma com mensagens classificadas como Spam e outra com mensagens classificadas como não Spam. Para fins didáticos, as mensagens são curtas e simples, mas o classificador pode ser aplicado da mesma forma para mensagens maiores.

# In[1]:


spam = ["offer is secret", "click secret link", "secret sport link"]
not_spam = ["play sport today", "went play sport", "secret sport event", "sport is today", "sport costs money"]


# Usando o Naive Bayes, vamos classificar a mensagem "secret is secret" para saber se ela é Spam ou não.
# Primeiramente, precisamos definir quais são as características dos nossos exemplos. Num classificador de Spam, podemos usar as palavras como as características. Com isso, o vetor de características do exemplo "secret is secret" é: ["secret", "is", "secret"].
# 
# Dessa forma, temos que encontrar: 
# 
# $$R = argmax_{(c \in C)} P(c | "secret", "is" , "secret")$$
# 
# Onde $C = \{spam, nãoSpam\}$.
# 
# Utilizando o Teorema de Bayes, escrevemos R como:
# 
# $$R = argmax_{(c \in C)} P("secret", "is", "secret" | c)P(c)$$
# 
# Para calcular  P("secret", "is", "secret" | c), o Naive Bayes supõe que a ordem das palavras não importa e que as probabilidade das palavras são independentes. Essa suposição não é verdade para um texto, sabemos que as palavras não são escritas de forma independente e que a ordem importa, mas essa suposição simplifica e agiliza os cálculos. Mesmo com essa suposição, em diversos casos, o Naive Bayes tem desempenho similar a classificadores mais sofisticados.
# 
# Dessa forma, $P("secret", "is", "secret" | c)$ se resume a: $P("secret"|c)P("is"|c)P("secret"|c)$.
# 
# Substituindo na equação para encontrar $R$, temos:
# 
# $$R = argmax_{(c \in C)} P("secret"|c)P("is"|c)P("secret"|c)P(c)$$
# 
# 

# Para estimar $P(c)$ basta contar quantas vezes a classe $c$ aparece nos dados de treinamento e dividir pelo total de dados de treinamento. Assim, temos:

# In[2]:


total = len(spam) + len(not_spam)
p_spam = len(spam) / total
p_not_spam = len(not_spam) / total

print("P(spam) = {}".format(p_spam))
print("P(nãoSpam) = {}".format(p_not_spam))


# Para calcular P("palavra"|c) precisamos contar quantas vezes "palavra" aparece na classe $c$ e dividir pelo total de palavras na classe $c$. A função implementada a seguir calcula a probabilidade de uma palavra dada uma classe. Ela recebe dois parâmetros, o primeiro é a palavra e o segundo é a lista com as mensagens de uma classe.

# In[3]:


def p(word, messages):
    total = 0
    word_count = 0

    for m in messages:
        words = m.split()
        
        for w in words:
            total += 1
            if w == word:
                word_count += 1
                
    return word_count/total

print("P(\"secret\" | spam) = {}".format(p("secret", spam)))
print("P(\"secret\" | nãoSpam) = {}".format(p("secret", not_spam)))


# Com a função para calcular probabilidades das palavras implementada, agora podemos verificar qual das duas classes tem a maior probabilidade para a mensagem "secret is secret".
# 
# Para a classe spam temos:
# 
# $$P("secret"|spam)P("is"|spam)P("secret"|spam)P(spam)$$
# 
# O código abaixo mostra o resultado desse cálculo:

# In[4]:


p_test_spam = p("secret", spam)*p("is", spam)*p("secret", spam)*p_spam

print("O resultado da mensagem \"secret is secret\" para a classe spam é {}".format(p_test_spam))


# Para a classe nãoSpam temos:
# 
# $$P("secret"|nãoSpam)P("is"|nãoSpam)P("secret"|nãoSpam)P(nãoSpam)$$
# 
# O código abaixo mostra o resultado desse cálculo:

# In[5]:


p_test_not_spam = p("secret", not_spam)*p("is", not_spam)*p("secret", not_spam)*p_not_spam

print("O resultado da mensagem \"secret is secret\" para a classe nãoSpam é {}".format(p_test_not_spam))


# Com os dois resultados em mãos, temos que a mensagem "secret is secret" é classificada como Spam, pois essa classe obteve o maior valor. Intuitivamente podemos perceber que isso era esperado, já que a palavra "secret" aparece com bastante frequência nos dados de treinamento para classe spam e aparece apenas uma vez para classe nãoSpam.

# O que calculamos anteriormente não são as probabilidades de ser ou não ser Spam, já que simplificamos o cálculo retirando o denominador na fórmula do teorema do Bayes. A probabilidade pode ser obtida normalizando os valores para que a soma deles seja 1. Assim, temos:
# 
# $$P("secret", "is", "secret" | spam) = \frac{0,004629629629629629}{0,004629629629629629+0,00018518518518518518} = 0,9615384615384616$$
# 
# 
# $$P("secret", "is", "secret" | nãoSpam) = \frac{0,00018518518518518518}{0,004629629629629629+0,00018518518518518518} = 0,038461538461538464$$

# ## Suavização
# 
# Vamos agora classificar a mensagem "today is secret" da mesma forma realizada anteriormente.
# 
# Para a classe spam temos:
# 
# $$P("today"|spam)P("is"|spam)P("secret"|spam)P(spam)$$
# 
# O código abaixo mostra o resultado desse cálculo:

# In[6]:


p_test_spam = p("today", spam)*p("is", spam)*p("secret", spam)*p_spam

print("O resultado da mensagem \"today is secret\" para a classe spam é {}".format(p_test_spam))


# Essa probabilidade não parece muito coerente, mudamos apenas uma palavra em relação mensagem anterior e diminuímos bruscamente o valor para classe spam.
# 
# Para a mensagem "today is secret" nós temos um problema. $P("today" | spam) = 0$, pois a palavra "today" não aparece nos dados de treinamento com a classificação Spam. Assim, uma única probabilidade igual a $0$ torna todas as outras probabilidades irrelevantes, pois 0 multiplicado por qualquer valor é igual a $0$.
# 
# Para resolver isso, utilizaremos uma técnica chamada Suavização de Laplace. A ideia dessa técnica é supor que cada palavra foi vista nos dados de treinamento uma vez a mais, ou seja, vamos adicionar 1 em todas as contagens. 
# 
# Com isso, usando a suavização de Laplace, temos:
# 
# $$P_{Laplace}(palavra|c) = \frac{count(palavra, c) + 1}{N(c) + V(c) + 1}$$
# 
# Onde, $count(palavra, c)$ é a quantidade de vezes que a palavra aparece com a classe $c$, $N(c)$ é a quantidade de palavras nos exemplos da classe $c$ e $V(c)$ é o tamanho do vocabulário para a classe $c$.
# 
# Como estamos adicionando 1 para cada palavra existente nos dados de treinamento, então o total de palavras precisa ser acrescido num valor igual à quantidade de palavras únicas, ou seja, o tamanho do vocabulário. Além disso, somamos 1 ao total de palavras do vocabulário para representar a possibilidade de palavras desconhecidas.
# 
# O código a seguir implementa o cálculo da probabilidade de uma palavra numa determinada classe usando suavização de Laplace.

# In[7]:


def p_laplace(word, messages):
    total = 1
    word_count = 1
    unique_words = set()

    for m in messages:
        words = m.split()
        
        for w in words:
            unique_words.add(w)
            total += 1
            if w == word:
                word_count += 1

    return word_count/(total+len(unique_words))

print("P_Laplace(\"today\" | spam) = {}".format(p_laplace("today", spam)))


# Classificaremos novamente "today is secret", mas agora usando a suavização de Laplace. O código abaixo apresenta o resultado do cálculo:

# In[8]:


p_test_spam = p_laplace("today", spam)*p_laplace("is", spam)*p_laplace("secret", spam)*p_spam

print("O resultado da mensagem \"today is secret\" para a classe spam é {}".format(p_test_spam))


# In[9]:


p_test_not_spam = p_laplace("today", not_spam)*p_laplace("is", not_spam)*p_laplace("secret", not_spam)*p_not_spam

print("O resultado da mensagem \"today is secret\" para a classe nãoSpam é {}".format(p_test_not_spam))


# Com isso, a mensagem "today is secret" é classificada como Spam, pois essa classe obteve o maior valor.

# ## Underflow
# 
# Usando o classificador Naive Bayes precisamos multiplicar as probabilidades de cada palavra numa mensagem. Como probabilidades são valores entre 0 e 1, multiplicar muitos valores dessa grandeza pode resultar em números extremamente pequenos. Por isso, é importante prestar atenção em casos que podem resultar em underflow.
# 
# Para evitar problemas de underflow, podemos calcular o logaritmo da multiplicação das probabilidades. Assim, temos:
# 
# $$\log( P(a_1|c)P(a_2|c)...P(a_n|c) ) = \log(P(a_1|c)) + \log(P(a_2|c)) + ... + \log(P(a_n|c))$$
# 
# Note que ao invés da multiplicação, usando o $\log$, nós somaremos os valores, evitando o underflow pela multiplicação de valores muito pequenos.