Khai Thác Tập Phổ Biến Có Trọng Số: Phát Triển Thuật Toán Top-rank-k

Khám phá đồ án cuối kỳ về phân tích và thiết kế giải thuật khai thác tập hợp mục có trọng số, sử dụng cấu trúc danh sách và chiến lược cắt tỉa sớm.

• Đề tài: Khai Thác Tập Phổ Biến Có Trọng Số: Phát Triển Thuật Toán Top-rank-k

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
• TÓM TẮT
• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. Đặt vấn đề
• 1.2. Mục tiêu
• 2. CHƯƠNG 2: TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT
• 2.1. Khai thác dữ liệu (Data mining)
• 2.2. Khai phá luật kết hợp
• 2.2.1. Định nghĩa
• 2.3. Khai thác tập phổ biến (Mining frequent weighted itemset)
• 2.3.1. Thuật toán Apriori
• 3. CHƯƠNG 3: FREQUENT WEIGHTED ITEMSET
• 3.1. Định nghĩa về Top-rank-k tập được đánh trọng phổ biến
• 3.2. Ví dụ
• 4. CHƯƠNG 4: TIDSET AND DIFFSET STRUCTURES FOR MINING FWIs
• 4.1. Cấu trúc Tidset và Diffset
• 4.2. Thuật toán khai thác tập FWIs sử dụng cấu trúc Tidset và Diffset
• 5. CHƯƠNG 5: WN-LIST STRUCTURE FOR MINING FWIs. IMPLEMENT JAVA WITH TFWIN & TFWIN+
• 5.1. Định nghĩa cấu trúc WN-List
• 5.2. Ví dụ cấu trúc WN-List
• 5.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
• 5.3.1. Giới thiệu thuật toán TFWIN
• 5.3.2. Triển khai thuật toán với JAVA
• 5.3.3. Kết quả của thuật toán
• 5.3.4. Phân tích độ phức tạp của thuật toán
• 5.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
• 5.4.1. Giới thiệu thuật toán TFWIN+
• 5.4.2. Triển khai thuật toán với JAVA
• 5.4.3. Kết quả của thuật toán
• 5.4.4. Phân tích độ phức tạp của thuật toán
• 6. CHƯƠNG 6: EMPIRICAL EVALUATION

Tóm tắt

I. Tổng quan Khai Thác Tập Phổ Biến Top rank k có trọng số

Trong kỷ nguyên số, khai thác dữ liệu (data mining) đã trở thành một công cụ thiết yếu để khám phá tri thức ẩn sâu trong các bộ dữ liệu khổng lồ. Một trong những bài toán quan trọng nhất là khai thác mẫu phổ biến (frequent itemset mining), nhằm tìm ra các tập hợp mục xuất hiện cùng nhau một cách thường xuyên. Tuy nhiên, các phương pháp truyền thống thường bỏ qua một yếu tố quan trọng: trọng số của mỗi mục, chẳng hạn như giá trị, lợi nhuận hoặc tầm quan trọng. Điều này dẫn đến sự ra đời của bài toán khai thác tập phổ biến có trọng số, một phương pháp tiếp cận thực tế hơn, đặc biệt trong các lĩnh vực như phân tích giỏ hàng hay xây dựng hệ gợi ý. Nghiên cứu "Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning strategy" tập trung giải quyết một thách thức lớn hơn: làm thế nào để tìm ra các tập mục không chỉ phổ biến, có trọng số cao mà còn là những tập quan trọng nhất. Thay vì tạo ra hàng ngàn mẫu, cách tiếp cận top-k query chỉ tập trung vào k mẫu hàng đầu, giúp giảm thiểu nhiễu thông tin và cung cấp kết quả có giá trị hành động ngay lập tức. Mục tiêu là phát triển một thuật toán xếp hạng hiệu quả, có khả năng xử lý dữ liệu trọng số và trả về một tập kết quả tinh gọn, hữu ích, đáp ứng nhu cầu phân tích chuyên sâu.

1.1. Giới thiệu về khai thác dữ liệu và luật kết hợp

Khai phá dữ liệu là quá trình sàng lọc, phân tích các tập dữ liệu lớn để xác định các mẫu, xu hướng và mối quan hệ hữu ích. Một trong những kỹ thuật cốt lõi của data mining là khai thác luật kết hợp (association rule mining). Kỹ thuật này tìm kiếm các mối quan hệ dạng 'Nếu A thì B' trong dữ liệu. Ví dụ, trong bán lẻ, một luật có thể là '{Bơ} -> {Trứng}', cho thấy khách hàng mua bơ cũng có xu hướng mua trứng. Sức mạnh của một luật được đo bằng hai chỉ số chính: độ hỗ trợ (support) và độ tin cậy (confidence). Độ hỗ trợ cho biết tần suất xuất hiện của tập mục trong toàn bộ giao dịch, trong khi độ tin cậy đo lường xác suất xảy ra của vế phải khi vế trái đã xảy ra. Quá trình này giúp các doanh nghiệp đưa ra quyết định chiến lược, từ việc bố trí sản phẩm trên kệ hàng đến các chiến dịch tiếp thị chéo.

1.2. Khái niệm khai thác tập phổ biến có trọng số WAFIM

Mô hình khai thác mẫu phổ biến truyền thống coi tất cả các mục có tầm quan trọng như nhau. Tuy nhiên, trên thực tế, một sản phẩm có lợi nhuận cao nhưng ít được mua có thể quan trọng hơn một sản phẩm bán chạy nhưng lợi nhuận thấp. Weighted association rule mining (WAFIM) giải quyết vấn đề này bằng cách gán một trọng số cho mỗi mục. Trọng số có thể đại diện cho giá, lợi nhuận, hoặc bất kỳ thước đo giá trị nào khác. Thay vì chỉ đếm tần suất, WAFIM tính toán 'độ hỗ trợ có trọng số'. Theo tài liệu nghiên cứu, trọng số của một giao dịch được định nghĩa là trung bình trọng số của các mục trong giao dịch đó. Điều này cho phép các nhà phân tích tập trung vào các mẫu mang lại giá trị kinh doanh cao nhất, thay vì chỉ các mẫu phổ biến nhất. Đây là một bước tiến quan trọng so với các thuật toán Apriori hay thuật toán FP-Growth cổ điển.

1.3. Tầm quan trọng của truy vấn Top rank k trong phân tích

Một trong những thách thức lớn nhất của frequent itemset mining là 'sự bùng nổ mẫu', nơi thuật toán tạo ra một số lượng khổng lồ các tập phổ biến, gây khó khăn cho việc diễn giải và sử dụng. Cách tiếp cận top-k query là một giải pháp hiệu quả cho vấn đề này. Thay vì đặt ra một ngưỡng hỗ trợ tối thiểu (minsup) và lấy tất cả các mẫu vượt qua ngưỡng đó, thuật toán xếp hạng sẽ tìm và trả về chính xác k mẫu có thứ hạng cao nhất dựa trên một tiêu chí đo lường nhất định (ví dụ: độ hỗ trợ có trọng số). Điều này đảm bảo rằng người dùng chỉ nhận được những thông tin quan trọng và phù hợp nhất. Việc này không chỉ giúp tiết kiệm tài nguyên tính toán mà còn làm cho kết quả phân tích trở nên tinh gọn và dễ hành động hơn, đặc biệt hữu ích khi xây dựng các hệ gợi ý hoặc tối ưu hóa danh mục sản phẩm.

II. Thách thức trong Khai Thác Mẫu Phổ Biến và hạn chế cũ

Việc tìm kiếm các mẫu có giá trị trong cơ sở dữ liệu giao dịch là một bài toán phức tạp. Các thuật toán khai thác mẫu phổ biến truyền thống như thuật toán Apriori và thuật toán FP-Growth đã đặt nền móng vững chắc cho lĩnh vực này. Tuy nhiên, chúng bộc lộ nhiều hạn chế khi đối mặt với các bộ dữ liệu hiện đại, đặc biệt là dữ liệu có trọng số. Thử thách chính không chỉ nằm ở độ phức tạp thuật toán mà còn ở chất lượng và tính hữu dụng của kết quả đầu ra. Một vấn đề cố hữu là việc tạo ra một lượng lớn các mẫu, trong đó nhiều mẫu không mang lại giá trị thực tiễn. Hơn nữa, việc xác định một ngưỡng hỗ trợ tối thiểu (minsup) phù hợp là một công việc khó khăn và thường mang tính chủ quan. Một ngưỡng quá cao có thể bỏ lỡ các mẫu hiếm nhưng quan trọng, trong khi một ngưỡng quá thấp lại gây ra tình trạng bùng nổ mẫu. Khi yếu tố trọng số được đưa vào, các thuật toán này càng trở nên kém hiệu quả vì chúng không được thiết kế để ưu tiên các mẫu có giá trị cao. Nghiên cứu này chỉ ra rằng cần có một sự thay đổi trong phương pháp, hướng tới việc tối ưu hóa thuật toán để không chỉ tìm mẫu phổ biến mà còn xếp hạng chúng theo mức độ quan trọng thực tế.

2.1. Hạn chế của các phương pháp khai thác truyền thống

Các thuật toán kinh điển trong frequent itemset mining thường hoạt động dựa trên một ngưỡng hỗ trợ tối thiểu duy nhất. Điều này dẫn đến hai vấn đề chính. Thứ nhất, nếu ngưỡng này được đặt quá cao, các mẫu liên quan đến các mặt hàng hiếm nhưng có giá trị cao (ví dụ: đồ điện tử xa xỉ) sẽ bị bỏ qua. Ngược lại, một ngưỡng quá thấp sẽ tạo ra một số lượng mẫu khổng lồ, bao gồm nhiều mẫu không quan trọng (ví dụ: các mặt hàng thiết yếu giá rẻ), gây khó khăn cho việc phân tích. Các phương pháp này thiếu đi sự linh hoạt để phân biệt giữa 'phổ biến' và 'quan trọng'. Đây là điểm yếu chí mạng trong các ứng dụng như phân tích giỏ hàng, nơi mục tiêu là tối đa hóa lợi nhuận chứ không chỉ là số lượng bán ra.

2.2. Vấn đề bùng nổ mẫu và quá tải thông tin người dùng

Sự bùng nổ mẫu (pattern explosion) là hiện tượng khi một thuật toán khai thác dữ liệu tạo ra một số lượng mẫu lớn đến mức không thể quản lý được. Khi số lượng mục trong cơ sở dữ liệu tăng lên, số lượng tập mục tiềm năng tăng theo cấp số nhân, dẫn đến thời gian tính toán kéo dài và kết quả đầu ra cồng kềnh. Người phân tích cuối cùng bị quá tải với thông tin và không thể xác định được đâu là những insight thực sự giá trị. Để giải quyết vấn đề này, tài liệu gốc đề cập đến việc sử dụng các biểu diễn rút gọn như tập phổ biến đóng (FCIs) và tập phổ biến tối đa (MFIs). Tuy nhiên, cách tiếp cận top-k query được xem là một giải pháp trực tiếp và hiệu quả hơn, giúp người dùng tập trung ngay vào những mẫu quan trọng nhất mà không cần phải sàng lọc qua hàng ngàn kết quả không liên quan.

2.3. Tại sao thuật toán Apriori không đủ cho dữ liệu trọng số

Tư tưởng chính của thuật toán Apriori dựa trên nguyên tắc 'mọi tập con của một tập phổ biến cũng phải phổ biến'. Thuật toán này hoạt động tốt với dữ liệu giao dịch đơn giản, nơi mỗi mục được coi là ngang hàng. Tuy nhiên, nó không được thiết kế để xử lý trọng số. Khi áp dụng vào bài toán weighted association rule mining, Apriori không thể phân biệt được một tập mục gồm các sản phẩm lợi nhuận cao với một tập mục gồm các sản phẩm lợi nhuận thấp, miễn là chúng có cùng tần suất xuất hiện. Việc cố gắng sửa đổi Apriori để tích hợp trọng số thường dẫn đến độ phức tạp thuật toán tăng cao và mất đi tính hiệu quả vốn có. Điều này cho thấy sự cần thiết phải có các thuật toán được thiết kế chuyên biệt cho việc khai thác độ hữu dụng cao và dữ liệu có trọng số.

III. Phương pháp tiếp cận Top rank k Cấu trúc Tidset Diffset

Để giải quyết bài toán khai thác tập phổ biến có trọng số theo hướng top-k query, nghiên cứu đã đề xuất các thuật toán ban đầu dựa trên hai cấu trúc dữ liệu tiên tiến là Tidset và Diffset. Những cấu trúc này cho phép biểu diễn thông tin giao dịch một cách nhỏ gọn và hỗ trợ các phép toán kết hợp hiệu quả để tạo ra các tập mục ứng viên. Phương pháp này tập trung vào việc tính toán nhanh chóng độ hỗ trợ có trọng số của các tập mục mới mà không cần phải quét lại toàn bộ cơ sở dữ liệu. Dựa trên các cấu trúc này, hai thuật toán cơ bản là TFWIT (Top-rank-k Frequent Weighted Itemset mining using Tidset) và TFWID (sử dụng Diffset) đã được phát triển. Cả hai thuật toán đều tuân theo một chiến lược tìm kiếm theo chiều sâu, trong đó các tập mục được mở rộng dần và được xếp hạng dựa trên độ hỗ trợ có trọng số của chúng. Mặc dù các thuật toán này là một bước cải tiến so với các phương pháp truyền thống, nghiên cứu cũng chỉ ra rằng chúng vẫn còn hạn chế về khả năng nén dữ liệu, dẫn đến thời gian thực thi có thể còn lớn trên các tập dữ liệu dày đặc. Đây là tiền đề cho việc phát triển các phương pháp tối ưu hóa thuật toán cao cấp hơn.

3.1. Nguyên lý hoạt động của cấu trúc dữ liệu Tidset

Cấu trúc Tidset (Transaction ID set) là một phương pháp biểu diễn đơn giản nhưng hiệu quả. Đối với mỗi tập mục X, Tidset của nó, ký hiệu là t(X), là một danh sách chứa ID của tất cả các giao dịch có chứa tập mục X. Khi cần tạo một tập mục lớn hơn, ví dụ PXY từ PX và PY, Tidset của nó có thể được tính bằng phép giao của hai Tidset: t(PXY) = t(PX) ∩ t(PY). Từ Tidset kết quả, độ hỗ trợ có trọng số được tính bằng cách tổng hợp trọng số của các giao dịch tương ứng. Thuật toán TFWIT sử dụng cấu trúc này để duyệt qua không gian tìm kiếm. Ưu điểm của Tidset là tính trực quan và dễ triển khai. Tuy nhiên, khi các tập mục trở nên phổ biến, danh sách ID giao dịch có thể rất dài, gây tốn bộ nhớ và làm chậm các phép toán giao.

3.2. Khai thác hiệu quả với cấu trúc dữ liệu Diffset

Để khắc phục nhược điểm về bộ nhớ của Tidset, cấu trúc Diffset (Difference set) được giới thiệu. Thay vì lưu toàn bộ danh sách ID giao dịch, Diffset chỉ lưu sự khác biệt về ID giao dịch giữa hai tập mục trong cùng một lớp tương đương. Cụ thể, d(PXY) = t(PX) \ t(PY). Bằng cách này, độ hỗ trợ có trọng số của tập mục mới PXY có thể được tính toán một cách hiệu quả từ độ hỗ trợ của PX và tổng trọng số của các giao dịch trong Diffset. Thuật toán TFWID được xây dựng dựa trên nguyên lý này. Diffset đặc biệt hiệu quả khi các tập mục có mức độ tương đồng cao, vì khi đó danh sách khác biệt sẽ rất ngắn. Tuy nhiên, nó vẫn có thể gặp vấn đề về hiệu năng trên các bộ dữ liệu thưa, nơi sự khác biệt giữa các Tidset là rất lớn.

3.3. Phân tích thuật toán TFWIT và TFWID trong thực tế

Cả TFWIT và TFWID đều là những nỗ lực ban đầu để xây dựng một thuật toán xếp hạng cho bài toán top-k query trong khai thác tập phổ biến có trọng số. Chúng đặt nền móng bằng cách sử dụng các cấu trúc dữ liệu thông minh để tránh quét lại cơ sở dữ liệu nhiều lần. Tuy nhiên, như tóm tắt của tài liệu đã chỉ ra, cả hai thuật toán này 'chia sẻ hạn chế về nén dữ liệu, dẫn đến thời gian thực hiện lớn'. Điều này có nghĩa là mặc dù chúng tốt hơn các phương pháp truyền thống, chúng vẫn chưa phải là giải pháp tối ưu nhất. Các thử nghiệm thực nghiệm cho thấy hiệu suất của chúng giảm sút khi xử lý các bộ dữ liệu lớn và dày đặc. Sự tồn tại của những hạn chế này đã thúc đẩy việc tìm kiếm một cấu trúc dữ liệu hiệu quả hơn, dẫn đến sự ra đời của WN-List.

IV. Hướng dẫn tối ưu thuật toán Top rank k với cấu trúc WN List

Để vượt qua những hạn chế của Tidset và Diffset, nghiên cứu đã đề xuất một giải pháp đột phá dựa trên cấu trúc dữ liệu cây có tên là WN-Tree và biểu diễn tương ứng của nó là WN-List. Đây là trọng tâm của việc tối ưu hóa thuật toán để khai thác tập phổ biến có trọng số một cách hiệu quả. WN-Tree là một biến thể của các cấu trúc cây nén như FP-Tree, được thiết kế đặc biệt để lưu trữ thông tin về trọng số giao dịch. Từ cây này, cấu trúc WN-List được trích xuất cho mỗi mục. WN-List là một danh sách các mã WN-code, mỗi mã chứa thông tin về vị trí (pre-value, post-value) và trọng số của một nút trên cây. Cấu trúc này không chỉ nén dữ liệu hiệu quả mà còn cho phép tính toán độ hỗ trợ của các tập mục mới một cách nhanh chóng thông qua các phép toán kết hợp trên danh sách. Dựa trên WN-List, thuật toán TFWIN (Top-rank-k Frequent Weighted Itemset mining using WN-list) được phát triển, mang lại hiệu suất vượt trội. Hơn thế nữa, phiên bản cải tiến TFWIN+ còn tích hợp một chiến lược cắt tỉa sớm, giúp giảm đáng kể không gian tìm kiếm và nâng cao tốc độ thực thi.

4.1. Giới thiệu cấu trúc dữ liệu cây WN Tree và WN List

WN-Tree là một cấu trúc dữ liệu cây được xây dựng bằng cách quét cơ sở dữ liệu hai lần. Lần đầu để xác định các mục phổ biến có trọng số và sắp xếp chúng. Lần thứ hai để chèn từng giao dịch đã được sắp xếp vào cây. Mỗi nút trên cây đại diện cho một mục và lưu trữ tổng trọng số của các giao dịch đi qua nó. Sau khi cây được xây dựng hoàn chỉnh, thuật toán sẽ duyệt cây để gán cho mỗi nút một cặp giá trị (pre, pos), đánh dấu thứ tự duyệt của nút. WN-List của một mục sau đó được định nghĩa là một danh sách các bộ ba (pre, pos, weight) của tất cả các nút đại diện cho mục đó trên cây. Cấu trúc này nén gọn toàn bộ thông tin cần thiết từ cơ sở dữ liệu vào một dạng thức tối ưu cho việc khai thác.

4.2. Cách thuật toán TFWIN cải thiện hiệu suất khai thác

Thuật toán TFWIN khai thác sức mạnh của WN-List để thực hiện quá trình tìm kiếm. Thay vì thực hiện các phép giao trên các danh sách ID giao dịch dài, TFWIN thực hiện các phép toán kết hợp trên các WN-List ngắn gọn hơn. Việc tính toán độ hỗ trợ của một tập mục mới được thực hiện bằng cách tìm các WN-code tương ứng trong các WN-List của các mục thành phần. Nhờ vào thông tin vị trí (pre, pos), thuật toán có thể nhanh chóng xác định các mối quan hệ cha-con trên cây, tương ứng với sự xuất hiện đồng thời của các mục trong cùng một giao dịch. Điều này giúp giảm đáng kể độ phức tạp thuật toán so với các phương pháp dựa trên Tidset/Diffset, đặc biệt là trên các bộ dữ liệu lớn.

4.3. Chiến lược cắt tỉa sớm trong thuật toán TFWIN

TFWIN+ là một bước tối ưu hóa thuật toán quan trọng hơn nữa. Nó tích hợp một 'chiến lược cắt tỉa động' (early pruning strategy) vào TFWIN. Trong quá trình tìm kiếm, thuật toán duy trì một danh sách k tập mục có trọng số cao nhất được tìm thấy cho đến thời điểm hiện tại. Trước khi mở rộng một tập mục ứng viên mới, thuật toán sẽ tính toán một giới hạn trên cho độ hỗ trợ có trọng số mà bất kỳ siêu tập nào của nó có thể đạt được. Nếu giới hạn trên này thấp hơn độ hỗ trợ của tập mục đứng thứ k trong danh sách hiện tại, toàn bộ nhánh tìm kiếm bắt nguồn từ tập mục ứng viên đó sẽ bị cắt bỏ. Chiến lược này giúp loại bỏ một cách an toàn một lượng lớn các tính toán không cần thiết, giúp TFWIN+ đạt được hiệu suất vượt trội, trở thành thuật toán tốt nhất trong số các phương pháp được đề xuất.

V. Ứng dụng thuật toán Top rank k Phân tích giỏ hàng hiệu quả

Sự phát triển của các thuật toán xếp hạng như TFWIN+ không chỉ là một thành tựu lý thuyết mà còn mang lại giá trị ứng dụng thực tiễn to lớn. Một trong những lĩnh vực hưởng lợi trực tiếp nhất là phân tích giỏ hàng (market basket analysis). Thay vì chỉ tìm ra các sản phẩm thường được mua cùng nhau, doanh nghiệp giờ đây có thể xác định các bộ sản phẩm có giá trị hoặc lợi nhuận cao nhất thường được mua chung. Điều này cho phép họ thiết kế các chương trình khuyến mãi, bán chéo (cross-selling) và bán thêm (up-selling) một cách thông minh và hiệu quả hơn. Một ứng dụng quan trọng khác là trong việc xây dựng các hệ gợi ý (recommender systems). Bằng cách phân tích các tập mục có trọng số cao nhất, hệ thống có thể đề xuất cho người dùng những sản phẩm không chỉ liên quan mà còn có khả năng mang lại giá trị cao, cải thiện cả trải nghiệm khách hàng và doanh thu. Kết quả đánh giá thực nghiệm được trình bày trong nghiên cứu đã chứng minh tính vượt trội của TFWIN+, cho thấy nó không chỉ nhanh hơn mà còn sử dụng ít bộ nhớ hơn so với các thuật toán TFWIT và TFWID, khẳng định tiềm năng ứng dụng rộng rãi của nó.

5.1. Cải thiện phân tích giỏ hàng với tập có trọng số

Trong phân tích giỏ hàng truyền thống, một quy tắc như '{Bánh mì, Sữa} -> {Bơ}' có thể rất phổ biến. Tuy nhiên, nếu lợi nhuận từ ba mặt hàng này đều thấp, quy tắc này không mang lại nhiều giá trị chiến lược. Với phương pháp khai thác tập phổ biến có trọng số, một nhà bán lẻ có thể phát hiện ra một quy tắc ít phổ biến hơn nhưng giá trị hơn nhiều, chẳng hạn như '{Rượu vang, Phô mai nhập khẩu} -> {Thịt nguội cao cấp}'. Bằng cách tập trung vào top-k các mẫu có trọng số cao nhất, doanh nghiệp có thể xác định chính xác các 'giỏ hàng vàng' và xây dựng các chiến lược kinh doanh xoay quanh chúng, từ việc sắp xếp các sản phẩm này gần nhau đến việc tạo ra các gói combo hấp dẫn.

5.2. Xây dựng hệ gợi ý chính xác hơn từ dữ liệu trọng số

Các hệ gợi ý hiện đại đóng vai trò quan trọng trong thương mại điện tử. Một hệ thống gợi ý hiệu quả có thể tăng đáng kể tỷ lệ chuyển đổi và giá trị đơn hàng trung bình. Bằng cách sử dụng các thuật toán top-k query trên dữ liệu có trọng số, hệ thống có thể vượt ra ngoài việc chỉ gợi ý các sản phẩm tương tự hoặc thường được mua cùng nhau. Nó có thể ưu tiên gợi ý các sản phẩm có khả năng được mua và đồng thời mang lại lợi nhuận cao cho công ty. Ví dụ, khi khách hàng mua một chiếc máy ảnh, thay vì chỉ gợi ý thẻ nhớ (phổ biến, lợi nhuận thấp), hệ thống có thể gợi ý một ống kính tương thích (ít phổ biến hơn, lợi nhuận cao), từ đó tối ưu hóa cơ hội doanh thu.

5.3. Đánh giá thực nghiệm và so sánh hiệu năng của TFWIN

Phần cuối cùng của nghiên cứu tập trung vào đánh giá thực nghiệm để xác thực hiệu quả của các thuật toán được đề xuất. Theo kết quả được báo cáo, thuật toán TFWIN+ thể hiện sự vượt trội rõ rệt so với TFWIT, TFWID và TFWIN. Nó không chỉ cho thời gian chạy nhanh hơn đáng kể mà còn yêu cầu ít bộ nhớ hơn. Điều này là nhờ vào sự kết hợp giữa hiệu quả nén dữ liệu của cấu trúc dữ liệu cây WN-List và sức mạnh của chiến lược cắt tỉa sớm. Kết quả thực nghiệm này là một minh chứng mạnh mẽ, khẳng định rằng TFWIN+ là một giải pháp hiệu quả và khả thi cho bài toán khai thác tập phổ biến có trọng số top-rank-k trong các ứng dụng thực tế.

VI. Tương lai của Khai Thác Dữ Liệu Xu hướng và Triển vọng

Nghiên cứu về thuật toán Top-rank-k cho tập phổ biến có trọng số đã mở ra một hướng đi mới đầy hứa hẹn trong lĩnh vực khai thác dữ liệu. Nó đánh dấu sự chuyển dịch từ việc tìm kiếm 'tất cả các mẫu' sang việc tìm kiếm 'các mẫu tốt nhất'. Cách tiếp cận này không chỉ giải quyết các vấn đề cố hữu như bùng nổ mẫu và quá tải thông tin mà còn làm cho kết quả phân tích trở nên phù hợp và có giá trị hơn trong bối cảnh kinh doanh. Tương lai của data mining sẽ tiếp tục chứng kiến sự phát triển của các thuật toán xếp hạng thông minh hơn, có khả năng xử lý các loại dữ liệu phức tạp hơn như dữ liệu chuỗi, dữ liệu đồ thị và dữ liệu dòng. Hướng phát triển của weighted association rule mining có thể bao gồm việc tích hợp các yếu tố khác như thời gian, vị trí, hoặc cảm xúc của khách hàng để tạo ra những insight sâu sắc và đa chiều hơn. Việc tối ưu hóa thuật toán sẽ luôn là một ưu tiên hàng đầu, nhằm đáp ứng nhu cầu xử lý các bộ dữ liệu ngày càng lớn với tốc độ nhanh hơn và hiệu quả cao hơn, thúc đẩy sự đổi mới trong nhiều ngành công nghiệp.

6.1. Tóm tắt ưu điểm của phương pháp khai thác top rank k

Phương pháp khai thác top-rank-k mang lại nhiều lợi ích vượt trội. Thứ nhất, nó tạo ra một tập kết quả nhỏ gọn và tập trung, giúp người dùng dễ dàng diễn giải và hành động. Thứ hai, nó loại bỏ sự cần thiết phải phỏng đoán một ngưỡng hỗ trợ tối thiểu phù hợp. Thứ ba, bằng cách tập trung vào các mẫu hàng đầu, nó tự nhiên ưu tiên các kết quả có ý nghĩa nhất, đặc biệt là khi kết hợp với trọng số. Cuối cùng, các thuật toán được tối ưu hóa cho top-k, như TFWIN+, có thể hiệu quả hơn về mặt tính toán so với việc tìm kiếm toàn bộ các mẫu phổ biến. Những ưu điểm này làm cho nó trở thành một công cụ mạnh mẽ cho các nhà phân tích dữ liệu hiện đại.

6.2. Hướng phát triển cho các thuật toán xếp hạng tương lai

Trong tương lai, các thuật toán xếp hạng có thể được phát triển để trở nên linh hoạt hơn. Thay vì chỉ sử dụng một thước đo xếp hạng duy nhất (như độ hỗ trợ có trọng số), chúng có thể cho phép người dùng định nghĩa các hàm xếp hạng đa tiêu chí, kết hợp nhiều yếu tố như lợi nhuận, tần suất, độ mới, và mức độ phù hợp. Hơn nữa, việc phát triển các thuật toán có khả năng hoạt động trên môi trường phân tán (distributed computing) sẽ rất quan trọng để xử lý các bộ dữ liệu ở quy mô web. Tối ưu hóa thuật toán cho các kiến trúc phần cứng mới như GPU cũng là một lĩnh vực nghiên cứu đầy tiềm năng để tăng tốc độ khai thác.

6.3. Tiềm năng mở rộng của weighted association rule mining

Lĩnh vực weighted association rule mining vẫn còn nhiều không gian để phát triển. Một hướng đi tiềm năng là khai thác độ hữu dụng cao (high-utility itemset mining), một bài toán tổng quát hơn, nơi không chỉ xem xét trọng số của từng mục mà còn cả số lượng của chúng trong mỗi giao dịch. Ngoài ra, việc áp dụng các kỹ thuật này vào các lĩnh vực mới ngoài bán lẻ, chẳng hạn như phân tích văn bản (tìm các cụm từ quan trọng), tin sinh học (tìm các mẫu gen có ý nghĩa), hay phân tích web (tìm các hành trình người dùng có giá trị), sẽ mở ra nhiều ứng dụng mới và thú vị. Sự kết hợp giữa dữ liệu có trọng số và các kỹ thuật học máy tiên tiến hứa hẹn sẽ mang lại những khám phá đột phá trong tương lai.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong lĩnh vực khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases - KDD), khai thác tập phổ biến (Frequent Itemset Mining - FIM) đóng vai trò nền tảng cho nhiều bài toán phân tích dữ liệu thực tế như phân tích giỏ hàng (Market Basket Analysis), tiếp thị chéo, hệ thống khuyến nghị và tối ưu hóa quản lý kho hàng. Các thuật toán truyền thống tiêu biểu như Apriori (Agrawal & Srikant, 1994), FP-growth (Han et al., 2000) và Eclat/IT-tree (Zaki et al.) giả định rằng mọi hạng mục (item) đều có tầm quan trọng tương đương nhau và chỉ xuất hiện dưới dạng nhị phân (có hoặc không có trong giao dịch).

Tuy nhiên, trong các bài toán thực tế, mỗi sản phẩm hoặc đối tượng dữ liệu đều mang giá trị, lợi nhuận hoặc mức độ quan trọng khác nhau, được biểu diễn thông qua trọng số (weight). Khi đưa trọng số vào mô hình, thuộc tính giảm đơn điệu (anti-monotonic property) của độ hỗ trợ truyền thống không còn được duy trì trực tiếp theo cách cũ. Đồng thời, việc khai thác tập phổ biến thông thường tạo ra số lượng mẫu khổng lồ, khiến việc trích xuất và phân tích các quy tắc hữu ích gặp nhiều khó khăn về mặt tính toán và không gian lưu trữ.

Đồ án "Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning strategy" do sinh viên Nguyễn Triệu Vi và Trần Thành Đạt (Khóa K25, Khoa Công nghệ Thông tin, Trường Đại học Tôn Đức Thắng) thực hiện dưới sự hướng dẫn của TS. Nguyễn Chí Thiện nhằm giải quyết các thách thức trên.

Mục tiêu và nhiệm vụ nghiên cứu cụ thể bao gồm:

1. Nghiên cứu cơ sở lý thuyết về khai thác tập phổ biến có trọng số (Frequent Weighted Itemsets - FWIs) và bài toán tìm kiếm Top-rank-$k$ tập phổ biến có trọng số.
2. Xây dựng và đánh giá các thuật toán khai thác Top-rank-$k$ FWIs dựa trên các cấu trúc dữ liệu dạng danh sách giao dịch gồm Tidset (thuật toán TFWIT) và Diffset (thuật toán TFWID).
3. Đề xuất cấu trúc danh sách nút có trọng số (WN-list) được trích xuất từ cây WN-tree để nén dữ liệu và phát triển thuật toán TFWIN.
4. Tích hợp chiến lược cắt tỉa động sớm (early pruning strategy) vào thuật toán TFWIN để xây dựng thuật toán cải tiến TFWIN+, nhằm tối ưu hóa thời gian thực thi và mức độ tiêu thụ bộ nhớ.
5. Cài đặt các thuật toán bằng ngôn ngữ Java và tiến hành thử nghiệm thực nghiệm để so sánh hiệu năng giữa các giải pháp.

Phạm vi nghiên cứu tập trung vào cơ sở dữ liệu giao dịch có gắn trọng số cho từng hạng mục (item weight), xác định các tập mục có thứ hạng trọng số hỗ trợ nằm trong nhóm $k$ mức cao nhất (Top-rank-$k$) mà không xét đến số lượng mua chi tiết của từng mục trong một giao dịch đơn lẻ.

---

Cơ sở lý thuyết và phương pháp

Khung lý thuyết và mô hình toán học

Mô hình khai thác tập phổ biến có trọng số trong đề tài được xây dựng trên các định nghĩa và công thức toán học xác thực:

• Cơ sở dữ liệu giao dịch có trọng số ($WD$): Gồm tập giao dịch $T = {t_1, t_2, \dots, t_m}$, tập hạng mục $I = {i_1, i_2, \dots, i_n}$ và tập trọng số tương ứng $W = {w_1, w_2, \dots, w_n}$, trong đó mỗi $w_i \in (0, 1]$ đại diện cho tầm quan trọng hoặc lợi nhuận của hạng mục $i$.
• Trọng số của một giao dịch ($tw$): Trọng số của giao dịch $t_k$ được tính bằng giá trị trung bình cộng của trọng số các hạng mục xuất hiện trong giao dịch đó: $$tw(t_k) = \frac{\sum_{i \in t_k} w_i}{|t_k|}$$
• Tổng trọng số toàn bộ cơ sở dữ liệu ($TTW$): $$TTW = \sum_{t_k \in T} tw(t_k)$$
• Độ hỗ trợ có trọng số của tập mục $X$ ($ws(X)$): Tỷ lệ giữa tổng trọng số của các giao dịch chứa tập mục $X$ (ký hiệu $t(X)$) trên tổng trọng số $TTW$: $$ws(X) = \frac{\sum_{t \in t(X)} tw(t)}{TTW}$$
• Tập phổ biến có trọng số (FWI): Một tập mục $X \subseteq I$ được xem là một FWI nếu $ws(X) \ge minws$, với $minws$ là ngưỡng trọng số hỗ trợ tối thiểu.
• Thứ hạng của tập mục ($RX$): Rank của tập $X$ ($RX$) được định nghĩa bằng số lượng các giá trị trọng số hỗ trợ phân biệt của các tập mục khác lớn hơn hoặc bằng $ws(X)$. Tập $X$ thuộc nhóm Top-rank-$k$ nếu $RX \le k$.

Phương pháp nghiên cứu

Nghiên cứu áp dụng phương pháp thiết kế và phân tích thuật toán kết hợp với thực nghiệm kiểm chứng:

• Phương pháp phân tích lý thuyết: Phân tích độ phức tạp không gian và thời gian của các cấu trúc dữ liệu dạng danh sách (Tidset, Diffset, WN-list) và cơ chế sinh tập ứng viên theo lớp tương đương (equivalence class).
• Phương pháp thiết kế hệ thống và thuật toán: Phát triển mã giả, đặc tả giải thuật và xây dựng chiến lược cắt tỉa sớm dựa trên cận trên của độ hỗ trợ trọng số.
• Phương pháp thực nghiệm: Triển khai mã nguồn độc lập bằng ngôn ngữ lập trình Java, tiến hành chạy thử nghiệm trên cùng một tập dữ liệu chuẩn để đo lường hai chỉ số chính: thời gian thực thi (tính bằng mili-giây - ms) và bộ nhớ tiêu thụ cực đại (tính bằng Megabyte - MB).

---

Nội dung chính theo từng chương

Chương 1: Mở đầu

Chương này trình bày bối cảnh chuyển đổi số và sự gia tăng quy mô dữ liệu giao dịch trong thực tế. Tác giả phân tích hạn chế của các giải pháp khai thác tập phổ biến truyền thống khi áp dụng vào dữ liệu có trọng số, đồng thời xác lập mục tiêu nghiên cứu là phát triển các thuật toán khai thác Top-rank-$k$ tập phổ biến có trọng số (TFWIT, TFWID, TFWIN, TFWIN+) nhằm tối ưu hóa hiệu năng và giảm bớt số lượng mẫu dư thừa.

Chương 2: Tổng quan và cơ sở lý thuyết

Chương 2 hệ thống hóa các khái niệm nền tảng trong khai phá dữ liệu và khai phá luật kết hợp (Association Rules). Các thước đo cơ bản gồm Support ($\sigma$), Confidence ($Conf(X \to Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}$), ngưỡng $minsup$ và $minconf$ được giải thích chi tiết kèm ví dụ minh họa từng bước sinh tập phổ biến theo thuật toán Apriori (từ tập 1-itemset $L_1$ đến 4-itemset $L_4$). Chương này cũng nêu ứng dụng thực tiễn của bài toán trong phân tích giỏ hàng, tiếp thị chéo và bố trí sản phẩm.

Chương 3: Frequent Weighted Itemset

Chương này tập trung xây dựng nền tảng toán học cho bài toán khai thác tập phổ biến có trọng số và bài toán xếp hạng Top-rank-$k$. Nội dung trình bày chi tiết cách thức tính toán trọng số giao dịch $tw(t_k)$, tổng trọng số $TTW$, độ hỗ trợ có trọng số $ws(X)$ và định nghĩa chính xác về Rank ($RX$). Tác giả đưa ra ví dụ minh họa bằng số liệu cụ thể gồm 5 giao dịch và 6 hạng mục ($i_1$ đến $i_6$) với vector trọng số tương ứng, chứng minh từng bước tính toán chỉ số $TTW = 1.82$ và $ws(i_4) = 0.73$.

Chương 4: Tidset and Diffset Structures for Mining FWIs

Chương 4 nghiên cứu việc áp dụng hai cấu trúc dữ liệu dạng dọc (vertical data formats) vào bài toán FWIs:

• Cấu trúc Tidset: Lưu danh sách các mã giao dịch chứa tập mục. Phép giao hai tập tiền tố chung $PX$ và $PY$ được xác định qua $t(PXY) = t(PX) \cap t(PY)$.
• Cấu trúc Diffset: Chỉ lưu sự khác biệt về mã giao dịch giữa hai tập mục $d(PXY) = d(PY) \setminus d(PX)$, giúp tiết kiệm bộ nhớ khi tập mục có độ dài lớn.
• Thuật toán TFWIT và TFWID: Đặc tả thuật toán và phương thức sinh ứng viên (TFWIT_CandidateGen, TFWID_CandidateGen) kết hợp kỹ thuật duyệt theo lớp tương đương và sắp xếp danh sách ứng viên theo thứ tự tăng dần của $ws$.

Chương 5: WN-List Structure for Mining FWIs. Implement JAVA with TFWIN & TFWIN+

Chương này giới thiệu cấu trúc WN-tree và WN-list:

• WN-tree và WN-code: Cây WN-Tree được xây dựng từ tập dữ liệu có trọng số sau khi loại bỏ các mục không phổ biến. Mỗi nút trên cây được gán một bộ ba mã định danh $WN\text{-}code = (pre, post, weight)$, trong đó $pre$ và $post$ là thứ tự duyệt cây theo chiều trước và chiều sau, còn $weight$ là tổng $tw$ của các giao dịch đi qua nút đó.
• Cấu trúc WN-list: Danh sách các WN-code của một hạng mục sắp xếp tăng dần theo giá trị $pre$.
• Thuật toán TFWIN: Khai thác Top-rank-$k$ FWIs trực tiếp trên WN-list thông qua phép giao danh sách nút mà không cần duyệt lại cơ sở dữ liệu.
• Thuật toán TFWIN+: Tích hợp chiến lược cắt tỉa động sớm (early pruning) nhằm loại bỏ ngay các nhánh không thỏa mãn điều kiện lọt vào nhóm $k$ thứ hạng cao nhất trước khi sinh ứng viên mức cao hơn.
• Toàn bộ thuật toán được cài đặt hoàn chỉnh trên nền tảng Java.

Chương 6: Empirical Evaluation

Chương 6 trình bày các thử nghiệm thực nghiệm đối sánh hiệu năng giữa bốn thuật toán TFWIT, TFWID, TFWIN và TFWIN+ trên cùng điều kiện phần cứng và tập dữ liệu kiểm thử.

---

Thiết kế và triển khai thuật toán

Đồ án thiết kế và hiện thực hóa bốn giải thuật khai thác Top-rank-$k$ FWIs với các chiến lược xử lý dữ liệu khác nhau:

Tiêu chí	Thuật toán TFWIT	Thuật toán TFWID	Thuật toán TFWIN	Thuật toán TFWIN+
Cấu trúc dữ liệu cốt lõi	Tidset (Tập ID giao dịch)	Diffset (Tập hiệu số giao dịch)	WN-tree & WN-list	WN-tree & WN-list
Cơ chế tính độ hỗ trợ ($ws$)	Giao tập $t(PXY) = t(PX) \cap t(PY)$	$ws(PXY) = ws(PX) - \frac{\sum tw(d)}{TTW}$	Giao WN-list dựa trên quan hệ tổ tiên-con cháu $(pre, post)$	Giao WN-list kết hợp kiểm tra cận trên trọng số
Chiến lược tối ưu hóa	Duyệt lớp tương đương	Nén biểu diễn giao dịch	Nén cây tiền tố có trọng số	Cắt tỉa nhánh sớm (Early Pruning)
Ngôn ngữ triển khai	Java (hướng đối tượng)	Java (hướng đối tượng)	Java (hướng đối tượng)	Java (hướng đối tượng)

Quy trình thực thi chung của giải thuật khai thác Top-rank-k:
1. Đọc cơ sở dữ liệu có trọng số (WD) -> Tính trọng số từng giao dịch tw(t) và tổng TTW.
2. Xác định các 1-itemset phổ biến thỏa ngưỡng minws và sắp xếp danh sách.
3. Khởi tạo cấu trúc biểu diễn tương ứng (Tidset / Diffset / WN-list).
4. Duyệt không gian trạng thái theo cây tiền tố (Prefix Tree) kết hợp duy trì danh sách Top-rank-k tốt nhất.
5. Áp dụng chiến lược cắt tỉa (nâng ngưỡng động / cắt tỉa sớm trên WN-list).
6. Xuất tập hợp hoàn chỉnh các Top-rank-k FWIs.

Trong phần mã nguồn Java được công bố, các lớp cấu trúc dữ liệu như FWIset, TRset, FloatByRef cùng các hàm xử lý cốt lõi findFWIs, tfwitCandidateGeneration, tfwidCandidateGeneration và tidsetCombination/diffsetCombination được xây dựng chi tiết để quản lý danh sách thứ hạng và thực hiện cập nhật danh sách Top-$k$ theo thời gian thực.

---

Kết quả và đóng góp

Kết quả thực nghiệm

Kết quả ghi nhận từ nhật ký thực thi thực tế của chương trình trên tập dữ liệu kiểm thử (với tổng độ dài giao dịch sumTransLength = 118252.0) thể hiện sự khác biệt rõ rệt về hiệu năng:

Thuật toán	Thời gian thực thi (Total time)	Bộ nhớ tiêu thụ cực đại (Max memory)
TFWIT (Tidset)	3.254 ms	32,99 MB
TFWID (Diffset)	2.765 ms	28,39 MB
TFWIN (WN-list)	Đã cải thiện so với TFWID	Đã cải thiện so với TFWID
TFWIN+ (WN-list + Early Pruning)	Nhanh nhất trong các thuật toán	Tiêu thụ bộ nhớ thấp nhất

Các chỉ số thực nghiệm cho thấy:

• Thuật toán TFWID giảm thời gian chạy từ 3.254 ms xuống 2.765 ms (nhanh hơn ~15%) và giảm bộ nhớ từ 32,99 MB xuống 28,39 MB so với TFWIT nhờ việc lưu trữ Diffset thay vì toàn bộ Tidset.
• Cấu trúc WN-list trong TFWIN giúp nén dữ liệu hiệu quả hơn cấu trúc khuếch tán (diffset).
• Thuật toán TFWIN+ đạt hiệu quả cao nhất nhờ việc tích hợp chiến lược cắt tỉa sớm, loại bỏ triệt để các ứng viên không tiềm năng ngay từ các tầng trên của không gian tìm kiếm.

Đóng góp khoa học và kỹ thuật

1. Mô hình hóa hoàn chỉnh bài toán: Đưa ra định nghĩa toán học rõ ràng về khái niệm Top-rank-$k$ trong môi trường dữ liệu có trọng số, giải quyết bài toán bùng nổ số lượng mẫu trong FIM truyền thống.
2. Cải tiến cấu trúc dữ liệu: Mở rộng thành công cấu trúc N-list thành WN-list với việc gán nhãn $WN\text{-}code = (pre, post, weight)$, cho phép xác định quan hệ cha-con và tính toán trọng số hỗ trợ trực tiếp mà không cần duyệt lại cơ sở dữ liệu gốc.
3. Đề xuất chiến lược cắt tỉa mới: Xây dựng cơ chế cắt tỉa sớm (Early Pruning Strategy) cho thuật toán TFWIN+, giảm thiểu đáng kể số lượng phép giao danh sách WN-list không cần thiết.

---

Hạn chế và hướng nghiên cứu tiếp

Theo nội dung đồ án, nghiên cứu còn một số điểm giới hạn:

• Phạm vi mô hình hóa: Đề tài tập trung vào trọng số cố định của từng hạng mục (item weight / item benefit) mà chưa tính đến số lượng xuất hiện (quantity) của từng mục trong mỗi giao dịch đơn lẻ (bài toán High Utility Itemset Mining - HUIM).
• Môi trường tính toán: Các thuật toán hiện tại được cài đặt tuần tự trên một máy tính đơn lập trình bằng Java, chưa khai thác mô hình xử lý phân tán hoặc tính toán song song đa luồng trên GPU/đa nhân.
• Loại hình dữ liệu: Nghiên cứu mới thử nghiệm trên cơ sở dữ liệu tĩnh, chưa mở rộng cho các luồng dữ liệu biến đổi liên tục theo thời gian (data stream).

Hướng nghiên cứu tiếp theo được tác giả định hướng bao gồm việc mở rộng giải thuật để xử lý dữ liệu động, tích hợp đại lượng số lượng sản phẩm vào bài toán khai thác mẫu hữu ích cao (Top-$k$ HUIM) và tối ưu hóa thêm cấu trúc cây WN-tree.

---

Giá trị tham khảo

Đồ án là tài liệu tham khảo có giá trị chuyên môn cao đối với:

• Sinh viên ngành Khoa học Máy tính, Kỹ thuật Phần mềm và Khoa học Dữ liệu: Tham khảo phương pháp biểu diễn dữ liệu nâng cao (Tidset, Diffset, N-list/WN-list), kỹ thuật sinh ứng viên theo lớp tương đương và kỹ thuật lập trình thuật toán trên Java.
• Học viên và nghiên cứu viên về Data Mining / KDD: Nắm bắt quy trình thiết kế và tối ưu hóa giải thuật khai phá mẫu có trọng số, kỹ thuật cắt tỉa không gian tìm kiếm và phương pháp thiết kế thực nghiệm đo lường hiệu năng.
• Kỹ sư phát triển hệ thống gợi ý và phân tích kinh doanh: Ứng dụng các thuật toán khai thác tập có trọng số vào bài toán phân tích hành vi khách hàng và tối ưu hóa danh mục sản phẩm dựa trên lợi nhuận thực tế.

---

Câu hỏi thường gặp

1. Trọng số của một giao dịch ($tw$) và độ hỗ trợ có trọng số ($ws$) được tính như thế nào trong đồ án?
Trọng số của một giao dịch $t_k$ được tính bằng trung bình cộng trọng số các hạng mục có trong giao dịch: $tw(t_k) = \frac{\sum_{i \in t_k} w_i}{|t_k|}$. Độ hỗ trợ có trọng số của tập mục $X$ ($ws(X)$) là tỷ lệ giữa tổng trọng số các giao dịch chứa $X$ chia cho tổng trọng số của toàn bộ cơ sở dữ liệu ($TTW$): $ws(X) = \frac{\sum_{t \in t(X)} tw(t)}{TTW}$.

2. Khái niệm Top-rank-$k$ khác với Top-$k$ thông thường như thế nào?
Trong khai thác Top-$k$ thông thường, thuật toán tìm kiếm đúng $k$ tập mục có giá trị đo lường cao nhất. Trong Top-rank-$k$, khái niệm Rank ($RX$) dựa trên số lượng các mức giá trị trọng số hỗ trợ phân biệt. Nếu nhiều tập mục có cùng độ hỗ trợ trọng số, chúng sẽ có cùng một thứ hạng và đều được giữ lại, đảm bảo không bỏ sót các mẫu có cùng mức độ quan trọng.

3. Cấu trúc WN-code của một nút trên cây WN-Tree gồm những thành phần nào?
Mỗi nút trên cây WN-Tree đại diện cho một hạng mục và được mã hóa bằng một bộ ba giá trị $WN\text{-}code = (pre, post, weight)$, trong đó $pre$ là số thứ tự duyệt cây theo thứ tự trước (pre-order), $post$ là số thứ tự duyệt cây theo thứ tự sau (post-order), và $weight$ là tổng trọng số giao dịch ($tw$) của các giao dịch đi qua nút đó.

4. Tại sao thuật toán TFWID lại tiết kiệm bộ nhớ và chạy nhanh hơn TFWIT?
TFWIT sử dụng cấu trúc Tidset để lưu trữ toàn bộ danh sách ID giao dịch chứa tập mục, dẫn đến chi phí bộ nhớ và thời gian tính toán phép giao tập lớn khi tập dữ liệu lớn. TFWID sử dụng Diffset, chỉ lưu trữ phần hiệu số (sự khác biệt) về ID giao dịch giữa hai tập mục kết hợp ($d(PXY) = d(PY) \setminus d(PX)$), từ đó kích thước lưu trữ giảm mạnh và việc tính toán $ws(PXY)$ được thực hiện nhanh hơn bằng phép trừ trực tiếp.

5. Kết quả thực nghiệm đã chứng minh thuật toán nào đạt hiệu năng tốt nhất?
Kết quả thực nghiệm trên tập dữ liệu mẫu khẳng định thuật toán TFWIN+ đạt hiệu năng cao nhất về cả tốc độ thực thi lẫn khả năng tối ưu hóa bộ nhớ, nhờ việc kết hợp cấu trúc nén WN-list với chiến lược cắt tỉa sớm (Early Pruning Strategy).

---

Kết luận

Đồ án của nhóm tác giả Nguyễn Triệu Vi và Trần Thành Đạt đã nghiên cứu và giải quyết bài toán khai thác Top-rank-$k$ tập phổ biến có trọng số thông qua việc phát triển hệ thống bốn thuật toán TFWIT, TFWID, TFWIN và TFWIN+. Nghiên cứu đã chứng minh sự vượt trội của cấu trúc dữ liệu WN-list kết hợp với chiến lược cắt tỉa động sớm trong việc giảm thiểu không gian tìm kiếm và nâng cao tốc độ xử lý dữ liệu có trọng số. Toàn bộ mã nguồn Java và kết quả thực nghiệm được trình bày rõ ràng, tạo cơ sở lý thuyết và thực tiễn vững chắc cho các nghiên cứu chuyên sâu tiếp theo trong lĩnh vực khai phá tri thức.

Trích đoạn nội dung tài liệu

Đặt vấn đề Trong thời đại sô hóa ngày nay, việc khai thác thông tm 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 van đề này, để tài này tập trung vào bài toán khai thác Top-rank-k tập pho biến từ cơ sở đữ 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+) duoc phat 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. CHUONG 2 -— TONG QUAN VA CO SO LY THUYET Tổng quan: Đề tai nay 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) c Data mining — khai phá dữ liệu là quá trình phân loại, sắp xếp các tập hop dtr 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 khong 16. 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é tinh trong số của mỗi giao dịch bằng cách lay trung bình của trọng số của các sản phâm trong giao dịch đó.