1.5 基于模型的协同过滤推荐算法
基于模型的协同过滤一般分为聚类模型、分类模型和矩阵分解模型等。本书主要研究其中的矩阵分解模型及其与社交网络的信任相结合的算法。
1.5.1 矩阵分解模型
推荐系统中的隐语义模型，它和Topic Model潜在的影响因素一样，最初是在文本挖掘领域中提出来的。例如，在推荐系统中它能够基于用户的行为对用户和项目进行自动分析，也就是把用户和项目划分到不同主题，这些主题可以理解为用户的兴趣和项目属性，其中的典型代表是矩阵分解模型。
传统的矩阵分解模型有奇异值分解（Sigular Value Decomposition, SVD）、概率矩阵分解（Probabilistic Matrix Factorization, PMF）和非负矩阵分解（Non-negative Matrix Factorization, NMF）等。文献[8]提出了概率矩阵分解模型，该模型从概率生成过程角度描述矩阵分解过程，有效缓解了数据稀疏性问题；文献[9]提出了基于邻域相似度的矩阵分解模型，该模型考虑了用户兴趣相似度，进一步挖掘评分矩阵的有效信息，提高推荐精度。近年来，随着使用社交平台和社交网络的用户数量增多，依赖性增强，社交信息为协同过滤推荐算法带来了新的数据源，如好友推荐和信任用户推荐均有效促进了用户的消费行为，因为在现实生活中相对于品牌、价格和销量等参考标准，用户更倾向于信任好友的推荐。文献[11]通过调查得出相对于系统给出的推荐，用户更喜欢来自友人的推荐；文献[12]则表明大部分网站通过邀请用户和粉丝来作决策。鉴于此，大量研究人员开始运用社交信息来改进推荐算法。
概率矩阵分解模型在传统矩阵分解的基础上引入了概率的思想，假设用户和项目的隐语义空间都服从高斯分布，同时预测评分和真实评分的误差也服从高斯分布，这样用户对项目的预测评分就是一系列的概率组合问题，然后根据最大似然估计最大化后验概率。
2008年Salakhutdinov和Mnih等人提出概率矩阵分解算法，该算法从概率的角度来预测用户的评分，假设用户潜在因子矩阵和项目潜在因子矩阵均服从均值为0的球形高斯先验分布，在此假设的基础上，结合概率论和矩阵论的相关理论来预测用户对项目的偏好。2013年，涂丹丹等将Ma等提出的联合概率矩阵分解并被应用到计算广告，该算法的主要思想是在用户的上下文环境约束下对用户项目评分矩阵进行分解。2015年刁海伦融合用户项目评分矩阵信息和社交网络中显式的信任关系提出一种改进的联合概率矩阵分解模型，同时结合隐式的社交网络关系做进一步的研究，实验结果表明改进的算法在数据稀疏情况下推荐精度较高，而且对于用户冷启动问题也有一定的缓解作用。2016年Hernando等人将非负矩阵分解模型应用在传统的贝叶斯概率矩阵分解模型之中，使得算法具有良好的可解释性。
概率矩阵分解算法通过优化预先设定的目标函数从而得到近似全局最优解，推荐精度较高，同时具有坚实的理论基础，能较好地应用于实践之中。但是海量数据情况下，由于用户和购买项目数量之间的关系服从幂律分布，用户少，项目多，造成数据集极度稀疏，而且由于算法不能充分挖掘用户与项目之间的关系，导致推荐精度急剧下降。
矩阵分解模型假设用户对项目的评分受到若干潜在因子的影响，将用户和项目映射到一个共同的潜在因子空间。和Topic Model不同的是，该类算法到底受哪种因素的影响却很难确定，正是囿于此种缺陷，一般又将矩阵分解模型称为隐语义模型，该模型最早由Koren于2009年提出。
传统的矩阵分解模型往往将固有的用户项目评分矩阵RNM分解为两个低秩矩阵的乘积，以达到对矩阵中缺失值的预测目的，如式（1-8）所示：
其中，k≪min（M，N），指的是潜在因子的数量；UkM和VkN为由分解得到的两个低秩矩阵，可以看作是用户潜在因子矩阵和项目潜在因子矩阵，往往通过迭代训练来使得UkM和VkN的内积不断逼近原始的用户项目评分矩阵，同时得到UkM和VkN后还可以对用户没有评分的项目进行评分预测。
基于矩阵分解的算法是一种学习型算法，实际中往往采用随机梯度下降（Stochastic Gradient Descent, SGD）来优化预先设定的目标函数从而得到全局最优解，而且由于潜在因子的数量k≪min（M，N），算法的离线计算的空间复杂度低，这在当今大数据的环境下具有很强的实用价值；同时，由于该算法有一个全局的目标函数，使得算法的预测准确率高。
1.5.2 交替最小二乘
理论研究表明交替最小二乘（Alternating Least Squares, ALS）随着迭代的进行误差会逐步降低直至收敛，ALS完全不能保证将会收敛至全局最优解，而且在实际应用中，ALS对初始点选取较为敏感，不恰当的选择会导致数据振荡地收敛到局部最优解。
首先按高斯分布初始化用户和项目的潜在因子向量U和V。
然后固定V，将损失函数对V求偏导，并令导数等于0，得到新的用户潜在因子向量U，如式（1-9）所示：
其次固定U，将损失函数对U求偏导，并令导数等于0，如式（1-10）所示：
式中，λ——正则化系数，需要实验确定。
最后便可利用得到的用户项目潜在因子空间U和V进行评分预测。
1.5.3 概率矩阵分解
概率矩阵分解是矩阵分解模型中的典型代表。图1-2是概率矩阵分解的概率图模型。
图1-2 概率矩阵分解的概率图模型
概率矩阵分解的基本思想是在矩阵分解的基础上引入概率的思想，假设用户和商品的特征向量矩阵都符合高斯分布，如式（1-11）所示：
根据上述考量，可以结合概率论和矩阵分解的相关知识预测用户对项目的喜好程度，如式（1-12）所示。
式中，N（x|μ，σ2）——期望为μ、方差为σ的高斯分布；
I——一个指示矩阵，当且仅当Iij=1表示用户i选择了项目j，否则为0。
利用贝叶斯推导，可得用户和物品隐式特征的后验概率，如式（1-13）所示。
对上述预测公式取对数，如式（1-14）所示。
式中，C——一个不依赖于模型超参数的常量。
最大化U和V的后验概率等于最小化式（1-15）。
式中，Fro——F范数；
λU和λV——正则化系数，防止过拟合。
然后利用SGD来训练，如式（1-16）所示。
式中，η——SGD的学习速率。
概率矩阵分解模型能较好地适应大规模数据集（与其他矩阵分解算法比较），时间复杂度随观测数据量的增长呈线性增长；同时，实验结果表明，在数据非常稀疏的情况下有更好的预测性能。
1.5.4 非负矩阵分解
非负矩阵分解是把一个矩阵分解成两个矩阵乘积的形式，以此来分解多维数据。
对于现代化推荐系统，需要处理的数据量非常庞大，在现有矩阵分解的基础上Lin提出了一种时间复杂度比较低的NMF算法。该算法利用每一个已知评分项更新分解后的用户－隐因子矩阵Pm×k和项目－隐因子矩阵Qk×n。在Lin算法的基础上，为了防止分解后的矩阵出现过拟合，加入正则项的乘性迭代，如式（1-17）所示。
式中：Iu——评分不为零的项目集合；
Ui——评分不为零的用户集合；
ru，i——用户u对项目i的实际评分；
——预测的用户u对i的评分，其可以由初始化的用户－隐因子矩阵Pm×k和项目－隐因子矩阵Qk×n计算得到。