决策树

Posted on Edited on In

机器学习 —1 分类篇

决策树学习小结

  1. summary
  • 优点: 
         1. 计算复杂度不高
        2. 输出结果易于结束,
        3. 对中间值不敏感,可以处理不相关特征数据
  • 缺点:易产生过拟合现象
  • 适用数据类型:数值型和标称型
  1. 主要流程

1: 收集数据
2: 准备数据: 树的构造算法只适用于标称型数据, 因此数值型数据必须离散化
而且不能处理缺失值, 在执行算法之前必须处理缺失值
3: 分析数据: 可以适用任何方法, 构造树完成之后, 我们应该检查图形是否符合预期
4: 训练算法: 构造树的数据结构
5: 测试算法: 适用经验树计算错误率
6: 适用算法: 此步骤可以适用于任何监督学习算法, 而使用决策树可以更好的理解数据的内在含义

  1. 核心问题
  • 如何划分?
    1. 如何决定测试条件的分配 (划分节点时, 使用什么特征?)
    2. 如何决定最好的划分?—————- 贪心策略
  • 何时停止划分

3.1 如何决定测试条件的分配

1
由特征的类型以及分类的种类(形成2叉树,还是多叉树)有关系

3.2 贪心的策略:

1
在不同的划分策略中,选择划分结果中,**子节点不纯度最高**(less impurity&&homogeneous class)对应的划分结果

如何评价 impurity?

总结

评价不纯度的方法 使用这种方法相应的算法
GINI SLIQ, CART , SLIQ ,SP RINT1
GAIN ID3 C4.5

3.2.1 GINI

k单个结点的不纯度计算
$GINI(t) = 1 -\sum_[p(j|t)]^2$

其中 t:表示结点t,GINI(t) 表示该结点t的不纯度的$p(j|t)$表示类别 j 在结点 t 中所占的比例

计算这整个划分方法:
连续型数值类型

3.2.2Entropy

3.2.3Misclassification error

计算公式:

​ $Error(t) = 1 -max_iP(i|t)$

何时停止划分结点?

  1. 当结点中所有的样本都属于同一个类别时
  2. 当结点中所有样本的特征值比较类似时, 虽然不属于同一类, 但是某些指标还是比较好的
  3. 剪枝策略

其他关于本话题的链接:

C4.5 : https://wizardforcel.gitbooks.io/dm-algo-top10/content/c4.5.html