i

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

-----------------------------

HOÀNG VIỆT DŨNG

KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN VÀ ỨNG DỤNG

Thái Nguyên, 2018


ii

LỜI CAM ĐOAN
Tôi xin cam đoan số liệu và kết quả nghiên cứu trong luận văn này là
trung thực và chưa sử dụng để bảo vệ luận văn của một học vị nào.
Tôi xin cam đoan mọi sự giúp đỡ cho việc thực hiện luận văn này đã
được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc.
Hà Nội, tháng 05 năm 2018
Tác giả

Hoàng Việt Dũng


iii

LỜI CẢM ƠN
Để hoàn thành luận văn, tôi đã nhận được sự giúp đỡ rất tận tình, sự đóng

góp quý báu của nhiều cá nhân và tập thể.
Trước hết, tôi xin trân trọng cảm ơn Thầy giáo PGS.TS. Nguyễn Long
Giang người đã nhiệt tình hướng dẫn, giúp đỡ tôi trong việc hoàn thành luận
văn này.
Tôi xin trân trọng cảm ơn sự góp ý chân thành của các Thầy, Cô giáo
Viện Công nghệ thông tin, Các thầy giáo, cô giáo Trường Đại học Công nghệ
thông tin và truyền thông - Đại học Thái Nguyên, đã tạo điều kiện thuận lợi cho
tôi thực hiện và hoàn thành đề tài.
Tôi xin cảm ơn đến gia đình, người thân, các đồng nghiệp và bạn bè đã
động viên, giúp đỡ, tạo điều kiện thuận lợi cho tôi trong quá trình thực hiện đề
tài này.
Một lần nữa tôi xin trân trọng cảm ơn !
Hà Nội, tháng 5 năm 2018
Tác giả

Hoàng Việt Dũng


iv

MỤC LỤC
Trang phụ bìa
LỜI CAM ĐOAN .............................................................................................. i
LỜI CẢM ƠN .................................................................................................. iii
MỤC LỤC ........................................................................................................ iv
DANH MỤC CÁC TỪ VIẾT TẮT …..……………………………………. vi
DANH MỤC BẢNG ....................................................................................... vii
DANH MỤC HÌNH ..................................................................................... ixvii
ĐẶT VẤN ĐỀ ................................................................................................... 1
1.1. Sự cần thiết lựa chọn đề tài ........................................................................ 1

1.2. Mục tiêu nghiên cứu của đề tài .................................................................. 3
2. Đối tượng và phạm vi nghiên cứu ................................................................. 3
2.1. Đối tượng ................................................................................................... 3
2.2. Phạm vi nghiên cứu .................................................................................... 3
3. Hướng nghiên cứu của đề tài ........................................................................ 3
4. Cấu trúc của luận văn .................................................................................... 3
Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ ....................... 4
1.1. Tổng quan về khai phá dữ liệu đồ thị......................................................... 4
1.1.1. Tại sao cần khai phá dữ liệu:.................................................................. 4
1.1.2. Các khái niệm khai phá dữ liệu .............................................................. 4
1.1.3. Các chức năng chính của khai phá dữ liệu ............................................. 5
1.1.4. Các công cụ khai phá dữ liệu .................................................................. 6
1.2. Quy trình khai phá dữ liệu đồ thị ............................................................... 7
1.2.1. Hình thành và định nghĩa bài toán ......................................................... 7
1.2.2. Thu thập và tiền xử lý dữ liệu.................................................................. 8
1.2.3. Khai phá dữ liệu và rút ra các tri thức ................................................... 8
1.2.4. Phân tích và kiểm định kết quả ............................................................... 9


v

1.2.5. Sử dụng các tri thức phát hiện được ....................................................... 9
1.3. Các bài toán trong khai phá dữ liệu đồ thị ................................................. 9
1.3.1. Khai phá luật kết hợp .............................................................................. 9
1.3.2. Phân lớp .................................................................................................. 9
1.3.3. Phân cụm ............................................................................................... 10
1.3.4. Dự báo ................................................................................................... 11
1.3.5. Các mẫu tuần tự .................................................................................... 11
1.3.6. Các cây quyết định ................................................................................ 12
1.4. Các ứng dụng của khai phá dữ liệu đồ thị ................................................ 13

1.4.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu ...... 13
1.4.2. Ứng dụng của khai phá dữ liệu ............................................................. 13
Chương 2. CÁC PHƯƠNG PHÁP KHAI PHÁ ĐỒ THỊ CON .................... 15
PHỔ BIẾN....................................................................................................... 15
2.1. Các định nghĩa về đồ thị con phổ biến ..................................................... 15
2.1.1. Giới thiệu về lý thuyết đồ thị ................................................................. 15
2.1.2. Khai phá dữ liệu .................................................................................... 19
2.1.3. Một số phương pháp khai phá dữ liệu ................................................. 21
2.1.4. Khai phá đồ thị con phổ biến ................................................................ 26
2.2. Các phương pháp khai phá đồ thị con phổ biến ....................................... 27
2.2.1 . Thuật toán Apriori để tìm tập con phổ biến ......................................... 27
2.2.2. Thuật toán FSG (Frequency SubGraph Mining) để phát hiện cộng đồng
mạng xã hội ..................................................................................................... 34
2.3. Ứng dụng khai phá đồ thị con phổ biến phát hiện cộng đồng trên mạng xã
hội .................................................................................................................... 39
2.3.1. Cộng đồng mạng xã hội ........................................................................ 39
2.3.2. Các phương pháp truyền thống ........................................................... 41
2.3.3. Các phương pháp áp dụng thuật toán phân chia: ................................ 43


vi

2.3.4. Phát hiện cộng đồng trong mạng xã hội ............................................... 45
Chương 3. THỬ NGHIỆM, ĐÁNH GIÁ KẾT QUẢ VỚI BÀI TOÁN PHÁT
HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................................................... 50
3.1. Mô tả bài toán........................................................................................... 50
3.2. Mô hình giải quyết bài toán ..................................................................... 50
3.2.1. Mô hình đồ thị thông tin ........................................................................ 50
3.2.2. Hướng của cạnh .................................................................................... 50
3.2.3. Trọng số của cạnh ................................................................................. 51

3.2.4. Lựa chọn mô hình cho bài toán ............................................................ 51
3.3. Thử nghiệm, đánh giá mô hình (thu thập dữ liệu từ mạng xã hội, biểu diễn
dữ liệu, cài đặt, thử nghiệm và đánh giá kết quả) ........................................... 51
3.3.1. Giới thiệu nhóm Facebook, phân tích nhóm Facebook ........................ 51
3.3.2. Phương pháp thu thập dữ liệu từ nhóm Facebook ............................... 53
3.3.3. Thử nghiệm bài toán ............................................................................. 54
3.3.4. Thuật toán chính ................................................................................... 55
3.3.5. Demo bài toán ....................................................................................... 56
3.3.6. Đánh giá ................................................................................................ 62
KẾT LUẬN VÀ KHUYẾN NGHỊ ................................................................. 64
1. Kết luận ....................................................................................................... 64
2. Khuyến nghị ................................................................................................ 64
TÀI LIỆU THAM KHẢO


vii

DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết tắt

Ý nghĩa

KDD

Knowleadge Discovery in Database

CSDL

Cơ sở dữ liệu


CNTT

Công nghệ thong tin

OLAP

On Line Analytical Processing

FSG

Frequency SubGraph Mining

CONGA
FNCA

Cluster Overlap Newman-Girvan Algorithm
Fast Network Community Algorithm


viii

DANH MỤC BẢNG
Bảng 2.1. Biểu diễn giao dịch ......................................................................... 30
Bảng 2.2. Biểu diễn giao dịch ......................................................................... 30
Bảng 2.3. Biểu diễn giao dịch ......................................................................... 31
Bảng 2.4. Biểu diễn giao dịch ......................................................................... 31
Bảng 2.5. Biểu diễn giao dịch ......................................................................... 31
Bảng 2.6. Biểu diễn giao dịch ......................................................................... 32
Bảng 2.7. Kết quả cuối cùng .......................................................................... 32
Bảng 3.1. Một dạng format (Ma trận thích (Like)) ........................................ 54

Bảng 3.2. Bảng người dùng sau khi đã giải mã .............................................. 57
Bảng 3.3. Mảng chuyển đổi ............................................................................ 58


ix

DANH MỤC HÌNH
Hình 1.1. Các bước trong khai phá dữ liệu và KDD......................................... 5
Hình 1.2. Quá trình khai phá dữ liêu (khám phá tri thức)................................. 7
Hình 1.3. Phân cụm ......................................................................................... 11
Hình 1.4. Cây quyết định ................................................................................ 12
Hình 2.1. Mô tả mô hình đồ thị ....................................................................... 15
Hình 2.2. Các loại đồ thị ................................................................................. 16
Hình 2.3. Đơn đồ thị vô hướng ....................................................................... 16
Hình 2.4. Đa đồ thị vô hướng.......................................................................... 17
Hình 2.5. Giả đồ thị vô hướng ........................................................................ 18
Hình 2.6. Đơn đồ thị có hướng ....................................................................... 18
Hình 2.7. Đa đồ thị có hướng ......................................................................... 19
Hình 2.8. Minh họa thuật toán FSG ............................................................... 35
Hình 2.9. Cộng đồng mạng xã hội đơn giản với 3 cộng đồng ....................... 40
Hình 2.10. Phương pháp phân vùng đồ thị ..................................................... 41
Hình 2.11. Ví dụ về phép phân chia một đỉnh trong đồ thị ............................ 44
Hình 2.12. Một số ví dụ về cộng đồng trên mạng xã hội .............................. 45
Hình 2.13. Mô hình mạng lưới cộng tác của các nhà khoa học ..................... 46
Hình 3.1. Liên kết giữa hai đỉnh (người) trên mạng xã hội ............................ 50
Hình 3.2. Quan hệ giữa hai người trên mạng xã hội với trọng số .................. 51
Hình 3.3. Hình ảnh một nhóm Facebook ........................................................ 52
Hình 3.5. Ví dụ 3 định dạng worksheet: bạn bè, thích, bình luận .................. 59
Hình 3.6. Đồ thị sau khi xử lý ......................................................................... 59
Hình 3.7. Bộ dữ liệu sau khi xử lý .................................................................. 60

Hình 3.8. So sánh thuật toán Light-FSG với thuật toán khác ......................... 60
Hình 3.9. Giao diện chương trình .................................................................. 61
Hình 3.10. Biểu diễn Mạng đồ thị 2D ............................................................. 61
Hình 3.11. Biểu diễn Mạng đồ thị 3D ............................................................. 62


1

ĐẶT VẤN ĐỀ
1.1. Sự cần thiết lựa chọn đề tài
Trong những năm gần đây, khai phá dữ liệu dữ liệu đồ thị là chủ đề thu
hút sự quan tâm của cộng đồng nghiên cứu về khai phá dữ liệu và học máy và
được ứng dụng rộng rãi trong nhiều lĩnh vực như: phân tích dữ liệu hóa học,
sinh học, phân tích mạng máy tính, phân tích mạng xã hội..[4, 5, 6]. Theo tìm
hiểu của tác giả, các nghiên cứu liên quan đến khai phá dữ liệu đồ thị thường
tập trung vào các bài toán như: liệt kê và đếm (Enumeration and Counting),
phân lớp đồ thị (graph classification), phân cụm đồ thị (graph clustering), học
bán giám sát (semi-supervisedlearning), tóm tắt đồ thị (graph summarization),
khai phá đồ thị phổ biến (frequent graph mining)…
Khai phá đồ thị phổ biến là hướng nghiên cứu sôi động trong mấy năm
gần đây trong lĩnh vực khai phá dữ liệu đồ thị. Dựa trên nền tảng của bài toán
khai phá luật kết hợp, khai phá đồ thị phổ biến nhằm tìm kiếm các đồ thị con
phổ biến (tương ứng với tập mục phổ biến). Các đồ thị con phổ biến là nền tảng
để giải quyết bài toán dự báo trên không gian dữ liệu đồ thị và có ứng rộng rãi
trong nhiều lĩnh vực khác nhau của đời sống. Một số thuật toán điển hình khai
phá đồ thị phổ biến là CMTMiner [7], HSIGRAM, VSIGRAM [8],. Thuật toán
CMTMiner thực hiện việc duyệt các cạnh phổ biến và xây dựng cây DFS để tìm
các đồ thị con phổ biến.Trong khi đó, HSIGRAM, VSIGRAM là hai thuật toán xác
định các đồ thị con phổ biến trong một đồ thị lớn.
Như đã trình bày ở trên, lĩnh vực khai phá dữ liệu đồ thị đã thu được các

kết quả quan trọng về lý thuyết và đã có ứng dụng hiệu quả trong việc giải quyết
một số bài toán trong thực tiễn.Một trong những bài toán ứng dụng của khai
phá đồ thị con phổ biến là phát hiện cộng đồng mạng xã hội.


2

Mạng xã hội là một cấu trúc mang tính xã hội được cấu tạo từ các nút và
các cung, trong đó các nút được liên kết với nhau bởi một hoặc nhiều cung, thể
hiện kiểu mối quan hệ cụ thể [9]. Mỗi nút, còn được gọi là tác nhân (actor),
biểu diễn cho một đối tượng trong xã hội, có thể là một người, một tài liệu, một
tổ chức, một quốc gia,…Mối liên hệ giữa các nút được biểu diễn bởi một liên
kết giữa các nút đó. Liên kết này có thể là mối quan hệ bạn bè, họ hàng, đồng
nghiệp,…, cũng có thể là các trao đổi tài chính, các giao dịch, số liệu,…Các
liên kết này có thể là liên kết vô hướng (hay còn gọi là liên kết đối xứng hoặc
liên kết có hướng. Mặt khác, các liên kết còn có thể được đánh trọng số, trọng
số này biểu diễn độ mạnh của liên kết đó giữa hai nút.Về mặt toán học, mạng
xã hội có thể được biểu diễn dưới dạng đồ thị có hướng, trên cơ sở đó có thể áp
dụng các phương pháp khai phá dữ liệu đồ thị để giải quyết các bài toán trên
mạng xã hội.
Phát hiện cộng đồng mạng xã hội là bài toán thu hút sự quan tâm của nhiều
nhóm nghiên cứu. Theo Simmel (1955) thì cộng đồng là một nhóm các cá nhân
trên mạng, tập các thực thể có những tính chất tương tự nhau và cùng đóng một
vai trò trong mạng xã hội. Bài toán phát hiện cộng đồng là từ các mạng xã hội
cho trước, phát hiện được các cấu trúc cộng đồng nằm trong đó và tìm hiểu về
mối liên hệ bên trong các cộng đồng cũng như giữa các cộng đồng với nhau,
mối liên hệ đó có ảnh hưởng thế nào đến cấu trúc của toàn mạng xã hội.
Theo Santo Fortunato [10], các phương pháp phát hiện cộng đồng trong
mạng xã hội điển hình là: các phương pháp truyền thống; các thuật toán phân
chia; các phương pháp dựa trên mô đun hóa; các thuật toán động; các phương

pháp phát hiện cộng đồng chồng chéo. Các thuật toán phát hiện cộng đồng điển
hình là Girvan- Newman [11], Conga [12]…


3

Định hướng nghiên cứu của đề tài là nghiên cứu các phương pháp khai phá
đồ thị con phổ biến là ứng dụng giải quyết bài toán phát hiện cộng đồng trên
mạng xã hội.
1.2. Mục tiêu nghiên cứu của đề tài
Nghiên cứu lý thuyết về các phương pháp khai phá đồ thị con phổ biến
và thử nghiệm giải quyết bài toán phát hiện cộng đồng trên mạng xã hội.
2. Đối tượng và phạm vi nghiên cứu
2.1. Đối tượng
Đối tượng nghiên cứu là các phương pháp, công cụ khai phá đồ thị con
phổ biến và dữ liệu thử nghiệm được thu thập từ mạng xã hội
2.2. Phạm vi nghiên cứu
Phạm vi nghiên cứu là bài toán khai phá đồ thị con phổ biến và thử nghiệm
với bài toán phát hiện cộng đồng mạng xã hội.
3. Hướng nghiên cứu của đề tài
- Khai phá dữ liệu đồ thị trong lĩnh vực khai phá dữ liệu và học máy
4. Cấu trúc của luận văn
Dự kiến luận văn gồm: Phần mở đầu, ba chương nội dung, kết luận và
tài liệu tham khảo cụ thể:


4

Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ĐỒ THỊ
1.1. Tổng quan về khai phá dữ liệu đồ thị

1.1.1. Tại sao cần khai phá dữ liệu:
Khoảng một thập kỷ trở lại đây lượng thông tin được lưu trữ trên các
thiết bị điện tử không ngừng tăng lên. Theo các chuyên gia trong ngành CNTT
sau cứ khoảng 2 năm thì lượng thông tin lưu trữ trên toàn thế giới tăng gấp đôi,
không những vậy các thông tin lưu trữ này có số lượng và kích cỡ CSDL ngày
càng lớn và tăng một cách nhanh chóng.
Để giải quyết vấn đề này khai phá dữ liệu ra đời như một cách hữu hiệu
giải quyết vấn đề vừa nêu ở trên. Hiện nay khai phá dữ liệu có rất nhiều định
nghĩa tuy nhiên chúng ta có thể hiểu đơn giản khai phá dữ liệu như là một công
nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu được
tích trữ trong suốt quá trình hoạt động của một tổ chức, đơn vị nào đó.
1.1.2. Các khái niệm khai phá dữ liệu
Thuật ngữ khai phá dữ liệu là nói đến việc tìm kiếm một tập hợp nhỏ có
giá trị từ một số lượng lớn các dữ liệu thô. Hiện nay có rất nhiều thuật ngữ được
dùng có nghĩa tương tự với khai phá dữ liệu (Data Mining) như: Khai phá tri
thức (Knowledge Mining), Chắt lọc tri thức (Knowledge extraction), Phân tích
dữ liệu/mẫu (Data/patern), ….
Định nghĩa : Khai phá dữ liệu là tập hợp các kỹ thuật đươc sử dụng để
tự động để khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một
tập hợp các dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ta các mẫu tiềm
ẩn trong tập dữ liệu.
Khai phá dữ liệu là một trong bảy bước của quá trình KDD (Knowleadge
Discovery in Database) và KDD được xem như 7 quá trình khác nhau theo thứ tự:


5

- Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu các
dữ liệu không cần thiết.
- Tích hợp dữ liệu (Data integration): Quá trình hợp nhất dữ liệu thành

kho dữ liệu sau khi đã làm sạch dữ liệu và tiền xử lý.
- Trích chọn dữ liệu (data selection): Trích chọn dữ liệu từ những kho dữ
liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức
- Chuyển đổi dữ liệu: Các dữ liệu được chuyển sang dạng phù hợp cho
quá trình xử lý
- Khai phá dữ liệu: Đây là một trong những bước quan trọng nhất, trong
đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu.
- Ước lượng mẫu (Knowledge evulation): Đây là quá trình đánh giá các
kết quả tìm được thông qua các độ đo nào đó.
- Biểu diễn tri thức (knowledge pesentation): Quá trình sử dụng các kỹ
thuật để biểu diễn và thể hiện trực quan cho người dùng.

Hình 1.1. Các bước trong khai phá dữ liệu và KDD
1.1.3. Các chức năng chính của khai phá dữ liệu
Khai phá dữ liệu đươc chia thành các nhánh nhỏ bao gồm:
- Mô tả khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khai niệm.


6

Ví dụ cụ thể minh hoa cho nhánh này chính là quá trình tóm tắt văn bản,
bài báo, bài luận….
- Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng khá đơn giản
VD: “ 70% nam giới đi mua bia thì trong số đó 85% sẽ mua thêm đồ nhắm”
Luật kết hợp được ứng dụng trong nhiều lĩnh vực như: y học, kinh doanh,
tài chính và thị trường chứng khoán…
- Phân lớp và dự đoán: Xếp một đối tượng vào trong một lớp đã biết
trước. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học
máy(machine learning) như cây quyết định, mạng noron nhân tạo, …đây còn
được hiểu theo nghĩa khác là học có giám sát.

VD: Phân lớp vùng địa lý theo dự báo thời tiết
- Phân cụm: Xếp các đối tượng theo từng cụm, số lượng cũng như tên cụm
chưa được biết trước. Phân cụm hay còn gọi tên khác là học không giám sát.
- Khai phá chuỗi: Khai phá chuỗi tương tự như khai phá luật kết hợp
nhưng ở đây có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được
ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có
tính dự báo cao.
1.1.4. Các công cụ khai phá dữ liệu
Khai phá dữ liệu không phải là tất cả các công cụ hay phần mềm cơ sở
dữ liệu đang sử dụng. Có thể thực hiện việc khai phá dữ liệu bằng các hệ thống
cơ sở dữ liệu bình thường và các công cụ đơn giản, bao gồm việc tạo và viết
phần mềm riêng hoặc sử dụng các gói phần mềm thương mại. Khai phá dữ liệu
phức tạp được hưởng lợi từ kinh nghiệm trong quá khứ và các thuật toán đã
định nghĩa với phần mềm và các gói phần mềm hiện có với các công cụ nhất
định để thu được mối quan hệ hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau.
Hiện nay các tập hợp dữ liệu rất lớn và việc xử lý dữ liệu theo cụm và
quy mô lớn có thể cho phép khai phá dữ liệu để sắp xếp và lập báo cáo về các


7

nhóm và các mối tương quan của dữ liệu phức tạp hơn. Bây giờ đã có sẵn rất
nhiều công cụ và hệ thống hoàn toàn mới gồm các hệ thống lưu trữ và xử lý dữ
kiệu kết hợp.
1.2. Quy trình khai phá dữ liệu đồ thị
Quá trình khai phá dữ liệu đồ thị (khám phá tri thức) được tiến hành qua
5 bước sau
Hình thành và
định nghĩa bài toán
Thu thập và

Tiền xử lý dữ liệu

Khai thác dữ liệu
Rút ra các tri thức

Phân tích và
kiểm định kết quả

Sử dụng các tri thức
phát hiện được

Hình 1.2. Quá trình khai phá dữ liêu (khám phá tri thức)
1.2.1. Hình thành và định nghĩa bài toán
Đây là bước tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước
này sẽ quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các
phương pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất
của dữ liệu.


8

1.2.2. Thu thập và tiền xử lý dữ liệu
Trong bước này dữ liệu được thu thập ở dạng thô (nguồn dữ liệu thu thập
có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này
dữ liệu cũng được tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu cho phù hợp
với phương pháp khai phá dữ liệu được chọn lựa trong bước trên.
Bước này thường chiếm nhiều thời gian nhất trong quá trình khám phá
tri thức.
Các giải thuật tiền xử lý dữ liệu bao gồm :
Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ được thay thế

bởi các giá trị thích hợp
Khử sự trùng lắp: các đối tượng dữ liệu trùng lắp sẽ bị loại bỏ đi. Kỹ thuật
này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu.
Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung sẽ bị
loại đi khỏi dữ liệu.
Chuẩn hoá: miền giá trị của dữ liệu sẽ được chuẩn hoá.
Rời rạc hoá: các dạng dữ liệu số sẽ được biến đổi ra các giá trị rời rạc.
Rút trích và xây dựng đặc trưng mới từ các thuộc tính đã có.
Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt.
1.2.3. Khai phá dữ liệu và rút ra các tri thức
Đây là bước quan trọng nhất trong tiến trình khám phá tri thức. Kết quả
của bước này là trích ra được các mẫu và/hoặc các mô hình ẩn dưới các dữ liệu.
Một mô hình có thể là một biểu diễn cấu trúc tổng thể một thành phần của hệ
thống hay cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ liệu được nảy
sinh. Còn một mẫu là một cấu trúc cục bộ có liên quan đến vài biến và vài
trường hợp trong cơ sở dữ liệu.


9

1.2.4. Phân tích và kiểm định kết quả
Bước thứ tư là hiểu các tri thức đã tìm được, đặc biệt là làm sáng tỏ các
mô tả và dự đoán. Trong bước này, kết quả tìm được sẽ được biến đổi sang
dạng phù hợp với lĩnh vực ứng dụng và dễ hiểu hơn cho người dùng.
1.2.5. Sử dụng các tri thức phát hiện được
Trong bước này, các tri thức khám phá được sẽ được củng cố, kết hợp
lại thành một hệ thống, đồng thời giải quyết các xung đột tiềm năng trong các
tri thức đó. Các mô hình rút ra được đưa vào những hệ thống thông tin thực tế
dưới dạng các môdun hỗ trợ việc đưa ra quyết định.
Các giai đoạn của quá trình khám phá tri thức có mối quan hệ chặt chẽ

với nhau trong bối cảnh chung của hệ thống. Các kỹ thuật được sử dụng trong
giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật được sử dụng
trong các giai đoạn tiếp theo. Các bước của quá trình khám phá tri thức có thể
được lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên
tất cả các lần thực hiện.
1.3. Các bài toán trong khai phá dữ liệu đồ thị
Một số kỹ thuật cốt lõi được sử dụng trong các bài toán khai phá dữ liệu,
mô tả kiểu hoạt động khai phá dữ liệu và hoạt động phục hồi dữ liệu.
1.3.1. Khai phá luật kết hợp
Khai phá luật kết hợp là kỹ thuật khai phá dữ liêu được biết đến nhiều
hơn vì tính quen thuộc và đơn giản. Ở đây thực hiện một sự tương quan đơn
giản giữa hai hoặc nhiều mục, thường cùng kiểu để nhận biết các mẫu. Việc
xây dựng các công cụ khai phá dữ liệu dựa trên sự kết hợp hay mối quan hệ có
thể thực hiện đơn giản bằng các công cụ khác nhau.
1.3.2. Phân lớp
Kỹ thuật phân lớp dùng để xây dựng một ý tưởng về kiểu khách hàng,
kiểu mặt hàng hoặc kiểu đối tượng bằng cách mô tả nhiều thuộc tính để nhận


10

biết một lớp cụ thể. Kỹ thuật phân lớp dùng để xây dựng một ý tưởng về kiểu
khách hàng, kiểu mặt hàng hoặc kiểu đối tượng. Hơn nữa chúng ta có thể sử
dụng việc phân lớp như một dạng nguồn thứ cấp, hoặc như là kết quả của các
kỹ thuật khác.
1.3.3. Phân cụm
Bằng cách xem xét một hay nhiều thuộc tính hoặc các lớp, có thể nhóm
các phần dữ liệu riêng lẻ với nhau để tạo thành một quan điểm cấu trúc. Ở mức
đơn giản, việc phân cụm đang sử dụng một hoặc nhiều thuộc tính làm cơ sở
cho bạn để nhận ra một nhóm các kết quả tương quan. Việc phân cụm giúp để

nhận biết các thông tin khác nhau vì nó tương quan với các ví dụ khác, nên có
thể thấy ở đâu có những điểm tương đồng và các phạm vi phù hợp.
Việc phân cụm có thể làm theo hai cách. Có thể giả sử rằng có một cụm
ở một điểm nhất định và sau đó sử dụng các tiêu chí nhận dạng để xem liệu có
đúng không. Đồ thị trong Hình 1.2 là một ví dụ. Một ví dụ mẫu về dữ liệu kinh
doanh so sánh tuổi của khách hàng với quy mô bán hàng. Hợp lý khi thấy rằng
những người ở độ tuổi hai mươi (trước khi kết hôn và còn nhỏ), ở độ tuổi năm
mươi và sáu mươi (khi không còn con cái ở nhà), có nhiều tiền tiêu hơn.
Với một đồ thị phân cụm đơn giản mà ta có thể tạo ra bằng cách sử dụng
bất kỳ phần mềm đồ họa thích hợp nào để có được cái nhìn nhanh chóng. Các
quyết định phức tạp hơn cần phải có một gói phần mềm phân tích đầy đủ, đặc
biệt là các quyết định dựa vào thông tin lân cận nhất.
Việc vẽ đồ thị theo phân cụm là cách đơn giản nhất để nhận ra sự lân cận
nhất. Có thể nhận ra các đối tượng riêng lẻ bằng sự gần gũi theo nghĩa đen của
các đối tượng trên đồ thị.


11

Hình 1.3. Phân cụm
1.3.4. Dự báo
Dự báo là một chủ đề rộng và đi từ dự báo về lỗi của các thành phần hay
máy móc đến việc nhận ra sự gian lận và thậm chí là cả dự báo về lợi nhuận
của công ty nữa. Được sử dụng kết hợp với các kỹ thuật khai phá dữ liệu khác,
dự báo gồm có việc phân tích các xu hướng, phân loại, so khớp mẫu và mối
quan hệ. Bằng cách phân tích các sự kiện hoặc các cá thể trong quá khứ, bạn
có thể đưa ra một dự báo về một sự kiện.
Khi sử dụng quyền hạn thẻ tín dụng, chẳng hạn, bạn có thể kết hợp phân
tích cây quyết định của các giao dịch riêng lẻ trong quá khứ với việc phân loại và
các sự so khớp mẫu lịch sử để nhận biết liệu một giao dịch có gian lận hay không.

Rất có thể là việc thực hiện một sự so khớp giữa việc mua vé các chuyến bay đến
Mỹ và các giao dịch tại Mỹ cho thấy giao dịch này hợp lệ.
1.3.5. Các mẫu tuần tự
Thường được sử dụng trên các dữ liệu dài hạn, các mẫu tuần tự là một
phương pháp có ích để nhận biết các xu hướng hay các sự xuất hiện thường
xuyên của các sự kiện tương tự. Ví dụ, với dữ liệu khách hàng, có thể nhận ra
rằng các khách hàng cùng nhau mua một bộ sưu tập riêng lẻ về các sản phẩm
tại nhiều thời điểm khác nhau trong năm. Trong một ứng dụng giỏ hàng, có thể
sử dụng thông tin này để tự động đề xuất rằng một số mặt hàng nào đó được


12

thêm vào một giỏ hàng dựa trên tần suất và lịch sử mua hàng trong quá khứ của
các khách hàng
1.3.6. Các cây quyết định
Liên quan đến hầu hết các kỹ thuật khác (chủ yếu là phân loại và dự báo),
cây quyết định có thể được sử dụng hoặc như là một phần trong các tiêu chí lựa
chọn hoặc để hỗ trợ việc sử dụng và lựa chọn dữ liệu cụ thể bên trong cấu trúc
tổng thể. Trong cây quyết định, bạn bắt đầu bằng một câu hỏi đơn giản có hai
câu trả lời (hoặc đôi khi có nhiều câu trả lời hơn). Mỗi câu trả lời lại dẫn đến
thêm một câu hỏi nữa để giúp phân loại hay nhận biết dữ liệu sao cho có thể
phân loại dữ liệu hoặc sao cho có thể thực hiện dự báo trên cơ sở mỗi câu trả
lời. Hình 1.3 cho thấy một ví dụ trong đó bạn có thể phân loại một điều kiện lỗi
gửi đến.
Error
triggered
Yes
Water lever
> 15ft

Yes

No

Send
warning

Are pumps
Working?

No

Yes

Send
alert

Hình 1.4. Cây quyết định

Send
warning


13

Các cây quyết định thường được sử dụng cùng với các hệ thống phân
loại liên quan đến thông tin có kiểu thuộc tính và với các hệ thống dự báo, nơi
các dự báo khác nhau có thể dựa trên kinh nghiệm lịch sử trong quá khứ để
giúp hướng dẫn cấu trúc của cây quyết định và kết quả đầu ra.
1.4. Các ứng dụng của khai phá dữ liệu đồ thị

1.4.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều ngành
và lĩnh vực khác nhau như: tài chính ngân hàng, thương mại, y tế, giáo dục,
thống kê, máy học, trí tuệ nhân tạo, csdl, thuật toán toán học, tính toán song
song với tốc độ cao, thu thập cơ sở tri thức cho hệ chuyên gia,…
1.4.2.Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều
lĩnh vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các
ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu, từ ảnh viễn thám, cảnh báo
hỏng hóc trong các hệ thống sản xuất; Được ứng dụng cho việc quy hoạch và
phát triển các hệ thống quản lý và sản xuất trong thực tế như dự đoán tải sử
dụng điện, mức độ tiêu thụ sản phẩm, phân nhóm khách hàng; Áp dụng cho các
vấn đề xã hội như phát hiện tội phạm, tăng cường an ninh…
Một số ứng dụng cụ thể như sau :
Khai phá dữ liệu được sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.
Trong sinh học: nó dùng để tìm kiếm , so sánh các hệ gen và thông tin di
chuyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di chuyền
Trong y học: khai phá dữ liệu giúp tìm ra mối liên hệ giữa các triệu
chứng, chuẩn đoán bệnh.
Tài chính và thị trường chứng khoán: Khai phá dữ liệu để phân tích tình
hình tài chính, phân tích đầu tư, phân tích cổ phiếu
Khai thác dữ liệu web.


14

Trong thông tin kỹ thuật: khai phá dữ liệu dùng để phân tích các sai hỏng,
điều khiển và lập lịch trình…
Trong thông tin thương mại: dùng để phân tích dữ liệu người dùng, phân
tích dữ liệu marketing, phân tích đầu tư, phát hiện các gian lận.



15

Chương 2. CÁC PHƯƠNG PHÁP KHAI PHÁ ĐỒ THỊ CON
PHỔ BIẾN
2.1. Các định nghĩa về đồ thị con phổ biến
2.1.1. Giới thiệu về lý thuyết đồ thị
2.1.1.1. Định nghĩa cơ bản về đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh
này. Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối
hai đỉnh nào đó của đồ thị. Để có thể hình dung được tại sao lại cần đến các loại
đồ thị khác nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy
tính. Giả sử ta có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là
kênh thoại) nối các máy tính này. Chúng ta có thể biểu diễn các vị trí đặt náy tính
bởi các điểm và các kênh thoại nối chúng bởi các đoạn nối

Hình 2.1. Mô tả mô hình đồ thị


16

2.1.1.2. Các loại đồ thị

Hình 2.2. Các loại đồ thị
+ Đơn đồ thị vô huớng
Đồ thị G=(V, E) được gọi là đơn đồ thị vô hướng:
- V: Là tập các đỉnh
- E: là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V


V= {1, 2, 3, 4, 5}
E= {(1, 2), (1, 3), (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)}
Hình 2.3. Đơn đồ thị vô hướng