Bài giảng Khai phá dữ liệu: Chương 3 - Phan Mạnh Thường

Kết cấu chương 3 Episodes và luật Episode thuộc bài giảng Khai phá dữ liệu trình bày về khái niệm cơ bản về Episodes và luật Episode, thuật toán Winepi, thuật toán Minepi và cuối cùng là bài tập ôn tập và củng cố kiến thức đã học.
Nội dung trích xuất từ tài liệu:
Bài giảng Khai phá dữ liệu: Chương 3 - Phan Mạnh Thường Chương 3 Episodes và luật Episode Nội dung1 Khái niệm cơ bản2 Thuật toán Winepi3 Thuật toán Minepi4 Bài tập Chương 3 Episodes và luật Episode CÁC KHÁI NIỆM CƠ BẢ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 Episode 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” Chương 3 Episodes và luật Episode CÁC KHÁI NIỆM CƠ BẢN 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 Chương 3 Episodes và luật Episode CÁC KHÁI NIỆM CƠ BẢN  Ví dụ chuỗi dữ liệu tín hiệu 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 : – 10…150 là các thời điểm xảy ra sự kiện – s =  (D, 10), (C, 20), …, (A, 150)  – A, B, C và D là các loại sự kiện (ở đây là tín hiệu báo động) – Ts (thời điểm bắt đầu) = 10 and Te (thời điểm kết thúc) = 150 Chương 3 Episodes và luật Episode CÁC KHÁI NIỆM CƠ 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 đó. Chương 3 Episodes và luật Episode CÁC KHÁI NIỆM CƠ BẢN 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ự) Chương 3 Episodes và luật EpisodeCÁC KHÁI NIỆM CƠ BẢN 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 Chương 3 Episodes và luật Episode THUẬT TOÁN WINEPI 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 Chương 3 Episodes và luật Episode THUẬT TOÁN WINEPI Ví dụ chuỗi dữ liệu tín hiệu 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ửa sổ là 40 giây• Cửa sổ đầu/cuối chỉ chứa sự kiện đầu/cuối Chương 3 Episodes và luật Episode THUẬT TOÁN WINEPI 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 Chương 3 Episodes và luật Episode THUẬT TOÁN WINEPI Cửa sổ trên chuỗi sự 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 ts W te tn Chương 3 Episodes và luật Episode THUẬT TOÁ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 t te1 t2 t3 tnts W te Chương 3 Episodes và luật Episode THUẬT TOÁ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 Chương 3 Episodes và luật Episode THUẬT TOÁ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á ngưỡ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 Chương 3 Episodes và luật Episode THUẬT TOÁN WINEPI 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  ...