基于改進(jìn)ID3算法的數(shù)據(jù)分類方法

孟雅蕾，周千明，師紅宇，馬 楠

(1. 西安工程大學(xué)計算機(jī)科學(xué)學(xué)院，陜西 西安 710048；2. 中國石油長慶油田分公司物資裝備處，陜西 西安 710021)

1 引言

由Quinlan提出的ID3算法是目前最具有影響力的一種決策樹構(gòu)造算法。ID3算法由于理論清晰，方法簡單，學(xué)習(xí)能力強(qiáng)，常用于處理大規(guī)模的學(xué)習(xí)問題，是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中一個極好的范例，也是一種知識獲取的有用工具[1]。

ID3算法雖是常用的分類算法，但在選擇屬性時存在屬性偏向的問題，偏向選擇取值較多的屬性作為分支節(jié)點[2]。針對ID3算法的多值偏向問題，許多學(xué)者進(jìn)行了相關(guān)的改進(jìn)工作：文獻(xiàn)[3]引進(jìn)屬性相似度和性價比值兩者對ID3算法進(jìn)行改進(jìn)；文獻(xiàn)[4]提出了一種基于斯皮爾曼等級相關(guān)系數(shù)的ID3決策樹構(gòu)造優(yōu)化算法，利用相關(guān)系數(shù)克服了ID3算法在多值屬性偏向方面的問題；文獻(xiàn)[5]利用屬性偏向?qū)D3算法進(jìn)行改進(jìn)，利用凸函數(shù)的性質(zhì)簡化了ID3算法中信息增益的計算；文獻(xiàn)[6] 在決策樹算法的節(jié)點中增加了貝葉斯分類算法作為預(yù)處理貝葉斯節(jié)點，形成增量學(xué)習(xí)決策樹，減少了決策樹的修剪時間。雖然多位學(xué)者改進(jìn)的ID3算法，在一定程度上克服了屬性偏向問題，但效率和速度低，不能用于增量模型。本文通過研究和學(xué)習(xí)相關(guān)的改進(jìn)算法，提出一種新的數(shù)據(jù)分類方法，該方法可以有效的控制屬性選擇時的多值偏向問題，提高預(yù)測的準(zhǔn)確率和算法的效率，用于增量模型。

2 ID3算法的改進(jìn)

ID3算法在生成相應(yīng)的決策樹時采用信息增益作為屬性選取的標(biāo)準(zhǔn)，根據(jù)拆分前后屬性信息增益的差值大小來判斷屬性的信息增益的變化，確定分支節(jié)點。

本文提出的數(shù)據(jù)分類方法通過對信息增益的修正和屬性偏向闕確定均衡系數(shù)，利用均衡系數(shù)對ID3算法得到的信息增益進(jìn)行優(yōu)化，得到優(yōu)化信息增益，根據(jù)優(yōu)化信息增益得到?jīng)Q策樹的根節(jié)點、各分支節(jié)點，對屬性進(jìn)行分類，構(gòu)建決策樹。信息增益的修正、屬性偏向闕、均衡系數(shù)、優(yōu)化信息增益的思想和論證如下文所示。

2.1 信息增益

根據(jù)ID3算法得到屬性Ai在訓(xùn)練集S上的條件熵E(Ai)、信息增益Gain(Ai)；

條件熵E(Ai)、信息增益Gain(Ai)的計算公式如下

(1)

(2)

Gain(Ai)=I-E(Ai)

(3)

2.2 信息增益的修正

對屬性Ai的信息增益Gain(Ai)進(jìn)行修正，得到修正信息增益Gain′(Ai)，其表達(dá)式如下：

Gain′(Ai)=f(n1)Gain(Ai)

(4)

2.3 屬性偏向闕

當(dāng)某個條件屬性的取值個數(shù)非常接近總數(shù)時，分裂信息度可能非常小或者為零，這會導(dǎo)致增益率修正補(bǔ)償過度。為避免這種情況，引入屬性偏向閾T，對多值偏向性的程度進(jìn)行度量和控制，對于集合S，有n2個條件屬性，屬性偏向閾T通常取值為所有條件熵E(Ai)的平均值，其表達(dá)式如下

(5)

其中，n2表示條件屬性的個數(shù)。

2.4 均衡系數(shù)

為了平衡多值偏向?qū)π畔⒃鲆娴挠绊懞托畔⒃鲆嫘拚a(bǔ)償過度，本文引入均衡系數(shù)的概念。均衡系數(shù)R(Ai)由修正信息增益Gain′(Ai)和屬性偏向閾T得到。通過修正參數(shù)修正后的信息增益和屬性偏向閾分別對應(yīng)電阻R1和R2，均衡系數(shù)對應(yīng)電阻R’，本方法的均衡系數(shù)R(Ai)是運(yùn)用等效電阻原理定義的。

在計算均衡系數(shù)R(Ai)之前，若屬性偏向閾T小于條件熵E(Ai)，令E(Ai)=T，重新計算信息增益Gain(Ai)、修正信息增益Gain′(Ai)；對屬性偏向閾T大于條件熵E(Ai)的屬性選擇信息增益Gain(Ai)進(jìn)行計算，這樣就有效避免了補(bǔ)償過度的情況。均衡系數(shù)R(Ai)公式如下：

(6)

即

(7)

均衡系數(shù)R(Ai)的作用效果，等效于修正后的信息增益Gain′(Ai)和屬性偏向閾T兩者共同作用的效果達(dá)到的最優(yōu)值。

2.5 優(yōu)化信息增益

利用均衡系數(shù)R(Ai)對信息增益Gain(Ai)進(jìn)行優(yōu)化，得到優(yōu)化信息增益Gain(Ai)new，根據(jù)優(yōu)化信息增益Gain(Ai)new得到?jīng)Q策樹的根節(jié)點，優(yōu)化信息增益Gain(Ai)new公式如下：

Gain(Ai)new=Gain(Ai)×R(Ai)

(8)

重復(fù)2.1-2.5，得到?jīng)Q策樹的各分支節(jié)點，對屬性Ai進(jìn)行分類。

通過本方法得到的優(yōu)化信息增益Gain(Ai)new，能避免多值偏向，證明如下：

(9)

由此可知式(9)的恒成立是造成多值偏向問題的本質(zhì)，所以要解決多值偏向問題只要避免式(9)恒成立即可。

(10)

3 算法實例

采用商務(wù)購車顧客數(shù)據(jù)庫(如表1所示)作為訓(xùn)練集，對數(shù)據(jù)進(jìn)行選取、預(yù)處理和轉(zhuǎn)換后得到樣本集合，該集合包含4個條件屬性；喜歡的季節(jié)(含4個屬性值：春、夏、秋、冬)、是否商務(wù)人士(含2個屬性值：是、否)、收入(含3個屬性值：高、中、低)、駕車水平(含2個屬性值：良好、一般)。樣本集合根據(jù)類別屬性“是否買車”(含有2個屬性值：買、不買)進(jìn)行劃分。

表1 數(shù)據(jù)訓(xùn)練集

利用本文提出的數(shù)據(jù)分類方法對訓(xùn)練集中的各個屬性進(jìn)行分類，具體過程如下：

步驟1：根據(jù)ID3算法得到各個屬性在訓(xùn)練集上的信息熵I、條件熵E(Ai)及信息增益Gain(Ai)：

步驟1.1：根據(jù)式(1)計算分類屬性“買車”的信息熵I。

根據(jù)上表可以看到，分類屬性“買車”共有11條記錄，其中7條記錄為“買”，4條記錄為“不買”，根據(jù)公式計算分類屬性“買車”的信息熵為

步驟1.2：根據(jù)式(2)計算各條件屬性的條件熵E(Ai)。

測試的訓(xùn)練集共有四個條件屬性“喜歡的季節(jié)”、“是否商務(wù)人士”、“收入”、和“駕車水平”。計算分兩個過程，首先計算出不同屬性值的條件熵，如“喜歡的季節(jié)”為“春”、“夏”、“秋”和“冬”，接著再計算整個屬性的條件熵。

屬性“喜歡的季節(jié)”包括四個屬性值“春”、“夏”、“秋”和“冬”，它們的條件熵分別為：

由“春”、“夏”、“秋”和“冬”的條件熵，可以求出屬性“喜歡的季節(jié)”的條件熵為

同理，可計算出E(是否商務(wù)人士)=0.796，E(收入)=0.5898，E(駕車水平)=0.796。

步驟1.3：根據(jù)式(3)計算各條件屬性的信息增益。

Gain(喜歡的季節(jié))=I(買車)-E(喜歡的季節(jié))=0.4，

Gain(是否商務(wù)人士)=I(買車)-E(是否商務(wù)人士)=0.149，

Gain(收入)=I(買車)-E(收入)=0.355，

Gain(駕車水平)=I(買車)-E(駕車水平)=0.149。

步驟2：根據(jù)式(4)對每個條件屬性的信息增益進(jìn)行修正，修正后的每個條件屬性的信息增益Gain′(Ai)為：

當(dāng)屬性為“喜歡的季節(jié)”時，包括四個決策屬性“春”、“夏”、“秋”和“冬”，則

當(dāng)屬性為“是否商務(wù)人士”時，包括兩個決策屬性“是”、“否”，則

當(dāng)屬性為“收入”時，包括三個決策屬性“高”、“中”及“低”，則

當(dāng)屬性為“駕車水平”時，包括兩個決策屬性“良好”、“一般”，則

步驟3：根據(jù)式(5)計算屬性偏向閾T，共有四個條件屬性，則：

步驟4：根據(jù)式(6)計算各條件屬性的均衡系數(shù)。

計算各條件屬性的均衡系數(shù)前，將每個條件屬性的屬性偏向閾T與條件熵進(jìn)行比較，對各屬性的信息增益進(jìn)行重新選擇。

當(dāng)屬性為“是否商務(wù)人士”時：E(是否商務(wù)人士)=0.796>T，令E(是否商務(wù)人士)=T，即E(是否商務(wù)人士)=0.682，重新利用步驟1、步驟2計算信息增益Gain(是否是商務(wù)人士)、修正信息增益Gain′(是否是商務(wù)人士)

Gain(是否是商務(wù)人士)=0.945-0.682=0.263，

同理，可計算出R(收入)=0.1，R(駕車水平)=0.11。

步驟5：根據(jù)式(8)計算各條件屬性的優(yōu)化信息增益Gain(Ai)new：

Gain(喜歡的季節(jié))new=0.4×0.087=0.035，

Gain(是否是商務(wù)人士)new=0.263×0.11=0.029，

Gain(收入)new=0.355×0.1=0.036，

Gain(駕車水平)new=0.263×0.11=0.029，

則根節(jié)點的屬性為“收入”。

完成了根節(jié)點的選擇后接下來重復(fù)上述步驟1-5選擇各內(nèi)部節(jié)點、葉節(jié)點(即各分支節(jié)點)，最終得到訓(xùn)練集的決策樹構(gòu)建如圖1所示。

圖1 改進(jìn)ID3算法決策樹圖

根據(jù)傳統(tǒng)ID3算法畫出的原始決策樹如圖2所示，比較圖1和圖2，從原始決策樹圖2第一層可以看出決策條件具有多值偏向性，屬性“喜歡的季節(jié)”屬性值個數(shù)最多，有 “春”、“夏”、“秋”、“冬”四個決策屬性，由于多值偏向使其成為決策樹的根節(jié)點，但“喜歡的季節(jié)”是一種主觀想法，并不是購車的決定性因素?，F(xiàn)實生活中，“收入”在一定程度上更能決定是否購車，由圖1可看出，本文提出的數(shù)據(jù)分類方法令“喜歡的季節(jié)”屬性離決策樹根結(jié)點的距離變遠(yuǎn)，降低其重要性；而“收入”屬性作為決策樹根結(jié)點，提高其重要性，符合實際情況。在傳統(tǒng)ID3算法構(gòu)建的決策樹的第二層，當(dāng)“是否商務(wù)人士”作為決策條件時，屬性值為“是”則“不買”，屬性值為“否”則“買”，這與實際情況是相違背的。而本文改進(jìn)的ID3算法構(gòu)建的決策樹的第二層，當(dāng)決策條件為“駕車水平”時，屬性值為“良好”則“買”，屬性值為“一般”則“不買”，這更符合現(xiàn)實情況。因此本文提出的數(shù)據(jù)分類方法不僅克服了多值偏向問題而且提升了算法的準(zhǔn)確性和實用性。

圖2 ID3算法決策樹圖

4 結(jié)束語

本文提出的基于改進(jìn)ID3算法的數(shù)據(jù)分類方法，通過修正信息增益，引入均衡系數(shù)、屬性偏向閾，實現(xiàn)對多值偏向程度的控制和度量，解決了現(xiàn)有ID3算法存在的多值偏向性問題，避免信息增益偏向取值較多的屬性，提高了預(yù)測的準(zhǔn)確率，降低了算法的運(yùn)行時間。