樸素貝葉斯分類器

單純貝氏分類器（Naive Bayes classifier），在機器學習中是一系列以假設特徵之間強（樸素）獨立下運用貝葉斯定理為基礎的簡單機率分類法。

單純貝氏自1950年代已廣泛研究，在1960年代初就以另外一個名稱引入到文本資訊檢索界中，並仍然是文本分類的一種熱門（基準）方法，文本分類是以詞頻為特徵判斷文件所屬類別或其他（如垃圾郵件、合法性、體育或政治等等）的問題。通過適當的預處理，它可以與這個領域更先進的方法（包括支持向量機）相競爭。它在自動醫療診斷中也有應用。

單純貝氏分類器是高度可擴展的，因此需要數量與學習問題中的變量（特徵/預測器）成線性關係的參數。最大似然訓練可以通過評估一個封閉形式的表達式來完成，只需花費線性時間，而不需要其他很多類型的分類器所使用的費時的迭代逼近。

在統計學和電腦科學文獻中，單純貝氏模型有各種名稱，包括簡單貝葉斯和獨立貝葉斯。所有這些名稱都參考了貝葉斯定理在該分類器的決策規則中的使用，但單純貝氏不（一定）用到貝葉斯方法；《人工智慧——一種現代方法》提到「『單純貝氏』有時被稱為貝葉斯分類器，這個馬虎的使用促使真正的貝葉斯論者稱之為傻瓜貝葉斯模型。」

## 簡介

單純貝氏是一種建分類器的簡單方法。該分類器模型會給問題實例分配用特徵值表示的類標籤，類標籤取自有限集合。它不是訓練這種分類器的單一演算法，而是一系列基於相同原理的演算法：所有單純貝氏分類器都假定樣本每個特徵與其他特徵都不相關。舉個例子，如果一種水果其具有紅，圓，直徑大概3英寸等特徵，該水果可以被判定為是蘋果。儘管這些特徵相互依賴或者有些特徵由其他特徵決定，然而單純貝氏分類器認為這些屬性在判定該水果是否為蘋果的機率分布上獨立的。

對於某些類型的機率模型，在監督式學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，單純貝氏模型參數估計使用最大似然估計方法；換而言之，在不用到貝葉斯機率或者任何貝葉斯模型的情況下，單純貝氏模型也能奏效。

儘管是帶著這些樸素思想和過於簡單化的假設，但單純貝氏分類器在很多複雜的現實情形中仍能夠取得相當好的效果。2004年，一篇分析貝葉斯分類器問題的文章揭示了單純貝氏分類器取得看上去不可思議的分類效果的若干理論上的原因。儘管如此，2006年有一篇文章詳細比較了各種分類方法，發現更新的方法（如決策樹和隨機森林）的性能超過了貝葉斯分類器。

單純貝氏分類器的一個優勢在於只需要根據少量的訓練數據估計出必要的參數（變量的均值和方差）。由於變量獨立假設，只需要估計各個變量的方法，而不需要確定整個協方差矩陣。

## 單純貝氏機率模型

理論上，機率模型分類器是一個條件概率模型。

$$p(C \vert F_1,\dots,F_n)\,$$

獨立的類別變量$C$有若干類別，條件依賴於若干特徵變量$F_1$,$F_2$,...,$F_n$。但問題在於如果特徵數量$n$較大或者每個特徵能取大量值時，基於機率模型列出機率表變得不現實。所以我們修改這個模型使之變得可行。

貝葉斯定理有以下式子：

$$p(C \vert F_1,\dots,F_n) = \frac{p(C) \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)}. \,$$

用樸素的語言可以表達為：

$$\mbox{posterior} = \frac{\mbox{prior} \times \mbox{likelihood}}{\mbox{evidence}}. \,$$

實際中，我們只關心分式中的分子部分，因為分母不依賴於$C$而且特徵$F_i$的值是給定的，於是分母可以認為是一個常數。這樣分子就等價於聯合分布模型。

$$p(C, F_1, \dots, F_n)\,$$

重複使用鏈式法則，可將該式寫成條件概率的形式，如下所示：

$$p(C, F_1, \dots, F_n)\,$$

$$\varpropto p(C) \ p(F_1,\dots,F_n\vert C)$$

$$\varpropto p(C) \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1)$$

$$\varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3,\dots,F_n\vert C, F_1, F_2)$$

$$\varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3)$$

$$\varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ \dots p(F_n\vert C, F_1, F_2, F_3,\dots,F_{n-1}).$$

現在「樸素」的條件獨立假設開始發揮作用：假設每個特徵$F_i$對於其他特徵$F_j$,$j\neq i$在給定類別$C$下是條件獨立的。這就意味著

$$p(F_i \vert C, F_j) = p(F_i \vert C)\,$$

對於$i\ne j$，所以聯合分布模型可以表達為

$$\begin{align} p(C \vert F_1, \dots, F_n) & \varpropto p(C, F_1, \dots, F_n)\\ & \varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots\, \\& \varpropto p(C) \prod_{i=1}^n p(F_i \vert C).\,\end{align}$$

這意味著上述假設下，類變量$C$的條件分布可以表達為：

$$p(C \vert F_1,\dots,F_n) = \frac{1}{Z} p(C) \prod_{i=1}^n p(F_i \vert C)$$

其中$Z$（證據因子）是一個只依賴與$F_1,\dots,F_n$等的縮放因子，當特徵變量的值已知時是一個常數。

由於分解成所謂的類先驗概率$p(C)$和獨立機率分布$p(F_i\vert C)$，上述機率模型的可掌控性得到很大的提高。如果這是一個$k$分類問題，且每個$p(F_i\vert C=c)$可以表達為$r$個參數，於是相應的單純貝氏模型有(k − 1) + n r k個參數。實際應用中，通常取$k=2$（二分類問題），$r=1$（伯努利分布作為特徵），因此模型的參數個數為$2n+1$，其中$n$是二值分類特徵的個數。

### 從機率模型中構造分類器

討論至此為止我們導出了獨立分布特徵模型，也就是單純貝氏機率模型。單純貝氏分類器包括了這種模型和相應的決策規則。一個普通的規則就是選出最有可能的那個：這就是大家熟知的最大後驗概率（MAP）決策準則。相應的分類器便是如下定義的$\mathrm{classify}$公式：

$$\mathrm{classify}(f_1,\dots,f_n) = \underset{c}{\operatorname{argmax}} \ p(C=c) \displaystyle\prod_{i=1}^n p(F_i=f_i\vert C=c).$$

## 參數估計

所有的模型參數都可以通過訓練集的相關頻率來估計。常用方法是機率的最大似然估計。類的先驗概率可以通過假設各類等機率來計算（先驗概率 = 1 / (類的數量)），或者通過訓練集的各類樣本出現的次數來估計（A類先驗概率=（A類樣本的數量）/(樣本總數)）。為了估計特徵的分布參數，我們要先假設訓練集數據滿足某種分布或者非參數模型。

### 高斯單純貝氏

如果要處理的是連續數據一種通常的假設是這些連續數值為高斯分布。

例如，假設訓練集中有一個連續屬性，$x$。我們首先對數據根據類別分類，然後計算每個類別中$x$的均值和方差。令$\mu_c$ 表示為$x$在c類上的均值，令$\sigma^2_c$為 $x$在c類上的方差。在給定類中某個值的機率，$P(x=v|c)$，可以通過將$v$表示為均值為$\mu_c$方差為$\sigma^2_c$正態分布計算出來。如下。

$$P(x=v|c)=\tfrac{1}{\sqrt{2\pi\sigma^2_c}}\,e^{ -\frac{(v-\mu_c)^2}{2\sigma^2_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

我們希望得到的是男性還是女性哪類的後驗概率大。男性的後驗概率通過下面式子來求取

$$posterior (male) = \frac{P(male) \, p(height | male) \, p(weight | male) \, p(foot size | male)}{evidence}$$

女性的後驗概率通過下面式子來求取

$$posterior (female) = \frac{P(female) \, p(height | female) \, p(weight | female) \, p(foot size | female)}{evidence}$$

證據因子（通常是常數）用來對各類的後驗概率之和進行歸一化.

$$evidence = P(male) \, p(height | male) \, p(weight | male) \, p(foot size | male) + P(female) \, p(height | female) \, p(weight | female) \, p(foot size | female)$$

證據因子是一個常數（在正態分布中通常是正數），所以可以忽略。接下來我們來判定這樣樣本的性別。

$$P(male) = 0.5$$

$p(\mbox{height} | \mbox{male}) = \frac{1}{\sqrt{2\pi \sigma^2}}\exp\left(\frac{-(6-\mu)^2}{2\sigma^2}\right) \approx 1.5789$,其中$\mu = 5.855$，$\sigma^2 = 3.5033e^{-02}$是訓練集樣本的正態分布參數. 注意，這裡的值大於1也是允許的 – 這裡是機率密度而不是機率，因為身高是一個連續的變量.

$$p(weight | male) = 5.9881e^{-06}$$

$$p(foot size | male) = 1.3112e^{-3}$$

$$posterior numerator (male) = 6.1984e^{-09}$$

$$P(female) = 0.5$$

$$p(height | female) = 2.2346e^{-1}$$

$$p(weight | female) = 1.6789e^{-2}$$

$$p(foot size | female) = 2.8669e^{-1}$$

$$posterior numerator (female) = 5.3778e^{-04}$$

由於女性後驗概率的分子比較大，所以我們預計這個樣本是女性。

### 文本分類

這是一個用單純貝氏分類做的一個文本分類問題的例子。考慮一個基於內容的文本分類問題，例如判斷郵件是否為垃圾郵件。想像文本可以分成若干的類別，首先文本可以被一些單詞集標註，而這個單詞集是獨立分布的，在給定的C類文本中第i個單詞出現的機率可以表示為：

$$p(w_i \vert C)\,$$

（通過這種處理，我們進一步簡化了工作，假設每個單詞是在文中是隨機分布的-也就是單詞不依賴於文本的長度，與其他詞出現在文中的位置，或者其他文本內容。）

所以，對於一個給定類別C，文本D包含所有單詞$w_i$的機率是:

$$p(D\vert C)=\prod_i p(w_i \vert C)\,$$

我們要回答的問題是「文檔D屬於類C的機率是多少？」換而言之$p(C \vert D)\,$是多少？

現在定義

$$p(D\vert C)={p(D\cap C)\over p(C)}$$

$$p(C\vert D)={p(D\cap C)\over p(D)}$$

通過貝葉斯定理將上述機率處理成似然度的形式

$$p(C\vert D)={p(C)\over p(D)}\,p(D\vert C)$$

假設現在只有兩個相互獨立的類別，S和¬S（垃圾郵件和非垃圾郵件），這裡每個元素（郵件）要麼是垃圾郵件，要麼就不是。$$p(D\vert S)=\prod_i p(w_i \vert S)\,$$

$$p(D\vert\neg S)=\prod_i p(w_i\vert\neg S)\,$$

用上述貝葉斯的結果，可以寫成

$$p(S\vert D)={p(S)\over p(D)}\,\prod_i p(w_i \vert S)$$

$$p(\neg S\vert D)={p(\neg S)\over p(D)}\,\prod_i p(w_i \vert\neg S)$$

兩者相除:

$${p(S\vert D)\over p(\neg S\vert D)}={p(S)\,\prod_i p(w_i \vert S)\over p(\neg S)\,\prod_i p(w_i \vert\neg S)}$$

整理得:

$${p(S\vert D)\over p(\neg S\vert D)}={p(S)\over p(\neg S)}\,\prod_i {p(w_i \vert S)\over p(w_i \vert\neg S)}$$

這樣機率比p(S | D) / p(¬S | D)可以表達為似然比。實際的機率p(S | D)可以很容易通過log (p(S | D) / p(¬S | D))計算出來，基於p(S | D) + p(¬S | D) = 1。

結合上面所討論的機率比，可以得到：

$$\ln{p(S\vert D)\over p(\neg S\vert D)}=\ln{p(S)\over p(\neg S)}+\sum_i \ln{p(w_i\vert S)\over p(w_i\vert\neg S)}$$

(這種對數似然比的技術在統計中是一種常用的技術。在這種兩個獨立的分類情況下（如這個垃圾郵件的例子），把對數似然比轉化為S曲線的形式)。

最後文本可以分類，當$p(S\vert D) > p(\neg S\vert D)$或者$\ln{p(S\vert D)\over p(\neg S\vert D)} > 0$時判定為垃圾郵件，否則為正常郵件。

## 外部連結

- 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.