Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Naive Bayes Classifier

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

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

0 ≤ each feature value and label ≤ 100

Ví dụ

Ví dụ 1
Đầu vào:
features = [
    [0, 1],
    [0, 0],
    [1, 1],
    [1, 0],
    [0, 1]
]
labels = [1, 1, 0, 0, 1]
query = [0, 1]

Kết quả mong đợi:
expected = 1
Đầu vào:
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};

Kết quả mong đợi:
long long expected = 1;
Đầu vào:
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};

Kết quả mong đợi:
long expected = 1;

Giải thích

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.

Ví dụ 2
Đầu vào:
features = [
    [0],
    [0],
    [1]
]
labels = [0, 0, 1]
query = [2]

Kết quả mong đợi:
expected = 0
Đầu vào:
std::vector<std::vector<long long>> features = {
    {0},
    {0},
    {1}
};
std::vector<long long> labels = {0, 0, 1};
std::vector<long long> query = {2};

Kết quả mong đợi:
long long expected = 0;
Đầu vào:
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};

Kết quả mong đợi:
long expected = 0;

Giải thích

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.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.