樸素貝葉斯演算法思想

A. 樸素貝葉斯（Naive Bayes）演算法

樸素貝葉斯演算法屬於分類演算法。發源於古典數學理論，對缺失數據不太敏感，有穩定的分類效率，模型所需估計的參數很少，演算法比較簡單。

樸素貝葉斯演算法 ， 貝葉斯 是說明這個演算法和貝葉斯定理有聯系，而 樸素 是因為處理實際的需要，做了一個簡化—— 假設每個特徵之間是獨立的 （如果研究的對象互相之間的影響很強，計算概率時考慮的問題非常復雜，做了獨立假設，就可以分解後進行研究），這是這個演算法模型與貝葉斯定理的區別。

將 x 作為特徵，y 作為類別，那公式左邊的 P（yi|x）就是說在知道特徵 x 的情況下，計算這個特徵屬於 yi 類的可能性大小。通過比較找出這個可能性的值最大的屬於哪一類，就將特徵 x 歸為這一類。

第3步的計算就是整個關鍵所在，計算依據是上面的貝葉斯公式。

對於每一個類的概率計算，公式右邊的分母的 P(x)都是相同的，所以可以不計算（我們只是對最終結果進行比較，不影響）。

P（yi）也稱為先驗概率，是 x 屬於 yi 類的一個概率，這個是通過歷史信息得到的（在程序實現的時候，歷史信息或者說先驗信息就是我們的訓練數據集），我們通過對訓練樣本數據進行統計，分別算出 x 屬於 y1,y2,...,yn 類的概率是多少,這個是比較容易得到的。

所以，主要是求 P（x|yi）= P(a1,a2,...,am|yi)

這個時候對於貝葉斯模型的 樸素 的獨立性假設就發揮作用了(綜合的計算變成了獨立計算後的綜合，簡化模型，極大地減少了計算的復雜程度)：

P(a1,a2,...,am|yi) = P(a1|yi)P(a2|yi)...P(am|yi)

所以計算想要得到的東西如下：

一個程序簡例

B. 數據挖掘十大經典演算法之樸素貝葉斯

樸素貝葉斯，它是一種簡單但極為強大的預測建模演算法。之所以稱為樸素貝葉斯，**是因為它假設每個輸入變數是獨立的。**這個假設很硬，現實生活中根本不滿足，但是這項技術對於絕大部分的復雜問題仍然非常有效。

貝葉斯原理、貝葉斯分類和樸素貝葉斯這三者之間是有區別的。

貝葉斯原理是最大的概念，它解決了概率論中「逆向概率」的問題，在這個理論基礎上，人們設計出了貝葉斯分類器，樸素貝葉斯分類是貝葉斯分類器中的一種，也是最簡單，最常用的分類器。樸素貝葉斯之所以樸素是因為它假設屬性是相互獨立的，因此對實際情況有所約束，**如果屬性之間存在關聯，分類准確率會降低。**不過好在對於大部分情況下，樸素貝葉斯的分類效果都不錯。

樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換而言之樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。

樸素貝葉斯分類 常用於文本分類 ，尤其是對於英文等語言來說，分類效果很好。它常用於垃圾文本過濾、情感預測、推薦系統等。

1、 需要知道先驗概率 

先驗概率是計算後驗概率的基礎。在傳統的概率理論中，先驗概率可以由大量的重復實驗所獲得的各類樣本出現的頻率來近似獲得，其基礎是「大數定律」，這一思想稱為「頻率主義」。而在稱為「貝葉斯主義」的數理統計學派中，他們認為時間是單向的，許多事件的發生不具有可重復性，因此先驗概率只能根據對置信度的主觀判定來給出，也可以說由「信仰」來確定。 

2、按照獲得的信息對先驗概率進行修正 

在沒有獲得任何信息的時候，如果要進行分類判別，只能依據各類存在的先驗概率，將樣本劃分到先驗概率大的一類中。而在獲得了更多關於樣本特徵的信息後，可以依照貝葉斯公式對先驗概率進行修正，得到後驗概率，提高分類決策的准確性和置信度。 

3、分類決策存在錯誤率 

由於貝葉斯分類是在樣本取得某特徵值時對它屬於各類的概率進行推測，並無法獲得樣本真實的類別歸屬情況，所以分類決策一定存在錯誤率，即使錯誤率很低，分類錯誤的情況也可能發生。 

第一階段：准備階段

在這個階段我們需要確定特徵屬性，同時明確預測值是什麼。並對每個特徵屬性進行適當劃分，然後由人工對一部分數據進行分類，形成訓練樣本。

第二階段：訓練階段

這個階段就是生成分類器，主要工作是 計算每個類別在訓練樣本中的出現頻率 及 每個特徵屬性劃分對每個類別的條件概率。

第三階段：應用階段

這個階段是使用分類器對新數據進行分類。

優點：

（1）樸素貝葉斯模型發源於古典數學理論，有穩定的分類效率。

（2）對小規模的數據表現很好，能個處理多分類任務，適合增量式訓練，尤其是數據量超出內存時，我們可以一批批的去增量訓練。

（3）對缺失數據不太敏感，演算法也比較簡單，常用於文本分類。

缺點：

（1）理論上，樸素貝葉斯模型與其他分類方法相比具有最小的誤差率。但是實際上並非總是如此，這是因為樸素貝葉斯模型給定輸出類別的情況下,假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，在屬性個數比較多或者屬性之間相關性較大時，分類效果不好。而在屬性相關性較小時，樸素貝葉斯性能最為良好。對於這一點，有半樸素貝葉斯之類的演算法通過考慮部分關聯性適度改進。

（2）需要知道先驗概率，且先驗概率很多時候取決於假設，假設的模型可以有很多種，因此在某些時候會由於假設的先驗模型的原因導致預測效果不佳。

（3）由於我們是通過先驗和數據來決定後驗的概率從而決定分類，所以分類決策存在一定的錯誤率。

（4）對輸入數據的表達形式很敏感。

參考：

https://blog.csdn.net/qiu__liao/article/details/90671932

https://blog.csdn.net/u011067360/article/details/24368085

C. 樸素貝葉斯演算法的原理是什麼

樸素貝葉斯分類（NBC）是以貝葉斯定理為基礎並且假設特徵條件之間相互獨立的方法，以特徵詞之間獨立作為前提假設，學習從輸入到輸出的聯合概率分布，再基於學習到的模型。

樸素貝葉斯法是基於貝葉斯定理與特徵條件獨立假設的分類方法。

最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBM）。和決策樹模型相比，樸素貝葉斯分類器(Naive Bayes Classifier 或 NBC)發源於古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。

同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。

樸素貝葉斯演算法（Naive Bayesian algorithm) 是應用最為廣泛的分類演算法之一。

樸素貝葉斯方法是在貝葉斯演算法的基礎上進行了相應的簡化，即假定給定目標值時屬性之間相互條件獨立。也就是說沒有哪個屬性變數對於決策結果來說佔有著較大的比重，也沒有哪個屬性變數對於決策結果佔有著較小的比重。

雖然這個簡化方式在一定程度上降低了貝葉斯分類演算法的分類效果，但是在實際的應用場景中，極大地簡化了貝葉斯方法的復雜性。

D. 樸素貝葉斯以及三種常見模型推導

樸素貝葉斯演算法Naive Bayes定義中有兩個關鍵定義:特徵之間強假設獨立和貝葉斯定理.這兩個定義就是樸素貝葉斯的關鍵.接下來先了解一下這兩個定義.

貝葉斯定義是概率論中的一個定理,它跟隨機變數的條件概率以及邊緣概率分布有關.

通常，事件A在事件B（發生）的條件下的概率，與事件B在事件A（發生）的條件下的概率是不一樣的，然而,這兩者之間是有確定的關系的，貝葉斯定理就是這種關系的陳述。貝葉斯公式的一個用途在於通過已知的三個概率函數推出第四個.

直接給出公式:

其中,P(A|B)是指事件B發生的情況下事件A發生的概率(條件概率).在貝葉斯定理中,每個名詞都有約定俗成的名稱:

按這些術語,貝葉斯定理可以表述為:

後驗概率 = (似然性 * 先驗概率)/標准化常量

也就是說,後驗概率與先驗概率和相似度的乘積成正比.

同時,分母P(B),可以根據全概率公式分解為:

如果P(X,Y|Z)=P(X|Z)P(Y|Z)，或等價地P(X|Y,Z）=P(X|Z），則稱事件X,Y對於給定事件Z是條件獨立的，也就是說，當Z發生時，X發生與否與Y發生與否是無關的。

應用在自然語言處理中,就是說在文章類別確定的條件下,文章的各個特徵(單詞)在類別確定的條件下是獨立的,並不相關,用通俗的話說,在文章類別確定的條件下,文章各個詞之間出現與否沒有相關性(事實上,並不成立).這是一個非常強的假設,但對問題的求解來說變得更加簡單.

設輸入空間 為n為向量的集合,輸出空間為類標記集合 .輸入為特徵向量 ,輸出為類標記 . X是定義在輸入空間X上的隨機變數,Y是定義在輸出空間Y上的隨機變數.P(X,Y)是X和Y的聯合概率分布.訓練數據集:

由P(X,Y)獨立同分布產生.因此樸素貝葉斯模型也是一個生成模型.

樸素貝葉斯演算法通過訓練集學習聯合概率分布P(X,Y),具體地,學習先驗概率分布以及條件概率分布.其中先驗概率分布

條件概率分布

, k=1,2,...,K

通過兩個概率得到聯合概率分布P(X,Y) = P(X|Y)P(Y).

條件概率分布P(X=x|Y=c_k)有指數級數量的參數,其估計實際上不可行的.假設 有 個取值,j=1,2,...,n,Y有K個取值,那麼參數個數為 .

指數級的參數估計事實上並不可行,因此樸素貝葉斯演算法針對各個特徵之間做了假設,也就是對條件概率分布作了條件獨立性假設,這是一個很強的假設,通過這個假設,我們的參數求解變得可行,這也就是樸素貝葉斯的"樸素"的由來.這種情況下,我們同樣假設 有 個取值,j=1,2,...,n,Y有K個取值,那麼參數個數為 ,需要估計的參數量大大減少.條件獨立性假設是

樸素貝葉斯演算法分類時,對給定輸入x,通過學習到的模型計算後驗概率分布 ,將後驗概率最大的類作為輸入x的類輸出.後驗概率根據貝葉斯定理計算:

上面的公式是後驗概率分布中的一項,由於對於相同輸入x下不同類別的後驗概率的分母都相同,而最終的類輸出是後驗概率分布中概率最大對應的類別,所以我們可以簡化為只比較分子的大小就可以確定最終的結果,也就是說,最終類輸出為:

.

如果我們對右邊的乘積概率取log,連乘積就可以轉換成為和,計算更簡單(加法總比乘法簡單),上訴公式存在一種變種:

.

同時這種形式,也可以看做是一種線性回歸,權重系數為1.

介紹完,樸素貝葉斯的概率模型之後,我們目前的主要問題就集中在如何估計這個模型的 個參數: ,估算出參數,我們就可以對輸入向量x做預測.針對這些參數的求解方法不同,存在不同的樸素貝葉斯類型,具體介紹三種:伯努利樸素貝葉斯,多項式樸素貝葉斯和高斯樸素貝葉斯.不同類型的樸素貝葉斯對參數的求法不同,而根源在於對P條件概率(X=x|Y=c_k)的假設分布不同,也就是說在給定類別的情況下,對X假設的分布不同:伯努利假設是伯努利分布(其實應該是多變數伯努利分布),多項式假設是多項式分布,而高斯也就是假設是高斯分布(其實是多變數高斯分布).然後,我們細化到三種不同類型的樸素貝葉斯理論中.

伯努利樸素貝葉斯,其實應該叫"Multi-variate Naive Bayes",假設P(X=x|Y=c_k)是多變數伯努利分布.在了解多變數伯努利分布之前,先介紹一下什麼是(單變數的)伯努利分布.

伯努利分布,又叫做兩點分布或0-1分布,是一個離散型概率分布.稱隨機變數X有伯努利分布,參數為p(0< p <1),它分別以概率p和1-p取1和0為值.

最簡單的例子就是拋硬幣,硬幣結果為正或反.

冪次運算變成乘法運算,更簡單.當x=1時,概率是P(X=1)=p,當x=0時,概率P(X=0)=1-p,這樣就可以將兩種情況合在一起.

了解了什麼是伯努利分布之後,我們再看什麼是多元伯努利分布(多變數 multi-variate Bernoulli).

多元伯努利分布,通俗的講就是同時進行多個不同的伯努利實驗, ,其中x是一個向量, 也是一個向量,表示不同伯努利實驗的參數.

伯努利多項式將文檔的生成模型P(X=x|Y=c_k)假設服從為多元伯努利分布,由於我們之前做的特徵獨立性假設, 是一個向量形式,而其中 ,也就是說x向量是onehot形式的向量(每個維度值是0或1),表示這個維度的特徵是否出現.特徵集 有n個特徵,特徵集的維度決定了輸入空間X的維度,而且特徵集的維度可以對應到輸入空間的各個維度上.

因為特徵之間的獨立性,所以多元伯努利變成各個伯努利分布的連乘積,需要注意的一點是 因為是伯努利分布,0-1,特徵出現有一個概率p,特徵不出現也有一個概率1-p .最終模型的參數估計完成之後,對新樣本進行預測時,如果某個特徵不出現,需要 乘上這個特徵不出現的概率 ,不能只計算特徵出現的概率!!!兩個向量直接相乘,並不能得到最終的結果.

對應的伯努利樸素貝葉斯模型為:

為了簡化運算,我們可以將分母忽略,雖然對應的結果不是真正的概率,但是相同樣本的各個後驗概率之間的大小關系保持不變,同時如果兩邊同時做log運算,後驗概率之間的大小關系同樣保持不變.因此,

.

了解了多元伯努利分布之後,接下來的工作就是對參數進行估計,計算 , .

參數估計的過程也是樸素貝葉斯分類器學習的過程.而參數估計可以使用極大似然估計.先驗概率 的極大似然估計是

, k=1,2,...,K

其中,I(x)是一個指示函數,如果x為真,I(x)結果為1,如果x為假,I(x)=0.用語言描述來說, 這個概率等於在N個樣本的數據集中,類別為 的樣本所佔的比例.

條件概率 的極大似然估計是:

用語言描述來說,條件概率 等於在類別為 的樣本集合(數據集的子集)中,第i個特徵等於 的概率, 是0或1,而且 服從伯努利分布,所以只需要計算一個,比如P , ,因為兩個概率和為1(這是 同一個變數 ).

這些參數估計完之後,樸素貝葉斯就完成了學習過程,接下來就可以使用它去進行預測了(應用才是最終的目的).

由於 是伯努利分布,參數p在[0,1]之間,有可能存在 ,也就是存在0概率.

舉例來說,在當前類別下的所有樣本中特徵i都出現了(=1),根據上面的條件概率極大似然估計,可以知道 ,那麼對應的, ,那麼當新樣本來的時候,加入存在一條記錄x,它很巧地沒有第i個特徵(這不巧了嗎?不是),由於0概率的存在,那麼使用上面的貝葉斯公式,就會出現屬於某個列別的概率為0, .但這種情況是應該避免的,那麼如何避免呢?

我們在對條件概率進行極大似然估計時,針對分子和分母做一些小變動,

其中, 表示第i個特徵不同取值的個數,由於這里是one-hot,取值為2,所以 , 乘以 是保證 個不同取值對應的條件概率之和為1,不偏袒任意一種情況,一視同仁.

To Be Continued.

多項式樸素貝葉斯,假設P(X=x|Y=c_k)是多項式分布.在了解多項式樸素貝葉斯之前,先介紹一下什麼是多項式分布?

將伯努利分布的單變數擴展到d維向量 ,其中 ,且 ,假設 的概率是 ,並且 ,則將得到離散分布:

.

其中x, 都是d維向量形式.在此的基礎上擴展二項分布到多項式分布(Multinomial distribution),該分布描述的是在n次獨立實驗中有 詞 的概率,其密度函數可以表達為如下形式:

多項式分布的期望,方差如下:

多項式分布應用到樸素貝葉斯上,對於文檔分類問題來說,假設給定文檔類型的基礎上文檔生成模型 是一個多項式分布.這樣對應關系就是:

需要注意的是,應用在文本分類的多項式樸素貝葉斯模型之前,一般多項式條件概率如下:

我們的多項式樸素貝葉斯概率模型為:

這里為了方便,首先我們假設文章長度和文章的類別之間沒有相關性(事實上也並不成立,比如說相對較長的郵件,相比垃圾郵件而言,正常郵件的概率更大),也就是說P(|x|)的分布與文章所屬類別無關.另一方面,由於最終所屬類別是後驗概率最大對應的類別,所以,我們可以將文章長度P(|x|)建模的概率,忽略掉,就像我們之前忽略伯努利分布中的分母一樣.

再者,為了更加方便,我們通常對兩邊取log運算,將冪次運算轉換成線性運算:

我們也可以將文章長度階乘省略,然後變成:

.

這樣就變成線性運算,就和線性回歸一樣,運算高效而簡單.

將文檔模型對應到多項式分布上得到多項式樸素貝葉斯,在我們對其做出假設分布之後,剩下的工作就是對假設分布下每個類別下的d個條件概率以及先驗分布進行估計.此外,還需要說明的一點是:多項式樸素貝葉斯模型採用詞袋模型,每個 表示第i個特徵出現的次數,也就是詞頻term-frequency,有時候也可以使用tf-idf作為值.

參數估計的過程也是樸素貝葉斯分類器學習的過程.而參數估計可以使用極大似然估計.先驗概率 的極大似然估計是

, k=1,2,...,K

其中,I(x)是一個指示函數,如果x為真,I(x)結果為1,如果x為假,I(x)=0.用語言描述來說, 這個概率等於在N個樣本的數據集中,類別為 的樣本所佔的比例.

條件概率 的極大似然估計是:

用語言描述來說,條件概率 等於在類別為 的樣本集合(數據集的子集)中,第t個特徵出現的概率等於 類樣本第t個特徵出現的總次數(考慮詞頻,不再是0,1)占 類樣本的總詞數(文章長度之和,文章單詞特徵是固定的,考慮了詞頻)的比例.

為了方便理解,將 表示為第k類樣本集合中第t個特徵出現的總次數, 表示為在所有樣本中第k類樣本的總詞數(第k類樣本長度之和,考慮頻數),簡寫成:

和伯努利樸素貝葉斯模型類似,有可能存在某一維度,數據集在這一維度上都是0,對應到文檔分類上,就是這個詞在所有文章中都沒有出現過(詞典選的不好,特徵選擇不好),這種情況就會出現0概率.所以我們需要對條件概率做一點小改動:

其中,d表示數據維度為d(有d個特徵,每個特徵都加 ,保證概率和為1, 需要乘d).當 時,叫做Laplace Smoonthing拉普拉斯平滑,當然 也可以小於1.

To Be Continued

高斯樸素貝葉斯,假設P(X=x|Y=c_k)是多元高斯分布.在了解高斯樸素貝葉斯之前,先介紹一下什麼是高斯分布,什麼是多元高斯分布?

高斯分布又稱正態分布，在實際應用中最為廣泛。對於單變數 ,高斯分布的參數有兩個，分別是均值 和方差 ，其概率密度函數為

其中, 是D維均值向量, 是DxD的協方差矩陣, 是 的行列式.多元高斯分布的期望是 ,方差是

特殊的, 如果D個維度之間相互獨立,那麼多元高斯分布就可以表示成單元高斯分布概率密度函數的連乘積 .

高斯樸素貝葉斯模型是假設條件概率P(X=x|Y=c_k)是多元高斯分布,另一方面,由之前的特徵的條件獨立性假設,我們就可以通過對每個特徵的條件概率建模, 每個特徵的條件概率 也服從高斯分布 .

在 類下第i個詞對應的高斯分布為:

其中, , 表示c類下第i個特徵的均值和方差.

由於特徵之間的獨立性假設,我們可以得到條件概率:

一共有d個特徵.

高斯樸素貝葉斯變成:

.

了解了多元高斯分布分布之後,接下來的工作就是對參數進行估計,計算 和 .

先驗概率和之前的估算方法相同,不再描述.主要是對高斯分布的均值和方差的估計,採用的方法仍然是極大似然估計.

均值的估計 是在樣本類別 中,所有 的平均值;

方差的估計 為樣本類別 中所有 的方差.

對於一個連續的樣本值,帶入高斯分布,就可以求出它的概率分布了.

所有參數估計完成之後,就可以計算給定樣本的條件概率 ,進而可以計算 ,之後就可以確定樣本類別,完成模型預測.

E. 樸素貝葉斯

        在所有的機器學習分類演算法中，樸素貝葉斯和其他絕大多數的分類演算法都不同。對於大多數的分類演算法，比如決策樹,KNN,邏輯回歸，支持向量機等，他們都是判別方法，但是樸素貝葉斯卻是生成方法。

如何理解這句話，看例題：

        根據上述數據集，如果一對男女朋友，男生想女生求婚，男生的四個特點分別是不帥，性格不好，身高矮，不上進，請你判斷一下女生是嫁還是不嫁？

這里我們聯繫到樸素貝葉斯公式：

p(不帥、性格不好、身高矮、不上進|嫁) = p(不帥|嫁)*p(性格不好|嫁)*p(身高矮|嫁)*p(不上進|嫁)---------->要使這個公式成立，需要各個特徵之間相互獨立。

而樸素貝葉斯演算法就是假設各個特徵之間相互獨立。

1、假如沒有這個假設，那麼我們對右邊這些概率的估計其實是不可做的，這么說，我們這個例子有4個特徵，其中帥包括{帥，不帥}，性格包括{不好，好，爆好}，身高包括{高，矮，中}，上進包括{不上進，上進}，那麼四個特徵的聯合概率分布總共是4維空間，總個數為2*3*3*2=36個。36個，計算機掃描統計還可以，但是現實生活中，往往有非常多的特徵，每一個特徵的取值也是非常之多，那麼通過統計來估計後面概率的值，變得幾乎不可做，這也是為什麼需要假設特徵之間獨立的原因。

2、假如我們沒有假設特徵之間相互獨立，那麼我們統計的時候，就需要在整個特徵空間中去找，比如統計p(不帥、性格不好、身高矮、不上進|嫁)。我們就需要在嫁的條件下，去找四種特徵全滿足分別是不帥，性格不好，身高矮，不上進的人的個數，這樣的話，由於數據的稀疏性，很容易統計到0的情況。 這樣是不合適的。

        根據上面倆個原因，樸素貝葉斯法對條件概率分布做了條件獨立性的假設，由於這是一個較強的假設，樸素貝葉斯也由此得名！這一假設使得樸素貝葉斯法變得簡單，但有時會犧牲一定的分類准確率。

所以公式整理以後變為：

整理訓練數據中，嫁的樣本數如下：

分別計算各個概率：

p(嫁) = 6/12（總樣本數） = 1/2

p(不帥|嫁) = 3/6 = 1/2

p(性格不好|嫁)= 1/6

p(矮|嫁) = 1/6

p(不上進|嫁) = 1/6

總樣本為：

p（不帥） = 4/12 = 1/3

p（性格不好） = 4/12 = 1/3

p（身高矮） = 7/12

p（不上進） = 4/12 = 1/3

將以上概率帶入公式，就能得出嫁的概率。

總結：理論上，樸素貝葉斯模型與其他分類方法相比具有最小的誤差率。但是實際上並非總是如此，這是因為樸素貝葉斯模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，在屬性個數比較多或者屬性之間相關性較大時，分類效果不好。

而在屬性相關性較小時，樸素貝葉斯性能最 為良好。

F. 數據挖掘十大經典演算法（1）——樸素貝葉斯(Naive Bayes)

在此推出一個演算法系列的科普文章。我們大家在平時埋頭工程類工作之餘，也可以抽身對一些常見演算法進行了解，這不僅可以幫助我們拓寬思路，從另一個維度加深對計算機技術領域的理解，做到觸類旁通，同時也可以讓我們搞清楚一些既熟悉又陌生的領域——比如數據挖掘、大數據、機器學習——的基本原理，揭開它們的神秘面紗，了解到其實很多看似高深的領域，其實背後依據的基礎和原理也並不復雜。而且，掌握各類演算法的特點、優劣和適用場景，是真正從事數據挖掘工作的重中之重。只有熟悉演算法，才可能對紛繁復雜的現實問題合理建模，達到最佳預期效果。

本系列文章的目的是力求用最干練而生動的講述方式，為大家講解由國際權威的學術組織the IEEE International Conference on Data Mining (ICDM) 於2006年12月評選出的數據挖掘領域的十大經典演算法。它們包括：

本文作為本系列的第一篇，在介紹具體演算法之前，先簡單為大家鋪墊幾個數據挖掘領域的常見概念：

在數據挖掘領域，按照演算法本身的行為模式和使用目的，主要可以分為分類(classification)，聚類(clustering)和回歸(regression)幾種，其中：

打幾個不恰當的比方 ：

另外，還有一個經常有人問起的問題，就是 數據挖掘 和 機器學習 這兩個概念的區別，這里一句話闡明我自己的認識：機器學習是基礎，數據挖掘是應用。機器學習研製出各種各樣的演算法，數據挖掘根據應用場景把這些演算法合理運用起來，目的是達到最好的挖掘效果。

當然，以上的簡單總結一定不夠准確和嚴謹，更多的是為了方便大家理解打的比方。如果大家有更精當的理解，歡迎補充和交流。

好了，鋪墊了這么多，現在終於進入正題！
作為本系列入門的第一篇，先為大家介紹一個容易理解又很有趣的演算法—— 樸素貝葉斯 。

先站好隊，樸素貝葉斯是一個典型的 有監督的分類演算法 。

光從名字也可以想到，要想了解樸素貝葉斯，先要從 貝葉斯定理 說起。
貝葉斯定理是我們高中時代學過的一條概率學基礎定理，它描述了條件概率的計算方式。不要怕已經把這些知識還給了體育老師，相信你一看公式就能想起來。

P(A|B)表示事件B已經發生的前提下，事件A發生的概率，叫做事件B發生下事件A的條件概率。其基本求解公式為：

其中，P(AB)表示A和B同時發生的概率，P(B)標識B事件本身的概率。

貝葉斯定理之所以有用，是因為我們在生活中經常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們更關心P(B|A)。

而貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。
下面不加證明地直接給出貝葉斯定理：

有了貝葉斯定理這個基礎，下面來看看樸素貝葉斯演算法的基本思路。

你看，其思想就是這么的樸素。那麼，屬於每個分類的概率該怎麼計算呢？下面我們先祭出形式化語言！

那麼現在的關鍵就是如何計算第3步中的各個條件概率。我們可以這么做：

因為分母對於所有類別為常數，因為我們只要將分子最大化皆可。又因為各特徵屬性是條件獨立的，所以有：

如果你也跟我一樣，對形式化語言有嚴重生理反應，不要怕，直接跳過前面這一坨，我們通過一個鮮活的例子，用人類的語言再解釋一遍這個過程。

某個醫院早上收了六個門診病人，如下表。

現在又來了第七個病人，是一個打噴嚏的建築工人。請問他最有可能患有何種疾病？

本質上，這就是一個典型的分類問題， 症狀 和 職業 是特徵屬性， 疾病種類 是目標類別

根據 貝葉斯定理

可得

假定"打噴嚏"和"建築工人"這兩個特徵是獨立的，因此，上面的等式就變成了

這是可以計算的。

因此，這個打噴嚏的建築工人，有66%的概率是得了感冒。同理，可以計算這個病人患上過敏或腦震盪的概率。比較這幾個概率，就可以知道他最可能得什麼病。

接下來，我們再舉一個樸素貝葉斯演算法在實際中經常被使用的場景的例子—— 文本分類器 ，通常會用來識別垃圾郵件。
首先，我們可以把一封郵件的內容抽象為由若干關鍵片語成的集合，這樣是否包含每種關鍵詞就成了一封郵件的特徵值，而目標類別就是 屬於垃圾郵件 或 不屬於垃圾郵件

假設每個關鍵詞在一封郵件里出現與否的概率相互之間是獨立的，那麼只要我們有若干已經標記為垃圾郵件和非垃圾郵件的樣本作為訓練集，那麼就可以得出，在全部垃圾郵件（記為Trash）出現某個關鍵詞Wi的概率，即 P(Wi|Trash)

而我們最重要回答的問題是，給定一封郵件內容M，它屬於垃圾郵件的概率是多大，即 P(Trash|M)

根據貝葉斯定理，有

我們先來看分子：
P(M|Trash) 可以理解為在垃圾郵件這個范疇中遇見郵件M的概率，而一封郵件M是由若干單詞Wi獨立匯聚組成的，只要我們所掌握的單詞樣本足夠多，因此就可以得到

這些值我們之前已經可以得到了。

再來看分子里的另一部分 P(Trash) ，這個值也就是垃圾郵件的總體概率，這個值顯然很容易得到，用訓練集中垃圾郵件數除以總數即可。

而對於分母來說，我們雖然也可以去計算它，但實際上已經沒有必要了，因為我們要比較的 P(Trash|M) 和 P(non-Trash|M) 的分母都是一樣的，因此只需要比較分子大小即可。

這樣一來，我們就可以通過簡單的計算，比較郵件M屬於垃圾還是非垃圾二者誰的概率更大了。

樸素貝葉斯的英文叫做 Naive Bayes ，直譯過來其實是 天真的貝葉斯 ，那麼他到底天真在哪了呢？

這主要是因為樸素貝葉斯的基本假設是所有特徵值之間都是相互獨立的，這才使得概率直接相乘這種簡單計算方式得以實現。然而在現實生活中，各個特徵值之間往往存在一些關聯，比如上面的例子，一篇文章中不同單詞之間一定是有關聯的，比如有些詞總是容易同時出現。

因此，在經典樸素貝葉斯的基礎上，還有更為靈活的建模方式—— 貝葉斯網路（Bayesian Belief Networks, BBN） ，可以單獨指定特徵值之間的是否獨立。這里就不展開了，有興趣的同學們可以做進一步了解。

最後我們來對這個經典演算法做個點評：

優點：

缺點：

好了，對於 樸素貝葉斯 的介紹就到這里，不知道各位看完之後是否會對數據挖掘這個領域產生了一點興趣了呢？

G. 樸素貝葉斯的推理學習演算法

樸素貝葉斯的推理學習演算法
貝葉斯公式簡易推導式：
樸素貝葉斯的樸素在於假設B特徵的每個值相互獨立，所以樸素貝葉斯的公式是這樣的
學習與分類演算法：
(1)計算先驗概率和條件概率
拉普拉斯平滑：
（2）代入被測樣本向量，得到不同類別P，再根據後驗概率最大化，取P最大的類別作為該標簽類別。
樸素貝葉斯優點在於對於小規模數據很好，適合多分類。缺點是數據輸入形式敏感而且特徵值之間的相互獨立很難保證帶來的影響。

H. 第10天：NLP補充——樸素貝葉斯(Naive-Bayes)

1、引言
  貝葉斯方法是一個歷史悠久，樸素貝葉斯中的樸素一詞的來源就是假設各特徵之間相互獨立。這一假設使得樸素貝葉斯演算法變得簡單，但有時會犧牲一定的分類准確率。當然有著堅實的理論基礎的方法，同時處理很多問題時直接而又高效，很多高級自然語言處理模型也可以從它演化而來。因此，學習貝葉斯方法，是研究自然語言處理問題的一個非常好的切入口。
2、貝葉斯公式
貝葉斯公式其實很簡單，但是很常用，就一行：

  而我們二分類問題的最終目的就是要判斷 P(「屬於某類」|「具有某特徵」) 是否大於1/2就夠了。貝葉斯方法把計算「具有某特徵的條件下屬於某類」的概率轉換成需要計算「屬於某類的條件下具有某特徵」的概率，而後者獲取方法就簡單多了，我們只需要找到一些包含已知特徵標簽的樣本，即可進行訓練。而樣本的類別標簽都是明確的，所以貝葉斯方法在機器學習里屬於有監督學習方法。
  這里再補充一下，一般『先驗概率』、『後驗概率』是相對出現的，比如 P(Y)與 P(Y|X) 是關於 Y的先驗概率與後驗概率， P(X)與 P(X|Y)是關於 X的先驗概率與後驗概率。
4、垃圾郵件識別
  我們可以通過一個例子來對郵件進行分類，識別垃圾郵件和普通郵件，如果我們選擇使用樸素貝葉斯分類器，那目標就是判斷 P(「垃圾郵件」|「具有某特徵」) 是否大於1/2。現在假設我們有垃圾郵件和正常郵件各1萬封作為訓練集。需要判斷以下這個郵件是否屬於垃圾郵件：

也就是判斷概率 P(「垃圾郵件」|「我司可辦理正規發票（保真）17%增值稅發票點數優惠！」)是否大於1/2。我們不難發現：通過上述的理解，也就是將其轉換成的這個概率，計算的方法：就是寫個計數器，然後+1 +1 +1統計出所有垃圾郵件和正常郵件中出現這句話的次數啊。也就是：

  於是當我們接觸到了中文NLP中，其中最為重要的技術之一：分詞！！！也就是把一整句話拆分成更細粒度的詞語來進行表示。另外，分詞之後去除標點符號、數字甚至無關成分(停用詞)是特徵預處理中的一項技術。我們觀察（「我」,「司」,「可」,「辦理」,「正規發票」,「保真」,「增值稅」,「發票」,「點數」,「優惠」)，這可以理解成一個向量：向量的每一維度都表示著該特徵詞在文本中的特定位置存在。這種將特徵拆分成更小的單元，依據這些更靈活、更細粒度的特徵進行判斷的思維方式，在自然語言處理與機器學習中都是非常常見又有效的。因此貝葉斯公式就變成了：

1、樸素貝葉斯(Naive Bayes)，「Naive」在何處？
  加上條件獨立假設的貝葉斯方法就是樸素貝葉斯方法（Naive Bayes）。將句子（「我」,「司」,「可」,「辦理」,「正規發票」) 中的 （「我」,「司」）與（「正規發票」）調換一下順序，就變成了一個新的句子（「正規發票」,「可」,「辦理」, 「我」, 「司」)。新句子與舊句子的意思完全不同。但由於乘法交換律，樸素貝葉斯方法中算出來二者的條件概率完全一樣！計算過程如下：

其中「發票」重復了三次。
3、處理重復詞語的三種方式
(1)、多項式模型：
  如果我們考慮重復詞語的情況，也就是說，重復的詞語我們視為其出現多次，直接按條件獨立假設的方式推導，則有：

統計計算 P(「詞語」|S）時也是如此。

我們掃描一下訓練集，發現「正規發票」這個詞從出現過！！！ ，於是 P(「正規發票」|S）=0 …問題嚴重了，整個概率都變成0了！！！樸素貝葉斯方法面對一堆0，很凄慘地失效了…更殘酷的是這種情況其實很常見，因為哪怕訓練集再大，也可能有覆蓋不到的詞語。本質上還是樣本數量太少，不滿足大數定律，計算出來的概率失真 *。為了解決這樣的問題，一種分析思路就是直接不考慮這樣的詞語，但這種方法就相當於默認給P(「正規發票」|S）賦值為1。其實效果不太好，大量的統計信息給浪費掉了。我們進一步分析，既然可以默認賦值為1，為什麼不能默認賦值為一個很小的數？這就是平滑技術的基本思路，依舊保持著一貫的作風，朴實/土但是直接而有效。對於伯努利模型，P(「正規發票」|S）的一種平滑演算法是：

接下來的核心問題就是訓練出一個靠譜的分類器。首先需要有打好標簽的文本。這個好找，豆瓣影評上就有大量網友對之前電影的評價，並且對電影進行1星到5星的評價。我們可以認為3星以上的評論都是好評，3星以下的評論都是差評。這樣就分別得到了好評差評兩類的語料樣本。剩下就可以用樸素貝葉斯方法進行訓練了。基本思路如下：

但是由於自然語言的特點，在提取特徵的過程當中，有一些tricks需要注意：

當然經過以上的處理，情感分析還是會有一部分誤判。這里涉及到許多問題，都是情感分析的難點：

(2)、拼寫糾錯
  拼寫糾錯本質上也是一個分類問題。但按照錯誤類型不同，又分為兩種情況：

真詞錯誤復雜一些，我們將在接下來的文章中進行探討。而對於非詞錯誤，就可以直接採用貝葉斯方法，其基本思路如下：

訓練樣本1：該場景下的正常用詞語料庫，用於計算 P(候選詞i)。

訓練樣本2：該場景下錯誤詞與正確詞對應關系的語料庫，用於計算 P(錯誤詞|候選詞i)

當然，樸素貝葉斯也是有缺陷的。比如我們知道樸素貝葉斯的局限性來源於其條件獨立假設，它將文本看成是詞袋子模型，不考慮詞語之間的順序信息，例如：樸素貝葉斯會把「武松打死了老虎」與「老虎打死了武松」認作是一個意思。那麼有沒有一種方法提高其對詞語順序的識別能力呢？當然有，就是這里要提到的N-gram語言模型。接下來詳細給大家介紹N-gram語言模型。

1、從假設性獨立到聯合概率鏈規則
 與我們之前我們垃圾郵件識別中的條件獨立假設是一樣的：

4、N-gram實際應用舉例
(1)、詞性標注
  詞性標注是一個典型的多分類問題。常見的詞性包括名詞、動詞、形容詞、副詞等。而一個詞可能屬於多種詞性。如「愛」，可能是動詞，可能是形容詞，也可能是名詞。但是一般來說，「愛」作為動詞還是比較常見的。所以統一給「愛」分配為動詞准確率也還足夠高。這種最簡單粗暴的思想非常好實現，如果准確率要求不高則也比較常用。它只需要基於詞性標注語料庫做一個統計就夠了，連貝葉斯方法、最大似然法都不要用。詞性標注語料庫一般是由專業人員搜集好了的，長下面這個樣子。其中斜線後面的字母表示一種詞性，詞性越多說明語料庫分得越細；需要比較以下各概率的大小，選擇概率最大的詞性即可：

將公式進行以下改造，比較各概率的大小，選擇概率最大的詞性：

N-gram分類器是結合貝葉斯方法和語言模型的分類器。這里用 Y1,Y2分別表示這垃圾郵件和正常郵件，用 X表示被判斷的郵件的句子。根據貝葉斯公式有：

比較這些概率的大小，找出使得 P(Yi|X)最大的 Yi即可得到 X 所屬的分類(分詞方案)了。Yi作為分詞方案，其實就是個詞串，比如（「我司」，「可」，「辦理」，「正規發票」）（「我」，「司可辦」，「理正規」，「發票」），也就是一個向量了。而上面貝葉斯公式中 P(X|Yi)項的意思就是在分類方案 Yi的前提下，其對應句子為 X的概率。而無論分詞方案是（「我司」，「可」，「辦理」，「正規發票」）還是（「我」，「司可辦」，「理正規」，「發票」），或者其他什麼方案，其對應的句子都是「我司可辦理正規發票」。也就是說任意假想的一種分詞方式之下生成的句子總是唯一的（只需把分詞之間的分界符號扔掉剩下的內容都一樣）。於是可以將 P(X|Yi)看作是恆等於1的。這樣貝葉斯公式又進一步化簡成為：

也就是說我們

I. 樸素貝葉斯演算法

貝葉斯演算法是由英國數學家托馬斯·貝葉斯提出的，這個演算法的提出是為了解決「逆向概率」的問題。首先我們先來解釋下正向概率與逆向概率的含義：

正向概率 ：假設一個箱子里有5個黃色球和5個白色球，隨機從箱子里拿出一個球，請問取出的是黃球的概率是多少？很容易計算P（黃球）= N（黃球）/N（黃球）+ N（白球） = 5/5+5 = 1/2。
逆向概率 ：起初我們並不知道箱子里有多少個球，我們依次從箱子里取出10個球，發現這個10個球中有7個白球，3個黃球，那麼我們會根據我們觀察到的結果去推測箱子里白球與黃球的分布比例大概是7:3，但是我們無法推測出箱子里的球的個數。

貝葉斯演算法是一種基於概率統計的機器學習演算法，它會計算出每種情況發生的概率，然後對其進行分類，貝葉斯演算法經常用於文本分類問題和垃圾郵件過濾問題。假設有一篇新聞報道news report，我們使用貝葉斯演算法來判斷它們的類別，結果如下：
p(politics|news) = 0.2
p(entertainment|news) = 0.4
p(sports|news) = 0.7
因為p(sports|news)的概率最大，所以我們判斷這篇新聞報道為體育類報道。「|」左邊為要判斷的類別，右邊是我們給定的文章。

貝葉斯公式推導
接下來，我們將通過一個例子來推導貝葉斯公式。在一所學校里，男生和女生的比例分別是60%和40%，男生全部穿長褲，女生一半穿長褲，一半穿裙子。現迎面走來一個同學，你只能看清他（她）穿的是長褲，而無法分辨出他（她）的性別，請問他（她）是女生的概率？

下面我們逐步計算這個問題：
假設學校里的學生總數為N。
男生人數：N * P(boys)，女生人數：N * P(girls)。
穿長褲的男生人數：N * P(boys) * P(pants|boys)，其中P(pants|boys)是條件概率的表達形式，意思是男生中穿長褲的概率。因為男生都穿長褲，所以N * P(boys) * P(pants|boys) = 60% * N。
穿長褲的女生的人數：N * P(girs) * P(pants|girls) = 0.2 * N。
穿長褲的總人數：N * P(boys) * P(pants|boys) + N * P(girs) * P(pants|girls)
穿長褲的同學是女生的概率：P(girl|pants) = N * P(girs) * P(pants|girls) / N * P(boys) * P(pants|boys) + N * P(girs) * P(pants|girls) = P(girs)*P(pants|girls) / P(pants)，分母用P(pants)表示穿長褲的概率。
最終結果：P(girl | pants) = P(pants | girl) * P(girl) / P(pants)
其中：P(girl)我們稱為先驗概率，是已知值，在這個例子中P(girl) = 40%。先驗概率：根據以往的經驗和分析得到的結果，先驗概率和其他條件的影響不受樣本影響。
P(girl | pants)我們稱為後驗概率，根據觀察到的結果，去反推是女生的概率。
貝葉斯數學表達式

貝葉斯演算法在垃圾郵件過濾中的應用
給定一封郵件，判定它是否屬於垃圾郵件？用D 來表示這封郵件，注意D 由N 個單片語成。我們用h+ 來表示垃圾郵件，h-表示正常郵件。
有貝葉斯公式可得：
P(h+ | D) = P(D | h+) * P(h+) / P(D)
P(h- | D) = P(D | h-) * P(h-) / P(D)
其中P(h+)，P(h-)為先驗概率，假如我們有1000封郵件，其中有50封是垃圾郵件，其他都是正常郵件，那麼P(h+)，P(h-)的概率就是已知的。兩個式子的分母都是P(D)，所以P(D)對於最終結果的比較是沒有影響的。接下來就是要求P(D | h+),P(D | h-)垃圾郵件中或正常郵件中是郵件D的概率。
我們都知道一封郵件是由許多詞構成的，所以我們將P(D | h+)的表達式轉化為P(d1,d2,d3......dn | h+)，就是看垃圾郵件中出現d1,d2...dn這些詞的概率是多少。
P(d1,d2,d3......dn | h+) = P(d1 | h+) * P(d2 |d1,h+) * P(d3 |d1,d2,h+) ...
這個式子計算起來非常困難，所以在這里我們做一個假設，假設每個詞都是獨立的並且互不影響，那麼這個式子就可以表示為：
P(d1,d2,d3......dn | h+) = P(d1 | h+) * P(d2 | h+) * P(d3 | h+) ...P(dn | h+)
P(h+ | D) = {P(d1 | h+) * P(d2 | h+) * P(d3 | h+) ...P(dn | h+)}* P(h+) / P(D)
上述這個式子我們就稱為樸素貝葉斯公式，樸素貝葉斯公式是對貝葉斯公式的簡化，它建立在每個條子互相獨立的基礎上。
在現實生活中，我們寫的每一句話中詞與詞之間肯定是有相互聯系，如果沒有聯系，那麼這句話是讀不通的。那麼為什麼樸素貝葉斯能夠在計算中使用，首先是計算簡單，其次對最終結果的影響非常小。
參考資料
1.唐宇迪，《機器學習與數據分析實戰》課程。
2.Peter，《機器學習實戰》。