TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN

BÁO CÁO CHUN ĐỀ HỌC PHẦN
NHẬP MƠN TRÍ TUỆ HỌC MÁY
ĐỀ TÀI:
PHÂN LOẠI THƯ RÁC SỬ DỤNG NAIVE BAYES

Giảng viên hướng dẫn : ĐÀO NAM ANH
Ngành

: CÔNG NGHỆ THÔNG TIN

Chuyên ngành

: QUẢN TRỊ AN NINH MẠNG

Khóa

: 2018-2023

Hà Nội, tháng 10 năm 2020


TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN

BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN
NHẬP MÔN HỌC MÁY
ĐỀ TÀI:
PHÂN LOẠI THƯ RÁC SỬ DỤNG NAIVE BAYES

Giảng viên hướng dẫn : ĐÀO NAM ANH
Ngành

: CÔNG NGHỆ THÔNG TIN

Chuyên ngành

: QUẢN TRỊ AN NINH MẠNG

Khóa

: 2018-2023

Hà Nội, tháng 10 năm 2020

PHIẾU CHẤM ĐIỂM
Sinh viên thực hiện:
2


PHIẾU CHẤM ĐIỂM
ST
T

Nội dung thực hiện

Điểm

Chữ

ký

1

2

3

.

Giảng viên chấm:

Họ và tên
Giảng viên chấm 1 :

Chữ ký

Ghi chú
3


Giảng viên chấm 2 :

MỤC LỤC
PHIẾU CHẤM ĐIỂM....................................................................................................................................3
DANH MỤC HÌNH ẢNH...............................................................................................................................7
LỜI MỞ ĐẦU..................................................................................................................................................8
4



CHƯƠNG 1: CƠ SỞ LÝ THUYẾT..............................................................................................................9
1.1.

GIỚI THIỆU VỀ CHUNG VỀ HỌC MÁY ( MACHINE LEARNING).................................9

1.1.1.

Trí tuệ nhân tạo (AI) là gì ?...................................................................................................9

1.1.2.

Học máy (Machine Learning) là gì ?....................................................................................9

1.1.3.

Học sâu (Deep Learning) là gì ?..........................................................................................10

1.1.4.

Phân nhóm các kỹ thuật trong Machine Learning...........................................................10

1.1.5.

Các bước thực hiện Machine Learning..............................................................................11

1.2.

Định lý Bayes (Bayes’ Theorem) là gì ?......................................................................................14

1.2.1.


Xác xuất có điều kiện............................................................................................................14

1.2.2.

Định lý Bayes.........................................................................................................................15

1.2.3.

Bài tốn Tuesday Child........................................................................................................16

1.3 Naive Bayes Classification (NBC).....................................................................................................18
1.3.1 Định nghĩa.....................................................................................................................................18
1.3.2 Các mô hình thuật tốn Naive Bayes.........................................................................................19
1.4.

Kết luận..........................................................................................................................................26

CHƯƠNG 2: PHÂN LOẠI THƯ RÁC BẰNG NBC................................................................................27
2.1 ĐẶT VẤN ĐỀ......................................................................................................................................27
2.2 BÀI TOÁN...........................................................................................................................................28
2.3 Chuẩn bị dữ liệu (dataset)..................................................................................................................28
2.4 Tiền xử lý dữ liệu (Preprocessing Data).............................................................................................29
2.5 Trích xuất đặc trưng (Feature Extraction).........................................................................................30
CHƯƠNG 3: XÂY DỰNG MƠ HÌNH, ĐÁNH GIÁ THỬ NGIỆM.......................................................36
3.1 Training and testing sets.....................................................................................................................36
3.2 Xử lý Bag of Words cho dataset........................................................................................................36
3.3 Thực thi Định lý Bayes.......................................................................................................................36
3.4 Đánh giá mơ hình................................................................................................................................37
3.5 Kết luận................................................................................................................................................38

3.6 Hướng phát triển.................................................................................................................................38
KẾT LUẬN....................................................................................................................................................39
TÀI LIỆU THAM KHẢO............................................................................................................................40

5


DANH MỤC HÌNH ẢNH
Hình 1.1: Cây mơ tả thuật tốn quay lui.........................................................15
Hình 1.2: Hàm gen.............................................................................................16
Hình 1.3: Hàm xuất...........................................................................................16
Hình 1.4: Kết quả chạy chương trình liệt kê dãy nhị phân có đo dài n........17
Hình 1.5: Liệt kê hốn vị với n=3.....................................................................18
Hình 1.6: Kết quả chạy chương trình liệt kê hốn vị tổ hợp.........................20
Hình 1.7: Kết quả chạy chương trình bài tốn 8 qn hậu...........................26
Hình 2.1: Vị trí xuất phát của qn Mã trên bàn cờ......................................28
Hình 2.2: Nước đi của quân Mã.......................................................................29
Hình 2.3: Mã ở rìa cũng giống như đồ trang trí.............................................30
Hình 2.4: Các nước đi có thể có của ngựa.......................................................32
Hình 3.1: Kết quả đạt được với C++...............................................................38
Hình 3.2: Giao diện khi chạy chương trình....................................................44
Hình 3.3: Nhập kích thước bàn cờ và tạo bàn cờ...........................................45
Hình 3.4: Chọn vị trí bắt đầu cho qn mã....................................................46
Hình 3.5: Qn mã có đầy đủ 8 nước có thể đi...............................................47
Hình 3.6: Qn mã ở cạnh bàn cờ có số nước đi ít hơn.................................48
Hình 3.7: Qn mã đang đi tuần......................................................................49
Hình 3.8: Kết quả cuối cùng.............................................................................50

6



LỜI MỞ ĐẦU
Trong cuộc sống với CNTT phát triển như ngày nay, giải quyết vấn đề thư rác
vẫn là một vấn đề nan giải. Với sự nổi lên nhanh chóng của trí tuệ nhân tạo hiện
nay, việc tiếp cận bằng học máy (machine learning) đã trở thành một thuật ngữ rất
quen thuộc với mọi người. Học máy đã đang và sẽ được ứng dụng trong vô số ứng
dụng hiện nay trong nhiều lĩnh vực như việc dự đoán rủi ro trong kinh tế, phân loại
tin nhắn trong các công cụ như Gmail hay Yahoo hay gần đây là ứng dụng chẩn
đốn bệnh trong y tế ,...
Chính vì vậy chúng em đã đi đến việc lựa chọn đề tài “PHÂN LOẠI THƯ
RÁC SỬ DỤNG NAIVE BAYES” cho bài tập lớn môn Nhập môn học máy.
Chúng em vô cùng biết ơn thầy Đào Nam Anh, người trực tiếp giảng dạy, hướng
dẫn nhiệt tình cho chúng em trong quá trình nghiên cứu và thực hiện đề tài.
Mặc dù đề tài đã hoàn thành, nhưng chắc chắn vẫn khơng thể tránh khỏi
những thiếu sót, vì vậy chúng em mong muốn nhận được các ý kiến đóng góp của
các thầy cơ để có thể hồn thiện hơn nữa.

Chúng em xin chân thành cảm ơn!

7


CHƯƠNG 1: CƠ SỞ LÝ THUYẾT
1.1.

GIỚI THIỆU VỀ CHUNG VỀ HỌC MÁY ( MACHINE LEARNING)

Biểu đồ trên cho ta thấy lịch sử phát triển cũng như mối quan hệ giữa AI, Machine
Learning và Deep Learning.
1.1.1. Trí tuệ nhân tạo (AI) là gì ?

Trí tuệ nhân tạo (AI) được hiểu là kỹ thuật giúp cho máy tính nói riêng và máy móc
nói chung có trí thơng minh và khả năng nhận biết cũng như tương tác với các hành
động cụ thể của con người. AI có lịch sử khá lâu đời, và được sử dụng rộng rãi
trong cuộc sống của chúng ta.
Gần gũi nhất có lẽ là các con bot ở chế độ Single Player (chế độ đấu với máy) trong
các trò chơi điện tử mà chúng ta hay chơi thuở bé. Các con bot này được thiết kế để
nhận biết các action của người chơi trong game và đưa ra các action đáp trả lại.
1.1.2. Học máy (Machine Learning) là gì ?
Học máy (Machine Learning - ML) là một mảng thuộc AI và được coi là một bước
nâng cấp của AI. Trước khi tìm hiểu ML là gì, ta nghĩ một chút xem thế nào là Học
(Learning)?
8


Học là một quá trình bao gồm: ghi nhớ (remembering), áp dụng (adapting), và
khái quát (generalising).
Lấy ví dụ như việc ta học Toán ở cấp 3, bắt đầu bằng việc ghi nhớ các cơng thức,
bài tập mẫu, sau đó tự giải lại các bài tập mẫu này, và cuối cùng là dùng kiến thức
đó để giải các bài tập mới.

Việc học của máy tính cũng tương tự, mục tiêu của ML là muốn cho máy tính
khơng chỉ ghi nhớ và thực hiện các lệnh có sẵn, mà cịn có thể khái qt vấn đề, từ
đó giải được các bài tốn mới khơng được lập trình sẵn.

Vậy máy tính học từ đâu? Học từ data.
Vì thế có thể nói ML là kỹ thuật thuộc ngành Khoa học dữ liệu (Data Science).

Quay trở lại ví dụ về con bot trong trị chơi điện tử ở trên. Nếu con bot được cài đặt
sử dụng ML, giả sử rằng ban đầu ta chiến thắng con bot này dễ dàng, nhưng sau
nhiều lần chơi, con bot học được cách chơi từ ta, từ đó nó phát kiến ra những cách

chơi mới để thắng ta, và ta khơng thể thắng nó được nữa. Chưa hết, con bot này cịn
có thể đem cách chơi học được để thắng ta để đấu với các người chơi mới. Đó là
một ví dụ của việc khái quát.
1.1.3. Học sâu (Deep Learning) là gì ?
Học sâu (Deep Learning - DL) là một kỹ thuật nằm trong Machine Learning, được
chú ý trong những năm trở lại đây vì hiệu quả và tính ứng dụng rộng rãi trên nhiều
lĩnh vực. Deep Learning là một tên gọi khác, một bước phát triển của Neural
Network, kỹ thuật mô phỏng hoạt động của bộ não con người.
Hầu hết các bài tốn khó hiện nay đều sử dụng DL. Tuy vậy DL cũng giống như bộ
não người, hoạt động như một black box khiến cho ta không thể dễ dàng quan sát
cơ chế hoạt động.
1.1.4. Phân nhóm các kỹ thuật trong Machine Learning

9


Có nhiều cách để phân nhóm các kỹ thuật trong Machine Learning. Các phân nhóm
dưới đây dựa trên phương pháp học.
 Học có giám sát (Supervised learning):
Là phương pháp học dựa trên tập dữ liệu có sẵn (gọi là tập training) và đáp án
kết quả của tập dữ liệu đó (thường người ta hay gọi là dữ liệu được dán nhãn).
Dựa dữ liệu training trên, máy tính khái qt hố thành thuật tốn, từ đó tìm kết
quả cho những đầu vào là các dữ liệu mới.
Trong học có giám sát phân chia tiếp thành 2 loại chính:
1. Phân loại (Classification): các nhãn dán của dữ liệu là một số hữu hạn.
Bài toán phân loại dữ liệu mới cho một trong các nhãn có sẵn. Ví dụ như
bài tốn phân loại thư rác, ta có 2 nhãn: thư rác hoặc khơng.
2. Hồi quy (Regression): các nhãn dán không được chia thành các nhóm
mà là một dữ liệu cụ thể. Bài tốn cần tìm giá trị cụ thể cho dữ liệu mới.
Ví dụ như bài toán định giá nhà ở dựa trên các thơng số ngơi nhà như

diện tích, địa điểm…
 Học không giám sát (Unsupervised learning):
Là phương pháp học mà tập dữ liệu training không được dán nhãn. Cách làm
chủ yếu là tìm ra các điểm tương tự của dữ liệu từ đó phân nhóm dữ liệu, hoặc
tìm ra thành phần chính nào đó của dữ liệu. Ví dụ như bài tốn phân nhóm thư
khiếu nại từ khách hàng.
 Học tăng cường (Reinforcement learning):
Là phương pháp học nằm giữa học có giám sát và khơng có giám sát. Kết quả
đầu ra của thuật toán được đánh giá khi nào là sai tuy nhiên lại khơng có câu trả
lời đáp án đúng. Máy tính cần thực hiện tìm kiếm tất cả các cách làm có thể, mỗi
cách làm sẽ được chấm điểm, từ đó tìm ra cách làm nào có điểm cao nhất. Ví dụ
như bài tốn máy tính học đánh cờ.

1.1.5. Các bước thực hiện Machine Learning
Thực hiện Machine Learning bao gồm các bước như sau:
 Thu thập và chuẩn bị dữ liệu:
Yếu tố ban đầu cần thiết để thực hiện Machine Learning là cần có dữ liệu. Dữ
10


liệu có thể được lấy từ nhiều nguồn khác nhau, có thể ít, có thể nhiều, có thể
sạch, có thể nhiều dữ liệu lỗi…
Sau khi thu thập, dữ liệu cần được làm sạch.
 Chọn Feature:
Với mỗi data có thể có rất nhiều feature (thành phần), nhưng không phải feature
nào cũng liên quan tới bài toán mà ta cần giải, việc lựa chọn feature (loại bỏ các
feature không cần thiết) giúp cho việc học của ta trở nên nhanh và hiệu quả hơn.
Tuy nhiên lựa chọn feature đòi hỏi sự thấu hiểu về dữ liệu và bài toán, chủ yếu
làm bằng tay và sức người.
Sau khi chọn được feature, nhiều khi ta quay lại bước 1, tiến hành loại bỏ các dữ

liệu không liên quan để thu nhỏ tập dữ liệu.
Việc thu nhỏ tập dữ liệu cũng khiến cho việc học của ta tốn ít thời gian hơn, tuy
nhiên dữ liệu ít quá cũng khiến việc học đạt độ chính xác không cao, cần cân đối
giữa các yếu tố này.
 Chuẩn hố dữ liệu: Nhiều khi data của từng feature có định dạng, kích thước
khác biệt lớn, ví dụ feature 1 có data trong khoảng [0, 1][0,1], feature 2 có data
trong khoảng [-1000, 1000][−1000,1000], feature 3 có data là hình ảnh… Để
tăng tốc độ và hiệu quả của việc học, ta cần chuẩn hoá dữ liệu, đưa data của tất
cả các feature về cùng một format (số hoá), và cùng khoảng biến thiên.
Một ví dụ về chuẩn hố dữ liệu có thể xem thêm ở đây.
 Chọn thuật toán:
Tuỳ vào dữ liệu, bài toán mà ta lựa chọn thuật toán ML tương ứng. Đơi khi lựa
chọn thuật tốn cũng cần dựa trên kinh nghiệm. Gợi ý cho việc lựa chọn thuật
toán là tham khảo bảng Cheat Sheet của Scikit-learn.

11


 Chọn parameter cho thuật toán:
Tuỳ mỗi thuật toán mà có nhiều các cách cài đặt khác nhau. Hơn thế nữa các
tham số tính tốn cũng quyết định khơng nhỏ tới kết quả tính tốn. Vì thế khi
sau khi chọn thuật toán thì việc chọn parameter phù hợp với dữ liệu cũng khá
quan trọng. Việc chọn Parameter chủ yếu dựa trên kinh nghiệm, nhiều khi có thể
sử dụng các thư viện support. Tuỳ từng thuật tốn có thể tham khảo ở đây.
 Huấn luyện và Đánh giá:
Sau khi chọn được thuật toán (một hoặc nhiều thuật toán) và parameter tương
ứng ta cho dữ liệu vào train. Tiến hành cross-validation để điều chỉnh model.
Sau khi train được model, ta đưa data test vào kiểm tra và đánh giá độ chính xác
của model vừa train được.
Phân chia dữ liệu

Thông thường với tập data cho trước ta thường chia làm 3 tập để sử dụng với mục đích
khác nhau:
 Tập huấn luyện (Training set): dùng để huấn luyện model.
12


 Tập kiểm chứng (Validation set): dùng để đánh giá, điều chỉnh model. Ví dụ
như ta dùng tập huấn luyện cho nhiều thuật toán khác nhau rồi dùng tập kiểm
chứng để chọn thuật toán phù hợp nhất. Hoặc tìm parameter phù hợp nhất cho
một thuật toán cụ thể.
 Tập kiểm tra (Test set): dùng để đánh giá model sau khi huấn luyện. Mô hình
đã được đánh giá bằng tập test phải là mô hình cuối cùng, không được thay đổi
nữa.
Việc phân chia tỉ lệ giữa 3 tập này được khuyên là 60% - 20% - 20%.
Nếu model cuối cùng thu được sau khi huấn luyện và kiểm chứng cần phải được đánh
giá bằng tập kiểm tra. Nếu kết quả không tốt, cần thực hiện huấn luyện lại từ đầu.

1.2.

Định lý Bayes (Bayes’ Theorem) là gì ?

Định lý Bayes (Bayes’ Theorem) là một định lý tốn học để tính xác suất xảy ra của
một sự kiện ngẫu nhiên A khi biết sự kiện liên quan B đã xảy ra.
Định lý này đặt theo tên nhà toán học Thomas Bayes, người Anh sống ở thế kỷ 18.
Đây là một trong những công cụ vơ cùng hữu ích, người bạn thân của các Data
Scientist, những người làm trong ngành khoa học dữ liệu.
1.2.1. Xác xuất có điều kiện
Ta có 2 sự kiện ngẫu nhiên A và B.
Nếu A và B là 2 sự kiện độc lập, ta có xác suất để xảy ra A và B đồng thời là:


P( A, B )=P( A )P( B )

(1)

trong đó:
P(A) là xác suất xảy ra A riêng biệt.
P(B) là xác suất xảy ra B riêng biệt.
Nếu A và B là 2 sự kiện liên quan đến nhau, và xác suất xảy ra sự kiện B lớn hơn 0,
ta có thể định nghĩa xác suất xảy ra A khi biết B xảy ra như sau:
Ta có thể viết lại thành:
13


P(A,B) = P(A|B)P(B)

| Khi A và B là 2 sự kiện độc lập ta có P(A|B) = P(A), ta thu được cơng thức như
(1).
Ví dụ
Để hiểu hơn, ta cùng lấy một ví dụ.
Đề bài:
Một gia đình có 2 đứa trẻ. Biết rằng có ít nhất 1 đứa trẻ là con gái. Hỏi xác suất 2
đứa trẻ đều là con gái là bao nhiêu?
Hiểu rằng:
 Xác suất để một đứa trẻ là trai hoặc gái là bằng nhau và bằng 1⁄2.
 Giới tính cả 2 đứa trẻ là ngẫu nhiên và khơng liên quan đến nhau.
Lời giải
Do gia đình có 2 đứa trẻ nên sẽ có thể xảy ra 4 khả năng: (trai, trai), (gái, gái), (gái,
trai), (trai, gái).

Do nếu xảy ra A thì đương nhiên sẽ xảy ra B nên ta có: P(A,B) = P(A) = 1⁄4

Lắp vào cơng thức trên ta có:

Bằng trực quan ta cũng có thể nhìn ra xác suất này. Khi biết một đứa trẻ là gái, giới
tính của 2 đứa trẻ sẽ có 3 khả năng: (trai, gái), (gái, trai), (gái, gái).

1.2.2. Định lý Bayes

14


Định lý Bayes dựa trên định nghĩa về xác suất có điều kiện ở trên, được phát biểu
dưới dạng cơng thức như sau:

Kí hiệu ¬A là khơng A (hay bù A). Ta có P(A) + P(¬A) = 1.
Từ đó: P(B) = P(B, A) +P (B, ¬A) = P(B∣A)P(A) + P(B∣¬A)P(¬A)
Định lý Bayes được viết dưới dạng biến thể như sau:

1.2.3. Bài toán Tuesday Child
Đây là một bài toán khá nổi tiếng trong xác suất thống kê, được giải theo nhiều
cách khác nhau. Ta hãy thử giải bài toán này bằng định lý Bayes xem sao.
Đề bài
Vẫn là gia đình có 2 đứa trẻ như ví dụ 1. Biết có ít nhất có một đứa trẻ là con gái và
sinh vào thứ 3. Hỏi xác suất 2 đứa trẻ đều là con gái là bao nhiêu?
Hiểu rằng:
 Xác suất để một đứa trẻ sinh vào một ngày nhất định trong tuần là 1⁄7.
 Giới tính của đứa trẻ và ngày sinh của nó là 2 sự kiện khơng liên quan đến
nhau.
Lời giải
Thoạt nhìn ta dễ tưởng giới tính và ngày sinh của đứa trẻ là 2 sự kiện không liên
quan đến nhau, nên ta sẽ thu được kết quả như ví dụ 1. Tưởng vậy mà không phải

vậy…
Ta ký hiệu các sự kiện như sau:

15


Để sử dụng định lý Bayes tính P(A|B) ta cần tính được P(B|A) và P(B).
P(B|A) được hiểu là xác suất ít nhất 1 đứa trẻ là con gái sinh ra vào thứ 3 nếu biết
trước 2 đứa trẻ là con gái.
Ta sẽ tính xác suất phần bù P(¬B∣A) là xác suất để khơng có đứa trẻ nào sinh ra
vào thứ 3.

Vậy ta có

P(B) là xác suất sự ít nhất 1 đứa trẻ là con gái sinh ra vào thứ 3.
Sự kiện này bao gồm 2 khả năng:
1. Cả 2 đứa trẻ đều là con gái (A)
2. Chỉ 1 đứa trẻ là con gái (A1)

Thay vào định lý Bayes, ta tính được
16


1.3 Naive Bayes Classification (NBC)
1.3.1 Định nghĩa
Naive Bayes Classification (NBC) là một thuật tốn phân loại dựa trên tính tốn
xác suất áp dụng định lý Bayes mà ta đã tìm hiểu ở bài trước (xem bài trước tại
đây).
Thuật toán này thuộc nhóm Supervised Learning (Học có giám sát).
Theo định lý Bayes, ta có cơng thức tính xác suất ngẫu nhiên của sự kiện y khi biết

x như sau:
(1)
Giả sử ta phân chia 1 sự kiện x thành n thành phần khác nhau x1, x2, …, xn.
Naïve Bayes theo đúng như tên gọi dựa vào một giả thiết ngây thơ rằng x1, x2, …,
xn là các thành phần độc lập với nhau. Từ đó ta có thể tính được:

Do đó ta có:

|

∝ là phép tỉ lệ thuận.

Trên thực tế thì ít khi tìm được dữ liệu mà các thành phần là hoàn toàn độc lập với
nhau. Tuy nhiên giả thiết này giúp cách tính tốn trở nên đơn giản, training data nhanh,
đem lại hiệu quả bất ngờ với các lớp bài toán nhất định.

Cách xác định các thành phần (class) của dữ liệu dựa trên giả thiết này có tên là Naive
Bayes Classifier.
1.3.2 Các mơ hình thuật tốn Naive Bayes
Một trong các bài toán nổi tiếng hiệu quả khi sử dụng NBC là bài tốn phân loại
text, trong đó phổ biến nhất là bài toán phân loại thư rác.

17


Trong bài toán này, mỗi văn bản được thể hiện thành dạng bag of words, hiểu nôm
na là thể hiện xem có bao nhiêu từ xuất hiện và tần suất xuất hiện trong văn bản,
nhưng bỏ qua thứ tự các từ.
Các từ và tần suất xuất hiện được coi là các feature vector, và theo giả thiết Naive
Bayes coi là các thành phần độc lập mà không ảnh hưởng đến nhau.

Có 2 mơ hình thuật tốn Naive Bayes thường sử dụng là: mơ hình Bernoulli và mơ
hình Multinomial.
Mơ hình Bernoulli
a. Công thức
Ở mô hình này, các feature vector là các giá trị nhị phân 0, 1. Trong đó 1 thể hiện từ có
xuất hiện trong văn bản, 0 thể hiện từ đó khơng xuất hiện trong văn bản.
Xác xuất P(xi|y) được tính bằng

với P(i|y) là tỉ lệ số lần từ xi xuất hiện trong tồn bộ tập training data có nhãn y.
Nhiều tài liệu biểu diễn công thức dưới dạng khác là:

Cơng thức (4) và (5) về giá trị tốn học là giống nhau.
b. Ví dụ
Đề bài
Ta có training data gồm 10 email, đánh 2 nhãn: Spam (S) và Not Spam (N).
Ta định nghĩa bảng từ vựng gồm 8 từ như sau:
V=[w1, w2, w3, w4, w5]
Cần phân loại email E11 thuộc loại nào

18


Lời giải
Để dễ phân biệt, ra xếp tập training data riêng thành 2 bảng như sau:
class = Spam (S)

class = Not Spam (N)
19



Ta có:

Số lần xuất hiện của từng từ tương ứng với 2 nhãn S và N như sau:
ns(w1) = 4 ns(w2) = 4
ns(w3) = 3 ns(w4) = 3
ns(w5) = 2
nn(w1) = 1 nn(w2) = 2
nn(w1) = 2 nn(w2) = 3
nn(w2) = 4

20


Với test data E11={w1=1,w4=1,w5=1}, ta tính xác suất tương ứng của E11 với mỗi
loại như sau:

Ta tính được xác suất tương ứng như sau:

Do đó ta phân loại E11 là Spam (S).
Mơ hình Multinomial
a. Cơng thức
Ở mơ hình này, các feature vector là các giá trị số tự nhiên mà giá trị thể hiện số lần từ
đó xuất hiện trong văn bản.
Ta tính xác suất từ xuất hiện trong văn bản P(xi|y) như sau:

Trong đó:
Ni là tổng số lần từ xi xuất hiện trong văn bản.
Nc là tổng số lần từ của tất cả các từ x1, … xn xuất hiện trong văn bản.
b. Laplace Smoothing
Cơng thức trên có hạn chế là khi từ x_ixi không xuất hiện lần nào trong văn bản, ta sẽ

có Ni = 0. Điều này làm cho P(xi∣y) = 0.
Vế phải của công thức (3) bằng 0 nếu bất kì một giá trị nào bằng 0 (mặc dù có thể các
giá trị khác rất lớn).
Để khắc phục vấn đề này, người ta sử dụng kỹ thuật gọi là Laplace Smoothing bằng
cách cộng thêm vào cả tử và mẫu để giá trị luôn khác 0.
21


Trong đó:
thường là số dương, bằng 1.
d được cộng vào mẫu để đảm bảo
c. Ví dụ
Đề bài:
Vẫn bài tốn phân loại mail Spam (S) và Not Spam (N).
Ta có bộ training data gồm E1, E2, E3. Cần phân loại E4.
Bảng từ vựng: [w1, w2, w3, w4, w5, w6, w7]
Số lần xuất hiện của từng từ trong từng email tương ứng như bảng dưới.

Lời giải
Ta có:

Sử dụng Laplace Smoothing với α=1 ta tính được xác suất xuất hiện của từng từ trong
văn bản như sau:
class = Spam (S)
22


class = Spam (N)

Vậy ta tính được:


Ta tính được xác suất tương ứng như sau:

23


Do đó ta phân loại E4 là Not Spam (N).

1.4.

Kết luận
 Naive Bayes Classifiers (NBC) là phương pháp cổ điển nhưng vẫn rất
hữu dụng với các bài toán nhất định như phân loại văn bản, email…
 NBC với công thức tính tốn đơn giản nên dễ cài đặt (hiện nay nếu dùng
thư viện sklearn thì chỉ cần gọi vài dòng lệnh như mình làm bên trên),
thời gian training và test nhanh, phù hợp với bài toán data lớn.
 Nếu giả sử về tính độc lập được thoả mãn (dựa vào bản chất của dữ liệu),
NBC được cho là cho kết quả tốt hơn so với SVM và logistic regression
khi có ít dữ liệu training.
 NBC có thể hoạt động với các feature vector mà một phần là liên tục (sử
dụng Gaussian Naive Bayes), phần còn lại ở dạng rời rạc (sử dụng
Multinomial hoặc Bernoulli).
 Cần chú ý sử dụng Smoothing để tránh lỗi xác suất tổng được bằng 0 khi
xác suất của một feature thành phần bằng 0.
 Độ chính xác của Naive Bayes nếu so với các thuật toán khác thì không
được cao.
 Trong thế giới thực, hầu như bất khả thi khi các feature của dữ liệu test là
độc lập với nhau.

24



CHƯƠNG 2: PHÂN LOẠI THƯ RÁC BẰNG NBC
2.1 ĐẶT VẤN ĐỀ
Thư rác bắt đầu được gọi là "spam" sau chương trình truyền hình có tên
"Monty Python’s Flying Circus". Trong show truyền hình này, một nhóm cướp biển
Vikings đã vào ăn trong một nhà hàng chuyên phục vụ đồ hộp (spam), rồi hát toáng
lên một ca khúc lặp đi lặp lại 2 chữ "quảng cáo". Ý nghĩa ban đầu của thư rác rất rõ
ràng: Một thứ lặp đi lặp lại và gây ra sự bực tức, khó chịu cho những người xung
quanh. Đó chỉ là trong một phạm vi hẹp cịn trong mơi trường internet khi khơng
cịn khoảng cách về địa lý nữa thì sẽ có rất nhiều người phải chịu sự bực tức, cảnh
nhàm chán gây ức chế tâm lý và cực kỳ mất thời gian vào nó.
Phần lớn các thư không mời mà đến, các thư chào hàng quảng cáo bị cho là
thư rác theo nhận xét của số đông người dùng thư điện tử. Đây là vấn đề nan giải
mà các hệ thống, hòm mail, các nhà quản trị mạng đang phải đối mặt trong thời
điểm hiện nay khi mà xã hội thông tin ngày càng phát triển với tốc độ chóng mặt.
Đe lọc và phát hiện thư rác, cần có giải pháp lâu dài như các biện pháp kĩ thuật,
quy ước xã hội và có thể dùng đến pháp luật. Nhưng khi các giải pháp này được thi
hành thì chỉ trong một khoảng thời gian ngắn chúng đã bị phá vỡ bởi các spammer,
nguyên nhân chính là họ luôn nghĩ ra những cái bẫy đánh lừa người dùng hay lách
luật mà các tổ chức chống thư rác quy ước.
Như vậy giải pháp ngăn chặn thư rác nào hiệu quả và dùng được lâu dài?
Một phương pháp tốt nhất đó là để chính người dùng thư điện tơ ngăn chặn thư rác,
bởi họ hiểu vấn đề một cách tường minh nhất. Chúng ta sẽ dùng cảm nhận về thư
rác của mỗi người để huấn luyện cho các bộ lọc thư rác của chính họ. Mỗi bộ lọc sẽ
xử lý thư rác tùy theo phong cách của từng người dùng thư điện tử. Và mô hình
thống kê Bayes được áp dụng để thực thi ý tưởng này. Từ những đặc điểm trên, ta
thấy rằng việc xây dựng được một bộ lọc thư rác thơng minh có thể loại bỏ một
cách chính xác hiện nay là một nhiệm vụ cịn nhiều thách thức.


25