單純貝氏分類器
單純貝氏分類器(英語:Naive Bayes classifier,中國大陸稱為樸素貝葉斯分類器),在機器學習中是一系列以假設特徵之間強(樸素)獨立下運用貝氏定理為基礎的簡單機率分類器。
單純貝氏自1950年代已廣泛研究,在1960年代初就以另外一個名稱引入到文字資訊檢索界中,[1]:488 並仍然是文字分類的一種熱門(基準)方法,文字分類是以詞頻為特徵判斷檔案所屬類別或其他(如垃圾郵件、合法性、體育或政治等等)的問題。通過適當的預處理,它可以與這個領域更先進的方法(包括支持向量機)相競爭。[2] 它在自動醫療診斷中也有應用。[3]
單純貝氏分類器是高度可延伸的,因此需要數量與學習問題中的變數(特徵/預測器)成線性關係的參數。最大概似訓練可以通過評估一個封閉形式的表達式來完成,[1]:718 只需花費線性時間,而不需要其他很多類型的分類器所使用的費時的迭代逼近。
在統計學和電腦科學文獻中,單純貝氏模型有各種名稱,包括簡單貝氏和獨立貝氏。[4] 所有這些名稱都參考了貝氏定理在該分類器的決策規則中的使用,但單純貝氏不(一定)用到貝氏方法;[4] 《Russell和Norvig》提到「『單純貝氏』有時被稱為貝氏分類器,這個馬虎的使用促使真正的貝氏論者稱之為傻瓜貝氏模型。」[1]:482
簡介
編輯單純貝氏是一種建分類器的簡單方法。該分類器模型會給問題實例分配用特徵值表示的類標籤,類標籤取自有限集合。它不是訓練這種分類器的單一演算法,而是一系列基於相同原理的演算法:所有單純貝氏分類器都假定樣本每個特徵與其他特徵都不相關。舉個例子,如果一種水果其具有紅,圓,直徑大概3英寸等特徵,該水果可以被判定為是蘋果。儘管這些特徵相互依賴或者有些特徵由其他特徵決定,然而單純貝氏分類器認為這些屬性在判定該水果是否為蘋果的機率分布上獨立的。
對於某些類型的機率模型,在監督式學習的樣本集中能取得得非常好的分類效果。在許多實際應用中,單純貝氏模型參數估計使用最大概似估計方法;換而言之,在不用到貝氏機率或者任何貝氏模型的情況下,單純貝氏模型也能奏效。
儘管是帶著這些樸素思想和過於簡單化的假設,但單純貝氏分類器在很多複雜的現實情形中仍能夠取得相當好的效果。2004年,一篇分析貝氏分類器問題的文章揭示了單純貝氏分類器取得看上去不可思議的分類效果的若干理論上的原因。[5] 儘管如此,2006年有一篇文章詳細比較了各種分類別方法,發現更新的方法(如決策樹和隨機森林)的效能超過了貝氏分類器。[6]
單純貝氏分類器的一個優勢在於只需要根據少量的訓練資料估計出必要的參數(變數的均值和變異數)。由於變數獨立假設,只需要估計各個變數的方法,而不需要確定整個共變異數矩陣。
單純貝氏機率模型
編輯理論上,機率模型分類器是一個條件機率模型。
獨立的類別變數 有若干類別,條件依賴於若干特徵變數 , ,..., 。但問題在於如果特徵數量 較大或者每個特徵能取大量值時,基於機率模型列出機率表變得不現實。所以我們修改這個模型使之變得可行。 貝氏定理有以下式子:
用樸素的語言可以表達為:
實際中,我們只關心分式中的分子部分,因為分母不依賴於 而且特徵 的值是給定的,於是分母可以認為是一個常數。這樣分子就等價於聯合分布模型。
現在「樸素」的條件獨立假設開始發揮作用:假設每個特徵 對於其他特徵 , 在給定類別 下是條件獨立的。這就意味著
對於 ,所以聯合分布模型可以表達為
這意味著上述假設下,類別變數 的條件分布可以表達為:
其中 (證據因子)是一個只依賴與 等的縮放因子,當特徵變數的值已知時是一個常數。 由於分解成所謂的類事前機率 和獨立機率分布 ,上述機率模型的可掌控性得到很大的提高。如果這是一個 分類問題,且每個 可以表達為 個參數,於是相應的單純貝氏模型有(k − 1) + n r k個參數。實際應用中,通常取 (二分類問題), (伯努利分布作為特徵),因此模型的參數個數為 ,其中 是二值分類特徵的個數。
從機率模型中構造分類器
編輯討論至此為止我們匯出了獨立分布特徵模型,也就是單純貝氏機率模型。單純貝氏分類器包括了這種模型和相應的決策規則。一個普通的規則就是選出最有可能的那個:這就是大家熟知的最大事後機率(MAP)決策準則。相應的分類器便是如下定義的 公式:
參數估計
編輯所有的模型參數都可以通過訓練集的相關頻率來估計。常用方法是機率的最大概似估計。類的事前機率可以通過假設各類等機率來計算(事前機率 = 1 / (類的數量)),或者通過訓練集的各類樣本出現的次數來估計(A類事前機率=(A類樣本的數量)/(樣本總數))。為了估計特徵的分布參數,我們要先假設訓練集資料滿足某種分布或者無母數模型。[7]
高斯單純貝氏
編輯如果要處理的是連續資料一種通常的假設是這些連續數值為高斯分布。 例如,假設訓練集中有一個連續屬性, 。我們首先對資料根據類別分類,然後計算每個類別中 的均值和變異數。令 表示為 在c類上的均值,令 為 在c類上的變異數。在給定類中某個值的機率, ,可以通過將 表示為均值為 變異數為 常態分布計算出來。如下, 處理連續數值問題的另一種常用的技術是通過離散化連續數值的方法。通常,當訓練樣本數量較少或者是精確的分布已知時,通過機率分布的方法是一種更好的選擇。在大量樣本的情形下離散化的方法表現更優,因為大量的樣本可以學習到資料的分布。由於單純貝氏是一種典型的用到大量樣本的方法(越大計算量的模型可以產生越高的分類精確度),所以單純貝氏方法都用到離散化方法,而不是機率分布估計的方法。
樣本修正
編輯如果一個給定的類和特徵值在訓練集中沒有一起出現過,那麼基於頻率的估計下該機率將為0。這將是一個問題。因為與其他機率相乘時將會把其他機率的資訊統統去除。所以常常要求要對每個小類樣本的機率估計進行修正,以保證不會出現有為0的機率出現。
討論
編輯儘管實際上獨立假設常常是不準確的,但單純貝氏分類器的若干特性讓其在實踐中能夠取得令人驚奇的效果。特別地,各類條件特徵之間的解耦意味著每個特徵的分布都可以獨立地被當做一維分布來估計。這樣減輕了由於維數災帶來的阻礙,當樣本的特徵個數增加時就不需要使樣本規模呈指數增長。然而單純貝氏在大多數情況下不能對類機率做出非常準確的估計,但在許多應用中這一點並不要求。例如,單純貝氏分類器中,依據最大事後機率決策規則只要正確類的事後機率比其他類要高就可以得到正確的分類。所以不管機率估計輕度的甚至是嚴重的不精確都不影響正確的分類結果。在這種方式下,分類器可以有足夠的強健性去忽略單純貝氏機率模型上存在的缺陷。
實例
編輯性別分類
編輯問題描述:通過一些測量的特徵,包括身高、體重、腳的尺寸,判定一個人是男性還是女性。
訓練
編輯訓練資料如下:
性別 | 身高(英尺) | 體重(磅) | 腳的尺寸(英寸) |
---|---|---|---|
男 | 6 | 180 | 12 |
男 | 5.92 (5'11") | 190 | 11 |
男 | 5.58 (5'7") | 170 | 12 |
男 | 5.92 (5'11") | 165 | 10 |
女 | 5 | 100 | 6 |
女 | 5.5 (5'6") | 150 | 8 |
女 | 5.42 (5'5") | 130 | 7 |
女 | 5.75 (5'9") | 150 | 9 |
假設訓練集樣本的特徵滿足高斯分布,得到下表:
性別 | 均值(身高) | 變異數(身高) | 均值(體重) | 變異數(體重) | 均值(腳的尺寸) | 變異數(腳的
尺寸) |
---|---|---|---|---|---|---|
男性 | 5.855 | 3.5033e-02 | 176.25 | 1.2292e+02 | 11.25 | 9.1667e-01 |
女性 | 5.4175 | 9.7225e-02 | 132.5 | 5.5833e+02 | 7.5 | 1.6667e+00 |
我們認為兩種類別是等機率的,也就是P(male)= P(female) = 0.5。在沒有做辨識的情況下就做這樣的假設並不是一個好的點子。但我們通過資料集中兩類樣本出現的頻率來確定P(C),我們得到的結果也是一樣的。
測試
編輯以下給出一個待分類是男性還是女性的樣本。
性別 | 身高(英尺) | 體重(磅) | 腳的尺寸(英寸) |
---|---|---|---|
未知性別的樣本 | 6 | 130 | 8 |
我們希望得到的是男性還是女性哪類的事後機率大。男性的事後機率通過下面式子來求取
女性的事後機率通過下面式子來求取
證據因子(通常是常數)用來對各類的事後機率之和進行歸一化.
證據因子是一個常數(在常態分布中通常是正數),所以可以忽略。接下來我們來判定這樣樣本的性別。
,其中 , 是訓練集樣本的常態分布參數. 注意,這裡的值大於1也是允許的 – 這裡是機率密度而不是機率,因為身高是一個連續的變數.
由於女性事後機率的分子比較大,所以我們預計這個樣本是女性。
文字分類
編輯這是一個用單純貝氏分類做的一個文字分類問題的例子。考慮一個基於內容的文字分類問題,例如判斷郵件是否為垃圾郵件。想像文字可以分成若干的類別,首先文字可以被一些單詞集標註,而這個單詞集是獨立分布的,在給定的C類文字中第i個單詞出現的機率可以表示為:
(通過這種處理,我們進一步簡化了工作,假設每個單詞是在文中是隨機分布的-也就是單詞不依賴於文字的長度,與其他詞出現在文中的位置,或者其他文字內容。)
所以,對於一個給定類別C,文字D包含所有單詞 的機率是:
我們要回答的問題是「文件D屬於類C的機率是多少?」換而言之 是多少? 現在定義
通過貝氏定理將上述機率處理成概似度的形式
- 假設現在只有兩個相互獨立的類別,S和¬S(垃圾郵件和非垃圾郵件),這裡每個元素(郵件)要麼是垃圾郵件,要麼就不是。
用上述貝氏的結果,可以寫成
兩者相除:
整理得:
這樣機率比p(S | D) / p(¬S | D)可以表達為概似比。實際的機率p(S | D)可以很容易通過log (p(S | D) / p(¬S | D))計算出來,基於p(S | D) + p(¬S | D) = 1。
結合上面所討論的機率比,可以得到:
(這種對數概似比的技術在統計中是一種常用的技術。在這種兩個獨立的分類情況下(如這個垃圾郵件的例子),把對數概似比轉化為S曲線的形式)。
最後文字可以分類,當 或者 時判定為垃圾郵件,否則為正常郵件。
參見
編輯參考文獻
編輯- ^ 1.0 1.1 1.2 Russell, Stuart; Norvig, Peter. Artificial Intelligence: A Modern Approach 2nd. Prentice Hall. 2003 [1995]. ISBN 978-0137903955.
- ^ Rennie, J.; Shih, L.; Teevan, J.; Karger, D. Tackling the poor assumptions of Naive Bayes classifiers (PDF). ICML. 2003 [2012-04-01]. (原始內容存檔 (PDF)於2023-11-29).
- ^ Rish, Irina. An empirical study of the naive Bayes classifier (PDF). IJCAI Workshop on Empirical Methods in AI. 2001 [2012-04-01]. (原始內容存檔 (PDF)於2017-12-10).
- ^ 4.0 4.1 Hand, D. J.; Yu, K. Idiot's Bayes — not so stupid after all?. International Statistical Review. 2001, 69 (3): 385–399. ISSN 0306-7734. doi:10.2307/1403452.
- ^ Harry Zhang "The Optimality of Naive Bayes". FLAIRS2004 conference. (available online: PDF (頁面存檔備份,存於網際網路檔案館))
- ^ Caruana, R. and Niculescu-Mizil, A.: "An empirical comparison of supervised learning algorithms". Proceedings of the 23rd international conference on Machine learning, 2006. (available online [1] (頁面存檔備份,存於網際網路檔案館))
- ^ George H. John and Pat Langley (1995). Estimating Continuous Distributions in Bayesian Classifiers. Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. pp. 338-345. Morgan Kaufmann, San Mateo.
延伸閱讀
編輯- Domingos, Pedro; Pazzani, Michael. On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning. 1997, 29: 103–137 [2012-04-01]. (原始內容存檔於2008-04-18).
- Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6.[永久失效連結]
- Mozina, M.; Demsar, J.; Kattan, M.; Zupan, B. Nomograms for Visualization of Naive Bayesian Classifier (PDF). Proc. PKDD-2004: 337–348. 2004 [2015-05-30]. (原始內容存檔 (PDF)於2023-11-29).
- Maron, M. E. Automatic Indexing: An Experimental Inquiry. JACM. 1961, 8 (3): 404–417. doi:10.1145/321075.321084.
- Minsky, M. Steps toward Artificial Intelligence. Proc. IRE 49 (1): 8–30. 1961.
外部連結
編輯- Book Chapter: Naive Bayes text classification, Introduction to Information Retrieval (頁面存檔備份,存於網際網路檔案館)
- Naive Bayes for Text Classification with Unbalanced Classes (頁面存檔備份,存於網際網路檔案館)
- Benchmark results of Naive Bayes implementations (頁面存檔備份,存於網際網路檔案館)
- Hierarchical Naive Bayes Classifiers for uncertain data (頁面存檔備份,存於網際網路檔案館) (an extension of the Naive Bayes classifier).
- 軟體
- Naive Bayes classifiers are available in many general-purpose machine learning and NLP packages, including Apache Mahout, Mallet (頁面存檔備份,存於網際網路檔案館), NLTK, Orange, scikit-learn and Weka.
- IMSL Numerical Libraries Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Data mining routines in the IMSL Libraries include a Naive Bayes classifier.
- Winnow content recommendation Open source Naive Bayes text classifier works with very small training and unbalanced training sets. High performance, C, any Unix.
- An interactive Microsoft Excel spreadsheet Naive Bayes implementation (頁面存檔備份,存於網際網路檔案館) using VBA (requires enabled macros) with viewable source code.
- jBNC - Bayesian Network Classifier Toolbox (頁面存檔備份,存於網際網路檔案館)
- Statistical Pattern Recognition Toolbox for Matlab (頁面存檔備份,存於網際網路檔案館).
- ifile (頁面存檔備份,存於網際網路檔案館) - the first freely available (Naive) Bayesian mail/spam filter
- NClassifier (頁面存檔備份,存於網際網路檔案館) - NClassifier is a .NET library that supports text classification and text summarization. It is a port of Classifier4J.
- Classifier4J (頁面存檔備份,存於網際網路檔案館) - Classifier4J is a Java library designed to do text classification. It comes with an implementation of a Bayesian classifier.