机器学习：决策树总结

【写博客的目的是促使自己进行总结，同时也将所学分享给大家，故对文中所述，若有疑议，均可留言讨论，将喜不自胜】
决策树是一种基于树状结构进行决策的策略，是一种有监督的机器学习算法

决策树优点：
　　简单易懂
　　易解释
　　可视化
　　适用性广
　　既可以处理离散值也可以处理连续值(ID3只能处理离散值)
　　可用于寻找重要特征变量
　　不需要提前归一化预处理
　　使用决策树预测的代价是$O(log_2m)$O(log2​m)， m为样本数。
决策树缺点：
　　容易过拟合。可以通过设置节点最少样本数量和限制决策树深度来优化。
　　决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
　　有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
　　每一个节点的选择都是贪婪算法，不能保证全局最优解。可以通过集成学习之类的方法来改善。
　　如果某些特征(label)的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

构造决策树的两大核心问题：如何选出最佳分支(特征)与最佳节点(特征节点)、剪枝策略(防过拟合)
如何选出最佳节点和最佳分支
　　采用贪心算法，每一步都选择最好的节点分支（以局部最优策略选择），而非死磕全局最优
决策树剪枝策略
　　决策树过拟合风险很大，理论上可以将类别完全分开，即在训练样本上实现100%的准确率
　　剪枝策略：
　　　　预剪枝(贪心算法思路)：边建立决策树边进行剪枝的操作
　　　　　　控制树的深度。 样本数和节点数
　　　　　　叶子节点个数，叶子节点样本数，信息增益量
　　　　后剪枝：完成决策树后进行剪枝操作，实用
　　　　　　通过一定的衡量标准
　　　　　　叶子节点越多，损失越大
后剪枝比预剪枝更为优越，通常它会保留更多的节点并具有更强的泛化能力，但是，由于需要构建完整的树并且验证多个节点，模型的复杂程度会更高。

重要概念：
熵：描述物质系统状态可能出现的程度，混乱状况，一般介于0~1之间，0是理想状况。对于
一组数据，分类后熵越小，说明分类效果越好
单一变量信息熵的计算公式：

多变量的联合熵的计算：

有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们在知道Y以后X剩下的不确定性。

互信息【也称之为，信息增益】I(X,Y) = H(X) - H(X|Y)，度量了X在知道Y以后不确定性减少程度

决策树的三种算法说明：
ID3 (信息增益entropy) 选择信息增益最大的分割属性，即熵减程度最大，即分类后熵最小结
果
适用于属性少（属性过多时，可以适当删除）。
信息增益反映的给定一个条件以后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是条件熵越小，信息增益越大，故容易过拟合
不足：仅处理离散数据类型，且极容易过拟合，现在很少使用ID3

C4.5(信息增益比率entropy) 选择信息增益比率(公式如下)最大的分割属性，
C4.5是针对ID3提出的，某特征中值的种类越多，特征对应的信息熵越大，它作为分母，可以校正信息增益导致的问题。
既可处理离散值，也能处理连续属性的数据
现在的C5.0则是对C4.5的进一步改进【大数据的商业场景应用】

C4.5不足：
由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。

CART产生背景：为了能简化模型且减少运算强度但又不牺牲太多准确性。这也是CART分类效果
优于其他决策树的理论根基
CART(最小基尼指数) 基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
既可处理离散值，也能处理连续属性的数据
属于二叉树，只能将一个父节点分为两个叶节点。

对比：ID3与C4.5算法只为叶子结点分配类别，而CART考虑到每个结点都有成为叶子结点的
可能，对每个结点（包括叶子结点与非叶子结点）都分配类别。

【未完待续。。。】