Luận văn Nghiên cứu một số phương pháp phân lớp dữ liệu và ứng dụng trong phân lớp nấm (mushroom) với công cụ weka

THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 84 8 01 01 Người hướng dẫn khoa học: TS. Nguyễn Văn Núi Thái Nguyên – 2020 I LỜI CẢM ƠN Trước tiên, tơi xin được gửi lời cảm ơn và lịng biết ơn sâu sắc nhất tới Thầy giáo, TS. Nguyễn Văn Núi đã tận tình chỉ bảo, hướng dẫn, động viên và giúp đỡ tơi trong suốt quá trình tơi thực hiện luận văn tốt nghiệp. Tơi xin gửi lời cảm ơn tới các thầy cơ Trường Đại Học Cơng nghệ Thơng Tin và Truyền Thơng – Đại học Thái Nguyên, những người đã tận tình giúp đỡ, hướng dẫn trong quá trình tơi học tập tại trường. Cuối cùng, tơi muốn gửi lời cảm ơn tới gia đình và bạn bè, những người thân yêu luơn bên cạnh, quan tâm, động viên tơi trong suốt quá trình học tập và thực hiện luận văn tốt nghiệp này. Tơi xin chân thành cảm ơn! Thái Nguyên, tháng 11 năm 2020 Học viên Inthavong Souksakhone II LỜI CAM ĐOAN Tơi xin cam đoan kết quả đạt được trong Luận văn là sản phẩm của riêng cá nhân tơi, khơng sao chép lại của người khác. Những điều được trình bày trong nội dung Luận văn, hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều cĩ xuất xứ rõ ràng và được trích dẫn đúng quy cách. Tơi xin hồn tồn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Thái Nguyên, tháng 11 năm 2020 Tác giả luận văn Inthavong Souksakhone III MỤC LỤC LỜI CẢM ƠN ......................................................................................................................... I LỜI CAM ĐOAN ..................................................................................................................II MỤC LỤC ............................................................................................................................. III DANH SÁNH BẢNG .......................................................................................................... VI DANH SÁNH HÌNH VẼ ................................................................................................... VII DANH SÁCH TỪ VIẾT TẮT .......................................................................................... IX CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC ..... 3 1.1 Giới thiệu tổng quan .......................................................................................................... 3 1.1.1 Khái niệm khai phá dữ liệu ................................................................................. 3 1.1.2 Nhiệm vụ của khai phá dữ liệu ........................................................................... 4 1.1.3 Một số ứng dụng khai phá dữ liệu ...................................................................... 4 1.1.4 Bước phát triển của việc tổ chức và khai thác các CSDL .................................. 5 1.1.5 Quá trình phát hiện tri thức ................................................................................. 6 1.1.6 Các bước của quá trình KPDL ............................................................................ 8 1.2. Một số kỹ thuật khai phá dữ liệu cơ bản ...................................................................... 10 1.2.1 Khai phá dữ liệu dự đốn .................................................................................. 10 1.2.1.1 Phân lớp (Classification) ............................................................................ 10 1.2.1.2 Hồi quy (Regression).................................................................................. 11 1.2.2 Khai phá dữ liệu mơ tả ...................................................................................... 11 1.2.2.1 Phân cụm .................................................................................................... 11 1.2.2.2 Khai phá luật kết hợp ................................................................................. 12 1.3 Một số so sánh giữa khai phá dữ liệu và các phương pháp cơ bản khác .................. 12 1.3.1 So sánh với phương pháp hệ chuyên gia (Expert Systems) ............................. 13 1.3.2 So sánh với phương pháp thống kê (Statistics) ................................................ 14 1.3.3 So sánh với phương pháp học máy (Machine Learning) .................................. 14 1.3.4 So sánh với phương pháp học sâu (Deep Learning) ......................................... 15 IV 1.4 Tổng kết chương .............................................................................................................. 18 CHƯƠNG 2 MỘT SỐ PHƯƠNG PHÁP VÀ KỸ THUẬT PHÂN LỚP DỮ LIỆU ............................................................................................................................. 19 2.1 Tổng quan về phân lớp dữ liệu ....................................................................................... 19 2.2 Phân lớp dữ liệu bằng cây quyết định ........................................................................... 22 2.2.1 Độ lợi thơng tin ................................................................................................. 26 2.2.2 Tỉ số độ lợi ........................................................................................................ 29 2.2.3 Chỉ số Gini ........................................................................................................ 30 2.2.4 Tỉa cây quyết định ............................................................................................ 32 2.3 Phân lớp dữ liệu Bayesian .............................................................................................. 33 2.3.1 Định lý Bayes ................................................................................................... 33 2.3.2 Phân lớp Nạve Bayes ....................................................................................... 34 2.4. Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM) .................................................. 36 2.4.1 Phân lớp đa lớp với SVM ................................................................................. 40 2.5. Phân lớp dữ liệu với Random Forest (rừng ngẫu nhiên) ........................................... 40 2.6 Một số phương pháp phân lớp dữ liệu khác ................................................................. 44 2.6.1 Thuật tốn phân lớp k-NN ................................................................................ 44 2.7 Đánh giá mơ hình phân lớp dữ liệu ............................................................................... 44 2.8 Tổng kết chương .............................................................................................................. 46 CHƯƠNG 3 ỨNG DỤNG PHÂN LỚP DỮ LIỆU MUSHROOM VỚI CƠNG CỤ WEKA VÀ MỘT SỐ THUẬT TỐN CƠ BẢN .................................................... 47 3.1 Giới thiệu bài tốn phân lớp dữ liệu Mushroom .......................................................... 47 3.1.1 Giới thiệu về bài tốn phân lớp dữ liệu Mushroom .......................................... 47 3.1.2. Thu thập, tiền xử lý và mã hĩa dữ liệu ......................................................... 47 3.1.3. Mơ tả sơ lược về dữ liệu ............................................................................... 51 3.2 Giới thiệu về cơng cụ Weka, cấu hình và ứng dụng phân lớp Mushroom .............. 52 3.2.1 Mơi trường Explorer ......................................................................................... 53 V 3.2.2 Khuơn dạng của tập dữ liệu .............................................................................. 54 3.2.3 Tiền xử lý dữ liệu .............................................................................................. 54 3.2.4 Phân tích chức năng phân lớp (Classify) .......................................................... 54 3.2.5 Mơ tả chức năng phân lớp (Classify) ................................................................ 58 3.3 Áp dụng các phương pháp phân lớp trên tập dữ liệu Mushroom .............................. 60 3.3.1 Thực hiện phân lớp bằng thuật tốn Naive Bayes ............................................ 61 3.3.2 Thực hiện phân lớp bằng thuật tốn k-Nearest neighbor ................................. 63 3.3.3 Thực hiện phân lớp bằng thuật tốn Support Vector Machines ....................... 66 3.4 Đánh giá mơ hình phân lớp dữ liệu Mushroom ........................................................... 70 3.4.1 Đánh giá mơ hình bằng phương pháp Hold-out ............................................... 70 3.4.2 Đánh giá mơ hình bằng phương pháp k-fold Cross validation ......................... 71 3.5 Kết luận thực nghiệm phần lớp dữ liệu Mushroom ..................................................... 71 3.6 Tổng kết chương .............................................................................................................. 72 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ....................................................................... 73 TÀI LIỆU THAM KHẢO .................................................................................................. 74 VI DANH SÁNH BẢNG Bảng 2.1: Bảng dữ liệu khách hàng .............................................................................. 25 Bảng 2.3: Bảng biểu diễn ma trận nhầm lẫn ................................................................. 45 Bảng 3.1: Bảng tổng hợp dữ liệu thu thập .................................................................... 47 Bảng 3.2: Các tính năng dành cho các dữ liệu nấm ...................................................... 48 Bảng 3.3: Mơ tả ý nghĩa các giá trị dữ liệu nấm ........................................................... 50 Bảng 3.4: Hiệu năng của mơ hình dự đốn, đánh giá bởi kiểm tra 70% ...................... 70 Bảng 3.5: Hiệu năng của mơ hình dự đốn, đánh giá bởi kiểm tra chéo mặt (fold=10 cross-validation) ............................................................................................. 71 VII DANH SÁNH HÌNH VẼ Hinh 1.1: Quá trình phát hiện tri thức ............................................................................. 6 Hinh 1.2: Quá trình khai phá dữ liêu (KPDL) ................................................................ 9 Hinh 1.3: Phân cụm tập dữ liệu cho vay thành 3 cụm .................................................. 12 Hinh 1.4: Một số lĩnh vực ứng dụng của trí tuệ nhân tạo ............................................. 13 Hinh 1.5: Học sau nhận dạng khuơn mặt hoặc biểu hiện cảm xúc trên khuân mặt ...... 16 Hình 2.1: Quá trình phân lớp dữ liệu - (a) Bước xây dựng mơ hình phân lớp ............. 21 Hình 2.2 : Quá trình phân lớp dữ liệu - (b1) Ước lượng độ chính xác của mơ hình .... 22 Hình 2.3: Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới ............................... 22 Hình 2.4:Phân lớp cho bài tốn cho vay vốn của ngân hàng ........................................ 23 Hình 2.5:Thuật tốn xây dựng cây quyết định .............................................................. 24 Hình 2.6: Minh họa cây quyết định ............................................................................... 26 Hình 2.7: Thuộc tính tuổi cĩ thơng tin thu được cao nhất ............................................ 29 Hình 2.8 :Các điểm trong khơng gian D chiều ............................................................. 36 Hình 2.9: Siêu phẳng phân lớp các điểm trong khơng gian .......................................... 37 Hình 2.10: Đồ thị biểu diễn các điểm trong mặt phẳng R+ .......................................... 37 Hình 2.11: Các điểm lựa chọn cho siêu phẳng ............................................................. 38 Hình 2.12: Kiến trúc mơ hình SVM .............................................................................. 38 Hình 2.13: Đồ thị biểu diễn siêu phẳng tìm được ......................................................... 39 Hình 2.14: Mơ hình rừng ngẫu nhiên ............................................................................ 42 Hình 2.15: Mơ hình chia tập dữ liệu Hold-out .............................................................. 45 Hình 2.16: Mơ hình chia tập dữ liệu Cross validation .................................................. 46 Hình 3.1: Sơ đồ Phương pháp phân lớp nấm (Mushroom). .......................................... 49 Hình 3.2 : Load Mushroom data ................................................................................... 51 Hình 3.3: Giao diên ban đầu Phần mềm WEKA .......................................................... 52 Hình 3.4: Giao diên của WEKA Explorer .................................................................... 53 Hình 3.5: Biểu diễn tập dữ liệu weather trong tập tin văn bản(text) ............................. 54 Hình 3.6: Biểu diễn đọc dữ liệu vào chương trình Weka ............................................. 55 VIII Hình 3.7: Biểu diễn chọn tab Classify để phân lớp....................................................... 55 Hình 3.8: Biểu diễn chọn thuật tốn phân lớp và xác định tham số ............................. 56 Hình 3.9: Biểu diễn chọn kiểu test ................................................................................ 56 Hình 3.10: Chạy thuật tốn phân lớp ............................................................................ 57 Hình 3.11: Bảng lưu thơng tin ....................................................................................... 57 Hình 3.12: Bảng kết quả sau chạy thuật tốn phân lớp ................................................. 58 Hình 3.13: Giải thích Running Information .................................................................. 58 Hình 3.14: Giải thích Classifier model (full training set) ............................................. 59 Hình 3.15: Giải thích xem xét tổng kết số liệu thống kế tập dữ liệu ............................ 59 Hình 3.16: Xem độ chính xác chi tiết cho từng phân lớp ............................................. 59 Hình 3.17: Confusion matrix của bộ phân lớp dữ liêu Mushroom ............................... 60 Hình 3.18: Sơ đồ tổng thể Mơ hình phân lớp dự đốn nấm (mushroom) ..................... 60 Hình 3.19: Cấu hình Weka cho thuật tốn Naive Bayes ............................................... 61 Hình 3.20: Kết quả phân lớp Weka cho thuật tốn Naive Bayes với số 70% Split ...... 62 Hình 3.21: Kết quả phân lớp Weka cho thuật tốn Naive Bayes kiểm tra chéo 10 mặt ................................................................................................................................. 63 Hình 3.22: Cấu hình Weka cho thuật tốn k-NN .......................................................... 64 Hình 3.23: Cấu hình Weka cho thuật tốn tìm kiếm trong thuật tốn k-NN ................ 64 Hình 3.24: Kết quả phân lớp Weka cho thuật tốn k-NN với số 70% Split ................. 65 Hình 3.25: Kết quả phân lớp Weka cho thuật tốn k-NN kiểm tra chéo 10 mặt .......... 65 Hình 3.26: Cấu hình Weka cho thuật tốn SVM .......................................................... 66 Hình 3.27: Kết quả phân lớp Weka cho thuật tốn SVM với số 70% Split .................. 67 Hình 3.28: Kết quả phân lớp Weka cho thuật tốn SVM kiểm tra chéo 10 mặt .......... 67 Hình 3.29: Cấu hình Weka cho thuật tốn J48 ............................................................. 68 Hình 3.30: Kết quả phân lớp Weka cho thuật tốn J48 decision với số 70% Split ...... 68 Hình 3.31: Kết quả phân lớp Weka cho thuật tốn J48 kiểm tra chéo 10 mặt.............. 69 Hình 3.32: Mơ hình cây quyết định hiển thị bởi Hold-out J48 ..................................... 69 Hình 3.33: cây quyết định Visualization ....................................................................... 70 IX DANH SÁCH TỪ VIẾT TẮT TT Từ viết tắt Dạng đầy đủ Chú thích 1 DM Data Mining Khai thác dữ liệu 2 SVM Supprot Vector Machin Máy hỗ trợ vector 3 KDD Knowlegde Discovery in Phát hiện tri thức trong Databases CSDL 4 RF Random forest Rừng ngẫu nhiên 5 E Edible Ăn được hoặc khơng cĩ độc 6 P Poisonous Cĩ độc hoặc Khơng ăn được 7 PCA Principal Component Analysis Thuật tốn phân tích thành phần chính 8 K-NN K-Nearest neighbor K láng giềng gần nhất 9 ACC Accuracy Độ chính xác 10 ARFF Attribute Relation File Format 1 MỞ ĐẦU Ly do chọn đề tài Sự bùng nổ và phát triển của ngành cơng nghệ thơng tin trong cách mạng 4.0 và việc ứng dụng cơng nghệ thơng tin ở hầu hết các lĩnh vực trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được thu thập và lưu trữ ngày càng lớn. Các hệ quản trị cơ sở dữ liệu truyền thống cũng chỉ khai thác được một lượng thơng tin nhỏ khơng cịn đáp ứng đầy đủ những yêu cầu, những thách thức mới. Do vậy một khuynh hướng mới được ra đời đĩ là kỹ thuật phát hiện tri thức trong cơ sở dữ liệu. Xin giới thiệu một cách tổng quan về phát hiện tri thức và khai phá dữ liệu cùng một số kỹ thuật cơ bản để trong khai phá dữ liệu để phát hiện tri thức và một số ứng dụng trong thực tế nhằm hỗ trợ cho tiến trình ra quyết định. Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, kỹ thuật này tương đối cịn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining - DM), giúp người sử dụng thu được những tri thức hữu ích từ những CSDL hoặc các nguồn dữ liệu khổng lồ khác. Rất nhiều doanh nghiệp và tổ chức trên thế giới đã ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và đã thu được những lợi ích to lớn. Khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge discovery) là một lĩnh vực quan trọng của ngành Cơng nghệ thơng tin với mục tiêu là tìm kiếm các tri thức cĩ ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn. Đây là lĩnh vực đã và đang thu hút đơng đảo các nhà khoa học trên thế giới và trong nước tham gia nghiên cứu. Phân lớp (classification) là một trong những bài tốn cơ bản trong khai phá dữ liệu với mục tiêu là phân loại các đối tượng vào các lớp cho trước. Nhưng để làm được điều đĩ, sự phát triển của các mơ hình tốn học và các giải thuật hiệu quả là chìa khố quan trọng. Vì vậy, trong luận văn này, tác giả sẽ đề cập tới kỹ thuật thường dùng trong khai phá dữ liệu, đĩ là Phân lớp (Classification). 2 Sau phần mở đầu, kết luận và tài liệu tham khảo nội dung chính của luận văn được trình bày chi tiết chia thành 3 chương như sau: Chương 1. Tổng quan về khai phá dữ liệu và phát hiện tri thức Phần này giới thiệu một cánh tổng quát về quá trình phát hiện tri thức nĩi chung và khai phá dữ liệu nĩi riêng. Đặc biệt nhấn mạnh về một kỹ thuật chính được nghiên cứu trong luận văn đĩ là Kỹ thuật phân lớp. Chương 2. Một số phương pháp và kỹ thuật phân lớp dữ liệu Trong phần này, sẽ giới thiệu tập trung vào kỹ thuật phân lớp được một số cách chi tiết. Cĩ nhiều kiểu phân lớp như phân lớp bằng cây quyết định (Decision Tree), phân lớp dữ liệu Bayesian, phân lớp dữ liệu với Random Forest (rừng ngẫu nhiên), Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM) và một số phương pháp phân lớp dữ liệu khác. Ngồi ra cịn đánh giá mơ hình của phương pháp phân lớp dữ liệu. Chương 3. Ứng dụng phân lớp dữ liệu Mushroom với cơng cụ Weka và một số thuật tốn cơ bản. Phần này giới thiệu bài tốn phân lớp dữ liệu Mushroom, giới thiệu về phân lớp dữ liệu sử dụng cơng cụ Weka, áp dụng các phương pháp phân lớp trên tập dữ liệu Mushroom. Sau đĩ phân chia tập dữ liệu để đánh giá mơ hình theo hai phương pháp Hold-out và K-fold cross validation để kết luận phân lớp dữ liệu Mushroom cho kết quả phân lớp tốt nhất. 3 CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC 1.1 Giới thiệu tổng quan Trong thời đại ngày nay, với sự phát triển vượt bật của cơng nghệ thơng tin, các hệ thống thơng tin cĩ thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng ngày của chúng. Khơng cĩ một lĩnh vực nào lại khơng cần đến sự hỗ trợ của cơng nghệ thơng tin và sự thành cơng của các lĩnh vực đĩ phụ thuộc rất nhiều vào việc nắm bắt thơng tin một cách nhạy bén, nhanh chĩng và hữu ích. Với nhu cầu như thế nếu chỉ sử dụng thao tác thủ cơng truyền thống thì độ chính xác khơng cao và mất rất nhiều thời gian. Từ khối dữ liệu này, các kỹ thuật trong Khai Phá Dữ Liệu (KPDL) và Máy Học (MH) cĩ thể dùng để trích xuất những thơng tin hữu ích mà chúng ta chưa biết. Các tri thức vừa học được cĩ thể vận dụng để cải thiện hiệu quả hoạt động của hệ thống thơng tin ban đầu. Do vậy việc khai phá tri thức từ dữ liệu trong các tập tài liệu lớn chứa đựng thơng tin phục vụ nhu cầu nắm bắt thơng tin cĩ vai trị hết sức to lớn. Từ đĩ, các kĩ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay. Khai phá dữ liệu (Data Mining) là một lĩnh vực mới xuất hiện, nhằm tự động khai thác những thơng tin, những tri thức cĩ tính tiềm ẩn, hữu ích từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp, từ đĩ làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả khoa học cùng những ứng dụng thành cơng trong khám phá tri thức, cho thấy, khai phá dữ liệu là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và cĩ nhiều triển vọng, đồng thời cĩ ưu thế hơn hẳn so với các cơng cụ phân tích dữ liệu truyền thống. Hiện nay, khai phá dữ liệu đã ứng dụng ngày càng rộng rãi trong các lĩnh vực như: Thương mại, tài chính, điều trị y học, viễn thơng, tin – sinh 1.1.1 Khái niệm khai phá dữ liệu Khai phá dữ liệu (data mining) là quá trình trích xuất, khai thác các mẫu trong các bộ dữ liệu lớn liên quan đến các phương pháp tại giao điểm của máy học, 4 thống kê và các hệ thống cơ sở dữ liệu và sử dụng những dữ liệu cĩ giá trị tiềm ẩn từ bên trong lượng lớn dữ liệu được lưu trữ trong các cơ sở dữ liệu (CSDL), kho dữ liệu, trung tâm dữ liệu lớn hơn là Big Data dựa trên kĩ thuật như mạng nơ ron, lí thuyết tập thơ, tập mờ, biểu diễn tri thức. Khai phá dữ liệu là một cơng đoạn trong hoạt động “làm sạch” dữ liệu giúp cho dữ liệu được truyền dẫn một cách nhanh nhất. Mục tiêu tổng thể của quá trình khai thác dữ liệu là trích xuất thơng tin từ một bộ dữ liệu và chuyển nĩ thành một cấu trúc dễ hiểu để sử dụng tiếp. Ngồi bước phân tích thơ, nĩ cịn liên quan tới cơ sở dữ liệu và các khía cạnh quản lý dữ liệu, xử lý dữ liệu trước, suy xét mơ hình và suy luận thống kê, các thước đo thú vị, các cân nhắc phức tạp, xuất kết quả về các cấu trúc được phát hiện, hiện hình hĩa và cập nhật trực tuyến. Khai thác dữ liệu là bước phân tích của quá trình “khám phá kiến thức trong cơ sở dữ liệu” hoặc KDD. Định nghĩa: Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Khai phá tri thức trong CSDL (Knowledge Discovery in Databases - KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá dữ liệu và KDD được các nhà khoa học trên hai lĩnh vực xem là tương đương với nhau. Thế nhưng, nếu phân chia một cách chi tiết thì khai phá dữ liệu là một bước chính trong quá trình KDD. 1.1.2 Nhiệm vụ của khai phá dữ liệu Những nhiệm vụ cơ bản nhất của KPDL là: • Phân cụm, phân loại, phân nhĩm, phân lớp. • Khai phá luật kết hợp. • Lập mơ hình dự báo. • Phân tích đối tượng ngồi cuộc. • Phân tích sự tiến hĩa. 1.1.3 Một số ứng dụng khai phá dữ liệu Mặc dù cịn rất nhiều vấn đề mà KPDL cần phải tiếp tục nghiên cứu để giải quyết nhưng tiềm năng của nĩ đã được khẳng định bằng sự ra đời của rất nhiều ứng 5 dụng. các ứng dụng của KPDL trong khoa học cũng được phát triển. các cơng ty phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: oracle tích hợp các cơng cụ khai phá dữ liệu vào bộ oracle 9i, IBM đã đi tiên phong trong việc phát triển các ứng dụng khai phá dữ liệu với các ứng dụng như Intelligence miner, Ta cĩ thể đưa ra một số ứng dụng trong các lĩnh vực như: • Thương mại: Phân tích dữ liệu bán hàng và thi trường, phân tích đầu tư, quyết định cho vay, phát hiện gian lận. • Thơng tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm. • Thơng tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, khoa học địa lý: dự báo động đất. • Trong y tế, marketing, ngân hàng, viễn thơng, du lịch, internet. 1.1.4 Bước phát triển của việc tổ chức và khai thác các CSDL Cùng với việc tăng khơng ngừng khối lượng dữ liệu, các hệ thống thơng tin cũng được chuyên mơn hĩa, phân hoạch theo các lĩnh vực ứng dụng như sản xuất, tài chính, buơn bán thị trường v.v. Như vậy, bên cạnh chức năng khai thác dữ liệu cĩ tính chất tác nghiệp, sự thành cơng trong kinh doanh khơng cịn là năng suất của các hệ thống thơng tin nữa mà là tính linh hoạt và sẵn sàng đáp lại những yêu cầu trong thực tế, CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu đĩ. các quyết định cần phải cĩ càng nhanh càng tốt và phải chính xác dựa trên những dữ liệu sẵn cĩ. lúc này các mơ hình CSDL truyền thống và ngơn ngữ SQL đã cho thấy khơng cĩ khả năng thực hiện cơng việc này. Để lấy được tri thức trong khối dữ liệu khổng lồ này, người ta đã đi tìm những kỹ thuật cĩ khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập hợp các cơ sở dữ liệu ổn định, cĩ chất lượng, chỉ được sử dụng riêng cho một vài mục đích nào đĩ. các kỹ thuật đĩ được gọi chung là kỹ thuật tạo kho dữ liệu (data warehousing) và mơi trường các dữ liệu cĩ được gọi là các kho dữ liệu (data warehouse). Với những thách thức như vậy, các nhà nghiên 6 cứu đã đưa ra một phương pháp mới trên kho dữ liệu đáp ứng cả nhu cầu trong khoa học cũng như trong hoạt động thực tiễn. Đĩ chính là cơng nghệ phát hiện tri thức từ cơ sở dữ liệu 1.1.5 Quá trình phát hiện tri thức Một vấn đề rất quan trọng để dẫn đến thành cơng là việc biết sử dụng thơng tin một cách cĩ hiệu quả. Điều đĩ cĩ nghĩa là từ các dữ liệu sẵn cĩ phải tìm ra những thơng tin tiềm ẩn cĩ giá trị mà trước đĩ chưa được phát hiện, phải tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng. Thực hiện cơng việc đĩ chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) mà trong đĩ kỹ thuật này cho phép ta lấy được các tri thức chính là pha khai phá dữ liệu (KPDL). Quá trình phát hiện tri thức tiến hành qua 6 giai đoạn như Hình 1.1 Hinh 1.1: Quá trình phát hiện tri thức Quá trình khám phá tri thức từ CSDL là một quá trình cĩ sử dụng nhiều phương pháp và cơng cụ tin học nhưng vẫn là một quá trình mà trong đĩ con người là trung tâm. Do đĩ, nĩ khơng phải là một hệ thống phân tích tự động mà là một hệ thống bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và CSDL, tất nhiên là với sự hỗ trợ của các cơng cụ tin học. Người sử dụng hệ thống ở đây 7 phải là người cĩ kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để cĩ thể chọn được đúng các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quan tâm so với mục đích. Tri thức mà ta nĩi ở đây là các tri thức rút ra từ các CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. Do đĩ, quá trình phát hiện tri thức cũng mang tính chất hướng nhiệm vụ, khơng phải là phát hiện mọi tri thức bất kỳ mà là phát hiện tri thức nhằm giải quyết tốt nhiệm vụ đề ra. Trong hình 1.1 quá trình phát hiện tri thức bắt đầu của quá trình là kho dữ liệu thơ và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì cĩ vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khĩ khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại tồn bộ quá trình, v.v... 1.1.5.1 Gom dữ liệu (Gathering) Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. 1.1.5.2 Lựa chọn dữ liệu (Selection) Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đĩ phục vụ mục đích khai thác, ví dụ chọn tất cả những người cĩ tuổi đời từ 25 - 35 và cĩ trình độ đại học. 1.1.5.3 Làm sạch, tiền xử lý và chuẩn bị dữ liệu (Cleaning, Pre-processing and Preparation) Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nĩ là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính khơng đủ chặt chẽ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vơ nghĩa và khơng cĩ khả năng kết nối dữ liệu. Ví dụ: điểm = -1. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu khơng chặt chẽ nĩi trên. Những dữ liệu dạng này được xem như thơng tin dư thừa, khơng cĩ giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu khơng được “làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. 1.1.5.4 Chuyển đổi dữ liệu (Transformation) 8 Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra cĩ thể sử dụng và điều khiển được bởi việc tổ chức lại nĩ, tức là dữ liệu sẽ được chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhĩm hoặc tập hợp. 1.1.5.5 Khai phá dữ liệu (Data mining) Đây là bước mang tính tư duy trong khai phá dữ liệu. Ở giai đoạn này nhiều thuật tốn khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật tốn thường dùng là nguyên tắc phân lớp, nguyên tắc kết, v.v... 1.1.5.6 Đánh giá các luật và biểu diễn tri thức (Evaluation of ... Cụ thể nĩ đã được chia thành 3 loại tuổi rời rạc: trẻ (youth), trung niên (middle_age) và già (senior). Điểm mấu chốt trong giải thuật xây dựng cây quyết định ở trên là hàm lựa chọn thuộc tính tốt nhất để phân chia dữ liệu. Phần tiếp theo sẽ trình bày một số độ đo dùng để đánh giá “chất lương” của các thuộc tính. age? youth senior Middle_age student? yes credit_rating? no yes fair excellent no yes no yes Hình 2.6: Minh họa cây quyết định Trong cây quyết định: • Nút gốc: là node trên cùng của cây • Node trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình chữ nhật) • Nhánh: biểu diễn các kết quả của kiểm tra trên node trong (mũi tên) • Node lá: biểu diễn lớp hay sự phân phối lớp (hình trịn) Để phân lớp mẫu dữ liệu chưa biết, giá trị các thuộc tính của mẫu được đưa vào kiểm tra trên cây quyết định. Mỗi mẫu tương ứng cĩ một đường đi từ gốc đến lá và lá biểu diễn dự đốn giá trị phân lớp mẫu đĩ. 2.2.1 Độ lợi thơng tin Độ lợi thơng tin (information gain) là độ đo đước sử dụng trong giải thuật ID3. Đầu tiên là cơng thức đo lượng thơng tin kỳ vọng để phân lớp một phần tử trong tập dữ liệu D đước đo bằng cơng thức sau: 27 m Info( D )=− p log( p ) (2.1) i=1 ii2 Trong đĩ pi là xác suất một phần tử dữ liệu trong D thuộc vào lớp Ci và nĩ Di được ước lượng bằng cơng thức p = , với D là tập các phần tử dữ liệu trong D i D i thuộc vào lớp Ci ; m là số lượng các lớp trong D. Hàm logarit cơ số 2 được sử dụng là do cơng thức trên đo lượng thơng tin theo đơn vị bit (theo lý thuyết thơng tin của C. Shannon). Hàm info(D) cịn được gọi là entropy của D. Bây giờ giả sử ta phân chia dữ liệu trong D theo thuộc A nào đĩ, và giả sử thuộc tính này cĩ v giá trị (rời rạc) khác nhau là {a1, a2, ..., av} Thuộc tính này chia tập dữ liệu D thành v tập con {D1, D2, ..., Dv} trong đĩ Dj là tập phần tử dữ liệu cĩ giá trị của thuộc tính A là ai. Tập con này sẽ tương ứng với một nhánh cây được phát triển từ nút N trong giải thuật tạo cây quyết định. Trường hợp lý tưởng thì ta muốn tập con này sẽ cĩ khả năng phân lớp chính xác các phần tử trong nĩ, hay nĩi một cách khác ta muốn tập con này càng đồng nhất (pure) càng tốt, đồng nhất ở đây cĩ thể hiểu là các phần tử trong trong tập con này đều cùng thuộc về một lớp. Tuy nhiên trong thực tế thì các tập này thường khơng đồng nhất (impure) vì nĩ chứa các phần tử dữ liệu thuộc về cac lớp khác nhau, do đĩ chúng ta cần thêm thơng tin để phân lớp chính xác tập con này. Lượng thơng tin này được đo bởi: v Dj infoAj()() D= info D (2.2) j=1 D Dj Trong đĩ được dùng làm trọng số của tập con D . Giá trị của info (D) là D J A lượng thơng tin kỳ vọng để phân lớp một phần tử dữ liệu trong D dựa trên việc chia dữ liệu bằng thuộc tính A. Giá trị này càng nhỏ thì độ đồng nhất của các tập con càng cao. Cuối cúng hàm đo độ lợi thơng tin được tính bằng cơng thực: Gain()()() A=− info D infoA D (2.3) 28 Giá trị Gain(A) cho chúng ta biết ta được lợi bao nhiều nếu chia dữ liệu theo thuộc tính A. Giá trị này càng lớn thì càng tốt, do đĩ thuộc tính nào cĩ giá trị Gian () lớn nhất sẽ được chọn để phân nhánh trong quá trình xây dựng cây quyết định. Để minh họa cho độ đo này ta tính tốn một thuộc tính trên tập dữ liệu ở bảng 2.1. Trong bảng này trường cuối cùng là nhãn của dữ liệu (Mua máy tính), nĩ cĩ 2 giá trị, do đĩ số lớp ở đây là 2. Cĩ 9 phần tử dữ liệu cĩ nhãn là yes và 5 phần tử dữ liệu cĩ nhãn là no, do đĩ theo cơng thức (1.2) ta cĩ: 9 9  5  5  info( D )= − log22  − log   = 0.94 bits 14 14  4  14  Tiếp đến theo cơng thức (2.2) ta tính giá trị của hàm cho thuộc tính tuổi (age): 5 2 2 3 3 infoage ( D )=  − log22 − log 14 5 5 5 5 4 4 4 0 0 +  −log22 − log 14 4 4 4 4 5 3 3 2 2 +  −log22 − log 14 5 5 5 5 = 0.694bits Tiếp đến theo cơng thức (2.3) ta cĩ độ lời thơng tin theo thuộc tính tuổi sẽ là: Gain( age )= info ( D ) − infoage ( D ) = 0.940 − 0.694 = 0.246 bits Tường tự ta cĩ thể tính được giá trị độ lợi thơng tin cho các thuộc tính thu nhập (income), sinnh viên (student) và đành giá tín dụng (credit_rating) Gain(income)= 0.092 bits, Gain (student)= 0.151 bits và Gain (credit rating) = 0.048 bits. Từ kết quả này, chúng ta thấy thuộc tính tuổi sẽ được chọn để phan chia dữ liệu. Lặp lại quá trình xây dựng cây tương ứng với các tập con dữ liệu (đã bỏ đi thuộc tính tuổi) ta sẽ thu được cây quyết định như hình (2.6) 29 Hình 2.7: Thuộc tính tuổi cĩ thơng tin thu được cao nhất 2.2.2 Tỉ số độ lợi Độ đo độ lợi thơng tin hoạt động khơng tốt trong trường hợp một thuộc tính cĩ nhiều giá trị. Vì dụ, thuộc tính mã sản phẩm (product_ID), hay mã giao dịch sẽ cĩ rất nhiều giá trị. Đặc biệt nữa, khi chia dữ liệu theo thuộc tính này thì mỗi một tập con dữ liệu sẽ chỉ cĩ tương ứng một bản ghi, do đĩ các tập con này là hồn tồn đồng nhất. Hay nĩi một cách khác, lượng thơng tin cần để phân lớp tập dữ liệu D dưa trên cách phân chia dữ liệu trên thuộc tính này InfoProduct_ID(D)= 0. Và giá trị độ lợi thơng tin sẽ đạt giá tri tối đa: Gian (Product_ID) = Info(D)- InfoProduct_ID(D)=Info(D) Nhưng rõ ràng việc phân lớp dựa trên thuộc tính này là vơ nghĩa. Do đĩ, trong giải thuật C4.5 (hậu duệ của giải thuật ID3) tác giả đã đề xuất sử dụng một độ đo mới gọi là tỉ số độ lợi (gain ratio) để cố tránh nhược điểm trên. Hàm này sử dụng một phương pháp chuẩn hĩa độ lợi thơng tin bằng cách sử dụng giá trị phân chia thơng tin (split information) được định nghĩa tương tự như hàm Info(D) như sau: v DD SplitInfo( D )= −jj  log  (2.4) A  DD2  j=1  30 Giá trị này biểu diễn thơng tin tiềm năng được sinh ra thơng qua việc chia tập dữ liệu huấn luyện D thành v tập con tương ứng với các giá trị của thuộc tính A. Chú ý rằng với mỗi giá trị của thuộc tính j, nĩ tính tốn số lượng các phần tử cĩ giá trị thuộc tính A là j trên tổng số lượng các phần tử của D. Đây là điểm khác so với độ lợi thơng tin, do đĩ cơng thức tính tỉ số đọ lợi sẽ là: Gain() A GainRatio() A = (2.5) SplitInfo() A Trong đĩ, hàm SplitInfoA (D) được viết ngắn gọn thành SplitInfo(A). Dựa trên độ đo này, các thuộc tính cĩ giá trị tỉ số độ lợi cao sẽ được chọn làm thuộc tính phân chia dữ liệu. Cĩ một chú ý rằng, nếu hàm SplitInfo(A)=0 thì cơng thức trên khơng dùng được, do đĩ cĩ thêm rằng bược để tránh trường hợp này. Cụ thể giá trị độ lợi thơng tin của thuộc tính được chọn phải đủ lớn, ít nhất là lớn hơn giá trị trung bình độ lợi thơng tin của tất cả các thuộc tính. Trở lại bảng dữ liệu (2.1), ta tính tỉ số độ lợi cho thuộc tính thu nhập (Income). Đầu tiên ta sử dụng cơng thức (2.4) để tính SplitInfoincome(D) 4 4  6  6  4  4  SplitInfoincome ( D )= −  log222  −  log   −  log   14 14  14  14  14  14  = 0.962 Gain( income ) 0.029 Do đĩ GainRatio( income )= = = 0.031 SplitInfo( income ) 0.962 2.2.3 Chỉ số Gini Đây là độ đo được sử dụng trong giải thuật CART, chỉ số Gini đo độ khơng đồng nhất của một tập dữ liệu D bằng cơng thức: m 2 Gini( D )=− 1  pi (2.6) i=1 Trong đĩ, pi cĩ ý nghĩa giống như cơng thức (2.1); m là số lượng lớp trong D. Chỉ số Gini quan tâm đến trường hợp ta sẽ sử dụng một thuộc tính và chia dữ liệu thành 2 nửa. Để đơn giản, ta xét trường hợp thuộc tính A cĩ v giá trị khác nhau {a1, a2, ..., av} xuất hiện trong D. Để xác định cách phân chia tốt nhất ta xét tốn bộ 31 các tập con của D phân chia theo của giá trị A. Do đĩ nếu A cĩ v giá tri khác nhau thì ta sẽ cĩ 2v tập con của D .Vì dụ thuộc tính thu nhập (income) cĩ 3 giá trị {low, medium, high} thì các tập con cĩ thể sẽ là {low, medium, high}, {low, medium}, {medium, high}, {low, high}, {low}, {medium}, {high}, và tập rỗng {}. Chúng ta khơng xét 2 tập con {low, medium, high} và {} vì nĩ khơng chia dữ liệu ra 2 tập, do đĩ ta cĩ tổng số 2v -2 cách để chia tập dữ liệu D thành 2 tập con dựa trên dựa trên thuộc tính A. Khi chia tập dữ liệu D thành 2 nửa D1 và D2 chúng ta xem xét độ khơng đồng nhất (impurity) của dữ liệu trong 2 nửa này: DD Gini()()() D=+12 Gini D Gini D (2.7) A DD12 Trong trường hợp thuộc tính A cĩ giá trị liên tục thì chúng ta phải xác định các điểm (giá trị) split_point đẻ chia tập dữ liệu D thành 2 tập con. Các điểm split_point cĩ thể lấy là giá trị trung bình giữa 2 giá trị gần nhau nhất của thuộc tính A. Khi xác định được chia dữ liệu split_point ta cĩ thể chia dữ liệu D thành 2 tập dữ liệu con là D1 và D2 sao cho: D1 = X  D xA  split_ point và D1 = X  D xA  split_ point trong đĩ vA là giá trị của thuộc tính A. Khi đĩ ta định nghĩa độ giảm của độ bất đồng nhất của dữ liệu khi chia dữ liệu thành 2 tập con theo thuộc tính A: Gini()()() A = Gini D − GiniA D (2.8) Trong đĩ cách phân chia nào mà tạo ra 2 tập con cĩ giá trị Gini() A lớn nhất (hay GiniA(D) nhỏ nhất) sẽ được chọn. tuy nhiên trong trường hợp này khác với các độ đo trước, ta cần kết hợp cách phân chia hay giá trị điểm phân chia (split point) với thuộc tính để dúng làm đều kiện nhánh cây quyết định. Quy lại cơ sở dữ liệu khách hàng ở bảng (2.1), ta cĩ 9 phần tử dữ liệu thuộc vào lớp Cyes và 5 phần tử dữ liệu thuộc tính vào lớp Cno do đĩ chỉ số Gini(D) đơ độ bất đồng nhất trong D là: 22 95    Gini( D )= 1 −  −   = 0.459 14   14  Tiếp theo ta xét thuộc tính thu nhập (income), bắt đầu bằng cách phân chia {low, medium} và {high}. Với cách phân chia này thì ta cĩ tập D1 chứa 10 phần tử 32 dữ liệu cĩ thuộc tính income cĩ giá trị nằm trong tập {low, medium} và tập D2 chứa 4 phần tử cĩ giá trị income= high. Khi đĩ chỉ số Gini sẽ được tính tốn là: 10   4  Giniincome low, medium ()()() D=+  Gini D12   Gini D   14   14  22 10 6   4  =1 − −     14 10   10  22 4 1   3  +1 − −     14 4   4  ==0.45Giniincome high ( D ) Tương tự, giá trị Gini cho cách chia {medium, high} và {low} là 0.3; giá trị Gini cho cách chia {low, high} và {medium} là 0,315. Do đĩ cách chia {medium, high} và {low} sẽ được chọn làm điều kiện để phân nhánh cây quyết định vì nĩ cho ta giá trị Gini nhỏ nhất. Với thuộc tính tuổi (age) thì cách phân chia {youth, senior} và {middle_age} cho giá trị tốt nhất là 0.375. Với thuộc tính student và credit_rating đều là giá trị nhị phân nên chúng ta chỉ cĩ một cách chia duy nhất, giá trị Gini của 2 thuộc tính này lần lượt là 0.367 và 0.429. Qua kết quả này ta thấy thuộc tính income cho giá trị Gini nhỏ nhất do đĩ nĩ sẽ được chọn để làm điều kiện phân nhánh cây quyết định, khác với 2 độ đo ở trên chọn thuộc tính tuổi làm điều kiện phân nhánh đầu tiên. Một điều chú ý là vời độ đo này thì ta khơng chỉ quan tâm đến thuộc tính dùng để phân chia tập dữ liệu mà cịn quan tâm đến cách chia dữ liệu theo thuộc tính đĩ. 2.2.4 Tỉa cây quyết định Sau khi cây được xây dựng, nĩ cĩ thể chứa nhiều nhánh phản ánh sự bất thường trong dư liệu huấn luyện: cĩ thể là các trường hợp ngoại lệ, dữ liệu lỗi hay là dữ liệu nhiều. Hiện tương trên cũng gây ra hệ quả là xảy ra hiện tượng cây thu được quá phù hợp dữ liệu (overfitting). Để giải quyết vấn đề này phương pháp tỉa cây (tree pruning) được đề xuất. Phương pháp tỉa cây vầ bản chất là loại bỏ các nhánh ít tin cây nhất, do đĩ ta khơng những thu được cây cĩ khả năng phân lớp tốt 33 hơn mà cịn làm cho cây cơ đọng hơn và tốc đọ xử lý sẽ nhánh hơn. Phương pháp tỉa cây được chia thành 2 loại: tỉa trước (prepruning) cây và tỉa sau (postpruning). Trong phương pháp tỉa cây trước, cây sẽ được tỉa ngay trong giai đoạn xây dựng cây, nĩ sẽ tương ứng với các điều kiện để dừng phát triển một nhánh nào đĩ. Cịn phương pháp tỉa cây sau lại xử lý cây sau khi nĩ đã được xây dựng hồn chính. 2.3 Phân lớp dữ liệu Bayesian Bộ phân lớp Bayesian là một giải thuật thuộc lớp giải thuật phân lớp thống kê, nĩ cĩ thể dữ đốn xác suất của một phần tử dữ liệu thuộc vào một lớp là bao nhiều. Phân lớp Bayesian dựa trên định lý Bayes (định lý được đặt theo then tác giả của nĩ là Thomas Bayes). Một classifier đơn giản của Bayesian đĩ là Naive Bayes, so với việc thực thi của classifier cây quyết định và mạng nơron, classifier Bayesian đưa ra độ chính xác cao và nhanh khi áp dụng vào các cơ sở dữ liệu lớn. Mục 2.3.1 nĩi lại các khái niệm xác suất cơ bản và định lý Bayes. Sau đĩ ta sẽ xem phân lớp Nạve Bayes trong 2.3.2 2.3.1 Định lý Bayes Gọi X là một chứng cứ (evidience) (trong bài tốn phân lớp thì X sẽ là một phần tử đữ liệu), Y là một giả thiết nào để cho X thuộc về một lớp một lớp C nào đĩ. Trong bài tốn phân lớp chúng ta muốn xác định giá trị P (Y |X) là xác suất để giả thiết Y là đúng với chứng cứ X thuộc vào lớp C với điều khiện ta biết các thơng tin mơ tả X. P (Y |X) là một xác suất hậu nghiệm (posterior probability hay posteriori probability) của Y với điều kiện X. Giả sử tập dữ liệu khách hàng của chúng ta được mơ tả bởi các thuộc tính tuổi và thu nhập, và một khách hàng X cĩ tuổi là 35 và thu nhập là $40.000. Giả sử Y là giả thiết khách hàng đĩ sẽ mua máy tính, thì P (Y /X) phảm ánh xác suất người dùng X sẽ mua máy tính, thì P (Y |X) phản ánh xác suất người dùng X sẽ mua máy tính với điều kiện ta biết tuổi và thu nhập của người đĩ. Ngược lại P(Y) là xác suất tiền nghiệm (prior probability hay priori probability) của Y. Trong ví dụ trên, nĩ là xác suất một khách hàng sẽ mua máy tính mà khơng cần biết các thơng tin về tuổi hay thu nhập của họ. Hay nĩi cách khác, xác suất này khơng phụ thuộc vào X. Tương tự P (X |Y) là xác suất của X với điều 34 kiện Y, nĩ là một xác hậu nghiệm. Vì dụ, nĩ là xác suất người dùng X (cĩ tuổi là 35 và thu thập là $40.000) sẽ mua máy tính với điều kiện ta đã biết là người dùng đĩ sẽ mua máy tính. Cuối cùng P(X) là xác suất tiền nghiệm cảu X. Trong ví dụ trên, nĩ sẽ là xác suất một người trong tập dữ liệu sẽ xĩ tuổi 34 và thu nhập $40.000. Các xác suất này sẽ được tính dựa vào định lý Bayes như sau: P( XY ) PXYPY( ) ( ) PYX( ) == (2.9) PXPX( ) ( ) Với: PX( ) : Xác suất của sử kiện X xảy ra, Khơng quan tâm đến Y PY( ) : Xác suất của sử kiện Y xảy ra, Khơng quan tâm đến X PXY( ) : Xác suất (cĩ điều kiện) của sự kiện X xảy ra, nếu biết rằng sự kiện Y xảy ra PYX( ) : Xác suất hậu nghiệm của Y nếu biết X Thuật tốn bayes dựa trên định lý Bayes áp dụng cho các bài tốn giả định điều kiện độc lập. Nghĩa là giả định đặc trưng của một lớp xảy ra khơng ảnh hưởng hay phụ thuộc vào đặc trưng của lớp khác 2.3.2 Phân lớp Nạve Bayes Bộ phân lớp Nạve Bayes hay là bộ phân lớp Bayes đơn giản (simple Bayes classifier) hoạt động như sau: 1) Gọi D là tâp dữ liệu huấn luyện, trong đĩ mỗi phần tử dữ liệu X được biểu diễn bằng một vector chứa n giá trị thuộc tính A1, A2, ..., An, X= {x1, x2, ..., xn}. 2) Giả sử cĩ m lớp C1, C2, ..., Cm; Cho một phần tử dữ liệu X, bộ phân lớp sẽ gán nhãn cho X là lớp cĩ xác suất hậu nghiệm lớn nhất. Cụ thể, bộ phân lớp Bayes sẽ dự đốn X thuộc vào lớp Ci nếu và chỉ nếu: PCXPCX( ij)  ( ) với (1,i  m i  j) (2.10) Ci: Phân lớp i, với i= {1, 2 , m} Giá trị này sẽ được tình dựa vào định lý Bayes: 35 PXCPC ( ii) ( ) (2.11) PCX( i ) = PX( ) 3) Để tìm giá trị xác suất lớn nhất, ta nhận thấy trong cơng thức (2.10) thì giá trị P(X) là giống nhau với mọi lớp nên ta khơng cần tìm. Do đĩ ta chỉ cần tìm giá trị lớn nhất của P(X|Ci) x P(Ci). chú ý rằng P(Ci) được ước lượng bằng cơng thức Di PC( ) = , trong đĩ Di là tập các phần tử dữ liệu thuộc vào lớp Ci. nếu xác suất i D tiền nghiệm P(Ci) cũng khơng xác định được thì ta coi chúng bằng nhau P(C1) = P(C2) = ...=P(Cm), khi đĩ ta chỉ cần tìm giá trị P(X|Ci) lớn nhất. 4) Khi số lượng các thuộc tính mơ tả dữ liệu là lớn thì chi phí tính tốn P(X|Ci) là rất lớn, do đĩ để làm giảm độ phức tạp, giải thuật Nạve Bayes giả thiết các thuộc tính là độc lập nhau hay khơng cĩ sự phụ thuộc nào giữa các thuộc tính. Khi đĩ ta cĩ thể tính: n PXC( i) = PxC( k i) = PxC( 1 i) ...  PxC( n i ) (2.12) k=1 Khi đĩ xác suất xảy ra của một điều kiện x mới là n max (P( ci)) =  P( x k C i ) (2.13) k=1 Trong đĩ: P(Ci): được tính dựa trên tần suất xuất hiện tài liệu trong tập huấn luyện. P(xk|Ci): được tính từ những tập thuộc tính đã được tính trong quá trình huấn luyện Bước tính thuật tốn Bayes: Bước 1: Huấn luyện tập dữ liệu: Tính xác suất P(Ci) Tính xác suất P(xk|Ci) Bước 2: Lớp của giá trị mới được gắn cho lớp cĩ xác suất lớn nhật theo cơng thức: 36 n max (P( ci)) =  P( x k C i ) k=1 2.4. Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM) Support vector machine là một khái niệm trong thống kê và khoa học máy tính cho một tập hợp các phương pháp học cĩ giám sát liên quan đến nhau để phân loại và phân tích hồi quy. Nguyên lý cơ bản của SVM là tìm một siêu phẳng phân hoạch tối ưu cho phép chia các điểm trong khơng gian nhiều chiều thành 2 lớp nằm ở 2 phía chưa siêu phẳng. SVM dạng chuẩn nhận dữ liệu vào và phân loại chúng vào hai lớp khác nhau. Do đĩ SVM là một thuật tốn phân loại nhị phân. Hình 2.8 :Các điểm trong khơng gian D chiều Cho trước n điểm trong khơng gian D chiều (mỗi điểm thuộc vào một lớp kí hiệu là +1 hoặc -1), mục đích của giải thuật SVM là tìm một siêu phẳng phân hoạch tối ưu cho phép chia các điểm này thành hai phần sao cho các điểm cùng một lớp nằm về một phía với siêu phẳng này. n D=( xi, y i) x i  p , y i  − 1,1 (2.14)  i=1 Mỗi siêu phẳng đều cĩ thể được viết dưới dạng một tập hợp các điểm x thỏa mãn: w• x − b = 0 (2.15) 37 Cơng thức trên là tích vơ hướng với vector pháp tuyến của siêu phẳng (w) và b đĩng vai trị là tham số. Ta cần chọn w và b để cực đại hĩa lề, hay khoảng cách giữa hai siêu mặt song song ở xa nhau nhất cĩ thể trong khi vẫn phân chia được dữ liệu Các siêu mặt ấy được xác định bằng: w• x − b =1 (2.16) w• x − b = −1 (2.17) Hình 2.9: Siêu phẳng phân lớp các điểm trong khơng gian Ví dụ: Giả sử ta cĩ một tập được gán nhãn (+1): {(3,1), (3, -1), (6, 1), (6, -1)} Và tập các điểm được gán nhãn âm (-1): {(1, 0), (0, 1), (0, -1), (-1, 0)} trong mặt phẳng R+ Hình 2.10: Đồ thị biểu diễn các điểm trong mặt phẳng R+ 38 Ta sử dụng SVM để phân biệt hai lớp (+1 và -1). Bởi vì dữ liệu được chia tách một cách tuyến tính, nên chúng ta sử dụng một hàm tuyến tính để phân tách 2 lớp. Theo quan sát, ta chọn ra ba vector hỗ trợ để thực thi các phép tốn nhằm tìm ra mặt phẳng phân tách tối ưu nhất: {s1 = (1,0), s2 = (3,1), s3 = (3, -1)} Hình 2.11: Các điểm lựa chọn cho siêu phẳng Các vector hỗ trợ được tăng cường bằng cách thêm 1. Tức là s1 = (1,0), thì nĩsẽ được chuyển đổi thành s = (1, 0, 1). Theo kiến trúc SVM, Nhiệm vụ là tìm ra những giá trị αi. 1(s 1). ( s 1) +  2 ( s 2) . ( s 1) +  3 ( s 3) . ( s 1 ) = − 1 (2.18) 1(s 1). ( s 2) +  2 ( s 2) . ( s 2) +  3 ( s 3) . ( s 2 ) = − 1 (2.19) 1(s 1). ( s 3) +  2 ( s 2) . ( s 3) +  3 ( s 3) . ( s 3 ) = − 1 (2.20) Hình 2.12: Kiến trúc mơ hình SVM 39 Do sử dụng SVM tuyến tính nên hàm Φ () - dùng để chuyển đổi vector từ khơng gia dữ liệu đầu vào sang khơng gian đặc trưng – sẽ bằngΦ = () I. Biểu thức trên được viết lại như sau: 1s 1. s 1+  2 s 2 . s 1 +  3 s 3 . s 1 = − 1 (2.21) 1s 1. s 2+  2 s 2 . s 2 +  3 s 3 . s 2 = + 1 (2.22) 1s 1. s 3+  2 s 2 . s 3 +  3 s 3 . s 3 = − 1 (2.23) Rút gọn biểu thức thơng qua tính tích vơ hướng của các vector: 21+ 4  2 + 4  3 = − 1 (2.24) 41+ 11  2 + 9  3 = + 1 (2.25) 41+ 9  2 + 11  3 = + 1 (2.26) Giải hệ phương trình trên cĩ: α1 = -3.5, α2 = 0.75, α3 = 0.75. Tiếp đến tính trọng số ω thơng qua cơng thức: 1   3   3   1          =s = −3.5 0 + 0.75 1 + 0.75 − 1 = 0  ii         i         1   1   1  − 2  Siêu phẳng phân chia hai lớp đĩ là: y = wx + b với w = (1, 0) và b = -2 Hình 2.13: Đồ thị biểu diễn siêu phẳng tìm được 40 2.4.1 Phân lớp đa lớp với SVM Thuật tốn SVM trình bày ở trên chỉ hoạt động với dữ liệu cĩ 2 lớp, trong thực tế số lượng lớp của dữ liệu cĩ thể rất lớn. Rất may là cũng cĩ giải pháp để mở rộng SVM cho bài tốn cĩ nhiều lớp. Bài tốn phân lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đĩ cần cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một trong những phương pháp cải tiến đĩ là sử dụng thuật tốn 1-against-all [Hau02, Milgram06]. Ý tưởng cơ bản là chuyển bài tốn phân lớp nhiều lớp thành nhiều bài tốn phân lớp nhị phân như sau: • Giả sử tập dữ liệu mẫu (x1, y1), ..., (xm, ym) với xi là một vector n chiều và yYi  là nhãn lớp được gán cho vector xi (cĩ m nhãn lớp khác nhau) • Biến đổi tập Y ban đầu thành m tập cĩ hai lớp con Zi=− y i, Y y i • Áp dụng SVM phân lớp nhị phân cơ bản với m tâp Zi để xây dựng siêu phẳng cho phân lớp này. Như vậy ta sẽ cĩ m bộ phân lớp nhị phân. Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp đa lớp mở rộng với SVM 2.5. Phân lớp dữ liệu với Random Forest (rừng ngẫu nhiên) Tiếp cận Random Forest (rừng ngẫu nhiên) do (Breiman, 2001) đưa ra là một trong những phương pháp tập hợp mơ hình thành cơng nhất. Giải thuật random forest tạo ra một tập hợp các cây quyết định (Breiman et al., 1984), (Quinlan, 1993) khơng cắt nhánh, mỗi cây được xây dựng trên tập mẫu bootstrap (lấy mẫu cĩ hồn lại từ tập học), tại mỗi nút phân hoạch tốt nhất được thực hiện từ việc chọn ngẫu nhiên một tập con các thuộc tính. Lỗi tổng quát của rừng phụ thuộc vào độ chính xác của từng cây thành viên trong rừng và sự phụ thuộc lẫn nhau giữa các cây thành viên. Giải thuật random forest xây dựng cây khơng cắt nhánh nhằm giữ cho thành phần lỗi bias thấp (thành phần lỗi bias là thành phần lỗi của giải thuật học, nĩ độc lập với tập dữ liệu học) và dùng tính ngẫu nhiên để điều khiển tính tương quan thấp giữa các cây trong rừng. Tiếp cận random forest cho độ chính xác cao khi so sánh với các thuật tốn học cĩ giám sát hiện nay, chịu đựng nhiễu tốt. Như trình bày 41 trong (Breiman, 2001), random forest học nhanh, chịu đựng nhiễu tốt và khơng bị tình trạng học vẹt. Giải thuật random forest sinh ra mơ hình cĩ độ chính xác cao đáp ứng được yêu cầu thực tiễn cho vấn đề phân loại, hồi quy. Rừng ngẫu nhiên (được mơ tả trong hình 2.14) tạo ra một tập hợp các cây quyết định khơng cắt nhánh, mỗi cây được xây dựng trên tập mẫu bootstrap (lấy mẫu ngẫu nhiên cĩ hồn lại), tại mỗi nút phân hoạch tốt nhất được thực hiện từ việc chọn ngẫu nhiên một tập con các thuộc tính. Lỗi tổng quát của rừng phụ thuộc vào độ chính xác của từng cây thành viên trong rừng và sự phụ thuộc lẫn nhau giữa các cây thành viên. Giải thuật rừng ngẫu nhiên cho độ chính xác cao khi so sánh với các thuật tốn học cĩ giám sát hiện nay, chịu đựng nhiều tốt NN Với bài tốn phân lớp: cho một tập dữ liệu huấn luyện D== d x, y ( i)ii==11( i i ) với xi là vector M chiều, yYi  , trong đĩ: Y gọi là lớp, giả sử cĩ C nhãn lớp YCC1,2, ,( 2) . Ý tưởng chính của mơ hình RF là lựa chọn ngẫu nhiên 2 lần (ngẫu nhiện mẫu và ngẫu nhiện thuộc tính) trong suốt quá trình xây dựng cây gồm cĩ 3 pha như sau: Pha 1: Từ dữ liệu ban đầu D, sử dụng kỹ thuật boostrap (lấy mẫu ngẫu nhiên cĩ hồn lại) để tạo ra t tập dữ liệu con S = {푆1, 푆2..., 푆t }. Pha 2: Trên mỗi tập dữ liệu Sj, xây dựng một cây quyết định ℎ푗. Mơ hình hh= t Rừng ngẫu nhiên là mơ hình  i j=1 . Thay vì sử dụng tất cả các biến là biến ứng cử để lựa chọn điểm chia tốt nhất, tại mỗi nút RF chọn ngẫu nhiên một khơng gian tập con M’ thuộc tính từ M thuộc tính ban đầu (M’<<M). Bên cạnh đĩ, cây quyết định trong mơ hình RF là cây quyết định khơng cắt nhánh. Pha 3: RF dự đốn nhãn lớp của phần tử mới đến bằng chiến lược bình chọn số đơng của các cây quyết định. Ưu điểm của RF là xây dựng cây khơng thực hiện việc cắt nhánh từ các tập dữ liệu con khác nhau, do đĩ thu được những cây với lỗi bias thấp. Bên cạnh đĩ, mối tương quan giữa các cây quyết định cũng được giảm xuống nhờ việc xây dựng 42 các khơng gian con thuộc tính một cách ngẫu nhiên. Sự chính xác của RF phụ thuộc vào chất lượng dự đốn của các cây quyết định và mức độ tương quan giữa các cây trong rừng. Trong quá trình xây dựng các cây quyết định, RF phát triển các nút con từ một nút cha dựa trên việc đánh giá chỉ số Gini của một khơng gian con M’ các thuộc tính được chọn ngẫu nhiên từ khơng gian thuộc tính ban đầu. Thuộc tính được chọn để tách nút t là thuộc tính cĩ điểm cắt làm cực tiểu độ hỗn tạp của các tập mẫu sau khi chia. Cơng thức tính chỉ số Gini cho nút t như sau: c Gini( t) = cc( t) 1 −  ( t) (2.27) c=1 trong đĩ c ()t là tần suất hiện của lớp cC Trong nút t Hình 2.14: Mơ hình rừng ngẫu nhiên Gọi s là một giá trị của thuộc tính 푋j. Giả sử tách nút t thành 2 nút con: nút trái 푡L và nút phải 푡R tại s. Tùy thuộc vào 푋j ≤ s hoặc 푋j> s ta cĩ 2 nút con: 푡L = {푋j ∈ 푡, 푋j ≤ 푠} 푣à 푡R = {푋j ∈ 푡, 푋j > 푠} Khi đĩ, tổng độ đo chỉ số Gini của 2 nút 푡L và 푡R sau khi dùng thuộc tính 푋j tách nút t tại s là: Gini( s, t) = p( tLLRR) Gini( t) + p( t) Gini( t ) (2.28) 43 Để đạt được điểm chia tốt, tại mỗi nút RF sẽ tìm tất cả các giá trị phân biệt của tất cả n’ thuộc tính để tìm ra điểm phân tách nút t (điểm s cĩ độ đo Gini (s, t) nhỏ nhất). Thuộc tính chứa điểm phân tách nút t được gọi là thuộc tính tách nút t. Gọi 퐼푆k (푋j), 퐼푆x lần lượt là độ đo sự quan trọng của thuộc tính 푋j trong một cây quyết định Tk (k=1÷m) và trong một rừng ngẫu nhiên. Cơng thức tính 퐼푆x (푋j) và 퐼푆xj như sau: ISk( X j) = Gini( X j, t ) (2.29) tT k 1 k ISk( X j) =  IS k( X j ) (2.30) k k=1 Chuẩn hĩa min - max để chuyển độ đo sự quan trọng thuộc tính về đoạn [0,1], theo cơng thức (2.31): IS X−minm IS j j=1( X j ) VlX (2.31) j maxmmIS− min ( IS ) j==11( Xjj) j X Kết quả dự đốn của mơ hình rừng ngẫu nhiên là kết hợp kết quả của một số lượng lớn những cây quyết định cĩ mối tương quan thấp (do RF lấy ngẫu nhiên mẫu và xây 33 dựng các khơng gian con thuộc tính cũng ngẫu nhiên) nên RF đạt được cả độ lệch thấp và phương sai thấp. Trong thực tế RF đã trở thành một cơng cụ tin cậy cho phân tích dữ liệu chiều cao. Tuy nhiên, tiếp cận cài đặt ban đầu, RF chỉ cho kết quả tốt trên các dữ liệu cĩ số chiều vừa phải và giảm đáng kể hiệu năng khi xử lý dữ liệu cĩ số rất chiều cao cỡ hàng nghìn thuộc tính, nhiều nhiễu, dung lượng mẫu ít (bài tốn phân tích dữ liệu gene là một trường hợp cụ thể). Sự chính xác của RF phụ thuộc vào chất lượng dự đốn của các cây quyết định và mức độ tương quan giữa các cây quyết định. Chính vì vậy, đã cĩ nhiều đề xuất cho việc cải tiến mơ hình Rừng ngẫu nhiên. Dưới đây sẽ trình bày tĩm tắt một số phương pháp cải tiến mơ hình Rừng ngẫu nhiên. 44 2.6 Một số phương pháp phân lớp dữ liệu khác 2.6.1 Thuật tốn phân lớp k-NN Classifier k-Nearest Neighbors dựa trên việc học bằng sự giống nhau. Các mẫu huấn luyện được mơ tả bởi các thuộc tính số n - chiều. Mỗi mẫu đại diện cho một điểm trong một khơng gian n - chiều. Vì vậy tất cả các mẫu huấn luyện được lưu trữ trong khơng gian mẫu n - chiều. Khi cĩ một mẫu chưa biết cho trước thì classifier k-Nearest Neighbors sẽ tìm kiếm trong khơng gian mẫu k mẫu huấn luyện gần mẫu chưa biết đĩ nhất. k mẫu huấn luyện này là k "k-Nearest Neighbors " của mẫu chưa biết. "Độ gần" được định nghĩa dưới dạng khoảng cách Euclidean, tại đĩ khoảng cách Euclidean giữa hai điểm X1 = (푥11, 푥12, ..., 푥1n) và X2 = (푥21, 푥22, ..., 푥2n) là: n 2 dist(,) X1 X 2=−( x 1ii x 2 ) (2.32) i=1 Mẫu chưa biết được phân vào lớp phổ biến nhất trong số k láng giềng gần nhất của nĩ. Khi k = 1 thì mẫu chưa biết được ấn định lớp của mẫu huấn luyện gần nhất với nĩ trong khơng gian mẫu. Classifier k-Nearest Neighbors dựa trên khoảng cách, từ đĩ chúng lưu trữ tất cả các mẫu huấn luyện. Các kỹ thuật đánh chỉ số hiệu quả được dùng khi số lượng các mẫu huấn luyện là rất lớn. Khơng giống như cây quyết định quy nạp và lan truyền ngược, classifier k-Nearest Neighbors ấn định các trọng số bằng nhau cho từng thuộc tính. Điều này cĩ thể là nguyên nhân gây nhập nhằng khi cĩ nhiều thuộc tính khơng thích hợp trong dữ liệu. Classifier k-Nearest Neighbors cũng được dùng để dự đốn, tức là trả lại một dự đốn giá trị thực cho một mẫu chưa biết cho trước. Lúc này, classifier trả lại giá trị trung bình của các nhãn giá trị thực kết hợp với k- láng giềng gần nhất của mẫu chưa biết đĩ 2.7 Đánh giá mơ hình phân lớp dữ liệu Trong thực tế, ta cần áp dụng nhiều thuật tốn Machine learning để chọn ra được mơ hình phù hợp nhất cho bài tốn của mình. Vấn đề đặt ra, làm thế nào để đánh giá và chọn ra các mơ hình. Ngồi thuật tốn học máy, sự thực thi của mơ hình 45 cĩ thể phụ thuộc vào các yếu tố khác như sự phân bố của các lớp, chi phí phân loại sai, kích thước của tập huấn luyện và tập thử nghiệm, độ đo thực thi. Trong bài viết này, ta sẽ đánh giá thực thi: tập trung vào khả năng dự đốn của mơ hình hơn là tốc độ phân loại hay xây dựng mơ hình, khả năng cĩ giãn. • Confusion matrix Bảng 2.2: Bảng biểu diễn ma trận nhầm lẫn Predicted Class Yes No Actual Class Yes a b No c d Đầu tiên, ta hãy làm quen với confusion matrix (ma trận nhầm lẫn). Quan sát confusion matrix, ta cĩ các thơng tin sau: − a:TP (true positive) – mẫu mang nhãn dương được phân lớp đúng vào lớp dương. − b:FN (false negative) – mẫu mang nhãn dương bị phân lớp sai vào lớp âm. − c:FP (false positive) – mẫu mang nhãn âm bị phân lớp sai vào lớp dương. − d:TN (true negative) – mẫu mang nhãn âm được phân lớp đúng vào lớp