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

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 Neighbors) Bộ phân lớp dựa trên thuật toá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 toá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 toá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 toá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 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 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 toán lặp đơn giản sau có thể tạo ra siêu phẳng phân cách[3]. ™ Thuật toá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 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 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 toá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 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 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 toá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 toá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 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 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 toá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 toá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 toá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 toán tối ưu (3.6) thì ⎟⎠ ⎞⎜⎝ ⎛ += = = ∑ posxwnegxwowixiyin i w .. 2 1, 1 &&&r&& α là nghiệm của bài toán (3.4). Mặt khác bài toán tối ưu (3.6) là bài toá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 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 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 toá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 toá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 toá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 toá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 toán này thành một số bài toá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 toá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 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 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 toá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á ; Thoá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á;Thoá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 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 49 Thuật toá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 toá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 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 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 Đoà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 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 51 Sử dụng thuật toá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 toá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 toá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 toá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 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 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 toà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 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 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 hoàn toà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 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 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 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 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 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 56 các lớp hoàn toà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 toán sau: Thuật toá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 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 57 3.5.2. Kết hợp thuật toán học máy EM và Naive Bayes Miền ứng dụng của bài toá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 toá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 toá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 toán sau: Thuật toá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 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 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 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 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. Ngoà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 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 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. Ngoà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. Ngoà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 thành công vào máy tìm kiếm VietSeek, cần phải bổ sung các bảng cơ sở dữ liệu và các modul thích hợp. 3.7.1. Bổ sung cơ sở dữ liệu Sau đây là các bảng cơ sở dữ liệu được bổ sung vào cơ sở dữ liệu ban đầu của máy tìm VietSeek nhằm mục đích phục vụ cho quá trình tích hợp bộ phân lớp trang văn bản Web vào máy tìm kiếm VietSeek. Dữ liệu có nhãn cho trước Tập kiểm tra Tập huấn luyện Xây dựng bộ phân lớp Ước lượng độ chính xác Hình 3.5.Chiến lược Holdout ước lượng độ chính xác 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 61 • Bảng category Chứa thông tin về tất cả các lớp (ngữ nghĩa) của một ứng dụng cụ thể nào đó. Trường Ý nghĩa cat_id Số định danh của lớp name Tên lớp prob Xác suất không điều kiện của lớp theshold Ngưỡng xác suất đề một tài liệu được phân vào lớp này. • Bảng urlsample Chứa thông tin về tất cả các tài liệu trong tập dữ liệu huấn luyện Trường Ý nghĩa url_id Số định danh của trang văn bản Web vector Vector biểu diễn nội dung của trang Web cat Số định danh xác định lớp của tài liệu • Bảng urlcate Chứa kết quả của quá trình phân lớp trên tất cả các trang Web đã được đánh chỉ mục. Trường Ý nghĩa url_id Số định danh của trang văn bản Web cat_id Số định danh của lớp được gán cho trang văn bản bởi bộ phân lớp CatUrlPro Giá trị xác suất P(C | doc) UrlCatPro Giá trị xác suất P(doc | C) • Bảng newurls Chứa tất cả các trang Web đã được đánh chỉ mục. Trường Ý nghĩa url_id Số định danh của trang văn bản Web vector Vector biểu diễn nội dung của trang Web 3.7.2. Giới thiệu các môđun bổ sung Mã chương trình cụ thể tích hợp trong một số modul chính của máy tìm kiếm VietSeek được trình bày ở phần phụ lục. Khóa luận đã tiến hành tích hợp bộ phân lớp Naive Bayes vào những nơi cần thiết và thích hợp trong mã chương trình của máy tìm kiếm VietSeek, nhưng chủ yếu là vào các modul sau: ™ Modul CUrlContent::Save ™ Modul truy cập cơ sở dữ liệu CSQLDatabaseI 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 62 Ngoài ra, do quá trình tính toán trong bộ phân lớp Naive Bayes yêu cầu độ chính xác rất cao, nên khóa luận đã phải xây dựng thành công bộ xử lý số thực lớn. Bộ xử số thực lớn được đặt trong hai file ‘bignum.h’ và ‘scibignum.h’. 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 63 Chương 4. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 4.1. Kết quả thực nghiệm Sử dụng tập dữ huấn luyện ban đầu gồm 2435 trang Web lấy từ trang chủ thuộc 6 lĩnh vực chính (Vi tính, Thể thao, Pháp luật, Sức khỏe, Văn hóa, Xã hội), sau đó tiến hành phân lớp lại dữ liệu mẫu trên lần lượt bằng các bộ phân lớp Naive Bayes dựa trên công thức (3.8), (3.15) và (3.16), khóa luận thu được kết quả trong hai trường hợp có sử dụng ngưỡng và không sử dụng ngưỡng như sau: (R-Là nhãn thực của các tài liệu Web;P-Là nhãn được gán bởi bộ phân lớp cho các tài liệu Web): 4.1.1. Kết quả trong trường hợp không sử dụng ngưỡng: Trong trường hợp phân lớp không sử dụng ngưỡng, tài liệu d sẽ được phân vào lớp c nếu như { }CicdicPMaxdcP ∈∀= ),|()|( . Sau đây là các kết quả thu được khi tiến hành phân lớp bằng các công thức khác nhau. ™ Sử dụng công thức thức (3.8) R P Vitính Thể thao Pháp luật Sứckhỏe Văn hóa Xãhội Recall Vi tính 340 1 6 5 96.59% Thể thao 495 5 99% Phápluật 1 173 0% sức khỏe 1 386 22 94.38% Văn hóa 500 100% Xã hội 1 499 99.8% Precision 100% 99.40% 0% 100% 93.63% 73.71% Bảng 4.1. Kết quả khi sử dụng công thức (3.8) và không sử dụng ngưỡ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 64 ™ Sử dụng công thức đề xuất thứ nhất (3.15) R P Vitính Thể thao Pháp luật Sứckhỏe Văn hóa Xãhội Recall Vi tính 336 1 6 9 95.45% Thể thao 495 5 99% Phápluật 1 173 0% sức khỏe 1 385 22 1 94.13% Văn hóa 500 100% Xã hội 1 499 99.8% Precision 100% 99.4% 0% 100% 93.63% 73.17% ™ Sử dụng công thức đề xuất thứ hai (3.16) R P Vitính Thể thao Pháp luật Sứckhỏe Văn hóa Xãhội Recall Vi tính 350 1 1 99.43% Thể thao 491 9 98.2% Phápluật 150 1 23 86.21% sức khỏe 405 4 99.02% Văn hóa 500 100% Xã hội 1 499 99.8% Precision 100% 99.59% 100% 100% 97.28% 95.41% Bảng 4.2. Kết quả khi sử dụng công thức (3.15) và không sử dụng ngưỡng Bảng 4.3. Kết quả khi sử dụng công thức (3.16) và không sử dụng ngưỡ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 65 ™ Nhận xét: Trong trường hợp sử dụng bộ phân lớp được xây dựng dựa trên công thức (3.8) và (3.15), kết quả thu được rất tốt (độ hồi tưởng và độ chình xác), ngoại trừ việc phân lớp sai hoàn toàn đối với lớp PhápLuật. Tuy nhiên điều này đã được khắc phục khi sử dụng bộ phân lớp dựa trên công thức đề xuất (3.16). Ngoài ra kết quả thu cũng tốt hơn trong trường hợp sử dụng bộ phân lớp dựa trên công thức (3.8) và công thức (3.15). 4.1.2. Kết quả trong trường hợp sử dụng ngưỡng theo thuật toán đề xuất: Trong trường hợp phân lớp có sử dụng ngưỡng, mỗi lớp c sẽ được gắn một giá trị ngưỡng thc được tạo ra bởi thuật toán đề xuất, ước lượng giá trị ban đầu của ngưỡng. Tài liệu d sẽ được gán vào lớp c nếu như thdcP c≥)|( . Sau đây là kết quả khi tiến hành phân lớp bằng các công thức khác nhau: ™ Sử dụng công thức (3.8) R P Vitính Thể thao Pháp luật Sứckhỏe Văn hóa Xãhội Recall Vi tính 351 12 88 77.83% Thể thao 499 9 98.23% Phápluật 173 174 49.86% sức khỏe 4 408 175 69.51% Văn hóa 10 4 499 64 86.48% Xã hội 3 1 499 99.2% Precision 100% 94.51% 100% 98.79% 100% 49.54% ™ ™ Bảng 4.4. Kết quả khi sử dụng công thức (3.8) và sử dụng ngưỡng theo thuật toán đề xuất 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 66 ™ Sử dụng công thức đề xuất thứ nhất (3.15) R P Vitính Thể thao Pháp luật Sứckhỏe Văn hóa Xãhội Recall Vi tính 351 10 85 78.7% Thể thao 499 7 98.62% Phápluật 173 174 49.86% sức khỏe 5 408 240 62.48% Văn hóa 10 4 499 80 84.15% Xã hội 3 1 499 99.2% Precision 100% 94.69% 100% 98.79% 100% 45.99% ™ Sử dụng công thức đề xuất thứ hai (3.16) R P Vitính Thểthao Pháp luật Sứckhỏe Văn hóa Xãhội Recall Vi tính 351 21 23 88.86% Thể thao 1 499 3 3 98.62% Phápluật 173 88 66.28% sức khỏe 2 408 4 98.55% Văn hóa 3 2 499 7 97.65% Xã hội 3 499 99.4% Precision 99.72% 94.51% 100% 99.51% 99.4% 79.97% Bảng 4.5. Kết quả khi sử dụng công thức (3.15) và sử dụng ngưỡng theo thuật toán đề xuất Bảng 4.6. Kết quả khi sử dụng công thức (3.16) và sử dụng ngưỡng theo thuật toán đề xuất 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 67 ™ Nhận xét Nếu tiến hành phân lớp có sử dụng ngưỡng, được tạo ra bởi thuật toán đề xuất [Ước lượng giá trị ban đầu cho các ngưỡng], thì kết quả thu được (độ chính xác và độ hồi tưởng) đều tương đối tốt với cả ba bộ phân lớp dựa trên công thức (3.8), (3.15) và công thức (3.16). Điều này chứng tỏ rằng giá trị ngưỡng của các lớp được tạo ra bởi thuật toán đề xuất là tương đối tốt. Ngoài ra, dựa trên các bảng (4.4), (4.5) và (4.6) có thể thấy rằng bộ phân lớp dựa trên công thức đề xuất (3.16) có số lần phân lớp sai bé hơn rất nhiều so với bộ phân lớp dựa trên công thức (3.8) và công thức (3.16). Sau đây là các biểu đồ so sánh kết quả thu được của ba bộ phân lớp dựa trên các công thức (3.8), (3.15) và (3.16) được xây dựng từ kết quả thực nghiệm: 95.41 73 17 73.71 97.28 93 63 100100 0 99 4 99.59 100 100 90 80 70 Vi tính Thể thao Pháp luật Sức khỏe Văn hóa Xã hội công thức (3.8) công thức (3.15) công thức (3.16) Biểu đồ 4.1. Độ chính xác trong trường hợp không sử dụng ngưỡng Precision (%) 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 68 10099.43 96.59 99.8 86.21 100 90 80 70 98.2 99 Thể thao 0 Pháp luật Văn hóa Xã hội công thức (3.8) công thức (3.15) công thức (3 16) Biểu đồ 4.2. Độ hồi tưởng trong trường hợp không sử dụng ngưỡng 95.45 Vi tính 94 38 99.02 94 13 Sức khỏe Recall (%) 79 97 45 99 49 54 99.4 99 51 100 94 51 10099 72100100 90 80 40 94.69 94.51 Thể thao Pháp luật Văn hóa Xã hội công thức (3.8) công thức (3.15) công thức (3 16) Biểu đồ 4.3. Độ chính xác trong trường hợp sử dụng ngưỡng đề xuất Vi tính 98.79 Sức khỏe Precision (%) 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 69 4.2. Đánh giá và khả năng ứng dụng Dựa trên các kết quả thực nghiệm ở trên, có thể khẳng định rằng công thức đề xuất (3.16) là tốt nhất so với hai công thức (3.8) và (3.15) trên tập dữ liệu đã cho. Hệ thống xây dựng trong khóa luận có khả năng áp dụng vào thực tế với vai trò như là một cổng thông tin, có khả năng lọc (phân loại) và phân phối các tài liệu Web đặc thù cho từng bộ phận chuyên môn trong một hệ thống nghiệp vụ lớn. Khóa luận xin phép được đưa ra một mô hình ứng dụng cho toàn Đại học Quốc Gia như hình (4.7). Ngoài ra hệ thống này là cơ sở cho việc nghiên cứu và xây dựng máy tìm kiếm tài liệu Web theo ngữ nghĩa. VietSeek Đại học Đại học Khoa học tự nhiên Khoa Công nghệ Khoa Luật Internet Url Url liên quan đến công nghệ Url liên quan đến pháp luật Url liên quan đến khoa học tự nhiên Hình 4.7. Mô hình ứng dụng hệ thống VietSeek 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 70 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TRONG TƯƠNG LAI Qua quá trình tự tìm hiểu và nghiên cứu, cộng với sự giúp đỡ nhiệt tình của các thầy cô giáo cũng như của bạn bè, khóa luận đã đạt được một số kết quả bước đầu như sau: ™ Trình bày mô hình hoạt động tổng quát của các máy tìm kiếm nói chung và máy tìm kiếm VietSeek nói riêng. Trình bày chi tiết quá trình hoạt động của modul đánh chỉ mục của máy tìm kiếm VietSeek để từ đó làm cơ sở cho việc cải tiến và tích hợp các yếu tố khai phá dữ liệu Web. ™ Trình bày khái quát các kỹ thuật cơ bản liên quan đến quá trình khai phá dữ liệu FullText cũng như quá trình khai phá dữ liệu Web, đặc biệt là các thuật toán (K-NN, SVM, Cây quyết định, Naive Bayes) được áp dụng nhằm giải quyết bài toán phân lớp trang văn bản. ™ Khóa luận đã đề xuất các công thức phân lớp trang tài liệu văn bản dựa trên thuật toán Bayes và chứng minh tính đúng dắn của chúng. Ngoài ra, khóa luận đã đề xuất thuật toán ước lượng và làm mịn giá trị ngưỡng cho các lớp dựa trên cơ sở lý thuyết xác suất. ™ Tích hợp 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, và bước đầu cho kết quả đáng tin cậy. Do thời gian không cho phép, kiến thức còn hạn chế và việc tích hợp các giải pháp khai phá web vào máy tìm kiếm là một bài toán lớn cho nên các môđun được xây dựng trong khóa luận còn cần phải phát triển thêm. Việc đánh giá hiệu quả của thuật toán làm mịn giá trị ngưỡng của các lớp phải được tiến hành trên một lượng dữ liệu lớn, do vậy hiện tại khóa luận chưa thể đưa ra được đánh giá chính xác về thuật toán đề xuất này. Trong tương lai, khóa luận cần phải được hoàn thiện theo các hướng sau đây: ™ Tích hợp quá trình xử lý ngôn ngữ tự nhiên vào bộ phân lớp. Cụ thể, ở mức đơn giản có thể áp dụng quá trình chuyển các từ phát sinh về từ gốc ban đầu (loại bỏ các tiền tố, hậu tố,......), còn ở mức cao hơn, đề cập tới bài toán phát hiện luật liên quan đến cấu trúc cũng như ngữ nghĩa trong một ngôn ngữ nhất định. ™ Xây dựng VietSeek trở thành một máy tìm kiếm theo nội dung bằng cách nghiên cứu quá trình tìm kiếm trong máy tìm kiếm VietSeek và các kỹ thuật 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 71 liên quan đến bài toán xây dựng hệ thống tìm kiếm thông tin thông minh (Intelligent Information System). 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 72 PHỤ LỤC Sau đây là mã chương trình cụ thể của bộ phân lớp Naive Bayes được tích hợp vào máy tìm kiếm VietSeek : CUrlContent::Save() { .......................... if((classifing/*&&changed*/)||(InitThreshold))//<ReIndex and ReClassify { CCategory*Cate=Classifier; hash_map Cat_Value; char* Mot=new char[2]; Mot[0]='1'; Mot[1]=0; char* one=new char[2]; one[0]='0'; one[1]=0; SciBigNum DocProb(one); //SciBigNum Min(Mot); while(Cate->next) { pvector=vector; char *CProbS=new char[22]; //CProbS=gcvt(Cate->prob,20,CProbS); CProbS=gcvt(Cate->prob,20,CProbS); SciBigNum CProb(CProbS); Cat_Value[Cate->cat_id].DocCatProb=Mot; for(int i=0;i<ewords-words;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 Khóa luận tốt nghiệp đại học Đặng Thanh Hải 73 double base=(double)FindWordClassParam(*(ULONG*)pvector,Cate); double oldbase=base; //base=(double)base/(1-(double)base); double exp=(double)(*(pvector+2))/(double)totalword;//TF double formular=pow(base, exp); //formular=(double) formular*(1-(double)oldbase); char* formularS=new char[22]; gcvt(formular,20,formularS); SciBigNum temp(formularS); Cat_Value[Cate->cat_id].DocCatProb=Cat_Value[Cate- >cat_id].DocCatProb*temp; pvector+=3; delete formularS; temp.~SciBigNum(); } Cat_Value[Cate->cat_id].catp=Cate; Cat_Value[Cate->cat_id].catevalue=Cat_Value[Cate- >cat_id].DocCatProb*CProb; if(strcmp(DocProb.value,one)==0) { DocProb=Cat_Value[Cate->cat_id].catevalue; } else { DocProb=DocProb+Cat_Value[Cate->cat_id].catevalue; } delete CProbS; CProb.~SciBigNum(); 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 74 Cate=Cate->next; } //int Predicted; char* threshold=NULL; int IsLabel; for(hash_map::iterator it=Cat_Value.begin();it!=Cat_Value.end();it++) { ((*it).second).catevalue=((*it).second).catevalue/DocProb; threshold=m_cache->m_database->GetThreshW((*it).first); SciBigNum ThreshBig(threshold); if(threshold) delete threshold; //if(answ) delete answ; if(InitThreshold) { int SampleOfClass=m_cache->m_database->IsSampleOfClass ( m_url.m_urlID, (*it).first ); if(SampleOfClass)// Actual belong to this class { if((strcmp(ThreshBig.value,Mot)==0)||(ThreshBig> ((*it).second).catevalue)) { char* min=(((*it).second).catevalue).Reverse(); m_cache->m_database->UpdateThreshold( min, (*it).first ); if(min) delete min; } } 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 75 //if(answ) delete answ; } else //Classifing { if((((*it).second).catevalue >(ThreshBig)) &&(strcmp(ThreshBig.value,Mot)!=0)) { IsLabel=1; logger.log(CAT_ALL, L_INFO, "<CLASS_ID:%d,DOC_ID:%lu >\n", (*it).first, m_url.m_urlID); const char* Cat_Doc=(Cat_Value[(*it).first].catevalue).Reverse() const char* Doc_Cat=(Cat_Value[(*it).first].DocCatProb). Reverse() m_cache->m_database->InsertRCate(m_url.m_urlID,(*it).first, Cat_Doc,Doc_Cat); if(Cat_Doc) delete Cat_Doc; if(Doc_Cat) delete Doc_Cat; } } ThreshBig.~SciBigNum(); }//end of for loop if(!IsLabel) { int AnotherCat=m_cache->m_database->GetAnotherCat(); const char* ACat_Doc=(Cat_Value[AnotherCat].catevalue).Reverse(); const char* ADoc_Cat=(Cat_Value[AnotherCat].DocCatProb).Reverse(); m_cache->m_database->InsertRCate(m_url.m_urlID,AnotherCat, ACat_Doc, ADoc_Cat); 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 76 if(ACat_Doc) delete ACat_Doc; if(ADoc_Cat) delete ADoc_Cat; } if(vector&&classifing) { char* bufnew=NULL; CSQLParam pnew; pnew.AddParam(&(m_url.m_urlID)); ULONG wordCount=ewords-words; ULONG vsize=(ewords-words)*3*sizeof(WORD); if ( vsize >= 20000) { bufnew = new char[sizeof(wordCount) + vsize]; } else { bufnew = (char*)alloca(sizeof(wordCount) + vsize); } memcpy(bufnew, (char*)&wordCount, sizeof(wordCount)); memcpy(bufnew+sizeof(wordCount), (char*)vector, vsize); pnew.AddParamEsc((char*)bufnew, vsize+ sizeof(wordCount)); CSQLQuery *sqlquery1 = m_cache->m_database->m_sqlquery ->InsertUrlNew(&pnew); m_cache->m_database->sql_real_query(sqlquery1); if(vsize>=20000) delete bufnew; } for(hash_map::iterator it=Cat_Value.begin(); 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 77 it!=Cat_Value.end();it++) { ((*it).second).catevalue.~SciBigNum(); } Cat_Value.clear(); delete one; delete Mot; //Max.~SciBigNum(); DocProb.~SciBigNum(); }// ................................................. }//<END OF FUNCTION 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 78 TÀI LIỆU THAM KHẢO [1]. Dunja Mladenic. Machine learning on non-homogenous, distributed text data,Doctoral Dissertation. 1998 [2]. Micheline Kamber, Jiawei Han: Data Mining, Concepts and Techniques [3]. Pierre Baldi, Paolo Fransconi, Padhraic Smyth. Modeling the Internet and the Web, Probabilistic Methods and Algorithms 2003 [4]. Paolo Boldi, Bruno Cdenotti, Massimo Santini, Sebastinao Virga. UbiCrawler: A scalable fully distributed web crawler. Jan. 27, 2003 [5]. Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. 1998 [6]. Sen Slattery (2002). Hypertext Classification. Doctoral dissertation (CMU-CS- 02-142). School of Computer Science. Carnegie Mellon University. [7]. Bùi Quang Minh (2002). Máy tìm kiếm VietSeek. Báo cáo kết quả nghiên cứu thuộc Đề tài khoa học đặc biệt cấp ĐHQGHN mã số QG-02-02. [8]. Đặng Tiểu Hùng. Phương pháp biểu diễn ngữ nghĩa lân cận siêu liên kết cho máy tìm kiếm VietSeek. Luận văn thạc sỹ Công nghệ thông tin- Đại học Quốc gia Hà Nội, 2004. [9]. Nguyen Ngoc Minh, Nguyen Tri Thanh, Ha Quanh Thuy, Luong Song Van, Nguyen Thi Van. A Knowledge Discovery Model in Full-text Databases. Proceedings of the First Workshop of International Joint Research: “Parallel Computing, Data Mining and Optical Networds”. March 7, 2001, Japan Advanced Institute of Science and Technology (JAIST), Tatsunokuchi, Japan, 59-68 [10]. Phạm Thanh Nam, Bùi Quang Minh, Hà Quang Thụy. Giải pháp tìm kiếm trang Web tương tự trong máy tìm kiếm VietSeek. Tạp chí Tin học và Điều khiển học (nhận đăng 1-2004). [11]. Phạm Thanh Nam. Một số giải pháp cho bài toán tìm kiếm trong cơ sở dữ liệu Hypertext. Luận văn thạc sỹ Công nghệ thông tin- Đại học Quốc gia Hà Nội. [12]. [13].