Tóm tắt Luận văn 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 Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.01.04 TÓM TẮT LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Hà Nội - 2016 i MỤC LỤC DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ..................... iii DANH MỤC CÁC BẢNG ................................................. iv MỞ ĐẦU ............................................................................ 5 CHƢƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH................................................................................ 8 1.1 Khai phá quy trình .................................................. 8 1.1.1 Sự cần thiết của KPQT ............................................ 8 1.1.2 Mục tiêu của KPQT................................................. 8 1.1.3 Mô hình quy trình và nhật ký sự kiện ..................... 8 1.1.4 Các bài toán KPQT ................................................. 8 1.1.5 Các khía cạnh của KPQT ........................................ 8 1.1.6 Các ứng dụng của KPQT: ....................................... 9 1.1.7 Một số thách thức đối với lĩnh vực KPQT .............. 9 1.2 Khía cạnh tổ chức trong KPQT .............................. 9 1.3 Bài toán toán khai phá khía cạnh tổ chức ............... 9 1.4 Ý nghĩa của luận văn ............................................ 10 1.4.1 Về mặt khoa học .................................................... 10 1.4.2 Về mặt thực tiễn .................................................... 10 CHƢƠNG 2. CÁC GIẢI THUẬT TÌM KIẾM CỘNG TRONG MXH .................................................................... 11 2.1 Cộng đồng mạng xã hội ....................................... 11 2.1.1 Nguyên nhân hình thành cộng đồng MXH ........... 11 2.1.2 Các loại cộng đồng trong MXH ............................ 11 2.1.3 Các loại cấu trúc cộng đồng .................................. 11 ii 2.2 Các phƣơng pháp phát hiện cộng đồng ................ 11 2.2.1 Ứng dụng ............................................................... 11 2.2.2 Các loại giải thuật .................................................. 12 2.3 Các giải thuật tìm kiếm cộng đồng chồng chéo .......... 12 2.4 Lựa chọn giải thuật tìm kiếm trong luận văn ....... 12 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 14 3.1. Phƣơng pháp nghiên cứu ..................................... 14 3.1.1 Tính hiệu quả của đề xuất ..................................... 14 3.1.2 Định dạng dữ liệu đầu vào các độ đo: ................... 14 3.2 Giải pháp thực hiện ............................................. 14 3.2.1 Đề xuất mô hình giải quyết ................................... 14 3.2.2 Các bƣớc thực hiện ................................................ 15 CHƢƠNG 4. KẾT QUẢ THỰC NGHIỆM, ĐÁNH GIÁ VÀ KẾT LUẬN ................................................. 17 4.1 Công cụ, môi trƣờng thực nghiệm ....................... 17 4.1.2 Phần mềm và tập dữ liệu đầu vào.......................... 17 4.2 Chƣơng trình thực nghiệm ................................... 17 4.3 Kết quả thực nghiệm và đánh giá ......................... 17 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN TƢƠNG LAI ... 21 TÀI LIỆU THAM KHẢO .................................................. 22 iii DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT Chữ viết tắt Ý nghĩa 1. Tiếng việt CNTT Công nghệ thông tin CSDL Cơ sở dữ liệu HTTT Mô hình quy trình KCTC Khía cạnh tổ chức KPQT Khai phá quy trình MHQT Mô hình quy trình MXH Mạng xã hội 2. Tiếng anh B2B Busines-to-Business BPNN Back-propagation neural network CRM Customer Relationship Management EPC Event-driven Process Chain ERP Systems for Enterprise Resource Planning NMI Normalized mutual information SCM Supply Chain Management UPGMA Unweighter Pair-Group Method using Arithmetic averages WFM Workflow Management XES eXtensible Event Stream XML EXtensible Markup Language iv DANH MỤC CÁC BẢNG Bảng 2.1 Sự mâu thuẫn của hai cấu trúc giữa chồng chéo và phân cấp ..................................................................... 11 Bảng 4.3 Đánh giá kết quả chƣơng trình thực nghiệm ... 17 Bảng 4.4 Đánh giá chất lƣợng các cộng đồng ................ 20 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 3.2 Mô hình áp dụng giải tìm kiếm cộng đồng vào KPQT ............................................................................. 14 Hình 3.5 Định dạng dữ liệu .txt lƣu đồ thị ..................... 15 5 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 là một tập các quy trình để thu thập, truy cập và phân tích thông tin kinh doanh, giúp nâng cao khả năng ra quyết định kinh doanh của các nhà quản lý. 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. 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ý quá 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à ba khía cạnh bao gồm các kỹ thuật khai phá quan trọng [1]. Khía cạnh tổ chức bao gồm nhiều kỹ thuật có giá trị nhƣ khai phá tổ chức, 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 là một trong những kỹ thuật đƣợ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 trong doanh nghiệp của họ. Trong mô hình MXH, phòng, đơn vị hay con ngƣời sẽ đƣợc biểu diễn dƣới dạng các đỉnh, mối quan hệ giữa các đỉnh đƣợc biểu diễn dƣới dạng cạnh. Vấn đề chồng 6 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ế lớn 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 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 phổ biến trong thực tế. 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 7 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. 8 CHƢƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH 1.1 Khai phá quy trình 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. KPQT 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”. 1.1.1 Sự cần thiết của KPQT: - Trực quan hóa quy trình kinh doanh . - Hỗ trợ ra quyết định. - Tạo ra sự khách quan, giảm thiểu rủi ro. 1.1.2 Mục tiêu 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 1.1.3 Mô hình quy trình và nhật ký sự kiện: a) Mô hình quy trình (MHQT): 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 cụ thể. 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. 1.1.4 Các bài toán KPQT: - Phát hiện quy trình. - Kiểm tra sự thống nhất. - Tăng cƣờng mô hình. 1.1.5 Các khía cạnh của KPQT - Khía cạnh tổ chức. - Khía cạnh trƣờng hợp. - Khía cạnh thời gian. 9 1.1.6 Các ứng dụng của KPQT: Một số ứng dụng nhƣ EmiT, ARIS PPM (Process Performance Manager), PISA, 1.1.7 Một số thách thức đối với lĩnh vực KPQT - Mục đích sử dụng rõ ràng. - Các bản ghi sự kiện bị lỗi và thiếu. - Chất lƣợng nhật ký sự kiện không đảm bảo. - Mô hình quy trình phức tạp. - Các loại hình quy trình. 1.2 Khía cạnh tổ chức trong KPQT 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à tại sao họ lại liên quan. - Phân tích MXH (SNA): bao gồm tập các phƣơng pháp, kỹ thuật, công cụ nhằm phân tích các MXH. Để phát hiện ra MXH, sử dụng các loại độ đo bao gồm: Handover of work, working together, Độ đo Handover of work tính số lần chuyển giao nhiệm vụ giữa ngƣời i sang ngƣời j. 1.3 Bài toán toán khai phá khía cạnh tổ chức Đầu vào: Tập dữ liệu sự kiện định dạng XES. Đầu ra: Các cộng đồng chồng chồng chéo. Tổng quát các bƣớc giải quyết: (1) Tiền xử lý dữ liệu: Loại bỏ các thông tin bị lỗi, nhiễu, những thông tin không có giá trị khai phá, chuyển về định dạng chuẩn XES 1.0. (2) Xây dựng MXH: Sử dụng các độ đo để xây dựng MXH từ tập nhật ký sự kiện. (3) Phân tích MXH: Sử dụng chiến lƣợc “Chia để trị”, hay áp dụng giải thuật tìm kiếm cộng đồng để tìm ra các cộng đồng chồng chéo trong MXH. (4) Từ kết quả thu đƣợc trong bƣớc 3, tìm ra cộng đồng ngƣời có cấu trúc chồng chéo. 10 1.4 Ý nghĩa của luận văn: 1.4.1 Về mặt khoa học: Luận văn đã tổng quát hóa các phƣơng pháp khoa học để giải quyết những thách thức trong bài toán KCTC. Trong luận văn, Tác giả tập trung đƣa ra các cơ sở khoa học, định hƣớng nghiên cứu để tìm ra sự chồng chéo trong cấu trúc tổ chức từ tập dữ liệu sự kiện, từ đó đề xuất hƣớng giải quyết bài toán. Từ các kết quả nghiên cứu, luận văn đã góp phần làm cơ sở thực tiễn cho các nghiên cứu khoa học sau này. 1.4.2 Về mặt thực tiễn: Những thách thức trong thực tế của doanh nghiệp là động lực Tác giả thực hiện nghiên cứu này và định hƣớng tìm phƣơng pháp giải quyết. Nền tảng của phƣơng pháp giải quyết dựa trên nền tảng khoa học, do đó các nhà quản lý, ngƣời nghiên cứu có thể tin tƣởng, nghiên cứu và phát triển mô hình giải quyết đƣợc đề xuất trong luận văn. Do vấn đề đƣợc đặt ra trong luận văn có tính thời sự, các kết quả nghiên cứu có thể đƣợc áp dụng vào thực tiễn hiện thời, không bị lạc hậu và có thể đánh giá đƣợc hiệu quả của đề xuất. 11 CHƢƠNG 2. CÁC GIẢI THUẬT TÌM KIẾM CỘNG TRONG MXH 2.1 Cộng đồng mạng xã hội: 2.1.1 Nguyên nhân hình thành cộng đồng MXH: - Cùng chung đặc điểm. - Mục đích hoạt động giống nhau. - Cùng mục tiêu về một vấn đề nào đó. - Cùng sở thích và thói quen. 2.1.2 Các loại cộng đồng trong MXH [16]: - Cộng đồng tường minh: Đƣợc hình do những đặc trƣng chung của nhóm đã đƣợc thiết lập. - Cộng đồng không tường minh: Đƣợc hình thành do sự tƣơng tác giữa những ngƣời trong cộng đồng, không thấy rõ bằng mắt thƣờng. 2.1.3 Các loại cấu trúc cộng đồng: TT Sự mâu thuẫn Loại cấu trúc Chồng chéo Không chồng chéo 1 Đặc điểm Một số đỉnh trong mạng có thể thuộc nhiều hơn 1 cộng đồng Mỗi đỉnh chỉ thuộc 1 cộng đồng duy nhất 2 Sự xuất hiện trong thực tế Nhiều Ít 3 Giải thuật tìm kiếm Phát hiện ra các cộng đồng chồng chéo các đỉnh Phát hiện ra các cộng đồng phân cấp các đỉnh Bảng 2.1 Sự mâu thuẫn của hai cấu trúc giữa chồng chéo và phân cấp 2.2 Các phƣơng pháp phát hiện cộng đồng 2.2.1 Ứng dụng: Nghiên cứu sự lây lan dịch bệnh và cách phòng chống, nhu cầu của khách hàng, quá trình trao đổi chất của tế bào, Trực quan hóa một mạng phức tạp. 12 2.2.2 Các loại giải thuật: Cho đồ thị G(E,V) với V là số đỉnh, E là số cạnh của đồ thị. a) Phân vùng đồ thị (Graph Partitioning). b) Phân cụm thứ bậc (Hierarchical). c) Tối ƣu hóa độ đo Modularity (Modularity Optimization). d) Phân cụm dựa trên quang phổ (Spectral clustering). 2.3 Các giải thuật tìm kiếm cộng đồng chồng chéo - Giải thuật tìm kiếm đồ thị clique (Clique Percolation Method - CPM). - Giải thuật phân vùng đồ thị dựa trên thông tin của cạnh (Link based algorithms). - Phân cụm mờ (Fuzzy). - Tối ƣu hóa và mở rộng hàm địa phƣơng (Local Exapansion and Optimization). - Giải thuật tìm kiếm cộng đồng dựa trên các tác tử và miền động (Agent and Dynamic based Algorithm). 2.4 Lựa chọn giải thuật tìm kiếm trong luận văn * Các bước thực hiện: Xét đồ thị G 𝑀,𝑁 vô hƣớng, không trọng số. Trong đó: 𝑀 là tổng số cạnh, 𝑁 là tổng số đỉnh của đồ thị. Ký hiệu: Đỉnh i, j ∈ đồ thị G; 𝑒𝑖𝑘 cạnh nối giữa đỉnh i và k; 𝑒𝑗𝑙 cạnh nối giữa đỉnh j và l Bước 1: Tính độ tƣơng tự giữa các cạnh: 𝑛+ 𝑖 = 𝑖,𝑘 𝑣à 𝑡ậ𝑝 đỉ𝑛ℎ 𝑘ề 𝑣ớ𝑖 𝑖 ; 𝑛+ 𝑗 = 𝑗, 𝑙 𝑣à 𝑡ậ𝑝 đỉ𝑛ℎ 𝑘ề 𝑣ớ𝑖 𝑗 ; Độ tƣơng tự giữa cạnh 𝑒𝑖𝑘 và 𝑒𝑗𝑙 là: S(𝑒𝑖𝑘 , 𝑒𝑗𝑙 )= |𝑛+ 𝑖 ∩𝑛+ 𝑗 | |𝑛+ 𝑖 ∪𝑛+ 𝑗 | 0 ,𝑘=𝑙 ,𝑘≠𝑙 13 Bước 2: Xây dựng ma trận độ tƣơng tự: Gọi 𝑀𝑠 là ma trận độ tƣơng tự, có kích thƣớc 𝑀 × 𝑀 Mỗi phần tử của ma tận 𝑀𝑠 sẽ đƣợc tính: 𝑀𝑠 (𝑒𝑖𝑘 , 𝑒𝑗𝑙 )= 𝑆(𝑒𝑖𝑘 , 𝑒𝑗𝑙 ) 0 𝑘=𝑙 𝑘≠𝑙 Bước 3: Thực hiện gom cụm đối với các cạnh: Sử dụng kỹ thuật gom cụm từ dƣới – lên (bottom-up) và phƣơng thức kết nối đơn để kết nối các cụm. Bước 4: Tìm ngƣỡng cắt cây lƣợc đồ: Cho trƣớc một ngƣỡng cắt cây lƣợc đồ, Gọi C tập các phân vùng cạnh đƣợc tạo ra từ lát cắt cây lƣợc đồ. Kí hiệu: C={𝐶1, 𝐶2, , 𝐶𝑙 , , 𝐶𝑙}, l ∈ 1,𝑘 ; 𝑚𝑙 = 𝐶𝑙 là số tổng lƣợng cạnh trong tập con 𝐶𝑙 ; 𝑛𝑙 = |∪𝑒𝑖𝑗 𝜖𝐶𝑙 {𝑖, 𝑗}| là số lƣợng đỉnh đƣợc kết nối bởi các cạnh ∈ Cl. 𝐷𝑙= 𝑚 𝑙−(𝑛 𝑙−1) 𝑛𝑙 𝑛 𝑙−1 2 –(𝑛 𝑙−1) 𝑛ế𝑢 𝑛𝑙 > 2 0 𝑛ế𝑢 𝑛𝑙 <= 2 Giá trị mật độ phân vùng D là giá trị trung bình của 𝐷𝑙 . Ngƣỡng cắt cây lƣợc đồ đƣợc tính: D = 2 |𝑀| 𝑚𝑙 𝑚 𝑙−(𝑛𝑙−1) (𝑛 𝑙−1)(𝑛𝑙−2) 𝑘 𝑙=1 Ngƣỡng cắt tốt nhất là ngƣỡng cắt mà giá trị mật độ phân vùng trung bình D đạt cực đại. * Ưu, nhược điểm của giải thuật: - Ưu điểm: tìm ra các cộng đồng chồng chéo. - Nhược điểm: gây phân tách cộng đồng, kết quả chƣa đảm bảo độ chính xác. 14 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 3.1. Phƣơng pháp nghiên cứu 3.1.1 Tính hiệu quả của đề xuất: Giải quyết vấn đề kích thƣớc dữ liệu lớn; Đƣa ra kết quả có độ tin cậy cao; Trích lọc thông tin có giá trị. 3.1.2 Định dạng dữ liệu đầu vào các độ đo: Nhật ký sự kiện định dạng XES, độ đo Handover of work, giải thuật phân vùng theo cạnh của Ahn et al., 2010 3.2 Giải pháp thực hiện 3.2.1 Đề xuất mô hình giải quyết: Hình 3.2 Mô hình áp dụng giải tìm kiếm cộng đồng vào KPQT (1) (2) (4) (3) (5) (6) (7) 15 3.2.2 Các bước thực hiện: Bƣớc 1. Thu thập dữ liệu: + 03 tệp định dạng XES tƣơng ứng với 03 chƣơng của cuốn sách Process Mining của tác giả Will M.P. Van der Alast trên + 01 tệp định dạng XES trên trang Bƣớc 2. Xử lý và làm sạch dữ liệu: Trong giới hạn luận văn, những thông tin không chứa thông tin ngƣời thực hiện hoạt động nên sẽ không đƣợc sử dụng để khai thác. Do đó, Tác giả đã loại bỏ loại thông tin này bằng phƣơng pháp thủ công. Bƣớc 3. Xây dựng ma trận mối quan hệ: Gọi i, j là những ngƣời tham gia vào quy trình; 𝑀ℎ là ma trận sinh ra sau khi sử dụng độ đo Handover of work; 𝑀ℎ 𝑖, 𝑗 là một phần tử của ma trận 𝑀ℎ . Ta có: 𝑀ℎ 𝑖, 𝑗 = số lần ngƣời i chuyển giao nhiệm vụ j và ngƣợc lại 0 ngƣời 𝑖 và j không có sự chuyển giao nhiệm vụ Bƣớc 4. Cách thức lƣu đồ thị trong tệp .txt: Hình 3.5 Định dạng dữ liệu .txt lưu đồ thị Bƣớc 5. Xây dựng ma trận kề: 16 Gọi 𝑀𝑎 là ma trận đỉnh kề đƣợc xây dựng danh sách cạnh của bƣớc 4. Trong đó: 𝑀𝑎 (i,j)= 1 0 𝑛ế𝑢 đỉ𝑛ℎ 𝑖 𝑘ề 𝑣ớ𝑖 đỉ𝑛ℎ 𝑗 𝑛𝑔ượ𝑐 𝑙ạ𝑖 Bƣớc 6. Áp dụng giải thuật tìm kiếm cộng đồng: + Xây dựng ma trận độ tƣơng tự giữa các cạnh. + Tiến hành gom cụm. + Tìm ngƣỡng cắt cây lƣợc đồ. Bƣớc 7. Đánh giá chất lƣợng cộng đồng: + Đối với cộng đồng cạnh: Giá trị mật độ phân vùng - 2 3 ≤D ≤1, giá trị D càng gần giá trị 1 thì các cộng đồng cạnh đƣợc phát hiện ra có chất lƣợng tốt, cộng đồng cạnh có giá trị D<=0, thƣờng không có giá trị để khai thác nên loại bỏ. Trong đó: D=1: cộng đồng đƣợc phát hiện là một đồ thị đầy đủ; D=0: mỗi cộng đồng là một cây; D<0: các đồ thị con trong cộng đồng không có sự kết nối; D= - 2 3 : là giá trị nhỏ nhất của một cộng đồng có hai cạnh không kết nối. + Đối với cộng đồng đỉnh: Những cộng đồng có giá trị khai thác là những cộng đồng không tầm thƣờng (Nontrivial community) [4], có chứa từ ba đỉnh trở lên. Sue 17 CHƢƠNG 4. KẾT QUẢ THỰC NGHIỆM, ĐÁNH GIÁ VÀ KẾT LUẬN 4.1 Công cụ, môi trƣờng thực nghiệm 4.1.2 Phần mềm và tập dữ liệu đầu vào: - Quá trình xây dựng chương trình: + Tải công cụ lập trình NetBeans IDE 8.0.2 và cài đặt. + Tạo chƣơng trình: Viết mã nguồn tiền xử lý tệp XES nhằm xây dựng mô hình MXH là đồ thị vô hƣớng, không trọng số. Xây dựng ma trận kề từ danh sách đỉnh, diễn dƣới dạng ma thƣa (Sparse Matrix) làm đầu vào cho chƣơng trình Link Clustering. 4.2 Chƣơng trình thực nghiệm Các thông tin đƣợc hiển thị trong chƣơng trình thực nghiệm: thông tin đầu vào của tệp .xes bao gồm số trƣờng hợp, số sự kiện, số ngƣời tham gia vào quy trình; hiển thị danh sách đỉnh kề bao gồm ký hiệu các đỉnh, số lƣợng đỉnh và cạnh; hiển thị danh sách các cộng đồng tìm thấy bao gồm danh sách các cộng đồng mà các đỉnh thuộc vào. 4.3 Kết quả thực nghiệm và đánh giá Sau khi cài đặt chƣơng trình, luận văn đã thực hiện thử nghiệm với 04 tệp .xes. Kết quả cụ thể nhƣ sau: Tệp dữ liệu Thông tin tệp XES Thông tin MXH Thông tin kết quả đầu ra Giá trị mật độ trun g bình T h ờ i g ian ch ạy (g iây ) S ố T rƣ ờ n g h ợ p S ố S ự k iện S ố N g ƣ ờ i th am g ia S ố Đ ỉn h S ố C ạn h S ố cộ n g đ ồ n g cạn h S ố cộ n g đ ồ n g đ ỉn h S ố cộ n g đ ồ n g ch ồ n g ch éo đ ỉn h S ố cộ n g đ ồ n g k h ô n g tầm th ƣ ờ n g S ố đ ỉn h ch ồ n g ch éo Chapter1.x 10 142 6 6 12 3 3 3 3 3 0.5 5 18 es Chapter5.x es 139 1 1507 8 8 8 14 4 4 4 2 4 0.36 7 Chapter6.x es 87 522 5 5 4 4 4 4 1 1 0 10 BPI2013.x es 1484 13288 442 442 781 576 576 576 499 767 0.035 13 Bảng 4.3 Đánh giá kết quả chương trình thực nghiệm Trong bảng kết quả, các khía cạnh cần quan tâm: - Về số người: Nếu số ngƣời tham gia vào quy trình thấp, kết quả phân cụm không có ý nghĩa nhiều trong thực tế. Đối với các tập dữ liệu thu đƣợc trên chuyên trang có số lƣợng ngƣời tham gia dƣới 10 ngƣời, do đó kết quả các cộng đồng chồng chéo không có giá trị khai thác cao trong phân tích và đánh giá sự chồng chéo trong nhiệm vụ. Khía cạnh có ý nghĩa là đánh giá mức độ quan trọng của từng ngƣời trong quy trình. - Về kích thước của MXH: Với một mạng có số cạnh ~ số đỉnh tức khả năng tƣơng tác giữa các đỉnh trong một mạng là thấp, các kỹ thuật khai phá sẽ sinh ra các kết quả không có giá trị về mặt thực tế. - Về kích thước các cộng đồng: Các cộng đồng có giá trị khai thác là những cộng đồng không tầm thƣờng có từ ba đỉnh trở lên [4], số lƣợng loại cộng đồng này phụ thuộc lớn vào mật độ kết nối trong MXH. Nếu MXH có mật độ kết nối thƣa, các đỉnh bị phân tách nên số lƣợng cộng đồng chứa 3 đỉnh trở lên là rất ít. - Số lượng đỉnh chồng chéo: Một đỉnh thuộc vào nhiều cộng đồng không tầm thƣờng thể hiện tầm quan 19 trọng của đỉnh đó trong đồ thị hay của cá nhân đó đối với các hoạt động trong quy trình. Một đồ thị có số lƣợng đỉnh chồng chéo thuộc các cộng đồng không tầm thƣờng lớn, khả năng xảy ra sự chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình lớn. - Mật độ phân vùng trung bình: Trong luận văn, Tác giả sử dụng giá trị mật độ phân vùng trung bình D để đánh giá chất lƣợng cộng đồng cạnh. Chất lƣợng các cộng đồng cạnh càng tốt, thể hiện sự phân tách của giải thuât là tối ƣu tƣơng ứng với các cộng đồng cạnh này là các cộng đồng đỉnh có sự chồng chéo lớn. Các đánh giá cụ thể: Tệp dữ liệu Đánh giá Chapter1.xes - Giá trị 𝐷 ≥ 0.5 → Chất lƣợng phân tách tốt, các cộng đồng cạnh có sự kết nối mạnh, tƣơng ứng là cộng đồng đỉnh có sự chồng chéo lớn. - Số lƣợng đỉnh = 1 2 số lƣợng cạnh → Mật độ kết nối dày. - Số lƣợng cộng đồng không tầm thƣờng chiếm 100% - Số lƣợng ngƣời tham gia là 6 < 10 ngƣời → ít  Có khả năng chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình cao. Tuy nhiên, do số lƣợng ngƣời tham gia ít, nên kết quả chồng chéo này không có giá trị khai thác cao trong thực tế, mà kết quả chỉ phù hợp với việc nhận xét tầm quan trọng của cá nhân đối với quy trình. Chapter5.xes - Giá trị 0 <D< 0.5 → Các cộng đồng cạnh có sự kết nối ở mức trung bình, sự chồng chéo xảy ra tại một số cộng đồng đỉnh đƣợc tìm ra. - Số lƣợng đỉnh ~ 1 2 số lƣợng cạnh → Mật độ kết nối dày. - Số lƣợng cộng đồng không tầm thƣờng chiếm 50% - Số lƣợng ngƣời tham gia là 8 < 10 ngƣời → ít  Có khả năng có sự chồng chéo nhiệm vụ của một số ngƣời tham gia vào quy trình. Tuy nhiên, do số lƣợng 20 ngƣời tham gia ít, số lƣợng cộng đồng không tầm thƣờng chỉ chiếm phần nửa nên kết quả này phù hợp với đánh giá tầm quan trọng của các cá nhân. Chapter6.xes - Giá trị 𝐷 = 0 → Chất lƣợng phân tách các cộng đồng thấp, do vậy mật độ kết nối giữa các đỉnh trong đồ thị là thấp. Các cộng đồng đƣợc tìm ra không có sự kết nối, độ chồng chéo các đỉnh là thấp. - Số lƣợng đỉnh xấp xỉ số lƣợng cạnh→ Mật độ kết nối giữa các đỉnh thƣa. - Số lƣợng cộng đồng không tầm thƣờng chiếm 33%  Không có thể có sự chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình. Kết quả chỉ phục vụ mục đích tìm ra các nhân nào có tầm quan trọng trong quy trình BPI2013.xes - Giá trị 𝐷~0 → Các cộng đồng cạnh gần nhƣ không có sự kết nối, do vậy các cộng đồng cạnh tƣơng ứng có độ chồng chéo thấp. - Số lƣợng đỉnh ~ ½ số lƣợng cạnh → Mật độ kết nối các đỉnh thƣa. - Số lƣợng cộng đồng không tầm thƣờng chiếm 50%  Không có thể có sự chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình. Kết quả chỉ phục vụ mục đích tìm ra các nhân nào có tầm quan trọng trong quy trình. Bảng 4.4 Đánh giá chất lượng các cộng đồng 21 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN TƢƠNG LAI 1. Kết luận - Tổng kết các kết quả nghiên cứu của các nhà khoa học trên thế giới về lĩnh vực KPQT và các giải thuật tìm kiếm cộng đồng trong MXH. Những nghiên cứu này tạo nền tảng cơ sở cho sự lựa chọn giải thuật tìm kiếm cộng cộng đồng chồng chéo áp dụng để giải quyết bài toán thuộc khía cạnh tổ chức. - Phát biểu bài toán và đề xuất mô hình giải quyết bài toán. Đề xuất giúp tìm ra các nhóm ngƣời có sự chồng chéo nhiệm vụ khi tham gia vào quy trình. - Xây dựng thành công chƣơng trình thực nghiệm dựa trên mô hình đề xuất giải quyết trong luận văn. 2. Hƣớng phát triển tƣơng lai Trong tƣơng lai, Tác giả sẽ tiếp tục nghiên cứu và giải quyết những thách thức: - Đối với dữ liệu đầu vào: Tác giả sẽ tiếp tục thu thập dữ liệu nhật ký sự kiện trong thực tế, áp dụng các công cụ tiền xử lý dữ liệu để đƣa dữ liệu về dạng chuẩn, làm đầu vào cho các giải thuật. - Đối với loại độ đo hỗ trợ biểu diễn cấu trúc MXH: Mở rộng kỹ thuật xây dựng MXH dƣới dạng đồ thị có hƣớng, có trọng số bằng cách sử dụng các độ đo khác nhau. - Đối với giải thuật tìm kiếm: Tác giả sẽ tiếp tục nghiên giải thuật cải tiến của giải thuật Phân vùng theo cạnh và các giải thuật khác, nhằm đánh giá các loại giải thuật phù hợp với từng loại mô hình MXH . - Đối với chức năng của phần mềm: Chƣơng trình thực nghiệm chỉ dừng ở việc xử lý tệp dữ liệu sự kiện định dạng .xes chứa khoảng hơn 1000 trƣờng hợp và 7000 sự kiện. Do đo, Tác giả sẽ nghiên cứu, mở rộng các chức năng của chƣơng trình để đáp ứng với tệp dữ liệu có kích thƣớc lớn hơn. 22 TÀI LIỆU THAM KHẢO [1] Wil M. P. van der Aalst. (2011), Process Mining: Discovery, Conformance and Enhancement of Business Processes. Springer, Berlin, Heidelberg. [2] Minseok Song and Wil M. P. van der Aalst. (2008), Towards comprehensive support for organizational mining. Decision Support Systems, pp. 300–317. [3] G. Palla, I. Derényi, I. Farkas, and T. Vicsek. (2005), Uncovering the overlapping community structure of complex networks in nature and society. Nature, vol. 435, no. 7043. [4] Ahn Y.-Y., Bargrow, J. P., and Lehmann, S. (2010), Link communities reveal multiscale complexity in networks. Nature 466, pp. 761–764. [5] Karsten Steinhaeuser and Nitesh v. Chawla. Community detection in large real world networks. [6] S. Gregory. (2009), Finding overlapping communities using disjoint community detection algorithms, in Complex Networks. Springer, pp. 47–61. [7] J. Xie, S. Kelley, and B. K. Szymanski. (2011), Overlapping community detection in networks: the state of the art and comparative study. arXiv preprint arXiv: 1110.5813. [8] Wil M.P. Van der Aalst, W., Weijters, A., and Maruster, L. (2004), Workflow Mining: Discovering Process Models from Event Logs. IEEE Transactions on Knowledge and Data Engineering, Vol. 16(9), pp. 1128– 1142. [9] Wil M.P. van der Aalst., Reijers, H.A., Song, M. (2005), Discovering Social Networks from Event Logs. Computer Supported Cooperative Work, Vol. 14 No. 6, pp. 549–593. [10] Borko Furht. (2010), Handbook of Social Network Technologies and Applications. Springer, 1st edition. [11] Girvan, M., & Newman, M. E. (2002), Community structure in social and biological networks. In Proceedings of the National Academy of Sciences, 99(12), pp. 7821- 7826. 23 [12] M. Bramer. (2007), Principles of Data Mining. Springer, Berlin. [13] J. Nakatumba and Wil M.P. van der Aalst. (2010), Analyzing resource behavior using process mining. In BPMW'09, vol. 43 of LNBIP, pp. 69-80. Springer. [14] Wil M.P. Van der Aalst and Minseok Song. (2004), Mining social networks: Uncovering interaction patterns in business processes. In Business Process Management, pp. 244–260. Springer. [15] Chen, Z. S., Kalashnikov, D. V. and Mehrotra, S. Exploiting context analysis for combining multiple entity resolution systems. (2009), In Proceedings of the 2009 ACM International Conference on Management of Data (SIGMOD'09). [16] Reza Zafarani, Mohammad Ali Abbasi, Huan Liu. (2014), Social Media Mining: An Introduction. Cambridge University Press. [17] Huang L, Wang G, Wang Y, Blanzieri E, Su C. (2013), Link Clustering with Extended Link Similarity and EQ Evaluation Division. [18] W.M.P. van der Aalst, B.F. van Dongen, J. Herbst, L. Maruster, G. Schimm, and A.J.M.M. Weijters. (2003), Workflow Mining: A Survey of Issues and Approaches. Data and Knowledge Engineering, pp. 237– 267. [19] Mini Singh ahuja and Jatinder singh. (2014), Future prospects in community detection. Vol. 4, Issue 5, pp. 37-48. [20] DR Ferreira, C Alves. (2012), Discovering User Communities in Large Event Logs. 7th International Workshop on Business Process Intelligence, pp. 123-134. [21] Zbigniew Paszkiewicz and Wily Picard. (2013), Analysis of the Volvo IT Incident and Problem Handling Processes using Process Mining and Social Network Analysis. [22] Jaewon Yang, Jure Leskovec. (2013), Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach. 24 [23] Reichert, M. (2012), Visualizing Large Business Process Models: Challenges, Techniques, Applications. In 1st Int’l Workshop on Theory and Applications of Process Visualization, Tallin. [24] Stanley W., Katherine. (1999), Social Network Analysis: Methods and Applications. ISBN 052137078. [25] Noel M. T., Micheal L. T and Charles (1979), Social Network Analysis for Organizations. The Academy of Management Review. Vol. 4. [26] Cook, J. E., and Wolf, A. L. (1998), Discovering models of software processes from event- based data. ACM Trans. Softw. Eng. Methodol. [27] Herbst, J., and Karagiannis, D. (1998), Integrating Machine Learning and Workflow Management to Support Acquisition and Adaptation of Workflow Models. In Proceedings 9th International Workshop on Database and Expert Systems Applications (DEXA’98), pp. 745–752. [28] Song, M., and Van der Aalst. (2008), Towards comprehensive Support for organizational mining. Decision Support Systems. [29] Weske, Mathias. (2012),Business process management concepts, languages, architectures, Berlin; New York: Springer. [30] J.L. Moreno.(1934), Who Shall Survive?Nervous and Mental Disease Publishing Company,Washington, DC. [31] Becker, J., Delfmann, P., Eggert, M., and Schwittay. (2012a),. Generalizability and Applicability of Model-Based Business Process Compliance- CheckingApproaches – A State-of-the-Art Analysis and Research Roadmap.BuR Business Research (5:2), pp. 221–247. [32] Grigori, D., Casati, F., Castellanos, M., Dayal, U., Sayal, M., and Shan, M. C. (2004), Business Process Intelligence. Computers in Industry, 53(3). [33] Ingvaldsen, J. E., Gulla, J. A., Hegle, A., and Prange A. (2005), Empirical Business Models. 17th 25 Conference on Advanced Information Systems Engineering, Porto, Portugal. [34] Steve Gregory. (2007), An Algorithm to Find Overlapping Community Structure in Networks. [35] Raghavan UN, Albert R, Kumara S. (2007), Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks. [36] Wil M.P Van der Aalst, W. M. P., Andriansyah, A., Alves de Medeiros, A. K., Arcieri, F., Baier, T., Blickle, T., Bose, J. C., Van den Brand, P., Brandtjen, R., and Buijs, J. (2012) Process mining manifesto. In BPM 2011 Workshops Proceedings, pp. 169–194.