前言

本文参考文献：《人工智能原理与应用》第四版

✨大家好，我是“Ghost&”，一名大学生。
🌍主页链接：Strange&的个人博客主页
☀️博文的主要方向是：课程学习知识、作业解题、期末考试准备。随着专业的深入，会越来越广泛……一起期待吧。
❤️一个“不想我做的不好成为你的遗憾”的博主。
💪很高兴认识你，让我们一起努力吧！

一、定义

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。

• 是一个
  归纳分类算法
  
• 属于
  监督学习
  
• 通过从训练集中学习，它挖掘出有用的规则来对新集进行预测。
  

二、原理

它基于贪心算法、树形结构和逐层筛选。
贪心法性质及特点详见文章链接：【算法设计与分析】3、贪心法

1、性质：

• 自上而下，分而治之
  
• 一开始，所有数据都在根节点
  
• 属性都是离散值字段（如果它们是连续的，则它们是离散化的）
  
• 所有记录都由选定的属性递归拆分
  
• 属性的选择基于启发式规则或统计测量
  

2、停止分割

• 一个节点上的数据都属于同一个类别
  
• 没有属性可以重复用于数据拆分
  

三、结构

1、结构示例

2、问题示例

4.舞台

1、训练阶段

从给定的训练数据集DB，构造出一颗决策树。
DT = fitctree(data,class)

2、分类阶段

从根开始，根据决策树的分类属性逐层划分，直到叶子节点，得到概念（决策，分类）的结果。
y = predict(DT,x)

5、优劣分工的判断

1、不纯性度量

通过杂质的测量来分析分类的优缺点。
对于所有分支，划分后选择同一个分支的所有实例都属于同一个类，则划分是纯的。

2、熵

• 系统越混乱，熵越大
  
• 如果某个节点上的数据类值均匀分布在可能的类值中，则该节点的熵最大
  
• 如果一个节点上数据的类值对所有数据都相同，则熵最小
  
• 决策树通过分裂进行选择，得到一个尽可能纯的节点，相当于降低了系统的熵。
  

6.信息增益

常用算法

1、ID3
2、C4.5
3、CART

意义

1、非参数学习。
2、其实决策树的性能并不是很好，但其逻辑易理解。
3、在集成学习中发挥重要作用。（不同数据训练出不同决策树，多个数量综合其结果。）