一种基于联合聚类的矩阵分解推荐方法

摘要

本发明公开了一种基于联合聚类的矩阵分解推荐方法，包括：1构造用户‑项目评分矩阵；2用户‑项目评分矩阵通过联合聚类分成若干个类别；3针对聚类后的类别，利用概率矩阵分解的方法对每个类别的未知评分并行地进行预测并根据预测的评分进行推荐。本发明能够充分利用聚类内部间的紧密相关性和概率矩阵分解算法的高精度，对于信息过载时代的大数据处理问题，能够在保证不错精度的同时以较快的速度进行推荐。

说明书

技术领域

本发明涉及个性化推荐领域，具体的说是一种基于联合聚类的矩阵分解推荐方法。

背景技术

随着网络技术的发展,使得用户在海量信息中失去方向，很难从中选出自己真正需要的信息，反而让信息的使用效率降低了，这就是所谓的信息过载问题。为解决信息过载问题，推荐系统应运而生。推荐系统是根据用户的信息需求，为用户推荐感兴趣物品的过程，这是一种个性化推荐过程。个性化推荐系统定位于目标用户的兴趣，不需要用户输入关键词，从用户先前的一些行为，比如浏览记录、加入购物车情况以及购买记录等，来主动推荐一些用户可能感兴趣的东西，帮助用户在信息的海洋中自由遨游。

目前存在的推荐算法中，协同过滤算法是各大电商应用最广泛的算法之一。协同过滤算法通过对用户历史行为数据的挖掘发现用户的偏好，从而推荐相似的商品。虽然该类算法能保持很好的精度，但还是存在时间复杂度较高的问题。

目前存在的协同过滤算法已经可以让推荐精度达到较高的水平，但是想在此基础上进行时间效率的提高，对目前存在的推荐算法而言仍是待解决的问题。所以，如何在保持较高精度的前提下，提高协同过滤算法的时间效率已经是个大问题。

发明内容

本发明是为了解决现有协同过滤算法的时效较低问题，提出的一种基于联合聚类的矩阵分解推荐方法，以期能够充分利用聚类内部间的紧密相关性和概率矩阵分解算法的高精度，对于信息过载时代的大数据处理问题，能够在保证不错精度的同时以较快的速度进行推荐。

本发明为解决技术问题采用如下技术方案：

本发明一种基于联合聚类的矩阵分解推荐方法的特点按如下步骤进行：

步骤1、构造用户-项目评分矩阵R

令U表示用户集，且U＝{u₁,u₂,...,u_i,...,u_M}，u_i表示第i个用户，1≤i≤M，M表示用户总数；令V表示项目集，且V＝{v₁,v₂,...,v_j,...,v_N}，v_j表示第j个项目，1≤j≤N，N表示项目总数；令r_ij表示第i个用户u_i对第j个项目v_j的评分值，则用户-项目评分矩阵为R＝{r_ij}_M×N；

步骤2、用户-项目评分矩阵R通过联合聚类分成若干个类别

步骤2.1、设定类别总数为K，随机初始化第i个用户u_i对第j个项目v_j的评分值r_ij属于第k个类别C_k的概率p(k|u_i,v_j,r_ij)，设定迭代阈值为τ_max，当前迭代次数为τ，并初始化τ＝1；

步骤2.2、利用式(1)、式(2)、式(3)分别计算第τ次迭代时第i个用户u_i属于第k个类别C_k的概率(p(k|u_i))^τ，第τ次迭代时第j个项目v_j属于第k个类别C_k的概率(p(k|v_j))^τ，第τ次迭代时第k个类别C_k中出现评分值r_ij的概率(p(r_ij|k))^τ：

式(1)中，V(u_i)表示第i个用户u_i评过分的所有项目集合，假设项目集合V(u_i)中的项目个数为A，则v_f表示项目集合V(u_i)中的第f个项目，且f∈{1，2,...,A}，r_if表示第i个用户u_i对第f个项目v_f的评分值，(p(k|u_i,v_f,r_if))^τ表示第τ次迭代时第i个用户u_i对第f个项目v_f的评分r_if属于第k个类别C_k的概率；

式(2)中，U(v_j)表示给第j个项目v_j评过分的所有用户的集合，假设用户集合U(v_j)中的用户个数为B，则u_q表示用户集合U(v_j)中的第q个用户，且q∈{1，2,...,B},r_qj表示第q个用户u_q对第j个项目v_j的评分值，(p(k|u_q,v_j,r_qj))^τ表示第τ次迭代时第q个用户u_q对第j个项目v_j的评分值r_qj属于第k个类别C_k的概率；

式(3)中，r_qf表示第q个用户u_q对第f个项目v_f的评分值，(p(k|u_q,v_f,r_qf))^τ表示第τ次迭代时第q个用户u_q对第f个项目v_f的评分值r_qf属于第k个类别C_k的概率；

步骤2.3、利用式(4)计算第τ次迭代的第i个用户u_i对第j个项目v_j的评分r_ij属于第k个类别C_k的概率(p(k|u_i,v_j,r_ij))^τ：

式(4)中，a，b，c是为了防止分母为零而设置的超参数；

步骤2.4、将τ+1赋值给τ，并判断τ≤τ_max是否成立，若成立，则返回步骤2.2执行；否则，表示获得最终的第i个用户u_i对第j个项目v_j的评分r_ij属于第k个类别C_k的概率p(k|u_i,v_j,r_ij)；

步骤2.5、重复步骤2.2-步骤2.4，从而获得最终的第i个用户u_i对第j个项目v_j的评分r_ij属于K个类别的概率，并将第i个用户u_i、第j个项目v_j及其评分r_ij划分到概率最大的类别中；

步骤2.6、重复步骤2.2-步骤2.5，从而将所有用户、所有项目及其评分划分到概率最大的类别中，进而将用户集U、项目集V以及用户-项目评分矩阵R划分成K个类别，其中，K个类别中存在有空集；

步骤3、利用概率矩阵分解的方法对第k个类别C_k中的未知评分进行预测和推荐；

步骤3.1、计算相似度

根据余弦相似度计算出用户与用户间的相似度矩阵，令s(u_i,u_e)表示第i个用户u_i与第e个用户u_e间的相似度，并有1≤i≤M，1≤e≤M，则用户相似度矩阵记为S＝{s(u_i,u_e)}_M×M；同理计算出项目与项目间的相似度矩阵，令z(v_j,v_p)表示第j个项目v_j与第p个项目v_p间的相似度，并有1≤j≤N，1≤p≤N，则项目相似度矩阵记为Z＝{z(v_j,v_p)}_N×N；

步骤3.2、分别根据式(5)和式(6)计算第k个类别C_k中第i个用户u_i的特征向量和第k个类别C_k中第j个项目v_j的特征向量

式(5)中，J表示单位向量；表示第k个类别C_k中第i个用户u_i的特征向量所服从正态分布的方差；

式(6)中，表示第k个类别C_k中第j个项目v_j的特征向量所服从正态分布的方差；

步骤3.3、根据式(7)计算第k个类别C_k的先验分布p(R^k|Q^k,L^k,σ²)：

式(7)中，R^k表示第k个类别C_k中的评分矩阵；L^k表示第k个类别C_k中所有项目的特征向量所构成的项目特征矩阵；Q^k表示第k个类别C_k中所有用户的特征向量所构成的用户特征矩阵；σ²为第k个类别C_k中的评分矩阵R^k所服从正态分布的方差，表示第k个类别C_k中第i个用户对第j个项目的评分；ω_ij为指标函数，当第i个用户u_i评论过第j个项目v_j时，ω_ij＝1，否则ω_ij＝0；表示第k个类别中的第i个用户对第j个项目的评分服从均值为方差为σ²的正态分布；

步骤3.4、建立如式(8)所示的误差平方和目标函数E^k：

式(8)中，x^k表示第k个类别C_k共有的用户总数；y^k表示第k个类别C_k共有的项目总数；λ_Q表示第e个用户u_e对第i个用户u_i在目标函数上的影响因子，λ_L表示第p个项目v_p对第j个项目v_j在目标函数上的影响因子，且有F表示Frobenius范数；

步骤3.4、设定迭代阈值μ_max，当前迭代次数为μ，并初始化μ＝1；

步骤3.5、随机初始化用户特征矩阵Q^k和项目特征矩阵L^k作为第μ-1次迭代的初始用户特征矩阵(Q^k)^μ-1和项目特征矩阵(L^k)^μ-1：

步骤3.6、利用式(9)和式(10)分别获得第μ次迭代的第k个类别C_k中第i个用户u_i的特征向量和第k个类别C_k中第j个项目v_j的特征向量

式(9)中，表示第k个类别C_k中第i个用户u_i的特征向量的正则化项，并且服从均值为零，方差为的正态分布；

式(10)中，表示第k个类别C_k中第j个项目v_j的特征向量的正则化项，并且服从均值为零，方差为的正态分布；

步骤3.7、利用式(11)和式(12)分别获得第μ次迭代的第i个用户u_i的特征向量的梯度以及第μ次迭代的第j个项目v_j的特征向量的梯度

步骤3.8、将μ+1赋值给μ，并判断μ≤μ_max是否成立，若成立，则重复步骤3.6执行；否则，表示获得最终的第k个类别C_k中的第i个用户u_i的特征向量以及第k个类别C_k中的第j个项目v_j的特征向量从而获得第k个类别C_k中的所有用户最终的用户特征矩阵Q^k和第k个类别C_k中的所有项目最终的项目特征矩阵L^k；

步骤3.9、利用式(13)获得第k个类别C_k的预测评分矩阵R^k，从而得到K个类别预测评分矩阵：

R^k＝(Q^k)^TL^k>

步骤3.10、根据K个类别预测评分矩阵，将满足评分要求的项目推荐给相应用户。

与已有技术相比，本发明有益效果体现在：

1、本发明通过在协同过滤算法的预处理中加入联合聚类算法，解决了协同过滤算法存在时效低的问题，有效减小了近邻查询空间，明显降低了计算维度。同时，利用各个类别内部的紧密相连性，保持了较高的精度。

2、本发明利用类别间差别大、互不相关的特点，在评分预测阶段利用了并行计算来对各个类别同时进行评分预测。实验证明这种处理极大地加速了预测的处理进程，彻底解决了时效较低的问题。

3、本发明在步骤2.3利用用户所属类别的概率、项目所属类别的概率以及类别中包含某个评分的概率这三者之间的关系来计算用户、项目和评分共同属于某个类别的概率，这样保证了聚类过程中的可靠性，从而减小了对后续评分预测阶段精度的影响。

4、本发明在步骤3.6加入了用户与用户邻居间及项目与项目邻居间的相似度关系，使得用户与其邻居群具有相似的行为方式，项目与其邻居群具有相似的特征，充分利用这样的邻居关系来保证较高的推荐精度。

具体实施方式

本实施例中，一种基于联合聚类的矩阵分解推荐方法是按如下步骤进行：

步骤1、构造用户-项目评分矩阵R

令U表示用户集，且U＝{u₁,u₂,...,u_i,...,u_M}，u_i表示第i个用户，1≤i≤M，M表示用户总数；令V表示项目集，且V＝{v₁,v₂,...,v_j,...,v_N}，v_j表示第j个项目，1≤j≤N，N表示项目总数；令r_ij表示第i个用户u_i对第j个项目v_j的评分值，则用户-项目评分矩阵为R＝{r_ij}_M×N；

步骤2、用户-项目评分矩阵R通过联合聚类分成若干个类别

步骤2.1、设定类别总数为K，随机初始化第i个用户u_i对第j个项目v_j的评分值r_ij属于第k个类别C_k的概率p(k|u_i,v_j,r_ij)，且第i个用户u_i对第j个项目v_j的评分值r_ij属于K个类别的概率总合归一化为1，设定迭代阈值为τ_max＝20，当前迭代次数为τ，并初始化τ＝1；

步骤2.2、利用式(1)、式(2)、式(3)分别计算第τ次迭代时第i个用户u_i属于第k个类别C_k的概率(p(k|u_i))^τ，第τ次迭代时第j个项目v_j属于第k个类别C_k的概率(p(k|v_j))^τ，第τ次迭代时第k个类别C_k中出现评分值r_ij的概率(p(r_ij|k))^τ：

式(1)中，V(u_i)表示第i个用户u_i评过分的所有项目集合，假设项目集合V(u_i)中的项目个数为A，则v_f表示项目集合V(u_i)中的第f个项目，且f∈{1，2,...,A}，r_if表示第i个用户u_i对第f个项目v_f的评分值，(p(k|u_i,v_f,r_if))^τ表示第τ次迭代时第i个用户u_i对第f个项目v_f的评分r_if属于第k个类别C_k的概率；

式(2)中，U(v_j)表示给第j个项目v_j评过分的所有用户的集合，假设用户集合U(v_j)中的用户个数为B，则u_q表示用户集合U(v_j)中的第q个用户，且q∈{1，2,...,B},r_qj表示第q个用户u_q对第j个项目v_j的评分值，(p(k|u_q,v_j,r_qj))^τ表示第τ次迭代时第q个用户u_q对第j个项目v_j的评分值r_qj属于第k个类别C_k的概率；

式(3)中，r_qf表示第q个用户u_q对第f个项目v_f的评分值，(p(k|u_q,v_f,r_qf))^τ表示第τ次迭代时第q个用户u_q对第f个项目v_f的评分值r_qf属于第k个类别C_k的概率；

步骤2.3、利用式(4)计算第τ次迭代的第i个用户u_i对第j个项目v_j的评分r_ij属于第k个类别C_k的概率(p(k|u_i,v_j,r_ij))^τ：

式(4)中，a，b，c是为了防止分母为零而设置的超参数，可根据具体环境设定，这里统一指定为1.0E-7；

步骤2.4、将τ+1赋值给τ，并判断τ≤τ_max是否成立，若成立，则返回步骤2.2执行；否则，表示获得最终的第i个用户u_i对第j个项目v_j的评分r_ij属于第k个类别C_k的概率p(k|u_i,v_j,r_ij)；

步骤2.5、重复步骤2.2-步骤2.4，从而获得最终的第i个用户u_i对第j个项目v_j的评分r_ij属于K个类别的概率，并将第i个用户u_i、第j个项目v_j及其评分r_ij划分到概率最大的类别中；

步骤2.6、重复步骤2.2-步骤2.5，从而将所有用户、所有项目及其评分划分到概率最大的类别中，进而将用户集U、项目集V以及用户-项目评分矩阵R划分成K个类别中，其中，K个类别中存在有空集；

步骤3、利用概率矩阵分解的方法对第k个类别C_k中的未知评分进行预测和推荐；

步骤3.1、计算相似度

根据余弦相似度计算出用户与用户间的相似度矩阵，令s(u_i,u_e)表示第i个用户u_i与第e个用户u_e间的相似度，并有1≤i≤M，1≤e≤M，则用户相似度矩阵记为S＝{s(u_i,u_e)}_M×M；同理计算出项目与项目间的相似度矩阵，令z(v_j,v_p)表示第j个项目v_j与第p个项目v_p间的相似度，并有1≤j≤N，1≤p≤N，则项目相似度矩阵记为Z＝{z(v_j,v_p)}_N×N；

步骤3.2、分别根据式(5)和式(6)计算第k个类别C_k中第i个用户u_i的特征向量和第k个类别C_k中第j个项目v_j的特征向量

式(5)中，J表示单位向量；表示第k个类别C_k中第i个用户u_i的特征向量所服从正态分布的方差；

式(6)中，表示第k个类别C_k中第j个项目v_j的特征向量所服从正态分布的方差；

步骤3.3、根据式(7)计算第k个类别C_k的先验分布p(R^k|Q^k,L^k,σ²)：

式(7)中，R^k表示第k个类别C_k中的评分矩阵；L^k表示第k个类别C_k中所有项目的特征向量所构成的项目特征矩阵；Q^k表示第k个类别C_k中所有用户的特征向量所构成的用户特征矩阵；σ²为第k个类别C_k中的评分矩阵R^k所服从正态分布的方差，表示第k个类别C_k中第i个用户对第j个项目的评分；ω_ij为指标函数，当第i个用户u_i评论过第j个项目v_j时，ω_ij＝1，否则ω_ij＝0；表示第k个类别中的第i个用户对第j个项目的评分服从均值为方差为σ²的正态分布；

步骤3.4、建立如式(8)所示的误差平方和目标函数E^k：

式(8)中，x^k表示第k个类别C_k共有的用户总数；y^k表示第k个类别C_k共有的项目总数；λ_Q表示第e个用户u_e对第i个用户u_i在目标函数上的影响因子，λ_L表示第p个项目v_p对第j个项目v_j在目标函数上的影响因子，并有F表示Frobenius范数；

步骤3.4、设定迭代阈值μ_max＝800，当前迭代次数为μ，并初始化μ＝1；

步骤3.5、利用均值为0，方差为的正态分布随机初始化用户特征矩阵Q^k和均值为0，方差为的正态分布随机初始化项目特征矩阵L^k作为第μ-1次迭代的初始用户特征矩阵(Q^k)^μ-1和项目特征矩阵(L^k)^μ-1：

步骤3.6、利用式(9)和式(10)分别获得第μ次迭代的第k个类别C_k中第i个用户u_i的特征向量和第k个类别C_k中第j个项目v_j的特征向量

式(9)中，表示第k个类别C_k中第i个用户u_i的特征向量的正则化项，并且服从均值为零，方差为的正态分布；

式(10)中，表示第k个类别C_k中第j个项目v_j的特征向量的正则化项，并且服从均值为零，方差为的正态分布；

步骤3.7、为了使误差平方和目标函数最小化，利用式(11)和式(12)分别获得第μ次迭代的第i个用户u_i的特征向量的梯度以及第μ次迭代的第j个项目v_j的特征向量的梯度

步骤3.8、将μ+1赋值给μ，并判断μ≤μ_max是否成立，若成立，则重复步骤3.6执行；否则，表示获得最终的第k个类别C_k中的第i个用户u_i的特征向量以及第k个类别C_k中的第j个项目v_j的特征向量从而获得第k个类别C_k中的所有用户最终的用户特征矩阵Q^k和第k个类别C_k中的所有项目最终的项目特征矩阵L^k；

步骤3.9、利用式(13)获得第k个类别C_k的预测评分矩阵R^k，从而得到K个类别预测评分矩阵：

R^k＝(Q^k)^TL^k>

步骤3.10、根据K个类别预测评分矩阵，将满足评分要求的项目推荐给相应用户。

实施例：

为了验证本专利中方法的效果，首先搭建实验的运行环境为：Intel Core i5CPU，3.00GHZ主频，Windows10系统，12G内存。本文选用了推荐系统中常用的MovieLens 10M数据集，对数据集中的每个标签而言，少于5个不同的用户和电影就将其删除；对于每个不同的用户和电影，少于5个不同的标签也被删除。

本文采用均方根误差(RMSE)作为评价标准。

本文选用了四种方法来和本文提出的方法进行效果的对比，分别是概率矩阵分解(PMF)、基于标签的概率矩阵分解(NHPMF)、联合聚类算法(Co-Clustering)和Co-Clustering+PMF四种。具体地，根据实验结果可得出结果如表1所示：

表1不同特征向量维度D下的RMSE值

从表1中各类方法在不同特征维度下的RMSE值的比较可以看出，本文提出的方法基于联合聚类矩阵分解的推荐系统加速方法MFCC能保持不错的精度。

表2迭代一次运行时间比较结果(秒)

从表2中的结果可以看出各个方法迭代一次所用的时间对比情况，MFCC的时间效率是最高的，从而证明了本文提出方法的可行性。