Khai Phá Dữ Liệu-Phát hiện các luật kết hợp

Khai Phá Dữ Liệu

quangnn-fit@mail.hut.edu.vn

Viện Công nghệ Thông tin và Truyền thông Trường Đại học Bách Khoa Hà Nội

Năm học 2010-2011

Nguyễn Nhật Quang

Nội dung môn học:

(cid:132) Giới thiệu về Khai phá dữ liệu

(cid:132) Giới thiệu về công cụ WEKA

ề

(cid:132) Tiền xử lý dữ liệu

(cid:132) Phát hiện các luật kết hợp

(cid:132) Các kỹ thuật phân lớp và dự đoán (cid:132) Các kỹ thuật phân lớp và dự đoán

(cid:132) Các kỹ thuật phân nhóm

Khai Phá Dữ Liệu

Phát hiện các luật kết hợp – Giới thiệu

(cid:132) Bài toán phát hiện luật kết hợp (Association rule mining) (cid:137) Với một tập các giao dịch (transactions) cho trước, cần tìm các

ộ ập g ( ) , ị

luật dự đoán khả năng xuất hiện trong một giao dịch của các mục (items) này dựa trên việc xuất hiện của các mục khác

Các ví dụ của luật kết hợp:

TID

Items

Bread, Milk

1

{Diaper} → {Beer} {Diaper} → {Beer}

{Milk, Bread} → {Eggs, Coke}

{Beer, Bread} → {Milk}

Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke

2 3 4 4 5

Khai Phá Dữ Liệu

Các định nghĩa cơ bản (1)

(cid:132) Tập mục (Itemset)

(cid:137) Một tập hợp gồm một hoặc nhiều mục

(cid:132) Ví dụ: {Milk, Bread, Diaper}

TID

Items

(cid:137) Tập mục mức k (k-itemset)

Bread, Milk

1

ố ỗ

(cid:132) Một tập mục gồm k mục ổ (cid:132) Tổng số hỗ trợ (Support count) σ ) (S (cid:137) Số lần xuất hiện của một tập mục (cid:137) Ví dụ: σ({Milk, Bread, Diaper}) = 2

Bread Diaper Beer Eggs Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke Bread Milk Diaper Coke

2 2 3 4 5 5

(cid:132) Độ hỗ trợ (Support) s

(cid:137) Tỷ lệ các giao dịch chứa một tập mục (cid:137) Ví dụ: s({Milk, Bread, Diaper}) = 2/5

(cid:132) Tập mục thường xuyên (Frequent/large itemset) (cid:137) Một tập mục mà độ hỗ trợ lớn hơn

hoặc bằng một giá trị ngưỡng minsup

Khai Phá Dữ Liệu

Các định nghĩa cơ bản (2)

TID

Items

(cid:132) Luật kết hợp (Association

Bread, Milk

1

ể

dạng: X → Y, trong đó X và Y là các tập mục

(cid:137) Ví dụ: {Milk, Diaper} → {Beer} (cid:137) Ví dụ: {Milk Diaper} → {Beer}

rule) (cid:137) Một biểu thức kéo theo có

Bread, Diaper, Beer, Eggs Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke

2 3 4 5

(cid:132) Các độ đo đánh giá luật ợ ( (cid:137) Độ hỗ trợ (Support) s

)

{ Milk ,Milk {

Diaper Diaper

} }

Beer Beer

→ →

,Milk

)Beer

( σ

4.0

pp ộ (cid:132) Tỷ lệ các giao dịch chứa cả X và Y đối với tất cả các giao dịch

Diaper, |T| |T|

2 == 5 5

(cid:137) Độ tin cậy (Confidence) c

Diaper,

67.0

,Milk

Diaper

)Beer )

2 == 3

( Milk, σ ( σ

(cid:132) Tỷ lệ các giao dịch chứa cả X và Y đối với các giao dịch chứa X chứa X

Khai Phá Dữ Liệu

Phát hiện các luật kết hợp

(cid:132) Với một tập các giao dịch T, mục đích của bài toán phát

hiện luật kết hợp là tìm ra tất cả các luật có: hiện luật kết hợp là tìm ra tất cả các luật có: (cid:137) độ hỗ trợ ≥ giá trị ngưỡng minsup, và (cid:137) độ tin cậy ≥ giá trị ngưỡng minconf

(cid:132) Cách tiếp cận vét cạn (Brute-force) (cid:137) Liệt kê tất cả các luật kết hợp có thể (cid:137) Tính toán độ hỗ trợ và độ tin cậy cho mỗi luật ậ ỗi l ật h (cid:137) Loại bỏ đi các luật có độ hỗ trợ nhỏ hơn minsup hoặc có độ tin

Tí h t á độ hỗ t à độ ti

⇒ Phương pháp vét cạn này có chi phí tính toán quá

lớn, không áp dụng được trong thực tế!

Khai Phá Dữ Liệu

cậy nhỏ hơn minconf

Phát hiện luật kết hợp

TID

Items

Các luật kết hợp:

Bread, Milk

1 E

B

d Di

Bread, Diaper, Beer, Eggs B Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Coke

2 2 3 4 5

{Milk, Diaper} → {Beer} (s=0.4, c=0.67) {Milk, Beer} → {Diaper} (s=0.4, c=1.0) {Diaper, Beer} → {Milk} (s=0.4, c=0.67) {Beer} → {Milk, Diaper} (s=0.4, c=0.67) {Diaper} → {Milk Beer} {Diaper} → {Milk, Beer} (s 0.4, c 0.5) (s=0 4 c=0 5) {Milk} → {Diaper, Beer} (s=0.4, c=0.5)

(cid:132) Tất cả các luật trên đều là sự phân tách (thành 2 tập con) của

cùng tập mục : {Milk, Diaper, Beer}

(cid:132) Các luật sinh ra từ cùng một tập múc sẽ có cùng độ hỗ trợ,

nhưng có thể khác về độ tin cậy nhưng có thể khác về độ tin cậy

(cid:132) Do đó, trong quá trình phát hiện luật kết hợp, chúng ta có thể

tách riêng 2 yêu cầu về độ hỗ trợ và độ tin cậy

Khai Phá Dữ Liệu

Phát hiện luật kết hợp

(cid:132) Quá trình phát hiện luật kết hợp sẽ gồm 2 bước (2 giai

đoạn) quan trọng: đoạn) quan trọng:

(cid:137) Sinh ra các tập mục thường xuyên (frequent/large itemsets)

(cid:132) Sinh ra tất cả các tập mục có độ hỗ trợ ≥ minsup

(cid:137) Sinh ra các luật kết hợp

(cid:132) Từ mỗi tập mục thường xuyên (thu được ở bước trên), sinh ra

(cid:132) Mỗi luật là một phân tách nhị phân (phân tách thành 2 phần)

tất cả các luật có độ tin cậy cao (≥ minconf) tất cả các luật có độ tin cậy cao (≥ minconf)

(cid:132) Bước sinh ra các tập mục thường xuyên (bước thứ 1)

vẫn có chi phí tính toán quá cao!

Khai Phá Dữ Liệu

của một tập mục thường xuyên

Lattice biểu diễn các tập mục cần xét

null

Với d mục, thì phải xét đến 2d đến 2 các tập mục có thể! thể!

ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

ABCD

ABCE

ABDE

ACDE

BCDE

ABCDE

Khai Phá Dữ Liệu

Sinh ra các tập mục thường xuyên

TID Items Bread, Milk 1 d Milk B 1 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer 4 Bread, Milk, Diaper, Beer 4 Bread, Milk, Diaper, Coke 5

(cid:132) Phương pháp vét cạn (Brute-force) Phương pháp vét cạn (Brute force) (cid:137) Mỗi tập mục trong lattice đều được xét (cid:137) Tính độ hỗ trợ của mỗi tập mục, bằng cách duyệt qua tất cả các

(cid:137) Với mỗi giao dịch, so sánh nó với mỗi tập mục được xét (cid:137) Độ phức tạp ~ O(N.M.w)

(cid:132) Với M = 2d, thì độ phức tạp này là quá lớn!

Khai Phá Dữ Liệu

giao dịch dị h i

Các chiến lược sinh tập mục thường xuyên

(cid:132) Giảm bớt số lượng các tập mục cần xét (M)

(

(cid:137) Tìm kiếm (xét) đầy đủ: M=2d ) (cid:137) Sử dụng các kỹ thuật cắt tỉa (pruning) để giảm giá trị M

) (cid:132) Giảm bớt số lượng các giao dịch cần xét (N)

ợ g

g

(

ị

(cid:137) Giảm giá trị N, khi kích thước (số lượng các mục) của

tập mục tăng lên

(cid:132) Giảm bớt số lượng các so sánh

ố

(

(matchings/comparisons) giữa các tập mục và các giao dịch (N.M) ) g (cid:137) Sử dụng các cấu trúc dữ liệu phù hợp (hiệu quả) để

lưu các tập mục cần xét hoặc các giao dịch

(cid:137) Không cần phải so sánh mỗi tập mục với mỗi giao dịch (cid:137) Không cần phải so sánh mỗi tập mục với mỗi giao dịch

Khai Phá Dữ Liệu

Giảm bớt số lượng các tập mục cần xét

(cid:132) Nguyên tắc của giải thuật Apriori – Loại bỏ (prunning)

dựa trên độ hỗ trợ dựa trên độ hỗ trợ (cid:137) Nếu một tập mục là thường xuyên, thì tất cả các tập con

(subsets) của nó đều là các tập mục thường xuyên Nếu một tập mục là không thường xuyên (not frequent) thì tất cả (cid:137) Nếu một tập mục là không thường xuyên (not frequent), thì tất cả các tập cha (supersets) của nó đều là các tập mục không thường xuyên

(cid:132) Nguyên tắc của giải thuật Apriori dựa trên đặc tính không đơn điệu (anti-monotone) của độ hỗ trợ

XYX

Xs (

)

Ys (

)

∀

Y ) ⇒⊆

≥

(cid:137) Độ hỗ trợ của một tập mục nhỏ hơn độ hỗ trợ của các tập con

Khai Phá Dữ Liệu

của nó

Apriori: Loại bỏ dựa trên độ hỗ trợ

Tập mục không không thường xuyên

Khai Phá Dữ Liệu

Các tập cha của tập mục đó (AB) bị loại bỏ m c đó (AB) bị loại bỏ

Apriori: Loại bỏ dựa trên độ hỗ trợ

Các tập mục mức 1 (1-itemsets)

Các tập mục mức 2 (2- itemsets)

Item Bread Coke C k Milk Beer Diaper Eggs Eggs

Count 4 2 2 4 3 4 1 1

(Không cần xét các tập (Không cần xét các tập mục có chứa mục Coke hoặc Eggs)

Itemset {Bread,Milk} {Bread,Beer} {Bread,Diaper} {Milk,Beer} {Milk,Diaper} {Beer,Diaper}

Count 3 2 3 2 3 3

Các tập mục mức 3 (3-itemsets)

•Nếu xét tất cả các tập mục có thể:

minsup= 3

C o u n t C o u n t 3

6C1 + 6C2 + 6C3 = 41 6 •Với cơ chế loại bỏ dựa trên độ hỗ trợ:

Ite m s e t Ite m s e t { B r e a d ,M ilk ,D ia p e r }

6 + 6 + 1 = 13

Khai Phá Dữ Liệu

Giải thuật Apriori

(cid:132) Sinh ra tất cả các tập mục thường xuyên mức 1 (frequent 1 itemsets): các tập mục thường xuyên chỉ chứa 1 mục 1-itemsets): các tập mục thường xuyên chỉ chứa 1 mục

(cid:132) Gán k = 1 p (cid:132) Lặp lại, cho đến khi không có thêm bất kỳ tập mục

ỳ p

thường xuyên nào mới (cid:137) Từ các tập mục thường xuyên mức k (chứa k mục), sinh ra các

(cid:137) Loại bỏ các tập mục mức (k+1) chứa các tập con là các tập mục

tập mục mức mức (k 1) cần xét tập mục mức mức (k+1) cần xét

(cid:137) Tính độ hỗ trợ của mỗi tập mục mức (k+1), bằng cách duyệt qua (cid:137) Tính độ hỗ trợ của mỗi tập mục mức (k+1) bằng cách duyệt qua

không thường xuyên mức k

(cid:137) Loại bỏ các tập mục không thường xuyên mức (k+1) (cid:137) Thu được các tập mục thường xuyên mức (k+1) Thu được các tập mục thường xuyên mức (k+1)

Khai Phá Dữ Liệu

tất cả các giao dịch

Giảm bớt số lượng các so sánh

(cid:132) Các so sánh (matchings/comparisons) giữa các tập mục cần xét và

ỗ

ầ

ấ

ể

mục cần xét

(cid:132) Để giảm bớt số lượng các so sánh, cần sử dụng cấu trúc băm (hash

các giao dịch (cid:137) Cần phải duyệt qua tất cả các giao dịch, để tính độ hỗ trợ của mỗi tập

so sánh nó với các tập mục chứa trong các ô (hashed buckets)

structure) để lưu các tập mục cần xét (cid:137) Thay vì phải so sánh mỗi giao dịch với mỗi tập mục cần xét, thì chỉ cần

TID Items Bread, Milk , 1 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke Bread, Milk, Diaper, Beer 4 Bread, Milk, Diaper, Coke 5

Khai Phá Dữ Liệu

Sinh ra cây băm (hash tree)

(cid:132) Giả sử chúng ta có 15 tập mục mức 3 cần xét:

{1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8} 4 5} {3 5 6} {3 5 7} {6 8 9} {3 6 7} {3 6 8}

(cid:132) Sinh ra cây băm (Hash tree):

(cid:137) Hàm băm (Hash function) – Ví dụ: h(p) = p mod 3 (cid:137) Kích thước tối đa của nút lá (Max leaf size): Số lượng tối đã các tập

mục được lưu ở một nút lá (Nếu số lượng các tập mục vượt quá giá trị này, nút đó sẽ tiếp tục bị phân chia) – Ví dụ: Max leaf size = 3

(Hàm băm)

2 3 4 5 6 7 3,6,9 1,4,7 1 4 7 1 4 5 1 4 5 3 4 5 3 4 5 1 3 6 3 6 7 3 6 7 3 6 8 2,5,8

3 5 6 3 5 6 3 5 7 6 8 9

1 5 9 1 5 9 1 2 4 4 5 7 4 5 7

Khai Phá Dữ Liệu

1 2 5 1 2 5 4 5 8

Phát hiện luật kết hợp bằng cây băm (1)

(Hàm băm)

Cây băm lưu các tập mục cần xét

1,4,7

3,6,9

2,5,8 2 5 8

2 3 4

5 6 7

1 4 5 1 3 6

3 4 5 3 5 6 3 6 7

3 5 7 3 5 7 3 6 8 3 6 8

Khai Phá Dữ Liệu

6 8 9 1 2 4 1 5 9 1 2 5 Băm (hash) đối với đối với 1, 4, hoặc 7 4 5 7 4 5 8

Phát hiện luật kết hợp bằng cây băm (2)

(Hàm băm)

Cây băm lưu các tập mục cần xét

1,4,7

3,6,9

2,5,8 2 5 8

2 3 4

5 6 7

1 4 5 1 3 6

3 4 5 3 5 6 3 6 7

3 5 7 3 5 7 3 6 8 3 6 8

6 8 9 1 2 4 1 5 9 1 2 5

Khai Phá Dữ Liệu

4 5 7 4 5 8 Băm (hash) (h h) đối với 2, 5, hoặc 8 hoặc 8

Phát hiện luật kết hợp bằng cây băm (3)

(Hàm băm)

Cây băm lưu các tập mục cần xét

1,4,7

3,6,9

2,5,8 2 5 8

2 3 4

5 6 7

1 4 5 1 3 6

3 4 5 3 5 6 3 6 7

3 5 7 3 5 7 3 6 8 3 6 8

6 8 9 1 2 4 1 5 9 1 2 5

Khai Phá Dữ Liệu

4 5 7 4 5 8 Băm (hash) (hash) đối với 3, 6, ặ hoặc 9

Các tập mục mức k trong một giao dịch

(cid:132) Đối với giao

(cid:137) Giả sử trong G ả sử o g mỗi tập mục, các mục được liệt kê theo thứ tự theo thứ tự từ điển

Khai Phá Dữ Liệu

dịch t, hãy xác dịch t, hãy xác định các tập mục mức 3?

Xác định các tập mục bằng cây băm (1)

(Hàm băm)

Giao dịch t

1 2 3 5 6

1,4,7

3,6,9

2,5,8

1 + 2 3 5 6 2 + 3 5 6

2 3 4

5 6 7

1 4 5

1 3 6

3 4 5

3 6 7 3 6 8

3 5 6 3 5 7 6 8 9

1 5 9

1 2 4 4 5 7 4 5 7

1 2 5 4 5 8 4 5 8

Khai Phá Dữ Liệu

3 + 3 + 5 6 5 6

Xác định các tập mục bằng cây băm (2)

(Hàm băm)

1 2 3 5 6 Giao dịch t

1,4,7

3,6,9

1 + 2 3 5 6 2 + 3 5 6

2,5,8

1 2 + 3 5 6

3 + 3 + 5 6 5 6

2 3 4

1 3 + 5 6

5 6 7 5 6 7

1 4 5

1 3 6

3 4 5

3 6 7 3 6 8

3 5 6 3 5 7 6 8 9

1 5 9

1 2 4 4 5 7

1 2 5 4 5 8 4 5 8

g Chỉ cần so sánh giao dịch t với 11 (trong tổng số 15) tập mục cần xét!

Khai Phá Dữ Liệu

1 5 + 6

Apriori: Các yếu tố ảnh hưởng độ phức tạp

(cid:132) Lựa chọn giá trị ngưỡng minsup

(cid:137) Giá trị minsup quá thấp sẽ sinh ra nhiều tập mục thường xuyên (cid:137) Điều này có thể làm tăng số lượng các tập mục phải xét và độ

ể

(cid:132) Kích thước của cơ sở dữ liệu (các giao dịch)

(cid:137) Giải thuật Apriori duyệt cơ sở dữ liệu nhiều lần. Do đó, chi phí

dài (kích thước) tối đa của các tập mục thường xuyên (cid:132) Số lượng các mục trong cơ sở dữ liệu (các giao dịch) (cid:137) Cân thêm bộ nhớ để lưu giá trị độ hỗ trợ đối với mỗi mục (cid:137) Nếu số lượng các mục (tập mục mức 1) thường xuyên tăng lên, thì chi phí tính toán và chi phí I/O (duyệt các giao dịch) cũng tăng

(cid:132) Kích thước trung bình của các giao dịch

(cid:137) Khi kích thước (số lượng các mục) trung bình của các giao dịch tăng lên, thì độ dài tối đa của các tập mục thường xuyên cũng tăng, và chi phí duyệt cây băm cũng tăng tăng và chi phí duyệt cây băm cũng tăng

Khai Phá Dữ Liệu

tính toán của Apriori tăng lên khi số lượng các giao dịch tăng lên

Biểu diễn các tập mục thường xuyên

(cid:132) Trong thực tế, số lượng các tập mục thường xuyên được

sinh ra từ một csdl giao dịch có thể rất lớn sinh ra từ một csdl giao dịch có thể rất lớn

(cid:132) Cần một cách biểu diễn ngắn gọn (compact

representation) representation) (cid:137) Bằng một tập (nhỏ) các tập mục thường xuyên đại diện – mà có thể dùng để suy ra (sinh ra) tất cả các tập mục thường xuyên khác khác

(cid:132) Có 2 cách biểu diễn như vậy

(cid:137) Các tập mục thường xuyên lớn nhất (Maximal frequent itemsets) (cid:137) Các tập mục thường xuyên lớn nhất (Maximal frequent itemsets)

(cid:137) Các tập mục thường xuyên đóng (Closed frequent itemsets)

Khai Phá Dữ Liệu

Các tập mục thường xuyên lớn nhất

(cid:132) Một tập mục thường xuyên là lớn nhất (Maximal frequent itemset), nếu

mọi tập cha (superset) của nó đều là tập mục không thường xuyên

Các tập mục thường xuyên lớn nhất

Ranh giới

Các tập mục không không thường xuyên

Khai Phá Dữ Liệu

Các tập mục thường xuyên đóng

(cid:132) Một tập mục thường xuyên là đóng (Closed frequent itemset), nếu không có tập cha nào của nó có cùng độ hỗ trợ với nó

g ộ

ập

ợ

Itemset Support

TID 1 2 3 3 4 5

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

Itemset Support {A,B,C} {A,B,D} {A,C,D} {B,C,D} {A,B,C,D}

2 3 2 3 2

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

4 4 5 3 4 4 2 3 3 4 3

Khai Phá Dữ Liệu

Tập mục thường xuyên: lớn nhất vs. đóng (1)

null

TIDs

124

123

245

345

TID

Items

A A

B B

1234 C C

D D

E E

ABC

ABCD

BCE

12

124

24

123

4

2 3 3

24 24

34 34

45 45

AB

AC

AE

BC

BD

BE

CD

CE

DE

ACDE

12

24

2

4

3

4 ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

4

2 ABCD

ABCE

ABDE

ACDE

BCDE

Không được hỗ trợ bởi bất kỳ giao dịch nào

ABCDE

Khai Phá Dữ Liệu

Tập mục thường xuyên: lớn nhất vs. đóng (2)

null

Minsup = 2

Đóng, nhưng không phải là lớn nhất

124

123

245

345 A

B

1234 C

D

E

Đóng và lớn nhất

12

124

24

123

4

2 3 3

24 24

34 34

45 45

AB

AC

AE

BC

BD

BE

CD

CE

DE

12 12

24 24

2 2

4 4

3

4 ABC

ABD

ABE

ACD

ACE

ADE

BCD

BCE

BDE

CDE

# Đóng = 9

4

2 ABCD

ABCE

ABDE

ACDE

BCDE

# Lớn nhất = 4

ABCDE

Khai Phá Dữ Liệu

Tập mục thường xuyên: lớn nhất vs. đóng (3)

(cid:132) Bất kỳ tập mục

thường xuyên lớn nhất nào cũng là tập mục thường xuyên đóng

(cid:132) Cách biểu diễn sử dụng tập mục thường xuyên lớn g nhất không giữ thông tin về độ hỗ trợ của các tập con (của mỗi tập ỗ mục thường xuyên lớn nhất)

Khai Phá Dữ Liệu

Giải thuật FP-Growth

(cid:132) Một phương pháp khác cho việc xác định các tập mục

thường xuyên thường xuyên (cid:137) Nhớ lại: Apriori sử dụng cơ chế sinh-kiểm tra (sinh ra các tập mục cần xét, và kiểm tra xem mỗi tập mục có phải là thường xuyên) xuyên)

(cid:132) FP-Growth biểu diễn dữ liệu của các giao dịch bằng một

cấu trúc dữ liệu gọi là FP tree cấu trúc dữ liệu gọi là FP-tree

(cid:132) FP-Growth sử dụng cấu trúc FP-tree để xác định trực

tiếp các tập mục thường xuyên tiếp các tập mục thường xuyên

Khai Phá Dữ Liệu

Biểu diễn bằng FP-tree

(cid:132) Với mỗi giao dịch, FP-tree xây dựng một đường đi (path)

trong cây trong cây

(cid:132) Hai giao dịch có chứa cùng một số các mục, thì đường đi

của chúng sẽ có phần (đoạn) chung của chúng sẽ có phần (đoạn) chung (cid:137) Càng nhiều các đường đi có các phần chung, thì việc biểu diễn

(cid:132) Nếu kích thước của FP-tree đủ nhỏ để có thể lưu trữ trong bộ nhớ làm việc, thì giải thuật FP-Growth có thể xác định các tập mục thường xuyên trực tiếp từ FP-tree xác định các tập mục thường xuyên trực tiếp từ FP tree lưu trong bộ nhớ (cid:137) Không cần phải lặp lại việc duyệt dữ liệu lưu trên ổ cứng

Khai Phá Dữ Liệu

bằng FP-tree sẽ càng gọn (compressed/compacted)

Xây dựng FP-tree (1)

(cid:132) Ban đầu, FP-tree chỉ chứa duy nhất nút gốc (được biểu

) diễn bởi ký hiệu null)

ý ệ

(cid:132) Cơ sở dữ liệu các giao dịch được duyệt lần thứ 1, để xác

định (tính) độ hỗ trợ của mỗi mục

)

(

(cid:132) Các mục không thường xuyên (infrequent items) bị loại bỏ

(cid:132) Các mục thường xuyên (frequent items) được sắp xếp ên (freq ent items) đ ợc sắp ếp

Các m c th ờng theo thứ tự giảm dần về độ hỗ trợ (cid:137) Trong ví dụ (ở các slides tiếp theo), thứ tự giảm dần về độ hỗ trợ:

(cid:132) Cơ sở dữ liệu các giao dịch được duyệt lần thứ 2, để xây

dựng FP-tree d

FP t

Khai Phá Dữ Liệu

A, B, C, D, E

Xây dựng FP-tree (2)

(Sau khi xét giao dịch thứ 2)

(Sau khi xét giao dịch thứ 1)

null null

A:1 A 1 B:1 B 1 A:1

B:1 B:1 B:1 B:1 C:1 C:1

null D:1

B:1 A:2

C:1 C 1

(Sau khi xét giao dịch thứ 3)

TID 1 2 3 4 5 6 7 8 8 9 10

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

B:1 C:1

D:1

Khai Phá Dữ Liệu

D:1 D 1 E:1

Xây dựng FP-tree (3)

(Sau khi xét giao dịch thứ 10)

Cơ sở dữ liệu các giao dịch dịch

null null

B:2 A:8

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

TID 1 2 3 4 5 6 7 8 9 10

Bảng con trỏ

B:5 C:2 C:1 D:1

Pointer

D:1 C:3 E:1 E:1 D:1

D:1 D:1

ập ụ

Item A A B C D E

Các con trỏ được sử dụng trong q quá trình sinh các tập mục thường xuyên của FP-Growth

Khai Phá Dữ Liệu

E:1 D:1

FP-Growth: Sinh các tập mục thường xuyên

(cid:132) FP-Growth sinh các tập mục thường xuyên trực tiếp từ

FP tree, từ mức lá đến mức gốc (bottom up) FP-tree từ mức lá đến mức gốc (bottom-up) (cid:137) Trong ví dụ trên, FP-Growth trước hết tìm các tập mục thường

(cid:132) Vì mỗi giao dịch được biểu diễn bằng một đường đi trong FP tree, chúng ta có thể xác định các tập mục trong FP-tree, chúng ta có thể xác định các tập mục thường xuyên kết thúc bởi một mục (vd: E), bằng cách duyệt các đường đi chứa mục đó (E) (cid:137) Những đường đi này được xác định dễ dàng bằng các con trỏ t ỏ á đị h dễ dà đi à đ

xuyên kết thúc bởi E… sau đó mới tìm các tập mục thường xuyên kết thúc bởi D… bởi C… bởi B… và bởi A kết thúc bởi D bởi C bởi B và bởi A

bằ á đ ờ

Khai Phá Dữ Liệu

Nhữ gắn với nút đó (vd: E)

Các đường đi kết thúc bởi một mục

(Các g đường đi kết thúc bởi e)

(Các g đường đi kết thúc bởi d)

( (Các đường đi kết thúc bởi c)

( (Các đường đi kết thúc bởi b)

( (Các đường đi kết thúc bởi a)

Khai Phá Dữ Liệu

Xác định các tập mục thường xuyên

(cid:132) FP-Growth tìm tất cả các tập mục thường xuyên kết thúc bởi một mục dựa theo chiến lược chia để trị (divide bởi một mục – dựa theo chiến lược chia để trị (divide- and-conquer) (cid:137) Ví dụ, cần tìm tất cả các tập mục thường xuyên kết thúc bởi e (cid:137) Trước hết, kiểm tra tập mục mức 1 ({e}) có phải là tập mục

ứ 1 ({ }) ó hải là tậ tậ

T ớ hết kiể t thường xuyên

(cid:137) Nếu nó là tập mục thường xuyên, xét các bài toán con: tìm tất cả á tậ các tập mục thường xuyên kết thúc bởi de… bởi ce…bởi be…và à ê kết thú bởi d bởi ae

(cid:137) Mỗi bài toán con nêu trên lại được phân tách thành các bài toán

bởi b th ờ bởi

(cid:137) Kết hợp các lời giải của các bài toán con, chúng ta sẽ thu được

con nhỏ hơn… hỏ h

Khai Phá Dữ Liệu

các tập mục thường xuyên kết thúc bởi e

Vd: Các tập mục thường xuyên kết thúc bởi e

(cid:132) Xác định tất cả các đường đi trong FP tree kết thúc bởi e trong FP-tree kết thúc bởi e (cid:137) Các đường đi tiền tố (prefix paths) đối

(cid:132) Dựa vào các đường đi tiền tố đối với e, xác định độ hỗ trợ của e, bằng cách cộng các giá trị hỗ trợ bằng cách cộng các giá trị hỗ trợ gắn với nút e

Các đường đi tiền tố đối với e

(cid:132) Giả sử minsup=2 thì tập mục {e} (cid:132) Giả sử minsup=2, thì tập mục {e} là tập mục thường xuyên (vì nó có độ hỗ trợ =3 > minsup)

Khai Phá Dữ Liệu

với e

Vd: Các tập mục thường xuyên kết thúc bởi e

(cid:132) Vì {e} là tập mục thường xuyên, nên FP-Growth phải giải quyết các bài toán con: tìm các tập mục thường xuyên quyết các bài toán con: tìm các tập mục thường xuyên kết thúc bởi de…bởi ce…bởi be…và bởi ae

(cid:132) Trước tiên, cần chuyển các đường đi tiền tố của e thành (cid:132) Trước tiên, cần chuyển các đường đi tiền tố của e thành biểu diễn FP-tree có điều kiện (conditional FP-tree) (cid:137) Có cấu trúc tương tự như FP-tree (cid:137) Được dùng để tìm các tập mục thường xuyên kết thúc bởi một ột

ê kết thú bởi á tậ th ờ để tì dù

Khai Phá Dữ Liệu

Đ mục

Xây dựng FP-tree có điều kiện

(cid:132) Cập nhật các giá trị hỗ trợ đối với các

đường đi tiền tố (cid:137) Vì một số giá trị hỗ trợ đã tính đến cả các

(cid:137) Ví dụ: Đường đi null → b:2 → c:2 → e:1 đã tính đến cả giao dịch {b,c} không chứa mục e. Do đó, giá trị hỗ trợ phải gán bằng 1, để thể hiện số lượng các giao dịch chứa {b,c,e}

FP-tree có điều kiện đối với e

(cid:132) Loại bỏ nút e khỏi các đường đi tiền tố (cid:132) Sau khi cập nhật các giá trị hỗ trợ đối với (cid:132) Sau khi cập nhật các giá trị hỗ trợ đối với các đường đi tiền tố, một số mục có thể trở nên không thường xuyên – Bị loại bỏ (cid:137) Vd: Nút b bây giờ có giá trị hỗ trợ =1 (cid:137) Vd: Nút b bây giờ có giá trị hỗ trợ =1

Khai Phá Dữ Liệu

ụ giao dịch không chứa mục e g

Vd: Các tập mục thường xuyên kết thúc bởi e

(cid:132) FP-Growth sử dụng cấu trúc biểu diễn FP-

tree có điều kiện đối với e, để giải quyết các bài toán con: tìm các tập mục thường xuyên kết thúc bởi de…bởi ce…bởi be…và bởi ae

á tậ

th ờ

Vd Để tì (cid:132) Vd: Để tìm các tập mục thường xuyên kết ê kết thúc bởi de, các đường đi tiền tố đối với d được xây dựng từ biểu diễn FP-tree có điều kiện đối với e kiệ đối ới

Các đường đi tiền tố đối với de

(cid:132) Bằng cách cộng với giá trị hỗ trợ gắn với nút d chúng ta xác định được độ hỗ trợ cho tập d, chúng ta xác định được độ hỗ trợ cho tập {d,e} (cid:137) Độ hỗ trợ của {d,e}=2: nó là một tập mục

Khai Phá Dữ Liệu

thường xuyên th ờ ê

Sinh ra các luật kết hợp (1)

(cid:132) Với mỗi tập mục thường xuyên L, cần tìm tất cả các tập f thỏa mãn điều con khác rỗng f ⊂ L sao cho: f → L – f thỏa mãn điều con khác rỗng f ⊂ L sao cho: f → L kiện về độ tin cậy tối thiểu (cid:137) Vd: Với tập mục thường xuyên {A,B,C,D}, các luật

cần xét gồm có: ầ

ồ

ACD →B, BCD →A, C →ABD, D →ABC D →ABC C →ABD

ABC →D, ABD →C, A →BCD, B →ACD, B →ACD A →BCD AB →CD, AC → BD, AD → BC, BC →AD, BD →AC, CD →AB,

(cid:132) Nếu |L| = k, thì sẽ phải xét (2k – 2) các luật kết hợp có

thể (bỏ qua 2 luật: L → ∅ và ∅ → L) thể (bỏ qua 2 luật: L → ∅ và ∅ → L)

Khai Phá Dữ Liệu