Chương 4 Khai phá luật kết hợp

KHAI PHÁ DỮ LIỆU

Nội dung

1. Khai phá luật kết hợp (Association rule)

2. Các thuật toán khai phá vô hướng luật kết hợp (giá trị

lôgic đơn chiều) trong CSDL giao dịch

3. Khai phá kiểu đa dạng luật kết hợp/tương quan

4. Khai phá kết hợp dựa theo ràng buộc

5. Khai phá mẫu dãy

DW

DM

214

1. Khai phá luật kết hợp

Một số ví dụ về “luật kết hợp” (associate rule) • “98% khách hàng mà mua tạp chí thể thao thì đều mua các tạp chí về

ôtô” sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ôtô”

• “60% khách hàng mà mua bia tại siêu thị thì đều mua bỉm trẻ em” 

sự kết hợp giữa “bia” với “bỉm trẻ em”

• “Có tới 70% người truy nhập Web vào địa chỉ Url 1 thì cũng vào địa chỉ Url 2 trong một phiên truy nhập web” sự kết hợp giữa “Url 1” với “Url 2”. Khai phá dữ liệu sử dụng Web (Dữ liệu từ file log của các site, chẳng hạn được MS cung cấp).

• Các Url có gắn với nhãn “lớp” là các đặc trưng thì có luật kết hợp liên

quan giữa các lớp Url này.

DW

DM

215

Khái niệm cơ sở: Tập phổ biến và luật kết hợp

DW

[IV06] Renáta Iváncsy, István Vajk (2006). Frequent Pattern Mining in Web DM Log Data, Acta Polytechnica Hungarica, 3(1):77-90, 2006 216

Khái niệm cơ sở: Tập phổ biến và luật kết hợp

Cơ sở dữ liệu giao dịch (transaction database)

• Giao dịch: danh sách các mục (mục: item, mặt hàng) trong một phiếu mua

hàng. Giao dịch T là một tập mục.

• Tập toàn bộ các mục I = {i1, i2, …, ik} “tất cả các mặt hàng”. Một giao dịch T

là một tập con của I: T  I. Mỗi giao dịch T có một định danh là TID. • A là một tập mục A  I và T là một giao dịch: Gọi T chứa A nếu A  T.

• Luật kết hợp

• Gọi A  B là một “luật kết hợp” nếu A  I, B  I và AB=. • Luật kết hợp A  B có độ hỗ trợ (support) s trong CSDL giao dịch D nếu trong D có s% các giao dịch T chứa AB: chính là xác suất P(AB). Tập mục A có P(A)  s>0 (với s cho trước) được gọi là tập phổ biến (frequent set). Luật kết hợp A  B có độ tin cậy (confidence) c trong CSDL D nếu như trong D có c% các giao dịch T chứa A thì cũng chứa B: chính là xác suất P(B|A).

= P(AB)

: 1  s (A  B)  0 : 1  c (A  B)  0

DM

• Support (A  B) • Confidence (A  B) = P(B|A) • Luật A  B được gọi là đảm bảo độ hỗ trợ s trong D nếu s(A  B)  s. Luật DW AB được gọi là đảm bảo độ tin cậy c trong D nếu c(A  B)  c. Tập mạnh. 217

Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp

 Tập mục I={i1, …, ik}. CSDL giao dịch

D = {d  I}

Transaction-id

Items bought

 A, B  I, AB=: AB là luật kết

10 A, B, C

hợp

 Bài toán tìm luật kết hợp.

20 A, C

30 A, D

40 B, E, F

Customer buys both

Cho trước độ hỗ trợ tối thiểu s>0, độ tin cậy tối thiếu c>0. Hãy tìm mọi luật kết hợp mạnh XY. Giả sử min_support = 50%, min_conf = 50%:

Customer buys diaper

A  C (50%, 66.7%) C  A (50%, 100%)

 Hãy trình bày các nhận xét về khái

niệm luật kết hợp với khái niệm phụ thuộc hàm.

 Các tính chất Armstrong ở đây.

DW Customer buys beer DM

218

Một ví dụ tìm luật kết hợp

Transaction-id Items bought

Min. support 50% Min. confidence 50%

10 A, B, C

{B}

50%

20 A, C Frequent pattern Support 30 A, D {A} 75% 40 B, E, F

For rule A  C:

{C} 50%

support = support({A}{C}) = 50% confidence = support({A}{C})/support({A}) = 66.6%

{A, C} 50%

DW

DM

219

Khai niệm khai phá kết hợp

DW

DM

220

Khái niệm khai phá luật kết hợp

 Khai phá luật kết hợp:

 Tìm tất cả mẫu phổ biến, kết hợp, tương quan, hoặc cấu trú nhan-quả trong tập các mục hoặc đối tượng trong CSDL quan hệ hoặc các kho chứa thông tin khác.

 Mẫu phổ biến (Frequent pattern): là mẫu (tập mục, dãy mục…) mà xuất hiện phổ biến trong 1 CSDL [AIS93]  Động lực: tìm mẫu chính quy (regularities pattern) trong DL  Các mặt hàng nào được mua cùng nhau? — Bia và bỉm

(diapers)?!

 Mặt hàng nào sẽ được mua sau khi mua một PC ?  Kiểu DNA nào nhạy cảm với thuộc mới này?  Có khả năng tự động phân lớp Web hay không ?

DW

DM

221

Mẫu phổ biến và khai phá luật kết hợp là một bài toán bản chất của khai phá DL

 Nền tảng của nhiều bài toán KPDL bản chất

 Kết hợp, tương quan, nhân quả

 Mẫu tuần tự, kết hợp thời gian hoặc vòng, chu kỳ bộ

phận, kết hợp không gian và đa phương tiện

 Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích tụ

(nén dữ liệu ngữ nghĩa)

 Ứng dụng rộng rãi

 Ví dụ: Phân tích DL bóng rổ, tiếp thị chéo (cross-

marketing), thiết kế catalog, phân tích chiến dịch bán hàng

DW  Phân tích Web log (click stream), Phân tích chuỗi DNA v.v. DM

222

2. Các thuật toán khai phá vô hướng LKH

 Khái quát: Khai phá luật kết hợp gồm hai bước:  Tìm mọi tập mục phổ biến: theo min-sup  Sinh luật mạnh từ tập mục phổ biến

 Mọi tập con của tập mục phổ biến cũng là tập mục phổ biến

 Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} cũng vậy: Mọi

giao dịch chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}.  Nguyên lý tỉa Apriori: Với tập mục không phổ biến thì không cần phải

sinh ra/kiểm tra mọi tập bao nó!

 Phương pháp:

 Sinh các tập mục ứng viên dài (k+1) từ các tập mục phổ biến có độ

dài k (Độ dài tập mục là số phần tử của nó),

 Kiểm tra các tập ứng viên theo CSDL

 Các nghiên cứu hiệu năng chứng tỏ tính hiệu quả và khả năng mở rộng

của thuật toán

 Agrawal & Srikant 1994, Mannila, và cộng sự 1994

DW

DM

223

Thuật toán Apriori

Trên cơ sở tính chất (nguyên lý tỉa) Apriori, thuật toán hoạt động theo quy tắc quy hoạch động

• Từ các tập Fi = {ci| ci tập phổ biến, |ci| = i} gồm mọi tập mục phổ biến có độ dài i với 1  i  k,

• đi tìm tập Fk+1 gồm mọi tập mục phổ biến

có độ dài k+1.

Trong thuật toán, các tên mục i1, i2, … in (n = |I|) được sắp xếp theo một thứ tự cố định (thường được đánh chỉ số 1, 2, ..., n).

DW

DM

224

Thuật toán Apriori

DW

DM

225

Thuật toán Apriori: Thủ tục con Apriori-gen

Trong mỗi bước k, thuật toán Apriori đều phải duyệt CSDL D. Khởi động, duyệt D để có được F1. Các bước k sau đó, duyệt D để tính số lượng giao dịch t thoả từng ứng viên c của Ck+1: mỗi giao dịch t chỉ xem xét một lần cho mọi ứng viên c thuộc Ck+1.

Thủ tục con Apriori-gen sinh tập phổ biến: tư tưởng

DW

DM

226

Thủ tục con Apriori-gen

DW

DM

227

Một ví dụ thuật toán Apriori (s=0.5)

Itemset sup Itemset sup

Database TDB

{A} 2 {A} 2

L1

Tid Items {B} 3

C1

{C}

3

{B} 3 10 A, C, D {C} 3

1st scan

20 B, C, E {D} 1 {E} 3 30 A, B, C, E {E} 3

40 B, E

C2

C2

Itemset

2nd scan

{A, B}

L2

{A, C}

{A, E}

{B, C} 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 {B, E}

{C, E}

Itemset DW

L3

C3

3rd scan

DM {B, C, E} Itemset {B, C, E} sup 2 228

Chi tiết quan trọng của Apriori

 Cách thức sinh các ứng viên:  Bước 1: Tự kết nối Lk  Step 2: Cắt tỉa

 Cách thức đếm hỗ trợ cho mỗi ứng viên.

 Ví dụ thủ tục con sinh ứng viên  L3={abc, abd, acd, ace, bcd}  Tự kết nối: L3*L3 từ abc

• abcd

và abd

• acde

từ acd và ace

 Tỉa:

• acde là bỏ đi vì ade không thuộc L3

 C4={abcd}

DW

DM

229

Ví dụ: D, min_sup*|D| = 2 (C4 = )

DW

DM

230

Sinh luật kết hợp

Việc sinh luật kết hợp gồm hai bước

 Với mỗi tập phổ biến W tìm được hãy sinh ra mọi tập

con thực sự X khác rỗng của nó.

 Với mỗi tập phố biến W và tập con X khác rỗng thực sự của nó: sinh luật X  (W – X) nếu P(W-X|X)  c.

Như ví dụ đã nêu có L3 = {{I1, I2, I3}, {I1, I2, I5}}

Với độ tin cậy tối thiểu 70%, xét tập mục phổ biến {I1, I2,

I5} có 3 luật như dưới đây:

DW

DM

231

Cách thức tính độ hỗ trợ của ứng viên

 Tính độ hỗ trợ ứng viên (lệnh 4-8) vấn đề cần quan tâm

 Số lượng ứng viên là rất lớn

 Một giao dịch chứa nhiều ứng viên

 Phương pháp:

 Tập mục ứng viên được chứa trong một cây-băm

(hash-tree)

 Lá của cây băm chứa một danh sách ứng viên và bộ

đếm (độ hỗ trợ hiện thời)

 Nút trong chứa bảng băm

 Hàm tập con: tìm ứng viên trong tập ứng viên

DW

DM

232

Tính độ hỗ trợ của ứng viên

 Tập các ứng viên Ck được lưu trữ trong một cây-băm.

 Gốc của cây băm ở độ sâu 1. Lá chứa một danh sách tập mục thuộc Ck.  Nút trong chứa một bảng băm (chắng hạn mod N): mỗi ô trỏ tới một nút khác

(Nút ở độ sâu d trỏ tới các nút ở độ sâu d+1).  Khi khởi tạo: gôc là nút lá với danh sách rỗng.  Xây dựng cây băm - thêm một tập mục c:

 bắt đầu từ gốc đi xuống theo cây cho đến khi gặp một lá.  Tại một nút trong độ sâu d:

• quyết định theo nhánh nào: áp dụng hàm băm tới mục thứ d của tập mục này.  Khi số lượng tập mục tại một lá vượt quá ngưỡng quy định, lá được chuyển thành

một nút trong và phân chia danh sách các tập mục như hàm băm.  Tính độ hỗ trợ: tìm tất cả các ứng viên thuộc giao dịch t:

 Nếu ở nút gốc: băm vào mỗi mục trong t.  Nếu ở một lá: tìm các tập mục ở lá này thuộc t và bổ sung chỉ dẫn các tập mục

này tới tập trả lời.

 Nếu ở nút trong và đã đạt được nó bằng cách băm mục i, trên từng mục đứng sau

i trong t và áp dụng đệ quy thủ tục này sang nút trong thùng tương ứng. DW

DM

233

Ví dụ: Tính hỗ trợ các ứng viên

Hàm tập con

3,6,9

1,4,7

Có tập các ứng viên độ dài 3 là 124, 125, 136, 145, 159, 234, 345, 356, 357, 367, 368, 457, 458, 567, 689

2,5,8

1, 4, 7 đi sang trái; 2, 5, 8 dừng ở giữa; 3, 6, 9 đi sang phải

124 125 136

Thêm 145 vượt qua ngưỡng, đưa 4 tập này sang nút con trái. Vì 4 tập này đều vượt qua ngưỡng nên tách thành 145; 124, 125; 136

Thêm 159 bổ sung vào nút giữa cây con trái

Thêm 234 bổ sung vào nút giữa cây mẹ

2 3 4 5 6 7

1 4 5

3 4 5

1 3 6

3 6 7 3 6 8

3 5 6 3 5 7 6 8 9

1 5 9

DW

Thêm 345 bổ sung vào nút phải cây mẹ; sau đó tách cây con phải 345; 356, 357; 367, 368

1 2 4 4 5 7

DM

1 2 5 4 5 8

234

Ví dụ: Tính hỗ trợ các ứng viên

Hàm tập con

3,6,9

1,4,7

Giao dịch t=1 2 3 5 6

2,5,8

1, 4, 7 đi sang trái; 2, 5, 8 dừng ở giữa; 3, 6, 9 đi sang phải

1 + 2 3 5 6

1 3 + 5 6

2 3 4 5 6 7

1 4 5

3 4 5

1 3 6

3 6 7 3 6 8

1 2 + 3 5 6

3 5 6 3 5 7 6 8 9

1 5 9

1 2 4 4 5 7

1 2 5 4 5 8

DM

12356 sang trái; 2356 ở giữa; 356 sang phải DW Trái: 12356 trái; 2356 ở giữa; 356 sang phải; … Bộ đếm của ba ứng viên 125, 136, 356 được tăng thêm 1 với giao dịch t-12356 235

Thi hành hiệu quả thuật toán Apriori trong SQL

 Khó có thể có một hiệu quả tốt nếu chỉ tiếp cận thuần

SQL (SQL-92)

 Sử dụng các mở rộng quan hệ - đối tượng như UDFs,

BLOBs, hàm bảng v.v.

 Nhận được các thứ tự tăng quan trọng

 Xem bài: S. Sarawagi, S. Thomas, and R. Agrawal. Integrating

association rule mining with relational database systems: Alternatives and implications. In SIGMOD’98

DW

DM

236

Thách thức khai phá mẫu phổ biến

 Thách thức

 Duyệt nhiều lần CSDL giao dịch

 Lượng các ứng viên rất lớn

 Tẻ nhạt việc tính toán độ hỗ trợ

 Cải tiến Apriori: tư tưởng chung  Giảm số lần duyệt CSDL giao dịch

 Rút gọn số lượng các ứng viên

 Giảm nhẹ tính độ hỗ trợ của các ứng viên

DW

DM

237

DIC (Đếm tập mục động): Rút số lượng duyệt CSDL

ABCD

ABC ABD ACD BCD

 Xây dựng dàn tập mục  Khi mà A và D được xác định là phổ biến thì việc tính toán cho AD được bắt đầu  Khi mọi tập con độ dài 2 của BCD được xác định là phổ biến: việc tính toán cho BCD được bắt đầu.

AB AC BC AD BD CD

Transactions

A B C D

Apriori

1-itemsets 2-itemsets …

1-itemsets 2-items

DIC

3-items

DW

DM

238

{} Itemset lattice S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD’97

Giải pháp Phân hoạch (Partition): Duyệt CSDL chỉ hai lần

 Mọi tập mục là phổ biến tiềm năng trong CSDL bắt buộc phải phổ biến ít nhất một vùng của DB  Scan 1: Phân chia CSDL và tìm các mẫu cục bộ  Scan 2: Hợp nhất các mẫu phổ biến tổng thể  A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB’95

DW

DM

239

Ví dụ về mẫu phổ biến

 Chọn một mẫu của CSDL gốc, khai phá mẫu phổ biến nội

bộ mẫu khi dùng Apriori

 Duyệt CSDL một lần để kiểm tra các tập mục phổ biến tìm thấy trong ví dụ, chỉ có các bao (borders ) đóng của các mẫu phổ biến được kiểm tra  Ví dụ: kiểm tra abcd thay cho ab, ac, …, v.v.

 Duyệt CSDL một lần nữa để tìm các mẫu phổ biến bị mất

(bỏ qua)

H. Toivonen. Sampling large databases for association rules. In VLDB’96

DW

DM

240

DHP: Rút gọn số lượng các ứng viên

 Một k-tập mục mà bộ đếm trong lô băm tương ứng dưới

ngưỡng (=3) thì không thể là tập mục phổ biến  Ứng viên: a, b, c, d, e  Điểm vào băm: {ab, ad, ae} {bd, be, de} …  1-tập mục phổ biến: a, b, d, e  ab không là một ứng viên 2-tập mục nếu tống bộ đếm trong lô băm {ab, ad, ae} là dưới ngưỡng hỗ trợ. Mọi giao dịch có chứa a đều ở lô băm {ab, ad, ae}.

J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining

association rules. In SIGMOD’95

DW

DM

241

Eclat/MaxEclat và VIPER: Thăm dò dạng dữ liệu theo chiều ngang

 Dùng danh sách tid của giáo dịch trong một tập mục

 Nén danh sách tid

 Tập mục A: t1, t2, t3, sup(A)=3

 Tập mục B: t2, t3, t4, sup(B)=3

 Tập mục AB: t2, t3, sup(AB)=2

 Thao tác chính: lấy giao của các danh sách tid  M. Zaki et al. New algorithms for fast discovery of association rules. In KDD’97

 P. Shenoy et al. Turbo-charging vertical mining of large databases. In

SIGMOD’00

DW

DM

242

Thắt cổ chai của khai phá mẫu phổ biến

 Duyệt CSDL nhiều là tốn kém  KP mẫu dài cần nhiều bước để duyệt và sinh nhiều ứng

viên  Để tìm các tập mục phổ biến i1i2…i100

0

• # duyệt: 100 • # ứng viên: (100

1) + (100

1 2) + … + (1

0

0) = 2100-1 = 1.27*1030 ! 0

 Thắt cổ chai: sinh ứng viên và kiểm tra  Tránh sinh ứng viên?

DW

DM

243

KP mẫu phổ biến không cần sinh ƯV

 Dùng các mục phổ biến để tăng độ dài mẫu từ các mẫu

ngắn hơn

 “abc” là một mẫu phổ biến

 Nhận mọi giao dịch có “abc”: DB|abc (DB đã luôn có abc: “có

điều kiện”)

 “d” là một mục phổ biến trong DB|abc  abcd là một mẫu

phổ biến

DW

DM

244

Xây dựng cây FP từ một CSDL giao dịch

(ordered) frequent items

min_support = 3

TID 100 200 300 400 500

Items bought {f, a, c, d, g, i, m, p} {a, b, c, f, l, m, o} {b, f, h, j, o, w} {b, c, k, s, p} {a, f, c, e, l, p, m, n}

{f, c, a, m, p} {f, c, a, b, m} {f, b} {c, b, p} {f, c, a, m, p}

1. Duyệt CSDL một lần, tìm

{}

Header Table

f:4

c:1

các 1-tập mục phổ biến (mẫu mục đơn). Loại các mục có độ hỗ trợ < minsup. Xếp các mục phổ biến theo thứ tự giảm dần về độ hỗ trợ (bậc): Tạo f-list. Tạo cây FP với gốc nhãn {}

c:3

b:1

b:1

2. Duyệt CSDL lần nữa: Với

a:3

p:1

Item frequency head f c a b m p

4 4 3 3 3 3

m:2

b:1

DW

DM

mỗi giao dịch t: xâu các mục phổ biến theo thứ tự như 2 và biểu diễn dưới dạng [p|P] với p là mục đầu, còn P là xâu mục còn lại; Gọi insert_tree ([p|P]), T)

p:2 m:1

F-list=f-c-a-b-m-p

245

3. Tìm tập phổ biến trên cây

FP

Xây dựng cây FP

DW

DM

246

Xây dựng cây FP: chèn một xâu vào cây

DW

DM

247

Lợi ích của cấu trúc FP-tree

 Tính đầy đủ

 Duy trì tính đầy đủ thông tin để khai phá mẫu phổ biến  Không phá vỡ mẫu dài bới bất kỳ giao dich

 Tính cô đọng

 Giảm các thông tin không liên quan: mục không phổ

biến bỏ đi

 Sắp mục theo tần số giảm: xuất hiện càng nhiều thì

cành hiệu quả

 Không lớn hơn so với CSDL thông thường

DW

DM

248

Tìm tập phổ biến từ cấu trúc FP-tree

DW

DM

249

Mẫu cực đại (Max-patterns)

 Mẫu phổ biến {a1, …, a100}  (100

0 0) = 1 2) + … + (1 0 0

 Mẫu cực đại: Mẫu phổ biến mà không là tập con thực sự

của mẫu phổ biến khác  BCDE, ACD là mẫu cực đại  BCD không là mẫu cực đại

Tid Items

10 A,B,C,D,E

20 B,C,D,E, 30 A,C,D,F

1) + (100 2100-1 = 1.27*1030 frequent sub-patterns!

Min_sup=2

DW

DM

250

Tập mục phổ biến cực đại

Một tập mục cực đại (Maximal Intemset) là tập mục phổ biến không là tập con thực sự của một tập mục phổ biến khác

Maximal Itemsets

Infrequent Itemsets

Border

DW

DM

251

Tập mục đóng

Tập mục đóng là tập mục mà không là tập con thực sự của một tập mục có cùng độ hỗ trợ

X đóng: Y  X  s(Y) < s(X)

DW

DM

252

Phân biệt tập mục cực đại với tập mục đóng

Transaction Ids

Not supported by any transactions

DW

DM

253

Tập mục cực đại với tập phổ biến đóng

Minimum support = 2

Closed but not maximal

Closed and maximal

# Closed = 9 # Maximal = 4

DW

DM

254

Tập mục cực đại với tập mục đóng

DW

DM

255

Tập mục cực đại với tập mục đóng

DW

DM

256

Tập mục cực đại với tập mục đóng

R. Bayardo. Efficiently mining long patterns from databases. SIGMOD’98 J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining

Frequent Closed Itemsets", DMKD'00

Mohammed Javeed Zaki, Ching-Jiu Hsiao: CHARM: An Efficient

Algorithm for Closed Itemset Mining. SDM 2002

DW

DM

257

3. Khai phá kiểu đa dạng luật kết hợp/tương quan

DW

DM

258

Luật kết hợp đa mức

 Các mục có thể phân cấp  Đặt hỗ trợ linh hoạt: Mục cấp thấp hơn là kỳ vọng có độ

hỗ trợ thấp hơn.

 CSDL giao dịch có thể được mã hóa theo chiều và mức  Thăm dò KP đa mức chia sẻ

uniform support

reduced support

Level 1 min_sup = 5%

Level 1 min_sup = 5%

Milk [support = 10%]

Level 2 min_sup = 3%

2% Milk [support = 6%]

Skim Milk [support = 4%]

Level 2 min_sup = 5%

DW

DM

259

Kết hợp đa chiều

 Luật đơn chiều (viết theo dạng quan hệ (đối tượng, giá trị)):

buys(X, “milk”)  buys(X, “bread”)

 Luật đa chiều:  2 chiều / thuộc tính

 Luật kết hợp liên chiều (không có thuộc tính lặp)

age(X,”19-25”)  occupation(X,“student”)  buys(X,“coke”)

 Luật KH chiều-kết hợp (lai/hybrid) (lặp thuộc tính)

age(X,”19-25”)  buys(X, “popcorn”)  buys(X, “coke”)

 Thuộc tính phân lớp

 Tìm số lượng các giá trị khả năng không được sắp

 Thuộc tính định lượng

 Số, thứ tự ngầm định trong miền giá trị

DW

DM

260

Kết hợp đa mức: Rút gọn lọc

 Trong luật phân cấp, một luật có thể dư thừa do đã có

quan hệ giữa “tổ tiên” của các mục.

 Ví dụ

 milk  wheat bread [support = 8%, confidence = 70%]

 2% milk  wheat bread [support = 2%, confidence = 72%]

 Nói rằng: luật đầu tiên là tổ tiên luật thứ hai.

 Một luật là dư thừa nếu độ hỗ trợ của nó là khít với giá trị

“mong muốn”, dựa theo tổ tiên của luật.

DW

DM

261

Luật kết hợp định lượng

 Thuộc tính số là sự rời rạc hóa động d

 Độ tin cậy hoặc độ cô đọng của luật là cực đại

 Luật kết hợp định lượng 2-D: Aquan1  Aquan2  Acat  Phân cụm các luật kết hợp Liền kề nhau từ các luật Tổng quát dựa trên Lưới 2-D

 Ví dụ

age(X,”30-34”)  income(X,”24K - 48K”)

 buys(X,”high resolution TV”)

DW

DM

262

Khai phá luật KH dựa theo khoảng cách

 Phương pháp đóng thùng không nắm bắt được ngữ nghĩa

của dữ liệu khoảng

 Phân vùng dựa trên khoảng cách, rời rạc có ý nghĩa hơn

khi xem xét :  Mật độ/ số điểm trong một khoảng  Tính “gần gũi” của các điểm trong một khoảng

DW

DM

263

Độ đo hấp dẫn: Tương quan (nâng cao)

 play basketball  eat cereal [40%, 66.7%] là lạc

 Phần trăm chung của sinh viên ăn ngũ cốc là 75% cao hơn so với

66.7%.

 play basketball  not eat cereal [20%, 33.3%] là chính xác hơn, do

độ hỗ trợ và tin cậy thấp hơn

 Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao)

Basketball

Not basketball

Sum (row)

Cereal

2000

1750

3750

Not cereal

1000

250

1250

Sum(col.)

3000

2000

5000

DW

DM

264

4. KPDL dựa trên ràng buộc

 Tìm tất cả các mẫu trong CSDL tự động? — phi hiện

thực!  Mẫu có thể quá nhiều mà không mục đích!

 KPDL nên là quá trình tương tác

 Người dùng trực tiếp xác định KPDL gì khi dùng ngôn

ngữ hỏi KPDL (hoặc giao diện đồ họa)

 KP dựa theo ràng buộc

 Linh hoạt người dùng: cung cấp ràng buộc trên cái mà

KP

 Tối ưu hệ thống: thăm dò các ràng buộc để hiệu quả

KP: KP dựa theo ràng buộc

DW

DM

265

Ràng buộc trong KPDL

 Ràng buộc kiểu tri thức:

 classification, association, etc.  Ràng buộc dữ liệu — dùng câu hỏi kiếu SQL

 Tìm các cặp sản phẩn mua cùng nhau trong

Vancouver vào Dec.’00

 Ràng buộc chiều/cấp

 Liên quan tới vùng, giá, loại hàng, lớp khách hàng

 Ràng buộc luật (mẫu)

 Mua hàng nhỏ (price < $10) nhanh hơn mua hàng lớn

(sum > $200)  Ràng buộc hấp dẫn

 Luật mạng: min_support  3%, min_confidence 

60%

DW

DM

266

KP ràng buộc <> tìm kiếm dựa theo ràng buộc

 KP ràng buộc <> tìm/lập luận dựa theo ràng buộc

 Cả hai hướng tới rút gọn không gian tìm kiếm  Tìm mọi mẫu bảm đảm ràng buộc <> tìm một vài (một_ câu trả lời của tìm dựa theo ràng buộc trong AI (TTNT)

 Cố tìm theo ràng buộc <> tìm kiếm heuristic  Tích hợp hai cái cho một bài toán tìm kiếm thú vị

 KP ràng buộc <> quá trình hỏi trong hệ CSDL quan hệ

 Quá trình hỏi trong CSDL quan hệ đòi hỏi tìm tất cả  KP mẫu ràng buộc chung một triết lý tương tựng như cố

gắng chọn về chiều sâu của câu hỏi

DW

DM

267

KP mấu phổ biến ràng buộc: vấn đề tố ưu hóa câu hỏi

 Cho một câu hỏi KP Mấu phổ biến với một tập ràng buộc C, thì thuật

toán nên là  Mạnh mẽ: chỉ tìm các tập phố biến bảo đảm ràng buộc C  đầy đủ: Tìm tất cả tập phổ biến bảo đảm ràng buộc C

 Giải pháp “thơ ngây/hồn nhiên” (naïve)

 Tìm tất cát tập PB sau đó kiểm tra ràng buộc

 Tiếp cận hiệu quả hơn

 Phân tích tính chất các ràng buộc một cách toàn diện  Khai thác chúng sâu sắc có thể nhất trong tính toán mẫu

PB.

DW

DM

268

Không đơn điêu trong KP theo ràng buộc

TDB (min_sup=2)

 Chống đơn điệu (Anti-monotonicity)

TID Transaction

10 a, b, c, d, f

 Một tập mục S vi phạm ràng buộc, mọi tập lớn hơn nó cũng vi phạm

20 b, c, d, f, g, h

 sum(S.Price)  v là chống đơn điệu

30 a, c, d, e, f

 sum(S.Price)  v là không chống đơn

40 c, e, f, g

điệu

Item Profit

b

0

 Ví dụ. C: range(S.profit)  15 là chống

a 40

đơn điệu

c -20

 Tập mục ab vi phạm C

d 10

e -30

 Cũng vậy mọi tập chứa ab

f 30

g DW

h 20 DM -10 269

Ràng buộc nào là chống đơn điệu

Ràng buộc

Chống đơn điệu

No

v  S

no

S  V

yes

S  V

no

min(S)  v

yes

min(S)  v

yes

max(S)  v

no

max(S)  v

yes

count(S)  v

no

count(S)  v

yes

sum(S)  v ( a  S, a  0 )

no

sum(S)  v ( a  S, a  0 )

yes

range(S)  v

no

range(S)  v

convertible

avg(S)  v,   { , ,  }

yes

support(S)  

DW

no

support(S)  

DM

270

Tính đơn điệu trong KP luật dựa theo ràng buộc

TDB (min_sup=2)

 Tính đơn điệu

TID Transaction

10 a, b, c, d, f

20 b, c, d, f, g, h

 Khi một tập mục S thỏa mãn ràng buộc, thì mọi tập lớn hơn của nó cũng thỏa mãn

30 a, c, d, e, f

40 c, e, f, g

 sum(S.Price)  v là đơn điệu

Item Profit

 min(S.Price)  v là đơn điệu

a 40

b 0

 Ví dụ. C: range(S.profit)  15

c -20

 Tập mục ab đảm bảo C

d 10

f

30

 Cũng vậy mọi tập chứa ab

e -30

g DW

h 20 DM -10 271

Ràng buộc đơn điệu

Ràng buộc

Đơn điệu

yes

v  S

yes

S  V

no

S  V

yes

min(S)  v

no

min(S)  v

no

max(S)  v

yes

max(S)  v

no

count(S)  v

yes

count(S)  v

no

sum(S)  v ( a  S, a  0 )

yes

sum(S)  v ( a  S, a  0 )

no

range(S)  v

yes

range(S)  v

convertible

avg(S)  v,   { , ,  }

no

support(S)  

DW

yes

support(S)  

DM

272

Tính cô đọng

 Tính cô đọng:

 Cho A1, là tập mục bảo đảm một ràng buộc cô đọng C, thì mọi S bảm đảm C là dựa trên A1 , chằng hạn., S chứa một tập con thuộc A1

 Tư tưởng: Bỏ qua xem xét CSDL giao dịch, có chăng một tập mục S bảo đảm ràng buộc C có thể được xác định dựa theo việc chọn các mục

 min(S.Price)  v là cô đọng

 sum(S.Price)  v không cô đọng

 Tối ưu hóa: Nếu C là cô đọng có thể đẩy đếm trước

DW

DM

273

Ràng buộc cô đọng

Ràng buộc

Cô đọng

yes

v  S

yes

S  V

yes

S  V

yes

min(S)  v

yes

min(S)  v

yes

max(S)  v

yes

max(S)  v

weakly

count(S)  v

weakly

count(S)  v

no

sum(S)  v ( a  S, a  0 )

no

sum(S)  v ( a  S, a  0 )

no

range(S)  v

no

range(S)  v

no

avg(S)  v,   { , ,  }

no

support(S)  

DW

no

support(S)  

DM

274

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

Database D

L1

C1

Scan D

C2

C2

Scan D

L2

DW

L3

C3

Scan D

DM

275

Thuật toán Naïve: Apriori +ràng buộc

Database D

L1

C1

Scan D

C2

C2

Scan D

L2

Constraint:

DW

L3

C3

Scan D

DM

Sum{S.price < 5} 276

Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu

Database D

L1

C1

Scan D

C2

C2

Scan D

L2

Constraint:

DW

L3

C3

Scan D

DM

Sum{S.price < 5} 277

Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu

Database D

L1

C1

Scan D

C2

C2

Scan D

L2

Constraint:

DW

L3

C3

Scan D

DM

min{S.price <= 1 }

278

5. Khai phá mẫu dãy

DW

Phần mềm phân tích chuỗi thời gian EidoSearch: Trợ giúp đánh dấu mẫu dữ liệu hấp dẫn và EidoSearch đi tìm mọi mẫu tương tự từ quá khứ và hiện tại, phân tích kết quả tìm kiếm này, và chỉ ra xu hướng gì sẽ xảy ra. Gait-CAD Matlab toolbox: trực quan hóa và phân tích chuỗi thời gian, bao gồm phân lớp, hồi quy, và phân cụm. Giấy phép GNU-GPL. Miningco: chương trình mã nguồn mở tự động tìm ra mẫu và quan hệ trong weblogs và các bộ dữ liệu khác. SAS Enterprise Miner XAffinity (TM): xác định mối quan hệ thân hoặc mẫu trong giao dịch và dòng dữ liệu nháy phím http://www.kdnuggets.com/software/sequence.html

DM

279

CSDL TT và PT MTT (2)

 CSDL giao dịch, CSDL chuỗi thời gian <> CSDL tuần tự

 Mấu PB <> mấu TT (PB)

 Ứng dụng của KP Mấu TT

 Tuần tự mua của khách hàng:

• Đầu tiên mua máy tính, sau đó CD-ROM, và sau đó là máy

ảnh số, trong vòng 3 tháng.

 Phẫu thuật y tế, thảm họa tự nhiên (động đất…), quá trình KH

và kỹ nghệ, chứng khoán và thị trường….

 Mẫu gọi điện thoại, dòng click tại Weblogs

 Dãy DNA và cấu trúc gene

DW

DM

280

Khái niệm KP mẫu TT

 Cho một tập các dãy, tìm tập đầy đủ các dãy con phổ biến

dãy TT : < (ef) (ab) (df) c b >

CSDL dãy TT

SID

sequence

10

Một phần tử chứa một tập mục. Tập mục trong một phần tử là không thứ tự , và viết chúng theo ABC.

20

<(ad)c(bc)(ae)>

30

<(ef)(ab)(df)cb>

là dãy con của

40

DW

Cho độ hỗ trợ min_sup =2, <(ab)c> là mẫu tuần tự sequential pattern DM

281

Một số chủ đề khai phá dữ liệu nóng

DW

DM

282