Korean, Edit

第 7 章. 降维算法

推荐帖子：【算法】 算法索引

1. 概述

2. 类型 1. 主成分分析 (PCA)

3.类型 2. SNE、对称-SNE、tSNE

4.类型 3. UMAP

5.类型 4. SVD

6.类型 5. ICA

7. 类型 6. PPCA

8. 类型 7. CCA

9. 其他

a. SNE、对称-SNE、tSNE

b. UMAP

1.概述

⑴ 降维的定义

① 当给定高维数据 X₍₁₎, ···, X_(n) ∈ ℝ^p,

② 找到合适的子空间 V ⊂ ℝ^p （其中dim(V) = k），

③计算X在V上的投影，记为X̃。

④ 是一种无监督算法。

⑵ 特点

① 信息保存

② 更容易的模型训练：在机器学习中，它需要的参数更少，因此速度更快，计算量更低。

③ 更容易的结果解释：高维数据的可视化。

④ 降噪

⑤ 能够揭示给定数据的真实维数。

⑶ 方法

① 特征选择

○ 从现有变量中选择一些重要变量，并丢弃其余变量。

○ 选择一个具有高相关性或高方差膨胀因子 (VIF) 的变量。

② 特征提取

○ 组合所有变量以得出最能代表数据的新变量。

○ 结合现有变量来创建新变量的技术。

2.类型 1. 主成分分析 (PCA)

⑴ 概述

①定义：将相关变量转化为正交变量的降维技术。

② 也就是说，它是一种只留下少数有意义的坐标系的降维方法。

③ 正交变量称为主成分，当其包含与原始数据一样多的信息时即可使用。

④ 源于对给定维度和数据真实维度可能不同的认识。

⑤ 1901 年由皮尔逊提出。

⑥ PCA不仅可以在子空间（经过原点）定义，也可以在仿射空间定义。

⑦ ** 按均值归一化，然后对子空间进行 PCA。

⑧ PCA 不要求给定数据的多元正态性。

⑨ 当数据呈线性分布时可以使用。

⑩ 白化：进行标准化时最好沿主成分方向对特征进行标准化。

⑵ 经营场所

① 将数据所属空间的基表示为e₁,…,e_p（基集不需要是正交的）。

○ e₁,…, e_p 可以被认为是表示给定维度的基（不需要正交性）。

② 目标：找到这样一个子空间 (k < n) 的正交基 Z₁,…, Z_k（典型的无监督问题设置）。

○ Z₁,…, Z_k 可以被认为是代表数据真实维度的基数。

③ 随机向量

○ X 代表一个特定的数据点：x₁、…、x_n 是每个分量。

④ 均值向量：也称为总体均值。

⑤ 方差-协方差矩阵

⑥ 无偏样本方差-协方差矩阵：用设计矩阵X，和中心矩阵X_c，

○ 当总体方差-协方差矩阵未知时使用。

○ 由于 X ε ℝ^n×p，X^TX ε ℝ^p×n × ℝ^n×p = ℝ^p×p。

⑦ 目标正交基的表达

○ Z_k: = k-th PC ∈ ℝ^p×1.

⑧ 目标正交基的特点：很容易从线性代数概念中推导出来。

○ Var、Cov等，是与方差相关的具体值，属于ℝ^1x1。

○ 不要与方差-协方差矩阵混淆。

⑶ PCA问题的定义

⑷ PCA问题的解决方法

① 方法1. Σ 的特征分解。

○ 第1步：数据构建和居中

○ X ∈ ℝ^n×d：具有 n 个样本和 d 个特征的数据矩阵。

○ 将数据矩阵 X 居中： X_c = X - μ 其中 μ ∈ ℝ^d 是逐列均值的向量）

○ 第2步：协方差矩阵计算

○ 根据中心数据计算样本协方差矩阵 C ∈ ℝ^d×d：

○ 由于给定样本代表整个总体，总体均值已知，因此样本协方差是通过除以 n 而不是 n−1 来计算的。

○ 步骤3：特征分解

○ 对协方差矩阵_C_进行特征分解，计算特征值和特征向量： C · p_i = λ_i · p_i

○ 这里，λ_i 表示特征值，p_i ​ε R^d 是特征向量。

○ 注意：对称矩阵 C 始终可以正交对角化（通过谱定理）。

○ 第4步：数据转换

○ 定义 P = [p₁, p₂, …, p_d] ∈ R^d×d，一个矩阵，其中特征向量存储为列。

○ 将数据转换到新的坐标系： Y = X_cP 其中 Y ∈ R^n×d 是转换后的数据矩阵。

○ 步骤 5： 协方差矩阵的对角化

○ 变换后的数据 Y 的协方差矩阵变成对角线：

○ 第6步： 主成分选择和降维

○ 选择最大特征值 λ_i 对应的_k_个主成分（特征向量）并降维： Y_k = X_cP_k with P_k ε ℝ^d×k, Y_k ε ℝ^n×k

○ 或者，不固定主成分的数量，而是可以排除小于特定阈值 η 的特征值。» ○ 结论1. 第d个主成分PC_d是第d个最大特征值对应的特征向量。

○ 结论2. 特征值相同的特征向量的含义：对应主成分的大小相同。

② 方法2. 中心矩阵的奇异值分解（SVD） X_c：目前PCA算法中使用的标准方法。

○ 步骤1：将数据居中，得到居中数据X_c。

○ 步骤2：定义​C = (1/n) X_c^TX_c = Σ（协方差矩阵） ​ ○ 步骤 3： 由于 C 是对称的，因此可以将其正交对角化为 C = VDV^T （其中 V 与 X_c = UΣV^T 中的 V 相同）

○ 步骤 4. V 的第 1^st、2^nd、… 列向量是第 1^st、2^nd、… 最大特征值对应的特征向量，是主成分。

③ 方法3. 【等式约束下的拉格朗日乘子】(https://jb243.github.io/pages/1813)。

○ 步骤 1. 通过求解 w 来获得第一主成分，该 w 在约束ㅣwㅣ = 1 的条件下最大化 Var(X_cw)。应用拉格朗日乘数方法会导致 Cw = λw 形式的条件，从而简化为特征值问题。

○ 步骤 2. 然后以相同的方式顺序找到第二个和第三个主成分，并附加约束，即它们与先前找到的成分正交（或不相关）。

⑸ 确定轴数

① 方法 1. 总方差分数的卵石图。

○ 总方差分数的定义。

○ 图形表示。

图 1. 轴设置示例。

图 2. 碎石图：显示每个主成分解释的方差量。

② 方法2. 基于特征值的碎石图

○ 绘制有序特征值 λ₁, …, λ_p 并识别曲线中的肘部（弯曲）。

○ 选择直到肘点的 PC 数量，此时剩余的特征值变得相对较小且大小相似。

③ 方法3. 通过最小化MSPE来选择p

○ 改变 PC p 的数量（例如，使用样本内 10 倍交叉验证）并评估预测模型。

○ 选择使 MSPE 最小化的最佳 p（或 RMSE = √MSPE）。

图 3. 轴数量的确定。

④ 由于剩余轴的信息丢失，PCA 起到有损压缩算法的作用。

⑹ Python代码示例

受保护_0

⑺ PCA的发展

① 内核PCA：使用kernels。可以将给定数据扩展到高维度，也可以通过投影将其降低到较低维度。

② MDS（多维尺度）

③ SNE、t-SNE

④ 乌玛普

3.类型2。SNE、对称SNE、tSNE

⑴ 一种试图保留数据中局部邻域的降维算法。

⑵ 非线性和非确定性。

⑶ 需要了解[深度学习]相关的成本函数、更新算法等知识(https://jb243.github.io/pages/1138)。

4.输入 3。 UMAP

5.类型 4. 奇异值分解 (SVD)

⑴从M×N维矩阵中提取奇异值并降低给定数据维数的方法。

⑵ 公式

①小结：若 A 是秩为 r 的 m × n 矩阵，则存在满足以下条件的 ℝm×m 矩阵 U 和 ℝn×n 矩阵 V：

○ U 和 V 是正交矩阵。

○ 由于改变U的每一列和V的对应列的符号仍然满足上式，因此SVD不是唯一确定的。

○ 矩阵 Σ：对角线上有 r 个非零奇异值 (> 0) 的 m × n 矩阵。

② 全程

③ 奇异值定义为 AA^T 或 A^TA 特征值的正平方根。

○ AA^T 和 A^TA 零特征值的数量可能不同，但它们产生相同的非零特征值。

○ 非零奇异值的数量等于rank(A)。

○ 零奇异值的数量为 max(dim(A)[0], dim(A)[1])−rank(A)。

④Python代码

受保护_1

⑶ 应用1. A^TA = V(Σ^TΣ)V^T ：A的奇异值是A^TA特征值的平方根。然而，根据等级，一些特征值被设置为0。

⑷ 应用2. 简化SVD：请注意，对于简化版本，U 和V 都有正交列。这意味着 U^TU = I 且 V^TV = I。但是，在此版本中 U 和 V 不是方阵，因此它们不是正交矩阵。

受保护_2

⑸ 应用3. k 阶近似

① 对于 k <rank(A)，可以将 m × n 矩阵 A 拆分为 m × k + k × n 矩阵来实现压缩。

② 给定k，如何求A的最优k阶近似：

○ A = UΣV^T = σ₁u₁v₁^T + ··· + σ_ru_rv_r^T，其中 σ₁ ≥ ⋯ ≥ σ_r，删除较小的奇异值 σ_r，σ_r−1，…。

○ 这样，A^(k) 和 A 之间的弗罗贝尼乌斯距离定义如下：

⑹ 应用4. PCA（主成分分析）

① 步骤 1. 将数据居中

图。 4. PCA的数据中心化

② 步骤2. X_c 是居中数据，C = (1/n) X_c^TX_c> ③ 步骤3. C 是对称的，因此可正交对角化为 C = VDV^T。 V 与 SVD 中的 X_c = UΣV^T 相同。

④ 步骤 4. V 的第 1^st、2^nd、… 列向量是第 1^st、2^nd、… 最大特征值对应的特征向量，是主成分。

⑤ 步骤 5. 如果您想仅根据前 2 个 PC 获取 X 中向量的新坐标，只需将 x_i （长度为 p 的向量）投影到前两个 PC 上即可：

6.类型 5. 独立成分分析 (ICA)

⑴ 与主成分分析不同，它是一种降维技术，将多元信号统计分离为独立的子成分。

⑵ 例如$N$个麦克风区分$M$个对话的场景。

⑶ 独立成分的分布服从非高斯分布。

⑷ 它利用矩阵分解。

7.类型 6.PPCA

⑴ 配方

① 步骤1. 假设观测数据x是由潜在变量z生成的：以下变换本身成为一种降维技术。

○ W：维度 D × d 的变换矩阵（用于从潜在空间映射到观察空间）

○ b: D 维平均向量

○ ϵ：噪声，服从正态分布 N(0,σ²I)

② 步骤2. 对潜变量z的假设

③ 步骤 3. x 给定 z 的条件分布

④ 步骤 4. 边际分布 p(x)

⑤ 步骤 5. MLE 估计

○ 最大似然估计 (MLE) 用于根据给定数据估计 b、W 和 σ。

○ MLE 解是以封闭形式获得的。

○ 当 σ → 0 时，该方法收敛于标准 PCA。

⑵ 代码

受保护_3

8.类型 7.CCA

⑴ CCA（典型相关分析）

① 问题陈述：给定数据矩阵 X ∈ ℝ^n×p 和 Y ∈ ℝ^n×q，目标是最大化变换变量的相关系数。

○ Σ_xx = X^TX: X ∈ ℝ^p×p 的协方差矩阵

○ Σ_yy = Y^TY：Y ∈ ℝ^q×q 的协方差矩阵

○ Σ_xy = X^TY: X 和 Y 之间的互协方差矩阵 ε ℝ^p×q

○ Σ_yx = (Σ_xy)^T

② 解决方法：将问题重新表述为优化问题，约束条件为：w_x^TΣ_xxw_x = 1 和 w_y^TΣ_yyw_y = 1，并应用[拉格朗日乘子]方法](https://jb243.github.io/pages/1813)。

③ 结论：典型相关性由矩阵广义特征值的正平方根给出：Σ_xx^-1Σ_xyΣ_yy^-1Σ_yx。

⑵ DCCA（对角CCA）

① 问题陈述：给定数据矩阵 X ∈ ℝ^n×p 和 Y ∈ ℝ^n×q

○ D_x = diag(Σ_xx)：仅使用协方差矩阵的对角线元素

○ D_y = diag(Σ_yy)：仅使用协方差矩阵的对角线元素

② 过程：SVD 的奇异值确定典型相关值。

⑶ CCA与DCCA的比较

表 1. CCA 和 DCCA 的比较

9.其他

⑴因素分析

① 定义：一种通过根据相似变量的相关性对相似变量进行分组来解释数据内部结构的方法。

② 假设存在数据中无法观察到的潜在变量。

③ 常用于社会科学或调查。

⑵ 多维标度（MDS）

① 定义：通过识别数据中潜在的模式和结构来可视化低维空间中对象的接近度和分组的统计技术。

② 测量对象之间的相似性和相异性，并将它们表示为 2D 或 3D 空间中的点。

⑶ 线性判别分析（LDA）

①定义：通过将数据投影到低维空间来降维的方法，类似于PCA。

⑷ RPCA（倒数主成分分析）

⑸ 自动编码器

① 变分自动编码器（VAE）

② 图自动编码器（GAE）

③【矩阵分解与NMF】(https://jb243.github.io/pages/956#4-type-3-matrix-factorization)

④【潜在主题模型】(https://jb243.github.io/pages/956#5-type-4-latent-topic-model)：潜在语义索引(LSI)、潜在狄利克雷分配(LDA)等。

⑹ 信号模式分析（SPA）（ref1、ref2)

① SPA 没有使用谱聚类中使用的传统拉普拉斯矩阵，而是利用从图中导出的马尔可夫转移矩阵 P^t 的力量来捕获不同扩散时间 t 的信息。> ② 较短的扩散时间 t 对局部模式敏感，而较长的时间反映更多的全局结构，利用这一特性进行分析。

⑺ 磷酸盐

⑻ 官方发展援助

⑼ 光引擎

⑽ LSA

⑾ PLSA（概率潜在语义分析）

① 用于从潜在类模型中分解混合组件。

② 应用：用于质谱数据降维。

输入：2021.12.3 16:22