【正文】 況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如〈x，c(x)〉是樣本集S中的一個訓(xùn)練實例，但是其屬性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略是賦給它結(jié)點n所對應(yīng)的訓(xùn)練實例中該屬性的最常見值；另外一種更復(fù)雜的策略是為A的每個可能值賦予一個概率。例如，給定一個布爾屬性A，如果結(jié)點n包含6個已知A=1和4個A=0的實例，那么A(x)=，而A(x)=。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例（fractional examples）的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進(jìn)一步細(xì)分。5 優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。缺點：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。 決策樹的剪枝通常在實際應(yīng)用中，直接生成的完全決策樹不能立即用于對未知樣本進(jìn)行分類。由于完全決策樹對訓(xùn)練樣本的特征描述得“過于精確”，無法實現(xiàn)對新樣本的合理分析，所以此時它不是一棵分析新數(shù)掘的最佳決策樹。一棵完全決策樹能準(zhǔn)確地反映訓(xùn)練集中數(shù)據(jù)特征，但因失去了一般代表性而無法用于對新數(shù)據(jù)的分類或預(yù)測，這種現(xiàn)象稱為“過適應(yīng)”。解決過適應(yīng)問題的主要方法是對決策樹進(jìn)行剪枝。剪枝(Pruning)方法的主要目的是去掉那些噪聲或異常數(shù)據(jù)，使決策樹具有更泛化能力。剪枝常采用統(tǒng)計度量，剪掉最不可靠的分枝，從而帶來較快的分類，提高樹獨立于測試數(shù)據(jù)進(jìn)行證確分類的能力。剪枝按其實施的時間分為兩種方法：事前修剪法和事后修剪法。（1）事前修剪法該方法通過提前停止樹的構(gòu)造而對樹“剪枝”，即通過在當(dāng)前節(jié)點上判斷是否需要繼續(xù)劃分該節(jié)點所含訓(xùn)練樣本集來實現(xiàn)。一旦停止，節(jié)點不再繼續(xù)分裂，當(dāng)前節(jié)點就成為一個葉節(jié)點。該葉節(jié)點中可能包含多個不同類別的訓(xùn)練樣本，由于該修剪是在分枝之前做出的，所以稱之為事前修剪。事前修剪法的優(yōu)點是在樹生成的同時進(jìn)行了剪枝，因而效率高，但是它可能剪去了某些有用但還沒生成的節(jié)點。常用的方法是設(shè)定決策樹的最大高度(層數(shù))來限制樹的生長。還有一種方法是設(shè)定每個節(jié)點必須包含的最少記錄數(shù)，當(dāng)節(jié)點中記錄的個數(shù)小于這個數(shù)值時就停止分割。然而，選擇一個適當(dāng)?shù)拈撝凳潜容^困難的，較高的閾值可能導(dǎo)致過分簡化的樹，而較低的閾值可能會導(dǎo)致多余樹枝無法修剪。（2）事后修剪法該方法是由完全生長的樹剪去分枝。通過刪除節(jié)點的分枝，剪掉樹節(jié)點。它在允許決策樹得到最充分生長的基礎(chǔ)上，再根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉節(jié)點或分枝。修剪后，被修剪的分枝節(jié)點就成為一個葉節(jié)點，并將其標(biāo)記為它所包含樣本中類別個數(shù)最多的類別。事后修剪是一邊修剪一邊檢驗的過程，一般規(guī)則是：當(dāng)樹建好之后，對每個內(nèi)部節(jié)點，首先計算該節(jié)點上的子樹被剪枝可能出現(xiàn)的錯誤率，然后，使用每個分枝的錯誤率，結(jié)合沿每個分枝觀察的權(quán)重評估，計算不對該節(jié)點剪枝的期望錯誤率。如果剪掉該節(jié)點能夠降低錯誤率，那么該節(jié)點的所有子節(jié)點就被剪掉，該節(jié)點成為葉節(jié)點。產(chǎn)生一組逐漸被剪枝的樹之后，使用一個獨立的測試集評估每棵樹的準(zhǔn)確率，就能得到具有最小期望錯誤率的決策樹。當(dāng)然也可以結(jié)合使用事前修剪和事后修剪，形成混合的修剪方法。事后修剪比事前修剪需要更多的計算時閫，但通常產(chǎn)生的決策樹更為可靠。 決策樹的建立決策樹的建立過程主要由兩個階段組成：第一階段，建樹階段。選取訓(xùn)練數(shù)據(jù)集進(jìn)行學(xué)習(xí)，導(dǎo)出決策樹。決策樹歸納的基本算法是貪心算法，它采用的是自項向下遞歸的各個擊破方式來構(gòu)建判定樹，算法概述如下。第二階段，剪枝階段。用測試數(shù)據(jù)集檢驗決策樹，如果所建立的決策樹不能正確回答所研究的問題，我們要對決策樹進(jìn)行剪枝以解決過分適應(yīng)數(shù)據(jù)問題，直到建立一棵正確的決策樹，目的是降低由于訓(xùn)練集的噪聲而產(chǎn)生的起伏。建立決策樹的算法可以被描述成一個遞歸的過程：首先，選擇訓(xùn)練樣本的一個屬性作為節(jié)點，對該屬性的每種可能的取值創(chuàng)建一個分枝，并據(jù)此將訓(xùn)練樣本劃分為幾個子集。然后，對每個分枝采取相同的方法，訓(xùn)練樣本是其父節(jié)點劃分的若干子集中的對應(yīng)于該分枝取值的那個樣本子集。當(dāng)以下情況出現(xiàn)時停止該節(jié)點分枝的分裂，并使其成為葉節(jié)點：(1)給定節(jié)點的所有訓(xùn)練樣本屬于同一類(2)沒有剩余屬性可以用來進(jìn)一步劃分樣本(3)該分枝沒有樣本。建立決策樹的算法如下：算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵判定樹。輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合attribute_jist。輸出：一棵判定樹。方法：(1)創(chuàng)建節(jié)點N；(2)If samples都在同一個類C then(3)返回N作為葉節(jié)點，以類C標(biāo)記：(4)If attribute_list為空。then(5)返回N作為葉節(jié)點，標(biāo)記為samples中最普通的類；(6)選擇attribute_list中具有最高信息增益的屬性test_attribute；(7)標(biāo)記節(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)加上一個樹葉，標(biāo)記為samples中最普通的類；(13)Else 加上一個由 Generate_decision_tree (s1，attribute_1ist_test_attribute)返回的節(jié)點。說明如下：決策樹開始時，作為一個單個結(jié)點(根節(jié)點)包含所有的訓(xùn)練樣本集。若一個節(jié)點的樣本均為同一類別，則該節(jié)點就成為葉節(jié)點并標(biāo)記為該類別。否則該算法將采用信息熵方法(信息增益)作為啟發(fā)信息來幫助選擇合適的屬性，以便將樣本分為若干子集。這個屬性就成為該節(jié)點的測試屬性。在算法中，所有屬性均為離散值，若有取連續(xù)值的屬性，就必須首先進(jìn)行離散化。一個測試屬性的每個值均對應(yīng)一個將要被創(chuàng)建的分枝，同時也對應(yīng)著一個被劃分的子集。算法遞歸使用上述各處理過程，針對所獲得的每個劃分均又獲得一個決策樹。若一個屬性一旦在某個節(jié)點出現(xiàn)，那它就不能再出現(xiàn)在該節(jié)點之后所產(chǎn)生的子樹節(jié)點中。算法遞歸操作停止的條件是：(1)一個節(jié)點的所有樣本均為同一類別。(2)若無屬性可用于當(dāng)?shù)臉颖炯@里用少數(shù)服從多數(shù)的原則，將當(dāng)前節(jié)點標(biāo)記成葉節(jié)點，并標(biāo)記為當(dāng)前所合樣本集中類別個數(shù)最多的類別。(3)沒有樣本滿足條件，則創(chuàng)建一個葉節(jié)點并將其標(biāo)記為當(dāng)前節(jié)點所含樣本集中類別個數(shù)最多的類別。