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

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:24

Thêm vào BST

Báo xấu

64
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầ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.

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 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. 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ện 2. Phát hiện quy trình 2
Phầ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 +, ++ 3
Phá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 4
Vế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 6
Ma 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 7
Thuậ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 8
Giả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 9
Ví 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 10
Ví 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 11
Ví 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 12
Ví 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 # # # 13
Hạn chế của thuật toán  Giới thiệu  TT 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ừa  Rất nhiều lưới WF khác nhau lại có hành vi như nhau  Ví dụ N6  Hai vị trí p1, p2 là thừa được gọi là “ẩn” , bị gỡ đi Không ảnh hướng hành vi  Như vậy, một lưới cho tương ứng nhiều lớp có thể 14
Hạn chế 2: chu trình ngắn  Chu trình ngắn  Chu trình ngắn: độ dài 1 hoặc 2  TT phát hiện chu trình độ dài 3 trở lên, có vấn đề với chu trình ngắn  Ví dụ  NKSK bên trái  NKSK bên phải 15
Hạn chế 3: Phụ thuộc không địa phương  Giới thiệu  Nonlocal dependency  TT chỉ xét quan hệ đi trước trực tiếp >L và cảm sinh trực tiếp  Ví 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}  … 16
Đá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 QT  Tồ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ét  Cá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ếp  Một số độ đo trong bài toán “kiểm tra phù hợp” sẽ có độ đo định lượng cụ thể. 17
Sự cân bằng của bốn độ đo  Cạnh tranh của bốn độ đo chất lượng  Xác định chất lượng TT phát hiện quy trình: Khó khăn  4 độ đo chính (nhiều độ đo): phù hợp, chính xác, khái quát, đơn giản  Sẽ đư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ể” 18
Thuật toán +: Bổ sung quan hệ  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: i=a i+1 =b i+2 =a.  L : a,b A nói a Lb nếu a bb L L a. Đố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 L b a>Lb (b≯a a Lb). Khi đó nói b L a. Không đối xứng  ||L: a||Lb a>Lb b>La not (a L b). Đối xứng  #L: a#Lb a≯Lb b≯La. Đối xứng 19
Thuật toán +: Nội dung  Thuật toán  Input: Cho NKSK L  Output: Lưới Petri 20