1. 基本內(nèi)容
2. 劃分選擇
3. 剪枝處理
4. 連續(xù)與缺失值
5. 多變量決策樹

1. 基本內(nèi)容

決策樹通常有三個(gè)步驟：特征選擇、決策樹生成、決策樹的修建。
決策樹是一種十分常用的分類方法，需要監(jiān)管學(xué)習(xí)，監(jiān)管學(xué)習(xí)就是給出一堆樣本，每個(gè)樣本都有一組屬性和一個(gè)分類結(jié)果，也就是分類結(jié)果已知，那么通過(guò)學(xué)習(xí)這些樣本得到一個(gè)決策樹，這個(gè)決策樹能夠?qū)π碌臄?shù)據(jù)給出正確的分類。

• 創(chuàng)建一個(gè)決策樹的主要問(wèn)題在于：
  1.決策樹中每個(gè)節(jié)點(diǎn)在哪個(gè)維度的特征上面進(jìn)行劃分？
  2.被選中的維度的特征具體在哪個(gè)值上進(jìn)行劃分？

參考：
知乎：決策樹算法的Python實(shí)現(xiàn)——黃耀鵬、YJanggo視頻信息熵是什么？ - 知乎 (zhihu.com)

YouTube：statquest

2. 劃分選擇

2.1 信息增益——決策樹ID3訓(xùn)練算法

• 熵：一種食物的不確定性叫做熵。
• 信息：消除不確定性的事物；調(diào)整概率；排除干擾；確定情況
  
  信息熵計(jì)算公式.png
  
  其中

2.2 增益率——決策樹C4.5訓(xùn)練算法

信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好，為減少這種偏好可能帶來(lái)的不利影響。C4.5算法使用增益率替代信息增益來(lái)選擇最優(yōu)劃分屬性。
使用方法：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再?gòu)闹羞x擇增益率最高的。

2.3 基尼指數(shù)——決策樹CART訓(xùn)練算法

基尼系數(shù)是信息增益準(zhǔn)則的一種近似，具有計(jì)算簡(jiǎn)單的特點(diǎn)。
基尼指數(shù)（基尼不純度）：表示在樣本集合中一個(gè)隨機(jī)選中的樣本被分錯(cuò)的概率。
注意： Gini指數(shù)越小表示集合中被選中的樣本被分錯(cuò)的概率越小，也就是說(shuō)集合的純度越高，反之，集合越不純。
即 基尼指數(shù)（基尼不純度）= 樣本被選中的概率 * 樣本被分錯(cuò)的概率

基尼系數(shù)公式.png

參考資料：（一）《機(jī)器學(xué)習(xí)》（周志華）第4章 決策樹 筆記 理論及實(shí)現(xiàn)——“西瓜樹” - 君以沫 - 博客園 (cnblogs.com)

3. 剪枝處理

3.1 預(yù)剪枝

3.2 后剪枝

4. 連續(xù)與缺失值

4.1 連續(xù)值處理

4.2 缺失值處理

5. 多變量決策樹

#! /usr/bin/python
#coding=utf-8
from math import log
import operator
#假設(shè)決策樹應(yīng)用為海洋動(dòng)物是否為魚類的分類。
def  createDataSet():
    dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']] #每一行的每一列含義依次為（不浮出水面是否可以生存的值，是否有腳蹼的值，屬于魚類的值）
    labels = ['no surfacing','flippers']#兩個(gè)特征項(xiàng)（不能浮出水面是否可以生存，腳蹼）
    return dataSet,labels
'''
dataSet：樣本集合
'''
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) #獲取整個(gè)數(shù)據(jù)集的行數(shù)，即數(shù)據(jù)的個(gè)數(shù)
    labelCounts = {} #標(biāo)簽計(jì)數(shù)器，初始化為空字典
    for featVec in dataSet:#對(duì)于數(shù)據(jù)集的每一行，即每一個(gè)數(shù)據(jù)特征項(xiàng)
        currentLabel = featVec[-1] #最后一列為當(dāng)前標(biāo)簽（即是否是魚類）
        if currentLabel not in labelCounts.keys(): #如果當(dāng)前標(biāo)簽第一次出現(xiàn)
            labelCounts[currentLabel]=0     #創(chuàng)建一個(gè)當(dāng)前標(biāo)簽對(duì)應(yīng)的字典值
        labelCounts[currentLabel] +=1   #當(dāng)前標(biāo)簽每出現(xiàn)一次，則當(dāng)前標(biāo)簽對(duì)應(yīng)的計(jì)數(shù)器+1
    shannonEnt = 0.0 #初始熵為0
    for key in labelCounts:#對(duì)于標(biāo)簽計(jì)數(shù)器的每個(gè)標(biāo)簽
        prob = float(labelCounts[key]) / numEntries #出現(xiàn)的概率=當(dāng)前的標(biāo)簽計(jì)數(shù)/總的數(shù)據(jù)個(gè)數(shù)
        shannonEnt -= prob*log(prob,2)  #根據(jù)熵的計(jì)算公式，當(dāng)前熵=負(fù)的（所有的概率*log概率）之和，這里的log以2為底
    return shannonEnt #返回信息熵
'''
dataSet：樣本集合
axis：特征項(xiàng)
value： 特征值
'''
def splitDataSet(dataSet, axis, value):
    retDataSet = [] #初始化返回的子樣本集合
    
    for featVec in dataSet: #對(duì)于數(shù)據(jù)集的每一行，即每一個(gè)數(shù)據(jù)特征項(xiàng)
        if featVec[axis] == value: #如果指定的特征項(xiàng)數(shù)值=給定的數(shù)值
            reducedFeatVec = featVec[:] #復(fù)制當(dāng)前數(shù)據(jù)點(diǎn)的特征值
            reducedFeatVec.remove(reducedFeatVec[axis]) # 去除指定的特征項(xiàng)
            retDataSet.append(reducedFeatVec) #添加到返回的樣本集合中去
    return retDataSet #返回的子樣本集合
'''
dataSet：樣本集合
'''
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1   #獲取樣本的特征項(xiàng)個(gè)數(shù)
    baseEntropy = calcShannonEnt(dataSet)   #計(jì)算總的樣本集合的熵
    bestInfoGain = 0.0;     #初始化最大信息增益值為0.0
    bestFeature = -1    #初始化最優(yōu)劃分特征為不劃分
    for i in range(numFeatures):    #對(duì)于每個(gè)特征項(xiàng)
        featList = [example[i] for example in dataSet]  #獲取每個(gè)樣本在該特征項(xiàng)上面的值
        uniqueVals = set(featList)  #去重
        newEntropy = 0.0    #
        for value in uniqueVals: #對(duì)于該特征項(xiàng)上每個(gè)不同的值
            subDataSet = splitDataSet(dataSet,i,value) #基于該特征項(xiàng)的特定值進(jìn)行劃分
            prob = len(subDataSet)/float(len(dataSet))  #計(jì)算滿足條件的子樣本集合概率=子樣本集合個(gè)數(shù)/總樣本個(gè)數(shù)
            newEntropy += prob * calcShannonEnt(subDataSet) #將每個(gè)子樣本集合的概率*相應(yīng)的熵進(jìn)行累加，獲得劃分之后總的熵值
        InfoGain = baseEntropy - newEntropy # 信息增益= 初始信息熵-新劃分知乎的信息熵
        if (InfoGain > bestInfoGain):   #判斷此次劃分信息增益是否大于最大信息增益值，若大于則說(shuō)明經(jīng)過(guò)劃分之后的不確定性減小了
            bestInfoGain = InfoGain #將組大信息增益值替換為此次劃分信息增益
            bestFeature = i #保留此次劃分的特征項(xiàng)為最優(yōu)劃分特征
    return bestFeature #返回最優(yōu)劃分特征所在的列數(shù)
 
def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
            classCount[vote] += 1
        sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]
'''
dataSet：樣本集合
labels： 特征項(xiàng)
'''
def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet] #分類結(jié)果集合為樣本集合每一行的最后一列
    if classList.count(classList[0]) == len(classList): #如果分類結(jié)果完全相同，則停止劃分
        return classList[0] #返回類別
    if len(dataSet[0]) == 1:    #如果樣本集合沒(méi)有特征項(xiàng)
        return majorityCnt(classList) #返回當(dāng)前集合中類別最多的
    bestFeat = chooseBestFeatureToSplit(dataSet)    #選擇樣本集合最優(yōu)的劃分特征項(xiàng)所在列數(shù)
    bestFeatLabel = labels[bestFeat]    #獲得最優(yōu)特征項(xiàng)
    myTree = {bestFeatLabel:{}} #初始化決策樹
    del(labels[bestFeat])   #刪除list中此特征項(xiàng)
    featValues = [example[bestFeat] for example in dataSet] #將所有樣本在該特征項(xiàng)下的值取出來(lái)
    uniqueVals = set(featValues)    #去重
    for value in uniqueVals:    #對(duì)于不同的特征值
        subLabels = labels[:]   #復(fù)制標(biāo)簽
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels) #遞歸創(chuàng)建決策樹，使用劃分后的子樣本集合和子標(biāo)簽
    return myTree   #返回決策樹，決策樹的key為最優(yōu)劃分特征，值為key為特征值，value為對(duì)應(yīng)的子樣本決策樹。
myDat,labels=createDataSet()
myTree = createTree(myDat,labels)
print myTree