ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Tiến Thành BÀI TOÁN TRÍCH XUẤT THÔNG TIN CHO DỮ LIỆU
BÁN CẤU TRÚC VÀ ÁP DỤNG XÂY DỰNG HỆ THỐNG
TÌM KIẾM GIÁ CẢ SẢN PHẨM 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 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Tôi chân thành cảm ơn các thầy, cô đã tạo cho tôi những điều kiện thuận lợi để tôi
học tập và nghiên cứu tại tr
ường Đại Học Công Nghệ.
Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong nhóm “Khai
phá dữ liệu” đã giúp tôi rất nhiều trong việc thu thập và xử lý dữ liệu.
Tôi xin gửi lời cảm ơn tới các bạn trong lớp K50CA và K50CHTTT đã ủng hộ
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.
Tôi xin chân thành cảm ơn ! Sinh viên
Vũ Tiến Thành
i
Tóm tắt nội dung
Trích xuất thông tin từ dữ liệu bán cấu trúc là một bài toán được sự quan tâm tại
nhiều hội nghị lớn trên thế giới [9],[10],[12],[13]. Bài toán này là một thành phần không
thể thiếu trong các ứng dụng về thu thập và trích xuất thông tin hiện nay. Một trong
những ứng dụng đó là trích xuất thông tin của sản phẩm từ các trang thương mại điện tử
1.2.1 Vấn đề đặt ra với bài toán ....................................................................................6
1.2.2 Một số phương pháp trích xu
ất thông tin cho dữ liệu bán cấu trúc .....................6
1.2.3 Phương pháp đánh giá..........................................................................................7
1.2.4 Ứng dụng của bài toán trích xuất thông tin cho dữ liệu bán cấu trúc..................8
Chương 2. Một số phương pháp sử dụng trong bài toán trích xuất thông tin cho dữ
liệu bán cấu trúc ...............................................................................................................10
2.1 Trích xuất thông tin dựa vào cây DOM....................................................................10
2.1.1 Khái nhiệm cây DOM........................................................................................10
2.1.2 Xây dựng cây DOM...........................................................................................11
2.1.3 Sử dụng cây DOM để trích xuất thông tin .........................................................12
2.2 Trích xuất thông tin dựa theo các mẫu biểu thức chính qui .....................................13
iii2.2.1 Khái niệm biểu thức chính qui...........................................................................13
2.2.2 Sử dụng biểu thức chính qui để trích xuất thông tin..........................................14
2.3 Một số giải thuật trích xuất thông tin cho dữ liệu bán cấu trúc................................14
2.3.1 Hai kiểu biểu diễn của các trang giàu dữ liệu....................................................14
2.3.2 Một số giải thuật điển hình ................................................................................16
Chương 3. Áp dụng bài toán trích xuất thông tin bán cấu trúc để xây dựng hệ thống
tìm kiếm giá cả sản phẩm ................................................................................................21
3.1 Khái quát hệ thống tìm kiếm giá cả của s
ản phẩm ...................................................21
3.1.1 Khái niệm...........................................................................................................21
3.1.2 Các phương pháp xây dựng ...............................................................................21
3.1.3 Các hệ thống hiện tại..........................................................................................22
3.2 Cơ sở thực tiễn..........................................................................................................23
3.3 Cơ sở khoa học .........................................................................................................25
HTML HyperText Markup Language
URL Uniform Resource Locator
XPath XML Path
W3C World Wide Web Consortium viDanh sách các hình
Hình 1. Ví dụ về tính cấu trúc của trang web bán cấu trúc ..................................................4
Hình 2. Ví dụ về bài toán nhận dạng thực thể......................................................................5
Hình 3. Ví dụ về trích xuất nội dung chính của trang Web..................................................8
Hình 4. Ví dụ về hệ thống tìm kiếm giá cả...........................................................................9
Hình 5. Ví dụ xây dựng cây DOM sử dụng hộp ảo............................................................12
Hình 6. Dạng biểu diễn của trang list page ........................................................................15
Hình 7. Dạng biểu diễn của trang detail page ....................................................................15
Hình 8. Chuyển đổi từ mã HTML sang cây EC.................................................................16
Hình 9. Ví dụ giải thuật RoadRunner [12] .........................................................................20
Hình 10. Trang giới thiệu sản phẩ
m HP CQ60-203TX......................................................24
Hình 11. Trang giới thiệu sản phẩm HP CQ60-101TX......................................................24
Hình 12. Biểu diễn cây DOM của mã HTML hai trang về sản phẩm HP..........................25
Hình 13. Ví dụ về trang kinh doanh thông thường.............................................................26
Hình 14. Ví dụ về trang rao vặt ..........................................................................................27
Hình 15. Ví dụ về trích xuất giá trong một trang web........................................................27
Hình 16. Ví dụ về sản phẩm chứa những giá không đúng .................................................29
Hình 17. Ví dụ về trích xuất giá thực của trang sản phẩm.................................................29
Hình 18. Tập luật trích xuất giá sản phẩm..........................................................................32
Hình 19. Luật trích xuất ảnh sản phẩm...............................................................................33
1Giới thiệu
Nhưng năm gần đây, cùng với sự phát triển mạnh mẽ của hạ tầng cơ sở mạng cũng
như công nghệ lưu trữ Internet đã trở thành một thành phần không thể thiếu trong đời
sống con người. Hàng loạt các ứng dụng dựa trên nền tảng của Internet đã ra đời để phục
vụ cho nhu cầu, lợi ích của con người. Nổi bật lên trong các ứng dụ
ng đó chính là các ứng
dụng liên quan đến thương mại điện tử. Thương mại điện tử ra đời giúp con người giảm
thiểu tối đa thời gian cũng như chi phí khi tham gia giao dịch hàng hóa.Tuy nhiên cùng
với sự phát triển của thông tin trên Internet thì các thông tin liên quan đến thương mại
điển tử cũng bùng nổ không kém, hàng loạt các trang web bán hàng trực tuyến cùng với
nó là hàng triệu sản phẩm và các thông tin liên quan đến sản phẩm làm cho con người khó
kh
ăn trong việc tìm kiếm. Các câu hỏi: Sản phẩm nào tốt ? Giá cả cửa hàng nào tốt hơn ?
Tìm kiếm thông tin của sản phẩm ở đâu ?... làm con người khó khăn khi lựa chọn một sản
phẩm cần giao dịch. Giải pháp cho vấn đề này đó chính là cần có một hệ thống tìm kiếm
phục vụ cho nhu cầu tìm kiếm này của con người các hệ thống này thường được biết đến
với tên gọi hệ thống tìm kiếm giá cả sản phẩm.
Chính từ nhu cầu thực tế đấy, hệ thống tìm kiếm giá cả đã được sự quan tâm của rất
nhiều công ty lớn như Yahoo, Google, Amazon…bên cạnh đó nó cũng được sự quan tâm
của công động nghiên cứu khoa học. Nhiều bài báo liên quan đến các thành phần của hệ
thống cũng xuất hiện trên nhiều hội nghị lớn c
ủa thế giới như: WWW
1
,
SIGMOD
2
Chương 2. Một số phương pháp sử dụng trong bài toán trích xuất thông tin
cho dữ liệu bán cấu trúc giới thiệu về các sử dụng cây DOM và biểu thức chính
qui để trích xuất thông tin. Chương này cũng đề c
ập đến hai giải thuật trích
xuất tiêu biểu đó là giải thuật dựa trên hệ thống Stalker và giải thuật
RoadRunner.
Chương 3. Áp dụng trích xuất thông tin bán cấu trúc để xây dựng hệ thống tìm
kiếm giá cả sản phẩm nêu khái niệm về hệ thống tìm kiếm giá cả, giới thiệu các
hệ thống hiện tại. Chương này cũng đề cập đến cơ sở thực tiễ
n về công nghệ
web hiện tại , từ cơ sở thực tiễn kết hợp với bài toán trích xuất thông tin từ dữ
liệu bán cấu trúc để xây dựng cơ sở lý thuyết để trích xuất thông tin giá cả của
sản phẩm, đưa ra mô hình của hệ thống và nêu được tính mở của hệ thống đề
xuất.
Chương 4. Thực nghiệm và đánh giá kết quả để đ
ánh giá các bài toán nêu ở
phần cơ sở lý thuyết tại chương 3 về trích xuất giá cả của sản phẩm. Kết quả
thực nghiệm cho thấy được hiệu quả của phương pháp trích xuất giá cả sản
phẩm.
Phần kết luận tóm lược nội dung chính của khóa luận và nêu định hướng phát
triển trong thời gian tới.
3Chương 1. Khái quát bài toán trích xuất thông tin cho dữ
liệu bán cấu trúc
Chủ đề chính của khóa luận là áp dụng bài toán trích xuất thông tin cho dữ liệu bán
cấu trúc để xây dựng hệ thống tìm kiếm giá cả. Chương này sẽ giới thiệu bài toán trích
xuất thông tin nói chung và bài toán trích xuất thông tin cho dữ liệu bán cấu trúc nói
dữ liệu .
Các trang web thông thường là một dạng tiêu biểu của dữ liệu bán cấu trúc, những
thành phần có cấu trúc trong trang web đó là dữ liệu được lấy từ tầng cơ sở dữ liệu (có
cấu trúc) bên dưới và hiện thị trên web thông qua các thẻ HTML…
Hình 1: Mô tả dữ liệu bán cấu trúc về trang sản phẩm, dữ liệu này chứ
a tên các sản
phẩm, giá sản phẩm và các thông tin chi tiết về sản phẩm. Các thông tin ứng với từng sản
phẩm được mô tả dưới dạng mã HTML đã định trước. Dữ liệu này được lấy từ tầng cơ sở
dữ liệu (có cấu trúc) bên dưới và hiển thị trên trang web thông qua các thẻ HTML. Đây
chính là thành phần có cấu trúc của trang web.
Hình 1. Ví dụ về tính cấu trúc của trang web bán cấu trúc
1.1.3 Các hướng tiếp cận trong bài toán trích xuất thông tin
Các bài toán trích xuất thông tin thông thường được tiếp cận theo dữ liệu mà bài
toán đó xử lý. Vì vậy có những dạng bài toán như sau:
Cấu trúc HTML
giống nhau
5• Dữ liệu có cấu trúc
Đối với dữ liệu có cấu trúc, việc trích xuất thông tin là khá đơn giản. Vì các thông
tin đã được biểu diễn theo những định dạng chuẩn của bảng, thực thể.. nên có thể lấy
được những thông tin cần thiết một các dễ dàng dựa vào những truy vấn.
Ví dụ: dữ liệu có cấu trúc được lưu trữ trong hệ quản trị cơ sở dữ li
ệu MS SQL,
MySQL có thể trích xuất được những thông tin cần thiết dựa vào các lệnh SQL như
SELECT, JOIN.
• Dữ liệu không cấu trúc
Đối với dữ liệu không cấu trúc thì có một số bài toán về trích xuất thông tin như
nên quan
trọng.
Bài toán này đã được bắt đầu nghiên cứu vào giữa những năm của thập niên 1990
bởi nhiều công ty và các nhà nghiên cứu[2].
1.2.2 Một số phương pháp trích xuất thông tin cho dữ liệu bán cấu trúc
Như ta đã nói về một số hướng tiếp cận ở mục 1.1.3 đối với dữ liệu bán cấu trúc thì
bài toán trích xuất có một số phương pháp điển hình như:
• Phương pháp thủ công
Quan sát một trang Web và mã nguồn của nó, người lập trình sẽ tìm một vài mẫu và
viết chương trình để trích xuất các dữ liệu mục tiêu. Để làm đơn giản hơn cho người lập
trình, một vài ngôn ngữ
miêu tả mẫu và các giao diện người dùng đã được xây dựng. Tuy
nhiên với phương pháp này thì không thể làm việc với một số lượng lớn các trang[2].
7• Wrapper qui nạp
Đây là phương pháp bán tự động. Nó được đề xuất vào khoảng năm 1995-1996.
Trong phương pháp này thì một tập hợp các luật trích xuất được học từ một bộ các trang
đã được gán nhãn bằng tay. Sau đó các luật này sẽ được dùng để trích xuất các thành phần
dữ liệu từ những trang có định dạng tương tự. Một số giải thuật tiêu biểu như: Stalker[5],
WIEN[13] (được sử
dụng trong máy tìm kiếm lycos).
• Phương pháp tự động
Được đề xuất trong năm 1998, phương pháp này tự động tìm các mẫu hoặc các cấu
trúc để trích xuất thông tin từ những trang cho trước. Vì phương pháp này không cần đến
sự gán nhãn bằng tay nên nó có thể trích xuất được dữ liệu từ một lượng khổng lồ các
trang; một số giải thuật tiêu biểu như RoadRunner[12], bootstrapping[1].
1.2.3 Phương pháp đánh giá
xP =
= 92,78 %
81.2.4 Ứng dụng của bài toán trích xuất thông tin cho dữ liệu bán cấu trúc
• Nhận dạng và trích xuất nội dung chính của trang Web
Với một trang web ngoài những thành phần mang thông tin chính thì còn những
thành phần ít có ý nghĩa về mặt thông tin như quảng cáo, các menu.... Việc nhận dạng và
trích xuất nội dung chính của trang web giúp giảm thiểu việc lưu trữ thông tin và tối ưu
kết quả trả về trong các máy tìm kiếm vì máy tìm kiếm chỉ phải lưu nội dung chính của
trang web và tìm kiếm trong nội dung chính này. Các giải thuật được đề xuấ
t như
ContentExtractor và FeatureExtractor của Debnath[9],[10].
Hình 3. Ví dụ về trích xuất nội dung chính của trang Web
Nội dung chính
9• Hệ thống tìm kiếm giá cả sản phẩm
Hệ thống cho phép người sử dụng so sánh được giá cả của sản phẩm mà họ
muốn mua. Hệ thống này phải duyệt qua các trang web kinh doanh sản phẩm để
trích xuất các thông tin hữu dụng về sản phẩm.
Hình 4. Ví dụ về hệ thống tìm kiếm giá cả
Dạng biểu diễn cây DOM của mã HTML
112.1.2 Xây dựng cây DOM
Xây dựng cây DOM từ những trang Web đầu vào là một bước cần thiết trang nhiều
giải thuật trích xuất dữ liệu [2]. Có hai phương pháp cơ bản để xây dựng các cây DOM.
- Sử dụng các thẻ riêng biệt
Hầu hết các thẻ HTML làm việc trong một cặp. Mỗi cặp chứa một thẻ mở <> và một
thẻ đóng </>. Bên trong mỗi cặp thẻ có thể có những cặp thẻ khác, kết quả là c
ấu trúc trở
nên chồng chéo. Xây dựng một cây DOM từ một trang Web bằng cách sử dụng mã
HTML của nó là một vấn đề cần thiết. Trong một cây DOM, mỗi cặp thẻ là một node,
những cặp thẻ ẩn bên trong là node con của node hiện tại. Có hai nhiệm vụ cần thi hành
đó là:
¾ Làm sạch mã HTML: Một vài thẻ không cần thẻ đóng (như <li>, <hr>,<p>) mặc
dù chúng có thẻ đóng. Bởi vậy một thẻ đóng nên
được chèn vào để tất cả các thẻ
được cân bằng. Các thẻ được định dạng không tốt cũng cần thiết được sửa chữa.
Một thẻ sai thường là một thẻ đóng, đó là thẻ cắt ngang các khối ẩn bên trong. Ví
dụ: <tr> … <td> … </tr> … </td>, sẽ rất khó để sửa lỗi trường hợp này nếu
tồn tại sự chồng chéo đa cấp. Có một vài ph
ần mềm mã nguồn mở để làm sạch
mã HTML, một số những phần mềm thông dụng như: JTidy, NekoHTML,
HTMLCleaner.
¾ Xây dựng cây: Chúng ta có thể đi theo các khối con của các thẻ HTML để xây
dựng được cây DOM.
- Sử dụng các thẻ và các hộp ảo (visual cue)
Thay vì phân tích mã HTML để sửa lỗi, có thể sử dụng sự biểu diễn hoặc các thông
Trích xuất thông tin web dựa vào cây DOM trước tiên việc trích xuất này được hỗ
trợ bởi xây dựng cây DOM cho mã HTML của trang.
Các mẫu trích xuất có thể được làm rõ như đường dẫn từ gốc của cây DOM đến
node chứa nội dung c
ần trích xuất.
13
Ví dụ :
Đây là cây DOM của một đoạn mã HTML chứa thông tin về cuốn sách, gồm tên
cuốn sách (title) và tên tác giả (author). Bài toán đặt ra là sử dụng cây DOM này trích
xuất các thông tin về tên sách và tác giả viết sách. Mẫu trích xuất được xây dựng sau:
2.2 Trích xuất thông tin dựa theo các mẫu biểu thức chính qui
2.2.1 Khái niệm biểu thức chính qui
Một biểu thức chính qui có thể được sử dụng để mô hình mã hóa HTML [2]. Cho
một tập các ký tự alphabe ∑ và một token “#text” không thuộc ∑, một biểu thức chính qui
trên ∑ là một chuỗi trên ∑∪{#text, *,?,|,(,)} được định nghĩa như sau :
Sample DOM Tree Extraction
Mẫu trích xuất tên sách: HTMLÆBODYÆBÆCharacterData
Mẫu trích xuất tên tác giả: HTMLÆ BODYÆFONTÆAÆ CharacterData
HTML
BODY
FONT B
Age of Spiritual
(A|B) thì nó gọi là biểu thức chính qui kết hợp tự do. Một biểu thức chính qui thường
dùng để thể hiện một mẫu trích xuất.
2.2.2 Sử dụng biểu thức chính qui để trích xuất thông tin
Với một biểu thức chính qui, một otomat hữu hạn trạng thái có thể được xây dựng
và được sử dụng để so khớp sự xuất hiện của nó trong chuỗi tuần tự các trang web. Trong
quá trình này, dữ liệu có thể được trích xuất.
Ví dụ: Với mã HTML như sau:
<head>
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<title>Tinh Tong cua cac so tu 1->n</title>
</head>
Để lấy được phần tiêu đề của đoạn mã này thì ta có thể xây dựng biểu thức chính qui
như sau: <head>.*?<title>(#text)</title>
2.3 Một số giải thuật trích xuất thông tin cho dữ liệu bán cấu trúc
2.3.1 Hai kiểu biểu diễn của các trang giàu dữ liệu
Các trang giàu dữ liệu được chia thành hai loại thông qua sự biểu diễn của chúng[2]
- List Page: là trang chứa đựng một vài danh sách của các đối tượng. Hình 8 giới
thiệu một list page. Có hai dạng trang list, đó là trang list bố trí theo chiều ngang
Copyright: Tài liệu đại học ©