决策树的一个重要任务是为了数据中所蕴含的知识信息

  • 决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,在这些机器根据数据集创建规则时,就是机器学习的过程
  • k-近邻算法可以完成很多分类任务,但是它最大的缺点就是无法给出数据的内在含义,决策树的主要优势就在于数据形式非常容易理解

决策数的构造

  • 优点:计算复杂度不高,输出结果易于理解,对中间值对缺失不敏感,可处理不相关特征数据
  • 缺点:可能会产生过度匹配的问题
  • 适用数据类型:数值型和 标称型

构建决策树的第一个问题:当前数据集上哪个特征在划分数据分类时起决定性作用

  • 为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。
  • 完成测试之后,原始数据集就被划分为几个数据子集
  • 这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型,则当前条件已经正确地划分数据分类, 无需进一步对数据集进行分割。
  • 如果数据子集内的数据不属于同一类型,则需要重复划分数据子集的过程

思路
检测数据集中的每个子项是否属于同一分类:
If so return 类标签;
Else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBranch并增加返回结果到分支节点中
return 分支节点

决策树的一般流程

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

划分数据集的大原则是:将无序的数据变得更加有序
组织杂乱无章数据的一种方法就是使用信息论度量信息,可以在划分数据之前或之后使用信息论量化度量信息的内容
在划分数据集之前之后信息发生的变化称为信息增益(information gain) 知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。
集合信息的度量方式称为香农熵或者简称为熵, 熵定义为信息的期望值

划分数据集
递归构建决策树


Artificial Intelligence   Machine Learning   Algorithm      Machine Learning Algorithm 决策树

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!