ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

VŨ NGỌC ANH
NGHIÊN CỨU CÔNG NGHỆ KHAI PHÁ DỮ LIỆU VĂN BẢN,
ÁP DỤNG CHO CÁC TRANG TIN TỨC TRÊN CÁC THIẾT BỊ
CẦM TAY (PDAS & SMARTPHONES)
LUẬN VĂN THẠC SỸ KHOA HỌC
HÀ NỘI-2006
Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

VŨ NGỌC ANH
NGHIÊN CỨU CÔNG NGHỆ KHAI PHÁ DỮ LIỆU VĂN BẢN,
ÁP DỤNG CHO CÁC TRANG TIN TỨC TRÊN CÁC THIẾT BỊ
CẦM TAY (PDAS & SMARTPHONES)
NGÀNH CÔNG NGHỆ THÔNG TIN
CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ: 01.01.10

LUẬN VĂN THẠC SỸ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HÀ QUANG THỤY
HÀ NỘI-2006
Kênh tin tức điện tử cho các thiết bị cầm tay

CÁC HÌNH MINH HỌA 8
MỞ ĐẦU 9
CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬ TRÊN THIẾT
BỊ CẦM TAY 12

1.1. Báo điện tử và công nghệ Internet không dây 12
1.1.1. Báo điện tử - một thành tựu của Internet 12
1.1.2. Sự phát triển của các thiết bị cầm tay 13
1.1.3. Công nghệ kết nối internet không dây 14
1.2. Bài toán xây dựng kênh tin tức điện tử trên thiết bị cầm tay 15
1.2.1. Mô tả bài toán 15
1.2.2. Mô tả các chức năng cơ bản của hệ thống 16
1.3. Hướng tiếp cận giải quyết bài toán 16
Chương II. THUẬT TOÁN RTDM VÀ ỨNG DỤNG TRONG TRÍCH XUẤT
TIN 18

2.1. Khái niệm “Chi phí chuyển đổi cây” 18
2.2. Thuật toán RTDM 22
2.3. Áp dụng RTDM trích xuất tin tức tự động 29
2.3.1 Phân cụm trang 31
2.3.2 Trích xuất mẫu chung 32
2.3.3 Khớp dữ liệu 35
2.3.4 Gán nhãn dữ liệu 37
Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 4 Chương III . PHÂN TÍCH THIẾT KẾ HỆ THỐNG 39

cấp tin tức hàng ngày của các tờ báo phổ biến nhất tại Braxin.
Luận văn đã tiến hành chi tiết và hoàn thiện các phần nội dung không công bố
của thuật toán RTDM, đồng thời tiến hành xây dựng một hệ thống kênh cung
cấp tin điện tử trên các thiết bị cầm tay thông minh. Hệ th
ống thử nghiệm việc
trích chọn tin tức trên các báo điện tử tiếng Việt phổ dụng hiện nay và đã cho
kết quả đáng khích lệ. Chúng tôi đang tiến hành cải tiến tốc độ làm việc của hệ
thống nhằm tiến tới đưa hệ thống vào hoạt động thực tế.

Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 6 CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT

Từ viết tắt Giải nghĩa
RTDM Restricted Top-Down Mapping
PDA Personal digital assistant
Data extraction Trích xuất dữ liệu
Trees Cây biểu diễn cấu trúc trang HTML
Edit distance Chi phí chuyển đổi giữa 2 cây (thay thế, chèn, xoá nút)
PK Primary Key
FK Foreign Key
PF Primary & Foreign Key
T
x
Cây biểu diễn trang Web.
T


Miêu tả sự phụ thuộc lẫn nhau của các đối
tượng Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 8 CÁC HÌNH MINH HỌA

Hình 3 - Ví dụ về ánh xạ giữa 2 cây 20
Hình 4 – Ví dụ ánh xạ trên-xuống 21
Hình 5 – Một ví dụ về ánh xạ trên xuống hạn chế 23
Hình 6 - Một mẫu tin chi tiết Quốc tế trên trang tienphongonline.com.vn 30
Hình 7: Các bước trích xuất tin tức [28] 31
Hình 8 - Các bước hình thành ne-pattern từ các nhóm 37
Hình 9 : Gói các lớp quản lý các cây HTML Error! Bookmark not defined.
Hình 10 : Gói các lớp phục vụ tính toán giá trị RTDM 46
Hình 11 : Gói các lớp quản lý các trang tin tức 46

Kênh tin tức điện tử cho các thiết bị cầm tay

Luận văn sử dụng thuật toán RTDM (Restricted Top-Down Mapping) do Davi
de Castro Reis và các đồng tác giả đề xuất [28], một thuật toán được đánh giá
rất hiệu quả trong việc trích xuất tin tức tức tự động thông qua việc phân tích
cấu trúc cây.
Thuật toán RTDM được cải tiến trên thuật toán trích xuất thông tin Web đã có
để áp dụng đặc thù riêng cho bài toán trích xuất tin tức. Qua thực nghiệm trên
35 trang tin tức, thuật toán RTDM cho kết quả trung bình 87.71% trích xuất tin
tức thành công không cần có sự can thiệp của con người. Hiện tại, RTDM
được sử
dụng như là thành phần lõi chính của hệ thống trích xuất tin tức có tên
là AkwanClipping (Akwan Information Technologies, ,
Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 10 thuộc công ty Google tại Braxin) cung cấp tin tức hàng ngày của các tờ báo
phổ biến nhất tại Braxin.
Chúng tôi đã chi tiết và hoàn thiện các nội dung không công bố của thuật toán
RTDM, đồng thời tiến hành xây dựng một hệ thống kênh cung cấp tin điện tử
trên các thiết bị cầm tay thông minh. Hệ thống thử nghiệm đã trích chọn thông
tin trên các báo điện tử tiếng Việt phổ dụng hiện nay. Chúng tôi đã tiến hành
đánh giá hệ thống và các kết quả đánh giá cho thấy hệ thống là hữu dụng. Tuy
nhiên, để đưa hệ thống vào hoạt động thực tiễn cần phải nghiên cứu tăng tốc độ
hoạt động của nó.
Nội dung của luận văn được tổ chức thành bốn chương được giới thiệu sơ bộ
như dưới đây.
Chương 1. Xây dựng kênh tin t
ức điện tử trên các thiết bị cầm tay giới thiệu sự


Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 12 CHƯƠNG I. XÂY DỰNG KÊNH CUNG CẤP TIN ĐIỆN TỬ
TRÊN THIẾT BỊ CẦM TAY
1.1. Báo điện tử và công nghệ Internet không dây
1.1.1. Báo điện tử - một thành tựu của Internet
Đọc báo chí, xem tin tức là một nhu cầu không thể thiếu của mỗi người trong
xã hội thông tin, không phân biệt lứa tuổi. Các loại báo chí được phát hành đa
dạng về nội dung, hình thức phù hợp với nhu cầu riêng biệt của từng độc giả.
Hiện nay, với sự phát triển lớn mạnh của internet kéo theo sự bùng nổ thông
tin, thông qua các trang báo điện tử. Chỉ với m
ột thao tác tìm kiếm đơn giản, ta
cũng có thể tìm được hàng trăm đến hàng ngàn trang báo đủ chủng loại. Chẳng
hạn ta sử dụng công cụ tìm kiếm của Google để tìm theo từ khoá "Báo điện tử"
và những trang từ Việt nam, hàng loạt các trang tin tức được liệt kê như
vietnamnet.vn, vnexpress.net, dantri.com.vn, tuoitre.com.vn… Theo thống kê
của google.com.vn thì có đến 755.000 kết quả tìm được, tất nhiên trong số đó
rất nhiều các kết quả là trùng nhau, nhưng con s
ố đó cũng đủ để nói lên sự phát
triển lớn mạnh về số lượng của các trang tin tức điện tử tại Việt Nam hiện nay.
Một ưu điểm lớn của các tin tức trên các trang báo điện tử đó là tính thời sự,
cập nhật rất cao. Đối với các tin tức trên báo in giấy, có khi ta phải đợi đến
ngày hôm sau mới được xem. Nhanh nhất như báo "Thể thao Việ
t nam", cũng
phải đến 5h sáng hôm sau mới có thể đăng thông tin về các trận đấu trong buổi

Times,
Washington
Post, số người
đọc báo qua
mạng đã vượt
trội số người
đọc báo in (New York Times: 12,8 triệu/5 triệu; Washington Post: 7.8 triệu/1.8
triệu, Los Angeles Times: 4.3 triệu/2.4 triệu)
1,2
.
Cũng vì sự phát triển bùng nổ như vậy nên việc đọc thông tin trên báo điện tử
một cách hiệu quả cũng không phải là dễ dàng. Hiện tượng người đọc báo điện
tử khó kiểm soát tin và nội dung tin đã đọc đã trở thành thực tế. Cần thiết xây
dựng phương tiện hỗ trợ người dùng giải quyết hiện tượng nói trên.
1.1.2. Sự phát triển của các thiế
t bị cầm tay
Ngày nay, với sự phát triển vượt bậc của khoa học công nghệ, các sản phẩm
cầm tay đã thực sự đem lại rất nhiều hiệu quả lao động cho con người. Các
thiết bị có thể kể đến ở đây là các điện thoại thông minh (smart phone), máy
tính bỏ túi (pocket pc). Cùng với sự phát triển công nghệ, các thiết bị này đã
được hỗ trợ khả năng lướ
t Web không dây với tốc độ ngày càng cải thiện. Do
đó, đây cũng là một kênh tiếp cận thông tin, tin tức điện tử thuận tiện nhanh
chóng, gọn nhẹ mọi lúc mọi nơi. Hơn thế nữa, do nhu cầu công việc của con
người cộng với giá cả cũng hợp lý nên các thiết bị này cũng ngày càng được
dùng phổ biến hơn (nhiều nhất vẫn là trong các doanh nghiệp). Những thuận 2


công nghệ WiMAX đang đượ
c sử dụng làm công nghệ không dây cố định cho
truy cập băng rộng đầu cuối trong năm 2005 và sẽ tiến tới di động hoàn toàn
trong những năm tới
4

Chưa cần đến khả năng kết nối tốc độ cao, các dịch vụ truy cập internet di
động cũng sẽ được hình thành tại VN trong thời gian tới với tốc độ chấp nhận
được 156Kbps đối với các thiết bị di động. Dịch vụ băng rộng di động của
EVN Telecom sử dụng công nghệ CDMA 2000-1X, tần số 450 Mhz, cho phép
người sử dụng kết nối Internet trực tiếp trên máy đ
iện thoại hoặc thông qua
máy tính cá nhân với tốc độ 156 Kbps đối với mạng 1X tại bất cứ nơi nào có
phủ sóng
5
. 3

4

5

Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 15
- Yêu cầu: xác định được các mục tin của các trang báo điện t
ử, trong các trang
chi tiết, hệ thống phải xác định được các vùng tin cần trích xuất, vùng tin có
thể loại bỏ. Các vùng tin tức sau khi trích xuất sẽ được định dạng lại cho phép
hiển thị trên thiết bị cầm tay.
- Đề xuất giải pháp:
Sử dụng kĩ thuật phân tích cấu trúc trang tin sử dụng thuật toán RTDM [28].
Giải pháp này áp dụng định dạng cho các trang tin bất kì có thể xem được trên
các màn hình thiết bị cầm tay có kích thước hạ
n chế.
b) Chức năng xử lý trang tin
- Yêu cầu: xử lý nội dung trang tin cần xem, xác định kiểu trang tin, lọc bỏ các
thông tin dư thừa và xây dựng lại trang tin cho phép hiển thị trên thiết bị cầm
tay.
c) Chức năng định dạng hiển thị tin trên các thiết bị cầm tay
- Yêu cầu: Hiển thị các trang tin (phân phối giữa hình ảnh, văn bản cho phù
hợp để có thể hiển thị tốt trên các thiết b
ị cầm tay)
- Đề xuất giải pháp: Bản thân các trình duyệt trên các thiết bị cầm tay khi kết
nối vào một trang bất kì sẽ hiển thị hết nội dung của trang đó, do vậy ta xây
dựng một Web site thu nhỏ kích thước của trang Web tin tức. Công việc chỉnh
sửa này thực hiện trên Web server sẽ làm tăng hiệu quả hoạt động của thiết bị
cầm tay do tốc độ xử lý của các thiế
t bị cầm tay là không yêu cầu cao.
1.3. Hướng tiếp cận giải quyết bài toán
Nội dung đề tài này là giải quyết bài toán phân cụm các trang web theo nội
dung. Trên cơ sở bài toán phân cụm các trang web, hệ thống tìm ra các khuôn
mẫu trang Web trong một site cung cấp tin tức điện tử, mỗi khuôn mẫu đó
Kênh tin tức điện tử cho các thiết bị cầm tay


Phiên bản chi tiết của thuật toán RTDM do luận văn đề xuất. Ngoài ra, luận
văn cũng đưa ra một số nhận xét, ý tưởng có thể dùng để cải tiến thuật toán.
Theo Davi de Castro Reis và các đồng tác giả [28], cấu trúc của các trang Web
có thể được biểu diễn dưới dạng một cây (Ví dụ như Cây DOM), vì vậy chúng
ta sử dụng khái niệm chi phí chuyển đổi cây (Tree Edit Distance) để đánh giá
mức độ giống nhau giữa các trang. Mộ
t cách trực quan, khoảng cách giữa hai
cây T
A
và T
B
là "giá tối thiểu" phải trả cho một tập các thao tác để chuyển đổi
T
A
thành T
B
.
Mặc dù có thể áp dụng cho cây bất kỳ, nhưng để thuận tiện áp dụng nên trong
luận văn này, chúng tôi tập trung chủ yếu vào cây có thứ tự, được gán nhãn, có
gốc cố định (labeled ordered rooted tree). Một cây có gốc (rooted tree) là cây
có đỉnh gốc là cố định. Cây có thứ tự có gốc (ordered rooted tree) là cây có gốc
cố định và thứ tự các con là cố định với mỗi đỉnh. Cây có thứ tự, được gán
nhãn, có gốc cố
định là cây có mỗi đỉnh được gán nhãn l. Từ đây về sau, chúng
ta sẽ đơn giản sử dụng khái niệm "cây" để chỉ cây có thứ tự, được gán nhãn, có
gốc cố định, các trường hợp khác sẽ được chú thích cụ thể.
Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 19

1
kích thước n
1
và cây T
2
kích thước n
2
là một tập hợp M các
cặp có thứ tự (i, j) thoả mãn các điều kiện sau với mọi (i
1
, j
1
), (i
2
, j
2
)
∈
M:
• i
1
= i
2
khi và chỉ khi j
1
= j
2
.
• T
1

2
[j
1
] là tổ tiên của T
2
[j
2
]

Hình 1 - Ví dụ về ánh xạ giữa 2 cây
Điều kiện 1 xác định một đỉnh của một cây không xuất hiện quá 1 lần trong
ánh xạ, điều kiện thứ 2 bảo toàn thứ tự trái - phải giữa các nút, còn điều kiện
thứ 3 đảm bảo cấu trúc phân cấp giữa 2 cặp nút trong ánh xạ.
Nói một cách đơn giản, phép ánh xạ cho phép mô tả các bước hiệu chỉnh từ
cây này thành cây kia, không quan tâm đến thứ tự các thao tác được áp dụng.
Trong hình 3, những đườ
ng nét đứt giữa các đỉnh của cây T
1
và các đỉnh của
cây T
2
phải thay đổi nếu các đỉnh này khác nhau, các đỉnh còn lại không phải
thay đổi. Đỉnh không có đường nào nối tới trên cây T
1
là đỉnh sẽ bị xoá, còn
đỉnh không có đường nào nối tới trên cây T
2

Thuật toán đầu tiên về bài toán ánh xạ (được giới thi
ệu trong tài liệu [18]) với
độ phức tạp là O(n
1
n
2
h
1
h
2
) với n
1
và n
2
là kích thước của cây, h
1
và h
2
là độ cao
tương ứng. Đây là thuật toán tính toán động thực hiện việc tính toán đệ quy chi
phí chuyển đổi giữa các xâu biểu diễn tập hợp các đỉnh con của các đỉnh của
cây. J. T. L. Wang và các đồng tác giả [21] đã giới thiệu một thuật toán với độ
phức tạp
O(d
2
n
1
n
2
min(h

2
)
∈
M, ta cũng có một cặp (cha(i
1
), cha(i
2
))
∈
M với i
1
và i
2
tương ứng không
phải là nút gốc của T
1
và T
2
.
Hình 2 – Ví dụ ánh xạ trên-xuống
Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 22

Trong bài toán "Trích xuất tin tức tự động", luận văn này chỉ quan tâm đến vấn
đề xác
định sự tương đồng giữa cấu trúc của các trang Web. Thực sự là các
trang Web có cấu trúc hoặc là cấu trúc HTML hoặc là XML, như đã đề cập ở
trên, có thể biểu diễn dưới dạng cây có thứ tự được gán nhãn, có gốc cố định.
Thường mô hình DOM được vận dụng để mô tả cây.
Trong phần tiếp theo sẽ trình bày thuật toán mới xác định chi phí ánh xạ giữa
các cây biểu diễn cấu trúc của các trang Web cho lớp bài toán gi
ới hạn đó là
ánh xạ trên-xuống, kết quả của thuật toán này chính là chi phí chuyển đổi giữa
các cây đó.
2.2. Thuật toán RTDM
Mục này sẽ trình bày một thuật toán xác định một kiểu ánh xạ "trên-xuống hạn
chế" (Restricted Top-Down Mapping) [28]. Một cách trực quan, trong phép
ánh xạ trên-xuống hạn chế, các thao tác chèn, xóa, thao tác thay thế các đỉnh
chỉ hạn chế thao tác với các lá của cây.
Kênh tin tức điện tử cho các thiết bị cầm tay Vũ Ngọc Anh – K9T3 Trang 23 Định nghĩa 3 [28]
Một ánh xạ trên-xuống M giữa cây T
1
và cây T
2
được gọi là trên-xuống hạn
chế khi và chỉ khi với mọi cặp (i
1Hình 3 – Một ví dụ về ánh xạ trên xuống hạn chế
Theo [28], thuật toán RTDM là kết hợp giữa ý tưởng được nêu trong các công
trình [19, 25]. Để xác định ánh xạ giới hạn trên-xuống giữa 2 cây T
1
và T
2
, đầu
tiên thuật toán RTDM tìm các cây con cùng mức giống hệt nhau của T
1
và T
2
.
Bước này của thuật toán thực hiện trong thời gian tuyến tính sử dụng đồ thị các
lớp tương đương thực hiện tương tự như trong [19], tuy nhiên thuật toán trong
[28] thực hiện duyệt cây theo thứ tự sau và cách tiếp cận đơn giản hơn vì chỉ
quan tâm đến những cây con cùng mức giống hệt nhau. Sau khi các đỉnh của
cây được nhóm thành các lớp tương đương, chúng ta áp dụng thuật toán của
Yang [25] để tìm ánh xạ
trên-xuống hạn chế nhỏ nhất giữa các cây. Nội dung
thuật toán RTDM được trình bày như sau:
1
RTDM(T
1
, T
2
,

0
∀
j = 0, n
7
for i=1 to m do
8 for j=1 to n do
9
C
i

←
{con của (t
1
[i])}
10
C
j

←
{con của (t
2
[j])}
11
d
←
M[i - 1, j] + tổng_chi_phí_xoá(T
1
[k]); (T
1
[k] là các đỉnh

[j] là các cây con giống nhau
16
s
←
0
17
elseif
18 if T
1
[i] là lá
19
s
←
chi_phí_thay_thế(T
1
[i], T
2
[j])
20
s
←
s + tổng_chi_phí_chèn (T
2
[k]) ; (T
2
[k] là các đỉnh
∈
C
j
)

[i], T
2
[j],
ε
)
26
end if
27
end if