Chương 1 giới thiệu các khái niệm cơ sở liên quan; phương pháp khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao. Chương 2 trình bày mô hình CWU, các thuật toán khai phá tập lợi ích cao dựa trên mô hình CWU như: HP, PPB, CTU-PRO+. Chương 3 trình bày cấu trúc cây mẫu lợi ích nén (CUP) kết hợp danh sách lợi ích và thuật toán HUI-Growth khai phá tập lợi ích cao dựa trên cấu trúc cây CUP; trình bày cấu trúc cắt tỉa RTWU và hai thuật toán tuần tự, song song khai phá tập lợi ích cao dựa trên cấu trúc cắt tỉa tập ứng viên RTWU là EAHUI- Miner, PEAHUI-Miner. TỔNG QUAN VỀ KHAI PHÁ TẬP PHỔ BIẾN Chương này trình bày các khái niệm liên quan đến khai phá tập phổ biến, luật kết hợp, tập phổ biến có trọng số, tập lợi ích cao; phân loại các phương pháp khai phá tập phổ biến, tập phổ biến có trọng số, tập lợi ích cao và phân tích những ưu điểm, hạn chế của chúng.
Đề xuất thuật toán khai phá tập phổ biến có trọng số theo chiều dọc [I]. Giới thiệu chung Khai phá tập phổ biến là tìm ra các tập phần tử có số lần xuất hiện lớn hơn một ngưỡng hỗ trợ tối thiểu (minsupp). Tuy nhiên, khai phá tập phổ biến có những hạn chế. Thứ nhất, nó xử lý tất cả các phần tử có tầm quan trọng như nhau.
Thứ hai, trong một giao dịch mỗi phần tử chỉ có trạng thái xuất hiện hoặc không xuất hiện. Rõ ràng những hạn chế này làm cho bài toán khai phá tập phổ biến truyền thống không phù hợp với các cơ sở dữ liệu thực tế, ví dụ như trong cơ sở dữ liệu của siêu thị, mỗi mặt hàng có tầm quan trọng hay giá cả khác nhau, số lượng mua các mặt hàng trong mỗi giao dịch cũng khác nhau,… Vì vậy, mô hình khai phá tập phổ biến chỉ phản ánh mối tương quan giữa các phần tử xuất hiện trong cơ sở dữ liệu, nhưng không phản ánh ý nghĩa của từng phần tử dữ liệu. Để khắc phục những nhược điểm trên có hai mô hình được đưa ra: Tập phổ biến có trọng số - WFI và Tập lợi ích cao - HUI. Trong đó, mỗi phần tử có một trọng số khác nhau như: lợi ích, giá cả, độ quan trọng hay số lượng,…Một tập các phần tử được xem là phổ biến có trọng số khi giá trị có trọng số của chúng lớn hơn một ngưỡng cho trước.
Từ mô hình này nhiều 17 thuật toán khai phá tập phổ biến có trọng số được đưa ra [11], [72], [64], [33], [58], [73],… Năm 2003 Chan [13] và cộng sự đã đưa ra mô hình khai phá tập lợi ích cao (High Utility Itemsets – HUI), khắc phục những hạn chế của mô hình khai phá tập phổ biến và tập phổ biến có trọng số. Mô hình này cho phép người sử dụng đánh giá được tầm quan trọng của từng phần tử qua hai trọng số khác nhau gọi là lợi ích trong và lợi ích ngoài. Lợi ích trong có thể là số lượng từng phần tử trong giao dịch; lợi ích ngoài có thể là lợi nhuận hoặc giá cả của các mặt hàng. Lợi ích của một phần tử là tích hai giá trị lợi ích trong và lợi ích ngoài.
Một tập phần tử được gọi là tập lợi ích cao khi giá trị lợi ích của nó lớn hơn một ngưỡng do người dùng định nghĩa trước. Nhờ khai phá tập lợi ích cao có thể đưa ra một số quyết định quan trọng như tối đa hóa doanh thu, giảm thiểu chi phí, hạn chế hàng tồn kho,… 1. Tập phổ biến Khai phá tập phổ biến là quá trình tìm kiếm tập các phần tử có số lần xuất hiện lớn hơn một ngưỡng cho trước và vấn đề này được R. Swami [5] đề xuất năm 1993, xuất phát từ nhu cầu bài toán phân tích dữ liệu trong cơ sở dữ liệu giao dịch, nhằm phát hiện các mối quan hệ giữa các tập hàng hóa đã bán tại siêu thị.
Việc xác định này không phân biệt sự khác nhau giữa các hàng hóa, chỉ dựa vào sự xuất hiện của chúng. Phần tiếp theo đây nêu một số khái niệm cơ sở liên quan đến bài toán luật kết hợp và tập phổ biến. Khái niệm cơ sở Cho D = {T1, T2,…Tm} là cơ sở dữ liệu giao dịch và I = {i 1, i2,…,in} là tập các phần tử trong cơ sở dữ liệu D. Mỗi giao dịch T i I.
Tập X I có k phần tử được gọi là tập k-phần tử.1) | D| Tập phổ biến thường dùng để sinh luật kết hợp. Luật kết hợp với dạng X Y, với X, Y là hai tập phần tử, được xác định thông qua hai khái niệm độ hỗ trợ và độ tin cậy của luật được định nghĩa như sau: Định nghĩa 1. [6] Độ tin cậy của luật X Y là tỉ số của số giao dịch trong D, kí hiệu là Confidence(X Y), chứa X Y và số giao dịch trong D có chứa tập X.3) Support( X) Định nghĩa 1. [6] Tập phần tử X được gọi là tập phổ biến nếu có Support(X) ≥ minsupp, với minsupp là ngưỡng hỗ trợ tối thiểu cho trước.
[6] Luật X Y được gọi là tin cậy nếu có Confidence(X Y) ≥ minconf, với minconf là ngưỡng tin cậy tối thiểu cho trước. Tập phổ biến có một số tính chất sau: Tính chất 1. [4] (Tính chất đóng của tập phần tử) Giả sử X, Y là hai tập phần tử, X, Y I. Nếu Y là tập phổ biến và X Y thì X cũng là tập phổ biến.
[4] Cho X, Y là hai tập phần tử, X Y và X là tập không phổ biến thì Y cũng là tập không phổ biến. Một số phương pháp khai phá tập phổ biến CHƯƠNG 2. Phương pháp dựa trên quan hệ kết nối Phương pháp thường được sử dụng là dựa vào việc kết nối để sinh tập ứng viên (k+1)-phần tử từ tập phổ biến k-phần tử, sau đó duyệt lại cơ sở dữ liệu giao dịch để xác nhận. Trong các phương pháp này, thuật toán Apriori là phổ biến và đơn giản nhất.
Srikant [6] đưa ra thuật toán Apriori dựa trên phương pháp kết nối. Thuật toán này xử lý từng mức một (level-wise), nghĩa là xác định các tập phổ biến có k-phần tử, rồi mới xác định tập phổ biến (k+1)-phần tử. Điều này đưa tới tính chất cơ bản của thuật toán Apriori là mọi tập con của tập phổ biến cũng là tập phổ biến. Vì vậy, các ứng viên phổ biến có chiều dài (k+1)-phần tử có thể được sinh ra bằng cách kết hợp các tập phổ biến có k- phần tử.
Một phép nối để tạo ra tập có k-phần tử được thực hiện khi (k-1)- phần tử chung. Để giảm số lượng ứng viên được sinh ra, tính chất đóng của tập phổ biến được sử dụng. Tính chất này đảm bảo rằng nếu trong tập k-phần 20 tử có tập con không phổ biến thì chắc chắn tập k-phần tử này cũng không phổ biến. Do vậy, có thể cắt tỉa tập này đi mà không cần xét tiếp.
Thuật toán DHP [45] được đề xuất dựa trên phương pháp Apriori, sử dụng phương pháp cắt tỉa và băm. Hai cách tối ưu cải thiện tốc độ thuật toán: cách thứ nhất là dựa vào việc cắt tỉa các ứng viên trong mỗi lần lặp và cách thứ hai là cắt tỉa các giao dịch để tính nhanh độ hỗ trợ. Phương pháp sử dụng cấu trúc cây Phương pháp sử dụng cấu trúc cây dựa trên kỹ thuật liệt kê tập hợp. Các ứng viên được xác định nhờ sử dụng đồ thị con của đồ thị các tập phần tử (Hình 1.1), còn được gọi là cây từ điển hoặc cây liệt kê [3].
Khi đó, việc sinh các tập phổ biến tương ứng với việc xây dựng cây từ điển. Cây có thể khai phá theo chiều rộng hoặc chiều sâu. Cấu trúc cây từ điển được xem là cơ sở cho phát triển thuật toán. Cây từ điển (hoặc cây liệt kê) 21 Thuật toán AIS [5] sử dụng cây từ điển, được xây dựng theo kiểu từng bước một.
Các tập phần tử được đưa ra ở mỗi mức gần với sử dụng cơ sở dữ liệu giao dịch. Thuật toán kết hợp các phần tử theo thứ tự từ điển để sinh tập ứng viên, sau đó đếm độ hỗ trợ của các tập ứng viên trên cơ sở dữ liệu giao dịch. Đây là phương pháp đơn giản khai phá toàn bộ không gian tìm kiếm. Thuật toán Eclat [74] sử dụng cách tiếp cận theo chiều rộng trước (breadth- first) dựa trên phép giao tập tid của tập phần tử giống như thuật toán của Savasere [51], sau đó phân chia các ứng viên vào các nhóm rời nhau, sử dụng cách tiếp cận phân vùng ứng viên tương tự như thuật toán Apriori song song.
Thuật toán Eclat [74] được trình bày hợp lý nhất trên cây từ điển với phép duyệt cây theo chiều rộng. Thuật toán Monet và Partition [31], [51] đề xuất xác định sự giao nhau đệ quy của danh sách tid (tid-lists) và một số biến thể hiệu quả của mô hình này. Thuật toán VIPER [53] sử dụng phương pháp tiếp cận dọc (vertical) theo tid để khai phá tập phổ biến. Ý tưởng cơ bản của thuật toán này là biểu diễn cơ sở dữ liệu giao dịch theo chiều dọc bằng véc tơ nhị phân.
Véc tơ này được sử dụng để đếm sự xuất hiện của tập ứng viên phổ biến khá hiệu quả. Đây là cách biểu diễn nén khác của tập tid cho phép đạt được một số điểm tối ưu trong thuật toán. Về bản chất, VIPER không khác nhau nhiều so với Eclat về phương pháp đếm. Sự khác biệt chủ yếu là về biểu diễn véc tơ bit nén và xử lý hiệu quả biểu diễn này.
Phương pháp tăng trưởng đệ quy dựa trên hậu tố Phương pháp FP-growth [30] tìm kiếm mẫu dựa trên hậu tố, sử dụng cấu trúc cây mẫu phổ biến (FP-tree) để biểu diễn CSDL giao dịch làm cho việc tính độ hỗ trợ của tập phần tử nhanh hơn. Cây mẫu phổ biến [30] biểu diễn 22 dạng nén của CSDL giao dịch, được xây dựng theo thứ tự giảm dần độ hỗ trợ của các phần tử từ gốc đến lá. Mỗi cây FP có thể xem như một cấu trúc dữ liệu cây dựa trên tiền tố (prefix-based) của CSDL giao dịch chứa các phần tử phổ biến. Do vậy, mỗi nút được gán nhãn là một phần tử nào đó và lưu trữ độ hỗ trợ của tập phần tử gồm những phần tử trên đường đi từ một nút bất kỳ đến nút gốc.
Thuật toán CT-PRO [57], sử dụng cấu trúc cây mẫu phổ biến mới gọi là cây nén mẫu phổ biến (CFP-Compact Frequent Pattern) chứa đủ các thông tin như trong cây FP, nhưng chỉ chiếm 50% lượng lưu trữ [57].