姓名：梁祥????????學(xué)號(hào)：17021210935
【嵌牛導(dǎo)讀】：決策樹(shù)算法作為數(shù)據(jù)挖掘領(lǐng)域的十大算法之一，與k-means算法、EM算法等在實(shí)際應(yīng)用中發(fā)揮著重要的作用。決策樹(shù)算法利用已知或人為定義的標(biāo)簽（Flag），在具有一定樣本規(guī)模的情況下，可以繪制出信息熵下降最快的樹(shù)模型。利用訓(xùn)練得到的樹(shù)，就可以利用先驗(yàn)知識(shí)判斷目標(biāo)對(duì)象屬于哪個(gè)預(yù)定義的目標(biāo)類(lèi)。
【嵌牛鼻子】：決策樹(shù)，ID3，信息熵，信息增益
【嵌牛提問(wèn)】：如何量化定義隨機(jī)事件所包含的信息量？在構(gòu)建決策樹(shù)時(shí)，如何使決策樹(shù)的信息熵下降最快？
【嵌牛正文】：
關(guān)于決策樹(shù)算法，不像之前的其他聚類(lèi)算法那么枯燥，我們這次可以先講小故事了~~~
一個(gè)女孩的母親要給這個(gè)女孩介紹男朋友，于是有了下面的對(duì)話(huà)：
女兒：多大年紀(jì)了？
母親：26。
女兒：長(zhǎng)的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務(wù)員不？
母親：是，在稅務(wù)局上班呢。
女兒：那好，我去見(jiàn)見(jiàn)。
（此例純屬虛構(gòu)，如有雷同，那這個(gè)例子一定也是從網(wǎng)上抄的）
決策樹(shù)是一種典型的分類(lèi)方法，功能強(qiáng)大且容易提取規(guī)則，利用歸納算法生成決策樹(shù)，樹(shù)中的每條路徑代表一個(gè)規(guī)則，所以比較適合用于數(shù)據(jù)挖掘中的分類(lèi)。這里呢，我們主要介紹ID3算法。該算法采用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹(shù)，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類(lèi)。
決策樹(shù)算法最大的優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過(guò)程中，不需要使用者了解過(guò)多的背景知識(shí)，只需要對(duì)訓(xùn)練實(shí)例進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。顯然，決策樹(shù)學(xué)習(xí)算法屬于有監(jiān)督學(xué)習(xí)，它從一類(lèi)無(wú)序、無(wú)規(guī)則的事物（概念）中推理出決策樹(shù)表示的分類(lèi)規(guī)則。
因此，建立決策樹(shù)的關(guān)鍵在于當(dāng)前狀態(tài)下選擇哪個(gè)屬性作為分類(lèi)依據(jù)。ID3算法的理論基礎(chǔ)是信息論中的信息熵和信息增益度，在算法中以其為度量標(biāo)準(zhǔn)在樹(shù)的內(nèi)部各個(gè)節(jié)點(diǎn)處尋找一個(gè)屬性，使該屬性能最好地將訓(xùn)練集進(jìn)行分類(lèi)。
那么，如何度量自信息量的大小呢？
通過(guò)自信息量，也成為非平均自信息量，是用來(lái)消除不確定度的一種表達(dá)：
信息熵是從平均意義上表征信源的總體特征，可以表示信源的平均不確定度，對(duì)于特定信源（概率空間給定），其信源熵是一個(gè)確定的數(shù)值，不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。
假定有n個(gè)互不相容的事件a1,a2,a3,......,an，令p（ai）表示時(shí)間ai發(fā)生的概率，則由該分布傳遞的信息量稱(chēng)為熵，記為式（1）
熵的實(shí)際意義表示是D中元組的類(lèi)標(biāo)號(hào)所需要的平均信息量。在每次分類(lèi)迭代中，首先計(jì)算當(dāng)前信息的全體信息熵，計(jì)算方法如上式所述。
在決策樹(shù)分類(lèi)中，假設(shè)S是訓(xùn)練樣本集合，假定當(dāng)前數(shù)據(jù)的類(lèi)別標(biāo)號(hào)屬性具有n個(gè)不同的值a1，a2，a3，......，an。同時(shí)在樣本集合中存在m個(gè)不同類(lèi)C1，C2，......，Cm（身高、體重、學(xué)歷等），同樣在每個(gè)類(lèi)Ci劃分出的子集中，也可能存在不同的類(lèi)別標(biāo)號(hào)屬性，其類(lèi)別數(shù)目可以表示為：Si1，Si2，......，Sin。子集的熵同樣可以利用經(jīng)驗(yàn)熵公式計(jì)算得出。通過(guò)比較每個(gè)明確某個(gè)子集劃分之后，信息熵的增加量，即信息增益，就可以將其確定為當(dāng)前生長(zhǎng)的決策樹(shù)節(jié)點(diǎn)。
? ? ? ? 信息增益 = 全體信息熵 - 當(dāng)前屬性下的信息熵
根據(jù)貪婪算法，為了使下一步所需的信息量最小，要求每一次都選擇其信息增益最大的屬性作為決策樹(shù)的新節(jié)點(diǎn)。
ID3決策樹(shù)建立算法的步驟：
1）決定分類(lèi)屬性；
2） 對(duì)目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn)N
3） 如果數(shù)據(jù)庫(kù)中的數(shù)據(jù)都屬于同一個(gè)類(lèi)，N就是樹(shù)葉，在樹(shù)葉上標(biāo)出所屬的類(lèi)
4） 如果數(shù)據(jù)表中沒(méi)有其他屬性可以考慮，則N也是樹(shù)葉，按照少數(shù)服從多數(shù)的原則在樹(shù)葉上標(biāo)出所屬類(lèi)別
5） 否則，根據(jù)平均信息期望值E或GAIN值選出一個(gè)最佳屬性作為節(jié)點(diǎn)N的測(cè)試屬性
6 ）節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中的每個(gè)值：從N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄
7）如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹(shù)。
決策樹(shù)算法比較適合處理離散數(shù)值的屬性，實(shí)際應(yīng)用中屬性是連續(xù)的或者離散的情況都比較常見(jiàn)。在應(yīng)用連續(xù)屬性值時(shí)，在一個(gè)樹(shù)節(jié)點(diǎn)可以將該屬性的值劃分為幾個(gè)合理的區(qū)間。然后信息增益的計(jì)算就可以采用和離散值處理一樣的方法。原則上可以將該屬性劃分為任意數(shù)目的空間。
小結(jié)：ID3算法是一種經(jīng)典的決策樹(shù)學(xué)習(xí)算法，其基本思想是，以信息熵為度量，用于決策樹(shù)節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變?yōu)樽钚〉膶傩?，以此?gòu)造一棵熵值下降最快的決策樹(shù)。判斷某個(gè)節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)的原則是，在該節(jié)點(diǎn)上的所有數(shù)據(jù)屬性一致，或者所有屬性已經(jīng)判斷完畢。對(duì)于屬性一致的情況，可以直接終止生成；而對(duì)于屬性判斷完畢的情況，如果當(dāng)前節(jié)點(diǎn)的類(lèi)別屬性不一致，可以利用多數(shù)投票法對(duì)目標(biāo)屬性進(jìn)行判斷。
