基于布谷鸟搜索的聚类推荐算法研究综述

刘姣

摘 要：目前推荐系统研究面临的主要问题是如何提高推荐准确度和用户满意度。为克服原始推荐算法和现存改进算法的局限性，利用一种具有较强全局搜索能力的智能优化算法——布谷鸟搜索算法，结合K-means聚类算法进行改进。在此基础上，设计了应用于Movielens数据集基于布谷鸟搜索的聚类推荐系统总体框架，对其中关键技术和目前存在问题进行了分析，并指出接下来需开展的研究工作。

关键词：推荐系统;布谷鸟搜索;K-means算法;智能优化算法

DOI：10. 11907/rjdk. 182830

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）004-0091-04

0 引言

推荐系统已成为电子商务应用中不可或缺的组成部分。推荐算法作为推荐系统的核心内容，算法性能优劣直接影响系统推荐的信息准确性。因此，各学者提出了许多性能优越的推荐算法，为用户提供更准确、更高效的推荐服务，协同过滤算法是推荐系统领域应用最广泛也是最成功的推荐算法，但是仍然存在数据稀疏性、算法可扩展性与冷启动等许多问题。随着推荐系统规模不断扩大，协同过滤算法推荐时需要在整个用户空间或项目空间查找目标最近邻居，这一查找过程将随着系统中用户和项目不断增多而变得十分耗时，从而导致推荐系统的实时性难以保障。然而，推荐系统的评分数据一般十分稀疏，又会导致协同过滤算法的推荐精度变差。文献[1-2]介绍了协同过滤算法的一些研究情况。近年来许多学者将数据挖掘中的聚类算法引入推荐系统，通过对用户或者项目进行聚类以缓解上述问题[3]。由于同一个类中各用户或项目之间相似度较大，因此在搜索最近邻时只需要搜索与目标最相近的几个类即可，从而缩小了搜索空间，大大提高了最近邻的搜索效率，而且还能有效保证推荐结果的准确度。K-means算法因其典型的基于划分思想，具有易于实现、思路简单、收敛速度快、时间复杂度接近线性等优点，但仍主要存在以下两个问题：①若初始聚类中心选取不恰当，则易导致聚类结果陷入局部最优，因而影响聚类准确率;②当数据量较大时，串行算法的计算能力有限，效率太低，无法快速响应用户需求。

针对以上问题，科研人员对K-means算法尝试了多种行之有效的改进方法[4-9]，也将改进算法与推荐算法结合[10-14]。布谷鸟搜索算法（Cuckoo search algorithm，CS）是一种元启发优化算法，能够在局部搜索战略与整个搜索空间的高效探索之间保持好平衡，常用于求解各类优化问题，非常适用于提高K-means 算法的全局寻优能力，不仅可以提高推荐准确率，而且可以提高推荐结果的覆盖率，从而减小推荐系统的马太效应[15-18]。

1 K-means聚类算法概述

K-means聚類算法的基本思想是：首先把每个聚类样本的数据均值作为初始聚类中心点，利用这些中心点进行新类别构造。然后进行算法的不断迭代，在每次迭代时都对数据重新规划，直到划分出的聚簇满足准则函数最优解。K-means算法对具有连续型属性的数据处理得比较理想。具体执行流程为：

输入：X={xm|m=1，2，…，n}表示的数据集，不过数据样本并没有包括类别属性，而只包括描述属性;聚类数量k。

输出：满足方差最小标准的k个聚类。

处理流程：

（1）从数据集X中随机抽取k个样本并将其视为最初聚集中心，每个中心分别表示一个类别。

（2）遍历X中的其它样本，分别计算它们与k个最初聚类中心的距离，找出距离最近的聚类中心，然后将其划分到该聚类中心所代表的类中。

（3）迭代（1）、（2）执行过程，等到所有聚类不再发生变化时终止迭代。

K-means算法中的k一般需要提前给出，如果刚开始聚类子集的个数不明确，可以对多个k值尝试使用K-means算法。结果表明，k值变大过程中误差平方和准则函数值随之变小。最终，可以依照准则函数曲线的变化情况和以往经验，推测出一个较理想的k值。

2 布谷鸟搜索算法概述

布谷鸟搜索算法是由英国学者Yang等[19-20]提出的一种元启发算法。它主要源于布谷鸟巢寄生繁殖行为和列维飞行（Levy flights）搜索机理。巢寄生是指某些鸟类将卵产在其它鸟的巢中，由其它鸟代为孵化和养育幼鸟的繁殖行为，某些类别布谷鸟就是采用这种方式繁衍后代的。在繁殖期间，布谷鸟不筑巢，而是寻找与孵化期和育雏期相似、雏鸟食性相近、鸟蛋形状和颜色也比较类似的宿主，寻找到合适宿主的巢之后，会趁宿主离巢外出时快速产卵，并让宿主鸟代替自己孵化幼鸟。通常，布谷鸟只在一个寄生巢里产一枚蛋，而且之前会把宿主鸟蛋移走或全部移出巢外。列维飞行是动物界一种觅食随机游走的方式，游走步长满足一个重尾的稳定分布，在游走过程中，短距离探索与偶尔长距离行走相间，它也是一种最为理想的觅食搜索方式，在智能算法中采用列维搜索方式能够克服容易陷入局部最优解的缺点。

3 基于K-means与cuckoo的协同过滤推荐框架

为了克服协作推荐系统的局限性，设计了一种混合聚类与优化算法的技术以提高推荐准确性。使用K-means作为聚类算法和布谷鸟搜索作为优化算法，最初将K-means聚类算法用来处理数据集，以便将用户聚类到不同集群中。首先随机选择聚类中心，然后通过计算其评级和聚类中心的差异逐一检查用户，如果差异最小，则该用户被分配到其最接近的集群。但是，此时不能确保每个用户都被分配到具有最小聚类中心差异的真实集群。因此，将每个用户的距离与其集群平均值进行比较，并与其它集群进行比较，用与任何集群平均值的最小距离表示并重新定位用户，然后进行算法的不断迭代，在每次迭代时都对数据重新进行规划，直到划分出的聚簇满足准则函数最优解。

下一步将布谷鸟搜索优化算法应用于k均值算法结果，以优化结果。

使用适应度函数准备聚类，该函数有助于改善用户的质心距离，而适应度函数在有限次数迭代中改变先前的质心（将质心重新定位到用户）。然后，通过计算最小质心差异或应用k均值再次对用户进行分类。布谷鸟搜索算法可以使用以下3个理想规则描述：①设定每只布谷鸟每次只产下一个蛋，并且对放入蛋的鸟巢选择是随机的;②将能够最好地孵化蛋的鸟巢即最优巢保留到下一代;③布谷鸟能选择的可用于放蛋的宿主巢数量是固定的，且宿主发现布谷鸟放的蛋非亲生的概率为Pα∈（0，1）。

在框架中，将每一个用户视为鸟蛋，每个嵌套都可以看作一个簇。图1展示了布谷鸟搜索算法的基本步骤。该过程从初始化开始，其中引入n个宿主巢的随机群体，并且获得列维飞行行为方程，然后使用适应度函数获得适应度以求得最优解。Lévy飞行是随机游走，其中步长根据Lévy分布，可以借助拉普拉斯和傅立叶变换计算步长与Lévy稳定分布。它已经在布谷鸟优化算法中实现，飞行长度为x（N）～N1/α，其中0<α<2，x是随机变量，N是步长。布谷鸟行进距离可以使用上述等式计算每次迭代。选择一个随机的巢，比如j，然后比较布谷鸟蛋（进入新的解决方案）的适合度与巢中宿主蛋的适应度。在这种情况下，布谷鸟蛋的适应度函数值小于或等于随机选择的嵌套适应度函数值，然后随机选择的嵌套j由等式（1）中给出的新分辨率替换。

当适应度函数值趋于零时，解之间的偏差随着迭代次数增加而减少，并且如果布谷鸟蛋与正常蛋相似，则主鸟难以区分蛋。适应性是解决方案的不同之处，如果布谷鸟蛋的适应性大于随机选择的巢，则新的解决方案被随机选择所取代，宿主鸟可以区分宿主和布谷鸟蛋。

总地来说，本文方法包括K-means聚类技术，通过生物启发算法——布谷鸟搜索进行优化。图2给出了框架伪代码。

通过兴趣相似性对用户进行分类的聚类类似于宿主鸟巢，并且每个蛋类似于布谷鸟优化算法中的用户，最初分类的用户被认为是寄主鸟蛋，选择一些随机用户初始化集群（嵌套）。初始化集群并实施K-means以对最初选择的用户进行分类，如算法中所示。未选择的用户是随机选择的。对于每个随机选择的用户，随机选择一个簇和适应度函数。根据计算该用户适应度函数，宿主鸟可以检测到蛋（用户），或者它可以保留在巢中。一旦布谷鸟蛋孵化，它就会试图将其它蛋随机地从巢中扔出来。如果布谷鸟蛋适应度优于集群中已存在的多个用户的预定义百分比，则在算法中完成此操作。

图3展示了算法应用于Movielens数据集的流程。通过读取文件，记录Movielens数据集，并且使用k均值聚类到k个聚类中，将数据集划分为聚类，使得每个聚类具有聚类中心。计算用户与聚类中心之间的距离，并将用户放置在聚类中心距离最近的簇中。当所有用户都被重新定位时，重新定位聚类中心并计算新的位置。计算用户给出的估计评级，并且使用布谷鸟搜索算法进行优化。

4 结语

为了改善传统推荐算法的不足，设计了一种基于CS优化算法的聚类推荐算法，本文对K-means聚类算法、布谷鸟搜索算法的研究现状进行了分析。通过利用布谷鸟搜索算法的特性优化聚类推荐算法结果，并给出了基于布谷鸟搜索的聚类推荐系统总体框架。在今后工作中，将进一步对其算法效率进行研究，以获得更好的推荐结果。

参考文献：

[1] 王凌，沈婧楠，王圣尧，等. 协同过滤算法研究进展[J]. 控制与决策，2015，30（2）：193-202.

[2] 陈军，谢卫红，陈扬森. 国内外大数据推荐算法领域前沿动态研究[J]. 中国科技论坛，2018 （1）：173-181.

[3] 王晓耘，钱璐，黄时友. 基于粗糙用户聚类的协同过滤推荐模型[J]. 现代图书情报技术，2015（1）：45-51.

[4] 喻金平，郑杰，梅宏标. 基于改进人工蜂群算法的K-均值聚類算法[J]. 计算机应用，2014，34（4）：1065-1069+1088.

[5] 刘靖明，韩丽川，侯立文. 基于粒子群的K均值聚类算法[J]. 系统工程理论与实践，2005，25（6）：54-58.

[6] 何宏，谭永红. 一种基于动态遗传算法的聚类新方法[J]. 电子学报，2012，40（2）：254-259.

[7] 郭凯，李海芳，王会青. 一种人工免疫的自适应谱聚类算法[J]. 小型微型计算机系统，2013，34（4）：856-859.

[8] 王彩霞. 基于改进引力搜索的混合 K-调和均值聚类算法研究[J]. 计算机应用研究，2016，33（1）：118-121.

[9] 王日宏，崔兴梅，李永珺. 自适应调整的布谷鸟搜索K-均值聚类算法[J/OL]. 计算机应用研究，2018， 35（12）. [2017-12-08]. http：//www.arocmag.com/article/02-2018-12-038.html.

[10] 任帅，王浙明，王明敏. 基于用户行为模型和蚁群聚类的协同过滤推荐算法[J]. 微型电脑应用，2014（3）：5-8.

[11] 冯智明，苏一丹，覃华，等. 基于遗传算法的聚类与协同过滤组合推荐算法[J]. 计算机技术与发展，2014（1）：35-38.

[12] 乔平安，曹宇，任泽乾. 融合隐语义模型和K-meansplus聚类模型的推荐算法[J]. 计算机与数字工程，2018（6）：1108-1111.

[13] 丁小焕，彭甫镕，王琼，陆建峰. 基于平行因子分解的协同聚类推荐算法[J]. 计算机应用，2016，36（6）：1594 -1598+1604.

[14] 郑丹，王名扬，陈广胜. 基于Weighted-slope One的用户聚类推荐算法研究[J]. 计算机技术与发展，2016 （4）：51-55.

[15] GANDOMI AH， YANG X S， ALAVI AH. Cuckoo search algorithm： a meta heuristic approach to solve structural optimization problems[J]. Engineering with Computers，2013;29：17-35.

[16] 李煜，马良. 新型元启发式布谷鸟搜索算法[J]. 系统工程，2012，30（8）：64-69.

[17] FENG D， QI R， LIMIN D U. Binary cuckoo search algorithm [J].  Journal of Computer Applications， 2013， 33 （6）： 1566-1570.

[18] SURESH S， LAL S， REDDY C S， et al. A novel adaptive cuckoo search algorithm for contrast enhancement of satellite images [J].  IEEE Journal of Selected Topics in Applied Earth Observations & Remote Sensing，2017 （99）：1-12.

[19] YANG X S，DEB S. Cuckoo search via lévy flights[C].  Nature & Biologically Inspired Computing，2009：210-214.

[20] YANG X S，DEB S. Engineering optimization by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimization，2010，1（4）：330-343.

（责任编辑：何 丽）