从决策树学习谈到贝叶斯分类算法
?? 從決策樹學(xué)習(xí)談到貝葉斯分類算法
引言
? ? 最近在面試中，除了基礎(chǔ) &? 算法 & 項目之外，經(jīng)常被問到或被要求介紹和描述下自己所知道的幾種分類或聚類算法，而我向來恨對一個東西只知其皮毛而不得深入，故寫一個有關(guān)聚類 & 分類算法的系列文章以作為自己備試之用(盡管貌似已無多大必要，但還是覺得應(yīng)該寫下以備將來常?；仡櫵伎?。行文雜亂，但僥幸若能對讀者也起到一定幫助，則幸甚至哉。
? ? 本分類 & 聚類算法系列借鑒和參考了兩本書，一本是Tom M.Mitchhell所著的機器學(xué)習(xí)，一本是數(shù)據(jù)挖掘?qū)д?#xff0c;這兩本書皆分別是機器學(xué)習(xí) & 數(shù)據(jù)挖掘領(lǐng)域的開山?or?杠鼎之作，讀者有繼續(xù)深入下去的興趣的話，不妨在閱讀本文之后，課后細(xì)細(xì)研讀這兩本書。除此之外，還參考了網(wǎng)上不少牛人的作品(文末會注明參考鏈接)，在此，皆一一表示感謝。
? ? 本分類 & 聚類算法系列暫稱之為Top 10 Algorithms in Data Mining，其中，各篇分別有以下具體內(nèi)容：
?
?
? ? OK，全系列任何一篇文章若有任何錯誤，漏洞，或不妥之處，還請讀者們一定要隨時不吝賜教 & 指正，謝謝各位。
?
第一部分、決策樹學(xué)習(xí)
1.1、什么是決策樹
? ? 咱們直接切入正題。所謂決策樹，顧名思義，是一種樹，一種依托于策略抉擇而建立起來的樹。
? ? 機器學(xué)習(xí)中，決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。
? ? 從數(shù)據(jù)產(chǎn)生決策樹的機器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí), 通俗點說就是決策樹。
? ? 來理論的太過抽象，下面舉兩個淺顯易懂的例子：
第一個例子
? ? 套用俗語，決策樹分類的思想類似于找對象?，F(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：
? ? ? 女兒：多大年紀(jì)了？
? ? ? 母親：26。
? ? ? 女兒：長的帥不帥？
? ? ? 母親：挺帥的。
? ? ? 女兒：收入高不？
? ? ? 母親：不算很高，中等情況。
? ? ? 女兒：是公務(wù)員不？
? ? ? 母親：是，在稅務(wù)局上班呢。
? ? ? 女兒：那好，我去見見。
? ? ? 這個女孩的決策過程就是典型的分類樹決策。相當(dāng)于通過年齡、長相、收入和是否公務(wù)員對將男人分為兩個類別：見和不見。假設(shè)這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務(wù)員，那么這個可以用下圖表示女孩的決策邏輯：
?
?
? ? 也就是說，決策樹的簡單策略就是，好比公司招聘面試過程中篩選一個人的簡歷，如果你的條件相當(dāng)好比如說某985/211重點大學(xué)博士畢業(yè)，那么二話不說，直接叫過來面試，如果非重點大學(xué)畢業(yè)，但實際項目經(jīng)驗豐富，那么也要考慮叫過來面試一下，即所謂具體情況具體分析、決策。
第二個例子
? ? 此例子來自Tom M.Mitchell著的機器學(xué)習(xí)一書：
? ? 小王的目的是通過下周天氣預(yù)報尋找什么時候人們會打高爾夫，他了解到人們決定是否打球的原因最主要取決于天氣情況。而天氣狀況有晴，云和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風(fēng)。如此，我們便可以構(gòu)造一棵決策樹，如下（根據(jù)天氣這個分類決策這天是否合適打網(wǎng)球）：
? ? 上述決策樹對應(yīng)于以下表達(dá)式：
（Outlook=Sunny ^Humidity<=70）V （Outlook = Overcast）V （Outlook=Rain ^ Wind=Weak）
1.2、ID3算法
1.2.1、決策樹學(xué)習(xí)之ID3算法
? ? ID3算法是決策樹算法的一種。想了解什么是ID3算法之前，我們得先明白一個概念：奧卡姆剃刀。
?
- 奧卡姆剃刀（Occam's Razor, Ockham's Razor），又稱“奧坎的剃刀”，是由14世紀(jì)邏輯學(xué)家、圣方濟(jì)各會修士奧卡姆的威廉（William of Occam，約1285年至1349年）提出，他在《箴言書注》2卷15題說“切勿浪費較多東西，去做‘用較少的東西，同樣可以做好的事情’。簡單點說，便是：be simple。
?
?
ID3算法（Iterative?Dichotomiser?3?迭代二叉樹3代）是一個由Ross?Quinlan發(fā)明的用于決策樹的算法。這個算法便是建立在上述所介紹的奧卡姆剃刀的基礎(chǔ)上：越是小型的決策樹越優(yōu)于大的決策樹（be simple簡單理論）。盡管如此，該算法也不是總是生成最小的樹形結(jié)構(gòu)，而是一個啟發(fā)式算法。? ? OK，從信息論知識中我們知道，期望信息越小，信息增益越大，從而純度越高。ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益(很快，由下文你就會知道信息增益又是怎么一回事)最大的屬性進(jìn)行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。
? ? ?所以，ID3的思想便是：
這形成了對合格決策樹的貪婪搜索，也就是算法從不回溯重新考慮以前的選擇。
?
? ? 下圖所示即是用于學(xué)習(xí)布爾函數(shù)的ID3算法概要：
1.2.2、哪個屬性是最佳的分類屬性
1、信息增益的度量標(biāo)準(zhǔn)：熵上文中，我們提到：“ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益(很快，由下文你就會知道信息增益又是怎么一回事)最大的屬性進(jìn)行分裂?！苯酉聛?#xff0c;咱們就來看看這個信息增益是個什么概念(當(dāng)然，在了解信息增益之前，你必須先理解：信息增益的度量標(biāo)準(zhǔn)：熵)。 上述的ID3算法的核心問題是選取在樹的每個結(jié)點要測試的屬性。我們希望選擇的是最有利于分類實例的屬性，信息增益(Information Gain)是用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力，而ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性。
? ? 為了精確地定義信息增益，我們先定義信息論中廣泛使用的一個度量標(biāo)準(zhǔn)，稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為：
?
?
?
? ? 上述公式中，p+代表正樣例，比如在本文開頭第二個例子中p+則意味著去打羽毛球，而p-則代表反樣例，不去打球(在有關(guān)熵的所有計算中我們定義0log0為0)。
? ? 如果寫代碼實現(xiàn)熵的計算，則如下所示：
?
?
? ? 舉例來說，假設(shè)S是一個關(guān)于布爾概念的有14個樣例的集合，它包括9個正例和5個反例（我們采用記號[9+，5-]來概括這樣的數(shù)據(jù)樣例），那么S相對于這個布爾樣例的熵為：
Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。
?
So，根據(jù)上述這個公式，我們可以得到：S的所有成員屬于同一類，Entropy(S)=0；?S的正反樣例數(shù)量相等，Entropy(S)=1；S的正反樣例數(shù)量不等，熵介于0，1之間，如下圖所示：
?
? ???Pi為子集合中不同性(而二元分類即正樣例和負(fù)樣例)的樣例的比例。
2、信息增益度量期望的熵降低
信息增益Gain(S,A)定義
? ? 已經(jīng)有了熵作為衡量訓(xùn)練樣例集合純度的標(biāo)準(zhǔn)，現(xiàn)在可以定義屬性分類訓(xùn)練數(shù)據(jù)的效力的度量標(biāo)準(zhǔn)。這個標(biāo)準(zhǔn)被稱為“信息增益（information?gain）”。簡單的說，一個屬性的信息增益就是由于使用這個屬性分割樣例而導(dǎo)致的期望熵降低(或者說，樣本按照某屬性劃分時造成熵減少的期望)。更精確地講，一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：
?
?
?
? ? 其中?Values(A)是屬性A所有可能值的集合，是S中屬性A的值為v的子集。換句話來講，Gain(S,A)是由于給定屬性A的值而得到的關(guān)于目標(biāo)函數(shù)值的信息。當(dāng)對S的一個任意成員的目標(biāo)值編碼時，Gain(S,A)的值是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)。
? ? 接下來，有必要提醒讀者一下：關(guān)于下面這兩個概念?or?公式，
?
第一個Entropy(S)是熵定義，第二個則是信息增益Gain(S,A)的定義，而Gain(S,A)由第一個Entropy(S)計算出，記住了。?
? ? 下面，舉個例子，假定S是一套有關(guān)天氣的訓(xùn)練樣例，描述它的屬性包括可能是具有Weak和Strong兩個值的Wind。像前面一樣，假定S包含14個樣例，[9+，5-]。在這14個樣例中，假定正例中的6個和反例中的2個有Wind?=Weak，其他的有Wind=Strong。由于按照屬性Wind分類14個樣例得到的信息增益可以計算如下。
?
? ? 運用在本文開頭舉得第二個根據(jù)天氣情況是否決定打羽毛球的例子上，得到的最佳分類屬性如下圖所示：
? ???在上圖中，計算了兩個不同屬性：濕度(humidity)和風(fēng)力(wind)的信息增益，最終humidity這種分類的信息增益0.151>wind增益的0.048。說白了，就是在星期六上午是否適合打網(wǎng)球的問題訣策中，采取humidity較wind作為分類屬性更佳，決策樹由此而來。
?
?
1.2.3、ID3算法決策樹的形成
? ? OK，下圖為ID3算法第一步后形成的部分決策樹。這樣綜合起來看，就容易理解多了。1、overcast樣例必為正，所以為葉子結(jié)點，總為yes；2、ID3無回溯，局部最優(yōu)，而非全局最優(yōu)，還有另一種樹后修剪決策樹。下圖是ID3算法第一步后形成的部分決策樹：
? ? 如上圖，訓(xùn)練樣例被排列到對應(yīng)的分支結(jié)點。分支Overcast的所有樣例都是正例，所以成為目標(biāo)分類為Yes的葉結(jié)點。另兩個結(jié)點將被進(jìn)一步展開，方法是按照新的樣例子集選取信息增益最高的屬性。
1.3、C4.5算法
1.3.1、ID3算法的改進(jìn)：C4.5算法? ? C4.5，是機器學(xué)習(xí)算法中的另一個分類決策樹算法，它是決策樹(決策樹也就是做決策的節(jié)點間的組織方式像一棵樹，其實是一個倒樹)核心算法，也是上文1.2節(jié)所介紹的ID3的改進(jìn)算法，所以基本上了解了一半決策樹構(gòu)造方法就能構(gòu)造它。
? ? 決策樹構(gòu)造方法其實就是每次選擇一個好的特征以及分裂點作為當(dāng)前節(jié)點的分類條件。
? ? 既然說C4.5算法是ID3的改進(jìn)算法，那么C4.5相比于ID3改進(jìn)的地方有哪些呢？：
?
?
? ? 針對上述第一點，解釋下：一般來說率就是用來取平衡用的，就像方差起的作用差不多，比如有兩個跑步的人，一個起點是10m/s的人、其10s后為20m/s；另一個人起速是1m/s、其1s后為2m/s。如果緊緊算差值那么兩個差距就很大了，如果使用速度增加率(加速度，即都是為1m/s^2)來衡量，2個人就是一樣的加速度。因此，C4.5克服了ID3用信息增益選擇屬性時偏向選擇取值多的屬性的不足。
C4.5算法之信息增益率
? ? OK，既然上文中提到C4.5用的是信息增益率，那增益率的具體是如何定義的呢？：
? ? 是的，在這里，C4.5算法不再是通過信息增益來選擇決策屬性。一個可以選擇的度量標(biāo)準(zhǔn)是增益比率gain?ratio（Quinlan?1986）。增益比率度量是用前面的增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)來共同定義的，如下所示：
? ? 其中，分裂信息度量被定義為(分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻)：
???
? ? 其中S1到Sc是c個值的屬性A分割S而形成的c個樣例子集。注意分裂信息實際上就是S關(guān)于屬性A的各值的熵。這與我們前面對熵的使用不同，在那里我們只考慮S關(guān)于學(xué)習(xí)到的樹要預(yù)測的目標(biāo)屬性的值的熵。
? ??請注意，分裂信息項阻礙選擇值為均勻分布的屬性。例如，考慮一個含有n個樣例的集合被屬性A徹底分割（譯注：分成n組，即一個樣例一組）。這時分裂信息的值為log2n。相反，一個布爾屬性B分割同樣的n個實例，如果恰好平分兩半，那么分裂信息是1。如果屬性A和B產(chǎn)生同樣的信息增益，那么根據(jù)增益比率度量，明顯B會得分更高。
? ??使用增益比率代替增益來選擇屬性產(chǎn)生的一個實際問題是，當(dāng)某個Si接近S（|Si|?|S|）時分母可能為0或非常小。如果某個屬性對于S的所有樣例有幾乎同樣的值，這時要么導(dǎo)致增益比率未定義，要么是增益比率非常大。為了避免選擇這種屬性，我們可以采用這樣一些啟發(fā)式規(guī)則，比如先計算每個屬性的增益，然后僅對那些增益高過平均值的屬性應(yīng)用增益比率測試（Quinlan?1986）。
? ? 除了信息增益，Lopez?de?Mantaras（1991）介紹了另一種直接針對上述問題而設(shè)計的度量，它是基于距離的（distance-based）。這個度量標(biāo)準(zhǔn)基于所定義的一個數(shù)據(jù)劃分間的距離尺度。具體更多請參看：Tom M.Mitchhell所著的機器學(xué)習(xí)之3.7.3節(jié)。
1.3.2、C4.5算法構(gòu)造決策樹的過程
?
1.3.3、C4.5算法實現(xiàn)中的幾個關(guān)鍵步驟
? ? 在上文中，我們已經(jīng)知道了決策樹學(xué)習(xí)C4.5算法中4個重要概念的表達(dá)，如下：
?
接下來，咱們寫下代碼實現(xiàn)， ??? 1、信息熵1.4、決策樹歸納的特點
第二部分、貝葉斯分類
說實話，友人劉未鵬有一篇講的貝葉斯的文章：數(shù)學(xué)之美番外篇：平凡而又神奇的貝葉斯方法，已經(jīng)把貝葉斯講的很清晰透徹了，我再講也是如李白看到崔顥在黃鶴樓上所提的：登黃鶴樓 昔人已乘黃鶴去，此地空余黃鶴樓； 黃鶴一去不復(fù)返，白云千載空悠悠。? ? 后便大為折服，已無什興致再提了，偶現(xiàn)在就是這感覺。然文章還得繼續(xù)寫，那就權(quán)當(dāng)是對它的一個總結(jié)或整理吧，有任何不妥之處，還望讀者和未鵬兄海涵，謝謝。
2.1、什么是貝葉斯分類
?
? ?貝葉斯定理：已知某條件概率，如何得到兩個事件交換后的概率，也就是在已知P(A|B)的情況下如何求得P(B|A)。這里先解釋什么是條件概率：
??????表示事件B已經(jīng)發(fā)生的前提下，事件A發(fā)生的概率，叫做事件B發(fā)生下事件A的條件概率。其基本求解公式為：。
????? 貝葉斯定理之所以有用，是因為我們在生活中經(jīng)常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們更關(guān)心P(B|A)，貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。
????? 下面不加證明地直接給出貝葉斯定理（公式被網(wǎng)友指出有問題，待后續(xù)驗證改正）：
? ? ??
?
? ???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、拼寫糾正
??? 經(jīng)典著作《人工智能：現(xiàn)代方法》的作者之一 Peter Norvig 曾經(jīng)寫過一篇介紹如何寫一個拼寫檢查/糾正器的文章，里面用到的就是貝葉斯方法，這里我們不打算復(fù)述他寫的文章，而是簡要地將其核心思想介紹一下。
??? 首先，我們需要詢問的是：“問題是什么？”
??? 問題是我們看到用戶輸入了一個不在字典中的單詞，我們需要去猜測：“這個家伙到底真正想輸入的單詞是什么呢？”用剛才我們形式化的語言來敘述就是，我們需要求：
P(我們猜測他想輸入的單詞 | 他實際輸入的單詞)
??? 這個概率。并找出那個使得這個概率最大的猜測單詞。顯然，我們的猜測未必是唯一的，就像前面舉的那個自然語言的歧義性的例子一樣；這里，比如用戶輸入： thew ，那么他到底是想輸入 the ，還是想輸入 thaw ？到底哪個猜測可能性更大呢？幸運的是我們可以用貝葉斯公式來直接出它們各自的概率，我們不妨將我們的多個猜測記為 h1 h2 .. （ h 代表 hypothesis），它們都屬于一個有限且離散的猜測空間 H （單詞總共就那么多而已），將用戶實際輸入的單詞記為 D （ D 代表 Data ，即觀測數(shù)據(jù)），于是
P(我們的猜測1 | 他實際輸入的單詞)
??? 可以抽象地記為：
P(h1 | D)
??? 類似地，對于我們的猜測2，則是 P(h2 | D)。不妨統(tǒng)一記為：
P(h | D)
運用一次貝葉斯公式，我們得到：
P(h | D) = P(h) * P(D | h) / P(D)
??? 對于不同的具體猜測 h1 h2 h3 .. ，P(D) 都是一樣的，所以在比較 P(h1 | D) 和 P(h2 | D) 的時候我們可以忽略這個常數(shù)。即我們只需要知道：
P(h | D) ∝ P(h) * P(D | h) （注：那個符號的意思是“正比例于”，不是無窮大，注意符號右端是有一個小缺口的。）
??? 這個式子的抽象含義是：對于給定觀測數(shù)據(jù)，一個猜測是好是壞，取決于“這個猜測本身獨立的可能性大小（先驗概率，Prior ）”和“這個猜測生成我們觀測到的數(shù)據(jù)的可能性大小”（似然，Likelihood ）的乘積。具體到我們的那個 thew 例子上，含義就是，用戶實際是想輸入 the 的可能性大小取決于 the 本身在詞匯表中被使用的可能性（頻繁程度）大小（先驗概率）和 想打 the 卻打成 thew 的可能性大小（似然）的乘積。
??? 剩下的事情就很簡單了，對于我們猜測為可能的每個單詞計算一下 P(h) * P(D | h) 這個值，然后取最大的，得到的就是最靠譜的猜測。更多細(xì)節(jié)請參看未鵬兄之原文。
2.3、貝葉斯的應(yīng)用
2.3.1、中文分詞
?
? ? 貝葉斯是機器學(xué)習(xí)的核心方法之一。比如中文分詞領(lǐng)域就用到了貝葉斯。浪潮之巔的作者吳軍在《數(shù)學(xué)之美》系列中就有一篇是介紹中文分詞的。這里介紹一下核心的思想，不做贅述，詳細(xì)請參考吳軍的原文。
? ? 分詞問題的描述為：給定一個句子（字串），如：
??? 南京市長江大橋
? ? 如何對這個句子進(jìn)行分詞（詞串）才是最靠譜的。例如：
1. 南京市/長江大橋
2. 南京/市長/江大橋
?
? ? 這兩個分詞，到底哪個更靠譜呢？
? ? 我們用貝葉斯公式來形式化地描述這個問題，令 X 為字串（句子），Y 為詞串（一種特定的分詞假設(shè)）。我們就是需要尋找使得 P(Y|X) 最大的 Y ，使用一次貝葉斯可得：
? ? P(Y|X) ∝ P(Y)*P(X|Y)
? ? ?用自然語言來說就是 這種分詞方式（詞串）的可能性 乘以 這個詞串生成我們的句子的可能性。我們進(jìn)一步容易看到：可以近似地將 P(X|Y) 看作是恒等于 1 的，因為任意假想的一種分詞方式之下生成我們的句子總是精準(zhǔn)地生成的（只需把分詞之間的分界符號扔掉即可）。于是，我們就變成了去最大化 P(Y) ，也就是尋找一種分詞使得這個詞串（句子）的概率最大化。而如何計算一個詞串：
? ? W1, W2, W3, W4 ..
? ? 的可能性呢？我們知道，根據(jù)聯(lián)合概率的公式展開：P(W1, W2, W3, W4 ..) = P(W1) * P(W2|W1) * P(W3|W2, W1) * P(W4|W1,W2,W3) * .. 于是我們可以通過一系列的條件概率（右式）的乘積來求整個聯(lián)合概率。然而不幸的是隨著條件數(shù)目的增加（P(Wn|Wn-1,Wn-2,..,W1) 的條件有 n-1 個），數(shù)據(jù)稀疏問題也會越來越嚴(yán)重，即便語料庫再大也無法統(tǒng)計出一個靠譜的 P(Wn|Wn-1,Wn-2,..,W1) 來。為了緩解這個問題，計算機科學(xué)家們一如既往地使用了“天真”假設(shè)：我們假設(shè)句子中一個詞的出現(xiàn)概率只依賴于它前面的有限的 k 個詞（k 一般不超過 3，如果只依賴于前面的一個詞，就是2元語言模型（2-gram），同理有 3-gram 、 4-gram 等），這個就是所謂的“有限地平線”假設(shè)。
? ? ?雖然上面這個假設(shè)很傻很天真，但結(jié)果卻表明它的結(jié)果往往是很好很強大的，后面要提到的樸素貝葉斯方法使用的假設(shè)跟這個精神上是完全一致的，我們會解釋為什么像這樣一個天真的假設(shè)能夠得到強大的結(jié)果。目前我們只要知道，有了這個假設(shè)，剛才那個乘積就可以改寫成： P(W1) * P(W2|W1) * P(W3|W2) * P(W4|W3) .. （假設(shè)每個詞只依賴于它前面的一個詞）。而統(tǒng)計 P(W2|W1) 就不再受到數(shù)據(jù)稀疏問題的困擾了。對于我們上面提到的例子“南京市長江大橋”，如果按照自左到右的貪婪方法分詞的話，結(jié)果就成了“南京市長/江大橋”。但如果按照貝葉斯分詞的話（假設(shè)使用 3-gram），由于“南京市長”和“江大橋”在語料庫中一起出現(xiàn)的頻率為 0 ，這個整句的概率便會被判定為 0 。 從而使得“南京市/長江大橋”這一分詞方式勝出。
?
2.3.2、貝葉斯圖像識別，Analysis by Synthesis
? ? 貝葉斯方法是一個非常 general 的推理框架。其核心理念可以描述成：Analysis by Synthesis （通過合成來分析）。06 年的認(rèn)知科學(xué)新進(jìn)展上有一篇 paper 就是講用貝葉斯推理來解釋視覺識別的，一圖勝千言，下圖就是摘自這篇 paper ：
?
?
?
?
? ? 首先是視覺系統(tǒng)提取圖形的邊角特征，然后使用這些特征自底向上地激活高層的抽象概念（比如是 E 還是 F 還是等號），然后使用一個自頂向下的驗證來比較到底哪個概念最佳地解釋了觀察到的圖像。
2.3.3、EM?算法與基于模型的聚類
? ? ?聚類是一種無指導(dǎo)的機器學(xué)習(xí)問題，問題描述：給你一堆數(shù)據(jù)點，讓你將它們最靠譜地分成一堆一堆的。聚類算法很多，不同的算法適應(yīng)于不同的問題，這里僅介紹一個基于模型的聚類，該聚類算法對數(shù)據(jù)點的假設(shè)是，這些數(shù)據(jù)點分別是圍繞 K 個核心的 K 個正態(tài)分布源所隨機生成的，使用 Han JiaWei 的《Data Ming： Concepts and Techniques》中的圖：
?
?
?
?
? ? 圖中有兩個正態(tài)分布核心，生成了大致兩堆點。我們的聚類算法就是需要根據(jù)給出來的那些點，算出這兩個正態(tài)分布的核心在什么位置，以及分布的參數(shù)是多少。這很明顯又是一個貝葉斯問題，但這次不同的是，答案是連續(xù)的且有無窮多種可能性，更糟的是，只有當(dāng)我們知道了哪些點屬于同一個正態(tài)分布圈的時候才能夠?qū)@個分布的參數(shù)作出靠譜的預(yù)測，現(xiàn)在兩堆點混在一塊我們又不知道哪些點屬于第一個正態(tài)分布，哪些屬于第二個。反過來，只有當(dāng)我們對分布的參數(shù)作出了靠譜的預(yù)測時候，才能知道到底哪些點屬于第一個分布，那些點屬于第二個分布。這就成了一個先有雞還是先有蛋的問題了。為了解決這個循環(huán)依賴，總有一方要先打破僵局，說，不管了，我先隨便整一個值出來，看你怎么變，然后我再根據(jù)你的變化調(diào)整我的變化，然后如此迭代著不斷互相推導(dǎo)，最終收斂到一個解。這就是 EM 算法。
? ? EM 的意思是“Expectation-Maximazation”，在這個聚類問題里面，我們是先隨便猜一下這兩個正態(tài)分布的參數(shù)：如核心在什么地方，方差是多少。然后計算出每個數(shù)據(jù)點更可能屬于第一個還是第二個正態(tài)分布圈，這個是屬于 Expectation 一步。有了每個數(shù)據(jù)點的歸屬，我們就可以根據(jù)屬于第一個分布的數(shù)據(jù)點來重新評估第一個分布的參數(shù)（從蛋再回到雞），這個是 Maximazation 。如此往復(fù)，直到參數(shù)基本不再發(fā)生變化為止。這個迭代收斂過程中的貝葉斯方法在第二步，根據(jù)數(shù)據(jù)點求分布的參數(shù)上面。
2.3.4、最大似然與最小二乘
?
?
?
?
? ? 學(xué)過線性代數(shù)的大概都知道經(jīng)典的最小二乘方法來做線性回歸。問題描述是：給定平面上 N 個點，（這里不妨假設(shè)我們想用一條直線來擬合這些點——回歸可以看作是擬合的特例，即允許誤差的擬合），找出一條最佳描述了這些點的直線。
? ? 一個接踵而來的問題就是，我們?nèi)绾味x最佳？我們設(shè)每個點的坐標(biāo)為 (Xi, Yi) 。如果直線為 y = f(x) 。那么 (Xi, Yi) 跟直線對這個點的“預(yù)測”：(Xi, f(Xi)) 就相差了一個 ΔYi = |Yi – f(Xi)| 。最小二乘就是說尋找直線使得 (ΔY1)^2 + (ΔY2)^2 + .. （即誤差的平方和）最小，至于為什么是誤差的平方和而不是誤差的絕對值和，統(tǒng)計學(xué)上也沒有什么好的解釋。然而貝葉斯方法卻能對此提供一個完美的解釋。
? ? 我們假設(shè)直線對于坐標(biāo) Xi 給出的預(yù)測 f(Xi) 是最靠譜的預(yù)測，所有縱坐標(biāo)偏離 f(Xi) 的那些數(shù)據(jù)點都含有噪音，是噪音使得它們偏離了完美的一條直線，一個合理的假設(shè)就是偏離路線越遠(yuǎn)的概率越小，具體小多少，可以用一個正態(tài)分布曲線來模擬，這個分布曲線以直線對 Xi 給出的預(yù)測 f(Xi) 為中心，實際縱坐標(biāo)為 Yi 的點 (Xi, Yi) 發(fā)生的概率就正比于 EXP[-(ΔYi)^2]。（EXP(..) 代表以常數(shù) e 為底的多少次方）。
? ? 現(xiàn)在我們回到問題的貝葉斯方面，我們要想最大化的后驗概率是：
P(h|D) ∝ P(h) * P(D|h)
? ? 又見貝葉斯！這里 h 就是指一條特定的直線，D 就是指這 N 個數(shù)據(jù)點。我們需要尋找一條直線 h 使得 P(h) * P(D|h) 最大。很顯然，P(h) 這個先驗概率是均勻的，因為哪條直線也不比另一條更優(yōu)越。所以我們只需要看 P(D|h) 這一項，這一項是指這條直線生成這些數(shù)據(jù)點的概率，剛才說過了，生成數(shù)據(jù)點 (Xi, Yi) 的概率為 EXP[-(ΔYi)^2] 乘以一個常數(shù)。而 P(D|h) = P(d1|h) * P(d2|h) * .. 即假設(shè)各個數(shù)據(jù)點是獨立生成的，所以可以把每個概率乘起來。于是生成 N 個數(shù)據(jù)點的概率為 EXP[-(ΔY1)^2] * EXP[-(ΔY2)^2] * EXP[-(ΔY3)^2] * .. = EXP{-[(ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + ..]} 最大化這個概率就是要最小化 (ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + .. 。 熟悉這個式子嗎？
2.4、樸素貝葉斯方法
? ? 樸素貝葉斯方法是一個很特別的方法，所以值得介紹一下。我們用樸素貝葉斯在垃圾郵件過濾中的應(yīng)用來舉例說明。
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+) 。我們又一次遇到了數(shù)據(jù)稀疏性，為什么這么說呢？P(d1,d2,..,dn|h+) 就是說在垃圾郵件當(dāng)中出現(xiàn)跟我們目前這封郵件一模一樣的一封郵件的概率是多大！開玩笑，每封郵件都是不同的，世界上有無窮多封郵件。瞧，這就是數(shù)據(jù)稀疏性，因為可以肯定地說，你收集的訓(xùn)練數(shù)據(jù)庫不管里面含了多少封郵件，也不可能找出一封跟目前這封一模一樣的。結(jié)果呢？我們又該如何來計算 P(d1,d2,..,dn|h+) 呢？
? ? 我們將 P(d1,d2,..,dn|h+)? 擴(kuò)展為： P(d1|h+) * P(d2|d1, h+) * P(d3|d2,d1, h+) * .. 。熟悉這個式子嗎？這里我們會使用一個更激進(jìn)的假設(shè)，我們假設(shè) di 與 di-1 是完全條件無關(guān)的，于是式子就簡化為 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 。這個就是所謂的條件獨立假設(shè)，也正是樸素貝葉斯方法的樸素之處。而計算 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 就太簡單了，只要統(tǒng)計 di 這個單詞在垃圾郵件中出現(xiàn)的頻率即可。關(guān)于貝葉斯垃圾郵件過濾更多的內(nèi)容可以參考這個條目，注意其中提到的其他資料。
2.5、層級貝葉斯模型
?
?
?
?
? ??層級貝葉斯模型是現(xiàn)代貝葉斯方法的標(biāo)志性建筑之一。前面講的貝葉斯，都是在同一個事物層次上的各個因素之間進(jìn)行統(tǒng)計推理，然而層次貝葉斯模型在哲學(xué)上更深入了一層，將這些因素背后的因素（原因的原因，原因的原因，以此類推）囊括進(jìn)來。一個教科書例子是：如果你手頭有 N 枚硬幣，它們是同一個工廠鑄出來的，你把每一枚硬幣擲出一個結(jié)果，然后基于這 N 個結(jié)果對這 N 個硬幣的 θ （出現(xiàn)正面的比例）進(jìn)行推理。如果根據(jù)最大似然，每個硬幣的 θ 不是 1 就是 0 （這個前面提到過的），然而我們又知道每個硬幣的 p(θ) 是有一個先驗概率的，也許是一個 beta 分布。也就是說，每個硬幣的實際投擲結(jié)果 Xi 服從以 θ 為中心的正態(tài)分布，而 θ 又服從另一個以 Ψ 為中心的 beta 分布。層層因果關(guān)系就體現(xiàn)出來了。進(jìn)而 Ψ 還可能依賴于因果鏈上更上層的因素，以此類推。
2.6、隱馬可夫模型（HMM）
?
?
?
?
? ? 吳軍在數(shù)學(xué)之美系列里面介紹的隱馬可夫模型（HMM）就是一個簡單的層級貝葉斯模型：
那么怎么根據(jù)接收到的信息來推測說話者想表達(dá)的意思呢？我們可以利用叫做“隱含馬爾可夫模型”（Hidden Markov Model）來解決這些問題。以語音識別為例，當(dāng)我們觀測到語音信號 o1,o2,o3 時，我們要根據(jù)這組信號推測出發(fā)送的句子 s1,s2,s3。顯然，我們應(yīng)該在所有可能的句子中找最有可能性的一個。用數(shù)學(xué)語言來描述，就是在已知 o1,o2,o3,…的情況下，求使得條件概率 P (s1,s2,s3,…|o1,o2,o3….) 達(dá)到最大值的那個句子 s1,s2,s3,…
? ? 吳軍的文章中這里省掉沒說的是，s1, s2, s3, .. 這個句子的生成概率同時又取決于一組參數(shù)，這組參數(shù)決定了 s1, s2, s3, .. 這個馬可夫鏈的先驗生成概率。如果我們將這組參數(shù)記為 λ ，我們實際上要求的是：P(S|O, λ) （其中 O 表示 o1,o2,o3,.. ，S表示 s1,s2,s3,..）
當(dāng)然，上面的概率不容易直接求出，于是我們可以間接地計算它。利用貝葉斯公式并且省掉一個常數(shù)項，可以把上述公式等價變換成
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,…本身能夠成為一個合乎情理的句子的可能性，所以這個公式的意義是用發(fā)送信號為 s1,s2,s3…這個數(shù)列的可能性乘以 s1,s2,s3.. 本身可以一個句子的可能性，得出概率。
? ? 這里，s1,s2,s3…本身可以一個句子的可能性其實就取決于參數(shù) λ ，也就是語言模型。所以簡而言之就是發(fā)出的語音信號取決于背后實際想發(fā)出的句子，而背后實際想發(fā)出的句子本身的獨立先驗概率又取決于語言模型。更多具體細(xì)節(jié)請參考未鵬兄之：數(shù)學(xué)之美番外篇：平凡而又神奇的貝葉斯方法。
參考文獻(xiàn)
后記
? ? 促成自己寫這篇文章乃至整個聚類 & 分類算法系列的有3個因素，
?
?
??? 最后一件事：關(guān)于讀書會第3期周愛民 & 梁斌，時間：本周日5月20日下午2點，地點：北大二教527。報名：發(fā)姓名 + 公司職位?or?學(xué)校專業(yè) + 專注方向至郵箱：zhoulei0907@yahoo.cn。詳情，請參見此文：讀書會·北京：最新第3期05.20下午周愛民 ，梁斌penny于北大舉辦。歡迎朋友們的到來。
??? 研究了一年有余的數(shù)據(jù)結(jié)構(gòu)方面的算法，現(xiàn)在可以逐漸轉(zhuǎn)向應(yīng)用方面(機器學(xué)習(xí) & 數(shù)據(jù)挖掘)的算法學(xué)習(xí)了。OK，本文或本聚類 & 分類算法系列中任何一篇文章有任何問題，漏洞，或bug，歡迎任何讀者隨時不吝賜教 & 指正，感謝大家，謝謝。完。July、二零一二年五月十八日凌晨二點半。
posted on 2012-05-18 22:26 wentingtu 閱讀(...) 評論(...) 編輯 收藏轉(zhuǎn)載于:https://www.cnblogs.com/wentingtu/archive/2012/05/18/2508393.html
總結(jié)
以上是生活随笔為你收集整理的从决策树学习谈到贝叶斯分类算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： kde下sudo出现cannot con
- 下一篇： 从雷军那里反思，做什么样的公司？