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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Chu Anh Minh BÀI TỐN TRÍCH XUẤT TỪ KHỐ CHO TRANG WEB ÁP DỤNG PHƯƠNG PHÁP PHÂN TÍCH THẺ HTML VÀ ĐỒ THỊ WEB KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Chu Anh Minh BÀI TỐN TRÍCH XUẤT TỪ KHỐ CHO TRANG WEB ÁP DỤNG PHƯƠNG PHÁP PHÂN TÍCH THẺ HTML VÀ ĐỒ THỊ WEB KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin Cán bộ hướng dẫn: Th.S Nguyễn Thị Hậu Cán bộ đồng hướng dẫn: CN. Trần Mai Vũ HÀ NỘI - 2009 Lời cảm ơn Trước tiên, tơi xin gửi lời cảm ơn và lịng biết ơn sâu sắc đến Th.s Nguyễn Thị Hậu và CN. Trần Mai Vũ, người đã tận tình chỉ bảo hướng dẫn tơi trong suốt quá trình thực hiện khố luận tốt nghiệp. Tơi xin bày tỏ lời cảm ơn sâu sắc đến các thầy cơ giáo đã giảng dạy tơi trong suốt bốn năm học qua, đã cho tơi nhiều kiến thức quý báu để tơi vững bước trên con đường học tập của mình. Tơi xin gửi lời cảm ơn chân thành tới các anh chị, các bạn trong nhĩm seminar về khai phá dữ liệu đã nhiệt tình giúp đỡ tơi trong quá trình tham gia nghiên cứu khoa học và làm khố luận tốt nghiệp. Tơi xin gửi lời cảm ơn tới các bạn trong lớp K50CA, và K50CHTTT đã ủng hộ khuyến khích tơi trong suốt quá trình học tập tại trường. Và cuối cùng, tơi xin bày tỏ niềm biết ơn vơ hạn tới bố mẹ, chị tơi, và những người bạn thân luơn bên cạnh, động viên tơi trong suốt quá trình thực hiện khố luận tốt nghiệp. Hà Nội, ngày 12 tháng 05 năm 2009 Sinh Viên Chu Anh Minh TĨM TẮT NỘI DUNG Trích xuất từ khố cho trang web là một bài tốn mở rộng của bài tốn trích xuất từ khố cho một văn bản. Ở mức cao hơn, nĩ là một bài tốn con trong hệ thống trích xuất thơng tin (Information Retrieval). Trong nhiều năm qua, bài tố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 tốn trích xuất từ khố 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ừ khố 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 khố luận tốt nghiệp này, tác giả đã đề xuất mơ hình giải quyết bài tốn trên dựa vào các phương pháp: độ quan trọng các thẻ HTML, đồ thị web. Ngồ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 Bảng các kí hiệu và chữ viết tắt Kí hiệu Diễn giải HTML HyperText Markup Language IR Information Retrieval SE Search Engine SEM Search Engine Marketing SEO Search Engine Optimization TF Term Frequency IDF Inverse Document Frequency URL Uniform Resource Locator W3C World Wide Web Consortium WWW World Wide Web Danh mục hình vẽ Hình 1. Minh họa các quảng cáo của doanh nghiệp trên máy tìm kiếm 9 Hình 2. Top từ khĩa của baomoi.com 10 Hình 3. Top từ khĩa của flickr.com 10 Hình 4. Từ khĩa được trích xuất từ phần tĩm tắt bài báo của trang web baomoi.com 11 Hình 5. Hình minh họa kết quả sinh từ khĩa của trang web 17 Hình 6. Mơ tả đồ thị web 25 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 25 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 25 Hình 9. Mơ hình đề xuất cho tồn hệ thống 28 Hình 10. Mơ hình mơ đun sinh từ khĩa 30 Hình 11. Mơ hình mơ đun sinh từ khĩa áp dụng độ quan trọng thẻ HTML 32 Hình 12. Mơ hình mơ đun sinh từ khĩa dựa trên phương pháp đồ thị web 33 Hình 13. Mơ hình mơ đun sinh từ khĩa dựa trên log 34 Hình 14. Mơ hình mơ đun sinh từ khĩa dựa trên từ điển hỗ trợ 35 Hình 15. Mơ hình mơ đun tổng hợp từ khĩa 36 Hình 16. Thư mục Tiếng_Việt của dmoz 38 Hình 17. Các liên kết cần lấy về trong các thư mục 39 Danh mục các bảng biểu Bảng 1. Bảng trọng số các thẻ HTML trongTextNet 21 Bảng 2. Bảng các thẻ HTML quan trọng khác 22 Bảng 3. Ví dụ về các trường trong querylog của MSN 26 Bảng 4. Cấu hình phần cứng trong thực nghiệm của bài tốn 36 Bảng 5. Các gĩi của chương trình 36 Bảng 6. Các lớp của gĩi general 37 Bảng 7. Các lớp của gĩi methods 37 Bảng 8. Các lớp của gĩi SELink 37 Bảng 9. Danh sách các phần mềm, mã nguồn sử dụng 38 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 40 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ử 44 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ừ khố và tìm những trang cĩ chứa từ khố 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ừ khố 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 tốn trích xuất từ khố cho trang web. Nhiệm vụ bài tốn đặt ra là cần tìm được một tập các từ khố sao cho các từ khố 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 tố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ừ khố để 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ẻ 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ừ khố 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ừ khố mà ngay cả chủ trang web cĩ thể thiếu xĩt. Với thực tế nêu trên, khố luận đã đề xuất một phương pháp giải quyết bài tốn trích xuất từ khố cho trang web tiếng Việt và tiếng Anh qua đề tài “Bài tố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 tốn sinh từ khố 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. Ngồ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ừ khố của chính người quản trị thì tập từ khố sinh ra là khá đầy đủ và chính xác. Ngồi phần MỞ ĐẦU và KẾT LUẬN, kết cấu của khố luận bao gồm các chương sau: - Chương 1: Giới thiệu về bài tốn. Nêu các khái niệm cơ bản về bài tốn. Các ứng dụng của bài tốn. Những thách thức đặt ra cho bài tố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 tố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 tố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ả. Chương 1. Giới thiệu bài tốn trích xuất từ khố cho trang web 1.1. Đặt vấn đề Sự phát triển nhanh chĩng của Internet và đặc biệt là sự bùng nổ World Wide Web (WWW) - cịn gọi tắt là web - làm cho thơng tin ngày càng lớn, khĩ kiểm sốt, và trùng lặp nhiều. Tìm kiếm thơng tin hiện nay càng là nhu cầu thiết yếu của nhiều người trên nhiều lĩnh vực khác nhau. Sự đột phá về cơng nghệ đã cho ra những máy tìm kiếm phần nào đã giải quyết được sự ngập lụt thơng tin này. Vì nhu cầu sử dụng máy tìm kiếm hiện nay là rất lớn, nên nĩ cũng được sự quan tâm của các doanh nghiệp nhằm dựa vào máy tìm kiếm để quảng cáo sản phẩm của mình qua các từ khĩa[26][2][36]. Đĩ cũng là động lực chính để phát triển bài tốn sinh từ khĩa cho trang web. Việc sinh từ khĩa cho trang web khơng những chỉ cĩ ý nghĩa trong các máy tìm kiếm, mà hiện nay nĩ cịn cĩ nhiều ứng dụng hơn trong các trang web tổng hợp thơng tin khác như các blog, báo điện tử, tìm ảnh, tìm phim, thư viện sách.... Với mỗi trang web, các từ khĩa của trang đĩ sẽ là những sự gợi ý rất tốt cho người dùng để tìm thấy những thơng tin khác liên quan mà họ cĩ thể đang quan tâm. Trong nhiều năm qua, bài tốn trích xuất từ khĩa đã được quan tâm, chú ý nhiều trong các hội nghị khoa học [26] [30] [28] [27] [11][25], và các doanh nghiệp kinh doanh, cũng như những người quản trị web với chiến dịch quảng bá web của mình (SEO: Search Engine Optimization) [4]. Những bài báo, luận văn trước chủ yếu làm trên miền văn bản. Cịn đối với miền trang web thì khá phức tạp, tốn nhiều thời gian; nhiều phương pháp phải cần đến tập huấn luyện. Các từ khĩa là các từ, cụm từ nhằm miêu tả nội dung của trang web, văn bản một cách ngắn gọn nhất, chính xác nhất. Các từ khĩa phải khơng quá chung chung hay khơng quá xa lạ đối với người sử dụng. Bài tốn trích xuất từ khĩa cho trang web là việc áp dụng các phương pháp khác nhau xử lý nội tại trang web, hay các thơng tin liên quan đến trang web để tìm ra được tập từ khĩa đại diện cho chúng [24][29]. Chính những sự áp dụng rộng rãi và nhu cầu thực tiễn của bài tốn đã là động lực để khĩa luận tập trung nghiên cứu về bài tốn sinh từ khĩa cho trang web. Khĩa luận cũng đề xuất mơ hình bài tốn sinh từ khĩa dựa trên hai phương pháp chính là: độ quan trọng của các thẻ HTML, đồ thị web. Bên cạnh đĩ, tơi cũng bổ sung hai phương pháp hỗ trợ việc tìm từ khĩa đĩ là: khai phá query log của máy tìm kiếm, tập từ điển hỗ trợ. 1.2. Khái niệm và các đặc trưng của từ khĩa Từ khĩa là một từ hay một cụm từ dùng để mơ tả một cách chính xác, ngắn gọn nhất nội dung chính của một tài liệu (văn bản, hay các trang web) [20][5][8][18]. Trong tiếng Anh, từ khĩa được thể hiện dưới nhiều thuật ngữ khác nhau như: keywords, term, query term, hay tags; nhưng ý nghĩa của chúng là giống nhau [25]. Trong các tài liệu thì cách viết keywords và tags được sử dụng nhiều nhất. Hiện nay, các trang web chuẩn theo W3C (World Wide Web Consortium) đều cĩ chứa những từ khĩa của trang trong thẻ với thuộc tính “keywords”. Các từ khĩa của các trang web đa số được sinh thủ cơng bởi người quản trị web. Bài tốn trích xuất từ khĩa của tài liệu tiếng Việt và tiếng Anh là một trong những bài tốn cấp thiết trong nghiên cứu xử lý ngơn ngữ tự nhiên cũng như trong cuộc sống hàng ngày. Tập các từ khĩa cĩ thể coi như là một bản tĩm tắt đơn giản nhất của văn bản[25]. Tập các từ khĩa sẽ nĩi lên rõ hơn ý nghĩa của văn bản hay trang web đĩ. Bài tốn trích xuất từ khĩa cho trang web là một quá trình tìm kiếm, nhận dạng, tập các từ, hay cụm từ cĩ ý nghĩa và các từ này cĩ thể đại diện cho trang web đĩ[24][29]. Giải quyết bài tốn này là đưa ra các phương pháp để áp dụng trên các trang web hay các thơng tin liên quan đến trang web để tìm ra các từ khĩa đại diện cho trang web này một cách tự động. Một số đặc điểm, tiêu chí ảnh hưởng [37] đến quá trình rút trích từ khĩa: Từ dừng: Các từ dừng(stopword) khơng nằm trong danh sách các từ khĩa được sinh ra. Các từ dừng là các từ khơng bao hàm ý nghĩa như là các từ: a , an , the, about, with, on ... trong tiếng Anh và các từ : là , sẽ , cùng, tới... trong tiếng Việt. Loại từ: Các từ trong danh sách từ khĩa thường là các động từ, hoặc danh từ. Tuy nhiên, cĩ thể các từ cĩ thể được viết tắt cũng cần xem xét. Các danh từ riêng được coi trọng hơn các danh từ thường. Liên quan đến tiêu đề :Những từ khĩa trong văn bản phải liên quan đến đầu đề văn bản. Số lượng: Tập từ khĩa của một trang web, văn bản là một danh sách các từ khĩa khác nhau, nĩ phù hợp với từng loại văn bản, trang web khác nhau. Thơng thường là 5-10 từ khĩa cho trang web, và 15-20 cho các bài báo... 1.3. Đánh giá các từ khĩa Thường thì các cơng ty, người quản trị trang web đều chắc chắn rằng họ đã biết từ khố lý tưởng nhất. Nhưng thường thì họ sai. Nguyên nhân là do khơng dễ dàng tách một cá nhân ra  khỏi một cơng ty và nhìn nhận với tư cách là một khách hàng tiềm năng. Soạn ra một danh sách các từ khố thì khơng nên bắt buộc phải là một quá trình nội bộ. Mọi người thường rất ngạc nhiên về những từ khố được gợi ý, đơi khi cịn khơng tưởng tượng được hầu hết các khách khơng nĩi cùng một ngơn ngữ với họ. Một khi đã cĩ được một danh sách từ khĩa hồn hảo, lúc này là lúc đánh giá từng cụm từ để chọn ra trong danh sách đến những từ khố mà sẽ mang lại cho trang web lượng người vào trang web cao. Mặc dù rất nhiều cá nhân đều đánh giá các cụm từ khố dựa trên số đơng, nhưng một số khía cạnh cần phải cĩ cho các từ khĩa[2]: Tính phổ biến Cho đến nay cách dễ nhất để đánh giá đĩ là tính phổ biến. Các phần mềm như WordTracker đưa ra các con số phổ biến của cụm từ được tìm kiếm dựa vào hoạt động thực tế của SE [2]. Rõ ràng là con số nào cao hơn thì dự kiến sẽ cĩ người vào cao hơn. Tính đặc trưng Khái niệm này trừu tượng hơn là con số thể hiện tính phổ biến nhưng lại quan trọng khơng kém. Ví dụ, giả dụ rằng cĩ thể đạt được thứ hạng cao trên SE nhờ cụm từ khố “insurance companies”. Nhưng nếu doanh nghiệp chỉ kinh doanh trong lĩnh vực bảo hiểm ơ tơ ( auto insurance). Mặc dù từ khố “insurance companies” cĩ tính phổ biến cao hơn từ khố “auto insurance”, nhưng cụm từ khố “insurance companies” sẽ dành cho những người tìm kiếm dịch vụ bảo hiểm nhân thọ, bảo hiểm sức khoẻ và bảo hiểm nhà cửa chứ kết quả cho tìm kiếm bảo hiểm ơ tơ thì lại khơng xuất hiện. Hướng người sử dụng Nhân tố này dựa vào cách nghĩ của số đơng người dùng. Ví dụ, giả dụ một đại lý bất động sản ở Atlanta đang cân nhắc hai từ khĩa đĩ là  "Atlanta real estate listings" và “Atlanta real estate agents”. Hai từ khố này cĩ tính phổ biến tương tự nhau. Chúng cũng cĩ tính đặc trưng riêng, vì nĩ liên hệ mật thiết đến cơng ty. Vậy thì từ nào thì tốt hơn. Nếu nhìn vào động cơ của người sử dụng trong log thì sẽ thấy từ thứ hai sẽ tối ưu hơn. Từ khố thứ hai cho rằng người sử dụng muốn tìm kiếm một đại lý nhiều hơn. 1.4. Thách thức của bài tốn sinh từ khĩa cho trang web Các nghiên cứu trước đây chủ yếu tập trung trên miền trích xuất từ khĩa cho các văn bản hay các bài tốn kiểu tĩm tắt văn bản. Một lợi điểm trong các văn bản là do văn bản chỉ thuần nĩi về một đề tài hay một chủ đề xác định, ít nhiễu. Trong khi đĩ đối với các trang web nĩ là tổng hợp của nhiều thơng tin trên một trang web, cĩ nhiều thơng tin khơng liên quan như: quảng cáo, thực đơn, thơng tin liên quan. Vì vậy, những thách thức của bài tốn trích xuất từ khĩa cho trang web đĩ là nhiễu trên các trang là lớn, nội dung của nhiều trang là khơng tập trung. 1.4.1. Đối với các trang cĩ nội dung tập trung Các trang cĩ nội dung tập trung là các trang mà trong nĩ chứa những nội dung cụ thể về một vấn đề. Nĩi khác đi, khi loại bỏ các phần thơng tin ngồi thì phần cịn lại như một văn bản. Và các kĩ thuật trích xuất từ khĩa đối với văn bản sẽ được áp dụng như tần số từ, vị trí từ trong các đoạn văn, độ tương đồng từ....Các trang cĩ nội dung tập trung như bài báo điện tử, bài viết hướng dẫn, một bài văn...Nĩi chung, việc lọc nhiễu cho các trang này là một điều quan trọng giúp tăng chất lượng của việc trích xuất từ khĩa. Với những bài viết quá dài thì thời gian chạy cũng khá lâu. 1.4.2. Đối với các trang cĩ nội dung tổng hợp Hiện nay, thơng tin ngày càng được cập nhật thường xuyên trong mỗi trang web. Nhu cầu tổng hợp tin tức là rất cần thiết. Các trang web luơn muốn những thơng tin cập nhật sẽ được hiển thị trên trang đầu khi mà người dùng tới trang của họ. Những trang đầu này cịn gọi là các trang chủ. Các trang web portal cũng tương tự [35]. Một trang web portal là một trang đưa ra những thơng tin ở nhiều nguồn khác nhau theo một cách thống nhất. Ngồi thỏa mãn là một cơng cụ tìm kiếm, web portal cung cấp các thơng tin dịch vụ khác như báo tin tức, chứng khốn, giải trí. Ví dụ về các web portal như: AOL, MSN, yahoo, iGoogle. Nếu áp dụng việc trích xuất từ khĩa áp dụng đối với nội dung trong các trang web này sẽ dẫn đến kết quả khơng chính xác. Cần cĩ những phương pháp khác để cĩ thể sinh từ khĩa cho loại trang này, và trong khĩa luận này tơi áp dụng phương pháp dùng đồ thị Web và log hỗ trợ. 1.4.3. Các vấn đề khác Ngày nay, số lượng các trang web trên Internet là rất nhiều. Vì vậy việc kiểm sốt nội dung cũng đã khĩ, chưa kể đến những lỗi trong việc mã hĩa HTML trên trang web. Ngơn ngữ HTML là một ngơn ngữ cĩ cấu trúc chặt chẽ theo chuẩn của W3C, với các luật như thẻ mở, đĩng, hay thẻ đơn. Để cĩ thể phân tích, lấy được những thơng tin trong trang web thì chúng ta cần các trang cĩ mã HTML theo chuẩn. Tuy các trình duyệt cĩ thể bỏ qua các lỗi HTML để thể hiện thị, nhưng những lỗi như vậy làm cho các chương trình xử lý của chúng ta gặp vấn đề về việc phân tích cú pháp, xác định sai các đoạn văn trong trang web. Do tiếng Việt và Tiếng Anh cĩ những cụm từ, nên một số từ khi xuất hiện một mình sẽ khơng cĩ ý nghĩa. Vì vậy, cần phải cĩ một bộ tách từ tốt, nhất là đối với tiếng Việt. Ngồi các lỗi về cấu trúc của HTML, ngay trong nội dung văn bản của các trang web cũng cĩ những lỗi như: viết tiếng Việt khơng dấu, viết sai.... Một số trang web cĩ sử dụng các tên miền miễn phí như : www.dot.tk , www.co.cc ...., cho nên khi trỏ đến các trang của họ thì mã HTML hiển thị lại khơng là mã HTML của trang web thực mà lại là mã HTML của các trang cung cấp tên miền. 1.5. Ứng dụng của từ khĩa trong các lĩnh vực 1.5.1. Vai trị từ khĩa trong máy tìm kiếm 1.5.1.1. Quảng cáo trên máy tìm kiếm Việc ra đời máy tìm kiếm đã giải quyết phần nào nhu cầu về tím kiếm thơng tin trên mạng. Do đĩ, máy tìm kiếm là một cơng cụ khơng thể thiếu cho những người dùng web hiện nay. Chính vì sự phổ biến, và lượng lớn người dùng sử dụng nĩ cho nên quảng cáo trên máy tìm kiếm là một trong những hình thức quảng cáo khá hiệu quả, và cĩ phần nở rộ hơn trong những năm gần đây. Các nhà doanh nghiệp, quản trị của các trang web (webmaster) cần cĩ những chiến lược khác nhau khi quảng cáo trên máy tìm kiếm một cách hiệu quả nhất. Do việc tìm kiếm trên máy tìm kiếm chủ yếu dựa trên từ khố cho nên việc tìm ra những từ khố đại diện cho các trang web để quảng cáo là một trong những nhiệm vụ hàng đầu của các doanh nghiệp, các người quản trị web muốn quảng bá trang web của mình. Các doanh nghiệp này cần đăng kí các từ khố này với các máy tìm kiếm để cĩ thể quảng cáo trang web của mình. Tuy nhiên, cĩ rất nhiều doanh nghiệp khác cũng muốn quảng cáo sản phẩm, và nảy sinh ra trường hợp cạnh tranh những từ khố chung. Trong quá khứ, những nhà quảng cáo thích đặt giá cho những từ khố mà nĩ cĩ xu hướng sinh ra số lượng lớn kết quả trả về, cho nên những từ khố này thường rất đắt. Cĩ một chiến lược khác bằng cách trả giá cho những từ khố khác liên quan cho ít kết quả hơn khi máy tìm kiếm trả về, nhưng nĩ vẫn cĩ tầm quan trọng và nĩi lên được cái ẩn, nội dung mà người quảng cáo muốn hướng tới. Do đĩ, nĩ vừa cĩ hiệu quả, lại vừa cĩ giá đầu tư cho từ khĩa là rẻ, ít cạnh tranh nhưng vẫn đảm bảo tính chất phổ biến, nhưng nổi trội của doanh nghiệp quảng cáo. Tìm kiếm cĩ tài trợ hay Marketing trên máy tìm kiếm(SEM)[33] là một cách thức quảng cáo khá phổ biến trên web hiện nay, nĩ cũng chính là thu nhập chính của các máy tìm kiếm. Các cỗ máy tìm kiếm thường thu thập một lượng thơng tin khổng lồ về các sở thích và hành vi của người sử dụng trong quá trình vận hành của chúng. Những thơng tin này, bên cạnh việc hỗ trợ cho việc nâng cấp các máy tìm kiếm để trả về kết quả phù hợp hơn, cịn cĩ thể được bán cho các cơng ty khác. Những cơng ty mua các thơng tin này cĩ thể sử dụng chúng để biết được những sản phẩm người tiêu dùng đang quan tâm hoặc tiên đốn nhu cầu của người tiêu dùng trong tương lai. Các từ khố sẽ làm nhiệm vụ quan trọng là gợi ý ra những tài liệu liên quan và những tài liệu liên quan này cũng cĩ từ khố đĩ. Nguồn thu từ quảng cáo trực tuyến của các máy tìm kiếm rất lớn. Ví dụ năm 2004, Google thu về 3 tỉ Đơ la Mỹ từ quảng cáo [2]. Cĩ hai cách quảng cáo trực tiếp trên máy tìm kiếm: - Cách thứ 1 là khách hàng trả tiền cho những từ khố để đảm bảo rằng trang web của họ nằm ở thứ hạng cao trong danh sách trả về của máy tìm kiếm (pay for placement.). Cách làm này thường bị nĩi là khơng cơng bằng khi máy tìm kiểm cố tình cho các kết quả cĩ tài trợ được thứ hạng cao. Cách này cũng ít được áp dụng do các máy tìm kiếm cần đảm bảo được sự cơng bằng của chính thuật tốn của máy tìm kiếm trả về. - Cách thứ 2 được áp dụng phổ biến hơn. Các máy tìm kiểm chia trang tìm kiếm trả về làm 2 phần như hình Hình 1, một phần là kết quả trả về chính xác mà máy tìm kiếm tìm thấy trong hệ thống các trang web đã crawl về, một phần là phần dành cho các trang web cĩ tài trợ. Với các trang web hiển thị ở phần này, các máy tìm kiếm áp dụng chiến lược trả tiền khi người dùng click. Cĩ nghĩa là các quảng cáo sẽ phải trả tiền cho máy tìm kiếm khi người dùng search trong máy tìm kiếm và click vào quảng cáo. Một trường hợp tự nhiên đĩ là hiện nay cĩ nhiều doanh nghiệp với nhiều mặt hàng là giống nhau, và đều muốn cạnh tranh với nhau. Khi quảng cáo trên máy tìm kiếm, các từ khố cĩ thể sẽ trùng nhau, và các doanh nghiệp đều muốn sở hữu từ khố đĩ vì những từ khố đĩ là phổ biến và quan trọng. Do đĩ, máy tìm kiếm sẽ cĩ quá trình đấu giá cho từ khố. Đối với mỗi từ khố, doanh nghiệp nào trả giá cho từ khố cao hơn sẽ được đứng ở vị trí đầu. Hình 1. Minh họa các quảng cáo của doanh nghiệp trên máy tìm kiếm 1.5.1.2. Hoạt động quảng bá web trong máy tìm kiếm Tối ưu hĩa cơng cụ tìm kiếm, hay SEO (viết tắt của search engine optimization), là một tập hợp các phương pháp nhằm nâng cao thứ hạng của một website trong các trang kết quả của các cơng cụ tìm kiếm và cĩ thể được coi là một tiểu lĩnh vực của tiếp thị qua cơng cụ tìm kiếm[4]. Một trong những các phương pháp trong quá trình SEO là việc tìm từ khĩa cho các trang web. Từ khĩa là những từ, cụm từ mà những người truy cập nhập vào trong những cỗ máy tìm kiếm để tìm thấy thơng tin từ những trang web. Điều quan trọng hàng đầu của các người quản trị web là các trang web của họ cĩ được những cỗ máy tìm kiếm tốt xếp hạng những từ khĩa phổ biến liên quan đến đề tài của trang web của họ khơng. Những từ khĩa đúng quan trọng với thành cơng của những hoạt động SEO của những người quản trị web. Sẽ khơng phải là giải pháp tốt khi tối ưu hĩa những trang Web cho những từ khĩa mà khơng ai sử dụng trong những cỗ máy tìm kiếm. Hơn nữa, để cĩ thêm những người dùng quan tâm đến trang web, những từ khĩa khơng được rộng quá hoặc chung quá[2]. Những từ khĩa nào là những từ khĩa đúng cho một trang web? Chìa khĩa ở đây là phải chọn ra những từ khĩa phổ thơng, nhưng khơng được quá chung chung để tránh nhận phải hàng triệu kết quả tìm kiếm. Tìm ra được những từ khĩa đặc biệt đáp ứng được địi hỏi trên sẽ giúp cho trang web đạt được thứ hạng cao trong danh sách tìm kiếm và cĩ thêm nhiều người dùng truy cập vào. Bước đầu tiên trong việc chọn đúng những từ khĩa là phải làm cho chúng trở nên đặc biệt [2][36]. Sử dụng những mệnh đề từ khĩa gồm cĩ hai tới bốn từ. Tránh những từ khĩa quá cạnh tranh với các trang web nổi tiếng khác. Đặc biệt (càng đặc biệt càng tốt nhưng khơng nên quá xa lạ đối với người dùng). Để một chiến dịch tiếp thị trực tuyến thành cơng, cần phải chọn được những từ khĩa đúng, phù hợp. Những từ khĩa sử dụng cần phải thích hợp với trang web đĩ và những người truy cập cần phải đang tìm kiếm những từ khĩa đĩ. Tuy nhiên, những từ khĩa của người dùng nhiều lúc lại khơng giống như những từ khĩa mà người quản trị web nghĩ. Đa số mọi người sử dụng hai tới bốn từ hoặc mệnh đề trong một sự tìm kiếm, vì vậy những mệnh đề rất cĩ hiệu quả. Những từ đơn khơng thể được quảng bá cĩ hiệu quả. Chẳng hạn, ít cĩ người tìm kiếm “free download software” mà chỉ nhập vào cĩ mỗi từ “soft”. Tránh những mệnh đề từ khĩa đại chúng nhất bởi vì rất dễ phải đua tranh với hàng triệu trang web khác cho một sự chú ý của cỗ máy tìm kiếm. Thật là khơng thực tế để tin rằng một trang web mới cĩ thể xếp hạng số một trên một mệnh đề đại chúng, ví dụ “Mp3” hay “báo điện tử”. Rõ ràng, các cơng ty được thành lập và tham gia vào internet vài năm sẽ cĩ lợi thế lớn nhờ tính phổ biến. 1.5.3. Vai trị từ khĩa trong các trang web tổng hợp thơng tin Một động lực khác để phát triển bài tốn trích xuất từ khố cho trang web đĩ là từ khố giúp phân loại các văn bản theo định nghĩa của người dùng dưới dạng chủ đề cho phép dễ dàng truy câp và tìm thơng tin trên đĩ. Nĩ cịn giúp việc liên kết mỗi tài liệu liên quan đến nhau (cross-link) một cách linh động, và giảm thời gian để tìm kiếm cho thơng tin giống với nội dung trang đang xem. Ví dụ như trong Hình 2, Hình 3 là những từ khố hàng đầu của 2 trang baomoi.com (tiếng Việt) và Flickr(tiếng Anh). Hình 2. Top từ khĩa của baomoi.com Hình 3. Top từ khĩa của flickr.com Tại một thời điểm nào đĩ, nếu người dùng truy cập, xem nhiều những trang mà cĩ chung những từ khố, vì vậy top từ khố sẽ nĩi lên được xu thế của người dùng. Những từ khĩa hay được người dùng sử dụng chính là những chủ đề mà người dùng hiện tại đang quan tâm. Và khi người khác truy cập vào trang web, họ cĩ thể khám phá, đọc, xem những trang được coi là mới nhất hiện nay. Những từ khĩa này giúp cho người dùng nắm bắt thơng tin mới theo cách khái quát, theo chủ đề xác định. Trong khi người dùng đọc, xem các trang web, “những điều gì họ sẽ quan tâm tiếp theo ?” là một câu hỏi được nhiều nhà quản trị các trang web tổng hợp thơng tin hướng tới nhằm thoả mãn nhu cầu tối đa của người dùng. Và từ khố là một trong những giải pháp khá hiệu quả và thành cơng. Mỗi một trang web người dùng khi đọc sẽ hiện ra những từ khố liên quan đến bài viết đĩ. Những từ khố này nĩi lên phần nào được nội dung trang web mà người dùng đang đọc. Với những từ khố này, người dùng cĩ thể tìm những bài liên quan đến trang họ đang đọc qua các từ khố. Ví dụ như trong Hình 4, người đọc quan tâm đến buổi duyệt binh của nước Nga vào ngày 9/5, những từ khố liên quan sẽ được gợi ý cho người dùng qua nội dung bài viết hiện tại, như người dùng cĩ thể xem các bài viết liên quan đến phát xít, duyệt binh, hồng quân, thủ tướng Nga, tổng thống Nga, Nga.... Hình 4. Từ khĩa được trích xuất từ phần tĩm tắt bài báo của trang web baomoi.com Ngồi các ứng dụng hướng đến sự quan tâm người dùng, các từ khố cịn cĩ một ứng dụng khác trong việc phân cụm các trang web theo chính các từ khĩa. Mỗi trang web cĩ một tập các từ khĩa riêng, các từ khĩa này cĩ thể trùng với các từ khĩa của các trang web khác. Do đĩ, một từ khĩa như là một thư mục chứa các trang web liên quan, cĩ từ khĩa chính là tên của thư mục đĩ. Một trang web cĩ nhiều từ khĩa, cho nên một trang web cĩ thể thuộc nhiều thư mục khác nhau. Chính sự tự nhiên này của các từ khĩa, nên nĩ cĩ tác dụng làm cho việc tìm kiếm nhanh hơn, hiệu quả hơn, làm cho việc lưu trữ trở nên cĩ cấu trúc hơn. Mạng xã hội cũng đang phát triển rất nhanh, thu hút được nhiều sự quan tâm của giới trẻ. Một trong các hình thức của mạng xã hội là blog. Blog là nơi để mọi người viết nhật kí, hay những bài viết chia sẻ kiến thức, hoặc những bài viết về các vấn đề trong xã hội được quan tâm. Những người viết blog cĩ rất nhiều bài viết khác nhau nhưng nhiều bài viết vẫn ở chung một chủ đề. Các blogger ưa thích việc dùng tag để biểu diễn ngắn gọn cho chủ đề một bài viết của họ. Tag ở đây cũng được coi là từ khĩa[25]. Với các tag, người đọc blog sẽ theo dõi được những thơng tin liên quan trong các bài viết trong blog một cách nhanh chĩng. Và các tag này đều do người viết đặt. Ví dụ: khi đọc một bài trong blog về vấn đề máy tính, người dùng cĩ thể tìm những bài viết liên quan đến từ Windows, lập trình, …Người đọc cĩ thể sẽ tìm thấy những thơng tin mà họ thích. Các từ khĩa cũng là một trong các phương thức để mọi người khám phá trang web đĩ. 1.6. Tổng kết chương Chương này tơi đã trình bày những khái niệm của từ khĩa, và bài tốn trích xuất từ khĩa cho trang web, thách thức của nĩ trong các tài liệu web. Và qua đây, chúng ta cũng thấy được tầm quan trọng của việc sinh từ khĩa trên các lĩnh vực khác nhau. Chương II, khĩa luận xin trình bày một số cơng trình khoa học cĩ liên quan đến bài tốn này. Chương 2. Các cơng trình liên quan 2.1. Các phương pháp trích xuất từ khĩa cho văn bản Trích xuất từ khố cho trang web là một bài tốn được cụ thể hĩa một phần từ bài tốn trích xuất thơng tin (IR: Information Retrieval). Đã cĩ các nghiên cứu khác nhau về bài tốn trích xuất từ khố một cách tự động. Mà đặc biệt với bài tốn tĩm tắt văn bản là một trong những bài tốn gần giống với bài tốn này. Mục tiêu của bài tốn trích xuất từ khĩa là tìm ra những từ khố miêu tả được nội dung của văn bản, trang web bằng cách áp dụng các phương pháp khác nhau dựa trên các đặc điểm của văn bản, web. Tuy nhiên, miền áp dụng của bài tốn tĩm tắt văn bản là trên các văn bản thơng thường. Một số phương pháp trong bài tốn tĩm tắt văn bản cũng cĩ thể áp dụng cho bài tốn trích xuất từ khĩa cho văn bản. Các lý thuyết, phương pháp được áp dụng khá đa dạng đối với văn bản như : sử dụng tần số (tfxidf), học máy nạve bayes, cây quyết định, co-occurrence, độ tương đồng từ khĩa, các kĩ thuật khác trong bài tốn tĩm tắt văn bản... Sau đây là phần giới thiệu một số phương pháp. 2.1.1. Phương pháp tần số từ Phương pháp tần suất xuất hiện của từ được giới thiệu bởi Luhn vào năm 1958[13]. Phương pháp này dựa trên giả thiết: tần số của từ xuất hiện trong các bài báo là một độ đo hữu ích về nghĩa của từ; ví trí tương đối của từ cĩ nghĩa trong phạm vi một câu cũng là độ đo hữu ích về mặt ý nghĩa của từ. Tuy nhiên, cơ sở của phương pháp bị hạn chế do khả năng của máy tính khơng thể biểu hiện được các thơng tin về mặt ngữ nghĩa. Phương pháp này xem xét rằng các từ mà xuất hiện nhiều lần thì sẽ mang tính phổ biến của bài viết, nĩi lên phần nào nội dung của nĩ. Các từ phổ biến này được chọn lựa theo cách sắp xếp từ cao đến thấp theo tần số xuất hiện. Tuy nhiên, theo phương pháp này, thì các dạng khác nhau của từ sẽ được coi như là một từ. Thêm vào đĩ, việc tính tốn tần số của từ sẽ dẫn đến việc các từ cĩ tần số quá cao như các từ dừng. Một cách tự nhiên thì những từ mà cĩ tần số quá cao, hoặc quá thấp cũng khơng quan trọng. Chúng ta cĩ thể tạo lập ngưỡng cho các từ khĩa, cĩ nghĩa là tạo ngưỡng khơng những cho những từ khĩa tần số thấp mà cịn cho những từ cĩ tần số quá cao. Do đĩ, ngưỡng được chấp nhận sẽ nằm trong khoảng [a,b] với a là cận dưới, b là cận trên. Các từ dừng cũng cĩ thể được loại bỏ hiệu quả nhờ một tập từ điển từ dừng. Để tính tần số của từ quan trọng, phương pháp tần số từ tính phân phối của mỗi từ trong tài liệu (tf) và phân phối của từ ở trong corpus (idf - inverted document)[34] idf(keyword) = Trong đĩ : NUMDOC: số tài liệu trong tập corpus NUMDOC(keyword) : chính là số tài liệu mà cĩ từ keyword xuất hiện. Nếu tf(keyword) x idf(keyword) vượt một ngưỡng xác định, các cụm từ khĩa được tìm thấy và được gán trọng số. Những từ nào cĩ trọng số cao thì được chọn. Đối với trang web, cĩ thể áp dụng phương pháp này bằng cách từ địa chỉ trang web cần lấy từ khĩa. Lần theo các liên kết trong trang hạt giống này (seed page) để lấy về các trang web khác và phải thuộc cùng domain[25]. Tập các trang web này tạo nên một tập corpus. Việc tính tốn từ khĩa cho mỗi tài liệu web sẽ được tính theo cơng thức trên dựa vào những đoạn text hiển thị trích ra từ các trang web đĩ. Tuy nhiên, do trang web cĩ nhiều những từ được hiển thị trong một trang khơng cĩ ý nghĩa như : thực đơn, quảng cáo... nhưng lại xuất hiện nhiều lần ở các trang. Vì vậy, các từ xuất hiện trong các mục này lại cĩ tần số xuất hiện cao, và thường vào các từ khĩa. 2.1.2. Phương pháp sử dụng các thơng tin khác trong văn bản Phương pháp tìm từ khĩa dựa vào trích xuất các phần quan trọng của các phần trong văn bản cĩ phần tương tự như phương pháp tĩm tắt của Edmundson [12], dựa vào phương pháp lấy phần quan trọng của văn bản: là các cụm từ gợi ý, từ khĩa, tiêu đề của văn bản, ví trị của câu trong văn bản. Phương pháp tìm từ khĩa cũng sẽ dùng các đặc điểm của văn bản để tìm ra những từ khĩa. Dưới đây là cơ sở của phương pháp: Cụm từ gợi ý trong văn bản Thơng thường các cụm từ gợi ý là liên quan hoặc khơng liên quan tới các câu quan trọng. Ví dụ với các từ “Trong bài báo này”, “Tĩm lại”... thường là phần quan trọng của văn bản. Hoặc những cụm từ khác như “ví dụ” chỉ ra phần khơng quan trọng của văn bản. Tiêu đề của văn bản Người viết khi viết về văn bản của mình thì phải luơn chú trọng đến nội dung, cũng như cách thể hiện tiêu đề sao cho người đọc chỉ cần nhìn qua vào tiêu đề cĩ thể hiểu được nội dung của tồn bộ văn bản. Vì vậy, tiêu đề là cĩ độ quan trọng rất cao trong văn bản. Đã cĩ các bài báo nghiên cứu tĩm tắt văn bản dựa vào độ tương đồng câu dùng câu tiêu đề làm câu mẫu để các câu khác so sánh [1]. Cĩ thể áp dụng phương pháp này trong văn bản web mà đặc biệt là phần văn bản trong thẻ của nguồn HTML của trang web. Việc bám sát vào các câu của tiêu đề văn bản sẽ cho việc tìm nội dung của văn bản, hay trang web sẽ trở nên chính xác hơn. Các câu tiêu đề cĩ thể được coi như là phần tĩm tắt ngắn gọn của văn bản, các từ cĩ nghĩa tương tự, hay những từ lặp lại nhiều trong văn bản trùng với các từ trong tiêu đề thì đều quan trọng. Vị trí của các từ khĩa trong văn bản Thơng thường những từ mà được xuất hiện trong những đoạn đầu tiên trong văn bản thường cĩ độ quan trọng cao hơn các từ mà đứng giữa hay cuối. Do vậy, cĩ thể chọn các từ khĩa mà sao cho nĩ xuất hiện nhiều ở phần mở đầu, nhất là đối với những bài viết dài. Tuy nhiên, một số bài lại cĩ cấu trúc dạng: phần giới thiệu, phần chính, tĩm lại. Các từ ở phần giới thiệu và phần tĩm lại nếu xuất hiện nhiều trong văn bản đều khá quan trọng Tần số từ trong văn bản Các từ xuất hiện thường xuyên trong văn bản cĩ xu hướng chỉ ra chủ đề của văn bản đĩ. Mức độ quan trọng của các từ, cụm từ tính tốn trên cơ sở tần số xuất hiện của chúng trong văn bản. Điểm khác của kĩ thuật tần số này so với tần số bên trên là : tần số từ bên trên xét về một tập các bài, hoặc tập các đoạn văn khác nhau. Cịn đây chỉ là áp dụng trong nội tại của một văn bản. Một mục từ, cụm từ xuất hiện trong văn bản nhiều hơn một ngưỡng nào đĩ thì được coi là từ quan trọng. Từ những cơ sở trên ta cĩ thể tính được trọng số của một từ khĩa bằng tổ hợp tuyến tính các trọng số nhận được từ các phương pháp trích rút ở trên: weight(K) = Các tham số sẽ được điều chỉnh phù hợp bằng cách thử nghiệm với các dữ liệu khác nhau. 2.1.3. Phương pháp sử dụng học máy KEA [19] và GenEX [9] là hai trình ứng dụng đưa ra một số giải pháp về bài tốn trích xuất từ khĩa (keyword extraction)[28]. Trong khi GenEX dùng giải thuật di truyền thì KEA dùng luật quyết định dựa trên phân lớp Naive Bayes (Nạve Bayes decision rule) trên 2 thuộc tính đĩ là TFxIDF và khoảng cách của từ đến đoạn đầu của văn bản. Một phương pháp khác áp dụng dựa trên chuỗi từ vựng (lexical chain), áp dụng từ điển WordNet và bài tốn phân lớp để giải quyết bài tốn sinh từ khĩa này. 2.1.3.1. Trích xuất từ khĩa sử dụng phân lớp Nạve Bayes Trong bài báo [28]Yasin Uzun sử dụng phân lớp Nạve Bayes để áp dụng vào bài tốn này. Ơng cho rằng bài tốn này cĩ thể coi là một vấn đề trong học máy. Cĩ các từ ở trong văn bản và mục đích là nhận ra một từ cĩ phải thuộc lớp từ khĩa( keywords) hay là một từ thơng thường(ordinary words). Như các mơ hình học máy khác, mơ hình này cũng sử dụng tập huấn luyện để học cách sao để nhận ra một từ là từ khĩa hay khơng. Dựa vào những thơng tin đã nhận được từ quá trình học để nhận biết, tìm ra các từ khĩa từ những văn bản mới đưa vào. Nạve Bayes dựa trên xác suất của các từ để quyết định xem từ đĩ cĩ thỏa mãn ngưỡng là một từ khĩa khơng. Trước hết, văn bản cần được được tách ra thành các token sử dụng các kí hiệu như: dấu cách, xuống dịng, tab, dấu chấm, phẩy,... Những chữ khơng là alpha-beta bị loại bỏ. Tính chỉ số TFxIDF cho các token. Do sử dụng IDF nên các tập dữ liệu phải trong cùng một chủ đề. Để xây dựng được một mơ hình phân lớp để nhận biết được đâu là từ khĩa. Tác giả đã sử dụng các thuộc tính gồm: tần số xuất hiện, vị trí của từ trong văn bản. 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 Trong bài báo năm 2007 [11] Gonenc Ercan, Ilyas Cicekli đã trình bày cách tiếp cận bài tốn theo hướng sử dụng từ điển ngữ nghĩa WordNet [38] kết hợp phân lớp cây quyết định để cĩ thể nhận dạng chính xác từ khĩa. Phương pháp này cĩ sử dụng các quan hệ ngữ nghĩa nhằm nâng cao chất lượng các từ khĩa liên quan. Trích xuất Chuỗi từ vựng là việc đưa ra các quan hệ ngữ nghĩa của câu, văn bản đưa vào. Trong một câu, chuỗi từ vựng sẽ chỉ ra được đâu là động từ, danh từ, trạng từ và các quan hệ đồng nghĩa, trái nghĩa, là (is a), cĩ (has a)...Cơng việc khĩ khăn nhất đĩ chính là xây dựng được một chuỗi từ vựng của văn bản dựa vào từ điển WordNet. WordNet được chọn vì từ điển tiếng Anh này cĩ đầy đủ các thơng tin về các từ trong tiếng Anh như: danh từ, các từ đồng nghĩa, trái nghĩa..... Với các quan hệ ngữ nghĩa này, tác giả xây dựng mơ hình để sinh ra chuỗi từ vựng (lexical chain) tồn bộ văn bản tạo thành một chuỗi từ vựng cĩ cấu tạo giống với WordNet. Nhiều câu phức tạp sẽ sinh ra trường hợp nhầm ngữ nghĩa. Sau khi cĩ được các chuỗi ngữ nghĩa của văn bản cần sinh từ khĩa. Tác giả chọn thuật tốn cây quyết định C4.5 với các thuộc tính là : vị trí xuất hiện đầu tiên, tần số xuất hiện, vị trí xuất hiện cuối cùng, và một thuộc tính lấy từ chuỗi từ vựng đã sinh ra từ văn bản. Bài báo cũng đề xuất ra các trọng số cụ thể cho các quan hệ như đồng nghĩa :10; quan hệ is a: 7. quan hệ has a: 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ừ khố 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ừ khố đơn và cụm từ khố 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ừ khố 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ừ khố 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ừ khố 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ừ khố liên quan tới từ khố 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 tố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ừ khố hạt giống (seed keyword) và tìm ra được những từ khố 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ề tồ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 tố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 tố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 tố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 tố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 tố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 tố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 tố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 tốn sinh từ khĩa. Trước hết, áp dụng phương pháp này vào bài tố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 tố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ố tồ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ố tồ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 ngồ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 tốn HITS), phân tích hành vi người dùng, hỗ trợ bài tố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 tồ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 tố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 tố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 tồn hệ thốngHình 9. Mơ hình đề xuất cho tồ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 tồ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ề tồn bộ các trang web mà trong nĩ cĩ liên kết trỏ đến những trang ta cần sinh từ khố (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. Ngồ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ừ khố. + output: tập các từ khố. 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ừ (tồ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 tồ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ừ khố. Ở mỗi thời điểm ta chọn 1 trang để sinh từ khố. + 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 tồ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 khố. + 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 tố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 tồ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 tồ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 tồ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ừ khố. Ướ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 tốn này. Bài tốn sử dụng hai phương pháp chính là: độ quan trọng các thẻ HTML, đồ thị web. Ngồ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 tốn thực nghiệm Bài tốn trích xuất từ khố 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ừ khố tốt khơng phải là dễ dàng. Những cách sinh từ khố 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ừ khố 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 tố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 tốn Thành phần Chỉ số CPU 1 Pentium IV 2.60 GHz RAM 1GB OS WindowsXP Service Pack 2 Bộ nhớ ngồ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. Ngồ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 tố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 tốn trên các từ khĩa ListKeyword Miêu tả cấu trúc dữ liệu, phép tố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 tố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 tố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 tốn sinh từ khĩa dựa vào tập từ điển cho trước Link_method Cài đặt thuật tố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 Khố 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ừ khố 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 tồ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 tốn duyệt theo chiều sâu, tơi đã thống kê được tồ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, tồ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ừ khố. 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ừ khố. Tiến hành thực nghiệm với tồ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ừ khố đượ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 tố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ừ khố 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 khố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ừ khố 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ừ khố phải mang ý nghĩa cao, nĩi lên được nội dung của trang web. Các từ khố phải là những từ khố 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 tồ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 tố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 tố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 tố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 tố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à hồ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 hồ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 tốn trích xuất từ khĩa cho trang web là bài tố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, Hồ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