zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Khai phá dữ liệu: Bài 3 - Văn Thế Thành

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:13

Báo xấu

46
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Khai phá dữ liệu - Bài 3: Episodes và luật Episode" giới thiệu tới người đọc các khái niệm cơ bản, cơ sở Episodes, tiếp cận WINEPI, thuật toán WINEPI, tiếp cận MINEPI. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khai phá dữ liệu: Bài 3 - Văn Thế Thành

Bài 3 Episodes and luậ luật Episode Chuyên đề đề khai phá phá dữ liệ liệu 1 Các khá niệm cơ bả khái niệ bản Luật kế • Luậ kết hợ hợp mô tảtả các sự sự kiệ kiện xuấ xuất hiệ hiện cù cùng nhau dữ liệ 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. luật Episode mô tả • Các luậ tả quan hệhệ thờ thời gian giữ giữa cá sự 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" Chuyên đề đề khai phá phá dữ liệ liệu 2 Cơ sở sở • Dữ liệ liệu telecom bao gồ gồm cá các tí hiệu bá tín hiệ báo độ động: ng: 1234 EL1 PCM 940926082623 A1 ALARMTEXT.. Alarm type Date, time Alarm severity class Alarming network element Alarm number giờ chú • Bây giờ sẽ quên cá chúng ta sẽ hệ giữ các quan hệ giữa cá thuộc các thuộ tính trong tí hiệu bá tín hiệ báo độ động (luậ (luật kế kết hợ hợp) • Chú chỉ xét cá Chúng ta chỉ thuộc tí các thuộ số hiệ tính số hiệu tí hiệu bá tín hiệ báo độ động xử lý nó , xử nó như là loại biế là loạ biến cố cố/tí hiệu bá /tín hiệ báo độ động và và xem xét các quan hệhệ giữ giữa cá biến cố các biế cố/tí hiệu bá /tín hiệ báo độ động. Chuyên đề đề khai phá phá dữ liệ liệu 3 1
Các khá niệm cơ bả khái niệ bản • Dữ liệ 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 Chuyên đề đề khai phá phá dữ liệ liệu 4 Các khá niệm cơ bả khái niệ bản • Ví dụ chuỗ chuỗi dữ dữ liệ liệu tí hiệu bá tín hiệ báo độ động: D C A B D A B C A D C A B D A 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 • Với: – A, B, C và D là các loại sự kiện (ở đây là tín hiệu báo động) – 10…150 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 Chuyên đề đề khai phá phá dữ liệ liệu 5 Các khá niệm cơ bả khái niệ bản • 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 đó. Chuyên đề đề khai phá phá dữ liệ liệu 6 2
Các khá niệm cơ bả khái niệ bản thứ tự riêng phầ • Các thứ phần phổ phổ dụng như: như: Thứ tự toà – Thứ phần toàn phầ • 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ự") Chuyên đề đề khai phá phá dữ liệ liệu 7 Các khá niệm cơ bả khái niệ bản • Ví dụ: A B A A C B B Episode Episode Episode vừa tuần tuần tự song song tự vừa song song Chuyên đề đề khai phá phá dữ liệ liệu 8 Tiếp cậ cận WINEPI của phương phá • Tên củ pháp WINEPI xuấ xuất phá từ phát từ kỹ thuậ thuật dù cửa số dùng cử số truợ truợt Nhận xé • Nhậ 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 Chuyên đề đề khai phá phá dữ liệ liệu 9 3
Tiếp cậ cận WINEPI • Ví dụ chuỗ chuỗi dữ dữ liệ liệu tí hiệu bá tín hiệ báo độ động: D C A B D A B C 0 10 20 30 40 50 60 70 80 90 • Bề rộng cử cửa sổ sổ là 40 giây • Cửa sổ sổ đầ đầu/cuố u/cuối chỉ chỉ chứ chứa sự sự kiệ kiện đầ đầu/cuố u/cuối Chuyên đề đề khai phá phá dữ liệ liệu 10 Tiếp cậ cận WINEPI • Cho tập E các loại sự kiện, chuỗi sự kiện S = (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 event1 event2 event3 … … eventn Ts Te t1 t2 t3 … … tn Chuyên đề đề khai phá phá dữ liệ liệu 11 Tiếp cậ cận WINEPI • Cửa sổsổ trên chuỗ chuỗi sự sự kiệ kiện S là chuỗi sự kiện S=(w,ts,te), với ts < Te, te > 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 event1 event2 event3 … … eventn Ts Te t1 t2 t3 tn ts W te Chuyên đề đề khai phá phá dữ liệ liệu 12 4
Tiếp cậ cận WINEPI • 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 event1 event2 event3 … … eventn Ts Te ts W tte1 t2 t3 ttns W te Chuyên đề đề khai phá phá dữ liệ liệu 13 Tiếp cậ cận WINEPI • 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 Chuyên đề đề khai phá phá dữ liệ liệu 14 Tiếp cậ cận WINEPI • 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 Chuyên đề đề khai phá phá dữ liệ liệu 15 5
Tiếp cậ cận WINEPI Luật episode rule là biểu thức β ⇒ γ, với β và γ là các episodes sao • Luậ 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 γ A A β: γ: C B B Chuyên đề đề khai phá phá dữ liệ liệu 16 Tiếp cậ cận WINEPI • 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ổ đó. Chuyên đề đề khai phá phá dữ liệ liệu 17 Tiếp cậ cận WINEPI Nhận xé • Nhậ 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ậ luận [bề [bề rộng cử cửa sổ sổ ] (f, c) Chuyên đề đề khai phá phá dữ liệ liệu 18 6
Thuật toá toán WINEPI Input Tập R các loại sự kiện/th báo động , chuỗi sự kiện s trên R, • Input: 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) • Output: • Method: 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 Chuyên đề đề khai phá phá dữ liệ liệu 19 Thuật toá toán WINEPI • 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ự Chuyên đề đề khai phá phá dữ liệ liệu 20 Thuật toá toán WINEPI • 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ổ tuần tự – Các episodes tuầ tự : dù dùng automata trạtrạng thá thái. Chuyên đề đề khai phá phá dữ liệ liệu 21 7
Tiếp cậ cận WINEPI • Ví dụ chuỗ chuỗi dữ dữ liệ liệu tí hiệu bá tín hiệ báo độ động: D C A B D A B C 0 10 20 30 40 50 60 70 80 90 • Bề rộng cử cửa sổ sổ là 40 giây, buớ buớc di chuyể chuyển là là 10 giây • Chiều dà Chiề của chuỗ dài củ chuỗi là là 70 giây (10- (10-80) Chuyên đề đề khai phá phá dữ liệ liệu 22 Tiếp cậ cận WINEPI • Bằng cá trượt cử cách trượ cửa sổ sổ, chú chúng ta có cửa sổ có 11 cử sổ (U1-U11): … U2 U1 U11 D C A B D A B C 0 10 20 30 40 50 60 70 80 90 Nguỡng tầ • Nguỡ tần số số đượ được ấn đị định là ví dụ episode xả là 40%, ví xảy ra tố tối thiểu trong 5 củ thiể của 11 cử cửa sổ sổ. Chuyên đề đề khai phá phá dữ liệ liệu 23 WINEPI Approach Chuyên đề đề khai phá phá dữ liệ liệu 24 8
Tiếp cậ cận WINEPI • Giả sử cần tì tất cả tìm 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. Chuyên đề đề khai phá phá dữ liệ liệu 25 Tiếp cậ cận WINEPI • Tần suấ suất Episode và luật ví và các luậ ví dụ với WINEPI: D : 73% C : 73% A : 64% B : 64% D ⇒ A [40] (55%, 75%) DC : 45% DA : 55% DB : 45% D A ⇒ B [40] (45%, 82%) CA : 45% CB : 45% AB : 45% DAB : 45% Chuyên đề đề khai phá phá dữ liệ liệu 26 Tiếp cậ cận MINEPI • Một cá tiếp cậ cách tiế cận khá khác để để khá khám phá 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. lợi: dễ sửa đổi các giới hạn thời gian, nhiều giới • Các tiên lợ 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ệ tiện: dùng nhiều khoảng trống Chuyên đề đề khai phá phá dữ liệ liệu 27 9
Tiếp cậ cận MINEPI • 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 α } Chuyên đề đề khai phá phá dữ liệ liệu 28 Tiếp cậ cận MINEPI • 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]} A A β: α: C B B D C A B D A B C 0 10 20 30 40 50 60 70 80 90 Chuyên đề đề khai phá phá dữ liệ liệu 29 Tiếp cậ cận MINEPI • 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à 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 Chuyên đề đề khai phá phá dữ liệ liệu 30 10
Tiếp cậ cận MINEPI • Độ 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] Chuyên đề đề khai phá phá dữ liệ liệu 31 Tiếp cậ cận MINEPI • Tần suất của luật β [win1] ⇒ α [win2] là |mo(α)|, với số lần luật thỏa trong CSDL ví dụ: • Xét ví – 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. D C A B D A B C 0 10 20 30 40 50 60 70 80 90 Chuyên đề đề khai phá phá dữ liệ liệu 32 Tiếp cậ cận MINEPI • Tìm tất cả cả các episodes tuần tự 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 Chuyên đề đề khai phá phá dữ liệ liệu 33 11
Tiếp cậ cận MINEPI tất cả • Tìm tấ cả các episodes tuầ tuần tự 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 Chuyên đề đề khai phá phá dữ liệ liệu 34 Tiếp cậ cận MINEPI tất cả • Tìm tấ cả các episodes tuầ tuần tự 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. Chuyên đề đề khai phá phá dữ liệ liệu 35 xuất hiệ Các xuấ hiện (tuầ (tuần tự tự ) tố tối thiể thiểu tần suấ suất trong dữ dữ liệ liệu ví ví dụ MINEPI Approach + cá các tầ Chuyên đề đề khai phá phá dữ liệ liệu 36 12
Tiếp cậ cận MINEPI IF D IF D THEN C A WITH [0] [10] 0.00 (0/2) THEN C [0] [20] 0.50 (1/2) WITH [40] [40] 0.50 (1/2) [0] [40] 1.00 (2/2) [20] [40] 1.00 (1/1) IF D IF D THEN A C C THEN A WITH [0] [10] 0.00 (0/2) B [0] [40] 0.50 (1/2) WITH [40] [40] 0.50 (1/2) [30] [40] 1.00 (1/1) Chuyên đề đề khai phá phá dữ liệ liệu 37 Tiếp cậ cận MINEPI • Dưới đây là xuất hiện tối IF D A thiểu của các luật ví dụ trong B dữ liệu ví dụ: THEN C DAB, DCAB WITH [40] [40] 0.50 (1/2) DC DC, DAC, DABC [30] [40] 1.00 (1/1) D C A B D A B C 0 10 20 30 40 50 60 70 80 90 DA DA DAB Chuyên đề đề khai phá phá dữ liệ liệu 38 Kết luậ luận • Khai phá luật Episode: phá luậ – Dựa trên kỹ thuật luật kết hợp – Dữ liệu hướng thời gian • Hai cá tiếp cậ cách tiế 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 • tiếp cậ Các tiế cận đượ được dù dùng cho cá mục tiêu khá các mụ khác nhau • Cần nghiên cứ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 Chuyên đề đề khai phá phá dữ liệ liệu 39 13

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.