基于中心聚类算法在大型和高维数据集中的应用

可在www.sciencedirect.com在线获取理论计算机科学电子笔记349（2020）49-67www.elsevier.com/locate/entcs一种基于中心聚类JaredLe'on1BorisCh信息学部Universidad Nacional de San Antonio Abad delCusco，秘鲁摘要基于中心的聚类是一组聚类问题，需要找到一个单一的元素，一个中心，代表整个集群。解决这类问题的算法对于聚类大型和高维数据集是非常有效的。在本文中，我们提出了一个类似的启发式LloydEMAX问题。此外，一个新的基于中心的聚类算法（SSO-C），这是基于一个群体智能技术称为社会蜘蛛优化。该算法最小化多目标优化函数，该函数定义为k均值和EMAX问题的目标函数的加权组合。此外，离散k-中心问题的近似算法被用作初始化种群的局部搜索策略。实验结果表明，SSO-C算法适合于寻找最大最优值，而EMAX算法在寻找中值和均值方面更优。关键词：中心聚类，近似算法，EMAX，多目标优化，社会蜘蛛优化。1介绍聚类通常被认为是无监督学习中最重要的问题。像任何其他无监督问题一样，它涉及在未标记数据中搜索模式和结构。聚类算法的目标是将相似的对象分组到称为聚类的集合中。由于问题的性质，它出现在许多研究领域，如数据压缩，图像分析，生物信息学和数据挖掘。1电邮地址：jared.leon. gmail.comunsaac.edu.pe2电子邮件：boris. unsaac.edu.pe3电子邮件：lauro. unsaac.edu.pe4电子邮件：jose. unsaac.edu.pehttps://doi.org/10.1016/j.entcs.2020.02.0121571-0661/© 2020作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。50J. León等人/理论计算机科学电子笔记349（2020）49从本质上讲，聚类不是一个定义明确的任务，而是一个需要解决的非常普遍的问题。因此，许多定义良好的问题和算法已经被提出来用于这个任务。关于什么是集群以及如何形成集群，有很多不同的概念和定义。关于什么类型的数据可以被聚类也没有通用的约定。因此，所有这些多样性导致了几种聚类模型[2]。一个非常流行的模型叫做基于中心的模型。基于中心的聚类是通过称为聚类“中心”的元素来表示整个聚类的任务虽然这个问题有很多变体，但基本思想是进行所谓的严格分区聚类，其中每个元素都属于一个簇。最著名的基于中心的聚类算法是k-均值或劳埃德这是最常用的算法之一，可能是因为它的简单性和它在大多数情况下提供的相当好的结果。尽管如此，该算法的主要问题是数据集中当前离群值对其的影响[19]。针对k-均值算法中的离群效应，已经提出了许多算法.然而，它们中很少有严格的划分聚类算法，也就是说，他们中的许多人试图识别离群点，并删除它们。提出了一种基于中心的严格划分聚类算法SSO-CSSO-C算法试图优化两个基于中心的问题。其中一个是k-means，另一个是EMAX，这是一个密切相关的问题，需要找到一个更强大的聚类解决方案。考虑到两个问题解的相关性，将两个问题浓缩在一个单目标优化函数中。该函数将使用称为社交蜘蛛优化（SSO）的全局优化算法进行优化。此外，k-中心问题的近似算法被用作用于生成初始解的局部搜索，即用于开始搜索的初始位置SSO-C算法是先前提出的基于中心的聚类算法的更通用版本[27]，称为SSO-A。在实验中，在13个数据集上评估了四种算法：k-均值，EMAX，SSO-A和SSO-C。生成了六个合成数据集，并拍摄了七个真实数据集。所有数据集都有点的真实标签，因此使用称为调整互信息的聚类度量[28]来评估每个预测的质量。在每个数据集上执行每个算法的多次执行，报告平均值、中位数和最高评分。本文的结构如下。第二节介绍了k-均值问题和Lloyd第3节定义了k-均值问题的一个更鲁棒的变体，并在Lloyd算法中使用类似的启发式近似求解，然后将该算法作为这两个问题的多目标优化的解决方案。还解释了作为初始化的局部搜索策略，用于少数起始点。第4节显示了在四个基于中心的算法上执行这四种算法分别在合成数据集和真实数据集上进行了实验。最后，结论见第6节。J. León等人/理论计算机科学电子笔记349（2020）49512ΣΣi=1ni=1 一IJ2背景2.1K-meansK-均值通常被称为聚类算法而不是优化问题。在本书中，该术语根据上下文可互换使用。k-均值优化问题定义为：设S是n个点的集合{x1，x2，.，xn}在度量空间（Rd，l2）中，其中d定义维数空间，l2表示欧氏度量，k> 1为整数。求一个集合C ={c1，c2，.，c k}和一个矩阵A=[ai j]的si z en×k，使得如下的翼最小化：n kJ1（C，A）=aij×xi−cj×2（一）i=1j =1须遵守：aij∈ {0，1}对于所有i，j（2）Ka ij= 1，对于所有i。（三）j=1问题的第一个参数，集合C，在与S相同的空间中包含k个点。这些点被称为中心。每个中心的目的是代表一个簇，因此S中的每个点都被分配到一个唯一的中心，因此，分配到一个唯一的簇。矩阵A定义了这些分配。一个点xi被称为中心cj，当且仅当元素aij等于1。还有，（3）保证集合S的每个元素都被分配给C的一个中心。目标是找到中心集合C和分配矩阵A，使得从每个点到它被分配到的中心的欧几里得距离的平方和最小化。k-均值问题被证明是NP-Hard问题[24]。然而，有一个众所周知的启发式近似的解决方案的问题。启发式算法包括迭代地解决以下子问题：• P1：确定A=A，并求解约化问题J1（A，C）.•P2：固定C =C，求解约化问题J1（A，C）.P1和P2可以很容易地在多项式时间内使用以下引理求解。引理2.1（[20]）给定k-m问题，设A={ai j}bfixed。 函数J1最小化当且仅当C的每个中心定义为S 的点分配给它。 也就是说，如果Σnaijxicj=对于所有J。（四）52J. León等人/理论计算机科学电子笔记349（2020）49.2引理2.2（[20]）给定k-m问题，令C={cj}befixed。 函数J1最小化当且仅当S的每一点都被分配到C的最靠近它的中心。 也就是说，仅当矩阵A具有以下条目时：国际新闻报 =1ifj=argmink×xi−ck×20否则对于所有的i，j。（五）求解P1意味着将中心集定义为聚类的质心。求解P2意味着根据由中心集C导出的Voronoi图对集合S进行非正式地说，Voronoi图是将平面划分为由一组固定点引起的单元，其中单元内的每个点都更接近这是一个比任何其他的固定点，产生这种细胞的固定点。[15]关于Voronoi图的更多信息，请参见[16]该算法通常从解决问题P2开始，用随机值固定中心。 由此产生的算法通常被称为k-均值算法，由于其流行性，也被称为劳埃德已经提出了几种用于更好地初始化中心的方法，其中最知名的是k-means++算法[4]。可以证明k均值的收敛性，但是不能保证找到全局最小值[18]。2.2社交蜘蛛优化优化问题有时很难以封闭形式求解。在这项工作中，将面临一个优化问题，需要一个全局优化算法来解决它。与最先进的算法相比，最近的群体智能算法之一是社会蜘蛛优化算法（SSO）[10]。群体智能是一组简单智能体处理群体行为的集体智能[13]。单点登录算法是在模拟社会蜘蛛协作行为的基础上提出的.该算法假设整个搜索空间是一个公共网络，其中蜘蛛的每个位置代表问题的解决方案。 每个spideri接收代表其解决方案质量的权重wi。通过公共网络传输的信息以振动的形式编码。由蜘蛛j产生并由蜘蛛i感知的振动根据下式建模：Vibij =wj·e−s i− s j<$2。（六）振动强度随着蜘蛛距离的平方而减小该算法区分男性和女性代理人。整个过程包括迭代仿真三个合作算子：女性合作算子，男性合作算子和交配交配算子。当执行这些操作时，蜘蛛会根据生物启发的规律改变它们的位置，以探索搜索空间并找到更好的解决方案。该算法被证明有更好的性能，在运行时间和解决方案的质量比其他国家的最先进的全局优化算法时，与一组著名的基准函数进行评估。J. León等人/理论计算机科学电子笔记349（2020）4953ΣΣ几何平均中位数3提案3.1Emax由于其基于中心的性质，k均值算法是无监督机器学习中最简单和最流行的算法之一。然而，基于中心的算法通常对数据进行假设，例如：假设聚类是超球形的并且大小均匀在实际应用中，k-均值问题的解决方案会对均值引起的原始集合进行划分，这一事实有一个缺点：由于目标函数中的平方距离之和，非典型值对中心定位有很大的影响。 大的距离对目标函数的影响比小的距离大，因为每个点得到的惩罚随着到固定点的距离的平方而增长。因此，如果一个点到它被分配的中心的距离为2d，它将具有比到它被分配的中心的距离为d的点的惩罚的两倍大得多的惩罚。当要聚类的集合包含许多离群值时，这种行为变得更加重要，因为离群值通常异常地远离典型点，从而远离理想中心。如果这个点被分配给一个被典型点包围的中心，它将导致它的惩罚很大，使得中心的位置在下一次迭代中显著改变，以减少惩罚。这在图1中示出，其中异常值生成中心点的重新调整以减小目标函数的值。在同一个图中，它还显示了一个特殊点（几何中位数），我们将在后面讨论。解决异常值效应和创建更鲁棒算法的常见方法是用以下表达式改变目标函数n kaij×xi−cj×1，（7）i=1j =1其中集合S不再属于（Rd，l2），而是属于（Rd，l1），l1是1-范数或曼哈顿范数。该函数的优点是在离群值场景中更鲁棒，因为它最小化了相对于1范数距离度量的聚类内误差，而不是平方2范数距离度量。问题P1和P2对于这个新问题保持不变。因此，这使得图1. 一个中心被一个离群值所包围。54J. León等人/理论计算机科学电子笔记349（2020）49ΣΣΣ使用上面提到的启发式在计算新的中心时，取每个维度的中值，然后合并。此外，S的点根据由中心集合C相对于1-范数距离度量诱导的Voronoi图来这种k-均值算法的变体通常称为k-中位数算法[21]。可以开发k均值和k中值之间的中间算法，使目标函数发生小的变化。让设S是n个点的集合{x1，x2，.，xn}，其中d定义维数空间，l2表示欧氏度量，设k> 1e为整数。 求一个集合C ={c1，c2， . ，c，k}和大小为n×k矩阵A=[ai，j]n kJ2（C，A）=aij×xi−cj×2（8）i=1j =1须遵守：cj∈Rd对于所有j（9）aij∈ {0，1}对于所有i，j（10）Ka ij= 1，对于所有i。（十一）j=1正如可以观察到的那样，k-均值问题和这个新问题之间的唯一区别是目标函数。函数J1取欧氏距离平方的聚类内和。另一方面，函数J2取欧氏距离的簇内和.到目前为止，文献中还没有EMAX问题的正式定义或用于解决它的算法。然而，EMAX问题在过去被不正式地处理，并且一些试图近似它的算法被实现为聚类包的一部分[8]。此外，在[27]中提出了一种全局优化方法，使用社会蜘蛛优化直接近似它。该算法将用于实验中，名为SSO-A。EMAX问题可以用另一种方式处理：用于k均值问题的相同启发式可以用于近似求解EMAX问题。首先，P1和P2可以用相同的方式定义• P1：固定A=A，求解约化问题J2（A，C）.•P2：固定C =C，求解约化问题J2（A，C）.然后，如在k-均值算法中，两个子问题都可以从先前迭代中获得解来迭代求解。如前所述，最小化J2的方法是当集合C固定时，与k均值算法相同J. León等人/理论计算机科学电子笔记349（2020）4955.⇒Σˆn⇒Σ⇐i=1引理3.1给定EMAX问题，设C={cj}b∈d。 则函数J2最小化当且仅当S的每一点都赋给C的最近中心到它。 也就是说，仅当矩阵A具有以下条目时：国际新闻报 =1ifj=argmink×xi−ck×20否则对于所有的i，j。（十二）证明（=）由于一点的中心分配是唯一的，且相互独立，若J2（C_n，A）是最小的，则对于每个chp，txi，下列表达式是最小的.Kaij×xi−cj×2（13）j=1则由y（10）和d（11），（13）对于一个s pecific j，i等于o×xi−cj×2。 因此，只有当j得到最小化表达式的值时，这才能为真。（f=）If×xi−cj ×2是最小值，则对于每个xi，由于（10）和（11），（13）是最这意味着J2（C，A）对每个xi是最小的.Q这解决了子问题P2。然而，解决问题P1引理3.2给定EMAX问题，令A={ai j}befix ed。 则函数J2最小化当且仅当C的每个中心被定义为S中分配给它的点的几何中值。 也就是说，如果cj∈argmin<$ai j×xi−c×2，对于a llj。（十四）证明（=）中心的位置并不包含未分配给它的点，因此中心与其他点无关。若J2（C，A）是minimum，则对于每个中心cj，下列表达式也是minimum：nai j×xi−cj×2。（十五）i=1因此，cj必须是使（15）最小化的点（=）如果c j是使（15）最小化的中心，则目标函数也是最小的，因为它是f_p_t_minimums的和。所以J2（C，A）是对每个cj的最小值.Q可以看出，解决子问题P1需要找到一个点，使一组固定点与它之间的欧氏距离之和最小化，这个点被称为几何中位数。 寻找一组点的几何中值也被称为费马-韦伯问题。尽管古老的自然这个问题，几乎没有理论保证来解决它。这个问题首先是在十七世纪由皮埃尔·德·费马研究三点的情况[22]，c∈Rd56J. León等人/理论计算机科学电子笔记349（2020）49.Σi=1你好，Σ尽管EvangelistaTorricelli使用尺子和指南针优雅地构造了几何中值，但是对于大量的点，没有类似的构造。事实上，即使对于五个点，几何中值也不能用有理数上的根式表示[5]，并且也没有精确的算法可以使用算术运算和k次根来解决这个问题。近似问题已被广泛研究了大量的点，作为结果，给出了许多多项式时间算法的近似几何中值问题。在[9]中，给出了许多这些算法的汇编，并提出了一个近似线性时间算法，用于以任意精度找到集合的几何中值已经提出了许多算法作为近似方案来寻找几何中值。它们中的大多数利用了这样一个事实，即从搜索点到所有其他点的距离之和是凸函数，因为到特定点的距离也是凸的。此外，还证明了当点不共线时几何中值是唯一的[26]。由于在大多数情况下，函数是凸的，并且有一个最小值，使用迭代地减少距离之和的搜索算法可以被认为是Weiszfeld算法[ 29 ]是一种简单且非常流行的几何中值搜索算法该算法迭代地创建几何中值的新估计当算法的一个估计落在其中一个点上时，算法无法收敛在实践中，该算法几乎在所有情况下收敛给定一个集合p1，p2，. t个点中的p t个点，该算法首先为几何中值创建初始估计c（0），确保该点与任何给定点不同。然后，该算法使用以下规则迭代地将当前估计c（h）更新为c（h+1）c（h+1）=不i=1PIT×pi−c（h）×21×pi−c（h）×2.（十六）在这项工作中采用的方法是使用Weiszfeld的算法来计算几何中值。该算法可以用实现相同目标的任何其他算法代替。当在EMAX算法中使用Weiszfeld算法时最后，算法收敛的一个相当自然的标准是，像在k均值算法中，当聚类不再改变时。给定集合C和矩阵A，可以容易地恢复簇。EMAX的整个过程在算法1中示出。算法1 EMAX算法输入：集合S ∈（Rd，l2），k.输出：聚类（C1，C2，...，C k）的S.1：C←初始中心集2：当未达到收敛标准时，3：如果j=argmink×xi−ck×2，则将每个xi∈ S分配给cjΣJ. León等人/理论计算机科学电子笔记349（2020）4957J2S1J1S2S3S4S6S54：对于j= 1至k，5：令P ={p1，p2，...， p m}是S中分配给c j的点的集合6：cj←P的几何中位数第七章： 设（C1，C2，.，C k）是k个不同的空簇8：对于i，j，使得xi被分配给cjdo9：将xi置于Cj中返回 （C1，C2，...，（C k）在算法的第1行中声明的中心的值可以被随机初始化。如在k-均值中，该算法迭代地求解P1和P2，将每个点分配到其最近的中心，然后重新计算中心作为几何中值（使用Weiszfeld这最后一步的目的是创建一个更强大的算法比k均值算法时，处理数据集中的多个离群值。 问题k-均值和EMAX可以使用多目标优化同时解决。这是非常合适的，因为这两个问题具有相同的参数和条件。它们之间唯一的区别是目标函数。3.2多目标优化解决多目标优化需要非常不同的方法比那些用来解决单目标问题。求解多目标优化问题时的一个常见准则是搜索帕累托边界。目标是在相同条件下同时极小化J1和J2为了说明帕累托边界，让我们假设两个问题都有六个可行的解决方案：s1，...，s6具有不同的值时，评估与J1和J2如图所示。二、在多目标优化中，通常不会找到一个可行的解决方案，图2.J1和J2的一组可行解。 帕累托最优解是s1，s4和s5，因为它们不受任何其他解决方案的支配58J. León等人/理论计算机科学电子笔记349（2020）492图3.左：由J1和J2求值时的解的行为.右：在最小值附近看到的相同图。最小化所有目标（在本例中为J1和J2）。因此，我们的任务是找到帕累托最优解：那些在不降低至少一个其他目标的情况下，任何其他解决方案都无法改进的可行解。回到这个例子，很明显，当用第一个目标进行评估时，s1是一个更好的候选者，即J1（s1）0且α+β= 1。而且，原始问题的条件保持不变。通过这种方式，我们可以通过一个优化任务为这两个问题找到好的解决方案。该问题不适合于连续优化算法，因为搜索域不是连续的，而且许多优化算法在每次迭代中都需要函数的梯度其他一些也需要60J. León等人/理论计算机科学电子笔记349（2020）49.2FF函数在特定点上的值，在这种情况下，无法定义。我们可以用C来定义目标函数，正如前面的情况一样，最优策略是将S的每个点xi分配给C中最接近xi的中心。这一事实的证明是平凡的，直接由引理2.2和3.1得出。因此，从这一点开始，矩阵A的元素的值将永久地被定义为与前面的情况类似：国际新闻报 =1ifj=argmink×xi−ck×20否则对于所有的i，j。（十八）目标函数现在完全依赖于C：n kF1（C）=αij.α×xi−cj×2+β×xi−cj×2<$。（十九）i=1j =1第2.2节中描述的社交蜘蛛优化算法将用于最小化F1。为了使目标函数适合于算法，函数的参数C可以被“转换”成单个变量，使得F1：Rkd→R.每个蜘蛛将是一个kd维向量，作为其结构：（c11，c12，.， c1 d，.， c k1，c k2，.， c kd）∈ Rkd.`c1x`ckx由于这是一个最小化问题，最佳s和最差s的值（算法固有的）以以下方式重新定义N最佳s= min1（si），（20）i=1N最坏s = max 1（s i）。（二十一）i=1N是群体中蜘蛛的数量。考虑到C的中心位置不能在由S的点建立的限制之外，将选择位置值的下限和上限。我们可以用下面的规则来处理：如果c是F1的参数，那么c的第i个分量的最小值将是S的所有点中分量（（i-1）modk）+1的最小值。类似地，c的第i个分量的最大值将是所有点中的分量（（i-1）modk）+1的最大值。 S.在算法执行过程中，蜘蛛产生的振动被其他群体成员感知。通过（6）对作为由蜘蛛j发射的信息的结果的由蜘蛛i感知的振动进行建模。这种行为可以在图中看到。四、可以观察到，某些蜘蛛感知到的振动强度随着到产生它的蜘蛛的欧几里得距离的平方而减小。 取决在S中的点的距离上，成对蜘蛛之间的距离可以J. León等人/理论计算机科学电子笔记349（2020）4961·dx∈Sc∈C1.00.8Vib =eIJ−d2IJ0.60.40.2国际新闻报0.00.00.51.01.52.0图4.振动强度的行为是蜘蛛之间的平方欧几里得距离的函数。非常大;使他们无法进行通信，因为振动强度实际上为零。在原有的单点登录算法中，没有直接的方法来处理这个问题。解决这个问题的一个建议策略是在计算振动为1时考虑可能的最大距离。5.为了使这为真，根据以下替换，每个距离dij被替换为dJijdJijDij=1。五、（二十二）Max其中dmax是蜘蛛i和群体中其他蜘蛛之间的最大距离。选择这种归一化是因为振动函数右侧约80%的区域在0和1之间。5.蜘蛛的一个理想的属性是，它们可以覆盖大部分的搜索空间与初始化。根据最初的位置，一些蜘蛛比其他人有更大的概率达到局部最优。将一些蜘蛛的位置初始化到F的相关函数的一些局部最优值附近可以提高收敛性。为了做到这一点，并考虑到离群值是关注的中心;我们将假设集合S在其结构中具有自然属性，以解决设施定位和聚类中的有用问题。 这个问题叫做k-中心和扰动弹性的性质。k-中心问题是找到一个集合C ={c1，...，c k}个中心，以最小化：J3（C）=max.min×x−c×2Ω。（二十三）k-中心问题的目标函数与k-均值和EMAX问题有很大的不同该函数也仅依赖于C，因为每个点都将被分配到最近的中心。 中心的集合必须属于S， 所以它本质上是一个组合优化问题扰动恢复力[7]是一个对集合S假设的稳定性概念。这一特性意味着，如果点之间的距离由于小扰动而改变，则k-均值的最优解是相同的形式上，ρ称为α-扰动62J. León等人/理论计算机科学电子笔记349（2020）49−→Σ2Σ一个距离函数，如果对所有x，y∈ S，×x-y ×2≤ ρ（x，y）≤ α×x-y ×2。（二十四）然后，如果对于距离函数的任何α-扰动，最佳k-中心聚类不改变，则对（S，l2）满足k-中心的α-扰动弹性。这是一个特殊的自然假设，因为当点之间的距离增加一个常数因子时，异常值效应会变大，特别是当用J2计算时。这个假设降低了这种可能性。下面的定理是有帮助的，当试图找到最佳的解决方案，扰动恢复下k-中心问题定理3.3（[6]）给定一个聚类实例（S，l~ 2）满足k-中心的α-扰动弹性，以及一个k-中心集C，它是k-中心的α-逼近因子。C 诱导的Voronoi划分是最优聚类。该结果表明，假设S在欧氏距离度量下具有扰动弹性，k-中心的α-近似算法将给出最优解对于k-中心问题[1]，已经设计了精确算法和近似算法.在文献[17]中，证明了除非P/ = NP，否则不存在逼近因子小于2的多项式时间算法，并给出了该问题的一个 2如果三角不等式成立，则该算法成功地找到2-近似解，这是（S，l2）的情况。利用这种2-近似贪婪算法，我们可以生成k-中心问题的解，作为初始种群中某些个体的局部搜索策略。SS O - C 算 法 的整个过程在算法2中示出。算法2SSO-C算法输入：一个集合S ∈（Rd，l2），k，α，ns，n it.输出：聚类（C1，C2，...，C k）的S.1：s←（−→0，−→0， . ，−→0）`˛n¸sx2：对于j= 1至k，3：C←贪婪k-中心（S，k）4：si←C5：β←1 −α第六章： F1（C）=ni=1kj=1 国际新闻报.α×xi−cj×2+β×xi−cj×2<$7：x←SSO（F1（C），s，ns，nit）第八章： 得到C ={c1，c2，.，c k}从x九： 设（C1，C2，.，C k）是k个不同的空簇10：对于i，j，使得xi被分配给cjdo11：将xi置于Cj中J. León等人/理论计算机科学电子笔记349（2020）4963返回 （C1，C2，...，（C k）算法2首先在第1行创建ns个第2行到第4行用k-中心问题的2-近似解初始化前k个由于α的值作为输入提供，因此在第5行中计算β的值然后，在第6行和第7行中定义目标函数，并在SSO算法中使用均匀随机值初始化空蜘蛛然后执行全局优化并恢复最佳蜘蛛。然后在第10行和第11行中获得聚类。该算法的输出是集合S的聚类。3.3数据集出于实验目的，生成了一组六个合成数据集。它们的特性详述如下。数据集的关键信息见表1。合成数据集的图可以在图5中看到。此外，从UCI机器学习库中获取了一组七个真实数据集[14]。表2显示了关于真实数据集的一些信息。第一个合成数据集对于基本的聚类算法来说相对简单。该数据集包含三个明显分离的聚类。第二个合成数据集包含两个近聚类和两个远离群值。第三个合成数据集包含根据多变量高斯概率分布生成的九个聚类，使用表1中指定的平均值μ和协方差矩阵μ。第四个合成数据集包含根据每个维度的Gamma分布使用表1中指定的形状a和速率b生成的三个聚类。最后，根据多元高斯概率分布，使用表1所示的μ和μ，生成第五和第六个数据集。4实验四种算法：k-均值，EMAX，SSO-A[27]和SSO-C使用来自UCI机器学习库的六个合成数据集和七个真实数据集进行了评估[14]：Iris，Vowel Indian，Crude Oil，Balance Scale，Breast Cancer和Wine。SSSO-C算法中参数α的值固定为0。2.这样，算法给第二个问题大约80%的总优先级。为了评估聚类质量，调整后的互信息度量[28]与聚类算法预测的标签和真实标签一起使用。度量的范围在-1到1之间变化，0表示聚类的随机预测，1表示完美预测（在某些情况下可能出现负值）。对于每种算法，在每个数据集上总共执行了50次。对于每个数据集，执行的最大值、中位数和平均值（使用AMI度量）如表3所示，其中该行的最佳值以粗体突出显示。使用C语言（gcc版本8.1.0）进行数值实验64J. León等人/理论计算机科学电子笔记349（2020）49数据1空间点每个群集R2集群集群集群150分250分350分数据2空间点每个群集R2集群集群1240分40分数据3空间每个群集的μΣR2集 群 集群集群123456789100100100100100100100100100点，点，点点（−2，2）（0，2）（2，2）（−2，0）（0，0）（2，0）（−2，−2）（0，−2）（2，−2）1. 6900001.69数据4空间每个群集的一BR2集群集群集群123100100100点点222二分之一1三分之二数据5空间每个群集的μΣR2集 群 集群集群12345200200200200200点点点（1，1）（2，2）（3，3）（1，3）（3，1）000.10分钟10分钟。1数据空间每个群集的μΣ集群1400 点（2，1. 44J. León等人/理论计算机科学电子笔记349（2020）49652）（6，6）（6，2）00001.44R2集群2400 点集群3400 点表1关于合成数据集的数据集虹膜 元音油平衡癌酒玻璃尺寸435430138集群3633236点15087156625569178214表2关于真实数据集的由MinGW-W 64构建）在3.40GHz Intel Core i7-6700上，具有16 GB RAM内存，运行Windows 10版本1809作为操作系统。66J. León等人/理论计算机科学电子笔记349（2020）49合成数据集15四、5合成数据集2合成数据集36四、0443 .第三章。5233. 0二、50210151050−5−10−150 1 2 3 4合成数据集4−10 −5 0 5 10 15二、01 .一、51 .一、00。5四、03 .第三章。53 .第三章。0二、5二、01 .一、51 .一、00。50。01 .一、01 .一、5二、0二、53 .第三章。03 .第三章。5四、0四、5合成数据集50。00。51 .一、01 .一、5二、0二、53 .第三章。03 .第三章。5四、0−2−4−6−6− 4−2 0 2 4 6合成数据集61086420−2−2 0 2 4 6 8 10图5.用于执行实验的合成数据集数据集合成SSO-a数据集k-均值EmaxSSO-C数据集真实数据集SSO-ak-均值EmaxSSO-C最大1.0001.0001.0001.000最大0.7930.7480.7870.829S.数据集1中值1.0001.0001.0001.000虹膜中值0.7130.7480.7570.762是说1.0001.0001.0001.000是说0.7160.7430.7630.765最大1.0000.8541.0001.000最大0.5170.4770.5090.517S. 数据集2中值1.0000.8021.0001.000元音印度语中值0.4510.4590.4900.453是说0.9640.8130.6641.000是说0.4450.4630.4930.452最大0.3530.3410.3520.366最大0.2500.2360.2720.250S. 数据集3中值0.3360.3400.3420.342原油中值0.2040.1820.2720.182是说0.3360.3380.3430.343是说0.2010.1900.2490.189最大0.8060.7700.8130.814最大0.2740.1600.1340.253S. 数据集4中值0.7610.7700.8130.790平衡量表中值0.2140.1150.1170.109是说0.7190.7700.8130.784是说0.2230.1060.1140.113最大0.8880.8850.8820.898最大0.4530.4220.4580.440S. 数据集5中值0.8630.8810.8820.884乳腺癌中值0.3510.4220.4580.374是说0.8520.8820.8820.882是说0.3220.4220.4580.369最大0.7700.7560.7580.779最大0.4320.4230.4270.432S. 数据集6中值0.7520.7540.7550.755酒中值0.4130.4230.4190.423是说0.7480.7540.7550.757是说0.4190.4080.4140.417玻璃最大中值是说0.3010.1770.1650.3160.2740.2900.3190.3190.3190.3890.3180.320表3在四种算法上进行的实验结果5讨论从表3中可以观察到：EMAX在关于最大值、中值和平均值的几乎所有数据集中具有比k均值更好的结果;SSO-C在关于最大值、中值和平均值的几乎所有数据集中具有J. León等人/理论计算机科学电子笔记349（2020）4967比SSO-A更好的结果。68J. León等人/理论计算机科学电子笔记349（2020）49数据集控制我 算法秩p值α/i数据集控制我算法秩p值α/iSSO-C3k-均值3.631.29E-140.017Emax3SSO-a3.181.48E-150.017S. 数据集2(Rank：2Emax2.499.95E-040.025元音(Rank：2SSO-C2.961.03E-120.0251.64）1SSO-a2.242.00E-020.0501.12）1k-均值2.743.51E-100.050SSO-C3SSO-a3.084.04E-050.017Emax3k-均值3.174.30E-170.017S. 数据集3(Rank：2k-均值2.764.00E-030.025油(Rank：2SSO-C3.174.30E-170.025（2.02）1Emax2.146.40E-010.050（1.00）1SSO-a2.661.28E-100.050Emax3SSO-a3.231.59E-160.017SSO-a3k-均值3.342.58E-190.017S. 数据集4(Rank：2k-均值3.222.20E-160.025平衡(Rank：2SSO-C3.029.49E-150.0251.10）1SSO-C2.451.71E-070.050（1.02）1Emax2.625.76E-100.050Emax3SSO-a3.564.58E-110.017Emax3SSO-a3.322.58E-190.017S. 数据集5(Rank：2k-均值2.548.00E-030.025癌(Rank：2SSO-C3.235.78E-180.0251.86）1SSO-C2.044.80E-010.050（1.00）1k-均值2.451.96E-080.050Emax3k-均值2.873.16E-040.017SSO-a3k-均值3.096.54E-040.017S. 数据集6(Rank：2SSO-a2.863.66E-040.025酒(Rank：2Emax2.473.10E-010.0251.94）1SSO-C2.331.30E-010.050（2.21）1SSO-C2.239.30E-010.050SSO-C3SSO-a3.512.76E-150.017Emax3SSO-a3.923.39E-210.017虹膜(Rank：2k-均值3.221.22E-110.025玻璃(Rank：2k-均值2.664.87E-060.025（1.47）1Emax1.802.00E-010.050（1.48）1SSO-C1.947.00E-020.050表4Holm测试的结果的平均值。当考虑所有算法时，SSO-C在几乎所有数据集的最大值方面都显示出最好的结果。此外，对于中位数和平均值，EMAX和SSO-C在相同数量的情况下（13例中的7例）具有最佳结果。统计测试（根据[11]，也见[16]和[12]）在算法的结果（50个元素的样本）中以以下方式进行：（a）首先，进行Friedman测试以测试实验中使用的算法具有相同性能的零假设，（b）当Friedman测试的零假设被拒绝时，然后进行Holm测试以测试控制算法具有与其他算法相同性能的零假设。为了进行统计检验，使用CONTROLTEST软件包（https://sci2s.ugr.es/sicidm），显著性水平为α = 0。05默认弗里德曼检验的零假设在所有数据