DATA MINING AND APPLICATION: KHAI THÁC TẬP PHỔ BIẾN & LUẬT KẾT HỢP

KHAI THÁC DỮ LIỆU & ỨNG DỤNG (DATA MINING)

GV : NGUYỄN HOÀNG TÚ ANH

BÀI 3- PHẦN 1 KHAI THÁC TẬP PHỔ BIẾN & LUẬT KẾT HỢP

NỘI DUNG

1. Giới thiệu 2. Các khái niệm cơ bản 3. Bài toán khai thác tập phổ biến

GIỚI THIỆU

biến và luật kết hợp

 Mẫu phổ biến : là mẫu (tập các hạng mục, chuỗi con, cấu trúc con, đồ thị con, …) xuất hiện thường xuyên trong tập DL – Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ

 Mục đích : Tìm các hiện tượng thường xuyên xảy ra

trong DL – Những sản phẩm nào thường được mua chung ? Bia và tã lót – Người ta thường mua gi tiếp theo sau khi mua máy PC ? – Dạng DNA nào có phản ứng với công thức thuốc mới ? – Làm thế nào đề phân loại tự động văn bản Web ?

– Áp dụng trong phân tích CSDL bán hàng – Mở rộng sang quảng cáo, thiết kế catalog, phân tích chiến

dịch bán hàng, Web log, chuỗi DNA, …

 Ứng dụng :

GIỚI THIỆU

 Là nền tảng cho nhiều nhiệm vụ KTDL khác :

 Bài toán khai thác tập phổ biến là bài toán rất quan trọng lĩnh vực KTDL : vạch ra tính chất ẩn, quan trọng của tập DL

– Phân tích luật kết hợp, mối tương quan – Mẫu tuần tự, cấu trúc ( Vd : đồ thị con) – Phân tích DL không gian, đa phương tiện, phụ thuộc thời gian

– Phân loại : phân loại dựa trên luật kết hợp – Phân tích nhóm: gom nhóm dựa trên mẫu phổ biến – ….

NỘI DUNG

1. Giới thiệu 2. Các khái niệm cơ bản 3. Bài toán khai thác tập phổ biến

KHÁI NIỆM CƠ BẢN

1. CSDL GIAO DỊCH (Transaction DB)

VD giỏ mua hàng: {Bánh mì, o Giỏ 1:

Trứng, Sữa}

o Giỏ 2: Đường}

{Bánh mì,

… o Giỏ n: {Bánh qui, ngũ cốc, sữa}

KHÁI NIỆM CƠ BẢN

Biến đổi CSDL về dạng nhị phân

ITEMS:

A = milk B= bread C= cereal D= sugar E= eggs

KHÁI NIỆM CƠ BẢN

1. CSDL GIAO DỊCH (tt)

o Giao dịch (Transation) : tập các hạng mục được mua trong một giỏ ( có TID – mã giao dịch) : (Tid, tập hạng mục)

o Giao dịch t : tập các hạng mục sao cho t I

o VD : t = { bánh mì, sữa chua, ngũ cốc}

o CSDL giao dịch : tập các giao dịch o CSDL D = {t1,t2, …, tn} , ti={ii1,ii2, …, iik} với iij  I : CSDL 9

giao dịch

Định nghĩa : o Hạng mục (Item) : mặt hàng trong giỏ hay một thuộc tính o Tập các hạng mục (itemset) I = {i1, i2, …, im} : VD : I = {sữa, bánh mì, ngũ cốc, sữa chua} Tập k hạng mục (k-itemset)

KHÁI NIỆM CƠ BẢN

2. ĐỘ PHỔ BIẾN VÀ TẬP PHỔ BIẾN

Giao dịch t chứa X nếu X là tập các hạng mục trong I và X  t

VD : X = { bánh mì, sữa chua}

Độ phổ biến (supp) của tập các hạng mục X trong CSDL D là tỷ lệ giữa số các giao dịch chứa X trên tổng số các giao dịch trong D

Supp(X) = count(X) / | D |

Tập các hạng mục phổ biến S hay tập phổ biến (frequent itemsets) là tập các hạng mục có độ phổ thiểu minsupp (do biến thỏa mãn độ phổ biến tối người dùng xác định)

Nếu supp(S)  minsupp thì S - tập phổ biến .

KHÁI NIỆM CƠ BẢN

3. TÍNH CHẤT TẬP PHỔ BIẾN

Tất cả các tập con của tập phổ biến đều là tập phổ biến Thảo luận :

Tại sao ? Chứng minh. Nếu tập con không phổ biến thì tập bao nó (tập cha) có phổ biến hay không ?

VÍ DỤ 1

Minsupp = 60%

I = { Beer, Bread, Jelly, Milk, PeanutButter} X= {Bread,PeanutButter} ; Count(X) = 3 và |D| = 5  supp(X) = 60% X- tập phổ biến X2 = {Bread}  supp(X2) = ? X3 = {PeanutButter}  supp(X3) = ?; X2 và X3 có phổ biến ?

X4 = {Milk}, X5={Milk, Bread}  X4 và X5 có phổ biến ?

TẬP PHỔ BIẾN của VD 1

minsupp=30%

KHÁI NIỆM CƠ BẢN

4. TẬP PHỔ BIẾN TỐI ĐẠI (Max-Pattern)

Tập phổ biến & không tồn tại tập nào bao nó là phổ biến (Bayardo – SIGMOD’98)

Tid Items 10 A,B,C,D,E 20 B,C,D,E, 30 A,C,D,F

Minsupp=2

{B, C, D, E}, {A, C, D} - tập phổ biến tối đại {B, C, D} - không phải tập phổ biến tối đại

KHÁI NIỆM CƠ BẢN

5. TẬP PHỔ BIẾN ĐÓNG (Closed

Pattern)

TID Items

10 a, b, c

20 a, b, c

30 a, b, d

40 a, b, d,

Minsupp=2

50 c, e, f

Tập phổ biến & không tồn tại tập nào bao nó có cùng độ phổ biến như nó. (Pasquier, ICDT’99) Tập phổ biến ĐÓNG là trường hợp nén các tập phổ biến (có mất thông tin) Ví dụ : {A, B}, {A, B, D}, {A,B, C} - tập phổ biến đóng. {A, B} - không phải tập phổ biến tối đại Mối quan hệ giữa tập phổ biến đóng và tập phổ biến tối đại ntn?

KHÁI NIỆM CƠ BẢN

6. LUẬT KẾT HỢP( Association rule)

LKH có dạng :

X  Y, với X, Y  I, và X Y ={} Ý nghĩa : khi X có mặt thì Y cũng có mặt ( với xác suất nào đó)

LKH thường được đánh giá dựa trên 2 độ đo: Độ phổ biến (support) : supp (X  Y ) =P (X  Y)

supp (X  Y ) = supp(XY)

Độ tin cậy (confidence) : conf (X  Y ) = P(Y | X)

conf (X  Y ) = supp(XY) / supp(X)

VÍ DỤ LUẬT KẾT HỢP (VD1)

Ký hiệu : s – supp, α - conf

KHÁI NIỆM CƠ BẢN

7. MÔ TẢ BÀI TOÁN KHAI THÁC LKH

Cho độ phổ biến tối thiểu (minsupp) và độ tin cậy tối thiểu (minconf) do người dùng xác định. Cho tập các hạng mục I={i1,i2,…,im} và CSDL giao dịch D={t1,t2, …, tn}, với ti={ii1,ii2, …, iik} và iij  I. Bài toán khai thác LKH là bài toán tìm tất cả các luật dạng X  Y (X, Y  I và X Y = {}) thỏa mãn độ phổ biến và độ tin cậy tối thiểu

supp (X  Y )  minsupp conf (X  Y )  minconf

Minsupp = 50% Minconf = 100%

Bài tập theo nhóm  Thời gian : 8’  Trình bày

ý

Trs-id Items bought

10 E, B, C, D

tưởng (không yêu cầu giải BT) giải quyết vần đề trước lớp trong vòng 3’

 Tình huống :

20 A, B, C, D

30 D, B, F

40 A, E, C – Cho CSDL bên với các giá trị minsupp =50 % và minconf = 100%

– Cần tìm tất cả các luật thỏa mãn hợp kết minsupp và minconf.

– Nhận xét ?

KHÁI NIỆM CƠ BẢN

8. QUI TRÌNH KHAI THÁC LKH

Bước 1 : Tìm tất cả các tập phổ biến ( theo ngưỡng minsupp) Bước 2 : Xây dựng luật từ các tập phổ biến

 conf (A  (S - A)) = supp(S) / supp(A)  minconf

Đối với mỗi tập phổ biến S, tạo ra tất cả các tập con khác rỗng của S Đối với mỗi tập con khác rỗng A của S, o Luật A  (S - A) là LKH cần tìm nếu :

 Từ bài toán khai thác LKH chuyển thành bài toán khai thác tập phổ biến : độ phức tạp tính toán cao.

VÍ DỤ

Transaction-id

Items bought

A, B, C

A, C

Minsupp = 50% Minconf = 80%

Frequent Itemsets

Support

A, D

{A}

75%

B, E, F

{B}

50%

{C}

50%

{A, C}

50%

Luật A  C :

Luật C  A :

supp (A  C) = supp({A}{C}) = 50% conf (A  C) = supp({A}{C})/supp({A}) = 66.6% (loại)

supp (C  A) = supp({C}{A}) = 50% conf (C  A) = supp({C}{A})/supp({C}) = 100% (chọn)

NỘI DUNG

1. Giới thiệu 2. Các khái niệm cơ bản 3. Bài toán khai thác tập phổ

biến  Thuật toán Apriori

GIỚI THIỆU Bài toán khai thác tập phổ biến là bài toán rất quan trọng lĩnh vực KTDL Bài toán khai thác tập phổ biến là bài toán tìm tất cả các tập các hạng mục S (hay tập phổ biến S) có độ phổ biến thỏa mãn độ phổ biến tối thiểu minsupp

supp(S) minsupp

Cách giải quyết : dựa trên tính chất của tập phổ biến Tìm kiếm theo chiều rộng : Thuật toán Apriori (1994) Phát triển mẫu : Thuật toán FP-Growth (2000) Tìm kiếm trên CSDL dạng dọc : Thuật toán Charm 23 (2002)

TÌM KIẾM THEO CHIỀU RỘNG

1. BẢN CHẤT

Nguyên tắc loại bỏ Apriori : Nếu không phải là tập phổ biến thì tập bao nó cũng không phổ biến Phương pháp :

Tìm tất cả các tập phổ biến 1- hạng mục. Tạo các tập ứng viên kích thước k-hạng mục (k - candidate itemset) từ các tập phổ biến có kích thước (k-1)-hạng mục Kiểm tra độ phổ biến của các ứng viên trên CSDL và loại các ứng viên không phổ biến Dừng khi không tạo được tập phổ biến hay tập ứng viên 24

VÍ DỤ TT APRIORI minsupp= 50%

C1 L1

1st scan

Itemset {A} {B} {C} {E}

sup 2 3 3 3

Itemset {A} {B} {C} {D} {E}

sup 2 3 3 1 3

CSDL D Items A, C, D B, C, E A, B, C, E B, E

Tid 10 20 30 40

C2 C2 2nd scan L2

Itemset {A, C} {B, C} {B, E} {C, E}

sup 2 2 3 2

Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}

sup 1 2 1 2 3 2

Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}

C3

3rd scan

Itemset {B, C, E}

sup 2

THUẬT TOÁN APRIORI

2. Pseudo-Code

Input : CSDL D, minsupp Output : L : các tập phổ biến trong D Ck : Tập ứng viên kích thước k Lk : Tập phổ biến kích thước k L1 = Tìm_tập_phổ_biến_1_hạng mục(D); for (k = 1; Lk ; k++) {

Ck+1 = apriori_gen(Lk); // Tạo tập ứng viên (k+1) hạng mục for mỗi giao tác t  D { // Duyệt CSDL để tính support

Ct = subset(Ck+1, t); // Lấy ra tập con của t là ứng viên for mỗi ứng viên c  Ct

c.count ++

} Lk+1 = { c  Ck+1 | c.count  minsupp }

} return L = k Lk;

THUẬT TOÁN APRIORI

3. Tạo tập ứng viên (k+1)- hạng mục Hàm apriori_gen nhận Lk và trả về tập ứng viên kích thước (k+1). Gồm 2 bước : kết và loại bỏ Giả sử các hạng mục trong Lk sắp xếp theo thứ tự

Procedure apriori_gen (Lk : Tập phổ biến kích thước k) for mỗi itemset l1 Lk for mỗi itemset l2 Lk

if (l1 [1] = l2 [1])  (l1 [2] = l2 [2])  … (l1 [k-1] = l2 [k-1]) 

(l1 [k] < l2 [k]) then

// Bước 1 :kết Lk với chính nó

{ c = l1  l2 ;

if has_infrequent_subset (c, Lk ) then

// B2 : Loại bỏ các ứng viên không có lợi

Xóa c ; else Thêm c vào Ck+1 ;

}

return Ck+1 ;

THUẬT TOÁN APRIORI

Tạo tập ứng viên (k+1)- hạng mục (tt)

Bước 2 : loại bỏ để giảm Ck+1

Procedure has_infrequent_subset (c: Tập ứng viên kích thước k+1, Lk : Tập phổ biến kích thước k) for mỗi k-subset s  c

if s Lk then

return True ;

return False ;

VÍ DỤ TẠO TẬP ỨNG VIÊN

 Giả sử L3 = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}}

 Sau bước kết :

– C4 = {{1, 2, 3, 4}, {1, 3, 4, 5}}

 Sau bước loại bỏ, còn : – C4 = {{1, 2, 3, 4}}

vì {1, 4, 5}  L3 nên {1, 3, 4, 5} bị loại

CÁC THÁCH THỨC CỦA TT APRIORI

Thách thức :

Phải duyệt CSDL nhiều lần Số lượng tập ứng viên rất lớn Thực hiện việc tính độ phổ biến nhiều, đơn điệu

Cải tiến Apriori : ý tưởng chung

Giảm số lần duyệt CSDL Giảm số lượng tập ứng viên Qui trình tính độ phổ biến thuận tiện hơn

CÁC KỸ THUẬT CẢI TIẾN THUẬT TOÁN APRIORI Tự tìm hiểu trong tài liệu tham khảo Chia để trị : A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. VLDB’95

Chia CSDL thành các phân hoạch D1,D2,…,Dp Tìm tập phố biến cục bộ trong từng phân hoạch và tổ hợp

Hàm băm (Hashing) : J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining association rules. SIGMOD’95

Băm các tập ứng viên k-hạng mục vào các giỏ Tập ứng viên k-hạng mục tương ứng giỏ có độ phổ biến

Lấy mẫu : H. Toivonen. Sampling large databases for association rules. VLDB’96 CSDL lớn Chọn mẫu từ CSDL và tìm tập phổ biến trên mẫu, kiểm tra bao đóng của các hạng mục phổ biến

Giảm số lượng giao dịch : R. Agrawal and R. Srikant. Fast algorithms for mining association rules. VLDB'94

Loại bỏ các giao dịch không chứa bất kỳ tập phổ biến nào

THUẬT TOÁN APRIORI -TID

BẢN CHẤT

toán Apriori, sử dùng hàm

Tương tự như thuật apriori_gen để tạo ứng viên. Cải tiến theo hướng giảm số lượng giao dịch TT Apriori_Tid không tính độ phổ biến của các tập hạng mục từ các mẫu tin của CSDL mà xây dựng cấu trúc lưu trữ mới Ck cho CSDL ban đầu .

Mỗi mẫu tin trong Ck có dạng với Xk là tập phổ biến k- hạng mục xuất hiện trong giao dịch có mã Tid. Nếu một giao dịch không chứa bất kỳ một tập phổ biến k hạng mục thì giao dịch này không được đưa vào Ck .

BÀI TẬP (cá nhân)

Items  Thời gian : 25’  Chỉ

M2, M4 M2, M3 trình bày kết quả câu 1 (không cần ghi chi tiết các bước của câu 1) và chi tiết câu 2, câu 3 vào giấy nộp cho GV. Cho CSDL giao dịch bên

M1, M3 M2, M3 M1, M3

1. Sử dụng thuật toán Apriori để tìm các tập phổ biến với minsupp = 22 % Liệt kê các tập phổ biến tối đại và tập phổ biến đóng. Tìm tất cả các luật kết hợp thỏa mãn

Tid 100 M1, M2, M5 200 300 400 M1, M2, M4 500 600 700 800 M1, M2, M3, M5

a. Minconf = 50 % b. Minconf = 70%

900 M1, M2, M3

Qui định trình bày bài nộp

Bài tập nộp cá nhân  Ngày nộp :

 Tên nhóm : – Họ và tên: – Mã số SV :  Nội dung :

Lưu ý : Nộp chung bài

làm của các

thành viên trong cùng một nhóm.

CÁC CÔNG VIỆC CẦN LÀM 1. Thực hiện bài tập nhóm chương 3.

– Nộp bài qua Moodle trước 23h00 ngày

chủ nhật – 18/10/2009

luật kết hợp – P2

– Xem nội dung bài 3 – Phần 2. – Chuẩn bị BT nhóm Bài 3 – Phần 2 – Cách thực hiện :

• Đọc slide, xem các ví dụ • Tham khảo trên Internet và tài liệu tham

2. Chuẩn bị bài 3 : Khai thác tập phổ biến và

khảo

BÀI TẬP PHẦN 1

trình khai

1. Hãy tìm hiểu trong tài liệu tham khảo [2], [3] và trình bày chi tiết một phương pháp cải tiến quá trình tìm luật kết hợp từ tập phổ biến (Bước 2 trong qui thác luật kết hợp)? Giải thích vì sao nó hiệu quả hơn.

2. Tìm hiểu các phương pháp cải tiến thuật toán Apriori. Trình bày chi tiết MỘT cải tiến ( ý tưởng, mã giả )

3. Áp dụng một trong các phương pháp cải tiến đó vào bài tập 4.a. Nêu rõ đã cải tiến ở phần nào .

BÀI TẬP PHẦN 1 4. Cho CSDL sau và minsupp=50%, minconf=80%

Items_bought

TID 100 200 300 400

Date 15/1/03 15/1/03 19/1/03 25/1/03

K, A, D, B, C, I D, A, C, E, B C, A, B, E, D B, A, D, I, K

a) Sử dụng thuật toán Apriori để tìm tất cả các tập phổ

biến, tập phổ biến tối đại, tập phổ biến đóng. Tìm tất cả LKH thỏa mãn ngưỡng minconf đã cho b) c) Ứng dụng cải tiến của câu 1 vào việc tìm các LKH thỏa mãn ngưỡng minconf. So sánh hiệu quả về thời gian thực hiện với kết quả ở câu b). Liệt kê LKH thỏa mãn ngưỡng đã cho và có dạng (item1  item2)  item3 kèm theo supp, conf của nó. 37