基于萤火虫聚类的协同过滤推荐算法

魏涛 刘亚军 叶传标 曹阳

摘要：针对基于聚类的协同过滤推荐算法在进行聚类代价函数优化时容易陷入局部最优的问题，将具有良好全局最优搜索能力的萤火虫优化算法与聚类算法相互结合，提出一种基于萤火虫聚类的协同过滤推荐算法，实验结果表明，所提出的算法优于基于聚类的协同过滤推荐算法，其推荐准确率更高，完成实时推荐所花费的时间更少。

关键词：协同过滤;推荐系统;聚类;萤火虫算法

中图分类号：TP391 文献标识码：A

文章编号：1009-3044（2019）33-0289-03

1概述

随着电子商务中的商品种类和数量快速增长，为便于客户快速选中心仪的商品，推荐系统应时而生。协同过滤推荐技术是推荐系統中的一个重要技术，该技术基于已有客户群过去的商品选择数据，去预测某个客户最可能感兴趣或者喜欢的商品。

协同过滤技术目前已经在推荐系统中得到广泛应用，该技术不依赖于商品本身的信息，当商品信息残缺时，仍然可以根据最近邻客户的评价值进行推荐，但该技术也存在数据稀疏和冷启动问题，尤其是当电子商务中客户数量急剧膨胀时，在较大的客户空间上搜索最近邻客户将变得非常耗时，这使得推荐系统的实时性等性能指标难以得到保证。

为了缩小客户搜索空间，国内外一些研究者将聚类技术引人协同过滤推荐算法中，提出了一些协同过滤推荐算法的改进算法，这些改进算法先将客户按照对商品评价的相似性进行聚类，接着判断目标客户所属的聚类，最后在其对应或邻近的聚类中进行最近邻客户的搜索，从而缩小了客户搜索空间，保证了推荐系统实时性等性能指标。

虽然这些基于聚类的协同过滤算法提高了推荐系统的推荐性能，但这些算法中使用的聚类算法容易陷人局部最优而达不到全局最优。为此，本文提出一种基于萤火虫聚类的协同过滤推荐算法，萤火虫算法属于群智能优化算法，它通过萤火虫群体中每个个体间信息交互合作来寻优，其良好的全局最优搜索能力能够使基于客户聚类的协同过滤算法中的聚类代价优化函数容易陷入局部最优的不足之处得到解决。

2基于萤火虫聚类的协同过滤推荐算法

2.2客户集合k均值聚类

利用k均值聚类将客户集合u划分为k个簇来缩小客户搜索空间，首先随机选取k个客户作为k个簇的初始聚类中心，然后计算每个客户与这些聚类中心的距离，把每个客户分配给距离最近的聚类簇，分配客户后聚类簇的中心将重新计算。以上过程重复迭代进行，最终目的是使得聚类代价函数最小，聚类代价函数如式（3）所示，其定义为各个客户距离所属簇中心点的误差平方和。

2.3萤火虫算法

萤火虫算法是一种利用自然界中萤火虫发光行为所设计出的群体搜索智能优化算法，这种算法用萤火虫来模拟搜索空间中的点，通过亮度低的萤火虫向亮度高的萤火虫移动来求得最优解，亮度和吸引度是萤火虫算法的两个重要参数。

萤火虫算法中的亮度参数表示萤火虫所表示解的优劣程度，亮度越高，表示萤火虫所代表的解越好，亮度低的萤火虫因被吸引向亮度高的萤火虫移动，故而，萤火虫的亮度参数决定萤火虫的移动方向，萤火虫算法中的吸引度参数表示被吸引萤火虫移动量的数值，萤火虫算法的亮度、吸引度公式如式（4）、（5）所示。

由图1所示，当最近邻个数较小时，两种算法的平均绝对误差MAE均较大，随着最近邻个数的增多，两种算法的平均绝对误差MAE均逐渐减小，本文所提出的基于萤火虫聚类的协同推荐算法比基于聚类的协同过滤推荐算法的平均绝对误差MAE低。

为了测试本文所提出算法的实时性性能，在测试实时性性能的实验中，最近邻个数为30，聚类的数目以15为间隔，依次从15增加到150，基于聚类的协同过滤推荐算法与本文所提出的算法完成实时推荐所花费时间的实验结果如图2所示。

由图2所示，当聚类数目较小时，两种算法完成实时推荐所花费的时间均较大，随着聚类数目的增多，两种算法完成实时推荐所花费的时间均逐渐减小，本文所提出的算法完成实时推荐所花费的时间比基于聚类的协同过滤推荐算法完成实时推荐所花费的时间少。

4总结

本文提出一种基于萤火虫聚类的协同过滤推荐算法，该算法通过萤火虫群体中每个个体间信息交互合作来寻优，从而解决了基于聚类的协同过滤算法中的聚类算法代价优化函数容易陷入局部最优的缺点，实验结果表明，本文所提出的算法比基于聚类的协同过滤推荐算法推荐准确率更高，完成实时推荐所花费的时间更少。