决策树

决策树和随机森林

概念

Decision Trees (DTs) 是一种用来 classification 和 regression 的无参监督学习方法。其目的是创建一种模型从数据特征中学习简单的决策规则来预测一个目标变量的值

分类的决策树

1. 树形结构
2. 基于特征，对实例进行分类的过程（if … else的集合）
3. 优点:可读性好，分类速度快

优势

1. 便于理解和解释
2. 训练需要的数据少
3. 可视化

缺点

1. 构建复杂,无法泛化
2. 数据微小变化,生成树不同
3. 贪心算法,无法全局最优

学习步骤

1. 特征选择
2. 决策树的生成
3. 决策树的修剪

算法思想

1. ID3
2. C4.5
3. CART

决策树模型

有结点（特征或属性）和叶节点(类)

特征的选择

信息增益和信息增益比

1. 信息增益值是相对于训练样本的

随机森林（Random Forest）

随机森林也是基于决策树的算法，只不过是利用集成的思想来提升单颗决策树的分类性能。主要特点是由于随机选择样本和特征，所以不容易陷入过拟合

优点:

• 在当前的很多数据集上，相对其他算法有着很大的优势，表现良好。
• 它能够处理很高维度（feature很多）的数据，并且不用做特征选择(因为特征子集是随机选择的)。
• 在训练完后，它能够给出哪些feature比较重要。
• 训练速度快，容易做成并行化方法(训练时树与树之间是相互独立的)。
• 在训练过程中，能够检测到feature间的互相影响。
• 对于不平衡的数据集来说，它可以平衡误差。
• 如果有很大一部分的特征遗失，仍可以维持准确度

缺点:

• 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
• 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。

算法步骤

• 随机选取n个样本,并从中选择k个属性,选择最佳分割属性作为节点建立分类器(CART,SVM)
• 重复以上m次,建立m个分类器,通过投票表决结果,决定数据的类别

提升树

• AdaBoost AdaBoost算法是提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样做的结果就是，使得被错误分类的样本能得到更多关注,AdaBoost采取加大分类误差率小的弱分类器的权值，使其起较大作用，并且减少分类误差率大的权值。可见，这里的决定因素就是这个分类误差率的大小
• GBDT 算法简述是每次迭代生成一颗新的决策树，计算损失函数在每个训练样本点的一阶导数gi和二阶导数hi ，然后通过贪心策略生成新的决策树。计算每个叶节点对应的预测值 ，并将新生成的决策树添加到模型中