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

còn gọi là phân cụm từ dƣới – lên, độ phức tạp của giải thuật O(n2log(n)). Các bƣớc thực hiện: + Mỗi đỉnh trong đồ thị đƣợc coi là một cụm đơn. 26 + Tìm các cặp cụm có khoảng cách ngắn nhất (độ tƣơng sự lớn nhất) và tập hợp chúng lại thành một cụm. Tính khoảng cách (độ tƣơng tự) giữa cụm mới với các cụm còn lại. + Lặp lại hai bƣớc trên cho đến khi tất các đỉnh thuộc một cụm duy nhất. Để tính khoảng cách giữa các cụm có nhiều cách khác nhau, có một số phƣơng pháp phổ biến: Kí hiệu: A, B là hai cụm bất kỳ; a, b lần lƣợt là các phần tử thuộc cụm A, B d(a,b) là khoảng cách từ phần tử a tới phần tử b. TT Tên phƣơng pháp Cách tính Tiêu chí Kết nối 1 Phƣơng thức kết nối đơn (Single Linkage Method) - Tên gọi khác: Phƣơng pháp láng giềng gần nhất Min 𝑑 𝑎, 𝑏 :𝑎 𝜖 𝐴, 𝑏 𝜖 𝐵 Độ tƣơng tự lớn nhất hay Khoảng cách ngắn nhất 2 Phƣơng thức kết nối toàn bộ (Complete Linkage Method) - Tên gọi khác: Phƣơng pháp láng giềng xa nhất Max 𝑑 𝑎, 𝑏 :𝑎 𝜖 𝐴, 𝑏 𝜖 𝐵 Độ tƣơng tự nhỏ nhất hay Khoảng cách xa nhất 3 Phƣơng thức kết nối trung bình (Average Linkage Method) - Tên gọi khác: UPGMA 1 𝐴 |𝐵| 𝑑(𝑎, 𝑏) 𝑏∈𝐵𝑎∈𝐴 Độ tƣơng tự trung bình hay khoảng cách trung bình Bảng 2.2 Các phương pháp tính khoảng cách hai cụm Hình 2.2 Các phương pháp phân cụm thứ bậc 27 - Phân cụm thứ bậc phân chia (Divisive): Hay còn gọi là phân cụm từ trên - xuống, độ phức tạp của giải thuật là O(2n). Giải thuật đƣợc đƣa ra bởi hai nhà khoa học Girvan và Newman vào năm 2002. Bắt đầu một mạng, tiến hành chia nhỏ mạng thành mạng nhỏ hơn. Quá trình này sẽ kết thúc mỗi cộng đồng chỉ chứa một đỉnh duy nhất. c) Tối ưu hóa độ đo Modularity (Modularity Optimization): Độ đo modularity là một độ đo đánh giá chất lƣợng các cộng đồng đƣợc phát hiện và cách cải thiện chất lƣợng các cộng đồng này. Năm 2006, Newman và Girvan đã đƣa ra một tiêu chí để dừng việc phân tách của các giải thuật tìm kiếm cộng đồng là độ đo modularity Q. Để xác định độ đo Q, ta so sánh số lƣợng cạnh trong đồ thị đã cho so với số lƣợng cạnh trong đồ thị ngẫu nhiên. Độ đo này sử dụng để đánh giá chất lƣợng các phân vùng, đƣợc tìm thấy từ các giải thuật tìm kiếm khác nhau. Giá trị Q càng lớn, chất lƣợng phân vùng đƣợc đánh giá là tốt. Tối ƣu hóa độ đo Q là một bài toán khó (Brandes et al., 2008), do rất khó có thể tìm giá trị Q tối ƣu. Có một số kỹ thuật tìm giá trị Q tối ƣu: + Giải thuật tìm kiếm tham lam (Greedy Optimization): Năm 2004, Newman đã đƣa ra giải thuật cực đại hóa độ đo modularity bằng phƣơng pháp tìm kiếm tham lam. Cùng năm đó, Clauset et al. đã đề xuất cải tiến các toán tử trong giải thuật của Newman, nhằm cải thiện thời gian chạy của giải thuật. Danon et al. đã chuẩn hóa các biến độ đo Modularity bằng cách sát nhập hai cộng đồng bằng cách sử dụng lát cắt ngẫu nhiên của một trong hai cộng đồng vào năm 2006. Hai năm sau đó, Blondel et al. đã áp dụng giải thuật tìm kiếm tham lam đối với đồ thị có trọng số. + Giải thuật theo hạt mô phỏng (Simulated Annealing): Đây là phƣơng pháp chỉ sử dụng với đồ thị có kích thƣớc nhỏ. Giải thuật đƣợc coi nhƣ một hàm xác suất, tiến hành lựa chọn một phân vùng trong đồ thị, tìm giá trị tối ƣu độ đo Modularity trong những phân vùng đó. Năm 2004, giải thuật đƣợc đƣa ra bởi Guimera et al. Ý tƣởng của giải thuật là bắt đầu tại một phân vùng đƣợc lựa chọn ngẫu nhiên. Sau đó di chuyển các đỉnh vào thành một cụm hoặc các cụm khác nhau. Tiếp tục việc sát nhập và phân tách các cụm, tính độ đo Modularity. Nếu cụm nào có độ đo Modularity tăng thì giữ lại, nếu giảm tiếp tục quá trình phân tách và sát nhập. + Tối ƣu hóa mở rộng (External optimization): Là giải thuật tìm kiếm heuristic đƣợc đƣa ra bởi Boettcher và Pecres vào năm 2001. Kết quả của giải thuật tìm thấy giá trị độ đo modularity tối ƣu và cải thiện thời gian chay của chƣơng trình. Năm 2005, Duch và Arenes tìm ra giá trị modularity của một đỉnh 28 dựa trên việc tối ƣu hóa biến cục bộ. Độ phức tạp của giải thuật này là O (n2 logn). Các bƣớc giải thuật: Bƣớc 1: Bắt đầu một phân vùng ngẫu nhiên nằm giữa hai cụm. Bƣớc 2: Sử dụng hàm Fitness để đánh giá độ tốt của một đỉnh. Đỉnh có độ fitness thấp nhất sẽ đƣợc chuyển sang cộng đồng khác. Bƣớc 3: Giá trị Fitness đƣợc tính lại với phân vùng khác. Bƣớc 4: Thuật toán sẽ dừng lại nếu độ đo Modularity của các cụm không đƣợc cải thiện hơn. d) Phân cụm dựa trên quang phổ (Spectral clustering): là kỹ thuật phân vùng dựa trên giá trị các phần tử của của ma trận. Sử dụng kỹ thuật phân cụm k- mean để phân chia đồ thị. Tuy nhiên, phƣơng pháp này có thể phân tách các đỉnh mà không cần sử dụng giải thuật k-mean. 2.3 Các giải thuật tìm kiếm cộng đồng chồng chéo Hiện tƣợng các cộng đồng chồng chéo đƣợc nghiên cứu lần đầu tiên bởi nhóm nghiên cứu Palla et al. vào năm 2005. Ông đã đề xuất phƣơng pháp tìm kiếm các đồ thị Clique, là một đồ thị đầy đủ. Phát hiện cộng đồng chồng chéo là một bài toán NP - khó và có nhiều phƣơng pháp cho phép giải quyết những vấn đề này nhƣng hầu hết không đạt hiệu quả nhƣ mong đợi. Một số 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): phƣơng pháp này đƣợc đƣa ra bởi Palla et al. vào năm 2005. Nhóm tác giả đã mở rộng các vấn đề của Girvan Newman là tìm các cộng đồng chồng chéo, trong đó một đỉnh có thể thuộc một hoặc nhiều cộng đồng. Ý tƣởng của giải thuật là mỗi cộng đồng đƣợc hình thành từ các đồ thị Clique và đồ thị ban đầu chứa một số lƣợng lớn đồ thị Clique. Khái niệm đồ thị k-clique đƣợc sử dụng để chỉ ra một đồ thị đầy đủ với k đỉnh. Hai đồ thị k-clique kề nhau có chung (k-1) đỉnh. Palla và các cộng sự đã thiết kế gói phần mềm Cfinder thực thi giải thuật này. Năm 2007, Palla et al. đã đƣa ra định nghĩa đồ thị k-clique có hƣớng và đề xuất giải pháp giải quyết những giới hạn của giải thuật CPM, gọi là CPMd (Clique Percolation Method with directed cliques). Cùng năm đó, Farkas et al. đã mở rộng giải thuật CPM đối với đồ thị có trọng số, giải thuật CPMw. Năm 2008, Kumpula et al. đã đƣa ra giải thuật phát hiện cộng đồng nhanh đƣợc gọi là SCP (Sequential Clique Percolation Method) đối với các đồ thị có trọng số và không trọng số, trong đó kích thƣớc đồ thị clique đƣợc cho trƣớc. Thời gian chạy của giải thuật SCP nhanh hơn CPM. Giải thuật CPM: 29 Đầu vào: Đồ thị G gồm N đỉnh, đồ thị Clique có k đỉnh. Đầu ra: Cấu trúc cộng đồng. Bƣớc 1: Tìm tất cả các đồ thị k-clique trong đồ thị G. Bƣớc 2: Xây dựng đồ thị Gc là đồ thị mà mỗi đỉnh đại diện cho một k- clique trong đồ thị ban đầu. Hai k-clique có cạnh kết nối với nhau nếu chúng có chung (k-1) đỉnh. Bƣớc 3: Mỗi đồ thị Clique đƣợc coi là một cộng đồng trong mạng. - Giải thuật phân vùng đồ thị dựa trên thông tin của cạnh (Link based algorithms): Ý tƣởng của giải thuật này là phân vùng các cạnh mà không phải là các đỉnh. Năm 2010, Ahn et al. đã đƣa ra khái niệm “cộng đồng cạnh” và giải quyết thành công mâu thuẫn giữa cấu trúc chồng chéo và phân cấp. Cùng năm đó, Evan et al. đã mở rộng giải thuật này bằng cách sử dụng các đồ thị Clique. Phƣơng pháp này coi mỗi đồ thị Clique trong đồ thị ban đầu là một đỉnh trong đồ thị đƣờng, các cạnh nối giữa các đồ thị clique này đƣợc đánh trọng số. Tuy nhiên, nhà khoa học Fortunato đã đƣa ra quan điểm rằng không có sự đảm bảo chính xác rằng đồ thị đƣờng cung cấp các cộng đồng cạnh có chất lƣợng cao hơn các cộng đồng đỉnh. - Phân cụm mờ (Fuzzy): Là phƣơng pháp phân cụm mà cho phép mỗi đỉnh thuộc về hai cụm hoặc nhiều cụm thông qua bậc thành viên. K-mean là thuật toán phân cụm rõ, c-mean là thuật toán phân cụm mờ. Đối với các cộng đồng chồng chéo, phƣơng pháp này cho phép mỗi đỉnh có thể thuộc nhiều hơn một cộng đồng nhƣng tầm ảnh hƣởng của đỉnh này với mỗi cộng đồng mà nó thuộc vào là khác nhau. Năm 2011, Gregory đã đánh giá tầm ảnh hƣởng của mỗi đỉnh trong mỗi cộng đồng mà đỉnh đó thuộc vào bằng hệ số sở hữu của mỗi cộng đồng. Năm 2007, Zhang et al. đã phát triển phƣơng pháp phân cụm dựa trên quang phổ, phân cụm mờ và tối ƣu hóa hàm đánh giá chất lƣợng. Một năm sau đó, Nepusz et al. đã đƣa ra phƣơng pháp cho phép mỗi đỉnh có thể thuộc vào nhiều cộng đồng tại cùng một thời gian. Năm 2009, Wang et al. đã áp dụng phƣơng pháp phát hiện các cộng đồng không kết nối vào giải thuật tối ƣu hóa hàm địa phƣơng. Gần đây, Psorakis et al. đã đƣa ra đề xuất phát hiện cộng đồng dựa vào ma trận với các phần tử giá trị không âm để trích lọc ra các cộng đồng chồng chéo. - Tối ưu hóa và mở rộng hàm địa phương (Local Exapansion and Optimization): Năm 2007, Gregory S đã đề xuất giải thuật CONGA (Cluster- Overlap Newman Girvan Algorithm), là sự mở rộng của giải thuật GN của 30 Girvan và Newman. Phƣơng pháp chia các đỉnh thành nhiều phần khác nhau, để một phần trong các đỉnh đã chia đó xuất hiện trong các cộng đồng con. Các bƣớc của giải thuật CONGA: Đầu vào: Đồ thị G gồm N đỉnh, M cạnh. Đầu ra: Các cộng đồng đỉnh. Bƣớc 1: Tính độ trung gian của các cạnh trong mạng. Bƣớc 2: Hủy bỏ các cạnh có độ trung gian cao nhất. Bƣớc 3: Tính lại độ trung gian cho tất cả các cạnh bị ảnh hƣởng theo các cạnh đã loại bỏ. Bƣớc 4: Lặp lại bƣớc 2 cho đến khi không còn cạnh trung gian nữa. - 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): Thuật toán lan truyền nhãn là phƣơng pháp dựa trên các tác tử, trong đó nhãn của các nút sẽ lan truyền tới các nút xung quanh theo độ gần của chúng. Đây là phƣơng pháp tìm kiếm nhanh, đƣợc sử dụng để tìm các cộng đồng không kết nối và chồng chéo. Trong quá trình lan truyền, cố định các nhãn trên các miền dữ liệu đã đƣợc gán nhãn. Năm 2007, giải thuật LPA (Label Progation Algorithm) đã đƣợc đề xuất bởi Raghavan et al., nhằm phát hiện các cộng đồng không kết nối trong các mạng có quy mô lớn. Giải thuật đƣợc mở rộng bởi Gregory vào năm 2010, trong đó tác giả đã đề xuất một đỉnh có thể sở hữu nhiều nhãn hơn. Giải thuật này gọi là COPRA (Community Overlap Label Propagation Algorithm). Các bƣớc giải thuật LPA: Đầu vào: Đồ thị G gồm N đỉnh, M cạnh. Đầu ra: Các cộng đồng đỉnh. Bƣớc 1: Mỗi đỉnh đƣợc gán một nhãn duy nhất. Bƣớc 2: Lựa chọn ngẫu nhiên đỉnh kề với đỉnh đang xét, gán nhãn giống đỉnh đang xét. Quá trình này sẽ đƣợc lặp lại nhiều lần. Bƣớc 3: Tất cả các đỉnh có nhãn giống nhau thuộc cùng một đỉnh. 2.4 Lựa chọn giải thuật tìm kiếm Trong luận văn, Tác giả lựa chọn giải thuật Phân vùng theo cạnh (Link Clustering) của Ahn et al. để áp dụng vào giải quyết bài toán khía cạnh tổ chức đã nêu tại Chƣơng 1. Năm 2009, hai nhà khoa học Evans và Lambiotte lần đầu đề xuất sử dụng đồ thị đƣờng – đây là đồ thị mà mỗi đỉnh là đại diện của một cạnh của đồ thị ban đầu (Wikipedia), phƣơng pháp này giúp phát hiện các cộng 31 đồng chồng chéo bằng cách phân cụm thứ bậc dựa trên các cạnh của đồ thị, mà không phải là các đỉnh. Một năm sau đó, Ahn et al. đã thực hiện ý tƣởng này bằng cách sử dụng độ tƣơng tự giữa hai cạnh kề và đƣa ra khái niệm cộng đồng cạnh. Ahn et al. đã viết: “Trong thực tế, phần lớn các mạng chứa các cộng đồng chồng chéo nhau, trong đó một hoặc tất cả các đỉnh có thể thuộc sở hữu của nhiều cộng đồng, dẫn đến cấu trúc phân cấp các đỉnh không thể mô tả đƣợc sự chồng chéo này” [4]. * Ý tưởng của giải thuật: Tính độ tƣơng tự giữa cặp cạnh trong đồ thị, từ đó xây dựng ma trận độ tƣơng tự. Tiến hành gom cụm bằng cách sử dụng kỹ thuật phân cụm thứ bậc từ dƣới – lên và phƣơng thức kết nối đơn đối với ma trận này. Quá trình gom cụm sẽ đƣợc lƣu lại, hình thành cây lƣợc đồ (Dendogram). Tìm ngƣỡng cắt cây lƣợc đồ mà tại đó giá trị mật độ phân vùng trung bình của tất cả các phân vùng đạt kết quả cực đại. Lựa chọn giá trị ngƣỡng cắt đó và thực hiện cắt cây lƣợc đồ. Kết quả cuối cùng sinh ra một tập các cộng đồng cạnh và các cộng đồng đỉnh tƣơng ứng. Nhƣ vậy, các cộng đồng cạnh có cấu trúc phân cấp, cộng đồng đỉnh có cấu trúc chồng chéo. Ý tƣởng này giúp giải quyết mâu thuẫn giữa hai loại cấu trúc cộng đồng điển hình này. Đầu vào: Đồ thị vô hƣớng, không trọng số Đầu ra: Các cộng đồng cạnh, và các cộng đồng đỉnh chồng chéo tƣơng ứng. * 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 ,𝑘=𝑙 ,𝑘≠𝑙 Bước 2: Xây dựng ma trận độ tương tự: Gọi 𝑀𝑠 là ma trận độ tƣơng tự, là ma trận vuông có kích thƣớc 𝑀 × 𝑀 Mỗi phần tử của ma tận 𝑀𝑠 sẽ đƣợc tính: 32 𝑀𝑠 (𝑒𝑖𝑘 , 𝑒𝑗𝑙 )= 𝑆(𝑒𝑖𝑘 , 𝑒𝑗𝑙 ) 0 𝑘=𝑙 𝑘≠𝑙 Bước 3: Thực hiện gom cụm: 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. Lịch sử của quá trình gom cụm tạo thành một cây lƣợc đồ (dendogram), trong đó mỗi cạnh là một lá của cây. 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 đồ, sau khi thực hiện cắt với ngƣỡng này ta thu đƣợc một tập các phân vùng. Tại mỗi ngƣỡng cho trƣớc, sau khi cắt sinh ra một tập các cộng đồng cạnh. Gọi C tập các phân vùng cạnh đƣợc tạo ra từ ngƣỡng cắt cho trƣớc. Tùy theo phƣơng thức sử dụng phân cụm khác nhau, kết quả tập C sẽ có giá trị khác nhau. Tổng số cạnh trong mỗi phân vùng ∈ 𝐶 luôn < 𝑀 . Kí hiệu: 𝐶 ={𝐶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 các cạnh ∈ Cl. 𝐷𝑙= 𝑚 𝑙−(𝑛 𝑙−1) 𝑛𝑙 𝑛 𝑙−1 2 –(𝑛 𝑙−1) 0 𝑛 𝑙>2 𝑛 𝑙≤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 Giá trị mật độ phân vùng D là giá trị giúp xác định ngƣỡng cắt tốt nhất để cắt cây lƣơc đồ. 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. Với ngƣỡng cắt này, kết quả tìm ra các cộng đồng cạnh có cấu trúc không chồng chéo, tƣơng ứng là các cộng đồng đỉnh có thể có cấu trúc chồng chéo tùy theo sự kết nối mạnh hay yếu của các cộng đồng cạnh. * Ưu, nhược điểm của giải thuật: - Ưu điểm: Tìm ra các cộng đồng cạnh có cấu trúc phân cấp, cộng đồng đỉnh tƣơng ứng có cấu trúc chồng chéo. Giải quyết đƣợc sự mâu thuẫn giữa hai loại cấu trúc phân cấp và chồng chéo. - Nhược điểm: Do việc tìm kiếm cộng đồng chủ yếu dựa trên độ tƣơng tự giữa các cạnh kề, có chung một đỉnh và bỏ qua độ tƣơng tự các cạnh không kề nhau. Nhƣ vậy, một lƣợng lớn các thông tin bị mất gây ảnh hƣởng đến kết quả phân tích cộng đồng. 33 + Hạn chế của độ tương tự: Ta có: S 𝑒𝑎𝑏 , 𝑒𝑐𝑑 = 0 => Cạnh eab và ecd không thuộc một cộng đồng. (1) S 𝑒𝑎𝑏 , 𝑒𝑕𝑓 = 0 => Cạnh eab và ehf không thuộc một cộng đồng. (2) Thực tế, cạnh 𝑒𝑎𝑏 và 𝑒𝑐𝑑 tuy thuộc cùng cộng đồng phải có giá trị độ tƣơng tự cao hơn cạnh 𝑒𝑎𝑏 và 𝑒𝑕𝑓 . Từ (1) và (2), ta có thể thấy rằng: nếu dựa vào độ tƣơng tự để phân chia cộng đồng đối với tất cả các loại cấu trúc đồ thị có thể tạo ra những kết quả không chính xác, gây chia chỏ cộng đồng. Hình 2.3 Đồ thị minh họa nhược điểm của giải thuật + Hạn chế của mật độ phân vùng: Ta có hai ngƣỡng cắt: TT Các phân vùng Mật độ phân vùng trung bình 1 P1:𝑒𝑎𝑏 , 𝑒𝑏𝑐 , 𝑒𝑎𝑐 P2: 𝑒𝑎𝑑 , 𝑒𝑐𝑑 P3: 𝑒𝑕𝑓 D= 2 6 3 ∗ 1 + 0 + 0 = 1 2 P1: 𝑒𝑎𝑏 , 𝑒𝑏𝑐 , 𝑒𝑎𝑐 , 𝑒𝑎𝑑 , 𝑒𝑐𝑑 P2: 𝑒𝑕𝑓 D= 1 6 5 ∗ 2 3 + 0 = 0.56 Bảng 3.3 Tính mật độ phân vùng Nếu chia đồ thị Hình 2.3 thành 3 cộng đồng con, giá trị mật độ phân vùng trung bình =1, nếu hai cộng đồng thì giá trị mật độ trung bình = 0.56 <1 (Cách tính như trong Bảng 3.3). Thực tế, hai tam giác này thuộc cùng một cộng đồng. Do đó, mật độ phân vùng chƣa phản ánh đúng bản chất các cộng đồng trong một mạng. Nếu dựa trên công thức tính mật độ phân vùng 𝐷𝑙 ở Chƣơng này, ta thấy tử số 𝑚𝑙 − (𝑛𝑙 − 1) tăng chậm hơn so với mẫu số [ 𝑛 𝑙 𝑛 𝑙−1 2 – (𝑛𝑙 − 1)]→ điều này làm cho giá trị mật độ phân vùng nhỏ đi, việc phân tách các cộng đồng diễn ra không hiệu quả. a b c d f h 34 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 Thách thức lớn nhất đối với các kỹ thuật khai phá thuộc khía cạnh tổ chức liên quan đến khối lƣợng và chất lƣợng dữ liệu lƣu trong nhật ký sự kiện bao gồm dung lƣợng dữ liệu lớn, lƣợng thông tin không giá trị nhiều, . Việc trích lọc những thông tin có giá trị trở lên khó khăn, tiêu tốn thời gian, sức lực và chi phí. Thậm chí, chi phí trích lọc thông tin có giá trị còn lớn hơn nhiều doanh thu của các doanh nghiệp có quy mô nhỏ. Từ lâu, chiến lƣợc “chia để trị” đã trở thành phƣơng pháp đƣợc áp dụng phổ biến trong các bài toán phức tạp. Việc chia vấn đề lớn thành các vấn đề nhỏ để giải quyết là phƣơng pháp mang lại hiệu quả cao. Tuy nhiên, việc áp dụng nhƣ thế nào, hiệu quả việc áp dụng này đối với từng bài toán đã và đang đƣợc các nhà khoa học quan tâm và nghiên cứu. Trong giới hạn luận văn, tác giả sử dụng chiến lƣợc này bằng cách đề xuất á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 nhằm tìm ra sự chồng nhiệm vụ giữa những ngƣời tham gia vào quy trình. Đề xuất trong luận văn mang lại những hiệu quả, cụ thể nhƣ: - Giải quyết vấn đề kích thước dữ liệu lớn: Luận văn sử dụng các kỹ thuật phát hiện MXH từ tập nhật ký sự có kích thƣớc dữ liệu lớn. Mỗi tập dữ liệu có thể chứa vài trăm trƣờng hợp, hàng nghìn sự kiện với vài trăm ngƣời tham gia thực hiện nhiệm vụ trong một quy trình lớn. Tuy nhiên, đề xuất này chỉ tập trung vào những ngƣời tham gia vào các hoạt động của quy trình và sự tƣơng tác của họ. Mô hình hóa một vấn đề là bƣớc đầu tiên, quan trọng của một bài toán. MXH biểu diễn ngƣời, mối quan hệ bằng các khái niệm hình học, giúp trực quan hóa các mối quan hệ này. - Đưa ra kết quả có độ tin cậy cao: Mô hình MXH đƣợc xây dựng trên dữ liệu sự kiện đƣợc ghi lại trong quá trình hoạt động của doanh nghiệp. Do đó, mô hình MXH đƣợc xây dựng phản ánh bản chất sự tƣơng tác giữa những ngƣời tham gia vào quy trình. Các kết quả phân tích MXH tạo ra độ tin cậy cao nhằm hỗ trợ các nhà quản lý ra quyết định liên quan đến vấn đề tổ chức. - Trích lọc thông tin có giá trị: Đề xuất trong luận văn sử dụng giải thuật tìm kiếm cộng đồng chồng chéo nhằm tìm ra sự chồng chéo trong nhiệm vụ giữa những ngƣời trong một công ty. Từ đó, nhà quản lý có thể nắm bắt đƣợc thông tin về sự chồng chéo trong phân công nhiệm vụ giữa những nhân viên của họ, từ đó đƣa ra các quyết định liên quan đến cấu trúc tổ chức một cách khách quan. 35 3.1.2 Định dạng dữ liệu đầu vào các độ đo: - Dạng chuẩn dữ liệu đầu vào: Luận văn sử dụng dữ liệu nhật ký sự kiện định dạng XES. Đây là một định dạng chuẩn đƣợc sử dụng để lƣu trữ nhật ký sự kiện trong các HTTT, đƣợc phát triển bởi IEEE Task Force Process Mining. Định dạng mới này có sự linh hoạt và giải quyết đƣợc những hạn chế của định dạng MXML. Do không có một thuộc tính xác định toàn cục nào trong tệp XES và các thuộc tính của các phần tử bên trong tệp XES có ngữ nghĩa không rõ ràng. Chính sự không rõ ràng này giúp lƣu một số định dạng dữ liệu mở rộng. Thủ tục mở rộng một số thuộc tính tại các mức khác nhau trong kiến trúc XES đã cung cấp một số tham chiếu để giải thích các thuộc tính. Nhà khoa học Christian W. Gunther đã định nghĩa một siêu mô hình cho định dạng XES. Các thuộc tính toàn cục đƣợc xác định nhƣ các phần mở rộng để giải quyết các vấn đề của vấn đề ngữ nghĩa không rõ ràng, khi mà các HTTT không xác định đƣợc nội dung của các thuộc tính chuẩn. Trong tệp dữ liệu định dạng XES, mỗi vết (trace) tƣơng ứng với một trƣờng hợp trong MXML. Một vết có thể có nhiều sự kiện và một số thuộc tính. Hình 3.1 Một phần mã nguồn dữ liệu nhật ký sự kiện Nhật ký sự kiện lƣu trữ các thông tin liên quan đến sự kiện nhƣ tài nguyên (bao gồm con ngƣời, thiết bị, ), thời gian xảy ra sự kiện, Mỗi trƣờng hợp tƣơng ứng một lần thực hiện một quy trình, gồm nhiều sự kiện. Mỗi sự kiện là tƣơng ứng với một trƣờng hợp duy nhất, bao gồm các thuộc tính nhƣ thời gian thực hiện, tên công việc, nguồn tài nguyên, ngƣời thực hiện, . Các giá trị các thuộc tính là đặc trƣng riêng của mỗi sự kiện. Mã Trƣờng hợp Mã sự kiện Thuộc tính Thời gian Hoạt động Ngƣời thực hiện Chi phí 1 35654423 30-12-2010:11.02 Đăng ký Pete 50 36 1 35654424 31-12-2010:10.06 Kiểm tra đơn Mike 400 2 35654483 30-12-2010:11.32 Đăng ký Mike 50 2 35654485 30-12-2010:12.12 Kiểm tra thẻ Sean 100 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 Bảng 3.1 biểu diễn một phần về các đặc điểm của nhật ký sự kiện, mỗi sự kiện là một loại công việc đƣợc thực hiện bởi con ngƣời. - Loại độ đo hỗ trợ biểu diễn cấu trúc mạng: Luận văn sử dụng độ đo Handover of work để xây dựng ma trận mối quan hệ giữa những ngƣời tham gia vào quy trình. Độ đo này có thể sinh ra một mô hình MXH hay đồ thị có hƣớng và có trọng số. Tuy nhiên, trong luận văn Tác giả chỉ sử dụng mô hình MXH đƣợc biểu diễn dƣới dạng đồ thị vô hƣớng, không trọng số làm đầu vào cho giải thuật Phân vùng theo cạnh. Độ đo đƣợc sử dụng trong Luận văn, do: + Độ đo là đo mức độ thƣờng xuyên chuyển giao việc giữa những ngƣời tham gia vào quy trình. Ý tƣởng của độ đo phù hợp với mục tiêu của luận văn, tìm ra những cộng đồng ngƣời trong đó có những ngƣời thƣờng xuyên tƣơng tác với nhau. + Kết quả khi áp dụng độ đo phù hợp định hƣớng luận văn sẽ mở rộng giải thuật phân vùng theo cạnh đối với đồ thị có hƣớng và trọng số. - Loại giải thuật tìm kiếm: Luận văn sử dụng giải thuật phát hiện cộng đồng chồng chéo là giải thuật phân vùng theo cạnh của Ahn et al., do: + Ý tƣởng giải thuật: Để giải quyết bài toán KCTC, yếu tố quan trọng nhất là sự tƣơng tác giữa những ngƣời tham gia vào quy trình. Sự tƣơng tác này đƣợc biểu diễn dƣới dạng cạnh trong mô hình MXH. Giải thuật này phân vùng mạng dựa trên thông tin của các cạnh kề. Do đó, ý tƣởng của giải thuật phù hợp với ý tƣởng của luận văn. + Kết quả giải thuật: Cấu trúc tổ chức phân cấp không phản ánh đúng bản chất liên quan giữa các cộng đồng trong thực tế. Mục tiêu của luận văn là tìm ra sự chồng chéo của các cộng đồng. Giải thuật này tìm ra các cộng đồng chồng chéo đáp ứng đƣợc mục liêu của luận văn. + Giải quyết mâu thuẫn giữa các loại cấu trúc: Có một nghịch lý trong một số doanh nghiệp hiện nay là chức danh, vị trí, nhiệm vụ trên sổ sách đƣợc phân theo mô hình phân cấp, nhƣng khi các hoạt động đƣợc thực hiện lại xảy ra sự chồng chéo về chức nhiệm vụ các cá nhân, phòng. Giải thuật Phân vùng theo cạnh giải quyết đƣợc nghịch lý này, phá vỡ mâu thuẫn cấu trúc chồng chéo và phân cấp. 37 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 Tệp XES Thu thập dữ liệu sự kiện Xử lý và làm sạch dữ liệu Xây dựng ma trận mối quan hệ Tệp XES Ma trận Áp dụng giải thuật tìm kiếm cộng đồng Cộng đồng chồng chéo Đánh giá chất lƣợng cộng đồng Xây dựng ma trận kề Lƣu đồ thị (1) (2) (4) (3) (5) (6) (7) Ma trận Danh sách cạnh 38 3.2.2 Các bước thực hiện: Bƣớc 1. Thu thập dữ liệu: Trong luận văn, Tác giả thu thập các tập dữ liệu sự kiện định dạng XES 1.0, đƣợc công khai trên 02 website. Trong đó: + 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ả Wil M.P. Van der Alast trên Những tệp này không chứa những thông tin lỗi, nhiễu, , bao gồm từ 100-1.500 trƣờng hợp, 50-15.000 sự kiện, 6-10 ngƣời tham gia thực hiện các hoạt động. + 01 tệp định dạng XES trên trang là một trong những dữ liệu đƣợc đƣa ra trong bài nghiên cứu về các thách thức của KPQT năm 2013. Trên chuyên trang này, các tập dữ liệu này đƣợc chia ra làm hai loại chính: nhật ký sự kiện trong thực tế và nhật ký sự kiện đƣợc tổng hợp. Các tệp dữ liệu có số sự kiện, trƣờng hợp, ngƣời tham gia quy trình lên đến hàng nghìn. Định dạng các tệp thuộc nhiều dạng nhƣ CSV, XES, MMXL, Tuy nhiên, lƣợng thông tin bị nhiễu, lỗi, các thông tin không có giá trị khai phá trong mỗi tệp dữ liệu rất lớn, đây chính là thách thức đối với nhiệm vụ tiền xử lý dữ liệu. Tệp dữ liệu đƣợc Tác giả sử dụng trong thực nghiệm chứa 1571 trƣờng hợp, trong đó 87 trƣờng hợp ghi lại quá trình xử lý sự cố, 1484 trƣờng hợp ghi lại hoạt động của quy trình bao gồm 6644 sự kiện, có 442 ngƣời tham gia thực hiện các hoạt động. Bƣớc 2. Xử lý và làm sạch dữ liệu: Đặc điểm của dữ liệu thu thập từ quá trình kinh doanh thƣờng chứa lƣợng thông tin không có giá trị khai thác lớn. Trong một tệp nhật ký sự kiện có những phần thông tin bị lỗi, không chính xác, thông tin về quá trình xử lý sự cố, ít khi dùng trong quá trình khai phá nguồn dữ liệu này. Những dạng thông tin này đƣợc sinh ra có thể do con ngƣời hoặc phần mềm và có thể nằm rải rác hoặc tập trung trong một tệp. Tệp dữ liệu BPI2013.xes là tệp dữ liệu đƣợc sử dụng trong phần thực nghiệm của Chƣơng 4, chứa các sự kiện đƣợc ghi lại trong khoảng thời gian từ 10/5/2007 đến 31/05/2012. Bên cạnh ghi lại các hoạt động của quy trình, tệp còn ghi lại thông tin về quá trình xử lý sự cố (Incident handling process). Hệ thống sẽ có những thông báo nhất định đối với từng loại sự cố, một số thông báo nhƣ: “Accepted/ In Progress", “Queued/Awaiting Assignment", “Completed/Resolved”, Completed/ Closed”, “Accepted/Wait-User", . Việc nhật ký sự kiện lƣu lại thông tin xử lý sự cố dƣới dạng không cấu trúc gây khó khăn đối với các công cụ KPQT, kết quả sinh ra mô hình quy trình phức tạp nhƣ 39 mô hình Spaghetty [21]. 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. <int key="Queued+Awaiting Assignment;Accepted+In Progress; Completed+Closed; Accepted+In Progress; Queued+Awaiting Assignment;Accepted+In Progress ;Queued+Awaiting Assignment; Accepted+In Progress; Accepted+Assigned" value="1"/><int key="Accepted+In Progress;Queued+Awaiting Assignment;Accepted+In Progress;Accepted+In Progress" value="1"/> Hình 3.3 Thông tin quá trình xử lý sự cố được lưu trong tệp BPI2013.xes Bƣớc 3. Xây dựng ma trận mối quan hệ: Cách tính dựa trên độ đo Handover of work: Mỗi tập dữ liệu .XES gồm nhiều trƣờng hợp (case), mỗi trƣờng hợp gồm nhiều sự kiện, và mỗi sự kiện ghi lại ngƣời thực hiện một nhiệm vụ trong một chu kỳ quy trình kinh doanh. - Xét từng trƣờng hợp, tính số lần ngƣời hai ngƣời chuyển giao nhiệm vụ cho nhau. Ví dụ: Trong trƣờng hợp 1, 3, 7, 8, 9 (Bảng 3.2) có 5 lần Peter và Mike thực hiện chuyển nhiệm vụ cho nhau. - Tính tƣơng tự với các trƣờng hợp khác, tính tổng số lần ngƣời i, j chuyển việc cho nhau. Giá trị này chính là giá trị phần tử của ma trận mối quan hệ Bảng 3.3. Bảng 3.2 mô tả thứ tự chuyển giao việc của từng ngƣời trong một trƣờng hợp. Từ bản mô tả này, ta xây dựng ma trận số lần chuyển tác vụ giữa những ngƣời tham gia vào quy trình. Trƣờng hợp 1 2 3 4 5 6 7 8 9 10 Peter Mike Peter Peter Mike Mike Ellen Peter Ellen Mike Mike Mike Mike Sue Sean Ellen Mike Mike Peter Sean Ellen Sean Ellen Mike Sara Mike Peter Sean Mike Peter Sara Sara Sara Sara Ellen Sara Sara Sara Sara Sara Sara Sara Peter Mike Sara Ellen Sara Sean Sean Ellen Ellen Peter Peter Mike Mike Sara Ellen Sara Sara Ellen Sara Sara Sue Sean 40 Peter Peter Sara Sara Mike Mike 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 𝑀𝑕 là ma trận sinh ra sau khi sử dụng độ đo Handover of work. Trong đó: i, j là những ngƣời tham gia vào quy trình; 𝑀𝑕 𝑖, 𝑗 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ụ (i,j) Ellen Mike Peter Sara Sean Sue Ellen - 7 1 7 0 0 Mike 7 - 5 8 4 0 Peter 1 5 - 5 4 2 Sara 7 8 5 - 6 1 Sean 0 4 4 6 - 0 Sue 0 0 2 1 0 - Bảng 3.3 Ma trận 𝑀𝑕 mối quan hệ Bảng 3.3 là ma trận thể hiện mối quan hệ giữa những ngƣời tham gia vào quy trình. Giá trị các phần tử của ma trận thể hiện số lần chuyển giao công việc giữa hai ngƣời, nếu giá trị phần tử ma trận = 0, thể hiện hai ngƣời không có sự chuyển giao công việc. Số lần chuyển giao cũng thể hiện sự tƣơng tác nhiều hay ít của hai ngƣời trong quá trình thực hiện các hoạt động. Bƣớc 4. Lƣu đồ thị: Cách thức lƣu trong tệp .txt: Hình 3.5 Định dạng dữ liệu .txt lưu đồ thị 41 + Đồ thị đƣợc lƣu trong các tệp .txt, dƣới dạng một danh sách các cạnh. Mỗi cạnh đƣợc coi là một dòng trong tệp. + Các đỉnh phải đƣợc đánh số thứ tự bắt đầu từ số 0 và là số tự nhiên cách nhau bởi một cách. Đƣợc sắp xếp lần lƣợt theo thứ tự. Ví dụ: Ký hiệu: Đỉnh 0: [Ellen]; Đỉnh 1: [Mike]; Đỉnh 2: [Pete]; Đỉnh 3: [Sara]; Đỉnh 4: [Sean]; Đỉnh 5: [Sue]. Bƣớc 5. Xây dựng ma trận kề: 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 đỉ𝑛𝑕 𝑖 𝑘ề 𝑣ớ𝑖 đỉ𝑛𝑕 𝑗 𝑛𝑔ượ𝑐 𝑙ạ𝑖 Đỉnh 0 1 2 3 4 5 0 1 1 1 1 0 0 1 1 1 1 1 1 0 2 1 1 1 1 1 1 3 1 1 1 1 1 1 4 0 1 1 1 1 0 5 0 0 1 1 0 1 Bảng 3.4 Ma trận đỉnh kề 𝑀𝑎 Trong bảng 3.4, giá trị các phần trận 𝑀𝑎 chỉ bao gồm hai loại giá trị là 0 và 1 thể hiện mối quan hệ của hai đỉnh trong đồ thị. + Mô hình đồ thị vô hƣớng, không trọng số đƣợc xây dựng từ ma trận đỉnh kề: Nếu đỉnh 𝑀𝑎 𝑖, 𝑗 = 1, có một cạnh kết nối giữa đỉnh i và j, ngƣợc lại không có cạnh kết nối giữa hai đỉnh. Hình 3.4 Đồ thị được xây dựng từ ma trận kề 0 1 3 2 5 4 42 Bƣớc 6. Áp dụng giải thuật tìm kiếm cộng đồng: Ma trận đỉnh kề sẽ đƣợc lƣu dƣới dạng ma trận thƣa hay danh sách liên kết làm đầu vào cho giải thuật Phân vùng theo cạnh. Đỉnh Đỉnh kề 0 1,2,3 1 0,2,3,4,5 2 0,1,3,4,5 3 0,1,2,4,5 4 1,2,3 5 1,2,3 Bảng 3.5 Danh sách đỉnh kề + Xây dựng ma trận độ tƣơng tự giữa các cạnh: Tính độ tƣơng tự giữa các cặp cạnh (Công thức trong Chƣơng 2). Ví dụ: độ tƣơng tự của cạnh 0-1 và cạnh 0-2, đƣợc tính theo công thức: S 0 − 1, 0 − 2 = |𝑛+ 1 ∩𝑛+ 2 | |𝑛+ 1 ∪𝑛+ 2 | = 6 6 =1 Trong đó: 𝑛+ 1 ,𝑛+ 2 là tập các đỉnh kề tƣơng ứng của đỉnh 1 và 2. 𝑛+ 1 = 0, 1, 2, 3, 4, 5 ; 𝑛+ 2 = 0, 1, 2, 3, 4, 5 ; + Tiến hành gom cụm: Sử dụng kỹ thuật gom cụm từ dƣới - lên và phƣơng thức kết nối đơn để gom hai cụm. Hai cụm có độ tƣơng tự lớn nhất sẽ đƣợc gom lại thành một cụm. Quá trình đƣợc lặp lại cho đến khi tất cả các cạnh thuộc vào một cụm duy nhất. C0 C1 C2 C3 0-1 0-2 0-3 1-2 1-3 2-3 1-4 2-4 3-4 1-5 2-5 3-5 C0 0-1 1 1 1 0.7 0.7 0 0.6 0 0 0.6 0 0 0-2 1 1 1 0.7 0 0.7 0 0.6 0 0 0.6 0 0-3 1 1 1 0 0.7 0.7 0 0 0.6 0 0 0.6 C1 1-2 0.7 0.7 0 1 1 1 0.7 0.7 0 0.7 0.7 0 1-3 0.7 0 0.7 1 1 1 0.7 0 0.7 0.7 0 0.7 2-3 0 0.7 0.7 1 1 1 0 0.7 0.7 0 0.7 0.7 C2 1-4 0.6 0 0 0.7 0.7 0 1 1 1 0.6 0 0 2-4 0 0.6 0 0.7 0 0.7 1 1 1 0 0.6 0 3-4 0 0 0.6 0 0.7 0.7 1 1 1 0 0 0.6 C3 1-5 0.6 0 0 0.7 0.7 0 0.6 0 0 1 1 1 2-5 0 0.6 0 0.7 0 0.7 0 0.6 0 1 1 1 43 3-5 0 0 0.6 0 0.7 0.7 0 0 0.6 1 1 1 Bảng 3.6 Ma trận 𝑀𝑠 độ tương tự C4 C2 C3 C0 C1 C2 C3 C4 C0 1 0.7 0.6 0.6 C1 0.7 1 0.7 0.7 C2 C2 0.6 0.7 1 0.6 C3 C3 0.6 0.7 0.6 1 C6 C5 C3 C6 C5 1 0.7 C3 0.7 1 Hình 3.6 Quá trình phân cụm thứ bậc từ dưới - lên + Tìm ngƣỡng cắt cây lƣợc đồ: Đồ thị gồm 6 đỉnh và 12 cạnh. Gọi t là ngƣỡng cắt cây lƣợc đồ cho trƣớc. * Tại t=1, ta có 04 phân vùng: Phân vùng Cạnh Số cạnh Số đỉnh Mật độ P1 0-1;0-2;0-3 3 4 D1= 3−(4−1) 4∗(4−1) 2 − (4−1) = 0 P2 1-2;1-3;2-3 3 3 D2= 3−(3−1) 3∗(3−1) 2 − (3−1) = 1 P3 1-4;2-4;3-4 3 4 D3= 3−(4−1) 4∗(4−1) 2 − (4−1) = 0 P4 1-5;2-5;3-5 3 4 D4= 3−(4−1) 4∗(4−1) 2 − (4−1) = 0 Bảng 3.7 Tính mật độ các phân vùng tại ngưỡng cắt t=1 Mật độ phân vùng trung bình: 𝐷𝑡=1= 1 12 0 + 3 ∗ 1 + 0 + 0 = 0.25 C5 c3 C4 C2 C3 C5 C4 1 0.7 0.7 C2 0.7 1 0.6 c3 C3 0.7 0.6 1 44 * Tại t=0.7 Khả năng 1: 3 phân vùng: P3, P4, P5 Phân vùng Cạnh Số cạnh Số đỉnh Mật độ P5 0-1;0-2;0-3;1-2;1-3;2-3 6 4 D5= 6−(4−1) 4∗(4−1) 2 − (4−1) = 3 3 = 1 Bảng 3.8 Tính mật độ các phân vùng tại ngưỡng cắt t=0.7(KN1) Mật độ phân vùng trung bình: 𝐷1𝑡=0.7= 1 12 6 ∗ 1 + 0 + 0 = 0.5 Khả năng 2: ta có 3 phân vùng P1, P4, P6 Phân vùng Cạnh Số cạnh Số đỉnh Mật độ P6 1-2;1-3;2-3;1-4;2-4;3-4 6 4 D6= 6−(4−1) 4∗(4−1) 2 − (4−1) = 3 3 = 1 Bảng 3.9 Tính mật độ các phân vùng tại ngưỡng cắt t=0.7(KN2) Mật độ phân vùng trung bình: 𝐷2𝑡=0.7= 1 12 0 + 0 + 6 ∗ 1 = 0.5 Kết luận: Tại ngƣỡng cắt cây lƣợc đồ 𝑡 = 0.7, giá trị mật độ phân vùng trung bình đạt cực đại 𝐷 = 0.5. + Kết quả: Từ các cộng đồng cạnh đƣợc tìm thấy, ta tìm đƣợc các cộng đồng đỉnh tƣơng ứng. Hình 3.8 Các cộng đồng đỉnh chồng chéo Cộng đồng Cộng đồng cạnh Cộng đồng đỉnh Cộng đồng ngƣời I 0-1;0-2;0-3; 1-2;1-3;2-3 0, 1, 2, 3 Ellen, Mike, Peter, Sara Ellen Mike Sara Pete Sue Sean 45 II 1-4;2-4;3-4 1,2, 3, 4 Mike, Peter, Sara, Sean III 1-5;2-5;3-5 1, 2, 3, 5 Mike, Peter, Sara, Sue Bảng 3.10 Danh sách các cộng đồng được tìm thấy Bƣớc 7. Đánh giá chất lƣợng cộng đồng: + Đối với cộng đồng cạnh: Ahn et al. đã sử dụng công thức tính mật độ phân vùng nhằm đánh giá chất lƣợng của các cộng đồng cạnh. Giá trị mật độ phân vùng - 2 3 ≤ 𝐷 ≤ 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ị 𝐷 ≤ 0, thƣờng không có giá trị để khai thác vào các mục đích cụ thể. Trong đó: 𝐷 = 1: cộng đồng đƣợc phát hiện là một đồ thị đầy đủ. 𝐷 = 0: mỗi cộng đồng là một cây. 𝐷 < 0: các cộng đồng trong mạng không có sự kết nối. 𝐷 = − 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. Trong ví dụ: Mật độ phân vùng trung bình 𝐷 = 0.5 tại ngƣỡng cắt 𝑡 = 0.7 → Các cộng đồng cạnh có sự kết nối mạnh → Các cộng đồng đỉnh tƣơng ứng có sự chồng chéo lớn. + Đố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. Trong ví dụ: Cả ba cộng đồng (I), (II), (III) này đều là những cộng đồng không tầm thƣờng vì có tổng số đỉnh ≥ 3. Số lƣợng đỉnh chồng chéo thuộc vào các cộng đồng không tầm thƣờng là 3, tƣơng ứng là Mike, Peter, Sara. Sự tƣơng tác của ba ngƣời này với những ngƣời khác trong quy trình là thƣờng xuyên, thể hiện vai trò quan trọng của họ trong một quy trình. 46 CHƢƠNG 4. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1 Công cụ, môi trƣờng thực nghiệm Để thực hiện quá trình thực nghiệm, Tác giả sử dụng cấu hình phần cứng, phần mềm, tập dữ liệu nhƣ sau: 4.1.1 Phần cứng: STT Thiết bị/ Hệ điều hành Chỉ số 1 CPU Intel Core i3 M370 2.40 GHz 2 RAM 4096 MB 3 HDD 320 GB 4 OS Window 7 Ultimate 32 bit Bảng 4.1 Chi tiết chỉ số phần cứng và hệ điều hành 4.1.2 Phần mềm và tập dữ liệu đầu vào: TT Tên công cụ Chức năng Nguồn tải 1 NetBeans IDE 8.0.2 Công cụ lập trình trên nền Window, Unix hỗ trợ ngƣời dùng lập trình Java, https://netbeans.org 2 Mã nguồn mở Link Clustering Là chƣơng trình thực hiện giải thuật tìm kiếm cộng đồng theo phân vùng cạnh Ahn et al. https://github.com/fozziethebe at/S-Space 2 Tập dữ liệu đầu vào Là các tệp .xes sử dụng làm đầu vào của chƣơng trình Bảng 4.2 Thông tin 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. + 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. Ma trận thƣa là ma trận các phần tử có giá trị > 0 (Wikipedia). Điều này giúp tiết kiệm dung 47 lƣợng bộ nhớ và cải thiện thời gian chạy chƣơng trình. Để thực chạy đƣợc chƣơng trình này, thêm thƣ viện junit chƣơng trình. 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. Hình 4.1 Kết quả chương trình thực nghiệm 48 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 dữ liệu định dạng 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 độ trung bình Thời gian chạy (giây) Số Trƣờng hợp Số Sự kiện Số Ngƣời tham gia Số Đỉnh Số Cạnh Số cộng đồng cạnh Số cộng đồng đỉnh Số cộng đồng chồng chéo đỉnh Số cộng đồng không tầm thƣờng Số đỉnh chồng chéo Chapter1.xes 10 142 6 6 12 3 3 3 3 3 0.5 5 Chapter5.xes 1391 15078 8 8 14 4 4 4 2 4 0.36 7 Chapter6.xes 87 522 5 5 4 4 4 4 1 1 0 10 BPI2013.xes 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: - Số người tham gia vào quy trình: Nếu có ít ngƣời tham gia vào quy trình, 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 này còn có ý nghĩa là đánh giá mức độ quan trọng của từng ngƣời trong quy trình. - Mật độ kết nối các đỉnh trong MXH: Với một mạng có số cạnh xấp xỉ 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ế. - Kích thước các cộng đồng được tìm ra: 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 và số lƣợng cộng đồng không có giá trị khai thác nhiều. - 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 trọng của đỉnh đó trong đồ thị hay của cá nhân đó 49 đố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à rất 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, từ đó có sự nhận xét về chất lƣợng chồng chéo của các cộng đồng đỉnh. Nếu giá trị D nhỏ, các cộng đồng cạnh có sự kết nối thấp. 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 ngƣời tham gia ít, số lƣợng cộng đồng không tầm thƣờng chỉ chiếm 50 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 51 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN TƢƠNG LAI 1. Kết luận Với những mục tiêu và kế hoạch thực hiện luận văn trong hơn một năm qua, luận văn đã đạt đƣợc những kết quả chính: - 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: Giải thuật Phân vùng theo cạnh còn tồn tại nhiều hạn chế về thời gian chạy, gây ra sự phân tách các cộng đồng làm giảm độ chính xác trong kết quả. Mặt khác, nếu đầu vào của giải thuật là đồ thị có mật độ kết nối giữa các đỉnh thƣa, kết quả phân cụm sẽ không có ý nghĩa. Do vậy, 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. 52 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. [12] M. Bramer. (2007), Principles of Data Mining. Springer, Berlin. 53 [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. [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. 54 [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 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.