Đề tài Ứng dụng cây quyết định trong khai phá dữ liệu

i TRƯỜNG …………………. KHOA………………………. ---------- Báo cáo tốt nghiệp Đề tài: PHÂN TÁCH CỤM DANH TỪ CƠ SỞ TRIẾNG ViỆT SỬ DỤNG MÔ HÌNH CRFs ii LỜI CAM ĐOAN Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Học viên Nguyễn Thanh Huyền iii LỜI CẢM ƠN Trong suốt thời gian học tập, hoàn thành luận văn tôi đã được các Thầy, Cô truyền đạt cho các kiến thức cũng như phương pháp nghiên cứu khoa học rất hữu ích và được gia đình, cơ quan, đồng nghiệp và bạn bè quan tâm, động viên rất nhiều. Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban, người Thầy đã tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trình thực hiện luận văn này. Cũng qua đây, tôi xin gửi lời cảm ơn đến ban giám hiệu trường Trung cấp kinh tế Hà Nội, nơi tôi đangcông tác đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình làm luận văn tốt nghiệp. Cuối cùng, tôi xin cảm ơn bố mẹ, anh, chị, chồng, con và các bạn bè, đồng nghiệp đã luôn ủng hộ, động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chế và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn được hoàn thiện hơn. Hà Nội, ngày 12 tháng 06 năm 2011 Nguyễn Thanh Huyền iv MỤC LỤC LỜI CAM ĐOAN ............................................................................................................. i LỜI CẢM ƠN ................................................................................................................. iii MỤC LỤC ........................................................................................................................ iv DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ....................................... vi DANH MỤC CÁC BẢNG ......................................................................................... vii DANH MỤC CÁC HÌNH .........................................................................................viii MỞ ĐẦU............................................................................................................................ 1 Chương 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ LÝ THUYẾT TẬP THÔ .......................................................................................................................... 3 1.1. Giới thiệu về khai phá dữ liệu .............................................................. 3 1.1.1 Khám phá tri thức ...................................................................................... 3 1.1.2. Khai phá dữ liệu........................................................................................ 4 1.2. Ứng dụng của khai phá dữ liệu ............................................................ 5 1.3. Một số phương pháp khai phá dữ liệu thông dụng................................ 6 1.3.1. Phân lớp (Classification) ......................................................................... 6 1.3.2. Phân cụm (Clustering) ............................................................................. 8 1.3.3. Luật kết hợp (Association Rules) .......................................................... 9 1.4. Lý thuyết tập thô .................................................................................. 9 1.4.1. Hệ thông tin ............................................................................................. 10 1.4.2. Bảng quyết định ...................................................................................... 10 1.4.3. Quan hệ không phân biệt được ........................................................... 12 1.4.4. Xấp xỉ tập hợp ......................................................................................... 12 1.5. Kết luận chương 1.............................................................................. 14 Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY DỰNG CÂY QUYẾT ĐỊNH..................................................................................................... 15 2.1. Tổng quan về cây quyết định ............................................................. 15 2.1.1. Định nghĩa................................................................................................ 15 2.1.2. Thiết kế cây quyết định ......................................................................... 16 2.1.3. Phương pháp tổng quát xây dựng cây quyết định............................. 18 2.1.3. Ứng dụng cây quyết định trong khai phá dữ liệu ............................. 19 2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy........................ 20 2.2.1. Tiêu chí chọn thuộc tính phân lớp ....................................................... 20 2.2.2. Thuật toán ID3 ........................................................................................ 21 2.2.3. Ví dụ về thuật toán ID3 ......................................................................... 23 2.3. Thuật toán xây dựng cây quyết định dựa vào độ phụ thuộc của thuộc tính ........................................................................................................... 28 v 2.3.1. Độ phụ thuộc của thuộc tính theo lý thuyết tập thô ......................... 28 2.3.2. Độ phụ thuộc chính xác  theo lý thuyết tập thô .............................. 28 2.3.3. Tiêu chí chọn thuộc tính để phân lớp.................................................. 28 2.3.4. Thuật toán xây dựng cây quyết định ADTDA .................................. 29 2.3.5. Ví dụ.......................................................................................................... 30 2.4. Thuật toán xây dựng cây quyết định dựa vào Entropy và độ phụ thuộc của thuộc tính ........................................................................................... 33 2.4.1. Tiêu chí chọn thuộc tính để phân lớp.................................................. 33 2.4.2. Thuật toán FID3 (Fixed Iterative Dichotomiser 3 [5] ) ................... 34 2.4.3. Ví dụ.......................................................................................................... 35 2.5. Kết luận chương 2.............................................................................. 39 Chương 3 - ỨNG DỤNG KIỂM CHỨNG VÀ ĐÁNH GIÁ.............................. 40 3.1. Giới thiệu bài toán ............................................................................. 40 3.2. Giới thiệu về cơ sở dữ liệu ................................................................. 40 3.3. Cài đặt ứng dụng................................................................................ 41 3.4. Kết quả và đánh giá thuật toán ........................................................... 42 3.4.1. Mô hình cây quyết định tương ứng với tập dữ liệu Bank_data...... 42 3.4.2. Các luật quyết định tương ứng với tập dữ liệu Bank_data ............. 44 3.4.3. Đánh giá thuật toán ................................................................................ 44 3.4.4. Ứng dụng cây quyết định trong khai phá dữ liệu ............................. 45 3.5. Kết luận chương 3.............................................................................. 46 KẾT LUẬN ..................................................................................................................... 47 TÀI LIỆU THAM KHẢO .......................................................................................... 49 vi DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT CÁC KÝ HIỆU: S = (U, A) Hệ thông tin Va Tập các giá trị của thuộc tính a IND(B) Quan hệ tương đương của tập thuộc tính B [ui]p Lớp tương đương chứa đối tượng ui U/B Phân hoạch của U sinh ra bởi quan hệ IND(B) DT=(U,CD) Bảng quyết định )(XB B-Xấp xỉ dưới của X )(XB B-xấp xỉ trên của X )(SC dPO Miền C-khẳng định của d |DT| Tổng số các đối tượng trong DT |U| Lực lượng của tập U [U]d Phân hoạch của U sinh ra bởi quan hệ IND(d) CÁC CHỮ VIẾT TẮT: ADTDA Algorithm for Buiding Decision Tree Based on Dependency of Attributes FID3 Fixed Iterative Dichotomiser 3 ID3 Iterative Dichotomiser 3 IG Information Gain vii DANH MỤC CÁC BẢNG Bảng 1. Hệ thông tin đơn giản......................................................................... 10 Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk}..................... 11 Bảng 3. Dữ liệu huấn luyện .............................................................................. 23 Bảng 4. Bảng các thuộc tính của tập dữ liệu Bank_data................................... 41 Bảng 5. Độ chính xác của các thuật toán ......................................................... 45 viii DANH MỤC CÁC HÌNH Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình ........................... 7 Hình 2. Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình ............. 8 Hình 3. Quá trình phân lớp dữ liệu –Phân lớp dữ liệu mới ................................ 8 Hình 4. Xấp xỉ tập đối tượng trong Bảng 2 bởi các thuộc tính điều kiện Age và LEMS ............................................................................................................... 14 Hình 5. Mô tả chung về cây quyết định............................................................. 15 Hình 6. Ví dụ về Cây quyết định ....................................................................... 16 Hình 7. Mô hình phân lớp các mẫu mới ........................................................... 19 Hình 8. Cây sau khi chọn thuộc tính Humidity (ID3)........................................ 25 Hình 9. Cây sau khi chọn thuộc tính Outlook (ID3).......................................... 26 Hình 10. Cây kết quả (ID3) .............................................................................. 27 Hình 11. Cây sau khi chọn thuộc tính Humidity (ADTDA) ............................... 31 Hình 12. Cây sau khi chọn thuộc tính Outlook (ADTDA) ................................. 32 Hình 13. Cây kết quả (ADTDA)........................................................................ 33 Hình 14. Cây quyết định sau khi chọn thuộc tính Humidity (FID3) .................. 36 Hình 15. Cây quyết định sau khi chọn thuộc tính Windy (FID3)....................... 38 Hình 16. Cây kết quả (FID3) ............................................................................ 39 Hình 17. Dạng cây quyết định ID3 ................................................................... 42 Hình 18. Dạng cây quyết định ADTDA............................................................. 42 Hình 19. Dạng cây quyết định FID3................................................................. 43 Hình 20. Một số luật của cây quyết định ID3 ................................................... 44 Hình 21. Một số luật của cây quyết định ADTDA ............................................. 44 Hình 22. Một số luật của cây quyết định FID3 ................................................. 44 Hình 23. Giao diện ứng dụng ........................................................................... 46 1 MỞ ĐẦU  Lý do chọn đề tài Trong những năm gần đây Công nghệ thông tin phát triển mạnh mẽ và có những tiến bộ vượt bậc. Cùng với sự phát triển của Công nghệ thông tin là sự bùng nổ thông tin. Các thông tin tổ chức theo phương thức sử dụng giấy trong giao dịch đang dần được số hóa, do nhiều tính năng vượt trội mà phương thức này mang lại như: có thể lưu trữ lâu dài, cập nhật, sửa đổi, tìm kiếm một cách nhanh chóng. Đó là lý do khiến cho số lượng thông tin số hóa ngày nay đang tăng dần theo cấp số nhân. Hiện nay, không 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. 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. Việc khai phá tri thức đã có từ lâu nhưng sự bùng nổ của nó thì mới chỉ xảy ra trong những năm gần đây. Các công cụ thu thập dữ liệu tự động và các công nghệ cơ sở dữ liệu được phát triển dẫn đến vấn đề một lượng dữ liệu khổng lồ được lưu trữ trong cơ sở dữ liệu và trong các kho thông tin của các tổ chức, cá nhân....Do đó việc khai phá tri thức từ dữ liệu là một trong những vấn đề đã và đang nhận được nhiều sự quan tâm của các nhà nghiên cứu. Một vấn đề quan trọng và phổ biến trong kỹ thuật khai phá dữ liệu là phân lớp, nó đã và đang được ứng dụng rộng rãi trong thương mại, y tế, công nghiệp... Trong những năm trước đây, phương pháp phân lớp đã được đề xuất, nhưng không có phương pháp tiếp cận phân loại nào là cao hơn và chính xác hơn hẳn những phương pháp khác. Tuy nhiên với mỗi phương pháp có một lợi thế và bất lợi riêng khi sử dụng. Một trong những công cụ khai phá tri thức hiệu quả hiện nay là sử dụng cây quyết định để tìm ra các luật phân lớp. Phân lớp sử dụng lý thuyết tập thô, được đề xuất bởi Zdzislaw Pawlak vào năm 1982, và đã được nghiên cứu rộng rãi trong những năm gần đây. Lý thuyết tập thô cung cấp cho nhiều nhà nghiên cứu và phân tích dữ liệu với nhiều kỹ thuật trong khai phá dữ liệu như là các khái niệm đặc trưng bằng cách sử dụng một số dữ kiện. Nhiều nhà nghiên cứu đã sử dụng lý thuyết tập thô trong các ứng dụng như phân biệt thuộc tính, giảm số chiều, khám phá tri thức, và phân 2 tích dữ liệu thời gian,... Đây là một công cụ toán học mới được áp dụng trong khai phá dữ liệu có thể được dùng để lựa chọn thuộc tính để phân nhánh trong việc xây dựng cấu trúc cây quyết định và có nhiều cách tiếp cận khác nhau để chọn thuộc tính phân nhánh tối ưu, làm cho cây có chiều cao nhỏ nhất. Chính vì vậy, trong luận văn này tôi đã tìm hiểu về các phương pháp xây dựng cây quyết định dựa vào tập thô. Việc ứng dụng cây quyết định để khai phá dữ liệu đã và đang được tiếp tục tìm hiểu, nghiên cứu. Với mong muốn tìm hiểu và nghiên cứu về lĩnh vực này, tôi đã chọn đề tài “Ứng dụng cây quyết định trong khai phá dữ liệu” làm luận văn tốt nghiệp.  Mục tiêu nghiên cứu Mục đích của luận văn là nghiên cứu các vấn đề cơ bản của lý thuyết tập thô, cây quyết định và các thuật toán xây dựng cây quyết định trên hệ thông tin đầy đủ dựa trên tập thô; cài đặt và đánh giá các thuật toán xây dựng cây quyết định đã nghiên cứu; bước đầu áp dụng mô hình cây quyết định đã xây dựng vào trong khai phá dữ liệu (hỗ trợ ra quyết định trong vay vốn).  Bố cục luận văn Luận văn gồm 3 chương chính: Chương 1: Tổng quan về khai phá tri thức và lý thuyết tập thô Trong chương này trình bày tổng quan về khai phá dữ liệu và lý thuyết tập thô. Chương 2: Cây quyết định và các thuật tóan xây dựng cây quyết định. Trong chương này giới thiệu tổng quan về cây quyết đinh, phương pháp tổng quát xây dựng cây quyết định và ba thuật toán xây dựng cây quyết định: ID3, ADTDA, FID3 Chương 3: Thực nghiệm và đánh giá. Phát biểu bài toán, cài đặt ứng dụng và đánh giá. 3 Chương 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ LÝ THUYẾT TẬP THÔ 1.1. Giới thiệu về khai phá dữ liệu 1.1.1 Khám phá tri thức Trong thời đại bùng nổ công nghệ thông tin, các công nghệ lưu trữ dữ liệu ngày càng phát triển nhanh chóng tạo điều kiện cho các đơn vị thu thập dữ liệu nhiều hơn và tốt hơn. Đặc biệt trong lĩnh vực kinh doanh, các doanh nghiệp đã nhận thức được tầm quan trọng cuả việc nắm bắt và xử lí thông tin. Nó hỗ trợ các chủ doanh nghiệp trong việc đưa ra các chiến lược kinh doanh kịp thời mang lại những lợi nhuận to lớn cho doanh nghiệp của mình. Tất cả lí do đó khiến cho các cơ quan, đơn vị và các doanh nghiệp đã tạo ra một lượng dữ liệu khổng lồ cỡ Gigabyte thậm chí là Terabyte cho riêng mình. Các kho dữ liệu ngày càng lớn và tiềm ẩn nhiều thông tin có ích. Sự bùng nổ đó dẫn tới một yêu cầu cấp thiết là phải có những kĩ thuật và công cụ mới để biến kho dữ liệu khổng lồ kia thành những thông tin cô đọng và có ích. Khám phá tri thức từ dữ liệu (Knowledge Discovery from Data - KDD) ra đời như một kết quả tất yếu đáp ứng các nhu cầu đó. Quá trình khám phá tri thức từ dữ liệu thông thường gồm các bước chính sau [2]-[7]: Bước 1: Xác định vấn đề và lựa chọn nguồn dữ liệu (Problem Understanding anh Data Understanding) Trong giai đoạn này các chuyên gia trong lĩnh vực cần phải thảo luận với các chuyên gia tin học, để xác định được chúng ta mong muốn khám phá những gì, thống nhất giải pháp cho quá trình khám phá dữ liệu (muốn có các luật hay muốn phân lớp, phâm cụm dữ liệu…). Đây là một giai đoạn quan trọng vì nếu xác định sai vấn đề thì toàn bộ quá trình phá sản, nó trở nên vô ích. Bước 2: Chuẩn bị dữ liệu (Data preparation) Bao gồm các quá trình sau: - Thu thập dữ liệu (data gathering) 4 - Làm sạch dữ liệu (data cleaning) - Tích hợp dữ liệu ( data integeration) - Chọn dữ liệu (data selection) - Biến đổi dữ liệu (data transformation) Đây cũng là một giai đoạn rất quan trọng vì nếu dữ liệu đầu vào không chính xác thì hiển nhiên sẽ không thể nào có một kết quả chính xác được. Bước 3 : Khai phá dữ liệu (Data Mining) Đây là bước xác định nhiệm vụ khai phá dữ liệu và lựa chọn kỹ thuật khai phá dữ liệu. Kết quả của quá trình này sẽ tìm ra các tri thức, mô hình hay các quy luật tiềm ẩn bên trong dữ liệu. Bước 4: Đánh giá mẫu (Partern Evalution) Đánh giá xem tri thức thu được có chính xác và có giá trị hay không, nếu không có thể quay lại các bước trên. Việc đánh giá này được thực hiện thông qua các chuyên gia trong lĩnh vực và người dùng là chính chứ không phải là các chuyên gia tin học. Bước 5: Biểu diễn tri thức và triển khai (Knowlegde presentation and Deployment) Biểu diễn tri thức phát hiện được dưới dạng tường minh, thân thiện và hữu ích với đa số người dùng và tiến hành đưa tri thức phát hiện được vào các ứng dụng cụ thể. 1.1.2. Khai phá dữ liệu Khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức từ cơ sở dữ liệu. Khai phá dữ liệu bao gồm các giai đoạn sau [7]: Giai đoạn 1: Gom dữ liệu (Gathering) Đây là bước tập hợp các dữ liệu đượ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. Giai đoạn 2: Trích lọc dữ liệu (Selection) 5 Ở 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 đó, 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. Giai đoạn 3: Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing, Pre-processing and Preparation) Giai đoan 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ụ: tuổi = 673. 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