Tóm tắt Luận văn 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

TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG

VIỆT NAM

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

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

TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT

HÀ NỘI - 2010

Luận văn được hoàn thành tại:

Học viện Công nghệ Bưu chính Viễn thông

Tập đoàn Bưu chính Viễn thông Việt Nam

Người hướng dẫn khoa học:

PGS.TS. TỪ MINH PHƯƠNG

Phản biện 1: ……………………………………………………

……………………………………………………

Phản biện 2: ……………………………………………………

……………………………………………………

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

tập trung nghiên cứu .

Luận văn này được chia làm 03 chương:

-

Chương I trình bày về các khai niệm về qui trình, khai phá qui trình, các khái

niệm cơ bản về khai phá qui trình.

Chương II trình bày về cơ sở lý thuyết dùng trong kỹ thuật khai phá qui trình,

phân tích kỹ thuật khai phá qui trình dựa trên thuật toán Alpha.

Chương III trình bày về phương pháp cài đặt thuật toán Alpha trên nền tảng

ProM Framework và áp dụng thuật toán Alpha để khai phá qui trình trong

ngân hàng.

CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ QUI TRÌNH

VÀ TÍNH KHẢ THI

I. Giới thiệu về Qui trình và Khai phá qui trình

-

Hệ thống quản lý qui trình công việc là các kỹ thuật, phương pháp dùng trong quản lý

luồng công việc được thực hiện trên mạng máy tính. Hệ thống này còn hỗ trợ việc

giám sát quá trình thực hiện các nhiệm vụ, giúp ban lãnh đạo có thể đánh giá kết quả

làm việc của các nhân viên của mình. Một chức năng quan trọng hơn cả, đó là việc

lưu trữ các thông tin, dữ liệu xử lý của xuyên suốt toàn bộ quá trình xử lý một công

việc nào đó trong doanh nghiệp, thời gian thực hiện, người hoặc hệ thống nào đã thực

hiện công việc trên. Các dữ liệu lưu trữ này chính là điểm khởi đầu của công việc

khai phá qui trình, các dữ liệu này thường được gọi là bản ghi sự kiện (event logs).

Luồng công việc (Workflow) là thuật ngữ được sử dụng để miêu tả các quy trình

được gắn liền với hệ thống, trong đó liệt kê danh sách các công việc cần hoàn

thành,cả thủ công lẫn tự động hoá và lên kế hoạch từ trước trong doanh nghiệp. Tối

ưu hoá quy trình doanh nghiệp là một quá trình liên tục và không có điểm dừng vì

việc tối ưu liên tục được phát triển theo quá trình phát triển của doanh nghiệp. Hiện

nay, trên thị trường có rất nhiều sản phẩm quản lý qui trình doanh nghiệp, tối ưu qui

trình doanh nghiệp của IBM, Oracle, và một số công ty phần mềm khác tại Ấn độ.

Đây cũng là một trong những hướng phát triển mạnh khi mà các doanh nghiệp đã

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 1

-

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 trích xuất dữ liệu logs rất khó khăn. Ví dụ, các hệ thống ERP như là SAP và

PeopleSoft thường là được thiết kế mà không có một qui trình rõ ràng. Thay vào đó,

các hệ thống này được xây dựng dựa trên một cơ sở dữ liệu lớn. Thông tin của một

giao dịch mua bán có thể được lưu rải rác ở một vài bảng, mỗi bảng một thông tin

khác nhau, mức độ chi tiết khác nhau. Với các trường hợp này, ta phải có thông tin về

thiết kế hệ thống tổng thể thì mới có thể tông hợp thông tin của các bảng để xây dựng

một qui trình rõ ràng hơn.

-

Nhật ký sự kiện là bản dữ liệu ghi lại các thao tác thực hiện trong qui trình công việc.

Việc lưu trữ các bản ghi này có thể dùng trên nhiều định dạnh khác nhau, như là tập

tin dạng csv (phân cách bằng dấu phẩy), tập tin dạng XML, hoặc tập tin văn bản đơn

giản, tuy nhiên đều phải có các thông tin sau: Tên công việc, tên người xử lý, thời

gian diễn ra công việc, tổng thời gian của nhật ký công việc

Phương pháp khai phá qui trình luồng điều khiển khám phá các mô hình qui trình có

sự liên hệ giữa các công việc của qui trình trong bản ghi sự kiện (event log). Từ các

Trang 2

bản ghi sự kiện, chúng ta có thể tìm được các thông tin về các công việc thuộc tiến

trình nào, thời gian thực hiện công việc, người thực hiện công việc, v.v. Chính vì vậy,

việc khai phá sử dụng kỹ thuật này thường xác định trước các nhiệm vụ trong qui

trình, luồng công việc, mục tiêu cần khai phá. Bởi vì các luồng nhiệm vụ đã được biết

trước, khai phá qui trình luồng điều khiển cũng phải xử lý được một số mô hình

chuẩn trong qui trình như là: thứ tự, xong xong, lựa chọn, lặp, và bắt buộc, nhiệm vụ

ẩn và nhiệm vụ trùng.

Trang 3

CHƯƠNG 2: CƠ SỞ LÝ THUYẾT CỦA KHAI PHÁ QUI TRÌNH

I. Lịch sử và các Khái niệm trong khai phá qui trình

- Một số khái niệm cơ bản:

. Bản ghi sự kiện (event log) là bản ghi các sự kiện của một tiến trình trong công

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 4

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

đó, ngược lại nếu đường chỉ hướng chạy từ nơi chuyển đổi thì địa điểm đó là địa điểm

xuất. Địa điểm có thể chứa một số lượng các thẻ (tokens). Sự phân phối của các thẻ

tại các địa điểm trong một mạng còn được gọi là đánh dấu (marking).

3. Workflow Nets

-

Một mạng Workflow Nets chính là một mạng Petri net được áp dụng trong ngữ cảnh

quản lý tiến trình, qui trình công việc. Chính vì vậy, các khái niệm trên mạng Petri net

cũng được thay đổi để phù hợp với ngữ cảnh của quản lý luồng công việc: Nhiệm vụ

(task) sẽ chính là các chuyển dịch (transitions), các điều kiện nhánh xử lý trong luồng

sẽ chính là các địa điểm (places) và các trường hợp (cases) sẽ là các thẻ (tokens)

trong mô hình Petri net.

-

Một mạng WorkFlow net (WF-net) được mô hình hoá dựa trên mạng Petri net phải

thoả mãn hai điều kiện:

. Một mạng WF-net phải có một đầu vào và một đầu ra. Một trường hợp (tương

ứng là thẻ trong Petri net) xuất phát từ đầu vào là trường hợp cần phải xử lý,

một trường hợp tại đầu ra là đã được xử lý xong.

. Tất cả các xử lý, điều kiệu trong mạng WF-net (tương ứng là các chuyển dịch

trong mạng Petri net) đều phải nằm trong qui trình xử lý từ điểm đầu đến điểm

cuối.

4. Thuật toán α

- Thuật toán α cho bản ghi dữ liệu L bao gồm 8 bước như sau:

Trang 5

1) Tạo tập hợp các chuyển dịch (T_L) trong mạng Workflow net. Các chuyển dịch này

được tìm trong bản ghi sự kiện.

2) Tạo các tập hợp chuyển dịch (T_I) xuất phát từ điểm nguồn.

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_Lcá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_Ldựa trên tập X_L, tập hợp Y_Lsẽ 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:

1.

2.

3.

},

,

4.

5.

6.

7.

8. α(L) =(

Trang 6

-

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.

Trang 7

CHƯƠNG 3: ỨNG DỤNG CÀI ĐẶT CHO MỘT

HỆ KHAI PHÁ QUI TRÌNH

I.

Giới thiệu

-

ProM Framework là một công cụ hàng đầu hiện nay trên thế giới dùng để nghiên cứu

và phát triển các thuật toán khai phá qui trình trong bản ghi sự kiện. ProM

Framework được phát triển theo phương thức mã nguồn mở, các thuật toán được cài

đặt trên ProM Framework dưới dạng các plug-ins. ProM Framework và các plug-ins

đều được phát triển trên nền Java, các plug-ins phát triển dựa trên ProM Framework

sẽ được hỗ trợ các thư viện trong kỹ thuật khai phá qui trình như là : Đọc các log

files, hiển thị kết quả, lựa chọn và giãm nhiễu các log files..v.v..Các log files được sử

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 8

. 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.

-

3. Cài đặt thuật toán Alpha dưới dạng Plugin trong ProM Framework.

-

Trong phần này em trình bày phương pháp và chương trình dùng để cài đặt thuật toán

Alphan trong ProM framework, sử dụng JBuilder.

III.

Áp dụng thuật toán Alpha trên dữ liệu thật

1. Định dạng MXML sử dụng trong ProM Framework:

- Định dạng MXML được dùng rộng rãi trong kỹ thuật khai phá qui trình để lưu thông tin

của qui trình và bản ghi sự kiện trong qui trình, trong phần này e giới thiệu các thành

phần chính của định dạng MXML.

2. Hướng dẫn sử dụng ProM Framework

-

Trong bản ghi sự kiện của chúng ta có thể có nhiều dữ liệu của các tiến trình chưa

hoàn thành. Chính vì vậy, để kết quả của thuật toán alpha có kết quả tốt nhất, ta chỉ

chọn các tiến trình trong bản ghi sử kiện có điểm bắt đầu và điểm kết thúc giống

trong qui trình thật, các tiến trình không có hoặc chưa hoàn thiện sẽ được loại bỏ.

ProM Framework cũng hỗ trợ việc tối ưu bản ghi sự kiện trong phần Log Filter.

Trong phần Log Filter, ta có thể chọn điểm bắt đầu, điểm kết thúc, các nhiệm vụ, các

loại sự kiện..v.v..sẽ dùng trong thuật toán khai phá

-

Trong phần này em giới thiệu một số màn hình và chức năng chính của Prom

Framework:

. Tối ưu và lọc thông tin dữ liệu.

Trang 9

. Xem thông tin bản ghi sự kiện.

. Chạy thuật toán alpha trên bản ghi sự kiện.

. Đánh giá kết quả sau khi chạy thuật toán alpha.

Trang 10

KẾT LUẬN

Khai phá dữ liệu trong qui trình là một phương pháp rất hữu dụng cho các hệ

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.

Trang 11