MKF-Cuckoo：多核模糊C均值算法的聚类优化

© 2013由Elsevier B. V.出版由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 4（2013）243 - 2492013年AASRI智能系统与控制MKF-Cuckoo：Cuckoo搜索与多核模糊C均值算法Binu Da*，Selvi Ma和Aloysius GeorgeaaAloy Labs，印度班加罗尔。摘要通过优化过程发现最优聚类是聚类过程中的一个新趋势。因此，在文献中已经开发了几种算法来挖掘最优聚类。文献中提出的大多数基于优化的聚类算法都只关注于众所周知的聚类过程中给出的相同目标，即k-均值聚类。研究者们设计了一些更有效的目标函数来代替k-means目标进行聚类。因此，将这些有效的目标与优化算法相结合，可以得到有效的聚类结果。为此，我们提出了一种混合算法，称为MKF-Cuckoo，它是基于多核的模糊c均值算法与cuckoo搜索算法的混合。在这里，MKFCM的目标是通过杜鹃搜索算法，这是最近的优化算法之一，证明了在许多优化问题的有效解决相同的目标。为了证明算法的有效性，用iris和wine数据集，从聚类精度、rand系数、jaccard系数和计算时间等方面对算法的性能进行了比较分析。实验结果表明，该算法在虹膜识别中的准确率达到96%，在葡萄酒识别中的准确率达到67%。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：聚类，优化，布谷鸟搜索，多核模糊C均值算法（MKFCM），聚类精度。1. 介绍由于数据使用量的巨大增长，各种应用程序都非常需要集群。随着聚类过程的这一重要应用，k-means聚类[1]最初被引入，*通讯作者电子邮件地址：altimatebinu@gmail.com2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.037244D. Binu等人/ AASRI Procedia 4（2013）243迭代过程中考虑的目标是最小化平方误差之和。在此之后，不同的作者试图找到一些问题，在k-means聚类，并介绍了改进算法。基于模糊逻辑的改进算法之一是模糊c均值聚类[2]，它利用隶属函数和质心计算过程来迭代地找到最佳质心。在介绍了各种聚类算法之后，将聚类算法分为划分聚类和层次聚类两大类。另一方面，文献中也提出了一些其他不同的聚类算法，即基于网格的聚类[3]，基于投影的聚类[4]，子空间聚类[5]和密度聚类[6]。然后，提出了聚类过程的优化算法。在基于优化的聚类算法中，研究者们以最小化误差平方和为聚类目标，并使用算法中定义的优化过程来求解聚类目标。基于类似的过程，遗传算法[7]，粒子群优化[8]，细菌觅食优化[9]，模拟退火[10]，人工蜂群[11，12]和萤火虫算法[13]被应用于聚类。在这里，大多数算法已经采取质心集作为解决方案，以产生最佳的聚类质心。同时，一些作者使用混合优化算法进行聚类[14，15]，其中两种不同的优化算法相结合，以实现有效的聚类结果。同时，在标准优化算法中进行了一些简单的修改，然后将其应用于聚类[16]。在获得更有效的聚类结果的同时，一些作者[17，18]将k-means和FCM算子添加到优化过程中，目的是改善聚类过程中的收敛性。在完全分析了关于聚类过程的文献之后，我们采用了MKFCM算法[19]中定义的目标，并且使用最近的优化算法布谷鸟搜索[20]来解决该目标。在这里，解决方案编码的基础上，通过MKFCM目标函数的帮助下，获得最佳的聚类中心。将MKFCM目标结合到聚类过程中的优点是，与仅通过数据空间进行的聚类相比，核空间可以更好地识别数据点之间的方差。此外，将多个内核合并到一个距离函数中也可以导致有效的距离测量，从而可以实现有效的聚类，因为距离查找是任何聚类过程的核心过程。根据布谷鸟在寻找最佳产卵巢时的搜索行为，利用MKFCM目标的适应度进行最佳聚类的搜索。在这里，新的解决方案，介绍了基于列维飞行方程，是有效的生成最近邻解决方案，包括聚类目标。本文组织如下：第2节提出了混合算法开发的聚类和第3节提供了实验进行混合聚类和详细的结果，以及比较分析。第四部分是本文的结论。2. 建议的方法：MKF-cuckoo算法根据文献综述，聚类过程可以很容易地重新表述为优化问题。目标聚类优化是通过迭代过程寻找最佳聚类中心。因此，在文献中已经提出了几种技术，用于在问题空间中搜索最优质心。但是，大多数算法使用相同的目标，以最小化数据对象之间的平方距离和的帮助下，找到最佳的质心。在我们的工作中，我们使用了一个有效的目标函数，可以导致更好的结果，在搜索最佳质心。基于这种动机，我们利用了多个基于核的FCM算法，并将其作为我们研究的目标，并将其与最近的布谷鸟搜索算法相结合，以快速找到最佳质心。本文的主要贡献是将最优搜索算法中的布谷鸟搜索算法与最近被证明有效的聚类算法之一MKFCM算法相结合，D. Binu等人/ AASRI Procedia 4（2013）243245Xi MJR22IJ聚类将这两种算法混合使用时，由于采用了MKFCM目标进行最优聚类中心搜索，使得最优搜索变得容易，同时又能得到有效的解。该算法的整个过程可以分为三个重要阶段：1）初始解的编码; 2）聚类的目标函数; 3）MKF-Cuckoo搜索的算法过程。2.1. 初始解编码任何一种优化算法在搜索最优解时都需要一种有效的解表示，以提高搜索效率，快速找到最优解。为此，我们的聚类过程的初始解是从输入数据集中获取的随机质心。假设，布谷鸟搜索的初始巢是P。然后，该算法从输入数据库中获取P个初始解。从数据集中提取的每个解都包含m*k矩阵。这里，m表示所需的质心的数量，k表示数据库中给定的属性的数量。因此，从数据库中取出m*P条记录，并在P个解决方案中表示。2. 2聚类目标函数取自[19]中给出的聚类方法，并用作适应度函数。这里，目标函数考虑数据点与其最近邻聚类质心之间的距离最小化。但是，距离查找使用基于核的距离和模糊隶属度函数。混合聚类算法的总体目标表示如下：n MOBuijb（1kcom（ximj））（一）i1j 1这里，kcom（ximj）表示为多核空间中的鲁棒距离测量。 为在上述目标函数上，如下计算隶属矩阵ub1uijb（1kcom（ximmj））b11（二）（一）kcom（xiJ1mj））b1核空间中的组合鲁棒距离测量是从两个核获得的两个距离的数学相加。在这里，我们使用了两个核，如高斯核和切向核。kcom（ximj）k1（ximj）k2（ximj）（三）k1（ximj）exp（四）k2（ximj）tanh（ximj（五）246D. Binu等人/ AASRI Procedia 4（2013）2432.3. MKF-Cuckoo搜索本节描述了所提出的MKF-Cuckoo搜索算法的详细步骤。该算法的伪代码如图3所示。步骤1：初始的一组P个主机嵌套：最初，在初始的一组嵌套中给出P个解决方案，每个嵌套用m*k矩阵表示。步骤2：通过Levy Flight选择随机数（j）：这里，通过Levy Flight方程，在1到P之间生成随机数（j），并选择相应的解（质心集）。第三步：评估位于随机数对应的种群中的巢的适应度。第3.2节中给出的适应度用于寻找初始种群第j个步骤4：在P中选择一个随机套（i）：这里，在1到P之间盲生成一个随机数，并选择初始种群第i个位置的解来寻找解的适应度。步骤5：如果属于j的适应度小于i，则用新的解替换嵌套j：通过比较适应度来找出从前面步骤中获得的两个解的溶液用一组新的解（m*k）最差嵌套的新解x（t1）由下式执行，矩阵），使用以下等式。x（t1）x（t）利维（六）其中，0是应该与感兴趣的问题的尺度相关的步长乘积表示逐项乘法。Levy飞行本质上提供随机游走，而它们的随机步长是从大步长的Levy分布中得出的，Levy~ut，（1 3）（七）一旦生成新的解，就检查下限和上限条件。检查m*k矩阵的新解中放置的每个值。如果在基于Levy飞行的新解中得到的值大于上界，则用上界值替换该值。如果该值小于下限，则新值将替换为下限值。首先从数据集中找出每个属性的上界和下界值。LB和UB是输入数据库中每个属性的最大值和最小值。步骤6：根据概率pa：基于算法中给出的概率，从群体中识别最差的一组巢，并基于步骤5中给出的步骤在相应的位置建立新的一组巢。步骤7：保留最好的一个：基于适应度函数在每次迭代中保持最佳嵌套集合，并且该过程从步骤2继续到步骤6，直到达到最大迭代。3. 结果和讨论本节讨论了拟议的MKF-Cuckoo的实验结果。该算法在MATLAB中实现，并在Core i5处理器，2.13GHZ，3 GB RAM的计算机上执行。3.1 数据集描述虹膜和葡萄酒数据集等两个数据集取自机器学习实验室[21]，用于MKF-Cuckoo算法在聚类中的实验。虹膜数据集：该数据集包含三个类别，具有相等数量的数据对象，其中每个类别指的是一种虹膜植物。在虹膜数据集中，有150个实例具有四个数字特征没有缺少的属性值。的属性D. Binu等人/ AASRI Procedia 4（2013）243247M虹膜数据集是以cm为单位的萼片长度、以cm为单位的萼片宽度、以cm为单位的花瓣长度和以cm为单位的花瓣宽度。葡萄酒数据集：该数据集包含来自三个不同品种的178种葡萄酒的化学分析。葡萄酒的类型是基于13个连续的特征，这些特征来自于化学分析：酒精、苹果酸、灰分、灰分的碱度、镁、总酚、类黄酮、非类黄酮酚、原花青素、颜色强度、色调、稀释葡萄酒和果仁糖的OD 280/OD 315。这三个类别的数据集中的物体数量分别为59、71和48。3.2 评估指标对于混合算法的性能评估，我们使用了三种不同的度量标准，即聚类准确率、rand系数和jaccard系数。Rand系数（R）：它决定了已知的正确聚类结构与聚类算法获得的结果之间的相似程度。其定义为：RSSSS SDDDDS DD（八）其中，SS表示两个数据点属于同一聚类和同一组，SD表示两个数据点属于同一聚类但不同组。DS表示属于不同聚类但属于同一组的两个数据点，DD表示属于不同聚类和不同组的两个数据点。Jaccard系数（J）：与rand系数相同，但不包括DD，定义为：JSS（九）SSSD DS聚类准确度（CA）：聚类准确度计算与原始标记数据相比的分组准确度。具体如下：CA1maxC mI j（十）nj1i1，2，，K这里，CC1C2、CK是一个标记的数据集，它提供了地面实况，m1，m2，，mm是一由数据集的聚类算法产生的分区3.3 参数调查集群大小和迭代在不同的簇大小（如2，3，4和5）下，对所提出的混合聚类算法的性能进行了分析。针对不同的迭代执行所提出的方法，并针对迭代10和100分析性能。逐步取得的结果见下表1。248D. Binu等人/ AASRI Procedia 4（2013）243表1：集群大小和迭代集群评价Iris数据集Wine数据集大小度量迭代迭代迭代迭代1010010100CA0.6800.6670.6690.517RC0.5550.5180.5540.498C=2JC0.3060.2740.3280.249F446.967446.398320.631315.200时间3.57232.7494.25339.290CA0.8930.7870.5170.511RC0.4230.5160.5710.572C=3JC0.3270.3300.2500.247F595.757595.519300.659289.042时间5.22648.9346.24158.408CA0.9530.6530.4100.399RC0.3640.5610.5920.599C=4JC0.3210.2820.2000.212F744.967744.334224.113228.837时间6.85963.7188.25677.076CA0.9590.8870.4550.354RC0.5830.4250.6280.612C=5JC0.3600.3220.2330.177F893.284892.667209.347125.874时间8.43779.38810.19095.348在这里，可以对具有不同聚类大小和不同迭代的虹膜和葡萄酒数据集进行分析。虹膜数据集的准确率在聚类大小为2时为68%。因此，为了提高准确性，我们将聚类大小增加到3、4和5。因此，聚类准确率同时提高到89%，95%和96%。当集群规模增加时，时间自动增加。但是，与10次迭代相比，100次迭代的精度值较低。在100次迭代中，准确率为89%。对于葡萄酒数据集，准确率为67%。当比较两个数据集时，iris的结果更好。4. 结论我们提出了一种混合算法，称为MKF-Cuckoo，这是混合的杜鹃搜索算法与基于多核的模糊c均值算法。在这里，解决方案编码的基础上的聚类质心和最佳的聚类质心是通过布谷鸟搜索算法，这是最近的优化算法之一，在许多优化问题证明是有效的。将MKFCM目标引入聚类过程的优点是，与仅通过数据空间进行聚类相比，核空间可以更好地识别数据点之间的方差。在这里，使用虹膜和葡萄酒数据集进行了实验。为了证明混合算法的有效性，通过聚类精度、rand系数和jaccard系数对混合算法进行了对比评价。从结果中，我们发现，该混合算法在虹膜数据中获得了95%的准确率，在葡萄酒数据中获得了67%的准确率。今后的工作方向是在布谷鸟搜索算法中加入有效的目标函数和改进。引用[1] J·麦奎因多变量观测值分类与分析的若干方法。第五届伯克利数学研讨会论文集。统计与概率。1967; 1281 -297.[2] J.C.贝兹德克模式识别的模糊目标函数算法。New York：Plenum Press，1981，ISBN：0306406713.D. Binu等人/ AASRI Procedia 4（2013）243249[3] 廖维铿，刘英。Alok Choudhary：一种使用自适应网格细化的基于网格的聚类算法。出现在第七届采矿科学和工程数据集研讨会上。2004年。[4] Mohamed Bouguessa和Shergrui Wang。在高维空间中挖掘投影簇。IEEE Transactions on Knowledgeand Data Engineering. 2009;21：4.[5] R. Agrawal，J. Gehrke，D. Gunopulos和P. Raghavan。数据挖掘应用中高维数据的自动子空间聚类。在ACM-SIGMOD国际会议记录中。数据管理。1998; 94[6] M.埃斯特，H.- P.Kriegel，J.Sander和X.徐一种基于密度的含噪声大型空间数据库聚类发现算法。第二届知识发现与数据挖掘国际会议论文集。1996; 226-231.[7] 穆阿利克，美国，&Bandyopadhyay，S.基于遗传算法的聚类技术。模式识别2002;33 1455[8] K. Premalatha和A.M. Natarajan。一种基于局部搜索PSO的数据聚类新方法。计算机与信息科学2008;1：4.[9] Miao Wan，Lixiang Li，Jinghua Xiao，Cong Wang，Yixian Yang.使用细菌觅食优化的数据聚类。JIntell Inf Syst.2012;38 321[10] S. Z. Selim和K.阿尔苏丹聚类问题的模拟退火算法。模式识别。1991;10：24 1003[11] 张长生，欧阳丹彤，宁嘉旭。一种人工蜂群聚类方法。专家系统及其应用2010;37 4761[12] 德尔维斯·卡拉博加，塞拉·奥兹图克.提出了一种新的聚类方法：人工蜂群算法.应用软计算2011;11 652[13] J. Senthilnath，S.N. Omkar，V. Mani.使用萤火虫算法的聚类：性能研究。Swarm和进化计算2011;164[14] S. Paterlini，T.克林克区分聚类中的差分进化和粒子群优化。Comput. Stat.数据分析2006;50 1220[15] T. Niknam，M. Nayeripour和B.Bahmani Firouzi。一种新的混合优化算法在聚类分析中的应用。国际电气与计算机工程杂志。2009;4：4.[16] Swagatam Das ， Ajith Abraham ， Amit Konar. 基 于 改 进 差 分 进 化 算 法 的 自 动 聚 类 。 IEEETransactions on Systems，Man，and Cybernetics-Part A：Systems And Humans（IEEE系统、人与控制论汇刊）2008;38：1。[17] 克里希纳，K.，&Murty.遗传K均值算法IEEE Transactions on Systems Man and Cybernetics BCybernetics，1999;29 433[18] Hesam Izakian，Ajith Abraham，Vaclav Snasel使用混合模糊c均值和模糊粒子群优化的模糊聚类。世界自然和生物启发计算大会（NaBIC 2009），印度，IEEE出版社。2009; 1690-1694.[19] Long Chen，C. L. Philip Chen和Mingzhu Lu。一种用于图像分割的多核模糊C均值算法。IEEE系统、人与控制论汇刊-B部分：控制论。2011;41：51263 - 1274.[20] Yang，X. S.和Deb，S.布谷鸟搜索通过L'evy航班。自然生物启发计算世界大会论文集（NaBIC2009，印度），IEEE出版物，USA/.2009; 210-214。[21] UCIdata Repository“http：//archiv e.ics.uci.edu/ml/picets.html”.