论文部分内容阅读
摘 要：针对协同过滤算法中扩展性问题，文章将用户兴趣看成多个兴趣的集合，然后提出一种基于局部兴趣的协同过滤算法，算法通过改善候选项目集来减少推荐时间。最后，文章给出了MovieLens数据集上的比较实验，实验结果表明，文章提出的算法在提高系统的实时性的同时，可以进一步提高系统的推荐精度。
关键词：协同过滤；扩展性；推荐精度；候选项目集
中图分类号：TP391
随着电子商务和个性化网站的迅猛发展，个性化推荐已经成为网络应用的热点问题。在诸多的推荐方法中，协同过滤算法是应用最广泛，也是最成功的技术之一[1]。随着系统用户数和项目数的增加，协同过滤算法面临着严重的可扩展性问题，推荐系统的实时性越来越难以满足用户的需求。本文提出了一种新的基于局部兴趣的协同过滤算法（Local-Interesting-Based Collaborative Filtering，LICF），改善了传统协同过滤算法在产生候选项目集中的不足，大大降低候选项目的个数，进而改善了系统的扩展性。
1 相关工作
1.1 协同过滤技术
目前研究和使用最多的两种协同过滤算法是：基于用户的协同过滤算法（User-based Collaborative Filtering，UBCF）和基于项目的协同过滤算法（Item-based Collaborative Filtering，IBCF）[2]。基于用户的协同过滤算法的基本原理是：通过计算用户对项目评分的相似性，搜索目标用户的最近邻居，然后根据最近邻居的评分向目标用户产生推荐。基于项目的协同过滤算法的原理是：能够引起用户兴趣的项目，必定与其之前评分高的项目相似[3]。
协同过滤算法使用用户对项目的评分进行产生推荐，假设在推荐系统中，存在m个用户和n个项目，则所有用户-项目评分可以用m×n阶矩阵Rmn表示，其中rij（1≤i≤m，1≤j≤n）是一个用户-项目对，表示用户i对项目j的评分。矩阵中每一行ru={ru1，ru2，…run}代表一个用户的评分向量，每一列ri={r1i，r2i，…rmi}代表一个项目的评分向量。本文中假设目标用户为u，待预测的目标项目为i。
1.2 基于用户的协同过滤算法
基于用户的协同过滤算法是通过用户向量计算用户之间的相似性，为目标用户找到若干最近邻居，然后根据最近邻居对目标项目的评分来预测目标用户的评分，最后选择预测评分最高的前N项（top-N）作为推荐结果反馈给用户。基于用户的协同过滤算法有如下核心步骤：
（1）计算用户间相似度。计算目标用户与其他所有用户的相似度，然后选取出k个相似度最大的用户作为目标用户的最近邻居。目前，比较常用相似度方法有Pearson相关系数、余弦向量相似度和修正余弦向量相似度等，本文中使用余弦向量相似度，公式如下。
其中，simuv表示用户u与用户v之间的相似度，和分别表示用户u与用户v的评分向量，与分别表示用户u与用户v评分向量的模，·表示向量的内积。
（2）预测评分。根据k个最近邻居对目标项目的评分预测目标用户的评分，预测评分一般采用以下公式。
其中，表示目标用户u对目标项目i的预测评分，simuv是目标用户u与邻居用户v之间的相似度，rvi是邻居用户v对项目i的评分，和分别是目标用户u与邻居用户v的平均评分，N为目标用户的最近邻居集合。
（3）产生推荐。根据预测评分从大到小排序，将预测评分最大的N个项目（Top-N）推荐给用户。
2 基于局部兴趣的协同过滤算法
2.1 扩展性问题分析
在基于用户的协同过滤算法中，计算量最大的两步是用户间相似度计算以及对目标用户未评分项目的评分预测。为了缓解协同过滤中的扩展性问题，学者们引入了矩阵分解、聚类等技术[4]，目的是为了降低评分矩阵的维数，缩小搜索空间，但在降维过程中往往伴随着用户信息丢失，导致推荐质量下降。因此，系统扩展性的提高往往是以牺牲推荐质量为代价的。
本文从一个新的角度来缓解系统扩展性问题，传统协同算法在产生候选项目集时会引入大量的无关项目，导致算法需要为无关项目预测评分而增加了计算量。一般情况下，基于用户的协同过滤算法不会为目标用户预测所有的未评分项目的评分，而是先为目标用户生成候选项目集，然后再对候选项目集中的项目进行预测。假设目标用户u的最近邻居集（候选近邻）为Nk={u1，u2，…uk}，用户u及其最近邻居对应的已评分项目集为Iu和{I1，I2，…Ik}，则目标用户的候选项目集C=I1∪I2∪…∪Ik-Iu。
本文提出了一种新的基于局部兴趣的协同过滤算法（Local-Interesting-Based Collaborative Filtering，LICF），算法中改善了传统协同过滤算法在产生候选项目集中的不足，大大降低候选项目的个数，进而改善了系统的扩展性。
2.2 基于局部兴趣的协同过滤算法
本文认为用户的兴趣并不是固定的，而是一般会拥有一个或多个兴趣，例如，有的用户对科幻电影和爱情感兴趣，而有的用户对科幻电影和恐怖电影感兴趣，本文中将用户的兴趣模型定义为：
定义1（用户兴趣模型）每个用户的兴趣可以表示为E={e1，e2，…et}，其中et表示用户的一个兴趣，每个兴趣会对应一系列相应的项目。
一般情况下，用户之间通常只有部分兴趣相似，其余兴趣并不相似，甚至是相反的。对于两个相似用户u和v，其用户模型又可以分别表示为Eu={e，eu}，Ev={e，ev}，其中e表示用户u和v共同的兴趣，eu，ev分别表示用户u和用户v与彼此不同的个人兴趣。
用户u的最近邻居至少是在部分兴趣上与用户u存在相似性，换句话说就是围绕兴趣e1，用户u将邻居N1={u1，u2，…uk}聚集在一起。兴趣e1对应一系列项目Ie1，用户u及邻居N1非常可能对这些项目感兴趣，所以对于这部分项目，在极大程度上有多个用户对其有过评分。而对应于用户个人兴趣的项目，基本上只有该用户本身或极其少数的其他用户有过评分。同样最近邻居N2中的用户与用户u围绕兴趣e2也有着相似的结果。 因此，本文认为并非是邻居用户感兴趣的所有项目，目标用户u都可能感兴趣。于是，在生成候选集的过程中，需要找出共同兴趣所对应的项目，去除邻居用户个人兴趣所对应的项目。本文认为在所有近邻用户评分过的项目中，只有评分用户较多的项目才是与共同兴趣相对应的项目，而评分用户过少的项目可能是由于某邻居用户的个人兴趣带来的。同时，本文引入了阈值α，定义最近邻居所有的评分过的项目，只有评分的邻居数超过阈值α的项目才入选候选项目集，否则不入选候选项目集。阈值α的取值与最近邻居数有关，一般情况下，邻居数越大，阈值α取值就越大，具体应用中，可以根据经验或实验数据来得到。
3 实验结果及分析
3.1 数据集及评价指标
实验采用的是公开的MovieLens数据集，数据集包括943名用户在1682部电影上的100000条评分记录，评分的范围是1-5的整数。以下实验中，我们将数据集分成80%的训练集和20%的测试集，并使用五折交叉法进行实验。
本文采用的测量指标是平均推荐时间与P@n值（推荐精度），一般情况下，系统拥有大量的优质资源，单个用户不可能也没有精力去浏览或购买所有的优质资源，因此，如何推荐出部分用户所需要优质资源比找出所有的优质资源更符合实际，因此，文章采用的了P@n值。其定义如下：
P@n=test∩topN/N
其中，test是测试集中的项目，topN是推荐列表。P@n值测量是前N项推荐列表中相关项目所占比率。
3.2 实验结果及分析
首先，文章比较了传统基于用户的协同过滤算法（UBCF）与本文提出的基于局部兴趣的协同过滤算法方法在P@n值上的区别，如图1所示。实验中，候选近邻数为5（生成候选项目集所用邻居数），相似度算法都使用余弦相似度，阈值α取值为2（LICF-2）和4（LICF-4），预测近邻取30（预测评分时所用邻居数），Top-N值从2增加到20，间隔为2。
从整体上来说，本文提出的算法要明显优于传统算法，比如推荐列表长度取常见值10时，三种算法的推荐精度分别约为16%，19%和22%。同时，LICF-2的效果整体上来说要优于LICF-4的效果，主要是因为候选近邻数为5，而阈值α取值为4时，过分降低了候选项目集的大小，将一部分用户可能感兴趣的项目也排除出了候选项目集。
图1 推荐精度比较
图2 推荐实时性比较
随后，文章比较了两种算法在平均推荐时间的上的比较，实验计算推荐所用CPU时间，单位为秒，取top-N=5，候选近邻数从5增长到10，间隔为1，结果如图2所示。从图中可以看出，随着近邻数的增加，两算法所用时间都是不断增长，但本文提出算法所用时间明显小于传统UBCF算法。
4 结束语
面对扩展性问题，传统的方法是用推荐质量换取推荐效率，本文从一个新的角度来缓解系统扩展性问题，通过改善候选项目集来减少推荐时间。实验证明本文提出的算法在提高系统的实时性的同时，还可以取得更优的推荐精度（P@n值）。另外，本文提出的算法与以往的解决方法并不冲突，下一步的工作是把本文提出的算法与以往的解决算法相结合，以便进一步提高推荐实时性和推荐效果。
参考文献：
[1]吴湖，王永吉，王哲等.两阶段联合聚类协同过滤算法[J].软件学报， 2010，21（5）：1042-1054.
[2]S.J.Gong.A Collaborative Filtering Recommendation Algorithm Based on User Clustering and Item Clustering [J]. Journal of Softwar，2010，5（7）：745-752.
[3]王茜，王均波.一种改进的协同过滤推荐算法[J].计算机科学，2010，37（6）：226-243.
[4]姚劲勃，余宜诚，于卓尔等.基于PCA降维协同过滤算法的改进[J].吉林大学学报：信息科学版，2011，5：494-497.
作者简介：韩淑云（1982-），女，硕士，助教，主要研究方向：知识服务，计算机应用技术。
关键词：协同过滤；扩展性；推荐精度；候选项目集
中图分类号：TP391
随着电子商务和个性化网站的迅猛发展，个性化推荐已经成为网络应用的热点问题。在诸多的推荐方法中，协同过滤算法是应用最广泛，也是最成功的技术之一[1]。随着系统用户数和项目数的增加，协同过滤算法面临着严重的可扩展性问题，推荐系统的实时性越来越难以满足用户的需求。本文提出了一种新的基于局部兴趣的协同过滤算法（Local-Interesting-Based Collaborative Filtering，LICF），改善了传统协同过滤算法在产生候选项目集中的不足，大大降低候选项目的个数，进而改善了系统的扩展性。
1 相关工作
1.1 协同过滤技术
目前研究和使用最多的两种协同过滤算法是：基于用户的协同过滤算法（User-based Collaborative Filtering，UBCF）和基于项目的协同过滤算法（Item-based Collaborative Filtering，IBCF）[2]。基于用户的协同过滤算法的基本原理是：通过计算用户对项目评分的相似性，搜索目标用户的最近邻居，然后根据最近邻居的评分向目标用户产生推荐。基于项目的协同过滤算法的原理是：能够引起用户兴趣的项目，必定与其之前评分高的项目相似[3]。
协同过滤算法使用用户对项目的评分进行产生推荐，假设在推荐系统中，存在m个用户和n个项目，则所有用户-项目评分可以用m×n阶矩阵Rmn表示，其中rij（1≤i≤m，1≤j≤n）是一个用户-项目对，表示用户i对项目j的评分。矩阵中每一行ru={ru1，ru2，…run}代表一个用户的评分向量，每一列ri={r1i，r2i，…rmi}代表一个项目的评分向量。本文中假设目标用户为u，待预测的目标项目为i。
1.2 基于用户的协同过滤算法
基于用户的协同过滤算法是通过用户向量计算用户之间的相似性，为目标用户找到若干最近邻居，然后根据最近邻居对目标项目的评分来预测目标用户的评分，最后选择预测评分最高的前N项（top-N）作为推荐结果反馈给用户。基于用户的协同过滤算法有如下核心步骤：
（1）计算用户间相似度。计算目标用户与其他所有用户的相似度，然后选取出k个相似度最大的用户作为目标用户的最近邻居。目前，比较常用相似度方法有Pearson相关系数、余弦向量相似度和修正余弦向量相似度等，本文中使用余弦向量相似度，公式如下。
其中，simuv表示用户u与用户v之间的相似度，和分别表示用户u与用户v的评分向量，与分别表示用户u与用户v评分向量的模，·表示向量的内积。
（2）预测评分。根据k个最近邻居对目标项目的评分预测目标用户的评分，预测评分一般采用以下公式。
其中，表示目标用户u对目标项目i的预测评分，simuv是目标用户u与邻居用户v之间的相似度，rvi是邻居用户v对项目i的评分，和分别是目标用户u与邻居用户v的平均评分，N为目标用户的最近邻居集合。
（3）产生推荐。根据预测评分从大到小排序，将预测评分最大的N个项目（Top-N）推荐给用户。
2 基于局部兴趣的协同过滤算法
2.1 扩展性问题分析
在基于用户的协同过滤算法中，计算量最大的两步是用户间相似度计算以及对目标用户未评分项目的评分预测。为了缓解协同过滤中的扩展性问题，学者们引入了矩阵分解、聚类等技术[4]，目的是为了降低评分矩阵的维数，缩小搜索空间，但在降维过程中往往伴随着用户信息丢失，导致推荐质量下降。因此，系统扩展性的提高往往是以牺牲推荐质量为代价的。
本文从一个新的角度来缓解系统扩展性问题，传统协同算法在产生候选项目集时会引入大量的无关项目，导致算法需要为无关项目预测评分而增加了计算量。一般情况下，基于用户的协同过滤算法不会为目标用户预测所有的未评分项目的评分，而是先为目标用户生成候选项目集，然后再对候选项目集中的项目进行预测。假设目标用户u的最近邻居集（候选近邻）为Nk={u1，u2，…uk}，用户u及其最近邻居对应的已评分项目集为Iu和{I1，I2，…Ik}，则目标用户的候选项目集C=I1∪I2∪…∪Ik-Iu。
本文提出了一种新的基于局部兴趣的协同过滤算法（Local-Interesting-Based Collaborative Filtering，LICF），算法中改善了传统协同过滤算法在产生候选项目集中的不足，大大降低候选项目的个数，进而改善了系统的扩展性。
2.2 基于局部兴趣的协同过滤算法
本文认为用户的兴趣并不是固定的，而是一般会拥有一个或多个兴趣，例如，有的用户对科幻电影和爱情感兴趣，而有的用户对科幻电影和恐怖电影感兴趣，本文中将用户的兴趣模型定义为：
定义1（用户兴趣模型）每个用户的兴趣可以表示为E={e1，e2，…et}，其中et表示用户的一个兴趣，每个兴趣会对应一系列相应的项目。
一般情况下，用户之间通常只有部分兴趣相似，其余兴趣并不相似，甚至是相反的。对于两个相似用户u和v，其用户模型又可以分别表示为Eu={e，eu}，Ev={e，ev}，其中e表示用户u和v共同的兴趣，eu，ev分别表示用户u和用户v与彼此不同的个人兴趣。
用户u的最近邻居至少是在部分兴趣上与用户u存在相似性，换句话说就是围绕兴趣e1，用户u将邻居N1={u1，u2，…uk}聚集在一起。兴趣e1对应一系列项目Ie1，用户u及邻居N1非常可能对这些项目感兴趣，所以对于这部分项目，在极大程度上有多个用户对其有过评分。而对应于用户个人兴趣的项目，基本上只有该用户本身或极其少数的其他用户有过评分。同样最近邻居N2中的用户与用户u围绕兴趣e2也有着相似的结果。 因此，本文认为并非是邻居用户感兴趣的所有项目，目标用户u都可能感兴趣。于是，在生成候选集的过程中，需要找出共同兴趣所对应的项目，去除邻居用户个人兴趣所对应的项目。本文认为在所有近邻用户评分过的项目中，只有评分用户较多的项目才是与共同兴趣相对应的项目，而评分用户过少的项目可能是由于某邻居用户的个人兴趣带来的。同时，本文引入了阈值α，定义最近邻居所有的评分过的项目，只有评分的邻居数超过阈值α的项目才入选候选项目集，否则不入选候选项目集。阈值α的取值与最近邻居数有关，一般情况下，邻居数越大，阈值α取值就越大，具体应用中，可以根据经验或实验数据来得到。
3 实验结果及分析
3.1 数据集及评价指标
实验采用的是公开的MovieLens数据集，数据集包括943名用户在1682部电影上的100000条评分记录，评分的范围是1-5的整数。以下实验中，我们将数据集分成80%的训练集和20%的测试集，并使用五折交叉法进行实验。
本文采用的测量指标是平均推荐时间与P@n值（推荐精度），一般情况下，系统拥有大量的优质资源，单个用户不可能也没有精力去浏览或购买所有的优质资源，因此，如何推荐出部分用户所需要优质资源比找出所有的优质资源更符合实际，因此，文章采用的了P@n值。其定义如下：
P@n=test∩topN/N
其中，test是测试集中的项目，topN是推荐列表。P@n值测量是前N项推荐列表中相关项目所占比率。
3.2 实验结果及分析
首先，文章比较了传统基于用户的协同过滤算法（UBCF）与本文提出的基于局部兴趣的协同过滤算法方法在P@n值上的区别，如图1所示。实验中，候选近邻数为5（生成候选项目集所用邻居数），相似度算法都使用余弦相似度，阈值α取值为2（LICF-2）和4（LICF-4），预测近邻取30（预测评分时所用邻居数），Top-N值从2增加到20，间隔为2。
从整体上来说，本文提出的算法要明显优于传统算法，比如推荐列表长度取常见值10时，三种算法的推荐精度分别约为16%，19%和22%。同时，LICF-2的效果整体上来说要优于LICF-4的效果，主要是因为候选近邻数为5，而阈值α取值为4时，过分降低了候选项目集的大小，将一部分用户可能感兴趣的项目也排除出了候选项目集。
图1 推荐精度比较
图2 推荐实时性比较
随后，文章比较了两种算法在平均推荐时间的上的比较，实验计算推荐所用CPU时间，单位为秒，取top-N=5，候选近邻数从5增长到10，间隔为1，结果如图2所示。从图中可以看出，随着近邻数的增加，两算法所用时间都是不断增长，但本文提出算法所用时间明显小于传统UBCF算法。
4 结束语
面对扩展性问题，传统的方法是用推荐质量换取推荐效率，本文从一个新的角度来缓解系统扩展性问题，通过改善候选项目集来减少推荐时间。实验证明本文提出的算法在提高系统的实时性的同时，还可以取得更优的推荐精度（P@n值）。另外，本文提出的算法与以往的解决方法并不冲突，下一步的工作是把本文提出的算法与以往的解决算法相结合，以便进一步提高推荐实时性和推荐效果。
参考文献：
[1]吴湖，王永吉，王哲等.两阶段联合聚类协同过滤算法[J].软件学报， 2010，21（5）：1042-1054.
[2]S.J.Gong.A Collaborative Filtering Recommendation Algorithm Based on User Clustering and Item Clustering [J]. Journal of Softwar，2010，5（7）：745-752.
[3]王茜，王均波.一种改进的协同过滤推荐算法[J].计算机科学，2010，37（6）：226-243.
[4]姚劲勃，余宜诚，于卓尔等.基于PCA降维协同过滤算法的改进[J].吉林大学学报：信息科学版，2011，5：494-497.
作者简介：韩淑云（1982-），女，硕士，助教，主要研究方向：知识服务，计算机应用技术。