歡迎光臨
每天分享高質量文章

一文讀懂貝葉斯分類演算法(附學習資源)


貝葉斯分類是一類分類演算法的總稱,這類演算法均以貝葉斯定理為基礎,故統稱為貝葉斯分類。本文首先介紹分類問題,給出分類問題的定義。隨後介紹貝葉斯分類演算法的基礎——貝葉斯定理。最後介紹貝葉斯分類中最簡單的一種——朴素貝葉斯分類,並結合應用案例進一步闡釋。

01 貝葉斯分類

1. 分類問題綜述

對於分類問題,我們每一個人都並不陌生,因為在日常生活中我們都在或多或少地運用它。例如,當你看到一個陌生人,你的腦子下意識判斷TA是男是女;你可能經常會走在路上對身旁的朋友說“這個人一看就很有錢、那邊有個非主流”之類的話,其實這就是一種分類操作。

從數學角度來說,分類問題可做如下定義:

已知集合:,確定映射規則,使得0任意有且僅有一個使得成立。其中C叫做類別集合,其中每一個元素是一個類別,而I叫做項集合,其中每一個元素是一個待分類項,f叫做分類器。分類演算法的任務就是構造分類器f。

這裡要強調的是,分類問題往往採用經驗性方法構造映射規則,即一般情況下的分類問題缺少足夠的信息來構造100%正確的映射規則,而是通過對經驗資料的學習從而實現一定概率意義上正確的分類,因此所訓練出的分類器並不是一定能將每個待分類項準確映射到其分類,分類器的質量與分類器構造方法、待分類資料的特性以及訓練樣本數量等諸多因素有關。

例如,醫生對病人進行診斷就是一個典型的分類過程,任何一個醫生都無法直接看到病人的病情,只能觀察病人表現出的癥狀和各種化驗檢測資料來推斷病情,這時醫生就好比一個分類器,而這個醫生診斷的準確率,與他當初受到的教育方式(構造方法)、病人的癥狀是否突出(待分類資料的特性)以及醫生的經驗多少(訓練樣本數量)都有密切關係。

2. 貝葉斯分類的基礎——貝葉斯定理

這個定理解決了現實生活里經常遇到的問題:已知某條件概率,如何得到兩個事件交換後的概率,也就是在已知P(A|B)的情況下如何求得P(B|A)。這裡先解釋什麼是條件概率:

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

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

下麵不加證明地直接給出貝葉斯定理:

 

3. 朴素貝葉斯分類


朴素貝葉斯分類的原理與流程:

朴素貝葉斯(分類器)是一種生成模型,它會基於訓練樣本對每個可能的類別建模。之所以叫朴素貝葉斯,是因為採用了屬性條件獨立性假設,就是假設每個屬性獨立地對分類結果產生影響。即有下麵的公式: 

後面連乘的地方要註意的是,如果有一項概率值為0會影響後面估計,所以我們對未出現的屬性概率設置一個很小的值,並不為0,這就是拉普拉斯修正(Laplacian correction)。 

拉普拉斯修正實際上假設了屬性值和類別的均勻分佈,在學習過程中額外引入了先驗識。

整個朴素貝葉斯分類分為三個階段:

Stage1:準備工作階段,這個階段的任務是為朴素貝葉斯分類做必要的準備,主要工作是根據具體情況確定特征屬性,並對每個特征屬性進行適當劃分,然後由人工對一部分待分類項進行分類,形成訓練樣本集合。這一階段的輸入是所有待分類資料,輸出是特征屬性和訓練樣本。這一階段是整個朴素貝葉斯分類中唯一需要人工完成的階段,其質量對整個過程將有重要影響,分類器的質量很大程度上由特征屬性、特征屬性劃分及訓練樣本質量決定。

Stage2:分類器訓練階段,這個階段的任務就是生成分類器,主要工作是計算每個類別在訓練樣本中的出現頻率及每個特征屬性劃分對每個類別的條件概率估計,並將結果記錄。其輸入是特征屬性和訓練樣本,輸出是分類器。這一階段是機械性階段,根據前面討論的公式可以由程式自動計算完成。

Stage3:應用階段,這個階段的任務是使用分類器對待分類項進行分類,其輸入是分類器和待分類項,輸出是待分類項與類別的映射關係。這一階段也是機械性階段,由程式完成。

4. 半朴素貝葉斯分類

在朴素的分類中,我們假定了各個屬性之間的獨立,這是為了計算方便,防止過多的屬性之間的依賴導致的大量計算。這正是朴素的含義,雖然朴素貝葉斯的分類效果不錯,但是屬性之間畢竟是有關聯的,某個屬性依賴於另外的屬性,於是就有了半朴素貝葉斯分類器。

為了計算量不至於太大,假定每個屬性只依賴另外的一個。這樣,更能準確描述真實情況。

公式就變成:

屬性為所依賴的屬性,成為的父屬性。


確定父屬性有如下方法:

  • SOPDE方法。這種方法是假定所有的屬性都依賴於共同的一個父屬性。

  • TAN方法。每個屬性依賴的另外的屬性由最大帶權生成樹來確定。

  • 先求每個屬性之間的互信息來作為他們之間的權值。

  • 構件完全圖。權重是剛纔求得的互信息。然後用最大帶權生成樹演算法求得此圖的最大帶權的生成樹。

  • 找一個根變數,然後依次將圖變為有向圖。

  • 添加類別y到每個屬性的的有向邊。

三種方法的屬性依賴關係

02 貝葉斯演算法應用舉例

以下我們再舉一些實際例子來說明貝葉斯方法被運用的普遍性,這裡主要集中在機器學習方面。

1 中文分詞

Google 研究員吳軍在《數學之美》系列中就有一篇是介紹中文分詞的,這裡只介紹一下核心的思想。

分詞問題的描述為:給定一個句子(字串),如:南京市長江大橋。如何對這個句子進行分詞(詞串)才是最靠譜的。例如:

  • 南京市/長江大橋

  • 南京/市長/江大橋

這兩個分詞,到底哪個更靠譜呢?

我們用貝葉斯公式來形式化地描述這個問題,令 X 為字串(句子),Y 為詞串(一種特定的分詞假設)。我們就是需要尋找使得 P(Y|X) 最大的 Y ,使用一次貝葉斯可得:

用自然語言來說就是這種分詞方式(詞串)的可能性乘這個詞串生成我們的句子的可能性。我們進一步容易看到:可以近似地將 P(X|Y) 看作是恆等於 1 的,因為任意假想的一種分詞方式之下生成我們的句子總是精準地生成的(只需把分詞之間的分界符號扔掉即可)。於是,我們就變成了去最大化 P(Y) ,也就是尋找一種分詞使得這個詞串(句子)的概率最大化。而如何計算一個詞串:W1, W2, W3, W4 ..的可能性呢?

我們知道,根據聯合概率的公式展開:P(W1, W2, W3, W4 ..) = P(W1) * P(W2|W1) * P(W3|W2, W1) * P(W4|W1,W2,W3) * .. 於是我們可以通過一系列的條件概率(右式)的乘積來求整個聯合概率。然而不幸的是隨著條件數目的增加(P(Wn|Wn-1,Wn-2,..,W1) 的條件有 n-1 個),資料稀疏問題也會越來越嚴重,即便語料庫再大也無法統計出一個靠譜的 P(Wn|Wn-1,Wn-2,..,W1) 來。

為了緩解這個問題,計算機科學家們一如既往地使用了“天真”假設:我們假設句子中一個詞的出現概率只依賴於它前面的有限的 k 個詞(k 一般不超過 3,如果只依賴於前面的一個詞,就是2元語言模型(2-gram),同理有 3-gram 、 4-gram 等),這個就是所謂的“有限地平線”假設。雖然這個假設似乎有些理想化,但結果卻表明它的結果往往是很強大的,後面要提到的朴素貝葉斯方法使用的假設跟這個精神上是完全一致的,我們會解釋為什麼像這樣一個理想化假設能夠得到強大的結果。

目前我們只要知道,有了這個假設,剛纔那個乘積就可以改寫成: P(W1) * P(W2|W1) * P(W3|W2) * P(W4|W3) .. (假設每個詞只依賴於它前面的一個詞)。而統計 P(W2|W1) 就不再受到資料稀疏問題的困擾了。對於我們上面提到的例子“南京市長江大橋”,如果按照自左到右的貪婪方法分詞的話,結果就成了“南京市長/江大橋”。但如果按照貝葉斯分詞的話(假設使用 3-gram),由於“南京市長”和“江大橋”在語料庫中一起出現的頻率為 0 ,這個整句的概率便會被判定為 0 。從而使得“南京市/長江大橋”這一分詞方式勝出。

2 貝葉斯垃圾郵件過濾器

給定一封郵件,判定它是否屬於垃圾郵件。按照先例,我們還是用D來表示這封郵件,註意D由N個單詞組成。我們用h+來表示垃圾郵件,h-表示正常郵件。問題可以形式化地描述為求:

P(h+|D) = P(h+) * P(D|h+) / P(D)

P(h-|D) = P(h-) * P(D|h-) / P(D)

其中 P(h+) 和 P(h-) 這兩個先驗概率都是很容易求出來的,只需要計算一個郵件庫裡面垃圾郵件和正常郵件的比例就行了。然而 P(D|h+) 卻不容易求,因為 D 裡面含有 N 個單詞 d1, d2, d3, .. ,所以P(D|h+) = P(d1,d2,..,dn|h+) 。我們又一次遇到了資料稀疏性,為何這麼說呢?P(d1,d2,..,dn|h+) 就是說在垃圾郵件當中出現跟我們目前這封郵件一模一樣的一封郵件的概率是非常小的,因為每封郵件都是不同的,世界上有無窮多封郵件。這就是資料稀疏性,因為可以肯定地說,你收集的訓練資料庫不管裡面含了多少封郵件,也不可能找出一封跟目前這封一模一樣的。結果呢?我們又該如何來計算 P(d1,d2,..,dn|h+) 呢?

我們將 P(d1,d2,..,dn|h+)擴展為: P(d1|h+) * P(d2|d1, h+) * P(d3|d2,d1, h+) * .. 。這個式子想必大家並不陌生,這裡我們會使用一個更激進的假設,我們假設 di 與 di-1 是完全條件無關的,於是式子就簡化為 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 。這個就是所謂的條件獨立假設,也正是朴素貝葉斯方法的朴素之處。而計算 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 問題至此就變得簡單了,只要統計di這個單詞在垃圾郵件中出現的頻率即可。

通過以上學習我們發現,由於無法窮舉所有可能性,貝葉斯推斷基本上不能給出肯定的結果。儘管如此,在進行大量的測試後,如果獲得的測試結果都無誤,我們也會對自己的演算法很有信心(即便演算法的準確性尚未確認)。事實上,隨著新的測試結果出現,演算法無誤的可信度也在逐漸改變。

生活中,我們經常有意或無意地運用著貝葉斯定理,從演算法的角度講,如果想真正搞懂其中的原理,還需要對數理統計知識進行更加深入地學習並且不斷實踐,最終相信大家一定能夠有所收穫。

推薦書目:

  • 《貝葉斯方法:概率編程與貝葉斯推斷》

  • 《貝葉斯分析》

  • 《貝葉斯思維:統計建模的Python學習法》

文獻參考:

1. http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html

2. https://wenku.baidu.com/view/8ae844c843323968001c921d.html

3. http://blog.csdn.net/zang141588761/article/details/48780733

4. 貝葉斯方法:概率編程與貝葉斯推斷 (加)卡梅隆 戴維森-皮隆(Cameron Davidson-PiIon) 著;辛願,鐘黎,歐陽婷 譯

來源:資料派THU

近期精彩活動(直接點擊查看):

福利 · 閱讀 | 免費申請讀大資料新書 第21期

END

投稿和反饋請發郵件至hzzy@hzbook.com。轉載大資料公眾號文章,請向原文作者申請授權,否則產生的任何版權糾紛與大資料無關。

大資料

為大家提供與大資料相關的最新技術和資訊。

長按指紋 > 識別圖中二維碼 > 添加關註

近期精彩文章(直接點擊查看):

華為內部狂轉好文,大資料,看這一篇就夠了!

讀完這100篇論文,你也是大資料高手!

如何建立資料分析的思維框架

百度內部培訓資料PPT:資料分析的道與術

論大資料的十大局限

打包帶走!史上最全的大資料分析和製作工具

資料揭秘:中國姓氏排行榜

程式猿分析了42萬字歌詞後,終於搞清楚民謠歌手唱什麼了

計算機告訴你,唐朝詩人之間的關係到底是什麼樣的?

資料分析:微信紅包金額分配的秘密

2000萬人口的大北京,上下班原來是這樣的(附超炫蝌蚪圖)

大資料等IT職業技能圖譜【全套17張,第2版】

不要跟賭場說謊,它真的比你老婆還瞭解你

如果看了這篇文章你還不懂傅里葉變換,那就過來掐死我吧

不做無效的營銷,從不做無效的用戶畫像開始

更多精彩文章,請在公眾號後臺點擊“歷史文章”查看,謝謝。

赞(0)

分享創造快樂