ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LƯU VĂN BA
THUẬT TOÁN PHÁT HIỆN QUÁ TRÌNH NÂNG CAO
DỰA TRÊN KHÁI NIỆM VÙNG TRẠNG THÁI
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
Hà Nội – 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LƯU VĂN BA
THUẬT TOÁN PHÁT HIỆN QUÁ TRÌNH NÂNG CAO
DỰA TRÊN KHÁI NIỆM VÙNG TRẠNG THÁI
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HÀ QUANG THỤY
Hà Nội – 2015
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
chỉ rõ về tài liệu tham khảo.
Hà Nội, ngày 20 tháng 05 năm 2015
Học viên
Lưu Văn Ba
MỤC LỤC
Danh mục các bảng..........................................................................................................1
Danh mục các hình vẽ, đồ thị .......................................................................................... 2
Mở đầu ............................................................................................................................. 4
Chương 1. GIỚI THIỆU VỀ KHAI PHÁ QUÁ TRÌNH ................................................6
1.1.
Tổng quan về khai phá quá trình........................................................................6
1.1.1.
Khai phá quá trình là gì ...............................................................................6
1.1.2.
Vị trí của khai phá quá trình trong KHDL và Big data. .............................. 6
1.1.3.
Mối liên hệ với khai phá dữ liệu .................................................................7
1.3.2.1.
Lưới Petri (Petri Nets) ........................................................................12
1.3.2.2.
Hệ thống chuyển (Transition systems) ...............................................15
Tóm tắt chương 1 ............................................................................................. 17
Chương 2. PHÁT HIỆN QUÁ TRÌNH VÀ NHỮNG THÁCH THỨC ........................ 18
2.1.
Bài toán phát hiện quá trình .............................................................................18
2.1.1.
Phát biểu bài toán ...................................................................................... 18
2.1.2.
Giới thiệu thuật toán Alpha .......................................................................19
2.2.
Chất lượng mô hình kết quả .............................................................................25
2.3.
Các thách thức trong phát hiện quá trình ......................................................... 26
Chuyển đổi từ hệ thống chuyển sang lưới Petri ........................................34
3.2.2.1.
Định nghĩa vùng .................................................................................34
3.2.2.2.
Lựa chọn vùng ....................................................................................36
3.2.2.3.
Xây dựng lưới Petri sử dụng vùng ..................................................... 36
Nhận xét đánh giá ............................................................................................ 39
3.3.1.
Ưu nhược điểm của phương pháp ............................................................. 39
3.3.2.
Giới thiệu một số đề xuất mô hình cải tiến ...............................................39
3.4.
Tóm tắt chương 3 ............................................................................................. 42
Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ.............................................................. 44
Danh mục các bảng
Bảng 1.1: Một phân đoạn của nhật ký sự kiện cho yêu cầu bồi thường [1] ..................10
Bảng 2.1: Bảng ví dụ về song kết nối cực đại và không cực đại [2] ............................. 20
Bảng 3.1: Ví dụ về các cách biểu diễn trạng thái cho một nhật ký sự kiện [1] .............33
Bảng 3.2: Bảng ví dụ về vùng và không phải là vùng [2] .............................................36
2
Danh mục các hình vẽ, đồ thị
Hình 1.1: Vị trí của khai phá quá trình trong khoa học dữ liệu [2] .................................6
Hình 1.2: Vai trò cầu nối của khai phá quá trình [6] ....................................................... 7
Hình 1.3: Các bài toán trong khai phá quá trình [2] ........................................................ 8
Hình 1.4: Lưới Petri và các thành phần [1] ...................................................................12
Hình 1.5: Ví dụ về marking của một lưới Petri cho hệ thống đèn giao thông [2] .........13
Hình 1.6: Bước chuyển được kích hoạt và có thể cháy [2] ...........................................14
Hình 1.7: Một hệ thống chuyển có một trạng thái khởi đầu..........................................15
và một trạng thái kết thúc[1] ......................................................................................... 15
Hình 2.1: Bài toán phát hiện quá trình [1] .....................................................................18
Hình 2.2: Ví dụ cặp tập song kết nối (A,B) [2] ............................................................. 20
Hình 2.3: Vị trí p(A,B) kết nối các bước chuyển trong tập A và B [2] ............................ 21
Hình 2.4: Kết quả thuật toán α cho L5 [1].....................................................................22
Hình 2.5: Ví dụ hạn chế dư thừa của thuật toán α [2] ...................................................23
Hình 2.6: Ví dụ hạn chế chu trình bằng 1 của thuật toán α [2] .....................................23
Hình 2.7: Ví dụ hạn chế chu trình bằng 2 của thuật toán α [2] .....................................24
Hình 2.8: Ví dụ hạn chế phụ thuộc không địa phương của thuật toán α [2] .................24
Hình 2.9: 4 tiêu chí chất lượng cho mô hình kết quả [1]...............................................25
Hình 2.10: Ví dụ 4 mô hình khác nhau cho cùng một nhật ký sự kiện [1] ...................26
Hình 3.1: Mô hình phát hiện quá trình dựa trên vùng trạng thái [2] ............................. 28
đang và sẽ đóng vai trò vô cùng quan trọng trong việc trích xuất tri thức từ dữ
liệu đã có từ đó có thể tạo lợi thế canh tranh lớn trong kinh doanh. Tuy nhiên các
kỹ thuật này mới chỉ tập trung chủ yếu vào đặc tính của dữ liệu mà đã bỏ qua
một yếu tố vô cùng quan trọng là quá trình thay đổi dữ liệu đã diễn ra như thế
nào? Để làm rõ vai trò quan trọng của yếu tố quá trình (process) này chúng ta
cùng xem xét một ví dụ điển hình đó là các hệ thống thông tin trong các tổ chức
kinh doanh nghiệp vụ. Các hệ thống thông tin này thường hỗ trợ khả năng ghi
chép, tức là lưu lại những gì đã được thực hiện trong quá trình hoạt động của tổ
chức. Loại dữ liệu sự kiện này ngày càng nhiều và có mặt ở khắp nơi. Trong khi
đó, các tổ chức, doanh nghiệp vẫn chỉ lên kế hoạch hoạt động bằng các mô hình
quá trình xây dựng thủ công với nhiều hạn chế, hay xác định các vấn đề trong
quá trình hoạt động qua những nhận định và nắm bắt chủ quan, nhiều khi sai
lệch thực tế.
Thông tin trong dữ liệu sự kiện là chi tiết, chân thực và khách quan về chính
những gì tổ chức đang cố gắng quan sát và nắm bắt. Nếu tổ chức tận dụng được
những thông tin này thì điều đó có thể hỗ trợ rất nhiều cho các quá trình kinh
doanh. Từ những yếu tố trên, khai phá quá trình đã ra đời và trở thành đề tài
nóng được nhiều nhà khoa học quan tâm nghiên cứu.
Phát hiện quá trình là một trong ba bài toán chính của khai phá quá trình với
mục tiêu xây dựng mô hình chỉ từ nhật ký sự kiện mà không sử dụng bất kì một
mô hình hay thông tin tiền nghiệm nào khác. Có rất nhiều thuật toán, phương
pháp phát hiện quá trình khác nhau. Ví dụ: thuật toán α, α+, α++, khai phá kinh
nghiệm, khai phá di truyền, khai phá dựa trên vùng… Mỗi loại đều có những
điểm mạnh điểm yếu riêng. Luận văn sẽ tập trung giới thiệu phương pháp phát
hiện quá trình nâng cao dựa trên vùng trạng thái. Nâng cao ở đây được hiểu với
ý nghĩa đây là một thuật toán ra đời sau, có nhiều ưu điểm hơn các thuật toán
kinh điển ban đầu như thuật toán α.
5
quá trình kinh doanh truyền thống với các kỹ thuật phân tích dữ liệu làm trung
tâm như: khai phá dữ liệu và học máy.
Hình 1.1: Vị trí của khai phá quá trình trong khoa học dữ liệu [2]
7
Hình 1.2: Vai trò cầu nối của khai phá quá trình [6]
Khai phá quá trình là phương tiên giao tiếp giữa phân tích mô hình quá
trình (process model analysis) với phân tích định hướng dữ liệu (data-oriented
analysis). Nó được dùng để trả lời các câu hỏi khác nhau liên quan đến hiệu
năng và tính tuân thủ.
1.1.3. Mối liên hệ với khai phá dữ liệu
Theo Van der Aalst [2], khai phá quá trình liên quan mật thiết đến khai phá
dữ liệu. Trong khi các kĩ thuật khai phá dữ liệu truyền thống chủ yếu tập trung
vào dữ liệu (data-centric) thì khai phá quá trình tập trung vào quá trình
(process-centric).
Khai phá quá trình được sử dụng để trả lời cho các câu hỏi:
- Quá trình nào con người thực sự làm theo?
- Đâu là những trở ngại trong quá trình của tôi?
- Đâu là chỗ mà con người hay máy móc thực hiện khác với lại quá trình
mong đợi hay quá trình lý tưởng ban đầu?
- Đâu là “lối mòn” trong quá trình của tôi?
- Những tác nhân nào đang gây trở ngại?
- Liệu tôi có thể tiên đoán các vấn đề có thể gặp phải (độ trễ, độ sai lệch,
rủi ro,…) trong các trường hợp đang chạy?
- Làm thế nào để thiết kế lại quá trình, tổ chức, máy móc cho hiệu quả?
sinh ra một lưới Petri tương ứng mà không cần sử dụng thêm tri thức bổ sung
nào khác.
Mô hình xây dựng được có thể trả lời các câu hỏi phổ biến trong quá trình
sản xuất kinh doanh như:
- Hoạt động nào nằm trước hoạt động nào?
- Có nhóm hoạt động nào được thực hiện đồng thời không?
- Trong quá trình có hoạt động nào bị lặp không?
- Các nhân viên tương tác như thế nào?
- Những ai làm cùng nhiệm vụ với nhau?
- Có bao nhiêu vị trí tham gia trong một trường hợp?
1.2.2. Kiểm tra độ phù hợp
Bài toán này sử dụng đầu vào gồm một mô hình có sẵn và nhật ký sự kiện.
Mô hình sẽ được sử dụng để kiểm tra xem các sự kiện thực tiễn được lưu trong
nhật ký sự kiện có phù hợp với mô hình không, và ngược lại.
Có thể mô hình đang sử dụng không bao hàm được tất cả các trường hợp
vì thế có những trường hợp các hoạt động không tuân theo mô hình. Cũng có
trường hợp chỉ tồn tại trên mô hình mà thực tế không bao giờ xảy ra. Do vậy, sẽ
luôn hữu ích khi có một công cụ cung cấp phản hồi về những vấn đề này. Bài
toán kiểm tra sự phù hợp của mô hình nhằm cung cấp những công cụ phản hồi
như vậy.
1.2.3. Tăng cường mô hình
Sau có được kết quả của bước kiểm tra độ phù hợp thì bài toán tiếp theo
được đặt ra là tăng cường mô hình. Bài toán hướng tới việc mở rộng hoặc cải
tiến mô hình có sẵn, nhờ rút ra kinh nghiệm từ thông tin về quá trình thực tế đã
thu thập được trong các nhật ký sự kiện. Tăng cường ở đây có 2 loại, một là
“sửa” mô hình để phản ánh đúng hơn với thực tế, hai là “mở rộng” mô hình để
thêm vào các khía cạnh bổ sung.
Tăng cường mô hình giúp tăng hiệu suất làm việc, giải quyết những điểm
mâu thuẫn hoặc bế tắc, loại bỏ các thành phần không cần thiết...
Loại dữ liệu trong nhật ký sự kiện xác định phương diện thông tin nào có
thể được khai phá. Theo Van der Aalst [1], có 4 phương diện khai phá chính:
1) Phương diện luồng điều khiển (control-flow perspective) tập trung vào luồng
điều khiển, tức là thứ tự của các hoạt động. Mục đích của khai phá phương
diện luồng điều khiển là tìm được các đặc tính tốt nhất có thể cho tất cả các
luồng điều khiển. Phương diện luồng điều khiển có thể được khai phá qua
nhật ký sự kiện khi nhật ký sự kiện cung cấp các nhiệm vụ đã được xử lý
trong quá trình (chẳng hạn qua các trường tên công việc, thời gian) và ta có
thể suy luận được thứ tự xử lý và liên kết các nhiệm vụ này vào các trường
hợp (mẫu) riêng biệt.
2) Phương diện tổ chức (organizational perspective) tập trung vào các thông tin
về nguồn lực ẩn trong nhật ký sự kiện, ví dụ như những đối tượng nào (người,
hệ thống, vai trò, bộ phận) tham gia vào hoạt động và các đối tượng liên quan
đến nhau như thế nào. Khai phá phương diện tổ chức ứng dụng cho cơ cấu tổ
chức qua việc phân loại nguồn lực vào các vai trò và đơn vị trổ chức hoặc
qua các thông tin thu được từ mô hình mạng xã hội.
3) Phương diện trường hợp (case perspective) tập trung vào các thuộc tính, đặc
điểm riêng của mỗi trường hợp. Rõ ràng, mỗi trường hợp đều có thể được mô
tả bằng đường đi của nó trong luồng quá trình. Tuy nhiên, ta cũng có thể mô
tả các trường hợp bằng giá trị của các phần tử dữ liệu tương ứng. Ví dụ, nếu
một trường hợp biểu diễn các đơn hàng bổ sung, thì qua đó ta có thể muốn
biết nhà cung cấp hoặc số lượng sản phẩm đã được đặt mua.
4) Phương diện thời gian (time perspective) quan tâm tới thời gian và mức độ
thường xuyên của các sự kiện. Khi các sự kiện được ghi lại cùng với thời
gian, ta có thể phát hiện các điểm thắt cổ chai, đo lường sức phục vụ, giám
sát việc sử dụng tài nguyên, và dự đoán thời gian xử lý còn lại của các trường
hợp đang chạy.
Các phương diện này không tách biệt độc lập mà chồng chéo một phần nào
đó lên nhau, và không đầy đủ. Tuy nhiên, chúng mô tả tốt những đặc điểm mà
khai phá quá trình muốn phân tích.
Hình 1.5: Ví dụ về marking của một lưới Petri cho hệ thống đèn giao thông [2]
Trong dấu khởi tạo thể hiện ở hình 1.4 chỉ có một thẻ, và start là vị trí duy
nhất được đánh dấu.
Định nghĩa 1.1[1]. Lưới Petri là một bộ ba N = (P, T, F) trong đó P là
một tập hữu hạn các vị trí (vị trí), T là một tập hữu hạn các bước chuyển
(transition) sao cho P ∩ T = Ø, và F ⊆ (P × T) ∪ (T × P) là tập các cạnh có
hướng, gọi là luồng quan hệ (flow relation) . Lưới Petri được đánh dấu là một
cặp (N, M), trong đó N = (P, T, F) là một lưới Petri và M ∈ 𝔹(P) là một tập bội
(multi-set) trên P biểu thị dấu (marking) của lưới. Tập tất cả các lưới Petri được
đánh dấu được biểu thị bằng kí hiệu 𝒩.
Theo định nghĩa, lưới Petri trong hình 1.4 có thể chuẩn hóa lại với bộ ba
N = (P, T, F) như sau:
P = {start, cl,c2, c3, c4, c5, end},
T = {a, b, c, d, e, f, g, h}, và
F = {(start, a), (a, cl), (a, c2), (cl, b), (cl, c), (c2, d), (b, c3), (c, c3), (d, c4),
(c3, e), (c4, e), (e, c5), (c5, f ), (f, cl), (f, c2), (c5, g), (c5, h), (g, end), (h, end)}.
Vị trí được đánh dấu trong hình 1.4 là [start], nghĩa là tập bội biểu thị dấu
ở đây chỉ chứa 1 thẻ. Các hành vi động của một lưới Petri được đánh dấu được
xác định bởi luật cháy (firing rule).
14
- Một bước chuyển sẽ được kích hoạt nếu mỗi vị trí đầu vào của nó chứa
một thẻ.
- Một bước chuyển đang kích hoạt sẽ có thể đốt cháy, qua đó tiêu thụ một
thẻ từ mỗi vị trí đầu vào và cung cấp một thẻ cho mỗi vị trí đầu ra.
Hình 1.6: Bước chuyển được kích hoạt và có thể cháy [2]
Trong hình 1.4, bước chuyển a được kích hoạt nhờ dấu [start]. Việc đốt
- Một lưới Petri là sống nếu tất cả các bước chuyển là sống.
- Một lưới Petri là sống thì deadlock-free. Tuy nhiên một lưới Petri là
deadlock-free thì không chắc là sống.
1.3.2.2.
Hệ thống chuyển (Transition systems)
Hình 1.7: Một hệ thống chuyển có một trạng thái khởi đầu
và một trạng thái kết thúc[1]
Hệ thống chuyển là loại kí hiệu mô hình quá trình cơ bản nhất. Hệ thống
chuyển bao gồm các trạng thái (state) và các bước chuyển (transition). Hình 1.7
mô tả một hệ thống chuyển với 7 trạng thái. Các trạng thái được biểu diễn bằng
hình tròn màu đen. Có một trạng thái khởi tạo được gán nhãn sl và trạng thái kết
thúc được gán nhãn s7. Mỗi trạng thái có một nhãn riêng biệt, nhãn này chỉ đơn
giản là định danh cho trạng thái và không có ý nghĩa gì cả. Các bước chuyển
16
được biểu diễn bằng các cạnh. Mỗi bước chuyển kết nối hai trạng thái và được
gán nhãn bởi tên của một hoạt động. Nhiều cạnh có thể có cùng nhãn, ví dụ
trong hình này nhãn "check ticket” xuất hiện 2 lần.
Định nghĩa hệ thống chuyển như sau:
Định nghĩa 1.2[1]. Hệ thống chuyển là một bộ ba TS = (S, A, T) trong đó
S là tập các trạng thái (state), A ⊆ 𝒜 là tập các hoạt động (activity), và T ⊆ S ×
A × S là tập các bước chuyển (transition). Sstart ⊆ S là tập các trạng thái ban đầu
(trạng thái bắt đầu), và Send ⊆ S là tâp các trạng thái cuối cùng (trạng thái kết
thúc).
Các tập hợp Sstart và Send được xác định ngầm. Về nguyên tắc, tập S có thể vô
hạn. Tuy nhiên, trong hầu hết các ứng dụng trên thực tế, không gian trạng thái là
hữu hạn. Trong trường hợp này, hệ thống chuyển cũng được coi là một máy hữu
được định nghĩa giúp hệ thống chuyển có thể dễ dàng dịch sang các ngôn ngữ
mô hình hóa bậc cao như lưới Petri, BPMN, UML...
Các hệ thống chuyển khá đơn giản nhưng lại gặp vấn đề trong biểu diễn
các đồng thời một cách ngắn gọn. Giả sử khi ta có n hoạt động song song, nghĩa
là n hoạt động cần thi hành nhưng theo thứ tự nào cũng được. Ta sẽ có thể có n!
trình tự hoạt động. Hệ thống chuyển sẽ yêu cầu 2n trạng thái và n × 2n-1 bước
chuyển. Đây là một ví dụ về vấn đề "bùng nổ trạng thái” (state explosion). Xem
xét ví dụ 10 hoạt động song song, số trình tự thi hành có thể có là 10! = 3628800,
số trạng thái có thể đạt tới là 210 = 1024, và số bước chuyển là 10 × 210-1 = 5120.
Lưới Petri tương ứng sẽ gọn hơn rất nhiều và chỉ cần 10 bước chuyển, 10 vị trí
để mô hình hóa 10 hoạt động song song. Để giải quyết vấn đề đồng thời trong
các quá trình thương mại, ta cần sử dụng các mô hình ý nghĩa hơn như lưới Petri
để thể hiện được đầy đủ kết quả khai phá quá trình.
1.4.
Tóm tắt chương 1
Chương 1 của luận văn đã giới thiệu tổng quan về khai phá quá trình, vị
trí, vai trò và các nhóm bài toán chính trong khai phá quá trình. Các khái niệm,
đặc điểm chính của nhật ký sự kiện, các phương diện khai phá đã được đề cập.
Tiếp theo, các khái niệm cơ bản và các đặc tính chính của hai loại mô hình hóa
được sử dụng trong luận văn là lưới Petri, và hệ thống chuyển đã được giới thiệu
khá chi tiết.
Trong chương tiếp theo của luận văn, sẽ đi chi tiết hơn vào một trong ba
bài toán chính trong khai phá quá trình là bài toán phát hiện quá trình.
18
Chương 2. PHÁT HIỆN QUÁ TRÌNH VÀ NHỮNG THÁCH THỨC
N là một lưới WF (workflow-net, WF-net) phù hợp và tất cả các vết trong L
tương ứng với trình tự cháy thích hợp của (N,M).
2.1.2. Giới thiệu thuật toán Alpha
Thuật toán α được WMP van der Aalst và cộng sự nghiên cứu và đề xuất
năm 2004 [12]. Đây là một thuật toán khá đơn giản, ứng dụng đặc điểm của lưới
WF, rằng trong nhiều lưới WF, hai hoạt động có sự kết nối với nhau nếu xác
định được quan hệ nhân quả của chúng trong nhật kí sự kiện.
Đầu vào: Nhật kí sự kiện L với tập các hoạt động T.
Đầu ra: Lưới Petri α(L) mô hình hóa L với hai vị trí đầu, cuối được định nghĩa
như dưới đây:
Giải thích thuật toán:
Bước 1: Mọi bước chuyển của lưới đầu ra TL : mỗi hoạt động trong L tương
ứng với một bước chuyển trong α(L)
Bước 2: Mọi bước chuyển được nối từ vị trí vào i (start): TI đó là các phần tử
đầu tiên ở mỗi vết 〈t1, …, tn〉, …, 〈t’1, …, t’m〉
Bước 3: Mọi bước chuyển nối tới vị trí ra o (end): TO đó là các phần tử xuất
hiện ở cuối mỗi vết 〈t1, …, tn〉, …, 〈t’1, …, t’m〉
Bước 4: Xác định mọi cặp tập song kết nối (A, B). mọi phần tử a∈A và mọi
phần tử b∈B là quan hệ nhân quả (ví dụ a →L b), tất cả các phần tử trong A
là độc lập với nhau (a1#La2), và tất cả các phần tử trong B là độc lập với
nhau (b1#Lb2).
Copyright: Tài liệu đại học ©