没有合适的资源?快使用搜索试试~ 我知道了~
沙特国王大学学报一种自适应离群点去除辅助k-means聚类算法Nawaf H.M.M.Shrifana,b,Muhammad F.阿克巴尔a,诺阿什迪马特伊萨a,a电子电气工程学院,马来西亚槟榔屿尼邦特巴尔14300号马来西亚萨恩斯大学工程学院b也门沙布瓦亚丁大学石油和矿物学院阿提奇莱因福奥文章历史记录:2021年4月1日收到2021年6月9日修订2021年7月2日接受2021年7月13日在线提供保留字:数据聚类改进的k-means离群点剔除改进的TukeyA B S T R A C TK-means是十大流行的聚类算法之一。然而,由于真实数据集中存在离群值,k-means表现不佳。此外,不同的距离度量会导致数据聚类精度的变化。从离群点去除和距离度量的角度提高k-means算法的聚类精度仍然是数据聚类领域的一个研究热点。在此,提出了一种新的修改的k-means算法的基础上Tukey的规则结合一个新的距离度量。对标准Tukey规则进行修改,通过考虑数据是否分布在输入数据的左、右或甚至平均值,自适应地去除离群值。在计算质心之前,将离群值的消除应用于所提出的k均值修改中,以最小化离群值的影响。同时,提出了一种新的距离度量,将每个数据点分配到最近的聚类。在本研究中,改进的k-means算法显著提高了聚类精度和质心收敛性。此外,建议的距离度量的整体性能优于大多数文献距离度量。本文版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍数据聚类是一种广泛应用的数据分析技术,用于将底层模式分类到一组组或聚类中。每个聚类都由相似的数据组成,使其与其他聚类大不相同聚类过程简化了数据发现的建模,并广泛用于各种应用 , 例 如 图 像 分 割 ( Siddiqui 等 人 , 2013 ) 、 生 物 信 息 学( UmaMaheswari , 2020 ) 和 无 损 检 测 ( Shrifan 等 人 , 2021年)。最近,数据聚类用于分析和了解冠状病毒(COVID-19)在意大利的分布(Doroshenko,2020)。数据聚类有多种方法,包括基于划分的方法、基于层次的方法和基于密度的方法。诸如模糊c均值(FCM)(Bezdek等人, 1981年 :最远的 第 一次*通讯作者。电 子 邮 件 地 址 : nawaf_shrifan@student.usm.my ( N.H.M.M. ) Shrifan ) ,firdaus. akbar@usm.myM.F. Akbar),ashidi@usm.my(N.A.M. Isa)。沙特国王大学负责同行审查算法(FFA)(Sharmila,2013)定义已知数量的聚类,并基于以下条件将每个数据对象分配到最近的质心距离度量。在基于层次的方法中,包括层次聚类算法(HCA)(Hochbaum和Shmoys,1985)和使用代表的聚类(CURE)(Guha等人,1998)中,在没有关于簇的数目的任何先验知识的情况下建立簇的树结构。此后,一组数据点被合并到更一般的聚类中,或者被顺序地划分为更小的聚类。在基于密度的聚类中,基于给定半径中的数据点的密度来构建数据聚类,其包括最小数量的实例,诸如具有噪声的应用的基于密度的空间聚类(DBSCAN)( Ester 等 人 , 1996 ) 和 基 于 分 布 的 大 型 空 间 数 据 库 聚 类(DBCLASD)(Xiaowei et al., 1998年)。考虑到聚类算法的范围很广,很难指定一个特定的算法明显优于另一个算法(Aggarwal和Reddy,2013)。它们之间的选择取决于数据集的属性和输入参数(Govindaraju等人, 2018年)。另一方面,基于优化算法的数据聚类是最稳健的技术之一,这是由于其发现数据聚类的最优形式的能力,诸如遗传算法(GA)(Maulik和Bandyopadhyay,2000)、组合粒子群优化(CPSO)(Jarboui等人,2007)和多体优化器(MVO)(Shukri等人, 2018年)。的优越性https://doi.org/10.1016/j.jksuci.2021.07.0031319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。制作和主办:Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页:www.sciencedirect.comNHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报6366优化技术在聚类准确性方面肯定地克服了许多传统的聚类技术。然而,这些算法仍然遭受陷入局部极值(Zhang等人,2011年)和产生冗余解决方案(Benmessahel和Touahria,2010年)。此外,基于盲源分离技术提出了许多无监督聚类技术,盲源分离技术将一组观测建模为线性组合,以在统计上分离成独立源或分量,例如独立分量分析(ICA)(Safont等人,2017)、主成分分析(PCA)(Kaya等人, 2017)和非负矩阵分解(NNFM)(LaxmiLydia等人,2020年)。 尽管基于数据聚类的源分离技术在线性数据上的令人鼓舞的性能,但是由于离群值的存在降低了数据线性度和聚类准确性,这些算法的性能很差(Lever等人, 2017年)。在聚类算法中,k-means(MacQueen,1967)是最流行的划分算法之一,并且由于其实现的效率和简单性而被广泛使用(Xie等人,2019年)的报告。然而,由于存在影响聚类质量的离群值,其表现不佳(Mousavi等人,2020年)。根据Hawkins(Hawkins,1980)的说法:当然,真实世界的数据并不总是理想的,并且可能包括由于异常现象或产生异常值的不同测量机制而产生的噪声最近,离群值处理成为数据挖掘技术开发人员的热门话题(Gupta和Chandra,2020)。因此,在对k-means算法进行改进时,需要除了离群点的影响外,不同的相似性度量导致不同的聚类形式,其可能增加或减少k-means聚类精度(Gupta和Chandra,2020)。在距离度量中,欧几里德距离通常与k均值一起用于数据聚类。此外,余弦和相关性是最知名的聚类区分度量。基于这些度量对数据域(Bekhet和Ahmed,2020)。对各种相似性度量的影响的评估可以在Gupta和Chandra(2020),Gupta和Chandra(2020)和Singh etal.(2013)中找到,而选择或开发合适的距离度量仍然是数据聚类社区研究人员中的一个本文提出了一种改进的k-means算法来改进数据聚类,而在线聚类和大数据聚类都超出了这项工作的范围。改进算法的目的是为了降低质心测量过程中离群点的影响,提高聚类精度。在该算法中,一个著名的Tukey的规则是适应和应用,而不是距离度量,以确定无离群数据的边界。然后,基于无离群数据的上边界和下边界的平均值来测量每个聚类的质心。平均测量独立地应用于数据点的每个属性。这消除了离群值的影响,而无需移除整个数据点。另一方面,本文提出了一种新的距离度量。最初,计算com-coverage属性中每两个对应值之间的比率。然后,使用反正切计算每个比率的角度。对于比较向量中的每个属性,测量所产生的角度之间的差异。最后,计算角度差异的均方根误差(RMSE)作为相似性度量。与文献算法相比,该方法在9个标准多元数据集上的总体聚类准确率提高了80.57%。在本文中,从离群点去除和距离度量的角度提高k-means聚类精度的相关工作在第2中给出。对传统K-平均值、各种距离度量和用于离群值去除的Tukey在第4节中介绍了所提出的方法,包括新的距离度量,适应Tukey第5节解释了结果和讨论,第6节讨论了挑战和局限性。最后,在第7中总结了结论和未来的工作。2. 相关工作许多研究都是基于各种离群点去除技术来提高k-means算法的聚类精度。在基于离群值检测的距离度量方面,几项研究已经基于数据点与其最近质心之间的距离识别出离群值(Sarvani等人,2019;Barai(Deb)和Dey,2017)。在这些技术中,具有到最近质心的较大距离的数据点被识别为离群值。此外,具有低密度和距其质心的大距离的数据点被认为是离群值,如He et al. (2020年)。 在不同的方法中,局部搜索技术(Gupta等人,2017; Friggstad等人,2019)用于辅助k均值进行离群值检测。局部搜索旨在从聚类内的数据中移除一些数据点,以最小化目标函数。如果移除的数据点已使目标函数最小化,则这些数据点被视为离群值并分组到单独的聚类中。在预处理技术方面,Im等人(2020)使用k-means++作为额外的过滤步骤,以在应用常规k-means之前将z数据点作为离群值去除。尽管这些技术的聚类结果令人鼓舞,但聚类过程仅在无离群值的剩余数据上执行。离群值数据被完全移除,并且不被分类到最初收集的任何已知聚类中。在其他研究中,离群值检测被用作优势到例如在图像处理中将对象与其背景分离(Tu等人,2020年,2019年)。然而,很少有研究涉及减轻平均测量的离群值影响,并将所有数据点分类到最初收集的已知聚类中。 在Olukanmi et al.(2017)中,提出了一种k-means#来消除聚类质心对离群值的影响。检测到的异常值仅从平均值测量中完全排除,但它们稍后参与聚类过程。因此,从质心测量中减轻了离群值的影响,并提高了聚类精度。虽然该方法优于传统的k-means方法,但具有N个属性的数据点完全从质心测量中消除。在这种情况下,算法无法独立地识别每个属性中的离群值。这是因为距离度量的单个值表示整个向量,而不是单个属性被删除。因此,在每个数据点中存在至少一个离群值的情况下,可能会出现空聚类。从距离度量的角度来看,聚类精度的提高Safont等人提出了ICA混合模型(PDI)的概率距离。(2018年)。距离度量数据的概率密度之间的不一致性,特别是对于每个ICAMM模型的参数。特别是在调整阈值后,基于PDI距离改进了ICAMM的源分离效果虽然,良好的性能检测的缺陷和变化的脑电图(EEG)。作者建议采用并行计算来减少处理时间。在Meng et al. (2018),在比较的向量之间测量几阶导数信息,并将其添加到距离度量。衍生工具的附加信息是有用的NHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报6367X¼ð Þ ¼2 ≤ ≤ ≤···≤ð Þ ¼ ðÞP< X X.X-L。第2项=dA;B-PNa2PNðJNdR A;BA1-i1i2用于捕获所比较的函数数据之间的差异。然而,由于计算函数数据的几个导数阶次在通常用于提高聚类精度的混合距离度量方面,Gu等人(2017)开发了一种名为“方向感知”的新距离度量,该距离结合了传统的欧氏距离来处理空间相似性,而余弦度量计算形状相似性。与原始度量相比,两种度量的混合提高了聚类纯度。此外,在Immink andWeber(2015)中引入了欧几里得距离和皮尔逊距离的加权和,使用了欧几里得系数和皮尔逊系数的权重一旦噪声显著增加,混合距离就提高了比较信号之间的相似性。如本节所讨论的,只要在测量聚类的质心之前去除离群值,就可以提高聚类的准确性。在这项研究中,一个众所周知的方法,如Tukey的规则,离群值删除被改编为使用,而不是距离度量。此外,几个距离度量的混合方法由于其用于提高聚类精度的效率而被遵循,如前所述。该方法综合了欧氏距离、余弦距离、相关距离等常用距离度量的优点,形成一种新的相似性度量,可以从不同的角度对数据进行处理。混合距离方法在消除了聚类中心离群点的影响后,对提高聚类精度的能力更强。所使用的技术,如k-均值,Tukey的规则和相似性度量的理论背景3. 理论背景3.1. K-means聚类算法k-means方法基于球形聚类,其中数据点围绕聚类的质心收敛。k-均值将一组数据点X1/4fx1;x2;x3;· · ·;xNg分成k个已知数量的聚类。随机地,k-均值选择k个质心集合C^fc1;c2;c3;· · ·;ckg,其中ek≤N。此后,基于最小欧几里德距离将每个数据点xi分配给最近的聚类Cj计算每个聚类内的数据点1j的平均值,以在每次迭代中更新质心。重复该过程,直到质心值没有变化或达到最大迭代次数。每个聚类内的数据点的相似性通过最小化它们之间的距离而很高,如(1)中给出的。数据点X¼fx1;x2;x3;· · ·;xNg包括一些离群值,其中XR和x1X2x3xn.开始时,第一四分位数Q1和第三四分位数Q3如(3)中所述计算,(4)分别。此后,使用(5)测量四分位数间距IQR。最后,分别在(6)和(7)中给出了下界lb和上界ub的突变。因此,任何低于lb或大于ub的数据点xi都被认为是离群值。Q1xiji回合N 1× 0: 253Q3回合N1 × 0: 754IQR¼Q3-Q 1-5lb¼Q1-r×IQR1.6mmub¼Q1r×IQR7其中i是数据点索引,而N表示数据点的总数。r是用于调整内点的边界的预定义常数。Tukey提出了一个预定义的常数r1: 5。然而,没有统计学基础来推理所提出的值(Seo等人,2006年)。因此,该值可以根据其应用进行调整。3.3.相似性度量欧 几 里 得 距 离 是 各 种 机 器 学 习 算 法 中 最 常 见 的 相 似 性 度 量(Mesquita等人,2017年)。为了测量两个向量之间的距离,令A<$fa1;a2;a3;· · ·;aNg和B<$fb1;b2;b3;· · ·;bNg是具有N个数值属性的两个数据A和B之间的欧几里得距离dE可以如(8)中所给出的那样测量。NdEA;B jai-bij81/1欧几里得距离满足几个性质,例如非负的,其中d E≥0,一旦A和B完全相似,距离d E1/4 0,并且距离是对称函数,其中d E A;B d E B;A(Han等人,2012年)。尽管分类和数值数据集中的聚类性能,但对于混合数据集,欧几里得距离的性能相对较差(Hu et al., 2016年)。另一方面,余弦度量基于如(9)中定义的内积计算两个向量之间的相似性(Lo et al.,2018年)。余弦距离dC A;B1表示两个向量没有相似性。一旦余弦距离趋于0,输入向量之间的相似性就越高arg min8k..9CNC1i¼1ð1Þai bi9**J. ;11 2 3 4567 8 910 11 12 13 1415 16 17 19 191X2Cjl¼1XX2mmX2Cj其中argmin是k均值的目标函数符号j·j表示欧氏距离,而N表示第j聚类内的数据点的数量。3.2. TukeyTukey通常,余弦距离用于测量文本-文档分类中的相似性(Manning等人,2008年)。余弦距离在分类和数值数据集独立和最差在混合数据集(Hu例如, 2016年)。在另一种方法中,Pearson系数用于计算直线回归线上A和B数据点之间的相关度(Yin和Wang,2020)。相似性度量通过从1中减去皮尔逊相关系数来定义,如(10)中所述。PN1a-Ab-B多元数据中的线性检测(Huyhues-Beaufond等人,ðsPN2sPN。ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiΣffiffi2ffiffi1/1 B-Bai- A1/1Bð10Þ2020年)。Tukey将离群值定义为位于内部围栏边界之外的数据。为了检测异常值,让一组NHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报6368b我J- -Y-ZY-ZJ- -¼ð Þ ¼ ðÞjai-bij其中A和B分别是A和B向量的均值。数据缩放和本地化对Pearson相关系数都是不变的因此,它不是距离度量,因为该方法旨在定义数据形状的变化,4. 该方法4.1. 距离测量在这项研究中,提出了一种新的相似性度量,以取代传统的k-均值中的欧氏距离拟议反之亦然。结果,使用a i b i为比较矢量A和B生成N个角度最后,如(17)中所述计算角度差的均方根误差(RMSE)RMSE在相似向量的情况下趋向于0,而在不相似向量的情况下趋向于大值。在这种技术中,RMSE是距离测量的最后结果。RMSE不是直接从原始数据中测量的,而是根据比例系数的角度差计算的ai¼tan-1ai;其中bib<$tan-1bi;其中ai我相似性度量旨在利用各种度量的优点由于不同的距离度量,诸如欧几里得距离、余弦度量和相关系数的度量导致不同的聚类精度的方式(Aggarwal等人, 2019年)的报告。设A<$fa1;a2;a3;· · ·;aNg和B<$fb1;b2;b3;· · ·;bNg为2a我vut1XN21/1具有N个数值属性的向量来衡量在A和B之间,首先应用归一化处理以将它们转换为1和90之间的正值,如下所示:Y¼max=A;B=11mmZ¼minA;B≤12mmA¼A-Z× λrmax-rminλrminλ13λB¼B-Z×R最大值-r最小值×R最小 值×14其中Y和Z分别表示A和B中的最大值和最小值。Rmax和Rmin表示目标缩放的最大值和最小值,分别为90和1规范化过程旨在保证ai并且bi不等于零,以避免在(15)和(16)。在归一化之后,首先计算归一化向量A和B之间的比例,以指示一个值包含在另一个值中的次数。可以通过测量互补向量A和B中的每两个对应值之间的比率来计算比例,例如ai=bi和bi=ai。在完全相似的向量的情况下,两个比率系数等于1,而在相异性中产生不同的值。在此之后,角度ai 两个比率的b1和b2被计算为在(15)和(16)中给出。对于相似的矢量,两个角度都趋向于45°,而不同值的角度趋向于0°和90°之间,如图1所示。因此,ai和bi之间的距离减小,而它们之间的差异很小提出的距离dP满足几个数学性质-联系,如非负的,其中d P≥ 0。在A和B完全相似的情况下,距离dP¼0。此外,如果d PA;B d PB;A,则所提出的距离是一个对称函数.此外,在计算建议的距离时考虑了几个优点。在第一阶段通过计算比较向量之间的比例来使用相关距离的优点其次,利用与余弦度量类似的反正切函数,利用比较向量第三,角度差aib我 实现类似于Euclidean距离。最后,RMSE被用来预测,如果由于整个点位于回归线上而在比较的向量之间存在强相关性,则dP的值趋于0因此,计算所提出的距离度量以与第4.3中讨论的修改的k均值一起使用。4.2. Tukey's rule的用法第3.2节中讨论的标准Tukey规则旨在使用Tukey常数r去除离群值1: 5,两者均较低上界相等。同时,未考虑其余数据的平均值分布,包括偏度。偏斜数据意味着数据沿平均值的左侧和右侧不均匀分布。因此,当硬偏度存在时,应用Tukey规则后从剩余数据计算平均值没有意义。偏斜数据影响k均值的质心测量。因此,本文提出了对标准Tukey规则的适应,Fig. 1.角度差ja-bj与所提出的距离度量dP之间的关系。dP=A;B= BNð17ÞNHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报63692>:2019年3月20日×IQRJ通用汽车公司×2¼¼¼:.ΣðÞðÞð Þ ðÞ1/4 f···gðÞ ¼ ð þÞ;2k-means这提供了不影响质心测量的无异常值数据通常,可以检测分布式数据的偏斜度4. 质心 更新: 新质心Cj 每个属性m集群内j计算如下:通过计算平均值右侧的数据点数量和左侧。因此,如果数据cj m¼lbmubmð20Þ点 沿 平 均 值 的 左 侧 和 右 侧 不 均 衡 。否 则 , 数 据 点 呈 正 态 分 布 。Tukeyr1/40: 85和r2/40: 65)。在偏斜数据的情况下,r1允许移除较少的数据点,这是由于其较大的值增加了在偏斜位置处要涉及的数据的边界相反,r2允许从偏度位置移除边界处的大量数据点。r2的小值减少了要涉及的数据边界远离偏度位置。另一方面,在数据沿着平均值的两侧均匀分布的情况下,将去除的数据量设置为r1和r2自适应过程的公式在(18)和(19)中给出。其中lb和ub是由下式获得的下边界和上边界:(18)和(19)。5. 终止条件:如果C中的所有数据质心未更改或达到最大迭代次数,则停止。否则,重复步骤2至5。递归地应用适应的Tukey规则有两个目标。第一种方法是通过挖掘每个聚类中的数据所关注的底层模式来获得无离群数据因此,递归过程有助于去除其他离群值可能覆盖的隐藏离群值第二种方法是独立地从每个属性中删除离群值删除整个观察,因为通常使用的俱乐部-磅/升8>< Q1-r1×IQRjGMLM Q1-r2×IQRjGM>LM<ð18Þ基于离群点剔除技术的聚类算法独立处理每个属性有助于避免>:Q1-r1r2×IQRJ通用汽车公司一旦出现至少一个离群值,在每一次观察中发现。单位:8>LMð19Þ算法1:改进的k-means聚类算法。r1r22其中GM和LM分别是大于和小于平均值的数据点的数量修正的Tukey规则的目的是自适应地消除三种数据分布情况下的异常值,无论数据是分布在左,右或平均值相等。这对于决定应该在哪里应用硬的和较少的去除而不是像标准Tukey规则中提出的那样从两侧同等地消除异常值是有用的。调整Tukey规则的目的是提供健壮的无离群值的边界。这些边界,例如lb和ub,可以仅用于计算修改的k均值的聚类的质心。离群值移除仅在质心测量期间应用。 因此,将不会删除任何输入数据,并且将对所有输入数据进行聚类与最初收集的已知组进行比较。在下一节中介绍了关于适应的Tukey规则和k均值之间的混合的详细讨论4.3. 改进的k-means本文对k-means算法进行了改进,以减小计算聚类中心时离群点的设X是一个数值N M数据集,其中N表示数据点的数量,M是属性的数量。算法1示出了修改的k-means的伪代码,并且整个步骤被讨论如下:1. 修正的k-均值随机选择k个数据点集作为数据质心,其中k≤N且C2X。2. 分配:每个数据点xi基于如等式中给出的所提出的距离度量被分配到最近的聚类cj(十七)、在该步骤中,初始构建k个数据聚类3. 离群输入:X是具有N个数据点的输入数据集,M美德.先知-愿k是预定义的簇的数目。MaxIter是迭代的最大次数。输出:S是属于X数据集的k个聚类的集合。1. 开始2. //下载3. 选择初始质心C c1;c2;c3;;ck的随机k个其中,X。4. 重复,直到满足MaxIter或C未更改//终止标准5. S6. //赋值7.对于i1:N8.对于j1k9.djdPx i;c j,计算x i和c j之间的距离,如式(17)所示。10.如果xi具有最小值,则将xi分配给它的聚类集Sjdj与cj。11. //删除异常值12.对于j¼1:k13.对于m¼1:M14.重复,直到在Sj:中未检测到离群值;m//15.如(18)中给出的计算Sj:;m的lb和ub,以及(19)分别。16.对于i¼1:thSj:;m17.如果Sj i;mlb或Sj i;m>ub//检查是否为离群值<18.删除离群数据点。19.//质心更新20.cj m lbub=2,更新每个属性的质心,如(20)中给出的。21. 端dently。调整后的Tukey属性NHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报6370X1½j\j阿吉岛在修改的k-均值中,质心是从在适应的Tukey规则的最后迭代处的无离群数据的lb和ub的平均值该步骤取代了传统k均值中的传统质心测量该步骤另一方面,改进的k-均值算法允许基于所提出的距离度量对整个数据点进行聚类。传统的基于离群点去除方法的聚类算法中没有一个数据点会像通常使用的那样从输入数据中去除。拟议方法在下一节讨论的各种常用数据集上得到验证。5. 结果和讨论5.1. 数据集所提出的方法在从加州大学欧文分校(UCI)的机器学习库获得的九个多变量数据集上进行了验证(Dua等人,2020年)。所使用的数据集具有不同数量的属性,范围从4到13。此外,给定数据集的聚类数从2到6不等。所用数据集的内容描述和总结见表1。5.2. 对拟议方法5.2.1. 改进的k-means聚类精度评价如前所述,在UCI数据集上评估修改后的k-means。给定的数据集通过将其值从1到90范围内进行归一化,以避免除以(15)和(16)中给定等式的零。 将所得结果与常用的文献算法,如k-均值(KMN),层次聚类算法(HCA)和最远优先算法(FFA)进行了比较。此外,该算法与著名的进化算法,如基于聚类的粒子群优化算法(CPSO),基于聚类的遗传算法(CGA)和静态基于聚类的MVO(SCMVO)之间的比较已被引入。此外,修改后的k-means的结果进行了比较,k-means#(KMN#)和DBSCAN,这是强大的算法离群在实验装置中,如等式1和等式2中所给出的,调整的Tukey规则的常(18)和(19),其中r1>r2。这些常数是基于最佳聚类准确性根据经验选择的,并在此实验期间全局用于所有数据集。在(17)中给出了所提出的方法的所利用的距离测量。修改后的k均值的最大迭代次数为50次,而准确度结果是从100次运行的平均值中每次运行中的聚类准确度基于聚类纯度(百分比)正确聚类的数据点的数量,如(21)所示。K纯度LC21N1其中N表示数据点的总数。Li表示每个聚类i内的真实数据点的数量。Ci表示使用聚类算法正确聚类的数据点所提出的方法克服了大多数文献算法,如表2所示。在所有数据集上,特别是在Glass、Balance、Vertebral、Ecoli和Blood数据集上,改进的k-means显著优于传统的k-means、k-means#和进化算法,如CPSO、CGA和SCMVO。然而,HCA在Balance数据集中以2.55%的准确度差异克服了所提出的算法。与此同时,HCA和FFA在血液数据集中的表现优于修改后的k-means,准确率差异为0.47%,这是一个有竞争力的表现。此外,DBSCAN取得了更好的性能,在血液数据集相比,所提出的方法与2%的准确性差异。对于具有大量类的最具挑战性的数据库,例如分别具有6个和5个类的玻璃和大肠杆菌,修改后的k-means实现了显着的性能。虽然初始质心是随机选择的,但100次运行的标准偏差率较低,反映了所提出技术的稳定性和稳健性。一般来说,修改后的k-means的整体性能在总共7个数据集上表现出最佳的准确性结果,在其他数据集中表现出竞争性的准确性结果。2数据集结果表明,改进的k-means算法完全克服了5种常用算法的不足,并在两个数据集上与其他3种算法5.2.2. 离群点剔除对聚类精度的影响在www.example.com章节中讨论了标准和修改后的Tukey规则对修改后的k均值的影响5.2.2.1此外,通过两种离群值技术的聚类过程去除离群值的机制在第5.2.2.2节中讨论。在实验装置中,调整后的Tukey在标准的Tukey规则中5.2.2.1. 通过改进的k-means迭代的聚类精度。图2示出了基于适应的Tukey规则的修改的k均值的迭代增量期间的准确度变化。每次迭代都对提高大多数数据集的聚类准确性做出了有价值的贡献,如图所示。 二、然而,可以在血液数据集上看到迭代增量期间的准确性损失,这推断出与HCA和FFA相比,修改后的这种行为表1从UCI存储库获得的所用数据集的描述数据集属性数班级数数据点每个类别数据类型虹膜43150五十,五十,五十房玻璃9621470、17、9、76、29、13房平衡4362549、288、288房癌82699四五八,二四一房酒133178五十九、七十一、四十八房椎62310二百零七,一百房Ecoli75327143,77,35,20,52房血液42748570,178房种子73210七十,七十,七十房NHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报6371表2与其他文献聚类算法相比,改进的k-means的准确性结果。 所有表中的粗体值表示最佳性能。数据集KMNHCA(HochbaumFFACPSOCGA(Maulik和CSMVODBSACNKMN编号提出(MacQueen,和什莫伊斯,(Sharmila,(JarbouiBandyopadhyay,(舒克里(Ester等人,(奥卢坎米(1967年)一九八五年)2013年度)例如,(2007年)(2000年)例如, 2018年)一九九六年)例如,(2017年)平均值±标准差平均值±标准差平均值±标准差平均值±标准差平均值±标准差平均值±标准差平均值±标准差平均值±标准差平均值±标准差虹膜0.57 24小时0.89 0.00-0.86 0.00-0.96 0.00-0.96 0.00-0.96 0.00-0.68 0.00-0.85 0.10 ±0.96 0.00-玻璃0.36 0.08 ±0.46 0.00-0.48 0.00-0.45 0.00-0.36 0.00-0.52 0.08 ±0.46 0.00-0.49± 0.040.56± 0.03个平衡0.470.170.63 0.00-0.65 0.00-0.37 0.18 ±0.41 0.18 ±0.490.170.47 0.00-0.55 0.07 ±0.61 0.07 ±癌0.95 0.00-0.66 0.00-0.84 0.00-0.96 0.00-0.96 0.00-0.96 0.00-0.93 0.00-0.96± 0.03个0.97 0.00-酒0.90 0.14 ±0.40 0.00-0.70 0.00-0.91 0.12 ±0.95± 0.01个0.96 0.00-0.61 0.00-0.71± 0.040.98 0.00-椎0.68 0.00-0.67 0.00-0.68 0.00-0.68 0.02 ±0.70 0.00-0.71 0.00-0.67 0.00-0.73± 0.040.78± 0.01个Ecoli0.66± 0.110.65 0.00-0.60 0.00-0.60± 0.110.62± 0.130.57± 0.130.43 0.00-0.66 0.09 ±0.71 0.07 ±血液0.53 0.06 ±0.76 0.00-0.76 0.00-0.48 0.00-0.48 0.00-0.48± 0.01个0.78 0.00-0.68± 0.03个0.76 0.02 ±种子0.79 0.19 ±0.90 0.00-0.67 0.00-0.89 0.05 ±0.90 0.00-0.90 0.00-0.68 0.00-0.90± 0.040.94 0.00-总体精度0.66± 0.110.67 0.00-0.69 0.00-0.70 0.05 ±0.70± 0.040.73± 0.040.63 0.00-0.73 0.05 ±0.81 0.02 ±所提出的算法由于数据集本身的性质而被包括的数据的多样性可以被聚类到18个不同的类(Lord等人,2017年)。因此,包含的数据点的高度多样性影响了修改的k均值的准确性。标准Tukey调整后的Tukey改进后的Tukey规则提高了聚类精度,同时减少了质心收敛所需的迭代次数。由于适应的Tukey规则基于如(18)和(19)中给出的去除离群值的添加规则自适应地消除离群值,所以获得了这种改进这使得适应Tukey的规则快速到达无离群值数据的边界,其中应该测量数据质心。另一方面,与文献聚类算法相比,基于标准Tukey规则的修改后的k均值在5.2.2.2. 离群值去除机制。在离群值去除机制方面,图。图4示出了在异常值去除过程期间在每次迭代处的质心测量的示例。图图4(a)示出了经调整的Tukey规则的箱形图参数的描述。在该示例中,在离群值去除过程期间,在每个单个聚类中监视Iris数据集的Sepal长度属性的数据在所有三个聚类中,最后一次迭代的剩余数据完全没有离群值,如图所示。 4(b)、(c)和(d)。可以注意到,在第一次迭代时,检测到一些离群值,并从每个聚类中的萼片长度属性中移除此外,有一些覆盖的离群值被检测到后,在Iris Setosa和Iris Virginica集群的适应Tukey的规则递归地应用因此,本文提出的野值递归剔除方法对剔除这类野值是有效的此外,所提出的技术的质心测量是不同于传统的k均值质心在最后一次迭代去除离群值。建议的质心往往接近无离群值数据的平均值。建议的质心与数据聚焦的 蓝 色 框 的 中 间 对 齐 。 在 偏 斜 数 据 方 面 , 可 以 注 意 到 在 IrisVirginica集群中显示了硬偏斜 在这个clus- ter中,数据中值在下边界处移动,如图所示。 4(d). 因此,适应的Tukey因此,在最后一次迭代中对硬偏度进行miti- gated之后测量质心。因此,适应的Tukey这提供图二. 通过修改的k-means的迭代来改进聚类精度。NHM Shrifan,M.F.Akbar和N.A.M.ISA沙特国王大学学报6372¼¼¼图三. 通过修改的基于k均值的标准Tukey规则的迭代来进化聚类精度表3从迭代次数和聚类精度两个方面比较了标准Tukey规则和改进后的Tukey规则的性能。所有表中的粗体值表示最佳性能。数据集迭代次数聚类精度标准适配差异标准适配差异虹膜223190.85810.96050.1024玻璃165110.45580.55930.1035平衡11740.57500.60450.0295癌6510.96460.96490.0003酒14590.97150.97480.0033椎10910.73760.78130.0437Ecoli11830.65180.71130.0595血液8800.61420.75530.1411种子2210120.90750.93920.0317平均13.33336.66676.66670.74850.80570.0572不影响质心测量的无离群数据。与适应的Tukey规则相比Tukey常数r 1:5的大值因此,未检测到覆盖的离群值,因为它们被安静地放置在低于ub且大于lb的位置。 因此,在这种情况下计算的质心类似于由传统的k均值计算的质心,如图2所示。 五、5.2.3. 稀缺数据聚类Glass数据集提供了稀缺数据聚类的一个很好的例子。在这个数据集中,给出了六个类,每个类中的数据点的数量分别为70,17,9,76,29和13。很明显,第二、第三和第四类属于稀缺数据聚类,因为与其他类相比,这些类中的数据点数量较少。所提出的方法正确分配的数据点的第二,第三和第四类分别为35.3%,88.9%和61.5%。 关注仅包括9个数据点的第三个聚类,其中8个被正确地分配给该聚类。在这个聚类中,只有两个数据点被错误地包含在其他聚类中。考虑到Glass数据集的聚类复杂性,如表2所示,所提出的方法成功地构建了一个独立的质心,该质心吸引了第二次聚类中的大多数数据点。具有少量数据点的聚类是从其他聚类中获得的。改进的k-means算法在数据聚类方面的性能得到了提高。5.2.4. 集群运行时在表4中,在常规k-均值(KMN)、基于k-均值的标准Tukey规则(KMN-TTR)和基于k-均值的适应Tukey规则(KMN-ATR)之间进行运行时比较。传统的k-means方法在处理时间上明显优于基于标准和适应Tukey规则的k-means方法。两种算法都增加了离群点去除步骤,增加了传统算法的处理时间。与标准Tukey规则相比,基于自适应Tukey规则的k-means在处理时间上是最差的。在适应的Tukey规则中同时,由于Tukey常数r1: 5的较大值,不会检测到更多的离群值,因此最小化了处理时间并很快达到了停止标准。
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 基于嵌入式ARMLinux的播放器的设计与实现 word格式.doc
- 经典:大学答辩通过_基于ARM微处理器的嵌入式指纹识别系统设计.pdf
- 嵌入式系统课程设计.doc
- 基于飞思卡尔控制器的智能寻迹车设计ARM基础课程课程设计.doc
- 下载基于ARM7的压电陶瓷换能器导纳圆测量仪的研制PDF格式可编辑.pdf
- 课程设计基于ARM的嵌入式家居监控系统的研究与设计.doc
- 论文基于嵌入式ARM的图像采集处理系统设计.doc
- 嵌入式基于ARM9的中断驱动程序设计—课程设计.doc
- 在Linux系统下基于ARM嵌入式的俄罗斯方块.doc
- STK-MirrorStore Product Release Notes(96130)-44
- STK-MirrorStore Storage Connectivity Guide for StorageTek Disk A
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-本科毕业设计.doc
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-.doc
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-本科生毕业论文.doc
- 麻阳风貌展示网站的设计与实现毕业论文.pdf
- 高速走丝气中电火花线切割精加工编程设计.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)