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

Bộ phân loại Naive Bayes

Dự đoán lớp từ các đặc trưng phân loại bằng định lý Bayes và làm trơn Laplace.

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

  • Tính xác suất tiên nghiệm và khả năng
  • Làm trơn giá trị đặc trưng chưa gặp
  • Chọn lớp có xác suất cao nhất

Đề bài

Xem bản gốc (English)

Naive Bayes giả định các đặc trưng độc lập với nhau khi đã biết lớp, và chọn lớp có điểm cao nhất:

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

Các đặc trưng là danh mục được mã hóa thành số nguyên. Ước lượng xác suất từ dữ liệu huấn luyện:

  • P(c) = (số mẫu thuộc lớp c) / (số mẫu)
  • P(xⱼ = v | c) = (số mẫu thuộc lớp c có đặc trưng j bằng v + 1) / (số mẫu thuộc lớp c + Kⱼ)

với Kⱼ là số giá trị khác nhau của đặc trưng j trong các mẫu huấn luyện và query. Phần +1 (làm trơn Laplace) giúp một giá trị chưa từng thấy không làm điểm bằng 0.

Trả về lớp có điểm cao nhất; nếu điểm bằng nhau, trả về lớp nhỏ hơn. Nhân nhiều xác suất nhỏ có thể bị tràn dưới, nên hãy cộng logarit thay vì nhân.

Hãy cài đặt naive_bayes_predict(features, labels, query).

Đầu vào

features: Mỗi mẫu huấn luyện một hàng gồm n đặc trưng phân loại.

labels: Lớp của từng mẫu huấn luyện.

query: n đặc trưng của mẫu cần phân loại.

Đầu ra

Trả về lớp dự đoán.

Ràng buộc

1 ≤ số mẫu ≤ 1.000, 1 ≤ n ≤ 20

0 ≤ mỗi giá trị đặc trưng và nhãn ≤ 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

Lớp 1 có 3 mẫu và lớp 0 có 2 mẫu. Đặc trưng 1 có các giá trị {0, 1} (K = 2), đặc trưng 2 có {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. Lớp 1 thắng.

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

Giá trị 2 chưa từng xuất hiện, nên K = 3 (các giá trị 0, 1 và 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 và score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Nhờ làm trơn, không điểm nào bằng 0, và lớp 0 phổ biến hơn thắng.

Hướng tiếp cận

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

Gợi ý 1

Chấm điểm mỗi lớp bằng cách kết hợp prior của nó với likelihood của các feature theo giả định độc lập.

Gợi ý 2

Dùng đếm tần suất với Laplace smoothing, và so sánh các lớp trong log space để tránh tích quá nhỏ.

Gợi ý 3

Bao gồm cả giá trị query khi xác định số lượng giá trị khác nhau của từng feature, và phá hòa bằng cách chọn lớp nhỏ hơn.

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

thời gian O(m × n), bộ nhớ phụ O(m × n)

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.