1
LUẬT KẾT HỢP
(Association Rules)
Chương 2
2
03/29/14
www.lhu.edu.vn
•
Phân tích việc
Phân tích việc
mua hàng của
mua hàng của
khách hàng bằng
khách hàng bằng
cách tìm ra những
cách tìm ra những
“mối kết hợp” giữa
“mối kết hợp” giữa
những mặt hàng
những mặt hàng
mà khách đã mua.
mà khách đã mua.
•
Bài toán được
Bài toán được
Agrawal thuộc
Agrawal thuộc
nhóm nghiên cứu
nhóm nghiên cứu
của IBM đưa ra
của IBM đưa ra

khăn ⇒ bia [0.5%, 60%]
–
mua:khăn ⇒ mua:bia [0.5%, 60%]
–
“Nếu mua khăn thì mua bia trong 60% trường hợp. Khăn và
bia được mua chung trong 0.5% dòng dữ liệu."
Các biểu diễn khác:
Các biểu diễn khác:
–
mua(x, “khăn") ⇒ mua(x, “bia") [0.5%, 60%]
–
khoa(x, "CS") ^ học(x, "DB") ⇒ điểm(x, "A") [1%, 75%]
Luật kết hợp: Cơ sở
Luật kết hợp: Cơ sở
5
khăn ⇒ bia [0.5%, 60%]
Luật kết hợp: Cơ sở
Luật kết hợp: Cơ sở
Tiền đề
Tiền đề, vế trái luật
Mệnh đề kết quả
Mệnh đề kết quả, vế phải luật
Support
Support, độ hỗ trợ/ủng hộ (“trong bao nhiêu phần trăm dữ
liệu thì những điều ở vế trái và vế phải cùng xảy ra")
Confidence
Confidence, độ mạnh (“nếu vế trái xảy ra thì có bao nhiêu
khả năng vế phải xảy ra")
“NẾU mua khăn
THÌ mua bia

ẹịnh nghĩa 5: Cho trJớc Min_Supp=s
0
và Min_Conf=c
0

Ta gọi luật X Y là xaỷ ra nếu thỏa:
Supp(X Y) > s
0
và Conf(X Y)>c
0
8
Ngµy T_ID C¸c ®¬n vÞ dJ liÖu
D
1
t
1
A
 
D E

t
2
A
   
F
t
3
A B

D E

t
8
A
 
D

F
t
9

B C

E

D
4
t
10

B C

E F
t
11

B C
 
F
t
12

2.1 Thuật toán Apriori
11
2.1 Thuật toán Apriori
Cách tiếp cận của thuật toán Apriori dựa trên
nhận xét sau: Nếu bất kỳ tập k-đvdl nào là
không phổ biến thì bất kỳ tập (k+1)-đvdl
chứa chúng cũng sẽ không phổ biến, và
ngược lại: Nếu bất kỳ tập k-đvdl nào là phổ
biến thì mọi tập con của nó là phổ biến.
12
Ký hiệu:
- Ta gọi số đơn vị dữ liệu trong một tập hợp là số
các phần tử của chúng và tập có k phần tử là k-
đơn vị dữ liệu
- Gọi L
k
: Tập hợp các tập phổ biến gồm các k-đvdl.
Mỗi phần tử gồm 2 trường: i) các đơn vị dữ liệu
và ii) đếm số lần xuất hiện.
- C
k
: Tập hợp các tập ứng viên k- đơn vị dữ liệu.
Mỗi phần tử gồm 2 trường: i) các đơn vị dữ liệu
và ii) đếm số lần xuất hiện.
2.1 Thuật toán Apriori
13
Thuật toán Apriori dựa trên các thủ tục sau
Procedure 1: Tạo ra các tập phổ biến
Begin
L

L
k
);
end
14
Procedure 2: Tìm ra tất cả các luật kết hợp
begin
Result = ∅
for mỗi tập xảy ra thường xuyên X∈L do
begin
for mỗi a ⊂ X sao cho a ≠∅ do
if(Mức xác nhận(X)/Mức xác nhận(a)>=Min_Conf)
then Result = Result ∪{a → (X-a)}
end
return Ressult
end
Thuật toán Apriori dựa trên các thủ tục sau
15
Trong ví dụ 1, với Min_Conf=c
0
=70% và Min_Supp
=s
0
=40%
- Ta có tập L gồm các tập đơn vị dữ liệu xảy ra
thường xuyên như sau:
L = {{A}, {B}, {C}, {D}, {E}, {F}, {AD}, {BE}, {CE},
{DE}}
Có các luật kết hợp như sau:
A→D với c=71.42% và s=41.66%


:
: (minconf)
–
Cao ⇒ ít luật nhưng tất cả “gần như đúng"
–
Thấp ⇒ nhiều luật, phần lớn rất “không chắc chắn"
Giá trị tiêu biểu
Giá trị tiêu biểu
:
:
σ
σ = 2 -10 %,
γ
γ = 70 - 90 %
Luật kết hợp: Cơ sở
Luật kết hợp: Cơ sở
17
Giao t
Giao t
ác
ác
:
:
–
Dạng quan hệ Dạng kết
<Tid,item> <Tid,itemset>
<1, item1> <1, {item1,item2}>
<1, item2> <2, {item3}>
<2, item3>

Tập phổ biến support
{A} 3 or 75%
{B} và {C}
2 or 50%
{D}, {E} và {F}
1 or 25%
{A,C} 2 or 50%
Các cặp khác max 25%
•
If min. support 50% and min. confidence 50%, then
A
A
⇒
⇒
C
C [50%, 66.6%],
C
C
⇒
⇒
A
A [50%, 100%]
19
Nguyên tắc Apriori:
Nguyên tắc Apriori:
Những tập con của tập phổ biến cũng phải phổ biến
L
L
3
3

4
={
={
abcd
abcd
}
}
Tạo ứng viên Apriori
Tạo ứng viên Apriori
20
ID giao tác Phần tử
100 1 3 4
200 2 3 5
300 1 2 3 5
400 2 5
Database D
Database D
Duyệt D
Duyệt D
Ví dụ về Apriori (1/6)
Ví dụ về Apriori (1/6)
Tập
Độ ủng hộ
{1} 2
{2} 3
{3} 3
{4} 1
{5} 3
C
C

{2 5} 3
{3 5} 2
C
C
2
2
Tập Độ ủng hộ
{1 3} 2
{2 3} 2
{2 5} 3
{3 5} 2
L
L
2
2
Duyệt D
Duyệt D
22
Duyệt D
Duyệt D
Ví dụ về Apriori (3/6)
Ví dụ về Apriori (3/6)
Tập
{2 3 5}
C
C
3
3
Tập
Độ ủng hộ

Không gian
Không gian
tìm kiếm của
tìm kiếm của
CSDL D
CSDL D
Ví dụ về Apriori (4/6)
Ví dụ về Apriori (4/6)
24
1
1
2
2
3
3
4
4
5
5
12 13
12 13
14
14
15 23
15 23
24
24
25
25
34

1245
1345
13452345
2345
12345
12345
Áp dụng
Áp dụng
Heuristic Apriori
Heuristic Apriori
trên Cấp 1
trên Cấp 1
Ví dụ về Apriori (5/6)
Ví dụ về Apriori (5/6)
25
1
1
2
2
3
3
4
4
5
5
12
12

1245
1245
1345 2345
1345 2345
12345
12345
Áp dụng Heuristic
Áp dụng Heuristic
Apriori
Apriori
trên Cấp 2
trên Cấp 2
Ví dụ về Apriori (6/6)
Ví dụ về Apriori (6/6)