Luận văn -Thuật toán Bayes và ứng dụng

tơ đặc trưng của 2 lớp. Sau đó ta tính các xác suất p(x|wi) , là xác suất để đối tượng thuộc lớp wi có đặc trưng là x gọi là likelihood of x tạm dịch là khả năng xảy ra x hay là hợp lý của x. Thực tế ta dùng công thức Bayes: (1-3) Với: Lưu ý rằng P(wi) và P(wi|x) là các xác suất rời rạc, trái lại p(x|wi) và p(x) là các giá trị của hàm mật độ xác suất. Để ý rằng khi so sánh (1-2a) ta có giá trị chung là p(x) do đó ta viết lại: if p(x|w1) P(w1) > p(x|w2)P(w2) then x  w1 else x  w2. (1-4) Hay là: then x  w1 else x  w2. (1-4a) Trong công thức (1-4a) thì v(x) gọi là tỷ số hợp lý (likelihood ratio) 1 ( ) ( | w ) (w ) c i i i p x p x P   ( | w ) (w )(w | ) ( ) i i i p x Pp x p x  1 2 2 1 ( | w ) (w )( ) ( | w ) (w ) p x pv x p x p   Thuật toán Bayes và ứng dụng 7 Hình 1: Biểu đồ của đặc trưng N cho hai lớp học của các nút chai. Giá trị ngưỡng N = 65 được đánh dấu bằng một đường thẳng đứng Giả sử rằng mỗi nút chai chỉ có một đặc trưng là N, tức là vec tơ đặc trưng là x = [N], giả sử có một nút chai có x = [65]. Từ đồ thị ta tính được các xác suất likelihood: p(x|w1) = 20/24 = 0.833 → P(w1) p(x|w1) = 0.333 (1-5a) p(x|w2) = 16/23 = 0.696 → P(w2) p(x|w1) = 0.418 (1-5b) Ta sẽ phân x = [65] vào lớp w2 mặc dù hợp lý(likelihood) của w1 lớn hơn của w2 Hình 2 minh họa ảnh hưởng của việc điều chỉnh ngưỡng xác suất tiên nghiệm đến các hàm mật độ xác suất.  Xác suất tiên nghiệm đồng nhất (equal prevalences). Với các hàm mật độ xác suất đồng nhất, ngưỡng quy định là một nửa khoảng cách đến phần tử trung bình. Số lượng các trường hợp phân lớp sai tương ứng với vùng được tô đậm. Đây là vùng mà khoảng cách phân lớp là nhỏ nhất.  Xác suất tiên nghiệm của w1 lớn hơn của w2. Ngưỡng quyết định thay thế các lớp có xác suất tiên nghiệm nhỏ hơn. Vì vậy giảm số trường hợp của lớp có xác suất tiên nghiệm cao dường như có vẻ thuận tiện. Thuật toán Bayes và ứng dụng 8 Hình 2: Xác suất tiên nghiệm đồng nhất (a), không đồng nhất (b). Chúng ta thấy rằng thật sự độ lệch ngưỡng quyết định đã dẫn đến lớp w2 tốt hơn lớp w1. Điều này nghe có vẻ hợp lý kể từ khi mà bây giờ lớp w2 xuất hiện thường xuyên hơn. Khi độ sai toàn phần tăng lên điều kỳ lạ là sự ảnh hưởng của xác suất tiên nghiệm là có lợi. Câu trả lời cho câu hỏi này là liên quan đến chủ đề phân lớp mạo hiểm, mà sẽ được trình bày ngay bây giờ. Chúng ta giả định rằng giá của một nút chai (cork stopper) thuộc lớp w1 là 0.025£, lớp w2 là 0.015£. Giả sử là các nút chai lớp w1 được dùng cho các chai đặc biệt, còn các nút chai lớp w2 thì dùng cho các chai bình thường. Nếu ta phân lớp sai một nút chai lớp w1 thì sẽ bị mất 0.025-0.015=0.01£. Nếu phân lớp sai một nút chai lớp w2 thì dẫn đến nó sẽ bị loại bỏ và sẽ bị mất 0.015£. Ta ký hiệu:  SB - Hành động của việc sử dụng một nút chai(cork stopper) để phân cho loại chai đặc biệt.  NB - Hành động của việc sử dụng một nút chai(cork stopper) để phân cho loại chai bình thường.  w1 = S (siêu lớp); w2 = A (lớp trung bình) Thuật toán Bayes và ứng dụng 9 Hình 3: Kết quả phân lớp của cork stoppers với xác suất tiên nghiệm không đồng nhất: 0.4 cho lớp w1 và 0.6 cho lớp w2 Định nghĩa: λij = λ(αi | wj ) là độ mất mát với hành động αi khi mà lớp đúng là wj, với αi{SB, NB}. λ11 = λ(α1 | w1 ) = λ(SB | S) = 0, λ12 = λ(α1 | w2 ) = λ(SB | A) = 0.015, λ21 = λ(α2 | w1 ) = λ(NB | S) = 0.01, λ22 = λ(α2 | w2 ) = λ(NB | A) = 0. Thuật toán Bayes và ứng dụng 10 Chúng ta có thể sắp xếp λij thành ma trận hao phí Λ. Λ = (1-6) Vì thế độ mất mát với hành động sử dụng một nút chai (mô tả bởi vectơ đặc trưng x) và phân vào cho những chai đặc biệt có thể được biểu thị như sau: R(α1 | x) = R(SB | x) = λ(SB | S)P(S | x) + λ(SB | A)P(A | x) (1-6a) R(α1 | x) = 0.015 P(A | x) Tương tự cho trường hợp nếu phân cho những chai thông thường: R(α2 | x) = R(NB | x) = λ(NB | S)P(S | x) + λ(NB | A)P(A | x) (1-6b) R(α2 | x) = 0.01P(S | x) Chúng ta giả định rằng đánh giá rủi ro chỉ chịu ảnh hưởng từ quyết định sai. Do vậy một quyết định chính xác sẽ không gây ra thiệt hại λii=0, như trong (1-6). Nếu thay vì 2 lớp chúng ta có c lớp thì sự mất mát ứng với một hành động αi sẽ là: (1-6c) Chúng ta quan tâm đến việc giảm thiểu mức rủi ro trung bình tính cho một lượng lớn nút chai bất kỳ. Công thức Bayes cho rủi ro nhỏ nhất làm được điều này bằng cách cực tiểu hóa các rủi ro có điều kiện R(αi | x). Giả sử ban đầu rằng các quyết định sai lầm có cùng một mất mát, chúng có tỉ lệ với một đơn vị mất mát: (1-7a) Trong trường hợp này từ tất cả các xác suất hậu nghiệm đều tăng lên một, chúng ta cần phải cực tiểu hóa: (1-7b) 0 0.015 0.01 0       i 1 ( | ) ( | ) ( | ) c i j j j R x P x       i 0 ( | ) 1ij j if i j if j j          ( | ) ( | ) 1 ( | )i j j i j R x P x P x       Thuật toán Bayes và ứng dụng 11 Điều này tương đương với việc chúng ta cực đại P(wi | x), luật quyết định Bayes cho rủi ro cực tiểu tương ứng với việc tổng quát hóa vấn đề: Phân lớp wi nếu P(wi | x) > P(wj | x), ij  (1-7c) Tóm lại: luật quyết định Bayes cho rủi ro cực tiểu, khi sự phân lớp đúng thì không bị mất mát và nếu như phân lớp sai thì có mất mát, ta cần phải chọn được lớp có xác suất hậu nghiệm là cức đại. Hàm quyết định cho lớp wi là: gi(x) = P(wi | x) (4-18d) Bây giờ hãy xem xét các tình huống khác nhau của các thiệt hại xảy ra cho những quyết định sai lầm, để cho đơn giản giả sử c = 2. Dựa vào các biểu thức (1-6a) và (1-6b) thật dễ nhận thấy rằng một nút chai sẽ thuộc lớp w1 nếu: < Hay là (1-8) Vì thế ngưỡng quyết định so với tỷ số hợp lý(likelihood) thì nó nghiêng về sự mất mát. Ta có thể cài đặt luật quyết định Bayes như hình 5. Tương tự chúng ta có thể điều chỉnh xác suất tiên nghiệm như sau: ; (1-8a) 12 2 1 21 1 2 ( ) ( | ) ( ) ( | ) P w P x w P w P x w    12 2( | )P x  21 1( | )P x  * 21 1 1 21 1 12 2 ( )( ) ( ) ( ) P wP w P w P w     * 12 22 21 1 12 2 ( )( ) ( ) ( ) P wP w P w P w     Thuật toán Bayes và ứng dụng 12 Với sự mất mát λ12 = 0.015 và λ21 = 0.01, sử dụng xác suất tiên nghiệm ở trên ta được P*(w1) = 0.308 và P*(w2) = 0.692. Sự thiệt hại sẽ là lớn hơn nếu như phân lớp sai lớp w2 do đó cần tăng P*(w2) lên so với P*(w1). Kết quả của việc điều chỉnh là giảm số lượng các phần tử thuộc lớp w2 bị phân lớp sai thành w1. Xem kết quả phân lớp ở hình ở hình 6. Ta có thể tính giá trị rủi ro trung bình trường hợp có 2 lớp: (1-9) 1 2 12 2 21 1 12 12 21 21( | ) ( ) ( | ) ( ) R R R P w x p x dx P w x p x dx Pe Pe        Thuật toán Bayes và ứng dụng 13 R2 và R2 là miền quyết định của lớp 1 và lớp 2 , còn Peij là xác suất sai số của sự quyết định lớp là i khi mà lớp đúng là j Chúng ta hãy sử dụng tập dữ liệu huấn luyện để đánh giá những sai số này, Pe12=0.1 và Pe21=0.46 (xem hình 6). Rủi ro trung bình đối với mỗi nút chai bây giờ là: R = 0.015Pe12 + 0.01Pe21 = 0.0061Є. Với Ω là tập các lớp ta có công thức (1-9) tổng quát: (1-9a) Luật quyết định Bayes không phải là lựa chọn duy nhất trong thống kê phân lớp. Cũng lưu ý rằng, trong thực tế một trong những cố gắng để giảm thiểu rủi ro trung bình là sử dụng ước lượng của hàm mật độ xác suất tính được từ một tập dữ liệu huấn luyện, như chúng ta đã làm ở trên cho cork Stoppers. Nếu chúng ta có những căn cứ để tin rằng các hàm phân phối xác suất thỏa mãn tham số mẫu, thì ta thay thế việc tính các tham biến thích hợp từ tập huấn luyện. Hoặc là chúng ta cũng có thể sử dụng phương pháp cực tiểu hóa rủi ro theo kinh nghiệm (empirical risk minimization (ERM)), nguyên tắc là cực tiểu hóa rủi ro theo kinh nghiệm thay vì rủi ro thực tế. 2.3 Phân lớp Bayes chuẩn tắc Cho đến giờ chúng ta vẫn chưa giả định đặc trưng của phân phối mẫu cho likelihoods. Tuy nhiên, mô hình chuẩn tắc là một giả định hợp lý. Mô hình chuẩn tắc có liên quan đến định lý giới hạn trung tâm nổi tiếng, theo định lý này thì tổng của một lượng lớn các biến ngẫu nhiên độc lập và phân phối đồng nhất sẽ có phân phối hội tụ về luật chuẩn. Thực tế ta có được một xấp xỉ đến luật chuẩn tắc, thậm chí với cả một số lượng tương đối nhỏ được thêm vào các biến ngẫu nhiên. Đối với các đặc trưng có thể được coi là kết quả của việc bổ sung các biến độc lập, thường thì giả định là có thể chấp nhận. Likelihood chuẩn tắc của lớp ωi được biểu diễn bởi hàm mật độ xác suất: ( ( ) | ) ( , ) ( ( ) | ) ( , ) ( ) i i i i i i X X R x P x dx x P x p x dx                 Thuật toán Bayes và ứng dụng 14 µi và ∑i là các tham số phân phối, đến giờ thì ta đã sử dụng các ước lượng mẫu mi và Ci. Hình 7 minh họa phân phối chuẩn trong trường hợp có hai chiều. Cho một tập huấn luyện có n mẫu T={x1, x2, … xn} được mô tả bởi một phân phối với hàm mật độ xác suất là p(T | θ), θ là một vec tơ tham số của phân phối (chẳng hạn như vec tơ trung bình của phân phối chuẩn). Một cách đáng chú ý tính được ước lượng mẫu của vectơ tham biến là cực đại hóa hàm mật độ xác suất p(T | θ), có thể coi dây là một hàm của θ gọi là likelihood of θ cho tập huấn luyện. Giả sử rằng mỗi mẫu là đưa vào độc lập từ một tập vô hạn, chúng ta có thể biểu thị likelihood như sau: Khi sử dụng ước lượng hợp lý cực đại (maximum likelihood estimation) của các biến phân phối thì nó thường dễ dàng hơn là tính cưc đại của ln[p(T|θ)], điều này là tương đương nhau. Với phân phối Gauss ước lượng mẫu được cho bởi các công thức (1-10a) và (1-10b) chính là ước lượng hợp lý cực đại và nó sẽ hội tụ về một giá trị thực. 1 ( | ) ( | ) n i i p T p x    Thuật toán Bayes và ứng dụng 15 Như có thể nhìn thấy từ (1-10), các bề mặt của mật độ xác suất đồng nhất với hợp lý chuẩn (normal likelihood) thỏa mãn Mahalanobis metric: Bây giờ chúng ta tiếp tục tính hàm quyết định cho các đặc trưng của phân phối chuẩn: gi(x) = P(ωi | x) = P(ωi) p(x | ωi) (1-11) biến đổi logarit ta được: Bằng cách sử dụng những hàm quyết định, rõ ràng phụ thuộc Mahalanobis metric, ta có thể xây dựng phân lớp Bayes với rủi ro nhỏ nhất, đây là phân lớp tối ưu. Chú ý rằng công thức (1-11b) sử dụng giá trị thật của khoảng cách Mahalanobis, trong khi mà trước đó chúng ta sử dụng ước lượng của khoảng cách này. Với trường hợp covariance đồng nhất cho tất cả các lớp (∑i=∑) và bỏ qua các hằng số ta được: (1-11c) 11( ) ( ) ( ) ln ( ) 2i i i i h x x x P       Thuật toán Bayes và ứng dụng 16 Với bài toán 2 lớp, biệt số d(x) =h1(x)-h2(x) là dễ đàng tính toán: Qua đó ta có được hàm quyết định tuyến tính Hai lớp phân biệt với phân phối chuẩn, xác suất tiên nghiệm đồng nhất và covariance và vẫn còn có một công thức rất đơn giản cho xác suất của lỗi của phân lớp: Thuật toán Bayes và ứng dụng 17 bình phương của khoảng cách Bhattacharyya, một khoảng cách Mahalanobis của sai phân trung bình, thể hiện tính dễ tách lớp. Hình 8 thể hiện dáng điệu của Pe với sự tăng dần của bình phương khảng cách Bhattacharyya. Hàm này giảm dần theo cấp số mũ và nó hội tụ tiệm cận tới 0. Vì vậy thật khó để giảm sai số phân lớp khi giá trị này là nhỏ. Lưu ý rằng ngay cả khi các phân phối mẫu không phải là phân phối chuẩn, miễn là chúng đối xứng và phải tuân theo Mahalanobis metric, thì chúng ta sẽ thu được mặt phân lớp quyết định tương tự như phân lớp chuẩn, cho dù có sự khác biệt về đánh giá sai số và xác suất hậu nghiệm. Để minh họa ta hãy xét hai lớp có xác suất tiên nghiệm đồng nhất và có ba loại phân phối đối xứng, với cùng độ lệch tiêu chuẩn và trung bình 0 và 2.3 như hình 9. Thuật toán Bayes và ứng dụng 18 Phân lớp tối ưu cho 3 trường hợp sử dụng cùng một ngưỡng quyết định có giá trị 1.15, tuy nhiên các sai số phân lớp là khác nhau:  Nomal: Pe = 1 – erf(2.3/2) = 12.5%  Cauchy: Pe = 22.7%  Logistic: Pe = 24.0% Kết quả thực nghiệm cho thấy, khi ma trận covariance đưa ra độ lệch giới hạn, thì sự phân lớp có thể thực hiện một cách tương tự với phương pháp tối ưu với điều kiện các covariance là đồng nhất. điều này là hợp lý vì khi các covariance không khác biệt nhau nhiều thì sự khác biệt giữa các giải pháp bậc hai và tuyến tính chỉ đáng kể khi các mẫu cách xa nguyên mẫu như ở hình 10. Chúng ta sẽ minh họa bằng cách sử dụng bộ dữ liệu Norm2c2d. Sai số lý thuyết đối với trường hợp hai lớp, hai chiều và bộ dữ liệu trên là: δ2 = Ước lượng sai số của bộ dữ liệu huấn luyện cho tập dữ liệu này là 5%. Bằng cách đưa vào sai số ±0.1 vào các giá trị của ma trận ánh xạ A cho bộ dữ liệu, với độ lệch nằm giữa 15% và 42% giá rị của covariance, ta được sai số tập huấn luyện là 6%.   0.8 0.8 2 2 3 8 1 ( 2) 7.9% 0.8 1.6 3 Pe erf                Thuật toán Bayes và ứng dụng 19 Trở lại với dữ liệu các nút chai, ta có bài toán phân lớp sử dụng 2 đặc trưng N và PRT với xác suất tiên nghiệm đồng nhất. Lưu ý phân lớp thống kê ngoài tính toán số nó không làm thay đổi các phép toán, vì thế mà các kết quả đạt được là giống nhau nếu như sử dụng PRT hay PRT10. Một danh sách riêng các xác suất hậu nghiệm hữu ích trong tính toán các sai số phân lớp, xem hình 11. Cho các ma trận covariances ở trong bảng 1. Độ lệch của các phần tử trong ma trận covariance so với giá trị trung tâm nằm trong khoảng từ 5% đến 30%. Hình dáng của các cụm là tương tự nhau, đây là bằng chứng để tin rằng việc phân lớp là gần với tối ưu. Bằng cách sử dụng hàm quyết định dựa trên các ma trận covariance riêng lẻ, thay vì chỉ một ma trận tổng covariance, ta sẽ xây dựng được đường biên quyết định bâc hai. Tuy nhiên phân lớp bằng đường bậc hai khó tính độ lệch hơn so với phân lớp tuyến tính, đặc biệt là trong không gian nhiều chiều, và ta cần phải có một lượng lớn tập dữ liệu huấn luyện (xem ví dụ của Fukunaga and Hayes, 1989). Thuật toán Bayes và ứng dụng 20 2.4 Miền quyết định Trong thực tế của các ứng dụng nhân dạng mẫu, đơn giản ta chỉ cần sử dụng một luật quyết định như các công thức (1-2a) và (1-7c) khi đó sẽ tạo ra nhiều biên quyết định, và rất dễ xuất hiện nhiễu ở trong dữ liệu, ảnh hưởng đến độ chính xác của các tính toán phân lớp. Nhiễu mẫu nằm gần biên quyết định có thể thay đổi lớp được gán chỉ với một điều chỉnh nhỏ. Nghĩa là thực tế, phần lớn các mẫu mang đặc điểm của cả 2 lớp. Đối với các mẫu như vậy, thích hợp cho vệc đặt chúng trong một lớp đặc biệt để có thể xem xét kỹ hơn. Điều này chắc chắn phải trong một số ứng dụng, ví dụ như, trong lĩnh vực y tế, nơi ranh giới giữa bình thường và khác thường là cần phải phân tích thêm. Một cách giải quyết là gắn một sự định tính(qualifications) trong việc tính toán xác suất hậu nghiệm P(ωi|x) cho lớp ωi. Chẳng hạn chúng ta gắn định tính "definite" nếu xác suất lớn hơn 0.9, "probable" nếu xác suất giữa 0.9 và 0.8, và "possible" nếu xác suất bé hơn 0.8. Theo cách này thì với nút chai có case 55 (xem hình 11) sẽ được phân lớp là một "possible" cork của lớp "super", và case 54 là một "probable" cork của lớp "average". Thay vì gắn mô tả định tính vào lớp nhận được, một phương pháp khác được sử dụng trong một số trường hợp nhất định đó là quy định cho sự tồn tại của một lớp đặc biệt gọi là lớp từ chối hay là miền quyết định (reject region). Ký hiêu: ω*: lớp được phân; ωi: lớp với xác suất hậu nghiệm cực đại, chẳng hạn P(ωi|x) = max P(wj|x) với mọi lớp ωij # ωi. Luật Bayes có thể viết như sau ω*= ωi Bây giờ ta quy định xác suất hậu nghiệm của một nút chai phải cao hơn nhiều so với một ngưỡng từ chối (reject threshold) nhất định λr, nếu không nó sẽ được phân vào reject class wr. Công thức Bayes được viết lại như sau: (1-14) Khi tính toán tỉ số hợp lý (likelihood ratio) với tỷ số xác suất tiên nghiệm (prevalence ratio), thì ta phải nhân tỉ số này với (1-λr)/λr. Một lớp c không bao giờ có một rejection nếu λr < (c-1)/c, do đó λr Є [(c-1)/c, 1]. * ( | ) ( | ) i i r r i r if P x if P x            Thuật toán Bayes và ứng dụng 21 Chúng ta sẽ minh họa khái niệm reject class sử dụng dữ liệu cork stoppers. Giả sử rằng một reject threshold λr = 0.7 là ngưỡng được quy định. Tính biên quyết định cho reject class là đủ để xác định hàm phân lớp với các xác suất tiên nghiệm P(ω1) = 1-λr = 0.3, P(ω2) = 1-λr = 0.7. Các đường thẳng quyết định là các đường nghiêng và giao với trục tung tại PRT10=15.5 và PRT10=20.1. Chú ý rằng hai đường này có xu hướng đối xứng nhau qua đường thẳng quyết định đã được xác định. Hình 12 là biểu đồ phân tán với các đường quyết định mới. vùng ở giữa hai đường thẳng là reject region. Chúng ta hãy xem các ma trận phân lớp hiển thị trong Hình 13. Nhớ lại một chút ta sẽ thấy rằng có 4 mẫu của lớp 1 và 5 mẫu của lớp 2 bị phân lớp sai, là nằm trong reject region chiếm 9% số mẫu. Số lượng phân lớp sai bây giờ cho lớp 1 là 1mẫu và cho lớp 2 là 5 mẫu, tổng số lỗi là 6%. Thuật toán Bayes và ứng dụng 22 Chương 3 Phân lớp Naive Bayes 3.1 Định nghĩa Naive Bayes classifier là một thuật ngữ trong xử lý số liệu thống kê Bayesian với một phân lớp xác suất dựa trên các ứng dụng định lý Bayes với giả định độc lập bền vững. Một thuật ngữ mô tả chi tiết cho những mô hình xác suất sẽ là “mô hình đặc trưng không phụ thuộc”. Trong thuật ngữ đơn giản, một naive Bayes classifier giả định rằng sự có mặt (hay không có mặt) của một đặc trưng của một lớp học là không liên quan đến sự hiện diện (hay thiếu vắng) của bất kỳ các đặc trưng. Ví dụ, một trái cây có thể được coi là một quả táo nếu nó có màu đỏ chung quanh, và đường kính khoảng 4 inch. Mặc dù các đặc trưng này phụ thuộc vào sự tồn tại của các đặc trưng khác, naive Bayes classifier xem xét tất cả các đặc tính độc lập góp phần vào khả năng trái cây này là quả táo. Tùy thuộc vào tính chính xác bản chất của mô hình xác suất, naive Bayes classifiers có thể được đào tạo rất hiệu quả trong một thiết lập học có giám sát. Trong nhiều ứng dụng thực tế, tham số ước lượng cho các mô hình naive Bayes sử dụng các phương pháp maximum likehood; nói cách khác, có thể làm việc với các mô hình naive Bayes mà không tin ở xác suất Bayesian hoặc bằng cách sử dụng bất cứ phương pháp Bayesian. Mặc dù thiết kế ngây thơ và hình như giả định đơn giản hơn, naive Bayes classifiers thường làm việc trong nhiều tình huống thế giới thực phức tạp tốt hơn có thể mong đợi. Mới đây, xem xét vấn đề phân lớp Bayesian đã có thể thấy có một số lý thuyết giải thích cho tính hiệu quả của naive Bayes classifiers. Một lợi thế của naive Bayes classifier là nó đòi hỏi một số lượng nhỏ dữ liệu đào tạo để ước lượng các tham số (các nghĩa và sự khác nhau của các biến) cần thiết cho việc phân loại. Bởi vì các biến được giả định độc lập, chỉ những khác biệt của các biến cho mỗi lớp học cần phải được xác định và không phải toàn bộ ma trận thống kê. Thuật toán Bayes và ứng dụng 23 3.2 Các mô hình xác suất Naive Bayes Tóm lại, các mô hình xác suất cho một classifier là một mô hình có điều kiện đối với một biến lớp phụ thuộc C với một số lượng nhỏ của các kết quả hay các lớp học, phụ thuộc vài biến đặc trưng F 1 cho tới F n. Vấn đề là nếu số các đặc trưng n là lớn hay khi một đặc trưng có thể chiếm một số lượng lớn các giá trị, sau đó dựa vào một mô hình trên các bảng xác suất là không thể làm được. Do vậy, chúng ta công thức hóa lại các mô hình để dễ xử lý. Bằng cách sử dụng định lý Bayes, có được: Trong thực hành, chỉ cần quan tâm tới tử số của phân số, khi mà mẫu số không phụ thuộc vào C và các giá trị của các đặc trưng của F i đã cho, nên mẫu số là hằng thực sự. Tử số tương đương với mô hình xác suất có thể được viết lại như sau, sử dụng định nghĩa của xác suất có điều kiện: Thuật toán Bayes và ứng dụng 24 Bây giờ giả định "naive" giả định có điều kiện độc lập đưa vào: giả định rằng mỗi đặc trưng Fi có điều kiện độc lập với tất cả các đặc trưng Fj cho j # i. Điều này có nghĩa là do đó có thể được thể hiện như: Điều này có nghĩa là dưới sự độc lập giả định ở trên, các điều kiện phân phối trên các lớp học biến C có thể được thể hiện: ở đây Z là một nhân tố xác định tỷ xích phụ thuộc vào F1, F2, .., Fn, chẳng hạn một hằng số nếu các giá trị của các biến đặc trưng đều được biết. Nếu có k lớp học và nếu một mô hình cho p(Fi) có thể được thể hiện trong các thuật ngữ của r tham số, sau đó các mô hình naive Bayes tương ứng có (k - 1) + nrk tham số. Trong thực tế, thường k = 2 (phân loại nhị phân) và r = 1 (các biến Bernoulli như là các đặc trưng) được phổ biến, và như vậy tổng số lượng các tham số của mô hình naive Bayes là 2n + 1, ở đây n là số các đặc trưng nhị phân sử dụng cho các dự đoán. 3.3 Ước lượng tham số Tất cả các tham số mô hình (tức là, lớp học ưu tiên và các đặc trưng phân phối xác suất) có thể được gần đúng với các tần số liên quan từ việc thiết lập đào tạo. Đây là các đánh giá maximum likehood khả năng có thể xảy ra. Các đặc trưng không riêng biệt cần phải được rời rạc đầu tiên. Sự rời rạc có thể không giám sát (các ràng buộc lựa chọn đặc biệt) hoặc giám sát (ràng buộc hướng dẫn bởi thông tin trong dữ liệu đào tạo). Thuật toán Bayes và ứng dụng 25 Nếu một lớp học và giá trị đặc trưng không bao giờ xảy ra cùng với nhau trong thiết lập đào tạo sau đó ước tính xác suất dựa tần số sẽ được 0. Đây là vấn đề vì nó sẽ phá hủy tất cả các thông tin trong các xác suất khi chúng được nhân rộng. Vì vậy, mong muốn kết hợp một mẫu nhỏ chỉnh sửa trong tất cả các xác suất ước tính rằng như vậy không bao giờ được thiết lập chính xác 0. 3.4 Xây dựng một classifier từ mô hình xác suất Các thảo luận cho đến nay đã bắt nguồn những mô hình đặc trưng độc lập, có nghĩa là, mô hình xác suất naive Bayes. Naive Bayes classifier kết hợp mô hình này với một luật quyết định. Là một luật chung để chọn nhiều nhất các giả thuyết có khả năng xảy ra, điều này được biết đến như là maximum a posteriori hay luật quyết định MAP. Classifier tương ứng là chức năng phân lớp được xác định như sau: Một chú ý rằng giả định độc lập có thể dẫn đến một số kết quả không mong muốn trong tính toán sau xác suất. Trong một số trường hợp khi có một phụ thuộc giữa sự quan sát, xác suất kể trên có thể mâu thuẫn với xác suất tiền đề thứ hai do mọi xác suất luôn nhỏ hơn hoặc bằng một. Mặc dù rằng sự thật có thể áp dụng rộng rãi, giả định độc lập thường không chính xác, các naive Bayes classifier có vài thuộc tính làm cho nó hữu ích trong thực hành. Đặc biệt thực hành, sự tách riêng của lớp có điều kiện phân loại đặc trưng có nghĩa là mỗi phân loại có thể được ước tính độc lập như là một phân phối một chiều. Toàn bộ classifier là mạnh đủ để bỏ qua các thiếu sót nghiêm trọng của nó trong những mô hình xác suất naive. 3.5 Thuật toán phân loại văn bản Naive Bayes Kĩ thuật phân hoạch của Naive Bayes dựa trên cơ sở định lí Bayes và đặc biệt phù hợp cho các trường hợp phân loại có kích thước đầu vào là lớn. Mặc dù Naive Bayes khá đơn giản nhưng nó có khả năng phân loại tốt hơn rất nhiều phương pháp phân hoạch phức tạp khác. Với mỗi loại văn bản, thuật toán Naive Bayes tính cho mỗi Thuật toán Bayes và ứng dụng 26 lớp văn bản một xác suất mà tài liệu cần phân hoạch có thể thuộc loại đó. Tài liệu đó sẽ được gán cho lớp văn bản nào có xác suất cao nhất. Xác suất P(ck| di) gọi là xác suất mà tài liệu di có khả năng thuộc vào lớp văn bản ck được tính toán như sau: tài liệu di sẽ được gán cho loại văn bản nào có xác suất hậu nghiệm cao nhất nên được biểu diễn bằng công thức: trong đó N là tổng số tài liệu. Tóm lại phân loại văn bản sử dụng thuật toán Naive Bayes có thể diễn đạt một cách ngắn gọn như sau: Với mỗi văn bản D (document), người ta sẽ tính cho mỗi loại một xác suất mà tài liệu D có thể thuộc vào lớp tài liệu đó bằng việc sử dụng luật Bayes: (1) Trong đó: D là tài liệu cần phân loại, Ci là một tài liệu bất kì. Theo giả định của Naive Bayes xác suất của mỗi từ trong tài liệu D là độc lập với ngữ cảnh xuất hiện các từ đồng thời cũng độc lập với vị trí của các từ trong tài liệu. Xác suất P(D|Ci) được tính toán từ tần suất xuất hiện của các từ đơn wj (word) trong tài liệu D (2) l là tổng số từ w trong tài liệu D: ( )* ( | )( | ) ( ) i i i P C P D CP C D P D  ( )* ( | )( | ) ( ) k i k k i i P c P d cP c d P d   Class of di arg arg 1 1 ( )* ( | )( | )max max ( ) k i k k i k N k N i P c P d cP c d P d       i j 1 j l P(D|C ) P(w | )iC     Thuật toán Bayes và ứng dụng 27 Như vậy biểu thức (1) có thể được viết lại như sau: )|P(w)( )( )|( lj1 j i i i CDP CPDCP    Giá trị lớn nhất của xác suất P(Ci | D) được đưa ra bởi nguời làm công tác phân loại. Giá trị này được gọi là ngưỡng hay ranh rới giữa các lớp văn bản mà chúng có thể chứa tài liệu D. Ví dụ: Phân loại thư điện tử bằng Naive Bayes classifier Đây là một ví dụ về làm việc naive Bayesian để phân loại các tài liệu phân loại vấn đề. Xem xét các vấn đề của phân loại các tài liệu theo nội dung của họ, ví dụ vào thư rác và không phải là thư rác trong các thư điện tử. Hãy tưởng tượng rằng các tài liệu được lấy ra từ một số lớp học của các tài liệu có thể làm mô hình như là bộ các từ mà ở đây xác suất từ thứ i của một tài liệu xảy ra trong một tài liệu từ lớp C có thể được viết như: Xử lý như vậy đã đơn giản các ý tưởng, hơn nữa bằng cách giả sử rằng xác suất của một từ trong một tài liệu là độc lập với chiều dài của một tài liệu hoặc tất cả các tài liệu cùng một chiều dài. Sau đó, xác suất của một tài liệu D, cho một lớp học C, là Câu hỏi mà mong muốn có câu trả lời là: "xác suất nào để một tài liệu D thuộc về một lớp học C?" Nói cách khác, ? Bây giờ, theo định nghĩa: Thuật toán Bayes và ứng dụng 28 và Nên có: Giả định rằng thời điểm chỉ có hai lớp học, S và ¬ S (ví dụ như thư rác và không phải là thư rác). Bằng cách sử dụng các kết quả Bayesian trên, có thể viết: Do đó: Vì vậy có thể viết: Thuật toán Bayes và ứng dụng 29 Trên thực tế xác suất p(S | D) có thể được tính dễ dàng từ log (p (S | D) / p (¬ S | D)) dựa trên nhận định (S | D) + p (¬ S | D) = 1. Và như vậy: Cuối cùng, các tài liệu có thể được phân loại như sau: Nếu nó là thư rác ,ngược lại nó không phải là thư rác. Thuật toán Bayes và ứng dụng 30 Chương 4 Giải quyết bài toán lọc thư rác 4.1 Đặt vấn đề Thư rác bắt đầu được gọi là "spam" sau chương trình truyền hình có tên "Monty Python’s Flying Circus". Trong show truyền hình này, một nhóm cướp biển Vikings đã vào ăn trong một nhà hàng chuyên phục vụ đồ hộp (spam), rồi hát toáng lên một ca khúc lặp đi lặp lại 2 chữ "quảng cáo". Ý nghĩa ban đầu của thư rác rất rõ ràng: Một thứ lặp đi lặp lại và gây ra sự bực tức, khó chịu cho những người xung quanh. Đó chỉ là trong một phạm vi hẹp còn trong môi trường internet khi không còn khoảng cách về địa lý nữa thì sẽ có rất nhiều người phải chịu sự bực tức, cảnh nhàm chán gây ức chế tâm lý và cực kỳ mất thời gian vào nó. Phần lớn các thư không mời mà đến, các thư chào hàng quảng cáo bị cho là thư rác theo nhận xét của số đông người dùng thư điện tử. Đây là vấn đề nan giải mà các hệ thống, hòm mail, các nhà quản trị mạng đang phải đối mặt trong thời điểm hiện nay khi mà xã hội thông tin ngày càng phát triển với tốc độ chóng mặt. Để lọc và phát hiện thư rác, cần có giải pháp lâu dài như các biện pháp kĩ thuật, quy ước xã hội và có thể dùng đến pháp luật. Nhưng khi các giải pháp này được thi hành thì chỉ trong một khoảng thời gian ngắn chúng đã bị phá vỡ bởi các spammer, nguyên nhân chính là họ luôn nghĩ ra những cái bẫy đánh lừa người dùng hay lách luật mà các tổ chức chống thư rác quy ước. Như vậy giải pháp ngăn chặn thư rác nào hiệu quả và dùng được lâu dài? Một phương pháp tốt nhất đó là để chính người dùng thư điện tử ngăn chặn thư rác, bởi họ hiểu vấn đề một cách tường minh nhất. Chúng ta sẽ dùng cảm nhận về thư rác của mỗi người để huấn luyện cho các bộ lọc thư rác của chính họ. Mỗi bộ lọc sẽ xử lý thư rác tùy theo phong cách của từng người dùng thư điện tử. Và mô hình thống kê Bayes được áp dụng để thực thi ý tưởng này. Từ những đặc điểm trên, ta thấy rằng việc xây dựng được một bộ lọc thư rác thông minh có thể loại bỏ một cách chính xác hiện nay là một nhiệm vụ còn nhiều thách thức. Thuật toán Bayes và ứng dụng 31 4.2 Bài toán Thư điện tử là một trong những phương tiện để giao tiếp đáng tin cậy và hầu như không tốn kém chi phí sử dụng. Phạm vi sử dụng của nó rộng khắp trên toàn thế giới và có thể dễ dàng truy cập bằng hầu hết các phương tiện truyền thông đã biến nó thành nạn nhân của những kẻ spam. Hậu quả đơn giản nhất là làm tốn băng thông mạng và nghiêm trọng hơn là làm mất thời gian của người dùng thư điện tử, làm lan truyền vi rút máy tính. Có thời điểm người ta thống kê được rằng có đến 60% thư điện tử là thư rác và mỗi ngày một người dung thư điện tử phải nhận ít nhất là 6 cú spam. Chúng ta không thể đổi địa chỉ hòm thư mỗi lần bị spam bởi điều này không những không hạn chế được thư rác mà có khi còn làm cho nó gia tăng. Vậy cần phải tìm ra một giải pháp chống thư rác sử dụng bộ lọc được gắn thuật toán phân loại với tính năng hiệu quả và kĩ thuật đơn giản dễ cài đặt. Và một yêu cầu không thể thiếu là có làm sao với thuật toán đó những kẻ spam hiểu rằng việc chúng cố tình spam là vô dụng. 4.3 Tiền xử lý mỗi lá thư điện tử Bộ lọc cá nhân được tích hợp vào mỗi địa chỉ hòm thư của người dùng. Nó luôn luôn ở trạng thái chờ thư đến để xử lý. Một khi thư được gửi đến địa chỉ người dùng thì thư đó phải được phân loại có là thư rác hay không. Nếu là thư rác thì nó bị ném ngay vào thư mục ‘sọt rác’ ngược lại sẽ được cho vào thư mục ‘thư đến’ chờ người dùng duyệt. Để có được kết quả đó là quả một quá trình kiểm duyệt nghiêm ngặt kết hợp nhiều công đoạn như đánh giá địa chỉ người gửi, thư được gửi đến từ IP, DNS nào có nằm trong blacklist của tổ chức chống thư rác quốc tế hay không, hay đơn giản hơn là xem thư đó có sai với định dạng của một lá thư thông thường hay không (ví dụ tiêu đề thư quá nhiều dấu than, dấu hỏi, hay viết hoa toàn bộ, màu sắc nhòe nhoẹt,…. Qua bước sàng lọc ở trên chúng ta bắt đầu tiền xử lý cho bộ lọc Bayes. . Với mỗi thư chúng ta quét toàn bộ văn bản bao gồm header và mã nhúng HTML kể cả javascript của mỗi thông điệp. Hiện tại chúng ta đánh giá các kí tự gồm chữ và số, nét gạch, dấu than và dấu $ vào các thẻ, và những cái còn lại cho vào các thẻ riêng biệt. Bỏ qua các thẻ mà chỉ chứa các chữ số. và cũng bỏ qua các đoạn comment HTML, tách các thẻ đó ra và không cần đánh giá. Như vậy sau bước này một lá thư sẽ ứng với một tập hợp chứa các thẻ riêng biệt. Thuật toán Bayes và ứng dụng 32 4.4 Dùng luật Bayes tính xác suất Tính xác suất cho mỗi thẻ ta dùng luật Bayes để tính. Giả sử ta cần tính xác suất cho thẻ chứa từ ‘promotion’. Từ này chúng ta thường xuyên gặp trong thư điện tử mời chào dịch vụ maketing. Công thức tính theo luật Bayes: Trong đó:  Pr(S|W) là xác suất mà thư mà chứa từ ‘promotion’ là thư rác  Pr(S) là xác suất mà thư bất kì là thư rác  P(W|S) là xác suất mà từ "promotion" xuất hiện trong thư rác  Pr(H) là xác suất mà một bản tin bất kì không là thư rác  P(W|H) là xác suất mà từ "promotion" xuất hiện trong thư rác Như đã nói ở trên, những thống kê gần đây cho thấy 80% thư điện tử là thư rác nên ta sẽ có: Tuy nhiên để cho đơn giản và đã qua thực tế nên người ta chọn các xác suất trước là giống nhau và đều có giá trị bằng 0.5. Tức là: Bộ lọc mà dùng giả thiết này được gọi là "không đối xứng", có nghĩa rằng chúng không có sự đối xử phân biệt các thư đến. Giả thiết này cho phép rút gọn công thức ở trên thành: Bộ lọc thư rác Bayesspam vận dụng chính xác công thức trên để tính xác suất cho mỗi từ đơn. Sau khi đã tính được xác suất thư chứa từ đơn là thư rác ta cần kết hợp các xác suất đơn đó lại thành một xác suất cuối cùng. Xác suất này dùng để đánh giá thư mà Thuật toán Bayes và ứng dụng 33 chứa tất cả các từ đơn đó có xác suất là thư rác là bao nhiêu. Công thức tính xác suất kết hợp là: f Trong đó:  p là xác suất thư đang xét là thư rác  p1là xác suất p(S|W1), ứng với từ đầu tiên (ví dụ từ "promotion")  p2 là xác suất p(S|W2) , ứng với từ thứ hai (ví dụ từ "offer")  ....  pN là xác suất p(S|WN) , ứng với từ thứ N (ví dụ từ "home") Kết quả p thường được dùng so sánh với một ngưỡng nào đó để quyết định thư đang xét có xác suất p đó có là thư rác hay không. Nếu p lớn hơn giá trị ngưỡng, thư đó sẽ bị đánh dấu là thư rác, ngược lại sẽ không bị đánh dấu là thư rác. 4.5 Huấn luyện cho bộ lọc Bayes Sử dụng hai tập thư điện tử huấn luyện, một tập là thư rác và tập còn lại không phải là thư rác. Mỗi tập chứa khoảng 4000 thư. Đếm số lần xuất hiện của mỗi thẻ trong mỗi tập thư điện tử. Mỗi lần đếm kết thúc với hai bảng băm. Mỗi bảng băm tương ứng với mỗi tập thư điện tử, bảng này là ánh xạ các thẻ đến số lần xuất hiện của thẻ đó. Tiếp theo chúng ta tạo ra bảng băm thứ 3, bảng băm này ánh xạ mỗi thẻ tới xác suất mà một email chứa nó là email spam. Ta tính theo công thức sau đây: Thuật toán Bayes và ứng dụng 34 Trong đó:  Ngood ứng với số thư không phải là thư rác.  Nbad ứng với số thư là thư rác. Công thức trên được diễn tả theo các biểu thức của ngôn ngữ Arc. Mỗi biểu thức là một cặp dấu ngoặc đơn. Trong ngoặc là một danh sách với biểu thức đứng ở vị trí đầu tiên theo sau là các tham số. Thực hiện biểu thức từ trái qua phải. Ví dụ: (< (+ g b) 5) tương đương với (g + b) < 5. Công thức này sẽ tính xác suất cho một từ hay thẻ (word) như sau: Thẻ được lấy từ trong bảng good, là bảng băm các thẻ của tập thư không phải là thư rác và nhân đôi lên. Nhân đôi lên để giảm độ chênh lệch xác suất giữa thư rác và không phải thư rác, tăng độ chính xác trong việc phân loại. Tiếp theo cũng thẻ đó ta lấy từ bảng bad, là bảng băm các thẻ tập thư rác. Như vậy ta có chỉ số g ứng với 2 lần suất hiện của thẻ trong tập thư không phải thư rác và b ứng với số lần xuất hiện của thẻ trong trong tập thư rác. Nếu như tổng g và b nhỏ hơn 5 thì thẻ sẽ bị loại bỏ. Xác suất tính được sẽ nằm trong khoảng giá trị từ .01 đến .99. Xét cho cùng thì việc tính toán ở trên tương ứng với công thức tính xác suất ở dạng luật Bayes đơn giản như sau: Như vậy kết quả của quá trình huấn luyện là một bảng băm hay nói khác hơn là một cơ sở dữ liệu rút ra từ tập thư huấn luyện. Bảng băm này là ánh xạ của các thẻ đến các giá trị xác xuất của chúng. Bảng băm này là cơ sở quyết định cho việc tính toán xác suất của một lá thư điện tử là thư rác. 4.6 Lọc thư đến, có là thư rác không? Khi một thư mới đến, nó phải trải qua vài công đoạn xử lý phân loại trước khi đi vào hộp thư người dùng. Tại sao lại thế? Nó cần phải được đánh giá có là thư rác hay không. Lọt qua được bước tiền xử lý lọc thô, người ta lọc đến nội dung của nó có phải là thư rác không bằng cách nội dung text của nó được quét vào các thẻ, thường là mười lăm thẻ sẽ được quan tâm nhất, các thẻ được quan tâm là các thẻ mà xác suất của chúng đạt mức trung bình 0.5, sẽ được dùng để tính toán xác suất mà thư đó có là spam hay không. Cách đây vài năm khi phần cứng máy tính còn nhiều hạn chế, để tiết Thuật toán Bayes và ứng dụng 35 kiệm tài nguyên và tốc độ xử lý thông tin người ta chỉ đặt số thẻ tối đa là mười lăm để tính xác suất thư là thư rác. Ngày nay vấn đề phần cứng dư sức đáp ứng cho ứng dụng lọc thư nên số thẻ không còn bị giới hạn nữa. Khi mà số thẻ không còn bị hạn chế nữa tức là ta phải tính xác suất kết hợp của tất cả chúng. Sẽ có trường hợp thẻ chưa xuất hiện trong bảng băm xác suất. Như vậy phải gán giá trị xác suất nào cho thẻ đó? Kinh nghiệm cho thấy gán giá trị 0.4 là hợp lý. Nói khác hơn thì đây là xác suất ngây thơ. Ta sẽ tính ra xác suất kết hợp của các giá trị xác suất đơn theo công thức sau đây: Đoạn mã trên vận dụng chính xác theo công thức tính xác suất kết hợp xác suất đã trình bày ở mục trên: Kết quả p sau đó sẽ so sánh với ngưỡng để phân loại chính xác thư rác như đã nói ở trên. Như vậy mỗi lần có một thư đến ta sẽ xác định thêm được một thư thuộc loại gì để bổ xung vào tập huấn luyện của bộ lọc. Người ta sắp xếp time để chạy lại quá trình huấn luyện để cập nhật lại hay nói khác hơn là nâng cao tri thức, khả năng phân loại cho bộ lọc. Vì thế mà bộ lọc qua thời gian sử dụng sẽ phân loại càng chính xác khiến người dùng phải bất ngờ vì khả năng phân loại của nó gần như là giống với việc chính người dùng tự phân loại. 4.7 Bộ lọc BayesSpam Bộ lọc BayesSpam thực hiện việc lọc thư điện tử theo quy trình cách thức trình bày ở trên. Ngôn ngữ lập trình được dùng để xây dựng bộ lọc viết bằng ngôn ngữ lập trình Web PHP dưới dạng một plugin rất tiện cho việc tích hợp vào hệ thống thư điện tử. Bộ lọc chạy độc lập với mỗi người dùng. Tức là mỗi người dùng có một bộ lọc cho riêng họ. Bộ lọc BayesSpam cho phép mỗi người dùng thư điện tử tự cấu hình bộ lọc hoặc từ chối dùng bộ lọc. Người dùng gần như làm chủ được bộ lọc trong việc điều chỉnh các thông tin cấu hình. Có thể tham khảo các tính năng cung cấp cho người dùng ở bảng điều khiển trong hình dưới đây. Thuật toán Bayes và ứng dụng 36 Hình 16: Bảng điều khiển bộ lọc dành cho mỗi người dùng thư điện tử Một khi thư bị đánh dấu là thư rác ngay lập tức nó sẽ bị di chuyển vào sọt rác. Và tiêu đề thư sẽ bị đánh dấu thành thư rác [**SPAM/Thư rác**]. Ở hình dưới đây thư rác được cấu hình cho riêng vào thư mục ‘test’. Sau một khoảng thời gian ngắn bộ lọc tự động xây dựng lại cơ sở dữ liệu nó sẽ dùng chính những thư mà nó đã phân loại để cập nhật lại bảng xác suất như đã nói ở trên. Bộ lọc làm việc khá ổn định, tốc độ xử lý thông tin nhanh bởi thuật toán khá ngắn gọn. Mỗi khi có sự kiện mới bộ lọc ngay lập tức tự cập nhật lại cơ sở dữ liệu nhằm gia tăng khả năng lọc thư. Việc huấn luyện cho bộ lọc song song với quá trình sử dụng và phụ thuộc vào cách nhìn nhận thư rác của mỗi người. Nói khác hơn là dần dần theo thời gian sử dụng bộ lọc sẽ mang tính cách duyệt thư điện tử của chính người dùng, người mà cấu hình và huấn luyện nó. Sau bước cấu hình chúng ta có thể dùng bộ lọc ngay chỉ cần thao tác dưới dạng report cho bộ lọc biết đâu là thư rác và có thể đánh giá lại thành không phải thư rác. Thông thường người ta hay dùng nút đánh dấu thư rác, ít khi phải dùng đến nút không phải thư rác. Lúc ban đầu cơ sở dữ liệu của bộ lọc còn nhỏ bé khả năng phân loại sẽ chưa được tốt. Người dùng phải tự nhận dạng thư đến có là thư rác không. Thuật toán Bayes và ứng dụng 37 Nhưng hầu như các thư sau này có nội dung tương tự thư rác mà đánh dấu bởi người dùng sẽ được bộ lọc bắt rất chính xác. Như vậy rõ ràng thời gian sử dụng và cách nhìn nhận về thư rác của người dùng có yếu tố quyết định đối với khả năng phân loại của bộ lọc. Dưới đây là hình ảnh thư rác thử nghiệm để chạy bộ lọc được lấy ra từ thư mục chứa thư rác: Hình 17: Thư rác đã bị lọc và đưa vào thư mục Test, 943 thư rác. Làm thế nào để các Spammer tránh khỏi bộ lọc thư rác? Câu trả lời cho câu hỏi này sẽ là minh chứng cho thấy việc cố gắng ‘spam’ là vô ích khi dùng bộ lọc. Để không bị phát hiện là thư rác các spammer phải cố gắng soạn thư điện tử có nội dung khác với thư mà người bình thường cũng nghĩ được nó là thư rác đến 80% về mặt nội dung thư hay nói chính xác hơn là khác về từ ngữ dùng để viết lên nội dung thư. Sẽ có hai trường hợp xảy ra đó là nếu cứ cố gắng né tránh nội dung, từ ngữ thì bức thư sẽ không thể truyền đạt được nội dung spam. Tức là một lá thư quảng cáo thì không thể thiếu các từ ngữ như ‘mua sắm’, ‘trực tuyến’, ‘miễn phí’, ‘nhân dịp’, ‘mua hàng’, ‘khuyến mại’,… Không dùng các từ ngữ đó spammer không thể soạn được thư rác quảng cáo. Như vậy không thể dùng cách này né tránh bộ lọc được. Còn một cách thứ hai đó là giữ nguyên nội dung quảng cáo nhưng không soạn thư bằng tiếng việt chuẩn nữa mà viết theo ngôn ngữ của teen. Ví dụ như thay dấu ngã thành ‘~’, dấu chấm thành ‘.’, dấu hỏi thành ‘?’…. “Khuye^’n mai. mua hang gia’ re? nha^’t …”. Cách này khá hay về mặt kĩ thuật (làm rối loạn các thẻ từ trong cơ sở dữ liệu nhưng không phải là không khắc phục được) nhưng có khi lại phản tác dụng vì có nhiều người rất ghét và thấy ngứa mắt với kiểu viết chữ như thế nên nhiều spammer phải từ bỏ phương án này. Thuật toán Bayes và ứng dụng 38 Như vậy spammer vẫn xả thư rác bình thường nhưng người dùng thư không bị quấy rối quá nhiều lần khi họ báo cho bộ lọc biết đó là thư rác một vài lần. Các lần sau đó do đã được huấn luyện bộ lọc càng thông minh hơn nó sẽ lọc hết những thư rác một cách chính xác đến không ngờ. Hầu hết những người dùng trung thành với bộ lọc đều đánh giá cao khả năng lọc thư của BayesSpam rất hiệu quả và hầu như là không có sai sót. Và thực tế là nó đang hoạt động khá tốt dưới hệ thống thư điện tử của trường Công nghệ ( 4.8 Một số cải tiến cho bộ lọc BayesSpam Trước khi đề cập đến vấn đề cải tiến ta cần quan tâm đến hạn chế hiện tại của bộ lọc đó là trong một khoảng thời gian dài người dùng thư điện tử không đăng nhập và giả sử lúc ấy người dùng nhận số lượng lớn thư sẽ dẫn đến tình trạng đăng nhập bị chậm ì ạch do chờ lọc thư đến. Để khắc phục tình trạng trên việc lọc thư cần hoạt động theo định kì mà không chờ người dùng đăng nhập. Mỗi thư là một file được đặt trong các thư mục (INBOX, SENT, TRASH,…), bộ lọc sẽ âm thầm lọc thư ngay cả khi người dùng không trực tuyến. Do đây là bộ lọc chung cho mọi người nên nó phải được xây dựng dựa trên phong cách chung, là cái nhìn chung về thư rác của tất cả người dùng. Để làm được điều này bộ lọc phải được huấn luyện kĩ lưỡng dựa trên dữ liệu thư của người dùng. Trong khóa luận này trình bày ứng dụng chọn lọc thư huấn luyện được trích chọn từ thư của tất cả người dùng trong hệ thống thư điện tử Squirrelmail đang dùng bộ lọc BayesSpam. Ứng dụng web viết bằng ngôn ngữ PHP, có giao diện đơn giản dưới đây: Thuật toán Bayes và ứng dụng 39 Hoạt động chính của ứng dụng: 1. Tạo thư mục tập huấn luyện Corpus chứa 2 thư mục con là thư mục thư rác (SPAM) và không phải thư rác (HAM). 2. Dựa trên CSDL của bộ lọc (spamCorpus) lấy ra tên những người đang dùng bộ lọc. 3. Với mỗi người dùng, copy tất cả file thư trong thư mục sọt rác (TRASH) vào thư mục SPAM. Tương tự copy tất cả các file trong thư mục hộp thư (INBOX) vào thư mục (HAM). 4. Xử lý thư mục SPAM. Chọn lọc các thư có chỉ số Bayes cao (lớn hơn ngưỡng đưa ra) ứng với thư có xác suất là thư rác cao hơn các thư cùng loại trong thư mục. Dựa vào thuộc tính messageID của bảng ScoreCache trong CSDL. 5. Xử lý thư mục HAM. Chọn lọc các thư có chỉ số Bayes thấp (nhỏ hơn ngưỡng đưa ra) ứng với thư có xác suất không là thư rác cao hơn các thư cùng loại trong thư mục. Dựa vào messageID trong bảng ScoreCache. Sau quá trình trên ta có được tập huấn luyện được chọn lọc từ mỗi người dùng bộ lọc. Tập huấn luyện này như là một cái nhìn chung về thư rác của tất cả mọi người dùng bộ lọc. Có thể dùng tập huấn luyện này để huấn luyện cho bộ lọc đề cập ở trên Thuật toán Bayes và ứng dụng 40 Chương 5 Kết luận Như đã nói từ đầu toán học thống kê đóng vai trò rất quan trọng trọng trong mọi lĩnh vực. Thống kê giúp cho việc nắm bắt đánh giá tình hình trở lên trực quan và dễ hiểu hơn. Xử lý và ứng dụng dữ liệu thống kê đem lại hiệu quả lớn lao trong việc tiên đoán và từ đó có thể xây dựng lên một hệ tự động hóa hoạt động chính xác. Hướng tiếp cận thống kê theo lý thuyết Bayes khá đơn giản nhưng đem lại hiệu quả rất cao chính vì thế mà nó được ứng dụng khá phổ biến trong hầu hết các lĩnh vực. So với các phương pháp khác, phương pháp thống kê Bayes lập luận theo kinh nghiệm được tích lũy áp dụng vào mô hình phân loại đối tượng linh hoạt hơn, phù hợp với đặc trưng của bài toán hơn. Các cơ chế ước lượng cũng gần gũi với cách suy luận thông thường chính vì vậy mà các kết quả phân loại tương đối giống với cách phân loại thông thường. Các kết quả đã đạt được là: Khoá luận đã tập trung nghiên cứu về lý thuyết Bayes, từ bước cơ sở đó tìm hiểu tiếp về một ứng dụng của nó liên quan trực tiếp đến ngành công nghệ thông tin đó là ứng dụng lọc thư rác. Quá trình tìm hiểu về nguyên lý và cách thức hoạt động của bộ lọc đã rút ra được những kết luận về ưu nhược điểm của tiếp cận thống kê Bayes trong việc phân loại thư rác. Đối với vấn đề ứng dụng thực tế, khoá luận sử dụng plugin BayesSpam như một đối tượng chính để tìm hiểu và nghiên cứu. Đối với vấn đề áp dụng lý thuyết Bayes, khoá luận nghiên cứu xây dựng các công thức tính xác suất sao cho việc xử lý thông tin trở lên nhanh gọn và có độ chính xác cao. Từ việc tìm hiểu ứng dụng BayesSpam, khoá luận đã rút ra được một số nhận định về ưu điểm và nhược điểm của bộ lọc trong quá trình hoạt động. Kết quả phân loại thư rác nhìn chung là gần giống với các kết quả đánh giá thư bởi người dùng. Tuy nhiên, do thời gian có hạn cũng như các kiến thức chuyên môn về hệ thống thư điện tử nên các kết luận rút ra được trong quá trình nghiên cứu còn nhiều hạn chế. Dưới đây là những ưu nhược điểm chính của bộ lọc thư rác Bayes. Những ưu điểm chính:  Ưu điểm của bộ lọc thư rác Bayes đó là nó có thể được huấn luyện bởi chính người dùng cơ sở. Đây có thể thể nói là ưu điểm lớn nhất, nó tạo ra được nét đặc trưng về cách nhìn nhận thư rác của mỗi người dùng. Thuật toán Bayes và ứng dụng 41  Các thư rác mà một người dùng nhận được thường liên quan tới các hoạt động trực tuyến của người dùng. Ví dụ, một người sử dụng có thể đã được đăng ký vào một bản tin trực tuyến mà người sử dụng xem xét như là thư rác. Đang xem thông tin này có thể chứa các từ ngữ được phổ biến cho tất cả các bản tin, chẳng hạn như tên của bản tin và nguồn gốc của nó địa chỉ email. Bộ lọc thư rác Bayesian sẽ chỉ định một xác suất cao hơn dựa trên cách nhìn nhận của người sử dụng.  Thư điện thử hợp pháp sẽ nhận được nhìn nhận theo xu hướng khác nhau đối với mỗi người. Ví dụ, trong môi trường một công ty, tên công ty của bạn và tên của khách hàng sẽ được đề cập thường xuyên. Các bộ lọc sẽ chỉ định một thư rác xác suất thấp hơn cho các email có chứa các tên đó.  Xác suất của các từ là duy nhất đối với mỗi người dùng và có thể lớn dần theo thời gian huấn luyện, cùng với sự hiệu chỉnh việc huấn luyện mỗi khi có thư lọc sai. Kết quả là, lọc thư rác Bayesian tăng độ chính xác khi được đào tạo thường xuyên theo các quy tắc được xác định trước. Những nhược điểm chính:  Một kỹ thuật được sử dụng bởi Spammer nhằm cố gắng để giảm tính hiệu quả của bộ lọc thư rác là dựa vào chính nguyên tắc hoạt động của nó. Kĩ thuật này sẽ chèn các từ mà không phải là bình thường liên kết với các nội dung spam với số lượng lớn văn bản hợp pháp (thu thập từ các nguồn tin tức hợp pháp hay văn chương). Do đó giảm giá trị xác suất kết hợp của thư điện tử là thư rác, làm cho nó càng có nhiều khả năng vượt qua bộ lọc thư rác Bayes.  Một kỹ thuật khác được sử dụng để che mắt bộ lọc thư rác Bayes đó là thay thế các văn bản bằng hình ảnh, hoặc trực tiếp đặt liên kết chứa nội dung spam đến hình ảnh. Toàn bộ nội dung của tin nhắn, hoặc một số phần của nó, được thay thế bằng một hình ảnh có cùng một nội dung được trình bày lôi cuốn người xem. Bộ lọc thư rác thường không thể phân tích hình ảnh này, mà có thể chứa các từ nhạy cảm như "khiêu dâm". Tuy nhiên, nhiều hệ thống thư điên tử đã vô hiệu hoá màn hình hiển thị của liên kết hình ảnh vì lý do bảo mật, nhưng các spammer lại gửi liên kết đến hình ảnh ở xa có thể tiếp cận với các mục tiêu spam ít hơn. Ngoài ra, một hình ảnh có kích thước lớn hơn kích thước tương đương của văn bản. Do đó, các spammer cần nhiều hơn nhu cầu băng thông để gửi tin nhắn trực tiếp bao gồm cả hình ảnh. Thuật toán Bayes và ứng dụng 42 Do vậy, sau bước tìm hiểu lý thuyết và ứng dụng thì hướng nghiên cứu tiếp của đề tài nhằm tăng hiệu quả lọc là:  Tìm ra cái nhìn chung về thư rác của những người dùng thư trong cùng hệ thống thư điện tử. Bằng cách rút ra những email có xác suất là thư rác cao để bổ xung vào tập huấn luyện chung cho tất cả mọi người nhằm gia tăng kinh nghiệm cho bộ lọc.  Ngăn chặn việc Spam bằng hình ảnh bằng việc đưa ra thông báo là thư rác nếu nó có nội dung chủ yếu là đồ họa. Đơn giản nhất là không cho hiển thị hình ảnh khi người dùng duyệt thư trừ khi họ có nhu cầu xem hình ảnh thì tự họ sẽ bật hiển thị.  Tích hợp phân tích hình ảnh để lấy ra văn bản trong hình nhằm giảm việc lọc sai do loại bỏ tất cả thư có nội dung chủ yếu đồ họa. Việc này đòi hỏi hệ thống phải mạnh cùng thuật toán phân tích hình ảnh thông minh.  Bổ xung thêm vào tập các từ trung tính tiếng Việt cho bộ lọc nhằm tăng tốc và tiết kiệm tài nguyên cho cơ sở dữ liệu. Ví dụ như các từ trung tính tiếng việt ứng với các từ trung tính tiếng Anh như: thì, là, ở, cái, con, và, hoặc, …. Thuật toán Bayes và ứng dụng 43 Phụ lục A Cơ sở dữ liệu của bộ lọc Thuật toán Bayes và ứng dụng 44 Tài liệu tham khảo [1] Nguyễn Quốc Đại, Lý Thuyết Bayes, mạng Bayes. (2009) [2] Nguyễn Thanh Sơn, Lê Khánh Luận; Lý thuyết xác suất và thống kê toán; Nxb Thống kê (2008) [3] Nguyễn Duy Tiến, Trần Minh Ngọc Đại học Khoa Học Tự Nhiên, ĐHQGHN, Bài giảng của Viện Thống Kê Thế Giới IMS tại Malaysia [4] Azam. N, Dar. H. A, Marwat. S; Comparative study on Feature Space Reduction for Spam Detection [5] Paul Graham; A plan for spam – 2002. Xem tại địa chỉ [6] Wikipedia ; Bayesian Spam Filtering. Xem tại địa chỉ [7] Wikipedia ; Sequential Bayesian Filtering. Xem tại địa chỉ