ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
   NGUYỄN HOÀNG TÚ ANH TIẾP CẬN ĐỒ THỊ
BIỂU DIỄN, KHAI THÁC VĂN BẢN VÀ ỨNG DỤNG
Chuyên ngành: Đảm bảo toán học cho máy tính và hệ
thống tính toán
Mã số chuyên ngành: 1.01.10
TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC
Tp. Hồ Chí Minh, năm 2011

1
1. Mở đầu
1.1 Dẫn nhập
Trong những năm gần đây, lĩnh vực Khám phá tri thức trong cơ sở dữ liệu (Knowledge
Discovery in Databases – KDD) hay còn được gọi là Khai thác dữ liệu (Data mining) đã ra
đời và phát triển nhanh chóng.
Theo đánh giá của công ty Oracle [28], hiện có đến 80% dữ liệu trên thế giới là dữ liệu
văn bản, vì vậy khai thác dữ liệu văn bản là vấn đề quan trọng, đầy thử thách và cần được đầu
tư nghiên cứu. Đặ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 và hay bị nhiễu. Ngoài ra đối với dữ liệu văn bản chúng ta còn
phải đối mặt với vấn đề nhập nhằng ở nhiều cấp độ (cấp độ về từ, ngữ, câu), ở nhiều khía
cạnh (hình thái, ngữ pháp, ngữ nghĩa).
Luận án này nghiên cứu khai thác dữ liệu văn bản, hay còn gọi là khai thác văn bản. Khai
thác văn bản là “sự tìm kiếm thông tin mới, chưa biết bằng cách dùng máy tính rút trích tự
động tri thức từ nhiều nguồn văn bản khác nhau”[18]. Các bài toán chính của khai thác văn
bản là phân loại, gom cụm văn bản, rút trích thông tin và tóm tắt tài liệu. Mặc dù đã có nhiều
tiến bộ trong nghiên cứu khai thác văn bản nhưng vẫn còn khoảng cách khá xa giữa nhu cầu
ứng dụng và các kết quả đạt được. Luận án tập trung nghiên cứu, phát triển các kỹ thuật khai
thác dữ liệu hiện có, cũng như những kỹ thuật phân tích dữ liệu văn bản nhằm tích hợp chúng
và tăng cường hiệu quả giải quyết bài toán khai thác dữ liệu văn bản.
1.2 Mục tiêu và đóng góp của luận án
Mô hình không gian vectơ [29] là một phương pháp biểu diễn văn bản phổ biến. 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. Tuy nhiên, phương pháp này không lưu trữ đượ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, vị trí xuất hiện của từ trong văn
bản. Những năm gần đây, mô hình biểu diễn văn bản bằng đồ thị (trong luận án này gọi tắt là
mô hình đồ thị) được đề xuất và sử dụng riêng lẻ trong các bài toán khác nhau của khai thác

xếp hạng đỉnh.
7. Tiến hành thử nghiệm khai thác văn bản tiếng Việt dựa trên tiếp cận đồ thị theo mô
hình đề xuất.
2. Mô hình biểu diễn văn bản bằng đồ thị
2.1 Giới thiệu
Mô hình đồ thị biểu diễn văn bản, cụ thể là mô hình đồ thị khái niệm, được John F. Sowa
trình bày vào năm 1976 [33]. Hiện nay, mô hình đồ thị không ngừng phát triển và ứ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ú. Luận án
trình bày những đặc tính khái quát của mô hình đồ thị biểu diễn văn bản.
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à 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. 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. Mô hình đồ thị đơn giản
2.2 Phân loại các mô hình đồ thị [CT4]
Luận án đã hệ thống các mô hình đồ thị chính và phân loại dựa trên loại đỉnh mà đồ thị sử
dụng thành các nhóm: nhóm mô hình sử dụng đỉnh là từ, nhóm sử dụng đỉnh là câu, nhóm sử

3
dụng đỉnh là các thành phần khác nhau trong văn bản. Bảng 2.1 so sánh những đặc trưng
chính và lĩnh vực ứng dụng cơ bản của các mô hình đồ thị.
 Nhóm mô hình đồ thị sử dụng đỉnh là từ trong văn bản (gồm các đồ thị ký hiệu từ số 1
→ 10 trong Bảng 2.1).
 Mô hình đồ thị sử dụng mạng ngữ nghĩa (mô hình số 1, 2, 3). Ưu điểm của nhóm
mô hình này là mô hình hoá văn bản một cách trực quan, logic, thể hiện được quan
hệ ngữ nghĩa giữa các khái niệm và cho kết quả truy vấn thông tin chính xác hơn.
 Mô hình đồ thị không sử dụng mạng ngữ nghĩa (mô hình số 4 → 10). Nhóm mô

Nhãn
1
Đồ thị khái
niệm _ CGs
Từ
2
Không
Liên kết khái
niệm
Có
Không
Truy vấn
thông tin,
thiết kế
CSDL
2
Đồ thị CGs cải
tiến vô hướng
Từ
1
Không
Liên kết khái
niệm
Không
Không
Tìm kiếm
thông tin
trên Web
3
Đồ thị khái

5
Đồ thị tần số
vô hướng
Từ
1
Có (tần
suất
xuất
hiện)
Liên kết từ
xuất hiện
chung trong
cấu trúc
Không
Có (tần suất
xuất hiện
chung)
Tìm kiếm
thông tin
trên Web

4
Mô
hình
Tên riêng của
mô hình
Đỉnh
Cạnh
Lĩnh vực
ứng dụng

trước từ b có
ít hơn n từ
Có
Không
Phân lớp
văn bản
8
Đồ thị khoảng
cách n
Từ
1
Không
Giữa từ a
trước từ b có
ít hơn n từ
Có
Có (số từ giữa a
và b + 1)
Phân lớp
văn bản
9
Đồ thị dạng
chuẩn
Từ
1
Có
(tên từ)
Từ a xuất hiện
ngay trước từ
b

(trọng
số đỉnh)
Liên kết hai
câu có từ
chung
Có/
Không
Có (Độ tương
tự giữa 2 câu)
Tóm tắt văn
bản
12
Đồ thị lưỡng
phần
Câu, từ
2
Không
Từ xuất hiện
trong câu
Không
Có (tần suất
xuất hiện của từ
trong câu)
Rút trích
thông tin,
gom cụm
3. Phân loại văn bản dựa trên tiếp cận đồ thị
Phân loại văn bản là quá trình gán văn bản vào một hoặc nhiều chủ đề đã xác định trước.
Rất nhiều phương pháp phân loại như Naïve Bayes, cây quyết định, k-láng giềng gần nhất (k-
NN), mạng nơron, máy vectơ hỗ trợ (SVM) đã áp dụng vào bài toán loại văn bản [32]. Trong

nhãn “nhan đề”, “liên kết”, hay “nội dung” như trên văn bản web nên luận án sử dụng mô
hình đồ thị đơn giản để biểu diễn văn bản. Trong mô hình này, mỗi văn bản là một đồ thị.
Đỉnh biểu diễn “thuật ngữ” trong văn bản. Các đỉnh được gán nhãn duy nhất là tên của “thuật
ngữ”. Sau bước tiền xử lý văn bản, nếu thuật ngữ a đứng ngay trước thuật ngữ b thì sẽ tồn tại
cạnh có hướng 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).
3.1.3 Rút trích đặc trưng đồ thị
Mục đích của quá trình này là xác định các đặc trưng (đồ thị con) liên quan đến việc phân
loại để giảm độ phức tạp tính toán và cũng là nội dung chính của bài toán khai thác đồ thị con
phổ biến - một bài toán quan trọng trong lĩnh vực khai thác đồ thị. Đồ thị con phổ biến là đồ
thị có tần suất xuất hiện trong tập đồ thị nhiều hơn một ngưỡng cho trước. Chỉ có những đồ
thị con xuất hiện ít nhất minSup% trong các đồ thị mới được dùng để xác định đặc trưng.
Trong các phương pháp tìm đồ thị con phổ biến trên tập dữ liệu đồ thị, gSpan là thuật toán
nhanh, cho kết quả ổn định [35]. Bên cạnh đó, trong khi phần lớn các thuật toán tìm đồ thị con
phổ biến khác khó có thể cải tiến cho tập đồ thị có hướng thì gSpan có thể cải tiến để áp dụng
cho tập đồ thị có hướng. Chính vì vậy luận án lựa chọn gSpan và thực hiện một số cải tiến để
có thể áp dụng gSpan lên tập đồ thị có hướng.
Tiền xử lý văn
bản
Tập văn
bản
huấn
luyện
Tổng hợp tập
đặc trưng - đồ
thị con phổ biến
Mô hình hóa
văn bản thành

đồ thị
Văn bản
mới
Tập vectơ đại diện lớp
R
1
=(1,0,1,…1)
R
2
=(1,1,0,…0)
…
R
m
=(0,0,1,…1)
Bộ phân loại

6
Thuật toán gSpan (graph-based Substructure pattern) [36] là thuật toán khai thác đồ thị
con phổ biến theo chiều sâu. Thuật toán ánh xạ mỗi mẫu vào nhãn chính tắc duy nhất và gán
mỗi đồ thị một mã DFS (Depth-first search) tối tiểu. Mã DFS là thứ tự duyệt các cạnh của đồ
thị theo chiều sâu hay là chuỗi các cạnh DFS. Dựa trên các nhãn này, quan hệ thứ tự đầy đủ
giữa các mẫu được tạo lập. Thứ tự từ điển này cũng được dùng trong việc thiết lập cây tìm
kiếm phân cấp (gọi là cây DFS). Trong quá trình duyệt cây theo chiều sâu, thuật toán gSpan
chỉ mở rộng ứng viên trên các đỉnh hay nhánh nằm bên phải nhất của cây DFS.
Cải tiến gSpan cho đồ thị có hướng
Do đồ thị biểu diễn văn bản là đồ thị có hướng, luận án thực hiện một số cải tiến để có thể
áp dụng gSpan lên tập đồ thị có hướng. Đầu tiên, luận án thêm giá trị hướng vào trong mã

(i,j)
=  nếu ngược lại. Chẳng hạn ta
có đồ thị s có hướng như trong Hình 3.4, khi đó
một mã DFS cho đồ thị này được mô tả bên cạnh.
Hình 3.4. Ví dụ mã DFS cho đồ thị có
hướng s
Khi thêm giá trị hướng vào trong mã DFS, ngoài thứ tự từ điển
L

giữa các nhãn đỉnh,
luận án bổ sung thứ tự từ điển
D

cho mã DFS để có thể xác định thứ tự giữa các mã DFS và
từ đó tìm mã DFS tối tiểu. Luận án định nghĩa thứ tự từ điển
D

giữa các hướng cạnh d
(i j)

như sau: d
(i j)
=  có thứ tự tự điển nhỏ hơn d
(i j)
= . Dưới đây là định nghĩa mới của thứ tự
từ điển trên mã DFS.
Định nghĩa 3.1. Thứ tự từ điển trên mã DFS
Nếu α = (a
0
, a

jijit
dlljib 
là cạnh DFS thứ t trong mã DFS α và β tương ứng. Khi đó


khi
và chỉ khi một trong những điều kiện sau là chính xác.
(i)  t, 0  t  min(m, n), sao cho a
k
= b
k
với k < t và a
t

e

b
t

(a
t

e

b
t
khi một trong những điều kiện dưới đây xảy ra:
1)
ftbt
Eb Ea

iiftft
lliiEbEa  và , ,
,,

v
3

E
v
4

v
2

v
1

v
0

A
B
C
D
Mã DFS:
(0, 1, A, B, )
(1, 2, B, D, )
(2, 3, D, E, )
(2, 4, D, C, )


thị con phổ biến, S là kích thước tập dữ liệu và r là số mã trùng lắp tối đa của một đồ thị con
phổ biến được phát triển từ mã tối tiểu.
Với tiếp cận biểu diễn văn bản thành đồ thị mà mỗi đỉnh được gán nhãn duy nhất và cạnh
có hướng thì độ phức tạp của bài toán xác đỉnh đẳng cấu đồ thị con giảm xuống còn O(n
2
) (n -
số cạnh của đồ thị). Từ tập các đồ thị con phổ biến thu được từ tất cả các lớp, xây dựng tập
các đặc trưng – tập đồ thị con phổ biến. Đây là đầu vào cho bước xây dựng vectơ đại diện lớp
tiếp theo.
3.1.4 Xây dựng vectơ đại diện lớp
Với mục tiêu thực hiện giai đoạn phân loại thuận tiện, các vectơ nhị phân đại diện cho
từng lớp được xây dựng. Mỗi lớp cho trước được biểu diễn thành một vectơ đặc trưng có số
chiều bằng kích thước tập đồ thị con phổ biến. Đặc trưng nhận giá trị 1 nếu đồ thị con phổ
biến tương ứng xuất hiện trong tập đồ thị con phổ biến của lớp và ngược lại sẽ nhận giá trị 0.
Để tiện cho việc trình bày các công thức, luận án sử dụng các ký hiệu sau.
Tập văn bản huấn luyện ký hiệu là D = {d
1
, d
2
, …, d
n
} có gán nhãn lớp và tập các lớp C =
{ C
1
, C
2
, …, C
m
}. Tập đồ thị G = {G
1

=1 nếu đặc trưng f
j
 F là một trong các đồ thị con phổ biến tìm được từ tập đồ thị biểu
diễn văn bản thuộc lớp C
i
và ngược lại.
3.1.5 Bộ phân loại
Lớp của văn bản mới X được xác định như sau. Đầu tiên, luận án sử dụng tập các “thuật
ngữ” đã lựa chọn trong quá trình huấn luyện để xây dựng đồ thị g biểu diễn cho X. Sau đó xây
dựng vectơ nhị phân v
0
có số chiều tương ứng với k đặc trưng của tập F. Giá trị của từng
thành phần trong vectơ v
0
thể hiện sự tồn tại hay không của các đặc trưng f
i
 F trong đồ thị g.

8
Tiếp theo, luận án tính toán sự tương tự giữa vectơ v
0
với tất cả m vectơ đại diện cho các lớp.
Luận án sử dụng độ đo Dice – độ đo sử dụng phổ biến, hiệu quả trong việc xác định độ tương
tự giữa các vectơ nhị phân. Độ đo Manhattan được cài đặt để so sánh kết quả phân loại với độ
đo Dice. Cuối cùng, dựa trên các độ tương tự Dice ta gán văn bản mới vào lớp cho giá trị Dice
lớn nhất. Còn nếu sử dụng độ đo Manhattan thì lớp có giá trị Manhattan nhỏ nhất được chọn
làm lớp cho văn bản mới.
3.2 Kết quả thử nghiệm
3.2.1 Thử nghiệm trên tập dữ liệu email tiếng Anh
Tập dữ liệu Enron gồm 619.446 email của 158 người và trung bình mỗi người dùng có

Biểu đồ trong hình 3.7 cho thấy kết quả phân loại theo thư mục của eClass nhỉnh hơn
phương pháp so khớp theo thứ hạng của eMailSift. Đó là do thay vì chỉ xác định sự trùng
khớp với đồ thị con đại diện có thứ hạng cao nhất (trong eMailSift) thì eClass tính độ phủ của
thư mục theo độ đo Dice so với email mới nên khắc phục được nhược điểm khó xác định
chính xác thư mục đích khi email mới trùng khớp với nhiều đồ thị con đại diện của các thư
mục. Như vậy với việc cải tiến eMailsft bằng độ đo tương tự Dice (trong eClass), chất lượng
phân loại đã tăng lên.
Trong Hình 3.8 là biểu đồ so sánh kết quả phân loại theo thư mục giữa eClass và eTCG.
Hệ thống eTCG cho kết quả phân loại tốt hơn eClass ở phần lớn các loại kích thước thư mục,

9
đặc biệt khi kích thước thư mục tăng lên. Điều này chứng tỏ mô hình biểu diễn đồ thị đơn
giản phù hợp cho việc biểu diễn văn bản trong bài toán phân loại văn bản.
Hình 3.7. Kết quả phân loại theo thư mục của
eClass và eMailSift [CT10]
Hình 3.8. Kết quả phân loại theo thư mục của
eTCG và eClass

So sánh độ chính xác phân loại theo người dùng với Naïve Bayes
Phương pháp phân loại Naïve Bayes dự đoán thư mục cho email mới dựa trên biểu diễn
vectơ. Kết quả trên biểu đồ hình 3.9 cho thấy độ chính xác phân loại khá khác biệt tùy theo
người dùng trong cả ba hệ thống. Dựa trên kết quả phân loại, chúng ta thấy eClass và eTCG
phân loại tương đối tốt với người dùng có nhiều thư mục và nội dung thư mục không đồng
nhất, cũng như khá tốt đối với các thư mục thưa.
Nói chung, eTCG cho kết
quả phân loại tốt hơn cả. Điều
này càng chứng minh phương
pháp biểu diễn bằng đồ thị đơn
giản cho kết quả phân loại tốt
hơn biểu diễn theo đồ thị hình

So sánh eClass với eMailSift
eMailSift
eClass
0 20 40 60 80 100
Độ chính xác
Người dùng
Naive Bayes
eClass
eTCG

10
chính xác phân lớp văn bản tiếng Việt phụ thuộc vào bộ dữ liệu, công cụ tách từ và có thể đạt
từ 48% cho đến 98% tùy theo phương pháp và bộ dữ liệu thử nghiệm.
Luận án xây dựng bộ dữ liệu thử nghiệm gồm các bài báo lấy từ các tờ báo điện tử lớn.
Tập dữ liệu thử nghiệm (gọi là TC1) bao gồm 3900 tập tin văn bản được chia thành 7 chủ đề.
Khi áp dụng qui trình phân loại đã đề xuất lên tiếng Việt, luận án chọn lựa đơn vị „tiếng”
biểu diễn đỉnh trong đồ thị. Sau khi tiền xử lý, đồ thị có kích thước trung bình 45 đỉnh/đồ thị.
Luận án thử nghiệm bằng phương pháp đánh giá chéo.
Bảng 3.4. Kết quả thử nghiệm phân loại [CT3]
Tên chủ đề
Độ đo tương tự Dice
Độ đo tương tự Manhattan
Độ phủ
Độ chính xác
F
1

Độ phủ
Độ chính xác
F

Văn hóa
0.798
0.941
0.864
0.8
0.909
0.851
Vi tính
0.717
0.865
0.784
0.615
0.767
0.683
Xã hội
0.792
0.933
0.857
0.65
0.915
0.76
Trung bình
0.805
0.87
0.83
0.716
0.791
0.746
Kết quả thử nghiệm tương ứng với độ đo Dice và độ đo Manhattan được trình bày trong
Bảng 3.4. Bộ phân lớp dùng độ đo tương tự Dice cho kết quả tốt hơn bộ phân lớp dùng độ đo

TCG
Mô hình đồ thị đơn
giản
Độ đo tương tự Dice, đỉnh đồ thị
tạo từ đơn vị “tiếng”
0.831
[0.8192,
0.8428]
Bảng 3.5 trình bày kết quả phân loại tốt nhất của các hệ thống cài đặt theo phương pháp:
k-NN trên biểu diễn vectơ (VSM), phương pháp lai của tác giả [23] với thuật toán k-NN và độ
đo tương tự Manhattan (Hybrid) và hệ thống dựa trên qui trình phân loại mà luận án đề xuất
(TCG) theo độ đo F
1
. Thời gian huấn luyện trung bình của TCG là 4.8 x 10
-3
giây/ văn bản và
thời gian thực hiện phân lớp trung bình là 2.55 x 10
-3
giây/văn bản (trên Intel Core Duo
2.56Ghz, 2GB RAM). Thời gian huấn luyện của TCG là nhỏ nhất mặc dù tốn thời gian vào
quá trình xây dựng đồ thị biểu diễn văn bản nhiều hơn VSM, nhưng tập đặc trưng rút ra từ đồ
thị có kích thước nhỏ hơn rất nhiều so với tập đặc trưng của mô hình vectơ VSM (931 đặc
trưng của TCG so với 20608 đăc trưng của VSM). Nhờ các cải tiến của gSpan cũng như đặc
điểm của đồ thị biểu diễn văn bản mà thời gian rút trích đặc trưng từ đồ thị rất nhỏ. Vì vậy

11
thời gian của các bước xác định đặc trưng, cũng như xây dựng vectơ biểu diễn văn bản của
VSM lớn hơn nhiều so với thời gian thực hiện công việc tương ứng của TCG.

Hình 3.11 là đồ thị so

Hình 4.1. Qui trình gom cụm văn bản động [CT2]
Luận án đã thực hiện việc cải tiến Incremental DBSCAN để hạn chế nhược điểm trộn cụm
của thuật toán. Luận án đề xuất kỹ thuật chọn lựa động đặc trưng nhằm nâng cao kết quả gom
cụm.
4.1 Gom cụm tập văn bản có biến động dựa trên biểu diễn đồ thị
Hình 4.1 là sơ đồ qui trình gom cụm văn bản động. Đầu tiên, ta thực hiện tiền xử lý tập
văn bản. Sau đó, mô hình của dữ liệu được xây dựng sử dụng biểu diễn đồ thị đơn giản. Khi
xây dựng đồ thị động chúng ta có thể rút trích các đặc trưng đồ thị ở dạng các cụm từ chung.
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Khoa học
Kinh doanh
Sức khoẻ
Thể thao
Văn hóa
Vi tính
Xã hội
Độ đo F1
VSM
Hybrid
TCG
12
Tiếp theo, độ tương tự giữa các văn bản được tính dựa trên các cụm từ chung và vectơ văn
bản đã tinh chỉnh. Cuối cùng, hệ thống gom cụm văn bản và tạo các cụm chỉ gồm những văn
bản liên quan đến cùng chủ đề. Luận án sử dụng thuật toán Incremental DBSCAN cải tiến để
gom cụm động văn bản dựa trên độ tương tự giữa các cặp văn bản.
4.1.1 Rút trích đặc trưng đồ thị
Luận án sử dụng cùng mô hình đồ thị đơn giản biểu diễn văn bản như trong bài toán phân
loại văn bản và dựa trên các kết quả nghiên cứu [30], [31]. Khi xử lý việc văn bản cập nhật
động, luận án sử dụng thuật toán xây dựng đồ thị DIG [17] để đánh chỉ mục văn bản trong khi
vẫn giữ nguyên được cấu trúc của văn bản gốc. Đồ thị biểu diễn văn bản được xây dựng động,
xử lý từng văn bản tại mỗi thời điểm. Khi xác định sự tương tự giữa các văn bản, chúng ta cần
rút trích đặc trưng từ đồ thị biểu diễn văn bản. Thuật toán DIG có thể xác định động các đồ thị
con đại diện hay các cụm từ chung từ các văn bản trước đó trong khi xây dựng đồ thị. Các
cụm từ chung này là những đặc trưng quan trọng được rút trích từ đồ thị biểu diễn văn bản và
có thể tính toán độ tương tự giữa các văn bản.
4.1.2 Xác định độ tương tự giữa các văn bản
Dựa trên khảo sát về việc sử dụng kết hợp cụm từ và từ đơn có thể tăng kết quả gom cụm,
luận án sử dụng độ đo lai là sự kết hợp hai độ đo tương tự: độ tương tự dựa trên cụm từ chung
(sim
sp
) và độ đo cosine giữa vectơ văn bản (sim
df

(d
1
, d
2
): độ tương tự dựa trên cụm từ chung giữa văn bản d
1
và
d
2
.
Định nghĩa 4.2: Độ đo tương tự dựa trên cụm từ chung giữa hai văn bản
Độ đo tương tự sim
sp
(d
1
, d
2
) dựa trên cụm từ chung giữa hai văn bản d
1
và d
2
được tính
như sau [CT5]:






k

cụm từ chung thứ i trong văn bản d
1
và d
2
, l
i
: chiều dài của cụm từ chung i, |s
ij
|: chiều dài của
câu thứ j trong văn bản d
i
, avg (s
i
): chiều dài trung bình của các câu chứa cụm từ chung i.
Độ tương tự dựa trên từ riêng biệt chính là độ tương tự giữa hai vectơ đặc trưng của hai
văn bản. Độ đo Cosine dùng để tính toán độ tương tự giữa các vectơ đặc trưng. 1
λ=0.2 qua thực nghiệm cho kết quả gom nhóm tốt nhất.

13
Do phương pháp trọng số TF×IDF không phù hợp với thuật toán gom cụm động (theo
[34]) cho nên luận án sử dụng hàm TF×IG (Term Frequency – Information Gain) nhằm xác
định chất lượng của từ không chỉ trong văn bản mà còn trong tất cả các cụm và dùng trong
quá trình lựa chọn đặc trưng động. Trọng số của vectơ văn bản được tính như sau [CT5]:
ijij
tf
MinIG
jIG






m
i
ii
m
i
ii
m
i
ii
tcptcptp
tcptcptpcpcptIG

(4.4)
Trong đó, p(c
i
): xác suất một văn bản thuộc về nhóm c
i
, p(t): xác suất một văn bản chứa
từ t, p(c
i
| t) xác suất một văn bản thuộc nhóm c
i
trong điều kiện có chứa t,
)(tp
: xác suất một

4.1.4 Thuật toán gom cụm động Incremental DBSCAN cải tiến
Thuật toán Incremental DBSCAN [15], thuật toán xử lý các đối tượng dữ liệu tuần tự, gán
động các đối tượng dữ liệu vào các cụm tương ứng trong khi xử lý. Thuật toán này ít chịu ảnh
hưởng bởi các đối tượng nhiễu (hay cá biệt), trong khi nhiễu là đặc điểm phổ biến của văn bản.
Ngoài ra, chất lượng gom cụm không phụ thuộc vào thứ tự thêm vào các đối tượng. Tuy
nhiên, thuật toán có khuynh hướng gộp các cụm ít kết nối với nhau thành một cụm lớn. Luận
án cải tiến kỹ thuật trộn cụm của thuật toán Incremental DBSCAN bằng cách kiểm tra mật độ
của các cụm này trước khi gộp lại.
Định nghĩa 4.3: Tập đối tượng bị ảnh hưởng khi chèn thêm đối tượng
Gọi D là một tập các đối tượng và p là một đối tượng được chèn thêm. Tập đối tượng bị
ảnh hưởng khi chèn p vào (ký hiệu là UpdSeed
Ins
) được định nghĩa như sau [15]:
UpdSeed
Ins
= {q | q là đối tượng nòng cốt trong D
∪
{p},
∃
q’: q’ là đối tượng nòng cốt trong
D
∪
{p} nhưng không phải trong D và q
∈
N
Eps
(q’)}
Cải tiến Incremental DBSCAN:
Thuật toán Incremental DBSCAN có khuynh hướng gộp các cụm ít kết nối với nhau thành
một cụm lớn. Theo kỹ thuật trộn cụm của thuật toán, khi thêm mới một đối tượng p, nếu tập

1. for mọi cụm C
i
 Clusters do

15
2. if DocumentInClusters[C
i
] < M
3. Loại các đối tượng nòng cốt của C
i
ra khỏi UpdSeed
ins

4. end if
5. end for
6. if UpdSeed
in s
 > 0
7. Trộn đối tượng p và các cụm có đối tượng nòng cốt thuộc UpdSeed
ins
thành một
cụm duy nhất
7. else
8. p là phần tử lạc loài
9. end if
Hình 4.6. Mã giả cho kỹ thuật trộn cụm của Incremental DBSCAN cải tiến
4.2 Kết quả thử nghiệm
Tập dữ liệu thử nghiệm (gọi là TC2) gồm 6700 văn bản với 10 chủ đề: âm nhạc, chứng
khoán, điện ảnh, quần vợt, vi tính, thời trang, du lịch, ẩm thực, hình sự và du học. Từ tập dữ
liệu thử nghiệm này, 6 bộ dữ liệu khác nhau được xây dựng với số lớp từ 3 đến 10 để quan sát

0.986
[0.9789,0.9931]
0.997
[0.9937, 1.0]
DS32
0.847
[0.8342,0.8598]
0.858
[0.8456,0.8704]
0.995
[0.9925,0.9975]
DS51
0.815
[0.8031,0.8269]
0.834
[0.8226,0.8454]
0.969
[0.9637, 0.9743]
DS71
0.791
[0.7801,0.8019]
0.812
[0.8225,0.8015]
0.966
[0.9611,0.9709]
DS91
0.775
[0.7647,0.7853]
0.809
[0.8187,0.7993]

Khoảng tin cậy
95%
DS31
0.089
[0.0671,0.1109]
0.088
[0.0662,0.1098]
0.035
[0.0210,0.0490]
DS32
0.058
[0.0474,0.0686]
0.052
[0.0419,0.0621]
0.047
[0.0374,0.0566]
DS51
0.396
[0.3738,0.4182]
0.336
[0.3151,0.3569]
0.141
[0.1256,0.1555]
DS71
0.485
[0.4565,0.5135]
0.454
[0.4262,0.4818]
0.214
[0.1940,0.2340]

Hình 4.9. So sánh kết quả gom cụm khi sử dụng và
không sử dụng kỹ thuật chọn lựa động đặc trưng
Luận án cài đặt thuật toán SHC [16] – thuật toán gom cụm văn bản động dựa trên độ đo sự
kết dính cụm bằng biểu đồ tương tự và so sánh với hệ thống ICG.
Thuật toán SHC được các các tác
giả [17] đánh giá tốt hơn thuật toán gom
cụm động khác như gom cụm động
phân cấp HAC, Single-Pass, hoặc gom
cụm k-NN. Luận án sử dụng chung mô
hình đồ thị và độ đo lai giữa các văn
bản cho cả thuật toán SHC và hệ thống
ICG (dùng Incremental DBSCAN).

Bảng 4.5. Sự cải thiện chất lượng gom cụm của
ICG [CT2]
Tập
DL
SHC
ICG
Độ đo F
Entropy
Độ đo F
Entropy
DS31
0.956
0.019
0.997
0.035
DS32
0.958

DS32
DS51
DS71
DS91
DS10
F-Measure
Tập dữ liệu
ICG-noFS
ICG

17

Bảng 4.4 so sánh độ đo F
cũng như độ đo Entropy giữa hệ
thống ICG và SHC trên các tập
dữ liệu. Chất lượng gom cụm
theo độ đo F tăng trung bình 9%.

Bảng 4.6. So sánh số lượng cụm thu được giữa ICG và
SHC [CT2]
Phương pháp
gom cụm
Mã tập DL
DS31
DS32
DS51
DS71
DS91
DS10
SHC

Hình 4.10. Đánh giá thuật toán Incremental DBSCAN
cải tiến theo độ đo F [CT7]
Do văn bản có đặc điểm mang tính nhập nhằng về nội dung nên Incremental DBSCAN cải
tiến đã giải quyết tốt hơn cho trường hợp trộn cụm và phù hợp cho việc gom cụm động văn
bản.
Để nghiên cứu ảnh hưởng của việc cập nhật động kết quả gom cụm, luận án chèn thêm
2500 văn bản vào đồ thị hiện tại của tập dữ liệu DS10 và quan sát sự thay đổi chất lượng gom
cụm. Quá trình chèn thêm văn bản mới vào tập dữ liệu DS10 được thực hiện 3 lần với thứ tự
chèn văn bản khác nhau. Bảng 4.6 cho thấy sự thay đổi của chất lượng gom cụm (lấy trung
bình qua 3 lần thực nghiệm) với mỗi 500 văn bản mới thêm vào.
So với kết quả gom cụm hiện hữu, từ
bảng 4.6 này chúng ta thấy độ đo F giảm từ
0.950 xuống còn 0.901. Chất lượng gom
cụm chỉ giảm khoảng 5% theo độ đo F,
trong khi chèn thêm số lượng văn bản gần
bằng 40% số văn bản hiện có.

Bảng 4.7. Kết quả cập nhật dữ liệu động [CT2]
Số văn bản
Độ đo F
Khoảng tin cậy 95%
7200
0.943
[0.9399, 0.9461]
7700
0.935
[0.9318, 0.9382]
8200
0.922
[0.9254, 0.9186]

bản tiếng Việt nào phát triển theo hướng này. Luận án kết hợp mô hình đồ thị vô hướng có
gán nhãn với đỉnh là câu và kỹ thuật xếp hạng đỉnh nhằm xác định các câu quan trọng của văn
bản. Hướng tiếp cận này không đòi hỏi phải có sẵn những bản tóm tắt chuẩn do con người
thực hiện để học hay huấn luyện và ít phụ thuộc vào bộ dữ liệu thử nghiệm cũng như lĩnh vực.
Tiếp cận này cũng giải quyết vấn đề trùng lắp thông tin trong bản tóm tắt và có khả năng thực
hiện tóm tắt trên văn bản đơn cũng như trên tập văn bản.
5.1 Mô hình tóm tắt văn bản tiếng Việt dựa trên biểu diễn đồ thị và kỹ thuật
xếp hạng
Hình 5.1 là sơ đồ mô hình tóm tắt văn bản dùng cho từng văn bản (gọi là văn bản đơn) lẫn
tập văn bản.
Độ quan trọng của câu xác định
bằng thuật toán xếp hạng đỉnh trên
đồ thị. Sau khi sắp xếp các câu theo
độ quan trọng, để hạn chế sự trùng
lắp thông tin, một phiên bản của độ
đo MMR[10] được dùng để lọc lại
câu có độ quan trọng cao khi đưa
vào bản tóm tắt. Khi tóm tắt tập văn
bản, các bản tóm tắt của từng văn
bản sẽ tổng hợp lại thành một văn
bản mới. Qui trình tóm tắt trong bộ
lõi tóm tắt được áp dụng tiếp lên
văn bản mới này và tạo ra bản tóm
tắt hoàn chỉnh cho tập văn bản.
Hình 5.1. Mô hình tóm tắt văn bản tiếng Việt [CT1]
Trước khi chuyển đổi văn bản thành đồ thị, ta cần thực hiện bước tiền xử lý. Trong mô
hình tóm tắt văn bản dựa trên đồ thị thì tách câu đóng vai trò chính yếu vì câu là yếu tố cơ bản
cấu thành đồ thị. Việc tách câu được thực hiện bằng phương pháp thống kê sử dụng
Maximum Entropy. Luận án áp dụng luật loại bỏ câu có độ dài thấp hơn một ngưỡng cho
trước nhằm giảm không gian lưu trữ và tăng tốc độ xử lý.

i
và S
j

trong văn bản như sau.
Định nghĩa 5.1: Độ đo tương tự giữa hai câu
Cho hai câu S
i
và S
j
, độ đo tương tự giữa hai câu được định nghĩa như sau [CT8]:
)(log)(log
),(
22 ji
SSW
k
jiij
SS
a
SSSimw
jik





(5.1)
Với W
k
là từ chung giữa hai câu S






)(
)(
)(
)1(
)(
ik
ij
VOutV
ki
j
W
VInV
jii
W
w
VPR
wd
N
d
VPR

(5.3)
Trong đó: PR
W
là trọng số của đỉnh, In(V

i
.
4. while độ chênh lệch của PR
W
(V
i
) ≥ 0.0001 do // độ chênh lệch giữa hai vòng
lặp liên tiếp
5. Tính giá trị độ quan trọng PR
W
(V
i
) // bằng công thức (5.3)
6. end while
7. end for
8. Sắp xếp các giá trị PR
W
theo thứ tự
Hình 5.4. Thuật toán xếp hạng câu
5.1.3 Tạo bản tóm tắt
Sau bước xếp hạng câu, mỗi câu S
i
có độ quan trọng PR
W
(S
i
) tương ứng. Dựa trên công
thức MMR[10], luận án sử dụng phiên bản của MMR để tái xếp hạng và chọn lựa câu đưa
vào bản tóm tắt. Phiên bản công thức MMR trong (5.4) có thể giúp xác định các câu có độ
quan trọng cao và ít thông tin trùng lắp.

của câu với các câu đã được chọn trước. Giá trị λ tốt nhất theo thực nghiệm là 0.6.
5.2 Kết quả thử nghiệm
Luận án xây dựng bộ dữ liệu thử nghiệm gồm các bài báo lấy từ những tờ báo điện tử lớn
và từ tạp chí Bưu chính viễn thông, tạp chí Phát triển Khoa học & Công nghệ - ĐHQG
Tp.HCM. Bộ dữ liệu thử nghiệm T1 (200 tập tin) dành cho việc đánh giá kết quả tóm tắt trên
văn bản đơn. Bộ dữ liệu T2 (207 tập tin) bao gồm các tập tin tức liên quan đến 6 chủ đề dành
cho việc đánh giá chất lượng tóm tắt tập văn bản. Với mỗi văn bản, hoặc tập văn bản, các
chuyên gia tạo ra bản tóm tắt gồm các câu quan trọng và đây là bản tóm tắt chuẩn dùng để
đánh giá. Luận án đánh giá bản tóm tắt dạng trích lược của hệ thống với bản tóm tắt chuẩn
theo phương pháp ROUGE[20] - phương pháp đánh giá dựa trên số lượng n-gram trùng nhau.

21
5.2.1 Kết quả tóm tắt văn bản đơn
Luận án chọn phương pháp cơ sở là phương pháp dựa vào câu tiêu đề (heading) [13].
Trong phương pháp cơ sở, bản tóm tắt dạng trích lược được xây dựng từ các câu đầu đoạn.
Ngoài ra, chương trình Auto
Summarize của MSWord cũng
được dùng để tạo ra bản trích lược
thứ ba. Trong Bảng 5.4 là thống kê
kết quả đánh giá chất lượng tóm tắt
văn bản của phương pháp cơ sở, kết
quả chương trình Auto Summarise
và mô hình đề xuất của luận án (ký
hiệu là TSGVi) theo từng chủ đề.

Bảng 5.4. Kết quả đánh giá bản tóm tắt văn bản đơn
[CT8]
Độ rút gọn =
20%
Chủ đề

0.3754
Thể thao
0.6481
0.3637
Luận án thử nghiệm quá trình tóm tắt văn bản dùng độ rút gọn = 20% với ngưỡng tạo cạnh
giữa hai đỉnh là α = 0.05 và tham số ưu tiên cho từ thuộc tiêu đề β= 1.5. Trên bộ dữ liệu thử
nghiệm này, mô hình TSGVi cho kết quả tốt hơn phương pháp cơ sở và AutoSummarise của
MsWord.
5.2.2 Kết quả tóm tắt tập văn bản
Luận án so sánh mô hình TSGVi đề xuất với hai hệ thống tóm tắt: TextRank [26],
LexRank [14] và phương pháp cơ sở LEAD (phương pháp lấy các câu đầu tiên tuần tự từ văn
bản thứ nhất đến văn bản cuối cùng đưa vào bản tóm tắt). Với mỗi tập văn bản, các hệ thống
sẽ tạo ra bản tóm tắt gồm 100 từ (giống bản tóm tắt chuẩn do chuyên gia tạo ra). Bảng 5.5 cho
biết giá trị của độ đo ROUGE trên toàn bộ tập văn bản T2 theo từng hệ thống và cho thấy
TSGVi có kết quả đánh giá tốt hơn TextRank, LexRank và LEAD trên tập dữ liệu này.
Bảng 5.5. So sánh các hệ thống tóm tắt trên tập T2 [CT1]
STT
Hệ thống
ROUGE-1
Khoảng tin cậy 95%
ROUGE-2
Khoảng tin cậy 95%
1
LEAD
0.5917
[0.5541,0.6393]
0.2036
[0.1728,0.2356]
2
LexRank

ROUGE-1
ROUGE-2
1
Kinh tế

LEAD
0.54
0.149
LexRank
0.535
0.167
TextRank
0.561
0.195
TSGVi
0.601
0.234
2
Xã hội

LEAD
0.61
0.231
LexRank
0.596
0.221
TexRank
0.691
0.321
TSGVi

4
Sức
khỏe
LEAD
0.62
0.219
LexRank
0.631
0.233
TextRank
0.679
0.224
TSGVi
0.705
0.272
5
Thời tiết

LEAD
0.685
0.322
LexRank
0.63
0.254
TextRank
0.631
0.292
TSGVi
0.593
0.297

DBSCAN cải tiến. Qui trình gom cụm đề xuất dễ dàng cập nhật thông tin cụm khi
có sự thay đổi trong dữ liệu. Nhằm nâng cao chất lượng gom cụm, luận án đề xuất
kỹ thuật chọn lựa động đặc trưng dựa trên phương pháp học có giám sát.
o Luận án đề xuất mô hình tóm tắt văn bản tiếng Việt với biểu diễn đồ thị có đỉnh là
câu và kỹ thuật xếp hạng đỉnh để rút ra các câu quan trọng đưa vào bản tóm tắt. Mô
hình tóm tắt này áp dụng được cho cả văn bản đơn lẫn tập văn bản.
 Luận án đã cải tiến một số thuật toán.
o Luận án cải tiến gSpan để tìm đồ thị con phổ biến trên tập đồ thị có hướng biểu
diễn văn bản. Luận án đề xuất biểu diễn mới cho mã DFS, định nghĩa lại thứ tự từ

23
điển trên mã DFS tương ứng với biểu diễn mới và đưa ra các lưu ý khi phát triển đồ
thị con. Độ phức tạp thời gian của gSpan cải tiến tốt hơn gSpan nguyên thủy.
o Luận án cải tiến thuật toán Incremental DBSCAN, một thuật toán gom cụm động
có khả năng xử lý nhiễu, ít phụ thuộc vào thứ tự dữ liệu đưa vào nhằm áp dụng
hiệu quả lên tập văn bản. Luận án cải tiến kỹ thuật trộn cụm của thuật toán
Incremental DBSCAN nhằm hạn chế việc trộn các cụm ít tương tự lại với nhau. Độ
phức tạp thời gian của Incremental DBSCAN cải tiến giống như thuật toán nguyên
thủy nhưng làm tăng chất lượng gom cụm.
Đồng thời kết quả luận án có ý nghĩa thực tiễn sau:
 Luận án đã tiến hành thử nghiệm khai thác văn bản tiếng Việt. Lần đầu tiên tiếp cận
đồ thị biểu diễn, khai thác văn bản được áp dụng vào văn bản tiếng Việt. Tiếp cận đồ thị
không chỉ khắc phục các nhược điểm của biểu diễn vectơ mà còn làm giảm bớt sự ảnh
hưởng của công cụ tách từ (bài toán khó trên tiếng Việt) và đồng thời quan tâm đến thứ
tự xuất hiện của từ trong văn bản (một đặc điểm quan trọng của tiếng Việt).
 Các kết quả thử nghiệm cho thấy tiếp cận đồ thị là phương pháp hiệu quả và có khả
năng mở rộng với những thuật toán cải tiến để cải thiện, nâng cao chất lượng phân loại,
gom cụm và tóm tắt văn bản. Thời gian xử lý văn bản khi sử dụng tiếp cận đồ thị kết
hợp với các kỹ thuật rút trích đặc trưng phù hợp gần như tương đương với phương pháp
sử dụng mô hình biểu diễn vectơ nhưng kết quả khai thác tốt hơn.