ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
TRƯƠNG THỊ PHƯƠNG THẢO

PHƯƠNG PHÁP HỌC BÁN GIÁM SÁT CHO
BÀI TOÁN TRÍCH CHỌN THÔNG TIN VÀ
ỨNG DỤNG
TRÍCH CHỌN THỰC THỂ TÊN MÁY ẢNH SỐ
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.05 LUẬN VĂN THẠC SĨ Cán bộ hướng dẫn khoa học: TS. Nguyễn Trí Thành
2.1.2. Huấn luyện tự động 14
2.2. Các phương pháp trích chọn 15
2.2.1. Học có giám sát trích chọn quan hệ 16
2.2.2. Học không giám sát trích chọn quan hệ 18
2.2.3. Học bán giám sát trích chọn quan hệ 21
2.2.3.1. DIPRE: Dual Iterative Pattern Relation Extraction 22
2.2.3.2. Hệ thống SNOWBALL 26
2.3. Nhận xét 32
CHƯƠNG 3. MÔ HÌNH HỌC BÁN GIÁM SÁT TRÍCH CHỌN THỰC THỂ
VÀ ỨNG DỤNG 33
3.1. Mô tả bài toán 33
3.2. Mô hình giải quyết bài toán 33
3.3. Mô hình hệ thống 35
3.3.1. Pha tiền xử lí 36
3.3.2. Pha sinh các mẫu 43
3.3.3. Pha sinh các bộ quan hệ mới 48
CHƯƠNG 4. THỰC NGHIỆM 50
4.1. Môi trường thực nghiệm 50
4.2. Dữ liệu thực nghiệm 50
4.3. Đánh giá hệ thống 51
4.4. Thực nghiệm 51
Kết luận và hướng phát triển tương lai 61
Tài liệu tham khảo 62
Phụ lục. Mối quan hệ ngữ nghĩa trong WordNet 64

4

Danh mục các ký hiệu, các chữ viết tắt
IE Information Extraction
NE Named Entity

Bảng 22: Kết quả thực nghiệm 5 - Thống kê các loại máy ảnh phổ biến nhất 59
Bảng 23: Kết quả thực nghiệm 5 - Thống kê số lượng máy ảnh theo hãng sản
xuất 60
Bảng 24: Các quan hệ ngữ nghĩa trong WordNet 64

6

Danh mục các hình vẽ, đồ thị
Hình 1: Minh họa về một hệ thống trích chọn thông tin 8
Hình 2: Ví dụ về khai phá quan điểm 10
Hình 3: Sơ đồ hoạt động của hệ thống AutoSlog 17
Hình 4: Sơ đồ hoạt động của hệ thống AutoSlog – TS 19
Hình 5: Ví dụ về AutoSlog - TS 21
Hình 6: Mô hình hoạt động của hệ thống DIPRE 22
Hình 7: Mô hình hoạt động của hệ thống Snowball 27
Hình 8: Các sự kiện tìm được dựa vào bộ quan hệ hạt giống 28
Hình 9: Mô hình hệ thống trích chọn tên máy ảnh số 35
Hình 10: Mô hình của pha tiền xử lí 36
Hình 11: Mô hình thuật toán sinh mẫu từ một bộ quan hệ 43
Hình 12: Giá trị của Precision, Recall, F1 thực nghiệm trên tập 1200 53
Hình 13: Giá trị Precision, Recall, F1 của hệ thống theo giá trị sup 54
Hình 14: Kết quả thực nghiệm 3 (a) và thực nghiệm 4 (b) đối với giá trị F1 57

7

Mở đầu
Trích chọn thực thể là bài toán cơ bản nhất trong các bài toán trích chọn
thông tin nhưng lại đóng vai trò khá quan trọng. Thực thể tên ngày càng được
ứng dụng trong nhiều bài toán trong khai phá dữ liệu web cũng như nhiều các
bài toán trong xử lý ngôn ngữ tự nhiên. Do đó việc xây dựng các giải thuật trích

phân tích các tài liệu liên quan để tập hợp những thông tin cần thiết. Nếu nhiều
mối quan hệ như “Công ty A liên doanh với công ty B” được lưu trong các tài
liệu thì nó tự động tổng hợp và cấu trúc hóa, điều này rất tốt không chỉ cho các
hệ thống truy vấn thông tin mà còn cho các hệ thống hỏi đáp tự động và tóm tắt
văn bản. Do đó khai thác được những tri thức đó sẽ mang lại nhiều thông tin bổ
ích. Đó là lĩnh vực mà “trích chọn thông tin” nghiên cứu.
Trích chọn thông tin (Information Extraction - IE) là công việc trích ra các
thông tin có cấu trúc từ các văn bản không có cấu trúc. Nói cách khác, một hệ
thống trích chọn thông tin rút ra những thông tin đã được định nghĩa trước về
các thực thể và mối quan hệ giữa các thực thể từ một văn bản dưới dạng ngôn
ngữ tự nhiên và điền những thông tin này vào một văn bản ghi dữ liệu có cấu
trúc hoặc một dạng mẫu được định nghĩa trước đó. Không giống như hiểu toàn
bộ văn bản, các hệ thống trích chọn thông tin chỉ cố gắng nhận biết một số thông
tin đáng quan tâm ở một lĩnh vực nào đó. Ví dụ hệ thống trích chọn các bộ quan
hệ <tên máy ảnh, hãng sản xuất> từ các tài liệu web, bổ sung chúng vào cơ sở
dữ liệu.
Canon has posted a firmware update for
its EOS 7D digital SLR.

Pentax has announced the Optio RS1500
compact camera with interchangeable,
user designable covers.

Casio and Ricoh have released firmware
updates for the Exilim EX-H20G and
G700SE digital cameras respectively


các mối quan hệ xã hội … giữa các cặp thực thể. Ví dụ, câu “George
Bush được bầu làm tổng thống của Mỹ.” Thì quan hệ, “George Bush”
(Person) là “tổng thống” của “Mỹ”, có thể được rút ra. [5]
 Trích chọn sự kiện cho miền dữ liệu tin tức dưới dạng khung mẫu
(template). Mỗi khung mẫu bao gồm tập hợp các slot cần được lấp đầy
bởi một hoặc nhiều giá trị. Những giá trị này có thể bao gồm văn bản
thuần túy, các con trỏ trỏ tới các đối tượng khung mẫu khác [4, 9]. Ví
dụ: “4 Apr. Dallas - Early last evening, a tornado swept through northwest
Dallas. The twister occurred without warning at about 7:15 pm and destroyed
two mobile homes. The Texaco station at 102 Main St. was also severely
damaged, but no injuries were reported.” Đoạn văn bản tóm tắt câu chuyện
về thảm họa tự nhiên lốc xoáy, trích chọn các thông tin về ngày và thời
gian xảy ra, và thiệt hại tài sản hay thương tích về con người do sự kiện
gây ra. Hệ thống có thể trích chọn ra khung mẫu sau:
Event: tornado
Date: 4/3/97
Time: 19:15
Location: “northwest Dallas”: Texas: USA
Damage: “mobile homes” (đối tượng bị thiệt hại – Damaged
Object)
“Texaco station” (đối tượng bị thiệt hại)
 Khai phá quan điểm (opinion mining): trong lĩnh vực này ta cần trích
chọn ra các nhận định của người dùng về một đối tượng nào đó [14].
Hình 2 chỉ ra một trong các quan điểm mà ta có thể trích ra là thông tin
10

người dùng nhận thấy “the colors of pictures” được chụp bởi sản phẩm
Powershot là “great”.

Hình 2: Ví dụ về khai phá quan điểm

Part <picture>
Attribute <colors>
Evaluation <great>
Condition <flash is used>

Opinion unit 1

Opinion holder (writer)
Suject <Powershot>
Part < >
Attribute < >
Evaluation <easy to grip>
Condition <body has a grip
handle>

Opinion unit 2
11

 Tóm tắt văn bản: Khi xác định được nội dung của một văn bản nói về
một thực thể tên nào đó thì chúng ta sẽ gán trọng số cao cho các câu có
đề cập đến thực thể tên, cách này có thể làm tăng chất lượng của hệ tóm
tắt [11].
 Phân lớp văn bản: khi tìm ra được một thực thể tên thường thuộc một
phân lớp văn bản nào đó, thì đó sẽ là một thông tin quan trọng để giúp
làm tăng chất lượng của các giải thuật phân lớp. Chẳng hạn như tin nói
về tổng thống Obama thường hay xuất hiện ở thể loại tin tức là: Thế giới
[15].
 Tìm kiếm thực thể: đây là một hướng phát triển mới của các máy tìm
kiếm. Khi nhu cầu người dùng tăng cao thì người ta muốn các máy tìm
kiếm trở nên thông minh hơn, và người ta mong muốn có một hệ thống

chức (organization) (ENAMEX); ngày tháng (date), thời gian (time) (TIME); và
tỷ lệ (percentage), tiền tệ (monetary) (NUMEX). Giờ các thực thể tên được mở
rộng hơn như tên các loại bệnh, tên các loại protin, tiêu đề bài báo, tên các cuộc
hành trình…
WWW chứa đựng một nguồn thông tin khổng lồ, và cực kỳ phân tán, từ cơ
sở dữ liệu DNA đến danh sách các nhà hàng ưu thích. Tuy nhiên dữ liệu rải rác
trong hàng ngàn nguồn thông tin với nhiều định dạng khác nhau. Nếu các mẩu
thông tin này có thể được trích chọn từ WWW và tích hợp vào một dạng có cấu
trúc, chúng sẽ tạo thành một nguồn thông tin chưa từng có. Nó sẽ bao gồm một
thư mục quốc tế lớn nhất của con người, các cơ sở dữ liệu lớn và đa dạng nhất
các sản phẩm, và nhiều nguồn tài nguyên hữu ích khác. Chúng ta sẽ trích chọn
một quan hệ từ hàng nghìn nguồn dữ liệu, để lấy được những mẩu quan hệ trong
WWW. Nhưng một thực tế là khối lượng thông tin quá lớn, việc trích chọn thủ
công là điều không tưởng, bởi ta không chỉ làm việc trên khoảng 10 tài liệu mà
phải thực hiện trên hàng nghìn tài liệu. Vậy mục đích ở đây là để khai phá các
nguồn thông tin và trích chọn các thông tin liên quan từ chúng một cách tự động,
hay sự cực tiểu sự can thiệp của con người.
Kết quả của việc trích chọn thực thể tên phụ thuộc vào mục đích được xác
định trước như tên người, tổ chức, địa điểm, biểu thức của thời đại, số lượng, giá
trị tiền tệ, tỷ lệ phần trăm…, người dùng có thể thu lượm được một loạt các tri
thức ẩn dưới các thực thể tên đó. Ở đây luận văn tập trung vào việc trích chọn
tên máy ảnh kĩ thuật số có sử dụng giải thuật học bán giám sát.
Thị trường máy ảnh kỹ thuật số hiện có không dưới 10 nhãn hiệu nổi tiếng
trên thế giới như Sony, Canon, Fujifilm, Olympus đến Konica, Nikon, Samsung,
Pentax Nhiều nhà sản xuất chuyên về công nghệ thông tin cũng tham gia vào
thị trường này như Epson, HP cho thấy đây là một thị trường đầy hứa hẹn.
Cuộc đua giữa các nhà sản xuất vô cùng sôi động thông qua việc liên tục đưa ra
thị trường các sản phẩm có kiểu dáng mới, độ phân giải máy cao, giá mềm.
Cuộc cạnh tranh của các nhà sản xuất vẫn đang tiếp tục gia tăng, đem lại
cho người tiêu dùng những sản phẩm có chất lượng ngày càng cao với giá ngày

dấu hoặc trích lọc thông tin sau khi tìm kiếm [5].
Kỹ sư tri thức sẽ phải truy cập đến một kho văn bản có kích thước vừa phải
của các miền liên quan. Rõ ràng rằng các kỹ năng của kỹ sư tri thức đóng một
yếu tố lớn trong mức độ thực hiện cần đạt đến của toàn bộ hệ thống.
Ngoài việc đòi hỏi kỹ năng và kiến thức chi tiết của một hệ thống trích
chọn thông tin cụ thể, Với cách tiếp cận này thì hệ thống hoạt động theo một chu
trình. Để xây dựng một hệ thống hoạt động tốt phải luôn luôn có sự tương tác
giữa người viết luật và hệ thống cùng với kho ngữ liệu huấn luyện và tập luật
luôn luôn được cập nhật để cho hệ thống có thể hoạt động tốt nhất. Việc xây
dựng một hệ thống thực hiện cao thường là một quá trình lặp đi lặp lại nhiều lần,
nhờ vào một tập các quy tắc được viết ra, hệ thống sẽ chạy qua một tập dữ liệu
văn bản được huấn luyện và đầu ra được kiểm tra xem nơi nào các quy tắc này
được tạo ra. Kỹ sư tri thức sau đó tạo ra những cải biến cho các quy tắc và lặp
lại quá trình.
Ưu điểm: thích hợp với hệ thống làm việc một cách thủ công, phụ thuộc
nhiều vào kỹ năng và kinh nghiệm của người viết ra luật.
Nhược điểm: yêu cầu một chu trình kiểm tra và sửa lỗi khá là khó khăn,
phụ thuộc vào rất nhiều nguồn tài nguyên ngôn ngữ như bộ từ điển phù hợp, khả
năng của người viết luật. Nếu một nhân tố nào bị mất mát, hệ thống có thể trở
lên không còn chắc chắn nữa.
Thích hợp với những hệ thống có sẵn nguồn tài nguyên về ngôn ngữ (bộ từ
điển) và con người (người viết luật), dữ liệu huấn luyện ít hoặc tốn kém, các đặc
tả trích chọn thay đổi nhiều theo thời gian.
2.1.2. Huấn luyện tự động
Trong hướng tiếp cận này, chúng ta không cần thiết phải có kiến thức chi
tiết về việc hệ thống trích chọn thông tin xem làm việc như thế nào, hay các quy
tắc được viết ra sao. Chỉ cần thiết phải có một ai đó biết một cách đầy đủ về
15

miền và công việc này để lấy được kho dữ liệu văn bản, và chú thích những văn

đặc tả ổn định. Nếu bản đặc tả thay đổi theo thời gian, thì hệ thống sẽ chú thích
lại tất cả những dữ liệu huấn luyện đã tồn tại bằng những đặc tả mới và sau đó
huấn luyện lại. Đây là một công việc khá khó khăn.
2.2. Các phương pháp trích chọn
Vì các giải thuật dựa trên luật đòi hỏi tri thức của các chuyên gia và khả
năng thích ứng với các miền dữ liệu mới là hạn chế, nên luận văn sẽ tập trung
16

vào các giải thuật học máy. Phần này sẽ giới thiệu một số giải thuật học máy
trong trích chọn thông tin.
2.2.1. Học có giám sát trích chọn quan hệ
a. Giới thiệu:
Một hướng tiếp cận thường sử dụng trong nhiều hệ thống trích chọn có
giam sát là để huấn luyện hệ thống trên một tập tài liệu được gán nhẵn thủ công,
dựa vào đó hệ thống có thể áp dụng các kĩ thuật máy học để sinh ra các mẫu
trích chọn. Nhược điểm của phương pháp này là phụ thuộc vào tập dữ liệu được
gán nhãn, bao gồm số lượng lớn các thao tác thủ công để tạo ra nó.
Mục tiêu của học có giám sát là tìm hiểu một mô hình để phân loại các thể
hiện một cách tự động. Học có giám sát được biết đến nhiều nhất là việc phân
lớp. Ví dụ, nếu một người muốn xây dựng một hệ thống giúp ai đó mua một
chiếc ô tô, nó có thể lựa chọn hãng, màu, năm sản xuất như các đặc trưng. Hệ
thống phải có một danh sách các ví dụ thể hiện cùng với các giá trị riêng biệt
cho mỗi đặc tính. Mỗi thể hiện sẽ được đánh giá bởi một chuyên gia và được
xếp vào một lớp nào đó phục vụ để phân loại các thông tin, với bài toán mua xe
ô tô, các lớp có thể là mua hoặc không mua. Với các thể hiện này, nhãn lớp đó
tạo thành một tập huấn luyện để có thể được sử dụng như là đầu vào cho một
chương trình học có giám sát.
Học có giám sát có thể được dùng để học các mẫu từ tập huấn luyện (dưới
dạng một tập tài liệu được gán nhãn) mà không cần sự trợ giúp của con người.
Tuy nhiên, thành công của hệ thống lại phụ thuộc vào độ tin cậy của dữ liệu

trên cơ sở các từ đặc trưng trong câu. Trong hầu hết các trường hợp, họ giả sử
rằng động từ quyết định vai trò. Các luật nhận dạng vài dạng thức của động từ
như chủ động, bị động, nguyên thể. Tập các luật heuristics được trình bày trong
bảng 1.
Ví dụ, có câu “Luke Johnson was killed in Iraq by insurgents.”. Giả sử rằng Luke
Johnson được gán nhãn như một nạn nhân liên quan, AutoSlog phân tích câu đó
và nhận dạng Luke Johnson như một chủ thể. Các luật chủ thể heuristic được
kiểm tra và nhận thấy duy nhất luật #1 <subj> passive – verb phù hợp với mệnh đề
trên. Luật này được so khớp với các từ chuyên dụng trong câu đó để tạo ra mẫu
trích chọn <victim> was killed. Mẫu này sẽ được sử dụng để trích chọn cụm danh
từ ở bất kì nơi nào mà động từ killed xuất hiện trong cấu trúc bị động và chủ thể
của nó sẽ được trích chọn như một nạn nhân.
18

Tương tự, nếu insurgents được gán nhãn là thủ phạm, AutoSlog sẽ sinh ra
mẫu was killed by <np> dựa trên luật #12. Mẫu này sẽ sinh ra tất cả các cụm danh
từ đi sau giới từ by và gắn với dạng thức bị động của động từ killed.
Mẫu luật heuristic Các mẫu học được từ các luật
1 <subj> passive-verb <victim> was murdered
2 <subj> active-verb <perpetrator> bombed
3 <subj> verb infinitive <perpetrator> attempted to kill
4 <subj> aux noun <victim> was victim

5 Passive-verb <dobj> Killed <victim>
6 Active-verb <dobj> Bombed <target>
7 Infinitive <direct-obj> To kill <victim>
8 Verb infinitive <direct-obj> Tried to attack <target>
9 Gerund <direct-obj> Killing <victim>
10 Noun aux <direct-obj> Fatality was <victim>


muốn học các mẫu trích chọn cho miền khủng bố, người dùng sẽ cung cấp một
tập văn bản mô tả các sự kiện khủng bố và một tập không liên quan các sự kiện
khủng bố. AutoSlog – TS tạo ra mọi mẫu có thể trong tập văn bản, sau đó tính
toán thống kê dựa trên tần xuất xuất hiện của mỗi mẫu trong tập các văn bản liên
quan so với tập các văn bản không liên quan. Sau đó hệ thống sẽ tạo ra một danh
sách xếp hạng các mẫu trích chọn được cùng với số liệu thống kê để chỉ ra mẫu
nào hỗ trợ nhiều nhất với miền đang xét.
AutoSlog TS sử dụng tập gồm 15 luật heuristic, bao gồm 13 luật của
AutoSlog ở bảng 1, cộng thêm 2 mẫu heuritic mới: <subj> active-verb dobj
(<perpetrator> attacked embassy); infinitive preposition <noun-phrase > (to sell for
<np>). Hai mẫu thêm vào này được tạo ra cho các miền kinh doanh từ các kinh
nghiệm đã có.

Hình 4: Sơ đồ hoạt động của hệ thống AutoSlog – TS
Hoạt động của hệ thống AutoSlog được thể hiện trong hình 4.
20

 Giai đoạn 1:
+ phân tích ngữ pháp để xác định các cụm danh từ
+ với mỗi cụm danh từ, các luật heuristic sinh ra các mẫu (gọi là các nút
khái niệm - concept node trong CIRCUS)
+ có thể sinh ra các luật phức tạp. Giả sử có câu “terrorists bombed the US
embassy”, và cụm danh từ terrorists đã được gán nhãn thủ phạm thì cả luật <subj>
active-verb và <subj> active-verb dobj đều được áp dụng vào  Ta có các mẫu
được sinh ra là: <perpetrator> bombed
<perpetrator> bombed embassy
Giai đoạn này tạo ra một số lượng lớn các mẫu trích chọn, đến hàng chục
nghìn mẫu riêng biệt, các mẫu này có khả năng trích chọn mọi cụm danh từ
trong tập tài liệu.
 Giai đoạn 2: Tiến hành quá trình huấn luyện tập dữ liệu lần 2 sử dụng

and claimed that the death of more judges would soon follow.
Irrelevant Text
The Los Angeles Times reported that Marlon Brando died today in
California. Marlon Brando died at the UCLA Hospital at the age of 80. Sources
claimed that he had been diagnosed with pulmonary fibrosis.

Total_Freq

Rel_Freq

Prob RlogF Pattern
4 3 0.750 1.189 died in <np>
2 2 1.000 1.000 death of <np>
21

3 2 0.667 0.667 <subj> claimed
4 2 0.500 0.500 <subj> died
1 0 0.000 0.000 was diagnosed with <np>
1 0 0.000 0.000 <subj> was diagnosed
1 0 0.000 0.000 age of <np>
1 1 1.000 0.000 <subj> follow
1 1 1.000 0.000 responsibility for <np>
1 1 1.000 0.000 claimed <dobj>
1 1 1.000 0.000 <subj> claimed responsibility
3 1 0.333 0.000 died at <np>
1 1 1.000 0.000 shot with <np>
1 1 1.000 0.000 shot <dobj>
1 1 1.000 0.000 <subj> shot judges
1 1 1.000 0.000 <subj> shot
2 1 0.500 0.000 <subj> reported

tên sách và tên tác giả viết cuốn sách. Ví dụ: cặp (The Comedy of Errors,
W.Shakespeare) thể hiện quyển sách The Comedy of Errors do W.Shakespeare viết
ra.
Điểm nổi bật trong nghiên cứu này là thuật toán DIPRE, một kỹ thuật trích
chọn các quan hệ cùng với việc tạo để sử dụng tính đối ngẫu của mẫu – quan hệ.
D = một CSDL lớn thông tin không có cấu trúc như là www
R = r1, ….rn là các quan hệ đích.
Một bộ dữ liệu t, của R xuất hiện một hoặc nhiều lần trong D, là một quan
hệ. Ví dụ trong [3], tập quan hệ đích R là bảng chứa các cặp (author, title).
Tính đối ngẫu giữa mẫu và quan hệ: từ một tập các mẫu tốt, ta có thể xây
dựng một tập các bộ quan hệ tốt. Ngược lại, chúng ta mong muốn đưa ra một tập
các bộ quan hệ tốt, chúng ta có thể xây dựng một tập các mẫu tốt.
Giải thuật DIPRE làm việc theo mô tả trong hình 6.

Hình 6: Mô hình hoạt động của hệ thống DIPRE
Quy trình rút trích dựa theo thuật toán DIPRE:
1. Lấy R’ là một tập nhỏ của tập quan hệ đích (danh sách 5 quyển sách với
tác giả).
2. O

FindOccurrences(R’; D): thủ tục tìm sự xuất hiện của các cặp quan
hệ hạt giống của R’ trong tập D.
Là đoạn văn bản chứa đồng thời tên tác giả và tiêu đề của quyển sách trong
văn bản (sự kiện chứa tên tác giả và tên sách).
Với bộ quan hệ tìm được, giữ ngữ cảnh xung quanh tên tác giả và tên sách
(url và văn bản xung quanh).
3. P

GenPatterns(O): Sinh các mẫu từ các sự kiện đã tìm được
Initial Seed Tuples

wrote, Great Expectations, book, true, www.books.com/TopRated).
 Mẫu là một bộ - 5: (order, urlprefix, prefix, middle, suffix)
Trong đó:
+ Order có giá trị Boolean, chỉ thứ tự xuất hiện của author và title
trong câu,
+ Các phần tử còn lại là một chuỗi ký tự.
Ví dụ: Mẫu có dạng <LI><B>title</B> by author ( , thì:
+ Order = true
+ Urlprefix = www.books.com
+ Prefix = <LI><B>
+ Middle = </B> by
+ Suffix = (
 Một cặp (title, author) được trích chọn nếu có một URL trên web hợp
với urlprefix* và nội dung của nó có chứa đoạn hợp với biểu thức
chính quy “*prefix, author, middle, title, suffix*”, đồng thời khi đó
biến order = true. Biểu thức chinh quy cho author và title lần lượt là:
[A-Z][A-Za-z .,&]5;30[A-Za-z.]
[A-Z0-9][A-Za-z0-9 .,:'#!?;&]4;45[A-Za-z0-9?!]
24

b. Bộ quan hệ ban đầu
Title Author
The Robots of Dawn Issac Asimov
Startide Rising David Brin
Chaos: Making a New Science James Gleick
Great Expectations Clarles Dickens
The Comedy of Errors W. Shakespeare
Bảng 2: Năm bộ quan hệ hạt giống của hệ thống DIPRE
c. Tìm các sự kiện dựa trên tập bộ quan hệ ban đầu
Ở công đoạn này, hệ thống cần trải qua hai lần lọc fgrep: fgrep author và

&#146;90)
Startide
Rising
David
Brin
F www.sff.net
/locus/c5.ht
ml
<LI>
<B>
</B>
by
(Pulphouse,
Jul
&#146;90)
Foundation Isaac
Asimov
F www.scifi.o
rg/bydecade
/1950.html
<LI>
<B>
</B>
by
(1951)
Nightfall Isaac
Asimov
F www.scifi.o
rg/bydecade
/1940.html

được thực thể là tên sách.
Để giải quyết vấn đề này, ta sẽ gắn mỗi mẫu với một độ đo specificity
specificity(p) = |p.middle||p.urlprefix||p.prefix||p.sufix|
trong đó: p.middle, p.urlprefix, p.prefix, p.sufix là middle, urlprefix, prefix,
sufix của mẫu p; |s| chỉ độ dài của xâu s.
Hệ thống sẽ loại bỏ các mẫu có độ specificity quá thấp, tuy nhiên
specificity(P)n > t với n là số lượng các quyển sách trong các thể hiện tương ứng
với mẫu P (n>1) và t là một ngưỡng nào đó.
* Thuật toán sinh nhiều mẫu GenPatterns(O).
1. Nhóm tất các sự kiện o trong O theo trường order và middle. Gọi các
nhóm này là O
1
, …, O
K
.
2. Với mỗi nhóm O
i
, p GenOnePattern(O
i
). Nếu p thoả mãn điều kiện về
độ “riêng biệt” thì đưa ra p. Nếu không:
 Nếu tất cả các sự kiện o trong O
i
có cùng url, ta không thể mở rộng
được urlprefix thì loại bỏ O
i
đó.