Đề bài
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ụ
Đầ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.
Đầ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.