趙 靜

沈陽市服裝藝術(shù)學(xué)校，遼寧沈陽 110032

1 ID3算法簡介

ID3算法由Quinlan于1979年提出。其基本思想是：在對訓(xùn)練集進(jìn)行分類時，以信息熵為度量，用于決策樹節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性對數(shù)據(jù)進(jìn)行劃分，以構(gòu)造一顆熵值下降最快的決策樹，每個葉子節(jié)點(diǎn)對應(yīng)的實(shí)例集中的實(shí)例屬于同一類。

2 ID3算法的優(yōu)點(diǎn)和不足

優(yōu)點(diǎn)：運(yùn)用信息論知識選擇屬性，理論清晰；容易生成IF-THEN語句；對于離散型樣本數(shù)據(jù)處理功能強(qiáng)；ID3自頂向下搜索，節(jié)省系統(tǒng)資源，計(jì)算時間與樣本大小。

不足：ID3算法在選擇分類屬性時往往選擇了取值較多的屬性；ID3算法只能處理離散型數(shù)據(jù)，若分析必須先進(jìn)行離散化；用ID3算法創(chuàng)建決策樹時必須知道所有內(nèi)部節(jié)點(diǎn)。

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

定理1：若函數(shù)f(x)在[a，b]上連續(xù)，在（a，b）內(nèi)有一階、二階導(dǎo)數(shù)，并且在（a，b）上，若f'(x)＜0，則f(x)在[a，b]上是凸函數(shù)；

3.1 算法改進(jìn)的實(shí)現(xiàn)

pi表示數(shù)據(jù)屬于類Ci的概率，在（0，1）上任取p1，p2有p1+p2=1，p1-p2=△p→0，因?yàn)閘og2p函數(shù)在（0，1]上連續(xù)，由定理1可知log2p函數(shù)在其連續(xù)區(qū)間上是凸函數(shù)。

由凸函數(shù)性質(zhì)計(jì)算得：

3.2 改進(jìn)算法的應(yīng)用

表一為某公司調(diào)查的顧客數(shù)據(jù)統(tǒng)計(jì)表.通過數(shù)據(jù)挖掘旨在回答“誰在買電腦”這一問題。

表1 顧客調(diào)查表

第2步：計(jì)算條件屬性的熵

1）年齡分三組:老、中、青。 青年384人，正例128人，反例256人；中年256人，正例256人，反例0人；老年252人，正例125，反例127人。

老年 ： I(125，127)=0.9157 所以 ，E（年齡）=0.6877 ； G（年齡）=0.9537-0.6877 =0.2660 ；

2）E（收入）=0.9361 G（收入信息增益）=0.9537-0.9361=0.0176；

3）E（學(xué)生）=0.7811 G（年齡信息增益）=0.9537-0.7811=0.1726；

4）E（信譽(yù)）=0.9048 G(信譽(yù)信息增益）=0.9537-0.9048=0.0453。

第3步：計(jì)算選擇節(jié)點(diǎn)。由上可知“年齡”具有最高的信息增益，選擇“年齡”為測試屬性 。

第4步：遞歸建樹算法，分別對各個子集分析，計(jì)算選擇分支的測試屬性。

1）年齡=“青年”的子集有：選擇學(xué)生為測試屬性對子集進(jìn)行再劃分；

2）對于年齡=“中年”，數(shù)據(jù)都屬于同一類，自然形成樹葉；

3）對于年齡=“老年”的子集有：選擇信譽(yù)為測試屬性。由此生成決策樹如下圖所示：