决策树既可以用来做分类【分类树】，又可以做回归【回归树】。
决策树由三个部分构成：
根节点：第一个选择点
非叶子节点和分支：中间过程
叶子节点：最终的决策结果
过程：利用给定的训练集构造一棵树，根据构造的树，把测试集从上到下走一遍
所以关键是如何选择特征来构造决策树
三种方法：ID3【按照信息增益计算】、C4.5【按照信息增益比计算】、CART【按照CINI系数计算】
分类树
例子：
image.png
1）ID3
衡量标准：熵【表示随机变量不确定性的指标】，熵值越大，不确定性越高
当时，
等于0 ，达到最小，完全没有不确定性；
当时，
等于1，达到最大，不确定性最大。
另外选择节点的最终标准是信息增益【表示特征X使得类Y的不确定性减少的程度【熵的下降程度】】，将信息增益最大的特征作为根节点，以此类推。
第一轮：
原始数据的熵值：
yes：9个，no：5个
如果按outlook分类：
sunny：yes有2个，no有3个，即取得sunny的概率为5/14
sunny类的熵值：
overcast：yes有4个，no有0个，即取得overcast的概率为4/14
overcast类的熵值：0
rainy：yes有3个，no有2个，即取得rainy的概率为5/14
rainy类的熵值：
综上，按outlook分类的熵值为【此处计算的实际是条件熵】
信息增益为0.940-0.693=0.247
同理
如果按temperature分类:
hot类：取hot的概率是4/14
熵值为：
mild类：取mild的概率是6/14
熵值为：
cool类：取cool的概率是4/14
熵值为：
综上，按temperature分类的熵值为
信息增益为0.940-0.911=0.029
按humidity分类：
normal类：取normal的概率是7/14
熵值为：
high类：取high的概率是7/14
熵值为：
综上，按humidity分类的熵值为
信息增益为0.940-0.7885=0.1515
按windy分类：
True类：取True的概率是6/14
熵值为：
False类：取False的概率是8/14
熵值为：
综上，按windy分类的熵值为
信息增益为0.940-0.892=0.048
根据信息增益比最大的原则，选择特征outlook为根节点。
现在的决策树长这样：
绘图1.jpg
由上图可知，当outlook等于overcast，可以得出肯定会去打球的结论，不需要再切分，下面对sunny和rainy继续切分
第二轮：
sunny类：当前样本的熵值等于
绘图1.jpg
最终生成5个叶子节点
但是ID3算法会偏向于取值较多的特征：当特征取值较多时，分类结果的纯度较高，不确定性越低，熵值越低，信息增益比越大。
2）C4.5【信息增益比】
为了解决这个问题，引入了信息增益比指标
image.png
信息增益比等于信息增益除以自身的熵值，相当于乘了一个惩罚项，当该特征取值较多时，不确定性较高，熵值较大，它的倒数较小，信息增益比较小，被选择为节点的可能性降低。
但是，反之，当特征取值较少时，不确定性较低，熵值较低，它的倒数较高，信息增益比较大，被选择的可能性较高，因此C4.5偏向于选择特征取值较少的为节点。
上述例子如果用C4.5作为衡量标准，结果如下：
第一轮：
按outlook分类：信息增益比为
绘图1.jpg
最左边和最右边的节点可以同理继续切分
3）CART【GINI系数】
image.png
以outlook和temperature为例
微信图片_20190220142714.jpg
微信图片_20190220142725.jpg
计算得出outlook的最佳切分点为{{rainy}，{sunny，overcast}}，GINI系数为0.457；
temperature的最佳切分点为{{mild}，{hot，cool}}，GINI系数为0.458
我所理解的应该是根据每个特征的最佳切分点对应的GINI系数，选择系数最小的作为节点以及切分点。
回归树
这一块在学习的时候是我觉得不太容易理解的，这里参考了https://blog.csdn.net/weixin_36586536/article/details/80468426和https://blog.csdn.net/Albert201605/article/details/81865261博主的内容
image.png
这个类似于CART算法，
首先遍历所有特征，对每一个特征的每个切分点，得到两个分支各自的标签值，计算两个分支各自的离差平方和，将这两块离差平方和之和作为这个切分点的离差平方和，将最小的离差平方和所对应的切分点为该特征的最佳切分点，以此类推，得到第一层的根节点，然后对每个分支重复执行上述步骤，直至得到最终的决策树，叶子节点输出的是该分支标签值的平均值，当有新的特征输入时，从上到下走一遍决策树，输出相应叶子节点的标签值。
网友评论