目录

ID3算法

C4.5算法

CART树

ID3算法

定义:在决策树各个结点上应用信息增益准则选择特征，递归的构建决策树。该决策树是多分支分类。

信息增益

意义：给定特征X的条件下，使得类别Y的信息的不确定性减少的程度。取值越大越好。

定义：集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D/A)之差。

缺点

• 分支过程中偏向取值较多的属性
• 无法处理连续值和缺失值，只能处理离散值
• 对缺失值敏感。

C4.5算法

定义：C4.5算法与ID3算法类似，C4.5算法使用信息增益比来选择特征。C4.5算法先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益比最大的属性。该决策树是多分支分类。

信息增益比

定义：在信息增益的基础上，再除以H(D)；取值越大越好。

连续属性的划分：采用"二分"法对连续属性进行离散化，划分点的选取可选使信息增益最大化的划分点。例:16个连续属性值选15个划分点。

缺点

• 分支过程中偏向取值较少的属性；
• 适合小样本
• 要进行剪枝操作；要对属性进行排序

CART树

CART树既可以用于分类，也可用于回归。CART树属于二叉树。

回归树

定义：使用平方误差来构建决策树，使用min(J){min(c1)sum(y-c1)^2+min(c2)sum(y-c2)^2}来选择最优划分变量和最优划分点。

预测：选择叶子节点的均值或者中位数作为当前节点的预测类别(通常都是均值)

分类树

定义：使用基尼系数选择最优特征。

基尼系数：

定义:从数据集中随机抽取两个样本，其类别标记不一致的概率。基尼系数越小，则样本集合的不确定性越小。

公式:1-sum(K){P(k)*P(k)},P(k)是属于第k个类别的概率，共有K个类别。

预测：选择叶子节点里概率最大的类别作为当前节点的预测类别；选择叶子节点中所有样本所属类别最多的那一类。

缺点:适合大样本

预剪枝：

过程：进行分支前，计算验证机准确率；分支后，计算验证机准确率，若变大，则进行分支，反之。

缺点：欠拟合风险较高。

后剪枝:

过程：当前决策树计算非叶子节点再验证集上的准确率，讲该非叶子节点替换为叶子节点后，计算验证机的准确率，若变大，则进行剪枝，反之。

决策树对缺失值的处理

• 删除缺失数据
• 用其他值猜测缺失项的可能值，如中位数、众数等，或者用已有数据构建模型，然后对缺失值进行预测
• 概率化:C4.5算法中，按比例对所有样本分配权重
• xgboost中，将缺失值分别导流到各个分支中，然后计算每个分支对损失函数的影响，该该缺失值分配到使得损失函数最小的分支。

树模型的优缺点

优点

• 可解释性强
• 可处理混合类型特征
• 不需要归一化
• 有特征组合、特征选择的作用
• 能够处理缺失值
• 对异常点鲁棒
• 可扩展性强，容易并行

缺点

• 却反平滑处理(回归预测的输出值只能输出若干种值)
• 不适合处理高维稀疏数据

树模型能够处理缺失值吗？(ID3、c4.5、cart、rf到底是如何处理缺失值的？ - 知乎)

1.ID３不能处理

2.C4.5的处理方式：概率权重思想

• 特征值缺失，如何进行特征选择？用没有缺失的样本子集计算信息增益，再乘以权重(无缺失样本的比例)，即为特征再数据集上的信息增益。
• 选定该划分特征，对于缺失该特征值的样本如何归类？将该缺失值同时划分到所有子节点种，并调整该缺失样本权重(该子节点在特征上取值的样本比例)，即以不同概率将样本划分到所有节点种。

3.CART中可用surrogate splits(替代划分)来处理

• 特征值缺失，如何进行划分特征的选择？用没有缺失的样本子集来计算Gini指数(均方误差)，再乘以一个权重(无缺失样本的比例)，即为特征再数据集上的Gini指数(均方误差)
• 选定该划分特征，对于缺失该特征值的样本如何归类？首先，需要遍历剩余的特征，但是仅仅再完全没有缺失值的特征上进行选择，我们选择其中能够与目标缺失特征分裂之后效果最接近的特征值代替缺失值；如果不满足这个条件，缺失样本默认进入样本个数较多的叶节点。

对于sklearn库来说，是不能的，需要填充；而对于xgboost这种是可以的。

预测截断，遇到特征有缺失情况，如何处理?

样本默认分到右子树。