Luận văn Thạc sĩ Khoa học: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:120

Thêm vào BST

Báo xấu

29
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Khoa học: 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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: 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

ĐẠ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
ĐẠ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
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
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
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
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
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
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
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
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
Hình 2.44. Thuật toán lọc ra TRFWUIk ................................................................ 70 Hình 2.45. So sánh thời gian chạy trên CSDL MBS-POS .................................... 71 Hình 2.46. So sánh thời gian chạy trên CSDL RETAIL....................................... 71 Hình 2.47. So sánh thời gian chạy trên CSDL CONNECT .................................. 72 Hình 2.48. So sánh thời gian trên CSDL SALE-FACT-1997 .............................. 72 Hình 2.49. So sánh thời gian trên CSDL SALE-FACT-1997+1998 .................... 72 Hình 2.50. So sánh thời gian trên CSDL SALE-FACT-SYNC ............................ 72 Hình 3.1. Tập các cây phân cấp Tr ..................................................................... 77 Hình 3.2. Thuật toán tính weight cho các mục cha ............................................. 80 Hình 3.3. Thuật toán thêm mục cha vào CSDL .................................................. 80 Hình 3.4. Thuật toán khai thác FWUI từ HQDB ................................................ 82 Hình 3.5. Cây HIT-tree với CSDL HD và minwus = 0,6.................................... 84 Hình 3.6. Sử dụng các phép AND và dịch bit để tách các đoạn hai byte ........... 87 Hình 3.7. Thuật toán tính nhanh wus của các tập mục ...................................... 89 Hình 3.8. Thuật toán xác định tidset các mục và tính twu của các giao dịch ..... 90 Hình 3.9. Thuật toán khai thác nhanh FWUI trên HQDB .................................. 92 Hình 3.10. So sánh thời gian trên CSDL SALE-FACT-1997 .............................. 96 Hình 3.11. So sánh thời gian trên CSDLSALE-FACT-1997+1998 ..................... 96 Hình 3.12. So sánh thời gian trên CSDL SALE-FACT-SYNC ............................ 97 Hình 3.13. So sánh thời gian trên CSDL SALE-FACT-1997 .............................. 98 Hình 3.14. So sánh thời gian trên CSDL SALE-FACT-1997+1998 .................... 98 Hình 3.15. So sánh thời gian trên CSDL SALE-FACT-SYNC ............................ 98 ix
DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT Stt Từ viết tắt Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt 1. CSDL Database Cơ sở dữ liệu 2. DBV Dynamic bit-vector Bit động 3. EDBV Extended dynamic bit-vector Bit động mở rộng 4. EIWS Extended interval word segment Các đoạn word mở rộng 5. FI Frequent itemset Tập mục phổ biến 6. FP-tree Frequent Pattern-Tree Cây FP Tập mục phổ biến có 7. FWI Frequent weighted itemset trọng số Tập mục phổ biến trọng 8. FWUI Frequent weighted utility itemset số hữu ích Hierarchical quantitative Cơ sở dữ liệu số lƣợng 9. HQDB database có sự phân cấp các mục 10. IT-tree Itemset tidset-tree Cây IT-tree 11. IWS Interval words segment Các đoạn word 12. MBiS Multi bits segment Các đoạn bit 1 liên tiếp 13. MByS Multi bytes segment Các đoạn byte 14. DTab Dynamic table Bảng động K nhóm tập mục phổ biến 15. TRFIk Top-rank-k frequent itemsets có thứ hạng cao nhất K nhóm tập mục phổ biến Top-rank-k frequent weight 16. TRFWUIk trọng số hữu ích có utility itemsets thứ hạng k cao nhất 17. DHeap Dynamic heap Heap động 18. Item Item Mục 19. Itemset Set of items Tập mục 20. LI Large integer Số nguyên lớn (tám byte) x
MỞ ĐẦU Sự phát triển mạnh mẽ của Công nghệ thông tin trong những năm gần đây đã thúc đẩy sự phát triển chung của toàn xã hội. Với các ứng dụng của Công nghệ thông tin, con ngƣời đã có những “trợ thủ” đắc lực hỗ trợ mình trong cuộc sống cũng nhƣ trong công việc. Công nghệ thông tin ứng dụng trong rất nhiều lĩnh vực đƣa đến sự tiện lợi và kết nối mọi ngƣời trên khắp thế giới lại với nhau. Các ứng dụng nhƣ ngân hàng điện tử, thƣơng mại điện tử, v.v… đã giúp cho con ngƣời tiết kiệm rất nhiều thời gian và công sức so với thao tác thủ công trƣớc đây. Trong những ứng dụng đó, thông tin, dữ liệu thƣờng xuyên đƣợc đƣa vào để các hệ thống thông tin lƣu trữ và xử lý. Bên cạnh đó, một số lƣợng lớn các dữ liệu đƣợc cập nhật hàng ngày và tự động lƣu trữ thông qua các hoạt động của con ngƣời khi tƣơng tác với các hệ thống thông tin, mạng xã hội, v.v… làm cho dữ liệu càng ngày càng lớn và phức tạp. Ngoài việc phục vụ cho các hệ thống thông tin hoạt động theo chức năng sẵn có thì một vấn đề đặt ra là làm sao có thể khai thác hiệu quả các loại dữ liệu lƣu trữ trong hệ thống, tìm ra các tri thức quan trọng, các quy luật của dữ liệu phục vụ cho việc đƣa ra các dự đoán, dự báo nhằm hỗ trợ ra quyết định và các nhu cầu liên quan khác. Ví dụ nhƣ từ cơ sở dữ liệu (CSDL) của hệ thống bán hàng trong siêu thị có thể tìm ra đƣợc quy luật (thói quen) mua hàng của các khách hàng. Khách hàng thƣờng mua các mặt hàng nào cùng với nhau? hay độ tuổi từ “A” đến “B” thƣờng ƣa thích mặt hàng nào?, v.v... Từ đó để giúp cho việc triển khai các kế hoạch phát triển sản phẩm hiệu quả hơn của các hệ thống bán hàng nhƣ trung tâm thƣơng mại, siêu thị, v.v… Khai thác tập mục phổ biến trên CSDL nhị phân Từ những yêu cầu thiết thực đó, lĩnh vực khai thác dữ liệu đã và đang đƣợc phát triển mạnh trong thời gian gần đây. Một trong những bài toán quan trọng trong khai thác dữ liệu đƣợc quan tâm nghiên cứu là khai thác tập mục phổ biến (frequent itemsets - FI), từ FI có thể khai thác luật kết hợp, đƣa ra 1
những dự báo, dự đoán và tìm ra quy luật của dữ liệu nhằm phục vụ cho các nhu cầu khác nhau của con ngƣời. Thuật toán đầu tiên đƣợc biết tới trong khai thác FI là đƣợc đề xuất bởi Agrawal và các đồng sự [2] năm 1993, sau đó chính Agrawal đề xuất thuật toán Apriori [1] năm 1994. Tuy nhiên thuật toán này sớm bộc lộ hạn chế về thời gian xử lý do đọc CSDL nhiều lần. Tiếp theo Han và các đồng sự đề xuất thuật toán FP-Growth [19] và Grahne cùng các đồng sự đề xuất FP-Growth* [18] dựa trên việc nén dữ liệu lên cây FP-tree (frequent pattern-tree) với chỉ hai lần đọc CSDL, đây là thuật toán hiệu quả về bộ nhớ sử dụng, song lại tốn thời gian cho duyệt cây FP-tree để khai thác các FI. Tiếp đến Zaki và các đồng sự đề xuất thuật toán Eclat [49] dựa trên cấu trúc IT-tree (Itemset Tidset-tree) với chỉ một lần đọc dữ liệu để chuyển CSDL ngang thành CSDL dọc với các mục và tidset (set of transaction identifiers - tập các giao dịch) của chúng. Tuy nhiên, Eclat có hạn chế là cần nhiều bộ nhớ để lƣu trữ tidset, do đó gián tiếp ảnh hƣởng đến hiệu quả về mặt thời gian của thuật toán này. Tiếp theo Zaki và các đồng sự [50] đề xuất cấu trúc diffset, với tƣ tƣởng sử dụng phần bù của tidset, nhƣng cách làm này chỉ thực sự có hiệu quả trên CSDL dày. Tuy nhiên, trong khi thực tế CSDL thƣa mới là loại CSDL phổ biến. Một số phát triển gần đây với cấu trúc N-list [8, 9,10,11,12, 17, 26, 40] là các nghiên cứu dựa trên tiếp cận lai ghép giữa FP-tree và định dạng dữ liệu dọc nhằm giảm bộ nhớ giúp cải tiến thời gian khai thác và bộ nhớ sử dụng. Tuy nhiên, các nghiên cứu này mới đề cập trên CSDL nhị phân, chƣa đƣợc nghiên cứu áp dụng trên CSDL số lƣợng, do đặc thù của CSDL số lƣợng cần tính trọng số các giao dịch của các tập mục để xác định độ hỗ trợ của các tập mục, mà đây là một khó khăn của tiếp cận dựa trên FP-tree. Khai thác tập mục phổ biến trên CSDL số lượng Các chủ đề nghiên cứu trên CSDL số lƣợng nhƣ khai thác tập mục phổ biến có trọng số (frequent weighted itemsets - FWI) [7, 22, 23, 32, 34, 37, 41, 42, 43, 44, 45, 46, 47, 48] hay khai thác tập mục phổ biến trọng số hữu ích 2
(frequent weighted utility itemsets - FWUI) [21, 39], hay tập mục hữu ích cao - (hight utility itemsets - HUIs) [14, 24, 25, 29] đã đƣợc quan tâm nghiên cứu. Rakumar và đồng sự [32] đề xuất bài toán khai thác luật kết hợp trọng số và một framework để khai thác FWI. Sau đó Tao và đồng sự [34] đề xuất thuật toán khai thác FWI dựa trên tiếp cận Apriori với hai độ đo trọng số giao dịch (transaction weight - tw) và độ hỗ trợ trọng số (weight support - ws), tuy nhiên nhƣ đã trình bày ở trên cách tiếp cận này rất tốn thời gian do quét CSDL nhiều lần. Tiếp đến, Vo và các đồng sự [37] đề xuất cấu trúc WIT-tree trong khai thác FWI và cấu trúc MWIT-tree [39] trong khai thác FWUI theo tiếp cận Eclat [49] với chỉ một lần quét CSDL. Hạn chế của các phƣơng pháp này là cần nhiều bộ nhớ lƣu trữ tidset của các tập mục bằng các danh sách, làm tốn thời gian xác định giao tidset của các tập mục. Một bài toán mới đƣợc đặt ra và phát triển gần đây trong khai thác FI là khai thác k nhóm tập mục phổ biến có thứ hạng cao nhất (Top-rank-k frequent itemset-TRFIk) [8, 11, 15, 26] Khai thác FI thông thƣờng không kiểm soát đƣợc số lƣợng các tập mục phổ biến tìm thấy. Trong nhiều trƣờng hợp chỉ cần quan tâm đến một số lƣợng nhất định các FI, hay số lƣợng các nhóm FI có độ hỗ trợ lớn nhất. Khai thác TRFIk giải quyết đƣợc đòi hỏi này. Bài toán khai thác TRFIk đã đƣợc Deng giới thiệu vào năm 2007 [8] với thuật toán FAE, sau đó đƣợc Fang đề xuất thuật toán VTK [17] để giải quyết. Tiếp theo, Deng [11] đề xuất thuật toán NTK dựa trên cây PPC-tree (Pre-order Post-order Code tree) và cấu trúc N-list. Gần đây, Le và các đồng sự [26] đề xuất thuật toán iNTK là một cải tiến của NTK. iNTK sử dụng cấu trúc N-list với khái niệm subsume đƣợc giới thiệu trong [40]. Đây đƣợc xem là thuật toán hiệu quả nhất cho đến hiện nay, mặc dù iNTK tốn thời gian cho việc tạo cây PPC- tree. Tuy nhiên, các nghiên cứu trên mới chỉ đề cập đến CSDL nhị phân, còn trên CSDL số lƣợng bài toán khai thác Top-rank-k vẫn chƣa đƣợc quan tâm nghiên cứu. 3
Khai thác tập mục phổ biến trên CSDL có sự phân cấp các mục Bên cạnh CSDL nhị phân và CSDL số lƣợng thì CSDL có sự phân cấp các mục là loại CSDL có nhiều trong ứng dụng thực tế. CSDL có sự phân cấp các mục là CSDL có thể hiện mối quan hệ khách quan giữa các mục dƣới dạng cây phân cấp, các mục có mặt trong CSDL là các mục ở nút lá của cây phân cấp. Năm 1995, Han và các đồng sự [20] lần đầu tiên đề cập tới bài toán khai thác FI trên CSDL có sự phân cấp các mục. Tiếp theo, Liu và các đồng sự [31] đề xuất bài toán khai thác FI với nhiều ngƣỡng hỗ trợ trên CSDL có sự phân cấp các mục, theo đó, mỗi mục có một ngƣỡng hỗ trợ riêng biệt. Từ đó đến nay đã có nhiều nghiên cứu liên quan đến bài toán này [4, 5, 6, 28, 30, 35, 36]. Tuy nhiên các tiếp cận hiện nay đối với khai thác trên CSDL có sự phân cấp các mục còn có nhiều hạn chế, trong đó đặc biệt là tốn thời gian và bộ nhớ để thêm các mục cha trên cây phân cấp vào CSDL. Ngoài ra các nghiên cứu hiện tại chƣa đề cập trên CSDL số lƣợng có sự phân cấp các mục. Động lực nghiên cứu của luận án Bài toán khai thác FI trên một số loại CSDL nhƣ đã phân tích ở trên mặc dù đã đƣợc quan tâm nghiên cứu nhiều, nhƣng cho đến hiện nay các phƣơng pháp khai thác FI trên các loại CSDL số lƣợng còn hạn chế là tốn bộ nhớ và thời gian xử lý chƣa đƣợc tối ƣu. Mặt khác, khai thác FI trên CSDL số lƣợng có sự phân cấp các mục hiện nay chƣa đƣợc quan tâm nghiên cứu, mặc dù đây là loại CSDL có nhiều trong các ứng dụng thực tế. Đồng thời, CSDL số lƣợng có sự phân cấp các mục là sự kết hợp giữa CSDL số lƣợng và CSDL có sự phân cấp các mục. Do đó, đề xuất thuật toán khai thác hiệu quả FI trên CSDL số lƣợng có sự phân cấp các mục có thể áp dụng để khai thác hiệu quả FI trên các CSDL số lƣợng và CSDL có sự phân cấp các mục, giúp cải thiện thời gian và bộ nhớ trong khai thác FI trên các hệ thống thông minh. 4
Trên cơ sở đó, Nghiên cứu sinh chọn đề tài “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” làm đề tài nghiên cứu cho luận án tiến sĩ của mình. Đối tượng và phạm vi nghiên cứu của luận án Đối tƣợng nghiên cứu là CSDL số lƣợng và CSDL số lƣợng có sự phân cấp mục. Phạm vi nghiên cứu của luận án là phát triển các thuật toán khai thác tập mục phổ biến ứng dụng trên CSDL số lƣợng và CSDL số lƣợng có sự phân cấp mục Mục tiêu của luận án như sau: i) Đối với các thuật toán hiện có trên CSDL số lƣợng, luận án nghiên cứu cách thức khai thác hiệu quả hơn bằng cách cải tiến theo hƣớng tiếp cận bit - vector. ii) Phát triển khái niệm CSDL số lƣợng có sự phân cấp mục và đề xuất phƣơng pháp khai thác mẫu trên CSDL số lƣợng có sự phân cấp mục. Luận án đạt được một số kết quả như sau: 1. Đề xuất một số cấu trúc dữ liệu mới, thuật toán mới để nâng cao hiệu quả khai thác FWI và FWUI trên CSDL số lượng. Từ đó áp dụng cho khai thác tập mục phổ biến trên CSDL số lượng có sự phân cấp các mục. 2. Đề xuất thuật toán hiệu quả để khai thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất trên CSDL số lượng. 3. Đề xuất cấu trúc dữ liệu, thuật toán hiệu quả để khai thác FWUI trên CSDL số lượng có sự phân cấp các mục. Cấu trúc luận án bao gồm năm phần, ngoài phần mở đầu và phần kết luận, nội dung luận án đƣợc trình bày trong ba chƣơng: Chương 1: “Tổng quan về khai thác tập mục” trình bày các khái niệm về khai thác FI các phƣơng pháp khai thác FI, FWI, FWUI và TRFIk. Phân tích ƣu điểm và hạn chế của các phƣơng pháp này đồng thời đề xuất hƣớng nghiên cứu của luận án. 5
Chương 2: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng” trình bày một số cấu trúc dữ liệu mới để biểu diễn tidset của các tập mục, trên cơ sở đó đề xuất các phƣơng pháp hiệu quả để khai thác nhanh FWI, FWUI trên CSDL số lƣợng. Đồng thời, trong chƣơng này cũng đề xuất bài toán khai thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất (TRFWUIk) trên CSDL số lƣợng và thuật toán hiệu quả để giải quyết bài toán này với hai cấu trúc DTab và DHeap. 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” đề xuất thuật toán khai thác FWUI trên CSDL số lƣợng có sự phân cấp các mục. Chƣơng này trình bày một mở rộng của cấu trúc dữ liệu trong chƣơng 2 và một số đề xuất nhằm cải tiến thuật toán khai thác hiệu quả FWUI trên CSDL số lƣợng có sự phân cấp các mục. 6
CHƢƠNG 1. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC Chƣơng này trình bày các nghiên cứu liên quan đến khai thác tập mục phổ biến trên các loại CSDL nhƣ CSDL nhị phân, CSDL số lƣợng, CSDL có sự phân cấp các mục và khai thác k nhóm tập phổ biến có thứ hạng cao nhất (Top-rank-k) từ các nhóm nghiên cứu trong nƣớc và quốc tế. Phần này cũng trình bày các phân tích về ƣu điểm và hạn chế của các phƣơng pháp khai thác tập mục phổ biến hiện có. Từ cơ sở đó luận án đề ra các thuật toán mới dựa trên các cấu trúc dữ liệu phù hợp hơn cho các bài toán này trong chƣơng 2 và 3 của luận án. 1.1. Bài toán khai thác tập mục Mục đích của việc khai thác tập mục là để xác định nhóm các mục (item) có tần suất xuất hiện thỏa mãn một ngƣỡng nào đó của ngƣời sử dụng đƣa vào. Trong đó, bài toán khai thác tập mục phổ biến là một bài toán con của bài toán khai thác tập mục với việc khai thác các tập mục có tần suất xuất hiện nhiều trong CSDL. Tần suất xuất hiện này thỏa mãn ngƣỡng do ngƣời sử dụng đƣa vào (đƣợc gọi là ngƣỡng phổ biến). Từ các FI khai thác đƣợc có thể sinh ra tập luật kết hợp nhằm khám phá mối quan hệ tiềm ẩn, hữu ích giữa các mục trong CSDL, phục vụ các yêu cầu xuất phát từ đòi hỏi của thực tế của ngƣời sử dụng. Có thể nói, từ khi đƣợc giới thiệu đến nay, đã có khá nhiều công trình nghiên cứu liên quan nhằm mục đích giải quyết tốt bài toán này. Hiện nay, bài toán khai thác tập mục đang đƣợc tiếp tục nghiên cứu để tìm ra các giải pháp hiệu quả hơn. Nội dung chƣơng 1 sẽ trình bày một số định nghĩa và khái niệm liên quan đến bài toán khai thác tập mục trên một CSDL nhƣ CSDL nhị phân, CSDL có sự phân cấp các mục, CSDL số lƣợng và một biến thể của CSDL số lƣợng là CSDL trọng số. Đồng thời chƣơng 1 giới thiệu tổng quát một số tiếp cận chính cho bài toán khai thác tập mục trên các loại CSDL đó. 7
1.1.1. Một số khái niệm cơ bản Định nghĩa 1.1. CSDL nhị phân (binary database) là một bộ gồm hai thành phần: T, I trong đó: T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ..., in} là tập gồm n mục trong CSDL Với giao dịch thứ k (k = 1..m): ={ } trong đó 0 hoặc 1, với j = Ví dụ 1.1: Cho CSDL DB với tập các mục I = {A, B, C, D, E} và tập các giao dịch T đƣợc biểu diễn bởi Bảng 1.1 nhƣ sau: Bảng 1.1. Các giao dịch của CSDL nhị phân DB Mục A B C D E Giao dịch t1 1 1 0 1 1 t2 0 1 1 1 0 t3 1 1 0 1 1 t4 1 1 1 0 1 t5 1 1 1 1 1 t6 0 1 1 0 1 Các mục xuất hiện trong một giao dịch của CSDL tƣơng ứng có giá trị 1, ngƣợc lại có giá trị 0. Ví dụ giao dịch t1 = {1, 1, 0, 1, 1} có nghĩa các mục A, B, D, E có trong giao dịch, mục C không có trong giao dịch. CSDL nhị phân là CSDL biểu diễn sự xuất hiện hay không của các mục trong các giao dịch. Trong nhiều trƣờng hợp, các mục trong CSDL có mối quan hệ với nhau đƣợc thể hiện qua các cây phân cấp, ví dụ "computer" là mức khái quát của "Desktop" và "Notebook", hay "Printer" là mức khái quát 8