Luận văn:Nghiên cứu thuật toán phân lớp nhị phân và ứng dụng cho bài toán protein folding

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TPHCM KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ TRI THỨC

(cid:87) (cid:9) (cid:88)

NGUYỄN QUANG PHƯỚC - 0112193

NNGGHHIIÊÊNN CCỨỨUU TTHHUUẬẬTT TTOOÁÁNN PPHHÂÂNN LLỚỚPP NNHHỊỊ PPHHÂÂNN VVÀÀ ỨỨNNGG DDỤỤNNGG CCHHOO BBÀÀII TTOOÁÁNN PPRROOTTEEIINN FFOOLLDDIINNGG

LUẬN VĂN CỬ NHÂN TIN HỌC

GIÁO VIÊN HƯỚNG DẪN

Ths. CHU TẤT BÍCH SAN

Niên khóa 2001 - 2005

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

............................................................................................................................. ............................................................................................................................. ............................................................................................................................. .............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. .............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. .............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. .............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. .............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. .............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. ............................................................................................................................. Tp HCM, ngày tháng năm 2005

ThS. Chu Tất Bích San

NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN

Tp HCM, ngày tháng năm 2005

TS. Lê Hoài Bắc

Lời cám ơn (cid:68)(cid:69)

Sau nhiều tháng nghiên cứu và thực hiện, luận văn đã hoàn tất và đã đạt

được những kết quả nhất định.

Trước hết, em xin được bày tỏ lòng biết ơn đối với cô Chu Tất Bích

San và thày Phạm Nguyễn Anh Huy đã nhiệt tình, tận tâm hướng dẫn và chỉ

bảo cho em thực hiện đề tài luận văn tốt nghiệp này.

Em xin chân thành cám ơn Khoa Công Nghệ Thông Tin, Trường Đại

học Khoa Học Tự Nhiên Tp HCM đã tạo điều kiện cho em thực hiện đề tài tốt

nghiệp này.

Em xin chân thành cám ơn quý thày cô trong Khoa Công Nghệ Thông

Tin đã tận tình giảng dạy, truyền đạt cho em những kiến thức quý báu trong

những năm học vừa qua.

Sau cùng, em xin chân thành cảm ơn gia đình, những người thân và bạn

bè đã giúp đỡ, động viên em trong suốt thời gian học tập và làm luận văn này.

Một lần nữa, xin chân thành cám ơn tất cả mọi người!

TpHCM, Tháng 7/2005

Sinh viên thực hiện

Nguyễn Quang Phước

MỞ ĐẦU

Trong những năm gần đây, khai thác dữ liệu đã trở thành một trong

những hướng nghiên cứu lớn nhất của lĩnh vực khoa học máy tính và công

nghệ tri thức. Khai thác dữ liệu đã và đang ứng dụng thành công vào nhiều

lĩnh vực thương mại, tài chính, thị trường chứng khoáng, y học, thiên văn,

môi trường, giáo dục, viễn thông và sinh học..v.v.

Khối lượng thông tin đã được xử lý và đã được sản sinh trong tất cả các

lĩnh vực hoạt động của loài người đã và đang tăng lên đáng kể, chúng được

lưu trữ trong các cơ sở dữ liệu tập trung hay phân tán. Trong những kho dữ

liệu này ẩn chứa một kho tàng tri thức quý báu, muốn lấy được kho báu này

chúng ta phải có một công cụ đó là các phương pháp khai thác dữ liệu.

Khai thác dữ liệu gồm nhiều hướng tiếp cận. Các kỹ thuật chính được

áp dụng trong lĩnh vự này phần lớn được kế thừa từ các lĩnh vực cơ sở dữ liệu,

máy học (machine learning), trí tuệ nhân tạo (artificial intelligence), lý thuyết

thông tin (information theory), xác suất thống kê (probability & statistics),

tính toán hiệu năng cao (high performance computing), và phương pháp tính

toán mềm (soft computing methodologies). Các bài toán chủ yếu trong khai

thác dữ liệu là khai thác chuỗi (text mining), khai thác web (web mining),

khai thác chuỗi (sequence mining), khai thác luật kết hợp (association rules

mining), lý thuyết tập thô (rough set theory), gom cụm (clustering), phân lớp

(classification)… Trong đó phân lớp là một trong các nội dung quan trọng của

khai thác dữ liệu và đây là một lĩnh vực nghiên cứu có nhiều triển vọng với

nhiều khả năng ứng dụng thực tế. Luận văn này được xây dựng dựa trên ý

tưởng cho một thuật toán giảm thiểu sự phân lớp quá khớp (overfitting) và sự

phân lớp quá khái quát (overgeneralization) của thầy Phạm Nguyễn Anh Huy

(2005). Sau đó, áp dụng thuật toán này cho bài toán protein folding, đây là

một bài toán khám phá cấu trúc 3D của protein. Cấu trúc 3D của protein được

hình thành từ cấu tạo các chuỗi amino axit, nó cung cấp những manh mối

quan trọng về các chức năng của từng protein. Vì vậy, bài toán protein folding

là một bài toán lớn và quan trọng trong ngành sinh học. Phần này sẽ được

trình bày kỹ hơn trong nội dung luận văn.

Luận văn sẽ bao gồm các phần chính như sau:

Chương 1: Giới thiệu tổng quan về bài toán phân lớp (classification)

và protein folding. Chương này sẽ giới thiệu các khái niệm về phân lớp, các

bước để giải quyết một bài toán phân lớp và trình bày vấn đề quá

khớp(overfitting) và quá khái quát (overgeneralization) trong bài toán phân

lớp. Đồng thời giới thiệu bài toán protein folding.

Chương 2 : Trình bày một số thuật toán phân lớp phổ biến hiện nay

như cây quyết định (decision trees), mạng Bayesian, mạng neural và thuật

toán Support Vector Machine (SVM).

Chương 3 : Trình bày chi tiết thuật toán phân lớp kết hợp giữa phân

lớp quá khớp với phân lớp quá khái quát của thầy Phạm Nguyễn Anh Huy.

Chương 4 : Áp dụng bài toán phân lớp cho Protein folding và đánh giá

kết quả được, so sánh kết quả đạt được so với các thuật toán phân lớp khác.

MỤC LỤC

DANH SÁCH CÁC BẢNG ........................................................................................i

DANH SÁCH CÁC HÌNH .......................................................................................iii

CHƯƠNG 1:TỔNG QUAN BÀI TOÁN PHÂN LỚPVÀ PROTEIN FOLDING ....1

1.1. BÀI TOÁN PHÂN LỚP (CLASSIFICATION).............................................2

1.1.1. Giới thiệu.............................................................................................2

1.1.2. Các bước chính để giải quyết bài toán phân lớp.................................3

1.2. OVERFITTING VÀ OVERGENERALIZATION TRONG BÀI TOÁN

PHÂN LỚP...................................................................................................6

1.3. PROTEIN FOLDING.....................................................................................7

CHƯƠNG 2: MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN.............................9

2.1. CÂY QUYẾT ĐỊNH (DECISION TREES) ...............................................10

2.1.1. Định nghĩa và thuật toán tạo cây quyết định.....................................10

2.1.2. Độ đo Entropy...................................................................................13

2.1.3. Rút trích luật phân lớp từ cây quyết định đo Entropy …..................14

2.2. MẠNG BAYESIAN....................................................................................17

2.2.1. Lý thuyết Bayes.................................................................................17

2.2.2.Thuật toán phân lớp Naive Bayes.....................................................18

2.2.3. Mạng Bayesian..................................................................................20

2.2.4.Học (huấn luyện) trên mạng Bayesian...............................................22

2.3. MẠNG NEURAL........................................................................................24

2.3.1. Mạng lan truyền tiến đa tầng.............................................................24

2.3.2. Xây dựng cấu trúc mạng...................................................................25

2.3.3. Lan truyền ngược……………….....................................................26

2.4. SUPPORT VECTOR MACHINE (SVM) ..................................................31

2.4.1 Giới thiệu SVM..................................................................................31

2.4.2. RBF Kernel.......................................................................................32

2.4.3. Tối ưu tham số...................................................................................33

CHƯƠNG 3: THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ

QUÁ KHÁI QUÁT...................................................................................................36

3.1. GIỚI THIỆU................................................................................................37

3.2. MỘT SỐ ĐỊNH NGHĨA..............................................................................38

3.2.1 Homogenous Clauses.........................................................................38

3.2.2. Mật độ của một Homogenous Clause...............................................41

3.3. CHI TIẾT THUẬT TOÁN..........................................................................41

3.3.1. Thuật toán chính................................................................................42

3.3.2. Các thuật toán hỗ trợ ........................................................................46

3.3.2.1. Thuật toán tìm các Positive Clauses....................................46

3.3.2.2. Thuật toán tìm các Homogenous Clauses ..........................48

3.3.2.3. Thuật toán mở rộng Homogenous Clause...........................50

3.3.2.4. Thuật toán gom các Homogenous Clauses..........................53

CHƯƠNG 4: CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN

PROTEIN FOLDING..........................................................................55

4.1. CÀI ĐẶT THUẬT TOÁN...........................................................................56

4.1.1. Chương trình Demo trên không gian hai chiều.................................56

4.1.2. Cài đặt thuật toán trên không gian N chiều.......................................64

4.1.2.1. Chuẩn bị dữ liệu..................................................................64

4.1.2.2. Giao diện và các chức năng của chương trình.....................65

4.2. KẾT QUẢ ĐẠT ĐƯỢC..............................................................................69

4.2.1 Nguồn dữ liệu trên web site

http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data.........................69

4.2.2. Nguồn dữ liệu trên web site

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.........71

4.3. ÁP DỤNG PHÂN LỚP CHO BÀI TOÁN PROTEIN

FOLDING...................................................................................................74

4.3.1. Bài toán Protein Folding...................................................................74

4.3.2. Mô tả cơ sở dữ liệu...........................................................................76

4.3.3. Kết quả thực hiện..............................................................................80

TỔNG KẾT...............................................................................................................85

TÀI LIỆU THAM KHẢO.........................................................................................86

DANH SÁCH CÁC HÌNH

Hình 1-1: Bước 1 - Học để xây dựng mô hình phân lớp........................................4

Hình 1-2: Bước 2 - Kiểm tra và đánh giá...............................................................5

Hình 1-3: Cấu trúc lớp hoàn toàn xoắn ốc (all- α) của protein..............................8

Hình 1-4: Cấu trúc lớp hoàn toàn hình sợi (all- β) của protein..............................8

Hình 2-1: Minh họa cây quyết định với việc phân lớp tế bào ung thư................10

Hình 2-2: Một ví dụ của mạng Bayesian.............................................................21

Hình 2-3: Mạng lan truyền hai tầng.....................................................................25

Hình 2-4: Một neural trong tầng ẩn hoặc tầng xuất.............................................28

Hình 2-5: Bộ phân lớp quá khít và bộ phân lớp tốt hơn......................................34

Hình 3-1: Minh họa định nghĩa Homogenous Clauses........................................39

Hình 3-2: Vùng A được thay thế bằng hai Homogenous Clauses A1 và A2.......40

Hình 3-3: Một tập mẫu học hai chiều...................................................................43

Hình 3-4: Các Positive Clauses tìm được ở bước 1.............................................43

Hình 3-5: Các Homogenous Clauses tìm được ở bước 2.....................................44

Hình 3-6: Các Homogenous Clauses được mở rộng ở bước 3............................45

Hình 3-7: Một ví dụ Positive Clauses với hai ngưỡng khoảng cách....................48

Hình 3-8: Các Homogenous Clauses cho mỗi Positive Clauses..........................50

Hình 3-9: Các Homogenous Clauses sau khi được mở rộng...............................53

Hình 3-10: Minh họa việc gom các Homogenous Clauses..................................54

Hình 4-1: Giao diện chương trình Demo.............................................................56

Hình 4-2: Giao diện chương trình sau khi nhập dữ liệu.......................................60

Hình 4-3: Giao diện chương trình sau khi tìm các Positive Clauses....................61

Hình 4-4: Giao diện chương trình sau khi tìm các Homogenous Clauses...........62

Hình 4-5: Giao diện chương trình sau khi mở rộng Homogenous Clauses.........63

Hình 4-6: Giao diện chương trình phân lớp cho dữ liệu N chiều.........................65

Hình 4-7: Giao diện chương trình sau khi đã học xong tập mẫu học...................67

Hình 4-8: Giao diện chương trình sau khi đã kiểm tra và đánh giá xong tậpmẫu

thử……………………………………………………………………………….68

Hình 4-9: Biểu đồ so sánh kết quả..…………………………………………….71

Hình 4-10: Các bậc cấu trúc khác nhau của phân tử protein……………………75

Hình 4-11: Biểu đồ so sánh kết quả phân lớp cấu trúc Protein............................84

Bảng 4-12: Kết quả phân lớp protein của thuật toán SVM và NN......................84

DANH SÁCH CÁC BẢNG

Bảng 2-: Thuật toán phát sinh cây quyết định......................................................12

Bảng 2-2 : Bảng ngẫu nhiên cho mỗi luật............................................................15

Bảng 2-3 : Thuật giải lan truyền ngược...............................................................31

Bảng 3-1: Thuật toán chính..................................................................................42

Bảng 3-2: Thuật toán tìm các Positive Clauses..............................................47

Bảng 3-3: Thuật toán tìm các Homogenous Clauses cho mỗi Positive Clauses..49

Bảng 3-4: Thuật toán mở rộng Homogenous Clause C.......................................52

Bảng 3-5: Thuật toán gom các Homogenous Clauses.........................................54

Bảng 4-1: Ví dụ một tập mẫu hai chiều...............................................................59

Bảng 4-2: Mô tả các tập dữ liệu trên

websitehttp://www.csie.ntu.edu.tw/~cjlin/papers/guide/data/ ............................69

Bảng 4-3: Kết quả phân lớp các tập dữ liệu trên

websitehttp://www.csie.ntu.edu.tw/~cjlin/papers/guide/data/ ............................70

Bảng 4-4: Kết quả phân lớp theo thuật toán SVM của Cjlin ..............................71

Bảng 4-5: Kết quả của quá trình học và dự đoán lớp cho tập dữ liệu trên website:

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/ .........................74

Bảng 4-6: Kết quả phân lớp protein vào lớp all-α ..............................................81

Bảng 4-7: Kết quả phân lớp protein vào lớp all-β...............................................81

Bảng 4-8: Kết quả phân lớp protein vào lớp α /β ..............................................82

Bảng 4-9: Kết quả phân lớp protein vào lớp α +β .............................................82

Bảng 4-10: Kết quả phân lớp protein của thuật toán phân lớp điều chỉnh tính quá

khớp và quá khái quát dữ liệu..............................................................................83

TỔNG QUAN

CHƯƠNG 1:

TỔNG QUAN

BÀI TOÁN PHÂN LỚP

VÀ PROTEIN FOLDING

TỔNG QUAN

1.1. BÀI TOÁN PHÂN LỚP (CLASSIFICATION)

1.1.1. Giới thiệu

Phân lớp (classification) là một tiến trình xử lý nhằm xếp các mẫu dữ

liệu hay các đối tượng vào một trong các lớp đã được định nghĩa trước. Các

mẫu dữ liệu hay các đối tượng được xếp về các lớp dựa vào giá trị của các

thuộc tính (attributes) cho một mẫu dữ liệu hay đối tượng. Sau khi đã xếp tất

cả các đối tượng đã biết trước vào các lớp tương ứng, lúc này mỗi lớp được

đặc trưng bởi tập các thuộc tính của các đối tượng chứa trong lớp đó. Ví dụ:

phân lớp tế bào để xác định tế bào ung thư, giả sử mỗi tế bào có ba thuộc tính

là màu sắc, đuôi và nhân, được biểu diễn tế bào(màu sắc, đuôi, nhân) và ta đã

xếp được ba tế bào vào lớp “tế bào ung thư”, ba tế bào này có giá trị thuộc

tính như sau: tế bào1(tối, 2, 2), tế bào2(tối, 2, 1), tế bào3 (tối, 3, 2). Khi xem

xét một tế bào mới có thuộc tính (tối, 3, 1) ta có thể kết luận nó bị ung thư hay

không bằng cách xác định một lớp mà tế bào này thuộc về, nếu tế bào này

thuộc về lớp “tế bào ung thư” thì tế bào này có thể bị ung thư, ngược lại tế

bào này có thể không bị ung thư.

Phân lớp còn được gọi là phân lớp có giám sát (supervised

classification), là một trong những lĩnh vực phổ biến nhất của học máy

(machine learning) và khai thác dữ liệu (data mining). Nó giải quyết việc xác

định những quy tắc giữa số lượng biến số độc lập và kết quả đạt được hay một

biến số xác định phụ thuộc trong tập dữ liệu được đưa ra. Tổng quát, đưa ra

một tập mẫu học (xi1, xi2, …., xik, yi), i=1,….,N, nhiệm vụ là phải ước lượng

được một bộ phân lớp hay một mô hình xấp xỉ một hàm y = f(x) chưa biết mà

phân lớp chính xác cho bất kỳ mẫu nào thuộc tập các mẫu học. Có nhiều cách

để biểu diễn một mô hình phân lớp và có rất nhiều thuật toán giải quyết nó.

Các thuật toán phân lớp tiêu biểu bao gồm như mạng neural, cây quyết định,

TỔNG QUAN

suy luận quy nạp, mạng Beyesian, Support Vector Machine…. Tất cả các

cách tiếp cập này xây dựng những mô hình đều có khả năng phân lớp cho một

mẫu mới chưa biết dựa vào những mẫu tương tự đã được học.

Bài toán phân lớp có thể xử lý thông tin được thu thập từ mọi lĩnh vực

hoạt động của con người và thế giới tự nhiên được biểu diễn dưới dạng các

bảng. Bảng này bao gồm các đối tượng và các thuộc tính. Các phần tử trong

bảng là các giá trị xác định các thuộc tính (attributes hay features) của các đối

tượng. Trong đó số cột chính là số thuộc tính của các đối tượng, mỗi cột là

một thuộc tính và số dòng chính là số đối tượng chứa trong dữ liệu này. Mọi

dữ liệu được biểu diễn dưới các dạng khác có thể được chuyển thành dạng

bảng như trên để thực hiện quá trình phân lớp. Bài toán phân lớp gồm các

bước như sau:

1.1.2. Các bước chính để giải quyết bài toán phân lớp

Phân lớp dữ liệu gồm hai bước xử lý chính:

Bước 1: Học (training), mục đích của bước này là xây dựng một mô

hình xác định một tập các lớp dữ liệu. Mô hình này được xây dựng bằng cách

phân tích các bộ dữ liệu của một cơ sở dữ liệu, mỗi bộ dữ liệu được xác định

bởi giá trị của các thuộc tính. Giả sử mỗi bộ dữ liệu đã thuộc về một trong các

lớp đã đựơc định nghĩa trước, điều này được xác định bởi một trong các thuộc

tính, gọi là thuộc tính phân lớp. Trong ngữ cảnh của bài toán phân lớp, mỗi bộ

dữ liệu được xem như là một mẫu, một ví dụ, hay một đối tượng. Những bộ

dữ liệu được phân tích để xây dựng mô hình phân lớp được lấy từ trong tập

dữ liệu học hay dữ liệu huấn luyện (training data set). Những bộ dữ liệu riêng

lẻ tạo thành tập dữ liệu huấn luyện còn gọi là những mẫu huấn luyện (training

samples) và được chọn ngẫu nhiên từ một kho các mẫu. Bước này được xem

TỔNG QUAN

là học có giám sát, ngược lại với học có giám sát là học không có giám sát

(unsupervised learing), tiêu biểu là bài toán gom cụm (clustering) trong đó

các lớp mà các mẫu huấn luyện thuộc về là không biết trước và số lớp dữ liệu

cũng không được biết trước.

Hình 1-1: Bước 1 - Học để xây dựng mô hình phân lớp

Mô hình được đưa ra sau khi đã phân tích xong tập dữ liệu huấn luyện

thường có dạng là những quy tắc phân lớp, cây quyết định hay các công thức

toán học. Ví dụ, hình 1.1 có một cơ sở dữ liệu về thông tin khách hàng, một

mô hình phân lớp (hay luật phân lớp) được xây dựng sau quá trình học ở

bước 1 có thể xác định những khách hàng tin cậy và những khách hàng bình

thường của một cửa hàng. Luật phân lớp này có thể được sử dụng để phân

TỔNG QUAN

loại các mẫu dữ liệu liệu trong tương lai, cũng như nó cung cấp một tri thức

hữu ích chứa trong cơ sở dữ liệu.

Bước 2 : Kiểm tra và đánh giá, bước này sử dụng mô hình phân lớp đã

được xây dựng ở bước 1 vào việc phân lớp.

Hình 1-2: Bước 2 - Kiểm tra và đánh giá

Đầu tiên, đánh giá độ chính xác của mô hình hay bộ phân lớp này, bằng

cách sử dụng một tập các mẫu đã được phân lớp để thử (test) gọi là bộ thử

(test set). Những mẫu này được chọn ngẫu nhiên và độc lập với các mẫu đã

được học ở bước 1 gọi là mẫu thử (test sample). Độ chính xác của một mô

hình phân lớp dựa trên bộ thử là tỷ lệ những mẫu thử được phân lớp đúng

bằng mô hình phân lớp đó. Nghĩa là với mỗi mẫu thử, so sánh lớp đúng mà

mẫu thử đó thuộc về với lớp mà mô hình phân lớp này dự đoán cho mẫu thử

đó. Lưu ý, nếu độ chính xác của mô hình này dựa trên tập dữ liệu huấn luyện,

TỔNG QUAN

thì mô hình này được đánh giá là tối ưu, nó phân lớp đúng hoàn toàn trên các

mẫu đã được học, trong trường hợp này, mô hình hướng tới sự quá khít

(overfitting) của dữ liệu. Vì vậy phải sử dụng một bộ dữ liệu liệu thử. Nếu độ

chính xác của một mô hình được xem xét có thể chấp nhận được thì mô hình

đó được dùng để phân lớp cho các bộ dữ liệu hoặc các đối tượng trong tương

lai. Ví dụ, mô hình phân lớp được xây dựng trong bước 1 bằng cách phân

tích dữ liệu của các khách hàng đã biết, được dùng để dự đoán sự “đánh giá”

các khách hàng mới trong tương lai ở hình 1-2.

1.2. OVERFITTING VÀ OVERGENERALIZATION TRONG BÀI

TOÁN PHÂN LỚP

Trong những năm gần đây, có rất nhiều thuật toán cải tiến cho bài toán

phân lớp nhưng chưa có một thuật toán nào hay một hệ thống phân lớp nào có

khả năng phân lớp chính xác tuyệt đối cho các mẫu hay các đối tượng mới (là

những mẫu chưa được học). Độ chính xác của các thuật toán phân lớp chỉ đạt

được ở một mức độ nhất định đối với tập mẫu thử. Độ chính xác này có thể

gần như tuyệt đối hay thấp phụ thuộc vào sự trùng hợp của tập mẫu thử với

tập mẫu đã được học. Gốc của vấn đề này là tính quá khớp (overfitting) và

quá khái quát (overgeneralization) của các thuật toán phân lớp này. Một số

thuật toán đưa ra mô hình phân lớp rất phức tạp để có thể phân lớp chính xác

cho các mẫu học nhưng không chắc rằng mô hình này có thể phân lớp chính

xác cho các mẫu mới, đây chính là sự quá khớp. Rõ hơn, thuật toán mang tính

quá khớp dữ liệu nghĩa là mô hình của thuật toán này đưa ra phân lớp rất tốt

cho những mẫu dữ liệu đã biết nhưng không thể phân lớp chính xác cho các

mẫu dữ liệu mới chưa được biết trước. Sự quá khái quát xuất hiện khi hệ

thống sử dụng dữ liệu sẵn có và cố gắng phân tích cho số lượng lớn dữ liệu

TỔNG QUAN

với các luật quá khái quát. Cả hai vấn đề này có thể là nguyên nhân của độ

chính xác phân lớp không tốt. Đây là lĩnh vực nghiên cứu của các thuật toán

thống kê, như mạng Neural cây quyết định, Support Vector Machine.

1.3. PROTEIN FOLDING

Protein folding là bài toán tìm kiếm cấu trúc 3D cho một protein, cũng

được gọi là trạng thái tự nhiên của nó. Một cấu trúc 3D của một protein được

tạo thành từ các chuỗi axit amin của nó, mỗi axit amin là một hợp chất hữu

cơ. Có 20 loại axit amin khác nhau, được đặt tên là A, C, G, T,… và một

protein được xem như là một chuỗi các axit amin (ví dụ : AGGTC….). Vì

vậy, bài toán protein folding là tìm ra cách mà một chuỗi axit amin (cấu trúc

1D) này xoắn vào trạng thái tự nhiên (cấu trúc 3D) của nó. Bài toán protein

folding là một lĩnh vực nghiên cứu rộng từ cấu trúc 3D của protein sẽ cung

cấp những manh mối quan trọng về chức năng của một protein, trong khi

những chức năng này không thể tìm hiểu được nhanh chóng và dễ dàng qua

các phương pháp thực nghiệm .

Trong quá trình tìm kiếm cấu trúc 3D của protein phải dựa vào một

bước là tìm cấu trúc 2D, đây là hình dạng bên trong chuỗi axit amin con của

protein, những hình dạng này là một hình xoắn ốc (gọi là α-helix) hoặc một

hình sợi (gọi là β-strand). Một protein được phân loại vào một trong bốn lớp

cấu trúc, phụ thuộc vào thành phần cấu trúc phụ đó là : hoàn toàn xoắn ốc (gọi

là all-α), hoàn toàn hình sợi (gọi là all-β), α /β, α +β. Hình dưới đây minh họa

hình dạng hai lớp cấu trúc all- α và all- β.

TỔNG QUAN

Hình 1-3 : Cấu trúc lớp hoàn toàn xoắn ốc (all- α) của protein

Hình 1-4 : Cấu trúc lớp hoàn toàn hình sợi (all- β) của protein

Trong đề tài này, phân lớp cấu trúc protein dựa vào sự tổng hợp các

axit amin (Amino Acid Composition - ACC), ACC là một vector 20 chiều

tương ứng với 20 loại axit amin khác nhau, vector này chỉ rõ tỷ lệ của mỗi

loại axit amin trong sự tổng hợp của 20 loại axit amin khác nhau. Mỗi protein

sẽ được sắp xếp vào một trong bốn lớp cấu trúc all-α, all-β, α /β, α +β.

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

CHƯƠNG 2

MỘT SỐ THUẬT TOÁN

PHÂN LỚP PHỔ BIẾN

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

2.1. CÂY QUYẾT ĐỊNH (DECISION TREES)

2.1.1. Định nghĩa và thuật toán tạo cây quyết định

Một cây quyết định là một cấu trúc cây, trong đó mỗi node trong biểu

thị cho một phép phân nhánh tương ứng cho một thuộc tính, mỗi nhánh biểu

thị cho một kết quả của một phép thử, các node lá biểu thị cho lớp hoặc các

phân bố lớp. Node trên cùng trong một cây được gọi là gốc. Minh họa cho cây

quyết định, hình 2-1 lấy lại ví dụ phân lớp tế bào ung thư với node trong

được biểu diễn bằng hình chữ nhật, node lá được biểu diễn bằng hình ellipse .

Hình 2-1 : Minh họa cây quyết định với việc phân lớp tế bào ung thư

Để phân lớp một mẫu chưa biết, những giá trị thuộc tính của mẫu đó

được thử ngược lại trên cây quyết định. Một đường dẫn từ gốc đến một node

lá là cơ sở cho việc dự đoán lớp của một mẫu. Cây quyết định có thể dễ dàng

chuyển đổi sang một tập các luật phân lớp.

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

Cơ sở toán học của cây quyết định là thuật toán tham lam (greedy

algorithm), thuật toán này đã xây dựng cây quyết định đệ quy từ trên xuống

dưới, theo phương pháp chia để trị. Thuật toán phát sinh cây quyết định dựa

vào dữ liệu học như sau:

Input : những mẫu học được biểu thị bằng những thuộc tính riêng biệt,

một tập các thuộc tính đặc trưng và danh sách các thuộc tính.

Output : một cây quyết định.

1) Khởi tạo một node N;

2) if tất cả các mẫu đều thuộc vào cùng một lớp C then

3) return node N, được xem là một node lá và đặt tên là lớp C;

4) if danh sách thuộc tính là rỗng then

5) return node N, là một node lá được đặt tên lớp là lớp chung nhất

trong các mẫu ; //đây là sự biểu quyết đa số

6) Chọn thuộc tính thử, là một thuộc tính trong danh sách thuộc tính mà

có độ đo cao nhất;

8) Với mỗi giá trị ai đã biết của thuộc tính thử

7) Đặt tên node N với tên của thuộc tính thử;

9) Tạo ra một nhánh từ node N cho điều kiện thuộc tính thử = ai ;

10) Đặt Si là một tập các mẫu lấy trong các mẫu ban đầu với thuộc

tính thử = ai;

11) if Si là rỗng then

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

12) Tạo ra một node lá trên cây quyết định, được đặt tên lớp là

lớp chung nhất của hầu hết các mẫu ;

13) else thêm vào một node là cây kết quả của thuật toán tạo cây với

tham số đầu vào(Si, danh sách thuộc tính , thuộc tính thử)

// một node cũng có cấu trúc cây.

Bảng 2-1: Thuật toán phát sinh cây quyết định

Đây cũng là cách xây dựng cây quyết định của thuật toán nổi

tiếng ID3 (Quinlan 1986), theo thuật toán này :

+ Cây khởi đầu là một node đơn biểu thị cho các mẫu học [bước 1)]

+ Nếu tất cả các mẫu đều thuộc cùng một lớp thì node này trở thành

node lá và được đặt tên là tên của lớp các mẫu thuộc về. [bước 2) và 3)]

+ Ngược lại, thuật toán sử dụng một độ đo Entropy hay còn gọi là độ

đo thông tin là một heuristic lựa chọn thuộc tính có khả năng phân chia cao

nhất các mẫu vào các lớp khác nhau [bước 6)], độ đo này sẽ được trình bày

trong phần 2.1.2. Thuộc tính này trở thành thuộc tính thử hay thuộc tính quyết

định [bước7)]. Trong thuật toán này tất cả các thuộc tính đều có giá trị rời rạc.

+ Một nhánh được tạo ra cho mỗi giá trị đã biết của thuộc tính thử và

các mẫu được phân chia tương ứng [bước 8) - 10)]

+ Thuật toán sử dụng quá trình đệ quy tương tự để hình thành nên cây

quyết định cho các mẫu tại mỗi bước phân chia. Mỗi lần, một thuộc tính xuất

hiện tại mỗi node nó không cần xác định bất kỳ node con cháu nào [bước

13)].

+ Sự phân chia đệ quy chỉ dừng khi thỏa một trong các điều kiện sau:

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

1. Tất cả các mẫu đã cho thuộc cùng một lớp [bước 2), 3)], hoặc

2. Không còn lại thuộc tính nào để các mẫu có thể phân chia

được nữa [bước )]. Trong trường hợp này, sử dụng sự biểu quyết đa

số [bước5)], kéo theo sự biến đổi node được đưa ra thành node lá và đạt

tên là tên lớp chung nhất trong các mẫu, hoặc

3. Không còn mẫu nào trong nhánh mà có thuộc tính thử =ai

[bước11)]. Trong trường hợp này, một node lá được tạo ra với lớp

chung nhất trong các mẫu [bước 12] .

2.1.2. Độ đo Entropy

Độ đo thông tin được dùng để chọn thuộc tính thử tại mỗi node trong

cây. Độ đo này được xem như là độ đo lựa chọn thuộc tính hay độ đo khả

năng của sự phân chia. Thuộc tính có độ đo thông tin cao nhất (hay sự giảm

thiểu Entropy lớn nhất) được chọn là thuộc tính thử cho node hiện hành, thuộc

tính này làm giảm thiểu những thông tin cần thiết để phân lớp cho các mẫu

trong kết quả của những phần phân chia(gồm các mẫu có cùng giá trị thuộc

tính thử). Đây là cách tiếp cận lý thuyết thông tin tối giản việc thử cần thiết

để phân lớp các đối tượng và đảm bảo một cây đơn giản được tạo thành .

Cho S là một tập gồm s mẫu dữ liệu , giả sử có m lớp riêng biệt Ci,

i=1…m, gọi si là số mẫu trong tập S mà thuộc lớp Ci, thông tin cần thiết để

phân lớp các mẫu đã cho được xác định bởi công thức:

i log2(pi) (2.1)

i 1 =

I(s1,s2 ,..., sm) = - ∑ p

Trong đó, pi là tỷ lệ các mẫu thuộc lớp Ci , pi= si / s.

Giả sử thuộc tính A có v giá trị {a1, a2 ,..., av}, thuộc tính A có thể chia

tập S thành v tập con {S1, S2, …, Sv}, trong đó Sj gồm các mẫu trong tập S mà

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

có giá trị thuộc tính A là ai. Nếu A được chọn là thuộc tính thử (thuộc tính tốt

nhất để phân chia) thì những tập con Si tương ứng với các nhánh được hình

thành từ node chứa tập S. Đặt sij số mẫu thuộc lớp Ci mà chứa trong tập con

s 1

Sj thì Entropy của thuộc tính A trong các tập con cho bởi công thức:

++ ... s

j 1 =

s mj

s 1

I(s1j,…, smj) (2.2) E(A) = ∑

++ ... s

j 1 =

được xem như là trọng lượng của tập con Toán hạng ∑

thứ j bằng số mẫu trong tập con mà thuộc tính A có giá trị bằng aj chia cho

tổng số mẫu chứa trong tập S. Hàm Enropy xác định tính không thuần khiết

của một tập con các mẫu dữ liệu, vì vậy phải giảm Entropy trên giá trị đã biết

của thuộc tính A.

Gain(A) = I(s1,s2 ,..., sm) – E(A) (2.3)

Thuật toán này xác định độ đo thông tin cho mỗi thuộc tính, thuộc tính

có độ đo thông tin cao nhất sẽ được chọn làm thuộc tính thử của tập S. Node

A được tạo ra và đặt tên là tên thuộc tính, các nhánh được tạo ra cho mỗi giá

trị của thuộc tính này và các mẫu được chia ra như đã trình bày.

2.1.3. Rút trích luật phân lớp từ cây quyết định

Tri thức trên cây quyết định có thể được rút trích và biểu diễn thành

một dạng luật phân lớp IF - THEN. Khi đã xây dựng được cây quyết định, ta

có thể dễ dàng chuyển cây quyết định này thành một tập các luật phân lớp

tương đương, một luật tương đương với một đường đi từ gốc đến node lá.

Sau khi thu được một tập các luật phân lớp từ cây quyết định, cần phải

tiến hành rút gọn các luật dư thừa nếu có. Một phương pháp đơn giản sử dụng

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

các phép thử thống kê để loại bỏ các luật không cần thiết, phương pháp này

bao gồm các bước như sau:

1) Loại bỏ các tiền đề không cần thiết để đơn giản hóa các luật

+ Xây dựng một bảng ngẫu nhiên cho mỗi luật có chứa nhiều hơn

một tiền đề

Các tổng biên C1 C2

x1 x2 R1T= x1+x2 R1

x3 x4 R2T= x3+x4 R2

Các tổng biên C1T= x1+x3 C2T= x2+x4 T= x1+x2+x3+x4

Bảng 2-2 : Bảng ngẫu nhiên cho mỗi luật

Trong đó:

- R1 và R2 biểu diễn các trạng thái boolean của một tiền đề đối

với các kết luận C1 và C2 (C2 là phủ định của C1).

- x1, x2, x3, x4 biểu diễn tần xuất của từng cặp tiền đề - kết luận

- R1T, R2T, C1T, C2T là tổng biên của các dòng và các cột .

- T là tổng tất cả các tần xuất của bảng

+ Kiểm chứng sự độc lập của kết quả đối với một tiền đề bằng một

trong các phép thử sau:

- Phép thử “Khi bình phương” nếu tần xuất mong đợi >10

- Phép thử “Fisher” nếu tần xuất mong đợi <5.

- Phép thử “Yates” nếu tần xuất mong đợi thuộc [5,10]

Chi tiết phương pháp kiểm sự độc lập, cho một bảng ngẫu nhiên

gồm r dòng và cột:

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

• Tính các tổng biên.

• Tính tổng tần xuất T của bảng.

Tính các tần xuất mong đợi cho mỗi ô theo công thức:

iT * T

2χ

ej =

dựa vào tần xuất • Chọn phép thử cần sử dụng để tính

≤

mong đợi cao nhất m, m>10 phép thử “Khi bình phương”,

2χ

5 ≤ m 10 phép thử Yates, m<5 phép thử Fisher.

e i

(

theo phép thử tương ứng: • Tính

x =2χ ∑ − i e i

x i

−

Phép thử “Khi bình phương”

2)5.0| e − i e i

Phép thử Yates =2χ ∑

2χ

• Tính bậc tự do df = (c-1)*(r-1)

và df đã • Sử dụng một bảng “Khi bình phương” với

tính, để xác định xem liệu các kết quả có độc lập với tiền đề tại

mức ý nghĩa đã chọn không.

2χ

Giả sử mức ý nghĩa α =0.05

2 0χ

> thì giữ lại tiền đề này vì kết luận phụ Nếu

thuộc vào nó.

2χ ≤

2 0χ

Nếu thì loại bỏ tiền đề này vì kết luận không

phụ thuộc vào nó.

2) Loại bỏ các luật không cần thiết để rút gọn tập luật

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

2.2. MẠNG BAYESIAN

Bayesian là phương pháp phân lớp dựa vào thống kê. Ta có thể dự đoán

xác suất của các lớp trong tập dữ liệu, dựa vào xác suất này có thể xếp các

mẫu vào các lớp riêng biệt. Thuật toán phân lớp Bayesian giả thiết rằng giá trị

các thuộc tính của một lớp độc lập với giá trị của các thuộc tính khác, giả

thiết này còn được gọi là lớp độc lập có điều kiện, nó làm đơn giản các tính

toán sau này. Mạng Bayesian là một đồ thị, trên đồ thị cho phép biểu diễn mối

quan hệ giữa các thuộc tính.

2.2.1. Lý thuyết Bayes

Cho X là một mẫu dữ liệu chưa được phân lớp, gọi H là các giả thiết

nào đó sao cho mẫu X thuộc về một lớp xác định C. Vấn đề phân lớp là xác

định P(H|X), là xác suất giả thiết H được chọn với mẫu dữ liệu X cho trước .

P(H|X) gọi là xác suất đến sau hay xác suất hậu nghiệm, đây là xác suất

cần tính vì nó thể hiện độ tin cậy hay khả năng đối với phân lớp tương ứng

với giả thiết H sau khi có mẫu dữ liệu X. Trái lại, P(H) gọi là xác suất đến

trước hay xác suất tiên nghiệm, là xác suất giả thiết H đúng, trước khi có tập

các mẫu dữ liệu. Có thể thấy rằng, xác suất hậu nghiệm P(H|X) phản ánh sự

ảnh hưởng của mẫu dữ liệu X lên giả thiết H. Ví dụ có tập dữ liệu về trái cây

với các thuộc tính là màu sắc và hình dạng, nếu X là một mẫu có màu đỏ,

hình tròn và H là giả thiết X là trái cà chua thì P(H|X) là xác suất X là trái cà

chua khi biết X có các thuộc tính màu đỏ và hình tròn. Còn P(H) là xác suất

xuất hiện trái cà chua, không quan tâm đến mẫu X.

Tương tự, P(X|H) cũng là xác suất hậu nghiệm, cho biết khả năng mẫu

dữ liệu X thuộc về phân lớp của giả thiết H. Với ví dụ trên P(X|H) là xác suất

X có màu đỏ và hình tròn khi biết X là trái cà chua. P(X) được tính theo công

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

thức xác suất đầy đủ, là xác suất mà mẫu X xảy ra, không cần biết thuộc về

phân lớp nào. P(X|H) được xem là xác suất tiên nghiệm vì phải xác định

trước. Trong ví dụ P(X) là xác suất một mẫu X lấy từ trong tập dữ liệu có màu

đỏ và hình tròn.

Các xác suất P(X), P(H) và P(X|H) có thể ước lượng dựa vào thống kê

(

)

XHP

(

)

HXPHP ) ( XP (

)

tập dữ liệu. Lý thuyết Bayes ra công thức tính xác suất P(H|X) như sau:

2.2.2.Thuật toán phân lớp Naive Bayes

Một ứng dụng mang tính thực tiễn của lý thuyết Bayes là thuật toán

phân lớp Naive Bayes. Bộ phân lớp Naive Bayes hoạt động theo các bước

1) Mỗi mẫu dữ liệu được biểu diễn bằng một vector đặc trưng n chiều,

X=(x1, x2, …, xn) tương ứng với n giá trị của n thuộc tính A1, A2, …, An .

2) Giả sử có m lớp C1, C2, …, Cm , lấy một mẫu dữ liệu X chưa biết

thuộc lớp nào. Thuật toán phân lớp sẽ dự đoán X thuộc về lớp có xác suất hậu

nghiệm cao nhất với điều kiện biết trước X. Đó là bộ phân lớp Naive Bayes

xếp một mẫu X vào lớp Ci nếu và chỉ nếu :

P(Ci|X) > P(Cj|X) với i ≠ j và 1 ≤ i , j ≤ m

(

)

XCP i

(

)

CXPCP ) ( ( XP

)

Như vậy, P(Ci|X) là cực đại, theo công thứ Bayes thì:

3) P(X) là không đổi với tất cả các lớp, vì vậy muốn P(Ci|X) cực đại thì

P(X|Ci) và P(Ci) cực đại. Nếu xác suất P(Ci) không biết thì thường cho xác

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

suất xuất hiện các lớp là như nhau P(C1) = P(C2)= … = P(Cm) và vì vậy

P(X|Ci)P(Ci). Xác suất P(C1) được ước lượng bằng công thức P(C1) = P(X|Ci) là cực đại. Ngược lại xác suất P(Ci) đã biết trước thì cực đại Si , S

trong đó Si là số mẫu trong tập dữ liệu học thuộc về lớp Ci, S là tổng số mẫu

4) Cho các tập dữ liệu với nhiều thuộc tính, thì rất tốn kém để tính

học.

P(X|Ci), để giảm tốn kém này, thuật toán phân lớp Naïve Bayes đưa ra giả

định “lớp độc lập có điều kiện”. Nó cho rằng giá trị của các thuộc tính độc lập

có điều kiện với nhau, không có sự phụ thuộc liên hệ giữa các thuộc tính, vì

P(x k

Ci)

vậy :

∏

k 1 =

P(X|Ci) =

Các xác suất P(x1|Ci), P(x2|Ci), …, P(xk|Ci) được ước lượng dựa vào

tập dữ liệu học. Trong đó:

S , Sik là số mẫu trong S

a) Nếu Ak có giá trị rời rạc, thì P(xk|Ci)=

tập dữ liệu học thuộc lớp Ci có giá trị thuộc tính Ak bằng xk và Si tổng

số mẫu học thuộc lớp Ci.

b) Nếu Ak có giá trị liên tục, thì thuộc tính được giả định có dạng

(

)

−

Ci µ− σ 2 2

CxP k

(

)

xg (

)

, σµ C C

1 2 σπ C

phân phối chuẩn Gaussian như sau:

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

kxg (

)

, σµ C C

Trong đó,

iCµ và

là hàm mật độ Gaussian cho thuộc iCσ lần lượt là kỳ vọng và phương sai các giá trị tính Ak, còn

của thuộc tính Ak của các mẫu học thuộc lớp Ci.

5) Để phân lớp cho một mẫu X, P(X|Ci)P(Ci) được ước lượng cho mỗi

lớp Ci. Mẫu X được xếp vào lớp Ci nếu và chỉ nếu:

i ≠ P(X|Ci)P(Ci) > P(X|Cj)P(Cj) với 1 ≤ j ≤ m, j

Nói cách khác X được xếp vào lớp Ci nếu P(X|Ci)P(Ci) cực đại.

2.2.3. Mạng Bayesian

Thuật toán phân lớp Naïve Bayes đưa ra giả định “lớp độc lập có điều

kiện”, nghĩa là giá trị của các thuộc tính độc lập với nhau, giả định này làm

đơn giản việc tính toán. Khi giả định này đúng thì bộ phân lớp Naïve Bayes

có độ chính xác cao nhất so với các bộ phân lớp khác (cây quyết định, mạng

neural,…). Tuy nhiên trong thực tế lại tồn tại sự phụ thuộc lẫn nhau của các

giá trị. Mạng Bayes chỉ rõ sự phân bố xác suất có điều kiện, nó cho phép “lớp

độc lập có điều kiện” định nghĩa giữa các tập con của các giá trị. Nó thiết lập

một đồ thị biểu diễn các mối liên hệ của các giá trị.

Mạng Bayesian được xác định bởi hai thành phần. Thành phần thứ nhất

là một đồ thị có hướng không chu trình, trong đó mỗi đỉnh biểu diễn cho một

biến ngẫu nhiên và mỗi cung biểu diễn một sự phụ thuộc xác suất. Nếu một

cung được vẽ từ đỉnh Y đến đỉnh Z, thì Y gọi là đỉnh cha hay đỉnh kề trước

của Z, còn Z gọi là đỉnh con của Y. Trên đồ thị, mỗi biến không phụ thuộc

vào điều kiện đỉnh con của nó, giá trị của các biến có thể là rời rạc hoặc liên

tục, nó tương ứng với các thuộc tính trong dữ liệu.

Thành phần thứ hai định nghĩa một mạng Bayesian bao gồm một bảng

xác suất có điều kiện cho mỗi biến. Bảng xác suất có điều kiện cho một biến

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

Z xác định rõ phân phối có điều kiện P(Z|Y), với Y là đỉnh cha của Z. Một ví

dụ đơn giản như sau:

Hình 2-2: Một ví dụ của mạng Bayesian

Xác suất chung của bất kỳ bộ dữ liệu (z1, …, zn) tương ứng với các biến

hay các thuộc tính Z1, …, Zn được tính bởi công thức:

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

i|Yi)

i 1 =

P(z1, …, zn) = ∏ P(z

Trong đó Yi là đỉnh cha của zi trong đồ thị mạng Bayesian và giá trị của

P(zi|Yi) tương ứng với các giá trị trong bảng xác suất có điều kiện của Zi.

Một node trong mạng Bayesian có thể được chọn là một node kết quả,

biểu diễn cho một thuộc tính phân lớp, có thể có nhiều hơn một node kết quả.

Những giải thuật suy diễn để học có thể áp dụng mạng Bayesian này. Quá

trình phân lớp hay nói đúng hơn là việc trả ra tên của một lớp, có thể trả ra

một phân phối xác suất cho thuộc tính phân lớp, tức là dự đoán xác suất cho

mỗi lớp.

2.2.4. Học (huấn luyện) trên mạng Bayesian

Trong việc học hay huấn luyện trên mạng Bayes, một số trường hợp có

khả năng học . Cấu trúc của mạng có thể được cho trước hoặc được suy luận

từ dữ liệu . Các biến trong mạng có thể thấy hoặc ẩn trong toàn bộ hoặc trong

một số mẫu học. Trường hợp dữ liệu ẩn được xem như là hay dữ liệu không

đầy đủ.

Nếu như cấu trúc mạng được biết trước và các biến nhìn thấy thì việc

học trên mạng là tường minh. Nó bao gồm việc tính toán các giá trị trong

bảng xác suất có điều kiện của các biến tương tự như việc tính các xác suất

trong thuật toán Beyesian (mục 2.2.2).

Khi cấu trúc mạng được cho trước và một số giá trị bị ẩn thì phương

pháp Gradient được sử dụng để huấn luyện mạng Bayesian. Một đối tượng

học những giá trị của bảng xác suất có điều kiện. Cho S là một tập gồm s mẫu

học X1,…,Xs gọi wijk là một giá trị trong bảng xác suất có điều kiện của biến

Yi bằng yij có đỉnh cha là Ui =uik. Wijk được xem như trọng số, trọng số này

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

được khởi tạo bằng giá trị xác suất ngẫu nhiên. Phương pháp giảm Gradient

thực hiện bằng thuật toán leo đồi tham lam (greedy hill-climbing), tại mỗi

bước lặp, trong số được cập nhật và cuối cùng tiến một giải pháp tối ưu cục

bộ. Mục đích của phương pháp này là làm cực đại xác suất P(S|H), điều này

được thực hiện bằng gradient của lnP(S|H) đã làm cho vấn đề trở nên đơn

giản hơn. Với cấu trúc mạng cho trước và giá trị wijk được khởi tạo, giải thuật

như sau:

)

( YP i

XuUyi =

∂

∑

ijk

, wi

( | HSP w ∂

1 =

YP ( i

)

XuUyi =

1) Tính gradients: với mỗi i, j, k tính :

Xác suất được tính cho mỗi mẫu học Xd lấy

YP ( i

)

XuUyi =

trong tập S. Khi các biến được biểu diễn bằng Yi và Ui là ẩn với một số mẫu

có thể được tính từ những Xd thì xác suất tương ứng

biến dễ dàng thấy của mẫu dữ liệu, sử dụng thuật giải suy diễn trên mạng

Bayesian.

2) Cập nhật trọng số trong giải thuật giảm gradient: các trọng số

)

∂

ijk

l )(

←

ijk

( w

HSP ∂

được cập nhật bởi công thức:

)

∂

Với (l) biểu diễn mức độ học (learning rate) biểu thị khích thước

HSP ( | ijkw ∂

được tính ở bước trước. Mức độ học được đặt là của bước. Và

một hằng số nhỏ.

ijk = 1.0 với mọi

3) Trung bình hóa lại trọng số: bởi vì những trọng số wijk là những

giá trị xác suất nên chúng nằm trong khoảng [0…1.0] và ∑ w

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

i, k. Những tiêu chuẩn này đạt được bằng cách trung bình hóa trọng số sau khi

cập nhật trọng số ở bước trên.

2.3. MẠNG NEURAL

Mạng neural ban đầu được đề cập bởi các nhà tâm lý học và sinh học,

họ đã cố gắng phát triển và mô phỏng mạng neural vào máy tính. Mạng neural

là một tập hợp các biến nhập /xuất liên kết với nhau, mỗi liên kết được kết

hợp với một trọng số. Một thuật giải học mạng neural phổ biến là giải thuật

lan truyền ngược. Trong quá trình học và phân tích, mạng học bằng cách điều

chỉnh trọng số để có thể dự đoán được lớp cho các mẫu đầu vào. Lợi thế của

mạng neural là nó có thể chấp nhận được dữ liệu có độ nhiễu cao và có thể

phân lớp cho các mẫu chưa được học. Ngoài ra, một số giải thuật đã và đang

được phát triển để rút trích những luật trong mạng neural, vì vậy mạng neural

được ứng dụng trong phân lớp khai thác dữ liệu.

2.3.1. Mạng lan truyền tiến đa tầng

Thuật giải lan truyền ngược trước tiên thực hiện việc học trên mạng lan

truyền tiến đa tầng. Ví dụ mạng lan truyền tiến hai tầng ở hình 2-3, các biến

nhập tương ứng với các thuộc tính của mỗi mẫu học. Các biến nhập được

chuyển đồng thời vào một tầng tạo thành tầng nhập, trọng số đầu ra của các

biến này được chuyển đồng thời vào tầng thứ hai giống như những neural, gọi

là tầng ẩn. Trọng số đầu ra của tầng ẩn này có thể là đầu vào của một tầng ẩn

khác và cứ tiếp tục như vậy. Số tầng ẩn là bất kỳ, tuy nhiên trong thực tiễn,

thường chỉ sử dụng một tầng ẩn. Trọng số đầu ra của tầng ẩn cuối cùng là đầu

vào của tầng xuất, tầng này đưa ra sự dự đoán các mẫu cho trước. Các đơn vị

(neural) trong các tầng ẩn được xem như các đơn vị đầu ra, mạng đa tầng ở

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

hình 2-3 có hai tầng chứa các đơn vị đầu ra vì vậy gọi nó là mạng hai tầng,

tương tự mạng chứa hai tầng ẩn gọi là mạng ba tầng, v.v…Gọi là mạng lan

truyền tiến vì trong mạng không có trọng số của một đơn vị nào quay lại làm

đầu vào hay đầu ra của một tầng trước.

Hình 2-3: Mạng lan truyền hai tầng

Mạng đa tầng lan truyền tiến là một hàm tuyến tính, các đơn vị ẩn được

đưa ra đủ để ước lượng một hàm bất kỳ.

2.3.2. Xây dựng cấu trúc mạng

Trước khi bắt đầu học (huấn luyện) mạng, người dùng phải quyết định

cấu trúc mạng bằng việc chỉ rõ số lượng biến đầu vào của tầng nhập, số lượng

tầng ẩn (có thể hơn một), số lượng neural (đơn vị) trong mỗi tầng ẩn và số

lượng neural trong tầng xuất.

Việc chuẩn hóa giá trị biến đầu vào cho mỗi giá trị thuộc tính trong tập

mẫu học sẽ làm tăng tốc độ học và phân tích. Điển hình, giá trị biến đầu vào

được chuẩn hóa sao cho rơi trong khoảng [0… 1.0]. Những thuộc tính có giá

trị rời rạc có thể được mã hóa sao cho chỉ có một đơn vị đầu vào cho mỗi

vùng giá trị. Ví dụ, nếu vùng giá trị của thuộc tính A là {a0, a1, a2} thì chúng

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

ta có thể cho ba đơn vị đầu vào đại diện cho thuộc tính A, gọi I0, I1, I2 là các

đơn vị đầu vào, mỗi đơn vị được khởi tạo bằng 0, nếu A = a0 thì I0=1, nếu A =

a1 thì I1=1, và tương tự như thế. Một đơn vị đầu ra có thể đại diện cho hai lớp

(giá trị bằng 0 đại diện cho một lớp, bằng 1 đại diện cho một lớp khác)

Không có quy tắc rõ ràng nào quy định số lượng tốt nhất các neural của

tầng ẩn. Xây dựng mạng là một sự thử nghiệm bởi quá trình xử lý sai số và

có thể ảnh hưởng đến độ chính xác của kết quả học trên mạng. Giá trị khởi tạo

của các trọng số có thể ảnh hưởng đến độ chính xác của kết quả. Mỗi lần,

mạng được học và kết quả của nó chưa thể chấp nhận được thì lặp lại quá

trình học với một cấu trúc mạng khác hoặc khởi tạo các trọng số với giá trị

khác.

2.3.3. Lan truyền ngược

Lan truyền ngược là quá trình xử lý tập các mẫu học được lặp đi lặp lại

nhiều lần, mỗi bước lặp so sánh các lớp mà mạng neural dự đoán cho mỗi

mẫu với các lớp chính xác của các mẫu. Với mỗi mẫu học, các trọng số được

điều chỉnh sao cho cực tiểu sai số trung bình-bình phương(phương sai) của

lớp được dự đoán và lớp thực sự. Sự điều chỉnh các trọng số này được thực

hiện ở bước quay ngược lại tức là bước từ tầng xuất quay ngược qua các tầng

ẩn đến tầng ẩn đầu tiên. Mặc dù không chắc chắn nhưng hầu hết các trọng số

đều hội tụ về một giá trị và quá trình học hết thúc. Thuật toán lan truyền

ngược gồm các bước như sau:

Khởi tạo các trọng số: Các trọng số trong mạng được khởi tạo giá trị

ngẫu nhiên trong khoảng từ -1.0 đến 1.0 hoặc từ -0.5 đến 0.5. Mỗi neural

được kết hợp với một định hướng (bias), giá trị định hướng này được khởi tạo

giống như các trọng số.

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

Với mỗi mẫu học X được xử lý theo các bước sau:

Lan truyền tiến các đầu vào: trong bước này, mạng đầu vào và đầu ra

của mỗi neural trong tầng ẩn và tầng xuất được tính toán. Đầu tiên mẫu học

được đưa vào tầng nhập của mạng. Mạng đầu vào cho mỗi neural trong các

tầng ẩn và tầng xuất được tính toán như là một ánh xạ của các biến đầu vào

(hình 2-4). Đầu vào của một neural là đầu ra của những neral ở tầng trước nối

đến nó. Để tính toán mạng đầu vào của neural thì mỗi đầu vào của nó được

cộng dồn bởi trọng số tương ứng. Cho một neural j ở trong tầng ẩn hay tầng

Ow ij

∑

xuất thì mạng đầu vào Ij của j là :

Trong đó wij là trọng số của liên kết từ neural i ở tấng trước đến neural

j, Oi là đầu ra của neural i từ tầng trước và jθ là định hướng của neural. Sự

định hướng này có tác dụng như là một ngưỡng, nó làm thay đổi cách hoạt

động của neural.

Mỗi neural ở trong tầng ẩn hay tầng xuất có một mạng đầu vào của nó

và áp dụng một hàm kích hoạt đến nó (hình 2-4), hàm này là hàm logistic

hoặc hàm simoid. Cho mạng đầu vào Ij của neural j thì đầu ra Oj của neural j

1 +

được tính như sau:

Hàm này được xem như là một hàm nén (squashing), vì nó ánh xạ một

miền đầu vào rộng lớn lên một vùng nhỏ hơn trong khoảng từ 0 đến 1. Hàm

logistic là một hàm không tuyến tính (phi tuyến) và có khả năng phân loại,

cho phép thuật giải lan truyền ngược mô hình theo bài toán phân lớp là tuyến

tính liên tục.

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

Hình 2-4 : Một neural trong tầng ẩn hoặc tầng xuất

Sai số lan truyền ngược: sai số được lan truyền ngược bởi quá trình

cập nhật trọng số và định hướng làm sai số trong việc dự đoán của mạng. Cho

neural j trong tầng xuất, sai số Errj được tính bởi:

Errj = Oj(1 - Oj)(Tj - Oj)

Với Oj là giá trị thực sự của đầu ra của neural j,và Tj là đầu ra đúng dựa

trên lớp đã biết của mẫu học được cho, Oj(1 - Oj) là đạo hàm của hàm logistic.

Để tính độ sai số của tầng ẩn với neural j, tổng các sai số của trọng số

của các neural trong tầng kế tiếp liên kết đến neural j được tính trước. Sai số

Err

)

Err

−

∑

của tầng ẩn với neural j là:

Trong đó wik là trọng số của liên kết từ neural j đến neural k trong tầng

kế tiếp, và Errk là sai số của neural k

Trọng số và định hướng được cập nhật đã làm sai số lan truyền. Trọng

số được cập nhật bởi công thức sau, với ∆wij là phần thay đổi trong trọng số

wij.

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

∆wij = (l)ErrjOj

wij = wij +∆wij

Biến l biểu thị khả năng học hay mức độ học, là một hằng số có giá trị

trong khoảng 0 và 1. Học lan truyền ngược sử dụng phương pháp giảm

gradient để kiếm ra một tập trọng số mà có thể mô hình hóa bài toán phân lớp

cho trước sao cho cực tiểu sai số bình phương-trung bình giữa lớp được mạng

dự đoán và lớp thực sự của mẫu học đã cho. Mức độ học ngăn không cho sa

lầy vào cực tiểu cục bộ trong không gian quyết định nghĩa là các trọng số xuất

hiện để hội tụ, nhưng nó không phải là giải pháp tốt nhất và đi tới khám phá

cực tiểu toàn cục. Nếu mức độ học quá nhỏ thì việc học tiến triển rất chậm.

Nếu mức độ học quá lớn thì các giải pháp không thỏa đáng. Một kinh nghiệm

là cho mức độ học l=t với t là số lần lặp đi lặp lại trên tập dữ liệu học cho tới

lúc này.

jθ∆ là phần thay

jθ .

Sự định hướng được cập nhật theo công thức sau, với

jErr

)(=∆θ j l

∆

j = θθ

∆+

j θ

đổi trọng

Điều kiện kết thúc: Quá trình học mạng được bắt đầu với các giá trị

trọng số tùy ý và tiến hành lặp đi lặp lại. Mỗi lần lặp được gọi là một thế hệ.

Trong mỗi thế hệ mạng điều chỉnh các trọng số sao cho sai số giảm dần và

quá trình học kết thúc khi:

+ Tất cả ∆wij ở thế hệ trước nhỏ hơn một ngưỡng xác định nào đó

hoặc

+ Tỷ lệ các mẫu bị phân lớp sai ở thế hệ trước nhỏ hơn một ngưỡng

nào đó hoặc

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

+ Lặp đủ số lượng thế hệ xác định trước.

Trong thực tế, có khi phải trải qua hàng trăm ngàn thế hệ thì các trọng

số mới có thể hội tụ. Tóm tắt thuật giải lan truyền ngược cho mạng neural học

để phân lớp được trình bày như sau:

Input: tập các mẫu học, mức độ học l, một mạng đa tầng

1) Khởi tạo tất cả các trọng số và định hướng trong mạng;

Output: một mạng neural đã được học để phân lớp cho các mẫu

2) While điều kiện kết thúc chưa thỏa {

3) for với mỗi mẫu X trong tập các mẫu học {

//lan truyền tiến các đầu vào

Ow ij

θ j

4) for với mỗi neural j của tầng ẩn hoặc tầng xuất

∑

5) ; // tính mạng đầu vào cho neural j

6) for với mỗi neural j của tầng ẩn hoặc tầng xuất

1 +

; //tính mạng đầu ra cho neural j 7)

//Sai số lan truyền ngược

8) for với mỗi neural j trong tầng xuất

9) Errj = Oj(1 - Oj)(Tj - Oj) ; //tính sai số

Err

10) for với mỗi neural j trong tầng ẩn

∑− ) O

11) ; //tính sai số

12) for với mỗi trọng số wij trong mạng {

13) ∆wij = (l)ErrjOj ; //độ tăng trọng số

14) wij = wij +∆wij; } //cập nhật trọng số

15) for với mỗi định hướng iθ trong mạng {

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

jErr

)(=∆θ l j

j j ∆+=∆ θθθ

16) ; //độ tăng định hướng

17) ; } //cập nhật định hướng

18) }

19) }

Bảng 2-3 : Thuật giải lan truyền ngược

2.4. SUPPORT VECTOR MACHINE (SVM)

2.4.1 Giới thiệu SVM

SVM là một phương pháp mới để phân lớp dữ liệu. Nó dễ sử dụng hơn

mạng neural, tuy nhiên nếu không sử dụng nó chính xác thì dễ bị bỏ qua một

số bước đơn giản nhưng cần thiết, dẫn đến kết quả không được thỏa mãn.

Mục đích của phương pháp SVM là phát sinh ra một mô hình từ tập mẫu học,

mô hình này có khả năng dự đoán lớp cho các mẫu thử. SVM tìm ra một hàm

quyết định phi tưyến trong tập mẫu học bằng cách ánh xạ hoàn toàn các mẫu

học vào một không gian đặc trưng kích thước lớn có thể phân lớp tuyến tính

và phân lớp dữ liệu trong không gian này bằng cách cực đại khoảng cách lề

(geometric margin) và cực tiểu lỗi học cùng một lúc. Vấn đề tối ưu chủ yếu

t ww

∑

min w ξ,

1 2

[ xwy

]

,...,1

1 −≥

≥

là:

, ξξ i i

phụ thuộc vào: n

1 tùy theo x Trong đó xi là mẫu học thứ i trong tập mẫu học, yi =

thuộc lớp nào, ở đây giả sử chỉ có hai lớp + và -, n là số lượng các mẫu học

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

trong tập mẫu học, C là một tham số điều chỉnh sự cân bằng giữa khoảng cách

iξ là lỗi học của mẫu thứ i.

lề và lỗi học,

(

)

−

α i

xKyy j

∑

max iα

1 2

αα i 1

0,0

, iC

,...,

≤

Vấn đề này tương ứng với một hàm kernel như sau:

∑

phụ thuộc vào: n

iα biểu thị sự phụ thuộc của mẫu thứ i vào giới hạn C, và K(xi, xj)

Với

là hàm kernel trong trường hợp phân lớp phi tuyến (không tuyến tính). Có

một số hàm kernel cơ bản sau đây:

T xj

+ Tuyến tính: K(xi, xj) = xi

T xj + r)d , γ >0

+ Đa thức: K(xi, xj) = (γxi

+ Hàm vòng RBF (Radial Basic Function) : K(xi, xj) = exp(-γ||xi - xj||2)

, γ>0

T xj + r)

+ Hàm chữ S Sigmoid: K(xi, xj) = tanh(γxi

2.4.2. RBF Kernel

Khi sử dụng SVM, ta cần phải chọn một hàm kernel và một tham số C.

Thông thường hàm RBF kernel được chọn đầu tiên vì nhiều lý do. Hàm phi

tuyến RBF kernel ánh xạ tập mẫu học vào một không gian có kích thước rộng

lớn, vì vậy nó không giống với hàm kernel tuyến tính, nó có thể áp dụng cho

trường hợp mối quan hệ giữa lớp và thuộc tính là phi tuyến. Hơn nữa hàm

~ C

kernel tuyến tính là một trường hợp đặc biệt của hàm RBF kernel nên hàm

γ). Ngoài ra hàm sigmoid kernel cũng thực hiện giống như

kernel tuyến tính với tham số sẽ thực hiện giống như hàm RBF kernel với

các tham số (C,

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

hàm RBF kernel với một tham số đích xác. Lý do thứ hai là số lượng siêu

tham số (siêu biến) tức là tham số ảnh hưởng đến độ phức tạp của mô hình

được chọn lựa. Hàm kernel đa thức có nhiều siêu biến hơn hàm RBF kernel.

≤

Cuối cùng là hàm RBF kernel có độ phức tạp ít hơn. Một điểm quan trọng là:

0 < Kij

T xj + r >1) và bằng không với (γxi

γxi

định, vô cực với ( 1, điều này trái ngược với hàm kernel đa thức có giá trị không xác T xj + r<1) khi độ đo d

lớn. Ngoài ra phải chú ý rằng hàm kernel không thể tính phải tích vô hướng

của hai vector.

2.4.3. Tối ưu tham số

Có hai tham số khi sử dụng hàm RBF kernel là C và γ. C và γ là tốt

nhất hay tối ưu cho mỗi bài toán thì chưa được biết trước, vì vậy phải tìm

kiếm các tham số tối ưu này. Mục đích là nhận ra (C, γ) tốt nhất để mà bộ

phân lớp có thể dự đoán chính xác lớp cho các mẫu chưa biết. Chú ý rằng nó

có thể không hữu ích để đạt được độ chính xác học cao, nghĩa là bộ phân lớp

dự đoán chính xác những mẫu dữ liệu học đã biết lớp trước. Vì vậy một cách

thông thường là chia tập mẫu dữ liệu học thành hai phần, một phần được xem

như không biết trong quá trình học của bộ phân lớp. Sau đó, sự dự đoán chính

xác trên phần này có thể chính xác hơn tương ứng với việc thực hiện phân lớp

trên dữ liệu chưa biết. Một phiên bản cải tiến của thủ tục này là “giao hiệu

suất” (cross - validation).

Trong v-nhóm cross-validation, đầu tiên chia tập mẫu học thành v tập

con bằng nhau. Lần lượt mỗi tập con sẽ được thử với bộ phân lớp được học

trên v-1 tập con còn lại. Theo cách đó, mỗi mẫu trong tập các mẫu học được

dự đoán một lần, như vậy độ chính xác cros-validation là tỷ lệ phần trăm các

mẫu dữ liệu được phân lớp chính xác.

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

a) dữ liệu học và bộ phân lớp quá khít b) áp dụng bộ phân lớp quá khít

trên dữ liệu thử

c) dữ liệu học và bộ phân lớp tốt hơn d) áp dụng bộ phân lớp tốt hơn

trên dữ liệu thử

Hình 2-5 : Bộ phân lớp quá khít và bộ phân lớp tốt hơn

MỘT SỐ THUẬT TOÁN PHÂN LỚP PHỔ BIẾN

Thủ tục cross-validation có thể ngăn ngừa vấn đề quá khớp

(overfitting). Ví dụ ở hình 2-5 minh họa bài toán phân lớp nhị phân (hình tam

giác và hình tròn), hình tam giác và hình tròn tô đen là dữ liệu học, hình tam

giác và hình tròn trắng là dữ liệu thử. Độ chính xác trên các mẫu thử mà bộ

phân lớp dự đoán ở hình 2-5 a) và b) là chưa thỏa mãn vì nó quá trên khít dữ

liệu học. Một hướng khác, bộ phân lớp ở hình 2-5 c) và d) không quá khớp

trên dữ liệu học đưa ra cross-validation tốt hơn cũng như độ chính xác của các

mẫu thử cao hơn.

Một lưới tìm kiếm (grid search) trên C và γ sử dụng cross-validation

được dùng, về cơ bản các cặp (C, γ) đã được thử và một trong số chúng đã

làm cho cross-validation tối ưu, và cặp (C, γ) này được chọn lọc. Chúng ta

thấy rằng nếu C và γ là dẫy tăng số mũ là một phương pháp tốt để tạo ra

tham số tốt, ví dụ C=2-5, 2-3, …, 215, γ= 2-15, 2-13 ,…, 23.

Trong một số trường hợp phương pháp SVM thì bất lợi và kết quả khó

chấp nhận. Thông thường phương pháp SVM phân lớp tốt với dữ liệu không

có nhiều thuộc tính, nếu gặp phải dữ liệu có hàng ngàn thuộc tính thì phải

chọn ra nhóm thuộc tính với số lượng vừa phải để áp dụng cho SVM.

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

CHƯƠNG 3

THUẬT TOÁN PHÂN LỚP

ĐIỀU CHỈNH SỰ QUÁ KHỚP

VÀ QUÁ KHÁI QUÁT

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

3.1. GIỚI THIỆU

Hầu hết các thuật toán phân lớp đều tập trung vào việc học quy nạp để

làm giảm thiểu lỗi phân lớp cho tập mẫu học. Theo cách này, các thuật toán

phân lớp hy vọng sẽ có một độ chính xác cao trong việc dự đoán lớp cho các

mẫu dữ liệu mới cần được xác định lớp. Vì vậy chúng dễ mắc phải vấn đề quá

khớp hoặc quá khái quát dữ liệu.

Các thuật toán cây quyết định như ID3, C4.5 đã có kết quả tốt đối với

những tập dữ liệu tương đối nhỏ. Nhưng khi áp dụng cho các cơ sở dữ liệu

lớn hoặc cơ sở dữ liệu của thế giới thực thì chúng gặp phải những hạn chế.

Hạn chế đầu tiên là tất cả các mẫu học phải được lưu trong bộ nhớ, nhưng

trong lĩnh vực khai thác dữ liệu, các tập mẫu học chứa hàng triệu mẫu rất phổ

biến. Vì vậy phải chuyển đổi các mẫu học giữa bộ nhớ chính và bộ nhớ cache

với bô nhớ phụ. Hoặc phải chia tập mẫu học thành các tập con và xây dựng

từng cây quyết định cho mỗi tập con. Bộ phân lớp của từng cây quyết định sẽ

được kết hợp lại nên hiệu quả của cây quyết định sẽ không còn cao như đối

với tập mẫu nhỏ. Hạn chế thứ hai, cây quyết mang tính quá khớp dữ liệu, vì

trong khi xây dựng cây quyết định, tại bước đặt tên lớp cho node lá nếu tất cả

các node thuộc cùng một lớp thì node lá được đặt tên là lớp đó. Ngược lại đã

hết thuộc tính thử và các mẫu không thuộc cùng một lớp thì node lá được đặt

tên là lớp mà nhiều mẫu thuộc về nhất. Như vậy, lớp này đúng với dữ liệu học

nhưng khi dự đoán cho các mẫu mới thì chưa chắc đã chính xác.

Đối với mạng neural, tiêu biểu là thuật giải lan truyền ngược, mục đích

của thuật giải không phải là nhớ tất cả các mẫu học mà xây dựng một mạng

đa tầng để phân lớp cho các mẫu mới. Trong mạng đa tầng có rất nhiều trọng

số, việc học quá nhiều trên các tầng ẩn của mạng có thể dẫn đến mất sự khái

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

quát hóa dữ liệu, vì mạng thực hiện một đường biên phân lớp phức tạp cho

những mẫu học đặc biệt mà không chú ý đến những thuộc tính chung.

Sau đây là một phương pháp phân lớp dựa trên sự điều chỉnh để tránh

được sự quá khớp dữ liệu đồng thời cũng tránh được sự quá khái quát dữ liệu,

phương pháp này được thầy Phạm Nguyễn Anh Huy đề xuất. Phương pháp

này thực hiện bằng cách cân bằng hai tính chất quá khớp và quá khái quát dữ

liệu trên tập mẫu học được cho. Theo phương pháp này, mỗi mẫu được xem

như một điểm trong không gian n chiều, với n là số thuộc tính của mẫu dữ

liệu. Một lớp được đại diện bằng một số vùng chứa các mẫu thuộc cùng một

lớp trong không gian n chiều này. Để tránh khỏi sự quá khớp và quá khái quát

thì độ lớn của các vùng này không được quá nhỏ cũng không quá lớn mà phụ

thuộc vào mật độ của các mẫu học chứa trong nó. Sau khi đã xác định được

các vùng này, muốn phân lớp cho một mẫu mới thì dựa vào vị trí của mẫu này

trong không gian n chiều, nếu mẫu này thuộc vào một trong các vùng vừa

được xác định thì nó thuộc cùng một lớp với các mẫu trong vùng đó.

3.2. MỘT SỐ ĐỊNH NGHĨA

Phần này sẽ định nghĩa cho một số thuật ngữ được dùng trong thuật

toán phân lớp điều chỉnh sự quá khớp và quá khái quát (quá rộng), đồng thời

trình bày ý tưởng của thuật toán này. Đây là cơ sở cho sự nghiên cứu và phát

triển bài toán phân lớp điều chỉnh hai tính chất nói trên.

3.2.1 Homogenous Clauses

Cho một tập dữ liệu, gồm nhiều mẫu mà mỗi mẫu chỉ thuộc về một

trong hai lớp, giả sử hai lớp này là positive và negative. Ánh xạ toàn bộ tập

mẫu này vào không gian n chiều, với n là số thuộc tính của tập dữ liệu, mỗi

mẫu được xem như một điểm trong không gian. Vị trí của một mẫu trong

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

không gian này được xác định bởi giá trị các thuộc tính của nó. Ví dụ, trong

không gian hai chiều, vị trí của một mẫu được xác định bởi tọa độ x và y, x

tương ứng với giá trị thuộc tính thứ nhất, y tương ứng với giá trị thuộc tính

thứ hai. Homogenous Clauses là các vùng trong không gian này, sao cho mỗi

vùng chỉ chứa các mẫu thuộc cùng một lớp positive hoặc negative, các mẫu

này phải tập trung đều và không thể chia nhỏ vùng này ra được. Các

Homogenous Clauses được xác định bởi tập dữ liệu học, sau đó sử dụng

chúng để phân lớp cho các mẫu dữ liệu mới. Một mẫu dữ liệu mới được phân

lớp bẳng cách xét xem vị trí của nó trong khong gian có thuộc một trong các

Homogenous Clauses hay không.

Ví dụ, hình 3-1 sau đây minh họa định nghĩa về Homogenous Clauses,

giả sử các mẫu chỉ có hai thuộc tính nên được biểu diễn trên mặt phẳng hai

chiều X-Y. Trong hình này, vùng A không phải là Homogenous Clause còn

vùng B là một Homogenous Clause. Ví dụ này chỉ chứa các mẫu thuộc cùng

một lớp, được biểu thị là những hình tròn nhỏ.

Hình 3-1: Minh họa định nghĩa Homogenous Clauses

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Vùng B là một Homogenous Clause vì các mẫu chứa trong nó là đồng

nhất và phân bố đều. Như vậy, những mẫu chưa được phân lớp mà chứa trong

không gian B có khả năng được xác định chính xác lớp mà nó thuộc về, đó là

lớp của các mẫu được biểu thị bằng các hình tròn nhỏ trong vùng B của hình

3-1 ở trên.

Vùng A ở hình trên không phải là một Homogenous Clause, bởi vì các

điểm trong vùng A phân bố không đều, vẫn còn vùng trống trong không gian

này. Vùng trống này nằm ở góc trái trên và phía dưới của vùng A. Vùng A có

thể được chia thành những vùng nhỏ hơn sao cho các điểm trong đó đồng nhất

và phân bố đều, xem hình sau:

Hình 3-2: Vùng A được thay thế bằng hai Homogenous Clauses A1 và A2

Việc phân lớp dựa vào các Homogenous Clauses có thể đạt được độ

chính xác cao, nếu các mẫu dữ liệu chứa trong chúng đồng nhất và phân bố

đều. Trong hình 3-2 ở trên, vùng A được thay thế bằng hai vùng nhỏ hơn

nhưng các điểm chứa trong chúng thì đồng nhất hơn, gọi là A1 và A2. Hai

vùng này là hai Homogenous Clauses. Trong vùng A1 và A2, các điểm đồng

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

nhất và phân bố đều hơn các điểm trong vùng A ban đầu. Vùng A1 và vùng

A2 bây giờ không còn những khoảng trống.

3.2.2. Mật độ của một Homogenous Clause

Mật độ là số lượng những vật chứa trong một diện tích không gian. Mật

độ nói lên mức độ nhiều và khoảng cách sát nhau của các vật trong một không

gian chứa chúng. Tương tự như vậy đối với Homogenous Clause, mật độ của

một Homogenous Clause là tỷ lệ giữa số lượng mẫu dữ liệu chứa trong nó với

diện tích không gian của nó. Mật độ của một Homogenous Clause quyết định

Homogenous Clause đó sẽ được mở rộng như thế nào. Nếu một Homogenous

Clause có mật độ cao thì vùng mở rộng của nó sẽ lớn, ngược lại thì vùng mở

rộng của nó nhỏ hơn. Trong ứng dụng ta cho Homogenous Clause là hình tròn

đối với các mẫu dữ liệu hai chiều, và là hình cầu nếu các mẫu dữ liệu có nhiều

chiều (n chiều). Và mật độ của một Homogenous Clause là số mẫu dữ liệu có

trong Homogenous Clause này. Trong minh họa của hình 3-2 thì các

Homogenous Clauses A1, A2 và B có mật độ lần lượt là 4, 7 và 10.

3.3. CHI TIẾT THUẬT TOÁN

Phần này sẽ trình bày chi tiết thuật toán điều chỉnh sự quá khớp và quá

khái quát dữ liệu. Thuật toán này sử dụng những ý tưởng được trình bày ờ

phần 3.2 làm cơ sở cho thuật toán xác định và mở rộng các Homogenous

Clauses. Phần này được chia thành hai phần nhỏ: phần một trình bày thuật

toán chính cho quá trình xác định mở rộng các Homogenous Clauses, phần

hai sẽ trình bày một số thuật toán hỗ trợ cho thuật toán chính mở rộng các

Homogenous Clauses này. Trong đề tài này chỉ nghiên cứu bài toán phân lớp

nhị phân nên các mẫu dữ liệu chỉ thuộc một trong hai lớp positive và

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

negative. Giả thiết các Homogenous Clauses chỉ chứa các mẫu thuộc lớp

positive.

3.3.1. Thuật toán chính

Đây là thuật toán học, mục đích của thuật toán này là xác định các

Homogenous Clauses của tập dữ liệu học, sau đó dựa vào mật độ của từng

Homogenous Clause mà mở rộng nó với kích thước lớn hay nhỏ tùy thuộc độ

lớn của mật độ. Tóm tắt thuật toán này như sau:

Input: tập dữ liệu học

Output: một sự phân lớp phù hợp (tức là các Homogenous Clauses đã được

mở rộng dùng để dự đoán lớp cho các mẫu mới)

Bước 1: Tìm các Positive Clauses

Bước 2: For với mỗi Positive Clauses P Do

Tìm các Homogenous clauses

Bước 3: For với mỗi Homogenous Clauses C Do

+ Tìm mật độ của C, gọi là D

+ Mở rộng C dựa trên mật độ D của nó

Bảng 3-1: Thuật toán chính

Theo thuật toán này, bước 1 tìm các Positive Clauses, một Positive

Clause là một vùng chứa các mẫu thuộc lớp positive, các mẫu này có thể phân

bố không đều và trong Positive Clauses còn chứa các khoảng trống. Trong

ứng dụng, Positive Clause được xem là hình chữ nhật đối với dữ liệu có hai

thuộc tính và là hình hộp đối với dữ liệu có n thuộc tính (n>2). Giả sử, cho

một tập dữ liệu hai chiều (nghĩa là mỗi mẫu có hai thuộc tính), gồm các mẫu

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

đã được phân lớp như sau, mẫu dấu “+” thuộc lớp positve, mẫu dấu “-” thuộc

lớp negative. Dựa vào giá trị hai thuộc tính của các mẫu ta được sự phân bố

của chúng trên mặt phẳng, chiều ngang đại diện cho thuộc tính thứ nhất, chiều

dọc đại diện cho thuộc tính thứ hai, ta có hình minh họa như sau:

Hình 3-3: Một tập mẫu học hai chiều

Sau bước 1 tìm các Positive Clauses, có được hai Positive Clauses được

biễu diễn bằng hai hình chữ nhật như sau:

Hình 3-4 : Các Positive Clauses tìm được ở bước 1

Mục đích của việc tìm các Positive Clauses là gom các điểm thuộc lớp

positive thành các nhóm dựa vào sự phân bố của chúng trong không gian dữ

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

liệu. Trong thực tế, các đối tượng thuộc cùng một lớp thường có một số thuộc

tính tương tự nhau, vì vậy chúng thường gom thành từng nhóm trong không

gian biểu diễn cho tập dữ liệu. Việc tìm các Positve Clauses đã thu hẹp không

gian dữ liệu chứa các đối tượng cần quan tâm, nghĩa là xác định được các

vùng mà các điểm positive có thể xuất hiện, các điểm positive không thể nằm

ngoài các vùng này được. Nếu thuật toán dừng ở đây thì sẽ mắc phải vấn đề

quá khái quát dữ liệu. Nghĩa là nếu dùng các Positive Clauses để dự đoán lớp

cho các mẫu dữ liệu mới thì xảy ra hiện tượng, dự đoán chính xác cho các

mẫu positive nhưng cũng có nhiều mẫu negative bị dự đoán thành positive.

Vì vậy, phải thực hiện một bước tiếp theo là tìm các Homogenous

Clauses, tức là tìm các vùng chỉ chứa các điểm positive mà trong đó các điểm

này phân bố đều và sát nhau. Nếu một điểm positive không nằm gần bất kỳ

một điểm positive khác thì Homogenous Clause chứa điểm này chỉ có duy

nhất một điểm positive. Do đó mỗi Homogenous Clause phải hoàn toàn nằm

trong một Positive Clause. Một Positive Clause có thể chứa một hoặc nhiều

Homogenous Clauses. Ví dụ, tìm các Homogenous Clauses cho hai Positive

Clauses trong hình 3-4 ở trên, các Homogenous Clauses được biểu diễn bằng

các hình tròn.

Hình 3-5: Các Homogenous Clauses tìm được ở bước 2

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Nhưng nếu sử dụng các Homogenous Clauses vừa tìm được ở bước 2

để phân lớp cho các mẫu mới thì thuật toán rơi vào trường hợp quá khớp dữ

liệu. Bởi vì các điểm positive chứa trong các Homogenous Clauses này phân

bố quá sát nhau, hay nói cách khác các Homogenous Clauses này quá hẹp chỉ

chứa chính xác các điểm positive trong tập mẫu học mà không có khả năng

chứa thêm các điểm positive mới chưa được học.

Như vậy, cần phải có một bước hiệu chỉnh tính quá khớp dữ liệu của

các Homogenous Clauses sao cho cũng không mắc phải tính quá khái quát dữ

liệu như ở bước 1. Bước này thực hiện bằng cách mở rộng các Homogenous

Clauses dựa vào mật độ của chúng. Các Homogenous Clauses sau khi được

mở rộng là những hình đồng dạng với các Homogenous Clauses ban đầu và

tâm của chúng thì không thay đổi chỉ có kích thước bán kính được tăng lên.

Mật độ của một Homogenous Clause càng lớn thì kích thước bán kính tăng

càng nhiều. Ví dụ, mở rộng các Homogenous Clauses trong hình 3-5 ở trên,

được kết quả như sau:

Hình 3-6: Các Homogenous Clauses được mở rộng ở bước 3

Các Homogenous Clauses sau khi được mở rộng là kết quả cuối cùng

của thuật toán phân lớp điều chỉnh sự quá khớp và quá khai quát dữ liệu. Việc

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

sử dụng các Homogenous Clauses này để phân lớp cho các tẫp dữ liệu mới

hay các tập dữ liệu trong tương lai có thể đạt kết quả cao. Bởi vì các

Homogenous Clauses này đã giảm được tính quá khớp dữ liệu của các

Homogenous Clauses trước khi mở rộng và cũng giảm được tính quá khái

quát dữ liệu của các Positive Clauses. Chi tiết từng bước sẽ được trình bày

trong phần tiếp theo sau.

3.3.2. Các thuật toán hỗ trợ

3.3.2.1. Thuật toán tìm các Positive Clauses

Thuật toán tìm các Positive Clauses được tóm tắt như sau:

Input: tập dữ liệu học, gồm các mẫu positive và các mẫu negetive

Output: các Positive Clauses

1) Xác định một ngưỡng khoảng cách Threshold.

2) Chọn ngẫu nhiên N mẫu positive.

3) For i=1 to N Do{

4) Chọn ngẫu nhiên một mẫu positive m trong tập dữ liệu học

5) If mẫu m chưa thuộc vào một Positive Clauses nào then{

6) Tạo ra một Positive Clause K

7) For với mỗi mẫu j của tập dữ liệu học Do{

8) If mẫu j là positve và j chưa thuộc Positive Clause nào Then{

9) Tính khoảng cách DC cách từ m đến j

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

10) If DC < Threshold Then{

11) Cho j vào Positive Clause K

12) Đánh dấu j đã thuộc vào một Positive Clause

13) } } }

14) Tăng K lên một

15) } }

//Duyệt lại xem còn mẫu positive nào chưa thuộc bất kỳ một Positive

Clauses nào

16) For với mỗi mẫu i của tập dữ liệu học Do{

17) If i là positive và i chưa thuộc bất kỳ Positive Clauses Then{

18) Tạo ra một Positive Clause K

29) For với mỗi mẫu j của tập dữ liệu học Do{

20) If j là positive và j chưa thuộc một Positive Clauses Then{

21) Tính khoảng cách DC từ i đến j

22) If DC < Threshold Then{

23) Cho j vào Positive Clause K

24) Đánh dấu j đã thuộc vào một Positive Clause

25) } } }

26) Tăng K lên một

27) } }

Bảng 3-2: Thuật toán tìm các Positive ClausesThuật toán chính

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Theo thuật toán này, tìm được K Positive Clauses. Ban đầu phải chọn

một ngưỡng khoảng cách, khoảng cách từ tâm của một Positive Clause đến tất

cả các điểm trong nó phải nhỏ hơn ngưỡng khoảng cách này. Tiếp theo, chọn

ngẫu nhiên N mẫu positive, các mẫu này được dùng làm tâm cho các Positive

Clauses. Với mỗi mẫu trong N mẫu positive được chọn làm tâm cho mỗi

Positive Clause, xét tất cả các mẫu positive trong tập dữ liệu, nếu mẫu nào có

khoảng cách đến tâm nhỏ hơn một ngưỡng khoảng cách cho trước thì xét nó

thuộc Positive Clauses chứa tâm đó. Mỗi mẫu positive chỉ thuộc vào duy nhất

một Positive Clause. Sau khi xét hết N mẫu làm tâm cho Positive Clauses mà

vẫn còn mẫu positive trong tập dữ liệu chưa thuộc vào bất kỳ một Positive

Clauses thì chọn chính mẫu đó làm tâm cho một Positive Clause mới và xác

định các mẫu thuộc Positive Clause này. Tương tự như vậy cho đến khi tất cả

các mẫu positive đều thuộc về một trong các Positive Clauses. Hình 3-7, cùng

một tập dữ liệu với hai ngưỡng khoảng cách khác nhau thì kết quả tìm được

các Positive Clauses cũng khác nhau.

Hình 3-7: Một ví dụ Positive Clauses với hai ngưỡng khoảng cách

3.3.2.2. Thuật toán tìm các Homogenous Clauses

Sau khi tìm được tất cả các Positive Clauses cho tập dữ liệu học, tiếp

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

tục tìm các Homogenous Clauses cho mỗi Positive Clause. Thuật toán tìm tất

cả các Homogenous clauses cho mỗi Positive Clause như sau:

Input: Positive Clause C

Output: Các homogenous Clauses có trong C

1) Chọn ngẫu nhiên N mẫu positive trong C.

2) For với mỗi mẫu positive X vừa mới được chọn Do{

3) If X chưa thuộc bất kỳ Homogenous Clauses nào Then{

4) Đặt một ngưỡng H = khoảng cách nhỏ nhất giữa hai mẫu positive

5) Do{

6) Tạo một vùng E với tâm là X và bán kính là H

7) If E nằm hoàn toàn trong C Then H = H*2

8) Else thoát khỏi vòng lặp

9) }While (true)

10) } }

//Duyệt lại dữ liệu xem còn mẫu nào chưa thuộc Homogenous Clauses

11) For với mỗi mẫu i trong C Do{

12) If i chưa thuộc Homogenous Clauses nào Then {

13) Đặt X = mẫu i và quay lại bước 2)

14) } }

Bảng 3-3: Thuật toán tìm các Homogenous Clauses

cho mỗi Positive Clauses

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Theo thuật toán này, mỗi Positive Clause được phân ra thành các

Homogenous Clauses, bằng cách sử dụng một khoảng cách cực tiểu, H, giữa

hai mẫu positve trong tập dữ liệu, để khởi tạo một vùng ban đầu của

Homogenous Clause. Nếu những vùng này không đụng vào biên của Positive

Clause chứa chúng thì chúng được mở rộng với bán kính gấp đôi, H*2, và cứ

tiếp tục như vậy. Quá trình mở rộng các vùng này chỉ dừng khi một trong các

Homogenous Clause đụng vào biên của Positive Clause chứa chúng. Nếu

ngay trong lần mở rộng đầu tiên mà Homogenous Clause đụng vào biên của

Positive Clause chứa nó thì Homogenous Clause này chỉ chứa duy nhất một

mẫu positive. Ví dụ, tìm các Homogenous Clauses cho mỗi Positive Clauses

trong ví dụ ở trên.

Hình 3-8: Các Homogenous Clauses cho mỗi Positive Clauses

3.3.2.3. Thuật toán mở rộng Homogenous Clause

Một Homogenous Clauses được mở rộng bằng cách giữ nguyên tâm và

tăng bán kính dựa vào mật độ của nó. Công thức tăng bán kính cho mỗi

Homogenous Clauses như sau:

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

− 2

1 D

Trong đó: + RC là bán kính của Homogenous Clause C ban đầu.

+ RF là bán kính của Homogenous Clause sau khi được mở

rộng F.

+ RG là bán kính của không gian G bao phủ C, không gian G

là một hình đồng dạng với Homogenous Clause C và có

bán kính gấp đôi bán kính của C.

+ D là mật độ của C.

Việc tăng bán kính của một Homogenous Clauses C được thực hiện

như sau: Ban đầu xác định một vùng G là một hình đồng dạng với

Homogenous Clause C và có bán kính gấp đôi bán kính của C. RC được tăng

lên trong khoảng từ RC đến RG, mỗi lần tăng một khoảng = RF - RC, sau mỗi

lần tăng RC được gán bằng RF, quá trình tăng bán kính dừng khi Homogenous

Clause F chứa điểm negative hoặc diện tích của F lớn hơn D* hệ số hoặc

RF>RG. Hệ số này là mức độ mở rộng của Homogenous Clauses, mặc định hệ

số này bằng một. Trước khi dừng cần kiểm tra, nếu RC=RG thì tiếp tục mở

rộng một lần nữa với mật độ D phải tính lại theo Homogenous Clauses C mới

và RG = RG*2.

Chi tiết thuật toán mở rộng một Homogenous Clause C dựa trên mật độ

D của nó, được mô tả như sau:

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Input: Homogenous Clause C và mật độ D của nó

Output: Homogenous Clause sau khi mở rộng F

Bước 1: Tìm không gian G bao phủ C, với bán kính gấp đôi bán kính của C.

G phải cùng hình dạng với C và có trọng tâm là trọng tâm của C.

− 2

1 D

Bước 2: Mở rộng C dựa vào D và G theo công thức

Bước 3: Dừng, nếu F chứa bất kỳ mẫu negative nào hoặc diện tích của F >

hệ số*D hoặc bán kính của F > bán kính của G. Ngược lại gán bán kính của

C = bán kính của F và quay lại bước 2.

Bước 4: Nếu bán kính RC=RG thì quay lại bước 1, ngược lại thì tiếp tục thực

hiện bước 5

Bước 5: Trả về C, nếu F chứa bất kỳ mẫu negative nào hoặc diện tích của F

> hệ số*D

Bảng 3-4: Thuật toán mở rộng Homogenous Clause C

Hình 3-9 sau đây minh học cho việc mở rộng các Homogenous

Clauses, hình a) là các Homogenous Clauses trước khi được mở rộng, hình b)

là các Homogenous Clauses được mở rộng với hệ số bằng 2, hình c) là các

Homogenous Clauses được mở rộng với hệ số bằng 5.

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Hình 3-9: Các Homogenous Clauses sau khi được mở rộng

3.3.2.4. Thuật toán gom các Homogenous Clauses

Các homogenous Clauses sau khi được xác định cho mỗi Positive

Clauses hay sau khi được mở rộng, thường sẽ gặp phải trường hợp một

Homogenous Clause chứa trong một Homogenous Clauses khác và một

Homogeous Clause chứa các mẫu, nhưng toàn bộ các mẫu này đã chứa trong

các Homogenous Clauses khác. Vì vậy cần loại bỏ các Homogenous Clauses

không cần thiết này để nâng cao tốc độ tính toán cũng như giảm dung lương

bộ nhớ phải lưu trữ chúng.

Thuật toán gom các Homogenous Clauses như sau:

THUẬT TOÁN PHÂN LỚP ĐIỀU CHỈNH SỰ QUÁ KHỚP VÀ QUÁ KHÁI QUÁT

Input: Tập các Homogenous Clauses

Output: Tập các Homogenous Clauses đã được gom

Bước 1: Kiểm tra xem có Homogenous Clause nào nằm trong một

Homogenous Clause khác thì hủy nó.

Bước 2: For với mỗi Homogenous Clauses C Do

Nếu tất cả các mẫu trong C đã thuộc vào các Homogenous

Clauses khác thì hủy C.

Bước 3: Return tập Homogenous Clauses còn lại sau khi hủy

Bảng 3-5: Thuật toán gom các Homogenous Clauses

Minh họa sau cho thấy việc gom các Homogenous clauses, hình bên

trái là các Homogenous Clauses trước khi gom, hình bên phải là các

Homogenous sau khi gom.

Hình 3-10: Minh họa việc gom các Homogenous Clauses

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

CHƯƠNG 4

CÀI ĐẶT THUẬT TOÁN

VÀ ÁP DỤNG CHO BÀI

TOÁN PROTEIN FOLDING

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

4.1. CÀI ĐẶT THUẬT TOÁN

4.1.1. Chương trình Demo trên không gian hai chiều

Dựa trên thuật toán điều chỉnh sự quá khớp và quá khái quát dữ liệu

trên mặt phẳng hai chiều, chương trình demo đã được cài đặt bằng ngôn ngữ

Java, công nghệ Applet trên môi trường JBuider8. Sau khi được biên dịch

chương trình có thể chạy trực tiếp bằng trình duyệt Internet Explorer, giao

diện như sau:

Hình 4-1: Giao diện chương trình Demo

Trên giao diện này, bao gồm các thành phần như sau:

+ Textbox Threshold : nhập giá trị ngưỡng khoảng cách sử dụng

trong thuật toán tìm các Positive Clauses.

+ Textbox Coefficient : nhập giá trị cho hệ số sử dụng ở thuật toán

mở rộng Homogenous Clauses.

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

+ Button Positive Clauses: tìm các Positive Clauses.

+ Button Homogenous: tìm các Homogenous Clauses.

+ Button Expand: mở rộng các Homogenous Clauses.

+ Tọa độ ở góc trái thanh Status: vị trí con trỏ chuột trên màn hình,

gốc tọa độ (0,0) là góc trái dưới của nàm hình.

Trong mặt phẳng hai chiều của giao diện này:

+ Chiều ngang biểu diễn giá trị thuộc tính thứ nhất.

+ Chiều dọc biểu diễn cho giá trị thuộc tính thứ hai.

+ Mỗi ô vuông nhỏ sẽ đại diện cho một mẫu.

Chương trình này sử dụng minh họa cho thuật toán, để đơn giản chỉ xét

trường hợp giá trị thuộc tính nguyên dương, giá trị nhỏ nhất là 0 được tính từ

góc trái dưới của màn hình. Thông tin mỗi mẫu gồm có giá trị hai thuộc tính

và một lớp mà mẫu này thuộc về, giả sử lớp positive hoặc negative. Cách

nhập dữ liệu cho chương trình như sau:

+ Di chuyển con trỏ chuột trên giao diện sao cho con số ở góc trái dưới

của giao diện hiển thị đúng với giá trị hai thuộc tính của mẫu.

+ Click trái chuột: đặt một mẫu positive tại vị trí con trỏ chuột, biểu thị

bằng dấu “+“.

+ Click phải chuột: đặt một mẫu negative tại vị trí con trỏ chuột, biểu

thị bằng dấu “-“.

Sau khi đã nhập thông tin của tất cả các mẫu cho chương trình thực

hiện lần lượt các bước sau:

+ Click button Positive Clauses: kết quả là các Positive Clauses được

biểu thị bằng các hình chữ nhật.

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

+ Click button Homogenous: kết quả là các Homogenous Clauses

cho mỗi Positive Clauses, được biểu thị bằng các hình tròn bên trong hình chữ

nhật.

+ Click button Expand: kết quả là các Homogenous Clauses đã được

mở rộng.

Kết quả có được là các Homogenous Clauses đã được mở rộng, biểu thị

là các hình tròn màu đỏ. Từ đây, muốn dự đoán lớp cho một mẫu mới, ta chỉ

việc di chuyển con trỏ chuột trên màn hình giao diện tương tự như khi nhập

dữ liệu, sao cho con số ở góc trái dưới màn hình bằng với giá trị hai thuộc

tính của mẫu cần dự đoán lớp, nếu con trỏ chuột nằm trong vùng hình tròn

biểu thị cho Homogenous Clauses thì mẫu này thuộc lớp positive ngựơc lại

mẫu này thuộc lớp negative.

Ví dụ, ta có tập mẫu như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Mẫu Thuộc tính 1

Thuộc tính 2

Lớp

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22

9 10 11 11 11 11 12 12 13 13 15 15 16 16 17 17 17 18 18 19 19 20

8 6 8 7 6 5 7 6 7 5 7 6 8 4 7 6 5 7 6 7 5 6

negative positive negative positive positive positive positive positive negative negative negative negative positive positive positive positive positive negative positive positive negative positive

Bảng 4-1: Ví dụ một tập mẫu hai chiều

Bước 1: Sau khi nhập toàn bộ dữ liệu trên vào chương trình, mẫu

positive là dấu “+”, mẫu negative là dấu “-”, màn hình giao diện như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Hình 4-2: Giao diện chương trình sau khi nhập dữ liệu

Bước 2: Với giá trị Threshold =3, click button Positive Clauses ta sẽ có

các Positive Clauses là các hình chữ nhật trong giao diện của chương trình

như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Hình 4-3: Giao diện chương trình sau khi tìm các Positive Clauses

Chương trình đã tìm được 4 Positive Clauses.

Bước 3: Click button Homogenous để tìm các Homogenous Clauses

cho mỗi Positive Clauses, kết quả tìm được như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Hình 4-4: Giao diện chương trình sau khi tìm các Homogenous Clauses

Bước 4: Mở rộng các Homogenous Clauses, chọn hệ số Coefficient =4,

sau đó click button Expand. Kết quả của bước này như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Hình 4-5: Giao diện chương trình sau khi mở rộng Homogenous Clauses

Ta đã có các Homogenous Clauses được mở rộng, biểu diễn bằng các

hình tròn, các hình tròn này dùng để dự đoán lớp cho các mẫu mới. Giả sử,

bây giờ ta cần dự đoán lớp cho hai mẫu sau y1 (12, 5) và y2 (14, 6), ta thấy y1

nằm trong vòng tròn lớn nhất bên trái, nên y1 được dự đoán thuộc lớp

positive. Còn mẫu y2 (14, 6) không nằm trong bất kỳ một vòng tròn nào nên

dự đoán lớp cho mẫu y2 thuộc về là negative.

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

4.1.2. Cài đặt thuật toán trên không gian N chiều

Thuật toán phân lớp cho các mẫu có n thuộc tính đã được cài đặt bằng

ngôn ngữ Java. Chương trình này yêu cầu dữ liệu phải theo đúng dịnh dạng

được trình bày ở phần 3.5.1 và chương trình sẽ thực hiện các chức năng được

trình bày ở phần 3.5.2.

4.1.2.1. Chuẩn bị dữ liệu

Để có thể sử dụng chương trình cho việc phân lớp và dự đoán thì dữ

liệu sau khi thu thập phải chuyển đổi cho đúng định dạng của chương trình

như sau:

+ Mỗi tập dữ liệu phải lưu trữ trên file có dạng *.TXT.

+ Mỗi mẫu dữ liệu thuộc 1 dòng.

+ Mỗi dòng gồm giá trị của n thuộc tính dạng số nguyên dương hay số

thực dương (n>0) và lớp mà mẫu dữ liệu trên dòng này thuộc về (ký hiệu là

dấu “+” nếu mẫu thuộc lớp positive, ký hiệu là dấu “-” nếu mẫu thuộc lớp

negative).

Ví dụ cách tổ chức dữ liệu trong file, giả sử file này được đặt tên là

DataSet.TXT , như sau :

14.1 0.7 7.4 5.4 5.4 4.0 1.3 5.4 8.7 6.7 3.4 1.3 +

12.5 0.7 8.3 2.1 4.2 6.9 1.4 5.6 10.4 9.0 2.1 6.9 +

19.0 0.7 4.9 5.6 7.0 11.3 1.4 1.4 7.0 6.3 3.5 4.2 +

20.4 0.7 4.1 2.0 2.7 13.6 3.4 5.4 8.2 7.5 3.4 2.0 -

11.0 0.0 3.9 9.1 3.9 7.1 7.1 5.8 12.3 12.3 1.9 1.3 -

12.5 0.0 6.6 3.7 10.3 8.1 2.9 6.6 7.4 4.4 2.9 3.7 -

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

4.1.2.2. Giao diện và các chức năng của chương trình

Sau khi đã có tập dữ liệu đã được chuẩn hóa và tổ chức trên file như đã

trình bày ở trên, ta sẽ sử dụng tập dữ liệu này cho chương trình, chương trình

có giao diện như sau:

Giá trị của hệ số Giá trị ngưỡng khoảng cách

Chọn file chứa tập mẫu học Tên file chứa tập mẫu học và tập mẫu thử

Chọn file chứa tập mẫu thử

Độ chính xác chương trình dự đoán cho tập mẫu thử

Hình 4-6: Giao diện chương trình phân lớp cho dữ liệu N chiều

Bước 1: Training data

Click button Browse ở trên để chọn file chứa tập mẫu học, file này có

dạng *.TXT. Sau đó click button “Training” để cho chương trình bắt đầu học

trên tập mẫu học, kết thúc quá trình học chương trình tìm được các

Homogenous Clauses đã được mở rộng, mỗi Homogenous Clause được lưu

trữ bằng một tâm là một mẫu học và một bán kính là một số thực. Chương

trình lưu các Homogenous Clauses này vào một file có tên là

Expanding.TXT, cấu trúc file này như sau:

+ Cột đầu tiên là số thứ tự của các Homogenous Clauses.

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

+ Cột thứ hai là tâm của Homogenous Clause, nó là số thứ tự của mẫu

học được chọn làm tâm trong tập mẫu học.

+ Cột thứ ba là một số thực chỉ kích thước của bán kính của

Homogenous Clause,

Ví dụ một file Expand.TXT:

1.1706077890859463 1 0

4.532 2 1

1.1706077890859463 3 2

5.0 4 8

20 3.454 5

Sau khi chương trình học xong, sẽ xuất hiện dòng chữ “Finished”

như hình minh họa sau đây:

…

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Hình 4-7: Giao diện chương trình sau khi đã học xong tập mẫu học

Bước 2: Testing data

Sau khi chương trình đã học xong trên tập mẫu học, click button

Browse để chọn file chứa tập mẫu thử, cấu trúc của file chứa tập mẫu thử

hoàn toàn giống như cấu trúc của file chứa tập mẫu học, các mẫu thử phải có

cùng số thuộc tính với các mẫu đã được học. Sau đó click button Testing để

kiểm tra và đánh giá độ chính xác của chương trình. Xác định độ chính xác

bằng cách so sánh lớp của các mẫu thử đã được chương trình dự đoán với lớp

chính xác của các mẫu thử. Độ chính xác này được hiện thị ở textbox

Accuracy của giao diện.

Đồng thời chương trình cũng lưu một file Result.TXT để mô tả sự so

sánh lớp được dự đoán của các mẫu thử và lớp chính xác của chúng. Cấu trúc

của file này như sau: dòng đầu tiên lưu ngưỡng khoảng cách, giá trị hệ số và

độ chính xác, dòng thứ hai mô tả tiêu đề của từng cột, cột đầu tiên là số thứ tự

của các mẫu thử trong file chứa tập mẫu thử, cột thứ hai là lớp chính xác của

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

các mẫu thử thuộc về và cuối cùng là cột thứ ba lưu lớp mà chương trình dự

đoán cho các mẫu thử. Xem hình minh họa và một đoạn đầu của file

Result.TXT sau đây:

Threshold 1.02 Coefficient 100 Accuracy 93.33%

num trust predict

1 + +

2 + +

3 + +

4 + +

5 - -

6 + +

…

Hình 4-8: Giao diện chương trình sau khi đã kiểm tra và đánh giá xong tập mẫu thử

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

4.2. KẾT QUẢ ĐẠT ĐƯỢC

Những ý tưởng và chi tiết của thuật toán điều chỉnh sự quá khớp và

khái quát dữ liệu, đã được trình bày ở trên, để kiểm tra độ chính xác của thuật

toán chương trình đã chạy thử một số tập dữ liệu có uy tín và ghi nhận lại các

kết quả đạt được. Các nguồn dữ liệu được lấy chủ yếu từ 2 web site:

http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data và

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/. Sau khi cho

chương trình chạy với các tập dữ liệu trên hai nguồn này đã đạt được kết quả

rất tốt.

4.2.1 Nguồn dữ liệu trên web site

http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data

Các tập dữ liệu của website này bao gồm như sau:

STT Tên tập dữ liệu Số mẫu Số thuộc tính Số lớp

1 Train_1 3089 4 2

Test_1 4000 4 2

2 Train_2 391 20 3

3 Train_3 1243 21 2

Test_3 41 21 2

Bảng 4-2: Mô tả các tập dữ liệu trên website http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data/

(cid:153) Tập dữ liệu Train_1 và Test_1 có được từ Jan Conrad thuộc Đại học

Uppsala, Thụy Điển. Trong hai tập dữ liệu này các mẫu thuộc một trong hai

lớp 0.0 và 1.0, vì vậy phải chuyển lớp 0.0 thành lớp negative (-) và lớp 1.0

thành lớp positive (+), sau đó lưu thành file Train_1.TXT và Test_1.TXT với

cấu trúc như đã trình bày ở trên. Cho chương trình học trên tập dữ liệu

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Train_1 và thử bằng tập dữ liệu Test_1 thì kết quả đạt được là 95.63% với

ngưỡng khoảng cách bằng 3 và hệ số bằng 1000. Cũng với bộ dữ liệu và

ngưỡng khoảng cách nhưng tăng hệ số bằng 900000 thì độ chính xác là

95.97%.

(cid:153) Tập dữ liệu Train_2 do Cory Spencer thuộc Đại học Simon Fraser,

Canada cung cấp, có ba lớp là “+1”, “+2” và “+3”. Chuyển lớp “+1” thành

lớp positive và hai lớp “+2”, “+3” thành lớp negative, sau đó lưu lại thành file

Train_2.TXT với cấu trúc file như đã trình bày ở trên. Dùng Train_2 làm dữ

liệu học đồng thời làm dữ liệu thử thì kết quả đạt được là 100% với ngưỡng

khoảng cách và hệ số tùy ý. Sau đó, đổi lại lớp “+2” thành lớp positive còn

lớp “+1” và “+3” thành lớp negative thì kết quả vẫn đạt 100%.

(cid:153) Tập dữ liệu Train_3 và Test_3 chỉ có hai lớp là “-1” và “+1”,

chuyển lớp “+1” thành lớp positive(+) và lớp “-1” thành negative(-). Tương

tự như trên, lưu thành hai file theo đúng cấu trúc qui định ban đầu. Sau đó

dùng tập Train_3 làm tập dữ liệu học cho chương trình và tập Test_3 làm tập

dữ liệu thử thì kết quả đạt được là 100%, bất kể ngưỡng khoảng cách và hệ

số. Bảng tóm tắt sau đây cho thấy độ chính xác của thuật toán phân lớp này.

Hệ số Độ chính xác

Tập dữ liệu học Tập dữ liệu thử Ngưỡng khoảng cách

Train_1 Test_1 3 900,000 95.97%

Train_2 Train_2 tùy ý tùy ý 100%

Train_3 Test_3 tùy ý tùy ý 100%

Bảng 4-3: Kết quả phân lớp các tập dữ liệu trên website http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data/

Cũng trên các tập dữ liệu này, Chih-Wei Hsu, Chih-Chung Chang, và

Chih-Jen Lin (http://www.csie.ntu.edu.tw/~cjlin/papers/guide) sử dụng thuật

toán phân lớp Support Vector Machine thì kết quả đạt được như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Tập dữ liệu học Tập dữ liệu thử Độ chính xác

Train_1 Test_1 96.9%

Train_2 Train_2 85.2%

Train_3 Test_3 87.8%

Bảng 4-4: Kết quả phân lớp theo thuật toán SVM của Cjlin

So sánh kết quả của chương trình phân lớp theo thuật toán điều chỉnh

sự quá khớp và quá khái quát dữ liệu với hệ thống phân lớp theo thuật toán

SVM của Cjlin trên cùng một số tập dữ liệu, được mô tả như sau:

100.0%

95.0%

Độ chính xác của thuật toán SVM của Cjlin

90.0%

85.0%

80.0%

75.0%

Độ chính xác của thuật toán điều chỉnh sự quá khớp và quá khái quát dữ liệu

Train_2

Train_1 và Test_1

Train_3 và Test_3

Hình 4-9: Biểu đồ so sánh kết quả

4.2.2. Nguồn dữ liệu trên web site

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary

Các tập dữ liệu thứ hai được sử dụng để đánh giá thuật toán được lấy từ

website : http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/. Một

số tập dữ liệu được lấy như a1a, a2a, a3a, a4a, a5a, a6a, a7a, w1a, w2a, w3a,

w4a, w5a và w6a. Các tập dữ liệu này chỉ có hai lớp, sau chuyển đổi các tập

dữ liệu này đúng cấu trúc như đã trình bày ở trên, lấn lượt cho chương trình

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

học một tập dữ liệu và lấy các tập còn lại làm dữ liệu thử thì kết quả đạt được

như sau:

Số thuộc tính 119 Số mẫu 1605 Độ chính xác a1a Tập dữ liệu Học a1a

119 2265 Thử a2a 91.39%

a2a Tập dữ liệu Số thuộc tính Số mẫu Độ chính xác

119 2265 Học a2a

119 1605 Thử a1a 98,69%

Số thuộc tính 122 Số mẫu 3185 Độ chính xác

a3a Tập dữ liệu a3a c ọ H

ử h T

122 122 122 122 4781 6414 11220 16100 a4a a5a a6a a7a 90,17% 86,47% 82,17% 79,99%

Số mẫu a6a Tập dữ liệu Số thuộc tính Độ chính xác

122 11220

a6a c ọ H

ử h T

122 122 122 122 3185 4781 6414 16100 a3a a4a a5a a7a 96,14% 96,03% 95,95% 89,71%

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Số thuộc tính 122 Số mẫu 16100 Độ chính xác

a7a Tập dữ liệu a7a c ọ H

ử h T

a3a a4a a5a a6a 122 122 122 122 3185 4781 6414 11220 94,98% 94,92% 94,92% 96,95%

ử h T

w1a Tập dữ liệu Học w1a w2a w3a w4a w5a w6a Số thuộc tính 300 300 300 300 300 300 Số mẫu 2477 3470 4912 7366 9888 17188 Độ chính xác 85,97% 85,40% 85,08% 84,64% 84,18%

ử h T

w2a Tập dữ liệu Học w2a w1a w3a w4a w5a w6a Số thuộc tính 300 300 300 300 300 300 Số mẫu 3470 2477 4912 7366 9888 17188 Độ chính xác 85,99% 85,91% 85,43% 84,09% 84,38%

ử h T

w4a Tập dữ liệu Học w4a w1a w2a w3a w5a w6a Số thuộc tính 300 300 300 300 300 300 Số mẫu 7366 2477 3470 4912 9888 17188 Độ chính xác 85,79% 86,57% 86,16% 85,41% 84,83%

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

ử h T

w5a Tập dữ liệu Học w5a w1a w2a w3a w4a w6a Số thuộc tính 300 300 300 300 300 300 Số mẫu 9888 2477 3470 4912 7366 17188 Độ chính xác 85,79% 86,57% 86,16% 86,14% 84,93%

Bảng 4-5: Kết quả của quá trình học và dự đoán lớp cho tập dữ liệu trên website: http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/

4.3. ÁP DỤNG PHÂN LỚP CHO BÀI TOÁN PROTEIN FOLDING

4.3.1. Bài toán Protein Folding

Ngày nay, các nhà sinh vật học đã xác định được rằng cơ sở vật chất

chủ yếu của sự sống gồm hai loại hợp chất hữu cơ là protein và axit nucleic.

Protein là hợp phần cấu tạo chủ yếu của chất nguyên sinh và là thành phần

chức năng trong cấu tạo của các enzim và hoocmon, đóng vai trò xúc tác và

điều hòa. Protein thuộc loại đại phân tử, có kích thước và khối lượng lớn.

Phân tử protein lớn nhất dài 0,1 micromet, khối lượng phân tử có thể tới 150

triệu đơn vị cacbon. Protein là chất cao phân tử được cấu tạo theo nguyên tắc

đa phân, mà đơn phân là axit amin. Mỗi phân tử protein gồm trung bình 100 –

30000 phân tử axit amin liên kết với nhau. Các axit min liên kết với nhau

bằng liên kết peptit, tạo nên chuỗi polypeptit. Có hơn hai mươi loại axit amin

khác nhau, được đặt tên là A, C, G, T,… đã tạo ra vô số loại protein khác

nhau ở số lượng, thành phần, trật tự sắp xếp các axit amin. Protein có bốn bậc

cấu trúc cơ bản.

• Cấu trúc bậc một là thứ tự sắp xếp các axit amin trong chuỗi

polypeptit.

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

• Cấu trúc bậc hai do chuỗi polypeptit bậc một xoắn hình lò xo hay

hình xoắn ốc, giữa các vòng xoắn có các liên kết hydro làm cho cấu trúc

protein được bền vững.

• Cấu trúc bậc ba chuỗi polypeptit xoắn hình lò xo uốn vòng trong

không gian, nhờ cấu trúc bậc ba mà protein thường có dạng hình cầu, giữa

các vòng uốn cũng có các liên kết hydro làm cho cấu trúc protein được

bền vững hơn.

• Cấu trúc bậc bốn gồm nhiều cấu trúc bậc ba kết hợp lại.

Hình 4-10: Các bậc cấu trúc khác nhau của phân tử protein

a) Cấu trúc bậc một c) Cấu trúc bậc ba

b) Cấu trúc bậc hai d) Cấu trúc bậc bốn

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Cấu trúc của protein được sử dụng trong dự đoán và phân lớp cho

protein, nên còn được gọi là phân lớp cấu trúc protein. Phân lớp protein sẽ hỗ

trợ cho việc xác định chức năng của protein dễ dàng và nhanh chóng hơn.

Protein folding là bài toán phân lớp cấu trúc không gian ba chiều của protein.

Một protein được xếp vào một trong bốn lớp cấu trúc, phụ thuộc vào thành

phần cấu trúc phụ đó là : hoàn toàn xoắn ốc (gọi là all-α), hoàn toàn hình sợi

(gọi là all-β), α /β, α +β. Trong những năm gần đây có rất nhiều sự nghiên cứu

về bài toán phân lớp cấu trúc protein, nhưng đến nay nó vẫn là một bài toán

mở. Ngày nay bài toán này được tiếp cận bởi nhiều hướng khác nhau và nó

được chia thành các nhiệm vụ nhỏ hơn như dự đoán cấu trúc bậc hai, xác định

lớp cấu trúc, dự đoán bề mặt tiếp xúc…

Trong đề tài này, phân lớp cấu trúc protein dựa vào sự tổng hợp các axit

amin (Amino Acid Composition - ACC), ACC là một vector 20 chiều tương

ứng với 20 loại axit amin khác nhau, vector này chỉ rõ tỷ lệ của mỗi loại axit

amin trong sự tổng hợp của 20 loại axit amin khác nhau. Sử dụng hệ thống

phân lớp đã được cài đặt theo thuật toán điều chỉnh sự quá khớp và quá khái

quát dữ liệu để phân lớp và dự đoán cho một số protein trong một số tập dữ

liệu về protein. Qua đó đánh giá được thuật toán đồng thời có thể áp dụng cho

việc phân lớp cấu trúc protein trong thực tế.

4.3.2. Mô tả cơ sở dữ liệu

Để đánh giá thuật toán chính xác và khách quan, phải chương trình đã

sử dụng một số dữ liệu phổ biến và uy tín. Vì vậy, trong phần này sẽ sử dụng

cơ sở dữ liệu lấy từ website http://www.nersc.gov/~cding/protein. Trong cơ

sở dữ liệu này gồm 12 tập dữ liệu về 6 lĩnh vực, mỗi lĩnh vựcgồm 2 tập dữ

liệu, 1 tập dữ liệu học và 1 tập dữ liệu thử. Sáu lĩnh vực đó là:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Amino Acids Composition (tổng hợp axit amin): gồm hai tập dữ liệu,

tập dữ liệu học có 605 mẫu, tập dữ liệu thử có 385 mẫu. Mỗi mẫu là một

vector 22 chiều, trong đó 20 chiều đầu tiên tương ứng với 20 loại axit amin

khác nhau, chiều thứ 21 là chiều dài của protein và chiều cuối cùng là lớp mà

Năm mục còn lại là Predicted secondary structure (dự đoán cấu trúc

mẫu đó thuộc về. Vì vậy xem như mỗi mẫu có 21 thuộc tính.

bậc hai), Polarity (khả năng phân cực của protein), Polarizability (tình trạng

phân cực của protein), Hydrophobicity (tính chống thấm nước), và Van der

Waals volume. Trong đó mỗi mục có một tập dữ liệu học gồm 605 mẫu và

một tập dữ liệu thử gồm 385 mẫu. Khác với mục Amino Acids Composition,

mỗi mẫu trong năm mục này là một vector 23 chiều. Trong 23 chiều này có

20 chiều là 20 mươi axit amin, một chiều là thuộc tính riêng của từng mục,

một chiều là chiều dài của protein và một chiều cuối cùng là lớp mà mẫu đó

thuộc về. Vì vậy xem như mỗi mẫu có 22 thuộc tính.

Đây là cơ sở dữ liệu đa lớp của protein mà hệ thống phân lớp là nhị

phân. Vì vậy cần phải chuyển đổi cơ sở dữ liệu. Thay vì phân lớp một lần cho

các mẫu protein trong mỗi mục, khi đó các mẫu thuộc về một trong bốn lớp

all-α, all-β, α /β hoặc α +β còn đối với hệ thống phân lớp nhị phân thì mỗi tập

dữ liệu được chuyển thành bốn tập dữ liệu tương đương. Tập dữ liệu tương

đương thứ nhất, lớp all-α chuyển thành positive các lớp còn lại chuyển thành

negative. Tập dữ liệu tương đương thứ hai, lớp all-β chuyển thành positive

các lớp còn lại chuyển thành negative. Tập dữ liệu tương đương thứ ba, lớp

α/β chuyển thành positive các lớp còn lại chuyển thành negative. Tập dữ liệu

tương đương thứ tư, lớp α+β chuyển thành positive các lớp còn lại chuyển

thành negative.

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Tập dữ liệu tương đương thứ nhất dùng để dự đoán lớp all-α, tập dữ

liệu tương đương thứ hai dùng để dự đoán lớp all-β, tập dữ liệu tương đương

thứ ba dùng để dự đoán lớp α /β , tập dữ liệu tương đương thứ tư dùng để dự

đoán lớp α +β.

Toàn bộ các tập dữ liệu học và dữ liệu thử của cơ sở dữ liệu đều phải

chuyển đổi như vậy, và được lưu trữ trong bốn thư mục tương đương với 4

tập dữ liệu tương đương. Mỗi tập dữ liệu chứa trong một file, như vậy có tất

cả 48 file, mỗi thư mục chứa 12 file. Trong mỗi file dữ liệu được lưu trữ theo

định dạng như sau: mỗi dòng là một mẫu protein, mỗi thuộc tính trong một

mẫu là một số thực cách nhau một số khoảng trắng và cuối dòng có ký kiệu

“+” nếu mẫu trên dòng đó thuộc lớp positive, có ký hiệu “-”, nếu mẫu trên

dòng đó thuộc lớp negative.

Ví dụ một tập dữ liệu gốc như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

14.1 0.7 7.4 5.4 … 1.3 2.7 149 2lhb

(cid:198) all-α

12.5 0.7 8.3 2.1 … 1.4 2.8 144 3sdha

(cid:198) all-α

19.0 0.7 4.9 5.6 … 2.8 0.7 142 1flp

(cid:198)all-α

20.4 0.7 4.1 2.0 … 1.4 2.0 147 2hbg

(cid:198)all-α

11.0 0.0 3.9 9.1 … 1.3 1.9 154 2mge

(cid:198)all-α

4.2 2.3 5.6 4.2 … 1.4 3.8 213 6fabl

(cid:198)all-β

2.9 1.9 4.4 5.8 … 1.9 4.4 206 1fc2d

(cid:198)all-β

2.2 2.2 5.6 5.1 … 1.7 0.6 178 3cd4

(cid:198)all-β

4.5 1.1 1.7 9.6 … 1.7 1.1 177 1cid

(cid:198)all-β

8.1 0.5 9.4 1.8 … 1.8 5.2 383 1cgt3

(cid:198)α /β

7.6 2.0 9.9 2.5 … 2.5 7.6 353 6taa1

(cid:198)α /β

6.0 2.5 6.0 5.0 … 4.0 4.2 402 1ppi1

(cid:198)α /β

8.1 1.1 9.5 2.8 … 5.0 4.8 357 1amg1

(cid:198)α /β

6.2 3.1 7.3 5.2 … 0.0 8.3 96 1gmpa

(cid:198)α+β

6.5 0.0 8.4 2.8 … 2.8 6.5 107 1bsaa

(cid:198)α+β

10.7 0.0 8.9 8.9 … 1.8 5.4 56 1pga

(cid:198)α+β

11.5 0.0 6.4 15 .… 0.0 5.1 78 2ptl

(cid:198)α+β

…

Trong tập dữ liệu gốc, mỗi mẫu có một cái tên. Tùy theo tập dữ liệu

này là tập dữ liệu học hay tập dữ liệu thử mà dựa vào file list_train.html hay

list_test.html trong cùng website với các tập dữ liệu, để lấy một con số chỉ

mục. Có được số chỉ mục, vào file classnames.html để lấy tên lớp mà mẫu

protein đó thuộc về. Ví dụ, xét xem lớp của mẫu có tên là “2lhb” trong tập dữ

liệu học, có số chỉ mục là 1, trong file classnames1 là lớp“Alpha” (all-α).

list_train.html classnames.html

1 Alpha; Globin-like 2 Alpha; Long alpha-hairpin 3 Alpha; Cytochrome c 4 DNA-binding 3-helical bundle 20 Beta; Immunoglobulin-like beta-sandwich 46 A/B; beta/alpha (TIM)-barrel 1 2lhb 1 3sdha 1 1flp 1 2hbg 2 1isca1 3 1ccr

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Sau đó chuyển tập dữ liệu gốc thành các các tập dữ liệu tương đương

như sau:

14.1 0.7 7.4 5.4 … 1.3 2.7 149 -

14.1 0.7 7.4 5.4 … 1.3 2.7 149 +

12.5 0.7 8.3 2.1 … 1.4 2.8 144 -

12.5 0.7 8.3 2.1 … 1.4 2.8 144 +

19.0 0.7 4.9 5.6 … 2.8 0.7 142 -

19.0 0.7 4.9 5.6 … 2.8 0.7 142 +

20.4 0.7 4.1 2.0 … 1.4 2.0 147 -

20.4 0.7 4.1 2.0 … 1.4 2.0 147 +

11.0 0.0 3.9 9.1 … 1.3 1.9 154 -

11.0 0.0 3.9 9.1 … 1.3 1.9 154 +

4.2 2.3 5.6 4.2 … 1.4 3.8 213 +

4.2 2.3 5.6 4.2 … 1.4 3.8 213 -

2.9 1.9 4.4 5.8 … 1.9 4.4 206 +

2.9 1.9 4.4 5.8 … 1.9 4.4 206 -

2.2 2.2 5.6 5.1 … 1.7 0.6 178 +

2.2 2.2 5.6 5.1 … 1.7 0.6 178 -

4.5 1.1 1.7 9.6 … 1.7 1.1 177 +

4.5 1.1 1.7 9.6 … 1.7 1.1 177 -

8.1 0.5 9.4 1.8 … 1.8 5.2 383 -

7.6 2.0 9.9 2.5 … 2.5 7.6 353 -

6.0 2.5 6.0 5.0 … 4.0 4.2 402 -

8.1 1.1 9.5 2.8 … 5.0 4.8 357 -

6.2 3.1 7.3 5.2 … 0.0 8.3 96 -

6.5 0.0 8.4 2.8 … 2.8 6.5 107 -

10.7 0.0 8.9 8.9 … 1.8 5.4 56 -

11.5 0.0 6.4 15 .… 0.0 5.1 78 -

…

Đây là hai tập dữ liệu tương đương thứ nhất và thứ hai, tập dữ liệu

tương đương thứ ba và thứ tư tương tự chuyển đổi như vậy.

4.3.3. Kết quả thực hiện

Sau khi đã chuyển đổi tất cả các tập dữ liệu học và dữ liệu thử của cơ

sở dữ theo đúng định dạng như đã trình bày ở trên, tiến hành phân lớp và dự

đoán cấu trúc lớp cho các mẫu protein. Đầu tiên sử dụng thư mục chứa các

tập dữ liệu tương đương thứ nhất để phân lớp và dự đoán cho các protein có

cấu trúc hoàn toàn xoắn (all-α), kết quả như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

stt Tập dữ liệu Ghi chú

Phân lớp all-α Số mẫu thử

Số thuộc tính Số mẫu học

1 Composition 605 385 Độ chính xác 87.27% 21

2 Hydrophobicity 605 385 86.75% 22

3 Polarity 605 385 87.27% 22

4 Polarizability 605 385 86.75% 22

5 Secondary 605 385 87.23% 22

Kết quả không phụ thuộc vào ngưỡng khoảng cách và hệ số

6 Volume 605 385 87.01% 22

Trung bình 87.05%

Bảng 4-6: Kết quả phân lớp protein vào lớp all-α

Tương tự như vậy, sử dụng thư mục chứa các tập dữ liệu tương đương

thứ hai để phân lớp và dự đoán cho các protein có cấu trúc hoàn toàn hình sợi

(all-β), kết quả như sau:

Phân lớp all-β

stt Tập dữ liệu Ghi chú

Số mẫu học Số mẫu thử Số thuộc tính

1 Composition 605 385 Độ chính xác 74.81% 21

2 Hydrophobicity 605 385 74.55% 22

3 Polarity 605 385 73.51% 22

4 Polarizability 605 385 74.29% 22

5 Secondary 605 385 72.21% 22

6 Volume 605 385 74.29% 22

Kết quả không phụ thuộc vào ngưỡng khoảng cách và hệ số

Trung bình 73.94%

Bảng 4-7: Kết quả phân lớp protein vào lớp all-β

Tương tự như vậy, đối với hai lớp α /β v2 α +β thì kết quả như sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

Phân lớp α /β

stt Tập dữ liệu Ghi chú

Số mẫu học Số mẫu thử Số thuộc tính

1 Composition 605 Độ chính xác 71.43% 21 385

2 Hydrophobicity 605 71.17% 22 385

3 Polarity 605 70.13% 22 385

4 Polarizability 605 70.13% 22 385

5 Secondary 605 66.75% 22 385

Kết quả không phụ thuộc vào ngưỡng khoảng cách và hệ số

6 Volume 605 71.43% 22 385

Trung bình 70.17%

Bảng 4-8: Kết quả phân lớp protein vào lớp α /β

Phân lớp α +β

stt Tập dữ liệu Ghi chú

Số mẫu học Số mẫu thử Số thuộc tính

1 Composition 605 Độ chính xác 91.95% 21 385

2 Hydrophobicity 605 91.69% 22 385

3 Polarity 605 91.95% 22 385

4 Polarizability 605 91.95% 22 385

5 Secondary 605 91.17% 22 385

Kết quả không phụ thuộc vào ngưỡng khoảng cách và hệ số

6 Volume 605 91.95% 22 385

Trung bình 91.78%

Bảng 4-9: Kết quả phân lớp protein vào lớp α +β

Trung bình độ chính xác được thể hiện ớ bảng sau:

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

stt Tập dữ liệu all-α all-β α/β α/β TBình

1 2 3 4 5 6 87.27% 74.81% 71.43% 91.95% 91.17 87.23 91.69 86.75 91.95 87.27 91.95 87.01 91.95 86.75 72.21 74.55 73.51 74.29 74.29 66.75 71.17 70.13 71.43 70.13 81.37% 79.34 81.04 80.72 81.17 80.78

Composition Secondary struc. Hydrophobicity Polarity Volume Polarizability

Bảng 4-10: Kết quả phân lớp protein của thuật toán phân lớp điều chỉnh

tính quá khớp và quá khái quát dữ liệu

Trên cùng cơ sở dữ liệu này Chris H.Q.Ding và Inna Dubchak (http://www.nersc.gov/~cding/protein) sử dụng thuật toán SVM và mạng Neural (NN) để phân lớp cấu trúc protein thì đạt kết quả như sau:

Stt Lĩnh vực

1 SVM Ind-Test 44.9% NN Ind_Test 20.5% Composition

2 3 4 5 6 35.6 36.5 32.9 35.0 32.9 18.3 14.2 11.1 13.4 13.2 Secondary struc. Hydrophobicity Polarity volume Polarizability

Bảng 4-11: Kết quả phân lớp protein của thuật toán SVM và NN

CÀI ĐẶT THUẬT TOÁN VÀ ÁP DỤNG CHO BÀI TOÁN PROTEIN FOLDING

90.0%

80.0%

Đ? chính xác c?a thu?t toán Neural Network

70.0%

60.0%

50.0%

Đ? chính xác c?a thu?t toán SVM

40.0%

30.0%

20.0%

10.0%

0.0%

1

2

3

4

5

6

Đ? chính xác c?a thu?t toán đi?u ch?nh s? quá kh?p và quá khái quát d? li?u

Hình 4-9: Biểu đồ so sánh kết quả phân lớp cấu trúc Protein

TỔNG KẾT

KẾT LUẬN

Đã cài đặt thử nghiệm được thuật toán phân lớp điều chỉnh sự quá khớp và

quá khái quát dữ liệu dựa trên định nghĩa về mật độ của tập Homogenous

Clauses. Chương trình demo trên mặt phẳng hai chiều với giao diện rõ ràng minh

họa tốt cho thuật toán. Chương trình phân lớp dữ liệu n chiều đã đạt đựơc kết

quả tốt trên một số nguồn dữ liệu.

Thử nghiệm với nhiều tập dữ liệu lớn thuộc 2 website

http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data và

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary. Và đã đạt được

kết quả rất tốt.

Ứng dụng thuật toán vào bài toán protein folding và đã dạt được kết quả

khá tốt.

HƯỚNG PHÁT TRIỂN

Nâng cao độ chính xác bằng cách tìm ra một hàm mật độ thích hợp cho

các Homogenous Clauses.

Nâng cao tốt độ xử lý bằng cách dùng kỹ thuật xử lý song song, ví dụ

moblie agent…

Thuật toán điều chỉnh sự quá khớp và quá khái quát không chỉ sử dụng

cho bài toán phân lớp mà có thể sử dụng cho nhiều lĩnh vực khác.

Phát triển thuật toán cho việc phân lớp đa lớp, bằng cách tìm các

Homogenous Clause cho tất cảc các lớp.

TỔNG KẾT

TÀI LIỆU THAM KHẢO

[1] Nguyễn Đình Thúc, Mạng Nơron_ Phương pháp và ứng dụng, Nhà xuất

bản giáo dục, 200.

[2] Jiawei Han and Micheline Kamber, Data Mining: Concepts and Techniques

[3] Olivia Parr Rud, Data Mining Cookbook, Willey Computer publishing,

Sons inc.

[4] Ming Syan Chen, Data Mining: An Overwiew Database Perspective,

National Taiwan Univ, Taipei, Taiwan, ROC.

[5] David Hand, Hekki Mannila and Padhraic Smyth, Principles of Datamining.

[6] Chih-Wei Hsu, Chih-Chung Chang, and Chih-Jen Lin, A Practical Guide to

Support Vector Classification,Information Engineering, National Taiwan,

University, Taipei 106, Taiwan.

[7] Zerrin Isik, Berrin Yanikoglu, Ugur Sezerman, Protein Structural Class

Determination Using Support Vector Machines, Sabanci University, Tuzla,

Istanbul, Turkey 34956.

[8] Hyunsoo Kim and Haeun Park, Protein Secondary Structure Prediction

Based on an Improved Support Vector Machines Approach, September

2002.

[9] Hyunsoo Kim and Haeun Park, Prediction of Protein Relative Solvent

Accessibility with Support Vector Machine and long-range Interaction 3D

Local Descriptor.

[10] Website: http://www.csie.ntu.edu.tw/~cjlin/papers/guide/data

[11] Website: http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/