Trước khi thực hiện việc phát sinh nhanh tập ứng viên, thì tập phổ biến 1-phần
tử phải được thực hiện trước. Tất cả tập không phổ biến 1-phần tử phải được lược bỏ để làm giảm kích thước của BitTable và cải thiện hiệu quả của tiến trình phát sinh ứng
tid A B C D E 1 1 0 1 1 0 2 0 1 1 0 1 3 1 1 1 0 1 4 0 1 0 0 1 BitTable 10 7 14 8 7
viên, vì tất cả tập không phổ biến 1-phần tử không có ích cho tiến trình phát sinh ứng
viên kế tiếp[6].
Kế đến, tập phổ biến 1-phần tử được sắp xếp theo thứ tự ký tự và mỗi mục dữ
liệu được đánh dấu bởi ký tự định danh. Sau khi tập phổ biến 2-phần tử được phát sinh,
tập các mục dữ liệu phổ biến được xây dựng.
Theo Apriori, tập ứng viên Ck+1 được xây dựng bằng cách giao hai mục dữ liệu
của Lk trong đó có (k-1) phần tử giống nhau. Trong mỗi thành phần E1 trong tập phổ
biến của BitTable BLk, một biến MID được phát sinh bằng cách thay thế bit 1 cuối
cùng của E1 với 0. Với mỗi thành phần E2 sau E1, phép dịch chuyển bitwise và toán tử & được thực hiện với MID. Nếu kết quả trả về bằng MID, thì E1 và E2 trong Lk có (k- 1) mục dữ liệu giống nhau. Khi đó, việc phát sinh tập các ứng viên bằng việc thực hiện
phép dịch chuyển bitwise trên E1 và E2 và các tập ứng viên này được thêm vào BitTable BCk+1.
Việc nén các tập phổ biến vào BitTable đã tiết kiệm nhiều bộ nhớ và tính toán bằng bitwise và phép toán and/or nhanh hơn rất nhiều so với việc so sánh mỗi mục dữ
Hình 3.1- Minh họa tiến trình tìm tập ứng viên
Ví dụ: Với dữ liệu ở bảng 3.1, minsup=2
Sau khi duyệt CSDL lần đầu tiên, L1={1, 2, 3, 5} được sinh ra, mục dữ liệu 4
không là tập phổ biến, vì thế tập phổ biến 1-phần tử được sắp xếp lại thành L1={1, 2,
3, 4} để làm giảm kích thước của BitTable. Như vậy, ta có 4 tập phổ biến 1-phần tử, thì chiều dài của BitTable là 4.
Sau khi BitTableFI hoàn thành, các tập phổ biến sẽ được trả lại giá trị ban đầu.
Input: tập ứng viên BitTable BLk
Có E1 trong BLk?
Tính MID bằng cách thay thế bit 1
cuối cùng của E1 thành 0
Có E2 sau E1 trong BLk?
Nếu MID&E2=MID thì thêm E1│E2 vào BCk+1
Output: BCk+1 Yes
Yes
No No
Thực hiện tính C1={{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}
Và L2 được sinh ra như sau L2={{1,3}, {2,3}, {2,4}, {3,4}} các bit nhị phân tương ứng của BitTable BL2 sẽ là {{1 0 1 0}, {0 1 1 0}, {0 1 0 1}, {0 0 1 1}}. Vì thế
các giá trị tương ứng của BitTable BL2 sẽ là {10 6 5 3}.
Tập {1, 3} có MID=8 vì ta thay thế bit 1 cuối cùng của {1, 3} (tương ứng là {1 0 10} ) với 0 ta được {1 0 0 0}. Sau đó ta thực hiện phép dịch chuyển bitwise và phép toán and trên tập {6, 5, 3} (tương ứng là {2, 3} {2, 4} {3, 4}) và kết quả là không có tập nào được sinh ra.
Tương tự, xét tập {2, 3} có MID=4, thực hiện phép dịch chuyển bitwise trên tập {5, 3} (tương ứng {2, 4} {3, 4}) và kết quả ta có {2, 3, 4}
L2
Hình 3.2- Minh họa tiến trình phát sinh nhanh tập ứng viên
itemset support {1, 3} 2 {2, 3} 2 {2, 5} 3 {3, 5} 2 L2[i], L2[j] BitTable BL2 {1, 3}{2, 3} 10, 6 {1, 3}{2, 4} 10, 5 {1, 3}{3, 4} 10, 3 {2, 3}{2, 4} 6, 5 {2, 3}{3, 4} 6, 3 {2, 4}{3, 4} 5, 3
MID(L2[i]) MID&L2[j] BitTable BC3
8 0 8 0 8 0 4 4 7{2, 3, 4} 4 0 4 0