FSDE-Forced Strategy Differential Evolution在数据聚类中的应用

沙特国王大学学报FSDE-Forced Strategy Differential Evolution用于数据聚类Meera Ramadasa，Ahith Abrahamb，Sushil Kumaraa印度北方邦诺伊达爱德大学bMIR实验室，华盛顿，美国阿提奇莱因福奥文章历史记录：2016年6月6日收到2016年11月27日修订2016年12月15日接受2016年12月25日在线发布关键词：突变交叉质心聚类质量量化误差指数A B S T R A C T经过大量的研究，差分进化算法发生了各种变化。各种算法的性能取决于变异和交叉策略的变化。在本文中，我们提出了一种新的差分进化变体，称为强制策略差分进化（Festival），通过创建一种新的变异策略。该策略使用两个参数进行变异：一个常数参数和一个可变参数。将使用k均值技术对聚类应用Festival。针对各种标准基准函数进行了实验。在聚类方面，将该算法与经典的DE、GA和PSO算法进行了比较，并将聚类质量结果实验结果表明，该策略比其他变异策略更有效©2016作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着研究领域的不断发展和快速进步，需要处理或产生的数据量成倍增加。随着数据收集的增加，数据挖掘领域出现了重大挑战。数据挖掘或知识发现是从各个方面识别数据，然后对这些数据信息进行适当分类的技术。数据挖掘软件分析数据中存在的关系和模式。传统的数据挖掘技术分为有监督学习和无监督学习两大类。监督学习技术用于分类和预测，而无监督学习技术是那些没有预测或分类是可能的。数据聚类是一种非监督学习技术。聚类分析是数据挖掘领域的一个新兴研究领域。聚类将数据划分为有用和有意义的组，称为聚类。聚类的主要目的是将一组中的对象或数据*通讯作者。电子邮件地址：meera_mgr@rediffmail.com（M. Ramadas）。沙特国王大学负责同行审查应该彼此相似，而与另一组中的对象不同。聚类确定未标记数据集合在机器学习、模式识别、图像处理、数据压缩和信息检索等领域，它是统计数据分析的主要方法Jain（2010）总结了聚类技术和使用的各种方法数据聚类在高效的数据挖掘、语音识别、Web挖掘、市场分析等方面起着至关重要快速准确的数据聚类在自动信息检索系统中起着重要的作用它被认为是一个多目标优化问题。它涉及反复试验和错误的任务聚类可以分为硬聚类和软聚类。在硬聚类中，每个对象属于一个聚类或不属于任何聚类。在软聚类或模糊聚类中，每个对象可以属于多个聚类（Bezdek et al. （1984））。聚类算法可以分为层次算法和划分在层次聚类中，构造分区的层次结构并创建树状图表示。在该技术中，每个parti- tion被分组在层次结构中的下一级别的分区在分区聚类中，单个分区由给定数量的非重叠聚类构成。分区聚类的主要缺点是找到具有指定数量的聚类的数据分区，从而最小化聚类内的分区算法是迭代的，通常收敛到局部极小值。最简单和最流行的分区聚类算法K-means技术是MacQueen（1967）提出的。https://doi.org/10.1016/j.jksuci.2016.12.0051319-1578/©2016作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comM. Ramadas等人/Journal of King Saud University53这里，给定的N个数据集被划分为k个不同的聚类。通过最小化数据和质心之间的欧几里德距离来完成数据的重构。它是用于聚类的最简单的无监督学习算法该算法对初始随机选取的质心非常敏感由于k均值算法的结果依赖于初始均值，因此经常会出现次优分割，由于k均值算法可能收敛于次优分割，因此采用随机优化方法来避免这种情况，从而找到全局最优解。这些问题可以用进化算法来解决 Coello等人（2002）指出，进化算法以鲁棒且有效的方式用于聚类。进化算法是进化计算的一部分，它利用生物学中的繁殖、重组、变异和选择等方法Storn和Price（1997）在演化算法的基础上提出了差分演化算法（DE）差分进化算法是一种简单的、基于种群的随机算法DE的有效性和性能取决于控制参数和测试向量生成策略。通过改变这些策略和控制测试向量参数，设计了许多变体。本文的目的是提出一种微分演化方法的变体，然后将这种方法与k-均值方法结合起来应用于聚类问题。本文的第一部分讨论了基本的聚类方法。第二部分是对差分进化技术的解释 第三部分介绍了DE算法的一个变种，即强制策略差分进化算法（FESSEARCH）。在后面的章节中解释了从FENG获得的实验结果。然后详细介绍了Festival等进化算法在k-均值算法上的实现，关于数据聚类。2. 聚类中进化算法的相关研究将进化计算的概念应用于聚类问题是一个长期的研究课题许多变种的进化算法，如DE，GA，PSO的创建和这些变种被应用到聚类问 题 。 Paterlini 和 Thiemo （ 2004 ） 给 出 了 一 个 关 于 遗 传 算 法（GA）、PSO和差分进化（DE）的性能比较。结果表明，DE方法是远远优于GA和PSO，DE应该考虑比其他算法的聚类。Zaharie（2005）研究了拥挤差分进化对无监督聚类的适用性。这种方法允许 识 别 集 群 的 任 意 形 状 ， 使 用 多 中 心 的 描 述 。 Abraham 等 人（2006）描述了一种新的方法，使用改进的经典差分进化将文本文档划分为聚类。引入了一种改进的变异算法以提高算法的收敛性能。然后将改进后的DE用于文本文档的聚类，以检索重要信息。通过对CS测度的改进，提出了一种新的高维文本聚类有效性指标这种技术被证明是优越的聚类速度和质量Zhang和Sanderson（2007）表明，DE的实现主要基于交叉概率和变异因子。对这些参数所做的更改将影响DE的性能。Zhang et al.（2008）还提出了一种先进的粒子群优化算法，提出了一种基于空间聚类的障碍约束演化方法（SCOC）。该方法具有较好的量化误差和收敛速度。Indrajit等人（2009）提出了将差分进化应用于分类数据集的模糊聚类。该算法有效全局优化模糊c中心点误差函数。 Maulik和Indrajit（2010）设计了一种基于模糊C-中值（FCMDD）的分类数据集的改进差分进化（DE）聚类。该技术显示了集成聚类和监督学习方法的优越性。Maulik等人（2010）还提出了一种新的基于实数编码的改进差分进化的自动模糊聚类算法，该算法自动计算聚类数和数据集的适当划分。在本文中，分配点到不同的集群是基于一个谢贝尼指数，考虑了欧几里德距离。Alguliev等人（2011）提出了一种文档摘要模型，该模型将关键句子从给定文档中分离出来，同时去除摘要中的冗余信息。实验结果表明，该方法优于早期的摘要模型。Pham等人（2011）介绍了一种新的方法来聚类混合数据类型的数据集。RANKPRO（rand-dom searchwith k prototype）是将蜜蜂算法与k prototype相结合的一种算法.RANKPRO算法被证明比k原型方法更有效。Suarez-Alvarez等人（2012）介绍了一种统一的统计方法来规范混合数据集的所有属性。本文还对几种标准数据集进行了聚类分析. Qu et al.（2012）给出了一种邻域变异策略，并将其与各种小生境差分进化（DE）算法相结合，以解决多模态优化问题。该方法具有收敛速度快、精度高的特点。该技术中的变异策略能够产生稳定的小生境行为，并能够定位和保持多个全局最优解。Hatamlou（2013）从黑洞现象中得到启发，设计了一种新的启发式方法实验结果表明，该技术优于现有的经典方法。将该方法应用于聚类领域。Saha和Bandyopadhyay（2013）设计了一种新的多目标（MO）聚类技术（GenClustMOO），可以自动将数据划分为适当的聚类。将该方法与k均值法和单连锁法进行了比较Singh和Saha（2014）在分析和消除基于欧氏距离和点对称性的距离度量的缺点并将改进的版本合并到一种方法中以获得两种方法的最佳效果之后，给出了聚类的解决方案这种方法加快了计算时间。 Thein等人（2015）提出了用于聚类的差分进化算法，并将其纯度与k-means算法进行了比较。在UCI数据库的Pima、肝脏和心脏根据得到的这项工作表明，DE执行更好的时候，需要强大的聚类。这项工作也消除了平均技术的缺点。 Mukherjee等人（2016）给出了差分进化的修改版本，用于有效地解决动态优化问题（DOP）。该算法被命名为改进的DE与局部诱导遗传算子（MDE-LiGO），它集成了经典DE框架的三个阶段的变化。吴等人（2016）设计了一种基于多人群的方法，以实现多个策略的单元。由此产生的新变体命名为多群体集成DE（MPEDE）由三种突变策略组成Ramadas et al.（2016）介 绍 了 一 种 策 略 ， 即 差 异 进 化 和 Flower Polymorphism 算 法（ssFPA/DE）的混合技术。将结果制成表格，证明了新方法的有效性。3. 数据聚类方法聚类有两种类型：硬聚类和软聚类。在硬聚类中，每个数据都是一个聚类的成员在软俱乐部-54M. Ramadas等人/Journal of King Saud University质心变化开始根据计算的距离将数据分配到相应的计算每个数据到质心的距离重新计算新质心¼X2½][½]我我;;;;;G;否则;我4. 差分进化算法聚类或模糊聚类，每个数据可以属于多个聚类。最常用的硬聚类方法之一是k均值算法。k-means的标准算法是由Stuard Lloyd在1982年提出的。该算法的目的是找到最好的划分n个实体到k个组或集群，在这样的方式，组成员之间的总距离和它的质心是最小的。它在更新数据到集群的分配和更新集群的摘要或中心之间迭代。在该技术中，初始化k个质心。这些中心最初是随机选择的。然后，通过计算质心和数据点之间的欧几里得距离，将每个点分配到最近的质心。欧氏距离是多维空间中的几何距离。K均值算法通常使用欧氏距离来计算质心与数据的贴近度。其计算为：1重新计算每个聚类的质心结束循环。K均值算法易于实现，计算速度快。 Fong等人（2014）指出，这种技术的主要缺点是没有找到全局最优值的保证。经典的k均值算法随机分配初始点，聚类结果易陷入局部最优.因此，需要一种全局优化算法来克服k-means方法的缺陷。差分进化技术是Storn和Price（1997）提出的一种简单的全局优化方法。DE算法具有全局搜索能力强、精度高、收敛速度慢的特点，而K均值聚类算法具有较快的收敛速度。将k-均值算法与差分进化算法相结合，使局部和全局搜索稳定。K均值算法在特征学习、聚类分析等领域有着广泛的应用分析和矢量量化。（X2）2其中xi，yi是必须计算距离的两个点。现在为每个组计算新的中心。如果质心分配发生变化，则再次计算从每个数据到新质心的距离这些迭代地执行，直到质心没有变化。使用k均值算法进行数据聚类的流程图如图1所示。假设我们有k个聚类，其中c = 1，2，. K.设数据集为X，其中X1/4x1;x2;. Xn，中心集表示为V，其中V1/4 V1;V2;. Vc.聚类的质心计算如下：DE使用NP候选解决方案的群体，表示为X i，G，其中i 1; 2. 其中指数i表示种群，G表示种群的世代.差分进化算法主要依靠变异、选择和繁殖三种操作。变异：该算子使DE不同于其他进化算法。它计算总体中向量之间的加权差。突变过程开始于从群体中随机选择三个个体。此操作CiV¼1=c xð2Þ扩展了工作空间。对于给定的参数Xi，G我们随机第1页其中ci是第i个聚类中的数据点的数量。k均值的基本算法如下：选择k个点作为初始中心。重复，直到中心不变：通过将质心附近的数据分组到相应的聚类中来形成k个聚类Vi;G ¼Xr1;GF×Xr2;G-Xr3;G3其中，i ^l. NP，r1; r2; r32 f 1;.. . NPg是随机选取的，满足：r1 -r2-r3- i，F0; 1，F是Storn和Price（1997）提出的突变控制参数.这里F是来自[0，1]的常数。突变函数将一个DE方案与另一个区分开。交叉：这个过程也被称为重组，将成功的解决方案纳入群体。通过二项式交叉为目标向量Xi，G创建试验向量Ui供体向量的元素以概率Cr2½0;1]进入试验向量：C r是与群体一起选择的交叉概率。尺寸NP P 4。Uj;i;GVj;i;G1如果randi;j½0;1]6Cr或如果j½IrandXjiG1如果randij½0;1]>Cr，或者如果jð4Þ这里rand i，j0; 1和I rand是从1，2... N. 选择：此操作不同于其他进化算法的选择操作。该算法从当前种群中的向量及其相应的试验向量中选择下一代种群，将目标向量Xi，G与试验向量Vi，G进行比较，取函数值最小的一个作为下一代种群一代. U iG1，如果f <$U iG1<$6 f <$X iG<$，其中i 1; 2;. NXi突变、交叉和选择操作继续进行，直到达到某些停止标准。图1. k均值算法的流程图。5. 差分进化提出了一种新的突变策略，称为Festival。由于它涉及最佳解向量XG，best，因此与只有随机向量的传统策略相比，它的一致性开始初始化集群数量为K随机选取K个质心.¼距离x;yxi-yið1ÞJ选择3个向量Xr1;G;Xr2;G和Xr3，G使得r1;r2;r3是不同的。然后，施主向量Vi，G被计算为：Xi;G1¼ð5ÞM. Ramadas等人/Journal of King Saud University55--;;;;;;tors. 这里，使用两个控制参数突变因子F取常值，N取（0，1）之间的变化值，F取常值0.6，使供体向量值在允许范围内由于采用了两种不同的控制参数，施主矢量的值得到了很大的改善，从而大大提高了DE算法的效率建议的策略如下：ViG¼Xr1GN：XGbest-Xr2G-F：XGbest-Xr3G6基于最佳值（vtr = 1.e 015）：对每种技术进行了比较分析和研究通过设置可达值（VTR）为e015，维数为25和50，计算了不同函数策略的最佳值、函数求值次数和CPU时间在某些函数上，经典DE和本文算法的结果都很好得到的 总 体 结 果 表 明 ， FRESH 方 法 比 经典的 DE 方 法 表 现 更 好 。Friedman统计测试运行进行了Festival算法，以验证结果。根据表1中的值，应用弗里德曼检验，结果列于在这里，基向量的随机选择防止策略本质上变得贪婪。6. 测试问题在i7上实现了上述混合算法表2.弗里德曼测试后获得的排名列表表3所表2使用Friedman检验进行统计学检验核心处理器，64位操作系统，12 GB RAM，MATLABr2008b中进行了仿真，并与原DE算法进行了比较。提出的变异策略取代了传统的变异策略，并构成了模糊遗传算法.在所进行的实验中，突变常数F的值为0.6，交叉概率Cr的值为0.8.我们采用了15个不同的函数，并通过固定要达到的值和迭代次数来最大迭代次数固定为5000，最大求值次数固定为5，000，000。要达到的值（VTR）是函数的全局最小值或最大值，或者是在达到该值时停止优化的值我们将维数固定为25和50，将各种结果制成表格结果制成表格与现有的算法进行比较。名为significance的列显示了Festival获得的结果是否优于其他策略。在表1中给出了所获得的结果中的几个。N25Chi平方23.6Df 5渐近显著性0.0003表3不同策略的排序。策略最佳价值DE/best/1 2.6De/rand/1 3.2DE/最佳评级/1 2.8De/best/2 4.3DE/rand/2 5.12.9英尺表1不同功能的最佳价值。25 1.e- 015 9.34e- 015 9.35e- 015 9.539e- 015 9.42e- 015 6.92e+000 8.9e- 016 + Beale 50 1.e- 015 3.265e- 016 2.318e- 016 3.713e- 0167.587e- 016 7.725e- 016 5.95e- 016- 25 1.e- 015 4.26e- 015 7.72e- 015 1.125e- 015 1.36e- 017 7.5e- 015 3.6e- 016-展位号50 1.e- 015 3.497e- 016 2.0514e- 016 6.0738e- 016 7.0792e- 016 8.35e- 016 3.28e- 016-25 1.e- 015 1.807e- 015 7.55e- 016 1.95e- 015 2.75e- 015 6.47e- 015 9.4e- 016-施韦费尔50 1.e- 015- 1.8e+003- 2.253e+003- 7.8403e+001- 1.38e+003- 1.66e+003- 4.56e+003NA 25 1.e- 015- 4.22+002- 4.8e+002- 1.67e+003- 4.47e+003- 1.5e+003- 2.5e +003NA1.e- 015- 7.6399e+00- 7.214e+00- 7.39e+00- 6.959 e+00- 6.847 e+00- 7.34e+00NA 25 1.e- 015- 7.69e+00- 7.64e+00- 6.87e+00- 7.35e+00- 6.98 e+00- 7.1e+00NASchaffer N.2 50 1.e- 015 6.6e- 016 8.88e- 016 4.43e- 016 6.55e- 016 8.87e- 016 2.22e- 016 + 25 1.e- 015 1.33e- 015 1.33e- 015 6.66e- 016 5.3e- 015 1.33e- 0150-Schaffer N.4 50 1.e- 015 3.05e- 015 2.9e- 001 2.92- 001HimmelBlau 50 1.e- 015 1.6e- 016 8.05e- 016 3.83e- 016 9.12e- 016 1.46e- 016 3.35e- 016-25 1.e- 015 4.83e- 015 4.42e- 015 1.902e- 015 3.95e- 015 5.14e- 015 1.59e- 015 + Bird 50 1.e- 015- 1.035e+002- 1.067e+002- 1.05e +002-1.065e +002- 1.03e+002- 1.029e+002NA25 1.e- 015- 9.303e+001- 1.04e+002- 1.066e+002- 1.034e +002- 1.06e+002NA扩展立方体50 1.e- 015 3.31e- 015 4.98e- 005 6.1e- 008 1.93e-005 2.68e+00 5.46e- 008 +25 1.e- 015 5.701e- 008 5.212e- 005 7.1003e- 008 1.73e- 005 2.92e+009 5.86e- 007- Accommodation 50 1.e- 015 7.19e- 015 6.46e- 0127.99e- 015 3.63e- 013 3.09e+00 7.99e- 015- 25 1.e- 015 7.99e- 015 5.02e- 015 7.99e- 015 3.59e- 013 3.213e+00 4.4e- 015 +黄金50 1.e- 015 3.00e +00 3.00e +00 3.00e +00 3.00e +00 3.00e +00 3.00e+00NA 25 1.e- 015 3.00e+00 3.00e +00 3.00e +00 3.00e +00 3.00e +00NA格里万克50 1.e- 015 9.99e- 016 9.99e- 016 1.6e- 013 6.56e- 013 1.07e+00 7.77e- 015-25 1.e- 015 1.477e- 002 9.214e- 015 7.88e- 015 5.07e- 009 1.06e+00 9.9e- 016-拉斯特里金50 1.e- 015 1.79e+001 1.23e+002 7.47e+001 1.28e+002 1.52e+002 2.98e+001NA 25 1.e- 015 3.61e+001 1.181e+002 8.17e+001 1.727e+0021.674e+002 0NA罗森布罗克50 1.e- 015 9.6e- 016 1.07e- 008 7.88e- 016 3.9e- 009 1.07e+005 1.107e+001-25 1.e- 015 3.98e+00 1.403e- 008 6.9e- 015 1.56e- 011 7.15e+004 8.5e- 016-突出显示的值显示每个函数的总体最佳值。功能DVTRDE意义DE/best/1DE/rand/1DE/best-to-rand/1De/best/2DE/rand/2费什球体501.e-0159.73e-0166.9e-0167.532e-0169.655e-0167.17 e +06.04e-016+56M. Ramadas等人/Journal of King Saud UniversityXXFitnessCjx-cjj7我我终止条件停止是的执行FRENTE algorNo与 的 拟突变功能伊特比较试验状态的代价函数，如果条件满足，则7. 拟议的聚类本节讨论了使用k均值算法在聚类中DE的突变变量的实现数据集中的每个记录都被处理为所考虑的总体的随机样本现在考虑将这些数据集聚类到k个随机组。数据集的分区是根据某些目标函数进行的。这是一个选择优化问题的功能，以最小化或最大化一组给定的可用选项的功能。此函数确定所选解决方案的性能。通过计算质心和实体点之间的平方误差函数来执行每个解的适应度，其定义为：如果超过了最大迭代。图2示出了使用DE的变体的聚类技术的流程图。8. 聚类的实验结果在五个标准的数值数据集上进行了实验，比较了k均值算法，遗传算法（GA），粒子群优化算法（PSO），和经典DE与Festival在聚类中的性能。将k-均值聚类算法与遗传算法、粒子群算法、经典DE算法和带模糊控制的DE算法相结合聚类算法在i7核处理器、64位操作系统、12GB RAM上用MATLABr2008b实现，并与传统的聚类算法进行了比较。K各种算法都得到了有效的结果。 的jj2我联系我们其中xj是实体点，cj是质心，jjxj-cjj j j给出质心和实体点之间的距离。然后，对于每k个组，任意选择质心。使用欧几里德距离方法，计算每个数据与组中相应质心的距离。如果分配的质心没有变化，则K均值算法终止。将k-均值算法的结果作为DE算法的一个元素，其余元素随机初始化。FRESH算法执行所提出的变异和交叉功能。如果得到的结果值具有更好的成本函数，则结果值替换总体中的最小拟合值Festival算法终止得到每个数据集对应的聚类图和曲线图所获得的簇的簇质量是一致的。来自机器学习数据库UCI存储库的五个实时数据集Blake et al.（1998）使用。使用的数据集描述如下：(a) Fisher Iris数据集（n= 150，d= 4，k= 3）：这是一个标准数据集，有150个输入，用于3种不同的花类型：圣淘沙，弗吉尼亚和versicolour。这里测量了花的4个不同特征(b) Morse数据集（n= 1296，d= 5，k= 4）：该数据集由36行和36列组成，代表字母A-Z和数字0 - 9的Morse代码每个字母或数字-开始将数据聚类为k个组从组中随机初始化k个集群中心图2. DE在聚类中的变体流程图变化在聚类中心没有是的计算每个解决方案重新计算每组聚类的新聚类中心通过计算实体点和中心之间的欧氏距离，M. Ramadas等人/Journal of King Saud University57BER用短划线或点表示。莫尔斯电码由5个元素组成：短标记、长标记、字符内间隔、短间隔和中间隔。(c) Hogg数据集（n= 30，d= 6，k= 4）：该数据集是基于实验室的不同牛奶运输中细菌计数的报告。在这里，6组细菌计数是从5个不同的牛奶运输。(d) 天气数据集（n= 60，d= 5，k= 4）：这是从实验室测试中获得的无监督数据集。描述了天气数据库的主要特征，包括前景、温度、湿度、风和播放5个属性。(e) 股票数据集（n= 950，d= 10，k= 4）：这是从模拟股票收益率获得的真实数据集。在这里，10家不同公司的股票回报率被考虑在这个数据集中。这些数据集被用作聚类的输入，并获得了各种算法的结果。虹膜数据集的聚类图和曲线图已经在下面给出。图图3-6示出了对虹膜数据集分别执行遗传算法、PSO、DE和FSVM之后获得的聚类。X轴示出了虹膜数据集的花瓣长度，y轴示出了虹膜数据集的花瓣宽度。图图7-10 示出了在使用遗传算法、PSO、DE和图3.应用遗传算法后聚类。iris数据集的fixed。在这些图中，x轴显示迭代次数，y轴显示每次迭代获得的最佳成本。图5. 应用经典DE后的聚类。图6. 聚类后，应用FRESH算法。图4.应用PSO后的集群图7.遗传算法的曲线图。58M. Ramadas等人/Journal of King Saud University我我我Jjj x i -c jj=Nj8.1.1. 簇内距离这将计算聚类中成员的距离。它计算方法是，距离地面的距离的平方和，每个簇的bers到它的质心。最小的内集群距离给出了良好的集群。簇内距离的计算公式给出为：K内部¼Xxj-c2第1页ð8Þ其中xj-cj是粒子和质心之间的距离。簇内距离值越小，形成的簇越好。表4中给出了聚类内距离平均值的比较结果。图8. PSO的曲线图8.1.2. 簇间距离它计算不同聚类的所有质心对之间的距离。它是每个聚类质心之间距离的平方和。计算公式如下：国际货币基金组织国际货币基金组织国际货币基金组织这里ci和cj是聚类i和j的质心最大的类间距离，更好的集群形成。表5给出了各种算法的聚类间距离平均值的比较结果。8.1.3. 量化误差矢量量化将大数据集划分为具有几乎相同数量的最接近它们的点的聚类。矢量量化的目标是减小平均量化误差。量化误差Qe的公式如下：XK “Xnj第1页1/1J2# 、图9. 曲线图为Festival。图10. 经典DE的曲线图。8.1. 聚类质量可以基于以下参数来比较所获得的聚类的质量其中，cj是簇j的质心，Nj是簇j的粒子数，jjxj-cjjj是粒子与质心之间的距离。量化误差越低，聚类形成得越好的量化误差的结果列于表6中。8.1.4. 执行时间它是执行任务所花费的总时间。降低执行时间，更好的集群。各种算法的执行时间如表7所示。8.2. 确认索引有各种定量评价技术可用于测试聚类质量，这些技术被称为验证指数。它被研究人员用作测试聚类结果的工具。内部质量比较不同组群，而不参考外部知识。一个好的聚类技术具有高的类内相似性和低的类间相似性。在这里，我们将计算两个验证指数：Davies Bouldin（DB）指数和Calinski Harabasz（CH）指数。8.2.1. Davies Bouldin（DB）指数它是一个评估聚类算法的矩阵它是内部距离和与内部距离之比的函数（Davies和Bouldin，1979）。如果Ri，j是聚类方案的度量，Mi，j是i和j簇之间的间隔，Si是簇I的簇内散布，则DB索引被定义为Si和Mi，j的比率，其遵循以下性质：1. Ri;jP0：2. Ri;j<$Rj;iQe¼k10M. Ramadas等人/Journal of King Saud University59K最大iI jdci;cj¼：表4平均聚类内距离的比较表。数据集平均簇内距离K均值GAPSO古典DE费什Morse（k= 4）16.0116.1719.46718.80316.07虹膜（k= 3）43.748.2445.7822.2420.34霍格（k= 4）120.1122.3146.66107.0899.04天气（k= 4）169983.2170500.6181200.7170400.84169772.8股票收益（k= 4）201121342345.72256.81693.03表5类间平均距离比较表。数据集平均聚类间距离K均值GAPSO古典DE费什Morse（k= 4）230.12224.14159.12241.9277.55虹膜（k= 3）3851.34015.724037.64144.865781.3霍格（k= 4）4245.24542.573158.74527.94549.71天气（k= 4）34567834.236725821.430251191.236689042.5136798677.6股票收益（k= 4）12876.2211660.3218330.713,20626,889表6量化误差比较表。数据集量化误差K均值GAPSO古典DE费什Morse（k= 4）4.034.044.864.74.01虹膜（k= 3）14.0316.0815.257.416.78霍格（k= 4）28.730.5736.6526.724.76天气（k= 4）42567.242625.1545300.1742600.242443.2股票收益（k= 4）530.3533.5586.4564.2423.2表7执行时间比较表。数据集执行时间K均值GAPSO古典DE费什Morse（k= 4）14.825.124.317.315.46虹膜（k= 3）12.425.01815.3425.0314.33霍格（k= 4）24.125.5426.3426.7724.7天气（k= 4）46.355.3456.6760.6548.7股票收益（k= 4）14.3216.4515.5636.5315.323. 当SiPSj且Mi;j^Mi;k时，则Ri;j>Ri;k。4. 当Si^Sj且Mi;j6Mi;k时，则Ri;j>Ri;k。1974年）。CH指数的值越高，形成的聚类越好CH指数的公式如下：这里，DB索引的值越低，集群内数据的分离性和紧密性越好。DB索引的公式CH迹线Bnp-1迹S_W_np-kð12Þ给出为：其中SB是簇间散射矩阵，SW是内部散射1倍。dx-dxK 1/1矩阵，npð11Þ是聚类样本的数量，k是其中，k是聚类的数量，i，j是聚类标签，dxi和d（xj）是聚类I和j中到相应聚类质心dci的所有样本;cj是这些质心之间的距离。表8列出了各种算法的DB指数的比较结果。8.2.2. Calinski Harabasz（CH）指数这是计算聚类质量的另一种方法。它用于评估聚类的最佳数量（Calin'ski和Harabasz，8.3. 图形表示以上列表中的聚类质量和验证指数的值以图形方式进行了描述。图图11和图12描绘了曲线图，其示出了集群质量中的执行时间和验证索引中的CH索引的性能曲线。X轴代表使用的不同数据集，y轴代表获得的值。线图显示，FRENTE获得的值明显优于经典的FRENTE获得的值。DB¼集群表9给出了CH指数的比较结果。60M. Ramadas等人/Journal of King Saud University表8DB索引比较表。数据集DB索引K均值GAPSO古典DE费什Morse（k= 4）1.201.221.191.231.12虹膜（k= 3）0.630.780.680.640.61霍格（k= 4）0.4320.430.450.410.40天气（k= 4）0.410.450.380.350.34股票收益（k= 4）3.244.344.234.542.16表9CH指数比较表。数据集CH指数K均值GAPSO古典DE费什Morse（k= 4）0.780.670.670.641.065虹膜（k= 3）0.320.220.3010.210.34霍格（k= 4）0.170.1680.230.200.26天气（k= 4）0.1440.1460.1330.1430.148股票收益（k= 4）2.122.04842.011.0752.4832.521.510.5CH指数执行时间706050403020100Morse Iris Hogg天气股票图11. CH指数曲线。0Morse Iris Hogg天气股票图12. 执行时间曲线。DE方法。记录了五个不同数据集的数值。9. 结论本文提出了一种变异的差异进化变异策略，并将其应用于数据聚类的k-均值技术。实验结果表明，该算法比经典的DE算法效率更高，对聚类应用有显著的效果。此方法仅用于聚类数据集。进一步的工作可以扩展到图像和文本领域。此外，Festival技术仅适用于聚类的k均值技术。本文的工作可以进一步推广到层次凝聚法、DBSCAN法等聚类技术中。引用亚伯拉罕·A达斯·S，Konar A.，基于差分进化的文档聚类。在：进化计算，CEC 2006，IEEE Congress on IEEE，2006，pp. 1784- 1791年。Alguliev，R.M.，Ramiz，硕士，Chingiz，上午，2011.基于自适应差分进化算法的通用文档摘要句子选择。群体进化者。Comput. 1（4），213-222.Bezdek，J.C.，埃利希河，Full，W.，一九八四年FCM：模糊C均值聚类算法。Comput.地球科学10（2），191-203。布莱克·C Keough E.，Merz C.J.，UCI Repository of Machine Learning Database，1998。[联机]。网址：http://www.ics.uci.edu/www.example.com~mlearn/MLrepository.html>。Calin'ski，T.，Harabasz，J.，一九七四年聚类分析的枝晶方法。Commun.Stat.理论方法3（1），1-27。Coello，Carlos A.，Coello，David A.，作者声明：Van Veldhuizen，Lamont，Gary B.2002.进化算法求解多目标问题，第242卷，Kluwer Academic，纽约，2002年。戴维斯，D.L.，Bouldin，D. W.，一九七九年一种聚类分离方法。IEEE Trans. 模式肛门。马赫内特尔2，224-227.Fong，S.，Suash，D.，Xin-She，Yang，Yan，Zhuang，2014.使用自然启发的优化算法增强K-均值聚类的性能。Sci. World J. 2014，16.Hatamlou，A.，2013.黑洞：一种新的启发式数据聚类优化方法。信息科学222，175-184。Indrajit S.，Ujjwal M.，尼兰·J 2009.分类数据的微分模糊聚类，计算机科学中的方法和模型，2009年。 ICM2CS 2009。 国际会议论文集，IEEE，2009，pp。1比6贾恩，A.K.，2010.数据聚类：超越K-means的50年模式n。Lett. 31（8），651-666。Lloyd，S.，1982. PCM中的最小二乘量化。IEEE Trans. Inf. Theory 28，129- 13