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

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

135
lượt xem 29
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 đó....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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 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