Luận văn Thạc sĩ Khoa học máy tính: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:85

Thêm vào BST

Báo xấu

52
lượt xem 4
download

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

Nội dung chính của luận văn được chia làm 3 chương: Chương 1 - Tổng quan về khai phá dữ liệu và phát hiện tri thức; Chương 2 - Một số phương pháp và kỹ thuật phân lớp dữ liệu và 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 toán cơ bản. Mời các bạn tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: 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

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG INTHAVONG SOUKSAKHONE 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 LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên – 2020
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG INTHAVONG SOUKSAKHONE 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 LUẬN VĂN 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 hoàn toà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ự đoá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 Naï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 toá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 TOÁN CƠ BẢN ....................................................47 3.1 Giới thiệu bài toán phân lớp dữ liệu Mushroom ..........................................................47 3.1.1 Giới thiệu về bài toá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 toán Naive Bayes ............................................ 61 3.3.2 Thực hiện phân lớp bằng thuật toán k-Nearest neighbor ................................. 63 3.3.3 Thực hiện phân lớp bằng thuật toá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ự đoán, đánh giá bởi kiểm tra 70% ...................... 70 Bảng 3.5: Hiệu năng của mô hình dự đoá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 toán cho vay vốn của ngân hàng ........................................ 23 Hình 2.5:Thuật toá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 toá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 toá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 toá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ự đoán nấm (mushroom) ..................... 60 Hình 3.19: Cấu hình Weka cho thuật toán Naive Bayes ............................................... 61 Hình 3.20: Kết quả phân lớp Weka cho thuật toán Naive Bayes với số 70% Split ...... 62 Hình 3.21: Kết quả phân lớp Weka cho thuật toán Naive Bayes kiểm tra chéo 10 mặt ................................................................................................................................. 63 Hình 3.22: Cấu hình Weka cho thuật toán k-NN .......................................................... 64 Hình 3.23: Cấu hình Weka cho thuật toán tìm kiếm trong thuật toán k-NN ................ 64 Hình 3.24: Kết quả phân lớp Weka cho thuật toán k-NN với số 70% Split ................. 65 Hình 3.25: Kết quả phân lớp Weka cho thuật toán k-NN kiểm tra chéo 10 mặt .......... 65 Hình 3.26: Cấu hình Weka cho thuật toán SVM .......................................................... 66 Hình 3.27: Kết quả phân lớp Weka cho thuật toán SVM với số 70% Split.................. 67 Hình 3.28: Kết quả phân lớp Weka cho thuật toán SVM kiểm tra chéo 10 mặt .......... 67 Hình 3.29: Cấu hình Weka cho thuật toán J48 ............................................................. 68 Hình 3.30: Kết quả phân lớp Weka cho thuật toán J48 decision với số 70% Split ...... 68 Hình 3.31: Kết quả phân lớp Weka cho thuật toá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 toá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 toá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 toán học và các giải thuật hiệu quả là chìa khoá 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. Ngoà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 toán cơ bản. Phần này giới thiệu bài toá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. Ngoà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 ngoà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 toà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 toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật toá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 Result) Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu dữ liệu được chiết xuất, không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần thiết. Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đó. Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng. Từ quá trình khám phá tri thức trên chúng ta thấy được sự khác biệt giữa khám phá tri thức và khai phá dữ liệu. Trong khi khám phá tri thức là nói đến quá trình tổng thể phát hiện tri thức hữu ích từ dữ liệu. Còn KPDL chỉ là một bước trong quá trình khám phá tri thức, các công việc chủ yếu là xác định được bài toán khai phá, tiến hành lựa chọn phương pháp KPDL phù hợp với dữ liệu có được và tách ra các tri thức cần thiết. 1.1.6 Các bước của quá trình KPDL Các giải thuật KPDL thường được mô tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích được.
9 Hinh 1.2: Quá trình khai phá dữ liêu (KPDL) Quá trình xử lý KPDL bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật KPDL có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng khi thực hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải rất nhiều vướng mắc như: các dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), … Bước tiếp theo là chọn thuật toán KPDL thích hợp và thực hiện việc KPDL để tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó (thường được biểu diễn dưới dạng các luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy, …). Đặc điểm của mẫu phải là mới (ít nhất là đối với hệ thống đó). Độ mới có thể đuợc đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới của mẫu được đánh giá bằng một hàm logic hoặc một hàm đo độ mới, độ bất ngờ của mẫu. Ngoài ra, mẫu còn phải có khả năng sử dụng tiềm tàng. các mẫu này sau khi được xử lý và diễn giải phải dẫn đến những hành động có ích nào đó được đánh giá bằng một hàm lợi ích. mẫu khai thác được phải có giá trị đối với các dữ liệu mới với độ chính xác nào đó.