Khóa luận Bài toán trích xuất từ khoá cho trang web áp dụng phương pháp phân tích thẻ HTML và đồ thị web

TÓM TẮT NỘI DUNG Trích xuất từ khoá cho trang web là một bài toán mở rộng của bài toán trích xuất từ khoá cho một văn bản. Ở mức cao hơn, nó là một bài toán con trong hệ thống trích xuất thông tin (Information Retrieval). Trong nhiều năm qua, bài toán này đã được đề cập, quan tâm nhiều ở các hội nghị quốc tế và các công ty lớn. Bài toán trích xuất từ khoá cho trang web là việc kết hợp giữa trích xuất từ khóa trong văn bản nội dung trang web và việc khai phá, đánh giá từ khoá dựa trên các đặc trưng, cấu trúc của Web. Đây cũng là vấn đề khá mới mẻ và được áp dụng trong rất nhiều lĩnh vực khác nhau như: quảng cáo trên máy tìm kiếm, phân cụm các trang web, hỗ trợ tìm kiếm, hỗ trợ gợi ý người dùng Trong khoá luận tốt nghiệp này, tác giả đã đề xuất mô hình giải quyết bài toán trên dựa vào các phương pháp: độ quan trọng các thẻ HTML, đồ thị web. Ngoài ra, các phương pháp hỗ trợ là khai phá log và từ điển hỗ trợ cũng được trình bày nhằm nâng cao chất lượng từ khóa. Khóa luận đã áp dụng trên một số miền dữ liệu cụ thể của các trang web tiếng Việt, tiếng Anh và cho kết quả khả quan. 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 iv Danh mục hình vẽ v Danh mục các bảng biểu vi MỞ ĐẦU 1 Chương 1. Giới thiệu bài toán trích xuất từ khoá cho trang web 3 1.1. Đặt vấn đề 3 1.2. Khái niệm và các đặc trưng của từ khóa 4 1.3. Đánh giá các từ khóa 5 1.4. Thách thức của bài toán sinh từ khóa cho trang web 5 1.4.1. Đối với các trang có nội dung tập trung 6 1.4.2. Đối với các trang có nội dung tổng hợp 6 1.4.3. Các vấn đề khác 6 1.5. Ứng dụng của từ khóa trong các lĩnh vực 7 1.5.1. Vai trò từ khóa trong máy tìm kiếm 7 1.5.1.1. Quảng cáo trên máy tìm kiếm 7 1.5.1.2. Hoạt động quảng bá web trong máy tìm kiếm 9 1.5.3. Vai trò từ khóa trong các trang web tổng hợp thông tin 10 1.6. Tổng kết chương 12 Chương 2. Các công trình liên quan 13 2.1. Các phương pháp trích xuất từ khóa cho văn bản 13 2.1.1. Phương pháp tần số từ 13 2.1.2. Phương pháp sử dụng các thông tin khác trong văn bản 14 2.1.3. Phương pháp sử dụng học máy 15 2.1.3.1. Trích xuất từ khóa sử dụng phân lớp Naïve Bayes 16 2.1.3.2. Trích xuất từ khóa sử dụng lexical chain (chuỗi từ vựng) và phân lớp 16 2.2. Các phương pháp trích xuất từ khóa cho trang web 17 2.2.1. Tần số từ 17 2.2.2. Kĩ thuật khai phá log 17 2.2.3. Kĩ thuật áp dụng máy tìm kiếm và độ tương đồng từ 18 2.3. Gán từ khóa trong văn bản, web (keyword assignment) 19 2.4 Tổng kết chương 19 Chương 3. Hướng giải quyết và đề xuất mô hình bài toán 20 3.1. Hướng giải quyết 20 3.1.1. Sử dụng độ quan trọng của các thẻ trong HTML 20 3.1.2. Sử dụng đồ thị web 23 3.1.2.1. Định nghĩa đồ thị Web 23 3.1.2.2 Nội dung của phương pháp 24 3.1.3. Sử dụng query log 26 3.1.4. Sử dụng từ điển hỗ trợ 27 3.2. Đề xuất mô hình bài toán 27 3.2.1. Mô hình toàn hệ thống 27 3.2.2. Mô đun Crawler 28 3.2.3. Mô đun sinh từ khóa 29 3.2.3.1. Mô đun sử dụng trọng số thẻ HTML 30 3.2.3.2. Mô đun sử dụng đồ thị web 32 3.2.3.3. Các phương pháp hỗ trợ 33 3.2.3.4. Mô đun tổng hợp 35 3.3. Tổng kết chương 35 Chương 4. Thực nghiệm và đánh giá 36 4.1. Giới thiệu bài toán thực nghiệm 36 4.2. Môi trường, dữ liệu 36 4.1.1. Môi trường phần cứng 36 4.1.2. Mô tả chương trình 36 4.1.3. Công cụ phần mềm 37 4.1.4. Dữ liệu thử nghiệm 38 4.3. Kết quả thực nghiệm 40 4.4. Đánh giá kết quả thực nghiệm 43 Kết luận 46 Hướng phát triển tiếp theo 47 Tài liệu tham khảo. 48 MỞ ĐẦU Trong những năm gần đây, sự bùng nổ của Internet mà đặc biệt là World Wide Web - còn gọi tắt là Web - làm thông tin ngày càng tràn ngập, đa dạng, có sự trùng lặp nhiều. Cùng với sự tăng trưởng và phổ cập của Internet thì việc quảng cáo trên mạng của các doanh nghiệp cũng tăng cao. Sự ra đời của máy tìm kiếm đã phần nào giải quyết được vấn đề tràn ngập thông tin của các trang web. Các máy tìm kiếm chủ yếu vẫn sử dụng những từ khoá và tìm những trang có chứa từ khoá và cho ra kết quả phù hợp. Việc sử dụng máy tìm kiếm làm công cụ quảng cáo đã nở rộ trong những năm gần đây. Nhưng các trang web có nội dung được nhiều người quan tâm lại trùng lặp về từ khoá nhiều, cho nên các doanh nghiệp muốn quảng cáo trên máy tìm kiếm phải cạnh tranh với các doanh nghiệp khác có từ khóa trùng với nó. Đó chính là một trong các động lực để phát triển bài toán trích xuất từ khoá cho trang web. Nhiệm vụ bài toán đặt ra là cần tìm được một tập các từ khoá sao cho các từ khoá này phải sát với nội dung của trang web. Một động lực khác làm cho bài toán trích xuất từ khóa cho các trang web được sự quan tâm của nhiều người, doanh nghiệp, đó chính là việc phân loại các tài liệu web vào các thư mục phân cấp, việc tìm kiếm trong các thư mục nhờ đó cũng dễ dàng hơn. Rất nhiều các trang web báo khác nhau, các blog như: vietbao.vn, baomoi.com, flickr.com, ebay.com . đã áp dụng việc sinh từ khóa cho các trang này để người đọc, người xem có thể liên hệ, theo dõi dễ dàng đối với các trang báo, hay các sản phẩm khác có liên quan. Các từ khóa giúp nâng cao sự gợi ý cho người dùng. Không những thế, những từ khóa được tìm kiếm nhiều nhất trong một thời điểm phản ánh được phần nào xu hướng của người dùng, giúp người dùng có cái nhìn tổng quan về các vấn đề đang được quan tâm. Một vấn đề quan trọng không kém, đó là với sự phát triển của web thì những chuẩn web càng được chú trọng. Trong đó các trang web cần có những phần giới thiệu tổng quan, các từ khoá để các máy tìm kiếm, các công cụ khác có thể xác nhận dễ dàng. Nó được thể hiện trong các trang web là các thẻ <meta> trong mã HTML. Nó sẽ giúp cho máy tìm kiếm làm việc tốt hơn, các chương trình khác có thể tiếp cận trang web tốt hơn. Đa số các trang web hiện nay đều sinh từ khoá một cách thủ công. Nó sẽ khá là hiệu quả đối với những doanh nghiệp có số lượng trang web nhỏ. Còn đối các máy tìm kiếm, các trang có nhiều văn bản web, thì việc sinh tự động là rất quan trọng. Nó vừa đảm bảo thời gian, công sức vừa có thể tìm ra được những từ khoá mà ngay cả chủ trang web có thể thiếu xót. Với thực tế nêu trên, khoá luận đã đề xuất một phương pháp giải quyết bài toán trích xuất từ khoá cho trang web tiếng Việt và tiếng Anh qua đề tài “Bài toán trích xuất từ khóa cho trang Web áp dụng phương pháp phân tích thẻ HTML và đồ thị Web”. Mục tiêu của đề tài là nghiên cứu giải quyết bài toán sinh từ khoá theo hai phương pháp chính là: phân tích nội dung trang dựa trên thẻ HTML và đồ thị web. Ngoài ra, khóa luận cũng nêu thêm hai phương pháp khác hỗ trợ để nâng cao chất lượng từ khóa đó là : khai phá log và dùng từ điển hỗ trợ. Với từng loại trang web sẽ có từng loại phương pháp khác nhau. Trong đó phương pháp khai phá nội dung trang dựa trên thẻ HTML là chủ đạo với nhiều trang. Qua thực nghiệm cho thấy các hướng tiếp cận này là khả quan và có triển vọng với độ chính xác khá cao, nếu kết hợp với các từ khoá của chính người quản trị thì tập từ khoá sinh ra là khá đầy đủ và chính xác. Ngoài phần MỞ ĐẦU và KẾT LUẬN, kết cấu của khoá luận bao gồm các chương sau: - Chương 1: Giới thiệu về bài toán. Nêu các khái niệm cơ bản về bài toán. Các ứng dụng của bài toán. Những thách thức đặt ra cho bài toán. - Chương 2: Các công trình liên quan. Giới thiệu sơ lược về các phương pháp đã được áp dụng với các bài toán sinh cho văn bản, cho trang web. - Chương 3: Hướng giải quyết và đề xuất mô hình bài toán. Miêu tả hướng giải quyết của tác giả, đề xuất mô hình có thể thực thi. -Chương 4 “Kết quả thực nghiệm và đánh giá”. Đưa ra những kết quả đã làm, và đánh giá kết quả.

doc59 trang | Chia sẻ: lvcdongnoi | Ngày: 03/07/2013 | Lượt xem: 1791 | Lượt tải: 2download
Bạn đang xem nội dung tài liệu Khóa luận Bài toán trích xuất từ khoá cho trang web áp dụng phương pháp phân tích thẻ HTML và đồ thị web, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
4. 2.2. Các phương pháp trích xuất từ khóa cho trang web 2.2.1. Tần số từ Phương pháp tần số từ trong văn bản có thể được áp dụng trên các trang web. Việc lấy ra nội dung của văn bản trong các trang web là đơn giản. Và phương pháp phân tích nội dung này, thống kê tần số xuất hiện của các từ, cụm từ áp dụng kĩ thuật n-gram. Một ví dụ về trích từ khoá cho trang web phục vụ hoạt động của SEO của Andy Hoskison, LLC trong Hình 5 áp dụng kĩ thuật tìm các từ khoá đơn và cụm từ khoá bằng phương pháp xét tần số xuất hiện của các từ trong văn bản hiển thị web. Phương pháp tìm từ khóa trang web này chỉ dừng lại ở việc tìm từ khóa đơn và kép, tính tần số của nó trên chính trang đó, cho nên nhiều trang web cho không chính xác. Hình 5. Hình minh họa kết quả sinh từ khóa của trang web 2.2.2. Kĩ thuật khai phá log Các máy tìm kiếm sử dụng kĩ thuật khai phá log để có thể tìm ra những từ khoá khác nhau cho trang web[31] . Đó là một lợi điểm của các máy tìm kiếm. Những hoạt động trước của người dùng được ghi lại sẽ cho ta hiểu cách nghĩ của người dùng đối với các trang web. Họ cố gắng tìm ra mối quan hệ giữa các từ khóa đã được người dùng tìm dựa vào một tập các từ khoá ban đầu. Google’s Adword Tool [31] là một ví dụ về việc dùng log để đưa ra những từ khóa gợi ý, với đầu vào là từ khoá ban đầu. Yahoo’s Keyword Selection Tool [32] cũng tương tự khi sử dụng tần số xuất hiện của những từ khoá liên quan tới từ khoá của người dùng yêu cầu. Một phương pháp mới hơn được Bart đễ xuất dựa trên việc lọc liên hợp (collaborative filtering) sử dụng mối quan hệ của query và các url click vào trong log [16]. Tuy nhiên những từ khóa gợi ý sẽ là những từ khóa xuất hiện nhiều trong log, thường có độ phổ biến cao và quan trọng do đó từ khóa này sẽ có giá cao. 2.2.3. Kĩ thuật áp dụng máy tìm kiếm và độ tương đồng từ Bài báo [25][17] sử dụng chính máy tìm kiếm, cùng độ tương đồng từ để áp dụng cho bài toán tìm từ khóa cho trang web. Phương pháp đã được dùng trong thương mại đó là việc áp dụng dựa vào tìm kiếm lân cận (proximity search) để sinh từ khóa. Proximity Search là cách dựa vào máy tìm kiếm, với một query đầu vào gọi là từ khoá hạt giống (seed keyword) và tìm ra được những từ khoá từ những trang liên quan trả về từ máy tìm kiếm. Kĩ thuật này nhằm tìm từ khóa cho một trang chủ, portal. Quy trình của phương pháp này có thể được miêu tả như sau: Bước 1: Tải về toàn bộ các trang thuộc cùng domain với trang này(có thể phải giới hạn số trang lấy về) Bước 2: Trích xuất các từ khóa cho các trang web này dựa vào độ đo (tf x idf). Lưu trữ dưới dạng một tập từ điển ban đầu (lấy trong các ngưỡng xác định, loại bỏ từ dừng...) Bước 3: Với mỗi từ khóa trong bộ từ điển từ khóa, tìm kiếm những trang web liên quan nhờ các máy tìm kiếm. Chỉ lấy các trang đầu trả về của máy tìm kiếm. Bước 4: Tải các trang trong kết quả máy tìm kiếm trả về, sinh từ khóa cho các trang web này dựa vào tần số xuất hiện của từ, so sánh độ tương đồng ngữ nghĩa của từ tìm kiếm và các từ khóa này. Nếu thỏa mãn các ngưỡng về độ tương đồng, tần số xuất hiện thì thêm vào từ điển những từ khóa này. Bước 5: Thống kê lại các từ khóa nhờ vào tần số xuất hiện trong từ điển. Kết quả của phương pháp này khá là hiệu quả và tốt, nhưng chi phí cho nó là rất nhiều, và nó phù hợp cho các trang mà độ nhiễu trong các trang khác nhau là không quá lớn. Việc so sánh ngữ nghĩa của các từ khóa tốt là thành công cho phương pháp này. 2.3. Gán từ khóa trong văn bản, web (keyword assignment) Các phương pháp nêu trên là các phương pháp dùng để trích xuất từ khóa (keyword extraction) [29][9][28]. Trong khi đó có một phương pháp cũng đã được sử dụng nhiều trong trang web, và cả văn bản đó là phương pháp gán từ khóa. Việc gán từ khóa chỉ là việc khớp các từ trong văn bản, web với các từ thuộc bộ từ điển có sẵn. Từ những trang cần sinh từ khóa, ta lấy ra những đoạn text trong trang web đó. Dùng các kĩ thuật tách từ, n-gram để khớp các từ khóa với các từ trong bộ từ điển có sẵn. Giải pháp này được áp dụng nhiều trong các trang báo điện tử, các bản tóm tắt, để có thể khớp một cách chính xác nhất. Các từ được khớp chính là các từ trong từ điển nên chúng sẽ không bị sai về mặt ngữ pháp, hay lộn xộn về mặt từ vựng. 2.4 Tổng kết chương Chương này đã giới thiệu những phương pháp cơ bản để giải quyết bài toán trích xuất từ khóa trong văn bản cũng như đối với Web. Các phương pháp này hiệu quả đối với một số miền, và có thể áp dụng trong nhiều bài toán khác nữa. Trong chương tiếp, tôi xin trình bày về hướng giải quyết bài toán sinh từ khóa trên các trang web, xây dựng mô hình. Chương 3. Hướng giải quyết và đề xuất mô hình bài toán 3.1. Hướng giải quyết Như đã đề cập ở chương II, nhiều phương pháp đã được áp dụng trên thực tế và có kết quả tốt như : sử dụng log, độ tương đồng từ. Tuy nhiên, các phương pháp này chỉ hiệu quả với các trang Web tiếng Anh. Các máy tìm kiếm có lợi thế khi họ lưu trữ được những bộ log rất lớn, ghi lại các giao dịch của người dùng trong nhiều năm. Vì vậy, việc tìm kiếm trong log sẽ rất hữu hiệu cho các doanh nghiệp tìm ra các từ khóa hướng người sử dụng. Còn các phương pháp áp dụng học máy, thì giá phải trả là họ phải có tập huấn luyện, thời gian chạy khá lâu. Kết quả tốt thì tập dữ liệu huấn luyện phải tốt. Các phương pháp sử dụng tần số đơn thuần thể hiện không hiệu quả do chỉ xét tần số mà chưa tính đến độ quan trọng trong văn bản Web. Một thách thức khác đặt ra với tiếng Việt chính là việc tách các cụm từ. Không những chỉ có văn bản thông thường được hiển thị, web còn chứa đựng trong nó nhiều các đặc trưng khác mà rất quan trọng cho bài toán sinh từ khóa. Dưới đây là hai hướng tiếp cận chính của tôi trong khóa luận đó là: sử dụng độ quan trọng của các thẻ trong HTML và đồ thị web. Hai hướng này là chủ đạo có thể áp dụng với các loại trang web tiếng Việt và tiếng Anh. Tuy nhiên, phương pháp đồ thị web do phải xử lý nhiều nên phù hợp hơn với các trang chủ, các web portal. Bên cạnh hai phương pháp trên, tôi còn ứng dụng thêm hai phương pháp đó là : query log, và từ điển (bài toán gán từ khóa). Do log chỉ giới hạn một số trang và với ngôn ngữ xác đinh, nên nó chỉ là thành phần hỗ trợ nhằm nâng cao kết quả cho các trang web trong log. Còn bài toán gán từ khóa là các từ trong từ điển tiếng Việt, thì nó chỉ phù hợp cho việc gán từ khóa cho các văn bản ngắn, các đoạn tóm tắt bằng tiếng Việt. Sau đây tôi xin trình bày các phương pháp đã đề cập ở trên. 3.1.1. Sử dụng độ quan trọng của các thẻ trong HTML Theo Wikipedia [3] HTML (tên Tiếng Anh viết tắt của HyperText Markup Language hay “ngôn ngữ đánh dấu siêu văn bản”) là một ngôn ngữ đánh dấu được thiết kế nhằm mục đích hiển thị các thông tin khác nhau lên trên trình duyệt. Với ngôn ngữ HTML, chúng ta có thể biểu diễn trang web một cách sinh động, tùy thích với nhiều màu sắc, điểm nhấn, cấu trúc khác nhau. HTML bây giờ đã trở thành chuẩn của tổ chức World Wide Wed Consortium (W3C) duy trì, và được mọi trình duyệt phải thiết kế theo. Các file HTML có chứa các thẻ đánh dấu, nghĩa là các chỉ thị cho chương trình về cách hiển thị hay xử lý văn bản ở dạng thuần túy. Ngôn ngữ HTML có rất nhiều các thẻ khác nhau, chi tiết có thể xem tại W3C. Ví dụ: Khi một người muốn nhấn mạnh một điều gì đó trong bài viết của mình họ thường tô đậm chữ với thẻ hoặc dùng các thẻ ,... để có thể phân biệt được với các chữ khác. Hay các thẻ như trong văn bản web có chứa tiêu đề của trang web đó. Nhờ những đặc điểm sẵn có là HTML trong văn bản web, tôi đã đề xuất phương án áp dụng độ quan trọng của các từ trong các thẻ khác nhau trong văn bản HTML để phục vụ cho bài toán sinh từ khóa. Trước hết, áp dụng phương pháp này vào bài toán trích xuất từ khóa là việc lấy nội dung nội tại của trang web về để xử lý - hay văn bản HTML của chính trang cần trích xuất. Như đã nhắc về các công trình liên quan tại chương II [25][13], tần số từ (TF) là một trong những phương pháp có thể áp dụng không những trong văn bản , mà còn trong cả web. Phương pháp của tôi đề xuất không tính trực tiếp tần số xuất hiện của các từ khóa trong văn bản web, nhưng cũng gián tiếp tính tần số của chúng nhưng theo độ quan trọng khác nhau của mỗi loại thẻ HTML quan tâm. Một chú ý, ở phương pháp này không dùng IDF do chỉ xét trên chính một trang. Mỗi trang web hiển thị lên trình duyệt được nhờ vào các thẻ HTML. Cho nên, với người soản thảo web, họ sẽ chủ động đặt những từ, câu quan trọng trong các thẻ HTML có độ quan trọng cao. Nhiệm vụ đặt ra là làm sao biết trong HTML thẻ nào là quan trọng, và thẻ nào quan trọng hơn thẻ nào, thẻ nào không quan trọng. Trong dự án tạo phần abstract (tóm tắt) cho văn bản của ứng dụng TextNet [7][6], qua nhiều thực nghiệm, nhóm các nhà nghiên cứu đã đưa ra được trọng số của các thẻ trong HTML dưới Bảng 1 sau: Bảng 1. Bảng trọng số các thẻ HTML trongTextNet TAG HTML WEIGHT A 1 B 2 BLOCKQUOTE -1 CENTER 3 CODE -1 EM 1 H1 10 H2 9 H3 8 H4 7 KBD -1 PRE -1 SAMP -1 STRONG 2 SUB -1 SUP -1 TITLE 15 U 1 Và tôi cũng áp dụng trọng số của các thẻ này trong quá trình thực nghiệm. Như thấy trong bảng, thẻ có trọng số cao nhất, một số thẻ dạng hay không quan trọng mà còn làm giảm đi ý nghĩa của từ thể hiện trong nó. Tuy nhiên, đối với bài toán sinh từ khóa không những chỉ xét những thẻ đó, mà còn cần xét những thẻ khác nữa và tôi đưa thêm vào một số thẻ khác trong Bảng 2 : Bảng 2. Bảng các thẻ HTML quan trọng khác TAG HTML WEIGHT P 1 DIV 1 META(name = ‘Keywords’) 17 META(name = ‘descriptions’) 10 Qua quá trình thực nghiệm, các trọng số của các thẻ này được điều chỉnh cho phù hợp sao cho kết quả đầu ra là tốt nhất. Những thông tin nằm trong các thẻ khác nhau thì có độ quan trọng khác nhau. Một câu, cụm từ, hay từ có thể nằm đan xen trong nhiều thẻ khác nhau. Vì vậy, trọng số toàn cục của câu, từ này sẽ là tổng số các trọng số mà nó thuộc vào các thẻ. Các từ hay câu thuộc vào những thẻ nào thì nó sẽ nhận tổng của các trọng số của các thẻ đó. Vì vậy, việc tính tần số vẫn tồn tại ngầm trong trọng số toàn cục. Ví dụ như một văn bản HTML dạng TIT P T B TIT Trong văn bản trên các từ “TIT” sẽ nhận các trọng số của thẻ và thẻ , do chúng đều nằm trong các thẻ này. Và trọng số của “TIT” = trọng số + trọng số + trọng số . Tương tự, trọng số của “T” được tính = trọng số + trọng số + trọng số. Gọi : T= {tập các thẻ của HTML mà ta quan tâm} W = {trọng số các thẻ HTML} W(i) = trọng số của thẻ thứ i thuộc T. Trọng số từ “A”=(với từ “A” xuất hiện trong “thông tin quan tâm” của thẻ i ) “Thông tin quan tâm” của thẻ i là những phần văn bản nằm trong phần mở thẻ và đóng thẻ hay những thuộc tính của thẻ. 3.1.2. Sử dụng đồ thị web 3.1.2.1. Định nghĩa đồ thị Web Các trang web ngoài các đặc trưng về sự hiển thị trên trình duyệt qua ngôn ngữ HTML mà chúng còn có sự liên kết, kết nối đến nhau. Chính những liên kết này tạo nên đồ thị web. Đồ thị Web là một đồ thị có hướng gồm các đỉnh là các trang web (các trang tĩnh), và có cung nối từ trang A đến trang B nếu từ trang A có liên kết đến trang B. Liên kết trong trang web được thể hiện qua thẻ của HTML(Hình 6). Thuộc tính href= “B” của thẻ có giá trị B chính là địa chỉ của trang B. Chính vì các trang web trên Internet hiện nay là rất lớn, và có rất nhiều liên kết, nên việc tạo được một đồ thị web cho liên quan đến các trang lớn đòi hỏi nhiều thời gian và phức tạp. Hình 6. Mô tả đồ thị web A C B D Mạng của các liên kết trong đồ thị web đã làm cho nâng cao, cải thiện việc tìm kiếm trên mạng [21][14][15][10] và làm cho việc phân lớp chính xác hơn [22] và đánh giá được các trang mới nhất trên cộng đồng mạng [23]. Hơn thế nữa các liên kết này còn là một nguồn thông tin cung cấp dồi dào phục vụ cho các ngành khoa học xã hội. Và bên cạnh đó, nó còn giúp đánh giá được các đường đi tồn tại trong đồ thị web này nhằm phục vụ việc gợi ý cho người dùng. Đồ thị web có rất nhiều ứng dụng trong việc khai phá web, là cơ sở để các máy tìm kiếm đánh hạng trang (thuật toán HITS), phân tích hành vi người dùng, hỗ trợ bài toán crawling... 3.1.2.2. Nội dung của phương pháp Trong các trang web có các liên kết đến các trang web khác, và có nhiều trang khác có link liên kết đến các trang này. Trong các trang web, liên kết được thể hiện qua thẻ . Trang A có các liên kết đến tập các trang khác và trong một số trường hợp tập các trang này liên quan đến trang A, nhưng nhiều trường hợp tập các trang lại không liên quan nhiều đến trang A đó. Đặc biệt đối với các trang chủ, trang tổng hợp thì có rất nhiều liên kết tới không liên quan. Trong khi đó, một phần nội dung của những trang trỏ đến trang A lại liên quan đến trang A. Những người soạn thảo web khi tạo liên kết đến một trang nào, họ luôn dùng một vài từ đặc trưng đến trang web họ muốn trỏ tới, rồi đặt thẻ liên kết đến trang đó. Vì vậy, chính những phần hiển thị (của phần liên kết trỏ tới các trang) trên trình duyệt nói lên phần nào suy nghĩ của người khác về trang đang được hướng tới. Trong liên kết web của trang THPT-NTT (Hình 7), ta thấy được cách đặt phần hiển thị cho một số trang báo nổi tiếng. Giả dụ ở đây, nếu ta muốn sinh từ khóa cho trang dân trí , dựa vào phần hiển thị là “Đọc báo trực tuyến Dân Trí” ta có thể trích xuất ra các từ khóa như : đọc báo, trực tuyến, dân trí.... Nếu phân tích nhiều trang khác trỏ đến trang dân trí này thì kết quả sẽ cho cao hơn. Hình 7. Phần hiển thị của các liên kết đến các trang cần trích xuất từ khóa Trong khóa luận này, tôi áp dụng các liên kết trỏ đến các trang cần sinh từ khóa. Vậy làm sao để có thể tìm được một trang có liên kết đến trang ta muốn sinh từ khóa? Những trang có liên kết đi thì dễ dàng tìm thấy khi chỉ phải phân tích nội dung của chính văn bản HTML và nhận dạng các thẻ . Để tìm được các link liên kết đến trang cần sinh từ khóa, tôi sử dụng công cụ máy tìm kiếm như google, yahoo, altavista để tìm ra các link trỏ đến trang web mà ta đang muốn có từ khóa. Câu truy vấn trong các máy tìm kiếm để tìm ra tập các trang trỏ đến một trang có dạng “link:A”. Với câu truy vấn này các máy tìm kiếm sẽ trả về tập các trang web có liên kết trỏ đến trang “A” này. Hình 8, là tập các trang web trả về từ máy tìm kiếm google có liên kết đến trang Hình 8. Kết quả trả về của máy tìm kiếm Google có liên kết trỏ tới trang vnexpress Qua việc xử lý kết quả trả về qua các máy tìm kiếm, chúng ta kết nối, tải các trang liên quan này về rồi phân tích cấu trúc của các trang web này. Dựa vào thẻ (anchor text) tìm những liên kết có địa chỉ giống như trang ta muốn sinh từ khóa. Từ đó lọc ra các phần hiển thị của thẻ đó, xử lý chúng để tìm ra từ khóa. Do kết quả của các máy tìm kiếm trả về có những trang với tập kết quả rất lớn, nên có thể dùng số lượng các từ khóa để giới hạn việc tải các trang web về. Việc sử dụng máy tìm kiếm làm công cụ trung gian không những giúp tìm các trang có liên kết đến trang ta cần sinh từ khóa, mà còn giảm đi lượng lớn các trang không đúng, thiếu tin cậy nhờ vào thứ hạng của máy tìm kiếm. Tuy nhiên phương pháp này sẽ có tác dụng đối với các trang có liên kết đến. Đối với các trang không nổi tiếng, hay không có link đến thì sẽ không tìm được các trang liên quan, và không có kết quả. 3.1.3. Sử dụng query log Các máy tìm kiếm hàng ngày phải trả lời yêu cầu của người dùng rất nhiều. Và những thông tin của người dùng cũng rất hữu hiệu cho việc tìm từ khóa cho các trang web. Đối với các người quản trị web thì họ có thể tự tìm được những từ khóa cho trang web của mình. Nhưng đôi khi chính họ cũng không thể biết được những suy nghĩ mà người dùng nghĩ tới trang web của mình như thế nào. Chính vì vậy, những nhận xét của số đông người dùng sẽ là một phương pháp hữu hiệu để sinh từ khóa một cách đại trà nhất theo cách hiểu của người dùng. Như đã đề cập ở chương I, các máy tìm kiếm có một lợi thế khi họ ghi lại quá trình sử dụng của người dùng để có thể hướng đến chủ đề người dùng quan tâm, hay cách nghĩ của họ về các trang web. Trong các máy tìm kiếm có các bộ log ghi lại toàn bộ thông tin truy cập, tra cứu của người dùng khi dùng. File này được lưu lại có các trường như: ngày tháng, phiên giao dịch, query truy vấn, url được click, browser...Dưới đây là ví dụ một phần của log của máy tìm kiếm MSN [39]( dung lượng ~ 1.3Gb) mà tôi cũng dùng làm thực nghiệm( Bảng 3): Bảng 3. Ví dụ về các trường trong querylog của MSN Time Query QueryID SessionID URL Result count 1 2006-05-01 00:00:03 us geography f6f710aa27014dac 1cb8398abb354112 20 2 2006-05-01 00:00:04 msn groups ba6d190cc4cd4fd3 136fd5e571d24886 10 3 2006-05-01 00:00:05 internal drive a0f7737bb44c46d5 0ff87b8bdbac406d 12 Hàng ngày số người tìm kiếm trên các máy tìm kiếm là rất nhiều, cho nên các file lưu trữ này thường rất lớn. Chúng ta quan tâm đến 2 trường query và url được click vào để giải quyết bài toán trích xuất từ khóa. Khi đưa trang web cần sinh từ khóa vào, nhiệm vụ đặt ra cần tìm các query mà đã dùng máy tìm kiếm rồi truy nhập vào trang này. Các từ khóa sinh ra sẽ dựa vào tần số xuất hiện của các từ trong query. Vì đã qua bước xử lý của máy tìm kiếm, nên kết quả thường có kết quả khá chính xác. Tuy nhiên, những kết quả trả về của số đông cho nên giá của các từ khóa trên máy tìm kiếm thường đắt. 3.1.4. Sử dụng từ điển hỗ trợ Đối với những trang tin tức, hay báo chí là những bài viết về một chủ đề. Chúng ta có thể áp dụng phương pháp gán từ khóa cho văn bản này bằng cách so khớp các từ trong văn bản với những từ hiện có trong từ điển. Sự phong phú, chính xác của từ điển cũng dẫn đến sự chính xác, đa dạng trong cách sinh từ khóa. Các từ khóa này sinh ra do đã qua từ điển nên chúng có ý nghĩa rõ ràng, rành mạch. Tuy nhiên, phương pháp này sẽ tốn nhiều thời gian nếu từ điển là lớn, và văn bản áp dụng dài. Nó đặc biệt hữu ích với các trang có các phần tóm tắt, và nhiệm vụ chỉ là sinh từ khóa cho một đoạn văn tóm tắt. Trang báo điện tử báo mới là một trong những trang web đã có phần sinh từ khóa này trong các tóm tắt văn bản [29][9][28]. 3.2. Đề xuất mô hình bài toán Internet tập các trang web Mô đun Crawler1 Mô đun crawler2 (sử dụng google, yahoo,altavista ) Tập các trang web có link trỏ tới Mô đun sinh từ khóa Tập các từ khóa (với mỗi trang web) Kết quả 3.2.1. Mô hình toàn hệ thốngHình 9. Mô hình đề xuất cho toàn hệ thống Internet: ở đây ta sẽ dùng một miền xác định(như 1 thư mục của máy tìm kiếm) Mô đun Crawler1: Có nhiệm vụ lấy về nội dung toàn bộ các trang web và sao lưu thành tập các trang web. Tập các trang web này chính là tập các trang để hệ thống sinh từ khóa Mô đun Crawler2: Dựa vào máy tìm kiếm google, yahoo, mô đun lấy về toàn bộ các trang web mà trong nó có liên kết trỏ đến những trang ta cần sinh từ khoá (tôi chỉ quan tâm thẻ a có địa chỉ chính xác như domain của trang web cần phân tích). Mô đun sinh từ khóa : mô đun có nhiệm vụ sinh từ khóa dựa vào các nguồn dữ liệu khác nhau (nội tại trang web, đồ thị web). Mô đun này được chia ra làm các mô đun nhỏ hơn ứng với các phương pháp. Ngoài ra, tôi cũng đề xuất thêm các môđun sinh từ khóa qua phân tích log (đối với các trang web tiếng Anh) và mô đun sinh từ khóa gán qua từ điển(đối với các trang ngắn bằng tiếng Việt). Mô hình cho các phương pháp bổ sung được trình bày ở phần “3.2.3.3. Các phương pháp hỗ trợ”. 3.2.2. Mô đun Crawler Gồm hai mô đun: Crawler1, Crawler2 có chung nhiệm vụ là tải các trang web về dựa theo việc phân tích liên kết trong nội dung của các trang. Mô đun Crawler1 tải các trang từ một thư mục trên Internet, còn mô đun Crawler2 dựa vào máy tìm kiếm để tải các trang về. Mô đun Crawler1 - Yêu cầu: input: địa chỉ của một trang web có chứa địa chỉ của tập các trang web cần sinh từ khóa( ví dụ như 1 thư mục trong các máy tìm kiếm). output: Tải về nội dung của các trang có địa chỉ trong trang thư mục đó, kể cả các thư mục con của nó. - Quy trình thực thi: Bước 1: Tải trang web của thư mục cần lấy về. Bước 2: Phân tích nội dung trang này, lấy về các địa chỉ cần sinh từ khóa. Bước 3: Tải các trang cần sinh từ khóa có địa chỉ vừa lấy được. Bước 4: Đưa địa chỉ các thư mục khác liên quan rồi quay lại bước 2. Lặp cho đến khi không còn trang web, hoặc đạt đến số trang cần lấy. Mô đun Crawler2 - Yêu cầu: input: địa chỉ trang web cần sinh từ khóa output: Tải về nội dung của các trang có liên kết đến trang web này. - Quy trình thực thi: Gửi yêu cầu đến các công cụ tìm kiếm là google, yahoo, altavista. Yêu cầu dạng : “link:A” (với A là địa chỉ trang web cần sinh từ khóa). Tải các trang nội dung trả về từ các máy tìm kiếm. Phân tích nội dung các trang này, tìm các địa chỉ và tải các trang về. Lặp lại để tìm được số lượng trang phù hợp. Để tiết kiệm bộ nhớ không phải lưu nội dung các trang khi tải về, có thể kết hợp việc tải các trang và xử lý sinh từ khóa cùng lúc. 3.2.3. Mô đun sinh từ khóa Đây là mô đun chính, sử dụng các phương pháp khác nhau. Phương pháp chủ đạo dành cho các trang web là sử dụng độ quan trọng của các thẻ HTML và đồ thị web. Phương pháp khai phá log hỗ trợ, nâng cao chất lượng của từ khóa. Phương pháp sử dụng từ điển hỗ trợ chỉ sử dụng đối với một số tóm tắt văn bản, hay những văn bản ngắn. Tập các trang web Tập các trang có liên kết trỏ đến Mô đun sử dụng trọng số thẻ HTML Mô đun tìm từ khóa sử dụng đồ thị web Tập từ khóa 1 Tập từ khóa 2 Tổng hợp từ khóa Tập các từ khóa Tập từ khóa từ log Tập từ khóa (từ điển) Hình 10. Mô hình mô đun sinh từ khóa 3.2.3.1. Mô đun sử dụng trọng số thẻ HTML - Nhiệm vụ : + input: tập các trang web cần sinh từ khoá. + output: tập các từ khoá. Kĩ thuật sử dụng là dùng những thông tin nội tại trong trang web, xét độ quan trọng của các thẻ khác nhau trong tập văn bản HTML để sinh từ khóa. Các từ xuất hiện trong thẻ nào thì nó sẽ có giá trị là trọng số của thẻ đó. Nếu một từ xuất hiện trong các thẻ khác nhau, trọng số của từ đó sẽ là tổng trọng số các thẻ nó thuộc vào. Đối với các trang Web tiếng Việt thì sử dụng mô đun tách từ, còn các trang tiếng Anh có thể bỏ qua các trang tách từ. Trong giai đoạn tách từ, các từ dừng sẽ được loại bỏ để tránh nhiễu. - Mô hình chi tiết: Hình 11. Mô hình mô đun sinh từ khóa áp dụng độ quan trọng thẻ HTML Nội dung của thẻ() Nội dung của thẻ ( ) Nội dung của thẻ () Sử dụng tách câu, tách từ(Tiếng Việt) Tập các từ(a) Tập các từ (b) Tập các từ(u) Tập các từ (toàn bộ trang) Thống kê từ có trọng số cao Trọng số thẻ b Tập trang web HTML parser Nội dung toàn bộ trang Tập từ khóa (thẻ HTML) - Quá trình thực thi: + Với đầu vào là tập các trang web cần sinh từ khoá. Ở mỗi thời điểm ta chọn 1 trang để sinh từ khoá. + Trang dưới dạng HTML được đưa qua bộ phân tích cú pháp HTML(HTML parser). + Đối với từng thẻ xác định (chỉ đề cập đến một số thẻ quan trọng) lấy ra nội dung của nó. Cùng với đó ta cũng lấy toàn bộ text của trang web (vì trong các tag quan trọng không có p, div...) + Nội dung sau khi được trích ra đi qua bộ phân tích để tách câu, tách từ (đối với tiếng Việt). + Với mỗi thẻ trong HTML có trọng số khác nhau. Gán trọng số cho mỗi thẻ, nếu từ nào trong thẻ nào thì nhận trọng số của thẻ đó, nếu từ nằm trong nhiều thẻ thì cộng các giá trị lại với nhau. + Qua thống kê loại bỏ những trọng số quá yếu đi => tâp các từ khóa (thẻ HTML) 3.2.3.2. Mô đun sử dụng đồ thị web - Nhiệm vụ: Bởi vì những trang trỏ đến những trang khác thì nó có khả năng nói lên được một cách ngắn gọn về trang đó. Nhiệm vụ của mô đun nhằm tìm ra những từ là nội dung của các thẻ a liên kết đến trang ta cần sinh tag. - Mô hình chi tiết: Tập các trang có liên kết tới HTML Parser Địa chỉ trang Nội dung của thẻ có href=địa chỉ trang Tập từ khóa (đồ thị web) Hình 12. Mô hình mô đun sinh từ khóa dựa trên phương pháp đồ thị web - Quy trình thực thi: + Đầu vào là một tập các trang web có liên kết đến trang cần tìm khoá. + Chỉ quan tâm domain, không quan tâm những link sub domain. + Với mỗi trang dùng HTML parser + lấy ra nội dung của các thẻ a mà có href trỏ trực tiếp đến trang ta quan tâm. + Loại bỏ trùng lặp=> tập các từ khóa (đồ thị web) sử dụng tần số. 3.2.3.3. Các phương pháp hỗ trợ Có hai phương pháp nhằm hỗ trợ nâng cao chất lượng từ khóa sinh ra là: sử dụng log của máy tìm kiếm, sử dụng từ điển hỗ trợ. Hai phương pháp này giới hạn về ngôn ngữ, và loại trang web sử dụng. 3.2.3.3.1. Phương pháp sử dụng log - Yêu cầu: có log của các máy tìm kiếm, chèn chúng vào cơ sở dữ liệu thì truy vấn kết quả sẽ nhanh hơn. Các trang web phù hợp với ngôn ngữ được dùng trong log. - Nhiệm vụ: + input: địa chị trang web cần sinh từ khóa. + output: tập các từ khóa. - Mô hình chi tiết: Hình 13. Mô hình mô đun sinh từ khóa dựa trên log CSDL log Địa chỉ trang web Mô đun sinh từ khóa dựa vào log truy vấn kết quả tập từ khóa (log) - Quy trình thực thi: + Truy vấn trong CSDL Log với url = địa chị trang web cần sinh, lấy các query tương ứng. + tổng hợp các query kết quả trả về, rồi tính toán dựa vào tần số xuất hiện. + Sắp xếp theo tần số xuất hiện để có tập từ khóa. => tập từ khóa (log). 3.2.3.3.2.Phương pháp sử dụng từ điển - Yêu cầu: cần có bộ từ điển - Nhiệm vụ: Dùng từ điển chuyên dụng để tìm ra những từ có trong từ điển và hay gặp, nâng cao chất lượng của từ. Hình 14. Mô hình mô đun sinh từ khóa dựa trên từ điển hỗ trợ Tập trang web HTML parser Lấy toàn bộ phần văn bản Tìm những từ xuất hiện trong từ điển Tập từ điển Tập từ khóa (từ điển) - Mô hình chi tiết - Quy trình thực thi: + Với mỗi trang web đầu vào đi qua bộ HTML parser. + Lấy ra nội dung văn bản của toàn bộ trang (hoặc có thể chỉ lấy phần quan trọng như phần tóm tắt đối với báo). + Khớp các từ trong nội dung với các từ trong từ điển đã có để tìm ra các từ. Có xét đến tần số xuất hiện của từ. + Sắp xếp có một tập các từ => tập các từ khóa (từ điển). 3.2.3.4. Mô đun tổng hợp - Nhiệm vụ: Tổng hợp toàn bộ từ khóa sinh ra bởi các phương pháp trên. Các phương pháp hỗ trợ cho nhau nhằm tìm ra được những ứng cử viên tốt nhất. Việc tổng hợp các từ khóa có thể áp dụng hàm tuyến tính, thay đổi các tham số để có kết quả chính xác hơn. - Mô hình chi tiết: Hình 15. Mô hình mô đun tổng hợp từ khóa Tập từ khóa (thẻ HTML) Tập từ khóa (đồ thị web) Tập từ khóa (từ điển) Trộn các từ khóa, sắp xếp a1 a2 a3 Tập từ khóa (log) a4 Tập từ khóa - Quy trình thực hiện : Với mỗi tập từ khóa tương ứng có những hệ số xác định Kết hợp các từ khóa, loại bỏ trùng lặp, những từ trọng số quá thấp. Lọc chọn ra top các từ khoá. Ước lượng các tham số a1, a2, a3, a4. 3.3. Tổng kết chương Trong chương này tôi đã trình bày cách tiếp cận của mình đối với bài toán này. Bài toán sử dụng hai phương pháp chính là: độ quan trọng các thẻ HTML, đồ thị web. Ngoài ra, tôi cũng bổ sung hai phương pháp khác là phân tích log, từ điển hỗ trợ nhằm nâng cao kết quả ở một số trang đặc biệt. Chương tiếp theo, tôi xin trình bày quá trình, môi trường thực nghiệm và kết quả của các phương pháp trên. Chương 4. Thực nghiệm và đánh giá 4.1. Giới thiệu bài toán thực nghiệm Bài toán trích xuất từ khoá cho trang web hiện nay đang được sự quan tâm của nhiều các trang web, và các máy tìm kiếm. Việc lựa chọn ra được các từ khoá tốt không phải là dễ dàng. Những cách sinh từ khoá cho trang web từ trước đến giờ đa số đều là sinh bằng tay và mang tính chất cá nhân. Trong luận văn này, tôi muốn đưa ra thực nghiệm trích xuất từ khoá tự động trên một tập các trang web. Các trang web áp dụng sẽ được dùng trên các miền khác nhau là tiếng Việt và tiếng Anh. 4.2. Môi trường, dữ liệu: 4.1.1. Môi trường phần cứng Bài toán được thực nghiệm trên máy có cấu hình như sau: Bảng 4. Cấu hình phần cứng trong thực nghiệm của bài toán Thành phần Chỉ số CPU 1 Pentium IV 2.60 GHz RAM 1GB OS WindowsXP Service Pack 2 Bộ nhớ ngoài 80GB 4.1.2. Mô tả chương trình Chương trình của tôi được mã hóa bằng Java. Ngoài các gói Jvntextpro, và gói HTML parser, chương trình gồm có 4 gói nữa được miêu tả dưới đây: Bảng 5. Các gói của chương trình Packages Vtagging.CharsetDectector Gói này nhằm xử lý các kí tự khác nhau trong văn bản web, xử lý các chữ Tiếng Việt Vtagging.general Miêu tả các cấu trúc dữ liệu liên quan đến các phương pháp Vtagging.methods Cài đặt cụ thể các phương pháp khác nhau Vtagging.SELinks Liên quan đến bài toán Crawl trang web, phân tích link Gói Vtagging.general gồm các lớp Bảng 6. Các lớp của gói general Class Summary Dictionary Tải từ điển có sẵn qua file cấu hình, lưu trữ các từ HTML Tag Miêu tả các thẻ trong HTML KeyWords Miêu tả cấu trúc dữ liệu, phép toán trên các từ khóa ListKeyword Miêu tả cấu trúc dữ liệu, phép toán trên tập các từ khóa StartJvn Miêu tả Jvn, khởi động bộ tách từ Jvn WebPage Miêu tả cấu trúc dữ liệu, phép toán trên các trang web Gói Vtagging.methods gồm các lớp Bảng 7. Các lớp của gói methods Class Summary Content_method Cài đặt thuật toán sinh từ khóa dựa vào nội dung và độ quan trọng thẻ HTML Dictionary_method Cài đặt thuật toán sinh từ khóa dựa vào tập từ điển cho trước Link_method Cài đặt thuật toán sinh từ khóa dựa vào liên kết trỏ đến Gói Vtagging.SELinks gồm các lớp Bảng 8. Các lớp của gói SELink Class Summary MyCrawl Thực hiện tải các trang về theo một miền xác định. NCR2Unicode Chuyển đổi mã trong HTML sang unicode WebPageDownload Tạo kết nối tải trang về SELinks Tải các trang liên quan qua máy tìm kiếm. 4.1.3. Công cụ phần mềm Khoá luận sử dụng một số công cụ phần mềm hỗ trợ trong quá trình thực hiện thực nghiệm: Bảng 9. Danh sách các phần mềm, mã nguồn sử dụng STT Tên phần mềm Tác giả Nguồn 1 JvnTextPro Nguyễn Cẩm Tú 2 HTML Parser Jericho 3 MySqL Mysql Group 4 Eclipse 5 Emeditor Emur asoft Inc. 4.1.4. Dữ liệu thử nghiệm Các trang chủ Dữ liệu dùng để làm đầu vào cho việc sinh tự động từ khoá chính là tập các trang web. Các trang web được crawl để chỉ lấy về url của nó từ địa chỉ ếng_Việt/ gồm các mục con như : Địa phương(99), Doanh nghiệp(246)....(Hình 16) Số ở trong ngoặc là số trang web có trong thư mục. Các thư mục có thể bao gồm các thư mục khác nữa, hoặc trống, hoặc có các link đến các trang web tiếng Việt. Tổng số trang web trên ếng_Việt/ gồm có 1016 trang. Hình 16. Thư mục Tiếng_Việt của dmoz Nhiệm vụ đặt ra là cần lấy được toàn bộ 1016 link trong Director Tiếng_Việt này. Qua mô đun Crawler1(phần mô hình chương III), bằng thuật toán duyệt theo chiều sâu, tôi đã thống kê được toàn bộ số liên kết trên và lưu trong một file văn bản. Các liên kết được lấy ra có dạng như Hình 17, toàn bộ nội dung thông tin liên quan của dmoz và đường dẫn đến thư mục cũng được ghi nhớ với từng trang web. Hình 17.Các liên kết cần lấy về trong các thư mục Một loại dữ liệu thực nghiệm nữa là các trang Tiếng Anh, crawl về cũng trên dmoz. Lấy khoảng tầm 200 trang về để sinh từ khoá. Query log Query log được lấy từ máy tìm kiếm của MSN [39] với khoảng 12 triệu query tương ứng với các url được vào. Query log này được qua quá trình tiền xử lý như : loại bỏ các từ dừng, các trường có chữ Trung Quốc, Ả Rập, giữ lại hai trường quan trọng là query và url.... Sau đó, các query và url này sẽ được chèn vào hệ cơ sở dữ liệu MySQL bằng câu lệnh sau: “load data infile 'C:/log.txt' into table logquery fields terminated by '\t'” Các bài báo Đối với các bài báo (những trang có nội dung tập trung) tôi chỉ lấy một số bài của trang Việt Báo [43], và thử nghiệm và so sánh với các kết quả từ khóa của Việt Báo bằng phương pháp gán từ khóa dựa vào từ điển. Từ điển để phục vụ cho việc gán từ khóa do chúng tôi tự tổng hợp (dựa vào trang báo mới [48] ). Từ điển này được chia theo các loại từ khác nhau như : cụm từ(16512 từ), danh từ(11744 từ), động từ (8599 từ).... Chất lượng của việc sinh từ khóa sẽ do từ điển quyết định. Mô tả dữ liệu - Input: Tập các địa chỉ tới trang web, hoặc nhập vào địa chỉ trang web cần sinh từ khoá. Tiến hành thực nghiệm với toàn bộ 1016 địa chỉ tìm được ở thư mục Tiếng_Việt của dmoz. Tuy nhiên do nhiều kết nối bị lỗi nên chỉ tiến hành thực nghiệm trên 920 trang. Thời gian chạy trung bình mỗi trang là 30s . - Output: Là tập các file chứa từ khoá được sinh ra tương ứng với tập trang web đầu vào. 4.3. Kết quả thực nghiệm: Khóa luận này, tôi áp dụng trên hai loại trang web đó là : các trang chủ và các trang viết về bài báo cụ thể (nội dung tập trung). Thử nghiệm trên các trang chủ Áp dụng quy trình được code theo mô hình ở “3.2. Đề xuất mô hình bài toán”. Tập từ khóa sinh ra được lưu trong các file text. Các từ khóa được sắp xếp theo trọng số từ cao đến thấp. Bảng dưới đây là trích 20 trang web tiếng Việt và tiếng Anh kết quả trích xuất từ khóa. 10 trang Web Tiếng Việt được trích từ các miền khác nhau trong thư mục dmoz/Tiếng_Việt/. Còn 10 trang tiếng Anh, do log chỉ có giới hạn một số trang, nên tôi đã chọn các trang tiếng Anh nổi tiếng để sinh. Các trang này đều là trang chủ với độ nhập nhằng cao. Bảng 10.Kết quả trích xuất từ khóa của một số trang tiếng Việt, tiếng Anh Loại trang web STT Địa chỉ trang web - Miêu tả trang web Kết quả theo các phương pháp khác nhau Dựa vào nội dung thẻ HTML Dựa vào đồ thị web Dựa vào Log Các trang web Tiếng Việt 1 - sức khỏecộng đồng Thầy thuốc mọi nhà health, medical , healthcare, sức_khỏe, y_tế, dịch_vụ, bệnh, y_học, y_khoa, phòng_khám sức_khỏe suckhoecongdong.com cộng_đồng Suckhoecongdong suckhoe - 2 - Ubuntu Việt Nam ubuntu, việt_nam, việt, linux, cộng_đồng, diễn_đàn, wiki, forum, người_dùng, trang_chủ. http:// forum.ubuntu-vn.com, diễn_đàn, ubuntu , vn, việt nam. - 3 - Diễn Đàn Cơ Khí thiet_bi, cơ_khí, diễn_đàn, cnc, cae, cad, cam,lap_trinh, tao_may, vat_tu, sat_thep, han , gia_công, máy. diễn_đàn, cơ_khí, diendancokhi.com, cokhi, diendancokhi - 4 - Diễn đàn Java Việt Nam java, vietnam, j2se, j2ee, mvnforum, jsp, servlet, database, javavietnam, organization, forum, diễn_đàn, lập_trình, câu_hỏi. javavietnam, javavietnam.org, www.javavietnam.org, java - 5 - Pioneer Forum đại_học, công_nghệ, việt_nam, fotech, coltech, quốc_gia, hà_nội, diễn_đàn, vn, sinh_viên diễn_đàn, thanh_niên, sinh_viên, ĐHQGHN, công_nghệ. - 6 - Nhóm câu cá Nguyễn Anh câu_cá, việt_nam, hồ, 4so9, giải_trí, vietnam, fishing, cá_nước_ngọt, cá_biển, cần_câu, nguyễn_anh. câu_cá, clb, nguyễn_anh, diễn_đàn. - 7 - Giao lưu kết bạn Online vietnam, vietnamese, chat, giaoluu, ket_ban, friend, giao_luu, tim_ban, lam_quen, ban_trai, ban_gai. giaoluu, giao_lưu, ----giaoluu----- - 8 -Chúa A Di Da ni, chua, phật, tâm, giới, ca_mưu, di_da, nam, hòa_thượng , chúng_ta, kinh, hội_phật, giáo_việt, canada giáo_hội, việt_nam, thế giói, anlac.ca, visit, chúa, a_di_da - 9 - Bộ Công nghiệp Việt Nam công_nghiệp, bộ, xây_dựng, môi_trường, đầu_tư, quy_hoạch, sản_xuất, quyết_định, tỉnh, chính_phủ www.moi.gov.vn, bộ, công_nghiệp, ministry, industry.công_thương. - 10 - Sudoku Việt Nam sudoku, doku, trò_chơi, game, diễn_đàn, thằng_bờm, chơi, free, jigsuku., bờm. sudoku, thằng_bờm, bờm, diễn_đàn, clb, trò_chời, trực_tuyến, vietnam - Các trang web Tiếng Anh 11 -tutorial web learn, html, examples, web, xml, javascript, asp, css, tutorials, xhtml, xsl, vbscript. ado, dom, building, learning.... W3, schools, tutorial, web. w3chools, w3, tutorial html, web tutorial, w3schools.com 12 -The IEEE Computer Society may, june, april, july, computing, ieee, deadline, cs, society, computer, volunteer, press, security, conference.... IEEE, computer, Society, homepage, ieee, computer.org, computer 13 - UsA government government, usa, portal,home, information, federal, services, state, local, us, us government , america, united states.... USA, gov, USA.gov, state, united, government. usa, usa gov, government, united state 14 - Amazon books, amazon, apparel, computers, electronics, jewelry, dvds, music, tools, beauty, furniture, videos, hardware, broadband, amazon.com, online shopping-, book store..... amazon, amazon.com, united states,book, buy. amazon, book, amazon.com, books 15 - Envelope Manager cass, standard, pave, mailing, ncoa, fastforward, envelope manager, dazzle, direct mail manager, dazzle express, dial-a-zip, first-class, national change of address, mailing software, mailing solutions..... envmgr, envelope, manager, envmgr.com, mail, dazzle, envmgr.com, mailing 16 - CNN News cnn, news, entertainment, weather, com, business, politics, travel, health, sports, cnn news, cnn.com, cnn tv, news online, breaking news, u.s. news, world news.... cnn, cnn.com, news, headlines. cnn, cnn.com, news, weather, usa 17 -BBC News bbc, radio, news, search, top, sport, bbc.co.uk, british broadcasting corporation, world, tv, stories, homepage, weather..... BBC, The Beeb, News, , codmate. bbc, bbc.co.uk, news, britain, radio 18 -Soccer live scores live, livescore, soccer, scores, com, score, euro, european, soccer livescore, live score, football, calcio, livescore.com, result. live results, world cup, real time, championship.... livscore, livesocre.com, realtime, results, live, Scores live, scores, realtime, livescore.com, soccers 19 - Car car, homepage, car.org, more, legal, C, A, R, price. C.A.R , California Association, Realtors, CAR car, C.A.R, car.org 20 - Sun Microsystem sun, java, storage, support, training, service, network, sun. microsystems, java computing, solaris, unix, jini, computer systems. server, mission critical, ras, high availability........ sun, java, microsystems, sun.com, www.sun.com, inc. sun, java, microsystem, sun.com, solaris Qua bảng thực nghiệm, từ khóa sinh ra đối với trang web tiếng Việt ít hơn, và đôi chỗ có những từ không dấu. Tôi thấy rằng các trang chủ của các trang tiếng Anh được bố trí các phần tốt hơn các trang tiếng Việt vì lượng từ khóa sinh ra đối với tiếng Anh tốt hơn, đa dạng hơn. Phương pháp sử dụng độ quan trọng của thẻ HTML đã cho thấy ưu điểm, khi tìm thấy các từ khóa vừa mang tính phổ biến vừa mang tính đặc trưng của các trang web. Thử nghiệm trên các trang báo cụ thể Phần a là các thực nghiệm đối với các trang web dạng trang chủ, portal. Các trang này cũng chính là mục tiêu hướng tới của khóa luận. Bên cạnh đó, đối với các trang có dữ liệu tập trung, chúng tôi cũng áp dụng phương pháp gán từ kết hợp tần số xuất hiện. Thực nghiệm những trang có chủ đề như các bài báo của baomoi.com, hay vietbao.com để sinh ra được nhờ từ điển. Qua hai trang này ta có thể so sánh được tập từ khóa của các trang này sinh ra. Việc dùng từ điển sẽ làm cho việc phân loại các trang báo vào các từ khoá chính xác hơn theo từ điển. Tuy nhiên dùng từ điển hỗ trợ thì sẽ bất lợi là phải trích xuất đúng được phần văn bản của trang web và thời gian để chạy đối với các trang web có nội dung dài là không nhanh. Ví dụ : Trang web tại địa chỉ có nội dung sau: - Theo thông tính chính thức từ CLB Juventus, trung vệ người Italy Fabio Cannavaro đã đồng ý ký vào bản hợp đồng có thời hạn 1đội bóng năm với đội bóng thành Turin. Trên website Juventus, thông tin về việc trung vệ Fabio Cannavaro đã quay trở lại sân Del Alphi đã nhanh chóng được các fan hâm mộ của "Bà đầm già" chào đón. Juventus là nơi Cannavaro đã thành danh và được nhiều cổ động viên hâm mộ. Tuy nhiên, có thời gian cầu thủ này bị gọi là "kẻ phản bội" khi nhanh nhẩu chạy tới Real Madrid khi Juventus bị đánh tụt hạng sau vụ bê bối cách đây vài năm trước. Tại Real Madrid, Fabio Cannavaro thường xuyên bị chấn thương đeo đuổi và gần như không ra sân thi đấu trong mùa giải vừa qua. Trung vệ từng giúp Italy đăng quang tại World Cup 2006 luôn phải ngồi trên băng ghế dự bị và thất vọng vì không được thi đấu, Cannavaro tìm cách quay trở về quê hương. "Tôi rất tự hào khi một lần nữa lại được khoác áo Juventus trong thời gian tới. Ban lãnh đạo đã tha thứ cho những cầu thủ từng ra đi nhưng vẫn luôn nghĩ về đội bóng", Cannavaro tâm sự. Hợp đồng của trung vệ Fabio Cannavaro với CLB Juventus có thời hạn 1 năm. Như vậy, cầu thủ người Italy này sẽ có thời gian chơi bóng tại sân Del Alphi từ tháng 7/2009 đến ngày 30/6/2010. "Nếu cậu ấy vẫn giữ được phong độ ổn định, chúng tôi sẽ tiếp tục gia hạn hợp đồng mới với Cannavaro. Mọi việc tuỳ thuộc vào Cannavaro sẽ thi đấu thế nào ở mùa giải năm tới", một quan chức của Juventus nói. Vừa qua, Juventus đã chính thức sa thải HLV Claudio Ranieri sau khi không thể giúp "Bà đầm già" đoạt Scudetto ở mùa giải năm nay. Qua Bảng 11 các từ khóa của VietBao sinh một tự động nhưng do không dùng từ điển nên có một số kết quả không đúng lắm như : thành, năm. Còn với thực nghiệm của tôi, dựa trên bộ từ điển làm cho các kết quả khá chính xác, nêu lên được nội dung bài viết. Nếu bộ từ điển càng lớn thì các từ khóa sinh ra càng chính xác. Bảng 11. So sánh kết quả trả về của một ví dụ sinh từ khóa cho báo điện tử Từ khóa của Việt báo Từ khóa của chương trình Fabio Cannavaro, CLB Juventus, Italy Fabio Cannavaro, có thời hạn, bản hợp đồng, chính thức, trung vệ, trở lại, thời gian, bóng, năm, thành canavaro-9, juventus-8, fabio canavaro - 4, trung vệ -4, cầu thủ -3, hợp đồng -3, mùa giải -3, thi đấu -3, hâm mộ -2, real madrid -2, madrid-2. 4.4. Đánh giá kết quả thực nghiệm Đánh giá kết quả của một danh sách các từ khoá là một việc làm rất khó khăn trong thời điểm hiện tại. Chủ yếu việc đánh giá vẫn dựa vào ý kiến đánh giá của các chuyên gia ngôn ngữ, hay người quản trị website. Những từ khoá phải mang ý nghĩa cao, nói lên được nội dung của trang web. Các từ khoá phải là những từ khoá phải nói lên được những cái riêng của trang web. Với lượng trang web được sinh từ khóa khá nhiều cả bằng tiếng Việt và tiếng Anh, tôi có một số nhận xét như sau. Các trang tiếng Anh thường được tổ chức tốt hơn, với ít lỗi HTML. Phương pháp áp dụng độ quan trọng của thẻ HTML có ưu điểm hơn các phương pháp khác với các từ khóa sinh ra thỏa mãn các tính chất phổ biến cũng như đặc trưng của trang web. Nó tốt đối với cả trang web dạng portal và các trang web dạng dữ liệu tập trung. Trong thực nghiệm này, đối với phương pháp dùng đồ thị web, do thời gian có hạn nên tôi chỉ giới hạn số từ khóa trả về. Thời gian để chạy cho một trang với phương pháp này là khá lâu bởi khi dùng truy vấn tới các máy tìm kiếm(ba máy tìm kiếm: google, yahoo, altavista ), các kết quả trả về thường lớn. Hơn thế nữa các kết quả này lại trùng nhau về từ khóa nhiều, xảy ra tình trạng tải các trang về lớn nhưng sinh ra từ khóa lại ít. Phương pháp này là một đánh giá tốt của người dùng, người viết trên các trang web khác khi nghĩ về trang web cần sinh từ khóa. Nếu có thời gian để xét trên toàn bộ các trang có liên kết trỏ tới, kết quả của phương pháp sẽ tốt hơn. Đối với log chúng tôi sử dụng, số lượng trang web trong nó chỉ chiếm lượng nhỏ của Internet, cho nên đối với một số trang tiếng Anh không xuất hiện trong log, hoặc xuất hiện ít làm cho kết quả sinh từ khóa chưa được đa dạng. Phương pháp này đã được áp dụng trong các phần mềm sinh từ khóa nổi tiếng như GoogleAdwords [31]. Nếu có những log lớn, thì việc phân tích sẽ cho nhiều kết quả thêm, nâng cao sự chính xác và nhiều sự lựa chọn từ khóa. Kết luận Khóa luận đã hệ thống hóa được các vấn đề của bài toán trích xuất từ khóa cho trang web bao gồm khảo sát về các từ khóa trong các ứng dụng, cách tiếp cận bài toán kèm theo các đánh giá nhận xét. Đặc biệt, khóa luận đã nêu ra một số phương pháp mới áp dụng trên dữ liệu web: độ quan trọng của các thẻ trong HTML, đồ thị web. Đồng thời, khóa luận cũng đã đề xuất ra một mô hình thực thi bằng việc sử dụng việc phân tích trực tiếp trên các trang dựa vào nguồn thông tin sẵn có, chứ không cần phải mất thời gian học. Thực nghiệm trên dữ liệu tiếng Anh, và tiếng Việt cho kết quả khá khả quan. Các nội dung chính của khóa luận được đề cập tóm lược dưới đây. Khảo sát các ứng dụng của từ khóa trong các dịch vụ quảng cáo trên máy tìm kiếm, trong tìm kiếm thông tin, trong hoạt động quảng bá web, phân loại web. Và tôi cũng đã trình bày những khó khăn, thách thức của bài toán đối với miền dữ liệu Web, đồng thời cũng phân tích những lợi điểm mà web đem lại. Trình bày cơ bản về các phương pháp trích xuất từ khóa trong các văn bản, một số phương pháp học máy, sử dụng log đã áp dụng trên dữ liệu web. Tôi cũng đã so sánh, kết hợp nhiều phương pháp khác nhau để có thể phân tích và đưa ra phương pháp riêng. Khóa luận đưa ra được hướng giải quyết bài toán theo cách tiếp cận không chỉ dựa trên nội dung của trang, mà còn xét đến các thông tin khác liên quan đến trang web như : đồ thị web, log. Khóa luận cũng trình bày được mô hình thực thi cụ thể cho các phương pháp, từ đó có thể dễ dàng mã hóa. Kết quả thực nghiệm, quá trình thực nghiệm được trình bày chi tiết. Nhiều thực nghiệm đã được thực hiện nhiều lần để có thể tìm ra được mô hình tốt nhất, và kết quả của khóa luận cũng đạt được khả quan, có thể áp dụng trong thực tế. Hướng phát triển tiếp theo Mặc dù kết quả thu được của khóa luận là đáng khích lệ và khá tốt nhưng do thời gian có hạn việc ước lượng các trọng số cho các phương pháp có thể chưa được tối ưu. Trong thời gian tới, tôi sẽ tiến hành thu thập thêm các dữ liệu và hoàn thiện những gì còn thiếu sót của các mô đun đã đề xuất. Cũng trên cơ sở đã đạt được của khóa luận, tôi dự định xây dựng một hệ thống hoàn thiện để tích hợp vào các máy tìm kiếm, và các trang báo với độ chính xác cao hơn, tiện dụng và thời gian chạy nhanh hơn. Bài toán trích xuất từ khóa cho trang web là bài toán mới và nhiều phần còn liên quan đến ngữ nghĩa, xử lý ngôn ngữ tự nhiên. Tôi sẽ cố gắng tìm hiểu thêm các lĩnh vực liên quan như tóm tắt văn bản tự động, nâng cao chất lượng tìm kiếm trang web với từ khóa.... Tài liệu tham khảo. Tiếng Việt Phạm Thị Thu Uyên, Hoàng Minh Hiền (2008). Độ tương đồng ngữ nghĩa giữa hai câu và ứng dụng trong tóm tắt văn bản Tiếng Việt, Công trình Sinh viên Nghiên cứu khoa học 03/2008 Website: Website: SEO Tiếng Anh Chengzhi ZHANG , Huilin WANG , Yao LIU , Dan WU , Yi LIAO , Bo WANG. Automatic Keyword Extraction from Documents Using Conditional Random Fields. China. Journal of Computational Information Systems4:3(2008) 1169-1180. Craven, T. (1998b). TexNet32 - WWW filters. In Texnet32. Retreived from Craven, Timothy C. HTML Tags as Extraction Cues for Web Page Description Construction. Informing Science; 2003, Vol. 6, p1-12, 12p David B. Bracewell, JiajunYan and Fuji Ren.Single Document Keyword Extraction For Internet News Articles. International Journal of Innovative Computing, Information and Control Volume 4,Number 4,April 2008. E. Frank, G. W. Paynter, I. H. Witten, C. Gutwin, and C. G. Nevill-Manning. Domain-specific keyphrase extraction. In IJCAI, pages 668--673, 1999. E. Spertus. ParaSite: Mining structural informationon the Web. Proc. 6th WWW Conf., 1997. Gonenc Ercan, Ilyas Cicekli. Using Lexical Chains for Keyword Extraction. Inf. Process. Manage., Vol. 43, No. 6. (November 2007), pp. 1705-1714. H.Edmundson(1969). New methods in automatic abstracting, Journal of ACM. 1969. HPLuhn(1958). The automatic creation of literature abstracts. IBM journal of research development. J. Carri ere and R. Kazman. WebQuery: Searching and visualizing the Web through connectivity. Proc. 6th WWW Conf., 1997. J. Kleinberg. Authoritative sources in a hyperlinked environment. J. of the ACM , 1999, to appear. Also appears as IBM Research Report RJ 10076 91892 May 1997. K. Bartz, V. Murthi, and S. Sebastian. Logistic regression and collaborative filtering for sponsoreed search term recommendation. In Second Workshop on Sponsored Search Auctions, 2006. M. Sahami and T. Heilman. A web-based kernel function for matching short text snippets. In International Conference on Machine Learning, 2005. Mori Junichiro, Matsuo Yutaka, Ishizuka Mitsuru, Faltings Boi. Keyword extraction from the Web for Personal Metadata Annotation.Proceedings of the4th International Workshop on Knowledge Markup and Semantic Annotation, (ISWC2004) (2004), pp. 51-60. P. D. Turney, Learning Algorithms for Keyphrase Extraction, Information Retrieval, 1999. Qiang Yang, Advertising keyword suggestion based on concept hierarchy presented by Qiang Yang, HongKong Univ of Science and Technology. S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine.Proc. 7th WWW Conf.,1998. S. Chakrabarti and B. Dom, and P. Indyk. Enhanced hypertext classication using hyperlinks. Proc. ACM SIGMOD, 1998. S. R. Kumar, P. Raghavan, S. Rajagopalan, and A.Tomkins. Trawling emerging cyber-communities automatically. Proc. 8th WWW Conf., 1999. Soumen Chakrabarti, Data mining for hypertext : A tutorial survey. Volume 1. ACM- 2000. Vibhanshu Abhishek , Kartik Hosanagar, Keyword generation for search engine advertising using semantic similarity between terms, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA. Wen-Tau Yih, Joshua Goodman and Vitor Carvalho, Finding Advertising Keywords on Web Pages WWW-06 (The 15th International World Wide Web Conference), June 2006. Y. MATSUO,M. Ishizuka.Keyword Extraction from a Single Document using Word Co-occurrence Statistical Information.International Journal on Artificial Intelligence Tools.2003. Yasin Uzun. Keyword Extraction Using Naive Bayes. Bilkent University, Department of Computer Science, Turkey. Yi-fang Brook Wu , Quanzhi Li , Razvan Stefan Bot , Xin Chen, Domain-specific keyphrase extraction, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany. Zhu Mengxiao ,Cai Zhi ,Cai Qingsheng.Automatic Keywords Extraction Of Chinese Document Using Small World Structure. Department of Computer Science, University of Science and Technology of China. Google Adwords Overture SEM Tf,IDF Web_portal Website: Website: WordNet Công cụ và dữ liệu sử dụng MSN search engine logs. (supported by DAIS Lab, University of Illinois at Urbarna Champaign). Trang web Tiếng Việt: ếng_Việt/ Nguyen Cam Tu, “JvnTextPro: A Java-based VietNamese Text Processing Toolkit”. Website : Website: Website: Website: Website: Website: Từ điển tiếng Việt được lọc từ các trang của

Các file đính kèm theo tài liệu này:

  • docBài toán trích xuất từ khoá cho trang web áp dụng phương pháp phân tích thẻ html và đồ thị web.doc