TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA CÔNG NGHỆ THÔNG TIN ĐỒ ÁN CUỐI KÌ MÔN PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning strategy Người hướng dẫn: GV NGUYỄN CHÍ THIỆN Người thực hiện: NGUYỄN TRIỆU VI – 52100143 TRẦN THÀNH ĐẠT – 52100879 Khoá : K25 THÀNH PHỐ HỒ CHÍ MINH, NĂM 2023 TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG KHOA CÔNG NGHỆ THÔNG TIN ĐỒ ÁN CUỐI KÌ MÔN PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning strategy Người hướng dẫn: GV NGUYỄN CHÍ THIỆN Người thực hiện: NGUYỄN TRIỆU VI TRẦN THÀNH ĐẠT Khoá : K25 THÀNH PHỐ HỒ CHÍ MINH, NĂM 2023 1 LỜI CẢM ƠN Chúng em xin gửi lời cảm ơn chân thành đến thầy cô đã hướng dẫn và hỗ trợ chúng em trong quá trình hoàn thành báo cáo môn học về Phân tích và thiết kế giải thuật. Sự kiên nhẫn và kiến thức của thầy đã giúp em nắm bắt một cái nhìn rõ ràng về chủ đề này. Em cũng xin cảm ơn bạn bè đã hỗ trợ trong suốt quá trình nghiên cứu và thảo luận. Lời cảm ơn này dành tặng thầy và các bạn đã đóng góp cho báo cáo này.
Chúng em xin chân thành cảm ơn. 2 ĐỒ ÁN ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG Tôi xin cam đoan đây là sản phẩm đồ án của riêng chúng tôi và được sự hướng dẫn của TS Nguyễn Chí Thiện;. Các nội dung nghiên cứu, kết quả trong đề tài này là trung thực và chưa công bố dưới bất kỳ hình thức nào trước đây. Những số liệu trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu tham khảo.
Ngoài ra, trong đồ án còn sử dụng một số nhận xét, đánh giá cũng như số liệu của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích nguồn gốc. Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội dung đồ án của mình. Trường đại học Tôn Đức Thắng không liên quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình thực hiện (nếu có). Hồ Chí Minh, ngày tháng năm Tác giả (ký tên và ghi rõ họ tên) Nguyễn Triệu Vi Thành Đạt 3 PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN Phần xác nhận của GV hướng dẫn _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ Tp.
Hồ Chí Minh, ngày tháng năm (kí và ghi họ tên) Phần đánh giá của GV chấm bài _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ _________________________________________________________ Tp. Hồ Chí Minh, ngày tháng năm (kí và ghi họ tên) 4 TÓM TẮT Nghiên cứu này tập trung vào bài toán khai thác các tập phổ biến trên cơ sở dữ liệu được đánh trọng số, với mục tiêu chính là phát triển thuật toán khai thác Top-rank- k tập phổ biến, tập trung vào việc xử lý dữ liệu có trọng số. Các thuật toán phổ biến như Apriori, FP-growth, Eclat và các phương pháp dựa trên cấu trúc N-list đã được đề xuất trước đó. Tuy nhiên, việc khai thác tập phổ biến tạo ra một lượng lớn các tập phổ biến, làm cho việc hiểu và khai thác các quy tắc trở nên khó khăn.
Một giải pháp cho vấn đề này là sử dụng biểu diễn rút gọn giảm kích thước tổng thể của bộ mẫu và quy tắc. Hai dạng biểu diễn chính là tập phổ biến đóng (FCIs) và tập phổ biến tối đa (MFIs). Một bộ sưu tập của FCIs hoặc MFIs có thể được sử dụng để suy luận tất cả các tập phổ biến. Số lượng FCIs hoặc MFIs ít hơn số lượng tập phổ biến, giảm thiểu không gian lưu trữ và yêu cầu thời gian tính toán.
Nghiên cứu này giới thiệu vấn đề khai thác Top-rank-k tập phổ biến, sử dụng hai cấu trúc dữ liệu tiên tiến là tidset và diffset. Ba thuật toán cơ bản cho vấn đề này được phát triển, bao gồm TFWIT, TFWID và TFWIN. TFWIT và TFWID sử dụng cấu trúc tidset và diffset để khai thác Top-rank-k tập phổ biến. Tuy nhiên, chúng chia sẻ hạn chế về nén dữ liệu, dẫn đến thời gian thực hiện lớn.
Do đó, thuật toán TFWIN (Top-rank-k tập phổ biến sử dụng cấu trúc N-list có trọng số) được phát triển. Nghiên cứu này áp dụng chiến lược cắt tỉa động vào thuật toán TFWIN để khai thác Top-rank- k tập phổ biến một cách hiệu quả hơn, từ đó đề xuất thuật toán TFWIN+. Cuối cùng, nghiên cứu tiến hành một thử nghiệm thực nghiệm để so sánh thời gian chạy và sử dụng bộ nhớ giữa các phương pháp thử nghiệm. Kết quả thử nghiệm chỉ ra rằng TFWIN+ là thuật toán tốt nhất cho việc khai thác Top-rank-k tập phổ biến.
5 MỤC LỤC LỜI CẢM ƠN.5 CHƯƠNG 1 – MỞ ĐẦU.7 CHƯƠNG 2 – TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT.1 Khai thác dữ liệu (Data mining).2 Khai phá luật kết hợp.2 Khai thác tập phổ biến (Mining frequent weighted itemset).2 Thuật toán Apriori.12 CHƯƠNG 3 – FREQUENT WEIGHTED ITEMSET.1 Định nghĩa về Top-rank-k tập được đánh trọng phổ biến:.4 CHƯƠNG 4 – TIDSET AND DIFFSET STRUCTURES FOR MINING FWIs.1 Cấu trúc Tidset và Diffset:.1 Cấu trúc Tidset.2 Cấu trúc Diffset.2 Thuật toán khai thác tập FWIs sử dụng cấu trúc Tidset và Diffset.9 CHƯƠNG 5 – WN-List structure for mining FWIs. Implement JAVA with TFWIN & TFWIN+.1 Định nghĩa cấu trúc WN-List:.2 Ví dụ cấu trúc WN-List:.3 Thuật toán TFWIN: Tìm kiếm tập FWIs xếp hạng thứ k sử dụng cấu trúc WN-list.1 Giới thiệu thuật toán & mã giả:.2 Triển khai thuật toán với Java:.3 Kết quả của thuật toán:.4 Phân tích độ phức tạp của thuật toán:.4 Thuật toán TFWIN+: Tìm kiếm tập FWIs xếp hạng thứ k sử dụng cấu trúc WN-list và chiến lược cắt tỉa sớm.1 Giới thiệu thuật toán & mã giả:.2 Triển khai thuật toán với Java:.3 Kết quả của thuật toán:.4 Phân tích độ phức tạp của thuật toán:.40 CHƯƠNG 6 – EMPIRICAL EVALUATION.44 7 CHƯƠNG 1 – MỞ ĐẦU 1.1 Đặt vấn đề Trong thời đại số hóa ngày nay, việc khai thác thông tin từ cơ sở dữ liệu đang trở thành một thách thức ngày càng lớn, đặc biệt là khi muốn tìm hiểu mối quan hệ giữa các sản phẩm trong danh mục có đánh trọng số. Điều này đặt ra câu hỏi về cách thức hiệu quả nhất để khai thác thông tin từ dữ liệu có tính chất này. Các thuật toán khai thác truyền thống như Apriori, FP-growth, và Eclat đã chứng minh được sự hiệu quả trong việc khai thác tập phổ biến từ cơ sở dữ liệu.
Tuy nhiên, khi dữ liệu được đánh trọng số, sự phức tạp tăng lên, đặt ra thách thức trong việc xử lý thông tin trọng số của từng sản phẩm một cách hiệu quả.2 Mục tiêu Để giải quyết vấn đề này, đề tài này tập trung vào bài toán khai thác Top-rank-k tập phổ biến từ cơ sở dữ liệu được đánh trọng số. Sự tiếp cận này đặt ra nhu cầu phát triển thuật toán mà không chỉ xử lý dữ liệu trọng số mà còn giảm thiểu lượng kết quả tạo ra, tăng tính hiệu quả trong việc hiểu và áp dụng thông tin. Để đối mặt với thách thức này, nghiên cứu giới thiệu hai cấu trúc dữ liệu tiên tiến là tidset và diffset. Bằng cách sử dụng những cấu trúc này, ba thuật toán cơ bản (TFWIT, TFWID, TFWIN, TFWIN+) được phát triển để khai thác Top-rank-k tập phổ biến.
Mục tiêu là vượt qua những hạn chế của các thuật toán truyền thống, đồng thời cải thiện thời gian thực hiện và khả năng nén dữ liệu. Những nghiên cứu này không chỉ đề cập đến vấn đề lý thuyết mà còn tập trung vào sự thực tế và tính ứng dụng của việc khai thác thông tin từ cơ sở dữ liệu có đánh trọng số. Kết quả của thử nghiệm thực nghiệm sẽ cung cấp cái nhìn rõ ràng về sự hiệu quả của các phương pháp đề xuất và mở ra hướng nghiên cứu tương lai trong lĩnh vực này. 8 CHƯƠNG 2 – TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT Tổng quan: Đề tài này tập trung vào lĩnh vực khai thác thông tin từ cơ sở dữ liệu có tính chất đặc biệt, khi dữ liệu được đánh trọng số.
Mục tiêu chính của nó là phát triển thuật toán khai thác Top-rank-k tập phổ biến, nơi tập trung vào xử lý thông tin có trọng số, giúp tìm ra những mẫu thông tin quan trọng mà không phải xử lý tất cả các kết quả có thể xuất hiện.1 Khai thác dữ liệu (Data mining) Data mining – khai phá dữ liệu là quá trình phân loại, sắp xếp các tập hợp dữ liệu nhất định để xác định xu hướng, các mẫu và thiết lập các mối liên hệ hữu ích nhằm giải quyết các vấn đề nhờ phân tích dữ liệu. Mục tiêu: cho phép các doanh nghiệp có thể dự đoán được xu hướng tương lai, nhằm đưa ra các quyết định được hỗ trợ dữ liệu từ các tập dữ liệu khổng lồ. Trọng số của một giao dịch được tính bằng trung bình của trọng số của các mục trong giao dịch đó. Mức hỗ trợ có trọng số của một tập mục (hoặc tập mục) được xác định bằng tỷ lệ của tổng trọng số của các giao dịch chứa tập mục đó trên tổng trọng số của tất cả các giao dịch.
Điều này giúp đo lường sự quan trọng của một tập mục cụ thể trong dữ liệu, đặc biệt khi dữ liệu có sự biến đổi về trọng số. Ví dụ: nếu bạn có một tập dữ liệu về mua sắm và mỗi sản phẩm có một trọng số dựa trên giá trị của nó, bạn có thể tính trọng số của mỗi giao dịch bằng cách lấy trung bình của trọng số của các sản phẩm trong giao dịch đó. Sau đó, mức hỗ trợ có trọng số cho một tập mục cụ thể sẽ đo lường mức độ phổ biến của tập mục đó trong các giao dịch dựa trên tổng trọng số của các giao dịch mà tập mục đó xuất hiện.2 Khai phá luật kết hợp 1.1 Định nghĩa Khai thác luật kết hợp là một phương pháp trong lĩnh vực khám phá tri thức từ dữ liệu (Knowledge Discovery in Databases - KDD). Nó nhằm mục đích tìm kiếm các mối quan hệ kết hợp giữa các mục (items) trong cơ sở dữ liệu.
Mục đích của luật kết hợp (Association Rule - AR) là tìm ra các mối quan hệ giữa các đối tượng trong khối lượng lớn dữ liệu.