算法整理模板01

算法整理模板01"/>

算法整理模板01

STEP1：整体概况
决策树是一种对样本进行分类的树形结构，也能够进行回归预测。决策树主要包含3种结点：根节点——初始结点；叶节点——最终分类结果结点；内结点——树内部进行判断的条件结点-即特征，在决策树中，每一个样本都只会被一条路径覆盖。

STEP2：生成原理
决策树常见的生成算法有三种，ID3，C4.5以及Cart。以ID3算法为例介绍一下决策树的生成原理。
第一步，计算信息增益。ID3算法是利用信息增益进行特征选择的。信息增益是指，已知某一特征xi后，使得样本整体特征不确定性减少的程度。
第二步，在每个节点上利用信息增益进行特征的选择，在选择特征时，优先选择信息增益最大的特征。直到剩余特征的信息增益小于阈值、或已经没有特征可以选择时终止。
第三步，对决策树进行剪枝优化。构建决策树的损失函数（与预测误差以及树的复杂度有关），将每一个叶节点回缩到上一层父节点，对损失函数最小的叶节点进行修剪。
C4.5算法的过程与ID3类似，只是使用了信息增益比而非信息增益进行计算。信息增益比是指在信息增益的基础之上乘一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。而CART算法则是使用基尼指数进行计算。基尼指数是指样本被某一特征分割后，整个样本集合不确定性程度的大小，基尼指数越小，样本集合被分割后的不确定性越小。

STEP3：优缺点
决策树的优势包括：输出树形图可解释性较强，if-then形式，逻辑很好理解；对输入数据的属性要求低（分类，连续）；
劣势包括：当数据集特征维度很多时，决策树会生成许多枝干，或者树非常深，陷入过拟合；判定过程很规则化，容易被识破并攻击。

STEP4：应用场景
决策树的应用场景十分广。可以用来评估贷款风险；可以辅助医生选择诊断模型；也可以用于垃圾邮件的分类判断。

STEP5：手推
【熵】、【信息增益】、【信息增益比】、【基尼指数】、【损失函数】的公式；
CART算法【回归树】、【分类树】的生成方式推导。

STEP6：延伸提问
（1）信息增益比和信息增益相比，有什么优势？
（2）如何解决决策树的过拟合问题？（剪枝、交叉验证、筛选特征）
（3）预剪枝和后剪枝？（参考树的高度、叶子结点的数量、不纯度等、在生成决策树前（后）进行剪枝）
（4）随机森林（这里同样从整体概况、原理、优缺点等进行整理）
（5）Bagging和Boosting的区别？（样本的抽取；样本的权重；是否并行计算等）
（6）GBDT\XGBOOST