Random Forest
Last updated
Last updated
见李航的《统计学习方法》
应思考的几个问题
属性值应当完全二值的还是多值的？或者节点的分支数应该是几?(CRAT和random forest是二叉树，ID3，C4.5等都是多叉树)
如何确定某节点出应该测试哪个属性
何时可以令某个节点成为叶子节点，即合适停止分裂。（1叶子节点很纯，2分裂后信息增益或gini系数或xgboost中的“gini”系数小于阈值）
如果树生长的“过大”，如何“剪枝”使得它变小变简单（误判，以父节点“作为”叶子节点，对比子节点的预测效果，若更优，则删除子节点）
如果叶子节点仍然不“纯”，那么怎么给他赋类别标签（以比较多的那类样本标签作为该节点的类别标签）
缺省属性的数据如何处理（随机森林中就包含着随机选择属性）
如果有些训练样本或者待分类样本缺失了一些属性值，那么该如何处理？要解决这个问题，需要考虑3个问题：
i)当开始决定选择哪个属性用来进行分支时，如果有些训练样本缺失了某些属性值时该怎么办？
ii)一个属性已被选择，那么在决定分支的时候如果有些样本缺失了该属性该如何处理？
iii)当决策树已经生成，但待分类的样本缺失了某些属性，这些属性该如何处理？针对这三个问题，昆兰提出了一系列解决的思路和方法。
对于问题i),计算属性a的增益或者增益率时，如果有些样本没有属性a，那么可以有这么几种处理方式：
(I)忽略这些缺失属性a的样本。（这种适合于只含少量缺失值的情况）
(C)给缺失属性a的样本赋予属性a一个均值或者最常用的值。
(R)计算增益或者增益率时根据缺失属性样本个数所占的比率对增益/增益率进行相应的“打折”。
Gain(A)=属性 A 在数据集中不空的比率 × ( Entropy(S)−Entropy_A(S) )
(S)根据其他未知的属性想办法把这些样本缺失的属性补全。
对于问题ii)，当属性a已经被选择，该对样本进行分支的时候，如果有些样本缺失了属性a,那么：
(I)忽略这些样本。
(C)把这些样本的属性a赋予一个均值或者最常出现的值，然后再对他们进行处理。
(R)把这些属性缺失样本，按照具有属性a的样本被划分成的子集样本个数的相对比率，分配到各个子集中去。至于哪些缺失的样本被划分到子集1，哪些被划分到子集2，这个没有一定的准则，可以随机而动。
(A)把属性缺失样本分配给所有的子集，也就是说每个子集都有这些属性缺失样本。
(U)单独为属性缺失的样本划分一个分支子集。
(S)对于缺失属性a的样本，尝试着根据其他属性给他分配一个属性a的值，然后继续处理将其划分到相应的子集。
对于问题iii)，对于一个缺失属性a的待分类样本，有这么几种选择：
(U)如果有单独的缺失分支，依据此分支。
(c)把待分类的样本的属性a值分配一个最常出现的a的属性值，然后进行分支预测。
(S)根据其他属性为该待分类样本填充一个属性a值，然后进行分支处理。
(F)在决策树中属性a节点的分支上，遍历属性a节点的所有分支，探索可能所有的分类结果，然后把这些分类结果结合起来一起考虑，按照概率决定一个分类。
(H)待分类样本在到达属性a节点时就终止分类，然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。
剪枝
C4.5算法与ID3算法相似，但：
能处理连续值的特征，对连续值进行离散化
能够处理缺失值
能剪枝
生成节点过程中使用的是信息增益比来选择特征
信息增益：特征A对训练集D的信息增益,为集合D的经验熵与特征A给定条件下D的经验条件熵之差。
信息增益就是互信息
信息增益比：特征A对训练集D的信息增益，为其信息增益与经验熵之比。 C4.5选择信息增益比，是因为信息增益值的大小受训练数据集经验熵影响。
ID3和C4.5只能做分类，而CART既可以处理分类，也可以处理回归。
CART算法采用一种二分递归分割的技术，与基于信息熵的算法不同，CART算法对每次样本集的划分计算GINI系数，GINI系数可以衡量纯度，与熵有类似性质，所以GINI系数越小则划分越合理。CART算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。
Logistic Regression Vs Decision Trees Vs SVM
Why are we growing decision trees via entropy instead of the classification error?
