Chương 3: Phát hiện quy trình

BÀI GIẢNG MỘT SỐ CHỦ ĐỀ HIỆN ĐẠI VỀ KHAI PHÁ DỮ LIỆU:KHAI PHÁ QUÁ TRÌNHCHƯƠNG 3. PHÁT HIỆN QUY TRÌNHPGS. TS. HÀ QUANG THỤYHÀ NỘI 01-2015TRƯỜNG ĐẠI HỌC CÔNG NGHỆĐẠI HỌC QUỐC GIA HÀ NỘI*Nội dungNhật ký sự kiệnPhát hiện quy trình *Phần 2. Họ thuật toán phát hiện quy trình , +, ++Ý tưởng phát hiện quy trìnhThuậ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 +, ++ *Phát biểu bài toánBài toán phát hiện quy trìnhInput: Nhật ký sự kiện ở dạng đơn giản LMột tập phức các xâu hành độngOutput:Mô hình quy trình trình bày NKSK dưới dạng lưới Petri NKỳ vọng lưới dòng công việc WF-net, đúng đắnVí 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 *Vết của NKSKCác quan hệ dựa trên NKSKCho 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  i+1=b. Nói b≯a: 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ứngMa 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#LbMa 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?LbVí dụ ma trận vết cho L1*Ý tưởng từ các mỗi quan hệ từ NKSKNhận xétQuan 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 dNế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-jointNế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-jointMinh họa các mẫu*Ma trận vết của một số NKSKNKSK L2Ma trận vếtChỉ 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*Thuật toán InputNKSK L với tập hành động TOutputLưới Petri N= mô hình hóa L với hai vị trí đầu, cuốiPhương pháp*Giải thích thuật toánCác bướcBước 1: Mọi thanh chuyển của lưới đầu ra TLBước 2: Mọi thanh chuyển được nối từ vị trí vào i (start): TIBước 3: Mọi thanh chuyển nối tới vị trí ra o (end): TOBướ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í raBước 7: Nối các cung Bước 8: Kết quảGiải thích bước 5-7Bướ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*Ví dụ NKSK L1Nhật ký và ma trậnDiễ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*Ví dụ thuật toán cho L5NKSK L5 và ma trận vếtDiễn giảiCác bước thuật toán*Ví dụ thuật toán cho L3NKSK L3Ma trận vếtMô hình quy trình N3 tương ứng L3*Ví dụ thuật toán cho L4NKSK L4Ma trận vếtMô hình quy trình N4 tương ứng L4*abcdea####b####c##d####e###Hạn chế của thuật toán Giới thiệuTT  khai phá lớp NKSK lớn với giả định NLSK liên quan hoàn toàn với quan hệ thứ tựTT có hạn chế ngay cả khi “liên quan hoàn toàn”Hạn chế 1: Tính dư thừaRất nhiều lưới WF khác nhau lại có hành vi như nhauVí dụ N6Hai vị trí p1, p2 là thừađược gọi là “ẩn” , bị gỡ đi Không ảnh hướng hành viNhư vậy, một lướicho tương ứng nhiều lớpcó thể*Hạn chế 2: chu trình ngắnChu trình ngắnChu trình ngắn: độ dài 1 hoặc 2TT phát hiện chu trình độ dài 3 trở lên, có vấn đề với chu trình ngắnVí dụNKSK bên tráiNKSK bên phải*Hạn chế 3: Phụ thuộc không địa phươngGiới thiệuNonlocal dependencyTT  chỉ xét quan hệ đi trước trực tiếp >L và cảm sinh trực tiếpVí dụMô hình thực sự: không phát hiện hai vị trí p1, p2{a,b,c,d,e}, {a,b}, {d, e}*Đánh giá thuật toán phát hiện quy trìnhĐặt vấn đềMô hình kết quả cần đáp ứng yêu cầu “phù hợp” (fitness) NKSK“Mọi vết trong NKSK” đều là vết cháy được trong mô hình QTTồn tại một số độ đo đo lường tính phù hợp.Các độ đo“phù hợp” (fitness): mô hình kết quả cần thừa nhận các hành vi nhìn được từ NKSK“chính xác” (precision): Mô hình kết quả cần không thừa nhận các hành vi không liên quan đầy đủ tới những cái nhìn được từ NKSK“khái quát” (generalization): Mô hình kết quả cần khái quát hóa các hành vi nhìn được từ NKSK.“đơn giản” (simplicity): Mô hình kết quả cần đơn giản nhất có thể được.Nhận xétCác độ đo trên đây đã rõ song vẫn chưa có công thức định lượng: vấn đề cần nghiên cứu tiếpMột số độ đo trong bài toán “kiểm tra phù hợp” sẽ có độ đo định lượng cụ thể.*Sự cân bằng của bốn độ đoCạnh tranh của bốn độ đo chất lượngXác định chất lượng TT phát hiện quy trình: Khó khăn4 độ đo chính (nhiều độ đo): phù hợp, chính xác, khái quát, đơn giảnSẽ đưa ra các công thức định lượng: đo theo trường hợp/sự kiện. phù hợp: Phù hợp  “hồi tưởng”đơn giản: “dao cạo” Occam.khái quát: tránh quá khít với NKSK; “quá chung chung”Chính xác: tránh quá sơ lược với NKSK; “quá cụ thể”*Thuật toán +: Bổ sung quan hệCác quan hệ dựa trên NKSKCho NKSK L với tập hành động A L: a,b  A nói aLb nếu L: i=ai+1=bi+2=a. L: a,b  A nói aLb nếu aLbbLa. Đối xứng>L: a,b  A nói a>Lb nếu L: a đi ngay trước b trong : i=a  i+1=b. Nói b≯a: L: b không đi ngay trước a.L: aLb  a>Lb(b≯a  aLb). Khi đó nói bLa. Không đối xứng||L: a||Lb a>Lbb>La  not (a Lb). Đối xứng#L: a#Lb a≯Lbb≯La. Đối xứng*Thuật toán +: Nội dungThuật toánInput: Cho NKSK L Output: Lưới Petri**Thuật toán alpha++: Bổ sung quan hệCác quan hệ dựa trên NKSKCho NKSK L với tập hành động A L: a,b  A nói aLb nếu L: i=ai+1=bi+2=a. L: a,b  A nói aLb nếu aLbbLa>L: a,b  A nói a>Lb nếu L: a đi ngay trước b trong : i=a  i+1=b. Nói b≯a: L: b không đi ngay trước a.L: aLb  a>Lb(b≯a  aLb  bLa). 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  (aLb  bLa)*Thuật toán alpha++NMM*Thuật toán alpha++Thuật toán alpha++ *