一.决策树

在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
1.画法

机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。
从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
一个决策树包含三种类型的节点：
决策节点：通常用矩形框来表示
机会节点：通常用圆圈来表示
终结点：通常用三角形来表示
决策树学习也是资料探勘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。
决策树同时也可以依靠计算条件概率来构造。
决策树如果依靠数学的计算方法可以取得更加理想的效果。 数据库已如下所示：
(x, y) = (x1, x2, x3…, xk, y)
相关的变量 Y 表示我们尝试去理解，分类或者更一般化的结果。 其他的变量x1, x2, x3 等则是帮助我们达到目的的变量。

2.决策树的剪枝

剪枝是决策树停止分支的方法之一，剪枝有分预先剪枝和后剪枝两种。预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。后剪枝技术的优点是克服了“视界局限”效应，而且无需保留部分样本用于交叉验证，所以可以充分利用全部训练集的信息。但后剪枝的计算量代价比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。

3.挑西瓜决策树

西瓜样本构建决策树模型

利用信息增益选择最优划分属性
（1）西瓜树信息熵
在西瓜样本集中，共有17个样本，其中正样本8个，负样本9个，样本集的信息熵为

（2）西瓜树信息增量
西瓜样本集中，以属性“色泽”为例，它有3个取值{青绿、乌黑、浅白}，对应的子集D1（色泽=青绿）中有6个样本，其中正负样本各3个，D2（色泽=乌黑）中有6个样本，正样本4个，负样本2个，D^3（色泽=浅白）中有5个样本，正样本1个，fuya负样本4个。

同理也可以计算出其他几个属性的信息增益，选择信息增益最大的属性作为根节点来进行划分，然后再对每个分支做进一步划分.

3.2python代码实现

#导入模块
import pandas as pd
import numpy as np
from collections import Counter
from math import log2

#数据获取与处理
def getData(filePath):
    data = pd.read_excel(filePath)
    return data

def dataDeal(data):
    dataList = np.array(data).tolist()
    dataSet = [element[1:] for element in dataList]
    return dataSet
    
    #获取属性名称
def getLabels(data):
    labels = list(data.columns)[1:-1]
    return labels
    
    #获取类别标记
def targetClass(dataSet):
    classification = set([element[-1] for element in dataSet])
    return classification
    
    #将分支结点标记为叶结点，选择样本数最多的类作为类标记
def majorityRule(dataSet):
    mostKind = Counter([element[-1] for element in dataSet]).most_common(1)
    majorityKind = mostKind[0][0]
    return majorityKind
    
    #计算信息熵
def infoEntropy(dataSet):
    classColumnCnt = Counter([element[-1] for element in dataSet])
    Ent = 0
    for symbol in classColumnCnt:
        p_k = classColumnCnt[symbol]/len(dataSet)
        Ent = Ent-p_k*log2(p_k)
    return Ent
    
    #子数据集构建
def makeAttributeData(dataSet,value,iColumn):
    attributeData = []
    for element in dataSet:
        if element[iColumn]==value:
            row = element[:iColumn]
            row.extend(element[iColumn+1:])
            attributeData.append(row)
    return attributeData
    
    #计算信息增益
def infoGain(dataSet,iColumn):
    Ent = infoEntropy(dataSet)
    tempGain = 0.0
    attribute = set([element[iColumn] for element in dataSet])
    for value in attribute:
        attributeData = makeAttributeData(dataSet,value,iColumn)
        tempGain = tempGain+len(attributeData)/len(dataSet)*infoEntropy(attributeData)
        Gain = Ent-tempGain
    return Gain
    
    #选择最优属性                
def selectOptimalAttribute(dataSet,labels):
    bestGain = 0
    sequence = 0
    for iColumn in range(0,len(labels)):#不计最后的类别列
        Gain = infoGain(dataSet,iColumn)
        if Gain>bestGain:
            bestGain = Gain
            sequence = iColumn
        print(labels[iColumn],Gain)
    return sequence
    
    #建立决策树
def createTree(dataSet,labels):
    classification = targetClass(dataSet) #获取类别种类（集合去重）
    if len(classification) == 1:
        return list(classification)[0]
    if len(labels) == 1:
        return majorityRule(dataSet)#返回样本种类较多的类别
    sequence = selectOptimalAttribute(dataSet,labels)
    print(labels)
    optimalAttribute = labels[sequence]
    del(labels[sequence])
    myTree = {optimalAttribute:{}}
    attribute = set([element[sequence] for element in dataSet])
    for value in attribute:
        
        print(myTree)
        print(value)
        subLabels = labels[:]
        myTree[optimalAttribute][value] =  \
                createTree(makeAttributeData(dataSet,value,sequence),subLabels)
    return myTree
    
    def main():
    filePath = 'D:/watermelondata.xls'
    data = getData(filePath)
    dataSet = dataDeal(data)
    labels = getLabels(data)
    myTree = createTree(dataSet,labels)
    return myTree
    
    if __name__ == '__main__':
    myTree = main()

输出

色泽 0.10812516526536531
根蒂 0.14267495956679277
敲声 0.14078143361499584
纹理 0.3805918973682686
脐部 0.28915878284167895
触感 0.006046489176565584
['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
{'纹理': {}}
稍糊
色泽 0.3219280948873623
根蒂 0.07290559532005603
敲声 0.3219280948873623
脐部 0.17095059445466865
触感 0.7219280948873623
['色泽', '根蒂', '敲声', '脐部', '触感']
{'触感': {}}
硬滑
{'触感': {'硬滑': '否'}}
软粘
{'纹理': {'稍糊': {'触感': {'硬滑': '否', '软粘': '是'}}}}
模糊
{'纹理': {'稍糊': {'触感': {'硬滑': '否', '软粘': '是'}}, '模糊': '否'}}
清晰
色泽 0.04306839587828004
根蒂 0.45810589515712374
敲声 0.33085622540971754
脐部 0.45810589515712374
触感 0.45810589515712374
['色泽', '根蒂', '敲声', '脐部', '触感']
{'根蒂': {}}
硬挺
{'根蒂': {'硬挺': '否'}}
稍蜷
色泽 0.2516291673878229
敲声 0.0
脐部 0.0
触感 0.2516291673878229
['色泽', '敲声', '脐部', '触感']
{'色泽': {}}
乌黑
敲声 0.0
脐部 0.0
触感 1.0
['敲声', '脐部', '触感']
{'触感': {}}
硬滑
{'触感': {'硬滑': '是'}}
软粘
{'色泽': {'乌黑': {'触感': {'硬滑': '是', '软粘': '否'}}}}
青绿
{'根蒂': {'硬挺': '否', '稍蜷': {'色泽': {'乌黑': {'触感': {'硬滑': '是', '软粘': '否'}}, '青绿': '是'}}}}
蜷缩

结果分析

纹理的信息增益是最大的，所以将纹理作为根节点进行分类更合适。

二.sk-learn库对西瓜数据集，分别进行ID3、C4.5和CART的算法代码实现

1.ID3算法
熵和信息增益
设S是训练样本集，它包括n个类别的样本，这些方法用Ci表示，那么熵和信息增益用下面公式表示：
信息熵：

其中pi表示Ci的概率
样本熵：

其中Si表示根据属性A划分的S的第i个子集，S和Si表示样本数目
信息增益：

ID3中样本分布越均匀，它的信息熵就越大，所以其原则就是样本熵越小越好，也就是信息增益越大越好。

代码

# 读取西瓜数据集
import numpy as np
import pandas as pd
df = pd.read_table(r'D:/watermelon.txt',encoding='utf8',delimiter=',',index_col=0)
df.head()
# 由于上面的数据中包含了中文汉字，所以需要对数据进一步处理
'''
属性：
色泽 1-3代表 浅白 青绿 乌黑 根蒂 1-3代表 稍蜷 蜷缩 硬挺
敲声 1-3代表 清脆 浊响 沉闷 纹理 1-3代表 清晰 稍糊 模糊
脐部 1-3代表 平坦 稍凹 凹陷 触感 1-2代表 硬滑 软粘
标签：
好瓜 1代表 是 0 代表 不是
'''
df['色泽']=df['色泽'].map({'浅白':1,'青绿':2,'乌黑':3})
df['根蒂']=df['根蒂'].map({'稍蜷':1,'蜷缩':2,'硬挺':3})
df['敲声']=df['敲声'].map({'清脆':1,'浊响':2,'沉闷':3})
df['纹理']=df['纹理'].map({'清晰':1,'稍糊':2,'模糊':3})
df['脐部']=df['脐部'].map({'平坦':1,'稍凹':2,'凹陷':3})
df['触感'] = np.where(df['触感']=="硬滑",1,2)
df['好瓜'] = np.where(df['好瓜']=="是",1,0)
#由于西瓜数据集样本比较少，所以不划分数据集，将所有的西瓜数据用来训练模型
Xtrain = df.iloc[:,:-1]
Xtrain = np.array(Xtrain)
Ytrain = df.iloc[:,-1]
# 调用sklearn内置的决策树的库和画图工具
from sklearn import tree
import graphviz
# 采用ID3算法，利用信息熵构建决策树模型
clf = tree.DecisionTreeClassifier(criterion="entropy")
clf = clf.fit(Xtrain,Ytrain)
# 绘制决策树的图形
feature_names = ["色泽","根蒂","敲声","纹理","脐部","触感"]
dot_data = tree.export_graphviz(clf
,feature_names=feature_names
,class_names=["好瓜","坏瓜"]
,filled=True
,rounded=True
)
graph = graphviz.Source(dot_data)
graph

三、决策树算法——C4.5

（一）对比ID3的改进点
C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法进行了改进 ，改进点主要有：

用信息增益率来选择划分特征，克服了用信息增益选择的不足，
信息增益率对可取值数目较少的属性有所偏好；
能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
能够处理具有缺失属性值的训练数据；
在构造树的过程中进行剪枝；
（二）特征选择
特征选择也即选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。 随着划分过程不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

（三）信息增益率
信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5算法采用信息增益率来选择最优划分属性。增益率公式

信息增益率准则对可取值数目较少的属性有所偏好。所以，C4.5算法不是直接选择信息增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。
（四）对连续特征的处理
当属性类型为离散型，无须对数据进行离散化处理；

当属性类型为连续型，则需要对数据进行离散化处理。具体思路如下：

（五）剪枝
通过信息增益比计算得到的决策树也需要进行剪枝，剪枝方法同ID3算法。

四.CART算法

CART算法构造的是二叉决策树，决策树构造出来后同样需要剪枝，才能更好的应用于未知数据的分类。CART算法在构造决策树时通过基尼系数来进行特征选择。

基尼指数

对于训练样本集，其基尼指数如下：

如果样本集合D根据特征Am的取值可以分为两部分D1和D2，那么在特征Am的条件下，D的基尼指数如下：

基尼指数Gini(D)表征着数据集D的不确定性，而在特征Am的条件下，D的基尼指数则表征着在特征Am确定的条件下D的不确定性，因此基尼指数之差和信息增益及信息增益比一样，可以表征特征Am对数据集D的分类的能力。
决策树构建

输入： 训练数据集D，特征集A，结点样本数阈值δ，基尼指数阈值ϵ
输出： CART二叉决策树TT
step1 若样本特征集为空，则TT是一棵单节点数，其类别为D中样本数最多的类，返回T；否则，转到step2。
step2 对数据集D，计算特征集A中所有特征所有可能切分点的基尼指数，若基尼指数的值均小于给定阈值ϵ，则TT是一棵单节点数，其类别为D中样本数最多的类，返回T；否则，转到step3。
step3 选择基尼指数最小的特征Amin和相应切分点α作为根节点的特征值和切分标准，根据D中样本是否等于α（或≤α≤α，或≥α≥α）将D分为两个子集D1和D2，将D1和D2分别分配到两个子结点中，若子结点样本数均小于给定阈值δ，则该子结点是一个叶结点，若两个子结点均为叶结点，返回T；否则，返回T并转到step4。
step4 对于非叶子结点，令D等于该子结点所对应的数据集，特征集A=A−{Amin}，递归的调用step1-step3，返回子树T。
输入： CART算法生成的决策树T
输出： 最优决策树Tα
step1 若T为单结点树或由一个根结点和两个叶结点构成的树，返回T；否则，k=0,α0=0,T0=T，转到step2。
step2 k=k+1，计算Tk−1所有内部结点t的g(t)值，g(t)的最小值为αk，g(t)取最小值处的结点为tk，剪掉以tk为根结点的子树Ttk，并以tk处类别最多的样本作为新的叶结点tk的类，得到[αk,αk+1)上的最优子树Tk。
step3 若Tk是由一个根结点和两个叶结点构成的树，转到step4；否则，转到step2。
step4 利用验证数据集对最优子树序列T0,T1,⋯,TL进行测试，选择对于验证数据集有最小基尼指数的最优子树作为最终的最优决策树Tα，返回Tα。

五.总结

本次实验我们通过进一步的学习了解了ID3，C4.5，CART算法之间的优点和缺点，改进的不同之处。

六.参考链接：

https://blog.csdn.net/leaf_zizi/article/details/82848682
https://www.cnblogs.com/dennis-liucd/p/7905793.html
https://blog.csdn.net/keyue123/article/details/82253538
https://blog.csdn.net/qq_41775769/article/details/110822101