Apriopi + FPGrowth Algorithm (Khai phá luật kết hợp)

 

Thuật toán tìm tập phổ biến:

B1: Đếm số lần xuất hiện của mỗi item trong db (có thể dùng map c++)

B2: Loại bỏ item (trong map) có số lần xuất hiện nhỏ hơn min_sup (ví dụ loại bỏ item có số lần xuất hiện<4)

B3: Xây dựng itemset gồm 2 phần tử từ map bằng for(i, 1, n-1) và for(j, i+1, n) 

B4: Đếm số lần xuất hiên của mỗi itemset trong db (có thể dùng map2 c++)

B5: Loại bỏ những itemset có số lần xuất hiện nhỏ hơn min_sup

B6: Xây dựng itemset gồm 3 phần tử từ map bằng for(i, 1, n-1) và for(j, i+1, n) 

B7: Lặp lại cho đến khi mapX chỉ còn 1 phần tử

Trong Apriori-gen, tập cha bị loại bỏ khi tồn tại một tập con trong tập cha không xuất hiện (ví dụ hình dưới)

THUẬT TOÁN FP Growth

B1: Tính tần suất 

B2: Sắp xếp tần suất giảm dần + loại bỏ những tần suất < minsup

B3: Tạo bảng item phổ biến từ CSDL và tần suất trên

B4: Vẽ cây fp tree

B5: Tạo bảng :

+Cột item: sắp xếp tăng dần tần suất

+Cơ sở mẫu điều kiên: lấy key từ nút [cha, root) và value là giá trị (số lần vẽ) của node con

+ FP tree dk: gộp các cơ sở mẫu đk và chỉ chọn > min_sup

+ Tập thường xuyên: item, sinh các tổ hợp FPtreedk + item

Sinh các luật kết hợp 

Độ đo LIFT:

ĐỘ đo Leverage

    

TLTK: