bài giảng khai phá dữ liệu

2.2. TÌM TẬP PHỔ BIẾN VỚI GIẢI THUẬT APRIORI 2.2.1. Nguyên lý Apriori “Nếu một tập mục là tập phổ biến thì mọi tập con khác rỗng bất kỳ của nó cũng là tập phổ biến” Chứng minh: Xét X’ ⊆ X. Ký hiệu p là ngưỡng độ hỗ trợ minsup. Một tập mục xuất hiện bao nhiêu lần thì các tập con chứa trong nó cũng xuất hiện ít nhất bấy nhiêu lần, nên ta có: C(X’) ≥ C(X) (1). X là tập phổ biến nên: sup( X ) = Từ (1) và (2) suy ra: C( X ) ≥ p ⇒ C ( X ) ≥ p | D | (2) |D| C ( X '') > p | D |⇒ sup( X '') = Tức là X’ cũng là tập phổ biến (đpcm). C ( X '') ≥p |D| 2.2.2. Giải thuật Apriori Mục đích: Tìm ra tất cả các tập phổ biến có thể có. Dựa trên nguyên lý Apriori. Hoạt động dựa trên Quy hoạch động: Từ các tập Fi = { ci | ci là tập phổ biến, |ci| = i} gồm mọi tập mục phổ biến có độ dài i (1 ≤ i ≤ k), đi tìm tập Fk+1 gồm mọi tập mục phổ biến có độ dài k+1. Các mục I1, I2,…, In trong tập I được coi là sắp xếp theo một thứ tự cố định. Input: Output: - Cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}. - Ngưỡng độ hỗ trợ tối thiểu minsup. - Tập hợp tất cả các tập phổ biến. mincount =  minsup * | D | ;   F1 = { các tập phổ biến có độ dài 1}; for(k=1; Fk != ⍉; k++) { Ck+1 = Apriori_gen(Fk); for each t ∈ D { Ct = { c | c ∈ Ck+1 và c ⊆ t}; for each c ∈ Ct c.count++; } Fk+1 = {c ∈ Ck+1 | c.count ≥ mincount}; } return F = U Fk k Thủ tục con Apriori_gen • Thủ tục con Apriori_gen có nhiệm vụ sinh ra (generation) các tập mục có độ dài k+1 từ các tập mục có độ dài k trong tập Fk. • Được thi hành qua hai bước: nối (join) các tập mục có chung các tiền tố (prefix) và sau đó áp dụng nguyên lý Apriori để loại bỏ bớt những tập không thỏa mãn. Cụ thể:  Bước nối: Sinh các tập mục c là ứng viên của tập phổ biến có độ dài k+1 bằng cách kết hợp hai tập phổ biến li và lj ∈ Fk có độ dài k và trùng nhau ở k-1 mục đầu tiên: c = li + lj = {i1, i2,…, ik-1, ik, ik’}. Với li = {i1, i2,…, ik-1, ik}, lj = {i1, i2,…, ik-1, ik’}, và i1 ≤ i2 ≤…≤ ik-1 ≤ ik ≤ ik’.  Bước tỉa: Giữ lại tất cả các ứng viên c thỏa thỏa mãn nguyên lý Apriori tức là mọi tập con có độ dài k của nó đều là tập phổ biến ( ∀sk ⊆ c và |sk| = k thì sk ∈ Fk). function Apriori_gen(Fk: tập các tập phổ biến độ dài k): Tập ứng viên có độ dài k+1 { Ck+1 = ⍉; for each li ∈ Fk for each lj ∈ Fk if (li[1]=lj[1]) and (li[2]=lj[2]) … and (li[k-1]=lj[k-1]) and (li[k]