Khóa luận 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

ĐẠ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Ệ 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 Cán bộ hướng dẫn: Th.S. Trần Thị Oanh Cán bộ đồng hướng dẫn: CN. Trần Mai Vũ HÀ NỘI – 2009 Lời cảm ơn Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy, Thạc sỹ Trần Thị Oanh, Cử nhân Trần Mai Vũ đã tận tình hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp. 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ử để xây dựng hệ thống tìm kiếm giá cả, nhằm cung cấp thông tin tốt nhất đến người tiêu dùng. Khóa luận này tập trung nghiên cứu bài toán trích xuất thông tin từ 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. Khóa luận xác định một tập luật trích xuất giá cả để giải bài toán trích xuất giá khi cho biết tên sản phẩm và trên cơ sở đó, bài toán tự động trích xuất thông tin về tên và giá của sản phẩm được giải quyết. Khóa luận đưa ra các bước xây dựng hệ thống tìm kiếm giá cho sản phẩm trên các trang web tiếng Việt. Khóa luận đã tiến hành các thực nghiệm và đánh giá kết quả. Kết quả thực nghiệm cho thầy các thông tin được trích xuất từ hệ thống là có độ tin cậy. 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 và chữ viết tắt.........................................................................................v Danh sách các hình............................................................................................................vi Danh sách bảng biểu ...................................................................................................... viii Giới thiệu.............................................................................................................................1 Chươ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 ..............3 1.1 Bài toán trích xuất thông tin .......................................................................................3 1.1.1 Giới thiệu bài toán................................................................................................3 1.1.2 Dữ liệu của bài toán .............................................................................................3 1.1.3 Các hướng tiếp cận trong bài toán trích xuất thông tin........................................4 1.2 Bài toán trích xuất thông tin cho dữ liệu bán cấu trúc................................................6 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 iii 2.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 3.3.1 Phân loại trang kinh doanh.................................................................................26 3.3.2 Bài toán trích xuất thông tin giá cả của một sản phẩm xác định. ......................27 3.3.3 Bài toán tự động trích xuất thông tin về tên và giá của sản phẩm trong các trang kinh doanh sản phẩm...................................................................................................33 3.4 Các bước xây dựng hệ thống ....................................................................................37 3.4.1 Mô hình hệ thống ...............................................................................................37 3.4.2 Khả năng mở rộng của hệ thống ........................................................................40 Chương 4. Thực nghiệm và đánh giá kết quả................................................................41 4.1 Môi trường phần cứng và phần mềm........................................................................41 4.1.1 Cấu hình phần cứng ...........................................................................................41 4.1.2 Công cụ phần mềm ............................................................................................41 4.2 Kết quả thực nghiệm.................................................................................................44 iv 4.2.1 Thực nghiệm trích xuất giá của một sản phẩm cho trước..................................44 4.2.2 Thực nghiệm xác định website kinh doanh .......................................................49 4.2.3 Thực nghiệm thu thập và trích xuất thông tin từ một website ...........................52 4.2.4 Thực nghiệm khả năng thu thập thông tin của hệ thống....................................53 Kết luận .............................................................................................................................55 Tài liệu tham khảo............................................................................................................56 v Bảng các kí hiệu và chữ viết tắt Kí hiệu Diễn giải HTML HyperText Markup Language URL Uniform Resource Locator XPath XML Path W3C World Wide Web Consortium vi Danh 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 Hình 20. Luật trích xuất thông tin bảo hành sản phẩm ......................................................33 Hình 21. Kết quả google trả về với truy vấn "nokia 1200"................................................35 Hình 22. Kết quả trả về của google với query "nokia 1200" + "vnđ OR usd"...................36 Hình 23. Mô hình tổng quan của hệ thống .........................................................................38 Hình 24. Module xác định các website kinh doanh sản phẩm và các mẫu trích xuất ........39 vii Hình 25. Module Thu thập dữ liệu và trích xuất thông tin.................................................40 Hình 26. Trích xuất các URL liên quan .............................................................................45 Hình 27. Trang Web có sự nhập nhằng giá cả ...................................................................48 Hình 28. Trang Web có giá cả rõ ràng ...............................................................................49 viii Danh sách bảng biểu Bảng 1. Cấu hình phần cứng sử dụng trong thực nghiệm ..................................................41 Bảng 2.Các phần mềm sử dụng trong thực nghiệm ...........................................................41 Bảng 3. Mô tả chương trình thực thi để trích xuất giá sản phẩm .......................................43 Bảng 4. Kết quả thực nghiệm trích xuất giá thực của một sản phẩm.................................47 Bảng 5. Kết quả thực nghiệm xác định website kinh doanh sản phẩm..............................51 Bảng 6. Kết quả thực nghiệm trích xuất sản phẩm.............................................................53 Bảng 7. Kết quả thực nghiệm khả năng thu thập thông tin của hệ thống...........................54 Bảng 8. Một số sản phẩm trích xuất được..........................................................................54 1 Giớ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ư: WWW1, SIGMOD2,…[1],[3],[7] hay các sản phẩm mang tính thương mại như: PriceScan, Kelkoo, Yahoo!Shopping... Mặc dù đã tồn tại khá nhiều các hệ thống như vậy nhưng bài toán này vẫn đặt ra rất nhiều các thách thức hiện nay. Do các hệ thống có sẵn hầu hết thu thập dữ liệu đều thông qua việc cung cấp của các cửa hàng hay nhập dữ liệu thu công, công việc này tốn nhiều chi phí và thời gian. Nhiều nghiên cứu đã được đưa ra để giảm thiểu chi phí này, hầu hết các nghiên cứu đều tập trung vào việc áp dụng các phương pháp trích xuất tự động dựa vào dữ liệu bán cấu trúc để xây dựng các thành phần thu thập tự động thông tin trên các trang web bán hàng trực tuyến. Trên cở sở các nghiên cứu đã có, luận văn cũng đã dựa trên định hướng xây dựng thành phần trích xuất thông tin tự động dựa vào trích xuất thông tin trên dữ liệu bán cấu 1 The International World Wide Web Conferences 2 ACM Special Interest Group on Management of Data . 2 trúc để đề xuất ra một mô hình hệ thống tìm kiếm giá cả sản phẩm. Và qua mô hình đã đề xuất tác giả đã tiến hành các thực nghiệm để đánh giá các kết quả đạt được của mô hình. Khóa luận gồm 4 chương nội dung được mô tả sơ bộ dưới đây: Chươ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 khái quát bài toán trích chọn thông tin nói chung, các cách tiếp cận giải quyết bài toán thông qua miền dữ liệu (có cấu trúc, không cấu trúc và bán cấu trúc) và giới thiệu bài toán trích chọn thông tin cho dữ liệu bán cấu trúc , phương pháp đánh giá khả năng trích xuất thông tin thông qua độ hồi tưởng (R), độ tin cây (P) và các ứng dụng thực tiễn của bài toán. 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. 3 Chươ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 riêng, từ đó đưa ra một số ứ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, đồng thời cũng giới thiệu về phương pháp đánh giá khả năng trích xuất thông qua độ hồi tưởng (R), độ tin cậy (P). 1.1 Bài toán trích xuất thông tin 1.1.1 Giới thiệu bài toán Trích xuất thông tin bài toán nhận dạng những thành phần thông tin cụ thể của một văn bản, những thành phần này chính là hạt nhân tạo nên nội dung ngữ nghĩa của văn bản đó [6]. Ví dụ: Với một báo cáo thời tiết có thể trích xuất được thông tin về các vùng, thời gian, nhiệt độ cao hay thấp. Với một trang web về kinh doanh sản phẩm trực tuyến có thể trích xuất được thông tin về tên sản phẩm, thuộc tính của sản phẩm và giá của sản phẩm đó. 1.1.2 Dữ liệu của bài toán Dữ liệu thông thường được chia thành 3 dạng cơ bản[17]: • Dữ liệu không cấu trúc: Dữ liệu không cấu trúc thường dùng để chỉ dữ liệu ở dạng tự do và không cần có cấu trúc định nghĩa sẵn ví dụ như: ngôn ngữ tự nhiên. • Dữ liệu có cấu trúc: Dữ liệu có cấu trúc thường dùng để chỉ dữ liệu lưu trữ trong các hệ quản trị cơ sở dữ liệu quan hệ như MS SQL server hay MySQL, trong đó các thực thể và các thuộc tính được định nghĩa sẵn . • Dữ liệu bán cấu trúc: Là dữ liệu có cấu trúc nhưng không hoàn toàn tường minh, nó không tuân theo những cấu trúc, cách thức cấu trúc của bảng và các mô hình dữ liệu trong cơ sở dữ liệu nhưng nó chứa những thẻ , những đánh dấu tới những 4 phần tử ngữ nghĩa riêng biệt của các bản ghi và các trường riêng biệt bên trong 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ì