Project-I

Cài đặt thuật toán Naive Bayes

Để sử dụng repository:

Bước 1: Set up môi trường trên máy theo hướng dẫn: https://docs.google.com/document/d/1e5V3rzkNQwQtopzfcJWVf_iBmCA8ZUQG/edit
Bước 2: Clone repo về máy
Bước 3: Tải dataset và cho vào folder data: https://drive.google.com/file/d/1Oprt8oOvR2gMqAhy5EslacziKVnIb3eP/view?usp=sharing

Cơ sở lý thuyết của Naive Bayes

1. Công thức xác suất có điều kiện Bayes:

$$\boldsymbol{P(C|X) = \frac{P(X|C).P(C)}{P(X)}}$$

• $\boldsymbol{C}$: lớp cần dự đoán (class)
• $\boldsymbol{X}$: vector thuộc tính (feature vector)
• $\boldsymbol{P(C)}$: xác suất tiên nghiệm của lớp (prior)
• $\boldsymbol{P(X|C)}$: xác suất quan sát đặc trưng khi biết lớp (likelihood)
• $\boldsymbol{P(X)}$: xác suất quan sát đặc trưng
• $\boldsymbol{P(C|X)}$: xác suất hậu nghiệm (posterior)

2. Giả định độc lập (Naive Assumption):

Giả định cho rằng các thuộc tính trong dữ liệu độc lập có điều kiện theo lớp C:

$$\boldsymbol{P(X|C) = \prod_{i = 1} ^ {n} {P(x_i|C)}}$$

Điều này giúp việc tính toán xác suất trở nên đơn giản hơn dù trong thực tế các thuộc tính thường có tương quan.

3. Công thức phân loại:

$$\boldsymbol{\hat{C} = \arg\max_C{P(C)\prod_{i = 1} ^ n {P(x_i|C)}}}$$

$\rightarrow$ Mô hình chọn lớp có xác suất hậu nghiệm lớn nhất.

Tuy nhiên việc tính toán với xác suất gần 0 sẽ có ảnh hưởng lớn đến kết quả phân loại nên chúng ta sẽ tính log của xác suất cho ổn định.

$$\boldsymbol{\hat{C} = \arg\max_C \left (\log{{P(C)} + \sum_{i = 1} ^ n \log{{P(x_i|C)}}} \right )}$$

$\rightarrow$ Mô hình chọn lớp có logarit xác suất hậu nghiệm lớn nhất.

4. Các biến thể chính:

Categorical Naive Bayes: Dùng cho dữ liệu kiểu định đạng (nhãn).

$$\boldsymbol{P(x_i|C) = \frac{count(v, i, c) + \alpha}{count(i, c) + \alpha.|V|}}$$

• $\boldsymbol{count(v, i, c)}$: số lượng mẫu có giá trị v của thuộc tính i với điều kiện lớp C
• $\boldsymbol{count(i, c)}$: số lượng mẫu của thuộc tính i với điều kiện lớp C
• $\boldsymbol{|V|}$: số lượng giá trị riêng biệt v của thuộc tính i
• $\boldsymbol{\alpha}$: hệ số để tránh trường hợp xác suất = 0

Gaussian Naive Bayes (Phân phối chuẩn): Dùng cho dữ liệu liên tục.

$$\boldsymbol{P(x_i|C) = \frac{1}{\sigma_{i, c}\sqrt{2\pi}} \exp \left ( {-\frac{1}{2} (\frac{x_i - \mu_{i, c}}{\sigma_{i, c}}) ^ 2} \right )}$$

• $\boldsymbol{x_i}$: giá trị của thuộc tính i
• $\boldsymbol{\mu_{i, c}}$: giá trị trung bình của thuộc tính i với điều kiện lớp C
• $\boldsymbol{\sigma_{i, c}}$: độ lệch chuẩn của thuộc tính i với điều kiện lớp C

Multinomial Naive Bayes: Dùng cho dữ liệu dạng đếm (thường được sử dụng trong phân loại văn bản và dữ liệu đếm là số các từ).

$$\boldsymbol{P(x_i|C) \propto (p_{ic}) ^ {x_i}}$$

$$\boldsymbol{p_{ic} = \frac{count(i, c) + \alpha}{count(c) + \alpha.|V|}}$$

• $\boldsymbol{x_i}$: số từ i trong văn bản
• $\boldsymbol{count(i,c)}$: đếm số từ i trong tất cả văn bản lớp C
• $\boldsymbol{count(c)}$: đếm số từ trong tất cả các văn bản lớp C
• $\boldsymbol{|V|}$: tổng tất cả số từ
• $\boldsymbol{\alpha}$: hệ số để tránh trường hợp xác suất = 0