Problème
Le classifieur naïf bayésien suppose que les variables sont indépendantes sachant la classe et choisit la classe au score le plus élevé :
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
Les variables sont des catégories codées par des entiers. Estimez les probabilités à partir des données d'entraînement :
- P(c) = (nombre d'exemples de la classe c) / (nombre d'exemples)
- P(xⱼ = v | c) = (nombre d'exemples de la classe c dont la variable j vaut v + 1) / (nombre d'exemples de la classe c + Kⱼ)
où Kⱼ est le nombre de valeurs distinctes de la variable j parmi les exemples d'entraînement et la requête. Le +1 (lissage de Laplace) évite qu'une valeur jamais vue donne un score nul.
Renvoyez la classe au score le plus élevé ; en cas d'égalité, la plus petite classe. Multiplier de nombreuses petites probabilités peut provoquer un dépassement par le bas : additionnez plutôt des logarithmes.
Implémentez naive_bayes_predict(features, labels, query).
Entrée
features : une ligne de n variables catégorielles par exemple d'entraînement.
labels : la classe de chaque exemple d'entraînement.
query : les n variables de l'exemple à classer.
Sortie
Renvoyez la classe prédite.
Contraintes
1 ≤ exemples ≤ 1 000, 1 ≤ n ≤ 20
0 ≤ chaque valeur de variable et étiquette ≤ 100
Exemples
Entrée :
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Sortie attendue :
expected = 1Entrée :
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}
};
Sortie attendue :
long long expected = 1;Entrée :
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}
};
Sortie attendue :
long expected = 1;Explication
La classe 1 a 3 exemples et la classe 0 en a 2. La variable 1 prend les valeurs {0, 1} (K = 2), 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. La classe 1 l'emporte.
Entrée :
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Sortie attendue :
expected = 0Entrée :
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
Sortie attendue :
long long expected = 0;Entrée :
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}
};
Sortie attendue :
long expected = 0;Explication
La valeur 2 n'apparaît jamais, donc K = 3 (valeurs 0, 1 et 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 et score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Grâce au lissage, aucun n'est nul, et la classe 0, plus fréquente, l'emporte.
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.