跳转至

认知计算与机器学习速成指南

考试重点:

  • [x] 机器学习基本问题
  • [x] 常用度量与评价方法
  • [x] 常用分类算法
  • [x] 常用聚类算法
  • [ ] BP算法
  • [x] 典型卷积神经网络
  • [x] 典型循环神经网络
  • [x] Attention 与 Transformer

推荐学习:

  1. 动手学机器学习 🌟
  2. 动手学深度学习

第一章 概述

机器学习的基本思想

动手学机器学习-Ch5

机器学习的基本问题

Danger

这个考过

机器学习的5类问题：分类、预测、聚类、联想、优化

  1. 分类问题
    • 目标: 将输入数据分为离散的类别标签
    • 方法: 决策树 / 贝叶斯方法 / 支持向量机 / 神经网络
    • 应用: 手写数字识别 (MNIST)
  2. 预测问题
    • 目标: 预测一个连续的数值输出
    • 方法: 深度学习 / 线性回归 / 非线性回归 / 灰色预测模型
    • 应用: 房价预测
  3. 聚类问题
    • 目标: 把已知数据集划分为不同子集, 不同类别之间的差距越大越好，同一类别内的数据差距越小越好
    • 方法: 无监督深度学习方法 / 划分聚类法 / 层次聚类法
    • 应用: 用户画像 (将用户划分为不同的兴趣群体，用于个性化推荐)
  4. 联想问题
    • 目标: 就是“相关性分析”, 发现不同数据（属性）之间的相互依赖关系
    • 方法: 反馈神经网络 / 关联规则 / 回归分析
    • 应用: 入侵检测 | 推荐系统
  5. 优化问题
    • 目标: 寻找某个目标函数在目标区间上的最优解(max/min)
    • 方法: 梯度下降 / 牛顿法 / 线性规划 / 群体智能优化 (蚁群/退火/...)
    • 应用: 路径规划(TSP)

机器学习的基本方式

机器学习的5种基本方式：有监督学习、无监督学习、半监督学习、自监督学习、强化学习

  1. 有监督学习
    • 特征: 所有数据都有一个标签
    • 解决问题: 分类 / 预测
  2. 无监督学习
    • 特征: 所有数据都没有标签
    • 解决问题: 聚类
  3. 半监督学习
    • 特征: 大部分数据没有标签
    • 解决问题: 分类 / 预测
  4. 自监督学习
    • 特征: 所有数据都没有标签, 但是训练过程是有监督的
    • 解决问题: 特征学习
  5. 强化学习
    • 特征: 不需要预先给定标签数据, 而是通过 接收环境对动作的奖励(反馈) 获得学习信息并更新模型参数
    • 解决问题: 优化 (最优决策)

机器学习的基本过程

(1) 机器学习系统的基本结构

alt text

(2) 机器学习的基本过程

  • 训练
    • 收集数据
    • 清洗数据
    • 深度学习: 特征提取 + 模型训练
    • 获得知识
  • 推理
    • 应用和检验知识

(1) 清洗数据

  1. 格式转换与归一化处理
  2. 决定数据的属性列表
  3. 处理数据缺失值与异常值
  4. 选择采样方法

(2) 特征提取 (把原始数据变成特征向量)

  1. 原始数据中发现特征
  2. 选择最适合的特征
  3. 降低特征向量的维度
  4. 数据变换: 降噪 / 降维

(3) 模型训练 (不同模型适用于不同的任务和应用)

  • 分类与预测:
    • KNN / ANN / 朴素贝叶斯 / SVM
  • 回归与泛化:
    • 逻辑斯蒂回归 / 多元线性回归
  • 解释与描述:
    • 决策树 / 关联规则
  • 异常检测与趋势分析:
    • ANN / 统计方法 / 时序预测分析

第二章 数据与度量

常见数据类型

  1. 记录数据: 数组/矩阵/数据库
  2. 图数据: 拓扑图
  3. 有序数据:
  • 图像: 记录数据
  • 视频: 记录数据 + 有序数据

常见属性类型

  1. 名词属性: 相异
  2. 顺序属性: 相异，有序
  3. 区间属性: 相异，有序，加法
  4. 比值属性: 相异，有序，加法，乘法

数据预处理

(1) 归一化处理

  • 做法: 对原始数据进行变换，消除量纲，将数据值规范到 [0,1] 区间内
  • 目的: 经过归一化处理后，各属性值处于同一数量级，解决了数据属性之间的可比性问题

(2) 归一化/标准化方法

  1. 线性方法 (aka. 最大最小法) $$ v = \frac{x - \min}{\max - \min} $$
  2. Z-Score方法 (经过处理的数据符合标准正态分布) $$ v = \frac{x - \mu}{\delta} $$
  3. 特殊函数 alt text

相似性与相异性度量

1) 距离与度量

度量是距离的一个子集

距离是一种度量，必须满足以下条件:

  1. 非负性
  2. 对称性
  3. 三角不等式法则

很显然，度量的要求更高

2) 相似性与相异性

  • 相似性:
    • [0,1], 数值越大, 相似程度越高
    • 对称性: \(s(p,q)\) = \(s(q,p)\)
  • 相异性:
    • 欧几里得距离
    • 明科夫斯基距离

相异性度量

(1) 欧几里得距离

\[ dist = \sqrt{\sum_{k=1}^{n}{(p_k - q_k)^2}} \]
  • \(n\): 维数
  • \(p_k\) and \(q_k\): p和q的第k个属性值
  • 如果各维值域(标度)不同, 则需要进行归一化与标准化处理

(2) 明科夫斯基距离

\[ dist = (\sum_{k=1}^{n}{(|p_k - q_k|)^r})^{\frac{1}{r}} \]
  • \(n\): 维数
  • \(p_k\) and \(q_k\): p和q的第k个属性值
  • 欧几里得距离是它的一个特例(r=2)
Warning

闵可夫斯基距离不是一种距离，而是一类距离的定义。它其实就是“距离度量”。

(3) 距离度量

\[ dist = (\sum_{k=1}^{n}{(|p_k - q_k|)^r})^{\frac{1}{r}} \]
  • \(r=1\): 曼哈顿距离（绝对值距离）
  • \(r=2\): 欧几里得距离（\(L_2\)范数）
  • \(r=\inf\): 无穷范数（数据对象中绝对值最大的数）

alt text

相似性度量

(1) 余弦相似度

alt text

  • 相似度为1: 夹角=0，相似度最高
  • 相似度为0: 正交
  • 相似度为-1: 完全相反的方向

(2) 距离倒数

alt text

  • 距离=0，相似度为1
  • 距离为\(\inf\)，相似度为0

(3) 杰卡德系数

alt text

  • 集合的重合度越高，相似度就越高
  • 1-s(A,B)是杰卡德距离，是“度量”

(4) Dice系数

alt text

  • 集合的重合度越高，相似度就越高
  • 1-s(A,B)是Dice距离，不是“度量”

(5) 皮尔逊相关系数

alt text

  • 线性正相关: 相似度为1
  • 线性负相关: 相似度为-1
  • 线性无关: 相似度为0

3) 熵

  • 熵: 0 表示没有任何差异
  • 交叉熵: 估计分布q与真实分布p之间的差异
  • KL散度: 度量分布q与p之间的差异，类似于距离，值域[0,∞]
    • 不是标准的距离，因为不满足交换律
  • 互信息:
    • 若 X 与 Y 独立，则 P(X,Y) = P(X) x P(Y)，I(X,Y) 就为 0
    • X,Y 关系越密切 I(X,Y) 越大，最大值是 H(Y)，即: 完全相关 alt text

评价机器学习结果

1) 评价原则

(1) 模型鲁棒性: 模型处理各种 非正常数据 的能力

  • 噪声数据
  • 缺失信息的数据
  • 错误数据/有矛盾的数据

(2) 模型适应性: 指对于不同数据，学习模型本身需要做多少人工调整

(3) 模型的简洁性和可解释性: Less is more

2) 取训练集和测试集

保留法

常用于已知数据量很大的时候

取 S 的一部分（通常为2/3）作为训练数据，剩下的部分（通常为1/3）作为测试数据

交叉验证法

常用于已知数据量不太大的时候

  • 把S划分为k个不相交的子集
  • 取其中一个子集作测试集，剩下数据作训练集
  • 此过程可以轮询

随机法

  • 随机抽取S中的一部分数据作为测试数据，把剩下的数据作为训练数据
  • 重复多次

3) 度量学习结果有效性的常用指标

Danger

这个考过, 很喜欢考, 连考2年了

(1) 误差 (Error)

Def: 在数据集 T 上的误差

\[ Error(T) = \sum_{i=1}^{|T|}{P_i \times ||E_i - L_i||} \]

|T| 表示数据集大小

  • 均方误差 MSE $$ MSE = \frac{1}{|T|} \times \sum_{i=1}^{|T|}{(E_i - L_i)}^2 $$
  • 平均绝对误差 MAE $$ MAE = \frac{1}{|T|} \times \sum_{i=1}^{|T|}{|E_i - L_i|} $$

(2) 正确率 (Accuracy)

顾名思义：正确处理的数据个数与所有被处理数据个数的比值

\[ Accuracy = \frac{T_{error<\epsilon}}{T} \]

(3) 复合指标

  • 精度（Precision，或称为命中率，准确率）
  • 召回率（Recall，或称为覆盖率，灵敏度）
Warning

表达式很奇怪，不需要知道起名原因，背了就行

alt text

  • a: TP 真正例
  • b: FP 假正例
  • c: TN 真负例
  • d: FN 假负例

4) AUC 曲线

Danger

这个考过

  • 假阳性率: False Positive Rate
  • 假阴性率: False Negative Rate

alt text

5) Fbeta

Danger

这个考过

\(F_{\beta}\) 测量:

\[ F_{\beta} = \frac{(\beta^2 + 1) \times precision(T) \times recall(T)}{(\beta^2 \times precision(T)) + recall(T)} \]
  1. \(F_1\) 测量: $$ F_1 = \frac{2 \times precision(T) \times recall(T)}{precision(T) \times recall(T)} $$
  2. \(\beta\) 是人为定义的:
    • β>1时召回率(Recall)权重更高，β<1时精确率(Precision)权重更高

6) 混淆矩阵

alt text

  • 每一行：代表真实的类别（True Labels）
  • 每一列：代表模型的预测类别（Predicted Labels）
  • 对角线上的数值：表示被正确分类的样本数（即真实类别和预测类别一致）
  • 非对角线上的数值：表示被错误分类的样本数（即真实类别和预测类别不一致）

比如:

  • 第一行第一列的“52”表示：真实类别为 daisy 的样本中，有 52 个被正确预测为 daisy
  • 第一行第二列的“5”表示：真实类别为 daisy 的样本中，有 5 个被误预测为 dandelion
  • 以此类推，每个格子表示“真实为某类，预测为某类”的样本数量

TL;DR

这里感觉理解含义更重要:

非常重要, 对于T/P的理解
  • “P”表示模型预测为正，“N”表示模型预测为负
  • “T”表示预测和实际一致（True），“F”表示预测和实际不一致（False）
实际为正 实际为负
预测为正 TP(a) FP(b)
预测为负 FN(d) TN(c)
  • TP（True Positive，真正例）：预测为正，实际也为正（比如: 病人真有病，模型也说有病）
  • FP（False Positive，假正例）：预测为正，实际却是负（比如: 健康人被误诊为有病）
  • TN（True Negative，真负例）：预测为负，实际也为负（健康人被正确诊断为健康）
  • FN（False Negative，假负例）：预测为负，实际却是正（病人被误诊为健康）

(1) 正确率 Acc:

预测正确的概率

\[ Acc = \frac{TP+TN}{TP+FP+TN+FN} \]

(2) 精确率 Pre:

模型判为“正”的里面，有多少是真的正（查准率）

\[ Pre = \frac{TP}{TP+FP} \]

(3) 召回率 Recall（也叫敏感度 Sensitivity）

aka. 真正率/阳性率 TPR

实际为“正”的里面，有多少被模型找出来了（查全率）

\[ TPR = \frac{TP}{TP+FN} \]

(4) 特异度 Specificity

aka. 真负率/真阴性率 TNR

实际为“负”的里面，有多少被模型正确识别为负

\[ TNR = \frac{TN}{TN+FP} \]

(5) 假阴性率 FNR

\[ FNR = 1 - TNR \]

(6) 假阳性率 FPR

\[ FPR = 1 - TPR \]

第三章 分类方法

KNN

这个考过

KNN (K-Nearest Neighbor) 是最简单的机器学习算法之一，可以用于分类和回归，是一种监督学习算法。

它的思路是这样，如果一个样本在特征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

也就是说， 该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定 待分样本所属的类别。

alt text

如上图所示，图中的正方形和三角形是打好了label的数据，分别代表不同的标签，那个绿色的圆形是我们待分类的数据。

  • 如果选K=3，那么离绿色点最近K个点中有2个三角形和1个正方形，这3个点投票，三角形的比例占2/3，于是绿色的这个待分类点属于三角形类别

  • 如果选K=5，那么离绿色点最近K个点中有2个三角形和3个正方形，这5个点投票，蓝色的比例占3/5，于是绿色的这个待分类点属于正方形类别

算法过程

  1. 计算待分类点与已知类别的点之间的距离
  2. 按照距离递增次序排序
  3. 选取与待分类点距离最小的K个点
  4. 确定前K个点所在类别的出现次数
  5. 返回前K个点出现次数最高的类别作为待分类点的预测分类

算法要点

  1. 算法超参数K
  2. 距离度量，特征空间中样本点的距离是样本点间相似程度的反映
  3. 分类决策规则，少数服从多数

(1) K值的选取

作为KNN算法中唯一的一位超参数，K值的选择对最终算法的预测结果会产生直观重要的影响。

如果选择较小的K值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有输入实例较近的训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。容易发生过拟合。

k过小, 易“过拟合”: 仅依赖极少数近邻样本进行预测，过度关注训练数据中的细节和噪声

如果选择较大的K值，就相当于用较大邻域中的训练实例进行预测，其实优点是减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的训练实例也会起预测作用，使预测发生错误，k值的增大就意味着整体的模型变得简单，容易发生欠拟合。

k过大, 易“欠拟合”: 考虑过多邻居导致决策边界过于平缓，无法捕捉数据局部特征

在应用中，通常采用交叉验证法来选择最优K值。从上面的分析也可以知道，一般K值取得比较小。我们会选取K值在较小的范围，同时在验证集上准确率最高的那一个确定为最终的算法超参数K。

超参数

超参数（hyperparameter）是指在模型训练之前需要人为设定的参数，其值不会通过训练数据自动学习得到，而是通过经验、规则或搜索方法（如交叉验证）来确定。

例如，在KNN（K-近邻）算法中，K值（即“最近邻”的数量）就是一个典型的超参数

(2) 距离度量选择

\[ dist = (\sum_{k=1}^{n}{(|p_k - q_k|)^r})^{\frac{1}{r}} \]
  • \(r=1\): 曼哈顿距离（绝对值距离）
  • \(r=2\): 欧几里得距离（\(L_2\)范数）
  • \(r=\inf\): 无穷范数（数据对象中绝对值最大的数）
过拟合与欠拟合
  • 过拟合: 模型过度适应训练数据中的噪声 和偶然规律，导致在新数据上表现显著下降
    • 原因: 模型复杂度过高 (如KNN中K=1) / 存在大量无关特征
  • 欠拟合: 模型未能学习数据中的基本规律，在训练集和新数据上表现均不佳
    • 模型过于简单 (如KNN中K=N) / 过早停止训练

决策树

基尼系数

基尼系数（Gini Index）是机器学习中决策树算法用于衡量数据集纯度或分类不确定性的核心指标，尤其在CART（分类与回归树）算法中作为划分属性的依据。其核心思想是：基尼系数越小，数据纯度越高

(1) 基尼系数通过以下公式计算：

\[ \text{Gini}(D) = 1 - \sum_{k=1}^K p_k^2 \]
  • \(K\)：数据集中类别的数量
  • \(p_k\)：第 \(k\) 类样本在数据集中的占比

基尼系数反映了从数据集中随机抽取两个样本，其类别不一致的概率。例如：

  • 若数据集完全纯净（仅一类样本），基尼系数为0（\(1 - 1^2 = 0\)）
  • 若两类样本各占50%，基尼系数为0.5（\(1 - (0.5^2 + 0.5^2) = 0.5\)）

(2) 决策树通过最小化基尼系数选择最优划分属性，具体步骤为：

  1. 计算划分前的基尼系数：评估当前数据集的纯度
  2. 尝试不同划分条件：对每个特征的可能取值进行划分，生成子集
  3. 计算 划分后的加权基尼系数 ： $$ \text{Gini}_{\text{split}} = \frac{|D_1|}{|D|} \text{Gini}(D_1) + \frac{|D_2|}{|D|} \text{Gini}(D_2) $$ 其中 \(D_1\) 和 \(D_2\) 是划分后的子集
  4. 选择基尼增益最大的划分：基尼增益定义为划分前后基尼系数的差值，增益越大说明划分效果越好

(3) 示例：

假设数据集包含10个样本（6个“是”，4个“否”），基尼系数为：

\[ 1 - \left(\frac{6}{10}\right)^2 - \left(\frac{4}{10}\right)^2 = 0.48 \]

若按某个特征划分为两个子集（子集1：4个“是”，1个“否”；子集2：2个“是”，3个“否”），则划分后的基尼系数为：

\[ \frac{5}{10} \left(1 - \left(\frac{4}{5}\right)^2 - \left(\frac{1}{5}\right)^2\right) + \frac{5}{10} \left(1 - \left(\frac{2}{5}\right)^2 - \left(\frac{3}{5}\right)^2\right) = 0.4 \]

基尼增益为 \(0.48 - 0.4 = 0.08\)，说明此划分有效。

基尼系数 vs 信息熵

两者均用于衡量数据不确定性，但有以下区别：

指标 基尼系数 信息熵
计算复杂度 仅需平方运算，计算更快 涉及对数运算，计算稍慢
实际效果 与信息熵相似，常作为默认选择 更偏向生成多分支的树结构
应用场景 Scikit-learn中CART算法的默认划分标准 ID3、C4.5算法的划分依据

信息熵

略

决策树模型

alt text

  1. “criteria”超参数定义了分割是“好”还是“坏”, 对应于基尼系数的比较
  2. 随机性是过程的一部分，“splitter”可以为模型添加一些可变性
  3. 用“max_depth”、“min_impurity_decrease”和“min_samples_split”处理欠拟合和过拟合

随机森林

算法思想

  1. 使用多颗树进行单独预测，最后的结论由这些树预测结果的组合共同来决定
  2. 每个基分类器可以很弱，但最后组合的结果通常很强

算法过程

对于分类问题:

每个基算法（决策树）单独预测，最后的结论由全部基算法进行投票

对于回归问题:

每个基算法（决策树）单独预测，最后的结论由全部基算法求平均 (加权平均)

朴素贝叶斯

如何理解朴素贝叶斯?

一个物品，有很多特征，我们认为物品可以表示成 \(X = (x_1, x_2, x_3, ..., x_d)\) (\(x_i\) 表示某特征)，现在我们想知道它属于哪个类。

也就是说，我们想对“具备 \(x_1, x_2, x_3, ..., x_d\)”特征的物品，求它所属的类 \(y\)。

等价于求:

\[ P(y|x_1, x_2, x_3, ..., x_d) \]

alt text

支持向量机

算法动机

alt text

alt text

形式化定义

alt text

线性可分数据

✅

线性不可分数据

SVM巧妙地通过核函数（Kernel function）避开了这种非线性变换。用特征向量 Φ(x) 代替输入向量 x

核函数

思想: 将特征空间的内积替换成了核函数，而运算实际上是在样本空间中进行的

性质: 核函数 的线性组合仍是 核函数

常用的Kernel函数:

\[ k(x, x_i) = [(x \cdot x_i) + 1]^q \]
\[ k(x, x_i) = exp{(- \frac{||x - x_i||^2}{\delta^2})} \]
\[ k(x, x_i) = tanh(\gamma(x \cdot x_i) + c) \]

逻辑回归

逻辑斯谛函数

\[ \delta(x) = \frac{1}{1 + e^{-x}} \]

alt text

性质:

\[ \frac{d\delta(x)}{dx} = \delta(x) \cdot (1 - \delta(x)) \]

目的:

\[ \theta^T \cdot x \rightarrow \{0,1\} \]

进行广义线性变换:

\[ f_{\theta}(x) = \delta(\theta^T \cdot x) \]

最大似然估计

任务: 寻找逻辑斯谛回归的参数 \(\theta\) 使得模型在训练数据上预测出正确标签的概率最大

设有 \(N\) 个样本 \(x_1, \dots, x_N\)，类别分别是 \(y_1, \dots, y_N\)。对于样本 \(x_i\)，如果 \(y_i=0\)，那么模型预测正确的概率为 \(1 - f_{\theta}(x_i)\)；如果 \(y_i=1\)，那么概率为 \(f_{\theta}(x_i)\)。

将两者综合起来，可以得到模型正确的概率为 \(f_{\theta}(x_i)^{y_i} (1 - f_{\theta}(x_i))^{1-y_i}\)。

假设样本之间是两两独立的，那么模型将所有样本的分类都预测正确的概率就等于单个样本概率的乘积：

\[ L(\theta) = \prod_{i=1}^N f_{\theta}(x_i)^{y_i} (1 - f_{\theta}(x_i))^{1-y_i} \]

该函数也称为似然函数（likelihood function）。为了使模型的预测尽可能准确，我们需要寻找使似然函数最大的参数 \(\theta\)。但是，该函数的连乘形式使得求导和优化都很困难，在计算机上直接计算甚至很容易造成浮点数溢出。因此，我们一般将似然值取对数，也即是对数似然（log-likelihood），将连乘转化为求和：

\[ l(\theta) = \log L(\theta) = \sum_{i=1}^N [y_i \log f_{\theta}(x_i) + (1 - y_i) \log (1 - f_{\theta}(x_i))] \]

由于对数函数是单调递增的，优化 \(l(\theta)\) 和 \(L(\theta)\) 可以得到相同的结果。于是，我们的优化目标为：

\[ \max_{\theta} l(\theta) \]

第四章 人工神经网络与深度学习

感知机

(1) 感知机（perceptron）的概念:

从生物接受刺激、产生感知的过程出发，用神经网络抽象出了这一模型，如图 8-2 所示

  1. 与原始的神经网络类似，输入经过神经元后被乘上权重并求和
  2. 但是，感知机还额外引入了偏置（bias）项，把它一起加到求和的结果上
  3. 最后，该结果再通过模型的激活函数（activation function），得到最终的输出

alt text

(2) 感知机中有两个新引入的结构:

第一是偏置，它相当于给线性变换加入了常数项。我们知道，对于一个纯线性函数 \(f(x) = kx\) 来说，无论我们如何调整参数 \(k\)，它都一定经过原点。而加入常数项变为 \(f(x) = kx + b\) 后，它就可以表示平面上的任意一条直线，模型的表达能力大大提高了。

第二是激活函数，它可以模拟神经元的兴奋和抑制状态。在感知机中，激活函数通常是示性函数 \(I(z \ge 0)\)。当输入 \(z\) 非负时，函数输出 \(1\)，对应兴奋状态；输入为负数时，函数输出 \(0\)，对应抑制状态。整个感知机模拟了一个经神经元受到输入刺激后给出反应的过程，可以用来解决二分类问题。

(3) 感知机的自学习机制:

Tip

动机: 利用生物中的负反馈调节机制来调整感知机的参数

感知机最重要的进步在于，它的参数可以自动调整，无须再由人工繁琐地一个个调试。假设二分类问题中，样本的特征为 \(x_1, \dots, x_m\)，标签 \(y \in \{0, 1\}\)。那么感知机对该样本的预测输出为：

\[ \hat{y} = I\left(\sum_{i=1}^m w_i x_i + b \ge 0\right) \]

罗森布拉特利用生物中的负反馈调节机制来调整感知机的参数。对于该样本，感知机收到的反馈为 \(\hat{y} - y\)。其参数根据反馈进行更新:

\[ w_i \leftarrow w_i - \eta (\hat{y} - y) x_i; \]
\[ b_i \leftarrow b_i - \eta (\hat{y} - y) \]

简单理解正确性:

  1. if \(\hat{y}\) > \(y\): 说明预测偏高, 需要给 \(w_i\) 和 \(b_i\) 都减小
  2. else, ...
学习率
  • η 是一个小的正数，称为学习率。它控制了每次更新的“步长”或幅度
  • η 越大，每次调整越大，学习可能更快，但也可能不稳定或“矫枉过正”
  • η 越小，每次调整越小，学习更稳定，但可能需要更多次迭代才能收敛

隐含层与多层感知机

多层感知机（multi-layer perceptron，MLP）

动机: 上述的感知机无法解决异或问题

红点和蓝点无法只通过一条直线分隔开

alt text

为进一步增强网络的表达能力，突破只能解决线性问题的困境，有研究者提出增加网络的层数，即将一个感知机的输出作为输入，连接到下一个感知机上。如果一个感知机对应平面上的一条直线，那么多个感知机就可以将平面分隔成多边形区域，达到超越线性的效果:

alt text

如何计算多层感知机的表达式

边上的数字 \(w\) 代表权重。偏置 \(b\) 和激活函数 \(I\) 都直接标注在了神经元上，神经元将所有输入相加后经过激活函数，再向后输出:

alt text

(1) 左侧多层感知机的最终输出:

第一层神经元输出：

  • 上方神经元： $$ z_1 = x_1 \times 1 + x_2 \times (-1) + (-0.5) $$ $$ h_1 = \mathbb{I}(z_1 \ge 0) $$

  • 下方神经元： $$ z_2 = x_1 \times (-1) + x_2 \times 1 + (-0.5) $$ $$ h_2 = \mathbb{I}(z_2 \ge 0) $$

第二层神经元输出： $$ z_3 = h_1 \times 1 + h_2 \times 1 + (-0.5) $$ $$ y = \mathbb{I}(z_3 \ge 0) $$

(2) 右侧多层感知机的最终输出:

第一层神经元输出：

  • 上面神经元: $$ z_1 = x_1 $$ $$ h_1 = \mathbb{I}(z_1 \ge 0) $$

  • 中间神经元: $$ z_2 = x_1 \times 1 + x_2 \times 1 + (-1.5) $$ $$ h_2 = \mathbb{I}(z_1 \ge 0) $$

  • 下面神经元: $$ z_3 = x_2 $$ $$ h_3 = \mathbb{I}(z_3 \ge 0) $$

第二层神经元输出： $$ z_3 = h_1 \times 1 + h_2 \times (-2) + h_3 \times 1 + (-0.5) $$ $$ y = \mathbb{I}(z_3 \ge 0) $$

可以将之前异或问题的 \(x_1, x_2\) 不同取值代入上述表达式，得到最终输出 (发现这两个感知机等价)

前馈网络

当我们组合多个单层的感知机时，通常采用前馈（feedforward）结构，即将神经元分为不同的层，每一层只和其前后相邻层的神经元连接，层内以及间隔一层以上的神经元之间没有连接。

这样，我们可以将网络的结构分为直接接收输入的输入层（input layer）、中间进行处理的隐含层（hidden layer）、以及最终给出结果的输出层（output layer）。

图示是一个 "两层" 的前馈网络示意图。 需要注意，前馈网络的层数是指权重的层数，即边的层数 ，而神经元上不携带权重!

alt text

下面，我们以图中的三层 MLP 为例，详细写出 MLP 中由输入计算得到输出的过程。

alt text

设第 \(i\) 层的权重、偏置和激活函数分别为 \(W_i\), \(b_i\) 和 \(\phi_i\)。那么对于输入 \(x \in \mathbb{R}^3\)，该 MLP 进行的运算依次为：

  • 第一层：\(l_1 = \phi_1(W_1 x + b_1)\)。由于下一层的维度是 4，因此 \(W_1 \in \mathbb{R}^{4 \times 3}\)，\(b_1 \in \mathbb{R}^4\)，输出 \(l_1 \in \mathbb{R}^4\)
  • 第二层：\(l_2 = \phi_2(W_2 l_1 + b_2)\)。同理，\(W_2 \in \mathbb{R}^{2 \times 4}\)，\(b_2 \in \mathbb{R}^2\)，输出 \(l_2 \in \mathbb{R}^2\)
  • 第三层，即输出层：\(y = \phi_3(W_3 l_2 + b_3)\)。由于输出 \(y\) 是标量，这里 \(W_3 \in \mathbb{R}^{1 \times 2}\)，\(b_3 \in \mathbb{R}\)

常用的激活函数 \(\phi(x)\)

  1. Logistics: \(Logistics(x) = \frac{1}{1+e^{-x}}\) alt text
  2. tanh: \(tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}\) alt text
  3. ReLU: \(ReLU(x) = max\{x, 0\}\) alt text

反向传播算法

这个考过, 这个超级无敌重要

设计动机

在神经网络训练中，核心目标是调整网络参数（例如权重 \(W_i\)​ 和偏置 \(b_i\)​），以最小化一个预定义的损失函数 \(J\)（Loss Function）

该损失函数量化了网络输出 \(y\) 与期望目标值 \(y_true\)​ 之间的差异 ‼️

基于梯度的优化算法（如梯度下降法）是实现这一目标的主要手段，其 关键在于计算损失函数 \(J\) 相对于网络中所有可训练参数的偏导数 （即梯度），例如 \(\frac{∂J}{​∂W1}\)​

数学原理

反向传播算法的数学基础是微积分中的链式法则（Chain Rule）

对于复合函数，如 y=f(g(h(x)))，其导数可通过各函数导数的乘积计算:

\[ \frac{dy}{dx} = f'(g(h(x))) \cdot g'(h(x)) \cdot h'(x) \]

alt text

以上面提到的那个2层“前馈”神经网络为例，看看BP算法是怎么工作的:

alt text

手推一下:

bp

最后, 设学习率为 \(\eta\)，我们可以根据梯度下降算法更新网络的参数:

\[ W_i \leftarrow W_i - \eta \cdot \frac{dJ}{dW_i} \]
\[ b_i \leftarrow b_i - \eta \cdot \frac{dJ}{db_i} \]
Danger

看完这一部分，我已经完全理解并掌握BP算法的原理和推导了

不过很遗憾，考试要默写又臭又长的PPT上的梯度表示公式，因此需要强记并手推一遍

TBD

卷积神经网络

0) 基础知识

(1) 卷积的计算

alt text

上图给出了一个 \(2 \times 2\) 的卷积核作用到 \(3 \times 3\) 的图像上得到的结果

很显然, 由于 图像 边界的存在， 卷积 得到的结果会比原来的图像更小。设原图宽为 \(W\)，高为 \(H\)，卷积核的宽和高分别为 \(W_k\) 和 \(H_k\)，易知输出图像的大小为:

\[ W_{out} = W - W_k + 1 \]
\[ H_{out} = H - H_k + 1 \]

(2) 填充 (padding)

有时候，我们希望输出图像能保持和输入图像同样的大小，因此会对输入图像的周围进行 填充（padding） ，以此抵消卷积对图像尺寸的影响。

填充操作会在输入图像四周补上数层额外的像素，假设为了保持图像尺寸不变，需要填充的总层数为:

\[ W_{pad} = W_k - 1 \]
\[ H_{pad} = H_k - 1 \]

填充常用的方式有全零填充、常数填充、边界扩展填充等等。其中，全零填充和常数填充即用0或某指定的常数进行填充，边界扩展填充则是将边界处的值向外复制。

通常来说，如果 \(W_{pad}\) 或 \(H_{pad}\) 是偶数，那么在两侧各填充总层数的一半以保持对称。因此，一般来说我们希望:

\(W_{pad}\) 或 \(H_{pad}\) 是偶数, 即: \(W_k\) 或 \(H_k\) 是奇数

当然也 可以根据需要，自行调整不同方向填充的具体层数 。以上面展示的卷积运算为例，如果我们希望输出大小与输入相同，还是 \(3 \times 3\)，就需要对输入的宽和高在两侧分别填充一层。如果我们在左方和上方进行全零填充，得到的结果如下图所示。

alt text

其中输入图像左边和上边灰色的部分是填充的0，得到了 \(4 \times 4\) 的矩阵，与 \(2 \times 2\) 的卷积核进行卷积后，输出的矩阵与原图像大小相同。我们用浅绿色标出了输出中有填充0参与运算的部分，其余部分和原本的输出相同。通过适当的填充操作，我们可以自由调整输出的大小。

Warning

这里讲的是最基础的padding, 后面会有复杂的, 见 (5)

(3) 感受野

卷积运算可以对一定范围内的图像进行特征提取，其==提取范围就是卷积核的大小 \(W_k\) 和 \(S_k\)。因此，卷积核的大小又称为 ==卷积核的感受野 (receptive field)

(4) 池化

除此之外，考虑到图像中通常会有大量相邻的相似像素，在这些区域上进行卷积得到的结果基本是相近的，从而包含大量冗余信息；另一方面，小卷积核对局部的信息可能过于敏感。

因此，在卷积之外，我们通常还会对图像进行 池化（pooling）操作

池化是一种 降采样（down-sampling） 操作，即用一个代表像素来替代一片区域内的所有像素，从而降低整体的复杂度。

常用的池化有平均池化和最大池化两种。顾名思义，平均池化（average pooling）是用区域内所有像素的平均值来代表区域，最大池化（max pooling）是用所有像素的最大值来代表区域。

alt text

上图展示了对 \(4 \times 4\) 的图像做最大池化的过程。

alt text

上图输出张量的高度为2，宽度为2。这四个元素为每个汇聚窗口中的最大值:

\(max(0,1,3,4) = 4\), \(max(1,2,4,5) = 5\), \(max(3,4,6,7) = 7\), \(max(4,5,7,8) = 8\)

池化与卷积操作类似，都可以看作将一个固定大小的窗口在图像上滑动。但是通常来说，池化运算的窗口在滑动时不会重复，因此得到的输出图像会比输入图像显著缩小。

(5) 填充与步幅

朴素型:

1) 条件:

  • 图像: \(W \times H\)
  • 卷积核: \(W_k \times H_k\)

2) 输出形状:

\[ W_{out} = W - W_k + 1 \]
\[ H_{out} = H - H_k + 1 \]

填充型:

1) 条件:

  • 图像: \(W \times H\)
  • 卷积核: \(W_k \times H_k\)
  • 填充: \(W_{pad}\) 和 \(H_{pad}\)

2) 输出形状:

\[ W_{out} = W - W_k + 1 + W_{pad} \]
\[ H_{out} = H - H_k + 1 + H_{pad} \]

填充+步幅型:

alt text

Note

事实上, "步幅" 和 "池化" 都是降采样的方式

1) 条件:

  • 图像: \(W \times H\)
  • 卷积核: \(W_k \times H_k\)
  • 填充: \(W_{pad}\) 和 \(H_{pad}\)
  • 步幅:
    • 水平: \(s_h\)
    • 竖直: \(s_w\)

2) 输出形状:

\[ [\frac{W - W_k + W_{pad} + s_w}{s_w}] \times [\frac{H - H_k + H_{pad} + s_h}{s_h}] \]

(6) 多输入与多输出通道

1) 多输入

确保 “卷积核的通道数” 等于 “输入的通道数”

  • 输入: \(C_i \times W \times H\)
  • 卷积核: \(C_i \times W_k \times H_k\)

输出:

  • C: \(C_i\)
  • W: \(W - W_k + 1\)
  • H: \(H - H_k + 1\)

遍历 \(C_i\) 个 \((W - W_k + 1)\) x \((H - H_k + 1)\) 的结果, 相加得到最终结果:

alt text

最终输出:

\((W - W_k + 1)\) x \((H - H_k + 1)\) x \(1\)

2) 多输出

到目前为止，不论有多少输入通道，我们还只有一个输出通道。然而，每一层有多个输出通道是至关重要的。在最流行的神经网络架构中，随着神经网络层数的加深，我们常会增加输出通道的维数。

如何设计卷积核的维度数值:

用 \(C_i\) 和 \(C_0\) 分别表示输入和输出通道的数目, \(W_k\) 和 \(H_k\) 表示普通卷积核的尺寸

回想一下上面提到的:

  • 输入: \(C_i \times W \times H\)
  • 卷积核: \(C_i \times W_k \times H_k\)
  • 最终输出: \(1 \times (W - W_k + 1) \times (H - H_k + 1)\)

相当于输出通道接收到 “一维” 的 “卷积处理结果”

但是我们实际上是想要 “\(C_0\)维” 的 “卷积处理结果”

因此需要的卷积核尺寸是 “\(C_0 \times C_i \times W_k \times H_k\)”

TL; DR

  • 输入: \(C_i \times W \times H\)
  • 卷积核: \(C_0 \times C_i \times W_k \times H_k\)
  • 最终输出: \(C_0 \times (W - W_k + 1) \times (H - H_k + 1)\)

1) LeNet

Warning

重点是每一层的输入与输出:

本质上，考察的就是: 卷积计算公式 + 池化计算公式

详见基础知识

alt text

2) AlexNet

Warning

重点是每一层的输入与输出:

本质上，考察的就是: 卷积计算公式 + 池化计算公式

详见基础知识

alt text

3) VGG

VGG设计思想

研究人员开始从单个神经元的角度思考问题，发展到整个层，现在又转向块，重复层的模式。

与AlexNet、LeNet一样，VGG网络可以分为两部分：第一部分主要由卷积层和汇聚层组成，第二部分由全连接层组成

VGG组成

原始VGG网络有5个卷积块，其中前两个块各有一个卷积层，后三个块各包含两个卷积层

Tip

由于该网络使用 8 个卷积层 (\(2 \times 1 + 3 \times 2\)) 和 3 个全连接层，因此它通常被称为 VGG-11

alt text

4) NiN

基于VGG的“block”思想

alt text

来点实例计算:

alt text

5) GoogleNet

这篇论文的一个重点是解决了什么样大小的卷积核最合适的问题。

毕竟，以前流行的网络使用小到 \(1 \times 1\)，大到 \(11 \times 11\) 的卷积核。本文的一个观点是，有时使用不同大小的卷积核组合是有利的。

alt text

6) ResNet

批处理标准化 (Batch Normalization)

批标准化（BN）就像是在神经网络的每一层都加了一个“数据预处理器”。

它在训练时，看一小批数据，把这批数据的特征“拉到”一个比较标准的范围内（均值接近0，方差接近1），然后再通过两个可学习的参数（γ 和 β）进行微调，让网络自己决定最佳的特征分布尺度和范围。这样做能让网络训练得更快、更稳定，也更容易训练深层网络。

残差卷积神经网络

残差网络的设计思路非常简单：一个深层的网络不应该表现的比浅层网络更差。

基于这个考量，作者在卷积层之间加上了短路链接。本质上，短路链接可以看作是一个恒等变换:

  • 如果在训练中，两个卷积层由于种种原因没能有效提取图片中的有效特征，因为有短路链接的存在，模型整体的效果也不会被影响很多
  • 如果两个卷积层提取到了有用的特征，那么后面的层就可以采用这两个卷积层的结果从而提高模型的表现

换句话说，如果我们的目标函数是 \(H(x)\) 而输入为 \(x\), 那么被短接的两个卷积层需要做的就是尽量弥合“输入”与“目标函数”之间的差距，也就是 \(H(x) - x\)

1) Building Block 残差块

alt text

2) ResNet-7 逐层维度分析

alt text

循环神经网络

1) RNN and BiRNN

RNN

alt text

alt text

RNN: 根据已有的知识，推断下一个word

BiRNN

BiRNN: 当前的输出(第t步的输出)不仅仅与前面的序列有关，并且还与后面的序列有关

alt text

alt text

2) LSTM

LSTM详解(zhihu)

  • 目的: 解决“长期依赖”问题
  • 避免: 梯度消失 / 梯度爆炸
  • 引入:
    • 遗忘门: 遗忘门决定哪些信息需要从细胞状态中抛弃
    • 输入门: 输入门的sigmoid层决定哪些值需要更新
    • 输出门: 决定细胞状态中哪些部分需要输出
    • 重要性排序: 遗忘门 > 输入门 > 输出门

3) 混合神经网络

赌一手不考，考就认栽...

4) Attention and Transformer

注意力机制

当我们用深度 CNN 模型识别图像时，一般是通过卷积核去提取图像的局部信息，然而， 每个局部信息对图像能否被正确识别的影响力是不同的 ，如何让模型知道图像中不同局部信息的重要性呢？

答案就是注意力机制 ‼️

详解注意力机制(zhihu)

上面的blog写的很好，尤其是“Attention 机制的本质”这一部分:

"Attention 机制听起来高大上，其关键就是学出一个权重分布，然后作用在特征上"

alt text

  • 第一个过程是根据Query和Key计算权重系数
    • 第一个过程又可以细分为两个阶段:
      • 第一个阶段根据Query和Key计算两者的相似性或者相关性
      • 第二个阶段对第一阶段的原始分值进行归一化处理
  • 第二个过程根据权重系数对Value进行加权求和

自注意力机制

  1. 自注意力机制是注意力机制的变体，其减少了对外部信息的依赖，更擅长捕捉数据或特征的内部相关性
  2. 自注意力机制在文本中的应用，主要是通过计算单词间的互相影响，来解决长距离依赖问题

self-attention是Transformer用来将其他相关单词的“理解”转换成我们正在处理的单词的一种思路，我们看个例子:

Text Only
1
The animal didn't cross the street because it was too tired.

这里的it到底代表的是animal还是street呢，对于我们来说能很简单的判断出来，但是对于机器来说，是很难判断的，self-attention就能够让机器把it和animal联系起来👍

详解自注意力机制(zhihu)

TL; DR: 本质是 “其他所有词” 之于 “当前词” 的 “打分机制”。分数高低可以体现“关联度” :))

alt text

核心就是这个公式:

\[ Self-Attention(Q,K,V) = softmax(\frac{Q \times K^T}{\sqrt{d_k}}) \times V \]

Transformers

重点就是自注意力机制 (self-attention)

详解 transformers(zhihu)

  • Transformer 与 RNN 不同，可以比较好地并行训练
    • RNN具有强烈的依赖关系, 不能并行处理 (CNN 可以)
  • Transformer 本身是不能利用单词的顺序信息的，因此需要在输入中添加位置 Embedding，否则 Transformer 就是一个词袋模型了
  • Transformer 的重点是 Self-Attention 结构，其中用到的 Q, K, V矩阵通过输出进行线性变换得到
  • Transformer 中 Multi-Head Attention 中有多个 Self-Attention，可以捕获单词之间多种维度上的相关系数 attention score

5) LLM

  • 多头注意力 (Multi-Head Attention)
  • 多指令预测 (Multi-Token Prediction)

第五章 聚类方法

定义: 将每个数据个体打上标签, 将全集分成若干个簇, 要求簇内元素相似, 而簇间元素不同

很显然, 聚类的本质是在打标签, 因此它是一种无监督学习

相似度:

  1. 按照距离定义: dist 越大, 相似度越小
  2. 按照密度定义: density 越大, 相似度越大
  3. 按照概念定义: 概念相近, 相似度越大

常用距离公式 (距离标准):

\[ dist(x,y) = (\sum_{k=1}^{m}{{|x_k-y_k|}^{q}})^{\frac{1}{q}} \]
  • q = 1: 曼哈顿距离 (绝对值距离)
  • q = 2: 欧几里得距离 (几何距离)
  • q > 2: 明克夫斯基距离

层次聚类方法

alt text

需要一个参数指明停止聚类的条件: 簇的期望个数k

特点: 聚类过程中一次性建好聚类树，没有回溯调整操作

  • 一个数据点一旦属于每个簇之后就一直属于该簇，不会更改
  • 一个簇一旦被合并或者分裂之后，也不会再调整其中的数据点

1) Linkage 算法

  1. 用距离定义相似度
  2. 合并或者分裂簇的时候，主要考虑簇间距离。一次只合并或分裂一个簇

簇间距离有三种度量方法:

  1. 单链 (Single Link): 两簇最近两个点间的距离
    1. 👍 易于处理簇大小不同的情况
    2. 😭 对噪音和异常点很敏感
  2. 全链 (Complete Link): 两簇最远两个点间的距离
    1. 👍 受噪音和异常点的影响小
    2. 😭 倾向于将大簇划分为多个簇
  3. 均链 (Average Link): 两簇点间距离的平均值 (簇间全连接, 算均值)
    1. 👍 受噪音和异常点的影响相对较小
    2. 😭 聚类结果倾向于球形

2) CURE 算法

  1. 寻找一些点作为各自簇的代表，然后取两个簇代表点中的最短距离作为簇间距离
  2. 理论上，簇的代表点基本上覆盖了簇的形状
    1. 代表点向簇中心收缩的用意在于中和外边界点的影响

3) CHAMELEON 算法

变色龙算法

  • 算法思路 alt text
  • 稀疏图
    • 节点表示数据项
    • 边权表示近似度: 距离越大, 近似度越小, 边权越小
Warning

这里边权(weight)表示近似度, 而不是点间距离

可以发现高质量的任意形状的簇!

划分聚类方法

设计:

  1. 每个簇都与一个簇心相关联
  2. 每个点被分配给距离最近的簇心
  3. 使用距离定义数据相似度

常见算法:

(1) K-Means:

  • 簇的代表点是簇的理论中心
  • 理论中心点不一定是簇内真实存在的数据点 (用加权公式计算出来的)

(2) k-Medoids:

  • 簇的代表点是簇内最靠近理论中心的数据点
Tips
  1. 在划分聚类过程中，簇心在不断地调整。调整的目的是使数据集上的划分到达 全局优化
  2. 全局优化: 误差最小 (总的距离之和min)
Note
  • k-mediods 每次选取的质心，必须是样本点
  • k-means 每次选取的质心可以是样本点之外的点
  • 就好比中位数和平均值的区别

1) K-Means

  1. 从数据集中随机选择K个数据点作为初始簇代表点
  2. 将数据集中每一个数据点按照距离分配给与其最近的簇
  3. 根据 质心公式 重新计算每个簇的中心, 获得新的代表点
  4. 如果所有簇的新代表点均无变化，则算法结束; 否则转至 step 2

簇的理论中心计算公式 (质心公式):

\[ r = \frac{\sum_{x \in C_i}{x}}{|C_i|} \]

alt text

特点分析:

  1. K-Means 算法经常会结束于局部最优解
  2. K值怎么选? 是一门玄学, 对结果影响很大
  3. 初始质心怎么选? 是一门玄学, 对结果影响很大
  4. 对异常值敏感
  5. 扫描顺序也会对结果有影响

2) K-Medoids

  1. 初始化阶段

    • 随机选择k个数据点作为初始medoids，例如在二维数据集中选取(4,6)和(9,3)作为初始中心点

  2. 数据分配阶段 将所有非中心点分配到最近的medoid所在簇。计算采用曼哈顿距离（L1距离）或欧氏距离，例如点(8,4)到medoids的距离分别为：

    • 到(4,6)：|8-4| + |4-6| = 6
    • 到(9,3)：|8-9| + |4-3| = 2

    因此该点归属第二个簇

  3. 中心点优化阶段 遍历 每个簇内非medoid点，假设计算将其设为新medoid后的总成本（所有点到medoid的距离和）。若新成本更低，则替换medoid。

    例如原medoid(9,3)所在簇总成本为： - (8,4)→2, (8,5)→3, (9,6)→3, (10,4)→2 → 总成本10

    若替换为(9,6)，新成本变为： - (8,4)→5, (8,5)→4, (9,3)→3, (10,4)→5 → 总成本17

    因此维持原medoid。

  4. 终止条件 重复步骤2-3直到medoid不再变化或达到最大迭代次数

特点分析:

  1. K-Means 算法经常会结束于局部最优解
  2. K值怎么选? 是一门玄学, 对结果影响很大
  3. 初始质心怎么选? 是一门玄学, 对结果影响很大
  4. 扫描顺序也会对结果有影响
  5. 计算效率较低

TL; DR

K-Means K-Medoids
K值影响 大 大
初始质心选择 大 大
扫描顺序 大 大
异常值影响 大 小
计算效率 高 低

基于密度的聚类方法

基于密度的聚类方法的核心思想是：簇是 数据空间中密度较高的点 的 最大连通区域。换句话说，聚类是由紧密相连的高密度区域组成，而这些区域之间由低密度区域分隔开。

与传统的基于距离或中心点的聚类方法（如K-means）不同，基于密度的聚类方法不需要预先指定簇的数量，且能够发现任意形状和大小的簇，且天然具有抗噪声能力。

1) DBSCAN 算法

(1) 密度定义

DBSCAN 通过两个关键参数定义密度：

  • ε (epsilon)：邻域半径，定义某个点周围的邻居范围
  • MinPts：邻域内的最小点数阈值，用于判断该点是否为“核心点”

根据这两个参数，DBSCAN 将数据点划分为三类：

  • 核心点(Core Point)：在ε邻域内至少有MinPts个点（包括自己）
  • 边界点(Border Point)：不是核心点，但在某个核心点的ε邻域内
  • 噪声点(Noise Point)：既不是核心点，也不在任何核心点的ε邻域内

alt text

(2) 密度关系定义

  • 密度直达（Directly density-reachable）：点q在核心点p的ε邻域内，则q从p密度直达。该关系是单向的 alt text
  • 密度可达（Density-reachable）：存在核心点序列p1, p2, ..., pn，使得p1=p且pn=q，且每个点都密度直达下一个点。即通过一系列密度直达连接，q从p密度可达 alt text
  • 密度相连（Density-connected）：存在某点o，使得p和q均从o密度可达。密度相连是对称关系 alt text

(3)算法流程

举个例子: 取 Eps=3，MinPts=3

alt text

第一步，顺序扫描数据集的样本点，首先取到 p1(1,2)。

1）计算 p1 的邻域，计算出每一点到 p1 的距离，如 d(p1,p2)=sqrt(1+1)=1.414。

2）根据每个样本点到 p1 的距离，计算出 p1 的 Eps 邻域为 {p1,p2,p3,p13}。

3）因为 p1 的 Eps 邻域含有 4 个点，大于 MinPts(3)，所以，p1 为核心点。

4）以 p1 为核心点建立簇 C1，即找出所有从 p1 密度可达的点。

5）p1 邻域内的点都是 p1 直接密度可达 的点，所以都属于C1。

6）寻找 p1 密度可达 的点，p2 的邻域为 {p1,p2,p3,p4,p13}，因为 p1 密度可达 p2，p2 密度可达 p4，所以 p1 密度可达 p4，因此 p4 也属于 C1。

7）p3 的邻域为 {p1,p2,p3,p4,p13}，p13的邻域为 {p1,p2,p3,p4,p13}，p3 和 p13 都是核心点，但是它们邻域的点都已经在 C1 中。

8）P4 的邻域为 {p3,p4,p13}，为核心点，其邻域内的所有点都已经被处理。

9）此时，以 p1 为核心点出发的那些密度可达的对象都全部处理完毕，得到簇C1，包含点 {p1,p2,p3,p13,p4}。

这一步得到的结论
  1. Cluster C1: {p1, p2, p3, p4, p13}
  2. P1: 核心点
  3. P2: 核心点
  4. P3: 核心点
  5. P4: 核心点
  6. P13: 核心点

第二步，继续顺序扫描数据集的样本点，取到p5(5,8)。

1）计算 p5 的邻域，计算出每一点到 p5 的距离，如 d(p1,p8)-sqrt(4+1)=2.236。

2）根据每个样本点到 p5 的距离，计算出p5的Eps邻域为{p5,p6,p7,p8}。

3）因为 p5 的 Eps 邻域含有 4 个点，大于 MinPts(3)，所以，p5 为核心点。

4）以 p5 为核心点建立簇 C2，即找出所有从 p5 密度可达的点，可以获得簇 C2，包含点 {p5,p6,p7,p8}。

这一步得到的结论
  1. Cluster C2: {p5, p6, p7, p8}
  2. P5: 核心点
  3. P6: 核心点
  4. P7: 核心点
  5. P8: 核心点

第三步，继续顺序扫描数据集的样本点，取到 p9(9,5)。

1）计算出 p9 的 Eps 邻域为 {p9}，个数小于 MinPts(3)，所以 p9 不是核心点。

2）对 p9 处理结束。

这一步得到的结论
  1. 没有新 Cluster 产生
  2. P9: 不是核心点 (究竟是 “边界点” or “噪声点” 还需进一步判断)

第四步，继续顺序扫描数据集的样本点，取到 p10(1,12)。

1）计算出 p10 的 Eps 邻域为 {p10,p11}，个数小于 MinPts(3), 所以 p10 不是核心点。

2）对 p10 处理结束。

这一步得到的结论
  1. 没有新 Cluster 产生
  2. P10: 不是核心点 (究竟是 “边界点” or “噪声点” 还需进一步判断)

第五步，继续顺序扫描数据集的样本点，取到 p11(3,12)。

1）计算出 p11 的 Eps 邻域为 {p11,p10,p12}，个数等于 MinPts(3)，所以 p11 是核心点。

2）从 p12 的邻域为 {p12,p11}，不是核心点。

3）以 p11 为核心点建立簇 C3，包含点 {p11,p10,p12}。

这一步得到的结论
  1. Cluster C3: {p11, p12, p10}
  2. P12: 是“边界点”（因为领域内点数不够，但是可以由核心点P11达）
  3. P10: 是“边界点”（因为领域内点数不够，但是可以由核心点P11达）

第六步，继续扫描数据的样本点，p12、p13 都已经被处理过，算法结束。

2) OPTICS 算法

...

3) DENCLUE 算法

...

基于子空间的聚类方法

主要用于处理高维、海量数据，设计思想:

对于数据的高维特征，对其各个特征的重要性进行加权，或者挑选出最重要的特征子集，减少或消除冗余特征以及不相关特征的影响，最大限度的保留和利用原始数据中的关键特征。

算法分类:

  1. 硬子空间聚类方法
    1. 自顶向下子空间聚类
    2. 自底向上子空间聚类
  2. 软子空间聚类方法
    1. 对每个数据簇的各个特征赋予相应的特征加权系数

1) 自底向上子空间聚类算法

一般基于网格密度

  1. 先将原始特征空间分成若干个网格
  2. 再以落到某网格中样本点的概率表示该子空间的密度情况
  3. 对于密度超过一定阈值的子空间作为密集单元进行保留，同时舍弃非密集的子空间

CLIQUE算法

alt text

2) 自顶向下子空间聚类算法

主要基于数据投影技术以及迭代搜索策略

  1. 首先将整个样本集划分为C个数据簇
  2. 对于每个数据簇赋予相同的权值，并为每一类的各个特征赋予不同权重
  3. 利用迭代策略对初始划分不断更新，产生新的权重和聚类划分

PROCLUS算法

...

人工神经网络聚类方法

自组织特征映射神经网络聚类算法（SOM）

原理

alt text

竞争网络

alt text

alt text

特点

alt text

第六章 智能优化方法

Abstract:

  • 待解决的问题: 对某个目标函数的全局优化
  • 进化计算: 模拟生物进化基础上的随机搜索优化

Trait:

  • 隐含的并行性
  • 不用具体解析，只需要对求解目标有个大致的合理表示即可

进化计算的一般步骤:

  1. 编码策略: 用字符串表示个体
  2. 适应函数: 评价每个字符串的“优劣程度” (aka. “适应程度”)
  3. 变异算子: 随机改变某个字符串的某几位
    1. 模拟的是自然过程中的“基因突变”
  4. 交叉算子: 两个编码串进行混合得到新的编码串
    1. 模拟的是自然过程中的“交配过程”
  5. 选择算子: 从一群编码串中选择较优的那些
    1. 模拟的是自然群体中的“自然选择”

遗传算法

Genetic Algorithm (GA)

算法原理

  1. 初始化种群
  2. 计算适应度
  3. 选择操作（“选择初代中适应度较高的个体”）
  4. 交叉操作（“优秀者享有交配权”）
  5. 变异操作（“基因突变”）
  6. wait and see ("终止条件")
    1. if 最优个体的适应度达到阈值/最优个体适应度不再上升/种群平均适应度不再上升 -> 收敛, 算法结束
    2. else -> 回到 2 进行循环操作

算法过程

alt text

alt text

alt text

alt text

alt text

算法特点

  1. 群体搜索，而不是从单个解开始
  2. 只需适应值和串编码等通用信息，普适性强
  3. 容错能力强，因为每一代都有筛选，属于一种“滤波”
  4. 具有隐含的并行性

蚁群算法

Ant Colony Optimization (Ants)

算法原理

(1) 信息素:

  • 蚂蚁碰到一个还未走过路口时就随机选择一条路径前行, 并释放出信息素
  • 信息素浓度会随着时间衰减

(2) 正反馈机制:

  • 越短的路上积累的信息素越多 ，越长的路上积累的信息素越少
  • 当后来的蚂蚁再次碰到这个路口时，选择信息素较多的路径的概率相对较大
  • 这样便形成了一个正反馈机制 (最优路径上的信息素越来越多, 整个蚁群可以寻找到最优路径)

算法细节

Danger

大概率不会考察

alt text

alt text

算法特点

(1) 优点

  • 自组织: 基于正反馈机制, 从无序到有序, 最终趋近最优解
  • 并行性
  • 正反馈性
  • 鲁棒性: 基于正反馈, 不需要人工参数干预

(2) 缺点

  • 时间周期较长
  • 容易收敛到局部最优解: 搜索进行到一定程度后，所有蚂蚁发现的解完全一致。此时不能进一步搜索解空间，不利于发现全局最优解

粒子群算法

Particle Swarm Optimization (PSO)

算法原理

粒子群算法（PSO）可以想象成一群鸟在森林里协作寻找最大粮仓的场景。每只鸟既依赖自己的经验，也参考同伴的信息，最终整个群体逐渐向最优位置聚集。下面通过一个生活化的例子解析其原理：

🌰 核心比喻：足球赛找球门

假设你在足球场蒙眼找球门，规则如下：

  1. 初始状态：你和队友随机分散在球场，各自记录自己走过的最接近球门的位置（个体最优）
  2. 信息共享：每隔1分钟，所有人通过微信群汇报自己找到的最佳位置，群主汇总出全局最优位置
  3. 调整方向：你下一步的移动方向由三部分组成：
    • 惯性：保持当前速度（避免急转弯）
    • 个体经验：朝自己历史最佳位置移动
    • 群体经验：朝群主公布的全局最佳位置移动
  4. 终止条件：当所有人聚集在球门附近时停止搜索

🔧 算法关键机制

(1) 速度更新公式（决策逻辑）

假设你当前速度为 \(v\)，则下一步速度：

\[ v_{\text{新}} = w \cdot v + c_1 r_1 (\text{个人最佳位置} - \text{当前位置}) + c_2 r_2 (\text{群体最佳位置} - \text{当前位置}) \]
  • 惯性权重 \(w\)：若 \(w=0.8\)，表示你更信任当前速度（适合大范围探索）
  • 加速常数 \(c_1, c_2\)：通常设为2，平衡个体与群体经验
  • 随机数 \(r_1, r_2\)：模拟现实中的不确定因素（如风向干扰）

(2) 位置更新（移动步骤）

新位置 = 当前位置 + 新速度，但需限制在球场边界内（避免飞出解空间）

算法特点

  1. 基于群体叠代的随机搜索算法:
    • 跟遗传很像，但是没有交叉变异
    • 粒子跟随最优解粒子跑

自适应协方差矩阵进化策略

自适应协方差矩阵进化策略（CMA-ES）可以想象成一支智能探险队，在未知地形中协作寻找宝藏。他们通过动态调整搜索方向和步长，逐渐锁定最优区域。以下通过比喻和实例解析其核心原理：

🌄 核心比喻：沙漠寻宝

假设你要在沙漠中寻找隐藏的绿洲，规则如下：

  1. 初始策略：派10架无人机随机扫描沙漠，每架记录自己发现的最湿润坐标
  2. 经验积累：将表现最好的5架无人机轨迹连线，分析它们的移动规律 （如：多数向东北方向移动时发现湿度更高）
  3. 调整搜索：
    • 方向优化： 下次搜索时，让无人机更多向东北方向飞行（更新协方差矩阵，强化优势方向）
    • 步长控制：若连续多次向东北都找到更湿区域，则增大飞行距离；若结果波动大，则缩小步长
  4. 终止条件：当所有无人机聚集在绿洲中心时停止

🔧 关键机制解析

(1) 协方差矩阵：智能地图

协方差矩阵就像一张动态概率地图，记录哪些方向更容易找到好解。例如：

  • 若东北方向连续找到更优解，矩阵会将该方向概率密度提高（特征值增大）
  • 若东西方向探索结果波动大，则减少该方向搜索权重（特征值减小）

协方差矩阵C直接描述群体突变分布的形状

(2) 进化路径：历史轨迹

  • 各向异性路径：记录连续多步的整体移动趋势（类似粒子群算法的群体经验）
  • 各向同性路径：检测步长是否合适。若路径过长（连续同向移动），则增大步长；若路径过短（频繁转向），则缩小步长

(3) 自适应公式（简化版）

  • 协方差更新：
    $$ C_{新} = (1-\alpha)C_{旧} + \alpha (\text{优秀轨迹均值} \times \text{优秀轨迹均值}^T) $$ 其中α控制历史经验的遗忘速度
  • 步长调整：
    $$ \sigma_{新} = \sigma_{旧} \times e^{\beta (\text{路径长度} - \text{理想长度})} $$
    β为学习率，动态平衡探索与开发