Stochastic Batch Coordinate Descent with Q-Structure Preservation and Gradient-Magnitude-Guided Non-Uniform Sampling (QG-SCD)
本文提出一种 Q 结构保持与梯度幅值引导的非均匀采样随机批量坐标下降法（QG-SCD），用于矩阵分解协同过滤的电影评分预测。仓库包含完整可运行代码、数据与实验图；论文正文（第 1–5 章、算法伪代码、核心代码、参考文献）已完整收录于本 README，便于直接阅读。
- 摘要 / Abstract
- 1 引言
- 1.1 研究背景及意义
- 1.2 国内外研究进展
- 1.3 论文的创新点、主要工作及组织框架
- 2 问题建模与预备知识
- 2.1 电影评分矩阵分解问题建模
- 2.2 随机坐标下降法（SCD）的基础知识
- 3 基于电影类型先验的智能采样策略 SCD 算法
- 3.1 Q 结构约束下的矩阵分解问题重构
- 3.2 基于梯度幅值的非均匀概率采样策略
- 3.3 算法流程与实现
- 4 实验验证与结果分析
- 4.1 实验设置
- 4.2 评估指标与对比方法
- 4.3 梯度放大指数对算法性能的影响分析
- 4.4 误差统计与稀疏性影响分析
- 5 总结与展望
- 附录：QG-SCD 核心 Python 代码
- 参考文献
- 仓库结构 / Repository Structure
- 快速开始 / Quick Start
- 实验图 / Figures
- License
中文：矩阵分解推荐算法作为协同过滤的核心技术，通过将用户-物品交互矩阵分解为低维隐因子空间，实现对用户偏好的精准建模与个性化推荐。在日常生活场景中，该算法广泛应用于音乐流媒体、电子商务、视频平台等领域，显著提升了信息服务的匹配效率。现在矩阵分解推荐算法已成为数字生活基础设施的重要组成部分，具有重要的理论研究价值与现实应用意义。本文针对传统矩阵分解推荐算法中存在的可解释性弱与收敛效率低两个核心问题，提出一种基于矩阵结构保持与梯度引导的改进随机坐标下降算法。该算法首先利用电影类型标签对物品隐因子矩阵 Q 进行语义化初始化，并在优化中保持其结构以增强模型可解释性；接着设计了一种基于梯度幅值的非均匀采样策略，使算法以更大概率更新对损失函数影响更大的参数，从而加速收敛。本研究基于 MovieLens Latest Small 数据集，分析不同梯度放大指数下算法在相同迭代次数的计算时间与预测误差 RMSE。实验结果表明，所给算法在保持良好预测精度的前提下，相较于均匀采样方法显著提升了训练效率。同时，所学习到的用户偏好矩阵与电影特征矩阵呈现出清晰的语义结构，从而为可解释推荐系统的研究提供了兼具理论价值与实践意义的解决方案。
关键词：推荐系统；隐语义模型；矩阵分解；随机坐标下降法
English: Matrix factorization recommendation algorithm, as the core technology of collaborative filtering, achieves precise modeling of user preferences and personalized recommendations by decomposing the user-item interaction matrix into a low-dimensional latent factor space. In daily life scenarios, this algorithm is widely applied in music streaming, e-commerce, video platforms, and other fields, significantly improving the matching efficiency of information services. This thesis addresses two core issues of the traditional matrix factorization recommendation algorithm, namely weak interpretability and low convergence efficiency. It proposes an improved stochastic coordinate descent algorithm based on matrix structure preservation and gradient guidance. The algorithm first initializes the item latent factor matrix Q semantically using movie genre labels and maintains its structure during optimization to enhance model interpretability. Then, a non-uniform sampling strategy based on gradient magnitude is designed to enable the algorithm to update parameters with a higher probability that have a greater impact on the loss function, thereby accelerating convergence. This study is based on the MovieLens Latest Small dataset, and analyzes the computing time and prediction error RMSE of the algorithm under different gradient amplification indices with the same number of iterations. The experimental results show that the proposed algorithm achieves good prediction accuracy while significantly improving training efficiency compared to the uniform sampling method.
KeyWords: recommendation system; latent semantic model; matrix factorization; stochastic coordinate descent method
随着互联网与信息技术的迅猛发展，人类社会已全面迈入大数据时代。如今，全球数据信息总量正以指数爆炸的速度快速增长，信息产生速度远远超出个体的接收与处理能力，由此引发的信息过载问题已成为数字化生存中的核心挑战之一。在此背景下，如何从海量、动态、异构的数据中精准识别用户需求，实现信息的高效筛选与个性化推送，已成为学术界与企业界共同关注的关键议题。
推荐系统作为解决信息过载的核心技术，它的根本任务是从海量用户行为数据（如评分、点击、购买）中挖掘潜在偏好，实现信息的个性化筛选与精准分发，从而提升用户体验和平台商业价值。
然而，随着数据规模的急剧膨胀，推荐系统在实践应用遇到了前所未有的技术挑战。首当其冲的就是数据稀疏性问题，即用户与物品之间的交互数据十分匮乏。例如，在拥有数百万用户和数十万物品（如电影、书籍）的平台中，单个用户所能接触并评价的物品数量极其有限，这导致用户-物品交互矩阵中高达 90% 以上的条目是缺失的。这种稀疏性使得传统算法难以准确计算用户或物品之间的关联，严重制约了推荐结果的准确性与覆盖率。
数据稀疏性问题会引发连锁反应，其后果在新用户或新物品上体现得尤为明显。由于历史交互数据的匮乏，系统无法刻画其有效的兴趣画像，因此无法准确推断其偏好，使得协同过滤等算法的核心功能失效，最终导致推荐效果大打折扣。此外，稀疏性数据还放大了推荐偏差，算法容易过度依赖少数热门物品的流行度偏见，导致越流行的内容越被频繁推荐，而大量末端物品则被系统忽略，使得用户兴趣范围被迫收窄，呈现"信息茧房"效应。这种偏差在算法与用户的反馈循环中被不断强化，进一步降低了推荐的多样性和新颖性。
为了解决上述推荐系统针对稀疏性数据存在的问题，隐语义模型（Latent Factor Model, LFM）被提出。在隐语义模型中，"隐"的核心含义是潜在的、未被直接观测或定义的。系统从用户交互数据（如用户对某物品的评分、对某视频的点击率）挖掘而来的"属性"（比如，某个电影的科幻成分，某个用户对于科幻成分的喜爱程度，某个商品的实用性，某个用户对于性价比的敏感度），不依赖任何先验的标签信息，就是隐因子。反之对应的显因子，是直接可用的、具有明确物理意义的特征，如用户的年龄、性别、职业，商品的类别、品牌、价格等等。LFM 通过将用户和物品映射到同一个低维潜空间，并利用向量内积度量用户对物品的偏好程度，从而将推荐问题转化为一个矩阵补全问题。这种方法能有效挖掘数据背后的深层特征，显著缓解了数据稀疏性问题。
隐语义模型以矩阵分解为核心技术，旨在通过将高维稀疏矩阵降维分解为两个低秩矩阵，来提取用户与物品的潜在因子，从而实现对原始交互结构的深度挖掘与表示。该模型的核心目标是将高维稀疏矩阵
(1.1)
其中，核心数据
矩阵分解技术可以有效挖掘潜在特征，但在处理大规模数据的矩阵时，其传统求解方法往往面临扩展性瓶颈。为此，基于随机采样策略的矩阵分解优化方案被采用，它通过利用单一样本或小批量数据来逼近梯度，极大地提升了求解海量矩阵分解问题的效率。其中：
- 随机梯度下降法（SGD） 每次迭代随机选择一个样本（或一个小批量样本）计算梯度并更新所有参数；
- 交替最小二乘法（ALS） 作为一种块坐标下降法，交替固定用户矩阵或物品矩阵，并利用评分矩阵的稀疏性解析求解另一个矩阵，成为处理隐式反馈的基准算法；
- 随机坐标下降法（SCD） 展现出独特优势：与 SGD 每次随机选择一个样本更新所有参数不同，SCD 每次迭代仅随机选择一个或一小部分坐标进行更新。这种"精细化"的更新策略使其单次迭代的计算成本极低，并且非常利于并行化实现，从而更加适合处理超大规模稀疏矩阵。
然而，传统的 SCD 通常采用均匀随机采样策略选择要更新的坐标。在高度稀疏的数据场景下，大部分参数的梯度值很小，更新它们对目标函数下降的贡献微乎其微。均匀采样会以同等概率选中这些"不重要"的坐标，导致大量计算资源被浪费，限制了算法的收敛速度和实际效率。因此，通过设计更智能的、非均匀的采样策略，使算法能优先选择梯度更大、即当前更"重要"的参数进行更新，可以显著减少迭代次数，加速收敛过程。
本研究旨在改进和优化 SCD 在稀疏矩阵分解中的应用。通过研究并设计自适应的基于梯度幅值采样的非均匀坐标采样策略，引导算法优先更新对目标函数下降贡献更大的关键参数，为大规模稀疏优化算法的发展提供新的思路和理论支撑。同时，一个高效的 SCD 算法能够更快地从海量稀疏数据中学习用户偏好，从而加速模型迭代周期，降低计算资源消耗。这对于需要实时更新推荐的在线系统至关重要。
在推荐系统领域中，矩阵分解（Matrix Factorization, MF）技术凭借其强大的稀疏数据处理能力，已成为协同过滤算法的核心技术范式之一。传统的奇异值分解（SVD）及其变体（如 FunkSVD）虽取得了显著成效，但其优化目标函数缺乏概率学解释。Salakhutdinov 提出了概率矩阵分解模型，该模型为矩阵分解提供了概率框架下的贝叶斯解释，成为后续众多改进算法的理论基础。
由 Koren 等人发表的综述论文《Matrix Factorization Techniques for Recommender Systems》是该领域的奠基性之作，系统性地阐述了基于矩阵分解的推荐模型及其优化方法。论文重点介绍了两种主流的优化算法：
-
随机梯度下降法（SGD）：遍历所有已知评分，对于每一个评分
$r_{ui}$ ，计算预测误差，然后沿误差减小的方向同时更新用户和项目的特征向量； -
交替最小二乘法（ALS）：固定其中一个矩阵（如
$Q$ ）时，优化另一个矩阵（如$P$ ）的问题就转化为一个简单的线性回归问题，具有解析解。通过交替固定$P$ 和$Q$ 并求解，直至收敛。ALS 的优势在于易于并行化，特别适合处理隐式反馈数据。
显式反馈数据（如用户评分）的稀缺性是一个巨大挑战，而隐式反馈数据（如点击、浏览、购买记录）则更为丰富和易得。Hu 等人在 2009 年提出了加权正则化矩阵分解模型（隐式反馈的 ALS 模型），为隐式反馈场景下的协同过滤奠定了理论基础。宋威和李雪松（2018）针对数据稀疏场景引入了标签信息作为辅助特征，通过标签自适应选择机制动态筛选最相关的物品标签。陈晔与刘志强（2019）通过自适应正则化约束项动态调整模型复杂度，并设计用户聚类引导的协同训练机制。高子建等人（2021）提出基于谱聚类的智能协同推荐方法，先聚类相似用户再在子矩阵上局部预测。
随着深度学习的兴起，Rendle（2010）发明了因子分解机（FM），从根本上解决了高效建模任意特征间二阶交互的问题；He 等人（2017）发明神经协同过滤框架（NCF），利用深度学习从数据中自动学习复杂的非线性用户-物品交互函数；Guo 等人（2017）发明 DeepFM 模型，无缝集成低阶与高阶特征交互；陈平华与朱禹（2018）提出将知识图谱表示学习与矩阵分解相融合的推荐算法，显著提升了推荐结果的可解释性。
随机坐标下降法（SCD）的理论研究已建立起严谨的分析体系。Nesterov 的开创性研究为 SCD 奠定了系统的理论基础，首次给出算法的严格收敛性证明，并深入分析基于 Lipschitz 常数的最优采样策略（如重要性采样）。随后 Richtárik 等人在 2014 年将上述理论框架推广至块坐标下降情形，系统分析了其在复合函数优化中的迭代复杂度。
在推荐系统的矩阵分解中，SCD 的理念深刻影响了主流优化算法。例如交替最小二乘法可视为一种块坐标下降法。Zhou 等人（2008）给出了一种基于 ALS 的大规模并行协同过滤算法，成功解决传统矩阵分解面对海量数据时的计算效率低下问题，其交替优化策略是确定性坐标下降法的核心，为后续随机化版本奠定坚实基础。赵磊等人（2019）针对大规模 SCAD 回归提出基于随机坐标下降的变量 Bregman 优化方法；徐宇淼等人（2022）针对 L1 正则化 L2 损失 SVM 提出多层随机坐标下降算法；谢亚君（2023）通过融合贪婪策略与 SCD，在每轮迭代中优先选择对目标函数下降贡献最大的坐标方向进行更新，有效突破传统均匀采样 SCD 的收敛速度瓶颈。Kemal 等人（2024）针对大规模矩阵补全提出混合并行 SGD，其无锁异步并行的核心思想与 SCD 高度契合。
本文提出两项核心创新：
-
结构保持的初始化与优化机制：针对传统矩阵分解中隐因子矩阵语义模糊的问题，基于电影类型标签构建具有明确物理含义的
$Q$ 矩阵初始值，并在迭代中保持其符号方向（稀疏结构）不变，从而确保用户偏好矩阵$P$ 与电影特征矩阵$Q$ 均可解释，有效克服了旋转不变性导致的解不唯一问题。 - 梯度幅值引导的非均匀采样策略：针对均匀采样在优化过程中效率低下的局限，将梯度幅值引导的非均匀采样策略引入结构保持的矩阵分解框架，通过依据参数梯度大小动态调整采样概率，使算法能够优先更新对当前损失函数影响显著的坐标，在理论层面减少了低效更新，在实践中显著加速了模型收敛。
本文包含五个章节：第一章阐述信息过载背景下数据稀疏性对推荐系统的制约及信息茧房现象，梳理国内外研究进展；第二章对电影评分预测问题进行数学建模并阐述 SCD 原理及批量坐标下降框架；第三章提出 QG-SCD 算法；第四章基于 MovieLens Latest Small 进行实验验证；第五章总结并展望。
推荐系统所要解决的核心问题，是如何依据已有的稀疏数据，为缺失位置预测出合理的评分估值。这一任务可被形式化地抽象为矩阵分解问题：通过将原始评分矩阵分解为低维用户偏好矩阵与物品特征矩阵的乘积，实现对未知评分的有效预测与补全。
矩阵分解的核心任务是：对给定的高维稀疏矩阵
(2.1)
对于用户
(2.2)
其中
优化目标通常定义为最小化已知元素上的重构误差，并加入正则化项以防止过拟合：
(2.3)
其中
数值示例。假设评分矩阵
(2.4)
可观测评分集合
(2.5)
以用户 1 对电影 1 的预测评分为例：
(2.6)
最终预测矩阵（示意）：
(2.7)
取
考虑优化问题
(2.10)
仅更新被选中的坐标
(2.11)
其中
采用交替迭代更新
(2.12)
当
(2.13)
参数更新规则分别为：
(2.14)
经典的 SCD"每次仅更新一个坐标"在大规模矩阵应用中面临效率瓶颈。本文提出随机批量坐标下降法（SBCD），在保持随机性的同时通过批量更新提升计算效率。设每次迭代随机选择一个坐标子集
(2.15)
应用于矩阵分解：当
(2.16)
SBCD 通过批量协同更新，每次迭代可并行更新多个高梯度坐标，显著提升了参数空间的探索效率与整体收敛速度，尤其适用于大规模稀疏矩阵分解场景，并为后续引入基于梯度幅值的非均匀采样策略奠定了优化基础。
传统矩阵分解中，隐因子矩阵
为提升推荐结果的可解释性，本文提出一种 Q 结构保持的矩阵分解方法，利用 MovieLens 数据集提供的电影类型标签，构建具有明确语义的
(3.1)
在优化过程中，$Q$ 的稀疏结构保持不变，即"$Q^{(t)}{ij}=0 \iff Q^{(0)}{ij}=0$"，只迭代初始
经典 SCD 中，$P$ 的元素
用户隐因子矩阵
(3.3)
其中梯度
电影隐因子矩阵
(3.6)
其中梯度
超参数说明：$\alpha$ 代表梯度放大指数，用于调节概率分布对梯度幅值的敏感度——$\alpha=1$ 时为线性比例；$\alpha>1$ 进一步放大梯度大的参数的采样概率；$\alpha=0$ 退化为均匀采样。$\omega$ 代表平滑常数（一个很小的正数，如
$10^{-8}$ ），用于确保当梯度为零时该坐标仍有非零概率被选中，避免某些坐标永远无法被更新，从而保证算法的收敛性。
QG-SCD 在奇数次迭代中聚焦于用户隐因子矩阵
算法 3.1 Q 结构保持与梯度幅值引导的非均匀采样随机批量坐标下降法（QG-SCD）
输入：用户-电影评分矩阵 R，电影隐因子矩阵 Q，隐因子维度 k，正则化系数 λ，
学习率 η，动量系数 γ，最大迭代次数 T，梯度放大指数 α，收敛阈值 ε，
平滑常数 ω，P 和 Q 的批量大小
输出：预测评分的矩阵 P 和 Q，损失函数历史记录 Loss_history
1. 加载用户-电影评分矩阵 R，得到用户数量 m 和电影数量 n
2. 加载电影隐因子矩阵 Q，标记可更新位置：Q_mask ← (Q ≠ 0)
3. 初始化用户隐因子矩阵 P（各元素在 (0,1) 均匀分布）
4. 初始化动量：v_P ← zeros(m,k)，v_Q ← zeros(n,k)
5. for t = 1 to T:
6. 根据公式 (2.3) 计算当前 Loss，存储在 Loss_history
7. if t > 1 and |Loss(t) − Loss(t−1)| < ε then
8. break
9. end if
10. if mod(t,2) = 1 then # 奇数次：更新 P
11. 根据公式 (2.12) 计算 P 矩阵所有坐标的梯度 g_p
12. 根据公式 (3.3) 和批量大小采样 P 矩阵中的坐标
13. 根据公式 (2.16) 和动量梯度下降法更新所选坐标：
v_P[p_uf] ← γ·v_P[p_uf] + η·g_p[p_uf]
p_uf ← p_uf − v_P[p_uf]
14. end if
15. if mod(t,2) = 0 then # 偶数次：更新 Q
16. 根据公式 (2.13) 计算 Q 矩阵非 0 坐标的梯度 g_q
17. 根据公式 (3.6) 和批量大小采样 Q 矩阵非 0 坐标
18. 根据公式 (2.16) 和动量梯度下降法更新所选坐标：
v_Q[q_if] ← γ·v_Q[q_if] + η·g_q[q_if]
q_if ← q_if − v_Q[q_if]
19. end if
20. end for
该算法的核心优势在于：通过"梯度幅值引导的非均匀采样"机制识别并优先更新梯度最大的坐标，更精准快速地降低整体损失函数，实现加速收敛；同时融入"矩阵结构保持"思想，更新
所有实验在搭载 Apple Silicon 芯片（8 核 ARM 架构 CPU、8GB 内存）的 MacBook Pro 上完成，运行 macOS 14.0。采用 Python 3.12.0，基于 NumPy 2.0.0、Pandas 2.2.2、Matplotlib 3.9.1。所有实验代码在单一 Python 进程中执行，确保可复现性与比较公平性。
数据集来源于 MovieLens 项目的 MovieLens Latest Small 版本（美国明尼苏达大学 GroupLens 研究团队维护），包含最近期的用户评分数据，数据量适中、质量较高，适合中等规模矩阵分解验证。
-
评分数据：
ratings.csv含四列（userId, movieId, rating, timestamp）。将其转换为行指标为用户编号、列指标为电影编号的矩阵$R$ ，元素$r_{ij}$ 为用户$i$ 对电影$j$ 的评分。 - 经统计，$R$ 矩阵包含 610 名用户与 9,724 部电影，矩阵稀疏度通过下式计算为 98.3%（仅约 1.7% 元素有观测值）：
(4.1)
- 由于数据极度稀缺，按 9:1 随机划分训练集与测试集（训练集样本数 90,753，测试集样本数 10,083），以确保泛化性能评估。
-
电影类型数据：
movies.csv含三列（movieId, title, genres）。转换为行指标为电影、列指标为电影类型的矩阵，若电影属于该类型则填 1，否则填 0，即得到$Q$ 矩阵。经统计$Q$ 矩阵包含 20 种电影类型（Action、Adventure、Animation…）。经检验$Q$ 矩阵是满秩阵，意味着所有类型特征维度均为有效信息，不存在冗余或可由其他类型线性组合表示的情况，保证了系数解存在且唯一，避免了共线性导致的计算不稳定，因此$Q$ 可作为后续实验的初始矩阵。
实验记录每次迭代的总运行时间：
(4.2)
采用 均方根误差（RMSE） 作为核心预测精度指标：
(4.3)
其中
为验证 QG-SCD 有效性，采用梯度放大指数对比实验作为核心评估方法：在固定其他超参数前提下，通过网格搜索在区间
实验参数设定：$k=20,\ \lambda=1,\ \eta=5\times10^{-5},\ \gamma=0.99,\ T=9000,\ \varepsilon=10^{-4},\ \omega=10^{-8}$，P 和 Q 的批量大小均为 500。特别地，$\alpha=0$ 退化为传统均匀采样坐标下降（基准参照）；$\alpha=0.5\sim1.5$ 为适度梯度放大区间；$\alpha=2\sim3$ 为强梯度放大区间。
七种
表 4.5 详列各
表 4.5 不同
| 训练 RMSE | 测试 RMSE | 最终损失 |
总时间 |
收敛效率 |
|
|---|---|---|---|---|---|
| 0.0 | 0.9664 | 1.1397 | 60972.90 | 418.0 | 439.6 |
| 0.5 | 0.7636 | 0.9753 | 44364.96 | 397.9 | 536.8 |
| 1.0 | 0.7274 | 0.9438 | 41779.97 | 395.2 | 554.1 |
| 1.5 | 0.7149 | 0.9416 | 40890.12 | 414.0 | 571.2 |
| 2.0 | 0.7106 | 0.9375 | 40618.73 | 410.9 | 575.8 |
| 2.5 | 0.7100 | 0.9372 | 40618.34 | 426.9 | 568.9 |
| 3.0 | 0.7096 | 0.9402 | 40611.02 | 428.6 | 565.4 |
收敛效率定义
$v = (L_0 - L_{\mathrm{final}})/t_{\mathrm{total}}$ ，其中初始损失$L_0 = 288987.02$ 。
总计算时间呈现先降后升趋势：当
不同
图 4.4（双轴对比）显示最佳测试 RMSE 随
取最优
表 4.6 模型预测误差分布统计
| 误差区间 | 个数 | 占比 |
|---|---|---|
| (0, 0.5] | 4597 | 46.0% |
| (0.5, 1.0] | 2921 | 29.0% |
| (1.0, 1.5] | 1470 | 15.0% |
| (1.5, 2.0] | 592 | 5.9% |
| > 2.0 | 415 | 4.1% |
误差在 (0, 0.5] 占比 46%，(0.5, 1.0] 占比 29%；若将 (0, 1] 定义为可接受范围，则可接受预测占比达 75%，表明算法在细粒度样本层面展现出稳健的预测精度。
典型坐标误差对比：坐标 (288,413) 绝对误差仅 0.02；坐标 (432,7317) 误差 1.19；坐标 (416,603) 误差高达 2.05。用户个案分析：用户 288（训练 948 条评分）测试 RMSE=0.6480；用户 432（训练 235 条）测试 RMSE=0.8723；用户 416（训练 46 条）测试 RMSE=1.1105。可见交互历史越丰富、模型捕捉偏好越准；随稀疏度升高精度下降，极端稀疏或异常偏好下仍有局限。
表 4.7 典型坐标的误差对比分析
| 坐标 | 真实值 | 预测值 | 误差 |
|---|---|---|---|
| (288, 413) | 3.0 | 3.02 | 0.02 |
| (432, 7317) | 4.5 | 3.31 | 1.19 |
| (416, 603) | 4.5 | 2.45 | 2.05 |
本文提出了一种基于矩阵分解和随机坐标下降法的协同过滤推荐算法，核心创新在于设计了一种 Q 结构保持与梯度幅值引导的非均匀采样策略。在经典矩阵分解损失函数框架下，通过对因子矩阵
相较于传统均匀采样或固定轮次坐标下降法，本文算法展现出显著优势：梯度幅值引导的非均匀采样能自适应聚焦预测误差较大的参数，使每次迭代更新方向更有效，从而在相同迭代次数下获得更快收敛速度和更低训练损失；Q 结构保持设计确保每个电影的类型种类不变、只变权重，使训练得到的
在 MovieLens Latest Small 上的实验表明：相同迭代次数下，本文算法相比均匀采样基线损失函数值降低约 30%，且收敛更平稳。随
未来研究可从多维推进：① 算法扩展性——探索面向超大规模评分矩阵的分布式实现；② 理论深化——建立非均匀采样策略与收敛速率的严格量化关系，发展自适应梯度放大机制；③ 技术融合——与图神经网络、序列模型结合捕捉兴趣演化与高阶交互，引入领域知识约束增强可解释性与可信推荐。
以下为核心函数（与仓库主程序 Q固定-非均匀采样-scd.py 一致；主程序已改为相对路径，可直接运行）。
import pandas as pd
import numpy as np
from pathlib import Path
import time
# ==================== 核心函数定义 ====================
def compute_loss_vectorized(R, P, Q, lambda_reg, R_mask):
"""向量化损失函数计算"""
R_pred = P @ Q.T
diff = (R - R_pred) * R_mask
mse_loss = 0.5 * np.sum(diff ** 2)
reg_term = (lambda_reg / 2) * (np.linalg.norm(P, 'fro') ** 2 +
np.linalg.norm(Q, 'fro') ** 2)
return mse_loss + reg_term
def compute_all_gradients_P(R, P, Q, R_mask, lambda_reg):
"""计算 P 矩阵所有元素的梯度"""
R_pred = P @ Q.T
error = (R_pred - R) * R_mask
grad_P = error @ Q + lambda_reg * P # (m, k)
return grad_P
def compute_all_gradients_Q(R, P, Q, R_mask, Q_mask, lambda_reg):
"""计算 Q 矩阵所有元素的梯度（只保留可更新位置）"""
R_pred = P @ Q.T
error = (R_pred - R) * R_mask
grad_Q = error.T @ P + lambda_reg * Q # (n, k)
grad_Q = grad_Q * Q_mask
return grad_Q
# ==================== 批量采样函数 ====================
def batch_sample_from_P(grad_P, batch_size, alpha, epsilon=1e-8):
"""从 P 矩阵中按梯度幅值非均匀采样多个坐标"""
m, k = grad_P.shape
actual_batch = min(batch_size, m * k)
weights = np.abs(grad_P) ** alpha + epsilon
probabilities = weights.flatten() / weights.flatten().sum()
flat_indices = np.random.choice(m * k, size=actual_batch, replace=False, p=probabilities)
return flat_indices // k, flat_indices % k
def batch_sample_from_Q(grad_Q, Q_nonzero_positions, batch_size, alpha, epsilon=1e-8):
"""从 Q 矩阵的非零位置中按梯度幅值非均匀采样多个坐标"""
num_nonzero = len(Q_nonzero_positions)
actual_batch = min(batch_size, num_nonzero)
gi = Q_nonzero_positions[:, 0]
gf = Q_nonzero_positions[:, 1]
weights = np.abs(grad_Q[gi, gf]) ** alpha + epsilon
probabilities = weights / weights.sum()
sel = np.random.choice(num_nonzero, size=actual_batch, replace=False, p=probabilities)
return Q_nonzero_positions[sel, 0], Q_nonzero_positions[sel, 1]主优化函数 Qsparse_preserving_bcd_nonuniform_vectorized 采用奇偶交替迭代：奇数次批量更新 v_P = γ·v_P + η·g，并施加非负约束），偶数次批量更新 |Loss(t)-Loss(t-1)|<ε 提前收敛。完整实现见 Q固定-非均匀采样-scd.py。
[1] Koren Y, Bell R, Volinsky C. Matrix Factorization Techniques for Recommender Systems[J]. Computer, 2009, 42(8): 30-37. [2] Herbert R, Sutton M. A Stochastic Approximation Method[J]. The Annals of Mathematical Statistics, 1951, 22(3): 400-407. [3] Meng X, Bradley J, Yavuz B, et al. MLlib: Machine Learning in Apache Spark[J]. Journal of Machine Learning Research, 2015, 17(1): 1235-1241. [4] Nesterov Y. Efficiency of Coordinate Descent Methods on Huge-scale Optimization Problems[J]. SIAM Journal on Optimization, 2012, 22(2): 341-362. [5] Luo X, Zhou M C, Xia Y N, et al. Generating Highly Accurate Predictions for Missing QoS Data Via Aggregating Nonnegative Latent Factor Models[J]. IEEE Transactions on Neural Networks and Learning Systems, 2015, 27(3): 524-537. [6] Salakhutdinov R, Mnih A. Probabilistic Matrix Factorization[C]. Curran Associates Inc. 2007: 1257-1264. [7] Hu Y, Koren Y, Volinsky C. Collaborative Filtering for Implicit Feedback Datasets[C]. Eighth IEEE International Conference on Data Mining. IEEE, 2009. [8] 宋威, 李雪松. 基于标签自适应选择的矩阵分解推荐算法[J]. 计算机工程与科学, 2018, 40(10): 1731-1736. [9] 陈晔, 刘志强. 基于 LFM 矩阵分解的推荐算法优化研究[J]. 计算机工程与应用, 2019, 55(02): 116-120+167. [10] 高子建, 张晗睿, 窦万春, 等. 基于谱聚类和隐语义模型的智能协同推荐方法[J]. 计算机集成制造系统, 2021, 27(09): 2517-2524. [11] Rendle S. Factorization Machines[C]. 2010 IEEE International Conference on Data Mining. IEEE, 2010: 995-1000. [12] He X, Liao L, Zhang H, et al. Neural Collaborative Filtering[C]. Proceedings of the 26th International Conference on World Wide Web. 2017: 173-182. [13] Guo H, Tang R, Ye Y, et al. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction[C]. IJCAI 2017. [14] 陈平华, 朱禹. 融合知识图谱表示学习和矩阵分解的推荐算法[J]. 计算机工程与设计, 2018, 39(10): 3137-3142. [15] Peter R, Martin T. Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function[J]. Mathematical Programming, 2014, 144(1-2): 1-38. [16] Ene A, Nguyen H L. Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions[J]. Eprint Arxiv, 2015: 2208-2216. [17] Zhou Y, Wilkinson D M, Schreiber R, et al. Large-Scale Parallel Collaborative Filtering for the Netflix Prize[J]. Springer, 2008: 337-348. [18] 赵磊, 陈玎, 朱道立. 求解大规模 SCAD 回归问题的随机坐标下降算法研究[J]. 上海管理科学, 2019, 41(05): 97-103. [19] 徐宇淼, 徐文静, 胡清洁. 求解 L1 正则化 L2 损失支持向量机问题的多层随机坐标下降算法[J]. 桂林电子科技大学学报, 2022, 42(02): 143-147. [20] 谢亚君. 求解大型最小二乘问题的混合贪婪随机坐标下降法[J]. 计算数学, 2023, 45(02): 230-239. [21] Kemal B, Karsavuran M O, Aykanat C. Stochastic Gradient Descent for matrix completion: Hybrid parallelization on shared- and distributed-memory systems[J]. Knowledge-Based Systems, 2024, 283: 12.
QG-SCD-Matrix-Factorization/
├── Q固定-非均匀采样-scd.py # 主程序：完整 QG-SCD 训练流程
├── code/ # 数据预处理脚本
│ ├── movies标签矩阵.py # 由 movies.csv 生成类型 one-hot 矩阵
│ ├── 用户-电影_评分矩阵.py # 由 ratings.csv 生成 user-movie 评分矩阵
│ └── 筛选电影及类型.py # 根据评分矩阵筛选出对应的类型矩阵
├── data/
│ └── ml-latest-small/ # MovieLens Latest Small 数据集
│ ├── README.txt # 官方数据说明
│ ├── movies.csv # 电影元数据
│ ├── ratings.csv # 评分原始数据
│ ├── user-movie_matrix.csv # 610×9724 评分矩阵（主程序输入）
│ ├── movie_genres_matrix.csv # 电影类型矩阵（主程序输入）
│ └── ... # 其他预处理产物
├── figures/ # 论文实验图
│ ├── fig_alpha_comparison.png # 不同 α 的收敛速度对比
│ ├── fig_qsparse_alpha_comparison.png # Q 稀疏保持下不同 α 对比
│ ├── fig_qsparse_alpha_multi.png # 多 α 详细对比
│ ├── fig_P287_Q48_analysis.png # P287/Q48 参数分析
│ ├── fig_test_rmse_comparison.png # 不同 α 最佳测试 RMSE 对比
│ └── fig_train_rmse_comparison.png # 不同 α 训练 RMSE 对比
├── README.md
└── LICENSE
- Python 3.12
- NumPy 2.0
- Pandas 2.2.2
- Matplotlib 3.9.1
pip install numpy==2.0 pandas==2.2.2 matplotlib==3.9.1仓库已配置为相对路径，直接运行主程序即可：
python "Q固定-非均匀采样-scd.py"主程序会自动读取 data/ml-latest-small/user-movie_matrix.csv 和 data/ml-latest-small/movie_genres_matrix.csv。
如果你想从原始 MovieLens 文件重新生成输入矩阵，依次运行：
cd code
python "movies标签矩阵.py" # movies.csv → movies_with_genres_matrix.csv
python "用户-电影_评分矩阵.py" # ratings.csv → user-movie_matrix.csv
python "筛选电影及类型.py" # 生成 movie_genres_matrix.csv
$\alpha=2.5$ 与$\alpha=3$ 的曲线下降最快，非均匀采样有效减少了低梯度坐标的无效更新（对应论文图 4.1）。
训练 RMSE 随 α 增大先快速下降后在 α≈2.5 达到最小 0.7099，呈现明显边际效益递减（对应论文图 4.3）。
$\alpha=2.5$ 时取得最优泛化（最佳测试 RMSE≈0.9374），且仅需 7539 次迭代即达到最优（对应论文图 4.4）。
