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 V a 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 [u i ] p Lớp tương đương chứa đối tượng u i 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 )(S C 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á. [...]... 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ậ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... đượ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... 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. .. đ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á... 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 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:... 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... 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, …) Cây quyết định Dữ liệu huấn luyện Dữ liệu cụ thể Kết quả ? (Sunny, True, Cool, High) 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ừ. .. 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 -... 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á, .  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 . 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