第二章決策樹(ID3分類算法)

第二章決策樹(ID3分類算法)為解決上述問題必須進(jìn)行分類分類是數(shù)據(jù)挖掘中的一種主要分析手段分類的任務(wù)是對(duì)數(shù)據(jù)集進(jìn)行學(xué)習(xí)并構(gòu)造一個(gè)擁有預(yù)測(cè)功能的分類模型，用于預(yù)測(cè)未知樣本的類標(biāo)號(hào)，如：根據(jù)瓦斯?fàn)顟B(tài)、開采技術(shù)條件、煤層賦存狀況等對(duì)危險(xiǎn)進(jìn)行分類評(píng)估根據(jù)核磁共振的結(jié)果區(qū)分腫瘤是惡性還是良性的根據(jù)星系的形狀對(duì)它們進(jìn)行分類劃分出交易是合法或欺詐將新聞分類金融、天氣、娛樂體育等主要分類方法決策樹分類方法貝葉斯分類方法K-最近鄰分類方法神經(jīng)網(wǎng)絡(luò)分類方法支持向量機(jī)組合學(xué)習(xí)方法不平衡數(shù)據(jù)分類問題分類模型的評(píng)價(jià)回歸方法研究生學(xué)院舉例說明分類任務(wù)應(yīng)用模型l歸納推論

學(xué)習(xí)模型模型Tid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

Tid

有房者

婚姻狀況2

年收入

拖欠貸款

11

否

單身l

55K

?

12

是

已婚

80K

?

13

是

離異

110K

?

14

否

單身

95K

?

15

否

已婚

67K

?

10

學(xué)習(xí)算法研究生學(xué)院有房婚姻狀況年收入是否否否是沒有已婚單身,離婚<80K>80K極快的屬性訓(xùn)練數(shù)據(jù)模型:決策樹Tid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

研究生學(xué)院婚姻狀況有房年收入是否否否是沒有已婚單身,離異<80K>80KTid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

測(cè)試數(shù)據(jù)申請(qǐng)模型到測(cè)試數(shù)據(jù)研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K開始從樹.的根測(cè)試數(shù)據(jù)研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院應(yīng)用模型l歸納推論

學(xué)習(xí)模型模型Tid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

Tid

有房者

婚姻狀況2

年收入

拖欠貸款

11

否

單身l

55K

?

12

是

已婚

80K

?

13

是

離異

110K

?

14

否

單身

95K

?

15

否

已婚

67K

?

10

學(xué)習(xí)算法研究生學(xué)院有房婚姻狀況年收入是否否否是沒有已婚單身,離婚<80K>80K極快的屬性訓(xùn)練數(shù)據(jù)模型:決策樹Tid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

決策樹的例子研究生學(xué)院婚姻狀況有房年收入是否否否是沒有已婚單身,離異<80K>80KTid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

決策樹的例子研究生學(xué)院應(yīng)用模型l歸納推論

學(xué)習(xí)模型模型Tid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

Tid

有房者

婚姻狀況2

年收入

拖欠貸款

11

否

單身l

55K

?

12

是

已婚

80K

?

13

是

離異

110K

?

14

否

單身

95K

?

15

否

已婚

67K

?

10

學(xué)習(xí)算法研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根申請(qǐng)模型到測(cè)試數(shù)據(jù)研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根研究生學(xué)院有房婚姻年收入是否否否是否已婚單身、離婚<80K>80K測(cè)試數(shù)據(jù)開始從樹.的根舉例說明分類任務(wù)研究生學(xué)院應(yīng)用模型l歸納推論

學(xué)習(xí)模型模型Tid

有房者

婚姻狀況

年收入

拖欠貸款

1

是

單身

125K

否

2

否

已婚

100K

否

3

否

單身

70K

否

4

是

已婚

120K

否

5

否

離異

95K

是

6

否

已婚

60K

否

7

是

離異

220K

否

8

否

單身

85K

是

9

否

已婚

75K

否

10

否

單身

90K

是

10

Tid

有房者

婚姻狀況2

年收入

拖欠貸款

11

否

單身l

55K

?

12

是

已婚

80K

?

13

是

離異

110K

?

14

否

單身

95K

?

15

否

已婚

67K

?

10

學(xué)習(xí)算法決策樹在構(gòu)建過程中需重點(diǎn)解決2個(gè)問題：(1)如何選擇合適的屬性作為決策樹的節(jié)點(diǎn)去劃分訓(xùn)練樣本；(2)如何在適當(dāng)位置停止劃分過程，從而得到大小合適的決策樹。雖然可以采用任何一個(gè)屬性對(duì)數(shù)據(jù)集進(jìn)行劃分，但最后形成的決策樹會(huì)差異很大。需要尋找合適的屬性選擇方法。屬性選擇是決策樹算法中重要的步驟，常見的屬性選擇標(biāo)準(zhǔn)包括信息增益(informationgain)和Gini系數(shù)。信息增益是決策樹常用的分枝準(zhǔn)則,在樹的每個(gè)結(jié)點(diǎn)上選擇具有最高信息增益的屬性作為當(dāng)前結(jié)點(diǎn)的劃分屬性。Gini系數(shù)是一種不純度函數(shù)，用來度量數(shù)據(jù)集的數(shù)據(jù)關(guān)于類的純度。二、DI3分類算法1.ID3分類算法提出：由Quinlan于1986年提出，它使用信息增益(informationgain)作為屬性的選擇標(biāo)準(zhǔn)。首先檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一個(gè)類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來對(duì)新的樣本進(jìn)行分類。2.ID3分類算法相關(guān)的基本概念：1）信息熵2）信息增益熵(entropy,也稱信息熵)用來度量一個(gè)屬性的信息量。假定S為訓(xùn)練集，S的目標(biāo)屬性C具有m個(gè)可能的類標(biāo)號(hào)值，C={C1,C2,…,Cm}，假定訓(xùn)練集S中，Ci在所有樣本中出現(xiàn)的頻率為(i=1,2,3,…,m)，則該訓(xùn)練集S所包含的信息熵定義為：熵越小表示樣本對(duì)目標(biāo)屬性的分布越純，反之熵越大表示樣本對(duì)目標(biāo)屬性分布越混亂。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoOvercast（陰天）coolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno信息熵例題演示考慮數(shù)據(jù)集weather如下,求weather數(shù)據(jù)集關(guān)于目標(biāo)屬性playball的熵。目標(biāo)屬性解答：令weather數(shù)據(jù)集為S，其中有14個(gè)樣本,目標(biāo)屬性playball有2個(gè)值{C1=yes,C2=no}。14個(gè)樣本的分布為：9個(gè)樣本的類標(biāo)號(hào)取值為yes，5個(gè)樣本的類標(biāo)號(hào)取值為No。C1=yes在所有樣本S中出現(xiàn)的概率為9/14，C2=no在所有樣本S中出現(xiàn)的概率為5/14。因此數(shù)據(jù)集S的熵為：信息增益：是劃分前樣本數(shù)據(jù)集的不純程度(熵)和劃分后樣本數(shù)據(jù)集的不純程度(熵)的差值。假設(shè)劃分前樣本數(shù)據(jù)集為S,并用屬性A來劃分樣本集S，則按屬性A劃分S的信息增益Gain(S,A)為樣本集S的熵減去按屬性A劃分S后的樣本子集的熵：按屬性A劃分S后的樣本子集的熵定義如下：假定屬性A有k個(gè)不同的取值，從而將S劃分為k個(gè)樣本子集{S1,S2,…,Sk}，則按屬性A劃分S后的樣本子集的信息熵為:其中|Si|(i,=1,2,…k)為樣本子集Si中包含的樣本數(shù)，|S|為樣本集S中包含的樣本數(shù)。信息增益越大，說明使用屬性A劃分后的樣本子集越純，越有利于分類。以數(shù)據(jù)集weather為例，設(shè)該數(shù)據(jù)集為S，假定用屬性wind來劃分S，求S對(duì)屬性wind的信息增益。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoovercastcoolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno解：(1)首先由前例計(jì)算得到數(shù)據(jù)集S的熵值為0.94；(2)屬性wind有2個(gè)可能的取值{weak,strong}，它將S劃分為2個(gè)子集：{S1,S2},S1為wind屬性取值為weak的樣本子集，共有8個(gè)樣本；S2為wind屬性取值為strong的樣本子集，共有6個(gè)樣本；下面分別計(jì)算樣本子集S1和S2的熵。對(duì)樣本子集S1，playball=yes的有6個(gè)樣本，playball=no的有2個(gè)樣本，則：對(duì)樣本子集S2，playball=yes的有3個(gè)樣本，playball=no的有3個(gè)樣本，則：利用屬性wind劃分S后的熵為：按屬性wind劃分?jǐn)?shù)據(jù)集S所得的信息增益值為：函數(shù)：DT(S,F)輸入：訓(xùn)練集數(shù)據(jù)S，訓(xùn)練集數(shù)據(jù)屬性集合F輸出：ID3決策樹(1)if

樣本S全部屬于同一個(gè)類別Cthen(2)創(chuàng)建一個(gè)葉結(jié)點(diǎn)，并標(biāo)記類標(biāo)號(hào)為C；(3)return；(4)else(5)計(jì)算屬性集F中每一個(gè)屬性的信息增益，假定增益值最大的屬性為A；(6)創(chuàng)建結(jié)點(diǎn)，取屬性A為該結(jié)點(diǎn)的決策屬性；(7)for結(jié)點(diǎn)屬性A的每個(gè)可能的取值Vdo(8)為該結(jié)點(diǎn)添加一個(gè)新的分支，假設(shè)SV為屬性A取值為V的樣本子集；(9)if

樣本SV全部屬于同一個(gè)類別Cthen(10)為該分支添加一個(gè)葉結(jié)點(diǎn)，并標(biāo)記類標(biāo)號(hào)為C；(11)else(12)遞歸調(diào)用DT(SV,F-{A})，為該分支創(chuàng)建子樹；(13)endif(11)endfor(12)endif以weather數(shù)據(jù)集為例，講解ID3的建立過程。outlooktemperaturehumiditywindplayballsunnyhothighweaknosunnyhothighstrongnoovercasthothighweakyesrainmildhighweakyesraincoolnormalweakyesraincoolnormalstrongnoovercastcoolnormalstrongyessunnymildhighweaknosunnycoolnormalweakyesrainmildnormalweakyessunnymildnormalstrongyesovercastmildhighstrongyesovercasthotnormalweakyesrainmildhighstrongno數(shù)據(jù)集具有屬性：outlook,temperature,humidity,wind.outlook={sunny,overcast,rain}temperature={hot,mild,cool}humidity={high,normal}wind={weak,strong}首先計(jì)算總數(shù)據(jù)集S對(duì)所有屬性的信息增益，尋找根節(jié)點(diǎn)的最佳分裂屬性:Gain(S,outlook)=0.246Gain(S,temperature)=0.029Gain(S,humidity)=0.152Gain(S,wind)=0.049顯然，這里outlook屬性具有最高信息增益值，因此將它選為根結(jié)點(diǎn).以outlook做為根結(jié)點(diǎn)，繼續(xù)往下：思想是，以outlook的可能取值建立分支，對(duì)每個(gè)分支遞歸建立子樹。因?yàn)閛utlook有3個(gè)可能值,因此對(duì)根結(jié)點(diǎn)建立3個(gè)分支{sunny,overcast,rain}.那么，哪個(gè)屬性用來最佳劃分根結(jié)點(diǎn)的Sunny分支？overcast分支？Rain分支？outlooksunnyovercastrain???首先對(duì)outlook的sunny分支建立子樹。找出數(shù)據(jù)集中outlook=sunny的樣本子集Soutlook=sunny，然后依次計(jì)算剩下三個(gè)屬性對(duì)該樣本子集Ssunny劃分后的信息增益：Gain(Ssunny,humidity)=0.971Gain(Ssunny,temperature)=0.571Gain(Ssunny,wind)=0.371顯然humidity具有最高信息增益值，因此它被選為outlook結(jié)點(diǎn)下sunny分支下的決策結(jié)點(diǎn)。outlooksunnyovercastrain?Humidity采用同樣的方法，依次對(duì)outlook的overcast分支、rain分支建立子樹，最后得到一棵可以預(yù)測(cè)類標(biāo)號(hào)未知的樣本的決策樹。ID3決策樹對(duì)未知樣本進(jìn)行預(yù)測(cè)下面利用決策樹對(duì)類標(biāo)號(hào)未知的樣本X進(jìn)行預(yù)測(cè)：X={rain,hot,normal,weak,?}ID3算法總結(jié)ID3算法是所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。ID3搜索的假設(shè)空間是可能的決策樹的集合，搜索目的是構(gòu)造與訓(xùn)練數(shù)據(jù)一致的一棵決策樹，搜索策略是爬山法，在構(gòu)造決策樹時(shí)從簡(jiǎn)單到復(fù)雜，用信息熵作為爬山法的評(píng)價(jià)函數(shù)。ID3算法的核心是在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性，用信息增益作為屬性選擇的標(biāo)準(zhǔn)，使得在每個(gè)非葉節(jié)點(diǎn)進(jìn)行測(cè)試時(shí)能獲得關(guān)于