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

Kết luận Luận văn đã giới thiệu một sốkỹthuật đánh giá luật dựa trên lý thuyết tập thô thông qua 3 độ đo: RIM, RAM, ERIM và đềxuất 2 độ đo mới WAERIM và AIERIM đểgiải quyết hạn chếcủa độ đo ERIM. Vì các rút gọn chứa các thuộc tính tiêu biểu nên những luật phát sinh từcác rút gọn là những tri thức tiêu biểu cho toàn bộCSDL. Ứng với mỗi rút gọn ta có một tập luật, một luật được xem là quan trọng nếu nó xuất hiện thường xuyên trong các tập luật, độ đo RIM của một luật chính là tỉlệgiữa sốlượng các tập luật chứa luật này so với tổng sốlượng các tập luật. Độ đo RIM dùng để đánh giá mức độquan trọng của một luật và so sánh tầm quan trọng của nó với các luật khác. Đây là một độ đo khách quan, đơn giản và tính toán khá dễ dàng. Độ đo RAM được đềxuất đểrút trích những luật quan trọng nhất từtập luật dù độ đo này không có một giá trịtượng trưng cụthể. Bằng cách xem luật như thuộc tính, độ đo này xây dựng lại bảng quyết định mới và tìm rút gọn của bảng quyết định mới này, vì rút gọn chứa những thuộc tính tiêu biểu nên các rút gọn của bảng quyết định mới chính là những luật tiêu biểu nhất cho toàn bộdữliệu. Độ đo ERIM là độ đo chủquan vì giá trịcủa độ đo này được tính toán dựa trên trọng sốcủa các thuộc tính được đánh giá bởi các chuyên gia. Từtập luật RIM – tập luật thu được từ độ đo RIM – ta tính toán giá trịERIM cho từng luật, những luật có giá trị độ đo RIM và ERIM cao được xem là quan trọng. Tuy nhiên hạn chếcủa độ đo ERIM là phụthuộc vào sốlượng các thuộc tính điều kiện trong luật, do đó luận văn đềxuất độ đo WAERIM nhưlà giải pháp thay thếERIM. Việc sửdụng trọng sốcủa các thuộc tính điều kiện trong quá trình đánh giá luật giúp người dùng có thểchọn ra những luật thực sự đáng tin cậy vì các trọng sốnày chính là ý kiến nhận định của các chuyên gia trong cùng lĩnh vực (ERIM, WAERIM). Tuy nhiên đối với những ứng dụng không được các chuyên gia đánh giá thì việc đánh giá tầm quan trọng của luật theo độ đo này mang lại hiệu quảthấp, vì vậy song song với độ đo WAERIM luận văn đềxuất độ đo AIERIM, độ đo này cũng cải tiến độ đo RIM dựa vào mức độquan trọng của các thuộc tính điều kiện. Khác với ERIM và WAERIM, mức độquan trọng các thuộc tính điều kiện ở độ đo AIERIM có được từchính nguồn dữliệu dùng đểkhai phá. Khảnăng đánh giá luật của các độ đo này được chứng minh bằng thử nghiệm thực tếtrên 2 nguồn dữliệu Nursery và BankLoan. Cũng nhưcác độ đo hữu ích, các độ đo dựa trên lý thuyết tập thô không phải là sựchọn lựa tốt nhất cho tất cảcác ứng dụng, mỗi độ đo đều có những mặc hạn chếnhất định và trong một sốtrường hợp nó không mang lại kết quảnhưmong đợi.  Hướng phát triển - Mởrộng kỹthuật đánh giá luật bằng cách kết hợp các độ đo đã được đề xuất, chẳng hạn kết hợp WAERIM với Confidence, AIERIM với Support, hay sửdụng tập luật RIM đểxây dựng lại bảng quyết định mới và tìm các luật quan trọng theo độ đo RAM - Tiếp tục tìm hiểu các độ đo khác kết hợp giữa độ đo chủquan và khách quan để đưa ra nhiều kỹthuật đánh giá luật hỗtrợviệc chọn lựa những tri thức thực sựcó ích trong quá trình khai thác dữliệu.

pdf79 trang | Chia sẻ: tuandn | Lượt xem: 2665 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Luận văn Một số kỹ thuật đánh giá luật dựa trên lý thuyết tập thô, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠ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á
Luận văn liên quan