Khóa luận Áp dụng phương pháp trích chọn thuộc tính đặc trưng để nâng cao hiệu quả phân lớp khi khai phá dữ liệu lớn

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Trần Phƣơng Nhung ÁP DỤNG PHƢƠNG PHÁP TRÍCH CHỌN THUỘC TÍNH ĐẶC TRƢNG ĐỂ NÂNG CAO HIỆU QUẢ PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Trần Phƣơng Nhung ÁP DỤNG PHƢƠNG PHÁP TRÍCH CHỌN THUỘC TÍNH ĐẶC TRƢNG ĐỂ NÂNG CAO HIỆU QUẢ PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: TS. Nguyễn Hà Nam HÀ NỘI - 2009 Lời cảm ơn “Để hoàn thành khóa luận này, tôi xin gửi lời cảm ơn chân thành tới quý thầy cô trong trường Đại học Công Nghệ - ĐHQGHN đã tận tình chỉ bảo tôi trong suốt bốn năm học đại học. Tôi cũng xin cảm ơn sự hướng dẫn nhiệt tình của thầy Nguyễn Hà Nam, cùng sự giúp đỡ của anh Đặng Tất Đạt – sinh viên cao học khoa Toán Tin trường Đại học Tự Nhiên, ĐHQGHN. Tôi cũng thầm biết ơn sự ủng hộ của gia đình, bạn bè – những người thân yêu luôn luôn là chỗ dựa tinh thần vững chắc cho tôi.” Hà Nội, tháng 05 năm 2009. Sinh viên Trần Phương Nhung 1 Tóm tắt khóa luận Trong khóa luận này tôi áp dụng thuật toán di truyền (Genetic Algorithm) để bước đầu cải tiến hiệu quả phân lớp của phương pháp minimax probability machine (MPM). Phần đầu tôi xin giới thiệu tổng quan về khái niệm khai phá dữ liệu. Tiếp đó, tôi sẽ trình bày về cơ sở lý thuyết của thuật toán di truyền và phương pháp phân lớp minimax probability machine. Cuối cùng, tôi sẽ mô tả chi tiết về quá trình xây dựng hệ thống có ứng dụng thuật toán di truyền trong phân lớp minimax probability machine để chuẩn đoán bệnh ung thư. Mô hình phân lớp mới này sẽ được chạy thử trên một số cơ sở dữ liệu lớn và đưa ra những số liệu thống kê để có thể thấy được hiệu quả của hệ thống so với phương pháp phân lớp chỉ sử dụng minimax probability machine. 2 Mục lục Giới thiệu ......................................................................................................................... 8 Chương 1: Giới thiệu về khai phá dữ liệu .................................................................... 10 1.1. Khai phá dữ liệu là gì? ...................................................................................... 10 1.2. Tại sao phải tiến hành khai phá dữ liệu? ........................................................... 10 1.3. Quá trình khai phá dữ liệu ................................................................................ 11 1.4. Kiến trúc điển hình của một hệ khai phá dữ liệu ............................................... 12 1.5. Các bài toán khai phá dữ liệu điển hình ............................................................ 13 1.6. Các lĩnh vực liên quan đến khai phá dữ liệu ..................................................... 15 1.7. Các ứng dụng điển hình của khai phá dữ liệu ................................................... 15 1.8. Các thách thức với khai phá dữ liệu .................................................................. 16 1.9. Kết luận ............................................................................................................ 16 Chương 2: Trích chọn thuộc tính phù hợp .................................................................. 17 2.1. Giới thiệu ......................................................................................................... 17 2.2. Mô hình trong bài toán trích chọn ..................................................................... 18 2.2.1. Các mô hình trong trích chọn .................................................................... 18 2.2.2. Đánh giá hai mô hình Filter và Wrapper ................................................... 19 2.2.2.1. Mô hình Filter .................................................................................... 19 2.2.2.2. Mô hình Wrapper ............................................................................... 19 2.3. Một số kỹ thuật xử lý........................................................................................ 20 2.3.1. Bộ sinh tập con (Feature Subset Generator) .............................................. 20 2.3.2. Bộ đánh giá tập con đặc trưng (Feature Subset Evaluator) ....................... 21 2.3.3. Thuật toán học điều khiển (Central machine learning algorithm) .............. 22 2.4. Kết luận ............................................................................................................ 22 3 Chương 3: Genetic algorithms ..................................................................................... 23 3.1. Giới thiệu ........................................................................................................... 23 3.2. Động lực ............................................................................................................ 23 3.3. Thuật giải di truyền ............................................................................................ 24 3.3.1. Nội dung thuật toán ....................................................................................... 24 3.3.2. Thể hiện các giả thuyết .................................................................................. 26 3.3.3. Các toán tử di truyền ..................................................................................... 27 3.3.4. Hàm thích nghi và sự chọn lọc ....................................................................... 29 Chương 4: Minimax probability machine ................................................................... 31 4.1. Giới thiệu ........................................................................................................... 31 4.2. Nội dung thuật toán ............................................................................................ 31 4.3. Ưu điểm và nhược điểm của minimax probability machine ................................ 32 4.4. Các phiên bản cải tiến của minimax probability machine ................................... 32 4.4.1. Minimum error minimax probability machine (MEMPM) .............................. 32 4.4.2. Biased minimax probability machine (BMPM) ............................................... 34 Chương 5: Phương pháp đề nghị ................................................................................. 35 5.1. Tổng quan về phương pháp .............................................................................. 35 5.1.1. Mô tả phương pháp ................................................................................... 35 5.1.2. Mô hình bài toán ....................................................................................... 36 5.2. Mô tả dữ liệu sử dụng ....................................................................................... 36 5.3. Các module trong hệ thống và giao diện của chương trình ................................ 37 5.3.1. Chi tiết các module của Genetic Algorithm ............................................... 37 5.3.2. Chi tiết các module của minimax probability machine............................... 41 5.4. Thực nghiệm và phân tích kết quả .................................................................... 43 5.4.1. Phương pháp đánh giá ................................................................................... 43 5.4.2. Phân tích kết quả ........................................................................................... 44 4 5.4.2.1. Kết quả thực hiện phân lớp trên bộ dữ liệu ban đầu ................................. 44 5.4.2.2. Kết quả thực hiện phân lớp trên bộ dữ liệu giảm chiều (outData.mat) ...... 45 5.4.2.3. So sánh kết quả 4 trường hợp kiểm thử .................................................... 51 5.4.2.4. Kết luận ................................................................................................... 52 Chương 6: Tổng kết ...................................................................................................... 53 5 Danh sách các hình Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu [2]. ........................................ 12 Hình 1.2: Kiến trúc điển hình của hệ thống khai phá dữ liệu [2]. .................................... 13 Hình 1.3: Tính đa/ liên ngành của khai phá dữ liệu [2]. .................................................. 15 Hình 2.1: Bốn bước cơ bản trong quá trình trích chọn các thuộc tính phù hợp [6]. ......... 17 Hình 2.2: Mô hình Filter [6] ........................................................................................... 18 Hình 2.3: Mô hình Wrapper [6] ...................................................................................... 18 Hình 3.1: Các toán tử chung cho thuật giải di truyền [20]............................................... 28 Hình 4.1: Mô tả sự khác nhau giữa MEMPM (h.1) và MPM (h.2) với cùng xác suất tiên nghiệm cho 2 lớp. [17] .................................................................................................... 34 Hình 5.1: Mô hình kết hợp thuật toán di truyền và phương pháp phân lớp MPM. ........... 36 Hình 5.2: 6 bước thực hiện để tìm ra chromosome tốt nhất. ............................................ 38 Hình 5.3: Giá trị của hàm đánh giá tại mỗi thế hệ. .......................................................... 39 Hình 5.4: Hình ảnh biểu diễn hàm đánh giá của GA tại mỗi thế hệ. ................................ 40 Hình 5.5: Kết quả quá trình tối ưu tập thuộc tính của dữ liệu ban đầu............................. 41 Hình 5.6: Giao diện kết quả của bộ phân lớp minimax probability machine. .................. 42 Hình 5.7: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 1). ................................................................................................................................... 46 Hình 5.8: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 2). ................................................................................................................................... 47 Hình 5.9: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 3). ................................................................................................................................... 49 Hình 5.10: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 4). ............................................................................................................................ 50 Hình 5.11: So sánh kết quả phân lớp trung bình trong 4 trường hợp kiểm thử và kết quả phân lớp của dữ liệu gốc. ................................................................................................ 51 6 Danh sách các bảng Bảng 3.1: Thuật giải di truyền mẫu. [20] ........................................................................ 24 Bảng 5.1: Mô tả bảng dữ liệu sử dụng (file Stomach_Full.mat) ...................................... 37 Bảng 5.2: Kết quả phân lớp trên bộ dữ liệu ban đầu ....................................................... 44 Bảng 5.3: Kết quả phân lớp trong trường hợp 1 .............................................................. 45 Bảng 5.4: Kết quả phân lớp trong trường hợp 2 .............................................................. 46 Bảng 5.5: Kết quả phân lớp trong trường hợp 3 .............................................................. 48 Bảng 5.6: Kết quả phân lớp trong trường hợp 4. ............................................................. 49 7 Bảng các từ viết tắt Biased Minimax Probability Machine BMPM Genetic Algorithm GA Genetic Algorithms Gas Las Vegas LV Matlab Matrix Laboratory Minimax Probability Machine MPM Minimum Error Minimax Probability Machine MEMPM Online Analytical Processing OLAP 8 Giới thiệu Những năm gần đây, các cơ sở dữ liệu đã đem lại những lợi ích vô cùng to lớn cho con người. Song hành cùng sự phát triển nhanh chóng của công nghệ thông tin và những ứng dụng của nó trong đời sống, kinh tế và xã hội, lượng dữ liệu thu thập ngày càng nhiều theo thời gian, dẫn đến việc xuất hiện ngày càng nhiều các hệ thống cơ sở dữ liệu có kích thước lớn. Trong xã hội hiện đại, thông tin được coi như sức mạnh và là yếu tố quyết định thành công trong mọi lĩnh vực, do đó việc tìm ra thông tin hữu ích trong khối dữ liệu khổng lồ được xem như mục tiêu hàng đầu của mọi tổ chức và cá nhân. Trong khóa luận này, tôi sẽ ứng dụng kỹ thuật chọn lựa tập các thuộc tính có ích trong bài toán trích chọn để nhằm cải thiện hiệu quả phân lớp dữ liệu, là nền tảng cho hệ thống chuẩn đoán bệnh ung thư. Hệ thống này sẽ được huấn luyện với tập dữ liệu về các bệnh nhân có từ trước và khi có dữ liệu của bệnh nhân mới, hệ thống sẽ tự động đưa ra chuẩn đoán người đó có bị bệnh hay không? Tôi sử dụng phương pháp phân lớp Minimax Probability Machine (MPM) kết hợp cùng thuật toán di truyền (Genetic Algorithm) để xây dựng hệ thống này. Với mục đích làm tăng độ chính xác của quá trình phân lớp dữ liệu và giảm thời gian huấn luyện của bộ phân lớp, tôi sử dụng thuật toán di truyền để lựa chọn tập thuộc tính tốt nhất của tập dữ liệu ban đầu nhằm tìm ra bộ dữ liệu phù hợp nhất cho đầu vào của bộ phân lớp MPM. Kết quả thực nghiệm đã chứng minh rằng phương pháp phân lớp sử dụng thuật toán di truyền để tối ưu tập thuộc tính cho kết quả tốt hơn phương pháp truyền thống. Nội dung chính của khóa luận bao gồm sáu chương, với nội dung cụ thể như sau: Chương 1 tập trung mô tả về khai phá dữ liệu (data mining), giới thiệu những bài toán điển hình trong khai phá dữ liệu cũng như những ứng dụng rộng rãi của lĩnh vực này. Cuối cùng là những thách thức đặt ra cho quá trình khai phá dữ liệu. Chương 2 có nội dung chủ yếu trình bày về khái niệm trích chọn thuộc tính phù hợp, những mô hình trích chọn điển hình và một số kỹ thuật xử lý trong quá trình trích chọn. Chương 3 giới thiệu về cơ sở lý thuyết cũng như những bước thực hiện của thuật toán di truyền. Thuật toán này được sử dụng để tìm ra tập các thuộc tính phù hợp nhất với thuật toán MPM sẽ được trình bày ở chương sau. 9 Chương 4 sẽ mô tả phương pháp phân lớp minimax probability machine. Phân tích những mặt mạnh và yếu của phương pháp này để đề ra những cải tiến nhằm nâng cao hiệu quả phân lớp của minimax probability machine. Chương 5 trình bày chi tiết quá trình xây dựng mô hình dự kiến của tôi bao gồm phân lớp minimax probability machine kết hợp với thuật toán di truyền. Phần còn lại của chương dùng để mô tả quá trình đánh giá chất lượng, từ đó đưa ra những phân tích kỹ thuật và kết luận về hiệu quả của mô hình. Chương 6 tóm tắt lại những kết quả đã đạt được của khóa luận, đồng thời nêu ra những mặt còn hạn chế trong phương pháp đề nghị và những hướng nghiên cứu có thể trong tương lai nhằm cải tiến hiệu quả của phương pháp này. 10 Chương 1: Giới thiệu về khai phá dữ liệu 1.1. Khai phá dữ liệu là gì? Có khá nhiều định nghĩa về khai phá dữ liệu, nhưng định nghĩa đơn giản nhất là khai phá dữ liệu là việc trích rút thông tin hay tri thức mới và có ích từ nguồn dữ liệu khổng lồ (Frawley, Piatetski-Shapiro và Matheus) [1]. Ngoài ra, khai phá dữ liệu còn có thể hiểu là trích rút các thông tin có ích từ những dữ liệu không tường minh, hoặc trích rút lấy những thông tin không biết trước và tiềm tàng trong dữ liệu. Cũng có thể hiểu, khai phá dữ liệu là việc phân tích khảo sát một cách tỉ mỉ số lượng lớn dữ liệu bằng các phương pháp tự động hoặc bán tự động nhằm tìm ra các thông tin hay tri thức có ích. Có thể nhận xét rằng, khái niệm khai phá dữ liệu là khá rộng lớn, nhưng không phải tất cả mọi công việc liên quan đến dữ liệu đều được coi là khai phá dữ liệu, chẳng hạn như những việc xử lý truy vấn đơn giản như tra cứu một số điện thoại, hay thống kê ra những học sinh giỏi của một lớp, thì không thể coi đó là khai phá dữ liệu. Nhưng những công việc như gom nhóm các tài liệu trả về từ máy tìm kiếm theo từng ngữ cảnh thì lại được xem là khai phá dữ liệu. Chính vì sự phong phú và đa dạng này mà dẫn đến thực trạng là tồn tại một số quan niệm khác nhau về chuyên ngành nghiên cứu gần gũi nhất với lĩnh vực khai phá dữ liệu. Tài liệu này của tôi tán thành quan điểm về khai phá dữ liệu của Frawley, Piatetski-Shapiro và Matheus [1]. 1.2. Tại sao phải tiến hành khai phá dữ liệu? Trong những năm gần đây, khai phá dữ liệu trở thành một lĩnh vực nghiên cứu rộng rãi trong ngành công nghiệp thông tin, nguyên nhân chủ yếu là do khối lượng khổng lồ của dữ liệu mà con người tạo ra, đi kèm với nó là sự cần thiết của việc rút trích tri thức từ những dữ liệu đó. Thông tin và tri thức có thể được áp dụng vào nhiều lĩnh vực từ phân tích thị trường tài chính, phát hiện giả mạo, cho đến điều khiển sản xuất và nghiên cứu khoa học. Nhìn vào hai lĩnh vực sinh ra nhiều dữ liệu nhất đó là thương mại và khoa học. Trong lĩnh vực thương mại, hàng ngày hàng giờ con người đang tạo ra, thu thập và lưu trữ lại rất nhiều dữ liệu, như dữ liệu web, dữ liệu về thương mại điện tử, dữ liệu về việc thanh toán tại các cửa hàng và các dữ liệu thanh toán trong các tài khoản… Tính cạnh tranh trong 11 kinh doanh là rất cao, cho nên việc phân tích dữ liệu để cung cấp dịch vụ tốt hơn, có nhiều tiện ích cho khách hàng, và đón bắt chính xác nhu cầu của khách hàng rất quan trọng. Trong lĩnh vực khoa học, dường như lượng dữ liệu sinh ra và thu thập lại còn lớn hơn nhiều, lên tới hàng GB/giờ, chẳng hạn như dữ liệu từ vệ tinh, từ các ảnh chụp vũ trụ và từ các mô phỏng thử nghiệm khoa học. Khai phá dữ liệu giúp các nhà khoa học trong việc phân lớp dữ liệu và hỗ trợ trong việc đưa ra các quyết định. Cùng với sự phát triển của khoa học, của ngành cơ sở dữ liệu không thể không kể đến là sự phát triển của ngành công nghiệp máy tính, người ta đã tạo ra những phương tiện lưu trữ lớn hơn, những máy tính rẻ hơn, tốc độ cao hơn, trợ giúp cho quá trình thu thập dữ liệu cũng như khai phá chúng. Trong quá trình tác nghiệp, người ta thường phải đưa ra các quyết định, tuy nhiên, với lượng dữ liệu khổng lồ như thế, người ta không thể sử dụng hết, hoặc nếu muốn sử dụng thì phải mất thời gian quá nhiều, như vậy có nguy cơ đánh mất cơ hội. Do đó, việc sử dụng máy tính để khai phá dữ liệu nhằm giúp đỡ con người trong công việc càng được thúc đẩy mạnh mẽ, làm sao với các dữ liệu đã thu thập được có thể đưa ra hành động mang lại lợi ích tối đa. 1.3. Quá trình khai phá dữ liệu Ở một góc độ nào đó, khái niệm khai phá dữ liệu và khai phá tri thức nhiều khi được coi là một. Tuy nhiên, nếu xét kỹ thì khai phá dữ liệu chỉ là một khâu quan trọng trong khai phá tri thức [1]. Một quá trình phát hiện tri thức trong cơ sở dữ liệu bao gồm các giai đoạn chính sau [2]: (1) Làm sạch dữ liệu (Data Cleaning): Khử nhiễu và các dữ liệu mâu thuẫn. (2) Tích hợp dữ liệu (Data Integration): Kết hợp nhiều nguồn dữ liệu khác nhau. (3) Lựa chọn dữ liệu (Data Selection): Chắt lọc lấy những dữ liệu liên quan đến nhiệm vụ phân tích sau này. (4) Biến đổi dữ liệu (Data Transformation): Biến đổi dữ liệu thu được về dạng thích hợp cho quá trình khai phá. (5) Khai phá dữ liệu (Data Mining): Sử dụng những phương pháp thông minh để khai thác dữ liệu nhằm thu được các mẫu mong muốn. (6) Đánh giá kết quả (Pattern Evaluation): Sử dụng các độ đo để đánh giá kết quả thu được. 12 (7) Biểu diễn tri thức (Knowledge Presentation): Sử dụng các công cụ biểu diễn trực quan để biểu diễn những tri thức khai phá được cho người dùng. Hình 1.1: Quá trình phát hiện tri thức trong cơ sở dữ liệu [2]. Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. 1.4. Kiến trúc điển hình của một hệ khai phá dữ liệu Trong kiến trúc điển hình của một hệ khai phá dữ liệu (hình 1.2), các nguồn dữ liệu cho hệ thống khai phá dữ liệu bao gồm cơ sở dữ liệu, hoặc kho dữ liệu, hoặc World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác, hoặc tổ hợp các kiểu dữ liệu nói trên. Cơ sở tri thức bao chứa các tri thức hiện có về miền ứng dụng, được sử dụng trong thành phần khai phá dữ liệu để tăng tính hiệu quả của thành phần này. Một số tham số của thuật toán khai phá dữ liệu tương ứng sẽ tinh chỉnh theo tri thức miền sẵn có từ cơ sở tri thức trong hệ thống. Cơ sở tri thức còn được sử dụng trong việc đánh giá các mẫu đã khai phá được xem chúng có thật sự đúng đắn hay không, trong đó có đối chứng với các tri Tri thức Đánh giá & Trình diễn Lựa chọn & Chuyển dạng Dữ liệu Kho dữ liệu Khai phá dữ liệu Dữ liệu chuyển dạng Mẫu Làm sạch & Tích hợp 13 thức đã có trong cơ sở tri thức. Nếu mẫu khai phá được thực sự là hấp dẫn thì được bổ sung vào cơ sở tri thức để phục vụ cho hoạt động tiếp theo của hệ thống. Hình 1.2: Kiến trúc điển hình của hệ thống khai phá dữ liệu [2]. 1.5. Các bài toán khai phá dữ liệu điển hình Hai mục tiêu chủ yếu của khai phá dữ liệu là dự báo (prediction) và mô tả (description). Dự báo dùng một số biến hoặc trường trong trong cơ sở dữ liệu để dự đoán về giá trị chưa biết hoặc về giá trị sẽ có trong tương lai của các biến. Mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu. Dự báo và mô tả được thể hiện thông qua các bài toán cụ thể sau [2]:  Mô tả khái niệm (Summarization) Mục đích của bài toán là tìm ra các đặc trưng và tính chất của các khái niệm. Điển hình cho bài toán này là các bài toán như tổng quát hóa, tóm tắt, các đặc trưng dữ liệu ràng buộc. Giao diện người dùng Đánh giá mẫu khai phá được Thành phần khai phá dữ liệu Phục vụ Cơ sở dữ liệu/ Kho dữ liệu Kho dữ liệu World Wide Web Kiểu kho chứa thông tin khác Cơ sở tri thức Làm sạch, tích hợp và chọn lựa dữ liệu Cơ sở dữ liệu 14  Quan hệ phụ thuộc (Dependency relationship) Một trong những vấn đề của phát hiện mối quan hệ là làm rõ ràng và nguyên nhân. Bài toán tìm luật kết hợp là một đại diện điển hình, thực hiện việc phát hiện ra mối quan hệ giữa các thuộc tính (các biến), có dạng ở phụ thuộc hàm trong cơ sở dữ liệu quan hệ.  Phân lớp (Classification)[5] Phân lớp còn được gọi là học máy có giám sát (supervised learning). Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại (classifier) dùng để phân dữ liệu mới vào trong những lớp (còn gọi là loại) đã được định trước. Một số phương pháp điển hình là cây quyết định, luật phân lớp, mạng neuron.  Phân cụm (Clustering) Phân cụm còn được gọi là học máy không giám sát (unsupervised learning), thực hiện việc nhóm dữ liệu thành các lớp mới để có thể phát hiện các mẫu phân bố. Phân cụm chỉ là bái toán mô tả hướng tới việc nhận biết một tập hữu hạn các loại hoặc các cụm để mô tả dữ liệu. Các loại (cụm) có thể rời nhau và toàn phần (tạo nên phân hoạch) hoặc chồng chéo lên nhau [3].  Phân đoạn (Segmentation) Về bản chất phân đoạn là tổ hợp của phân cụm và phân lớp, trong đó phân cụm được tiến hành trước và sau đó là phân lớp.  Hồi quy (Regression) Hồi quy là học một hàm ánh xạ dữ liệu nhằm tìm và xác định giá trị thực của một biến.  Mô hình phụ thuộc (Dependency modeling) Bài toán xây dựng mô hình phụ thuộc hướng tới việc tìm ra một mô hình mô tả sự phụ thuộc có ý nghĩa giữa các biến. Mô hình phụ thuộc gồm hai mức: mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị) và mức định lượng.  Phát hiện biến đổi và độ lệch (Change and Deviation Detection) Tập trung vào việc phát hiện hầu hết sự thay đổi có ý nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn. 15 1.6. Các lĩnh vực liên quan đến khai phá dữ liệu Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực như thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu... Đặc biệt khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật. Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến (OLAP – Online Analytical Processing) cũng liên quan chặt chẽ với khai phá dữ liệu [2]. Các kỹ thuật truyền thống không còn thích hợp với các loại dữ liệu bị lỗi, bị nhiễu hay dữ liệu nhiều chiều và các hệ dữ liệu tự nhiên phân tán hay hỗn tạp. Do đó khi kết hợp với nhau, hình thành lĩnh vực mới, đó là khai phá dữ liệu. Hình 1.3: Tính đa/ liên ngành của khai phá dữ liệu [2]. 1.7. Các ứng dụng điển hình của khai phá dữ liệu Ứng dụng của khai phá dữ liệu được chia thành hai lớp chính bao gồm các ứng dụng phân tích – hỗ trợ ra quyết định và lớp các lĩnh vực ứng dụng khác.  Lớp các ứng dụng trong phân tích dữ liệu và hỗ trợ ra quyết định bao gồm các ứng dụng trong [2] [4]: - Thông tin thương mại: Phân tích dữ liệu Marketing, khách hàng; Phân tích đầu tư; Phê duyệt cho vay vốn hay phát hiện gian lận. - Thông tin kỹ thuật: Điều khiển và lập trình lịch; Quản trị mạng. Khai phá dữ liệu Hệ thống cơ sở dữ liệu Thống kê Học máy Thuật toán Các bộ môn khác Trực quan hóa 16 - Bảo hiểm y tế. - Viễn thông. - Thể thao  Lớp các lĩnh vực ứng dụng điển hình khác được kể đến là khai phá văn bản, khai phá Web, khai phá dữ liệu sinh học và khai phá dữ liệu dòng. 1.8. Các thách thức với khai phá dữ liệu  Cơ sở dữ liệu lớn.  Số chiều lớn.  Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp.  Dữ liệu bị thiếu hoặc bị nhiễu.  Quan hệ giữa các trường phức tạp.  Giao tiếp với người sử dụng và kết hợp với các tri thức đã có.  Tích hợp với các hệ thống khác [2] [4] … 1.9. Kết luận Qua các vấn đề đã trình bày, chúng ta nhận thấy với một lượng dữ liệu thực tế nhỏ và với mục đích bài toán cụ thể nhưng ta có thể tiếp cận theo nhiều hướng khác nhau của cùng một phương pháp khai phá dữ liệu và đạt được kết quả khác nhau, điều đó càng làm sáng tỏ khả năng ứng dụng thực tế to lớn đồng thời với những thách thức đối với kỹ thuật khai phá dữ liệu trong các bài toán kinh tế - xã hội và trong nhiều lĩnh vực khác. 17 Chương 2: Trích chọn thuộc tính phù hợp 2.1. Giới thiệu Trích chọn đặc trưng (Feature Selection) là phương pháp chọn ra một tập con tốt nhất từ tập các đặc trưng đầu vào bằng cách lọai bỏ những đặc trưng có rất ít hoặc không có thông tin dự đoán. Trích chọn đặc trưng có vai trò quan trọng trong việc chuẩn bị và lựa chọn dữ liệu cho quá trình khai phá dữ liệu. Nó sẽ làm giảm kích cỡ của không gian đặc trưng, loại bỏ dư thừa hay nhiễu của dữ liệu. Phương pháp này có thể tìm chính xác những tập con đặc trưng có khả năng dự đoán, do đó giúp cải thiện đáng kể kết quả thu được trong các mô hình phân lớp. Về cơ bản, quá trình trích chọn đặc trưng bao gồm bốn bước cơ bản: sinh tập con (subset generation), đánh giá tập con (subset evaluation), kiểm tra điều kiện dừng của quá trình trích chọn (stopping criterion) và kết quả (result validation). Hình 2.1: Bốn bước cơ bản trong quá trình trích chọn các thuộc tính phù hợp [6]. Subset generation là một thủ tục tìm kiếm. Về cơ bản, nó sinh ra một tập con của tập các đặc trưng để đánh giá. Giả sử có N đặc trưng trong tập dữ liệu gốc, thì số lượng các tập con tiềm năng là 2n. Vì một tập con tối ưu các điểm đặc trưng không phải là duy nhất nên số lượng các tập con có thể thỏa mãn là rất lớn, do đó quá trình tìm kiếm trong trích chọn đặc trưng sẽ tốn nhiều thời gian và công sức. Mỗi tập con được sinh ra cần phải được đánh giá và so sánh với những tập con tốt nhất đã được tìm thấy trước. Nếu tập con tìm thấy sau là tốt hơn thì nó sẽ được thay thế cho tập con tốt nhất trước đây. Nếu không Original Set Subset Generation Subset Evaluation Result Validation Stopping Criterion YES NO Goodness of Subset Subset 18 có một điều kiện dừng hợp lý thì quá trình tìm kiếm các tập con tốt nhất sẽ được xem như là vô hạn. Một quá trình trích chọn đặc trưng có thể dừng khi thỏa mãn một trong những điều kiện đánh giá sau: (a) chọn đủ số lượng đã được xác định trước của tập đặc trưng, (b) thỏa mãn số lần đã được xác định trước của quá trình lặp lại. (c) ở một khía cạnh (điều kiện) nào đó tập con mới được đánh giá là không tốt hơn tập con trước, (d) tập con được bộ đánh giá cho là tốt nhất [6]. 2.2. Mô hình trong bài toán trích chọn 2.2.1. Các mô hình trong trích chọn Trích chọn đặc trưng thật sự là lý tưởng trong lựa chọn tập con đặc trưng tối ưu từ một tập ứng cử để mô tả khái niệm mục tiêu trong hệ thống học. Độ tốt của một tập con đặc trưng có thể được đánh giá qua nhiều cách khác nhau, nhờ đó mà có nhiều mô hình khác nhau được đưa ra trong phương pháp trích chọn. Điển hình là hai mô hình: Filter và Wrapper [10]. Hình 2.2: Mô hình Filter [6] Hình 2.3: Mô hình Wrapper [6] Giải thích hình vẽ: A: Tập đặc trưng đầu vào. 1: Bộ sinh tập con (Feature Subset Generator). 1 2 4 Wrapper Model 3 A 1 2 Filter Model 3 A 19 2: Bộ đánh giá (Feature Subset Evaluator). 3: Các thuật toán học máy (Followed Machine learning Algorithm) 4: Thuật toán học máy điều khiển (Central Machine learning Algorithm). Mô hình Filter đánh giá mỗi cá thể bằng một vài tiêu chuẩn hay độ đo nào đó, rồi chọn ra tập con các thuộc tính được đánh giá cao nhất. Nhìn chung, Filter coi tiến trình của trích chọn thuộc tính như tiến trình thực thi trước, sau đó mới sử dụng thuật toán để phân lớp. Wrapper sử dụng một thuật toán tìm kiếm để đánh giá tập con các thuộc tính coi như là một nhóm hơn là một cá thể riêng lẻ. Cốt lõi của mô hình Wrapper là một thuật toán máy học cụ thể. Nó đánh giá độ tốt của những tập con đặc trưng tùy theo độ chính xác học của tập con, điều này xác định thông qua một tiêu chí nào đó. Những thuật toán tìm kiếm cũng sử dụng hàm đánh giá kinh nghiệm (heuristics) để hướng dẫn việc tìm kiếm tập trung vào các đối tượng có triển vọng. 2.2.2. Đánh giá hai mô hình Filter và Wrapper 2.2.2.1. Mô hình Filter  Ưu điểm: - Không có xử lý học máy trong quá trình lựa chọn các đặc trưng. - Dễ dàng nhận diện và thời gian tiêu thụ ít hơn mô hình Wrapper.  Nhược điểm: - Hiệu suất sản sinh các tập con đặc trưng là không đảm bảo vì nó thường đánh giá một tập con đặc trưng chỉ dựa trên đặc trưng nhỏ thiên về nguyên lý mà không tính tới độ chính xác của kết quả học máy. - Kết quả thu được bị giảm sút về độ chính xác học ở những giai đoạn sau vì các hàm đánh giá hiện thời được sử dụng thường thiên về giá trị ở một vài phạm vi, do đó sẽ không đánh giá một cách khách quan tầm quan trọng của các đặc trưng. 2.2.2.2. Mô hình Wrapper  Ưu điểm: - Đảm bảo hiệu suất của kết quả học hơn mô hình Filter.  Nhược điểm: - Ít được sử dụng hơn môt hình Filter trên thực tế vì: 20  Tiến trình học tốn kém về thời gian đến mức thời gian thực hiện đưa ra bởi một thuật toán sử dụng mô hình Wrapper là không chấp nhận được.  Với một hệ thống kích thước cực lớn, mô hình này không thực tế do phạm vi của nó buộc phải thu nhỏ lại trước khi thuật toán học máy được áp dụng.  Kết quả đánh giá của mô hình phụ thuộc nhiều vào thuật toán học máy điều khiển. 2.3. Một số kỹ thuật xử lý 2.3.1. Bộ sinh tập con (Feature Subset Generator) Tùy từng chiến lược cụ thể, bộ sinh tập con sẽ tạo ra những tập con đặc trưng từ một tập đầu vào tương ứng. Đầu ra của bộ sinh sẽ xác định thuật toán trích chọn đặc trưng của việc tìm đường và tìm kiếm phạm vi trong một không gian đặc trưng tương ứng. Nói chung, bộ sinh có hai chiến lược để sản sinh ra những tập con đặc trưng:  Đầy đủ (Completely): Một bộ khởi tạo đầy đủ có thể sản sinh ra tất cả các tập con từ một tập đặc trưng đầu vào, do vậy phạm vi tìm kiếm của chiến lược này là NP đầy đủ, tuy nhiên điều này không phải lúc nào cũng chứng tỏ tìm kiếm vét cạn là cần thiết trong thực tế, bởi vì một số công nghệ như: đường biên và rẽ nhánh có thể được áp dụng để lược bớt phạm vi tìm kiếm tốt nhất. Bởi vậy nếu là thuật toán trích chọn với bộ khởi tạo đầy đủ, thực nghiệm chỉ ra rằng không gian tìm kiếm lớn nhất là O(2k). Mà đối với hầu hết những hệ thống học máy thực, điều này là không cần thiết phải đánh giá tất cả những tập con từ một tập đặc trưng tương ứng. Thường thì, thuật toán trích chọn với bộ khởi tạo đầy đủ có thể tìm ra một tập con đặc trưng tối ưu của hệ thống học máy nhưng đòi hỏi thời gian thực thi phức tạp. Liu H. [10] đã đưa ra bộ khởi tạo đầy đủ đặc biệt mà sản sinh một cách ngẫu nhiên ra những tập con đặc trưng dựa vào thuật toán Las Vegas (LV). Thuật toán LV có thể tìm kiếm trên toàn bộ không gian đáp án rồi sau đó đưa ra kết quả tối ưu đảm bảo. Tuy nhiên khác với những bộ khởi tạo đầy đủ khác, đối với một ứng dụng thực tế, khả năng thực thi của bộ khởi tạo Liu là hoàn toàn thay đổi, nó phụ thuộc nhiều vào quá trình phân chia dữ liệu ngẫu nhiên trong toàn bộ hệ thống học máy.  Kinh nghiệm (Heuristically): Để lược bớt không gian tìm kiếm, bộ khởi tạo kinh nghiệm sản sinh ra các tập con đặc trưng dựa vào những chiến lược dựa theo kinh nghiệm nào đó. Có ba kỹ thuật tìm kiếm tập con điển hình là: 21 - Lựa chọn tiến (Forward Selection): Các tập con đặc trưng được khởi tạo trước hết là rỗng (null), sau đó liên tục gán những tính năng tốt nhất hiện thời cho tập con đó cho đến khi không còn tính năng nào nữa hay các điều kiện thực thi đưa ra đã được tiếp nhận hết. - Lược bỏ lùi (Backward Elimination): Các tập con đặc trưng được khởi tạo trước hết là đầy đủ các đặc trưng, sau đó loại bỏ lần lượt những đặc trưng kém nhất hiện thời từ các tập con đó, cho đến khi không còn đặc trưng nào hoặc các điều kiện thực thi đưa ra đã được triệt tiêu hết. - Lựa chọn hai hướng (Bi – direction Selection): Các tập con đặc trưng được khởi tạo trước hết là rỗng, đầy, hoặc sản sinh ngẫu nhiên một tập con đặc trưng, sau đó liên tục hoặc là gán tính năng tốt nhất hiện thời cho tập con đó hoặc là triệt tiêu tính năng kém nhất từ các tập con đó. Để từ đó đưa ra những giá trị định hướng tốt nhất ở mỗi lần lặp lại đó. Quá trình tiếp tục cho tới khi tất cả điều kiện được đưa ra từ trước đã được tiếp nhận hết. Bộ phận khởi tạo dựa trên kinh nghiệm giảm thiểu phạm vi tìm kiếm đa thức số mũ, do đó giảm thời gian thực hiện thuật toán phức tạp trong phương pháp trích chọn. Tuy nhiên, thuật toán chỉ đưa ra một lượng nhỏ kết quả tối ưu, khi thực hiện tìm đường và tìm kiếm phạm vi của bộ phận khởi tạo, kết quả này được đảm bảo thông qua những thuật toán này. 2.3.2. Bộ đánh giá tập con đặc trưng (Feature Subset Evaluator) Hiệu suất của một tập con đặc trưng được đánh giá dựa trên cơ sở nào đó mà bộ đánh giá đạt được. Bộ đánh giá của những mô hình thuật toán khác nhau là khác nhau. Bộ đánh giá của mô hình Filter thường là các hàm đánh giá, trong khi của mô hình Wrapper là độ học chính xác đạt được bởi quá trình thực thi thuật toán học máy điều khiển trên hệ thống học.  Hàm đánh giá Những hàm đánh giá điển hình dùng để đo đạc và phân biệt khả năng phân lớp của những đặc điểm khác nhau trên các mẫu. Thực tế, các hàm đánh giá khác nhau thường được dùng hiện nay như: xấp xỉ chất lượng (Approximation Quality), độ quan trọng của thuộc tính (Feature Importance), trọng số của thuộc tính (Feature Weight).  Học chính xác 22 Trong mô hình Wrapper, để ước lượng độ học máy chính xác, trước hết, các mẫu của huấn luyện phải được chia ngẫu nhiên làm hai tập dữ liệu, bao gồm: tập huấn luyện và tập kiểm tra, trong đó, cấu trúc của hai hệ thống con có cùng đặc điểm và được tạo ra bởi bộ sinh; sau đó mô hình được huấn luyện (training) để tìm ra tham số tối ưu và các tham số này được kiểm chứng lại nhờ quá trình kiểm tra kết quả học thông qua tập kiểm tra (Validation set). Hiển nhiên, độ chính xác đạt được trong trường hợp này là giá trị ngẫu nhiên, nó phụ thuộc lớn vào kết quả của việc chia mẫu. Để tăng mức độ ổn định của việc ước lượng độ chính xác học máy, bộ đánh giá của mô hình Wrapper thường được sử dụng cùng kỹ thuật kiểm tra chéo (Cross Validation) [11]. 2.3.3. Thuật toán học điều khiển (Central machine learning algorithm) Trong mô hình Wrapper, thuật toán học máy điều khiển có ảnh hưởng lớn tới ước lượng độ chính xác học của một tập con đặc trưng. Do vậy, thuật toán đóng vài trò quyết định trong mô hình Wrapper. Thuật toán thường được chọn ở ví trí trung tâm mô hình thường là: ID3, CN2, C4.5 … 2.4. Kết luận Trích chọn được xem như bước tiền xử lý dữ liệu. Phương pháp này lọc ra những đặc trưng tốt nhất, đồng thời loại bỏ nhiễu, giảm bớt chiều trong dữ liệu. Hai mô hình phổ biến trong phương pháp trích chọn thuộc tính đặc trưng là Filter và Wrapper. Mỗi mô hình đều có những ưu điểm và nhược điểm riêng. Tùy từng yêu cầu và trường hợp cụ thể mà ta có thể áp dụng một trong hai mô hình này. 23 Chương 3: Genetic algorithms 3.1. Giới thiệu Thuật toán di truyền là thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc tự nhiên và tiến hóa di truyền. Thuật toán di truyền được ứng dụng đầu tiên trong hai lĩnh vực chính: tối ưu hóa và học máy. Trong lĩnh vực tối ưu hóa thuật toán di truyền được phát triển nhanh chóng và ứng dụng trong nhiều lĩnh vực khác nhau như tối ưu hàm, xử lý ảnh, bài toán hành trình người bán hàng, nhận dạng hệ thống và điều khiển. Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể xem như một tiên đề đúng, không chứng minh được, nhưng phù hợp với thực tế khách quan. Quá trình tiến hóa thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước bởi tính kế thừa và đấu tranh sinh tồn. 3.2. Động lực Thuật giải di truyền cung cấp một phương pháp học được thúc đẩy bởi sự tương tự với sự tiến hóa sinh học. Thay vì tìm kiếm các giả thuyết từ tổng quát đến cụ thể hoặc từ đơn giản đến phức tạp, GAs tạo ra các giả thuyết kế tiếp bằng cách lặp việc đột biến và việc tái hợp các phần của giả thuyết được biết hiện tại là tốt nhất. Ở mỗi bước, một tập các giả thuyết được gọi là quần thể hiện tại được cập nhật bằng cách thay thế vài phần nhỏ quần thể bởi cá thể con của các giả thuyết tốt nhất ở thời điểm hiện tại. Sự phổ biến của GAs được thúc đẩy bởi các yếu tố sau:  Tiến hóa là một phương pháp mạnh và thành công cho sự thích nghi bên trong các hệ thống sinh học.  GA có thể tìm kiếm trên các không gian giả thuyết có các phần tương tác phức tạp, ở đó ảnh hưởng của mỗi phần lên toàn thể độ thích nghi giả thuyết khó có thể mô hình hóa.  Thuật giải GA có thể được thực hiện song song và có thể tận dụng thành tựu của phần cứng máy tính. 24 3.3. Thuật giải di truyền 3.3.1. Nội dung thuật toán Bài toán dành cho GAs là tìm kiếm trên không gian các giả thuyết ứng cử để xác định giả thuyết tốt nhất. Trong GAs “giả thuyết tốt nhất” được định nghĩa như là một giả thuyết tối ưu hóa một đại lượng số được định nghĩa trước cho bài toán sắp tới, được gọi là độ thích nghi của giả thuyết. Ví dụ, nếu tác vụ học hỏi là bài toán xấp xỉ một hàm chưa biết cho tập mẫu huấn luyện gồm dữ liệu đầu vào và dữ liệu đầu ra, thì độ thích nghi có thể được định nghĩa như là độ chính xác của giả thuyết trên dữ liệu huấn luyện này. Nếu tác vụ là học chiến lược chơi cờ, độ thích nghi có thể là số ván thắng của chiến lược này khi đấu với các chiến lược khác trong quần thể hiện tại. Mặc dù các thuật giải di truyền được thực hiện thay đổi theo bài toán cụ thể, nhưng chúng chia sẻ chung cấu trúc tiêu biểu sau: Thuật giải hoạt động bằng cách cập nhật liên tục tập giả thuyết – được gọi là quần thể. Ở mỗi lần lặp, tất cả các cá thể trong quần thể được ước lượng tương ứng với hàm thích nghi. Rồi quần thể mới được tạo ra bằng cách lựa chọn có xác suất các cá thể thích nghi tốt nhất từ quần thể hiện tại. Một số trong những cá thể được chọn được đưa nguyên vẹn vào quần thể kế tiếp. Những cá thể khác được dùng làm cơ sở để tạo ra các cá thể con bằng cách áp dụng các tác động di truyền: lai ghép và đột biến. Bảng 3.1: Thuật giải di truyền mẫu. [20] GA (Fitness, Fitness_threshold, p, r, m) { // Fitness: hàm gán thang điểm ước lượng cho một giả thuyết. // Fitness_threshold: Ngưỡng xác định tiêu chuẩn dừng giài thuật tìm kiếm. // p: Số cá thể trong quần thể giả thuyết. // r: Phân số cá thể trong quần thể được áp dụng toán tử lai ghép ở mỗi bước. // m: Tỉ lệ cá thể bị đột biến.  Khởi tạo quần thể: P  Tạo ngẫu nhiên p cá thể giả thuyết  Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)  while [max Fitness(h)] < Fitness_threshold do Tạo thế hệ mới, PS 1. Chọn cá thể: chọn theo xác suất (1 – r)p cá thể trong quần thể P thêm vào PS. Xác suất Pr(hi) của giả thuyết hi thuộc P được tính bởi công thức: 25 𝐏𝐫 hi = Fitness(hi) Fitness(hj) p j=1 2. Lai ghép: chọn lọc theo xác suất 2 r p cặp giả thuyết từ quần thể P, theo Pr(hi) đã tính ở bước trên. Ứng với mỗi cặp , tạo ra hai con bằng cách áp dụng toán tử lai ghép. Thêm tất các các con vào PS. 3. Đột biến: Chọn m% cá thể của PS với xác suất cho mỗi cá thể là như nhau. Ứng với mỗi cá thể biến đổi một bit được chọn ngẫu nhiên trong cách thể hiện của nó. 4. Cập nhật: P  PS. 5. Ước lượng: Ứng với mỗi h trong P, tính Fitness(h)  Trả về giả thuyết trong P có độ thích nghi cao nhất. } Quần thể gồm p cá thể. Ở mỗi lần lặp, quần thể kế tiếp PS được hình thành từ việc lựa chọn theo xác suất các giả thuyết hiện tại theo độ thích nghi của chúng và bằng cách thêm vào các giả thuyết mới. Các giả thuyết mới được tạo ra bằng cách áp dụng toán tử lai ghép cho cặp giả thuyết thích nghi nhất và bằng cách tạo ra các đột biến điểm đơn trong thế hệ giả thuyết kết quả. Quá trình này được lặp cho đến khi các giả thuyết thích hợp được phát hiện. Các toán tử lai ghép và đột biến tiêu biểu được định nghĩa trong bảng kế tiếp. Một thuật giải di truyền mẫu được mô tả trong bảng 3.1. Các đầu vào cho thuật giải này bao gồm hàm tính độ thích nghi để tính hạng cho các giả thuyết ứng cử, một giá trị ngưỡng được định nghĩa cấp độ thích nghi có thể chấp nhận để kết thúc thuật giải, kích thước quần thể, và các tham số quyết định các quần thể kế tiếp được tạo ra như thế nào: phần quần thể bị thay thế ở mỗi thế hệ và tỉ lệ đột biến. Lưu ý trong thuật giải này, ở mỗi bước lặp qua vòng lặp chính tạo ra một thế hệ mới các giả thuyết dựa vào quần thế hệ hiện tại. Trước tiên, một số giả thuyết được chọn từ quần thể hiện tại để đưa vào thế hệ kế tiếp. Những giả thuyết này được chọn theo xác suất, ở đây xác suất của giả thuyết được tính bởi [20]: Pr 𝑕𝑖 = 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 𝑕𝑖 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 𝑕𝑗 𝑝 𝑗=1 Vì vậy, xác suất để giả thuyết được chọn tỉ lệ với độ thích nghi của nó và tỉ lệ nghịch với độ thích nghi của các giả thuyết cạnh tranh khác trong quần thể hiện tại. Một khi các cá thể này của thế hệ hiện tại đã được chọn để đưa vào quần thể thế hệ kế tiếp, các cá thể thêm vào được tạo ra dùng toán tử lai ghép. Lai ghép, được định nghĩa chi 26 tiết trong phần kế tiếp, lấy hai giả thuyết từ thế hệ hiện tại và tạo ra hai giả thuyết con bằng cách kết hợp các phần của hai giả thuyết cha. Các giả thuyết cha được chọn theo xác suất từ quần thể hiện tại, sử dụng hàm xác suất được định nghĩa ở trên. Sau khi các cá thể mới được tạo ra từ hoạt động lai ghép này, quần thế thế hệ mới bây giờ có đủ số lượng thành viên mong muốn. Lúc này, một phân số m nào đó các cá thể này được chọn một cách ngẫu nhiên và tất cả các đột biến ngẫu nhiên được thực hiện để thay đổi các cá thể này. 3.3.2. Thể hiện các giả thuyết Các giả thuyết trong GAs thường được thể hiện dưới dạng chuỗi các bit, để chúng có thể dễ dàng được thực hiện bởi các toán tử di truyền là đột biến và lai ghép [14]. Các giả thuyết được thể hiện bởi chuỗi bit này có thể khá phức tạp. Ví dụ, tập các luật if-then có thể dễ dàng được thể hiện theo cách này, bằng cách chọn một cách thức mã hóa các luật để phân bố các chuỗi con riêng cho mỗi điều kiện trước và điều kiện sau của luật. Để thấy các luật if-then có thể được mã hóa bằng các chuỗi bit như thế nào, trước tiên hãy xem chúng ta có thể sử dụng chuỗi bit như thế nào để mô tả ràng buộc trên giá trị của thuộc tính đơn. Lấy một ví dụ [20], hãy xem xét thuộc tính Outlook, thuộc tính này có thể lấy bất kì giá trị nào trong ba giá trị: Sunny, Overcast hoặc Rain. Một cách rõ ràng để thể hiện ràng buộc cho Outlook là dùng một chuỗi bit có chiều dài 3, mỗi vị trí bit tương ứng với một trong ba giá trị có thể của nó. Đặt giá trị 1 ở một vài vị trí để chỉ ra rằng thuộc tính được phép lấy giá trị tương ứng. Ví dụ, chuỗi 010 thể hiện ràng buộc Outlook phải lấy giá trị thứ hai trong các giá trị này, hay là Outlook = Overcast. Một cách tương tự, chuỗi 011 thể hiện ràng buộc tổng quát hơn là cho phép hai giá trị có thể, hay là Outlook = Overcast ∪ Rain. Chú ý 111 thể hiện ràng buộc có thể tổng quát nhất, chỉ ra rằng chúng ta không quan tâm giá trị nào trong các giá trị có thể của nó mà thuộc tính giữ. Đưa ra phương pháp này để thể hiện các ràng buộc trên thuộc tính đơn, các liên kết của các ràng buộc trên nhiều thuộc tính có thể dễ dàng được thể hiện bằng cách nối các chuỗi bit tương ứng. Ví dụ, xem xét thuộc tính thứ hai, Wind có thể lấy giá trị Strong hoặc Weak. Điều kiện trước của luật chẳng hạn như: 𝑂𝑢𝑡𝑙𝑜𝑜𝑘 = 𝑂𝑣𝑒𝑟𝑐𝑎𝑠𝑡 ∪ 𝑅𝑎𝑖𝑛 ∩ (𝑊𝑖𝑛𝑑 = 𝑆𝑡𝑟𝑜𝑛𝑔) Có thể được biểu diễn bởi chuỗi bit có chiều dài là 5 sau: Outlook Wind 27 011 10 Các điều kiện sau của luật (chẳng hạn như PlayTennis = yes) có thể được thể hiện theo kiểu tương tự. Vì vậy, toàn bộ luật có thể được mô tả bởi móc nối các chuỗi bit mô tả các điều kiện đầu, cùng với chuỗi bit mô tả điều kiện sau của luật. Ví dụ, luật IF Wind = Strong THEN PlayTennis = yes sẽ được thể hiện bởi chuỗi: Outlook Wind PlayTennis 111 10 10 ở đây 3 bit đầu tiên mô tả ràng buộc “không quan tâm” trên Outlook , hai bit kế tiếp mô tả ràng buộc trên Wind, và hai bit cuối cùng mô tả điều kiện sau của luật (ở đây chúng ta giả sử PlayTennis có thể lấy giá trị Yes hoặc No). Chú ý chuỗi bit thể hiện luật chứa một chuỗi con cho mỗi thuộc tính trong không gian giả thuyết, thậm chí thuộc tính không bị ràng buộc bởi các điều kiện trước. Điều này tạo ra một chuỗi bit có chiều dài cố định để thể hiện các luật, trong đó các chuỗi con ở các vị trí cụ thể mô tả các ràng buộc trên các thuộc tính cụ thể. Đưa ra cách thể hiện này cho các luật đơn, chúng ta có thể thể hiện tập các luật bằng cách móc nối các thể hiện chuỗi bit của các luật riêng biệt. Trong thiết kế mã hóa chuỗi bit cho một vài không gian giả thuyết, thật là hữu ích để sắp xếp cho mọi chuỗi bit tuân thủ theo cú pháp để thể hiện một giả thuyết được định nghĩa tốt. Để mô tả, chú ý cách mã hóa luật ở đoạn trên, chuỗi bit 111 10 11 thể hiện luật có điều kiện trước không ràng buộc thuộc tính mục tiêu PlayTennis. Nếu tránh xem xét giả thuyết này, chúng ta có thể mượn một cách mã hóa khác (ví dụ phân bố chỉ một bit cho điều kiện sau để chỉ định giá trị là Yes hoặc No), thay đổi các toán tử di truyền để tránh một cách tường minh việc xây dựng các chuỗi bit như thế, hoặc đơn giản gán một độ thích nghi rất thấp cho các chuỗi bit như vậy. 3.3.3. Các toán tử di truyền Những thế hệ sau trong GAs được quyết định bởi tập các toán tử tái hợp và đột biến các cá thể được chọn từ quần thể hiện tại. Các toán tử GAs tiêu biểu để thực hiện các giả thuyết chuỗi bit được mô tả trong bảng 3.1. Các toán tử này tương ứng với các phiên bản được ý tưởng hóa của các hoạt động di truyền trong tiến hóa sinh học. Hai toán tử phổ biến nhất là lai ghép và đột biến. 28 Toán tử lai ghép tạo ra hai con từ hai chuỗi cha bằng cách sao chép các bit được chọn lựa từ mỗi cha. Bit ở vị trí i trong mỗi con được sao chép từ bit ở vị trí i của một trong hai cha. Chọn lựa cha nào phân phối bit cho vị trí i được quyết định bởi thêm vào một chuỗi mặt nạ lai ghép. Hình 3.1: Các toán tử chung cho thuật giải di truyền [20]. Để minh họa, xem xét toán tử lai ghép điểm đơn (single-point) ở đầu hình 3.1. Xem xét hai con trên nhất trong trường hợp này. Con này lấy năm bit đầu tiên của nó từ cha thứ nhất và sáu bit còn lại từ cha thứ hai, bởi mặt nạ lai ghép là 11111000000 xác định các lựa chọn này cho mỗi vị trí bit. Con thứ hai dùng cùng mặt nạ lai ghép, nhưng đổi vai trò của hai cha. Do đó, nó chứa các bit không được dùng bởi con đầu tiên. Trong lai ghép điểm đơn, mặt nạ lai ghép luôn luôn được xây dựng sao cho nó bắt đầu với chuỗi chứa n giá trị 1 liên tục, được theo sau một số giá trị 0 cần thiết để hoàn chỉnh chuỗi. Cách này tạo ra cá thể con có n bit đầu được phân phối bởi một cha và các bit còn lại bởi cha thứ hai. Mỗi 11101001000 00001010101 11101010101 00001001000 11111000000 11101001000 00001010101 11001011000 00101000101 00111110000 11101001000 00001010101 10001000100 01101011001 00111110000 11101001000 11101011000 Các chuỗi ban đầu Mặt nạ lai ghép Các cá thể con Lai ghép điểm đơn: Lai ghép điểm kép: Lai ghép đồng nhất: Đột biến điểm: 29 lần toán tử lai ghép điểm đơn được áp dụng, điểm lai ghép n được chọn ngẫu nhiên, rồi mặt nạ lai ghép được tạo và áp dụng. Trong lai ghép hai điểm (điểm kép), cá thể con được tạo ra bởi thay thế các đoạn trung gian của một cá thể cha vào giữa của chuỗi cha thứ hai. Nói một cách khác, mặt nạ lai ghép là một chuỗi bắt đầu với n0 trị 0, được theo sau bởi chuỗi liên tục n1 trị 1, được theo sau bởi một số trị 0 cần thiết để hoàn chỉnh chuỗi. Mỗi lần toán tử lai ghép hai điểm được áp dụng, một mặt nạ được tạo ra bằng cách chọn ngẫu nhiên các số nguyên n0 và n1. Ví dụ, ở hình 3.1 cá thể con được tạo ra dùng một mặt nạ với n0 = 2 và n1 = 5. Như lai ghép trước, hai cá thể con được tạo ra bằng cách hoán đổi vai trò của hai cá thể cha. Lai ghép đồng nhất kết hợp các bit được lấy mẫu đồng nhất từ hai cá thể cha, như được minh họa trong trong hình 3.1. Trong trường hợp này, mặt nạ lai ghép được tạo ra như là một chuỗi bit ngẫu nhiên với mỗi bit được chọn ngẫu nhiên và độc lập với các bit khác. Thêm vào các toán tử tái kết hợp - tạo ra cá thể con bằng cách kết hợp các phần của hai cá thể cha, một loại toán tử thứ hai tạo ra cá thể con từ một cá thể cha. Cụ thể là toán tử đột biến tạo ra những thay đổi ngẫu nhiên nhỏ cho chuỗi bit bằng cách chọn một bit ở vị trí ngẫu nhiên, rồi thay đổi giá trị của nó. Đột biến thường được thực hiện sau khi lai ghép được áp dụng như trong giải thuật mẫu trong bảng 3.1. Một vài hệ thống GAs mượn thêm một vài toán tử, các toán tử đặc biệt được chuyên biệt hóa cho biểu diễn giả thuyết cụ thể được sử dụng bởi hệ thống. Ví dụ, John J. Grefenstette [15] mô tả hệ thống học tập luật điều khiển robot. Nó sử dụng đột biến và lai ghép cùng với một toán tử để chuyên biệt hóa các luật. 3.3.4. Hàm thích nghi và sự chọn lọc Hàm thích nghi định nghĩa tiêu chuẩn để xếp hạng các giả thuyết tiềm ẩn và để chọn lọc chúng theo xác suất để đưa vào quần thể thế hệ kế tiếp. Nếu tác vụ là học các luật phân loại, thì hàm thích nghi thông thường có một thành phần cho điểm độ chính xác phân loại của luật trên tập mẫu huấn luyện được cho. Thường các tiêu chuẩn khác có thể được bao hàm, chẳng hạn như độ phức tạp và mức độ tổng quát của luật. Một cách tổng quát hơn, khi giả thuyết chuỗi bit được hiểu như là một thủ tục phức tạp (ví dụ, khi chuỗi bit thể hiện tập chọn lọc, các luật if-then sẽ được móc xích với nhau, để điều khiển thiết bị robot), hàm thích nghi có thể đo hiệu suất tổng của thủ tục kết quả hơn là hiệu suất của các luật riêng biệt. 30 Trong thuật giải GA mẫu được chỉ trong bảng 3.1, xác suất để một giả thuyết được chọn được cho bởi tỉ số của độ thích nghi của nó với độ thích nghi của các thành viên khác của quần thể hiện tại, như đã thấy trong phương trình tính giá trị thích nghi. Phương pháp này thỉnh thoảng thường được gọi là sự chọn lọc tỉ lệ độ thích nghi, hoặc sự chọn lọc vòng roulette. Các phương pháp khác dùng độ thích nghi để chọn lọc các giả thuyết cũng sẽ được đề xuất. Ví dụ, sự chọn lọc kiểu vòng thi đấu, hai giả thuyết đầu tiên được chọn ngẫu nhiên từ quần thể hiện tại. Với một vài xác suất p được định nghĩa trước hai cá thể này càng phù hợp càng được chọn và với xác suất (1 – p) giả thuyết càng ít phù hợp càng được chọn. Sự chọn lọc theo vòng thi đấu thường tạo ra quần thể khác nhau nhiều hơn so với sự chọn lọc tỉ lệ với độ thích nghi (Goldberg và Deb 1991). Trong phương pháp sự chọn lọc theo hạng, các giả thuyết trong quần thể hiện tại đầu tiên sẽ được sắp xếp theo độ thích nghi. Xác suất để giả thuyết sẽ được chọn tỉ lệ với hạng của nó trong danh sách đã sắp xếp hơn là độ thích nghi của nó. 31 Chương 4: Minimax probability machine 4.1. Giới thiệu Xuất phát từ bài toán phân lớp, giả sử cho tập dữ liệu trong đó các thuộc tính của các phần tử là các triệu chứng của bệnh nhân bị bệnh ung thư chẳng hạn . Nhiệm vụ chính là phân biệt được người bị bệnh và người không bị bệnh . Ở đây gọi lớp X là nhóm người không bị bệnh và lớp Y là nhóm người bị bệnh. Minimax probability machine là một thuật toán phân hai lớp dữ liệu, cung cấp một giới hạn cho xác suất phân loại sai trong trường hợp xấu nhất dựa trên những đánh giá đáng tin cậy về giá trị trung bình và ma trận hiệp phương sai của các lớp trong tập dữ liệu huấn luyện. 4.2. Nội dung thuật toán Trong bài toán phân lớp ta cần đi tìm một siêu phẳng (nếu hiểu trong mặt phẳng thì nó là một đường thẳng) chia tập dữ liệu ra làm hai, siêu phẳng cụ thể có dạng tổng quát là [16]: 𝑎𝑇𝑧 = 𝑏(𝑎, 𝑧 ∈ 𝑅𝑛 ,𝑎 ≠ 0, 𝑏 ∈ 𝑅) Để tìm được một siêu phẳng tối ưu nhất (tức là phân chia tốt nhất) cần thực hiện quá trình huấn luyện (training). Như vậy tập dữ liệu sẽ phải c hia ra làm tập training và tập test. Tập training dùng để tìm ra siêu phẳng . Sau đó ta dùng tập test để xem rằng độ chính xác của siêu phẳng đó là bao nhiêu và có tốt hay không? Trong MPM dữ liệu được phân ra làm hai lớp bằng cách cực tiểu hóa xác suất phân lớp sai của dữ liệu tương lai trong trường hợp xấu nhất [16]: 𝐦𝐚𝐱 𝛼 ,𝑎≠0,𝑏 𝛼 𝑠. 𝑡 inf𝑃𝑟 𝑎𝑇𝑥 ≥ 𝑏 ≥ 𝛼 , inf𝑃𝑟 𝑎𝑇𝑦 ≤ 𝑏 ≥ 𝛼 Trong đó: 𝛼 đại diện cho cận dưới của độ chính xác đối với dữ liệu tương lại, được gọi là độ chính xác trong trường hợp xấu nhất. Như vậy MPM sẽ có các yếu tố a, b, 𝛼 được xác định. Bài toán phân lớp đặt ra trong hai trường hợp:  Tập dữ liệu là tuyến tính, khi đó các điểm dữ liệu mới sẽ được phân chia bởi dấu hiệu 𝑠𝑖𝑔𝑛(𝑎∗ 𝑇𝑧𝑛𝑒𝑤 − 𝑏∗) nếu dấu này là +1, khi đó 𝑧𝑛𝑒𝑤 ∈ 𝑋 , ngược lại thì 𝑧𝑛𝑒𝑤 ∈ 𝑌. 32  Tập dữ liệu là phi tuyến, khi đó sử dụng một hàm kernel để đưa không gian gốc về một không gian đặc biệt, ở đó dữ liệu là tuyến tính, khi đó việc phân lớp sẽ được thực hiện trên không gian đặc biệt đó , chiếu tới một không gian đặc biệt 𝑅𝑓 qua ánh xạ sau 𝜑:𝑅𝑛 → 𝑅𝑓 , hàm kernel 𝐾 𝑧1, 𝑧2 = 𝜑 𝑧1 𝑇𝜑(𝑧2) thỏa mãn điều kiện Mercer (điều kiện để một hàm là Kernel). Khi đó việc phân lớp điểm dữ liệu mới 𝑧𝑛𝑒𝑤 được thực hiện bằng cách đánh giá: 𝑠𝑖𝑔𝑛 𝑎∗ 𝑇𝜑 𝑧𝑛𝑒𝑤 − 𝑏∗ = 𝑠𝑖𝑔𝑛 𝑟∗ 𝐾 𝑧𝑖 , 𝑧𝑛𝑒𝑤 𝑁𝑥+𝑁𝑦 𝑖=1 − 𝑏∗ Nếu giá trị này bằng +1 khi đó 𝑧𝑛𝑒𝑤 ∈ 𝑋, ngược lại thì 𝑧𝑛𝑒𝑤 ∈ 𝑌. 4.3. Ưu điểm và nhược điểm của minimax probability machine  Ưu điểm: - Phi phân phối (distribution-free): không cần đưa ra một giả thuyết phân phối cụ thể, bộ phân lớp được xây dựng trực tiếp từ bộ dữ liệu. - Trong các trường hợp tổng quát, độ chính xác của việc phân lớp được giới hạn bởi giá trị 𝛼.  Nhược điểm: - Trong các trường hợp cụ thể, tầm quan trọng của hai phân lớp không phải luôn luôn ngang nhau, do vậy việc đặt cận dưới 𝛼 như nhau cho cả hai lớp là không cần thiết → sự ra đời của Biased Minimax Probability Machine. - Mặt khác, không có gì chứng tỏ hai cận dưới này phải bằng nhau. Do đó, mô hình thu được trong trường hợp này là không tối ưu → sự ra đời của Minimum Error Minimax Probability Machine. 4.4. Các phiên bản cải tiến của minimax probability machine Phần này sẽ giới thiệu tổng quan về hai mô hình cải tiến của minimax probability machine là: Minimum error minimax probability machine và Biased minimax probability machine. 4.4.1. Minimum error minimax probability machine (MEMPM) Minimum error minimax probability machine là mô hình phân lớp tối ưu Bayes phi phân phối (distribution-free), được mở rộng từ MPM. [17] Xuất phát từ việc MPM giả sử độ chính xác trong trường hợp xấu nhất đối với hai lớp là như nhau, và điều này có vẻ không hợp lý. Dẫn đến, siêu phẳng do MPM sinh ra không 33 nhất thiết phải cực tiểu hóa tỉ lệ lỗi trong trường hợp xấu nhất, do vậy chưa tối ưu. MEMPM loại bỏ ràng buộc trên, đưa ra mô hình tổng quát sau [17]: 𝐦𝐚𝐱 𝛼 ,𝛽 ,𝑎≠0,𝑏 𝜃𝛼 + 1− 𝜃 𝛽 , 𝒔. 𝒕 inf x~ x , x 𝑃𝑟 𝑎𝑇𝑥 ≥ 𝑏 ≥ 𝛼 , inf y~ y , y 𝑃𝑟 𝑎𝑇𝑦 ≤ 𝑏 ≥ 𝛽. Tương tự như MPM, 𝛼 và 𝛽 là độ độ chính xác của việc phân lớp trong trường hợp xấu nhất, tương ứng với đó, 𝜃 ∈ 0,1 là xác suất tiên nghiệm của lớp x và 1− 𝜃 là xác suất tiên nghiệm của lớp y. Ta thấy việc cực đại hóa 𝜃𝛼 + (1− 𝜃)𝛽 chính là cực đại hóa độ chính xác trong trường hợp xấu nhất. Nói cách khác, nếu chúng ta thay 𝑚𝑎𝑥 𝜃𝛼 + (1 − 𝜃)𝛽 bằng 𝑚𝑖𝑛 𝜃 1− 𝛼 + 1 − 𝜃 (1− 𝛽) và coi 1− 𝛼 là xác suất cận trên mà một điểm dữ liệu thuộc lớp x được xếp vào lớp y (tương tự với 1− 𝛽), thì mô hình MEMPM chính xác là cực tiểu hóa lỗi Bayes cực đại và do đó thu được siêu phẳng tối ưu Bayes trong trường hợp xấu nhất. Đặc biệt, khi giả sử 𝛼 = 𝛽 thì MEMPM chính là MPM. (h.1) 34 (h.2) Hình 4.1: Mô tả sự khác nhau giữa MEMPM (h.1) và MPM (h.2) với cùng xác suất tiên nghiệm cho 2 lớp. [17] Trong hình 4.1, mặt phẳng quyết định tối ưu ứng với điểm giao nhau, tại đó lỗi error (1-a)+(1-b) là cực tiểu (độ chính xác a+b là cực đại) như trong MEMPM. 4.4.2. Biased minimax probability machine (BMPM) Biased minimax probability machine cũng là mô hình được mở rộng từ MPM bằng cách loại bỏ giả thuyết về trọng số đối xứng cho mỗi phân lớp trong MPM [18]. BMPM dùng để giải quyết các bài toán phân lớp bất đối xứng, đặc biệt là trong các ứng dụng chẩn đoán y học. Mục tiêu của bộ phân lớp kiểu này là đảm bảo độ chính xác của các lớp quan trọng càng cao càng tốt, còn độ chính xác của các lớp ít quan trọng hơn thì chỉ cần ở mức độ chấp nhận được. Công thức của BMPM: [18] 𝐦𝐚𝐱 𝛼 ,𝛽 ,𝑎≠0,𝑏 𝛼 𝒔. 𝒕. inf x~ x , x 𝑃𝑟 𝑎𝑇𝑥 ≥ 𝑏 ≥ 𝛼 , inf y~ y , y 𝑃𝑟 𝑎𝑇𝑦 ≤ 𝑏 ≥ 𝛽. 𝛽 ≥ 𝛾 Trong đó các ký hiệu có ý nghĩa giống như trên đã nói, 𝛾 là một hằng số dương xác định trước, thể hiện mức độ chính xác chấp nhận được đối với lớp ít quan trọng. 35 Chương 5: Phương pháp đề nghị 5.1. Tổng quan về phương pháp Bước quan trọng đầu tiên trong việc xây dựng mô hình dự đoán là làm sao chọn được tập giá trị đầu vào thích hợp. Hầu hết các kỹ thuật khai phá dữ liệu hiện nay đều không đạt hiệu quả cao với tập dữ liệu có số chiều lớn, độ chính xác và hiệu quả truy vấn giảm nhanh chóng khi số chiều tăng lên. Ngoài ra việc thu thập dữ liệu cũng tốn nhiều thời gian, công sức và tiền bạc, nhưng số chiều bên trong dữ liệu cần sử dụng trên thực tế là nhỏ (ví dụ: số lượng các Gen tương ứng cho một loại bệnh là rất nhỏ). Việc chọn lựa dữ liệu thích hợp làm đầu vào cho mô hình dự đoán sẽ giúp đưa ra kết quả có tính chính xác cao và giúp tối ưu thời gian thực hiện công việc. 5.1.1. Mô tả phương pháp Theo ý tưởng trên, trong bài toán cụ thể là chuẩn đoán bệnh ung thư, dữ liệu về bệnh nhân được trình bày dưới dạng một ma trận, trong đó mỗi cột là một dấu hiệu (thuộc tính) của bệnh ung thư, mỗi dòng sẽ biểu diễn những số liệu về một bệnh nhân cụ thể. Ở bước đầu tiên, chúng ta sử dụng thuật toán di truyền (GA) để giải quyết vấn đề tối ưu tập thuộc tính từ tập dữ liệu ban đầu. Bước thứ hai, phương pháp phân lớp MPM sẽ thực hiện phân lớp với tập thuộc tính đã được chọn lọc để đưa ra kết luận bệnh nhân đó có khả năng bị ung thư hay không? Ở đây ta áp dụng GA như một công cụ tối ưu hóa đầu vào cho quá trình phân lớp, nhằm tăng hiệu năng và tính chính xác của quá trình phân lớp. Trước tiên, GA được áp dụng để chọn ra tập con thuộc tính tốt nhất từ tập dữ liệu ban đầu. Dữ liệu của chúng ta bao gồm n cột số liệu sẽ được mô tả dưới dạng một vector nhị phân 01110…11101 có độ dài ứng với số thuộc tính và có ý nghĩa như sau: 0 là không chọn cột đó, còn 1 là chọn cột có số thứ tự tương ứng. Cách biểu diễn này sẽ mô tả được bộ dữ liệu với số cột được lựa chọn theo một thứ tự ngẫu nhiên. Một chuỗi nhị phân được coi là một chromosome trong thuật toán di truyền. Tiếp đó, tìm các chuỗi nhị phân này được thực hiện thông qua các phép toán của GA như chọn lọc, lai ghép và đột biến dựa trên hàm mục tiêu là MPM hay MPM dùng để tính toán giá trị thích nghi (fitness function) cho GA. Với tập thuộc tính được coi là tối ưu, chúng ta sẽ sử dụng phương pháp MPM để chuẩn đoán bệnh nhân đó 36 thuộc về lớp bị bệnh hay không bị bệnh và so sánh kết quả phân lớp với kết quả thực tế nhằm đánh giá mức độ tốt của hệ thống. 5.1.2. Mô hình bài toán Hình 5.1: Mô hình kết hợp thuật toán di truyền và phương pháp phân lớp MPM. Trong đó, bộ dữ liệu Test chiếm 30% dữ liệu gốc, bộ dữ liệu Train chiếm 70% dữ liệu gốc. Tiếp tục chia theo dữ liệu Train thành hai phần trong đó dữ liệu Validation chiếm 30% bộ dữ liệu Train và 70% còn lại của dữ liệu Train là Training set. 5.2. Mô tả dữ liệu sử dụng Dữ liệu sử dụng để đánh giá và kiểm thử mô hình là một bộ dữ liệu phi tuyến về bệnh ung thư. Bộ dữ liệu bao gồm 311 hàng và 120 cột, trong đó cột cuối cùng là nhãn. Nó có 2 lớp nhãn, ký hiệu nhãn +1 tương ứng với không bị bệnh và nhãn -1 là bị bệnh ung thư. GA > MPM > Training Set Validation Set Error Training Model MPM đã được tối ưu Test Set Best chromosome Kết quả phân lớp 37 Như vậy, bộ dữ liệu có 311 phần tử và mỗi phần tử có 119 thuộc tính. Bảng 5.1: Mô tả bảng dữ liệu sử dụng (file Stomach_Full.mat) 1 2 3 … 119 Nhãn 1 642.48 835.28 615.65 … 329.66 1 2 587.21 786.04 380.87 … 131.73 -1 3 1006 1325.7 330.09 … 252.63 -1 4 524.47 646.16 417.86 … 314.33 -1 … … … … … … … 310 648.43 1155.9 230.35 … 236.92 1 311 496.06 1413.8 293.8 … 335.01 1 312 1060 1205.4 177.06 … 224.09 1 5.3. Các module trong hệ thống và giao diện của chương trình Chương trình được xây dựng và chạy trên MATLAB 7.0. MATLAB (Matrix Laboratory) là một phần mềm khá mạnh trong việc giải quyết các bài toán kỹ thuật và thống kê như xử lý tín hiệu số, hệ thống điều khiển, mô phỏng hay mạng neuron. 5.3.1. Chi tiết các module của Genetic Algorithm Để nâng cao tính chính xác của bộ phân lớp, chương trình sử dụng gói “Genetic Algorithm Tool” trong Matlab 7.0 để thực hiện việc tối ưu hóa tập dữ liệu đầu vào cho bộ phân lớp MPM. Dữ liệu của ta bao gồm 119 cột thuộc tính sẽ được mã hóa ở dạng chuỗi nhị phân 0101…011 với ý nghĩa như sau: 0 là không chọn và 1 là chọn cột thuộc tính có số thứ tự tương ứng. Mỗi chuỗi nhị phân có độ dài cố định là 119 được xem như một chromosome trong thuật toán di truyền. Tiếp theo ta sẽ sử dụng MPM là hàm đánh giá (fitness function) để tìm ra chromosome tốt nhất ở thế hệ cuối cùng bằng cách cực tiểu hóa tỷ lệ lỗi. Để tìm ra chromosome tốt nhất từ tập dữ liệu ban đầu, thuật toán di truyền cần thực hiện quá trình chọn lựa, lai ghép và đột biến. 38 Hình 5.2: 6 bước thực hiện để tìm ra chromosome tốt nhất.  Chương trình gồm các hàm sau: - Gói Genetic Tool của Matlab 7.0. - funtion tinhloi: trả về số lỗi tìm ra bằng cách so sánh nhãn mới của tập test sau khi đưa vào bộ phân lớp MPM với nhãn ban đầu. - function fitness: sử dụng MPM là hàm đánh giá của thuật giải di truyền.  input: vector nhị phân có độ dài cố định 119.  output: phần trăm lỗi được theo công thức sau 𝐸𝑟𝑟𝑜𝑟𝑅𝑎𝑡𝑒 = 𝑒𝑟𝑟𝑜𝑟 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑒𝑠𝑡 𝑝𝑜𝑖𝑛𝑡𝑠 ∗ 100 Trong đó: error: là số lỗi tìm ra bằng cách so sánh nhãn mới của tập test sau khi đưa vào bộ phân lớp MPM với nhãn ban đầu. Thực hiện đột biến Thế hệ = 0 Tạo quần thể gồm các chromosome Xác định giá trị của hàm đánh giá với mỗi cá thể Chọn thế hệ kế tiếp Thực hiện lai ghép Chromosome tốt nhất Thế hệ tiếp theo >N thế hệ 39 Hình 5.3: Giá trị của hàm đánh giá tại mỗi thế hệ. Giải thích: o Generation: số thế hệ. o f-count: Giá trị tích lũy số lần đánh giá hàm fitness. o Best f(x): giá trị tốt nhất của fitness function tại thế hệ hiện tại. o Mean f(x): giá trị trung bình của fitness function tại thế hệ hiện tại. o Stall Generations: số lượng thế hệ tính từ thời điểm cuối cùng có sự cải thiện trong giá trị của hàm fitness. 40 Hình 5.4: Hình ảnh biểu diễn hàm đánh giá của GA tại mỗi thế hệ. Giải thích: o Hình vẽ biểu diễn giá trị của hàm đánh giá (fitness function) tại mỗi thế hệ: trục tung – fitness value (chiều dọc) thể hiện giá trị của hàm đánh giá; trục hoành – Generation (chiều ngang) thể hiện số thế hệ trong thuật toán di truyền. o Chấm màu xanh và chấm màu đen tương ứng thể hiện giá trị tốt nhất và trung bình mà fitness function tính toán được tại mỗi thế hệ. o Best: 10.7692 là giá trị tốt nhất của fitness function tính toán được tại thế hệ cuối cùng (ở ví dụ này thế hệ cuối cùng là 60). o Mean: 11.5385 là giá trị trung bình của fitness function tính toán được tại thế hệ cuối cùng (ở ví dụ này thế hệ cuối cùng là 60). 41 Hình 5.5: Kết quả quá trình tối ưu tập thuộc tính của dữ liệu ban đầu. Giải thích: o Current generation: Thế hệ tại thời điểm hiện tại. o Status and results: Cửa sổ hiển thị trạng thái của thuật toán di truyền, giá trị của hàm đánh giá tại thế hệ cuối cùng và nguyên nhân thuật toán kết thúc. o Final point: hiển thị chromosome tốt nhất (dạng nhị phân). - function DataSelection:  input: vector nhị phân, ma trận dữ liệu ban đầu.  output: ma trận mới gồm các cột thuộc tính được chọn tương ứng với vị trí có bit 1 trong chuỗi nhị phân. 5.3.2. Chi tiết các module của minimax probability machine Thuật toán MPM viết bởi Matlab được dùng để phân chia một tập dữ liệu phi tuyến thành 2 lớp. Chương trình gồm các hàm sau: - function build_MPM_k_binclass_Lsreg: có chức năng là tìm ra 𝑎∗ 𝑇 , 𝑏∗ và 𝛼. 42 - function eval_MPM_k_binclass: dựa trên các kết quả tìm được trên để đưa ra kết luận về tập test xem khả năng chính xác là bao nhiêu. - function run: thực hiện phân lớp MPM trên bộ dữ liệu giảm chiều và đưa ra tỷ lệ phân lớp chính xác của tập training và tập test. - function example: thực hiện phân lớp MPM trên bộ dữ liệu gốc và đưa ra tỷ lệ phân lớp chính xác của tập training và tập test. Hình 5.6: Giao diện kết quả của bộ phân lớp minimax probability machine. 43 Giải thích: o Number of features: số lượng thuộc tính của dữ liệu. o Training set accuracy: Tỷ lệ đúng của tập huấn luyện. o Test set accuracy: Kết quả của tập kiểm tra. 5.4. Thực nghiệm và phân tích kết quả 5.4.1. Phương pháp đánh giá  Các bước thực hiện quá trình đánh giá mô hình xây dựng: - Bước 1: Bộ dữ liệu gốc (Stomach_Full.mat) được chia làm 2 phần: dữ liệu train chiếm 70% dữ liệu ban đầu và dữ liệu test chiếm 30% dữ liệu ban đầu. Thực hiện phân lớp bằng MPM trên bộ dữ liệu đã được chia như trên  kết quả phân lớp của MPM trên bộ dữ liệu gốc. - Bước 2: Sử dụng bộ dữ liệu Train (Training_Validation.mat) chiếm 70% bộ dữ liệu gốc (trong đó dữ liệu Validation chiếm 30% dữ liệu Train) để thực hiện quá trình trích chọn thuộc tính bằng GA tool trong Matlab 7.0, với các tham số tùy chọn như sau:  Fitness function: @fitness.  Number of variables: 119.  Population type: Bit string.  Population size: 20.  Selection function: Stochastic uniform.  Crossover function: Scattered – khởi tạo ngẫu nhiên một vector nhị phân. Chọn các gen mà vector có giá trị là 1 từ cha thứ nhất và những gen mà vector có gí trị 0 từ cha thứ hai, rồi kết hợp các gen đó thành con. Ví dụ: cha1 = [a b b d e f g h] cha2 = [1 2 3 4 5 6 7 8] vector lai ghép ngẫu nhiên = [1 1 0 0 1 0 0 0] con = [a b 3 4 e 6 7 8]  Mutation function: Gaussian – thêm một số ngẫu nhiên vào mỗi vector đầu vào của một cá thể. Số ngẫu nhiên này được lấy từ phân bố Gauss. 44 - Bước 3: Chạy hàm DataSelection với đầu vào là chromosome tốt nhất vừa tìm được và bộ dữ liệu Test (TestSet.mat) chiếm 30% dữ liệu gốc để sinh ra tập dữ liệu mới (outData.mat) là bộ dữ liệu giảm chiều làm đầu vào cho bộ phân lớp MPM. - Bước 4: chạy bộ phân lớp MPM với tập dữ liệu là “outData”. Bộ dữ liệu giảm chiều cũng được chia làm 2 phần với tỷ lệ như phân chia 70% là Training và 30% Test để thực hiện phân lớp  kết quả phân lớp của bộ dữ liệu giảm chiều. Lặp lại bước 2 đến 4 nhiều lần với những điều kiện dừng ở bước 2 là “Generations” để thu được số liệu phục vụ cho quá trình phân tích. - Bước 5: thống kê số liệu các lần thực hiện bước 2 đến 4 và so sánh kết quả thu được từ bước 1. 5.4.2. Phân tích kết quả 5.4.2.1. Kết quả thực hiện phân lớp trên bộ dữ liệu ban đầu Stomach_Full (311x120) được chia thành bộ Training (218x120) và bộ Test (93x120). Bảng 5.2: Kết quả phân lớp trên bộ dữ liệu ban đầu Số lượng thuộc tính Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra 1 119 98.17 70.9677 2 119 97.2477 72.043 3 119 97.2477 75.2688 4 119 95.8716 77.4194 5 119 96.3303 76.3441 6 119 97.2477 65.5914 7 119 96.3303 69.8925 8 119 95.8716 68.8172 9 119 99.0826 73.1183 10 119 99.0826 65.5914 11 119 98.1651 67.7419 12 119 95.8716 70.9677 13 119 98.1651 76.3441 14 119 99.0826 74.1935 15 119 96.789 64.5161 MAX 119 99.0826 77.4194 Phương sai 0 1.19 4.21 Trung bình 97.37 71.25 45 5.4.2.2. Kết quả thực hiện phân lớp trên bộ dữ liệu giảm chiều (outData.mat) Chúng ta sử dụng điều kiện dừng cho quá trình tìm kiếm chromosome tốt nhất của thuật toán di truyền là “Generations”.  Trường hợp 1: Generations = 30 với 15 lần chạy thử. Bảng 5.3: Kết quả phân lớp trong trường hợp 1 Số lượng thuộc tính Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra 1 55 100 85.7143 2 57 100 57.1429 3 54 100 64.2857 4 60 100 82.1429 5 54 100 75 6 54 100 85.7143 7 60 100 71.4286 8 65 100 82.1429 9 63 100 85.7143 10 61 100 78.5714 11 51 98.4615 89.2857 12 48 100 71.4286 13 50 100 85.7143 14 56 100 89.2857 15 59 100 89.2857 MAX 65 100 89.2857 Phương sai 4.87 0.40 9.78 Trung bình 99.90 79.52 46 Hình 5.7: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 1). Nhận xét: o Số chiều của tập dữ liệu mới giảm xấp xỉ 1.8 lần so với tập dữ liệu ban đầu. o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 79.52, tuy nhiên phương sai lại tăng (từ 4.21 lên 9.78) nên mô hình kiểm tra không ổn định bằng. o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 99.9, đồng thời phương sai cũng giảm (từ 1.19 còn 0.4) nên mô hình huấn luyện có tính ổn định hơn.  Trường hợp 2: Generations = 40 với 15 lần chạy thử. Bảng 5.4: Kết quả phân lớp trong trường hợp 2 Số lượng thuộc tính Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra 1 63 100 92.8571 2 63 100 53.5714 3 52 100 60.7143 4 55 98.4615 82.1429 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T ỷ l ệ đ ú n g Số lần thực hiện Tập DL mới Tập DL gốc 47 5 64 100 78.5714 6 62 100 50 7 62 100 75 8 54 100 82.1429 9 66 100 96.4286 10 58 100 78.5714 11 53 100 57.1429 12 54 100 75 13 56 100 89.2857 14 58 100 85.7143 15 45 100 53.5714 MAX 66 100 96.4286 Phương sai 5.70 0.38 15.30 Trung bình 99.90 74.05 Hình 5.8: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 2). Nhận xét: o Số chiều của tập dữ liệu mới giảm xấp xỉ 1.8 lần so với tập dữ liệu ban đầu. 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T ỷ l ệ đ ú n g Số lần thực hiện Tập DL mới Tập DL gốc 48 o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 74.05, tuy nhiên phương sai lại tăng (từ 4.21 lên 15.3) nên mô hình kiểm tra không ổn định bằng. o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 99.9, đồng thời phương sai cũng giảm (từ 1.19 còn 0.38) nên mô hình huấn luyện có tính ổn định hơn.  Trường hợp 3: Generations = 50 với 15 lần chạy thử. Bảng 5.5: Kết quả phân lớp trong trường hợp 3 Số lượng thuộc tính Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra 1 55 100 75 2 58 100 75 3 48 100 71.4286 4 62 100 85.7143 5 51 100 71.4286 6 57 100 53.5714 7 52 100 78.5714 8 52 100 78.5714 9 49 100 75 10 57 100 89.2857 11 57 100 92.8571 12 63 100 67.8571 13 49 100 92.8571 14 59 100 75 15 63 100 89.2857 MAX 63 100 92.8571 Phương sai 5.11 0 10.62 Trung bình 100 78.10 49 Hình 5.9: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 3). Nhận xét: o Số chiều của tập dữ liệu mới giảm xấp xỉ 1.9 lần so với tập dữ liệu ban đầu. o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 78.1, tuy nhiên phương sai lại tăng (từ 4.21 lên 10.62) nên mô hình kiểm tra không ổn định bằng. o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 100, đồng thời phương sai cũng giảm (từ 1.19 còn 0) nên mô hình huấn luyện có tính ổn định cao.  Trường hợp 4: Generations = 60 với 15 lần chạy thử. Bảng 5.6: Kết quả phân lớp trong trường hợp 4. Số lượng thuộc tính Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra 1 52 100 89.2857 2 54 100 53.5714 3 48 100 75 4 60 100 82.1429 0 10 20 30 40 50 60 70 80 90 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T ỷ l ệ đ ú n g Số lần thực hiện Tập DL mới Tập DL gốc 50 5 59 100 50 6 58 100 78.5714 7 43 98.4615 96.4286 8 65 100 67.8571 9 64 100 78.5714 10 57 100 96.4286 11 63 100 85.7143 12 65 100 75 13 67 100 50 14 57 100 85.7143 15 54 100 60.7143 MAX 67 100 96.4286 Phương sai 6.76 0.40 15.57 Trung bình 99.90 75.00 Hình 5.10: So sánh tỷ lệ phân lớp chính xác của tập dữ liệu gốc và dữ liệu mới (trường hợp 4). Nhận xét: o Số chiều của tập dữ liệu mới giảm xấp xỉ 1.8 lần so với tập dữ liệu ban đầu. 0 20 40 60 80 100 120 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 T ỷ l ệ đ ú n g Số lần thực hiện Tập DL mới Tập DL gốc 51 o Tỷ lệ phân lớp chính xác được cải thiện rõ rệt: tăng từ 71.25 lên 75, tuy nhiên phương sai lại tăng (từ 4.21 lên 15.57) nên mô hình kiểm tra không ổn định bằng. o Tỷ lệ chính xác của bộ dữ liệu huấn luyện cũng tăng lên: từ 97.37 lên 99.9, đồng thời phưưng sai cũng giảm (từ 1.19 còn 0.4) nên mô hình huấn luyện có tính ổn định hơn. 5.4.2.3. So sánh kết quả 4 trường hợp kiểm thử Điều kiện dừng là Generations sẽ được tăng dần trong mỗi trường hợp. Hình 5.11: So sánh kết quả phân lớp trung bình trong 4 trường hợp kiểm thử và kết quả phân lớp của dữ liệu gốc. Nhận xét: o Tỷ lệ phân lớp chính xác đối với bộ dữ liệu huấn luyện với tập thuộc tính mới không thay đổi nhiều khi ta tăng dần giá trị của Generations và tỷ lệ 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 Tỷ lệ đúng của tập huấn luyện Kết quả của tập kiểm tra Generations=30 Generations=40 Generations=50 Generations=60 Dữ liệu gốc 52 này lớn hơn so với tỷ lệ phân lớp chính xác cho bộ dữ liệu huấn luyện gốc (119 thuộc tính). o Khi ta tăng dần giá trị của Generations, thì tỷ lệ phân lớp chính xác đối với bộ dữ liệu test không có sự cải thiện rõ ràng, nhưng mô hình huấn luyện lại có tính ổn định hơn. 5.4.2.4. Kết luận o Sử dụng hàm kernel Poly (kernel tuyến tính) trong thuật toán phân lớp MPM vẫn chưa thực sự hiệu quả với tập dữ liệu phi tuyến chúng ta sử dụng để đánh giá mô hình. o Số lượng các đặc trưng giữ lại sau khi giảm chiều không làm ảnh hưởng nhiều tới kết quả phân lớp thu được. o Khi tiến hành giảm chiều tập dữ liệu ban đầu (311x119), rồi sử dụng bộ phân lớp MPM thì rõ ràng tỷ lệ phân lớp chính xác đã tăng lên, đồng thời tỷ lệ chính xác phân lớp trong huấn luyện cũng được cải thiện. o Khi ta tăng số thế hệ trong thuật toán di truyền nhằm tìm ra chromosome tốt nhất ở thế hệ cuối cùng làm dữ liệu đầu vào cho bộ phân lớp, thì tỷ lệ phân lớp chính xác của MPM cũng tăng lên nhưng độ ổn định của kết quả không thực sự tốt hơn. Tuy nhiện tỷ lệ chính xác trong huấn luyện được cải thiện rõ ràng và ổn định hơn. 53 Chương 6: Tổng kết Trong khóa luận này, bước đầu tôi đã tìm hiểu cơ sở lý thuyết và thuật toán cho việc giải bài toán trích chọn thuộc tính phù hợp dựa trên các kỹ thuật giảm chiều dữ liệu. Tôi đã trình bày ý tưởng kết hợp thuật toán di truyền (Genetic Algorithm) trong cải tiến hiệu quả phân lớp của thuật toán phân lớp minimax probability machine. Các kết quả thực nghiệm của phương pháp này đã cải thiện hiệu quả phân lớp so với thuật toán nguyên gốc, tuy nhiên ta cũng nhận thấy sự kết hợp này vẫn còn những điểm hạn chế như:  Chưa cải thiện rõ rệt tốc độ xử lý của bộ phân lớp kết hợp so với bộ phân lớp gốc.  Số lượng chiều của dữ liệu cần giảm là bao nhiêu để vừa giảm được thuộc tính dư thừa vừa cải thiện được hiệu quả phân lớp tốt nhất.  Trong quá trình giảm chiều không thể tránh khỏi những mất mát hay sai sót, do đó sự mất mát thông tin quan trọng dẫn đến hiệu quả của giảm chiều đối với phương pháp phân lớp là không ổn định.  Kết quả phân lớp chính xác vẫn chưa thực sự làm hài lòng. Để giải quyết những vấn đề còn tồn tại trong phương pháp này, tôi sẽ thử nghiệm kết hợp các hàm đánh giá (fitness function) khác nhau trong thuật toán di truyền, nhằm tìm ra kết quả đầu vào tốt hơn cho thuật toán phân lớp và cũng để cải thiện tốc độ tìm kiếm. Ngoài ra, tôi sẽ thử nghiệm phương pháp tối ưu hàm kernel của thuật toán MPM nhằm thu được kết quả phân lớp chính xác hơn (lớn hơn 95%) và ổn định hơn. Trong khóa luận này tôi hi vọng thử nghiệm giải quyết bài toán phân lớp với dữ liệu nhiều chiều và tạo ra các hệ thống đánh giá và dự đoán để có thể áp dụng một cách thiết thực vào đời sống. 54 Tài liệu tham khảo  Tài liệu tham khảo tiếng Anh [1] Fayyad, Piatesky-Shapiro, Smyth (1996) - From Data Mining to Knowledge Discovery: An Overview. In Fayyad, Piatesky-Shapiro, Smyth, Uthurusamy - Advances in Knowledge Discovery and Data Mining, AAAI Press/ The MIT Press, MenloPark, CA, 1996, 1-34. [2] Jiawei Han and Micheline Kamber (2001) - Data Mining: Concepts and Techniques (second edition). Chapter 1. [3] Boris Kovalerchuk and Evgenii Vityaev (2001) - Data mining in Finance: Advances in Relational and Hybrid Methods, Kluwer Academic Publishers, Boston, Dordrecht – London, 2001. [4] David Taniar, Monash University, Australia - Research and Trends in Data Mining Techonologies and Application, 2007. [5] Ralf Herbrich, the MIT Press, Cambridge, Massachussets, London, England - Learning Kernel Classification and Algorithms. [6] H. Liu and L.Yu, Department of Computer Science and Engineering, Arizona State University, Tempe - Feature Selection for Data mining. [7] H. Liu and H.Motoda - Feature Extraction, Construction and Selection: A Data Mining Perspective. [8] P.A. Devijver and J.Kittler - Pattern Recoginition: A Statistical Approach. [9] Peter Norvig, Palo Alto, California (2006) - Feature Selection Book. [10] JUN ZHAO(a,b), GUO-YIN WANG(b), HONG TANG(a), HUA LI(a) - The study on technologies for feature selection. (a) Department of Computer Science of Chongqing University, Chongqing, 400065, China. (b) Inst. of Computer Sci. & Tech. Of Chongqing Univ. of P. & T., Chongqing, 400065, China. [11] Ricardo Gutierrez-Osuna, Wright State University - Intelligent Sensor Systems (Cross Validation). [12] M. Pei1, E. D. Goodman1, W. F. Punch2 - Feature Extraction Using Genetic Algorithms. 55 1 Case Center for Computer – Aided Engineering and Manufacturing. 2 Department of Computer Science, Genetic Algorithms Research and Application Group (GARAGe), Michigan State University, 2325 Engineering Building, East Lansing, MI 48824. [13] Genetic Algorithm and Direct Search Toolbox 2.1.4 – Help Document. [14] Laetitia Jourdan, Clarisse Dhaenens, El-Ghazali Talbi. LIFL, University of Lille, France - A Genetic Algorithm for Feature Selection in Data-Mining for Genetics. [15] Grefenstette, J. J. (1991) - Strategy acquisition with genetic algorithms, in Handbook of Genetic Algorithms, Davis, L. D. (Ed.), Boston: Van Nostrand Reinhold. [16] Gert R. G. Lanckriet, Lauren El Ghaoui, Chrianjib Bhattacharyya and Micheal I. Jordan. University of California - Minimax Probability Machine. [17] Kaizhu Huang, Haiqin Yang, Irwin King, Michael R. Lyu and Laiwan Chan - The Minimum Error Minimax Probability Machine. [18] Kaizhu Huang, Haiqin Yang, Irwin King, Michael R. Lyu and Laiwan Chan - Biased Minimax Probability Machine for Medical Diagnosis. [19] Zhen-Guo Chen and Shu Wang. Department of Computer Science and Technology, North China Institute of Science and Technology, East Yanjiao, Beijing, China - Minimax Probability Machine with Genetic Feature Optimized for Intrusion Detection. [20] Genetic Algorithm:  Tài liệu tham khảo tiếng Việt [21] Nguyễn Đức Cường, Khoa Công nghệ thông tin, Đại học Bách Khoa, Thành phố Hồ Chí Minh - Tổng quan về khai phá dữ liệu (Reviewing of Data Mining). [22] Vấn đề tri thức và “xã hội tri thức” thuc.html;jsessionid=7D49738B61116C5B527B009CC142141F?zone=2 [23] Giáo sư Hà Quang Thụy, Đại học Công Nghệ, Đại học Quốc Gia Hà Nội - Giáo trình giảng dạy môn Khai phá dữ liệu Web (2008).