BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC TÂY BẮC

BÁO CÁO TỔNG KẾT ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ

NGHIÊN CỨU CẢI TIẾN HIỆU QUẢ
TÓM TẮT VĂN BẢN DỰA TRÊN ĐỒ THỊ
Mã số: TB2017 - 14

CHỦ NHIỆM ĐỀ TÀI: PHAN TRUNG KIÊN

SƠN LA, NĂM 2017


MỤC LỤC
MỤC LỤC ..............................................................................................................1
DANH MỤC CÁC THUẬT NGỮ, KÝ HIỆU, CHỮ VIẾT TẮT .........................3
DANH MỤC CÁC HÌNH.......................................................................................5
MỞ ĐẦU ................................................................................................................6
1. Tính cấp thiết của đề tài ..................................................................................6
2. Mục tiêu đề tài ................................................................................................6
3. Đối tượng, phạm vi nghiên cứu ......................................................................6
4. Phương pháp nghiên cứu ................................................................................7
5. Nội dung .........................................................................................................7
CHƯƠNG 1. TỔNG QUAN VỀ TÓM TẮT VĂN BẢN ....................................8
1.1. Giới thiệu về tóm tắt văn bản.......................................................................8
1.2. Phân loại các hệ thống tóm tắt văn bản .......................................................9
1.3. Tình hình nghiên cứu trong và ngoài nước................................................11
1.3.1. Ngoài nước..........................................................................................11
1.3.2. Trong nước..........................................................................................14
1.4. Mô hình biểu diễn văn bản ........................................................................15

CHƯƠNG 2. BIỂU DIỄN VĂN BẢN BẰNG ĐỒ THỊ ....................................16
2.1. Tổng quan về đồ thị ...................................................................................16
2.1.1. Khái niệm cơ sở ..................................................................................16
2.1.2. Các độ đo trên đồ thị ...........................................................................18
2.2. Mô hình biểu diễn văn bản bằng đồ thị .....................................................23
2.2.1. Mô hình đồ thị khái niệm....................................................................24
2.2.2. Mô hình đồ thị hình sao ......................................................................25
2.2.3. Mô hình đồ thị tần số vô hướng ..........................................................26

1


2.2.4. Mô hình đồ thị đơn giản .....................................................................27
2.2.5. Mô hình đồ thị khoảng cách n đơn giản .............................................28
2.2.5. Mô hình đồ thị đỉnh là câu ..................................................................29
2.2.6. Mô hình đồ thị lưỡng phần .................................................................30
CHƯƠNG 3. TÓM TẮT VĂN BẢN DỰA TRÊN ĐỒ THỊ .............................32
3.1. Tiền xử lý văn bản .....................................................................................33
3.2. Mô hình hóa văn bản thành đồ thị .............................................................34
3.3. Xếp hạng câu .............................................................................................36
3.4. Tạo bản tóm tắt ..........................................................................................38
3.5. Kết quả thử nghiệm....................................................................................39
3.5.1. Dữ liệu thử nghiệm .............................................................................39
3.5.2. Kết quả thử nghiệm.............................................................................40
KẾT LUẬN...........................................................................................................42
1. Kết luận .........................................................................................................42
2. Hướng phát triển của đề tài...........................................................................42
TÀI LIỆU THAM KHẢO ....................................................................................43

2



DANH MỤC CÁC THUẬT NGỮ, KÝ HIỆU, CHỮ VIẾT TẮT
Average link

liên kết trung bình

Bag of words model

mô hình túi từ

Clustering

gom cụm

Complete link

liên kết đầy đủ

Cue

ngữ chỉ thị

Cross-validation

đánh giá chéo

Data mining

khai thác dữ liệu


Dendrograms

sơ đồ nhánh

Document

tài liệu

Graph-based model

mô hình biểu diễn bằng đồ thị

Heading

tiêu đề

Hyperplane

siêu phẳng

Information extraction

trích chọn thông tin

Information retrieval

truy vấn thông tin

Single link


liên kết đơn

Title

nhan đề

Text mining

khai thác dữ liệu văn bản (khai thác văn bản)

CGs

mô hình đồ thị khái niệm - Conceptual Graphs

CSDL

cơ sở dữ liệu

DC-Tree

cây gom cụm tài liệu – Document Clustering Tree

DF

tần suất xuất hiện của tài liệu – Document frequency

DIG

đồ thị chỉ mục tài liệu - Document Index Graph


DUC

Document Understanding Conference

HAC

gom cụm phân cấp tích tụ - Hierachical Agglomerative

Clustering
ICG

gom cụm động dựa trên đồ thị - Incremental Clustering
based on Graph

IDF

nghịch đảo tần suât xuât hiện của tài liệu - Inverse
Document Frequency

IG

độ lợi thông tin - Information gain
3


KDD

khám phá tri thức trong cơ sở dữ liệu - Knowledge
discovery in databases


k-NN

k - láng giềng gần nhât - k- Nearest Neighbor

KTTL

kích thước của văn bản/email

KTLOP

kích thước thư mục /lớp

MCS

đồ thị con chung cực đại - Maximal Common Subgraph

MDL

độ dài mô tả cực tiểu - Minimum description length

MMR

mức độ cực đại tương ứng - Maximal Marginal Relevance

NB

Naïve Bayes

ROUGE


Recall Oriented Understudy for Gisting Evaluation

SOM

bản đồ tự tổ chức - Self Organizing Map

SVM

máy vectơ hỗ trợ - Support Vector Machine

STC

gom cụm dựa trên cây tiền tố - Suffix Tree Clustering

TF

tần suất xuất hiện của thuật ngữ - Term Frequency

TTVB

tóm tắt văn bản

VSM

mô hình không gian vectơ - Vector Space Model

log

logarit cơ số 10


4


DANH MỤC CÁC HÌNH
Hiǹ h 1.1. Framework chung cho hệ thống TTVB bằng phương pháp học máy ..13
Hiǹ h 2.1. Ví dụ mô hình đồ thị khái niệm ............................................................25
Hiǹ h 2.2. Ví dụ mô hình đồ thị hình sao biểu diễn văn bản .................................26
Hiǹ h 2.3. Ví dụ mô hình đồ thị hình sao biểu diễn email .....................................26
Hình 2.4 Ví dụ mô hình đồ thị tần số vô hướng ...................................................27
Hình 2.5. Ví dụ mô hình đồ thị đơn giản ..............................................................28
Hình 2.6. Ví dụ mô hình đồ thị khoảng cách n đơn giản ......................................29
Hình 2.7. Ví dụ mô hình đồ thị với đỉnh là câu ....................................................30
Hiǹ h 2.8. Minh họa mô hình đồ thị lưỡng phần với đỉnh là câu và từ .................31
Hiǹ h 3.1. Mô hình tóm tắt văn bản tiếng Việt ......................................................32
Hiǹ h 3.2. Qui trình bộ tóm tắt văn bản đơn ..........................................................33
Hiǹ h 3.3. Đồ thị biểu diễn văn bản .......................................................................35
Hiǹ h 3.4. Thuật toán xếp hạng câu .......................................................................37
Hình 3.5. Kết quả đánh giá bản tóm tắt văn bản đơn theo ROUGE-1 .................41
Hình 3.6. Kết quả đánh giá bản tóm tắt văn bản đơn theo ROUGE-2 .................41

5


MỞ ĐẦU
1. Tính cấp thiết của đề tài
Một ứng dụng phổ biến của dữ liệu đồ thị là biểu diễn văn bản, thường ở dạng
XML. Ngày nay, với sự phát triển bùng nổ của Internet, lượng thông tin văn bản được
sinh ra mỗi ngày vô cùng lớn đã mang lại nhiều lợi ích cho con người. Tuy nhiên, với
một lượng lớn thông tin như vậy thì người ta không thể nào có đủ thời gian và sức lực

để đọc hết được chúng khiến cho chúng ta khó khăn trong việc tìm kiếm, phân loại và
tổng hợp thông tin. Một giải pháp cho vấn đề này là tóm tắt văn bản tự động.
Đặc điểm của dữ liệu văn bản là thường không có cấu trúc hoặc bán cấu trúc, cơ
sở dữ liệu rất lớn, đa chiều. Những năm gần đây, mô hình biểu diễn văn bản bằng đồ thị
được đề xuất và sử dụng trong các bài toán khác nhau của khai thác văn bản và cho kết
quả tốt vì tận dụng được các thông tin quan trọng về cấu trúc văn bản.
Tóm tắt văn bản tự động được xác định là một bài toán thuộc lĩnh vực khái phá dữ
liệu văn bản; việc áp dụng tóm tắt văn bản sẽ giúp người dùng tiết kiệm thời gian đọc,
cải thiện tìm kiếm cũng như tăng hiệu quả đánh chỉ mục cho máy tìm kiếm.
Tại trường Đại học Tây Bắc chưa có nghiên cứu nhiều về tóm tắt văn bản. Do đó
chúng tôi chọn đề tài này nhằm nghiên cứu, khảo sát, đánh giá và đề xuất ra một phương
pháp tóm tắt văn bản hiệu quả. Qua đó nâng cao trình độ và giúp cho các giảng viên,
sinh viên có thêm tài liệu để tham khảo, nghiên cứu sâu hơn trong lĩnh vực khai phá dữ
liệu.

2. Mục tiêu đề tài
Nghiên cứu đồ thị, các dạng biểu diễn văn bản dựa trên đồ thị.
Nghiên cứu các phương pháp tóm tắt văn bản dựa trên đồ thị.
Đề xuất giải pháp nâng cao hiệu quả tóm tắt văn bản dựa trên đồ thị.
Thử nghiệm và đánh giá.

3. Đối tượng, phạm vi nghiên cứu
- Đối tượng nghiên cứu
Bài toán tóm tắt văn bản tự động.
6


- Phạm vi nghiên cứu
Biểu diễn văn bản dựa trên đồ thị và một số phương pháp tóm tắt văn bản theo
hướng tiếp cận học máy.


4. Phương pháp nghiên cứu
- Phương pháp phân tích, tổng hợp tài liệu.
- Phương pháp thực nghiệm.

5. Nội dung
Ngoài phần mở đầu và kết luận, đề tài có những nội dung sau:
Chương 1. Tổng quan về tóm tắt văn bản
Chương 2. Tóm tắt văn bản dựa trên đồ thị
Chương 3. Thực nghiệm và đánh giá

7


CHƯƠNG 1. TỔNG QUAN VỀ TÓM TẮT VĂN BẢN
1.1. Giới thiệu về tóm tắt văn bản
Tóm tắt văn bản chính thức được nghiên cứu lần đầu tiên vào năm 1958 bởi Luhn
(1958) [1], tiếp theo đó là Edmundson (1969) [2]. Tóm tắt văn bản được quan tâm và
nghiên cứu tích cực trong những năm gần đây cùng với sự bùng nổ thông tin trên web.
Tóm tắt văn bản là quá trình chắt lọc những thông tin quan trọng nhất từ một nguồn
(hoặc nhiều nguồn) và tạo ra một bản ngắn gọn hơn đáp ứng các nhiệm vụ cụ thể, cho
người dùng cụ thể. Tóm tắt văn bản có thể áp dụng cho từng văn bản lẫn tập văn bản
(các văn bản cùng chung chủ đề). Tóm tắt tập văn bản có độ phức tạp cao hơn rất nhiều
so với tóm tắt từng văn bản vì phải giải quyết nhiều vấn đề như: chi phí thuật toán, thông
tin phải được tổng hợp, chọn lọc từ nhiều văn bản và phải đảm bảo tính súc tích, cô
đọng, không trùng lắp thông tin.
Nội dung của bản tóm tắt phụ thuộc vào nhu cầu của người dùng. Bản tóm tắt theo
truy vấn tập trung vào câu truy vấn của người dùng và rút trích các thông tin liên quan
đến câu truy vấn này từ văn bản. Ngược lại bản tóm tắt tổng quát cố gắng bao quát đầy
đủ các nội dung và bảo toàn cấu trúc chung của văn bản gốc.

Bản tóm tắt có thể có dạng trích lược (extract) hoặc tóm lược (abstract) [3]. Bản
tóm tắt dạng trích lược gồm tập các câu từ văn bản gốc. Trong bản tóm tắt dạng tóm
lược, nội dung của văn bản gốc được viết lại, có thể chứa những câu hoàn toàn mới so
với văn bản gốc, những câu ngắn gọn hơn, trau chuốt hơn nhưng vẫn chuyển tải đầy đủ
nội dung của tài liệu. Mặc dù các bản tóm tắt do người dùng biên soạn thường không ở
dạng trích lược, nhưng phần lớn các nghiên cứu hiện này đều tập trung vào tóm tắt theo
dạng trích lược. Tóm lược văn bản đòi hỏi nhiều ở những tri thức chuyên sâu và liên
quan đến ngôn ngữ học, mà đặc biệt là các thành tựu của lĩnh vực xử lý ngôn ngữ tự
nhiên. Đó là lý do khiến bản tóm lược hiện nay chưa đạt kết quả tốt như bản trích lược.
Thật sự bài toán tóm tắt dạng trích lược chưa đạt đến mức độ hoàn chỉnh và các nghiên
cứu đi theo hướng này còn hạn chế. Các công cụ tóm lược hiện tại thường dựa trên các
thành phần trích lược đã xử lý trước. Kết quả đầu ra của quá trình trích lược sẽ được cắt,
dán hay tổng hợp và tạo ra bản tóm lược [4]

8


Bài toán tóm tắt văn bản hiện nay thường có khuynh hướng nghiêng về dạng trích
lược và sẽ được trình bày kỹ trong phần tiếp theo dưới đây. Mục đích của tóm tắt dạng
trích lược là xác định và lựa chọn các câu quan trọng nhất trong văn bản để tạo thành
bản tóm tắt. Có thể phân loại các phương pháp tóm tắt dạng trích lược theo các tiếp cận
[5]: sử dụng đặc trưng ngôn ngữ, đặc trưng Heuristic, thống kê và kết hợp của các
phương pháp trên.
Trong các tiếp cận này, mặc dù phương pháp sử dụng đặc trưng Heuristic được
nghiên cứu từ những năm 50 nhưng ý tưởng đó vẫn còn được sử dụng rộng rãi tại thời
điểm hiện nay. Từ những năm 90 đến nay, các hướng tiếp cận khác dựa trên thống kê,
các phương pháp máy học và lý thuyết đồ thị trở thành tiêu điểm của các nghiên cứu,
đạt được nhiều kết quả khả quan và trở thành hướng tiếp cận chính cho bài toán tóm tắt
dạng trích lược.
Đánh giá chất lượng bản tóm tắt là vấn đề khá khó khăn và phức tạp. Một bản tóm

tắt đạt yêu cầu khi nó thỏa các điều kiện sau: chuyển tải được toàn bộ nội dung chính
của văn bản một cách gãy gọn, thể hiện phải mạch lạc, không bị trùng lắp hay dư thừa
thông tin. Nhưng làm sao đánh giá được những tiêu chí này thì vẫn còn là một câu hỏi
khó. Một số phương pháp đánh giá đã được đề xuất như đánh giá dựa trên độ tương tự
về nội dung (độ đo cosine), đánh giá dựa trên độ chính xác (Precision), độ bao phủ
(Recall). Độ chính xác là phần trăm số câu của bản tóm tắt cần đánh giá trùng với bản
tóm tắt chuẩn, còn độ bao phủ là tỷ lệ giữa số câu trùng nhau với số câu trong bản tóm
tắt chuẩn.
Gần đây, các tác giả [6] đã xây dựng công cụ ROUGE (Recall Oriented Understudy
for Gisting Evaluation), một công cụ đánh giá tóm tắt sử dụng phương pháp n-gram. Ý
tưởng chính là xác định sự tương tự giữa các bản tóm tắt dựa trên số lượng n-gram trùng
nhau. Đây là phương pháp đánh giá tự động có độ chính xác cao, độc lập ngôn ngữ và
gần như tương đồng với đánh giá của con người. Công cụ ROUGE được sử dụng phổ
biến trong các nghiên cứu về tóm tắt văn bản trên thế giới

1.2. Phân loại các hệ thống tóm tắt văn bản
Có nhiều tiêu chí để phân loại các phương pháp tóm tắt văn bản, sau đây là một
9


số cách phân loại tiêu biểu [15]:
Theo kết quả (output):
Tóm tắt trích rút (Extract): là một bản tóm tắt bao gồm các đơn vị văn bản quan
trọng như câu, đoạn... được trích rút từ văn bản gốc.
Tóm tắt tóm lược (Abstract): tương tự như cách con người thực hiện tóm tắt, nghĩa
là đầu tiên phải hiểu các khái niệm chính của một văn bản, sau đó tạo ra bản tóm tắt có
chứa các nội dung không được thể hiện trong văn bản [3].
Theo mục đích hay chức năng tóm tắt (Function):
Tóm tắt chỉ thị (Indicative): tóm tắt nhằm cung cấp một chức năng tham khảo để
chọn tài liệu đọc chi tiết hơn (ứng dụng trong tóm tắt kết quả tìm kiếm).

Ví dụ: Trong tóm tắt tin tức, tóm tắt đưa ra chi tiết chính của từng sự kiện.
Tóm tắt thông tin (Information): tóm tắt bao gồm tất cả các thông tin nổi bật của
văn bản gốc ở nhiều mức độ chi tiết khác nhau.
Tóm tắt đánh giá (Evaluation): tóm tắt nhằm mục đích đánh giá vấn đề chính của
văn bản gốc theo quan điểm của người đánh giá.
Theo nội dung:
Tóm tắt chung (Generalized): tóm tắt nhằm mục đích đưa ra các nội dung quan
trọng phản ánh toàn bộ nội dung văn bản gốc.
Tóm tắt hướng truy vấn (Query-based): tóm tắt nhằm mục đích đưa ra kết quả dựa
vào câu truy vấn của người. Tóm tắt này thường được sử dụng trong quá trình tìm kiếm
thông tin (information retreival).
Theo miền dữ liệu:
Tóm tắt trên một miền dữ liệu (Domain): tóm tắt nhắm vào một miền nội dung nào
đó, như tin tức khủng bố, tin tức tài chính...
Tóm tắt trên một thể loại (Genre): tóm tắt nhắm vào một thể loại văn bản nào đó,
như báo chí, email, web, bài báo...
Tóm tắt độc lập (Independent): tóm tắt cho nhiều thể loại và nhiều miền dữ liệu.
10


Theo mức độ chi tiết:
Tóm tắt tổng quan (overview): tóm tắt miêu tả tổng quan tất cả các nội dung nổi
bật trong văn bản nguồn.
- Tóm tắt tập trung sự kiện (event): tóm tắt miêu tả một sự kiện cụ thể nào đó
trong văn bản nguồn.
Theo số lượng:
- Tóm tắt đơn văn bản: Nếu một bản tóm tắt được tạo thành từ một văn bản riêng
lẻ thì hệ thống tóm tắt đó được gọi là hệ thống tóm tắt đơn văn bản.
- Tóm tắt đa văn bản: Nếu một bản tóm tắt được tạo thành từ nhiều văn bản liên
quan tới một chủ đề riêng lẻ thì hệ thống tóm tắt đó gọi là hệ thống tóm tắt đa văn bản.

Theo ngôn ngữ:
- Tóm tắt đơn ngôn ngữ: Văn bản nguồn chỉ có một loại ngôn ngữ. Kết quả ra là
văn bản ngôn ngữ đó.
- Tóm tắt đa ngôn ngữ: Mỗi văn bản nguồn chỉ có một loại ngôn ngữ. Nhưng ứng
dụng có khả năng tóm tắt trên nhiều loại ngôn ngữ. Tùy vào văn bản nguồn hoặc tham
số mà hệ thống tóm tắt trên một ngôn ngữ được chọn.
Tóm tắt xuyên ngôn ngữ (cross-language): Trong văn bản nguồn chứa hai hay
nhiều ngôn ngữ khác nhau, hệ thống có thể tùy vào từng đơn vị ngữ liệu mà nhận dạng
và tóm tắt cho phù hợp. Đây là loại tóm tắt phức tạp nhất trong ba loại phân chia theo
số lượng ngôn ngữ.

1.3. Tình hình nghiên cứu trong và ngoài nước
1.3.1. Ngoài nước
1.3.1.1. Các phương pháp tóm tắt trích rút
Các phương pháp tóm tắt trích rút cố gắng tìm ra các đơn vị quan trọng nhất của
một văn bản đầu vào và chọn các câu có liên quan tới các đơn vị quan trọng này để tạo
ra bản tóm tắt.

11


a. Các phương pháp tiên phong
Nghiên cứu đầu tiên về tóm tắt văn bản vào những năm 50 của thế kỷ 20 là của
Luhn [1] được dựa trên tần suất các từ trong văn bản với quan điểm từ xuất hiện thường
xuyên là từ quan trọng nhất. Câu chứa nhiều từ thường xuyên quan trọng hơn các câu
khác và được chọn trong bản tóm tắt.
Sau nghiên cứu của Luhn, các nhà nghiên cứu đề xuất rất nhiều phương pháp khác
dựa trên các đặc trưng đơn giản khác như các từ khóa/cụm từ khóa, vị trí câu [5].
b. Các phương pháp thống kê
Các phương pháp tóm tắt nổi tiếng nhất dùng thống kê là dựa trên khái niệm tương

quan và phân loại Bayes.
Dự án SUMMARIST [7] là một dự án tóm tắt văn bản nổi tiếng dùng phương pháp
thống kê. Trong dự án này thông tin về khái niệm tương quan trích rút từ các từ điển và
WordNet được dùng cùng với các phương pháp xử lý ngôn ngữ tự nhiên. Trong phương
pháp này, một từ được cho là có xuất hiện khi các từ khác có liên quan cũng xuất hiện.
Ví dụ số các lần xuất hiện của từ “automobile” được tăng lên nếu ta đã thấy từ “car”.
Một ứng dụng tóm tắt khác dựa trên thống kê là của Kupiec, trong đó phân loại
Bayes được dùng để trích rút câu. Trong phương pháp này tác giả dùng một kho ngữ
liệu các bản văn và các bản tóm tắt để huấn luyện hệ thống. Các đặc trưng được sử dụng
trong hệ thống này là tần suất xuất hiện các từ, các từ viết hoa, độ dài câu, vị trí trong
các đoạn và cấu trúc cụm từ.
c. Các phương pháp dựa trên kết nối bản văn
Phương pháp này liên quan tới các bài toán tham chiếu tới các phần đã được đề
cập của một văn bản. Các phương pháp sử dụng chuỗi từ vựng và Lý thuyết cấu trúc tu
từ RST (Rhetorical Structure Theory).
Phương pháp chuỗi từ vựng là một thuật toán nổi tiếng sử dụng kết nối bản văn.
Trong phương pháp này, mối tương quan ngữ nghĩa của các từ (tính đồng nghĩa, tính
trái nghĩa,...) được thực hiện bằng cách sử dụng các từ điển và WordNet. Các chuỗi từ
vựng có mối tương quan ngữ nghĩa được xây dựng được sử dụng để trích rút các câu
quan trọng trong một văn bản.
12


Các phương pháp dựa trên RST để tổ chức các đơn vị bản văn thành cấu trúc dạng
cây. Sau đó cấu trúc này được sử dụng để thực hiện tóm tắt [8].
d. Các phương pháp dựa trên đồ thị [9]
Phương pháp đồ thị được xây dựng dựa trên các thuật toán HITS và Google’s
PageRank. Các thuật toán này sau đó được dùng trong tóm tắt văn bản.

Hình 1.1. Framework chung cho hệ thống TTVB bằng phương pháp học máy

Trong bài toán tóm tắt văn bản dựa vào đồ thị, các đỉnh biểu diễn các câu, còn các
cạnh biểu diễn độ tương tự giữa các câu. Các giá trị đo độ tương tự được tính toán bằng
cách sử dụng độ tương tự giữa các từ hoặc các cụm từ. Các câu có độ tương tự cao nhất
với các câu khác được chọn ra cho bản tóm tắt đầu ra theo tỷ lệ tóm tắt. Điển hình cho
hướng tiếp cận tóm tắt văn bản dựa trên đồ thị là hai phương pháp TextRank và Cluster
LexRank.
e. Các phương pháp dựa vào học máy [10]
Các phương pháp dựa vào học máy cũng được sử dụng cho tóm tắt văn bản với sự
hỗ trợ của các tiến bộ trong học máy và xử lý ngôn ngữ tự nhiên. Các phương pháp đầu
tiên sử dụng giả thiết các đặc trưng độc lập với nhau. Các phương pháp phát triển sau
đó lại sử dụng giả thiết các đặc trưng phụ thuộc lẫn nhau. Các thuật toán tóm tắt dựa
trên học máy sử dụng các kỹ thuật như Naïve- Bayes, mô hình Markov ẩn HMM, các
13


mô hình logarit tuyến tính (Log-linear Models) mạng nơ-ron và giải thuật phỏng sinh
học như.
1.3.1.2. Các phương pháp tóm tắt theo hướng tóm lược [3], [11], [12]
Các phương pháp tóm tắt tóm lược cố gắng để hiểu đầy đủ các văn bản cần tóm
tắt, ngay cả các văn bản có chủ đề không rõ ràng. Sau đó, tạo ra các câu mới cho bản
tóm tắt theo tỉ lệ của người dùng yêu cầu. Phương pháp này rất giống với cách tóm tắt
của con người. Nhưng về mặt thực tế, để đạt được biểu diễn của con người rất khó. Do
đó, các nghiên cứu đã dựa vào các đơn vị đặc trưng như từ, cụm từ, thành phần câu quan
trọng để sinh ra các câu mới cho tóm tắt văn bản.
Theo hướng này có: phương pháp dựa vào các từ hay cụm từ quan trọng để tạo ra
các câu cho bản tóm tắt, phương pháp dựa trên kỹ thuật cô đọng văn bản, phương pháp
dựa trên kỹ thuật rút gọn văn bản, nối hai hay nhiều câu thành một câu, phương pháp
dựa trên kỹ thuật rút gọn câu để tạo ra bản tóm tắt.
1.3.2. Trong nước
Tại Việt Nam hiện nay, lĩnh vực xử lý ngôn ngữ tự nhiên đã có được thành tích

trong các bài toán phân tách từ, phân lớp và phân nhóm văn bản. Tuy nhiên bài toán tóm
tắt văn bản chưa có nhiều nghiên cứu và đa phần các công trình nghiên cứu đều sử dụng
hoặc cải tiến các phương pháp dựa trên thống kê, cũng có một số nghiên cứu có dựa trên
ngữ nghĩa để nâng cao độ chính xác.
Có thể kể đến một số công trình nghiên cứu như:
Đỗ Phúc, Hoàng Kiếm (2006) [13] đã sử dụng cây hậu tố để phát hiện các dãy từ
phổ biến trong các câu của văn bản, dùng từ điển đồng nghĩa và WordNet tiếng Việt để
giải quyết vấn đề nghĩa của từ, rồi dùng kĩ thuật gom cụm để gom các câu trong văn bản
(vector đặc trưng cho câu) và hình thành các vector đặc trưng cụm, sau đó rút ra câu
chứa nhiều thành phần của các vector đặc trưng cụm.
Vương Toàn (2007) [14] đã đề xuất quy trình tóm tắt văn bản khoa học. Theo đó,
đầu tiên cho máy đọc lướt văn bản và tìm xem có sẵn những đoạn văn mang tính chất
“tóm tắt” hay không; tiếp theo là định chủ đề, xác định 4-5 tiêu đề đề mục hoặc từ khoá
để máy tự động chọn lưu tất cả những câu có các từ khoá đó.
Công trình nghiên cứu của Nguyễn Trọng Phúc, Lê Thanh Hương (2008) [15] lại
sử dụng cấu trúc diễn ngôn để tóm tắt văn bản. Theo đó, xây dựng cây cấu trúc diễn
14


ngôn biểu diễn mỗi quan hệ diễn ngôn giữa các đoạn văn bản (như các quan hệ nhânquả, liệt kê, diễn giải,...), rồi từ cây cấu trúc diễn ngôn này đánh giá được độ quan trọng
của các đoạn văn bản và tiến hành trích xuất tạo ra tóm tắt nội dung cho văn bản.
Với hướng tiếp cận tóm tắt đa văn bản dựa vào trích xuất câu, Trần Mai Vũ (2009)
[16] đã xây dựng đồ thị quan hệ thực thể để tăng cường tính ngữ nghĩa cho độ tương
đồng câu để áp dụng cho tóm tắt đa văn bản tiếng Việt.

1.4. Mô hình biểu diễn văn bản
Khi khai thác tập văn bản, ta cần tiền xử lý văn bản và lưu trữ thông tin ở dạng cấu
trúc phù hợp hơn để xử lý sau này thay vì các tập tin văn bản thuần túy. Mô hình biểu
diễn văn bản là một trong những nhân tố quan trọng của quá trình khai thác văn bản.
Hiện nay, có nhiều mô hình biểu diễn văn bản. Mô hình đơn giản nhất là mô hình

túi từ. Toàn bộ từ trong tập văn bản được sử dụng cho việc xây dựng vectơ nhị phân
biểu diễn văn bản. Mỗi chiều của vectơ đại diện cho một từ và nhận giá trị 1 khi từ xuất
hiện trong văn bản và ngược lại. Mô hình không gian vectơ là mô hình phát triển từ mô
hình túi từ. Trong mô hình này, mỗi văn bản được biểu diễn thành một vectơ của các
thuật ngữ (từ/cụm từ) với giá trị của mỗi chiều thường là trọng số của thuật ngữ. Mô
hình biểu diễn bằng đồ thị là mô hình với đỉnh có thể là từ, cụm từ hay câu hoặc kết hợp
câu và từ. Cạnh nối giữa các đỉnh thể hiện mối quan hệ trong đồ thị. Mô hình N-gram là
mô hình được sử dụng phổ biến trong xử lý ngôn ngữ tự nhiên với các từ được biểu diễn
như chuỗi ký tự có độ dài N. Trong mô hình N-gram, văn bản được tách ra thành các
chuỗi n ký tự liên tục và thường không sử dụng thông tin ngữ nghĩa hay đặc trưng ngôn
ngữ. Phần tiếp theo tập trung giới thiệu mô hình không gian vectơ.
Mô hình không gian vectơ là phương pháp biểu diễn văn bản phổ biến trong lĩnh
vực truy vấn thông tin và trong một số tiếp cận khai thác văn bản. Với mô hình này, các
văn bản được biểu diễn thành vectơ trong không gian m - chiều. Mỗi chiều của không
gian tương ứng với một thuật ngữ (có thể là từ đơn lẻ, từ khóa hay cụm từ dài) riêng
biệt. Hay nói một cách khác, tất cả các thuật ngữ trong CSDL tạo thành “không gian”
với mỗi thuật ngữ đại diện cho một “chiều”. Với mục đích phân biệt văn bản này với
văn bản khác, trọng số được gán cho từng thuật ngữ nhằm xác định độ quan trọng của
thuật ngữ trong văn bản. Giá trị của mỗi thành phần trong vectơ là trọng số của thuật
ngữ tương ứng. Có nhiều cách tính trọng số này, trong đó TFxIDF là phương pháp phổ
biến nhất.
15


CHƯƠNG 2. BIỂU DIỄN VĂN BẢN BẰNG ĐỒ THỊ
2.1. Tổng quan về đồ thị
Dữ liệu đồ thị đã và đang được quan tâm nghiên cứu nhiều vì chúng có ứng dụng
đa dạng phong phú trong lý thuyết cũng như trong thực tế ở rất nhiều lĩnh vực khác
nhau: xử lý ngôn ngữ tự nhiên, văn bản được biểu diễn theo cấu trúc chuỗi, cây, hoặc
đồ thị; trong tin sinh học, các chuỗi DNA, RNA, proteins được biểu diễn ở dạng chuỗi

và đồ thị; trong lĩnh vực phân tích các mạng xã hội [17], phân tích các liên kết web.
2.1.1. Khái niệm cơ sở
Định nghĩa 2.1. Cho đồ thị G  V , E  , trong đó V là tập các đỉnh và E là tập các
cạnh. Đường đi có độ dài n đi từ nút v đến w là dãy các cạnh

 v0 , v1  ,  v1, v2  , .,  vn1, vn  , trong đó v0 = v, vn = w và  vi , vi1   E . Đường đi đơn là
đường đi không đi qua một đỉnh nào quá một lần. Hiển nhiên đường đi ngắn nhất đi từ
đỉnh s đến đỉnh t là đường đi đơn có độ dài (số cạnh) ít nhất trong số các đường đi giữa
hai đỉnh.
Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một
cặp đỉnh. Một cạnh (v, w) của đồ thị G được gọi là khuyên (loop) nếu v = w. Đồ thị
không có các cạnh bội được gọi là đơn đồ thị, ngược lại gọi là đa đồ thị. Trong phần này
chúng ta chỉ xét những đơn đồ thị, gọi tắt là đồ thị.
Hai đỉnh u và v trong đồ thị G được gọi là liền kề nếu (u, v)  E, hoặc (v, u)  E.
Nếu e = (u, v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Các đỉnh u và v gọi là các
điểm đầu mút của cạnh e. Một đồ thị có k cạnh (|E| = k) được gọi là k-đồ thị.
Định nghĩa 2.2. Bậc của đỉnh v trong đồ thị G, ký hiệu deg  v  , là số các cạnh liên
thuộc với nó, Đỉnh v gọi là đỉnh treo nếu deg(v) = 1 và gọi là đỉnh cô lập nếu deg  v   0
. Bậc của đỉnh là số các đỉnh liền kề với đỉnh đó.
Tính chất 2.1. Mọi đơn đồ thị n đỉnh  n  2 có tổng bậc của hai đỉnh tuỳ ý không
nhỏ hơn n đều là đồ thị liên thông.
Tính chất 2.2. Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên
thông, tức là có một đường đi nối chúng.
16


Định nghĩa 2.3. Danh sách liền kề (Adjacency List). Với mỗi đỉnh i của đồ thị
chúng ta lưu trữ danh sách các đỉnh kề với nó, ký hiệu là

List  i  ,


List  i   { j V : i, j   E or  j, i   E} ,

Với cách biểu diễn này, mỗi đỉnh i của đồ thị tương ứng với một danh sách tất cả
các đỉnh kề với nó và được ký hiệu là List(i). Để biểu diễn List(i), ta có thể dùng các
kiểu dữ liệu kiểu tập hợp, mảng hoặc danh sách liên kết (DSLK).
Định nghĩa 2.4. Giả sử G = (V, E) là đồ thị có n đỉnh  V  n  ,V  v1 , v2 , , vn  .
Ma trận liền kề (adjacency matrix) của đồ thị G ứng với thứ tự các đỉnh v1, v2,..., vn là
ma trận A  ai , j | i, j  1 n , trong đó ai,j = 1 nếu (vi, vj)  E, ngược lại ai,j = 0.
Cho trước một đồ thị có tập đỉnh V = {v1, v2,…, vn} thì sẽ có n! ma trận liền kề
tương ứng, bởi vì ứng mỗi cách sắp xếp các đỉnh (một hoán vị của V) thì ta có một ma
trận liền kề. Cho trước đồ thị G, ta ký hiệu AM(G) là tập các ma trận liền kề của G.
Với đồ thị không có trọng số chúng ta có tính chất sau:
Tính chất 2.3. Cho G là một đồ thị (vô hướng không có trọng số) với ma trận liền
kề A theo thứ tự các đỉnh v1, v2, ..., vn. Khi đó số các đường đi khác nhau độ dài r từ vi
tới vj trong đó r là một số nguyên dương, bằng giá trị của phần tử dòng i cột j của ma
trận Ar.
Định nghĩa 2.5. Giả sử A là ma trận liền kề của một đồ thị. Ta ký hiệu diag[A] là
vector biểu diễn tất cả các phần tử trên đường chéo chính của A. Tương tự, upper[A] là
vector biểu diễn tất cả các phần tử phần tam giác trên của A (không kể các phần tử trên
đường chéo chính).
Định nghĩa 2.6. Cho đồ thị vô hướng G = (V, E), với v1, v2,…, vn là các đỉnh và e1,
e2, ..., em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma
trận A = {ai,j | i = 1..n, j = 1..m}, trong đó ai,j là bằng 1 nếu cạnh ej nối với đỉnh vi và
bằng 0 nếu cạnh ej không nối với đỉnh vi.
Định nghĩa 2.7. Hợp của hai đơn đồ thị G1 = (V1, E1) và G2 = (V2, E2) là một đơn
đồ thị G có tập các đỉnh là V1  V2 và tập các cạnh là El  E2, ký hiệu là G = G1  G2.

17



Định nghĩa 2.8. Đơn đồ thị G’  V , E’ được gọi là đồ thị bù của đơn đồ thị
G  V , E  nếu G và G’ không có cạnh chung nào (E  E’= ) và G  G’là đồ thị đầy

đủ.
Dễ thấy rằng nếu G’ là bù của G thì G cũng là bù của G’. Khi đó ta nói hai đồ thị
là bù nhau.
Định nghĩa 2.9. Cho trước hai đồ thị G = (V, E), với mỗi S  V, đồ thị con cảm
sinh (induced) bởi S trong đồ thị, ký hiệu là GS  ( S , E  SxS ) .
Định nghĩa 2.10. Cạnh eE được gọi là cầu nối (bridge) nếu G - e có số thành
phần liên thông nhiều hơn G.
Trong đó, G - e = (V, E - {e}), là đồ thị thu được bằng cách bỏ đi cạnh e.
Định nghĩa 2.11. Đỉnh v  V được gọi là đỉnh khớp (articulation) của đồ thị G nếu
G - V có số thành phần liên thông hơn G. Trong đó, G - V = (V - {v}, E - {(v, u) E | u
 V}) , là đồ thị thu được bằng cách bỏ đi đỉnh V và các cạnh liền kề với V.
Nhận xét:
(i)

Hai đỉnh liền kề của cạnh cầu nối là các đỉnh khớp.

(ii) Nếu e là cầu nối thì mọi đường đi từ các đỉnh của một thành phần liên thông
tới các đỉnh của một thành phần liên thông khác của G-e đều phải đi qua e.
Ngoài ra, dễ nhận thấy, các đỉnh khớp là những đỉnh có tần quan trọng trong việc
liên kết với nhiều thành phần liên thông trên mạng. Tương tự, cạnh cầu nối là đóng vai
trò quan trọng trong các mối liên kết, truyền thông trên mạng.
2.1.2. Các độ đo trên đồ thị
Giả thiết có một đồ thị vô hướng, liên thông G = (V, E), trong đó V là tập các đỉnh,
E là tập các cạnh. Ta qui ước, những đỉnh gần nhau (closed) nếu chúng có cạnh nối trực
tiếp, ngược lại là xa nhau (distant). Khoảng cách giữa đỉnh x và y V, ký hiệu là d(x, y),
có thể định nghĩa d(x, y) theo hai cách:

■ d(x, y) = 0 nếu (x, y)  E, ngược lại là d(x, y) = 1.
■ Hoặc d(x, y) = 1 nếu có cạnh nối giữa chúng, và bằng ∞ khi chúng xa nhau.
18


Tuy nhiên, cả hai trường hợp trên đều không phải là định nghĩa độ đo khoảng cách
thực sự (metric), bởi chúng không thỏa mãn bất đẳng thức tam giác.
3.1. Độ trung tâm theo bậc của đỉnh
Độ trung tâm theo bậc của đỉnh được định nghĩa là số các đường liên kết (các cạnh)
với một đỉnh. Những đỉnh có bậc cao hơn sẽ có độ trung tâm (quan trọng) cao hơn.
Độ trung tâm theo bậc của đỉnh v là: CD(V) = deg(v).
Độ trung tâm theo bậc của đỉnh v V được chuẩn hóa như sau:
CD(V) = deg(v) / (n-1)
Các độ trung tâm theo bậc được xếp theo thứ tự giản dần và số thứ tự của từng độ
đo sẽ xác định thứ hạng (ranking) của đỉnh tương ứng trên đồ thị.
Tính chất 2.4. Giả sử K  Rn là vector bậc của các đỉnh V = {v1, v2, ..., vn} và I
Rn là vector đơn vị (tất cả thành phần là 1), A là ma trận liền kề của đồ thị G = (V, E).
Khi đó:

K = AI.

3.2. Độ trung gian của đỉnh
Xét một đồ thị G = (V, E) liên thông, vô hướng. Xét cặp đỉnh {vi, vj} bất kỳ của G,
không phân biệt thứ tự. Giữa chúng có thể có một hoặc nhiều đường đi. Trong số các
đường đi đó sẽ có một số đường đi ngắn nhất. Nếu {vi, vj}, {vi, vj} E, thi đường đi ngắn
nhất sẽ có độ dài là 1. Trường hợp đường đi ngắn nhất lớn hơn 1 thi chắc chắn phải có
ít nhất một đỉnh khác nằm trên đường đi ngắn nhất nối giữa vi với vj và những đỉnh này
có tiềm năng để điều khiển sự liên kết hay truyền thông giữa các đỉnh vi, vj.
Độ trung gian (Betweenness) là độ đo trung tâm của các đỉnh trong đồ thị. Những
đỉnh xuất hiện trên nhiều đường đi ngắn nhất giữa các đỉnh có độ trung gian cao hơn

những đỉnh không nằm trên những đường đi ngắn nhất đó.
Để tiện lợi việc tính toán các độ đo trung gian, độ trung tâm của các đỉnh trên đồ
thị, chúng ta sử dụng các ký hiệu sau:
-

st là số đường đi ngắn nhất đi từ s tới t.

-

st (v) là số đường đi ngắn nhất từ s tới t, đi qua v.

-

st(v) = st (v) /st là độ phụ thuộc của cặp đỉnh s, t vào v.
19


-

s (v) =



tV

 st (v) /  st là độ phụ thuộc của đỉnh nguồn s vào v.

Lưu ý: vì ở đây ta xét đồ thị vô hướng nên các cạnh có tính đối xứng, do đó đường
đi cũng có tính đổi xứng, nghĩa là st (v)= ts (v) và st (v) = ts (v).
Định nghĩa 2.12. Cho đồ thị G = (V, E) có n đỉnh, độ trung gian của đỉnh v, ký hiệu

là CB(v) xác định như sau:
- Với mỗi cặp đỉnh (s, t), tính tất cả các đường đi ngắn nhất nối giữa chúng - σst;
- Với mỗi cặp đỉnh (s, t), tính phân số giữa những đường đi ngắn nhất σst (v) có đi
qua v và số tất cả các đường đi ngắn nhất từ s tới t là: σst (v)/ σst;
- Tính tổng các phân số của tất cả các cặp đỉnh (s, t) vào v. CB(v) được tính cụ thể
như sau:
CB (V )  s t v  st (v) s t v  st (v) /  st

Từ tính chất đối xứng của các đường đi nêu trên suy ra chỉ cần tính một chiều từ s
đến t, không cần tính chiều ngược lại.
Độ trung gian có thể chuẩn hóa bằng cách chia cho số các cặp đỉnh không kể đỉnh
v, nghĩa là đối với đồ thị có hướng là chia cho (n − 1)(n − 2), còn đối với đồ thị vô
hướng thì chia cho (n − 1)(n − 2)/2.
Việc tính CB(v) phụ thuộc vào hai yếu tố chính: sắp xếp các cạnh để xác định vị
trí của v và những đường đi ngắn nhất giữa các cặp đỉnh; Số đỉnh n trên đồ thị.
Chúng ta nhận thấy, độ trung gian của đỉnh v đạt được giá trị cực đại khi mọi đỉnh
khác trong G đều có cạnh nối với v và v nằm trên tất cả các đường đi ngắn nhất có độ
dài lớn hơn 1. Những đồ thị như thế sẽ có dạng hình sao hoặc bánh xe. Trong đồ thị, khi
mọi đỉnh đều đến được (có đường đi) tới tất cả các đỉnh khác (trực tiếp hoặc gián tiếp đi
qua v) thì số đường đi giữa chúng là n * (n – 1) / 2, trong đó có n-1 được nối với đỉnh v.
Vậy, độ trung gian cực đại của đỉnh v sẽ là:

Lưu ý 1: Tất cả các đỉnh treo w (có bậc là 1) đều có CB(w) = 0.
20


3.3 Độ gần nhau theo khoắng cách trắc địa
Trong lý thuyết đồ thị, độ gần nhau là độ đo trung tâm của các đỉnh trong một đồ
thị. Những đỉnh che bóng các đỉnh khác (những đỉnh có khuynh hướng có những khoảng
cách trắc địa ngắn (short geodesic distances) tới những đỉnh khác sẽ có độ gần nhau

nhiều hơn.
Trong lý thuyết mạng, độ gần nhau là độ trung tâm khá phức tạp. Nó được định
nghĩa theo những khoảng cách trắc địa (geodesic distance), là số các đường đi ngắn nhất
giữa đỉnh v và những đình khác mà nó có đường đi tới. Cụ thể:

Trong đó, σvt là số đường đi ngắn nhất đi từ v đến t. Độ gần nhau được xem như
là độ dài mà luồng thông tin có thể đi qua từ một đỉnh cho trước tới những đỉnh khác.
Độ gần nhau Cc(v) của đỉnh v được định nghĩa là tỷ lệ nghịch với tổng các khoảng
cách trắc địa tới tất cả các đỉnh của V:

3.4. Độ đo trung tâm của đồ thị
Độ đo trung tâm của đồ thị được xác định theo hai cách. Cách thứ nhất dựa vào lý
thuyết đồ thị, trung tâm của đồ thị được đánh giá theo bậc (degre) của các đỉnh trong đồ
thị. Những đỉnh có bậc cực đại có thể được xem như là tâm điểm của đồ thị. Đo theo
cách này thì việc ứng dụng sẽ bị hạn chế, bởi nó chỉ áp dụng được cho những bài toán
như thiết kế truyền thông với mục đích là nhằm đạt được hiệu quả truyền thông cực đại.
Cách thứ hai là dựa vào ưu thế trội (Domination) của các đỉnh. Một đỉnh có ưu thế trội
là đỉnh có thể điều khiển sự truyền thông trên đồ thị.
Định nghĩa 2.13. Đỉnh trung tâm của đồ thị G là đỉnh vk* có độ trung gian C’(vk*)
đạt giá trị cực đại. Khi đó, độ trội (ưu thế) của đỉnh trung tâm nhất trong đồ thị sẽ là:

Đây là độ lệch trung bình của đỉnh trung tâm nhất so với các đỉnh khác. Giá trị CG
luôn nằm trong khoảng 0 và 1. Dễ nhận thấy, CG = 0 với mọi đồ thị G mà độ trung tâm
21


của tất cả các đỉnh đều bằng nhau, và CG = 1 cho những đồ thị hình sao hoặc hình bánh
xe.
3.5 Độ đo trung gian của cạnh
Chúng ta đã nghiên cứu ba độ đo CB(V), CC(v), CG để xác định những tâm điểm

của đồ thị và chúng được ứng dụng trong nhiều mục đích khác nhau. Trong đó khái niệm
độ trung gian (Betweenness) được xem là quan trọng, có ảnh hưởng tới quá trình xử lý
sự liên kết giữa các đỉnh.
Chúng ta định nghĩa độ trung gian của các cạnh trên đồ thị như sau.
Định nghĩa 2.14. Độ trung gian của cạnh (a, b) là số các cặp đỉnh x và y mà cạnh
(a, b) nằm trên đường đi ngắn nhất nối giữa x và y. (Lưu ý: x, y có thể trùng với a, b).
Ta hình dung, cạnh (a, b) giữa hai cộng đồng thì a và b không nằm trong cùng một
cộng đồng. Một cạnh nằm giữa hai cộng đồng được xem như là cầu nối giữa hai cộng
đồng đó, do vậy số các đường đi ngắn nhất đi qua cạnh đó thường là khá lớn.
3.6. Độ trung tâm vector đặc trưng
Độ trung tâm (vị thế) không chỉ phụ thuộc vào số các đỉnh liền kề mà còn phụ
thuộc vào độ trung tâm của những đỉnh liền kề với những đỉnh đó. Độ trung tâm của
đỉnh thường xác định tổng quát theo quan hệ đệ qui (recursively related) theo các độ
trung tâm mà chúng có mối liên kết (trực tiếp hoặc gián tiếp) với nhau. Độ đo đó được
gọi là độ trung tâm đặc trưng (Eigenvector).
Định nghĩa 2.15. Giả thiết A là ma trận liền kề không âm của đồ thị vô hướng G =
(V, E). Độ trung tâm xi của đỉnh i định nghĩa như sau:
xi  Ai1 x1  Ai 2 x2  ...  Ain xn , i  1, 2,..., n .

Độ trung tâm đặc trưng của mỗi cá thể xi là một hàm của những cá thể có liên kết
với cá thể đó. Tập các phương trình được thể hiện theo ma trận (AT là ma trận chuyển vị
của A) là: AT x = x
Độ trung tâm của đình i cùng với các đỉnh lân cận của nó là N(i):

22


2.2. Mô hình biểu diễn văn bản bằng đồ thị [18]
Hiện nay, chúng ta dùng các mô hình biểu diễn để giải quyết hầu hết những vấn
đề liên quan đến văn bản. Các mô hình biểu diễn đóng vai trò trung gian giữa ngôn ngữ

tự nhiên dạng văn bản và chương trình xử lý trong các lĩnh vực khai thác dữ liệu văn
bản, truy vấn thông tin, xử lý ngôn ngữ tự nhiên. Sau khi được tái thể hiện, văn bản trở
thành những cấu trúc dữ liệu trực quan, đơn giản và có thể xử lý được. Vì vậy, các mô
hình biểu diễn không ngừng phát triển, hàm chứa được nhiều hơn những suy nghĩ mà
con người muốn diễn đạt, đồng thời nâng cao hiệu quả sử dụng. Mô hình biểu diễn văn
bản truyền thống như: mô hình túi từ và không gian vectơ là các mô hình được sử dụng
phổ biến nhất. Mô hình không gian vectơ biểu diễn văn bản như một vectơ đặc trưng
của các thuật ngữ (từ) xuất hiện trong toàn bộ tập văn bản. Trọng số các đặc trưng thường
được tính qua độ đo TF x IDF. Tuy nhiên, mô hình này không nắm bắt được các thông
tin cấu trúc quan trọng như trật tự xuất hiện của các từ, vùng lân cận của từ, vị trí xuất
hiện của từ trong văn bản. Nhằm giải quyết các hạn chế trên, mô hình đồ thị được đề
xuất và được đánh giá có nhiều tiềm năng vì tận dụng được các thông tin quan trọng về
cấu trúc mà mô hình túi từ và không gian vectơ đã bỏ qua.
Mô hình đồ thị biểu diễn văn bản, cụ thể là mô hình đồ thị khái niệm (Conceptual
Graphs - CGs). Hiện nay, mô hình đồ thị không ngừng phát triển dựa trên ý tưởng của
mô hình CGs, được ứng dụng vào dãy rộng các bài toán liên quan đến xử lý văn bản và
trở nên khá phong phú. Khi ứng dụng vào từng loại bài toán khác nhau, các thành phần
thích hợp nhất trong văn bản trở thành đỉnh của đồ thị và mối quan hệ hiệu quả nhất
giữa các đỉnh được chọn để xây dựng cạnh của đồ thị. Đỉnh của đồ thị có thể biểu diễn
câu, từ, hay câu kết hợp từ. Cạnh có thể thể hiện những mối quan hệ khác nhau giữa các
đỉnh như: trật tự xuất hiện, tần suất đồng hiện, vị trí xuất hiện, độ tương đồng.
Các mô hình đồ thị được sử dụng hiện nay tương đối đa dạng và mỗi mô hình
mang nét đặc trưng riêng. Dưới đây giới thiệu những đặc tính khái quát của một số mô
hình đồ thị biểu diễn văn bản chính như sau.
Mỗi đồ thị là một văn bản hoặc biểu diễn cho tập văn bản. Đỉnh của đồ thị có thể
là câu, hoặc từ, hoặc kết hợp các thành phần khác nhau của văn bản (ví dụ như câu và
23


từ). Cạnh nối giữa các đỉnh là vô hướng hoặc có hướng, thể hiện mối quan hệ trong đồ

thị. Nhãn đỉnh thường là tần suất xuất hiện của đỉnh. Còn nhãn cạnh là tên mối liên kết
khái niệm giữa hai đỉnh, hay tần suất xuất hiện chung của hai đỉnh trong một phạm vi
nào đó, hay tên vùng mà đỉnh xuất hiện.
Chẳng hạn trong bài toán rút trích thông tin, đỉnh là từ hay từ kết hợp câu [109],
cạnh thể hiện tần suất đồng hiện. Trong bài toán phân lớp văn bản, đỉnh là từ, cạnh thể
hiện trật tự xuất hiện của từ hay vị trí xuất hiện của từ trong văn bản. Còn trong bài toán
tóm tắt văn bản thì đỉnh là câu, cạnh thể hiện sự tương đồng giữa các câu.
Do thông tin cấu trúc quan trọng của văn bản thể hiện ở trật tự xuất hiện của từ,
vùng lân cận của từ, cũng như vị trí xuất hiện của từ trong văn bản nên mô hình đồ thị
sử dụng đỉnh là từ được nghiên cứu sâu hơn và có nhiều biến thể nhất.
Sau đây, sẽ trình bày chi tiết một số mô hình đại diện với đỉnh biểu diễn từ. Đó là
mô hình đồ thị khái niệm, đồ thị hình sao, đồ thị tần số xuất hiện vô hướng, đồ thị đơn
giản, đồ thị khoảng cách n đơn giản. Bên cạnh đó mô hình với đỉnh là câu và mô hình
đồ thị lưỡng phần cũng đề cập đến.
2.2.1. Mô hình đồ thị khái niệm
Mô hình đồ thị khái niệm (Conceptual Graphs - CGs) sử dụng mạng ngữ nghĩa
biểu diễn văn bản thành đồ thị.
Định nghĩa 2.16: Mô hình đồ thị khái niệm
Mô hình đồ thị khái niệm là mô hình coi 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.
Ví dụ 2.1: Ta có câu: “Jonh is going to Boston by bus”.

24