机器学习——无监督学习¶

K 均值聚类¶

若干定义¶

$n$ 个 $m$ 维数据 $\{x_1, x_2, \dots, x_n\}$，其中 $x_i \in \mathbb{R}^m \ (1 \leq i \leq n)$。
两个 $m$ 维数据之间的欧氏距离为：

\[ d(x_i, x_j) = \sqrt{(x_{i1} - x_{j1})^2 + (x_{i2} - x_{j2})^2 + \cdots + (x_{im} - x_{jm})^2} \]

$d(x_i, x_j)$ 值越小，表示 $x_i$ 和 $x_j$ 越相似；反之越不相似。
聚类集合数目 $k$。
问题：如何将 $n$ 个数据依据其相似度大小将它们分别聚类到 $k$ 个集合，使得每个数据仅属于一个聚类集合。

算法步骤¶

第一步：初始化聚类质心：

初始化 $k$ 个聚类质心 $c = \{c_1, c_2, \dots, c_k\}$，其中 $c_j \in \mathbb{R}^m \ (1 \leq j \leq k)$。
每个聚类质心 $c_j$ 所在集合记为 $G_j$。

第二步：将每个待聚类数据放入唯一一个聚类集合中：

计算待聚类数据 $x_i$ 和质心 $c_j$ 之间的欧氏距离 $d(x_i, c_j)$，其中 $1 \leq i \leq n, 1 \leq j \leq k$。
将每个 $x_i$ 放入与之距离最近的聚类质心所在的聚类集合中，即：

\[ \text{argmin}_{c_j \in c} d(x_i, c_j) \]

第三步：根据聚类结果，更新聚类质心：

根据每个聚类集合中所包含的数据，更新该聚类集合质心值，即：

\[ c_j = \frac{1}{|G_j|} \sum_{x_i \in G_j} x_i \]

第四步：算法循环迭代，直到满足条件：

在新聚类质心基础上，根据欧氏距离大小，将每个待聚类数据放入唯一一个聚类集合中。
根据新的聚类结果，更新聚类质心。

聚类迭代满足如下任意一个条件，则聚类停止：

已经达到了迭代次数上限。
前后两次迭代中，聚类质心基本保持不变。

另一个视角¶

最小化每个类簇的方差

方差定义¶

用来计算变量（观察值）与样本平均值之间的差异。

\[ \text{argmin}_G \sum_{i=1}^k \sum_{x \in G_i} ||x - G_i||^2 = \text{argmin}_G \sum_{i=1}^k |G_i| \text{Var}(G_i) \]

第 $i$ 个类簇的方差：

\[ \text{Var}(G_i) = \frac{1}{|G_i|} \sum_{x \in G_i} ||x - G_i||^2 \]

目标¶

欧氏距离与方差量纲相同。
最小化每个类簇方差将使得最终聚类结果中每个聚类集合中所包含数据呈现出差异性最小。
最小化簇内距离，最大化簇间距离。

K均值聚类算法的不足¶

需要事先确定聚类数目：K 均值算法要求事先指定聚类数目 $ k $，但在许多实际场景中，数据的自然分组可能是未知的。选择错误的 $ k $ 值可能导致不合理的聚类结果。
需要初始化聚类质心：聚类结果对初始质心位置敏感，不同的初始化可能导致不同的结果。若初始质心选择不当，可能会陷入局部最优解，而不是全局最优解。
算法是迭代执行，时间开销非常大：K 均值聚类需要多次迭代，直到簇中心稳定，尤其是在数据量大或维度高时，计算欧氏距离的时间复杂度较高，导致算法执行时间增加。
欧氏距离假设数据每个维度之间的重要性是一样的：
- K均值默认使用欧氏距离作为相似性度量，但如果不同维度的尺度或重要性不同，欧氏距离可能无法准确衡量相似性。以下是欧氏距离公式： $$ d(x_i, x_j) = \sqrt{(x_{i1} - x_{j1})^2 + (x_{i2} - x_{j2})^2 + \cdots + (x_{im} - x_{jm})^2} $$
- 若某些维度在聚类中更为重要，而其他维度对聚类影响较小，简单使用欧氏距离会忽略这种差异性。

主成分分析算法¶

算法动机¶

主成分分析是一种特征降维的方法，但需要确保降维后的结果要保持原始数据固有结构。
在数理统计中，方差被经常用来度量数据和其数学期望（即均值）之间偏离程度，这个偏离程度反映了数据分布结构。
在许多实际问题中，研究数据和其均值之间的偏离程度有着很重要的意义。
在主成分分析算法降维之中，需要尽可能将数据向方差最大方向进行投影，使得数据所蕴含信息没有丢失，彰显个性。如下图所示：
向$y$方向投影（使得二维数据映射为一维）就比向$x$方向投影结果在降维这个意义上来说要好；
右下图则是斜线方向投影更好。
LDA（线性判别分析）：最大类间间隔，最小类内方差。
PCA：将每个样本当作一个类，最大类间间隔（方差）。

协方差矩阵与降维目标¶

降维后 $n$ 个 $l$ 维样本数据 $Y$ 的方差为： $$ \text{var}(Y) = \frac{1}{n-1} \text{trace}(Y^T Y) $$ 将 $Y = XW$ 代入，得到： $$ \text{var}(Y) = \frac{1}{n-1} \text{trace}(W^T X^T X W) $$ 因此，可以写为： $$ \text{var}(Y) = \text{trace} \left( W^T \frac{1}{n-1} X^T X W \right) $$
定义协方差矩阵 $\Sigma$ 为： $$ \Sigma = \frac{1}{n-1} X^T X $$
主成分分析的求解目标函数为： $$ \max_{W} \text{trace}(W^T \Sigma W) $$ 满足约束条件： $$ W^T W = I $$ 该约束条件保证降维后结果正交以去除相关性（即冗余度）。

拉格朗日乘子法优化¶

主成分分析的目标函数为：

$$ \max_{W} \text{trace}(W^T \Sigma W) $$ 满足约束条件： $$ W^T W = I $$
所有带约束的优化问题，可通过引入拉格朗日乘子法将其转化为无约束优化问题。

构建拉格朗日目标函数： $$ L(W, \lambda) = \text{trace}(W^T \Sigma W) - \sum_{i=1}^l \lambda_i (w_i^T w_i - 1) $$ 其中，$\lambda_i \ (1 \leq i \leq l)$ 为拉格朗日乘子，$w_i$ 为矩阵 $W$ 第 $i$ 列。
对上述拉格朗日目标函数中变量 $W$ 求偏导并令偏导数为零，得到：

$$ \Sigma w_i = \lambda_i w_i $$

以上式表明：每一个 $w_i$ 都是 $n \times d$ 维样本数据 $X$ 的协方差矩阵 $\Sigma$ 的一个特征向量，$\lambda_i$ 是这个特征向量所对应的特征值。

PCA的计算过程¶

数据中心化：

PCA的第一步是对原始数据进行中心化，即从每个特征值中减去该特征的均值。假设数据集为一个 $n \times m$ 的矩阵 $X$，其中 $n$ 是样本数，$m$ 是特征数，那么中心化后的数据 $X_c$ 为： $$ X_c = X - \mu $$

其中，$\mu$ 是数据集 $X$ 每个特征的均值向量。
计算协方差矩阵：

计算数据集的协方差矩阵是下一步。协方差矩阵描述了数据集内各个特征之间的相关性。协方差矩阵 $C$ 的计算公式为：

$$ C = \frac{1}{n-1} X_c^T X_c $$

其中，$X_c^T$ 是中心化后的数据矩阵的转置，$X_c$ 是中心化后的数据矩阵。
特征值和特征向量：

求解协方差矩阵 $C$ 的特征值和特征向量。特征值代表了主成分的“重要性”，即它们表示该方向上的方差大小；特征向量代表了数据变换后的坐标轴（主成分的方向）。求解特征值和特征向量可以通过以下特征方程：

$$ C v = \lambda v $$

其中，$\lambda$ 是特征值，$v$ 是特征向量。
排序特征值：

将所有特征值按降序排列，并选择前 $k$ 个特征值及其对应的特征向量。选择的 $k$ 个特征向量构成一个新的矩阵 $V_k$，这些特征向量表示数据集中的主要变化方向。
数据投影：

最后，将原始数据投影到新的特征向量上，得到降维后的数据。投影公式为：

$$ X_{reduced} = X_c V_k $$

其中，$V_k$ 是前 $k$ 个特征向量组成的矩阵，$X_{reduced}$ 是降维后的数据。

LDA 与 PCA 的对比¶

LDA 和 PCA 都是降维方法，但它们的目标和适用场景有所不同：

特性	LDA	PCA
学习方式	监督学习	无监督学习
目标	优化类间差异最大化，类内差异最小化	优化数据投影后方差最大化
用途	更适合分类任务，依赖数据的类别标注	更适合降维任务，不需要类别标注信息
降维限制	降维后维度 ≤ min(K-1, d)，K 为类别数	降维后维度 ≤ 原始数据的维度 d

其他降维方法¶

非负矩阵分解（Non-negative Matrix Factorization, NMF）¶

该方法将非负的大矩阵分解成两个非负的小矩阵。
矩阵分解的一般目标是将原始矩阵 $D$ 表示为矩阵 $W$ 和矩阵 $H$ 相乘的形式，即 $D = WH$。
主成分分析方法可以实现降维，但主成分分析不要求原始矩阵 $D$ 中所有元素为正数（即非负）。
在很多实际情况下，如图像所组成的像素矩阵或自然语言中常用的单词-文档矩阵中并不存在为负数的元素，因此，对非负矩阵的分解是很有意义的问题。

多维尺度法（Metric Multidimensional Scaling, MDS）¶

多维尺度法（Metric Multidimensional Scaling, MDS）保持原始数据之间两两距离不变。
MDS算法会计算原始数据两两之间的距离，形成一个距离矩阵，以此来保证降维之前距离近的数据在降维之后也能很接近。
不过，正因为MDS需要知道这样的距离矩阵，所以无法对新数据集合进行降维（比如测试集），这被称为“out-of-sample”问题。

局部线性嵌入（Locally Linear Embedding, LLE）¶

LLE属于流形学习（Manifold Learning）的一种。
流形学习是一大类基于流形的框架。数学意义上的流形比较抽象，不过我们可以认为LLE中的流形是一个不闭合的曲面。这个流形曲面有数据分布比较均匀、且比较稠密的特征，有点像流水的味道。
基于流形的降维算法就是将流形从高维到低维的降维过程，在降维的过程中我们希望流形在高维的一些特征可以得到保留。

特征人脸识别¶

动机¶

特征人脸方法是一种应用主成分分析来实现人脸图像降维的方法，其本质是用一种称为“特征人脸（eigenface）”的特征向量，用特征人脸矩阵和人脸图像进行矩阵乘法，实现降维。

所以我们一是要得到这个特征人脸矩阵，二是要实现有效的降维识别。

算法描述¶

数据中心化：

对于每个人脸样本数据 $x_i$ 进行中心化处理： $$ x_i = x_i - \mu, \quad \mu = \frac{1}{n} \sum_{j=1}^n x_j $$
计算协方差矩阵：

计算原始人脸样本数据的协方差矩阵： $$ \Sigma = \frac{1}{n-1} X^T X $$
特征值分解与降维：

对协方差矩阵 $\Sigma$ 进行特征值分解，对所得特征根从大到小排序 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_d$。
取前 $l$ 个最大特征根对应特征向量 $w_1, w_2, ..., w_l$ 组成映射矩阵 $W$（类似 PCA，还是要方差最大）
将每个人脸图像 $x_i$ 按照如下方法降维： $$ (x_i){1 \times d}(W) = 1 \times l $$

基于特征人脸的降维¶

降维操作：

将每幅人脸分别与每个特征人脸做矩阵乘法，得到一个相关系数（？）。每幅人脸得到 $l$ 个相关系数 $\Rightarrow$ 每幅人脸从 $1024$ 维约减到 $l$ 维。
表述形式：

由于每幅人脸是所有特征人脸的线性组合，因此就实现人脸从“像素点表达”到“特征人脸表达”的转变。每幅人脸从 $1024$ 维约减到 $l$ 维： $$ x_i = \alpha_{i1} \cdot w_1 + \alpha_{i2} \cdot w_2 + \cdots + \alpha_{il} \cdot w_l $$
意义：

在后续人脸识别分类中，就使用这 $l$ 个系数来表示原始人脸图像。例如，计算两张人脸是否相似，不是去计算两张 $32 \times 32$ 矩阵是否相似，而是计算两个人脸所对应的 $l$ 个系数是否相似。

潜在语义分析¶

动机¶

潜在语义分析（Latent Semantic Analysis, LSA）是一种用于从文档-词项矩阵中提取潜在语义结构的技术。其核心思想是通过降维来消除词汇间的冗余信息，提取隐含的语义关系。
LSA 的关键在于通过矩阵分解，将文档和词项表示在一个低维的语义空间中，使得相似的文档和词项在该空间中具有较高的相似性。

算法描述¶

构建文档-词项矩阵：

假设有 $m$ 个文档和 $n$ 个词项，用一个 $m \times n$ 的矩阵 $X$ 表示，其中 $X_{ij}$ 表示词项 $j$ 在文档 $i$ 中的权重（如词频或 TF-IDF 值）。

矩阵奇异值分解 (SVD)：

对矩阵 $X$ 进行奇异值分解（奇异值分解适用于任何矩阵），将其分解为以下三个矩阵的乘积： $$ X = U \Sigma V^T $$ 其中：
- $U$ 是一个 $m \times r$ 的正交矩阵，表示文档的特征向量。
- $\Sigma$ 是一个 $r \times r$ 的对角矩阵，其对角线上的值为 $X$ 的奇异值，按降序排列。
- $V^T$ 是一个 $r \times n$ 的正交矩阵，表示词项的特征向量。

降维：

选取奇异值矩阵 $\Sigma$ 中最大的 $k$ 个奇异值（保留最多的信息），截断矩阵 $\Sigma$、$U$ 和 $V^T$，得到降维后的矩阵：

$$ X_k = U_k \Sigma_k V_k^T $$

其中，$U_k$ 是 $m \times k$ 的矩阵，$\Sigma_k$ 是 $k \times k$ 的对角矩阵，$V_k^T$ 是 $k \times n$ 的矩阵。

语义空间表示：

文档和词项被映射到 $k$ 维的潜在语义空间中：
- 每个文档由矩阵 $U_k \Sigma_k$ 的列表示。
- 每个词项由矩阵 $\Sigma_k V_k^T$ 的行表示。

特性¶

通过降维去除文档-词项矩阵中的噪声和冗余，提取出词项与文档的潜在语义结构。
在语义空间中，相关的文档和词项距离更近，能够反映更深层的语义关系。

应用¶

信息检索：

在语义空间中计算文档与查询的相似度，能够有效提高信息检索的准确率。

文档聚类：

根据文档在语义空间中的表示对其进行聚类，发现主题。

文本分类：

在语义空间中，文档的低维表示能够作为分类器的输入特征。

期望最大化算法¶

疑似上课没讲？到时候再说吧