treeq.png
决策树主要包括ID3，C4.5以及CART。下面给出三种算法的说明：
image
image
CART
首先看下面表格中的示例数据(随机生成，仅供参考)。其中年龄，身高，月收入为连续变量，学历，工作为离散变量。
如果把动心视为目标变量，此问题为分类问题。
如果把动心度视为目标变量，此问题为回归问题。
image
CART的目的是生成一个类似下面这样的树：分类树或者回归树。
image
叶子节点若为Y或者N，是分类树；若是数字，则为回归树。下面分别讲述回归树和分类树的生成方式。
image
分类树
D3算法使用信息增益来选择特征，信息增益大的优先选择，这种方式会使得特征值较多的特征容易被选择【示例数据中的学历可能会比工作优先选择，因为学历有3个值，而工作有2个值】。
在C4.5算法中，采用了信息增益比来选择特征，改进了ID3容易选择特征值多的特征的问题。C4.5也是优先选择较大的。
上述2者都是基于信息论的熵模型的，这里面会涉及对数运算，因此计算成本较大。
CART分类树算法使用基尼系数，既减少了计算成本，又保留了熵这种运算形式的优点。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。
基尼系数
对于一个样本集合S，假设其包含m个不同的值，这m个值可看作m个不同的类。其中由类i组成的集合为Si，那么对于属于类i的样本点k而言，其概率为P(k)=集合Si的样本个数除去集合S的样本个数。则基于概率分布的基尼指数定义如下：
image
其中符号“||”为计算集合内元素个数的符号，对于m等于2的情况，上面的式子等价与
image
如果样本集合S，被某个规则R划分为n个数据子集，分别为S1， S2，……， Sn，则此时的计算基尼系数公示如下：
image
在CART算法中，上述n的值一定为2。因为每一次分裂，都是把数据集合一分为二。示例计算说明可点击。
树的结果
叶子节点数据集中，目标变量中占多数的类别，为这个叶子节点的输出类别。如果把上面给定的示例数据集看作一个叶子节点的话，如果某条数据正好落在这个数据集内，则这个数据的分类为N，因为这个数据集中有6条数据为N，多于为Y的数据条数。
image
回归树
以上面给出的示例数据为例，下面说明生成回归树的方式。将数据集合定义为D。
离散变量：以学历为例
将数据集合D分为Dsp1=D(学历=专科)以及Dsp2=D(学历!=专科)，其中Dsp1中动心度构成的集合为Msp1，均值为asp1；Dsp2中动心度构成的集合为Msp2，均值为asp2；计算2个数据子集合的误差序列方差的和值：
image
类似于MSE(sp)，遍历所有学历中的值，得到下面的MSE(ms)，MSE(dr)。
image
其中
数据集Dms1=D(学历=硕士) 以及 Dms2=D(学历!=硕士)，Dms1中动心度构成的集合为Mms1，均值为ams1；Dms2中动心度构成的集合为Mms2，均值为ams2；
Ddr1=D(学历=博士) 以及 Ddr2=D(学历!=博士)，Ddr1中动心度构成的集合为Mdr1，均值为adr1；Ddr2中动心度构成的集合为Mdr2，均值为adr2。
连续变量：以身高为例
将身高的所有值去重后按照从小到大的顺序排列，得到集合H=[166,173,175,180], 取相邻两个数的中间值得到集合MH=[169.5,174,177.5],接下来的计算就类似于离散变量的情况，挨个遍历，把数据分为小于、大于这2个数据子集。以169.5为例，把数据集分为Dn169.5=D(身高<169.5)和Dm169.5=D(身高>169.5)，数据子集相应的动心度组成的集合分别为Mn169.5,Mm169.5,集合相应的均值为an169.5, am169.5。详细计算过程可点击。
树的输出
树是通过一个个叶子节点决定输出的。输出的方式也包括2种：
回归树：叶子节点代表的数据子集中目标变量的均值，就作为输出值。例如示例中的叶子节点，其输出值为0.56+0.52=0.54。当要预测的某条数据恰好属于这个数据子集，则针对这条数据的动心度的预测值就是0.54。
模型树：对于一个叶子节点来说，有输入，也有对应的输出。根据输入和输出的关系，建立模型，这个模型可以是线性回归，也可以通过神经网络来建立。这个叶子节点的输出值是所建立的模型的输出值。当要预测的某条数据恰好属于这个数据子集，则针对这条数据的动心度的预测值就是将数据带入建立的模型中得到的值。
image
树到了这里还没有完，关于树的剪枝算法以及实例代码可点击。下面给出结果图展示：
分类树：成年人收入数据集
image
分类树：鸢尾花数据集
image
回归树：结果对比曲线
image
作者：AiFan
链接：https://www.jianshu.com/p/4430896b1cf5