ĐẠI HỌC QUỐC GIA TP. HCM
TRƢỜNG ĐẠI HỌC BÁCH KHOA

NGUYỄN KIM HUYỀN

RƯT TRÍCH CÁC CỤM TỪ KHĨA DỰA TRÊN VAI TRÕ
VÀ ĐẶC ĐIỂM CỦA CÁC CỤM TỪ TRONG VĂN BẢN

Chuyên ngành: Khoa Học Máy Tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 11 năm 2013


Cơng trình đƣợc hồn thành tại: Trƣờng Đại Học Bách Khoa –ĐHQG-HCM

Cán bộ hƣớng dẫn khoa học: GS.TS. Cao Hoàng Trụ ......................................................

Cán bộ chấm nhận xét 1: GS.TS. Phan Thị Tƣơi …..........................................................

Cán bộ chấm nhận xét 2: ………………………...............................................................

Luận văn thạc sĩ đƣợc bảo vệ tại: Trƣờng Đại Học Bách Khoa, ĐHQG TP. HCM
ngày ..25.. tháng ..12.. năm ..2013..
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. PGS.TS. Quản Thành Thơ..................................................................................................
2. TS. Nguyễn Hứa Phùng .....................................................................................................
3. GS.TS. Phan Thị Tƣơi .....................................................................................................
4. TS. Hồ Bảo Quốc .............................................................................................................

5. GS.TS. Cao Hoàng Trụ ..................................................................................................
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trƣởng Khoa quản lý chuyên ngành sau
khi luận văn đã đƣợc sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƢỞNG KHOA…………


ĐẠI HỌC QUỐC GIA TP.HCM
CỘNG HÕA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƢỜNG ĐẠI HỌC BÁCH KHOA
Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: NGUYỄN KIM HUYỀN ............................ MSHV: 11070455..........
Ngày, tháng, năm sinh: 16/07/1983 ........................................ Nơi sinh: Biên Hòa- ĐN
Chuyên ngành: KHOA HỌC MÁY TÍNH .............................. Mã số : 604801 ...........
I. TÊN ĐỀ TÀI: ............................................................................................................
Rút trích các cụm từ khóa dựa trên vai trò và đặc điểm của các cụm từ trong
văn bản ...........................................................................................................................
II. NHIỆM VỤ VÀ NỘI DUNG: .................................................................................
........................................................................................................................................
........................................................................................................................................
III. NGÀY GIAO NHIỆM VỤ : 02/07/2012 ................................................................
IV. NGÀY HOÀN THÀNH NHIỆM VỤ:21/06/2013 .................................................
V. CÁN BỘ HƢỚNG DẪN: GS. TS. CAO HOÀNG TRỤ ..........................................
........................................................................................................................................

Tp. HCM, ngày . . . . tháng .. . . năm 20....
CÁN BỘ HƢỚNG DẪN

(Họ tên và chữ ký)

TRƢỞNG KHOA….………
(Họ tên và chữ ký)


LỜI CẢM ƠN
Tơi xin chân thành cảm ơn gia đình tôi, những ngƣời luôn yêu thƣơng, ủng hộ và
tạo mọi điều kiện để tơi hồn thành tốt việc học tập và nghiên cứu của mình.
Xin chân thành cảm ơn thầy, GS.TS. Cao Hồng Trụ. Những lời khun bổ ích và
sự chỉ dẫn tận tình của thầy đã giúp tơi hồn thành tốt luận văn này.
Xin chân thành cảm ơn những ngƣời bạn của tơi, những ngƣời ln lắng nghe và
đóng góp ý kiến trong suốt thời gian thực hiện luận văn.
Xin chân thành biết ơn sự tận tình giảng dạy và giúp đỡ của tất cả quý thầy cô tại
trƣờng Đại học Bách khoa, đặc biệt là các thầy cô trong khoa Khoa học và Kỹ thuật
Máy tính.


LỜI CAM ĐOAN
Tôi xin cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác nhƣ
đã ghi rõ trong luận văn, các nội dung trình bày trong luận văn này là do chính tơi
thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy bằng cấp
ở một trƣờng khác.
TP.HCM, tháng 11 năm 2013
Nguyễn Kim Huyền


TĨM TẮT
Cụm từ khóa là những từ hay cụm từ có nghĩa đại diện cho nội dung tóm tắt của tài
liệu. Có hai hƣớng tiếp cận chính trong các hệ thống rút trích các cụm từ khóa:

hƣớng học máy giám sát và hƣớng học máy không giám sát. Nhƣng trong cả hai
hƣớng, đặc điểm quan hệ ngữ nghĩa giữa các cụm từ vẫn chƣa nhận đƣợc sự quan
tâm đầy đủ. Mục tiêu của đề tài là cải tiến hiệu suất của SemiRank, một phƣơng
pháp đánh giá vai trò của các cụm từ dựa trên mối quan hệ ngữ nghĩa và tập các
cụm từ khóa ban đầu. Đề tài đề xuất hai phƣơng pháp để cải tiến tập khóa ban đầu
này: phƣơng pháp cụm từ trọng tâm và phƣơng pháp đặc điểm thông tin. Từ những
cải tiến tập các cụm từ khóa ban đầu, đề tài cho thấy rằng hiệu suất của SemiRank
cải thiện rõ rệt trong trƣờng hợp đánh giá lại tập các cụm từ khóa ban đầu thơng qua
mối quan hệ ngữ nghĩa giữa chúng với nhau. Các kết quả thực nghiệm đƣợc đánh
giá trên tập Wiki-20 và so sánh với một số phƣơng pháp rút trích cụm từ khóa đã
có. Hai phƣơng pháp đề xuất đều cải tiến hiệu suất của SemiRank và cho kết quả tốt
hơn những phƣơng pháp so sánh.

SUMMARY
Keyphrases are single or multiple words summarizing the main contents of a
document. There are two main approaches for keyphrase extraction: supervised and
unsupervised learning. However, semantic relations between phrases have not been
adequately considered in both approaches. In this thesis, we proposed two methods
to improve performance of SemiRank, an approach to extract keyphrases based on
initial keyphrases and semantic relations between phrases in the document. The two
methods are: Core Phrases and Information Features methods. Our methods
outperform SemiRank with intitial keyphrases from title and two derivatives of
KEA and KEA++ on F1 measure. In addition, we show that, the new methods give
better results to SemiRank in the case that initial keyphrases are re-ranked based on
their semantic relations.

.


i


NỘI DUNG
Chƣơng 1. MỞ ĐẦU ............................................................................................. 1
1.1

Xác định bài toán........................................................................................ 1

1.2

Mục tiêu và phạm vi ................................................................................... 2

Chƣơng 2. CÁC CÔNG TRÌNH LIÊN QUAN ...................................................... 4
2.1.

Tổng quát ................................................................................................... 4

2.2.

Các đặc điểm của cụm từ khóa nói chung ................................................... 5

Chƣơng 3. CƠ SỞ LÝ THUYẾT ........................................................................ 10
3.1.

Wikipedia ...................................................................................................... 10

3.2.

Định lƣợng mối quan hệ ngữ nghĩa và phân giải nhập nhằng ................... 12

3.3.


Siêu đồ thị (hyper-graph).............................................................................. 15

3.4.

Nhóm theo chủ đề (community) .................................................................. 17

Chƣơng 4. PHƢƠNG PHÁP ĐỀ XUẤT ............................................................. 18
4.1

SemiRank ................................................................................................. 18

4.2

Phƣơng pháp cụm từ trọng tâm ................................................................. 25

4.3

Phƣơng pháp sử dụng đặc điểm thơng tin của cụm từ khóa ....................... 28

4.4

Tiền xử lý dữ liệu đầu vào ........................................................................ 29

Chƣơng 5. THỰC NGHIỆM ............................................................................... 32
5.1.

Wiki-20 .................................................................................................... 32

5.2.


Phƣơng pháp đánh giá .............................................................................. 32

5.3.

Hiện thực các phƣơng pháp ...................................................................... 35



Hiện thực SemiRank ....................................................................................... 36



Hiện thực tiền xử lý dữ liệu ............................................................................ 38


ii



Hiện thực phƣơng pháp cụm từ trọng tâm ..................................................... 38



Hiện thực phƣơng pháp sử dụng đặc điểm thông tin của cụm từ khóa........ 39

5.3.

Đánh giá hiệu quả ..................................................................................... 39




Xác định số lƣợng cụm từ khóa ban đầu ....................................................... 39



Hiệu quả khi kết hợp với mối quan hệ ngữ nghĩa trong SemiRank ............. 42



So sánh với các phƣơng pháp khác ................................................................ 43



Sử dụng phƣơng pháp phân nhóm Walktrap ................................................. 44

Chƣơng 6. TỔNG KẾT ....................................................................................... 46
6.1

Các đóng góp ........................................................................................... 46

6.2

Hƣớng phát triển ...................................................................................... 46

THAM KHẢO ...................................................................................................... 48


iii


DANH MỤC HÌNH

Hình 3.1. Ví dụ về các thành phần trong Wikipedia ............................................... 11
Hình 3.2. Ví dụ về biểu diễn siêu đồ thị G1 ........................................................... 16
Hình 4.1. Quy trình rút trích cụm từ khóa trong SemiRank .................................... 18
Hình 4.2. Giải thuật PhraseRank trong SemiRank ................................................. 22
Hình 4.3. Minh họa một số bƣớc lặp trong giải thuật PhraseRank. ......................... 23
Hình 4.4. Q trình rút trích tập các cụm từ khóa ban đầu trong phƣơng pháp cụm
từ trọng tâm. .......................................................................................................... 25
Hình 5.1. Đồ thị biểu diễn hiệu suất thu đƣợc khi sử dụng phƣơng pháp cụm từ
trọng tâm ............................................................................................................... 40


iv

DANH MỤC BẢNG

Bảng 2-1. Các đặc điểm đƣợc sử dụng trong một số hệ thống rút trích cụm từ khóa 9
Bảng 3-1. Trọng lƣợng của các kiểu liên kết khác nhau ......................................... 13
Bảng 5-1. Hiệu suất của SemiRank khi sử dụng tiêu đề và sử dụng phƣơng pháp
cụm từ trọng tâm ................................................................................................... 41
Bảng 5-2. Hiệu suất của SemiRank khi sử dụng tiêu đề và sử dụng phƣơng pháp đặc
điểm thông tin ....................................................................................................... 42
Bảng 5-3. Hiệu suất của tập các cụm từ khóa ban đầu so với tập các cụm từ khóa
sau khi đánh giá ngữ nghĩa .................................................................................... 43
Bảng 5-4. Hiệu suất của các phƣơng pháp rút trích cụm từ khóa khác nhau trên tập
dữ liệu Wiki-20 ..................................................................................................... 44
Bảng 5-5. Hiệu suất đạt đƣợc khi sử dụng giải thuật phân nhóm Walktrap. ........... 44



1

Chƣơng 1. MỞ ĐẦU

1.1 Xác định bài tốn
Cụm từ khóa là những từ hay cụm từ có nghĩa đại diện cho nội dung tóm tắt của tài
liệu. Vì diễn tả nội dung chính của tài liệu, những cụm từ khóa này có thể đƣợc sử
dụng trong các cơng cụ tìm kiếm nhƣ là trở thành siêu dữ liệu (metadata) để giúp
ngƣời sử dụng dự đoán nội dung của tài liệu và từ đó tìm kiếm đƣợc bài viết có nội
dung phù hợp [9]. Các cụm từ khóa này cũng có thể đƣợc dùng để gom nhóm và
phân loại các tài liệu vào các chủ đề khác nhau [6]. Chúng cũng có thể đƣợc dùng
để xây dựng các bộ từ điển đồng nghĩa (thesaurus) [19].
Cùng với sự phát triển của công nghệ thông tin, số lƣợng các tài liệu điện tử
ngày càng nhiều nhƣng ít trong số chúng đƣợc tác giả gán các cụm từ khóa. Thêm
vào đó việc gán các cụm từ khóa bằng tay là một cơng việc địi hỏi nhiều thời gian
và cơng sức, vì thế, các cơng cụ gán tự động trở thành một lựa chọn mang lại nhiều
hứa hẹn.
Có hai hƣớng tiếp cận chính để giải quyết bài toán này: hƣớng sử dụng các
cụm từ thuộc một bộ từ vựng đƣợc kiểm soát (controlled vocabulary) làm khóa và
hƣớng rút trích các cụm từ khóa từ trong nội dung của văn bản. Trong hƣớng tiếp
cận thứ nhất, các cụm từ khóa là các từ vựng trong bộ từ vựng đƣợc kiểm soát. Bộ
từ vựng kiểm soát bao gồm những cụm từ đƣợc chọn lựa kỹ lƣỡng, mỗi cụm từ diễn
tả một khái niệm duy nhất nào đó. Khi chọn khóa cho tài liệu, những cụm từ này sẽ
đƣợc xem xét. Bộ từ vựng kiểm soát giúp bảo tồn tính đồng nhất giữa các cụm từ
khóa của các tài liệu khác nhau. Bộ từ vựng kiểm soát thƣờng đƣợc tạo ra cho một
lĩnh vực (domain) cụ thể nào đó và có kích thƣớc giới hạn. Ví dụ nhƣ MeSH1 là một

1

/>


2

dạng của bộ từ vựng kiểm soát, MeSH cung cấp những cụm từ và những mô tả
cho lĩnh vực y khoa.
Hƣớng tiếp cận thứ hai là rút trích các cụm từ khóa từ trong nội dung của văn
bản. So với hƣớng tiếp cận thứ nhất những cụm từ đƣợc chọn làm khóa khơng bị
giới hạn. Nhƣng nhƣ vậy khơng có sự đồng nhất giữa các cụm từ khóa đƣợc chọn
giữa các tài liệu khác nhau. Ở đây đề tài quan tâm đến những phƣơng pháp rút trích
các cụm từ khóa từ trong nội dung của tài liệu.

1.2 Mục tiêu và phạm vi
Để xác định đƣợc tập các cụm từ khóa đại diện cho nội dung tóm tắt của tài liệu, đề
tài đã kết hợp những đặc trƣng của những cụm từ khóa với ngữ nghĩa. Cụ thể, đề tài
xây dựng một tập các cụm từ khóa ban đầu dựa vào các đặc trƣng của khóa, sau đó
tiến hành đánh giá vai trị cụm từ khóa của chúng bằng cách xem xét mối quan hệ
ngữ nghĩa của chúng với nhau.
Bằng cách sử dụng lại phƣơng pháp đánh giá ngữ nghĩa trong SemiRank, trong
phạm vi của mình, đề tài xây dựng lại tập các cụm từ khóa ban đầu cho nó dựa vào
các đặc trƣng khác nhau của cụm từ khóa. Hai phƣơng pháp đƣợc đề xuất là:
phƣơng pháp cụm từ trọng tâm và phƣơng pháp sử dụng đặc điểm thông tin của
cụm từ khóa.
SemiRank rút trích các cụm từ trong tiêu đề và coi chúng là các cụm từ khóa
ban đầu cũng nhƣ là cụm từ khóa sau cùng, sau đó tìm kiếm thêm những cụm từ
khóa cịn lại từ trong văn bản mà những cụm từ khóa này có mối quan hệ ngữ nghĩa
phù hợp với các cụm từ khóa ban đầu đã cho. Trong khi đó, đề tài mở rộng tập từ
khóa ban đầu và đánh giá lại vai trị của các cụm từ khóa ban đầu này thơng qua
mối quan hệ ngữ nghĩa của chúng với nhau. Nhƣ thế tập các cụm từ khóa sau cùng
đại diện cho văn bản vừa có đặc trƣng của việc là cụm từ khóa ban đầu và vừa có
đặc trƣng ngữ nghĩa.



3

Khi xử lý tiền dữ liệu, các cụm từ đi qua một bƣớc lọc liên quan đến việc gán
cụm từ vào các bài viết Wikipedia tƣơng ứng với chúng. Nên ở đây, có sự ràng
buộc vào Wikipedia. Mặc dù Wikipedia có kích thƣớc lớn nhƣng nó vẫn nhỏ hơn số
lƣợng cụm từ có trong ngơn ngữ tự nhiên.
Trong phƣơng pháp cụm từ trọng tâm, đề tài sử dụng một số mẫu là các từ
trong tiếng Anh, nên phƣơng pháp này chỉ áp dụng đƣợc cho các tài liệu có ngơn
ngữ là tiếng Anh.


4

Chƣơng 2. CÁC CƠNG TRÌNH LIÊN QUAN

Để rút trích các cụm từ khóa thích hợp, các hệ thống thƣờng tiến hành qua hai bƣớc
sau: rút trích các cụm từ có trong văn bản làm khóa tiềm năng và lọc ra từ các cụm
từ khóa tiềm năng này những cụm từ thích hợp làm khóa. Chƣơng này trình bày
khái qt về các hệ thống rút trích cụm từ khóa. Mục 2.1 mơ tả tổng qt về các hệ
thống nói chung. Mục 2.2 nêu lên các đặc điểm đƣợc sử dụng để lọc ra các cụm từ
khóa.

2.1. Tổng quát
Nhƣ đã nói ở trên, các hệ thống rút trích các cụm từ khóa thƣờng trải qua hai bƣớc:
rút trích các cụm từ khóa tiềm năng và lọc lấy các cụm từ khóa. Có nhiều phƣơng
pháp khác nhau để tìm kiếm các cụm từ khóa tiềm năng trong nội dung văn bản.
Cách đơn giản và phổ biến nhất là n-gram [3, 5, 11, 23], cắt tuần tự n từ đơn đứng
kế tiếp nhau và coi nó là khóa tiềm năng. Nhƣợc điểm của phƣơng pháp này là các

từ đơn đứng kế nhau không phải lúc nào cũng tạo thành cụm từ có nghĩa.
Để khắc phụ nhƣợc điểm trên, phƣơng pháp lấy theo mẫu (POS pattern) đƣợc
sử dụng [5, 18], các câu trong văn bản đƣợc đƣa qua một bộ phân tích cú pháp để
xác định từ loại của nó và chỉ những cụm từ nào trong câu thỏa mãn các mẫu từ loại
mới đƣợc chọn làm cụm từ khóa tiềm năng.
Trong những năm gần đây, cùng với sự lớn mạnh của Wikipedia, các cụm từ
trong văn bản còn đƣợc gán với các bài viết trong Wikipedia (article) [4, 8, 14], các
bài viết này đại diện cho ngữ nghĩa của cụm từ. Chỉ những cụm từ có khả năng tìm
thấy một hay nhiều bài viết tƣơng ứng với nó mới đƣợc chọn làm cụm từ khóa tiềm
năng.
Một khi đã có đƣợc tập các cụm từ khóa tiềm năng, để có thể chọn ra đƣợc các
cụm từ thích hợp làm khóa, các hệ thống tự động thƣờng sử dụng những đặc điểm
đƣợc cho là nên có ở một cụm từ khóa để xây dựng nên bộ lọc. Những đặc điểm


5

này có đƣợc do sự đúc kết từ những quan sát trên các tập khóa đƣợc thực hiện bằng
tay.
Tùy theo từng hệ thống khác nhau mà việc khai thác các đặc điểm này là khác
nhau, mỗi hệ thống sẽ chú trọng một số đặc điểm đƣợc cho là nổi bật hơn cả và bỏ
qua những đặc điểm khác. Có thể chia các hệ thống này thành hai nhóm chính:
nhóm sử dụng phƣơng pháp học có giám sát (marchine learning) và nhóm sử dụng
phƣơng pháp học khơng có giám sát (unsupervised learning). Nhóm sử dụng
phƣơng pháp học có giám sát [5, 11, 14, 23] sử dụng một tập dữ liệu huấn luyện
(training data) để xây dựng nên mơ hình học máy. Tập dữ liệu huấn luyện này bao
gồm các tài liệu đã có sẵn các cụm từ khóa đƣợc gán bằng tay. Những mơ hình học
máy thƣờng đƣợc áp dụng là mơ hình Nạve Bayes [18, 23] hay cây ra quyết định
(decision tree) [11, 14, 18]. Nhƣợc điểm của phƣơng pháp này là đòi hỏi tập dữ liệu
huấn luyện phải lớn [14].

Hƣớng tiếp cận học khơng có giám sát: những hệ thống của nhóm này khơng
địi hỏi phải có tập huấn luyện ban đầu, [1, 3, 24] xây dựng phƣơng trình đo lƣờng
tầm quan trọng của các cụm từ tiềm năng; [8, 15] biểu diễn nội dung của tài liệu
dƣới dạng đồ thị ngữ nghĩa từ đó xác định vai trị của một cụm từ thông qua các mối
quan hệ này.

2.2. Các đặc điểm của cụm từ khóa nói chung
Các đặc điểm dùng để đánh giá vai trò của một cụm từ trong tài liệu nhìn chung có
thể chia làm ba nhóm chính. Nhóm đặc điểm từ nằm trong cụm từ xem xét sự đóng
góp của các từ đơn cho cụm từ mà nó thuộc về. Nhóm đặc điểm thơng tin của cụm
từ xem xét cụm từ độc lập với các cụm từ khác, nó đánh giá vai trị của cụm từ
thơng qua thơng tin mà cụm từ đóng góp cho tài liệu. Và cuối cùng là đặc điểm xem
xét mối quan hệ ngữ nghĩa giữa các cụm từ trong văn bản.


6

Đặc điểm từ nằm trong cụm từ
Một đặc điểm thƣờng dùng khi xem xét các từ nằm trong một cụm từ nào đó là độ
kết dính của các từ trong nó. Đặc diểm này dùng để xác định mức độ cấu thành cụm
từ của các từ trong nó. Phép đo độ kết dính đo đạc trên khả năng các từ này đồng
xuất hiện cùng với nhau trong một cụm từ. Phép đo này dựa trên giải thiết là các
cụm từ có độ kết dính cao có khả năng trở thành cụm từ khóa.
Đặc điểm liên quan đến thơng tin mà cụm từ đóng góp cho tài liệu
Đây là nhóm đƣợc khai thác nhiều nhất trong các hệ thống rút trích từ khóa tự động.
Ở đây, đề tài chỉ nêu lên một số đặc điểm phổ biến trong nhóm này. Đầu tiên phải
kể đến là sự xuất hiện lặp lại của cụm từ, phép đo chính của nó là TF (term
frequency – tầng suất xuất hiện của một cụm từ), TF dựa trên giả thiết là nếu một
cụm từ là quan trọng, nó sẽ đƣợc lặp lại nhiều lần trong nội dung của văn bản. TF
có nhiều biến thể khác nhau, có thể đƣợc đo trên cả văn bản hoặc chỉ trên một phân

đoạn nào đó của văn bản. TF thƣờng đƣợc kết hợp cùng IDF (Inverse document
frequency – tấn suất nghịch của một cụm từ) để tránh trƣờng hợp những cụm từ
đƣợc lặp lại là những cụm từ quá phổ biến, khơng diễn tả nội dung chính của tài liệu
và có thể tìm thấy ở nhiều tài liệu khác, IDF đo số lần cụm từ xuất hiện trong các tài
liệu khác nhau của một tập thống kê (corpus), vì thế IDF phụ thuộc vào tập thống kê
này.
Kế đến là đặc điểm vị trí của cụm từ, phép đo chính là phép đo vị trí lần đầu
tiên cụm từ xuất hiện FOC (first of occurrence – vị trí lần đầu xuất hiện). Phép đo
này dựa trên giả thiết là nếu cụm từ là quan trọng, nó sẽ đƣợc nhắc đến sớm trong
nội dung của tài liệu. Một biến thể của nó là phép đo vị trí lần cuối cùng cụm từ
xuất hiện (last occurrence) và độ phủ của cụm từ (occurrence spread) trong nội
dung văn bản, độ phủ xác định khoảng cách giữa lần đầu tiên và lần cuối cùng cụm
từ xuất hiện. Ngồi ra cịn có thêm một dạng biến thể nữa đó là phép đo lần đầu tiên
cụm từ xuất hiện trong một phân đoạn cụ thể của tài liệu ví dụ nhƣ trong phần tóm
tắt hay phần giới thiệu.


7

Một đặc điểm cũng đƣợc sử dụng thƣờng xuyên trong các hệ thống rút trích
cụm từ khóa đó là xem xét mức độ cụ thể mà một cụm từ diễn tả, phép đo đƣợc
dùng là đo chiều dài của cụm từ khóa. Những cụm từ khóa bao gồm nhiều từ gộp lại
thƣờng diễn tả ý cụ thể hơn là những cụm từ ngắn và vì thế có nhiều cơ hội làm
khóa hơn. Nhƣng chiều dài tối đa của cụm từ khóa thƣờng khơng lớn hơn ba [23].
Đặc điểm kế tiếp là dựa trên phép đo keyphraseness. Khi một cụm từ đã đƣợc
chọn làm khóa, thì nó cũng có khả năng đƣợc chọn làm khóa trong một tài liệu khác
có cùng chủ đề. Keyphraseness đo đạc dựa trên số lần một cụm từ đƣợc chọn làm
khóa trong một tập thống kê. Vì vậy, một cách tự nhiên, keyphraseness phụ thuộc
vào kích thƣớc và chủ đề của tập thống kê.
Khi gán các bài viết Wikipedia cho các cụm từ để diễn tả nội dung của các

cụm từ này, một số đặc điểm mới đã đƣợc đề xuất, trong đó có Wiki-keyphraseness,
Wiki-keyphraseness dựa trên giả thiết rằng nếu cụm từ là quan trọng thì mỗi lần nó
xuất hiện trong một bài viết Wikipedia nào đó, nó sẽ đƣợc gán một liên kết tham
khảo đến bài viết diễn tả ý nghĩa hoặc nội dung liên quan đến nó. Một biến thể của
Wiki-keyphraseness là tính Wiki-keyphraseness cho một bài viết Wikipedia thay vì
tính cho một cụm từ (inverse Wikipedia frequency).
Đặc điểm mối quan hệ ngữ nghĩa
Khi sử dụng mối quan hệ ngữ nghĩa để tìm khóa, một số hệ thống dựa trên giả
thiết rằng những từ khóa sẽ giữ vai trị trung tâm, chúng đƣợc hỗ trợ về nghĩa cao
nhất bởi các từ có trong tài liệu. [10, 15] định nghĩa mối quan hệ này bằng cách liên
kết những từ đơn cùng xuất hiện trong một cửa sổ (window) có kích thƣớc cố định.
Cửa sổ đƣợc chạy dọc nội dung văn bản và các liên kết tạo thành một đồ thị đại
diện cho nội dung của văn bản. Liên kết tìm đƣợc có thể là liên kết ngữ nghĩa hoặc
liên kết về từ (lexicon). Mục đích của TextRank [15] và DegExt [10] là tìm kiếm
các từ trọng tâm trong đồ thị và từ những từ đơn này, các cụm từ chứa chúng sẽ
đƣợc dùng làm khóa. Trong khi đó, [11] xác định mối quan hệ ngữ nghĩa giữa hai
cụm từ khi chúng cùng xuất hiện trong một tài liệu. Mối quan hệ ngữ nghĩa giữa hai


8

cụm từ đƣợc đo đạc bằng xác suất để một cụm từ đƣợc coi là khóa nếu cụm từ cịn
lại đƣợc chọn làm khóa. Các cụm từ nào có mối quan hệ ngữ nghĩa cao nhất với các
cụm từ còn lại thì có nhiều khả năng trở thành khóa.
Maui [14] khơng coi cụm từ khóa là trung tâm nhƣng nó có mối quan hệ ngữ
nghĩa cao với các cụm từ khóa khác. Maui định lƣợng mối quan hệ ngữ nghĩa của
hai cụm từ dựa vào số lƣợng bài viết Wikipedia chung mà hai bài viết đại diện cho
hai cụm từ đang xét có liên kết tham khảo. Mối quan hệ ngữ nghĩa giữa một cụm từ
và các cụm từ còn lại đƣợc tính và nó trở thành một đặc điểm để xây dựng mơ hình
học máy cùng với nhiều đặc điểm khác nhƣ là vị trí hay số lần lặp lại của cụm từ.

Cũng giống nhƣ Maui, [4, 8] dựa vào các bài viết Wikipedia chung của hai bài
viết đại diện cho hai cụm từ cần định lƣợng mối quan hệ ngữ nghĩa, nhƣng [4, 8]
gán tầm quan trọng khác nhau cho từng liên kết có đƣợc tại một bài viết và xét mối
liên hệ của hai bài viết thông qua trọng lƣợng của các liên kết chung này. Ngoài ra
[4, 8] còn xác định các mối quan hệ ngữ nghĩa giữa một nhóm các cụm từ bằng
cách phân nhóm cho các cụm từ này theo quan hệ ngữ nghĩa giữa chúng. Tuy
nhiên, [4] đánh giá tầm quan trọng của cả nhóm và coi mọi phần tử trong nhóm là
cụm từ khóa. [8] xem một cụm từ là khóa nếu nó có mối quan hệ ngữ nghĩa thích
hợp với tập các cụm từ khóa ban đầu.
Các đặc điểm trên đƣợc sử dụng kết hợp với nhau trong các hệ thống tự động.
Ví dụ nhƣ sau khi chọn ra các cụm từ khóa tiềm năng, [18] đo đạc các đặc điểm TF,
IDF, FOC và chiều dài cho các cụm từ tiềm năng trong văn bản, ngồi ra cịn có TF
cho các từ đơn hoặc cụm từ con trong các cụm từ tiềm năng này để xây dựng mơ
hình học máy cho việc phân loại cụm từ khóa. Bảng 2.1 liệt kê chi tiết đặc điểm
đƣợc sử dụng trong một số hệ thống rút trích cụm từ khóa.
Việc khai thác đặc điểm ngữ nghĩa vẫn còn là vấn đề đang đƣợc quan tâm
trong việc giúp lọc ra các cụm từ khóa [7], nên ở đây đề tài chú trọng đến mối quan
hệ ngữ nghĩa giữa các cụm từ. Cụ thể, đề tài khai thác mối quan hệ ngữ nghĩa có


9

trong [8] bằng cách kết hợp một số đặc trƣng khác của cụm từ khóa với nó nhƣ
đƣợc trình bày trong Chƣơng 4.

x

x

WINGNUS [18]


x

x

x

MAUI [14]

x

x

x

KP-MINER [3]

x

x

x

DERIUNLP [1]

x

x

x


COREWORD [13]

x

x

x

x

TEXTRANK [15]
SEMIRANK [8]
TOPIC [4]

x

Phƣơng pháp học

x

HUMB [11]

Khóa là nhóm

x

Khóa - khóa

x


Khóa làm tâm

KEA++ [13]

Khóa-cụm từ

x

Cụm từ - Cụm từ

Wikipedia
keyphraseness

x

Từ viết tắt

KEA [23]

Keyphraseness

Vị trí

Mức độ cụ thể

Thông tin của cụm từ

Sự lặp lại


Độ kết dính

TừCụm từ

S
x

x

x

S
x

S
S

x

x

x

S
U

x

U
U


x

x

x

U
x

x

U
x

U

Bảng 2-1. Các đặc điểm được sử dụng trong một số hệ thống rút trích cụm từ khóa.
S: học có giám sát và U:học khơng có giám sát


10

Chƣơng 3. CƠ SỞ LÝ THUYẾT

Chƣơng 3 mô tả các khái niệm và phƣơng pháp nền tảng đƣợc sử dụng trong đề tài:
Wikipedia, định lƣợng mối quan hệ ngữ nghĩa, phân giải nhập nhằng, siêu đồ thị và
nhóm theo chủ đề.

3.1. Wikipedia

Wikipedia là dự án nhằm xây dựng một bách khoa tồn thƣ trực tuyến miễn phí cho
tất cả các ngôn ngữ trên thế giới. Đƣợc thành lập năm 2001, đến nay Wikipedia là
một trong những trang trực tuyến đƣợc tham khảo nhiều nhất trên thế giới, khoảng
470 triệu ngƣời tham khảo mỗi tháng, đƣợc tính cho tới tháng 2/2012. Đến tháng
10/2013, Wikipedia có trên 30 triệu bài viết (article) trên 286 ngơn ngữ. Trong đó,
có hơn 4 triệu bài bằng tiếng Anh.
Cấu trúc của Wikipedia bao gồm các thành phần nhƣ: các bài viết, liên kết
tham khảo, thể loại của bài viết, … Ở đây, đề tài chỉ xin tóm tắt các thành phần
chính của Wikipedia:


Bài viết Wikipedia (article): bài viết là các thành phần chủ đạo của Wikipedia.
Mỗi bài viết mô tả một khái niệm duy nhất nào đó. Wikipedia đƣa ra những
hƣớng dẫn về soạn thảo để đảm bảo về nội dung và hình thức của các bài viết.
Tiêu đề là duy nhất cho mỗi bài viết, bên cạnh tiêu đề mỗi bài viết cịn có mã
định danh(id) để phân biệt nó với các bài viết khác.



Trang chuyển hƣớng (redirect): trang chuyển hƣớng là những trang không có
nội dung, nó chỉ bao gồm một tham khảo để liên kết đến một trang khác (một
bài viết hay một trang chuyển hƣớng mới). Bởi vì mỗi khái niệm chỉ đƣợc mô
tả bởi một bài viết duy nhất, nên những cụm từ diễn tả cùng một khái niệm có
thể đƣợc mô tả bằng những trang chuyển hƣớng này và chúng chứa liên kết
tham khảo đến bài viết trình bày khái niệm.


11




Liên kết (hyper-link): trong nội dung của bài viết, nếu có một cụm từ nào đó
quan trọng, tác giả bài viết đƣợc khuyến khích tạo ra một liên kết từ cụm từ
này đến bài viết có nội dung liên quan. Bài viết này có thể là mơ tả khái niệm
của cụm từ cũng có thể là chứa thơng tin liên quan đến nó. Cụm từ đƣợc tạo
liên kết trên đƣợc gọi là cụm từ neo (anchor). Cùng một cụm từ neo có thể liên
kết đến các bài viết khác nhau, ví dụ 84% liên kết từ từ neo “library”(“thư
viện”) dẫn đến bài viết “Library” (“Thư viện”), và 13% liên kết là dẫn tới bài
viết “Library (computing)” (Thư viện (máy tính)) [14].



Trang định hƣớng (disambiguation page): trang định hƣớng chứa các liên kết
đến những bài viết khác nhau diễn tả các nghĩa khác nhau có thể có của một
cụm từ nào đó. Tại đây ngƣời sử dụng chọn lựa nghĩa thích hợp mà họ muốn
tham khảo.



Thể loại (category): các bài viết thƣờng đƣợc phân vào các thể loại liên quan
đến nội dung mà nó đề cập. Các tác giả bài viết đƣợc khuyến khích nên gán
thể loại cho các bài viết. Một thể loại có thể thuộc về một thể loại khác, điều
này hình thành nên cấu trúc gần giống cấu trúc cây cho các thể loại.

Hình 3.1. Ví dụ về các thành phần trong Wikipedia
Hình 3.1 là một ví dụ về các thành phần của Wikipedia [14]. “Library”(“Thư
viện”) là một bài viết, nó có các trang chuyển hƣớng nhƣ “Libraries”(“các thư
viện”), “Reading room” (“phịng đọc”) và nó có các liên kết đến các bài viết khác
nhƣ là “Book”(“sách”), “Bookend” (“giá sách”). Bài viết “Library” thuộc về thể



12

loại “Libraries”, thể loại này vừa là thể loại con của các thể loại: “Library and
information science” (“thư viện và khoa học thơng tin”), “Buildings and
structures” (“tịa nhà và cấu trúc”) …, vừa có các thể loại con nhƣ: “Digital
libraries” (“thư viện số”), “Academic libraries” (“thư viện học thuật”).
Bản Wikipedia đƣợc sử dụng trong đề tài là bản đƣợc công bố ngày
22/07/2011. Bản Wikipedia này chỉ bao gồm các bài viết bằng tiếng Anh. Số lƣợng
bao gồm khoảng 3.5 triệu bài, 5 triệu trang chuyển hƣớng (redirect) và khoảng
700,000 thể loại (category).

3.2. Định lƣợng mối quan hệ ngữ nghĩa và phân giải nhập nhằng
Có nhiều cách khác nhau để định lƣợng mối quan hệ ngữ nghĩa giữa hai cụm từ, ở
đây, đề tài chỉ xin trình bày phƣơng pháp dựa vào Wikipedia. Cụ thể hơn, là phƣơng
pháp đƣợc nêu trong [22], đo đạc mối quan hệ ngữ nghĩa giữa hai bài viết
Wikipedia đại diện cho hai cụm từ đang xét. [22] không bao gồm phƣơng pháp gán
bài viết Wikipedia đại diện cho ngữ nghĩa của từ mà chỉ đề xuất phƣơng pháp để đo
lƣờng mối quan hệ giữa hai bài viết này. Phƣơng pháp đo đạc đƣợc tóm tắt nhƣ
phần trình bày tiếp theo sau đây.
Mỗi bài viết Wikipedia bao gồm các liên kết đi (outgoing link) và các liên kết
đến (incoming link). Ở đây chỉ tính đến những liên kết xuất phát hoặc dẫn đến một
bài viết Wikipedia. Để một bài viết đƣợc tham khảo đến một bài viết khác thì các
bài viết này phải có nội dung liên quan đến nhau, [22] nhận thấy rằng sự tham khảo
này sẽ có những mức độ khác nhau tùy theo kiểu liên kết. Vì vậy, [22] đã gán các
trọng lƣợng khác nhau cho các kiểu liên kết đến và liên kết đi thuộc một bài viết
Wikipedia nhƣ sau:


Liên kết “Xem thêm” (See Also): hầu hết các bài viết Wikipedia đều có một

phân đoạn dành để liên kết với những bài viết có nội dung liên quan đến nó gọi
là “Xem thêm” (See Also). Một liên kết nằm trong phân đoạn này (gọi là liên
kết trong “Xem thêm”) thì đƣợc gán giá trị cao nhất, bằng 5. Và ngƣợc lại,


13

nếu liên kết đến bài viết này lại thuộc vào phân đoạn “Xem thêm” của một bài
viết Wikipedia nào đó (gọi là liên kết từ “Xem thêm”), thì liên kết cũng đƣợc
gán giá trị tƣơng xứng, bằng 2.


Liên kết hai chiều: nếu liên kết đi của một bài viết Wikipedia dẫn đến một bài
viết Wikipedia khác mà tại đó cũng có một liên kết chiều ngƣợc lại đến bài
viết này (gọi là liên kết hai chiều) thì liên kết cũng đƣợc gán giá trị bằng 2.



Liên kết cùng một thể loại: liên kết là cùng một thể loại nếu bài viết Wikipedia
chứa liên kết tham khảo và bài viết Wikipedia đƣợc tham khảo đến thuộc cùng
một thể loại. Ở đây không phân biệt liên kết đi hay liên kết đến. Những liên
kết này đƣợc gán giá trị bằng 1.5.



Liên kết ngày và liên kết thuộc bản mẫu (template): liên kết ngày là liên kết
mà nó dẫn tới một bài viết mơ tả một thời điểm nào đó tính theo thời gian. Ví
dụ: bài viết “1977” mơ tả các sự kiện quan trọng diễn ra trong năm 1977. Và
liên kết thuộc bản mẫu là liên kết nằm trong một bản mẫu nào đó. Các bài viết
có nội dung liên quan đến nhau thƣờng sử dụng chung một số bản mẫu, nhƣ là

để thống nhất văn phong hay cách trình bày. Cả hai loại liên kết này nhận giá
trị thấp nhất, bằng 0.1.



Liên kết tham khảo: tất cả liên kết đi còn lại đƣợc gán giá trị bằng 1 và tất cả
liên kết đến còn lại đƣợc gán giá trị bằng 0.5.

Bảng 3.1 tóm tắt giá trị đƣợc gán cho các kiểu liên kết khác nhau.
Liên kết trong “Xem thêm”

5

Liên kết hai chiều

2

Liên kết từ “Xem thêm”

2

Liên kết cùng thể loại

1.5

Liên kết đi

1

Liên kết đến


0.5

Liên kết ngày

0.1

Liên kết bản mẫu

0.1

Bảng 3-1. Trọng lượng của các kiểu liên kết khác nhau


14

Mối quan hệ ngữ nghĩa giữa hai bài viết đƣợc đo bằng các liên kết chung mà
hai bài viết này có với nhau (bao gồm cả liên kết đi và liên kết đến). Ở đây, [22] áp
dụng phép đo Dice có trọng lƣợng, mối quan hệ ngữ nghĩa đƣợc tính dựa trên trọng
lƣợng của những liên kết chung của hai bài viết. Trong phần mơ tả phƣơng pháp
của mình, [22] đã khơng mơ tả phép tính chi tiết, nên đề tài đã tính theo cơng thức
sau:

𝑠𝑖𝑚(𝐴𝑖 , 𝐴𝑗 ) =

𝑡∈(𝐴 𝑖 ∩𝐴 𝑗 )(𝑤 𝐴 𝑖

𝑡 +𝑤 𝐴 𝑗 𝑡 )

𝑡∈𝐴 𝑖 𝑤 𝐴 𝑖


𝑡∈𝐴 𝑗

𝑡 +

𝑤𝐴𝑗 𝑡

(3.1)

Trong đó Ai, Aj là các bài viết Wikipedia đang xét. 𝑤𝐴𝑖 𝑡 là trọng lƣợng của
liên kết t trong bài viết Ai.
Nếu trong quá trình gán bài viết Wikipedia đại diện cho ngữ nghĩa của một
cụm từ nào đó mà có thể tìm thấy hơn một bài viết Wikipedia có khả năng đại diện
cho nó, thì ở đây ta có một dạng của bài toán nhập nhằng, lúc này cần chọn ra bài
viết nào là thích hợp nhất cho cụm từ đang xét. Để giải quyết vấn đề này, ngƣời ta
thƣờng sử dụng nội dung của văn bản nơi cụm từ đó xuất hiện, tìm kiếm những cụm
từ khơng nhập nhằng xung quanh cụm từ đang xét làm ngữ cảnh, từ đó xem xét tất
cả các nghĩa có thể của cụm từ đang xét. Cụm từ không nhập nhằng là những cụm
từ mà chỉ tìm thấy duy nhất một bài viết Wikipdia cho nó. Lúc này, từng bài viết
Wikipedia đƣợc giả định là đại diện cho nghĩa của cụm từ đang xét và từ đó tính
tốn mối quan hệ ngữ nghĩa với ngữ cảnh của nó. Bài viết Wikipedia giả định nào
có mối quan hệ tốt nhất với ngữ cảnh thì nó đƣợc chọn đại diện cho nghĩa của cụm
từ. [22] đề xuất sử dụng phƣơng pháp đo lƣờng ngữ nghĩa nhƣ đã nêu ở trên để tìm
kiếm bài viết Wikipedia thích hợp cho cụm từ theo ngữ cảnh của nó.
Nhận xét: Để có thể xác định đƣợc trọng lƣợng của các liên kết đến và đi của một
bài viết Wikipedia nào đó, việc xử lý nội dung của bài viết là cần thiết. Ví dụ, để
biết đƣợc một liên kết thuộc kiểu liên kết trong “Xem thêm” hay khơng, thì cần phải
tìm kiếm chúng trong phân đoạn “Xem thêm” của bài viết này; hay để biết đƣợc



15

một liên kết đến có thuộc kiểu liên kết từ “Xem thêm” hay khơng, thì cũng cần đọc
qua phân đoạn “Xem thêm” của bài viết tạo liên kết đến này.
Nếu một bài viết Wikipedia diễn tả một khái niệm chung nào đó thì nó sẽ có
rất nhiều liên kết đi và liên kết đến, ví dụ bài viết “United Kingdom” có hơn 80
ngàn liên kết đi và liên kết đến [22], nhƣ vậy việc phải đọc qua toàn bộ nội dung
của các bài viết này để xác định trọng lƣợng của các liên kết trong bài viết “United
Kingdom” đòi hỏi cần phải có thời gian xử lý.

3.3. Siêu đồ thị (hyper-graph)
Siêu đồ thị là đồ thị mà mỗi cạnh của nó bao gồm từ một đỉnh trở lên (≥1đỉnh). Cho
một siêu đồ thị G = (V, E), trong đó V là tập các đỉnh và E là tập các cạnh thuộc đồ
thị. Mỗi cạnh e (e ∈ 𝐸) là một tập bao gồm các đỉnh 𝑣 (𝑣 ∈ 𝑉) và số lƣợng đỉnh
thuộc e: 1≤ |e| ≤ |V|, e có tối thiểu một đỉnh và tối đa là tất cả các đỉnh của đồ thị.
Các cạnh e đƣợc gọi là các cạnh bậc cao (hyper-edge).
Ví dụ: cho đồ thị G1 đƣợc biểu diễn nhƣ trong Hình 3.2. Hình (A) biểu diễn
dạng đồ thị của G1. Trong đó G1 gồm có 8 đỉnh (V) và 3 cạnh bậc cao (E). Ta có,
cạnh e2 bao gồm tập đỉnh {v3, v4, v8} và tƣơng tự cho các cạnh còn lại.
Một siêu đồ thị có trọng lƣợng là một siêu đồ thị nhƣng các cạnh của nó đƣợc
gán các giá trị khác nhau đại diện cho trọng lƣợng của cạnh. Thêm thông tin trọng
lƣợng vào đồ thị G, ta có G´ = (V, E, W), trong đó W là trọng lƣợng của các cạnh
tƣơng ứng trong E.
Để biểu diễn mối liên hệ giữa đỉnh v (𝑣 ∈ 𝑉) và các cạnh e (e ∈ 𝐸), ta có:
ℎ(𝑣, 𝑒) =

1, 𝑛ế𝑢 𝑣 ∈ 𝑒
0, 𝑛ế𝑢 𝑣 ∉ 𝑒

(3.2)


Từ đó ta có ma trận H biểu diễn mối liên hệ giữa tập đỉnh V và tập cạnh E. Hình
3.2(B) biểu diễn dạng ma trận mối liên hệ giữa tập đỉnh và tập cạnh trong G1.