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
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


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


MỤC LỤC
LỜI CAM ĐOAN ................................................................................................................. i
LỜI CẢM ƠN ................................................................................................................... iii
MỤC LỤC ......................................................................................................................... iv
DANH MỤC CÁC TỪ VIẾT TẮT ................................................................................ vii
DANH MỤC CÁC BẢNG, BIỂU .................................................................................... ix
DANH MỤC HÌNH VẼ..................................................................................................... x
MỞ ĐẦU ............................................................................................................................. 1
CHƯƠNG 1 TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC ......... 3
1.1 Giới thiệu chung ......................................................................................................... 3
1.1.1 Khái niệm khai phá dữ liệu .................................................................................. 3
1.1.2 Các bước của quá trình phát hiện tri thức ............................................................ 4
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
2.2.1 Cây quyết định quy nạp ..................................................................................... 16
Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN


3.2 Giới thiệu về phân lớp dữ liệu sử dụng công cụ Weka ............................................ 55
3.2.1 Thuật toán Hồi quy logistic (Logistic Regression) ............................................ 56
3.2.2 Thuật toán Naive Bayes ..................................................................................... 58
3.2.3 Thuật toán Cây quyết định (Decision Tree) ...................................................... 60
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


vi

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


5.

AAPC

6.

TP

True Positive

Đúng là dữ liệu Positive

7.

FP

False Positive

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

8.

TN

True Negative

Đúng là dữ liệu Negative

9.


Chú thích
Thành phần sửa đổi tương tựa
như một Ubiquitin nhỏ
Phát hiện tri thức

Đặc trưng: AAPC

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

Specificity:

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


http://lrc.tnu.edu.vn


ix

DANH MỤC CÁC BẢNG, BIỂU

Bảng 2. 1 Các bộ dữ liệu huấn luyện từ cơ sở dữ liệu khách hang AllElectronics ........... 18
Bảng 2. 2. Dữ liệu mẫu cho lớp mua máy tính .................................................................. 23
Bảng 3. 1 Bảng tổng hợp dữ liệu thu thập từ các nguồn khác nhau .................................. 48
Bảng 3. 2 Bảng tổng hợp dữ liệu thu được sau khi loại bỏ dữ liệu dư thừa bởi công cụ
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


x

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

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
Hình 3. 15. Kết quả phân lớp Weka cho thuật toán k-Nearest Neighbors ........................ 65
Hình 3. 16. Cấu hình Weka cho thuật toán Máy hỗ trợ Vector (Support Vector
Machines). ......................................................................................................................... 66
Hình 3. 17. Kết quả phân lớp Weka cho thuật toán Máy hỗ trợ Vector ............................ 67

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

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


3

CHƯƠNG 1
TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC
1.1 Giới thiệu chung
Trong những năm gần đây, Công nghệ thông tin phát triển mạnh mẽ và có những
tiến bộ vượt bậc. Cùng với sự phát triển của Công nghệ thông tin là sự bùng nổ thông tin.
Các thông tin tổ chức theo phương thức sử dụng giấy trong giao dịch đang dần được số
hóa, do nhiều tính năng vượt trội mà phương thức này mang lại như: có thể lưu trữ lâu dài,
cập nhật, sửa đổi, tìm kiếm một cách nhanh chóng. Đó là lý do khiến cho số lượng thông

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

http://lrc.tnu.edu.vn


5

liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. Vì
vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ:
tuổi = 673. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên.
Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là
một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch - tiền xử lý - chuẩn
bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng.
(4) Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có

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ử dụng

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


7

các miền phân lớp để tự động quyết định liệu những người vay nợ trong tương lai có nên
cho vay hay không.

Hinh 1. 3. Phân lớp được học bằng mạng nơron cho tập dữ liệu cho vay

đượ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:
• Bước 1: tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác định qua tính độ
hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.
• Bước 2: sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ
trợ cực tiểu và độ tin cậy cực tiểu.
Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như marketing có
chủ đích, phân tích quyết định, quản lí kinh doanh,…
1.3. Phân tích, so sánh với các phương pháp cơ bản khác
Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành học khác như: hệ
CSDL, thống kê,... Hơn nữa, tuỳ vào cách tiếp cận được sử dụng, khai phá dữ liệu còn có
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

thể áp dụng một số kĩ thuật như mạng nơ ron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri
thức…
Như vậy, có thể hiểu rằng khai phá dữ liệu thực ra là dựa trên các phương pháp cơ
bản đã biết. Tuy nhiên, sự khác biệt của khai phá dữ liệu so với các phương pháp đó là gì?
Tại sao khai phá dữ liệu lại có ưu thế hơn hẳn các phương pháp cũ? Ta sẽ lần lượt xem xét

thống kê một cách hiệu quả vì thế giảm bớt công việc của người dùng đầu cuối, tạo ra một
công cụ dễ sử dụng hơn.
1.3.3 So sánh với phương pháp học máy (Machine Learning)
So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai phá dữ
liệu có thể sử dụng với các cơ sở dữ liệu thường động, không đầy đủ, bị nhiễu và lớn hơn
nhiều so với các tập dữ liệu học máy điển hình. Trong khi đó phương pháp học máy chủ
yếu được áp dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu không quá lớn.
Thật vậy, trong học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập tới một tập các mẫu
được lưu trong tệp. Các mẫu thường là các vectơ với độ dài cố định, thông tin về đặc điểm,
dãy các giá trị của chúng đôi khi cũng được lưu lại như trong từ điển dữ liệu. Một giải thuật
học sử dụng tập dữ liệu và các thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra
biểu thị kết quả của việc học. Học máy có khả năng áp dụng cho cơ sở dữ liệu, lúc này,
học máy sẽ không phải là học trên tập các mẫu nữa mà học trên tập các bản ghi của cơ sở
dữ liệu. Tuy nhiên, trong thực tế, cơ sở dữ liệu thường động, không đầy đủ và bị nhiễu, lớn
hơn nhiều so với các tập dữ liệu học máy điển hình. Các yếu tố này làm cho hầu hết các
giải thuật học máy trở nên không hiệu quả. Khai phá dữ liệu lúc này sẽ xử lý các vấn đề
vốn đã điển hình trong học máy và vượt quá khả năng của học máy, đó là sử dụng được
các CSDL chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục.
1.3.4 So sánh với phương pháp học sâu (Deep Learning)
Khái niệm chính trong thuật toán nghiêng sâu là tự động hóa việc khai thác các biểu
diễn (trừu tượng) từ dữ liệu. Thuật toán học tập sâu sử dụng một lượng lớn dữ liệu không
giám sát để tự động trích xuất biểu diễn phức tạp. Những thuật toán này chủ yếu được thúc
đẩy bởi lĩnh vực trí thông minh nhân tạo, có mục tiêu chung là mô phỏng khả năng của con
người để quan sát, phân tích, học hỏi và đưa ra quyết định, đặc biệt cho các vấn đề cực kỳ
phức tạp. Công việc liên quan đến những thách thức phức tạp này là động lực chính đằng
sau các thuật toán Deep Learning cố gắng mô phỏng cách tiếp cận học tập phân cấp của bộ
não con người. Các mô hình dựa trên kiến trúc học tập nông như cây quyết định, máy hỗ
trợ vector và lý do dựa trên trường hợp có thể bị thiếu khi cố gắng trích xuất thông tin hữu
ích từ cấu trúc và mối quan hệ phức tạp trong kho dữ liệu đầu vào. Ngược lại, kiến trúc
Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN

nhiều nguồn. Ví dụ: hình ảnh bao gồm các nguồn biến thể khác nhau như ánh sáng, hình
dạng đối tượng và vật liệu đối tượng. Các biểu diễn trừu tượng được cung cấp bởi các thuật
toán học tập sâu có thể tách các nguồn khác nhau của các biến thể trong dữ liệu.
Thuật toán học sâu là kiến trúc sâu của các lớp liên tiếp. Mỗi lớp áp dụng một phép
biến đổi phi tuyến trên đầu vào của nó và cung cấp một biểu diễn trong đầu ra của nó. Mục
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

đích là để tìm hiểu một biểu diễn phức tạp và trừu tượng của dữ liệu theo cách phân cấp
bằng cách truyền dữ liệu qua nhiều lớp chuyển đổi. Dữ liệu cảm giác (ví dụ: pixel trong
một hình ảnh) được nạp vào lớp đầu tiên. Do đó, đầu ra của mỗi lớp được cung cấp làm
đầu vào cho lớp tiếp theo của nó.

CHƯƠNG 2
CÁC PHƯƠNG PHÁP VÀ KỸ THUẬT PHÂN LỚP 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


13

2.1 Tổng quan về phân lớp dữ liệu
Phân lớp dữ liệu là một xử lý bao gồm hai bước (Hinh 2. 1). Ở bước đầu tiên, xây
dựng mô hình mô tả một tập cho trước các lớp dữ liệu. Mô hình này có được bằng cách

14

Hinh 2. 1. Xử lý phân lớp dữ liệu
Ví dụ 2.1: Giả sử rằng ta có một cơ sở dữ liệu các khách hàng trên danh sách thư
(mailing list) AllElectronics. Danh sách thư được dùng để gửi đi các tài liệu quảng cáo mô
tả các sản phẩm mới và yết lên các sản phẩm hạ giá. Cơ sở dữ liệu mô tả các thuộc tính của
khách hàng như tên, tuổi, thu nhập, nghề nghiệp và độ tín nhiệm. Khách hàng được phân
lớp vào nhóm người mua hay không mua máy tính tại AllElectronics. Giả sử rằng các khách
hàng mới được thêm vào cơ sở dữ liệu và bạn sẽ thông báo cho những khách hàng này
thông tin bán máy tính. Thay vì gửi tài liệu quảng cáo tới từng khách hàng mới, ta chỉ gửi
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