Problema
Naive Bayes supone que las variables son independientes dada la clase y elige la clase con la puntuación más alta:
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
Las variables son categorías codificadas como enteros. Estima las probabilidades a partir de los datos de entrenamiento:
- P(c) = (número de ejemplos de la clase c) / (número de ejemplos)
- P(xⱼ = v | c) = (número de ejemplos de la clase c cuya variable j vale v + 1) / (número de ejemplos de la clase c + Kⱼ)
donde Kⱼ es el número de valores distintos de la variable j entre los ejemplos de entrenamiento y la consulta. El +1 (suavizado de Laplace) evita que un valor nunca visto deje una puntuación en 0.
Devuelve la clase con la puntuación más alta; si hay empate, la clase menor. Multiplicar muchas probabilidades pequeñas puede producir subdesbordamiento, así que suma logaritmos en su lugar.
Implementa naive_bayes_predict(features, labels, query).
Entrada
features: Una fila de n variables categóricas por ejemplo de entrenamiento.
labels: La clase de cada ejemplo de entrenamiento.
query: Las n variables del ejemplo a clasificar.
Salida
Devuelve la clase predicha.
Restricciones
1 ≤ ejemplos ≤ 1000, 1 ≤ n ≤ 20
0 ≤ cada valor de variable y etiqueta ≤ 100
Ejemplos
Entrada:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Salida 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}
};
Salida 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}
};
Salida esperada:
long expected = 1;Explicación
La clase 1 tiene 3 ejemplos y la clase 0 tiene 2. La variable 1 toma los valores {0, 1} (K = 2) y la variable 2 {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. Gana la clase 1.
Entrada:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Salida 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}
};
Salida 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}
};
Salida esperada:
long expected = 0;Explicación
El valor 2 no aparece nunca, así que K = 3 (valores 0, 1 y 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 y score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Gracias al suavizado ninguna es 0, y gana la clase 0, que es más común.
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.