基于肯德爾系數(shù)的改進(jìn)ID3算法

侯勛 方剛

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

1 概述

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

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

2 ID3 算法概念及改進(jìn)原理

2.1 ID3算法概念

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

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

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

熵的公式可以表示為：

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

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

其計(jì)算方式如下所示：

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

其中C表示XY中擁有的同序?qū)υ貙?shù)；D表示XY中擁有的逆序?qū)υ貙?shù)。

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

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

τ的取值范圍在-1到1之間，當(dāng)τ為1時(shí)，表示兩個(gè)隨機(jī)變量擁有一致的等級相關(guān)性；當(dāng)τ為-1時(shí)，表示兩個(gè)隨機(jī)變量擁有完全相反的等級相關(guān)性；當(dāng)τ為0時(shí)，表示兩個(gè)隨機(jī)變量是相互獨(dú)立的[8]。

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

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

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

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

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

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

3 實(shí)驗(yàn)和分析

3.1 實(shí)例分析

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

表1 訓(xùn)練集樣本實(shí)例

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

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

對訓(xùn)練集進(jìn)行等級數(shù)字化之后，由肯德爾相關(guān)系數(shù)計(jì)算公式可得：τ（色澤）=0.20 ，τ根蒂）=0.34 ，τ敲聲）=0.34 ，τ紋理）=0.63 ，τ臍部）=0.50 ，τ觸感）=0.09 。將求得的系數(shù)帶入ID3算法中可得到改進(jìn)后的信息增益為：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é)點(diǎn)，然后不斷重復(fù)以上的過程得到最終的決策樹。通過與ID3得出的信息增益進(jìn)行比較，乘以相關(guān)系數(shù)使得結(jié)果得到了一定的修正，避免了偏向?qū)傩詡€(gè)數(shù)過多的情況。

3.2 實(shí)驗(yàn)結(jié)果驗(yàn)證

為了驗(yàn)證改進(jìn)算法的有效性，引入U(xiǎn)CI數(shù)據(jù)集中的若干數(shù)據(jù)在weka平臺(tái)上進(jìn)行仿真驗(yàn)證。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 準(zhǔn)確率對比

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

結(jié)束語

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