Đại Học Quốc Gia TP.HCM
Trường Đại Học Công Nghệ Thông Tin
***
BÀI THU HOẠCH MÔN
HỆ HỖ TRỢ QUYẾT ĐỊNH
ĐỀ TÀI:
LUẬT KẾT HỢP
THUẬT TOÁN APRIORI
GVHD :PGS.TS ĐỖ PHÚC
Người thực hiện: :Dương Trí Dũng
Mã học viên: :CH1301008
TP.HCM – 2014
1
LỜI CẢM ƠN
Lời đầu tiên, em xin gửi lời cảm ơn chân thành đến thầy PGS.TS Đỗ Phúc đã
tận tình truyền đạt kiến thức, đóng góp ý kiến cũng như hướng dẫn để em thực hiện
bài thu hoạch này.
Mặc dù đã rất cố gắng nhưng bài thu hoạch khó tránh khỏi những thiếu sót,
emrất mong thầy cô và bạn bè đóng góp ý kiến để bài thu hoạch hoàn thiện hơn.
Tp. HCM, tháng 06 năm 2014
Dương Trí Dũng
2
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong tiểu luận là trung thực và chưa từng được ai
công bố trong bất kỳ công trình nào khác.
Dương Trí Dũng (đã ký)
3
MỤC LỤC
LỜI MỞI ĐẦU
Trong thời đại bùng nổ công nghệ thông tin, các công nghệ lưu trữ dữ liệu

ngày càng phát triển tạo điều kiện cho các đơn vị thu thập dữ liệu tốt hơn. Đặc biệt
trong lĩnh vực kinh doanh, các doanh nghiệp đã nhận thức được tầm quan trọng của
việc nắm bắt và xử lý thông tin, nhằm giúp các chủ doanh nghiệp trong việc vạch ra
các chiến lược kinh doanh kịp thời mang lại những lợi nhuận to lớn cho doanh
nghiệp của mình. Tất cả lí do đó khiến cho các cơ quan, đơn vị và các doanh nghiệp
đã tạo ra một lượng dữ liệu khổng lồ cỡ Gigabyte thậm chí là Terabyte cho riêng
mình.
Khi lưu trữ các dữ liệu khổng lồ như vậy 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à luôn đượ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 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ó. Với những lý do như vậy, các phương pháp
quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được
4
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 (KDD - Knowledge Discovery and Data Mining).
Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số và các
ký hiệu, hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương
trình dưới một dạng nhất định. Chúng ta sử dụng các bit để đo lường các thông tin
và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa, được rút gọn tới mức tối
thiểu để đặc trưng một cách cơ bản cho dữ liệu. Chúng ta có thể xem tri thức như là
các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các
mối quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học.
Nói cách khác, tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao.
Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu
hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể

hiểu được. Còn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm
có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả
tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói
một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra
các mẫu và/hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị
che khuất bởi hàng “núi” dữ liệu.
Nhiều người coi khai phá dữ liệu và khám phá tri thức trong cơ sở dữ liệu là
như nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiế t yếu trong
quá trình phát hiện tri thức trong cơ sở dữ liệu.
5
Chương 1. TỔNG QUAN VỀ LUẬT KẾT HỢP
Lĩnh vực khai thác luật kết hợp cho đến nay đã được nghiên cứu và phát triển
theo nhiều hướng khác nhau. Có những đề xuất nhằm cải tiến tốc độ thuật toán, có
những đề xuất nhằm tìm kiếm luật có ý nghĩa hơn… và có một số hướng chính như
sau:
Luật kết hợp nhị phân là hướng nghiên cứu đầu tiên của luật kết hợp. Hầu
hết các nghiên cứu ở thời kỳ đầu về luật kết hợp đều liên quan đến luật kết hợp nhị
phân. Trong dạng luật kết hợp này, các mụ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 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á, … Một ví dụ về dạng luật này: “gọi liên tỉnh= ‘yes’ AND gọi di động=
‘yes’ => gọi quốc tế= ‘yes’ AND gọi dịch vụ 108 = ‘yes’, với độ hỗ trợ 20% và độ
tin cậy 80%”
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 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 rời rạc hoá nhằm chuyển dạng luật này về dạng nhị phân để có thể

áp dụng các thuật toán đã có. Một ví dụ về dạng luật này “phương thức gọi = ‘Tự
6
động’ AND giờ gọi IN [‘23:00:39 23:00:59’] AND Thời gian đàm thoại IN [‘200
300’] => gọi liên tỉnh = ‘có’ , với độ hỗ trợ là 23. 53% , và độ tin cậy là 80%”.
Luật kết hợp tiếp cận theo hướng tập thô: Tìm kiếm luật kết hợp dựa trên lý thuyết
tập thô.
Luật kết hợp nhiều mức: Cách tiếp cận theo luật này sẽ tìm kiếm thêm những
luật có dạng “mua máy tính PC =>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ể như “mua máy tính IBM PC
=>mua hệ điều hành Microsoft Windows AND mua phần mềm tiện ích văn phòng
Microsoft Office, …”. Như vậy 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.
Luật kết hợp mờ: Với những hạn chế còn gặp phải trong quá trình rời rạc hoá
các thuộc tính số (quantitave attributes), các nhà nghiên cứu đã đề xuất luật kết hợp
mờ nhằm khắc phục các hạn chế trên 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 một ví dụ của dạng này là: “thuê bao tư nhân =
‘yes’ AND thời gian đàm thoại lớn AND cước nội tỉnh = ‘yes’ =>cước không hợp lệ
= ‘yes’, với độ hỗ trợ 4% và độ tin cậy 85%”. Trong luật trên, điều kiện thời gian
đàm thoại lớn ở vế trái của luật là một thuộc tính đã được mờ hoá.
Luật kết hợp với thuộc tính được đánh trọng số: Trong thực tế, các thuộc tính
trong CSDL không phải lúc nào cũng có vai trò như nhau. Có một số thuộc tính
được chú trọng hơn và có mức độ quan trọng cao hơn các thuộc tính khác. Ví dụ khi
khảo sát về doanh thu hàng tháng, thông tin về thời gian đàm thoại, vùng cước là
quan trọng hơn nhiều so với thông tin về phương thức gọi Trong quá trình tìm
kiếm luật, chúng ta sẽ gán thời gian gọi, vùng cước các trọng số lớn hơn thuộc tính
phương thức gọi. Đây là hướng nghiên cứu rất thú vị và đã được một số nhà nghiên
cứu đề xuất cách giải quyết bài toán này. Với luật kết hợp có thuộc tính được đánh
trọng số, chúng ta sẽ khai thác được những luật “hiếm” (tức là có độ hỗ trợ thấp,
nhưng có ý nghĩa đặc biệt hoặc mang rất nhiều ý nghĩa).
7

Luật kết hợp song song: Bên cạnh khai thác luật kết hợp tuần tự, các nhà làm
tin học cũng tập trung vào nghiên cứu các thuật giải song song cho quá trình phát
hiện luật kết hợp. Nhu cầu song song hoá và xử lý phân tán là cần thiết bởi kích
thước dữ liệu ngày 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.
8
Chương 2. LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU
VÀ THUẬT TOÁN APRIORI
2.1. Khai phá luật kết hợp[3]
Được giới thiệu từ năm 1993, bài toán khai thác luật kết hợp nhận được rất nhiều sự
quan tâm của nhiều nhà khoa học. Ngày nay việc khai thác các luật như thế vẫn là một
trong những phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và
khai thác dữ liệu.
Mục đích chính của khai phá dữ liệu là các tri thức được kết xuất ra sẽ được sử
dụng trong dự báo thông tin trợ giúp trong sản xuất kinh doanh và nghiên cứu khoa học.
Trong hoạt động sản xuất kinh doanh, ví dụ kinh doanh các mặt hàng tại siêu thị,
các nhà quản lý rất thích có được các thông tin mang tính thống kê như: “90% phụ nữ có
xe máy màu đỏ và đeo đồng hồ Thuỵ Sỹ thì dùng nước hoa hiệu Chanel” hoặc “70% khách
hàng là công nhân khi mua TV thường mua loại TV 21 inches”. Những thông tin như vậy
rất hữu ích trong việc định hướng kinh doanh. Vậy vấn đề đặt ra là liệu có tìm được các
luật như vậy bằng các công cụ khai phá dữ liệu hay không? Câu trả lời là hoàn toàn có thể.
Đó chính là nhiệm vụ khai phá luật kết hợp.
Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong đó sự xuất hiện

của tập các mục S nào đó trong các bản ghi của D sẽ kéo theo sự xuất hiện của một tập
những mục U cũng trong những bản ghi đó. Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ
lệ. Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi trong D chứa cả S và U.
Vấn đề khám phá luật kết hợp được phát biểu như sau: Cho trước tỉ lệ hỗ trợ
θ
và
độ tin cậy
β
. Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn
θ

và
β
tương ứng.
Giả thiết D là CSDL giao dịch và với
θ
= 40%,
β
= 90%. Vấn đề phát hiện luật
kết hợp được thực hiện như sau:
Liệt kê, đếm tất cả những qui luật chỉ ra sự xuất hiện một số các mục sẽ kéo theo
một số mục khác.
Chỉ xét những qui luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn 90%.
Hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách hàng được
yêu cầu điền vào các mẫu bán hàng để công ty có được một CSDL về các yêu cầu của
9
khách hàng. Giả sử công ty quan tâm đến mối quan hệ "tuổi, giới tính, nghề nghiệp và sản
phẩm". Khi đó có thể có rất nhiều câu hỏi tương ứng với luật trên. Ví dụ trong lứa tuổi nào
thì những khách hàng nữ là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là
nhiều nhất, thoả mãn một ngưỡng nào đó ?

2.1.1. Định nghĩa luật kết hợp [2]
Cho một tập I = {I
1
, I
2
, , I
m
} 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.
Đ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à:
{ }
D
TXDT
X
⊆∈
=
|
)sup(
Độ 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à |X|=k.
10
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:
)sup(
)sup(
)(
)(
|()(
X
YX
TXp
TXTYp
IXIYpYXconf
∪
=
⊆
⊆∧⊆
=⊆⊆=⇒
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ỗ trợ và tin cậy cụ thể. Thực vậy, cho một tập các giao dịch D, bài

toán phát hiện luật kết hợp là sinh ra tất cả các luật kết hợp mà có độ tin cậy conf
lớn hơn độ tin cậy tối thiểu minconf và độ hỗ trợ sup lớn hơn độ hỗ trợ tối thiểu
minsup tương ứng do người dùng xác định. Khai phá luật kết hợp được phân thành
hai bài toán con:
Bài toán 1: Tìm tất cả các tập mục mà có độ hỗ trợ lớn hơn độ hỗ trợ tối
thiểu do người dùng xác định. Các tập mục thoả mãn độ hỗ trợ tối thiểu được gọi là
các tập mục phổ biến.
Bài toán 2: Dùng các tập mục phổ biến để sinh ra các luật mong muốn. Ý
tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có thể
xác định luật nếu AB => CD giữ lại với tỷ lệ độ tin cậy:
)sup(
)sup(
AB
ABCD
conf =
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.1.2. Các tính chất của tập phổ biến
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)
11
Đ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à sup(B)< minsup
thì một tập con A của 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.1.3. Các tính chất của luật kết hợp
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
Tuy nhiên đảo lại: X→Y∪Z ⇒ X→Y ∧ X→Z
Tính chất 3: (Các luật kết hợp không có tính bắc cầu)
Nếu X→Y và Y→Z, chúng ta không thể suy ra X→Z.
12
Ví dụ: giả sử T(X) ⊂ T(Y) ⊂ T(Z), ở đó T(X), T(Y), T(Z) tương ứng là các giao
dịch chứa X,Y,Z, và độ tin cậy cực tiểu minconf
conf(X→Y) =conf(Y→Z)=minconf thế thì: conf(X→Y) =minconf2 < minconf vì
minconf < 1, do đó luật X→Z không đủ độ tin cậy
Tính chất 4:
Nếu A→(L - A) không thoả mãn độ tin cậy cực tiểu thì luật
B →(L -B) cũng không thoả mãn, với các tập mục L,A,B và B ⊆ A ⊂ L
Vì supp(B) ≥ sup(A) (theo tính chất 1) và định nghĩa độ tin cậy, chúng ta nhận
được:
conf
B
L
B
L

BL min
)sup(
)sup(
)sup(
)sup(
)( conf(B
< ≤=)−→
Cũng như vậy: Nếu có (L-C)→ C thì ta cũng có luật (L – D)→D, với D⊆C và D≠∅.
Bởi vì D⊆C nên (L - D) ⊇ (L - C), do đó sup(L - D) ≤ sup(L-C)
⇒

−
≥
−
)sup(
)sup(
)sup(
)sup(
CL
L
DL
L
≥ minconf
2.2. Thuật toán Apriori [v4]
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.
13
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
: Tập các tập k-mục phổ biến (với độ hỗ trợ cực tiểu minsup nào đó)
C
k
: Tập các tập k-mục ứng cử (các tập mục phổ biến tiềm năng)
Input: CSDL D, minsup.
Output: Tập các tập mục phổ biến.
1. L
1
= {Các 1 - itemsetphổ biến};
2. k=2;
3. While( L
k-1
! =
∅
)
4. { C
k
= apriori_gen(L
k-1

, minsup);// các ứng cử mới theo chương trình con ở
dưới đây.
5. for( ∀ giao dịch t∈ D)
6. { C
t
=Subset (C
k
,t);// ứng cử viên được chứa trong t
7. for (∀ứng cử c ∈ C
t
)
8. c.count ++;
10. }
11. L
k
={ c
∈
C
k

c.count
≥
minsup}
12. k++;
13. }
14. Return L=
∪
k
L
k'

;
// sinh ứng cử viên mới (**)
Void apriori_gen(L
k-1
, minsup )
14
1. { for(
∀
itemset l
1
∈
L
k-1
)
2. for(
∀
itemset l
2
∈
L
k-1
)
3. if((L
1
(1)== L
2
(1)&&L
1
(2) == L
2

(2)&& && L
1
(k-2) == L
2
(k-2)) &&L
1
(k-1)
== L
2
(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 1- itemset phổ biến. Lần duyệt thứ k (k ≥ 2) sẽ bao gồm 2 giai đoạn:
Tập phổ biến L
k-1
đã tìm thấy ở lần duyệt thứ k-1 được sử dụng để sinh
ra các tập ứng cử viên C
k
bằng việc sử dụng hàm Apriori_gen.
Dựa vào CSDL, tính độ hỗ trợ của các ứng của viên trong C
k
. Các ứng
cử viên trong C
k
mà được chứa trong giao dịch t có thể được xác định một cách hiệu
quả bằng việc sử dụng cây băm được mô tả như sau:
15
Trong giai đoạn 2 (giai đoạn sửa, tỉa): xoá bỏ các tập c
∈
C
k
sao cho một vài
(k-1) – tập con của c không nằm trong L

k-1
. Thủ tục này là đầy đủ bởi đối với bất kì
tập nào L
k
với độ hỗ trợ tối thiểu thì các tập con kích cỡ (k-1) cũng có độ hỗ trợ tối
thiểu, do đó nếu ta mở rộng mỗi tập trong L
k-1
với tất cả các tập mục có thể và sau
đó xoá tất cả các tập mà (k-1) – tập con của nó không nằm trong L
k-1
, ta sẽ nhận
được tập các tập trong L
k.
Việc kết nối là tương đương với việc mở rộng L
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. 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ỏ trong Bucket tương ứng. Tất cả các nút ban
đầu được tạo ra như là nút lá. Khi số các tập trong một nút lá vượt quá ngưỡng được
chọn, nút lá này được chuyển thành một nút trong.
Bắt đầu từ nút gốc, hàm Subset tìm tất cả các ứng cử viên được chứa trong
giao dịch t như sau: Nếu ta bắt đầu tại một lá, ta tìm những tập trong nút lá này
được chứa trong giao dịch t và bổ sung các mối quan hệ với chúng đối với tập kết
quả mong muốn. Nếu ta đang ở một nút trong và ta đến được nó bằng việc băm mục
i, ta băm trên mỗi mục đi sau i trong t và áp dụng một cách đệ quy thủ tục đó đối
với nút này trong Bucket tương ứng. Đối với nút gốc, ta băm theo mỗi mục trong t.
16
Để thấy được tại sao hàm Subset trả lại tập các tham khảo mong muốn hãy
để ý đến những gì sẽ xảy ra tại nút gốc. Đối với bất kỳ tập c nào được chứa trong
giao dịch t, mục đầu tiên cần phải có trong t. Tại nút gốc, việc băm mọi mục trong t
đảm bảo được rằng ta chỉ không biết các tập mà nó bắt đầu với một mục không nằm
trong t. Những lí luận tương tự áp dụng cho các mức sâu hơn. Vì các mục trong bất
kì tập nào cũng được sắp thứ tự, nếu ta đến được một nút hiện tại bằng việc băm
mục i, ta chỉ cần quan tâm đến những mục trong t nó xuất hiện sau i.

// Bước tỉa: Xoá bớt tất cả các tập mục c ∈ C
k
mà (k-1) tập con của c không phụ
thuộc L
k-1
.
1. for (∀ tập mục c ∈ C
k
)
2. for (∀ (k-1) – tập con s của c)
3. if(s ∉ L
k-1
)
4. delete c khỏi C
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.
2.3. Sinh các luật kết hợp từ các tập 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 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

17
X → Y là: conf (X → Y) = P(Y/X) = sup(X∪Y)/sup(X) với 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ả mãn, tức là độ hỗ trợ của luật
chính là sup(l).
Thuật toán đơn giản.
Chúng ta cải tiến thủ tục xử lý bằng cách sinh ra các tập con của mục lớn
theo kiểu đệ qui ưu tiên độ sâu. Ví dụ: với tập mục ABCD, đầu tiên chúng ta xét tập
con ABC, sau đó đến AB,
Tiếp đến, nếu tập con a của tập mục lớn l không sinh ra được luật thì không
cần xét đến các tập con của nó nữa. Chẳng hạn: nếu luật ABC→ D không đủ độ tin
cậy thì ta không cần xét đến luật AB→ CD.
Điều này có thể chứng minh đơn giản như sau:
Nếu luật a →(l-a) không thoả mãn độ tin cậy, tức là: conf(a→l-a)) nhỏ hơn minconf,
thế thì với bất kỳ tập con b nào của a ta có:
Vì b⊂ a nên supp(b)≥supp(a), do vậy:
Conf(b→(l-b)) =
)sup(
)sup(
)sup(

)sup(
a
l
b
l
≤
=conf((a→(l-a))<minconf
Tức là độ tin cậy của luật b→(l-b) cũng nhỏ hơn minconf
Thuật toán đơn giản này có thể mô tả như sau:
18
Thuật toán 1.
For all large itemsets l
k
, k≥2 do call genrules(l
k
,l
k
)
Procedure genrules(l
k
:large k-itemsets, a
m
: large m-itemsets)
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
-a
m-1
),
with confidence=conf and support=support(l
k
)
if (m-l > l) then call genrules(l
k
,a
m-1
);
//để sinh ra các luật với tập con của a
m-1
là phần tiền đề
end
end

Thuật toán nhanh hơn.
Ở trên ta đã chỉ ra rằng nếu một luật không thoả mãn với tập cha a thì cũng
không thoả mãn với tập con của nó. Ví dụ như trên đã xét: nếu ABC→D không đủ
độ tin cậy thì luật AB→CD cũng không đủ độ tin cậy. Điều đó cũng có thể áp dụng
theo hướng ngược lại như sau: nếu xảy ra luật với tập con thì cũng xảy ra luật với
tập cha. Ví dụ: nếu luật AB→CD có đủ độ tin cậy thì luật ABC→D cũng đủ độ tin
cậy.
Thuật toán 2.
For all larger itemsets l
k
, k≥ 2 do
Begin
19
H
l
={các phần kết luận của các luật nhận được từ 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
-h
m+1
);
If (conf ≥minconf) then
Output the rule(l
k
-h
m+1
)→h
m+1
//với độ tin cậy là conf và độ hỗ trợ là support (l
k
)
Else

Delete h
m+1
from H
m+1
End
Call ap_genrules(l
k
, H
m+1
)
End
Thuật toán nhanh hơn này sử dụng thủ tục apriori_gen mô tả ở phần thuật
toán Apriori ở trên. Ta xem tại sao thuật toán 2 này nhanh hơn thuật toán 1 trên:
Ví dụ, ta xét tập mục ABCDE: Giả sử rằng ACDE→B, ADE→CB là các luật có l-
mục ở phần kết luận thoả mãn độ hỗ trợ cực tiểu minconf.
20
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.
Chương 3. TRÌNH BÀY THUẬT TOÁN APRIORI
Giả sử ta có có sở dữ liệu giao dịch (Transaction Database -TDB) như sau :
Thuật toán Apriori khai phá luật kết hợp được mô tả qua các bước sau
21
Ta có frequent itemsets I ={B,C,E}, với min_conf =80% ta có 2 luật kết hợp
là

{B,C} => {E} và {C,E} => {B}

Giả sử có cơ sở dữ liệu giao dịch bán hàng gồm 5 giao dịch như sau:
22
Thuật toán Apriori tìm các luật kết hợp trong giao dịch bán hàng trên như
sau:

Kết quả ta có các luật kết hợp sau (với min_sup= 40%, min_conf=70%)
23
R1: Beer => Diaper (support =60%, confidence = 75%)
R2: Diaper =>Beer (support =60%,confidence = 75%)
R3: Milk =>Beer (support =40%, confidence = 100%)
R4: Baby Powder => Diaper (support =40%,confidence = 100%)
Từ kết quả các luật được sinh ra bởi giao dịch bán hàng trên, ta thấy rằng có
luật có thể tin được (hợp lý) như Baby Powder => Diaper, có luật cần phải phân
tích thêm như Milk =>Beer và có luật có vẻ khó tin như Diaper =>Beer.Ví dụ này
sinh ra các luật có thể không thực tế vì dữ liệu dùng để phân tích (transaction
database) hay còn gọi là tranining data rất nhỏ.
24
Chương 4. THỰC NGHIỆM VÀ THẢO LUẬN
Restore database Apriori vào database server và thiết lập chương trình khi
chạy lần đầu tiên ở file App.config. Tìm đến đoạn sau:
<connectionStrings>
<add name="DataConnection" providerName="System.Data.SqlClient"
connectionString="Data Source=.\Standard;Initial Catalog=APriori;Persist
Security Info=True;User ID=sa;Password=123" />
</connectionStrings>
Chỉnh sử lại để phù hợp với database bạn muốn sử dụng.
Chương trình sử dụng dotnet 4.5, Entity Framework Code First 6.1
Giao diện chính của chương trình như sau:

Nhập Min_Support và Min_Confidence cho thuật toán:
25