MKF-Cuckoo：布谷鸟搜索与基于多核的模糊 C-means 算法的混合算法

0 AASRI Procedia  4 ( 2013 )  243 – 24902212-6716 © 2013 The Authors. Published by Elsevier B.V.under responsibility of American Applied Science Research Institute doi:10.1016/j.aasri.2013.10.0370ScienceDirect02013 AASRI智能系统和控制会议0MKF-Cuckoo: 布谷鸟搜索和多重核的混合算法0基于核的模糊c均值算法0Binu D a* , Selvi M a  and Aloysius George a0a Aloy Labs, 印度班加罗尔0摘要0通过优化过程发现最佳聚类是聚类过程中的一个新趋势。因此，文献中提出了几种算法来挖掘最佳聚类。文献中提出的大多数基于优化的聚类算法仅关注于k-means聚类中给定的相同目标。为了设计更有效的聚类目标函数，研究人员提出了一些其他的目标函数。因此，将这些有效目标与优化算法相结合可以获得更有效的聚类结果。为此，我们提出了一种名为MKF-Cuckoo的混合算法，它是将布谷鸟搜索算法与多核模糊c均值算法相结合。在这里，采用MKFCM目标并通过布谷鸟搜索算法解决相同的目标，布谷鸟搜索算法是最近在许多优化问题上证明有效的优化算法之一。通过使用聚类准确度、兰德系数、杰卡德系数和计算时间与鸢尾花和葡萄酒数据集进行比较分析，以验证算法的有效性。结果表明，该混合算法在鸢尾花数据集上获得了96%的准确率，在葡萄酒数据集上获得了67%的准确率。  © 2013 Published by Elsevier B.V.Selection and/orpeer review under responsibility of American Applied  Science Research Institute关键词：聚类，优化，布谷鸟搜索，多核模糊c均值算法（MKFCM），聚类准确度。01. 引言0由于数据使用的巨大增长，聚类在各种应用中都是非常需要的。0*  通讯作者电子邮件地址：altimatebinu@gmail.com0在线提供：www.sciencedirect.com0© 2013 The Authors. Published by Elsevier B.V.responsibility of American Applied Science Research Institute0CC BY-NC-ND许可下的开放获取。0CC BY-NC-ND许可下的开放获取。0244     D. Binu et al. /  AASRI Procedia  4 ( 2013 )  243 – 2490通过考虑最小化平方误差和的目标，k-means聚类的迭代过程被引入。此后，各种作者试图在k-means聚类中找到一些问题，并引入了改进的算法。基于模糊逻辑的改进算法之一是模糊c均值聚类[2]，它利用成员函数和质心计算过程来迭代地找到最佳质心。在研究人员介绍了各种算法之后，聚类算法被分为两大类，即划分聚类和层次聚类。另一方面，文献中还提出了其他不同的聚类算法，如基于网格的聚类[3]，基于投影的聚类[4]，子空间聚类[5]和密度聚类[6]。然后，引入了用于聚类过程的优化算法。在基于优化的聚类中，研究人员将聚类目标视为最小平方误差，并在其算法中使用了定义的优化过程来解决聚类目标。根据类似的过程，应用了遗传算法[7]、粒子群优化[8]、细菌觅食优化[9]、模拟退火[10]、人工蜜蜂群算法[11,12]和萤火虫算法[13]进行聚类。在这里，大多数算法将质心集合作为解来生成最佳的质心。同时，一些作者使用混合优化算法进行聚类[14,15]，其中将两种不同的优化算法结合起来以实现聚类中的有效结果。与此同时，一些标准优化算法进行了简单的修改，然后应用于聚类[16]。为了获得更有效的聚类结果，一些作者还在优化过程中额外添加了k-means和FCM运算符[17,18]，以改进聚类过程中的收敛性。在对聚类过程的文献进行全面分析后，我们采用了MKFCM算法[19]中定义的目标，并使用最近的优化算法布谷鸟搜索[20]解决该目标。在这里，基于聚类质心进行编码，并通过MKFCM目标函数实现最佳聚类质心的获取。将MKFCM目标融入聚类过程的优势在于，核空间可以更好地识别数据点之间的差异，而不仅仅是通过数据空间进行聚类。此外，将多个核融合到一个距离函数中也可以实现有效的距离测量，因此可以实现有效的聚类，因为距离计算是任何聚类过程的核心过程。根据布谷鸟搜索在寻找最佳巢穴以产卵方面的行为，通过MKFCM目标的适应度来搜索最佳聚类。在这里，基于列维飞行方程引入了新的解决方案，该方程在包含聚类目标的情况下可以生成最近邻解决方案。本文的结构如下：第2节介绍了用于聚类的混合算法，第3节提供了进行混合聚类和详细结果的实验以及比较分析。第4节总结了本文。02. 提出的方法：MKF-Cuckoo算法0根据文献综述，聚类过程可以很容易地转化为优化问题。聚类优化的目标是通过迭代过程搜索最佳聚类质心。因此，文献中提出了几种技术来在问题空间中搜索最佳质心。但是，大多数算法使用相同的目标来通过最小化数据对象之间的平方距离来寻找最佳质心。在我们的工作中，我们使用了一种有效的目标函数，可以在搜索最佳质心时获得更好的结果。出于这个动机，我们利用了多核模糊c均值算法及其目标来进行研究，并将其与最近的布谷鸟搜索算法结合起来，以快速找到最佳质心。本文的主要贡献是将布谷鸟搜索与MKFCM算法进行混合，布谷鸟搜索是一种在优化搜索中表现良好的算法，而MKFCM算法则是一种最近证明在聚类中有效的算法。当混合这两个算法时，最佳搜索变得容易，同时可以实现有效的解决方案，因为我们在最佳聚类质心搜索中使用了MKFCM目标。算法的整个过程可以分为三个重要的阶段：1）初始解编码2）聚类目标函数3）MKF-Cuckoo搜索算法的算法过程。)) (1) 111111( (2) 2 (4) 0245  D. Binu et al. /  AASRI Procedia  4 ( 2013 )  243 – 2490根据文献综述，聚类过程可以很容易地转化为优化问题。聚类优化的目标是通过迭代过程搜索最佳聚类质心。因此，文献中提出了几种技术来在问题空间中搜索最佳质心。但是，大多数算法使用相同的目标来通过最小化数据对象之间的平方距离来寻找最佳质心。在我们的工作中，我们使用了一种有效的目标函数，可以在搜索最佳质心时获得更好的结果。出于这个动机，我们利用了多核模糊c均值算法及其目标来进行研究，并将其与最近的布谷鸟搜索算法结合起来，以快速找到最佳质心。本文的主要贡献是将布谷鸟搜索与MKFCM算法进行混合，布谷鸟搜索是一种在优化搜索中表现良好的算法，而MKFCM算法则是一种最近证明在聚类中有效的算法。当混合这两个算法时，最佳搜索变得容易，同时可以实现有效的解决方案，因为我们在最佳聚类质心搜索中使用了MKFCM目标。算法的整个过程可以分为三个重要的阶段：1）初始解编码2）聚类目标函数3）MKF-Cuckoo搜索算法的算法过程。02.1. 初始解编码0通过任何优化算法寻找最优解需要一个有效的解表示方式，以提高寻找快速解的搜索效率。为此，我们的聚类过程的初始解是从输入数据集中随机选择的初始质心。假设， cuckoo搜索给出的初始解是  P。然后，算法从输入数据库中获取  P  个初始解。从数据集中获取的每个解都包含一个 m * k矩阵。因此，从数据库中获取  m * P  条记录，并在  P  解中表示。02. 2 用于聚类的目标函数0目标函数取自[19]中给出的聚类方法，并被用作适应度函数。在这里，目标函数考虑到数据点与其最近邻聚类质心之间的距离最小化。但是，距离的计算使用了基于核的距离和模糊隶属函数。混合聚类算法的总体目标如下所示：0n0m0ij b m x k u OB0在上述目标函数中， ) ( j i com m x k 代表多核空间中的鲁棒距离测量。0根据上述目标函数，计算成员矩阵  u ij b  如下所示。0m x k0m x k u0在核空间中的组合鲁棒距离测量是从两个核得到的两个距离的数学相加。在这里，我们使用了两个核，即高斯核和切线核。 ) ( ) ( ) ( 2 1 j i j i j i com m x k m x k m x k                                                                            (3)0m x m x k j i0j i0j i j i m x m x k tanh( ) 2 (                                                                                  (5)0246     D. Binu et al. /  AASRI Procedia  4 ( 2013 )  243 – 24902.3. MKF-Cuckoo搜索算法的算法步骤0本节描述了提出的MKF-Cuckoo搜索算法的详细步骤。算法的伪代码如图3所示。步骤1：初始一组  P个主机巢穴：首先，给定一组初始解（巢穴），每个巢穴都用一个 m * k矩阵表示。步骤2：通过列维飞行选择一个随机数（  j  ）：利用列维飞行方程，在1到  P 之间生成一个随机数（ j），并选择相应的解（质心集）。步骤3：评估位于种群中与随机数对应的巢穴的适应度。使用第3.2节中给出的适应度函数来计算初始种群中第  j  个位置的解的适应度。步骤4：在  P  个巢穴中选择一个随机巢穴（  i）：在1到  P  之间盲目地生成一个随机数，并选择初始种群中第  i个位置的解以计算解的适应度。步骤5：如果  j  的适应度小于  i  的适应度，则用新解替换  j的巢穴：通过比较两个解的适应度来评估前面步骤中获取的两个解的适应度。适应度较低的解将用以下方程替换为新的解（m * k  矩阵）。最差巢穴的新解 )1 x ( t 是通过以下方式执行的：0(  ) ( ) )1 ( Levy x  t x t                                                                (6)   其中，  0是步长，应与感兴趣的问题的尺度有关。0意味着逐个元素的乘法。列维飞行本质上提供了一种随机行走，其随机步长是从列维分布中绘制的，用于大步长，   )3 1(, ~ t u Levy                              (7)生成新的解后，会检查下界和上界条件。每个值都会进行检查，如果大于上界，则替换为上界值。如果小于下界，则替换为下界值。0将旧解放置在 k m *矩阵的新解中进行检查。如果基于列维飞行得到的新解中的值大于上界，则将值替换为上界值。如果值小于下界，则将新值替换为下界值。每个属性的上界值和下界值最初从数据集中找到。LB和UB是输入数据库中每个属性的最大值和最小值。步骤6：基于概率 a p移除最差的巢：根据算法中给定的概率，确定种群中最差的一组巢，并根据第5步给定的步骤在相应位置创建新的巢。步骤7：保留最佳的巢：根据适应度函数在每次迭代中保留最佳的巢，并从第2步到第6步继续执行，直到达到最大迭代次数。03. 结果与讨论0本节讨论了提出的MKF-Cuckoo算法的实验结果。该算法在MATLAB中实现，并在一台核心i5处理器、2.13GHz、3 GB RAM的计算机上运行。03.1 数据集描述0我们从机器学习实验室[21]获取了两个数据集，即鸢尾花数据集和葡萄酒数据集，用于在聚类中测试MKF-Cuckoo算法。鸢尾花数据集：该数据集包含三个具有相同数据对象数量的类别，每个类别代表一种鸢尾花的类型。鸢尾花数据集中有150个具有四个数值特征的实例。没有缺失属性值。数据集的属性为：0247  D. Binu et al. /  AASRI Procedia  4 ( 2013 )  243 – 2490鸢尾花数据集包括以厘米为单位的花萼长度、花萼宽度、花瓣长度和花瓣宽度。葡萄酒数据集：该数据集包含178种葡萄酒的化学分析，分为三个不同的品种。葡萄酒类型是基于从化学分析中得出的13个连续特征：酒精、苹果酸、灰分、灰分碱度、镁、总酚、黄酮类化合物、非黄酮类酚、原花青素、颜色强度、色调、稀释酒的OD280/OD315和酚醛。数据集中三个类别的对象数量分别为59、71和48。03.2 评估指标0为了对混合算法的性能进行评估，我们使用了三个不同的度量标准，即聚类准确度、兰德系数和Jaccard系数。兰德系数（R）：它确定了聚类算法得到的结果与已知正确的聚类结构之间的相似度程度。它的定义如下：0DD SS R           (8)0其中，SS表示两个数据点属于同一聚类和同一组，SD表示两个数据点属于同一聚类但不同组，DS表示两个数据点属于不同聚类但同一组，DD表示两个数据点属于不同聚类和不同组。Jaccard系数（J）与兰德系数相同，只是不包括DD，定义如下：0DS SD SS SS J                        (9)0聚类准确度（CA）：聚类准确度计算与原始标记数据相比的分组准确度。计算公式如下：0j j i K01 , ,2,1 max 1                                                         (10)0这里，C K C C C , , , 2 1是一个标记数据集，提供了基本事实，m m m m m , , , 21是由聚类算法为数据集生成的一个划分。03.3 参数调查0聚类大小和迭代次数对所提出的混合聚类算法的性能进行了不同聚类大小（例如2、3、4和5）的分析。该方法在不同迭代中执行，并分析了迭代10和100的性能。逐渐获得的结果如下表1所示。0248     D. Binu et al. /  AASRI Procedia  4 ( 2013 )  243 – 2490表1：聚类大小和迭代次数的性能分析0迭代次数  10 迭代次数  100 迭代次数  10 迭代次数  100 C=20RC  0.555 0.518 0.554 0.498 JC  0.306 0.274 0.328 0.249 F  446.967 446.398320.631 315.200  Time  3.572 32.749 4.253 39.290  C=30RC  0.423 0.516 0.571 0.572 JC  0.327 0.330 0.250 0.247 F  595.757 595.519300.659 289.042  Time  5.226 48.934 6.241 58.408  C=40RC  0.364 0.561 0.592 0.599 JC  0.321 0.282 0.200 0.212 F  744.967 744.334224.113 228.837  Time  6.859 63.718 8.256 77.076  C=50RC  0.583 0.425 0.628 0.612 JC  0.360 0.322 0.233 0.177 F  893.284892.667 209.347 125.874  Time  8.437 79.388 10.190 95.3480在这里，可以针对鸢尾花和葡萄酒数据集进行不同聚类大小和不同迭代的分析。鸢尾花数据集的准确度在聚类大小为2时为68%。因此，为了提高准确性，将聚类大小增加到3、4和5。因此，聚类准确度同时增加到89%、95%和96%。当聚类大小增加时，时间自动增加。但是与10次迭代相比，我们在100次迭代中获得了较低的准确度值。在100次迭代中的准确度为89%。对于葡萄酒数据集，准确度为67%。比较这两个数据集，鸢尾花有更好的结果。04. 结论0我们提出了一种混合算法，称为MKF-Cuckoo，它是布谷鸟搜索算法与基于多核的模糊c均值算法的混合。这里，解决方案基于聚类中心进行编码，并通过布谷鸟搜索算法获得最优聚类中心，布谷鸟搜索算法在许多优化问题中被证明是有效的最新优化算法之一。将MKFCM目标纳入聚类过程的优点是核空间可以更好地识别数据点之间的差异，而不仅仅是通过数据空间进行聚类。在这里，使用鸢尾花和葡萄酒数据集进行实验。为了证明混合算法的有效性，通过聚类准确度，兰德系数和杰卡德系数进行了比较评估。从结果中，我们发现混合算法在鸢尾花数据集中获得了95%的准确度，在葡萄酒数据集中获得了67%的准确度。这项工作的未来方向是将有效的目标函数和布谷鸟搜索算法的修改纳入其中。0参考文献0[1] J. McQueen。一些多元观测分类和分析方法。在第五届伯克利数学统计和概率研讨会论文集中。1967年；1281-297。[2] J.C. Bezdek。具有模糊目标函数算法的模式识别。纽约：PlenumPress，1981年，ISBN：0306406713。0249  D. Binu et al. /  AASRI Procedia  4 ( 2013 )  243 – 2490[3] 魏庚廖，刘颖。AlokChoudhary：一种使用自适应网格细化的基于网格的聚类算法。出现在第7届矿工科学和工程数据集研讨会上。2004年。[4] Mohamed Bouguessa和ShergruiWang。在高维空间中挖掘投影聚类。IEEE知识与数据工程交易。2009；21：4。[5] R. Agrawal，J.Gehrke，D. Gunopulos和P.Raghavan。自动子空间聚类高维数据挖掘应用。在ACM-SIGMOD国际数据管理会议论文集中的论文。1998年；94-105。[6] M. Ester，H.-P.Kriegel，J. Sander和X.Xu。一种用于在大型空间数据库中发现聚类的基于密度的算法。在第二届知识发现和数据挖掘国际会议论文集中的论文。1996年；226-231。[7]Mualik，U。，＆Bandyopadhyay，S.基于遗传算法的聚类技术。模式识别。2002年；33 1455-1465。[8] K.Premalatha和A.M.Natarajan。基于PSO和局部搜索的数据聚类的新方法。计算机与信息科学。2008年；1：4。[9] MiaoWan，Lixiang Li，Jinghua Xiao，Cong Wang，Yixian Yang。使用细菌觅食优化的数据聚类。J Intell InfSyst。2012年；38 321-341。[10] S. Z. Selim和K.Alsultan。用于聚类问题的模拟退火算法。模式识别。1991年；10：24 1003-1008。[11]张长生，欧阳丹彤，宁佳旭。一种用于聚类的人工蜜蜂群算法。专家系统与应用。2010年；374761-4767。[12] Dervis Karaboga，CelalOzturk。一种新的聚类方法：人工蜜蜂群（ABC）算法。应用软计算2011年；11 652-657。[13] J.Senthilnath，S.N. Omkar，V. Mani。使用萤火虫算法进行聚类：性能研究。Swarm and EvolutionaryComputation。2011年；164-171。[14] S. Paterlini，T.Krink。基于差分进化和粒子群优化的分区聚类。计算机统计数据分析。2006年；50 1220-1247。[15] T.Niknam，M. Nayeripour和B.BahmaniFirouzi。在集群分析中应用一种新的混合优化算法。国际电气与计算机工程学报。2009年；4：4。[16]Swagatam Das，Ajith Abraham，AmitKonar。使用改进的差分进化算法进行自动聚类。IEEE系统，人类和控制论文。2008年；38：1。[17]Krishna，K。，＆Murty。遗传K均值算法。IEEE系统，人类和控制论文B Cybernetics，1999；29433-439。[18] Hesam Izakian，Ajith Abraham，VaclavSnasel。使用混合模糊c均值和模糊粒子群优化的模糊聚类。世界自然和生物启发计算大会（NaBIC2009），印度，IEEE出版社。2009年；1690-1694。[19] Long Chen，C. L. Philip Chen和MingzhuLu。用于图像分割的多核模糊C均值算法。IEEE系统，人类和控制论文B Cybernetics。2011年；41：51263-1274。[20]杨希望和黛布。通过L´evy飞行进行布谷鸟搜索。世界自然与生物启发计算大会论文集（NaBIC2009，印度），IEEE出版社，美国。2009年；210-214。[21]UCI数据库“http://archive.ics.uci.edu/ml/datasets.html”。