Giới thiệu
Có một số biến thể của thuật toán Apriori được đề xuất nhằm cải thiện hiệu suất của thuật toán gốc. Dưới đây là 4 kỹ thuật chính:
1. Kỹ thuật dựa trên băm (Hash-based technique)
Băm các mục hàng (itemsets) vào các bucket tương ứng. Giảm kích thước tập ứng cử k-itemsets Cₖ cho k > 1.
Ví dụ: Khi quét mỗi giao dịch để tạo tập mục hàng thường xuyên 1-itemsets L₁ từ ứng cử 1-itemsets C₁, có thể tạo một số 2-itemsets cho mỗi giao dịch, băm (ánh xạ) chúng vào các bucket của bảng băm, tăng bộ đếm bucket tương ứng.
2. Giảm giao dịch (Transaction reduction)
Một giao dịch không chứa bất kỳ k-itemsets thường xuyên nào thì cũng không chứa (k+1)-itemsets thường xuyên. Giao dịch đó có thể đánh dấu hoặc xóa khỏi xem xét tiếp theo vì các lần quét sau cho j-itemsets (j > k) sẽ không cần nó.
3. Phân vùng (Partitioning)
Kỹ thuật phân vùng cần 2 lần quét CSDL để khai thác tập mục hàng thường xuyên. Hai giai đoạn:
- Giai đoạn I: Chia giao dịch của D thành n phân vùng không chồng chéo. Nếu ngưỡng hỗ trợ tối thiểu cho D là min_sup, ngưỡng hỗ trợ cho phân vùng = min_sup × số giao dịch trong phân vùng đó. Tìm tất cả tập mục hàng thường xuyên cục bộ (local frequent itemsets) trong mỗi phân vùng. Dùng cấu trúc dữ liệu ghi TID giao dịch chứa mục hàng để tìm tất cả local frequent k-itemsets chỉ trong 1 lần quét.
- Giai đoạn II: Quét thứ 2 của D để đánh giá hỗ trợ thực tế của mỗi ứng cử, xác định global frequent itemsets. Mọi tập mục hàng có thể thường xuyên toàn cục phải xuất hiện là thường xuyên cục bộ trong ít nhất một phân vùng.
4. Lấy mẫu (Sampling)
Ý tưởng cơ bản: chọn mẫu ngẫu nhiên S của dữ liệu D, tìm tập mục hàng thường xuyên trong S thay vì D. Trao đổi độ chính xác đổi lấy hiệu suất. Kích thước mẫu S đủ nhỏ để tìm tập mục hàng thường xuyên trong S hoàn thành trong bộ nhớ chính, chỉ cần 1 lần quét giao dịch trong S tổng thể.