Luận văn Một số kỹ thuật đánh giá luật dựa trên lý thuyết tập thô

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN THỊ LY SA MỘT SỐ KỸ THUẬT ĐÁNH GIÁ LUẬT DỰA TRÊN LÝ THUYẾT TẬP THÔ LUẬN VĂN THẠC SĨ NGÀNH KHOA HỌC MÁY TÍNH Thành phố Hồ Chí Minh - 2010 ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN THỊ LY SA MỘT SỐ KỸ THUẬT ĐÁNH GIÁ LUẬT DỰA TRÊN LÝ THUYẾT TẬP THÔ Chuyên ngành: Khoa học máy tính LUẬN VĂN THẠC SĨ HƯỚNG DẪN KHOA HỌC TS. VŨ THANH NGUYÊN Thành phố Hồ Chí Minh - 2010 i NHẬN XÉT CỦA CÁN BỘ HƯỚNG DẪN ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... TP Hồ Chí Minh, ngày …….tháng …… năm 2010 Cán bộ hướng dẫn TS. Vũ Thanh Nguyên ii NHẬN XÉT CỦA CÁN BỘ PHẢN BIỆN ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... TP Hồ Chí Minh, ngày …….tháng …… năm 2010 Cán bộ phản biện iii MỤC LỤC Trang NHẬN XÉT CỦA CÁN BỘ HƯỚNG DẪN ................................................................ I NHẬN XÉT CỦA CÁN BỘ PHẢN BIỆN .................................................................. II MỤC LỤC ...................................................................................................................III DANH MỤC CÁC BẢNG ......................................................................................... VI DANH MỤC CÁC HÌNH..........................................................................................VII DANH MỤC CÁC TỪ VIẾT TẮT ..........................................................................VIII CHƯƠNG 1. GIỚI THIỆU.........................................................................................1 1.1. KHAI PHÁ DỮ LIỆU .........................................................................................1 1.2. LUẬT KẾT HỢP.................................................................................................2 1.3. LÝ THUYẾT TẬP THÔ .....................................................................................2 1.4. ĐÁNH GIÁ LUẬT..............................................................................................3 1.5. TÓM LẠI ............................................................................................................4 CHƯƠNG 2. KIẾN THỨC CƠ BẢN.........................................................................5 2.1. LÝ THUYẾT TẬP THÔ .....................................................................................5 2.1.1. Các khái niệm ..............................................................................................5 2.1.2. Thuật toán tìm các rút gọn .........................................................................12 2.1.3. Thuật toán tìm rút gọn tối ưu .....................................................................16 2.1.4. Tập thô và rời rạc hóa dữ liệu ....................................................................17 2.2. PHÁT SINH LUẬT KẾT HỢP .........................................................................23 2.2.1. Giới thiệu ...................................................................................................23 2.2.2. Khai thác tập phổ biến ...............................................................................23 2.2.3. Khai thác luật kết hợp từ tập phổ biến .......................................................28 2.2.4. Sử dụng luật kết hợp vào việc phân lớp.....................................................30 CHƯƠNG 3. CÁC PHƯƠNG PHÁP ĐÁNH GIÁ LUẬT DỰA TRÊN LÝ THUYẾT TẬP THÔ..................................................................................................32 3.1. ĐỘ ĐO SỰ HỮU ÍCH CỦA LUẬT ..................................................................32 3.1.1. Độ hỗ trợ ...................................................................................................33 3.1.2. Độ tin cậy ..................................................................................................33 3.1.3. Độ đo Lift...................................................................................................34 iv 3.1.4. Độ đo Laplace ............................................................................................34 3.1.5. Độ chắc chắn .............................................................................................35 3.1.6. Độ đo Leverage..........................................................................................35 3.1.7. Độ đo Correlation ......................................................................................35 3.1.8. Độ đo Jaccard.............................................................................................36 3.1.9. Độ đo Cosine..............................................................................................36 3.1.10. Độ đo Odds Ratio.....................................................................................36 3.1.11. Rule Template..........................................................................................36 3.2. ĐỘ ĐO TẦM QUAN TRỌNG CỦA LUẬT .....................................................38 3.2.1. Các định nghĩa ...........................................................................................38 3.2.2. Một ví dụ về độ đo RIM ............................................................................39 3.2.3. Nhận xét về độ đo RIM..............................................................................40 3.3. ĐỘ ĐO XEM LUẬT NHƯ THUỘC TÍNH.......................................................41 3.3.1. Xây dựng bảng quyết định mới..................................................................41 3.3.2. Các định nghĩa ...........................................................................................43 3.3.3. Một ví dụ về độ đo RAM...........................................................................43 3.3.4. Nhận xét giữa hai độ đo RIM và độ đo RAM............................................44 3.4. ĐỘ ĐO TẦM QUAN TRỌNG CẢI TIẾN ........................................................45 3.4.1. Định nghĩa..................................................................................................45 3.4.2. Quá trình thực hiện ....................................................................................45 3.4.3. Một ví dụ về độ đo ERIM..........................................................................46 3.4.4. Nhận xét về độ đo ERIM ...........................................................................47 3.5. ĐỘ ĐO WAERIM.............................................................................................47 3.5.1. Định nghĩa..................................................................................................48 3.5.2. Quá trình thực hiện ....................................................................................48 3.6. ĐỘ ĐO AIERIM ...............................................................................................49 3.6.1. Định nghĩa..................................................................................................49 3.6.2. Một ví dụ về độ đo AIERIM......................................................................50 CHƯƠNG 4. XÂY DỰNG ỨNG DỤNG SO SÁNH KỸ THUẬT ĐÁNH GIÁ LUẬT GIỮA CÁC ĐỘ ĐO.......................................................................................51 4.1. GIỚI THIỆU .....................................................................................................51 4.1.1. Nguồn dữ liệu “Nursery” ...........................................................................51 4.1.2. Nguồn dữ liệu “BankLoan” .......................................................................52 v 4.2. MÔ HÌNH XÂY DỰNG ỨNG DỤNG .............................................................54 4.3. KẾT QUẢ SO SÁNH GIỮA CÁC ĐỘ ĐO.......................................................55 4.3.1. Sử dụng nguồn “Nursery”..........................................................................55 4.3.2. Sử dụng nguồn “BankLoan”......................................................................56 4.3.3. Kết luận......................................................................................................57 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN................................................................65 TÀI LIỆU THAM KHẢO.........................................................................................67 vi DANH MỤC CÁC BẢNG Bảng 2.1. Một ví dụ về Hệ thông tin ................................................................................... 5 Bảng 2.2. Một ví dụ về Bảng quyết định ............................................................................. 6 Bảng 2.3. Ma trận khả phân xây dựng từ Bảng 2.2.......................................................... 11 Bảng 2.4. Một ví dụ về Bảng quyết định ........................................................................... 11 Bảng 2.5. Ma trận khả phân xây dựng từ Bảng 2.4.......................................................... 12 Bảng 2.6. Quá trình rời rạc hoá ....................................................................................... 18 Bảng 2.7. Bảng quyết định mới ∗T ................................................................................... 21 Bảng 2.8. Kết quả rời rạc hóa dữ liệu .............................................................................. 23 Bảng 2.9. Ví dụ về cơ sở dữ liệu dạng giao dịch .............................................................. 24 Bảng 2.10. Một ví dụ về tập phổ biến ............................................................................... 24 Bảng 2.11. Luật kết hợp thỏa minSupp=50%, minConf=80% ......................................... 29 Bảng 3.1. Ví dụ cho mẫu luật............................................................................................ 37 Bảng 3.2. Một số rút gọn từ nguồn Zoo............................................................................ 39 Bảng 3.3. Tập luật quan trọng theo độ đo RIM từ nguồn Zoo.......................................... 40 Bảng 3.4. Bảng quyết định ví dụ cho độ đo RAM ............................................................. 42 Bảng 3.5. Xây dựng bảng quyết định mới ......................................................................... 43 Bảng 3.6. Các luật kết hợp từ nguồn Lenses với minSupp=3% và minConf=70%.......... 44 Bảng 3.7. Tập luật quan trọng theo độ đo RAM từ nguồn Lenses.................................... 44 Bảng 3.8. Trọng số cho từng thuộc tính điều kiện của nguồn Car ................................... 46 Bảng 3.9. Tập luật với độ đo ERIM từ nguồn Car............................................................ 46 Bảng 3.10. Mức độ quan trọng của các tập thuộc tính trên nguồn Car ........................... 50 Bảng 3.11. Tập luật với độ đo AIERIM từ nguồn Car...................................................... 50 Bảng 4.1. Các thuộc tính của nguồn Nursery ................................................................... 51 Bảng 4.2. Các thuộc tính của dữ liệu BankLoan .............................................................. 52 Bảng 4.3. Trọng số các thuộc tính điều kiện của BankLoan ............................................ 53 Bảng 4.4. Kết quả 10 lần thử nghiệm với Nursery ........................................................... 60 Bảng 4.5. Kết quả 10 lần thử nghiệm với BankLoan (trường hơp 1) ............................... 62 Bảng 4.5. Kết quả 10 lần thử nghiệm với BankLoan (trường hơp 2) ............................... 64 vii DANH MỤC CÁC HÌNH Hình 1.1. Quá trình phát hiện tri thức ................................................................................ 1 Hình 2.1. Tập các điểm cắt trên thuộc tính a.................................................................... 19 Hình 2.2. Tập các điểm cắt cực tiểu ................................................................................. 22 Hình 2.3. Cây tìm kiếm IT-tree ......................................................................................... 26 Hình 2.4. Cây tìm kiếm tập phổ biến với minSupp=50% ................................................. 27 Hình 4.1. Mô hình xây dựng ứng dụng ............................................................................. 54 Hình 4.2. Biểu đồ so sánh giữa các độ đo từ nguồn Nursery ........................................... 55 Hình 4.3. Biểu đồ so sánh giữa các độ đo từ nguồn BankLoan (trường hợp 1)............... 56 Hình 4.4. Biểu đồ so sánh giữa các độ đo từ nguồn BankLoan (trường hợp 2)............... 57 viii DANH MỤC CÁC TỪ VIẾT TẮT AIERIM Attributes Importance Degree Based Enhanced Rule Importance Measure CBA Classification Based on Associations CSDL Cơ Sở Dữ Liệu ERIM Enhanced Rule Importance Measure IT-pair Itemset-Tidset pair IT-tree Itemset-Tidset tree KDD Knowledge Discovery in Database RIM Rule Importance Measure RAM Rule-as-Attribute Measure WAERIM Weight Average Based Enhanced Rule Importance Measure 1 Chương 1. GIỚI THIỆU 1.1. KHAI PHÁ DỮ LIỆU Phát hiện tri thức trong cơ sở dữ liệu (KDD-Knowledge Discovery in Database) là quá trình tìm kiếm những thông tin ẩn có giá trị từ tập dữ liệu lớn, là quá trình hoạt động tương tác giữa con người và cơ sở dữ liệu với sự hỗ trợ của công cụ tin học để chọn ra những tri thức có ích phục vụ cho một mục đích nhất định trong một lĩnh vực nhất định. Khai phá dữ liệu (Data Mining) là một trong những hoạt động của quá trình phát hiện tri thức, là kỹ thuật chính giúp ta lấy được các tri thức hữu ích, quan trọng. Quá trình phát hiện tri thức có thể được biểu diễn bằng Hình 1.1: Hình 1.1. Quá trình phát hiện tri thức Hiện nay trên thế giới đã có nhiều ngành công nghiệp sử dụng kỹ thuật khai phá dữ liệu để phục vụ cho các hoạt động kinh doanh của mình và bước đầu thành công như ngành tài chính, y học, bảo hiểm, sản xuất… Mặc dù kỹ thuật khai phá dữ liệu hiện nay vẫn còn nhiều vấn đề nổi cộm nhưng với những tri thức mà nó đem lại cũng đã chứng tỏ khai phá dữ liệu có một tiềm năng to lớn trong việc tạo ra những lợi nhuận đáng kể trong nền kinh tế. Các hướng tiếp cận khai phá dữ liệu phổ biến đang được nghiên cứu và sử dụng hiện nay: mạng nơron, kỹ thuật phân cụm và phân đoạn, phương pháp Xác định mục tiêu Thu thập và tiền xử lý dữ liệu KHAI PHÁ DỮ LIỆU (Triết xuất tri thức) Phát biểu kết quả và đánh giá Sử dụng tri thức đã phát hiện được 2 láng giềng gần nhất, giải thuật di truyền, phương pháp phát hiện luật kết hợp… Trong đó, các hướng tiếp cận khai phá luật kết hợp: luật kết hợp nhị phân, luật kết hợp mờ, luật kết hợp nhiều mức, luật kết hợp tiếp cận theo hướng tập thô, luật kết hợp với các thuộc tính được đánh trọng số… Luận văn này tập trung vào kỹ thuật phát hiện luật kết hợp theo hướng tiếp cận tập thô trong quá trình khai phá dữ liệu, tiếp theo đó giới thiệu những kỹ thuật đánh giá luật dựa trên cơ sở lý thuyết tập thô để rút trích những luật quan trọng và có ích để tri thức phát hiện được thật sự có ý nghĩa cho ứng dụng. 1.2. LUẬT KẾT HỢP Luật kết hợp là lĩnh vực quan trọng trong khai phá dữ liệu, là kỹ thuật khai phá dữ liệu khá đơn giản nhưng thiết thực. Phát hiện luật kết hợp giúp ta tìm ra được các mối liên quan của các thành phần trong dữ liệu. Chẳng hạn, từ việc phân tích dữ liệu bán hàng của siêu thị, ta có thể phát hiện thói quen mua hàng của khách hàng như: khi khách hàng mua bánh mì thì hầu như họ sẽ mua sữa. Luật kết hợp có thể được sử dụng để tìm hiểu các thói quen này của khá