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

GV : NGUYỄN HOÀNG TÚ ANH

1

BBBBÀÀÀÀI 4I 4I 4I 4 KHAI THÁC CHUỖI TUẦN TỰ

2

1

NỘI DUNG

1. Giới thiệu 2. Khái niệm cơ bản 3. Thuật toán GSP khai thác

chuỗi tuần tự

3

GIỚI THIỆU

(cid:1) Thứ tự (theo thời gian): quan trọng

(cid:1) Ứng dụng của khai thác mẫu tuần tự

CSDL chuỗi thời gian (time-series DB) , CSDL chuỗi (sequence DB) Tập (mẫu) phổ biến → Mẫu tuần tự phổ biến (sequental pattern)

Mua máy tính, sau đó mua CD-ROM, sau đó mua máy camera kỹ thuật số trong vòng 3 tháng

Chuỗi mặt hàng :

4

2

Chăm sóc bệnh nhân, tại họa tự nhiên (động đất), qui trình kỹ thuật, thị trường và tiếp thị,… Cuộc gọi điện thoại, Weblog Chuỗi DNA và cấu trúc gen

VÍ DỤ DỮ LIỆU CHUỖI

Sách, sổ tay, CD, …

Khách hàng

Quá trình mua hàng của khách hàng

Tập các mặt hàng được khách hàng mua vào thời điểm t

Dữ liệu Web

Hoạt động duyệt web của người sử dụng

Tập các file đã xem ( sau khi nhắp chuột )

Trang chủ, trang index , thông tin liên lạc, …

Chuỗi gen

Chuỗi DNA

Phần tử của chuỗi DNA

Tổ hợp của A,T,G,C

Phần tử

(Giao dịch)

E2

E2

E1 E2

E1 E3

E3 E4

Sự kiện (Hạng mục)

5

Chuỗi

NỘI DUNG

Chuỗi CSDL chuỗi Phần tử (giao dịch) Sự kiện (hạng mục)

1. Giới thiệu 2. Khái niệm cơ bản 3. Thuật toán GSP khai thác

chuỗi tuần tự

6

3

KHÁI NIỆM CƠ BẢN

1. CHUỖI (Sequence)

là danh sách các phần tử ( giao dịch) có

Chuỗi thứ tự.

Mỗi phần tử của chuỗi : tập các sự kiện (hạng mục) Các sự kiện trong một phần tử không có thứ tự (thường viết theo bảng chữ cái)

Ký hiệu :

Chuỗi s = < s1 s2 … sn > với sj là tập các sự kiện. sj - gọi là phần tử của chuỗi s và có dạng (x1x2 … xm ) với xj là một sự kiện (hạng mục)

VD : < C (M,P) (S,T) > là một chuỗi có chiều dài =5 và có 3 phần tử

7

KHÁI NIỆM CƠ BẢN

(cid:2) CHUỖI (tt)

(cid:1)

Chuỗi si = < a1 a2 … an > là chuỗi con của chuỗi sj = < b1 b2 … bm > nếu :

(cid:1)

(cid:1)

n ≤≤≤≤ m ∃∃∃∃ các số nguyên i1 < i2 <…

Chuỗi dữ liệu Chuỗi con Thuộc ?

< {2,4} {3,5,6} {8} > < {2} {3,5} > Có

< {1,2} {3,4} > < {1} {2} > Không

8

4

< {2,4} {2,4} {2,5} > < {2} {4} > Có

KHÁI NIỆM CƠ BẢN

Mã hàng

2. CSDL CHUỖI

Mã KH

Ngày mua

Cho CSDL D Ví dụ :

100 100 100 100 100

10 15 20 25 30

a a, b, c a, c d c, f

SID Sequence

200 200 200 200

15 20 25 30

100

a, d c b, c a, e

300

20

200 <(a,d)c(b,c)(a,e)>

300 <(e,f)(a,b)(d,f)c,b>

e, f …

400

10

9

400

e, g …

KHÁI NIỆM CƠ BẢN

2. CSDL CHUỖI (tt)

Cho CSDL chuỗi D ={ d1, d2, …, dn} Đ(cid:2) ph(cid:3) bi(cid:4)n c(cid:5)a chu(cid:6)i s trên CSDL D là t(cid:7) l(cid:8) gi(cid:9)a s(cid:10) chu(cid:6)i ch(cid:11)a s trên t(cid:3)ng s(cid:10) chu(cid:6)i trong D

Supp(s)= |{di ∈ ∈ ∈ ∈D | s là chu(cid:6)i con c(cid:5)a di }| / |D|

Ví dụ :

SID Sequence

100

200 <(a,d)c(b,c)(a,e)>

300 <(e,f)(a,b)(d,f)cb>

10

400

s = <(a,b) c> Supp(s) = 2/4 = 50% s1 = s2 = s3 = Supp(s1) =? Supp(s2) =? Supp(s3) =?

5

KHÁI NIỆM CƠ BẢN

3. BÀI TOÁN KHAI THÁC CHUỖI TUẦN TỰ

Cho CSDL chuỗi và ngưỡng minsupp, cần tìm toàn bộ các chuỗi con phổ biến thỏa mãn minsupp đã cho. Ví dụ : CSDL chuỗi D và minsupp = 50% = 2/4

SID Sequence

100

200 <(a,d)c(b,c)(a,e)>

300 <(e,f)(a,b)(d,f)cb>

• Chuỗi con s = <(a,b) c> là chuỗi tuần tự phổ biến • Các chuỗi s1 = , s2 = , s3 = có phải là chuỗi phổ biến ?

11

400

KHÁI NIỆM CƠ BẢN

4. THÁCH THỨC

Tồn tại một số lượng lớn chuỗi tuần tự phổ biến bị dấu trong CSDL Thuật toán khai thác cần

Tìm toàn bộ các mẫu thỏa mãn ngưỡng minsupp Hiệu quả, co dãn, số lần duyệt CSDL nhỏ Có thể kết hợp với nhiều loại ràng buộc của người dùng.

12

6

KHÁI NIỆM CƠ BẢN

5. NGHIÊN CỨU

triển mẫu

:

Định nghĩa khái niệm và thuật toán giống thuật toán Apriori ( Apriori-All) - 1995. GSP – Phương pháp khai thác dựa trên tính chất Apriori - 1996 Phương pháp phát PrefixSpan - 2001

13

KHÁI NIỆM CƠ BẢN

6. Tính chất cơ bản của chuỗi tuần tự

Tính ch(cid:12)t Apriori :

Nếu S là chuỗi không phổ biến thì không có chuỗi bao (super-sequence) nào của S là phổ biến

Ví dụ : Trong CSDL dưới, nếu là chuỗi không phổ biến →→→→, và <(a,h)b> cũng không phổ biến

minsupp = 2

14

Seq. ID 10 20 30 40 50

Sequence <(b,d)cb(a,c)> <(b,f)(c,e)b(f,g)> <(a,h)(b,f)abf> <(b,e)(c,e)d>

7

NỘI DUNG

1. Giới thiệu 2. Khái niệm cơ bản 3. Thuật toán GSP khai thác

chuỗi tuần tự

15

THUẬT TOÁN GSP

1. BẢN CHẤT

GSP : Generalized Sequential Pattern- Agrawal & Srikant, EDBT’96 Duyệt CSDL để tìm các chuỗi phổ biến có độ dài 1.

For mỗi cấp ( chuỗi có độ dài k)

Tạo các chuỗi ứng viên có độ dài (k+1) từ các chuỗi phổ biến chiều dài k (sử dụng Apriori) Duyệt CSDL để đếm độ phổ biến của từng chuỗi ứng viên và loại các ứng viên không thỏa mãn ngưỡng minsupp

Lặp lại đến khi không còn chuỗi phổ biến hoặc không còn ứng viên S(cid:13) d(cid:14)ng tính ch(cid:12)t Apriori đ(cid:16) c(cid:17)t b(cid:18)t (cid:11)ng viên

16

8

VÍ DỤ THUẬT TOÁN GSP

Cand Sup

C1

(cid:1) Các (cid:11)ng viên đ(cid:19)u tiên C1 :

3

5

, , , , , , , (cid:1) Duyệt CSDL để tính độ phổ biến của từng

4

3

ứng viên và tìm F1 -> F1 = , , , , ,

3

2

1

minsupp=2

1

17

Seq. ID 10 20 30 40 50 Sequence <(b,d)cb(a,c)> <(b,f)(c,e)b(f,g)> <(a,h)(b,f)abf> <(b,e)(c,e)d>

VÍ DỤ THUẬT TOÁN GSP (cid:1) T(cid:20)o các (cid:11)ng viên C2 : = phép kết

(cid:1) Các chuỗi chiều dài = 2 và có 2 phần tử

18

9

VÍ DỤ THUẬT TOÁN GSP (cid:1) T(cid:20)o các (cid:11)ng viên C2 (tt)

(cid:1) Các chuỗi chiều dài = 2 và có 1 phần tử (cid:1) Tổng cộng có 51 chuỗi ứng viên chiều dài =2

<(a,b)>

<(a,c)>

<(a,d)>

<(a,e)>

<(a,f)>

<(b,c)>

<(b,d)>

<(b,e)>

<(b,f)>

<(c,d)>

<(c,e)>

<(c,f)>

<(d,e)>

<(d,f)>

<(e,f)>

19

VÍ DỤ THUẬT TOÁN GSP

(cid:1) Xác đ(cid:21)nh t(cid:22)p chu(cid:6)i ph(cid:3) bi(cid:4)n F2

(cid:1) Duyệt CSDL và xác định độ phổ biến của từng chuỗi ứng viên chiều dài = 2 (cid:1) Có 19 ứng viên có độ phổ biến

≥ minsupp (=2)

(cid:1) > Tập chuỗi phổ biến F2 gồm có

19 chuỗi

20

10

VÍ DỤ THUẬT TOÁN GSP

Supp=2 2 1 1 1 1

21

VÍ DỤ THUẬT TOÁN GSP

<(a,b)> Supp=0

<(a,c)> 1

<(a,d)> 1

<(a,e)> 1

<(a,f)> 0

<(b,c)> 0

<(b,d)> 2

<(b,e)> 1

<(b,f)> 2

<(c,d)>

<(c,e)>

<(c,f)>

<(d,e)>

<(d,f)>

<(e,f)>

22

11

VÍ DỤ THUẬT TOÁN GSP

(cid:1) T(cid:20)o t(cid:22)p (cid:11)ng viên C3

(cid:1) Dùng phép kết : F2 với F2

(cid:1) Ví d(cid:14) : , và : chuỗi phổ biến chiều dài = 2 (cid:3) , , , , - ứng viên chiều dài = 3

(cid:1) <(b,d)>, và chuỗi phổ biến chiều dài=2 (cid:3) <(b,d)b>, , , , - ứng viên chiều dài = 3

23

(cid:1) Phép loại bỏ : dựa trên tính chất Apriori (cid:1) Có 46 ứng viên chiều dài = 3

VÍ DỤ THUẬT TOÁN GSP

(cid:1) Tìm t(cid:22)p chu(cid:6)i ph(cid:3) bi(cid:4)n F3

(cid:1) Duyệt CSDL và xác định độ phổ biến của từng chuỗi ứng viên chiều dài = 3 (cid:1) Có 19 ứng viên có độ phổ biến

≥ minsupp

(cid:1) > Tập chuỗi phổ biến F3 gồm 19

chuỗi

24

12

VÍ DỤ THUẬT TOÁN GSP

Supp(Cand.)<<<< minsupp

<(b,d)cba>

5th scan: 1 cand. 1 length-5 seq. pat.

<(b,d)bc> …

Cand. ∉∉∉∉ CSDL

4th scan: 8 cand. 6 length-4 seq. pat.

…

… … <(ab)> … <(ef)>

3rd scan: 46 cand. 19 length-3 seq. pat. 20 cand. not in DB at all

2nd scan: 51 cand. 19 length-2 seq. pat. 10 cand. not in DB at all

1st scan: 8 cand. 6 length-1 seq. pat.

minsupp =2

25

Seq. ID 10 20 30 40 50

Sequence <(b,d)cb(a,c)> <(b,f)(c,e)b(f,g)> <(a,h)(b,f)abf> <(b,e)(c,e)d>

THUẬT TOÁN GSP

2. Pseudo-Code

Input : CSDL chuỗi D, minsupp Output : F - các chuỗi tuần tự phổ biến trong D

Ck+1 = apriori_gen(Lk); // Tạo tập chuỗi ứng viên chiều dài

(k+1)

Ck : Tập chuỗi ứng viên chiều dài k Fk : Tập chuỗi phổ biến chiều dài k F1 = Tìm_chuỗi_phổ_biến_chiều dài 1(D); // có dạng for (k = 1; Fk ≠∅; k++) {

if Ck+1 ≠∅ then

{ Duyệt CSDL để tính Fk+1 = { s ∈Ck+1 | supp(s)≥ minsupp }

}

26

13

} return F = ∪k Fk;

THUẬT TOÁN GSP

3. Tạo tập chuỗi ứng viên chiều dài (k+1)

Hàm apriori_gen nhận Fk và trả về tập chuỗi ứng viên chiều dài (k+1). G(cid:23)m 2 bư(cid:18)c : k(cid:4)t và c(cid:17)t b(cid:25) Bư(cid:18)c k(cid:4)t :

Chu(cid:6)i s1 k(cid:4)t v(cid:18)i chu(cid:6)i s2 n(cid:4)u

Chu(cid:6)i s1 sau khi b(cid:25) b(cid:18)t đi 1 h(cid:20)ng m(cid:14)c đ(cid:19)u tiên thì gi(cid:10)ng như Chu(cid:6)i s2 b(cid:25) b(cid:18)t 1 h(cid:20)ng m(cid:14)c cu(cid:10)i cùng K(cid:4)t qu(cid:26) phép k(cid:4)t = chuỗi s1 mở rộng thêm 1 hạng mục cuối cùng của chuỗi s2 . H(cid:20)ng m(cid:14)c thêm này có th(cid:16) t(cid:20)o thành m(cid:2)t ph(cid:19)n t(cid:13) m(cid:18)i trong s1 n(cid:4)u nó là ph(cid:19)n t(cid:13) riêng bi(cid:8)t thu(cid:2)c s2, ngư(cid:27)c l(cid:20)i là m(cid:2)t thành viên c(cid:5)a ph(cid:19)n t(cid:13) cu(cid:10)i cùng c(cid:5)a s1

27

Bư(cid:18)c c(cid:17)t b(cid:25) : lo(cid:20)i các chu(cid:6)i (cid:11)ng viên có ch(cid:11)a các chu(cid:6)i con không ph(cid:3) bi(cid:4)n

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

(cid:1) Giả sử F3 = {<(1,2) 3>, <(1,2) 4>, <1(3,4)>,

<(1,3) 5>, <2 (3,4)>, <2 3 5>}

(cid:1) Sau bước kết :

(cid:1)

(cid:1)

C4 = {<(1,2) (3,4)>, <(1,2) 3 5>} <(1,2) 4> không kết được với chuỗi nào khác vì không tồn tại chuỗi có dạng <2 (4,x) > hoặc <2 4 x>

(cid:1)

(cid:1) Sau bước loại bớt : C4 = {<(1,2) (3,4)>} vì <1 3 5> ∉ F3 nên <(1,2) 3 5> bị loại

28

14

BÀI TẬP XD TẬP CHUỖI ỨNG VIÊN

• Thời gian : 7’

F3

• Giả sử F3 là tập gồm 7 chuỗi

• Xác định tập ứng viên C4

• Trình bày kết quả trước lớp

< {1} {2} {3} > < {1} {2 5} > < {1} {5} {3} > < {2} {3} {4} > < {2 5} {3} > < {3} {4} {5} > < {5} {3 4} >

29

ĐÁP ÁN BÀI TẬP XD TẬP CHUỖI ỨNG VIÊN

F3

< {1} {2} {3} > < {1} {2 5} > < {1} {5} {3} > < {2} {3} {4} > < {2 5} {3} > < {3} {4} {5} > < {5} {3 4} >

30

15

HẠN CHẾ CỦA GSP

(cid:1) Số lượng khổng lồ tập chuỗi ứng viên (đặc

biệt chuỗi có chiều dài = 2)

(cid:1) Duyệt CSDL nhiều lần (cid:1) Không hi(cid:8)u qu(cid:26) khi khai thác các chu(cid:6)i dài

-> M(cid:2)t trong các cách gi(cid:26)i quy(cid:4)t : PrefixSpan

(t(cid:28) đ(cid:30)c trong tài li(cid:8)u tham kh(cid:26)o)

31

BÀI TẬP TẠI LỚP

(cid:1) Thời gian : 10’ (cid:1) Cho CSDL chuỗi và minsupp = 4 (cid:1) Tìm các t(cid:22)p (cid:11)ng viên và t(cid:22)p chu(cid:6)i ph(cid:3) bi(cid:4)n

Seq. ID Sequence

10 <(b,d)cb(a,c)>

20 <(b,f)(c,e)b(f,g)>

30 <(a,h)(b,f)abf>

40 <(b,e)(c,e)d>

32

16

50

ĐÁP ÁN BÀI TẬP TẠI LỚP

33

BÀI TẬP

Mã hàng

Ngày mua

Mã KH

10 10 10 10

a, d a, b, c a, b,f a,c,d,f

10 15 20 25

20 20

a, b,f e

15 20

30

a,b, f

10

1. Cho CSDL chuỗi D và minsupp = 50%. Xác định tập chuỗi phổ biến trên D . 2. Có thể áp dụng ý thuật tưởng toán FP-Growth vào bài toán tìm chuỗi phổ biến không và như thế nào ?

40 40 40

d,g,h b,f a,g,h

10 20 25 34

17

TÀI LIỆU THAM KHẢO

2.

for : Principles and

3.

4.

35

1. R. Srikant, R. Agrawal . Mining sequential patterns : Generalizations and perfomance improvements. EDBT’96. J. Han J. Pei. Pattern Growth Methods Sequential Pattern Mining Extensions, ACM SIGKDD 2001, USA. http://illimine.cs.uiuc.edu/demo/ : Demo một số thuật toán tìm tập phổ biến và chuỗi phổ biến http://www- users.cs.umn.edu/~kumar/dmbook/resources.htm : Chương trình một số thuật toán và phần mềm cơ bản của các bài toán trong khai thác dữ liệu

Q & A

36

18