Đề tài Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek

Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 1 LỜI CẢM ƠN Em xin bày tỏ lịng kính trọng và biết ơn sâu sắc tới thầy giáo tiến sĩ Hà Quang Thụy và thầy Nguyễn Trí Thành, khoa Cơng nghệ, ĐHQG Hà nội đã hướng dẫn và động viên em rất nhiều trong quá trình làm luận văn. Em xin cảm ơn các Thầy Cơ trong khoa Cơng nghệ, Đại học Quốc Gia Hà Nội, và nhĩm Xemina "Máy tìm kiếm VietSeek" thuộc bộ mơn Các Hệ thống Thơng tin, khoa Cơng nghệ, những người đã giúp đỡ cho em trong suốt quá trình học tập và nghiên cứu. Cuối cùng, em xin bày tỏ lịng biết ơn tới gia đình và các bạn bè đã giúp đỡ, động viên em rất nhiều trong suốt quá trình học tập. Hà Nội ngày 28/05/2003 Sinh viên Đặng Thanh Hải Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 2 TĨM TẮT NỘI DUNG Do kích thước khổng lồ của dữ liệu Web, việc xây dựng cũng như tích hợp các yếu tố khai phá dữ liệu Web vào cơng cụ tìm kiếm trên mạng Internet đang thu hút được sự quan tâm rất lớn của rất nhiều nhà nghiên cứu. Khĩa luận đề cập tới vấn đề cải tiến chất lượng và tốc độ của máy tìm kiếm bằng việc nghiên cứu bài tốn phân lớp trong máy tìm kiếm. Nội dung chính của khĩa luận trình bày cấu trúc cũng như mơ hình hoạt động của modul đánh chỉ mục trong máy tìm kiếm VietSeek, các kỹ thuật cơ bản và các thuật tốn thơng dụng liên quan đến quá trình khai phá dữ liệu Web trong máy tìm kiếm, mà cụ thể là bài tốn phân lớp trang văn bản Web. Đặc biệt khĩa luận tập trung vào giải pháp phân lớp theo phương pháp Bayes thứ nhất. Xuất phát từ cơng thức (3.8) [1], khĩa luận đề xuất các cơng thức (3.15), (3.16) và chứng minh tính đúng đắn của chúng, với giả thiết về tính độc lập của các biến cố. Đi kèm với giải pháp phân lớp Bayes là các đề xuất nhằm giải quyết vấn đề tính ngưỡng cho các lớp. Khĩa luận đã tích hợp thành cơng các đề xuất này vào máy tìm kiếm VietSeek và thu được kết quả rất khả quan. Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 3 PHẦN MỞ ĐẦU Ngày nay sự phát triển vượt bậc của cơng nghệ thơng tin, đặc biệt là sự ra đời và phát triển như vũ bão của mạng Internet đã tạo ra một cuộc cách mạng trong mọi lĩnh vực đời sống xã hội. Cĩ thể nĩi rằng Internet là một thế giới ảo với vơ vàn các thơng tin về mọi mặt của đời sống kinh tế, chính trị, xã hội được trình bày dưới dạng văn bản, hình ảnh, âm thanh,... Internet luơn biến đổi khơng ngừng cả về kích thước lẫn nội dung. Đến nay khơng cĩ một ai biết được chính xác kích thước của Internet là bao nhiêu, cĩ bao nhiêu Website và bao nhiêu trang Web. Bên cạnh đĩ, thơng tin trong chính các trang Web cũng được cập nhật liên tục. Theo kết quả nghiên cứu , hơn 500.000 trang Web trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10 ngày thì 50% các trang trong tên miền đĩ biến mất, nghĩa là địa chỉ URL của nĩ khơng cịn tồn tại nữa [2]. Một điều thực tế là khối lượng dữ liệu tăng lên gấp nhiều lần, nhưng tỷ lệ các thơng tin cĩ ích so với khối lượng dữ liệu đĩ lại giảm đi rất nhiều. Theo thống kê, 99% của thơng tin Web là vơ ích với 99% người dùng Web [2]. Rõ ràng với một khối lượng khổng lồ dữ liệu được lưu trữ trên Internet thì vấn đề tìm kiếm thơng tin cĩ ích đang trở thành một vấn đề nghiên cứu cĩ tính thời sự cao. Người dùng khơng thể tự tìm kiếm địa chỉ trang Web chứa thơng tin mà mình cần, do vậy địi hỏi cần phải cĩ một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ trang Web cĩ nội dung giống với yêu cầu của người tìm kiếm. Hiện nay, trên thế giới cĩ một số máy tìm kiếm thơng dụng như Yahoo, Google, Alvista,...đã được xây dựng và triển khai nhằm đáp ứng nhu cầu tìm kiếm thơng tin của người dùng. Mặc dù đã đáp ứng ứng được phần lớn nhu cầu tìm kiếm thơng tin của người dùng, tuy nhiên hầu hết các máy hiện nay mới chỉ hỗ trợ việc tìm kiếm theo từ khĩa, mà chưa xét đến vấn đề ngữ nghĩa của các từ cần tìm kiếm. Với việc tìm kiếm bằng cách đối sánh các từ khĩa, kết quả tìm kiếm cĩ thể khơng bao gồm tất cả các tài liệu như ý muốn của người dùng (do vấn đề từ đồng nghĩa). Thậm chí các tài liệu tìm thấy cĩ thể khơng liên quan đến yêu cầu của người dùng (do vấn đề từ đa nghĩa). Mặc khác các máy tìm kiếm thơng dụng hiện nay đều chưa cĩ chức năng lưu trữ và phân tích tiểu sử của người dùng, để từ đĩ cĩ khả năng hỗ trợ tốt hơn với từng lớp người dùng. Cụ thể, giả sử chúng ta cĩ các trang Web về các vấn đề Tin học, Thể thao, Kinh tể-Xã hội và Xây dựng...Căn cứ vào nội dung của các tài liệu mà khách Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 4 hàng xem hoặc tải về, sau khi phân lớp chúng ta sẽ biết khách hàng hay tập trung vào nội dung gì, từ đĩ chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà khách hàng quan tâm. Từ những nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài tốn hay, cĩ tính thời sự cao, cần được phát triển và nghiên cứu hiện nay. Đề tài khĩa luận tốt nghiệp ‘Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek (Vinahoo)’ cũng khơng nằm ngồi mục đích trên. Ngồi phần mở đầu và phần kết luận, nội dung của khĩa luận được tổ chức thành 4 chương với nội dung chính như sau: Chương 1, với tên gọi Máy tìm kiếm VietSeek, nhằm mục đích giới thiệu một cách chi tiết cấu trúc cũng như cơ chế hoạt động của các máy tìm kiếm VietSeek. Ngồi ra, phần đầu của chương cịn giới thiệu tổng quát về cấu trúc chung của các máy tìm kiếm đang được sử dụng rộng rãi hiện nay. Chương 2 cĩ tên gọi là Khai phá dữ liệu Web trong máy tìm kiếm. Nội dung chính của chương trình bày các kỹ thuật cơ bản liên quan dến bài tốn khai phá dữ liệu Web trong máy tìm kiếm. Chương 3, tích hợp giải pháp phân lớp trang văn bản vào máy tìm kiếm VietSeek, giới thiệu các thuật tốn điển hình được áp dụng để giải quyết bài tốn phân lớp văn bản. Trong đĩ đặc biệt tập trung vào giải pháp phân lớp theo phương pháp Bayes thứ nhất. Các cơng thức đề xuất (3.15) và (3.16), cùng với quá trình chứng minh tính đúng đắn của chúng được trình bày một cách chi tiết trong chương này. Đi kèm với giải pháp phân lớp Bayes là các đề xuất nhằm giải quyết vấn đề tính ngưỡng cho các lớp. Phần cuối của chương giới thiệu quá trình tích hợp giải pháp phân lớp trang văn bản vào máy tìm kiếm VietSeek. Chương 4 với tựa đề Kết qủa thực nghiệm và đánh giá sẽ giới thiệu các kết quả thực nghiệm thu được khi tiến hành tích hợp giải pháp phân lớp văn bản Web vào máy tìm kiếm VietSeek. Sau đĩ đưa ra các đánh giá về các cơng thức đề xuất dựa trên kết quả thực nghiệm. Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 5 Chương 1. MÁY TÌM KIẾM VIETSEEK 1.1. Giới thiệu máy tìm kiếm VietSeek Hiện nay, trên thế giới cĩ một số máy tìm kiếm thơng dụng như Yahoo, Google, Alvista,...đã được xây dựng và triển khai nhằm đáp ứng nhu cầu tìm kiếm thơng tin ngày càng lớn của người dùng. Máy tìm kiếm là một hệ thống được xây dựng cĩ khả năng tiếp nhận các yêu cầu tìm kiếm từ phía người dùng (thường là một tập các từ khố), phân tích nội dung câu truy vấn và tiến hành tìm kiếm trong cơ sở dữ liệu đã được xây dựng sẵn từ trước. Kết quả trả về cho người sử dụng bởi máy tìm kiếm là tập hợp các trang Web liên quan hoặc cĩ chứa các từ khĩa xuất hiện trong câu truy vấn. Đối với các máy tìm kiếm, vấn đề biểu diễn dữ liệu là rất quan trọng. Biểu diễn các trang Web như thế nào để vừa cĩ khả năng lưu trữ được một số lượng khổng lồ các trang Web, vừa cho phép máy tìm kiếm thực hiện việc tìm kiếm nhanh chĩng và chính xác. Cấu trúc điển hình của một máy tìm kiếm được mơ tả như trong hình (1.0 ) Trong thực tế thì mỗi máy tìm kiếm lại cĩ các sửa đổi riêng theo cách riêng, tuy nhiên về cơ bản vẫn dựa trên các bộ phận được mơ tả trong hình (1.0 ) Kho trang web Bé t×m duyƯt Hình 1.0. Mơ hình cấu trúc hoạt động của máy tìm kiếm Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 6 Bộ dị tìm trang Web (Crawler): Hầu hết các máy tìm kiếm hoạt động dựa vào các bộ dị tìm trang Web, là các chương trình cĩ kích thước nhỏ đảm nhận chức năng cung cấp dữ liệu (các trang web) cho máy tìm kiếm hoạt động. Bộ dị tìm trang Web thực hiện cơng việc duyệt web. Hoạt động của nĩ tương tự như hoạt động của con người khi truy cập web là dựa vào các mối liên kết để đi từ trang web này tới trang web khác. Modul đánh chỉ mục (Indexer) thực hiện việc khảo sát tất cả các từ khĩa trong từng trang web cĩ trong kho trang Web, và ghi lại các địa chỉ URL của các trang web cĩ chứa mỗi từ. Kết quả sinh ra một bảng chỉ mục rất lớn gọi là chỉ mục ngược. Nhờ cĩ bảng chỉ mục này, máy tìm kiếm cung cấp tất cả các địa chỉ URL của các trang web khi cĩ yêu cầu: Khi cho một từ khĩa bất kỳ thì qua bảng chỉ mục, máy tìm kiếm sẽ nhận được tất cả các địa chỉ URL của các trang web cĩ chứa từ khĩa đĩ. Bộ phân tích tập (Collection Analysis Module) hoạt động dựa vào thuộc tính của bộ truy vấn (Query Engine). Ví dụ nếu bộ truy vấn chỉ địi hỏi việc tìm kiếm hạn chế trong một số Website đặc biệt, hoặc giới hạn trong một tên miền thì cơng việc sẽ nhanh và hiệu quả hơn nếu tồn tại một bảng chỉ mục các Website mà trong đĩ mỗi tên miền được gắn với một danh sách các trang Web thuộc miền đĩ. Cơng việc như thế được thực hiện bởi bộ phân tích tập. Bộ truy vấn chịu trách nhiệm nhận các yêu cầu của người sử dụng. Bộ phận này hoạt động thường xuyên dựa vào bảng chỉ mục và thỉnh thoảng dựa vào kho trang Web. Do số lượng các trang web là rất lớn, và trong thực tế thì người sử dụng chỉ đưa vào khoảng một hoặc vài từ khố, cho nên tập kết quả thường rất lớn. Vì vậy bộ xếp hạng (Rangking) cĩ chức năng sắp xếp kết quả thành một danh sách các trang web theo thứ tự giảm dần về độ liên quan (theo máy tìm kiếm) tới vấn đề mà người sử dụng đang quan tâm, và sau đĩ hiển thị danh sách kết quả tìm được cho người sử dụng. VietSeek là một trong số ít các máy tìm kiếm tiếng Việt đã được xây dựng và đưa vào sử dụng hiện nay (như PanVietNam của NetNam, HoaTieu của Vương Quang Khải). VietSeek được phát triển dựa trên ASPSeek, là một phần mềm mã nguồn mở, bởi nhĩm Vinahoo (ban đầu do Bùi Quang Minh thực hiện ) trong khuơn khổ của đề tài QG-02-02 và cơng ty TTVNOnline [7]. Là một máy tìm kiếm trên Internet với tất cả các đặc tính mong muốn từ phía người dùng, VietSeek được viết bằng ngơn ngữ C++, sử dụng thư viện STL, và kết hợp giữa hệ quản trị cơ sở dữ liệu MySQL và các file nhị phân cho mục đích lưu trữ. VietSeek bao gồm ba modul chính: modul đánh chỉ Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 7 mục (indexer), modul tìm kiếm chạy ngầm (search deamon), và modul CGI chạy ở phía người dùng. • Modul đánh chỉ mục Modul này sẽ lần theo các Web site, tải về các trang Web mà nĩ bắt gặp, phân tích và lưu trữ nội dung các trang Web đĩ trong một cấu trúc dữ liệu đặc biệt(một số dữ liệu được lưu trữ trong cơ sỡ dữ liệu MySQL, số cịn lại được lưu trong các file nhị phân được gọi là “file delta” ở thư mục “/usr/local/aspseek/var”). Khi khơng cịn trang Web nào để đánh chỉ số, modul này sẽ sắp xếp các file delta và trộn nội dung trong các file delta vào cơ sỡ dữ liệu MySQL để xây dựng chỉ số ngược. Modul đánh chỉ mục hỗ trợ các giao thức HTTP, HTTPS và cĩ thể phân tích được các tài liệu full text cũng như các tài liệu HTML. Hầu hết các chức năng của modul index đều được điều khiển bởi nội dung file cấu hình “vinaseek.conf”. • Modul tìm kiếm Modul tìm kiếm chạy ngầm để lắng nghe và trả lời các câu truy vấn đến từ modul đầu cuối “s.cgi”. Modul phía người dùng (s.cgi) nhận kết quả tìm kiếm, định dạng và hiện thị kết quả tìm kiếm dưới dạng trang Web. Hình 1.1. Giao diện một trang kết quả tìm kiếm của máy tìm kiếm Vietseek Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 8 1.2. Một số tính chất của máy tìm kiếm VietSeek VietSeek được tối ưu hĩa để cĩ thể làm việc với nhiều Website, và cĩ thể tiến hành tìm kiếm trên hàng triệu trang Web. Người sử dụng cĩ thể yêu cầu VietSeek tìm kiếm các từ, cụm từ, sử dụng các ký tự đại diện cũng như các phép tốn Logic. Dưới đây là một số tính năng của máy tìm kiếm VietSeek: ™ Khả năng đánh chỉ mục và tìm kiếm trên hàng triệu trang tài liệu ™ Kết quả tìm kiếm trả về rất tốt, được sắp xếp theo độ liên quan đến câu truy vấn ™ Khả năng tìm kiếm nâng cao Người sử dụng cĩ thể yêu cầu máy tìm kiếm VietSeek tìm kiếm khơng chỉ một từ mà cĩ thể là một cụm từ. Để tìm kiếm một cụm từ, người dùng chỉ cần thêm dấu mở ngoặc và đĩng ngoặc vào cụm từ đĩ. Ví dụ, ‘many years ago’. Nếu người dùng biết chính xác cụm từ cần tìm, nhưng lại quên một từ trong cụm từ đĩ thì cĩ thể sử dụng dấu (*) để thay thế cụm từ đĩ. Bởi vậy câu truy vấn sẽ là: “many * ago” . Người dùng cĩ thể sử dụng biểu thức tìm kiếm logic để yêu cầu tìm kiếm. Biểu thức logic cĩ thể được kết hợp dựa trên các phép tốn logic như AND, OR, và các dấu ngoặc. Ví dụ, (some OR any) AND (days OR months OR years). Người dùng cũng cĩ thể loại trừ các từ khơng muốn xuất hiện trong kết quả tìm kiếm bằng cách đặt dấu “-“ trước các từ đĩ.Với câu truy vấn dạng này, các trang Web chứa các từ đĩ sẽ bị loại bỏ khỏi kết quả tìm kiếm. Ví dụ: search engine –prorietary Đặc tính tìm kiếm theo khuơn mẫu cho phép tìm các tài liệu chứa các từ phù hợp với khuơn mẫu được xác định trước. Ký tự “?” đại diện cho một ký tự bất kỳ, ký tự “*” đại diện cho một chuỗi các ký tự bất kỳ. Ví dụ, để tìm kiếm tất cả các tài liệu cĩ chứa các từ bắt đầu bằng ‘provider’ ta đánh: provider* VietSeek cho phép người dùng giới hạn việc tìm kiếm trong một vài site cụ thể. Ví dụ để tìm kiếm tất cả các tài liệu cĩ chứa từ ‘bubble’ trong site www.mysite.org người dùng đánh câu truy vấn: bubble site: www.mysite.org bubble site: mysite.org Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 9 bubble –site: mysite.org site: www.fotech.edu.vnn.vn Cuối cùng người sử dụng cĩ thể tiến hành tìm kiếm tất cả các trang Web chứa các liên kết tới các trang Web đặc biệt khác. Ví dụ: link: www.aspseek.org ™ Hỗ trợ các giao thức HTTP,HTTPS,HTTP proxy, FTP proxy ™ Hỗ trợ hai loại tài liệu full text và html ™ Sử dụng đa tuyến Modul đánh chỉ mục tải về các tài liệu từ nhiều Website và modul tìm kiếm cĩ khả năng xử lý nhiều câu truy vấn đồng thời. Đặc điểm này sẽ giúp chúng ta cải thiện tốc độ của modul đánh chỉ mục vì trong trường hợp sử dụng chỉ một luồng, phần lớn thời gian được dành cho việc chờ dữ liệu từ mạng. Nhân tố làm chậm tốc độ của modul đánh chỉ mục chính là việc phải tìm các máy chủ phục vụ tên miền nhiều lần. Để tránh điều này, quá trình tìm kiếm khơng đồng bộ ( việc tìm kiếm DNS được thực hiện bởi một số tiến trình riêng biệt được xác định trước ) và bộ nhớ đệm chứa các ánh xạ từ tên máy sang địa chỉ IP được triển khai trong máy tìm kiếm VietSeek ™ Hỗ trợ các từ dừng ( stopword ) Từ dừng là các từ mà bản thân nĩ khơng cĩ ý nghĩa hồn chỉnh. Ví dụ :’is, are,at,this’. Việc tìm kiếm trên các từ dừng là hồn tồn vơ nghĩa, bởi vậy các từ dừng sẽ bị loại bỏ khỏi câu truy vấn. Các từ dừng cũng bị loại bỏ ra khỏi cơ sở dữ liệu trong suốt quá trình đánh chỉ mục, bởi vậy cơ sỡ dữ liệu sẽ nhỏ hơn và nhanh hơn. Khơng cĩ tập các từ dừng được xây dựng sẵn trong VietSeek, người sử dụng phải xây dựng tập hợp các từ dừng tương ứng với từng ngơn ngữ và lưu vào file. ™ Hỗ trợ việc đốn nhận mã chữ cái Một số máy chủ bị hỏng hoặc do cấu hình sai sẽ khơng cho máy khách biết bộ mã chữ cái của tài liệu mà chúng cung cấp. Nếu người quản trị hệ thống tìm kiếm VietSeek đang đánh chỉ mục các máy chủ này, hay sử dụng VietSeek để đánh chỉ mục Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 10 các máy chủ FTP (giao thức FTP khơng cho biết thơng tin về bộ mã chữ cái), bộ đốn nhận mã chữ cái cĩ thể được sử dụng để giải quyết điều này. Bộ đốn nhận sẽ sử dụng các bảng chứa tần số các từ ( được gọi là ‘langmaps’ ) để tìm ra tập chữ cái đúng. ™ Hỗ trợ việc sử dụng “robots” của các máy chủ phục vụ Web Máy tìm kiếm VietSeek sẽ tiến hành kiểm tra một file đặc biệt trong thư mục gốc của mày chủ phục vụ Web cĩ tên là “robots.txt”. Nội dung của file “robots.txt” thơng báo cho máy tìm kiếm VietSeek khơng được thăm một tập hợp các trang Web cụ thể trên máy chủ này. File “robots.txt” sử dụng giao thức “Robots Exclusion Protocol”, giao thức này cho phép người quản trị Website cĩ thể xác định máy tìm kiếm nào khơng được thăm phần nào của site. Giao thức “Robots Exclusion Protocol” được miêu tả như sau: Ví dụ Ý nghĩa User-agent: * Disallow: Dấu (*) cĩ ý nghĩa “bất cứ máy tìm kiếm nào” User-agent: * Disallow: /cgi-bin/ Disallow: /tmp/ Disallow:/private/ Tất cả các máy tìm kiếm cĩ thể thăm tất cả các thư mục ngoại trừ ba thư mục đề cập ở đây User-agent: BadBot Disallow: / Máy tìm kiếm BadBot khơng được phép thăm bất cứ thư mục nào. User-agent: BadBot Disallow: / User-agent:* Disallow : /private/ Riêng máy tìm kiếm BadBot khơng được phép thăm bất cứ thư mục nào cịn tất cả các máy tìm kiếm cịn lại đều cĩ quyền thăm tất cả các thư mục ngoại trừ thư mục “private” ™ Cĩ thể điều khiển việc sử dụng độ rộng băng thơng mạng Nhà quản trị hệ thống VietSeek cĩ thể điều khiển độ rộng băng thơng mạng để modul đánh chỉ mục sử dụng. Chính xác nhà quản trị máy tìm kiếm VietSeek cĩ thể giới hạn độ rộng băng thơng (số byte trên một giây ) được sử dụng bởi modul đánh chỉ mục trong một ngày xác định. ™ Hỗ trợ chế độ đánh chỉ mục khơng đồng bộ theo thời gian thực Một số máy tìm kiếm yêu cầu việc tìm kiếm phải dừng lại trong suốt thời gian cập nhật cơ sở dữ liệu. VietSeek khơng yêu cầu điều này bằng cách hỗ trợ chế độ thời Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 11 gian thực cho modul đánh chỉ mục. Trong chế độ thời gian thực chúng ta sử dụng một cơ sở dữ liệu giống hệt cơ sở dữ liệu ban đầu để lưu trữ nỗi dung đã được đánh chỉ số ngược của các trang Web. Tính năng này sẽ rất cĩ ích khi tiến hành xây dựng một máy tìm kiếm chuyên biệt cho các trang Web cĩ nội dung thay đổi liên tục ví dụ như các trang tin trực tuyến. Chú ý rằng số lượng tài liệu trong cơ sở dữ liệu thời gian thực bị giới hạn vào khoảng 1000 tài liệu. Nếu cĩ càng nhiều tài liệu trong cơ sở dữ liệu thời gian thực thì tốc độ index vào cơ sở dữ liệu chính sẽ càng bị chậm. ™ Sắp xếp kết quả trả về theo độ liên qua hoặc theo ngày tháng Các máy tìm kiếm thường trả về các kết quả liên quan nhất trước tiên. Nhưng nếu muốn tìm kiếm các trang mới nhất, người dùng cĩ thể yêu cầu VietSeek sắp xếp kết quả trả về theo thời gian thay đổi gần đây nhất, do đĩ các trang Web bị thay đổi gần đây nhất sẽ được trình bày đầu tiên. ™ Chắt lọc nội dung và tơ sáng các từ trong câu truy vấn khi trình bày kết quả tìm kiếm Với VietSeek người dùng cĩ thể tùy biến độ dài nội dung tổng quát cho các tài liệu. Mỗi tài liệu tìm thấy đều được đi kèm với một liên kết tới cơ sở dữ liệu của VietSeek. VietSeek lưu trữ một bản sao được nén của các tài liệu đã được xử lý, do đĩ người dùng cĩ thể xem tồn bộ nội dung của trang Web cả trong trường hợp các trang Web đĩ đã bị loại bỏ khỏi Website. ™ Khả năng nhĩm các kết quả theo site ™ Hỗ trợ các trang Web nhân bản (clone- origin) ™ Hỗ trợ tìm kiếm tiếng Việt Tính năng này được phát triển bởi Bùi Quang Minh, bằng việc cài đặt thêm một số thuật tốn nhận dạng các chuẩn tiếng Việt và chuyển tất cả các chuẩn đĩ về cùng chuẩn UNICODE 1.3. Cấu trúc máy tìm kiếm VietSeek Như đã trình bày ở trên, vấn đề biểu diễn dữ liệu trong máy tìm kiếm là rất quan trọng. Biểu diễn các trang Web như thế nào để vừa cĩ khả năng lưu trữ được một số lượng khổng lồ các trang Web, vừa cho phép máy tìm kiếm thực hiện việc tìm Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 12 kiếm nhanh chĩng và chính xác. Đối với máy tìm kiếm VietSeek, dữ liệu được tổ chức, lưu trữ trong cơ sở dữ liệu MySQL và hệ thống file nhị phân xác định. 1.3.1. Cơ sở dữ liệu sử dụng trong máy tìm kiếm VietSeek • Bảng wordurl: chứa các thơng tin về mỗi từ khĩa Tên trường Miêu tả word bản thân các từ khĩa,khơng phải từ dừng word_id Số định danh của từ(khĩa chính) urls Thơng tin về các site và các url mà từ khĩa này xuất hiện.Trường này sẽ rỗng nếu như kích thước của nĩ lớn hơn 1000 byte, trong trường hợp này thơng tin sẽ được lưu trữ trong các file nhị phân. urlcount Số lượng các url cĩ chứa từ khĩa này totalcount Tổng số lần xuất hiện của từ khĩa này trong tất cả các tài liệu mà nĩ xuất hiện Trong đĩ trường wordurl.urls và wordurl1.urls cĩ cấu trúc dữ liệu như sau: Địa chỉ tương đối Độ dài Miêu tả 0 4 Địa chỉ tương đối của vùng thơng tin URL cho site thứ nhất 4 4 Số định danh của site thứ nhất cĩ chứa từ khĩa này 8 4 Địa chỉ tương đối của vùng thơng tin URL cho site thứ hai 12 4 Số định danh của site thứ hai cĩ chứa từ khĩa này ....... .... ...................................................... (N-1)*8 4 Địa chỉ tương đối của vùng thơng tin URL cho site thứ N (N-1)*8+4 4 Số định danh của site thứ N cĩ chứ từ khĩa này (N-1)*8+12 4 Địa chỉ tương đối của cuối vùng thơng tin URL cho site thứ N. VÙNG THƠNG TIN URL 0 4 URLID của site thứ nhất cĩ chứa từ khĩa 4 2 Số lần xuất hiện của từ khĩa trong URLID này 6 2 Vị trí của lần xuất hiện thứ nhất 8 2 Vị trí của lần xuất hiện thứ hai ..... ... ...... 6+(N-1)*2 2 Vị trí của lần xuất hiện thứ N Lặp lại các thơng tin như trên cho các URL khác cĩ chứa từ khĩa này của site thứ nhất ................... .......................... .......................................... Lặp lại các thơng tin trên cho các URL cĩ chứa từ khĩa này của các site tiếp theo • Bảng urlword Chứa thơng tin về tất cả các URL đã hoặc chưa được đánh chỉ số bởi máy tìm kiếm VietSeek, thỏa mãn một điều kiện đặc biệt nào đĩ Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 13 Tên trường Miêu tả url_id Số định danh của URL site_id Số định danh của site deleted =1 nếu máy chủ trả về lỗi 404 và tùy chọn “deleteBad” được thiết lập, hoặc cĩ thể do file “robots.txt” khơng cho phép được đánh chỉ số trang Web này url Nội dung của chính URL next_index_time Thời điểm tiếp theo cần index, tính theo giây status =Trạng thái HTTP trả về bởi máy chủ hoặc =0 nếu trang Web này chưa được đánh chỉ số crc chuỗi đại diện MD5 của tài liệu last_modified tiêu đề chứa thơng tin về lần thay đổi nội dung gần đây nhất(Last_Modified) được trả về từ máy chủ phục vụ Web etag tiêu đề “Etag” được trả về bởi máy chủ last_index_time thời điểm tiến hành đánh chỉ số cuối cùng referre Số định danh của URL tham chiếu đầu tiên đến trang Web này hops độ sâu của URL trong cây siêu liên kết redir =URLID mới nếu trang Web này bị chuyển hướng nếu khơng sẽ bằng 0 origin =URLID của trang Web ban đầu nếu trang Web này là một bản sao =0 nếu trang Web này khơng phải là bản sao • Bảng urlwordNN (với NN là các số 00,01,...15) Bảng này chứa thơng tin về các URL đang được đánh chỉ số. Số NN của bảng chính là URL_ID mod 16 Tên trường Miêu tả url_id Số định danh của URL deleted =1 nếu máy chủ trả về lỗi 404 và tùy chọn “deleteBad” được thiết lập, hoặc cĩ thể do file “robots.txt” khơng cho phép được đánh chỉ số trang Web này wordcount Số lượng các từ khác nhau trong nội dung đã được đánh chỉ số của URL totalcount Tổng tất cả các từ trong nội dung đã được đánh chỉ số của URL content-type Tiêu đề “Content-Type” được trả về bởi máy chủ charset Bộ chữ cái được sử dụng trong nội dung tài liệu, thơng tin này được lấy từ thẻ META title 128 ký tự đầu tiên trong tiêu đề của trang Web txt 255 ký tự đầu tiên,khơng tính các thẻ HTML, trong nội dung của trang Web docsize Kích thước của tài liệu description 100 ký tự đầu tiên trong phần mơ tả trang Web words Nội dung được nén của các URL hrefs Danh sách đã sắp xếp của các liên kết (URLID) tìm thấy trong phần đã được đánh chỉ số của trang Web này Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 14 1.3.2. Hệ thống file nhị phân được sử dụng trong máy tìm kiếm VietSeek ™ Hệ thống file tạm, delta Để nâng cao tốc độ của quá trình xây dựng cơ sở dữ liệu chỉ mục ngược cho tất cả các từ khĩa trong tồn bộ các trang Web đã được phân tích bởi bộ dị tìm, máy tìm kiếm VietSeek sử dụng hệ thống gồm 100 file nhị phân delta để lưu trữ nội dung đã được phân tích của các trang Web trong mỗi lần thực thi modul đánh chỉ mục. Một trăm file delta (d00,,d99) trong thư mục ‘usr/local/aspseek/var/aspseek12’ được dùng để thu thập các thơng tin về các URL mới hoặc bị thay đổi cho các từ khĩa. Sau khi tải một Url về, nội dung của nĩ sẽ được lưu vào 100 file ‘delta’. Chúng ta xem nội dung của 100 file ‘delta’ như là nội dung mới cần được trộn với nội dung cũ trong trường ‘wordurl.urls’. Để xây dựng chỉ số ngược chúng ta sẽ dùng nội dung của 100 file ‘delta’ để cập nhật nội dung trường ‘urls’ của bảng ‘wordurl’ cho các từ xuất hiện trong 100 file ‘delta’. File ‘delta’ thứ i sẽ chứa các từ khĩa thỏa mãn điều kiện ‘(word_ID mod 100)=i’. Các file delta cĩ cấu trúc như sau: Địa chỉ tương đối Độ dài Miêu tả 0 4 Site_id 4 8 Url_id 8 2 Số lượng các từ khác nhau trong Url_id này cĩ giá trị “word_id %100” bằng chỉ số của file 10 4 word_id 14 2 Số lần xuất hiện của từ khĩa này trong nội dung xác định bởi Url_id 16 2 Vị trí thứ nhất của từ ........ ........ ........ 16+(N-1)*2 2 Vị trí cuối cùng của từ ----Lặp lại các thơng tin trên cho các từ khĩa tiếp theo, bắt đầu bằng Word_ID---- ................. .................... .......................... ----------Lặp lại các thơng tin trên cho các URL khác, bắt đầu bằng Site_ID------- ........... ........................ ..................................... ™ Hệ thống file lưu trữ chỉ mục ngược Với cơ sở dữ liệu chỉ mục ngược của các từ khĩa được lưu trữ trong cơ sở dữ liệu MySQL, quá trình tìm kiếm sẽ được thực hiện một cách nhanh chĩng. Tuy nhiên, kích thước của cơ sở dữ liệu chỉ mục ngược thường rất lớn và vượt quá khả năng lưu Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 15 trữ của hệ quản trị cơ sở dữ liệu MySQL. Để giải quyết khĩ khăn này, máy tìm kiếm VietSeek sử dụng thêm hệ thống file nhị phân để lưu trữ cơ sở dữ liệu chỉ mục ngược. Với việc sử dụng thêm hệ thống file nhị phân này, máy tìm kiếm VietSeek sẽ cĩ khả năng lưu trữ cơ sở dữ liệu chỉ mục ngược cĩ kích thước khơng giới hạn. Cách thức lưu trữ dữ liệu chỉ số ngược trong máy tìm kiếm VietSeek được điều khiển bởi giá trị tham số CompactStorage. Tùy thuộc vào giá trị của tham số CompactStorage, chúng ta cĩ hai cơ chế lưu trữ như sau: 1. Cơ chế lưu trữ thơng thường Cơ chế này được sử dụng khi giá trị tham số CompactStorage bằng 0. Với cơ chế này, nếu kích thước dữ liệu chỉ số ngược (nội dung trường urlword.urls) tương ứng với một từ khĩa (word_id) nào đĩ lớn hơn 10000 byte, thì nĩ sẽ được lưu trong một file nhị phân cĩ tên trùng với ‘word_id’ của từ khĩa đĩ,và được đặt trong thư mục ‘/usr/local/aspseek/var/aspseek12/wNN, với NN=’word_id’ % 100. 2. Cơ chế lưu trữ CompactStorage Được sử dụng khi giá trị tham số CompactStorage bằng 1. Thay vì lưu trữ nội dung chỉ số ngược (trường “urlword.urls”) của các từ khĩa trong một file nhị phân riêng biệt, modul đánh chỉ mục sẽ kết hợp nội dung tất cả các file nhị phân cĩ trong thư mục ‘/usr/local/aspseek/var/aspseek12/wNN’ vào ba file nhị phân đặc biệt cĩ tên là ‘ind’, ‘urls’ và ‘sites’. Cấu trúc của ban file nhị phân này được mơ tả như hình (1.2): • File ‘ind’: dùng để lưu cấu trúc dữ liệu “WordInd” như sau: struct{ ULONG m_offset; ULONG m_siteCount; ULONG m_urlCount; ULONG m_totalCount; }WordInd; • File ‘sites’: dùng để lưu trữ cấu trúc dữ liệu “SiteInd” như sau: struct{ ULONG m_siteID; ULONG m_offset; }SiteInd; Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 16 • File ‘urls’: dùng để lưu trữ vùng thơng tin về Url trong nội dung của trường ‘urlword.urls’ cho tất cả các từ khĩa, word_id của tất cả các từ khĩa này lập thành một cấp số cộng với cơng sai là d=100. File ‘urls’ cĩ cấu trúc như sau: (Giả sử file nằm trong thư mục “.../wNN”) Địa chỉ tương đối Độ dài Miêu tả 0 4 Url_id trong Site_id1 4 8 Số lần xuất hiện của từ cĩ “word_id”=NN 8 2 Vị trí lần xuất hiện thứ nhất 10 2 Vị trí lần xuất hiện thứ hai ..... ..... .............. 8+(N-1)*2 2 Vị trí lần xuấ hiện cuối cùng của từ Lặp lại các thơng tin như trên cho các Url_ID trong cùng một Site(Site_id1) cĩ chứa từ khĩa “word_id”=NN .............. ............. ........................... Lặp lại các thơng tin trên cho một Site khác(site_id2) cĩ chứa từ khĩa “word_id”=NN ................. .................... .......................... Lặp lại vùng thơng tin URl trên cho từ khĩa cĩ “word_id”=NN+100 ................ .......................... ..................................... • Mối liên hệ giữa ba file nhị phân: IND Site_id Offset ....... Site_id Offset Site_id Offset ..... Site_id Offset ............. Thơng tin về vùng Site của từ cĩ Thơng tin về vùng Site của từ cĩ word_id = NN word_id = NN+100 SITES Url_id Count 1st position .... n th pos ... Url_id Count 1st pos .... n th pos .... Url_id ..... Thơng tin về vùng Url của từ cĩ Thơng tin về vùng Url của từ cĩ word_id = NN word_id = NN+100 URLS Biểu diễn cho từ cĩ word id = NN Biểu diễn cho từ cĩ word id =NN+100 Offset SiteCount UrlCount TotalCount .... ...... ...... ...... Hình 1.2. Mối quan hệ giữa ba file nhị phân trong cơ chế CompactStorage Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 17 ™ File nhị phân ’ ./dev/zero’ Trong quá trình đánh chỉ số các trang Web, máy tìm kiếm VietSeek thường xuyên thêm mới các Url vào bảng ‘urlword’ và ‘urlwordNN”, hoặc xĩa các Url sẵn cĩ trong hai bảng đĩ (chỉ cĩ trong quá trình đánh chỉ mục theo cơ chế ‘CompactStorage’) Do vậy miền khơng gian các ‘Url_id’ hiện được sử dụng trong bảng ‘urlword’ sẽ khơng liên tục. Thơng thường khi thêm mới một Url, máy tìm kiếm VietSeek sử dụng cơ chế tự động tăng khĩa của hệ quản trị cơ sở dữ liệu MySQL. Nếu số lượng các trang Web cần đánh chỉ số là rất lớn (khoảng vài triệu trang) thì việc sử dụng cơ chế tự động tăng khĩa của hệ quản trị cơ sở dữ liệu MySQL sẽ khơng hợp lý, gây ra sữ lãng phí về tài nguyên ‘url_id’ dùng để cấp cho các trang Web. Trong nhiều trường hợp, cĩ thể khơng chèn được các trang Web mới vào cơ sở dữ liệu. VietSeek giải quyết vấn đề trên bằng cách lưu lại tất cả các ulr_id bị đánh dấu xĩa hoặc bị xĩa khỏi bảng urlword(urlwordsNN) trong file nhị phân ‘./dev/zero’. File ‘./dev/zero’ chứa cấu trúc ULONG(4 byte). Mỗi bít trong một ULONG được đánh chỉ số theo thứ tự tăng dần từ phải qua trái. Chỉ số của tất cả các bít trong file nhị phân này tăng liên tục từ trái sang phải trên tất cả các ULONG(4 byte). Cấu trúc và chức năng quản lý tài nguyên urlID của file ’./dev/zero’ theo thứ tự được thể hiện thơng qua lớp CDelMap và CDelMapReuse: Lớp CDelMap class CDelMap { public: ULONG*m_chunks[DELMAP_SIZE];///<Chứanộidungfile“./dev/zero” pthread_mutex_t m_mutex; ///< Mutex để đồng bộ hĩa các thao tác trên m_chunks int m_fd; ///< Số mơ tả file “.../dev/zero” } Trong cấu trúc m_chunks[DELMAP_SIZE] được mơ tả trong hình (1.3), mỗi bít được gán một chỉ số theo một qui tắc thống nhất, bít cĩ chỉ số thứ ‘i’ sẽ đại diện cho ‘Url_id = i’ theo qui tắc sau: Url_id = i sẽ bị đánh dấu xĩa trong bảng ‘urlword’ và bảng urlwordsNN tương ứng nếu giá trị của bít thứ ‘i’ bằng 1. Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 18 Lớp CDelMapReuse Lớp CDelMapReuse được thiết kế để tối ưu việc sử dụng khơng gian “Url_id” để cấp phát cho các trang Web mới. Bằng cách lưu lại và cập nhật giá trị Url_id nhỏ nhất đã bị xĩa trong file nhị phân “./dev/zero”, VietSeek sẽ sử dụng Url_id nhỏ nhất này làm khĩa định danh cho các trang Web được chèn mới, thay vì sử dụng khĩa tự sinh ra do hệ quản trị cơ sở dữ liệu MySQL. class CDelMapReuse { public: int m_file; //< chỉ số mơ tả file “.../dev/zero” Hình 1.3. Cấu trúc biến thành viên DelMap::m chunks Bít 31 .......... Bit 0 Bít 63 ......... Bit 32 .............................................. 215 ULONG (15=DEL_CHUNK_SHIFT –3 –2) Bít 2*(1<<DEL_CHUNK_SHIFT) Bít 2*(1<<DEL_CHUNK_SHIFT)+31 ....... ..................... m_chunks[DELMAP_SIZE] ....... ..................... .... ... ... ... ... .. ... ... ... m_chunks NULL Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 19 long m_length; //< Kích thước dữ liệu trong file “.../dev/zero” ULONG* m_map;//<Bộ đệm chứa nội dung của file ULONG m_urlID; //< Miền [ 0, m_urlID) khơng cĩ Url_id nào bị xĩa hoặc bị đánh dấu xĩa pthread_mutex_t m_mutex; //<mutex dùng để đồng bộ hĩa các thao tác trên bộ đệm ULONG Get(); ///<Lấy giá trị Url_id nhỏ nhất đã bị xĩa, hoặc bị đánh dấu xĩa void Put(ULONG urlID); ///<Thiết lập giá trị bít tương ứng với Url_id bằng 1, cập nhật lại giá trị m_urlID } 1.3.3. Bộ dị tìm trang Web (Crawler) trong máy tìm kiếm VietSeek Bộ dị tìm trang Web là một chượng trình cĩ nhiệm vụ dị tìm và tải về các trang Web mà nĩ bắt gặp trong quá trình hoạt động. Ban đầu, bộ dị tìm trang Web sẽ tải về nội dung của một địa chỉ Url ban đầu (Url hạt nhân), phân tích nội dung Url này qua đĩ tìm ra tất cả các siêu liên kết trỏ tới các trang Web khác. Tất cả các siêu liên kết tìm thấy này sẽ được lưu trữ trong một hàng đợi theo một chiến lược nhất định. Sau khi phân tích xong nội dung một Url, bộ dị tìm trang Web sẽ tiến hành lấy địa chỉ Url đầu tiên trong hàng đợi ra để tiếp tục hoạt động. Quá trình này sẽ được thực hiện cho tới khi thỏa mãn một điều kiện cụ thể nào đĩ hoặc hàng đợi rỗng, tức là khơng cĩ địa chỉ Url nào để tải về. Như vậy cĩ thể kết luận rằng bộ dị tìm trang Web là một chương trình duyệt cây Website theo chiều rộng. Trong máy tìm kiếm VietSeek, bộ dị tìm trang Web cĩ các đặc điểm sau: ™ Danh sách các Url hạt nhân được lấy từ lệnh ‘Server’ trong quá trình tải file cấu hình ‘vinahoo.conf’ ™ Sử dụng hàng đợi (m_queue) cĩ cấu trúc CSitesQueue ™ Mỗi urlID trong hàng đợi được gắn với hai trọng số đánh giá: độ sâu của trang Web trong cây Website và giá trị thời gian đánh chỉ mục tiếp theo (next_index_time) Sơ đồ tổng quát quá trình hoạt động của bộ dị tìm trong máy tìm kiếm VietSeek được trình như hình (1.4): Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 20 • Hàng đợi m_queue Hàng đợi m_queue được khởi tạo với tư cách là một biến thành viên của lớp ‘CMySQLDatabaseI’. Nĩ là một thể hiện của lớp CSiteQueues và cĩ thể được mơ tả bằng hình (1.5): m_first m_last 1 100 m_first m_last 1 100 m_first m_last 1 100 UrlLink Site_id Site_id Site id CSiteUrl m_first m_last Hàng đợi các Url thuộc Site_id m_first m_last m_current m_currentFail Hình 1.5. Cấu trúc hàng đợi m_queue Url id Url id url hạt nhân Tải nội dung file cấu hình ‘vinahoo.conf’ Lưu vào hàng đợi và cơ sở dữ liệu Lấy thơng tin về tài liệu tiếp theo cần đánh chỉ mục Tải trang Web về và tạo chỉ số xuơi và lưu vào 100 file tạm deta d/sách hàng đợi m_queue Hình 1.4. Sơ đồ tổng quát quá trình hoạt động của VietSeek Crawler Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 21 • Chiến lược dị tìm trang Web trong máy tìm kiếm VietSeek Bộ dị tìm trang Web trong máy tìm kiếm VietSeek cĩ hai chiến lược hoạt động dựa trên nguyên tắc lưu trữ các urlID trong hàng đợi ‘ m_queue’. 1. Chiến lược thứ nhất Bộ dị tìm tiến hành dị tìm các trang Web theo độ ưu tiên về giá trị thời gian đánh chỉ mục tiếp theo (next_index_time). Với chiến lược này, các urlID trong hàng đợi m_queue được sắp xếp theo thứ tự tăng dần của giá trị next_index_time. Tại một thời điểm nào đấy, máy tìm kiếm VietSeek sẽ chọn urlID cĩ giá trị next_index_time bé nhất trong tất cả các urlID, đang cần được đánh chỉ mục, là trang Web tiếp theo sẽ được đánh chỉ mục. Đặc trưng của chiến lược phần này cĩ thể được mơ tả thơng qua sơ đồ thuật tốn lấy urlID tiếp theo từ hàng đợi m_queue để tiến hành đánh chỉ mục trong hình (1.6) 2. Chiến lược thứ hai Bộ dị tìm tiến hành dị tìm các trang Web trước tiên theo độ ưu tiên về độ sâu trang Web và sau đĩ theo độ ưu tiên về giá trị thời gian đánh chỉ mục tiếp theo (next_index_time). Trong chiến lược này, các urlID trong hàng đợi m_queue được sắp xếp theo thứ tự tăng dần của giá trị độ sâu trong cây Website. Trong cùng một độ sâu, các urlID lại được sắp xếp theo thứ tự tăng dần của giá trị next_index_time. Tại một thời điểm nào đấy, máy tìm kiếm VietSeek sẽ chọn urlID cĩ giá trị next_index_time bé nhất trong tất cả các urlID thuộc về độ sâu thấp nhất, đang cần được đánh chỉ mục, là trang Web tiếp theo sẽ được đánh chỉ mục. Đặc trưng của chiến lược thứ hai này phần nào cĩ thể được mơ tả thơng qua sơ đồ thuật tốn lấy urlID tiếp theo từ hàng đợi m_queue để tiến hành đánh chỉ mục trong hình 1.7 1.4. Mơ hình hoạt động của máy tìm kiếm VietSeek 1.4.1 Modul đánh chỉ mục các trang Web ™ Mơ hình mức cao(Hình 1.8) ™ Mơ hình mức thấp (Hình 1.9) kết quả DS các sites nếu thay đổi Internet Index File cấu hình CSDL lấy 1 URL 2 3 1 4 Hình 1.8. Mơ hình hoạt động mức cao của modul index Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 22 Tải file cấu hình 1.Khởi tạo biến “Hrefs” 2.Khởi tạo biến “ServerD” 1.Khởi tạo biến “resolverList” 2. Tạo cơ sở dữ liệu nếu chưa tồn tại 3. Lưu nội dung “Hrefs” vào CSDL, hàng đợi Hàng đợi rỗng? Lấy thơng tin tài liệu tiếp theo để đánh chỉ số Tìm thơng tin về Server chứa tài liệu này Nội dung mới khác n/d cũ thơng tin về tài liệu 1.Xĩa nội dung tài liệu trong file delta 2.Đánh dấu xĩa url DomainName Resolving Tải nội dung mới của tài liệu IP Phân tích nội dung mới Đọc và phân tích nội dung cũ từ CSDL Lưu nội dung mới vào CSDL <Một số điều kiện> N 1.Kết hợp nội dung cũ vào nội dung mới và lưu vào file delta Lưu các siêu liên kết tìm thấy vào file nhị phân 010101 File nhị phân Database url Database Database nội dung url_id Internet Request content siêu liên kết Từ vựng Y Y N Y N 1.Xây dựng dữ liệu chỉ số ngược 2.Tính hạng tất cả Wp END Database Hàng đợi Hình 1.9. Mơ hình hoạt động mức thấp của modul index Hàng đợi Bộ đệm từ vựng ResoverList Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 23 BEGIN Số lượng các Site chưa được kết nối trong hàng đợi < numthreads *4 1.Lấy ra tất cả các url trong bảng “urlword” thỏa mãn điều kiện : m_maxtime < ”next_index_time” <= now(), sắp xếp theo thứ tự tăng dần của “next_index_time” và lưu một số lượng nhất định các Url đầu tiên vào hàng đợi CSQLDatabaseI::m_queue 2.Cập nhật giá trị CSQLDatabaseI::m_maxtime 3.numr <= Số lượng các Url được thêm mới vào hàng đợi CSQLDatabaseI::m_queue Y numr > 0 1.Lọc ra các Url thỏa mãn điều kiện “next_index_time”=maxtime 2.Lưu một số lượng nhất định các Url này vào hàng đợi 3.Cập nhật giá trị CSQLDatabaseI::m_maxtime Y Lấy và trả về Url_id đầu tiên trong hàng đợi CSQLDatabaseI::m_queue END Hình 1.6. Chiến lược lấy urlID tiếp theothứ nhất để tiến hành đánh chỉ mục numthreads Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 24 Hình 1.7. Chiến lược lấy urlID tiếp theothứ hai để tiến hành đánh chỉ mục BEGIN (Số lượng các Site chưa được kết nối trong hàng đợi < numthreads *4) AND (m_maxhops < 65536) 1.maxtime <= giá trị “next_index_time” lớn nhất trong tất cả các trang Web cĩ cùng độ sâu bằng m_maxhops, xuất hiện trong hàng đợi Y maxtime < now 1.Lọc ra các Url thỏa mãn điều kiện maxtime<“next_index_time”<=now() và hops=m_maxhops 2.Sắp xếp theo thứ tự tăng dần của “next_index_time” 3.Lưu một số lượng nhất định các Url đầu tiên vào hàng đợi CSQLDatabaseI::m_queue 4.Cập nhật giá trị CSQLDatabaseI::m_maxtime 5. numr <= số lượng các Url được thêm vào hàng đợi Y Lấy và trả về Url_id đầu tiên trong hàng đợi CSQLDatabaseI:: m_queue END 1.Lọc ra các Url thỏa mãn điều kiện “next_index_time”=maxtime và hops = m_maxhops 2.Lưu một số lượng nhất định các Url này vào hàng đợi 3.Cập nhật giá trị CSQLDatabaseI::m_queue numr > 0 Y m_maxhops <=m_maxhops+1 numthreads Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 25 Chương 2. KHAI PHÁ DỮ LIỆU WEB TRONG MÁY TÌM KIẾM 2.1. Quá trình khai phá dữ liệu Web Hệ thống các Website trên Internet được xem như là một trung tâm dịch vụ thơng tin tồn cầu rộng lớn, phân tán một cách rỗng rãi, về mọi mặt của đời sống xã hội như tin tức, quảng cáo, thơng tin khách hàng, quản lý tài chính, giáo dục, chính phủ, thương mại điện tử, và nhiều dịch vụ thơng tin khác. Ngồi ra, nội dung các trang Web cũng bao hàm một tập hợp phong phú, luơn biến đổi khơng ngừng các siêu liên kết, các truy xuất trang Web và các thơng tin sử dụng trang Web. Chính những thơng tin này là nguồn tài nguyên phong phú cho quá trình khai phá dữ liệu (data mining). Tuy nhiên, dựa trên các đặc điểm được trình bày sau đây, chúng ta thấy rằng hệ thống các Website cịn ẩn chứa rất nhiều thách thức cho quá trình khai phá tri thức: ™ Hệ thống trang Web dường như quá lớn để phục vụ một cách cĩ hiệu quả quá trình xây dựng kho dữ liệu (data warehouse), cũng như quá trình khai phá dữ liệu (data mining) Các CSDL truyền thống thường cĩ kích thước khơng lớn lắm và được lưu trữ tập trung ở một nơi. Trong khi đĩ kích thước Web rất lớn, tới hàng terabytes và thay đổi liên tục, khơng những thế cịn phân tán trên rất nhiều máy tính khắp nơi trên thế giới. Một vài nghiên cứu về kích thước của Web đã đưa ra các số liệu như sau: Hiện nay trên Internet cĩ khoảng hơn một tỷ các trang Web được cung cấp cho người sử dụng., giả sử kích thước trung bình của mỗi trang là 5-10Kb thì tổng kích thước của nĩ ít nhất là khoảng 10 terabyte[2]. Cịn tỷ lệ tăng của các trang Web thì thật sự gây ấn tượng. Hai năm gần đây số các trang Web tăng gấp đơi và cịng tiếp tục tăng trong hai năm tới. Nhiều tổ chức và xã hội đặt hầu hết những thơng tin cơng cộng của họ lên Web. Như vậy việc xây dựng một kho dữ liệu (datawarehouse) để lưu trữ, sao chép hay tích hợp các dữ liệu trên Web là gần như khơng thể ™ Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản truyền thống khác Các dữ liệu trong các CSDL truyền thống thì thường là loại dữ liệu đồng nhất (về ngơn ngữ, định dạng,…), cịn dữ liệu Web thì hồn tồn khơng đồng nhất. Ví dụ về Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 26 ngơn ngữ dữ liệu Web bao gồm rất nhiều loại ngơn ngữ khác nhau (Cả ngơn ngữ diễn tả nội dung lẫn ngơn ngữ lập trình), nhiều loại định dạng khác nhau (Text, HTML, PDF, hình ảnh âm thanh,…), nhiều loại từ vựng khác nhau (Địa chỉ Email, các liên kết (links), các mã nén (zipcode), số điện thoại) Nĩi cách khác, trang Web thiếu một cấu trúc thống nhất. Chúng được coi như một thư viện kỹ thuật số rộng lớn, tuy nhiên con số khổng lồ các tài liệu trong thư viện thì khơng được sắp xếp tuân theo một tiêu chuẩn đặc biệt nào, khơng theo phạm trù, tiêu đề, tác giả, số trang hay nội dung,... Điều này là một thử thách rất lớn cho việc tìm kiếm thơng tin cần thiết trong một thư viện như thế. ™ Web là một nguồn tài nguyên thơng tin cĩ độ thay đổi cao Web khơng chỉ cĩ thay đổi về độ lớn mà thơng tin trong chính các trang Web cũng được cập nhật liên tục. Theo kết quả nghiên cứu , hơn 500.000 trang Web trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10 ngày thì 50% các trang trong tên miền đĩ biến mất, nghĩa là địa chỉ URL của nĩ khơng cịn tồn tại nữa[2]. Tin tức, thị trường chứng khốn, các cơng ty quản cáo và trung tâm phục vụ Web thường xuyên cập nhật trang Web của họ. Thêm vào đĩ sự kết nối thơng tin và sự truy cập bản ghi cũng được cập nhật ™ Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng Internet hiện nay được nối với khoảng 50 triệu trạm làm việc, và cộng đồng người dùng vẫn đang nhanh chĩng lan rộng[2]. Mỗi người dùng cĩ nền tảng kiến thức, mối quan tâm, sở thích khác nhau. Nhưng hầu hết người dùng khơng cĩ kiến thức tốt về cấu trúc mạng thơng tin, hoặc khơng ý thức được cơng sức của quá trình tìm kiếm, rất dễ bị "lạc" khi đang "mị mẫm"trong "bĩng tối" của mạng hoặc dễ cảm thấy chán khi tiến hành tìm kiếm mà chỉ nhận những mảng thơng tin khơng mấy hữu ích. ™ Chỉ một phần rất nhỏ của thơng tin trên Web là thực sự hữu ích. Theo thống kê, 99% của thơng tin Web là vơ ích với 99% người dùng Web[2]. mặc dù điều này cĩ thể khơng chính xác, nhưng cĩ một sự thật là mỗi người dùng nhất định chỉ quan tâm đến một phần nhỏ lượng thơng tin trên Web, trong khi phần cịn lại chứa những thơng tin khơng phù hợp với nhu cầu của người dùng lại cĩ thể xuất hiện Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 27 trong kết quả tìm kiếm. Vậy thì ta cần phải khai phá Web như thế nào để nhận được trang web chất lượng cao nhất theo tiêu chuẩn của người dùng? Tất cả những thách thức trên đã thúc đẩy lĩnh vực khai phá dữ liệu Web (web mining) phát triển một cách mãnh mẽ trong những năm gần đây. Hiện nay cĩ rất nhiều máy tìm kiếm dựa trên quá trình đánh chỉ mục các trang Web, chúng được xây dựng và lưu trữ cơ sở dữ liệu chỉ mục ngược của tất cả các từ khĩa nhằm mục đích xác định tập hợp các trang Web cĩ chứa các từ khĩa nhất định. Với những máy tìm kiếm như thế, một người dùng cĩ kinh nghiệm trong quá trình tìm kiếm cĩ thể nhanh chĩng tìm thấy các tài liệu mong muốn bằng cách cung cấp một tập hợp các từ khĩa hoặc cụm từ khĩa. Mặc dù vậy, các máy tìm kiếm dựa trên từ khĩa vẫn cịn một vài thiếu sĩt. Thứ nhất, một chủ đề cĩ thể bao gồm hàng trăm ngàn tài liệu. Do đĩ, một số lượng rất lớn các tài liệu cĩ thể được trả về bởi máy tìm kiếm, tuy nhiên phần lớn các tài liệu đĩ cĩ thể liên quan rất ít hay thậm chí khơng liên quan đến yêu cầu của người dùng. Thứ hai, cĩ thể cĩ nhiều tài liệu thực sự liên quan đến yêu cầu tìm kiếm của người dùng nhưng lại khơng được trả về bởi máy tìm kiếm, bởi vì các tài liệu đĩ khơng chứa các từ khĩa tìm kiếm. Điều này cho thấy rằng, các máy tìm kiếm hiện tại chưa đáp ứng đầy đủ cho quá trình khai phá dữ liệu Web. 2.2. Các nội dung liên quan đến khai phá dữ liệu Web 2.2.1. Khai phá nội dung trang Web (Web Content mining) Quá trình khai phá nội dung trang Web liên quan đến các vấn đề như khai phá chính bản thân nội dung của trang web (text mining) mà khơng tính đến các siêu liên kết, nghiên cứu và xây dựng hệ thống tìm kiếm trang web theo yêu cầu người dùng. Ngồi ra, một cơng việc khơng kém phần quan trọng của quá trình khai phá nội dung trang web là tính hạng các trang web trả về theo kết quả tìm kiếm. 2.2.2. Khai phá cấu trúc của hệ thống các trang web (web structure mining) Là quá trình khám phá ra các thơng tin cĩ ích từ cấu trúc siêu liên kết trong hệ thống các trang web. 2.2.3. Khai phá quá trình sử dụng Web (WebUusage Mining) Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 28 Quá trình này chủ yếu cĩ chức năng lưu trữ và phân tích tiểu sử của người dùng, để từ đĩ cĩ khả năng hỗ trợ tốt hơn với từng loại người dùng. 2.3. Cơ sở dữ liệu Fulltext 2.3.1 Giới thiệu về cơ sở dữ liệu Fulltext Cơ sỡ dữ liệu Fulltext là cơ sở dữ liệu phi cấu trúc mà dữ liệu chứa trong đĩ bao gồm các nội dung text và các thuộc tính về tài liệu văn bản của nội dung đĩ. Dữ liệu trong cơ sở dữ liệu Fulltext thường được tổ chức thành hai phần: phần cơ sở dữ liệu thơng thường quản lý thuộc tính của tài liệu, và phần tập hợp nội dung của các tài liệu được quản lý. Chúng ta cĩ thể hình dung một cơ sở dữ liệu Fulltext được tổ chức như hình (2.2)[6]: Web Mining Web Content Mining Web Structure Mining Web Usage Mining Text Mining Information Retrieval System Hình 2.1. Các nội dung chính của quá trình khai phá dữ liệu Web Cơ sở dữ liệu Fulltext CSDL về thuộc tính tài liệu Tập hợp nội dung các tài liệu Hình 2.2. Mơ hình tổ chức cơ sở dữ liệu Fulltext Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 29 Trong trường hợp phổ biến, nội dung tài liệu được lưu trữ gián tiếp trong cơ sở dữ liệu theo nghĩa hệ thống chỉ quản lý các con trỏ(địa chỉ) trỏ tới các địa chỉ chứa nội dung tài liệu (một ví dụ dễ thấy nhất là mạng Internet, các trang Web thường lưu giữ các địa chỉ tới nơi cĩ lưu nội dung cụ thể). Cịn các con trỏ (địa chỉ) và các thuộc tính khác về nĩ được lưu trữ trực tiếp trong cơ sở dữ liệu bằng hệ quản trị cơ sở dữ liệu cĩ cấu trúc. Nội dung của dữ liệu Fulltext (văn bản) khơng cĩ cấu trúc nội tại, được coi như là một dãy các từ, các dấu ngăn cách. Ngữ nghĩa của văn bản được quyết định dựa trên ngữ nghĩa của các từ mang nghĩa cĩ trong văn bản (các từ này được gọi là từ khĩa) và cách bố trí các từ khĩa đĩ trong văn bản. Do khơng cĩ cấu trúc nên bài tốn “tổ chức theo cấu trúc hồn tồn” các từ khĩa trong văn bản là khơng thích hợp do tính quá phức tạp khi thực hiện điều đĩ. Do đĩ phổ biến hiện hơn người ta sử dụng các phương pháp biểu diễn ngữ nghĩa văn bản thơng qua tập các từ khĩa cĩ trong văn bản đĩ. Phần lớn tri thức của lồi người được lưu trữ bằng cơ sở dữ liệu Fulltext như sách báo, tạp chí, bài viết. Ngày nay do sự phát triển như vũ bào của cơng nghệ thơng tin và mạng Internet, cơ sở dữ liệu nĩi chung và cơ sở dữ liệu Fulltext nĩi riêng đang tăng lên với một tốc độ rất nhanh, vượt ra khỏi sự kiểm sốt của con người. Việc nghiên cứu các phương pháp tổ chức, lưu trữ và biểu diễn cơ sở dữ liệu Fulltext (trang văn bản) đã, đang ,và sẽ là một lĩnh vực cĩ tính thời sự nhằm mục đích nâng cao khả năng khai phá tri thức để từ đĩ đáp ứng được tốt hơn nhu cầu thực tiễn của con người. 2.3.2. Quá trình xử lý từ vựng Là quá trình cần được thực hiện trước khi tiến hành đánh chỉ mục các tài liệu hay trước quá trình chuyển tài liệu sang một mơ hình biểu diễn nào đĩ, nhằm mục đích thu được tất cả các từ đơn cũng như các cụm từ cĩ mặt trong tài liệu. Ngồi ra quá trình này cũng nhằm loại bỏ các siêu dữ liệu và các thành phần cĩ cấu trúc hoặc cĩ chuẩn biểu diễn. Mặc dù đây là một vấn đề dễ hiểu, tuy nhiên trong thực tế chúng ta lại gặp rất nhiều khĩ khăn khi tiến hành phân tích từ vựng đối với các trang văn bản cĩ định dạng PS, PDF,...,và một số lượng lớn các định dạng văn bản khơng được cơng bố. Thơng thường các thẻ gắn với trang HTML cĩ thể được khai thác để ánh xạ tài liệu vào một biểu diễn bán cấu trúc bằng việc để ý tới sự xuất hiện của các từ trong các thành phần đặc biệt của tài liệu. Phương pháp biểu diễn này cho phép trả lời các câu hỏi phức tạp của người dùng như “Tìm các tài liệu cĩ chứa từ dân số trong phần đầu và từ gia đình trong câu tiêu đề?”. Quá trình xây dựng biểu diễn bán cấu trúc từ trang tài liệu HTML về mặt lý thuyết là rất đơn giản, vì các thẻ HTML sẽ cung cấp tất cả các Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 30 thơng tin cĩ cấu trúc. Tuy nhiên, chúng ta phải chú ý rằng mặc dù cấu trúc ngữ pháp của HTML đã được định nghĩa một cách rõ ràng, tuy nhiên hầu hết các trình duyệt Web đều khơng kiểm tra tính đúng đắn về mặt cấu trúc một cách chặt chẽ. Do đĩ bộ phân tích từ vựng phải cĩ khả năng bỏ qua các lỗi cấu trúc và phục hồi lại các thơng tin cĩ ích. Sau khi đã thu được tất cả các từ vựng cĩ mặt trong tài liệu, chúng ta cĩ thể tiến hành chắt lọc nội dung tài liệu và giảm kích thước bộ từ vựng bằng các cách sau: ™ Loại bỏ các dấu câu, các ký tự đặc biệt ™ Chuyển tất cả các ký tự in hoa về dạng chữ thường. ™ Loại bỏ các từ phát sinh, chỉ lưu từ gốc trong số chúng vào bộ từ vựng , ví dụ như: fish, fishes, fisher và fishers ™ Với mỗi từ khĩa, chúng ta sẽ lưu lại các từ phát sinh từ nĩ nhằm nâng cao khả năng tìm kiếm. Ví dụ: fish ==>(fisher, fishes,fishing) ™ Loại bỏ các từ dừng như các giới từ, trạng từ, liên từ. Sau quá trình này, một bộ từ điển các từ khĩa sẽ được tạo ra và cĩ cấu trúc như hình (2.3). Máy tính Security Sách protected DocID Offset 2 57 3 245 2 78 2 83 1 278 1 319 3 142 3 167 DocID=1 DocID=2 DocID=3 Hình 2.3. Cấu trúc chung của một bộ từ điển từ vựng Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 31 2.3.3. Mơ hình khơng gian vector Các trang tài liệu văn bản cĩ thể được biểu diễn một cách đơn giản trong khơng gian vector nhiều chiều, trong đĩ mỗi từ vựng được gắn với một thành phần của vector. Cụ thể, mỗi tài liệu d cĩ thể được biểu diễn như là một chuỗi các từ khĩa: )||,......,2,1( ωωω dd = , trong đĩ |d| là độ dài của tài liệu và ω i là một từ khĩa thứ i trong bộ từ vựng. Một biểu diễn vector của d khi đĩ sẽ được định nghĩa như là một vector Rx V ||∈ , trong đĩ mỗi thành phần x j biểu diễn sự liên quan về mặt thống kê tới sự xuất hiện của từ khĩa thứ j trong tài liệu. Mơ hình biểu diễn vector đơn giản nhất là mơ hình lơgic 0-1, ví dụ { }1,0∈x j sẽ cho chúng ta biết từ khĩa thứ j cĩ xuất hiện trong tài liệu hay khơng. Mơ hình biểu diễn vector thường được đề cập như là cái túi chứa từ khĩa (bag of words) nhằm nhấn mạnh rằng vector biểu diễn tài liệu khơng phụ thuộc vào thứ tự các từ khĩa trong tài liệu. Mặc dù đây là một phương pháp đơn giản, khơng chặt chẽ đối với cơ sở lý thuyết thơng tin, nhưng nhiều hệ thống phân loại và tìm kiếm văn bản trong thực tế đã hoạt động tương đối tốt với mơ hình vector. Chú ý rằng, số lượng các từ khĩa trong tập tất cả các tài liệu thường lớn hơn rất nhiều so với số lượng các từ khác nhau trong một tài liệu cụ thể, |V|>>|d|, bởi vậy biểu diễn vector của tài liệu cĩ xu hướng phân bố rất lỗng trong khơng gian |V| chiều. Đặc tính này cĩ thể được khai thác triệt để cho việc lưu trữ lẫn thiết kế thuật tốn. Mơ hình vector Boolean cĩ thể được mở rộng bằng việc xem xét các trọng số cĩ giá trị cụ thể đi kèm với mỗi từ khĩa trong tài liệu. Lúc này Njx ∈ chính là số lần xuất hiện của từ khĩa thứ j trong tài liệu tương ứng đang xét. Ngồi ra x j cĩ thể được nhân với một hằng số 1/|d| để xây dựng vector tần số xuất hiện (TF) của tất cả từ khĩa trong tài liệu. Cĩ một lược đồ đánh trọng số quan trọng khác nhằm kết hợp tần số xuất hiện của các từ khĩa (trong một tài liệu nhất định) với số đo độ quan trọng của từ khĩa, được gọi là IDF(Inverse Document Frequency)[3]. Với một tập hợp các tài liệu cho trước, IDF sẽ giảm khi số lượng các tài liệu cĩ chứa từ khĩa tăng lên. Do vậy các từ ít xuất hiện trong tập hợp tài liệu cho trước này sẽ được đánh trọng số cao. Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 32 Giả sử { }dddD n,.....,2,1= là tập hợp các trang văn bản cho trước, nij là số lần xuất hiện của từ khĩa ω j trong tài liệu d i và n j là số tài liệu cĩ chứa từ khĩa ω j ít nhất một lần. Khi đĩ[3]: n n IDF d n TF j i ij j ij log || = = Hàm logarit được sử dụng như là hệ số hãm. Trọng số TF-IDF (Salton et al.1983) của từ khĩa ω j trong tài liệu d i cĩ thể được tính theo cơng thức sau: IDFTFx jijij *= hoặc là[3]: IDF IDF TF TF x kdik j ikdik ij ij maxmax * ∈∈ = ωω 2.3.4. Độ gần nhau giữa các tài liệu Chúng ta cĩ thể định nghĩa độ gần nhau của hai tài liệu d và d’ như là một hàm s(d, d’) ∈R. Hàm này sẽ cho phép chúng ta đánh giá độ tương tự của tài liệu so với câu truy v vấn.Với mơ hình khơng gian vector chúng ta sẽ cĩ kết quả như sau[3]: '*'* '* '. '*)',cos()',( . xxxx xx xx xxxxdds === Trong đĩ X, X’ là hai biểu diễn vector tương ứng của các tài liệu d và d’ Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 33 2.3.5. Vấn đề từ đồng nghĩa và đa ngơn ngữ trong mơ hình vector Giải pháp cho vấn đề từ đồng nghĩa và đa ngơn ngữ trong bài tốn khai phá dữ liệu Fulltext được thực hiện bằng cách liệt kê danh sách các từ đồng nghĩa đối với mỗi từ khĩa trong bộ từ điển. Các từ đồng nghĩa được gắn với một trọng số thể hiện sự tương quan về mặt ngữ nghĩa giữa chúng với nhau. Cụ thể, trong một nhĩm các từ đồng nghĩa, mặc dù cùng biểu đạt một nội dung nhưng vì một số từ cĩ thể được sử dụng nhiều hơn các từ khác trong nhĩm, do đĩ vai trị ngữ nghĩa của các từ cĩ thể sẽ khác nhau. Ví dụ: trong nhĩm từ đồng nghĩa (du lịch, du ngoạn, du hành) thì từ du lịch được sử dụng nhiều hơn các từ cịn lại. Sau khi đã phân tích như trên ta cĩ thể biểu diễn hệ số của các từ trong nhĩm từ đồng nghĩa trên như sau: Từ ‘du lịch’ cĩ hệ số = 1.0 Từ ‘du ngoạn’ cĩ hệ số = 0.8 Từ ‘du hành’ cĩ hệ số = 0.7 Từ ‘travel’ cĩ hệ số = 1.0 Từ ‘tour’ cĩ hệ số = 0.9 Việc thống kê các từ đồng nghĩa và đánh giá về hệ số của các từ đồng nghĩa trong nhĩm là một việc khá phức tạp địi hỏi phải cĩ một số kiến thức về ngữ nghĩa của từ trong nhiều thứ tiếng. Vì vậy các nhĩm từ đồng nghĩa trong hệ thống cần phải thơng qua sự đánh giá bởi những nhà ngơn ngữ học. Trong hệ thống tìm kiếm, mỗi từ thuộc câu hỏi đưa vào, việc tìm kiếm sẽ được tiến hành khơng chỉ trên các từ được hỏi mà cịn được tìm kiếm trên tất cả các từ đồng nghĩa với nĩ trong bảng từ đồng nghĩa. Ngồi ra, cách tính các thành phần của vector biểu diễn tài liệu trong bài tốn sử dụng từ đồng nghĩa cũng khác so với cách tính trong bài tốn thơng thường, và được tính theo cách sau: Giả sử trong một nhĩm từ đồng nghĩa gồm : Từ thứ nhất với hệ số là H1 Từ thứ hai với hệ số là H2 ............................... Từ thứ n với hệ số là Hn Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 34 Khi đĩ độ sai khác về nghĩa của từ thứ i so với từ thứ j trong nhĩm trên được tính theo cơng thức sau: Aij = 1 - |Hi-Hj|/ Hj Lúc này tài liệu d sẽ được biểu diễn bằng vector V(d) = (v1, v2, v3,....., vm), trong đĩ vi được tính bằng tần suất của từ khố i trong tài liệu d + ∑ (tần suất của từ đồng nghĩa với từ i) * hệ số (của từ đĩ so với từ i). Với cách biểu diễn này, những từ khơng xuất hiện trong tài liệu vẫn cĩ thể gián tiếp được xem là một thành phần của tài liệu thơng qua tất cả các từ đồng nghĩa với nĩ xuất hiện trong tài liệu. 2.3.6. Chuỗi các từ khĩa Ngồi việc sử dụng các từ khĩa, chúng ta cĩ thể sử dụng các chuỗi từ, đựoc gọi là n-grams, để xây dựng vector biểu diễn cho tài liệu, ví dụ như “machine learning”, “world wide web”. Trong quá trình xây dựng chuỗi các từ, chúng ta sẽ loại bỏ tất cả các từ dừng (stop-word) xuất hiện trong chuỗi đĩ. Điều này cĩ nghĩa là nội dung các chuỗi từ thu được khơng chứa bất cứ từ dừng nào.Ví dụ chuỗi từ “Word for Window” hoặc “winners will be posted at the end of each two-week period” sẽ được thay bằng các chuỗi từ tương ứng như sau: ”Word Window” và “winners posted end two-week period”[1]. Nếu số lần xuất hiện của một chuỗi các từ trong một tài liệu bé hơn một số cho trước, chuỗi từ đĩ cũng sẽ bị loại bỏ. Bằng việc sử dụng chuỗi các từ khĩa để xây dựng biểu diễn vector của tài liệu, chúng ta cĩ thể thu được nhiều tính chất liên quan đến sự kết hợp giữa các từ với nhau. Quá trình xây dựng vector biểu diễn tài liệu cĩ sử dụng chuỗi các từ khĩa được thực hiện từ dưới lên, trong đĩ các chuỗi gồm ‘i’ từ ở bước thứ ‘i’ được xây dựng dựa trên các chuỗi cĩ ‘i-1’ từ ở bước trước đĩ. Quá trình này được mơ tả bởi thuật tốn sau[1]: Input: MinNGramOcc– Số lần xuất hiện nhỏ nhất của các chuỗi từ, N-Grams, trong tập các chuỗi từ kết quả (LargeNGramSet) MaxNGramSize – kích thước tối đa của các chuỗi từ (N-Gram) StopWordSet – tập hợp các từ dừng của một ngơn ngữ xác định Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 35 DocVec – vector biểu diễn tất cả các tài liệu SymVec– vector biểu diễn nội dung các tài liệu trong DocVec Biến phụ: Sym – các từ khĩa trong tài liệu CandNGramMap – ánh xạ từ một chuỗi các từ, N-Gram, vào số lần xuất hiện của nĩ trong tài liệu NGramQueue – hàng đợi chứa “NGramSize” từ cuối cùng (khơng tính từ dừng) Output: LargeNGramSet–tập các chuỗi từ (N-Gram) cĩ số lần xuất hiện >=MinNGramOcc Thuật tốn: (1).LargeNGramSet := tất cả các từ đơn khác từ dừng trong DocVec và số lần xuất hiện >= MinNGramOcc; (2).For NGramSize=2 to MaxNGramSize do{ (3). CandNGramMap=[]; (4). For SymVec=DocVec[1] to DocVec[|DocVec|] do{ (5). NGramQueue=[]; (6). For Sym=SymVec[1] to SymVec[|SymVec|] do{ (7). if(TypeOf(Sym)==word){ (8). if(Sym not in StopWordSet){ (9). if(Sym in LargeNGramSet) { (10). if(|NGramQueue|+1==NGramSize){ (11). if(Concatenated(NGramQueue) in LargeNGramSet){ (12). NGramQueue.Push(Sym); Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 36 (13). CandNGramMap[Concatenated(NGramQueue)]++; (14). NGramQueue.Pop(); (15). }else {NGramQueue.Push(Sym);NGramQueue.Pop();} (16). }else {NGramQueue.Push();} (17). }else{NGramQueue=[];}//xem lại (18). } (19) }else {NGramQueue=[];} (20) } (21).LargeNGramSet+={NGram:CandNGramMap[NGram]>=MinNGramOcc}; (22)} (23).return LargeNGramSet; 2.4. Cơ sở dữ liệu hypertext 2.4.1. Giới thiệu về cơ sở dữ liệu hypertext Hypertext là thuật ngữ được Theodore Nelson đưa ra lần đầu tiên vào năm 1965 tại Hội thảo của Hội tốn học Mỹ ACM lần thứ 20[6]. Theo Nelson thì Hypertext là các tài liệu dạng chữ viết khơng liên tục. Chúng được phân nhánh và cho phép người đọc cĩ thể chọn cách đọc theo ý muốn của mình, tốt nhất là nên đọc nĩ trên các màn hình cĩ khả năng tương tác. Sáng kiến tạo ra một tập hợp các văn bản cùng với con trỏ trỏ tới các văn bản khác nhằm phản ánh mối liên quan giữa các trang văn bản với nhau thực sự là một giải pháp sáng tạo để tổ chức thơng tin. Với người viết cách này cho phép người dùng cĩ thể thoải mái loại bỏ những băn khoăn về thứ tự trình bày những vấn đề liên quan đến nhau để tập trung vào hồn thành các vấn đề nhỏ, và sau đĩ cĩ thể sử dụng các liên kết để chỉ cho người đọc thấy được các vấn đề nhỏ đĩ cĩ mối quan hệ với nhau như thế nào. So sánh với cách đọc tuyến tính, thì Hyperlext đã cung cấp cho chúng ta một giao diện để cĩ thể tiếp xúc với nội dung thơng tin hiệu quả hơn rất nhiều. Một cơ sở dữ liệu Hypertext bao gồm hai thành phần chính sau: Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 37 Hình 2.4. Đồ thị mơ tả cây Website Tài liệu Hypertext: là một tài liệu Text đơn nằm trong một cơ sở dữ liệu Hypertext. Nếu chúng ta tưởng tượng cơ sở dữ liệu Hypertext như một đồ thị thì một tài liệu Text đơn là một nút trong đồ thị[6]. Siêu liên kết (Hyperlink): là một sự kết nối giữa các tài liệu Hypertext với nhau. Các siêu liên kết đĩng vai trị là các cung trong đồ thị cĩ hướng[6]. 2.4.2. Phương pháp biểu diễn trang Web theo mơ hình vector Xuất pháp từ mục tiêu sử dụng phương pháp biểu diễn trang Web bằng vector, cùng với quan điểm sử dụng các thơng tin về liên kết nhằm tăng độ chính xác tìm kiếm cũng như phân lớp các trang Web, chúng ta cĩ bốn cách biểu diễn các trang Web như sau: Hình 2.5. Mơ hình minh họa cho các phương pháp biểu diễn trang Web Trang đang xét (A) a, b, b c, c d, e b, g a, c, f Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 38 ™ Cách biểu diễn thứ nhất: Cách này khơng quan tâm đến bất cứ một liên kết nào cũng như bất cứ một trang láng giềng nào mà chỉ đơn giản biểu diễn nội dung của chính trang Web đĩ. Đây chính là phương pháp biểu diễn vector cho tài liệu Fulltext đã được đề cập ở trên. ™ Cách biểu diễn thứ hai Cách đơn giản nhất để sử dụng thơng tin về các liên kết trong trang Web là kết hợp trang web đĩ với tất cả các trang láng giềng của nĩ để tạo ra một siêu trang (super-document). Nếu sử dụng phương pháp này ta sẽ cĩ vector biểu diễn cho trang web A như sau: a b c d e f g 2 3 3 1 1 1 1 Điểm yếu của phương pháp này là làm lỗng đi nội dung của trang A, và cĩ thể tạo thêm nhiễu cho việc phân lớp. Cách biểu diễn này là sự lựa chọn rất tốt trong trường hợp cần biểu diễn một tập các trang Web cĩ cùng một chủ đề. ™ Cách biểu diễn thứ ba Cấu trúc của vector biểu diễn được chia làm hai phần, phần thứ nhất dùng để biểu diễn các từ xuất hiện trong bản thân trang A, cịn phần thứ hai được dùng để biểu diễn các từ xuất hiện trong tất cả các trang láng giềng của A. Cách biểu diễn này tránh được khả năng các trang láng giềng cĩ thể làm lỗng nội dung của trang A. Theo cách này, trang web A sẽ cĩ vector biểu diễn như sau: a b c d e f g a b c d e f g 1 2 2 0 0 0 0 1 1 1 1 1 1 1 Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 39 ™ Cách biểu diễn thứ tư Chúng ta xây dựng một vector biểu diễn cĩ cấu trúc theo các bước sau: •Xác định bậc cao nhất d của các trang web trong tập tài liệu Hypertext •Xây dựng một vector cấu trúc với d+1 thành phần như sau: ∗Phần đầu biểu diễn cho chính tài liệu A ∗Các phần từ 2 đến d+1 biểu diễn các tài liệu láng giềng của A, mỗi tài liệu được biểu diễn bởi một phần. Phương pháp biểu diễn này cĩ hai khĩ khăn chính sau: ∗Kích thước của vector thường là rất lớn ∗Mỗi trang web cĩ thể cĩ nhiều vector biểu diễn nếu chúng ta hốn đổi thứ tự các phần từ 2 cho đến d+1 2.4.3. Khai thác các siêu liên kết Chúng ta cĩ thể tận dụng cấu trúc liên kết giữa các trang Web với nhau để thu được các thơng tin cĩ ích về tài liệu, mặc dù bản các thơng tin này khơng xuất hiện trong bản thân tài liệu đĩ. Ví dụ như đoạn văn bản cĩ chứa các siêu liên kết thường mơ tả một cách tổng quát nhất nội dung của trang Web được trỏ tới bởi siêu liên kết này. Mặc dù chúng ta khơng cần đọc nội dung của trang Web đích v, nhưng chúng ta cĩ thể biết được nội dung tổng quát của trang Web này thơng qua các đoạn văn bản chứa siêu liên kết tới v trong tất cả các trang Web w là cha của trang Web v. Ví dụ: trong bài tốn tìm kiếm, đoạn văn bản chứa các siêu liên kết này đã được phân tích và khai thác một cách triệt để nhằm đánh giá trang Web đích. ™ Học quan hệ Học quan hệ là một phương pháp tiếp cận thích hợp cho việc khai thác thơng tin cĩ ích từ các cấu trúc siêu liên kết. Với phương pháp này, dữ liệu được xem như tồn tại trong một mối quan hệ nào đĩ, và thuật tốn học cĩ thể khai thác tối đa quan hệ giữa các đối tượng. Đối với tập dữ liệu Web, ngồi các quan hệ được mã hĩa dưới dạng cấu trúc siêu liên kết giữa các trang Web cịn cĩ các quan hệ cục bộ thể hiện tính bán cấu trúc của tài liệu Web thơng qua các thẻ HTML đặc trưng. Năm 1990, Quinlan Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 40 đã đưa ra thuật tốn dựa trên lý thuyết logic vị từ cấp một (FOIL) để giải quyết bài tốn phân tích và khai thác các mối quan hệ trong tập dữ liệu Web. Ví dụ: nếu nội dung của trang Web A cĩ chứa siêu liên kết trỏ tới trang Web B thì chúng ta sẽ biểu diễn mối quan hệ đĩ bằng vị từ Link_to(A, B). Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 41 Chương 3. TÍCH HỢP GIẢI PHÁP PHÂN LỚP TRANG VĂN BẢN VÀO MÁY TÌM KIẾM VIETSEEK 3.1. Bài tốn phân lớp văn bản Phân lớp trang văn bản là quá trình gồm hai bước, với mục đích phân các tài liệu văn bản vào các lớp cố định cĩ sẵn. Trong bước thứ nhất, một mơ hình được xây dựng nhằm miêu tả một tập hợp ban đầu các lớp tài liệu. Mơ hình này được xây dựng bằng cách phân tích nội dung các trang văn bản trong tập dữ liệu huấn luyện. Tập dữ liệu huấn luyện là tập hợp các trang văn bản trong cơ sở dữ liệu đã được gán nhãn từ trước dựa trên sự kết hợp giữa các tri thức chuyên gia với một hay nhiều thuộc tính nào đĩ. Do đĩ giai đoạn thứ nhất thường được đề cập như là việc học cĩ giám sát (Việc học của mơ hình được giám sát thơng qua việc nĩ được cho biết mỗi trang văn bản trong tập huấn luyện thuộc vào lớp nào). Trong bước thứ hai, mơ hình này được sử dụng cho việc phân lớp các trang văn bản chưa được gán nhãn hoặc các tài liệu sẽ xuất hiện trong tương lai. Điều này thực sự rất hữu ích, ví dụ để đốn nội dung của một trang Web, hay quyết định xem nội dung của trang Web đĩ cĩ phù hợp với lĩnh vực của người dùng hay khơng?. Hiện nay cĩ rất nhiều phương pháp được áp dụng vào quá trình phân lớp trang văn bản như [3]: ♦ K người láng giềng gần nhất (K- Nearest Neighbours) ♦ Naive Bayes ♦ Support Vector Machines ♦ Cây quyết định (Decision Tree) ♦ Mang nơron ♦ Phương pháp tìm luất kết hợp Chương này chủ yếu tập trung vào thuật tốn Naive Bayes được áp dụng trong quá trình xây dựng bộ phân lớp trang văn. Phần đầu của chương giới thiệu tổng quát một số thuật tốn thơng dụng được áp dụng hiệu quả trong bài tốn phân lớp trang văn bản. Trong đĩ, đặc biệt tập trung vào việc chứng minh cơng thức phân lớp (3.15) và đề xuất cơng thức phân lớp (3.16) dựa trên thuật tốn Naive Bayes. Ngồi ra cịn đề xuất các thuật tốn ước lượng và làm mịn giá trị ngưỡng cho các lớp trong bài tốn phân lớp. Phần cịn lại của chương đề cập đến các chiến lược đánh giá bộ phân lớp. Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 42 3.2. Thuật tốn K người láng giềng gần nhất (K-Nearst Neighbors) Bộ phân lớp dựa trên thuật tốn K người láng giềng gần nhất là một bộ phân lớp dựa trên bộ nhớ, đơn giản vì nĩ được xây dựng bằng cách lưu trữ tất cả các đối tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ phân lớp sẽ tính khoảng cách từ điểm x đến tất cả các điểm dữ liệu trong tập huấn luyện. Qua đĩ tìm được tập N(x, D, k) gồm k điểm dữ liệu mẫu cĩ khoảng cách đến x là gần nhất. Ví dụ nếu các dữ liệu mẫu được biểu diễn bởi khơng gian vector thì chúng ta cĩ thể sử dụng khoảng cách Euclian để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm đại đa số trong tập N(x, D, k). Mặc dù rất đơn giản, nhưng thuật tốn K người láng giềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế. Để áp dụng thuật tốn k-NN vào tài liệu văn bản, chúng ta cĩ sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức (3.1). Trong đĩ ),,( kDxcN là tập con chỉ chứa các đối tượng thuộc lớp c của tập ),,( kDxN . )1.3(),cos()|( ),,( xxxcScore kDxNcx ′∑= ∈′ Khi đĩ tài liệu x sẽ được phân vào lớp oc nếu: { }CcxcscoreMaxxocscore ∈= ),|()|( 3.3. Bộ phân lớp sử dụng vector hỗ trợ Máy sử dụng vector hỗ trợ (SVM) được giới thiệu bởi Cortes và Vapnik vào năm 1995[3]. SVM thực sự hiệu quả khi giải quyết vấn đề trên dữ liệu cĩ số chiều lớn, ví dụ như biểu diễn vector của các trang tài liệu văn bản. Ban đầu, SVM chỉ được thiết kế để giải quyết các bài tốn phân lớp cĩ số lớp bằng 2, vấn đề phân lớp nhị phân.Giả sử tập dữ liệu huấn luyện được biểu diễn như sau: { }niiyixD ...1),,( == Trong đĩ mRix ∈ và { }1,1−∈iy sẽ xác định điểm dữ liệu ix là ví dụ dương hay ví dụ âm. Khi đĩ bộ phân cách tuyến tính sẽ là một siêu phẳng được định nghĩa như sau: { }00)(: =+= wxTwxfx Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 43 Với mRw ∈ và Rw ∈0 là các hệ số thích nghi, đĩng vai trị như là các tham số biểu diễn mơ hình cho máy phân lớp sử dụng vector hỗ trợ(SVM). Ta cĩ thể định nghĩa một hàm phân lớp nhị phân: )2.3( .0 0)(.1 )( ⎩⎨ ⎧ >= otherwise xfif xh Giai đoạn học của mơ hình này bao gồm việc ước lượng các tham số mRw ∈ và Rw ∈0 từ tập dữ liệu huấn luyện. Một tập dữ liệu huấn luyện được gọi là cĩ thể phân tách tuyến tính nếu tồn tại một siêu phẳng cĩ hàm phân lớp h(x) bền vững với tất cả các nhãn, ví dụ hàm phân lớp đĩ cĩ thể thỏa mãn điều kiện sau đây: niixfiy ..10)(* =∀> . Sử dụng giả thuyết này, Rosenblartt đã chứng minh được rằng thuật tốn lặp đơn giản sau cĩ thể tạo ra siêu phẳng phân cách[3]. ™ Thuật tốn tạo siêu phẳng phân cách: 1. 0←w 2. 00 ←w 3. repeat 4. e ← 0 5. for i ← 1 to n do 6. s ← sgn( )0( wixTwiy + ) 7. if(s < 0) then 8. ixiyww *+← 9. iyww +← 00 10. e ← e+1 11.untill e=0 12.return )0,( ww Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 44 Cĩ thể thấy rằng điều kiện đủ để tập dữ liệu huấn luyện D cĩ thể phân cách tuyến tính được là số lượng các đối tượng dữ liệu trong D, n=|D| phải bé hơn hoặc bằng m+1. Điều kiện này thường đúng với bài tốn phân lớp trang văn bản, nơi cĩ số lượng các từ khĩa rất lớn, khoảng vài ngàn từ, và lớn hơn rất nhiều so với số lượng các đối tượng trong tập huấn luyện. Trong hình (3.1), giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian với cùng một ma trận tương quan, và được tạo ra với cùng một xác suất. Khi đĩ một siêu phẳng phân cách được gọi là lý tưởng nếu nĩ làm cực tiểu hĩa xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng cĩ mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng mà chúng ta xây dựng nhằm phân cách các điểm dữ liệu mẫu cĩ thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đĩ sẽ dẫn tới việc phân lớp khơng tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của khơng gian đầu vào, m. vì với một số lượng các dữ _ _ _ _ _ _ _ _ _ _ _ _ + + + + + + ++ + + + + + + _ Siêu phẳng phân cách lý tưởng Siêu phẳng thực tế Hình 3.1. Mối quan hệ giữa các siêu phẳng phân cách Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 45 liệu mẫu cố định, tập hợp các siêu phẳng thực tế sẽ tăng theo hàm mũ với lũy thừa m. Với bài tốn phân lớp trang văn bản, m thường rất lớn, vào khoảng vài ngàn hay thậm chí là hàng triệu từ. Trên cơ sở lý thuyết học theo xác suất được phát triển bởi Vapnik năm 1998, chúng ta cĩ thể định nghĩa một siêu phẳng phân cách lý tưởng bằng hai đặc tính sau: ™ Là duy nhất đối với mỗi tập dữ liệu huấn luyện cĩ thể phân tách tuyến tính. ™ Xác suất phân lớp sai cho các dữ liệu mới của nĩ là bé nhất so với tất cả các siêu phẳng phân cách khác. Biên giới M của bộ phân lớp được định nghĩa là khoảng cách giữa siêu phẳng phân cách và điểm dữ liệu mẫu gần với nĩ nhất. Như vậy siêu phẳng phân cách lý tưởng là siêu phẳng cĩ biên giới M lớn nhất (Hình 3.2). Cĩ thể thấy rằng khoảng cách từ một điểm dữ liệu x đến siêu phẳng được tính theo cơng thức: )0(|||| 1 wxTw w + . Bởi vậy siêu phẳng phân cách lý tưởng cĩ thể được tìm thấy bằng việc giải quyết bài tốn tối ưu cĩ điều kiện sau: + + + + + + + + + + + + + + MwwTx =+ 0 MwwTx −=+ 0 00 =+ wwTx M w 2 |||| 2 = Hình 3.2. Biên giới của siêu phẳng phân cách Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 46 MMax ww 0, trong đĩ: )3.3(....1,)0(|||| 1 niMwix Twiyw =≥+ Với mỗi siêu phẳng, bao giờ cũng tồn tại một điểm x’ sao cho: |||| 1 |||| )0(|||| 1 ww ConstwxTwiyw M ⇐=+′= Thay vào (3.3) ta cĩ: wwMin ww rr.2 1 0, với )4.3(....1,1)0( niwixTwiy =≥+ Theo Lemma thì nghiệm w& của bài tốn tối ưu (3.4) bao giờ cũng được biểu diễn tuyến tính theo các vector niix ...1= bằng biểu thức[3]: )5.3(0 1 ≥ = = ∑ iixiyin i w αα r& Trong đĩ iα được gọi là các hệ số quyết định Lagrang. Bài tốn tối ưu đối ngẫu với (3.4) cĩ dạng như sau[3]: ∑+∑∑ === − n i i n j jxixjyiyji n i Max 11 . 12 1 ααα α rr trong đĩ )6.3(0,0 1 ≥= = ∑ iiyin i αα Theo lý thuyết đại số tuyến tính thì bài tốn tối ưu (3.4) và (3.6) là tương đương với nhau. Nĩi cách khác nếu α& là nghiệm của bài tốn tối ưu (3.6) thì ⎟⎠ ⎞⎜⎝ ⎛ += = = ∑ posxwnegxwowixiyin i w .. 2 1, 1 &&&r&& α là nghiệm của bài tốn (3.4). Mặt khác bài tốn tối ưu (3.6) là bài tốn bậc hai (quadratic programming), về nguyên tắc cĩ thể giải được bằng các phương pháp tối ưu chuẩn. Khi đĩ vector α& được gọi là vector hỗ trợ (support vector). Mỗi thành phần iα& được gắn với một điểm dữ liệu mẫu ix , thể hiện độ ảnh hưởng của điểm dữ liệu mẫu này tới kết quả của việc phân lớp sau này. Hàm quyết định phân lớp h(x) cĩ thể được tính bằng biểu thức (3.2) hoặc bằng dạng đối ngẫu tương đương (3.7) : Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 47 )7.3( 1 )( ∑ = = n i ixTixiiyxf α Trong trường hợp dữ liệu huấn luyện khơng cĩ khả năng phân cách tuyến tính, phương pháp phân tích này vẫn cĩ khả năng áp dụng bằng cách bổ sung n biến khơng âm iξ , khi đĩ bài tốn tối ưu sẽ được phát biểu lại như sau: ∑ = + n i iC ww wwMin 12 1 0, . ξrr với niiwixTwiy ....1,1)0( =−≥+ ξ và bài tốn đối ngẫu sẽ là: ∑+∑∑ === − n i i n j jxixjyiyji n i Max 11 . 12 1 ααα α rr với điều kiện niCi ...1,0 =≤≤α Việc giải quyết bài tốn tối ưu bậc hai sử dụng các phương pháp chuẩn cĩ độ phức tạp )3(nΟ , với giả thuyết rằng số lượng các vector hỗ trợ tăng tuyến tính với số lượng các đối tượng trong tập dữ liệu huấn luyện. Đây là một vấn đề khĩ khăn của phương pháp SVM. Bộ phân lớp SVM mà chúng ta đang thảo luận chỉ cĩ thể được áp dụng cho các bài tốn phân lớp nhị phân. Với các ứng dụng cĩ số lớp lớn hơn hai, phương pháp tiếp cận truyền thống là tiến hành chuyển bài tốn này thành một số bài tốn phân lớp nhị phân nhỏ hơn, mỗi lớp được biểu diễn bởi một xâu nhị phân. Sau đĩ áp dụng bộ phân lớp SVM nhị phân cho từng nhãn bộ phận. ™ Ví dụ về SVM giải quyết bài tốn cĩ nhiều lớp Tập dữ liệu mẫu huấn luyện: [ ] { }{ }1,12,1,...1),2,1,( −∈== iyiyniiyiyixD A A A D D D D B B B C C C C Lớp Nhãn A B C D (1, 1) (1, -1) (-1, 1) (-1,-1) Hình 3.3. Tập dữ liệu huấn luyện nhiều lớp Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 48 3.4. Bộ phân lớp sử dụng cây quyết định Cây quyết định là một cấu trúc cây giống biểu đồ luồng, trong đĩ mỗi nút trong là một bộ kiểm tra giá trị cho một thuộc tính xác định, mỗi nhánh thể hiện một kết quả của quá trình kiểm tra và mỗi lá đại diện cho các lớp hoặc sự phân bố của lớp. Nút trên cùng của cây là nút gốc. Thuật tốn: Decision_Tree[2] Input: samples: tập dữ liệu huấn luyện attributes_list: tập hợp các thuộc tính Output: Cây quyết định (1)Tạo ra một nút N (2)If (tất cả dữ liệu mẫu trong “samples” đều thuộc lớp C) then (3) Nhãn(N) ← C ; Xác định N là nút lá ; Thốt (4)If(attribute_list rỗng) then (5) Nhãn(N) ← Lớp chiếm đại đa số trong “sample”; Xác định N là nút lá;Thốt (6)test_attribute ←thuộc tính trong “attribute_list” cĩ độ đo InformationGain lớn nhất (7)Nhãn(N) ←”test_attribute” (8)For mỗi giá trị ai của thuộc tính “test_attribute” do (9) Xây dựng một nhánh từ nút N (10) si ← tập các dữ liệu thuộc “samples” cĩ giá trị của thuộc tính “test_attribute”=ai (11) If(si rỗng) then (12) Gắn thêm một nút lá cĩ nhãn là lớp chiếm đại đa số trong “samples” vào cây quyết định (13) else (14) Nút M ← Decision_Tree(si, attribute_list-test_attribute); (15) Gắn thêm nút M vào cây. Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 49 Thuật tốn trên hoạt động theo chiến lược tham lam, xây dựng cây quyết định theo phương pháp đệ quy từ trên xuống dưới. ™ Độ đo Information Gain Độ đo Information Gain được sử dụng để lựa chọn thuộc tính làm nhãn cho mỗi nút trong thuật tốn xây dựng cây quyết định. Nĩ thể hiện khả năng quyết định tới việc phân lớp của các thuộc tính. Thuộc tính cĩ độ đo Information Gain lớn nhất sẽ được chọn làm thuộc tính phục vụ việc kiểm tra (phân hoạch)dữ liệu tại nút hiện thời. Thuộc tính này sẽ làm cực tiểu hĩa lượng thơng tin cần thiết để cĩ thể phân lớp các dữ liệu huấn luyện trong kết quả của quá trình phân hoạch hiện tại. Phương pháp tiếp cận dựa trên lý thuyết thơng tin này sẽ làm cực tiểu hĩa số lần kiểm tra trung bình cần thiết để phân lớp một đối tượng dữ liệu và đảm bảo rằng cây quyết định đơn giản(khơng nhất thiết phải tối ưu) sẽ được tạo ra. Giả sử S là một tập gồm s đối tượng dữ liệu huấn luyện, C là tập hợp các lớp gồm m phần tử khác nhau. Gọi is là số lượng các dữ liệu mẫu trong S thuộc về lớp iC . Khi đĩ lượng thơng tin trung bình cần thiết để phân lớp một dữ liệu mẫu sẽ được tính theo cơng thức (x.y)[2]: ∑ = −= m i ipipmssisI 1 )(2log),......,2,( Trong đĩ ip là xác suất để một đối tượng dữ liệu mẫu thuộc về lớp iC và được ước lượng bởi sis . Ở đây chúng ta sử dụng hàm logarit theo cơ số 2 là vì thơng tin được mã hĩa bằng dãy các bít. Giả sử thuộc tính A cĩ v giá trị phân biệt, { }vaaa ,....,2,1 , và cĩ thể được sử dụng để phân hoạch S thành v tập con, { }vSSS ,.....,2,1 , trong đĩ iS là tập chứa các dữ liệu mẫu cĩ giá trị của thuộc tính A bằng ia . Nếu A được chọn để kiểm tra việc phân hoạch tập dữ liệu mẫu, thì các tập con này sẽ tương ứng với các nhánh được tạo ra từ nút chứa tập S. Gọi ijs là số lượng các mẫu thuộc tập jS cĩ nhãn là iC .Độ đo Entropy, hay lượng thơng tin trung bình, dựa trên sự phân hoạch bởi thuộc tính A được tính theo cơng thức sau[2]: Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 50 ∑ = +++= v j mjsjsIs mjsjsjsAE 1 ),.....,1( ....21)( Đại lượng s mjsjsjs +++ .....21 đĩng vai trị là trọng số của tập con thứ j, chính là số lượng các mẫu trong tập con jS chia cho tổng số các mẫu trong S. Giá trị độ đo Entropy của một thuộc tính càng nhỏ, thì sự phân hoạch tập dữ liệu mẫu theo thuộc tính này càng tốt. Chú ý, với tập con jS cho trước ta cĩ: ∑ = −= m i ijpijpmjsjsjsI 1 )(2log.),.......,2,1( Với || jS ijs ijp = là xác suất để một mẫu trong tập jS thuộc về lớp iC .Khi đĩ độ đo Information Gain của thuộc tính A được tính theo cơng thức sau[2]: Gain(A)= )(),......,2,1( AEmsssI − ™ Ví dụ về cây quyết định Qua quá trình theo dõi việc đi chơi Tennis của một vận động viên, giả sử chúng ta cĩ bảng thống kê như sau (xxx ví dụ phân lớp văn bản: xem luận văn anh Đồn Sơn): Thời tiết Nhiệt độ Độ ẩm(%) Cĩ giĩ? Lớp Cĩ nắng 75 70 đúng Đi chơi Cĩ nắng 80 90 đúng Khơng đi Cĩ nắng 85 85 sai Khơng đi Cĩ nắng 72 95 sai Khơng đi Cĩ nắng 69 70 sai Đi chơi U ám 72 90 đúng Đi chơi U ám 83 78 sai Đi chơi U ám 64 65 đúng Đi chơi U ám 81 75 sai Đi chơi Mưa 71 80 đúng Khơng đi Mưa 65 70 đúng Khơng đi Mưa 75 80 sai Đi chơi Mưa 68 80 sai Đi chơi Mưa 70 96 sai Đi chơi Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 51 Sử dụng thuật tốn xây dựng cây quyết định ở trên chúng ta sẽ cĩ cây quyết định như hình (3.4): Để gán nhãn cho một dữ liệu mới, các giá trị thuộc tính của dữ liệu này sẽ được kiểm tra trên cây quyết định(tiến hành duyệt cây quyết định theo chiều sâu dựa trên giá trị các thuộc tính của dữ liệu). Một đường đi trên cây sẽ được xây dựng từ nút gốc cho đến nút lá. Nhãn của nút lá này chính là lớp được gán cho dữ liệu mới. 3.5. Bộ phân lớp dựa trên thuật tốn Naive Bayes Năm 1998, trong luận án tiến sỹ [ Machine learning on non-homogenous, distributed text data ], Dunja Mladenic đã sử dụng cơng thức (3.8) để tiến hành xây dựng bộ phân lớp dựa trên thuật tốn Naive Bayes: )8.3()()|().( )()|().( )|( ∑ ∏ ∏ ∈ ∈= i dj jTF icjPicP dj jTFcjPcP dcP ω ωω ω ωω Trong phần sau, khĩa luận sẽ tập trung vào việc chứng minh cơng thức phân lớp (3.15) và đưa ra cơng thức đề xuất (3.16), được áp dụng để xây dựng bộ phân lớp dựa trên thuật tốn Naive Bayes. Thời tiết Độ ẩm Cĩ giĩ? Đi chơi U ám MưaNắng Khơng đi Đi chơi Đi chơi Khơng đi <=75 >75 sai đúng Hình 3.4. Cây quyết định Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 52 Khi muốn gán nhãn cho một tài liệu d nào đĩ, bộ phân lớp sẽ tính xác suất cĩ điều kiện của mỗi một lớp c với điều kiện đã cĩ tài liệu d. Theo lý thuyết xác suất Bayes ta cĩ: )9.3()|( )|().,|( ),|( θ θθθ dP cPcdP dcP = Trong đĩ θ là mơ hình tham số của bộ phân lớp mà chúng ta cần phải xây dựng. Tuy nhiên, sự xuất hiện của θ sẽ được ngầm hiểu trong các cơng thức đề cập sau này. Do tập các lớp C lập thành một hệ đầy đủ về xác suất, nên theo cơng thức tính xác suất tồn phần ta cĩ: )10.3()(*)|()( || 1 ∑ = = C i cPcdPdP ii Một cách trực quan ta cĩ thể biểu diễn tài liệu d bằng một tập hợp các từ khĩa xuất hiện trong tài liệu )||,......,2,1( ωωω d , trong đĩ mỗi từ khĩa ω i được gắn với một trọng số ni là số lần xuất hiện của từ khĩa đĩ trong tài liệu d . Theo quan điểm của lý thuyết xác suất tài liệu d được xem là một sự kiện xác suất (biến cố xác suất) với mỗi từ khĩa và số lần xuất hiện của từ khĩa đĩ là những tính chất của nĩ. Như vậy tài liệu d cĩ thể được thay thế tương đưong bằng một tập hợp các tính chất sau: Gọi W i là biến ngẫu nhiên chỉ số lần xuất hiện của từ khĩa ω i và X là biến ngẫu nhiên chỉ số lượng từ khĩa cần dùng để xây dựng tài liệu. Do đĩ ta cĩ: d ⇔ 2. Số lần xuất hiện của )( 1ω = n1 3.Số lần xuất hiện của )( 2 ω =n2 ......................... .............................. |d|+1.Số lần xuất hiện của )( ||ω d = n d || 1.Số lượng từ khĩa =|d| Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 53 )|,....,,|,|()|( ||||2211 cnWnWnWdXPcdP dd ===== Do số lượng từ khĩa cần dùng độc lập xác suất với số lần xuất hiện của tất cả các từ khĩa trong tài liệu cũng như với ngữ nghĩa của tài liệu nên ta cĩ thể viết lại cơng thức trên như sau: )11.3()|,....,,(|).|()|( ||||2211 cnWnWnWPdXPcdP dd ===== Giả sử rằng số lần xuất hiện của các từ khĩa trong tài liệu là độc lập với nhau từng đơi một khi cho biết trước ngữ nghĩa (tên lớp) của các tài liệu. Khi đĩ kết hợp giả thiết này với cơng thức (3.11) chúng ta cĩ: )12.3()|(*...*)|(*)|(*|)|()|( ||||2211 cnWPcnWPcnWPdXPcdP dd ===== Giả thiết rằng xác suất xuất hiện từ khĩa ω i trong một miền ngữ nghĩa cho trước là một hằng số , constciwP =)|( . Giả thiết này thường khơng đúng trong nhiều trường hợp thực tế. Ví dụ: trong một tập hợp S gồm rất nhiều (đủ lớn cho việc thống kê) các tài liệu liên quan đến chủ đề “văn hĩa ẩm thực” cĩ chứa từ khĩa “ăn”. Tuy nhiên cĩ khả năng vào một thời điểm nào đĩ, từ khĩa “ăn” sẽ được thay thế bằng từ đồng nghĩa khác, ví dụ “xơi”, “chén”, “nhậu”. Rõ ràng trong trường hợp này xác suất xuất hiện từ khĩa “ăn” đã thay đổi. Mặc dù vậy sự thay đổi này vơ cùng bé vì mỗi một từ trong số các từ đồng nghĩa đĩ đều cĩ một sắc thái tình cảm riêng, khơng thể tùy tiện thay thế cho nhau được. Như vậy giả thiết trên hồn tồn cĩ thể chấp nhận được. Chúng ta hãy thực hiện lược đồ xác suất S như sau: ♦ Chọn ngẫu nhiên giá trị của |d| ♦ Thực hiện |d| lần một phép thử cĩ đặc điểm như sau: xác suất xuất hiện từ khĩa iω trong miền ngữ nghĩa c cho trước là constciP =)|(ω và xác suất xuất khơng xuất hiện từ khĩa iω trong miền ngữ nghĩa này là )|(1 ciP ω− . Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 54 Lược đồ S chính là lược đồ Becnulli, do đĩ theo cơng thức của lược đồ Becnulli ta cĩ: )13.3( || )(1)|(*|)(|)|( || nd PncPCdPcnWP i i i i n i dii − −== ⎥⎦⎤⎢⎣⎡ ωω Kết hợp các cơng thức (3.9), (3.10), (3.12) và (3.13) ta cĩ = −−∏∑ −−∏= ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ ∈ n cP cPd cPCdPdPcP n cP cPd cPCdPdPcP dcP i ik i ki ki ki n i dk i i i n i ddi )|(1 )|(|| )|(1|)(||)(|)( )|(1 )|(|| |(1|)(||)(|)( )|( || || ω ωω ω ωω ω ω )14.3( )|(1 )|(|| )|(1)( )|(1 )|(|| |(1)( n cP cPd cPcP n cP cPd cPcP i k i ki ki kidik i i idi ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ −−∏∑ −−∏= ∈ ∈ ω ωω ω ωω ω ω Chúng ta ánh xạ giá trị in trong miền [ 0, |d|] vào một giá trị tương ứng in′ trong miền [0, 1] theo cơng thức sau: )|(001 0|| 0 dTF d n n i i i ω=−−=′ +⎟⎠ ⎞⎜⎝ ⎛− Thay vào cơng thức (3.14) ta cĩ: )15.3()( )|(1 )|( )|(1)( )( )|(1 )|( )|(1)( )|( ω ω ωω ω ω ωω ω ω i ki ki kidik i i i idi TF cP cP cPcP TF cP cP cPcP dcP k ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ −−∏∑ −−∏= ∈ ∈ Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 55 Gọi )( iCF ω là số lượng miền ngữ nghĩa cĩ chứa từ khĩa iω . Cĩ thể nhận thấy rằng, tham số )( iCF ω cũng phần nào ảnh hưởng tới việc quyết định ngữ nghĩa cho tài liệu d của từ khĩa này. Từ cơng thức đề xuất thứ nhất (3.15) kết hợp với trọng số )( iCF ω , khĩa luận đã đề xuất cơng thức thứ hai như sau: )16.3()()( )|(1 )|( )|(1)( )()( )|(1 )|( )|(1)( )|( i i ki ki kidik i i i i idi CFTF cP cP cPcP CFTF cP cP cPcP dcP k ωω ω ωω ωω ω ωω ω ω ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ ⎢⎢ ⎢⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ ⎟⎠ ⎞⎜⎝ ⎛ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ −−∏∑ −−∏ = ∈ ∈ Như vậy bộ phân lớp cĩ thể được biểu diễn bằng một mơ hình θ bao gồm tập hợp các tham số sau đây: )|();( cjPcjcPc ωθθ == . Các tham số của mơ hình cĩ thể được ước lượng dựa trên tập dữ liệu huấn luyện ban đầu gồm n tài liệu theo cơng thức sau: nV n nK N il n cc ii V l ij n cc ii cj c c ∑∑+ ∑+= + += == = : || 1 : || 1 1 θ θ 3.5.1. Ước lượng ngưỡng cho các lớp Sau khi xây dựng được mơ hình tham số cho bộ phân lớp, chúng ta cĩ thể tiến hành phân lớp cho các tài liệu mới thu được. Tài liệu d sẽ được phân vào lớp c nếu như { }CicdicPMaxdcP ∈∀= ),|()|( . Phương pháp này đơn giản, dễ hiểu và phù hợp với suy luận logic của chúng ta. Vì mỗi tài liệu chỉ thuộc về một lớp duy nhất, nên phương pháp này chỉ phù hợp với các ứng dụng cĩ mật độ phân bố tài liệu khơng đều, ♦Nc: là số tài liệu thuộc lớp c ♦|V|: số từ khĩa trong tập dữ liệu huấn luyện ♦K: hằng số tùy chọn Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 56 các lớp hồn tồn khơng giao nhau. Trong thực tế do ngơn ngữ tự nhiên thường cĩ tính đa nghĩa, một tài liệu cĩ thể cĩ nhiều ngữ nghĩa khác nhau nên phương pháp này sẽ khơng chính xác. Để khắc phục điều này mỗi lớp c sẽ được gán một giá trị ngưỡng, thc .Tài liệu d sẽ được gán vào lớp c nếu như thdcP c≥)|( . Với phương pháp thứ hai này, điều khĩ khăn nhất là chúng ta phải ước lượng được chính xác giá trị ngưỡng thc . ™ Đề xuất giải pháp ước lượng giá trị ban đầu cho các ngưỡng thc Gọi T là tập các trang văn bản dùng để huấn luyện bộ học, C là tập các lớp cho trước. Quá trình ước lượng giá trị ban đầu cho các ngưỡng được thực hiện theo thuật tốn sau: Thuật tốn: (1). Xây dựng mơ hình tham số θ cho bộ phân lớp (2). For mỗi lớp c ∈ C do (3). { (4). thc← 1; (5). For mỗi tài liệu d ∈ T, cĩ nhãn là c do (6). { (7). Tính giá trị P(c|d) theo cơng thức (3.16); (8). if (P(c|d) < thc ) then thc ← P(c|d); (9). } (10). } Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 57 3.5.2. Kết hợp thuật tốn học máy EM và Naive Bayes Miền ứng dụng của bài tốn phân lớp trang văn bản là tập hợp rất lớn các tài liệu khơng nhãn D. Thuật tốn EM được sử dụng để xử lý dữ liệu khơng nhãn, từ đĩ xây dựng được một mơ hình phân lớp cĩ khả năng thích nghi với các dữ liệu khơng nhãn. Cụ thể, bước E bao gồm việc tính tốn xác suất cĩ điều kiện )|( idcP cho mỗi tài liệu id ∈ D . Xác suất này sau đĩ sẽ được sử dụng để ước lượng lại các tham số của mơ hình trong bước M. Trong mơ hình biểu diễn vector, chúng ta sử dụng cơng thức ước lượng lại các tham số như sau: nK dcP dcPnV dcPn i n i iik n i V k iij n i c cj + ∑+ ∑∑+ ∑+ = == = = = )|(1 )|(|| )|(1 1 1 || 1 1 θ θ ™ Đề xuất giải pháp làm mịn giá trị ngưỡng của các lớp Giá trị ngưỡng của các lớp sẽ được thích nghi với dữ liệu khơng cĩ nhãn(dữ liệu trong tương lai) bằng thuật tốn sau: Thuật tốn: (1) For mỗi tài liệu d ∈ Dtest do (2) { (3) Tiến hành phân lớp cho tài liệu d ; (4) Lưu lại các gía trị )|( cdP và )|( dcP ; (5) } (6) For mỗi lớp c ∈ C do (7) { (8) othres ← thc ; (9) tmp ← 0; (10) tmpv ←0; Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 58 (11) For (mỗi tài liệu d ∈ Dtest ) AND tài liệu d cĩ nhãn là c do (12) { (13) tmp ← tmp + )|( cdP * )|( dcP ; (14) tmpv ← tmpv + )|( cdP * )|( 2dcP ; (15) } (16) tmpv ← tmp – tmpv; (17) n ← 1; (18) while ((tmp – n*tmpv) > othres) do (19) { (20) thc ← tmp – n*tmpv; (21) n ← n+1; (22) } (23) } 3.6. Các yếu tố đánh giá bộ phân lớp Khả năng sử dụng hàm lý thuyết h(•) để mơ tả hàm phân lớp thật sự f(•) (hàm phân lớp kỳ vọng) cĩ thể được đánh giá bằng việc so sánh giá trị của hàm h(•) và hàm f(•) trên cùng một tập dữ liệu đã biết trước nhãn. Giả sử chúng ta chỉ cĩ hai lớp cho trước và hàm lý thuyết h(•) được mơ tả bằng ma trận sau: Lớp thật sự Lớp được phân _ + - TN FN - FP TP Nếu ứng dụng cĩ các miền ngữ nghĩa phân bố đồng đều nhau(xác suất khơng điều kiện của các lớp tương đương nhau), khi đĩ độ chính xác A(Accuracy) thường được sử dụng để làm tham số đánh giá: Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 59 ||D TPTN A test += Nếu các miền ngữ nghĩa khơng cân bằng với nhau, thì độ đo )( precisionρ và )(recallπ sẽ phù hợp hơn. Khơng mất tính tổng quát, cĩ thể giả sử rằng số lượng các dữ liệu thật sự thuộc lớp (+) lớn hơn rất nhiều lần số lượng dữ liệu thuộc lớp (-). Khi đĩ ta cĩ: FNTN TN FPTP TP += += ρ π Trong trường hợp cĩ nhiều lớp, cĩ thể định nghĩa )( precisionρ và )(recallπ một cách độc lập cho từng lớp, đồng thời xem tất cả các lớp cịn lại như là lớp (-). 3.6.1. Các chiến lược đánh giá độ chính xác của bộ phân lớp Việc ước lượng độ chính xác của của bộ phân lớp là một cơng việc quan trọng, qua đĩ cho phép chúng ta đánh giá độ chính xác của bộ phân lớp trong việc gán nhãn cho các dữ liệu trong tương lai, dữ liệu khơng nhãn. Ngồi ra nĩ cịn cho phép chúng ta so sánh giữa các bộ phân lớp với nhau, tìm ra bộ phân lớp tốt nhất để áp dụng vào thực tiễn. Cĩ một số chiến lược hay được sử dụng để ước lượng độ chính xác của bộ phân lớp như chiến lược ước lượng trên hai tập con (holdout) và chiến lược ước lượng chéo trên k tập con, k-fold cross validation. Cả hai chiến lược này đều ước lượng độ chính xác của bộ phân lớp bằng cách phân hoạch ngẫu nhiên tập dữ liệu cĩ nhãn cho trước. ™ Chiến lược ước lượng trên hai tập con (holdout strategy) Trong chiến lược này, tập dữ liệu cĩ nhãn cho trước được phân hoạch thành hai tập con độc lập, tập huấn luyện và tập kiểm tra. Đặc biệt tập huấn luyện cĩ lực Thuật tốn phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek Khĩa luận tốt nghiệp đại học Đặng Thanh Hải 60 lượng lớn gấp hai lần tập kiểm tra. Tập huấn luyện dùng để xây dựng bộ phân lớp, sau đĩ độ chính xác của bộ phân lớp này sẽ được ước lượng dựa trên tập kiểm tra. Ngồi ra chúng ta cĩ thể tiến hành lặp chiến lược này k lần, khi đĩ trung bình cộng của tất cả các độ chính xác trong mỗi lần lặp sẽ là kết quả cuối cùng. ™ Chiến lược ước lượng chéo trên k tập con (k-fold cross validation strategy) Trong chiến lược này, tập dữ liệu cĩ nhãn ban đầu được phân hoạch thành k tập cĩ lực lượng bằng nhau và loại trừ lẫn nhau từng đơi một, S1,S2, ......,Sk. Quá trình huấn luyện và kiểm tra được tiến hành k lần. Trong lần lặp thứ i, tập con Si sẽ được sử dụng như là tập kiểm tra và tất cả các tập cịn lại sẽ được dùng để xây dựng bộ phân lớp. Độ chính xác của bộ phân lớp sẽ được ước lượng bằng thương của số lần phân lớp đúng chia cho tổng số đối tượng dữ liệu trong tập huấn luyện ban đầu. 3.7. Tích hợp bộ phân lớp Bayes vào máy tìm kiếm VietSeek Qua quá trình nghiên cứu, khĩa luận đã tiến hành xây dựng và ứng dụng thành cơng bộ phân lớp trang văn bản Web đề xuất vào máy tìm kiếm VietSeek, bước đầu cho kết quả rất khả quan. Ngồi ra hệ thống cịn cĩ khả năng tạo dữ liệu huấn luyện ban đầu một các tự động theo hạn chế cụ thể nào đĩ. Để cĩ thể tích hợp bộ phân lớp Bayes