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

第一章 概述

机器学习的基本问题

Danger

这个考过

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

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

机器学习的基本方式

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

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

机器学习的基本过程

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

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

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

(1) 清洗数据

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

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

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

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

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

第二章 数据与度量

数据预处理

(1) 归一化处理

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

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

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

相似性与相异性度量

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)

(3) 距离度量

\[ dist = (\sum_{k=1}^{n}{(|p_k - q_k|)^r})^{\frac{1}{r}} \]

• \(r=1\): 曼哈顿距离（绝对值距离）
• \(r=2\): 欧几里得距离（\(L_2\)范数）
• \(r=\inf\): 无穷范数（数据对象中绝对值最大的数）

相似性度量

(1) 余弦相似度

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

(2) 距离倒数

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

(3) 杰卡德系数

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

(4) Dice系数

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

(5) 皮尔逊相关系数

• 线性正相关: 相似度为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)，即: 完全相关

评价机器学习结果

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

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

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

4) AUC 曲线

Danger

这个考过

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

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) 混淆矩阵

• 每一行：代表真实的类别（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

这个考过

决策树

随机森林

朴素贝叶斯

支持向量机

逻辑回归

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

感知器

反向传播算法

这个考过

卷积神经网络

1) LeNet

2) AlexNet

3) GoogleNet

4) VGG

5) ResNet

循环神经网络

1) RNN and BiRNN

2) LSTM

3) 混合神经网络

4) Attention and Transformer

5) LLM

第五章 聚类方法

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

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

相似度:

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: 明克夫斯基距离

层次聚类方法

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

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

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

Linkage 算法

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

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

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

CURE 算法

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

CHAMELEON 算法

变色龙算法

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

Warning

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

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

划分聚类方法

设计:

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

常见算法:

(1) K-Means:

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

(2) k-Medoids:

• 簇的代表点是簇内最靠近理论中心的数据点

Tips

1. 在划分聚类过程中，簇心在不断地调整。调整的目的是使数据集上的划分到达 全局优化
2. 全局优化: 误差最小 (总的距离之和min)

Note

• k-mediods 每次选取的质心，必须是样本点
• k-means 每次选取的质心可以是样本点之外的点
• 就好比中位数和平均值的区别

K-Means

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

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

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

特点分析:

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

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）不同，基于密度的聚类方法不需要预先指定簇的数量，且能够发现任意形状和大小的簇，且天然具有抗噪声能力。

DBSCAN 算法

(1) 密度定义

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

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

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

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

(2) 密度关系定义

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

(3)算法流程

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

第一步，顺序扫描数据集的样本点，首先取到 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 都已经被处理过，算法结束。

OPTICS 算法

...

DENCLUE 算法

...

基于子空间的聚类方法

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

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

算法分类:

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

自底向上子空间聚类算法

一般基于网格密度

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

CLIQUE算法

自顶向下子空间聚类算法

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

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

PROCLUS算法

...

人工神经网络聚类方法

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

原理

竞争网络

特点

第六章 智能优化方法