ĐẠI HỌC QUỐC GIA TP HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN


NGUYỄN HỒ DUY TRI

KHAI PHÁ CHỦ ĐỀ CỦA KHO VĂN BẢN LỚN THEO
TIẾP CẬN ĐỒ THỊ TRÊN NỀN TÍNH TOÁN PHÂN TÁN

LUẬN VĂN THẠC SĨ
NGÀNH KHOA HỌC MÁY TÍNH
Mã số: 60 48 01 01

TP HỒ CHÍ MINH – NĂM 2018


ĐẠI HỌC QUỐC GIA TP HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN


NGUYỄN HỒ DUY TRI

KHAI PHÁ CHỦ ĐỀ CỦA KHO VĂN BẢN LỚN THEO
TIẾP CẬN ĐỒ THỊ TRÊN NỀN TÍNH TOÁN PHÂN TÁN

LUẬN VĂN THẠC SĨ
NGÀNH KHOA HỌC MÁY TÍNH
Mã số: 60 48 01 01

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. ĐỖ PHÚC

TP HỒ CHÍ MINH – NĂM 2018


Lời cam đoan

LỜI CAM ĐOAN
Tác giả luận văn có lời cam đoan danh dự về công trình khoa học của mình, cụ thể:
Tôi tên: NGUYỄN HỒ DUY TRI
Sinh ngày 10 tháng 09 năm 1991 tại tỉnh Đồng Nai
Quê quán: Quảng Nam
Hiện công tác tại: Trường Đại học Công Nghệ Thông Tin – ĐHQG TP.HCM
Là học viên khóa 9 ngành Khoa học Máy tính
Mã số học viên: CH1401037
Tôi cam đoan: “Khai phá chủ đề của kho văn bản lớn theo tiếp cận đồ thị trên nền
tính toán phân tán” là công trình nghiên cứu của riêng tôi, các kết quả nghiên cứu có
tính độc lập riêng, không sao chép bất kỳ tài liệu nào và chưa công bố nội dung này
ở bất kỳ đâu. Các số liệu trong luận văn được sử dụng trung thực, nguồn trích dẫn có
chú thích rõ ràng, minh bạch, có tính kế thừa, phát triển từ các tài liệu, tạp chí, các
công trình nghiên cứu đã được công bố, các website có uy tín.
Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về lời cam
đoan danh dự của tôi. Trường Đại học Công Nghệ Thông Tin không liên quan đến
những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình thực hiện (nếu có).
TP. HCM, ngày 10 tháng 02 năm 2018
Tác giả luận văn

Nguyễn Hồ Duy Tri

-1-



Mục lục

MỤC LỤC
LỜI CAM ĐOAN ..............................................................................................................1
MỤC LỤC ...........................................................................................................................2
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .................................................5
DANH MỤC CÁC B ẢNG ...............................................................................................6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .......................................................................7
MỞ ĐẦU..............................................................................................................................9
Chương 1. TỔNG QUAN ............................................................................................. 10
1.1. Lý do chọn đề tài................................................................................................... 10
1.2. Mục tiêu, đối tượng và phạm vi nghiên cứu của luận văn............................... 10
1.3. Nội dung và phương pháp nghiên cứu ............................................................... 11
1.3.1. Xây dựng kho văn bản lớn ........................................................................... 11
1.3.2. Nghiên cứu áp dụng phương pháp biểu diễn văn bản bằng đồ thị .......... 12
1.3.3. Nghiên cứu áp dụng phương pháp tìm đồ thị con phổ biến trên nền tính
toán phân tán .............................................................................................................. 12
1.3.4. Xây dựng tập đồ thị đặc trưng cho từng chủ đề văn bản, qua đó rút trích
được mô hình chủ đề ................................................................................................. 12
1.4. Cấu trúc luận văn .................................................................................................. 13
Chương 2. CƠ SỞ LÝ THUYẾT ................................................................................ 14
2.1. Mô hình hóa chủ đề .............................................................................................. 14
2.2. Biểu diễn văn bản bằng đồ thị ............................................................................. 15
2.2.1. Giới thiệu ........................................................................................................ 15
2.2.2. Tổng quan biểu diễn văn bản bằng đồ thị ................................................... 15
2.2.3. Các loại mô hình đồ thị cơ bản .................................................................... 16
2.2.4. Đồ thị đồng hiện (Co-occurrence Graph) ................................................... 19
2.3. Mô hình hóa chủ đề văn bản được biểu diễn bằng đồ thị ................................ 21
2.4. Khai phá đồ thị con phổ biến............................................................................... 21

2.4.1. Giới thiệu ........................................................................................................ 21
2.4.2. Hướng tiếp cận ............................................................................................... 22
2.4.3. Thuật toán Graph-Based Substructure Pattern Mining – gSpan.............. 23
2.5. Khoảng cách giữa hai đồ thị ................................................................................ 25
2.6. Cơ sở dữ liệu đồ thị .............................................................................................. 27
-2-


Mục lục

2.6.1. Hệ quản trị cơ sở dữ liệu MongoDB ........................................................... 28
2.6.2. Hệ quản trị cơ sở dữ liệu Neo4j ................................................................... 29
2.6.3. Hệ quản trị cơ sở dữ liệu OrientDB ............................................................ 31
2.6.4. So sánh giữa hệ quản trị cơ sở dữ liệu OrientDB với MongoDB và Neo4j
.......................................................................................................................... 32
2.7. Tổng quan về dữ liệu lớn ..................................................................................... 37
2.7.1. Khái niệm và lịch sử hình thành phát triển ................................................ 37
2.7.2. Đặc điểm ......................................................................................................... 38
2.8. Các nền tảng tính toán phân tán .......................................................................... 41
2.8.1. MapReduce..................................................................................................... 41
2.8.2. Giới thiệu chung về Hadoop ........................................................................ 42
2.8.3. Hadoop 1.0 (MRv1) ...................................................................................... 43
2.8.4. Hadoop 2.0 (MRv2, YARN - Yet Another Resource Negotiator) .......... 45
2.8.5. Giới thiệu về Apache Spark ......................................................................... 48
2.8.6. Các thành phần của Apache Spark .............................................................. 49
Chương 3. PHÂN TÍCH THIẾT KẾ HỆ THỐNG ................................................. 52
3.1. Tổng quan hệ thống .............................................................................................. 52
3.2. Tiền xử lý và lưu trữ kho văn bản lớn ................................................................ 53
3.3. Biểu diễn văn bản sử dụng mô hình đồ thị ........................................................ 54
3.4. Khai phá tập đồ thị con phổ biến ........................................................................ 56

3.5. Mô hình hóa chủ đề dựa trên việc trích xuất đồ thị đặc trưng ........................ 58
Chương 4. HIỆN THỰC VÀ THỬ NGHIỆM ......................................................... 60
4.1. Môi trường và công cụ ......................................................................................... 60
4.1.1. Hệ điều hành Ubuntu .................................................................................... 60
4.1.2. Môi trường phát triển tích hợp Eclipse ....................................................... 62
4.1.3. Ngôn ngữ Scala.............................................................................................. 63
4.2. Dữ liệu sử dụng ..................................................................................................... 67
4.3. Hiện thực phương pháp khai phá chủ đề đã đề xuất ........................................ 68
Chương 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................ 71
5.1. Kết luận .................................................................................................................. 71
5.2. Những đóng góp của đề tài .................................................................................. 71
5.3. Khả năng ứng dụng thực tiễn .............................................................................. 71
5.4. Hướng phát triển ................................................................................................... 72
-3-


Mục lục

DANH MỤC CÔNG BỐ KHOA HỌC CỦA TÁC GIẢ........................................ 73
TÀI LIỆU THAM KHẢO ............................................................................................ 74
BÀI BÁO KHOA HỌC
QĐ THÀNH LẬP HỘI ĐỒNG CHẤM LUẬN VĂN THẠC SĨ
QĐ THAY ĐỔI THÀNH VIÊN HỘI ĐỒNG CHẤM LUẬN VĂN THẠC SĨ
NHẬN XÉT LUẬN VĂN THẠC SĨ
PHIẾU YÊU CẦU CHỈNH SỬA LUẬN VĂN THẠC SĨ
BẢN GIẢI TRÌNH CHỈNH SỬA LUẬN VĂN THẠC SĨ

-4-



Danh mục các ký hiệu và chữ viết tắt

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
STT Từ viết tắt
Cụm từ gốc
1
ACID
Atomicity, Consistency, Isolation, và Durability
2

CG

Conceptual Graph

3

CSDL

4

DFS

Depth First Search

5

FTP

File Transfer Protocol


6

GPL

GNU General Public License

7

gSpan

Graph-Based Substructure Pattern Mining

8

HD

9

HDFS

10

IDE

11

JSON

JavaScript Object Notation


12

NASA

National Aeronautics and Space Administration

13

RDD

Resilient Distributed Datasets

14

YARN

Yet Another Resource Negotiator

Cơ sở dữ liệu

High Definition
Hadoop Distributed File System
Integrated Development Environment

-5-


Danh mục các bảng

DANH MỤC CÁC BẢNG

Bảng 2.1: So sánh chức năng giữa OrientDB và MongoDB .......................................34
Bảng 2.2: So sánh ngôn ngữ truy vấn trong OrientDB và MongoDB ........................36
Bảng 4.1: Mô tả các kiểu dữ liệu trong ngôn ngữ Scala...............................................64
Bảng 4.2: Số lượng đồ thị con đặc trưng ứng với từng chủ đề ....................................69

-6-


Danh mục các hình vẽ, đồ thị

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 2.1: Mô hình túi từ ...................................................................................................15
Hình 2.2: Mô hình đồ thị khái niệm ................................................................................16
Hình 2.3: Mô hình đồ thị hình sao...................................................................................17
Hình 2.4: Mô hình đồ thị vô hướng sử dụng tần số xuất hiện .....................................18
Hình 2.5: Mô hình đồ thị có hướng cạnh không gán nhãn ...........................................18
Hình 2.6: Mô hình đồ thị khoảng cách n đơn giản của câu “AAA BBB CCC DDD”
..............................................................................................................................................19
Hình 2.7: Mô hình đồ thị đồng hiện ................................................................................20
Hình 2.8: Ví dụ về đồ thị con chung ...............................................................................26
Hình 2.9: Đồ thị con chung lớn nhất ...............................................................................26
Hình 2.10: Hệ quản trị cơ sở dữ liệu MongoDB ...........................................................28
Hình 2.11: Hệ quản trị cơ sở dữ liệu Neo4j ...................................................................30
Hình 2.12: Hệ quản trị cơ sở dữ liệu OrientDB .............................................................31
Hình 2.13: Bộ dữ liệu đơn giản dưới dạng JSON .........................................................32
Hình 2.14: Liên kết dữ liệu trong OrientDB ..................................................................33
Hình 2.15: 05 đặc điểm của dữ liệu lớn (mô hình 5V) .................................................40
Hình 2.16: Framework Apache Hadoop .........................................................................42
Hình 2.17: Các thành phần của Hadoop 1.0...................................................................43
Hình 2.18: Quy trình MapReduce trong Hadoop ..........................................................44

Hình 2.19: Cấu trúc cài đặt một cụm tính toán của Hadoop 1.0..................................45
Hình 2.20: Những thay đổi cơ bản của Hadoop 2.0 so với Hadoop 1.0 .....................46
Hình 2.21: Cấu trúc cài đặt một cụm tính toán mới YARN.........................................47
Hình 2.22: Biểu tượng của Apache Spark ......................................................................48
Hình 2.23: Các thành phần của Apache Spark ..............................................................50
Hình 3.1: Tổng quan hệ thống .........................................................................................52
Hình 3.2: Quy trình tiền xử lý tập tin văn bản ...............................................................53
Hình 3.3: Cửa sổ trượt kích thước 2 được cho trượt qua văn bản để tạo thành đồ thị
..............................................................................................................................................54
Hình 3.4: Đồ thị đồng hiện được tạo thành từ ví dụ đã cho .........................................55
-7-


Danh mục các hình vẽ, đồ thị

Hình 3.5: Quy trình biểu diễn văn bản sử dụng mô hình đồ thị ..................................56
Hình 3.6: Mô hình phân tán của thuật toán gSpan ........................................................57
Hình 3.7: Sơ đồ các bước trích xuất đồ thị đặc trưng ...................................................59
Hình 4.1: Biểu đồ thời gian thực thi chương trình ........................................................70

-8-


Mở đầu

MỞ ĐẦU
Đề tài “Khai phá chủ đề của kho văn bản lớn theo tiếp cận đồ thị trên nền tính toán
phân tán” được đặt ra nhằm mục tiêu tìm kiếm và đề xuất được phương pháp mới
dùng để mô hình hóa chủ đề của tập văn bản mà vẫn giữ nguyên được cấu trúc của
thông tin, cụ thể là trật tự của từ, điều làm ảnh hưởng rất lớn đến chủ đề của văn bản

nhưng lại không được các mô hình trước đây đề cập đến.
Thông qua quá trình nghiên cứu, đề tài đã khảo sát và lựa chọn các thuật toán, cũng
như công cụ phù hợp như đồ thị đồng hiện (Co-occurrence Graph), thuật toán phân
tán Graph-Based Substructure Pattern Mining (Distributed gSpan), hệ quản trị cơ sở
dữ liệu OrientDB, nền tảng hỗ trợ xử lý phân tán Apache Spark… để đề xuất phương
pháp mô hình hóa chủ đề mới, nhằm giúp ích trong việc khai thác mô hình chủ đề về
sau. Trong đó, quá trình rút trích mô hình chủ đề cũng được luận văn thực hiện trên
hệ thống xử lý phân tán dữ liệu lớn nhằm phù hợp với hiện thực dữ liệu ngày nay.

-9-


Tổng quan

Chương 1. TỔNG QUAN
Ở Chương đầu tiên, luận văn trình bày về nhu cầu thực tế của xã hội hiện nay, cũng
như trong nghiên cứu khoa học dẫn đến lý do lựa chọn đề tài, bên cạnh đó là các
thông tin về mục tiêu, đối tượng và phạm vi mà luận văn này nhắm đến. Phần còn lại
trong chương này sẽ mô tả nội dung, phương pháp nghiên cứu và cấu trúc của toàn
bộ báo cáo.
1.1. Lý do chọn đề tài
Từ lâu, mô hình chủ đề của một văn bản đã được sử dụng để kiểm tra và khám phá
nội dung của một tập tài liệu văn bản dựa trên việc tìm kiếm các chủ đề tiềm ẩn nằm
trong văn bản đó. Nhiều năm qua, đã có không ít các thuật toán phát triển dựa trên
mô hình này, chủ yếu dựa vào các hướng tiếp cận như “túi từ” và không gian vector.
Các hướng tiếp cận này chủ yếu thực hiện việc tìm kiếm, thống kê tần suất xuất hiện
của các từ liên quan đến chủ đề của văn bản, qua đó rút trích được mô hình của một
chủ đề cụ thể. Tuy nhiên, với các hướng tiếp cận này cấu trúc của câu, cụ thể là thứ
tự của từ, điều làm ảnh hưởng đến nội dung ý nghĩa của văn bản lại thường bị bỏ qua.
Một điểm cần lưu ý nữa của hướng tiếp cận này là do dựa trên việc thống kê nên khi

làm việc với các văn bản ngắn, có số lượng từ hạn chế thì độ chính xác của mô hình
sẽ không cao. Do đó, thông qua nghiên cứu này, luận văn muốn đưa ra một hướng
tiếp cận mới để khai phá chủ đề tìm ẩn của tập tài liệu văn bản, sao cho có thể giữ
nguyên được thứ tự của các từ trong văn bản. Mục tiêu của luận văn là muốn khắc
phục được vấn đề thứ tự từ ảnh hưởng đến ý nghĩa và chủ đề của văn bản. Ngoài ra,
mô hình đề xuất của luận văn còn có thể được ứng dụng trên tập các văn bản ngắn.
Bên cạnh đó, với sự bùng nổ thông tin trong thời đại ngày nay, dữ liệu được sinh ra
trong một đơn vị thời gian ngày càng lớn, đòi hỏi việc xử lý tính toán phải càng nhanh
và hiệu quả mới mang lại được lợi ích thực tế cao, do đó đề tài cũng muốn cài đặt mô
hình đề xuất của mình trên hệ thống xử lý phân tán dữ liệu lớn nhằm tăng tốc quá
trình xử lý, cũng như tận dụng tối đa được nguồn tài nguyên xử lý đang ngày một
phát triển.
1.2. Mục tiêu, đối tượng và phạm vi nghiên cứu của luận văn
Mục tiêu nghiên cứu của đề tài là khai phá chủ đề của kho văn bản lớn theo tiếp cận
đồ thị trên nền tính toán phân tán. Để làm được điều đó, đề tài sẽ áp dụng phương
- 10 -


Tổng quan

pháp mô hình hóa chủ đề thông qua việc biểu diễn văn bản bằng đồ thị, sử dụng thuật
toán để khai phá tập đồ thị con phổ biến trên tập đồ thị biểu diễn văn bản. Đồng thời,
đề tài cũng sử dụng mô hình xử lý dữ liệu lớn nhằm song song hóa giải thuật, tăng
tốc độ xử lý trên tập dữ liệu với số lượng lớn.
Đối tượng nghiên cứu của đề tài bao gồm: nội dung của các bài báo tin tức, cụ thể là
các chủ đề và tập từ khóa tương ứng được trình bày trong bài báo tin tức; các mô hình
khai phá chủ đề ẩn dựa trên phương pháp đồ thị hóa tài liệu văn bản; các phương thức
xử lý, phân tích đồ thị biểu diễn văn bản; mô hình xử lý dữ liệu lớn…
Phạm vi nghiên cứu của đề tài là mô hình biểu diễn văn bản bằng đồ thị; mô hình tổ
chức dữ liệu tuần tự; hệ quản trị cơ sở dữ liệu hướng đồ thị; mô hình xử lý dữ liệu

lớn MapReduce, Apache Spark và các thư viện hỗ trợ như MLlib, GraphX.
1.3. Nội dung và phương pháp nghiên cứu
Đề tài nghiên cứu bao gồm các nội dung sau:
1.3.1. Xây dựng kho văn bản lớn
Mục tiêu: Tổ chức lưu trữ dữ liệu số lượng lớn các bài báo trên một trang tin trực
tuyến theo chủ đề cụ thể, được phân loại sẵn, một cách hợp lý để hỗ trợ tốt việc khai
thác, sử dụng ở các nội dung kế tiếp.
Đặc điểm: Hệ thống hỗ trợ việc lưu trữ dữ liệu phù hợp với nhu cầu của người dùng,
hỗ trợ truy vấn nhanh chóng. Dữ liệu sau khi được tiền xử lý phải được tổ chức một
cách hợp lý, phù hợp với yêu cầu về số lượng, cũng như đảm bảo cho việc truy xuất
và xử lý trên hệ thống phân tán.
Phương pháp:
✓ Tìm hiểu ưu khuyết điểm của các hệ quản trị cơ sở dữ liệu hoặc hệ thống lưu
trữ tập tin phân tán như Neo4j, MongoDB, Hadoop Distributed File System –
HDFS, OrientDB... Phân tích sự phù hợp trong việc lưu trữ đối với tập dữ liệu
bài báo đã thu thập.
✓ Tìm hiểu các phương pháp thống kê, rút gọn các từ khóa, loại bỏ stopword và
áp dụng với tập dữ liệu hiện có.
✓ Lựa chọn phương án lưu trữ thích hợp và tổ chức lưu trữ tập dữ liệu sau khi
tiền xử lý.

- 11 -


Tổng quan

Kết quả dự kiến: Thu được tập dữ liệu bài báo với số lượng lớn, đã được tiền xử lý,
lưu trữ trên nền tảng hỗ trợ cho việc xử lý phân tán, sẵn sàng cho các bước tính toán
tiếp theo.
1.3.2. Nghiên cứu áp dụng phương pháp biểu diễn văn bản bằng đồ thị

Mục tiêu: Mô hình hóa tập dữ liệu bài báo đã thu thập từ trước theo tiếp cận đồ thị.
Đặc điểm: Tập bài báo số lượng lớn đã thu được ở bước trước cần phải được biểu
diễn bằng đồ thị, nhằm hỗ trợ việc xử lý rút trích mô hình chủ đề để tìm ra chủ đề ẩn
của bài báo.
Phương pháp:
✓ Tìm hiểu và áp dụng phương pháp biểu diễn văn bản bằng đồ thị.
✓ Tổ chức lưu trữ các đồ thị đã tính toán được một cách hợp lý nhằm hỗ trợ việc
xử lý, tính toán trên dữ liệu đồ thị.
Kết quả dự kiến: Tập dữ liệu bài báo thu thập đã được mô hình hóa theo tiếp cận đồ
thị.
1.3.3. Nghiên cứu áp dụng phương pháp tìm đồ thị con phổ biến trên nền tính
toán phân tán
Mục tiêu: Áp dụng mô hình xử lý dữ liệu lớn để tăng tốc quá trình tính toán với tập
dữ liệu văn bản lớn được biểu diễn bằng đồ thị, tìm ra tập các đồ thị con phổ biến.
Đặc điểm: Số lượng bài báo lớn, do đó số lượng đồ thị biểu diễn là rất lớn. Vì thế các
xử lý và tính toán trên tập dữ liệu này đòi hỏi phải có phương pháp cụ thể, dựa trên
mô hình tính toán song song phân tán nhằm tận dụng tối đa tài nguyên, giảm bớt thời
gian thực thi chương trình so với khi thực hiện trên máy đơn.
Phương pháp:
✓ Tìm hiểu một số bài toán xử lý trên đồ thị như tìm đồ thị con, đồ thị con đẳng
cấu, đồ thị con phổ biến.
✓ Tìm hiểu và áp dụng mô hình xử lý dữ liệu lớn vào việc song song hóa các giải
thuật trên đồ thị dựa vào thư viện MLlib, GraphX của Apache Spark.
Kết quả dự kiến: Hệ thống tìm kiếm đồ thị con phổ biến dựa trong tập đồ thị biểu
diễn văn bản trên nền tảng xử lý phân tán dữ liệu lớn.
1.3.4. Xây dựng tập đồ thị đặc trưng cho từng chủ đề văn bản, qua đó rút trích
được mô hình chủ đề
- 12 -



Tổng quan

Mục tiêu: Rút trích được tập đồ thị mang đặc trưng riêng cho từng chủ đề, qua đó xác
định được mô hình chủ đề.
Đặc điểm: Qua tập đồ thị con phổ biến ứng với từng chủ đề đã được khai phá ở bước
trước, đề tài nhận thấy, không phải đồ thị con nào cũng mang tính chất riêng, không
trùng lặp với đồ thị con khác, do đó không thể đặc trưng riêng biệt được cho chủ đề
của nó, tránh gây nhầm lẫn với chủ đề khác. Vì thế cần tìm ra được phương pháp lọc
ra được các đồ thị con riêng biệt của từng chủ đề, đủ khả năng tạo thành đặc trưng
riêng cho chủ đề đó so với các chủ đề khác.
Phương pháp:
✓ Tìm hiểu phương pháp tính khoảng cách giữa hai đồ thị.
✓ Áp dụng phương pháp tính khoảng cách để tìm ra tập đồ thị đặc trưng.
Kết quả dự kiến: Xây dựng được tập đồ thị đặc trưng cho từng chủ đề, qua đó mô
hình hóa được chủ đề trong tập văn bản.
1.4. Cấu trúc luận văn
Nội dung luận văn này được trình bày chia thành 05 chương bao gồm: Chương 1 giới
thiệu tổng quan về đề tài, lý do lựa chọn đề tài, mục tiêu, đối tượng và phạm vi nghiên
cứu của đề tài, nội dung nghiên cứu đã thực hiện đi kèm theo đó là phương pháp đã
sử dụng tương ứng với từng nội dung; Chương 2 – trình bày cơ sở lý thuyết về các
khái niệm, định nghĩa và những mô hình, thuật toán liên quan đến vấn đề nghiên cứu;
Chương 3 mô tả chi tiết những nghiên cứu, áp dụng lý thuyết, từ đó phát triển phương
pháp mới, đề xuất để giải quyết vấn đề đã đặt ra; Chương 4 trình bày việc hiện thực
phương pháp tiếp cận đã đặt ra ở chương 3, cài đặt hệ thống và kết quả ban đầu đạt
được; Chương 5 trình bày kết luận, những điều luận văn đã đóng góp và hướng phát
triển tiếp theo của đề tài này trong tương lai.

- 13 -



Cơ sở lý thuyết

Chương 2. CƠ SỞ LÝ THUYẾT
Trong Chương 2, luận văn sẽ trình bày chi tiết cơ sở lý thuyết được sử dụng trong đề
tài nghiên cứu bao gồm: mô hình hóa chủ đề; mô hình biểu diễn văn bản bằng đồ thị,
trong đó mô hình đồ thị đồng hiện (Co-occurrence Graph) được đề tài chọn sử dụng;
các thuật toán khai phá đồ thị con phổ biến, cụ thể về thuật toán nổi bật Graph-Based
Substructure Pattern Mining (gSpan); cơ sở dữ liệu đồ thị và các hệ quản trị cơ sở dữ
liệu MongoDB, Neo4j, OrientDB, so sánh giữa chúng; nền tảng tính toán phân tán,
trong đó đề cập chủ yếu đến mô hình xử lý dữ liệu lớn nổi tiếng đang được nhiều
người sử dụng là Map-Reduce, hai framework hỗ trợ là Apache Hadoop và Apache
Spark; cuối cùng là độ đo khoảng cách giữa hai đồ thị.
2.1. Mô hình hóa chủ đề
Chủ đề là một vấn đề đang được nói đến, được thảo luận, được trình bày trong một
văn bản hoặc được nghiên cứu. Chủ đề thường được xác định trước khi tạo lập văn
bản và nó sẽ chi phối quá trình tạo ra văn bản, mà chủ yếu là ảnh hưởng đến việc
chọn từ để đưa vào văn bản.
Năm 1990, Deerwester cùng cộng sự trong bài báo [8] đã đề xuất mô hình chủ đề,
trong đó, mô hình này cho phép kiểm tra và khai thác tập tài liệu văn bản dựa trên
việc tìm kiếm và thống kê các từ có liên quan đến chủ đề trong mỗi văn bản, và khám
phá ra những chủ đề tiềm ẩn khi được tạo lập trong văn bản đó. Một trong những
những hướng tiếp cận phổ biến nhất và tiêu chuẩn để mô hình hóa chủ đề của một
văn bản là tiếp cận dựa trên “túi từ”. Đây là phương pháp phù hợp để áp dụng tính
toán tần số xuất hiện của từ, tuy nhiên cấu trúc và ngữ nghĩa của thông tin lại bị bỏ
qua không được sử dụng để tính toán.

- 14 -


Cơ sở lý thuyết


Hình 2.1: Mô hình túi từ
(Nguồn: Youtube)
Trong nghiên cứu này, luận văn đi theo hướng tiếp cận đồ thị, dựa vào việc biểu diễn
một văn bản bằng đồ thị, qua đó áp dụng các thuật toán để khai phá các đồ thị con
phổ biến trong tập văn bản đã được đồ thị hóa, để từ đó mô hình hóa được chủ đề của
tập văn bản.
2.2. Biểu diễn văn bản bằng đồ thị
2.2.1. Giới thiệu
Một phương pháp tiếp cận chung và tiêu chuẩn để mô hình hóa tài liệu văn bản phổ
biến là sử dụng mô hình “túi từ” và không gian vector. Đây là mô hình phù hợp để
áp dụng tính toán tần số xuất hiện của từ, tuy nhiên cấu trúc và ngữ nghĩa của thông
tin lại bị bỏ qua không được sử dụng để tính toán.
Trong khi đó, đồ thị là các cấu trúc toán học có thể được sử dụng để mô hình hóa mối
quan hệ giữa các thành phần và biểu diễn thông tin cấu trúc của dữ liệu một cách hiệu
quả. Một văn bản có thể biểu diễn dưới dạng đồ thị có đỉnh là các thuật ngữ và thuộc
tính của thuật ngữ đó, cạnh của đồ thị sẽ biểu diễn mối quan hệ giữa các thuật ngữ.
Biểu diễn tài liệu sử dụng mô hình đồ thị cung cấp các tính toán liên quan khác nha u
như độ quan trọng của thuật ngữ, xếp hạng thuật ngữ… mà các tính toán này thường
được sử dụng nhiều trong các ứng dụng rút trích thông tin.
2.2.2. Tổng quan biểu diễn văn bản bằng đồ thị
Trong một khảo sát có hệ thống của S. S. Sonawane và P. A. Kulkarni [17] về văn
bản được biểu diễn bằng đồ thị, một cách tổng quan, đỉnh của đồ thị thường được
dùng để biểu diễn năm loại sau: thuật ngữ, câu, đoạn văn, văn bản hoặc khái niệm.
- 15 -


Cơ sở lý thuyết

Cạnh của đồ thị biểu diễn mối quan hệ giữa các đỉnh sẽ thay đổi tùy theo những ngữ

cảnh khác nhau, dựa theo đỉnh sẽ biểu diễn loại nào mà cạnh sẽ có những loại cơ bản
như sau: từ xuất hiện cùng nhau trong một câu hoặc một đoạn văn hoặc một phần
hoặc một văn bản, từ phổ biến trong một câu hoặc một đoạn văn hoặc một phần hoặc
một văn bản, cụm từ đồng hiện, từ có quan hệ ngữ nghĩa (từ có cùng nghĩa, từ đánh
vần giống nhau nhưng khác nghĩa hay những từ có nghĩa trái ngược nhau). Từ đó có
được nhiều phương pháp xây dựng đồ thị khác nhau có cùng mục đích biểu diễn tài
liệu văn bản như: đồ thị đồng hiện, đồ thị đồng hiện dựa trên nhãn từ loại, đồ thị ngữ
nghĩa, đồ thị khái niệm, đồ thị từ khóa theo thứ bậc…
2.2.3. Các loại mô hình đồ thị cơ bản
2.2.3.1. Mô hình đồ thị khái niệm (Conceptual Graphs - CGs)
Mô hình đồ thị khái niệm được John F. Sowa trình bày lần đầu tiên vào năm 1976
[18], mô hình này sử dụng mạng ngữ nghĩa để biểu diễn văn bản thành đồ thị. Mỗi từ
trong văn bản là một khái niệm và được biểu diễn bằng đỉnh hình vuông. Đỉnh hình
oval thể hiện mối quan hệ giữa các khái niệm. Các đỉnh hình vuông được nối với
nhau dựa trên mối quan hệ trong mạng ngữ nghĩa và qua trung gian là đỉnh hình oval.
Trong công trình [12], các đồ thị khái niệm được sử dụng để mô tả mối quan hệ ngữ
nghĩa giữa các khái niệm trong hệ thống dạy học. Trong bài báo của Pattabhi R K
Rao và Sobha Lalitha Devi [15], các tác giả sử dụng đồ thị khái niệm để tạo ra một
mạng ngữ nghĩa giữa tất cả các câu trong các bằng sáng chế để cho việc khai thác
khái niệm và tóm tắt. Ưu điểm của CGs là mô hình hoá văn bản một cách trực quan,
chính xác và logic. Điểm hạn chế của CGs là khá phức tạp, đòi hỏi phân tích ngữ
nghĩa sâu, chuyên biệt và phải phụ thuộc vào lĩnh vực.
Ví dụ: Đồ thị khái niệm đối với câu “Elsie the cat is sitting on a mat” sẽ là:

Hình 2.2: Mô hình đồ thị khái niệm
(Nguồn: Wikipedia)
- 16 -


Cơ sở lý thuyết


2.2.3.2. Mô hình đồ thị hình sao
Đỉnh trung tâm của đồ thị hình sao là đỉnh khái quát cấu trúc của văn bản. Ngoài đỉnh
trung tâm, các đỉnh còn lại biểu diễn từ trong văn bản. Đỉnh thuộc phần nào trong văn
bản sẽ có cạnh nối từ đỉnh đó đến đỉnh trung tâm. Cạnh nối giữa các đỉnh được gán
nhãn, thể hiện mối quan hệ giữa các đỉnh. Khi chúng ta mô hình hoá một văn bản thì
nhãn của cạnh có thể là: “tiêu đề”, “chứa”… Ưu điểm của đồ thị hình sao là nắm bắt
được các thông tin cấu trúc của văn bản (phần tiêu đề, phần nội dung), mối quan hệ
giữa từ với các phần cấu trúc (đồng hiện của từ trong các phần tiêu đề, nội dung...).

Hình 2.3: Mô hình đồ thị hình sao [1]
2.2.3.3. Mô hình đồ thị vô hướng sử dụng tần số xuất hiện
Đồ thị vô hướng sử dụng tần số xuất hiện [19] có đỉnh và cạnh đều được gán nhãn.
Trong đó, nhãn đỉnh là tần số xuất hiện của từ trong văn bản. Cạnh được nối giữa hai
đỉnh nếu hai từ xuất hiện chung trong tập hợp (câu hoặc nhóm từ hoặc trang) và có
tần số xuất hiện chung lớn hơn ngưỡng cho phép. Nhãn cạnh là tần số xuất hiện chung
của hai từ trong tập hợp. Ưu điểm của mô hình đồ thị vô hướng sử dụng tần số xuất
hiện là khai thác được mối quan hệ giữa từ với từ trong cấu trúc văn bản, cũng như
tần số xuất hiện của từ và hỗ trợ cho quá trình tìm kiếm thông tin nhanh chóng.

- 17 -


Cơ sở lý thuyết

Màn hình
0.8
0.7

0.5

Bộ nhớ
0.5

Vi xử lý
0.4

0.6

0.4
Điện thoại di động
0.7

Hình 2.4: Mô hình đồ thị vô hướng sử dụng tần số xuất hiện
2.2.3.4. Mô hình đồ thị có hướng cạnh không gán nhãn
Mô hình này còn được gọi là mô hình đồ thị đơn giản [16]. Mỗi đỉnh biểu diễn một
từ riêng biệt và chỉ xuất hiện một lần trên đồ thị (ngay cả khi từ đó xuất hiện nhiều
lần trong văn bản). Nhãn đỉnh là duy nhất và là tên của từ. Sau bước tiền xử lý văn
bản, nếu từ “a” đứng ngay trước từ “b” sẽ có cạnh nối từ đỉnh “a” đến đỉnh “b” (không
kể các trường hợp phân cách bởi dấu câu). Điểm mạnh của mô hình là lưu trữ được
các thông tin cấu trúc như thứ tự xuất hiện, vị trí của từ trong văn bản và làm tăng
hiệu quả của bài toán phân lớp cũng như gom cụm văn bản.

Hình 2.5: Mô hình đồ thị có hướng cạnh không gán nhãn [16]

- 18 -


Cơ sở lý thuyết

2.2.3.5. Mô hình đồ thị có hướng, cạnh không gán nhãn, cạnh là khoảng cách n giữa

hai từ trong văn bản (mô hình khoảng cách n đơn giản)
Trong cách biểu diễn này, người dùng cung cấp tham số n. Thay vì chỉ quan tâm từ
“A” trực tiếp ngay trước từ “B”, ta còn chú ý đến n từ đứng trước từ “B”. Cạnh được
xây dựng giữa hai từ khi giữa chúng có số từ xuất hiện nhiều nhất là (n-1) từ (ngoại
trừ trường hợp các từ được phân cách bởi các dấu câu). Ưu điểm của mô hình là tận
dụng được mối quan hệ giữa các từ, vùng lân cận của từ trong câu và có thể áp dụng
vào bài toán phân lớp văn bản [1].

Hình 2.6: Mô hình đồ thị khoảng cách n đơn giản của câu “AAA BBB CCC DDD”
[16].
2.2.4. Đồ thị đồng hiện (Co-occurrence Graph)
Đồ thị đồng hiện là đồ thị được xây dựng dựa trên sự đồng hiện của các từ hoặc câu
trong một văn bản. Có nhiều cách để xây dựng đồ thị đồng hiện, trong đó tiêu biểu là
cách của S. Hassan và đồng sự [9] giới thiệu vào năm 2007. Với mỗi từ trong văn bản
sẽ là một đỉnh của đồ thị và một cạnh vô hướng sẽ được thêm vào giữa hai đỉnh nếu
hai từ cùng xuất hiện trong một kích thước khung nhất định.
Đoạn văn bản “In an effort to help tackle the stigma surrounding HIV and AIDS, the
Queen's grandson, Prince Harry, has been tested for HIV. He wants to encourage
more peo-ple to come forward to find out if they have the virus and his goal is to raise
aware-ness about HIV and AIDS. He confessed he had been a bit nervous before
having the simple procedure done.” (trích “BBC Learning English”, Oct 7th, 2016)
sẽ được đồ thị hóa thành đồ thị đồng hiện sau đây theo kích thước khung là 2:

- 19 -


Cơ sở lý thuyết

Hình 2.7: Mô hình đồ thị đồng hiện
Bên cạnh đó, năm 2011, trong bài báo [3], H. Balinsky và đồng sự đã đưa ra hướng

tiếp cận xây dựng đồ thị đồng hiện với đỉnh là các câu. Và các câu này sẽ được nối
với nhau tạo thành các cạnh nếu hai câu đó nằm gần nhau trong văn bản hoặc chúng
có cùng ít nhất là một từ khóa chung.
Ngoài ra còn có rất nhiều công trình nghiên cứu khác sử dụng đồ thị đồng hiện, trong
đó, có nhiều phương pháp tiếp cận xây dựng cạnh của đồ thị để biểu diễn sự đồng
hiện giữa các đỉnh phải kể đến như sử dụng quan hệ cú pháp giữa hai từ [6], sử dụng
phương pháp thống kê để xác định tần suất của từ [4], hay sử dụng chiều dài tối thiểu
của một câu để làm đơn vị đo cho thông tin đồng hiện của từ thay vì sử dụng toàn bộ
đoạn văn làm đơn vị, điều này tránh cho việc mở rộng đồ thị lại làm mất thông tin
giữa các từ [21].
Trong khuôn khổ của nghiên cứu này, luận văn sử dụng hướng tiếp cận xây dựng đồ
thị biểu diễn văn bản bằng sự đồng hiện của từ trong một kích thước khung nhất định,
mà ở đây sẽ lựa chọn kích thước khung là 2. Điều này sẽ giúp đồ thị thể hiện được
quan hệ của mỗi từ đối với từ ngữ đứng ngay cạnh nó. Và đồ thị mà đề tài muốn xây
dựng sẽ là đồ thị có hướng, với hướng của cạnh sẽ thể hiện được trật tự xuất hiện của
từ trong văn bản. Cụ thể, hướng của cạnh sẽ trỏ từ từ ngữ đứng trước đến từ ngữ đứng
- 20 -


Cơ sở lý thuyết

sau trong văn bản. Thông qua việc giữ gìn được trật tự xuất hiện của từ trong văn bản,
luận văn hy vọng sẽ giúp cho việc phân biệt văn bản đã được đồ thị hóa theo ý nghĩa
được rõ ràng và chính xác hơn.
2.3. Mô hình hóa chủ đề văn bản được biểu diễn bằng đồ thị
Qua đồ thị biểu diễn văn bản thu được, bài toán đặt ra là làm sao để áp dụng các giải
thuật phân lớp để phân lớp văn bản từ đó tìm ra chủ đề văn bản đã mô hình hóa. Năm
2009, nhóm tác giả bài báo [1] đã sử dụng thuật toán gSpan để tìm ra các đồ thị con
phổ biến. Từ tập các đồ thị con phổ biến của tất cả các chủ đề, nhóm tác giả đã xây
dựng vector nhị phân đặc trưng cho từng chủ đề. Đồ thị biểu diễn văn bản cần phân

lớp lúc này sẽ được chuyển hóa thành vector nhị phân có số chiều bằng với số chiều
của tập đồ thị con phổ biến của tất cả các chủ đề. Sau đó, nhóm tác giả sử dụng
phương pháp so khớp với độ đo Dice để tính khoảng cách giữa vector nhị phân từ đồ
thị biểu diễn văn bản với vector nhị phân đặc trưng cho từng chủ đề để tìm được chủ
đề của văn bản.
Trong một hướng tiếp cận khác, năm 2011, J. Wu và cộng sự [21] đã đề xuất phương
pháp cực đại hóa đồ thị con chung để tìm ra các văn bản tương tự nhau được biểu
diễn bởi đồ thị trọng số có hướng. Hướng tiếp cận này tính toán độ tương đồng của
hai đồ thị bằng việc đánh giá sự đóng góp của các đỉnh chung, các cạnh chung cũng
như trọng số của chúng.
2.4. Khai phá đồ thị con phổ biến
2.4.1. Giới thiệu
Khai phá đồ thị con phổ biến là một phần trong việc khai phá đồ thị mà nó rất thường
được sử dụng cho các mục đích phân lớp đồ thị, xây dựng chỉ mục và gom cụm đồ
thị. Khai phá đồ thị con phổ biến được đề cập đến từ nhiều quan điểm và góc nhìn
trong những hướng khác nhau dựa trên những miền kỳ vọng khác nhau. Trong những
năm gần đây, khi nhiều nhà khoa học nghiên cứu các thuật toán và công cụ để chuyển
đổi dữ liệu thành những thông tin hữu ích, khai phá đồ thị con phổ biến trở thành một
trong những kỹ thuật chính khi những dữ liệu đó được biểu diễn dưới dạng đồ thị
[14]. Bài toán nhận dạng đồ thị, đồ thị con phổ biến trong cơ sở dữ liệu đồ thị hoặc
trong một đồ thị đơn lớn là một phần của khai phá đồ thị con phổ biến, được sử dụng
trong phân lớp, gom cụm đồ thị và xây dựng chỉ mục.
- 21 -


Cơ sở lý thuyết

Cho đồ thị được gán nhãn 𝐺 , đại diện bởi bốn tập 𝐺 = (𝑉, 𝐸, 𝐿, 𝑙 ), trong đó: 𝑉 là tập
các đỉnh của đồ thị, 𝐸 ⊆ 𝑉 × 𝑉 là tập các cạnh của đồ thị, 𝐿 là tập các nhãn đỉnh và
cạnh, 𝑙: 𝑉 ∪ 𝐸 → 𝐿 là hàm gán nhãn cho đỉnh và cạnh của đồ thị. Khi đó, một đẳng

cấu giữa hai đồ thị 𝐺 và 𝐺′ là một hàm song ánh 𝑓: 𝑉(𝐺 ) → 𝑉(𝐺 ′ ), sao cho:
• ∀𝑢 ∈ 𝑉(𝐺 ), 𝑙𝐺 (𝑢) = 𝑙 𝐺 ′ (𝑓 (𝑢)) và
• ∀(𝑢, 𝑣) ∈ 𝐸 (𝐺 ), (𝑓 (𝑢) , 𝑓 (𝑣) ) ∈ 𝐸 (𝐺′) và 𝑙𝐺 (𝑢, 𝑣) = 𝑙𝐺′ (𝑓 (𝑢) , 𝑓(𝑣) )
Cho tập dữ liệu đồ thị 𝔾𝕊 = {𝐺𝑖 |𝑖 = 0 . . 𝑛}. Gọi:
1 𝑛ế𝑢 𝑔 đẳ𝑛𝑔 𝑐ấ𝑢 𝑣ớ𝑖 đồ 𝑡ℎị 𝑐𝑜𝑛 𝑐ủ𝑎 𝐺,
ς (𝑔, 𝐺 ) = {
0 𝑛ế𝑢 𝑔 𝑘ℎô𝑛𝑔 đẳ𝑛𝑔 𝑐ấ𝑢 𝑣ớ𝑖 𝑏ấ𝑡 𝑘ỳ đồ 𝑡ℎị 𝑐𝑜𝑛 𝑛à𝑜 𝑐ủ𝑎 𝐺.
𝜎 (𝑔, 𝔾𝕊) = ∑ 𝜍 (𝑔, 𝐺𝑖 )
𝐺𝑖 ∈ 𝔾𝕊

𝜎 (𝑔, 𝔾𝕊) ký hiệu cho tần suất xuất hiện của 𝑔 trong 𝔾𝕊, hay còn gọi là độ hỗ trợ của
𝑔 trong 𝔾𝕊. Khi đó, khai phá đồ thị con phổ biến là tìm tất cả các đồ thị 𝑔, sao cho
𝜎 (𝑔, 𝔾𝕊) lớn hơn hoặc bằng một ngưỡng hỗ trợ tối thiểu cho trước [22].
Trong quá trình tìm kiếm, khi kích thước đồ thị con giảm mạnh, kích thước mẫu đồ
thị sẽ tăng theo cấp số nhân. Điều này có thể gây ra một số vấn đề nghiêm trọng như
việc nhận dạng đồ thị con phổ biến có thể tốn nhiều thời gian hơn, gây cản trở tác vụ
nhận dạng đồ thị… Lưu ý rằng, việc tìm kiếm đồ thị con phổ biến trong đồ thị trực
tiếp dẫn đến bài toán liệt kê đồ thị con trong đồ thị đã cho, đó là một bài toán rất phức
tạp.
2.4.2. Hướng tiếp cận
Cho đến nay, có khá nhiều các thuật toán được đề xuất cho việc khai phá các đồ thị
con phổ biến từ một đồ thị. Đồ thị con là một đồ thị thu được từ đồ thị ban đầu bằng
cách loại bỏ một số đỉnh và một số cạnh. Đồ thị con phổ biến là đồ thị con có số lần
xuất hiện trong một đồ thị lớn hơn một ngưỡng cho trước. Hầu hết các thuật toán tìm
đồ thị con phổ biến đều phải đối mặt với hai thách thức về tính toán: (1) đồ thị con
đẳng cấu: xác định một đồ thị con của một đồ thị xuất hiện trong các đồ thị khác; (2)
liệt kê một cách hiệu quả tất cả các đồ thị con phổ biến: vì số lượng các đồ thị con sẽ
tăng lên theo kích thước của chính nó và kích thước của đồ thị, do vậy để làm việc
được với các đồ thị lớn và có cấu trúc phức tạp cần phải có các thuật toán khai phá
mẫu phổ biến hiệu quả. Là một trong những bước đầu tiên của khai phá đồ thị con

- 22 -


Cơ sở lý thuyết

phổ biến, tập các ứng viên đồ thị con được tạo ra một cách hệ thống. Có nhiều phương
pháp để tạo tập ứng viên này như ghép khôn ngoan, mở rộng đầu mút bên phải, mở
rộng và ghép, cây ghép trái và phải, lớp tương đương mở rộng…
Có hai hướng tiếp cận có thể tìm ra đồ thị con phổ biến trong đồ thị hay cơ sở dữ liệu
cho trước là: hướng tiếp cận dựa trên Apriori và hướng tiếp cận phát triển mẫu [10].
Hướng tiếp cận dựa trên Apriori tương tự việc khai phá tập phổ biến và đệ quy nó.
Một vài thuật toán khai phá đồ thị con phổ biến dựa trên Apriori là: AGM, FSG, Edge
disjoint path-join… AGM được đưa ra bởi Inokuchi và đồng sự, FSG được đưa ra
bởi Kuramochi và đồng sự. Các thuật toán này đều dựa trên các đồ thị con phổ biến
hiện có, rồi “sinh” ra các ứng viên tiếp theo bằng cách thêm cạnh hoặc đỉnh mới. Tại
thời điểm xuất phát, thuật toán coi đồ thị con chỉ có một đỉnh hoặc một cạnh. Điểm
khác nhau giữa các thuật toán này là phương thức “sinh” ra các ứng viên mới từ các
đồ thị con phổ biến hiện thời. Trong khi AGM sử dụng phương thức tạo ứng viên dựa
trên các đỉnh và gia tăng kích thước của đồ thị con bằng cách thêm 1 đỉnh mới. FSG
lựa chọn chiến lược tạo ứng viên dựa trên các cạnh để gia tăng kích thước của đồ thị
con bằng cách thêm mới một cạnh
Hướng tiếp cận phát triển mẫu bao gồm những thuật toán sau: SPIN, Mofa, gSpan,
FFSM và Gaston… Các thuật toán này đều tìm các đồ thị con liên thông phổ biến
trong đồ thị nhưng khác nhau ở cách sinh ra các đồ thị con ứng viên. Trong gSpan,
một đồ thị con phổ biến G được sử dụng để sinh ra các đồ thị con ứng viên G′ bằng
cách chọn một đỉnh v thuộc G và thêm vào cạnh (v, w), trong đó w thuộc G hoặc
không thuộc G. Ngược lại, thuật toán Mofa không sinh ra các ứng viên mà thay vào
đó là lưu giữ tất cả các đẳng cấu có thể có của đồ thị con phổ biến hiện thời.
2.4.3. Thuật toán Graph-Based Substructure Pattern Mining – gSpan
Thuật toán Graph-Based Substructure Pattern Mining viết tắt là gSpan, được giới

thiệu bởi X.Yan và J.Han vào năm 2002 [22]. Thuật toán dựa trên tiếp cận phát triển
mẫu, sử dụng chiến lược tìm kiếm theo chiều sâu (Depth-first search) để duyệt qua
các đồ thị, tìm kiếm các đồ thị con ứng viên và kiểm tra đồ thị con phổ biến. Từ khi
được công bố, đã có rất nhiều các công trình khoa học sử dụng thuật toán này hay các
thuật toán kế thừa để khai phá đồ thị con phổ biến trong tập đồ thị cho trước.

- 23 -