Mẫu báo cáo

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÁO CÁO HỌC PHẦN DỰ ÁN Đề tài
TRÍCH XUẤT ĐẶC TRƯNG TRÊN DỮ LIỆU
OCEL BẰNG PHƯƠNG PHÁP
XÂY DỰNG ĐỒ THỊ
Giảng viên hướng dẫn: ThS. Nguyễn Thị Thùy Linh
Họ và tên: Long Hoàng Vinh Mã sinh viên: 22022673 Lớp: K67-AI2 Ý kiến đánh giá:
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
…………………………………………………………………………………………………………….
Điểm số ……………. Điểm chữ …………….
Hà Nội, ngày …, tháng…, năm 20… . Giảng viên đánh giá (Ký, ghi rõ họ tên) LỜI CẢM ƠN
Lời đầu tiên, em xin được gửi lời cảm ơn chân thành nhất đến cô Nguyễn Thị
Thùy Linh. Trong quá trình học tập và tìm hiểu môn Dự án, em đã nhận được rất
nhiều sự quan tâm, giúp đỡ, hưỡng dẫn tâm huyết và tận tình của cô. Cô đã giúp
em tích lũy thêm nhiều kiến thức về môn học này để có thể hoàn thành được
bài tiểu luận về đề tài: Trích xuất đặc trưng trên dữ liệu OCEL bằng phương
pháp xây dựng đồ thị
Trong quá trình làm bài chắc chắn khó tránh khỏi những thiếu sót. Do đó, em
kính mong nhận được những lời góp ý của Cô để bài tiểu luận của em ngày càng hoàn thiện hơn. Em xin chân thành cảm ơn! TỔNG QUAN
Báo cáo này trình bày quá trình thực nghiệm lại bài báo mang tên “Graph-
Based Feature Extraction on Object-Centric Event Logs for Process Mining” , với
mục tiêu tìm hiểu, triển khai lại và đánh giá phương pháp trích xuất đặc trưng
dựa trên đồ thị từ nhật ký sự kiện hướng đối tượng (Object-Centric Event Logs – OCEL).
Trong bối cảnh process mining hiện đại, OCEL được coi là định dạng mở rộng
giúp khắc phục các hạn chế của nhật ký truyền thống khi mô hình hóa các quy
trình có nhiều loại đối tượng tương tác với nhau. Tuy nhiên, việc phân tích OCEL
đòi hỏi những kỹ thuật biểu diễn dữ liệu và trích xuất đặc trưng mới. Bài báo
trên đề xuất một phương pháp có hệ thống để xây dựng ba loại đồ thị đặc trưng
(Interaction Graph, Creation Graph, và Continuation Graph), từ đó trích xuất các
đặc trưng đồ thị và tổng hợp thành vector đại diện cho toàn bộ log, giúp phục
vụ các tác vụ học máy như phân loại log hoặc phát hiện bất thường. MỤC LỤC
LỜI CẢM ƠN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
TỔNG QUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. GIỚI THIỆU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1. Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2. Mục tiêu nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3. Câu hỏi nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2. CƠ SỞ LÝ THUYẾT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1. Tổng quan về Process Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2. Dữ liệu Procure-to-Pay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3. Khai phá quy trình hướng đối tượng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4. Object-Centric Event Log (OCEL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5. Đặc trưng trong Process Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3. PHƯƠNG PHÁP TRÍCH SUẤT ĐẶC TRƯNG OCEL TỪ ĐỒ THỊ . . . . . . . . . . 15
3.1. Biểu diễn đối tượng bằng đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1. Object Interaction Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.2. Object Creation Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.3. Object Continuation Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2. Đặc trưng từ đồ thị hướng đối tượng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1. Basic Feature Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2. Graph Based Feature Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3. Lan truyền đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4. THỰC NGHIỆM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1. Phát hiện bất thường các thay đổi xảy ra sau yêu cầu mua hàng . . . . . 20
4.2. Phát hiện bất thường trong hợp đồng bảo trì . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3. Phát hiện trường hợp mua hàng tự phát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.4. Phát hiện bất thường bằng Isolation Forest . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.5. Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5. KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 DANH SÁCH HÌNH ẢNH
Hình 1 Minh họa các trụ cột trong Process Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Hình 2 Object Interation Graph với dữ liệu từ Bảng 1 . . . . . . . . . . . . . . . . . . . . . . . . . 16
Hình 3 Object Creation Graph với dữ liệu từ Bảng 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Hình 4 Object Creation Graph với dữ liệu từ Bảng 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Hình 5 Kết quả khi sử dụng PCA trong phát hiện bất thường bằng Isolation
Forest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 DANH SÁCH BẢNG
Bảng 1 Ví dụ về một OCEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Bảng 2 Kết quả của quá trình thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1. GIỚI THIỆU 1.1. Đặt vấn đề
Trong thời đại chuyển đổi số, các hệ thống thông tin hiện đại ngày càng
trở nên phức tạp, dẫn đến việc sinh ra khối lượng lớn dữ liệu về quá trình
hoạt động của doanh nghiệp. Process Mining [1] là lĩnh vực nghiên cứu
nhằm khai thác thông tin có giá trị từ các event log (nhật ký sự kiện) để
phân tích, tối ưu và tái thiết kế quy trình nghiệp vụ. Tuy nhiên, các phương
pháp truyền thống trong Process Mining chủ yếu dựa trên giả định rằng
mỗi sự kiện liên quan đến duy nhất một case (hoặc quy trình), điều này
không phản ánh đúng bản chất của các hệ thống thực tế, nơi một sự kiện
có thể liên quan đến nhiều đối tượng cùng lúc.
Nhằm giải quyết hạn chế đó, chuẩn Object-Centric Event Logs (OCEL)
[2] đã được đề xuất như một định dạng mới cho phép mô hình hóa mối quan
hệ nhiều-nhiều giữa sự kiện và đối tượng. Tuy nhiên, việc phân tích OCEL
lại đặt ra những thách thức mới: các phương pháp hiện tại chưa được thiết
kế để làm việc với dữ liệu phức tạp này, đặc biệt là trong việc trích xuất đặc
trưng (feature extraction) cho các bài toán học máy (machine learning) như
phân loại, phân cụm hoặc phát hiện bất thường trong quy trình.
Bài báo Graph-Based Feature Extraction on Object-Centric Event Logs
for Process Mining [3] đề xuất một phương pháp trích xuất đặc trưng dựa
trên đồ thị từ OCEL, với mục tiêu tạo ra các biểu diễn đặc trưng hữu ích,
không phụ thuộc vào các giả định về quy trình cụ thể. Việc trích xuất này
diễn ra thông qua việc xây dựng đồ thị biểu diễn mối liên hệ giữa các đối
tượng trong log, sau đó áp dụng các chỉ số đồ thị như PageRank, degree
centrality, clustering coefficient, v.v., để tạo ra các vector đặc trưng đại diện
cho từng log. Một khi các đặc trưng đã được tạo ra từ dữ liệu OCEL, chúng sẽ
được sử dụng trong một số tác vụ phân tích quy trình thông thường, qua đó
giúp chúng ta hiểu hơn về các vấn đề đang xảy ra với quy trình nghiệp vụ.
1.2. Mục tiêu nghiên cứu
Dự án này hướng đến việc thực nghiệm lại phương pháp đã được đề xuất
trong bài báo “Graph-Based Feature Extraction on Object-Centric Event
Logs for Process Mining” [3], với mục tiêu chính là kiểm chứng hiệu quả
của hướng tiếp cận này trong thực tế. Cụ thể, dự án tập trung vào việc hiểu
rõ và triển khai lại toàn bộ pipeline trích xuất đặc trưng từ nhật ký sự kiện
hướng đối tượng (OCEL) thông qua các biểu diễn đồ thị. Sau khi thu được
các đặc trưng, chúng được ứng dụng vào một số tác vụ phân tích quy trình 8
điển hình từ đó xác định và suy diễn các vấn đề tiềm ẩn hoặc các điểm bất
thường đang tồn tại trong quy trình nghiệp vụ.
1.3. Câu hỏi nghiên cứu
Dự án này tập trung vào việc giải quyết hai câu hỏi nghiên cứu chính
liên quan đến việc phân tích dữ liệu theo định dạng OCEL (Object-Centric
Event Log) để hiểu rõ hơn về các quy trình nghiệp vụ:
1. Trích xuất đặc trưng từ dữ liệu OCEL bằng kỹ thuật xây dựng đồ
thị: Liệu các kỹ thuật xây dựng đồ thị có khả năng chuyển đổi thông
tin phức tạp trong dữ liệu OCEL thành các đặc trưng số học có cấu trúc,
nắm bắt được mối quan hệ giữa các đối tượng và sự kiện trong nhật ký hay không?
2. Ứng dụng đặc trưng trích xuất để suy diễn vấn đề quy trình: Các
đặc trưng được trích xuất từ dữ liệu OCEL thông qua kỹ thuật xây dựng
đồ thị có thể được sử dụng như thế nào để xác định và suy diễn các vấn
đề tiềm ẩn hoặc các điểm bất thường đang tồn tại trong quy trình nghiệp
vụ được ghi lại trong nhật ký sự kiện? 2. CƠ SỞ LÝ THUYẾT
2.1. Tổng quan về Process Mining
Process Mining [1] là một lĩnh vực nghiên cứu kết hợp giữa khoa học dữ
liệu và quản lý quy trình nghiệp vụ (Business Process Management - BPM).
Mục tiêu của nó là khai thác các mô hình và hiểu biết về quy trình từ dữ
liệu sự kiện (event logs) được thu thập từ các hệ thống thông tin như ERP,
CRM hoặc hệ thống quản lý quy trình công việc.
Ba trụ cột chính trong Process Mining bao gồm:
• Discovery (khám phá quy trình): biến dữ liệu sự kiện thành các mô hình
quy trình bằng cách sử dụng các kỹ thuật khám phá quy trình. Các mô
hình được khám phá này nhằm mục đích mô tả quy trình cơ bản. Các
mô hình quy trình được khám phá có thể tập trung vào hành vi chủ đạo,
thường xuyên trong dữ liệu sự kiện hoặc cũng bao gồm cả các hành vi
không thường xuyên. Có sẵn một loạt các kỹ thuật khám phá quy trình [4], [5], [6], [7]
• Conformance checking (kiểm tra sự phù hợp): so sánh giữa log thực tế và
mô hình quy trình đã biết. Nhận đầu vào là dữ liệu sự kiện và các mô hình
quy trình. Các mô hình quy trình này có thể được tạo ra bằng cách sử
dụng khám phá quy trình hoặc được tạo thủ công (hoặc kết hợp cả hai). 9
Dữ liệu sự kiện được “chạy lại” (replayed) trên các mô hình này. Điều này
làm lộ ra tất cả các sự khác biệt giữa dữ liệu và mô hình.[1], [8]
• Enhancement (nâng cao): cải tiến mô hình quy trình hiện có bằng cách
sử dụng dữ liệu log [9]. Điều này có thể bao gồm các kỹ thuật học máy
(ML) [10] hiện đại sử dụng mạng nơ-ron hoặc các phương pháp khai phá
dữ liệu (DM) và thống kê cổ điển, chẳng hạn như cây quyết định [11] và hồi quy .
Hình 1: Minh họa các trụ cột trong Process Mining
Tuy nhiên, các phương pháp truyền thống chủ yếu làm việc với event
logs dạng dòng tuyến tính, trong đó mỗi sự kiện được gán với đúng một
“case” (một instance của quy trình).
2.2. Dữ liệu Procure-to-Pay
Dữ liệu Procure-to-Pay (P2P) [12] là toàn bộ thông tin được tạo ra, thu
thập và quản lý trong suốt quy trình mua sắm hàng hóa và dịch vụ của một
tổ chức, từ khi phát sinh nhu cầu cho đến khi hoàn tất thanh toán cho nhà
cung cấp. Đây là một tập hợp dữ liệu quan trọng, phản ánh chi tiết các hoạt
động mua hàng và có vai trò thiết yếu trong việc quản lý chi tiêu, tối ưu
hóa quy trình và ra quyết định chiến lược.
Quy trình Procure-to-Pay (P2P) là một hệ thống tích hợp các bước nhằm
hợp lý hóa và tự động hóa việc yêu cầu, mua sắm, tiếp nhận và thanh toán
cho hàng hóa, dịch vụ. Quy trình này thường bao gồm các giai đoạn chính như:
• Xác định nhu cầu và yêu cầu mua hàng: Phát sinh nhu cầu, tạo yêu cầu
mua hàng (purchase requisition).
• Tìm kiếm và lựa chọn nhà cung cấp: Đánh giá, so sánh và chọn lựa nhà cung cấp phù hợp.
• Đặt hàng (Purchase Order - PO): Tạo và gửi đơn đặt hàng chính thức cho nhà cung cấp. 10
• Nhận hàng và kiểm tra: Tiếp nhận hàng hóa/dịch vụ, kiểm tra số lượng
và chất lượng so với đơn đặt hàng.
• Xử lý hóa đơn: Nhận hóa đơn từ nhà cung cấp, đối chiếu với đơn đặt hàng và biên bản nhận hàng.
• Phê duyệt và thanh toán: Phê duyệt hóa đơn và thực hiện thanh toán cho nhà cung cấp.
• Theo dõi và báo cáo: Ghi nhận, lưu trữ và phân tích dữ liệu giao dịch.
2.3. Khai phá quy trình hướng đối tượng
Phương pháp khai phá quy trình truyền thống thường dựa trên giả định
rằng mỗi sự kiện trong nhật ký chỉ liên quan đến một trường hợp hoặc đối
tượng duy nhất. Tuy nhiên, trong các hệ thống thông tin phức tạp của thế
giới thực, giả định này thường không còn phù hợp. Ví dụ điển hình là các
sự kiện trong hệ thống hoạch định nguồn lực doanh nghiệp (ERP), nơi một
giao dịch mua hàng có thể liên quan đồng thời đến nhiều đối tượng khác
nhau như đơn hàng, sản phẩm, nhà cung cấp và khách hàng.
Nhận thấy những hạn chế này, sự quan tâm đến khai phá quy trình hướng
đối tượng (OCPM) ngày càng tăng lên. Kỹ thuật tiên tiến này được phát
triển để giải quyết các vấn đề hội tụ (convergence) và phân kỳ (divergence)
thường gặp phải khi phân tích nhật ký sự kiện theo phương pháp truyền thống.
Vấn đề hội tụ [13]: Vấn đề hội tụ phát sinh khi một sự kiện thực tế cần
được sao chép và gán cho nhiều trường hợp khác nhau trong nhật ký sự
kiện truyền thống. Điều này dẫn đến sự trùng lặp dữ liệu và làm phức tạp
quá trình phân tích, đồng thời có thể làm sai lệch bức tranh thực tế của quy trình.
Vấn đề phân kỳ [13]: Ngược lại, vấn đề phân kỳ xảy ra khi nhiều phiên
bản khác nhau của cùng một hoạt động được ghi nhận trong cùng một
trường hợp (case). Hiện tượng này thường mô tả một vòng lặp không thực
sự tồn tại trong quy trình kinh doanh, gây khó khăn trong việc hiểu đúng
luồng công việc và xác định các điểm cần cải thiện.
Xét một đơn hàng 𝑜 bao gồm mười mặt hàng 𝑖 , và các hoạt động 1, 𝑖2, …𝑖10
place_order, pick_item, pack_item.
place_order liên quan tới đối tượng 𝑜, 𝑖 , được kí hiệu là 1, 𝑖2, …𝑖10
place_order(𝑜, 𝑖1, 𝑖2, …, 𝑖10). Có 10 sự kiện pick_item, mỗi sự kiện liên quan
tới 𝑜 và một trong các mặt hàng, được kí hiệu pick_item(𝑜, 𝑖𝑘) | 1 ≤ 𝑘 ≤
10. Tương tự có 10 sự kiện pack_item, được kí hiệu pack_item(𝑜, 𝑖𝑘) | 1 ≤ 𝑘 ≤ 10 11
Nếu ta coi item là case, vậy nên sự kiện place_order(𝑜, 𝑖1, 𝑖2, …𝑖10)
cần phải chuyển thành 10 sự kiện place_order(𝑖1), place_order(𝑖2),…
place_order(𝑖10). Mặc dù hoạt động place_order chỉ xảy ra một lần, nhật ký
sự kiện đã làm phẳng sẽ cho thấy nó xảy ra mười lần. Đây là vấn đề hội tụ
ảnh hưởng đến các thống kê liên quan đến tần suất, thời gian, chi phí.
Nếu chọn order là case, thì lượng sự kiện cũng không đổi, tức là không
có vấn đề hội tụ, nhưng lại có vấn đề phân kì, vì có một sự kiện place_order,
mười sự kiện pick_item và mười sự kiện pack_item.
Do vấn đề phân kỳ, mười sự kiện pick_item(o) và mười sự kiện
pack_item(o) trở nên không thể phân biệt được. Kết quả là, mối quan hệ
nhân quả rõ ràng giữa pick_item(o) và pack_item(o) bị mất.
Các ví dụ về hội tụ và phân kỳ ở trên cho thấy những hạn chế của nhật
ký và mô hình sự kiện truyền thống. Bằng cách chỉ tập trung vào các item,
người ta không còn có thể thấy tần suất hoạt động chính xác, dẫn đến một
cái nhìn bị bóp méo. Bằng cách chỉ tập trung vào các order, người ta không
còn có thể thấy các mối quan hệ nhân quả. Vì vậy cẩn phải có cách biểu
diễn dữ liệu hiệu quả hơn.
2.4. Object-Centric Event Log (OCEL)
Để khắc phục hạn chế trên, định dạng Object-Centric Event Logs (OCEL)
[2] đã được đề xuất, cho phép một sự kiện liên quan đến nhiều đối tượng
thuộc nhiều loại khác nhau. OCEL phản ánh chính xác hơn các hệ thống
phức tạp trong thực tế, nơi mà các thực thể (đơn hàng, khách hàng, sản
phẩm…) tương tác với nhau theo cách không tuyến tính.
Ví dụ: Trong một hệ thống thương mại điện tử, một sự kiện “thanh
toán thành công” có thể liên quan đến một đơn hàng, một khách hàng và
một phương thức thanh toán. Một object-centric event log là một bộ 𝐿 =
(𝐸, 𝐴𝑁 , 𝐴𝑉 , 𝑂𝑇 , 𝑂, 𝜋act, 𝜋time, 𝜋vmap, 𝜋omap, 𝜋otyp, 𝜋ovmap, ≤) mà:
• 𝐸 ⊆ 𝑈 là tập hợp các định danh sự kiện. 𝑒
• 𝐴𝑁 ⊆ 𝑈 là tập hợp các tên thuộc tính. att
• 𝐴𝑉 ⊆ 𝑈 à tập hợp các giá trị thuộc tính (với yêu cầu là val 𝐴𝑁 ∩ 𝐴𝑉 = ∅).
• 𝑂𝑇 ⊆ 𝑈 là tập hợp các kiểu đối tượng. ot
• 𝐴 ⊆ 𝑈 là tập hợp các kiểu đối tượng. o • 𝜋
là hàm ánh xạ một sự kiện (định danh) tới hoạt động act : 𝐸 ⟶ 𝑈act của nó. • 𝜋
là hàm ánh xạ một sự kiện (định danh) tới dấu thời time : 𝐸 ⟶ 𝑈timest gian của nó. 12
• 𝜋vmap : 𝐸 ⟶ (𝐴𝑁 ↛ 𝐴𝑉 ) à hàm ánh xạ một sự kiện (định danh) tới các
gán giá trị thuộc tính của nó.
• 𝜋omap : 𝐸 ⟶ 𝒫(𝑂) là hàm ánh xạ một sự kiện (định danh) tới một tập
hợp các định danh đối tượng liên quan.
• 𝜋otyp : 𝑂 ⟶ 𝑂𝑇 gán chính xác một kiểu đối tượng cho mỗi định danh đối tượng.
• 𝜋ovmap : 𝑂 ⟶ (𝐴𝑁 ↛ 𝐴𝑉 ) là hàm ánh xạ một đối tượng tới các gán giá trị thuộc tính của nó.
• ≤ là một quan hệ thứ tự toàn phần trên các sự kiện (tức là, nó thỏa mãn
các tính chất phản đối xứng, bắc cầu và liên thông). Một cách khả thi để
định nghĩa một thứ tự toàn phần là xem xét các dấu thời gian liên kết với
các sự kiện như một tiền thứ tự (tức là, giả định một thứ tự tùy ý nhưng
cố định cho các sự kiện có cùng dấu thời gian).
Bảng 1 minh họa một ví dụ về một bộ dữ liệu OCEL trong dữ liệu P2P. 13 Ev.ID Activity Timestamp Purch.req
Purch.ord. GoodIssues Invoice Payment e1
create purchase req 2021-03-20 10:30 [PR1] e2 close purchase req 2021-03-20 14:30 [PR1] e3
create purchase req 2021-03-21 10:30 [PR2] e4
create purchase ord 2021-03-22 14:30 [PR2] [PO1] e5 invoice receipt 2021-03-35 11:00 [PO1] [R1] e6 perform payment 2021-03-30 11:58 [R1] [P1] e7 create purchase req 2021-04-01 9:15 [PR3] e8 pr formal approval 2021-04-01 10:15 [PR3] e9
create purchase ord 2021-04-02 17:30 [PR3] [PO2] e10 change purch req 2021-04-03 10:30 [PR3] e11 invoie receipt 2021-04-05 15:00 [PO2] [R2] e12 perform payment 2021-03-22 14:30 [R2] [P2] e13
create purchase ord 2021-04-17 14:30 [PO3] e14 invoice receipt 2021-04-28 10:00 [PO3] [R3] e15 perform payment 2021-04-28 15:00 [R3] [P3] e16 invoice receipt 2021-05-28 10:00 [PO3] [R4] e17 perform payment 2021-05-28 15:05 [R4] [P4] e18 invoice receipt 2021-06-28 10:00 [PO3] [R5] e19 perform payment 2021-06-28 15:35 [R5] [P5] e20
create purchase req 2021-07-01 14:30 [PR4] e21 create purchase ord 2021-07-02 9:45 [PR4] [PO4] e22 invoice receipt 2021-07-09 10:00 [PO4] [R6] e23 goods issue 2021-03-11 14:30 [PO4] [GI1] e24 perform payment 2021-05-15 15:35 [R6] [P6] e25 invoice receipt 2021-05-20 12:00 [R7] e26
create purchase ord 2021-05-20 14:30 [PO5] [R7] e27
create purchase ord 2021-03-20 16:30 [PO6] e28
create purchase ord 2021-06-02 14:30 [PO7] e29 create purchase ord 2021-06-05 9:00 [PO6, PO7] [R8]
Bảng 1: Ví dụ về một OCEL
2.5. Đặc trưng trong Process Mining
Để áp dụng các kỹ thuật Data Mining, Thống kê, Học máy vào Process
Mining, cần chuyển đổi dữ liệu event log sang dạng vector đặc trưng
(feature vector). Một số đặc trưng phổ biến trong các event log truyền thống gồm: • Số lượng sự kiện
• Thời gian giữa các sự kiện
• Tần suất xuất hiện của các hoạt động 14
Tuy nhiên, những đặc trưng này không còn phù hợp với OCEL, vì trong
OCEL không còn khái niệm rõ ràng về “case” như trong log truyền thống.
Do đó, cần một phương pháp mới để trích xuất đặc trưng phi tuyến tính, ví
dụ như từ biểu diễn đồ thị.
3. PHƯƠNG PHÁP TRÍCH SUẤT ĐẶC TRƯNG OCEL TỪ ĐỒ THỊ
3.1. Biểu diễn đối tượng bằng đồ thị
Một đồ thị hướng đối tượng diễn tả các mối quan hệ giữa các đối tượng của một bộ OCEL.
Đồ thị hướng đối tượng được định nghĩa là một tập hợp các đối tượng 𝑂 ⊆ 𝑈 và 𝑜
Λ ⊆ 𝑂 × 𝑂, (𝑂, Λ).
Có 3 loại đồ thị hướng đối tượng quan trọng nhất đó chính là: Object
Interaction Graph, Object Creation Graph, Object Continuation Graph
3.1.1. Object Interaction Graph
Object Creation Graph 𝐺 = (𝑂, Λ), Λ = ∪𝑒∈𝐸 {(𝑜1, 𝑜2)| 𝑜1, 𝑜2 ∈
𝜋omap(𝑒) ∧ 𝑜1 ≠ 𝑜2}.
Theo như định nghĩa trên, đồ thị này sẽ nối toàn bộ các đối tượng cùng
xuất hiện liên quan tới một sự kiện trong log. Các nút của đồ thị là đối tượng,
tập các cạnh Λ thể hiện cặp đối tượng cùng xuất hiện, quan hệ này có tính
đối xứng nên ta sử dụng một đồ thị không có hướng để thể hiện mối quan
hệ này. Hình 1 thể hiện một ví dụ về Object Interation Graph đươc xây dựng
dựa trên bộ dữ liệu từ Bảng 1. Cụ thể ta có thể thấy được 𝑃 𝑂6, 𝑃 𝑂7, 𝑅8
đều nằm trong 𝑒29, vì vậy chúng được nối với nhau.
Object Interation Graph có thể được sử dụng để xem liệu một mối quan
hệ dự kiến có tồn tại hay không. Ví dụ, chúng ta có thể kỳ vọng rằng mọi
đơn đặt hàng trong một hệ thống P2P đều được kết nối với ít nhất một yêu
cầu mua hàng (điều này ngụ ý rằng đơn hàng đã tuân theo một quy trình phê duyệt tiêu chuẩn) 15
Hình 2: Object Interation Graph với dữ liệu từ Bảng 1
3.1.2. Object Creation Graph
Object Creation Graph 𝐺 = (𝑂, Λ), Λ = ∪𝑒∈𝐸 {(𝑜1, 𝑜2)| 𝑜1, 𝑜2 ∈
𝜋omap(𝑒) ∧ 𝑒 ≠ start(𝑜1) ∧ 𝑒 = start(𝑜2)}.
Đồ thị này xem xét chuỗi các sự kiện trong nhật ký, đối với mỗi sự kiện,
kết nối mọi đối tượng đã tồn tại trước đó (tức là, một đối tượng bắt đầu trước
sự kiện hiện tại) với mọi đối tượng mới (vòng đời của đối tượng này bắt đầu
với sự kiện hiện tại).
Nhìn vào Bảng 1, 𝑃 𝑅2 (bắt đầu vòng đời của nó trong 𝑒3 và thuộc về các
đối tượng liên quan của sự kiện 𝑒4) được kết nối trong đồ thị tạo đối tượng
với 𝑃 𝑂1 (bắt đầu vòng đời của nó trong 𝑒4). Hình 2 minh họa một ví dụ về
Object Creation Graph được tính toán dựa trên nhật ký sự kiện được mô tả
trong Bảng 1. Trong trường hợp này, quan hệ là bất đối xứng, và chúng ta
có thể biểu diễn một đồ thị có hướng.
Một ví dụ cụ thể khác với Object Interation Graph được mô tả trong Hình
2, 𝑃 𝑂6 và 𝑃 𝑂7 không được kết nối trực tiếp, nhưng chúng được kết nối
bởi một cung tới 𝑅8 (vì 𝑅8 bắt đầu vòng đời của nó trong 𝑒29 và cả 𝑃 𝑂6
lẫn 𝑃 𝑂7 đều bắt đầu vòng đời của chúng sớm hơn và kết thúc tại 𝑒29).
Object Creation Graph có thể được sử dụng để xem liệu các mối quan hệ
giữa các đối tượng có tuân theo thứ tự thời gian dự kiến hay không. Ví dụ,
trong một hệ thống P2P, chúng ta có thể kỳ vọng một đơn đặt hàng sẽ được
theo sau bởi hóa đơn chứ không phải ngược lại 16
Hình 3: Object Creation Graph với dữ liệu từ Bảng 1
3.1.3. Object Continuation Graph
Object Continuation Graph 𝐺 = (𝑂, Λ), Λ = ∪𝑒∈𝐸 {(𝑜1, 𝑜2)| 𝑜1, 𝑜2 ∈
𝜋omap(𝑒) ∧ 𝑒 ≠ start(𝑜1) ∧ 𝑒 = end(𝑜1) ∧ 𝑒 = start(𝑜2)}.
Object Contination Graph kết nối hai đối tượng 𝑜1, 𝑜2 ∈ 𝑂 khi vòng đời
của 𝑜 kết thúc bởi cùng sự kiện mà vòng đời của bắt đầu. 1 𝑜2
Nhìn vào Bảng 1, chúng ta thấy rằng sự kiện e4 kết thúc vòng đời của
yêu cầu mua hàng 𝑃 𝑅2 và bắt đầu vòng đời của đơn đặt hàng 𝑃 𝑂1. Do đó,
𝑃 𝑅2 và 𝑃 𝑂1 được kết nối trong Object Continuation Graph. Hình 3 minh
họa một ví dụ về Object Continuation Graph được tính toán dựa trên nhật
ký sự kiện được mô tả trong Bảng 1. Trong trường hợp này, quan hệ là bất
đối xứng, và chúng ta có thể biểu diễn một đồ thị có hướng.
Khi nhìn vào Bảng 1, khác với Object Creation Graph được hiển thị trong
Hình 2, yêu cầu mua hàng 𝑃 𝑅3 không được kết nối với đơn đặt hàng 𝑃 𝑂2,
bởi vì yêu cầu mua hàng bị thay đổi sau khi vòng đời của 𝑃 𝑂2 bắt đầu.
Object Continuation Graph chứa một tập hợp con các cạnh có trong Object Creation Graph.
Hình 4: Object Creation Graph với dữ liệu từ Bảng 1 17
3.2. Đặc trưng từ đồ thị hướng đối tượng
Ma trận đặc trưng dựa trên đồ thị hướng đối tượng ánh xạ mỗi đối tượng
trong một OCEL tới một tập hợp các đặc trưng số. Điều này rất cần thiết
để thực hiện bất kỳ tác vụ học máy nào (phân loại, dự đoán, phát hiện bất thường, …).
• Object-Based Feature Map: giả sử có một tập hợp đối tượng 𝑂 ⊆ 𝑈 và một 𝑜
tập hợp đặc trưng ∑ ⊆ 𝑈 , một Object-Based Feature Map là một hàm ∑ số: 𝑂 → (∑ → ℝ)
Có hại loại đặc trưng có thể tính toán khi đã mô hình hóa dữ liệu thành
đồ thị, thứ nhất là các đặc trưng truyền thống(Basic Feature Map) 3.2.1. Basic Feature Map
Gọi 𝐿 là một bộ OCEL, có ACT = {𝜋act(𝑒) | 𝑒 ∈ 𝐸} và ∑ =
{numrelevs, throughput, wip} ∪ {#@𝑎 | 𝑎 ∈ ACT} khi mà @ là phép nối
chuỗi. các đặc trưng cơ bản 𝑓bas : 𝑂 → ℝ được xác định như sau:
• với 𝑜 ∈ 𝑂, 𝑓bas(𝑜)(numrelevs) = |lif(𝑜)|
• với 𝑜 ∈ 𝑂, 𝑓bas(𝑜)(throughput) = 𝜋time(end(𝑜)) − 𝜋time(start(𝑜))
• với 𝑜 ∈ 𝑂, 𝑓bas(𝑜)(wip) = |{𝑜′ ∈ 𝑂 | [𝜋time(end(𝑜)), 𝜋time(start(𝑜)] ∩
[𝜋time(end(𝑜′)), 𝜋time(start(𝑜′)] ≠ ∅}|
• với 𝑜 ∈ 𝑂 và 𝑎 ∈ ACT, 𝑓bas(𝑜)(#@a) = |{𝑒 ∈ lif(0)| 𝜋act(𝑒) = 𝑎}|
Với dữ liệu từ Bảng 1 ta có thể tính được các đặc trưng cho đối tượng 𝑃 𝑂4 như sau:
• 𝑓bas(𝑃 𝑂4)(numrelevs) = 3 (vì 𝑒21, 𝑒22, 𝑒23 đều liên quan tới 𝑃 𝑂4)
• 𝑓bas(𝑃 𝑂4)(throughputs) = 9 days (vì bắt đầu ở 𝑒21 → 𝑒23)
• 𝑓bas(𝑃 𝑂4)(wip) = 4 bởi vì các đối tượng 𝑃 𝑅4, 𝐺𝐼1 và 𝑅6 có giao nhau
về thời gian với vòng đời của𝑃 𝑂4, và bản thân 𝑃 𝑂4 cũng vậy
• 𝑓bas(𝑃 𝑂4)(#CreatePurchaseOrder) = 1 (bởi vì chỉ có một lần hoạt
động Tạo Đơn Mua Hàng cho đối tượng.
3.2.2. Graph Based Feature Map
Gọi 𝐿 là một bộ OCEL, và 𝐺 = (𝑂, Λ) là một đồ thị hướng đối tượng, ∑ =
{outdegree} ∪ {outdegreeot @𝑜𝑡 | 𝑜𝑡 ∈ 𝑂𝑇 } với @ là phép nối chuỗi,
các đặc trưng 𝑓graph : 𝑂 → ℝ được xác định như sau
• với 𝑜 ∈ 𝑂, 𝑓graph(𝑜)(outdegree) = |{(𝑜1, 𝑜2) ∈ Λ | 𝑜1 = 𝑜}|
• với 𝑜 ∈ 𝑂 và 𝑜𝑡 ∈ 𝑂𝑇 , 𝑓graph(𝑜)(outdegreeot@ot) = |{(𝑜1, 𝑜2) ∈
Λ | 𝑜1 = 𝑜 ∧ 𝜋otyp(𝑜2) = 𝑜𝑡}|
Với dữ liệu từ Bảng 1 ta có thể tính được các đặc trưng cho đối tượng 𝑃 𝑂4 như sau: 18
• 𝑓graph(PO4)(outdegree) = 3 vì các đối tượng 𝑃 𝑅4, 𝐺𝐼1, 𝑅6 được kết
nối tới 𝑃 𝑂4 trong Object Interation Graph.
• 𝑓graph(PO4)(outdegreeotPurch.Req.) = 1 vì đối tượng 𝑃 𝑅4 được kết nối tới 𝑃 𝑂4
• 𝑓graph(PO4)(outdegreeotInvoice) = 1 vì đối tượng 𝑅6 được kết nối tới 𝑃 𝑂4
• 𝑓graph(PO4)(outdegreeotGoodsIssues) = 1 vì đối tượng 𝐺𝐼1 được kết nối tới 𝑃 𝑂4
3.3. Lan truyền đặc trưng
Gọi 𝐿 là một bộ dữ liệu OCEL, 𝐺 = (𝑂, Λ) là một đồ thị hướng đối
tượng, và 𝑓 : 𝑂 → (∑ → ℝ) là một ma trận đặc trưng. Một hàm tổng hợp
agg: 𝒫(ℝ) → ℝ, ta định nghĩa 𝑓agg, G(𝑜)(𝜎) = agg({𝑓(𝑜′)(𝜔)| 𝑜 = 𝑜′ ∧ (𝑜, 𝑜′) ∈ Λ})
Một ví dụ ứng dụng như sau: Nhìn vào Bảng 1, nếu chúng ta chọn Object
Interation Graph (Hình 1) và tập trung vào Payment 𝑅6, chúng ta có thể
thấy đối tượng hóa đơn này được kết nối với đơn đặt hàng 𝑃 𝑂4. Chúng ta
cũng thấy rằng 𝑃 𝑂4 được kết nối với đối tượng phiếu xuất kho 𝐺𝐼1. Sự
hiện diện của một đối tượng phiếu xuất kho kết nối với 𝑃 𝑂4 có thể làm
chậm đáng kể việc thanh toán hóa đơn 𝑅6. Do đó, số lượng phiếu xuất kho
được kết nối với một đơn đặt hàng là một đặc trưng quan trọng đối với cả
hóa đơn, và việc lan truyền đặc trưng có hiệu quả tốt trong bối cảnh này.
Lan truyền đặc trưng cho phép một đối tượng “học hỏi” từ các đối tượng
lân cận của nó trong đồ thị. Thay vì chỉ sử dụng các đặc trưng riêng của
một đối tượng, nó còn kết hợp thông tin từ các đối tượng có liên quan. Điều
này đặc biệt hữu ích khi bản thân một đối tượng có ít thông tin hoặc thông
tin bị nhiễu, nhưng các đối tượng xung quanh nó lại chứa đựng những tín hiệu quan trọng.
Đôi khi, các mối quan hệ quan trọng giữa các đối tượng không được thể
hiện rõ ràng trong các đặc trưng ban đầu. Quá trình lan truyền có thể giúp
làm nổi bật những mối quan hệ này bằng cách tổng hợp thông tin theo cấu trúc của đồ thị.
Bằng cách tổng hợp thông tin từ các đối tượng liên quan, quá trình lan
truyền đặc trưng có thể tạo ra các đặc trưng mới, mang tính biểu diễn cao
hơn. Các đặc trưng này có thể nắm bắt được các mối tương tác và phụ thuộc
phức tạp giữa các đối tượng mà các đặc trưng riêng lẻ không thể hiện được.
Việc sử dụng các đặc trưng được lan truyền thường dẫn đến việc cải thiện
hiệu suất của các mô hình học máy, đặc biệt trong các tác vụ như phân loại, 19
dự đoán hoặc phát hiện bất thường trên dữ liệu có cấu trúc đồ thị. Mô hình
có thể đưa ra các quyết định chính xác hơn nhờ vào việc xem xét ngữ cảnh
và mối quan hệ giữa các đối tượng. 4. THỰC NGHIỆM
Để tiến hành nghiên cứu và đánh giá hiệu quả của các phương pháp phát
hiện bất thường trong quy trình P2P, em đã xây dựng một bộ dữ liệu P2P
tự tổng hợp. Bộ dữ liệu này bao gồm 1000 dòng dữ liệu, mô phỏng các hoạt
động mua sắm và thanh toán tương tự như được trình bày trong Bảng 1.
Trước khi tiến hành các thử nghiệm phát hiện bất thường, bộ dữ liệu này
đã trải qua quá trình xử lý và tiền xử lý kỹ lưỡng. Từ dữ liệu thô, em đã
xây dựng các ma trận đặc trưng dựa trên các loại đồ thị mạng P2P đã được
đề cập trước đó trong nghiên cứu. Tiếp theo, em đã áp dụng kỹ thuật lan
truyền đặc trưng (feature propagation) trên các đồ thị này để làm phong
phú thêm thông tin đặc trưng cho từng giao dịch, nhằm nâng cao khả năng
phát hiện các mẫu bất thường tiềm ẩn. Các ma trận đặc trưng đã được xây
dựng này sẽ được sử dụng làm đầu vào cho các thuật toán phát hiện bất
thường trong các bài toán cụ thể được trình bày dưới đây.
4.1. Phát hiện bất thường các thay đổi xảy ra sau yêu cầu mua hàng
Trong quy trình Procure-to-Pay - P2P, đặc biệt đối với các đơn đặt hàng
có giá trị lớn, việc tuân thủ nghiêm ngặt quy trình phê duyệt và đảm bảo
sự nhất quán thông tin giữa yêu cầu mua hàng (Purchase Requisition - PR)
và đơn đặt hàng (Purchase Order - PO) là yếu tố then chốt để ngăn ngừa
các sai sót tiềm ẩn, gian lận và đảm bảo tính minh bạch của giao dịch. Tuy
nhiên, một vấn đề bất thường đã được ghi nhận, đó là sự xuất hiện của các
trường hợp yêu cầu mua hàng bị sửa đổi sau thời điểm đơn đặt hàng tương
ứng đã được tạo lập.
Để định lượng mức độ phổ biến của vấn đề này, em đã tiến hành phân
tích nhật ký giao dịch P2P. Sử dụng các đặc trưng tính toán khi đã xây dựng
được Object Continuation Graph. Kết quả thực nghiệm cho thấy có tới 19%
tổng số yêu cầu mua hàng đã trải qua các thay đổi sau khi đơn đặt hàng liên
quan đã được hệ thống ghi nhận. Tỷ lệ này chỉ ra một lỗ hổng đáng lo ngại
trong quy trình, cho thấy khả năng thông tin ban đầu trong yêu cầu mua
hàng không còn khớp với thông tin trong đơn đặt hàng đã được phê duyệt. 20