Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
1
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN MÔN HỌC
KHAI THÁC DỮ LIỆU ĐỒ THỊ
Giảng viên phụ trách : PGS. TS. Đỗ Phúc
Học viên thực hiện : Châu Kim Hùng – CH1101013
Lớp : CH.CNTT.K6
Khóa : 06
Tp HCM, Tháng 08 năm 2012
Page 1
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
2
Tóm tắt
Để tìm kiếm giải pháp và phương hướng giải quyết và khắc phục những hạn chế
trong các quá trình xử lý khai thác dữ liệu trên đồ thị, người ta đã đưa ra nhiều phương
pháp để giải quyết bài toán, nó tập trung vào hướng nghiên cứu giải quyết vấn đề về đẳng
cấu đồ thị, đẳng cấu đồ thị con và tìm sự tương đồng của đồ thị, nhưng còn nhiều hạn chế
về thời gian tìm kiếm và lưu trữ dữ liệu cho phù hợp.
Với những lý do nêu trên, đồ án này tập trung nghiên cứu cài đặt lại những
phương pháp, giải thuật đã được nghiên cứu trước đó để có sự tiếp cận rõ hơn về khai
thác dữ liệu đồ thị, tạo tiền đề để nghiên cứu sau này.
Page 2
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
3
MỤC LỤC
Chương 1

để phục vụ cho lĩnh vực khai thác dữ liệu – khai thác dữ liệu đồ thị. Đây là một trong
những hướng nghiên cứu mới có nhiều tiềm năng, ứng dụng trong cuốc sống ngày nay.
Nổi bật là hướng nghiên cứu về phân tích mạng xã hội trên đồ thị, sự tương đồng trong
thành phần hóa học – cấu trúc - chức năng có liên quan mật thiết với nhau trong lĩnh vực
hóa sinh.
Vì việc tiếp cận và thực hiện chuyên đề trong khoảng thời gian ngắn, nên chuyên
đề này tập trung nghiên cứu, phân tích ưu nhược điểm, phân tích đặc điểm những hướng
nghiên cứu trước đó và cài đặt lại những phương pháp, giải thuật đó để có sự tiếp cận rõ
hơn về bài toán tìm đẳng cấu đồ thị và đẳng cấu đồ thị con trong lĩnh vực khai thác dữ
liệu đồ thị, tạo tiền đề để nghiên cứu sau này.
Page 4
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
5
Chương 2
TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU ĐỒ THỊ
2.1.Cơ sở lý thuyết
2.1.1. Đẳng cấu đồ thị
Hai đồ thị có chứa cùng số đỉnh, và các đỉnh có liên kết với nhau theo một cách
nào đó giống nhau thi được gọi là đẳng cấu.
Định nghĩa toán học, hai đồ thị G
1
= (V
1
, E
1
) và G
2
= (V
2

.
φ (1) = can, φ (2) = cat, φ (3) = car, φ (4) = ear.
Hình 2.1 hai đồ thị đẳng cấu
Hai đồ thị đẳng cấu thì ta có:
- Cùng số đỉnh
Page 5
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
6
- Cùng số đỉnh bậc k, với mọi k nguyên dương
- Cùng số cạnh
- Cùng số thành phần
 Nếu hai đồ thị có ma trận kề bằng nhau, thì chúng đẳng cấu với nhau.
2.1.2. Đẳng cấu đồ thị con
Một đồ thị G
’
là một đồ thị con của một đồ thị G cho trước nếu số đỉnh và số cạnh
của G
’
thỏa tập con của số đỉnh và số cạnh của G.
Một đồ thị G
1
= (V
1
, E
1
) là đẳng cấu với một đồ thị con của một đồ thị G
2
= (E
2

trong P đến một đỉnh trong G (hình 2.4).

Hình 2.4 một cây tìm kiếm cho giải thuật Ullman, ánh xạ từ đồ thị mẫu P đến đồ
thị dữ liệu G. Đường tô đen trình bày sự so khớp của P trong G.
Mỗi nhánh từ gốc đến node lá trong cây tìm kiếm trình bày một ánh xạ các đỉnh
trong P đến các đỉnh trong G. Bất kỳ ánh xạ nào mà duy trì tính kề trong P và trong G
( các đỉnh kề nhau trong P ánh xạ với các đỉnh kề nhau trong G) thể hiện một đằng cấu từ
P đến một đồ thị con của G. Nếu không tồn tại bất cứ nhánh nào thỏa điều kiện trên thì
không tôn tại đẳng cấu. Vì không gian tìm kiếm tỉ lệ với kích thước đồ thị nhập vào tăng
theo hàm mũ, Ullman đề xuất các bước tinh lọc, cắt tỉa không gian tìm kiếm ở các cây
con, loại ra những nhánh không thể ánh xạ, để thu hẹp không gian tìm kiếm.
Các tiêu chuẩn để có thể thu hẹp không gian tìm kiếm:
- Bậc của đỉnh: nếu bậc của đỉnh Vertex V
pi
(số cạnh có nối với đỉnh V
pi
) lớn
hơn bậc của đỉnh V
Gj
thì V
Pi
không thể ánh xạ đến V
Gj
. Ví dụ, V
p1
không thể
ánh xạ với V
G4
, vì degree(V
P1

p2
đến V
G3
không phù hợp tính liên
thuộc vì V
P1
và V
P2
là hai đỉnh kế nhau trong P, nhưng V
G1
và V
G3
không kế
nhau trong G. Vì vấy ta loại bỏ trường hợp ánh xạ từ V
P2
đến V
G3
.
 Khi ta duyệt trong cây tìm kiếm nếu trương hợp nào không thỏa một trong ba
tiêu chuẩn trên thì ta bỏ tất cả nhánh con liên quan tới nó.
 Ưu điểm
Tuy ý tưởng của giải thuật cảu Ullman là duyệt trên không gian tìm kiếm là một
cây tìm kiếm được dựng từ đồ thị dữ liệu, nhưng thực chất là ta duyệt trên một cây gián
tiếp chứ không dựng cây, bởi vì việc dụng cây như thế chi phí là n! ( n là số đỉnh của đồ
thị mẫu). Trong quá trình duyệt cây tại mỗi node mà nó không thỏa một trong ba tiêu
chuẩn được Ullman đề xuất ở trên thì ta loại tất cả các nhánh con của node đó, thu gọn
không gian tìm kiếm,ta có thể dừng một cách an toàn không cần phải mở rộng các node
con sau đó và tránh được trường hợp quay lui, tiết kiệm được rất nhiều thời gian.
Đối với trường hợp kiểm tra sự đẳng cấu giữa hai đồ thị mà chúng ít tương đồng
với nhau thì việc cắt tỉa thu gọn được không gian tìm kiếm rất hiệu quả (không phải đi

), trong đó:
- V là tập đỉnh của đồ thị
- E là tập cạnh của đồ thị
- μ: V -> L
V
hàm gán tên cho đỉnh
- ν: E -> L
E
hàm gán tên cho cạnh
Rõ ràng, ma trận M thì không phải là ma trận kề duy nhất biển diễn cho đồ thị G.
Nếu M là biễu diển của G, thì bất kỳ hoán vị nào của M cũng đều là biễu diễn của G.
Định nghĩa: một ma trận n x n P = (p
ij)
thì được gọi là ma trận hoán vị nếu
1. p
ij
€ {0,1}

với i, j = 1 n
2. với j = 1 n
3. với j = 1 n
Nếu ma trận G được biểu diễn bởi một ma trận kề M (n x n) và P ma trận hoán vị
n x n, thì ma trận M
’
(n x n)
M
’
= P.M.P
T
(1)

cấp của mỗi node trong cây quyết định thì giá trị để phân lớp đồ thị là các thành phần của
dòng m cột n trong ma trận kề. Nếu tại mỗi node của cây mà các thành phần dòng cột của
các ma trận kề giống nhau thi chúng được gom chung thành một nhóm, đảm bảo theo cây
phân cấp từ trên xuống của cây quyết định (hình 2.5).
Hình 2.5 cây quyết định cho phân lớp của các ma trận kề A F của đồ thị g
1
Một yêu cầu quan trọng của cây quyết định là sự phân lớp tại mỗi cấp phải được
tính một cách dễ dàng. Bên cạnh đó, nêu một ma trận M
P
thì được phân lớp theo thành
Page 10
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
11
phần dòng cột thứ k a
k
, những nhánh con co cùng phân lớp từ a
k ,
với a
ki
= a
k
thì cúng
phải được tính một cách dễ dàng. Thật vậy, ta thấy các thành phần dòng cột thứ k có
chính xác 2k-1 yếu tố m
ij
từ dòng thứ k cột thứ k trong ma trận kề và mỗi thành phần đó
được dùng như một chỉ mục. Để tìm một thành phần trong a
k
ta có thể thực hiện trong

lớp tại mỗi node của cây quyết định. Đồ thị nhập sẽ được phân lớp bởi cây quyết định với
toàn bộ tập dữ liệu đồ thị nếu ở đó tồn tại đẳng cấu đồ thị con tại một node, các đồ thị có cùng
phân lớp với đồ thị nhập thuộc các nhánh hướng trực tiếp từ node mà ở đó tồn tại đẳng cấu đồ thị
con.
 Ưu điểm
Như ta đã thấy phép duyệt trên cây quyết định là tối hơn hơn phép duyệt trên cây
tìm kiếm của Ullman là rất nhiều. Phép duyệt trên cây quyết định chỉ đi theo một hướng
duy nhất, không đổi hướng, quay lui. Và đồ thị nhập đẳng cấu đồ thị con với đồ thị trong
dữ liệu tại một node trên một nhanh đi duy nhất, nếu không tôn tại node nay thì sẽ không
có đẳng cấu.
Theo Messmer đã phân tích thì độ phức tạp của bước duyệt cây tìm đẳng cấu đồ
thị con khoảng O(M
2
) – M là số đỉnh lớn nhất của một tập dữ liêu đồ thị.
Và việc tìm được đẳng cấu đồ thị con của đồ thị nhập với tập dữ liệu đồ thị nó
đồng thời xác định đồ thị đó thuộc phân nhóm nào của các đồ thị trong dữ liệu. Điều này
rất có lợi cho chúng ta trong những bài toán tìm sự tương đồng, phân lớp độ tương tự,
khai thác được những đặc điểm giống của các đồ thị, như áp dụng trong lĩnh vực phân
tích mạng xã hội…
 Nhược điểm
Như ta đã nói ở đầu bài toán tạm thời bỏ qua việc tiền xử lý xây dựng cây quyết
định từ tập đồ thị. Việc tìm tất cả các trường hợp hoán vị của ma trận kề biểu diển cho
một đồ thị n đỉnh là n!. Xây dựng cây quyết định chi phí tốn ở dạng hàm mũ với số đỉnh
của đổ thị. Và nó thật sự có vấn đề đối với giải thuật này nếu đồ thị với số lượng đỉnh
lớn.
2.2.3. Độ tương tự đồ thị
Page 12
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
13

Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
14
Từ ưu khuyết điểm của hai giải thuật ta thấy tùy vào trường hợp cụ thể ta có thể sử
dụng phương pháp nào cho phù hợp. Tính về tổng thời gian chạy giải thuât của Ullman
và Messmer trong cùng một lúc thì giải thuật của Ullman sẽ tốt hơn, chạy nhanh hơn, vì
trường hợp xấu nhất của Ullman mới rơi vào độ phức tạp ở dạng hàm mũ, trong khi đó ở
bước tiền xử lý khởi tạo cây quyết định của Messmer đã rơi vào độ phức tạp ở dạng hàm
mũ và bước đến bước duyệt cây quyết định mất O(M
2
).
Giải thuật của Ullman còn thích hợp mới một số bài toán cụ thể mà ta có thể dựa
vào đặc trưng của bài toán mà có thể thu gọn được không gian tìm kiếm một cách tốt
nhất. Giải thuật Ullman là nền tảng cơ sở để ta phát triển cho những hướng nghiên cứu
tìm ra những phương pháp mới giải quyết cho bài toán cụ thể nào đó.
Nhưng ta thấy giải thuật Messmer lại được cụ thể hơn và có áp dụng thực tiển hơn.
Tuy hạn chế về mặt dựng cây quyết định nhưng đây chỉ là bước tiền xử lý, còn bài toán
của ta là tìm đẳng cấu đồ thị con, việc tìm đẳng cấu đồ thị con theo cách duyệt cây quyết
định hiệu quả đem lại rất cao. Và trên thực tế thì thường người ta sử dụng việc tìm đẳng
cấu đồ thị con để làm cái gì đó trong tức khắc thì theo Messmer sẽ hiệu quả hơn. Vì ta có
thể tạo cây quyết định từ trước và chỉ dùng nó để tìm sự đẳng cấu.
Và ưu điểm của Messmer nửa là có khả năng phân lớp đồ thị. Điều này rất có
lợi cho chúng ta trong những bài toán tìm sự tương đồng, phân lớp độ tương tự,
khai thác được những đặc điểm giống của các đồ thị, như áp dụng trong lĩnh vực
phân tích mạng xã hội…
Page 14
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
15
Chương 3

Xây dựng một cấu trúc để biểu diển đồ thị bằng ma trận kề, có lưu bậc của từng
đỉnh và số thứ tự của đỉnh trong ma trận.
struct graph
{
public int[,] matrix;
public int[] degree;
public List<int> name;
public graph(int count) { }
}
Xây dựng lớp Ullman xử lý chính cho giải thuật của Ullman có các hàm xử lý:
- Khởi tạo và nhập dữ liệu cho đối tương Graph của đổ thị: khởi tạo hai đối tượng Graph
cho đồ thị mẫu và đồ thị dữ liệu
public void initializesGraphs(string pathA, string pathB,
int vertexA, int vertexB)
- Hàm kiểm tra sự liên thuộc của hai đồ thị: trả về true nếu hai đồ thị liên thuộc, ngược lại
trả về false
private bool forwardChecking( int level, int[] isomorphism)
Page 16
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
17
- Tìm đẳng cấu đồ thị và đẳng cấu đồ thị con: đây là xử lý chính của lớp, hàm sẽ lưu tập
kết quả ánh xạ có thể có của đồ thị.
private void findIsomorphism(List<int> subName, int level)
- Hàm gọi hàm tìm đẳng cấu: gọi hàm findIsomorphism trả về tập kết quả ánh xạ có thể
có của đồ thị.
public ArrayList isoGraph()
 Giao diện chương trình
Giao diện chính của chương trình
Page 17

trường hợp độ thị Mathon thì giải thuật Ullman chạy chậm hơn, trong trường hợp đồ thị
Siberian ta thấy có sự chênh lệch đáng kể vể thời gian thực hiện. Ta có tập kết quả theo
biểu đồ sau.
Hình 3.1 biểu đồ so sánh thời gian thực hiện của giải thuật Ullman với chương
trình theo [4], thời gian được tính theo giây.
3.2.2. Giải thuật Messmer
Để cài đặt giải thuật của Messmer ta tập trung vào việc xử lý hai vấn đề chỉnh là:
xây dựng cây quyết định và duyệt cây tìm sự đẳng cấu.
Việc dựng cây quyết định ta không tạo ra tập ma trận hoán vị từ ma trận kề biểu
diển cho đồ thị một cách tường minh, mà tạo ra một cách gán tiếp trong quá trình theo
node vào cây quyết định, để tiết kiệm chi phí thực hiện n! bước tìm n! hoán vị.
Việc duyệt cây quyết định đơn giản là so sánh tập thành phần dòng cột trong ma
trận nhập với giá trị a
k
tại mỗi node cũng giống như việc theo một node vào cây quyết
định để phân lớp cho nó.
 Xây dựng chương trình
Xây dựng một cấu trúc để biểu diển đồ thị bằng ma trận kề, có lưu bậc của từng
đỉnh và số thứ tự của đỉnh trong ma trận.
struct graph
{
public int[,] matrix;
public int[] degree;
public List<int> name;
public graph(int count) { }
}
Xây dựng lớp Messmer xử lý chính cho giải thuật của Messmer có các hàm xử lý:
- Khởi tạo và nhập dữ liệu cho đối tương Graph của đổ thị: khởi tạo hai đối tượng Graph
cho đồ thị mẫu và đồ thị dữ liệu
public void initializes(string pathA, string pathB, int

Ta thực tế ta thấy nếu chạy trực tiếp giải thuật Messmer thế này thì thời gian thực
hiện là rất lâu nếu không sử dụng chia tiểu trình và xử lý song song. Trong giải thuật
Ullman đồ thị Petersen chạy chưa tới 1 giây thì giải thuật Messmer chạy tới khoảng 30
giây!
Và trong trường hợp tìm đẳng cấu đồ thị con cũng thế. Đồ thị nhập chỉ có 3 đỉnh
và đồ thị dữ liệu là đồ thị Petersen (10 đỉnh) thời gian chạy cũng tới khoảng 30 giây,
tương đương với trường hợp chạy hai đồ thị Petersen ở trên.
Chương 4
Page 22
Trường ĐH Công Nghệ Thông Tin
Khai Thác Dữ Liệu Đồ Thị
23
TỔNG KẾT
Khai thác dữ liệu - khai thác dữ liệu đồ thị là một hướng nghiên cứu triển vọng
ngày nay. Có nhiều ứng dụng trong thực tế, đặc biệt có ý nghĩa trong các ứng dụng sinh,
hóa học, khai thác weblog, phân loại, phân tích mạng xã hội Đã có rất nhiều nhóm
nghiên cứu về lĩnh vực này nhưng hầu hết vẫn chưa giải quyết được vấn đề chính là chi
phí về thời gian, và một số bài toán về đồ thị mà chưa được quan tâm nhiều đến như tìm
sự đẳng cấu giữa hai độ thị con, cái mà gặp nhiều khó khăn nhưng có ứng dụng quan
trọng trong thực tế.
Vì việc tiếp cận và triển khai thực hiện chuyên đề trong khoảng thời gian ngắn,
nên chỉ tập trung vào việc tìm hiểu có một cái nhìn tổng quát về vấn đề, cài đặt thử
nghiệm lại các giải thuật nỗi tiếng đã được nghiên cứu trước đó. Tạo nền tảng cho việc
thực hiện và tìm hướng giải quyết sau này.
Thông qua việc cài đặt và thử nghiệm ta thấy, rõ ràn các giải thuật đều mắc phải là
chưa tối ưu được thời gian thực hiện, cả hai giải thuật thực chất đều bỏ ra chi phí ở dạng
hàm mũ. Vì vậy bài toán này có rất nhiều vấn đề giải quyết.
TÀI LIỆU THAM KHẢO
[1] Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching -
Brian Gallagher