【人工智能】监督学习、分类问题、决策树、信息增益-Toy模板网

这篇具有很好参考价值的文章主要介绍了【人工智能】监督学习、分类问题、决策树、信息增益。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Decision Trees 决策树

什么是决策树 —— 基本概念

非叶节点：一个属性上的测试，每个分枝代表该测试的输出
叶节点：存放一个类标记
规则：从根节点到叶节点的一条属性取值路径

建立决策树分类模型的流程

模型训练：从已有数据中生成一棵决策树
分裂数据的特征，寻找决策类别的路径
相同的数据，根据不同的特征顺序，可以建立多种决策树

如何建立决策树?

基本的决策树学习过程，可以归纳为以下三个步骤：

特征选择：选取对于训练数据有着较强区分能力的特征
生成决策树：基于选定的特征，逐步生成完整的决策树
决策树剪枝：简化部分枝干，避免过拟合因素影响

决策树学习

问题：基于以下属性，决定是否在餐厅等待桌子：

Alternate：附近是否有其他选择的餐厅？
Bar：是否有一个舒适的酒吧区等待？
Fri/Sat：今天是星期五还是星期六？
Hungry：我们饿了吗？
Patrons：餐厅里的人数（无人、有些人、满座）
Price：价格范围（$、$$、$$$）
Raining：外面是否下雨？
Reservation：我们是否预约了？
Type：餐厅类型（法国、意大利、泰国、汉堡）
WaitEstimate：等待时间的预估值（0-10、10-30、30-60、>60）

假设的一种可能表示
例如，在上述餐厅等待桌子的问题中，我们可以使用决策树来表示假设，该决策树定义了在不同属性值下等待桌子的决策。以下是一个可能的假设树示例：

表达能力

决策树可以表示任何输入属性的函数，但使用单条路径来表示每个训练示例的决策树可能会过度拟合数据，无法很好地推广到新的未见过的数据示例。

决策树可以表达输入属性的任何函数。例如，对于布尔函数，函数真值表的每行对应于树中的一条路径: 【人工智能】监督学习、分类问题、决策树、信息增益,人工智能,深度学习,算法,人工智能,学习,分类
简单来说，针对每个训练示例，可以创建一条路径到叶子节点的一致性决策树（除非函数在输入属性上是非确定性的），但这种决策树可能会过度拟合数据，无法很好地泛化到新的未见过的数据示例。因此，更倾向于找到更紧凑的决策树来提高泛化性能。

决策树学习

目的：找到一个与训练示例一致的小树
想法：（递归）选择“最重要”属性作为（子）树的根
【人工智能】监督学习、分类问题、决策树、信息增益,人工智能,深度学习,算法,人工智能,学习,分类
想法：一个好的属性将示例拆分为（理想情况下）“全正”或“全负”的子集

根据Patron分类是一个更好的选择

信息论在决策树学习中的应用

信息熵：计算数据的不确定性

$\text{Entropy}(t) = - \sum_{j=1}^m p(j|t) \log_2 p(j|t)$
此时：表示某个节点𝑡 （即某个特征）的信息不确定性
$p (j ∣ t)$ 是节点特征𝑡的属于类别𝑗的样本的比例

特点：对于该节点特征t
- 当样本均匀地分布在各个类别时，熵达到最大值 $log(n_c)$ , 此时包含的信息最少
- 当样本只属于一个类别时，熵达到最小值 0, 此时包含的信息最多

对于包含 $p$ 个正例和 $n$ 个反例的训练集，其熵可以用以下公式计算：

$I(\frac{p}{p+n},\frac{n}{p+n}) = -\frac{p}{p+n}\log_2\frac{p}{p+n}-\frac{n}{p+n}\log_2\frac{n}{p+n}$

其中，第一项和第二项分别表示正例和反例的占比， $log_2$ 表示以 2 为底的对数。熵的值越高，表示数据集越不确定。

【人工智能】监督学习、分类问题、决策树、信息增益,人工智能,深度学习,算法,人工智能,学习,分类

特征选择准则一：信息增益

信息增益: 按某个特征划分之后，数据不确定性降低的程度

$\text{Gain}(m) = \text{Entropy}(p) - (\sum^k_{i=1} \frac{|n_i|}{n}\text{Entropy}(i))$

第一项 $\text{Entropy}(p)$ 表示数据未划分时的信息熵
第二项 $\sum^k_{i=1} \frac{|n_i|}{n}\text{Entropy}(i)$ 表示按特征m划分后，数据的信息熵
1. 按特征 $m$ 划分后，父节点分裂成 $k$ 个子节点
2. 𝑛表示父节点的样本个数
3. 𝑛𝑖 表示子节点𝑖的样本个数
  选择准则：选择最大的𝐺𝐴𝐼N 对应的特征m

举例

结论

信息增益能够较好地体现某个特征在降低信息不确定性方面的贡献
信息增益越大，说明信息纯度提升越快，最后结果的不确定性越低

不足

信息增益的局限性，尤其体现在更偏好可取值较多的特征
取值较多，不确定性相对更低，因此得到的熵偏低，但不一定有实际意义 【人工智能】监督学习、分类问题、决策树、信息增益,人工智能,深度学习,算法,人工智能,学习,分类
特征Customer ID有最大的信息增益，因为每个子节点的熵均为0

回到餐厅的例子

对于训练集， $p = n = 6$ ，信息熵为 $I(\frac{6}{12}, \frac{6}{12})=1$ bit。
考虑属性Patrons和Type（以及其他属性）
【人工智能】监督学习、分类问题、决策树、信息增益,人工智能,深度学习,算法,人工智能,学习,分类文章来源地址https://www.toymoban.com/news/detail-600524.html