1

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH

TRẦN THỊ XUÂN HƯƠNG

LUẬN VĂN THẠC SĨ
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã ngành: 60.48.02.01

ĐỀ TÀI
NGHIÊN CỨU KỸ THUẬT CHỌN THUỘC TÍNH CHO CÁC
THUẬT TOÁN PHÂN LỚP

Người hướng dẫn: TS. Phan Anh Phong
Vinh, tháng 07/2018


2

MỤC LỤC
MỞ ĐẦU .....................................................................................................................5
DANH MỤC BẢNG ...................................................................................................7
DANH MỤC HÌNH ....................................................................................................9
CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN PHÂN LỚP ......................................10
1.1. Khai phá dữ liệu .............................................................................................10
1.2. Phân lớp dữ liệu .............................................................................................12
1.2.1. Bài tốn phân lớp ....................................................................................12
1.2.2. Q trình phân lớp dữ liệu ......................................................................13
1.3 Một số thuật toán phân lớp dữ liệu .................................................................14

1.3.1. Thuật toán phân lớp Navie Bayes...........................................................15
1.3.2. Thuật toán phân lớp J48 .........................................................................18
1.3.3. Thuật toán phân lớp KNN ......................................................................20
1.4. Độ đo hiệu năng cho các thuật toán phân lớp ................................................23
1.4.1. Ma trận nhầm lẫn ....................................................................................23
1.4.2. Đợ chính xác phân lớp ............................................................................24
1.4.3. Độ đo F ...................................................................................................24
1.4.4. Độ nhạy và độ đặc tả ..............................................................................25
1.4.5. Đường cong ROC ...................................................................................25
1.4.6. Giá trị AUC ............................................................................................27
1.4.7. Hệ số Gini ...............................................................................................27
1.5. Các thách thức cho bài toán phân lớp ............................................................28
1.6. Kết luận chương 1 ..........................................................................................29
CHƯƠNG 2: KỸ THUẬT CHỌN THUỘC TÍNH CHO CÁC THUẬT TỐN
PHÂN LỚP ...............................................................................................................30
2.1. Các tiếp cận chọn tḥc tính cho bài tốn phân lớp ......................................30
2.1.1. Mơ hình Filter (mơ hình đợc lập) ...........................................................31
2.1.2. Mơ hình Wrapper (mơ hình kết hợp) .....................................................32
2.1.3. So sánh mơ hình Filter và mơ hình Wrapper ..........................................34
2.2. Chọn tḥc tính theo mơ hình đợc lập ...........................................................34
2.2.1. Mợt sớ đợ đo thơng tin............................................................................34
2.2.2. Các bước lựa chọn tḥc tính .................................................................37
2.2.3. Kỹ thuật sử dụng độ lợi thông tin ...........................................................39


3

2.2.4. Kỹ thuật sử dụng đo sự tương quan........................................................40
2.2.5. Thuật toán Relief-F.................................................................................41
2.3. Kết luận chương 2 ..........................................................................................42

CHƯƠNG 3: THỬ NGHIỆM ...................................................................................43
3.1. Tổng quan về WEKA ....................................................................................43
3.1.1.

Giới thiệu về WEKA .........................................................................43

3.1.2.

Dữ liệu WEKA ..................................................................................45

3.2. Các bộ dữ liệu thử nghiệm .............................................................................46
3.2.1. Bộ dữ liệu Labor .....................................................................................46
3.2.2. Bộ dữ liệu Bank Marketing ....................................................................47
3.3. Phương pháp thử nghiệm ...............................................................................48
3.4. Kết quả thử nghiệm với bợ dữ liệu Labor......................................................49
3.4.1. Các tḥc tính được chọn theo đợ lợi thơng tin ........................................49
3.4.2. Các tḥc tính tính được chọn theo Relief-F .........................................51
3.4.3. Các tḥc tính được chọn dựa trên sự tương quan .................................52
3.4.4. Các tḥc tính được chọn dựa theo Wrapper .........................................53
3.4.5. Kết quả phân lớp với tḥt tốn Nạve Bayes ........................................54
3.4.6. Kết quả phân lớp với thuật toán thuật toán cây quyết định J48 .............58
3.4.7. Kết quả phân lớp sử dụng thuật toán K-NN ...........................................61
3.4.8. Đánh giá kết quả thử nghiệm..................................................................63
3.5. Kết quả thử nghiệm với bợ dữ liệu Bank Marketing ....................................66
3.5.1. Các tḥc tính được chọn .......................................................................66
3.5.2. Đánh giá hiệu suất phân lớp ...................................................................69
3.5.3. Đánh giá kết quả thử nghiệm..................................................................74
KẾT LUẬN ...............................................................................................................77
TÀI LIỆU THAM KHẢO .........................................................................................78



4

LỜI CÁM ƠN
Trước tiên, em xin chân thành cám ơn thầy giáo TS. Phan Anh Phong đã tận
tình chỉ bảo, giúp đỡ, hướng dẫn em trong thời gian qua.
Em cũng xin bày tỏ lịng biết ơn tới các thầy cơ giáo trong Viện Kỹ tḥt và
Cơng nghệ nói riêng và trường Đại học Vinh nói chung đã cung cấp cho em những
kiến thức quý báu trong quá trình học tập, nghiên cứu tại trường.
Em cũng xin cám ơn gia đình, bạn bè những người thân yêu đã cổ vũ, động viên,
quan tâm, giúp đỡ em vượt qua mọi khó khăn trong suốt thời gian học tập cũng như
làm luận văn.
Do kiến thức cũng như thời gian nghiên cứu có hạn nên ḷn văn sẽ khơng tránh
khỏi nhiều sai sót nhất định. Em rất mong nhận được sự góp ý quý báu của các thầy
cô và bạn bè.
Vinh, tháng 7 năm 2018
Học viên

Trầ Thị Xuân Hương


5

MỞ ĐẦU
Khoa học kỹ thuật ngày càng phát triển, đi cùng với nó là sự phát triển khơng
ngừng của dữ liệu về kích thước và chủng loại. Nhiệm vụ khai phá dữ liệu nói
chung cũng như nghiên cứu các thuật tốn phân lớp nói riêng trở nên ngày càng bức
thiết và đóng vai trị trung tâm trong việc giải quyết các bài toán cụ thể. Vấn đề xử
lý dữ liệu lớn ngày càng trở thành vấn đề cấp thiết và đóng vai trị chủ đạo trong
việc giải quyết các bài toán thực tế. Thực tế cho thấy, chúng ta chỉ có thể tìm ra mợt

sớ tḥt tốn phù hợp với một số loại dữ liệu cụ thể và bị giới hạn về kích thước dữ
liệu. Kết quả của tḥt tốn phụ thuộc rất nhiều vào việc xử lý dữ liệu thơ. Trong
khai phá dữ liệu, phương pháp trích chọn đóng vai trị quan trọng trong tiền xử lý sớ
liệu, đặc biệt đối với ngành tin sinh học, xử lý dữ liệu âm thanh, hình ảnh, dữ liệu
mạng xã hợi... Đặc điểm chung của những lĩnh vực này là kích thước rất lớn (hàng
trăm, hàng trăm nghìn tḥc tính) nhưng chỉ mợt sớ ít tḥc tính có giá trị dùng để
phân tích. Phần lớn các tḥt tốn phân lớp đã phát triển chỉ có thể giải quyết được
với mợt lượng sớ liệu giới hạn cũng như với một độ phức tạp dữ liệu biết trước.
Trong khi đó lượng dữ liệu mà chúng ta thu thập được ngày càng trở nên
phong phú và đa dạng nhờ sự phát triển mạnh mẽ của khoa học kỹ thuật. Mặc dù rất
nhiều kỹ thuật khai phá dữ liệu dựa trên một số nền tảng lý thuyết khác nhau đã
được phát triển và ứng dụng từ rất lâu, nhưng thực tế cho thấy kết quả phụ tḥc rất
nhiều vào đặc tính dữ liệu cũng như khả năng xử lý dữ liệu thơ của từng nhóm
nghiên cứu. Một điều hiển nhiên là với mỗi phương pháp chỉ có thể đáp ứng và xử
lý tớt trên mợt vài dữ liệu và ứng dụng cụ thể nào đó. Trong khai phá dữ liệu thì
phương pháp trích chọn đóng mợt vai trị quan trọng trong tiền xử lý sớ liệu. Hướng
tiếp cận này làm tăng hiệu năng thu nhận tri thức trong các ngành như tin sinh, xử
lý dữ liệu web, xử lý tiếng nói, hình ảnh với đặc tính là có rất nhiều tḥc tích (vài
trăm cho đến vài trăm ngàn tḥc tính) nhưng thường chỉ có mợt sớ lượng tương
đối nhỏ các mẫu dùng để huấn luyện (thường là vài trăm). Phương pháp trích chọn
sẽ giúp giảm kích cỡ của không gian dữ liệu, loại bỏ những thuộc tính khơng liên
quan và những tḥc tính nhiễu nhưng khơng ảnh hưởng đến chất lượng của bài


6

toán phân lớp.
Những năm trở lại đây, do nhu cầu giảm chiều sớ liệu ngày càng cao nên có
rất nhiều các nghiên cứu về lựa chọn tḥc tính, lĩnh vực này phát triển mạnh mẽ cả
về chiều rộng lẫn chiều sâu.

Bớ cục của ḷn văn: Ngồi các phần Mở đầu, Mục lục, Danh mụa hình,
Danh mục bảng, Kết luận, Tài liệu tham khảo, thì luận văn được chia làm 3 chương:
Chương I: TỔNG QUAN VỀ BÀI TOÁN PHÂN LỚP
Phần này giới thiệu tổng qua về khai phá dữ liệu, phân lớp dữ liệu, các thuật toán
phân lớp dữ liệu và thách thức của bài toán phân lớp
Chương II: LỰA CHỌN THUỘC TÍNH CHO CÁC THUẬT TỐN PHÂN LỚP
Phần này giới thiệu các cách tiếp cận bài toán phân lớp, lựa chọn tḥc tính theo
các mơ hình. Đặc biệt trình bày được chi tiết về độ đo thông tin, các bước lựa chọn
tḥc tính, các kỹ tḥt sử dụng đợ đo...
Chương III: THỬ NGHIỆM
Chương này trình bày các bước thử nghiệm, tổng hợp các kết quả và đánh giá
hiệu năng của các mơ hình phân lớp.


7

DANH MỤC BẢNG
Bảng 1.1. Cở sở dữ liệu về Thời tiết .........................................................................17
Bảng 1.2. Cở sở dữ liệu về Phim ..............................................................................22
Bảng 1.3. Ma trận nhầm lẫn ......................................................................................24
Bảng 1.4. Ví dụ ma trận nhầm lẫn lẫn cho Mơ hình phân lớp nhị phân ...................28
Bảng 2.1. Cơ sở dữ liệu về khả năng Mua máy tính .................................................35
Bảng 3.1. Tập tḥc tính của bợ dữ liệu Labor .........................................................46
Bảng 3.2. Tập tḥc tính của bợ dữ liệu Bank Marketing .......................................47
Bảng 3.3. So sánh hiệu suất phân lớp với thuật toán Naiver Bayes trên tập dữ liệu
Labor .........................................................................................................................56
Bảng 3.4. Ma trận nhầm lẫn cho thuật toán Naïve Bayes trên tập dữ liệu Labor sử
dụng phương pháp wrapper.......................................................................................57
Bảng 3.5. Các hiệu suất cho tḥt tốn Nạve Bayes trên tập dữ liệu Labor sử dụng
phương pháp wrapper ................................................................................................57

Bảng 3.6. Bảng so sánh hiệu suất cho thuật toán phân lớp J48 trên tập dữ liệu Labor
...................................................................................................................................60
Bảng 3.7. Ma trận nhầm lẫn cho thuật toán J48 trên tập dữ liệu Labor sử dụng
phương pháp wrapper ................................................................................................61
Bảng 3.8. Các hiệu suất cho thuật toán J48 trên tập dữ liệu Labor sử dụng phương
pháp wrapper .............................................................................................................61
Bảng 3.9. Bảng so sánh hiệu suất cho thuật toán phân lớp K-NN trên tập dữ liệu
Labor .........................................................................................................................61
Bảng 3.10. Ma trận lẫn lợn cho K-NN hàng xóm gần nhất sử dụng k = 1cho tập dữ
liệu Labor ..................................................................................................................63
Bảng 3.11. Hiệu suất phân lớp KNN bằng cách sử dụng k = 1cho tập dữ liệu Labor
...................................................................................................................................63
Bảng 3.12. Độ chính xác với các tham sớ tới ưu nhất trong các lần chạy trên tập dữ
liệu Labor ..................................................................................................................64


8

Bảng 3.13. Kết quả AUC với các tham số tối ưu nhất trong các lần chạy trên tập dữ
liệu Labor ..................................................................................................................64
Bảng 3.14. Kết quả F-Means với các tham số tối ưu nhất trong các lần chạy trên tập
dữ liệu Labor .............................................................................................................65
Bảng 3.15. Các tḥc tính được chọn lựa bằng Wrapper trên tập dữ liệu banhk
Marketing ..................................................................................................................68
Bảng 3.16. Kết quả phân lớp với Naïve Bayes cho tập dữ liệu Bank Marketing .....69
Bảng 3.17. Ma trận nhầm lẫn cho tḥt tốn Nạve Bayes trên tập dữ liệu Bank sử
dụng phương pháp Wrapper ......................................................................................70
Bảng 3.18. Hiệu suất cho tḥt tốn Nạve Bayes trên tập dữ liệu Bank sử dụng
phương pháp Wrapper ...............................................................................................70
Bảng 3.19. Kết quả phân lớp với J48 cho tập dữ liệu Bank Marketing ....................70

Bảng 3.20. Ma trận nhầm lẫn cho thuật toán J48 trên tập dữ liệu Bank Marketing sử
dụng phương pháp CFS.............................................................................................71
Bảng 3.21. Các biện pháp hiệu suất cho thuật toán J48 trên tập dữ liệu Bank
Marketing sử dụng phương pháp CFS ......................................................................72
Bảng 3.22. Kết quả hiệu suất phân lớp cho thuật toán phân lớp K-NN trên tập dữ
liệu Bank Marketing ..................................................................................................72
Bảng 3.23. Ma trận nhầm lẫn cho thuật toán K-NN với k=10 trên tập dữ liệu Bank
Maketing sử dụng phương pháp lựa chọn tḥc tính CFS .......................................73
Bảng 3.24. Hiệu suất cho thuật toán K-NN với k=10 trên tập dữ liệu Bank Maketing
sử dụng phương pháp lựa chọn tḥc tính CFS ........................................................73
Bảng 3.25 . Đợ chính xác với các tham số tối ưu nhất trong các lần chạy trên tập dữ
liệu Bank Marketing ..................................................................................................74
Bảng 3.26. Kết quả AUC với các tham số tối ưu nhất trong các lần chạy trên tập dữ
liệu Bank Marketing ..................................................................................................75
Bảng 3.27. Kết quả F-Means với các tham số tối ưu nhất trong các lần chạy trên tập
dữ liệu Bank Marketing.............................................................................................75


9

DANH MỤC HÌNH
Hình 1.1. Tập dữ liệu phân thành 2 lớp: bi vàng và bi xanh .....................................12
Hình 1.2. Tập dữ liệu phân thành 3 cụm ...................................................................12
Hình 1.3. Liệu bi mới thêm vào sẽ thuộc lớp bi vàng hay lớp bi xanh .....................13
Hình 1.4. K-Nearest Neighbor với k = 3 ...................................................................20
Hình 1.5. Receiver Operating Characteristic (ROC) các điểm cong ........................26
Hình 1.6. Đường cong Receiver Operating Characteristic (ROC) ...........................27
Hình 1.7. Vùng dưới đường cong(AUC) Receiver Operating Characteristic ...........27
Hình 2.1. Mơ hình lọc Filter......................................................................................31
Hình 2.2. Mơ hình lọc Wrapper ................................................................................32

Hình 2.3 . Quy trình lựa chọn tḥc tính ..................................................................38
Hình 3.1. Giao diện của Weka ..................................................................................44
Hình 3.2. Weka Explorer ..........................................................................................44
Hình 3.3. Quy trình thử nghiệm ................................................................................49
Hình 3.4. Hiệu suất của phân lớp Nạve Bayes trên các bợ tính năng của tập dữ liệu
Labor về đợ chính xác Accuracy, AUC, F-Measure, TPR và TNR..........................57
Hình 3.5 . Hiệu suất của phân lớp J48 trên các bộ tính năng của tập dữ liệu Labor về
đợ chính xác Accuracy, AUC, F-Measure, TPR và TNR .........................................61
Hình3.6. Hiệu suất của phân lớp K-NN trên các bợ tính năng của tập dữ liệu Labor
...................................................................................................................................63
Hình 3.7. Hiệu suất phân lớp Nạve Bayes trên các bợ tính năng của tập dữ liệu
Bank Marketing về đợ Accuracy, AUC, F-Measure, TPR và TNR .........................70
Hình 3.8. Hiệu suất của phân loại J48 trên các bợ tính năng của tập dữ liệu Bank
Marketing về đợ chính xác Accuracy, AUC, F-Meas, TPR và TNR........................71
Hình 3.9 . Hiệu suất phân lớp K-NN trên các bợ tính năng của tập dữ liệu Bank
Marketing về đợ chính xác Accuracy, AUC, F-Measure, TPR và TNR ..................73


10

CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN PHÂN LỚP
Ngày nay, với sự phát triển mạnh mẽ của các ngành khoa học kĩ thuật, sự tích
lũy dữ liệu trong thực tế không ngừng tăng lên, lượng thông tin cần thiết phải lưu
trữ trong các thiết bị điện tử ngày càng nhiều. Bên cạnh đó, việc tin học hóa mọi
mặt các hoạt động sản xuất, kinh doanh và các lĩnh vực khác của đời sống đã tạo ra
một lượng dữ liệu cần lưu trữ khổng lồ. Sớ lượng và kích thước bản ghi ngày càng
lớn gây khó khăn cho việc lưu trữ và xử lí nên vấn đề xử lí dữ liệu ngày càng bức
thiết. Vì vậy, việc khai phá dữ liệu và trong đó có phân lớp dữ liệu đang là mới quan
tâm hàng đầu trong vấn đề xử lí dữ liệu hiện nay.
1.1. Khai phá dữ liệu

Khai phá dữ liệu là một khái niệm bắt đầu xuất hiện từ những ći những năm 80
của thế kỷ XX. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện các thông tin có
giá trị tiềm ẩn trong tập các dữ liệu lớn.Về bản chất, khai phá dữ liệu liên quan đến
việc phân tích các dữ liệu và sử dụng các kỹ tḥt để tìm ra các mẫu hình có tính
chính quy trong tập dữ liệu. Năm 1989, các nhà nghiên cứu Fayyad, PiatestskyShapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu
(Kownledge Discovery in Database – KDD) để chỉ tồn bợ q trình phát hiện các
tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu là mợt bước thực
hiện trong tồn bợ q trình, bằng cách sử dụng các giải thuật đặc biệt để chiết xuất
ra các mẫu hay các mơ hình từ dữ liệu thu thập. Khai phá dữ liệu chủ yếu tập trung
vào 3 nhiệm vụ chính sau:
Giảm chiều dữ liệu: Giảm chiều dữ liệu là việc làm giảm chiều của khơng gian tìm
kiếm dữ liệu, giảm chi phí thu thập và lưu trữ dữ liệu, nâng cao hiệu quả của việc khai
phá dữ liệu và làm đơn giản hóa các kết quả khai phá dữ liệu. Trong nhiệm vụ làm
giảm chiều dữ liệu chúng ta cần xem xét hai khái niệm sau:
+ Trích chọn thuộc tính (Feature Extraction): Trích chọn tḥc tính là việc tìm ra
mợt tập tḥc tính mới từ tập tḥc tính ban đầu nhằm nâng cao hiệu suất tính tốn
và đợ chính xác phân lớp. Các kỹ tḥt trích chọn tḥc tính thường liên quan đến
các phép biến đổi phi tuyến (non-linear). Linear discriminant analysis (LDA) và


11

principal components analysis (PCA) là hai kỹ thuật phổ biến dùng trong trích chọn
tḥc tính.
+ Chọn lựa thuộc tính (Feature Selection): Chọn lựa tḥc tính là việc chọn ra mợt
tập tḥc tính con từ tập tḥc tính ban đầu sao cho các tập tḥc tính con này thể
thể hiện tớt nhất chức năng của một hệ thống quy nạp, chẳng hạn như mợt hệ thớng
phân lớp. Việc tìm kiếm mợt tập con tḥc tính tới ưu thường là rất khó và rất nhiều
các vấn đề của chọn lựa tḥc tính là tḥc về lớp các bài tốn NP-hard. Tuy nhiên,
chọn lựa tḥc tính lại được sử dụng rợng rãi trong giảm chiều dữ liệu vì các kết

quả dựa trên các tḥc tính được chọn lựa từ tập tḥc tính ban đầu thường dễ dàng
lý giải hơn so với một tập các tḥc tính được biến đổi từ tập tḥc tính ban đầu.
Phân cụm và phân lớp: Phân lớp và phân cụm là hai nhiệm vụ có mới quan hệ
tương đới gần nhau trong khai phá dữ liệu. Một lớp là mợt tập các đới tượng có
cùng mợt sớ đặc điểm hoặc mới quan hệ nào đó, tất cả các đới tượng trong lớp này
được phân vào trong cùng một lớp tên nhằm mục đích là để phân biệt với các lớp
khác. Một cụm là một tập các đối tượng tương tự nhau về mặt vị trí. Các cụm
thường được được tạo ra nhằm mục đích để sau đó tiến hành phân lớp các đối
tượng. Một tập dữ liệu với các lớp tên, phân tích dữ liệu nhằm mục đích xây dựng
mợt bợ phân lớp, bợ phân lớp này đóng vai trị như mợt “người dự đoán” mợt đới
tượng mới xuất hiện sẽ tḥc về lớp nào. Mơ hình phân lớp được xây dựng dựa trên
các dữ liệu sẵn có. Tiếp theo tiến hành dự đoán, phân lớp các đối tượng dựa vào mơ
hình máy học được xây dựng ở bước trên. Ví dụ, trong hoạt đợng của ngân hàng các
thơng tin cá nhân cũng và các hành vi tiêu dùng của khách hàng được thu thập
nhằm xây dựng một mô hình phân lớp cho những khách hàng mới vào các lớp: có
rủi ro tín dụng thấp, rủi ro tín dụng trung bình và rủi ro tín dụng cao. Trong trường
hợp khác, chỉ có mợt sớ thơng tin cơ bản về những khách hàng tiềm năng như: tuổi,
trình đợ chun mơn và thu nhập. Chúng ta có thể sử dụng mợt sớ kỹ tḥt phân
cụm nhằm nhóm các đới tượng này vào các cụm theo mợt sớ tiêu chí về đợ tương
đồng nào đó, sau đó tiến hành dán nhãn cho các cụm được phân: mức độ rủi ro thấp,
mức độ rủi trung bình và mức đợ rủi ro cao dựa vào các tiêu chí kinh doanh. Nhìn


12

chung, phân cụm thường được triển khai để xử lý với các dữ liệu khơng có lớp
nhãn. Mợt sớ phương pháp phân lớp sẽ tiến hành phân cụm các đối tượng vào các
nhóm nhỏ trước khi tiến hành phân lớp, chẳng hạn như trong mạng neural RBF
(radial basis function).


Hình 1.1. Tập dữ liệu phân thành 2 lớp: bi
vàng và bi xanh

Hình 1.2. Tập dữ liệu phân thành 3 cụm

Trích chọn luật: Trích chọn ḷt tìm kiếm và đưa ra dữ liệu bằng cách tất cả các
dữ liệu được đưa ra dựa trên các suy diễn/các quyết định mà các suy diễn/quyết
định này được xây dựng từ các tri thức thu thập được từ dữ liệu đó. Đới với người
sử dụng các kết quả của khai phá dữ liệu họ chỉ mong ḿn có mợt cách giải thích
đơn giản là tại sao có các kết quả phân lớp đó, tḥc tính nào ảnh hưởng đến kết
quả khai phá dữ liệu…Tuy nhiên, bằng các tham sớ phân lớp rất khó để có thể diễn
giải các tri thức đó theo cách mà người sử dụng có thể dễ dàng hiểu được. Do đó,
trích chọn ra các luật IF-THEN để đưa ra các thông tin có giá trị là mợt cách diễn
giải đơn giản và dễ hiểu nhất đối với người sử dụng.
1.2. Phân lớp dữ liệu
1.2.1. Bài toán phân lớp
Bài toán phân lớp (classification) là q trình phân lớp mợt đới tượng dữ liệu vào
một hay nhiều lớp đã cho trước nhờ một mơ hình phân lớp. Mơ hình này được xây
dựng dựa trên một tập dữ liệu đã được xây dựng trước đó có gắn nhãn (cịn gọi là
tập huấn luyện). Q trình phân lớp là quá trình gán nhãn cho đới tượng dữ liệu.


13

y

x

?


Hình 1.3. Liệu bi mới thêm vào sẽ tḥc lớp bi vàng hay lớp bi xanh
Như vậy, nhiệm vụ của bài tốn phân lớp là cần tìm mợt mơ hình phần lớp để
khi có dữ liệu mới thì có thể xác định được dữ liệu đó tḥc vào phân lớp nào. Có
nhiều bài tốn phân lớp dữ liệu như phân lớp nhị phân (binary), phân lớp đa lớp
(multiclass), phân lớp đa trị.
Bài toán phân lớp nhị phân là bài toán gán nhãn dữ liệu cho đối tượng vào trong
hai lớp khác nhau dựa vào việc dữ liệu đó có hay khơng các đặc trưng (feature) của
bợ phân lớp
Bài tốn phân lớp đa lớp là quá trình phân lớp dữ liệu với số lượng lớp lớn hơn
hai. Như vậy tùy thuộc vào từng bộ dữ liệu mà chúng ta cần phải xem xét và phân
lớp chúng vào những lớp khác nhau chứ không phải chỉ là phân lớp vào hai lớp như
bài tốn phân lớp nhị phân. Về thực chất thì bài toán phân lớp nhị phân là bài toán
đặc biệt của phân lớp đa lớp. Ứng dụng của bài toán này được sử dụng rộng rãi
trong thực tế với các bài toán như bài toán nhận dạng khuôn mặt, bài tốn nhận diện
giọng nói, bài tốn phân lớp văn bản, bài tốn phát hiện các email spam... Và đới
với các bài toán phân lớp dữ liệu chúng ta sử dụng các tḥt tốn học có giám sát
(supervised learning) để xây dựng mơ hình cho bài tốn này.
1.2.2. Q trình phân lớp dữ liệu
Để xây dựng được mơ hình phân lớp và đánh giá được mơ hình chúng ta phải
thực hiện quá trình sau:
Bước 1: Chuẩn bị tập dữ liệu huấn luyện và lựa chọn đặc trưng
Công đoạn này được xem là cơng đoạn quan trọng trong các bài tốn về Machine


14

Learning vì đây là đầu vào cho việc học để tìm ra mơ hình của bài tốn. Chúng ta
phải biết chọn ra những tḥc tính đặc trưng tớt của dữ liệu, lược bỏ những tḥc
tính khơng tớt, gây nhiễu hoặc thừa của bộ dữ liệu. Ước chừng số chiều của dữ liệu
bao nhiêu là tớt hay nói cách khác là chọn bao nhiêu đặc trưng. Nếu số chiều quá

lớn làm ảnh hưởng đến việc tính tốn thì phải tìm cách làm giảm số chiều của dữ
liệu nhưng vẫn giữ được đợ chính xác của dữ liệu khi phân lớp.
Ở bước này chúng ta cũng chuẩn bị bộ dữ liệu để test trên mơ hình. Thơng
thường sẽ sử dụng cross-validation (kiểm tra chéo) để chia tập dữ liệu thành hai
phần là tập dữ liệu đào tạo (training datasets) và phần còn lại phục vụ cho mục đích
thử nghiệm trên mơ hình (testing dataset). Có hai cách thường sử dụng trong crossvalidation là splitting và k-fold.
Bước 2: Xây dựng mơ hình phân lớp
Mục đích của mơ hình huấn luyện là tìm ra hàm f(x) và thơng qua hàm f tìm được
để gán nhãn cho tập dữ liệu : f(x)=y .
Trong đó: x là các đặc trưng hay đầu vào của dữ liệu, y là nhãn của lớp hay đầu
ra của dữ liệu.
Thông thường để xây dựng mơ hình phân lớp cho các bài toán phân lớp này ta cần
sử dụng các thuật tốn học có giám sát như : KNN(k-nearest neighbors), Decision
Tree (cây quyết định), Naïve Bayers, Neural Netwwork (mạng nơron)...
Bước 3: Kiểm tra dữ liệu với mơ hình : Sau khi tìm ra được mơ hình phân lớp ở
bước thứ 2 thì ở bước này chúng ta sẽ đưa vào mơ hình các dữ liệu mới (test) để
kiểm tra trên mơ hình phân lớp.
Bước 4: Đánh giá mơ hình phân lớp và chọn ra mơ hình tớt nhất
Ở bước này chúng ta sẽ đánh giá mơ hình bằng cách đánh giá mức độ lỗi của dữ
liệu thử nghiệm(testing) và dữ liệu huấn luyện(training) thơng qua mơ hình tìm
được. Nếu khơng đạt kết quả mong muốn chúng ta phải thay đổi các tham sớ của
các tḥt tốn học để tìm ta các mơ hình khác tớt hơn và kiểm tra đánh giá lại mơ
hình phân lớp. Ći cùng chọn ra mơ hình phân lớp tớt nhất cho bài tốn.
1.3 Mợt sớ tḥt toán phân lớp dữ liệu


15

Có nhiều tḥt tốn phân lớp dữ liệu đã được xây dựng và đề xuất bởi các
chuyên gia và được tiếp cận theo nhiều cách khác nhau. Phần tiếp theo sẽ trình bày

mợt sớ tḥt tốn phân lớp nổi tiếng và thường được lựa chọn để giải quyết các bài
toán phân lớp dữ liệu.
1.3.1. Thuật toán phân lớp Navie Bayes
Naive Bayes Classification (NBC) là mợt tḥt tốn dựa trên định lý Bayes về
lý thuyết xác suất để đưa ra các phán đoán cũng như phân loại dữ liệu dựa trên các
dữ liệu được quan sát và thống kê. NBC là một trong những thuật toán được ứng
dụng rất nhiều trong các lĩnh vực Machine Learning dùng để đưa các dự đoán chính
xác nhất dự trên mợt tập dữ liệu đã được thu thập, vì nó khá dễ hiểu và đợ chính xác
cao. Nó tḥc vào nhóm Supervised Machine Learning Algorithms (tḥt tốn học
có hướng dẫn), tức là máy học từ các ví dụ từ các mẫu dữ liệu đã có.
Ví dụ như ta có thể ứng dụng vào việc thiết kế mợt ứng dụng nghe nhạc có thể
phán đoán được sở thích của nghe nhạc của người dùng dựa trên các hành vi như
nhấn nút “thích” bài hát, “nghe đi nghe” lại nhiều lần các bài hát, “bỏ qua” các bài
hát khơng thích …. Dựa trên tập dữ liệu đó ta có thể áp dụng NBC để tính tốn ra
các phong cách nhạc mà người dùng thích nhất, từ đó chúng ta có thể đưa ra các
“gợi ý” nghe nhạc gần đúng nhất cho người dùng từ việc học hỏi từ những thói
quen đó.
Bợ phân lớp Bayes có thể dự báo các xác suất là thành viên của lớp, chẳng hạn
xác suất mẫu cho trước thuộc về một lớp xác định.
Bợ phân lớp Nạve Bayes có thể so sánh đuợc về công năng với Bộ phân lớp cây
quyết định và mạng nơron. Chúng giả định các tḥc tính là đợc lập nhau (độc lập
điều kiện lớp).
Định lý Bayes
- X là mẫu dữ liệu chưa biết nhãn lớp, H là giả thuyết sao cho X thuộc về lớp C.
- Ấn định xác suất hậu nghiệm (posterior probability) P(H|X) sao cho H đúng khi
cho trước quan sát X (H conditioned on X).
- Giả sử thế giới các mẫu dữ liệu gồm trái cây, được mơ tả bằng màu sắc và hình


16


dáng.
+ Giả sử X là màu đỏ và hình trịn
+ H là giả thuyết mà X là quả táo.
+ Thì P(H|X) phản ánh độ tin cậy X là quả táo khi biết trước X có màu đỏ và hình
trịn
Cơng thức của định luật Bayes được phát biểu như sau:
P(X|H) là xác suất hậu nghiệm của X có điều kiện trên. Định lý Bayes:
P(H| X)=
Khi có n giả thuyết:

𝑃(𝑋|𝐻)𝑃(𝐻)
𝑃(𝑋)

P(Hi| X)=

𝑃(𝑋|𝐻𝑖 )𝑃(𝐻𝑖 )
∑𝑛
𝑗−1 𝑃(𝑋)

(1.1)
(1.2)

Phân lớp Naïve Bayyesian (NBC):
Mỗi mẫu dữ liệu được biểu diễn bằng X= (x1, x2,…, xn) với các thuộc tính A1,
A2,…, An. Các lớp C1, C2, …, Cm. Cho trước mẫu chưa biết X. NBC gán X vào Ci khi
và chỉ khi P(Ci|X) > P(Cj|X) với 1 ≤ j ≤ m, j ≠ i. Do vậy, chúng ta cực đại P(Ci|X).
Lớp Ci sao cho P(Ci|X) là cực đại được gọi là giả thuyết hậu nghiệm cực đại
(maximum posterior hypothesis). Theo định lý Bayers:
P(Ci| X)=


𝑃(𝑋|𝐶𝑖 )𝑃(𝐶𝑖 )
𝑃(𝑋)

(1.3)

Do P(X) là hằng cho tất cả các lớp, chỉ cần cực đại P(X|Ci) P(Ci). Nếu chưa biết
P(Ci) cần giả định P(C1)=P(C2)=…= P(Cm) và chúng ta sẽ cực đại P(X|Ci). Ngược
lại, ta cực đại P(X|Ci) P(Ci). Nếu m là lớn, sẽ rất tốn kém khi tính P(X|Ci) P(Ci).
NBC giả định đợc lập điều kiện lớp

(1.4)
Có thể phỏng tính P(x1|Ci), …, P(xn|Ci) từ các mẫu huấn luyện. Nếu Ak được
phân lớp thì P(xk|Ci) = Sik/Si với Sik là sớ mẫu huấn luyện của Ci có trị xk cho Ak và
Si là số các mẫu thuộc về lớp Ci
Nếu Ak là liên tục thì nó được giả định có phân bớ Gaussian


17

(1.5)
Để phân lớp mẫu chưa biết X, ta tính P(X|Ci), P(Ci) cho từng Ci. Sau đó mẫu X
được gán vào Ci :

if P(Ci|X) > P(Cj|X) for 1 ≤ j ≤ m, j ≠ i

Nói cách khác, NBC gán X vào lớp Ci sao cho P(X|Ci) P(Ci) là cực đại
Ví dụ: Bảng 1.1 Cơ sở dữ liệu về Thời tiết
Bảng 1.1. Cở sở dữ liệu về Thời tiết
Day

Outlook
Temp

Humidity

Wind

Play?

High

Weak

No

D1

Sunny

Hot

D2

Sunny

Hot

High

Strong


No

D3

Overcast

Hot

High

Weak

Yes

D4

Rain

Mild

High

Weak

Yes

D5

Rain


Cool

Normal

Weak

Yes

D6

Rain

Cool

Normal

Medium

No

D7

Overcast

Cool

Normal

D8


Sunny

Mild

High

Weak

No

D9

Sunny

Cool

Normal

Weak

Yes

D10

Rain

Mild

Normal


Weak

Yes

D11

Sunny

Mild

Normal

Strong

Yes

D12

Overcast

Mild

High

Strong

Yes

D13


Overcast

Hot

Normal

Weak

Yes

D14

Rain

Mild

High

Strong

No

Strong

Yes

Dự báo nhãn lớp với phân lớp Bayesian :
Với X = (O = Sunny, Temp = Hot, Humidity = Normal, Wind = Weak)
Yes


No

P(Play = yes) = 9/14

P(Play = no) = 5/14

P(O = Sunny| Play = Yes) = 2/9

P(O = Sunny| Play = No) = 3/5


18

P(T = Hot|Play = Yes) = 2/9

P(T = Hot | Play = No) = 2/5

P(H = Normal | Play = Yes) = 6/9

P(H = Normal | Play = No) = 1/5

P(W = Weak | Play = Yes) = 6/9

P(W = Weak | Play = No) = 2/5

P(Yes | X) =
P(No | X) =

9∗2∗2∗6∗6

14∗9∗9∗9∗9
5∗3∗2∗1∗2
14∗5∗5∗5∗5

=
=

8
567
2
875

Naive Bayes là một phương pháp rất hiệu quả trong một số trường hợp. Nếu tập dữ
liệu huấn luyện nghèo nàn và các tham số dự đoán (như khơng gian đặc trưng) có
chất lượng kém thì sẽ dẫn đến kết quả tồi. Tuy nhiên, nó được đánh giá là mợt tḥt
tốn phân lớp tuyến tính thích hợp trong phân lớp văn bản nhiều chủ đề với một số
ưu điểm: cài đặt đơn giản, tốc độ nhanh, dễ dàng cập nhật dữ liệu huấn luyện mới
và có tính đợc lập cao với tập huấn luyện, có thể sử dụng kết hợp nhiều tập huấn
luyện khác nhau. Thông thường, người ta cịn đặt thêm mợt ngưỡng tới ưu để cho
kết quả phân lớp khả quan.
1.3.2. Thuật toán phân lớp J48
Cây quyết định (Decision Tree) là mợt cây phân cấp có cấu trúc được dùng để phân
lớp các đối tượng dựa vào các ḷt (series of rules). Các tḥc tính của đớt tượng
(ngoại trừ tḥc tính phân lớp) có thể có các kiểu dữ liệu khác nhau trong khi đó
các tḥc tính phân lớp phải có kiểu dữ kiệu Binary hoặc Ordinal. Tóm lại, cho dữ
liệu về các đới tượng gồm các tḥc tính cùng với lớp (classes) của nó, cây quyết
định sẽ sinh ra các luật để dự đoán lớp của các đối tượng chưa biết (unseen data).
Cây quyết định là cấu trúc cây sao cho: Mỗi nút trong ứng với mợt phép kiểm tra
trên mợt tḥc tính. Mỗi nhánh biểu diễn kết quả phép kiểm tra. Các nút lá biểu diễn
các lớp hay các phân bố lớp. Nút cao nhất trong cây là nút gốc.

Cây quyết định là một trong những phương pháp được sử dụng phổ biến nhất (Ngai,
Xiu, & Chau, 2009). Đây là phương pháp học xấp xỉ các hàm mục tiêu có giá trị
rời rạc. Mợt ưu điểm của phương pháp cây quyết định là có thể chuyển dễ dàng
sang dạng cơ sở tri thức là các ḷt Nếu - Thì (If - Then). Giớng như tất cả các thuật


19

toán phân lớp, các mục tiêu của phương pháp này là phân loại mợt biến đích dựa
trên các giá trị tḥc tính hiện có. Trong trường hợp cây quyết định, cây bắt đầu ở
nút gốc, nút đơn biểu diễn tất cả các mẫu. Nếu các mẫu thuộc về cùng một lớp, nút
trở thành nút lá và được gán nhãn bằng lớp đó. Ngược lại, dùng đợ đo tḥc tính để
chọn tḥc tính sẽ phân tách tớt nhất các mẫu vào các lớp. Quyết định chia tách
được thực hiện bởi các biện pháp đo lường (Quinlan,1986). Hai biện pháp được sử
dụng phổ biến trong xây dựng cây quyết định là Information Gain và Chỉ số Gini
Index (Chen, Wang, & Zhang, 2011). Mợt nhánh được tạo cho từng giá trị của
tḥc tính được chọn và các mẫu được phân hoạch theo. Các nút này sẽ tiếp tục
phân chia cho đến khi nút cuối cùng hoặc nút lá được phát triển. Nút lá xác định
phân loại cuối cùng của biến được kiểm tra. Vì mỗi nút kiểm tra mợt tḥc tính cụ
thể trong bợ dữ liệu, mơ hình rất dễ hiểu. Các phép thử tại mỗi nút có thể được thực
hiện trên các kiểu dữ liệu rời rạc cũng như liên tục. Theo mặc định cây sẽ cố gắng
để bao gồm tất cả các kết quả có thể trong cấu trúc của nó. Những bất lợi của
phương pháp này là cây sẽ over-fit dữ liệu vào giải pháp của nó. Sự phức tạp của
cây sẽ làm cho chuyên gia về miền khó có thể theo dõi quá trình ra quyết định trong
cây. Dùng đệ quy cùng mợt quá trình để tạo cây quyết định.
Tiến trình kết thúc chỉ khi bất kỳ điều kiện nào sau đây là đúng:
- Tất cả các mẫu cho một nút cho trước đều thuộc về cùng một lớp.
- Khơng cịn tḥc tính nào mà mẫu có thể dựa vào để phân hoạch xa hơn.
- Khơng cịn mẫu nào cho nhánh test_attribute = ai .
Ví dụ với cơ sở dữ liệu trên Bảng 1.1

Từ bảng dữ liệu trên, ta xây dựng được cây quyết định như sau:


20

1.3.3. Thuật toán phân lớp KNN
Thuật toán k - láng giềng (k-nearest Neightbor (kNN) ) được cho là thuật toán
đơn giản nhất trong máy học. Mơ hình được xây dựng chỉ bao gồm việc lưu trữ dữ
liệu tập huấn (training dataset). Để dự đoán được một điểm dữ liệu mới, tḥt tốn
sẽ tìm ra những láng giềng trong dữ liệu tập huấn (training dataset), đó là láng
giềng (nearest neightbors).
Tḥt tốn gán một lớp cho đối tượng dựa trên lớp lân cận xung quanh bằng cách
sử dụng một hàm khoảng cách xác định trước.

Hình 1.4. K-Nearest Neighbor với k = 3
Giá trị k là sớ lượng hàng xóm quyết định lớp của phần tử được đề cập. Một
đối tượng được phân lớp dựa vào k láng giềng của nó, k là số nguyên dương được


21

xác định trước khi thực hiện thuật toán. Nếu giá trị của k là 1, thì đới tượng được
phân loại trong cùng mợt lớp với hàng xóm gần nhất của nó. Kết quả của tḥt tốn
K-NN phụ tḥc vào giá trị được sử dụng trong tính tốn của nó. Người ta thường
dùng khoảng cách Euclidean, Cosine,… để tính khoảng cách giữa các đối tượng.
Việc phân lớp dùng KNN gồm các bước:
- Xác định sớ láng giềng gần nhất k.
- Tính khoảng cách giữa đối tượng cần phân lớp với tất cả các đối tượng trong tập
dữ liệu huấn luyện.
- Sắp xếp khoảng cách theo thứ tự tăng dần và xác định k láng giềng gần nhất với

đối tượng cần phân lớp.
- Lấy tất cả các lớp của k láng giềng gần nhất đã xác định.
- Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho đối tượng.
Lợi thế của việc sử dụng K-NN trên các tḥt tốn phân lớp là nó là trực quan và
dễ dàng để thiết lập. Tuy nhiên, có mợt sớ nhược điểm khi sử dụng thuật toán KNN:
1. Chức năng khoảng cách phải được lựa chọn cẩn thận và tinh chỉnh để đạt
được đợ chính xác cao hơn. Vì phương trình khoảng cách được tính cho tất cả các
tính năng đã chọn, tính năng có giá trị lớn hơn sẽ chiếm ưu thế. Để tính cho điều
này, bình thường hóa các tḥc tính được thực hiện trước khi đo khoảng cách.
2. Dữ liệu có tính năng khơng liên quan hoặc tương quan phải được làm sạch
trước khi không làm lệch kết quả của q trình (Bhatia&Vendana, 2010).
3. Chi phí tính tốn lớn hơn các thuật toán khác, vì quá trình được tính trong bợ
nhớ lượng bợ nhớ u cầu cao.
Để hiểu K-NN được dùng để phân lớp thế nào ta xem minh họa dưới đây:
Chúng ta sẽ đi phân loại xem một bộ phim thuộc thể loại phim hành động hay
phim tình cảm. Việc phân loại phim sẽ được xác định bằng cách đếm số lượng cú đá
hoặc số lượng nụ hơn trong phim. Ở đây, chúng ta đã có mợt tập huấn
luyện(training set), tập đó chứa mợt sớ phim đã biết sớ lượng cú đá, sớ lần ơm trong
phim đó, và loại phim được cho trong bảng sau:


22

Bảng 1.2. Cở sở dữ liệu về Phim
Tên phim
Số cú đá

Sớ nụ hơn

Loại phim


California Man

3

104

Tình cảm

Titanic

2

100

Tình cảm

Beautiful Woman

1

81

Tình cảm

Kevin Longblade

101

10


Hành động

Robo Slayer 3000

99

5

Hành động

Amped II

98

2

Hành động

???

18

90

Chưa xác định

Chúng ta đã biết được số lượng cú đá, số lượng nụ hôn trong phim. Nhiệm vụ của
chúng ta ở đây là xác định xem phim “???” tḥc thể loại phim gì?
Đầu tiên chúng ta sẽ xác định xem sự giống nhau của phim “???” với các phim

khác như thế nào? Để làm được điều đó, chúng ta sẽ sử dụng Euclidean distance.
Euclidean distance là việc chúng ta tìm khoảng cách giữa hai điểm trong khơng
gian, ví dụ cho 2 điểm P1(x1,y1) và P2(x2,y2) thì khoảng cách Euclidean sẽ được tính
theo cơng thức:
d= √(𝑥2 − 𝑥1 )2 + (𝑦2 − 𝑦1 )2

(1.6)

Để áp dụng tính khoảng cách Euclidean vào trong trường hợp này, chúng ta sẽ
coi mỗi phim sẽ được biểu diễn bởi một điểm trong tọa độ Oxy với số lượng cú đá
là tọa độ x và số lượng nụ hôn là tọa đợ y. Điều đó có nghĩa là phim “California
Man” sẽ được biểu diễn bởi điểm (3, 104); phim “Titanic” sẽ được biểu diễn bởi
điểm (2, 100),...
Gọi d là khoảng cách Euclidean thì:
California Man:

d=√(8 − 3)2 + (90 − 104)2 =20.5

Titanic:

d=√(18 − 2)2 + (90 − 100)2 =18.7

Beautiful Woman:

d=√(18 − 1)2 + (90 − 81)2 =19.2

Kevin Longblade:

d=√(18 − 101)2 + (90 − 10)2 =115.3



23

Robo Slayer 3000:

d=√(18 − 99)2 + (90 − 5)2 =117.4

Amped II:

d=√(18 − 98)2 + (90 − 2)2 =118.9

Sau khi tính toán, chúng ta sẽ được kết quả như sau:
Tên phim

Euclidean distance

California Man

20.5

He isn’t really into dudes

18.7

Beautiful Woman

19.2

Kevin Longblade


115.3

Robo Slayer 3000

117.4

Amped II

118.9

Chúng ta đã có khoảng cách Euclidean từ phim chưa biết loại tới từng phim
trong tập huấn luyện, giờ chúng ta sẽ tìm ra k làng giềng gần nhất bằng cách sắp
xếp các phim theo thứ tự Euclidean distance từ nhỏ đến lớn. Giả sử k = 3 thì 3 làng
giềng gần nhất, đó là các phim California Man, He isn't really into dudes và
Beautiful Woman. thuật toán kNN sẽ lấy loại phim nào chiếm ưu thế trong các láng
giếng gần nhất để làm loại phim cho phim cần được xác định loại. Vì 3 phim trên
đều là thể loại Tình cảm ==> Phim cần xác định(“???”) tḥc thể loại phim tình
cảm.
1.4. Đợ đo hiệu năng cho các tḥt tốn phân lớp
Để xác định hiệu quả của thuật toán phân lớp đã được sử dụng thì cần thiết sử
dụng mợt phép đo. Các phép đo phổ biến được sử dụng bao gồm Classification
Accuracy (đợ chính xác phân lớp), Phép đo F-Measure, Precision và recall (Tính
chính xác và đợ bao phủ) , Đường cong ROC và Area Under Curve (AUC)
(Fawcett, 2006). Các phép đo này có thể được tính tốn bằng các kết quả phân loại
thường được lập bảng trong một dạng ma trận gọi là ma trận nhầm lẫn.
1.4.1. Ma trận nhầm lẫn
Trong một vấn đề phân loại nhị phân cổ điển, người ta phân loại bằng cách xếp
các mục như là dương hoặc âm. Một ma trận nhầm lẫn tóm tắt kết quả của tḥt
tốn trong mợt định dạng ma trận (Chawla, 2005). Ma trận nhầm lẫn sẽ có bốn kết



24

quả:
True positives TP : mẫu mang nhãn dương được phân lớp đúng vào lớp dương.
True negatives TN: mẫu mang nhãn âm được phân lớp đúng vào lớp âm.
False positives FP: mẫu mang nhãn dương bị phân lớp sai vào lớp âm.
False negatives FN: mẫu mang nhãn âm bị phân lớp sai vào lớp dương.
Bảng 1.3. Ma trận nhầm lẫn
Classified As:

Confusion Matrix

Positive Negative

Actual

Positive

TP

FN

Class

Negative

FP

TN


Các phép đo hiệu suất sau đây sử dụng các giá trị của ma trận nhầm lẫn trong
phép tính:
1.4.2. Đợ chính xác phân lớp
Cách đo hiệu suất đơn giản nhất chính là đợ chính xác. Hiệu quả tổng thể của
thuật toán được tính bằng cách chia nhãn đúng cho tất cả các phân lớp. Đợ chính
xác của mơ hình(M) được tính như sau:

A(M) =

𝑇𝑃+𝑇𝑁
𝑇𝑃+𝐹𝑃+𝑇𝑁+𝐹𝑁

(1.7)

Đợ lỗi của mơ hình M được tính như sau: Err_rate(M)= 1- A𝑐𝑐𝑢𝑟𝑎𝑐𝑦(M)
Đợ chính xác xác định có thể khơng phải là mợt thước đo hiệu suất phù hợp khi số
trường hợp negatives lớn hơn nhiều trường hợp positive (Kubat và cợng sự, 1998).
Tỷ lệ chính xác càng cao thì mơ hình phân loại càng hoạt động tốt hơn.
1.4.3. Độ đo F
F-Measure (Lewis và Gale, 1994) là một trong những thước đo phổ biến được sử
dụng như là một thước đo hiệu suất. Độ đo được tính bằng cách sử dụng hai hiệu
suất khác đo lường là Precision và Recall.
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =

𝑇𝑃
𝑇𝑃+𝐹𝑃

𝑟𝑒𝑐𝑎𝑙𝑙 = 𝑠𝑒𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦 =


(1.8)
𝑇𝑃
𝑇𝑃+𝐹𝑁

(1.9)


25

Precision là sớ ví dụ đúng được phân lớp trên tất cả các ví dụ được phân lớp. Recall
cịn được gọi là True Positive Rate (TPR), là tỷ lệ số lượng các ví dụ đúng được
phân lớp trên tất cả các ví dụ đúng. Dựa trên các định nghĩa, F-measure này được
định nghĩa như sau:
f – measure =

2 ×𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛×𝑟𝑒𝑐𝑎𝑙𝑙
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛+𝑟𝑒𝑐𝑎𝑙𝑙

(1.10)

Về bản chất, F-Measure là trung bình điều hịa của các hiệu suất Recall và
Precision.
1.4.4. Độ nhạy và độ đặc tả
Hiệu suất của trình phân lớp nhị phân đơi khi có thể được định lượng theo đợ
chính xác của nó như được mô tả ở trên, nghĩa là phần lớp được phân lớp sai trong
tồn bợ tập. Tuy nhiên, có thể có những lần các lớp bị phân lớp sai có thể là rất
quan trọng trong phân cấp phân lớp (Powers, 2011). Trong những trường hợp này,
các giá trị độ nhạy và độ đặc hiệu được sử dụng để xác định hiệu suất của phân loại.
True Positive Rate (TPR) là tỷ lệ số lượng dự đoán đúng thực trên số lượng các
trường hợp đúng trong tồn bợ bợ dữ liệu.

𝑠𝑒𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡𝑦 =

𝑇𝑃

(1.11)

𝑇𝑃+𝐹𝑁

Đợ đặc hiệu hoặc Tỷ lệ phủ định thực (True Negative Rate - TNR) là tỷ sớ dự
đoán âm tính thực với sớ lượng các trường hợp âm trong tồn bợ bợ dữ liệu.
𝑠𝑝𝑒𝑐𝑖𝑓𝑖𝑐𝑖𝑡𝑦 =

𝑇𝑁

(1.12)

𝑇𝑁+𝐹𝑃

1.4.5. Đường cong ROC
ROC là một đường cong minh họa hiệu suất của một hệ thống phân loại nhị phân khi
thay đổi ngưỡng phân lớp. Đường cong được tạo ra bằng cách vẽ tỷ lệ true
positive (TPR) so với tỷ lệ false positive (FPR) các thiết lập ngưỡng khác nhau.
TPR =

𝑇𝑃
𝑇𝑃+𝐹𝑁

FPR =

𝐹𝑃

𝐹𝑃+𝑇𝑁

(1.13)

Đường cong cho thấy hiệu quả của phân lớp được thử nghiệm trong các trường
hợp dương xếp hạng tương đối so với trường hợp âm. Các điểm (0, 1) biểu thị phân