張永昭　岳晟　劉曉楠

摘 要 ID3、C4.5、CART是三種已經(jīng)研究發(fā)展很多年的經(jīng)典算法，是從事數(shù)據(jù)挖掘研究工作基礎(chǔ)模板。三種決策樹(shù)模型應(yīng)用廣泛，原理簡(jiǎn)明，各有所長(zhǎng)，但缺點(diǎn)同樣明顯。經(jīng)過(guò)深入的學(xué)習(xí)研究，團(tuán)隊(duì)對(duì)三種算法的特點(diǎn)及改進(jìn)進(jìn)行了匯總，為進(jìn)一步的研究做了總結(jié)性分析；并運(yùn)用分析成果對(duì)ID3算法進(jìn)行了改進(jìn)。

關(guān)鍵詞 數(shù)據(jù)挖掘；決策樹(shù)算法；特點(diǎn)；改進(jìn)；匯總

引言：

近年來(lái)，決策樹(shù)方法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)等領(lǐng)域得到了廣泛應(yīng)用。數(shù)據(jù)挖掘作為一種發(fā)現(xiàn)大量數(shù)據(jù)中潛在信息的數(shù)據(jù)分析方法和技術(shù)，已經(jīng)成為各界關(guān)注的熱點(diǎn)。其中，決策樹(shù)以其出色的數(shù)據(jù)分析效率、直觀易懂等特點(diǎn)，倍受青睞。構(gòu)造決策樹(shù)有多種算法，國(guó)際上最早的、具有影響力的決策樹(shù)是由Quinlan于1986年提出的ID3算法[1]，是基于信息熵的決策樹(shù)分類(lèi)算法。ID3算法采用信息熵作為屬性選擇標(biāo)準(zhǔn)，可這個(gè)標(biāo)準(zhǔn)易偏向于取值較多的候選屬性。

一、ID3算法優(yōu)化

1.改進(jìn)思路

針對(duì)ID3算法的缺點(diǎn)④，即信息增益的計(jì)算依賴于特征數(shù)目較多的特征，而屬性取值最多的屬性并不一定最優(yōu)，這會(huì)導(dǎo)致結(jié)果與實(shí)際誤差較大?；谏鲜鰧?duì)ID3算法改進(jìn)方案的分析，本文提出以下改進(jìn)思路：

（1）提出子屬性信息熵的概念。假設(shè)所有屬性集合為{A1，A2，…，An}，對(duì)于屬性Ai有子屬性{Ai1，Ai2， …， Aim}。定義Aij的子屬性信息熵為。

（2）引入屬性優(yōu)先[18]的概念。不同的屬性對(duì)決策的影響程度不同，這種影響程度可以在輔助知識(shí)的的基礎(chǔ)上事先加以假設(shè)，給每個(gè)屬性賦予一個(gè)權(quán)值{w1，w2，…，wn}，通過(guò)權(quán)值，弱化非重要屬性，強(qiáng)化重要屬性。

（3）引入屬性修正信息熵的概念，目的是弱化非重要多值屬性對(duì)信息增益的影響。假設(shè)所有屬性集合為{A1，A2，…，An}，每個(gè)屬性發(fā)生概率分別是{P1，P2，…，Pn}，對(duì)于屬性Ai每個(gè)子屬性發(fā)生的概率為{Pi1，Pi2，…，Pim}。定義屬性Ai的屬性修正信息熵為。

而entropy（Ai）采用ID3中的算法計(jì)算。

2.算法步驟

（1）對(duì)當(dāng)前例子集合，計(jì)算各個(gè)屬性的修正信息熵。

（2）選擇修正信息熵最小的屬性Ai作為根節(jié)點(diǎn)。

（3）把在Ai處取值相同的例子歸于同一子集，Ai取幾個(gè)值就得幾個(gè)子集。

（4）依次對(duì)每種取值情況下的子集，遞歸調(diào)用建樹(shù)算法，即返回（1）。

（5）若子集只含有單個(gè)屬性，則分支為葉子節(jié)點(diǎn)，判斷其屬性值并標(biāo)上相應(yīng)的符號(hào)，然后返回調(diào)用處。

二、實(shí)例分析

針對(duì)表1中的數(shù)據(jù)，用ID3算法求解得圖1所示決策樹(shù)。

由表一，對(duì)于該例子集合的屬性集合為{天氣，溫度，濕度，風(fēng)} 。對(duì)于“天氣”屬性有子屬性{多云，雨，晴}，對(duì)于“溫度”屬性有子屬性{高，低，適中}，對(duì)于“濕度”屬性有子屬性{正常，大}，對(duì)于“風(fēng)”屬性有子屬性{無(wú)風(fēng)，中風(fēng)，大風(fēng)}。

由經(jīng)驗(yàn)我們假定“天氣”的優(yōu)先權(quán)值為0.95，“風(fēng)”的優(yōu)先權(quán)值為0.35，濕度和溫度的優(yōu)先權(quán)值為0。

計(jì)算“天氣”的子屬性的子屬性信息熵：

由ID3算法可知：

由5.1中屬性修正信息熵的定義可得：

同理，，。所以選取“濕度”為根節(jié)點(diǎn)。接下來(lái)將例子集分成兩個(gè)子集：

接下來(lái)重復(fù)上面步驟，可得決策樹(shù)如圖2所示。

通過(guò)比較，可以得到以下結(jié)論：

（1）優(yōu)化算法所生成是二叉樹(shù)，而ID3算法所生成的是多叉樹(shù)，簡(jiǎn)化了決策問(wèn)題處理的復(fù)雜度。

（2）引入子屬性信息熵、優(yōu)先權(quán)、屬性修正信息熵的概念，從本例來(lái)看，根節(jié)點(diǎn)選擇了濕度而沒(méi)有選擇屬性值最多的天氣，所以本優(yōu)化算法確實(shí)能克服傳統(tǒng)ID3算法的多值偏向性。

三、結(jié)束語(yǔ)

數(shù)據(jù)挖掘技術(shù)是當(dāng)前數(shù)據(jù)庫(kù)和人工智能領(lǐng)域研究的熱點(diǎn)課題，分類(lèi)是數(shù)據(jù)挖掘的一種非常重要的任務(wù)。決而策樹(shù)算法是一種非常重要的數(shù)據(jù)挖掘分類(lèi)算法。本文主要對(duì)三種算法的特點(diǎn)及改進(jìn)進(jìn)行了匯總。對(duì)于ID3算法，目前的改進(jìn)方向主要集中在解決ID3偏向于選擇取值較多的屬性的不足、解決不能處理連續(xù)值的屬性、解決易受噪聲干擾和優(yōu)化儲(chǔ)存這四個(gè)方面。

本文對(duì)這三種決策樹(shù)算法當(dāng)前研究情況進(jìn)行了總結(jié)分析，并運(yùn)用分析結(jié)果對(duì)經(jīng)典ID3算法提出了改進(jìn)方法。通過(guò)進(jìn)行實(shí)例分析，了解和熟悉實(shí)際應(yīng)用上的差別，為對(duì)決策樹(shù)算法進(jìn)一步的研究作準(zhǔn)備。