Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI TIỂU LUẬN
MÔN CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
ĐỀ TÀI:
ỨNG DỤNG THUẬT TOÁN
TÌM LUẬT KẾT HỢP
PHÂN TÍCH CƠ SỞ DỮ LIỆU BÁN HÀNG
GVHD: GS. TSKH. HOÀNG KIẾM
HVTH: TRẦN KHÁNH AN
MSHV: CH1301076
TP HCM, tháng 10 năm 2014
MỤC LỤC
HVTH:Trần Khánh An -CH1301076 1
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
HVTH:Trần Khánh An -CH1301076 2
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
MỞ ĐẦU
Trong xã hội hiện đại hôm nay, có vô số thông tin và tri thức được sáng tạo và
phát triển hằng ngày. Việc khai phá các dữ liệu để phục vụ cho mục đích nghiên cứu,
kinh doanh đang càng ngày được xem trọng. Một trong những yếu tố thành công trong
hoạt động kinh doanh ngày nay là biết sử dụng, khai thác thông tin một cách hiệu quả.
Điều đó có nghĩa là từ các dữ liệu có sẵn phải tìm ra những thông tin tìm ẩn chưa được
phát hiện, khai thác. Thực hiện công việc đó chính là quá trình phát hiện tri thức trong cơ
sở dữ liệu mà trong đó kỹ thuật cho phép ta lấy được các tri thức là nhờ vào kỹ thuật khai
phá dữ liệu. Mặt khác, trong môi trường cạnh tranh, người ta ngày càng cần có nhiều
thông tin với tốc độ nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi
mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có.
Từ thực tế đó đã làm phát triển một khuynh hướng kỹ thuật mới đó là kỹ thuật phát hiện
tri thức và khai phá dữ liệu. Mục tiêu chính của khai phá dữ liệu là lấy được những thông

Mục đích của việc nghiên cứu là xây dựng một giải pháp hiệu quả tính ứng dụng
luật kết hợp trong việc ra quyết định của cơ quan doanh nghiệp dựa trên cơ sở dữ liệu
giao dịch.
1.2. Khai phá dữ liệu
Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỹ 1980.
Nó là quá trình khám phá thông tin ẩn được tìm thấy trong các cơ sở dữ liệu và có thể
xem như là một bước trong quá trình khám phá tri thức. Data Mining là giai đoạn quan
trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong
việc ra quyết định trong khoa học và kinh doanh.
Những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ được chiết xuất ra và
sử dụng một cách hữu ích nhờ khai phá dữ liệu. Chức năng khai phá dữ liệu gồm có gộp
nhóm phân loại, dự báo, dự đoán và phân tích các liên kết. Năm 1989 Fayyad, Smyth và
Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ cơ sở dữ liệu (Knowledge
Discovery in Database-KDD). Trong đó, khai phá dữ liệu là một giai đoạn rất đặc biệt
trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu.
HVTH:Trần Khánh An -CH1301076 4
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
1.3. Quy trình phát hiện tri thức trong CSDL
Một trong những yếu tố thành công trong hoạt động kinh doanh ngày nay là biết sử
dụng, khai thác thông tin một cách hiệu quả. Điều đó có nghĩa là từ các dữ liệu có sẵn
phải tìm ra những thông tin tìm ẩn chưa được phát hiện, khai thác. Thực hiện công việc
đó chính là quá trình phát hiện tri thức trong cơ sở dữ liệu mà trong đó kỹ thuật cho phép
ta lấy được các tri thức là nhờ vào kỹ thuật khai phá dữ liệu.
Khi lưu trữ các dữ liệu khổng lồ thì chúng ta thấy rằng chắc chắn chúng phải chứa
những giá trị nhất định nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ của
những dữ liệu này (khoảng từ 5% đến 10%) là được phân tích, số còn lại họ không biết sẽ
phải làm gì hoặc có thể làm gì với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý
nghĩ lo sợ rằng sẽ có cái gì đó quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Mặt
khác, trong môi trường cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ
nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định

phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai
lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần
chiết xuất ra.
Quá trình này có thể được lặp lại nhiều lần, qua một hay nhiều giai đoạn dựa trên
phản hồi từ kết quả của các giai đoạn phía sau.
1.4. Các kỹ thuật khai phá dữ liệu
1.4.1. Các kỹ thuật tiếp cận trong khai phá dữ liệu
Căn cứ vào lớp các bài toán cần giải quyết, khai phá dữ liệu có các kỹ thuật áp dụng
sau:
Phân lớp và dự đoán: xếp một đối tượng vào một trong những lớp đã biết trước. Ví
dụ: phân lớp các bệnh nhân dữ liệu trong hồ sơ bệnh án. Hướng tiếp cận này thường sử
dụng một số kỹ thuật của học máy như cây quyết định, mạng nơ ron nhân tạo.
Luật kết hợp: Mục đích của luật kết hợp là tìm ra sự kết hợp (association) hay
tươngquan (correlation) giữa các items. Những luật kết hợp này có dạng X =>Y.
Luật kết hợp X =>Y có thể hiểu rằng những người mua các mặt hàng trong tập X
cũng thường mua các mặt hàng trong tập Y. (X và Y gọi là itemset).
Ví dụ, nếu X = {Apple, Banana} và Y = {Cherry, Durian} và ta có luật kết hợp X
=>Y thì chúng ta có thể nói rằng những người mua Apple và Banana thì cũng thường
mua Cherry và Durian.
Phân tích chuỗi theo thời gian: Tượng tự như khai phá luật kết hợp nhưng có thêm
tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài
chính và thị trường chứng khoán vì nó có tính dự báo cáo.
Gom nhóm dữ liệu: xếp các đối tượng theo từng nhóm dữ liệu tự nhiên.
Mô tả khái niệm: thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn
bản.
1.4.2. Các dạng dữ liệu có thể khai phá
Do khai phá dữ liệu được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều
kiểu dữ liệu khác nhau. Sau đây là một số dạng dữ liệu điển hình: CSDL quan hệ, CSDL
đa chiều (multidimentional structures, data warehouses), CSDL dạng giao dịch, CSDL
quan hệ-hướng đối tượng, dữ liệu không gian và thời gian, Dữ liệu chuỗi thời gian,

Cho một tập I = {I1, I2, , Im} các tập m mục, một giao dịch T được định nghĩa
như một tập con của các khoản mục trong I (T⊆I).
Tương tự như khái niệm tập hợp, các giao dịch không được trùng lặp, nhưng có thể
nới rộng tính chất này của tập hợp và trong các thuật toán sau này, người ta đều giả thiết
rằng các khoản mục trong một giao dịch và trong tất cả các tập mục khác, có thể coi
chúng đã được sắp xếp theo thứ tự từ điển của các mục.
Gọi D là CSDL của n giao dịch và mỗi giao dịch được đánh nhãn với một định danh
duy nhất. Nói rằng, một giao dịch T ∈ D hỗ trợ một tập X ⊆ I nếu nó chứa tất cả các item
của X.
HVTH:Trần Khánh An -CH1301076 7
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
Điều này nghĩa là X ⊆ T, trong một số trường hợp người ta dùng ký hiệu T(X) để
chỉ tập các giao dịch hỗ trợ cho X. Kí hiệu support(X) (hoặc sup(X), s(X)) là tỷ lệ phần
trăm của các giao dịch hỗ trợ X trên tổng các giao dịch trong D, nghĩa là:
sup(X) = (2.1)
Độ hỗ trợ tối thiểu minsup là một giá trị cho trước bởi người sử dụng. Nếu tập mục
X có sup(X) ≥ minsup thì ta nói X là một tập các mục phổ biến. Một tập phổ biến được
sử dụng như một tập đáng quan tâm trong các thuật toán, ngược lại, những tập không
phải tập phổ biến là những tập không đáng quan tâm. Các phần sau sẽ sử dụng những
cụm từ khác như “X có độ hỗ trợ tối thiểu”, hay “X không có độ hỗ trợ tối thiểu” cũng để
nói lên rằng X thỏa mãn hay không thỏa mãn support(X) ≥ minsup.
→Một khoản mục X được gọi là k-itemset nếu lực lượng của X bằng k, tức là
.
Một luật kết hợp có dạng R: X => Y, trong đó X, Y là tập các mục, X, Y ⊆ I và X
∩Y = ∅. X được gọi là tiên đề và Y được gọi là hệ quả của luật.
Luật X => Y tồn tại một độ tin cậy c . Độ tin cậy c được định nghĩa là khả năng giao
dịch T hỗ trợ X thì cũng hỗ trợ Y. Ta có công thức tính độ tin cậy c như sau:
conf(X =>Y) = p(Y ⊆ I | X ⊆ I ) = (2.2)
Tuy nhiên, không phải bất cứ luật kết hợp nào có mặt trong tập các luật có thể được
sinh ra cũng đều có ý nghĩa trên thực tế. Mà các luật đều phải thoả mãn một ngưỡng hỗ

⊆
⊆∧⊆
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
(2.3)
Nếu conf ≥ minconf thì luật được giữ lại (luật này sẽ thoả mãn độ hỗ trợ tối thiểu vì
ABCD là phổ biến).
2.2.2. Một số tính chất liên quan đến các hạng mục phổ biến:
2.2.2.1. Với tập mục phổ biến, có 3 tính chất sau:
Tính chất 1 (Độ hỗ trợ của tập con):
Với A và B là tập các mục, nếu A ⊆ B thì sup(A) ≥ sup(B)
Điều này là rõ ràng vì tất cả các giao tác của D hỗ trợ B thì cũng hỗ trợ A.
Tính chất 2:
Một tập chứa một tập không phổ biến thì cũng là tập không phổ biến.
Nếu một mục trong B không có độ hỗ trợ tối thiểu trên D nghĩa là A ⊆ B và sup(A)<
minsup thì B sẽ không phải là một tập phổ biến vì support(B) ≤ support(A) < minsup
(theo tính chất 1)
Tính chất 3: Các tập con của tập phổ biến cũng là tập phổ biến
Nếu mục B là mục phổ biến trên D, nghĩa là support(B) ≥ minsup thì mọi tập con A
của B là tập phổ biến trên D vì support(A) ≥ support(B) > minsup.
2.2.2.2. Với luật kết hợp, có 4 tính chất sau:
Tính chất 1:( Không hợp các luật kết hợp)
Nếu có X→Z và Y→Z trong D thì không nhất thiết X∪Y→Z là đúng
Xét trường hợp X ∩Z =∅ và các tác vụ trong D hỗ trợ Z nếu và chỉ nếu chúng hỗ trợ
mỗi X hoặc Y, khi đó luật X∪Y→Z có độ hỗ trợ 0%.
Tương tự : X→Y ∧ X→Z ⇒ X→Y∪Z
Tính chất 2:(Không tách luật)
Nếu X∪Y→Z thì X→Z và Y→Z chưa chắc xảy ra
Ví dụ trường hợp Z có mặt trong một giao tác chỉ khi cả hai X và Y cũng có mặt, tức
là sup(X∪Y)= sup(Z), nếu độ hỗ trợ của X và Y đủ lớn hơn sup(X∪Y), tức là sup(X) >
sup(X∪Y) và sup(Y) > sup(X∪Y) thì hai luật riêng biệt sẽ không đủ độ tin cậy

trong giao tác của CSDL chứ không quan tâm về “mức độ” xuất hiện. Ví dụ: Trong hệ
thống tính cước điện thoại thì việc gọi 10 cuộc điện thoại và một cuộc được xem là giống
nhau. Thuật toán tiêu biểu nhất khai phá dạng luật này là thuật toán Apriori và các biến
thể của nó. Đây là dạng luật đơn giản và các luật khác cũng có thể chuyển về dạng luật
này nhờ một số phương pháp như rời rạc hoá, mờ hoá, …
Luật kết hợp có thuộc tính số và thuộc tính hạng mục: Các thuộc tính của các CSDL
thực tế có kiểu rất đa dạng, như số nhị phân, giá trị định tính, định lượng Để phát hiện
HVTH:Trần Khánh An -CH1301076 10
)sup(
)sup(
)sup(
)sup(
A
L
B
L
≤
)sup(
)sup(
)sup(
)sup(
CL
L
DL
L
−
≥
−
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
luật kết hợp với các thuộc tính này, các nhà nghiên cứu đã đề xuất một số phương pháp

càng lớn hơn nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ của hệ thống phải
được đảm bảo. Có rất nhiều thuật toán song song khác nhau đã đề xuất để có thể không
phụ thuộc vào phần cứng.
Bên cạnh những nghiên cứu về các biến thể của luật kết hợp, các nhà nghiên cứu
còn chú trọng đề xuất những thuật toán nhằm tăng tốc quá trình tìm kiếm tập phổ biến từ
CSDL.
Ngoài ra, còn có một số hướng nghiên cứu khác về khai thác luật kết hợp như: khai
thác luật kết hợp trực tuyến, khai thác luật kết hợp được kết nối trực tuyến đến các kho
dữ liệu đa chiều thông qua công nghệ OLAP, MOLAP, ROLAP, ADO.
HVTH:Trần Khánh An -CH1301076 11
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
CHƯƠNG 3: MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP
3.1. Thuật toán Apriori
3.1.1. Ý tưởng thuật toán Apriori
Apriori là một thuật giải được do Rakesh Agrawal, Tomasz Imielinski, Arun
Swami đề xuất lần đầu vào năm 1993. Thuật toán tìm giao dịch t có độ hỗ trợ và độ tin
cậy thoả mãn lớn hơn một giá trị ngưỡng nào đó.
Thuật toán được tỉa bớt những tập ứng cử viên có tập con không phổ biến trước
khi tính độ hỗ trợ.
Thuật toán Apriori tính tất cả các tập ứng cử của tập k trong một lần duyệt CSDL.
Apriori dựa vào cấu trúc cây băm. Tìm kiếm đi xuống trên cấu trúc cây mỗi khi ta chạm
lá, ta tìm được một tập ứng cử viên có tiền tố chung được bao gồm trong giao dịch. Sau
đó các tập ứng cử này được tìm trong giao dịch đã được ánh xạ trước đó. Trong trường
hợp tìm thấy biến đếm được tăng lên 1.
Ký hiệu:Giả sử các mục trong mỗi giao dịch được lưu giữ theo trật tự từ điển. Gọi
số các mục trong một tập mục là kích thước của nó và gọi tập mục có kích thước k là tập
k-mục (tập k mục). Các mục trong mỗi tập mục cũng được giữ ở trật tự từ điển. Ta sử
dụng các ký hiệu sau:
L
k

)
8. c.count ++;
10. }
11. L
k
={ c
∈
C
k

c.count
≥
minsup}
12. k++;
13. }
HVTH:Trần Khánh An -CH1301076 12
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
14. Return L=
∪
k
L
k'
;
// sinh ứng cử viên mới (**)
Void apriori_gen(L
k-1
, minsup )
1. { for(
∀
itemset l

(k-1))
4. { c= L
1
kết nối L
2
;
5. if( has_inrequent_subset(c,L
k-1
)) delete c;
6. else add c to C
k
;
7. }
8. return C
k
9.}
Boolean has_infrequent_subset(c,L
k-1
)
1.{ for(
∀
(k-1)-subset s
∈
c)
2. if(s∉ L
k-1
) return TRUE;
3. else return FALSE ;
4.}
Giải thích: Lần duyệt đầu tiên, sẽ tính số lần xuất hiện của mỗi mục để xác định các

k-1
với mỗi mục nằm trong CSDL và
sau đó xoá bỏ các tập này mà đối với nó (k-1) –itemset nhận được bằng việc xoá đi mục
thứ (k-1) không nằm trong L
k-1
. Ở giai đoạn này C
k
⊇
L
k
. Với lập luận như vậy, giai đoạn
tỉa là giai đoạn người ta xoá khỏi C
k
tấtcả các tập mà các (k-1) tập con của nó không nằm
trong L
k-1
, cũng không xoá bất kỳ một tập nào có thể nằm trong L
k
.
Hàm Subset: Các tập ứng cử viên C
k
được lưu trữ trong một cây băm. Một nút của
cây này hoặc là chứa một danh sách của các tập (nút lá) hoặc bảng băm ( một nút trong).
Trong mỗi một nút trong, mỗi cụm (bucket) của bảng băm chỉ đến một nút khác. Gốc của
cây băm được xem ở độ sâu là 1. Một nút trong ở độ sâu d sẽ dẫn đến nút ở độ sâu d+1.
HVTH:Trần Khánh An -CH1301076 13
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
Các tập được lưu trữ trong các lá. Khi ta bổ sung thêm một tập c, ta bắt từ nút gốc và đi
xuống cây cho đến khi ta chạm vào một lá. Tại một nút ở độ sâu d, ta quyết định sẽ đi
theo cành nào bằng việc áp dụng hàm băm đối với mục thứ d của tập đó và theo con trỏ

k
;
Nhận xét: Thuật toán Apriori với n là độ dài lớn nhất của tập được sinh ra. Vậy thì
thuật toán sẽ thực hiện duyệt toàn bộ các giao tác n+1 lần. Như vậy, nếu bỏ qua thời gian
so sánh tìm sự xuất hiện của một mẫu trong một giao tác thì độ phức tạp của thuật toán
Apriori là O(A) > O(n*L) trong đó L là kích thước CSDL còn n là độ dài cần đạt được
của các mẫu.
Ngoài ra, nếu độ hỗ trợ tối thiểu minsup bị thay đổi thì thuật toán sẽ phải thực hiện lại
từ đầu, điều này sẽ rất mất thời gian. Thuật toán Apriori được xây dựng nhằm phát hiện
các luật kết hợp giữa các đối tượng với độ hỗ trợ và độ tin cậy tối thiểu.
3.1.3. Sinh các luật kết hợp từ tập mục phổ biến:
Sau khi các tập mục phổ biến từ các tác vụ trong CSDL đã được tìm thấy, nó có thể
sinh ra các luật kết hợp mạnh, ở đó luật kết hợp mạnh (strong association rule) là luật
thoả mãn cả hai độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Điều đó có thể thực hiện bằng
HVTH:Trần Khánh An -CH1301076 14
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
việc sử dụng tính độ tin cậy của luật, ta nhắc lại: độ tin cậy của luật X → Y là: conf (X →
Y) = P(Y/X) = sup(X∪Y)/sup(X)
ở đó sup(X∪Y) là độ hỗ trợ của X∪Y và sup(X) là độ hỗ trợ của X.
Có thể coi tỷ số trên là tỷ số giữa: số các tác vụ chứa X∪Y và số các tác vụ chứa X.
Dựa trên biểu thức tính toán đó, các luật kết hợp có thể được sinh như sau:
Với mỗi tập mục phổ biến l, sinh ra tất cả các tập con không rỗng của l
Với mỗi tập con không rỗng a của l, ta có luật a → (l-a) nếu
)sup(
)sup(
a
l
≥ minconf ở đó
minconf là ngưỡng độ tin cậy cực tiểu
Vì các luật được sinh ra từ các tập mục phổ biến nên độ hỗ trợ của luật đã được thoả

,l
k
)
Procedure genrules(l
k
:large k-itemsets, a
m
: large m-itemsets)
HVTH:Trần Khánh An -CH1301076 15
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
A={(m-1)-itemsets a
m-1
|a
m-1
⊂ a
m
};
for all a
m-1
∈ A do again
conf=support(l
k
)/support(a
m-1
);
if (conf ≥ minconf) then
begin
output the rule a
m-1
→(l

k
với l-mục ở kết luận};
Call ap_genrules(l
k
,H
l
)
End
Procedure ap_genrules(l
k
:large k-itemsets, H
m
:set of m-item consequents)
If (k>m+1) then
begin
H
m+1
=apriori_gen(H
m
);
For all h
m+1
∈H
m-1
do
Begin
Conf = support(l
k
)/support(l
k

mục ở phần kết luận thoả mãn độ hỗ trợ cực tiểu minconf.
Trong thuật toán đơn giản trên, gọi đệ quy genrules(ABCDE, ACD) sẽ kiểm tra các
luật với 2-mục ở phần kết luận là: ACD→BE, ADE→BC, CDE→AB và ACE→BD
Luật thứ nhất không xảy ra vì E ⊂ BE và ABCD →E không thoả mãn độ tin cậy. Các
luật thứ hai và thứ ba cũng không thoả mãn độ tin cậy với lý do tương tự.
Chỉ có một luật với 2 - mục ở phần kết luận nhận được là ACE→BD, ở đó B và D là
các kết luận của các luật kết hợp có 1- mục ở phần kết luận. Thuật toán nhanh hơn mô tả
ở trên chỉ kiểm tra một luật này.
3.2. Thuật toán FP-growth
3.2.1. Ý tưởng thuật toán
Thuật toán kinh điển Apriori tìm tập mục phổ biến thực hiện tốt bởi rút gọn kích
thước các tập ứng cử nhờ kỹ thuật tỉa. Tuy nhiên, trong tình huống mà số các mẫu nhiều,
mẫu dài hoặc độ hỗ trợ cực tiểu thấp, các thuật toán Apriori gặp phải 2 chi phí lớn:
Chi phí cho số lượng khổng lồ các tập ứng cử. Ví dụ: nếu có 10
4
tập 1-mục phổ
biến thì thuật toán Apriori sẽ cần sinh ra hơn 10
7
các ứng cử 2-mục và thực hiện kiểm tra
sư xuất hiện của chúng. Hơn nữa, để khám phá được một số mẫu phổ biến kích thước (độ
dài) là l, thuật toán phải kiểm tra (2
l
-2 ) các mẫu phổ biến tiềm năng. Ví dụ l=100, chẳng
hạn là {a
1
,a
2
, ,a
100
}, nó phải sinh ra tổng số 2

theo cách phát triển (growth) các đoạn mẫu để tránh chi phí cho việc sinh ra số lượng lớn
các tập ứng cử.
Thứ ba, kỹ thuật tìm kiếm được dùng ở đây là dựa vào sự phân chia và chế ngự
(divide-and-conquer method) để phân rã nhiệm vụ khai phá thành tập các nhiệm vụ nhỏ
hơn với giới hạn các mẫu trong các CSDL nhằm thu gọn không gian tìm kiếm.
Phương pháp FP-growth đã chứng tỏ được tính hiệu quả của nó và thể hiện khai
phá cho cả các mẫu ngắn và dài, nhanh hơn thuật toán Apriori, luôn chỉ cần duyệt CSDL
2 lần.
3.2.2. Thuật toán FP-growth.
Đầu tiên, thuật toán duyệt CSDL lần thứ nhất để tính độ hỗ trợ của các tập mục (đếm
số lần xuất hiện của từng mục).
Tiếp đến, những mục không đủ độ hỗ trợ bị loại. Các mục còn lại được sắp theo thứ
tự giảm dần của độ hỗ trợ (cũng tức là giảm dần theo số lần xuất hiện trong CSDL), ta
nhận được danh sách L các mục đã sắp.
Duyệt CSDL lần thứ 2, với mỗi tác vụ t, loại các mục không đủ độ hỗ trợ, các mục
còn lại theo thứ tự giống như xuất hiện trong L (tức là thứ tự giảm dần theo độ hỗ trợ)
được đưa vào cây FP-tree.
Phần tiếp theo thuật toán khai phá tìm các mẫu phổ biến trên cây FP-tree đã xây dựng
mà không cần duyệt lại CSDL nữa.
Cấu trúc cây FP-tree như sau:
HVTH:Trần Khánh An -CH1301076 18
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
Gốc của cây nhãn null, các đường đi trên cây biểu diễn item prefixs
Các liên kết trên cây: liên kết các mục xuất hiện có tên giống nhau
Mỗi nút, (trừ nút gốc) bao gồm:
Tên mục (item identifier)
Count: số đếm
Node link: liên kết đến nút tiếp theo trên cây có cùng tên
Bảng các đầu mục phổ biến (header table): bắt đầu cho các liên kết
Thủ tục thêm một dãy các mục (đã sắp giảm dần theo độ hỗ trợ) của một tác vụ vào

Ngược lại: với mỗi mục a
i
trong header table của Tree{
Sinh ra β:= a
i
∪α với support=a
i
.count;
Xây dựng cơ sở mẫu phụ thuộc của β và sau đó FP-tree phụ thuộc của β là
Tree
β
;
Nếu Tree
β
≠∅ thì gọi FP-growth(Tree
β
,β)}
3.2.3. Đánh giá thuật toán FP-growth.
Thuật toán này như đã phân tích ở trên, nó thực hiện hiệu quả hơn thuật toán
Apriori, thực hiện tốt cho mẫu phổ biến ngắn cũng như dài. Ta có một số nhận xét về
thuật toán như sau:
Độ phức tạp về thời gian:
• Chỉ duyệt CSDL 2 lần
• Thời gian xây dựng cây là o(n), ở đó n là số các tác vụ của CSDL. Tức là tuyến
tính với số các tác vụ.
Độ phức tạp về không gian:
• O(n), n là số các tác vụ của CSDL
• Độ cao của cây được giới hạn bởi kích thước của tác vụ lớn nhất
Thuật toán không bao giờ bị ngắn bởi một mẫu dài nào của mọi tác vụ. Cây FP-tree
duy trì đầy đủ thông tin cho khai phá các mẫu phổ biến. Đồng thời thuật toán cũng rút

luật kết hợp” để tìm các luật dựa trên các hóa đơn hiện có.
4.2. Thiết kế chương trình
Dữ liệu
HVTH:Trần Khánh An -CH1301076 21
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
Input: chương trình dùng xml để lưu trữ dữ liệu bán hàng. Bao gồm hai tập tin
1) Items.xml chứa các thông tin về các mặt hàng.
<Items>
<Item ID="1" Name="Bánh mì" />
<Item ID="2" Name="Nước ngọt" />
<Item ID="3" Name="Bia" />
<Item ID="4" Name="Sữa" />
<Item ID="5" Name="Khăn giấy" />
</Items>
2) Orders.xml chứa thông tin đơn hàng
<Orders>
<Order ID="1">
<Item ID="1" Price="50" Amount="4" />
<Item ID="2" Price="50" Amount="4" />
<Item ID="4" Price="50" Amount="4" />
</Order>

</Orders>
Khi chương trình chạy sẽ load 2 tập tin này.
Cài đặt
Thuật toán cài đặt tìm kiếm luật kết hợp làApriori.ProcessTransaction
đặt trong lớp Apriori.cs
Prototype của hàm
// items: danh sách các mặt hàng cửa hàng kinh doanh
//transactions/itemset: danh sách các tổ hợp/nhóm các mặt hàng thực tế khách hàng mua

1, 2, 3, 5 {3} 3
2, 5 {4} 1
{5} 3
C2 support
{1,2} 1
{1,3} 2
{1,5} 1
{2,3} 2
{2,5} 3
{3,5} 2
C3 support
{1,2,3} 0
{1,2,5} 1
{1,2,3,5} 1
{1,3,5} 1
{2,3,5} 2
Dừng
HVTH:Trần Khánh An -CH1301076 23
Công nghệ tri thức và ứng dụng GVHD: GS.TSKH.HOÀNG KIẾM
Bước 2: Tạo luật kết hợp (minconf=0.8)
rule support (X,Y) support (X) confidence
{1} => {3} 2 2 1
{2} => {3} 2 3 0.6
{2} => {5} 3 3 1
{3} => {5} 2 3 0.6
{2} => {3,5} 2 3 0.6
{3} => {2,5} 2 3 0.6
{5} => {2,3} 2 3 0.6
{3} => {1} 2 3 0.6
{3} => {2} 2 3 0.6