递归终止条件

决策树使用递归实现，而递归终止条件有以下三种：

1. 当前结点所有样本属于同类，无需划分

2. 当前属性集为空，无法划分，选取此节点中数量更多的标记作为类别标记

3. 当前样本集为空，不能划分，依据父节点中数量更多的标记作为类别标记

名词概念

1.纯度：同类聚集程度高、不同类越分散，则纯度越高
2.信息熵：纯度的量化指标，来源于信息论
3.剪枝：防止决策树过拟合，减去部分划分属性。分为预剪枝和后剪枝

信息熵

信息熵计算公式：
$$ E n t ( D ) = - \sum _ { k = 1 } ^ { | y | } p _ { k } \log _ { 2 } p _ { k }$$
信息熵用于衡量信息的不确定性或信息的混乱程度，我们可以将其用于量化纯度
信息熵越大，数据分布越均匀、随机、杂乱无章，明显这不是我们想要的。我们想要的是相同类靠近，不同类远离的效果，即需要越小的信息熵

$p_k$表示选到k类别的概率，而 $-\log _ { 2 } p _ { k }$则表示信息量

1

我们可以理解对于某一事件，其发生的概率越小，那么其信息量越大；发生的概率越大，那么其信息量越小。所有对两者求期望即得到信息熵。

注意：此处计算公式里的Y的输出值种类，如二分类问题中Y=2

所需数学知识

1. 求偏导
2. 矩阵求导
3. 求逆矩阵

名词解释

1.序关系

有序：属性之间可进行相对比较（如大、中、小）
无序：属性之间不可进行相对比较（如南瓜、西瓜、冬瓜）

2.符号arg与s.t.

arg：即argument（参数），用于表示求出指定函数时的**参数取值**
	例如：
	arg min 就是使后面这个式子达到最小值时的 变量的取值
	arg max 就是使后面这个式子达到最大值时的 变量的取值
	
s.t.：即subject to，意思是受限于...，后面紧跟约束条件

3.闭式解

也叫做 解析解，
闭式解就是一些严格的公式,给出任意的自变量就可以求出其因变量,也就是问题的解
南瓜书中说闭式解是指可以通过具体的表达式解出待解参数

模型介绍

术语名词

1.泛化误差与经验误差

泛化误差：在“未来”样本上的误差

经验误差：在训练集上的误差，亦称“训练误差”

训练集样本数越接近数据集数量，经验误差就越小。但是经验误差越小，模型效果就越好吗？

请注意，我们是为了得到泛化能力强的模型，而经验误差≠泛化误差

经验误差很小，会使模型学习到训练样本中的许多无用特征，导致泛化能力变弱
我们称其为过拟合(overfitting)

而与之相对的概念，我们称为欠拟合(underfitting)，其表示的就是模型没有很好的学习到训练样本上的特征，从而也导致泛化能力变弱

2.过拟合与欠拟合

过拟合：模型在训练数据上表现得过于复杂，以至于在未见过的数据上表现不佳。欠拟合：模型在训练数据上表现得过于简单，无法捕捉到数据的内在结构和模式。

出现原因：
1.出现欠拟合的情况，一般是由于样本特征少，模型复杂度低等

本书的使用：

第1章-绪论

计算学习理论

概率近似正确 模型：PAC (Probably Approximate Correct)

公式：$$ P ( | f ( x ) - y | \leq \epsilon ) \geq 1 - \delta$$

其中 f 表示模型，y表示真相，x为样本

公式分析：

其中$ | f ( x ) - y | \leq \epsilon$ 用于计算模型的误差，判断模型的优劣

由于模型基于不同的算法和数据是不唯一的

故用$$ P ( … ) \geq 1 - \delta$$ 表示取得该模型的概率