本文数学表示：$\mathbf{x}$表示向量，$x$表示标量，$\mathbf{A}$表示矩阵。
图源：西电软工云计算方向2025年《机器学习与数据挖掘》PPT
上一篇：万字长文（上）|带你一键入门西电软工课程《机器学习与数据挖掘》|绪论|数学基础|特征工程|线性模型|决策树

🦌：本文根据笔者自己容易理解的顺序所写，包含了PPT上所有内容，内容较多，按需自取，另外本文有很多笔者个人想法和总结，如有错误请指出。

六、神经网络

重点：全连接多层神经网络，卷积神经网络，特征图大小的计算，复杂度计算。

神经网络：由具有适应性的简单单元组成的广泛并行互联的网络，它的组织能够模拟生物神经系统对真实世界物体所做出的反应。

神经元激活函数：

• 阶跃函数：理想化。$\text{sgn}(x)=\{\begin{array}{ll}1& \text{if }x\ge 0\\ 0& \text{if }x<0\end{array}$
• 对数几率函数：用于二分类，作为输出层激活函数。$\text{sigmoid}(x)=\frac{1}{1+e^{-x}}$
• Softmax函数：用于多分类，作为输出层激活函数。$\text{softmax}(x)=\frac{e^{z_i^l}}{{\sum }_{i=1}^n{e}^{z_i^l}}$
• 双曲正切函数Tanh：$\text{tanh}(x)=\frac{\text{sinh}(x)}{\text{cosh}(x)}=\frac{e^x-e^{-x}}{e^x+e^{-x}}$
• ReLU函数：单侧抑制，常用于隐含层激活函数和CNN卷积核的激活函数。$\text{ReLU}(x)=\max (x,0)=\{\begin{array}{ll}x& \text{if }x>0\\ 0& \text{if }x\le 0\end{array}$

为什么使用非线性激活函数：如果激活函数是线性的，最终会导致${\mathbf{a}}^L=\mathbf{W}{\mathbf{a}}^0$，意味着深度神经网络（DNN）退化成一个线性模型，失去绝大部分学习能力。

1.全连接多层神经网络

全连接多层神经网络（Fully Connected Network, FCN）：

• 多层：包含隐含层的神经网络（层数 $\ge 2$）

• 定义：每层神经元与下一层完全互联（两层间任意两个神经元之间都有连接），不存在同层连接和跨层连接。

• 前馈：输入层接受输入，隐含层与输出层进行加工，输出层输出。

• 学习：根据训练数据调整层间神经元之间的权重（连接权）和每个功能神经元的阈值（threshold）。

参数：

记号定义：

记号	含义
$a_i^l$	第$l$层第$i$个神经元的激活值
${\mathbf{a}}^l$	第$l$层的神经元激活向量
$z_i^l$	第$l$层第$i$个神经元的激活函数的带权输入
${\mathbf{z}}^l$	第$l$层的激活函数的带权输入
$w_{ij}^l$	第$l-1$层第$j$个神经元到第$l$层第$i$个神经元的权重
${\mathbf{W}}^l$	连接从第$l-1$层到第$l$层的权重矩阵
$b_i^l$	第$l$层第$i$个神经元的偏置（bias）
${\mathbf{b}}^l$	第$l$层的偏置向量

• 层间关系：

$${\mathbf{z}}^l={\mathbf{W}}^l{\mathbf{a}}^{l-1}+{\mathbf{b}}^l$$

• 同层关系：

$${\mathbf{a}}^l=\sigma ({\mathbf{z}}^l)$$

• 层输出关系：

$${\mathbf{a}}^l=\sigma ({\mathbf{z}}^l)=\sigma ({\mathbf{W}}^l{\mathbf{a}}^{l-1}+{\mathbf{b}}^l)$$

损失函数（Loss function）：计算单个样本的预测值与真实值之间的差异

欧几里得距离：即L2范数，$\text{loss}=\sqrt{(\mathbf{y}-\hat{\mathbf{y}}{)}^2}$

交叉熵（cross-entropy）：用于分类任务。$\text{loss}=-y_i\log p_i-(1-y_i)\log (1-p_i)$

总代价函数（total cost function）：整个数据集上所有样本损失。$C(\theta )={\sum }_{r=1}^R{L}^r(\theta )$

均方误差MSE：$C(\theta )=\frac{1}{2m}\Vert \mathbf{y}-\hat{\mathbf{y}}{\Vert }^2=\frac{1}{2m}(\mathbf{y}-\hat{\mathbf{y}}{)}^2$

交叉熵（cross-entropy）：$C(\theta )=\frac{1}{m}\sum -y_i\log p_i-(1-y_i)\log (1-p_i)$

目标：求使总代价函数最小的参数$\theta$。

1.1梯度降方法

梯度降方法（Gradient Descent）：每次朝着与当前梯度相反的方向搜索解，不停地更新参数。
$$\begin{gathered} \theta \leftarrow \theta -\eta \frac{\partial C(\theta )}{\partial \theta } \\ (w_{ij}^l{)}^{k+1}=(w_{ij}^l{)}^k-\eta \frac{\partial C\left((w_{ij}^l{)}^k\right)}{\partial (w_{ij}^l{)}^k},(b_i^l{)}^{k+1}=(b_i^l{)}^k-\eta \frac{\partial C\left((b_i^l{)}^k\right)}{\partial (b_i^l{)}^k} \end{gathered}$$
不能保证获得全局最小解。

1.2反向传播算法

反向传播算法（Backpropagation，BP）：允许来自代价函数的信息通过网络反向流动，以便计算梯度。

目标：计算梯度。
$$(w_{ij}^l{)}^{k+1}=(w_{ij}^l{)}^k-\eta \frac{\partial C\left((w_{ij}^l{)}^k\right)}{\partial (w_{ij}^l{)}^k},(b_i^l{)}^{k+1}=(b_i^l{)}^k-\eta \frac{\partial C\left((b_i^l{)}^k\right)}{\partial (b_i^l{)}^k}$$
链式法则（chain rule）：$\Delta z=\frac{\partial z}{\partial y}\Delta y=\frac{\partial z}{\partial y}\frac{\partial y}{\partial x}\Delta x$

误差：第$l$层第$i$个神经元上的误差${\delta }_i^l$
$$\begin{gathered} {\delta }_i^l=\frac{\partial C}{\partial z_i^l} \\ {z}_i^l=\sum _k{w}_{ik}^l{a}_k^{l-1}+b_i^l \end{gathered}$$
求误差步骤：

1.计算输出层（最后一层）误差${\delta }^L$。
$$\begin{gathered} {\delta }_i^L=\frac{\partial C}{\partial z_i^L}=\frac{\partial C}{\partial a_i^L}\frac{\partial a_i^L}{\partial z_i^L}=\frac{\partial C}{\partial a_i^L}{\sigma }^{\prime }(z_i^L) \\ {a}_i^L=\sigma (z_i^L) \end{gathered}$$

• 其中$a_i^L$是实际输出值，$\frac{\partial C}{\partial a_i^L}$与损失函数相关。

记为：
$${\delta }^L=\nabla C({\mathbf{a}}^L)\odot {\sigma }^{\prime }({\mathbf{z}}^L)$$

$\odot$表示逐元素相乘。

2.由${\delta }^{l+1}$计算${\delta }^l$
$${\delta }_i^l=\frac{\partial C}{\partial z_i^l}=\sum _k\left(\frac{\partial C}{\partial z_k^{l+1}}\frac{\partial z_k^{l+1}}{\partial a_i^l}\frac{\partial a_i^l}{\partial z_i^l}\right)=\frac{\partial a_i^l}{\partial z_i^l}\sum _k\left(\frac{\partial z_k^{l+1}}{\partial a_i^l}{\delta }_k^{l+1}\right)={\sigma }^{\prime }(z_i^l)\sum _k{w}_{ki}^{l+1}{\delta }_k^{l+1}$$
记为：
$${\delta }^l={\sigma }^{\prime }({\mathbf{z}}^l)\odot ({\mathbf{W}}^{\mathbf{l}+1}{)}^T{\delta }^{l+1}$$
计算梯度：
$$\begin{gathered} \frac{\partial C}{\partial w_{ij}^l}=\frac{\partial C}{\partial z_i^l}\frac{\partial z_i^l}{\partial w_{ij}^l}={\delta }_i^l\frac{\partial z_i^l}{\partial w_{ij}^l}=\{\begin{array}{ll}{\delta }_i^l{a}_j^{l-1}& l>1\\ {\delta }_i^l{x}_j& l=1\end{array} \\ \frac{\partial z_i^l}{\partial w_{ij}^l}=\{\begin{array}{ll}{a}_j^{l-1}& l>1\\ x_j& l=1\end{array} \end{gathered}$$

$$\frac{\partial C}{\partial b_i^l}=\frac{\partial C}{\partial z_i^l}\frac{\partial z_i^l}{\partial b_i^l}={\delta }_i^l$$

• 梯度的计算基于正向传播和反向传播两个预先计算的项。
  • 正向传播：$\frac{\partial z_i^l}{\partial w_{ij}^l}=\{\begin{array}{ll}{a}_j^{l-1}& l>1\\ x_j& l=1\end{array}$
  • 反向传播：${\delta }_i^l$

总结一下BP算法：

1. 输入样本$\mathbf{x}$：为输入层设置对应的激活值${\mathbf{a}}^1$。
2. 正向传播：对每一层$l=1,2,...,L$计算相应的${\mathbf{z}}^l={\mathbf{W}}^l{\mathbf{a}}^{l-1}+{\mathbf{b}}^l$和${\mathbf{a}}^l=\sigma ({\mathbf{z}}^l)$。
3. 输出层误差${\delta }^L$：${\delta }^L={\nabla }_{a}C({\mathbf{a}}^L)\odot {\sigma }^{\prime }({\mathbf{z}}^L)$。
4. 反向误差传播：对每一层$l=L-1,L-2,...,2$，计算${\delta }^l={\sigma }^{\prime }({\mathbf{z}}^l)\odot ({\mathbf{W}}^{\mathbf{l}+1}{)}^T{\delta }^{l+1}$
5. 输出：计算梯度$\frac{\partial C}{\partial w_{ij}^l}={\delta }_i^l{a}_j^{l-1}$和 $\frac{\partial C}{\partial b_i^l}={\delta }_i^l$

1.3优化求解权重和偏置

🦌：不是重点，了解一下。

1.3.1批量（batch）梯度降

1.3.2随机梯度降（SGD）

1.3.3小批量（Mini-batch）梯度降优化

1.4其他小知识

1.4.1实际训练中概念

• Batch size（批量大小）：1次迭代使用的样本量。
• Iteration（迭代）：使用1个batch size样本训练网络参数1次。
• Epoch（期、轮）：遍历了1遍训练集中所有样本。

$$总迭代（iteration）次数=\frac{训练集大小}{batchsize}$$

1.4.2偏置在神经网络中的作用

偏置（bias）：$\mathbf{b}$，将激活函数向左或向右移动：负右正左。

2.卷积神经网络

卷积神经网络（Convolutional Neural Network，CNN）：可用于图像分类（图像识别）。

演化历史：

完整CNN：

全连接层（fully connected，FC）：“分类器”作用，将学到的“分布式特征表示”映射到样本标记空间，即将卷积层和池化层提取的空间特征转换为类别概率分布（这里都是分类任务）。

需先将输入特征图展平为1D向量（如7×7×512 → 25088维），参数量占比高。

2.1卷积操作

卷积操作用于提取特征，得到特征图（feature map）。

滤波（filiter）：滤波也称卷积核、特征检测器。

注意这里是逐元素相乘后相加得到一个值，不是矩阵乘法。

• 逐元素相乘：$\mathbf{A}\odot \mathbf{B}$。
• 矩阵乘法：$\mathbf{AB}$或$\mathbf{A}\times \mathbf{B}$。

卷积滑动步幅（stride，步长，幅度）：控制特征图（feature map）尺寸的方式之一。

加边（Padding，填充）：在图像周围补充0的预定值（零填充，Zero padding）。与步幅一起控制特征图大小。

通道一致性：每一个卷积核（滤波）的通道数必须和输入图像的通道数相同。

• 输出特征图的通道数等于卷积核个数。

卷积操作后特征图（Feature map）大小：
$$\underset{H_{\text{out}}}{\left(\lfloor \frac{H_{in}-k+2P}{S}\rfloor +1\right)}\times \underset{W_{\text{out}}}{\left(\lfloor \frac{W_{in}-k+2P}{S}\rfloor +1\right)}\times K$$

• 输入图像大小：$H_{in}\times W_{in}\times n_c$
• $K$个卷积核大小：$k\times k\times n_c$
• 加边：$P$ 步幅：$S$

$1\times 1$卷积的作用：

• 减小（增加）通道数：一般用$1\times 1$卷积都不会改变图像大小，只是用卷积核个数控制通道数。
• 增加非线性：每个卷积核有自己的非线性激活函数，多个卷积核增加非线性增强学习且没有显著增加参数。

🦌：个人感觉$1\times 1$与其他大小的卷积核最大差别就是一般用$1\times 1$卷积核不改变图像大小改变通道数进行降维，其他大小卷积核（一般用$3\times 3$多）用于特征提取。

特性	1×1 卷积核	其他尺寸卷积核（如 3×3）
空间感知能力	无（仅作用于通道维度）	有（捕捉局部空间特征）
参数量	极低（仅需 $c_{in}\times c_{out}$ 参数）	较高（如 3×3 核需 $9\times c_{in}\times c_{out}$）
主要用途	通道混合、降维/升维、非线性增强	提取空间特征（边缘、纹理等）
计算复杂度	低	高（与核尺寸平方成正比）

2.2最大池化

最大池化（Max Pooling）：选取输入特征图的某个区域内所有神经元的最大值或平均值作为该区域的概括。（区域可重叠）

🦌：和卷积操作很像，都需要卷积核（滤波）与输入图像进行操作，知识卷积操作是逐元素相乘后相加，最大池化是取最大值或平均值，上图是取最大值。

后文的各类CNN模型里，最大池化一般用于减半特征图大小。

池化操作后特征图大小：
$$\underset{H_{\text{out}}}{\left(\lceil \frac{H_{in}-k+2P}{S}\rceil +1\right)}\times \underset{W_{\text{out}}}{\left(\lceil \frac{W_{in}-k+2P}{S}\rceil +1\right)}\times K$$

卷积操作：为什么向下取整（Floor）？

• 边界处理原则：卷积核必须完全覆盖输入区域*才会计算输出。如果剩余窗口不足一个步长，则舍弃边缘部分。*
• 信息完整性：向下取整确保所有输出位置的计算都基于完整的输入窗口，避免引入无效填充数据。

池化操作：为什么向上取整（Ceil）？

• 保留边缘信息：池化的目的是降维但尽可能保留显著特征（如纹理、边缘）。即使剩余窗口不足池化核大小，仍对其进行池化。
• 池化常用于压缩特征图，向上取整能减少信息损失。

池化层（Pooling）的作用：本质是采样，对输入的特征图选择某种方式进行压缩。

• 保留主要特征的同时减少参数和计算量。
• 防止过拟合。（这一层没有参数，不需要学习。）
• 特征不变性：平移（translation）不变性、旋转（rotation）不变性、尺度（scale）不变性。有一定抗扰动作用。

2.3CNN与FCN

关于图像识别：CNN为什么比FCN更有效？

• 全连接神经网络（FCN）：输入图像需要参数量太多。
• 卷积神经网络（CNN）：
  • 稀疏连接：下一层神经元只关注上一层的局部感受野$⟺$神经元识别一些关键的模式，比一整个图像小得多。
  • 参数共享：不同区域的相同模式可用相同的滤波，共享相同的参数（权重和偏置）。
  • 下采样使图像更小，但不改变目标，使处理网络的网络参数较少。

模式：从数据中提取的具有区分性和重复性的抽象特征。

感受野（Receptive Field）：网络中某一层特征图上的一个像素点（或神经元）所能“看到”的输入图像的区域大小。描述了输入空间中影响该神经元响应的范围。

下采样：主要用于压缩特征图尺寸、减少计算量，同时保留重要信息。常见方法：池化（Pooling）、跨步卷积（Strided Convolution）。

关于参数：都是权重$\mathbf{W}$与偏置$\mathbf{b}$

• 全连接神经网络（FCN）：存在于层与层之间，${\mathbf{z}}^l={\mathbf{W}}^l{\mathbf{a}}^{l-1}+{\mathbf{b}}^l$，有$N_{l-1}\times N_l$个权重参数和$N_l$个偏置参数。
• 卷积神经网络（CNN）：存在于每个卷积核中，一个卷积核有$k\times k\times n_c$个权重参数和$1$个偏置参数。

2.4时间复杂度

浮点运算次数（FLOPs，Floating Point Operations）：一次乘法或一次加法算一次（或者一次乘法加上一次加法算一次’Multi-Add’）。

• 单个卷积层的浮点运算次数：

$$\text{FLOPs}=[(k\times k\times n_c)+(k\times k\times n_c-1)+1]\times H_{out}\times W_{out}\times K=2\times k\times k\times n_c\times H_{out}\times W_{out}\times K$$

• 全连接层的浮点计算量：

$$\text{FLOPs}=[N_{in}+(N_{in}-1)+1]\times N_{out}=2\times N_{in}\times N_{out}$$

每个输出神经元对应$N_{in}$次权重乘法，$N_{in}-1$次权重加法，1次加上偏置。

2.5分类网络模型

要会算参数量。

2.5.1LeNet-5

网络架构：3个卷积层（包括1次卷积+1个激活函数+1次最大池化），2个全连接层（包括1个输出层，输出层激活函数为softmax）

• 网络权重参数量：(5*5*1)*6+(5*5*6)*16+(5*5*16)*120+120*84+84*10
• 网络全部参数量：(5*5*1)*6+6+(5*5*6)*16+16+(5*5*16)*120+120+120*84+84+84*10+10

🦌：参数量只需要计算卷积核和全连接层的参数，因为池化操作没有参数。参数计算可看“CNN与FCN”中的”关于参数“部分

2.5.2AlexNet

网络架构：5个卷积层+3个全连接层

优点：

• 比LeNet更深。
• 加入了Dropout层防止过拟合。
• 使用裁剪翻转等操作做数据增强，增强了模型的泛化能力。
• 分块训练，把图像分为两块分别训练后在全连接层合并。

Dropout层：在训练时以0.5的概率使某些神经元的输出为0，丢掉一半结点的输出，BP（反向传播）中也不更新这些结点。

2.5.3ZFNet

思想：使用可视化技术窥视中间特征层的功能，通过反卷积完成。

对比AlexNet：AlexNet第一层有大量高频（边缘）和低频（非边缘）信息的混合，几乎没有覆盖到中间的频率信息。

• ZFNet：第一层卷积核大小（Kernal size）由$11\times 11$改为$7\times 7$，移动步长由4改为2。

2.5.4VGGNet

网络架构：由块结构构成，每个小块内部有多个卷积操作。

多个$3\times 3$卷积层堆叠的优势：感受野更大，参数量更少，更多非线性变换。

• 2个$3\times 3$卷积层 $⟺$ 1个5 $\times$ 5卷积层。
• 3个$3\times 3$卷积层 $⟺$ 1个7 $\times$ 7卷积层。

2.5.5GoogLeNet

Inception Module：使网络深度更深但训练时依然可以很好的收敛。

• 核心思想：将不同的卷积层通过并联的方式结合在一起，经过不同卷积层处理的结果矩阵在深度这个维度拼接起来，形成一个更深的矩阵。

上图对比原始版本增加了黄色的1$\times$1卷积块先进行通道数降维。

瓶颈层：减少计算量。

2.5.6RexNet

残差网络：使网络更容易学习和收敛。

跳转连接（Shortcut，skip connection）：跳过一层或多层的连接。在这里都仅执行恒等映射（不增加参数和计算复杂度）。

• 残差块输入与输出维数相同：$H(x)=F(x)+x$
• 残差块输入与输出维数不同：
  • 空间（$H,W$）不一致：给跳转连接的$x$增加一个线性映射$H(x)=F(x)+W_{s}x$
  • 深度（$n_c$）不一致：用$1\times 1$卷积层进行升维，或者补零。

2.6迁移学习

迁移学习（Transfer learning）：将现有训练好的机器学习模型应用于新的训练中。

• 对整个网络进行微调（fine-tuning）。
• 将网络的原始部分用作特征提取器，仅训练新增的层，不改之前的权重。

七、支持向量机

重点：SVM的思想，原始问题的最优化问题数学表达式

支持向量机（SVM）：使边界点（支持向量）距离分类超平面的间隔最大。

对比LDA和SVM：线性判别分析与支持向量机的对比-CSDN博客

• LDA和SVM的主要区别是什么？

  • LDA是一种假设测试方法，它假设数据是来自不同的高斯分布，并通过最大化类别间的线性相关度来优化。

  • SVM是一种强大的分类和回归方法，它通过寻找最优的分割面(或超平面)来将数据点分为不同的类别。

• LDA和SVM的优缺点有哪些？

  • LDA的优点是它的训练时间较短，对于高维数据集表现较好。LDA的缺点是它对于非线性问题的表现不佳，对于噪声和异常数据的敏感性较高。
  • SVM的优点是它可以处理线性和非线性问题，对于高维数据集表现较好。SVM的缺点是它的训练时间较长，对于噪声和异常数据的敏感性较高。

概念：

• 超平面：$n$维空间中的超平面 ${\mathbf{w}}^T\mathbf{x}+b=0$，$f(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b$。
• 间隔（margin）：分类超平面到最接近它的训练样本（支持向量）之间的距离 $\gamma =\underset{i}{\min }{\gamma }_i=\underset{i}{\min }\frac{y_i({\mathbf{w}}^T\mathbf{x}+b)}{\Vert \mathbf{w}\Vert }$ 。
• 决策函数：$f(\mathbf{x})=\text{sgn}\left(g(\mathbf{x})\right)=\{\begin{array}{ll}1,& g(\mathbf{x})\ge 0\\ -1,& g(\mathbf{x})<0\end{array}$

目标：
$$\underset{\mathbf{w},b}{\max }\gamma \text{s.t.}\frac{y_i({\mathbf{w}}^T\mathbf{x}+b)}{\Vert \mathbf{w}\Vert }\ge \gamma$$
令$\Vert \mathbf{w}\Vert \cdot \gamma =1$，则上式等价于：
$$\underset{\mathbf{w},b}{\max }\frac{1}{\Vert \mathbf{w}\Vert }\text{s.t.}{y}_i({\mathbf{w}}^T\mathbf{x}+b)\ge 1⟺\underset{\mathbf{w},b}{\min }\Vert \mathbf{w}{\Vert }_2\text{s.t.}{y}_i({\mathbf{w}}^T\mathbf{x}+b)\ge 1$$

超平面具有缩放不变性，即$\mathbf{w}$和$b$同比例缩放所得还是同一个平面。可以找到一个缩放值$k$把$\mathbf{w}$和$b$缩放到满足$\Vert \mathbf{w}\Vert \cdot \gamma =1$。

支撑向量：满足$y_i({\mathbf{w}}^T\mathbf{x}+b)=1$

支撑向量机的原始形式（primal form SVM）：
$$\underset{\mathbf{w},b}{\min }\Vert \mathbf{w}{\Vert }_2\text{s.t.}{y}_i({\mathbf{w}}^T\mathbf{x}+b)\ge 1⟺\underset{\mathbf{w},b}{\min }\Vert \mathbf{w}{\Vert }_2^2\text{s.t.}{y}_i({\mathbf{w}}^T\mathbf{x}+b)\ge 1$$

• 求解上式是一个凸二次规划问题（convex quadratic programming），可用二次规划优化软件计算包（CVX）求解。

凸二次规划问题：目标函数是二次，约束条件是线性的。

1.对偶问题

对偶问题（dual problem）：不直接求解有约束的最优化问题，而是通过寻求其对偶问题的解得到它的解。引入作为对偶变量的拉格朗日（lagrange）乘子。

朗格朗日函数：
$$L(\mathbf{w},b,\alpha )=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^m{\alpha }_i\left(y_i({\mathbf{w}}^T\mathbf{x}+b)-1\right)$$

上式即为对偶问题，对偶问题中训练数据总以内积（${\mathbf{x}}_i{\mathbf{x}}_j$）形式出现。

KKT（Karush-Kuhn-Tucker）条件：拉格朗日函数在最优解处必须满足的条件。
$$\{\begin{array}{ll}{\alpha }_i\ge 0& \text{拉格朗日乘子非负}\\ y_{i}f({\mathbf{x}}_i)-1\ge 0& \text{所有样本必须满足约束}\\ {\alpha }_i(y_{i}f({\mathbf{x}}_i)-1)=0& \text{乘子与约束的乘积为零}\end{array}$$
可见对任意的训练样本$({\mathbf{x}}_i,y_i)$，总有${\alpha }_i=0$或者$y_{i}f({\mathbf{x}}_i)=1$：

• ${\alpha }_i=0$：该样本对分割超平面无影响。
• $y_{i}f({\mathbf{x}}_i)=1$：支持向量。

$\Rightarrow$最终分类超平面仅与支持向量有关。

为什么需要${\alpha }_i(y_{i}f({\mathbf{x}}_i)-1)=0$？

• 互补松弛性：只有支持向量会影响最终的超平面。非支持向量的样本对超平面无贡献，从而实现了解的稀疏性。

🦌：上面是AI给的答案，笔者不懂。

序贯最小化算法（Sequential Minimal Optimization，SMO）：求解对偶问题。
$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j\text{s.t.}\sum _{i=1}^n{\alpha }_i{y}_i=0,{\alpha }_i\ge 0,\forall i$$
不断执行以下两个步骤直至收敛：

1. 选一对需要更新的变量${\alpha }_i，{\alpha }_j$
2. 固定其它参数，求解问题更新${\alpha }_i，{\alpha }_j$。

则对偶问题变为：约束条件变了
$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j\text{s.t.}{\alpha }_i{y}_i+{\alpha }_j{y}_j=-\sum _{k\ne i,j}{\alpha }_k{y}_k,{\alpha }_i\ge 0,{\alpha }_j\ge 0$$

求解$b$：取支持向量计算出的所有$b$的均值$b=\frac{1}{|S|}{\sum }_{i\in S}(\frac{1}{y_i}-{\mathbf{w}}^T{\mathbf{x}}_i)$

转换成对偶问题的优点：

• 原始问题的不等式约束转为对偶问题的等式约束。
• 改变问题的复杂度，把SVM从依赖$d$个维度（$\mathbf{w}$的维度）转变为依赖$m$个数据点（$m$个样本）。
• 求解更高效，求解的$\alpha$只与支持向量有关。
• 方便核函数的引入，进而推广到非线性分类问题。

2.核函数

线性模型中，可以把低维空间中的非线性问题转变为高维空间的线性问题。

$\Rightarrow$样本在原始空间线性不可分，就映射到更高维的特征空间使其线性可分。

高维空间划分超平面模型：
$$f(\mathbf{x})={\mathbf{w}}^T\varphi (\mathbf{x})+b$$

核函数（kernel function）：隐式地将输入数据映射到高维特征空间，使得原本线性不可分的数据在高维空间中变得线性可分，而无需显式计算高维映射。
$$k({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)=<\varphi ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)>$$

• 把高维向量的内积转变为求低维向量的内积问题。
• 核函数是一种表征映射、实现内积逻辑关系且降低计算复杂度的特殊函数。

支持向量展式（support vector expansion）：
$$\underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_{j}k({\mathbf{x}}_i,{\mathbf{x}}_j)-\sum _{i=1}^m{\alpha }_i\text{s.t.}\sum _{i=1}^m{\alpha }_i{y}_i=0,{\alpha }_i\ge 0,\forall i$$
梅塞定理（Mercer）：任何半正定的函数都可以作为核函数。

半正定核函数：$k(\mathbf{x},\mathbf{y})=k(\mathbf{y},\mathbf{x})$且任意函数$f$有$\int \int f(\mathbf{x})k(\mathbf{x},\mathbf{y})f(\mathbf{y})dxdy\ge 0$

八、关联分析

重点：项集和规则的支持度，规则的置信度，Apriori算法，频繁项集，强关联规则挖掘，子序列生成，频繁序列。

概念：

• 项（item）：每个商品。定义$I$为所有项的集合。
• 项集（itemset）：多个项组成的集合。$k$-项集含有$k$个项，长度为$k$。
• 事务/交易（transaction）：包含一个标识TID和项集（购买的商品集合）。定义$D$为事务数据库， T = { t 1 , . . . , t N } T=\{t_1,...,t_N\} T={t1​,...,tN​}是所有事务构成的集合。

1.关联规则

关联规则（Association rules）：找到事务数据库中多次重复出现的项/项集之间的关联，$P\to Q$

支持度（Support）：单调不增。度量了频率。最小支持度$minsup:\sigma$
$$\text{sup}(X)=\frac{\#X}{\#D},\text{sup}(X\to Y)=P(X\cup Y)=\frac{\#(X\cup Y)}{\#D}$$

置信度（Confidence）：度量了强度。最小置信度$minconf:\Phi$
$$\text{conf}(X\to Y)=P(Y|X)=\frac{\#(X\cup Y)}{\#X}=\frac{\text{sup}(X\to Y)}{\text{sup}(X)}$$

频繁项集（Frequent Itemsets）：$sup(X)\ge \sigma$，频繁$k$项集记$L_k$

强关联规则（强规则，Strong Rules）：$sup(X\to Y)\ge \sigma 且conf(X\to Y)\ge \Phi$

1.1关联规则挖掘

分解为两个子任务：

1. 生成频繁项集（Frequent Itemset Generation）：发现满足最小支持度阈值的所有项集。
2. 生成规则（Rule Generation）：提取所有高置信度规则。

1.1.1暴力法（Brute-force approach）

计算每个可能规则的支持度和置信度。

计算代价过高：$O(NMW)$

1.1.2先验算法（Apriori）

先验原理（Apriori principle）：$\to$候选集剪枝（Candidate Pruning）

• 如果一个项集$X$是频繁的，则它的所有非空子集$Y\subset X$一定频繁。
• 如果一个项集$X$是非频繁的，则它的所有超集$X\subset Y$一定非频繁。

候选项集生成：$L_k\to C_{k+1}$，只对$L_k$中那些$X$和$Y$前$k-1$项相同且第$k$项不同的频繁项集进行连接，生成$C_{k+1}$的候选项集。

2.序列模式

序列模式（Sequential Pattern）：寻找事务之间时间上的相关性。

序列：$s=<s_1,s_2,...,s_n>$，$s_i$是$s$的一个元素（element） s i = { x 1 , . . . , x k } s_i=\{x_1,...,x_k\} si​={x1​,...,xk​}

• 大小（size）：元素个数$n$。
• 长度（length）：所有项的个数，$k$-序列，$k=\sum k_i$，。
• 子序列：

序列挖掘：满足用户指定最小支持度$\sigma$的所有序列（频繁序列）。

• 支持度：包含s的所有数据序列所占比例。

先验原理（Aprior）：

• 如果一个$k$-序列是频繁的，则它的所有($k-1$)-子序列也频繁。
• 如果一个$k$-序列是非频繁的，则它的超序列也非频繁。

候选序列产生：GSP算法

• 仅当丢弃$s_1$中的第一项获得的子序列与丢弃$s_2$中的最后一项获得的子序列相同时，合并$s_1$和$s_2$。

九、聚类分析

重点：有监督和无监督，k-means聚类，凝聚层次聚类，邻近性度量（单链，全链），树状图，DBSCAN密度聚类基本概念。

无监督学习（Unsupervised Learning）：根据没有标记的样本，从输入数据中发现潜在的结构、模式或分布。

• 没有标记信息（No labels）。
• 数据驱动（Data driven）。

聚类：无监督学习，根据信息相似度原则进行聚类。

分类：监督学习，根据训练样本获得分类器。

类、簇（cluster）：一组在特征空间彼此相似、接近的样本（对象、点）集合，同簇尽可能相似，不同簇尽可能不同。

相异性与相似性度量：

🦌：也可以看之前三、数据与特征工程里的相似性与相异性

1.聚类方法

• 划分方法（Partitioning Methods）：
  • K-均值（K-Means）
  • 顺序领导者方法（Sequential Leader Methods）
  • 基于密度的方法（Density Based Methods）
  • 基于模型的方法（Model Based Methods）
• 层次方法（Hierarchical Methods）

1.1K-means

K-means：适用于各类样本比较密集（球状分布）且样本数目悬殊不大的样本分布。

误差平方和（SSE）：
$$\text{SSE}=\sum _{i=1}^K\sum _{x\in C_i}\Vert x-c_i{\Vert }_2^2,c_i=\frac{1}{n_i}\sum _{x\in C_i}x$$

均方误差（MSE）：$\text{MSE}=\frac{1}{n}{\sum }_{i=1}^n(y_i-{\hat{y}}_i{)}^2$，是SSE/n得到平均数，多用于预测建模中估算误差。

流程：

1. 选择聚类数目K。
2. 随机选择K个中心。
3. 将所有数据点划分到离其最近的类中心所在的类。
4. 计算SSE。
5. 重新分配数据点到离其最近的类中心所在类，并重新计算各类的中心$c_i$。
6. 重复步骤3-5直至没有样本点需要调整（或者重复次数上限）。

优点：

• 简单，收敛较快，时间复杂度$O(I\times K\times n\times m)$，$I$是收敛所需迭代次数，$K$个中心，$n$个数据点，$m$个类别。

缺点：

• 需提前指定K值。
• 可能会收敛到局部最优点$\to$尝试不同初始中心点。
• 对噪声数据和异常值敏感。
• 只适合球形分布样本聚类。

1.2层次聚类

分类：

• 凝聚的（自下而上）：从点作为个体簇开始，每一步合并两个最接近的簇，直至只剩下一个簇。
• 分裂的（自上而下）：从包含所有点的某个簇开始，每一步分裂一个簇。

表示方法：

• 树状图（dendrogram）
• 嵌套簇图（nested cluster diagram）

1.2.1凝聚方法（Agglomerative Methods）

邻近性度量：

• 单链（single link，MIN）：不同簇的两个最近的点之间的邻近度。
• 全链（complete link，MAX）：不同簇中两个最远点之间的邻近度。
• 组平均（group average）：不同簇的所有点对邻近度的平均值。

距离（相异度）作为邻近度度量$\to$值越小点越接近（单链：小中取小；全链：大中取小）。

相似度作为邻近度度量$\to$值越大点越接近（单链：小中取大；全链：大中取大）

🦌：“小中取小”：第一个“小”指单链定义，取点距离的最小值作为两个簇间距离；第二个“小”指的相异度定义，取相异度最小值即最相似的两个簇进行合并。

1.3基于密度的聚类方法

密度：指定样本周围一定半径内所包含的样本数量。

样本点分为：

• 核心点（core point，稠密区域内部的点）：给定邻域内的点的个数超过给定的阈值（$MinPts$）。
• 边界点（border point，稠密区域边缘上的点）：不是核心点，落在某个或多个核心点的邻域内。
• 噪声点/背景点（noise point，稀疏区域中的点）

DBSCAN：典型的基于密度方法，能从含有噪声的空间数据库中发现任意形状的聚类。

概念：

• 领域半径 Eps：半径为Eps内的区域。
• 阈值：MinPts。
• 直接密度可达：样本集合D。样本点$q$在$p$的Eps邻域内，且$p$为核心点，则点$q$从点$p$直接密度可达（密度直达）。
• 密度可达：样本集合D，一串样本点$p_1,p_2,...,p_n,p=p_1,q=p_n$。$p_i$从$p_{i-1}$直接密度可达，则点$q$从点$p$密度可达。
• 密度相连：样本集合D，任意点$o$，存在点$p$到点$o$密度可达，且点$q$到点$o$密度可达，则点$q$到点$p$密度相连。

🦌：直接密度可达，就是q在p的圈里；密度可达，就是q可以不是核心点，q之前的点都是核心点且圈两两交叉（过圆心），q在前一个点的圈里；密度相连就是两个密度可达同一个点的点。

流程：

1. 初始化：所有点标记为“未访问”。
2. 核心点判断：
   • 随机选一个未访问点 p，计算其 ε-邻域。
   • 若 p 是核心点，启动簇扩展；否则标记为噪声。
3. 簇扩展：
   • 从 p 出发，递归/迭代地找到所有密度可达的点，形成簇。
4. 终止：重复上述步骤，直到所有点被访问。

优点：

• 能发现任意形状的簇。
• 对噪点不敏感。

缺点：

• 对两个参数（Eps，MinPts）设置敏感。
• 不适合样本集密度不均匀、聚类间距相差很大。
• 数据样本集越大，收敛时间越长。

🦌：恭喜你看完了！应该对整个课程内容有大致了解和掌握了吧！祝你考试顺利！

如果你感兴趣

1.特征提取技术之一：梯度方向直方图（HOG）

方向梯度直方图（Histogram of Oriented Gradient, HOG）：通过计算和统计图像 局部区域 的梯度方向直方图来构成特征。

来源：机器学习与数据挖掘-ch1 绪论_2025.pdf

参考文章：图像特征：方向梯度直方图 HOG_图像的梯度方向直方图特征地图-CSDN博客

2.线性代数技术：奇异值分解

奇异值分解（Singular Value Decomposition, SVD）：对于任意 $m\times n$ 的实数或复数矩阵 $\mathbf{A}$，其奇异值分解为：$\mathbf{A}=\mathbf{U\Sigma V}$

其中：

• $\mathbf{U}$：$m\times m$的正交矩阵（左奇异向量），列向量为单位正交向量。
• $\mathbf{\Sigma }$：$m\times n$的对角矩阵，对角元素为非负的奇异值（通常按降序排
• 列），其余元素为零。
• $\mathbf{V}$：$n\times n$的正交矩阵的共轭转置（右奇异向量），列向量为单位正交向量。

若 $\mathbf{A}$为实数矩阵，则 $\mathbf{U}$ 和 $\mathbf{V}$为正交矩阵，即${\mathbf{V}}^{\ast }={\mathbf{V}}^T$ 。

来源：机器学习与数据挖掘-ch3-线性模型.pdf

参考文章：超详细解释奇异值分解（SVD）【附例题和分析】-CSDN博客