Khai Thác Tập Phổ Biến Có Trọng Số Sử Dụng Thuật Toán TFWIN+

Khám phá phương pháp khai thác tập hợp mục có trọng số k thường xuyên hàng đầu bằng cấu trúc danh sách wn 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ố: Thuật Toán TFWIN+

Mục lục chi tiết

• LỜI CẢM ƠN
• 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.3. Khai thác tập phổ biến (Mining frequent weighted itemset)
• 2.4. 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
• 4. CHƯƠNG 4: TIDSET AND DIFFSET STRUCTURES FOR MINING FWIs
• 4.1. Cấu trúc Tidset và Diffset
• 4.1.1. Cấu trúc Tidset
• 4.1.2. Cấu trúc 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 & mã giả
• 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 & mã giả
• 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. Hướng Dẫn Về Khai Thác Tập Phổ Biến Có Trọng Số WFIM

Trong lĩnh vực khai phá dữ liệu (data mining), việc tìm ra các mẫu ẩn và quy luật có giá trị là mục tiêu cốt lõi. Khai thác mẫu phổ biến (frequent pattern mining) là một kỹ thuật nền tảng, nhưng mô hình truyền thống thường bỏ qua tầm quan trọng khác nhau của các mục. Weighted Frequent Itemset Mining (WFIM) ra đời để giải quyết bài toán này, gán một trọng số mục (item weight) cho từng đối tượng, phản ánh đúng giá trị hoặc mức độ quan trọng của chúng trong thực tế. Phương pháp này cho phép các phân tích trở nên sâu sắc và chính xác hơn, đặc biệt trong các ứng dụng như phân tích giỏ hàng nơi lợi nhuận của sản phẩm có sự chênh lệch lớn.

1.1. Tầm quan trọng của khai phá dữ liệu và luật kết hợp

Khai phá dữ liệu là quá trình trích xuất các thông tin hữu ích, các mẫu tiềm ẩn và tri thức từ các tập dữ liệu lớn. Một trong những kỹ thuật quan trọng nhất trong lĩnh vực này là khai phá luật kết hợp (association rule mining). Mục tiêu của kỹ thuật này là phát hiện các mối quan hệ thú vị giữa các biến trong cơ sở dữ liệu lớn. Ví dụ kinh điển là quy tắc "Nếu khách hàng mua tã, họ cũng có khả năng mua bia". Các quy tắc này được ứng dụng rộng rãi trong phân tích giỏ hàng (market basket analysis), thiết kế danh mục sản phẩm và chiến lược khuyến mãi. Các thuật toán ban đầu như thuật toán Apriori đã đặt nền móng cho việc tìm kiếm các tập mục phổ biến, từ đó suy ra các luật kết hợp mạnh. Tuy nhiên, các phương pháp này coi tất cả các mục là có tầm quan trọng như nhau, dẫn đến những hạn chế trong các kịch bản thực tế.

1.2. Sự ra đời của khái niệm độ hỗ trợ có trọng số

Mô hình khai thác truyền thống dựa trên tần suất xuất hiện đơn thuần. Tuy nhiên, trong nhiều ứng dụng, các mục có giá trị hoặc tầm quan trọng khác nhau. Ví dụ, trong một siêu thị, việc bán một chiếc TV mang lại lợi nhuận cao hơn nhiều so với một ổ bánh mì. Để giải quyết vấn đề này, khái niệm độ hỗ trợ có trọng số (weighted support) được giới thiệu. Mỗi mục được gán một trọng số mục để phản ánh tầm quan trọng của nó. Thay vì chỉ đếm số lần xuất hiện, độ hỗ trợ có trọng số của một tập mục được tính toán dựa trên tổng trọng số của các giao dịch chứa nó. Điều này cho phép các nhà phân tích tập trung vào các mẫu không chỉ phổ biến mà còn có giá trị kinh tế cao, mở ra một hướng tiếp cận mới và hiệu quả hơn trong lĩnh vực học máy (machine learning).

II. Thách Thức Khi Áp Dụng Apriori và FP Growth Với Dữ Liệu Lớn

Mặc dù là những thuật toán tiên phong, thuật toán Apriori và thuật toán FP-Growth phải đối mặt với nhiều thách thức khi xử lý cơ sở dữ liệu giao dịch (transaction database) có trọng số và quy mô lớn. Vấn đề lớn nhất là "sự bùng nổ mẫu", nơi một lượng khổng lồ các tập phổ biến được tạo ra, gây khó khăn cho việc lưu trữ, phân tích và tìm kiếm tri thức thực sự hữu ích. Hơn nữa, việc xác định một ngưỡng hỗ trợ (support threshold) duy nhất cho toàn bộ cơ sở dữ liệu thường không hiệu quả, có thể bỏ sót các mẫu có giá trị nhưng tần suất thấp. Những hạn chế này thúc đẩy nhu cầu phát triển các thuật toán tiên tiến hơn.

2.1. Hạn chế của thuật toán Apriori trong thực tiễn

Thuật toán Apriori hoạt động 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 thực hiện quét cơ sở dữ liệu nhiều lần để tạo ra các tập ứng viên và kiểm tra độ hỗ trợ của chúng. Quá trình này cực kỳ tốn kém về mặt tính toán và I/O khi tập dữ liệu lớn và số lượng mục tăng lên. Hơn nữa, việc tạo ra một số lượng lớn các tập ứng viên ở mỗi bước, đặc biệt là các tập có độ dài trung bình, dẫn đến yêu cầu bộ nhớ khổng lồ. Đối với dữ liệu có trọng số, việc tính toán weighted support lặp đi lặp lại càng làm tăng thêm độ phức tạp, khiến Apriori trở nên không thực tế cho các bài toán hiện đại.

2.2. Vấn đề của FP Growth và sự cần thiết của Top rank k

Thuật toán FP-Growth cải thiện Apriori bằng cách tránh tạo tập ứng viên. Nó sử dụng một cấu trúc dữ liệu nén gọi là cây FP-Tree để lưu trữ thông tin về các mục phổ biến và chỉ cần quét cơ sở dữ liệu hai lần. Mặc dù hiệu quả hơn Apriori, FP-Growth vẫn gặp khó khăn trong việc tạo ra một lượng lớn các mẫu phổ biến khi ngưỡng hỗ trợ được đặt ở mức thấp. Theo nghiên cứu của Nguyễn Triệu Vi và Trần Thành Đạt (2023), "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". Để giải quyết vấn đề này, phương pháp khai thác Top-rank-k ra đời, tập trung vào việc chỉ tìm ra k tập mục có độ hỗ trợ cao nhất, giúp loại bỏ nhiễu và tập trung vào những mẫu quan trọng nhất.

III. Phương Pháp TFWIN Khai Thác Hiệu Quả Với Cấu Trúc WN List

Để vượt qua các hạn chế của thuật toán trước đó, thuật toán TFWIN (Top-rank-k Frequent Weighted Itemsets using Weighted N-list) được đề xuất. Thuật toán này là một bước đột phá trong weighted frequent itemset mining (WFIM). TFWIN sử dụng một cấu trúc dữ liệu tiên tiến gọi là WN-list, được thiết kế đặc biệt để xử lý dữ liệu có trọng số một cách hiệu quả. Thay vì quét toàn bộ cơ sở dữ liệu, TFWIN thực hiện các phép giao trên các cấu trúc WN-list để tính toán độ hỗ trợ có trọng số, giúp giảm đáng kể thời gian tính toán và yêu cầu bộ nhớ.

3.1. Giới thiệu cấu trúc WN List và ưu điểm

WN-list (Weighted N-list) là một cấu trúc dữ liệu được phát triển để tối ưu hóa việc khai thác các tập mục có trọng số. Mỗi mục trong cơ sở dữ liệu được liên kết với một WN-list riêng. Cấu trúc này không chỉ lưu trữ danh sách các mã giao dịch (TID) chứa mục đó, mà còn lưu trữ tổng trọng số tích lũy của các mục đứng trước nó trong mỗi giao dịch. Thiết kế thông minh này cho phép thuật toán tính toán weighted support của một tập mục mới một cách nhanh chóng chỉ bằng cách thực hiện phép giao giữa các WN-list của các mục thành phần. Ưu điểm chính của WN-list là khả năng nén thông tin và tăng tốc độ tính toán, làm cho nó phù hợp với các bài toán data mining quy mô lớn.

3.2. Quy trình hoạt động của thuật toán TFWIN

Thuật toán TFWIN hoạt động theo chiến lược tìm kiếm theo chiều sâu (depth-first search). Ban đầu, nó tạo ra các WN-list cho tất cả các mục 1-itemset. Sau đó, thuật toán đệ quy khám phá không gian tìm kiếm bằng cách mở rộng các tập mục hiện tại với các mục khác. Tại mỗi bước, một tập mục mới được tạo ra bằng cách kết hợp tập mục cha với một mục mới. WN-list của tập mục mới này được tính toán bằng cách thực hiện phép giao hiệu quả giữa WN-list của tập cha và WN-list của mục mới. Quá trình này tiếp tục cho đến khi không thể mở rộng thêm, đảm bảo tìm ra top-k các tập mục có độ hỗ trợ có trọng số cao nhất mà không cần tạo ra tập ứng viên một cách tường minh.

IV. Tối Ưu Hóa Thuật Toán TFWIN Chiến Lược Cắt Tỉa Sớm

Mặc dù thuật toán TFWIN đã cải thiện đáng kể hiệu suất, nó vẫn có thể khám phá những nhánh không gian tìm kiếm không cần thiết. Để giải quyết vấn đề này, thuật toán TFWIN+ được ra đời. Đây là phiên bản nâng cao của TFWIN, tích hợp một "chiến lược cắt tỉa sớm" (early pruning strategy) thông minh. Chiến lược này cho phép thuật toán loại bỏ các tập ứng viên không có khả năng lọt vào top-k ngay từ giai đoạn đầu, giúp tiết kiệm tài nguyên tính toán và tăng tốc độ khai thác một cách vượt trội. TFWIN+ đại diện cho một bước tiến quan trọng trong việc khai thác hiệu quả các tập mục có trọng số.

4.1. Cơ chế hoạt động của chiến lược cắt tỉa sớm

Chiến lược cắt tỉa sớm trong TFWIN+ hoạt động dựa trên việc tính toán một giới hạn trên (upper bound) cho độ hỗ trợ có trọng số của bất kỳ tập mục nào có thể được tạo ra từ một nhánh tìm kiếm cụ thể. Trong quá trình đệ quy, trước khi mở rộng một tập mục, thuật toán sẽ tính toán giới hạn trên này. Nếu giới hạn trên này nhỏ hơn giá trị độ hỗ trợ của tập mục đứng thứ k trong danh sách top-k hiện tại, toàn bộ nhánh tìm kiếm đó sẽ bị cắt tỉa. Điều này có nghĩa là thuật toán sẽ không lãng phí thời gian để khám phá các tập mục con trong nhánh đó, vì chúng chắc chắn không thể trở thành một trong k tập phổ biến nhất. Kỹ thuật này giúp thu hẹp đáng kể không gian tìm kiếm và tập trung vào các khu vực hứa hẹn nhất.

4.2. So sánh hiệu năng giữa TFWIN và TFWIN

Theo kết quả thử nghiệm thực nghiệm được trình bày trong đồ án của Nguyễn Triệu Vi và Trần Thành Đạt (2023), thuật toán TFWIN+ thể hiện hiệu suất vượt trội so với phiên bản tiền nhiệm TFWIN. Nhờ chiến lược cắt tỉa sớm, TFWIN+ giảm đáng kể thời gian chạy và mức sử dụng bộ nhớ, đặc biệt trên các cơ sở dữ liệu giao dịch dày đặc và có số lượng mục lớn. Báo cáo chỉ ra rằng "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". Sự cải tiến này không chỉ là về mặt lý thuyết mà còn được chứng minh bằng thực nghiệm, khẳng định vị thế của TFWIN+ là giải pháp hàng đầu cho các bài toán WFIM.

V. Ứng Dụng Thực Tiễn và Kết Quả Nghiên Cứu của Thuật Toán

Thuật toán TFWIN+ không chỉ là một cải tiến lý thuyết mà còn có tiềm năng ứng dụng thực tiễn to lớn trong nhiều ngành công nghiệp. Từ bán lẻ, thương mại điện tử đến y sinh và phân tích mạng xã hội, khả năng xác định các mẫu quan trọng nhất trong dữ liệu có trọng số mở ra nhiều cơ hội để tối ưu hóa quy trình và đưa ra quyết định thông minh. Các kết quả nghiên cứu thực nghiệm đã chứng minh tính hiệu quả và khả năng mở rộng của thuật toán, củng cố vai trò của nó như một công cụ mạnh mẽ trong lĩnh vực khai phá dữ liệu và học máy.

5.1. Ứng dụng trong phân tích giỏ hàng và hệ gợi ý

Một trong những ứng dụng rõ ràng nhất của TFWIN+ là trong phân tích giỏ hàng. Bằng cách gán trọng số cho các sản phẩm dựa trên giá hoặc lợi nhuận, các nhà bán lẻ có thể phát hiện các bộ sản phẩm không chỉ được mua cùng nhau thường xuyên mà còn mang lại giá trị kinh tế cao nhất. Thông tin này rất quan trọng để thiết kế các chương trình khuyến mãi, sắp xếp bố cục cửa hàng và chiến lược bán chéo (cross-selling). Tương tự, trong các hệ gợi ý (recommender system) của các nền tảng như Amazon hay Netflix, TFWIN+ có thể giúp xác định các nhóm mục (phim, sản phẩm) có giá trị cao thường được tiêu thụ cùng nhau, từ đó đưa ra những đề xuất chính xác và mang lại lợi ích kinh doanh lớn hơn.

5.2. Đánh giá thực nghiệm Thời gian và bộ nhớ

Các nghiên cứu thực nghiệm so sánh TFWIN+ với các thuật toán khác như TFWIT, TFWID, và TFWIN đã cho thấy kết quả ấn tượng. Trên nhiều bộ dữ liệu chuẩn, TFWIN+ luôn cho thấy thời gian thực thi nhanh hơn và yêu cầu bộ nhớ thấp hơn. Đặc biệt, khi ngưỡng hỗ trợ giảm hoặc mật độ dữ liệu tăng, lợi thế của chiến lược cắt tỉa sớm càng trở nên rõ rệt. Những kết quả này khẳng định rằng TFWIN+ không chỉ hiệu quả mà còn có khả năng mở rộng tốt, sẵn sàng để triển khai trong các hệ thống data mining thực tế, nơi tốc độ và hiệu quả sử dụng tài nguyên là yếu tố then chốt.

Nội dung chính

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

Khai phá dữ liệu (Data Mining) và khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) đóng vai trò then chốt trong việc phân tích các tập dữ liệu lớn nhằm phát hiện các xu hướng, mẫu hình ẩn và thiết lập những mối quan hệ có giá trị, hỗ trợ quá trình ra quyết định trong hoạt động thực tiễn và kinh doanh. Trong đó, khai phá tập phổ biến (Frequent Itemset Mining - FIM) và khai phá luật kết hợp (Association Rule Mining - ARM) là những bài toán nền tảng. Các thuật toán kinh điển như Apriori, FP-growth và Eclat đã được phát triển để xử lý hiệu quả bài toán khai thác tập phổ biến trên các cơ sở dữ liệu giao dịch truyền thống.

Tuy nhiên, các phương pháp truyền thống phần lớn giả định rằng tất cả các mục (items) trong cơ sở dữ liệu đều có tầm quan trọng hay giá trị tương đương nhau. Trong thực tế, các sản phẩm hoặc đối tượng trong giao dịch thường mang các giá trị kinh tế, số lượng hoặc mức độ ưu tiên khác nhau, đòi hỏi phải gán trọng số cụ thể cho từng mục. Khi cơ sở dữ liệu được đánh trọng số, độ phức tạp của bài toán khai phá tăng lên rõ rệt do cần xử lý đồng thời tần suất xuất hiện và giá trị trọng số của từng phần tử. Thêm vào đó, việc khai thác tập phổ biến thông thường thường sinh ra một số lượng rất lớn các mẫu (pattern), gây khó khăn cho người dùng trong việc tiếp nhận, diễn giải và trích xuất các luật kết hợp thực sự hữu ích.

Để giải quyết các thách thức trên, đồ án tập trung vào bài toán khai thác Top-rank-$k$ tập phổ biến có trọng số (Mining Top-rank-$k$ Frequent Weighted Itemsets - FWIs). Mục tiêu và nhiệm vụ nghiên cứu cụ thể bao gồm:

1. Nghiên cứu bài toán khai thác tập phổ biến có trọng số (FWIs) và cơ chế xếp hạng Top-rank-$k$ nhằm kiểm soát số lượng kết quả đầu ra, chỉ giữ lại $k$ mức xếp hạng phổ biến có trọng số cao nhất.
2. Khảo sát và ứng dụng hai cấu trúc dữ liệu biểu diễn theo chiều dọc là Tidset và Diffset để xây dựng các thuật toán cơ sở gồm TFWIT (Top-rank-$k$ Frequent Weighted Itemsets using Tidsets) và TFWID (Top-rank-$k$ Frequent Weighted Itemsets using Diffsets).
3. Phát triển cấu trúc danh sách nút có trọng số WN-list (Weighted N-list) và đề xuất thuật toán TFWIN nhằm khắc phục hạn chế về nén dữ liệu và thời gian thực thi của các cấu trúc dọc truyền thống.
4. Tích hợp chiến lược cắt tỉa sớm (early pruning strategy) vào thuật toán TFWIN để hình thành thuật toán cải tiến TFWIN+, nâng cao hiệu quả thu hẹp không gian tìm kiếm.
5. Triển khai cài đặt các thuật toán bằng ngôn ngữ lập trình Java, phân tích độ phức tạp thuật toán và tiến hành đánh giá thực nghiệm (Empirical Evaluation) về thời gian chạy cùng mức tiêu thụ bộ nhớ.

Đối tượng nghiên cứu của đề tài là các mô hình toán học của tập phổ biến có trọng số, các biểu diễn rút gọn (như tập phổ biến đóng FCIs, tập phổ biến tối đa MFIs), cùng các cấu trúc dữ liệu Tidset, Diffset và WN-list. Phạm vi nghiên cứu được thực hiện trong khuôn khổ đồ án môn học Phân tích và thiết kế giải thuật tại Khoa Công nghệ Thông tin, Trường Đại học Tôn Đức Thắng (khóa K25, năm 2023), do sinh viên Nguyễn Triệu Vi (MSSV: 52100143) và Trần Thành Đạt (MSSV: 52100879) thực hiện dưới sự hướng dẫn của giảng viên TS. Nguyễn Chí Thiện.

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

Cơ sở lý thuyết của nghiên cứu được xây dựng trên các nguyên lý khai phá dữ liệu, khai phá luật kết hợp và lý thuyết về tập phổ biến có trọng số:

• Mô hình trọng số giao dịch: Trọng số của một giao dịch ($T$) được tính bằng giá trị trung bình của trọng số các mục thành phần có trong giao dịch đó.
• Mức hỗ trợ có trọng số (Weighted Support): Mức hỗ trợ có trọng số của một tập mục được xác định bằng tỷ lệ giữa tổng trọng số của tất cả các giao dịch chứa tập mục đó trên tổng trọng số của toàn bộ các giao dịch trong cơ sở dữ liệu. Độ đo này phản ánh mức độ quan trọng thực tế của tập mục trong dữ liệu có biến đổi về trọng số.
• Khai phá luật kết hợp: Gồm hai giai đoạn tuần tự: (1) Khai thác tất cả các tập phổ biến (FIs hoặc FWIs) thỏa mãn ngưỡng hỗ trợ, và (2) Sinh các luật kết hợp (Association Rules - ARs) dạng $X \rightarrow Y$ đạt ngưỡng độ tin cậy (confidence) xác định.
• Biểu diễn rút gọn: Sử dụng các tập phổ biến đóng (Frequent Closed Itemsets - FCIs) hoặc tập phổ biến tối đa (Maximal Frequent Itemsets - MFIs) nhằm giảm không gian lưu trữ và thời gian tính toán mà vẫn cho phép suy dẫn đầy đủ tập phổ biến.
• Cơ chế Top-rank-$k$: Thay vì sử dụng một ngưỡng hỗ trợ tối thiểu cố định (minsup) khó thiết lập chính xác trong thực tế, bài toán Top-rank-$k$ tự động tìm kiếm các tập mục có mức hỗ trợ có trọng số thuộc $k$ mức giá trị cao nhất.

Về mặt phương pháp luận và kỹ thuật, đồ án kết hợp phương pháp nghiên cứu lý thuyết giải thuật với phương pháp thực nghiệm:

• Phân tích cấu trúc dữ liệu: Khảo sát cấu trúc Tidset (lưu trữ danh sách mã giao dịch chứa tập mục), Diffset (lưu trữ phần sai khác giữa các tập TID) và cấu trúc WN-list (Weighted N-list) dựa trên mã hóa tiền thứ tự và hậu thứ tự của cây tiền tố PPC-tree để nén dữ liệu và hỗ trợ tính toán giao cắt nhanh.
• Chiến lược cắt tỉa sớm (Early Pruning): Áp dụng kỹ thuật cắt tỉa động trong quá trình duyệt không gian trạng thái, cập nhật cận dưới của mức hỗ trợ có trọng số trong danh sách top-$k$ để loại bỏ sớm các nhánh không có tiềm năng lọt vào nhóm dẫn đầu.
• Phương pháp thực nghiệm: Toàn bộ các thuật toán TFWIN và TFWIN+ được thiết kế mã giả, phân tích độ phức tạp thời gian/không gian và lập trình hoàn chỉnh trên nền tảng Java. Đánh giá hiệu năng được tiến hành thông qua việc đo đạc thời gian thực thi (runtime) và dung lượng bộ nhớ sử dụng (memory consumption) trên các tập dữ liệu thử nghiệm.

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

Chương 1 – Mở đầu

Chương 1 trình bày bối cảnh chuyển đổi số và sự cần thiết của việc khai thác mối quan hệ giữa các sản phẩm trong danh mục có gắn trọng số. Tác giả phân tích hạn chế của các thuật toán truyền thống (Apriori, FP-growth, Eclat) khi xử lý dữ liệu trọng số phức tạp. Trên cơ sở đó, chương xác định mục tiêu 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+), tận dụng các cấu trúc Tidset, Diffset và WN-list kết hợp chiến lược cắt tỉa động nhằm cải thiện thời gian thực thi và tối ưu hóa khả năng nén dữ liệu.

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 về khai phá dữ liệu và khám phá tri thức từ dữ liệu (KDD). Nội dung tập trung làm rõ:

• Định nghĩa khai phá dữ liệu và mục tiêu hỗ trợ dự đoán xu hướng cho doanh nghiệp.
• Công thức tính trọng số giao dịch và mức hỗ trợ có trọng số của tập mục.
• Khái niệm luật kết hợp, cấu trúc luật $X \rightarrow Y$ kèm theo hai chỉ số đo lường mức hỗ trợ (support) và độ tin cậy (confidence). Chương minh họa qua bảng dữ liệu khảo sát tiện nghi 8 hộ gia đình (với các thiết bị: Tivi, Tủ lạnh, Máy lạnh, Máy giặt, Máy vi tính) và ví dụ luật kết hợp cụ thể: $\text{Tivi} \rightarrow \text{Máy vi tính}$ $[50%, 57%]$.
• Quy trình hai giai đoạn của khai phá luật kết hợp và nguyên lý hoạt động của thuật toán kinh điển Apriori.

Chương 3 – Frequent Weighted Itemset

Chương 3 đi sâu vào các định nghĩa hình thức liên quan đến tập phổ biến có trọng số (FWIs) và bài toán Top-rank-$k$ tập phổ biến có trọng số. Chương làm rõ sự khác biệt giữa bài toán tìm kiếm dựa trên ngưỡng hỗ trợ cố định và bài toán xếp hạng $k$ mức cao nhất, đồng thời phân tích vai trò của các dạng biểu diễn rút gọn (FCIs và MFIs) trong việc giảm bớt số lượng mẫu dư thừa mà không làm mất mát tri thức suy dẫn.

Chương 4 – Tidset and Diffset structures for mining FWIs

Chương 4 trình bày chi tiết về cấu trúc dữ liệu dạng dọc:

• Cấu trúc Tidset: Lưu trữ trực tiếp danh sách mã định danh giao dịch (TID) cho từng tập mục, cho phép tính mức hỗ trợ thông qua phép giao hai tập hợp.
• Cấu trúc Diffset: Chỉ lưu trữ sự khác biệt về TID giữa tập mục cha và tập mục con, giúp giảm đáng kể kích thước bộ nhớ so với Tidset trong các cơ sở dữ liệu dày đặc.
• Thuật toán khai thác FWIs: Mô tả giải thuật TFWIT và TFWID, đồng thời chỉ ra nhược điểm của chúng về hiệu quả nén dữ liệu trên không gian tìm kiếm lớn, dẫn đến chi phí thời gian thực hiện còn cao.

Chương 5 – WN-List structure for mining FWIs. Implement JAVA with TFWIN & TFWIN+

Chương 5 là trọng tâm kỹ thuật của đồ án, bao gồm:

• Định nghĩa hình thức và ví dụ minh họa về cấu trúc WN-list (Weighted N-list), kết hợp thông tin thứ tự duyệt cây (pre-order, post-order) và trọng số nút.
• Thuật toán TFWIN: Trình bày nguyên lý khai thác Top-rank-$k$ FWIs dựa trên WN-list, cung cấp mã giả thuật toán, chi tiết cài đặt bằng ngôn ngữ Java, phân tích kết quả thu được và đánh giá độ phức tạp thuật toán.
• Thuật toán TFWIN+: Đề xuất cải tiến tích hợp chiến lược cắt tỉa sớm (early pruning strategy) vào TFWIN, cung cấp mã giả chi tiết, mã nguồn triển khai Java, phân tích kết quả và chứng minh độ phức tạp tính toán được cải thiện nhờ loại bỏ sớm các nhánh không tiềm năng.

Chương 6 – Empirical Evaluation

Chương 6 trình bày quy trình và kết quả thử nghiệm thực nghiệm (Empirical Evaluation). Nội dung tập trung đo lường, đối sánh định lượng giữa các phương pháp TFWIT, TFWID, TFWIN và TFWIN+ dựa trên hai tiêu chí cốt lõi: thời gian thực thi (running time) và dung lượng bộ nhớ tiêu thụ (memory consumption). Kết quả thực nghiệm cung cấp bằng chứng định lượng khẳng định hiệu năng của thuật toán cải tiến TFWIN+.

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

Đồ án tập trung thiết kế cấu trúc dữ liệu và hiện thực hóa các giải thuật xử lý dữ liệu có trọng số bằng ngôn ngữ lập trình Java. Các thành phần thiết kế và triển khai chính bao gồm:

+-------------------------------------------------------------------------+
|                        Quy trình thuật toán TFWIN+                      |
|                                                                         |
|  [CSDL giao dịch có trọng số]                                           |
|               |                                                         |
|               v                                                         |
|  [Khởi tạo cấu trúc WN-list ban đầu cho từng mục]                       |
|               |                                                         |
|               v                                                         |
|  [Duyệt không gian tìm kiếm theo nhánh]                                  |
|               |                                                         |
|               v                                                         |
|  [Áp dụng chiến lược cắt tỉa sớm (Early Pruning Strategy)]               |
|         /                           \                                   |
|        / (Không đạt ngưỡng)          \ (Đạt ngưỡng tiềm năng)           |
|       v                               v                                 |
|  [Loại bỏ nhánh]             [Sinh WN-list con & Cập nhật danh sách]    |
|                                       |                                 |
|                                       v                                 |
|                         [Xuất Top-rank-k FWIs kết quả]                  |
+-------------------------------------------------------------------------+

So sánh đặc tính các cấu trúc và thuật toán triển khai

Thuật toán	Cấu trúc dữ liệu chính	Cơ chế xác định hỗ trợ	Chiến lược cắt tỉa	Đặc điểm hiệu năng
TFWIT	Tidset (Vertical format)	Giao danh sách TID giữa các tập mục	Cắt tỉa theo ngưỡng hỗ trợ cơ bản	Kích thước Tidset lớn, tốn bộ nhớ và thời gian giao cắt
TFWID	Diffset (Sai khác TID)	Tính tập sai biệt TID giữa các tập mục	Cắt tỉa theo ngưỡng hỗ trợ cơ bản	Giảm bộ nhớ so với Tidset trên dữ liệu dày, nhưng vẫn hạn chế nén
TFWIN	WN-list (Weighted N-list)	Giao danh sách nút dựa trên mã hóa cây	Cập nhật danh sách Top-$k$ thông thường	Khả năng nén dữ liệu cao, tốc độ tính toán mức hỗ trợ vượt trội
TFWIN+	WN-list kết hợp Pruning	Giao danh sách nút WN-list tối ưu	Cắt tỉa sớm/động (Early Pruning Strategy)	Tối ưu hóa thời gian chạy và bộ nhớ, loại bỏ sớm các nhánh dư thừa

Quá trình triển khai Java cho TFWIN và TFWIN+ được xây dựng theo các module: module đọc và chuẩn hóa cơ sở dữ liệu có trọng số, module xây dựng cây tiền tố và ánh xạ WN-list, module quản lý hàng đợi ưu tiên cho Top-rank-$k$, và module thực thi cắt tỉa nhánh động.

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

Thông qua việc nghiên cứu lý thuyết, thiết kế thuật toán và đánh giá thực nghiệm, đồ án đã đạt được các kết quả và đóng góp cụ thể sau:

1. Về mặt thuật toán và cấu trúc dữ liệu:

   • Xây dựng thành công cấu trúc WN-list cho bài toán khai thác tập phổ biến có trọng số, giúp nén không gian lưu trữ hiệu quả hơn so với cấu trúc dọc Tidset và Diffset.
   • Phát triển hoàn chỉnh thuật toán TFWIN và đề xuất thuật toán cải tiến TFWIN+ tích hợp chiến lược cắt tỉa sớm (early pruning strategy), giúp thu hẹp đáng kể không gian trạng thái cần duyệt.

2. Về mặt triển khai và kết quả thực nghiệm:

   • Hoàn thành việc lập trình và thử nghiệm các thuật toán TFWIN và TFWIN+ trên nền tảng Java.
   • Thử nghiệm thực nghiệm ở Chương 6 đã kiểm chứng định lượng về thời gian chạy và mức độ sử dụng bộ nhớ giữa các phương pháp. Kết quả cho thấy TFWIN+ đạt hiệu quả tối ưu nhất trong nhóm các thuật toán được thử nghiệm, vượt trội hơn TFWIT, TFWID và TFWIN về cả tốc độ thực thi lẫn khả năng tiết kiệm tài nguyên bộ nhớ.

3. Về mặt giá trị ứng dụng:

   • Giải quyết hiệu quả vấn đề bùng nổ số lượng mẫu bằng cách giới hạn kết quả theo Top-rank-$k$, giúp người dùng nhận được tập kết quả cô đọng, có trọng số cao nhất để phục vụ trực tiếp cho việc sinh luật kết hợp trong các hệ thống hỗ trợ ra quyết định.

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

Dựa trên phạm vi và nội dung được trình bày trong đồ án, một số hạn chế và hướng phát triển mở rộng bao gồm:

• Hạn chế:
  • Phạm vi thử nghiệm thực nghiệm chủ yếu tập trung so sánh nội bộ giữa các biến thể thuật toán đề xuất (TFWIT, TFWID, TFWIN, TFWIN+) trên một số tập dữ liệu đại diện, chưa khảo sát sâu trên các môi trường phân tán hoặc dữ liệu phân luồng (data stream).
  • Thuật toán tập trung vào bài toán Top-rank-$k$ FWIs đầy đủ; việc kết hợp trực tiếp cấu trúc WN-list với các biểu diễn rút gọn như tập đóng (FCIs) hoặc tập tối đa (MFIs) trong cùng một mô hình chưa được triển khai chi tiết.
• Hướng nghiên cứu tiếp:
  • Mở rộng chiến lược cắt tỉa sớm của TFWIN+ để khai thác trực tiếp các tập phổ biến đóng có trọng số (Closed FWIs) hoặc tập tối đa có trọng số (Maximal FWIs) thuộc Top-rank-$k$.
  • Nghiên cứu tối ưu hóa cấu trúc bộ nhớ và song song hóa thuật toán TFWIN+ nhằm xử lý các cơ sở dữ liệu có quy mô cực lớn (Big Data).

Giá trị tham khảo

Đồ án là tài liệu tham khảo hữu ích cho:

• Sinh viên và học viên ngành Công nghệ Thông tin, Khoa học Dữ liệu: Nắm vững phương pháp phân tích, thiết kế giải thuật khai phá dữ liệu, hiểu rõ nguyên lý hoạt động từ các thuật toán cơ bản (Apriori, Eclat) đến các cấu trúc nâng cao (Tidset, Diffset, N-list, WN-list).
• Người nghiên cứu về khai phá mẫu (Pattern Mining): Cung cấp tài liệu tham khảo chi tiết về công thức toán học tính toán mức hỗ trợ có trọng số, cơ chế xếp hạng Top-rank-$k$, mã giả thuật toán và mã nguồn Java hoàn chỉnh của TFWIN và TFWIN+.
• Phần đáng tham khảo nhất: Chương 4 và Chương 5, nơi trình bày chi tiết định nghĩa, cấu trúc dữ liệu WN-list, các bước cài đặt Java và phân tích độ phức tạp của chiến lược cắt tỉa sớm.

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

1. Đề tài giải quyết bài toán cốt lõi nào trong khai phá dữ liệu?
Đề tài giải quyết 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ố (Top-rank-$k$ Frequent Weighted Itemsets - FWIs), nhằm xử lý thông tin trọng số của từng sản phẩm và kiểm soát số lượng mẫu sinh ra ở mức $k$ hạng cao nhất.

2. Mức hỗ trợ có trọng số (weighted support) của một tập mục được tính như thế nào?
Trọng số của một giao dịch được tính bằng trung bình cộng trọng số của các mục có trong giao dịch đó. Mức hỗ trợ có trọng số của một tập mục được xác định bằng tỷ lệ giữ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 trong cơ sở dữ liệu.

3. Thuật toán TFWIN giải quyết nhược điểm gì của TFWIT và TFWID?
TFWIT và TFWID sử dụng cấu trúc Tidset và Diffset gặp hạn chế về khả năng nén dữ liệu, dẫn đến dung lượng bộ nhớ lớn và thời gian chạy kéo dài. TFWIN sử dụng cấu trúc danh sách nút WN-list (Weighted N-list) giúp nén dữ liệu hiệu quả và tăng tốc độ tính toán mức hỗ trợ.

4. Điểm cải tiến chính của thuật toán TFWIN+ so với TFWIN là gì?
TFWIN+ tích hợp chiến lược cắt tỉa sớm (early pruning strategy / dynamic pruning) vào cấu trúc WN-list của TFWIN, cho phép loại bỏ sớm các nhánh không gian tìm kiếm không thỏa mãn điều kiện lọt vào nhóm Top-rank-$k$, từ đó giảm thiểu số phép tính và tối ưu hóa thời gian chạy.

5. Kết quả đánh giá thực nghiệm ở Chương 6 đưa ra kết luận gì về 4 thuật toán?
Kết quả thử nghiệm thực nghiệm so sánh thời gian chạy và mức độ sử dụng bộ nhớ chỉ ra rằng TFWIN+ là thuật toán đạt hiệu năng tốt nhất trong số các phương pháp được thử nghiệm (TFWIT, TFWID, TFWIN, TFWIN+).

Kết luận

Đồ án "Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning strategy" của sinh viên Nguyễn Triệu Vi và Trần Thành Đạt (Trường Đại học Tôn Đức Thắng) đã giải quyết hiệu quả bài toán khai thác tập phổ biến trên cơ sở dữ liệu có trọng số. Bằng việc ứng dụng cấu trúc WN-list và chiến lược cắt tỉa sớm, nghiên cứu đã xây dựng thành công thuật toán TFWIN+, khắc phục những nhược điểm về thời gian chạy và tiêu hao bộ nhớ của các phương pháp Tidset/Diffset truyền thống. Kết quả thực nghiệm và mã nguồn Java hoàn chỉnh của đồ án đóng góp một giải pháp kỹ thuật có giá trị tham khảo cao trong lĩnh vực phân tích thuật toán và khai phá dữ liệu.

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

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.