Bài giảng Khai quá dữ liệu - Chương 3: Kết luận hợp

ữa,... 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
Định dạng thể hiện đặc trưng cho các luật kết hợp: 
- Khăn  Bia [0.5%,60%] 
- Mua:Khăn  Mua:Bia [0.5%,60%] 
- NẾU mua khăn THÌ mua bia trong 60% trường hợp. 
Khăn và bia được mua chung trong 0.5% dòng dữ liệu 
Các hình thức biểu diễn khác: 
- Mua(x,”khăn”)  Mua(x,”bia”) [0.5%,60%] 
- Khoa(x, “CNTT”) ^ Học(x,”DB”)  Điểm(x,”A”) 
[1%,75%] 
Các hướng tiếp cận luật kết hợp 
Chương 3: Luật kết hợp 
Luật kết hợp nhị phân (Binary Association Rule): 
Các thuộc tính chỉ được quan tâm là có hay không xuất 
hiện trong giao tác của cơ sở dữ liệu (không quan tâm về 
“mức độ“ xuất hiện) 
Ví dụ: 
- Việc gọi 10 cuộc điện thoại và 1 cuộc được xem là giống 
nhau (có cuộc gọi hay không – Có hay Không?) 
- NẾU “gọi liên tỉnh=‟yes‟ AND gọi di động=”yes” 
 THÌ gọi quốc tế=‟yes‟ AND gọi dịch vụ 108 = „yes‟ 
 với độ hỗ trợ 20% và độ tin cậy 80%” 
Các hướng tiếp cận luật kết hợp 
Chương 3: Luật kết hợp 
Luật kết hợp có thuộc tính số và thuộc tính hạng mục 
(Quantitative And Categorial Association Rule) 
Các thuộc tính của các cơ sở dữ liệu có kiểu đa dạng (nhị 
phân – binary, số – quantitative, hạng mục – categorial, ...) 
 Rời rạc hoá nhằm chuyển dạng luật này về dạng nhị 
phân 
Ví dụ: 
NẾU phương thức gọi=‟Tự động‟ 
 AND giờ gọi ∈ „23:00...23:59‟ 
 AND Thời gian đàm thoại ∈ „20.. 30 phút‟ 
THÌ gọi liên tỉnh =‟có‟ , 
 với độ hỗ trợ là 23. 53% , và độ tin cậy là 80%”. 
Các hướng tiếp cận luật kết hợp 
Chương 3: Luật kết hợp 
Luật kết nhiều mức (Multi-level Association Rule) 
Dạng luật đầu là dạng luật tổng quát hoá của dạng luật sau 
và tổng quát theo nhiều mức khác nhau 
Ví dụ: 
Luật có dạng: 
 NẾU mua máy tính PC 
 THÌ mua hệ điều hành 
 AND mua phần mềm tiện ích văn phòng 
thay vì chỉ những luật quá cụ thể: 
 NẾU mua máy tính iBM PC 
 THÌ mua hệ điều hành Microsoft Windows 
 AND mua phần mềm Microsoft Office 
Các hướng tiếp cận luật kết hợp 
Chương 3: Luật kết hợp 
Luật kết hợp mờ (Fuzzy Association Rule) 
Trong quá trình rời rạc hoá các thuộc tính số, luật kết hợp 
mờ nhằm khắc phục các hạn chế và chuyển luật kết hợp về 
một dạng tự nhiên hơn, gần gũi hơn với người sử dụng 
Ví dụ: 
NẾU thuê bao tư nhân = „yes‟ 
 AND thời gian đàm thoại lớn (Thuộc tính được mờ hóa) 
 AND cước nội tỉnh = „yes‟ 
THÌ cước không hợp lệ = „yes‟ 
 với độ hỗ trợ 4% và độ tin cậy 85%”. 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
Phân tích định dạng luật kết hợp: 
NẾU mua khăn THÌ mua bia trong 60% trường hợp. Khăn 
và bia được mua chung trong 0.5% dòng dữ liệu 
Khăn  Bia [0.5%,60%] 
1. Tiền đề: Khăn (vế trái) 
2. Mệnh đề kết quả: Bia (vế phải, đầu) 
3. Support: 0.5% - tần số (hay độ hỗ trợ, độ phổ biến) – 
trong bao nhiêu % dữ liệu thì những điều ở vế trái và 
vế phải cùng xảy ra? 
4. Confidence: 60% - độ mạnh (hay xác suất điều kiện, độ 
tin cậy, độ gắn kết) – nếu vế trái xảy ra thì có bao nhiêu 
khả năng vế phải xảy ra? 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
Độ ủng hộ: Biểu thị tần số luật có trong các giao tác 
Độ tin cậy: biểu thị số phần trăm giao tác có chứa luôn B 
trong các giao tác có chứa A 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
Độ ủng hộ tối thiểu (min support): 
- Cao:  ít tập phần tử (itemset) phổ biến 
 ít luật hợp lệ rất thường xuất hiện 
- Thấp:  nhiều luật hợp lệ hiếm xuất hiện 
Độ tin cậy tối thiểu (min confidence): 
- Cao:  ít luật nhưng tất cả “gần như dúng” 
- Thấp: nhiều luật, phần lớn rất “không chắc 
chắn” 
Giá trị tiêu biểu: 
minsupport: 2-10%, minconfidence: 70-90% 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
item và itemsets: 
i = { i1, i2, , in } là tập bao gồm n mục (item – còn gọi là 
thuộc tính – attribute). X ⊆ i được gọi là tập mục (itemset). 
Giao tác: 
T = { t1, t2, , tm} là tập gồm m giao tác (Transaction – còn 
gọi là bản ghi –record). Mỗi giao tác được định danh bởi 
TiD (Transaction identification). 
Tập phần tử phổ biến: 
Tập các phần tử có độ ủng hộ (support) ≥ độ ủng hộ tối 
thiểu (minsupport) 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
Cho: CSDL các giao tác, mỗi giao tác là 
một danh sách mặt hàng được mua 
(trong một lượt mua của khách hàng). 
Tìm tất cả các luật với minsupport=50% và 
minconfidence=50% 
Tid Hàng mua 
100 A B C 
200 A C 
400 A D 
500 B E F 
Quá trình 2 bước để khai phá luật kết hợp: 
- Bước 1: Tìm các tập phổ biến: các tập các phần tử có độ support tối thiểu. 
 * Mẹo Apriori: tập con của tập phổ biến cũng là một tập phổ biến 
 VD: Nếu {AB} là tập phổ biến thì {A} và {B} là tập phổ biến 
 * Lặp việc tìm tập phổ biến với kích thước từ 1 đến k (tập kích 
thước k) 
- Bước 2: Dùng các tập phổ biến để tạo các luật liên kết 
Khai phá luật kết hợp 
Chương 3: Luật kết hợp 
Tid Hàng mua 
100 A B C 
200 A C 
400 A D 
500 B E F 
Tập Độ phổ biến 
{A} 3=75% 
{B} 2=50% 
...... 
{A} và {B} 1=25% 
{A} và {C} 2=50% 
...... 
Tập phổ biến Độ tin cậy 
{A, C} = 50% 2/3=66,6% 
{C, A} = 50% 2/2=100% 
- A  C [50%,66.6%] 
- C A [50%,100%] 
Các tập phổ biến với mẹo Apriori 
Chương 3: Luật kết hợp 
1. Bước kết hợp: Ck được tạo bằng cách kết Lk-1 với chính nó 
2. Bước rút gọn: Những tập kích thước k-1 không phổ biến thì không thể là 
tập con của tập phổ biến kích thước k 
3. Mã giả: 
Ck là tập ứng viên có kích thước k 
Lk là tập phổn biến có kích thước k 
L1={các phần tử phổ biến} 
FOR (k=1;Lk != NULL; k++) 
 Ck+1 ={các ứng viên được tạo từ Lk} 
 FOR mỗi giao tác t trong database 
 tăng số đếm của tất cả các ứng viên trong Ck+1 mà được 
 chứa trong t 
 Lk+1={các ứng viên trong Ck+1 có độ ủng hộ tối thiểu} 
 END FOR 
RETURN ∪ 𝒌Lk 
Tìm tập ứng viên với mẹo Apriori 
Chương 3: Luật kết hợp 
Nguyên tắc Apriori: 
Những tập con của tập phổ biến cũng phải phổ biến 
Ví dụ: 
Ta có: L3 = {abc,abd,acd,ace,bcd} 
 Tự kết: 
 * {abcd} 
 * {abce} 
 * {acde} 
 Rút gọn: 
 * {abce} bị loại vì bce không có trong L3 
 * {acde} bị loại vì ade không có trong L3 
 C4 = {abcd} 
Khai phá luật kết hợp với Apriori 
Chương 3: Luật kết hợp 
Database D 
Tid Hàng mua 
100 1 3 4 
200 2 3 5 
300 1 2 3 5 
400 2 5 
Duyệt D 
Tập Độ ủng hộ 
{1} 2=50% 
{2} 3=75% 
{3} 3=75% 
{4} 1=25% 
{5} 3=75% 
C1 L1 
Tập Độ ủng hộ 
{1} 2=50% 
{2} 3=75% 
{3} 3=75% 
{5} 3=75% 
Tập 
{1,2} 
{1,3} 
{1,5} 
{2,3} 
{2,5} 
{3,5 
C2 
Duyệt D 
Tập Độ ủng hộ 
{1,2} 1=25% 
{1,3} 2=50% 
{1,5} 1=25% 
{2,3} 2=50% 
{2,5} 3=75% 
{3,5 2=50% 
C2 L2 
Tập Độ ủng hộ 
{1,3} 2=50% 
{2,3} 2=50% 
{2,5} 3=75% 
{3,5 2=50% 
Khai phá luật kết hợp với Apriori 
Chương 3: Luật kết hợp 
Tập 
{2,3,5} 
C3 
Duyệt D 
Tập Độ ủng hộ 
{2,3,5} 2=50% 
C3 L3 
Tập Độ ủng hộ 
{2,3,5} 2=50% 
Không gian tìm kiếm của CSDL D 
Chương 3: Luật kết hợp 
Không gian tìm kiếm của CSDL D 
Áp dụng mẹo tìm kiếm Apriori trên cấp 1 
Chương 3: Luật kết hợp 
Không gian tìm kiếm của CSDL D 
Áp dụng mẹo tìm kiếm Apriori trên cấp 2 
Chương 3: Luật kết hợp 
Rút các luật kết hợp từ các tập 
Chương 3: Luật kết hợp 
Mã giả: 
FOR mỗi tập phổ biến l 
 tạo tất cả các tập con khác rỗng s của l 
FOR mỗi tập con khác rỗng s của l 
 iF support(l)/support(s)≥min_conf 
 cho ra luật s  l-s 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Cho tập mặt hàng i={i1, i2, i3, i4, i5, i6, i7, i8} và tập giao tác O={o1, o2, 
o3, o4, o5, o6} 
Trong đó: 
 O1={i1, i7, i8} 
 O2={i1, i2, i6, i7, i8} 
 O3={i1, i2, i6, i7} 
 O4={i1, i7, i8} 
 O5={i3, i4, i5, i6, i8} 
 O6={i1, i4, i5} 
a. Xây dựng ngữ cảnh khai phá dữ liệu 
b. Tìm các tập phổ biến tối đại với min_supp=0.3 
c. Tìm các luật kết hợp với min_supp=0.3 và min_conf=1.0 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
a. Ngữ cảnh khai thác dữ liệu 
 i1 i2 i3 i4 i5 i6 i7 i8 
O1 1 1 1 
O2 1 1 1 1 1 
O3 1 1 1 1 
O4 1 1 1 
O5 1 1 1 1 1 
O6 1 1 1 
O1 i1 i7 i8 
O2 i1 i2 i6 i7 i8 
O3 i1 i2 i6 i7 
O4 i1 i7 i8 
O5 i3 i4 i5 i6 i8 
O6 i1 i4 i5 
 
Transition database 
Chương 3: Luật kết hợp 
b. Tìm các tập phổ biến tối đại với min_supp=0.3 
Tập Độ ủng hộ 
{i1} =5/6=0.83 
{i2} =2/6=0.33 
{i3} =1/6=0.16 
{i4} =2/6=0.33 
{i5} =2/6=0.33 
{i6} =3/6=0.5 
{i7} =4/6=0.66 
{i8} =4/6=0.66 
C1 
Tập Độ ủng hộ 
{i1} =5/6=0.83 
{i2} =2/6=0.33 
{i4} =2/6=0.33 
{i5} =2/6=0.33 
{i6} =3/6=0.5 
{i7} =4/6=0.66 
{i8} =4/6=0.66 
L1 
i1 i2 i3 i4 i5 i6 i7 i8 
Chương 3: Luật kết hợp 
Tập Độ ủng hộ 
i1, i2 2=0.33 
i1, i4 1=0.16 
i1, i5 1=0.16 
i1, i6 2=0.33 
i1, i7 4=0.66 
i1, i8 3=0.5 
i2, i4 0 
i2, i5 0 
i2, i6 2=0.33 
i2, i7 2=0.33 
i2, i8 1=0.16 
i4, i5 2=0.33 
i4, i6 1=0.16 
i4, i7 0 
i4, i8 1=0.16 
i5, i6 1=0.16 
i5, i7 0 
i5, i8 1=0.16 
i6, i7 2=0.33 
i6, i8 2=0.33 
i7, i8 3=0.5 
C2 L2 
i1 i2 i3 i4 i5 i6 i7 i8 
Tập Độ ủng hộ 
i1, i2 2=0.33 
i1, i6 2=0.33 
i1, i7 4=0.66 
i1, i8 3=0.5 
i2, i6 2=0.33 
i2, i7 2=0.33 
i4, i5 2=0.33 
i6, i7 2=0.33 
i6, i8 2=0.33 
i7, i8 3=0.5 
{i1,i2} {i1,i6} {i1,i7} {i1,i8} {i2,i6} {i2,i7} {i4,i5} {i6,i7} {i6,i8} {i7,i8} 
Chương 3: Luật kết hợp 
Tập Độ ủng hộ 
i1, i2, i6 2=0.33 
i1, i2, i7 2=0.33 
i1, i2, i8 1=0.16 
i1, i6, i7 2=0.33 
i1, i6, i8 1=0.16 
i1, i7, i8 2=0.33 
i2, i6, i7 2=0.33 
i2, i7, i8 1=0.16 
i6, i7, i8 1=0.16 
C3 L3 
i1 i2 i3 i4 i5 i6 i7 i8 
{i1,i2} {i1,i6} {i1,i7} {i1,i8} {i2,i6} {i2,i7} {i4,i5} {i6,i7} {i6,i8} {i7,i8} 
Tập Độ ủng hộ 
i1, i2, i6 2=0.33 
i1, i2, i7 2=0.33 
i1, i6, i7 2=0.33 
i1, i7, i8 2=0.33 
i2, i6, i7 2=0.33 
{i1,i2,i6} {i1,i2,i7} {i1,i6,i7} {i1,i7,i8} {i2,i6,i7} 
Chương 3: Luật kết hợp 
Tập Độ ủng hộ 
i1, i2, i6,i7 2=0.33 
C4 L4 
i1 i2 i3 i4 i5 i6 i7 i8 
{i1,i2} {i1,i6} {i1,i7} {i1,i8} {i2,i6} {i2,i7} {i4,i5} {i6,i7} {i6,i8} {i7,i8} 
Tập Độ ủng hộ 
i1, i2, i6,i7 2=0.33 
{i1,i2,i6} {i1,i2,i7} {i1,i6,i7} {i1,i7,i8} {i2,i6,i7} 
{i1,i2,i6,i7} 
Các tập phổ biến tối đại với min_supp=0.3: 
1. {i4,i5} 
2. {i6,i8} 
3. {i1,i7,i8} 
4. {i1,i2,i6,i7} 
Chương 3: Luật kết hợp 
c. Tìm các luật kết hợp với min_supp=0.3 và min_conf=1.0 
• Xét tập {i4, i5}: 
conf({i4}  {i5}) = 1 OK 
conf({i5}  {i4}) = 1 OK 
• Xét tập {i6, i8}: 
Conf({i6}  {i8}) = 2/4 
Conf({i8}  {i6}) = 2/3 
• Xét tập {i1, i7, i8}: 
Conf({i1}  {i7, i8}) = 2/5 
Conf({i7}  {i1, i8}) = 2/4 
Conf({i8}  {i1, i7}) = 2/4 
Conf({i1, i7}  {i8}) = 2/4 
Conf({i1, i8}  {i7}) = 2/3 
Conf({i7, i8}  {i1}) = 2/3 
• Xét tập {i1, i2, i6, i7}: 
Conf({i1}  {i2, i6, i7}) = 2/5 
Conf({i2}  {i1, i6, i7}) = 2/2 OK 
Conf({i6}  {i1, i2, i7}) = 2/3 
Conf({i7}  {i1, i2, i6}) = 2/4 
Conf({i1, i2}  {i6, i7}) = 2/2 OK 
Conf({i1, i6}  {i2, i7}) = 2/2 OK 
Conf({i1, i7}  {i2, i6}) = 2/4 
Conf({i2, i6}  {i1, i7}) = 2/2 OK 
Conf({i2, i7}  {i1, i6}) = 2/2 OK 
Conf({i6, i7}  {i1, i2}) = 2/2 OK 
Conf({i2, i6, i7}  {i1}) = 2/5 
Conf({i1, i6, i7}  {i2}) = 2/2 OK 
Conf({i1, i2, i7}  {i6}) = 2/3 
Conf({i1, i2, i6}  {i7}) = 2/4 
Chương 3: Luật kết hợp 
c. Tìm các luật kết hợp với min_supp=0.3 và min_conf=1.0 
Có tất cả 9 luật được rút ra: 
• {i4}  {i5} [0.33%,100%] 
• {i5}  {i4} [0.33%,100%] 
• {i1, i2}  {i6, i7} [0.33%,100%] 
• {i1, i6}  {i2, i7} [0.33%,100%] 
• {i2, i6}  {i1, i7} [0.33%,100%] 
• {i2, i7}  {i1, i6} [0.33%,100%] 
• {i6, i7}  {i1, i2} [0.33%,100%] 
• {i1, i6, i7}  {i2} [0.33%,100%] 
Chương 3: Luật kết hợp 
Các hạn chế của thuật toán Apriori 
- Phải duyệt cơ sở dữ liệu nhiều lần 
- Khi khai thác các mẫu dài, phải tạo lượng lớn tập ứng viên 
Ví dụ: để tìm tập phổ biến của I={i1,i2,....,i100} cần: 
 - Số lần duyệt CSDL: 100 
 - Số lượng ứng viên: 2100-1 
Chương 3: Luật kết hợp 
Thuật toán FP-Growth 
Quy trình: 
- Bước 1: * Tìm tập phổ biến 1 phần tử (Duyệt CSDL lần 1) 
 * Sắp xếp tập phổ biến giảm dần vào trong danh sách F_List 
 * Sắp xếp CSDL theo tập phổ biến trong danh sách F_List (Duyệt 
CSDL lần 2) và thiết lập cây FP 
- Bước 2: Xây dựng cơ sở mẫu điều kiện (Conditional Patern Bases) cho mỗi 
hạng mục phổ biến. 
- Bước 3: Thiết lập cây FP điều kiện (Conditional FP Tree) từ mỗi cơ sở 
mẫu điều kiện 
- Bước 4: Đệ quy cây FP điều kiện và phát triển mẫu phổ biến cho đến khi 
cây FP điều kiện chỉ còn chứa 1 đường dẫn duy nhất  Tạo tất cả tổ hợp 
của mẫu phổ biến 
Tập phổ biến 1 phần tử 
Đã sắp xếp giảm dần 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Cho CSDL 
(minsupp=60% ≥3 ): 
Tập (Đã sắp xếp) Độ ủng hộ 
f 4 
c 4 
a 3 
b 3 
m 3 
p 3 
- Bước 1: * Tìm tập phổ biến 1 phần tử (Duyệt CSDL lần 1) 
 * Sắp xếp tập phổ biến giảm dần vào trong danh sách F_List 
100 {f,a,c,d,g,i,m,p} 
200 {a,b,c,f,l,m,o} 
300 {b,f,h,j,o,w} 
400 {b,c,k,s,p} 
500 {a,f,c,e,l,p,m,n} 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
- Bước 1: ...... 
 Duyệt CSDL , sắp xếp CSDL theo tập phổ biến 1 phần tử và thiết 
lập cây FP 
TID Items bought 
100 {f,a,c,d,g,i,m,p} 
200 {a,b,c,f,l,m,o} 
300 {b,f,h,j,o,w} 
400 {b,c,k,s,p} 
500 {a,f,c,e,l,p,m,n} 
TID Ordered frequent items 
100 {f,c,a,m,p} 
200 {f,c,a,b,m} 
300 {f,b} 
400 {c,b,p} 
500 {f,c,a,m,p} 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
- Bước 1: ...... 
 Duyệt CSDL , sắp xếp CSDL theo tập phổ biến 1 phần tử và thiết 
lập cây FP 
TID 
Ordered 
frequent items 
100 {f,c,a,m,p} 
200 {f,c,a,b,m} 
300 {f,b} 
400 {c,b,p} 
500 {f,c,a,m,p} 
f:1 
c:1 
a:1 
m:1 
p:1 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
- Bước 1: 
 ...... 
 Duyệt CSDL , sắp xếp CSDL theo tập phổ biến 1 phần tử và thiết 
lập cây FP 
TID 
Ordered 
frequent items 
100 {f,c,a,m,p} 
200 {f,c,a,b,m} 
300 {f,b} 
400 {c,b,p} 
500 {f,c,a,m,p} 
f:2 
c:2 
a:2 
m:1 
p:1 
b:1 
m:1 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
- Bước 1: ...... 
 Duyệt CSDL , sắp xếp CSDL theo tập phổ biến 1 phần tử và thiết 
lập cây FP 
TID 
Ordered 
frequent items 
100 {f,c,a,m,p} 
200 {f,c,a,b,m} 
300 {f,b} 
400 {c,b,p} 
500 {f,c,a,m,p} 
f:3 
c:2 
a:2 
m:1 
p:1 
b:1 
m:1 
b:1 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
- Bước 1: ...... 
 Duyệt CSDL , sắp xếp CSDL theo tập phổ biến 1 phần tử và thiết 
lập cây FP 
TID 
Ordered 
frequent items 
100 {f,c,a,m,p} 
200 {f,c,a,b,m} 
300 {f,b} 
400 {c,b,p} 
500 {f,c,a,m,p} 
f:3 
c:2 
a:2 
m:1 
p:1 
b:1 
m:1 
b:1 
c:1 
b:1 
p:1 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
- Bước 1: ...... 
 Duyệt CSDL , sắp xếp CSDL theo tập phổ biến 1 phần tử và thiết 
lập cây FP 
TID 
Ordered 
frequent items 
100 {f,c,a,m,p} 
200 {f,c,a,b,m} 
300 {f,b} 
400 {c,b,p} 
500 {f,c,a,m,p} 
f:4 
c:3 
a:3 
m:2 
p:2 
b:1 
m:1 
b:1 
c:1 
b:1 
p:1 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 2: Xây dựng cơ sở mẫu điều kiện (Conditional Patern Bases) cho 
mỗi hạng mục phổ biến (mỗi nút trên cây FP-Tree) 
Items Độ hỗ trợ 
f 4 
c 4 
a 3 
b 3 
m 3 
p 3 
f:4 
c:3 
a:3 
m:2 
p:2 
b:1 
m:1 
b:1 
c:1 
b:1 
p:1 
Items Conditional Patern Bases 
f {} 
c 
a 
b 
m 
p 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 2: Xây dựng cơ sở mẫu điều kiện (Conditional Patern Bases) cho 
mỗi hạng mục phổ biến (mỗi nút trên cây FP-Tree) 
Items Độ hỗ trợ 
f 4 
c 4 
a 3 
b 3 
m 3 
p 3 
f:4 
c:3 
a:3 
m:2 
p:2 
b:1 
m:1 
b:1 
c:1 
b:1 
p:1 
Items Conditional Patern Bases 
f 
c f:3 
a fc:3 
b fca:1, f:1, c:1 
m fcab:1, fca:2 
p fcam:2, cb:1 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 3: Thiết lập cây FP điều kiện (Conditional FP Tree) từ mỗi cơ sở 
mẫu điều kiện: 
- Với cơ sở mẫu điều kiện cho p là {fcam:2, cb:1} 
 số lượng mỗi mẫu trên cơ sở mẫu: f:2, c:3, a:2, m:2, b:1 
 Minsupp≥3 nên: c:3 phổ biến trên cơ sở mẫu điều kiện của p 
Items 
Conditional 
Patern Bases 
f 
c f:3 
a fc:3 
b fca:1, f:1, c:1 
m fcab:1, fca:2 
p fcam:2, cb:1 
Items frequence 
c 3 
c:3 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 3: Thiết lập cây FP điều kiện (Conditional FP Tree) từ mỗi cơ sở 
mẫu điều kiện: 
Items 
Conditional 
Patern Bases 
f 
c f:3 
a fc:3 
b fca:1, f:1, c:1 
m fcab:1, fca:2 
p fcam:2, cb:1 
Items freq 
f 3 
c 3 
a 3 
f:3 
c:3 
a:3 
m-conditional 
Items freq 
c 3 c:3 
p-conditional 
Items freq 
f 3 
c 3 
f:3 
c:3 
a-conditional 
Items freq 
f 3 f:3 
c-conditional 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 4: Đệ quy cây FP điều kiện và phát triển mẫu phổ biến cho đến khi 
cây FP điều kiện chỉ còn chứa 1 đường dẫn duy nhất  Tạo tất cả tổ hợp 
của mẫu phổ biến 
Quy tắc: 
- Dựa trên tính chất mở rộng mẫu: 
 Giả sử α là tập phổ biến trong CSDL, B là cơ sở mẫu điều kiện 
của α và β là một tập các hạng mục trong B. 
 Khi đó: α v β là tập phổ biến trong CSDL khi và chỉ khi β phổ 
biến trong B. 
- Giả sử cây FP T là một đường dẫn đơn, tập mẫu phổ biến cuối cùng 
của T sinh ra bằng cách liệt kê tất cả các tổ hợp con của đường dẫn 
con thuộc p. 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 4: Đệ quy cây FP điều kiện và phát triển mẫu phổ biến cho đến khi 
cây FP điều kiện chỉ còn chứa 1 đường dẫn duy nhất  Tạo tất cả tổ hợp 
của mẫu phổ biến 
Items freq 
c 3 c:3 
p-conditional 
Tất cả các mẫu phổ biến liên quan 
đến p là: 
p:3, 
cp:3 
Items freq 
f 3 
c 3 
a 3 
f:3 
c:3 
a:3 
m-conditional 
Tất cả các mẫu phổ biến liên quan 
đến m là: 
m:3, 
fm:3, cm:3, am:3, 
fcm:3, fam:3, cam:3, 
fcam:3 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Bước 4: Đệ quy cây FP điều kiện và phát triển mẫu phổ biến cho đến khi 
cây FP điều kiện chỉ còn chứa 1 đường dẫn duy nhất  Tạo tất cả tổ hợp 
của mẫu phổ biến 
 Tất cả các mẫu phổ biến liên quan 
đến c là: 
c:3, 
fc:3 
Tất cả các mẫu phổ biến liên quan 
đến a là: 
a:3, 
fa:3, ca:3, 
fca:3 
Items freq 
f 3 
c 3 
f:3 
c:3 
a-conditional 
Items freq 
f 3 f:3 
c-conditional 
Ví dụ mẫu 
Chương 3: Luật kết hợp 
Item Conditional FP Tree Frequent Pateerns 
f {} f 
c {(f:3)} | c 
c, 
fc 
a {(f:3,c:3)} | a 
a, 
fa, ca, fca 
b {} b 
m {(f:3, c:3, a:3)} | m 
m, 
fm, cm, am, 
fcm, fam, cam, 
fcam 
p {(c:3)} | p 
p, 
cp 
Thuật toán FP-Growth 
Chương 3: Luật kết hợp 
Procedure FP_Growth(Tree, α) 
 If (cây chứa một đường đơn P) then 
 For mỗi tổ hợp (β) của các nút trong đường dẫn P 
 - Sinh mẫu α ∪ β với support=độ hỗ trợ nhỏ nhất của các 
 nút trong β 
 Else 
 For mỗi ai trong header của cây 
 - Sinh mẫu β = αi ∪ 𝛂 
 - Support = αi . Support 
 - Tìm cơ sở mẫu phụ thuộc của β và khởi tạo cây FP-Tree 
 phụ thuộc Tree β 
 - If Tree β ≠ ∅ then FP_Growth(Tree β,β) 
Độ đo lý thú 
Chương 3: Luật kết hợp 
Thế nào là luật hay, lý thú? 
- Thuật toán khai thác luật kết hợp có xu hướng sinh ra quá 
nhiều luật 
- Có nhiều luật không hay/bị thừa 
Các độ đo khách quan: 
- Độ phổ biến (supp) 
- Độ tin cậy (conf) 
- Khoảng hơn 20 độ đo khác 
Các độ đo chủ quan: 
- Độ đo lý thú: Luật kết hợp được gọi là lý thú nếu nó là điều 
mới lạ, gây ngạc nhiên và có khả năng ứng dụng 
- Độ đo lý thú giúp loại bớt/hạn chế luật 
Độ đo lý thú 
Chương 3: Luật kết hợp 
Ví dụ: 
Trong 5000 sinh viên, có: 
- 3000 chơi bóng đá 
- 3750 thích uống bia 
- 2000 chơi bóng đá và thích uống bia 
+ Với minsupp=40% và minconf=66.7%: 
 chơi bóng đá  thích uống bia 
 Luật này là sai lầm vì % sinh viên thích uống bia là 75%>66.7% 
+ Với minsupp=20% và minconf=33.3%: 
 chơi bóng đá  không thích uống bia 
 Luật này có ý nghĩa thực tiễn hơn, dù độ supp và conf thấp hơn 
Độ đo lý thú 
Chương 3: Luật kết hợp 
- Cần độ đo sự phụ thuộc hay mối liên quan giữa các sự kiện 
- Xác định độ đo lý thú: 𝑰𝒏𝒕𝒆𝒓𝒆𝒔𝒕 =
𝑷(𝑿,𝒀)
𝑷 𝑿 ∗𝑷(𝒀)
- X và Y được là tương quan nghịch nếu Interest<1 và ngược 
lại 
 Ví dụ: 
 Interest(Chơi bóng đá, Thích uống bia) 
 = 
𝟐𝟎𝟎𝟎/𝟓𝟎𝟎𝟎
𝟑𝟎𝟎𝟎
𝟓𝟎𝟎𝟎
∗(
𝟑𝟕𝟓𝟎
𝟓𝟎𝟎𝟎
)
= 0.89 
Cho CSDL: 
 a. Tìm các tập phổ biến với phương pháp Apriori với 
minsupp=30% 
 b. Tìm các tập phổ biến với phương pháp FP-Growth với 
minsupp=30%. So sánh với Apriori 
 c. Tìm các luật kết hợp và tính độ đo lý thú Interest cho các luật 
đã được tìm thấy tương ứng với các trường hợp. 
Bài tập 
Chương 3: Luật kết hợp 
 i1 i2 i3 i4 i5 i6 i7 i8 
O1 1 1 1 
O2 1 1 1 1 1 
O3 1 1 1 1 
O4 1 1 1 
O5 1 1 1 1 1 
O6 1 1 1