BỘ GIÁO DỤC VÀ ĐÀO TẠO

TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG
VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
LÊ QUANG HƯNG NGHIÊN CỨU PHƯƠNG PHÁP TỐI ƯU QUY TRÌNH
DỰA TRÊN PHÂN TÍCH DỮ LIỆU CHUYÊN NGÀNH :
TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH

MÃ SỐ: 60.48.15


Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn tại Học viện Công nghệ
Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:
- Thư viện Học viện Công nghệ Bưu chính Viễn thông

LỜI MỞ ĐẦU Trong môi trường hiện nay, một doanh nghiệp muốn hoạt động tốt đều cần phải có một
qui trình các luồng xử lý công việc rõ ràng nhằm đảm bảo được sự vận hành tốt và nhanh
chóng của toàn bộ hệ thống doanh nghiệp. Một qui trình xử lý tốt của doanh nghiệp sẽ đem lại
được nhiều lợi ích, từ tiết kiệm chi phí, nhân công tới việc tăng chất lượng, số lượng sản phẩm
ra thị thường. Khi các quy trình nghiệp vụ được quản lý tốt hơn, các tổ chức có thể quản lý
các tác vụ và tự động hóa các tác vụ đòi hỏi nhiều thời gian, giải phóng nhân viên để họ tập
trung vào các công việc mang lại giá trị cao hơn và tạo ra các kết quả kinh doanh đồng nhất,
liên tục và hiệu quả hơn
Phân tích dữ liệu quy trình (gọi là process mining) là kỹ thuật quản lý quy trình dựa trên
việc phân tích dữ liệu event logs. Kỹ thuật này cho phép giải quyết tối ưu hoá một qui trình có
từ trước (hoặc có thể chưa có), tuy nhiên qui trình này chưa rõ ràng hoặc là kết quả xử lý của
qui trình này chưa được tốt. Các dữ liệu sự kiện xử lý của các qui trình này sẽ được lưu lại
(gọi là events log), các thuật toán về khai phá dữ liệu sẽ dựa trên khối dữ liệu này để có thế
đánh giá (tốc độ, thời gian, chất lượng, số lượng), so sánh (so với các qui trình áp dụng trước
đây) và tối ưu (đưa ra được các tham số tối ưu cho qui trình hiện tại) nhằm đạt được một qui
trình tốt hơn hiện tại. Đánh giá, so sánh, tối ưu cũng là ba hướng chính mà hiện tại đang được

trang bị xong các hệ thống như là ERP, CRM, Core v.v…
II. Khai phá Qui trình
- Khai phá qui trình chính là khám phá một cách tự động các thông tin trong các bản
ghi sự kiện này. Các thông tin được khám phá ra có thể sử dụng để triển khai ra một
hệ thống mới tốt hơn, hoặc có thể là công cụ để đánh giá phân tích và tối ưu qui trình
hiện hành. Điểm mạnh chính của khai phá qui trình chính là các thông tin được đánh
giá một cách khách quan. Nói một cách khác, kỹ thuật khai phá qui trình hữu dụng là
bởi vì cách lấy thông tin dựa trên những gì đã xảy ra thực tế thông qua các bản ghi sự
kiện, chính vì vậy, điểm khởi đầu của bất kỳ một kỹ thuật khai phá qui trình nào cũng
là một bản ghi sự kiện.
- Các dạng khai phá qui trình chính:
Trang 2

- Khai phá: Không có một mô hình có trước, dựa trên một bản ghi sự kiện của
một mô hình khác mà được xây dựng từ trước. Ví dụ: sử dụng thuật toán
alpha một mô hình tiến trình có thể được khai phá ra dựa trên những bản ghi
sự kiện cấp thấp.
- Sự phù hợp: Đã có mô hình sẵn, mô hình này sẽ được kiểm tra tính hiện thực
và phù hợp với thực tế hay không, hoặc có thể so sánh với các mô hình khác.
Ví dụ: Một doanh nghiệp đang xem xét áp dụng một trong hai mô hình cách
xử lý các giao dịch mua bán trên 1 triệu Euro, 1 là chỉ kiểm tra 2 lần một cách
cẩn thận, 2 là 1 lần kiểm tra và một lần phê duyệt của cấp trên, 2 mô hình này
sẽ được áp dụng thử và so sánh xem mô hình nào tốt hơn.
- Mở rộng: Xây dựng trên mô hình có trước. Phương pháp này thường áp dụng
để mở rộng, cải tiến mô hình có sẵn, mục đích không phải là tìm sự phù hợp
mà là tối ưu qui trình, tìm kiếm các chỗ thắt cổ chai trong qui trình.
- Một hệ thống có qui trình rõ ràng được vận hành thông qua một mô hình qui trình
được định nghĩa trước, như là hệ thống quản trị luồng công việc, hệ thống xử lý các
tình huống và một số hệ thống thực hiện/quản lý trong Webservices. Trong hệ thống
mà không có qui trình cụ thể thì việc tìm ra một qui trình rõ ràng là khó khăn, dẫn đến

việc từ khi bắt đầu đến khi kết thúc. Nội dung bản ghi sự kiện rất quan trọng vì
nó quyết định phần lớn các kỹ thuật khai phá có thể áp dụng trên nó.
 Mô hình được khai phá là toàn bộ lượng thông tin thể hiện cấu trúc của mô hình
sẽ khai phá. Một số mô hình chỉ thể hiện qui trình của các nhiệm vụ sẽ được thực
hiện trong mô hình, tuy nhiên một số mô hình có thông tin đầy đủ hơn, nhất là
các qui trình có nhiều điểm tách hợp trong qui trình. Các kỹ thuật khai phá có thể
dành cho toàn bộ qui trình, hoặc có thể chỉ là một đoạn quan trong nhỏ nào đó
trong qui trình mà thôi.
 Phương pháp khai phá là các kỹ thuật sử dụng để khai phá mô hình qui trình, 1
bước hoặc nhiều bước với các khai phá trung gian.
 Khả năng khai phá thể hiện khả năng kỹ thuật có thể đáp ứng khai phá trong các
cấu trúc của mô hình như là: thứ tự, lựa chọn, xong xong…
 Xử lý nhiễu thể hiện khả năng xử lý nhiễu của kỹ thuật. Hầu hết các kỹ thuật xử
lý nhiễu sẽ suy luận từ qui trình ra, sau đó sẽ tinh chỉnh dữ liệu bản ghi sự kiện
bởi các ngưỡng đặt ra từ trước.
II. Cơ sở lý thuyết của khai phá qui trình
1. Giới thiệu thuật toán α
- Thuật toán α sử dụng các quan hệ thứ tự để khám phá (hoặc khám phá lại) một mô
hình qui trình mà các hành vi của qui trình này được lưu tại bản ghi sự kiện (event
logs). Mô hình được tìm ra sau khi khai phá (hoặc khám phá) sẽ được thể hiện thông
qua một Workflow net (WF-net). Workflow nets là một hình thức đặc biệt của Petri
nets.
2. Petri Nets
- Mạng Petri nets bao gồm 4 thành phần chính là địa điểm (places), các nơi chuyển đổi
(transitions), các đường chỉ hướng (directed arcs) và các thẻ (tokens). Các đường chỉ
hướng sẽ kết nối từ địa điểm đến nơi chuyển đổi hoặc ngược lại, lưu lý là các đường
Trang 5

chỉ hướng sẽ không tồn tại giữa 2 địa điểm hoặc 2 nơi chuyển đổi. Địa điểm mà có
đường chỉ hướng chạy tới nơi chuyển đổi thì gọi là địa điểm nhập của nơi chuyển đổi

3) Tạo các tập hợp chuyển dịch (T
O
) đi đến điểm đích.
4) Xây dựng tập hợp X
L
các chuyển dịch có liên quan đến nhau (cùng điểm xuất
phát hoặc cùng điểm kết thúc), từ đó ta có thể xây dựng các phép toán AND-
split/join hoặc XOR-split/join cho các chuyển dịch này.
5) Xây dựng tập hợp Y
L
dựa trên tập X
L
, tập hợp Y
L
sẽ loại đi các chuyển dịch trùng
nhau, hoặc bao gồm nhau, đồng thời tập hợp này chỉ bao gồm các địa điểm có
trong luồng công việc và không bị trùng nhau.
6) Tạo các địa điểm cần thiết (bao gồm cả đầu vào và đầu ra của WF-net)
7) Tạo các đầu vào và đầu ra cho các chuyển dịch đã tạo được trong bước 5.
8) Trả về kết quả α(L) = (P
L
,T
L
,F
L
).
- Định nghĩa thuật toán α:
 Gọi T là tập hợp các nhiệm vụ.
 Gọi L là bản ghi sự kiện trên tập hợp T.
 Thuật toán α xây dựng WF-net dựa trên L như sau:

dụng trong ProM Framework được định dạng dưới dạng MXML, các log files này
được tạo từ các công cụ chuyển đổi log-files của ProM, hoặc một số các ứng dụng
khác như CPN Tool.
II. Cài đặt thuật toán
1. Cài đặt Plug-in
- Trên nền tảng ProM Framework, chúng ta có thể cài đặt 5 loại plug-in như sau:
 Khai phá plugin, dùng để khai phá các qui trình dựa trên các bản ghi sự kiện
của Workfow
 Các plugin để xuất, hiển thị ra qui trình (Petri net, Workflow nets)
 Các plug-in dùng để nhập các dữ liệu logs, chuyển thành định dạng MXML
để có thể sử dụng trong Prom Framework
 Các plugin dùng để khảo sát, lấy các thông tin trên các bản ghi sự kiện
 Các plugin dùng để chuyển đổi qua lại các dạng dữ liệu.
2. Định dạnh MXML
- Định dạng MXML được viết tắt từ Mining XML mới đầu được sử dụng như là chuẩn
đầu vào chung cho các công cụ khai phá khác nhau.
- Các thành phần chính của cấu trúc MXML:
 Element WorkflowLog: Tên của bản ghi sự kiện (Event log)
Trang 9

 Element Source: Tên chương trình tổng hợp và tạo ra bản ghi sự kiện.
 Element Process: Thông tin các tiến trình sẽ được lưu dữ liệu trong bản ghi sự
kiện.
 Element ProcessInstance: Thông tin các trường hợp, tình huống xảy ra trong
tiến trình (các thực thể của tiến trình).
 Element AuditTrailEntry: Các công việc trong tiến trình
 Element WorkflowModelElement: Tên của các công việc trong tiến trình.
- Element EventType: Tên loại sự kiện của công việc, có tất cả 13 loại sự kiện:
schedule, assign, reassign, start, resume, sus pend, autoskip, manualskip, withdraw,
complete, ate_abort, pi_abort và unknown.

thống quản trị luồng công việc,.v.v. trong doanh nghiệp, đặc biệt là cho các doanh
nghiệp lớn, có các văn phòng ở xa nhau dẫn đến việc đánh giá rất khó khăn. Việc tìm
ra các điểm yếu của qui trình giúp cho doanh nghiệp cải thiện được thời gian xử lý
công việc, tiết kiệm chi phí, đưa ra được cam kết phục vụ khách hàng tốt hơn. Thuật
toán α áp dụng rất hiệu quả cho các qui trình có độ phức tạp thấp, tuy nhiên lại gặp
khó khăn với một số qui trình có vòng lặp, các nhiệm vụ lặp, trùng, v.v việc tối ưu
thuật toán α sẽ giúp cải thiện thuật toán này và đưa ra qui trình dựa trên mạng Petri
Nets tốt nhất. ProM Framework có rất nhiều điểm mạnh, tuy nhiên vẫn còn một số
hạn chế trong việc tối ưu các bản ghi dữ liệu, hỗ trợ phân tích Online, các phương
pháp phân tích dựa trên bộ dữ liệu lớn, tính toán nhiều thời gian còn nhiền khó khăn.
Do thời gian có hạn và việc tiếp cận với khai phá qui trình còn mới, tài liệu tham
khảo chưa nhiều nên chắc chắn luận văn sẽ không tránh khỏi những thiếu sót nhất
định, em rất mong nhận được sự giúp đỡ, đóng góp ý kiến của các thầy cô giáo trong
Học viện và các bạn để em có thể hoàn thiện và nghiên cứu sâu hơn trong lĩnh vực
này.
Cuối cùng em xin chân thành cảm ơn thầy cô giáo trong Học viện Bưu chính Viễn
thông, đặc biệt là thầy PGS.TS Từ Minh Phương, đã tận tình chỉ bảo, giúp đỡ em
trong suốt quá trình hoàn thiện luận văn này.