BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

ĐỖ PHAN TRƯỜNG

NGHIÊN CỨU KỸ THUẬT KHAI PHÁ QUY TRÌNH
VÀ ỨNG DỤNG ĐỂ PHÂN TÍCH QUY TRÌNH
U CẦU BỒI THƯỜNG TẠI SÂN BAY

LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Đà Nẵng - Năm 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

ĐỖ PHAN TRƯỜNG

NGHIÊN CỨU KỸ THUẬT KHAI PHÁ QUY TRÌNH
VÀ ỨNG DỤNG ĐỂ PHÂN TÍCH QUY TRÌNH
U CẦU BỒI THƯỜNG TẠI SÂN BAY

Chuyên ngành: HỆ THỐNG THÔNG TIN
Mã số: 60.48.01.04

LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Người hướng dẫn khoa học: TS. PHẠM ANH PHƯƠNG

Đà Nẵng - Năm 2016

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn nghiên cứu kỹ thuật khai phá quy trình và
ứng dụng phân tích quy trình xử lý yêu cầu bồi thƣờng ở sân bay là do tôi
thực hiện dƣới sự hƣớng dẫn của TS Phạm Anh Phƣơng.
Tất cả các tài liệu tham khảo từ các nghiên cứu liên quan đến luận văn
đều đƣợc nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo.
Trong luận văn, khơng có việc sao chép tài liệu, cơng trình nghiên cứu của
ngƣời khác mà không ghi rõ tài liệu tham khảo.
TÁC GIẢ

Đỗ Phan Trƣờng


MỤC LỤC
MỞ ĐẦU ..............................................................................................................1
1.

Tính cấp thiết của đề tài ................................................................................1

2.

Mục tiêu nghiên cứu ......................................................................................2

3.

Đối tƣợng và phạm vi nghiên cứu .................................................................2

4.


Phƣơng pháp nghiên cứu ...............................................................................3

5.

Bố cục đề tài ..................................................................................................3

CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH...........................4
1.1. GIỚI THIỆU CHUNG VỀ KHAI PHÁ QUY TRÌNH .................................4
1.2. MƠ HÌNH QUY TRÌNH VÀ PHÂN TÍCH MƠ HÌNH THEO QUY
TRÌNH ...................................................................................................................6
1.2.1. Mơ hình hóa quy trình...........................................................................6
1.2.2. Một số ngơn ngữ mơ hình quy trình .....................................................7
1.2.3. Phân tích quy trình dựa trên mơ hình ...................................................8
1.2.4. Giới hạn của phân tích quy trình dựa trên mơ hình ..............................9
1.2.5. Các thao tác nhật ký sự kiện và mơ hình quy trình ............................10
1.3. BÀI TỐN PHÁT HIỆN QUY TRÌNH .....................................................11
1.3.1. Nhật ký sự kiện ...................................................................................11
1.3.2. Phát hiện quy trình ..............................................................................14
1.4. KIỂM TRA PHÙ HỢP ................................................................................17
1.4.1. Bài tốn kiểm tra phù hợp ...................................................................17
1.4.2. Kiểm tra phù hợp theo trƣờng hợp replay ..........................................19
1.4.3. Kiểm tra phù hợp theo so sánh vết......................................................22
1.4.4. Ứng dụng khác của kiểm tra phù hợp. ................................................22
1.5. MỞ RỘNG QUY TRÌNH ...........................................................................24
1.5.1. Thêm quan điểm tổ chức.....................................................................25
1.5.2. Thêm quan điểm thời gian và xác suất ...............................................29


1.5.3. Thêm quan điểm trƣờng hợp...............................................................30

1.6. KẾT LUẬN CHƢƠNG I ............................................................................31
CHƢƠNG II. MỘT SỐ THUẬT TỐN KHAI PHÁ QUY TRÌNH ..........32
2.1. THUẬT TỐN ALPHA .............................................................................32
2.1.1. Đầu vào của thuật tốn ........................................................................32
2.1.2. Thuật toán: ..........................................................................................34
2.1.3. Ý tƣởng của thuật toán Alpha .............................................................35
2.1.4. Giới hạn của thuật tốn Alpha. ...........................................................36
2.2. THUẬT TỐN KHAI PHÁ QUY TRÌNH HEURISTIC (HM) ................41
2.2.1. Đầu vào và đầu ra của thuật toán. .......................................................41
2.2.2. Thuật toán khai phá quy trình Heuristic .............................................43
2.2.3. Kết luận thuật tốn khai phá quy trình Heuristic ................................56
2.3. THUẬT TỐN KHAI PHÁ QUY TRÌNH DI TRUYỀN (GPM) .............57
2.3.1. Thuật toán di truyền (GA)...................................................................57
2.3.2. Một số lựa chọn thiết kế cần thực hiện ...............................................60
2.3.3. Kết luận thuật tốn khai phá quy trình di truyền ................................65
2.4. KẾT LUẬN CHƢƠNG 2 ............................................................................65
CHƢƠNG III. ỨNG DỤNG KHAI PHÁ QUY TRÌNH XỬ LÝ YÊU
CẦU BỒI THƢỜNG TẠI SÂN BAY. .............................................................67
3.1. BÀI TỐN KHAI PHÁ QUY TRÌNH XỬ LÝ U CẦU BỒI
THƢỜNG TẠI SÂN BAY..................................................................................67
3.1.1. Đầu vào của bài toán ...........................................................................67
3.1.2. Đầu ra của bài toán .............................................................................69
3.1.3. Hƣớng giải quyết bài tốn ...................................................................69
3.2. CƠNG CỤ KHAI PHÁ QUY TRÌNH PROM ............................................69
3.2.1. Giới thiệu chung về công cụ khai phá quy trình ProM.......................69
3.2.2. Các chức năng của cơng cụ khai phá quy trình ProM ........................70


3.3. THỰC NGHIỆM KHAI PHÁ QUY TRÌNH XỬ LÝ YÊU CẦU BỒI
THƢỜNG TẠI SÂN BAY..................................................................................75

3.3.1. Khai phá quy trình xử lý yêu cầu bồi thƣờng bằng thuật toán
Alpha .............................................................................................................75
3.3.2. Khai phá quy trình xử lý yêu cầu bồi thƣờng bằng thuật tốn
Heuristic mining. ...............................................................................................77

3.3.3. Khai phá quy trình u cầu bồi thƣờng bằng thuật tốn khai phá quy
trình di truyền. ...................................................................................................79
3.3.4. Đánh giá các thuật toán .......................................................................82
3.4. KẾT LUẬN CHƢƠNG 3 ............................................................................84
KẾT LUẬN ........................................................................................................85
TÀI LIỆU THAM KHẢO ................................................................................87
QUYẾT ĐỊNH GIAO ĐỀ TÀI (BẢN SAO)


DANH MỤC CÁC CHỮ VIẾT TẮT
BPM

Business Process Management

BPMN

Business Process Modeling Notation

C-net

Causal Net

CRM

Customer Relationship Management


DG

Dependency Graph

EmiT

Enhanced Mining Tool

EPC

Event-driven Process Chain

ERP

Enterprise Resource Planning

FHM

Flexible Heuristics Miner

GPM

Genetic Process Mining

HM

Heuristics Miner

MXML


Mining eXtensible Markup Language

PNML

Petri Net Markup Language

SCM

Software Configuration Management

SWF-net

Structured Workflow Net

WFM

Workflow management

WF-net

Workflow Nets

XES

eXtensible Event Stream

YAWL

Yet Another Workflow Language



DANH MỤC CÁC BẢNG
Bảng 1.1: Một ví dụ bảng ghi sự kiện ..................................................... 12
Bảng 1.2: Một cách biểu diễn gọn hơn của bản ghi sự kiện. .................. 13
Bảng 1.3: Một bản ghi sự kiện đơn giản với thông tin nguồn lực đƣợc
làm nổi bật. ..................................................................................................... 26
Bảng 1.4: Bảng nguồn lực hoạt động cho thấy thời gian trung bình một
ngƣời thực hiện một hoạt động cho mỗi trƣờng hợp ...................................... 26
Bảng 2.1: Ví dụ về một bảng in vết ........................................................ 33
Bảng 2.2: Chuyển đổi một mạng Petri trong hình 2.8 thành một C-net . 43
Bảng 2.3: Đếm tần suất xuất hiện của các mối quan hệ nhân quả giữa các
hoạt động ......................................................................................................... 47
Bảng 2.4: Đếm số vịng lặp có độ dài 2 (tức là đếm a >>w b). ............... 47
Giá trị 89 tại vị trí D,F cho biết có 89 mẫu DF trong bản ghi sự kiện.... 47
Bảng 2.5: Hiển thị độ phụ thuộc giữa các hoạt động.............................. 49
Bảng 2.6: Đồ thị phụ thuộc kết quả đƣợc suy ra từ bảng 2.5. ................ 49
Bảng 2.7: Một C-net mở rộng đối với đồ thị phụ thuộc của bảng 2.6 với
sự liên kết các bản ghi sự kiện với 1000 vết. .................................................. 52
Bảng 3.1: Bản ghi sự kiện LFull ............................................................... 68
Bảng 3.2: So sánh, đánh giá các thuật toán đã thực nghiệm .................. 82


DANH MỤC CÁC HÌNH VẼ
Hình 1.1: Sơ đồ khai phá quy trình. .......................................................... 5
Hình 1.2: Ba sự liên quan giữa các bản ghi sự kiện và quy trình mơ hình:
Play-in, Play-out, và Replay............................................................................ 10
Hình 1.3: WF-net N2 đƣợc phát hiện cho L2.......................................... 15
Hình 1.4: Vấn đề phát hiện lại quy trình................................................. 16
Hình 1.5: Kiểm tra phù hợp. ................................................................... 18

Hình 1.6: kiểm tra sự phù hợp cung cấp các biện pháp phù hợp tồn cục
và chẩn đốn địa phƣơng. ............................................................................... 21
Hình 1.7: Mơ hình tích hợp ..................................................................... 25
Hình 1.8: Một mạng xã hội bao gồm các nút đại diện cho các tổ chức và
cung đại diện cho mối quan hệ........................................................................ 27
Hình 1.9: Mơ hình tổ chức đƣợc phát hiện dựa trên bản ghi sự kiện ..... 28
Hình 2.1: Một mơ hình quy trình đƣợc khai phá từ bản ghi sự kiện đƣợc
mơ tả nhƣ bảng 1.2 bằng thuật tốn Alpha. .................................................... 35
Hình 2.2: Mối liên hệ giữa bản ghi sự kiện với cấu trúc mạng Petri cơ
bản dựa trên các mối quan hệ >W, →W, ||W v{ #W...................................... 36
Hình 2.4: Một mơ hình quy trình với các hoạt động trùng lặp. .............. 37
Hình 2.5: Một mơ hình quy trình với cấu trúc khơng tự do lựa chọn..... 38
Hình 2.6: Mơ hình quy trình có vịng lặp ngắn độ dài 1 ......................... 39
Hình 2.7: Mơ hình quy trình có vịng lặp ngắn độ dài 2 ......................... 39
Hình 2.8: Mơ hình mạng Petri đƣợc sử dụng để tạo ra một bản ghi sự
kiện. ................................................................................................................. 42
Hình 2.9: Đồ thị phụ thuộc kết quả khi sử dụng các tham số mặc định. 50
Hình 2.10: Đồ thị phụ thuộc kết quả khi thiết lập tham số σa = 0.80 và
σr = 0.2. ........................................................................................................... 51
Hình 2.11: Một mơ hình quy trình dƣới dạng mạng Petri với cấu trúc phụ
thuộc khoảng cách xa ...................................................................................... 54


Hình 2.12: Sự tƣơng ứng của DG với hình 2.11 mà khơng có mối quan
hệ phụ thuộc khoảng cách xa. ......................................................................... 54
Hình 2.13: DG tƣơng ứng với hình 2.12 với quan hệ đồ thị phụ thuộc
khoảng cách xa. ............................................................................................... 56
Hình 2.14: Tổng quan về hƣớng tiếp cận sử dụng khai phá di truyền.... 58
Hình 2.15: Hai mơ hình bố mẹ (trên) và hai mơ hình con là kết quả từ
phép giao nhau. ............................................................................................... 64

Hình 2.16: Mơ tả q trình đột biến, một vị trí bị loại bỏ và một cung
mới đƣợc thêm vào .......................................................................................... 64
Hình 3.1: Tổng quan về khung ứng dụng ProM ..................................... 70
Hình 3.2: Các tùy chọn đối với dữ liệu đầu vào là bản ghi sự kiện........ 71
Hình 3.3: Giao diện làm việc trên ProM 5.2 ........................................... 72
Hình 3.4: Giao diện chức năng quản lý gói flugin của ProM 6.5 ........... 73
Hình 3.5: Kết quả khai phá quy trình xử lý yêu cầu bồi thƣờng tại sân
bay bằng thuật tốn Alpha............................................................................... 75
Hình 3.6: Kết quả nhân đƣợc khi khai phá với bản ghi sự kiện có lỗi. .. 76
Hình 3.7: Mơ hình kết quả khai phá quy trình bằng thuật tốn HM khi sử
dụng các tham số mặc định ............................................................................. 77
Hình 3.8: Mơ hình kết quả khai phá quy trình bằng thuật tốn HM khi
thiết lập tham số σa = 0.90 và σr = 0.1 ........................................................... 78
Hình 3.9: Kết quả khai phá với bản ghi có sự kiện lỗi và hoạt động trùng
lặp .................................................................................................................... 79
Hình 3.10: Các tham số thiết lập khi thực hiện thuật toán khai phá quy
trình di truyền .................................................................................................. 80
Hình 3.11: Một cá thể có độ phù hợp gần bằng 1 ................................... 81
Hình 3.12: Một cá thể có độ phù hợp thấp. ............................................ 81
Hình 3.13: So sánh thời gian thực hiện và độ phù hợp của mơ hình kết
quả của ba thuật tốn Alpha, HM, GPM ......................................................... 83


1

MỞ ĐẦU
1. Tính cấp thiết của đề tài
Trong mọi lĩnh vực hoạt động, bất kỳ một cơ quan, tổ chức, doanh
nghiệp nào dù lớn hay nhỏ muốn thực hiện các cơng việc của mình đều phải
thực hiện theo các quy trình nghiệp vụ định sẵn. Cùng với sự phát triển của

cơng nghệ thơng tin, ngày càng có nhiều thơng tin về các quy trình nghiệp vụ
đƣợc lƣu lại trong các hệ thống thông tin dƣới dạng các bản ghi sự kiện, các
bản ghi sự kiện này có đặc điểm là nó phản ánh một cách trung thực, chính
xác những gì đã xảy ra trong thực tế. Tuy nhiên, cho đến gần đây, các thơng
tin này ít khi đƣợc các tổ chức, doanh nghiệp sử dụng để phân tích việc thực
hiện các quy trình nghiệp vụ cơ bản của cơ quan, tổ chức, doanh nghiệp mình.
Ý tƣởng của khai phá quy trình nghiệp vụ là trích xuất thơng tin từ các bản
ghi sự kiện để khai phá ra các mơ hình quy trình nghiệp vụ. Những mơ hình
này có thể đƣợc dùng để phân tích các quy trình, phát hiện những vấn đề sai
lệch từ đó đề xuất điều chỉnh, thiết kế lại quy trình một cách chính xác hơn
mang lại hiệu quả cơng tác cao hơn. Với những lợi ích mà nó mang lại, khai
phá quy trình đang trở thành một trong những hƣớng nghiên cứu thu hút đƣợc
sự quan tâm của các nhà nghiên cứu lĩnh vực quản lý quy trình nghiệp vụ
(BPM) và giới nghiên cứu khoa học máy tính. Trong những năm gần đây, bên
cạnh việc nghiên cứu cải tiến các giải thuật khai phá quy trình, các nhà nghiên
cứu trên thế giới đang tập trung nghiên cứu ứng dụng các kỹ thuật khai phá
quy trình vào các lĩnh vực cụ thể nhƣ lĩnh vực y tế, giáo dục, tài chính kinh
doanh, thƣơng mại v.v… Ngày càng có nhiều nhà cung cấp phần mềm bổ
sung chức năng khai thác quy trình vào các cơng cụ của họ.
Từ sự cấp thiết đó, luận văn thực hiện nghiên cứu tổng quan về kỹ thuật
khai phá quy trình và một số thuật tốn khai phá quy trình để đem đến cái
nhìn rõ ràng hơn về kỹ thuật này. Bên cạnh đó, luận văn thực nghiệm kỹ thuật


2

khai phá quy trình đối với quy trình xử lý yêu cầu bồi thƣờng ở sân bay. Đây
là một quy trình đơn giản, thực nghiệm khai phá quy trình này có thể giúp
minh họa rõ hơn kỹ thuật này cũng nhƣ các thuật tốn khai phá quy trình.
2. Mục tiêu nghiên cứu

- Tìm hiểu một cách tổng quan về khai phá quy trình nghiệp vụ.
- Nghiên cứu một số thuật tốn sử dụng trong khai phá quy trình nghiệp
vụ. Qua đó so sánh, đánh giá ƣu và nhƣợc điểm của các thuật tốn.
- Sử dụng các thuật tốn và cơng cụ khai phá quy trình nghiệp vụ để
minh họa ứng dụng khai phá quy trình xử lý yêu cầu bồi thƣờng tại sân bay
với dữ liệu thực tế đƣợc mô tả trong tài liệu W.M.P. van der Aalst (2011),
Process Mining: Discovery, Conformance and Enhancement of Business
Processes, Springer - Verlag, Berlin .
3. Đối tƣợng và phạm vi nghiên cứu
Đối tượng nghiên cứu
- Kỹ thuật khai phá quy trình.
- Các thuật tốn khai phá quy trình.
- Cơng cụ khai phá quy trình ProM.
Phạm vi nghiên cứu
- Tập trung nghiên cứu một số thuật tốn ứng dụng trong khai phá quy
trình nghiệp vụ.
- Sử dụng bộ dữ liệu sự kiện quy trình đăng kí u cầu bồi thƣờng tại sân
bay đƣợc trình bày trong tài liệu W.M.P. van der Aalst (2011), Process
Mining: Discovery, Conformance and Enhancement of Business Processes,
Springer - Verlag, Berlin để mơ phỏng kỹ thuật khai phá quy trình.
- Phương pháp thu thập thơng tin: Tìm kiếm tài liệu từ sách, giáo trình,
báo cáo, internet.


3

4. Phƣơng pháp nghiên cứu
- Phương pháp so sánh: Tổng hợp và đối chiếu giữa những tài liệu thu
đƣợc để đƣa ra một cái nhìn tổng quan nhất về kỹ thuật khai phá quy trình và
các thuật tốn khai phá quy trình.

- Phương pháp chuyên gia: Tham vấn từ những ngƣời có kinh nghiệm
nhằm hồn thiện các nội dung cần nghiên cứu.
- Phương pháp thực nghiệm: Thực nghiệm khai phá quy trình xử lý yêu
cầu bồi thƣờng của khách ở sân bay.
5. Bố cục đề tài
- Chương 1: Tổng quan về khai phá quy trình, sẽ giới thiệu ý tƣởng,
mục đích của khai phá quy trình nghiệp vụ, giới thiệu kỹ thuật mơ hình quy
trình và một số hạn chế của các kỹ thuật đó, giới thiệu các bài tốn của khai
phá quy trình. Q đó, cho thấy ý nghĩa và tầm quan trọng của việc ứng dụng
khai phá quy trình nghiệp vụ tại các cơ quan, doanh nghiệp…
- Chương 2: Một số thuật tốn khai phá quy trình, giới thiệu chi tiết ba
trong số các thuật toán thƣờng đƣợc sử dụng trong khai phá quy trình nghiệp
vụ, đó là: thuật tốn khai phá quy trình Anpha, thuật tốn khai phá quy trình
Heuristic và thuật tốn khai phá quy trình di truyền, qua đó so sánh đánh giá
ƣu, nhƣợc điểm của từng thuật toán.
- Chương 3: Ứng dụng khai phá quy trình xử lý yêu cầu bồi thường tại
sân bay, sẽ giới thiệu một cách tổng quan về công cụ khai phá quy trình
ProM. Qua đó ứng dụng ProM để khai phá quy trình xử lý yêu cầu bồi thƣờng
tại sân bay bằng các thuật tốn đã đƣợc trình bày ở chƣơng 2. Kết quả khai
phá sẽ góp phần mơ tả chi tết và đánh giá cụ thể hơn ƣu nhƣợc điểm của các
thuật tốn khai phá quy trình đã đƣợc trình bày.
- Phần Kết luận tổng kết những kết quả đã đạt đƣợc và đƣa ra hƣớng
phát triển của luận văn trong tƣơng lai.


4

CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH
1.1.


GIỚI THIỆU CHUNG VỀ KHAI PHÁ QUY TRÌNH
Trƣớc khi tập trung vào kỹ thuật khai phá quy trình, ta lƣớt qua một số

kỹ thuật và mơ hình liên quan. Hệ thống quản lý quy trình nghiệp vụ (BPM),
hệ thống quản lý luồng công việc (WFM) là hệ thống cho phép chúng ta xác
định và điều khiển luồng công việc của một quy trình, hệ thống hoạch định
nguồn lực doanh nghiệp (ERP), hệ thống quản lý mối quan hệ với khách hàng
(CRM), công cụ quản lý cấu hình phần mềm (SCM)... Những hệ thống thơng
tin khác nhau này đều có một điểm chung đó là tất cả các hoạt động của
chúng đều đƣợc ghi lại trong bản ghi sự kiện. Các bản ghi đƣợc ghi lại bởi các
hệ thống thơng tin nói trên chứa dữ liệu về các sự kiện, các giao dịch, các
trƣờng hợp ngoại lệ trong quá trình thực hiện quy trình. Các bản ghi này phản
ánh các quy trình thực của nó một cách trung thực nhất, nghĩa là chúng phản
ánh đúng thực tế.
Khai phá quy trình trong phạm vi của các quy trình luồng cơng việc
đƣợc giới thiệu đầu tiên bởi Agrawal et al vào năm 1998. Tuy nhiên, thuật
ngữ khai phá luồng cơng việc hay cịn gọi là khai phá quy trình chính thức
đƣợc đƣa ra vào năm 1999 bởi Ton Weijters và Van der Aalst. Theo Van der
Aalst: Ý tưởng của khai phá quy trình là để khám phá, giám sát và cải thiện
quy trình thực sự của nó bằng cách trích xuất tri thức từ những bản ghi sự
kiện có sẵn trong các hệ thống thơng tin ngày nay [6].
Cụ thể hơn theo A. Rozinat, I.S.M. de Jong, C.W. G"unther, và W.M.P.
van der Aalst, 2007: ý tưởng cơ bản của khai phá quy trình là nghiên cứu từ
những hoạt động quan sát được của một quy trình và dùng nó để
(i) : khám phá mơ hình mới,
(ii) : kiểm tra tính phù hợp của mơ hình bằng cách kiểm tra xem trạng
thái của mơ hình đó có phù hợp với trạng thái mơ hình được quan sát hay


5


khơng?
(iii): mở rộng mơ hình đang có bằng cách sắp xếp thơng tin được trích
xuất từ những bản ghi vào một số mơ hình ban đầu [6].

Hình 1.1: Sơ đồ khai phá quy trình.
Hình 1.1 cho chúng ta thấy quá trình khai phá quy trình và các mối quan
hệ giữa các thực thể nhƣ là hệ thống thông tin, quy trình hoạt động, các bản
ghi sự kiện và mơ hình quy trình. Khai phá quy trình thiết lập liên kết, một mặt
giữa quy trình thực tế và dữ liệu của chúng, mặt khác giữa quy tình thực tế và
mơ hình quy trình. Các hệ thống thơng tin ngày nay ghi lại một lƣợng lớn các
dữ liệu về quá trình hoạt động. Dữ liệu này đƣợc mô tả nhƣ là bản ghi sự kiện
ở sơ đồ trên.
Chiết tách dữ liệu là một phần không thể thiếu của bất kỳ nỗ lực khai
thác quy trình nào bởi vì dữ liệu đƣợc lƣu trong các hệ thống thông tin thƣờng
không đƣợc cấu trúc sẵn.


6

Bản ghi sự kiện đƣợc sử dụng trong ba loại khai phá quy trình. Đó là
phát hiện quy trình, kiểm tra phù hợp, và cải thiện quy trình nhƣ đã trình bày
ở định nghĩa phía trên. Ba hoạt động khai phá quy trình này sẽ đƣợc trình bày
chi tiết ở các phần sau.
1.2.

MƠ HÌNH QUY TRÌNH VÀ PHÂN TÍCH MƠ HÌNH THEO

QUY TRÌNH
Sự phát triển của các kỹ thuật, ngơn ngữ mơ hình hóa quy trình cho thấy

sự quan trọng của q trình mơ hình hóa quy trình. Ngày nay, hầu hết các mơ
hình quy trình đƣợc thực hiện bằng tay và khơng dựa trên một phân tích
nghiêm ngặt của dữ liệu quy trình hiện có. Phần này trình bày hai nội dung
chính. Một là, giới thiệu chung về các kỹ thuật mơ hình quy trình sẽ đƣợc sử
dụng trong các chƣơng sau. Hai là, chƣơng này cho thấy những hạn chế của
phƣơng pháp cổ điển, do đó thúc đẩy nhu cầu khai thác q trình.
1.2.1. Mơ hình hóa quy trình
Ngày nay, các hoạt động kinh doanh trở nên phức tạp hơn. Mơ hình q
trình hỗ trợ quản lý phức tạp bằng cách cung cấp cái nhìn sâu sắc về mơ hình
và lập hồ sơ thủ tục. Kết quả là, các mơ hình quy trình đƣợc sử dụng rộng rãi
trong các tổ chức hiện nay.
Theo [11], quản lý hoạt động trong tổ chức, doanh nghiệp, và nghiên cứu
những hoạt động cụ thể là một nhánh của khoa học quản lý phụ thuộc nhiều
vào mơ hình. Tạo ra một mơ hình do đó là một nhiệm vụ khó khăn và dễ bị
lỗi. lỗi điển hình bao gồm: mơ hình mơ tả một phiên bản lý tƣởng của thực
tại, mơ hình khơng có khả năng để nắm bắt đầy đủ hành vi của con ngƣời và
mơ hình ở mức độ trừu tƣợng sai.


7

1.2.2. Một số ngơn ngữ mơ hình quy trình
Có rất nhiều ngơn ngữ mơ hình và việc quyết định chọn một hay nhiều
mơ hình phụ thuộc vào nhiều yếu tố. Trong phần dƣới đây luận văn sẽ giới
thiệu một số ngơn ngữ mơ hình thƣờng đƣợc sử dụng trong khai phá quy
trình.
a. Mạng Petri
Mạng Petri [8], [11], [12], cơng cụ hình học và tốn học biểu diễn q
trình biến đổi trạng thái của các hệ thống, do Carl Adam Petri đề xuất vào
năm 1962. Mạng Petri đƣợc xem là một ngơn ngữ mang tính tƣợng trƣng cao

và dễ dàng giao tiếp giữa các nhà thiết kế khác nhau trên thế giới cũng nhƣ rất
thuận lợi và dễ dàng cho ngƣời sử dụng. Trong lĩnh vực khai phá quy trình
mạng Petri đƣợc sử dụng rộng rãi để mơ hình hóa luồng quy trình dựa vào các
bản ghi sự kiện. Hiện nay có nhiều phƣơng pháp đƣợc dùng để phân tích
mạng Petri. Hơn thế nữa, ngôn ngữ ProM cung cấp cho chúng ta nhiều công
cụ để chuyển đổi những ngôn ngữ mô hình khác thành mạng Petri.
Mạng Petri là một dạng biểu đồ có hƣớng gồm hai loại nút: chuyển tiếp
(transition) và vị trí (place). Các vị trí và chuyển tiếp đƣợc nối với nhau bằng
các đƣờng nối (liên kết). Chỉ có thể nối vị trí với chuyển tiếp, khơng thể nối
giữa hai vị trí hoặc hai chuyển tiếp với nhau. Khi một đƣờng nối đi từ một vị
trí đến một chuyển tiếp, thì vị trí đó đƣợc gọi là vị trí đầu vào của chuyển tiếp
đó. Ngƣợc lại, khi có một đƣờng nối đi từ chuyển tiếp tới một vị trí thì vị trí
đó đƣợc gọi là vị trí đầu ra của chuyển tiếp đó. Các vị trí có thể chứa một số
lƣợng các thẻ (token) nào đó. Thẻ trong vị trí đƣợc biểu diễn bằng dấu chấm.
Chuyển tiếp của Petri Net có thể hoạt động đƣợc khi tất cả các vị trí đầu vào
của nó có ít nhất một token. Sau khi chuyển tiếp hoạt động (bắn), mỗi vị trí
đầu vào sẽ mất một thẻ và mỗi vị trí đầu ra thêm một thẻ. Tại một thời điểm,
việc phân bố các thẻ trên các vị trí, đƣợc gọi là đánh dấu (marking) của Petri
Net. Nó biểu diễn trạng thái hiện tại của hệ thống đƣợc mơ hình hóa.


8

b. Mạng Workflow
Khi mơ hình hóa quy trình nghiệp vụ dƣới dạng mạng Petri ta thƣờng
quan tâm đến một tập con của mạng Petri đƣợc gọi là mạng luồng công việc
[10] (Workflow nets hay WF-nets). Một WF-nets là một mạng Petri chỉ có
một vị trí dành riêng cho nguồn nơi quy trình bắt đầu và một vị trí dành riêng
cho đích nơi quy trình kết thúc. Ngồi ra, tất cả các nút đều trên một đƣờng
dẫn từ nguồn đến đích.

1.2.3. Phân tích quy trình dựa trên mơ hình
Theo [11], phân tích quy trình dựa trên mơ hình bao gồm kiểm tra quy
trình và phân tích hiệu suất quy trình. Kiểm tra quy trình tập trung vào sự
đúng đắn của hệ thống hoặc quy trình. Phân tích hiệu suất tập trung vào số
dịng cơng việc, thời gian chờ, dịch vụ đƣợc sử dụng và mức độ.
a. Kiểm tra quy trình.
Một phƣơng pháp ta kiểm tra tính mạnh của mơ hình, tức là tính liên
thơng của mơ hình khi từ bất kỳ một trạng thái nào cũng có đƣờng chuyển
đến trạng thái kết thúc. Một phƣơng pháp kiểm tra khác là so sánh hai mơ
hình. Ví dụ, khi bƣớc vào giai đoạn triển khai, quy trình đó cần đƣợc so sánh
với các đặc điểm kỹ thuật cao cấp hơn. Nếu quy trình đó có thể “theo tất cả
các hành động” của quy trình cao cấp hơn thì có thể nói, mơ hình quy trình
đƣợc triển khai là đúng đắn.
b. Phân tích hiệu năng
Hiệu suất của một q trình hoặc tổ chức có thể đƣợc định nghĩa theo
nhiều cách khác nhau. Thông thƣờng, ba khía cạnh của hoạt động đƣợc xác
định: thời gian, chi phí và chất lƣợng. Đối với từng khía cạnh hiệu suất, chỉ số
hiệu suất chính khác nhau có thể đƣợc xác định. Các chỉ số sau đây có thể
đƣợc xác định cho khía cạnh thời gian: Thời gian dẫn là tổng thời gian từ việc
tạo ra các trƣờng hợp đến hoàn thành các trƣờng hợp. Mức độ lệch thời gian


9

dẫn giữa các trƣờng hợp khác nhau có tầm quan trọng khi đánh giá hiệu suất.
Thời gian phục vụ là thời gian làm việc thực tế trên một trƣờng hợp. Thời
gian chờ đợi là thời gian một trƣờng hợp đang chờ tài nguyên trở nên có sẵn.
Thời gian đồng bộ hóa là thời điểm hoạt động chƣa đƣợc kích hoạt đầy đủ và
chờ đợi một kích hoạt bên ngồi hoặc một nhánh song song. Chỉ số hiệu suất
cũng có thể đƣợc định nghĩa cho mức chi phí. Các chi phí thực hiện một hoạt

động có thể đƣợc cố định hoặc phụ thuộc vào loại tài nguyên đƣợc sử dụng,
tận dụng, hoặc thời gian hoạt động. Chỉ số hiệu suất thƣờng đƣợc tính bằng
trung bình các nguồn lực trong một thời gian nhất định. Các chỉ số chất lƣợng
thƣờng tập trung vào các "sản phẩm" hoặc "dịch vụ" giao cho khách hàng.
Nhƣ chi phí, điều này có thể đƣợc đo bằng nhiều cách khác nhau. Ví dụ sự hài
lịng của khách hàng đo lƣờng thông qua bảng câu hỏi.
Trong khi kiểm tra tập trung vào tính chính xác của quy trình đƣợc mơ
hình hóa thì phân tích hiệu quả nhằm mục tiêu cải tiến quy trình liên quan đến
thời gian, chi phí, hoặc chất lƣợng. Trong bối cảnh của hoạt động quản lý,
nhiều kỹ thuật phân tích đã đƣợc phát triển.
1.2.4. Giới hạn của phân tích quy trình dựa trên mơ hình
Kiểm định và phân tích hiệu suất phụ thuộc rất nhiều vào sự sẵn có của
mơ hình chất lƣợng cao. Khi các mơ hình và thực tế có rất ít điểm chung,
phân tích dựa trên mơ hình khơng có ý nghĩa nhiều. Ví dụ, mơ hình quy trình
có thể nhất quán và đáp ứng tất cả các loại tính chất mong muốn. Tuy nhiên,
nếu mơ hình mơ tả một phiên bản lý tƣởng của thực tế, điều này là khá vô
dụng nhƣ trong thực tế tất cả các loại sai lệch có thể xảy ra, mơ hình mơ
phỏng cũng tƣơng tự. Có thể mơ hình dự đốn một sự cải thiện đáng kể trong
khi trên thực tế đây không phải là trƣờng hợp vì các mơ hình dựa trên các giả
định sai lầm. Tất cả những vấn đề này xuất phát từ sự thiếu liên kết giữa các
mơ hình làm bằng tay và thực tế. Khai phá quy trình giải quyết những vấn đề
này bằng cách thiết lập một kết nối trực tiếp giữa các mơ hình và dữ liệu sự


10

kiện cấp thấp thực tế về quá trình này. Hơn nữa, các kỹ thuật phát hiện quy
trình cho phép xem cùng một thực tế từ các góc độ khác nhau và ở mức độ
trừu tƣợng khác nhau.
1.2.5. Các thao tác nhật ký sự kiện và mơ hình quy trình

Một trong những yếu tố quan trọng của khai phá quy trình là sự nhấn
mạnh vào việc thiết lập một mối quan hệ mạnh mẽ giữa một mơ hình quy
trình và "thực tế" đƣợc ghi lại dƣới các hình thức của một bản ghi sự kiện. Ta
sử dụng các thuật ngữ Play-in, Play-out, và Replay để phản ánh về mối quan
hệ này [11]. Hình 1.2 minh họa ba khái niệm.

Mơ hình quy trình

Bản ghi sự kiện

Mơ hình quy trình

Bản ghi sự kiện

- Mở rộng mơ hình
- Kiểm tra, chản
đốn
- Dự đốn
- Đề xuất
Bản ghi sự kiện

Mơ hình quy trình

Hình 1.2: Ba sự liên quan giữa các bản ghi sự kiện và quy trình mơ hình:
Play-in, Play-out, và Replay


11

Play-out đề cập đến cách sử dụng cổ điển của các mơ hình quy trình. Có

thể hiểu đơn giản, Play-out có đầu vào là một mơ hình và mục tiêu là thu thập
số liệu thống kê và khoảng tin cậy bằng cách chạy liên tục một mơ hình thơng
qua mơ phỏng. Play-in ngƣợc lại với Play-out, tức là, hành vi mẫu đƣợc lấy
làm đầu vào và mục tiêu là xây dựng một mơ hình. Replay sử dụng một bản
ghi sự kiện và một mơ hình quy trình nhƣ đầu vào. Nhật ký sự kiện đƣợc "tái
hiện lại" trên đỉnh của các mơ hình quy trình cho các mục đích khác nhau nhƣ
kiểm tra phù hợp, mở rộng các mơ hình với tần số và thông tin thời gian, xây
dựng mô hình dự báo, hỗ trợ hoạt động
1.3.

BÀI TỐN PHÁT HIỆN QUY TRÌNH
1.3.1. Nhật ký sự kiện
Bản ghi sự kiện (event log) hay cịn đƣợc gọi là bản ghi luồng cơng việc

là một trong những thành phần chính của các kỹ thuật khai phá quy trình nó
có thể đƣợc xem nhƣ là đầu vào của các kỹ thuật khai phá quy trình [11]. Các
bản ghi này chứa thơng tin về các sự kiện và các quy trình xảy ra trong hệ
thống, nó có thể đƣợc sử dụng để khai phá một mơ hình, mở rộng một mơ
hình đã tồn tại hay tính tốn chất lƣợng của nó. Ngày nay, bất kỳ một hệ
thống phần mềm nào đƣợc sử dụng để hỗ trợ quy trình (ERP, WFM.) đều ghi
lại thơng tin này theo các hình thức khác nhau. Tuy nhiên, để phục vụ mục
đích khai phá quy trình, các sự kiện đƣợc ghi lại trong bản ghi phải thỏa mãn
các yêu cầu sau:
- Mỗi sự kiện phải đề cập đến một hoạt động hay một tác vụ,
- Mỗi sự kiện đề cập đến một trƣờng hợp (ví dụ nhƣ một yêu cầu tìm
kiếm đối tƣợng),
- Mỗi sự kiện có thể có một ngƣời thực hiện còn gọi là ngƣời khởi đầu
(ngƣời thực hiện hoặc bắt đầu hoạt động),
- Các sự kiện có một nhãn thời gian và tất cả các sự kiện đều đƣợc sắp
xếp theo thứ tự.



12

Bên cạnh đó bản ghi có thể chứa các loại của sự kiện, ví dụ nhƣ: sự kiện
bắt đầu (bắt đầu một hành động), sự kiện hoàn thành (kết thúc một hành
động), sự kiện đã đƣợc lịch trình (một hành động dự kiến sẽ đƣợc thực hiện)
v.v. Bảng 1.1 cho thấy một ví dụ về bản ghi sự kiện với một số thơng tin nhƣ
đã nói ở trên. Bản ghi sự kiện ở bảng 1.1 là một ví dụ điển hình cho cấu trúc
của một bản ghi sự kiện
Khơng phải tất cả những thông tin chứa trong bản ghi sự kiện đều cần
thiết cho mục đích khai phá quy trình mà phụ thuộc vào kỹ thuật khai phá quy
trình đƣợc sử dụng và những câu hỏi đặt ra, chỉ có một phần thông tin trong
bản ghi đƣợc sử dụng. Do đó, để đơn giản hóa bảng ghi sự kiện, ta có thể sử
dụng các ký hiệu đại diện cho tên các hoạt động hoặc các thuộc tính khác tùy
theo yêu cầu phân tích. Trong đó mỗi dịng của bản ghi đƣợc gọi là một vết
tƣơng ứng với chuỗi các sự kiện đã đƣợc nhóm thành các “mã trƣờng hợp”
(case id). Trong trƣờng hợp xem xét dựa trên các quan điểm khác, những dữ
liệu khác đƣợc lƣu trữ trong bản ghi sẽ đóng vai trị quan trọng hơn.
Bảng 1.1: Một ví dụ bảng ghi sự kiện
Mã
trƣờng
hợp
1
1
1
1
1
2
2

2
2
2
3
3
3
3
3

Mã sự
kiện
35654423
35654424
35654425
35654426
35654427
35654483
35654485
35654487
35654488
35654489
35654521
35654522
35654524
35654525
35654526

Thuộc tính
Nhãn thời gian
dd-MM-yyyy:HH.mm

30-12-2010:11.02
31-12-2010:10.06
05-01-2011:15.12
06-01-2011:11.18
07-01-2011:14.24
30-12-2010:11.32
30-12-2010:12.12
30-12-2010:14.16
05-01-2011:11.22
08-01-2011:12.05
30-12-2010:14.32
30-12-2010:15.06
30-12-2010:16.34
06-01-2011:09.18
06-01-2011:12.18

Hoạt động
đăng ký yêu cầu
kiểm tra kỹ
kiểm tra vé
quyết định
từ chối yêu cầu
đăng ký yêu cầu
kiểm tra vé
kiểm tra nhanh
quyết định
chi trả bồi thƣờng
đăng ký yêu cầu
kiểm tra nhanh
kiểm tra vé

quyết định
xem lại yêu cầu

Nguồn
lực
Pete
Sue
Mike
Sara
Pete
Mike
Mike
Sean
Sara
Ellen
Pete
Mike
Ellen
Sara
Sara

Chi
phí
50
400
100
200
200
50
100

400
200
200
50
400
100
200
200


13

3
3
3
3
4
4
4
4
4

35654527
35654530
35654531
35654533
35654641
35654643
35654644
35654645

35654647

06-01-2011:13.06
08-01-2011:11.43
09-01-2011:09.55
15-01-2011:10.45
06-01-2011:15.02
07-01-2011:12.06
08-01-2011:14.43
09-01-2011:12.02
12-01-2011:15.44

kiểm tra kỹ
kiểm tra vé
quyết định
chi trả bồi thƣờng
đăng ký yêu cầu
kiểm tra vé
kiểm tra kỹ
quyết định
từ chối yêu cầu

Sean
Pete
Sara
Ellen
Pete
Mike
Sean
Sara

Ellen

400
100
200
200
50
100
400
200
200

Định dạng đƣợc sử dụng để lƣu trữ các bản ghi trong mỗi hệ thống
thƣờng là khác nhau. Nếu thiếu một định dạng thống nhất thì sẽ làm cho việc
chia sẻ và trao đổi các bản ghi giữa các công cụ gặp khó khăn và làm tăng chi
phí của q trình phân tích khai phá quy trình. Vì lý do đó, năm 2003 một
định dạng đã đƣợc đề xuất bởi Medeiros, Ana Karla và Van der Aalst và trở
thành định dạng chuẩn cho các bản ghi sự kiện, đó là Mining eXtensible
Markup Language (MXML) [13]. MXML dựa trên XML và có thể đƣợc sử
dụng để lƣu trữ bất kỳ thông tin nào có liên quan đến các sự kiện và các quy
trình. MXML là định dạng đƣợc hỗ trợ bởi hầu hết các cơng cụ phân tích khai
phá quy trình, chẳng hạn nhƣ ProM. Tuy nhiên, để có thể chạy ProM từ và
ProM6.0 ra đời vào tháng 11/2010 ngƣời ta sử dụng định dạng eXtensible
Event Stream (XES) [11] thay vì sử dụng MXML. XES là một chuẩn khai
phá quy trình mới đƣợc thực hiện bởi IEEE Task Force cho khai phá quy
trình. Hiện tại, một số cơng cụ nhƣ XESame, ProM Import, Nitro có thể
chuyển đổi đƣợc hầu hết các bản ghi sự kiện về định dạng MXML và XES.
Bảng 1.2: Một cách biểu diễn gọn hơn của bản ghi sự kiện.
Mã trƣờng hợp
Vết sự kiện

1
(A, B, C, D)
2
(A, C, B ,D)
3
(A, B, C, D)
4
(A, C, B, D)
5
(A, E, D)


14

1.3.2. Phát hiện quy trình
Phát hiện quy trình là một trong những nhiệm vụ khó khăn nhất của khai
phá quy trình. Dựa trên nhật ký sự kiện, một mơ hình quy trình đƣợc xây
dựng nhờ nắm bắt đƣợc các hành vi trong nhật ký sự kiện [11]. Phần này trình
bày các vấn đề về phát hiện quy trình từ bản ghi sự kiện, phát hiện lại quy
trình từ bản ghi sự kiện và quy trình mẫu.
a. Đặc vấn đề phát hiện quy trình.
Nhƣ đã trình bày ở phần trƣớc, có ba lớp bài tốn khai phá quy trình:
phát hiện quy trình, kiểm tra phù hợp, cải tiến quy trình. Ở phần này, ta tập
trung vào lớp phát hiện quy trình và quan điểm điều khiển luồng
Ta xác định mục tiêu là một mơ hình mạng Petri. Ta sử dụng một bản
ghi sự kiện đơn giản làm đầu vào. Một bản ghi sự kiên đơn giản L là tập dấu
vết trên một số thiết lập của hoạt động A, tức là, L ∈ 𝔹 (𝒜 ∗) . Ví dụ,
L1 = [(a,b,c,d)3,(a,c,b,d)2,(a,e,d)]
L1 là một bản ghi sự kiện đơn giản mô tả lịch sử của sáu trƣờng hợp.
Mục tiêu là khám phá một lƣới Petri có thể "phát lại" bản ghi sự kiện L1. Rõ

ràng, lƣới Petri là một lƣới WF-net mạnh nhƣ đƣợc nhắc đến ở các phần
trƣớc. Dựa trên những sự lựa chọn, ta xây dựng các vấn đề phát hiện quy trình
và làm cho nó cụ thể hơn.
Định nghĩa 1.1 Một thuật tốn phát hiện quy trình là một hàm ánh xạ
bản ghi L ∈ 𝔹 (𝒜 ∗) vào một mạng Petri đã đƣợc đánh dấu γ(L) = (N,M). Khi
đó, N là một WF-net mạnh và tất cả các trình tự trong L tƣơng ứng với trình
tự có thể có của (N, M).
Xét L2 là một bản ghi sự kiện đơn giản bao gồm 13 trƣờng hợp đại diện
của 6 dấu vết khác nhau.


15

L2 = [(a,b,c,d)3, (a,c,b,d)4, (a,b,c,e,f,b,c,d)2, (a,b,c,e,f,c,b,d),
(a,c,b,e,f,b,c,d)2, (a,c,b,e,f,b,c,e,f,c,b,d)]
Hàm γ định nghĩa kỹ thuật "Play-in" đã mô tả ở phần 1.2.4. Dựa trên L2,
một thuật tốn phát hiện quy trình γ có thể phát hiện các WF-net thể hiện
trong hình 1.3 , tức là, γ (L2) = (N2, [start]). Mỗi trình tự trong L2 tƣơng ứng
với một trình tự có thể có của WF-net N2 trong hình 1.3. Vì vậy, rất dễ dàng
để thấy rằng WF-net thực sự có thể mơ tả lại tất cả các trình tự trong các bản
ghi sự kiện.
Dựa trên bản ghi sự kiện L2, một số hàm γ có thể khám phá WF-net N2
nhƣ hình 1.3. WF-net này có thể xem lại tất cả các dấu vết trong bản ghi. Tuy
nhiên, khơng phải tất cả các trình tự N2 tƣơng ứng với dấu vết trong L2. Ví dụ,
trình tự (a, c, b, e, f, c, b, d) khơng xuất hiện trong L2. Trong thực tế, có vơ
hạn các trình tự vì các cấu trúc vịng lặp trong N2. Rõ ràng, những điều này
không thể xuất hiện trong tất cả các bản ghi sự kiện. Do đó, định nghĩa 1.1
khơng u cầu tất cả các trình tự của (N, M) là dấu vết L.

Hình 1.3: WF-net N2 đƣợc phát hiện cho L2 = [(a,b,c,d)3, (a,c,b,d)4,

(a,b,c,e,f,b,c,d)2, (a,b,c,e,f,c,b,d), (a,c,b,e,f,b,c,d)2, (a,c,b,e,f,b,c,e,f,c,b,d)]
Trong phần này, ta tập trung vào phát hiện quy trình trên lƣới Petri bởi vì
lƣới Petri đơn giản và trực quan nhƣng vẫn cho phép mơ hình hóa truy cập
đồng thời, lựa chọn, và lặp. Điều này đƣợc minh họa qua hình 1.3. Lƣới N2 là