Báo cáo Phân tách cụm danh từ cơ sở tiếng Việt sử dụng mô hình CRFS

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ệch nghiêm trọng. Giai đoạn 4: Chuyển đổi dữ liệu (Transformation) Dữ liệu sẽ được chuyển đổi phù hợp với mục đích khai thác. Giai đoạn 5: Phát hiện và trích mẫu dữ liệu (Pattern Extraction and Discovery) Ở 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 loại, nguyên tắc kết hợp hoặc các mô hình dữ liệu tuần tự,. v.v. Giai đoạn 6: Đánh giá kết quả mẫu (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 ra bởi phần mềm khai phá dữ liệu. 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 chiết xuất ra. 1.2. Ứng dụng của khai phá dữ liệu Hiện nay, kĩ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet, … 6 + Y học và chăm sóc sức khỏe : chẩn đoán bệnh trong y tế dựa trên kết quả xét nghiệm đã giúp cho bảo hiểm y tế Australia phát hiện ra nhiều trường hợp xét nghiệm không hợp lí tiết kiệm được 1 triệu $/năm. + Marketing: IBM Surf – Aid đã áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các trang có liên quan đến thị trường để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động của các Website; Trang Web mua bán qua mạng Amazon cũng tăng doanh thu nhờ áp dụng Khai phá dữ liệu trong việc phân tích sở thích mua bán của khách hàng… + Tài chính và thị trường chứng khoán: Áp dụng vào việc phân tích các thẻ tín dụng tiêu biểu của các khách hàng, phân đoạn tài khoản nhận được, phân tích đầu tư tài chính như chứng khoán, giấy chứng nhận, và các quỹ tình thương, đánh giá tài chính, và phát hiện kẻ gian, .... Dự báo giá của các loại cổ phiếu trong thị trường chứng khoán, ... + Bảo hiểm: Áp dụng vào việc phân tích mức độ rủi ro xảy ra đối với từng loại hàng hoá, dịch vụ hay chiến lược tìm kiếm khách hàng mua bảo hiểm, ... + Quá trình sản xuất: Các ứng dụng giải quyết sự tối ưu của các nguồn tài nguyên như các máy móc, nhân sự, và nguyên vật liệu; thiết kế tối ưu trong quá trình sản xuất, bố trí phân xưởng và thiết kế sản phẩm, chẳng hạn như quá trình tự động dựa vào yêu cầu khách hàng... 1.3. Một số phương pháp khai phá dữ liệu thông dụng Nhiệm vụ chính của khai phá dữ liệu là mô tả và dự đoán. Trong đó mô tả nhằm biểu thị các đặc điểm chung của dữ liệu có trong CSDL, còn dự đoán nhằm thực hiện, suy luận trên dữ liệu hiện có để đưa ra các kết luận của dự đoán đó. Dưới đây giới thiệu 3 phương pháp thông dụng nhất là: phân cụm dữ liệu, phân lớp dữ liệu và luật kết hợp. 1.3.1. Phân lớp (Classification) Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: Bước 1: Xây dựng mô hình Trong bước này, một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc 7 được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị được gọi chung là một mẫu (sample). Trong tập dữ liệu này, mỗi mẫu được giả sử thuộc về một lớp định trước, lớp ở đây là giá trị của một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính quyết định. Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng if-then, cây quyết định, công thức logic, hay mạng nơron. Quá trình này được mô tả như trong hình 1 Hình 1. Quá trình phân lớp dữ liệu – Bước xây dựng mô hình Bước 2: Sử dụng mô hình đã xây dựng để phân lớp dữ liệu Trong bước này việc đầu tiên là phải làm là tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra được ước lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp. Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đưa là tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với thực tế). 8 Hình 2. Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình Hình 3. Quá trình phân lớp dữ liệu –Phân lớp dữ liệu mới 1.3.2. Phân cụm (Clustering) Mục tiêu chính phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát. Trong phương pháp này ta sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân loại thị trường, phân loại khách hàng, nhận dạng mẫu, phân loại trang web,… Ngoài ra 9 phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán khai phá dữ liệu khác. 1.3.3. Luật kết hợp (Association Rules) Luật kết hợp là luật mà trong đó phản ánh mối quan hệ kết hợp chặt chẽ trong một tập các đối tượng trong một CSDL [2]. Mục tiêu của phương pháp này là phát hiện và đưa ra mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Khai phá luật kết hợp được thực hiện qua 2 bước:  Bước 1: Tìm tất cả các tập mục phổ biến, một văn bản phổ biến được xác định qua độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.  Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. 1.4. Lý thuyết tập thô Lý thuyết tập thô (rough set theory) lần đầu tiên được đề xuất bởi Z.Pawlak vào những năm đầu thập niên 1980. Phương pháp này đóng vai trò hêt sức quan trọng trong lĩnh vực trí tuệ nhân tạo và các ngành liên quan đến nhận thức, đặc biệt là trong lĩnh vực học máy, thu nhận tri thức, phân tích quyết định, phát hiện và khám phá tri thức từ cơ sở dữ liệu, các hệ chuyên gia, các hệ hỗ trợ quyết định, lập luận dựa trên quy nạp [1]-[8]. Các lĩnh vực ứng dụng trong tập thô bao gồm: - Chẩn đoán y học (medical diagnosis) - Nghiên cứu dược lý ((pharmacology) - Dự đoán thị trường cổ phiếu và phân tích dữ liệu tài chính - Kinh doanh tiền tệ (banking) - Nghiên cứu thị trường - Các hệ thu nhận và lưu trữ thông tin - Nhận dạng mẫu, gồm nhận dạng tiếng nói và chữ viết tay - Thiết kế hệ điều khiển ( control system design) - Xử lý ảnh (image processing) 10 - Thiết kế logic số(digital logic design) Sau đây chúng ta sẽ nghiên cứu các khái niệm cơ bản của lý thuyết tập thô. Đây là những kiến thức quan trọng cho việc áp dụng tập thô để xây dựng cây quyết định. 1.4.1. Hệ thông tin Trong hầu hết các hệ quản trị cơ sở dữ liệu thông thường thì thông tin thường được biểu diễn dưới dạng các bảng, trong đó mỗi bảng biểu diễn thông tin về một đối tượng, mỗi cột biểu diễn thông tin về một thuộc tính của đối tượng. Từ đầu những năm 80 Pawlak đã định nghĩa một khái niệm mới là hệ thông tin (infomation system) dựa trên khái niệm bảng truyền thống như sau [4]: Định nghĩa 1.1. [1]-[8] Hệ thông tin là một cặp S = (U, A) trong đó U là tập hữu hạn khác rỗng các đối tượng (được gọi là tập vũ trụ các đối tượng) và A là tập hữu hạn khác rỗng các thuộc tính. Với mọi aA ta kí hiệu Va là tập giá trị của thuộc tính a. Nếu xU và aA thì ta kí hiệu x(a) là giá trị thuộc tính a của đối tượng x. Ví dụ 1.1. [8] Bảng dữ liệu dưới đây là một hệ thông tin với 7 đối tượng và 2 thuộc tính. Age LEMS x1 16-30 50 x2 16-30 0 x3 31-45 1-25 x4 31-45 1-25 x5 46-60 26-49 x6 16-30 26-49 x7 46-60 26-49 Bảng 1. Hệ thông tin đơn giản 1.4.2. Bảng quyết định Để có thể biểu diễn một dữ liệu thực tế, trong đó có những thuộc tính quyết đinh, chúng ta xét một trường hợp đặc biệt của hệ thông tin được gọi là bảng quyết định được định nghĩa như sau: 11 Định nghĩa 1.2: Bảng quyết định (hệ quyết định) là một dạng đặc biệt của hệ thông tin, trong đó tập các thuộc tính A bao gồm hai tập con rời nhau là tập thuộc tính điều kiện C và tập các thuộc tính quyết định D. Như vậy bảng quyết định là một hệ thông tin có dạng DT= (U, C D) với C  D =  [1]. Ví dụ 1.2. Bảng 2 dưới đây thể hiện một bảng quyết định, trong đó tập thuộc tính điều kiện như ở Bảng 1 và thuộc tính quyết định {Walk} được thêm vào nhận hai giá trị là Yes và No [8]. Age LEMS Walk x1 16-30 50 Yes x2 16-30 0 No x3 31-45 1-25 No x4 31-45 1-25 Yes x5 46-60 26-49 No x6 16-30 26-49 Yes x7 46-60 26-49 No Bảng 2. Một bảng quyết định với C={Age, LEMS} và D={Walk} Định nghĩa 1.3. Miền khẳng định Cho bảng quyết định DT = {U,CD}. Tập POSC(D) =  )(/ )( DINDUX XC  được gọi là C-miền khẳng định của D. Nói cách khác, uPOSC(D) nếu và chỉ nếu u(C) = v(C) kéo theo u(D) = v(D) với mọi vU [1]. Một thuộc tính c  C được gọi là không cần thiết trong DT nếu POSC(D) = POSC-{c}(D). Ngược lại, c là cần thiết trong DT. Ta nói bảng quyết định DT = (U, C  {d}) là độc lập nếu mọi thuộc tính c  C đều cần thiết trong DT. Định nghĩa 1.4. Xét bảng quyết định DT = (U, C {d}) và hai đối tượng x, y  U. Ta nói x và y mâu thuẫn nhau trong DT nếu x(C) = y(C) nhưng x(d) ≠ y(d) [3]. Đối tượng x được gọi là nhất quán trong DT nếu không tồn tại một đối tượng y khác mâu thuẫn với x. DT được gọi là nhất quán nếu mọi đối tượng trong xU đều là nhất quán. 12 1.4.3. Quan hệ không phân biệt được Một trong những đặc điểm cơ bản của lý thuyết tập thô là dùng để lưu giữ và xử lý các dữ liệu trong đó có sự mập mờ, không phân biệt được. Trong một hệ thông tin theo định nghĩa trên cũng có thể có những đối tượng không phân biệt được. Định nghĩa 6: Cho hệ thông tin S = (U, A). Với mỗi tập thuộc tính B  A đều tạo ra tương ứng một quan hệ tương đương, kí hiệu IND(B) [1]-[8]: IND(B) = {(x,x’)  U2 |  a B, x(a) = x’(a) } IND(B) được gọi là quan hệ B-không phân biệt được. Nếu (x,x’)  IND(B) thì các đối tượng x và x’ là không thể phân biệt được với nhau qua tập thuộc tính B. Với mọi đối tượng x  U, lớp tương đương của x trong quan hệ IND(B) được kí hiệu bởi [x]B là tập tất cả các đối tượng có quan hệ IND(B) với x. Quan hệ B- không phân biệt được phân hoạch tập đối tượng U thành các lớp tương đương, kí hiệu là U/ IND(B) hay U/B, tức là U/B = {[x]P | x  U}. Ví dụ 1.3. [8] Xét hệ thông tin cho trong Bảng 1 Xét thuộc tính B = {LEMS}, ta có phân hoạch của tập U sinh bởi quan hệ tương đương IND(B) là: U/B = {{x1}, {x2}, {x3, x4}, {x5, x6, x7}} Khi đó, ta nói các cặp đối tượng x3, x4 và x5, x6 là không phân biệt qua tập thuộc tính {LEMS} vì chúng thuộc cùng một lớp tương đương định bởi quan hệ IND(B). Nếu ta xét B = {Age, LEMS}, ta có: U/B = {{x1}, {x2}, {x3, x4}, {x5, x7},{ x6}} Khi đó x5 và x6 là phân biệt được qua tập thuộc tính {Age, LEMS} vì chúng không thuộc cùng lớp tương đương định bởi quan hệ IND(B). 1.4.4. Xấp xỉ tập hợp Ta thấy ở bảng 2 khái niệm Walk không thể định nghĩa rõ ràng qua 2 thuộc tính điều kiện Age và LEMS vì có x3, x4 thuộc cùng một lớp tương đương tạo bởi 2 thuộc tính Age và LEMS nhưng lại có giá trị khác nhau tại thuộc tính 13 Walk. Vì vậy, nếu một đối tượng nào đó có (Age,LEMS) = (31-45, 1-25) thì ta vẫn không thể biết chắc chắn giá trị của nó tại thuộc tính Walk là Yes hay No. Vì vậy, ta thấy khái niệm Walk không được mô tả rõ ràng. Tuy nhiên, căn cứ vào tập thuộc tính {Age, LEMS} ta vẫn có thể chỉ ra được chắc chắn một số đối tượng có Walk là Yes, một số đối tượng có Walk là No, còn lại là các đối tượng thuộc tính về biên của hai giá trị Yes và No, cụ thể:  Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập {{16-30, 50}, {16-30, 26-49}} thì có Walk là Yes.  Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} thuộc tập {{16-30, 0}, {46-60, 26-49}} thì có Walk là No.  Nếu đối tượng nào có giá trị tại tập thuộc tính {Age,LEMS} = {31-45, 1- 25} thì có Walk là Yes hoặc No. Chính vì vậy ta có khái niệm xấp xỉ tập hợp như sau: Định nghĩa 1.3. [10] Cho hệ quyết định DT = (U, CD), tập thuộc tính BC, tập đối tượng XU. Chúng ta có thể xấp xỉ tập hợp X bằng cách sử dụng các thuộc tính trong B từ việc xây dựng các tập hợp B-xấp xỉ dưới và B-xấp xỉ trên được định nghĩa như sau: B-xấp xỉ dưới của tập X: BX = {x  U | [x]B  X} B-xấp xỉ trên của tập X: B X = {x  U | [x]B X ≠  Tập hợp BX là tập các đối tượng trong U mà sử dụng các thuộc tính trong B ta có thể biết chắc chắn được chúng là các phần tử của X. Tập hợp BX là các đối tượng trong U mà sử dụng các thuộc tính trong B ta chỉ có nói rằng chúng có thể là các phần tử của X. Tập BNB(X) = B X \BX được gọi là B-biên của tập X, nó chứa các đối tượng mà sử dụng các thuộc tính của B ta không thể xác định được chúng có thuộc tập X hay không. Tập U\ BX được gọi là B-ngoài của tập X, gồm những đối tượng mà sử dụng tập thuộc tính B ta biết chắc chắn chúng không thuộc tập X. Một tập hợp được gọi là thô nếu đường biên của nó là không rỗng, ngược lại ta nói tập này là rõ. Ví dụ 1.4. Xét hệ quyết định cho trong Bảng 2 14 Xét tập đối tượng X = {x U | x(Walk) = Yes} = {x1, x4, x6} và tập thuộc tính B = {Age, LEMS}. Khi đó ta có [8]: U/B ={{x1}, {x2}, {x3, x4}, {x5, x7},{ x6}} BX = {x U | [x]B  X} = {x1, x6} B X = {x  U | [x]B X ≠ } = {u1, u2, u5, u7, u8} 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 1.5. Kết luận chương 1 + Chương này đã giới thiệu tổng quan về khai phá dữ liệu, ứng dụng của khai phá dữ liệu, và giới thiệu một số phương pháp khai phá dữ liệu thông dụng. + Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thống thông tin, quan hệ không phân biệt được, các tập thô, bảng quyết định,… Và đồng thời trình bày các ví dụ cụ thể để minh họa các khái niệm này. 15 Chương 2- CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY DỰNG CÂY QUYẾT ĐỊNH 2.1. Tổng quan về cây quyết định Cây quyết định là công cụ dùng để phân lớp các dữ liệu, nó có cấu trúc cây. Mỗi cây quyết định là một sự tượng trưng cho một sự quyết định của một lớp các dữ kiện nào đó. Mỗi nút trong cây là tên của một lớp hay một phép thử thuộc tính cụ thể nào đó, phép thử này phân chia không gian trạng thái các dữ kiện tại nút đó thành các kết quả có thể đạt được của phép thử. Mỗi tập con được phân chia của phép thử là không gian con của các sự kiện, nó tương ứng với một vấn đề con của sự phân lớp. Các cây quyết định được dùng để hỗ trợ quá trình ra quyết định. 2.1.1. Định nghĩa Cây quyết định là một cây mà mỗi nút của cây là: - Nút lá hay còn gọi là nút trả lời biểu thị cho một lớp các trường hợp mà nhãn của nó là tên của lớp. - Nút không phải là nút lá hay còn gọi là nút trong, nút định phép kiểm tra các thuộc tính, nhãn của nút này là tên của thuộc tính và có một nhánh nối nút này đến các cây con ứng với mỗi kết quả có thể có phép thử. Nhãn của nhánh này là các giá trị của thuộc tính đó. Nút trên cùng gọi là nút gốc. Hình 5. Mô tả chung về cây quyết định Để 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ự đoán giá trị phân lớp của mẫu đó. Nút gốc Các nhánh Nút trong Nút trong Nút lá Nút lá 16 Ví dụ 2.1: Cây quyết định Hình 6. Ví dụ về Cây quyết định 2.1.2. Thiết kế cây quyết định 2.1.2.1. Xử lý dữ liệu Trong thế giới thực, nói chung dữ liệu thô chắc chắn có mức độ nhiễu. Điều này có các nguyên nhân khác nhau như là dữ liệu lỗi, dữ liệu có đại lượng không chính xác, .... Do đó, chúng ta thường tiền xử lý (nghĩa là, “làm sạch”) để cực tiểu hoá hay huỷ bỏ tất cả dữ liệu thô bị nhiễu. Các giai đoạn tiền xử lý này cũng có thể biến đổi dữ liệu thô hiển thị hữu ích hơn, như hệ thống thông tin. Khi nhiều bước tiền xử lý ứng dụng hiệu quả, nó sẽ giúp cải tiến hiệu quả phân lớp. Các công việc cụ thể của tiền xử lý dữ liệu bao gồm những công việc như: - Filtering Attributes: Chọn các thuộc tính phù hợp với mô hình. - Filtering samples: Lọc các mẫu (instances, patterns) dữ liệu cho mô hình. - Transformation: Chuyển đổi dữ liệu cho phù hợp với các mô hình như chuyển đổi dữ liệu từ numeric sang nomial - Discretization (rời rạc hóa dữ liệu): Nếu bạn có dữ liệu liên tục nhưng có một số thuật toán chỉ áp dụng cho các dữ liệu rời rạc (như ID3, ADTDA,…) thì bạn phải thực hiện việc rời rạc hóa dữ liệu. mild Humidity high Normal low Outlook Temp Overcast Rainy hot TRUE FALSE TRUE FALSE Sunn TRUE FALSE 17 2.1.2.2. Tạo cây Cây quyết định được tạo thành bằng cách lần lượt chia (đệ quy) một tập dữ liệu thành các tập dữ liệu con, mỗi tập con được tạo thành chủ yếu từ các phần tử của cùng một lớp. Các nút (không phải là nút lá) là các điểm phân nhánh của cây. Việc phân nhánh tại các nút có thể dựa trên việc kiểm tra một hay nhiều thuộc tính để xác định việc phân chia dữ liệu. 2.1.2.3. Tiêu chuẩn tách Việc lựa chọn chủ yếu trong các thuật toán phân lớp dựa vào cây quyết định là chọn thuộc tính nào để kiểm tra tại mỗi nút của cây. Chúng ta mong muốn chọn thuộc tính sao cho việc phân lớp tập mẫu là tốt nhất. Như vậy chúng ta cần phải có một tiêu chuẩn để đánh giá vấn đề này. Có rất nhiều tiêu chuẩn được đánh giá được sử dụng đó là: + Lượng thông tin thu thêm IG (Information Gain, thuật toán ID3 của John Ross Quilan [9]). + Độ phụ thuộc của thuộc tính quyết định vào thuộc tính điều kiện theo nghĩa lí thuyết tập thô của Zdzisław Pawlak [3]-[10] Các tiêu chuẩn trên sẽ được trình bày trong các thuật toán xây dựng cây quyết định ở các phần dưới đây. 2.1.2.4. Tiêu chuẩn dừng Đây là phần quan trọng trong cấu trúc phân lớp của cây quyết định nhằm chia một nút thành các nút con. Chúng ta tập trung một số tiêu chuẩn dừng chung nhất được sử dụng trong cây quyết định. Tiêu chuẩn dừng truyền thống sử dụng các tập kiểm tra. Chúng ta kiểm tra cây quyết định trong suốt qúa trình xây dựng cây với tập kiểm tra và dừng thuật toán khi xảy ra lỗi. Một phương pháp khác sử dụng giá trị ngưỡng cho trước để dừng chia nút. Chúng ta có thể thay ngưỡng như là giảm nhiễu, số các mẫu trong một nút, tỉ lệ các mẫu trong nút, hay chiều sâu của cây, ... 2.1.2.5. Tỉa cây Trong giai đoạn tạo cây chúng ta có thể giới hạn việc phát triển của cây bằng số bản tin tối thiểu tại mỗi nút, độ sâu tối đa của cây hay giá trị tối thiểu của lượng thông tin thu thêm. Sau giai đoạn tạo cây chúng ta có thể dùng phương pháp “Độ dài mô tả ngắn nhất” (Minimum Description Length) hay giá trị tối thiểu của IG để tỉa cây 18 (chúng ta có thể chọn giá trị tối thiểu của IG trong giai đoạn tạo cây đủ nhỏ để cho cây phát triển tương đối sâu, sau đó lại nâng giá trị này lên để tỉa cây). 2.1.3. Phương pháp tổng quát xây dựng cây quyết định Quá trình xây dựng một cây quyết định cụ thể bắt đầu bằng một nút rỗng bao gồm toàn bộ các đối tượng huấn luyện và làm như sau [3]: 1. Nếu tại nút hiện thời, tất cả các đối tượng huấn luyện đều thuộc vào một lớp nào đó thì cho nút này thành nút lá có tên là nhãn lớp chung của các đối tượng. 2. Trường hợp ngược lại, sử dụng một độ đo, chọn thuộc tính điều kiện phân chia tốt nhất tập mẫu huấn luyện có tại nút. 3. Tạo một lượng nút con của nút hiện thời bằng số các giá trị khác nhau của thuộc tính được chọn. Gán cho mỗi nhánh từ nút cha đến nút con một giá trị của thuộc tính rồi phân chia các các đối tượng huấn luyện vào các nút con tương ứng. 4. Nút con t được gọi là thuần nhất, trở thành lá, nếu tất cả các đối tượng mẫu tại đó đều thuộc vào cùng một lớp. Lặp lại các bước 1-3 đối với mỗi nút chưa thuần nhất. Trong các thuật toán cơ sở xây dựng cây quyết định chỉ chấp nhận các thuộc tính tham gia vào quá trình phân lớp có giá trị rời rạc, bao gồm cả thuộc tính được dùng để dự đoán trong quá trình học cũng như các thuộc tính được sử dụng để kiểm tra tại mỗi nút của cây. Do đó trong trường hợp các thuộc tính có giá trị liên tục có thể dễ dàng loại bỏ bằng cách phân mảnh tập giá trị liên tục của thuộc tính thành một tập rời các khoảng. Việc xây dựng cây quyết định được tiến hành một cách đệ qui, lần lượt từ nút gốc xuống tới tận các nút lá. Tại mỗi nút hiện hành đang xét, nếu kiểm tra thấy thoả điều kiện dừng: thuật toán sẽ tạo nút lá. Nút này được gán một giá trị của nhãn lớp tùy điều kiện dừng được thoả mãn. Ngược lại, thuật toán tiến hành chọn điểm chia tốt nhất theo một tiêu chí cho trước, phân chia dữ liệu hiện hành theo điều kiện chia này. Sau bước phân chia trên, thuật toán sẽ lặp qua tất cả các tập con (đã được chia) và tiến hành gọi đệ qui như bước đầu tiên với dữ liệu chính là các tập con này. 19 Trong bước 3, tiêu chuẩn sử dụng lựa chọn thuộc tính được hiểu là một số đo độ phù hợp, một số đo đánh giá độ thuần nhất, hay một quy tắc phân chia tập mẫu huấn luyện. 2.1.3. Ứng dụng cây quyết định trong khai phá dữ liệu Sau khi đã xây dựng thành công cây quyết định ta sử dụng kết quả từ mô hình cây quyết định đó. Đây là bước sử dụng mô hình để phân lớp dữ liệu hoặc rút ra các tri thức trong phương pháp khai phá dữ liệu bằng phương pháp phân lớp. 2.1.3.1. Xác định lớp của các mẫu mới Trên cơ sở đã biết giá trị của các thuộc tính của các mẫu X1, X2, …, Xn ta xác định thuộc tính quyết định (hay phân lớp) Y của đối tượng đó (có thể dùng kỹ thuật này để nhận dạng mẫu, dự báo, …) Hình 7. Mô hình phân lớp các mẫu mới 2.1.3.2. Rút ra các tri thức hay luật từ cây Với mục đích và nhiệm vụ chính của việc khai phá dữ liệu là phát hiện ra các quy luật, các mô hình từ trong CSDL. Từ mô hình thu được ta rút ra các tri thức hay các quy luật dưới dạng cây hoặc các luật dưới dạng “If … Then…”. Hai mô hình trên là tương đương, chúng có thể được chuyển đổi qua lại giữa các mô hình đó với nhau. (Sunny, True, Cool, High) Cây quyết định Dữ liệu huấn luyện Dữ liệu cụ thể Kết quả ? 20 Ví dụ 2.2: Một trong các luật rút ra từ cây trong ví dụ 2.1 là +Luật 1: IF(Humidity: high) AND (Outlook: rainy) THEM (=> Quyết định: False) +Luật 2: IF(Humidity: high) AND (Outlook: sunny) THEM (=> Quyết định: False) +Luật 3: IF(Humidity: high) AND (Outlook: Overcast) THEN (=> Quyết định: True) … Từ đây ta sử dụng các luật này để hỗ trợ quá trình ra các quyết định, dự đoán, … 2.2. Thuật toán xây dựng cây quyết định dựa vào Entropy 2.2.1. Tiêu chí chọn thuộc tính phân lớp Tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng được xem là một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tưởng chính trong việc đưa ra các tiêu chí trên là làm sao cho các tập con được phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt. Thuật toán dùng độ đo lượng thông tin thu thêm (information IG - IG) để xác định điểm chia [9]. Độ đo này dựa trên cơ sở lý thuyết thông tin của nhà toán học Claude Shannon, độ đo này được xác như sau: Xét bảng quyết định DT = (U, C  {d} ), số giá trị (nhãn lớp) có thể của d là k. Khi đó Entropy của tập các đối tượng trong DT được định nghĩa bởi: i k i i ppUEntropy 2 1 log)(    trong đó pi là tỉ lệ các đối tượng trong DT mang nhãn lớp i. Lượng thông tin thu thêm (Information Gain - IG) là lượng Entropy còn lại khi tập các đối tượng trong DT được phân hoạch theo một thuộc tính điều kiện c nào đó. IG xác định theo công thức sau: )( || ||)(),( v Vv v UEntropy U UUEntropycUIG c    21 trong đó Vc là tập các giá trị của thuộc tính c, Uv là tập các đối tượng trong DT có giá trị thuộc tính c bằng v. IG(U, c) được John Ross Quinlan [9] sử dụng làm độ đo lựa chọn thuộc tính phân chia dữ liệu tại mỗi nút trong thuật toán xây dựng cây quyết định ID3. Thuộc tính được chọn là thuộc tính cho lượng thông tin thu thêm lớn nhất. 2.2.2. Thuật toán ID3 Thuật toán ID3 – Iterative Dichotomiser 3 [9] là thuật toán dùng để xây dựng cây quyết định được John Ross Quinlan trình bày. Ý tưởng chính của thuật toán ID3 là để xây dựng cây quyết định bằng cách ứng dụng từ trên xuống (Top- Down), bắt đầu từ một tập các đối tượng và các thuộc tính của nó. Tại mỗi nút của cây một thuộc tính được kiểm tra, kết quả của phép kiểm tra này được sử dụng để phân chia tập đối tượng theo kết quả kiểm tra trên. Quá trình này được thực hiện một cách đệ quy cho tới khi tập đối tượng trong cây con được sinh ra thuần nhất theo một tiêu chí phân lớp nào đó, hay các đối tượng đó thuộc cùng một dạng giống nhau nào đó. Các lớp hay các dạng này được gọi là nhãn của nút lá của cây, còn tại mỗi nút không phải là nút lá thì nhãn của nó là tên thuộc tính được chọn trong số các thuộc tính được dùng để kiểm tra có giá trị IG lớn nhất. Đại lượng IG được tính thông qua hàm Entropy. Như vậy, IG là đại lượng được dùng để đưa ra độ ưu tiên cho thuộc tính nào được chọn trong quá trình xây dựng cây quyết định. Giả mã của thuật toán ID3 như sau: Dữ liệu vào: Bảng quyết định DT = (U, C  {d}) Dữ liệu ra: Mô hình cây quyết định Function Create_tree (U, C, {d}) Begin If tất cả các mẫu thuộc cùng nhãn lớp di then return một nút lá được gán nhãn di else if C = null then return nút lá có nhãn dj là lớp phổ biến nhất trong DT else begin bestAttribute:= getBestAttribute(U, C); // Chọn thuộc tính tốt nhất để chia 22 C := C- {bestAttribute}; //xóa bestAttribute khỏi tập thuộc tính Với mỗi giá trị v in bestAttribute begin Uv := [U]v ; //Uv là phân hoạch của U theo thuộc tính //bestAttribute có giá trị là v ChildNode:=Create_tree(UV, C, {d}); //Tạo 1 nút con Gắn nút ChildNode vào nhánh v; end end End Giả mã của hàm getBestAttribute như sau: Dữ liệu vào: Bảng quyết định DT = (U, C{d}) Dữ liệu ra: Thuộc tính điều kiện tốt nhất Function getBestAttribute (U, C); Begin maxIG := 0; Với mỗi c in C begin tg : = IG(U, c); // Tính lượng thông tin thu thêm IG(U,c) If (tg > max IG) then begin maxIG := tg; kq := c; end end return kq; //Hàm trả về thuộc tính có lượng thông tin thu thêm IG là lớn nhất End 23 2.2.3. Ví dụ về thuật toán ID3 Xét bảng quyết định DT = {U, C  {d}} sau đây: Outlook Windy Temp Humidity d 1 overcast true cool high True 2 sunny false mild high false 3 sunny false hot high false 4 overcast false hot normal false 5 sunny true hot low True 6 rainy false mild high false 7 rainy false hot high false 8 rainy false hot normal false 9 overcast true hot low True 10 rainy false mild normal True 11 rainy true hot normal false 12 rainy false hot high false Bảng 3. Dữ liệu huấn luyện Giải thích cơ sở dữ liệu trong bảng 5: Mỗi một mẫu biểu diễn cho tình trạng thời tiết gồm các thuộc tính Outlook (quang cảnh), Temp (nhiệt độ), Humidity (độ ẩm) và Windy (gió); và đều có một thuộc tính quyết định d (chơi Tennis). Thuộc tính quyết định chỉ có hai giá trị True, False (chơi, không chơi tennis). Mỗi thuộc tính đều có một tập các giá trị hữu hạn: Thuộc tính Outlook có ba giá trị: Overcast (âm u) , Rain (mưa), Sunny (nắng); Temp có ba giá trị: Hot (nóng), Cool (mát) , Mild (ấm áp); Humidity có hai giá trị: High (cao), Normal (TB) và Windy có hai giá trị: True (có gió), False (không có gió). Các giá trị này chính là ký hiệu (symbol) dùng để biểu diễn bài toán. Thuật toán xây dựng cây quyết định như sau.  Đầu tiên nút lá được khởi tạo gồm các mẫu từ 1 đến 12 Để tìm điểm chia tốt nhất, phải tính toán chỉ số IG của tất cả các thuộc tính trên. Đầu tiên sẽ tính Entropy cho toàn bộ tập huấn luyện U gồm: bốn bộ 24 {1, 5, 9, 10} có giá trị thuộc tính nhãn là “TRUE” và tám bộ {2, 3, 4, 6, 7, 8, 11, 12} có thuộc tính nhãn là “FALSE”, do đó: Tính IG cho từng thuộc tính: - Thuộc tính “Outlook”. Thuộc tính này có ba giá trị là “Overcast”, “Sunny” và “Rainy”. Nhìn vào bảng dữ liệu ta thấy:  Với giá trị “Overcast” có ba bộ {1, 9} có giá trị thuộc tính nhãn là “TRUE” và có một bộ {4} có nhãn lớp là “FALSE”.  Tương tự giá trị “Sunny” có một bộ {5} có nhãn lớp là “TRUE” và có hai bộ {2, 3} có nhãn lớp là “FALSE”;  Với giá trị “Rainy” có một bộ {10} có nhãn lớp “TRUE” và năm bộ {6, 7, 8, 11, 12} có nhãn lớp “FALSE”. Theo công thức trên, độ đo lượng thông tin thu thêm của thuộc tính “Outlook” xét trên U là: Theo cách tính tương tự như trên, ta tính được: - IG(U,Windy)= )]log 8 7log 8 1( 12 8)log 4 1log 4 3( 12 4[918.0 8 7 28 1 24 1 24 3 2  = 0.285 - IG(U, Temp)= 148.0)]log 8 6log 8 2( 12 8)log 3 2log 3 1( 12 3[918.0 8 6 28 2 23 2 23 1 2  - IG(U, Humidity)= 323.0)]log 4 3log 4 1( 12 4)log 6 5log 6 1( 12 6[918.0 4 3 24 1 26 5 26 1 2  Như vậy, thuộc tính “Humidity” là thuộc tính có chỉ số IG lớn nhất nên sẽ được chọn là thuộc tính phân chia. Vì thế thuộc tính “Humidity” được chọn làm nhãn cho nút gốc, ba nhánh được tạo ra lần lượt với tên là: “high”, “Normal”, “low”. 0.918log 12 8log 12 4)( 12 8 212 4 2 UEntropy    Outlook )( || ||)()Outlook,( Vv v v UEntropy U UUEntropyUIG 134.0)]log 6 5log 6 1( 12 6)log 3 2log 3 1( 12 3)log 3 1log 3 2( 12 3[918.0 6 5 26 1 23 2 23 1 23 1 23 2 2  25 Hơn nữa nhánh “low” có các mẫu {5, 9} cùng thuộc một lớp “TRUE ” nên nút lá được tạo ra với nhãn là “TRUE ”. Kết quả phân chia sẽ là cây quyết định như sau: Hình 8. Cây sau khi chọn thuộc tính Humidity (ID3)  Bước tiếp theo gọi thuật toán đệ quy: ID3(U1, C-{Humidity}, {d}) Tương tự để tìm điểm chia tốt nhất tại thuật toán này, phải tính toán chỉ số IG của các thuộc tính “Outlook”, “Windy”, “Temp”. - Đầu tiên ta cũng tính Entropy cho toàn bộ tập huấn luyện trong U1 gồm một bộ {1} có thuộc tính nhãn là “TRUE ” và năm bộ {2, 3, 6, 7, 12} có thuộc tính nhãn là “FALSE”: - Tiếp theo tính IG cho thuộc tính “Outlook”, thuộc tính này có ba giá trị là “Overcast”, “Sunny” và “Rainy”. Nhìn vào bảng dữ liệu:  Với giá trị “Overcast” chỉ có một bộ {1} có giá trị thuộc tính nhãn là “TRUE ”.  Tương tự giá trị “Sunny” chỉ có hai bộ {2, 3} đều có nhãn lớp là “FALSE”;  Với giá trị “Rainy” chỉ có ba bộ {6, 7, 12} đều có nhãn lớp “FALSE”. Do đó, độ đo lượng thông tin thu thêm của thuộc tính “Outlook” xét trên U1 là: IG(U1, Outlook) =0.65 - )]log3 3( 6 3)log 2 2( 6 2)log 1 1( 6 1[ 3 3 22 2 21 1 2  = 0.65 - Tính tương tự ta cũng có: Humidity {1, 2, …., 12} ID3(U1, C-{humidity}, {d}) {1, 2, 3, 6, 7, 12} ID3(U2, C-{humidity}, {d}) {4, 8, 10, 11} high Normal low TRUE {5, 9 } 65.0log 6 5log 6 1)( 6 5 26 1 21 UEntropy 26 IG(U1, Windy) = 0.65 - )]log5 5( 6 5)log 1 1( 6 1[ 5 5 21 1 2  = 0.65 IG(U1, Temp) = 0.65 - )]log5 5( 6 5)log 1 1( 6 1[ 5 5 21 1 2  = 0.65 Ta thấy chỉ số IG của ba thuộc tính “Outlook”, “Windy”, “Temp” là như nhau, ta có thể chọn bất kỳ thuộc tính nào để phân chia. Giả sử ta chọn thuộc tính “Outlook” để phân chia. Do đó, thuộc tính “Outlook” làm nhãn cho nút bên trái nối với nhánh “high”. Thuộc tính này có ba giá trị “Overcast”, “Sunny” và “Rainy” nên ta tiếp tục tạo thành ba nhánh mới là “Overcast”, “Sunny” và “Rainy”:  Với nhánh “Overcast” gồm một mẫu {1} và có giá trị quyết định là “TRUE ” nên ta tạo nút lá là “TRUE ”.  Với nhánh “Sunny” gồm hai mẫu {2, 3} và có cùng giá trị quyết định là “FALSE” nên tạo nút lá là “FALSE”.  Với nhánh “Rainy” có ba mẫu {6, 7, 12} và đều có giá trị quyết định là “FALSE” nên ta tạo nút lá là “FALSE”. Sau khi thực hiện xong thuật toán đệ quy: ID3(U1, C-{Humidity}, {d}), ta có cây như sau: Hình 9. Cây sau khi chọn thuộc tính Outlook (ID3)  Bước tiếp theo gọi thuật toán đệ quy: ID3(U2, C-{ Humidity}, {d}) Tính một cách tương tự như trên ta có: Entropy (U2) = 811.0log4 3log 4 1 4 3 24 1 2  Overcast Rainy Humidity {1, 2,…, 12} high Normal low Outlook {1, 2, 3, 6, 7, 12} ID3(U2, C-{humidity}, {d}) {4, 8, 10 , 11} TRUE {5, 9 } FALSE {6, 7, 12 } TRUE {1 } FALSE {2, 3 } Sunny 27  IG(U2, Outlook) = 0.811 - )]log 3 2log 3 1( 4 3)log 1 1( 4 1[ 3 2 23 1 21 1 2  = 0.811-0.689 = 0.123  IG(U2, Windy) = 0.811 - )]log 1 1(4/1)log 3 2log 3 1( 4 3[ 1 1 23 2 23 1 2  = 0.811-0.689 = 0.123  IG(U2, Temp) = 0.811 - )]log 1 1( 3 1)log 3 3( 4 3[ 1 1 23 3 2  = 0.811-0 = 0.811 Ta thấy chỉ số IG của “Temp” là lớn nhất, nên nó được chọn để phân chia. Do đó, thuộc tính “Temp” làm nhãn cho nút bên phải nối với nhánh “Normal”. Trong U2, thuộc tính này có hai giá trị “hot” và “mild” nên ta tiếp tục tạo thành hai nhánh mới là “hot” và “mild”:  Với nhánh “hot” gồm ba mẫu {4, 8, 11} và đều có giá trị quyết định là “FALSE” nên ta tạo nút lá là “FALSE”.  Với nhánh “mild” gồm một mẫu {10} và có giá trị quyết định là “TRUE ” nên tạo nút lá là “TRUE ”. Cây cuối cùng như sau: Hình 10. Cây kết quả (ID3) mild Humidity {1, 2,…, 12} high Normal low Outlook {1, 2, 3, 6, 7, 12} Temp {4, 8, 10 , 11} Overcast Rainy hot TRUE {5, 9 } FALSE {6, 7, 12 } TRUE {1 } FALSE {2, 3 } Sunny TRUE {10 } FALSE {4, 8, 11 } 28 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 2.3.1. Độ phụ thuộc của thuộc tính theo lý thuyết tập thô Xét bảng quyết định DT = (U, C  {D}). Ta nói D phụ thuộc C với độ phụ thuộc k (0 k  1) [10]: k = γ(C,D) = || |)(| U DCPOS Dễ dàng thấy rằng: γ(C,D) =   )(/ || || DINDUX U XC 0  (C, D)  1 Độ phụ thuộc (C, D) có các tính chất sau: - Nếu (C, D) = 1 thì D phụ thuộc hoàn toàn vào C - Nếu 0 < (C, D) < 1 thì d phụ thuộc một phần vào B - Nếu (d, B) = 0 thì không có đối tượng nào của U có thể được phân lớp đúng (như d) dựa vào tập thuộc tính B. 2.3.2. Độ phụ thuộc chính xác  theo lý thuyết tập thô Xét bảng quyết định DT = (U, C  {D}) và tập con thuộc tính điều kiện B  C. Giả sử U/D = {Y1, Y2, …, Ym} và U/B = {X1, X2, …, Xn}. Đặt       || |x| |x||x ),( U Y DB B B B        (B, D) gọi là độ phụ thuộc chính xác  dùng để đo tỉ lệ các đối tượng được phân lớp với mức độ chính xác , trong đó giá trị  (0.5 ≤  ≤ 1) dùng để xác định tỉ lệ các phân lớp đúng [10]. 2.3.3. Tiêu chí chọn thuộc tính để phân lớp Theo cách tiếp cận tập thô, độ phụ thuộc (c, d) được sử dụng làm tiêu chuẩn lựa chọn thuộc tính kiểm tra tại mỗi nút trong quá trình phát triển cây quyết định: thuộc tính được chọn là thuộc tính c cho giá trị (c, d) lớn nhất trong số các thuộc tính còn lại tại mỗi bước [10]. Nếu tất cả độ phụ thuộc (c, d) của các thuộc tính bằng không thì thuộc tính được chọn là thuộc có độ phụ thuộc chính xác  lớn nhất. 29 2.3.4. Thuật toán xây dựng cây quyết định ADTDA Thuật toán ADTDA - Algorithm for Buiding Decision Tree Based on Dependency of Attributes [10] là thuật toán dùng để xây dựng cây quyết định được Longjun Huang, Minghe Huang, Bin Guo, and Zhiming Zhang trình bày. Ý tưởng chính của thuật toán ADTDA là để xây dựng cây quyết định bằng cách ứng dụng từ trên xuống chiến lược tham lam thông qua các tập đã cho để kiểm tra từng thuộc tính ở mọi nút của cây. Để chọn thuộc tính "tốt nhất" (để có cây tối ưu – có độ sâu nhỏ nhất), người ta phải tính độ phụ thuộc của thuộc tính quyết định vào thuộc tính điều kiện. Thuộc tính được chọn phải có độ phụ thuộc lớn nhất. Giả mã của thuật toán ADTDA như sau: Dữ liệu vào: Bảng quyết định DT = (U, C  {d}) Dữ liệu ra: Mô hình cây quyết định Function Create_tree (U, C, {d}) Begin If tất cả các mẫu thuộc cùng nhãn lớp di then return một nút lá được gán nhãn di else if C = null then return nút lá có nhãn dj là lớp phổ biến nhất trong DT else begin bestAttribute:= getBestAttribute(U, C); // Chọn thuộc tính tốt nhất để chia Lấy thuộc tính bestAttribute làm gốc; C := C- {bestAttribute}; //xóa bestAttribute khỏi tập thuộc tính Với mỗi giá trị v in bestAttribute begin Uv := [U]v ; //Uv là phân hoạch của DT theo thuộc tính //bestAttribute có giá trị là v ChildNode:=Create_tree(Uv, U, {d}); //Tạo 1 nút con Gắn nút ChildNode vào nhánh v; end 30 end End Thuật toán ADTDA giống thuật toán ID3, nhưng khác nhau ở hàm getBestAttribute. Giả mã của hàm getBestAttribute như sau: Dữ liệu vào: Bảng quyết định DT = (U, C{d}) Dữ liệu ra: Thuộc tính điều kiện tốt nhất Function getBestAttribute (U, C); Begin maxDependency := 0; Với mỗi c in C begin k : = DependencyGama(U, c); // Tính độ phụ thuộc của thuộc tính γ(c,d) If (k > maxDependency) then begin maxDependency := k; kq := c; end end return kq; //Hàm trả về thuộc tính có độ phụ thuộc của thuộc tính γ(c,d) lớn nhất End 2.3.5. Ví dụ Xét bảng quyết định cho trong Bảng 5  Để xây dựng cây ta tính độ phụ thuộc của tất cả các thuộc tính điều kiện vào thuộc tính quyết định d. - Thuộc tính quyết định d có 4 mẫu {1, 5, 9, 10} có giá trị “TRUE ” và 6 mẫu {2, 3, 4, 6, 7, 8, 11, 12} có giá trị “FALSE” , nên ta có: [U]d = {{1, 5, 9 ,10}, {2, 3, 4, 6, 7, 8, 11, 12}} - Thuộc tính “Outlook” có ba giá trị “Overcast” gồm 3 mẫu {1, 4, 9}, “sunny” gồm 3 mẫu {2, 3, 5} và “rainy” gồm sáu mẫu {6, 7, 8, 10, 11, 12} nên : [U]Outlook= {{1, 4, 9}, {2, 3, 5}, {6, 7, 8, 11, 11, 12}} 31 Do đó: 0 12 0 || |{}| || |)(| ),(  UU dpos dOutlook Outlook Tương tự, ta có:  [U]Windy = {{1, 5, 9, 11},{2, 3, 4, 6, 7, 8, 10, 12}} .0 12 0 || |{}| || |)(| )dWindy,( Windy  UU dpos   [U]Temp={{1}, {2, 6, 10}, {3, 4, 5, 7, 8, 9, 11, 12} . 12 1 || |}1{| || |)(| ),(  UU dpos dTemp Temp  [U]Humidity = {{1, 2, 3, 6, 7, 12}, {4, 8, 10, 11}, {5, 9}} . 12 2 || |}9,5{| || |)(| ),Humidity( Humidity  UU dpos d Ta thấy ),Humidity( d có giá trị lớn nhất nên ta chọn thuộc tính “Humidity” làm thuộc tính phân chia. Như vậy nút gốc có nhãn là “Humidity” và có 3 nhánh được tạo ra lần lượt với tên là: “high”, “Normal”, “low”. Hơn nữa nhánh “low” có các mẫu {5, 9} cùng thuộc một lớp “TRUE ” nên nút lá được tạo ra với nhãn là “TRUE ”. Kết quả phân chia sẽ là cây quyết định như sau: Hình 11. Cây sau khi chọn thuộc tính Humidity (ADTDA)  Bước tiếp theo gọi thuật toán đệ quy: ADTDA (U1, C-{Humidity}, {d}) Ta có: [U1]d = {{1}, {2, 3, 6, 7, 12}}  [U1]Outlook= {{1}, {2, 3}, {6, 7, 12}} Do đó, 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dposdOutlook Outlook  [U1]windy = {{1}, {2, 3, 6, 7, 12} Humidity U={1, 2, …., 12} ADTDA(U1, C-{humidity}, {d}) U1={1, 2, 3, 6, 7, 12} ADTDA(U2, C-{humidity}, {d}) U2={4, 8, 10, 11} high Normal low TRUE {5, 9 } 32 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dwindy windy  [U1]Temp={{1}, {2, 6}, {3, 7, 12}} 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dTemp Temp Ta thấy độ phụ thuộc của ba thuộc tính “Outlook”, “Windy”, “Temp” vào thuộc tính quyết định d là như nhau, nên ta có thể chọn bất kỳ thuộc tính nào để phân chia. Tương tự như ở thuật toán ID3, ta có cây như sau: Hình 12. Cây sau khi chọn thuộc tính Outlook (ADTDA)  Bước tiếp theo gọi thuật toán đệ quy: ADTDA(U2, C-{Humidity}, {d}) Một cách tương tự như trên ta có: [U2]d= {{10}, {4, 8, 11}}  [U2]Outlook = {{4}, {8, 10, 11}} Do đó, 4 1 || |}4{| || |)(| ),( 22  UU dposdOutlook Outlook  [U2]windy = {{4, 8, 10}, {11} 4 1 || |}11{| || |)(| ),( 22  UU dpos dwindy windy  [U2]Temp={{4, 8, 11}, {10}} high Normal low outlook U1={1, 2, 3, 6, 7, 12} ADTDA(U2, C-{humidity}, {d}) U2={4, 8, 10 , 11} Overcast Rainy TRUE {5, 9 } FALSE {6, 7, 12 } TRUE {1 } FALSE {2, 3 } Sunny Humidity U={1, 2, …., 12} 33 1 4 4 || |}11,10,8,4{| || |)(| ),( 22  UU dpos dTemp Temp Ta thấy ),( dTemp là lớn nhất, nên thuộc tính “temp” được chọn để phân chia. Do đó, thuộc tính “Temp” làm nhãn cho nút bên phải nối với nhánh “Normal”. Tương tự như trong thuật toán ID3, cây cuối cùng như sau: Hình 13. Cây kết quả (ADTDA) 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 2.4.1. Tiêu chí chọn thuộc tính để phân lớp Xét bảng quyết định DT = (U, C  {d}). Lượng thông tin thu thêm ổn định IGfix - Fixed Information Gain [5] là tiêu chuẩn mới cho chọn thuộc tính thuộc tính điều kiện c nào đó để phân chia. IGfix được xác định theo công thức sau: || ),(*),(),( c cUIGcdcUIG fix  Trong đó: + |c| là số các giá trị khác nhau của thuộc tính điều kiện c + (c, d) là độ phụ thuộc c vào d + IG(U, c) là lượng thông tin thu thêm high Normal low Outlook {1, 2, 3, 6, 7, 12} Temp {4, 8, 10 , 11} Overcast Rainy mild hot TRUE {5, 9 } FALSE {6, 7, 12 TRUE {1 } FALSE {2, 3 } Sunny Humidity {1, 2,…, 12} TRUE {10 } FALSE {14, 8, 11} 34 Lượng thông tin thu thêm ổn định của thuộc tính được sử dụng như một tiêu chuẩn cho việc chọn thuộc tính kiểm tra tại mỗi nút trong cây quyết định. Thuộc tính điều kiện với giá trị lượng thông tin thu thêm ổn định lớn nhất được chọn từ tập rút gọn thuộc tính và được sử dụng làm nút gốc của cây. 2.4.2. Thuật toán FID3 (Fixed Iterative Dichotomiser 3 [5] ) Dữ liệu vào: Bảng quyết định DT = (U, C  {d}) Dữ liệu ra: Mô hình cây quyết định Function Create_tree (U, C, {d}) Begin If tất cả các mẫu thuộc cùng nhãn lớp di then return một nút lá được gán nhãn di else if C = null then return nút lá có nhãn dj là lớp phổ biến nhất trong DT else begin bestAttribute:= getBestAttribute(U, C); // Chọn thuộc tính tốt nhất để chia Lấy thuộc tính bestAttribute làm gốc; C := C- {bestAttribute}; //xóa bestAttribute khỏi tập thuộc tính Với mỗi giá trị v in bestAttribute begin Uv := [U]v ; //Uv là phân hoạch của DT theo thuộc tính //bestAttribute có giá trị là v ChildNode:=Create_tree(Uv, C, {d}); //Tạo 1 nút con Gắn nút ChildNode vào nhánh v; end end End Thuật toán FID3 giống thuật toán ID3, nhưng khác nhau ở hàm getBestAttribute. Giả mã của hàm getBestAttribute như sau [5]: 35 Dữ liệu vào: Bảng quyết định DT = (U, C{d}) Dữ liệu ra: Thuộc tính điều kiện tốt nhất Function getBestAttribute (U, C); Begin C’:= C ; Với mỗi c in C begin k := DependencyGama(U, c); // Tính độ phụ thuộc của thuộc tính γ(c,d) If (k =0) then C’:= C’ - {c}; end Với mỗi c in C’ begin tg := Igfix(U,c); //Tính lượng thông tin thu thêm ổn định If (tg>maxIGfix) then begin maxIGfix:= tg; kq := c; end end return kq; //Hàm trả về thuộc tính có lượng thông tin thu thêm IGfix(U,c) lớn nhất End 2.4.3. Ví dụ Xét bảng quyết định DT= (U, C  {d}} cho trong Bảng 5 Trong thuật toán ADTDA ở trên, ta đã tính được: γ(Outlook,d) = 0 γ(Windy,d) = 0 γ(Temp,d) = 12 1 . 12 2),Humidity( d 36 Nên thuộc tính mới C’ = {Temp, Humidity}. Ta tính IGfix(U,Temp) và IGfix(U, Humidity) : Trong thuật toán ID3 ở trên ta có: IG(U, Temp)= 0.148 IG(U, Humidity)= 0.323 Do đó: IGfix(U,Temp) = 064.03 148.0* 12 1 || ),( *),(  Temp TempUIG dTemp IGfix(U,Humidity) = || ),(*),( Temp HumidityUIGdHumidity = 134.0 3 323.0* 12 2  Ta thấy IGfix(U,Humidity) có giá trị lớn nhất nên ta chọn thuộc tính “Humidity” làm thuộc tính phân chia. Tương tự như thuật toán ID3, ta có cây như sau: Hình 14. Cây quyết định sau khi chọn thuộc tính Humidity (FID3)  Bước tiếp theo gọi thuật toán đệ quy: FID3(U1, C-{Humidity}, {d})  Theo thuật toán ADTDA ta có: [U1]d = {{1}, {2, 3, 6, 7, 12}  [U1]Outlook= {{1}, {2, 3}, {6, 7, 12}} Do đó, 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dposdOutlook Outlook  [U1]windy = {{1}, {2, 3, 6, 7, 12} TRUE U={1, 2, …., 12} FID3(U1, C-{humidity}, {d}) U1={1, 2, 3, 6, 7, 12} FID3(U2, C-{humidity}, {d}) U2={4, 8, 10, 11} high Normal low TRUE {5, 9 } 37 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dwindy windy  [U1]Temp={{1}, {2, 6}, {3, 7, 12}} 1 6 6 || |}12,7,6,3,2,1{| || |)(| ),( 11  UU dpos dTemp Temp  Theo thuật toán ID3 ta có: IG(U1, Windy) = 0.65 IG(U1, Outlook) = 0.65 IG(U1, Temp) = 0.65 Vậy:  IGfix(U1, Windy)= 57.02 65.0*1 || ),( *),( 1  Windy WindyUIGdWindy  IGfix(U1, Outlook)= 465.03 65.0*1 || ),( *),( 1  Outlook OutlookUIGdOutlook  IGfix(U1, Temp)= 465.03 65.0*1 || ),( *),( 1  Temp TempUIGdTemp Ta thấy IGfix(U1, Windy) có giá trị lớn nhất nên thuộc tính “Windy” được chọn làm thuộc tính phân chia. Do đó, thuộc tính “Windy” làm nhãn cho nút bên trái nối với nhánh “high”. Thuộc tính này có hai giá trị “true” và “false” nên ta tiếp tục tạo thành hai nhánh mới là “true” và “false”:  Với nhánh “true” gồm một mẫu {1} và có giá trị quyết định là “Y” nên ta tạo nút lá là “Y”.  Với nhánh “false” gồm năm mẫu {2, 3, 6, 7, 12} và có cùng giá trị quyết định là “N” nên tạo nút lá là “N”. Sau khi thực hiện xong thuật toán đệ quy: FID3(U1, C-{Humidity}, {d}), ta có cây như sau: 38 Hình 15. Cây quyết định sau khi chọn thuộc tính Windy (FID3)  Bước tiếp theo gọi thuật toán đệ quy: FID3(U2, C-{Humidity}, {d})  Theo thuật toán ADTDA ta có: [U2]d= {{10}, {4, 8, 11}}  [U2]Outlook = {{4}, {8, 10, 11}} Do đó, 4 1 || |}4{| || |)(| ),( 22  UU dposdOutlook Outlook  [U2]windy = {{4, 8, 10}, {11} 4 1 || |}11{| || |)(| ),( 22  UU dpos dwindy windy  [U2]Temp={{4, 8, 11}, {10}} 1 4 4 || |}11,10,8,4{| || |)(| ),( 22  UU dpos dTemp Temp  Theo thuật toán ID3 ta có:  IG(U2, Outlook) =0.123  IG(U2, Windy) = 0.123  IG(U2, Temp) = 0.811 Vậy:  IGfix(U2, Windy)= 124.02 123.0* 4 1 || ),( *),( 2  Windy WindyUIGdWindy  IGfix(U2, Outlook)= 101.0 3 1235.0* 4 1 || ),( *),( 2  Outlook OutlookUIGdOutlook Humidity {1, 2,…, 12} high Normal low windy {1, 2, 3, 6, 7, 12} FID3(U2, C-{humidity}, {d}) {4, 8, 10 , 11} true false TRUE {5, 9 } FALSE {2, 3, 6, 7, 12 } TRUE {1 } 39  IGfix(U2, Temp)= 519.03 811.0*1 || ),( *),( 2  Temp TempUIGdTemp Ta thấy chỉ số IGfix(U2,Temp) là lớn nhất, nên nó được chọn để phân chia. Tương tự như thuật toán ID3 ta có cây cuối cùng như sau: Hình 16. Cây kết quả (FID3) 2.5. Kết luận chương 2 Trong chương này đã trình bày phương pháp tổng quát xây dựng cây quyết định; ba thuật toán xây dựng cây quyết định ID3, ADTDA, FID3; các ví dụ cụ thể để minh họa từng bước trên mỗi thuật toán; high Normal low windy {1, 2, 3, 6, 7, 12} true false TRUE {5, 9 } FALSE {2, 3, 6, 7, 12 } TRUE {1 } Humidity {1, 2,…, 12} temp {4, 8, 10 , 11} mild hot TRUE {10 } FALSE {4, 8, 11} 40 Chương 3 - ỨNG DỤNG KIỂM CHỨNG VÀ ĐÁNH GIÁ 3.1. Giới thiệu bài toán Chúng ta đang sống trong thế giới thừa thông tin thiếu tri thức – đó là nhận định của nhiều người trong thời đại bùng nổ thông tin hiện nay. Sử dụng phương pháp khai phá tri thức từ dữ liệu để dự đoán rủi ro tín dụng là một phương pháp mới nhằm nâng cao chất lượng tín dụng của Ngân hàng. Rủi ro tín dụng có thể được hiểu là nguy cơ một người đi vay không thể trả được gốc và/hoặc lãi đúng thời hạn quy định. Hiện nay, để phòng ngừa rủi ro tín dụng, các chuyên gia Ngân hàng thực hiện các phương pháp thu thập, phân tích và đánh giá các thông tin về khách hàng, tài sản bảo đảm của khoản vay… Phương pháp truyền thống này có nhiều hạn chế do phụ thuộc vào trình độ, tâm lý và yếu tố chủ quan khác của các cán bộ thẩm định hồ sơ vay nợ của khách hàng. Chính vì vậy mà một công cụ trợ giúp thẩm định và ước đoán chất lượng tín dụng một cách khách quan dựa trên các cơ sở khoa học là hết sức có ý nghĩa và cần thiết. Việc đề xuất cho vay hay không dựa vào các luật quyết định (phân lớp) được xây dựng thông qua cây quyết định đã được nghiên cứu. Nhờ các luật quyết định này sẽ hỗ trợ cán bộ tín dụng có quyết định cho khách hàng vay hay không. Trong phạm vi luận văn này tôi đã tập trung nghiên cứu đối với công tác tín dụng tiêu dùng của khách hàng với tập dữ liệu Bank_data. Dựa vào tập Bank_data sẽ xây dựng mô hình cây quyết định, từ cây quyết định rút ra các luật quyết định. Dựa vào các luật quyết định đó ta sẽ phân lớp được tập dữ liệu mới (dữ liệu về khách hàng xin vay tiêu dùng, nhưng chưa được phân lớp) và tập dữ liệu sau khi được phân lớp sẽ hỗ trợ cho các cán bộ tín dụng ra quyết định cho khách hàng vay hay không. 3.2. Giới thiệu về cơ sở dữ liệu Trong quá trình thử nghiệm, tôi sử dụng tập dữ liệu Bank_data trích từ cơ sở dữ liệu được sưu tầm bởi giáo sư Bamshad Mobasher của Khoa “School of Computing, College of Computing and Digital Media” tại đại học “DePaul University” tại Mỹ ( bank-data.csv). Tập dữ liệu này gồm 600 đối tượng, sau khi tiền sử lí với phần 41 mềm Weka và lưu dưới dạng file excel ta có tập dữ liệu gồm 600 đối tượng, 10 thuộc tính điều kiện và thuộc tính quyết định “result” quyết định mỗi khách hàng là được vay và không được vay. Các thuộc tính và giá trị của các thuộc tính của tập dữ liệu Bank_data được mô tả trong bảng sau: Thứ tự Tên thuộc tính Giá trị Giải thích 1 Tuoi Tre, Trung nien, Gia Trẻ, trung niên, già 2 Gioi_tinh Nam, Nu Nam, Nữ 3 Khu_vuc NT, TTran, Ngoai o, TP Nông thôn, Thị trấn, ngoại ô, thành phố 4 Thu_nhap Thap, TB, Cao Thấp, trung bình, cao 5 Ket_hon C, K Có, không 6 Con 0_Con, 1_con, 2_con, 3_con Không con, một con, hai con, ba con 7 Xe C, K Có, không 8 TKTK (tài khoản tiết kiệm) C, K Có, không 9 TK_Htai (tài khoản hiện tại) C, K Có, không 10 The_chap C, K Có, không 11 RESULT (Cho vay) True, false Có (True), không (False) Bảng 4. Bảng các thuộc tính của tập dữ liệu Bank_data 3.3. Cài đặt ứng dụng Ứng dụng này được viết trong môi trường Visual Studio 2008, viết bằng ngôn ngữ lập trình Visal Basic. Ứng dụng này tập trung vào xây dựng và đánh giá độ chính xác của các thuật toán được trình bày ở chương 2. Từ các cây quyết định hay các luật quyết định rút ra từ cây quyết định sẽ hỗ trợ cho các cán bộ tín dụng trong ngân hàng quyết định cho khách hàng được vay hay không. 42 3.4. Kết quả và đánh giá thuật toán 3.4.1. Mô hình cây quyết định tương ứng với tập dữ liệu Bank_data  Cây quyết định ứng với thuật toán ID3 Hình 17. Dạng cây quyết định ID3  Cây quyết định ứng với thuật toán ADTDA Hình 18. Dạng cây quyết định ADTDA 43  Cây quyết định ứng với thuật toán FID3 Trong quá trình thực nghiệm tác giả thấy trong thuật toán FID3 nếu áp dụng trên 1 cơ sở dữ liệu lớn thì độ phục thuộc của các thuộc tính điều kiền vào thuộc tính quyết định đều bằng 0 (ở bước đầu tiên khi xây dựng cây quyết định). Do đó, lượng thông tin thu thêm ổn định IGfix của các thuộc tính điều kiện cũng bằng 0. Trong trường hợp này thì thuật toán sẽ chọn một thuộc tính bất kỳ (thuộc tính đầu tiên) làm thuộc tính phân chia, và như vậy cây quyết định sẽ không tối ưu. Vì vậy, tác giả đã mạnh dạn cải tiến dựa theo thuật toán ADTDA, đó là nếu tất các các độ phụ thuộc của thuộc tính điều kiện vào thuộc tính quyết định là bằng 0, thì lượng thông tin thu ổn định IGfix sẽ được tính dựa vào độ phụ thuộc chính xác , tức là: Và khi đó cây quyết định của thuật toán FID3 trên cơ sở dữ liệu Bank_data như sau: Hình 19. Dạng cây quyết định FID3 || ),(*),(),( c cUIGcdcUIG fix  44 3.4.2. Các luật quyết định tương ứng với tập dữ liệu Bank_data  Các luật quyết định ứng với cây quyết định ID3 Hình 20. Một số luật của cây quyết định ID3  Các luật quyết định ứng với cây quyết định ADTDA Hình 21. Một số luật của cây quyết định ADTDA  Các luật quyết định ứng với cây quyết định FID3 Hình 22. Một số luật của cây quyết định FID3 3.4.3. Đánh giá thuật toán Đánh giá độ chính xác của thuật toán với số nếp gấp (fold) là 10 trên bộ dữ liệu tennis (Bảng 3) và bộ dữ liệu Bank_data, ta được kết quả như sau: 45 Dữ liệu Số mẫu Số thuộc tính ID3 ADTDA FID3 Bank_data 600 11 77.33% 78.57% 80.71% Tennis 12 5 80% 80% 80% Trung bình 78.67% 79.29% 80.36% Bảng 5. Độ chính xác của các thuật toán 3.4.4. Ứng dụng cây quyết định trong khai phá dữ liệu Ứng dụng hỗ trợ các bộ ngân hàng ra quyết định cho khách hàng vay hay không. Với những tin về khách hàng xin vay (đã biết giá trị của các thuộc tính điều kiện nhưng chưa được phân lớp) dựa vào mô hình cây quyết định đã được xây dựng ta dự đoán được lớp của bộ dữ liệu đó (cho vay hay không cho vay). Từ đó hỗ trợ cho cán bộ ngân hàng trong quá trình ra quyết định cho vay hay không. Trong ứng dụng, khi xây dựng mô hình cây quyết định có đánh giá độ chính xác của từng luật quyết định dựa trên bộ dữ liệu đưa vào để training. Do đó, việc phân lớp các mẫu dữ liệu mới đã đưa ra được độ tin cậy của việc phân lớp đó. Ví dụ khi đánh giá độ chính xác của luật 9 dựa trên bộ dữ liệu training là 90%. Quá trình phân lớp trên mẫu dữ liệu nào đó dựa vào luật 9, thì độ tin cậy của lớp đó sẽ là 90%. Độ tin cậy của các luật quyết định phụ thuộc rất lớn vào bộ dữ liệu training, dữ liệu training càng đủ lớn thì độ tin cậy của các luật càng cao. Tuy nhiên, trong ứng dụng này việc xây dựng cây quyết định chỉ dựa trên bộ dữ liệu training gồm 600 dữ liệu, do đó độ tin cậy của các luật chỉ mang tính chất minh họa (tính chính xác không cao). 46 Hình 23. Giao diện ứng dụng 3.5. Kết luận chương 3 Trong chương này đã phát biểu bài toán để kiểm chứng các thuật toán xây dựng cây quyết định ở chương 2 trên bộ dữ liệu mẫu Bank_data. Đồng thời cài đặt, đánh giá độ chính xác của từng thuật toán và đánh giá độ chính xác của các luật. Dựa vào mô hình cây quyết định (các luật quyết định) đã được xây dựng, phân lớp các mẫu dữ liệu mới. 47 KẾT LUẬN Khai phá dữ liệu là một lĩnh vực đã, đang và luôn luôn thu hút các nhà nghiên cứu bởi nó là một lĩnh vực cho phép phát hiện tri thức trong cơ sở dữ liệu khổng lồ bằng các phương thức thông minh. Nghiên cứu lĩnh vực này đòi hỏi người nghiên cứu phải biết tổng hợp các kết quả nghiên cứu ở nhiều lĩnh vực của khoa học máy tính và việc ứng dụng nó trong từng nhiệm vụ của khai phá dữ liệu. Qua hai năm học tập, tìm tòi, nghiên cứu, đặc biệt là trong khoảng thời gian làm luận văn, tác giả đã hoàn thiện luận văn với các mục tiêu đặt ra ban đầu. Cụ thể luận văn đã đạt được những kết quả sau: - Trình bày các kiến thức cơ bản về khai phá dữ liệu; hệ thống hóa các kiến thức cơ bản của lý thuyết tập thô được áp dụng để xây dựng cây quyết định. - Giới thiệu phương pháp tổng quát xây dựng cây quyết định, và trình bày ba thuật toán xây dựng cây quyết định ID3, ADTDA, FID3 và một số ví dụ minh họa cho các phương pháp xây dựng cây quyết định cũng được trình bày. - Cài đặt bằng Visual Basic ba thuật toán xây dựng cây quyết định ID3, ADTDA, FID3 trên cơ sở dữ liệu mẫu Bank_data. Đánh giá độ chính xác của các thuật toán trên và đánh giá độ chính xác của từng luật trong mô hình cây quyết định. Qua quá trình học tập, nghiên cứu tác giả không những tích lũy được thêm các kiến thức mà còn nâng cao được khả năng lập trình, phát triển ứng dụng. Tác giả nhận thấy luận văn đã giải quyết tốt các nội dung, yêu cầu nghiên cứu đặt ra, có các ví dụ minh họa cụ thể. Song do thời gian có hạn nên luận văn vẫn còn tồn tại một số thiếu sót, một số vấn đề mà tác giả còn phải tiếp tục nghiên cứu, tìm hiểu. Hướng phát triển của đề tài là: Về lý thuyết: - Cần tiếp tục nghiên cứu các thuật toán khai phá dữ liệu bằng cây quyết định dựa vào tâp thô như: thuật toán ADTCCC (dựa vào CORE và đại 48 lượng đóng góp phân lớp của thuộc tính), thuật toán ADTNDA (dựa vào độ phụ thuộc mới của thuộc tính), … - Nghiên cứu các phương pháp xây dựng cây quyết định trên hệ thống thong tin không đầy đủ, dữ liệu liên tục và không chắc chắn. Về chương trình demo: - Cần bổ sung thêm dữ liệu cho tập training để mô hình cây quyết định có độ tin cậy cao hơn và hoạt động hiệu quả hơn. - Cần tiếp tục phát triển hoàn thiện theo hướng trở thành phần mềm khai phá dữ liệu trong tín dụng tiêu dùng nhằm hỗ trợ cho cán bộ tín dụng đưa ra quyết định cho khách hàng vay hay không. - Tìm hiểu nhu cầu thực tế để từ đó cải tiến chương trình, cài đặt lại bài toán theo các thuật toán đã nghiên cứu để làm việc tốt hơn với các cơ sở dữ liệu lớn và có thể có được sản phẩm trên thị trường.. 49 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử dụng ma trận phân biệt được”, Chuyên san các công trình nghiên cứu triển khai Viễn thông và CNTT, (15), tr. 83-87. [2] Nguyễn Thanh Bình (2007), “Ứng dụng cây quyết định trong bài toán phân lớp”, Luận văn thạc sỹ khoa học. Trường đại học Khoa học - Đại học Huế. [3] Nguyễn Thanh Tùng (2009), “Một tiêu chuẩn mới chọn nút xây dựng cây quyết định”, Tạp chí Khoa học và Công nghệ, 47(2), tr. 15–25. Tiếng Anh [4] Andrzej Skowron, Ning Zhong (2000), “Rough Sets in KDD”, Tutorial Notes. [5] Baoshi Ding, Yongqing Zheng, Shaoyu Zang (2009), "A New Decision Tree Algorithm Based on Rough Set Theory", Asia-Pacific Conference on Information Processing, (2), pp. 326-329. [6] Cuiru Wang, Fangfang OU (2008), "An Algorithm for Decision Tree Construction Based on Rough Set Theory", International Conference on Computer Science and Information Technology, pp. 295-298. [7] Ho Tu Hao, Knowledge Discovery and Dataming Techniques and Practice, http:// www.netnam.vn/unescocourse/knowledge. [8] Jan Komorowski, Lech Polkowski, Andrzej Skowron, “Rough Sets: A Tutorial”. [9] John Ross Quilan (1990), “Decision trees and decision making”, IEEE transactions on Man and Cybernetics, (20), pp. 339-346. [10] Longjun Huang, Minghe Huang, Bin Guo, Zhimming Zhang (2007), "A New Method for Constructing Decision Tree Based on Rough Set 50 Theory", IEEE International Conference on Granular Computing, pp. 241- 244. [11] Ramadevi Yellasiri, C.R.Rao, Vivekchan Reddy (2007), “Decision Tree Induction Using Rough Set Theory – Comparative Study”, Journal of Theoretical and Applied Information Technology, pp. 110-114. [12] Sang Wook Han, Jae Yearn Kim (2007), "Rough Set-based Decision Tree using the Core Attributes Concept", Second International Conference on Innovative Computing Information and Control, pp. 298 - 301. [13] Weijun Wen (2009), “A New Method for Constructing Decision Tree Based on Rough Set Theory”, Proceedings of the International Symposium on Intelligent Information Systems and Applications Qingdao China, pp. 416-419. [14] Z. Pawlak (1998) - Rough Set Theory and Its Application to Data Analysis, Cybernetics and Systems: An International Journal 29, pp. 661-688.