Luận văn Xây dựng công cụ quảng cáo theo ngữ cảnh tiếng Việt

21 Phương pháp tự động xác định phần nội dung chính của một trang web bất kỳ 1.6 Tổng quan Để hiểu được trang Web đang nói về vấn đề gì, trước hết phải xác định được nội dung chính của trang Web. Chú ý rằng trang web ở đây được hiểu là trang web bất kỳ, nghĩa là cấu trúc của trang web không được biết trước. Hơn nữa, trang web phải thật sự có nội dung chính (nghĩa là nếu chúng ta nhìn vào sẽ biết đâu là chủ đề của trang web) thì việc xác định này mới thật sự có ý nghĩa. Tại sao cần phải bóc tách nội dung chính? Khối lượng thông tin lưu trữ trên Internet ngày càng tăng chóng mặt theo thời gian. Từ đây đã làm nảy sinh các nhu cầu nghiên cứu, xử lý trên khối lượng dữ liệu thông tin này sao cho hiệu quả và nhanh chóng nhất. Một số ứng dụng như Search Engine, RSS, Feedback, Tóm tắt văn bản, Tìm kiếm song ngữ… rất cần rút trích được các thông tin chính xác, gọn gẽ, có ý nghĩa từ kho dữ liệu trên. Khó khăn của bài toán là không phải toàn bộ nội dung của trang web đều cần thiết. Chúng hay bị “nhiễu” bởi rất nhiều các thông tin khác nhau. Nếu chỉ đơn thuần loại các chuỗi script HTML thì nội dung lọc được sẽ rất nhiều lỗi rác không cần thiết. Ví dụ: phần thông tin quảng cáo, tin mới cập nhật, nội dung tin ngắn, menu... những nội dung như thế này thường cần phải bỏ qua trong quá trình bóc tách nội dung chính của trang web. Cụ thể hơn, nội dung của các các trang web được tổ chức theo dạng dữ liệu HTML với cấu trúc theo dạng tag, node… Những tag này chỉ có ý nghĩa với trình duyệt để hiển thị tài liệu, văn bản theo một bố cục và trình diễn cho trước, và hoàn toàn không có ngữ nghĩa nào đối với người duyệt web. 22 Bên cạnh đó, do tính phong phú của Internet nên nội dung trang web thường chứa nhiều thông tin khác nhau. Bên cạnh các nội dung chính lại thường chứa thêm nhiều nội dung bên lề, không liên quan. Ví dụ như các trang web thường chứa các thanh thực đơn (menu) ngang hoặc dọc, các danh sách đường dẫn (link) dùng để định hướng cho người sử dụng có thể dễ dàng truy xuất tới nội dung mà mình cần. Các quảng cáo dạng banner, các đoạn phim Flash, các hiệu ứng âm thanh, hình ảnh, các định dạng stylesheet (css) , mã kịch bản javascript, cũng như các đoạn văn bản (text) không liên quan khác đã làm cho nội dung web thật sự là một kho dữ liệu khá phức tạp. Hình 0-1: Xác định và bóc tách nội dung chính của trang web Vấn đề: Quá nhiều nhiễu trong trang web. Mục tiêu: Khử nhiễu để lọc ra nội dung chính. 23 Ngoài ra, trên cùng một trang web lại cũng có thể chứa nhiều chủ đề khác nhau. (ví dụ như là rất khó để xác định nội dung chính của trang chủ Yahoo.com!). Do đó, bóc tách khối nội dung chính chỉ có ý nghĩa khi trang web có chứa nội dung thật sự. Một khó khăn nữa là nội dung HTML của các trang web có cú pháp rất “dễ dãi”. Bạn có thể có tag mở, nhưng không có tag đóng, các mã HTML có thể bị khai báo sai cú pháp, chồng chéo lên nhau, vẫn được trình duyệt ưu ái hiển thị bình thường mà không bắt lỗi. Tất cả các vấn đề trên đã làm cho nội dung web bị “nhiễu” khá nhiều, đặt ra một thách thức không nhỏ trong việc định dạng nội dung chính của nó. 1.7 Một số nghiên cứu gần đây Để xác định được khối nội dung chính của một trang web bất kỳ, không biết trước cấu trúc, hiện nay đã có nhiều cách tiếp cận khác nhau: 1.7.1 Tiếp cận theo hướng loại bỏ các tag HTML Đây là cách tiếp cận đơn giản nhất, và dĩ nhiên hiệu quả cũng thấp nhất. Sử dụng biểu thức chính quy (regular expression) sau để loại bỏ các tag HTML: Regular Expression = “ ]*>" ”. Do như đã trình bày ở trên, nội dung web không chỉ là các tag HTML mà còn chứa các nội dung rác khác. Vì thế cách này chỉ có thể áp dụng được cho các đoạn HTML nhỏ và riêng lẻ, không thể áp dụng cho toàn bộ trang web. 24 Hình 0-2: Tách nội dung web bằng loại bỏ tag HTML 1.7.2 Tiếp cận theo hướng rút trích các Text node Phương pháp này cũng tương tự phương pháp loại bỏ các tag HTML nhưng tiếp cận theo hướng khác. Bằng cách thực hiện phân tích mã HTML để tạo thành cây biểu diễn nội dung trang web Document tree (DOM)1, trong đó các node của cây đại diện cho các thành phần khác nhau trong trang web. Khi đó, phần văn bản chính sẽ được lấy ra bằng việc nối nội dung các node được đánh dấu với tag là “TEXT”. Tiếp cận theo phương pháp này có thể áp dụng cho toàn bộ trang web và cho kết quả chính xác hơn so với phương pháp loại bỏ các tag HTML. Nhưng vẫn không thể khắc 1 Document Object Model (DOM): mô hình đối tượng tài liệu, có dạng một cây cấu trúc dữ liệu, được dùng để truy xuất các tài liệu dạng HTML và XML. RSS Thứ bảy, 18/4/2009, 15:24 GMT+7 Email Bản In Trang nhất Xã hội Thế giới Kinh doanh Văn hóa Thể Thao Pháp luật Đời sống Khoa học Vi tính Ô tô Rao vặt Cười BẠN ĐỌC VIẾT /> VnExpress - Chứng khoán thăng hoa một cách khó hiểu - Chung khoan thang hoa mot cach kho hieu var PAGE_SITE=0; var PAGE_FOLDER=139; var PAGE_ID=1000399507; var DOMESTIC_IP=1; setTypingMode(1); sLoDID=sLoDID.concat('1000399507').con cat(','); checkCookie(); ShowTopBanner(); Hiện tượng bùng nổ của thị trường chứng khoán thời gian qua thật khó tưởng. Theo cách nhìn nhận của cá nhân tôi thì nền kinh 25 phục nhược điểm là không thể lọc nội dung rác để lấy phần nội dung chính mà chỉ đơn thuần là lấy toàn bộ văn bản text của trang web. 1.7.3 Tiếp cận theo hướng so sánh khung mẫu Phương pháp rút trích thông tin bằng cách so trùng hai trang web được xây dựng trên nền tảng nhận dạng mẫu được tác giả Trang Nhật Quang thực hiện trong việc rút trích nội dung nhằm cung cấp tin tức trên trang web hành chính. Phương pháp này cho phép so khớp trang web cần rút trích với một trang web mẫu để xác định khung trình bày chung cho cả hai trang web cần rút trích, từ đó đi đến rút trích ra nội dung nằm trong phần được xác định chứa nội dung chính trên trang mẫu. (a) (b) (c) Hình 0-3: Mô hình bóc tách nội dung chính bằng so sánh khung mẫu (a) Trang web cần rút nội dung chính (b) Trang web khung mẫu (được xác định trước) (c) Nội dung chính sau khi so khớp và rút được Phương pháp này không đòi hỏi người sử dụng phải biết về ngôn ngữ xây dựng hoặc phải chỉ ra khu vực nội dung cần bóc tách khi cách trình bày thay đổi do trang 26 web mẫu có thể lấy trực tiếp từ trang chủ và có cùng cách trình bày với trang cần rút trích. Tuy nhiên, đối với mỗi tên miền khác nhau, cần phải xác định được một trang web làm mẫu cho những trang khác. Đây cũng là một hạn chế trong quá trình tự động hóa xác định nội dung chính của web. 1.7.4 Tiếp cận theo hướng phân tích mã HTML và xử lý ngôn ngữ tự nhiên Giải pháp thực hiện này được tác giả Ngô Quốc Hưng phát triển trong luận án “Tìm kiếm tự động văn bản song ngữ Anh-Việt từ Internet” [21]. Hướng tiếp cận này dựa trên phương pháp bóc tách nội dung nhờ vào phân tích mã HTML theo các bộ mã nguồn HTMLParser của dự án Majestic-12 để tạo thành cây DOM biểu diễn nội dung trang web. Từ đó áp dụng các công cụ và kỹ thuật ngôn ngữ để quyết định phần nội dung chính. Phương pháp này dựa trên tiền đề là trang web đã được phân tích các tag HTML để xây dựng nên cây Document Tree. Từ cây này chúng ta đi xác định node nào ở trên cây chứa nội dung chính của trang WEB. Phương pháp cho điểm các node dựa vào kết quả xử lý ngôn ngữ tự nhiên trên nội dung mà nó chứa bên trong đó. Một số quy tắc cho điểm được áp dụng: + Chỉ cho điểm cho những NODE có tag là TEXT. Vì chỉ có những node này mới là node chứa nội dung thực sự. Các node khác tổng hợp từ node này. + Cho điểm NODE TEXT dựa vào số câu của nội dung chứa bên trong node đó. Càng nhiều câu thì node có điểm càng cao. + Node được cho điểm phải chứa tối thiểu một đoạn văn. (Tuy nhiên việc xác định như thế nào là một đoạn văn vẫn chỉ là một heuristic) + Điểm của các node cha sẽ bằng điểm của các node con cộng lại. 27 Hình 0-4: Node chứa nội dung chính trên cây văn bản Xác định node nội dung: Để xác định node nội dung chính mà không chứa các nội dung không cần thiết chính là đi xác định node sâu nhất trên cây có điểm cao nhất. Bằng việc xác định node nội dung như vậy, hệ thống có thể tự động xác định nội dung trang web mà không cần biết trước khung mẫu cũng như nguồn gốc của trang web đó. Hướng tiếp cận này cho kết quả rất khả quan, tuy nhiên cách này có thể bị bỏ sót nội dung nếu nội dung chính được nằm phân tán trên các node độc lập khác nhau trong cây Document Tree. 28 1.7.5 Tiếp cận theo hướng phân đoạn trang web Hướng tiếp cận này tiến hành phân đoạn trang web thành các khối (block) riêng biệt theo cách tiếp cận trực quan (vision-based approach), nghĩa là mắt người cảm nhận thấy ra sao thì sẽ phân đoạn như vậy. Bằng cách sử dụng giải thuật VIPS (Vision- based Page Segmentation) [5] được phát triển bởi phòng thí nghiệm của Microsoft. Ý tưởng chính là dựa trên độ liền mạch của các node trong cấu trúc cây DOM với một số nhận xét heuristic để thực hiện phân đoạn tự động trang web theo khu vực một cách trực quan. Hình 0-5: Thuật toán VIPS, phân đoạn trang web dựa trên cấu trúc cây DOM Thuật toán VIPS sơ lược gồm 3 bước chính: o Bước 1: Tách các khối chính (Block Extraction) + Tiến hành phân tách các node của cây DOM ra thành các khối lớn bằng cách: lần lượt chia tách các node chứa đựng (container node - là node có khả năng chứa các node khác, ví dụ như node có tag là , ,…) cho đến khi không còn các container node nào. Từ đó xây dựng được cây chỉ bao gồm các container node trên, gọi là cây Visual Block 1 (VB1), biểu diễn các khối chính của trang web. 29 + Từ cây VB1 này, ta tiến hành xem xét xem các node nào trong cây nên bị chia tách tiếp hay không bằng một số luật Heuristic như sau: ƒ Dựa vào tag: những tag ví dụ như , … thường dùng để chia tách các chủ đề khác nhau, do đó nếu node là những tag này thì tiến hành chia tách tiếp. ƒ Dựa vào màu sắc (color): giả sử như nếu màu nền của node cha khác với một trong các node con của nó thì tiến hành chia tách tiếp vì nếu màu sắc khác nhau thì thường thể hiện nội dung của các chủ đề khác nhau. ƒ Dựa vào văn bản (text): nếu node là text node thì không chia tách tiếp. ƒ Dựa vào kích thước (size): Nếu độ sai biệt về kích thước của node cha và các node con lớn hơn một ngưỡng cho trước thì tiến hành chia tách node đó tiếp. + Tới đây, ta thu được cây mới, tạm gọi là cây VB2. o Bước 2: Xác định các đường phân cách (Seperator Detection) + Các block trong cây VB2 được đưa vào một pool để xác định ranh giới phân tách (seperator). Các đường phân tách được định nghĩa như đường ngang hoặc dọc trong trang web mà không chứa block nào trong pool. + Từ đó xác định tiếp trọng số của các seperator. Các trọng số này sẽ được xác định dựa vào các tiêu chí Heuristic sau: ƒ Khoảng cách: trọng số sẽ càng cao nếu khoảng cách, khoảng trống xung quanh Seperator càng nhiều. 30 ƒ Tag: Nếu Seperator nằm cùng vị trí với các tag dạng phân cách (ví dụ như …) thì trọng số sẽ càng cao. ƒ Font: Nếu font chữ, kích thước chữ (font,size) của các khối xung quanh Seperator càng khác nhau thì trọng số Seperator đó sẽ càng cao. ƒ Color: Nếu màu nền (background color) xung quanh Seperator càng khác nhau thì trọng số của Seperator càng cao. + Từ đây, ta xác định được các Seperator trên trang web cùng với trọng số của chúng. o Bước 3: Tổng hợp cấu trúc nội dung (Content Structure Construction) + Khi các Seperator đã được xác định, ta tiến hành bỏ đi các Seperator có trọng lượng thấp bằng cách gom (merge) các block nằm hai phía của Seperator này lại với nhau. + Quá trình gom block này sẽ được thực hiện cho đến khi gặp được Seperator có trọng lượng lớn nhất. Tiếp tục xác định độ đo liền mạch (DoC) của block vừa gom được. + Sau đó mỗi block sẽ được kiểm tra xem độ đo DoC của nó có lớn hơn ngưỡng cho trước hay không? Nếu thõa yêu cầu ngưỡng thì dừng, nếu chưa thì tiếp tục quay lại Bước 1 để tiếp tục tách block. Sau khi chạy thuật giải VIPS, trang Web sẽ được phân đoạn thành các khối riêng biệt. Ta tiếp tục tiến hành xác định khối nào là khối chứa nội dung chính của trang Web bằng cách xét độ quan trọng từng khối trong trang Web [6]. 31 Hình 0-6: Ước lượng độ quan trọng của từng khối phân đoạn Độ quan trọng của mỗi khối có thể được xác định bằng cách sử dụng một số độ đo heuristic để xác định dựa vào các đặc trưng của khối: như tần suất xuất hiện các liên kết (link) trong khối, chiều dài của đoạn văn bản trong khối, màu nền, màu chữ của các đoạn văn bản, kích thước của khối. Bên cạnh đó, có thể tiếp cận xây dựng một mô hình học có giám sát bằng mạng Neuron với đầu vào là các đặc trưng trên để xác định khối nội dung chính [6]. Đây là cách tiếp cận mạnh và hiệu quả nhất, tuy nhiên rất phức tạp và khó khăn trong cài đặt trên thực tế nếu đầu vào chỉ là những mã văn bản HTML mà không có sự hỗ trợ đặc biệt của trình duyệt. 32 1.8 Mô hình đề xuất của luận văn Luận văn sẽ tiếp cận vấn đề này theo hướng phân đoạn trang web bằng mô hình lược đồ (histogram). Hướng tiếp cận này sẽ dựa trên phân tích cấu trúc cây Document Tree (DOM) của trang web. Sử dụng bộ mã nguồn HTMLParser của dự án mã nguồn mở HtmlAgilityPack [22] để tạo thành cây Document Tree. Sau khi phân tích được cấu trúc cây DOM của trang web, dựa trên cấu trúc này chúng ta sẽ thực hiện biểu diễn lại nội dung trang web như là một lược đồ histogram bằng cách rút trích ra các Content node. Tiếp đến, chúng ta tiến hành mịn hóa Histogram để loại bỏ các Content node có độ quan trọng thấp và chống bỏ sót các Content node có độ quan trọng cao. Sau cùng, dựa vào nhận xét heuristic rằng “vùng nội dung chính của trang web sẽ là vùng tập trung mật độ văn bản cao nhất”, chúng ta tiến hành gom nhóm trên histogram này để lọc ra được nhóm có giá trị mật độ ngưỡng cao nhất. Đây được xem là nội dung chính của trang web. Hình 0-7: Mô hình bóc tách nội dung chính trang web Biểu diễn bằng lược đồ: + Rút trích cây DOM + Tính trọng số của Text node Tiền xử lý: + Lọc trung bình + Khử bớt nhiễu Phân đoạn trang web: + Gom cụm bằng K-means + Xác định trọng số cụm Html Nội dung chính 33 1.8.1 Biểu diễn nội dung web dưới dạng lược đồ Histogram Trang web của chúng ta, dưới dạng mã HTML, thực chất được các trình duyệt hiểu như là một cấu trúc dạng cây, bao gồm các node cha và con có quan hệ với nhau theo một trình bày nhất định nào đó, được gọi là cây DOM (Document Object Model). Sau khi phân tích được các tag HTML trong trang web để xây dựng nên cây DOM, chúng ta tiến hành duyệt cây DOM để thực hiện các xử lý cần thiết. Đầu tiên, tiến hành xóa bỏ các node không liên quan, không thể nhìn thấy bởi người dùng trên trình duyệt như các node có tag là script, style, remark,.v.v… Sau đó bóc tách ra các node là Text node, vì chỉ có những node này mới là node chứa nội dung văn bản thật sự. Sau đó tổ chức lại các node này dưới dạng mảng các Text node, cùng với tỷ trọng (weight) của chúng. Tỷ trọng của node ở đây được hiểu như là độ đo sự quan trọng của node đó trong trang web, và trong khuôn khổ luận văn này nó được hiểu heuristic như là kích thước của node đó, cụ thể là số ký tự của node đó. Chúng ta có thể tùy ngữ cảnh mà cải thiện độ chính xác của giải thuật bằng cách mô tả chính xác hơn độ đo này bằng cách kết hợp thêm các yếu tố khác, ví dụ như là vị trí của node, định dạng của node, độ liền mạch với các node xung quanh,… Độ đo này càng được thể hiện rõ thì độ chính xác của giải thuật càng cao. 34 Các bước thực hiện được mô tả như trong giải thuật sau: Bảng 0-1: Giải thuật biểu diễn nội dung web dưới dạng lược đồ histogram Để làm rõ hơn giải thuật trên, ta cần hiểu thêm một số định nghĩa về các loại node trong cây DOM. Trong khuôn khổ luận văn này, chúng ta chia các node nầy thành 4 loại chính: InvisibleNode, InlineNode, TextNode, VirtualTextNode. + InvisibleNode: Chính là các node không thể nhìn thấy được bởi người dùng, nó chỉ được hiểu bởi trình duyệt để tô vẽ thêm cho trang web (ví dụ các node có tag là , , ,…). Nó cũng có thể là các node mà chúng ta không cần Input DOM Å mã nguồn HTML Begin Xóa bỏ các InvisibleNode. Với mỗi node trong cây DOM: Nếu (node là VirtualTextNode) thì: TEXTNodeArray[i] Å Weight (node) Nếu không thì TEXTNodeArray[i] Å 0 Return TEXTNodeArray End 35 quan tâm nhiều khi tiến hành bóc tách nội dung (như các node có nội dung rỗng, các node xuống hàng, line break…). + InlineNode: Là node không gây ảnh hưởng gì nhiều đến nội dung của văn bản. Chúng chỉ ảnh hưởng đến định dạng của các chuỗi văn bản mà không gây ra sự xuống hàng hoặc khoảng phân cách nào đáng kể (Ví dụ như các node có tag là , , , , , , , …). + TextNode: Là node có tag là TEXT, chỉ đơn giản chứa văn bản thuần túy, không chứa mã hoặc tag HTML (Ví dụ như “tôi đi học ở KHTN”là một text node). + VirtualTextNode: Là dạng mở rộng của TextNode, nhưng nội dung node có thể chứa các InlineNode. VirtualTextNode được định nghĩa một cách đệ quy như sau: Việc xác định một node là VirtualTextNode rất quan trọng vì nếu xác định không đúng sẽ làm mất mát các node có nội dung ngắn, làm ảnh hưởng đến sự liền mạch của kết quả bóc tách được. Một node được gọi là VirtualTextNode nếu: - Nếu node có các node con đều là InlineNode hoặc TextNode thì là VirtualTextNode - Nếu node có các node con đều là InlineNode hoặc TextNode hoặc VirtualTextNode thì là VirtualTextNode. 36 Ghi chú: Do có cùng ý nghĩa nên để ngắn gọn, từ đây chúng ta sẽ gọi chung VirtualTextNode và TextNode là ContentNode. Hình 0-8: Minh họa một trích đoạn nội dung web và cây DOM của nó với các loại node khác nhau Từ giải thuật này, chúng ta sẽ xây dựng được một mảng các ContentNode chứa nội dung văn bản từ trang web. Từ mảng này, ta sẽ biểu diễn được lược đồ histogram theo tỷ trọng của node. Virtual Text Node Invisible Node Text Node 37 Lấy ví dụ với một trang web tin tức của vnexpress.net đăng ngày 18/8/2009 tại Trang web này tương tự như vô vàn các trang tin khác trên Internet: có tựa đề, banner, hình ảnh, menu, và quảng cáo chiếm hầu hết khoảng trống, còn nội dung chính của nó thì chỉ được giới hạn ngay ở phần giữa của trang. Ở phía cuối trang cũng có các quảng cáo, các liên kết, các nội dung thông tin bản quyền và các thông tin dùng để quản trị khác… Hình 0-9: Trang web vnexpress.net dùng để minh họa việc xác định nội dung chính Khi chúng ta tiến hành phân tích trang web này bằng thuật toán trên, ta sẽ xây dựng được mảng các content node, và thu được lược đồ histogram sau: 38 VnExpress.net Histogram 0 50 100 150 200 250 300 350 400 450 500 1 23 45 67 89 111 133 155 177 199 221 243 265 287 309 331 353 375 397 419 Node's Number N od e' s W ei gh t Hình 0-10: Lược đồ của trang web song/2009/07/3BA119E9/ Ở lược đồ histogram trên: Trục X chính là thứ tự của các node trong mảng (cũng chính là thứ tự của node trên cây DOM). Còn trục Y chính là tỷ trọng của node đó (cụ thể ở đây là chiều dài của node). Phân tích kỹ lược đồ trên, chúng ta nhận thấy rằng vùng có chứa tỷ trọng cao chính là vùng chứa nội dung chính của trang web (vùng chứa các node nằm từ vị trí thứ 23 đến 67 trong hình 2-10 tương ứng với phần nội dung chính trong trang web ở hình 2-9, là phần văn bản chính ở bên trái). Thử nghiệm trên một số trang web khác, ta cũng có nhận xét tương tự như vậy. Vì thế, dựa trên ý tưởng này, ta sẽ tiến hành bóc tách nội dung chính của trang web bằng cách trích xuất nội dung của các node từ 23 đến 67, là vùng tập trung mật độ cao nhất (xem hình 2-10). Tự mình kiểm chứng lại, ta thấy đó thật sự đúng là nội dung chính cần bóc tách của trang web này (các vùng quảng cáo, các menu, các liên kết banner,… đã bị loại bỏ). 39 Do đó, dựa vào đặc điểm này, ta sẽ thực hiện xác định nội dung chính c