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ủa trang web bằng cách dựa vào phát biểu Heuristic sau: “ Với mỗi node trong mảng ContentNode, nếu tỷ trọng của node đó càng cao thì khả năng node đó chứa nội dung chính của trang web càng lớn ” Dựa vào đây, ta sẽ tập trung chuyển sang tiến hành lọc ra các node nội dung quan trọng bằng cách thực hiện gom nhóm trên lược đồ. 1.8.2 Mịn hóa Histogram Trước khi tiến hành thực hiện kỹ thuật gom nhóm, chúng ta sẽ tiến hành tiền xử lý để mịn hóa bằng kỹ thuật lọc trung bình 2 trên lược đồ histogram. Việc xử lý này sẽ giúp cho ta tránh được việc mất mát các node quan trọng như là các node chứa các nội dung tiêu đề, các nội dung ngắn cần thiết,… có thể bị mất trong quá trình gom cụm, giúp tăng tính liền mạch của các node và cũng giúp ta loại bỏ được các node thật sự chứa nội dung dư thừa không cần thiết do cách xa vùng nội dung chính ngay từ đầu. Nói cách khác, nó giúp khử bớt nhiễu và nâng cao chất lượng của histogram. Lấy ví dụ trang web vnexpress.net trong hình 2-9 ở trên, ta thấy rằng câu tựa đề và một vài câu bên trong nội dung chính khá ngắn, nếu không tiến hành mịn hóa để cân đối lại tỷ trọng của node chứa các câu này thì khả năng mất nội dung của các câu này khi thực hiện gom cụm theo tiêu chí Heuristic trên là khá cao. + Sử dụng lọc trung bình (mean filter): Chúng ta sẽ sử dụng lọc trung bình để mịn hóa lược đồ histogram trên. Với mỗi phần tử trong histogram, ta sẽ tiến hành tính toán và cập nhật lại giá trị (tỷ trọng) của nó bằng cách dựa vào giá trị trung bình của các phần tử lân cận. 2 Các phương pháp lọc ảnh để khử nhiễu: 40 Hình 0-11: Thuật toán lọc trung bình Cụ thể ở đây, mỗi phần tử trong lược đồ sẽ được cập nhật lại bằng giá trị trung bình của r phần tử lân cận hai bên. Tính theo công thức sau: 12 )( += ∑ += −= r irayTEXTNodeAr e rki rki k (0.1) Vớ ek là phần tử thứ k trong mảng TEXTNodeArray. Ở trong khuôn khổ luận văn nầy, ta sẽ chọn bán kính r = 2. 41 Sau khi thực hiện mịn hóa histogram trên bằng lọc trung bình, ta thu được kết quả như sau: VnExpress.net Smooth Histogram 0 50 100 150 200 250 300 350 400 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-12: Lược đồ sau khi đã xử lý lọc trung bình 42 So sánh lại với lược đồ ban đầu: Hình 0-13: So sánh lược đồ trước (a) và sau khi (b) mịn hóa bằng lọc trung bình Ngưỡng trung bình là giá trị trung bình của tất cả các phần tử trong histogram. Ngưỡng trung bình được thể hiện bằng đường ngang màu đỏ trong các lược đồ histogram trên. Kết quả ban đầu (Hình 2-13a) có ngưỡng trung bình tính được là 26.6 và kết quả sau khi mịn hóa (Hình 2-13b) có ngưỡng trung bình tính được là 26.4. Kết quả mịn hóa cho thấy histogram trong hình 2-13b được đều và mịn hơn. Các phần tử có tỷ trọng thấp rải rác từ vị trí thứ 89 trở đi được mịn xuống thấp hơn so với đường VnExpress.net Smooth Histogram 0 50 100 150 200 250 300 350 400 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 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 ( a ) ( b ) 43 ngưỡng trung bình và các phần tử từ vị trí 23 đến 67 thì được làm cao và nổi bật hơn so với hình 2-13a. Điều nầy làm cho chúng ta dễ dàng loại bỏ các nội dung thừa (chính là các phần tử nằm dưới ngưỡng trung bình) và tập trung vào các phần tử nằm trên đường trung bình, là các phần tử có khả năng chứa nội dung chính của trang web cao nhất. Vì thế, chúng ta sẽ loại bỏ các node nằm dưới đường trung bình bằng cách thiết lập lại tỷ trọng bằng 0 cho các node này. 1.8.3 Gom nhóm trên Histogram Sau khi tiến hành tiền xử lý mịn hóa histogram bằng lọc trung bình và lọc bỏ các phần tử thừa thãi nằm dưới ngưỡng trung bình, ta tiếp tục áp dụng kỹ thuật gom cụm (clustering) các phần tử trên lược đồ để lấy ra cụm có tỷ trọng cao nhất. Do chúng ta nhận thấy trong hình lược đồ rằng các phần tử có xác suất là nội dung chính nằm khá gần bên nhau nên ta sẽ sử dụng thuật toán gom cụm K-means3 với mong muốn gom chúng lại thành chung một cụm để có thể tách chúng ra được sau này. Thuật toán gom cụm K-means là thuật toán phải xác định trước số cụm. Vậy ta phải chọn số cụm như thế nào để có thể phân đoạn lược đồ chính xác nhất? Chú ý rằng các trang web khác nhau sẽ có bố cục khác nhau nên lược đồ biểu diễn của chúng cũng phân bố khác nhau. Nhưng ta để ý rằng tuy các trang web có các bố cục khác nhau nhưng nhìn chung chúng thường được phân chia thành ba phần chính (phần chứa thông tin giới thiệu, phần chứa nội dung chính, và phần chứa các nội dung bên lề, các quảng cáo). Do đó ta ước đoán rằng nên chọn số cụm là 3. Ta cũng có thể chọn số cụm là 2, 4,… nhưng kết quả thử nghiệm ở phần sau sẽ cho thấy chọn 3 là tốt nhất. Ta sẽ so sánh các cách chọn này ở phần thử nghiệm ở mục sau. 3 44 VnExpress.net Smooth Histogram 0 50 100 150 200 250 300 350 400 0 50 100 150 200 250 300 350 400 450 Node's Number N od e' s W ei gh t Hình 0-14: Lược đồ nhìn lại dưới dạng điểm. Phân đoạn trang web bằng cách gom nhóm các node có tỷ trọng trội gần nhau. Trong hình là 3 cụm được thể hiện bằng 3 màu khác nhau. Kế tiếp, xem mỗi phần tử trước khi làm đầu vào cho K-means có các thuộc tính lần lượt là (x, y), với x là giá trị thứ tự của node, y là giá trị tỷ trọng của node. Với các n phần tử (x, y) trên, ta dễ dàng sử dụng K-means để gom chúng thành 3 cụm (với khoảng cách sử dụng trong K-means là khoảng cách Euclide). Sau đó xác định cụm có tỷ trọng cao bằng cách tính giá trị trung bình của từng cụm, lấy cụm có giá trị trung bình cao nhất. Đây cũng chính là cụm chứa nội dung chính cần tìm của trang web. Kết quả cuối cùng ta có được một cụm trong đó chứa nhiều Content node. Từ các node này ta ánh xạ ngược lại để lấy ra được nội dung văn bản. Sau cùng khử các mã HTML còn sót lại (nếu có, do InlineNode) để lấy được kết quả hoàn chỉnh. 45 1.9 Kết quả thử nghiệm Để kiểm định tính chính xác của mô hình, chúng ta tiến hành tải về máy tính 50 trang web đầu tiên được lấy từ Google khi tìm kiếm với từ khóa “thông tin”. Hơn nữa, chúng ta cũng thêm vào tập dữ liệu 7 trang web tin tức tiếng Việt thông dụng khác. Mục tiêu của thí nghiệm này là kiểm chứng xem mô hình đề xuất có bóc tách nội dung chính của các trang web và lọc bỏ các nội dung thừa, nội dung rác như các mục quảng cáo, các liên kết… một cách đúng đắn hay không và cũng thử so sánh kết quả với các phương pháp khác. Với mỗi trang web được tải về này, chúng ta sẽ loại bỏ bớt một số trang có đặc tính không phù hợp do có nội dung không rõ ràng, nội dung ít, hoặc quá đơn giản v.v… Tiếp đến, ta sẽ mở từng trang web để xem trong trình duyệt, tự xác định và chọn ra phần nội dung chính bằng tay. Phần nội dung đã chọn ra này sẽ được lưu vào một tập tin riêng dùng để sau này so sánh lại với kết quả của mô hình. Để thẩm định tính đúng đắn của mô hình này, ta tiến hành kiểm thử với hai độ đo là: độ chính xác (precision) và độ bao phủ (recall). Trong khuôn khổ của vấn đề này, các độ đo trên được định nghĩa như sau: + Độ chính xác: được tính là tỷ lệ phần trăm số ký tự đúng mà mô hình rút trích được so với tổng số ký tự mà mô hình rút trích được. Precision = Số ký tự đúng từ mô hình / Tổng số ký tự của mô hình + Độ bao phủ: được tính là tỷ lệ phần trăm số ký tự đúng mà mô hình rút trích được so với số ký tự của nội dung đúng thực tế (do chúng ta tự trích xuất bằng tay). Recall = Số ký tự đúng từ mô hình / Số ký tự của nội dung đúng 46 Với định nghĩa như trên thì “số ký tự đúng mà mô hình rút trích được” sẽ được tính bằng cách đo “chuỗi con chung dài nhất” (LCS - Longest Common Substring)4 [13] giữa kết quả của mô hình với kết quả chọn bằng tay. LCS được xác định bằng cách so sánh chuỗi con chung dài nhất giữa hai tập tin. Trước khi so sánh chúng ta phải loại bỏ tất cả các ký tự xuống hàng, các khoảng trắng dư thừa, để đảm bảo sự so sánh được chính xác vì chỉ cần một khác biệt nhỏ là kết quả so sánh sẽ thay đổi hoàn toàn. Ngoài ra, để ước lượng giá trị trung bình của hai độ đo trên, chúng ta sẽ sử dụng thêm độ đo F1, được định nghĩa như sau 5: recallprecision recallprecisionF ++= . .).1( 2 2 βββ , với 1=β (0.2) Các trang web thử nghiệm cũng như các tập tin chứa kết quả trích xuất bằng tay sẽ được sắp xếp và đặt tên theo một định dạng thích hợp để có thể dễ dàng chạy kiểm thử. Sau khi đã chuẩn bị bộ dữ liệu thí nghiệm đầy đủ, ta thực hiện chạy thí nghiệm bằng cách cho chương trình quét qua tất cả các trang web đã được tải về trong máy tính, tự động bóc tách ra nội dung chính và thực hiện so sánh lại với các kết quả đã được rút trích bằng tay để tính ra được hai độ đo là độ chính xác và độ bao phủ. Để đảm bảo tính đúng đắn, thí nghiệm sẽ được thực hiện với nhiều cách thử khác nhau: có áp dụng và không áp dụng mịn hóa histogram với các số cụm được gom khác nhau. Số cụm được chọn lần lượt là 2, 3 và 4. Kết quả kiểm thử được thể hiện trong bảng 2-2: 4 5 47 Bảng 0-2: Kết quả thử nghiệm bóc tách nội dung chính bằng phân đoạn trang web với các phép thử khác nhau Phương pháp / Độ đo Độ chính xác trung bình (%) Độ bao phủ trung bình (%) Độ đo F1 trung bình (%) Không mịn hóa, gom 2 cụm 45.57 86.52 58.41 Không mịn hóa, gom 3 cụm 45.58 86.51 58.42 Không mịn hóa, gom 4 cụm 45.56 86.52 58.41 Có mịn hóa, gom 2 cụm 69.47 79.94 71.32 Có mịn hóa, gom 3 cụm 74.10 80.32 76.04 Có mịn hóa, gom 4 cụm 75.28 78.60 76.03 Kết quả thí nghiệm cho thấy rằng áp dụng mô hình có mịn hóa histogram với số cụm được gom là 3 cho kết quả tốt nhất. Chọn mô hình tốt nhất này để so sánh với phương pháp Rút trích Text node và Tiếp cận theo hướng phân tích mã HTML và xử lý ngôn ngữ tự nhiên đã đề cập ở phần 2.2, ta được kết quả so sánh trong bảng 2-3. 48 Bảng 0-3: So sánh kết quả với phương pháp khác Phương pháp / Độ đo Độ chính xác trung bình (%) Độ bao phủ trung bình (%) Độ đo F1 trung bình (%) 1. Rút trích Text node 45.58 86.52 58.41 2. Phân tích HTML kết hợp xử lý ngôn ngữ tự nhiên 74.17 80.26 75.05 3. Phương pháp đề xuất 74.10 80.32 76.04 Kết quả đạt được cho thấy rằng áp dụng mô hình trên cho kết quả tương đương với phương pháp 2 (phân tích HTML và kết hợp xử lý ngôn ngữ tự nhiên) và cao hơn hẳn so với phương pháp 1 (rút trích Text node). Về trung bình nó cho kết quả cao nhất (độ đo F1) mặc dù trong một số trường hợp độ chính xác của nó thấp hơn với phương pháp 2, nhưng không đáng kể. Kết quả này có thể chấp nhận được trong khuôn khổ của luận văn nầy. Hệ thống của chúng ta sẽ áp dụng mô hình này để thực hiện bóc tách nội dung chính của trang web. Tiếp đến, sau khi đã bóc tách được nội dung chính của trang web, chúng ta cần phải biết nội dung đó đang nói về vấn đề gì để có thể đưa ra các quảng cáo phù hợp tương ứng. Có nhiều phương pháp để làm được điều nầy. Có thể tiếp cận theo hướng phân loại văn bản. Cũng có thể tiếp cận theo hướng tóm tắt tự động nội dung văn bản. Nhưng có lẽ cách thức phù hợp nhất đối với yêu cầu của hệ thống của chúng ta là rút trích tự động các từ khóa chính của nội dung đó. Chương tiếp theo chúng ta sẽ bàn chi tiết hơn về điều nầy.