Bài giảng Xây dựng hệ khai mỏ dữ liệu: Mẫu thường xuyên, luật kết hợp - Phan Hiền

XÂY DỰNG HỆ KHAI MỎ DỮ LIỆU

MẪU THƯỜNG XUYÊN, LUẬT KẾT HỢP

Phan Hiền

KHÁI QUÁT

Đây là phương pháp khai mỏ dựa trên độ lặp lại thường xuyên của mẫu tin nào đó.  Xác định quy luật quan hệ giữa các thuộc tính (phần tử) trong mẫu tin đó.

Lấy ví dụ: Trong vô số khách hàng mua hàng của siêu thị, nhà quản lý đặt ra vấn đề là các giỏ hàng thường xuyên có các món hàng gì.

KHÁI QUÁT

Ta nhận thấy thường người dùng mua áo đầm

là mua nón kiểu.

mua áo đầm  mua nón kiểu (Hỗ trợ là 0.2 và độ tin là 0.8) Ta có thể nói như sau: Chỉ có 20% số người

mua áo đầm và nón kiểu trên toàn bộ người mua. Nhưng trong số tất cả người mua áo đầm, có 80% người mua kèm nón kiểu.

 Quan tâm đến 2 khái niệm độ tin & hỗ trợ

KHÁI NIỆM

 Tập giá trị (ItemSet) I = {I1,I2,…,In}  Giao tác (Transaction) T = {Ik,..,Ih} con của I.  Luật kết hợp A và B

Kết hợp G  D có Hỗ trợ : Độ tin :

T4 = {M,D}

2/5 2/3

◦ A con I, B con I, và A,B cùng thuộc vào T ◦ Suy ra A  B hay B  A Cho tập các sản phẩm I = {G,D,M} T1 = {G,D} T2 = {G,M,D} T5 = {M} T3 = {G}  Các giá trị trong ItemSet là cùng thuộc tính.

KHÁI NIỆM

 Các giá trị trong ItemSet là nhiều thuộc tính. I = {X,.,W,.,Y,.} = {X1,…,Xn,… Wk,…, Y1,…, Ym}  Giao tác T là con của I  Luật Xk  Yh có nghĩa

I = {Tuổi, màu} Màu = {xanh, vàng, đỏ}

Tuổi = {20,21,22}

◦ Xk là con của X, Yh là con của Y, và cùng T. Ví dụ: Giao tác T là ý nghĩa độ tuổi thích màu T1={20,vàng} T2={21,vàng} T3={22,đỏ} T4={20,xanh} ,..

KHÁI NIỆM

 Độ hỗ trợ (support)

 Độ tin (confident)

Trong đó

VẤN ĐỀ

 Sự lựa chọn các thuộc tính  Độ hỗ trợ, độ tin như thế nào là phù hợp

THUẬT TOÁN

 Thuật toán Apriori  Thuật toán FP-Tree (Frequent Pattern

Tree)

Hai thuật toán này mục đích để khai thác

các giao tác ít lại mà vẫn có thể xác định được độ hỗ trợ của các kết hợp giá trị. Các thuật toán đều có dùng hệ số tối thiểu của độ hỗ trợ và độ tin để xác định luật.

THUẬT TOÁN APRIORI

Phát biểu: - Cho độ hỗ trợ, tin tối thiểu là Smin , Cmin - Thuật toán tận dụng yếu tố

Giả sử ta có S(A) = x và S(B) = y, trong đó x >= Smin và y < Smin  S(AB) < Smin

Thuật toán chủ yếu tập trung vào điều đó

để giảm bớt sự duyệt các giao tác khi chuyển từ bộ ứng viên k phần tử sang k+1 phần tử.

THUẬT TOÁN APRIORI

Thuật toán: 01: Chuẩn bị các ứng viên – độ rộng k (tổ hợp các giá trị cần xét độ hỗ trợ) 02: Chọn ra các ứng viên thỏa độ hỗ trợ 03: Chuẩn bị các ứng viên có độ rộng k+1 Đó là sự kết hợp các phần tử trong luachon mà có khả năng là thỏa độ hỗ trợ. Trở về bước 01.

THUẬT TOÁN APRIORI

ta có W = X hợp Y và |W| = k + 1 Nếu mọi Z con W và |Z| = k

và mọi Z cũng là con luachonk

thì ungvien(k+1) += W

I = {Ii} / i thuộc [1,n] Cho k = 1, ungvienk = I, luachonk = {} Khi [(k <= n)||(ungvienk != {})] { Với mọi U thuộc ungvienk Nếu S(U[i]) > Smin thì luachonk += U[i] // tao ungvien(k+1) Với mọi X,Y thuộc luachonk { } k++ }

VÍ DỤ APRIORI

Cho tập I = {A,B,C,D,E} Cho tập các giao tác như sau T1 = {A,B,C,D,E} T2 = {A,B,C} T3 = {D,C,B} T4 = {A,B,D} T5 = {D,C} T6 = {D,C,A,B} T7 = {A,B,E,D} Xét với độ hỗ trợ tối thiểu là 0.5 ~ >= 4 lần

VÍ DỤ APRIORI

B1: ungvien1={A,B,C,D,E}, S(ungvien) = {5,6,5,6,2} luachon1={A:5,B:6,C:5,D:6} Xét AB đều có A,B thuộc luachon1  ungvien2 += AB Xét AC đều có A,C thuộc luachon1  ungvien2 += AC ……… Xét CD đều có C,D thuộc luachon1  ungvien2 += CD  ungvien2 = {AB,AC,AD,BC,BD,CD}

VÍ DỤ APRIORI

=> ungvien3 += ABD

=> ungvien3 += BCD

B2: ungvien2 = {AB,AC,AD,BC,BD,CD} tính S(ungvien2) = {5,3,4,4,5,4} luachon2= {AB:5,AD:4,BC:4,BD:5,CD:4} Xét ABD có AB,AD,BD đều thuộc luachon2 Xét ABC có AB,AC,BC có AC không thuộc luachon2 Xét BCD có BC,CD,BD đều thuộc luachon2 Xét ACD có AC,AD,CD có AC không thuộc luachon2 ungvien3 = {ABD,BCD}

VÍ DỤ APRIORI

tính S(ungvien3) = {4,3} luachon3 = {ABD:4}

{A:5,B:6,C:5,D:6}

A -> BD; B -> AD; D -> AB;

B3: ungvien3 = {ABD,BCD} Chấm dứt thuật toán vì ứng viên không còn Lựa chọn = {AB:5,AD:4,BC:4,BD:5,CD:4,ABD:4} Với B4: Xác định các luật và độ tin của luật Với ABD ta có AB -> D; AD -> B; BD -> A; Xét luật AB -> D có C(AB->D) = 4/5 ……

Bài tập APRIORI

T8 = {Nu, 21, Click} T9 = {Nu, 17, Dream} T10 = {Nu, 16, Click} T11 = {Nu, 16, Click} T12 = {Nu, 28, Click}

[21,26] : Trẻ (T) [36,40] : Già (G)

Cho tập { gioitinh, tuoi, xe } T1 = {Nam, 20, Dream} T2 = {Nam, 21, Dream} T3 = {Nam, 15, Dream} T4 = {Nam, 17, Click} T5 = {Nam, 22, Click} T6 = {Nam, 21, Dream} T7 = {Nam, 22, Dream} [10,20] : Thanh niên (TN) Trong đó [27,35] : Trung niên (TR) Dùng Apriori để xác định các luật có thể với Độ hỗ trợ >= 0.2 và độ tin >= 0.7

THUẬT TOÁN FP - TREE

 Thuật toán này tận dụng yếu tố sự kết hợp sau

là sự mở rộng của tổ hợp trước đó.

 Không cần phải chuẩn bị các ứng viên như

S(AB) = 3

Apriori Lấy ví dụ: Ta có AB Khi đó nếu ta tìm thấy được một và chỉ một giao

tác có A, B, C khi đó ta có

ABC

S(ABC) = 1

Mô tả:

A:3 B:3 C:1

THUẬT TOÁN FP - TREE

Thuật toán: 01: Tạo tập các giá trị với độ hỗ trợ giảm dần và

thỏa mãn độ hỗ trợ tối thiểu.  Q

02: Ứng với từng giao tác  Tạo cây T

Ta tạo nhánh cây chỉ với các giá trị đã có ở Q. Đánh dấu tăng 1 nếu một node trên cây được đi qua lại  số lần lặp lại trong nhánh.

03: Duyệt lại từ node trong Q, theo thứ tự thấp đến cao trên cây T. Để xác định các tổ hợp với các số trên node, xác định độ hỗ trợ.

TẠO FP - TREE

(node Ii).solan++ ngược lại Tạo mới (node Ii) là con (TMP)

Nếu (TMP) có chứa con là (node Ii) (TMP) = (node Ii)

Nếu Ii thuộc về Tj { }

Tạo cây với gốc là null ~ TR // Kết quả là cây đủ Q = {Ii} / S(Ii) >= Smin Xếp Q giảm dần theo S Với từng giao tác Tj trong T { Cho (TMP) = (TR.gốc) Cho i = 1 đến Q.kíchthước } // Mỗi lần tạo mới một node thì node.solan = 1

DUYỆT FP - TREE

Tăng độ hỗ trợ của X

Nếu Prefix(Ii) chứa X Ngược lại

Prefix(Ii) += X

Với từng tổ hợp X có chứa Ii và |X| > |Ii|{ } // độ hỗ trợ của X là số lần của (node Ii)

Tạo Pre = {} // chứa các tổ hợp For i = Q.kíchthước đến 1 { Tạo Prefix(Ii) = {} Với từng nhánh có (node Ii) là lá { //là nhánh qua (node Ii) và chỉ xét đến (node Ii) } Lưu lại vào tập Pre += Prefix(Ii) với điều kiện S(Prefix(Ii)) >= Smin } // Có thể bỏ tất cả (node Ii) sau từng lần duyệt

VÍ DỤ FP TREE

Cho tập I = {A,B,C,D,E} Cho tập các giao tác như sau T1 = {A,B,C,D,E} T2 = {A,B,C} T3 = {D,C,B} T4 = {A,B,D} T5 = {D,C} T6 = {D,C,A,B} T7 = {A,B,E,D} Xét với độ hỗ trợ tối thiểu là 0.5 ~ >= 4 lần

VÍ DỤ FP TREE

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T1 = {A,B,C,D,E}, Ta tạo cây

B:1

D:1

A:1

C:1

null

B:1

VÍ DỤ FP TREE

D:1

A:1

Ta tạo cây

C:1

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T2 = {A,B,C},

B:2

D:1 A:1

A:1 C:1

C:1

null

B:2

VÍ DỤ FP TREE

D:1

A:1

A:1

C:1

Ta tạo cây

C:1

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T3 = {D,C,B},

B:3

D:2 A:1

C:1 A:1 C:1

C:1

null

B:3

VÍ DỤ FP TREE

D:2

A:1

C:1

A:1

C:1

Ta tạo cây

C:1

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T4 = {A,B,D},

B:4

D:3 A:1

C:1 A:2 C:1

C:1

null

B:4

VÍ DỤ FP TREE

D:3

A:1

C:1

A:2

C:1

Ta tạo cây

C:1

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T5 = {D,C},

D:1 B:4

C:1 D:3 A:1

C:1 A:2 C:1

C:1

null

B:4

D:1

VÍ DỤ FP TREE

D:3

A:1

C:1

C:1

A:2

C:1

Ta tạo cây

C:1

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T6 = {D,C,A,B},

D:1 B:5

C:1 D:4 A:1

C:1 A:3 C:1

C:2

null

B:5

D:1

VÍ DỤ FP TREE

D:4

A:1

C:1

C:1

A:3

C:1

Ta tạo cây

C:2

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét T7 = {A,B,E,D},

D:1 B:6

C:1 D:5 A:1

C:1 A:4 C:1

C:2

nul l

B: 6

D: 1

VÍ DỤ DUYỆT FP TREE

D: 5

A: 1

C: 1

C: 1

A: 4

C: 1

C: 2

null

: 2 : 3

B:6 D:1

: 3

D:5 A:1 C:1

C:1 A:4 C:1

: 4 : 4 : 3

C:2

Có tập Q = {B:6, D:6, A:5, C:5} Xét C, ta có tổ hợp và độ hỗ trợ B,D,A,C B,D,C (B,D,C:1) + (B,D,C:2) B,A,C (B,A,C:1) + (B,A,C:2) B,C D,C A,C

nul l

B: 6

D: 1

VÍ DỤ DUYỆT FP TREE

D: 5

A: 1

C: 1

C: 1

A: 4

C: 1

C: 2

null

: 4 : 5 : 4

B:6 D:1

Có tập Q = {B:6, D:6, A:5, C:5} Xét A, ta có tổ hợp và độ hỗ trợ B,D,A B,A D,A

A:1 D:5

A:4

nul l

B: 6

D: 1

VÍ DỤ DUYỆT FP TREE

D: 5

A: 1

C: 1

C: 1

A: 4

C: 1

C: 2

: 5

null

Có tập Q = {B:6, D:6, A:5, C:5} Xét D, ta có tổ hợp và độ hỗ trợ B,D

D:1 B:6

D:5

nul l

D: 1

B: 6

VÍ DỤ DUYỆT FP TREE

D: 5

A: 1

C: 1

C: 1

A: 4

C: 1

C: 2

null

B:6

Có tập Q = {B:6, D:6, A:5, C:5} Xét B, ta có tổ hợp và độ hỗ trợ Chấm dứt thuật toán. Từ các tổ hợp đã chọn được ta tạo luật.

Bài tập FP-Tree

T8 = {Nu, 21, Click} T9 = {Nu, 17, Dream} T10 = {Nu, 16, Click} T11 = {Nu, 16, Click} T12 = {Nu, 28, Click}

[21,26] : Trẻ (T) [36,40] : Già (G)

Cho tập { gioitinh, tuoi, xe } T1 = {Nam, 20, Dream} T2 = {Nam, 21, Dream} T3 = {Nam, 15, Dream} T4 = {Nam, 17, Click} T5 = {Nam, 22, Click} T6 = {Nam, 21, Dream} T7 = {Nam, 22, Dream} [10,20] : Thanh niên (TN) Trong đó [27,35] : Trung niên (TR) Dùng FP-Tree để xác định các luật có thể với Độ hỗ trợ >= 0.2 và độ tin >= 0.7

Tạo luật

 Với những tổ hợp các giá trị có mức độ hỗ trợ vượt qua mức tối thiểu, ta có thể tạo các luật kết hợp từ bộ đó.

 Tính toán tất cả độ tin của từng luật để

xác định chính xác luật lựa chọn.

Lấy ví dụ: Có tập {A,B,C} Ta xác định B,C  A; AC  B; BA  C B  A;C  A;A  B;C  B; A  C; B  C A  BC; B  AC; C  AB Tính độ tin cho từng luật  lựa chọn luật phù hợp.

Sự tương quan (Correlation)

 Việc dựa vào độ hỗ trợ và độ tin không

phải lúc nào cũng là giải pháp tốt.

Xét ví dụ sau: Giả sử có 10 phiếu mua hàng. Có 5 phiếu mua gạo, trong đó có 3 phiếu có mua thêm bắp. Có 8 phiếu mua bắp trong 10 phiếu mua. Ta xác định được cặp {G,B} với S(G,B)=5/10; C(GB) = 3/5. Nhưng S(B) = 8/10. Ta có Xác suất mua B nếu đã mua G là 60% Xác suất mua B là 80%. Có nên tin rằng người dùng mua G là mua B không ??? Quan hệ giữa G và B là ra sao, độc lập hay phụ thuộc.

Sự tương quan (Correlation)

 Xét độ

 Nếu giá trị = 1: A và B là độc lập  Nếu giá trị < 1: A và B có quan hệ nghịch  Nếu giá trị > 1: A và B có quan hệ thuận  Đây chỉ là 1 trong nhiều phương pháp.

Ứng dụng

Thu thập dữ liệu, phân tích để có thể giải

quyết cho các vấn đề.

- Khi doanh số của mình giảm, thì sản phẩm nào trên thị trường ??? làm cho sản phẩm của mình mất thế,.. Quy luật nào không ? - Nhu cầu của người dùng với sản phẩm của đối phương tăng, ta có nên tăng sản phẩm đó hay không ??? Hay là phát triển sản phẩm kết hợp hay thay thế với sản phẩm đó, và đó có thể là sản phẩm nào ???? ……..