基于自适应布谷鸟聚类搜索的推荐系统算法的研究

胡安明

摘要：推荐系统本质是一种信息检索技术，能根据用户喜好在海量数据中检索出合适数据推荐给用户，传统推荐系统一般使用协同过滤推荐算法，协同过滤推荐算法主要通过挖掘用户的历史行为数据进行推荐，但传统推荐算法存在着稀疏矩阵、冷启动、实时性等问题困扰[1];因此，本文提出一种基于自适应布谷鸟聚类搜索的改进推荐系统算法，首先对推荐数据进行聚类处理，然后利用布谷鸟算法较强的全局搜索能力，提升推荐系统的准确度，实验结果表明，引入自适应布谷鸟聚类搜索能对传统协同过滤算法在推荐精度、召回率等方面指标方面有一定提高，计算效果优于传统推荐算法。

关键词：布谷鸟搜索算法;推荐系统;聚类

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

文章编号：1009-3044（2022）06-0087-02

开放科学（资源服务）标识码（OSID）：

近年来，随着软件技术和大数据技术的不断发展，基于大数据平台的服务推荐系统技术应运而生生，推荐系统技术针对每位用户提供个性化推荐服务。解决了海量数据情况下，信息过载问题;但如何让用户高效精确的访问到所需的资源，减少搜索时间;如何根据用户的个人历史行为数据，结合网络资源情况，挖掘用户偏好特点，有效地处理推荐用户所需的信息资源，仍是目前推荐系统研究的热点。

传统推荐算法采用协同过滤算法进行推荐，其原理为：挖掘出数据集中与目标用户具有相同的兴趣爱好、消费行为或社会属性的用户数据，将这些用户感兴趣的物品推荐给目标用户[2]。但随着数据规模的扩大，海量的信息资源，协同过滤算法需要计算整个项目中所有用户的数据进行查找推荐，这一过程这就存在着耗时过高，同时海量数据也造成稀疏矩阵，推荐精度下降等问题[3]。因此，必须引入其他智能算法改进推荐系统算法。

1 布谷鸟搜索算法

布谷鸟搜索（Cuckoo Search，CS）算法是Xin-She Yang 等于2009 年在群体智能技术的基础上提出的搜索算法，CS算法是依据布谷鸟在其他鸟巢中的育雏行为与其他它鸟类的莱维飞行（Levy flight）行为的元启发类算法，CS算法具有很强的搜索能力，相比其他算法而言，CS算法输入参数少，结构简单，易于实现等有点。但CS算法也存在着局部搜索能力差，搜索后期收敛速度慢等缺点。因此，在原始CS算法基础上进行改进，以适应应用的需求是必须要的。本文使用自适应布谷鸟聚类算法（ K-means Adaptive Cuckoo Search，K-means ACS）与推荐算法相结合，改进推荐系统中存在的长尾分布等问题，提升推荐系统的精度，提升推荐系统效率。

CS算法实现是来源于布谷鸟寄生繁殖行为，在自然界中布谷鸟在寄主鸟鸟巢中产卵繁衍后代，布谷鸟通过模仿寄主鸟蛋的颜色和图案或选择合适的时间进行产卵增加后代生存率，布谷鸟寻巢过程就是莱维飞行（Levy flight），莱维飞行是一种随机行走。

CS算法实现过程就是将现有的寄主鸟巢看作一代，将卵随机产在寄主鸟巢。目标就是通过不断的多次迭代寻找出潜在最优鸟巢替代现有鸟巢[4]。CS算法实现过程如下：

（1） 布谷鸟每次产一枚卵，假设有N个鸟巢，原始位置为[Xi=（1，2，3，…）]，寄主鸟发现概率值：[Pa∈（0，1）]，对算法迭代次数和问题维度进行初始化。

（2） 对所有鸟巢位置计算，获得所有鸟巢位置的函数值，计算所有鸟巢函数值后，对比所得适应度函数值，找出最优函数值，利用莱维飞行的随机步长计算公式如式（1）：

[xt+1，i=xt，i+a0⊗Levy（β）]        （1）

其中[xt+1，i]表示，第[i]个鸟巢的[t+1]代的更新位置，[xt，i]表示第[i]个鸟巢的[t]代的位置，[a0]表示步长缩放因子，[⊗]表示卷积运算操作，[Levy（β）]表示莱维飞行，[β]表示莱维飞行的控制因子。

（3） 其中莱维飞行的路径具有随机性，Mantegna在1994年提出一种用正态分布对莱维飞行进行求解，计算公式如式（2）：

[Levyβ=Φ×uv/β]                     （2）

其中u，v为正态分布随机量，一般情况下取值在1.5，[Φ]计算过程如式（3）：

[Φ=（Γ（1+β）×sin （π×β/2）β×Γ（1+β2）×2（β-1）/2）1/β]               （3）

其中[Γ]为标准的Gamma函数，综上所述鸟巢的位置计算如式（4）：

[xt+1，i=xt，i+a⊗Φ×uv/β]    （4）

其中a表示步长缩放因子，为（0，1）间的平均分布随机数;算法通过全局随機搜索更新每个鸟巢位置，然后依据寄主鸟发现概率值：[Pa]对一部分分解淘汰，再通过局部随机搜索对淘汰值进行更新[5]。

2 、自适应布谷鸟搜索算法

CS 算法通过模拟布谷鸟的寄生繁衍策略来寻找最优解。在算法求解过程中，是通过莱维飞行来确定下一次飞向的鸟巢位置，莱维飞行随机步长越长，则搜索的精度越低，越容易搜索全局最优解;飞行步长越短，则会提高搜索精度，但会严重影响搜索速度;一般莱维飞行步长通过控制因子a进行控制，但a一般取固定值，这就导致CS算法迭代后期，莱维飞行步长变大，使得算法不易收敛;因此，为了能够自动适应搜索步长的变化，均衡CS算法的搜索步长，提高算法收敛速度，文献[6]提出一种自适应调整步长缩放因子的调整策略算法，算法过程如式（5）：

[ai=1tal+au-alFmax-FiFmax-Fmin;i=1，2，…，n] （5）

其中，[al]为预定最小步长因子;[au]为预定最大步长因子：[Fi]为当前鸟巢位置，[Fmax]为本次迭代中鸟巢位置最大值：[Fmin]为本次迭代中鸟巢位置最小值，t为当前迭代次数。

3 基于K-means聚类和自适应布谷鸟搜索的推荐系统算法实现

传统推荐算法采用协同过滤算法进行推荐，该算法的实现过程是：通过用户与待推荐物的历史行为数据，构造协同过滤矩阵，通过每一行用户对物品的评价，和每一列所有用户对物品的评价，进行协同过滤计算，从中筛选出用户可能感兴趣的物品。但随着数据规模的扩大，海量的信息资源，协同过滤算法需要计算整个项目中所有用户的数据进行查找推荐，这一过程这就存在着耗时过高，同时海量数据也造成稀疏矩阵等问题，导致推荐精度下降等问题。

因此，引入K-means聚类和自适应布谷鸟搜索算法改进推荐系统算法（K-means ACS），实现过程如下：

（1） 提取用户特征数据，随机选取n个样本作为聚类中心点，对用户数据进行聚类;

（2） 逐个检查每个聚类样本与用户间的距离，确保差异小的用户聚到一类;

（3） 确定用户数据聚类数n，即确定n个鸟巢并初始化，及最大迭代次数[Iterator]，发现概率P，最大步长[Fmax]，最小步长[Fmin];

（4） 进行聚类划分，计算每个鸟巢的适应度值，找出最优鸟巢;

（5） 应用式5自适应布谷鸟搜索算法对其他鸟巢进行搜索更新;

（6） 重复4、5两步，通过自适应布谷鸟算法优化更新所有鸟巢，即聚类;

（7） 直至迭代次数达到最大[Iterator]迭代次数。

算法实现过程，如图1所示：

实现过程

4 实验结果分析

本实验软件环境为：Windows10操作系统、Python3.7，硬件环境为：Intel 2.9GHz CPU、16GB RAM、硬盘500GB。实验数据选择MovieLens 1MB版本数据集，该数据集是美国明尼苏达大学GroupLens小组建立的电影影评数据集，共收录了6，040余名用户，3706部电影的100万条评论数据，每条评论包含有发表评论时间。

本文采用绝对平均误差MAE对算法进行评估，计算公式如式（6）所示，其中[rui]为用户u对物品i的实际评分，[rui]为用户u对物品i的推荐预测。

[MAE=1n1nrui-rui] （6）

测试对不同聚类数n情况下进行算法验证，根据MAE值判断寻找出最优聚类个数，聚类个数n取值2～70范围，从图2中可以看出聚类个数在64个时MAE值最低，达到最优。

K-means聚类和自适应布谷鸟搜索的推荐系统算法（K-means ACS）与传统ItemCF算法相比，在MovieLens 1MB数据集上，Top-N值分别取10，20，30的情况下，MAE值情况如表1所示：

从实验结果分析：本文使用MovieLen 1 MB数据集，在Top-N为20时下K-means聚类和自适应布谷鸟搜索算法改进推荐系统算法对传统协同过滤算法在MAE指标方面有一定提高，计算效果好于传统推荐算法。

5 结论

本文针对传统推荐系统算法协同过滤的推荐过程中存在的问题进行分析，在此基礎上引入布谷鸟搜索算法，对布谷鸟搜索算法的原理及实践应用存在的问题进行分析，引出自适应布谷鸟算法;在此基础上提出一种K-means聚类和自适应布谷鸟搜索的推荐系统算法，并详细论述了该算法的实现过程。通过实验分析，基于K-means聚类和自适应布谷鸟搜索的推荐系统算法对传统推荐算法有一定改进效果，为传统的协同过滤算法的改进提供了一些思路。

参考文献：

[1] 王国霞，刘贺平.个性化推荐系统综述[J].计算机工程与应用，2012，48（7）：66-76.

[2]苏庆，章静芳，林正鑫，等.改进模糊划分聚类的协同过滤推荐算法[J].计算机工程与应用，2019，55（5）：118-123.

[3] 张玉洁，杜雨露，孟祥武.组推荐系统及其应用研究[J].计算机学报，2016，39（4）：745-764.

[4] 张燕，袁书卷，达列雄，等.基于局部搜索增强策略的自适应反向学习布谷鸟算法[J].数学的实践与认识，2020，50（20）：191-200.

[5] 向庭立，王红军，史英春.基于布谷鸟搜索的混合传感器网络覆盖优化策略[J].计算机工程，2019，45（12）：79-85.

[6] 杨辉华，王克，李灵巧，等.基于自适应布谷鸟搜索算法的K-means聚类算法及其应用[J].计算机应用，2016，36（8）：2066-2070.

【通联编辑：闻翔军】