樸素貝葉斯、決策樹算法學(xué)習(xí)總結(jié)

1、基礎(chǔ)算法學(xué)習(xí)總結(jié)樸素貝葉斯學(xué)習(xí)算法簡(jiǎn)介貝葉斯分類是一類分類算法的總稱，這類算法均以貝葉斯定理為基礎(chǔ)，故統(tǒng)稱為貝葉斯分類。而樸素樸素貝葉斯分類是貝葉斯分類中最簡(jiǎn)單，也是常見的一種分類方法。從數(shù)學(xué)角度來(lái)說(shuō)，分類問(wèn)題可做如下定義:已知集合：C = y , y , y，,y 和I = (x ,x ,x ,., x ，確定映射規(guī)則y = f (x)，使得任意 123 n123 nx g I有且僅有一個(gè)y e C使得y = f (x )成立。(不考慮模糊數(shù)學(xué)里的模糊集情況)。其中Ciiii叫做類別集合，其中每一個(gè)元素是一個(gè)類別，而I叫做項(xiàng)集合，其中每一個(gè)元素是一個(gè)待分類項(xiàng)，f叫做分類器。分類算法的任務(wù)就是

2、構(gòu)造分類器f。分類問(wèn)題往往采用經(jīng)驗(yàn)性方法構(gòu)造映射規(guī)則，即一般情況下的分類問(wèn)題缺少足夠的信息來(lái)構(gòu)造100%正確的映射規(guī)則，而是通過(guò)對(duì)經(jīng)驗(yàn)數(shù)據(jù)的學(xué)習(xí)從而實(shí)現(xiàn)一定概率意義上正確的分類，因此所訓(xùn)練出的分類器并不是一定能將每個(gè)待分類項(xiàng)準(zhǔn)確映射到其分類，分類器的質(zhì)量與分類器構(gòu)造方法、待分類數(shù)據(jù)的特性以及訓(xùn)練樣本數(shù)量等諸多因素有關(guān)。解決問(wèn)題：已知某條件概率，如何得到兩個(gè)事件交換后的概率，也就是在已知P(AIB) 的情況下如何求得P(BIA)。這里先解釋什么是條件概率：P(BIA)表示事件B已經(jīng)發(fā)生的前提 下，事件A發(fā)生的概率，叫做事件B發(fā)生下事件A的條件概率。其基本求解公式為：P( AW) =冬P (B)貝

3、葉斯定理之所以有用，是因?yàn)槲覀冊(cè)谏钪薪?jīng)常遇到這種情況：我們可以很容易直接得出P(AIB)，P(BIA)則很難直接得出，但我們更關(guān)心P(BIA)，貝葉斯定理就為我們打通從 P(AIB)獲得P(BIA)的道路。下面不加證明地直接給出貝葉斯定理：P(B I A) = P(AIB)P(B)P (A)算法流程樸素貝葉斯分類是一種十分簡(jiǎn)單的分類算法，叫它樸素貝葉斯分類是因?yàn)檫@種方法的思 想真的很樸素，樸素貝葉斯的思想基礎(chǔ)是這樣的：對(duì)于給出的待分類項(xiàng)，求解在此項(xiàng)出現(xiàn)的 條件下各個(gè)類別出現(xiàn)的概率，哪個(gè)最大，就認(rèn)為此待分類項(xiàng)屬于哪個(gè)類別。樸素貝葉斯分類的正式定義如下：1、設(shè)X =風(fēng),.,%為一個(gè)待分類項(xiàng)，而每

4、個(gè)a為x的一個(gè)特征屬性。2、有類別集合 C = y, y , y ,., y TOC o 1-5 h z 123 n3、 計(jì)算 P(yi I x), P(y2 I x),., P(y I x)。4、 如果 P(y I x) = maxP(y I x), P(y I x),., P(y I x)，則 x e yk12nk那么現(xiàn)在的關(guān)鍵就是如何計(jì)算第3步中的各個(gè)條件概率。我們可以這么做：1、找到一個(gè)已知分類的待分類項(xiàng)集合，這個(gè)集合叫做訓(xùn)練樣本集。2、統(tǒng)計(jì)得到在各類別下各個(gè)特征屬性的條件概率估計(jì)。即：P(aI y ), P(aI y ),., P(aI y ); P(aI y ), P(aI y )

5、,., P(aI y );.;P(aI y ), P(aI y ),., P(aI y )1121m 11222m 21 n2 nm n3、如果各個(gè)特征屬性是條件獨(dú)立的，則根據(jù)貝葉斯定理有如下推導(dǎo):P(y Ix) = P七)P(yiP( x)因?yàn)榉帜笇?duì)于所有類別為常數(shù)，因?yàn)槲覀冎灰獙⒎肿幼畲蠡钥?。又因?yàn)楦魈卣鲗傩允?條件獨(dú)立的，所以有:P(x I y )P(y ) = P(a I y )P(a I y ).P(a I y ) = P(y )H P(a I y )i i1 i 2 im iij i根據(jù)上述分析，樸素貝葉斯分類的流程可以由下圖1表示(暫時(shí)不考慮驗(yàn)證):準(zhǔn)備工作階段對(duì)每個(gè)特征屬性

6、計(jì)算所有劃分的 條件概率應(yīng)用階段分類器訓(xùn)練階段圖1樸素貝葉斯分類流程可以看到，整個(gè)樸素貝葉斯分類分為三個(gè)階段：第一階段一一準(zhǔn)備工作階段，這個(gè)階段的任務(wù)是為樸素貝葉斯分類做必要的準(zhǔn)備，主要工作是根據(jù)具體情況確定特征屬性，并對(duì)每個(gè)特征屬性進(jìn)行適當(dāng)劃分，然后由人工對(duì)一部分 待分類項(xiàng)進(jìn)行分類，形成訓(xùn)練樣本集合。這一階段的輸入是所有待分類數(shù)據(jù)，輸出是特征屬 性和訓(xùn)練樣本。這一階段是整個(gè)樸素貝葉斯分類中唯一需要人工完成的階段，其質(zhì)量對(duì)整個(gè) 過(guò)程將有重要影響，分類器的質(zhì)量很大程度上由特征屬性、特征屬性劃分及訓(xùn)練樣本質(zhì)量決 定。第二階段一一分類器訓(xùn)練階段，這個(gè)階段的任務(wù)就是生成分類器，主要工作是計(jì)算每個(gè) 類別

7、在訓(xùn)練樣本中的出現(xiàn)頻率及每個(gè)特征屬性劃分對(duì)每個(gè)類別的條件概率估計(jì)，并將結(jié)果記 錄。其輸入是特征屬性和訓(xùn)練樣本，輸出是分類器。這一階段是機(jī)械性階段，根據(jù)前面討論 的公式可以由程序自動(dòng)計(jì)算完成。第三階段一一應(yīng)用階段。這個(gè)階段的任務(wù)是使用分類器對(duì)待分類項(xiàng)進(jìn)行分類，其輸入是 分類器和待分類項(xiàng)，輸出是待分類項(xiàng)與類別的映射關(guān)系。這一階段也是機(jī)械性階段，由程序 完成。特征屬性劃分的條件概率及Laplace校準(zhǔn)由上文看出，計(jì)算各個(gè)劃分的條件概率P(aly)是樸素貝葉斯分類的關(guān)鍵性步驟，當(dāng)特征 屬性為離散值時(shí)，只要很方便的統(tǒng)計(jì)訓(xùn)練樣本中各個(gè)劃分在每個(gè)類別中出現(xiàn)的頻率即可用來(lái) 估計(jì)P(aly)，下面重點(diǎn)討論特征屬

8、性是連續(xù)值的情況。當(dāng)特征屬性為連續(xù)值時(shí)，通常假定其值服從高斯分布(也稱正態(tài)分布)。即：1 _(2g(xm,b) = e 2。22na而P(a l y ) = g(ak ,Q )因此只要計(jì)算出訓(xùn)練樣本中各個(gè)類別中此特征項(xiàng)劃分的各均 k yi yi值和標(biāo)準(zhǔn)差，代入上述公式即可得到需要的估計(jì)值。另一個(gè)需要討論的問(wèn)題就是當(dāng)P(aly)=0怎么辦，當(dāng)某個(gè)類別下某個(gè)特征項(xiàng)劃分沒(méi)有出現(xiàn) 時(shí)，就是產(chǎn)生這種現(xiàn)象，這會(huì)令分類器質(zhì)量大大降低。為了解決這個(gè)問(wèn)題，我們引入Laplace 校準(zhǔn)，它的思想非常簡(jiǎn)單，就是對(duì)沒(méi)類別下所有劃分的計(jì)數(shù)加1，這樣如果訓(xùn)練樣本集數(shù)量 充分大時(shí)，并不會(huì)對(duì)結(jié)果產(chǎn)生影響，并且解決了上述頻率為

9、0的尷尬局面。算法小結(jié)樸素貝葉斯算法的主要原理基本已經(jīng)做了總結(jié)，這里對(duì)樸素貝葉斯的優(yōu)缺點(diǎn)做一個(gè)總結(jié)。樸素貝葉斯的主要優(yōu)點(diǎn)有：樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有穩(wěn)定的分類效率。對(duì)小規(guī)模的數(shù)據(jù)表現(xiàn)很好，能夠處理多分類任務(wù)，適合增量式訓(xùn)練，尤其是數(shù)據(jù)量 超出內(nèi)存時(shí)，我們可以一批批的去增量訓(xùn)練。對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡(jiǎn)單，常用于文本分類。樸素貝葉斯的主要缺點(diǎn)有：1）理論上，樸素貝葉斯模型與其他分類方法相比具有最小的誤差率。但是實(shí)際上并非 總是如此，這是因?yàn)闃闼刎惾~斯模型假設(shè)屬性之間相互獨(dú)立，這個(gè)假設(shè)在實(shí)際應(yīng)用中往往是 不成立的，在屬性個(gè)數(shù)比較多或者屬性之間相關(guān)性較大時(shí)，分類效果不好。而在屬性

10、相關(guān)性 較小時(shí)，樸素貝葉斯性能最為良好。對(duì)于這一點(diǎn)，有半樸素貝葉斯之類的算法通過(guò)考慮部分 關(guān)聯(lián)性適度改進(jìn)。2）需要知道先驗(yàn)概率，且先驗(yàn)概率很多時(shí)候取決于假設(shè)，假設(shè)的模型可以有很多種， 因此在某些時(shí)候會(huì)由于假設(shè)的先驗(yàn)?zāi)Ｐ偷脑驅(qū)е骂A(yù)測(cè)效果不佳。3）由于我們是通過(guò)先驗(yàn)和數(shù)據(jù)來(lái)決定后驗(yàn)的概率從而決定分類，所以分類決策存在一 定的錯(cuò)誤率。4）對(duì)輸入數(shù)據(jù)的表達(dá)形式很敏感。決策樹算法學(xué)習(xí)算法簡(jiǎn)介決策樹是一種通過(guò)對(duì)歷史數(shù)據(jù)進(jìn)行測(cè)算實(shí)現(xiàn)對(duì)新數(shù)據(jù)進(jìn)行分類和預(yù)測(cè)的算法。簡(jiǎn)單來(lái)說(shuō) 決策樹算法就是通過(guò)對(duì)已有明確結(jié)果的歷史數(shù)據(jù)進(jìn)行分析，尋找數(shù)據(jù)中的特征。并以此為依 據(jù)對(duì)新產(chǎn)生的數(shù)據(jù)結(jié)果進(jìn)行預(yù)測(cè)。決策樹（decision

11、 tree）是一個(gè)樹結(jié)構(gòu)（可以是二叉樹或 非二叉樹）。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試，每個(gè)分支代表這個(gè)特征屬性在某 個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開 始，測(cè)試待分類項(xiàng)中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達(dá)葉子節(jié)點(diǎn)，將葉 子節(jié)點(diǎn)存放的類別作為決策結(jié)果。不同于貝葉斯算法，決策樹的構(gòu)造過(guò)程不依賴領(lǐng)域知識(shí)，它使用屬性選擇度量來(lái)選擇將 元組最好地劃分成不同的類的屬性。所謂決策樹的構(gòu)造就是進(jìn)行屬性選擇度量確定各個(gè)特征 屬性之間的拓?fù)浣Y(jié)構(gòu)。構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性。所謂分裂屬性就是在某個(gè)節(jié)點(diǎn)處按照某一特征屬性 的不同劃分構(gòu)造不同的分支

12、，其目標(biāo)是讓各個(gè)分裂子集盡可能地純”。盡可能“純”就是盡量 讓一個(gè)分裂子集中待分類項(xiàng)屬于同一類別。分裂屬性分為三種不同的情況：1、屬性是離散值且不要求生成二叉決策樹。此時(shí)用屬性的每一個(gè)劃分作為一個(gè)分支。2、屬性是離散值且要求生成二叉決策樹。此時(shí)使用屬性劃分的一個(gè)子集進(jìn)行測(cè)試，按照“屬 于此子集”和“不屬于此子集”分成兩個(gè)分支。3、屬性是連續(xù)值。此時(shí)確定一個(gè)值作為分裂點(diǎn)split_point，按照 split_point和=split_point 生成兩個(gè)分支。構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進(jìn)行屬性選擇度量，屬性選擇度量是一種選擇分裂準(zhǔn)則，是 將給定的類標(biāo)記的訓(xùn)練集合的數(shù)據(jù)劃分D“最好”地分成個(gè)體類的

13、啟發(fā)式方法，它決定了拓?fù)?結(jié)構(gòu)及分裂點(diǎn)split_point的選擇。算法工作原理決策樹一般都是自上而下的來(lái)生成的。選擇分割的方法有多種，但是目的都是一致的， 即對(duì)目標(biāo)類嘗試進(jìn)行最佳的分割。從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)都有一條路徑，這條路徑就是一條“規(guī)則”。決策樹可以是二叉的， 也可以是多叉的。對(duì)每個(gè)節(jié)點(diǎn)的衡量：1：通過(guò)該節(jié)點(diǎn)的記錄數(shù)；2：如果是葉子節(jié)點(diǎn)的話，分類的路徑；3：對(duì)葉子節(jié)點(diǎn)正確分類的比例。2.2.1. ID3 算法ID3算法的核心是：在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益(information gain) 作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非葉結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的 類

14、別信息。其具體方法是：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由 該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直 到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來(lái)對(duì)新的樣本進(jìn)行 分類。下面先定義幾個(gè)要用到的概念。設(shè)D為用類別對(duì)訓(xùn)練元組進(jìn)行的劃分，則D的熵(entropy)表示為：info(D)=翊 p log (p )i 2 i其中pi表示第i個(gè)類別在整個(gè)訓(xùn)練元組中出現(xiàn)的概率，可以用屬于此類別元素的數(shù)量 除以訓(xùn)練元組元素總數(shù)量作為估計(jì)。熵的實(shí)際意義表示是D中元組的類標(biāo)號(hào)所需要的平均 信息量。我們假設(shè)將訓(xùn)練元組D按屬性A進(jìn)行劃分，

15、則A對(duì)D劃分的期望信息為：Dinf o (D) = Z jinf o(D )j=1而信息增益即為兩者的差值：gain( A) = inf o(D) 一 inf o(D)ID3算法就是在每次需要分裂時(shí)，計(jì)算每個(gè)屬性的增益率，然后選擇增益率最大的屬性進(jìn)行分裂。ID3算法的優(yōu)點(diǎn)是：算法的理論清晰，方法簡(jiǎn)單，學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是： 只對(duì)比較小的數(shù)據(jù)集有效，且對(duì)噪聲比較敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時(shí)，決策樹可能會(huì)隨之改 變。2.2.2. C4.5 算法C4.5算法繼承了 ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：1：用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的 不足

16、；2：在樹構(gòu)造過(guò)程中進(jìn)行剪枝；3：能夠完成對(duì)連續(xù)屬性的離散化處理；4：能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法首先定義了“分裂信息”，其定義可以表示成：split _ inf o (D) =Z tlog () aD 2 di=1其中各符號(hào)意義與ID3算法相同，然后，增益率被定義為：gain ratio (A)=知(A)一split _inf o( A)C4.5算法與其它分類算法如統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)等比較起來(lái)有如下優(yōu)點(diǎn)：產(chǎn)生的分類 規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序 掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn) 練

17、集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。決策樹剪枝在決策樹構(gòu)造時(shí)，由于訓(xùn)練數(shù)據(jù)中的噪音或孤立點(diǎn)，許多分枝反映的是訓(xùn)練數(shù)據(jù)中的異 常，使用這樣的判定樹對(duì)類別未知的數(shù)據(jù)進(jìn)行分類，分類的準(zhǔn)確性不高。因此試圖檢測(cè)和減 去這樣的分支，檢測(cè)和減去這些分支的過(guò)程被稱為樹剪枝。樹剪枝方法用于處理過(guò)分適應(yīng)數(shù) 據(jù)問(wèn)題。通常，這種方法使用統(tǒng)計(jì)度量，減去最不可靠的分支，這將導(dǎo)致較快的分類，提高 樹獨(dú)立于訓(xùn)練數(shù)據(jù)正確分類的能力。決策樹常用的剪枝常用的簡(jiǎn)直方法有兩種：預(yù)剪枝(Pre-Pruning)和后剪枝 (Post-Pruning)。預(yù)剪枝是根據(jù)一些原則及早的停止樹增長(zhǎng)，如樹的深度達(dá)到用戶所要的深 度、節(jié)點(diǎn)中樣本個(gè)數(shù)少于

18、用戶指定個(gè)數(shù)、不純度指標(biāo)下降的最大幅度小于用戶指定的幅度等。 預(yù)剪枝的核心問(wèn)題是如何事先指定樹的最大深度，如果設(shè)置的最大深度不恰當(dāng)，那么將會(huì)導(dǎo) 致過(guò)于限制樹的生長(zhǎng)，使決策樹的表達(dá)式規(guī)則趨于一般，不能更好地對(duì)新數(shù)據(jù)集進(jìn)行分類和 預(yù)測(cè)。除了事先限定決策樹的最大深度之外，還有另外一個(gè)方法來(lái)實(shí)現(xiàn)預(yù)剪枝操作，那就是 采用檢驗(yàn)技術(shù)對(duì)當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的樣本集合進(jìn)行檢驗(yàn)，如果該樣本集合的樣本數(shù)量已小于事先 指定的最小允許值，那么停止該結(jié)點(diǎn)的繼續(xù)生長(zhǎng)，并將該結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)，否則可以繼續(xù) 擴(kuò)展該結(jié)點(diǎn)。后剪枝則是通過(guò)在完全生長(zhǎng)的樹上剪去分枝實(shí)現(xiàn)的，通過(guò)刪除節(jié)點(diǎn)的分支來(lái)剪去樹節(jié)點(diǎn)， 可以使用的后剪枝方法有多種，比如：代價(jià)復(fù)雜性剪枝、最小誤差剪枝、悲觀誤差剪枝等等。后剪枝操作是一個(gè)邊修剪邊檢驗(yàn)的過(guò)程，一般規(guī)則標(biāo)準(zhǔn)是:在決策樹的不斷剪枝操作過(guò)程中， 將原樣本集合或新數(shù)據(jù)集合作為測(cè)試數(shù)據(jù)，檢驗(yàn)決策樹對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度，并計(jì)算出相 應(yīng)的錯(cuò)誤率，如果剪掉某個(gè)子樹后的決策樹對(duì)測(cè)試數(shù)據(jù)的預(yù)測(cè)精度或其他測(cè)度不降低，那么 剪掉該子樹。算法小結(jié)決策樹算法優(yōu)點(diǎn)如下：1：決策樹易于理解和實(shí)現(xiàn)，人們?cè)谠趯W(xué)習(xí)過(guò)程中不需要