一種基于動態(tài)屬性權(quán)值的ID3算法改進

武文廷

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

關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹算法；ID3算法；算法改進

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

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

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

1 ID3算法原理

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

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

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

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

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

2 ID3算法優(yōu)缺點

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

2.1 ID3算法的優(yōu)點

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

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

（3）ID3算法非常適用于處理離散的數(shù)據(jù)，結(jié)果呈現(xiàn)分層樹結(jié)構(gòu)，可以輕松提取“IF...Then...”分類規(guī)則，這個規(guī)則很容易理解。

2.2 ID3算法的缺點

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

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

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

總之，ID3算法簡單易于理解，很適合用于處理數(shù)據(jù)規(guī)模較大的問題，應(yīng)用價值較大。

3 幾種現(xiàn)有的ID3算法的改進分析

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

3.1 基于修正函數(shù)的算法

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

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

3.2 基于固定的屬性優(yōu)先值的改進算法

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

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

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

4 一種新的基于動態(tài)屬性權(quán)值的改進ID3算法

對于決策樹中ID3算法的缺點，本文依賴于具有更多屬性值的屬性和用于計算信息增益的數(shù)學(xué)公式的特征，引入動態(tài)的屬性權(quán)值，對ID3算法進一步優(yōu)化改進，并使增益計算輕量化。

4.1 引入動態(tài)屬性權(quán)值函數(shù)

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

屬性值個數(shù)越多，經(jīng)過公式計算所得屬性的權(quán)值則越小，一定程度上會抵消屬性多值偏向?qū)Q策結(jié)果帶來的影響。此公式在解決數(shù)據(jù)集中大量數(shù)據(jù)覆蓋了小量數(shù)據(jù)的重要程度方面具有一些優(yōu)勢，解決了ID3算法多值依賴性的問題，且不會出現(xiàn)因用戶主觀因素過多造成影響決策樹的準(zhǔn)確性的問題。

4.2 實驗驗證及分析

本文通過研究甘肅林業(yè)職業(yè)技術(shù)學(xué)院信息工程學(xué)院就業(yè)信息樣本集及相應(yīng)屬性權(quán)值，計算結(jié)果如表1所示：

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

5 結(jié)語

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

參考文獻：

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

[2] 韓松來，張輝，周華平.基于關(guān)聯(lián)度函數(shù)的決策樹分類算法[J].計算機應(yīng)用，2005（11）：197-199.

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

[4] 鄭碧嶷.基于數(shù)據(jù)挖掘技術(shù)的高校輔助決策系統(tǒng)設(shè)計與實現(xiàn)[D].北京工業(yè)大學(xué)，2014.

【通聯(lián)編輯：代影】