Khai phá dữ liệu - Chương 3: Dãy phổ biến

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 khách hàng mua sản phẩm A với số lượng 10 THEN sẽ mua sản phẩm B với số lượng 20.Các luật dãy phổ biến mô tả quan hệ thời gian giữa các sự kiệnVí dụ: IF hôm nay khách hàng mua sản phẩm A THEN sau 1 tuần khách hàng sẽ mua tiếp sản phẩm B và C”Tập R các loại sự kiện.Mỗi sự kiện là một cặp (A, t), với A  R là loại sự kiện (ví dụ loại...
Nội dung trích xuất từ tài liệu:
Khai phá dữ liệu - Chương 3: Dãy phổ biếnChương 3:Dãy phổ biến 1Chương 3: Dãy phổ biến 1. CÁC KHÁI NiỆM CƠ BẢNLuậ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 khách hàng mua sản phẩm A với số lượng 10 THEN sẽ mua sản phẩm B với số lượng 20.Các luật dãy phổ biến mô tả quan hệ thời gian giữa các sự kiện – Ví dụ: IF hôm nay khách hàng mua sản phẩm A THEN sau 1 tuần khách hàng sẽ mua tiếp sản phẩm B và C” 21. CÁC KHÁI NiỆM CƠ BẢN (tt) – Tập R các loại sự kiện. – Mỗi sự kiện là một cặp (A, t), với • A ∈ R là loại sự kiện (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 sự kiện – Chuỗi sự kiện 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` 31. CÁC KHÁI NIỆM CƠ BẢN (tt) Ví dụ chuỗi sự kiện: 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 • Trong đó: – A, B, C, D: là các loại sự kiện – 10…150 là các thời điểm xảy ra sự kiện – 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 42. DÃY PHỔ BiẾN TRONG MỘT CHUỖI (Episode)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 sự kiện, episode α = (V, ≤ ) xảy ra trong phạm vi S nếu các loại sự kiện trong V xuất hiện trong S theo thứ tự được xác định bằng quan hệ thứ tự. 5 2. DÃY PHỔ BiẾN TRONG MỘT CHUỖI (Episode)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ự) 62. DÃY PHỔ BiẾN TRONG MỘT CHUỖI (Episode) Ví dụ: A B A A C B B Episode Episode Episode vừa tuần tự tuần tự song song vừa song song 7 3. THUẬT TOÁN WINEPITên của phương pháp WINEPI xuất phát từ kỹ thuật dùng cửa sổ truợtNhậ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 83. THUẬT TOÁN WINEPI (tt)Ví dụ chuỗi dữ liệu sự kiện: D C A B D A B C 0 10 20 30 40 50 60 70 80 90• 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 9 3. THUẬT TOÁN WINEPI (tt)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 event1 event2 event3 … … eventn Ts Te t1 t2 t3 … … tn 10 3. THUẬT TOÁN WINEPI (tt)Cửa sổ trên chuỗi sự kiện S là chuỗi sự kiện Sw=(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 < teGiá trị ts ≤ t < te được gọi là bề rộng cửa sổ W event1 event2 event3 … … eventn Ts Te t1 t2 t3 ts W te t n 11 3. THUẬT TOÁN WINEPI (tt)Theo định nghĩa, cửa sổ đầu và cuối trên chuỗi có thể 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 te t1 t2 t3 tn ts W te 12 3. THUẬT TOÁN WINEPI (tt)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ĩ. ...