Luận vă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 web 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 để giải quyết 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, tiến hành các thực nghiệm trên hệ thống 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...........................................................................................10 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 ................................................................................15 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............................................................................................................57 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 DOM Document Object Model 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 ...........................................................42 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 khóa luận đã 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 là 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 ta có thể trích xuất được thông tin về các vùng, thời gian, nhiệt độ. Với một trang web về kinh doanh sản phẩm trực tuyến ta 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ì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ư nhận dạng và trích xuất thực thể: tên người, tên tổ chức… Hình 2 là một ví dụ về bài toán nhận dạng thực thể. Hình 2. Ví dụ về bài toán nhận dạng thực thể Để giải quyết bài toán trích xuất thực thể thì có nhiều cách tiếp cận như HMM, SVM hay CRF…ngoài ra còn một giải thuật khá nổi tiếng đó là giải thuật DIPRE - Dual 6 Iterative Pattern Relation Expansion của BRin [8] trong việc trích xuất cặp thực thể quan hệ tên sách và tác giả đối với trang amazon.com. • Dữ liệu bán cấu trúc 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 trình hay một luật trích xuất thường được gọi là một wrapper [2]. Phương pháp trích xuất này có nhiều hướng tiếp cận như sử dụng cây DOM [15]. Phương pháp này sẽ phân tích mã nguồn HTML dưới dạng một cây các node, mỗi node là một thẻ HTML, quá trình trích xuất thông tin sẽ dựa vào đường đi từ gốc đến node chứa thông tin cần trích xuất. 1.2 Bài toán trích xuất thông tin cho dữ liệu bán cấu trúc 1.2.1 Vấn đề đặt ra với bài toán Bài toán trích xuất thông tin cho dữ liệu bán cấu trúc là rất hữu dụng bởi vì nó cho phép chúng ta thu được và tích hợp dữ liệu từ nhiều nguồn để cung cấp cho những dịch vụ giá trị gia tăng như : thu được những thông tin Web một cách tùy ý, hệ thống tìm kiếm giá cả, hay meta-search. Ngày càng nhiều các công ty, các tổ chức phổ cập các thông tin ở trên Web, thì khả năng trích xuất dữ liệu từ các trang Web đó ngày càng trở 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á Để đánh giá chất lượng phương pháp trích xuất thông tin cho dữ liệu bán cấu trúc người ta thường sử dụng một số độ đo như độ hồi tưởng (R), độ tin cậy (P). Giả sử sau khi sử dụng bài toán trích xuất cho một tập dữ liệu gồm n tài liệu. Kết quả trích xuất được là m tài liệu.Kết quả trích xuất đúng là q tài liệu khi đó độ hồi tưởng R và độ chính xác P sẽ được tính theo công thức (1) và (2). %100q x n R = (1) %100q x m P = (2) Ví dụ: Nếu tập dữ liệu cần trích xuất là 100 (tài liệu). Dữ liệu trích xuất được là: 97 (tài liệu). Dữ liệu trích xuất đúng là: 90 (tài liệu) . %100 100 90 xR = = 90 % %100 97 90 xP = = 92,78 % 8 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 • 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. Hình 3 dưới đây là ví dụ trích xuất nội dung chính của trang web. 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 dưới đây là ví dụ về một hệ thống tìm kiếm giá cả sản phẩm. Hình 4. Ví dụ về hệ thống tìm kiếm giá cả 10 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 Chương 2 sẽ giới thiệu hướng tiếp cận trích xuất sử dụng cây DOM [15], [6] và biểu thức chính qui [2]. Đồng thời chương cũng trình bày hai giải thuật trong bài toán trích xuất thông tin cho dữ liệu bán cấu trúc cũng như các ưu nhược điểm của nó. Đây cũng chính là những tiền đề để xây dựng phương pháp trích xuất giá cả sản phẩm. 2.1 Trích xuất thông tin dựa vào cây DOM 2.1.1 Khái nhiệm cây DOM Theo W3C thì DOM (Document Object Model) là một giao diện lập trình ứng dụng (API) cho các văn bản HTML hợp lệ và các văn bản XML có cấu trúc chặt chẽ. Nó định nghĩa cấu trúc logic của các văn bản và cách thức một văn bản được truy cập và thao tác [15]. Ví dụ về một bảng (table) được lấy văn bản HTML: Shady Grove Aeolian Over the River, Charlie Dorian Dạng biểu diễn cây DOM của mã HTML 2.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. 11 - 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ư , ,) 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ụ: … … … , 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. ¾ 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 tin ảo (ví dụ như: địa chỉ trên màn hình mà các thẻ được biểu diễn) để suy luận mối quan hệ có cấu trúc của các thẻ và có thể xây dựng được cây DOM. Phương thức xây dựng có thể phân tích mã HTML thành cây DOM, miễn là trình duyệt có thể hiển thị được đoạn mã đó một cách chính xác. Trong một trình duyệt web, mỗi phần tử HTML (chứa đựng một thẻ mở, các thuộc tính tùy chọn, nội dung HTML được nhúng tùy ý và một thẻ đóng, thẻ này có thể thiếu) được biểu diễn như một hình chữ nhật. Thông tin ảo này có thể lấy được sau khi mã HTML được biểu diễn trên trình duyệt. Một cây DOM sau đó có thể được xây dựng dựa vào các thông tin ảo này. Các bước xử lý như sau: ¾ Tìm 4 đường biên của hình chữ nhật ứng với mỗi phần tử HTML thông qua việc công cụ trình diễn của trình duyệt, ví dụ: Internet Explorer. ¾ Theo sự tuần tự của các thẻ mở và sự kiểm tra xem một hình chữ nhật có nằm trong một hình chữ nhật khác không, để xây dựng cây DOM. 12 Hình 5 là một ví dụ minh họa về sử dụng visual cue: Một đoạn mã HTML có 3 lỗi. sử dụng thông tin ảo có thể dễ dàng xây dựng được cây DOM. Hình 5. Ví dụ xây dựng cây DOM sử dụng hộp ảo 2.1.3 Sử dụng cây DOM để trích xuất thông tin Để trích xuất được thông tin cần thiết ở một node của cây DOM, chúng ta cần chỉ rõ đường đi từ gốc của cây đến node cần trích xuất thông tin. Đường đi này gọi là một XPath [16]hay mẫu trích xuất. 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. 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: 13 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 : Một chuỗi rỗng ε và tất cả các phần tử trong ∑ ∪ {#text} đều là một biểu thức chính qui. Nếu A và B là một biểu thức chính qui, thì AB, (A|B) và (A)? cũng là một biểu thức chính qui, trong đó (A|B) tức là A hoặc B và (A)? thức là (A|ε). Nếu A là một biểu thức chính qui, thì (A)* cũng là biểu thức chính qui, trong đo (A)*= {ε, A, AA, AAA,…}. Chúng ta cũng sử dụng (A)+ để chỉ A(A)*. Nếu biểu thức chính qui không có chứa (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. 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 Machines Ray Kurzwei Element Character-Data HEADER A 14 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: Tinh Tong cua cac so tu 1->n Để 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: .*?(#text) 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 6 giới thiệu một list page. Có hai dạng trang list, đó là trang list bố trí theo chiều ngang hoặc chiều dọc. Bên trong mỗi vùng, bản ghi dữ liệu được định dạng sử dụng cùng một mẫu và mẫu sử dụng trong hai vùng khác nhau là khác nhau [2]. - Detail Page: là trang chỉ giới thiệu một đối tượng đơn. Ví dụ hình 7 là một trang detail page giới thiệu về sản phẩm . Nó chứa đựng tất cả các thuộc tính của sản phẩm như: tên, ảnh, giá, thông số kỹ thuật, thời gian bảo hành [2] . 15 Hình 6. Dạng biểu diễn của trang list page Hình 7. Dạng biểu diễn của trang detail page 2.3.2 Một số giải thuật điển hình Hiện nay tư tưởng của phương pháp trích xuất thủ công không còn được sử dụng . Vì vậy khóa luận chỉ giới thiệu phương pháp trích xuất thông tin tự động và bán tự động cho “bài toán trích xuất thông tin cho dữ liệu bán cấu trúc”. • Phương pháp Wrapper qui nạp: đây là phương pháp trích xuất bán tự động 16 Giải thuật được nêu ra dưới đây là giải thuật dựa trên hệ thống Stalker. - Một ví dụ về trích xuất theo giải thuật dựa trên hệ thống Stalker. Một trang Web có thể được nhìn dưới dạng có thứ tự của token S (ví dụ như: các từ, các số và các thẻ HTML). Việc trích xuất sử dụng một cấu trúc cây gọi là cây EC(embedded catalog tree), đây là công cụ để mô hình dữ liệu nhúng trong một trang HTML. Gốc của cây là văn bản chứa tất cả các token tuần tự S của trang, nội dung của mỗi node con là một chuỗi con của node cha. Để trích xuất một node, Wrapper sử dụng miêu tả cây EC của trang đó và tập hợp các luật trích xuất. Hình 8 bên dưới là ví dụ sự chuyển đổi một đoạn mã HTML sang cây EC. Chú ý rằng chúng ta sử dụng LIST ở đây bởi vì tập hợp các địa chỉ luôn luôn có thứ tự. Hình 8. Chuyển đổi từ mã HTML sang cây EC Với mỗi node trong cây, Wrapper nhận dạng hoặc trích xuất nội dung của node từ cha của nó, node cha là node chứa đựng chuỗi token của tất cả các node con. Mỗi trích xuất được thực hiện bởi 2 luật, Start Rule và End Rule. Start Rule chỉ ra sự bắt đầu của node và End Rule chỉ ra sự kết thúc của node. Phương thức này có thể áp dụng cho cả node lá và các node danh sách (list node). 17 Các luật trích xuất dựa trên ý tưởng của mỏ neo (landmark). Mỗi mỏ neo là một chuỗi các token liên tiếp và nó dùng để đánh dấu sự bắt đầu hay kết thúc của một phần tử mục tiêu. Dưới đây là một đoạn mã HTML trong trang web. Restaurant Name: Good Noodles 205 Willow, Glen, Phone 1-773-366-1987 25 Oak, Forest, Phone (800) 234-7903 324 Halsted St., Chicago, Phone 1-800-996-5023 700 Lake St., Oak Park, Phone: (708) 798-0008 Để trích xuất được tên của quán ăn “Good Noodles” thì luật trích xuất sẽ là: Start Rule: R1: SkipTo() tức là hệ thống nên xuất phát ở điểm bắt đầu của trang và bỏ qua tất cả các token cho đến khi chúng thấy được thẻ đầu tiên. Các luật SkipTo(:) hoặc SkipTo(i) đề không đúng. Vì theo cây EC trong hình 8 R1 là cha của node name, như vậy nó sẽ là node gốc. Node gốc thì chứa chuỗi token tuần tự của cả trang Web. Tương tự End Rule : R2: SkipTo () sẽ xác định được điểm kết thúc tên của quán ăn. - Quá trình học luật Trong hệ thống Wrapper qui nạp quá trình học là một quá trình chủ đạo. Khóa luận này sẽ trình bày giải thuật học của wrapper để sinh ra các luật trích xuất. Ý tưởng cơ bản của giải thuật học luật như sau: Để sinh ra Start Rule cho một node của cây EC, một vài token tiền tố hay các đại diện của node được nhận dạng như các mỏ neo, chúng có thể nhận dạng đơn nhất sự bắt đầu của một node. Để sinh ra End Rule cho một node, một vài token hậu tố hay các đại diện của node được nhận dạng như một mỏ neo. Tiến trình sinh Start Rule và End Rule là giống nhau. Cho trước một tập các mẫu huấn luyện đã được gán nhãn, giải thuật học sẽ sinh ra các luật trích xuất tổng quan để trích xuất tất cả các phần tử mục tiêu (positive items) mà không trích xuất các phần tử khác (nagertive items). 18 Sau quá trình này thì một wrapper đã được sinh ra , nó sẽ được áp dụng cho các trang web khác chứa đựng các dữ liệu tương tự và được định dạng cùng một cách với tập mẫu huấn luyện. - Ưu điểm và nhược điểm ƒ Ưu điểm: Người sử dụng chỉ phải gán nhãn một lượng nhỏ các dữ liệu mẫu.Quá trình học là quá trình tự động để sinh ra luật trích xuất. ƒ Nhược điểm: Nếu một site thay đổi, làm sao để wrapper biết được sự thay đổi đó? Nếu phát hiện chính xác có sự thay đổi, làm sao để tự động sử wrapper? Vì phương pháp này phụ thuộc vào việc gán nhãn bằng tay nên nó không phù hợp cho trích xuất một lượng lớn các trang. Ví dụ, nếu một trang kinh doanh sản phẩm muốn trích xuất tất cả các các sản phẩm được bán trên Web, việc gán nhãn bằng tay hầu như là nhiệm vụ không thể. Việc duy trì wrapper là việc làm rất tốn kém, vì web là một môi trường động. Các site thì luôn luôn thay đổi. • Phương pháp trích xuất tự động Để hạn chế nhược điểm của Wrapper qui nạp, phương pháp trích xuất tự động đã được nghiên cứu rất nhiều. Việc trích xuất tự động là hoàn toàn có thể bởi vì dữ liệu trên một website thường được mã hóa với một số lượng mẫu cố định. Có thể tìm những khuôn mẫu đó bằng việc khai phá những mẫu lặp lại trong nhiều trang của một website. Trong một vài ứng dụng, chúng ta cần trích xuất dữ liệu từ các trang detail-page, vì những trang này chứa nhiều thông tin hơn. Ví dụ: trong một trang list-page, thông tin của mỗi sản phẩm thông thường chỉ là tên, ảnh và giá. Tuy nhiên nếu ứng dụng cần những thông tin miêu tả sản phẩm thì chúng ta cần trích xuất từ những trang detail. Một thuật toán trích xuất tự động khá tiêu biểu mà có thể trích xuất ở cả trang detail và trang list đó là RoadRunner. - Mô tả giải thuật 19 Đầu vào: Một tập hợp các trang mẫu, mỗi trang chứa đựng một hay nhiều bản ghi (một trang có thể là list page hoặc detail page). Đầu ra: Một mẫu trích xuất có thể trích xuất được tất các các trang trong tập mẫu, trong giải thuật này mẫu trích xuất đó là biểu thức chính qui kết hợp tự do. - Phương thức tiếp cận Ban đầu, giải thuật sẽ lấy một số lượng ngẫu nhiên các trang với mẫu trích xuất W. Mẫu trích xuất W sau đó được định nghĩa lại bởi việc kết hợp có thứ tự với mã HTML của mỗi trang pi khác trong tập mẫu, để giải quyết vấn đề sai khác giữa các mẫu trích xuất của các trang trong tập mẫu. Cuối sung giải thuật sinh ra một wrapper chung có thể trích xuất được tất cả các trang trong tập mẫu. Wrapper này sẽ được áp dụng trích xuất cho những trang khác có cấu trúc tương tự với những trang trong mẫu Sự sai khác xuất hiện khi một vài token của trang pi xuất hiện sai khác so với W. Có hai kiểu sai khác trong việc so khớp đó là: ¾ Sự sai lệch xâu văn bản (string mismatch) : Chúng biểu thị thông qua các trường dữ liệu hay các mục. ¾ Sự sai khác giữa các thẻ (tag mismatch). Giải thuật này được làm rõ trong hình 9 dưới đây: 20 Hình 9. Ví dụ giải thuật RoadRunner [12] - Ưu, nhược điểm của giải thuật ƒ Ưu điểm: Không cần sự gán nhãn của người dùng với tập mẫu huấn luyện, có thể tự động xây dựng được mẫu trích xuất. ƒ Nhược điểm: Nó không thể tự động nhận dạng được đâu là thực thể thông tin mong muốn của người dùng. Vì vậy người sử dụng sẽ vẫn phải tự gán nhãn những kết quả đầu ra. Ví dụ: giải thuật trong hình 9 khi nó xác định được thẻ có dữ liệu tương đương của 2 trang nhưng nó không thể xác định đấy là tên của quyển sách, mà chỉ có thể xác định nó là một xâu ký tự. 21 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 Việc á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ả sản phẩm là vấn đề quan trọng nhất của khóa luận. Trong chương này khóa luận sẽ đề cập đến khái niệm của hệ thống tìm kiếm giá cả, phương pháp xây dựng hệ thống và cách đánh giá các hệ thống đang tồn tại. 3.1 Khái quát hệ thống tìm kiếm giá cả của sản phẩm Trong phần này khóa luận sẽ đề cập tới khái niệm về hệ thống tìm kiếm giá cả, các phương pháp xây dựng, ưu nhược điểm của các hệ thống tìm kiếm giá cả hiện tại, từ đó đưa ra cách tiếp cận để xây dựng hệ thống tìm kiếm giá cả phù hợp. 3.1.1 Khái niệm Hệ thống tìm kiếm giá cả (hay còn được biết đến với tên là “dịch vụ so sánh giá cả”) là một khái niệm thuộc lĩnh vực thương mại điện tử. Các hệ thống này cho phép người sử dụng tìm kiếm và thấy được sự so sánh giá cả của một sản phẩm cụ thể trên nhiều trang web bán hàng khác nhau [18]. Hệ thống tìm kiếm giá cả thông thường không phải là một hệ thống bán hàng trực tuyến, tuy nhiên nó chính là một công cụ gián tiếp hỗ trợ việc giới thiệu sản phẩm của các cửa hàng kinh doanh cũng như việc mua hàng của người sử dụng. 3.1.2 Các phương pháp xây dựng Do các hệ thống tìm kiếm giá cả tập trung vào việc thể hiện các thông tin giá cả trên nhiều trang web bán hàng khác nhau nên hướng tiếp cận để giải quyết bài toán này cũng đều đi sâu vào việc tạo ra một môi trường tốt nhất cho việc thu thập, trao đổi thông tin sản phẩm giữa các cửa hàng có sản phẩm và hệ thống. Thông thường có ba phương pháp để xây dựng hệ thống dựa vào đặc trưng trên [18] : - Phương pháp dựa vào sự cung cấp thông tin trực tiếp từ các cửa hàng. Các hệ thống dạng này sẽ nhận được sự cung cấp thông tin của các cửa hàng về thông tin, giá cả của sản phẩm, người quản trị hệ thống sẽ cập nhập vào cơ sở dữ liệu của hệ thống. Các cửa hàng sẽ không tương tác trực tiếp lên hệ thống. 22 - Phương pháp dựa vào sự tương tác của cửa hàng trên hệ thống. Các hệ thống dạng này thường được biết đến như là các mô hình B2C(Business To Customer), B2B (Business To Business) trong thương mại điện tử. Hệ thống sẽ tạo ra môi trường giao diện, cho phép các cửa hàng tương tác trực tiếp với hệ thống để cung cấp thông tin. - Phương pháp tự động thu thập thông tin từ các trang web bán hàng hay giới thiệu sản phẩm của các cửa hàng. Hệ thống dạng này sẽ không dựa vào sự cung cấp thông tin của các cửa hàng mà tự động truy nhập vào các trang web của cửa hàng để trích xuất các thông tin sản phẩm đưa về cơ sở dữ liệu của hệ thống. 3.1.3 Các hệ thống hiện tại • Các hệ thống hiện tại. Đối với ba phương pháp tiếp cận đã được giới thiệu ở mục 3.1.2, việc áp dụng hai phương pháp đầu sẽ gặp phải các hạn chế do dữ liệu của hệ thống hoàn toàn phụ thuộc vào sự cung cấp của các cửa hàng trong khi giá cả là dạng dữ liệu biến động liên tục theo thời gian đòi hỏi phải có sự cập nhật liên tục thông tin vào cơ sở dữ liệu. Bên cạnh đó, việc áp dụng hai phương pháp này, cơ sở dữ liệu sẽ bị giới hạn về số lượng cửa hàng cung cấp dữ liệu cho hệ thống. Do đó hai phương pháp này không phải là phương pháp tối ưu để xây dựng hệ thống tìm kiếm giá cả. Còn ở phương pháp tiếp cận thứ ba, dữ liệu được thu thập thông qua các trang kinh doanh sản phẩm. Hệ thống sẽ quét qua những trang web cửa hạng để nhận được giá cả của sản phẩm, thay vì phải sử dụng nguồn cung cấp của người kinh doanh. Vì vậy đây là phương pháp có giá trị nhất tình tới thời điểm hiện nay. Có rất nhiều bài toán được đề xuất theo phương thức tiếp cận thứ ba để xây dựng hệ thống tìm kiếm giá cả như: - Andrew Carlson và Charles Schafer áp dụng [1] để trích xuất tự động các thông tin ở các website du lịch và kinh doanh nhà đất, nhằm xây dựng hệ thống tìm kiếm giá cả về nhà đất và du lịch - “Elwin Chai, Rick Jones áp dụng [3] để xây dựng hệ thống tìm kiếm giá cả tự động PriceHunter. - Robert Bo Doorenbos, Oren Etzioni và Daniel So Weld đã giới thiệu [7] để xây dựng một ứng dụng so sánh giá cả cỡ lớn cho web. 23 • Các vấn đề của bài toán nêu trên Các bài toán này được đề xuất để xây dựng những hệ thống tìm kiếm giá cả sản phẩm, tuy nhiên chúng gặp phải một vấn đề, đó là các tên của sản phẩm phải được cung cấp trước và các trang kinh doanh sản phẩm phải xác định rõ trên hệ thống. Ở Việt Nam hiện nay cũng có một vài hệ thống khá tiêu biểu như : Vatgia1, Aha2. Tuy nhiên hai hệ thống này lại xây dựng theo cách tiếp cận thứ hai, nên phải phụ thuộc nhiều vào các nhà kinh doanh. Từ những nhận định đã nêu trên, khóa luận này sử dụng cách tiếp cận thứ ba để xây dựng hệ thống và sẽ giải quyết một số tồn tại một số phương pháp xây dựng hệ thống tìm kiếm giá cả hiện tại. 3.2 Cơ sở thực tiễn Hiện nay các trang web đều xây dựng trên nền những ngôn ngữ lập trình động như PHP, ASP…. Khi người dùng vào một trang kinh doanh sản phẩm và tìm kiếm một sản phẩm nào đó thì kết quả được trả về và hiển thị trên trình duyệt theo một số khuôn mẫu định sẵn, các trang trong cùng khuôn mẫu này thì có chung cấu trúc HTML. Tức là khi chúng ta biết mẫu để trích xuất một trang trong khuôn mẫu này, thì có thể sử dụng mẫu đó để trích xuất những thông tin của những trang khác có cùng khuôn mẫu. Ví dụ : Với website www.trananh.vn, hình 10,11 biểu diễn của trang detail về hai sản phẩm của laptop HP. 1 2 vn 24 Hình 10. Trang giới thiệu sản phẩm HP CQ60-203TX Hình 11. Trang giới thiệu sản phẩm HP CQ60-101TX Hai trang detail này tuy giới thiệu về hai sản phẩm khác nhau nhưng đều có chung một dạng biểu diễn của cây DOM như hình 12 dưới đây 25 Hình 12. Biểu diễn cây DOM của mã HTML hai trang về sản phẩm HP Mẫu trích xuất các thông tin Tên Sản phẩm: HTML Æ BODY Æ TABLE Æ TR[1] Æ TD[1] Æ TÊN SẢN PHẨM (1). Giá Sản Phẩm: HTML Æ BODY Æ TABLE Æ TR[3] Æ TD[1] Æ DIV[1] Æ FONT [1]Æ GIÁ SẢN PHẨM (2). Nhận xét: Vì các trang trong cùng một website có cấu trúc tuân theo một vài khuôn mẫu nhất định nên ta có thể sử dụng những mẫu trích xuất (1) để trích xuất tên sản phẩm và (2) để trích xuất giá sản phẩm từ trang khác có cùng cây DOM trên. 3.3 Cơ sở khoa học Phần cơ sở lý thuyết sẽ nêu và giải quyết những bài toán cơ sở để xây dựng hệ thống tìm kiếm giá cả. Trong phần này sẽ tập trung vào hai bài toán chính đó là “bài toán về xác định giá thực của một sản phẩm” và “bài toán tự động trích xuất thông tin về tên và giá 26 sản phẩm”. “Bài toán xác định giá thực một sản phẩm” sẽ bổ trợ để giải quyết “bài toán tự động trích xuất thông tin về tên và giá của sản phẩm”. Đây chính là thành phần cốt lõi để xây dựng hệ thống tìm kiếm giá cả sản phẩm. 3.3.1 Phân loại trang kinh doanh Các trang kinh doanh sản phẩm được chia làm hai loại chính: - Các trang kinh doanh sản phẩm thuần tuý: đây là các trang có bố cục và trình bày rõ ràng, các thông tin được cung cấp theo những khuôn mẫu nhất đinh. Hình 13 minh họa một trang kinh doanh thuần túy Hình 13. Ví dụ về trang kinh doanh thông thường 27 - Các trang rao vặt: các trang có bố cục không rõ ràng, tùy thuộc vào người sử dụng. Hình 14 dưới đây là ví dụ một trang ra vặt. Hình 14. Ví dụ về trang rao vặt 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. • Bài toán tiền đề: xác định giá trong một trang Web - Đầu vào: Mã nguồn HTML của một trang Web. - Đầu ra: Các giá chứa trong mã nguồn đó. Ví dụ: Với một trang Web về kinh doanh sản phẩm “HP Mini-note” trong hình 15. Hình 15. Ví dụ về trích xuất giá trong một trang web Tiền tố: Giá Hậu tố: VNĐ 28 Thì các giá trích xuất được sẽ là: - 6,559,000 VNĐ - 4,950,000 VNĐ - 13,999,000 VNĐ - 14,399,000 VNĐ Phương pháp khóa luận sử dụng đó là xây dựng cây DOM tương ứng với mã HTML của trang, sau đó sẽ duyệt qua cây DOM để xác định được giá chứa trong trang. Để xác định được node nào trong cây DOM là chứa giá thì khóa luận đã xây dựng được bộ luật xác định giá. Để xác định được giá ta sử dụng một số luật sau: - Trước giá thì có một vài tiền tố: như “GIÁ”, “PRICE” - Sau giá cũng có các hậu tố như: “VNĐ”, “USD”, “VND”,”Đ”,”$” …. - Định dạng của giá: dạng số , tức là bao gồm các ký tự {0, 1, 2,…, 9, “,”, “.”} - Node chứa giá là: #text Tuy nhiên trong quá trình thống kê này chúng tôi cũng thấy có nhiều giá không liên quan ví dụ như trường hợp trên thì “300.000 VNĐ” không phải là giá mặc dù nó chứa hậu tố VNĐ. Trong một số trường hợp như hình 16 thì mặc dù thỏa mãn các điều kiện về tiền tố, hậu tố và định dạng của giá. Nhưng nó không phải là giá có ý nghĩa với người sử dụng. Vì vậy khóa luận này xây dựng các tiền tố loại trừ để loại trừ các giá không ý nghĩa đó. Một số tiền tố loại trừ như : “GIÁ CŨ”, “GIÁ BÌA”, “GIÁ THỊ TRƯỜNG”… 29 Hình 16. Ví dụ về sản phẩm chứa những giá không đúng • Bài toán trích xuất thông tin giá cả của sản phẩm. Mô tả bài toán - Đầu vào: Tên sản phẩm và trang Web liên quan đến sản phẩm. - Đầu ra: Giá thực của sản phẩm, mẫu trích xuất giá thực đó và mẫu trích xuất tên sản phẩm. Ví dụ: đầu vào là trang web bán sản phẩm Nokia 1200 như hình 17. Hình 17. Ví dụ về trích xuất giá thực của trang sản phẩm Giá không đúng Tiền tố loại trừ Giá thực 30 Đầu ra sẽ là giá của sản phẩm này : VNĐ 540.000 là giá thực của sản phẩm, mẫu trích xuất tên sản phẩm này là “HTML Æ BODY Æ TABLE[1] Æ TR[1] Æ TD[1] Æ Tên sản phẩm” và mẫu trích xuất giá này là “HTML Æ BODY Æ TABLE[1] Æ TR[2] Æ TD[2] Æ Giá thực sản phẩm”. Xác định được giá của sản phẩm là một bài toán hết sức quan trọng trong hệ thống tìm kiếm giá cả. Tuy nhiên không có một chuẩn để nhận dạng được giá mà có thể áp dụng để nhận dạng tất cả các trang. Phương pháp giải quyết bài toán Để xác định giá phương pháp được thực hiện thông qua những bước sau: Xây dựng cây DOM tương ứng với mã HTML của trang Web đầu vào - Bước 1: Xác định được node của cây DOM chứa tên sản phẩm và lấy được mẫu trích xuất tên sản phẩm. - Bước 2: Xác định tất các các node chứa giá trong trang Web như đã nêu ở trong bài toán tiền đề và lấy được mẫu trích xuất tương ứng với những giá đó. - Bước 3: Loại trừ các giá không phù hợp. - Bước 4: Xác định được giá thực của sản phẩm thông qua mối quan hệ giữa tên và giá của sản phẩm. Tại bước 1, ta sẽ duyệt qua cây DOM, xác định node chứa tên sản phẩm (tên sản phẩm đã định rõ từ đầu vào). Từ các node này ta sẽ sinh ra mẫu trích xuất tương ứng với tên sản phẩm. Tại bước 2 sau khi xác định được node có chứa giá theo bài toán tiền đề, ta có thể lấy được mẫu trích xuất tương ứng với node đó theo phương pháp trích xuất sử dụng cây DOM đã nêu ở phần 2.1. Sau khi đã xác định được tất cả các mẫu trích xuất giá và mẫu trích xuất tên sản phẩm, để xác định được giá thực của sản phẩm ta phải loai trừ những giá không phù hợp, đó là những giá nằm trong một số thẻ hay thẻ . Giá có thể xuất hiện độc lập hoặc không độc lập, ví dụ: giá 120.000 vnđ là giá độc lập trong khi giá 100.000 vnđ (30%) là giá không độc lập. Nếu chỉ có một giá độc lập thì giá này được coi là giá thực. Nếu có nhiều giá độc lập, thì 31 tất cả các giá đó đều có thể là giá của sản phẩm. Vì vậy ta phải dựa vào mối quan hệ giữa tên sản phẩm và giá của sản phẩm đó. Mối quan hệ giữa tên sản phẩm và giá của nó trong một trang kinh doanh sản phẩm đó là sự gần nhau về mặt cấu trúc HTML (ví dụ: chúng thuộc 2 node kề nhau trong cây DOM ). Để xác định được sự gần nhau giữa các node chứa tên và giá trong cây DOM, khóa luận này sử dụng độ trùng lặp về đường đi từ gốc đến node của mẫu trích xuất. Ví dụ: Mẫu trích xuất tên sản phẩm là: HTML Æ BODY Æ TABLE Æ TR Æ TD Æ DIV[1] Æ Tên sản phẩm. Mẫu trích xuât giá sản phẩm là: HTML Æ BODY Æ TABLE Æ TR Æ TD Æ DIV[2] Æ FONT Æ Tên sản phẩm. Với 2 mẫu trích xuất như trên thì độ trùng lặp sẽ là : 5 tương ứng với 5 bước đi: HTML[1] Æ BODY[2] Æ TABLE [3]Æ TR[4] Æ TD[5]. Nếu độ trùng lặp giữa mẫu trích xuất tên và mẫu trích xuất giá là lớn nhất thì nó được coi là giá thực của sản phẩm. Tuy nhiên trong một số trang không cung cấp giá của sản phẩm nhưng lại có chứa những giá ngoại lai, những giá này không phải là giá sản phẩm. Vấn đề đặt ra là làm sao có thể xác định được giá đó không phải là giá của sản phẩm. Để giải quyết vấn đề này, khóa luận sử dụng thêm một độ đo về sự khác biệt giữa 2 mẫu trích xuất. Nếu sự khác nhau này nhỏ hơn một ngưỡng thì mẫu trích xuất trỏ đến giá và mẫu trích xuất trỏ đến tên sản phẩm mới được chấp nhận là một ứng cử để trích xuất giá thực và tên của sản phẩm các trang. Đối với những trang Việt Nam, khóa luận này gặp một vài thách thức đó là cách thức viết giá không đúng hoặc giá quá nhập nhằng, như một số trang lại viết là : Giá: VNĐ 120.000 , trong khi thực tế thì phải viết là 120.000 VNĐ. Mặt khác một số trang lại chưa cập nhật được giá sản phẩm và giá chỉ xuất hiện dưới dạng “Giá:(x)vnđ”. Đặt biệt là giá ở một số trang về rao vặt ở Việt Nam thì không theo một qui tắc viết, ví dụ “Cần bán nokia 1200 giá 320k”… Qua thống kê tại nhiều trang kinh doanh các loại sản phẩm ở Việt Nam và trên thế giới trên nhiều lĩnh vực như các trang về: Điện thoại, máy tính, mỹ phẩm và trang sức, 32 đặc biệt là một số trang về rao vặt….. .Kết hợp bài toán tiền đề và bài toán “xác định giá thực” khóa luận này đã đề xuất ra một tập luật để trích xuất giá của sản phẩm, tập luật này được đưa ra trong hình 18 bên dưới. Hình 18. Tập luật trích xuất giá sản phẩm Trong tập luật này gồm một số luật chính: - FirstRule: tiền tố của giá - LastRule: Hậu tố của giá - RejectRule: tiền tố loại trừ - Format: định dạng của giá - TagName: tên thẻ HTML mà giá nằm trong đó. Trong khi xây dựng được tập luật để trích xuất giá cả, chúng tôi nhận thấy ngoài giá cả của sản phẩm người sử dụng còn quan tâm đến những thuộc tính khác của sản phẩm như ảnh của sản phẩm, thời gian bảo hành, thông tin khuyến mại… Bên cạnh đó cách tổ chức tập luật với giá có thể áp dụng cho những thuộc tính này. Trên tư tưởng chung của phương pháp trích xuất giá, tức là lấy tên sản phẩm làm neo để xác định giá thực của sản phẩm bằng cách xác định giá gần nhất với sản phẩm. Khóa luận này cũng đã xây dựng thành công các luật trích xuất cho những thuộc tính trên hình 19, 20 là các tập luật trích xuất cho một số thuộc tính này: 33 - Luật trích xuất ảnh sản phẩm Hình 19. Luật trích xuất ảnh sản phẩm - Luật trích xuất thời gian bảo hành Hình 20. Luật trích xuất thông tin bảo hành sản phẩm 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 Trong những bài toán về trích xuất thông tin ở mục 2.3 thì tập mẫu huấn luyện phải được xác định trước. Với phương pháp trích xuất bán tự động thì cần sự gán nhãn bằng tay với tập mẫu huấn luyện này. Với phương pháp trích xuất tự động như RoadRunner thì phải gán nhãn bằng tay kết quả đầu ra. Trong bài toán khóa luận nêu ra dưới đây có thể tự động xác định tập mẫu huấn luyện từ một tập các tên sản phẩm, tự động sinh ra các mẫu trích xuất tên và giá của sản phẩm. Với một tập hạt giống các tên sản phẩm, chúng ta có thể tự động xác định được tập các trang liên quan đến sản phẩm, sau đó sẽ sinh ra các mẫu trích xuất thông tin về tên và giá sản phẩm một cách tự động trong tập trang liên quan này dựa vào tập luật nêu ở 3.3.2. 34 Mô tả bài toán - Đầu vào: Một tập hạt giống tên các sản phẩm. - Đầu ra: Các website kinh doanh sản phẩm và các mẫu trích xuất thông tin về tên, giá của các sản phẩm trong website đó. Phương pháp giải quyết bài toán Để giải quyết bài toán này khóa luận sử dụng bài toán xác định giá thực của sản phẩm nêu ở mục 3.3.2. - Bước 1: Xác định các trang lên quan Với tập hạt giống các tên này, ta sẽ tạo ra các truy vấn gửi đến máy tìm kiếm, kết quả trả về sẽ được những trang liên quan đến sản phẩm đó. Cụ thể ta sẽ giải quyết bước 1 như sau : Với tên sản phẩm ta sẽ tạo ra những truy vấn gửi tới máy tìm kiếm, kết quả trả về của máy tìm kiếm là các trang liên quan đến sản phẩm. Ví dụ: với tên sản phẩm nokia 1200, ta sẽ tạo truy vấn “nokia 1200” gửi tới máy tìm kiếm google ta sẽ xác định được các trang liên quan đến sản phẩm nokia 1200 như hình 21 sau. 35 Hình 21. Kết quả google trả về với truy vấn "nokia 1200" Tuy nhiên các kết quả trả về có thể chỉ là trang giới thiệu, trang tin tức về sản phẩm, ngay trong ví dụ trên thì kết quả đầu tiên trả về của máy tìm kiếm lại là một trang tin tức sản phẩm.Vì vậy ta phải tối ưu những truy vấn gửi đến máy tìm kiếm để đạt được kết quả tốt nhất, tức là số lượng trang liên quan đến kinh doanh sản phẩm nhiều nhất. Dựa vào đặc thù của các trang kinh doanh sản phẩm chúng ta có thể tạo ra những truy vấn tốt để gửi tới máy tìm kiếm. Ví dụ: một truy vấn được tối ưu của “nokia 1200” là “nokia 1200” + “vnđ OR usd” Kết quả trả về của máy tìm kiếm google được minh họa trong hình 22: Trang tin tức Trang kinh doanh sp 36 Hình 22. Kết quả trả về của google với query "nokia 1200" + "vnđ OR usd" Qua ví dụ này chúng tôi thấy nếu tối ưu các truy vấn gửi đến máy tìm kiếm thì kết quả trả về những trang kinh doanh sản phẩm xuất hiện nhiều hơn, như trong ví dụ trên thì 6 trang đầu tiên này đều là trang kinh doanh sản phẩm. - Bước 2: Lấy được mẫu trích xuất tương ứng với từng trang ở bước 1. Với mỗi một trang liên quan được xác định ở bước 1, nó sẽ tương ứng là trang liên quan đến một sản phẩm trong tập hạt giống. Cặp “tên sản phẩm, trang lên quan đến sản phẩm” sẽ làm đầu vào cho “bài toán trích xuất thông tin giá của một sản phẩm xác định”, kết quả trả về sẽ là các mẫu trích xuất tương ứng với từng trang. - Bước 3: Xác định được website kinh doanh và các mẫu trích xuất tương ứng. Qua bước 2 ta sẽ thống kê được những cặp mẫu trích xuất trên từng website. Trang kinh doanh sp 37 Để xác định được một website là kinh doanh sản phẩm. Chúng tôi sử dụng một phương pháp thống kê đó là thống kê số lượng sản phẩm có thể trích xuất được giá trong website đó. Nếu số lượng này lớn hơn một ngưỡng thì website này sẽ là website kinh doanh sản phẩm. Ngưỡng này được xác định thông qua số lượng sản phẩm trong tập hạt giống. Sau khi đã xác định được website kinh doanh sản phẩm. Khóa luận này xác định được các mẫu trích xuất thông tin về tên sản phẩm và giá sản phẩm tương ứng với website đó. Thống kê sự trùng lặp của các mẫu trích xuất, nếu độ trùng lặp lớn hơn một ngưỡng thì mẫu trích xuất đó có thể áp dụng cho các trang khác trong cùng website này. 3.4 Các bước xây dựng hệ thống Như nhận xét nêu ở phần 3.1.3 về “vấn đề của các hệ thống hiện tại”. Khóa luận đã xác định được việc phải xây dựng một hệ thống tìm kiếm giá cả có thể giải quyết được những vấn đề đó. Dưới các cơ sở thực tiễn và cơ sở lý thuyết nêu ở trên, khóa luận này đã đưa ra mô hình để xây dựng hệ thống hoàn toàn tự động, có thể tự động xác định được các website kinh doanh sản phẩm lượng nhỏ tên sản phẩm ban đầu và có thể tự động trích xuất thông tin về tên và giá của sản phẩm trong các website đó. Trong phần này khóa luận đưa ra mô hình hệ thống và nêu lên được khả năng tự động mở rộng của hệ thống. 3.4.1 Mô hình hệ thống 38 • Mô hình tổng quan Hình 23. Mô hình tổng quan của hệ thống Trước hết, tập hạt giống các tên sản phẩm được đưa qua “module xác định website kinh doanh sản phẩm và mẫu trích xuất” để tạo ra một tập các website kinh doanh sản phẩm và mẫu trích xuất tên, giá sản phẩm tại các website đó. Các website và mẫu trích xuất tương ứng này sẽ qua “module thu thập dữ liệu và trích xuất thông tin” để thu thập được tên sản phẩm và giá của sản phẩm, thông tin này sẽ được cập nhật vào cơ sở dữ liệu “thông tin sản phẩm” và “tập hạt giống tên sản phẩm”. 39 • Module xác định các website kinh doanh sản phẩm và các mẫu trích xuất 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 Module này được xây dựng trên cơ sở “bài toán động trích xuất thông tin về tên và giá của các trang sản phẩm”. Tập hạt giống ban đầu qua tiến trình “xác định các trang liên quan” để được một tập các trang liên quan đến sản phẩm. Tập các trang liên quan sẽ được qua tiến trình “trích xuất các mẫu trích xuất thông tin” để đạt được các mẫu trích xuất và website tướng ứng với mẫu trích xuất đó. Các mẫu và website này sẽ được thống kê sự trùng lặp, để đạt được website và mẫu trích xuất phù hợp với website. 40 • Module Thu thập dữ liệu và trích xuất thông tin Hình 25. Module Thu thập dữ liệu và trích xuất thông tin Sau khi xác định được các website và các mẫu trích xuất thông tin của website, thì website này sẽ được thu thập dữ liệu. Sau đó tập dữ liệu thu thập này sẽ được qua module trích xuất thông tin để lấy các thông tin về sản phẩm: tên sản phẩm và giá của sản phẩm. Các thông tin này sẽ được cập nhật vào cơ sở dữ liệu về sản phẩm, tên của sản phẩm sẽ được dùng để mở rộng tập hạt giống. 3.4.2 Khả năng mở rộng của hệ thống Hệ thống có thể xác định được nhiều trang và mẫu trích xuất hay không phụ thuộc vào kích cỡ của tập hạt giống. Do tên sản phẩm thu dược thông qua module thu thập và trích xuất dữ liệu được cập nhật tiếp vào tập hạt giống tên sản phẩm, vì thế cơ sở dữ liệu về “tập hạt giống sản phẩm” sẽ luôn được cập nhật. Vì vậy hệ thống luôn được mở rộng. 41 Chương 4. Thực nghiệm và đánh giá kết quả Để đánh giá được hệ thống tìm kiếm giá cả, khóa luận sẽ tập trung đánh giá khả năng thu thập dữ liệu về tên và giá của sản phẩm. Trong chương này khóa luận đưa ra 3 thực nghiệm để đánh giá khả năng thu thập thông tin về tên và giá sản phẩm của hệ thống, đưa ra các bảng kết quả đạt được của từng thực nghiệm và những nhận xét, đánh giá kết quả đó. 4.1 Môi trường phần cứng và phần mềm 4.1.1 Cấu hình phần cứng Bảng 1 mô tả cấu hình phần cứng sử dụng trong thực nghiệm. Bảng 1. Cấu hình phần cứng sử dụng trong thực nghiệm Thành phần Chỉ số CPU Intel Celeron ® CPU 2.66 ghz RAM 768 MB Hệ điều hành WindowsXP Service Pack 2 Bộ nhớ ngoài 40GB 4.1.2 Công cụ phần mềm Các công cụ phần mềm mã nguồn mở mà khóa luận sử dụng để xây dựng thực nghiệm được mô tả ở bảng 2 dưới đây 42 Bảng 2.Các phần mềm sử dụng trong thực nghiệm STT Tên phần mềm Tác giả Nguồn 1 Neko HTML Phân phối bởi Apache kohtml 2 eclipse-SDK- 3.4.1-win32 s/ Với các công cụ phần mềm trên khóa luận đã xây dựng chương trình để thực thi trích xuất giá của sản phẩm. Cấu trúc chương trình được phân làm 3 gói (package) chính như sau: • Crawler : chức năng chính của gói này đó là thu thập dữ liệu • GettingPattern: Chức năng của gói này là xác định mẫu trích xuất thông tin về giá và tên sản phẩm của một trang web. • Extracting: chức năng của gói này đó là trích là xác định các website kinh doanh và trích xuất tên, giá sản phẩm trong website đó. Chi tiết các lớp của 3 gói này được mô tả theo bảng 3 bên dưới. 43 Bảng 3. Mô tả chương trình thực thi để trích xuất giá sản phẩm Tên gói (package) Tên lớp (class) Chức năng Crawling Thu thập dữ liệu từ một website SEProcessing Thu thập các url trả về từ truy vấn gửi đến google Crawler StandardHTML Loại bỏ một số thành phần không quan trọng trong mã HTML như các đoạn mã SCRIPT, STYLE … ParserHTML Phân tích mã HTML sang dạng cây DOM (sử dụng NekoHTML) GettingXPath Xác định tất cả các mẫu trích xuất trỏ đến tên và giá sản phẩm. GettingPattern ProcessingXPath Xác định được mẫu trích xuất chính xác tên và giá sản phẩm. GettingWebsite Xác định được website kinh doanh sản phẩm và mẫu trích xuất của website đó Extracting ExtractingInformation Trích xuất thông tin về tên, giá các sản phẩm trong các website kinh doanh sản phẩm 44 4.2 Kết quả thực nghiệm 4.2.1 Thực nghiệm trích xuất giá của một sản phẩm cho trước Mô tả thực nghiệm Mục đích của thực nghiệm này để kiểm nghiệm tính đúng đắn của “bài toán xác định giá thực của sản phẩm” bằng các luật nêu ở mục 3.3.2. - Đầu vào : Tên sản phẩm và trang web chứa tên sản phẩm đó. - Đầu ra : Giá của sản phẩm nếu trang web có chứa giá. Dữ liệu thực nghiệm - Dữ liệu để trích xuất giá của một sản phẩm được thu thập thông qua máy tìm kiếm google. - Với một tên sản phẩm cho trước, ta sẽ tạo ra truy vấn gửi đến máy tìm kiếm. o Ví dụ: Với tên sản phẩm máy ảnh “Canon PowerShot G10” thì truy vấn gửi đến máy tìm kiếm sẽ là : “Canon PowerShot G10” + “VNĐ OR USD” - Lấy một lượng kết quả trả về đầu tiên của máy tìm kiếm, ta sẽ trích xuất được tập các url từ kết quả đó o Ví dụ: Ứng với truy vấn “Canon PowerShot G10” + “VNĐ OR USD” thì 5 kết quả đầu tiên trả về thông qua máy tìm kiếm google và các url tương ứng được mô tả trong hình 26 dưới đây : 45 Hình 26. Trích xuất các URL liên quan - Sau đó các url này sẽ được chuẩn hóa về dạng chuẩn và được tải dữ liệu trang web đó về. - Dữ liệu được tải về được cho qua module trích xuất giá để sinh ra giá của sản phẩm. Ví dụ: Tương ứng với 5 URL trên thì kết quả trích xuất được sẽ là: - o Product: canon powershot g10 Price:8.008.000 vnđ (440,00 usd) URL trích xuất 46 - o Product: canon powershot g10 Price: giá 490 usd - o Product: canon powershot g10 Price:644 sd - G10.html o Product: máy chụp hình canon powershot g10 Price:8.550.000vnđ - o Product: canon powershot g10 Price:665 usd Khóa luận đã thực nghiệm trên tập các sản phẩm: nokia 1200, lenovo thinkpad t61, canon powershot g103; mỗi sản phẩm này sẽ thực nghiệm trên 3 trường hợp tương ứng với số lượng 10, 30, 100 kết quả mà google trả về. Để đánh giá kết quả thực nghiệm khóa luận này sử dụng độ đo hồi tưởng (R) và độ tin cậy (P). Kết quả thực nghiệm mô tả theo bảng 4 47 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 Tên sản phẩm Query Số lượng kết quả trả về bởi google Kết quả thực tế đúng Kết quả trích xuất được Kết quả đúng Thời gian thực thi Độ hồi tưởng Độ tin cậy 10 8 8 8 37,45 s 100% 100% 30 23 26 23 147,4 3s 100% 88,46% Nokia 1200 “Nokia 1200” + “VNĐ OR USD” 100 68 70 67 407,1 7s 98,53 % 95,71 % 10 10 10 9 39,67s 90% 90% 30 23 25 22 125,2 5s 95,6% 88% Lenovo Thinkpad t61 “Lenovo Thinkpad t61” + “VNĐ OR USD” 100 43 46 40 1200s 93,02% 86,95% 10 9 9 9 52,92s 100% 100% 30 19 21 18 86,91s 94,74 % 85,71 % Canon PowerShot G10 “Canon PowerSho t G10” + “VNĐ OR USD” 100 45 50 44 263,3 3s 97,78% 88% 48 Nhận xét Với tất cả các kết quả đạt được thì ta có thể thấy rằng độ tin cậy thấp hơn độ hồi tưởng. Sở dĩ có kết quả như vậy bởi vì: Có một vài trường hợp giá xuất hiện quá nhập nhằng. Hình 27 là minh họa về trường hợp trang web chứa giá nhập nhằng. Hình 27. Trang Web có sự nhập nhằng giá cả Với trường hợp này có thể nhận dạng nhầm thành: “nokia 1200” có giá: “599.000 đồng” Thực tế thì nó lại muốn cung cấp thông tin về “nokia 1202” có giá: “599.000 đồng” Độ hồi tưởng cao bởi vì hầu như các trang có giá đúng thì có thể trích xuất được chính xác. Giá đúng là giá mà thể hiện là giá thực của sản phẩm. 49 Ví dụ: Hình 28 là minh họa về trang web chứa giá không nhập nhằng Hình 28. Trang Web có giá cả rõ ràng Kết quả trích xuất được sẽ là: Tên sản phẩm: nokia 1200 black , Giá sản phẩm: 520,000 vnđ 4.2.2 Thực nghiệm xác định website kinh doanh Mô tả thực nghiệm Mục đích của thực nghiệm này là kiểm nghiệm sự chính xác và khả năng xác định được các trang kinh doanh sản phẩm từ tập hạt giống tên sản phẩm ban đầu của 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 mục 3.3.3 - Đầu vào : Một tập hạt giống tên các sản phẩm. - Đầu ra : Website kinh doanh sản phẩm có bán những sản phẩm trong tập hạt giống đó và các mẫu trích xuất tương ứng với website. Dữ liệu thực nghiệm - Tập hạt giống tên sản phẩm cho trước. - Chọn máy tìm kiếm google để xác định các trang liên quan đến sản phẩm 50 - Tạo truy vấn từ tên các sản phẩm ở tập hạt giống, gửi tới google, để thu được các trang liên quan - Tải các trang liên quan đến sản phẩm và xác định được các mẫu trích xuất thông tin sản phẩm, ta sẽ thu được một bộ (Website, mẫu_trích_tên sản phẩm, mẫu_trích_giá sản phẩm) Xác định sự trùng lặp của các bộ, nếu một bộ trùng lặp nhiều lần, thì website trong bộ đó là website kinh doanh và các mẫu trích xuất trong bộ là mẫu trích xuất có thể áp dụng cho website này. Với tập hạt giống gồm 4 tên sản phẩm như sau : - nokia 1200 - nokia e71 white steel - nokia 1202 - nokia 6300 silver Chọn ngưỡng là 3 thì ta có: Kết quả thực nghiệm được mô tả thông qua bảng 5 51 Bảng 5. Kết quả thực nghiệm xác định website kinh doanh sản phẩm Số lượng kết quả từ google trả về Thời gian chạy Domain bán hàng nhận được 10 288,84s www.123mua.com.vn www.vatgia.com www.chodientu.vn www.vinacms.vn 30 708s www.123mua.com.vn www.vatgia.com www.chodientu.vn www.vinacms.vn www.enbac.com 100 3638.76s www.123mua.com.vn www.vatgia.com www.chodientu.vn www.vinacms.vn www.enbac.com www.quangcaosanpham.com www.dienthoaididong.com.vn www.aha.vn www.trananh.vn 52 Nhận xét Kết quả đạt được là khả quan. Trong các website mà hệ thống xác định được thì tất cả đều là website kinh doanh sản phẩm. Tương ứng với các trường hợp : - google trả về là 10 thì nhận dạng được 4 website - google trả về là 30 thì nhận dạng được 5 website - google trả về là 100 thì nhận dạng được 10 website Tuy nhiên do số lượng tập hạt giống ban đầu mới chỉ có 4 tên sản phẩm nên số lượng website kinh doanh sản phẩm nhận dạng được vẫn còn ít. 4.2.3 Thực nghiệm thu thập và trích xuất thông tin từ một website Mô tả thực nghiệm Mục đích của thực nghiệm này để kiểm nghiệm phương pháp trích xuất thông tin sản phẩm nêu ở “bài toán tự động trích xuất tên và giá của sản phẩm” trong muc 3.3.3. Thực nghiệm này cũng giúp đánh giá được tính chính xác của các mẫu trích xuất trong thực nghiệm 4.3.2 - Đầu vào : Website kinh doanh và các mẫu trích xuất tương ứng với wesite đó ở thực nghiệm xác định website kinh doanh. - Đầu ra : Tên sản phẩm và giá của các sản phẩm . Dữ liệu sử dụng Trong thực nghiệm này chúng tôi sẽ sử dụng 2 website trong thực nghiệm 2: - www.dienthoaididong.com.vn - www.trananh.vn Hai website kinh doanh sẽ được thu thập dữ liệu, với số lượng 5000 tài liệu trên một website và trích xuất dữ liệu từ tập dữ liệu này dựa vào các mẫu trích xuất tương ứng với từng website đó. 53 Kết quả thực nghiệm được mô tả thông qua bảng 6. Bảng 6. Kết quả thực nghiệm trích xuất sản phẩm Website Kết quả trích xuất được www.dienthoaididong.com.vn 743 sản phẩm www.trananh.vn 416 sản phẩm Nhận xét Số lượng sản phẩm trích xuất được là khá nhiều. Trong số những sản phẩm trích xuất được thì tất cả những sản phẩm đó đều chính xác, điều đó cho thấy phương pháp trích xuất thông tin này chính xác. Tuy nhiên trong 416 sản phẩm của website www.trananh.vn thì chỉ có các sản phẩm về điện thoại di động trong khi website này còn có những sản phẩm về máy vi tính, nguyên nhân của kết quả này là do sản phẩm trên tập hạt giống đều là tên của các loại điện thoại di động và khuôn mẫu của lĩnh vực điện thoại và máy tính ở website này là khác nhau. 4.2.4 Thực nghiệm khả năng thu thập thông tin của hệ thống Mô tả thực nghiệm Mục đích thực nghiệm này là đánh giá khả năng thu thập thông tin về tên và giá sản phẩm của hệ thống - Đầu vào: Tập hạt giống tên sản phẩm - Đầu ra: Tên và giá của những sản phẩm có thể trích xuất được. Dữ liệu thực nghiệm Tên sản phẩm trong tập hạt giống được lấy từ trang vatgia.com [19]. Các tên sản phẩm này được phân bố đều nhiều loại sản phẩm như: điện thoại, máy tính, máy ảnh, trang sức, đồ gia dụng… 54 Kết quả thực nghiệm được mô tả thông qua bảng 7 dưới đây. Bảng 7. Kết quả thực nghiệm khả năng thu thập thông tin của hệ thống Số lượng tên sản phẩm trong tập hạt giống Số lượng website kinh doanh được xác định Số lượng sản phẩm trích xuất được 334 sản phẩm 125 trang kinh doanh (phụ lục 2) 47.856 sản phẩm, trong đó có 34.012 sản phẩm không trùng nhau Nhận xét: Kết quả này cho thấy khả năng thu thập thông tin trong hệ thống đạt hiệu quả tốt. Số lượng sản phẩm được hệ thống trích xuất được là lớn, những sản phẩm này cũng dàn trải trên nhiều chủng loại . Một số sản phẩm tiêu biểu được minh họa bởi bảng 8. Bảng 8. Một số sản phẩm trích xuất được Tên sản phẩm Giá sản phẩm Chủng loại nokia 2680 slide 1,530,000 vnđ Điện thoại di động canon powershot g10 8.645.000 vnđ Máy ảnh kỹ thuật số dell inspiron mini 9 - r560921vn ( pc - dos ) 8,029,000 vnđ Máy laptop Comple nam hiệu Cavil Klein 14.560.000 vnđ Thời trang Phấn trang điểm - Ohui 575.000 vnđ Mỹ phẩm 55 Kết luận Kết quả đạt được của khóa luận này Từ việc nghiên cứu bài toán trích xuất thông tin cho dữ liệu bán cấu trúc, khóa luận đã đưa ra phương pháp tự động trích xuất giá của sản phẩm. Qua những kết quả thực nghiệm đạt được cho thấy tính hữu dụng của phương pháp này. Về mặt nội dung, khóa luận đã đạt được những kết quả sau: - Trình bày khái niệm, miền dữ liệu và các hướng tiếp cận của bài toán trích xuất thông tin trên Web - Nghiên cứu bài toán trích xuất thông tin cho dữ liệu bán cấu trúc: Nêu được những phương pháp sử dụng trong việc trích xuất, giới thiệu hai giải thuật trích xuất Stalker và Roadrunner đồng thời phân tích những ưu nhược điểm của các giải thuật này nhằm xây dựng phương pháp phù hợp để giải quyết bài toán trích xuất thông tin giá sản phẩm. - Xây dựng được tập luật để trích xuất giá khi biết tên sản phẩm trong một trang web, ngoài ra khóa luận cũng xây dựng được các tập luật để trích xuất ảnh, thông tin bảo hành của sản phẩm. - Xây dựng được mô hình hệ thống tìm kiếm giá cả sản phẩm dựa vào cơ sở lý thuyết của bài toán trích xuất thông tin giá sản phẩm. - Xây dựng được module trích xuất giá sản khi biết tên sản phẩm. - Xây dựng module xác định website kinh doanh sản phẩm. - Xây dựng được module trích xuất thông tin về tên và giá sản phẩm trong một website kinh doanh sản phẩm thông qua các mẫu trích xuất. - Xây dựng được chương trình để thi hành được bài toán trích xuất thông tin giá cả sản phẩm và đạt được kết quả khả quan trong việc thu thập thông tin. 56 Bên cạnh những, do hạn chế về mặt thời gian và kiến thức khóa luận vẫn còn hạn chế sau: - Khóa luận chưa xây dựng được giao diện người dùng và kết quả thực nghiệm xác định giá thực của một sản phẩm cho trước chưa đạt độ chính xác như mong muốn. Định hướng tương lai Trong tương lai, khóa luận sẽ tiếp tục hoàn thiện những hạn chế nên trên, đồng thời cũng cố gắng để công bố hệ thống này để phục vụ cho người sử dụng. 57 Tài liệu tham khảo [1]. Andrew Carlson and Charles Schafer, Bootstrapping Information Extraction from Semi-structured Web Pages, ECML/PKDD, 2008. [2]. Bing Liu, Web Data Mining Exploring Hyperlinks, Contents, and Usage Data, ,December, 2006. [3]. Elwin Chai, Rick Jones, Automated Price Comparison Shopping Search Engine _ PriceHunter, CSE,2001 [4]. Irmak, and T. Suel, Interactive Wrapper Generation with Minimal User Effort. In Proc. of the 15th Intl. Conf. on World Wide Web (WWW'06), 2006. [5]. I. Muslea, S. Minton, and C. A. Knoblock. A Hierarchical Approach to Wrapper Induction. In Proc. of the Intl. Conf. on Autonomous Agents (AGENTS’99), pp. 190– 197, 1999. [6]. Jaeyoung Yang, Heekuck Oh, Kyung-Goo Doh and Joongmin Choi A ,Knowledge- Based Information Extraction System for Semi-structured Labeled Documents, Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning, 2002 [7]. Robert Bo Doorenbos, Oren Etzioni, and Daniel So Weld, A Scalable Comparison- Shopping Agent for the World-Wide Web, www.cs.washington.edu/homes/etzioni/papers/agents97.pdf, 1997 [8]. Sergey Brin, Extracting Patterns and Relations from the World Wide Web, WebDB Workshop at 6th International Conference on Extending Database Technology, 1998 [9]. S. Debnath, P. Mitra, N. Pal, and C. L. Giles. Automatic Identification of Informative , IEEE Trans. Knowl. Data Eng. 17 , 2005 [10]. S. Debnath, P. Mitra, and C. L. Giles. Automatic extraction of informative blocks from webpages. In Proc. SAC, pages 1722-1726, 2005. [11]. Sections of Web-pages. In TKDE, pages 1233–1246, 2005. 58 [12]. V. Crescenzi, G. Mecca, and P. Merialdo. Roadrunner: Towards Automatic Data Extraction from Large Web Sites.In Proc. of Very Large Data Bases (VLDB’01), pp.109–118, 2001. [13]. WIEN N. Kushmerick. Wrapper Induction for Information Extraction. Ph.D Thesis. Dept. of Computer Science, University of Washington, TR UW-CSE-97-11- 04, 1997 [14]. W. Cohen, M. Hurst, and L. S. Jensen. A Flexible Learning System for Wrapping Tables and Lists in Html Documents. In Proc. of the 11th Intl. World Wide Web Conf. (WWW’02), pp. 232–241, 2002. [15]. [16]. [17]. [18]. [19]. 59 Phụ lục Phụ lục 1: Danh sách một số website được khảo sát đặc trưng của giá sản phẩm Địa chỉ website www.amazon.com www.jr.com www.imobilecellphones.com www.220depot.com www.trananh.vn www.vatgia.com www.rongbay.com www.vinabook.com www.sieuthitrangsuc.com www.aodaiminhthu.com www.goodsmart.vn 60 Phụ lục 2: Danh sách một số website kinh doanh xác định được trong thực nghiệm 4.4.4 Địa chỉ website www.ducminhmobile.net www.gsmserver.com www.gounlock.com www.123mua.com.vn www.dienthoaididong.com.vn www.vatgia.com www.aha.vn www.chodientu.vn www.raovat.net www.trananh.vn www.megabuy.vn