Luận văn Thạc sĩ Công nghệ Thông tin: Khai phá mạng xã hội dựa trên các bản ghi sự kiện hoạt động của doanh nghiệp

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

26
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung đề tài sẽ trình bày bao gồm các phần như sau: Chương 1: Trình bày những khái niệm cơ bản về nhật ký sự kiện, khai phá quy trình và những kiến thức khác liên quan đến đề tài. Chương 2: Trình bày về khai phá mạng xã hội bao gồm những khái niệm cơ bản, các độ đo trong trích xuất đồ thị quan hệ xã hội và phân tích mạng xã hội. Chương 3: Cải thiện độ đo trong trích xuất đồ thị quan hệ xã hội. Chương 4: Cài đặt và thực nghiệm.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ Thông tin: Khai phá mạng xã hội dựa trên các bản ghi sự kiện hoạt động của doanh nghiệp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN THỊ PHƯƠNG KHAI PHÁ MẠNG XÃ HỘI DỰA TRÊN CÁC BẢN GHI SỰ KIỆN HOẠT ĐỘNG CỦA DOANH NGHIỆP Ngành: Công nghệ Thông tin Chuyên ngành: Hệ thống thông tin Mã số: 604805 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. HÀ QUANG THỤY Hà Nội - 2015
2 LỜI CÁM ƠN Lời đầu tiên, tôi xin chân thành cảm ơn sự hướng dẫn và chỉ bảo tận tình của PGS.TS. Hà Quang Thụy – người đã đưa ra định hướng khoa học và luôn quan tâm, động viên, thông cảm, tạo điều kiện thuận lợi cho tôi trong suốt quá trình thực hiện luận văn. Tôi xin cảm ơn Phòng thí nghiệm Khoa học dữ liệu và Công nghệ Tri thức (DS&KTLab)và Đề tài cấp Đại học Quốc Gia Hà Nội, mã số QG.15.22 đã định hướng cho tôi trong đề tài nghiên cứu này. Cuối cùng, tôi xin gửi lời cảm ơn tới các bạn bè đã giúp đỡ, hỗ trợ tôi cả về mặt tinh thần và nền tảng kiến thức để tôi có thể hoàn thành luận văn. Hà Nội, tháng 10 năm 2015 Trần Thị Phương
3 LỜI CAM ĐOAN Tôi 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ôi, 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 là của cá nhân tôi hoặc được tôi tổng hợp từ nhiều nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin chịu toàn bộ 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 tôi. Hà Nội, tháng 10năm 2015 Trần Thị Phương
4 MỤC LỤC LỜI CÁM ƠN ................................................................................................................2 LỜI CAM ĐOAN ..........................................................................................................3 DANH MỤC TỪ VIẾT TẮT ........................................................................................6 DANH MỤC BẢNG BIỂU ...........................................................................................7 DANH MỤC HÌNH VẼ.................................................................................................8 MỞ ĐẦU .........................................................................................................................9 Chương 1. Những khái niệm cơ bản về nhật ký sự kiện và khai phá quy trình....11 1.1. Khái niệm nhật ký sự kiện ............................................................................... 11 1.2. Khai phá quy trình ........................................................................................... 12 Chương 2. Khai phá mạng xã hội ..............................................................................15 2.1. Trích xuất đồ thị quan hệ xã hội từ các bản ghi sự kiện .................................. 15 2.2. Các độ đo trong xây dựng đồ thị quan hệ xã hội ............................................. 16 2.2.1. Độ đo dựa trên quan hệ nhân quả ..........................................................17 2.2.2. Độ đo dựa trên trường hợp chung ..........................................................24 2.2.3. Độđo dựa trên các hoạt động chung ......................................................25 2.3. Phân tích mạng xã hội ...................................................................................... 27 2.3.1. Mật độ mạng ..........................................................................................28 2.3.2. Độ gần ....................................................................................................28 2.3.3. Độ trung tâm ..........................................................................................29 2.3.4. Độ trung gian .........................................................................................31 Chương 3. Cải thiện độ đo trong xây dựng đồ thị quan hệ xã hội ..........................33 3.1. Đặt vấn đề ........................................................................................................ 33 3.2. Giải pháp .......................................................................................................... 34 3.2.1. Đánh trọng số .........................................................................................34 3.2.2. Áp dụng trọng số chuyển giao vào công thức độ đo .............................36
5 Chương 4. Cài đặt, thực nghiệm ................................................................................37 4.1. Công cụ MiSoN ............................................................................................... 37 4.2. Thiết kế và cài đặt ............................................................................................ 39 4.2.1. Thiết kế tổng thể ....................................................................................39 4.2.2. Cấu trúc tệp nhật ký sự kiện đầu vào .....................................................41 4.2.3. Thiết kế lớp ............................................................................................41 4.2.4. Luồng hoạt động ....................................................................................43 4.3. Kết quả thực nghiệm ........................................................................................ 44 Kết luận ........................................................................................................................50
6 DANH MỤC TỪ VIẾT TẮT Từ viết tắt Từ viết đầy đủ Diễn giải HRM Human resource management Hệ thống quản lý nguồn nhân lực CRM Customer relationship Hệ thống quản trị quan hệ management khách hàng HR Human resource Bộ phận quản lý nhân sự SNA Social Network analysis Phân tích mạng xã hội
7 DANH MỤC BẢNG BIỂU Bảng 1.1 Một ví dụ nhật ký sự kiện tổng quát .................................................... 12 Bảng 1.2 Nhật ký sự kiện tổng quát đã sắp xếp theo từng trường hợp ............... 13 Bảng 2.1. Giá trị độ đo dựa trên sự chuyển giao công việc ................................ 21 Bảng 2.2. Ma trận tần xuất thực thi hoạt động .................................................... 25 Bảng 4.1 Bảng trọng số các hoạt động................................................................ 47 Bảng 4.2. Ma trận trọng số khi bỏ qua chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp........................................................................................... 47 Bảng 4.3. Ma trận trọng số khi bỏ qua chuyển giao công việc nhiều lần, có tính tới chuyển giao gián tiếp ..................................................................................... 47 Bảng 4.4. Ma trận trọng số khi có tính tới chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp .................................................................................... 48 Bảng 4.5. Ma trận trọng số khi có tính tới chuyển giao công việc nhiều lần, bỏ qua chuyển giao gián tiếp .................................................................................... 49
8 DANH MỤC HÌNH VẼ Hình 1.1. Sơ đồ quy trình tuyển dụng ................................................................. 11 Hình 1.2. Sơ đồ quy trình dạng lưới Petri cho nhật ký sự kiện tổng quát .......... 14 Hình 2.1. Đồ thị quan hệ xã hội trích xuất từ nhật ký sự kiện Bảng 1.1 ............ 16 Hình 2.2. Đồ thị minh họa về độ gần của nút trong đồ thị.................................. 29 Hình 2.3. Đồ thị minh họa về độ trung tâm cục bộ của nút ................................ 30 Hình 2.4. Đồ thị minh họa về độ trung gian ....................................................... 31 Hình 4.1. Kiến trúc của MiSoN .......................................................................... 38 Hình 4.2 Giao diện MiSoN hiển thị đồ thị quan hệ xã hội với dữ liệu từ Staffware log ....................................................................................................... 39 Hình 4.3. Vị trí và mối quan hệ của package SocialNetwork trong ProM ......... 40 Hình 4.4. Thiết kế lớp cài đặt độ đo chuyển giao công việc............................... 42 Hình 4.5 Biểu đồ công tác xây dựng đồ thị quan hệ xã hội ................................ 44 Hình 4.6 Sơ đồ luồng tính toán ma trận trọng số ................................................ 44
9 MỞ ĐẦU Cùng với sự phát triển của công nghệ thông tin, các hệ thống thông tin doanh nghiệp ngày càng được ứng dụng phổ biến, trong đó có thể kể đến những cái tên tiêu biểu: HRM – hệ thống quản lý nhân sự, CRM - quản trị quan hệ khách hàng… Các hệ thống này lưu trữ dữ liệu sự kiện hoạt động của doanh nghiệp dưới dạng các bản ghi có cấu trúc kèm theo thông tin về thời gian, chi tiết hoạt động, đối tượng tham gia…, nhờ đó chúng ta có thể hình dung được luồng công việc một cách có hệ thống. Tuy nhiên, các hệ thống nói trên mới mới chỉ dừng ở mức lưu trữ và thống kê, dữ liệu sự kiện của các doanh nghiệp vẫn chưa được sử dụng một cách hiệu quả trong việc hỗ trợ nhà quản trị đưa ra quyết định điều hành. Việc phân tích các bản ghi sự kiện đã được thực hiện từ rất sớm với nhiều công trình nghiên cứu khác nhau. Hầu hết các đề tài nghiên cứu hiện nay đều đi theo hướng khai phá quy trình - sử dụng các bản ghi sự kiện phục vụ việc xây dựng, cải tiến và kiểm chứng mô hình quy trình. Tuy nhiên, bên cạnh các thông tin về thời gian, công việc thì nhiều hệ thống còn ghi lại cả thông tin về yếu tố con người (ví dụ người thực thi hành động, người được chuyển giao công việc…). Như vậy, các bản ghi sự kiện ngoài việc phản ánh luồng công việc còn có thể phản ánh được mối quan hệ cộng tác trong công việc giữa các cá nhân, nhóm người trong doanh nghiệp. Môi trường doanh nghiệp cũng có thể coi là một xã hội thu nhỏ, và mối quan hệ trong công việc có thể coi là một loại quan hệ xã hội trong xã hội thu nhỏ đó. Các cá nhân, nhóm người trong doanh nghiệp cùng mối quan hệ giữa họ hình thành nên mạng xã hội. Từ các bản ghi sự kiện chúng ta có thể xây dựng nên mô hình mạng xã hội cũng như phân tích dữ liệu để cho ra những thông tin tổng hợp dưới góc nhìn thuận tiện, hữu ích, hỗ trợ cho nhà quản trị doanh nghiệp. Luận văn của tôi dựa trên nghiên cứu của WMP Van der Aalst và Minseok Song trình bày trong [1]. Trong đó, các bản ghi sự kiện sẽ được sử dụng trong khai phá mạng xã hội (mà cụ thể hơn là khai phá mối quan hệ giữa các cá nhân/nhóm người) nhằm phục vụ cho việc quản trị nhân sự trong doanh nghiệp. Nội dung đề tài tôi sẽ trình bày bao gồm các phần như sau: Chương 1: Trình bày những khái niệm cơ bản về nhật ký sự kiện, khai phá quy trình và những kiến thức khác liên quan đến đề tài.
10 Chương 2: Trình bày về khai phá mạng xã hội bao gồm những khái niệm cơ bản, các độ đo trong trích xuất đồ thị quan hệ xã hội và phân tích mạng xã hội. Chương 3: Cải thiện độ đo trong trích xuất đồ thị quan hệ xã hội. Chương 4: Cài đặt và thực nghiệm. Hà Nội, ngày18 tháng10 năm 2015 Trần Thị Phương
11 Chương 1. Những khái niệm cơ bản về nhật ký sự kiện và khai phá quy trình Trong luận văn này, tôi sử dụng các bản ghi sự kiện lấy được từ các hệ thống thông tin doanh nghiệp, kết hợp với phân tích quy trình như đầu vào đã biết cho khai phá mạng xã hội. Vì vậy, trước khi trình bày về khai phá mạng xã hội cũng như việc ứng dụng khai phá mạng xã hội trong môi trường doanh nghiệp, tôi xin trình bày một vài khái niệm và lý thuyết liên quan bao gồm: khái niệm nhật ký sự kiện (event log) và khai phá quy trình(process mining). 1.1. Khái niệm nhật kýsự kiện Giả sử rằng các hệ thống thông tin doanh nghiệp lưu trữ lịch sử hoạt động của doanh nghiệp trong nhật ký sự kiện (event log)dưới dạng các bản ghi có cấu trúc gọi là sự kiện (event). Các sự kiện ghi trong nhật ký sự kiện thỏa mãn những tính chất sau[2]: - Mỗi sự kiện tương ứng với một trường hợp (case), một thể hiện quy trình hoạt động. - Mỗi sự kiện tương ứng với một hoạt động(activity), một bước nào đó trong một thể hiện quy trình hoạt động. - Mỗi sự kiện tương ứng có một người thực thi (performer hoặc resource). - Trong cùng một trường hợp, các sự kiện được ghi lại theo đúng trình tự thực hiện về thời gian. Để hiểu rõ hơn về các khái niệm trường hợp, hoạt động,người thực thi, ta xét ví dụ sau về một quy trình tuyển dụng như Hình 1.1. Hình 1.1. Sơ đồ quy trình tuyển dụng Quy trình tuyển dụng bao gồm các bước  Bước 1: Trưởng phòng nhân sự lên kế hoạch tuyển dụng.  Bước 2: Bộ phận nhân sự (HumanResource -HR) đăng tin tuyển dụng.
12  Bước 3: Ứng viên nộp hồ sơ ứng dụng.  Bước 4: HR liên hệ với ứng viên để sắp xếp lịch phỏng vấn.  Bước 5: Trưởng bộ phận/HR v.v. phỏng vấn ứng viên.  Bước 6: Trưởng bộ phận/HR v.v. đánh giá kết quả phỏng vấn và lựa chọn ứng viên phù hợp.  Bước 7: HR thông báo kết quả tuyển dụng cho ứng viên. Trong ví dụ này, mỗi lần tuyển dụng tương ứng là một trường hợp. Các bước trong quy trình tuyển dụng (1, 2,..., 6, 7) là các hoạt động. Trưởng phòng nhân sự, HR, ứng viên, trưởng bộ phận… là những người thực thi. 1.2. Khai phá quy trình Sử dụng đầu vào là nhật ký sự kiện, mục tiêu của khai phá quy trình (Process mining)là trích xuất thông tin về các quy trình [3], qua đó phát hiện, xây dựng và cải tiến quy trình để nâng cao hiệu suất làm việc của doanh nghiệp. Trong phát hiện quy trình, yếu tố con người được bỏ qua, và chúng ta chỉ quan tâm đến thứ tự thực hiện của các hoạt động trong các trường hợp. Để minh họa cho khái niệm khai pháquy trình, xét ví dụ với một nhật ký sự kiệntổng quát như trongBảng 1.1. Bảng 1.1 Một ví dụ nhật ký sự kiện tổng quát Trường hợp Hoạt động Người thực thi 1 A An 2 A An 3 A Mai 3 B Chi 1 B Duy 1 C An 2 C Duy 4 A Mai 2 B An 2 D Minh 5 A Mai 4 C Chi 1 D Minh 3 C Mai 3 D Minh
13 4 B Mai 5 E Nga 5 D Nga 4 D Minh Sắp xếp lại theo từng trường hợp, chúng ta có Bảng 1.2. Bảng 1.2 Nhật ký sự kiện tổng quát đã sắp xếp theo từng trường hợp Trường hợp Hoạt động Người thực thi 1 A An 1 B Duy 1 C An 1 D Minh 2 A An 2 C Duy 2 B An 2 D Minh 3 A Mai 3 B Chi 3 C Mai 3 D Minh 4 A Mai 4 C Chi 4 B Mai 4 D Minh 5 A Mai 5 E Nga 5 D Nga Quan sát ví dụ trên ta thấy: - Mỗi trường hợp đều bắt đầu với hoạt động A và kết thúc bằng hoạt động D. - Giữa A và D có thể là E hoặc B và C. - B và C không có thứ tự thực hiện cố định. Áp dụng thuật toán alpha1, chúng ta có thể biểu diễn mô hình thể hiện mối quan hệ về mặt thứ tự thực hiện giữa các hoạt động dưới dạng lưới Petri2 như trong Hình 1.2: 1 https://en.wikipedia.org/wiki/Alpha_algorithm 2 https://en.wikipedia.org/wiki/Petri_net
14 Hình 1.2. Sơ đồ quy trình dạng lưới Petri cho nhật ký sự kiện tổng quát Trong luận văn này, tôi tập trung vào khía cạnh xã hội (tức mối quan hệ giữa các cá nhân) của nhật ký sự kiện. Vì vậy, các khái niệm cụ thể trong khai phá quy trình, thuật toán và ký pháp biểu diễntôi sẽ không trình bày chi tiết.
15 Chương 2. Khai phá mạng xã hội Khác với khai phá quy trình, khai phá mạng xã hội nhằm tới mục tiêu hỗ trợ nhà quản trị đưa ra các quyết định về mặt nhân sự trong doanh nghiệp.Do đó, thay vì tập trung vào thứ tự thực hiện của các hoạt động, khai phá mạng xã hội khai thác mối quan hệ giữa các cá nhân, nhóm người tham gia vào quy trình trích xuất được từ nhật ký sự kiện. Quá trình khai phá mạng xã hội trải qua hai bước. Đầu tiên, đồ thị quan hệ xã hội (sociogram) giữa các cá nhân tham gia vào quy trình hoạt động của doanh nghiệp được trích xuất từ nhật ký sự kiện. Sau đó,đồ thị quan hệ xã hội được sử dụng làm đầu vào cho phân tích mạng xã hội, tổng hợp dữ liệu và biểu diễn dưới các góc độ, khía cạnh khác nhau, thuận tiện hơn cho việc ra quyết định. 2.1. Trích xuất đồ thị quan hệ xã hội từ các bản ghi sự kiện Từ góc nhìn toán học, đồ thị quan hệ xã hội là đồ thị G(P, R) trong đó[1]  P:tập các nút của đồ thị, tương ứng tập những người thực thi các hoạt động trong các bản ghi sự kiện.  R ⊆ P × P là tập các mối quan hệ giữa những người thực thi. Tùy thuộc vào yêu cầu phân tích mà đồ thị có thể có hướng hoặc vô hướng, có trọng số hoặc không có trọng số. Nếu đồ thị G có trọng số, G có một hàm W dùng để gán giá trị cho các phần tử của R. Tập P có thể được xác định trực tiếp từ các bản ghi sự kiện. Tuy nhiên, R và W thì có nhiều tiêu chí khác nhau để xác định. Ví dụ, ta có thể coi giữa những người trong cùng một phòng ban trên cây cơ cấu tổ chức là có mối liên hệ với nhau. Trong cùng phòng ban đó, những người làm việc cùng một nhóm nhỏ sẽ có mối liên hệ mạnh hơn so với những người cùng phòng ban nhưng khác nhóm. Những người có cùng vai trò trong công việc hay có sự chuyển giao công việc cho nhau cũng được coi là có mối liên hệ với nhau(ta gọi đó là mối quan hệ chuyển giao công việc – Transfer of work) Theo ngôn ngữ của khai phá quy trình, giả sử trong cùng một trường hợp C, nếu hoạt động A2 được thực hiện ngay sau hoạt động A1 thì mối quan giữa người thực thi A1 và A2 được gọi là quan hệ chuyển giao công việc. Nhìn chung, mối quan hệ chuyển giao công việc phản ánh khá chính xác mối quan hệ trong thực tế hoạt động của doanh nghiệp.
16 Quay lại với ví dụ nhật ký sự kiện trong Bảng 1.1, ta có nhận xét như sau: - Chi và Duy có thể thực hiện các hoạt động như nhau (B và C) - Duy thì luôn làm việc với An (trường hợp 1 và 2), còn Chi thì lại luôn làm việc với Mai (trường hợp 3 và 4). Như vậy, mặc dù có thể Chi và Duy có cùng vai trò nhưng Chi không làm việc với An và Duy không làm việc với Mai. Lập luận tương tự, dựa trên mối quan hệ chuyển giao công việc, từ nhật ký sự kiệnBảng 1.1, ta có thể trích xuất ra đồ thị quan hệ xã hội như Hình 2.1. Hình 2.1. Đồ thị quan hệ xã hội trích xuất từ nhật ký sự kiện Bảng 1.1 Trong đồ thị trên Hình 2.1, giữa An và Duy, Mai và Chi có sự chuyển giao công việc qua lại. Tuy nhiên giữa Mai và Minh chỉ có sự chuyển giao công việc từ Mai sang Minh mà không có chiều ngược lại. Tương tự với mối quan hệ giữa An và Minh, Mai và Nga. Đồ thị trên là đồ thị không có trọng số, tuy nhiên, để phục vụ cho việc phân tích mạng xã hội, trọng số có thể được thêm vào đồ thị. Trọng số được đánh căn cứ vào tần suất chuyển giao công việc, ví dụ, cung từ An tới Duy có trọng số là 2. 2.2. Các độ đo trong xây dựng đồ thị quan hệ xã hội Để xây dựng được đồ thị quan hệ xã hội, chúng ta định nghĩa ra các độ đo khác nhau nhằm đánh trọng số cho các cung thể hiện mối quan hệgiữa những người thực thi. Gọi trọng số trên cung nối giữa người thực thi i và j là Wi,j. Nếu Wi,j>= τ nào đó (τ là giá trị ngưỡng) thì ta thêm cung ịj vào tập R. Bằng cách đó, chúng ta có được đồ thị G (P, R, W) có thể dùng làm đầu vào cho các công cụ phân tích mạng xã hội. Trong luận văn này, tôi chỉ trình bày ba loại độ đo có thể được trích xuất từ nhật ký sự kiện [1][2]: (1) Độ đo dựa trên quan hệ nhân quả
17 (2) Độ đo dựa trên những trường hợp chung (3) Độ đo dựa trên các hoạt động chung Để thuận tiện, tôi xin định nghĩa lại dưới dạng toán học khái niệm nhật ký sự kiện và các ký pháp tôi sẽ sử dụng trong phần này[1][2]. Định nghĩa 2.1(Nhật ký sự kiện):Gọi A là một tập các hoạt động, P là tập ntác nhân (cá nhân, nhóm người tham gia vào quy trình).E = A×P là tập hợp các sự kiện có thể xảy ra. Khi đó: - Mỗi sự kiện được định nghĩa dưới dạng một cặp giá trị (a, p) thể hiện hoạt động a được thực hiện bởi p. - C = E* là tập các chuỗi sự kiện có thể (mỗi chuỗi sự kiện tương ứng với một trường hợp). - B(C) là tập các túi từ trên C. - L ⊆ B(C) là một nhật ký sự kiện và là tập con của C. Với sự kiện e(a, p) ta định nghĩa hai phép toán - 𝜋a (e) = a - 𝜋p(e) = p 2.2.1. Độ đo dựa trên quan hệ nhân quả Độ đo dựa trên quan hệ nhân quả phản ánh cách luồng công việc di chuyển giữa các cá nhân trong từng trường hợp. Tính nhân quả thể hiện trong hai loại mối quan hệ mà chúng ta sẽ sử dụng làm độ đo trong phần này: quan hệ chuyển giao công việc (Handover of work) và quan hệ thầu phụ (Sub-contracting). Quan hệ chuyển giao công việc: Trong cùng một trường hợp, nếu có một hoạt động thực hiện bởi j được thực hiện ngay sau hoạt động thực hiện bởi i thì ta nói ở đây có sự chuyển giao công việc từ i sang j. Khi đánh giá quan hệ chuyển giao công việc ta có thể kết hợp với khai phá quy trình để xác định có thật sự có mối quan hệ nhân quả trong việc chuyển giao hay không. Ngoài ra, khi sử dụng làm độ đo, khái niệm chuyển giao công việc cũng cần thay đổi để có thể phân cấp được độ mạnh yếu của mối quan hệ giữa những người thực thi. Ngoài việc dựa vào sự chuyển giao trực tiếp, chuyển giao gián tiếp cũng có thể được tính tớithông qua việc sử dụng hệ số nhân quả β[1]. Ví dụ nếu có 3 hoạt động xen
18 giữa hoạt động thực hiện bởi i và hoạt động thực hiện bởi j thì hệ số nhân quả là β3. Quan hệ thầu phụ: Nếu giữa hai hoạt động được thực hiện bởiicó hoạt động được thực hiện bởi j thì ta có nói có mối quan hệ thầu phụ giữa i và j[1]. a. Độ đo dựa trên mối quan hệ nhân quả trong chuyển giao công việc Ý tưởng cơ bản của độ đo này là những người thực thi có mối liên hệ với nhau nếu giữa họ có sự chuyển giao công việc cho nhau. Khi đánh giá theo độ đo này, có 3 yếu tố cần cân nhắc[1]: - Ta chỉ quan tâm đến chuyển giao công việc trực tiếp hay tính tới cả chuyển giao công việc gián tiếp. - Nếu trong cùng một trường hợp, hai người thực thi chuyển giao công việc cho nhau nhiều lần thì tính thành một lần hay nhiều lần. - Chỉ xét tới chuyển giao công việc khi có mối quan hệ nhân quả hay cả khi chuyển giao công việc theo thứ tự bất kỳ (ví dụ trong Hình 1.2, ta thấy A và B không có quan hệ nhân quả vì sau A không nhất thiết phải là B mà còn có thể là C hoặc E) Căn cứ theo những tiêu chí trên, chúng ta có thể có 8 (23) biến thể khác nhau của độ đo này. Công thức độ đo và các toán tử sử dụng trong độ đo được định nghĩa như sau: Định nghĩa 2.2 (⊳, ⊵):Gọi L là một nhật ký sự kiện. Ký hiệu → biểu diễn mối quan hệ nhân quả trích xuất được từ L. Với a1, a2∈ A, p1, p2∈ P, c = (c0, c1,…) ∈ L và n ∈ N ta có[1] p nc p  0  i |c|n  p (C )  p  p (Cin )  p 1 2 i 1 2 1 Nếu  p (Ci )  p  p (Cin )  p | p nc p |   0  i  |c|n 1 2 1 2 0 trong trường hợp khác p cn p  0  i  |c|n  p (C )  p  p (Cin )  p  a (C )  a (Cin ) 1 2 i 1 2 i 1 Nếu  p (Ci )  p  p (Cin )  p  a (C )  a (Cin ) | p cn p |   0  i  |c|n 1 2 1 2 i 0 trong trường hợp khác
19  p nc p 1 2 là một hàm trả về giá trị 1 nếu tồn tại ít nhất một trường hợp trong đó có cả p1 và p2 cùng tham gia, và khoảng cách giữa 2 hoạt động mà p1 và p 2 thực hiện là n. Nếu n = 1 thì sự chuyển giao công việc là trực tiếp, ngược lại, nếu n > 1 là chuyển giao gián tiếp.  | p nc p | trả ra số lần của p nc p trong cùng trường hợp c, hay nói cách 1 2 1 2 khác, | p nc p | có tính đến việc trong cùng một trường hợp có thể có nhiều 1 2 lần chuyển giao công việc giữa những người thực thi.  p cn p 1 2 và | p cn p | cũng tương tự như p nc p và | p nc p | 1 2 1 2 1 2 , chỉ khác ở chỗ là ở đây ta có tính tới cả trường hợp chuyển giao công việc ngẫu nhiên chứ không nhất thiết phải có mối quan hệ nhân quả. Ví dụ với nhật ký sự kiện Bảng 1.1, xét trường hợp 1, thứ tự thực hiện của các hoạt động là: A (An), B (Duy), C (An), D (Minh). Ta có  Duy nc An = 1  Duy nc Minh = 0  Duy cn An = 0 vì mặc dù Duy thực hiện B ngay sau A thực hiện bởi An thực hiện A nhưng giữa A và B không có mối quan hệ nhân quả bởi sau A không nhất thiết là B mà có thể là C.  Duy cn Minh = 1 do B và C có mối quan hệ nhân quả (sau B nhất định phải có D) Sử dụng định nghĩa ở trên, ta có 8 công thức về mối quan hệ chuyển giao công việc như sau: Định nghĩa 2.3 (Độ đo dựa trên sự chuyển giao công việc): Gọi L là một nhật ký sự kiện, p1, p2∈ P và giá trị hệ số β (0 < β < 1) ta có [1]
20 p L p 1 2  ( cL | p1 1c p2 |)/ ( cL |c| 1) . p L p  ( cL  p 1c p 1) /| L| 1 2 1 2 ( cL 1 n |c|  n1 | p1 nc p2 |)  p1 L p2  ( cL 1  n|c|  n1(| c |  n)) .  ( cL 1 n |c| p nc p  n1 ) p1  L p2  1 2 n 1 ( cL 1 n|c|  ) p L p  ( cL | p 1c p |)/ ( cL |c| 1) 1 2 1 2 . p L p  ( cL  p 1c p 1) /| L| 1 2 1 2 ( cL 1 n|c|  n1 | p1 cn p2 |)  p1 L p2  ( cL 1n|c|  n1(| c |  n)) . ( cL 1  n |c| p cn p  n1 ) p1  L p2  1 2 ( cL 1n|c|  n1)  p L p 1 là tỉ lệ giữa số lần chuyển giao công việc trực tiếp từ p1 đến p2 và 2 . tổng số lần chuyển giao công việc của nhật ký sự kiện. p1 L p2 cũng vậy nhưng đã được bỏ qua những lần chuyển giao công việc trùng nhau trong cùng một trường hợp. Ví dụ trong Bảng 1.1 ta có: An L Duy = 2/14 . An L Duy = 2/5. .  p L p và p1  L p2 xử lý cả việc chuyển giao công việc không trực tiếp 1 2 vào độ đo bằng cách bổ sung thêm hệ số giảm β. Nếu trong cùng một trường hợp, giữa hai người thực thi có n sự kiện thì hệ số giảm sẽ là βn.  p L p quan tâm đến tất cả các lần chuyển giao công việc trong nhật ký sự 1 2 kiện .  p  L p bỏ qua những lần những lần chuyển giao công việc trong cùng một 1 2 trường hợp. Nếu áp dụng công thức trên cho nhật ký sự kiện trong Bảng 1.1, ta có kết quả như trong Bảng 2.1.