侯勛 方剛

(重慶三峽學院，重慶 404020)

1 概述

隨著科技的飛速發(fā)展，人類積累的數(shù)據(jù)也越來越多，以數(shù)字化儲存的數(shù)據(jù)信息量達到了一個十分龐大的地步，這些數(shù)據(jù)中也存在著大量有用的信息和知識。同時為了獲得這些信息和知識，數(shù)據(jù)挖掘技術被人們發(fā)現(xiàn)并應用，在短時間內就應用于各行各業(yè)[1]。

決策樹算法是應用最為廣泛的數(shù)據(jù)挖掘算法之一[2]，它易于理解和解釋。而在決策樹算法中，ID3[3]算法是最具影響力和獨特地位的算法，之后的許多決策樹算法都是由之延伸而來。但是作為基礎的決策樹算法，ID3算法也存在許多不足之處。ID3算法在分類過程中存在多值傾向問題，且它是貪心算法，存在著局部最優(yōu)問題。因此本文提出一種ID3的改進，在計算信息增益時引入修正函數(shù)以達到屬性的信息增益修正的目的，解決多值偏向問題[4]。并利用遺傳算法對決策樹算法進行優(yōu)化[5]，能有效的解決ID3算法面對的問題。

2 ID3 算法概念及改進原理

2.1 ID3算法概念

ID3算法的核心思想是以信息增益值作為屬性選擇度量，將具有最大增益值的屬性作為最優(yōu)分裂屬性，對屬性進行分類[6]。

信息增益指的是劃分前后熵的變化，可以用下面的公式表示：

其中，A表示樣本的屬性，Value(A)是屬性A所有的取值集合。V是A的其中一個屬性值，SV是S中A的值為V的樣例集合。

熵的公式可以表示為：

2.2 肯德爾等級相關系數(shù)

肯德爾等級相關系數(shù)的定義為：設X、Y兩個集合的元素個數(shù)均為N，兩個隨即變量取的第i（1<=i<=N）個值分別用Xi、Yi表示。X與Y中的對應元素組成一個元素對集合XY，其包含的元素為(Xi,Yi)（1<=i<=N）。當集合XY中任意兩個元素(Xi,Yi)與(Xj,Yj)滿足Xi>Xj且Yi>Yj或XiXj且YiYj時這兩個元素被認為是逆序對。當出現(xiàn)Xi=Xj或Yi=Yj時，這兩個元素既不是同序的也不是逆序的[7]。

其計算方式如下所示：

(1)當集合中不存在Xi=Xj或Yi=Yj的情況時；

其中C表示XY中擁有的同序對元素對數(shù)；D表示XY中擁有的逆序對元素對數(shù)。

(2)當集合中存在Xi=Xj或Yi=Yj的情況時；

將X，Y中的相同元素分別組合成小集合，ti(或ui)表示X(或Y)中第i個小集合所包含的元素數(shù)。

τ的取值范圍在-1到1之間，當τ為1時，表示兩個隨機變量擁有一致的等級相關性；當τ為-1時，表示兩個隨機變量擁有完全相反的等級相關性；當τ為0時，表示兩個隨機變量是相互獨立的[8]。

2.3 基于肯德爾等級相關系數(shù)的ID3算法實現(xiàn)

若訓練集A是由n個條件屬性X和一個決策屬性Y構成，我們可以把n個條件屬性看成是隨機變量，表示為Xp(p=1,2,…,n)，決策屬性可以看成是隨機變量Y[5]。

令x,y是抽自兩個不同總體X,Y的樣本，其觀察值表示為x1,x2,x3,…,xn和y1,y2，…，yn,將它們配對成順序(x1,y1),(x2,y2),…,(xn,yn)。其中Xi,Yi的大小依據(jù)是用戶預先設定Y的排序以及X的排序。

例如Y內包含數(shù)據(jù)有兩個值，則設定其為1和2，y1值為1，y2值為2則y1

ID3的改進算法在ID3算法公式(2)的基礎上引入系數(shù)θ。公式定義如下：

運用公式(6)計算每個屬性的Gain(S,A)，把Gain(S,A)最大的屬性設為決策樹的劃分節(jié)點，然后不斷重復以上的過程得到最終的決策樹。

3 實驗和分析

3.1 實例分析

根據(jù)一個實例對上述的優(yōu)化算法進行比較分析。在這里我們選擇西瓜數(shù)據(jù)集進行分析。其中訓練樣本實例如表1所示。

表1 訓練集樣本實例

通過計算我們可知，西瓜數(shù)據(jù)集信息熵為:

同理可計算得：Gain（根蒂）=0.143 ；Gain敲聲）=0.141 ；Gain紋理）=0.381 ；Gain臍部）=0.289 ；Gain觸感）=0.006 。

對訓練集進行等級數(shù)字化之后，由肯德爾相關系數(shù)計算公式可得：τ（色澤）=0.20 ，τ根蒂）=0.34 ，τ敲聲）=0.34 ，τ紋理）=0.63 ，τ臍部）=0.50 ，τ觸感）=0.09 。將求得的系數(shù)帶入ID3算法中可得到改進后的信息增益為：Gain色澤）=0.109 ×1-|τ（色澤）|）=0.0872 ；Gain根蒂）=0.143 ×1-|τ（根蒂）|）=0.0944 ；Gain敲聲）=0.141 ×1-|τ（敲聲）|）=0.0931 ；Gain紋理）=0.381 ×1-|τ（紋理）|）=0.1410 ；Gain臍部）=0.289 ×1-|τ（臍部）|）=0.1445 ；Gain觸感）=0.006 ×1-|τ（觸感）|）=0.0055 。由于Gain臍部）>Gain（紋理）>Gain（根蒂）>Gain（敲聲）>Gain(色澤)>Gain（觸感）。臍部屬性的值最大，所以我們選擇臍部屬性作為劃分該決策樹的根節(jié)點，然后不斷重復以上的過程得到最終的決策樹。通過與ID3得出的信息增益進行比較，乘以相關系數(shù)使得結果得到了一定的修正，避免了偏向屬性個數(shù)過多的情況。

3.2 實驗結果驗證

為了驗證改進算法的有效性，引入UCI數(shù)據(jù)集中的若干數(shù)據(jù)在weka平臺上進行仿真驗證。實驗結果如圖1所示。

圖1 準確率對比

通過實驗結果的對比，可以看出改進后的算法的準確率要明顯優(yōu)于原算法。能夠幫助我們更好的對數(shù)據(jù)進行決策樹分類。

結束語

本文通過利用肯德爾等級相關系數(shù)的知識對傳統(tǒng)的ID3算法進行了優(yōu)化改進，并且通過實驗證明了改進的算法在一定程度上提升了算法的準確率。