Luận án tiến sĩ phát triển một số thuật toán hiệu quả khai thác tập mục trên 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 TIEU LUAN MOI download : skknchat@gmail.com ĐẠ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. NGUYỄN THỊ HỒNG MINH 2. 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.

Huỳnh Quyết Thắng Hà Nội - 2016 TIEU LUAN MOI download : skknchat@gmail.com 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 TIEU LUAN MOI download : skknchat@gmail.com 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.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.

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. Hồ Chí Minh, tháng năm 2016 ii TIEU LUAN MOI download : skknchat@gmail.com MỤC LỤC LỜI CAM ĐOAN. 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. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC. Bài toán khai thác tập mục.

Một số khái niệm cơ bản. Bài toán khai thác FI. Các phƣơng pháp khai thác FI. Phƣơng pháp khai thác FI trên CSDL ngang.

Phƣơng pháp khai thác FI trên CSDL dọc dựa trên IT-tree. Một số phƣơng pháp khai thác FWI và FWUI trên CSDL số lƣợng. Khai thác FWI. Khai thác FWUI.

Khai thác TRFIk. Khai thác FI trên CSDL có sự phân cấp các mục. Tiếp cận bit-vector trong khai thác FI. Kết luận chƣơng.

KHAI THÁC TẬP MỤC PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU SỐ LƢỢNG. Thuật toán khai thác tập FWI. Thuật toán tính giao của hai IWS. Thuật toán khai thác FWI.

Kết quả thực nghiệm. Thuật toán khai thác FWUI. Cấu trúc Multi bit segment. Thuật toán xác định giao MBiS.

Thuật toán khai thác FWUI dựa trên MBiS-tree. Kết quả thực nghiệm. 59 iii TIEU LUAN MOI download : skknchat@gmail. Thuật toán khai thác TRFWUIk.

Một số khái niệm. Cấu trúc DTab. Cấu trúc TR-tree. Thuật toán khai thác TRFWUIk sử dụng cấu trúc dữ liệu DTab.

Thuật toán khai thác nhanh TRFWUIk dựa trên cấu trúc DHeap. Kết quả thực nghiệm. Kết luận chƣơng. 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.

Giới thiệu bài toán. Thuật toán khai thác FWUI trên HQDB. Thuật toán xác định weight cho các mục cha. Thuật toán thêm mục cha vào CSDL.

Thuật toán khai thác FWUI. Một số cải tiến nâng cao hiệu quả khai thác FWUI trên HQDB. Cấu trúc EDBV. Tính tidset nút cha từ tidset nút con.

Kiểm tra mối quan hệ cha con đối với các mục trong tập mục. Thuật toán khai thác nhanh FWUI trên HQDB. Kết quả thực nghiệm. CSDL thực nghiệm.

Kết quả thực nghiệm. 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 TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC BẢNG Bảng 1. Các giao dịch của nhị phân DB. Các giao dịch của CSDL nhị phân có sự phân cấp mục DB. ID của các mục của DB.

Các giao dịch của DB bằng ID. Giao dịch của CSDL số lƣợng BD. Trọng số các mục của DB. Các giao dịch của CSDL trọng số DB.

Trọng số của các mục của DB. DB theo chiều dọc. Giá trị tw của CSDL DB trong ví dụ 1. twu các giao dịch của DB trong ví dụ 1.

DB trong Ví dụ 1.2 sau khi thêm mục cha. DBV của bit-vector trong ví dụ 2. IWS từ bit-vector trong ví dụ 2. Chỉ số các bit 1 của IWS(X).

IWS của các mục. Mô tả CSDL thực nghiệm. Bit-vector với 96 phần tử. MBiS từ bit-vector ở Bảng 2.

Giao dịch của HD. Tên mặt hàng của các mục. 77 v TIEU LUAN MOI download : skknchat@gmail. Giao dịch của HD.

twu của các giao dịch. Tập 1-itemset phổ biến. Mảng MAP với 65. Biểu diễn số nguyên K dƣới dạng bốn đoạn, mỗi đoạn là một word.

Mô tả CSDL. Các mức trên cây phân cấp. So sánh bộ nhớ và số lƣợng các mục. Thực nghiệm trên CSDL SALE-FACT-SYNC.

So sánh thời gian chạy trên CSDL SALE-FACT-1997. 99 vi TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1. Cây phân cấp Tr. Cây phân cấp Tr biểu diễn theo ID.

Thuật toán Apriori trong khai thác tập mục phổ biến. Thuật toán FP-Growth dựa trên cấu trúc FP-tree. Thuật toán Eclat dựa trên cấu trúc IT-tree. Cây IT tree với minsup = 0,5 của CSDL DB.

Thuật toán xác định giao hai IWS. Thuật toán tính ws của tập mục X. Thuật toán xây dựng cây IWS-tree. Thuật toán khai thác FWI dựa trên IWS-tree.

IWS-tree với nút A(minws = 0,4). IWS-tree với nútA vàB(minws = 0,4). IWS-tree với minws = 0,4. So sánh thời gian chạy với CSDL RETAIL.

So sánh thời gian chạy với CSDL BMS-POS. So sánh thời gian chạy với CSDL SALE-FACT-1997. So sánh thời gian chạy với CSDL SALE-FACT-1997+1998. So sánh thời gian chạy với CSDL SALE-FACT-SYNC.

So sánh thời gian chạy với CSDL CONNECT. So sánh thời gian chạy với CSDL ACCIDENTS. So sánh bộ nhớ sử dụng với CSDL RETAIL. So sánh bộ nhớ sử dụng với CSDL BMS-POS.

So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-1997+1998. 52 vii TIEU LUAN MOI download : skknchat@gmail. So sánh bộ nhớ sử dụng với CSDL SALE-FACT-SYNC.

So sánh bộ nhớ sử dụng với CSDL CONNECT. So sánh bộ nhớ sử dụng với CSDL ACCIDENT. Thuật toán xác định giao hai MBiS. Thuật toán tính wus dựa trên MBiS.

Thuật toán khai thác FWUI dựa trên MBiS-tree. So sánh thời gian chạy trên CSDL RETAIL. So sánh thời gian chạy trên CSDL BMS-POS. So sánh thời gian chạy trên CSDL SALE-FACT-1997.

So sánh thời gian chạy trên CSDL SALE-FACT-1997+1998. So sánh thời gian chạy trên CSDL SALE-FACT-SYNC. So sánh thời gian chạy trên CSDL CONNECT. So sánh thời gian chạy trên CSDL ACCIDENTS.

So sánh bộ nhớ sử dụng trên CSDL RETAIL. So sánh bộ nhớ sử dụng trên CSDL BMS-POS. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997. So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-1997+1998.

So sánh bộ nhớ sử dụng trên CSDL SALE-FACT-SYNC. So sánh bộ nhớ sử dụng trên CSDL CONNECT. So sánh bộ nhớ sử dụng trên CSDL ACCIDENT. Thuật toán tạo TR-tree sử dụng DTab.

Thuật toán lọc ra TRFWUIk. DHeap với k = 5 với CSDL trong ví dụ 1. Thuật toán tạo TR-tree sử dụng DHeap. 70 viii TIEU LUAN MOI download : skknchat@gmail.

Thuật toán lọc ra TRFWUIk. So sánh thời gian chạy trên CSDL MBS-POS. So sánh thời gian chạy trên CSDL RETAIL. So sánh thời gian chạy trên CSDL CONNECT.

So sánh thời gian trên CSDL SALE-FACT-1997. So sánh thời gian trên CSDL SALE-FACT-1997+1998. So sánh thời gian trên CSDL SALE-FACT-SYNC. Tập các cây phân cấp Tr.

Thuật toán tính weight cho các mục cha. Thuật toán thêm mục cha vào CSDL. Thuật toán khai thác FWUI từ HQDB. Cây HIT-tree với CSDL HD và minwus = 0,6.

Sử dụng các phép AND và dịch bit để tách các đoạn hai byte. Thuật toán tính nhanh wus của các tập mục. Thuật toán xác định tidset các mục và tính twu của các giao dịch. Thuật toán khai thác nhanh FWUI trên HQDB.

So sánh thời gian trên CSDL SALE-FACT-1997. So sánh thời gian trên CSDLSALE-FACT-1997+1998. So sánh thời gian trên CSDL SALE-FACT-SYNC. So sánh thời gian trên CSDL SALE-FACT-1997.

So sánh thời gian trên CSDL SALE-FACT-1997+1998. So sánh thời gian trên CSDL SALE-FACT-SYNC .