结合关联规则填充的协同过滤改进算法
包志强 宋静霞
关键词： 关联规则; 数据填充; 协同过滤; 推荐算法; 评分矩阵; 数据稀疏; 对比实验
中图分类号： TN911.1?34; TP301.6 ? ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2019）03?0078?04
Abstract： Since the traditional collaborative filtering algorithm for personalized recommendation has the problems of sparse scoring matrix of user and item， low recommendation accuracy and cold start， an improved collaborative filtering recommendation algorithm based on association rules filling is proposed. The result obtained by association rules is added into this algorithm before the first step of the collaborative filtering algorithm to predict some items without score value. The obtained data is filled into original user?item scoring matrix to reduce the sparseness of the scoring matrix， which can provide the similarity calculation for more data. And on this basis， the traditional collaborative filtering algorithm based on item is combined to make recommendation to users. The experiment contrast is carried out with MovieLens dataset. The results show that， in comparison with the traditional algorithm， the proposed algorithm can improve the accuracy and effectiveness of the recommendation system.
Keywords： association rule; data filling; collaborative filtering; recommendation algorithm; scoring matrix; data sparseness; contrast experiment0 ?引 ?言
当今是数据化的时代，每天被海量信息充斥，为便于人们从中快速准确地找到自己所需要的，个性化推荐应运而生，而协同过滤算法是其中最重要和运用最广泛的一种技术方法。它最开始是对邮件进行过滤[1]，随后运用在新闻推荐[2]中，现在扩展到物联网、在线视频等其他领域。传统的协同过滤算法大致可以分为基于用户的协同过滤[3]（user_based CF）和基于项目的协同过滤[4]（item_based CF）兩类。第一种方法先利用数据集中的相关数据求出不同用户间的相似性，选择和所求的用户相似度比较高的那几个用户组成该用户的近邻用户集合，然后再根据这些近邻用户对某些项目的评分值利用相关公式预测目标用户的评分值;而第二种方法则是根据相同用户之前已经评分过的不同项目计算不同项目之间的相似程度，去掉计算近邻用户，后续步骤和第一种类似。
但该算法有几个非常明显的缺陷，例如：冷启动、推荐准确度低、可扩展性差以及数据稀疏等。为了进一步得到更精确的推荐结果，学者们基于现有技术和知识水平提出了很多新的方法和观点对传统算法进行改进。文献[2]研究项目相似度的不同计算方法，并将结果与K?最近邻算法进行比较。文献[5]利用主成分分析法将高维的评分矩阵降为较低维。文献[6]实现了一种基于可信任传达的推荐办法，这是在认为用户间的信任关系具有传播性的基础上得到的。文献[7]添加用户标签作为一个用户兴趣特征的相似度权重进行计算，提高了精度。文献[8]通过打分精度和数量确定可信度得分，将用户信任等级与相似度计算相结合，从而提高算法的准确性。文献[9]建议通过社交网络首先对用户之间的信任度进行运算，然后通过用户的兴趣找到其最近邻居，最后再融合用户数据，从而提高推荐精度。总体而言，已有的大多数研究方法都是从提高相似度计算效率的角度来提高最终的推荐效果。
事实上，除了计算相似度的方法，数据本身的情况也会很大程度影响最终的推荐效果。在实际应用中，用户数和项目数都是动态的，在不断增多，随之带来的结果就是用户?项目的评分矩阵渐渐变成了高维。而实际利用率通常在1%以下[10]，只是数据中很小的一部分，也就是说，此时的评分矩阵有用数据很少，大部分都是无意义的数据。如果系统通过某种方式填充了一些新数据加入到原来较稀疏的评分矩阵中，就降低了这个评分数据的稀疏性，问题就可能得到解决。
本文提出一种结合关联规则的协同过滤改进算法（Association Rules Data Filling Item_Based Collaborative Filtering，ARDF?IBCF），该算法首先通过关联规则得到二阶频繁项集的置信度，然后把置信度作为一个权值因子，按照用户之前评分过的项目值预测出一些还没有评分项目的评分值填充到用户?项目矩阵中，接下来再按照传统基于项目的协同过滤算法一步步施行，最终得到所需要的用户推荐目录，从而达到目的。
1 ?传统基于项目的协同过滤算法
传统基于项目的协同过滤算法就是将与用户以前购买过的相类似的物品推荐给他们。第一步先计算项目间相似度，再根据项目间相似程度和用户之前购买过的历史记录产生对用户进行推荐的清单表。因此，在经常使用的传统IBCF算法中，第一步是基础。
通常使用以下三种相似性计算方法进行计算： 基于余弦的相似度计算、基于修正余弦相似度计算以及基于Pearson相关系数法相似度计算方法。其中基于Pearson相关系数法的相似度计算经过试验比照证实在这三种方法中误差最小，成效极明显[11]。
假设有关于[m]个用户和[n]个项目的一个数据集，可以通过一个[m×n]的大矩阵[R]表示数据集中用户和项目的评分信息，如表1所示。表中第[i]行第[j]列元素[Rij]表示用户[i]对项目[j]的实际评分值。
3.3 ?实验结果及分析
关联规则的支持度阈值一般设为5%～10%，置信度阈值一般设为70%～90%。本文实验选择置信度阈值[C=0.7]，当支持度阈值[S=0.15]时，得到181条规则，可以填充2 589项数据;当支持度阈值[S=0.1]时，得到577条规则，可以填充4 833项数据。通过比较传统的UBCF，IBCF算法和本文实验的改进算法的预测结果和测试集中给出的实际数据，分别计算RMSE和MAE值，得到的结果如表2～表4，图1～图3所示。由表2和图1可以得到，在本文数据集下，传统算法中IBCF算法优于UBCF算法，所以本文实验选择关联规则与IBCF相结合。
由表3和图2可以得出，本文实验ARDF?IBCF算法的RMSE和MAE值均小于IBCF算法，表示改进的算法确实提高了推荐效率的准确性。
由表4和图3可以看出，在改进算法中填充数据较多的ARDF?IBCF（577）算法的RMSE和MAE值更小，推荐质量更优。
4 ?结 ?论
传统协同过滤算法因为数据稀疏导致推荐质量效果差，本文提出一种基于关联规则数据填充的改进算法。通过各个实验对比显示，先利用關联规则预测出一些还未评分过的项目值填充至稀疏矩阵中，再运用传统基于项目的协同过滤进行推荐，确实提高了推荐的准确性。因此本文提出的改进算法的推荐质量优于传统的协同过滤算法，并具有一定的实际意义。
参考文献
[1] HERLOKCER J L， KONSTAN J A， BORHCESR A， et al. An algorithmic framework for performing collaborative filtering [C]// Proceedings of 1999 ACM SIGIR Conference on Research and Development in Information Retrieval. Berkeley： ACM Press， 1999： 230?237
[2] SARWAR B， KARYPIS G， KONSTAN J， et al. Item?based collaborative filtering recommendation algorithms [C]// Procee?dings of the 10th International World Wide Web Conference. Hong Kong， China： ACM， 2001： 285?295.
[3] GOLDBERG D， NICHOLS D， OKI B M， et al. Using collabo?rative filtering to weave an information tapestry [J]. Communications of the ACM， 1992， 35（12）： 61?70.
[4] RESNICK P， LACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// Proceedings of 1994 ACM Conference on Computer Supported Cooperative Work. Chapel Hill： ACM， 1994： 175?186.
[5] KIM D， YUM B L. Collaborative filtering based on iterative principal component analysis [J]. International journal of expert systems with applications， 2005， 28（4）： 823?830.
[6] JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks [C]// Proceedings of the 4th ACM Conference on Recommender Systems. Barceloa， Spain： ACM， 2010： 135?142.
[7] 蔡强，韩东梅，李海生，等.基于标签和协同过滤的个性化资源推荐[J].计算机科学，2014，41（1）：69?71.
CAI Q， HAN D M， LI H S， et al. Personalized resource re?commendation based on tags and collaborative filtering [J]. Computer science， 2014， 41（1）： 69?71.
[8] 刘胜宗，廖志芳，吴言凤，等.一种融合用户评分可信度和相似度的协同过滤算法[J].小型微型计算机系统，2014，35（5）：973?977.
LIU S Z， LIAO Z F， WU Y F， et al. A collaborative filtering algorithm combined with user rating credibility and similarity [J]. Journal of Chinese computer systems， 2014， 35（5）： 973?977.
[9] 俞琰，邱广华. 融合社会网络的协同过滤推荐算法研究[J].现代图书情报技术，2012，28（6）：54?59.
YU Y， QIU G H. Research on collaborative filtering recommendation algorithm by fusing social network [J]. New technology of library and information service， 2012， 28（6）： 54?59.
[I0] SARWAR B M. Sparsity， scalability and distribution in recommender systems [D]. Minneapolis， USA： University of Minnesota， 2001.
[11] HERLOCKER L J， KONSTAN A J， RIEDL T J. Empirical analysis of design choices in neighborhood?based collaborative filtering algorithms [J]. Information retrieval， 2002， 5（4）： 287?310.
关键词： 关联规则; 数据填充; 协同过滤; 推荐算法; 评分矩阵; 数据稀疏; 对比实验
中图分类号： TN911.1?34; TP301.6 ? ? ? ? ? ? ? ? ?文献标识码： A ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2019）03?0078?04
Abstract： Since the traditional collaborative filtering algorithm for personalized recommendation has the problems of sparse scoring matrix of user and item， low recommendation accuracy and cold start， an improved collaborative filtering recommendation algorithm based on association rules filling is proposed. The result obtained by association rules is added into this algorithm before the first step of the collaborative filtering algorithm to predict some items without score value. The obtained data is filled into original user?item scoring matrix to reduce the sparseness of the scoring matrix， which can provide the similarity calculation for more data. And on this basis， the traditional collaborative filtering algorithm based on item is combined to make recommendation to users. The experiment contrast is carried out with MovieLens dataset. The results show that， in comparison with the traditional algorithm， the proposed algorithm can improve the accuracy and effectiveness of the recommendation system.
Keywords： association rule; data filling; collaborative filtering; recommendation algorithm; scoring matrix; data sparseness; contrast experiment0 ?引 ?言
当今是数据化的时代，每天被海量信息充斥，为便于人们从中快速准确地找到自己所需要的，个性化推荐应运而生，而协同过滤算法是其中最重要和运用最广泛的一种技术方法。它最开始是对邮件进行过滤[1]，随后运用在新闻推荐[2]中，现在扩展到物联网、在线视频等其他领域。传统的协同过滤算法大致可以分为基于用户的协同过滤[3]（user_based CF）和基于项目的协同过滤[4]（item_based CF）兩类。第一种方法先利用数据集中的相关数据求出不同用户间的相似性，选择和所求的用户相似度比较高的那几个用户组成该用户的近邻用户集合，然后再根据这些近邻用户对某些项目的评分值利用相关公式预测目标用户的评分值;而第二种方法则是根据相同用户之前已经评分过的不同项目计算不同项目之间的相似程度，去掉计算近邻用户，后续步骤和第一种类似。
但该算法有几个非常明显的缺陷，例如：冷启动、推荐准确度低、可扩展性差以及数据稀疏等。为了进一步得到更精确的推荐结果，学者们基于现有技术和知识水平提出了很多新的方法和观点对传统算法进行改进。文献[2]研究项目相似度的不同计算方法，并将结果与K?最近邻算法进行比较。文献[5]利用主成分分析法将高维的评分矩阵降为较低维。文献[6]实现了一种基于可信任传达的推荐办法，这是在认为用户间的信任关系具有传播性的基础上得到的。文献[7]添加用户标签作为一个用户兴趣特征的相似度权重进行计算，提高了精度。文献[8]通过打分精度和数量确定可信度得分，将用户信任等级与相似度计算相结合，从而提高算法的准确性。文献[9]建议通过社交网络首先对用户之间的信任度进行运算，然后通过用户的兴趣找到其最近邻居，最后再融合用户数据，从而提高推荐精度。总体而言，已有的大多数研究方法都是从提高相似度计算效率的角度来提高最终的推荐效果。
事实上，除了计算相似度的方法，数据本身的情况也会很大程度影响最终的推荐效果。在实际应用中，用户数和项目数都是动态的，在不断增多，随之带来的结果就是用户?项目的评分矩阵渐渐变成了高维。而实际利用率通常在1%以下[10]，只是数据中很小的一部分，也就是说，此时的评分矩阵有用数据很少，大部分都是无意义的数据。如果系统通过某种方式填充了一些新数据加入到原来较稀疏的评分矩阵中，就降低了这个评分数据的稀疏性，问题就可能得到解决。
本文提出一种结合关联规则的协同过滤改进算法（Association Rules Data Filling Item_Based Collaborative Filtering，ARDF?IBCF），该算法首先通过关联规则得到二阶频繁项集的置信度，然后把置信度作为一个权值因子，按照用户之前评分过的项目值预测出一些还没有评分项目的评分值填充到用户?项目矩阵中，接下来再按照传统基于项目的协同过滤算法一步步施行，最终得到所需要的用户推荐目录，从而达到目的。
1 ?传统基于项目的协同过滤算法
传统基于项目的协同过滤算法就是将与用户以前购买过的相类似的物品推荐给他们。第一步先计算项目间相似度，再根据项目间相似程度和用户之前购买过的历史记录产生对用户进行推荐的清单表。因此，在经常使用的传统IBCF算法中，第一步是基础。
通常使用以下三种相似性计算方法进行计算： 基于余弦的相似度计算、基于修正余弦相似度计算以及基于Pearson相关系数法相似度计算方法。其中基于Pearson相关系数法的相似度计算经过试验比照证实在这三种方法中误差最小，成效极明显[11]。
假设有关于[m]个用户和[n]个项目的一个数据集，可以通过一个[m×n]的大矩阵[R]表示数据集中用户和项目的评分信息，如表1所示。表中第[i]行第[j]列元素[Rij]表示用户[i]对项目[j]的实际评分值。
3.3 ?实验结果及分析关联规则的支持度阈值一般设为5%～10%，置信度阈值一般设为70%～90%。本文实验选择置信度阈值[C=0.7]，当支持度阈值[S=0.15]时，得到181条规则，可以填充2 589项数据;当支持度阈值[S=0.1]时，得到577条规则，可以填充4 833项数据。通过比较传统的UBCF，IBCF算法和本文实验的改进算法的预测结果和测试集中给出的实际数据，分别计算RMSE和MAE值，得到的结果如表2～表4，图1～图3所示。
由表2和图1可以得到，在本文数据集下，传统算法中IBCF算法优于UBCF算法，所以本文实验选择关联规则与IBCF相结合。由表3和图2可以得出，本文实验ARDF?IBCF算法的RMSE和MAE值均小于IBCF算法，表示改进的算法确实提高了推荐效率的准确性。由表4和图3可以看出，在改进算法中填充数据较多的ARDF?IBCF（577）算法的RMSE和MAE值更小，推荐质量更优。
4 ?结 ?论
传统协同过滤算法因为数据稀疏导致推荐质量效果差，本文提出一种基于关联规则数据填充的改进算法。通过各个实验对比显示，先利用關联规则预测出一些还未评分过的项目值填充至稀疏矩阵中，再运用传统基于项目的协同过滤进行推荐，确实提高了推荐的准确性。因此本文提出的改进算法的推荐质量优于传统的协同过滤算法，并具有一定的实际意义。
参考文献
[1] HERLOKCER J L， KONSTAN J A， BORHCESR A， et al. An algorithmic framework for performing collaborative filtering [C]// Proceedings of 1999 ACM SIGIR Conference on Research and Development in Information Retrieval. Berkeley： ACM Press， 1999： 230?237
[2] SARWAR B， KARYPIS G， KONSTAN J， et al. Item?based collaborative filtering recommendation algorithms [C]// Procee?dings of the 10th International World Wide Web Conference. Hong Kong， China： ACM， 2001： 285?295.
[3] GOLDBERG D， NICHOLS D， OKI B M， et al. Using collabo?rative filtering to weave an information tapestry [J]. Communications of the ACM， 1992， 35（12）： 61?70.
[4] RESNICK P， LACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// Proceedings of 1994 ACM Conference on Computer Supported Cooperative Work. Chapel Hill： ACM， 1994： 175?186.
[5] KIM D， YUM B L. Collaborative filtering based on iterative principal component analysis [J]. International journal of expert systems with applications， 2005， 28（4）： 823?830.
[6] JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks [C]// Proceedings of the 4th ACM Conference on Recommender Systems. Barceloa， Spain： ACM， 2010： 135?142.
[7] 蔡强，韩东梅，李海生，等.基于标签和协同过滤的个性化资源推荐[J].计算机科学，2014，41（1）：69?71.
CAI Q， HAN D M， LI H S， et al. Personalized resource re?commendation based on tags and collaborative filtering [J]. Computer science， 2014， 41（1）： 69?71.
[8] 刘胜宗，廖志芳，吴言凤，等.一种融合用户评分可信度和相似度的协同过滤算法[J].小型微型计算机系统，2014，35（5）：973?977.
LIU S Z， LIAO Z F， WU Y F， et al. A collaborative filtering algorithm combined with user rating credibility and similarity [J]. Journal of Chinese computer systems， 2014， 35（5）： 973?977.
[9] 俞琰，邱广华. 融合社会网络的协同过滤推荐算法研究[J].现代图书情报技术，2012，28（6）：54?59.
YU Y， QIU G H. Research on collaborative filtering recommendation algorithm by fusing social network [J]. New technology of library and information service， 2012， 28（6）： 54?59.
[I0] SARWAR B M. Sparsity， scalability and distribution in recommender systems [D]. Minneapolis， USA： University of Minnesota， 2001.
[11] HERLOCKER L J， KONSTAN A J， RIEDL T J. Empirical analysis of design choices in neighborhood?based collaborative filtering algorithms [J]. Information retrieval， 2002， 5（4）： 287?310.
