Luận văn 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

ầ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. Ngoà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 toá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 toá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 toán “tổ chức theo cấu trúc hoàn toà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 loà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 soá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. Ngoà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 toá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 toá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 loã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 toá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. Ngoà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 toá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 toá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 toá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. Ngoà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 toán sử dụng từ đồng nghĩa cũng khác so với cách tính trong bài toá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 toá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ừ khoá 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 Ngoà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 toá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 toá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 toá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 toá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 toá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 hoà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 toá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 toá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 loã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 loã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 toá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 hoá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 toá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 toá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, ngoà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 toá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 toán dựa trên lý thuyết logic vị từ cấp một (FOIL) để giải quyết bài toá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 toá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 toá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ụ để đoá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 toá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 toán thông dụng được áp dụng hiệu quả trong bài toá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 toán Naive Bayes. Ngoài ra còn đề xuất các thuật toán ước lượng và làm mịn giá trị ngưỡng cho các lớp trong bài toá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 toá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 toán K người láng giềng gần nhất (K-Nearst Ne