基于Python的关联规则算法在推荐领域的应用研究

韩潞潞 刘念 王枫

摘 要：如今，推荐系统在国内各大网站应用非常广泛，可以让用户在更短的时间内去获得需要的信息，提高用户的体验。传统的推荐系统多采用协同过滤算法来进行推荐，由于其在计算项目相似度时没有考虑到项目之间的内在联系，但是现实生活中项目之间是可以分类的，具有一定的内在联系。所以针对此问题本文提出了一种改进算法。改进算法的重点在于应用关联规则算法（FP-growth），挖掘出项目之间的强关联规则，然后在具有强关联规则的项目之间进行重点推荐。将本算法在雅虎音乐数据集上进行了实验验证，结果证明，改进的算法提高了推荐的准确性。

关键词：Python 协同过滤 FP-growth

中图分类号：TP31 文献标识码：A 文章编号：1672-3791（2018）01（b）-0023-03

随着近几年移动互联网的快速发展，手机作为移动互联网的终端设备，几乎成为人人必备的电子产品。人们通过手机可以进行各种活动，例如手机支付、网上购物、新闻浏览和在线学习等，手机已经成为人们获取信息和产生信息的主要媒介。而且，伴随着移动互联网的快速普及，信息出现爆炸式的增长，使得人们从海量信息中准确发现自己感兴趣的项目也越来越困难，于是，项目推荐问题已经变的越来越突出[1]。

目前常用的推荐算法是协同过滤算法。协同过滤算法以其简单的思想理念广受研究者的喜爱。然而由于移动互联网的快速发展，信息积累越来越多，也越来越复杂。此时如果使用传统的协同过滤算法，使得其构建的矩阵越来越大，同时矩阵也越来越稀疏。因为难以在大矩阵中找到高质量的最近邻，所以使得推荐系统的准确性快速下降。

随着推荐问题越来越明显，如何在海量数据集中寻找到用户喜欢的信息已经变的越来越重要。因此也吸引了很多研究者投入推荐算法的研究中，同时也取得了很多成就。有的人通过将多维稀疏向量转换成三维特征向量，然后采用云模型方法来进行推荐[2]。

由于现实生活中项目之间是可以分类的，具有一定的内在联系。所以针对此问题提出了一种改进算法。改进算法首先应用关联规则算法（FP-growth），挖掘出项目之间的强关联规则，然后在具有强关联规则的项目之间来产生推荐，从而提高推荐的准确性。

1 技术简介

1.1 关联规则

关联规则是形如X=>Y的形式，其在一定程度上可以表示喜欢X的人也在很大的程度上喜欢Y，即如果一个人购买了项目X，那他也会在很大程度上去购买Y。Apriori算法作为关联规则的数据挖掘算法之一，是由RAgrawal和RSrikant在1994年提出的，该算法的基本原理是：如果一个项集是非频繁集，那么它的所有超集也是非频繁集[3]。后来，在Apriori算法的基础上，Luan Ru-peng[4]等人通过挖据数据集中项集之间的关系提出了FP-growth算法。FP-growth是目前比较流行的算法，是基于Apriori构建的。FP-growth算法的優势在于建立FP树时只需要扫描两次数据集，因而FP-growth算法执行效率要比Apriori高很多。FP-growth在很多领域都有其优势，如推荐系统，社交网络等[5]。

1.2 Python

Python作为一门动态语言，以其简洁方便的语法和丰富的类库深受研究者的喜爱。基于庞大的开源社区的支持，使得其包含的类库越来越多，越来越高效。从而可以使得研究人员从细节中解脱出来，可以更加专注于个人领域知识的研究。本论文中所涉及的算法采用Python语言来进行实现，提高了效率。

2 结合关联规则的协同过滤改进算法

2.1 相似度的计算方法

计算相似度的方法主要有以下3种。

（1）余弦相似度。

sim（Ii，Ij）=cos（Ii，Ij）= （1）

（2）person相关系数。

sim（Ii，Ij）=person（Ii，Ij）= （2）

（3）修正的余弦相似度。

sim（Ii，Ij）=cos（Ii，Ij）= （3）

其中Ii，Ij表示项目i和j，UAij表示同时对i和j进行过评分的用户集合，Wk，i表示用户k对项目i的评分，Wk，j表示用户k对项目j的评分，Ii表示用户对项目i的评分的平均值，Ij表示用户对项目j的评分的平均值，Uk表示用户k已评分项目的平均值。

2.2 协同过滤算法问题

协同过滤算法首先在数据集上采用2.1节中相应的相似度的计算方法来构建用户-项目偏好矩阵，然后求出目标用户的邻居用户，最后根据其相邻的用户的偏好信息来进行推荐。在表1中，是5个用户对6个项目的评价，其中项目I1，I3，I6是属于流行音乐，I2，I4，I5是属于古典音乐。用户项目评价矩阵如表1所示。

现在要预测C5，6的值，首先我们根据2.1节中列出的person相似度计算方法，然后根据表2中列出的信息可以求得U5用户与其他用户的相似度，如表2所示。

从表2中可以知道，U4的相似度最高，因此选择U4作为U5的最近邻。经过对原始数据的分析，选择U4作为最近邻，是因为他与U5在古典音乐方面的行为极其相似。用古典音乐的相似性来推荐属于流行音乐的项目，推荐结果也将受到质疑。也就是说，我们拿那些在其他类别上与我们有相似爱好的项目去推荐这个类别的项目，推荐精准度将大打折扣。

2.3 结合关联规则的协同过滤算法

通过2.2节的分析，可以得出协同过滤算法在类别具有明显差别的数据集中推荐效果并不好，因为其没有考虑项目之间的类别差异，只是适用于在类别不明显的数据集中进行推荐。然而，现实生活中，由于人们的关注点不同，而项目的目标人群也不同，因此在大多数应用场景下，项目之间是具有明显差异的。现实生活中绝大多数用户感兴趣的项目往往只是在可数的几个类别中，如果在同类别的项目之间进行推荐，可以提高推荐的准确性。

首先，将项目进行关联分析，然后找出与预测项目同类别的其他项目，形成具有一定相关关系的集合。然后，在该集合中寻找该项目的近邻。

经过分析，由于项目是可以进行分类的、是具有一定的类别性的，而协同过滤算法在类别明显的数据集上推荐精准度不高，从而提出了一种改进策略。

2.4 算法设计

改进算法首先使用FP-growth对项目进行分类。然后在此结果上再进行推荐。其流程如下：

（1）事务集合。在用户-项目矩阵中，假设I={I1，I2，…，In}是项目所在的集合，n为项目总的数目，用户Ui评价过的项目集合记为Ti，将其组合形成数据集T={T1，T2，…，Tk}。

（2）强关联规则。对（1）产生的事务数据集T作为FP-growth的输入，然后依据经验设定阀值，求出频繁集，得到具有强关联规则的项目集合。

（3）计算推荐值。根据上一步产生的结果，求出用户对项目的预测值。①遍历上一步形成的结果，查询所有包含项目j的频繁项集，求并集形成相关项目类U，然后在原始数据集中提取出所有用户对项目集合U的评价信息，形成基于相关项目的用户-项目矩阵。②在①形成的矩阵中计算项目的相似度。采用person相似度计算公式（见公式2）。

（4）形成推荐。计算项目预测值的公式如公式（4）所示。

Predictionm，j= （4）

其中Umi代表用户m对项目i的评分，sim（i，j）代表项目i和j的之间的相似度。

根据公式（4）来计算出该用户对未评分过的项目的预测值，取预测值最高的前几个推荐给用户。

3 实验方案设计

3.1 实验数据集

本实验数据来源是雅虎音乐公开提供的数据集。雅虎音乐是第一个提供给个人的网络音乐电台，其数据库中保存了成千上万首的歌曲。它是在线流媒体的先锋。雅虎音乐是曾经排名最高的在线音乐网站。用户可以将歌曲、艺术家、专辑甚至流派进行评分。这些评分使得雅虎音乐可以根据音乐的类别或其他相似用户推荐的音乐来匹配这个用户的音乐爱好。

数据集收集了在1999—2010年期间1，000，990用户对624，961音乐项目的262，810，175评分记录。在整个数据集中，每个用户和每个项目至少包含20条的记录数。数据集被划分为训练集和测试集，测试集中包含了每个用户至少对6个项目的评分记录。

图1所示展示了每个项目评级数量的分布和每个用户评级数量的分布。这两个分布图表现出明显的幂律特征的长尾流行项目和非常活跃的用户，具有很强的稀疏性。

3.2 数据预处理

为了方便实验，对数据进行以下的处理：（1）对原始数据进行转换，去掉和本实验无关的标签（例如时间字段），形成原始数据集。（2）为了寻找频繁项集，需要把数据转换成FP-growth算法需要的数据格式（用户对项目的事务信息）形成新的文件，成为FP-growth算法的输入。

3.3 实验方案

（1）将用户对项目的事务信息作为输入，设置最小支持度作为FP-growth算法的输入，最后把形成的频繁项集存入mysql数据库中。（2）遍历测试数据集，对于测试数据集的每一项，把用户和相应的项目作为输入，查询mysql数据库，然后形成与该项目关联的项目集合。（3）遍历原始数据集，找出用户对上一步形成的项目集合评分的数据，形成用户和关联项目的评分矩阵。（4）把该矩阵和第二步用户的编号来作为输入，用皮尔森相似度来计算项目与项目之间的相似度。（5）根据用户对最近邻项目的评分来预测对该项目的评分。（6）把测试数据集中该用户对该项目的评分与该预测值求差值的平方。（7）求出数据集的RMSE（均方根误差）。

3.4 算法评价指标

根据常用的推荐系统性能指标以及大多数社会推荐系统的研究论文中利用的评测指标，本论文采用均方根误差、覆盖率和准确率来对算法来进行性能优劣的评估。

3.5 实验结果与分析

本文采用基于用户的协同过滤（User-CF）算法和基于项目的协同过滤（Item-CF）算法来作为对比实验，得出结果并进行比较。最终的结果如表3所示。

由于本实验的数据集采用的是百分制的评分，所以均方根误差比较大。通过與Item-CF和User-CF这两个算法的实验结果比较可知，使用关联分析和传统的协同过滤算法的结合有效地降低了预测评分误差，提高了推荐的准确性。这是因为利用关联分析之后，在相似的项目之间进行推荐，将使得预测评分更加客观、合理。

4 结语

本文针对传统协同过滤算法的不足，结合FP-growth去挖掘项目之间的内在联系。在本算法中，最小支持度阀值需要根据经验或者迭代来寻找最优解。下一步工作是考虑如何改进FP-growth中输入参数最小支持度的设定，以及如何在数据集上找到最优的最小支持度参数。

参考文献

[1] 欧立奇.协同过滤在电子商务推荐系统中的应用研究[D].西安：西北大学，2006.

[2] LuoR，Xue Q.Study on the user preferences based on cloud model[A].2009 2nd International Conference on Power Electronics and Intelligent Transportation System（PEITS）[C].2009（3）：268-270.

[3] 陈小华，赵捧未.基于关联规则的个性化信息检索系统研究[J].情报科学，2006（6）：915-918.

[4] Luan Ru-peng，Zhang Qian，Zhang Jun-feng，et al.An association rule discovery algorithm applicable to Web log mining[J].Computer Applications and Software，2013，30（1）：114-116，225.

[5] 卫华.数据挖掘在电子商务推荐系统中的应用与研究[D].西安：西安科技大学，2013.