MỤC LỤC
1
DANH MỤC HÌNH ẢNH
2
LỜI MỞ ĐẦU
Trích chọn thông tin là một khâu cơ bản trong bài toán khai phá dữ liệu. Ngày
nay cùng với sự phát triển của công nghệ thông tin, tin học đã dần được ứng dụng rộng
rãi trong nhiều lĩnh vực: kinh tế, thương mại, y tế, ngân hàng … và mang lại nhiều lợi
ích to lớn.
Trong nhiều thập kỷ qua, các nhà khoa học quan tâm đến lĩnh vữ xử lý ngôn ngữ
tự nhiên đã nghiên cứu và đề xuất được nhiều phương pháp mô hình xử lý ngôn ngữ
với hiệu quả cao. Nổi bật trong phướng pháp đó là trích rút thông tin bán giám sát.
Từ đó em chọn đề tài “ Trích chọn tên công ty, địa chỉ , doanh thu trên nền web.
3
CHƯƠNG 1. SƠ LƯỢC BÀI TOÁN TRÍCH CHỌN THỰC THỂ TÊN
CÔNG TY, ĐỊA CHỈ VÀ DOANH THU.
1.1. Tổng quan về trích chọn thông tin.
Với sự bùng nổ của Internet và các phương tiện lưu trữ đã tạo ra một lượng thông
tin khổng lồ. Bên cạnh đó nhu cầu về tốc độ xử lý thông tin cũng như tính chính xác
ngày càng tăng. Hiện nay, các máy tìm kiếm (search engine) thực hiện việc tìm những
trang web phù hợp với yêu cầu câu hỏi người dùng.
Mặc dù chất lượng của các máy tìm kiếm đã được cải thiện nhưng kết quả trả về
chỉ là những tài liệu có liên quan, chúng không dễ dàng gì rút ra được các mối quan hệ
tiềm ẩn và tạo được các câu trả lời cho các truy vấn phức tạp, chẳng hạn như “danh
sách các công ty liên doanh” hoặc “danh sách các nhà lãnh đạo quốc tế trên toàn thế
giới”. Người ta phân loại câu trả lời các truy vấn ở dạng: có 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.
1.2. Bài toán rút trích thực thể tên công ty, địa chỉ và doanh thu.
Tổ chức là một trong những đối tượng cơ bản xuất hiện trong văn bản, đặc biệt là
trong các website về kinh tế, xã hội, thế giới… Cùng với sự phát triển của thương mại
điện tử, sự toàn cầu hóa …nên nhu cầu tìm hiểu về các tổ chức Việt Nam cũng như thế
giới là vấn đề đáng được quan tâm. Rút trích tên tổ chức là liệt kê ra danh sách tên các
tổ chức xuất hiện trong văn bản.
4
Bài toán rút trích tên thực thể (mà cụ thể ở báo cáo này là bài toán trích chọn
thực thể tên các tổ chức) là bài toán cơ bản trong các bài toán trích chọn thông tin. Bởi
vì trước khi khai phá được các tri thức về thuộc tính, tính chất của các thực thể, thì đầu
tiên chúng ta phải rút trích ra được chính xác tên của thực thể đó. Tuy nó là bài toán cơ
bản, nhưng tồn tại rất nhiều vấn đề nhập nhằng làm cho việc rút trích gặp khó khăn.
Đặc biệt với ngôn ngữ tiếng Việt, đa dạng trong cách viết, đôi khi nhập nhằng về ngữ
pháp, và chưa có một chuẩn nào cụ thể về chữ hoa, chữ thường cho tên tiếng Việt cũng
như xuất hiện nhiều từ “thừa” chỉ mang tính chất liệt kê, bổ nghĩa
Có nhiều phương pháp được áp dụng cho bài toán rút trích tên thực thể như
phương pháp học máy HMM … Trong báo cáo này, em sử dụng phương pháp “học
gần không giám sát“ dựa trên thuật toán DIPRE và ý tưởng rút trích cặp quan hệ
(author, title) của Brin, kết hợp các luật hỗ trợ để rút trích thực thể tên tổ chức. Tuy
nhiên, có một hạn chế là thuật toán DIPRE thường áp dụng cho bài toán rút trích cặp

quan hệ như (tên sách, tên tác giả), (tổ chức, trụ sở chính của tổ chức) …., còn nội
dung báo cáo này chỉ là trích chọn thực thể đơn – tên tổ chức. Nhưng lợi thế của
DIPRE là tính tự động (automatic), cần ít thao tác thủ công của con người, có thể áp
dụng trong miền dữ liệu lớn. Hơn thế nữa tên các tổ chức thường có “quan hệ” nào đó
với các “tiền tố” đứng liền nó. Đấy là những tiền đề để áp dụng kỹ thuật DIPRE vào
bài toán trong báo cáo này. Các chương tiếp theo sẽ đề cập chi tiết hơn.
1.3. Ý nghĩa của bài toán rút trích thực thể tên công ty, địa chỉ và doanh thu.
Một hệ thống rút trích các loại thực thể hiểu quả có thể có nhiều ứng dụng trong
thực tế:
- Hỗ trợ xây dưng Web ngữ nghĩa.
- Xây dựng các máy tìm kiếm hướng thực thể. Do đó thời gian tiềm kiếm sẽ giảm
đi khi có sự trợ giúp của hệ thống trích chọn thực thể
- Hỗ trợ hệ thống tóm tắt văn bản tự động. …
Bài toán rút trích thực thể tên tổ chức trong báo cáo này đưa ra chỉ là bài toán cơ
bản, chưa có ứng nhiều trong thực tế. Mới chỉ dừng lại ở mức là làm giàu thông tin
cho dữ liệu. Tuy nhiên nó là cơ sở để phát triển bài toán phức tạp hơn, hữu ích hơn.
5
CHƯƠNG 2. HƯỚNG TIẾP CẬN BÀI TOÁN TRÍCH CHỌN THỰC THỂ
Học máy là hướng tiếp cận phổ biến nhất cho bài trích chọn thực thể. Bài toán
đưa ra trong báo cáo sẽ tiếp cận một cách khác. Chương này, chúng em sẽ giới thiệu
một số bài toán điển hình đã được thực hiện để rút trích cặp quan hệ, từ đó rút ra ý
tưởng áp dụng cho bài toán rút trích thực thể tên công ty, địa chỉ và doanh thu.
2.1. Rút trích cặp quan hệ (title, author) của cuốn sách trong tài liệu web.
Nhận thấy rằng thông tin trên WWW không phải chỉ ở dạng thô, mà chúng còn
tiềm ẩn những quan hệ, cấu trúc nào đó. Nếu khai phá được những đặc tính đó thì sẽ
rất hữu ích cho việc xử lý thông tin. Segrey Brin đã đưa ra một ý tưởng là rút trích ra
các cặp “title” và “author” của cuốn sách. Đặc điểm của cặp được rút trích này là
chúng có quan hệ với nhau. Điểm nổi bật trong nghiên cứu này là thuật toán DIPRE sẽ
được trình bày dưới đây.
Đầu tiên giới thiệu một số khái niệm có trong bài toán, sau đó sẽ đưa ra quy trình

rút trích tổng quát và chi tiết các thuật toán sử dụng trong bài.
2.1.1. Occurrences của sách.
Occurrences của cuốn sách được hiểu là thông tin về sự “xuất hiện” của cuốn
sách (gồm title và author) trên tập dữ liệu. Để thuận tiện cho việc xử lý, Brin biểu diễn
occurrences của cuốn sách là một bộ gồm 7 trường:
(author, title, order, url, prefic, sufix)
Order: Thứ tự xuất hiện của author và title.
url: Địa chỉ trang web mà nội dung có chứa author, title.
Prefix: Xâu nằm giữa author và title.
Sufix: Xâu đứng sau author hay title.
2.1.2. Patterns của sách
Patterns sẽ được “ánh xạ” ngược vào tập tài liệu để rút trích ra tập quan hệ mới
(ở đây là “title” và “author”). Patterns được “sinh ra” từ tập các Occurrences ở trên
theo một tiêu chí, quy tắc nào đó (sẽ được trình bày ở dưới). Patterns có ý nghĩa quan
trọng trong việc rút trích. Patterns tố sẽ tăng số lượng cũng như chất lượng tìm kiếm,
rút trích.
Patterns cho những cuốn sách là một bộ gồm 5 trường:
(order, urlprefix, prefix, middle, suffix)
Order: Giống ở Occurrences
Một cặp (author, title) được rút trích nếu có một URL trên web hợp (matchs) 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,
6
middle, title, suffix”, đồng thời khi đó biến order = true. Biểu thức chính 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?!]

2.1.3. Quy trình rút trích
Quy trình rút trích dựa theo thuật toán DIPRE. Ý tưởng là:
Bước 1. Bắt đầu bằng mẫu nhỏ R’ – tập 5 cuốn sách và tên tác giả tuơng ứng.
Mẫu này được thao tác trực tiếp bằng tay.
Bước 2. O←FindOccurrences(R’;D)
Tìm tất cả sự xuất hiện của các bộ (author, title) của R’ trong D. Ứng với mỗi bộ
tìm thấy, ghi nhớ lại url và text xung quanh (ở giữa, 2 bên) “author” và “title”.
Bước 3. P←GenPatterns(O)
Dựa vào tập xuất hiện của cặp (author, title) để sinh ra mẫu (pattern). Mẫu sinh ra
phải không được quá riêng biệt, hay quá chung chung thì mới là mẫu tốt.
Bước 4. R’←M
D
(P)
Từ những pattern xây dựng được, tìm kiếm trên CSDL những bộ (tuples) mà hợp
với mẫu đó.
Bước 5. Nếu R’ đủ lớn thì kết thúc. Ngược lại nhảy về bước 2
Kỹ thuật trên có thể được mô tả như hình dưới đây:
7
Bộ dữ liệu ban đầu Xuất hiện của dữ liệu
Tạo bộ dữ liệu mới
Tạo ra các mô hình khai thác
Hình 2.1: Quy trình rút trích.
2.1.4. Thuật toán sinh Patterns
Như đã trình bày trong mục trên, thủ tục GrePatterns có nhiệm vụ sinh ra các
patterns dựa vào các Occurrenes. Nó là một quy trình quan trọng trong DIPRE. Giả sử
chúng ra có một bộ occurrences, và sẽ “thử” dựng nên một pattern từ bộ đó. Khi đã có
thủ tục sinh ra 1 pattern, thì thủ tục sinh tất các patterns có thể cũng sẽ tương tự, như
được trình bày dưới đây:
Sinh một Pattern
Các bước cho thủ tục GenOnePattern(O) – sinh 1 pattern như sau:

• Cần phải chắc chắn rằng order và middle của tất cả sự xuất hiện (occurrences)
phải giống nhau. Nếu không thì không thể sinh ra được pattern để match với tất
cả occurrences. Đặt outpattern.order và outpattern.middle tương ứng với order
và middle.
8
• Tìm đoạn prefix dài nhất của các url mà chúng giống nhau. Đặt
outpattern,urlprefix = prefix
• Đặt outpattern.prefix là xâu dài nhất của các prefix mà chúng giống nhau tính
từ cuối (suffix) của các tiền tố (prefix) đó.
• Đặt outpattern.suffix là sau dài nhất của các suffix mà chúng giống nhau tính từ
đầu (prefix)của các hậu tố (sufixs) đó.
Kết quả thu được một pattern.
Sinh tập patterns
Thuật toán cho GenPatterns (O) dựa vào thuật toán GrenOnePatern(O) đã được
giới thiệu ở trên:
• Nhóm tất cả sự xuất hiện (occurrences) o trong O theo order và middle. Được
các nhóm O
1
, …, O
k
.
• Với mỗi O
i
, p ← GenOnePattern(O
i
). Nếu p thỏa mán điều kiện về độ “riêng
biệt” thì nhận p đưa ra ngoài. Nếu không:
- Nếu tất cả occurrences o trong O
i
có chung url thì bỏ O

i
.
- Ngược lại: Tách các occurrences o trong O
i
thành những nhóm con dựa
vào đặc điểm urls của chúng – qua p.urlprefix. Lặp lại thủ tục ở bước 2 cho
những nhóm con này.
Ý tưởng của thủ tục sinh patterns như trên là chia nhỏ urls khi patterns sinh ra
không đủ “riêng biệt”. Như thế thì cũng có thể sử dụng kỹ thuật chia nhỏ theo prefix
hay suffix. Tất cả trên chỉ là những giải pháp cơ bản, để có được 1 kỹ thuật tốt hơn thì
cần phải nghiên cứu thêm. Tuy nhiên kết quả mà kỹ thuật vừa đưa ra cũng có một kết
quả thực nghiệm chấp nhận được.
2.2. Thu thập tên và miền tương ứng từ tập tài liệu web.
Con người, thời gian, địa điểm…là những thực thể cơ bản trong văn bản dù ở bất
cứ ngôn ngữ nào. Nhưng với từng “chuyên ngành” hay lĩnh vực riêng thì vẫn tồn tại
rất nhiều thực thể và miền của thực thể đó. Nếu rút trích được các cặp tên miền và thực
thể (C, N) rồi tích hợp vào các hệ thống như WordNet thì sẽ tạo ra cơ sở tri thức hữu
ích.
Dựa trên DIPRE, Marius Pasca đưa ra một mô hình để thu được cặp (C,N) từ tài
tập liệu web. C và N tương ứng viết tắt cho Category và named Entity ( miền và tên
thực thể). Pattern được sử dụng có dạng :
[StartOfSent] X [such as|including] N [and|,|.]
9
Ở đây X là một “categorical fact” tạm hiểu nó là một xâu mà được coi là có chứa
miền C. N là “potential instance name” tạm hiểu là thực thể cần tìm thuộc miền C.
Một đặc điểm để nhận dạng N đó là nó là một danh từ riêng nên thường được viết hoa.
Để tăng số lượng cặp (C, N) rút trích được, mô hình đưa ra phương thức để “tự
động” sinh ra những patterns mới. Bằng cách “ánh xạ” những cặp (C, N) đã được rút
trích ở vòng lặp trước vào dữ liệu. Ý tưởng được mô tả như trong hình dưới :
Hình 2.2: Rút trích Patterns mới.

2.3. Hệ thống Snowball.
Cũng dựa trên tư tưởng của DIPRE, Eugene Agichtein và Luis Gravano đã xây
dựng hệ thống Snowball [3] để rút trích cặp quan hệ (organization, location) – tổ chức
và địa điểm. Biểu diễn mối quan hệ một tổ chức organization có trục sở đặt tại địa
điểm location. Snowball đã đưa ra một kỹ thuật mới để sinh patterns và rút trích cặp
quan hệ từ tài liệu. Snowball cũng có thêm chiến lược đánh giá chất lượng của mỗi
patterns và cặp quan hệ, nếu cái nào đủ tin cậy thì mới được sử dụng cho các vòng lặp
tiếp theo. Tuy nhiên Snowball cần đến sự hỗ trợ của NER (Named Entity
Recognition).
Mô hình của Snowball được biểu diễn như dưới :
10
Bộ dữ liệu ban đầu Xuất hiện của dữ liệu
Tạo bộ dữ liệu mới
Tạo ra các mô hình trích rút
Gán thực thể
11
Hình 2.3: Hệ thống Snowball.
Với mỗi cặp organization-location <o, l> Snowball xác định nó trong tập tài liệu
và phân tích các thành phần trái (left), giữa (middle) và phải (right) để sinh pattern.
Pattern của Snowball là một bộ 5 thành phần :
<left, tag1, middle, tag2, right>
Trong đó tag1, tag2 là các thẻ tên thực thể (cụ thể ở đây là <ORGANIZATION>
và <LOCATION> ) và left, middle, right là các vector liên kết “terms” và “weights”.
(terms là xâu tùy ý hoặc kí tự trống, weights – trọng số biểu thị độ quan trọng của
terms). Mỗi vector các terms có trọng số weights nằm trong khoảng từ 0 đến 1. Trọng
số càng lớn thì độ ưu tiên của term đó càng cao.
Sinh cặp quan hệ
Trước hết định nghĩa độ phù hợp của hai bộ tP = < lP , t1, mP , t2, rP > (t1, t2 là
các thẻ) tS = <lS, t’1, mS, t’2, rS > (t’1, t’2 là các thẻ) theo công thức :
Sau khi sinh được các patterns, Snowball quét tập tài liệu để tìm ra những cặp (o,

l) mới. Dùng MITRE Corporation’s Alembic Workbench [2] để nhận dạng những câu
có chứa một organization và location. Phân tích nội dung xung quanh nó và sinh ra 1
bộ 5 trường t = <lc, t1, mc, t2, rc > theo quy tắc giống ở trên. Gọi cặp <o, l> là cặp
“ứng cử viên” nếu có một pattern tp thỏa mãn Match(t, tp) >= tsim (tsim là ngưỡng).
Mỗi một cặp “ứng cử viên” được sinh bởi các patterns ứng với từng “độ phù hợp”
(như giá trị Match(t , tp) trên ). Và mỗi một pattern cũng có một độ đo tính “chọn lọc”
của nó. Snowball sẽ sử dụng hai thông số này để quyết định cặp “ứng cử viên” nào là
thích hợp.
2.4. Tổng kết chương.
Rút trích cặp quan hệ (title, author) là bài toán cơ bản nhất, kỹ thuật biểu diễn
pattern và occurrence đơn giản, thuật toán để sinh pattern từ occurrence cũng không
phức tạp. Độc đáo nhất ở bài toán là thuật toán DIPRE.
Hệ thống Snowball độc đáo với cách biểu diễn pattern mềm dẻo , cộng với sự hỗ
trợ của thẻ tên thực thể (NER) nên có kết quả thu được tốt nhất. Tuy nhiên chỉ “học “
được ở Snowball chiến lược đánh giá pattern và cặp thực thể thu được để áp dụng vào
báo cáo, còn để biểu diễn được pattern thì cần sự hỗ trợ của NER – trong khi bài toán
trong báo cáo này bản chất chính là xây dựng NER.
12
CHƯƠNG 3. CHƯƠNG TRÌNH TRÍCH CHỌN TÊN CÔNG TY, ĐỊA CHỈ VÀ
DOANH THU
3.1. Chuẩn bị đầu vào.
3.1.1. Thu thập dữ liệu.
Dữ liệu cho phần thực nghiệm gồm các bài viết về tin kinh tế được lấy từ các
nguồn
/>3.1.2. Xây dựng mô hình đầu vào.
Trong phần trích rút tên công ty, địa chỉ, doanh thu ta có 3 mô hình đầu vào
- Công ty: Hầu như trong văn bản Tiếng Việt tên công ty thường có các cụm
từ đứng trước mỗi công ty: Công ty, Công ty TNHH, Công ty cổ phần,
Doanh nghiệp tư nhân,…. Từ đó em xây dựng tập dữ liệu đầu vào gồm các
cụm từ trên.

- Địa chỉ: Để trích chọn được thực thể địa chỉ ta cũng có một tập huấn luyện
đầu vào: địa chỉ, địa phận, địa bàn,….
- Doanh thu: Đối với thực thể doanh thu ta cũng cần một tập huấn luyện đầu
vào: doanh thu, doanh thu đạt, doanh thu xấp xỉ, doanh thu hằng năm,….
3.1.3. Xây dựng các luật.
• Đối với thực thể Công ty thì thường tên công ty sẽ được viết hoa chữ cái đầu,
nhưng trong nhiều văn phạm thì có các cách viết phong phú nên việc trích chọn
vẫn còn gặp nhiều khó khăn và sai sót.
Để trích chọn được tên công ty:
- Tìm kiếm sự xuất hiện của các từ trong tập dữ liệu đầu vào của thực thể
công ty.
- Lấy giá trị xuất hiện đầu tiên sau cụm từ mẫu và trích chọn thực thể nếu
gặp một ký tự thường, hoặc các dấu “. , ; ( /” thì trích chọn dừng lại.
- Kiểm tra nếu thực thể có độ dài lớn hơn 2 ký tự thì kiểm tra xem thực thể
đó đã tồn tại trong bảng thực thể hay chưa. Nếu chưa thì thực hiện lưu
thực thể vừa tìm được vào cơ sở dữ liệu.
• Đối với thực thể Địa chỉ thì rất khó xác định được bởi vì cách viết rất đa dạng
của tiếng việt . Vì vậy ở đây ta xác định việc trích chọn dừng khi gặp các dấu
hiệu “ : . ; (“
• Đối với thực thể Doanh thu rất khó tìm thấy thực thể trên các trang tin tức. Vì
vậy cần phải tìm nguồn tốt. Việc trích chọn được xác định bởi các dấu hiệu
“ . , ; ( “
13
3.2. Kết quả thực nghiệm.
Giao diện lấy các nguồn tin
Hình 3.1. Giao diện lấy nguồn tin.
14
Giao diện lấy thông tin chi tiết bài viết.
Hình 3.2. Giao diện lấy thông tin chi tiết bài viết.
Trích rút thực thể

Hình 3.3. Phần trích rút thực thể
15
KẾT LUẬN
Báo cáo đã khái quát hóa một số vấn đề lý thuyết về trích chọn thông tin, bài toán
trích chọn thực thể tên tổ chức, đồng thời đưa ra các bài toán nền tảng để áp dụng vào
cho báo cáo này. Một số vấn đề và giải pháp cho bài toán đã được đưa ra, điểm đặc
biệt chú ý nhất là kỹ thuật DIPRE. Thực nghiệm đã đưa ra một số trường hợp tiêu biểu
để thể hiện đặc điểm, bản chất của bài toán. Tuy nhiên kết quả của thực nghiệm mới
chỉ ở mức tạm chấp nhận được. Khái quát lại nội dung mà luận văn đã đưa ra.
Chương 2 trình bày các bài toán liên quan, nó là cơ sở để áp dụng cho bài toán
trong báo cáo này. Vấn đề mấu chốt nhất trong chương là kỹ thuật DIPRE. Đó là một
kỹ thuật chính sử dụng cho bài toán trong báo cáo, với một đặc điểm nổi bật là có thể
áp dụng cho tập dữ liệu lớn mà cần ít sự can thiệp của con người. Sử dụng kết quả của
vòng lặp hiện tại để làm dữ liệu vào cho vòng lặp tiếp theo …. Ngoài ra những kỹ
thuật rút trích thực thể từ tập các patterns của hệ thống Snowball hay kỹ thuật rút trích
tên thực thể, tên miền mà Pasca đưa ra cũng là ý tưởng quan trọng để em áp dụng vào
báo cáo của mình.
16
TÀI LIỆU THAM KHẢO
[1]. Phương pháp học gần không giám sát để trích chọn thực thể tên tổ chức của Vũ
Quốc Đạt – Đại học Quốc Gia Hà Nội – Trường Đại học Công Nghệ.
[2]. Trích chọn thực thể tên người trong Tiếng Việt của Lê Thu Thùy – Đại học Quốc
Gia – Trường Đại học Công Nghệ
17