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

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

Hà Nội - 2016


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

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Trí Thành

Hà Nội - 2016

Cuối cùng, em xin được cảm ơn cha mẹ, người thân, ban bè và đồng
nghiệp của em tại Sở Nông nghiệp và PTNT tỉnh Hưng Yên, những người đã
luôn bên em, khuyến khích và động viên em trong cuộc sống và học tập.
HỌC VIÊN

Nguyễn Thị Hồng Hạnh


3

MỤC LỤC
DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ....................................................... v DANH
MỤC CÁC BẢNG................................................................................... vi MỞ ĐẦU
............................................................................................................... 7
CHƯƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH ................................ 9
1.1 Khai phá quy trình........................................................................................ 9
1.1.1 Sự cần thiết của KPQT ........................................................................ 10
1.1.2 Mục tiêu của KPQT ............................................................................. 11
1.1.3 Mô hình quy trình và nhật ký sự kiện .................................................. 11
1.1.4 Các bài toán KPQT .............................................................................. 12
1.1.5 Các khía cạnh của KPQT ..................................................................... 13
1.1.6 Các ứng dụng của KPQT ..................................................................... 14
1.1.7 Một số thách thức đối với lĩnh vực KPQT .......................................... 14
1.2 Khía cạnh tổ chức trong KPQT.................................................................. 15
1.3 Bài toán toán khai phá khía cạnh tổ chức .................................................. 18
1.3.1 Trong thực tế ........................................................................................ 18
1.3.2 Trong luận văn ..................................................................................... 18
1.4 Ý nghĩa của luận văn.................................................................................. 20
1.4.1 Về mặt khoa học .................................................................................. 20
1.4.2 Về mặt thực tiễn ...................................................................................

4.1.2 Phần mềm và tập dữ liệu đầu vào ........................................................
46
4.2 Chương trình thực nghiệm ......................................................................... 47
4.3 Kết quả thực nghiệm và đánh giá .............................................................. 48
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TƯƠNG LAI ................................... 51
TÀI LIỆU THAM KHẢO................................................................................... 52


55

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT
STT
I
1
2
3
4
5
6
II
1
2
3
4
5
6
7
8
9
10

Busines - to - Business
Back - propagation neural network
Customer Relationship Management
Event - driven Process Chain
Systems for Enterprise Resource Planning
Normalized mutual informaton
Supply Chain Management
Unweighter Pair - Group Method using Arithmetic averages

Workflow Management
eXtensible Event Stream
EXtensible Markup Language


66

DANH MỤC CÁC BẢNG
Bảng 2.1 So sánh các loại cấu trúc cộng đồng.................................................... 24
Bảng 2.2 Các phương pháp tính khoảng cách hai cụm....................................... 26
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 ....................
36
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 .....
40
Bảng 3.3 Ma trận �� mối quan hệ .....................................................................
40
Bảng 3.4 Ma trận đỉnh kề �� .............................................................................
41
Bảng 3.5 Danh sách đỉnh kề................................................................................ 42
Bảng 3.6 Ma trận �� độ tương tự.......................................................................
43

Hình 3.8 Các cộng đồng đỉnh chồng chéo .......................................................... 44
Hình 4.1 Kết quả chương trình thực nghiệm ...................................................... 47


7

MỞ ĐẦU
Trong môi trường cạnh tranh hiện nay, yếu tố cốt lõi của các tổ chức,
doanh nghiệp là truy cập thông tin, nghiệp vụ một cách nhanh chóng, hiệu
quả và đạt chi phí tối ưu. Kinh doanh thông minh bao gồm các công nghệ và
công cụ để chuyển đổi những dữ liệu thô thành những thông tn có nghĩa và có
ích cho mục đích phân tích kinh doanh, là các ứng dụng và công nghệ để
chuyển dữ liệu doanh nghiệp thành hành động. Với sự gia tăng các hệ thống
tích hợp thông tin từ quá trình kinh doanh như WFM, ERP, CRM, SCM và B2B,
… đã tạo ra cách thức tiếp cận mới trong việc phân tích dữ liệu lớn (big data).
Khai phá quy trình (KPQT) kinh doanh hay KPQT là cầu nối quan trọng giữa khai
phá dữ liệu với quản lý quá trình kinh doanh [12]. Các kỹ thuật này giúp trích
lọc các thông tn có giá trị hay các thông tn mà các doanh nghiệp cần từ tập
nhật ký sự kiện được lưu trong các hệ thống tích hợp thông tin, giúp bổ sung
vào các tiếp cận hiện có để quản lý quy trình kinh doanh. Bài toán KPQT gồm ba
bài toán nhằm cải thiện quy trình kinh doanh và để mở rộng mô hình quy trình
(MHQT) cần bổ sung ba khía cạnh: tổ chức, thời gian và trường hợp[1].
Khía cạnh tổ chức bao gồm nhiều kỹ thuật có giá trị như 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 bao gồm những kỹ thuật khai phá đượ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 tch 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 hiện có
trong tổ chức của họ. Trong mô hình MXH, các đỉnh đại diện cho phòng, đơn vị
hay con người, mối quan hệ giữa các đỉnh được biểu diễn dưới dạng cạnh. Vấn

3. Xây dựng chương trình thực nghiệm dựa trên mô hình đề xuất
trong luận văn và đánh giá kết quả thu được.
Bố cục của luận văn bao gồm phần mở đầu, bốn chương nội dung, phần
kết luận và phương phát triển tương lai, danh mục tài liệu tham khảo.
Chương 1. Tổng quan về KPQT: Giới thiệu tổng quan về KPQT, trong
đó trình bày chi tiết các vấn đề liên quan đến khía cạnh tổ chức và phân tích
phương pháp phát hiện MXH từ nhật ký sự kiện. Phần chính của Chương này là
phát biểu bài toán cần xử lý và đưa ra phương pháp giải quyết. Từ đó, có những
nhận định về ý nghĩa thực tễn, ý nghĩa khoa học của luận văn.
Chương 2. Các giải thuật tìm kiếm cộng đồng trong MXH: Giới thiệu
các loại giải thuật tìm kiếm và đặc biệt là các giải thuật tm kiếm cộng đồng
chồng chéo. Sau đó, Tác giả sẽ lựa chọn giải thuật tìm kiếm cộng đồng chồng
chéo sẽ áp dụng vào bài toán KPQT. Phân tch chi tiết giải thuật Phân vùng theo
cạnh của nhóm tác giả Ahn et al. đưa ra vào năm 2010 [4].
Chương 3. Áp dụng các giải thuật tìm kiếm cộng đồng vào bài toán
KPQT: Đề xuất mô hình giải quyết bài toán và đưa ra định dạng dữ liệu đầu vào
các độ đo được sử dụng trong mô hình. Phân tích chi tiết các bước thực
hiện trong mô hình. Kết quả của quá trình này tm 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.


10

CHƯƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH

Ý tưởng KPQT được các nhà khoa học Cook và Wolf đã nghiên cứu các
từ năm 1998. Sau đó, Herbst và Karagianis cũng đưa các vấn đề KPQT trong nội
dung liên quan quản lý luồng công việc. Trong hội thảo về kinh doanh thông
minh, KPQT cũng được các nhà khoa học đề cập trong các nội dung quản lý


11

kinh doanh. Những đóng góp lớn tới lĩnh vực này đã được thêm vào sau bởi Wil
M.P. Van der Aalst và các cộng sự. Nhóm nghiên cứu đã đưa ra các thuật toán
khai phá đỉnh cao và sự thêm đa dạng các chủ đề liên quan tới các thách
thức


12

trong các quy trình kinh doanh. Do vậy, các nhà khoa học và người nghiên cứu
lĩnh vực này có thể dễ sử dụng nhiều phương pháp và công cụ có sẵn.
Quản lý quy trình kinh doanh là một lĩnh vực kết nối giữa tri thức công
nghệ thông tn và khoa học quản lý, áp dụng những tri thức này vào quá trình
điều hành kinh doanh [1]. Những năm gần đây, KPQT đã nổi lên và trở thành
lĩnh vực nghiên cứu đầy tiềm năng, 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 […] Giúp phát hiện, giám sát và cải thiện các quy trình thực bằng cách
trích lọc tri thức từ các nhật ký sự kiện” [1] được lưu trong các HTTT. KPQT là
một khái niệm bao gồm tất cả các phương pháp trích xuất các mô hình quy
trình có cấu trúc từ một tập các công việc trong thực tế [8]. Cụ thể, các kỹ
thuật này giúp trích lọc các thông tn có giá trị và liên quan đến quy trình từ các
tập nhật ký sự kiện. Tuy nhiên, các tổ chức gặp phải các vấn đề về giá trị trích
lọc từ những dữ liệu này [28].

quyết có thể không phù hợp với thực tế. KPQT giúp các doanh nghiệp có cơ sở
tin tưởng những giải pháp cho những vấn đề phức tạp của doanh nghiệp.
1.1.2 Mục tiêu của KPQT: Mục têu chính của KPQT là phát hiện, phân
tch và hiểu các quy trình kinh doanh dựa trên các bản ghi các hoạt động tại
thời một thời điểm xác định, thông tin này được lưu trong các tập nhật ký sự
kiện. KPQT giúp trích lọc các thông tin liên quan, phát hiện ra mô hình quy trình
mới từ các dữ liệu sự kiện, được lưu trong các HTTT lớn [1]. Quá trình này bao
gồm các kỹ thuật, công cụ và phương thức để phát hiện, giám sát, cải thiện các
quy trình trong thực tế [36].
1.1.3 Mô hình quy trình và nhật ký sự kiện:
a) Mô hình quy trình (MHQT): Trong bối cảnh khoa học HTTT, một mô
hình là đại diện phi vật chất của thế giới thực, được sử dụng cho một mục
đích cụ thể [31]. Các mô hình được sử dụng để làm giảm độ phức tạp bằng cách
biểu diễn những đặc trưng được quan tâm, bỏ qua những đặc trưng khác. Một
MHQT là sự biểu diễn hình học của một quy trình kinh doanh, mô tả sự ràng


15

buộc giữa các công việc cần được thực hiện trong những kế hoạch kinh
doanh. MHQT là


16

một tập các mô hình biểu diễn các hoạt động của công ty và sự ràng buộc giữa
các mô hình [29]. Các mô hình này có thể được biểu diễn dưới dạng BPNN,
EPC hoặc lưới Petri. Nếu các mô hình được xây dựng theo phương pháp thủ
công, độ tn cậy không cao do những yếu tố chủ quan. Để đảm bảo được sự tin
cậy của MHQT, phương pháp khai phá dữ liệu lưu trong các HTTT được đưa ra.



17

Đầu vào: Mô hình quy trình hiện có, Nhật ký sự kiện.


18

Đầu ra:Mô hình quy trình được bổ sung.

Hình 1.3 Các bài toán KPQT
Hình 1.3 biểu diễn sự tương tác giữa KPQT, dữ liệu nhật ký sự kiện và
nền tảng phân tích. Khai phá nhật ký sự kiện hay sự các quy trình kinh doanh
thực để phát hiện ra sự tắc nghẽn, đứt đoạn của quy trình. Trong KPQT,
sự tương tác giữa những thực thể theo một quy luật logic, do đó những kết quả
của lĩnh vực này mang lại là rất lớn đối với lĩnh vực kinh doanh thông minh.
1.1.5 Các khía cạnh của KPQT: Mở rộng MHQT khi bổ sung các khía cạnh,
bao gồm:
Khía cạnh tổ chức: tập trung vào các thông tin về các nguồn tài nguyên ẩn
dưới các nhật ký. Các nguồn tài nguyên này bao gồm con người, hệ thống hay
vai trò hay bộ phận liên quan và sự liên hệ giữa các yếu tố đó. Mục tiêu của
khía cạnh này là để xây dựng cấu trúc tổ chức bằng cách phân lớp người
tham gia quy trình theo vai trò, đơn vị, đồng thời biểu diễn MXH.
Khía cạnh trường hợp: Tập trung vào các thuộc tính riêng của các trường
hợp như số người tham gia, thứ tự thực hiện các hoạt động, những người
tham gia, … Từ đó thiết lập mối quan hệ giữa những thuộc tnh này, tạo đầu
vào cho các giải thuật phân cụm.
Khía cạnh thời gian: Liên quan đến thời gian và tần suất xuất hiện của các
sự kiện. Từ lịch biểu thời gian xảy ra các sự kiện giúp phát hiện các đoạn “nút

bảo đảm quá trình, giảm thiểu sai sót, kiểm soát chất lượng dịch vụ.


20

- Các bản ghi sự kiện bị lỗi và thiếu: Đối với các bản ghi không chính xác
của nhật ký sự kiện có thể được sinh ra do sự cố phần mềm, đột biến
người dùng, lỗi phần cứng hoặc bị cắt xén các trường hợp của quy trình trong
lúc trích lọc dữ liệu. Các bản ghi bị sai trong nhật ký sự kiện được coi là một biểu
hiện lạ trong một hiện tượng được gọi là bản ghi bị lỗi. Các bản ghi bị lỗi được
lưu lại chính xác và thường hiếm khi xảy ra [1]. Các bản ghi sự kiện lỗi này sẽ làm
tăng độ phức tạp của mô hình quy trình. Các đề xuất KPQT vì thế mà đưa ra
những sự phân tích và mô hình không đúng.
- Chất lượng nhật ký sự kiện: Việc thu thập dữ liệu và tiền xử lý dữ liệu là
một thách thức trước khi bắt đầu KPQT, vì chất lượng của dữ liệu ảnh hưởng
lớn đến kết quả của KPQT. Chất lượng của các nhật ký sự kiện sẽ ảnh hưởng
chủ yếu tới chất lượng khai phá và tái cấu trúc các mô hình quy trình. Các hệ
thống quy trình kinh doanh và quản lý luồng công việc tạo ra các nhật ký sự kiện
với chất lượng cao nhất [36].
- Mô hình quy trình phức tạp: Các quy trình trong thực tế thường
rất phức tạp. Việc biểu diễn chúng bằng hình học có thể dẫn các mô hình
có độ phức tạp cao và rất khó hiểu. Hai mô hình quy trình phức tạp điển hình
được gọi là quy trình Lasagna và Spaghetti [1]. Giảm độ phức tạp của mô hình là
một thách thức lớn và đang là đối tượng nghiên cứu ngày nay [23].
- Các loại hình quy trình: KPQT chỉ có thể được áp dụng đối với các quy
trình được kiểm soát hoàn toàn bằng HTTT. Trong thực tế, các quy trình chỉ cần
được quan sát dưới một số hình thức. Đối với một số hệ thống quản lý quy trình
kinh doanh theo mô hình và cấu hình định sẵn thường ít có giá trị đối với việc
phát hiện lại các luồng tiến trình. Thông thường, các bộ phận trong một
quy trình là tự động, một số bộ phận được điều khiển bởi con người. Do vậy, rất

- Vai trò KCTC: Các kỹ thuật này giúp phát hiện cấu trúc tổ chức, phân
tch MXH, cấp phát tài nguyên và khai phá vai trò từng cá thể, nhóm hay tổ
chức trong MXH. Khai phá khía cạnh tổ chức là phân tích những thông tin được
tết lộ từ khía cạnh tổ chức. Kỹ thuật này bao gồm việc phát hiện các MXH, cấu
trúc tổ chức và hành vi của tổ chức [2]. Các kỹ thuật khai phá này tạo nên nền
tảng đối với các nhiệm vụ sau:
+ Chứng thực: tập trung vào kiểm soát truy nhập giúp đảm bảo chỉ những
cá nhân, đơn vị nào được chứng thực có vai trò mới được phép thực hiện
các hoạt động trong quy trình.
+ Kiểm soát tài nguyên: tập trung vào những ràng buộc sau khi truy nhập
dữ liệu như người hay nhóm người sẽ nắm giữ và sử dụng dữ liệu.
+ Tái cơ cấu tổ chức:
Phân tách: ràng buộc liên quan tới quy trình giới hạn các khả năng của
các đơn vị khi thực hiện các hoạt động, giúp giảm rủi ro khi gặp lỗi.
Sát nhập: đây là sự ràng buộc hai chiều, sắp xếp các chủ thể, tác vụ vào
cùng một nhóm các hoạt động cụ thể.