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

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

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

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

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

    通過比較ID3算法和本文所提出的組合優(yōu)化算法所生成的決策樹可知，組合優(yōu)化算法的改進為：
    (1)從本實例所生成的決策樹的形態(tài)來看，改進后的算法生成的是一棵二叉樹，而ID3算法生成的是多叉樹，簡化了決策問題處理的復(fù)雜度。
    (2)引入了分支信息熵和屬性優(yōu)先的概念，用條件熵、分支信息熵與屬性優(yōu)先三者相結(jié)合來選擇分裂屬性。從本實例來看，根結(jié)點選擇濕度而未選擇屬性值最多的天氣，所以本優(yōu)化算法確實能克服傳統(tǒng)ID3算法的多值偏向性。
參考文獻
[1] 安淑芝.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京：清華大學(xué)出版社，2005：104-107.
[2] 史忠植.知識發(fā)現(xiàn)[M].北京：清華大學(xué)出版社，2002：23-37.
[3] 徐潔磐.數(shù)據(jù)倉庫與決策支持系統(tǒng)[M].北京：科學(xué)出版社，2005：77-86.
[4] 路紅梅.基于決策樹的經(jīng)典算法綜述[J].宿州學(xué)院學(xué)報，2007(4)：91-95.
[5] 韓慧.數(shù)據(jù)挖掘中決策樹算法的最新進展[J].計算機應(yīng)用研究，2004(12)：5-8.
[6] KANTARDZIC M. Data mining concepts， models， methods， and algorithms[M]. 北京：清華大學(xué)出版社，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.