Mẫu 1a MẪU BÌA LUẬN VĂN CĨ IN CHỮ NHŨ VÀNG Khổ 210 x 297 mm PHẠM NGUYỄN TUẤN ANH BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - Phạm Nguyễn Tuấn Anh CÔNG NGHỆ THƠNG TIN TỰ ĐỘNG TRÍCH XUẤT THƠNG TIN SẢN PHẨM TRÊN WEB ỨNG DỤNG KỸ THUẬT SIMHASH LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN 2009 Hà Nội – 2011 MẪU TRANG PHỤ BÌA LUẬN VĂN Mẫu 1b BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Phạm Nguyễn Tuấn Anh TỰ ĐỘNG TRÍCH XUẤT THÔNG TIN SẢN PHẨM TRÊN WEB ỨNG DỤNG KỸ THUẬT SIMHASH Chuyên ngành : Công nghệ thông tin LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC : TS NGUYỄN KHANH VĂN Hà Nội – 2011 Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 MỤC LỤC MỤC LỤC T 26T ĐẶT VẤN ĐỀ .4 T 26T CHƯƠNG I: KHÁI QUÁT BÀI TOÁN TRÍCH XUẤT THƠNG T TIN CHO DỮ LIỆU BÁN CẤU TRÚC T Bài tốn trích xuất thơng tin T T 1.1 Giới thiệu toán T 26T 1.2 Dữ liệu toán T 26T Các hướng tiếp cận toán trích xuất thơng tin 11 T T Bài tốn trích xuất thơng tin cho liệu bán cấu trúc 12 T T 3.1 Vấn đề đặt với toán 12 T T 3.2 Một số phương pháp trích xuất thơng tin cho liệu bán cấu trúc 13 T T 3.3 Phương pháp đánh giá .13 T 26T 3.4 Ứng dụng tốn trích xuất thơng tin cho liệu bán cấu trúc 14 T T CHƯƠNG II: MỘT SỐ PHƯƠNG PHÁP SỬ DỤNG TRONG T BÀI TỐN TRÍCH XUẤT THƠNG TIN CHO DỮ LIỆU BÁN CẤU TRÚC .17 26T Trích xuất thông tin dựa vào DOM 17 T T 1.1 Khái nhiệm DOM .17 T 26T 1.2 Xây dựng DOM 18 T 26T 1.3 Sử dụng DOM để trích xuất thơng tin 20 T T 2 Trích xuất thơng tin dựa theo mẫu biểu thức qui 21 T T 2.1 Khái niệm biểu thức qui 21 T T 2.2 Sử dụng biểu thức qui để trích xuất thơng tin 22 T T Một số giải thuật trích xuất thơng tin cho liệu bán cấu trúc 22 T T -1- Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 3.1 Hai kiểu biểu diễn trang giàu liệu 22 T T 3.2 Một số giải thuật điển hình 23 T T CHƯƠNG III: PEWEB – HỆ THỐNG BĨC TÁCH THƠNG TIN T SẢN PHẨM DỰA TRÊN TÍNH TỐN ENTROPY .29 T Xây dựng HTML 29 T 26T Tính tốn Entropy 30 T 26T CHƯƠNG IV: TỰ ĐỘNG TRÍCH XUẤT THƠNG TIN SẢN T PHẨM TRÊN WEB ỨNG DỤNG KỸ THUẬT SIMHASH 39 T Bài tốn trích xuất thơng tin sản phẩm từ website thương mại 39 T T 2 Kỹ thuật xác định vị trí vùng mơ tả sản phẩm sử dụng Simhash 41 T T 2.1 Các trang web thương mại DOM 42 T T 2.2 Kỹ thuật Simhash dùng phát văn trùng lặp 44 T T 2.3 Sử dụng Simhash để tìm tương tự DOM .44 T T 2.4 Xây dựng định cho trình lọc kết 47 T T Cài đặt hệ thống bóc tách thơng tin sản phẩm sử dụng Simhash 49 T T 3.1 Tìm kiếm vùng có khả chứa thơng tin sản phẩm 49 T T 3.2 Loại bỏ nhiễu 51 T 26T Chương trình bóc tách thơng tin sản phẩm 52 T T Các kết thực nghiệm 55 T 26T Kết luận hướng phát triển 58 T 26T TÀI LIỆU THAM KHẢO .60 T T -2- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 DANH MỤC HÌNH Hình 1: Ví dụ tính cấu trúc trang web bán cấu trúc 10 U T T U Hình 2: Ví dụ toán nhận dạng thực thể 11 U T T U Hình 3: Ví dụ trích xuất nội dung trang Web 15 U T T U Hình 4: Ví dụ hệ thống tìm kiếm giá 16 U T T U Hình 5: Ví dụ xây dựng DOM sử dụng hộp ảo 20 U T T U Hình 6: Dạng biểu diễn trang list page 23 U T T U Hình 7: Dạng biểu diễn trang detail page 23 U T T U Hình 8: Chuyển đổi từ mã HTML sang EC 24 U T T U Hình 9: Ví dụ giải thuật RoadRunner 28 U T T U Hình 10: Các mơ tả sản phẩm DOM 31 U T T U Hình 11: Q trình tính giá trị đại diện 32 U T T U Hình 12: Một trang web bán máy tính xách tay 43 U T T U Hình 13: Các vùng sản phẩm vị trí chúng DOM 43 U T T U Hình 14: Một ví dụ q trình tính Simhash node T 46 U T T U Hình 15: Cây định xác định vùng có vùng sản phẩm hay khơng U T T U 48 Hình 16: Giao diện chương trình bóc tách thơng tin sản phẩm 53 U T T U Hình 17: Sau nhập đường link trang web bán hàng, chương tình tiến U T hành phần tích cấu trúc trang web xây dựng DOM tương ứng 54 T U Hình 18: Kết sau tìm bóc tách thơng tin từ vùng chứa thông tin U T sản phẩm 55 26T U -3- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 ĐẶT VẤN ĐỀ Nhưng năm gần đây, với phát triển mạnh mẽ hạ tầng sở mạng công nghệ lưu trữ Internet trở thành thành phần thiếu đời sống người Hàng loạt ứng dụng dựa tảng Internet đời để phục vụ cho nhu cầu, lợi ích người Nổi bật lên ứng dụng ứng dụng liên quan đến thương mại điện tử Thương mại điện tử đời giúp người giảm thiểu tối đa thời gian chi phí tham gia giao dịch hàng hóa Tuy nhiên với phát triển thơng tin Internet thông tin liên quan đến thương mại điển tử bùng nổ không kém, hàng loạt trang web bán hàng trực tuyến với hàng triệu sản phẩm thông tin liên quan đến sản phẩm làm cho người khó khăn việc tìm kiếm Các câu hỏi: Sản phẩm tốt ? Giá cửa hàng tốt ? Tìm kiếm thơng tin sản phẩm đâu ? làm người khó khăn lựa chọn sản phẩm cần giao dịch Giải pháp cho vấn đề cần có hệ thống tìm kiếm phục vụ cho nhu cầu tìm kiếm người hệ thống thường biết đến với tên gọi hệ thống tìm kiếm giá sản phẩm Chính từ nhu cầu thực tế đấy, hệ thống tìm kiếm giá nhiều quan tâm máy tìm kiếm (Search Engine) lớn giới Google, Yahoo, Bing… Ngồi dịch vụ tìm kiếm thơng thường khác, Search Engine có dịch vụ tìm kiếm riêng cho sản phẩm, hàng hoá rao bán trực tuyến website thương mại Cách thức hoạt động chung dịch vụ tìm kiếm sản phẩm trực tuyến là: sau thu thập trang web website thương mại lưu vào kho liệu mình, Search Engine tiến hành bóc tách thơng tin liên qua đến mặt hàng sản phẩm có trang web đó, tổ chức lưu trữ liệu bóc tách hợp lý để nhanh chóng đáp ứng truy vấn từ người dùng Những thông tin mà người dùng quan tâm đến sản phẩm thường tên sản -4- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 phẩm, giá cả, mô tả chi tiết sản phẩm, hay địa rao bán… Nếu việc thu thập tổ chức lưu trữ liệu vấn đề khó khăn Search Engine, liệu sản phẩm trực tuyến phần nhỏ so với liệu toàn liệu Web, vấn đề bóc tách thơng tin sản phẩm thực đặt nhiều thách thức cho Search Engine Có thể nói, chất lượng dịch vụ tìm kiếm phụ thuộc nhiều vào chất lượng q trình bóc tách thơng tin sản phẩm Chỉ có phương pháp bóc tách thơng tin sản phẩm thật đầy đủ chi tiết, Search Engine đem lại kết tìm kiếm tốt cho người dùng Vấn đề tiến hành bóc tách thơng tin sản phẩm từ trang web bán hàng trực tuyến xác định vị trí phần chứa thơng tin sản phẩm có trang web Tuy nhiên, khơng phải vấn đề giải cách dễ dàng Trên trang web bán hàng, khu vực chứa thơng tin sản phẩm, cịn có vùng thông tin khác menu, quảng cáo, danh sách danh mục mặt hàng… Các phương pháp bóc tách sản phẩm cần phải phân biệt vùng chứa không chứa thơng tin sản phẩm, để khơng phát thiếu hay nhầm lẫn, làm ảnh hưởng tới trình bóc tách sau Khó khăn mà Search Engine gặp phải website có cách trình bày hay bố trí sản phẩm trang web riêng, cách trình bày thay đổi cách thường xuyên Cộng với việc số lượng website bán hàng, dẫn đến số lượng trang web chứa thơng tin sản phẩm, lớn Search Engine thực cần phương pháp nhanh mà cịn phải hồn tồn tự động để xác định vị trí vùng sản phẩm trang web Do đó, vấn đề đặt nghiên cứu từ nhiều năm Bóc tách thơng tin sản phẩm vấn đề nằm tốn bóc tách thơng tin Web nói chung Từ lâu, tốn bóc tách liệu từ Web đặt nghiên cứu để phục vụ cho nhiều mục đích, để thu thập viết từ trang báo điện tử, thơng tin tài chính… Các phương pháp trích xuất thơng tin Web nhiều áp dụng cho tốn bóc tách thơng tin sản phẩm Từ trước tới nay, bóc tách -5- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 liệu Web thường xây dựng chương trình đặc biệt, gọi wrapper, để tìm liệu cần xây dựng khung để áp dụng vào trang web, ta có liệu mong muốn Việc xây dựng trì wrapper khó khăn, có nhiều cải tiến cho việc Sau vài phương pháp công cụ tương ứng xây dựng wrapper, tính hiệu chúng dựa khả tự động chúng - Ngôn ngữ xây dựng wrapper: hướng tiếp cận thiết kế ngôn ngữ đặc biệt nhằm hỗ trợ người xây dựng wrapper dễ dàng Một vài công cụ bật Minera[11] TSIMMIS[15], Web-OQL[3] Các ngơn ngữ sử dụng để thay ngơn ngữ lập trình - Các công cụ dựa HTML: Hướng tiếp cận nhằm xây dựng cơng cụ dựa vào đặc tính cấu trúc vốn có văn HTML để trích xuất liệu Trong q trình tiền xử lý, công cụ sử dụng hướng tiếp cận này, W4F[27], XWRAP[21], RoandRunner[10] biến đổi văn thành mà phản ánh tính phân cấp văn HTML - Các công cụ sử dụng kỹ thuật xử lý ngôn ngữ tự nhiên: Trong hướng tiếp cận này, công cụ RAPIER[6], SRV[14], WHISK[31],… xây dựng luật bóc tách thơng tin văn ngôn ngữ tự nhiên sử dụng kỹ thuật NLP, chẳng hạn lọc, gán nhãn, đánh thẻ từ vựng ngữ nghĩa Hướng tiếp cận thường thích hợp để xử lý văn có cú pháp chuẩn - Các cơng cụ wrapper qui nạp: hướng tiếp cận này, luật bóc tách dựa vào dấu phân cách xây dựng từ tập học mẫu Các công cụ wrapper qui nạp, WIEN[18], SoftMealy[16], STALKER[23], thích hợp với văn HTML công cụ sử dung kỹ thuật NLP, chúng phụ thuộc vào đặc tính định dạng tạo nên cấu trúc liệu cần tìm, buộc ngơn ngữ -6- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 - Các công cụ sử dụng mẫu: Ý tưởng hướng tiếp cận tìm trang web mẩu liệu mà khớp với cấu trúc đối tượng cần quan tâm Sau đó, cách sử dụng thuật tốn công cụ wrapper qui nạp, công cụ sử dụng mẫu, NoDoSe[1], DeByE[19] xác định đối tượng có cấu trúc giống với cấu trúc cho trước trang web Một tiêu chí quan trọng so sánh phương pháp bóc tách thông tin mức độ tự động phương pháp Trong hướng tiếp cận ngôn ngữ xây dựng wrapper, người phát triển cần phải viết lượng lớn code, để xây dựng chương trình bóc tách đối tượng cần quan tâm Do đó, người phát triển phải kiểm tra văn tìm thẻ HTML cần cho trình xác định biên đối tượng cách thủ cơng Trong khí đó, có mức độ tự động hố cao hơn, cơng cụ dựa HTML thực hiệu có thẻ HTML trang web Điều khó xảy với số lượng trang web lớn Trong hướng tiếp cận NLP, wrapper qui nạp, sử dụng mẫu, người phát triển phải cung cấp mẫu thử cho trình xây dựng wrapper Do đó, cơng cụ coi bán tự động Có thể thấy rằng, phương pháp bóc tách liệu khơng hồn tồn tự động: chúng cần giai đoạn cần can thiệp người phát triển Điều không khả thi áp dụng để xử lý tập liệu lớn trang web Vấn đề cần đặt phải tìm hướng tiếp cận khác mà q trình bóc tách liệu khơng cần đến tác động từ người phát triển Trong luận văn này, tác giả đề xuất phương pháp hoàn toàn tự động để xác định vùng chứa mơ tả sản phẩm có trang web bán hàng Phương pháp dựa vào hướng tiếp cận có tác giả Phan Xuân Hiếu tác giả khác[32], trình xây dựng hệ thống lấy thông tin sản phẩm, có tên PEWeb Hướng tiếp cận tận dụng tính chất thường gặp trang web bán hàng, vùng chứa sản phẩm trang web thường có cách trình bày giống gần giống Đây đặc tính quan trọng, giúp ta dễ dàng xác định vùng sản -7- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 phẩm trang web Tuy có hướng tiếp cận, phương pháp khác với phương pháp PEWeb Chúng đề xuất sử dụng hàm băm đặc biệt, gọi Simhash, để tìm vùng chứa mơ tả sản phẩm Simhash sử dụng để tìm đối tượng có thuộc tính tương tự nhau, chẳng hạn văn trùng lặp Chúng biến đổi hàm Simhash để áp dụng cho toán xác định vùng chứa sản phẩm trang web Chúng chọn Simhash sử dụng kỹ thuật khơng đem lại kết cao tốc độ xử lý nhanh mà cịn khơng phụ thuộc vào cấu trúc văn HTML cụ thể nên khơng cần có xử lý từ phía người phát triển, hay nói cách khác, hồn tồn tự động Do đó, giải pháp giải khó khăn mà Search Engine gặp phải mà nêu Chi tiết phương pháp đề xuất trình bày kỹ luận văn Luận văn gồm chương nội dung mô tả sơ đây: - Chương 1: Trong chương này, chúng tơi khái qt tốn trích xuất thơng tin cho liệu bán cấu trúc - Chương 2: Chúng tơi trình bày số phương pháp sử dụng tốn trích xuất thơng tin cho liệu - Chương 3: Chúng giới thiệu PEWeb, hệ thống bóc tách thơng tin sản phẩm hồn tồn tự động - Chương 4: Chúng tơi trình bày phương pháp để xác định lấy thông tin sản phẩm từ trang web thương mại -8- Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 nItalics Số lượng thẻ nBrs Số lượng thẻ nLists Số lượng thẻ

nUnits Số lượng ký hiệu tiền tệ (như VNĐ, USD, $ ) nPrices Số lượng từ "Giá", "giá", "Price"… nPromos Số lượng từ "khuyến mãi", "khuyến mại"… nDigits Số lượng ký tự số Bảng 6: Các thuộc tính ghi trình lọc Để xây dựng định từ tập học trên, sử dụng WEKA [33], phần mềm học máy mã nguồn mở tiếng Kết nhận mô tả hình 15 Hình 15: Cây định xác định vùng có vùng sản phẩm hay khơng Có thể thấy từ hình, định khơng sử dụng tồn thuộc tính mà - 48 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 chọn Thực tế, chọn lấy thuộc tính: nUnits, nImages nDigits để định vùng vùng sản phẩm hay không Ta dễ dàng thấy rằng, số thuộc tính này, nUnits thuộc tính quan trọng Quả thực, tập học chúng tôi, hầu hết vùng sản phẩm có thuộc tính nUnits lớn Đây thơng tin quan trọng để phân loại vùng Điều so với thực tế website thương mại, mơ tả sản phẩm ln có đăng giá sản phẩm (kèm với ký hiệu tiền tệ) Cài đặt hệ thống bóc tách thơng tin sản phẩm sử dụng Simhash Phần mô tả cách thức áp dụng kỹ thuật đề xuất để xây dựng hệ thống bóc tách thơng tin sản phẩm Q trình bóc tách cho trang web bao gồm hai giai đoạn: tìm kiếm vùng có khả vùng sản phẩm khử nhiễu (các kết sai giai đoạn 1) 3.1 Tìm kiếm vùng có khả chứa thơng tin sản phẩm Như nói trên, tìm kiếm vùng có khả vùng sản phẩm thực chất tìm tất tương tự DOM sử dụng kỹ thuật Simhash Giả lệnh thuật toán Simhash mơ tả bảng Thuật tốn nhận gốc T tham số đầu vào tính dấu vân tay node T Sau lần duyệt DOM để tính dấu vân tay tất node, duyệt lần để tỉm tương tự Hàm findProductRegions mô tả bảng Hai chọn chúng thoả mãn điều kiện sau: - Chúng thuộc node cha - Độ sâu chúng lớn tham số h - Dấu vân tay chúng sai khác nhiều n bit vị trí (n gọi ngưỡng sai khác) - 49 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 Ta có điều kiện giải thích phần trước: vùng sản phẩm thường biểu diễn liên tiếp vùng, tương ứng với việc có node cha Điều kiện thứ hai có từ quan sát chúng tôi: vùng sản phẩm thường nằm có độ sâu lớn ngưỡng đó, tham số h Do đó, chúng tơi sử dụng ngưỡng để loại bỏ "nhiễu" mà không thực chứa mơ tả sản phẩm Giải thuật – Simhash: Tính dấu vân tay Simhash Đầu vào: node T DOM HTML Đầu ra: dấu vân tay Simhash T Khởi tạo vector 32 chiều, với thành phần gán với node t T với i từ đến 31 bit thứ i t V[i] = V[i] + t.num_node không V[i] = V[i] – t.num_node #Tạo số H từ V sau: với i từ đến 31 V[i] >= bit thứ i H gán không bit thứ i H gán T.fingerprint = H XOR hash(T.tag_name) Bảng 7: Hàm tính dấu vân tay node - 50 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 Giải thuật – findProductRegions: tìm tương tự (hoặc vùng vùng sản phẩm) Đầu vào: node T DOM HTML Đầu ra: tất có cấu trúc tương tự gốc T check = False với node t T R R t depth > h R R t ≠ t t depth > h diff(t Simhash, t Simhash) < n R R R R R R R R R R productRegionSet.add(t ) R R productRegionSet.add(t ) R R check = True check = False với node t T t.depth > h findProductRegions(t, productRegionSet) Bảng 8: Hàm tìm có cấu trúc tương tự DOM (biểu diễn vùng có khả vùng sản phẩm) Đầu vào hàm findProductRegions node T' đầu tập con, productRegionSet, gốc T mà thoả mãn điều kiện Đây hàm đệ qui, có trường hợp kết thúc kích thước T nhỏ (độ sâu nhỏ h) node T vùng sản phẩm 3.2 Loại bỏ nhiễu Từ định miêu tả phần 2.4, có hàm kiểm tra sau Hàm - 51 - Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 nhận vùng (một đoạn mã nguồn HTML) làm tham số đầu vào, trả True vùng sản phẩm, False Hàm lọc đơn giản so với hàm lọc hệ thống PEWeb Hàm cần tối đa phép so sánh để xác định vùng sản phẩm Trong đó, hệ thống PEWeb, vùng phải kiểm tra qua 30 biểu thức điều kiện, với phép so sánh biểu thức Điều làm ảnh hưởng không nhỏ tới tốc độ PEWeb áp dụng vào tập liệu lớn Giải thuật – isProductRegion : kiểm tra vùng có phải vùng sản phẩm hay không Đầu vào: vùng trang web Đầu ra: True vùng sản phẩm, False nếu R.nUnits = R.nDigits > 29 R.nImages = trả False không trả True không trả False không R.nImages = trả False không trả True Bảng 9: Hàm kiểm tra vùng có phải vùng sản phẩm hay khơng Chương trình bóc tách thơng tin sản phẩm Dưới số hình ảnh giao diện chương trình bóc tách thơng tin sản phẩm sử dụng kỹ thuật Simhash - 52 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 Hình 16: Giao diện chương trình bóc tách thơng tin sản phẩm - 53 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 Hình 17: Sau nhập đường link trang web bán hàng, chương tình tiến hành phần tích cấu trúc trang web xây dựng DOM tương ứng - 54 - Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 Hình 18: Kết sau tìm bóc tách thông tin từ vùng chứa thông tin sản phẩm Các kết thực nghiệm Trong phần này, chúng tơi trình bày kết thử nghiệm hệ thống sử dụng kỹ thuật đề xuất Đồng thời so sánh hệ thống với hệ thống PEWeb sử dụng kỹ thuật tính tốn entropy a) Dữ liệu Dữ liệu thử nghiệm tập trang web chọn từ website thương mại tiếng Việt Nam Những website thuộc nhiều mặt hàng khác nhau, máy tính, điện thoại di động thiết bị khác Mỗi website thường có vài khn mẫu chúng tơi chọn hai trang web cho khn mẫu, thử nghiệm trang web có cách trình bày kết đem lại - 55 - Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 b) Tham số: Trong hệ thống chúng tơi, có hai tham số quan trọng: ngưỡng khác n độ sâu tối thiếu h Việc gán giá trị cho n có tính quan trọng lớn tới hiệu suất hệ thống chúng tôi, n q lớn, có nhiều kết nhiễu trình tìm kiếm, n q nhỏ, bỏ sót kết Sau thử giá trị khác n trang web, chọn n Tham số h gán Trong hệ thống PEWeb, có tham số: ngưỡng sâu tối thiểu (DTh), ngưỡng tỉ số entropy tối thiểu (ERTh), ngưỡng điểm tối thiểu (STh) Giá trị mặc định tham số 3, 0.90, 15 Trong thử nghiệm chúng tôi, giá trị mặc định giữ nguyên cho tham số c) Kết thực nghiệm Kết thực nghiệm liệt kê bảng 10 Cột thứ hai URL website Cột thứ ba biểu thị tổng số sản phẩm trang mẫu website tương ứng Hai cột sau kết đầu hệ thống sử dụng Simhash cho trang web, : cột tổng số sản phẩm tìm hệ thống, cột thứ hai tổng số kết Hai cột cuối biểu diễn kết tương tự hệ thống PEWeb Ở bảng, ta tính tổng số liệu thống kê Sau đó, ta tính hai tỉ số recall precision cho hai hệ thống với website d) Kết luận Có thể dễ dàng thấy từ bảng 10 hệ thống vượt hệ thống PEWeb độ xác tính đầy đủ Tỉ số recall hệ thống, 98.2 %, cao hệ thống PEWeb, 88.5%, chứng tỏ kỹ thuật sử dụng Simhash hiệu kỹ thuật sử dụng tính tốn entropy PEWeb việc tìm tương tự Điều hiệu suất PEWeb phụ thuộc nhiều vào ngưỡng tỉ số, tham số thiết lập với website, khó để chọn tham số hợp lý Tỉ số precision (99.8%) đồng thời cao tỉ số PEWeb (93.1%) kỹ thuật lọc kết giai đoạn hiệu kỹ thuật lọc PEWeb Điều dễ hiểu phương pháp lọc (sử dụng định) tập trung vào thuộc tính tiêu biểu vùng sản phẩm (như - 56 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 số lượng ký hiệu tiền tệ, ảnh, …), có nhiều thuộc tính PEWeb thừa, khơng có nhiều ý nghĩa Tuy nhiên, lưu ý vài website, kết hai hệ thống thấp, website sử dụng script để sinh mã HTML,như http://vatgia.com/, U T T U http://www.dienmaycholon.vn/, http://laptopcaocap.com/ Để có tồn mã HTML, cần script engine để biên dịch chạy script Tính nằm phạm vi đồ án này, xem xét để phát triển thêm hệ thống sau Cuối cùng, hệ thống tập trung vào website thương mại Việt Nam, chúng tơi mở rộng để xử lý với website nước ngoài, đơn giản cách mở rộng tập học trình lọc để bao hàm website Website Số Simhash PEWeb lượng Số Số Số Số sản lượng lượng lượng lượng phẩm kết kết kết kết quả xác xác http://www.phucanh.vn/ 39 39 39 21 21 http://trananh.com/ 94 94 94 82 82 http://vatgia.com/ 78 66 66 42 40 http://thegioididong.com/ 274 253 253 273 273 http://dienthoaididong.com.vn/ 132 126 126 129 126 http://www.dienmaycholon.vn/ 39 29 29 32 11 http://picoplaza.com.vn/ 88 70 66 74 68 - 57 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 http://www.mediamart.vn/ 57 15 15 49 49 http://www.bestcarings.com.vn/ 32 32 32 32 32 http://www.thegioidientu.com/ 252 248 248 226 226 http://www.goldtime.com.vn/ 16 16 16 25 http://www.phatdatmobile.com/ 37 37 37 58 35 http://www.laptopprocom.com/ 92 92 92 115 91 http://laptopcaocap.com/ 115 104 104 127 115 http://www.maytinhxachtay.com/ 40 38 38 40 40 http://laptopgiatot.com/ 33 30 30 33 33 http://www.giagoc.com.vn/ 36 36 36 46 36 http://www.thegioiblackberry.vn/ 151 151 151 150 150 http://www.laptopshop.vn/ 161 161 161 121 120 http://nama.com.vn/ 49 46 46 51 40 http://www.trungvietlaptop.com/ 21 20 20 21 21 http://namphongpc.com/ 78 78 78 77 76 http:/www.123mua.vn/ 30 30 30 30 30 http://www.dienthoai.com.vn/ 104 104 104 94 92 Tổng số 2048 2015 2011 1948 1813 Precision 99.8% 93.1% Recall 98.2% 88.5% Bảng 10: Kết thực nghiệm hai hệ thống Kết luận hướng phát triển Trong đồ án này, đề xuất kỹ thuật đơn giản hiệu để xác - 58 - Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 định vùng có chứa thơng tin sản phẩm từ trang web thương mại cách tự động Kỹ thuật sử dụng hàm băm đặc biệt, gọi Simhash, để xác định vùng có khả chứa thơng tin sản phẩm định để lọc bỏ kết sai bước Sử dụng Simhash đặc biệt thích hợp hiệu để tìm mà có cấu trúc tương tự DOM trang web: thời gian sinh so sánh dấu vân tay Simhash với ngắn Việc sử dụng định để loại bỏ kết sai bước lọc thứ hai làm tăng chất lượng trình Các kết thực nghiệm chứng minh hiệu hệ thống hẳn so với PEWeb, hệ thống xác định vùng sản phẩm có trước Trong tương lai, tiếp tục nghiên cứu vấn đề bóc tách thơng tin sản phẩm từ trang web Bước sau xác định vùng sản phẩm xác định lấy nội dung trường từ vùng lấy được, tiêu đề, ảnh, giá trường thơng tin liên quan khác Ta thực sử dụng vài đặc tính đặc biệt website thương mại liên quan đến ngữ nghĩa, từ vựng thẻ HTML… Ngoài ra, chúng tơi mở rộng hệ thống cho tự động xác định website thương mại từ website khác Điều làm tăng mức độ tự động hệ thống chúng tôi, điều quan trọng xử lý với tập liệu lớn Internet - 59 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 TÀI LIỆU THAM KHẢO Adelberg, B 1998 NoDoSe: A tool for Semi-Automatically Extracting Structured and Semi-Structured Data from Text Documents SIGMOD Record 27,2, 283-294 Andrew Carlson and Charles Schafer, 2008, Bootstrapping Information Extraction from Semi-structured Web Pages, ECML/PKDD Arocena, G O., and Mendelzon, A O 1998 WebOQL: Restructuring Documents, Databases and Webs In Proceedings of the 14th IEEE International Conference of Data Engineering (Orlando, Florida), pp 24-33 Bing, L., Robert, G and Yanhong, Z 2003 Mining data records in web pages Proceedings of ACM SIGKDD Butter, D., Liu, L and Pu, C 2001 A fully automated extraction system for the world wide web Proceedings of IEEE ICDCS-21 Califf, M and Mooney, R J 1993 Relational learning for pattern match rules for information extraction Proceedings of the Sixteenth National Conference on Artificial Intelligence, pages 328-334 Chang, C.-H and Lui, S.-L 2001 Iepad: Information extraction based on pattern discovery Proceedings of WWW-10 Charikar, M 2002 Similarity estimation techniques from rounding algorithms In Proc 34th Annual Symposium on Theory of Computing (STOC 2002), pages 380388 Cohen W., Hurst M., Jensen L S., 2002, A Flexible Learning System for Wrapping Tables and Lists in Html Documents, In Proc Of the 11 th Intl World Wide Web Conf (WWW'02), pp 232-241 10 Crescenzi, V., Mecca, G and Merialdo, P 2001 Roadrunner: Towards automatic data extraction from large web sites Proceedings of the 26th VLDB, pages 109-118 11 Crescenzi, V., and Mecca, G 1998 Grammars have exceptions Information Systems 23, 8, 539-565 12 Elwin Chai, Rick Jones, 2001, Automated Price Comparison Shopping Search Engine – Price Hunter, CSE 13 Embley, D W., Campbell, D M., Jiang, Y S., Liddle, S W., Ng, Y K., Quass, D and Smith, R D 1999 Conceptual-model-based data extraction from multiplerecord web pages Data and Knowledge Engineering, 31(3);227-251 14 Freitag, D 2000 Machine learning for information extraction in informal domains Machine Learning, 39(2-3):169-202 - 60 - Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 15 Hammer, J., McHugh, J and Garcia-Molina, H 1997 Semistructured data: the TSIMMIS Experience In Proceedings of the First East-European Symposium on Andvances in Databases and Information Systems, St Petersburg, Russia, pp 1-8 16 Hsu, C.-N and Dung, M.-T 1998 Generating finite-state transducers for semistructured data extraction from the web Information Systems, 23(8):521-538 17 Jaeyoung Yang, Heekuck Oh, Kyung-Goo Doh and Joongmin Choi A, 2002, Knowledge-Based Information Extraction System for Semi-structured Labeled Documents, Proceedings of the Third International Conference of Intelligent Data Engineering and Automated Learning 18 Kushmerick, N 2000 Wrapper induction: Efficiency and expressive Artificial Intelligence, 118(1-2):15-68 19 Laender, A H F., Ribeiro-Neto, B A., and da Silva, A S 2001 DEByE – Data Extraction by Example Data and Knowledge Engineering 20 Laender, A H F., Ribeiro-Neto, B A., da Silva, A and Teixeira, J 2002 A brief survey of web data extraction tools Sigmod Record, 21(2) 21 Liu, L., Pu, C and Han, W 2000 Xwrap: An xml-enable wrapper construction system for web information sources Proceedings of the 16th IEEE International Conference on Data Engineering, pages 611-612 22 Manku, G S., Jain, A and Sarma, A D 2007 Detecting near-duplicates for web crawling In Proceedings of the 16th International Conference on World Wide Web, pp 141-150 Banff, Alberta, Canada 23 Muslea, I., Minton, S and Knoblock, C A Hierarchical wrapper induction for semistructured information sources Autonomous Agents and Multi-agent 4(12):93-114, 2001 24 Ribeiro-Neto, B A., Laender, A H F., and da Silva, A S 1999 Extracting SemiStructured Data Through Examples In Proceedings of Eighth ACM International Conference on Information and Knowledge Management (Kansas City, Missouri), pp 94-101 25 Robert Bo Doorenbos, Oren Etzioni, and Daniel So Weld, 1997, A Scalable Comparison Shopping Agent for the World Wide Web, www.cs.washington.edu/etzioni/papers/agents97.pdf 26 Sahuguet, A and Azavant, F 2001 Buiding intelligent web applications using lightweight wrappers Data and Knowledge Engineering, 36(3):283-272 27 Sahuguet, A., and Azavant, F Building intelligent web applications using lightweight wrappers Data and Knowledge Engineering 36, 3, 283-316 - 61 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 28 Sergey Brin, 1998, Extracting Patterns and Relations from the World Wide Web, WebDB Workshop at 6th International Conference on Extending Database Technology 29 S Debnath, P Mitra, N Pal, and C L Giles, 2005, Automatic Identification of Informative, IEEE Trans, Knowl, Data Eng 17 30 S Debnath, P.Mitra, and C L Giles, 2005, Automatic extraction of informative blocks from webpages, In Proc SAC, pages 1722-1726 31 Soderlan, S 1999 Learning information extraction rules for semistructured and free text Machine Learning, 34(1-3):233-272 32 Phan, X.H., Horiguchi, S and Ho, T.B 2004 PEWeb: product extraction from the web based on entropy estimation The IEEE/WIC/ACM Conf on Web Intelligence, IEEE Computer Society 20-24, Beijing, China, pp.590-593 DOI= http://dx.doi.org/10.1109/WI.2004.114 33 WEKA Data Mining with Open Source Machine Learning Software in Java http://www.cs.waikato.ac.nz/ml/weka/ P P - 62 - ... cấu trúc trang sản phẩm, liệu chứa tên sản phẩm, giá sản phẩm thông tin chi tiết sản phẩm Các thông tin ứng với - 10 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn... tả sản - 36 - Tự động trích xuất thông tin sản phẩm Web ứng dụng kỹ thuật Simhash Phạm Nguyễn Tuấn Anh – Cao học CNTT 2009 phẩm hay khơng Giải thuật – PEWeb : Trích xuất thông tin sản phẩm từ Web. .. dụng so sánh giá sản phẩm mà họ muốn mua Hệ thống phải duyệt qua trang web kinh doanh sản phẩm để trích xuất thơng tin hữu dụng sản phẩm - 15 - Tự động trích xuất thơng tin sản phẩm Web ứng dụng