ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Xuân Thành
TỰ ĐỘNG TỔNG HỢP VÀ PHÂN LOẠI TIN
TRONG HỆ THỐNG TRANG TIN ĐIỆN TỬ
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Xuân Thành
TỰ ĐỘNG TỔNG HỢP VÀ PHÂN LOẠI TIN
TRONG HỆ THỐNG TRANG TIN ĐIỆN TỬ
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: TS. Nguyễn Trí Thành
HÀ NỘI - 2010
Lời cảm ơn
Lời đầu tiên, tôi xin được bày tỏ lòng biết ơn sâu sắc nhất tới thầy giáo – TS.
Nguyễn Trí Thành đã tận tình hướng dẫn, đôn đốc tôi trong suốt quá trình là khóa luận tốt
nghiệp.
Tôi xin được chân thành cảm ơn các thầy, cô và các cán bộ của trường Đại Học
Công Nghệ đã tạo cho tôi những điều kiện thuận lợi để học tập và nghiên cứu.
Tôi xin gửi lời cảm ơn tới ThS Nguyễn Thanh Bình, ThS Lê Văn Thanh và tập thể
các anh chị em của công ty iTim đã động viên, khích lệ, tạo điều kiện cho tôi trong suốt
quá trình làm khóa luận.
Tôi cũng xin gửi lời cảm ơn tới các bạn trong tập thể lớp K51CD và K51CHTTT đã
ủng hộ và khuyến khích tôi trong suốt quá trình học tập tại trường.
Cuối cùng, tôi muốn được gửi lời cảm ơn vô hạn tới gia đình và bạn bè, những
người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt
nghiệp.

1
/>

ii

Mục lục
Tóm tắt nội dung i

Mục lục ii

Bảng các ký hiệu viết tắt iv

Danh sách các hình v

Danh sách các bảng biểu vi

Giới thiệu 1

Chương 1.

Khái quát về các trang tin tức và các hệ thống tổng hợp tin tức của Việt
Nam 3

1.1.

Trích chọn thông tin trên tài liệu Web 11

2.2.2.

Xây dựng bộ trích chọn tài liệu Web 11

2.3.

Xây dựng bộ phân lớp 12

2.3.1.

Khái niệm phân lớp văn bản 12

2.3.2.

Áp dụng thuật toán phân lớp entropy cực đại xây dựng bộ phân lớp văn bản.
14

2.3.3.

Phương pháp đánh giá hiệu suất phân lớp 18

Chương 3.

Xây dựng hệ thống tổng hợp và phân loại tin tự động 21

3.1.

Cơ sở thực tiễn 21

Thực nghiệm và đánh giá kết quả 34

4.1.

Môi trường phần cứng và phần mềm 34

4.1.1.

Môi trường phần cứng 34

4.1.2.

Công cụ phần mềm 34

4.2.

Cấu trúc Cơ sở dữ liệu 37

4.3.

Đánh giá chất lượng tổng hợp tin 39

4.4.

Thực nghiệm và đánh giá hiệu suất phân loại tin tự động 39

4.4.1.

Xây dựng tập dữ liệu huấn luyện và kiểm tra mô hình 39


HTML HyperText Markup Language
URL Uniform Resource Locator
WWW World Wide Web
CSDL Cở sở dữ liệu
v

Danh sách các hình
Hình 1. Minh họa lỗi tổng hợp tin trang Baomoi.com…………………………………….5
Hình 2. Minh họa lỗi mất ảnh trang tintuc.xalo.vn……………………………………… 7
Hình 3. Sơ đồ cơ bản của một crawler đơn luồng…………………………………………9
Hình 4. Lược đồ chung xây dựng bộ phân lớp văn bản………………………………….13
Hình 5a. Mô tả phần nội dung cần lấy trên trang tin 1………………………………… 21
Hình 5b. Mô tả phần nội dung cần lấy trên trang tin 2………………………………… 22
Hình 6. Mô hình cây DOM của 2 detail-pages………………………………………… 22
Hình 7a. Các đặc trưng cho phép trích chọn thông tin bài báo 1……………………… 23
Hình 7b. Các đặc trưng cho phép trích chọn thông tin bài báo2…………………………24
Hình 8. Mô hình tổng quan của hệ thống tổng hợp và phân loại tin tức…………………25
Hình 9. Đặc điểm giúp loại tin thuộc lớp chưa quan tâm……………………… … 28

có đủ thông tin. Như vậy, nhu cầu đặt ra cần có một hệ thống tổng hợp tin tức nhanh
nhất và được phân chia theo các mục, phân mục rõ ràng, giúp thuận tiện hơn cho nhu cầu
thông tin của người dùng. Điều này giúp người dùng thuận tiên hơn cho việc tìm, cập nhật
các thông tin mà mình quan tâm một cách thuận tiện nhất, tiết kiệm thời gian nhất. Điều
này đặc biệt có ý nghĩa trong cuộc sống bận rộn hiện đại ngày nay.
Để giải quyết được bài toán về hệ thống tổng hợp tin tức cần phải giải quyết được
hai bài toán khác là trích xuất thông tin từ tài liệu Web và phân lớp tự động các văn bản
Web – là hai bài toán được quan tâm ở rất nhiều các hội nghị lớn về khai phá dữ liệu và
xử lý ngôn ngữ tự nhiên [6],[9],[10],[14]. Khóa luận xây dựng một tập luật cho phép tự
động gom và trích xuất thông tin từ các trang tin tức của Việt Nam, tin tức được lấy về sẽ
được gán nhãn tự động nhờ vào thuật toán phân lớp văn bản entropy cực đại (maximum
entropy), và được ghi lại vào CSDL, phục vụ cho việc xuất bản tin.
Khóa luận gồm có 4 chương được mô tả sơ bộ dưới đây:
Chương 1: Khái quát về các trang tin tức và các hệ thống tổng hợp tin tức của Việt
Nam. Giới thiệu về các trang báo điện tử (trang tin tức) và các hệ thống tổng hợp tin tức.
Đánh giá ưu và nhược điểm của các hệ thống đó.
Chương 2: Cơ sở lý thuyết xây dựng mô hình hệ thống tổng hợp và phân loại tin tự
động. Giới thiệu về crawler, trích chọn thông tin từ tài liệu Web, phân lớp văn bản bằng
phương pháp entropy cực đại. Đồng thời chương này cũng giới thiệu về phương pháp
đánh giá hiệu suất của việc phân lớp văn bản thông độ hồi tưởng, độ chính xác và độ đo
F1.

2

Chương 3: Xây dựng hệ thống tổng hợp và phân loại tin tự động. Nêu ra các cơ sở
lý thực tiễn có thể áp dụng cho việc trích chọn thông tin đối với tài liệu Web. Đưa ra mô
hình hệ thống, các module, cách thức tương tác giữa các module với nhau. Từ đó nêu lên
được tính mở rộng cao của hệ thống.
Chương 4: Thực nghiệm và đánh giá kết quả để đánh giá bài toán mô hình được
xây dựng trong chương 3. Kết quả thực nghiệm cho thấy hiệu quả tốt của hệ thống tổng

nhất tại Việt Nam, theo xếp hạng của alexa.com.
Mặc dù vậy các báo điện tử của Việt Nam hiện nay, việc phân lớp (phân loại) tin tức
thường được làm thủ công bởi người viết báo hoặc người biên tập. Do vậy nhu cầu đặt ra
là cần có một hệ thống phân lớp văn bản Tiếng Việt, cho phép gán nhãn cho các tài liệu
một cách tự động. Khóa luận xin trình bày một phương pháp cho phép phân lớp các văn
bản hay tài liệu Web vào các lớp, dựa vào mô hình được trả về sau quá trình huấn luyện,
sẽ được trình bày kỹ hơn trong chương 2.
1.2. Khái quát chung về các hệ thống tổng hợp tin tức
Khoảng hơn một năm trở lại đây, các hệ thống tổng hợp tin tức của Việt Nam phát
triển rất mạnh. Sau đây khóa luận xin liệt kê ra một số hệ thống hiện đang được xem là
thành công nhất, đều nằm trong top 40 websites được truy cập nhiều nhất Việt Nam theo
xếp hạng của alexa.com.
 Baomoi.com: Có thể nói baomoi.com là trang tổng hợp tin nổi bật nhất hiện nay với
rất nhiều ưu điểm nổi trội so với các hệ thống tổng hợp báo khác:
• Ưu điểm:
- Baomoi.com được biết đến như là trang tổng hợp lấy tin từ nhiều nguồn nhất, từ
các báo điện tử lớn tin tức tổng hợp trên đủ lĩnh vực cho đến các báo chỉ chuyên về một
lĩnh vực (ví dụ: chỉ chuyên về ôtô-xe máy), hay đến cả các báo địa phương.
- Baomoi.com còn được biết đến như là trang tổng hợp tin có crawler tốt nhất, tin
tức sau khi xuất hiện trên trang gốc, chỉ sau một vài phút đã có tin tổng hợp trên
baomoi.com.

4

- Hỗ trợ tìm kiếm tin tức
• Nhược điểm: baomoi.com cho phép người đọc xem một tin chi tiết theo 2 cách,
tuy nhiên cả 2 cách đều có những vấn đề không tốt:
- Cách thứ nhất là xem trang gốc - website chứa bài báo quan tâm thông qua trang
của baomoi.com. Như vậy có nghĩa là báo mới đứng vai trò trung gian, nhận dữ liệu từ
webstie chứa bài báo và gửi nguyên vẹn đến cho người đọc. Cách làm này là cách phổ
6

 tintuc.xalo.vn:
• Ưu điểm:
- Tốc độ lấy tin của tintuc.xalo.vn là rất nhanh, có thể nói về tốc độ thì
tintuc.xalo.vn không hề thua kém baomoi.com.
- Tintuc.xalo.vn cho phép người đọc có thể dễ dàng truy cập đến bài báo gốc
nếu cần bằng một liên kết đặt phía dưới tiêu đề ở detail-page.
• Nhược điểm:
- Ở page-list khá nhiều tin của tintuc.xalo.vn gặp hiện tượng mất ảnh minh
họa

 tin247.com: Tốc độ lấy tin của tin247.com là khá chậm, tin tức sau khi xuất hiện ở
trang gốc khoảng vài giờ mới được cập nhật trên trang tin của tin247.com. Như vậy
thì nói chung không đáp ứng được nhu cầu cập nhật tin tức nhanh chóng như 2 trang
tổng hợp trên.

các độ đo là độ chính xác (P), độ hồi tưởng (R) và độ đo (F1).
2.1. Xây dựng crawler
2.1.1. Khái niệm crawler
Kích thước quá lớn và bản chất thay đổi không ngừng của Web đặt ra một nhu cầu
mang tính nguyên tắc là, cần phải cập nhật không ngừng tài nguyên cho các hệ thống trích
chọn thông tin trên Web. Thành phần crawler đáp ứng được nhu cầu này bằng cách đi
theo các siêu liên kết trên các trang Web để tải về một cách tự động nội dung các trang
Web. Web crawler khai thác sơ đồ cấu trúc của Web để duyệt không gian Web bằng cách
chuyển từ trang Web này sang trang Web khác.
9Hình 3. Sơ đồ cơ bản của một crawler đơn luồng [12]

Hình vẽ biểu diễn sơ đồ khối một crawler đơn luồng. Chương trình crawler yêu cầu
một danh sách các URL chưa được thăm (frontier). Ban đầu frontier chứa các URL hạt
nhân do người dùng hoặc chương trình khác cung cấp. Mỗi vòng lắp crawling bao gồm:
lấy ra các URL tiếp theo cần được tải về từ frontier, nạp trang Web tương ứng với URL
đó bằng giao thức HTTP, chuyển nội dung trang Web vừa được tải về cho phục vụ kho
chứa trang Web. Quá trình crawling được kết theo theo hai tình huống:
- Đạt được điều kiện dừng cho trước, chẳng hạn như số lượng các trang Web được
tải về đã đáp ứng được yêu cầu đặt ra.
- Danh sách các URL tại frontier rỗng, không còn trang Web yêu cầu crawler phải
tải về. Lưu ý rằng, điều kiện frontier rỗng được tính với một độ trễ nào đó, bởi có
[done]
[no URL]
Crawling Loop

trước tiên cần gieo cho frontier một hạt giống là URL trang Home (hoặc trang Portal) của
Web X đó.
Ví dụ đối với vnexpress.net thì trang Home có URL là:

Dùng giao thức HTTP để tải về mã html - gọi là Y - của URL hạt giống. Mã html Y
chứa rất nhiều các URL, trong đó chỉ một bộ phận nhỏ URL là siêu liên kết đến các
detail-page của một tin bài cụ thể là có giá trị, còn phần lớn các URL có trong Y đều là
liên kết không liên quan, chủ yếu là các liên kết quảng cáo
Nếu đưa tất cả các siêu liên kết này vào frontier thì sẽ là không tối ưu, do frontier
phải duyệt qua các URL không chứa nội dung thông tin, như vậy sẽ ảnh hưởng đến tốc độ
cập nhật tin mới của hệ thống, có thể gặp phải trường hợp như tin247.com ở trên. Để lấy
được các URL chứa nội dung thông tin cần thiết (phù hợp), khóa luận đưa ra một tập mẫu
cho phép nhận dạng thẻ HTML chứa siêu liên kết tới detail-page.
Ví dụ đối với báo vnexpress.net, từ mã html của trang Home có thể dễ dàng nhận
biết được các tin có nội dung thông tin được chứa trong các thẻ HTML với tên class như
là link-topnews, folder-topnews, other-foldernews, link-othernews hay link-title. Tập dữ
liệu đặc trưng này giúp dễ dàng nhận diện và lấy ra các siêu liên kết chứa nội dung thông
tin đưa vào frontier.
Để lấy được các tin mới một cách nhanh nhất, crawler dừng quá trình thêm vào URL
vào frontier sau chỉ một lần duyệt frontier hạt giống. Sau khi toàn bộ URL thuộc frontier
được xử lý hết, crawler được tạm dừng (delay) trong một khoảng thời gian xác định trước
khi lặp lại quá trình.

11

Việc xây dựng crawler cũng chính là xây dựng luật lấy URL từ tập các đặc trưng.
2.2. Xây dựng bộ trích chọn thông tin
2.2.1. Trích chọn thông tin trên tài liệu Web
Web là dữ liệu điển hình trong dữ liệu bán cấu trúc. Trích xuất thông tin Web đó là
vấn đề trích xuất các thành phần thông tin mục tiêu từ những trang Web. Một chương

- Phần thân bài báo
Tương tự với việc trích rút ra các URL để đưa vào frontier như phần crawler (2.1.2).
Xậy dựng bộ trích chọn tài liệu cũng là việc tạo ra một tập gồm các đặc trưng, cho phép
nhận biết để trích rút được các nội dung cần thiết như trình bày ở trên. Chính tập các đặc
trưng này, kết hợp với URL hạt giống và tập các đặc trưng nhận biết URL chứa nội dung
thông tin (được trình bày trong phần 2.1.2) tạo nên một tập dữ liệu đầu vào, cho phép
crawling, trích chọn ra nội dung thông tin của một trang Web bất kì.
2.3. Xây dựng bộ phân lớp
2.3.1. Khái niệm phân lớp văn bản
Phân lớp là một trong những mối quan tầm nhiều nhất của con người trong quá trình
làm việc với một tập hợp đối tượng. Điều này giúp con người có thể tiến hành việc sắp
xếp, tìm kiếm các đối tượng, một cách thuận lợi. Khi biểu diễn đối tượng vào hệ thống
thông tin, tính chất lớp vốn có của đối tượng trong thực tế thường được biểu diễn bằng
một thuộc tính “lớp” riêng biệt. Chẳng hạn, trong hệ thống thông tin quản lý tư liệu thuộc
thư viện, thuộc tính về loại tư liệu có miền giá trị là tập tên chuyên nghành của tư liệu,
gồm các giá trị như “Tin học”, “Vật lý”, Trước đây các công việc gán các giá trị của
thuộc tính lớp thường được làm một cách thủ công. Nhưng hiên nay, với sự bùng nổ của
thông tin và các loại dữ liệu, việc đánh thuộc tính lớp một cách thủ công là rất khó khăn,
có thể nói là không thể. Do vậy, cácphương pháp phân lớp tự động, trong đó có phân lớp
văn bản là rất cần thiết và là một trong những chủ đề chính của khai phá dữ liệu.
Phân lớp văn bản được các nhà nghiên cứu định nghĩa thống nhất như là việc gán
tên các chủ đề (tên lớp/nhãn lớp) đã được xác định cho trước vào các văn bản dựa trên nội
dung của nó. Phân lớp văn bản là công việc được sự dụng để hỗ trợ trong quá trình tìm
kiếm thông tin (Information Retrieval), chiết lọc thông tin (Information Extraction), lọc
văn bản hoặc tự động dẫn đường cho các văn bản tới những chủ đề xác định trước. 13
Tri thức
ngoài
Học
quy nạp
Các công cụ
phân lớp
Biểu diễn ban đầu
Biểu diễn ban
Biểu diễn cuối
Làm giảm số chiều
hoặc
l
ự
a ch
ọ
n thu
ộ
c tính

(1)14

2.3.2. Áp dụng thuật toán phân lớp entropy cực đại xây dựng bộ phân
lớp văn bản

Rất nhiều bài toán trong lĩnh vực xử lý ngôn ngữ tự nhiên (NLP) có thể được xem
xét dưới dạng các bài toán phân lớp với việc ước lượng xác suất có điều kiện
(

2.3.2.1. Biểu diễn các đặc trưng

Theo [1],[7] các đặc trưng (feature) được biểu diễn bằng các mệnh đề biểu diễn
thông tin ngữ cảnh (context predicate). Nếu A là tập các lớp thực hiện phân lớp và B là
tập các ngữ cảnh mà quan sát được, thì mệnh đề biểu diễn thông tin ngữ cảnh là một hàm
được mô tả như sau:
: { , }
cp B true false
→

Hàm này trả về giá trị true hoặc false, phụ thuộc vào sự xuất hiện hoặc không xuất
hiện của các thông tin hữu ích trong một số ngữ cảnh
b B
∈
. Tập các mệnh đề biểu diễn
thông tin ngữ cảnh được sử dụng rất nhiều trong các bài toán tuy nhiên với mỗi bài toán
thì người thực nghiệm phải cung cấp một tập thông tin ngữ cảnh riêng. Các mệnh đề biểu
diễn thông tin ngữ cảnh được sử dụng trong các đặc trưng – đó là một hàm có dạng như
sau:
: {0,1}
f A B
× →15

Và được mô tả dưới dạng:
( )
(
)

1
{ , , }
N
b b
…
được gắn nhãn tương ứng trong tập hợp các lớp
1
{ , , }
N
a a
…
, sau đó tiến hành học cho mô hình phân lớp entropy cực đại trên tập dữ liệu
huấn luyện đó. Ý tưởng tập dữ liệu huấn luyện bao gồm các cặp, mỗi cặp là một véc-tơ
giá trị logic cùng với một lớp tương ứng rất phổ biến và được sử dụng với rất nhiều các
thuật toán được mô tả trong các tài liệu về học máy.

 Học với ước lượng likelihood cực đại trên mô hình mũ
Để kết hợp các cứ liệu ta có thể đánh trọng số cho các đặc trưng bằng cách sử dụng
một mô hình log-linear hay mô hình mũ:
( )
( )
( )
,
1
1
,
i
k
f a b
i

điều kiện
( | ) 1
a
p a b
=
∑
. Mỗi tham số
i
λ
tương ứng với một đặc điểm
i
f
và có thể được
hiểu là “trọng số” của đặc điểm tương ứng (
i
λ
> 0). Khi đó xác suất
(
)
,
p a b
là kết quả
được chuẩn hoá của các đặc trưng có ý nghĩa với cặp
(
)
,
a b
, tức là với các đặc điểm
i
f

Q p p a b
Z b
λ
=
= =
∏

,
( ) ( , )log ( , )
a b
L p p a b p a b
=
∑

*
argmax ( )
q Q
p L q
∈
=

trong đó
Q
là tập hợp các mô hình của dạng log-linear,
( | )
p a b
là xác suất thực
nghiệm trên tập T,
( )
L p

là phân phối
“không chắc chắn nhất” (entropy đạt cực đại) thoả mãn k ràng buộc trên các kì vọng của
các đặc điểm:
*
argmax ( )
p P
p H p
∈
=

,
( ) ( , )log ( , )
a b
H p p a b p a b
=
∑