04 无监督学习

01 K-means

若干定义:
- n 个 m-维数据 ${x_{1}, x_{2}, . . ., x_{n}}$ ， $x_{i} \in R^{m}$ (1≤i≤n)
- 两个 m 维数据之间的欧氏距离为 $d (x_{i}, x_{j}) = \sqrt{(x_{i 1} - x_{j 1})^{2} + (x_{i 2} - x_{j 2})^{2} + . . . + (x_{i m} - x_{j m})^{2}}$ $d (x_{i}, x_{j})$ 值越小，表示 $x_{i}$ 和 $x_{j}$ 越相似；反之越不相似
聚类集合数目 k
问题: 如何将 n 个数据依据其相似度大小将它们分别聚类到 k 个集合，使得每个数据仅属于一个聚类集合。

算法流程

初始化聚类质心
- 初始化 $k$ 个聚类质心 $c = {c_{1}, c_{2}, . . ., c_{k}}, c_{j} \in R^{m} (1 \leq j \leq k)$
- 每个聚类质心 $c_{j}$ 所在集合记为 $G_{j}$
将每个待聚类的数据放入唯一一个聚类集合中
- 计算待聚类数据 $χ_{i}$ 和质心 $c_{j}$ 之间的欧氏距离 $d (x_{i}, c_{j}) (1 \leq i \leq n, 1 \leq j \leq k)$
- 将每个 $x_{i}$ 放入与之距离最近聚类质心所在聚类集合中，即 $\underset{c \in C}{argmin} d (x_{i}, c_{j})$
更新聚类质心
- 根据每个聚类集合中所包含的数据，更新该聚类集合质心值，即： $c_{j} = \frac{1}{| G_{j} |} \sum_{x_{i} \in G_{j}} x_{i}$
算法迭代，直至满足条件
- 迭代次数上限
- 质心基本不变

欧式距离，也可以换成方差

最小化簇内距离，最大化簇间距离

不足：

欧氏距离假设数据每个维度之间的重要性是一样的
需要初始化聚类质心，初始化聚类中心对聚类结果有较大的影响
需要事先确定聚类数目，很多时候我们并不知道数据应被聚类的数目

K-medoids Algorithm

Chooses input data points as centers;
选择输入的数据点作为聚类中心

Works with an arbitrary matrix of distances between data points instead of Euclidean distance
可以用别的距离度量公式

02 主成分分析

主成分分析是一种特征降维方法

奥卡姆剃刀定律（Occam’s Razor）：“如无必要，勿增实体”，即“简单有效原理”，对于现象最简单的解释往往比较复杂的解释更正确

概念解析

方差
- 对象：n 个数据 $X = {x_{i}}$
- 方差等于各个数据与样本均值之差的平方和之平均数
- 方差描述了样本数据的波动程度 $Var (X) = \frac{1}{n} \sum_{i = 1}^{n} (x_{i} - μ)^{2}$
协方差
- 对象：n 个 2 维变量数据 $(X, Y) = {(x_{i}, y_{i})}$
- 衡量两个变量之间的相关度 $cov (X, Y) = \frac{1}{n} \sum_{i = 1}^{n} (x_{i} - E (X)) (y_{i} - E (Y))$
Pearson Correlation coefficient
- 将两组变量的关联度规整到一定的范围内 $corr (X, Y) = \frac{C o v (X, Y)}{\sqrt{V a r (X) V a r (Y)}} = \frac{C o v (X, Y)}{σ_{x} σ_{y}}$
- 性质：
  - $| c o r r (X, Y) | \leq 1$
  - $| c o r r (X, Y) | = 1$ 的充要条件是存在常数 $a$ 和 $b$ , 使得 $Y = a X + b$
  - 皮尔逊相关系数是对称的，即 corr $(X, Y) = c o r r (Y, X)$
- 作用：刻画两个变量之间的线性相关度
  - 如果 $| c o r r (X, Y) |$ 的取值越大，则两者在线性相关的意义下相关程度越大。
  - $| c o r r (X, Y) | = 0$ 表示两者不存在线性相关关系 (可能存在其他非线性相关的关系)。
相关性 correlation 与独立性 independence
- 如果 X 和 Y 的线性不相关，则 $| c o r r (X, Y) | = 0$
- 如果 $X$ 和 $Y$ 的彼此独立，则一定 $| c o r r (X, Y) | = 0$ , 且 $X$ 和 Y 不存在任何线性或非线性关系
- “不相关” 比 “独立” 弱

算法动机

主成分分析：特征降维的方法，但要保证降维后的结果要保持原始数据固有结构

需要尽可能将数据向方差最大方向进行投影，使得数据所蕴含信息没有丢失，彰显个性
将𝒅维特征数据映射到𝒍维空间（𝒅≫𝒍），去除原始数据之间的冗余性（通过去除相关性手段达到这一目的）
将原始数据向这些数据方差最大的方向进行投影。一旦发现了方差最大的投影方向，则继续寻找保持方差第二的方向且进行投影（保证方向的正交性）

	线性判别分析	主成分分析
是否需要样本标签	监督学习	无监督学习
降维方法	优化寻找特征向量 $w$	优化寻找特征向量 $w$
目标	类内方差小、类间距离大	寻找投影后数据之间方差最大的投影方向
维度	LDA 降维后所得到维度是与数据样本的类别个数 $K$ 有关 ( $S_{b}$ 的秩最多为 K-1)	PCA 对高维数据降维后的维数是与原始数据特征维度相关

算法描述

Conclusion：每一个

𝐰_{𝒊}

都是

𝒏

个

𝒅

维样本数据

𝐗

的协方差矩阵

𝜮

的一个特征向量，

𝝀_{i}

是这个特征向量所对应的特征值

假定每一维度的特征均值均为零（已经标准化）

Y_{n \times l, 降 维 结 果} = X_{n \times d, 原 始 数 据} W_{d \times l, 映 射 矩 阵}

降维后 n 个 l 维样本数据 Y 的方差为:

var (Y) = \frac{1}{n - 1} trace (Y^{T} Y)

= \frac{1}{n - 1} trace (W^{T} X^{T} X W)

= trace (W^{T} \frac{1}{n - 1} X^{T} X W)

降维前 n 个 d 维样本数据 X 的协方差矩阵记为:

Σ = \frac{1}{n - 1} X^{T} X

主成份分析的求解目标函数为

max_{W} trace (W^{T} Σ W)

满足约束条件

W^{T} W = I

保证降维后结果正交以去除相关性（即冗余度）

Pasted image 20250415122140.png|425

在主成份分析中，最优化的方差等于原始样本数据 𝐗 的协方差矩阵 𝜮 的特征根之和
要使方差最大，我们可以求得协方差矩阵 𝜮 的特征向量和特征根，然后取前 𝒍 个最大特征根所对应的特征向量组成映射矩阵 𝐖 即可

Pseudo-Code

输入：n 个 d 维样本数据所构成的矩阵 X，降维后的维数为 l
输出：映射矩阵 $W = {w_{1}, w_{2}, . . ., w_{l}}$

对于每个样本数据 $x_{i}$ 进行中心化处理： $x_{i} = x_{i} - μ, μ = \frac{1}{n} \sum_{j = 1}^{n} x_{j}$
计算原始样本数据的协方差矩阵： $Σ = \frac{1}{n - 1} X^{T} X$
对协方差矩阵 $Σ$ 进行特征值分解，对所得特征根按其值大到小排序 $λ_{1} \geq λ_{2} \geq \dots \geq λ_{d}$
取前 $ι$ 个最大特征根所对应特征向量 $w_{1}, w_{2}, . . ., w_{l}$ 组成映射矩阵 W
将每个样本数据 $x_{i}$ 按照如下方法降维： $(x_{i})_{1 \times d} (W)_{d \times l} = 1 \times l$

其他降维方法

非负矩阵分解（non-negative matrix factorization, NMF）
- 将非负的大矩阵分解成两个非负的小矩阵
多维尺度法（Metric multidimensional scaling, MDS）
局部线性嵌入（Locally Linear Embedding，LLE）

非负矩阵分解 PCA

非负矩阵分解将给定的非负矩阵 $D \in R^{n \times d}$ 分解为两个非负矩阵 $W \in R^{n \times l}$ 和 $H \in R^{l \times d}$ , 并满足下面的条件：

D \approx W H D_{i, j}, W_{i, μ}, H_{μ, j} \geq 0

其中， $0 \leq i < n - 1, 0 \leq j < d - 1$ , $0 \leq μ < l - 1$ 。
代价函数：度量原始矩阵 𝐷 与其近似矩阵 𝑊𝐻 之间的误差
- 欧氏距离函数
- KL 散度函数

多维尺度法 MDS

保持原始数据之间两两距离不变：MDS 算法会计算原始数据两两之间的距离，形成一个距离矩阵，以此来保证降维之前距离近的数据在降维之后也能很接近

无法对新数据集合进行降维（比如测试集），因为需要先验的距离矩阵知识

算法逻辑

令 N 是原始数据数量, 每个数据由 d 维特征表示, 即 $x_{i} = (x_{i 1}, x_{i 2}, . . ., x_{i d})$

可以将所有原始数据表示为 $X$ , $X = [x_{1}, . . ., x_{i}, . . ., x_{n}]$

多维尺度法首先计算任意两个数据 $x_{i}$ 和 $x_{j} (1 \leq i, j \leq n)$ 之间的距离 $s_{i j}$ , 得到距离矩阵 $A$ , 即 $A = (s_{i j})$

A 是一个 $n \times n$ 大小的矩阵, $x_{i}$ 和 $x_{j}$ 之间的距离度量函数由具体应用来定 (如可选取余弦距离等)

接着计算中心化矩阵 $H = I - \frac{1}{n} 1_{n} 1_{n}^{T}$ , 其中 $I$ 是单位矩阵， $1_{n}$ 是全 1 的 n 维列向量，可以得到如下 $n \times n$ 大小的矩阵 $B :$

B = - \frac{1}{2} H A H

假设矩阵 B 的秩为 p，对矩阵 B 进行奇异值分解，可得：

B = Γ Λ Γ^{T}

$Λ = d i a g (λ_{1}, . . ., λ_{l})$ 是一个对角矩阵，对角线上的元素为矩阵 B 的非零特征根
$Γ = (γ_{1}, . . ., γ_{l})$ 是一个 n×l 矩阵，其中 $γ_{j}$ 为特征根 $λ_{j} (1 \leq j \leq l)$ 所对应的特征向量

于是 $X = [x_{1}, . . ., x_{i}, . . ., x_{n}]$ 中 d 维原始数据可通过如下变换转变为 l 维数据，从而实现降维：

{\bar{X}}^{T} = [{\bar{x}}_{1}, {\bar{x}}_{2}, . . ., {\bar{x}}_{n}]^{T} = Γ Λ^{1 / 2}

其中 ${\bar{x}}_{i} (1 \leq i \leq n)$ 表示原始数据 x_i 降维后的结果

局部线性嵌入 LLE

PCA 和 MDS 都属于线性降维方法，LLE 是一种非线性降维方法

假设数据是局部线性的 (即使数据的原始高维空间是非线性流形嵌入)，这时可以用和邻居数据的线性关系进行局部重构

保持邻域内的线性关系，并使得该线性关系在降维后的空间中继续保持

03 特征人脸方法

用（特征）人脸表示人脸，而非用像素点表示人脸

将每幅人脸图像转换成列向量

如将一幅 32 × 32 的人脸图像转成 1024 × 1 的列向量

输入： $n$ 个 1024 维人脸样本数据所构成的矩阵 X，降维后的维数 $l$
输出：映射矩阵 W $= {w_{1}, w_{2}, . . ., w_{l}} ($ 其中每个 $w_{j} (1 \leq$ j $\leq l)$ 是一个特征人脸)
算法步骤：

对于每个人脸样本数据 $x_{i}$ 进行中心化处理： $x_{i} = x_{i} - μ, μ = \frac{1}{n} \sum_{j = 1}^{n} x_{j}$
计算原始人脸样本数据的协方差矩阵： $Σ = \frac{1}{n - 1} X^{T} X$
用 $L = X X^{T}$ 代替大的协方差矩阵计算，避免 d 维度过高计算复杂
对协方差矩阵 $Σ$ 进行特征值分解，对所得特征根从到小排序 $λ_{1} \geq λ_{2} \geq \cdot \cdot \cdot \geq λ_{d}$
取前 $l$ 个最大特征根所对应特征向量 $w_{1}, w_{2}, . . ., w_{l}$ 组成映射矩阵 W
将每个人脸图像 $x_{i}$ 按照如下方法降维： $(x_{i})_{1} \times d (W)_{d \times l} = 1 \times l$

04 潜在语义分析

这一部分考试不作要求

潜在语义分析先构建一个单词-文档 (term-document) 矩阵 A，进而寻找该矩阵的低秩逼近 (low rank approximation)，来挖掘单词-单词、单词-文档以及文档-文档之间的关联关系

第一步，计算单词-文档矩阵：

第二步，奇异值分解：

第三步，重建矩阵：

当 k=2, 即选取最大的前两个特征根及其对应的特征向量对矩阵 A 进行重建。下面给出了选取矩阵 U、矩阵 D 和矩阵 V 的子部分重建所得矩阵 $A_{2} :$

第四步，挖掘语义关系：

基于单词-文档矩阵 A，可以计算任意两个文档之间的皮尔逊相关系数，从而得到如下文档-文档相关系数矩阵：
基于重建单词-文档矩阵 A 2，可以计算任意两个文档之间的皮尔逊相关系数，从而得到如下文档-文档相关系数矩阵：

Conclusion:

基于重建单词-文档矩阵 𝐴2 得到的相关系数矩阵中文档-文档之间的相关关系更加明确
在同一文档中出现过的单词之间相关系数趋近为 1，没有同时出现在同一文档中的单词之间相关系数趋近为-1

05 期望最大化算法

这一部分考试不作要求

无论是最大似然估计算法或者是最大后验估计算法，都是充分利用已有数据，在参数模型确定 (只是参数值未知) 情况下，对所优化目标中的参数求导，令导数为 0，求取模型的参数值

在解决一些具体问题时，难以事先就将模型确定下来

期望最大化（expectationmaximization, EM）

解决含有隐变量 (latent variable) 问题的参数估计方法
算法分为两个步骤：
- 求取期望（E 步骤，expectation）
  先假设模型参数的初始值，估计隐变量取值
- 期望最大化（M 步骤， maximization）
  基于观测数据、模型参数和隐变量取值一起来最大化“拟合”数据，更新模型参数
- 然后，基于所更新的模型参数，得到新的隐变量取值 (E 步骤)，然后更新参数 (M 步骤), 直至算法收敛

二硬币投掷

假设有 A 和 B 两个硬币，进行五轮掷币实验

每一轮实验中，先随机选择一个硬币，然后用所选择的硬币投掷十次，将投掷结果作为本轮实验观测结果
H 代表硬币正面朝上、T 代表硬币反面朝上

实验结果如下：

问题：从这五轮观测数据出发，计算硬币 A 或硬币 B 被投掷为正面的概率; 记硬币 A 或硬币 B 被投掷为正面的概率为 $θ = {θ_{A}, θ_{B}}$

问题分析
隐变量	每一轮选择硬币 A 还是选择硬币 B 来完成 10 次投掷 (选择硬币 A 或硬币 B 投掷的概率)
模型参数	硬币 A 和硬币 B 投掷结果为正面的概率