非负矩阵分解（NMF）算法
题目描述
非负矩阵分解（Non-negative Matrix Factorization, NMF）是一种线性代数算法，其目标是将一个非负矩阵 \(V \in \mathbb{R}^{m \times n}\)（其中所有元素 \(V_{ij} \geq 0\)）分解为两个非负矩阵 \(W \in \mathbb{R}^{m \times k}\) 和 \(H \in \mathbb{R}^{k \times n}\) 的乘积，即 \(V \approx WH\)。这里 \(k\) 是一个远小于 \(m\) 和 \(n\) 的预设秩（通常满足 \(k \ll \min(m, n)\)）。NMF 在数据降维、特征提取和主题建模等领域有广泛应用，例如从图像数据中提取部分特征或从文本数据中发现潜在主题。
解题过程
- 问题形式化
NMF 的优化问题可表述为：
\[ \min_{W \geq 0, H \geq 0} \| V - WH \|_F^2 \]
其中 \(\| \cdot \|_F\) 是 Frobenius 范数（矩阵元素平方和的平方根），约束条件 \(W \geq 0\) 和 \(H \geq 0\) 要求所有元素非负。该问题是非凸的，但可通过迭代算法逼近局部最优解。
- 迭代更新规则的设计
常用方法是基于梯度下降的乘法更新规则（Multiplicative Update Rules）。具体步骤：- 初始化：随机生成非负矩阵 \(W\) 和 \(H\)。
- 迭代更新：交替固定其中一个矩阵，更新另一个矩阵，使目标函数减小。
- 更新 \(H\)（固定 \(W\)）：
\[ H_{ij} \leftarrow H_{ij} \frac{(W^T V)_{ij}}{(W^T W H)_{ij}} \]
- 更新 $ W $（固定 $ H $）：
\[ W_{ij} \leftarrow W_{ij} \frac{(V H^T)_{ij}}{(W H H^T)_{ij}} \]
每一步更新均通过元素乘除实现，确保非负性。
- 收敛判断：当目标函数变化小于阈值或达到最大迭代次数时停止。
-
算法原理解释
- 乘法更新规则本质是对梯度下降步长的自适应调整：分母项 \(W^T W H\) 或 \(W H H^T\) 作为归一化因子，避免手动设置学习率。
- 非负约束使得分解结果具有可解释性（例如，图像中的部分表示或文本中的主题分布）。
-
示例说明
假设 \(V\) 是一个 \(4 \times 5\) 的非负矩阵（如4个文档的5个单词频率），设定 \(k=2\)：- 初始化 \(W\)（4×2）和 \(H\)（2×5）为随机非负矩阵。
- 迭代10次后，\(W\) 的每一列可解释为“主题”，\(H\) 的行表示主题在文档中的权重。
- 最终 \(WH\) 逼近 \(V\)，且所有元素保持非负。
-
应用与注意事项
- NMF 对初始值敏感，可能收敛到不同局部最优解，建议多次运行取最佳结果。
- 若数据包含负值，需先进行非负预处理（如平移或取绝对值）。
通过以上步骤，NMF 能够从非负数据中提取低维结构，同时保持分解结果的物理意义。