Problem
Naive Bayes nimmt an, dass die Merkmale bei gegebener Klasse unabhängig sind, und wählt die Klasse mit dem höchsten Score:
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
Die Merkmale sind als ganze Zahlen kodierte Kategorien. Schätze die Wahrscheinlichkeiten aus den Trainingsdaten:
- P(c) = (Anzahl der Beispiele der Klasse c) / (Anzahl der Beispiele)
- P(xⱼ = v | c) = (Anzahl der Beispiele der Klasse c, deren Merkmal j gleich v ist, + 1) / (Anzahl der Beispiele der Klasse c + Kⱼ)
wobei Kⱼ die Anzahl der verschiedenen Werte von Merkmal j in den Trainingsbeispielen und der Anfrage ist. Die +1 (Laplace-Glättung) verhindert, dass ein unbekannter Wert einen Score von 0 erzeugt.
Gib die Klasse mit dem höchsten Score zurück; bei Gleichstand die kleinere Klasse. Das Multiplizieren vieler kleiner Wahrscheinlichkeiten kann unterlaufen, also addiere stattdessen Logarithmen.
Implementiere naive_bayes_predict(features, labels, query).
Eingabe
features: Eine Zeile mit n kategorialen Merkmalen pro Trainingsbeispiel.
labels: Die Klasse jedes Trainingsbeispiels.
query: Die n Merkmale des zu klassifizierenden Beispiels.
Ausgabe
Gib die vorhergesagte Klasse zurück.
Einschränkungen
1 ≤ Beispiele ≤ 1.000, 1 ≤ n ≤ 20
0 ≤ jeder Merkmalswert und jedes Label ≤ 100
Beispiele
Eingabe:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Erwartete Ausgabe:
expected = 1Eingabe:
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}
};
Erwartete Ausgabe:
long long expected = 1;Eingabe:
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}
};
Erwartete Ausgabe:
long expected = 1;Erläuterung
Klasse 1 hat 3 Beispiele und Klasse 0 hat 2. Merkmal 1 hat die Werte {0, 1} (K = 2), Merkmal 2 hat {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. Klasse 1 gewinnt.
Eingabe:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Erwartete Ausgabe:
expected = 0Eingabe:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
Erwartete Ausgabe:
long long expected = 0;Eingabe:
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}
};
Erwartete Ausgabe:
long expected = 0;Erläuterung
Der Wert 2 kommt nie vor, also K = 3 (Werte 0, 1 und 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 und score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Dank der Glättung ist keiner 0, und die häufigere Klasse 0 gewinnt.
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.