Chương 2

LUẬT KẾT HỢP
(Association Rules)
Nội dung
1

Khái niệm cơ bản

2

Thuật toán Apriori

3

Tìm tập phổ biến tối đại với FP-Tree

4

Phân loại luật kết hợp

5

Tối ưu tập luật


Các khái niệm cơ bản
Bài toán phân tích giỏ hàng
 Phân tích thói quen mua
hàng của khách hàng
bằng cách tìm ra những

7/12/2014

www.lhu.edu.vn


Các khái niệm cơ bản
Luật kết hợp
 Định dạng thể hiện đặc trưng cho các luật kết
hợp:
 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:
 mua(x, “khăn")  mua(x, “bia") [0.5%, 60%]
 khoa(x, "CS") ^ học(x, "DB")  điểm(x, "A") [1%, 75%]


Các khái niệm cơ bản
Luật kết hợp
khăn
1

 bia [0.5%, 60%]
2

3

4


 Support của tập I:
số lượng giao tác có chứa I
 Min Support : ngưỡng cho support
 Tập phần tử phổ biến: có độ ủng hộ (support)  


Các khái niệm cơ bản
Ví dụ
 Cho: (1) CSDL các giao tác, (2) mỗi giao tác là một
danh sách mặt hàng được mua (trong một lượt mua
của khách hàng) Frequent item sets
ID của giao tác Hàng mua
100
A,B,C
200
A,C
400
A,D
500
B,E,F

Tập phổ biến
{A}
{B} và {C}
{D}, {E} và {F}
{A,C}
Các cặp khác

support

 Bước rút gọn:
Những tập kích thước (k-1) không phổ biến
không thể là tập con của tập phổ biến kích thước k
 Mã giả:
Ck : Tập ứng viên có kích thước k; Lk : Tập phổ biến có kích
thước k
L1 = {các phần tử phổ biến};
for (k = 1; Lk !=; k++) do begin
Ck +1 = {các ứng viên được tạo từ Lk };
for each giao tác t trong database do
tăng số đếm của tất cả các ứng viên trong Ck+1
mà được chứa trong t

Lk +1 = {các ứng viên trong Ck +1 có độ ủng hộ tối tiểu}
end
return k Lk ;


Thuật toán 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
L3={abc, abd, acd, ace, bcd}
Tự kết: L3*L3


{1}
Duyệt D {2}
{3}
{4}
{5}

L1

Độ ủng hộ

2
3
3
1
3

Tập

{1}
{2}
{3}
{5}

Độ ủng hộ

2
3
3
3

2

L2

Tập Độ ủng hộ
{1 3}
2
{2 3}
2
{2 5}
3
{3 5}
2


Thuật toán Apriori
Ví dụ
C3

Tập
{2 3 5}

L3

Duyệt D

Tập Độ ủng hộ
{2 3 5}
2



23

1

2

145

24
3

1345

234

25
4

2345

235

34

35
5

245


1245

1345

134

135

145

234

15

23

24

25

2

3

4

2345

235


13

14
1

1235

1245

1345

134

135

145

234

15

23

24

25

2

3

 Phần cốt lõi của thuật toán Apriori: FP tree
 Dùng các tập phổ biến kích thước (k – 1) để tạo các tập phổ
biến kích thước k ứng viên
 Duyệt CSDL và đối sánh mẫu để đếm số lần xuất hiện của
các tập ứng viên trong các giao tác

 Tình trạng nghẽn cổ chai của thuật toán Apriori:
việc tạo ứng viên
 Các tập ứng viên đồ sộ:
• 104 tập phổ biến kích thước 1 sẽ tạo ra 107 tập ứng viên
kích thước 2
• Để phát hiện một mẫu phổ biến kích thước 100, ví dụ
{a1, a2, …, a100}, cần tạo 2100  1030 ứng viên.
 Duyệt CSDL nhiều lần:
• Cần duyệt (n +1 ) lần, n là chiều dài của mẫu dài nhất


Thuật toán Apriori
Hạn chế của thuật toán Apriori
 Thực tế:
 Đối với tiếp cận Apriori căn bản thì số lượng thuộc tính trên
dòng thường khó hơn nhiều so với số lượng dòng giao tác.
 Ví dụ:
• 50 thuộc tính mỗi cái có 1-3 giá trị, 100.000 dòng (không quá tệ)
• 50 thuộc tính mỗi cái có 10-100 giá trị, 100.000 dòng (hơi tệ)
• 10.000 thuộc tính mỗi cái có 5-10 giá trị, 100 dòng (quá tệ...)

 Lưu ý:
• Một thuộc tính có thể có một vài giá trị khác nhau
• Các thuật toán luật kết hợp có đặc trưng là xem một cặp thuộc

 Chọn các item phổ biến trong các giao tác và sắp xếp chúng
theo thứ tự giảm dần độ phổ biến trong tập L
 Gọi hàm Insert_tree([p|P],T) để đưa các item vào trong cây T


Thuật toán FP-Tree

Xây dựng cây FP-Tree


Thuật toán FP-Tree
null

Thêm TID=1 vào cây:

TID
1
2
3
4
5
6
7
8
9
10

Items
{A,B}
{B,C,D}