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 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 4.2.2. Nguồn dữ liệu trên web site 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 s