Chương 1. GIỚI THIỆU VỀ KHAI PHÁ QUÁ TRÌNH 1. Tổng quan về khai phá quá trình 1. Khai phá quá trình là gì Khai phá quá trình (process mining) là một chuyên ngành nghiên cứu mới.P van der Aalst [1], khai phá quá trình là chuyên ngành nghiên cứu về những phương thức phát hiện, phân tích và cải tiến các quá trình dựa vào thông tin trích xuất được từ dữ liệu sự kiện.
Vị trí của khai phá quá trình trong KHDL và Big data. Ngày nay trong KHDL (khoa học dữ liệu) người ta không chỉ chú ý tới việc lưu trữ và phân tích dữ liệu mà người ta còn quan tâm đến mối liên hệ giữa dữ liệu với các quá trình liên quan. Khai phá quá trình chính là cầu nối giữa quản lý quá trình kinh doanh truyền thống với các kỹ thuật phân tích dữ liệu làm trung tâm như: khai phá dữ liệu và học máy.1: Vị trí của khai phá quá trình trong khoa học dữ liệu [2] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2: Vai trò cầu nối của khai phá quá trình [6] Khai phá quá trình là phương tiên giao tiếp giữa phân tích mô hình quá trình (process model analysis) với phân tích định hướng dữ liệu (data-oriented analysis). Nó được dùng để trả lời các câu hỏi khác nhau liên quan đến hiệu năng và tính tuân thủ.
Mối liên hệ với khai phá dữ liệu Theo Van der Aalst [2], khai phá quá trình liên quan mật thiết đến khai phá dữ liệu. Trong khi các kĩ thuật khai phá dữ liệu truyền thống chủ yếu tập trung vào dữ liệu (data-centric) thì khai phá quá trình tập trung vào quá trình (process-centric). Khai phá quá trình được sử dụng để trả lời cho các câu hỏi: - Quá trình nào con người thực sự làm theo? - Đâu là những trở ngại trong quá trình của tôi? - Đâu là chỗ mà con người hay máy móc thực hiện khác với lại quá trình mong đợi hay quá trình lý tưởng ban đầu? - Đâu là “lối mòn” trong quá trình của tôi? - Những tác nhân nào đang gây trở ngại? - Liệu tôi có thể tiên đoán các vấn đề có thể gặp phải (độ trễ, độ sai lệch, rủi ro,…) trong các trường hợp đang chạy? - Làm thế nào để thiết kế lại quá trình, tổ chức, máy móc cho hiệu quả? LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Mặc dù cả hai đều bắt đầu từ dữ liệu nhưng các kỹ thuật khai phá dữ liệu thường không tập trung đến quá trình, không tập trung vào dữ liệu sự kiện. Những chủ đề như phát hiện quá trình, kiểm tra độ phù hợp, phân tích các trở ngại trong quá trình kinh doanh là không được đề cập trong các kỹ thuật khai phá dữ liệu truyền thống.
Khai phá dữ liệu và khai phá quá trình cần được kết hợp với nhau để trả lời các câu hỏi nâng cao hơn. Các bài toán trong khai phá quá trình Trong khai phá quá trình có 3 loại bài toán chính: bài toán phát hiện quá trình (process discovery), kiểm tra sự phù hợp (conformance checking), tăng cường quá trình (process enhancement). Có 3 thao tác chính thể hiện mối quan hệ giữa mô hình và nhật ký sự kiện là: : Play-out, Play-in và Replay. Trong đó Play-out là từ mô hình sinh ra hoạt động, Play-in là tự động hình thành mô hình từ nhật ký sự kiện, Replay là chạy lại mô hình đồng thời so sánh với dữ liệu sự kiện để kiểm tra tính đúng đắn cũng như là cải tiến mô hình.3: Các bài toán trong khai phá quá trình [2] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Phát hiện quá trình Là bài toán với mục tiêu xây dựng mô hình chỉ từ nhật ký sự kiện mà không sử dụng bất kì một mô hình hay thông tin tiền nghiệm nào khác. Một ví dụ là thuật toán Alpha (α- algorithm) chỉ nhận đầu vào là một nhật ký sự kiện, sẽ sinh ra một lưới Petri tương ứng mà không cần sử dụng thêm tri thức bổ sung nào khác. Mô hình xây dựng được có thể trả lời các câu hỏi phổ biến trong quá trình sản xuất kinh doanh như: - Hoạt động nào nằm trước hoạt động nào? - Có nhóm hoạt động nào được thực hiện đồng thời không? - Trong quá trình có hoạt động nào bị lặp không? - Các nhân viên tương tác như thế nào? - Những ai làm cùng nhiệm vụ với nhau? - Có bao nhiêu vị trí tham gia trong một trường hợp? 1. Kiểm tra độ phù hợp Bài toán này sử dụng đầu vào gồm một mô hình có sẵn và nhật ký sự kiện.
Mô hình sẽ được sử dụng để kiểm tra xem các sự kiện thực tiễn được lưu trong nhật ký sự kiện có phù hợp với mô hình không, và ngược lại. Có thể mô hình đang sử dụng không bao hàm được tất cả các trường hợp vì thế có những trường hợp các hoạt động không tuân theo mô hình. Cũng có trường hợp chỉ tồn tại trên mô hình mà thực tế không bao giờ xảy ra. Do vậy, sẽ luôn hữu ích khi có một công cụ cung cấp phản hồi về những vấn đề này.
Bài toán kiểm tra sự phù hợp của mô hình nhằm cung cấp những công cụ phản hồi như vậy. Tăng cường mô hình Sau có được kết quả của bước kiểm tra độ phù hợp thì bài toán tiếp theo được đặt ra là tăng cường mô hình. Bài toán hướng tới việc mở rộng hoặc cải tiến mô hình có sẵn, nhờ rút ra kinh nghiệm từ thông tin về quá trình thực tế đã thu thập được trong các nhật ký sự kiện. Tăng cường ở đây có 2 loại, một là “sửa” mô hình để phản ánh đúng hơn với thực tế, hai là “mở rộng” mô hình để thêm vào các khía cạnh bổ sung.
Tăng cường mô hình giúp tăng hiệu suất làm việc, giải quyết những điểm mâu thuẫn hoặc bế tắc, loại bỏ các thành phần không cần thiết. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Mô hình hóa quá trình Các phương pháp mô hình hóa quá trình thương mại chính thường sử dụng các dạng kí hiệu mô hình như BPMN, UML, EPC, các loại lưới Petri, hệ thống chuyển, luồng điều khiển,. Nhật ký sự kiện (Event Logs) Điểm khởi đầu cho khai phá quá trình là nhật ký sự kiện (event logs).
Mỗi sự kiện trong nhật ký sự kiện tương ứng với một hoạt động và một trường hợp cụ thể. Trong mỗi trường hợp, các sự kiện này được sắp xếp theo một thứ tự nào đó tùy thuộc vào thực tế diễn ra trong quá trình. Ngoài các sự kiện, nhật ký sự kiện còn có thể lưu trữ một số thông tin khác liên quan đến sự kiện mà một số kỹ thuật khai phá quá trình cũng có thể tận dụng như nguồn lực thi hành sự kiện, thời gian bắt đầu thi hành, thời gian kết thúc, v.1: Một phân đoạn của nhật ký sự kiện cho yêu cầu bồi thường [1] - Mỗi quá trình (process) bao gồm các trường hợp (cases). - Mỗi trường hợp bao gồm các sự kiện (event) sao cho mỗi sự kiện chỉ liên kết với đúng một trường hợp.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 - Trong mỗi trường hợp, các sự kiện diễn ra theo thứ tự. - Các sự kiện có thể có thuộc tính (attribute) như hoạt động, thời gian, chi phí, nguồn lực,. Không phải tất cả các sự kiện đều phải có tập thuộc tính như nhau, song thông thường, các sự kiện liên quan đến cùng hoạt động thì sẽ có chung tập thuộc tính. Loại dữ liệu trong nhật ký sự kiện xác định phương diện thông tin nào có thể được khai phá.
Theo Van der Aalst [1], có 4 phương diện khai phá chính: 1) Phương diện luồng điều khiển (control-flow perspective) tập trung vào luồng điều khiển, tức là thứ tự của các hoạt động. Mục đích của khai phá phương diện luồng điều khiển là tìm được các đặc tính tốt nhất có thể cho tất cả các luồng điều khiển. Phương diện luồng điều khiển có thể được khai phá qua nhật ký sự kiện khi nhật ký sự kiện cung cấp các nhiệm vụ đã được xử lý trong quá trình (chẳng hạn qua các trường tên công việc, thời gian) và ta có thể suy luận được thứ tự xử lý và liên kết các nhiệm vụ này vào các trường hợp (mẫu) riêng biệt. 2) Phương diện tổ chức (organizational perspective) tập trung vào các thông tin về nguồn lực ẩn trong nhật ký sự kiện, ví dụ như những đối tượng nào (người, hệ thống, vai trò, bộ phận) tham gia vào hoạt động và các đối tượng liên quan đến nhau như thế nào.
Khai phá phương diện tổ chức ứng dụng cho cơ cấu tổ chức qua việc phân loại nguồn lực vào các vai trò và đơn vị trổ chức hoặc qua các thông tin thu được từ mô hình mạng xã hội. 3) Phương diện trường hợp (case perspective) tập trung vào các thuộc tính, đặc điểm riêng của mỗi trường hợp. Rõ ràng, mỗi trường hợp đều có thể được mô tả bằng đường đi của nó trong luồng quá trình. Tuy nhiên, ta cũng có thể mô tả các trường hợp bằng giá trị của các phần tử dữ liệu tương ứng.
Ví dụ, nếu một trường hợp biểu diễn các đơn hàng bổ sung, thì qua đó ta có thể muốn biết nhà cung cấp hoặc số lượng sản phẩm đã được đặt mua. 4) Phương diện thời gian (time perspective) quan tâm tới thời gian và mức độ thường xuyên của các sự kiện. Khi các sự kiện được ghi lại cùng với thời gian, ta có thể phát hiện các điểm thắt cổ chai, đo lường sức phục vụ, giám sát việc sử dụng tài nguyên, và dự đoán thời gian xử lý còn lại của các trường hợp đang chạy. Các phương diện này không tách biệt độc lập mà chồng chéo một phần nào đó lên nhau, và không đầy đủ.
Tuy nhiên, chúng mô tả tốt những đặc điểm mà khai phá quá trình muốn phân tích. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các loại mô hình hóa quá trình Có rất nhiều bộ ký hiệu cho mô hình hóa quá trình, tuy nhiên trong luận văn sẽ chỉ giới thiệu về hai loại mô hình hóa mà sẽ được sử dụng ở các phần sau là Lưới Petri (Petri net) và Hệ thống chuyển (Transition system). Chúng ta có thể dễ dàng chuyển đổi sang các ngôn ngữ mô hình hóa khác như BPMN, BPEL hay biểu đồ hoạt động UML,.
Lưới Petri (Petri Nets) Lưới Petri (petri net) là ngôn ngữ mô hình hóa quá trình lâu đời nhất và tốt nhất trong các ngôn ngữ đã được khảo sát. Lưới Petri cho phép biểu diễn các mô hình chứa thành phần đồng thời.