武文廷
摘要:該文對決策樹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)編輯:代影】