ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Lại Thị Huyền Trang

PHÁT HIỆN MÔ HÌNH QUY TRÌNH TỪ
NHẬT KÝ SỰ KIỆN KHÔNG ĐẦY ĐỦ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin

HÀ NỘI - 2016


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Lại Thị Huyền Trang

PHÁT HIỆN MÔ HÌNH QUY TRÌNH TỪ
NHẬT KÝ SỰ KIỆN KHÔNG ĐẦY ĐỦ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin

Cán bộ hướng dẫn: PGS. TS. Hà Quang Thụy

Cán bộ đồng hướng dẫn: Ths. Lê Hoàng Quỳnh

HÀ NỘI - 2016

VIETNAM NATIONAL UNIVERSITY
UNIVERSITY OF ENGINEERING AND TECHNOLOGY

Lai Thi Huyen Trang

DISCOVERING PROCESS MODELS FROM
INCOMPLETE EVENT LOGS

A THESIS PRESENTED FOR THE DEGREE BACHELOR
Department: Information Technology

Supervisors: Assoc. Prof. Ha Quang Thuy
MsC. Le Hoang Quynh

HA NOI - 2016


LỜI CẢM ƠN
Trước tiên, em xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới Phó giáo
sư- Tiến sĩ Hà Quang Thụy đã tận tình chỉ bảo, hướng dẫn và giúp đỡ em trong suốt
thời gian thực hiện đề tài này.
Em xin chân thành biết ơn các thầy cô trong Khoa Công Nghệ Thông Tin và
trong trường Đại học Công Nghệ đã tận tình chỉ bảo, dạy dỗ và truyền đạt kiến thức
cho em trong suốt bốn năm học đại học.
Em cũng xin được gửi lời cảm ơn đến các thầy, các anh chị, các bạn và các em
sinh viên trong Phòng thí nghiệm Công nghệ tri thức và Khoa học dữ liệu KT- Lab,
đặc biệt là trong nhóm “Khai phá quy trình” đã giúp đỡ và hỗ trợ em rất nhiều để hoàn
thành tốt khóa luận.
Con cũng xin gửi lời cảm ơn đến bố mẹ vì công ơn sinh thành, nuôi dưỡng, chăm

sóc và chỉ bảo cho con, yêu thương, động viên và giúp đỡ con trên mọi con đường.
Cuối cùng, xin gửi lời cảm ơn đến các bạn trong tập thể lớp K57CLC, các bạn
trong nhóm hai và các bạn nữ trong lớp K57CLC đã ủng hộ, giúp đỡ trong suốt quá
trình học tập trên giảng đường đại học.
Em xin chân thành cảm ơn!

i


TÓM TẮT
Tóm tắt: Khai quá quy trình tập trung vào việc phân tích dữ liệu quá trình từ những dữ liệu
sự kiện ghi lại được. Khai phá quy trình sử dụng những dữ liệu ghi nhận được từ nhật ký sự
kiện để phát hiện, phân tích và cải thiện quá trình kinh doanh. Bài toán phát hiện quy trình
(process discovery) là một trong ba bài toán lớn của khai phá quy trình (phát hiện quy trình,
kiểm tra sự phù hợp và tăng cường mô hình). Về cơ bản, bài toán này dựa trên nhật ký sự kiện
có sẵn của những hành vi thực tế để phát hiện mô hình của quá trình đó. Hiện nay đã có nhiều
kĩ thuật được đưa ra nhằm phát hiện mô hình quy trình, đã thành công và được áp dụng trong
một số hệ thống và công cụ hỗ trợ quá trình quản lý kinh doanh, điển hình là nhóm nghiên
cứu của Wil M. P. van der Aalst, Sander J.J Leemans. Theo Sander J.J. Leemans và cộng sự
(2014, 2015), một trong những thách thức chính trong việc khai phá quy trình là khám phá mô
hình quá trình mô tả hành vi được quan sát một cách tốt nhất có thể. Bởi vì nhật ký sự kiện
chỉ bao gồm các hành vi mẫu nên không thể giả thiết là có thể nhìn thấy tất cả các hành vi có
thể, các kỹ thuật phát hiện quy trình cần để có thể xử lý tính không đầy đủ.
Dựa trên nghiên cứu của Sander J.J. Leemans và cộng sự về các kỹ thuật phát hiện mô
hình quy trình từ nhật ký sự kiện không đầy đủ, khóa luận này nhằm giới thiệu khái quát về
phương pháp giải quyết bài toán phát hiện quy trình và những ảnh hưởng của tính không đầy
đủ của nhật ký sự kiện đến việc phát hiện quy trình. Khóa luận cũng trình bày thuật toán phát
hiện mô hình từ nhật ký sự kiện không đầy đủ, cụ thể thuật toán được chọn cho thực nghiệm
là thuật toán IMin (Inductive Miner - incompleteness). Cuối cùng, khóa luận tiến hành thực
nghiệm trên ba bộ dữ liệu đưa ra mô hình quy trình với trung bình độ đo phù hợp (fitness) là

0.688, độ đo chính xác (precision) là 0.809, và độ đo tổng quát (generalization) là 0.979.
Từ khóa: Phát hiện quy trình, nhật ký sự kiện không đầy đủ, lưới Petri, cây quy trình

ii


ABSTRACT
Abstract: Process mining focus on data analysis process from data recorded event. Process
mining uses the recorded data from the event logs to detect, analyze and improve business
process. Process discovery is one of the three major problems of the process mining (process
discovery, checks the compatibility and enhanced models). Basically, this problem is based on
the diary of the event which is available on the actual behavior to detect the actual model of
the process. Currently, there are many techniques that can be taken to detect process model,
these techniques have been applied successfully in some systems and tools to support business
process management, typically Wil M. P. van der Aalst, Sander J.J Leemans. According to
Sander J.J. Leemans and his colleagues (2014, 2015), one of the main challenges of the
process mining is discovery process model that captures the given behavior precisely.
Because the event log only includes behavioral patterns, therefore it should not be assumed to
be able to see all the possible behaviors, and techniques detection processes need to be able to
handle the incompleteness of event logs.
Based on Sander J.J Leemans and his colleagues’s research, this thesis aims are to
introducing an overview of methods to solve the detection process problem and the effect of
the incomplete event log to the process discovery. This thesis also introduces detection
algorithm models from event logs which are incompleted, specially, IMin algorithm
(Inductive Miner – incompleteness). Finally, the thesis proceeds the experimental section with
three data sets, gives process model with fitness approximately 0.688, precision
approximately 0.809, generalization approximately 0.979.
Keywords: process discovery, incomplete event log, petri-net, process tree

iii



LỜI CAM ĐOAN
Em xin cam đoan đề tài khóa luận “Phát hiện mô hình quy trình từ nhật ký sự
kiện không đầy đủ” áp dụng các kĩ thuật khai phá quy trình và xây dựng mô hình thực
nghiệm là do em thực hiện dưới sự hướng dẫn của PGS.TS Hà Quang Thụy.
Tất cả những tài liệu nghiên cứu liên quan của các tác giả khác được sử dụng
trong khóa luận đều được nêu rõ ràng và tường minh về tác giả và đều có trong danh
mục tài liệu tham khảo của khóa luận.

Hà Nội, ngày tháng năm 2016
Sinh viên

Lại Thị Huyền Trang

iv


Mục lục
LỜI CẢM ƠN ............................................................................................................... i
TÓM TẮT ....................................................................................................................ii
ABSTRACT ................................................................................................................ iii
LỜI CAM ĐOAN ........................................................................................................ iv
Danh sách thuật ngữ và từ viết tắt ............................................................................. vii
Danh sách hình vẽ .................................................................................................... viii
Danh sách bảng biểu ................................................................................................... x
Lời mở đầu .................................................................................................................. 1
Chương 1: Phát hiện quy trình từ nhật ký sự kiện không đầy đủ .................................. 3
1.1.


Phát hiện quy trình ......................................................................................... 3

1.1.1.

Giới thiệu tổng quan về phát hiện quy trình ............................................. 3

1.1.2.

Độ đo tiêu chuẩn chất lượng của mô hình ................................................ 4

1.2.

Nhật ký sự kiện không đầy đủ ......................................................................... 5

1.2.1.

Nhật ký sự kiện......................................................................................... 5

1.2.2.

Tính không đầy đủ của nhật ký sự kiện ..................................................... 7

1.3.

Phát hiện quy trình từ nhật ký sự kiện không đầy đủ ....................................... 9

1.3.1.

Lưới Petri, Cây quy trình và Đồ thị luồng có hướng................................. 9


1.3.2.
đủ

Sơ bộ các phương pháp phát hiện quy trình từ nhật ký sự kiện không đầy
11

1.4.

Sơ bộ bài toán của khóa luận........................................................................ 12

Tóm tắt chương 1 ................................................................................................... 12
Chương 2. Một số kỹ thuật phát hiện quy trình từ nhật ký sự kiện không đầy đủ ........ 13
2.1.

Thuật toán IMin ............................................................................................ 13

2.1.1.

Quan hệ hành vi ..................................................................................... 13

2.1.2.

Thuật toán IMin ..................................................................................... 15

2.2.

Thuật toán IMinD ......................................................................................... 18

2.2.1.


Khái niệm đồ thị luồng có hướng và phân hoạch.................................... 19

2.2.2.

Phát hiện quy trình sử dụng đồ thị luồng có hướng ................................ 21

v


2.3. Ý tưởng mô hình phát hiện quy trình từ nhật ký sự kiện không đầy đủ của khóa
luận 25
Tóm tắt chương 2 ................................................................................................... 26
Chương 3: Một mô hình phát hiện quy trình từ nhật ký sự kiện không đầy đủ ............ 27
3.1.

Giới thiệu sơ bộ ............................................................................................ 27

3.2.

Mô hình giải quyết bài toán phát hiện quy trình đề nghị ............................... 27

3.2.1.

Pha áp dụng thuật toán phát hiện quy trình ........................................... 29

3.2.2.

Pha tính toán các độ đo ......................................................................... 30

3.2.3.


Pha so sánh các phương pháp ................................................................ 31

Tóm tắt chương 3 ................................................................................................... 32
Chương 4: Thực nghiệm và đánh giá ......................................................................... 33
4.1.

Mô tả thực nghiệm ........................................................................................ 34

4.1.1.

Mô tả dữ liệu.......................................................................................... 34

4.1.2.

Môi trường thực nghiệm......................................................................... 40

4.1.3.

Các công cụ, phần mềm và plug-in sử dụng ........................................... 40

4.2.

Kết quả thực nghiệm và đánh giá.................................................................. 41

4.2.1.

Kết quả thực nghiệm .............................................................................. 41

4.2.2.


Đánh giá kết quả thực nghiệm ................................................................ 44

Tóm tắt chương 4 ................................................................................................... 47
Kết luận ..................................................................................................................... 48
Kết quả đạt được của khóa luận và hạn chế ........................................................... 48
Định hướng tương lai ............................................................................................. 48
Tài liệu tham khảo ..................................................................................................... 49

vi


Danh sách thuật ngữ và từ viết tắt
Tiếng Anh/ Từ viết tắt

Tiếng Việt/ Cụm từ đầy đủ

Directly- Follow Relation

Quan hệ luồng có hướng

Event Log

Nhật ký sự kiện

Fitness

Độ đo phù hợp

Generalization


Độ đo tổng quát

IM

Inductive Miner

IMD

Inductive Miner framework

IMin

Inductive Miner- incompleteness

IMinD

Inductive Miner-incompleteness-directlyfollows based

Incomplete Event Log

Nhật ký sự kiện không đầy đủ

Precision

Độ đo chính xác

Process Discovery

Phát hiện quy trình


Simplicity

Đọ đo tính đơn giản

WP- net

Lưới luồng công việc

vii


Danh sách hình vẽ
Chương 1
Hình 1.1: Ngữ cảnh khai phá quy trình [1] .................................................................. 3
Hình 1.2: Luồng công việc tiêu biểu trong khai phá quy trình (trong [7] ) ................... 4
Hình 1.3: Cân bằng bốn tiêu chí chất lượng: fitness, simplicity, precision và
generalization ([10]) ................................................................................................... 4
Hình 1.4: Một đoạn nhật ký sự kiện [10] ..................................................................... 6
Hình 1.5: Dạng cô đọng của một nhật ký sự kiện bao gồm các vết trường hợp [10] .... 7
Hình 1.6: Ví dụ mô hình lưới luồng công việc .............................................................. 8
Hình 1.7: Ví dụ lưới Petri [8] ...................................................................................... 9
Hình 1.8: Cây quy trình →( × ( (a, b), c), × (Q (→ (d, e), f), g)) tương ứng với lưới
[6] ............................................................................................................................. 10
Hình 1.9a: Đồ thị quan hệ luồng có hướng Hình 1.9b:Đồ thị bao đóng của đồ thị 1.9a
.................................................................................................................................. 11
Chương 2
Hình 2.1: Các quan hệ hành vi được tổ chức trong một lưới [6] ................................ 14
Hình 2.2: Ví dụ chạy thuật toán IMin ([6]) ................................................................ 18
Hình 2.3: Ví dụ về đồ thị luồng có hướng[7].............................................................. 19

Hình 2.4: Các cắt đặc trưng [7] ................................................................................ 20
Hình 2.5: Đồ thị luồng có hướng D1 của L với phân hoạch ({a},{b,c,d,e},{f,g,h},{i})
được kí hiệu bởi các đường nét đứt[7] ....................................................................... 20
Hình 2.6: Các đồ thị con được phân chia từ D1 sử dụng cắt tuần tự phát hiện được [7]
.................................................................................................................................. 22
Hình 2.7: Đồ thị phân chia bởi cắt từ đồ thị D3[7]..................................................... 23
Hình 2.8: Một đồ thị luồng có hướng không đầy đủ [7] ............................................. 24
Chương 3
Hình 3.1: Mô hình giải quyết bài toán phát hiện quy trình ......................................... 28

viii


Chương 4
Hình 4.1: Một phần dữ liệu của nhật ký sự kiện Lfull................................................. 35
Hình 4.2: Mô tả dữ liệu trong toàn bộ nhật ký sư kiện Lfull ....................................... 35
Hình 4.3: Dữ liệu data1 được thể hiện trong ProM ................................................... 37
Hình 4.4: Dữ liệu data2 được thể hiện trong ProM ................................................... 38
Hình 4.5: Dữ liệu data3 được mô tả trong ProM ....................................................... 39
Hình 4.6: Mô hình lưới Petri được tạo ra bởi áp dụng thuật toán IMin sử dụng bộ dữ
liệu data1................................................................................................................... 41
Hình 4.7: Mô hình lưới Petri được tạo ra bởi áp dụng thuật toán alpha sử dụng bộ dữ
liệu data1................................................................................................................... 42
Hình 4.8: Mô hình quy trình lưới Petri được tạo ra bởi áp dụng thuật toán IMin sử
dụng data2 ................................................................................................................. 42
Hình 4.9: Mô hình quy trình lưới Petri được tạo ra bởi áp dụng thuật toán alpha sử
dụng dữ liệu data2 ..................................................................................................... 43
Hình 4.10: Mô hình quy trình lưới Petri được tạo ra bởi áp dụng thuật toán IMin sử
dụng dữ liệu data3 ..................................................................................................... 43
Hình 4.11: Mô hình quy trình lưới Petri được tạo ra bởi áp dụng thuật toán alpha sử

dụng dữ liệu data3 ..................................................................................................... 44
Hình 4.12: Biểu đồ so sánh độ đo phù hợp giữa IMin và Alpha ................................. 45
Hình 4.13: Biểu đồ so sánh độ đo chính xác giữa IMin và Alpha ............................... 46
Hình 4.14: Biểu đồ so sánh độ đo tổng quát giữa IMin và Alpha ............................... 46

ix


Danh sách bảng biểu
Chương 2
Bảng 2.1: Xác suất quan hệ hành vi của a và b [6] .................................................... 15
Chương 4
Bảng 4.1: Đặc điểm dữ liệu trong nhật ký sự kiện Lfull ............................................. 34
Bảng 4.2: Thống kê dữ liệu của sự kiện bắt đầu và sự kiện kết thúc ........................... 35
Bảng 4.3: Thống kê tần suất của các lớp sự kiện ....................................................... 36
Bảng 4.4: Dữ liệu data1 được sử dụng cho thực nghiệm ............................................ 36
Bảng 4.5: Thống kê tần xuất của các lớp sự kiện trong data1 .................................... 37
Bảng 4.6: Dữ liệu data2 được sử dụng cho thực nghiệm ............................................ 38
Bảng 4.7: Thống kê tần xuất của các lớp sự kiện trong data2 .................................... 39
Bảng 4.8: Dữ liệu data3 được sử dụng cho thực nghiệm ............................................ 39
Bảng 4.9: Môi trường thực nghiệm (phần cứng và hệ điều hành) .............................. 40
Bảng 4.10: Các công cụ, phần mềm và plug-in sử dụng ............................................. 40
Bảng 4.11: Kết quả so sánh data1 ............................................................................. 44
Bảng 4.12: Kết quả so sánh data2 ............................................................................. 45
Bảng 4.13: Kết quả so sánh data3 ............................................................................. 45

x


Lời mở đầu

Ngày nay, các doanh nghiệp thường ghi lại quá trình thực hiện quy trình nghiệp
vụ của mình vào nhật ký sự kiện. Việc sử dụng những dữ liệu sẵn có trong các hệ
thống để phát hiện, theo dõi và cải tiến quá trình thực tế là mục tiêu chính của khai phá
quy trình. Trong đó, có nhiều thách thức được đặt ra như: các tác vụ ẩn, các tác vụ lặp,
nhiễu trong nhật ký sự kiện hay tính không đầy đủ của nhật ký sự kiện, do một vài sự
cố của hệ thống khi đang thực thi hoặc do tác động của nhân tố con người, các vấn đề
này đặt ra thách thức lớn cho các kĩ thuật phát hiện quy trình. Việc phát triển và đưa ra
các kĩ thuật mới để xử lý các vấn đề này là vô cùng cần thiết, được sự quan tâm của
nhiều nhóm nghiên cứu như nhóm nghiên cứu của Sander J.J Leemans, nhóm nghiên
cứu của Ivona Zakarija.
Khóa luận này tập trung chủ yếu vào việc phát hiện mô hình quy trình từ các vết
mẫu sẵn có trong nhật ký sự kiện không đầy đủ để đưa ra mô hình quy trình (ví dụ như
một lưới Petri), giúp hỗ trợ và cải thiện quá trình kinh doanh của doanh nghiệp. Hướng
tiếp cận của khóa luận được đưa ra dựa trên những nghiên cứu của Sander J.J.
Leemans và cộng sự [6][7], sử dụng kĩ thuật tính toán xác suất quan hệ hành vi để xây
dựng mô hình quy trình, tiêu biểu là thuật toán IMin (Inductive Miner incompleteness).
Nội dung của khóa luận được chia thành các chương sau:
Chương 1: Khóa luận giới thiệu khái quát về phát hiện mô hình quy trình, đưa ra
định nghĩa và các ảnh hưởng của nhật ký sự kiện không đầy đủ đến việc phát hiện quy
trình, đồng thời khóa luận cũng giới thiệu phương pháp để phát hiện mô hình quy trình
từ nhật ký sự kiện không đầy đủ. Cuối cùng, trong chương này cũng đưa ra cái nhìn
tổng quan cho bài toán của khóa luận.
Chương 2: Khóa luận trình bày về hai phương pháp phát hiện mô hình quy trình
từ nhật ký sự kiện không đầy đủ của Sander J.J. Leemans và cộng sự [6][7], tiêu biểu
là phương pháp sử dụng thuật toán IMin và phương pháp sử dụng thuật toán IMinD
(Inductive Miner-incompleteness-directly-follows based). Cuối chương này là đề cập
đến ý tưởng mô hình phát hiện quy trình từ nhật ký sự kiện không đầy đủ của khóa
luận.
Chương 3: Khóa luận trình bày tổng quan và chi tiết về mô hình phát hiện quy
trình từ nhật ký sự kiện không đầy đủ, trong đó trình bày rõ từng bước thực hiện trong

mô hình đã được đề xuất.

1


Chương 4: Khóa luận trình bày thực nghiệm với dữ liệu mẫu đã thu thập được,
đồng thời đưa ra đánh giá mô hình quy trình thu được từ thực nghiệm dựa trên các độ
đo fitness, precision, generalization.
Phần kết luận: Tóm tắt kết quả đã đạt được của khóa luận và đưa ra định hướng
nghiên cứu tiếp theo trong tương lai

2


Chương 1. Phát hiện quy trình từ nhật ký sự kiện không đầy đủ
1.1. Phát hiện quy trình
1.1.1. Giới thiệu tổng quan về phát hiện quy trình
Kĩ thuật khai phá quy trình có mục đích chính là để hỗ trợ các tổ chức, doanh
nghiệp trong việc nâng cao hiệu quả quản lý quy trình kinh doanh của doanh nghiệp
đó. Hình 1.1 thể hiện sự liên kết giữa mô hình quá trình thực tế và dữ liệu ghi nhận
được. Ngày nay, các hệ thống ghi nhận dữ liệu với số lượng lớn và yêu cầu đặt ra là
làm sao chúng ta có thể sử dụng những thông tin hữu ích đó nhằm hỗ trợ và cải tiến
quá trình kinh doanh của doanh nghiệp. Theo WMP Van der Aalst [10], khai phá quy
trình bao gồm ba bài toán chính là bài toán phát hiện quá trình, kiểm tra sự phù hợp và
tăng cường mô hình. Đặc biệt, trong khóa luận chủ yếu tập trung vào bài toán phát
hiện quy trình.

Hình 1.1: Ngữ cảnh khai phá quy trình [1]
Bài toán phát hiện quy trình: đây là một kĩ thuật phát hiện quá trình từ nhật ký sự
kiện và xây dựng mô hình quy trình doanh nghiệp mà không sử dụng bất kì dữ liệu

tiền nghiệm nào trước đó, việc phát hiện quy trình thực thi chỉ dựa trên những ví dụ
hành vi được ghi lại trong nhật ký sự kiện. Thật vậy, các tập nhật ký sự kiện bao gồm
những hành vi lịch sử mà hệ thống ghi lại được trong quá trình thực thi nghiệp vụ, có
thể được sử dụng để khai phá mô hình quy trình của các quy trình xảy ra thực sự trong
hệ thống.

3


Hình 1.2: Luồng công việc tiêu biểu trong khai phá quy trình (trong [7] )
Hình 1.2 thể hiện một luồng công việc tiêu biểu trong khai phá quy trình, hệ
thống này thực thi và tạo ra một nhật ký sự kiện. Từ nhật ký sự kiện thu được, một kĩ
thuật phát hiện quy trình được đề xuất nhằm xây dựng mô hình quy trình. Bước tiếp
theo của việc xây dựng mô hình, nhật ký sự kiện được lọc, tức là các hành vi thể hiện
trong tập nhật ký sự kiện không khớp với mô hình tìm được sẽ được phân tích bằng
tay, trong khi các hành vi khớp với nhật ký sự kiện được phân tích kỹ lưỡng với mô
hình. Sau đó là bước chọn các phần đặc trưng và đi sâu vào nó sử dụng bộ lọc, cuối
cùng là một mô hình mới được phát hiện.

1.1.2. Độ đo tiêu chuẩn chất lượng của mô hình

Hình 1.3: Cân bằng bốn tiêu chí chất lượng: fitness, simplicity, precision và
generalization ([10])
Hình 1.3 định nghĩa bốn tiêu chí chính để đánh giá chất lượng mô hình là: sự phù
hợp(fitness), sự đơn giản(simplicity), sự chính xác(precision) và sự tổng
quát(generalization).
Một mô hình với sự phù hợp cao cho phép hành vi được nhìn thấy trong nhật ký
sự kiện, một mô hình có một sự phù hợp hoàn hảo nếu tất cả các vết trong nhật ký sự
kiện có thể được thể hiện bởi mô hình từ lúc bắt đầu cho đến khi kết thúc. Có nhiều
cách khác nhau để định sự phù hợp, nó có thể được định nghĩa ở mức độ trường hợp,

tức là các phần của các vết trong nhật ký sự kiện có được thể hiện đầy đủ. Hoặc, nó có

4


thể được định nghĩa ở mức độ sự kiện, tức là các phần của các sự kiện trong nhật ký sự
kiện được thể hiện như theo mô hình.
Sự đơn giản, chúng ta tìm kiếm phát hiện mô hình quy trình đơn giản nhất mà có
thể giải thích những gì quan sát được trong nhật ký sự kiện. Tính phức tập của mô hình
có thể được định nghĩa bởi số lượng các nút và các cung trong đồ thị.
Sự chính xác là cao khi các hành vi trong nhật ký sự kiện được mô tả trong mô
hình, sự tổng quát là cao khi mô hình cho phép nhiều hành vi hơn không chỉ những
hành vi trong nhật ký sự kiện.

1.2. Nhật ký sự kiện không đầy đủ
1.2.1. Nhật ký sự kiện
Nhật ký sự kiện là một đầu vào cơ bản của khai phá quy trình. Các thuật toán
phát hiện quy trình nhận đầu vào thường là một nhật ký sự kiện ở dạng cô đọng (có thể
đầy đủ hoặc không đầy đủ). Trong nhật ký sự kiện dạng cô đọng, mỗi sự kiện được
biểu diễn chỉ bằng một hoạt động được thể hiện trong sự kiện đó và mỗi trạng thái
được biểu diễn dưới dạng một vết, mỗi vết trường hợp chính là một tập phức các hoạt
động.
Để hiểu rõ và hình dung được rõ về nhật ký sự kiện, khóa luận đưa ra một đoạn
của một nhật ký sự kiện được thể hiện như trong hình 1.4 dưới đây.
Hình 1.4 đưa ra thông tin của một nhật ký sự kiện ghi lại diễn biến quy trình
nghiệp vụ xử lý đơn bồi thường của một hãng hàng không, "register request"- a,
"examine thoroughly"-b, "examine casually"- c, "check ticket"- d, "decide"- e,
"reinititate request"- f, "pay compensasion"- g và "reject request"- h.

5



Hình 1.4: Một đoạn nhật ký sự kiện [10]
 Sự kiện (event): sự kiện là một lần thực thi một hành động cụ thể trong thực
tế. Khi khách hàng nào đó nộp đơn đăng ký đòi bồi thường, một sự kiện
tương ứng với hoạt động ghi nhận đơn đăng ký (register request) được thực
hiện trong một thời gian nhất định, do một người cụ thể thực hiện, sử dụng
tài nguyên và là một bước trong toàn bộ quá trình xử lý đơn đăng ký. Các
thông tin liên quan tới một sự kiện được gọi là thuộc tính hay đặc trưng của
sự kiện đó, tiêu biểu trong hình 1.4 là “case id”, “event id” biễu diện một sự
kiện với chỉ số sự kiện tương ứng, “Timestamp”(thời gian sự kiện),
“Activity”(hoạt động trong sự kiện), “Resource”(tác nhân thực hiện hoạt
động), “Cost”(chi phí thực hiện sự kiện).

6


 Trường hợp (case): là dãy bao gồm các hoạt động được thực hiện trong một
lần xử lý cụ thể đối với nghiệp vụ quy trình. Ví dụ như trong hình 1.4 đưa
ra, một trường hợp tức là bao gồm các hành vi từ khi khách hàng nộp đơn
đến khi đơn được xử lý xong. Vết (trace) của một trường hợp là dãy có thứ
tự các hoạt động thuộc trường hợp đó. Như trong hình 1.4, đối với trường
hợp một ta thu được một vết là check ticket, dicide, reject request> hay kí hiệu tương ứng là <a, b, d, e, h>,
đây là dạng trình bày cô đọng của trường hợp. Một vết có thể được kí hiệu
bởi . Một nhât ký sự kiện là một tập các vết L={1, 2, 3,.. }

Hình 1.5: Dạng cô đọng của một nhật ký sự kiện bao gồm các vết trường hợp [10]

1.2.2. Tính không đầy đủ của nhật ký sự kiện

Để phát hiện một mô hình quy trình phù hợp nếu giả định là nhật ký sự kiện bao
gồm một mẫu hành vi mang tính đại diện cho mô hình quy trình thực tế. Có hai hiện
tượng liên quan mà có thể làm giảm tính đại diện của nhật ký sự kiện cho việc phát
hiện quy trình:
 Nhiễu (noise): tức là nhật ký sự kiện bao gồm hành vi hiếm khi và không
thường xuyên, không mang tính đại diện cho các hành vi đặc trưng của quy
trình.
 Tính không đầy đủ (incompleteness): tức là nhật ký sự kiện bao gồm quá ít
các sự kiện để có thể phát hiện một vài cấu trúc luồng cơ bản.
Trong khi nhiễu nói đến vấn đề của nhật ký sự kiện có quá nhiều dữ liệu (mô tả
hành vi hiếm khi xảy ra) thì tính không đầy đủ nói đến vấn đề có quá ít dữ liệu. Nhật
7


ký sự kiện không đầy đủ có thể xảy ra trong các mô hình quy trình thực tế bởi các lý
do về hệ thống hay con người mà có thể có các trường hợp, hành vi không được thể
hiện trong nhật ký sự kiện.
Để minh họa tính xác đáng của tính đầy đủ, chúng ta xét một quy trình bao gồm
10 hành vi mà có thể được thực thi song song và một nhật ký sự kiện tương ứng bao
gồm thông tin về 10000 vết. Tổng số các trường hợp có thể có trong mô hình với 10
hoạt động đồng thời là 10! = 3628800. Vì vậy, không thể thực hiện được với mỗi
trường hợp được thể hiện trong nhật ký sự kiện bởi vì có ít các trường hợp (10000)
hơn các vết có khả năng (3628800). Ngay cả khi có 3628800 trường hợp trong nhật ký
sự kiện, nó là quá lớn để có thể được thể hiện. Cho một quy trình với 10 hoạt động có
thể được thực hiện đồng thời, một khái niệm cục bộ của tính đầy đủ có thể làm giảm
số yêu cầu được quan sát. Ví dụ, đối với thuật toán  chỉ có 10 *(10 - 1) = 90 hơn là
3628800 trường hợp khác nhau cần để xây dựng mô hình [8]
Ví dụ về nhật ký sự kiện không đầy đủ:
Giả sử nhật ký sự kiện L được mô tả với ba vết như sau: L = ({As, Ac, Bs, Bc,
Cs, Cc, Ds, Dc}, {As, Ac, Bs, Bc, Cs, Cc, Ds, Dc}, {As, Ac, Cs, Cc, Bs, Bc, Ds, Dc}.

Theo như mô hình quy trình trong hình 1.6, nhật ký sự kiện L là không đầy đủ nếu giả
sử B và C là quan hệ song song trong thực tế nhưng không được thể hiện trong nhật ký
sự kiện này, tức là nếu chỉ xem xét đến các sự kiện bắt đầu và kết thúc thì sẽ là phù
hợp nhưng nếu B và C là quan hệ song song thì cần có nhiều vết hơn nữa để suy ra
quan hệ song song của B và C.

Hình 1.6: Ví dụ mô hình lưới luồng công việc

8


1.3. Phát hiện quy trình từ nhật ký sự kiện không đầy đủ
1.3.1. Lưới Petri, Cây quy trình và Đồ thị luồng có hướng
Lưới Petri
Lưới Petri là ngôn ngữ mô hình hóa quá trình lâu nhất và cũng được nghiên cứu
tốt nhất cho phép mô hình hóa được những sự kiện. Lưới Petri có thể được thực thi và
nhiều kĩ thuật phân tích có thể được sử dụng để phân tích. Lưới Petri được thiết kế và
đề xuất bởi Carl Adam Petri 1962 trong luận án tiến sĩ của ông. Ý tưởng chính là mô tả
sự chuyển trạng thái trong một hệ thống với những thanh chuyển.
Định nghĩa 1.1(Lưới Petri): là một bộ 3 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 = Ø
F (PT)È(TP) là tập các cung trực tiếp, gọi là luồng quan hệ.
Thành phần P È T được gọi là các nút (nodes)
Ví dụ một lưới Petri được thể hiện trong hình 1.7 trong đó:
P = {p1,p2, p3, p4, p5, p6}, T = {t1, t2, t3, t4} và
F={(p1,t1),(t1,p2),(p2,t2),(t2,p1),(t1,p3),(p3,t3),(t3,p5),(p5,t4),(t4,p4),(p4,t2),(t4,p6),(p
6,t3)}

Hình 1.7: Ví dụ lưới Petri [8]

Nếu N = (P, T, F) là một lưới Petri. Một nốt x là nốt đầu vào của nốt y nếu có
cung đi từ x sang y. Nốt x được gọi là đầu ra của nốt y nếu có cung đi từ y sang x. Ví
dụ trong hình 1.7, p3 và p6 là nốt vào của t3, p5 là nốt ra của t3.
Lưới luồng công việc (WP-net) là một lưới Petri có một đầu vào và một đầu ra
duy nhất thể hiện trạng thái ban đầu và kết thúc của hệ thống. Mỗi phần tử nằm trên
một đường từ đầu vào đến đầu ra. Quy trình được thực thi tuần tự từ trạng thái đầu đến

9


trạng thái cuối của hệ thống tương ứng với một vết. Một tập các vết được xây dựng bởi
mô hình M.
Cây quy trình
Theo Sander J. J. Leemans [6], một cây quy trình là một thể hiện trừu tượng phân
cấp của một lưới luồng công việc cấu trúc khối. Lá của cây là các hoạt động, đại diện
cho các chuyển. Nốt của cây là các toán tử, mô tả cách các con của nó được kết hợp
như thế nào. Có bốn toán tử được sử dụng : × – thể hiện lựa chọn loại trừ giữa các con
của nó, → - mô tả quan hệ tuần tự,

- mô tả thành phần song song và Q- mô tả vòng

lặp.

Hình 1.8: Cây quy trình →( × ( (a, b), c), × (Q (→ (d, e), f), g)) tương ứng với lưới
[6]
Kí hiệu Å để thể hiện một tập các toán tử và kí hiệu Å để kí hiệu một toán tử cây
quy trình: Å Î Å, Å = {×, →,

, Q}. Để định nghĩa ngữ nghĩa của cây quy trình, giả

sử một tập các hành vi å được đưa ra. Cách thể hiện của một hành vi là sự thực thi của
hành vi đó. Thể hiện của hành vi tĩnh  chỉ bao gồm vết rỗng, tức là sự thực hiện  sẽ
không thêm gì vào nhật ký sự kiện.
Mỗi cây quy trình là dễ dàng được chuyển thành một lưới luồng công việc đúng
đắn. Để một cây quy trình được chuyển thành lưới Petri thì một ánh xạ được đưa ra
giữa các lá của cây quy trình và các chuyển trong lưới Petri. Ví dụ, trong hình 1.8 thể
hiện, một ví dụ về sự chuyển từ cây quy trình thành lưới Petri, lưới luồng công việc
tương ứng với cây quy trình ME = →(× ( (a, b), c), × (Q (→ (d, e), f), g)).
Quan hệ luồng có hướng (Directly- Follows Relation)
Quan hệ luồng có hướng → được giới thiệu trong [6] như là một trừu tượng hóa
của hành vi được mô tả bởi mô hình hoặc nhật ký sự kiện. Từ một mô hình M, chúng
10


ta lấy hai hoạt động a và b bất kì. Nếu b theo sau a trong M, tức là <..,a,b,..>, thì kí
hiệu a →M b.
Một đường → là một tuần tự của các hoạt động a1, a2, …, ak với k ≥ 2. Bao đóng
của nó được kí hiệu là →+, ví dụ với hai hoạt động a, b thì quan hệ a →+ b nếu tồn tại
một đường → từ a tới b. Theo Sander J.J Leemans[6] đưa ra ví dụ về đồ thị quan hệ
luồng có hướng và bao đóng như thể hiện trong hình 1.9a và 1.9b:

Hình 1.9a: Đồ thị quan hệ luồng có hướng Hình 1.9b:Đồ thị bao đóng của đồ thị 1.9a

1.3.2. Sơ bộ về các phương pháp phát hiện quy trình từ nhật ký sự kiện
không đầy đủ
Bài toán phát hiện quy trình từ nhật ký sự kiện không đầy đủ nhận đầu vào là
một nhật ký sự kiện và đầu ra là mô hình quá trình tương ứng. Mô hình được tạo ra
cần phù hợp nhất với nhật ký sự kiện để làm đầu vào cho bài toán kiểm tra tính phù
hợp cũng như bài toán tăng cường mô hình. Với các yêu cầu đặt ra là khá quan trọng
và cần thiết cùng với thách thức đối với tập nhật ký sự kiện không đầy đủ, Sander J.J

Leemans và cộng sự [6] đã đề xuất sử dụng xác suất trong việc tính các quan hệ hành
vi để xây dựng cây quy trình. Với cách tiếp cận chia để trị và phỏng theo ý tưởng của
thuật toán IM [5] để đưa ra một thuật toán phát hiện mới đối với nhật ký sự kiện không
đầy đủ là IMin sẽ được trình bày cụ thể trong chương hai của khóa luận.
Sau đó, Sander J.J. Leemans và cộng sự [7] đã đề xuất ý tưởng trong việc phát
hiện quy trình sử dụng một đồ thị luồng có hướng. Kĩ thuật được giới thiệu là một

11


khung được phỏng theo thuật toán IM dựa trên đồ thị luồng có hướng. Kĩ thuật này áp
dụng đệ quy trên đồ thị luồng có hướng. Đối với nhật ký sự kiện không đầy đủ thì
IMinD được đề xuất, dựa trên ý tưởng của IMin trong [6] trong khung IMD sẽ được đề
cập cụ thể trong chương hai của khóa luận.

1.4. Sơ bộ bài toán của khóa luận
Trong phần trên của khóa luận đã đưa ra sơ bộ về một số ý tưởng của Sander J.J.
Leemans và cộng sự về bài toán phát hiện quy trình từ nhật ký sự kiện không đầy đủ.
Cụ thể trong mục này của khóa luận sẽ cụ thể hóa bài toán phát hiện quy trình sử dụng
nhật ký sự kiện không đầy đủ của khóa luận.
Bài toán của khóa luận được đưa ra với đầu vào là một nhật ký sự kiện không
đầy đủ được ghi lại bởi hệ thống. Nhật ký sự kiện này mô tả các hành vi thực hiện
được trong hệ thống. Đầu ra là một mô hình quy trình mô tả đầy đủ các hành vi được
thể hiện trong nhật ký sự kiện không đầy đủ. Khóa luận này áp dụng kĩ thuật đã được
đưa ra bởi Sander J.J Leemans và cộng sự [6], kĩ thuật sử dụng xác suất quan hệ để
tính mối quan hệ giữa các hành vi hệ thống, từ đó xây dựng mô hình phù hợp nhất sử
dụng nhật ký sự kiện không đầy đủ được cung cấp.

Tóm tắt chương 1
Trong chương một của khóa luận đã trình bày khái quát về khai phá quy trình và

bài toán phát hiện quy trình. Bên cạnh đó, khóa luận trình bày về các khái niệm cơ bản
trong bài toán phát hiện quy trình bao gồm nhật ký sự kiện, nhật ký sự kiện không đầy
đủ, lưới Petri, cây quy trình. Đồng thời, khóa luận cũng đưa ra cái nhìn sơ bộ về các
phương pháp phát hiện quy trình từ nhật ký sự kiện không đầy đủ từ các nghiên cứu
của Sander J.J. Leemans và cộng sự [5][6][7] và trình bày khái quát bài toán phát hiện
quy trình của khóa luận. Trong chương hai, khóa luận sẽ đi vào trình bày cụ thể từng
phương pháp sử dụng thuật toán IMin [6] và IMinD [7] và đề xuất phương pháp được
thực hiện trong khóa luận.

12