ĐẠ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

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


Event-driven Process Chain
Systems for Enterprise Resource
Planning

NMI

Normalized mutual information

SCM

Supply Chain Management
Unweighter Pair-Group Method using
Arithmetic averages

UPGMA
WFM

Workflow Management

XES

eXtensible Event Stream

XML

EXtensible Markup Language


iv
DANH MỤC CÁC BẢNG

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à

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.

- 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

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:
Loại cấu trúc
Chồng chéo
Không chồng chéo
Một số đỉnh trong
mạng có thể thuộc
Mỗi đỉnh chỉ thuộc 1
nhiều hơn 1 cộng
cộng đồng duy nhất
đồng

TT

Sự mâu thuẫn

1

Đặc điểm



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:
𝑛+ 𝑖 = 𝑖, 𝑘 𝑣à 𝑡ậ𝑝 đỉ𝑛ℎ 𝑘ề 𝑣ớ𝑖 𝑖 ;
𝑛+ 𝑗 = 𝑗, 𝑙 𝑣à 𝑡ậ𝑝 đỉ𝑛ℎ 𝑘ề 𝑣ớ𝑖 𝑗 ;

𝐷𝑙 =

𝑚 𝑙 −(𝑛 𝑙 −1)
𝑛 𝑙 𝑛 𝑙 −1
–(𝑛 𝑙 −1)
2

𝑛ế𝑢 𝑛𝑙 > 2

0 𝑛ế𝑢 𝑛𝑙
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

+ Đố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.


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:
Thông tin tệp XES


Số cộng đồng cạnh

6

Số cộng đồng không
tầm thƣờng

Số Cạnh

6

Số cộng đồng chồng
chéo đỉnh

Số Đỉnh

142

Số Ngƣời tham gia

10

Số Sự kiện

Chapter1.x

Số Trƣờng hợp

Tệp dữ

87

522

5

5

4

1484

13288

442

442

781

BPI2013.x
es

4

7
4

4


576

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

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.
- Giá trị 0
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.



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

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 eventbased 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