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
W X
NGUYỄN QUANG PHƯỚC - 0112193
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
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
DE
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
1
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,
2
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
3
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
4
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,
5
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
6
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- β.
7
- Xem thêm -