机器学习：决策树_机器学习

一.什么是决策树？

分类决策树模型是一种描述对实例进行分类的树形结构，属于预测模型。决策树方法在分类、预测、规则提取等领域有着广泛应用。它代表的是对象属性与对象值之间的一种映射关系。其由结点和有向边组成。结点有两种类型：内部结点和叶节点。每个内部结点表示一个特征或属性，每个叶节点表示一个决策结果。

如上图，决策过程中提出的每个判定问题都是对某个属性的“测试”，而测试的结果是导出最终结论，或者加以更进一步的判定测试；决策树学习的关键在于如何选择最优划分属性

二.怎么划分选择，寻找最优划分属性

经典的属性划分方法：

信息增益： id 3

增益率：c 4.5

基尼指数：cart

1. id3（信息增益）

在理解信息增益前，先了解“信息熵”，它是度量样本集合纯度最常用的一种指标，描述的是随机变量的不确定性（也就是混乱程度）。假设某随机变量的概率分布为：pk (k=1, 2, ..., |y|)
则它的信息熵计算公式为：
（若p = 0，则plog2p=0）

系统越混乱越复杂，不确定性越大，熵就越大

h（x）值越小，则x的纯度越高，最小值为0，最大值为log2|n|

离散属性a有v个可能的取值{a1, a2, ..., av}，用a来进行划分，则会产生v个分支结点，其中第v个分支结点包含了d中所有在属性a上取值为av的样本，记为dv。则可计算出用属性a对样本集d进行划分所获得的“信息增益”：

信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大

2. c4.5（增益率）

增益率不像信息增益偏好可取值数目多的属性，反而对可取值数目较少的属性有所偏好

定义增益率：

iv(a)称为属性a的“固有值” [quinlan, 1993] ，增益比就是信息增益除以iv(a)，iv(a)是属性a的固有属性，当属性a可取值增多的时候，iv(a)一般也增大

3. cart（基尼指数）

基尼指数也是一个寻找最优划分属性的准则，反映了随机抽取两个样本，其类别标记不一致的概率，在分类问题中，假设d有k个类，样本点属于第k类的概率为p_k,则概率分布的基尼值定义为：

$gini(d)=\sum_{k=1}^{k}p_{k}(1-p_{k})=1-\sum_{k=1}^{k}p_{k}^{2}$

gini(d)越小，数据集d的纯度越高；

基尼指数就是在样本集中随机抽出两个样本不同类别的概率。当样本集越不纯的时候，这个概率也就越大，即基尼指数也越大。

基尼指数和信息增益计算方式类似，但其两者划分准则不同，而且id3、c4.5划分时，一个节点可以划分为多个子结点，子结点数量根据属性可取值的数量决定；而cart决策树是严格的二叉树结构，就是说1个节点最多划分为2子结点。

三.剪枝处理

“剪枝”是决策树学习算法对付“过拟合”的主要手段，其基本策略分为“预剪枝”和“后剪枝”。

预剪枝：在决策树生成过程中，对每个结点在划分前先进性估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。它的位置在每一次生成分支节点前，先判断有没有必要生成，如没有必要，则停止划分。

优点

降低过拟合风险

显著减少训练时间和测试时间开销。

缺点

欠拟合风险

后剪枝：先从训练集生成一棵完整的决策树（相当于结束位置），然后自底向上的对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点，相当于将子树剪去。值得注意的是，后剪枝时要用到一个测试数据集合，如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子。
理论上讲，后剪枝生成的决策树要比预剪枝生成的效果好，但是后剪枝在计算复杂度上比预剪枝高。

优点

后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树

缺点

训练时间开销大

四.特殊类型数据处理

连续值处理：

取值数目非有限，属性的可取值无穷多，就无法直接划分节点，需要先将连续值离散化，采用离散属性值方法，计算这些划分点的增益，选取最优的划分点进行样本集合的划分：

缺失值处理：

参考此篇博客：

决策树原理详解（无基础的同样可以看懂）_决策树怎么看-csdn博客https://blog.csdn.net/greenyang5277/article/details/104500739

五.实验小结

首先要知道决策树模型是一种描述对实例进行分类的树形结构，代表的是对象属性与对象值之间的一种映射关系。树的每个内部结点表示一个特征或属性，每个叶节点表示一个决策结果。决策树的划分属性有信息增益： id 3，增益率：c 4.5和基尼指数：cart。id3、c4.5划分时，一个节点可以划分为多个子结点，子结点数量根据属性可取值的数量决定；而cart决策树是严格的二叉树结构，就是说1个节点最多划分为2子结点。再然后就是“预剪枝”和“后剪枝”，预剪枝可以降低过拟合风险，而后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树。对待特殊类连续值处理，采用二分法，选取最优的划分点进行样本集合的划分。

决策树的优缺点

优点：

简单的理解和解释，树木可以可视化；
需要很少的数据准备，其他技术通常需要归一化。

缺点：

决策树学习者可以创建不能很好的推广数据的过于复杂的数，因为会产生过拟合。

python实现

ef choosebestfeaturetosplit(dataset):
    numfeatures = len(dataset[0]) - 1
    baseentropy = calcshannonent(dataset)#计算出原始的香农熵
    bestinfogain = 0.0;bestfeature =-1
    for i in range(numfeatures):
        #创建唯一的分类标签列表
        featlist = [example[i] for example in dataset]
#使用python语言原生的集合（set）数据类型，集合数据类型与列表类型相似，
#不同之处在于集合数据类型中的每个值都互不相同，从列表中创建集合是python语言得到列表
# 中唯一元素值得最快方式
        uniquevals = set(featlist)
        #条件熵的初始化
        newentropy = 0.0
        #计算每一种划分方式的熵
        for value in uniquevals:
            #划分获得数据集
            subdataset = splitdataset(dataset,i,value)
            prob = len(subdataset)/float(len(dataset))#概率
            #条件熵的计算
            newentropy += prob*calcshannonent(subdataset)
           
        #计算信息增益
        infogain = baseentropy - newentropy
        print("第%d个特征的信息增益为%.3f"%(i,infogain))
        #计算最好的信息增益
        if(infogain > bestinfogain):
            bestinfogain = infogain
            #找出最好的划分数据集的特征
            bestfeature = i
    return bestfeature
mydata,labels = createdataset()
print(mydata)
print("最优特征索引值："+str(choosebestfeaturetosplit(mydata)))