Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Naive-Bayes-Klassifikator

Sage eine Klasse aus kategorialen Merkmalen mit dem Satz von Bayes und Laplace-Glättung voraus.

Das lernst du

  • Klassen-Priors und Likelihoods berechnen
  • Ungesehene Merkmalswerte glätten
  • Die wahrscheinlichste Klasse wählen

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

Beispiel 1
Eingabe:
features = [
    [0, 1],
    [0, 0],
    [1, 1],
    [1, 0],
    [0, 1]
]
labels = [1, 1, 0, 0, 1]
query = [0, 1]

Erwartete Ausgabe:
expected = 1
Eingabe:
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};

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
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};

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.

Beispiel 2
Eingabe:
features = [
    [0],
    [0],
    [1]
]
labels = [0, 0, 1]
query = [2]

Erwartete Ausgabe:
expected = 0
Eingabe:
std::vector<std::vector<long long>> features = {
    {0},
    {0},
    {1}
};
std::vector<long long> labels = {0, 0, 1};
std::vector<long long> query = {2};

Erwartete Ausgabe:
long long expected = 0;
Eingabe:
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};

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.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Bewerte jede Klasse, indem du ihren Prior mit den Likelihoods der Features unter der Unabhängigkeitsannahme kombinierst.

Hinweis 2

Nutze Häufigkeitszählungen mit Laplace-Smoothing und vergleiche die Klassen im Log-Raum, um winzige Produkte zu vermeiden.

Hinweis 3

Beziehe die Query-Werte ein, wenn du die Anzahl verschiedener Werte pro Feature bestimmst, und entscheide Gleichstände zugunsten der kleineren Klasse.

Erwartete Komplexität

Zeit O(m × n), zusätzlicher Speicher O(m × n)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.