Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Naive Bayes Classifier

Predict a class from categorical features with Bayes' theorem and Laplace smoothing.

Das lernst du

  • Compute class priors and likelihoods
  • Smooth unseen feature values
  • Pick the most probable class

Problem

Übersetzung anzeigen

Naive Bayes assumes features are independent given the class and picks the class with the highest score:

score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)

Features are categories encoded as integers. Estimate the probabilities from the training data:

  • P(c) = (number of samples of class c) / (number of samples)
  • P(xⱼ = v | c) = (count of samples of class c whose feature j equals v + 1) / (number of samples of class c + Kⱼ)

where Kⱼ is the number of distinct values of feature j among the training samples and the query. The +1 (Laplace smoothing) keeps an unseen value from making a score 0.

Return the class with the highest score; if scores tie, return the smaller class. Multiplying many small probabilities can underflow, so add logarithms instead.

Implement naive_bayes_predict(features, labels, query).

Input

features: One row of n categorical features per training sample.

labels: The class of each training sample.

query: The n features of the sample to classify.

Output

Return the predicted class.

Einschränkungen

1 ≤ samples ≤ 1,000, 1 ≤ n ≤ 20

0 ≤ each feature value and 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

Class 1 has 3 samples and class 0 has 2. Feature 1 has values {0, 1} (K = 2), feature 2 has {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. Class 1 wins.

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

Value 2 never appears, so K = 3 (values 0, 1 and 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 and score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Thanks to smoothing neither is 0, and the more common class 0 wins.

So gehst du vor

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

Hinweis 1

Score each class by combining its prior with feature likelihoods under the independence assumption.

Hinweis 2

Use frequency counts with Laplace smoothing, and compare classes in log space to avoid tiny products.

Hinweis 3

Include the query values when determining each feature’s distinct value count, and break ties by choosing the smaller class.

Erwartete Komplexität

O(m × n) time, O(m × n) extra space

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.