決策樹(shù)算法：
優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高获搏，輸出結(jié)果易于理解赖条，對(duì)中間值的缺失不敏感，可以處理不相關(guān)的特征數(shù)據(jù)常熙。
缺點(diǎn)：可能會(huì)產(chǎn)生過(guò)度匹配問(wèn)題纬乍。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型。
算法原理：
決策樹(shù)是一個(gè)簡(jiǎn)單的為輸入值選擇標(biāo)簽的流程圖裸卫。這個(gè)流程圖由檢查特征值的決策節(jié)點(diǎn)和分配標(biāo)簽的子葉節(jié)點(diǎn)組成仿贬。為輸入值選擇標(biāo)簽，我們以流程圖的初始決策節(jié)點(diǎn)(即根節(jié)點(diǎn))開(kāi)始墓贿。此節(jié)點(diǎn)包含一個(gè)條件茧泪，檢查輸入值的特征之一，基于該特征的值選擇一個(gè)分支聋袋。沿著這個(gè)描述我們輸入值的分支队伟，我們到到了一個(gè)新的決策節(jié)點(diǎn)，有一個(gè)關(guān)于輸入值的特征的新條件幽勒。我們繼續(xù)沿著每個(gè)節(jié)點(diǎn)的條件選擇的分支嗜侮，直到到達(dá)葉節(jié)點(diǎn)，它為輸入值提供了一個(gè)標(biāo)簽。
算法流程：
收集數(shù)據(jù)：即建立訓(xùn)練測(cè)試數(shù)據(jù)集锈颗。
準(zhǔn)備數(shù)據(jù)：決策樹(shù)構(gòu)造算法只適用于標(biāo)稱型數(shù)據(jù)顷霹，因此數(shù)值型數(shù)據(jù)必須是離散化的。
分析數(shù)據(jù)：建立構(gòu)造樹(shù)击吱，構(gòu)造樹(shù)完成后我們檢查圖形是否符合預(yù)期淋淀。
訓(xùn)練數(shù)據(jù)：完善構(gòu)造樹(shù)的數(shù)據(jù)結(jié)構(gòu)。
測(cè)試數(shù)據(jù)：使用經(jīng)驗(yàn)樹(shù)計(jì)算覆醇。
使用算法：對(duì)實(shí)際數(shù)據(jù)進(jìn)行預(yù)測(cè)绅喉。
ID3算法：
ID3算法(Iterative Dichotomiser 3，迭代二叉樹(shù)3代)是一種貪心算法叫乌，用來(lái)構(gòu)造決策樹(shù)柴罐。ID3算法起源于概念學(xué)習(xí)系統(tǒng)（CLS），以信息熵的下降速度為選取測(cè)試屬性的標(biāo)準(zhǔn)憨奸，即在每個(gè)節(jié)點(diǎn)選取還尚未被用來(lái)劃分的具有最高信息增益的屬性作為劃分標(biāo)準(zhǔn)革屠，然后繼續(xù)這個(gè)過(guò)程，直到生成的決策樹(shù)能完美分類訓(xùn)練樣例排宰。
為了實(shí)現(xiàn)ID3算法我們還需要了解這個(gè)高富帥提出的三個(gè)概念：信息似芝、信息熵和信息增益。
并且由上面的公式我們可以看出其實(shí)信息熵就是信息的期望值板甘，所以我們可知党瓮，信息熵越小，信息的純度越高盐类，也就是信息越少寞奸，在分類領(lǐng)域來(lái)講就是里面包含的類別越少，所以我們可以得出在跳，與初始信息熵的差越大分類效果越好枪萄。
下面我們來(lái)舉個(gè)例子：
買蘋果的時(shí)候，從外觀上評(píng)判一個(gè)蘋果甜不甜有兩個(gè)依據(jù)：紅不紅 和 圓不圓 (原諒我淺薄的挑蘋果經(jīng)驗(yàn)吧猫妙。瓷翻。。)
下面來(lái)算一下啊這5個(gè)蘋果是不是好蘋果的信息熵(只看結(jié)果值)：
下面給出python求信息熵的代碼
def calcShannonEnt(dataSet):
numEntries = len(dataSet) #數(shù)據(jù)集大小
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1] #獲取分類標(biāo)簽
if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1 #每個(gè)類中數(shù)據(jù)個(gè)數(shù)統(tǒng)計(jì)
shannonEnt = 0.0
for key in labelCounts: #信息熵計(jì)算
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log(prob,2)
return shannonEnt
接下來(lái)我們要尋找怎么分類比較好也就是決策樹(shù)的叉割坠，我們的例子中可以按兩個(gè)方式分類齐帚，紅不紅和圓不圓。彼哼。到的按哪個(gè)分更好一點(diǎn)呢对妄，這下就用到信息增益了：
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #計(jì)算分類依據(jù)的個(gè)數(shù)
baseEntropy = calcShannonEnt(dataSet) #計(jì)算原始分類的信息熵
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures): #對(duì)apple進(jìn)行分類
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
for value in uniqueVals: #計(jì)算該種分類的信息熵
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy #計(jì)算當(dāng)前分類的信息增益
if (infoGain > bestInfoGain): #比較那種分類的信息增益最大并返回
bestInfoGain = infoGain
bestFeature = i
return bestFeature
我們可以看出，這種分類的信息熵是0.5509775沪羔，它的信息增益是0.419973
如果按照?qǐng)A不圓來(lái)分類：
我們可以看出饥伊，這種分類的信息熵是0.8象浑，它的信息增益是0.17095
顯然第一種分類的信息增益較大
確實(shí)第一種方法劃分的較好。
