Problema
Naive Bayes assume che le variabili siano indipendenti data la classe e sceglie la classe con il punteggio più alto:
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
Le variabili sono categorie codificate come interi. Stima le probabilità dai dati di addestramento:
- P(c) = (numero di esempi della classe c) / (numero di esempi)
- P(xⱼ = v | c) = (numero di esempi della classe c con variabile j uguale a v + 1) / (numero di esempi della classe c + Kⱼ)
dove Kⱼ è il numero di valori distinti della variabile j tra gli esempi di addestramento e la query. Il +1 (smoothing di Laplace) evita che un valore mai visto azzeri un punteggio.
Restituisci la classe con il punteggio più alto; in caso di parità, la classe minore. Moltiplicare tante piccole probabilità può causare underflow, quindi somma i logaritmi invece.
Implementa naive_bayes_predict(features, labels, query).
Input
features: Una riga di n variabili categoriali per esempio di addestramento.
labels: La classe di ogni esempio di addestramento.
query: Le n variabili dell'esempio da classificare.
Output
Restituisci la classe prevista.
Vincoli
1 ≤ esempi ≤ 1.000, 1 ≤ n ≤ 20
0 ≤ ogni valore delle variabili ed etichetta ≤ 100
Esempi
Input:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Output atteso:
expected = 1Input:
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}
};
Output atteso:
long long expected = 1;Input:
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}
};
Output atteso:
long expected = 1;Spiegazione
La classe 1 ha 3 esempi e la classe 0 ne ha 2. La variabile 1 ha valori {0, 1} (K = 2), la variabile 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. Vince la classe 1.
Input:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Output atteso:
expected = 0Input:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
Output atteso:
long long expected = 0;Input:
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}
};
Output atteso:
long expected = 0;Spiegazione
Il valore 2 non compare mai, quindi K = 3 (valori 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. Grazie allo smoothing nessuno è 0, e vince la classe 0, più comune.
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.