决策树

顾名思义。决策树由结点和分支组成，结点分为叶子节点和分支节点，分支节点代表的是分类的标准。叶子节点代表的是分类类别

特征选择

选取对数据具有分类能力的特征
基础知识：

自信息

X如果可以取三个值：x1,x2,x3,概率分别为p1,p2,p3。
那么-log(p1),-log(p2),-log(p3)相应称为x1,x2,x3的自信息，代表了它们各自的不确定性

信息熵

随机变量的不确定性。只依赖于X的分布而与其值无关只看概率大小而取值不影响
可以理解为对自信息的不确定性加权平均值这里的权就是发生的概率
H(X)=-p1log(p1)±p2log(p2)±p3*log(p3)

举例：描点法

条件熵

P(Y/X)已知随机变量X的情况下Y的不确定性，定义为数学期望注意X是一个定属性，可能有n个值，分别计算这n个值下Y取不同值的熵再相加，如果Y有k个值，相当于计算n*K个式

信息增益：等价于互信息

信息增益=经验熵-经验条件熵，显然我们理解为，经验熵指的是D的不确定程度，经验条件熵指的是在A的条件下D的不确定程度，两者的差就是不确定程度的衰减量，即我们要做的就是选择信息增益最大的特征

如何计算信息增益？

例子：

信息增益比

当训练数据集经验熵较大时，信息增益值会偏大。较小时会偏小。使用信息增益比可以对其矫正

建立决策树

ID3

建树方法：A指的是特征，C指的是实例的分类值
1：从D中所有实例都属于同一类Ck，则不用继续分类，返回树
2：若不属于同一类Ck，依次计算每一个特征A的信息增益，并选择最大的信息增益
3：若最大的信息增益大于信息阈值，则将其作为当前根节点，按照Ai=ai可能的取值将实例划分为|Ai|棵子树，每一棵子树递归调用步骤1
4：若最大的信息增益小于信息阈值，则置当前结点为根节点，并将D中实例数最大的类Ck作为该结点的类标记因为没有明确的分类特征了，防止过拟合，采用多数表决规则

缺点：容易过拟合

C4.5

与ID3类似，只不过将信息增益改为信息增益比，用信息增益比来选择特征

剪枝操作

因为上述的生成树算法是划分到没有其他类节点为之，这样对训练集是提高准确率，但是却会导致过拟合，所以需要采取剪枝操作

首先理解损失函数：这里的是特殊的损失函数，意义是使得变量的不确定性最小
Ca(T)由三部分组成：
Ht(T)：指的是根节点下的某一分区内变量的互信息，也就是变量的加权平均不确定性
Nt：由于加权平均不确定性只和分布有关，所以需要乘以Nt来引入样本量例如样本区1里有80个A，20个B，样本区间2里有8个A，2个B，两者带来的贡献肯定是不同的，但是互信息是相同的，所以必须乘以样本数
α|T|：

剪枝算法：后剪枝

应该是从带有叶结点的分支节点开始吧？
理解一：
比如对于那个被剪枝的节点A【左下角的分支节点】
在作为分支节点时，其损失函数为Ca(T)–
而假设剪枝，即作为分支节点
C(T)=-1*N∑ Ni/N * log(Ni/N)+α|T-2|

如果Ca(T)》（T）则要剪枝，反之则不剪枝

理解二：根据准确率计算。剪枝前整个模型的精确到如果小于剪枝后，则剪枝

Cart

分为回归树和分类树，生成的树都是二叉树
回归树是预测连续型变量
分类树是预测离散型变量

回归树

有点难理解
1：
首先“”选择最优切分变量”：当x有很多维度，每一维相当于一个特征，那么我们需要遍历每一维x(1)-x(k)
“选择切分点”：当选择第x(k)维度的时候，利用启发式法感觉就是穷举法，将x(k)上的值排序，并且尝试所以划分空间，即将x(k)上的值划分为两个空间。对于x(k)上的n个不同值x1-xn，有n-1种划分方法
2：

因为我们已经划分好了两个空间选择的是第x(k)维度，(x1(k)-xi(j)和(xi+1(k)，xn(j)))的划分策略，两个空间可以计算出预测值c1和c2，分别在彼此的空间中求得平方均差，相加
我们需要比较所有维度的所有值划分(K*N)次划分的平方均差，取得最小值得均差就是我们想要的第J维度的第（1-K）（K-N）划分

3：划分好两个空间后，对两个空间分别进行1,2。直到满足停止条件不明白，难道是划分尽后再剪枝？
关于预测值c1和c2如何计算：
对于第x(k)维度的(x1(k)-xi(j)）划分，我们可以想象要求得预测值就是通过实例获得值，这里损失函数定义为均方损失函数

这里yi等于xi(k)实例所对应的y值，f(xi)是预测值
对于f(x)整体求导，得到

所以可以看到，使得损失函数最小的预测值，就是所以空间里y的均值

这里有个实例，因为太长就不拷贝过来，如果还是不能理解就看看实例
https://blog.csdn.net/weixin_40604987/article/details/79296427#commentBox

4：当选择最小的第x(k)维度的(x1(k)-xi(j)）划分后，落在此区间的值即为f(x),区间内y的平均值【当此区间是叶子节点的话】

分类树

基本概念：基尼系数

对于特征x(k)的某一取值xi(k)，可以将样本划分为两个区间x(k)=xi(k)和x(k)!=xi(k)，这样就划分为两个子空间，则对应的基尼系数

基尼系数的意义：与信息熵类似，都是代表不确定性。基尼系数越大，样本的不确定性越大。例如对于二分分类，第一个类的概率P 则Gini§=2p(1-p)，若p=1或者0，样本不具有不确定性，对应的Gini=0。若p=1/2，对应的基尼不确定性最大，同样样本的不确定性也最大。
只不过基尼系数可以进行二叉分类，而信息熵不可以

生成算法

例子：

CART的剪枝