Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
MỤC LỤC

LỜI NHẬN XÉT

HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 1
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth” LỜI MỞ ĐẦU

Môn học: “Khai Phá Tri Thức” đã mở rộng hơn việc tìm hiểu, khám phá các tri
thức tiềm ẩn trong các cơ sở dữ liệu (CSDL) khổng lồ và phân tích khai thác hiệu quả
nguồn thông tin từ các CSDL đó, hỗ trợ cần thiết cho tiến trình trích lọc, sản sinh những
tri thức hữu ích mang tính khái quát, tính quy luật cho việc ra quyết định thông minh
nhất giúp nhà sản xuất và kinh doanh giảm thiểu chi phí và gia tăng lợi nhuận trong

Ví dụ các luật kết hợp tiêu biểu như sau:
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 3
KH
mu
a
tôm
cầu
tre
KH
mua
cả 2
KH mua
Beer 333
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
- Có 78% khách hàng mua sữa hộp Vinamilk thì mua tra Lipton
- Có 67% khách hàng mua bia 333 thì mua bánh tôm Cầu Tre.
I.2 Các khái niệm cơ bản:
I.2.1 Khái niệm:
Cho I = {i1, i2, i3, …, in} là tập hợp các trường gọi là items
D: tập các giao tác có các giao tác Ti mà Ti ⊆ I
T chứa X nếu X ⊆ T (X là tập có các phần tử ⊆ I).
Mỗi giao tác Ti có chỉ danh là TID.
Luật kết hợp là một mối liên hệ điều kiện giữa hai tập các hạng mục dữ liệu X và Y
theo dạng sau: Nếu X thì Y, và ký hiệu là X ⇒ Y. Chúng ta có luật kết hợp X ⇒ Y, nếu
X ⊂ I, Y ⊂ I và X ∩ Y = ∅
Thước đo giá trị của một luật kết hợp là độ tác động và độ tin cậy (support là s và
confidence là c).
I.2.2 Độ tác động (Support):
Thể hiện phạm vi ảnh hưởng của luật trên tòan bộ CSDL.
Luật X=>Y có độ support là s nếu s% số giao tác trong D có chứa X∪Y. Hay là :

TID Age Married NumCars
100 23 No 1
200 25 Yes 1
300 29 No 0
400 34 Yes 2
500 38 Yes 2
Người ta đưa ra minsupp = 40% và mincon f = 50 %.
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 5
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
Tìm ra được 2 luật kết hợp thỏa mãn minsupp và minconf
(1): Age (30 39) and (Married: Yes) ⇒ NumCars = 2 (s = 40%, c = 100%)
(2): NumCars(0 1) ⇒ Married = No (s = 40%, c = 66,6%).
II.3 Ý tưởng về thuật toán tìm luật kết hợp:
II.3.1 Ý tưởng:
Tìm tất cả các luật R : X → Y; sao cho support(R) > minsup và confidence(R) >
minconf.
Chỉ những luật nào có độ support lớn hơn minsup và độ confidence lớn hơn minconf
mới được quan tâm.
Để rút ra được luật trong CSDL cần tiến hành 5 bước sau:
B1: Xác định khoảng phân chia của mỗi thuộc tính khi cần phân tích.
B2: Kết hợp mỗi khoảng thuộc tính đã phân chia ở bước B1 với một số nguyên để
thực hiện các thuật toán được nhanh, dễ dàng.
B3: So sánh các support của các item với minsupp, tạo tập Largeitemset.
B4: ABCD và AB là Large itemset ta rút ra được luật
AB ⇒ CD khi support(ABCD)/support(AB) >= minconf
B5: Xác định chọn những luật phù hợp .
II.3.2 Vậy có thể nói thuật toán tìm tập phổ biến được xây dựng 2 bước sau:
Bước 1 : Liệt kê tất cả các tập con P của I (tập tất cả các thuộc tính của cơ sở dữ
liệu). sao cho P÷ > 1.
Bước 2 : Với mỗi tập con P, liệt kê tất cả các tập con X khác trống của P.

Để tăng tốc thuật toán, ta cần phải tìm cách giải quyết hai "điểm nóng" (các điểm tiêu
tốn nhiều thời gian thi hành của máy tính) trong thuật toán ở trên là số lần lặp (2
n
) và
thời gian duyệt cơ sở dữ liệu để tính support và confidence.
- Loại bỏ nhanh các tập thuộc tính có support < minsup theo quy tắc nhánh cận.
- Tính support dựa vào thông tin từ những lần tính trước.
- Xây dựng cơ sở dữ liệu tương đương nhưng có tốc độ truy xuất nhanh hơn.
II.2 Thuật toán Apriori:
II.2.1Trình bày thuật toán:
Trong ý tưởng thuật toán tìm tập phổ biến trên, có thể thấy rằng ở bước 2 là tốn kém
nhiều chi phí nhất trong những cơ sở dữ liệu lớn trong thực tế. Thuật toán Apriori và
một số cải tiến tốc độ cũng có thể nói góp phần giảm chi phí đáng kể khi các giao dịch
có nhiều các mẫu (giá trị) thường xuyên và ngưỡng minsupport thấp.
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 8
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
Dưới đây là phần trình bày thuật toán tìm Tập Phổ Biến tổng quát cho trong thuật toán
Apriori
Bước 1:
Duyệt tất cả các giao tác (transactions) và dựa vào ngưỡng minsupport để tìm ra tập
ban đầu.
Bước 2:
Giả sử tại bước k-1, đã có được tập phổ biến F-1 khác rỗng. Tại bước k, phát sinh
tập ứng viên Ck (Candidate k-itemset) dựa vào tổ hợp các phần tử trong tập F-1. Tập
kết quả chứa các giá trị không bị trùng lắp.
Bước 3:
Tiếp tục cho bước k, đã có trước tập ứng viên Ck. Duyệt qua tất cả các giao tác
(trong CSDL) để cập nhật giá trị support cho các phần tử trong Ck, đồng thời so
sánh với minsupport để chọn ra tập phổ biến Fk.
Bước 4:

…
sp({“sữa”,”khăn giấy”}) = 3/5
F2 = {{“nước ngọt”,”sữa”}, {“sữa”,”khăn giấy”}}
C3 = {{“nuớc ngọt”,”sữa”,”khăn giấy”}}
* Tìm F3 từ C3:
sp({“nuớc ngọt”,”sữa”,”khăn giấy”}) = 2/5 (loại)
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 10
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
F3 = {}
C4 = {}
- Vậy tập phổ biến là {{“nước ngọt”,”sữa”}}
- Ta xây dựng 2 luật:
(R1) “nước ngọt” → “sữa”;
(R2) “sữa” → “nước ngọt”
conf(R1) = sp(R1)/sp(“nước ngọt”) = 3/5 : 3/5 = 1 (100%)
conf(R2) = sp(R1)/sp(sữa) = 3/5 : 4/5 = ¾ (75%) (loại)
=> Vậy tìm được 1 luật: “nuớc ngọt” → “sữa”
với minsupp = 50% minconf = 100%
Khách hàng mua “nước ngọt” thì cũng sẽ mua “sữa”
* Các thuật toán cải tiến như AprioriTID cũng dựa trên các bước cơ bản trên, nhưng để
hạn chế truy xuất vào CSDL và tăng tốc độ, thuật toán này đã thực hiện công việc: tại
mỗi bước k, ghi lại danh sách các ItemSet cho tất cả các giao tác còn đang xét. Giá trị
ghi này gọi là Set-of-ItemSets. Nhằm mục đích sử dụng cho tính toán giá trị support ở
bước sau. Ngoài ra, có thể kết hợp bộ nhớ cache sử dụng dạng bit Array để lưu trữ lại tất
cả các giao tác.
II.3 Thuật toán tìm tập phổ biến FP-Growth:
Trong thuật toán Apriori cũng còn giới hạn ở bước tìm tập phổ biến là tốn kém rất nhiều
chi phí và nặng nề nhất. Do đó phải có một cách tổ chức lại cấu trúc của các giá trị
( hạng mục – item) và các giao tác (transactions) để tìm các giá trị support đó một cách
trực tiếp từ cấu trúc mà không cần phải truy xuất vào CSDL.

mỗi giao tác trong CSDL, thực hiện hai việc sau:
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 12
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
- Chọn các phần tử phổ biến trong mỗi giao tác sắp xếp support giảm dần theo thứ tự
trong tập F1. Ký hiệu danh sách các phần tử đã sắp xếp là [p|P], trong đó p là phần tử
đầu tiên của danh sách, P là các phần tử còn lại.
- Gọi hàm Insert_tree([p|P],T) để đưa các phần tử trong danh sách vào cây T.
II.3.1.5 Xét ví dụ tạo FP-Tree dưới đây
Lần duyệt thứ nhất: Tìm các 1-frequent itemset và sắp xếp chúng theo danh sách với
trật tự giảm dần theo tần số xuất hiện, loại bỏ các item nhỏ hơn ngưỡng min_sup = 3
TID Items Bought Ordered Frequent Items
1 f, a, c, d, g, i, m, p f, c, a, m, p
2 a, b, c, f, l, m, o f, c, a, b, m
3 b, f, h, j, o f, b
4 b, c, k, s, p c, b, p
5 a, f, c, e, l, p, m, n f, c, a, m, p
(f:4, c:4, a:3, b:3, m:3, p:3)
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 13
Header table
f
c
a
m
p
Root
f:1
c:1
a:1
m:1
p:1

c
a
m
p
Root
f:2
c:1
a:1
m:1
p:1
P: (a, b, m)
T:
Header table
f
c
a
m
p
Root
f:2
c:2
a:1
m:1
p:1
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
Insert_tree([p|P],T)
Insert_tree([p|P],T)
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 15
P: (b, m)
T:

P: ()
T:
Header table
f
c
a
b
m
p
Root
f:2
c:2
a:2
m:1
p:1
b:1
m:1
Header table
f
c
a
b
m
p
Root
f:3
c:2
a:2
m:1
p:1

b
m
p
Root
f:4
c:3
a:3
m:2
p:2
b:1
m:1
b:1
c:1
b:1
p:1
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
2.6 Sau khi chèn giao dịch thứ 5, TID = 5 với P: (f, c, a, m, p) và T như sau (FP-Tree):
II.3.1.6 Thuật toán xây dựng FP-Tree
 Xây dựng cây FP-Tree từ CSDL giao tác
 Input:
- CSDL giao tác D
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 18
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
- Ngưỡng min-sup
 Output:
- Cây FP-Tree
 Method
1. Duyệt D lần đầu để thu được tập F gồm các frequent item và support count
của chúng. Sắp xếp các item trong F theo trật tự giảm dần của supprort count ta
được danh sách F1.

m:1
c:1
b:1
p:1
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
12. H[p].count ++;
13. If (P-p) != null then
14. Call Insert_Tree(P-p, N) ;
}
II.3.2 Thuật toán FP-Growth (Dựa vào tính chất của FP-Tree):
II.3.2.1 Tính chất 1: (Node-link property)
Với mỗi phần tử phổ biến a
i
, tất cả các tập phổ biến có chứa phần tử này có thể tìm
được bằng cách dò theo các nút liên kết bắt đầu từ a
i
. Tính chất này có cơ sở trực tiếp từ
cách xây dựng FP-tree. Nó cho phép dễ dàng tìm ra tất cả các tập phổ biến có chứa a
i
bằng cách duyệt FP-tree một lần theo các nút liên kết với a
i
.
Ví dụ: Tính chất Node-link property khám phá các tập phổ biến dựa trên FP-tree theo
ví dụ mục II.3.1.5 :
Frequent-item Header Table
Item
f:4
c:4
a:3
b:3

- Với nút p, chúng ta thu được mẫu phổ biến (p:3) và hai đường đi trên FP-tree : (f:4;
c:3; a:3; m:2; p:2) và (c:1; b:1; p:1).
Đường đi thứ nhất chỉ ra rằng chuỗi "(f; c; a; m; p)" xuất hiện hai lần trong CSDL.
Chú ý là mặc dù chuỗi (f; c; a ) xuất hiện ba lần và (f) xuất hiện bốn lần trong CSDL,
nhưng chúng chỉ xuất hiện hai lần cùng với p, vì thế số đếm của chuỗi trước p là f:2;
c:2; a:2; m:2
Tương tự, đường đi thứ hai chỉ ra rằng chuỗi "(c; b; p)" xuất hiện một lần trong
các giao tác của CSDL huặc chuỗi trước p là c:1; b:1. Cả hai chuỗi truớc p , "{(f:2; c:2;
a:2;m:2), (c:1; b:1)}" , tạo thành một "cơ sở điều kiện của p". Xây dựng một FP-tree dựa
trên cơ sở điều kiện của p ta có một FP-tree (gọi là cây điều kiện FP của p) chỉ có một
nhánh là c:3. do đó chỉ tìm được một tập phổ biến là cp:3. Sự tìm kiếm các tập phổ biến
có chứa p chấm dứt.
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 21
Header table
f
c
a
b
m
p
Root
f:4
c:3
a:3
m:2
p:2
b:1
m:1
b:1
c:1

f
c
a
Cơ sở điều kiện của "cm:3": (f:3) Cơ sở điều kiện của "cam:3": (f:3)
Đầu tiên chúng ta nhận được tập phổ biến (am:3), và gọi "mine(<f:3; c:3>|am)" chúng ta
có tập phổ biến (cm:3), kế đến gọi "mine(<f:3|>cm)" chúng ta có (fm:3).
Gọi đệ qui sâu hơn nữa với "mine(<f:3; c:3>|am)", chúng ta thu đuợc các tập phổ biến
(cam:3), (fam:3), sau đó gọi "mine(<f:3>|cam)" chúng ta đuợc tập dài nhất (fcam:3).
Tương tự, gọi "mine(<f:3>|cm" chúng ta đuợc (fcm:3).
=> Do đó, tất cả các tập phổ biến liên quan đến m là {(m:3), (am:3), (cm:3), (fm:3),
(cam:3), (fam:3), (fcam:3), (fcm:3)}. Điều này chỉ ra rằng một đường đi đơn trên FP-tree
có thể xuất ra tất cả các sự kết hợp của các nút trong đường đi.
* Bảng kết quả của tất cả các Item
item Conditional pattern base Conditional FP-tree
p {(f:2; c:2; a:2; m:2),(c:1; b:1)} {(c:3)}|p
m {(f:4; c:3; a:3;m:2), (f:4; c:3; a:3; b:1;m:1)} {(f:3; c:3;a:3)}|m
b {(f:4; c:3; a:3; b:1), (f:4; b:1), (c:1; b:1)} ∅
a {(f:3; c:3)} {(f:3; c:3)}|a
c {(f:3)} {(f:3)}|c
f ∅ ∅
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 23
Cây điều kiện FP của "m" Cây điều kiện FP của "am"
Cây điều kiện FP của "cm"
Cây điều kiện FP của "cam"
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
II.3.2.2 Tính chất 2: (Prefix path property)
Để tìm ra các tập phổ biến từ một nút a
i
trên đuờng đi P, chỉ cần đến đường đi con trước
nút a

13. Xây dựng cơ sở có điều kiện của
14. Xây dựng FP-Tree có điều kiện của
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 24
Tiểu luận:“Tìm hiểu và cài đặt thuật toán phát sinh tập phổ biến bằng giải thuật FP-Growth”
15. if !=
16. call FP_growth(, );
17. }
18.}
}
Thuật toán FP-Growth phát triển là để khắc phục một số nhược điểm của các thuật toán
trước đó, tuy nhiên nó lại sinh ra một số nhược điểm khác. Sau đây là các ưu điểm và
nhược điểm của FP-Growth
Ưu Điểm
- Chỉ cần duyệt 2 lần vào Cơ Sở Dữ Liệu.
- Nén tập dữ liệu theo ý nghĩa vào tree.
- Không phát sinh tập ứng viên.
- Không đếm trùng lắp trên giao tác trong CSDL.
- Nhanh hơn nhiều so với Apriori.
Nhược điểm
- Bộ nhớ có thể không đủ cấp cho FP-Tree trong trường hợp CSDL to và chia ra
làm quá nhiều nhánh.
- Thời gian tạo FP-Tree khá tốn kém
- Thời gian tạo tree khá tốn kém, nhưng chỉ tạo 1 lần và sử dụng nhiều lần
- Khi minsuport càng cao thì thời gian tạo cây dường như càng phí.
Biểu đồ so sánh FP–growth và Apriori
HVTH: Nguyễn Hoàng Sỹ - MSHV: CH 1101037 Trang 25