一種基于動態屬性權值的ID3算法改進

武文廷

摘要：該文對決策樹ID3算法進行分析，針對原有ID3算法的不足之處做了一些改進，一是ID3算法多值偏差的缺點，對每個屬性的信息熵引入了一個動態屬性權值，使信息增益的計算結果不太依賴于屬性的取值個數，且避免了類似用戶興趣度之類改進的主觀性，二是對改進的基于屬性權值的ID3算法在解決學生職業發展分析問題上進行可行性和有效性驗證。

關鍵詞：數據挖掘；決策樹算法；ID3算法；算法改進

中圖分類號：TP302 文獻標識碼：A 文章編號：1009-3044（2019）06-0223-03

決策樹是一種基于策略選擇的樹型結構圖，該圖表示著屬性和值之間的映射關系。每個節點表示著一個對象，對象的屬性值則由每個分支路徑表示[1]，作為非常重要的人工智能技術，在分類問題上十分常用。

決策樹算法類型較多，但最有影響力的當屬ID3（IterativeDiehotomieversion3）算法，即迭代二叉樹生成算法3代。ID3算法的優點是通過信息增益來選擇分類屬性，更加的簡單直觀，分類的效率也較高。但也暴露出一些問題，信息增益的計算依賴于特征數目較多的特征，然而屬性取值較多的那個特征不一定是全部特征中最佳的。

1 ID3算法原理

ID3算法是一種基于Occam的剃刀原理的決策樹算法。它使用盡可能少的工具去做更多的事，常用于構建決策樹。決策樹中每個非葉子節點都對應于一個屬性，分支節點用來表示屬性值；葉子節點表示與從根到葉子節點的路徑相對應的類型屬性的值；每個非葉子節點將與屬性中信息量最豐富的特征屬性相關聯，用信息熵的減少率是做選擇測試屬性的標準，即選擇具有最高信息增益但尚未用于將節點作為劃分屬性的標準，然后該過程繼續，直到生成的決策樹能夠對訓練樣本完全進行分類。

ID3算法的重點思想是通過信息增益來測量屬性的選擇，并在分割后選擇其信息增益值最大的屬性。該算法使用自頂向下的貪心搜索來遍歷可能的決策范圍。系統越有序，信息的熵值就越低，不然，系統越是混亂，其熵則高。因此，信息熵可以被視為系統順序的度量。

ID3算法通過特征差異構造子節點；遞歸調用子節點上構造的決策樹；在所有特征的信息增益很小或者不能選擇任何特征之前，最終獲得決策樹。信息增益計算如下：

把信息增益當作是信息熵的減少值，在分類時，通過原公式和修改后的增益式（1）～式（6），計算每個屬性的增益，選取所有屬性中增益值是最大的屬性作為決策樹的根節點，屬性的不同值構成樹的不同分支。用與決策樹的根節點相同的方法計算該子集中的增益最大的屬性，遞歸直到每個數據集屬于相同的子集，迭代地生成決策樹。新數據遍歷此樹直到葉節點，從而完成對新數據的預測。

然而，修改后的增益具有以下限制：它可能不是總被定義（分母有可能為零），并且它可以選擇具有非常低IV（Ak）的屬性，而不是具有高增益的屬性。為了避免這種情況，Quinlan建議從那些初始（未修改）增益中與所有屬性的平均增益差不多一樣高的屬性中進行選擇應用增益比率。

2 ID3算法優缺點

從ID3算法的描述和原理中可以看出，ID3算法有以下優、缺點：

2.1 ID3算法的優點

（1）ID3算法使用了樣本集中的全部樣本，提高了分類決策的準確率，也降低了由于異常數據、噪聲數據所帶來的錯誤。

（2）ID3算法采用的是自上而下的分類策略，使得分類的時間復雜度較低。

（3）ID3算法非常適用于處理離散的數據，結果呈現分層樹結構，可以輕松提取“IF...Then...”分類規則，這個規則很容易理解。

2.2 ID3算法的缺點

（1）ID3算法在建樹的過程中，如果選擇了一個特征作為分類屬性，則不會選擇兩次，可能導致結果局部最優，但可能不是全局的最優選擇。

（2）ID3算法使用基于互信息的方法。此方法傾向于使用具有更多屬性值的屬性，即很容易傾向于多屬性值項，但具有最多屬性值的屬性不一定是最佳的屬性。

（3）ID3算法可以很好地處理離散化數據，但它卻對連續數據處理能力非常有限，因此在對連續數據分類之前，需要進行離散化處理。

總之，ID3算法簡單易于理解，很適合用于處理數據規模較大的問題，應用價值較大。

3 幾種現有的ID3算法的改進分析

ID3算法在信息增益的求解過程很容易受到多值依賴問題的影響，如果屬性需要很多值，那么它在分類中的作用將非常明顯，僅根據計算信息增益值來盲目地選取具有大量屬性的特征是不客觀的。針對此現象人們在傳統ID3算法的基礎上提出了不少改進方法，如引入了修正函數、屬性優先值等。

3.1 基于修正函數的算法

由文獻[2]可知，ID3算法所產生多值依賴的原因，是Gain（A）≥Gain（A）恒成立導致的，而多值依賴影響的改進就是破壞該平衡。文獻中首先將修正函數f（n）與原始計算的屬性增益相乘，并通過該修正函數對屬性的信息增益進行多值修正，使結果更加客觀。

由以式可以得出，由于算法中引入了修正函數[sin1n]和[sin1n+1]的作用.使得[GainA']≥[GainA]不再始終成立，當屬性的取值n>4時，通過修正函數的修正作用，降低了多值屬性的影響，使得計算信息增益的結果更為客觀。但是此方法當屬性的數量小于4時校正函數不起作用，因此沒有完全解決多值依賴問題。

3.2 基于固定的屬性優先值的改進算法

對于同一問題，在文獻[3]中引入屬性優先值。根據用戶以有經驗和應用需求，為屬性設置屬性優先值，從而影響決策樹生成過程。

對每個屬性Ai，定義其優先值為ai，使得滿足：

該方法加重了重要屬性對分類產生的影響，在生成決策樹過程中屬性值個數較小的屬性會被放大而不被忽略。但該方法的屬性優先值的概念中用戶主觀因素過多，可能會影響決策樹的準確性。

4 一種新的基于動態屬性權值的改進ID3算法

對于決策樹中ID3算法的缺點，本文依賴于具有更多屬性值的屬性和用于計算信息增益的數學公式的特征，引入動態的屬性權值，對ID3算法進一步優化改進，并使增益計算輕量化。

4.1 引入動態屬性權值函數

譬如，在學生就業情況分類預測中，其數據集來分類屬性的重要性相差不是太大，但屬性取值個數可能有較大差別[4]，因此本文中引入一個屬性權值ωi，用來減少因屬性取值個數較多的特征對模型分類結果所產生的較大影響。ωi用來在屬性重要性相差不大的情況下，減少取值數較多的屬性的分類權重，同時加大取值數較少的屬性的分類權重，以克服其多值依賴的不足。屬性權值參與計算來自動矯正分類屬性權重，該過程因無過的多人為參與度及干擾，從而避免了決策結果受用戶主觀思想的影響。

屬性值個數越多，經過公式計算所得屬性的權值則越小，一定程度上會抵消屬性多值偏向對決策結果帶來的影響。此公式在解決數據集中大量數據覆蓋了小量數據的重要程度方面具有一些優勢，解決了ID3算法多值依賴性的問題，且不會出現因用戶主觀因素過多造成影響決策樹的準確性的問題。

4.2 實驗驗證及分析

本文通過研究甘肅林業職業技術學院信息工程學院就業信息樣本集及相應屬性權值，計算結果如表1所示：

其對應的屬性權值曲線如圖1所示，不難看出，改進的基于屬性權值的ID3決策樹優化算法，該算法可以適當降低取值個數較多的屬性權重，且取值個數相差越大效果越明顯，克服了ID3算法多值依賴的影響，且規避了類似于用戶興趣度之類改進中因主觀權值參數而導致做出適用范圍不大、做出個人主觀性過強的決策的情況。

5 結語

本文對決策樹分類中的ID3算法相關理論做了詳細介紹，對比了兩個現有的ID3的改進算法，針對存在的不足，從兩個方面對ID3算法進行了改進優化，針對ID3算法多值偏向的缺點，對每個屬性的信息熵乘以動態屬性權值，使信息熵的結果不太依賴于屬性的取值個數，也避免了因采用類似用戶興趣度之類的主觀權值參數而導致做出不適合實際情況的決策。

參考文獻：

[1] 任天成.基于數據流的相似計算及其行為預測[D].南京郵電大學，2016.

[2] 韓松來，張輝，周華平.基于關聯度函數的決策樹分類算法[J].計算機應用，2005（11）：197-199.

[3] 盛俊.決策樹ID3算法的改進及其應用[J].揚州職業大學學報，2011（04）：38-40.

[4] 鄭碧嶷.基于數據挖掘技術的高校輔助決策系統設計與實現[D].北京工業大學，2014.

【通聯編輯：代影】