機器學(xué)習(xí)算法總結(jié)-決策樹(參考版)
2025-06-20 03:55本頁面
【正文】 。(2)若無屬性可用于當(dāng)?shù)臉颖炯?，這里用少數(shù)服從多數(shù)的原則，將當(dāng)前節(jié)點標記成葉節(jié)點，并標記為當(dāng)前所合樣本集中類別個數(shù)最多的類別。若一個屬性一旦在某個節(jié)點出現(xiàn)，那它就不能再出現(xiàn)在該節(jié)點之后所產(chǎn)生的子樹節(jié)點中。一個測試屬性的每個值均對應(yīng)一個將要被創(chuàng)建的分枝，同時也對應(yīng)著一個被劃分的子集。這個屬性就成為該節(jié)點的測試屬性。若一個節(jié)點的樣本均為同一類別，則該節(jié)點就成為葉節(jié)點并標記為該類別。then(5)返回N作為葉節(jié)點，標記為samples中最普通的類；(6)選擇attribute_list中具有最高信息增益的屬性test_attribute；(7)標記節(jié)點為test_attribute：(8)For each test_attribute中的已知值ai：(9) 由節(jié)點N長出一個條件為test_attribute=a．的分枝：(10)設(shè)S1是samples中test—attribute=a．的樣本的集合：(1I)If S1為空，then(12)加上一個樹葉，標記為samples中最普通的類；(13)Else 加上一個由 Generate_decision_tree (s1，attribute_1ist_test_attribute)返回的節(jié)點。輸出：一棵判定樹。建立決策樹的算法如下：算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵判定樹。然后，對每個分枝采取相同的方法，訓(xùn)練樣本是其父節(jié)點劃分的若干子集中的對應(yīng)于該分枝取值的那個樣本子集。用測試數(shù)據(jù)集檢驗決策樹，如果所建立的決策樹不能正確回答所研究的問題，我們要對決策樹進行剪枝以解決過分適應(yīng)數(shù)據(jù)問題，直到建立一棵正確的決策樹，目的是降低由于訓(xùn)練集的噪聲而產(chǎn)生的起伏。決策樹歸納的基本算法是貪心算法，它采用的是自項向下遞歸的各個擊破方式來構(gòu)建判定樹，算法概述如下。 決策樹的建立決策樹的建立過程主要由兩個階段組成：第一階段，建樹階段。當(dāng)然也可以結(jié)合使用事前修剪和事后修剪，形成混合的修剪方法。如果剪掉該節(jié)點能夠降低錯誤率，那么該節(jié)點的所有子節(jié)點就被剪掉，該節(jié)點成為葉節(jié)點。修剪后，被修剪的分枝節(jié)點就成為一個葉節(jié)點，并將其標記為它所包含樣本中類別個數(shù)最多的類別。通過刪除節(jié)點的分枝，剪掉樹節(jié)點。然而，選擇一個適當(dāng)?shù)拈撝凳潜容^困難的，較高的閾值可能導(dǎo)致過分簡化的樹，而較低的閾值可能會導(dǎo)致多余樹枝無法修剪。常用的方法是設(shè)定決策樹的最大高度(層數(shù))來限制樹的生長。該葉節(jié)點中可能包含多個不同類別的訓(xùn)練樣本，由于該修剪是在分枝之前做出的，所以稱之為事前修剪。（1）事前修剪法該方法通過提前停止樹的構(gòu)造而對樹“剪枝”，即通過在當(dāng)前節(jié)點上判斷是否需要繼續(xù)劃分該節(jié)點所含訓(xùn)練樣本集來實現(xiàn)。剪枝常采用統(tǒng)計度量，剪掉最不可靠的分枝，從而帶來較快的分類，提高樹獨立于測試數(shù)據(jù)進行證確分類的能力。解決過適應(yīng)問題的主要方法是對決策樹進行剪枝。由于完全決策樹對訓(xùn)練樣本的特征描述得“過于精確”，無法實現(xiàn)對新樣本的合理分析，所以此時它不是一棵分析新數(shù)掘的最佳決策樹。此外，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。5 優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。處理缺少屬性值的一種策略是賦給它結(jié)點n所對應(yīng)的訓(xùn)練實例中該屬性的最常見值；另外一種更復(fù)雜的策略是為A的每個可能值賦予一個概率。4對于缺失值的處理在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。方法中使用的公式如下： 其中N是實例的數(shù)量，f=E/N為觀察到的誤差率（其中E為N個實例中分類錯誤的個數(shù)），q為真實的誤差率，c為置信度（，），z為對應(yīng)于置信度c的標準差，其值可根據(jù)c的設(shè)定值通過查正態(tài)分布表得到。對于每一個分割點劃分數(shù)據(jù)集的方式，并且從中選擇信息增益比最大的分割點來劃分數(shù)據(jù)集。第i（0itotal）個分割點的取值設(shè)置為Vi=（Aic+A（i+1）c）/2,它可以將該節(jié)點上的數(shù)據(jù)集劃分為兩個子集。(1)將該結(jié)點上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進行排序，得到屬性值的取值序列{A1c，A2c，……Atotalc}。如按照屬性A把S集（含30個用例）分成了10個用例和20個用例兩個集合則2可以處理連續(xù)數(shù)值型屬性，也可以處理連續(xù)性描述屬性。信息增益率定義為： 其中Gain(S,A)與ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照屬性A分裂樣本集S的廣度和均勻性。以信息熵和信息增益度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。 ，并在以下幾方面對ID3算法進行了改進： 1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足； 2) 在樹構(gòu)造過程中進行剪枝； 3) 能夠完成對連續(xù)屬性的離散化處理； 4) 能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。根據(jù)最大信息量原理,ID3就選取頭發(fā)為決策樹的根節(jié)點屬性。 如果我們不是選擇高度而選用屬性頭發(fā),則有: B(C,頭發(fā)) = 3/8 * 0 + 1/8 * 0 + 4/8 * 1 = bits則測試屬性頭發(fā)獲取的信息為M(C)B(C,頭發(fā)) = = bits。二者的差越大，說明測試這個屬性所能傳遞的信息量越大,則判別的速度也就越快?！ ∥覀兿Ｍx的測試屬性能使決策樹獲得最大的信息增益即M(C)B(C, A)為最大值。屬性A將集合C劃分為若干個子集合{C1，C2，...，Cn}?！ 腃集對應(yīng)的決策樹中得到消息的期望信息量記為M(C)，并定義M({})=0。決策樹的復(fù)雜程度與借助這個消息所傳遞的信息量密切相關(guān)。ID3采用了香農(nóng)（Shannon）信息論中的方法以使分類時期望（平均）的測試次數(shù)最小。 若不存在這樣的二個對象:它們在每個屬性上都具有相同的值，卻屬于不同的類別，那么這種生成決策樹的過程是可行的。有時判別一個對象的類別，由于從根到葉節(jié)點的路徑較短，只要測試少量的屬性。至此，所有葉結(jié)點相應(yīng)的對象子集只含同一類的對象，我們就可以用相應(yīng)的類別名（本例中的+ 和 ）來取代各子集，得到一決策樹?！ ∠鄳?yīng)于黑色，紅色和金色三值都有一個對象子集。這里，將人分為兩類，分別以＋、－來指示。對每一個這樣的子集又可以用同樣的策略處理，最后的結(jié)果是一棵樹。決策樹形式的分類規(guī)則適用于任何的對象集Ｃ。在ID3中, 每一個例子用相同的一組屬性來表示，每一個屬性又有自身的屬性值集，如顏色屬性可取值是{紅、綠、蘭}等。ID3的顯著優(yōu)點是歸納學(xué)習(xí)花費的時
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1