從決策樹學習談到貝葉斯分類算法

轉自：http://blog.csdn.net/v_july_v/article/details/7577684

第一篇：從決策樹學習談到貝葉斯分類算法

引言

    最近在面試中，除了基礎 &  算法 & 項目之外，經常被問到或被要求介紹和描述下自己所知道的幾種分類或聚類算法，而我向來恨對一個東西隻知其皮毛而不得深入，故寫一個有關聚類 & 分類算法的系列文章以作為自己備試之用(盡管貌似已無多大必要，但還是覺得應該寫下以備将來常常回顧思考)。行文雜亂，但僥幸若能對讀者也起到一定幫助，則幸甚至哉。

    本分類 & 聚類算法系列借鑒和參考了兩本書，一本是Tom M.Mitchhell所著的機器學習，一本是資料挖掘導論，這兩本書皆分别是機器學習 & 資料挖掘領域的開山 or 杠鼎之作，讀者有繼續深入下去的興趣的話，不妨在閱讀本文之後，課後細細研讀這兩本書。除此之外，還參考了網上不少牛人的作品(如本文第二部分貝葉斯分類基本上是整理自劉未鵬之手)，在此，皆一一表示感謝。

    本分類 & 聚類算法系列暫稱之為Top 10 Algorithms in Data Mining，其中，各篇分别有以下具體内容：

1. 開篇：決策樹學習，與貝葉斯分類算法；
2. 第二篇：支援向量機SVM(support vector machine)，與神經網絡ANN；
3. 第三篇：待定...

    說白了，一年多以前，我在本blog内寫過一篇文章，叫做： 資料挖掘領域十大經典算法初探(題外話：最初有個出版社的朋友便是是以文找到的我，盡管現在看來，我離出書日期仍是遙遙無期)。現在，我抽取其中幾個最值得一寫的幾個算法每一個都寫一遍，以期對其有個大緻通透的了解。

    OK，全系列任何一篇文章若有任何錯誤，漏洞，或不妥之處，還請讀者們一定要随時不吝賜教 & 指正，謝謝各位。

第一部分、決策樹學習

1.1、什麼是決策樹

    咱們直接切入正題。所謂決策樹，顧名思義，是一種樹，一種依托于政策抉擇而建立起來的樹。

    機器學習中，決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關系。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經曆的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。

    從資料産生決策樹的機器學習技術叫做決策樹學習, 通俗點說就是決策樹。

    來理論的太過抽象，下面舉兩個淺顯易懂的例子：

第一個例子

    套用俗語，決策樹分類的思想類似于找對象。現想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

      女兒：多大年紀了？

      母親：26。

      女兒：長的帥不帥？

      母親：挺帥的。

      女兒：收入高不？

      母親：不算很高，中等情況。

      女兒：是公務員不？

      母親：是，在稅務局上班呢。

      女兒：那好，我去見見。

      這個女孩的決策過程就是典型的分類樹決策。相當于通過年齡、長相、收入和是否公務員對将男人分為兩個類别：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務員，那麼這個可以用下圖表示女孩的決策邏輯：

    也就是說，決策樹的簡單政策就是，好比公司招聘面試過程中篩選一個人的履歷，如果你的條件相當好比如說某985/211重點大學博士畢業，那麼二話不說，直接叫過來面試，如果非重點大學畢業，但實際項目經驗豐富，那麼也要考慮叫過來面試一下，即所謂具體情況具體分析、決策。

第二個例子

    此例子來自Tom M.Mitchell著的機器學習一書：

    小王的目的是通過下周天氣預報尋找什麼時候人們會打高爾夫，他了解到人們決定是否打球的原因最主要取決于天氣情況。而天氣狀況有晴，雲和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風。如此，我們便可以構造一棵決策樹，如下（根據天氣這個分類決策這天是否合适打網球）：

    上述決策樹對應于以下表達式：

（Outlook=Sunny ^Humidity<=70）V （Outlook = Overcast）V （Outlook=Rain ^ Wind=Weak）

1.2、ID3算法

1.2.1、決策樹學習之ID3算法

    ID3算法是決策樹算法的一種。想了解什麼是ID3算法之前，我們得先明白一個概念：奧卡姆剃刀。

• 奧卡姆剃刀（Occam's Razor, Ockham's Razor），又稱“奧坎的剃刀”，是由14世紀邏輯學家、聖方濟各會修士奧卡姆的威廉（William of Occam，約1285年至1349年）提出，他在《箴言書注》2卷15題說“切勿浪費較多東西，去做‘用較少的東西，同樣可以做好的事情’。簡單點說，便是：be simple。

     ID3算法（Iterative Dichotomiser 3 疊代二叉樹3代）是一個由Ross Quinlan發明的用于決策樹的算法。這個算法便是建立在上述所介紹的奧卡姆剃刀的基礎上：越是小型的決策樹越優于大的決策樹（ be simple簡單理論）。盡管如此，該算法也不是總是生成最小的樹形結構，而是一個啟發式算法。

    OK，從資訊論知識中我們知道，期望資訊越小，資訊增益越大，進而純度越高。ID3算法的核心思想就是以資訊增益度量屬性選擇，選擇分裂後資訊增益(很快，由下文你就會知道資訊增益又是怎麼一回事)最大的屬性進行分裂。該算法采用自頂向下的貪婪搜尋周遊可能的決策樹空間。

     是以，ID3的思想便是：

1. 自頂向下的貪婪搜尋周遊可能的決策樹空間構造決策樹(此方法是ID3算法和C4.5算法的基礎)；
2. 從“哪一個屬性将在樹的根節點被測試”開始；
3. 使用統計測試來确定每一個執行個體屬性單獨分類訓練樣例的能力，分類能力最好的屬性作為樹的根結點測試。
4. 然後為根結點屬性的每個可能值産生一個分支，并把訓練樣例排列到适當的分支（也就是說，樣例的該屬性值對應的分支）之下。
5. 重複這個過程，用每個分支結點關聯的訓練樣例來選取在該點被測試的最佳屬性。

這形成了對合格決策樹的貪婪搜尋，也就是算法從不回溯重新考慮以前的選擇。

    下圖所示即是用于學習布爾函數的ID3算法概要：

1.2.2、哪個屬性是最佳的分類屬性

1、資訊增益的度量标準：熵

    上文中，我們提到：“ID3算法的核心思想就是以資訊增益度量屬性選擇，選擇分裂後資訊增益( 很快，由下文你就會知道資訊增益又是怎麼一回事)最大的屬性進行分裂。”接下來，咱們就來看看這個資訊增益是個什麼概念( 當然，在了解資訊增益之前，你必須先了解：資訊增益的度量标準：熵)。     上述的ID3算法的核心問題是選取在樹的每個結點要測試的屬性。我們希望選擇的是最有利于分類執行個體的屬性，資訊增益(Information Gain)是用來 衡量給定的屬性區分訓練樣例的能力，而ID3算法在增長樹的每一步使用資訊增益從候選屬性中選擇屬性。

    為了精确地定義資訊增益，我們先定義資訊論中廣泛使用的一個度量标準，稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。給定包含關于某個目标概念的正反樣例的樣例集S，那麼S相對這個布爾型分類的熵為：

    上述公式中，p+代表正樣例，比如在本文開頭第二個例子中p+則意味着去打羽毛球，而p-則代表反樣例，不去打球(在有關熵的所有計算中我們定義0log0為0)。

    如果寫代碼實作熵的計算，則如下所示：

1. //根據具體屬性和值來計算熵    
2. double ComputeEntropy(vector <vector <string> > remain_state, string attribute, string value,bool ifparent){    
3.     vector<int> count (2,0);    
4.     unsigned int i,j;    
5.     bool done_flag = false;//哨兵值    
6.     for(j = 1; j < MAXLEN; j++){    
7.         if(done_flag) break;    
8.         if(!attribute_row[j].compare(attribute)){    
9.             for(i = 1; i < remain_state.size(); i++){    
10.                 if((!ifparent&&!remain_state[i][j].compare(value)) || ifparent){//ifparent記錄是否算父節點    
11.                     if(!remain_state[i][MAXLEN - 1].compare(yes)){    
12.                         count[0]++;    
13.                     }    
14.                     else count[1]++;    
15.                 }    
16.             }    
17.             done_flag = true;    
18.         }    
19.     }    
20.     if(count[0] == 0 || count[1] == 0 ) return 0;//全部是正執行個體或者負執行個體    
21.     //具體計算熵 根據[+count[0],-count[1]],log2為底通過換底公式換成自然數底數    
22.     double sum = count[0] + count[1];    
23.     double entropy = -count[0]/sum*log(count[0]/sum)/log(2.0) - count[1]/sum*log(count[1]/sum)/log(2.0);    
24.     return entropy;    
25. }    

    舉例來說，假設S是一個關于布爾概念的有14個樣例的集合，它包括9個正例和5個反例（我們采用記号[9+，5-]來概括這樣的資料樣例），那麼S相對于這個布爾樣例的熵為：

Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。

     So，根據上述這個公式，我們可以得到：S的所有成員屬于同一類，Entropy(S)=0； S的正反樣例數量相等，Entropy(S)=1；S的正反樣例數量不等，熵介于0，1之間，如下圖所示：

    資訊論中對熵的一種解釋，熵确定了要編碼集合S中任意成員的分類所需要的最少二進制位數。更一般地，如果目标屬性具有c個不同的值，那麼S相對于c個狀态的分類的熵定義為：

     Pi為子集合中不同性(而二進制分類即正樣例和負樣例)的樣例的比例。

2、資訊增益度量期望的熵降低

資訊增益Gain(S,A)定義

    已經有了熵作為衡量訓練樣例集合純度的标準，現在可以定義屬性分類訓練資料的效力的度量标準。這個标準被稱為“資訊增益（information gain）”。簡單的說，一個屬性的資訊增益就是由于使用這個屬性分割樣例而導緻的期望熵降低(或者說，樣本按照某屬性劃分時造成熵減少的期望)。更精确地講，一個屬性A相對樣例集合S的資訊增益Gain(S,A)被定義為：

    其中 Values(A)是屬性A所有可能值的集合，是S中屬性A的值為v的子集。換句話來講，Gain(S,A)是由于給定屬性A的值而得到的關于目标函數值的資訊。當對S的一個任意成員的目标值編碼時，Gain(S,A)的值是在知道屬性A的值後可以節省的二進制位數。

    接下來，有必要提醒讀者一下：關于下面這兩個概念 or 公式，

1. 

2. 

    第一個Entropy(S)是熵定義，第二個則是資訊增益Gain(S,A)的 定義，而Gain(S,A)由第一個Entropy(S)計算出，記住了。

    下面，舉個例子，假定S是一套有關天氣的訓練樣例，描述它的屬性包括可能是具有Weak和Strong兩個值的Wind。像前面一樣，假定S包含14個樣例，[9+，5-]。在這14個樣例中，假定正例中的6個和反例中的2個有Wind =Weak，其他的有Wind=Strong。由于按照屬性Wind分類14個樣例得到的資訊增益可以計算如下。

    運用在本文開頭舉得第二個根據天氣情況是否決定打羽毛球的例子上，得到的最佳分類屬性如下圖所示：

     在上圖中，計算了兩個不同屬性：濕度(humidity)和風力(wind)的資訊增益，最終humidity這種分類的資訊增益0.151>wind增益的0.048。說白了，就是在星期六上午是否适合打網球的問題訣策中，采取humidity較wind作為分類屬性更佳，決策樹由此而來。

1. //計算資訊增益，DFS建構決策樹    
2. //current_node為目前的節點    
3. //remain_state為剩餘待分類的樣例    
4. //remian_attribute為剩餘還沒有考慮的屬性    
5. //傳回根結點指針    
6. Node * BulidDecisionTreeDFS(Node * p, vector <vector <string> > remain_state, vector <string> remain_attribute){    
7.     //if(remain_state.size() > 0){    
8.         //printv(remain_state);    
9.     //}    
10.     if (p == NULL)    
11.         p = new Node();    
12.     //先看搜尋到樹葉的情況    
13.     if (AllTheSameLabel(remain_state, yes)){    
14.         p->attribute = yes;    
15.         return p;    
16.     }    
17.     if (AllTheSameLabel(remain_state, no)){    
18.         p->attribute = no;    
19.         return p;    
20.     }    
21.     if(remain_attribute.size() == 0){//所有的屬性均已經考慮完了,還沒有分盡    
22.         string label = MostCommonLabel(remain_state);    
23.         p->attribute = label;    
24.         return p;    
25.     }    
26.     double max_gain = 0, temp_gain;    
27.     vector <string>::iterator max_it;    
28.     vector <string>::iterator it1;    
29.     for(it1 = remain_attribute.begin(); it1 < remain_attribute.end(); it1++){    
30.         temp_gain = ComputeGain(remain_state, (*it1));    
31.         if(temp_gain > max_gain) {    
32.             max_gain = temp_gain;    
33.             max_it = it1;    
34.         }    
35.     }    
36.     //下面根據max_it指向的屬性來劃分目前樣例，更新樣例集和屬性集    
37.     vector <string> new_attribute;    
38.     vector <vector <string> > new_state;    
39.     for(vector <string>::iterator it2 = remain_attribute.begin(); it2 < remain_attribute.end(); it2++){    
40.         if((*it2).compare(*max_it)) new_attribute.push_back(*it2);    
41.     }    
42.     //确定了最佳劃分屬性，注意儲存    
43.     p->attribute = *max_it;    
44.     vector <string> values = map_attribute_values[*max_it];    
45.     int attribue_num = FindAttriNumByName(*max_it);    
46.     new_state.push_back(attribute_row);    
47.     for(vector <string>::iterator it3 = values.begin(); it3 < values.end(); it3++){    
48.         for(unsigned int i = 1; i < remain_state.size(); i++){    
49.             if(!remain_state[i][attribue_num].compare(*it3)){    
50.                 new_state.push_back(remain_state[i]);    
51.             }    
52.         }    
53.         Node * new_node = new Node();    
54.         new_node->arrived_value = *it3;    
55.         if(new_state.size() == 0){//表示目前沒有這個分支的樣例，目前的new_node為葉子節點    
56.             new_node->attribute = MostCommonLabel(remain_state);    
57.         }    
58.         else     
59.             BulidDecisionTreeDFS(new_node, new_state, new_attribute);    
60.         //遞歸函數傳回時即回溯時需要1 将新結點加入父節點孩子容器 2清除new_state容器    
61.         p->childs.push_back(new_node);    
62.         new_state.erase(new_state.begin()+1,new_state.end());//注意先清空new_state中的前一個取值的樣例，準備周遊下一個取值樣例    
63.     }    
64.     return p;    
65. }    

1.2.3、ID3算法決策樹的形成

    OK，下圖為ID3算法第一步後形成的部分決策樹。這樣綜合起來看，就容易了解多了。1、overcast樣例必為正，是以為葉子結點，總為yes；2、ID3無回溯，局部最優，而非全局最優，還有另一種樹後修剪決策樹。下圖是ID3算法第一步後形成的部分決策樹：

    如上圖，訓練樣例被排列到對應的分支結點。分支Overcast的所有樣例都是正例，是以成為目标分類為Yes的葉結點。另兩個結點将被進一步展開，方法是按照新的樣例子集選取資訊增益最高的屬性。

1.3、C4.5算法

1.3.1、ID3算法的改進：C4.5算法

    C4.5，是機器學習算法中的另一個分類決策樹算法，它是決策樹(決策樹也就是做決策的節點間的組織方式像一棵樹，其實是一個倒樹)核心算法，也是上文1.2節所介紹的ID3的改進算法，是以基本上了解了一半決策樹構造方法就能構造它。

    決策樹構造方法其實就是每次選擇一個好的特征以及分裂點作為目前節點的分類條件。

    既然說C4.5算法是ID3的改進算法，那麼C4.5相比于ID3改進的地方有哪些呢？：

1. 用資訊增益率來選擇屬性。ID3選擇屬性用的是子樹的資訊增益，這裡可以用很多方法來定義資訊，ID3使用的是熵(entropy，熵是一種不純度度量準則),也就是熵的變化值，而C4.5用的是資訊增益率。對，差別就在于一個是資訊增益，一個是資訊增益率。
2. 在樹構造過程中進行剪枝，在構造決策樹的時候，那些挂着幾個元素的節點，不考慮最好，不然容易導緻overfitting。
3. 對非離散資料也能處理。
4. 能夠對不完整資料進行處理

    針對上述第一點，解釋下：一般來說率就是用來取平衡用的，就像方差起的作用差不多，比如有兩個跑步的人，一個起點是10m/s的人、其10s後為20m/s；另一個人起速是1m/s、其1s後為2m/s。如果緊緊算內插補點那麼兩個差距就很大了，如果使用速度增加率(加速度，即都是為1m/s^2)來衡量，2個人就是一樣的加速度。是以，C4.5克服了ID3用資訊增益選擇屬性時偏向選擇取值多的屬性的不足。

C4.5算法之資訊增益率

    OK，既然上文中提到C4.5用的是資訊增益率，那增益率的具體是如何定義的呢？：

    是的，在這裡，C4.5算法不再是通過資訊增益來選擇決策屬性。一個可以選擇的度量标準是增益比率gain ratio（Quinlan 1986）。增益比率度量是用前面的增益度量Gain(S，A)和分裂資訊度量SplitInformation(S，A)來共同定義的，如下所示：

    其中，分裂資訊度量被定義為( 分裂資訊用來衡量屬性分裂資料的廣度和均勻)：

    其中S1到Sc是c個值的屬性A分割S而形成的c個樣例子集。注意分裂資訊實際上就是S關于屬性A的各值的熵。這與我們前面對熵的使用不同，在那裡我們隻考慮S關于學習到的樹要預測的目标屬性的值的熵。

    請注意，分裂資訊項阻礙選擇值為均勻分布的屬性。例如，考慮一個含有n個樣例的集合被屬性A徹底分割（譯注：分成n組，即一個樣例一組）。這時分裂資訊的值為log2n。相反，一個布爾屬性B分割同樣的n個執行個體，如果恰好平分兩半，那麼分裂資訊是1。如果屬性A和B産生同樣的資訊增益，那麼根據增益比率度量，明顯B會得分更高。

    使用增益比率代替增益來選擇屬性産生的一個實際問題是，當某個Si接近S（|Si|»|S|）時分母可能為0或非常小。如果某個屬性對于S的所有樣例有幾乎同樣的值，這時要麼導緻增益比率未定義，要麼是增益比率非常大。為了避免選擇這種屬性，我們可以采用這樣一些啟發式規則，比如先計算每個屬性的增益，然後僅對那些增益高過平均值的屬性應用增益比率測試（Quinlan 1986）。

    除了資訊增益，Lopez de Mantaras（1991）介紹了另一種直接針對上述問題而設計的度量，它是基于距離的（distance-based）。這個度量标準基于所定義的一個資料劃分間的距離尺度。具體更多請參看：Tom M.Mitchhell所著的機器學習之3.7.3節。

1.3.2、C4.5算法構造決策樹的過程

1. Function C4.5(R:包含連續屬性的無類别屬性集合,C:類别屬性,S:訓練集)  
2. Begin  
3.    If S為空,傳回一個值為Failure的單個節點;  
4.    If S是由相同類别屬性值的記錄組成,  
5.       傳回一個帶有該值的單個節點;  
6.    If R為空,則傳回一個單節點,其值為在S的記錄中找出的頻率最高的類别屬性值;  
7.    [注意未出現錯誤則意味着是不适合分類的記錄]；  
8.   For 所有的屬性R(Ri) Do  
9.         If 屬性Ri為連續屬性，則  
10.      Begin  
11.            将Ri的最小值賦給A1：  
12.         将Rm的最大值賦給Am；  
13.            For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m;  
14.            将Ri點的基于{< =Aj,>Aj}的最大資訊增益屬性(Ri,S)賦給A；  
15.      End；  
16.   将R中屬性之間具有最大資訊增益的屬性(D,S)賦給D;  
17.    将屬性D的值賦給{dj/j=1,2...m}；  
18.   将分别由對應于D的值為dj的記錄組成的S的子集賦給{sj/j=1,2...m};  
19.    傳回一棵樹，其根标記為D;樹枝标記為d1,d2...dm;  
20.    再分别構造以下樹:  
21.    C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);  
22. End C4.5  

1.3.3、C4.5算法實作中的幾個關鍵步驟

    在上文中，我們已經知道了決策樹學習C4.5算法中4個重要概念的表達，如下：

1. 

2. 

3. 

4. 

    接下來，咱們寫下代碼實作，     1、資訊熵

1. double C4_5::entropy(int *attrClassCount, int classNum, int allNum){  
2.     double iEntropy = 0.0;  
3.     for(int i = 0; i < classNum; i++){  
4.         double temp = ((double)attrClassCount[i]) / allNum;  
5.         if(temp != 0.0)  
6.             iEntropy -= temp * (log(temp) / log(2.0));  
7.     }  
8.     return iEntropy;  
9. }  

    2、資訊增益率

1. double C4_5::gainRatio(int classNum, vector<int *> attriCount, double pEntropy){  
2.     int* attriNum = new int[attriCount.size()];  
3.     int allNum = 0;  
4.     for(int i = 0; i < (int)attriCount.size(); i++){  
5.         attriNum[i] = 0;  
6.         for(int j = 0; j < classNum; j++){  
7.             attriNum[i] += attriCount[i][j];  
8.             allNum += attriCount[i][j];  
9.         }  
10.     }  
11.     double gain = 0.0;  
12.     double splitInfo = 0.0;  
13.     for(int i = 0; i < (int)attriCount.size(); i++){  
14.         gain -= ((double)attriNum[i]) / allNum * entropy(attriCount[i], classNum, attriNum[i]);  
15.         splitInfo -= ((double)attriNum[i]) / allNum * (log(((double)attriNum[i])/allNum) / log(2.0));  
16.     }  
17.     gain += pEntropy;  
18.     delete[] attriNum;   
19.     return (gain / splitInfo);  
20. }  

     3、選取最大增益屬性作為分類條件

1. int C4_5::chooseAttribute(vector<int> attrIndex, vector<int *>* sampleCount){  
2.     int bestIndex = 0;  
3.     double maxGainRatio = 0.0;  
4.     int classNum = (int)(decisions[attrIndex[(int)attrIndex.size()-1]]).size();//number of class  
5.     //computer the class entropy  
6.     int* temp = new int[classNum];  
7.     int allNum = 0;  
8.     for(int i = 0; i < classNum; i++){  
9.         temp[i] = sampleCount[(int)attrIndex.size()-1][i][i];  
10.         allNum += temp[i];  
11.     }  
12.     double pEntropy = entropy(temp, classNum, allNum);  
13.     delete[] temp;  
14.     //computer gain ratio for every attribute  
15.     for(int i = 0; i < (int)attrIndex.size()-1; i++){  
16.         double gainR = gainRatio(classNum, sampleCount[i], pEntropy);  
17.         if(gainR > maxGainRatio){  
18.             bestIndex = i;  
19.             maxGainRatio = gainR;  
20.         }  
21.     }  
22.     return bestIndex;  
23. }  

    4、還有一系列建樹，列印樹的步驟，此處略過。

1.4、決策樹歸納的特點

    略過....

第二部分、貝葉斯分類

    說實話，友人劉未鵬有一篇講的貝葉斯的文章： 數學之美番外篇：平凡而又神奇的貝葉斯方法，已經把貝葉斯講的很清晰透徹了，我再講也是如李白看到崔颢在黃鶴樓上所提的：登黃鶴樓

昔人已乘黃鶴去，此地空餘黃鶴樓； 黃鶴一去不複返，白雲千載空悠悠。

    後便大為折服，已無什興緻再提了(偶現在就是這感覺)。然文章還得繼續寫，那就權當是對它的一個總結或整理吧，有任何不妥之處，還望讀者和未鵬兄海涵，謝謝。

2.1、什麼是貝葉斯分類

   貝葉斯定理：已知某條件機率，如何得到兩個事件交換後的機率，也就是在已知P(A|B)的情況下如何求得P(B|A)。這裡先解釋什麼是條件機率：

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

。

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

      下面不加證明地直接給出貝葉斯定理（公式被網友指出有問題，待後續驗證改正）：

     So，其一般形式就是：

P(A|B) = P(A|B) * P(B) / [P(A|B) * P(B) + P(A|~B) * P(~B) ]

    收縮起來就是：

P(A|B) = P(AB) / P(B)

    其實這個就等于：

P(A|B) * P(B) = P(AB)

    然看似這麼平凡的貝葉斯公式，背後卻隐含着非常深刻的原理。

2.2、拼寫糾正

    經典著作《人工智能：現代方法》的作者之一 Peter Norvig 曾經寫過一篇介紹如何寫一個拼寫檢查/糾正器的文章，裡面用到的就是貝葉斯方法，這裡我們不打算複述他寫的文章，而是簡要地将其核心思想介紹一下。

    首先，我們需要詢問的是：“問題是什麼？”

    問題是我們看到使用者輸入了一個不在字典中的單詞，我們需要去猜測：“這個家夥到底真正想輸入的單詞是什麼呢？”用剛才我們形式化的語言來叙述就是，我們需要求：

P(我們猜測他想輸入的單詞 | 他實際輸入的單詞)

    這個機率。并找出那個使得這個機率最大的猜測單詞。顯然，我們的猜測未必是唯一的，就像前面舉的那個自然語言的歧義性的例子一樣；這裡，比如使用者輸入： thew ，那麼他到底是想輸入 the ，還是想輸入 thaw ？到底哪個猜測可能性更大呢？幸運的是我們可以用貝葉斯公式來直接出它們各自的機率，我們不妨将我們的多個猜測記為 h1 h2 .. （ h 代表 hypothesis），它們都屬于一個有限且離散的猜測空間 H （單詞總共就那麼多而已），将使用者實際輸入的單詞記為 D （ D 代表 Data ，即觀測資料），于是

P(我們的猜測1 | 他實際輸入的單詞)

    可以抽象地記為：

P(h1 | D)

    類似地，對于我們的猜測2，則是 P(h2 | D)。不妨統一記為：

P(h | D)

運用一次貝葉斯公式，我們得到：

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

    對于不同的具體猜測 h1 h2 h3 .. ，P(D) 都是一樣的，是以在比較 P(h1 | D) 和 P(h2 | D) 的時候我們可以忽略這個常數。即我們隻需要知道：

P(h | D) ∝ P(h) * P(D | h) （注：那個符号的意思是“正比例于”，不是無窮大，注意符号右端是有一個小缺口的。）

    這個式子的抽象含義是：對于給定觀測資料，一個猜測是好是壞，取決于“這個猜測本身獨立的可能性大小（先驗機率，Prior ）”和“這個猜測生成我們觀測到的資料的可能性大小”（似然，Likelihood ）的乘積。具體到我們的那個 thew 例子上，含義就是，使用者實際是想輸入 the 的可能性大小取決于 the 本身在詞彙表中被使用的可能性（頻繁程度）大小（先驗機率）和 想打 the 卻打成 thew 的可能性大小（似然）的乘積。

    剩下的事情就很簡單了，對于我們猜測為可能的每個單詞計算一下 P(h) * P(D | h) 這個值，然後取最大的，得到的就是最靠譜的猜測。更多細節請參看未鵬兄之原文。

2.3、貝葉斯的應用

2.3.1、中文分詞

    貝葉斯是機器學習的核心方法之一。比如中文分詞領域就用到了貝葉斯。浪潮之巅的作者吳軍在《數學之美》系列中就有一篇是介紹中文分詞的。這裡介紹一下核心的思想，不做贅述，詳細請參考吳軍的原文。

    分詞問題的描述為：給定一個句子（字串），如：

    南京市長江大橋

    如何對這個句子進行分詞（詞串）才是最靠譜的。例如：

1. 南京市/長江大橋

2. 南京/市長/江大橋

    這兩個分詞，到底哪個更靠譜呢？

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

P(Y|X) ∝ P(Y)*P(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.3.2、貝葉斯圖像識别，Analysis by Synthesis

    貝葉斯方法是一個非常 general 的推理架構。其核心理念可以描述成：Analysis by Synthesis （通過合成來分析）。06 年的認知科學新進展上有一篇 paper 就是講用貝葉斯推理來解釋視覺識别的，一圖勝千言，下圖就是摘自這篇 paper ：

    首先是視覺系統提取圖形的邊角特征，然後使用這些特征自底向上地激活高層的抽象概念（比如是 E 還是 F 還是等号），然後使用一個自頂向下的驗證來比較到底哪個概念最佳地解釋了觀察到的圖像。

2.3.3、EM 算法與基于模型的聚類

     聚類是一種無指導的機器學習問題，問題描述：給你一堆資料點，讓你将它們最靠譜地分成一堆一堆的。聚類算法很多，不同的算法适應于不同的問題，這裡僅介紹一個基于模型的聚類，該聚類算法對資料點的假設是，這些資料點分别是圍繞 K 個核心的 K 個正态分布源所随機生成的，使用 Han JiaWei 的《Data Ming： Concepts and Techniques》中的圖：

    圖中有兩個正态分布核心，生成了大緻兩堆點。我們的聚類算法就是需要根據給出來的那些點，算出這兩個正态分布的核心在什麼位置，以及分布的參數是多少。這很明顯又是一個貝葉斯問題，但這次不同的是，答案是連續的且有無窮多種可能性，更糟的是，隻有當我們知道了哪些點屬于同一個正态分布圈的時候才能夠對這個分布的參數作出靠譜的預測，現在兩堆點混在一塊我們又不知道哪些點屬于第一個正态分布，哪些屬于第二個。反過來，隻有當我們對分布的參數作出了靠譜的預測時候，才能知道到底哪些點屬于第一個分布，那些點屬于第二個分布。這就成了一個先有雞還是先有蛋的問題了。為了解決這個循環依賴，總有一方要先打破僵局，說，不管了，我先随便整一個值出來，看你怎麼變，然後我再根據你的變化調整我的變化，然後如此疊代着不斷互相推導，最終收斂到一個解。這就是 EM 算法。

    EM 的意思是“Expectation-Maximazation”，在這個聚類問題裡面，我們是先随便猜一下這兩個正态分布的參數：如核心在什麼地方，方差是多少。然後計算出每個資料點更可能屬于第一個還是第二個正态分布圈，這個是屬于 Expectation 一步。有了每個資料點的歸屬，我們就可以根據屬于第一個分布的資料點來重新評估第一個分布的參數（從蛋再回到雞），這個是 Maximazation 。如此往複，直到參數基本不再發生變化為止。這個疊代收斂過程中的貝葉斯方法在第二步，根據資料點求分布的參數上面。

2.3.4、最大似然與最小二乘

    學過線性代數的大概都知道經典的最小二乘方法來做線性回歸。問題描述是：給定平面上 N 個點，（這裡不妨假設我們想用一條直線來拟合這些點——回歸可以看作是拟合的特例，即允許誤差的拟合），找出一條最佳描述了這些點的直線。

    一個接踵而來的問題就是，我們如何定義最佳？我們設每個點的坐标為 (Xi, Yi) 。如果直線為 y = f(x) 。那麼 (Xi, Yi) 跟直線對這個點的“預測”：(Xi, f(Xi)) 就相差了一個 ΔYi = |Yi – f(Xi)| 。最小二乘就是說尋找直線使得 (ΔY1)^2 + (ΔY2)^2 + .. （即誤差的平方和）最小，至于為什麼是誤差的平方和而不是誤差的絕對值和，統計學上也沒有什麼好的解釋。然而貝葉斯方法卻能對此提供一個完美的解釋。

    我們假設直線對于坐标 Xi 給出的預測 f(Xi) 是最靠譜的預測，所有縱坐标偏離 f(Xi) 的那些資料點都含有噪音，是噪音使得它們偏離了完美的一條直線，一個合理的假設就是偏離路線越遠的機率越小，具體小多少，可以用一個正态分布曲線來模拟，這個分布曲線以直線對 Xi 給出的預測 f(Xi) 為中心，實際縱坐标為 Yi 的點 (Xi, Yi) 發生的機率就正比于 EXP[-(ΔYi)^2]。（EXP(..) 代表以常數 e 為底的多少次方）。

    現在我們回到問題的貝葉斯方面，我們要想最大化的後驗機率是：

P(h|D) ∝ P(h) * P(D|h)

    又見貝葉斯！這裡 h 就是指一條特定的直線，D 就是指這 N 個資料點。我們需要尋找一條直線 h 使得 P(h) * P(D|h) 最大。很顯然，P(h) 這個先驗機率是均勻的，因為哪條直線也不比另一條更優越。是以我們隻需要看 P(D|h) 這一項，這一項是指這條直線生成這些資料點的機率，剛才說過了，生成資料點 (Xi, Yi) 的機率為 EXP[-(ΔYi)^2] 乘以一個常數。而 P(D|h) = P(d1|h) * P(d2|h) * .. 即假設各個資料點是獨立生成的，是以可以把每個機率乘起來。于是生成 N 個資料點的機率為 EXP[-(ΔY1)^2] * EXP[-(ΔY2)^2] * EXP[-(ΔY3)^2] * .. = EXP{-[(ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + ..]} 最大化這個機率就是要最小化 (ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + .. 。 熟悉這個式子嗎？

2.4、樸素貝葉斯方法

    樸素貝葉斯方法是一個很特别的方法，是以值得介紹一下。我們用樸素貝葉斯在垃圾郵件過濾中的應用來舉例說明。

2.4.1、貝葉斯垃圾郵件過濾器

    問題是什麼？問題是，給定一封郵件，判定它是否屬于垃圾郵件。按照先例，我們還是用 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 這個單詞在垃圾郵件中出現的頻率即可。關于貝葉斯垃圾郵件過濾更多的内容可以參考這個條目，注意其中提到的其他資料。

2.5、層級貝葉斯模型

    層級貝葉斯模型是現代貝葉斯方法的标志性建築之一。前面講的貝葉斯，都是在同一個事物層次上的各個因素之間進行統計推理，然而層次貝葉斯模型在哲學上更深入了一層，将這些因素背後的因素（原因的原因，原因的原因，以此類推）囊括進來。一個教科書例子是：如果你手頭有 N 枚硬币，它們是同一個工廠鑄出來的，你把每一枚硬币擲出一個結果，然後基于這 N 個結果對這 N 個硬币的 θ （出現正面的比例）進行推理。如果根據最大似然，每個硬币的 θ 不是 1 就是 0 （這個前面提到過的），然而我們又知道每個硬币的 p(θ) 是有一個先驗機率的，也許是一個 beta 分布。也就是說，每個硬币的實際投擲結果 Xi 服從以 θ 為中心的正态分布，而 θ 又服從另一個以 Ψ 為中心的 beta 分布。層層因果關系就展現出來了。進而 Ψ 還可能依賴于因果鍊上更上層的因素，以此類推。

2.6、隐馬可夫模型（HMM）

    吳軍在數學之美系列裡面介紹的隐馬可夫模型（HMM）就是一個簡單的層級貝葉斯模型：

那麼怎麼根據接收到的資訊來推測說話者想表達的意思呢？我們可以利用叫做“隐含馬爾可夫模型”（Hidden Markov Model）來解決這些問題。以語音識别為例，當我們觀測到語音信号 o1,o2,o3 時，我們要根據這組信号推測出發送的句子 s1,s2,s3。顯然，我們應該在所有可能的句子中找最有可能性的一個。用數學語言來描述，就是在已知 o1,o2,o3,…的情況下，求使得條件機率 P (s1,s2,s3,…|o1,o2,o3….) 達到最大值的那個句子 s1,s2,s3,…

    吳軍的文章中這裡省掉沒說的是，s1, s2, s3, .. 這個句子的生成機率同時又取決于一組參數，這組參數決定了 s1, s2, s3, .. 這個馬可夫鍊的先驗生成機率。如果我們将這組參數記為 λ ，我們實際上要求的是：P(S|O, λ) （其中 O 表示 o1,o2,o3,.. ，S表示 s1,s2,s3,..）

當然，上面的機率不容易直接求出，于是我們可以間接地計算它。利用貝葉斯公式并且省掉一個常數項，可以把上述公式等價變換成

P(o1,o2,o3,…|s1,s2,s3….) * P(s1,s2,s3,…)

其中

P(o1,o2,o3,…|s1,s2,s3….) 表示某句話 s1,s2,s3…被讀成 o1,o2,o3,…的可能性, 而 P(s1,s2,s3,…) 表示字串 s1,s2,s3,…本身能夠成為一個合乎情理的句子的可能性，是以這個公式的意義是用發送信号為 s1,s2,s3…這個數列的可能性乘以 s1,s2,s3.. 本身可以一個句子的可能性，得出機率。

    這裡，s1,s2,s3…本身可以一個句子的可能性其實就取決于參數 λ ，也就是語言模型。是以簡而言之就是發出的語音信号取決于背後實際想發出的句子，而背後實際想發出的句子本身的獨立先驗機率又取決于語言模型。更多具體細節請參考未鵬兄之：數學之美番外篇：平凡而又神奇的貝葉斯方法。

參考文獻

1. 機器學習，Tom M.Mitchhell著；
2. 資料挖掘導論，[美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著；
3. 資料挖掘領域十大經典算法初探；
4. 數學之美番外篇：平凡而又神奇的貝葉斯方法(本文第二部分、貝葉斯分類主要來自此文)。
5. http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html；
6. 數學之美：http://www.google.com.hk/ggblog/googlechinablog/2006/04/blog-post_2507.html；
7. 決策樹ID3分類算法的C++實作 & yangliuy：http://blog.csdn.net/yangliuy/article/details/7322015。

後記

    促成自己寫這篇文章乃至整個聚類 & 分類算法系列的有3個因素，

1. 一的确是如本文開頭所說，在最近參加的一些面試中被問到描述自己所知道或了解的聚類 & 分類算法(當然，這完全不代表你将來的面試中會遇到此類問題，隻是因為我的履歷上寫了句熟悉常見的聚類 & 分類算法而已)，
2. 二則是之前去一家公司面試，他們有資料挖掘工程師的崗位，原來是真有那麼一群人是專門負責資料分析，算法決策與調研的，情不自禁的對資料挖掘産生了興趣；
3. 三則是手頭上有兩本這樣的經典書籍：機器學習 & 資料挖掘導論，看看又何妨呢，看的同時寫寫文章，做做筆記，備忘錄又有何不可呢？

    最後一件事：關于讀書會第3期周愛民 & 梁斌，時間：本周日5月20日下午2點，地點：北大二教527。報名：發姓名 + 公司職位 or 學校專業 + 專注方向至郵箱：[email protected]。詳情，請參見此文：讀書會·北京：最新第3期05.20下午周愛民 ，梁斌penny于北大舉辦。歡迎朋友們的到來。

    研究了一年有餘的資料結構方面的算法，現在可以逐漸轉向應用方面(機器學習 & 資料挖掘)的算法學習了。OK，本文或本聚類 & 分類算法系列中任何一篇文章有任何問題，漏洞，或bug，歡迎任何讀者随時不吝賜教 & 指正，感謝大家，謝謝。完。July、二零一二年五月十八日淩晨二點半。