【基于麻雀搜索聚类的协同过滤算法综述9800字】

基于麻雀搜索聚类的协同过滤算法综述目录TOC\o"1-3"\h\u1277基于麻雀搜索聚类的协同过滤算法综述 1181241.1麻雀搜索及相关群智能优化算法 1234201.1.1群智能优化算法 1124841.1.2常见的群智能优化算法 2209431.1.3麻雀搜索算法 5151611.2聚类推荐算法 8194041.2.1聚类概念 8236271.2.2常见的聚类算法 8107731.2.3聚类的评价指标 10125661.3基于麻雀搜索聚类的协同过滤推荐算法 11164881.4实验设计与分析 1313181.4.1数据集 13327051.4.2实验环境 1547681.4.3实验方法与度量标准 15313331.4.4实验结果 15本章根据前文提出的概念和理论，针对电影推荐场景下的数据信息进行算法的研究，提出使用融合群智能优化算法与聚类算法相结合的算法模型。首先对用户聚类，减小算法整体的数据维度，提高最近邻的相似程度。之后提出使用麻雀搜索策略对聚类中心点的选择寻优，解决聚类中心点敏感的问题，从而提高整体的推荐准确度。最后设计实验，在真实的电影评分数据集下验证，最终证明该算法比其他相关推荐算法的推荐准确率更高。1.1麻雀搜索及相关群智能优化算法1.1.1群智能优化算法在自然界中，动物觅食大都采用以集体为单位的群体觅食行为，且随着时间发展和进化，这一群体中个体表现出的行为虽然不同，但通过个体间的互相合作，互相交换信息，解决个体不能完成的任务。1989年，Wang和Beni在文献[41]中，阐述了一种全新的由动物群体行为模式演化而来的算法——群体智能算法。研究人员纷纷对群体智能展开研究，算法将自然界中动物行为建模表达，这个群体是由简单个体组成，它们会按照相互间的简单合作去搜寻并交流信息，从而表现出了智能行为[42]。生物群体的社会性是群智能优化算法的本质，通过模仿种群中的不同行为比如在自然界中，鱼群、狼群、狮群和鸟群的群体觅食行为，通过合理的分工寻找食物，并交流信息，最终找到食物。可以发现群体中的个体都遵循着某些特殊的群体性社会规则。算法在各个领域中得到应用，并成功解决一些复杂的问题。群智能优化依靠其速度快、操作简单、独立性强和扩展性好等优点，越来越被研究者们所关注。群智能优化是一种典型的元启发式策略[43]。元启发策略不需要受制于问题所需要的特定环境。防止算法过早得陷入局部最优值是现在元启发式算法的主要研究问题。根据模拟的生物群体对象的不同，元启发算法可以有以下几种分类，如图1.1所示。图1.1元启发算法分类1.1.2常见的群智能优化算法（1）遗传算法遗传算法[44]是参考自然进化过程，基于自然选择和基因突变的进化遗传模型规则演化而来。也是最早的搜索启发算法。该算法属于启发式算法，算法对于问题的优化过程是来自于生物遗传物质的操作包括三种基本的遗传算子：选择、交叉和变异算子。选择算子，在自然界中，生物群体会受自然环境的影响进行自然选择进化和淘汰，优秀的个体基因会在自然界的筛选下存活下来并传递给后代。于是算法根据个体的适应值去判断个体的好坏，然后根据选择算子择优选取种群中的个体。交叉算子，是模仿自然界的生物交配形成新个体的行为过程。首先从种群中选取两个个体，利用交叉算子对所选择个体基因进行交叉操作，生成的新个体都拥有了新的基因，保持物种的多样性。变异算子，随着自然环境的不断变化，自然界中的生物群体会发生一定概率的基因突变来适应变化的环境。算法根据变异因子使每个个体都有一定的概率发生突变，加速种群的收敛速度。遗传算法易与其它算法结合，但是算法涉及参数较多，且过于依赖初始种群。图1.2遗传算法流程图（2）蚁群算法蚁群优化算法[45]在发表后就应用在了数学领域中。其原理是来自蚂蚁组成的群体觅食行为，每只蚂蚁都会分泌一种信息物质，并且释放在路过的路径上供其他蚂蚁辨识。当其余蚂蚁进行路径选择时就会被这些信息物质所吸引，再通过识别每条路径上信息物质的浓度来选择最优行径方向。所以就会形成一种正反馈，信息物质越多的路径，会吸引越多的蚂蚁，然后留下更多信息物质，逐渐这条路径上的信息物质浓度将会更高，随着信息物质的挥发，会有更过的蚂蚁跟从。这种反馈机制就会帮助蚁群在面临多条路径的时候，通过识别信息物质的变化，最终找到一条最短最优路径。简化这种行为过程：离食物更短的路径上，会有更多的蚂蚁经过，则留下信息物质的浓度就会变高，会吸引其他蚂蚁选择该路径，随之形成正反馈过程，就会找到最佳路径。算法中，蚂蚁个体行为简单，但个体行为间分工却非常明确，个体组成的蚁群拥有高级社会的智能分工组织体系。相互间进行信息的交换，有较强的的全局优化能力。正反馈机制让蚂蚁在觅食选择移动方向的时候，会选择信息物质浓度最高的路径，同时释放信息物质，这样路径上就会积累更高浓度的信息物质，吸引蚁群选择这条路径。图1.3蚁群算法流程图（3）粒子群算法粒子群优化算法[46]是在一个区域内，有一群不知道食物的位置的鸟在随机地搜寻食物。鸟群会根据自身的适应值，和其他鸟交换信息，来分析当前的自身位置是不是离食物更近，并且找到周围食物较多的鸟，通过搜寻其附近区域去快速有效地找到食物。算法是通过将鸟群中的每一只鸟作为一个粒子，粒子群中的每个粒子都拥有两种属性，速度属性决定粒子移动的快慢和移动的朝向，位置属性用粒子当前所在的坐标点表示。粒子搜索到的所有解中最优的个体极值即为粒子群的最优解。算法原理简单，使用操作起来比较方便等优点。但算法收敛时粒子都会向最优粒子移动，从而趋于一致损失掉复杂性。1.4粒子群算法流程图1.1.3麻雀搜索算法麻雀搜索算法是2020年Xue等在文献[47]中提出。麻雀通常是群居的鸟类，种类繁多。它们分布在世界的大部分地区，喜欢生活在人类生活的地方。麻雀群中有两种不同类型的麻雀，发现者和跟随者。发现者积极寻找食物来源，指引跟随者来寻找食物。此外，证据表明，鸟类通常灵活地使用行为策略，并扮演不同的角色。也可以说，为了找到食物，每只麻雀会在发现者和跟随者两种间进行转换。对于麻雀搜索策略，该算法主要有三种行为的麻雀分为发现者、跟随者和警戒者，每种麻雀的行为都不同。麻雀的觅食和反捕食行为遵循以下几条规则：（1）发现者通常有高水平的能量储备。它负责确定可以找到丰富食物来源的地区。能量储备的水平取决于个体的适应度值的评估。（2）当麻雀发现了危险，则为判断危险程度，若超过了安全阈值，则会发出警告信号，麻雀群便会向安全位置移动。（3）算法中发现者、警戒者和跟随者两种，但是其比例不会变，只是每次迭代时按照适应度值随机选择。（4）能量较高的麻雀充当发现者。跟随者通过跟随发现者谁能提供最好的食物寻找食物。（5）处于群体边缘的麻雀会遭遇天敌的袭击，当危险靠近时，麻雀则会放弃食物，飞向更安全的位置继续觅食。 对于规则（1），发现者负责寻找食物位置，通常有较高的适应值，并为所有的麻雀提供最佳觅食位置和移动方向。它负责确定可以找到丰富食物来源的地区。适应度值的高低取决于对麻雀健康值的评估。其他麻雀作为跟随者，跟随者则是根据判断发现者位置食物的多少，来选择往哪一只发现者的位置移动，从而获取食物。对于规则（2），还有部分麻雀会被选择为警戒者，侦察危险，避免被天敌反捕食处在种群边缘的麻雀易受到被天敌捕食的危险，所以会随机选取一定数量的麻雀作为警戒者，来预防危险的发生。发现危险时则迅速发出警告，警告其他麻雀则放弃食物飞往其他安全区域去搜寻食物。当报警值大于安全阈值时，发现者会率先移动，并将所有麻雀引向安全区域。发现者的位置更新公式如下：Xi,式中，t表示当前迭代，j=1,2,…d。Xi,jt表示第t次迭代中i麻雀的所在的j维位置。T是迭代次数最多的常数。α的取值范围为(0,1]，为一个随机数。R2和ST分别代表报警值和安全阈值，取值范围R2∈[0,1]和ST∈[0.5,1]。Q则为标准正态分布的随机数。当对于规则（4），跟随者，一些跟随者麻雀更频繁地监视发现者。一旦发现者找到更好的觅食位置，他们就会从当前所在位置直接跳跃到发现者所在的位置去争夺食物。如果赢了则可以获得食物，否则他们将继续执行跟随能提供最好食物的发现者去寻找食物。跟随者的位置更新公式如下：Xi,jt+1其中，XPt+1是全局最优位置，Xworstt是全局最差位置。A由1或−1随机构成的1×d矩阵，并且针对规则（5），当麻雀在觅食时，会有部分麻雀负责警惕被捕食的危险，当危险信号超标时，他们会发出危险信号警告其他麻雀，向更安全的位置移动。每次迭代都会从种群中随机选取Sn个麻雀变成警戒者来进行警戒。警戒者位置更新公式如下：Xi,其中，β、K是控制移动步长和移动方向的参数变量。fg表示最优适应值，fworst表示最差适应值，ε是最小常数，用来避免零除误差。当fi≠f1.5麻雀搜索算法流程图1.2聚类推荐算法1.2.1聚类概念聚类的核心思想是指按照某种指标将相近的对象聚集到不同的类中的过程，这种划分过程是无监督的，特征相似的对象会被分到同一类群，相差较大的就被分到其他类群。聚类算法的算法过程是：设定初始聚类的簇数和中心点，计算数据与中心点的距离，将与中心距离近或相似度高的样本分到一个聚类簇里，最终划分为几个簇。因此，推荐系统对于搜寻目标用户最近邻之前可以利用聚类技术，将用户按照特征属性的不同进行分簇。目前聚类里面对计算样本特征进行分类使用最多方法是选择测量数据样本间的距离。对于样本不同的属性特征，就用相对应之方法进行相似度的计算。因为通常判断相似程度取决于样本间的距离。其中，x=xii=1,2,⋯,n表示一个数据样本，dxi,xj指代两个样本xi和xj间的距离，d维向量中每个样本x1.2.2常见的聚类算法作为机器学习中的分类模型，聚类算法因其算法原理简单、适应性强，算法不断被研究者们的优化更新，按照聚类中计算的步骤以及底层设计的不同，大致分为以下三类[55]，我们对其进行介绍并给出其算法原理。（一）基于划分的聚类方法该方法是利用事先规定的特征属性将数据集中的数据对象按照距离或其他规则划分到不同的簇类中。首先在算法开始之前，首先需要对聚类簇的数目聚类的中心点进行初始化，之后算法根据规则将每个数据依次划分到对应的簇类，直到算法满足终止条件。聚类算法K-means算法的算法原理是在算法开始之前需要对聚类中心点和聚类簇数进行初始化，对每个数据进行分簇，每次迭代都重新选取簇类中的中心点。算法的具体步骤如下：（1）选取k个聚类中心点，以及最大迭代次数Max；（2）选择划分依据公式，按照公式计算数据与中心点数据的距离，并将其分到最近的簇类中；（3）计算簇内平均值，将这k个平均数作为新的中心点；（4）若聚类指标未满足目标函数或未达到最大迭代次数，则返回步骤（3）；（5）触发终止条件，算法结束。K-means算法一般选取欧氏距离作为目标函数。K-means算法在开始执行时我们无法知道数据大致有哪些类，甚至不知道会被划分为哪一类，所以k值的选择就非常关键；其次聚类算法的初始中心点是算法开始时随机初始化得到的，所以聚类效果的好坏将直接由中心点的选取所决定。（二）基于密度的聚类方法由于基于划分的聚类方法多数以距离作为划分簇类的依据，所以聚类后的结果多数以球形居多。而复杂的数据集往往需要聚类形成各种各样不同的形状，为满足不同的要求，基于密度的聚类应运而生。该种聚类方法的原理是按照数据点的密集程度作为划分簇类的依据，比较常见的是DBSCAN算法。算法在聚类前，不需要特意指定簇数，而是将邻域半径内密度达到某一阈值的区域划分成一簇，噪声点会形成特殊形状的簇，更方便区分。算法需要提前预设邻域半径r和密度阈值ρ。具体步骤如下：（1）初始化：数据集S、邻域范围半径r、密度阈值ρ、核心数据集合P、簇群数目K=0、没被访问过的对象集合Q=S、聚类划分结果C；（2）从S中遍历数据，统计每个数据在邻域半径内出现的数据数，将数据数大于密度阈值ρ的数据加入核心数据集合P中。（3）判断P是否为空，若不为空则输出聚类的划分结果C，否则执行（4）；（4）遍历P，取出P中的一个核心数据xi，建立聚类核心数据集合p+=（5）若p+为空，则执行（6），若不为空则第K个聚类对象集合Ck完成，修改（6）从p+中取出一个数据，找出邻域半径内中其他数据对象个数Nr，并将核心数据加入到p+，更新C（三）基于层次的聚类方法基于层次的聚类方法是计算数据属性的相似度作为划分依据来对数据集分簇。层次聚类可以分为两种：（1）基于凝聚的聚类，每个数据都是单独一类，计算类与类间的相似度，将高相似度的簇合并，直至归为一类，是自下而上的。（2）基于分裂的聚类则是自上而下的，首先计算簇内数据的相似度，判断簇内中相似度的差异，若差异过大，则进行簇类分裂产生两个小簇类，直至达到最大迭代次数或者所有的簇类中都只剩唯一数据时结束。基于凝聚的聚类算法AGNES算法，执行过程如下：（1）初始化：数据集S、簇数K；（2）将数据集中每个数据作为单独一个簇类进行分簇，产生初始簇类集；（3）选取聚类距离公式，计算类间距，合并相近的两个簇；（4）若当前簇数大于等于K，输出结果；否则执行（3）。AGNES算法适用比较广，不局限于数据本身的形状。但是若遇到的数据量太大，则会消耗更多的时间，且在聚类过程中合并过程不可逆，因此比较局限。1.2.3聚类的评价指标聚类算法的效果需要评价指标来评估，聚类的效果好坏根据簇内数据的相似度来界定，簇内高相似且簇间低相似，则说明聚类效果越好。基于这样的一种思想，研究人员设计了多种目标函数作为评估指标。聚类评估指标一般分为两种：（1）外部评价指标由于只能在已知每个数据的真实分类后才能进行评价，所以只适用于有标签的数据；（2）内部评价指标则是根据数据本身的特征值和不同属性来进行评价，所以适用的数据集更为广泛。常用的内部评价指标[49]有：轮廓指数（SI）、邓恩指数（DVI）和戴维森堡丁指数（DBI）等。（1）轮廓指数（SI）计算的是簇内数据距离与其他相邻簇间的距离比值：SI=iSI(idis(Cavg(C其中，dis(Ci,Cj)表示簇类Ci和簇类Cj（2）邓恩指数（DBI）计算的是两个簇类质心的间距与两类内数据的平均距离之和的比值：DBI=1ui=其中，ui表示簇类Ci的簇心，（3）戴维森堡丁指数（DVI）计算的是两个簇类间的最短距离和簇内数据的类内最大距离的比值：DVI=min其中，dis(Ci,Cj)表示两个不同簇类1.3基于麻雀搜索聚类的协同过滤推荐算法（1）基于K-means的协同过滤算法电影平台中，由于数据信息的规模逐渐增大，其推荐系统在处理矩阵时将面临更大的时空损耗压力。可以先对用户进行聚类，然后再对簇类间用户进行推荐，从而减少矩阵的规模。这种方式将不需要在评分预测阶段遍历矩阵中所有的用户数据，减少内存的消耗，提高运行速度。目前基于K-means的协同过滤推荐算法[50]已经被越来越多的推荐系统所使用的，算法实现过程如表1.1所示。（2）基于麻雀搜索聚类的协同过滤推荐算法针对上节所提算法继续深入研究，K-means协同过滤算法虽然可以提高运行速度，但在随机选取中心点时，由于中心点过于集中或者过于分散都会导致寻有效果不理想问题，就会降低算法的推荐准确度，所以本文使用麻雀搜索算法与聚类协同过滤算法相结合的策略，提出了一种基于麻雀搜索聚类的协同过滤算法（以下简称SSA-CF）。算法首先利用麻雀搜索策略对聚类的初始聚类中心点寻优，解决中心点选取敏感问题。SSA-CF的算法思想是：首先使用麻雀搜索算法对所有数据进行寻优，找到最优的初始聚类中心点。在麻雀搜索算法中，每一只麻雀代表一个聚类中心矩阵C=C1Fx=其中d表示麻雀的数量，发现者由位置最好的麻雀组成，剩余麻雀则为跟随者。Fx中每得到初始聚类中心后，算法开始对用户进行聚类，获得到分类的用户簇后，使用相似度公式2-(1)计算目标用户所在簇和所有邻居之间的相似度，找到目标用户的最近邻，对其中用户可能喜爱的项目评分进行预测，完成推荐。基于SSA-CF的具体流程如表1.2所示。表1.1基于K-means的协同过滤推荐算法算法1基于K-means的协同过滤推荐算法输入:用户-项目评分矩阵P；用户数量N；最大迭代次数T输出：推荐项目及预测评分开始：初始化：k个初始聚类点；while(t<for(i=1:N)计算i与中心点的距离，并划分到最近的簇类中；重新计算簇类的中心点；endwhile输出k个簇类结果；使用公式2-(1)按照相似度对用户排序，生成最近邻集合；使用公式2-(2)对用户未评分的项目进行预测，完成推荐。表1.2SSA-CF算法流程算法2SSA-CF输入：用户-项目评分矩阵P；用户数量N；用户簇数C；最大迭代次数T；生产麻雀的数量Pm；预警麻雀的数量Rx；报警值Av；麻雀的数量D输出：Xbest,开始：初始化n只麻雀种群并定义它们的相关参数。while(t<排名适应度值并找到当前最佳麻雀和当前最差麻雀。Av=fori=1:fori=fori=1:Rx{使用公式3-(3)更新警戒者麻雀的位置；}获得当前最新位置；If(当前最新位置优于之前的最优位置)更新Xbestt=endwhile输出Xbestwhile(t<Tfor(i=1:N)计算i与中心点的距离，并划分到最近的簇中；重新计算选取簇类的中心点；endwhile输出k个簇类结果；使用公式2-(1)按照相似度对用户排序，生成最近邻集合；使用公式2-(2)对用户未评分的项目进行预测，完成推荐。1.4实验设计与分析1.4.1数据集针对本章提出的算法，在电影推荐场景下设计实验并进行验证推荐的准确度，本次实验选择使用的是MovieLens电影评分数据集。该数据集是由GroupLens小组建立的电影网站中的真实电影评分[51]。在各种行业的科学研究实验中都可以见到该数据集的身影，国内外推荐算法的研究者通常使用该数据集进行有效性实验。其中有以下四种规模评分数据集：ML100K，ML1M，ML10M，ML20M。具体数据如表1.3所示。其中ML100K数据集包括近千个用户对1682部带有标签的电影提供的评分记录，该数据集可以使用的评分只占6.3%，是一种特别稀疏的数据集。本文选取的ML100K版本来进行实验的验证。该数据集包括三部分：用户信息提供了个人的信息统计及观影行为数据。电影信息分为19种类型包括动画片、恐怖片和动作片等共1682部电影。用户对电影的评分信息，包括近十万条评分信息，分值是从0到5之间的整数，0分标注了用户未对该电影进行打分，由小到大说明用户对该电影的喜爱程度是逐渐上升的。表1.3MovieLens数据集数据集ML20MML10MML1MML100K用户个数电影个数评分个数稀疏程度138439272872000万99.32%69876108661000万98.61%70895706100万95.58%1093168210万91.67%该数据集可以使用的评分只占6.3%，是一种特别稀疏的数据集。本文实验之前首先对数据集进行预处理工作，将初始数据中有用的信息按照用户-项目-评分整理成矩阵，然后将数据集进行划分，其中80%是训练集，分别为u1.base到u5.base，10%是测试集，分别为u1.test到u1.test，为了验证使用麻雀搜索算法优化后的拟合结果，取出10%不参与算法训练过程的数据作为验证数据集，分别为u1.test到u5.test，防止出现过拟合。具体数据如表1.4所示。表1.4数据集说明数据集说明数量1原始数据集2训练数据集3测试数据集4验证数据集初始提供的数据用于模型学习的训练数据验证算法准确度的测试数据验证优化后拟合结果的数据94367550（80%）943（10%）943（10%）1.4.2实验环境本文实验环境为一台个人笔记本电脑，机器的硬件配置为intelcorei5、1.60GHz、8GB内存、500G硬盘。软件配置为windows10的操作系统，使用软件为Spyder，使用语言为Python3。1.4.3实验方法与度量标准本文采用K折交叉验证的方法对数据集进行取样实验。首先将数据集平均分为K等份，再将K份数据采用不同比例的分割进行交叉验证。文中K=5，即5折交叉验证。每个实验在完全相同的环境下进行5次试验，最终统计5次实验的结果，并求出平均值进行分析。本文使用平均绝对误差（meanabsoluteerror，MAE）作为度量标准。MAE评估标准是通过计算用户对项目的真实评分和预测评分之间的误差大小。计算具体公式如下：MAE=u,i∈Tu其中，用户集用Tu表示，测试集中商品数量用N表示，用户u对i的预测评分用Ru,i表示，真实评分用1.4.4实验结果（1）确定最佳聚类个数C为了确定聚类个数对算法准确度带来的影响，并希望可以找出最佳聚类个数，设置实验进行分析观察。在不同的C值下对算法进行实验，并记录每次的MAE值。实验中C值的取值范围为［3,20］，其MAE结果如图1.6所示。图1.6聚类个数的选取对MA