摘  要： 重點研究了經典的、具有較大影響力的決策樹分類算法——ID3算法，并對其性能優(yōu)劣作了比較分析。就ID3算法兩個較為明顯的缺陷進行了探討，提出了優(yōu)化算法。
關鍵詞： 數據挖掘；分類；決策樹；信息增益

    分類是一種非常重要的數據挖掘方法，也是數據挖掘領域中被廣泛研究的課題。決策樹分類方法是一種重要的分類方法，它是以信息論為基礎對數據進行分類的一種數據挖掘方法。決策樹生成后成為一個類似流程圖的樹形結構，其中樹的每個內部結點代表一個屬性的測試，分枝代表測試結果，葉結點則代表一個類或類的分布，最終可生成一組規(guī)則。相對其他數據挖掘方法而言，決策樹分類方法因簡單、直觀、準確率高且應用價值高等優(yōu)點在數據挖掘及數據分析中得到了廣泛應用。
1 決策樹分類過程
    決策樹的分類過程也就是決策樹分類模型(簡稱決策樹)的生成過程，如圖1所示。從圖中可知決策樹分類的建立過程與用決策樹分類模型進行預測的過程實際上是一種歸納-演繹過程。其中，由已分類數據得到決策樹分類模型的過程稱歸納過程，用決策樹分類模型對未分類數據進行分類的過程稱為演繹過程。需要強調的是：由訓練集得到分類模型必須經過測試集測試達到一定要求才能用于預測。

  
    信息增益是不確定性的消除，也就是接收端所獲得的信息量。
2.2 ID3算法多值偏向性分析
    首先，設A是某訓練樣本集的一個屬性，它的取值為A1，A2，…，An，創(chuàng)建另外一個新屬性A′，它與屬性A唯一的區(qū)別：其中一個已知值An分解為兩個值A′n和A′n+1，其余值和A中的完全一樣，假設原來n個值已經提供足夠的信息使分類正確進行，很明顯，則屬性A′相對于A沒有任何作用。但如果按照Qulnina的標準，屬性A′應當優(yōu)先于屬性A選取。
    綜上所知，把ID3算法分別作用在屬性A和屬性A′上，如果屬性選取標準在屬性A′上的取值恒大于在屬性A上的取值，則說明該算法在建樹過程中具有多值偏向；如果屬性選取標準在屬性A′上的取值與在屬性A上的取值沒有確定的大小關系，則說明該決策樹算法在建樹過程中不具有多值偏向性。
2.3 ID3算法的缺點
    (1)ID3算法往往偏向于選擇取值較多的屬性，而在很多情況下取值較多的屬性并不總是最重要的屬性，即按照使熵值最小的原則被ID3算法列為應該首先判斷的屬性在現實情況中卻并不一定非常重要。例如:在銀行客戶分析中，姓名屬性取值多，卻不能從中得到任何信息。
    (2)ID3算法不能處理具有連續(xù)值的屬性，也不能處理具有缺失數據的屬性。
    (3)用互信息作為選擇屬性的標準存在一個假設，即訓練子集中的正、反例的比例應與實際問題領域中正、反例的比例一致。一般情況很難保證這兩者的比例一致，這樣計算訓練集的互信息就會存在偏差。
    (4)在建造決策樹時，每個結點僅含一個屬性，是一種單變元的算法，致使生成的決策樹結點之間的相關性不夠強。雖然在一棵樹上連在一起，但聯(lián)系還是松散的。
    (5)ID3算法雖然理論清晰，但計算比較復雜，在學習和訓練數據集的過程中機器內存占用率比較大，耗費資源。
    決策樹ID3算法是一個很有實用價值的示例學習算法，它的基礎理論清晰，算法比較簡單，學習能力較強，適于處理大規(guī)模的學習問題，是數據挖掘和知識發(fā)現領域中的一個很好的范例，為后來各學者提出優(yōu)化算法奠定了理論基礎。表1是一個經典的訓練集。
     由ID3算法遞歸建樹得到一棵決策樹如圖2所示。

3 ID3算法優(yōu)化的探討
    ID3算法在選擇分裂屬性時，往往偏向于選擇取值較多的屬性，然而在很多情況下取值較多的屬性并不總是最重要的屬性，這會造成生成的決策樹的預測結果與實際偏離較大，針對這一弊端，本文提出以下改進思路：
    (1)引入分支信息熵的概念。對于所有屬性，任取屬性Ａ，計算Ａ屬性的各分支子集的信息熵，在每個分支子集中找出最小信息熵，并計算其和，比較大小，選擇其最小值作為待選擇的最優(yōu)屬性。
    (2)引入屬性優(yōu)先的概念。不同的屬性對于分類或決策有著不同的重要程度，這種重要程度可在輔助知識的基礎上事先加以假設，給每個屬性都賦予一個權值，其大小為(0，1)中的某個值。通過屬性優(yōu)先法，降低非重要屬性的標注，提高重要屬性的標注。
4 實例分析
    仍以表1為例，分別計算其H(A)的值。在此通過反復測試，天氣的屬性優(yōu)先權值為0.95，風的屬性優(yōu)先權值為0.35，其余兩個的屬性優(yōu)先權值都為0。

(1)確定根結點
    選取天氣屬性作為測試屬性，天氣為多云時，信息熵為：
 
    根據算法步驟(6)，選擇值H(A)為最小的作為候選屬性，所以此時應選擇濕度作為根結點。在24個訓練集中對濕度的2個取值進行分枝，2個分枝對應2個子集，分別為：

    通過比較ID3算法和本文所提出的組合優(yōu)化算法所生成的決策樹可知，組合優(yōu)化算法的改進為：
    (1)從本實例所生成的決策樹的形態(tài)來看，改進后的算法生成的是一棵二叉樹，而ID3算法生成的是多叉樹，簡化了決策問題處理的復雜度。
    (2)引入了分支信息熵和屬性優(yōu)先的概念，用條件熵、分支信息熵與屬性優(yōu)先三者相結合來選擇分裂屬性。從本實例來看，根結點選擇濕度而未選擇屬性值最多的天氣，所以本優(yōu)化算法確實能克服傳統(tǒng)ID3算法的多值偏向性。
參考文獻
[1] 安淑芝.數據倉庫與數據挖掘[M].北京：清華大學出版社，2005：104-107.
[2] 史忠植.知識發(fā)現[M].北京：清華大學出版社，2002：23-37.
[3] 徐潔磐.數據倉庫與決策支持系統(tǒng)[M].北京：科學出版社，2005：77-86.
[4] 路紅梅.基于決策樹的經典算法綜述[J].宿州學院學報，2007(4)：91-95.
[5] 韓慧.數據挖掘中決策樹算法的最新進展[J].計算機應用研究，2004(12)：5-8.
[6] KANTARDZIC M. Data mining concepts， models， methods， and algorithms[M]. 北京：清華大學出版社，2003：120-136.
[7] OLARU C， WEHENKEL L. A complete fuzzy decision tree technique[J]. Fuzzy Sets and Systems， 2003，138(2)：221-254.
[8] AITKENHEAD M J. Aco-evolving decision tree classification method[J]. Expert System with Application，  2008(34)：18-25.
[9] Norio Takeoka. Subjective probability over a subjective decision tree[J]. Journal of Economic Theory， 2007(136):536-571.