Bài giảng Một số chủ đề hiện đại về khai phá dữ liệu - khai phá quá trình: Chương 3 - PGS.TS. Hà Quang Thụy

Bài giảng Một số chủ đề hiện đại về khai phá dữ liệu - khai phá quá trình: Chương 3 do PGS.TS. Hà Quang Thụy thực hiện sau đây nhằm trang bị cho các bạn những kiến thức về phát hiện quy trình. Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích.
Nội dung trích xuất từ tài liệu:
Bài giảng Một số chủ đề hiện đại về khai phá dữ liệu - khai phá quá trình: Chương 3 - PGS.TS. Hà Quang ThụyBÀI GIẢNG MỘT SỐ CHỦ ĐỀ HIỆN ĐẠI VỀ KHAI PHÁ DỮ LIỆU: KHAI PHÁ QUÁ TRÌNH CHƯƠNG 3. PHÁT HIỆN QUY TRÌNH PGS. TS. HÀ QUANG THỤY HÀ NỘI 01-2015 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI 1 Nội dung 1. Nhật ký sự kiện2. Phát hiện quy trình 2Phần 2. Họ thuật toán phát hiện quy trình , +, ++ -Ý tưởng phát hiện quy trình -Thuật toán -Đáng giá thuật toán phát hiện quy trình -- Các hạn chế của thuật toán -Các thuật toán +, ++ 3Phát biểu bài toán  Bài toán phát hiện quy trình  Input:  Nhật ký sự kiện ở dạng đơn giản L  Một tập phức các xâu hành động  Output:  Mô hình quy trình trình bày NKSK dưới dạng lưới Petri N  Kỳ vọng lưới dòng công việc WF-net, đúng đắn  Ví dụ : N1 như hình vẽ  Ý tưởng sơ bộ  N đại diện hành vi trong L  “Hành vi” thường là quan hệ giữa các hành động trong L  “Vết” của L là “hành vi”  Xem xét vết 4Vết của NKSK  Các quan hệ dựa trên NKSK  Cho NKSK L với tập hành động A  >L: a,b A nói a>Lb nếu L: a đi ngay trước b trong : i=a =b. Nói b≯a: i+1 L: b không đi ngay trước a.  L: a Lb a>Lb b≯a. Khi đó nói b La. Quan hệ không đối xứng  ||L: a||Lb a>Lb b>La: Quan hệ đối xứng  #L: a#Lb a≯Lb b≯La. Quan hệ đối xứng  Ma trận vết của L dựa trên các quan hệ  Nhận xét: a,b A: tồn tại duy nhất một quan hệ hoặc a Lb (b La) hoặc a||Lb hoặc a#Lb  Ma trận vết “footprint” ma trận vuông cỡ |A| |A| mà giá trị phần tử dòng a cột b là quan hệ a?Lb  Ví dụ ma trận vết cho L1 5Ý tưởng từ các mỗi quan hệ từ NKSK  Nhận xét  Quan hệ >L chứa mọi cặp hành động đi sau trực tiếp  c Ld: có c>Ld d≯c: có c đi ngay trước d và d không bao giờ đi trước c: một “mẫu tuần tự“ theo “quan hệ nhân quả” trong mô hình kết quả: đặt một vị trí sau c và trước d  Nếu a Lb và a Lc và b#Lc “mẫu rẽ nhánh XOR” từ a sang b,c đây là XOR-split ; tương tự a Lc và b Lc và a#Lb:một XOR-joint  Nếu a Lb và a Lc và b||Lc “mẫu rẽ nhánh AND” từ a sang b,c đây là AND-split ; tương tự a Lc và b Lc và a||Lb một AND-joint  Minh họa các mẫu 6Ma trận vết của một số NKSK  NKSK L2  Ma trận vết  Chỉ khác ma trận vết L1 ở hai hàng (e, f) và hai cột (e,f)  Mô hình quy trình tương ứng L2 7Thuật toán  Input  NKSK L với tập hành động T  Output  Lưới Petri N= mô hình hóa L với hai vị trí đầu, cuối  Phương pháp 8Giải thích thuật toán  Các bước  Bước 1: Mọi thanh chuyển của lưới đầu ra TL  Bước 2: Mọi thanh chuyển được nối từ vị trí vào i (start): T I  Bước 3: Mọi thanh chuyển nối tới vị trí ra o (end): TO  Bước 4: Xác định mọi cặp tập song kết nối (A, B)  Bước 5: Xác định mọi cặp tập song kết nối cực đại (A, B)  Bước 6: Xác định tập vị trí từ song kết nối cực đại, vị trí vào, vị trí ra  Bước 7: Nối các cung  Bước 8: Kết quả  Giải thích bước 5-7  Bước 5: các căp tập có thể, Bước 6 loại các cặp con, bước 7 kết nối hai cặp cực đại 9Ví dụ NKSK L1  Nhật ký và ma trận  Diễn giải các bước  (1) TL={a,b,c,d,e}; (2) TI={a}; TO={d}  (4)  (5)  (6) PL1= {iL,oL} {pa.be, pa.ce, pbe.d, pce.d}  (7, 8 ) như hình vẽ  Đẳng cầu lưới đã nói 10Ví dụ thuật toán cho L5  NKSK L5 và ma trận vết  Diễn giải  Các bước thuật toán 11Ví dụ thuật toán cho L3  NKSK L3  Ma trận vết  Mô hình quy trình N3 tương ứng L3 12Ví dụ thuật toán cho L4  NKSK L4 a b c d e  Ma trận vết  Mô hình quy trình a # # # # N4 tương ứng L4 b # # # # c # # d # # # # e # # # ...