ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

Phạm Huy Thành

CÁC ĐỘ ĐO TRONG PHÂN CỤM VÀ ÁP DỤNG
VÀO PHÁT HIỆN MƠ HÌNH TỔ CHỨC
TRONG KHAI PHÁ Q TRÌNH

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Cơng nghệ thông tin

Hà Nội - 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

Phạm Huy Thành

CÁC ĐỘ ĐO TRONG PHÂN CỤM VÀ ÁP DỤNG
VÀO PHÁT HIỆN MƠ HÌNH TỔ CHỨC
TRONG KHAI PHÁ Q TRÌNH

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Cơng nghệ thông tin

Cán bộ hƣớng dẫn:

PGS. TS. Hà Quang Thụy


Trước tiên, tơi xin bày tỏ lịng biết ơn chân thành và sâu sắc nhất tới Thầy giáo
PGS. TS. Hà Quang Thụy và ThS. Lê Hoàng Quỳnh, những người đã tận tình chỉ bảo,
hướng dẫn, động viên và giúp đỡ tơi trong suốt q trình thực hiện đề tài khóa luận.
Tơi xin gửi lời cảm ơn sâu sắc tới các thầy cô trong Khoa Công nghệ thông tin đã
truyền đạt kiến thức quý báu cho tôi trong suốt bốn năm vừa qua, những kiến thức tôi
nhận được trên giảng đường sẽ là hành trang quan trọng giúp tôi vững bước trong tương
lai.
Tôi cũng xin gửi lời cảm ơn tới các thầy cô, các anh chị, các bạn và các em sinh
viên trong phịng thí nghiệm KT-Sis lab đã giúp tôi rất nhiều trong việc hỗ trợ kiến thức
chuyên mơn để hồn thành tốt nghiệp khóa luận.
Tơi gửi lời cảm ơn tới tập thể lớp K55CD và K55CLC đã ủng hộ, khích lệ và ln
sát cánh bên tơi trong suốt quá trình học tập và rèn luyện tại trường.
Cuối cùng,tôi muốn gửi lời cảm ơn sâu sắc tới bạn bè, người thân đặc biệt là cha
mẹ và em gái tôi, những người luôn ủng hộ con đường tôi đã lựa chọn, giúp đỡ và động
viên tôi vượt qua những khó khăn trong cuộc sống.
Tơi xin chân thành cảm ơn!

Hà Nội, ngày 13 tháng 05 năm 2014
Sinh viên

Phạm Huy Thành


TÓM TẮT
Theo W.M.P Van der Aalst, 2011 [10], khai phá quá trình trong những năm gần đây đang
nổi lên như một lĩnh vực khoa học mới tập trung vào việc phân tích các q trình bằng việc sử
dụng dữ liệu sự kiện. Lĩnh vực này đang thu hút được sự quan tâm từ rất nhiều các nhà khoa học
trên thế giới. Tuy nhiên hầu hết những tiếp cận này mới chỉ quan tâm và tập trung vào việc phát
hiện khía cạnh luồng điều khiển mà bỏ qua một số khía cạnh quan trọng khác trong đó nổi bật là
khía cạnh tổ chức [9]. Một trong những bài toán quan trọng trong khai phá khía cạnh tổ chức là


LỜI CAM ĐOAN
Tơi xin cam đoan mơ hình giải quyết bài tốn phát hiện mơ hình tổ chức áp dụng
các độ đo trong phân cụm, thực nghiệm áp dụng thuật toán K-medoids và dựa trên các độ
đo phân cụm được trình bày trong khóa luận là do tơi thực hiện dưới dự hướng dẫn của
PGS. TS. Hà Quang Thụy và ThS. Lê Hồng Quỳnh.
Tất cả các bài báo, khóa luận, tài liệu, công cụ, phần mềm của các tác giả khác được
sử dụng trong khóa luận này đều được chỉ dẫn tường minh về tác giả và đều có trong
danh sách tài liệu tham khảo.
Hà Nội, ngày 13 tháng 05 năm 2014
Sinh viên

Phạm Huy Thành


MỤC LỤC
Chương 1.
BÀI TỐN PHÁT HIỆN MƠ HÌNH TỔ CHỨC TRONG KHAI PHÁ QUÁ TRÌNH ...... 2
1.1.

Giới thiệu chung về khai phá quá trình ................................................................... 2

1.2.

Nhật ký sự kiện ....................................................................................................... 4

1.3.

Các bài tốn trong khai phá q trình ..................................................................... 6



2.2.1.

Thuật tốn AHC ............................................................................................. 12

2.2.2.

Thuật tốn K-means ....................................................................................... 13

2.2.3.

Thuật toán K-medoids (PAM) ....................................................................... 14

2.3.

Các độ đo chất lượng phân cụm............................................................................ 14

2.3.1.

Độ đo bóng (Silhouette) ................................................................................. 15

2.3.2.

Độ đo Davies – Bouldin ................................................................................. 16

2.3.3.

Độ đo Dunn .................................................................................................... 16

2.3.4.


3.3.2.

Sử dụng thuật toán K-medoids phát hiện mơ hình tổ chức ............................ 26

3.4.

Tóm tắt chương 3 .................................................................................................. 27

Chương 4.
THỰC NGHIỆM VÀ ĐÁNH GIÁ..................................................................................... 28
4.1.

Mô tả thực nghiệm ................................................................................................ 28

4.1.1.

Mô tả dữ liệu .................................................................................................. 28

4.1.2.

Các công cụ và phần mềm sử dụng ................................................................ 29

4.1.3.

Môi trường thực nghiệm ( Phần cứng và hệ điều hành ) ............................... 30

4.1.4.

Các module chính trong chương trình ........................................................... 30

cụm. .................................................................................................................. 24
Hình 3. 3. Meta-model của chuẩn XES ............................................................................. 25
Hình 4. 1. Một phần được trích ra từ nhật ký sự kiện trong thực nghiệm ......................... 29
Hình 4. 2. Mơ hình mạng xã hội mơ tả quan hệ giữa các cá nhân .................................... 33
Hình 4. 3. Hình mơ tả các module trong chương trình......................................................31
Hình 4. 4. Biểu đồ giá trị Silhouette .................................................................................. 36
Hình 4. 5. Biểu đồ giá trị Dunn ......................................................................................... 36
Hình 4. 6. Biểu đồ giá trị Modularity ................................................................................ 36
Hình 4. 8. Biểu đồ giá trị CPLw ......................................................................................... 36
Hình 4. 8. Kết quả mơ hình tổ chức ứng với K = 8 ........................................................... 37


DANH SÁCH BẢNG BIỂU

Bảng 1. 1. Một đoạn trong nhật ký sự kiện mỗi dòng tương ứng với mỗt sự kiện ............. 5
Bảng 4. 1. Bảng thống kê môi trường thực nghiệm (phần cứng và HĐH)........................30
Bảng 4. 2. Một phần trích từ bảng ma trận kề theo độ đo WorkingTogether .................... 32
Bảng 4. 3. Bảng mơ hình tổ chức tương ứng với giá trị K ( số lượng cụm) ..................... 35


LỜI MỞ ĐẦU
Ngày nay, hầu hết các tổ chức đều ghi lại quá trình kinh doanh của mình dưới dạng
các nhật ký sự kiện. Những nhật ký này có thể được sử dụng để phát hiện khía cạnh luồng
điều khiển bằng các kỹ thuật phát hiện quá trình nhằm đưa ra các mơ hình q trình để
phân tích và chẩn đốn nhằm cải thiện q trình sản xuất. Tuy nhiên, trong thực tế, các
q trình khơng hồn tồn bị điều khiển bởi các hệ thống mà thay vào đó, nó ln có sự
tham gia của con người và những hành vi của con người cũng đóng vai trị rất quan trọng
đối với hiệu suất của các q trình. Do đó việc khai thác vào khía cạnh tổ chức như việc
phát hiện cấu trúc tổ chức hay mạng lưới xã hội sẽ giúp những người quản lý nắm rõ
được cấu trúc tổ chức và giúp cải thiện quá trình kinh doanh.

nhiều dữ liệu sự kiện được ghi nhận lại, do đó cung cấp thơng tin ngày càng chi tiết về
lịch sử của quá trình. Mục tiêu của khai phá quá trình là nhằm phát hiện, giám sát và cải
thiện các q trình thực tế bằng cách trích lọc tri thức từ các nhật ký sự kiện đã có sẵn
trong các hệ thông thông tin ngày nay [11]. Các ứng dụng của khai phá quá trình đã được
áp dụng vào rất nhiều miền ứng dụng khác nhau, trong đó nổi bật nhất là quản lý quá
trình kinh doanh.
Các kỹ thuật khai phá dữ liệu cổ điển như phân lớp, phân cụm, học luật kết hợp,
khai phá dãy không tập trung vào các mơ hình q trình kinh doanh và thường chỉ được
sử dụng để phân tích một bước cụ thể trong q trình tổng thể [11]. Trong khi đó, khai
phá q trình tập trung vào các quá trình end-to-end và ngày càng phát triển bởi sự tăng
lên mạnh mẽ của dữ liệu sự kiện cũng như sự xuất hiện của các kỹ thuật phát hiện quá
trình và kiểm tra sự phù hợp mới.
Sự quan tâm tăng lên trong phân tích quá trình đã thúc đẩy việc thành lập Đội đặc
nhiệm IEEE về khai phá quá trình (IEEE Task Force on Process Mining: IEEE-TFoPM).
Gần đây Đội đặc nhiệm về khai phá quá trình đã đưa ra tun ngơn về khai phá q
trình. Tuyên ngôn này được hỗ trợ bởi 53 tổ chức và 77 chuyên gia về khai phá quá trình
[11].
Hình 1.1. cho thấy khai phá quá trình thiết lập các liên kết giữa các quá trình thực
tế và dữ liệu ở một bên và các mơ hình q trình ở bên kia. Hệ thống thông tin ngày nay
phải đối mặt với sự gia tăng khơng ngừng cả về mặt số hóa và vật lý ( công nghệ vật
liệu). Nhất là về mặt số hóa, hệ thống thơng tin ngày nay ghi lại nhật ký với số lượng rất
lớn các sự kiện. Các hệ thống WFM ( Workforce Management ) như Staffware hay Cosa,

2


Hình 1. 1. Ngữ cảnh khai phá quá trình [11]

các hệ thống BPM ( Business Process Management ) như BPM|One của Pallas Athena,
SmartBPM của Pegasystems, ... cung cấp một lượng thông tin chi tiết và rất lớn về các

Một cách tổng qt hóa nhật ký sự kiện về nhật ký sự kiện đơn giản được W.M.P
Van der Aalst định nghĩa trong [10] theo toán học như sau:
 Cho A là một tập những hành động trong nhật ký sự kiện, một vết hay trường
hợp(trace) là một chuối các hành động, tức là σ ∊
một đa tập (multi-set) trên tập A tức L∊ B(

. Một nhật ký sự kiện đơn giản L là

).

Trong đó khái niệm đa tập trên tập A có thể hiểu như là nhật ký sự kiện đơn giản L
là một tập hợp của các vết σ, trong đó mỗi dấu vết σ được thể hiện kèm chỉ số số lần dấu
vết đó được thực thi trong nhật ký sự kiện.
Ví dụ: A = {a,b,c,d,e} có ba vết
lần , và
sau:

= (a,b,c,d) xảy ra 3 lần,

= ( a,c,b,d) xảy ra 2

= (a,e,d) xảy ra 1 lần. Khi đó nhật ký sự kiện L được biểu diễn dưới dạng như

L = [ (a,b,c,d)3, (a,c,b,d)2, (a,e,d)]
Tuy nhiên, có thể dễ dàng cách biểu diễn nhật ký theo dạng như vậy chỉ quan tâm
vào khía cạnh luồng sự kiện và đã bỏ qua các thuộc tính của sự kiện khác.
4


Bảng 1. 1. Một đoạn trong nhật ký sự kiện mỗi dòng tương ứng với mỗt sự kiện [10]

được mơ hình hóa) và ngược lại.

Tăng cường mơ hình
Cuối cùng là bài tốn tăng cường mơ hình. Bài tốn này hướng tới việc cải tiến hay
mở rộng mơ hình bằng cách khai thác các khía cạnh khác trong nhật kí sự kiện mà trước
đó đã bị lược bỏ trong bài tốn phát hiện q trình. Chẳng hạn như thời gian, nguồn của
sự kiện, v.v…

Hình 1. 3. Ba bài tốn trong khai phá quá trình dưới dạng input và output bao gồm:
Phát hiện quá trình (a), Kiểm tra sự phù hợp (b) và Tăng cường mơ hình (c) [10]

7


1.4. Bài tốn phát hiện mơ hình tổ chức
Hầu hết những phương pháp nghiên cứu khai phá quá trình đều tập trung vào việc
phát hiện luồng điều khiển, xây dựng một mơ hình q trình dựa trên nhật ký sự kiện
trong khi các khía cạnh khác thường bị bỏ qua, chẳng hạn khía cạnh: thời gian liên quan
đến thuộc tính thời gian (timestamp), tổ chức liên quan đến thuộc tính nguồn (resource),...
Tuy nhiên, trong thực tế, các q trình khơng hoàn toàn bị điều khiển bởi các hệ thống mà
thay vào đó, nó ln có sự tham gia của con người và những hành vi của con người cũng
đóng vai trò rất quan trọng đối với hiệu suất của các q trình. Do đó việc khai thác vào
khía cạnh tổ chức như việc phát hiện cấu trúc tổ chức hay mạng lưới xã hội cũng đóng
một vai trị hết sức quan trọng, bởi nó sẽ giúp những người quản lý nắm rõ được cấu trúc
tổ chức và giúp cải thiện q trình kinh doanh [9]. Đó là lý do bài tốn khai phá khía cạnh
tổ chức được đưa ra.
Một trong những vấn đề quan trọng nhất trong khai phá khía cạnh tổ chức là việc
phát hiện cấu trúc tổ chức để phục vụ cho việc phân tích. Cấu trúc tổ chức sẽ được phát
hiện dưới dạng các mơ hình mạng lưới thể hiện mối quan hệ giữa các cá nhân, các nhóm,
... với nhau.

Handover of work metric:
Độ đo này xác định mức độ chuyển giao cơng việc giữa các cá nhân bằng việc trích
lọc từ nhật ký sự kiện theo thứ tự thực hiện cơng việc trong từng trường hợp, trong đó
hành động đầu tiên được hồn thành bởi một cá thể nào đó, sau đó quy trình được tiếp tục
với hành động tiếp theo và được hoàn thành, cứ như vậy một trường hợp được hồn
thành với sự chuyển giao cơng việc giữa các cá thể.
Subcontracting metric:
Độ đo này tương tự với Handover of work metric, tuy nhiên trong handover of work
metric mối quan hệ giữa hai cá thể là một chiều thì trong Subcontracting metric mối quan
hệ giữa hai cá thể là hai chiều. Ví dụ cá nhân A subcontract cá nhân B khi giữa 2 hành
động thực hiện bởi A có một hành động được thực hiện bởi B.
Working together metric:
Hai cá nhân A và B làm việc cùng nhau khi họ thực hiện các hành động trong cùng
một trường hợp. Độ đo này đơn giản chỉ đếm số lượng các trường hợp mà 2 cá nhân làm
việc cùng nhau.
Similar task metric:
Kỹ thuật này tập trung vào hành động chung, mục tiêu của kỹ thuật này là xác định
xem các cá thể thực hiện bao nhiêu hành động giống nhau trong nhật ký sự kiện. Để thực
hiện kỹ thuật này, mỗi một cá thể sẽ được thống kê số lần thực hiện các hành động cụ
thể, sau đó các cá thể được so sánh với nhau để tìm ra sự tương đồng.
Reassignment metric:
Kỹ thuật này phát hiện mức độ ủy thác hành động từ cá nhân này đến cá nhân khác.
Ví dụ như nếu cá thể A thường ủy thác công việc cho cá thể B và khơng có việc B ủy
thác cơng việc cho A thì có thể A là cấp trên của B.

2.1.3. Các cách tính khoảng cách giữa các tổ chức
Khoảng cách giữa các tổ chức ( hay các cụm ) được tính dựa trên khoảng cách giữa

10



2.2. Các thuật tốn phân cụm trong phát hiện mơ hình
tổ chức
Mặc dù có rất nhiều thuật tốn phân cụm với các cách tiếp cận khác nhau, tuy nhiên
theo [10], hai thuật tốn thơng dụng thường được sử dụng là AHC và K-means. Sau đây
tơi xin trình bày nội dung của hai thuật toán này và một biến thể của thuật toán K-means
là K-medoids sẽ được dùng cho nội dung thực nghiệm ở chương sau.
2.2.1. Thuật toán AHC
Thuật toán AHC là một trong hai loại của thuật toán phân cụm phân cấp bao gồm:

12


 Tích đống (Agglomerative hierarchical clustering hay AHC ) là hướng tiếp cận từ
dưới lên với khởi tạo ban đầu mỗi phần tử thuộc về một cụm riêng của nó và tiến
hành gộp dần các phần tử lại trong quá trình lặp.
 Phân chia (Divisive hierarchical clustering ) là hướng tiếp cận từ trên xuống,
khởi tạo ban đầu với chỉ một cụm và tiến hành chia nhỏ cụm đó để tạo các cụm mới
trong quá trình lặp.
Tuy nhiên, với mục tiêu phát hiện mơ hình tổ chức từ các đơn vị cá thể ( người thực
hiện) , thuật toán AHC sẽ hữu ích hơn thuật tốn cịn lại. Nội dung cụ thể của thuật toán
như sau [3]:
Cho trước mạng gồm N node:
Bước 1.Mỗi node được coi như là một cụm ( N cụm gồm 1 phần tử )
Bước 2. Tìm cặp cụm gần nhau nhất và gộp chung chúng thành một cụm.
Bước 3.Tính lại khoảng cách giữa cụm mới với các cụm cũ.
Bước 4. Lặp lại bước 2 và 3 cho đến khi tất cả các phần tử đã được gộp lại thành
một cụm duy nhất N phần tử hoặc đã đạt số lượng cụm yêu cầu.

2.2.2. Thuật toán K-means

Bước 3.2.Hốn đổi M và O và tính tốn lại hàm mục tiêu cho sự hốn
chuyển này.
Bước 4. Chọn sự hốn chuyển có hàm mục tiêu đạt nhỏ nhất
Bước 5.Lặp lại các bước từ 2 đến 4 cho đến khi khơng có sự thay đổi về trọng tâm.
Hàm mục tiêu được tính như sau:

E=∑

∑

∊

2.3. Các độ đo chất lƣợng phân cụm
Theo [5] và [8], các độ đo chất lượng phân cụm được phân thành 3 loại là:
Đánh giá trong ( internal evaluation): Kết quả phân cụm được đánh giá dựa trên
chính dữ liệu được phân cụm bằng cách sử dụng các đại lượng đánh giá sự gắn kết
cụm như mật độ ( density), khoảng cách giữa các phần tử bên trong cụm hay
khoảng cách giữa các cụm với nhau, ... Hướng tiếp cận của loại này dựa trên tiêu

14