楊洋

摘 要：介紹了數(shù)據(jù)挖掘的相關(guān)概念，數(shù)據(jù)挖掘中決策樹(shù)ID3算法的相關(guān)概念以及信息增益和信息熵概念。通過(guò)實(shí)例介紹了ID3算法的主要內(nèi)容，指出了ID3算法的不足及改進(jìn)之處。針對(duì)該實(shí)例提出ID3算法的一種改進(jìn)算法——MIND算法，并通過(guò)MIND算法重新計(jì)算實(shí)例內(nèi)容。最后通過(guò)實(shí)例分析將改進(jìn)算法與ID3算法進(jìn)行對(duì)比，證明了改進(jìn)算法的有效性。

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

DOIDOI：10.11907/rjdk.161585

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2016）008-0046-03

0 引言

ID3算法屬于決策樹(shù)算法當(dāng)中的一種，它是通過(guò)把實(shí)例從根結(jié)點(diǎn)排列到某個(gè)葉子結(jié)點(diǎn)來(lái)對(duì)實(shí)例進(jìn)行分析，葉子結(jié)點(diǎn)即為實(shí)例所屬的分類(lèi)[1]。決策樹(shù)上的每一個(gè)結(jié)點(diǎn)就是對(duì)該實(shí)例某一個(gè)屬性的測(cè)試，并且該結(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)著該屬性的一個(gè)可能值。分類(lèi)從根節(jié)點(diǎn)開(kāi)始，對(duì)所有的實(shí)例通過(guò)所選屬性進(jìn)行分割，屬性的選擇采用最高信息增益法。停止分割的條件是：沒(méi)有屬性可以再對(duì)實(shí)例進(jìn)行分割，或者結(jié)點(diǎn)上的實(shí)例都屬于同一目標(biāo)屬性類(lèi)別。ID3算法主要針對(duì)屬性選擇問(wèn)題，是決策樹(shù)學(xué)習(xí)方法中最為典型的算法，該方法使用信息增益度選擇測(cè)試屬性。

MIND算法可以作為ID3算法的一種改進(jìn)算法，其算法思想更方便考慮每一個(gè)概化數(shù)據(jù)元組。MIND算法是一種典型的決策樹(shù)構(gòu)造方法的構(gòu)造分類(lèi)器，是采用數(shù)據(jù)庫(kù)中用戶(hù)定義的函數(shù)UDF發(fā)現(xiàn)分類(lèi)規(guī)則的算法，也就是在決策樹(shù)的每一層，為每個(gè)屬性建立一張維度表，用來(lái)存放各個(gè)屬性的取值屬于哪個(gè)類(lèi)別及結(jié)點(diǎn)編號(hào)，其優(yōu)點(diǎn)是通過(guò)采用UDF實(shí)現(xiàn)決策樹(shù)的構(gòu)造過(guò)程使得分類(lèi)算法易于與數(shù)據(jù)庫(kù)系統(tǒng)集成。

1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘這個(gè)概念于1989年提出 [2]，指從大量模糊的、有噪聲的、不完全的、隨機(jī)的數(shù)據(jù)中挖掘出有價(jià)值的信息。隨著信息技術(shù)的發(fā)展，大數(shù)據(jù)技術(shù)廣泛應(yīng)用，數(shù)據(jù)挖掘發(fā)揮著越來(lái)越重要的作用。在數(shù)據(jù)挖掘中人們對(duì) “啤酒與尿布”的經(jīng)典案例津津樂(lè)道：在美國(guó)超市，研究人員發(fā)現(xiàn)啤酒和尿布的銷(xiāo)量總成某種特殊的關(guān)聯(lián)關(guān)系，原來(lái)當(dāng)父親來(lái)到超市給孩子買(mǎi)尿布時(shí)，總會(huì)捎帶啤酒。根據(jù)這個(gè)發(fā)現(xiàn)，超市工作人員特意將啤酒和尿布這兩個(gè)看似毫不相干的商品擺放在一起，于是這兩種商品的銷(xiāo)量增大，為超市帶來(lái)可觀收益。這個(gè)小小例子足以說(shuō)明數(shù)據(jù)挖掘的重要性。

數(shù)據(jù)挖掘遵循一定步驟：首先要確定業(yè)務(wù)對(duì)象，然后是數(shù)據(jù)準(zhǔn)備工作，在數(shù)據(jù)準(zhǔn)備工作中有數(shù)據(jù)選擇、數(shù)據(jù)預(yù)處理、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘、結(jié)果分析和知識(shí)同化這些步驟，如圖1所示。

2 決策樹(shù)ID3算法基本原理

2.1 信息增益與信息熵概念

信息增益和信息熵是ID3算法中最重要的兩個(gè)概念，簡(jiǎn)單來(lái)說(shuō)，在ID3算法中，信息增益最大的節(jié)點(diǎn)屬性作為劃分標(biāo)準(zhǔn)，信息熵是當(dāng)獲取信息時(shí)，將不確定的內(nèi)容轉(zhuǎn)為確定內(nèi)容，因此信息伴著不確定性，分別有以下數(shù)學(xué)定義：

其中，Gain值越大，說(shuō)明選擇測(cè)試屬性對(duì)分類(lèi)提供的信息越多。

信息熵：已知隨機(jī)樣本的集合T中的樣本個(gè)數(shù)為a，有n個(gè)互不相同的值為類(lèi)別屬性，即可得到n個(gè)類(lèi)別 Mi （i=1，2，…，n）。假設(shè)Mi的樣本個(gè)數(shù)為ai，則某一樣本分類(lèi)需要的數(shù)學(xué)期望為：

在上述公式中，pi為樣本集合中Mi的概率值，可以用aia計(jì)算得出，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位，通常取2。

2.2 ID3算法實(shí)現(xiàn)

下面給出一個(gè)實(shí)例。表1是不同年齡、收入、性別的人群對(duì)于買(mǎi)車(chē)或者不買(mǎi)車(chē)的一個(gè)訓(xùn)練數(shù)據(jù)集。

對(duì)于給定的行，類(lèi)標(biāo)號(hào)屬性為買(mǎi)車(chē)，計(jì)數(shù)表示年齡、收入、性別在該行上具有給定值的元組數(shù)。首先計(jì)算決策屬性的熵，根據(jù)信息增益與信息熵的公式可知，設(shè)買(mǎi)車(chē)的人數(shù)為S1，不買(mǎi)車(chē)的人數(shù)為S2，P1為樣本中買(mǎi)車(chē)的概率值，P2為樣本中不買(mǎi)車(chē)的概率值，總?cè)藬?shù)為148，可知

S1=94，S2=54

P1=94/148，P2=54/148I（S1，S2）=I（94，54）=-P1log2P1-P2log2P2=0.9388

條件屬性一共有3個(gè)，年齡、收入、性別，分別計(jì)算這3個(gè)條件屬性的信息增益，以計(jì)算年齡的信息熵與信息增益為例。年齡分青年、中年、老年3個(gè)組。青年買(mǎi)的人數(shù)為22，所占比例為22/38，不買(mǎi)的人數(shù)為16，所占比例為16/38，則青年的信息熵為-0.58log20.58-0.42log20.42=0.9832。同理可得中年的信息熵為0.971，老年的信息熵為0.242。

青年所占整體人數(shù)比重為38/148=0.26，中年所占整體人數(shù)的比重為60/148=0.41，老年所占整體人數(shù)的比重為50/148=0.33。

則年齡的平均期望為：

E（年齡）=0.26*0.9832+0.41*0.971+0.33*0.242=0.7336

年齡的信息增益為：

G（年齡）=0.9388-0.7336=0.2052

同理可算出收入的信息增益為0.6628，性別的信息增益為0.3858，可知收入的信息增益是最大的，因此選擇性別為決策樹(shù)的根結(jié)點(diǎn)，如圖2所示。

找到了根結(jié)點(diǎn)后，其它葉子結(jié)點(diǎn)的尋找過(guò)程與根結(jié)點(diǎn)的尋找過(guò)程一樣。

3 決策樹(shù)ID3算法的改進(jìn)算法

3.1 ID3算法的不足

雖然ID3算法理解簡(jiǎn)單，使用方便，適用于處理大規(guī)模的學(xué)習(xí)問(wèn)題，但是ID3算法并不適應(yīng)所有的數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)問(wèn)題， ID3算法效率較低。下面歸納出ID3算法的不足之處：

（1） 因?yàn)镮D3算法為一種貪心算法，即在對(duì)問(wèn)題求解時(shí)，總是做出目前狀況下的最好選擇。換句話(huà)說(shuō)，在算法過(guò)程中，不從整體最優(yōu)上加以考慮，算法選擇只是某種意義上的局部最優(yōu)解。因此，ID3算法的決策樹(shù)搜索是無(wú)回溯的，很有可能在得到局部最優(yōu)解后丟失了全局最優(yōu)解。

（2） ID3算法只能處理離散屬性，對(duì)于連續(xù)值的屬性，必須首先對(duì)其進(jìn)行離散化處理才能投入使用。比如年齡屬性就是一個(gè)連續(xù)值屬性，在ID3算法中對(duì)這種連續(xù)值屬性是無(wú)法進(jìn)行計(jì)算的，必須先將年齡屬性離散化才能進(jìn)行下一步計(jì)算。

（3） ID3的決策樹(shù)計(jì)算中，每個(gè)葉子節(jié)點(diǎn)都必須要有屬性值才能進(jìn)行計(jì)算，但是并不是每個(gè)節(jié)點(diǎn)都必須擁有屬性值，如果樣本的某個(gè)屬性缺少對(duì)應(yīng)的屬性值，那么ID3算法計(jì)算將無(wú)法繼續(xù)，只能對(duì)缺省值進(jìn)行賦值才能繼續(xù)計(jì)算。

3.2 ID3改進(jìn)算法實(shí)現(xiàn)

由ID3算法可知，生成決策樹(shù)的關(guān)鍵是找到根結(jié)點(diǎn)，ID3算法是計(jì)算各個(gè)屬性的信息熵和信息增益來(lái)尋找根結(jié)點(diǎn)的。下面介紹ID3算法的一種改進(jìn)算法——MIND算法，通過(guò)計(jì)算各個(gè)屬性的基尼系數(shù)來(lái)尋找到根結(jié)點(diǎn)以及葉子結(jié)點(diǎn)。

基尼系數(shù)或譯堅(jiān)尼系數(shù)，是20世紀(jì)初由意大利經(jīng)濟(jì)學(xué)家基尼根據(jù)勞倫斯曲線(xiàn)所定義的判斷收入分配公平程度的指標(biāo)。 基尼系數(shù)是一個(gè)比例數(shù)值，在0和1之間，是國(guó)際上用來(lái)綜合考察居民內(nèi)部收入分配差異狀況的一個(gè)重要指標(biāo)。我們可以利用基尼系數(shù)的思想來(lái)計(jì)算屬性的分配程度，從而選擇決策樹(shù)的根結(jié)點(diǎn)。

MIND算法具體操作：將各個(gè)屬性按類(lèi)別分成不同的小樹(shù)。

因?yàn)橘I(mǎi)/不買(mǎi)為類(lèi)標(biāo)號(hào)屬性，因此令S1（買(mǎi)）=94，S2（不買(mǎi)）=54。

計(jì)算年齡屬性的基尼系數(shù)，已知青年中買(mǎi)的人數(shù)為22，不買(mǎi)的人數(shù)為16，因此記為青（22，16），中年中買(mǎi)的人數(shù)為24，不買(mǎi)的人數(shù)為36，因此記為中（24，36），老年中買(mǎi)的人數(shù)為48，不買(mǎi)的人數(shù)為2，因此記為老（48，2）。

Gini（青）=1-[（2238）2+（1638）2]=0.488

Gini（中）=1-[（2460）2+（3660）2]=0.48

Gini（老）=1-[（4850）2+（250）2]=0.0768

由上式可知，年齡屬性的基尼系數(shù)為

Gini（年齡）=38148×0.488+60148×0.48+50148×0.0768=0.346

計(jì)算收入屬性的基尼系數(shù)：已知低收入中買(mǎi)的人數(shù)為2，不買(mǎi)的人數(shù)為34，因此記為低（2，34）；中收入中買(mǎi)的人數(shù)為12，不買(mǎi)的人數(shù)為20，因此記為中（12，20）；高收入中買(mǎi)的人數(shù)為80，不買(mǎi)的人數(shù)為0，因此記為高（80，0）。計(jì)算得：Gini（低）=0.105，Gini（中）=0.469，Gini（高）=0，Gini（收入）=0.127。

計(jì)算性別屬性的基尼系數(shù)：已知男性中買(mǎi)的人數(shù)為50，不買(mǎi)的人數(shù)為34，因此記為男（50，34）；女性中買(mǎi)的人數(shù)為44，不買(mǎi)的人數(shù)為20，因此記為女（44，20）。計(jì)算得：Gini（男）=0.482，Gini（女）=0.43，Gini（性別）=0.46。

由上述計(jì)算可知，收入的基尼系數(shù)是最小的，因此選擇收入作為決策樹(shù)的根結(jié)點(diǎn)，這個(gè)結(jié)論與ID3算法一樣。根結(jié)點(diǎn)決策樹(shù)與圖2一致。

4 結(jié)語(yǔ)

本文利用一種新的MIND算法對(duì)ID3算法進(jìn)行改進(jìn)，從而實(shí)現(xiàn)尋找到?jīng)Q策樹(shù)根結(jié)點(diǎn)的簡(jiǎn)便計(jì)算方法。新算法引入基尼系數(shù)概念，可以適當(dāng)減少非重要屬性的信息量，相應(yīng)減少I(mǎi)D3算法對(duì)取值較多的屬性依賴(lài)性，使整個(gè)運(yùn)算更加獨(dú)立，從而改善分類(lèi)規(guī)則和結(jié)果。

參考文獻(xiàn)：

[1]譚建豪，章兢，黃耀，等. 數(shù)據(jù)挖掘技術(shù)[M].北京：中國(guó)水利水電出版社，2009：16-148.

[2]DAVIDSON IAN，TAYI GIRI. Data preparation using data quality matrices for classification mining[J]. European Journal of Operational Research，2009， 197（2）：764-772.

[3]朱付寶，霍曉齊，徐顯景. 基于粗糙集的ID3決策樹(shù)算法改進(jìn)[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)：自然科學(xué)版，2015，30（1）：50-54.

[4]王小巍，蔣玉明.決策樹(shù)ID3算法的分析與改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（9）：3070-3072.

（責(zé)任編輯：杜能鋼）