机器学习

正在更新……

本笔记随课更新。

2023-2024学年度秋季学期。

Chapter 2. 线性回归

1. 线性回归模型

\[f_{\theta}(x)=\theta_1x_1+\theta_2x_2+…+\theta_nx_n\]

单变量线性回归：

对于 \(f_{\theta}(x)=\theta_1x+\theta_0\)，线性回归就退化为一条直线。

使用梯度下降法来确定一个抛物线（抛物面）的最低点，通过迭代更新，直到收敛（每次变化的大小趋近于一个很小的数，这个数字可以自己确定）找到要确定的 \(\theta\) 的值。

显然，对于 \(f_{\theta}(x)=\theta_1x_1+\theta_2x_2+\theta_0\)，就不再是一个线性函数；这时，模型具有两个特征。

在有多个 \(\theta\) 时，它们在迭代时应该同步更新。

线性回归的损失函数是凸函数，线性回归模型不存在局部最小值。

多变量线性回归：

考虑多变量线性回归中可能存在的变量方差不一的问题，它会导致抛物面的形状过于扁，此时，使用梯度下降方法可能导致在一个变量下降，而另一个变量震荡。

我们希望抛物面的形状趋近于标准圆的形状，因此，我们需要统一变量的尺度。这称为特征归一化。

特征归一化的方法有很多，但它们的目的都是把不同的特征统一到相似的尺度当中，它们的效果是相近的。

从另一个思路优化算法，既然特征的尺度不一致，我们可以考虑调整不同特征的学习率。例如：自适应的学习率，我们可以调节不同特征，赋予不同的学习率。当然，自适应的学习率也有多种不同的算法。

2. 多项式回归

多项式回归可以拟合各种各样的函数，但是存在容易过拟合的问题。

调节正则项系数有助于解决过拟合问题。

3. 最小二乘法线性回归

我们可以通过最小二乘法求解的方法，直接计算出 \(\theta\) 的值。但是，它涉及到矩阵的求逆运算，计算复杂度是比较高的。

对于梯度下降：

需要选择学习率
需要迭代很多次
一般可以得到比较好的效果，即使特征维度很大

对于最小二乘法：

不需要选择学习率
不需要迭代
需要进行矩阵的求逆运算
只适用于线性回归模型
不适合复杂模型（特征维度较大）的求解

4. 评价标准

MSE 均方误差、RMSE 均方根误差、MAE 平均绝对误差、R-Squared R 方/决定系数

具体选择哪个评价标准，和具体的学习任务有关，也可以综合取多个指标，评价模型的效果。

Chapter 4. 决策树

1. 目标

决策树（decision tree）是常见的机器学习方法，我们可以使用决策树来完成一个分类任务。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回：

当前结点包含的样本全属于同一类别，无需划分；
当前属性集为空，或是所有样本在所有属性上的取值相同，无法划分；
当前结点包含的样本集合为空，不能划分。

决策树学习的关键

决策树学习的关键是：如何选择最优划分属性。

一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。

2. 划分选择

根据选择最优划分属性方法的不同，我们可以了解一下三种基本的决策树算法：ID3、C4.5、CART，它们分别使用信息增益、增益率、基尼指数来计算属性划分所获得的“纯度提升”。

接下来，我们将结合一组实例，分别介绍三种算法的原理和具体计算流程。

数据实例：西瓜数据集

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

2.1 信息增益

2.1.1 算法原理

首先，使用“信息熵”（information entropy）来度量样本集合的纯度。

假定当前样本集合 \(D\) 中第 \(k\) 类样本所占比例为 \(p_k(k=1,2,…,|\mathcal{Y}|)\)，则 \(D\) 的信息熵定义为：

\[ Ent(D)=-\sum\limits*{k=1}^{|\mathcal{Y}|}p_klog*{2}p_k\]

计算信息熵时约定，若 \(p=0\)，则 \(plog_{2}p=0\)。

\(Ent(D)\) 的最小值为 0，最大值为 \(log_{2}|\mathcal{Y}|\)。

\(Ent(D)\) 的值越小，则 \(D\) 的纯度越高。

下面介绍“信息增益”（information gain）的概念，这一概念的描述可能比较复杂，我们可以结合具体的计算实例来理解。

假定离散属性 \(a\) 有 \(V\) 个可能的取值 \({a^1,a^2,…,a^V}\)，若使用属性 \(a\) 来对样本集 \(D\) 进行划分，则会产生 \(V\) 个分支结点，（显然，其中第 \(v\) 个分支结点将包含 \(D\) 中所有在属性 \(a\) 上取值为 \(a^v\) 的样本），记为 \(D^v\)。我们分别计算出 \(D^v\) 的信息熵，给各个分支结点赋予权重 \(\dfrac{|D^v|}{|D|}\)，（即样本数越多的分支节点的影响越大）。于是，我们就可以计算出用属性 \(a\) 对样本集 \(D\) 进行划分所获得的“信息增益”。

\[Gain(D,a)=Ent(D)-\sum\limits^{V}_{v=1}\dfrac{|D^v|}{|D|}Ent(D^v)\]

其中，公式前一项为未划分时的信息增益，后一项为每个子树的信息增益乘以权重的和，权重的意义是使样本数多的子节点更重要。

信息增益用来描述一次划分之后纯度的提升有多大。

一般而言，信息增益越大，“纯度提升”越大。我们可以用信息增益来选择决策树的划分属性。

\[a_*=\mathop {argmax}\limits_{a\in A}Gain(D,a)\]

ID3 决策树算法使用信息增益选择划分属性。

2.1.2 具体算例

以“西瓜数据集”为例：

\(\vert\mathcal{Y}\vert=2\)，\(p_1=\dfrac{8}{17}\)，\(p_2=\dfrac{9}{17}\)

根节点信息熵：

\[Ent(D)=-\sum\limits^2_{k=1}p_klog_{2}p_k=-(\dfrac{8}{17}log_{2}\dfrac{8}{17}+\dfrac{9}{17}log_{2}\dfrac{9}{17})=0.998\]

若以属性“色泽”划分，\(D^1(色泽=青绿)\)，\(D^2(色泽=乌黑)\)，\(D^3(色泽=浅白)\)

由此，三个分支结点的信息熵：

\[Ent(D^1)=-(\dfrac{3}{6}log_{2}\dfrac{3}{6}+\dfrac{3}{6}log_{2}\dfrac{3}{6})=1.000\]

\[Ent(D^2)=-(\dfrac{4}{6}log_{2}\dfrac{4}{6}+\dfrac{2}{6}log_{2}\dfrac{2}{6})=0.918\]

\[Ent(D^3)=-(\dfrac{1}{5}log_{2}\dfrac{1}{5}+\dfrac{4}{5}log_{2}\dfrac{4}{5})=0.722\]

属性“色泽”的信息增益：

\[Gain(D,色泽)=Ent(D)-\sum\limits^3_{v=1}\dfrac{|D^v|}{|D|}Ent(D^v)=0.998-(\dfrac{6}{17}\times1.000+\dfrac{6}{17}\times0.918+\dfrac{5}{17}\times0.722)=0.109\]

类似地，计算其他属性的信息增益：

\[Gain(D,根蒂)=0.143;\quad Gain(D,敲声)=0.141\]

\[Gain(D,纹理)=0.381;\quad Gain(D,脐部)=0.289\]

\[Gain(D,触感)=0.006\]

属性“纹理”的信息增益最大，因此它被选为划分属性。

基于“纹理”对根节点的划分结果：

\[ 纹理 = \begin{cases}{\{1,2,3,4,5,6,8,10,15\}}\quad \text {if {清晰}} \\ {\{7,9,13,14,17\}}\quad \text{if {稍糊}}\\ {\{11,12,16\}} \quad\text{if {模糊}} \end{cases} \]

然后，对每个分支结点做进一步划分，以第一个分支结点 \(D^1\) 为例，基于 \(D^1\) 计算各属性的信息增益：

\[Gain(D,色泽)=0.043;\quad Gain(D,根蒂)=0.458\]

\[Gain(D,敲声)=0.331;\quad Gain(D,脐部)=0.458\]

\[Gain(D,触感)=0.458\]

“根蒂”、“脐部”、“触感” 3 个属性均取得了最大的信息增益，可任选其中之一作为划分属性；类似的，对每个分支结点进行上述操作。直到算法递归结束，得到最终的决策树。

速记：计算根节点信息熵 → 计算各分支节点信息熵 → 计算各个属性信息增益 → 选取最大信息增益作为划分属性

2.2 增益率

2.2.1 算法原理

由于信息增益准则会对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，C4.5 决策树算法不直接使用信息增益，而使用“增益率”（gain ratio）来选择最优划分属性。

增益率定义为：

\[Gain\_raion(D,a)=\dfrac{Gain(D,a)}{IV(a)}\]

其中，属性 \(a\) 的“固有值”（intrinsic value）为：

\[IV(a)=-\sum\limits^V_{v=1}\dfrac{|D^v|}{|D|}log_{2}\dfrac{|D^v|}{|D|}\]

属性 \(a\) 的可能取值数目越多（即 \(V\) 越大），则 \(IV(a)\) 的值通常会越大。

注意：

信息率准则对可取值数目较少的属性有所偏好。因此，C4.5 算法不是直接选择增益率最大的候选划分属性，而是使用启发式：先从候选划分属性中选择信息增益高于平均水平的属性，再从中选择增益率最高的。

2.2.2 具体算例

以“西瓜数据集”为例：

\[IV(色泽)=-(\dfrac{6}{17}log_{2}\dfrac{6}{17}+\dfrac{6}{17}log_{2}\dfrac{6}{17}+\dfrac{5}{17}log_{2}\dfrac{5}{17})=-(-0.5304-0.5304-0.5193)=1.580\]

\[IV(根蒂)=-(\dfrac{8}{17}log_{2}\dfrac{8}{17}+\dfrac{7}{17}log_{2}\dfrac{7}{17}+\dfrac{2}{17}log_{2}\dfrac{2}{17})=-(-0.5117-0.5271-0.3633)=1.402\]

\[IV(敲声)=-(\dfrac{10}{17}log_{2}\dfrac{10}{17}+\dfrac{5}{17}log_{2}\dfrac{5}{17}+\dfrac{2}{17}log_{2}\dfrac{2}{17})=-(-0.4504-0.5193-0.3633)=1.333\]

\[IV(纹理)=-(\dfrac{9}{17}log_{2}\dfrac{9}{17}+\dfrac{5}{17}log_{2}\dfrac{5}{17}+\dfrac{3}{17}log_{2}\dfrac{3}{17})=-(-0.4858-0.5193-0.4416)=1.447\]

\[IV(脐部)=-(\dfrac{7}{17}log_{2}\dfrac{7}{17}+\dfrac{6}{17}log_{2}\dfrac{6}{17}+\dfrac{4}{17}log_{2}\dfrac{4}{17})=-(-0.5271-0.5304-0.4912)=1.549\]

\[IV(触感)=-(\dfrac{12}{17}log_{2}\dfrac{12}{17}+\dfrac{5}{17}log_{2}\dfrac{5}{17})=-(-0.3547-0.5193)=0.874\]

\[Gain(D,色泽)=0.109;\quad Gain(D,根蒂)=0.143\]

\[Gain(D,敲声)=0.141;\quad Gain(D,纹理)=0.381\]

\[Gain(D,脐部)=0.289;\quad Gain(D,触感)=0.006\]

\[\overline{Gain(D,a)}=\dfrac{0.109+0.143+0.141+0.381+0.289+0.006}{6}=0.178\]

信息增益高于平均水平的属性：纹理、脐部

\[Gain\_ratio(D,纹理)=\dfrac{Gain(D,纹理)}{IV(纹理)}=\dfrac{0.381}{1.447}=0.263\]

\[Gain\_ratio(D,脐部)=\dfrac{Gain(D,脐部)}{IV(脐部)}=\dfrac{0.289}{1.549}=0.187\]

选择增益率最高的“纹理”属性作为划分属性。

速记：计算根节点信息熵 → 计算各分支节点信息熵 → 计算各个属性信息增益 → 计算各个属性的固有值 → 计算各个属性的增益率 → 选取信息增益高于平均水平，并且增益率最高的属性作为划分属性

2.3 基尼指数

2.3.1 算法原理

数据集 \(D\) 的纯度可以用基尼值来度量：

\[Gini(D)=\sum\limits^{|\mathcal{Y}|}_{k=1}\sum\limits_{k'\neq k}p_kp_{k'}=1-\sum\limits^{|\mathcal{Y}|}_{k=1}p_k^2\]

\(Gini(D)\) 反映了从数据集 \(D\) 中随机抽取两个样本，其类别标记不一致的概率；\(Gini(D)\) 越小，数据集 \(D\) 的纯度越高。

属性 \(a\) 的“基尼指数”（Gini index）定义为：

\[Gini\_index(D,a)=\sum\limits^V_{v=1}\dfrac{|D^v|}{|D|}Gini(D^v)\]

在候选属性集合 \(A\) 中，选择使得划分后基尼指数最小的属性作为最优划分属性：

\[a_*=\mathop {argmin}\limits_{a\in A}Gini\_index(D,a)\]

CART 决策树使用“基尼指数”来选择划分属性。

2.3.2 具体算例

若以属性“色泽”划分，\(D^1(色泽=青绿)\)，\(D^2(色泽=乌黑)\)，\(D^3(色泽=浅白)\)

由此，三个分支结点的基尼值：

\[Gini(D^1)=1-\Big(\Big(\dfrac{3}{6}\Big)^2+\Big(\dfrac{3}{6}\Big)^2\Big)=0.500\]

\[Gini(D^2)=1-\Big(\Big(\dfrac{4}{6}\Big)^2+\Big(\dfrac{2}{6}\Big)^2\Big)=0.444\]

\[Gini(D^3)=1-\Big(\Big(\dfrac{1}{5}\Big)^2+\Big(\dfrac{4}{5}\Big)^2\Big)=0.320\]

属性“色泽”的基尼指数：

\[Gini\_index(D,色泽)=\dfrac{6}{17}\times0.500+\dfrac{6}{17}\times0.444+\dfrac{5}{17}\times0.320=0.427\]

类似地，计算其他属性的基尼指数：

\[Gini\_index(D,根蒂)=0.422;\quad Gini\_index(D,敲声)=0.424\]

\[Gini\_index(D,纹理)=0.277;\quad Gini\_index(D,脐部)=0.344\]

\[Gini\_index(D,触感)=0.494\]

选择基尼指数最小的“纹理”属性作为划分属性。

速记：计算各分支节点基尼值 → 计算各个属性基尼指数 → 选取基尼指数最小的属性作为划分属性

3. 剪枝

剪枝（pruning）是决策树算法防止“过拟合”的主要手段。主要分为“预剪枝”（prepruning）和“后剪枝”（post-pruning）两种。

判断决策树的泛化性能，可以使用留出法，即预留一部分数据用作“验证集”以进行性能评估。此时，未剪枝决策树将基于训练集构建，而泛化性能将基于验证集中的准确率来衡量。

3.1 预剪枝

预剪枝是指在决策树生成过程中，在每个结点划分前先进行估计，若当前节点划分不能带来决策树泛化性能提升，则停止划分当前结点，并将当前节点标记为叶节点，其类别标记为结点中训练样例数最多的类别。

预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

3.2 后剪枝

后剪枝是指先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

4. 连续与缺失值

4.1 连续值处理

我们有必要讨论一下如何在决策树学习中使用连续属性。

首先，我们更新一下数据集，以便讨论连续属性。

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	0.697	0.460	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	0.774	0.376	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	0.634	0.264	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	0.608	0.318	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	0.556	0.215	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	0.403	0.237	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	0.481	0.149	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	0.437	0.211	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	0.666	0.091	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	0.243	0.267	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	0.245	0.057	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	0.343	0.099	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	0.639	0.161	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	0.657	0.198	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	0.360	0.370	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	0.593	0.042	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	0.719	0.103	否

4.1.1 算法原理

由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。

此时，连续属性离散化技术可派上用场。

最简单的策略是采用二分法（bi-partition）对连续属性进行处理，这也是 C4.5 决策树算法中采用的机制。

下面介绍二分法的具体流程，同样地，这一概念的描述可能比较复杂，但我们仍可以结合具体的计算实例来理解。

给定样本集 \(D\) 和连续属性 \(a\)，假定 \(a\) 在 \(D\) 上出现了 \(n\) 个不同的取值，将这些值从小到大进行排序，记为\(\{a^1,a^2,…,a^n\}\)。基于划分点 t 可将 \(D\) 分为子集 \(D_t^-\) 和 \(D_t^+\)，其中 \(D_t^-\) 包含那些在属性 \(a\) 上取值不大于 \(t\) 的样本，而 \(D_t^+\) 则包含那些在属性 \(a\) 上取值大于 \(t\) 的样本。显然，对相邻的属性取值 \(a^i\) 与 \(a^{i+1}\) 来说，\(t\) 在区间 \([a^i,a^{i+1})\) 中取任意值所产生的划分结果相同。因此，对连续属性 \(a\)，我们可考察各个包含 \(n-1\) 个元素的候选划分点集合，即把区间 \([a^i,a^{i+1})\) 的中位点 \(\dfrac{a^i+a^{i+1}}{2}\) 作为候选划分点。

候选划分点集合：

\[T_a=\Big\{\dfrac{a^i+a^{i+1}}{2}\mid1\leq i\leq n-1\Big\}\]

然后，像考察离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。

\[Gain(D,a)=\mathop{max}\limits_{t\in T_a}\ Gain(D,a,t)=\mathop{max}\limits_{t\in T_a}\ Ent(D)-\sum\limits_{\lambda\in\{-,+\}}\dfrac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda})\]

其中，\(Gain(D,a,t)\) 是样本集 \(D\) 基于划分点 \(t\) 二分后的信息增益。于是，我们就可选择使 \(Gain(D,a,t)\) 最大化的划分点。

4.1.2 具体算例

对于属性“密度”，在决策树学习开始时，根节点包含 17 个训练样本在该属性上取值均不同。

属性“密度”的候选划分点集合包含 16 个候选值：

\[T_{密度}=\{0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746\}\]

逐个计算各个候选划分点的信息增益，得到最优划分点：0.381

若以 0.381 划分，两个分支结点的信息熵：

\[Ent(D_{0.381}^-)=-(0+\dfrac{4}{4}log_{2}\dfrac{4}{4})=0\]

\[Ent(D_{0.381}^+)=-(\dfrac{8}{13}log_{2}\dfrac{8}{13}+\dfrac{5}{13}log_{2}\dfrac{5}{13})=-(-0.431-0.530)=0.961\]

属性“密度”的信息增益：

\[Gain(D,密度)=-(\dfrac{8}{17}log_{2}\dfrac{8}{17}+\dfrac{9}{17}log_{2}\dfrac{9}{17})-(\dfrac{4}{17}\times 0+\dfrac{13}{17}\times 0.961)=0.998-0.735=0.263\]

同样地，对于属性“含糖率”，候选划分点集合也包含 16 个候选值，最优划分点 0.126，信息增益 0.349。

综上：

\[Gain(D,色泽)=0.109;\quad Gain(D,根蒂)=0.143\]

\[Gain(D,敲声)=0.141;\quad Gain(D,纹理)=0.381\]

\[Gain(D,脐部)=0.289;\quad Gain(D,触感)=0.006\]

\[Gain(D,密度)=0.262;\quad Gain(D,含糖率)=0.349\]

于是，“纹理”被选作根节点划分属性，此后结点划分过程递归进行。

需要注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

4.2 缺失值处理

我们需要解决两个问题：

（1）如何在属性值缺失的情况下进行划分属性选择？

（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

同样地，我们更新一下数据集，使其产生一些缺失值，其余的值同第 2 节中的表格。

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	-	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	-	是
3	乌黑	蜷缩	-	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	-	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	-	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
8	乌黑	稍蜷	浊响	-	稍凹	硬滑	是
9	乌黑	-	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	清脆	-	平坦	软粘	否
11	浅白	硬挺	清脆	模糊	平坦	-	否
12	浅白	蜷缩	-	模糊	平坦	软粘	否
13	-	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	-	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	-	沉闷	稍糊	稍凹	硬滑	否

4.2.1 算法原理

给定训练集 \(D\) 和属性 \(a\)，令 \(\tilde{D}\) 表示 \(D\) 中在属性 \(a\) 上没有缺失值的样本子集。对于问题（1），显然我们仅可根据 \(\tilde{D}\) 来判断属性 \(a\) 的优劣。

假定属性 \(a\) 有 \(V\) 个可取值 \(\{a^1,a^2,…,a^V\}\)，令 \(\tilde{D}^v\) 表示 \(\tilde{D}\) 在属性 \(a\) 上取值为 \(a^v\) 的样本子集，\(\tilde{D}^k\) 表示 \(\tilde{D}\) 中属于第 \(k\) 类（\(k=1,2,…,|\mathcal{Y}|\)）的样本子集，则显然有 \(\tilde{D}=\cup_{k=1}^{|\mathcal{Y}|}\tilde{D}_k\)，\(\tilde{D}=\cup_{v=1}^{V}\tilde{D}^v\)。

假定我们为每个样本 \(x\) 赋予一个初始权重 \(w_x\)，在决策树学习开始阶段，根节点中各样本的权重初始化为 1，并定义：

\[\rho=\dfrac{\sum_{x\in\tilde{D}}w_x}{\sum_{x\in D}w_x}\]

\[\tilde{p}_k=\dfrac{\sum_{x\in\tilde{D}_k}w_x}{\sum_{x\in D}w_x}\quad(1\leq k\leq |\mathcal{Y}|)\]

\[\tilde{r}_v=\dfrac{\sum_{x\in\tilde{D}^v}w_x}{\sum_{x\in D}w_x}\quad(1\leq v\leq V)\]

直观地看，对属性 \(a\)，\(\rho\) 表示无缺失值样本所占的比例，\(\tilde{p}_k\) 表示无缺失值样本中第 \(k\) 类所占的比例，\(\tilde{r}_v\) 表示无缺失值样本中在属性 \(a\) 上取值 \(a^v\) 的样本所占的比例。显然，\(\sum\limits_{k=1}^{|\mathcal{Y}|}\tilde{p}_k=1\)，\(\sum\limits_{v=1}^{V}\tilde{r}_v=1\)。

基于上述定义，信息熵的计算式：

\[Ent(\tilde{D})=-\sum\limits_{k=1}^{|\mathcal{Y}|}\tilde{p}_klog_{2}\tilde{p}_k\]

信息增益的计算式推广为：

\[Gain(D,a)=\rho\times Gain(\tilde{D},a)=\rho\times\Big(Ent(\tilde{D})-\sum\limits_{v=1}^{|\mathcal{Y}|}\tilde{r}_vEnt(\tilde{D}^v)\Big)\]

对于问题（2），若样本 \(x\) 在划分属性 \(a\) 上的取值已知，则将 \(x\) 划入与其取值对应的子结点，且样本权值在子结点中保持为 \(w_x\)；若样本 \(x\) 在划分属性 \(a\) 上的取值未知，则将 \(x\) 同时划入所有子结点，且样本权值在与属性值 \(a^v\) 对应的子节点中调整为 \(\tilde{r}_v\cdot w_x\)。直观地看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

4.2.2 具体算例

在学习开始时，根节点包含样本集 \(D\) 中全部 17 个样例，且个样例的权值均为 1。

以属性“色泽”为例：

在该属性上，无缺失值的样例子集 \(\tilde{D}\) 包含编号：\(\{2,3,4,6,7,8,9,10,11,12,14,15,16,17\}\) 共 14 个样例。

\(\tilde{D}\) 的信息熵：

\[Ent(\tilde{D})=-\sum\limits_{k=1}^{2}\tilde{p}_{k}log_{2}\tilde{p}_{k}=-\Big(\dfrac{6}{14}log_{2}\dfrac{6}{14}+\dfrac{8}{14}log_{2}\dfrac{8}{14}\Big)=0.985\]

令 \(\tilde{D}^1\)，\(\tilde{D}^2\) 与 \(\tilde{D}^3\) 分别表示在属性“色泽”上取值为“青绿”“乌黑”以及“浅白”的样本子集，计算各样本子集的信息熵：

\[Ent({\tilde{D}^1})=-\Big(\dfrac{2}{4}log_{2}\dfrac{2}{4}+\dfrac{2}{4}log_{2}\dfrac{2}{4}\Big)=1.000\]

\[Ent({\tilde{D}^2})=-\Big(\dfrac{4}{6}log_{2}\dfrac{4}{6}+\dfrac{2}{6}log_{2}\dfrac{2}{6}\Big)=0.918\]

\[Ent({\tilde{D}^3})=-\Big(\dfrac{0}{4}log_{2}\dfrac{0}{4}+\dfrac{4}{4}log_{2}\dfrac{4}{4}\Big)=0.000\]

样本子集 \(\tilde{D}\) 在属性“色泽”的信息增益：

\[Gain(\tilde{D},色泽)=Ent(\tilde{D})-\sum\limits_{v=1}^{3}\tilde{r}_{v}Ent(\tilde{D}^v)=0.985-\Big(\dfrac{4}{14}\times1.000+\dfrac{6}{14}\times0.918+\dfrac{4}{14}\times0.000\Big)=0.306\]

样本集 \(D\) 在属性“色泽”的信息增益：

\[Gain(D,色泽)=\rho\times Gain(\tilde{D},色泽)=\dfrac{14}{17}\times 0.306=0.252\]

所有属性在 \(D\) 上的信息增益：

\[Gain(D,色泽)=0.252;\quad Gain(D,根蒂)=0.171\]

\[Gain(D,敲声)=0.145;\quad Gain(D,纹理)=0.424\]

\[Gain(D,脐部)=0.289;\quad Gain(D,触感)=0.006\]

属性“纹理”取得了最大的信息增益，被用于对根节点进行划分，划分结果是：

编号为 \(\{1,2,3,4,5,6,15\}\) 的样本进入“纹理=清晰”分支，样本在子结点中的权重保持为 1；

编号为 \(\{7,9,13,14,17\}\) 的样本进入“纹理=稍糊”分支，样本在子结点中的权重保持为 1；

编号为 \(\{11,12,16\}\) 的样本进入“纹理=模糊”分支，样本在子结点中的权重保持为 1；

编号为 \(\{8,10\}\) 的样本在属性“纹理”出现缺失值，同时进入三个分支，样本在三个子结点中的权重分别调整为 \(\dfrac{7}{15}\)、\(\dfrac{5}{15}\) 和 \(\dfrac{3}{15}\)。

速记：计算根节点无缺失值样本子集信息熵 → 计算各分支节点无缺失值样本子集信息熵 → 计算各个属性样本子集信息增益 →→ 计算各个属性样本集信息增益 → 选取最大信息增益作为划分属性 → 更新样本在子结点中的权重

5. 多变量决策树

5.1 算法目标

若把每个属性视为坐标空间中的一个坐标轴，则 \(d\) 个属性描述的样本就构成了 \(d\) 维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。

单变量决策树（univariate decision tree）所形成的分类边界是轴平行（axis-parallel）的，它的分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果由较好的可解释性；但在真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，决策树会相当复杂，预测时间开销会很大。

多变量决策树（multivariate decision tree）能够实现斜的划分边界，甚至能够实现更复杂的划分，从而简化决策树模型。此时，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点是一个形如 \(\sum\limits_{i=1}^{d}w_{i}a_{i}=t\) 的分类器，其中 \(w_{i}\) 是属性 \(a_{i}\) 的权重，\(w_{i}\) 和 \(t\) 可在该节点所含的样本集和属性集上学得。

多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。举例来看，分类条件不再是形似 “\(含糖率\leq 0.126?\)”，而是形似 “\(-0.800\times 密度-0.044\times 含糖率\leq 0.313?\)” 的形式。

5.2 主要算法

多变量决策树的算法主要有 OC1 和一系列引入了线性分类器学习的最小二乘法算法。

OC1 先贪心地寻找每个属性的最优权值，在局部优化的基础上再对分类边界进行随机扰动以试图找到更好地边界。

还有一些算法试图在决策树的叶节点上嵌入神经网络，例如“感知机树”在决策树的每个叶节点上训练一个感知机；还有算法直接在叶节点上嵌入多层神经网络。

6. 增量学习

有一些决策树算法可以进行“增量学习”（incremental learning），即在接收到新样本后可对已学得的模型进行调整，而不用完全重新学习；主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构，代表性算法有 ID4、ID5R、ITI 等。

增量学习可有效降低每次接收到新样本后的训练时间开销，但多步增量学习后的模型会与基于全部数据训练而得的模型有较大差别。

Chapter 5. 神经网络

1. 动机

例子：图像识别中的目标检测，在处理非线性问题中，前面介绍的模型存在困难。此外，例如“异或”XOR 问题就是一个非线性问题。

大脑解决问题，并不会给每一个特定领域的问题写一个专门的算法，而是有一个通用的方法应用在遇到的各种问题中。

2. 神经元模型

“M-P 神经元模型”。

3. 感知机与多层网络

一般地，给定训练数据集，权重 \(w_i\) 以及阈值 \(\theta\) 可以通过学习得到。

但是，感知机只有输出层神经元进行激活函数处理，即只拥有一层功能神经元，其学习能力非常有限。事实上，如果两类模式是线性可分的，即存在一个线性超平面能将它们分开，则感知机的学习过程一定会收敛，从而求得适当的权向量；否则，感知机的学习过程将会发生震荡。

但是，感知机不能解决非线性可分问题。

要解决非线性可分问题，需要考虑使用多层功能神经元。例如，简单的两层感知机就能解决异或问题。

对于激活函数的选择，sigmoid 函数虽然连续，非线性，易于计算；但是，在层数更多的情形下，会导致梯度消失问题。

4. 神经网络的标准结构

包括输入层、隐藏层（代表了网络用来学习中间的结果）、输出层。

在神经网络中，我们关心在各个神经元中的权重。

在给定一个神经网络结构时，其实就相当于确定了一个函数集。

在全连接前馈神经网络中，使用 sigmoid 函数作为激活函数。