Luận án Phát triển một số thuật toán hiệu quả khai thác tập mục trên cơ sở dữ liệu số lượng có sự phân cấp các mục

Nội dung tài liệu: Luận án Phát triển một số thuật toán hiệu quả khai thác tập mục trên cơ sở dữ liệu số lượng có sự phân cấp các mục

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------------ NGUYỄN DUY HÀM PHÁT TRIỂN MỘT SỐ THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP MỤC TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG CÓ SỰ PHÂN CẤP CÁC MỤC LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2016
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------------ NGUYỄN DUY HÀM PHÁT TRIỂN MỘT SỐ THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP MỤC TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG CÓ SỰ PHÂN CẤP CÁC MỤC Chuyên ngành: CƠ SỞ TOÁN CHO TIN HỌC Mã số: 62460110 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. TS. NGUYỄN THỊ HỒNG MINH 2. PGS.TS. VÕ ĐÌNH BẢY XÁC NHẬN NCS ĐÃ CHỈNH SỬA THEO QUYẾT NGHỊ CỦA HỘI ĐỒNG ĐÁNH GIÁ LUẬN ÁN Ngƣời hƣớng dẫn khoa học Chủ tịch hội đồng đánh giá Luận án Tiến sĩ TS. Nguyễn Thị Hồng Minh PGS.TS. Huỳnh Quyết Thắng Hà Nội - 2016
3. LỜI CAM ĐOAN Tôi xin cam đoan luận án này là công trình nghiên cứu do tác giả thực hiện dƣới sự hƣớng dẫn của tập thể cán bộ hƣớng dẫn. Luận án có sử dụng thông tin trích dẫn từ nhiều nguồn tham khảo khác nhau, các thông tin trích dẫn đều đƣợc ghi rõ nguồn gốc. Các số liệu thực nghiệm, kết quả nghiên cứu trình bày trong luận án là hoàn toàn trung thực, chƣa đƣợc công bố bởi tác giả nào hay trong bất kì công trình nào khác. Tác giả Nguyễn Duy Hàm i
4. LỜI CẢM ƠN Luận án Tiến sĩ này đƣợc thực hiện tại trƣờng Đại học Khoa học và Tự nhiên - Đại học Quốc gia Hà Nội với sự hƣớng dẫn khoa học của TS. Nguyễn Thị Hồng Minh, PGS.TS.Võ Đình Bảy và TS. Lê Quang Minh. Nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo, cô giáo hƣớng dẫn đã định hƣớng khoa học, tận tâm giúp đỡ và chỉ bảo tỉ mỉ trong suốt quá trình nghiên cứu mới có thể hoàn thiện bản luận án này. Nghiên cứu sinh luôn ghi nhớ công lao dạy dỗ, dìu dắt vào con đƣờng khoa học của cố PGS.TS. Hoàng Chí Thành - ngƣời đã hƣớng dẫn Nghiên cứu sinh ở giai đoạn đầu làm nghiên cứu khoa học. Nghiên cứu sinh xin chân thành cảm ơn các nhà khoa học, tác giả các công trình nghiên cứu đã đƣợc trích dẫn trong luận án vì đây là nguồn tài liệu quý báu để Nghiên cứu sinh phát triển và hoàn thiện các công bố của mình. Nghiên cứu sinh xin chân thành cảm ơn Ban Giám hiệu, lãnh đạo Khoa Toán - Cơ - Tin học, các thầy cô, giảng viên Bộ môn Tin học - Trƣờng Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo những điều kiện thuận lợi nhất để Nghiên cứu sinh hoàn thành chƣơng trình học tập và thực hiện hoàn tất luận án của mình. Nghiên cứu sinh xin chân thành cảm ơn Ban Giám hiệu Trƣờng Đại học An ninh nhân dân, tập thể giáo viên Bộ môn Toán - Tin học Trƣờng Đại học An ninh nhân dân nơi Nghiên cứu sinh công tác và các bạn bè thân thiết đã luôn tạo điều kiện, động viên, khuyến khích và hỗ trợ tối đa để Nghiên cứu sinh hoàn thành bản luận án này. Cuối cùng, con xin cảm ơn Bố Mẹ, đặc biệt là Mẹ - ngƣời đã luôn hy sinh tất cả vì sự nghiệp học tập của các con, rất tiếc mẹ đã không đợi đƣợc đến ngày con hoàn thành luận án. Xin cảm ơn gia đình, chị gái và các em đã luôn đồng hành, động viên, chia sẻ giúp duy trì nhiệt huyết và nghị lực để đi đến hoàn thành bản luận án này./ TP. Hồ Chí Minh, tháng năm 2016 ii
5. MỤC LỤC LỜI CAM ĐOAN ........................................................................................................... I LỜI CẢM ƠN ............................................................................................................... II MỤC LỤC .................................................................................................................... III DANH MỤC BẢNG ......................................................................................................V DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .................................................................. VII DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT...................................................X MỞ ĐẦU ........................................................................................................................ 1 CHƢƠNG 1. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC ...................................... 7 1.1. Bài toán khai thác tập mục .................................................................................. 7 1.1.1. Một số khái niệm cơ bản ................................................................................. 8 1.1.2. Bài toán khai thác FI ...................................................................................... 15 1.2. Các phƣơng pháp khai thác FI ......................................................................... 15 1.2.1. Phƣơng pháp khai thác FI trên CSDL ngang ................................................ 15 1.2.2. Phƣơng pháp khai thác FI trên CSDL dọc dựa trên IT-tree .......................... 18 1.3. Một số phƣơng pháp khai thác FWI và FWUI trên CSDL số lƣợng ............ 21 1.3.1. Giới thiệu ....................................................................................................... 21 1.3.2. Khai thác FWI ............................................................................................... 21 1.3.3. Khai thác FWUI ............................................................................................. 24 1.3.4. Khai thác TRFIk ............................................................................................. 26 1.4. Khai thác FI trên CSDL có sự phân cấp các mục ........................................... 28 1.5. Tiếp cận bit-vector trong khai thác FI ............................................................. 31 1.6. Kết luận chƣơng ................................................................................................. 32 CHƢƠNG 2. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG ................................................................................................................. 35 2.1. Thuật toán khai thác tập FWI .......................................................................... 36 2.1.1. Giới thiệu ....................................................................................................... 36 2.1.2. Thuật toán tính giao của hai IWS .................................................................. 40 2.1.3. Thuật toán khai thác FWI .............................................................................. 42 2.1.4. Kết quả thực nghiệm ...................................................................................... 48 2.2. Thuật toán khai thác FWUI .............................................................................. 54 2.2.1. Cấu trúc Multi bit segment ............................................................................ 54 2.2.2. Thuật toán xác định giao MBiS ..................................................................... 55 2.2.3. Thuật toán khai thác FWUI dựa trên MBiS-tree ........................................... 56 2.2.4. Kết quả thực nghiệm ...................................................................................... 59 iii
6. 2.3. Thuật toán khai thác TRFWUIk ....................................................................... 63 2.3.1. Một số khái niệm ........................................................................................... 63 2.3.2. Cấu trúc DTab ............................................................................................... 64 2.3.3. Cấu trúc TR-tree ............................................................................................ 65 2.3.4. Thuật toán khai thác TRFWUIk sử dụng cấu trúc dữ liệu DTab ................... 65 2.3.5. Thuật toán khai thác nhanh TRFWUIk dựa trên cấu trúc DHeap.................. 68 2.3.6. Kết quả thực nghiệm ...................................................................................... 70 2.4. Kết luận chƣơng ................................................................................................. 73 CHƢƠNG 3. KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG CÓ SỰ PHÂN CẤP CÁC MỤC .......................................................... 75 3.1. Giới thiệu bài toán .............................................................................................. 76 3.2. Thuật toán khai thác FWUI trên HQDB ......................................................... 79 3.2.1. Thuật toán xác định weight cho các mục cha ................................................ 79 3.2.2. Thuật toán thêm mục cha vào CSDL ............................................................ 80 3.2.3. Thuật toán khai thác FWUI ........................................................................... 81 3.3. Một số cải tiến nâng cao hiệu quả khai thác FWUI trên HQDB ................... 84 3.3.1. Cấu trúc EDBV .............................................................................................. 84 3.3.2. Tính tidset nút cha từ tidset nút con .............................................................. 89 3.3.3. Kiểm tra mối quan hệ cha con đối với các mục trong tập mục ..................... 91 3.3.4. Thuật toán khai thác nhanh FWUI trên HQDB ............................................. 92 3.4. Kết quả thực nghiệm .......................................................................................... 93 3.4.1. CSDL thực nghiệm ........................................................................................ 93 3.4.2. Kết quả thực nghiệm ...................................................................................... 94 3.5. Kết luận chƣơng ............................................................................................... 100 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................................... 101 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN ......................................................................................................... 103 iv
7. DANH MỤC BẢNG Bảng 1.1. Các giao dịch của nhị phân DB ............................................................. 8 Bảng 1.2. Các giao dịch của CSDL nhị phân có sự phân cấp mục DB.......... 9 Bảng 1.3. ID của các mục của DB ....................................................................... 10 Bảng 1.4. Các giao dịch của DB bằng ID ............................................................ 10 Bảng 1.5. Giao dịch của CSDL số lƣợng BD .................................................. 12 Bảng 1.6. Trọng số các mục của DB ................................................................... 12 Bảng 1.7. Các giao dịch của CSDL trọng số DB ................................................ 13 Bảng 1.8. Trọng số của các mục của DB ............................................................. 13 Bảng 1.9. CSDL DB ............................................................................................ 15 Bảng 1.10. DB theo chiều dọc ............................................................................... 19 Bảng 1.11. Giá trị tw của CSDL DB trong ví dụ 1.4 ............................................. 23 Bảng 1.12. twu các giao dịch của DB trong ví dụ 1.4 ........................................... 25 Bảng 1.13. DB trong Ví dụ 1.2 sau khi thêm mục cha .......................................... 30 Bảng 2.1. Bit-vector ............................................................................................ 36 Bảng 2.2. DBV của bit-vector trong ví dụ 2.1 .................................................... 36 Bảng 2.3. IWS từ bit-vector trong ví dụ 2.1 ........................................................ 37 Bảng 2.4. Chỉ số các bit 1 của IWS(X) ................................................................ 39 Bảng 2.5. Mảng MAP .......................................................................................... 42 Bảng 2.6. IWS của các mục ................................................................................ 46 Bảng 2.7. Mô tả CSDL thực nghiệm ................................................................... 49 Bảng 2.8. Bit-vector với 96 phần tử .................................................................... 54 Bảng 2.9. MBiS từ bit-vector ở Bảng 2.8 ............................................................ 55 Bảng 2.10. Bảng TRFWUIk ................................................................................... 64 Bảng 3.1. Giao dịch của HD ................................................................................ 76 Bảng 3.2. Trọng số .............................................................................................. 76 Bảng 3.3. Tên mặt hàng của các mục ................................................................. 77 v
8. Bảng 3.4. Giao dịch của HD ................................................................................ 82 Bảng 3.5. Trọng số .............................................................................................. 82 Bảng 3.6. twu của các giao dịch .......................................................................... 83 Bảng 3.7. Tập 1-itemset phổ biến ........................................................................ 83 Bảng 3.8. Mảng MAP với 65.535 phần tử .......................................................... 86 Bảng 3.9. Biểu diễn số nguyên K dƣới dạng bốn đoạn, mỗi đoạn là một word .... 86 Bảng 3.10. Mô tả CSDL ........................................................................................ 93 Bảng 3.11. Các mức trên cây phân cấp ................................................................. 93 Bảng 3.12. So sánh bộ nhớ và số lƣợng các mục ................................................. 94 Bảng 3.13. Thực nghiệm trên CSDL SALE-FACT-SYNC .................................. 95 Bảng 3.14. So sánh thời gian chạy trên CSDL SALE-FACT-1997 ...................... 99 vi
9. DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Cây phân cấp Tr .................................................................................. 10 Hình 1.2. Cây phân cấp Tr biểu diễn theo ID ..................................................... 11 Hình 1.3. Thuật toán Apriori trong khai thác tập mục phổ biến ......................... 16 Hình 1.4. Thuật toán FP-Growth dựa trên cấu trúc FP-tree ................................ 17 Hình 1.5. Thuật toán Eclat dựa trên cấu trúc IT-tree .......................................... 19 Hình 1.6. Cây IT tree với minsup = 0,5 của CSDL DB ...................................... 20 Hình 2.1. Thuật toán xác định giao hai IWS ....................................................... 41 Hình 2.2. Thuật toán tính ws của tập mục X ....................................................... 43 Hình 2.3. Thuật toán xây dựng cây IWS-tree ..................................................... 45 Hình 2.4. Thuật toán khai thác FWI dựa trên IWS-tree ...................................... 45 Hình 2.5. IWS-tree với nút A(minws = 0,4) ........................................................ 46 Hình 2.6. IWS-tree với nútA vàB(minws = 0,4) .................................................. 47 Hình 2.7. IWS-tree với minws = 0,4 ................................................................... 48 Hình 2.8. So sánh thời gian chạy với CSDL RETAIL........................................ 49 Hình 2.9. So sánh thời gian chạy với CSDL BMS-POS. .................................... 49 Hình 2.10. So sánh thời gian chạy với CSDL SALE-FACT-1997. ...................... 50 Hình 2.11. So sánh thời gian chạy với CSDL SALE-FACT-1997+1998............. 50 Hình 2.12. So sánh thời gian chạy với CSDL SALE-FACT-SYNC. ................... 50 Hình 2.13. So sánh thời gian chạy với CSDL CONNECT. .................................. 50 Hình 2.14. So sánh thời gian chạy với CSDL ACCIDENTS. .............................. 51 Hình 2.15. So sánh bộ nhớ sử dụng với CSDL RETAIL. .................................... 51 Hình 2.16. So sánh bộ nhớ sử dụng với CSDL BMS-POS................................... 51 Hình 2.17. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997. .................... 51 Hình 2.18. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997+1998. ......... 52 vii
10. Hình 2.19. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-SYNC. ................. 52 Hình 2.20. So sánh bộ nhớ sử dụng với CSDL CONNECT. ................................ 52 Hình 2.21. So sánh bộ nhớ sử dụng với CSDL ACCIDENT. .............................. 52 Hình 2.22. Thuật toán xác định giao hai MBiS .................................................... 56 Hình 2.23. Thuật toán tính wus dựa trên MBiS .................................................... 57 Hình 2.24. Thuật toán khai thác FWUI dựa trên MBiS-tree ................................ 58 Hình 2.25. So sánh thời gian chạy trên CSDL RETAIL....................................... 59 Hình 2.26. So sánh thời gian chạy trên CSDL BMS-POS. ................................... 59 Hình 2.27. So sánh thời gian chạy trên CSDL SALE-FACT-1997. ..................... 60 Hình 2.28. So sánh thời gian chạy trên CSDL SALE-FACT-1997+1998............ 60 Hình 2.29. So sánh thời gian chạy trên CSDL SALE-FACT-SYNC. .................. 60 Hình 2.30. So sánh thời gian chạy trên CSDL CONNECT. ................................. 60 Hình 2.31. So sánh thời gian chạy trên CSDL ACCIDENTS. ............................. 61 Hình 2.32. So sánh bộ nhớ sử dụng trên CSDL RETAIL. ................................... 61 Hình 2.33. So sánh bộ nhớ sử dụng trên CSDL BMS-POS. ................................. 61 Hình 2.34. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997. ................... 61 Hình 2.35. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997+1998. ........ 62 Hình 2.36. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-SYNC. ................ 62 Hình 2.37. So sánh bộ nhớ sử dụng trên CSDL CONNECT. ............................... 62 Hình 2.38. So sánh bộ nhớ sử dụng trên CSDL ACCIDENT. ............................. 62 Hình 2.39. DTab với k = 5 .................................................................................... 65 Hình 2.40. Thuật toán tạo TR-tree sử dụng DTab ................................................ 67 Hình 2.41. Thuật toán lọc ra TRFWUIk ................................................................ 68 Hình 2.42. DHeap với k = 5 với CSDL trong ví dụ 1.4 ........................................ 69 Hình 2.43. Thuật toán tạo TR-tree sử dụng DHeap .............................................. 70 viii