Tài liệu Tìm hiểu một số giải thuật tìm kiếm cộng đồng trong mạng xã hội và áp dụng vào bài toán khai phá quy trình

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HỒNG HẠNH TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CỘNG ĐỒNG TRONG MẠNG XÃ HỘI VÀ ÁP DỤNG VÀO BÀI TOÁN KHAI PHÁ QUY TRÌNH LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Hà Nội - 2016 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HỒNG HẠNH TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CỘNG ĐỒNG TRONG MẠNG XÃ HỘI VÀ ÁP DỤNG VÀO BÀI TOÁN KHAI PHÁ QUY TRÌNH Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.01.04 LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Trí Thành Hà Nội - 2016 i LỜI CAM ĐOAN Tác giả xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm của riêng cá nhân Tác giả và đƣợc sự hƣớng dẫn khoa học của PGS.TS Nguyễn Trí Thành, không sao chép lại của ngƣời khác. Trong toàn bộ nội dung của luận văn, những điều trình bày của cá nhân hoặc đƣợc tổng hợp của nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp. Tác giả xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày tháng năm 2016 HỌC VIÊN Nguyễn Thị Hồng Hạnh ii LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy PGS.TS Nguyễn Trí Thành, ngƣời thầy đã trực tiếp hƣớng dẫn tận tình và đóng góp những ý kiến quý báu cho em trong suốt quá trình thực hiện luận văn tốt nghiệp này. Em xin gửi lời cảm ơn đến các thầy cô giáo Trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội, đã tận tâm truyền đạt những kiến thức quý báu làm nền tảng cho em trong công việc và cuộc sống. Qua đây, em cũng xin cảm ơn sinh viên Nguyễn Duy Kiên – Trƣờng Đại học Công nghệ Hà Nội đã hỗ trợ và giúp đỡ em về mặt kỹ thuật. Cuối cùng, em xin đƣợc cảm ơn cha mẹ, ngƣời thân, ban bè và đồng nghiệp của em tại Sở Nông nghiệp và PTNT tỉnh Hƣng Yên, những ngƣời đã luôn bên em, khuyến khích và động viên em trong cuộc sống và học tập. HỌC VIÊN Nguyễn Thị Hồng Hạnh iii MỤC LỤC DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ....................................................... v DANH MỤC CÁC BẢNG................................................................................... vi MỞ ĐẦU ............................................................................................................... 7 CHƢƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH ................................ 9 1.1 Khai phá quy trình........................................................................................ 9 1.1.1 Sự cần thiết của KPQT ........................................................................ 10 1.1.2 Mục tiêu của KPQT ............................................................................. 11 1.1.3 Mô hình quy trình và nhật ký sự kiện .................................................. 11 1.1.4 Các bài toán KPQT .............................................................................. 12 1.1.5 Các khía cạnh của KPQT ..................................................................... 13 1.1.6 Các ứng dụng của KPQT ..................................................................... 14 1.1.7 Một số thách thức đối với lĩnh vực KPQT .......................................... 14 1.2 Khía cạnh tổ chức trong KPQT.................................................................. 15 1.3 Bài toán toán khai phá khía cạnh tổ chức .................................................. 18 1.3.1 Trong thực tế ........................................................................................ 18 1.3.2 Trong luận văn ..................................................................................... 18 1.4 Ý nghĩa của luận văn .................................................................................. 20 1.4.1 Về mặt khoa học .................................................................................. 20 1.4.2 Về mặt thực tiễn ................................................................................... 21 CHƢƠNG 2. CÁC GIẢI THUẬT TÌM KIẾM CỘNG TRONG MXH ............. 22 2.1 Cộng đồng mạng xã hội ............................................................................. 22 2.1.1 Nguyên nhân hình thành cộng đồng MXH .......................................... 22 2.1.2 Các loại cộng đồng trong MXH........................................................... 23 2.1.3 Các loại cấu trúc cộng đồng ................................................................. 23 2.2 Các phƣơng pháp phát hiện cộng đồng...................................................... 24 2.2.1 Ứng dụng.............................................................................................. 24 2.2.2 Các loại giải thuật ................................................................................ 25 2.3 Các giải thuật tìm kiếm cộng đồng chồng chéo ......................................... 28 2.4 Lựa chọn giải thuật tìm kiếm ..................................................................... 30 iv CHƢƠNG 3. ÁP DỤNG GIẢI THUẬT TÌM KIẾM CỘNG ĐỒNG CHỒNG CHÉO VÀO BÀI TOÁN KPQT ......................................................................... 34 3.1. Phƣơng pháp nghiên cứu........................................................................... 34 3.1.1 Tính hiệu quả của đề xuất .................................................................... 34 3.1.2 Định dạng dữ liệu đầu vào các độ đo: ................................................. 35 3.2 Giải pháp thực hiện ................................................................................... 37 3.2.1 Đề xuất mô hình giải quyết .................................................................. 37 3.2.2 Các bƣớc thực hiện .............................................................................. 38 CHƢƠNG 4. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ ............................ 46 4.1 Công cụ, môi trƣờng thực nghiệm ............................................................. 46 4.1.1 Phần cứng ............................................................................................. 46 4.1.2 Phần mềm và tập dữ liệu đầu vào ........................................................ 46 4.2 Chƣơng trình thực nghiệm ......................................................................... 47 4.3 Kết quả thực nghiệm và đánh giá .............................................................. 48 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN TƢƠNG LAI ................................... 51 TÀI LIỆU THAM KHẢO ................................................................................... 52 v DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT STT I 1 2 3 4 5 6 II 1 2 3 4 5 6 7 8 9 10 11 Chữ viết tắt Tiếng việt CNTT HTTT KCTC KPQT MHQT MXH Tiếng anh B2B BPNN CRM EPC ERP NMI SCM UPGMA WFM XES XML Chú giải Công nghệ thông tin Hệ thống thông tin Khía cạnh tổ chức Khai phá quy trình Mô hình quy trình Mạng xã hội Busines - to - Business Back - propagation neural network Customer Relationship Management Event - driven Process Chain Systems for Enterprise Resource Planning Normalized mutual information Supply Chain Management Unweighter Pair - Group Method using Arithmetic averages Workflow Management eXtensible Event Stream EXtensible Markup Language vi DANH MỤC CÁC BẢNG Bảng 2.1 So sánh các loại cấu trúc cộng đồng .................................................... 24 Bảng 2.2 Các phƣơng pháp tính khoảng cách hai cụm ....................................... 26 Bảng 3.1 Bảng mô tả các thuộc tính của một phần dữ liệu sự kiện .................... 36 Bảng 3.2 Thứ tự thực hiện nhiệm vụ của từng ngƣời trong mỗi trƣờng hợp ..... 40 Bảng 3.3 Ma trận 𝑀𝑕 mối quan hệ ..................................................................... 40 Bảng 3.4 Ma trận đỉnh kề 𝑀𝑎 ............................................................................. 41 Bảng 3.5 Danh sách đỉnh kề ................................................................................ 42 Bảng 3.6 Ma trận 𝑀𝑠 độ tƣơng tự ....................................................................... 43 Bảng 3.7 Tính mật độ các phân vùng tại ngƣỡng cắt t=1 ................................... 43 Bảng 3.8 Tính mật độ các phân vùng tại ngƣỡng cắt t=0.7(KN1)...................... 44 Bảng 3.9 Tính mật độ các phân vùng tại ngƣỡng cắt t=0.7(KN2)...................... 44 Bảng 3.10 Danh sách các cộng đồng đƣợc tìm thấy ........................................... 45 Bảng 4.1 Chi tiết chỉ số phần cứng và hệ điều hành ........................................... 46 Bảng 4.2 Thông tin phần mềm và tập dữ liệu đầu vào ....................................... 46 Bảng 4.3 Đánh giá kết quả chƣơng trình thực nghiệm ....................................... 48 Bảng 4.4 Đánh giá chất lƣợng các cộng đồng .................................................... 50 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1 Tổng quan về KPQT ............................................................................ 10 Hình 1.2 Quá trình phát hiện mô hình quy trình từ nhật ký sự kiện ................... 11 Hình 1.3 Các bài toán KPQT .............................................................................. 13 Hình 1.4 Các ứng dụng KPQT trong các lĩnh vực .............................................. 14 Hình 1.5 Mô hình tổ chức đƣợc phát hiện từ các nhật ký sự kiện ...................... 19 Hình 2.1 Các loại cấu trúc cộng đồng ................................................................. 24 Hình 2.2 Các phƣơng pháp phân cụm thứ bậc .................................................... 26 Hình 3.1 Một phần mã nguồn dữ liệu nhật ký sự kiện........................................ 35 Hình 3.2 Mô hình áp dụng giải tìm kiếm cộng đồng vào KPQT ........................ 37 Hình 3.3 Thông tin quá trình xử lý sự cố đƣợc lƣu trong tệp BPI2013.xes ....... 39 Hình 3.5 Định dạng dữ liệu .txt lƣu đồ thị .......................................................... 40 Hình 3.4 Đồ thị đƣợc xây dựng từ ma trận kề .................................................... 41 Hình 3.6 Quá trình phân cụm thứ bậc từ dƣới - lên ............................................ 43 Hình 3.8 Các cộng đồng đỉnh chồng chéo .......................................................... 44 Hình 4.1 Kết quả chƣơng trình thực nghiệm ...................................................... 47 7 MỞ ĐẦU Trong môi trƣờng cạnh tranh hiện nay, yếu tố cốt lõi của các tổ chức, doanh nghiệp là truy cập thông tin, nghiệp vụ một cách nhanh chóng, hiệu quả và đạt chi phí tối ƣu. Kinh doanh thông minh bao gồm các công nghệ và công cụ để chuyển đổi những dữ liệu thô thành những thông tin có nghĩa và có ích cho mục đích phân tích kinh doanh, là các ứng dụng và công nghệ để chuyển dữ liệu doanh nghiệp thành hành động. Với sự gia tăng các hệ thống tích hợp thông tin từ quá trình kinh doanh nhƣ WFM, ERP, CRM, SCM và B2B, … đã tạo ra cách thức tiếp cận mới trong việc phân tích dữ liệu lớn (big data). Khai phá quy trình (KPQT) kinh doanh hay KPQT là cầu nối quan trọng giữa khai phá dữ liệu với quản lý quá trình kinh doanh [12]. Các kỹ thuật này giúp trích lọc các thông tin có giá trị hay các thông tin mà các doanh nghiệp cần từ tập nhật ký sự kiện đƣợc lƣu trong các hệ thống tích hợp thông tin, giúp bổ sung vào các tiếp cận hiện có để quản lý quy trình kinh doanh. Bài toán KPQT gồm ba bài toán nhằm cải thiện quy trình kinh doanh và để mở rộng mô hình quy trình (MHQT) cần bổ sung ba khía cạnh: tổ chức, thời gian và trƣờng hợp[1]. Khía cạnh tổ chức bao gồm nhiều kỹ thuật có giá trị nhƣ khai phá mạng xã hội, khai phá luật phân phối nguồn tài nguyên, …[8]. Trong đó, khai phá mạng xã hội bao gồm những kỹ thuật khai phá đƣợc sử dụng rộng rãi, cho phép phát hiện ra mạng xã hội (MXH) giữa những phòng, đơn vị, cá nhân tham gia vào quy trình kinh doanh từ nhật ký sự kiện. Việc phân tích và đánh giá những mối quan hệ này giúp nhà quản lý có cái nhìn chính xác về các quy trình hiện có trong tổ chức của họ. Trong mô hình MXH, các đỉnh đại diện cho phòng, đơn vị hay con ngƣời, mối quan hệ giữa các đỉnh đƣợc biểu diễn dƣới dạng cạnh. Vấn đề chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình là một thách thức mang tính thời sự đối với các doanh nghiệp. Hậu quả của vấn đề này mang lại thiệt hại về kinh tế và quy trình kinh doanh hoạt động kém thông suốt. Với một doanh nghiệp quy mô lớn, mô hình MXH sẽ kích thƣớc lớn bao gồm nhiều đỉnh và mật độ kết nối giữa các đỉnh dày đặc. Để tìm ra đƣợc những ngƣời có sự chồng chéo về nhiệm vụ trong MXH có kích thƣớc lớn vẫn là một bài toán khó, đã và đang đƣợc khoa học quan tâm, nghiên cứu. Để giải quyết những thách thức trên, tác giả đề xuất phƣơng pháp áp dụng giải thuật tìm kiếm cộng đồng vào bài toán khái phá quy trình. Ý tƣởng của đề xuất là sử dụng các kỹ thuật của KCTC để phát hiện mô hình MXH từ tập nhật ký sự kiện. Sau đó, sử dụng giải thuật tìm kiếm cộng đồng chồng chéo để tìm ra các cộng đồng có cấu trúc chồng chéo. Hiệu quả của đề xuất này là giúp đơn giản hóa cấu trúc mạng tức là chia một mạng có kích thƣớc lớn thành các mạng 8 có kích thƣớc nhỏ và sự kết nối chặt chẽ hơn [7]. Do mục tiêu của luận văn tìm ra các cộng đồng chồng chéo nên Tác giả chỉ tập trung vào các giải thuật tìm kiếm cộng đồng chồng chéo, là loại cấu trúc cộng đồng xuất hiện phổ biến trong thực tế. Các nhiệm vụ chính của Luận văn sẽ thực hiện: 1. Nghiên cứu tổng quan về lĩnh vực KPQT và giải thuật tìm kiếm cộng đồng trong MXH những năm gần đây. 2. Phát biểu bài toán KCTC và đề xuất mô hình giải quyết bài toán. 3. Xây dựng chƣơng trình thực nghiệm dựa trên mô hình đề xuất trong luận văn và đánh giá kết quả thu đƣợc. Bố cục của luận văn bao gồm phần mở đầu, bốn chƣơng nội dung, phần kết luận và phƣơng phát triển tƣơng lai, danh mục tài liệu tham khảo. Chương 1. Tổng quan về KPQT: Giới thiệu tổng quan về KPQT, trong đó trình bày chi tiết các vấn đề liên quan đến khía cạnh tổ chức và phân tích phƣơng pháp phát hiện MXH từ nhật ký sự kiện. Phần chính của Chƣơng này là phát biểu bài toán cần xử lý và đƣa ra phƣơng pháp giải quyết. Từ đó, có những nhận định về ý nghĩa thực tiễn, ý nghĩa khoa học của luận văn. Chương 2. Các giải thuật tìm kiếm cộng đồng trong MXH: Giới thiệu các loại giải thuật tìm kiếm và đặc biệt là các giải thuật tìm kiếm cộng đồng chồng chéo. Sau đó, Tác giả sẽ lựa chọn giải thuật tìm kiếm cộng đồng chồng chéo sẽ áp dụng vào bài toán KPQT. Phân tích chi tiết giải thuật Phân vùng theo cạnh của nhóm tác giả Ahn et al. đƣa ra vào năm 2010 [4]. Chương 3. Áp dụng các giải thuật tìm kiếm cộng đồng vào bài toán KPQT: Đề xuất mô hình giải quyết bài toán và đƣa ra định dạng dữ liệu đầu vào các độ đo đƣợc sử dụng trong mô hình. Phân tích chi tiết các bƣớc thực hiện trong mô hình. Kết quả của quá trình này tìm ra các cộng đồng cạnh có cấu trúc phân cấp, tƣơng ứng là cộng đồng đỉnh có cấu trúc chồng chéo. Chương 4. Kết quả thực nghiệm và đánh giá: Đƣa ra các yêu cầu về dữ liệu, phần cứng, phần mềm và mã nguồn cần thiết để xây dựng chƣơng trình thực nghiệm theo mô hình đề xuất. Dựa trên bảng số liệu thu đƣợc sau khi chạy chƣơng trình với các tệp dữ liệu dùng làm mẫu thử nghiệm, tác giả sẽ sử dụng các tiêu chuẩn và độ đo để phân tích chi tiết các thông số trong bảng. Từ đó, đánh giá các kết quả thu đƣợc dựa vào sự phân tích này. 9 CHƢƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH 1.1 Khai phá quy trình Ngày nay, câu nói “khách hàng là thượng đế” đã trở nên quen thuộc đối với các doanh nghiệp, bởi khách hàng là ngƣời trả tiền cho các sản phẩm, dịch vụ của họ. Hầu hết, doanh nhân của mọi quốc gia trên thế giới đều nhận thức đầy đủ về tầm quan trọng của khách hàng và họ luôn cố gắng phục vụ khách hàng chu đáo nhất. Thực tế cho thấy, nhu cầu và mong muốn của khách hàng thƣờng xuyên thay đổi. Điều này đã tác động rất lớn đến các doanh nghiệp, tạo ra một thị trƣờng cạnh tranh, tất cả họ đều có chung một mục đích là đáp ứng tốt nhất những yêu cầu thay đổi thƣờng xuyên này. Đây là là một thách thức lớn nhất mà mỗi doanh nghiệp hàng ngày phải đối mặt. Do đó, để có thể cạnh tranh thuận lợi, các doanh nghiệp cần phải nghiên cứu, thay đổi và cải tiến quy trình kinh doanh phù hợp với thực tế. Kinh doanh thông minh (Business intelligence) là một hƣớng nghiên cứu quan trọng, trong đó có sử dụng dữ liệu đƣợc lƣu trữ trong các hệ thống thông tin (HTTT). Sự xuất hiện “nền kinh tế số” đã làm thay đổi hai vấn đề là quá trình điều hành kinh doanh và đánh giá hiệu suất công việc. Hầu hết, các doanh nghiệp có quy mô lớn đều sử dụng các HTTT để hỗ trợ toàn hộ hay một phần của quy trình kinh doanh. Dữ liệu sinh ra từ quá trình này đƣợc lƣu lại gọi là nhật ký sự kiện. Các hệ thống ERP, WFM, CRM, SCM, B2B đều là kết quả của sự cải tiến công nghệ và quá trình kinh doanh trong thực tế. Ngày nay, các HTTT trở lên liên quan mật thiết hơn với các quy trình kinh doanh mà chúng hỗ trợ. Một quy trình kinh doanh giúp điều hành hiệu quả các lĩnh vực quản lý hậu cần, quản lý bán hàng, quản lý nhân lực, ... Sự gia tăng các hệ thống lƣu trữ thông tin giúp quy trình kinh doanh đạt hiệu quả, hỗ trợ khả năng truy nhập và phân tích dữ liệu. Việc trích lọc ra các thông tin có giá trị nhằm cải thiện khả năng ra quyết định và mô hình quy trình vẫn là một vấn đề đƣợc các doanh nghiệp quan tâm. Thực tế, việc tràn ngập các thông tin đã gây ra áp lực, thách thức lớn trong việc trích lọc ra những thông tin có giá trị. KPQT giúp trích lọc và phân tích dữ liệu để tìm ra mối liên quan giữa những đối tƣợng dữ liệu. Ý tƣởng KPQT đƣợc các nhà khoa học Cook và Wolf đã nghiên cứu các từ năm 1998. Sau đó, Herbst và Karagianis cũng đƣa các vấn đề KPQT trong nội dung liên quan quản lý luồng công việc. Trong hội thảo về kinh doanh thông minh, KPQT cũng đƣợc các nhà khoa học đề cập trong các nội dung quản lý kinh doanh. Những đóng góp lớn tới lĩnh vực này đã đƣợc thêm vào sau bởi Wil M.P. Van der Aalst và các cộng sự. Nhóm nghiên cứu đã đƣa ra các thuật toán khai phá đỉnh cao và sự thêm đa dạng các chủ đề liên quan tới các thách thức 10 trong các quy trình kinh doanh. Do vậy, các nhà khoa học và ngƣời nghiên cứu lĩnh vực này có thể dễ sử dụng nhiều phƣơng pháp và công cụ có sẵn. Quản lý quy trình kinh doanh là một lĩnh vực kết nối giữa tri thức công nghệ thông tin và khoa học quản lý, áp dụng những tri thức này vào quá trình điều hành kinh doanh [1]. Những năm gần đây, KPQT đã nổi lên và trở thành lĩnh vực nghiên cứu đầy tiềm năng, là lĩnh vực “một mặt nằm giữa thông minh điện toán và khai phá dữ liệu, mặt khác nằm giữa mô hình và phân tích quy trình […] Giúp phát hiện, giám sát và cải thiện các quy trình thực bằng cách trích lọc tri thức từ các nhật ký sự kiện” [1] đƣợc lƣu trong các HTTT. KPQT là một khái niệm bao gồm tất cả các phƣơng pháp trích xuất các mô hình quy trình có cấu trúc từ một tập các công việc trong thực tế [8]. Cụ thể, các kỹ thuật này giúp trích lọc các thông tin có giá trị và liên quan đến quy trình từ các tập nhật ký sự kiện. Tuy nhiên, các tổ chức gặp phải các vấn đề về giá trị trích lọc từ những dữ liệu này [28]. Hình 1.1 Tổng quan về KPQT 1.1.1 Sự cần thiết của KPQT: - Trực quan hóa quy trình kinh doanh bằng mô hình: Tất cả những hoạt động trong công ty nếu nhìn bằng mắt thƣờng chỉ là cái nhìn chủ quan, nó không phản ánh đƣợc bản chất sâu bên trong của từng hoạt động. Vì vậy, KPQT sẽ giúp các doanh nghiệp thấy rõ các hoạt động, sự tƣơng tác, thời điểm xảy ra các hoạt động trong nội bộ của họ. - Hỗ trợ ra quyết định: Những mô tả hoạt động của doanh nghiệp trên giấy có thể khác xa so với thực tế, tùy theo từng nhà quản lý có thể nhìn thấy hoặc không nhìn thấy vấn đề này. Kết quả là một loạt các đơn vị chức năng hoạt động yếu kém do không đáp ứng đƣợc yêu cầu, đòi hỏi từ thực tế. KPQT tìm ra những tồn tại, hạn chế trong hoạt động kinh doanh một cách nhanh chóng, giúp nhà quản lý có thể ra quyết định chính xác trong các công việc. 11 Hình 1.2 Quá trình phát hiện mô hình quy trình từ nhật ký sự kiện Hình 1.2 cho thấy dữ liệu hoạt động của doanh nghiệp sẽ đƣợc lƣu lại trong các HTTT, áp dụng các kỹ thuật KPQT để trích xuất ra các thông tin có giá trị hay mô hình quy trình. - Tạo ra sự khách quan, giảm thiểu rủi ro: Nhà quản lý có thể có những ý kiến chủ quan cũng nhƣ có sự thiên vị hay kỳ vọng quá mức về một vấn đề nào đó. Những sai lệch này dẫn đến một loạt các cuộc họp gây lãng phí thời gian, tiền bạc và tạo ra sự mâu thuẫn nội bộ. Kết quả của những phƣơng án giải quyết có thể không phù hợp với thực tế. KPQT giúp các doanh nghiệp có cơ sở tin tƣởng những giải pháp cho những vấn đề phức tạp của doanh nghiệp. 1.1.2 Mục tiêu của KPQT: Mục tiêu chính của KPQT là phát hiện, phân tích và hiểu các quy trình kinh doanh dựa trên các bản ghi các hoạt động tại thời một thời điểm xác định, thông tin này đƣợc lƣu trong các tập nhật ký sự kiện. KPQT giúp trích lọc các thông tin liên quan, phát hiện ra mô hình quy trình mới từ các dữ liệu sự kiện, đƣợc lƣu trong các HTTT lớn [1]. Quá trình này bao gồm các kỹ thuật, công cụ và phƣơng thức để phát hiện, giám sát, cải thiện các quy trình trong thực tế [36]. 1.1.3 Mô hình quy trình và nhật ký sự kiện: a) Mô hình quy trình (MHQT): Trong bối cảnh khoa học HTTT, một mô hình là đại diện phi vật chất của thế giới thực, đƣợc sử dụng cho một mục đích cụ thể [31]. Các mô hình đƣợc sử dụng để làm giảm độ phức tạp bằng cách biểu diễn những đặc trƣng đƣợc quan tâm, bỏ qua những đặc trƣng khác. Một MHQT là sự biểu diễn hình học của một quy trình kinh doanh, mô tả sự ràng buộc giữa các công việc cần đƣợc thực hiện trong những kế hoạch kinh doanh. MHQT là 12 một tập các mô hình biểu diễn các hoạt động của công ty và sự ràng buộc giữa các mô hình [29]. Các mô hình này có thể đƣợc biểu diễn dƣới dạng BPNN, EPC hoặc lƣới Petri. Nếu các mô hình đƣợc xây dựng theo phƣơng pháp thủ công, độ tin cậy không cao do những yếu tố chủ quan. Để đảm bảo đƣợc sự tin cậy của MHQT, phƣơng pháp khai phá dữ liệu lƣu trong các HTTT đƣợc đƣa ra. Những dữ liệu này là các dữ liệu đƣợc tạo ra từ các giao dịch kinh doanh, các mô hình sinh ra phản ánh đúng thực tế quá trình kinh doanh của doanh nghiệp và tạo ra độ tin cậy cao. b) Nhật ký sự kiện: Là nguồn thông tin đƣợc lấy từ nhiều nguồn khác nhau nhƣ phỏng vấn, khảo sát, giám sát công việc, ….sẽ đƣợc lƣu trong các HTTT. Sau đó, chúng đƣợc trích lọc các thông tin liên quan đến cấu trúc mô hình, việc phân tích sẽ đƣợc thực hiện. Những công việc này có thể đƣợc thực hiện thủ công hay bằng một số ứng dụng KPQT. Các thông tin đƣợc trích lọc từ tập các nhật ký sự kiện sẽ đƣợc trích xuất và lƣu dƣới dạng XML [18], các bản ghi trong cơ sở dữ liệu liệu [33] hoặc kho dữ liệu [32]. Dựa vào các nguồn dữ liệu này, các ứng dụng KPQT sẽ xây dựng lên các MHQT và những dự đoán hiệu quả kinh doanh. Tập dữ liệu đƣợc lấy từ nhiều nguồn đƣợc lƣu trữ trong cùng một hệ thống nhƣ kho dữ liệu, cung cấp nền tảng khai phá tri thức chƣa đƣợc biết đến và mối quan hệ giữa các thực thể trong quy trình. Các tri thức mới đƣợc phát hiện có liên quan nhƣ các bộ phận kinh doanh, danh mục sản phẩm, nhà cung cấp, lộ trình và thời gian thực hiện quy trình. 1.1.4 Các bài toán KPQT: Có 03 bài toán chính: Phát hiện mô hình quy trình:Kỹ thuật này phát hiện ra các mô hình chƣa đƣợc biết đến trƣớc đó, các mô hình này sẽ đƣợc dùng vào mục đích phân tích hoặc tối ƣu hóa [36]. Trong đó: Đầu vào: Nhật ký sự kiện. Đầu ra: Mô hình quy trình. Kiểm tra sự phù hợp của mô hình quy trình: Kỹ thuật này sử dụng mô hình quy trình đang tồn tại và so sánh với dữ liệu lƣu trong nhật ký sự kiện, nhằm kiểm tra sự phù hợp của mô hình quy trình với thực tế. Trong đó: Đầu vào: Nhật ký sự kiện, Mô hình quy trình. Đầu ra: Các độ đo phù hợp. Tăng cường mô hình quy trình: Đây là kỹ thuật mở rộng hay cải tiến mô hình quy trình đang tồn tại sử dụng thông tin về quy trình thực đƣợc ghi lại trong các nhật ký sự kiện. Đầu vào: Mô hình quy trình hiện có, Nhật ký sự kiện. 13 Đầu ra:Mô hình quy trình đƣợc bổ sung. Hình 1.3 Các bài toán KPQT Hình 1.3 biểu diễn sự tƣơng tác giữa KPQT, dữ liệu nhật ký sự kiện và nền tảng phân tích. Khai phá nhật ký sự kiện hay sự các quy trình kinh doanh thực để phát hiện ra sự tắc nghẽn, đứt đoạn của quy trình. Trong KPQT, sự tƣơng tác giữa những thực thể theo một quy luật logic, do đó những kết quả của lĩnh vực này mang lại là rất lớn đối với lĩnh vực kinh doanh thông minh. 1.1.5 Các khía cạnh của KPQT: Mở rộng MHQT khi bổ sung các khía cạnh, bao gồm: Khía cạnh tổ chức: tập trung vào các thông tin về các nguồn tài nguyên ẩn dƣới các nhật ký. Các nguồn tài nguyên này bao gồm con ngƣời, hệ thống hay vai trò hay bộ phận liên quan và sự liên hệ giữa các yếu tố đó. Mục tiêu của khía cạnh này là để xây dựng cấu trúc tổ chức bằng cách phân lớp ngƣời tham gia quy trình theo vai trò, đơn vị, đồng thời biểu diễn MXH. Khía cạnh trường hợp: Tập trung vào các thuộc tính riêng của các trƣờng hợp nhƣ số ngƣời tham gia, thứ tự thực hiện các hoạt động, những ngƣời tham gia, … Từ đó thiết lập mối quan hệ giữa những thuộc tính này, tạo đầu vào cho các giải thuật phân cụm. Khía cạnh thời gian: Liên quan đến thời gian và tần suất xuất hiện của các sự kiện. Từ lịch biểu thời gian xảy ra các sự kiện giúp phát hiện các đoạn “nút thắt cổ chai” hay bị trì hoãn, tắc nghẽn luồng công việc, ƣớc tính các mức độ dịch vụ, giám sát các nguồn tài nguyên hay dự đoán thời gian trống trong các trƣờng hợp. 14 1.1.6 Các ứng dụng của KPQT Các ứng dụng KPQT có thể đƣợc sử dụng nhƣ là một công cụ kiểm soát trực tiếp hiệu suất quy trình kinh doanh. Một số ứng dụng KPQT hiện nay nhƣ: - EmiT là công cụ sử dụng nhật ký sự kiện định dạng XML làm dữ liệu đầu vào. Giúp phát hiện mô hình quy trình và biểu diễn quy trình dƣới dạng lƣới Petri. - ARIS PPM là công cụ để đánh giá quy trình kinh doanh. Kỹ thuật này giúp phân tích lịch sử của các quy trình để tìm ra điểm yếu trong quy trình hiện tại, tối ƣu hóa cấu trúc tổ chức, … - PISA là công cụ dùng để xác định hiệu suất quy trình từ nhật ký sự kiện. - ProM là phần mềm mã nguồn mở, dùng cho những ngƣời nghiên cứu lĩnh vực KPQT. Công cụ này cung cấp nhiều plug-in cho nhiều giải thuật khai phá khác nhau. - Disco là một ứng dụng thƣơng mại, giúp trích lọc và tải các nhật ký sự kiện. Hình 1.4 Các ứng dụng KPQT trong các lĩnh vực Hình 1.4 cho thấy sự phổ biến các ứng dụng KPQT trong rất nhiều các lĩnh vực kinh doanh. 1.1.7 Một số thách thức đối với lĩnh vực KPQT - Mục đích sử dụng: KPQT là một công nghệ cần phải đƣợc đặt trong bối cảnh cụ thể thì mới làm nổi bật lên giá trị của lĩnh vực này. Các lợi ích của KPQT mang lại nhƣ tăng hiệu quả hoạt động của doanh nghiệp, quản lý rủi ro và bảo đảm quá trình, giảm thiểu sai sót, kiểm soát chất lƣợng dịch vụ. 15 - Các bản ghi sự kiện bị lỗi và thiếu: Đối với các bản ghi không chính xác của nhật ký sự kiện có thể đƣợc sinh ra do sự cố phần mềm, đột biến ngƣời dùng, lỗi phần cứng hoặc bị cắt xén các trƣờng hợp của quy trình trong lúc trích lọc dữ liệu. Các bản ghi bị sai trong nhật ký sự kiện đƣợc coi là một biểu hiện lạ trong một hiện tƣợng đƣợc gọi là bản ghi bị lỗi. Các bản ghi bị lỗi đƣợc lƣu lại chính xác và thƣờng hiếm khi xảy ra [1]. Các bản ghi sự kiện lỗi này sẽ làm tăng độ phức tạp của mô hình quy trình. Các đề xuất KPQT vì thế mà đƣa ra những sự phân tích và mô hình không đúng. - Chất lượng nhật ký sự kiện: Việc thu thập dữ liệu và tiền xử lý dữ liệu là một thách thức trƣớc khi bắt đầu KPQT, vì chất lƣợng của dữ liệu ảnh hƣởng lớn đến kết quả của KPQT. Chất lƣợng của các nhật ký sự kiện sẽ ảnh hƣởng chủ yếu tới chất lƣợng khai phá và tái cấu trúc các mô hình quy trình. Các hệ thống quy trình kinh doanh và quản lý luồng công việc tạo ra các nhật ký sự kiện với chất lƣợng cao nhất [36]. - Mô hình quy trình phức tạp: Các quy trình trong thực tế thƣờng rất phức tạp. Việc biểu diễn chúng bằng hình học có thể dẫn các mô hình có độ phức tạp cao và rất khó hiểu. Hai mô hình quy trình phức tạp điển hình đƣợc gọi là quy trình Lasagna và Spaghetti [1]. Giảm độ phức tạp của mô hình là một thách thức lớn và đang là đối tƣợng nghiên cứu ngày nay [23]. - Các loại hình quy trình: KPQT chỉ có thể đƣợc áp dụng đối với các quy trình đƣợc kiểm soát hoàn toàn bằng HTTT. Trong thực tế, các quy trình chỉ cần đƣợc quan sát dƣới một số hình thức. Đối với một số hệ thống quản lý quy trình kinh doanh theo mô hình và cấu hình định sẵn thƣờng ít có giá trị đối với việc phát hiện lại các luồng tiến trình. Thông thƣờng, các bộ phận trong một quy trình là tự động, một số bộ phận đƣợc điều khiển bởi con ngƣời. Do vậy, rất khó kiểm soát đƣợc những việc mà họ đã làm gì trong bộ phận đó. KPQT đƣợc áp dụng cho một lƣợng lớn các loại dữ liệu bao gồm cơ sở dữ liệu, các nhật ký giao dịch, các bảng excel. 1.2 Khía cạnh tổ chức trong KPQT Trong một tổ chức, dù có trang thiết bị hiện đại, tối tân thì yếu tố con ngƣời vẫn đóng vai trò quan trong nhất. Sự chồng chéo chức năng, nhiệm vụ giữa các cá nhân, phòng, ban, đơn vị làm cho cơ cấu tổ chức trở nên cồng kềnh, giảm hiệu suất công việc và tốn kém chi phí. Những giải pháp cải tiến về khía cạnh tổ chức đã và đang đƣợc các nhà khoa học, nhà quản lý quan tâm và nghiên cứu. 16 Khía cạnh tổ chức là một trong ba khía cạnh quan trọng nhất của bài toán KPQT, các kỹ thuật bao gồm: khai phá tổ chức, khai phá MXH, khai phá luật phân phối nguồn tài nguyên, …[8]. Đây là những kỹ thuật giá trị cho phép phát hiện mô hình MXH của một tổ chức. Đồng thời giúp đƣa ra cách thức đánh giá các mạng lƣới này bằng cách ánh xạ và phân tích các mối quan hệ giữa những cá nhân, đơn vị trong công ty. Tuy nhiên, khi phân tích MXH với kích thƣớc lớn, các kỹ thuật của KPQT sinh ra các mô hình với sự phức tạp cao, điều này làm cho ngƣời dùng bối dối và khó khăn để hiểu đƣợc chúng. Phân tích dựa vào cấu trúc hình học bao gồm chiến lƣợc “chia để trị” nhằm trực quan hóa và phân tích mô hình mạng trong các mức độ tổng quát khác nhau. - Mục tiêu của KCTC: Khía cạnh tổ chức tập trung vào các nguồn tài nguyên, nhƣ những ngƣời thực hiện có liên quan đến mô hình quy trình và sự liên quan và mối quan hệ của họ với quy trình. Mục tiêu chính của khía cạnh này là tìm ra cấu trúc tổ chức bằng cách phân lớp ngƣời tham gia vào quy trình trong các giới hạn của các đơn vị, vai trò của từng ngƣời, mối quan hệ của những ngƣời tham gia vào quy trình. - Vai trò KCTC: Các kỹ thuật này giúp phát hiện cấu trúc tổ chức, phân tích MXH, cấp phát tài nguyên và khai phá vai trò từng cá thể, nhóm hay tổ chức trong MXH. Khai phá khía cạnh tổ chức là phân tích những thông tin đƣợc tiết lộ từ khía cạnh tổ chức. Kỹ thuật này bao gồm việc phát hiện các MXH, cấu trúc tổ chức và hành vi của tổ chức [2]. Các kỹ thuật khai phá này tạo nên nền tảng đối với các nhiệm vụ sau: + Chứng thực: tập trung vào kiểm soát truy nhập giúp đảm bảo chỉ những cá nhân, đơn vị nào đƣợc chứng thực có vai trò mới đƣợc phép thực hiện các hoạt động trong quy trình. + Kiểm soát tài nguyên: tập trung vào những ràng buộc sau khi truy nhập dữ liệu nhƣ ngƣời hay nhóm ngƣời sẽ nắm giữ và sử dụng dữ liệu. + Tái cơ cấu tổ chức: Phân tách: ràng buộc liên quan tới quy trình giới hạn các khả năng của các đơn vị khi thực hiện các hoạt động, giúp giảm rủi ro khi gặp lỗi. Sát nhập: đây là sự ràng buộc hai chiều, sắp xếp các chủ thể, tác vụ vào cùng một nhóm các hoạt động cụ thể. + Kiểm soát xung đột: ngăn các luồng thông tin mang tính nhạy cảm giữa những đối thủ cạnh tranh hay các phòng, ban là những đơn vị tham gia vào quy trình kinh doanh. 17 - Phân tích MXH: Jacob Levy Moreno đã đƣa ra khái niệm mô hình MXH vào năm 1932-1938, ông đã nghiên cứu mô hình MXH các trƣờng học dành cho nhóm học sinh nữ tại Hudson, NewYork [30]. MXH là một mô hình đƣợc biểu diễn dƣới dạng đồ thị, là phƣơng pháp biểu diễn dữ liệu và các mối quan hệ của các dữ liệu này dƣới dạng đồ thị. Phát hiện MXH từ nhật ký sự kiện là phát hiện mối quan hệ giữa những ngƣời, nhóm ngƣời tham gia vào quy trình. Nhật ký sự kiện chứa thông tin những ngƣời tham gia vào quy trình hoặc việc khởi tạo sự kiện. Sử dụng một số kỹ thuật phân tích MXH và các kết quả nghiên cứu có sẵn, các MXH này cho phép phân tích mối quan hệ giữa các chủ thể bao gồm các tiến trình thực thi quy trình. Các kết quả phân tích đƣợc sử dụng để xác định những ngƣời thƣờng xuyên giao tiếp với nhau trong quy trình, ngƣời có kết giao tiếp nhiều nhất (tầm ảnh hƣởng nhất) với ngƣời khác, vai trò ngƣời và nhóm ngƣời trong quy trình hay hiện tƣợng tắc nghẽn hoạt động bởi ngƣời nào trong quy trình. Phân tích MXH (Social Network Analysis) bao gồm tập các phƣơng pháp, kỹ thuật, công cụ giúp trực quan hóa và phân tích các MXH. Kỹ thuật này đóng vai trò quan trọng, giúp đánh giá mối quan hệ giữa những cá nhân, các phòng, đơn vị hay tổ chức tham gia vào quy trình kinh doanh [24] và có thể thu đƣợc những thông tin quan trọng giúp cải thiện quá trình quản lý luồng công việc trong một tổ chức và cho phép ngƣời quản lý tìm ra phƣơng pháp cải thiện chúng [25]. Mục tiêu của các kỹ thuật phân tích MXH là trả về quy trình thực sự minh bạch và cung cấp các kỹ thuật giúp các quy trình kinh doanh trở nên tốt và liền mạch hơn. Để phát hiện ra MXH, các kỹ thuật sẽ sử dụng các độ đo để định lƣợng mức độ thƣờng xuyên và sự chuyển giao công việc giữa những ngƣời thực hiện. Wil M.P. van der Aalst et al. đã đề xuất các loại độ đo xây dựng mô hình MXH từ nhật ký sự kiện [8], bao gồm: - Độ đo dựa trên quá trình thực hiện nhiệm vụ: đánh giá mức độ các công việc đƣợc chuyển giữa những ngƣời tham gia vào quy trình. Độ đo Handover of work tính số lần mà ngƣời i thực hiện một nhiệm vụ trƣớc một ngƣời j trong một trƣờng hợp. Giá trị độ đo Subcontracting là số lần ngƣời j thực hiện nhiệm vụ giữa hai nhiệm vụ khác mà ngƣời i thực hiện. - Độ đo dựa trên những người tham gia cùng một trường hợp: tính mức độ thƣờng xuyên hai ngƣời thực hiện nhiệm vụ trong cùng một trƣờng hợp. Hai cá nhân thƣờng xuyên làm việc cùng một trƣờng hợp có mối quan hệ mật thiết với nhau hơn những ngƣời khác. Giá trị độ đo Working together là số lần hai ngƣời thực hiện nhiệm vụ trong cùng một trƣờng hợp. 18 - Độ đo dựa trên loại nhiệm vụ: tập trung vào tính chất công việc cần phải thực hiện. Hai ngƣời thực hiện các nhiệm vụ tƣơng tự nhau sẽ có mối quan hệ mật thiết hơn. Độ đo Similar task sử dụng hàm tính khoảng cách Hamming, … để tính khoảng cách giữa các nhiệm vụ. - Độ đo dựa trên loại sự kiện: Các sự kiện tƣơng ứng với sự thực hiện các nhiệm vụ. Tuy nhiên, có những sự kiện tƣơng ứng với hoạt động chỉ đƣợc giao giữa ngƣời i sang ngƣời j và không có chiều ngƣợc lại. Mối quan hệ này thể hiện sự phân cấp quyền lực. 1.3 Bài toán toán khai phá khía cạnh tổ chức 1.3.1 Trong thực tế: Hầu hết, các doanh nghiệp và tổ chức đều đang gặp phải vấn đề liên quan đến sự chồng chéo, trùng lắp, phân công chƣa rõ ràng, chƣa hợp lý về chức năng, nhiệm vụ giữa các cá nhân, bộ phận. Đây là những vấn đề đƣợc coi là những thách thức vì nhà quản lý đã nhìn thấy, nhƣng chƣa tìm đƣợc cách giải quyết tối ƣu. Những thách thức này là nguyên nhân dẫn đến giảm doanh thu và hiệu suất công việc, tăng chi phí cho các nhiệm vụ thống kê, phân tích viết báo cáo lập kế hoạch, quy hoạch liên quan đến những vấn đề tổ chức. Nguyên nhân: Chƣa thống nhất về phân công nhiệm vụ giữa các phòng, ban, đơn vị; cách nhìn chủ quan của nhà quản lý đối với việc phân công nhiệm vụ; thiếu tiêu chuẩn để phân định rõ ràng; tính chất phức tạp, đa dạng của công việc; việc đáp ứng những mong muốn thay đổi theo ngày của khách hàng cũng là nguyên nhân làm cho những cơ cấu tổ chức trƣớc đó trở lên lạc hậu. Giải pháp trong thực tế: Rà soát, nghiên cứu, phân tích, đánh giá và làm rõ chức năng, nhiệm vụ của từng bộ phận để tìm ra sự chồng chéo. 1.3.2 Trong luận văn: Dựa trên những thách thức của bài toán trong thực tế, luận văn tập trung vào giải quyết những thách thức này trong bài toán KPQT. - Giới hạn luận văn: Phát hiện sự chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình từ tập dữ liệu sự kiện có sẵn. Phát biểu bài toán: Đầu vào: Tập dữ liệu sự kiện định dạng XES 1.0. Đầu ra: Các cộng đồng chồng chồng chéo. - Phân tích bài toán: Có 04 danh từ, cụm danh từ trong bài toán trên cần quan tâm: “người”, “mối quan hệ”, “nhóm người” và “mật thiết”. Ta giả định