Bài tập | NEU OJ

Hãy cài đặt bộ phân lớp Multinomial Naive Bayes mini để phân loại tin nhắn theo mô hình bag-of-words. Từ điển có $V$ từ (đánh số 0..V−1), có $C$ lớp và $n$ tin nhắn huấn luyện; mỗi tin nhắn được biểu diễn bằng vectơ đếm từ $(w_1, \dots, w_V)$ .

Huấn luyện:

Prior: $P(c) = n_c / n$ với $n_c$ là số tin nhắn lớp $c$ .
Likelihood với làm trơn Laplace: $P(w \mid c) = \dfrac{\text{count}(w, c) + 1}{\text{total}(c) + V}$ , trong đó $\text{count}(w,c)$ là tổng số lần từ $w$ xuất hiện trong các tin nhắn lớp $c$ , $\text{total}(c)$ là tổng tất cả các từ của lớp $c$ .

Phân lớp tin nhắn mới có vectơ đếm $q$ : tính điểm log cho từng lớp

$\text{score}(c) = \ln P(c) + \sum_{w=0}^{V-1} q_w \ln P(w \mid c)$

và chọn lớp có điểm lớn nhất (nếu bằng nhau, chọn lớp chỉ số nhỏ nhất). Mỗi lớp đảm bảo có ít nhất một tin nhắn huấn luyện.

Định dạng đầu vào:
Dòng đầu: ba số nguyên $V$ $C$ $n$ . $n$ dòng tiếp theo: số nguyên $c_i$ (nhãn lớp) rồi $V$ số nguyên là vectơ đếm từ của tin nhắn $i$ . Dòng cuối: $V$ số nguyên là vectơ đếm từ của tin nhắn cần phân lớp.
Ràng buộc đầu vào:
1 ≤ V ≤ 100; 2 ≤ C ≤ 10; 1 ≤ n ≤ 1000; 0 ≤ số đếm ≤ 100.
Định dạng đầu ra:
Một dòng duy nhất: chỉ số lớp dự đoán (số nguyên).

solution

Đề bài: [Data Science] Phân loại tin nhắn bằng bag-of-words