Luận Văn Thạc Sĩ: Nghiên Cứu Mô Hình Đa Phân Lớp Dựa Trên GA và SVM

Luận văn thạc sĩ nghiên cứu vnu uet nghiên cứu xây dựng mô hình đa phân lớp dựa trên ga và svm, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực

• Tác giả: Lữ Đăng Nhạc
• Người hướng dẫn: TS. Nguyễn Hà Nam
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Nghiên cứu xây dựng mô hình đa phân lớp dựa trên GA và SVM
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2010
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• DANH MỤC HÌNH VẼ
• DANH MỤC BẢNG BIỂU
• DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT
• 1. CHƯƠNG 1: MỞ ĐẦU
• 2. CHƯƠNG 2: THUẬT TOÁN PHÂN LỚP VỚI SVM
• 2.1. Giới thiệu chung về phân lớp
• 2.2. Khái niệm cơ bản
• 2.3. Quá trình phân lớp
• 2.4. Xây dựng mô hình
• 2.5. Sử dụng mô hình
• 2.6. Các yêu cầu đối với bài toán phân lớp
• 2.7. Kỹ thuật phân lớp SVM (Support vector machines)
• 2.7.1. SVM tuyến tính
• 2.7.2. Các bộ phận phân lớp tuyến tính
• 2.7.3. Tập huấn luyện có thể phân chia tuyến tính
• 2.7.4. SVM tuyến tính cho bộ huấn luyện có thể phân chia
• 2.7.5. Tìm siêu phẳng tối ưu
• 2.7.6. Các véc tơ hỗ trợ
• 2.8. Kết luận chương
• 3. CHƯƠNG 3: GIẢI THUẬT DI TRUYỀN
• 3.1. Nội dung thuật toán
• 3.2. Thể hiện giả thuyết
• 3.3. Các toán tử di truyền
• 3.4. Hàm thích nghi và sự chọn lọc
• 3.5. Kết luận chương
• 4. CHƯƠNG 4: MÔ HÌNH TỐI ƯU ĐA PHÂN LỚP SVM
• 4.1. Mô hình đề xuất
• 4.2. Cấu trúc hàm Kernel
• 4.3. Cấu trúc của cá thể và kỹ thuật tìm tham số tối ưu dựa trên giải thuật di truyền
• 4.4. Kết luận chương
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Mô Hình Đa Phân Lớp Dựa Trên GA và SVM

Mô hình đa phân lớp dựa trên thuật toán di truyền (GA) và máy vector hỗ trợ (SVM) đang trở thành một trong những phương pháp tiên tiến trong lĩnh vực khai thác dữ liệu. Nghiên cứu từ Đại học Quốc gia Hà Nội đã chỉ ra rằng việc kết hợp hai thuật toán này có thể cải thiện đáng kể độ chính xác trong việc phân loại dữ liệu. Mô hình này không chỉ giúp phân loại dữ liệu thành nhiều lớp mà còn tối ưu hóa các tham số của hàm nhân Kernel, từ đó nâng cao hiệu suất phân lớp.

1.1. Khái niệm về Mô Hình Đa Phân Lớp

Mô hình đa phân lớp là một phương pháp phân loại dữ liệu thành nhiều lớp khác nhau. Trong nghiên cứu này, mô hình được xây dựng dựa trên sự kết hợp giữa GA và SVM, cho phép phân loại dữ liệu phức tạp với độ chính xác cao.

1.2. Tầm quan trọng của GA và SVM trong Phân Lớp

GA giúp tối ưu hóa các tham số của mô hình, trong khi SVM cung cấp một phương pháp phân lớp mạnh mẽ. Sự kết hợp này tạo ra một mô hình có khả năng phân loại tốt hơn so với việc sử dụng từng thuật toán riêng lẻ.

II. Vấn đề và Thách thức trong Phân Lớp Dữ Liệu

Phân lớp dữ liệu là một thách thức lớn trong khai thác dữ liệu, đặc biệt khi đối mặt với các tập dữ liệu lớn và phức tạp. Các vấn đề như dữ liệu không đầy đủ, nhiễu và tính đa dạng của dữ liệu đều ảnh hưởng đến hiệu suất của mô hình phân lớp. Nghiên cứu từ Đại học Quốc gia Hà Nội đã chỉ ra rằng việc áp dụng GA và SVM có thể giúp giải quyết những thách thức này.

2.1. Các Vấn Đề Thường Gặp trong Phân Lớp

Một số vấn đề phổ biến bao gồm dữ liệu không đầy đủ, dữ liệu nhiễu và sự đa dạng của các loại dữ liệu. Những vấn đề này có thể làm giảm độ chính xác của mô hình phân lớp.

2.2. Thách Thức trong Việc Tối Ưu Hóa Mô Hình

Tối ưu hóa mô hình phân lớp đòi hỏi phải tìm ra các tham số tốt nhất cho hàm nhân Kernel. Điều này có thể gặp khó khăn khi dữ liệu có nhiều chiều và phức tạp.

III. Phương Pháp Kết Hợp GA và SVM trong Mô Hình Đa Phân Lớp

Nghiên cứu đã áp dụng phương pháp One Against All (OAA) kết hợp với GA để tối ưu hóa các tham số của SVM. Phương pháp này cho phép mô hình phân loại dữ liệu thành nhiều lớp một cách hiệu quả. Việc sử dụng GA giúp tìm ra các tham số tối ưu cho hàm nhân Kernel, từ đó nâng cao độ chính xác của mô hình.

3.1. Giới Thiệu về Phương Pháp One Against All

Phương pháp OAA cho phép phân loại dữ liệu thành nhiều lớp bằng cách xây dựng một bộ phân loại cho mỗi lớp. Điều này giúp cải thiện độ chính xác trong việc phân loại dữ liệu.

3.2. Tối Ưu Hóa Tham Số với GA

GA được sử dụng để tối ưu hóa các tham số của hàm nhân Kernel trong SVM. Việc này giúp cải thiện hiệu suất của mô hình phân lớp, đặc biệt trong các tập dữ liệu phức tạp.

IV. Ứng Dụng Thực Tiễn và Kết Quả Nghiên Cứu

Mô hình đa phân lớp dựa trên GA và SVM đã được áp dụng thành công trong nhiều lĩnh vực, từ y tế đến tài chính. Kết quả nghiên cứu cho thấy mô hình này có khả năng phân loại dữ liệu với độ chính xác cao hơn so với các phương pháp truyền thống. Các thử nghiệm trên tập dữ liệu thực tế đã chứng minh tính hiệu quả của mô hình.

4.1. Ứng Dụng trong Y Tế

Mô hình đã được áp dụng để phân loại dữ liệu bệnh nhân, giúp xác định giai đoạn bệnh và phương pháp điều trị phù hợp. Điều này có thể cải thiện đáng kể kết quả điều trị cho bệnh nhân.

4.2. Kết Quả Thực Nghiệm với Tập Dữ Liệu

Các thử nghiệm cho thấy mô hình GA&SVM đạt được độ chính xác cao trong việc phân loại dữ liệu, vượt trội hơn so với các phương pháp phân lớp khác.

V. Kết Luận và Hướng Phát Triển Tương Lai

Mô hình đa phân lớp dựa trên GA và SVM đã chứng minh được tính hiệu quả trong việc phân loại dữ liệu. Tuy nhiên, vẫn còn nhiều hướng nghiên cứu có thể được khai thác để cải thiện hơn nữa độ chính xác và khả năng ứng dụng của mô hình. Nghiên cứu trong tương lai có thể tập trung vào việc phát triển các thuật toán mới và cải tiến các phương pháp hiện tại.

5.1. Tóm Tắt Kết Quả Nghiên Cứu

Nghiên cứu đã chỉ ra rằng mô hình GA&SVM có khả năng phân loại dữ liệu hiệu quả, mở ra nhiều cơ hội ứng dụng trong thực tiễn.

5.2. Hướng Nghiên Cứu Tương Lai

Các nghiên cứu tiếp theo có thể tập trung vào việc cải tiến thuật toán và áp dụng mô hình vào các lĩnh vực mới, từ đó nâng cao khả năng phân loại và dự đoán.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LỮ ĐĂNG NHẠC NGHIÊN CỨU XÂY DỰNG MÔ HÌNH ĐA PHÂN LỚP DỰA TRÊN GA VÀ SVM LUẬN VĂN THẠC SĨ HÀ NỘI - 2010 LUAN VAN CHAT LUONG download : add [e-mail] ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LỮ ĐĂNG NHẠC NGHIÊN CỨU XÂY DỰNG MÔ HÌNH ĐA PHÂN LỚP DỰA TRÊN GA VÀ SVM Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.05 LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: TS. NGUYỄN HÀ NAM HÀ NỘI - 2010 LUAN VAN CHAT LUONG download : add [e-mail] 6 MỤC LỤC LỜI CẢM ƠN . 1 DANH MỤC HÌNH VẼ . 2 DANH MỤC BẢNG BIỂU . 4 BANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT . 6 Chƣơng 1 - MỞ ĐẦU. 8 Chƣơng 1 - THUẬT TOÁN PHÂN LỚP VỚI SVM .Giới thiệu chung về phân lớp .Khái niệm cơ bản .Quá trình phân lớp .Xây dựng mô hình .Sử dụng mô hình .Các yêu cầu đối với bàn toán phân lớp .Kỹ thuật phân lớp SVM(Support vector machines) .SVM tuyến tính .Các bộ phận phân lớp tuyến tính .Tập huấn luyện có thể phân chia tuyến tính .SVM tuyến tính cho bộ huấn luyện có thể phân chia .Tìm siêu phẳng tối ưu.Các véc tơ hỗ trợ .SVM tuyến tính cho tập huấn luyện tổng quát .SVM không tuyến tính .Không gian đặc trưng .SVM tuyến tính trong không gian đặc trưng .Ngầm xạ sang không gian đặc trưng .Các hàm nhân phổ biến .Một số biến thể và cải tiến của SVM.Một số kỹ thuật đa phân lớp .Kỹ thuật Cross Validation . 25 Kết luận chương . 26 LUAN VAN CHAT LUONG download : add [e-mail] 7 Chƣơng 2 - GIẢI THUẬT DI TRUYỀN .Nội dung thuật toán .Thể hiện giả thuyết .Các toán tử di truyền .Hàm thích nghi và sự chọn lọc . 34 Kết luận chương . 35 Chƣơng 3 - MÔ HÌNH TỐI ƢU ĐA PHÂN LỚP SVM .Mô hình đề xuất .Cấu trúc hàm Kernel .Cấu trúc của cá thể và kỹ thuật tìm tham số tối ưu dựa trên giải thuật di truyền . 39 Kết luận chương . 40 Chƣơng 4 - XÂY DỰNG CHƢƠNG TRÌNH MÔ PHỎNG .Giao diện chương trình .Giới thiệu về MatLab .Các module trong hệ thống và giao diện của chương trình . Module Genetic Algorithm .Các hàm trong chương trình .Sử dụng bộ dữ liệu Stomach cho chương trình .Kết quả thực nghiệm với hàm Gaussian .2 Kết quả thực nghiệm với hàm Poly. Thực nghiệm với bộ dữ liệu men Yeast.Kết quả thực nghiệm với hàm Gaussian .Kết quả thực hiện với hàm Poly. 54 Kết luận chương .Các đóng góp khoa học của luận văn .Hướng phát triển . 58 TÀI LIỆU THAM KHẢO . 61 LUAN VAN CHAT LUONG download : add [e-mail] 1 LỜI CẢM ƠN Trước tiên, em xin chân thành cảm ơn TS.Nguyễn Hà Nam người thày đã hướng dẫn, chỉ dạy tận tình để em hoàn thành luận văn này. Em cũng xin gửi lời cảm ơn các thày, cô giáo khoa Công nghệ thông tin - Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã truyền thụ kiến thức, giúp đỡ em trong suốt quá trình học tập vừa qua. Tôi cũng xin cảm ơn gia đình, đồng nghiệp và những người thân đã cùng chia sẻ, giúp đỡ, động viên, tạo mọi điều kiện thuận lợi để tôi hoàn thành nhiệm vụ học tập và luận văn tốt nghiệp cuối khóa. Hà Nội, tháng 10 năm 2010 Học viên Lữ Đăng Nhạc LUAN VAN CHAT LUONG download : add [e-mail] 2 DANH MỤC HÌNH VẼ Hình 1.1 Mô hình phân lớp .Quá trình phân lớp . Véc tơ hai chiều x .4 Mặt phẳng phân chia hai lớp [11] .5 Các siêu phẳng phân chia tập dữ liệu [11] .6 Siêu phẳng tối ưu .7 Các véc tơ hỗ trợ .8 Biến nới lỏng cho lề mềm . Không gian đặc trưng. Mô tả kỹ thuật One against all (a) và one against one(b)[9] .11 Thẩm định chéo K-fold . Thẩm định chéo lấy mẫu ngẫu nhiên . Các toán tử chung cho thuật giải di truyền [15] .Mô hình mới dựa trên GA và SVM . Đưa dữ liệu về không gian mới .1 Các bước thực hiện để tìm ra chromosome tốt nhất.2 Hàm đánh giá của GA tại mỗi thế hệ .3 Giao diện chương trình.Kết quả thử nghiệm SVM với hàm Gaussian trên Stomach .5 Kết quả thử nghiệm của GA&SVM với hàm Gaussian trên tập Stomach.6 So sánh kết quả thực nghiệm của SVM và GA&SVM với hàm Gaussian trên tập Stomach .7 Kết quả thực nghiệm của SVM với Poly trên tập Stomach .8 Kết quả thực nghiệm của GA&SVM với Poly trên Stomach .9 So sánh kết quả thực nghiệm của SVM và GA&SVM với hàm Poly trên Stomach .10 Kết quả thử nghiệm của SVM với hàm Gaussian trên tập Yeast .11 Kết quả thử nghiệm của GA&SVM với hàm Gaussian trên tập Yeast .12 So sánh kết quả thực nghiệm của SVM và GA&SVM với hàm Gaussian trên tập Yeast . 54 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.13 Kết quả thử nghiệm của SVM với hàm Poly trên tập Yeast .14 Kết quả thử nghiệm GA&SVM với hàm Poly trên tập Yeast .15 So sánh kết quả thực nghiệm của SVM và GA&SVM với hàm Gaussian trên tập Yeast . 57 LUAN VAN CHAT LUONG download : add [e-mail] 4 DANH MỤC BẢNG BIỂU Bảng 1.Mô tả dữ liệu Stomach .Kết qủa lỗi thu được của SVM với hàm Gaussian trên tập stomach .Kết quả lỗi thu được của GA&SVM với hàm Gaussian trên Stomach .Kết quả lỗi thu được của SVM với hàm Poly trên dữ liệu Stomach. 48 Bảng 5 Kết qủa lỗi thu được của GA&SVM với hàm Poly trên tập Stomach : . 49 Bảng 6 Kết quả lỗi thu được của SVM với hàm Gaussian trên tập Yeast . 51 Bảng 7 Kết quả lỗi thu được của GA&SVM với hàm Gaussian trên tập Yeast . 52 Bảng 8 Kết quả lỗi thu được của SVM với hàm Poly trên tập Yeast . 54 Bảng 9 Kết quả lỗi thu được của GA& SVM với hàm Poly trên tập Yeast . 55 LUAN VAN CHAT LUONG download : add [e-mail] 5 BANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT Từ viết tắt Tiếng anh GA Genetic Algorithm Gas Genetic Algorithms OAA One Against All OAO One Against One SVM Suporst Vector Machine MSVM Mô hình đa phân lớp xây dựng bởi OAA và SVM Matlab Matrix Laboratory LUAN VAN CHAT LUONG download : add [e-mail] 8 MỞ ĐẦU Ngày nay cùng với việc phát triển của Khoa Học Công Nghệ thì lượng dữ liệu ngày càng trở nên lớn hơn, khai thác đươ ̣c những thông tin có ích từ lươ ̣ng dữ liê ̣u khổ n g lồ như vâ ̣y đang là vấn đề lớn đặt ra trong thực tiễn cuộc sống. Khai phá dữ liệu là một trong những lĩnh vực nghiên cứu của khoa học máy tính hiện nay đang được phát triển rất mạnh mẽ. Nó kết hợp giữa học máy, công nghệ cơ sở dữ liệu và một số chuyên ngành khác để tìm ra những tri thức, bao gồm cả các thông tin dự báo, từ những cơ sở dữ liệu lớn. Phân lớp dữ liệu được coi là một trong những vấn đề nghiên cứu mở rộng hiện nay trong Khai phá dữ liệu, hiện nay có rất nhiều dữ liệu thực tế lớn cần được phân lớp như: Việc khai thác thông tin về nhu cầu mua hàng dành cho những người bán hàng, hoặc các khả năng rủi ro trong việc cho vay tiền ở ngân hàng, hoặc việc cần phải phân biệt những người bị bệnh hoặc không bị bệnh trong một lớp dữ liệu của bệnh viện…. Như vậy việc phân tích được thông tin rất quan trọng, nhưng dữ liệu thực tế rất lớn và có rất nhiều lớp khác nhau, vậy bài toán được đặt ra ở đây là làm thế nào để phân loại được những lớp dữ liệu khác nhau càng nhiều càng tốt với độ chính xác cao. Như việc phân tích một bệnh ung thư, bệnh được chia làm nhiều giai đoạn, giờ đây điều quan tâm không những là việc xác định người bị bệnh và người không bị bệnh nữa mà còn là việc quan tâm xem người bị bệnh đang ở giai đoạn nào. Với một dữ liệu ung thư nếu xác định được giai đoạn bệnh của bệnh nhân thì khả năng những giai đoạn mới đầu là có thể được chữa khỏi, vì vậy việc đa phân lớp sẽ trở thành rất quan trọng trong việc phân lớp dữ liệu. Yêu cầu của một bài toán đa phân lớp đó là làm thế nào phân lớp dữ liệu thành nhiều lớp đạt hiệu quả cao nhất ở khả năng dự đoán những dữ liệu mới vào đúng lớp dữ liệu một cách chính xác nhất. Hiện nay có rất nhiều thuật toán phân lớp như thuật toán Support vector machines (SVM) thuật toán phân lớp bằng Học cây quyết định, mô hình Mạng lan truyền ngược (Neural Network)[8],… và có nhiều kết quả đạt được trong việc sử dụng các mô hình phân lớp này vào việc đa phân lớp[8,11,14]. Nhưng vấn đề tìm kiếm một phương pháp đủ tốt đáp ứng nhu cầu cần phải phân tích dữ liệu ra nhiều lớp khác nhau vẫn là một vấn đề hiện nay cần nghiên cứu. LUAN VAN CHAT LUONG download : add [e-mail] 9 Luận văn này tập trung tìm hiểu, xây dựng mô hình đa phân lớp mới bằng việc kết hợp một thuật toán phân lớp SVM với kĩ thuật đa phân lớp One agaist all (OAA) nhằm thực hiện đa phân lớp một tập dữ liệu. Luận văn cũng tập trung vào việc sử dụng giải thuật di truyền (GA) để tối ưu các tham số của hàm nhân Kernel của SVM phục vụ cho việc đa phân lớp nhằm tăng độ chính xác khi phân lớp của mô hình[10]. Nội dung chính của luận văn được tổ chức thành 4 chương có nội dung được mô tả như dưới đây. Thuật toán phân lớp SVM. Chương này giới thiê ̣u cơ bản về vấn đề phân lớp, các bước trong phân lớp và những yêu cầu trong vấn đề phân lớp. Chương này tập trung vào một thuật toán phân lớp SVM, nghiên cứu kỹ thuật đa phân lớp nhằm xây dựng mô hình đa phân lớp với SVM Chƣơng 2. Giải thuật di truyền. Chương này trin ̀ h bày về giải thuật di truyền, tìm hiểu và áp dụng giải thuật nhằm tối ưu các giá trị Chƣơng 3. Mô hình tối ƣu đa phân lớp SVM. Chương này trin ̀ h bầ y viê ̣c xây dựng một mô hình đa phân lớp dựa vào giải thuật di truyền, kĩ thuật One against all và SVM. Đề cập đến việc tìm kiếm các Kernel tốt cho mô hình bằng việc sử dụng giải thuật di truyền để tối ưu các tham số của Kernel. Xây dựng chƣơng trình mô phỏng. Chương này sử dụng những lý luận ở trên kết hợp với MATLAB để xây dựng mô hình phân lớp phân tích trên một số tập dữ liệu cụ thể nhằm thu được các kết quả để đánh giá mô hình mới xây dựng (GA&SVM) so với mô hình đa phân lớp SVM.