TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
----------

BÁO CÁO BÀI TẬP LỚN
MÔN KHAI PHÁ DỮ LIỆU
ĐỀ TÀI: TÌM HIỂU GIẢI THUẬT APRIORI
Giảng viên hướng dẫn: Nguyễn Quốc Tuấn
Sinh viên thực hiện: Nhóm 07
Họ và tên
Bùi Thị Vân
Đặng Thị Thanh Loan
Đỗ Hoàng Trung
Đỗ Thị Thùy
Lê Thị Lan Phương

Mã sinh viên
181201178
181213060
181202261
181201887
181200836

Lớp: Cơng nghệ thơng tin 4
Khóa 59
Hà Nội, 2021


MỤC LỤC
LỜI NĨI ĐẦU ..................................................................................................................... 3
I. Tìm hiểu tổng quan về Luật kết hợp ............................................................................. 4

1.

Giới thiệu về luật kết hợp ....................................................................................... 4

2.

Các thuật toán được áp dụng ................................................................................. 6

3.

Lĩnh vực ứng dụng .................................................................................................. 6

II. Tìm hiểu thuật tốn Apriori ....................................................................................... 10
1. Mơ tả thuật tốn ........................................................................................................ 10
2. Apriori Algorithm .................................................................................................... 10
3. Ví dụ ........................................................................................................................... 10
III. Ứng dụng thuật tốn .................................................................................................. 17
1. Tên ứng dụng ............................................................................................................. 17
2. Nguồn dữ liệu............................................................................................................. 17
3. Cách thức thực hiện .................................................................................................. 17
4. Kết quả ....................................................................................................................... 21
Tài liệu tham khảo: .......................................................................................................... 22


LỜI NĨI ĐẦU
Trong thời buổi hiện đại ngày nay, cơng nghệ thơng tin cũng như những ứng dụng
của nó khơng ngừng phát triển, lượng thông tin và cơ sở dữ liệu được thu thập và lưu trữ
cũng tích lũy ngày một nhiều lên. Con người cũng vì thế mà cần có thơng tin với tốc độ
nhanh nhất để đưa ra quyết định dựa trên lượng dữ liệu khổng lồ đã có. 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 thực tế, vì

thế, 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 nhanh
chóng được phát triển.
Khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác
nhau ở các nước trên thế giới. Ở Việt Nam, kỹ thuật này đang được nghiên cứu và dần đưa
vào ứng dụng. Khai phá dữ liệu là một bước trong quy trình phát hiện tri thức. Hiện nay,
mọi người khơng ngừng tìm tịi các kỹ thuật để thực hiện khai phá dữ liệu một cách nhanh
nhất và có được kết quả tốt nhất.
Trong bài tập lớn này, chúng em tìm hiểu và trình bày về một thuật tốn khai phá
luật kết hợp cũng như tổng quan về luật kết hợp, với đề tài “Tìm hiểu giải thuật Apriori”.
Trong quá trình làm bài tập lớn này, chúng em xin gửi lời cảm ơn đến thầy giáo
Nguyễn Quốc Tuấn. Thầy đã rất tận tình hướng dẫn chi tiết cho chúng em, những kiến thức
thầy cung cấp rất hữu ích. Chúng em rất mong nhận được những góp ý từ thầy.
Chúng em xin chân thành cảm ơn!
Sinh viên nhóm 07.


I. Tìm hiểu tổng quan về Luật kết hợp
1. Giới thiệu về luật kết hợp
Bài toán kinh điển dẫn đến việc khai phá luật kết hợp

a.

Bài toán giỏ mua hàng trong siêu thị. Giả định chúng ta có rất nhiều mặt hàng, ví dụ
như “bánh mì”, “sữa”,…(coi là tính chất hoặc trường). Khách hàng khi đi siêu thị sẽ bỏ vào
giỏ mua hàng của họ một số mặt hàng nào đó, và chúng ta muốn tìm hiểu các khách hàng
thường mua các mặt hàng nào đồng thời, chúng ta không cần biết khách hàng cụ thể là ai.
Nhà quản lý dùng những thông tin này để điều chỉnh việc nhập hàng về siêu thị, hay đơn
giản là để bố trí sắp xếp các mặt hàng gần nhau, hoặc bán các mặt hàng đó theo một gói
hàng, giúp cho khách đỡ mất cơng tìm kiếm.
Khai phá luật kết hợp được mơ tả như sự tương quan của các sự kiện, những sự kiện

xuất hiện thường xuyên một cách đồng thời.
Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện
trong một khối lượng giao dịch lớn của một cơ sở dữ liệu cho trước.
b. Các khái niệm và định nghĩa.
•

Tập mục(Itemset)

Gọi I = {x , x , . . . , x } là tập n mục (item). Một tập X ⊆ I được gọi là một tập mục
(itemset).Nếu X có k mục (tức |X| = k) thì X được gọi là k–itemset.
1

•

2

n

Giao dịch và cơ sở dữ liệu giao dịch(Transaction & Transactional Database)

Transaction là một thành phần cơ sở dữ liệu mà nó bao gồm tập hợp các item.
Transaction được ký hiệu là T và T⊆I. Một transaction chứa tập hợp các item
T={I1,I2,…,Im}.
Ký hiệu D = {T ,T , . . . , T } là cơ sở dữ liệu gồm m giao dịch (transaction). Mỗi
giao dịch T ∈ D là một tập mục, tức T ⊆ I.
1

2

i


•

m

i

Tập/mẫu phổ biến (frequent itemset/pattern)
Cho tập mục X (⊆ I)

•

Độ hỗ trợ của X, kí hiệu là supp(X, D), là số lượng giao dịch trong D chứa tập X:
supp(X, D) = |{T|T ⊆ D và X ⊆ T}|

•

Độ hỗ trợ tương đối của X, kí hiệu là rsupp(X, D) là số phần trăm các giao dịch
trong D chứa X:
rsupp(X, D) = supp(X, D)/|D|


•

•

Tập mục X được gọi là tập phổ biến trong cơ sở giao dịch D nếu sup(X, D) >=
minsup, với minsup là một ngưỡng độ hỗ trợ tối thiểu (minimum support threshold)
do người dùng định nghĩa.
F là kí hiệu của tất cả các tập phổ biến

F là ký hiệu của tập các tập phổ biến có độ dài k
(k)

Luật kết hợp

c.

Cho I={I1, I2, .., Im} là tập hợp của m tính chất riêng biệt. Giả sử D là CSDL, với các bản
ghi chứa một tập con T các tính chất (có thể coi như T ⊆ I ), các bản ghi đều có chỉ số riêng.
Một luật kết hợp là một mệnh đề kéo theo có dạng X → Y, trong đó X, Y⊆ I, thỏa mãn
điều kiện X ∩Y =Ø. Các tập hợp X và Y được gọi là các tập hợp tính chất (itemset). Tập X
gọi là nguyên nhân, tập Y gọi là hệ quả.
Có 2 độ đo quan trọng đối với luật kết hợp: Độ hỗ trợ (support) và độ tin cậy (confidence),
được định nghĩa như phần dưới đây.
•

Độ hỗ trợ(support)
• Độ hỗ trợ của một luật kết hợp X⟶ Y là tỷ lệ giữa số lượng các giao dịch
chứa tập hợp X ⟶ Y, so với tổng số các giao dịch trong D - Ký hiệu supp(X
⟶ Y).
supp(X ⟶ Y) = (X
•

∪Y).countn

Độ hỗ trợ tương đối của luật X⟶Y trong cơ sở dữ liệu D kí hiệu là
rsupp(X⟶Y, D) là số phần trăm các giao dịch trong D chứa cả X và Y.
rsupp(X⟶Y, D) = supp(X∪Y,

D)|D|


Nếu độ hỗ trợ của một kết kết hợp X ⟶ Y là 30% thì có nghĩa là 30% tổng số bản ghi
chứa X hợp Y. Như vậy độ hỗ trợ mang ý nghĩa thống kê của luật.
•

Độ tin cậy

Độ tin cậy (confidence) của luật X → Y trong D, ký hiệu conf (X → Y , D), là tỉ lệ giữa
số giao dịch chứa cả X và Y trên số giao dịch chỉ chứa X.
conf(X⟶Y, D) = (X∪Y).countX.count
Ký hiệu độ tin cậy của một luật r là conf(r). Ta có 0 <= conf(r) <= 1
Độ hỗ trợ và độ tin cậy có xác suất như sau:
•

Độ hỗ trợ là xác suất trong giao dịch chứa cả X và Y.


•

Độ tin cậy là xác suất có điều kiện mà một giao dịch trong D chứa Y trong
khi đã chứa X (bản chất vẫn là mức độ tin cậy của luật).
Supp(X⟶Y)=P(X∪Y)
Conf (X⟶Y) = P(Y/X)=supp(X∪Y)/supp(X)

•

•

2.


Kết luận
• Luật X ⟶ Y được gọi là phổ biến nếu sup(X⟶Y, D) >= minsup (minsup do
người dùng định nghĩa)
• Luật X⟶ Y được gọi là mạnh nếu độ tin cậy của nó lớn hơn hoặc bằng một
ngưỡng minconf do người dùng định nghĩa: conf (X⟶Y) >= minconf
Tính chất
• Tính chất 1: Giả sử A,B ⊆ I là hai tập hợp với A⊆B thì sup(A) >= sup(B).
Như vậy, những bản ghi nào chứa tập hợp B thì cũng chứa tập hợp A
• Tính chất 2: Giả sử A, B là hai tập hợp, A,B ⊆ I, nếu B là tập phổ biến và
A⊆B thì A cũng là tập phổ biến. Vì nếu B là tập phổ biến thì sup(B) >=
minsup, mọi tập hợp A là con của tập hợp B đều là tập phổ biến trong cơ sở
dữ liệu D vì sup(A) >= sup(B) (Tính chất 1)
• Tính chất 3: Giả sử A, B là hai tập hợp, A ⊆ B và A là tập hợp khơng thường
xun thì B cũng là tập hợp khơng thường xun (Tính chất 1) (Tức nếu A là
tập hợp khơng phổ biến thì mọi tập cha của nó cũng khơng biến)
Các thuật toán được áp dụng

-

Thuật toán Apriori

-

Thuật toán FP-Growth
3.

Thuật toán Brute-Force
Lĩnh vực ứng dụng

a, Phân lớp, phân loại (classification/decision rules)

b, Phân tích dữ liệu bán lẻ (market basket analysis)


c, Tư vấn trực tuyến (online recommendation)

d, Hiểu người dùng trực tuyến (user understanding)


e, Phân tích tìm ngoại lệ (outlier detection)
f, Ứng dụng trong các bài tốn viễn thơng (vd:churn prediction)


g. Phân tích dữ liệu di truyền.
h. Phân tích dữ cấu trúc mạng.


II. Tìm hiểu thuật tốn Apriori
1. Mơ tả thuật tốn
- Tư tưởng chính của thuật tốn Apriori là:
+ Tìm tất cả frequent itemsets:
k-itemset (itemsets gồm k items) được dùng để tìm (k+1)- itemset.
Đầu tiên tìm 1-itemset (ký hiệu L1). L1 được dùng để tìm L2 (2-itemsets). L2 được dùng
để tìm L3 (3-itemset) và tiếp tục cho đến khi khơng có k-itemset được tìm thấy.
+ Từ frequent itemsets sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn 2 tham số
min_sup và min_conf)
- Tính chất: mọi tập con khác rỗng của một itemset phổ biến cũng phải là itemset phổ biến.
2. Apriori Algorithm
Bước 1: Duyệt (Scan) toàn bộ transaction database để có được support S của 1-itemset, so
sánh S với min_sup, để có được 1-itemset (L )
Bước 2: Sử dụng L nối (join) L để sinh ra candidate k-itemset. Loại bỏ các itemsets

không phải là frequent itemsets thu được k-itemset
Bước 3: Scan transaction database để có được support của mỗi candidate k-itemset, so sánh
S với min_sup để thu được frequent k –itemset (L )
Bước 4: Lặp lại từ bước 2 cho đến khi Candidate set (C) trống (không tìm thấy frequent
itemsets)
Bước 5: Với mỗi frequent itemset I, sinh tất cả các tập con s không rỗng của I
Bước 6: Với mỗi tập con s không rỗng của I, sinh ra các luật s => (I-s) nếu độ tin cậy
(Confidence) của nó > =min_conf.
3. Ví dụ
1

k-1

k-1

k

Bảng 1 biểu diễn một giao dịch cơ sở dữ liệu có 4 giao dịch.
TID là một nhận dạng duy nhất cho mỗi giao dịch.
TABLE_1
TID

Support

T100

A,C, D

T200


B, C, E

T300 A, B, C, E
T400

B, E


•

Thực hiện bước đầu tiên là chức năng duyệt cơ sở dữ liệu để xác định số lượng sự
xuất hiện cho một item cụ thể. Sau bước đầu tiên chúng ta sẽ có C1 được thể hiện
trong Table 2.

TABLE_2 C1
Itemset Support
{A}

2

{B}

3

{C}

3

{D}


1

{E}

3

•

Bước tiếp theo là bước cắt tỉa, trong đó support tập phổ biến được so sánh với
minimum support. Các tập phổ biến thỏa mãn minimum support sẽ được xử lý tiếp
tục. Giả sử rằng minimum support là 2. Chúng ta sẽ có được L1 từ bước này. TABLE
3 cho thấy kết quả cắt tỉa.

TABLE_3 L1
Itemset Support
{A}

2

{B}

3

{C}

3

{E}

3


•

Bây giờ bước tiếp theo phát sinh ứng viên được thực hiện trong đó tất cả ứng viên
có thể có 2 tập phổ biến ứng viên được tạo. Bảng này được ký hiệu là C2. TABLE
4 cho thấy tất cả khả năng kết hợp mà có thể tạo ra từ TABLE 3 tập phổ biến.

TABLE_4 C2
Itemset Support
{A, B}

1

{A, C}

2

{A, E}

1


{B, C}

2

{B, E}

3


{C, E}

2

•

Bây giờ cắt tỉa phải được thực hiện trên cơ sở các điều kiện minimum support. Từ
TABLE 4 hai tập phổ biến sẽ được loại bỏ. Sau khi cắt tỉa chúng ta nhận được kết
quả như sau:

TABLE_5 L2
Itemset Support
{A, C}

2

{B, C}

2

{B, E}

3

{C, E}

2

•


Các q trình tương tự được tiếp tục cho đến khi khơng có tập phổ biến hoặc bộ ứng
viên có thể tạo ra. Tiến trình được mô tả trong TABLE 6 và TABLE 7.

TABLE_6 C3
Itemset Support
{A, C}

2

{B, C}

2

{B, E}

3

TABLE_7 (Kết quả cuối cùng)
Itemset

Support

{B, C, E}

2

Ví dụ bài 6.6: Cho Dataset D: minsup = 60%, minconf = 80%


min_sup = 60% → min_sup_count = 60% * 5 = 3

I = {A, C, D, E, I, K, M, N, O, U, Y}
1. C = I
1

→L:
1


Tìm tập ứng viên L ⨝ L :

2.

1

→C:
2

1


→L:
2

3.

Tìm tập ứng viên L ⨝ L :
2

2



→C:
3

→L:
3

L=L ∪L ∪L
1

2

3

→ L = (E, K, M, O, Y, {E, K}, {E, O}, {K, M}, {K, O}, {K, Y}, {E, K, O}.
4.

Tìm các luật kết hợp mạnh:

{E, K} → O

conf = 3/4 = 75%

{E, O}→ K

conf = 3/3 = 100%

{K, O} → E

conf = 3/3 = 100%


E → {K, O}

conf = 3/4 = 75%

K → {E, O}

conf = 3/5 = 60%

O → {E, K}

conf = 3/3 = 100%

E→K

conf = 4/4 = 100%

K→E

conf = 4/5 = 80%

E→O

conf = 3/4 = 75%

O→E

conf = 3/3 = 100%

K→M


conf = 3/5 = 60%

M→K

conf = 3/3 = 100%

K→O

conf = 3/5 = 60%

O→K

conf = 3/3 = 100%


K→Y

conf = 3/5 = 60%

Y→K

conf = 3/3 = 100%

min_conf = 80% nên suy ra các luật kết hợp mạnh là:
{E, O}→ K
{K, O} → E
O → {E, K}
E→K
K→E

O→E
M→K
O→K
Y→K
III. Ứng dụng thuật toán
1. Tên ứng dụng: Market basket analysis
2. Nguồn dữ liệu:
- UCI Machine Learning Repository:
( />-

Đây là tập dữ liệu Bán lẻ Trực tuyến II này do Daqing Chen tạo lên chứa tất cả các

giao dịch xảy ra cho một cửa hàng bán lẻ trực tuyến khơng có cửa hàng và có trụ sở tại
Vương quốc Anh trong khoảng thời gian từ ngày 01/12/2009 đến ngày 09/12/2011
3. Cách thức thực hiện
a. Xử lý dữ liệu
Dữ liệu được dùng là dữ liệu giao dịch của khách hàng, qua đó tìm ra mối tương quan
giữa các sản phẩm đã bán tại cửa hàng.
-

Một số dữ liệu gốc:


-

Sau khi xử lý dữ liệu được các giao dịch trong tháng 10/2010 gồm 960 thuộc tính
và 137 giao dịch:

Hình 1. Dữ liệu về một số giao dịch
Bảng dữ liệu có 2 cột : Transaction và ItemSet. Mỗi dịng chỉ liệt kê 1 itemset các mã

sản phẩm, mỗi mã sản phẩm thể hiện một sản phẩm duy nhất.


Mẫu dữ liệu gơm 960 mã sản phẩm:

Hình 2. Một số sản phẩm tương ứng mã sản phẩm
Cài đặt thuật tốn
Lựa chọn ngơn ngữ lập trình: HTML,CSS,Javascript
Cơng cụ lập trình: Visual studio code
Cài đặt:
Đưa dữ liệu về dạng định tính: sản phẩm được mua là 1, sản phẩm không được
mua là 0.
+ Tìm tập ứng viên
b.
+


+ Tính support

+ Tìm tập phổ biến


4. Kết quả

+
+
+
+
+
+


Với Support Threshold = 8% tìm được tập phổ biến gồm 6 phần tử:
{85123A} support: 10,95%
{84029E} support: 8,76%
{22632}
support: 11,68%
{22961}
support: 8,76%
{22866}
support: 8,76%
{22865}
support: 8,03%


Tài liệu tham khảo:
•

•

/>2sEZC1Y5a2t2Y
a/p/khai-pha-mau-pho-bien-va-luat-ket-hop-gGJ59QAa5X2