随机森林——sklearn库
多个决策树的组合优化目标：找到尽可能趋向于最优的决策树（叶子结点数最少、叶子结点深度最小）。
泛化能力：预测未知样本的能力
关于过拟合：
树的结构越复杂过拟合的可能性越大
--->剃刀法则：具有泛化误差（即预测误差）的两个模型，选择更简单的模型，将另一个模型剔除。
--->后剪枝法：对完整的树剪去置信度不高的子树，将分支用叶节点去代替。
--->预剪枝：1）树的深度达到一定值后停止生长；2）到达节点的实例具有相同的特征向量，而不一定属于同一类，也可停止生长；3）到达节点的实例少于一定数额也可停止生长；4）扩展对系统的增益小于某阈值也可停止生长
决策树：在多个条件属性的综合作用下得到最终的决策属性的值
特征分裂：从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选取最优的特征
ID3：采用信息增益最大的特征
C4.5：采用信息增益比选取特征
CART：采用基尼系数最小化标准选取特征【由二元逻辑问题生成，每个节点只有两个分支】
信息熵：度量一个属性的信息或者说信息的不确定性、不纯度
\(Entropy(S)=-\sum_{i=1}^{m} {p_i*log_2{p_i}}\)
其中，\(p_i\)为每个属性各个取值的占比
熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱
信息增益：决策属性的熵和按条件属性不同取值划分后样本数据集的不纯程度（熵）的差值
\(Gain(S,A)=Entropy(S)-Entropy_A (S)\)
表示属性A在集合S上的信息增益，其中
\(Entropy_A(S) = \sum_{i=1}^{k} \frac{|S_i|}{|S|}Entropy(S_i)\)
其中，属性A有k个不同的取值，从而将S划分为k个样本子集\(｛S_1,S_2,...,S_k｝\)，\(|S_i|\)、\(|S|\)分别表示样本集中的样本个数
信息增益越大表示按照属性A划分的样本越纯，越有利于分类
在未选择的属性（特征）中选择最大信息增益的属性作分裂
ID3：
信息增益Gain\(Gain(S,A)=Entropy(S)-Entropy_A (S)\)
选择Gain最大的属性作为节点N的测试属性，该属性的每个取值作为一个分支，每个子节点作为一个新的数据集继续选择Gain最大的属性；如果没有其他属性待选择，则节点N为叶子，选择其中占比最大的类别作为结果输出【也就是最终结果的值】
C4.5：ID3的一个扩展，引入后剪枝算法、以及连续性变量的离散化
信息增益率
\(GainRatio(S,A)=\frac{Gain(S,A)}{-\sum_{i=1}^{k}{\frac{|S_i|}{|S|}log_2\frac{|S_i|}{|S|}}}\)
对于非离散数据、不完整数据也能处理，步骤如下：
将连续性属性A的n个值按照升序排列；将相邻两个元素中间值作为划分，共n-1个；计算这n-1种划分方法对应的信息增益；选择最大的作为A属性的二划分阈值。
PEP剪枝:根据剪枝前后的错误率来判断是否进行子树的修剪，不需要单独的剪枝数据集。一个叶子节点错误率的计算公式如下：
\(ErrorRatio = \frac{e+0.5}{n}\)
其中，n表示节点覆盖的样本数量，e表示n个样本中错误的个数，0.5是惩罚因子。一个子树的错误率就是子树的全部叶节点的错误率的平均。**如果剪枝后的新增叶子节点的错误均值小于等于被剪掉的子树的错误均值与标准差的和，则满足剪枝条件进行剪枝。
缺失值的处理：赋予同节点样本的插值或者简单地忽略调含有缺失值的样本。
缺点：只能在内存上进行；多次顺序扫描和排序导致算法效率低，尤其在连续属性上更为突出；选择分裂属性的过程中没有考虑到条件属性之间的相关性，仅考虑各条件属性和决策属性之间的期望信息。
属性分裂点：信息增益率最大的属性
CART:
回归树：平方差最小化准则
分类树：Gini系数最小化准则
假设决策属性一共有m种取值，则基尼指数的定义如下：
\(Gini=1- \sum_{i=1}^{m}{P_i^2}\)
未完待续...