趙 靜

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

1 ID3算法簡(jiǎn)介

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

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

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

不足：ID3算法在選擇分類屬性時(shí)往往選擇了取值較多的屬性；ID3算法只能處理離散型數(shù)據(jù)，若分析必須先進(jìn)行離散化；用ID3算法創(chuàng)建決策樹(shù)時(shí)必須知道所有內(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ì)表.通過(guò)數(shù)據(jù)挖掘旨在回答“誰(shuí)在買(mǎi)電腦”這一問(wèn)題。

表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)。由上可知“年齡”具有最高的信息增益，選擇“年齡”為測(cè)試屬性 。

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

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

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

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