基于联合聚类和矩阵分解的协同过滤算法研究

第３３卷第２期　２０１４年６月　武汉轻工大学学报　Ｖ０１．３３Ｎｏ．２　Ｊｏｕｒｎａｌ　ｏｆ　Ｗｕｈａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖｅｒｓｉｔｙ　Ｊｕｎ．２０１４　文章编号：２０９５－７３８６（２０１４）０２－００６０－０４　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．２０９５－７３８６．２０１４．０２．０１５　基于联合聚类和矩阵分解的协同过滤算法研究　赵广艳，李禹生，韩昊　（武汉轻工大学数学与计算机学院，湖北武汉４３００２３）　摘要：提出了基于联合聚类和带正则化的迭代最小二乘法的协同过滤算法。该算法对原始　矩阵进行用户一项目两个维度的联合聚类生成若干子矩阵，子矩阵的规模远小于原始评分矩　阵，可有效降低预测阶段计算量，而且也缓解了数据稀疏性问题。在子矩阵中通过对传统的矩　阵分解进行正则化约束来防止模型过拟合现象，并采用迭代最小二乘法进行训练分解模型，可　有效缓解可扩展性。实验表明，该方法具有高效性。　关键词：协同过滤；联合聚类；稀疏性；最小二乘法；评分预测　中图分类号：ＴＰ　３９１．４　文献标识码：Ａ　Ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｃｏ－ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ｍａｔｒｉｘ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ＺＨＡＯ　Ｇｕａｎｇ．ｙａｎ，ＬＩ　Ｙｕ－ｓｈｅｎｇ，ＨＡＮ　Ｈａｏ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｗｕｈａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００２３，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｃｏ—ｃｌｕｓｔｅｒｉｎｇ　ａｎｄ　ａｌｔｅｒｎａｔｉｎｇ—ｌｅａｓｔ－ｓｑｕａｒｅｓ　ｗｉｔｈ　ｗｅｉｇｈｔｅｄ－ｒｅｇｕｌａｒｉｚａｔｉｏｎ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｄｉｖｉｄｅｓ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ｍａｔｉｒｘ　ｉｎｔｏ　ｓｅｖｅｒａｌ　ｓｕｂ—ｍａｔｒｉｘ，ａｎｄ　ｔｈｅ　ｓｕｂ－ｍａｔｉｒｘ　ｉｓ　ｍｕｃｈ　ｓｍａｌｌｅｒ　ｔｈａｎ　ｔｈｅ　ｓｉｚｅ　ｏｆ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ｓｃｏｒｉｎｇ　ｍａｔｉｒｘ，ｗｈｉｃｈ　ｎｏｔ　ｏｎｌｙ　ｒｅｄｕｃｅｓ　ｔｈｅ　ａｍｏｕｎｔ　ｏｆ　ｃｏｍｐｕｔａｔｉｏｎ，ｂｕｔ　ｌｓｏ　ａａｌｌｅｖｉａｔｅｓ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｄａｔａ　ｓｐａｒｓｉｔｙ．Ｉｎ　ｔｈｅ　ｓｕｂ—ｍａｔｉｒｘ　ｂｙ　ｕｓｉｎｇ　ｒｅｇｕｌａｒｉｚａｔｉｏｎ　ｃｏｎｓｔｒａｉｎｔ　ｔｏ　ｐｒｅｖｅｎｔ　ｍｏｄｅｌ　ｆｒｏｍ　ｏｖｅｒ　ｆｉｔｔｉｎｇ　ａｎｄ　ｂｙ　ｕｓｉｎｇ　ｌｅａｓｔ—ｓｑｕａｒｅｓ　ｍｅｔｈｏｄ　ｔｏ　ｔｒａｉｎ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｍｏｄｅｌ，ｔｈｅ　ｓｅａｌａｂｉｌｉｔｙ　ｃａｎ　ｂｅ　ｅｆｆｅｃｔｉｖｅｌｙ　ｌｌｅｖｉａｔｅｄ．Ｔｈｅ　ｅｘｐｅｒａｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｉｓ　ｅｆｆｉｃｉｅｎｔ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ；ＣＯ—ｃｌｕｓｔｅｒｉｎｇ；ｓｐａｒｓｉｔｙ；ｌｅａｓｔ　ｓｑｕａｒｅｓ；ｓｃｏｒｅ　ｐｒｅｄｉｃｔｓ　协同过滤个性化推荐是电子商务个性化推荐中　应用最多的技术之一。近年来，国内外学者对协同　过滤算法做了大量研究工作，并取得了丰硕成果，许　数据稀疏性，算法的可扩展性。由于算法的计算量　大，导致算法的性能急剧下降。基于用户聚类的协　同过滤推荐算法…，与传统的协同过滤算法相比，　提高了推荐速度和质量，但是只考虑了用户相似性。　王辉等提出了个性化服务中基于用户聚类的协同过　滤推荐　Ｊ，该算法对可扩展性和数据型稀疏性方面　进行了一定改进，但是效率和准确度还有待提高。　多大型电子商务网站，如Ａｍａｚｏｎ，Ｅｂａｙ，Ｌｅｖｉｓ，阿里　巴巴，当当网上书店等都采用了各种形式的推荐系　统功能。伴随着电子商务规模的增大，用户与项目　的数量急剧上升，协同过滤算法面临的关键挑战是　收稿１３期：２０１３．１１－２５．　作者简介：赵广艳（１９８７一），女，硕士研究生，Ｅ－ｍａｉｌ：ｚｈａｏｇｕａｎｇｙａｎ２７＠１６３．ｔｏｍ　通信作者：李禹生（１９５４一），男，教授，Ｅ—ｍａｉｌ：ｐｒｏｆ．１ｉ＠１６３．ｃｏｒｎ．　２期　赵广艳，李禹生，韩吴：基于联合聚类和矩阵分解的协同过滤算法研究　６１　在协同过滤推荐算法中，需要处理的数据都是　根据用户．项目评分矩阵来进行的。针对协同过滤　算法存在的可扩展性和数据稀疏性，笔者引入联合　会变得相对容易；②有效缓解评分稀疏性。　协同过滤算法，就是处理用户一项目评分矩阵，　联合聚类的目的就是缩小子矩阵内部评分数据间的　差异。以评分模式为标准的联合聚类　采用的思　路是扫描用户～项目评分矩阵中已经有的评分，进　聚类（ＢｌｏｃｋＣｌｕｓｔ，简称ＢＣ）和带正则化的迭代最小　二乘法（ａｌｔｅｒｎａｔｉｎｇ—ｌｅａｓｔ－ｓｑｕａｒｅｓ　ｗｉｔｈ　ｗｅｉｇｈｔｅｄ—ｒｅｇｕ—　ｌａｒｉｚａｔｉｏｎ，简称ＡＷ），提出了一种基于ＢＣ—ＡＷ的协　行行聚类与列聚类两个步骤进行概率计算，每次迭　代都需要重新评估计算用户、项目、评分这三者属于　每个子矩阵的概率直至收敛。将每个评分分配到所　求概率最大的那个子矩阵，不同的子矩阵可能包含　同一个用户一项目。每个子矩阵的用户、项目、评分　同过滤推荐算法，有效缓解了传统算法难以并行化、　可扩展性差的问题，整个算法主要分为两步：①在原　始评分矩阵中进行用户一项目两个维度的联合聚　类，聚类后生成具有相同模式评分块的若干子矩阵，　联合聚类后的子矩阵规模远小于原始评分矩阵，大　会组成新矩阵，此时的新矩阵已经是高相似性评分　的子矩阵，可以快速有效应用计算。　联合聚类后原来非常稀疏的用户一项目评分矩　阵转变成为　个规模较小的子矩阵，每个子矩阵的　内部评分相似度较高并且相对稠密，从而可以进行　有效的降维。在下一阶段的评分预测也会变更容　易、更准确。　幅度降低预测阶段计算量。②在联合聚类后生成的　每个子矩阵上分别利用带正则化的迭代最小二乘法　的协同过滤算法来预测子矩阵中的未知评分，进而　进行推荐。　ｌ　联合聚类　怎样处理大量并且很稀疏的训练数据是协同过　对评分模式为标准的联合聚类，扫描评分矩阵，　计算每个评分属于某子矩阵的概率ｐ（ｋ　ｌ　ｕ，　，ｒ），　要判定一个评分属于某子矩阵，需要考虑与评分所　关联的用户一项目属于该子矩阵的概率分别为Ｐ（ｋ　滤算法面ｌｌ缶的关键问题，因此通过联合聚类的方法　将原始训练数据划分成数据规模较小、相似度较高　的子矩阵是一种有效的方法。对于协同过滤算法问　题，联合聚类算法应用到协同过滤算法有两大优势：　Ｉ　ｕ）与Ｐ（ｋ　ｌ　），以及该评分值出现在这个子矩阵　中的概率Ｐ（ｒ　Ｉ．ｉ｝）。计算公式如下：　①需要处理的数据规模大量减少，算法的复杂操作　觜　（２）　…、　∑　㈩ｐ（ｋ　Ｉ　，ｒ）　’　（３）　ｐ（ｒ　ｌ　ｋ）＝　．　（４）　其中，ｕ为当前用户，　为当前项目，ｒ为评分值，　ｒ　为１到５的整数，ｋ为当前聚类，ｋ　为累加时的当前　传统的矩阵分解模型的方法。通过考虑，这里采用　改进的矩阵分解算法（ａｌｔｅｒｎａｔｉｎｇ—ｌｅａｓｔ—ｓｑｕａｒｅｓ　ｗｉｔｈ　ｗｅｉｇｈｔｅｄ．ｒｅｇｕｌａｒｉｚａｔｉｏｎ，简称ＡＷ）　来进行评分预　聚类，Ｕ（ｖ）为给项目　评过分的所有用户集合，　（Ｍ）为用户“已评过分的所有项目集合，为了防止　分母为０需要设置超参数Ｏｔ　，０，可根据具体情况设　定，在下面的实验中统一设为０．０００　０００　１。　测。对于联合聚类后的子矩阵，ＡＷ方法可以在极　短的时间内收敛到局部最小。　给定一个矩阵尺，　ｉ　为矩阵的元素，Ｒｉ．为矩阵　ＪＲ的第ｉ行，　．　为矩阵的第　列，　为矩阵尺的转　２带正则化的迭代最小二乘法的矩阵　分解　在预测阶段，评分预测可以选用很多种矩阵填　充方法，例如简单的ｋ．最近邻模型预测方法，基于　置。　为矩阵的逆。矩阵Ａ∈Ｃ　、Ｂ∈Ｃ　分别　为用户和项目矩阵的特征矩阵，，为一个ｄ×ｄ的单　位矩阵。　为了能够找到低秩矩阵　来最大程度的接近　６２　武汉轻工大学学报　２０１４篮　矩阵Ｒ，最小化下面损失函数　￡（　）＝∑　（ＪＲ　一Ｘ　）　．　（５）　其中，Ｘ＝ＡＢ　，ｄ为特征数目，一般情况下ｄ＜＜　ｒ，ｒ为矩阵　的秩，ｒ＜ｍｉｎ（ｍ，ｎ），Ｘ　为　矩阵的元　素。　式（５）中（Ｒ　一　）　是低秩逼近中常见平方误　差项，由Ｘ＝ＡＢ　把式（５）改成有效并且快速的求解　最优化问题。　Ｌ（Ａ，　）＝∑　（Ｒ＃一Ａｉ．　）　．　（６）　给式（６）加上正则化项来预防过拟合现象，则　式（６）可以改写成：　Ｌ（Ａ，　）＝∑　（Ｒ　一Ａｉ．　）　＋Ａ（　．　２＋　Ｉｆ　．Ｉｌ；）．　（７）　固定Ｂ，对Ａｉ．求导　警　＝０，得到求解Ａｆ　．的公式如式（８）所示。　Ａ‘．＝Ｒｉ．Ｂ　（Ｂ　Ｔ　＋Ａ＾　，）一１，ｉ∈［１，ｄ］．　（８）　同理，根据式（８）固定Ａ，可以得到Ｂ　的公式　为：　＝Ｒ．ｒ．Ａ　（Ａ　Ａ　＋ＡⅣ　，）一ｌ，　∈［１，ｄ］．　（９）　３　基于ＢＣ－ＡＷ的协同过滤推荐算法　为了预测评分矩阵中的未知项，采用两阶段算　法。具体算法如下：　第１阶段联合聚类　输入：用户一项目评分矩阵　，子矩阵个数Ｋ。　输出：Ｋ个子矩阵　Ｓｔｅｐｌ：随机初始化用户　，项目　，评分ｒ共同　属于聚类ｋ的概率ｐ（｜ｊ｝ＩⅡ，　，ｒ），使得∑　ｋＰ（ｋ　ｌ　ｕ，　，ｒ）＝１；　Ｓｔｅｐ２：根据式（２）计算用户ｕ属于聚类ｋ的概　率Ｐ（ｋ　Ｉ　ｕ）；　Ｓｔｅｐ３：根据式（３）计算用户　属于聚类ｋ的概　率Ｐ（ｋ　ｌ　）；　Ｓｔｅｐ４：根据式（４）计算分值概率ｐ（ｒ　Ｉ　ｋ）；　Ｓｔｅｐ５：根据式（１）计算Ｐ（ｋ　Ｉ　，　，ｒ），并选取概　率最大的ｋ作为该评分的子矩阵；　Ｓｔｅｐ６：跳转到Ｓｔｅｐ２，直至收敛，否则结束程序。　第２阶段：基于ＡＷ的协同过滤评分预测　输入：子矩阵所对应的用户一项目评分矩阵；　输出：预测评分矩阵Ｘ；　Ｓｔｅｐｌ：随机初始化Ａ、Ｂ；　Ｓｔｅｐ２：用式（８）、式（９）反复迭代更新Ａ、Ｂ，直　到收敛或迭代次数足够多而结束迭代；　ｓｔｅ　＝　分析基于ＢＣ—ＡＷ的协同过滤推荐算法，可以　看出该算法的第２阶段的关键步骤是Ｓｔｅｐ２，运用公　式反复迭代更新４和Ｂ直到收敛或迭代次数足够多　而结束迭代。通过式（８）、式（９）可分析出，可以对　矩阵Ａ、Ｂ进行分割，因为每次调用公式只是计算　更新矩阵Ａ、Ｂ的一行值。把矩阵Ａ、Ｂ分成多个　具有相同列长的矩阵来进行并行运算，从而缓解了　传统的基于矩阵分解的协同过滤算法难以并行化、　可扩展性差的问题。　４实验结果分析　４．１　实验数据集和度量标准　该文选取ＭｏｖｉｅＬｅｎｓ数据集评估改进算法的性　能，ＭｏｖｉｅＬｅｎｓ是美国的明尼苏达州立大学（Ｕｎｉｖｅｒ－　ｓｉｔｙ　ｏｆ　Ｍｉｎｎｅｓｏｔａ）的ＧｒｏｕｐＬｅｎｓ研究小组搜集的电影　评价数据集。该数据集中包括９４３位用户对１６８２　部电影的十万条评分数据（评分值为１到５的整　数），５表示评分最好，１表示评分最差，每个用户至　少给出２Ｏ个评分。　将原数据集分为训练集与测试集，从原数据集　中随机抽取８０％的评分数据作为一个训练集，记为　Ｔｒａｉｎ８０；原评分数据中除Ｔｒａｉｎ８０以外的数据集构　成测试集，记为Ｔｅｓｔ２０；把Ｔｒａｉｎ８０中的评分数据集　中的１／２抽取出来作为另一个训练集，记为　Ｔｒａｉｎ４０。通过训练集生成模型，对测试集进行评分　预测，根据预测评分的结果与原实际评分之间的偏　差来度量预测的准确性。本文采用的评估方法为均　方根误差ＲＭＳＥ　（Ｒｏｏｔ　Ｍｅａｎ　Ｓｑｕａｒｅ　Ｅｒｒｏｒ）的方　法，ＲＭＳＥ值越小，代表准确度越高。假设ｎ表示将　要评估预测评分的项目数量，用户对　个项目的预　测评分值集合为｛Ｐ。，Ｐ　…．，Ｐ　｝，实际评分值集合　为｛ｑ。，ｑ　…．ｑ　｝，ＲＭＳＥ的计算公式如下：　２期　赵广艳，李禹生，韩吴：基于联合聚类和矩阵分解的协同过滤算法研究　６３　ＭｏｖｉｅＬｅｎｓ进行评分预测，算法的超参数设置如下：　＝　＝０＝０．０００　０００　１。对于子矩阵个数　的设　置做了一组实验，实验结果如图１所示。　图１　子矩阵个数　与剐　阳的关系　由图１可知，在各种实验条件下，在训练集为　Ｔｒａｉｎ８０类别数为５０的情况下ＲＭＳＥ最小，系统推　荐质量最好。在以下的实验中，采用类别数Ｋ为　５０。　将基于ＢＣ．ＡＷ的协同过滤算法的有效性进行　对比实验，参与对比实验的算法包含Ｈｏｆｍａｎｎ提出　的潜在语义模型协同过滤算法（ＬＳＭ）　和基于矩　阵分解的协同过滤算法（ＡＬＳ．ＷＲ）。各个算法均分　别在Ｔｒａｉｎ８０，Ｔｒａｉｎ４０训练集上训练，在Ｔｅｓｔ２０上测　试得到ＲＭＳＥ值，实验数据如图２所示。　１．１５　１．１Ｏ　１．０５　１．Ｏ０　Ｏ．９５　图２不同算法性能比较结果　从图２可以看出，本算法的均方根误差较小，说　明推荐准确度得到了一定的提升。　５　结束语　该文提出了基于联合聚类和迭代最小二乘法的　两阶段协同过滤算法。首先对原始评分数据进行基　于用户一项目的联合聚类，即以评分值为标准，寻找　具有相同模式的评分块，从而把原始评分矩阵划分　成为相互可能有交叉的评分子块，聚类后的矩阵规　模远小于原始评分矩阵，可快速灵活的进行评分预　测。在评分预测阶段，采用基于ＡＷ的协同过滤算　法的评分预测，并分析了其可扩展性及抗稀疏性问　题。分别在Ｔｒａｉｎ８０，Ｔｒａｉｎ４０的训练集下采用不同　类别数　下，比较了均方根误差，找出了效果最好　的条件。在效果最好的条件下，和几个经典协同过　滤算法进行比较。实验结果表明，ＢＣ—ＡＷ算法优于　几个经典的协同过滤算法。　参考文献：　［１］　李涛，王建东，叶飞跃，等．一种基于用户聚类　的协同过滤推荐算法［Ｊ］．系统工程与电子技　术，２００７，２９（７）：１１７８－１１８２．　［２］　王辉，高利军，王听忠．个性化服务中基于用　户聚类的协同过滤推荐［Ｊ］．计算机应用，　２００７，２７（５）：１２２５—１２２７．　［３］　吴湖，王永吉，王哲，等．两阶段联合聚类协同　过滤算法［Ｊ］．软件学报，２０１０，２１（５）：１０４２—　１０５４．　［４］　李改，李磊．基于矩阵分解的协同过滤算法　［Ｊ］．计算机工程与应用，２０１１，４７（３０）：４－７．　［５］　Ｋｏｒｅｎ　Ｙ．Ｆａｃｔｏｒｉｚａｔｉｏｎ　ｍｅｅｔｓ　ｔｈｅ　ｎｅｉｇｈｂｏｒｈｏｏｄ：　Ａ　ｍｕｈｉｆａｃｅｔｅｄ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ　ｍｏｄｅｌ　［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　１４ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔｅｍａ．　ｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，２００８：４２６４３４．　［６］Ｈｏｆｍａｎｎ　Ｔ．Ｌａｔｅｎｔ　ｓｅｍａｎｔｉｃ　ｍｏｄｅｌｓ　ｆｏｒ　ｃｏｌｌａｂｏ—　ｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ［Ｊ］．ＡＣＭ　Ｔｒａｎｓ　ａｃｔｉｏｎｓ　ｏｎ　Ｉｎｆｏｒ－　ｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，２００４，２２：８９—１　１５．