1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

HOÀNG THỊ VÂN ANH TRÍCH RÚT THỰC THỂ TÊN TỪ CÁC VĂN BẢN
TIẾNG VIỆT TRÊN INTERNET LUẬN VĂN THẠC SĨ KỸ THUẬT



Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

26
với đặc thù riêng của bài toán trích rút thực thể tên tiếng
Việt. Hệ thống đã hoạt động và trích rút các thực thể tên từ
các văn bản tiếng Việt.
Quá trình xây dựng hệ thống còn gặp một số khó
khăn như: Thuật toán DIPRE chỉ thường áp dụng cho các
bài toán trích rút cặp quan hệ. Vì vậy, khi trích rút thực thể
đơn sẽ gặp khó chọn lọc được Pattern mẫu trong quá trình
xây dựng Pattern và sinh Pattern mới. Mặt khác, thực thể
tên có nhiều cách biểu diễn khác nhau nên rất khó để tìm
ra mối liên hệ khi xây dựng mẫu hoặc có thể xảy ra nhập
nhằng.
Trong tương lai, tôi sẽ tiếp tục nghiên cứu về trích
rút thông tin và phát triển hệ thống, bổ sung chức năng tìm
kiếm, nhận diện thực thể tên ở những trường hợp đặc biệt
và nâng cao chất lượng trích rút. Tôi dự định sẽ tìm hiểu
sâu hơn về kỹ thuật xây dựng Pattern để có những Pattern
hợp lý hơn. Ngoài ra, tôi sẽ tiến hành phân tích thêm về
xâu ký tự đứng trước Pattern để hạn chế nhập nhằng và
trích rút được thực thể tên ở một số dạng đặc biệt.
3
MỞ ĐẦU
Thông tin trên các trang web thường thể hiện dưới
dạng ngôn ngữ tự nhiên và được định dạng theo HTML.
Hạn chế của HTML là thiếu khả năng diễn đạt ngữ nghĩa
về các đối tượng xuất hiện trong trang web nên phần lớn

25
KẾT LUẬN
Luận văn đã hệ thống hóa một số lý thuyết về trích
chọn thông tin, trình bày, phân tích, đánh giá các phương
pháp đó. Sau đây là một số nét chính mà luận văn đã tập
trung giải quyết.
Chương I trình bày và nêu ý nghĩa của bài toán
trích rút thực thể tên. Trong chương I, phần đặc điểm tiếng
Việt được để có thể làm căn cứ cho quá trình tìm kiếm và
trích rút thực thể tên. Ngoài ra, chương I còn trình bày một
số hướng tiếp cận để giải quyết bài toán trên là: Giải thuật
DIPRE, phương pháp Snowball, phương pháp KnowItAll.
Sau đó, luận văn phân tích ưu nhược điểm của từng
phương pháp để đề xuất một phương pháp có hiệu quả hơn
trong trích rút thực thể tên. Ở đây, luận văn sử dụng giải
thuật DIPRE kết hợp Snowball để xây dựng hệ thống trích
rút thực thể tên.
Chương II đưa ra mô hình khái quát, mô hình chi
tiết, ý tưởng và cách giải quyết bài toán trích rút thực thể
tên từ các văn bản tiếng Việt.
Chương III xây dựng hệ thống thử nghiệm dựa theo
ý tưởng của thuật toán DIPRE và có cải tiến để phù hợp
24
Bảng 3.4. Bảng kết quả thực nghiệm
File
name
correct

incorrect



95,24

95,24

23254.seg

6
1 1 0 85,71

75,00

80,00

Trung bình:
81,90

77,80

79,710,00
50,00
100,00
1 2 3 4 5 6
Pr
e

Hình 3.5. Giá trị ba độ đo Precision, Recall, F-measure

“author – book” với tập dữ liệu ban đầu khảng 5 ví dụ cho
mối quan hệ này. Hệ thống DIPRE mở rộng tập ban đầu
thành một danh sách khoảng 15.000 cuốn sách.
Tóm tắt giải thuật DIPRE như sau:
Đầu vào: Tập các quan hệ mẫu S={A
i
,

B
i
}
Ví dụ: trong trường hợp trên, tập quan hệ mẫu là S
= {<author
i
, book
i
}. Tập này được gọi là tập hạt giống.
Đầu ra: Tập các quan hệ R trích chọn được.
Xử lý:
- Tập quan hệ đích R được khởi tạo từ tập hạt giống
(seed) S. Ký hiệu tập seed ban đầu là <A, B>
- Tìm tất cả các câu có chứa đủ các thành phần của
tập seed ban đầu.
- Dựa vào tập câu đã tìm được, tiến hành tìm các
mẫu quan hệ giữa các thành phần của seed ban đầu. Mẫu
quan hệ được biểu diễn dưới dạng sau:
[order, author, book, prefix, suffix, middle]
23

Hình 3.1 Giao diện hệ thống

tên từ các văn bản tiếng Việt trên Internet
Hệ thống được thiết kế bằng ngôn ngữ lập trình C#
trên nền tảng .Net Framework của Microsoft Visual Studio
2008 và sử dụng dữ liệu lưu trữ trong phần mềm quản trị
dữ liệu SQL Server 2005.
Hệ thống có giao diện như sau:
7
Từ những mẫu chưa được gán nhãn, ta thu được
một tập seed <A’, B’> mới; thêm seed mới này vào tập
seed cho quan hệ đó.
- Quay lại bước 2 để tìm ra những hạt giống và mẫu
mới.
* Thuật toán GenOnePattern(O) sinh một Pattern
1) Điều kiện: order và middle của tất cả sự xuất hiện
(occurrences) phải giống nhau.
Nếu điều kiện trên không thỏa mãn thì không thể sinh
ra được pattern khớp với tất cả occurrences.
Đặt outpattern.order và outpattern.middle tương ứng
với order và middle.
2) Tìm đoạn prefix giống nhau dài nhất của các urls.
Đặt outpattern.urlprefix = prefix
3) Đặt outpattern.prefix là xâu giống nhau dài nhất của
các prefixs tính từ cuối (suffix) của các tiền tố
(prefixs)
4) Đặt outpattern.suffix là xâu giống nhau dài nhất của
các suffix tính từ đầu (prefix) của các hậu tố (suffixs)
đó.
Kết quả thu được một pattern.
8
* Thuật toán GenPatterns(O) sinh tập Patterns


Hình 1.3 Kiến trúc của hệ thống Snowball
21
thức chính quy CandidateRegularExpression nên cần phải
cắt tỉa và chuẩn hóa để thu được tên chính xác.
Cách viết của tiếng Việt trong các văn bản tiếng Việt
trên Internet rất đa dạng và phong phú. Vì vậy, đôi khi
thông tin viết trong các văn bản tiếng Việt trên Internet
không thật sự theo chuẩn – chuẩn ngữ pháp, chuẩn chữ
hoa chữ thường… khiến cho việc việc cắt tỉa gặp nhiều
khó khăn. Tuy nhiên, các văn bản tiếng Việt đưa vào hệ
thống là các văn bản đã qua khâu tách từ và viết chuẩn chữ
hoa chữ thường. Vì vậy, đây là mặt thuận lợi để kiểm tra
xem xâu con của xâu kỳ vọng CandidateString có phải là
xâu thực thể tên cần trích rút hay không.
2.4 Tổng kết chương
Chương 2 đã trình bày toàn bộ ý tưởng và các thuật
toán để giải quyết bài toán trích rút thực thể tên. Tận dụng
ưu điểm của các văn bản đã qua khâu phân đoạn từ, việc
xây dựng hệ thống trích rút thực thể tên đỡ phức tạp hơn
rất nhiều. Hệ thống trích rút thực thể tên sẽ tập trung vào
khâu nhận biết thực thể qua các tiền tố và tiến hành trích
rút.
20
Bước 2: Kiểm tra ký tự đầu tiên của xâu ký tự được
kỳ vọng là thực thể tên có phải là chữ hoa hay không.
Bước 3: Kiểm tra xâu ký tự tìm được có trùng với
các xâu ký tự trong bảng tblNotPattern hay không.
Bước 4: Kiểm tra xâu ký tự so khớp tìm được đã có
trùng với kết quả ở các bước lặp trước hay không.

Snowball sẽ tính độ chính xác của từng mẫu dựa
trên số Positive và Negative của nó và chọn ra top N mẫu
có điểm số cao nhất.

Bước 2: Tìm các seed mới cho vòng lặp tiếp theo.
Với mỗi mẫu trong danh sách top N được chọn sẽ
là các cặp trong tập seed mới được đưa vào vòng lặp mới.
10
Hệ thống sẽ chọn ra được m cặp được đánh giá tốt
nhất dùng làm seed cho quá trình rút mẫu kế tiếp.
Hệ thống tiếp tục quay lại bước một. Quá trình trên
lặp cho đến khi hệ thống không tìm được cặp mới hoặc lặp
theo số lần mà ta xác định trước.
1.3.3. Phương pháp KnowItAll
Phương pháp KnowItAll tiến hành trích rút ra
những sự vật, khái niệm và các mẫu quan hệ từ các trang
web. KnowItAll được mở rộng từ một ontology và dựa
vào một tập các luật để từ đó trích rút ra các luật cho mỗi
lớp và các quan hệ trong ontology [4].
Đầu vào của KnowItAll là một tập các lớp thực thể
được trích xuất, kết quả là một danh sách các thực thể
được trích xuất từ các trang web. Các mẫu sử dụng đã
được gán nhãn bằng tay, những mẫu này được xây dựng
dựa vào việc tách cụm danh từ (Noun Phrase chunker).
1.4. Tổng kết chương
Phương pháp KnowItAll sử dụng các kĩ thuật xử lý
ngôn ngữ (phân tích cú pháp, tách cụm danh từ) nên khó
áp dụng cho tài liệu tiếng Việt vì đối với ngôn ngữ tiếng
Việt, các kĩ thuật xử lý ngôn ngữ, tài nguyên ngôn ngữ học
19

Ta cần tách xâu ký tự nhận được thỏa mãn các điều
kiện kiểm tra để lấy thực thể tên cần trích rút.
* Filter_Entities
Tập thực thể tên sau khi được trích rút sẽ được ánh
xạ ngược trở lại văn bản ở bước lặp tiếp theo để tìm sự
xuất hiện (Occurrences).
* Find_PrefixStrings
Hệ thống tìm kiếm các tiền tố (PrefixString) mới của
thực thể tên đã tìm thấy ở bước trước.
* Generate_NewPrefixPattern
Thủ tục Generate_NewPrefixPattern sinh ra
NewPrefixPattern từ tập PrefixStrings đã được trích rút ở
bước trước để trích rút những thực thể mới.
11
cũng như các kĩ thuật học máy đã xây dựng nhưng chưa
đưa ra được kết quả tốt nhất. SnowBall đưa ra phương
pháp tìm kiếm, trích chọn và đánh giá độ tin cậy của seed
mới và mẫu mới được sinh ra. Vì thế, tập dữ liệu mới
(mẫu quan hệ và tập seed mới) được sinh ra có độ tin cậy
cao, chính xác từ những dữ liệu nhỏ ban đầu.
Dựa vào ưu và nhược điểm của từng phương pháp,
hệ thống xây dựng trong phần demo sẽ sử dụng giải thuật
DIPRE kết hợp với phương pháp SnowBall. Tuy nhiên,
các phương pháp này đều yêu cầu phải tiến hành bước
nhận dạng các thực thể, đây là một bước bắt buộc để đảm
bảo quá trình sinh tập seed mới cũng như việc trích rút ra
được các mẫu có độ chính xác cao.
12
CHƯƠNG II: PHƯƠNG PHÁP TRÍCH
RÚT THỰC THỂ TÊN

ngay sau tiền tố của so khớp tìm được xem đó có phải là
ký tự viết hoa không. Nếu kết quả của quá trình kiểm tra là
false thì hệ thống sẽ quay lại tìm PrefixPattern tiếp theo
trong tblPattern để tiếp tục tìm kiếm các thực thể tên khác.
Thủ tục Find_IndexsOfPrefixPattern với tham số đầu
vào PrefixPattern sẽ tìm các xâu khớp (match) với
PrefixPattern, kết quả thu được là các xâu chứa tiền tố
xuất hiện trong văn bản.
* Extract_CandidateStrings
Xét mỗi so khớp tìm được, xâu con đứng ngay sau
tiền tố được mong đợi sẽ là một tên thực thể. Điều kiện:
16
Từ PrefixStrings sinh ra các mẫu mới.
7) Quy lại bước 1 với NewPrefixPattern vừa được
sinh ra và bắt đầu một bước lặp mới.

Hình 2.2 Mô hình bài toán
Các mục dưới đây sẽ giải thích rõ ràng hơn.
* Find_IndexsOfPrefixPattern
Ngữ cảnh của thực thể tên có nhiều điểm khác biệt
như:
- Đứng trước mỗi một thực thể tên thực thể thường là
các “tiền tố” có dạng đặc biệt hoặc nằm trong một miền
giá trị cụ thể.
13
tìm kiếm của hệ thống cần có sự can thiệp của các luật để
hạn chế sai sót trên. Chương trình dừng lại khi hệ thống
không tìm thêm được mẫu mới hoặc số lượng tên thực thể
trích rút bị sai quá nhiều.
Quy trình rút trích được mô tả như hình dưới đây :

động trích rút thực thể tên với một mẫu được xây dựng thủ
công
1) IndexsOfPrefixPattern 
Find_IndexsOfPrefixPattern (PrefixPattern)
15
Ánh xạ PrefixPattern vào tập tài liệu để xác định
các xâu mà mẫu này đoán nhận.
2) CandidateStrings  Extract_CandidateStrings
(Extract_CandidateStrings,
CandidateRegularExpression): Thu được xâu ký
tự được kỳ vọng là xâu có chứa thực thể tên.
3) Entities  Trim (CandidateStrings)
Hệ thống sẽ tiến hành tách xâu kỳ vọng (không bị
loại trong cơ sở dữ liệu) CandidateStrings để thu
được các thực thể (Entities) thích hợp.
4) RepresentativeEntities  Filter_Entities
(Entities)
Từ Entities chọn ra những thực thể đại diện.
5) PrefixStrings 
Find_PrefixStrings(RepresentativeEntities,
PrefixRegularExpression)
Sử dụng biểu thức chính quy
PrefixRegularExpression kết hợp với
RepresentativeEntities để đoán nhận “tiền tố” của
các RepresentativeEntities (PrefixStrings).
6) NewPrefixPattern  Generate_NewPrefixPattern
( PrefixStrings )