Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

MỤC LỤC
MỤC LỤC ................................................................................................................... 1
LỜI CAM ĐOAN ....................................................................................................... 3
LỜI CẢM ƠN ............................................................................................................. 4
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ....................................................... 5
DANH MỤC CÁC BẢNG.......................................................................................... 6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................................... 7
CHƯƠNG 1

MỞ ĐẦU .......................................................................................... 9

1.1

Lý do chọn đề tài ...........................................................................................9

1.2

Mục đích nghiên cứu .....................................................................................9

1.3

Nội dung nghiên cứu ...................................................................................10

1.4

Bố cục luận văn ...........................................................................................11

1.5

Các kết quả đạt được của luận văn .............................................................. 11

1.6

Ý nghĩa của luận văn ...................................................................................12

CHƯƠNG 2 KHÁI QT VỀ TRÍCH RÚT THƠNG TIN .................................... 13
2.1

Bài tốn trích rút thơng tin...........................................................................13

2.2

Trích rút thơng tin từ môi trường Web ........................................................14

2.2.1

Hệ thống KnowItAll ............................................................................. 16

2.2.2

Hệ thống TextRunner............................................................................ 26

2.2.3

So sánh KnowItAll và TextRunner ....................................................... 33

CHƯƠNG 3 MƠ TẢ BÀI TỐNVÀ PHƯƠNG PHÁP GIẢI QUYẾT.................. 35
3.1


Mơ tả bài tốn .............................................................................................. 35

3.1.1

u cầu trích rút thơng tin đối với các doanh nghiệp cung cấp dịch vụ

thương mại điện tử ............................................................................................. 35
3.1.2

u cầu trích rút thơng tin đối với người tiêu dùng thương mại điện tử
37

3.2

Phương pháp giải quyết ...............................................................................39

1


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

3.2.1

Trích rút thơng tin bán cấu trúc ............................................................ 40

3.2.2

Trích rút thơng tin phi cấu trúc ............................................................. 43

CHƯƠNG 4


THIẾT KẾ VÀ XÂY DỰNG HỆ THỐNGTRÍCH RÚT VÀ ỨNG

DỤNG VÀO CÁC DỊCH VỤ DỰA TRÊN GIÁ ..................................................... 48
4.1

Thiết kế hệ thống .........................................................................................48

4.1.1

Kiến trúc hệ thống................................................................................. 48

4.1.2

Nền tảng công nghệ .............................................................................. 51

4.2

Chức năng hệ thống .....................................................................................53

4.2.1

Phân hệ trích rút thông tin..................................................................... 54

4.2.2

Phân hệ FrontEnd.................................................................................. 54

4.2.3


Phân hệ BackEnd .................................................................................. 62

4.2.4

Phân hệ Mobile ..................................................................................... 64

4.3

Đánh giá kết quả trích rút ............................................................................66

CHƯƠNG 5 KẾT QUẢ VÀ BÀN LUẬN ............................................................. 67
5.1

Các kết quả đạt được trong luận văn ...........................................................67

5.1.1

Về lý thuyết ........................................................................................... 67

5.1.2

Về thực nghiệm ..................................................................................... 67

5.2

Hướng nghiên cứu tiếp ................................................................................68

KẾT LUẬN VÀ KIẾN NGHỊ................................................................................... 69
TÀI LIỆU THAM KHẢO ......................................................................................... 70


2


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

LỜI CAM ĐOAN
Tôi xin cam đoan, luận văn tốt nghiệp Thạc sỹ này là cơng trình nghiên cứu
của bản thân tôi dưới sự hướng dẫn của PGS. TS. Lê Thanh Hương. Các kết quả trong
luân văn tốt nghiệp là trung thực, khơng phải sao chép tồn văn của bất kỳ cơng trình
nào khác. Tơi xin chịu hoàn toàn trách nhiệm về nội dung quyển luận văn này.

Tác giả

Nguyễn Hồng Nghi

3


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

LỜI CẢM ƠN
Luận văn được hoàn thành tại trường Đại học Bách khoa Hà Nội. Để hoàn
thành luận văn này, tác giả đã nhận được sự chỉ bảo tận tình, cùng những yêu cầu
nghiêm khắc của PGS.TS. Lê Thanh Hương, người đã truyền đạt rất nhiều kiến thức
quí báu cũng như những kinh nghiệm nghiên cứu khoa học trong suốt thời gian tác
giả theo học và nghiên cứu.
Tác giả xin chân thành gửi lời biết ơn đến Ban lãnh đạo Viện Công nghệ thông
tin và Truyền thông, Viện Đào tạo Sau đại học và Bộ môn Hệ thống Thông tin, thuộc
trường Đại học Bách khoa Hà Nội đã tạo điều kiện thuận lợi trong quá trình học tập,
nghiên cứu và hoàn thành luận văn.

Với năng lực hạn chế của bản thân cũng như những nguyên nhân chủ quan,
khách quan, luận văn khơng tránh những thiếu sót. Tác giả rất mong được sự góp ý
của quý thầy cô, các bạn bè và đồng nghiệp để luận văn được hoàn thiện hơn.

Tác giả

Nguyễn Hồng Nghi

4


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT

Ký hiệu

Ý nghĩa

IE

Information Extraction – Trích rút thơng tin

CSDL

Cơ sở dữ liệu

WIE

Web Information Extraction – Trích rút thơng tin từ môi trường

Web

PMI-IR

Pointwise Mutual Information for Information Retrieval

OIE

Open Information Extraction – Trích rút thơng tin mở

NBC

Nạve Bayes Classifier – Bộ phân loại Nạve Bayes

RE

Regular Expression – Biểu thức chính quy

SOA

Service Oriented Architect – Kiến trúc hướng dịch vụ

5


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

DANH MỤC CÁC BẢNG
Bảng 1 Giả ngơn ngữ của KnowItAll .......................................................................18
Bảng 2 Một luật trích rút tạo bởi thay tên lớp “Thành-Phố” và số nhiều của lớp có

nhãn “thành phố” thành một mẫu luật chung. ...........................................................19
Bảng 3 Ví dụ các vị từ cho lĩnh vực địa lý và lĩnh vực phim. ..................................21
Bảng 4 Tám mẫu trích rút chung sử dụng cho các luật trích rút đơn, hai mẫu cho mẫu
trích rút nhị phân .......................................................................................................22
Bảng 5 Một ví dụ của luật trích rút 2 ngơi để tìm CEO của một cơng ty .................24
Bảng 6 Ví dụ về đặc trưng sử dụng trong Bộ phân loại tự giám sát trong TextRunner
...................................................................................................................................30
Bảng 7 Ví dụ về các ràng buộc về đường trên cây cú pháp có thể trích rút quan hệ 31
Bảng 8 Mười vị từ sử dụng trong so sánh KnowItAll và TextRunner .....................33
Bảng 9 So sánh kết quả thử nghiệm giữa TextRunner và KnowItAll ......................34
Bảng 10 Kết quả trích rút ..........................................................................................66

6


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 1 Mơ hình trích rút thơng tin ............................................................................14
Hình 2 Biểu đồ trình tự của các thành phần trong KnowItAll ..................................17
Hình 3 Trình tự xử lý của các thành phần trong TextRunner ...................................29
Hình 4 Mơ hình nghiệp vụ theo dõi giá truyền thống của các doanh nghiệp thương
mại điện tử .................................................................................................................36
Hình 5 Nhu cầu giải quyết bài tốn của doanh nghiệp .............................................37
Hình 6 Nhu cầu theo dõi giá của người tiêu dùng ....................................................38
Hình 7 Nhu cầu của người tiêu dùng về thơng tin giá ..............................................39
Hình 8 Thơng tin trên trang Web của một doanh nghiệp thương mại điện tử ..........41
Hình 9 Cơng cụ biểu thức chính quy RegexBuddy ..................................................42
Hình 10 Trích rút thơng tin giá bằng OIE .................................................................43

Hình 11 Q trình tiền xử lý .....................................................................................44
Hình 12 Bộ trích rút duyệt một lần ...........................................................................45
Hình 13 Bộ phân loại tự giám sát..............................................................................46
Hình 14 Bộ đánh giá dựa trên dư thừa ......................................................................46
Hình 15 Lịch sử phát triển của kiến trúc ứng dụng...................................................48
Hình 16 Kiến trúc hệ thống .......................................................................................49
Hình 17 Mơ hình triển khai hệ thống ........................................................................50
Hình 18 Nền tảng cơng nghệ của hệ thống ............................................................... 51
Hình 19 Chức năng của hệ thống ..............................................................................53
Hình 20 Đăng ký tài khoản chính thức trên hệ thống ...............................................55
Hình 21 Đăng nhập vào hệ thống ..............................................................................55
Hình 22 Trang chủ của hệ thống ...............................................................................56
Hình 23 Thơng tin sản phẩm .....................................................................................56
Hình 24 Thơng tin sản phẩm và biểu đồ so sánh giá các nhà cung cấp ....................57
Hình 25 Thơng tin sản phẩm và biểu biến động giá của các nhà cung cấp ..............57
Hình 26 Gian hàng ảo của một nhà cung cấp ...........................................................58

7


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

Hình 27 Bản đồ các nhà cung cấp trên hệ thống .......................................................58
Hình 28 Diễn đàn trao đổi thơng tin .........................................................................59
Hình 29 Thơng tin trong một topic của diễn đàn ......................................................59
Hình 30 Quản lý thơng tin tài khoản cá nhân ...........................................................60
Hình 31 Đăng ký nhận biến động giá của sản phẩm.................................................61
Hình 32 Bảng quản lý của doanh nghiệp ..................................................................62
Hình 33 Phân hệ BackEnd ........................................................................................63
Hình 34 Cấu hình thơng tin sản phẩm.......................................................................64

Hình 35 Thơng tin về các đợt giảm giá .....................................................................65
Hình 36 Xem thơng tin chi tiết sản phẩm .................................................................65
Hình 37 Tìm sản phẩm giá tốt nhất ...........................................................................65
Hình 38 Tích hợp với mạng xã hội Facebook ...........................................................65

8


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

CHƯƠNG 1 MỞ ĐẦU

1.1 Lý do chọn đề tài
Trong những năm qua, các nghiên cứu về trích rút thơng tin từ mơi trường
Web đã đạt được nhiều thành tựu đáng kể. Sự ra đời của hàng loạt các phương pháp
trích rút đã mở ra cơ hội cũng như thách thức cho việc phát triển các hệ thống ứng
dụng cho bài toán cụ thể. Đặc biệt, chúng mở ra cơ hội để tạo ra các hệ thống dựa
trên tri thức (knowledge-based) mà độc lập với miền tri thức. Tuy nhiên, điều này
cũng đặt ra nhiều thử thách kỹ thuật để có thể vượt qua.
Trong thời đại bùng nổ về cơng nghệ thơng tin nói chung và thương mại điện
tử nói riêng, hàng loạt các trang web, diễn đàn thương mại điện tử được mở ra với số
lượng ngày một tăng. Trước một lượng dữ liệu khổng lồ về thông tin giá cả của các
sản phẩm, người tiêu dùng rất khó khăn để lựa chọn được một sản phẩm với giá cả
tốt nhất trong hàng loạt các trang web, diễn đàn như vậy. Bên cạnh đó, các doanh
nghiệp cũng tốn rất nhiều thời gian, công sức và tiền bạc trong việc theo dõi thông
tin giá cả biến động không ngừng của đối thủ cạnh tranh để đưa ra chiến lược giá cho
doanh nghiệp mình nhằm nâng cao vị thế cạnh tranh.
Thông tin về giá cả của mỗi trang web, diễn đàn được tổ chức đa dạng từ có
cấu trúc, bán cấu trúc đến cả phi cấu trúc, việc thu thập thông tin giá cả này một cách
tự động là khá khó khăn với doanh nghiệp cũng như người tiêu dùng. Đứng trước

thực trạng đó, tác giả đã chọn đề tài này với mong muốn nghiên cứu, xây dựng một
giải pháp trích rút thơng tin giá cả cho các dịch vụ thương mại điện tử dựa trên thông
tin giá.
1.2 Mục đích nghiên cứu
Thơng qua nghiên cứu đề tài “Ứng dụng trích rút thơng tin trong xây dựng các
dịch vụ dựa trên giá”, tác giả mong muốn đạt được kết quả:

9


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

 Nghiên cứu các phương pháp trích rút thơng tin nói chung và trích rút
thơng tin từ mơi trường Web nói riêng và từ đó lựa chọn một phương
pháp phù hợp với bài toán.
 Xây dựng một giải pháp trích rút thơng tin giá từ các trang Web, diễn
đàn thương mại điện tử.
 Xây dựng một giải pháp cho người tiêu dùng có thể dễ dàng lựa chọn
được các sản phẩm quan tâm với giá tốt nhất. Bên cạnh đó, cung cấp
các dịch vụ tiện ích khác dựa trên thông tin giá cả này.
 Xây dựng một giải pháp cho doanh nghiệp thương mại điện tử có thể
dễ dàng theo dõi biến động giá cả của các đối thủ, nhà cung cấp khác
để hỗ trợ doanh nghiệp đưa ra một chiến lược giá cạnh tranh.
Đối tượng nghiên cứu của đề tài là bài tốn trích rút thơng tin đối với dữ liệu
có cấu trúc, bán cấu trúc cũng như phi cấu trúc.
Phạm vi nghiên cứu của luận văn là tập trung vào việc trích rút thực thể và
quan hệ giữa chúng (quan hệ giá cả) từ văn bản phi cấu trúc thuộc lĩnh vực thương
mại điện tử trên môi trường Web. Các tập dữ liệu thử nghiệm được thu thập từ các
trang web, diễn đàn thương mại điện tử. Do kết quả của việc xử lý ngôn ngữ Tiếng
Việt đã đạt được nhiều thành tựu với độ chính xác cao, nên tác giả sẽ sử dụng lại kết

quả của một số tác giả trong các vấn đề liên quan.
1.3 Nội dung nghiên cứu
Trong luận văn này, tác giả nghiên cứu 2 phương pháp trích rút thơng tin từ
môi trường Web như: phương pháp KnowItAll; phương pháp TextRunner. Trong đó,
tập trung nghiên cứu kỹ về phương pháp TextRunner để ứng dụng vào bài tốn trích
rút thơng tin giá.
Bên cạnh đó, tác giả cũng nghiên cứu về kiến trúc, mơ hình hệ thống, phương
pháp kỹ thuật để xây dựng được hệ thống khai thác thông tin giá.

10


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

1.4 Bố cục luận văn
Luận văn được bố cục thành các chương sau:
 Chương I. Khái qt về trích rút thơng tin
Chương này tác giả sẽ giới thiệu về các khái niệm cơ bản trong trích rút
thơng tin và một số phương pháp trích rút thơng tin từ môi trường Web
hiện nay và lựa chọn phương pháp phù hợp.
 Chương II. Mơ hình bài tốn và phương pháp giải quyết
Trong chương này, tác giả sẽ mô hình hóa các u cầu của bài tốn và
phương pháp luận để giải quyết vấn đề.
 Chương III. Thiết kế và xây dựng hệ thống trích rút và ứng dụng vào các
dịch vụ dựa trên giá
Trong chương này, tác giả sẽ mô tả thiết kế và xây dựng cho bài tốn trích
rút thơng tin cũng như việc khai thác thơng tin giá này cho các dịch vụ dựa
trên giá.
 Chương IV. Kết quả và bàn luận
Nêu lên một số kết quả đạt được của sản phẩm, một số bàn luận.

1.5 Các kết quả đạt được của luận văn
Luận văn đã được một số kết quả như sau:
 Về bài toán trích rút thơng tin
-

Nghiên cứu các phương pháp trích rút thơng tin, đặc biệt là các phương pháp
trích rút thơng tin từ môi trường Web và ứng dụng phương pháp Open
Information Extraction trong việc trích rút thơng tin từ nguồn dữ liệu phi cấu
trúc.

-

Ứng dụng của phương pháp Open Information Extraction trong bài tốn trích
rút thơng tin giá cả từ các trang web, diễn đàn thương mại điện tử.

 Về xây dựng hệ thống hỗ trợ các dịch vụ dựa trên giá

11


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

-

Xây dựng hệ thống cho người tiêu dùng dễ dàng lựa chọn được sản phẩm có
giá tốt, cũng như các tiện ích để việc mua hàng hóa được thuận tiện và hiệu
quả hơn.

-


Xây dựng hệ thống cho doanh nghiệp thương mại điện tử theo dõi được biến
động giá của các đối thủ để đưa ra chiến lược giá mang tính cạnh tranh.

1.6 Ý nghĩa của luận văn
Với kết quả đã đạt được, luận văn đã mang lại một số kết quả nghiên cứu nhất
định trong việc trích rút thơng tin từ các trang web, diễn đàn và đặc biệt là nghiên cứu
và ứng dụng phương pháp Open Information Extraction trong việc giải quyết bài toán
cụ thể. Bên cạnh đó, cũng mở ra hướng nghiên cứu về việc ứng dụng phương pháp
này trong việc trích rút các thông tin khác từ Internet.
Đồng thời, luận văn cũng cung cấp cho người tiêu dùng cũng như các doanh
nghiệp thương mại điện tử một hệ thống hỗ trợ trong việc mua, bán mang lại hiệu quả
hơn.

12


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

CHƯƠNG 2 KHÁI QUÁT VỀ TRÍCH RÚT THƠNG TIN

Trong chương này, luận văn sẽ trình bày các kiến thức cơ bản về trích rút thơng
tin bao gồm: khái niệm về trích rút thơng tin; trích rút thực thể; trích rút mối quan hệ
giữa các thực thể; và các phương pháp trích rút thơng tin mới từ mơi trường Web.
2.1 Bài tốn trích rút thơng tin
Hiện nay, có rất nhiều định nghĩa về trích rút thơng tin, trên cơ sở nghiên cứu
các nghiên cứu liên quan[5], có thể định nghĩa “Trích rút thơng tin” (IE - Information
Extraction) là quá trình phát hiện các thực thể/tên, các mối quan hệ và các sự kiện từ
văn bản bán có cấu trúc, bán cấu trúc hay phi cấu trúc; và chuyển chúng sang dạng
thể hiện có cấu trúc (VD: cơ sở dữ liệu).
Việc trích rút ra các thơng tin có cấu trúc từ các nguồn dữ liệu (có nhiễu và

phi cấu trúc) là một cơng việc rất khó khăn, thu hút được sự quan tâm của cộng đồng
các nhà nghiên cứu trong hai thập kỉ qua. Bắt nguồn từ cộng đồng các nhà xử lý ngôn
ngữ tự nhiên, IE đã nhanh chóng được quan tâm chú ý bởi những cộng đông nghiên
cứu khác nhau về học máy, truy vấn thông tin, cơ sở dữ liệu, Web, và phân tích văn
bản. Hai hội nghị quan trọng đối với các nghiên cứu về trích rút thơng tin là: Message
Understanding Conference (MUC) và Automatic Content Extraction (ACE).
Có nhiều mức độ trích rút thơng tin từ văn bản như: trích rút các thực thể
(Named Entity Recognition), trích rút quan hệ giữa các thực thể (Relation Extraction),
phân giải đồng tham chiếu (Co-reference Resolution)… Các kĩ thuật được sử dụng
trong trích rút thơng tin gồm có: phân đoạn, phân lớp, kết hợp và phân cụm.
IE có nhiều ứng dụng rộng rãi và hữu ích. Trên thế giới, IE được ứng dụng
khá nhiều vào việc trích rút thông tin trên Internet. Các ứng dụng thực tế bao gồm:
lấy thông tin về tên của các công ty, tên người điều hành công ty, theo dõi thông tin
về các dịch bệnh, theo dõi các sự kiện khủng bố… IE cịn được ứng dụng vào việc
chăm sóc khách hàng, đó là việc tìm kiếm và trích rút ra các thơng tin của khách hàng

13


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

như: họ tên, địa chỉ, email, số điện thoại rồi lưu vào cơ sở dữ liệu (CSDL) hay phục
vụ các hệ thống quản lý thông tin cá nhân. Gần đây IE đặc biệt được chú trọng trong
lĩnh vực y học. Đã có khá nhiều nghiên cứu được tiến hành nhằm ứng dụng IE vào
việc trích rút các thực thể trong ngành y, như tên các protein và gene.
Theo[1], hệ thống trích rút thơng tin có các thao tác chính như sau

Hình 1 Mơ hình trích rút thơng tin
Chương này, sẽ trình bày về một số phương pháp trích rút và lựa chọn phương
pháp phù hợp cho bài tốn của luận văn.

2.2 Trích rút thơng tin từ môi trường Web
Trong vài năm gần đây các nhà nghiên cứu đã trích rút được số lượng lớn
thơng tin từ các dữ liệu văn bản trên môi trường Web. Các hệ thống mới như
KnowItAll, KnowItNow, TextRunner, và một số hệ thống khác đã chứng minh được
khả năng xử lý lượng lớn dữ liệu một cách hiệu quả. Số lượng lớn tri thức tạo ra bởi
các hệ thống này đã mở ra nhiều cơ hội và thách thức. Đặc biệt, chúng mở ra cơ hội
để tạo ra các hệ thống dựa trên tri thức (knowledge-based) mà độc lập với miền tri
thức. Tuy nhiên, điều này cũng đặt ra nhiều thử thách kỹ thuật để có thể vượt qua.
Thứ nhất, thơng tin được trích rút ra chỉ là một phần trong việc hướng tới cách thức
xử lý được hoàn toàn bởi máy tính, cần nhiều nghiên cứu để chuyển dữ liệu văn bản
14


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

sang dạng biểu diễn logic của tri thức. Thứ hai, xây dựng một hệ thống dựa trên tri
thức sử dụng trích rút thơng tin u cầu cái nhìn tổng thể về việc tích hợp các tri thức
trích rút được từ các hệ thống phức tạp. Thứ ba, cần thiết xây dựng các giải pháp linh
hoạt để xử lý lượng lớn của tri thức. Luận văn này nghiên cứu một số phương pháp
để tiếp cận và vượt qua các thử thách này.
Trích rút thơng tin là q trình thu nhận các thơng tin có cấu trúc từ văn bản
phi cấu trúc. Các hệ thống trích rút thơng tin từ môi trường Web (WIE - Web
Information Extraction) khác với các hệ thống truyền thổng ở cả phương pháp và mục
đích. Trong khi các hệ thống trích rút thơng tin truyền thống tập trung vào việc xiết
chặt đến mức có thể từ tập dữ liệu nhỏ, thì các hệ thống WIE tập trung vào trích rút
thơng tin độc lập với miền tri thức từ các câu tương đối đơn giản, và dựa vào sự dư
thừa của môi trường Web để cung cấp lượng lớn thông tin.
Các hệ thống WIE đối diện với nhiều thử thách mới do phải xử lý với quy mô
lớn của môi trường Web một cách hiệu quả. Trên mơi trường này, do có rất nhiều
người cung cấp thông tin, nên các hệ thống WIE phải giải quyết được ràng buộc về

các kiểu khác nhau của ngơn ngữ mà có thể là ngun nhân làm nhiều công cụ xử lý
ngôn ngữ bị giảm hiệu năng. Và hầu hết các nghiên cứu về trích rút thơng tin dựa vào
việc trích rút các trường hợp mà có tập vị từ thường dùng và phụ thuộc vào miền tri
thức. Để đạt được việc độc lập với miền tri thức, và có thể trích rút thơng tin từ các
văn bản tùy ý trên môi trường Web, các hệ thống WIE phải làm cách nào đó giảm
thiếu và loại trừ số lượng lớn đầu vào mà yêu cầu trên mỗi miền tri thức hoặc vị từ.
Có một số phương pháp giúp cho việc tạo ra hệ thống WIE như vậy khả thi và
thực tế hơn. Turney [2] là người đầu tiên nhận ra rằng các máy tìm kiếm Web (search
engine) cung cấp các bộ đếm hitcount cho việc tính tốn thống kê mà tốn chi phí rẻ
bằng mơ hình PMI-IR (Pointwise Mutual Information for Information Retrieval). Hệ
thống KnowItAll trích rút các thể hiện của bất kỳ lớp nào từ môi trường Web, sử dụng
thống kê PMI-IR làm bằng chứng cho việc xác nhận trích rút.
Hearst là người tiên phong trong việc sử dụng các mẫu chung trong việc trích
rút thơng tin[4]. Từ đó, nhiều hệ thống cải tiến các khái niệm cơ bản của các trích rút

15


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

dựa trên mẫu bằng cách nâng cấp lên môi trường Web và học các mẫu mới sử dụng
q trình trích rút. Cách thức học này được gọi là bootstrapping, có thể nâng cao tính
triệu hồi (recall) của các hệ thống trích rút và thiết lập chúng chuyên biệt cho vùng
tri thức.
Bootstrapping có thể giúp giảm chi phí của trích rút thơng tin cho vùng tri thức
mới bằng cách tự động tạo và học mẫu mới đối với các quan hệ trong vùng tri thức,
nhưng nó khơng thể xác định các mối quan hệ. Các hệ thống cao cấp khác của WIE
thực hiện Trích rút thơng tin mở (OIE – Open Information Extraction) [6] theo cách
tất cả các quan hệ có khả năng được trích rút ra từ dữ liệu như là một trường hợp của
quan hệ. Cách thức này nâng câp tốc độ của WIE và quy mô của đầu ra.

Phần tiếp theo sẽ mô tả hai hệ thống WIE, là KnowItAll và TextRunner là 2
phương pháp mới và hiệu quả hiện nay.
2.2.1

Hệ thống KnowItAll
Trích rút thơng tin là thực hiện trích rút tự động tri thức từ văn bản. Trích rút

thơng tin khơng giám sát không cần thiết phải gán nhãn dữ liệu đào tạo thủ cơng. Bởi
vì các hệ thống trích rút khơng giám sát không yêu cầu sự can thiệp của nhân công,
chúng có thể tự phát hiện quan hệ, thuộc tính và thể hiện mới một cách tự động và
linh hoạt. KnowItAll là hệ thống không giám sát, độc lập miền tri thức có thể trích
rút thơng tin từ mơi trường Web như vậy.
Thu thập một lượng lớn thông tin bằng cách tìm kiếm trên Web có thể là một
q trình thủ công, buồn tẻ. Việc thu thập một cách đầy đủ, tồn vẹn là khá khó khăn
trừ khi ta có các tài liệu chuẩn hoặc một cơ sở dữ liệu mới có thể giảm thiểu được lỗi.
Một trong các mục đích của KnowItAll là giải quyết bài tốn tích lũy các thu thập lớn
vềcác thể hiện. Dưới đây là biểu đồ trình tự của các thành phần trong KnowItAll:

16


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

Hình 2 Biểu đồ trình tự của các thành phần trong KnowItAll
Bootstrapping của KnowItAll sử dụng một tập các mẫu trích rút độc lập với
miền tri thức để tạo ra các luật trích rút và bộ phân tách với mỗi vị từ mà nó quan
tâm. Bootstrapping là tự động hoàn toàn, ngược với các phương pháp bootstrapping
khác yêu cầu tập các dữ liệu đào tạo thủ cơng.
Hai thành phần chính của KnowItAll là bộ trích rút (Extractor) và bộ đánh giá
(Assessor). Bộ trích rút tạo một câu truy vấn từ các từ khóa trong mỗi luật, rồi gửi

câu truy vấn tới máy tìm kiếm Web, và áp dụng luật để trích rút thơng tin từ kết quả
trả về của các trang Web. Bộ đánh giá tính tốn xác suất mà mỗi trích rút là chính xác
trước khi bổ sung trích rút vào nền tảng tri thức của KnowItAll. Bộ đánh giá dựa trên
tính tốn xác suất trên bộ đếm hitcount của máy tìm kiếm và sử dụng thuật toán PMIIR để đánh giá.

KNOWITALL(information focus I , rule templates T )
Bootstrap(I , T ) sets rules R, queries Q, and discriminators D
Do until queries in Q are exhausted (or other termination criterion)
Extractor(R, Q) writes extractions list E
Assessor(E, D) adds extractions to the knowledgebase

17


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

Extractor(rules R, queries Q)
Select queries from Q, set the number of downloads for each query
Send selected queries to search engines
For each webpage w whose URL was returned by a search engine
Extract fact e from w using the rule associated with the query
Write e to extractions list E

Assessor(extraction list E, discriminators D)
For each extraction e in E
Assign a probability p to e using a Bayesian classifier based on D
Add e,p to the knowledgebase
Bảng 1 Giả ngôn ngữ của KnowItAll
Bootstrapping tạo ra các luật và bộ phân tách với mỗi vị từ quan tâm.
KnowItAll tạo ra danh sách các câu truy vấn máy tìm kiếm tương ứng với các luật

trích rút và thực thi trong vịng lặp chính. Ở đầu mỗi vòng lặp, KnowItAll lựa chọn
các câu truy vấn, các vị từ hay dùng và các luật hiệu quả nhất trong các phép lặp trước
của vịng lặp chính. Bộ trích rút gửi các câu truy vấn đã chọn tới máy tìm kiếm và
trích rút thơng tin từ kết quả trả về của các trang Web. Bộ đánh giá tính tốn xác suất
mà mỗi trích rút là chính xác hay không và bổ sung vào nền tảng tri thức. Vòng lặp
này lặp cho đến khi tất cả các câu tri vấn được xử lý hết hoặc cho rằng không cịn kết
quả có giá trị.
2.2.1.1

Các luật trích rút và bộ phân loại
KnowItAll tự động tạo một tập các luật trích rút với mỗi vị từ. Mỗi luật bao

gồm một vị từ, một mẫu trích rút, các ràng buộc, liên kết và từ khóa. Vị từ cung cấp
tên quan hệ và tên lớp của mỗi tham số vị từ. Trong luật dưới đây, vị từ duy nhất là
“Thành-Phố”. Mẫu trích rút được ứng dụng vào một câu có một trình tự các xâu xen
kẽ và các khe (slot), trong đó mỗi khe tượng trưng một xâu trong câu. Luật có thể

18


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

thiết lập các ràng buộc trên khe, và có thể liên kết nó với một trong các tham số vị từ
như là 1 cụm được trích rút. Trong luật ví dụ ở dưới, mẫu trích rút bao gồm 3 phần
tử: một khe tên là NP1, một xâu ngữ cảnh “như là”, và một khe tên NPList2. Có một
ràng buộc ngụ ý trong các slot với tên NP<digit>. Chúng phải khớp với các các cụm
danh từ và tên của nó là NPList<digit> khớp với một danh sách các cụm danh từ đơn
giản. Tên slot của P<digit> có thể khớp với các cụm tùy ý.
Bộ trích rút sử dụng biểu thức chính quy trên các nhãn từ loại (part-of-speech)
từ bộ gán nhãn Brill để xác định các danh từ đơn giản và NPList. Đầu (head) của một

cụm danh từ nhìn chung là từ cuối của cụm. Nếu từ cuối là viết hoa, bộ trích rút tìm
kiếm bên trái là bắt đầu của danh từ riêng, dựa trên cú pháp chính tả. Ví dụ, câu
“Chuyến du lịch gồm các thành phố chính như là New York, trung tâm Los Angeles,
và Dallas”. Đầu của NP “các thành phố chính” chỉ là “các thành phố”, trong đó head
của “New York” là “New York” và head của “trung tâm Los Angeles” là “Los
Angeles”.
Vị từ:

“Thành-Phố”

Mẫu

NP1 “như là” NPList2

Ràng buộc:

Head(NP1)= “các thành phố”
properNoun(head(each(NPList2)))

Liên kết:

City(head(each(NPList2)))

Từ khóa:

“các thành phố như là”

Bảng 2 Một luật trích rút tạo bởi thay tên lớp “Thành-Phố” và số nhiều của
lớp có nhãn “thành phố” thành một mẫu luật chung.
Các ràng buộc của một luật có thể chỉ ra bên trong cụm khớp với khe, đầu của

mỗi cụm, hoặc đầu của mỗi cụm danh từ NP đơn giản trong khe NPList. Một trong
những kiểu của ràng buộc là một ràng buộc xâu chính xác, như là head(NP1)= “các
thành phố” trong luật ở bảng trên. Các ràng buộc khác có thể chi ra một cụm hoặc
đầu của nó phải theo mẫu chính tả của danh từ riêng hoặc của một danh từ chung.
Luật liên kết chỉ ra các khe nào hoặc các đầu của khe nào là được trích rút cho mỗi
thơng số của vị từ. Nếu liên kết có một khe NPList, một trích rút riêng biệt được tạo
19


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

ra cho mỗi cụm danh từ NP đơn giản trong danh sách mà thỏa mãn tất cả các ràng
buộc. Trong ví dụ luật trên, một trích rút được tạo với tham số Thành-Phố liên kết
với mỗi cụm danh từ NP đơn giản trong NPList2 mà thỏa mãn ràng buộc danh từ
riêng.
Phần cuối của luật là danh sách của các từ khóa mà được tạo từ xâu ngữ cảnh
và bất kỳ khe nào có một ràng buộc từ chính xác. Trong ví dụ trên, có một cụm từ
khóa đơn “các thành phố như là” mà nhận được từ khe NP1 và tuân thủ hoàn toàn
theo sau ngữ cảnh. Một luật có thể có nhiều cụm từ khóa nếu ngữ cảnh hoặc các khe
với ràng buộc xâu chính xác khơng phải tính từ.
KnowItAll sử dụng các từ khóa như là các câu truy vấn máy tìm kiếm, áp dụng
các luật vào các kết quả nhận được từ các trang Web, sau khi tìm các câu trong trang
mà chứa từ khóa. Bộ trích rút sử dụng các luật trích rút áp dụng vào các trang Web
và thực hiện phân tích cú pháp. Ngược lại, bộ đánh giá sử dụng bộ phân loại để áp
vào các dấu hiệu máy tìm kiếm. Những bộ phân loại này là tương tự với các luật trích
rút đơn giản mà khơng quan tâm tới cú pháp, dấu chấm câu, chữ viết hoa và cả dấu
hết câu, là các giới hạn khi sử dụng các truy vấn máy tìm kiếm thương mại. Mặt khác,
các bộ phân loại có giá trị tương đương khi ứng dụng các mẫu trích rút cùng lúc với
tập các trang Web được đánh chỉ mục bởi máy tìm kiếm.
Một bộ phân loại bao gồm một mẫu trích rút với các xâu ngữ cảnh xen kẽ và

các khe. Khơng có các ràng buộc rõ ràng hoặc ngụ ý trên các khe, và các mẫu khớp
với các trang Web mà các xâu và khe trực tiếp là tính từ, loại bỏ dấu chấm, dấu trăng,
và thẻ HTML.
2.2.1.2

Bootstrapping
Đầu vào của KnowItAll là một tập của các vị từ tượng trưng cho các lớp hoặc

mối quan hệ hoặc sở thích. Các vị từ cung cấp tên tượng trưng cho mỗi lớp (VD:
“Diễn-Viên-Phim”), và cũng cung cấp một hoặc nhiều nhãn cho mỗi lớp (VD: “diễn
viên” và “ngôi sao phim ảnh”). Những nhãn này là dạng bề ngồi của lớp có thể xuất
hiện trong các câu thực. Bootstrapping sử dụng các nhãn để thể hiện các luật trích rút
của vị từ từ các mẫu luật chung.

20


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

Vị từ: Thành-Phố

Vị từ: Phim

Nhãn: “thành phố”, “đô thị”

Nhãn: “phim”

Vị từ: Quốc-Gia

Vị từ: Diễn-Viên-Phim


Nhãn: “đất nước”, “quốc gia”, Nhãn: “diễn viên”, “ngôi sao điện
“nước”

ảnh”

Vị từ: Thủ-Đô-Của(Thành-Phố, Vị từ: Đóng-Phim(Diễn-Viên-Phim,
Quốc-Gia)

Phim)

Nhãn quan hệ: “đơ thị của”

Nhãn quan hệ: “đóng trong”, “ngơi
sao của”

Nhãn class-1: “thành phố”, “đơ Nhãn class-1: “diễn viên”, “ngôi sao
điện ảnh”

thị”

Nhãn class-2: “đất nước”, “quốc Nhãn class-2: “phim”
gia”, “nước”
Bảng 3 Ví dụ các vị từ cho lĩnh vực địa lý và lĩnh vực phim.
Đầu tiên Bootstrapping sử dụng một tập các mẫu trích rút chung độc lập với
miền tri thức (VD: Trong Bảng 1). Mẫu trong bảng 1 có thể tóm tắt lại ở dạng
<class1> “như là” NPList. Đó là, cho một câu bao gồm nhãn lớp theo sau đó là “như
là”, theo sau bởi một danh sách các cụm danh từ đơn giản, KnowItAll trích rút đầu
của mỗi cụm danh từ như là một ứng viên của lớp, sau khi kiểm tra thì đó là một danh
từ riêng.

Kết hợp mẫu này với vị từ Thành-Phố tạo ra 2 luật, một là nhãn lớp “thành
phố” và một luật tương tự cho nhãn “đô thị”. Các mẫu trích rút mang đặc tính hớp là:
“các thành phố như là” NPList
“các đô thị như là” NPList

21


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

Mỗi thể hiện của luật trích rút có một danh sách các từ khóa được gửi tới các
thuật ngữ truy vấn với máy tìm kiếm. Một ví dụ của mẫu cú pháp dưới các mẫu luật
KnowItAll được thể hiện dưới bảng dưới. Một số mẫu luật được điều chỉnh từ mẫu
của Marti Hearst và một số người khác được phát triển độc lập. Tám mẫu đầu tiên
bên dưới là các vị từ mà tên số nhiều của nó khớp với <class1>. Để thể hiện các luật,
nhãn lớp số nhiều được tự động thay cho <class1>, tạo các mẫu như “các thành phố
như là” NPList.
NP “và” <class1>
NP “hoặc” <class1>
<class1> “đặc biệt là” NPList
<class1> “bao gồm” NPList
<class1> “như là” NPList
“<class1> “chứa” NPList
NP “là một” <class1>
NP “là” <class1>
<class1> “là” <relation><class2>
<class1> “,” <relation><class2>
Bảng 4 Tám mẫu trích rút chung sử dụng cho các luật trích rút đơn, hai mẫu
cho mẫu trích rút nhị phân
Chúng ta ví dụ với các mẫu luật cho vị từ nhị phân. Có vị từ chung,

relation(Class1, Class2). Đầu tiên tạo mẫu <Thành-Phố> “là thành phố của”<QuốcGia> cho vị từ capitalOf(Thành-Phố,Quốc-Gia) và mẫu <Người> “là Tổng giám đốc
của” <company> cho vị từ CeoOf(Người, Côngty).
Bootstrapping cũng khởi tạo Bộ đánh giá cho mỗi vị từ một cách tự động hồn
tồn. Đầu tiên nó tạo ra tập các cụm phân loại cho vị từ dựa vào nhãn lớp và các từ
khóa trong các luật trích rút của vị từ đó. Sau đó, Bootstrapping sử dụng các luật trích
rút để tìm tập các thể hiện để đào tạo các bộ phân loại cho mỗi vị từ đó.

22


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

2.2.1.3

Bộ trích rút
Xem xét xử lý của các luật trích rút trong KnowItAll, giả sử <class1> trong

mẫu
<class1> “như là” NPList
là ràng buộc tên của lớp trong ontology. Sau đó với mỗi cụm danh từ đơn giản trong
NPList giống như là một thể hiện của lớp đó. Khi mẫu này được dùng cho lớp QuốcGia nó sẽ khớp với câu mà bao gồm cụm “các quốc gia như là X, Y, và Z” trong đó
X, Y, và Z là tên của quốc gia. Các mẫu tương tự được dùng để tạo ra các luật để tìm
các thể hiện của các lớp Diễn-Viên, trong đó các luật tìm kiếm “các diễn viên như
làX, Y và Z”.
Bằng cách sử dụng các nguyên mẫu như là nền tảng cho các mẫu luật trích rút,
chúng ta bổ sung các ràng buộc cú pháp để tìm kiếm các cụm danh từ NP dưới dạng
cụm danh từ đơn giản; NPList phải là danh sách các NPs; và biểu trưng cho <class1>
là cụm danh từ đơn giản với tên lớp ở đầu. Các luật tìm kiếm tên riêng cũng bao gồm
các ràng buộc về chính tả. Để xem tại sao phân tích cụm danh từ là cần thiết, ta so
sánh 2 câu sau:

A) “Việt nam là nước nằm trong Châu Á.”
B) “Lavie là nước khoáng tự nhiên.”
Trong câu A từ “nước” là đầu của một cụm danh từ (Châu Á), và Việt nam là
thể hiện của lớp Quốc-Gia. Trong câu B, phân tích cụm danh từ có thể phát hiện ra
“nước” khơng phải là đầu của một cụm danh từ, nên Laive sẽ không được trích rút
thành tên của một quốc gia.
Chúng ta xem xét mẫu luật trong Bảng 1 và xem cách thức tạo ra một thể hiện
của một lớp cụ thể. Module Bootstrapping tạo ra một luật của lớp Thành-Phố từ mẫu
này bằng cách thay thế “Thành-Phố” cho “Class1”. Bootstrapping cũng tạo ra các
luật tương tự với “các đô thị” như là ràng buộc với NP1, nếu vị từ chỉ ra “đô thị”
cũng như “thành phố” như là dạng bề ngoài tương ứng với tên lớp. Sau đó,
Bootstrapping lấy một số luật và tạo thành một tập các từ khóa để Bộ phân loại gửi

23


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

tới một máy tìm kiếm như là một câu truy vấn. Trong trường hợp này, truy vấn tìm
kiếm là cụm từ “các thành phố như là”.
Bộ phân loại khớp với luật trong Bảng 1 với các câu trong các trang Web trả
về từ câu truy vấn. NP1 khớp với một cụm danh từ đơn giản; nó phải theo sau bởi
xâu “như là”; tiếp sau phải là danh sách các cụm danh từ NP đơn giản. Nếu khớp
thành công, Bộ phân loại áp dụng các ràng buộc từ các luật. Đầu của NP1 phải khớp
với xâu “các thành phố”. Bộ phân loại kiểm tra đầu của mỗi NP trong danh sách
NPList2 có theo mẫu viết hoa của danh từ riêng hay không. Bất kỳ NPs mà không
phù hợp với điều kiện này sẽ bị bỏ qua. Nếu tất cả các ràng buộc là khớp, Bộ phân
loại tạo ra một hoặc nhiều trích rút: một thể hiện của lớp Thành-Phố cho mỗi danh từ
riêng trong NPList2.
Các luật trong Bảng 1 sẽ trích rút ba thể hiện của lớp Thành-Phố từ câu “Chúng

tôi cung cấp dịch vụ cho các khách hàng ở các các thành phố như là London, Paris
và Berlin.” Nếu tất cả việc kiểm tra cho danh từ riêng thất bại, sẽ khơng có gì được
trích rút như là trong câu “Bản đồ và thông tin chi tiết của các thành phố như là bản
đồ đường xá, sơng ngịi”.
Bộ trích rút sử dụng các luật cho các mối quan hệ 2 ngôi hoặc n ngôi, bảng
dưới cho thấy một luật tìm kiếm các thể hiện của quan hệ CeoOf(Người, Cơngty)
trong đó vị từ chỉ ra một hoặc nhiều nhãn của quan hệ này, như là “Tổng giám đốc
của” được thay vào mẫu chung trong mẫu luật
<class1> “,” <realtion><class2>
Vị từ:

CeoOf(Người,Côngty)

Mẫu:

NP1 “,” P2 NP3

Ràng buộc:

properNoun(NP1)
P2 = “Tổng giám đốc của”
NP3 = ”VNPT”

Liên kết:

CeoOf(NP1,NP3)

Từ khóa:

“Tổng giám đốc của VNPT”


Bảng 5 Một ví dụ của luật trích rút 2 ngơi để tìm CEO của một cơng ty

24


Ứng dụng trích rút thơng tin trong xây dựng các dịch vụ dựa trên giá

Luật này có tham số thứ 2 liên kết với một thể hiện của Côngty, “VNPT” mà
KnowItAll vừa bổ sung vào nền tảng tri thức.
KnowItAll tự động tạo thành các câu truy vấn dựa trên các luật trích rút. Mỗi
luật tương ứng với câu truy vấn tạo từ các từ khóa của luật. Ví dụ, nếu mẫu trong
Bảng 1 được thể hiện hóa cho lớp Thành-Phố, nó sẽ dẫn KnowItAll đến 1)phát hành
truy vấn tới máy tìm kiếm xâu “các thành phố như là”, 2)download các trang cùng
lúc có tên trong các kết quả trả về và 3) áp dụng Bộ trích rút vào các câu trên mỗi
trang download được.

2.2.1.4

Bộ đánh giá
KnowItAll sử dụng tính tốn thống kê bằng truy vấn máy tìm kiếm để đánh

giá khả năng Bộ trích rút đã trích rút được chính xác hay chưa. Đặc biệt, Bộ đánh giá
sử dụng mô hình PMI giữa các từ và cụm từ được ước tính từ bộ đếm hitcount của
máy tìm kiếm theo phương pháp tương tự với thuật toán PMI-IR của Turney [7]. Bộ
đánh giá tính tốn PMI giữa mỗi thể hiện trích rút được với nhau, tự động tạo ra bộ
phân tách tương ứng với lớp (như là “X là một thành phố” cho lớp Thành-Phố). Ví
dụ, theo thứ tự để ước đoán rằng “Hà nội” là tên của một thành phố, bộ đánh giá có
thể kiểm tra xem nếu có một PMI cao giữa “Hà nội” và các cụm như là “Hà nội là
một thành phố”.

Gọi I là một thể hiện và D là một cụm phân tách. Chúng ta tính điểm PMI như
sau:
PMI ( I , D) 

| Hits( D  I ) |
| Hits( I ) |

Điểm PMI là số hit của một truy vấn kết hợp bộ phân tách và thể hiện, chia
bởi số lần hit cho mỗi lần thể hiện.
Những thống kê thông tin chung được coi như là các đặc trưng đầu vào của bộ
phân loại Bayes (NBC – Nạve Bayes Classifier) sử dụng cơng thức dưới đây. Đây là

25