i

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

VILAISAK SOPHABMIXAY

NGHÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP VÀ ỨNG
DỤNG TRONG PHÂN LỚP DỮ LIỆU PROTEIN SUMO HÓA.
Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 84 80 10 1

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: TS. NGUYỄN VĂN NÚI

THÁI NGUYÊN - 2019


ii

LỜI CAM ĐOAN
Luận văn này là công trình nghiên cứu của cá nhân tôi, được thực hiện dưới sự
hướng dẫn khoa học của TS. Nguyễn Văn Núi. Các số liệu, những kết luận nghiên cứu
được trình bày trong luận văn này hoàn toàn trung thực.
Học Viên
Vilaisak SOPHABMIXAY


3

LỜI CẢM ƠN

1.2 Tổng quan các kỹ thuật khai phá dữ liệu cơ bản........................................................ 5
1.2.1 Khai phá dữ liệu dự đoán..................................................................................... 6
1.2.1.1 Phân lớp......................................................................................................... 6
1.2.1.2 Hồi quy .......................................................................................................... 7
1.2.2 Khai phá dữ liệu mô tả......................................................................................... 7
1.2.2.1 Phân cụm ....................................................................................................... 7
1.2.2.2 Luật kết hợp................................................................................................... 8
1.3. Phân tích, so sánh với các phương pháp cơ bản khác ............................................... 8
1.3.1 So sánh với phương pháp hệ chuyên gia (Expert Systems) ................................ 9
1.3.2 So sánh với phương pháp thống kê (Statistics) ................................................... 9
1.3.3 So sánh với phương pháp học máy (Machine Learning)................................... 10
1.3.4 So sánh với phương pháp học sâu (Deep Learning).......................................... 10
CHƯƠNG 2 CÁC PHƯƠNG PHÁP VÀ KỸ THUẬT PHÂN LỚP DỮ LIỆU............... 12
2.1 Tổng quan về phân lớp dữ liệu................................................................................. 13
2.2 Phân lớp dữ liệu bằng cây quyết định ...................................................................... 15


5

2.2.1 Cây quyết định quy nạp ..................................................................................... 16


6

2.2.2 Cây cắt tỉa .......................................................................................................... 20
2.2.3 Trích luật phân lớp từ các cây quyết định ......................................................... 20
2.2.4 Cải tiến cây quyết định quy nạp cơ bản............................................................. 21
2.2.5 Khả năng mở rộng và cây quyết định quy nạp .................................................. 22
2.3 Phân lớp dữ liệu Bayesian........................................................................................ 23
2.3.1 Định lý Bayes..................................................................................................... 24

3.2.4 Thuật toán k-Nearest Neighbors ........................................................................ 63
3.2.5 Thuật toán Máy hỗ trợ Vector (Support Vector Machines) .............................. 65
3.3 Kết quả phân lớp dữ liệu vị trí protein SUMOylation ............................................. 68
KẾT LUẬN ....................................................................................................................... 70
TÀI LIỆU THAM KHẢO ................................................................................................. 71
Tiếng Việt:...................................................................................................................... 71
Tiếng Anh:...................................................................................................................... 71

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


vii

DANH MỤC CÁC TỪ VIẾT TẮT

TT

Từ viết tắt

Tên đầy đủ

1.

SUMO

Small Ubiquitin-like MOdifier

2.


7.

FP

False Positive

Không phải dữ liệu Positive

8.

TN

True Negative

Đúng là dữ liệu Negative

9.

FN

False Negative

Không phải dữ liệu Negative

10.

SEN

Sensitivity: SEN=TP/(TP+FN)


Tỷ lệ dự đoán đúng dữ liệu

SPE=TN/(TN+FP)

Negative

Accuracy

Độ chính xác

Mathews Correlation
Coefficient

Hệ số tương quan Mathews

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


8

14.
15.

16.

SUMOylated
protein

CD-HIT .......................................................................................................... 52
Bảng 3. 3. Hiệu năng của mô hình dự đoán, đánh giá bởi kiểm tra chéo 5 mặt (5-fold
cross-validation)............................................................................................. 68
Bảng 3. 4 Hiệu năng của mô hình dự đoán, đánh giá bởi dữ liệu kiểm thử độc lập ......... 69

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


1
0

DANH MỤC HÌNH VẼ
Hinh 1. 1. Quá trình phát hiện tri thức................................................................................. 4
Hinh 1. 2. Tập dữ liệu với 2 lớp: có và không có khả năng trả nợ...................................... 6
Hinh 1. 3. Phân lớp được học bằng mạng nơron cho tập dữ liệu cho vay ..........................
7
Hinh 1. 4. Phân cụm tập dữ liệu cho vay vào trong 3 cụm ................................................. 8
Hinh 2. 1. Xử lý phân lớp dữ liệu...................................................................................... 14
Hinh 2. 2. Cây quyết định cho khái niệm mua máy tính ...................................................
15
Hinh 2. 3. Thuộc tính tuổi có thông tin thu được cao nhất................................................ 19
Hinh 2. 4. Các cấu trúc dữ liệu danh sách thuộc tính và danh sách lớp được dung trong
SLIO cho dữ liệu mẫu trong bảng 2.2 ............................................................................... 23
Hinh 2. 5. a) Mạng belief Bayesian đơn giản, b) Bảng xác suất có điều kiện cho............
28
Hinh 2. 6. Mô hình Rừng ngẫu nhiên ................................................................................ 31
Hinh 2. 7. Một đường thẳng tuyến tính phân chia 2 lớp điểm (hình vuông và hình tròn)
trong không gian hai chiều. Ranh giới quyết định chia không gian thành hai tập tùy thuộc

................................................................................................................. 41

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


1
2

Hinh 2. 12. Một xấp xỉ tập thô của tập các mẫu thuộc lớp C ...........Error! Bookmark not
defined.
Hinh 2. 13. Các giá trị mờ đối với thu nhập ...................... Error! Bookmark not defined.
Hinh 2. 14. Đánh giá độ chính xác classifier với phương pháp holdout ........................... 44
Hinh 2. 15. Tăng độ chính xác classifier ........................................................................... 45
Hình 3. 1. Sơ đồ tổng thể hoạt động của phương pháp triển khai ..................................... 49
Hình 3. 2. Sơ đồ trích chọn và mã hóa đặc trưng .............................................................. 53
Hình 3. 3. Sơ đồ quá trình trích chọn đặc trưng AAC....................................................... 53
Hình 3. 4. Sơ đồ quá trình trích chọn đặc trưng AAPC .................................................... 55
Hình 3. 5 Phần mềm WEKA (Waikato Environment for Knowledge Analysis).............. 55
Hình 3. 6. Cấu hình Weka cho thuật toán hồi quy logistic................................................ 57
Hình 3. 7. Kết quả phân lớp Weka cho thuật toán hồi quy logistic................................... 58
Hình 3. 8. Cấu hình Weka cho thuật toán Naive Bayes .................................................... 59
Hình 3. 9. Kết quả phân lớp Weka cho thuật toán Naive Bayes ....................................... 60
Hình 3. 10. Cấu hình Weka cho thuật toán Cây quyết định (Decision Tree).................... 61
Hình 3. 11. Kết quả phân lớp Weka cho thuật toán Cây quyết định (Decision Tree)....... 62
Hình 3. 12. Mô hình cây quyết định hiển thị bởi C4.5...................................................... 62
Hình 3. 13. Cấu hình Weka cho thuật toán k-Nearest Neighbors ..................................... 63
Hình 3. 14. Cấu hình weka cho thuật toán tìm kiếm trong thuật toán k-Nearest Neighbors
........................................................................................................................................... 64

chìa khoá quan trọng. Vì vậy, trong luận văn này, tác giả sẽ đề cập tới kỹ thuật thường
dùng trong khai phá dữ liệu, đó là Phân lớp (Classification).
Sau phần mở đầu, nội dung chính của luận văn được trình bày chi tiết và bố cục chia
thành 3 chương như sau:
Chương 1. Tổng quan về khai phá dữ liệu và phát hiện tri thức
Phần này giới thiệu một cánh tổng quát về quá trình phát hiện tri thức nói chung và
khai phá dữ liệu nói riêng. Đặc biệt nhấn mạnh về một kỹ thuật chính được nghiên cứu
trong luận văn đó là Kỹ thuật phân lớp.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


2

Chương 2. Các phương pháp và kỹ thuật phân lớp dữ liệu
Trong phần này, kỹ thuật phân lớp được giới thiệu một cách chi tiết. Có nhiều kiểu
phân lớp như phân lớp bằng cây quyết định quy nạp, phân lớp dữ liệu Bayesian, phân lớp
dữ liệu với Random Forest (rừng ngẫu nhiên), Phân lớp dữ liệu sử duing máy hỗ trợ
vector và một số phương pháp phân lớp dữ liệu khác. Ngoài ra còn vấn đề đánh giá độ
chính xác của phương pháp phân lớp dữ liệu.
Chương 3. Kết quả thử nghiệm
Phần này giới thiệu bài toán phân lớp dữ liệu protein SUMO hóa, giới thiệu về phân
lớp dữ liệu sử dụng công cụ Weka và một số kết quả phân lớp dữ liệu protein SUMO hóa.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


có giá trị tiềm ẩn từ bên trong lượng lớn dữ liệu được lưu trữ trong các cơ sở dữ liệu
Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


4

(CSDL), kho dữ liệu, trung tâm dữ liệu… lớn hơn là Big Data dựa trên kĩ thuật như mạng
nơ ron, lí thuyết tập thô, tập mờ, biểu diễn tri thức… Đây là một công đoạn trong hoạt
động “làm sạch” dữ liệu.
1.1.2 Các bước của quá trình phát hiện tri thức
Quá trình phát hiện tri thức tiến hành qua 6 giai đoạn như Hình 1.1:

Hinh 1. 1. Quá trình phát hiện tri thức
Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra.
Về lý thuyết thì có vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp
phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá
trình, v.v...
(1) Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu.
Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ
liệu từ các nguồn ứng dụng Web.
(2) Trích lọc dữ liệu: Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo
một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những người có
tuổi đời từ 25 - 35 và có trình độ đại học.
(3) Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai
đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai
phá dữ

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

năng trả nợ ngân hàng).
Hai mục đích chính của khai phá dữ liệu trong thực tế là dự đoán và mô tả.

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


6

Hinh 1. 2. Tập dữ liệu với 2 lớp: có và không có khả năng trả nợ
1.2.1 Khai phá dữ liệu dự đoán
Nhiệm vụ của khai phá dữ liệu dự đoán là đưa ra các dự đoán dựa vào các suy diễn
trên dữ liệu hiện thời. Nó sử dụng các biến hay các trường trong cơ sở dữ liệu để dự đoán
các giá trị không biết hay các giá trị tương lai. Bao gồm các kĩ thuật: phân lớp
(classification), hồi quy (regression)...
1.2.1.1 Phân lớp
Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ
liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô
hình để phân lớp dữ liệu.
Bước 1: Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước. Mỗi
mẫu thuộc về một lớp, được xác định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu
dữ liệu này còn được gọi là tập dữ liệu huấn luyện. Các nhãn lớp của tập dữ liệu huấn
luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn
được gọi là học có giám sát.
Bước 2: Sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phải tính độ
chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng
để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Hay nói cách khác, phân
lớp là học một hàm ánh xạ một mục dữ liệu vào một trong số các lớp cho trước. Hình 1.3
cho thấy sự phân lớp của các dữ liệu vay nợ vào trong hai miền lớp. Ngân hàng có thể sử


http://lrc.tnu.edu.vn


8

thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation),
trong

Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


9

khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này
bạn sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì
vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu được.
Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân
đoạn khách hàng, nhận dạng mẫu, phân lớp trang Web… Ngoài ra phân cụm dữ liệu còn
có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác.
Hình 1.4 cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm: lưu ý rằng
các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một cụm.

Hinh 1. 4. Phân cụm tập dữ liệu cho vay vào trong 3 cụm
1.2.2.2 Luật kết hợp
Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá
trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm
được. Khai phá luật kết hợp được thực hiện qua 2 bước:

xem xét và giải quyết các câu hỏi này.
1.3.1 So sánh với phương pháp hệ chuyên gia (Expert Systems)
Các hệ chuyên gia nắm bắt các tri thức cần thiết cho một bài toán nào đó. Các kỹ
thuật thu thập giúp cho việc lấy tri thức từ các chuyên gia con người.
Mỗi phương pháp hệ chuyên gia là một cách suy diễn các luật từ các ví dụ và giải
pháp đối với bài toán chuyên gia đưa ra. Phương pháp hệ chuyên gia khác với khai phá
dữ liệu ở chỗ các ví dụ của chuyên gia thường ở mức chất lượng cao hơn nhiều so với các
dữ liệu trong CSDL, và chúng thường chỉ bao hàm được các trường quan trọng. Hơn nữa
các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các mẫu phát hiện được.
1.3.2 So sánh với phương pháp thống kê (Statistics)
Mặc dù các phương pháp thống kê cung cấp một nền tảng lý thuyết vững chắc cho
các bài toán phân tích dữ liệu nhưng chỉ có tiếp cận thống kê thuần tuý thôi chưa đủ bởi:
● Các phương pháp thống kê không phù hợp với các kiểu dữ liệu có cấu trúc trong
rất nhiều các cơ sở dữ liệu
● Thống kê hoàn toàn tính toán trên dữ liệu, nó không sử dụng tri thức sẵn có về
lĩnh vực quan tâm
● Các kết quả của phân tích thống kê có thể rất nhiều và khó có thể làm rõ được
● Các phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định
phân tích dữ liệu như thế nào và ở đâu.
Phương pháp thống kê là một trong những nền tảng lí thuyết của khai phá dữ liệu.
Sự khác nhau cơ bản giữa khai phá dữ liệu và thống kê ở chỗ khai phá dữ liệu là một
phương tiện được dùng bởi người sử dụng đầu cuối chứ không phải là các nhà thống kê.
Khai phá dữ liệu đã khắc phục được các yếu điểm trên của thống kê, tự động quá trình
Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

http://lrc.tnu.edu.vn


12


http://lrc.tnu.edu.vn