Đề 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:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Kết quả mong đợi:
expected = 1Đầu vào:
std::vector<long long> query = {0, 1};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<std::vector<long long>> features = {
{0, 1},
{0, 0},
{1, 1},
{1, 0},
{0, 1}
};
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long[] query = new long[] {0, 1};
long[] labels = new long[] {1, 1, 0, 0, 1};
long[][] features = new long[][] {
new long[] {0, 1},
new long[] {0, 0},
new long[] {1, 1},
new long[] {1, 0},
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:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[] query = new long[] {2};
long[] labels = new long[] {0, 0, 1};
long[][] features = new long[][] {
new long[] {0},
new long[] {0},
new long[] {1}
};
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.
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.