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