Problema
O Naive Bayes supõe que as variáveis são independentes dada a classe e escolhe a classe com a maior pontuação:
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
As variáveis são categorias codificadas como inteiros. Estime as probabilidades a partir dos dados de treinamento:
- P(c) = (número de exemplos da classe c) / (número de exemplos)
- P(xⱼ = v | c) = (número de exemplos da classe c cuja variável j é v + 1) / (número de exemplos da classe c + Kⱼ)
onde Kⱼ é o número de valores distintos da variável j entre os exemplos de treinamento e a consulta. O +1 (suavização de Laplace) impede que um valor nunca visto zere uma pontuação.
Retorne a classe com a maior pontuação; em caso de empate, a menor classe. Multiplicar muitas probabilidades pequenas pode causar underflow, então some logaritmos.
Implemente naive_bayes_predict(features, labels, query).
Entrada
features: Uma linha de n variáveis categóricas por exemplo de treinamento.
labels: A classe de cada exemplo de treinamento.
query: As n variáveis do exemplo a classificar.
Saída
Retorne a classe prevista.
Restrições
1 ≤ exemplos ≤ 1.000, 1 ≤ n ≤ 20
0 ≤ cada valor de variável e rótulo ≤ 100
Exemplos
Entrada:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Saída esperada:
expected = 1Entrada:
std::vector<long long> query = {0, 1};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<std::vector<long long>> features = {
{0, 1},
{0, 0},
{1, 1},
{1, 0},
{0, 1}
};
Saída esperada:
long long expected = 1;Entrada:
long[] query = new long[] {0, 1};
long[] labels = new long[] {1, 1, 0, 0, 1};
long[][] features = new long[][] {
new long[] {0, 1},
new long[] {0, 0},
new long[] {1, 1},
new long[] {1, 0},
new long[] {0, 1}
};
Saída esperada:
long expected = 1;Explicação
A classe 1 tem 3 exemplos e a classe 0 tem 2. A variável 1 tem valores {0, 1} (K = 2) e a variável 2 tem {0, 1} (K = 2). score(1) = 3/5 × (3+1)/(3+2) × (2+1)/(3+2) = 0.6 × 0.8 × 0.6 = 0.288. score(0) = 2/5 × (0+1)/(2+2) × (1+1)/(2+2) = 0.4 × 0.25 × 0.5 = 0.05. A classe 1 vence.
Entrada:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Saída esperada:
expected = 0Entrada:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
Saída esperada:
long long expected = 0;Entrada:
long[] query = new long[] {2};
long[] labels = new long[] {0, 0, 1};
long[][] features = new long[][] {
new long[] {0},
new long[] {0},
new long[] {1}
};
Saída esperada:
long expected = 0;Explicação
O valor 2 nunca aparece, então K = 3 (valores 0, 1 e 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 e score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Graças à suavização nenhuma é 0, e a classe 0, mais comum, vence.
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.