Chương 1: Giới thiệu chung về hệ thống thông tin và khai phá quá trình

A là A* là dãy các hành động, Một LB(A*) là một nhật ký dự kiện (trên A)[AD13] Wil M. P. van der Aalst, Boudewijn F. van Dongen (2013). Discovering Petri Nets from Event Logs. T. Petri Nets and Other Models of Concurrency 7: 372-422.*Nhật ký sự kiện: khía cạnh bổ sungBa khía cạnh bổ sung điển hìnhTổ chức: Con người, đơn vị, tổ chứcThời gian: Tem thời gian, thời gian thực hiện, thời gian chờ, Tài nguyên: Chi phí.Quy trình chung: Phát hiện mô hình quy trình từ NKSK đơn giản, tiến hành khai phá dữ liệu các khía cạnh bổ sung[AD13] Wil M. P. van der Aalst, Boudewijn F. van Dongen (2013). Discovering Petri Nets from Event Logs. T. Petri Nets and Other Models of Concurrency 7: 372-422.** Cycle DiagramContents Mô hình quá trình [3]- Mô hình quy trình được biểu diễn bằng một ngôn ngữ mô hình hóa.- Có nhiều loại ngôn ngữ mô hình hóa khác nhau như: BPMN, BPEL, UML, Petri-net,- Petri-net là mô hình thường được sử dụng để mô hình hóa quy trình và có thể chuyển đổi sang các mô hình BPMN, PBEL, UML, Mô hình quy trìnhLưới Petri: Một dạng mô hình quy trìnhGiới thiệuMột dạng máy trạng thái hữu hạnDạng đơn giảnBộ ba N = (P,T,F) trong đóP là tập hữu hạn các vị trí (places) T là tập hữu hạn các thanh chuyển, P T = Ø. Thành phần PT được gọi là các nút (nodes)F (PT)(TP) là tập các cung trực tiếp, gọi là luồng quan hệLưới Petri mô hình quy trìnhT: Thanh chuyển  hành độngP: Vị trí kết nối các hành động, nơi “công việc” chuẩn bị được xử lýVí dụ:Trang tiếp theo*Ví dụ mô hình quy trình bằng lưới PetriLưới Petri mô hình hóa quy trình giải quyết yêu cầu bồi thường từ khách hàng của một hãng hàng không*Petri net: một biểu diễn khácVí dụ: P={start,c1,c2,c3,c4,c5,c6,end}T={a,b,c,d,e,f,g,h}F={(start,a), (a,c1), (a,c2), (c1,b), (c1,c), (c2,d), (b,c3), (c,c3), (d,c4), (c3,e), (c4,e), (e,c5), (c5,f), (f,c1), (f,c2), (c5,g), (c5,h), (g,end), (h,end)}*Lưới Petri tổng quátĐịnh nghĩaLưới Petri là bộ năm PN=(P, T, F, W, Mo):P={p1, p2, ..., pm} là tập hữu hạn các trạng tháiT={t1, t2, ..., tn} là tập hữu hạn các thanh chuyểnF (PT)(TP) là tập các cung (quan hệ tiếp sau)W: F{0, 1, 2, ...} là hàm trọng số (trên các cung)Mo: P{0, 1, 2, ...} là đánh dấu ban đầuP T = Ø, PT  ØLưới Petri như trên bỏ qua đánh dấu ban đầu (P, T, F, W) được ký hiệu N. Như vậy PN=(N, Mo)tT: t={pP: (p,t) F} và t ={pP: (t,p) F}. Tương tự, có thể định nghĩa cho pP. Kí hiệu W(p,t)::=W((p,t)), W(t,p)::=W((t,p));Nhận xét dạng tổng quátW: Trọng số cung, Mo : Trọng số vị tríĐánh dấu M: P{0, 1, 2, ...}, M={M(p1), M(p2), ..., M(pm)}. (N, M)Tính đồng thời rộng hơn lưới Petri trong KPQTtT: được gọi là nguồn nếu t=, được gọi là kết nếu t=. Nguồn cháy vô điều kiện, kết tiêu thụ không sinh thẻ.*Hoạt động của lưới PetriCháy được và quy tắc cháyCho (N, M): Một thanh chuyển t “cháy được”  p t thì M(p)  W((p,t))Một thanh chuyển t cháy được có thể “cháy” hoặc “không cháy” Quy tắc cháy: Cho (N, M) và t là “cháy được”. Quy tắc “cháy” t : (N, M)  (N,M’) vớip t  t: M’(p)=M(p)p  t : M’(p)=M(p)-W(p,t)p  t : M’(p)=M(p)+W(t,p)M’ được gọi “đạt được trực tiếp” từ M: MtM’M được gọi là đạt được từ Mo nếu t1, t2, ..., tk để cho Mo t1M1 t2M2... tkMk=M Tự chu trìnhCặp (p,t) được gọi là “tự chu trình” nếu như pttLưới Petri N “thuần túy” (pure) nếu không có bất kỳ tự chu trình Lưới Petri N là “thông thường” nếu mọi trọng số cung là 1 (lúc đó không ghi trọng số cung).Lưới Petri trong KPQT: (i) thông thường; (ii) Mo=(1,0,...,0) với p1 là vị trí khởi đầu *Ví dụ 1Ví dụ 1: cháy thanh chuyển t(a) Trước khi cháy: Mo=(2, 2, 0)(b) Sau khi cháy : M’= (0, 1, 2)Lưới chứa vô hạn, lưới chứa hữu hạnĐịnh nghĩa cháy không hạn chế số thẻ tại mỗi vị trí: Lưới chứa vô hạn Thực tiễn: hạn chế số thẻ trong mỗi vị trí: Lưới chứa hữu hạn hay ngắn gọn là “lưới hữu hạn”Trong lưới hữu hạn: K(p) là số cực đại vị trí p có thể lưu giữĐiều kiện cháy bổ sung: “cháy được” (quy tắc chuyển chặt) pt thì M(p) + W(t,p)  K(p). Nếu bỏ qua bổ sung “yếu”.*Ví dụ 2Biến đổi lưới thuần túy qua quy tắc không chặt (a) pP: P=P{p’} với Mo(p’)=K(p)-Mo(p)(b) tT: p t thì F=F(t,p’) với W(t,p’)=W(p,t) tT: p t thì F=F(p’,t) với W(p’,t)=W(t,p)Ví dụ 2(a) Lưới hạn chế (b) Lưới bổ sung không hạn chế (c) Đồ thị “đạt được” theo lưới bổ sung không hạn chếĐịnh lýLưới chứa hữu hạn thuần khiết và lưới bổ sung theo hai bước trên là tương đương theo nghĩa tạo cùng một tập dãy cháy.*Ứng dụng lưới Petri: máy trạng thái HH*Máy bán kẹo 15 xu và 20 xu*Lưới Petri: hành động đồng thời*Trái: Hoạt động song song xác địnhPhải: Tính lộn xộn (a) lộn xộn đối xứng: t1, t2 cháy đồng thời và xung đột với t3 (b) lộn xộn không đối xứng: t1 và t3 chỉ đồng thời khi t2 cháy trước t1.*Lưới Petri: Dòng dữ liệu tính toán*Lưới Petri mô tả dòng dữ liệu tính toán x=(a+b)/(a-b)*Lưới Petri: Mô tả giao thức truyền thông*Một giao thức truyền thông liên quá trình đơn giản*Lưới Petri: Hệ thống đọc-ghi*Đọc đồng thời, ghi độc quyền*Lưới Petri: Hệ thống sản xuất-tiêu dùngthụ*Người tiêu dùng A ưu tiên hơn người tiêu dùng Bvà nhiều ứng dụng khác[Takao89] Murata Tadao (1989). Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE, 77(4): 541-580, April 1989.*Lưới Petri trong KPDL*Định nghĩaLưới Petri N=(P, T, F)Trọng số cung và trọng số vị trí là 1Đánh dấu M là hàm bội: MB(A)Tập vào: x và tập ra x : x PTThanh chuyển “cháy được”Chuyển dịch đánh dấuDãy cháy: t1, t2, , tk như đã nói ở lưới Petri tổng quátHàm chuyển dịch > từ đánh dấu M sang đánh dấu M’*Triết lý đường mòn trong KPQT*Ví dụ triết lý đường mònXây dựng lối đi trong ĐH ColumbiaTác giả: Dwight Eisenhower, Chủ tịch ĐH Columbia (sau này là Tổng thống Mỹ đời thứ 34)Bài toán: xây lối đi tốt nhất nối các nhà trong khu trườngLời giải: Cho cỏ mọc giữa các tòa nhà và trì hoãn tạo vỉa hèMọi người đi: Hình thành dần lối mòn giữa các nhàXây vỉa hè theo các lối mòn đó*Mô hình vòng đời quản lý QT tác nghiệpMô hình vòng đời BPMKhai phá quy trình: học máy & khai phá dữ liệu ~ mô hình hóa & phân tích quá trình (quá trình kinh doanh).Mục tiêu chính của khai phá quy trình là phát hiện, theo dõi và cải tiến quy trình thực tế, bằng cách lấy tri thức từ nhật ký sự kiện có sẵn trong các hệ thống hiện nay*Ba bài toán khai phá quy trìnhKhai phá quy trình: thiết lập mối liên kết quy trình thực tế và dữ liệu  mô hình quy trình.Khai phá quy trình gồm 3 bài toán:Phát hiện mô hình quy trình.Kiểm tra sự phù hợp của mô hình.Tăng cường mô hình.** Cycle DiagramContents Các bài toán trong khai phá quá trìnhPhát hiện Kiểm tra phù hợp Tăng cườngBa bài toán khai phá quy trìnhDiễn giải quá trình từ DL tới kết quả KPQT*Phát hiện mô hình quá trìnhLà bài toán thứ nhất trong khai phá quá trìnhInput: Nhật ký sự kiện.Output: Mô hình quá trình.Bài toán thực hiện phát hiện mô hình quá trình dựa vào thông tin trong nhật ký sự kiện mà không sử dụng bất kỳ thông tin tiền nghiệm nào.Mô hình quá trình được biểu diễn bằng một ngôn ngữ mô hình hóaCó nhiều loại ngôn ngữ mô hình hóa khác nhau (BPMN, BPEL, UML, Petri-net,)Petri-net thường được sử dụng để mô hình hóa quá trình và có thể chuyển đổi sang các mô hình BPMN, PBEL, UML, khác.** Cycle DiagramContents BÀI TOÁN KIỂM TRA SỰ PHÙ HỢP Input: - Nhật ký sự kiện (Event Log) - Mô hình quá trình (Model) Output: Các độ đo phù hợp. Ứng dụng:Xem xét chất lượng của một mô hình quá trình.Để xác định những trường hợp chệch hướng và hiểu chúng có hành vi chung gì.Để xác định các đoạn quá trình mà ở đó hầu hết xảy ra lệch hướng.Cho mục đích kiểm toán, Kiểm tra phù hợpTrực quan mô hình quy trình[Aalst11] WMP Van der Aalst (2011). Process Mining: Discovery, Conformance and Enhancement of Business Processes, Springer, 2011.[Aalst12] Wil M. P. van der Aalst: Process Mining: Overview and Opportunities. ACM Trans. Management Inf. Syst. 3(2): 7 (2012)Mở rộng mô hình khi bổ sung các khía cạnh: khía cạnh tổ chức (organizational perspective, “What are the organizational roles and which resources are performing particular activities?”), khía cạnh trường hợp (case perspective, “Which characteristics of a case influence a particular decision?”) và khía cạnh thời gian (time perspective, “Where are the bottlenecks in my process?”)*Tuyên ngôn Khai phá quy trình [IE3-TFPM12][IEEE-TFPM] The IEEE Task Force on Process Mining (2012). Process Mining Manifesto, *Nhật ký sự kiện  mô hình quy trìnhBa thao tác liên quan nhật ký sự kiện (hoặc các nguồn thông tin chứa mẫu hành vi khác) và mô hình quy trình: Play-in, Play-out, và Phát lại [Aalst11] *