從決策樹學(xué)習(xí)談到貝葉斯分類算法、EM、HMM(共41頁)

1、第一篇：從決策樹學(xué)習(xí)(xux)談到貝葉斯分類算法、EM、HMM引言(ynyn) 最近(zujn)在面試中，除了基礎(chǔ) & 算法 & 項目之外，經(jīng)常被問到或被要求介紹和描述下自己所知道的幾種分類或聚類算法(當然，這完全不代表你將來的面試中會遇到此類問題，只是因為我的簡歷上寫了句：熟悉常見的聚類 & 分類算法而已)，而我向來恨對一個東西只知其皮毛而不得深入，故寫一個有關(guān)數(shù)據(jù)挖掘十大算法的系列文章以作為自己備試之用，甚至以備將來常?；仡櫵伎肌Ｐ形碾s亂，但僥幸若能對讀者起到一點幫助，則幸甚至哉。 本文借鑒和參考了兩本書，一本是Tom M.Mitchhell所著的機器學(xué)習(xí)，一本是數(shù)據(jù)挖掘?qū)д摚@兩本書皆分

2、別是機器學(xué)習(xí) & 數(shù)據(jù)挖掘領(lǐng)域的開山 or 杠鼎之作，讀者有繼續(xù)深入下去的興趣的話，不妨在閱讀本文之后，課后細細研讀這兩本書。除此之外，還參考了網(wǎng)上不少牛人的作品(文末已注明參考文獻或鏈接)，在此，皆一一表示感謝(從本質(zhì)上來講，本文更像是一篇讀書 & 備忘筆記)。 本系列暫稱之為 HYPERLINK /v_july_v/article/category/1061301 t _blank Top 10 Algorithms in Data Mining，其中，各篇分別有以下具體內(nèi)容：開篇：即本文從決策樹學(xué)習(xí)談到貝葉斯分類算法、EM、HMM；第二篇： HYPERLINK /v_july_v/art

3、icle/details/7624837 t _blank 支持向量機通俗導(dǎo)論（理解SVM的三層境界）；第三篇： HYPERLINK /v_july_v/article/details/8203674 t _blank 從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法；第四篇：神經(jīng)網(wǎng)絡(luò) 待寫. 說白了，一年多以前，我在本blog內(nèi)寫過一篇文章，叫做： HYPERLINK /v_july_v/article/details/6142146 t _blank 數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法初探(題外話：最初有個出版社的朋友便是因此文找到的我，盡管現(xiàn)在看來，我離出書日期仍是遙遙無期)。現(xiàn)在，我抽取其

4、中幾個最值得一寫的幾個算法每一個都寫一遍，以期對其有個大致通透的了解。 OK，全系列任何一篇文章若有任何錯誤，漏洞，或不妥之處，還請讀者們一定要隨時不吝賜教 & 指正，謝謝各位。分類與聚類，監(jiān)督(jind)學(xué)習(xí)與無監(jiān)督學(xué)習(xí) 在講具體的分類和聚類算法之前(zhqin)，有必要講一下什么是分類，什么是 HYPERLINK /wiki/%E6%95%B0%E6%8D%AE%E8%81%9A%E7%B1%BB t _blank 聚類，以及都包含哪些(nxi)具體算法或問題。Classification (分類)，對于一個 classifier ，通常需要你告訴它“這個東西被分為某某類”這樣一些例子，理

5、想情況下，一個 classifier 會從它得到的訓(xùn)練集中進行“學(xué)習(xí)”，從而具備對未知數(shù)據(jù)進行分類的能力，這種提供訓(xùn)練數(shù)據(jù)的過程通常叫做 supervised learning (監(jiān)督學(xué)習(xí))，而Clustering(聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們并不關(guān)心某一類是什么，我們需要實現(xiàn)的目標只是把相似的東西聚到一起，因此，一個聚類算法通常只需要知道如何計算相似 度就可以開始工作了，因此 clustering 通常并不需要使用訓(xùn)練數(shù)據(jù)進行學(xué)習(xí)，這在 Machine Learning 中被稱作 unsupervised learning (無監(jiān)督學(xué)習(xí)). 常見的分類與聚類算法

6、 所謂分類分類，簡單來說，就是根據(jù)文本的特征或?qū)傩?，劃分到已有的類別中。如在自然語言處理NLP中，我們經(jīng)常提到的文本分類便就是一個分類問題，一般的模式分類方法都可用于文本分類研究。常用的分類算法包括：決策樹分類法，樸素的貝葉斯分類算法(native Bayesian classifier)、基于 HYPERLINK /v_july_v/article/details/7624837 t _blank 支持向量機(SVM)的分類器，神經(jīng)網(wǎng)絡(luò)法，k-最近鄰法(k-nearest neighbor，kNN)，模糊分類法等等(所有這些分類算法日后在本blog內(nèi)都會一一陸續(xù)闡述)。 分類作為一種監(jiān)督學(xué)習(xí)

7、方法，要求必須事先明確知道各個類別的信息，并且斷言所有待分類項都有一個類別與之對應(yīng)。但是很多時候上述條件得不到滿足，尤其是在處理海量數(shù)據(jù)的時候，如果通過預(yù)處理使得數(shù)據(jù)滿足分類算法的要求，則代價非常大，這時候可以考慮使用聚類算法。 而K均值(K-means clustering)聚類則是最典型的聚類算法(當然，除此之外，還有很多諸如屬于劃分法K-MEDOIDS算法、CLARANS算法；屬于層次法的BIRCH算法、CURE算法、CHAMELEON算法等；基于密度的方法：DBSCAN算法、OPTICS算法、DENCLUE算法等；基于網(wǎng)格的方法：STING算法、CLIQUE算法、WAVE-CLUSTE

8、R算法；基于模型的方法，本系列后續(xù)會介紹其中幾種)。 監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí) 機器學(xué)習(xí)發(fā)展到現(xiàn)在，一般劃分為 監(jiān)督學(xué)習(xí)(supervised learning)，半監(jiān)督學(xué)習(xí)(semi-supervised learning)以及無監(jiān)督學(xué)習(xí)(unsupervised learning)三類。舉個具體的對應(yīng)例子，則是比如說，在NLP詞義消岐中，也分為監(jiān)督的消岐方法，和無監(jiān)督的消岐方法。在有監(jiān)督的消岐方法中，訓(xùn)練數(shù)據(jù)是已知的，即每個詞的語義分類是被標注了的；而在無監(jiān)督的消岐方法中，訓(xùn)練數(shù)據(jù)是未經(jīng)標注的。 上面所介紹的常見的分類算法(sun f)屬于監(jiān)督學(xué)習(xí)，聚類則屬于無監(jiān)督學(xué)習(xí)(反過來說，監(jiān)督學(xué)習(xí)屬于

9、分類(fn li)算法則不準確，因為監(jiān)督學(xué)習(xí)只是說我們給樣本sample同時(tngsh)打上了標簽（label），然后同時利用樣本和標簽進行相應(yīng)的學(xué)習(xí)任務(wù)，而不是僅僅局限于分類任務(wù)。常見的其他監(jiān)督問題，比如相似性學(xué)習(xí)，特征學(xué)習(xí)等等也是監(jiān)督的，但是不是分類)。 再舉個例子，正如人們通過已知病例學(xué)習(xí)診斷技術(shù)那樣，計算機要通過學(xué)習(xí)才能具有識別各種事物和現(xiàn)象的能力。用來進行學(xué)習(xí)的材料就是與被識別對象屬于同類的有限數(shù)量樣本。監(jiān)督學(xué)習(xí)中在給予計算機學(xué)習(xí)樣本的同時，還告訴計算各個樣本所屬的類別。若所給的學(xué)習(xí)樣本不帶有類別信息,就是無監(jiān)督學(xué)習(xí)(淺顯點說：同樣是學(xué)習(xí)訓(xùn)練，監(jiān)督學(xué)習(xí)中，給的樣例比如是已經(jīng)標注了如

10、心臟病的，肝炎的；而無監(jiān)督學(xué)習(xí)中，就是給你一大堆的樣例，沒有標明是何種病例的)。 而在支持向量機導(dǎo)論一書給監(jiān)督學(xué)習(xí)下的定義是：當樣例是輸入/輸出對給出時，稱為監(jiān)督學(xué)習(xí)，有關(guān)輸入/輸出函數(shù)關(guān)系的樣例稱為訓(xùn)練數(shù)據(jù)。而在無監(jiān)督學(xué)習(xí)中，其數(shù)據(jù)不包含輸出值，學(xué)習(xí)的任務(wù)是理解數(shù)據(jù)產(chǎn)生的過程。第一部分、決策樹學(xué)習(xí)1.1、什么是決策樹 咱們直接切入正題。所謂決策樹，顧名思義，是一種樹，一種依托于策略抉擇而建立起來的樹。 機器學(xué)習(xí)中，決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路

11、徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。 從數(shù)據(jù)產(chǎn)生決策樹的機器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí), 通俗點說就是決策樹，說白了，這是一種依托于分類、訓(xùn)練上的預(yù)測樹，根據(jù)已知預(yù)測、歸類未來。 來理論的太過抽象，下面舉兩個淺顯易懂的例子：第一個例子 套用俗語，決策樹分類的思想類似于找對象?，F(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話： 女兒：多大年紀了？ 母親：26。 女兒：長的帥不帥？ 母親：挺帥的。 女兒：收入高不？ 母親：不算很高，中等情況。 女兒：是公務(wù)員不？ 母親：是，在稅務(wù)局上班呢。 女兒：那好，我去見見。 這個女孩的決策過程

12、就是典型的分類樹決策。相當于通過年齡、長相、收入和是否(sh fu)公務(wù)員對將男人分為兩個類別：見和不見。假設(shè)這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務(wù)員，那么這個可以(ky)用下圖表示女孩的決策邏輯： 也就是(jish)說，決策樹的簡單策略就是，好比公司招聘面試過程中篩選一個人的簡歷，如果你的條件相當好比如說某985/211重點大學(xué)博士畢業(yè)，那么二話不說，直接叫過來面試，如果非重點大學(xué)畢業(yè)，但實際項目經(jīng)驗豐富，那么也要考慮叫過來面試一下，即所謂具體情況具體分析、決策。但每一個未知的選項都是可以歸類到已有的分類類別中的。第二個例子 此例子來自Tom M.

13、Mitchell著的機器學(xué)習(xí)一書： 小王的目的是通過下周天氣預(yù)報尋找什么時候人們會打高爾夫，他了解到人們決定是否打球的原因最主要取決于天氣情況。而天氣狀況有晴，云和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風(fēng)。如此，我們便可以構(gòu)造一棵決策樹，如下（根據(jù)天氣這個分類決策這天是否合適打網(wǎng)球）： 上述(shngsh)決策樹對應(yīng)于以下表達式：（Outlook=Sunny Humidity=70）V （Outlook = Overcast）V （Outlook=Rain Wind=Weak）1.2、ID3算法(sun f)1.2.1、決策樹學(xué)習(xí)(xux)之ID3算法 ID3算法是決策樹算法的一種

14、。想了解什么是ID3算法之前，我們得先明白一個概念：奧卡姆剃刀。奧卡姆剃刀（Occams Razor, Ockhams Razor），又稱“奧坎的剃刀”，是由14世紀邏輯學(xué)家、圣方濟各會修士奧卡姆的威廉（William of Occam，約1285年至1349年）提出，他在箴言書注2卷15題說“切勿浪費較多東西，去做用較少的東西，同樣可以做好的事情。簡單點說，便是：be simple。 ID3算法（IterativeDichotomiser3迭代二叉樹3代）是一個由RossQuinlan發(fā)明的用于決策樹的算法。這個算法便是建立在上述所介紹的奧卡姆剃刀的基礎(chǔ)上：越是小型的決策樹越優(yōu)于大的決策樹（

15、be simple簡單理論）。盡管如此，該算法也不是總是生成最小的樹形結(jié)構(gòu)，而是一個啟發(fā)式算法。 OK，從信息論知識中我們知道，期望信息越小，信息增益越大，從而純度越高。ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益(很快，由下文你就會知道信息增益又是怎么一回事)最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。 所以(suy)，ID3的思想(sxing)便是：自頂向下的貪婪搜索遍歷可能的決策樹空間(kngjin)構(gòu)造決策樹(此方法是ID3算法和C4.5算法的基礎(chǔ))；從“哪一個屬性將在樹的根節(jié)點被測試”開始；使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣

16、例的能力，分類能力最好的屬性作為樹的根結(jié)點測試(如何定義或者評判一個屬性是分類能力最好的呢？這便是下文將要介紹的信息增益，or 信息增益率)。然后為根結(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓(xùn)練樣例排列到適當?shù)姆种Вㄒ簿褪钦f，樣例的該屬性值對應(yīng)的分支）之下。重復(fù)這個過程，用每個分支結(jié)點關(guān)聯(lián)的訓(xùn)練樣例來選取在該點被測試的最佳屬性。這形成了對合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。 下圖所示即是用于學(xué)習(xí)布爾函數(shù)的ID3算法概要：1.2.2、哪個屬性是最佳的分類屬性1、信息增益的度量標準：熵 上文中，我們提到：“ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益(很

17、快，由下文你就會知道信息增益又是怎么一回事)最大的屬性進行分裂?！苯酉聛?，咱們就來看看這個信息增益是個什么概念(當然，在了解信息增益之前，你必須先理解：信息增益的度量標準：熵)。 上述(shngsh)的ID3算法的核心問題是選取在樹的每個結(jié)點(ji din)要測試的屬性。我們希望選擇的是最有利于分類實例的屬性，信息增益(Information Gain)是用來(yn li)衡量給定的屬性區(qū)分訓(xùn)練樣例的能力，而ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性。 為了精確地定義信息增益，我們先定義信息論中廣泛使用的一個度量標準，稱為熵（entropy），它刻畫了任意樣例集的純度（puri

18、ty）。給定包含關(guān)于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為： 上述公式中，p+代表正樣例，比如在本文開頭第二個例子中p+則意味著去打羽毛球，而p-則代表反樣例，不去打球(在有關(guān)熵的所有計算中我們定義0log0為0)。 如果寫代碼實現(xiàn)熵的計算，則如下所示：cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/deta

19、ils/7577684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?/根據(jù)具體屬性和值來計算熵doubleComputeEntropy(vectorvectorremain_state,stringattribute,stringvalue,boolifparent)vectorcount(2,0);unsignedinti,j;booldone_flag=false;/哨兵值for(j=1;jMAXLEN;j+)if(done_flag)break;if(!attribute_pare(attribute)fo

20、r(i=1;iremain_state.size();i+)if(!ifparent&!remain_pare(value)|ifparent)/ifparent記錄是否算父節(jié)點if(!remain_stateiMAXLEN-pare(yes)count0+;elsecount1+;done_flag=true;if(count0=0|count1=0)return0;/全部是正實例或者負實例/具體(jt)計算熵根據(jù)(gnj)+count0,-count1,log2為底通過換底公式(gngsh)換成自然數(shù)底數(shù)doublesum=count0+count1;doubleentropy=-coun

21、t0/sum*log(count0/sum)/log(2.0)-count1/sum*log(count1/sum)/log(2.0);returnentropy;/根據(jù)具體屬性和值來計算熵 double ComputeEntropy(vector vector remain_state, string attribute, string value,bool ifparent) vector count (2,0); unsigned int i,j; bool done_flag = false;/哨兵值 for(j = 1; j MAXLEN; j+) if(done_flag) bre

22、ak; if(!attribute_pare(attribute) for(i = 1; i wind增益的0.048。說白了，就是在星期六上午是否適合打網(wǎng)球的問題訣策中，采取humidity較wind作為分類屬性更佳，決策樹由此而來。cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print pr

23、int HYPERLINK /v_july_v/article/details/7577684 o ? ?/計算信息(xnx)增益，DFS構(gòu)建(u jin)決策樹/current_node為當前(dngqin)的節(jié)點/remain_state為剩余待分類的樣例/remian_attribute為剩余還沒有考慮的屬性/返回根結(jié)點指針Node*BulidDecisionTreeDFS(Node*p,vectorvectorremain_state,vectorremain_attribute)/if(remain_state.size()0)/printv(remain_state);/if(p=

24、NULL)p=newNode();/先看搜索到樹葉的情況if(AllTheSameLabel(remain_state,yes)p-attribute=yes;returnp;if(AllTheSameLabel(remain_state,no)p-attribute=no;returnp;if(remain_attribute.size()=0)/所有的屬性均已經(jīng)考慮完了,還沒有分盡stringlabel=MostCommonLabel(remain_state);p-attribute=label;returnp;doublemax_gain=0,temp_gain;vector:iter

25、atormax_it;vector:iteratorit1;for(it1=remain_attribute.begin();it1max_gain)max_gain=temp_gain;max_it=it1;/下面根據(jù)max_it指向的屬性來劃分當前樣例，更新樣例集和屬性集vectornew_attribute;vectorvectornew_state;for(vector:iteratorit2=remain_attribute.begin();it2attribute=*max_it;vectorvalues=map_attribute_values*max_it;intattribu

26、e_num=FindAttriNumByName(*max_it);new_state.push_back(attribute_row);for(vector:iteratorit3=values.begin();it3values.end();it3+)for(unsignedinti=1;iarrived_value=*it3;if(new_state.size()=0)/表示當前(dngqin)沒有這個分支的樣例，當前的new_node為葉子(y zi)節(jié)點new_node-attribute=MostCommonLabel(remain_state);elseBulidDecision

27、TreeDFS(new_node,new_state,new_attribute);/遞歸函數(shù)返回時即回溯時需要1將新結(jié)點加入父節(jié)點孩子容器2清除new_state容器p-childs.push_back(new_node);new_state.erase(new_state.begin()+1,new_state.end();/注意先清空new_state中的前一個取值的樣例，準備遍歷下一個取值樣例returnp;/計算信息增益，DFS構(gòu)建決策樹 /current_node為當前的節(jié)點 /remain_state為剩余待分類的樣例 /remian_attribute為剩余還沒有考慮的屬性 /

28、返回根結(jié)點指針 Node * BulidDecisionTreeDFS(Node * p, vector vector remain_state, vector remain_attribute) /if(remain_state.size() 0) /printv(remain_state); / if (p = NULL) p = new Node(); /先看搜索到樹葉的情況 if (AllTheSameLabel(remain_state, yes) p-attribute = yes; return p; if (AllTheSameLabel(remain_state, no) p

29、-attribute = no; return p; if(remain_attribute.size() = 0)/所有的屬性均已經(jīng)考慮完了,還沒有分盡 string label = MostCommonLabel(remain_state); p-attribute = label; return p; double max_gain = 0, temp_gain; vector :iterator max_it; vector :iterator it1; for(it1 = remain_attribute.begin(); it1 max_gain) max_gain = temp_

30、gain; max_it = it1; /下面根據(jù)max_it指向的屬性來劃分當前樣例，更新樣例集和屬性集 vector new_attribute; vector vector new_state; for(vector :iterator it2 = remain_attribute.begin(); it2 attribute = *max_it; vector values = map_attribute_values*max_it; int attribue_num = FindAttriNumByName(*max_it); new_state.push_back(attribut

31、e_row); for(vector :iterator it3 = values.begin(); it3 values.end(); it3+) for(unsigned int i = 1; i arrived_value = *it3; if(new_state.size() = 0)/表示當前沒有這個分支的樣例，當前的new_node為葉子節(jié)點 new_node-attribute = MostCommonLabel(remain_state); else BulidDecisionTreeDFS(new_node, new_state, new_attribute); /遞歸函數(shù)返

32、回時即回溯時需要1 將新結(jié)點加入父節(jié)點孩子容器 2清除new_state容器 p-childs.push_back(new_node); new_state.erase(new_state.begin()+1,new_state.end();/注意先清空new_state中的前一個取值的樣例，準備遍歷下一個取值樣例 return p; 1.2.3、ID3算法決策樹的形成 OK，下圖為ID3算法第一步后形成的部分決策樹。這樣綜合起來看，就容易理解多了。1、overcast樣例必為正，所以為葉子結(jié)點，總為yes；2、ID3無回溯，局部最優(yōu)，而非全局最優(yōu)，還有另一種樹后修剪決策樹。下圖是ID3算法第

33、一步后形成的部分決策樹： 如上圖，訓(xùn)練樣例被排列(pili)到對應(yīng)的分支結(jié)點。分支Overcast的所有樣例都是正例，所以成為目標(mbio)分類為Yes的葉結(jié)點。另兩個結(jié)點將被進一步展開，方法是按照(nzho)新的樣例子集選取信息增益最高的屬性。1.3、C4.5算法1.3.1、ID3算法的改進：C4.5算法 C4.5，是機器學(xué)習(xí)算法中的另一個分類決策樹算法，它是決策樹(決策樹也就是做決策的節(jié)點間的組織方式像一棵樹，其實是一個倒樹)核心算法，也是上文1.2節(jié)所介紹的ID3的改進算法，所以基本上了解了一半決策樹構(gòu)造方法就能構(gòu)造它。 決策樹構(gòu)造方法其實就是每次選擇一個好的特征以及分裂點作為當前節(jié)點

34、的分類條件。 既然說C4.5算法是ID3的改進算法，那么C4.5相比于ID3改進的地方有哪些呢？：用信息增益率來選擇屬性。ID3選擇屬性用的是子樹的信息增益，這里可以用很多方法來定義信息，ID3使用的是熵(entropy，熵是一種不純度度量準則),也就是熵的變化值，而C4.5用的是信息增益率。對，區(qū)別就在于一個是信息增益，一個是信息增益率。在樹構(gòu)造過程中進行剪枝，在構(gòu)造決策樹的時候，那些掛著幾個元素的節(jié)點，不考慮最好，不然容易導(dǎo)致overfitting。對非離散數(shù)據(jù)(shj)也能處理。能夠?qū)Σ煌暾?wnzhng)數(shù)據(jù)進行處理 針對上述第一點，解釋下：一般來說率就是用來取平衡用的，就像方差起的作

35、用差不多，比如有兩個跑步的人，一個(y )起點是10m/s的人、其10s后為20m/s；另一個人起速是1m/s、其1s后為2m/s。如果緊緊算差值那么兩個差距就很大了，如果使用速度增加率(加速度，即都是為1m/s2)來衡量，2個人就是一樣的加速度。因此，C4.5克服了ID3用信息增益選擇屬性時偏向選擇取值多的屬性的不足。C4.5算法之信息增益率 OK，既然上文中提到C4.5用的是信息增益率，那增益率的具體是如何定義的呢？： 是的，在這里，C4.5算法不再是通過信息增益來選擇決策屬性。一個可以選擇的度量標準是增益比率gainratio（Quinlan1986）。增益比率度量是用前面的增益度量Ga

36、in(S，A)和分裂信息度量SplitInformation(S，A)來共同定義的，如下所示： 其中，分裂信息度量被定義為(分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻)： 其中S1到Sc是c個值的屬性A分割S而形成的c個樣例子集。注意分裂信息實際上就是S關(guān)于屬性A的各值的熵。這與我們前面對熵的使用不同，在那里我們只考慮S關(guān)于學(xué)習(xí)到的樹要預(yù)測的目標屬性的值的熵。 請注意，分裂信息項阻礙選擇值為均勻分布的屬性。例如，考慮一個含有n個樣例的集合被屬性A徹底分割（譯注：分成n組，即一個樣例一組）。這時分裂信息的值為log2n。相反，一個布爾屬性B分割同樣的n個實例，如果恰好平分兩半，那么分裂信息是1。如

37、果屬性A和B產(chǎn)生同樣的信息增益，那么根據(jù)增益比率度量，明顯B會得分更高。 使用增益比率代替增益來選擇屬性產(chǎn)生的一個實際問題是，當某個Si接近S（|Si|S|）時分母可能為0或非常小。如果某個屬性對于S的所有樣例有幾乎同樣的值，這時要么導(dǎo)致增益比率未定義，要么是增益比率非常大。為了避免選擇這種屬性，我們可以采用這樣一些啟發(fā)式規(guī)則，比如先計算每個屬性的增益，然后僅對那些增益高過平均值的屬性應(yīng)用增益比率測試（Quinlan1986）。 除了信息(xnx)增益，LopezdeMantaras（1991）介紹了另一種直接針對上述問題而設(shè)計的度量，它是基于(jy)距離的（distance-based）。這

38、個(zh ge)度量標準基于所定義的一個數(shù)據(jù)劃分間的距離尺度。具體更多請參看：Tom M.Mitchhell所著的機器學(xué)習(xí)之3.7.3節(jié)。1.3.2、C4.5算法構(gòu)造決策樹的過程cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print print HYPERLINK /v_july_v/artic

39、le/details/7577684 o ? ?FunctionC4.5(R:包含連續(xù)屬性的無類別屬性集合,C:類別屬性,S:訓(xùn)練集)/*返回一棵決策樹*/BeginIfS為空,返回一個值為Failure的單個節(jié)點;IfS是由相同類別屬性值的記錄組成,返回一個帶有該值的單個節(jié)點;IfR為空,則返回一個單節(jié)點,其值為在S的記錄中找出的頻率最高的類別屬性值;注意未出現(xiàn)錯誤則意味著是不適合分類的記錄；For所有的屬性R(Ri)DoIf屬性Ri為連續(xù)屬性，則Begin將Ri的最小值賦給A1：將Rm的最大值賦給Am；/*m值手工設(shè)置*/ForjFrom2Tom-1DoAj=A1+j*(A1Am)/m;將

40、Ri點的基于Aj的最大信息增益屬性(Ri,S)賦給A；End；將R中屬性之間具有最大信息增益的屬性(D,S)賦給D;將屬性D的值賦給dj/j=1,2.m；將分別由對應(yīng)于D的值為dj的記錄組成的S的子集賦給sj/j=1,2.m;返回一棵樹，其根標記為D;樹枝標記為d1,d2.dm;再分別構(gòu)造以下樹:C4.5(R-D,C,S1),C4.5(R-D,C,S2).C4.5(R-D,C,Sm);EndC4.5Function C4.5(R:包含連續(xù)屬性的無類別屬性集合,C:類別屬性,S:訓(xùn)練集)/*返回一棵決策樹*/Begin If S為空,返回一個值為Failure的單個節(jié)點; If S是由相同類別屬

41、性值的記錄組成, 返回一個帶有該值的單個節(jié)點; If R為空,則返回一個單節(jié)點,其值為在S的記錄中找出的頻率最高的類別屬性值; 注意未出現(xiàn)錯誤則意味著是不適合分類的記錄； For 所有的屬性R(Ri) Do If 屬性Ri為連續(xù)屬性，則 Begin 將Ri的最小值賦給A1： 將Rm的最大值賦給Am；/*m值手工設(shè)置*/ For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m; 將Ri點的基于Aj的最大信息增益屬性(Ri,S)賦給A； End； 將R中屬性之間具有最大信息增益的屬性(D,S)賦給D; 將屬性D的值賦給dj/j=1,2.m； 將分別由對應(yīng)于D的值為dj的記錄

42、組成的S的子集賦給sj/j=1,2.m; 返回一棵樹，其根標記為D;樹枝標記為d1,d2.dm; 再分別構(gòu)造以下樹: C4.5(R-D,C,S1),C4.5(R-D,C,S2).C4.5(R-D,C,Sm);End C4.51.3.3、C4.5算法實現(xiàn)中的幾個關(guān)鍵步驟 在上文中，我們已經(jīng)知道了決策樹學(xué)習(xí)C4.5算法中4個重要概念的表達，如下： 接下來，咱們寫下代碼(di m)實現(xiàn)， 1、信息熵cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/de

43、tails/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?doubleC4_5:entropy(int*attrClassCount,intclassNum,intallNum)doubleiEntropy=0.0;for(inti=0;iclassNum;i+)doubletemp=(double)attrClassCounti)/allNum;if(temp!=0.0)iEntropy

44、-=temp*(log(temp)/log(2.0);returniEntropy;double C4_5:entropy(int *attrClassCount, int classNum, int allNum)double iEntropy = 0.0;for(int i = 0; i classNum; i+)double temp = (double)attrClassCounti) / allNum;if(temp != 0.0)iEntropy -= temp * (log(temp) / log(2.0);return iEntropy; 2、信息(xnx)增益率cpp HYP

45、ERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?doubleC4_5:gainRatio(intclassNum,vectorattriCount,doublepEntropy)int*att

46、riNum=newintattriCount.size();intallNum=0;for(inti=0;i(int)attriCount.size();i+)attriNumi=0;for(intj=0;jclassNum;j+)attriNumi+=attriCountij;allNum+=attriCountij;doublegain=0.0;doublesplitInfo=0.0;for(inti=0;i(int)attriCount.size();i+)gain-=(double)attriNumi)/allNum*entropy(attriCounti,classNum,attri

47、Numi);splitInfo-=(double)attriNumi)/allNum*(log(double)attriNumi)/allNum)/log(2.0);gain+=pEntropy;deleteattriNum;return(gain/splitInfo);double C4_5:gainRatio(int classNum, vector attriCount, double pEntropy)int* attriNum = new intattriCount.size();int allNum = 0;for(int i = 0; i (int)attriCount.size

48、(); i+)attriNumi = 0;for(int j = 0; j classNum; j+)attriNumi += attriCountij;allNum += attriCountij;double gain = 0.0;double splitInfo = 0.0;for(int i = 0; i (int)attriCount.size(); i+)gain -= (double)attriNumi) / allNum * entropy(attriCounti, classNum, attriNumi);splitInfo -= (double)attriNumi) / a

49、llNum * (log(double)attriNumi)/allNum) / log(2.0);gain += pEntropy;delete attriNum; return (gain / splitInfo); 3、選取最大增益(zngy)屬性作為分類條件cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/757

50、7684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?intC4_5:chooseAttribute(vectorattrIndex,vector*sampleCount)intbestIndex=0;doublemaxGainRatio=0.0;intclassNum=(int)(decisionsattrIndex(int)attrIndex.size()-1).size();/numberofclass/computertheclassentropyint*temp=newintclassNum;intal

51、lNum=0;for(inti=0;iclassNum;i+)tempi=sampleCount(int)attrIndex.size()-1ii;allNum+=tempi;doublepEntropy=entropy(temp,classNum,allNum);deletetemp;/computergainratioforeveryattributefor(inti=0;imaxGainRatio)bestIndex=i;maxGainRatio=gainR;returnbestIndex;int C4_5:chooseAttribute(vector attrIndex, vector

52、* sampleCount)int bestIndex = 0;double maxGainRatio = 0.0;int classNum = (int)(decisionsattrIndex(int)attrIndex.size()-1).size();/number of class/computer the class entropyint* temp = new intclassNum;int allNum = 0;for(int i = 0; i classNum; i+)tempi = sampleCount(int)attrIndex.size()-1ii;allNum +=

53、tempi;double pEntropy = entropy(temp, classNum, allNum);delete temp;/computer gain ratio for every attributefor(int i = 0; i maxGainRatio)bestIndex = i;maxGainRatio = gainR;return bestIndex; 4、還有一系列建樹，打印(d yn)樹的步驟，此處略過。1.4、讀者(dzh)點評formWind：決策樹使用于特征(tzhng)取值離散的情況，連續(xù)的特征一般也要處理成離散的(而很多文章沒有表達出決策樹的關(guān)鍵(gun

54、jin)特征or概念)。實際應(yīng)用中，決策樹overfitting比較的嚴重，一般要做boosting。分類器的性能上不去，很主要的原因在于特征的鑒別性不足，而不是分類器的好壞，好的特征才有好的分類效果，分類器只是弱相關(guān)。那如何提高特征的鑒別性呢？一是設(shè)計特征時盡量引入domainknowledge，二是對提取出來的特征做選擇、變換和再學(xué)習(xí)，這一點是機器學(xué)習(xí)算法不管的部分(我說的這些不是針對決策樹的，因此不能說是決策樹的特點，只是一些機器學(xué)習(xí)算法在應(yīng)用過程中的經(jīng)驗體會)。第二部分、貝葉斯分類 說實話，友人劉未鵬有一篇講的貝葉斯的文章： HYPERLINK /2008/09/21/the-magi

55、cal-bayesian-method/ t _blank 數(shù)學(xué)之美番外篇：平凡而又神奇的貝葉斯方法，已經(jīng)把貝葉斯講的很清晰透徹了，我再講也是如李白看到崔顥在黃鶴樓上所提的：登黃鶴樓昔人已乘黃鶴去，此地空余黃鶴樓；黃鶴一去不復(fù)返，白云千載空悠悠。 后便大為折服，已無什興致再提了(偶現(xiàn)在就是這感覺)，然文章還得繼續(xù)寫。So，本文第二部分之大部分基本整理自未鵬兄之手(做了部分改動)，若有任何不妥之處，還望讀者和未鵬兄海涵，謝謝。2.1、什么是貝葉斯分類 據(jù)維基百科上的介紹，貝葉斯定理是關(guān)于隨機事件A和B的條件概率和邊緣概率的一則定理。 如上所示，其中P(A|B)是在B發(fā)生的情況下A發(fā)生的可能性。在

56、貝葉斯定理中，每個名詞都有約定俗成的名稱：P(A)是A的先驗概率或邊緣概率。之所以稱為先驗是因為它不考慮任何B方面的因素。P(A|B)是已知B發(fā)生后A的條件概率（直白來講，就是先有B而后=才有A），也由于得自B的取值而被稱作A的后驗概率。P(B|A)是已知A發(fā)生后B的條件概率（直白來講，就是先有A而后=才有B），也由于得自A的取值而被稱作B的后驗概率。P(B)是B的先驗概率或邊緣概率，也作標準化常量（normalizedconstant）。 按這些(zhxi)術(shù)語，Bayes定理可表述(bio sh)為：后驗概率=(相似(xin s)度*先驗概率)/標準化常量，也就是說，后驗概率與先驗概率和相

57、似度的乘積成正比。另外，比例P(B|A)/P(B)也有時被稱作標準相似度（standardisedlikelihood），Bayes定理可表述為：后驗概率=標準相似度*先驗概率。2.2貝葉斯公式如何而來 貝葉斯公式是怎么來的？下面再舉wikipedia 上的一個例子：一所學(xué)校里面有 60% 的男生，40% 的女生。男生總是穿長褲，女生則一半穿長褲一半穿裙子。有了這些信息之后我們可以容易地計算“隨機選取一個學(xué)生，他（她）穿長褲的概率和穿裙子的概率是多大”，這個就是前面說的“正向概率”的計算。然而，假設(shè)你走在校園中，迎面走來一個穿長褲的學(xué)生（很不幸的是你高度近似，你只看得見他（她）穿的是否長褲，而

58、無法確定他（她）的性別），你能夠推斷出他（她）是男生的概率是多大嗎？ 一些認知科學(xué)的研究表明（決策與判斷以及 HYPERLINK /subject/3199621/ t _blank Rationality for Mortals第12章：小孩也可以解決貝葉斯問題），我們對形式化的貝葉斯問題不擅長，但對于以頻率形式呈現(xiàn)的等價問題卻很擅長。在這里，我們不妨把問題重新敘述成：你在校園里面 HYPERLINK /wiki/Random_walk t _blank 隨機游走，遇到了 N 個穿長褲的人（仍然假設(shè)你無法直接觀察到他們的性別），問這 N 個人里面有多少個女生多少個男生。 你說，這還不簡單：算

59、出學(xué)校里面有多少穿長褲的，然后在這些人里面再算出有多少女生，不就行了？ 我們來算一算：假設(shè)學(xué)校里面人的總數(shù)是 U 個。60% 的男生都穿長褲，于是我們得到了 U * P(Boy) * P(Pants|Boy) 個穿長褲的（男生）（其中 P(Boy) 是男生的概率 = 60%，這里可以簡單的理解為男生的比例；P(Pants|Boy) 是條件概率，即在 Boy 這個條件下穿長褲的概率是多大，這里是 100% ，因為所有男生都穿長褲）。40% 的女生里面又有一半（50%）是穿長褲的，于是我們又得到了 U * P(Girl) * P(Pants|Girl) 個穿長褲的（女生）。加起來一共是 U * P

60、(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 個穿長褲的，其中有 U * P(Girl) * P(Pants|Girl) 個女生。兩者一比就是你要求的答案。 下面我們把這個答案形式化一下：我們要求的是 P(Girl|Pants) （穿長褲的人里面有多少女生），我們計算的結(jié)果是 U * P(Girl) * P(Pants|Girl) / U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 。容易發(fā)現(xiàn)這里校園內(nèi)人的總數(shù)是無關(guān)的，兩邊同時消去U，于是得到P(Girl|Pants) =