Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Clasificador Naive Bayes

Predice una clase a partir de variables categóricas con el teorema de Bayes y el suavizado de Laplace.

Lo que aprenderás

  • Calcular probabilidades a priori y verosimilitudes
  • Suavizar valores de características no vistos
  • Elegir la clase más probable

Problema

Ver original (inglés)

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

Ejemplo 1
Entrada:
features = [
    [0, 1],
    [0, 0],
    [1, 1],
    [1, 0],
    [0, 1]
]
labels = [1, 1, 0, 0, 1]
query = [0, 1]

Salida esperada:
expected = 1
Entrada:
std::vector<std::vector<long long>> features = {
    {0, 1},
    {0, 0},
    {1, 1},
    {1, 0},
    {0, 1}
};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<long long> query = {0, 1};

Salida esperada:
long long expected = 1;
Entrada:
long[][] features = new long[][] {
    new long[] {0, 1},
    new long[] {0, 0},
    new long[] {1, 1},
    new long[] {1, 0},
    new long[] {0, 1}
};
long[] labels = new long[] {1, 1, 0, 0, 1};
long[] query = 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.

Ejemplo 2
Entrada:
features = [
    [0],
    [0],
    [1]
]
labels = [0, 0, 1]
query = [2]

Salida esperada:
expected = 0
Entrada:
std::vector<std::vector<long long>> features = {
    {0},
    {0},
    {1}
};
std::vector<long long> labels = {0, 0, 1};
std::vector<long long> query = {2};

Salida esperada:
long long expected = 0;
Entrada:
long[][] features = new long[][] {
    new long[] {0},
    new long[] {0},
    new long[] {1}
};
long[] labels = new long[] {0, 0, 1};
long[] query = new long[] {2};

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.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Calcula el score de cada clase combinando su prior con las probabilidades de las features bajo la suposición de independencia.

Pista 2

Usa conteos de frecuencia con smoothing de Laplace y compara las clases en log space para evitar productos diminutos.

Pista 3

Incluye los valores de la query al determinar el número de valores distintos de cada feature, y rompe empates eligiendo la clase más pequeña.

Complejidad esperada

tiempo O(m × n), espacio extra O(m × n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.