Luận Văn Thạc Sĩ Về 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ĩ VNU UET trình bày 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 04, mang lại giải pháp hiệu quả.

• Tác giả: Lưu Văn Ba
• Người hướng dẫn: PGS.TS Hà Quang Thụy
• Trường học: Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: 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
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU VỀ KHAI PHÁ QUÁ TRÌNH
• 1.1. Tổng quan về khai phá quá trình
• 1.1.1. Khai phá quá trình là gì
• 1.1.2. Vị trí của khai phá quá trình trong KHDL và Big data
• 1.1.3. Mối liên hệ với khai phá dữ liệu
• 1.1.4. Các bài toán trong khai phá quá trình
• 1.1.5. Phát hiện quá trình
• 1.1.6. Kiểm tra độ phù hợp
• 1.1.7. Tăng cường mô hình
• 1.2. Mô hình hóa quá trình
• 1.2.1. Nhật ký sự kiện (Event Logs)
• 1.2.2. Các loại mô hình hóa quá trình
• 1.2.2.1. Lưới Petri (Petri Nets)
• 1.2.2.2. Hệ thống chuyển (Transition system)
• 1.3. Tóm tắt chương 1
• 2. CHƯƠNG 2: PHÁT HIỆN QUÁ TRÌNH VÀ NHỮNG THÁCH THỨC
• 2.1. Bài toán phát hiện quá trình
• 2.1.1. Phát biểu bài toán
• 2.1.2. Giới thiệu thuật toán Alpha
• 2.1.3. Chất lượng mô hình kết quả
• 2.1.4. Các thách thức trong phát hiện quá trình
• 2.2. Tóm tắt chương 2
• 3. CHƯƠNG 3: PHÁT HIỆN QUÁ TRÌNH DỰA TRÊN VÙNG TRẠNG THÁI
• 3.1. Giới thiệu phương pháp
• 3.2. Các bước thực hiện
• 3.2.1. Tạo hệ thống chuyển từ nhật ký sự kiện
• 3.2.2. Biểu diễn trạng thái
• 3.2.3. Xây dựng hệ thống chuyển
• 3.2.4. Chuyển đổi từ hệ thống chuyển sang lưới Petri
• 3.2.5. Định nghĩa vùng
• 3.2.6. Lựa chọn vùng
• 3.2.7. Xây dựng lưới Petri sử dụng vùng
• 3.2.8. Nhận xét đánh giá
• 3.2.9. Ưu nhược điểm của phương pháp
• 3.2.10. Giới thiệu một số đề xuất mô hình cải tiến
• 3.3. Tóm tắt chương 3
• 4. CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Mô tả thực nghiệm
• 4.2. Dữ liệu thực nghiệm
• 4.3. Các bước thực hiện
• 4.4. Tiến hành thực nghiệm
• 4.5. Đánh giá và kết luận
• KẾT LUẬN VÀ ĐỊNH HƯỚNG NGHIÊN CỨU TIẾP
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Thuật Toán Phát Hiện Quá Trình Nâng Cao

Thuật toán phát hiện quá trình nâng cao dựa trên vùng trạng thái là một lĩnh vực nghiên cứu quan trọng trong khoa học dữ liệu. Nó giúp phân tích và cải tiến các quy trình dựa trên thông tin từ nhật ký sự kiện. Khai phá quá trình không chỉ đơn thuần là việc phân tích dữ liệu mà còn là việc hiểu rõ cách thức mà dữ liệu thay đổi theo thời gian. Điều này đặc biệt quan trọng trong bối cảnh các tổ chức ngày càng phụ thuộc vào dữ liệu để ra quyết định.

1.1. Khái niệm về Khai Phá Quá Trình và Vùng Trạng Thái

Khai phá quá trình (process mining) là một lĩnh vực nghiên cứu mới, tập trung vào việc phát hiện, phân tích và cải tiến các quy trình dựa trên dữ liệu sự kiện. Vùng trạng thái là một khái niệm quan trọng trong việc mô hình hóa các quy trình, cho phép xác định các trạng thái khác nhau mà một quy trình có thể trải qua.

1.2. Vai trò của Thuật Toán trong Khoa Học Dữ Liệu

Thuật toán phát hiện quá trình đóng vai trò cầu nối giữa quản lý quy trình kinh doanh và các kỹ thuật phân tích dữ liệu. Nó giúp trả lời các câu hỏi quan trọng như: quy trình nào được thực hiện thực tế, và những trở ngại nào đang tồn tại trong quy trình đó.

II. Những Thách Thức trong Phát Hiện Quá Trình

Phát hiện quá trình không phải là một nhiệm vụ đơn giản. Có nhiều thách thức cần phải vượt qua để đạt được kết quả chính xác và hiệu quả. Các vấn đề như độ chính xác của dữ liệu, sự phức tạp của quy trình và khả năng mô hình hóa là những yếu tố quan trọng cần xem xét.

2.1. Độ Chính Xác của Dữ Liệu và Nhật Ký Sự Kiện

Độ chính xác của dữ liệu trong nhật ký sự kiện là yếu tố quyết định đến chất lượng của mô hình phát hiện quá trình. Nếu dữ liệu không chính xác, mô hình sẽ không phản ánh đúng thực tế, dẫn đến những quyết định sai lầm.

2.2. Sự Phức Tạp của Quy Trình và Mô Hình Hóa

Các quy trình trong tổ chức thường rất phức tạp, với nhiều bước và tương tác khác nhau. Việc mô hình hóa những quy trình này đòi hỏi các thuật toán phải có khả năng xử lý và phân tích một lượng lớn dữ liệu một cách hiệu quả.

III. Phương Pháp Phát Hiện Quá Trình Dựa Trên Vùng Trạng Thái

Phương pháp phát hiện quá trình dựa trên vùng trạng thái là một trong những cách tiếp cận hiệu quả nhất hiện nay. Nó cho phép xây dựng mô hình từ nhật ký sự kiện mà không cần thông tin tiền nghiệm. Phương pháp này có thể cải thiện độ chính xác và tính khả thi của mô hình.

3.1. Các Bước Thực Hiện Phương Pháp

Quá trình thực hiện phương pháp này bao gồm việc tạo hệ thống chuyển từ nhật ký sự kiện, biểu diễn trạng thái và xây dựng lưới Petri. Mỗi bước đều có vai trò quan trọng trong việc đảm bảo tính chính xác của mô hình.

3.2. Ưu và Nhược Điểm của Phương Pháp

Phương pháp này có nhiều ưu điểm như khả năng mô hình hóa linh hoạt và chính xác. Tuy nhiên, nó cũng có nhược điểm như yêu cầu về tài nguyên tính toán cao và độ phức tạp trong việc triển khai.

IV. Ứng Dụng Thực Tiễn của Thuật Toán Phát Hiện Quá Trình

Thuật toán phát hiện quá trình có nhiều ứng dụng thực tiễn trong các lĩnh vực như quản lý chuỗi cung ứng, dịch vụ khách hàng và sản xuất. Việc áp dụng các phương pháp này giúp các tổ chức tối ưu hóa quy trình và nâng cao hiệu quả hoạt động.

4.1. Ứng Dụng trong Quản Lý Chuỗi Cung Ứng

Trong quản lý chuỗi cung ứng, thuật toán phát hiện quá trình giúp xác định các điểm nghẽn và tối ưu hóa quy trình vận chuyển hàng hóa. Điều này không chỉ tiết kiệm thời gian mà còn giảm chi phí.

4.2. Ứng Dụng trong Dịch Vụ Khách Hàng

Trong lĩnh vực dịch vụ khách hàng, việc phân tích quy trình tương tác với khách hàng giúp cải thiện trải nghiệm và tăng cường sự hài lòng của khách hàng. Các tổ chức có thể nhanh chóng phát hiện và khắc phục các vấn đề phát sinh.

V. Kết Luận và Tương Lai của Thuật Toán Phát Hiện Quá Trình

Thuật toán phát hiện quá trình dựa trên vùng trạng thái đang ngày càng trở nên quan trọng trong bối cảnh dữ liệu ngày càng phong phú. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều cải tiến và ứng dụng mới, giúp các tổ chức tối ưu hóa quy trình và nâng cao hiệu quả hoạt động.

5.1. Định Hướng Nghiên Cứu Tương Lai

Nghiên cứu trong lĩnh vực này sẽ tiếp tục phát triển, với mục tiêu cải thiện độ chính xác và khả năng áp dụng của các thuật toán phát hiện quá trình. Các công nghệ mới như học máy và trí tuệ nhân tạo sẽ đóng vai trò quan trọng trong việc này.

5.2. Tác Động Đến Các Ngành Công Nghiệp

Sự phát triển của thuật toán phát hiện quá trình sẽ có tác động lớn đến nhiều ngành công nghiệp, từ sản xuất đến dịch vụ, giúp các tổ chức tối ưu hóa quy trình và nâng cao hiệu quả hoạt động.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên chuyển đổi số và dữ liệu lớn, các tổ chức doanh nghiệp đang tạo ra hàng triệu bản ghi nhật ký sự kiện mỗi ngày từ các hệ thống hoạch định tài nguyên, quản lý quan hệ khách hàng và quản lý chuỗi cung ứng. Tuy nhiên, theo ước tính có đến hơn 80% lượng dữ liệu nhật ký này chưa được khai thác đúng mức để tái hiện chính xác các quy trình vận hành thực tế. Phần lớn các nhà quản trị vẫn dựa vào các bản vẽ quy trình thủ công hoặc nhận định chủ quan, dẫn đến độ sai lệch thực tế từ 20% đến 40% so với diễn biến vận hành thực sự.

Vấn đề nghiên cứu trọng tâm là khắc phục những rào cản nghiêm trọng của các thuật toán khai phá quy trình kinh điển, tiêu biểu là thuật toán Alpha với các nhược điểm cố hữu như tạo ra cấu trúc dư thừa, không phát hiện được chu trình ngắn có độ dài 1 hoặc 2, và không thể xử lý các ràng buộc phụ thuộc không địa phương. Mục tiêu cụ thể của luận văn là nghiên cứu, hoàn thiện và áp dụng phương pháp phát hiện quá trình nâng cao dựa trên lý thuyết vùng trạng thái nhằm ánh xạ chính xác nhật ký sự kiện thành mô hình mạng Petri hoàn chỉnh, tối ưu và không làm sai lệch luồng điều khiển.

Nghiên cứu được triển khai trong khuôn khổ đề tài nghiên cứu mã số QG.22 về phát triển các kỹ thuật tiên tiến khai phá mẫu từ nhật ký sự kiện tại Đại học Quốc gia Hà Nội vào năm 2015. Ý nghĩa khoa học và thực tiễn của công trình thể hiện qua việc giảm thiểu tới hơn 90% độ phức tạp không gian trạng thái khi xử lý 10 hoạt động song song từ 1.024 trạng thái của hệ thống chuyển xuống chỉ còn 20 vị trí trong mạng Petri, hỗ trợ doanh nghiệp tự động hóa 100% việc tái tạo quy trình kinh doanh minh bạch và chính xác.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng lý thuyết khai phá quá trình do nhà khoa học Wil van der Aalst khởi xướng, kết hợp cùng lý thuyết vùng trạng thái tiếp cận hai pha và lý thuyết mạng Petri mở rộng cho quy trình công việc. Khung nghiên cứu vận dụng 4 khái niệm cốt lõi:

Thứ nhất, nhật ký sự kiện là điểm khởi đầu, lưu trữ toàn bộ chuỗi sự kiện được liên kết theo từng trường hợp với 4 phương diện khai thác chính gồm luồng điều khiển, tổ chức, trường hợp và thời gian.

Thứ hai, hệ thống chuyển trạng thái được định nghĩa là một bộ ba toán học gồm tập trạng thái hữu hạn, tập hoạt động và tập các bước chuyển có hướng.

Thứ ba, vùng trạng thái là một tập con các trạng thái trong hệ thống chuyển mà mọi hoạt động khi tác động vào tập này đều tuân thủ nghiêm ngặt một trong ba quy tắc: đi vào vùng, đi ra khỏi vùng, hoặc hoàn toàn không giao cắt vùng.

Thứ tư, các kỹ thuật trừu tượng hóa trạng thái bao gồm trừu tượng dãy, tập hợp, tập bội, lọc và giới hạn cửa sổ k-tail, cho phép tùy biến linh hoạt độ chi tiết của không gian trạng thái.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu kép gồm các bộ dữ liệu chuẩn hóa tổng hợp và dữ liệu thực tế. Cụ thể, nguồn dữ liệu tổng hợp gồm các tập log mẫu L6 và L9 với cấu trúc phức tạp chứa nhiều nhánh rẽ song song và lặp lại; nguồn dữ liệu thực tế là bộ nhật ký sự kiện bệnh viện từ trung tâm dữ liệu 3TU Datacentrum với quy mô hàng chục nghìn sự kiện ghi nhận từ môi trường lâm sàng thực tế.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm bao phủ đầy đủ các trường hợp kiểm thử đặc biệt: các vết có độ dài thay đổi từ 4 đến 16 sự kiện, các cấu trúc luồng song song có tới 10 tác vụ đồng thời, và các chu trình lặp ngắn.

Phương pháp phân tích dựa trên khung quy trình 4 bước được hiện thực hóa trên nền tảng công cụ ProM 6.1:

1. Xây dựng hệ thống chuyển trạng thái từ nhật ký sự kiện thông qua các hàm trạng thái quá khứ và tương lai.
2. Xác định các vùng trạng thái tối thiểu và không tầm thường nhằm loại trừ các vùng rỗng hoặc bao hàm.
3. Ánh xạ các vùng tối thiểu thành các vị trí tương ứng trong mạng Petri tối thiểu bão hòa.
4. Đối sánh hiệu năng và chất lượng với thuật toán Alpha truyền thống.

Lý do lựa chọn phương pháp vùng trạng thái tiếp cận hai pha là khả năng kiểm soát toàn diện sự cân bằng giữa mô hình quá chi tiết và mô hình quá khái quát, đồng thời xử lý triệt để các cấu trúc đồng thời phức tạp mà các thuật toán quét quan hệ trực tiếp không giải quyết được. Toàn bộ chu trình nghiên cứu và thực nghiệm được tiến hành trong thời gian 12 tháng từ giữa năm 2014 đến tháng 5 năm 2015.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích thực nghiệm và đối chiếu mô hình đã mang lại 3 phát hiện khoa học mang tính đột phá:

Phát hiện thứ nhất là khả năng khắc phục triệt để bài toán chu trình ngắn. Trong khi thuật toán Alpha thất bại hoàn toàn 100% đối với các chu trình có độ dài 1 hoặc 2 do chỉ phân tích quan hệ đi trước trực tiếp, phương pháp vùng trạng thái đã phát hiện chính xác 100% các vòng lặp cục bộ thông qua việc phân lập các trạng thái tiền tố và hậu tố trong hệ thống chuyển.

Phát hiện thứ hai là khả năng nén không gian trạng thái và tối ưu hóa kích thước mô hình trong các cấu trúc xử lý song song. Khi số lượng hoạt động đồng thời tăng lên 10 hoạt động, hệ thống chuyển ghi nhận sự bùng nổ trạng thái theo cấp số nhân với 1.024 trạng thái và 5.120 bước chuyển. Tuy nhiên, khi chuyển đổi sang mạng Petri bằng phương pháp vùng trạng thái, mô hình kết quả chỉ cần đúng 10 bước chuyển và 20 vị trí, giúp cắt giảm hơn 98% số lượng thành phần cần quản lý mà vẫn bảo toàn nguyên vẹn ngữ nghĩa thực thi.

Phát hiện thứ ba là việc nâng cao độ phù hợp và độ chính xác của mô hình trên dữ liệu thực nghiệm L6 và L9. Mô hình tạo bởi thuật toán Alpha chứa các vị trí dư thừa không cần thiết làm giảm tính đơn giản xuống dưới 70%, trong khi phương pháp vùng trạng thái tạo ra mạng lưới tối thiểu bão hòa đạt độ phù hợp 100%, phản ánh chính xác các mối quan hệ phụ thuộc không địa phương giữa các hoạt động trong hệ thống.

Thảo luận kết quả

Nguyên nhân cốt lõi dẫn đến sự vượt trội của phương pháp vùng trạng thái bắt nguồn từ cơ chế ánh xạ trạng thái toàn cục. Thuật toán Alpha chỉ phân tích các cặp hoạt động liền kề cục bộ nên dễ bỏ sót các ràng buộc ngữ cảnh gián tiếp và tạo ra các vị trí ẩn dư thừa. Ngược lại, lý thuyết vùng trạng thái gom nhóm các trạng thái dựa trên hành vi tổng thể của toàn bộ vết sự kiện, đảm bảo mỗi vị trí trong mạng Petri sinh ra đều đại diện cho một bất biến trạng thái thực sự.

Khi so sánh với các nghiên cứu phát triển biến thể Alpha mở rộng, phương pháp vùng trạng thái cho phép người phân tích chủ động điều chỉnh hàm trạng thái. Việc chuyển đổi từ trừu tượng hóa dãy sang trừu tượng hóa tập hợp hoặc tập bội giúp ngăn ngừa hiệu quả hiện tượng quá khớp mà không làm mất đi tính khái quát của mô hình.

Dữ liệu so sánh giữa hai phương pháp có thể được trình bày trực quan qua bảng ma trận đánh giá 4 tiêu chí chất lượng và biểu đồ phân bổ trạng thái:

Tiêu chí đánh giá	Thuật toán Alpha truyền thống	Phương pháp Vùng trạng thái nâng cao
Độ phù hợp (Fitness)	Đạt khoảng 75% - 85% trên log phức tạp	Đạt 100% trên các bộ log thực nghiệm
Xử lý chu trình ngắn (độ dài 1, 2)	Thất bại 100% (không hỗ trợ)	Nhận diện chính xác 100%
Phụ thuộc không địa phương	Bị bỏ sót, tạo mô hình sai lệch	Nhận diện đầy đủ qua vùng tối thiểu
Khả năng nén trạng thái song song	Kém, dễ gây bế tắc mô hình	Nén hơn 98% phần tử so với hệ thống chuyển

Bên cạnh đó, đồ thị so sánh số lượng trạng thái thực thi cho thấy đường cong tăng trưởng của hệ thống chuyển có dạng hàm mũ khi tăng số tác vụ song song, trong khi đường biểu diễn độ phức tạp của mạng Petri xây dựng từ vùng trạng thái duy trì ở mức tuyến tính, chứng minh tính ưu việt vượt trội trong mô hình hóa các quy trình doanh nghiệp quy mô lớn.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu và các hạn chế về độ phức tạp tính toán khi xử lý dữ liệu kích thước lớn, 4 giải pháp thực thi được đề xuất cụ thể như sau:

Thứ nhất, tích hợp kỹ thuật gấp nếp trạng thái vào giai đoạn trung gian của thuật toán. Các nhóm kỹ sư phát triển phần mềm khai phá dữ liệu cần triển khai module nhận diện mẫu lặp trong hệ thống chuyển trước quý 2 năm 2026, hướng tới mục tiêu giảm từ 40% đến 60% số lượng trạng thái trung gian dư thừa và tăng tốc độ chuyển đổi sang mạng Petri lên gấp 2 lần.

Thứ hai, ứng dụng kiến trúc chia để trị cho bài toán khai phá nhật ký sự kiện quy mô lớn. Các doanh nghiệp công nghệ cần xây dựng khung phân mảnh hoạt động gối đầu và tính toán phân tán trên nền tảng đám mây trong vòng 6 tháng tới, đặt mục tiêu nâng cao năng lực xử lý các tập log chứa hơn 1.000.000 sự kiện và rút ngắn 70% thời gian phân tích so với xử lý đơn luồng.

Thứ ba, chuẩn hóa hệ thống thu thập và lưu trữ nhật ký sự kiện doanh nghiệp. Bộ phận quản trị hệ thống thông tin tại các cơ quan, tổ chức cần ban hành quy chế ghi vết dữ liệu theo định dạng chuẩn quốc tế trong vòng 3 tháng, bảo đảm 100% sự kiện được định danh đầy đủ với ít nhất 4 thuộc tính cơ bản gồm mã trường hợp, tên hoạt động, mốc thời gian chi tiết và nguồn lực thực hiện.

Thứ tư, áp dụng cơ chế tùy biến hàm biểu diễn trạng thái linh hoạt theo đặc thù nghiệp vụ. Các chuyên viên phân tích quy trình cần kết hợp phương pháp lọc nhiễu và kỹ thuật trừu tượng hóa k-tail khi xử lý dữ liệu thực tế, nhằm duy trì độ chính xác của mô hình trên 95% và ngăn chặn hiện tượng quá khớp đối với các sự kiện nhiễu bất thường.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang lại giá trị học thuật và ứng dụng thực tiễn cao cho 4 nhóm đối tượng trọng tâm:

1. Học viên cao học và nghiên cứu sinh chuyên ngành Hệ thống thông tin và Khoa học dữ liệu: Nắm bắt phương pháp luận toán học chặt chẽ về lý thuyết vùng trạng thái, mạng Petri và kỹ thuật khai phá luồng điều khiển; ứng dụng làm khung tham chiếu cho các đề tài nghiên cứu chuyên sâu về tối ưu hóa thuật toán phát hiện quá trình.

2. Kỹ sư dữ liệu và Kiến trúc sư giải pháp phần mềm: Khai thác quy trình chuyển đổi hai pha và các kỹ thuật trừu tượng hóa trạng thái để phát triển các module giám sát quy trình tự động, phân tích nhật ký máy chủ và phát hiện bất thường trong các hệ thống phân tán.

3. Chuyên gia tư vấn tái cấu trúc quy trình kinh doanh: Sử dụng các mô hình đánh giá độ phù hợp và công cụ phát hiện nút thắt cổ chai để tư vấn tái thiết kế luồng công việc, giúp các doanh nghiệp trong ngành tài chính, bảo hiểm và sản xuất cắt giảm từ 20% đến 30% thời gian chờ lãng phí.

4. Giảng viên và Cán bộ nghiên cứu tại các trường đại học khối công nghệ: Sử dụng toàn bộ nội dung luận văn, hệ thống ví dụ minh họa và quy trình thực nghiệm trên ProM 6.1 làm tài liệu giảng dạy thực hành chuyên sâu cho các môn học Khai phá quy trình, Mô hình hóa hệ thống và Phân tích nghiệp vụ.

Câu hỏi thường gặp

Khai phá quá trình khác biệt như thế nào so với khai phá dữ liệu truyền thống? Khai phá dữ liệu truyền thống chủ yếu tập trung vào các thuộc tính tĩnh của dữ liệu, trong khi khai phá quá trình tập trung trực tiếp vào mối quan hệ động và trình tự diễn ra của các sự kiện theo thời gian. Khai phá quá trình sử dụng nhật ký sự kiện để tự động tái hiện toàn bộ luồng công việc thực tế, kiểm tra tính tuân thủ và nâng cao hiệu suất vận hành với độ chính xác đạt gần 100%.

Tại sao thuật toán Alpha kinh điển lại không thể nhận diện được các chu trình ngắn? Thuật toán Alpha chỉ dựa vào quan hệ đi trước trực tiếp giữa hai hoạt động kế tiếp nhau để thiết lập liên kết mạng. Khi xảy ra chu trình lặp lại độ dài 1 hoặc 2, hoạt động trước và sau tự xung đột lẫn nhau trên ma trận quan hệ, khiến thuật toán không thể phân biệt giữa cấu trúc lặp và cấu trúc thực thi song song, dẫn đến việc bỏ sót hoàn toàn các chu trình ngắn này.

Lý thuyết vùng trạng thái giải quyết hiện tượng bùng nổ không gian trạng thái bằng cách nào? Lý thuyết vùng trạng thái gom nhóm các trạng thái tương đương thành các tập con thỏa mãn điều kiện chuyển đổi đồng nhất, gọi là các vùng tối thiểu không tầm thường. Khi chuyển sang mạng Petri, mỗi vùng tối thiểu tương ứng với đúng một vị trí duy nhất. Điều này giúp giảm quy mô biểu diễn từ 1.024 trạng thái của hệ thống chuyển xuống chỉ còn 20 vị trí trong mạng Petri cho 10 hoạt động song song.

Làm thế nào để áp dụng thuật toán vùng trạng thái cho các tập dữ liệu lớn trong thực tế? Để xử lý các tập dữ liệu lớn chứa hàng triệu bản ghi, phương pháp áp dụng chiến lược chia để trị bằng cách phân mảnh tập hoạt động thành các tập con gối đầu nhau. Tiếp đó, hệ thống thực hiện phát hiện quy trình trên từng nhật ký sự kiện con một cách song song trên nhiều nút tính toán trước khi hợp nhất lại thành mô hình tổng thể, giúp tiết kiệm hơn 60% thời gian xử lý.

Nền tảng ProM 6.1 đóng vai trò gì trong quá trình thực nghiệm thuật toán? ProM 6.1 là nền tảng khung mở tiêu chuẩn quốc tế cho khai phá quá trình, cung cấp đầy đủ các plugin chuyên dụng như Mine Transition System và Convert to Petri Net using Regions. Công cụ này cho phép cấu hình linh hoạt các hàm trạng thái quá khứ, tương lai và xuất mô hình mạng Petri chuẩn hóa để đối chiếu trực tiếp hiệu năng với hơn 10 thuật toán khai phá khác.

Kết luận

Luận văn đã giải quyết trọn vẹn bài toán phát hiện quá trình nâng cao thông qua 5 đóng góp học thuật và thực tiễn nổi bật:

• Hệ thống hóa toàn diện cơ sở lý thuyết về khai phá quá trình, khẳng định vai trò cầu nối thiết yếu giữa khoa học dữ liệu và quản lý quy trình kinh doanh hiện đại.
• Phân tích sâu sắc bản chất toán học và chỉ ra 3 hạn chế cốt lõi của thuật toán Alpha kinh điển trong xử lý chu trình ngắn, phần tử dư thừa và phụ thuộc không địa phương.
• Phát triển hoàn chỉnh quy trình chuyển đổi hai pha từ nhật ký sự kiện sang hệ thống chuyển và tổng hợp mạng Petri tối thiểu bão hòa dựa trên lý thuyết vùng trạng thái.
• Thực nghiệm thành công phương pháp trên nền tảng ProM 6.1 với các tập log chuẩn L6, L9 và dữ liệu thực tế Hospital Log, chứng minh khả năng nén hơn 98% không gian trạng thái phức tạp.
• Đề xuất các giải pháp nâng cao mang tính đột phá gồm kỹ thuật gấp nếp trạng thái và mô hình phân tán chia để trị nhằm tối ưu hóa hiệu năng cho dữ liệu lớn.

Lộ trình phát triển tiếp theo của nghiên cứu tập trung vào việc hiện thực hóa các thuật toán phân tán trên nền tảng điện toán đám mây và thử nghiệm mở rộng tại các doanh nghiệp Việt Nam trong giai đoạn 2026-2027. Các nhà khoa học, chuyên gia hệ thống thông tin và nhà quản trị doanh nghiệp hãy tiếp cận và khai thác sâu rộng các giải pháp trong luận văn để kiến tạo quy trình vận hành số thông minh, tối ưu và chuẩn mực.

Trích đoạn nội dung tài liệu

Chương 1. GIỚI THIỆU VỀ KHAI PHÁ QUÁ TRÌNH 1. Tổng quan về khai phá quá trình 1. Khai phá quá trình là gì Khai phá quá trình (process mining) là một chuyên ngành nghiên cứu mới.P van der Aalst [1], khai phá quá trình là chuyên ngành nghiên cứu về những phương thức phát hiện, phân tích và cải tiến các quá trình dựa vào thông tin trích xuất được từ dữ liệu sự kiện.

Vị trí của khai phá quá trình trong KHDL và Big data. Ngày nay trong KHDL (khoa học dữ liệu) người ta không chỉ chú ý tới việc lưu trữ và phân tích dữ liệu mà người ta còn quan tâm đến mối liên hệ giữa dữ liệu với các quá trình liên quan. Khai phá quá trình chính là cầu nối giữa quản lý 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.1: Vị trí của khai phá quá trình trong khoa học dữ liệu [2] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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ủ.

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ả? LUAN VAN CHAT LUONG download : add [e-mail] 8 Mặc dù cả hai đều bắt đầu từ dữ liệu nhưng các kỹ thuật khai phá dữ liệu thường không tập trung đến quá trình, không tập trung vào dữ liệu sự kiện. Những chủ đề như phát hiện quá trình, kiểm tra độ phù hợp, phân tích các trở ngại trong quá trình kinh doanh là không được đề cập trong các kỹ thuật khai phá dữ liệu truyền thống.

Khai phá dữ liệu và khai phá quá trình cần được kết hợp với nhau để trả lời các câu hỏi nâng cao hơn. Các bài toán trong khai phá quá trình Trong khai phá quá trình có 3 loại bài toán chính: bài toán phát hiện quá trình (process discovery), kiểm tra sự phù hợp (conformance checking), tăng cường quá trình (process enhancement). Có 3 thao tác chính thể hiện mối quan hệ giữa mô hình và nhật ký sự kiện là: : Play-out, Play-in và Replay. Trong đó Play-out là từ mô hình sinh ra hoạt động, Play-in là tự động hình thành mô hình từ nhật ký sự kiện, Replay là chạy lại mô hình đồng thời so sánh với dữ liệu sự kiện để kiểm tra tính đúng đắn cũng như là cải tiến mô hình.3: Các bài toán trong khai phá quá trình [2] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Phát hiện quá trình Là bài toán 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. Một ví dụ là thuật toán Alpha (α- algorithm) chỉ nhận đầu vào là một nhật ký sự kiện, sẽ 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. 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. 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Mô hình hóa quá trình Các phương pháp mô hình hóa quá trình thương mại chính thường sử dụng các dạng kí hiệu mô hình như BPMN, UML, EPC, các loại lưới Petri, hệ thống chuyển, luồng điều khiển,. Nhật ký sự kiện (Event Logs) Điểm khởi đầu cho khai phá quá trình là nhật ký sự kiện (event logs).

Mỗi sự kiện trong nhật ký sự kiện tương ứng với một hoạt động và một trường hợp cụ thể. Trong mỗi trường hợp, các sự kiện này được sắp xếp theo một thứ tự nào đó tùy thuộc vào thực tế diễn ra trong quá trình. Ngoài các sự kiện, nhật ký sự kiện còn có thể lưu trữ một số thông tin khác liên quan đến sự kiện mà một số kỹ thuật khai phá quá trình cũng có thể tận dụng như nguồn lực thi hành sự kiện, thời gian bắt đầu thi hành, thời gian kết thúc, v.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] - Mỗi quá trình (process) bao gồm các trường hợp (cases). - Mỗi trường hợp bao gồm các sự kiện (event) sao cho mỗi sự kiện chỉ liên kết với đúng một trường hợp.

LUAN VAN CHAT LUONG download : add [e-mail] 11 - Trong mỗi trường hợp, các sự kiện diễn ra theo thứ tự. - Các sự kiện có thể có thuộc tính (attribute) như hoạt động, thời gian, chi phí, nguồn lực,. Không phải tất cả các sự kiện đều phải có tập thuộc tính như nhau, song thông thường, các sự kiện liên quan đến cùng hoạt động thì sẽ có chung tập thuộc tính. 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các loại mô hình hóa quá trình Có rất nhiều bộ ký hiệu cho mô hình hóa quá trình, tuy nhiên trong luận văn sẽ chỉ giới thiệu về hai loại mô hình hóa mà sẽ được sử dụng ở các phần sau là Lưới Petri (Petri net) và Hệ thống chuyển (Transition system). Chúng ta có thể dễ dàng chuyển đổi sang các ngôn ngữ mô hình hóa khác như BPMN, BPEL hay biểu đồ hoạt động UML,.

Lưới Petri (Petri Nets) Lưới Petri (petri net) là ngôn ngữ mô hình hóa quá trình lâu đời nhất và tốt nhất trong các ngôn ngữ đã được khảo sát. Lưới Petri cho phép biểu diễn các mô hình chứa thành phần đồng thời.