一种改进的模糊c——基于跟踪集和PSO聚类算法

文摘

组织各种各样的数据集自动获取准确的分类,提出了一种模糊的修改则算法(SP-FCM)基于粒子群优化(PSO)和跟踪执行功能聚类集。SP-FCM介绍算法的全局搜索特性来处理传统的模糊聚类的过早收敛的问题,利用模糊平衡阴影的属性集来处理重叠的集群中,在课堂上和模型不确定性边界。这种新方法使用Xie-Beni指数作为集群有效性和自动发现最优集群与集群分区的数量在一个特定范围提供紧凑,布置得井然有序的集群。实验表明,该方法极大地提高了聚类的效果。

1。介绍

聚类的对象分配一个组别的过程为子集,称为集群,这样每个集群中的对象相似比对象从不同集群基于它们的属性的值(1]。数据挖掘中的聚类技术已经被广泛的研究(2),模式识别(3),和机器学习4]。

聚类算法通常可以分为两个主要的类,即监督聚类和非监督聚类分类器的参数优化。许多无监督聚类算法被开发出来。一个这样的算法则,分配对象集群通过最小化之间的欧几里得距离的平方和的对象在每个集群的集群中心。的主要缺点算法则是结果是敏感的选择初始聚类质心和可能收敛于局部最适条件(5]。

为处理这些随机分布的数据集,引入了软计算在集群6),利用不精确和不确定性的容忍为了实现温顺和鲁棒性。模糊集和粗糙集已经被纳入——框架开发的模糊——(FCM) [7)和粗糙——(RCM) [8)算法。

模糊算法可以将数据对象部分分配给多个集群和处理重叠分区。模糊集群成员的程度取决于数据的亲密对象集群中心。最受欢迎的模糊聚类算法是FCM Bezdek[引入的9),现在它被广泛使用。FCM是一种有效的算法,但在中心点随机选择使迭代过程分为鞍点容易或局部最优解。此外,如果数据集包含严重的噪声点或高维数据集,如生物信息学(10),交替优化往往无法找到全局最优。在这些情况下,找到全局最优的概率可以增加随机方法如进化或群方法。Bezdek和海瑟薇11)优化硬——(HCM)模型与遗传算法。Runkler [12]引入了蚁群优化算法,明确最小化HCM和FCM聚类模型。Al-Sultan和斯莱姆(13]提出了模拟退火算法(SA)克服这些限制,有不错的效果。

算法是一个基于人口优化工具进行开发的埃伯哈特和肯尼迪(14),这很容易实现和应用来解决各种各样的函数优化问题。Runkler和卡茨(15]引入了两个新的方法来减少这种改进的FCM聚类模型的目标函数算法:PSO -和PSO -。为了克服FCM的缺点,PSO-based模糊聚类算法进行了讨论(16];这个算法使用算法的全局搜索能力来克服FCM的缺点。寻找更合适的集群中心,广义优化FCM的PSO算法(17提出了]。

跟踪集被认为是作为一个概念和算法粗糙集和模糊集之间的桥梁,从而将通用的优点,并被成功地用于无监督学习。跟踪集介绍区间来表示这些聚类点的归属感,和不确定性模式躺在阴影区域是有效处理会员。因此,为了消除歧义和捕获一个分布的本质,最近跟踪集的概念引入了(18),这也可以提高效率在迭代过程中新的原型通过消除一些“坏点”,有坏影响集群结构(19,20.]。与FCM相比,跟踪的能力——增强在处理异常时(21]。

虽然很多基于FCM聚类算法,算法,提出了或跟踪集,其中大部分是需要输入概况集群数量。获得理想的集群分区在给定数据,一般手动设置,这是一个非常主观的,有些武断的过程。提出了很多方法来选择适当的。Bezdek et al。22建议的经验法则必须确定的上界基于知识或应用程序的数据。另一种方法是使用一个集群效度指数作为衡量标准数据分区,如Davies-Bouldin (DB) (23),Xie-Beni (XB) [24],邓恩(25)指数。这些指标通常遵循的原则,同一集群中的对象之间的距离应尽可能小,对象在不同的集群之间的距离应尽可能大。他们也被用来获得最优数量的集群根据他们的最大值或最小值。

因此,我们希望找到最好的在某些范围内,通过考虑密实度和获得集群分区intercluster分离,并减少对初始值的敏感性。在这里,我们提出一个修改算法命名为SP-FCM集算法的优点和交叉阴影集之间稳定的迭代。它可以自动估计最优簇数和更快的比我们之前的初始化方法。

论文的结构如下。部分2概述了所有必要的先决条件。节3,提出了一种新的聚类方法称为SP-FCM自动寻找最优集群数量。部分4包括涉及UCI数据集的实验结果,酵母基因表达数据集和真实数据集。5,主要结论是覆盖。

2。相关的聚类算法

在本节中,我们简要介绍一些基本概念的FCM算法,跟踪集和XB有效性指数和审查PSO-based聚类方法。

2.1。FCM

我们定义随着宇宙的聚类数据集,的原型集群,作为一个模糊划分矩阵,的会员在一个集群原型;,,在那里P数据维数,,。FCM算法推导出通过最小化目标函数(22] 在哪里在每个模糊加权指数成员和吗是欧式距离数据向量聚类中心。和 这将生成以下更新方程:

计算所有对象的会员后,集群计算的新原型。当原型稳定过程停止。从先前的迭代中,原型是靠近那些当前迭代中生成的,通常少于一个错误阈值。

2.2。算法

PSO最初引入社会和认知行为的鸟类聚集和鱼的教育。潜在的解决方案被称为粒子穿越问题空间遵循当前最好的粒子。每个粒子跟踪的问题空间的坐标与迄今为止取得的最佳解决方案。解决方案是评估的健身价值,也是存储。这个值被称为最好的。另一个最佳值跟踪的算法是最好的价值,获得了迄今为止任何粒子群。最好的价值是全球最好的最好的。寻找更好的位置遵循规则 在哪里和粒子位置和速度矢量,分别惯性权重,和正的常数,称为加速度系数控制的影响最好和在搜索过程中,和和随机值的范围。每个粒子的位置的健身价值是由一个适应度函数,算法通常是执行和重复应用(5),直到指定的迭代次数已超过或接近速度更新一分之零的迭代次数。

2.3。PSO-Based FCM

在这个算法26),每个粒子代表一个聚类中心向量,构造成 在哪里代表了th粒子,,是粒子数,。是集群中心的粒子。因此,一群代表一个数量的候选人集群中心数据向量。每个数据向量属于集群根据其隶属函数,从而模糊成员被分配给每个数据向量。每个集群有一个集群中心每个迭代和提供了一个解决方案,给出了向量的集群中心。这个方法决定了位置矢量对于每个粒子,更新它,然后更改集群中心的位置。和广义解的适应度函数来评价说

小的是,更好的聚类效果和较高的健身功能。

2.4。跟踪设置

传统不确定性模型像模糊集倾向于通过会员获取模糊值,并将会员的精确数值与模糊的概念。通过引入切(19),一个模糊集可以转化成一套经典。阴影设置给定模糊集合的每个元素映射到0,1,单位时间间隔,即排除在外,包括分别和不确定。

构建一套跟踪,Mitra et al。21)提出了一个基于模糊平衡优化。作为提升成员值的一些地区1,同时减少一些地区的成员值为0,这些地区的不确定性可以消除。保持平衡的不确定性区域,它需要补偿这些变化不确定的施工区域,即跟踪集吸收前消除部分成员在低和高范围。引起的阴影集模糊隶属函数图1。

在这里表示对象;是连续隶属函数的对象属于一个集群。符号显示会员的减少,象征会员,描绘了海拔和象征显示的形成阴影。为了平衡总不确定性,保持平衡转化为以下依赖:

和积分形式给出

阈值的降低和提升和()。的最优值应该被翻译成以下目标函数的最小化:

与离散模糊集隶属函数,修改平衡方程

为了找到最好的,它应该满足如下优化问题: 在哪里的会员在一个集群原型;和表示的最高及最低的成员值th集群;和的门槛集群。可行的阈值的范围是(19]。

这种方法考虑所有集群成员价值观对一个固定时更新此集群的原型。跟踪集的主要优点包括选择不同的阈值优化机制,减少纯数值计算的负担。

2.5。XB聚类有效性指标

上述聚类算法需要prespecification集群的数量。分区结果依赖于所选择的。存在有效性指数来评价聚类的美好根据给定数量的集群;因此,这些有效性指数可以用来获得的最优值(27]。

XB指数提出了一种基于fuzzy-validity准则效度函数确定整体紧凑和单独的模糊分区。这个函数取决于数据集,几何距离测量,和聚类质心之间的距离和模糊分区,不管任何模糊算法。评估的数据分区的美好,集群密实度和intercluster分离应该考虑。的FCM算法可以证明,Xie-Beni指数 在哪里是集群质心之间的最小距离。单独的集群,越多越大和小。

3所示。跟踪则PSO-Fuzzy集群:SP-FCM

FCM努力找到紧凑的集群在哪里是指定的参数之一。但选择和调整的过程手动获取理想的集群分区在给定的数据集是非常主观的,有些武断。寻求最优的集群结构,总是允许高估了(28),这样一些集群之间的距离不够大或一些对象的成员值不同的集群是相邻的,模棱两可的在一个给定的数据集,在这种情况下,通过长时间的迭代修改原型是没有意义的。

集群验证的主体是集群的评价结果来找到最适合的分区数据集。基于上述算法,我们希望找到集群分区包含紧凑,布置得井然有序的集群。在我们的算法也高估和集群竞争数据成员。我们可以设置作为集群数量的合理的范围内基于数据的知识。这提供了一种更加透明和驯良的集群数量减少的过程。考虑到模糊划分矩阵,每一列由成员值的特征向量与单个集群中心。因此,最优阈值()每一列应该发现努力创建一个分区(12)。的数据量的分配成员值等于1的基数确定为相应的集群。根据的基数th列

这里的阈值不是主观定义的但它是建立在不确定性和可调整的平衡自动聚类过程。这个属性的阴影集可以用来降低集群数量。为了控制收敛速度,决定删除集群可以基于一些阈值。不同的阈值应该设置为不同的数据集根据集群结构和数据集的大小。在这里,一个阈值和流失率()是集。SP-FCM决定删除集群是完全基于集群基数和阈值。如果太小了,减少更慢,这可能阻止过早优化集群数量之前发现。另一方面,如果太大,可能会大幅减少。在我们的方法中,集群的基数是去除视为“候选人”。我们可以删除集群的最低基数从池中指定的候选人。限制了集群的数量可以删除一次阻止了从时也大大减少设置太高了对于一个给定的数据集。这将自动估计最好的集群数量,同时利用更快的,一致的,可重复初始化技术。评估的数据分区的美好,集群密实度和intercluster分离应该考虑。因此采用XB指数。

为每一个在的范围一组集群效度指标计算,是初始集群数量将比预期的更大的集群。分区矩阵集群的最佳聚合效度指数选择最后一个集群分区。SP-FCM算法在算法概括为1。

这里,如果= 0,我们可以让它为1。这意味着集群最低的基数可能被删除。最初的集群原型可以使用原型从初始化数据点选择。终止后,和从最好的集群有效性指数选为最终集群原型和分区。

4所示。实验结果

在本节中,FCM的性能,RCM,阴影——(SCM) (21),跟踪粗糙——(SRCM) [19),和SP-FCM算法提出了四个UCI数据集,四酵母基因表达数据集和真实数据。评价融合效果,基本准则可以描述如下:不同的对象之间的距离在同一集群应该尽可能;不同的对象在不同的集群之间的距离应尽可能。这里我们使用DB指数和邓恩指数来评价聚类的效果。对于一个给定的数据集值,簇内相似度值越高,intercluster分离,数据库索引值越低。一个好的聚类过程应DB指数尽可能低的价值。相对地,邓恩的高值指数表明更好的集群,集群已经分离,而且比较紧凑。实验的细节在下面提到。

4.1。UCI数据集

完全在我们的实验中,四个UCI数据集,包括四维虹膜,13-dimensional酒,十维玻璃和34-dimensional电离层。有三个集群在Iris数据集,每一个都有50个数据模式;3集群数据集的葡萄酒,50岁,60岁,和68年的数据模式;6组数据集的玻璃,30岁,35岁,40岁,42岁,36岁和31日分别;和2集群在电离层数据集,226年和125年的数据模式。每个方法的有效性指标比较表1。SP-FCM可以识别致密组织与其他算法相比,当考虑到集群数量。它还可以看到SRCM和SP-FCM比FCM更明显的优势,RCM, SCM。SP-FCM表现略优于SRCM在大多数情况下,由于全球搜索能力使它收敛到一个最优或接近最优的解决方案。此外,跟踪设置,粗糙集合聚类方法,即SP-FCM, SRCM,比FCM RCM, SCM,表现的更好。这意味着近似区域的分区可以揭示数据结构的性质,只有下界和边界地区的每个集群都有积极贡献的过程中更新原型。

像往常一样,集群的数量是隐含的本质问题。这里,涉及跟踪设置,可以预计,能找到最优数量的集群。模糊化系数可以优化;然而,通常假设一个固定的值为2.0,与隶属函数的形式关联生成的集群。测试SP-FCM算法,规则被采用,和预期的范围集群数量可以设置为(1)虹膜,;(2)葡萄酒,;(3)玻璃,;(4)电离层,。蜂群大小设置,最大迭代算法,减少集群,集群基数阈值和员工的流失率。在每一个周期,每个集群的分布,消除他们的一部分根据他们的基数,并计算XB指数和集群的号码不同来。循环结束后,选择分区的最小值作为最终结果。图2介绍了有效性指标的过程中生成最优簇数。较小的值表明更紧凑,布置得井然有序的集群。有效性指标达到最小值3、6和2分别对应于最后集群原型和最好的分区。通过跟踪集和PSO方法,每个边界区域的影响形成的原型和集群可以妥善解决。虽然需要更多的计算时间SP-FCM运行,可以获得合理的结果处理重叠和模糊数据模式。

4.2。酵母基因表达数据集

有四个实验中使用的酵母基因表达数据集,包括GDS608 GDS2003, GDS2267, GDS2712从基因表达综合下载。类和GDS608样品的数量是26,6303;GDS2003,类和样本的数量是23和5617年GDS2267 14, 9275, GDS2712 15和9275年。表2介绍了不同方法的有效性指标后,集群数量给出了。SP-FCM SRCM获得同样的效果和执行比其他聚类算法。改善可以归因于这样一个事实:算法的全局搜索能力有利于找到更合适的集群中心而逃离当地的最适条件。

获得最优自动,我们让,,,和规则采用。蜂群大小设置,最大迭代算法的数量,减少集群,集群范围的预期数量,集群基数阈值和流失率可以设置为(1)GDS608,,,;(2)GDS2003,,,;(3)GDS2267,,,;(4)GDS2712,,,。在每一个周期,每个集群的分布,消除他们的一部分根据他们的基数,并计算XB指数和集群的号码不同来。选择分区的最小值作为循环结束后的最终结果。见图3初为GDS608,集群数量减少速度,减少集群需要26个迭代来和4的迭代来,XB指数开始增加当集群。GDS2003,减少集群需要24个迭代来和7的迭代来,XB指数开始增加当集群。GDS2267,减少集群需要23个迭代来和6次迭代来,XB指数开始增加当集群。GDS2712,减少集群需要23个迭代来和5个迭代来,XB指数开始增加当集群。模糊集的优势,算法,和跟踪集SP-FCM集成,使该算法适用于处理重叠分区,不确定性,和产生的模糊边界地区,在跟踪和优化过程集使这个方法健壮的异常值,这样近似区域的每个集群可以确定准确的和获得的原型方法所需的位置。

4.3。真实的数据

在这个实验中完全测试10个不同的包。每个包是由100帧捕获由相机从不同的角度,和每一帧提取筛选特征点用于训练识别系统。图4与他们的筛选重点展示了一些图片。这个数据集是由248150年的描述符。我们让,,,,,,SP-FCM和选择合理的范围内根据要点的类别数量的包和分布在每一个图像。八十次迭代算法的运行在每个给定的生产集群原型和分区矩阵作为跟踪的起始点集。长算法稳定需要获得更稳定的集群分区。在每个集群,最优决定减少基数和实现集群,XB指数计算。每一个分区使用这个索引和排名选为最终的输出最小的索引值,表明最好的紧凑,布置得井然有序的集群。一开始,集群数量减少以更快的速度;减少集群需要26个迭代来和20次迭代来。XB指数增加在集群数量的相对速度。图5显示了XB指数。该指数达到最小值这意味着最好的分区数据集是276集群。表3展品收敛效果的比较分析。正如所料,SP-FCM真实数据可以提供良好的结果;性能评估的有效性指标。

5。结论

本文提出一种修改模糊——基于粒子群优化算法和跟踪集进行无监督特征聚类。这种算法称为SP-FCM利用算法的全局搜索性能和模糊平衡阴影的属性集,这样它可以估计最优簇数贯穿其交替优化过程。SP-FCM作为基于随机的方法能够减轻FCM面临的问题,有一些初始化和陷入局部最小值的缺点。此外,该算法避免了主观和任意试验来估计集群数量的适当的值,并找到最优,从而增强了此功能集群数量在一个特定范围使用集群措施有效性指标。XB有效性指数的使用允许算法找到最优集群与集群分区数量提供紧凑,布置得井然有序的集群。从实验中,我们已经表明,SP-FCM算法产生好的结果,参照DB和邓恩指标,特别是对高维度和大型数据情况。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

这项研究得到了国家自然科学基金(批准号61105089,国家自然科学基金委)。

引用

1. a . k . Jain数据聚类:50年超越了k - means, "模式识别的字母没有,卷。31日。8,651 - 666年,2010页。视图:出版商的网站|谷歌学术搜索
2. H.-P。Kriegel、p·克罗格和a . Zimek”集群高维数据:调查子空间聚类、基于模式的聚类,聚类和关联,”ACM交易数据的知识发现,3卷,不。1,第一条,2009。视图:出版商的网站|谷歌学术搜索
3. p .梅林和o·卡斯蒂略,”回顾2型模糊逻辑应用于集群、分类和模式识别、”应用软计算杂志21卷,第577 - 568页,2014年。视图:出版商的网站|谷歌学术搜索
4. m . Yuwono s w·苏b·d·默尔顿和h·t·阮”数据集群使用变体的快速质心估计,“IEEE进化计算,18卷,不。3、366 - 377年,2014页。视图:出版商的网站|谷歌学术搜索
5. s . c . Satapathy g . Pradhan s Pattnaik j . v . r .没吃,和p v .国民生产总值Reddy,“基于PSO聚类的性能比较InterJRI计算机科学和网络,1卷,不。1、18 - 23,2009页。视图:谷歌学术搜索
6. g·彼得斯和r·韦伯”与软计算动态聚类”,威利跨学科评论:数据挖掘和知识发现,卷2,不。3、226 - 236年,2012页。视图:出版商的网站|谷歌学术搜索
7. d·t·安德森,j . c . Bezdek m . Popescu和j·m·凯勒”比较模糊,概率和可能主义的分区”,IEEE模糊系统,18卷,不。5,906 - 918年,2010页。视图:出版商的网站|谷歌学术搜索
8. p和s .保罗中,“强劲rough-fuzzy c均值算法:设计和应用程序编码和非编码RNA表达数据聚类,“Fundamenta Informaticae,卷124,不。1 - 2、153 - 174年,2013页。视图:出版商的网站|谷歌学术搜索|MathSciNet
9. j . Bezdek模糊数学在模式分类[博士学位。论文)美国康奈尔大学,纽约,纽约,1974年。
10. 诉Olman f,毛、h·吴和y,“大型数据集的并行聚类算法在生物信息学中的应用,”IEEE / ACM事务计算生物学和生物信息学》第六卷,没有。2、344 - 352年,2009页。视图:出版商的网站|谷歌学术搜索
11. j . c . Bezdek和r·j·海瑟薇”,使用遗传算法优化模糊聚类标准,”学报第一进化计算IEEE会议1994年6月,页589 - 594。视图:谷歌学术搜索
12. t . a . Runkler“蚁群优化的聚类模型,”国际期刊的智能系统,20卷,不。12日,第1251 - 1233页,2005年。视图:出版商的网站|谷歌学术搜索
13. k . s . Al-Sultan和z s斯莱姆,”全球的模糊聚类算法的问题,”模式识别,26卷,不。9日,第1361 - 1357页,1993年。视图:出版商的网站|谷歌学术搜索
14. 进行r·埃伯哈特和j·肯尼迪,“新的优化器使用粒子群的理论,”学报第六届国际研讨会微机器和人类科学页39-43名古屋,日本,1995年10月。视图:谷歌学术搜索
15. t . a . Runkler和c . Katz,“由粒子群优化模糊聚类”《IEEE国际会议上模糊系统可以,页601 - 608年,2006年7月。视图:出版商的网站|谷歌学术搜索
16. 张炳扬。Juang C.-M。萧,学术界。许,“分层的基于集群multispecies粒子群优化的模糊系统优化,“IEEE模糊系统,18卷,不。1、14日至26日,2010页。视图:出版商的网站|谷歌学术搜索
17. 模糊c h . Izakian和a·亚伯拉罕”,为模糊聚类和模糊群的问题,“专家系统与应用程序,38卷,不。3、1835 - 1838年,2011页。视图:出版商的网站|谷歌学术搜索
18. w . Pedrycz”,跟踪集:模糊集表示和处理”,IEEE系统,人,控制论B:控制论,28卷,不。1,第109 - 103页,1998。视图:出版商的网站|谷歌学术搜索
19. j .周w . Pedrycz, d .苗族“尾随rough-fuzzy集群的特征集,”模式识别,44卷,不。8,1738 - 1749年,2011页。视图:出版商的网站|谷歌学术搜索
20. w . Pedrycz”,从模糊集跟踪集:解释和计算,”国际期刊的智能系统,24卷,不。1,48 - 61年,2009页。视图:出版商的网站|谷歌学术搜索
21. s . Mitra w . Pedrycz b招待,“跟踪c:集成模糊和粗糙的集群,”模式识别,43卷,不。4、1282 - 1291年,2010页。视图:出版商的网站|谷歌学术搜索
22. j . c . Bezdek j·m·凯勒r . Krishnapuram和n . r .朋友模糊模式识别和图像处理模型和算法4卷模糊集的手册施普林格,纽约,纽约,美国,1999年。
23. d·l·戴维斯和d . w . Bouldin集群分离的人制定出的措施”,IEEE模式分析与机器智能,1卷,不。2、224 - 227年,1978页。视图:谷歌学术搜索
24. x l·谢·g·贝尼省,“模糊聚类有效性措施。”IEEE模式分析与机器智能,13卷,不。8,841 - 847年,1991页。视图:出版商的网站|谷歌学术搜索
25. j . c . Bezdek和n . r .朋友”一些新的索引集群效度”,IEEE系统,人,控制论,B部分:控制论,28卷,不。3、301 - 315年,1998页。视图:出版商的网站|谷歌学术搜索
26. s . c . Satapathy s . k . Patnaik c d p, s Sahoo,“数据集群使用修改fuzzy-PSO (MFPSO)”学报》第五多学科Int,人工智能技术研讨会,海得拉巴,印度,2011。视图:谷歌学术搜索
27. m . k . Pakhira s Bandyopadhyay, Maulik,“清晰和模糊集群、有效性指数”模式识别,37卷,不。3、487 - 501年,2004页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
28. r . Krishnapuram和j·m·凯勒”可能性c均值算法:见解和建议”,IEEE模糊系统,4卷,不。3、385 - 393年,1996页。视图:出版商的网站|谷歌学术搜索

版权

版权©2014剑凌张和沈。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。