Bài giảng Khai phá dữ liệu - Bài 3: Episodes and luật Episode - Văn Thế Thành

1Chuyên đề khai phá dữ liệu 1 Bài 3 Episodes and luật Episode Chuyên đề khai phá dữ liệu 2 • Luật kết hợp mô tả các sự kiện xuất hiện cùng nhau trong dữ liệu – Ví dụ: "IF một tín hiệu báo động (alarm) có các tính chất nào đó THEN nó sẽ có các tính chất xác định khác. • Các luật Episode mô tả quan hệ thời gian giữa các sự vật – Ví dụ: IF một tổ hợp các tín hiệu báo nguy xảy ra trong một khoảng thời gian THEN sẽ có một tổ hợp các tính hiệu báo nguy khác sẽ xảy ra trong một khoảng thời gian xác định khác" Các khái niệm cơ bản Chuyên đề khai phá dữ liệu 3 Cơ sở • Dữ liệu telecom bao gồm các tín hiệu báo động: 1234 EL1 PCM 940926082623 A1 ALARMTEXT.. • Bây giờ chúng ta sẽ quên các quan hệ giữa các thuộc tính trong tín hiệu báo động (luật kết hợp) • Chúng ta chỉ xét các thuộc tính số hiệu tín hiệu báo động , xử lý nó như là loại biến cố/tín hiệu báo động và xem xét các quan hệ giữa các biến cố/tín hiệu báo động. Alarm number Alarming network element Alarm type Date, time Alarm severity class 2Chuyên đề khai phá dữ liệu 4 • Dữ liệu: – Dữ liệu là tập R các biến cố – Mỗi biến cố là một cặp (A, t), với • A ∈ R là loại biến cố (ví dụ loại tín hiệu báo động ) • t là một số nguyên xác định thời điểm xuất hiện của biến cố – Các chuỗi biến cố s trên R là bộ ba (s, Ts, Te) • Ts là thời điểm bắt đầu và Te là thời điểm kết thúc • Ts < Te là các số nguyên • s = 〈 (A1, t1), (A2, t2), , (An, tn) 〉 • Ai ∈ R và Ts ≤ ti < Te với mọi i=1, , n Các khái niệm cơ bản Chuyên đề khai phá dữ liệu 5 • Ví dụ chuỗi dữ liệu tín hiệu báo động: Các khái niệm cơ bản • Với: – A, B, C và D là các loại sự kiện (ở đây là tín hiệu báo động) – 10150 là các thời điểm xảy ra – s = 〈 (D, 10), (C, 20), , (A, 150) 〉 – Ts (thời điểm bắt đầu) = 10 and Te (thời điểm kết thúc) = 150 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 D C A B D A B C A D C A B D A Chuyên đề khai phá dữ liệu 6 • Episodes: – Episode là cặp (V, ≤) • V là tập hợp các loại sự kiện,ví dụ loại tín hiệu báo động • ≤ là thứ tự riêng phần trên V – Cho chuỗi S các tín hiệu báo động, episode α = (V, ≤) xảy ra trong phạm vi S nếu có cách thỏa loại sự kiện (ví dụ loại tín hiệu báo động) trong V dùng các tín hiệu báo động của S để thứ tự riêng phần ≤ được tôn trọng – Nhận xét: episodes chứa các tín hiệu báo động có các tính chất nào đó và xày ra theo một thứ tự riêng phần nào đó. Các khái niệm cơ bản 3Chuyên đề khai phá dữ liệu 7 • Các thứ tự riêng phần phổ dụng như: – Thứ tự toàn phần • Các vị từ của mỗi episode có thứ tự cố định • Các episodes như vậy được gọi là tuần tự (hay “có thứ tự") – Các thứ tự riêng phần hiển nhiên • Không xét trật tự của các vị từ • Các episodes này được gọi là song song (hay “không có thứ tự") Các khái niệm cơ bản Chuyên đề khai phá dữ liệu 8 • Ví dụ: Các khái niệm cơ bản A B Episode tuần tự A B Episode song song A B C Episode vừa tuần tự vừa song song Chuyên đề khai phá dữ liệu 9 • Tên của phương pháp WINEPI xuất phát từ kỹ thuật dùng cửa số truợt • Nhận xét: – Cửa sổ được trượt qua chuỗi dữ liệu các sự kiện – Mỗi cửa sổ là một “khung ảnh" giống như một dòng của CSDL – Tập các “khung ảnh" tạo thành các dòng của CSDL Tiếp cận WINEPI 4Chuyên đề khai phá dữ liệu 10 • Ví dụ chuỗi dữ liệu tín hiệu báo động: Tiếp cận WINEPI 0 10 20 30 40 50 60 70 80 90 D C A B D A B C • Bề rộng cửa sổ là 40 giây • Cửa sổ đầu/cuối chỉ chứa sự kiện đầu/cuối Chuyên đề khai phá dữ liệu 11 • Cho tập E các loại sự kiện, chuỗi sự kiện S = (s,Ts,Te) là một chuỗi có thứ tự các sự kiện eventi sao cho eventi ≤ eventi+1 với mọi i=1, , n-1, và Ts ≤ eventi < Te với mọi i=1, , n Tiếp cận WINEPI Ts Te t1 t2 t3 tn event1 event2 event3 eventn Chuyên đề khai phá dữ liệu 12 • Cửa sổ trên chuỗi sự kiện S là chuỗi sự kiện S=(w,ts,te), với ts Ts, và w chứa các cặp (event, t) của s mà ts ≤ t < te • Giá trị ts ≤ t < te được gọi là bề rộng cửa sổ W Tiếp cận WINEPI Ts Te t1 t2 t3 tn event1 event2 event3 eventn Wts te 5Chuyên đề khai phá dữ liệu 13 • Theo định nghĩa, cửa sổ đầu và cuối trên chuỗi vuơn ra ngoài chuỗi, do vậy cửa sổ đầu tiên chỉ chứa thời điểm đầu và cửa sổ cuối cùng chỉ chứa thời điểm cuối Tiếp cận WINEPI Wts te Ts Te t1 t2 t3 tn event1 event2 event3 eventn Wts te Chuyên đề khai phá dữ liệu 14 • Tần suất (độ hỗ trợ với luật kết hợp) của episode α là tỷ số giữa các cửa số có xuất hiện với tổng sổ các cửa sổ khả dĩ. |Sw ∈ W(S, W) | α xuất hiện trong Sw |fr(α, S, W) = |W(S, W)| Với W(S, W) là tập tất cả các cửa số Sw của chuỗi S sao cho bề rộng cửa sổ là W Tiếp cận WINEPI Chuyên đề khai phá dữ liệu 15 • Khi tìm episodes cần sử dụng một ngưỡng tần suât min_fr • Episode α là phổ biến nếu fr(α, s, win) ≥ min_fr, ví dụ, “nếu tần suất của α vượt quá nguỡng tần suất nhỏ nhất trong phạm vi chuỗi dữ liệu s và với bề rộng cửa sổ win" • F(s, win, min_fr): tập hợp các episodes phổ biến trong s ứng với win và min_fr • Meo Apriori: Nếu episode α là phổ biến trong chuỗi sự kiện s, thì tất cả các episodes con β ≺ α là phổ biến Tiếp cận WINEPI 6Chuyên đề khai phá dữ liệu 16 • Luật episode rule là biểu thức β⇒ γ, với β và γ là các episodes sao cho β là episode con của γ • Episode β là episode con của γ (β ≺ γ), nếu đồ thị biểu diễn β là đồ thị con của đồ thị biểu diễn γ Tiếp cận WINEPI A B β: A B Cγ: Chuyên đề khai phá dữ liệu 17 • Phân số fr(γ, S, W) = tần suất của toàn bộ episode fr(β, S, W) = tần suất của episode về trái là độ tin cậy của luật WINEPI episode • Độ tin cậy được xem như xác suất điều kiện của toàn bộ của γ xảy ra trong cửa sổ khi cho trước β xảy ra trong cửa sổ đó. Tiếp cận WINEPI Chuyên đề khai phá dữ liệu 18 • Nhận xét: – Các luật WINEPI giống luật kết hợp nhưng có thêm yếu tố thời gian: Nếu sự kiện (tín hiệu báo động) thỏa về trái của luật xuất hiện theo thứ tự bên phải trong phạm vi W đơn vị thời gian, thì cũng xuất hiện trong phần kết luận (vế phải ) xuất hiện trong vị trí được mô tả bởi quan hệ thứ tự ≤, trong phạm vi W đơn vị thời gian. phần thân⇒ kết luận [bề rộng cửa sổ ] (f, c) Tiếp cận WINEPI 7Chuyên đề khai phá dữ liệu 19 • Input: Tập R các loại sự kiện/th báo động , chuỗi sự kiện s trên R, tập E các episodes, bề rộng cửa sổ win, và nguỡng tần suất min_fr • Output: Tập hợp F(s, win, min_fr) • Method: 1. Tính C1 := {α ∈ E | |α| = 1}; 2. i := 1; 3. while Ci≠ ∅ do 4.(* Tính F(s, win, min_fr) := {α ∈ Ci | fr(α, s, win) ≥ min_fr}; 5. i := l+1; 6.(** Tính Ci:= {α ∈ E | |α| = I, and β ∈ F|β |(s, win, min_fr) for all β ∈ E, β ≺ α}; (* = quét database , (** tạo ứng viên Thuật toán WINEPI Chuyên đề khai phá dữ liệu 20 • Bài toán đầu tiên: cho chuỗi và episode, xác định episode có xuất hiện trong chuỗi. • Tìm số các cửa sổ có episode xuất hiện • Các cửa sổ liền nhau có nhiều phần chung • Cách xử lý? – Thuật toán tăng cường (incremental algorithm) – Giống ý tưởng luật kết hợp – Episode ứng viên là tổ hợp của hai episodes có kích thước nhỏ hơn – Các episodes song song, episodes tuân tự Thuật toán WINEPI Chuyên đề khai phá dữ liệu 21 • Các episodes song song: – Đối với ứng viên α có biến đếm α.event_count cho biết α xuất hiện bao nhiên lần trong cửa sổ – Khi α.event_count bằng |α|, thì α hoàn toàn năm trong cửa sổ, lưu thời điểm bắt đầu của cửa sổ trong α.inwindow – Khi .event_count giảm trở lại, hãy tăng trường α.freq_count bằng số cửa sổ với α vẫn giữ nguyên toần bộ trong cửa sổ – Các episodes tuần tự : dùng automata trạng thái. Thuật toán WINEPI 8Chuyên đề khai phá dữ liệu 22 • Ví dụ chuỗi dữ liệu tín hiệu báo động: Tiếp cận WINEPI 0 10 20 30 40 50 60 70 80 90 D C A B D A B C • Bề rộng cửa sổ là 40 giây, buớc di chuyển là 10 giây • Chiều dài của chuỗi là 70 giây (10-80) Chuyên đề khai phá dữ liệu 23 • Bằng cách trượt cửa sổ, chúng ta có 11 cửa sổ (U1-U11): Tiếp cận WINEPI 0 10 20 30 40 50 60 70 80 90 D C A B D A B C • Nguỡng tần số được ấn định là 40%, ví dụ episode xảy ra tối thiểu trong 5 của 11 cửa sổ. U1 U2 U11 Chuyên đề khai phá dữ liệu 24 WINEPI Approach 9Chuyên đề khai phá dữ liệu 25 • Giả sử cần tìm tất cả các episodes song song: – Đầu tiên, tạo singletons, ví dụ episodes song song có kích thuớc là 1 (A, B, C, D) – Tiếp đến nhận dạng các singletons phổ biến(ở dây là tất cả ) – Từ các episodes phổ biến này, tạo các episodes ứng viên có kích thước là 2: AB, AC, AD, BC, BD, CD – Tiếp đến nhận dạng các episodes song song phổ biến(ở đây là tất cả) – Từ các episodes phổ biến này, tạo các episodes phổ biến có kích thước là 3: ABC, ABD, ACD, BCD – Khi nhận dạng các episodes phổ biến, chỉ có ABD xuất hiện trong hơn 4 cửa sổ – Không có episodes ứng viên có kích thước là 4. Tiếp cận WINEPI Chuyên đề khai phá dữ liệu 26 • Tần suất Episode và các luật ví dụ với WINEPI: D : 73% C : 73% A : 64% B : 64% D ⇒ A [40] (55%, 75%) D C : 45% D A : 55% D B : 45% D A ⇒ B [40] (45%, 82%) C A : 45% C B : 45% A B : 45% D A B : 45% Tiếp cận WINEPI Chuyên đề khai phá dữ liệu 27 • Một cách tiếp cận khác để khám phá episodes – Không dùng cửa sổ trượt – Đối với từng episode quan tâm tiền năng, tìm số lần xuất hiện chính xác của episode. • Các tiên lợi: dễ sửa đổi các giới hạn thời gian, nhiều giới hạn thời gian cho một luật : “Nếu A và B xảy ra trogn phạm vi 15 giây, thì C sẽ theo sau trong phạm vi 30 giây" • Bất tiện: dùng nhiều khoảng trống Tiếp cận MINEPI 10 Chuyên đề khai phá dữ liệu 28 • Cho episode α và chuỗi sự kiện S, khoảng [ts,te] là xuất hiện nhỏ nhất α của S, – Nếu α xảy ra trong cửa sổ ứng với khoảng – Nếu α không xảy ra trong bất kỳ khoảng con đúng nào • Tập các xuất hiện nhỏ nhất của episode α trong một chuỗi sự kiện cho trước được ký hiệu là mo(α): mo(α) = { [ts,te] | [ts,te] là sự xuất hiện nhỏ nhất của α } Tiếp cận MINEPI Chuyên đề khai phá dữ liệu 29 • Ví dụ: Episode song song β chứa các loại sự kiện A và B có ba lần xuất hiện nhỏ nhất trong s là : {[30,40], [40,60], [60,70]}, α có một lần xuất hiện trong s là : {[60,80]} Tiếp cận MINEPI D C A B D A B C 0 10 20 30 40 50 60 70 80 90 A B A B Cβ: α : Chuyên đề khai phá dữ liệu 30 • Luật Episode MINEPI cho xác suất điều kiện để tổ hợp các sự kiện ( tín hiệu báo động) xảy ra trong một thời khoảng khi cho trước tổ hợp khác các sự kiện khác đã xuất hiện trong thời khoảng • Luật episode là β [win1] ⇒ α [win2] • β và α là các episodes sao cho β ≺ α (β là episode con của α) • Nếu episode β có xuất hiện nhỏ nhất trong khoảng [ts,te] với te - ts ≤ win1, thì episode α xảy ra trong khoảng [ts,t'e] ứng với vài t'e sao cho t'e - ts ≤ win2 Tiếp cận MINEPI 11 Chuyên đề khai phá dữ liệu 31 • Độ tin cậy của luật β [win1] ⇒ α [win2] là xác suất điều kiện để α xảy ra khi cho trước β xảy ra, dưới các ràng buộc thời gian được chỉ định bởi các luật: |mo(α)| / |mo(β)| với |mo(β)| là số các xuất hiện nhỏ nhất [ts,te] của β sao cho te - ts ≤ win1 và |mo(α)| là số các xuất hiện như thế và cũng có một xuất hiện của α trong phạm vi khoảng [ts,ts+win2] Tiếp cận MINEPI Chuyên đề khai phá dữ liệu 32 • Tần suất của luật β [win1] ⇒ α [win2] là |mo(α)|, với số lần luật thỏa trong CSDL • Xét ví dụ: – Bài toán: tìm tất cả các episodes tuần tự bằng cách dùng thời khoảng cực đại là 40 giây và kích thuớc cửa sổ là 10, 20, 30 and 40 giây Ngưỡng tần suất được gán cho một lần xuất hiện. Tiếp cận MINEPI D C A B D A B C 0 10 20 30 40 50 60 70 80 90 Chuyên đề khai phá dữ liệu 33 • Tìm tất cả các episodes tuần tự (1/3): – Đầu tiên, tạo singletons, ví dụ episodes có kích thước là 1 (A, B, C, D) – Trong khi tạo singletons, chúng ta cũng tạo bảng xuất hiện cho chúng. Sau lần quét CSDL đầu tiên, chúng ta không cần quét CSDL nữa mà dùng các bảng đảo ngược được tạo lập. – Sau đó, nhận dạng các singletons phổ biến(với ví dụ này là tất cả) – Từ các episodes phổ biến này, tạo các episodes ứng viên có kích thước là 2: AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD, DC Tiếp cận MINEPI 12 Chuyên đề khai phá dữ liệu 34 • Tìm tất cả các episodes tuần tự(2/3): – Sau đó, dùng bảng đảo ngược để tạo xuất hiện nhỏ nhất cho các ứng viên ví dụ cho AB nhận tất cả các episodes con, có tên là A và B, rồi tính mo(AB) như sau: • Đọc xuất hiện đầu tiên của A (30-30), và tìm xuất hiện đầu tiên theo sau B (40-40) • Sau đó lấy xuất hiện thứ hai của A (60-60) và tìm xuất hiện đầu tiên sau B (70-70) • Rồi tiếp tục với BA Tiếp cận MINEPI Chuyên đề khai phá dữ liệu 35 • Tìm tất cả các episodes tuần tự(3/3): – Trong giai đoạn nhận dạng, chúng ta tìm tất cảc episodes phổ biến và tạo các episodes ứng viên có kích thước 3. Lần nữa, hầu như tất cả các ứng viên đều phổ biến. – Cuối cùng, thủ tục tương tự được lặp cho các ứng viên có kích thước là 4 và tìmn được các episodes xảy ra là DCAB trong 10-40, DABC trong 50-80, CABD trong 20-50, CBDA trong 20-60, và BDAC trong 40-80 – Không tìm thất các ứng viên có kích thước 5, do vậy thuật toán kích thước. Tiếp cận MINEPI Chuyên đề khai phá dữ liệu 36 MINEPI Approach Các xuất hiện (tuần tự ) tối thiểu + các tần suất trong dữ liệu ví dụ 13 Chuyên đề khai phá dữ liệu 37 IF D THEN C WITH [0] [10] 0.00 (0/2) [0] [20] 0.50 (1/2) [0] [40] 1.00 (2/2) IF D THEN A C WITH [0] [10] 0.00 (0/2) [0] [40] 0.50 (1/2) Tiếp cận MINEPI IF D A THEN C WITH [40] [40] 0.50 (1/2) [20] [40] 1.00 (1/1) IF D C THEN A B WITH [40] [40] 0.50 (1/2) [30] [40] 1.00 (1/1) Chuyên đề khai phá dữ liệu 38 IF D A B THEN C WITH [40] [40] 0.50 (1/2) [30] [40] 1.00 (1/1) Tiếp cận MINEPI • Dưới đây là xuất hiện tối thiểu của các luật ví dụ trong dữ liệu ví dụ: D C A B D A B C 0 10 20 30 40 50 60 70 80 90 DC DAB, DCAB DC, DAC, DABC DA DA DAB Chuyên đề khai phá dữ liệu 39 • Khai phá luật Episode: – Dựa trên kỹ thuật luật kết hợp – Dữ liệu hướng thời gian • Hai cách tiếp cận: – WINEPI với cửa sổ trượt – MINEPI với việc tìm sự xuất hiện nhỏ nhất • Các tiếp cận được dùng cho các mục tiêu khác nhau • Cần nghiên cứu thêm – Bài toán khám phá mẫu tuần tự (sequential pattern mining ) – Thuật toán tăng cường cho bài toán sequential pattern mining Kết luận