文摘

模糊的缺点c则算法(FCM)需要提前知道集群的数量,提出了一种新的自适应方法来确定最优数量的集群。首先,density-based算法被提出。算法,根据数据集的特点,自动确定可能的最大数量的集群而不是使用经验法则并获得最优初始聚类质心,改进的FCM限制随机选择聚类质心铅结果收敛到局部最小值。其次,本文通过引入罚函数,提出了一种新的模糊聚类有效性指数基于模糊紧性和分离,确保当集群所作的数量的对象数据集,聚类有效性指标的价值并不单调下降,接近于零,所以最优数量的集群失去了鲁棒性和决策功能。然后,基于这些研究,提出了一种自适应FCM算法来估计最优数量的集群的迭代试错过程。最后,实验完成UCI, KDD Cup 1999,和合成数据集,这表明,该方法不仅有效地确定最优数量的集群,但也减少了迭代稳定的FCM聚类结果。

1。介绍

聚类分析已经有很长的研究历史。由于其优势的学习没有先验知识,它广泛应用于模式识别、图像处理、网络挖掘,时空数据库应用程序,商业智能,等等。

集群通常是无监督学习和目标对象数据集分割成几个自然分组,即所谓的集群,集群对象往往是类似虽然属于不同簇的对象是不同的。通常,数据集不同应用领域的不同特性,和聚类的目的是多方面的。因此,最好的方法聚类分析取决于数据集和使用目的。没有统一的集群技术,可广泛适用于各种数据集所呈现的不同结构(1]。根据积累的规则对象在集群和应用这些规则的方法,聚类算法分为许多类型。然而,对于大多数聚类算法包括partitional聚类和层次聚类簇的数量是一个参数需要预设,聚类结果的质量是密切相关的。在实际应用程序中,它通常依赖于用户的经验或相关领域的背景知识。但在大多数情况下,集群的数量对用户来说是未知的。如果分配数量太大,可能会导致更复杂的聚类结果难以解释道。相反,如果太小,很多有价值的信息聚类结果可能会丢失(2]。因此,它仍然是一个基本问题的研究聚类分析来确定最优的集群数量数据集(3]。

本文的贡献如下。(1)density-based算法,可以快速、简洁地生成高质量的初始聚类质心而不是随机选择,以稳定聚类结果也加快聚类算法的收敛性。此外,该算法可以自动估计的最大数量集群基于数据集的特性,据此确定搜索范围估计最优数量的集群,有效减少了迭代的聚类算法。(2)基于紧凑的特点在集群和集群之间的分离,一种新的模糊聚类有效性指标(CVI)界定本文避免其值接近于零随着集群的数量趋于对象的数量和获得最优聚类结果。(3)自适应迭代方法,使用改进的FCM算法来估计提出了最优数量的集群。

2。相关工作

最简单的方法确定集群的数量数据可视化。的数据集可以有效地映射到一个二维欧氏空间中,集群的数量可以直观地通过数据点的分布曲线。然而,对于高维、复杂的数据,这个方法是无用的。罗德里格斯和Laio提出了基于密度的聚类算法山峰,宣称它能检测nonspherical集群和自动找到真正的集群的数量(4]。但事实上,聚类质心的数量仍然需要人为选择根据决策图。接下来,相关技术来确定最优数量的集群总结如下。

2.1。基于聚类有效性指标的方法

聚类有效性指标用来评估质量的分区数据集生成的聚类算法。它是一种有效的方法来构造一个合适的聚类有效性指数来确定集群的数量。这个想法是为了分配不同的集群的数量值在一定范围内,然后在数据集上运行模糊聚类算法,最后通过聚类有效性指标来评估结果。当聚类有效性的价值指数的最大值或最小值或者一个明显的拐点出现,相应的价值集群的最优数量吗。到目前为止,研究人员已经提出了大量的模糊聚类有效性指标,分为以下两种类型。

(1)基于模糊聚类有效性指数分区。这些指数是根据这种观点截然分开的数据集,模糊分区的模糊性越小,聚类结果越可靠。在此基础上,陈守煜,模糊集的创始人,提出第一个聚类有效性指数在1965年分离度(5]。但其识别效果并不理想。1974年,Bezdek提出分配系数的概念(PC) (6)是第一个实用的通用函数测量模糊聚类的有效性,随后提出另一个聚类有效性函数划分熵(PE) (7分配系数密切相关。之后,温德姆定义比例指数利用模糊隶属函数的最大值8]。李提出一个模糊聚类有效性指标使用distinguishableness集群以亲近的对象(9]。基于香农熵和模糊变异理论,张和江提出一种新的模糊聚类有效性指标考虑数据集的几何结构(10]。萨哈等人提出一种基于微分进化算法为集群自动检测,这好评价聚类结果的有效性(11]。越等人分区原始数据空间成网格结构,提出了集群分离测量基于网格的距离(12]。基于模糊划分聚类有效性指数只是模糊隶属程度有关,简单和计算量小的优点。但它缺乏直接关系与一些数据集的结构特点。

(2)聚类有效性指数基于数据集的几何结构。这些指数是基于这样一种观点截然分开的数据集,每一个集群都应该尽量紧凑,彼此分离。密实度和分离的比例是用作聚类有效性的标准。这种类型的代表聚类有效性指标包括Xie-Beni指数(13],Bensaid指数[14],Kwon指数(15]。太阳等人提出了一种新的基于线性组合有效性指数的密实度和分离和灵感来自Rezaee的有效性16]。李和Yu定义新的密实度和分离,提出了一种新的模糊聚类有效性函数(17]。基于模糊granulation-degranulation、萨哈和Bandyopadhyay提出一个模糊聚类有效性函数(18]。张等人采用皮尔逊相关测量距离提出有效性函数(19]。金等人提出了一个聚类有效性指数GK算法基于平均值的相对程度的共享所有可能的双模糊集群(20.]。Rezaee提出了一种新的有效性指数g·金算法来克服的缺点指数(21]。张等人提出了一个新颖的WGLI检测最优簇数,利用全球最佳会员的全球房地产和模块化两偶网络作为当地的独立财产(22]。聚类有效性指数基于数据集的几何结构考虑模糊隶属程度和几何结构,但其隶属函数非常复杂的计算量大。

基于聚类有效性指标,确定最优数量的集群通过穷举搜索。为了提高估计的最优数量的集群的效率的搜索范围必须设置;也就是说,集群的最大数量,分配给符合条件。大多数研究人员使用了经验法则,在那里是数据集的数据。对于这个问题,进行了理论分析和实例验证(23),这表明它在某种意义上是合理的。然而,很显然,这种方法有以下缺点。(1)每必须试着反过来,这将导致一个巨大的计算。(2)不能保证聚类的结果是全局最优的解决方案。(3)现有噪声和离群值时,聚类有效性指标的可靠性薄弱。(4)对于某些数据集像FaceImage24),如果,经验法则将会无效。研究表明,由于多元化的数据类型和结构,没有通用的模糊聚类有效性指标可以适用于所有的数据集。这项研究是迫切和仍将继续。

2.2。启发式方法

最近陆续提出了一些新的聚类算法。的主要思想是使用某些标准来指导聚类过程中,集群的数量被调整。通过这种方式,而聚类完成后,可以获得适当数量的集群。例如,则算法(25基于分裂层次聚类的代表。与上述过程相反,RCA (26)集群的实际数量取决于竞争聚集的过程。单点迭代技术结合层次聚类,相似性聚类方法(SCM) (27提出了]。美世基于聚类(28]估计数量的集群由一个内核矩阵的特征向量。基于最大的聚类算法遥远的子树(29日)检测到任意数量的布置得井然有序集群与任何形状。此外,弗雷和Dueck提出一个亲和力传播聚类算法(美联社)(24)产生高质量通过对象之间的消息传递集群重心确定集群的大规模数据的最优数量。Shihong等人提出了一个Gerschgorin磁盘estimation-based准则来估计真实数量的集群(30.]。Jose-Garcia和Gomez-Flores提出的最新审查所有主要产品表面metaheuristic迄今为止算法用于自动聚类,确定集群的数量(的最佳估计31日]。所有这些已经扩大了思想相关研究。

3所示。传统的FCM确定最优数量的集群

自从Ruspini首次把模糊集理论引入聚类分析(1973年32),不同的模糊聚类算法被广泛讨论,各领域的开发和应用。FCM (33)是最常用的算法之一。FCM在1974年首次由邓恩。随后,Bezdek引入加权指数模糊隶属程度(34进一步发展FCM)。FCM划分数据集成模糊集群。该算法认为每个对象属于某一集群不同的隶属程度,也就是说,一个集群被认为是一个数据集上的模糊子集。

假设是一个有限的数据集,在哪里是l-dimensional对象是th的属性对象。表示集群(s)。代表l-dimensional集群质心(s),。是一个模糊划分矩阵,的隶属程度是th对象th集群,。目标函数是重距离的平方和的样品每个集群的集群重心;也就是说, 在哪里显示之间的欧氏距离th对象和聚类质心。()是一个模糊性指数,控制会员的模糊性。的价值变得越来越高,由此产生的会员成为模糊35]。朋友和Bezdek建议应该在1.5和2.5之间,通常让吗如果没有特殊要求36]。

根据聚类准则,适当的模糊划分矩阵和聚类质心得到了最小化目标函数。基于拉格朗日乘子法,和分别是由下面的公式计算:

FCM算法进行通过最小化目标函数的迭代过程的更新和。具体步骤如下。

步骤1。分配的初始值集群的数量,模糊性指数、最大迭代和阈值。

步骤2。初始化模糊分区根据随机约束的隶属程度。

步骤3。在一步一步,计算集群重心根据(3)。

步骤4。计算目标函数根据(1)。如果或,然后停止;否则继续第5步。

第5步。计算根据(2)并返回到步骤3。

最后,每一个对象都可以安排到一个集群按照最大隶属程度的原则。FCM的优点可以总结为简单的算法,快速收敛,并轻松扩展。其缺点在于选择初始聚类质心,噪声和离群值的灵敏度,集群的数量的设置,对聚类结果有很大的影响。的随机选择初始聚类质心不能确保这一事实FCM收敛于最优解,不同初始聚类质心FCM用于多个运行;否则他们决心通过使用其他的快速算法。

的传统方法确定最优簇数的FCM是设置集群的数量的搜索范围,运行FCM生成聚类的结果不同数量的集群,选择一个合适的聚类有效性指数来评价聚类结果,最后得到最优数量的集群根据评价结果。该方法由以下步骤组成。

步骤1。输入的搜索范围;一般来说,和。

步骤2。对于每一个整数。
步骤2.1。FCM运行。
步骤2.2。计算聚类有效性指标。

步骤3。比较聚类有效性指标的所有值。对应的最大或最小值的最优数量的集群。

步骤4。输出聚类有效性指标的最优值,聚类的结果。

4所示。提出的方法

4.1。Density-Based算法

考虑到很大的影响的随机选择初始聚类质心聚类结果,density-based算法来选择初始聚类质心和集群的最大数量可以大约在同一时间。一些相关术语的定义。

定义1(本地密度)。当地的密度的对象被定义为 在哪里两个物体之间的距离吗和和是一截距离。推荐的方法是任何两个物体之间的距离在降序排列,然后分配值对应于第一(适当的排序的距离)。这表明更多的对象的距离不到有更大的价值是多少。截止距离最终可以决定初始聚类质心的数量,即集群的最大数量。density-based算法是鲁棒的选择。

定义2(核心)。假设有一个对象,如果和,,,然后是一个核心问题。

定义3(直接density-reachable)。假设有两个对象,,如果他们的距离,然后直接density-reachable反之亦然。

定义4 (density-reachable)。假设是一个数据集和对象属于它。如果为每个,直接density-reachable,然后是density-reachable。

定义5(邻居)。邻居的一个对象是那些直接density-reachable或density-reachable,表示是邻居吗。

定义6(边界点)。对象被称为边界点,如果它没有邻居。

示例如图1。

density-based算法的初始聚类质心的选择原则是,通常,一个集群重心是一个对象与当地更高密度,周围邻居当地较低的密度比,和有一个相对较大的其他集群质心的距离(4]。Density-based算法可以自动选择初始聚类质心和确定集群的最大数量据当地密度。算法伪代码所示1。这些集群重心获得按降序排序根据当地密度。图2演示了density-based算法的过程。

4.2。模糊聚类有效性指标

首先基于数据集的几何结构,谢和贝尼省提出了Xie-Beni模糊聚类有效性指数(13),试图找到一个平衡点之间的模糊密实度和集群分离,以获得最优的结果。该指数被定义为

公式中,分子的平均距离是各种物体质心,用来测量密实度,分母是任意两个重心之间的最小距离,测量分离。

然而,Bensaid等人发现,每个集群的大小有很大影响Xie-Beni指数,提出一个新的索引(14),这是对对象的数量在每个集群。Bensaid指数被定义为 在哪里的模糊基数吗集群和定义为

显示的变化模糊聚类。然后,密实度计算

表示的分离th模糊集群,集群定义为距离的总和其质心的重心集群。

因为 这个指数是一样的Xie-Beni指数。当,索引值将单调下降,接近0,将失去的鲁棒性和判断函数确定最优数量的集群。因此,本文改进了Bensaid指数,提出一个新的索引:

分子代表的密实度th集群,是它的模糊基数。第二项,引入惩罚函数,表示的聚类质心的距离集群平均的集群质心,从而消除单调递减趋势随着集群的数量增加。分母代表的平均距离th集群质心到其他集群重心,用于测量分离。分子和分母的比率代表的聚类效果集群。聚类有效性指数被定义为集群效应的总和(比例)的所有集群。显然,值越小,更好的数据集的聚类效果,和相应的最小值的最优数量的集群。

4.3。自适应FCM

在这篇文章中,迭代试错过程(16)仍然是用来确定最优数量的集群的自适应FCM (SAFCM)。SAFCM算法的伪代码描述的算法2。

5。实验和分析

本文选择8实验数据集,其中3个数据集来自UCI数据集,分别虹膜,酒,和种子,一个数据集(SubKDD)是随机选择从KDD Cup 1999表所示1,剩下的合成数据集如图4的数据集3。SubKDD包括正常,2种探针攻击(ipsweep和portsweep)和三种DoS攻击(海王星,蓝精灵,回)。第一个合成数据集(SD1)由20二维高斯分布数据与10个样本。协方差矩阵二阶单位矩阵。数据集的结构特征是任何两个集群之间的距离很大,和类的数量大于。第二种合成数据集(SD2)由4二维高斯分布数据。集群重心,分别(5,5),(10,10),(15日,15),和(20、20),每个包含500个样本的协方差矩阵。数据集的结构特征是短intercluster距离小重叠。第三个合成数据集(SD3)具有复杂的结构。第四个合成数据集(SD4)是一个非凸。

摘要数值是归一化 在哪里和表示的意思th属性值和标准差分别;然后

SubKDD的分类属性的简单匹配用于不同措施,也就是说,0为不同的值相同的价值观和1。

5.1。实验的模拟

在[37),它提出了集群的数量由美联社生成算法可以选为集群的最大数量。所以本文估计的价值由经验法则、AP算法和density-based算法。具体实验结果如表所示2。让在AP算法。分别是,选为距离的1%,2%,3%,5%。

实验结果表明,与集群的真实数量大于数据集,这显然是不正确的,让。换句话说,经验法则是无效的。集群的数量最后通过AP算法接近集群的实际数量。真实的数据集数量的集群小于集群的数量由AP算法可以作为一个合适的,但有时,价值大于价值估计的经验法则,扩大搜索范围的最优数量的集群。如果提出density-based估计的算法,结果在大多数情况下是合适的。是无效的方法只有在SD1当截止距离是第一个5%的距离。当选择截止距离距离,第一个3%生成的算法要小得多。它更接近真实数量的集群和大大缩小搜索范围的最优数量的集群。因此,选择截止距离的距离第一个3%在以后的实验。

5.2。影响实验的初始聚类质心FCM的收敛

表明density-based获得的初始聚类质心算法可以加快聚类算法的收敛性,采用传统的FCM核查。集群的数量分配的真正价值,与收敛阈值。由于随机选择初始聚类质心对FCM有很大影响,每个数据集都是反复的实验50次,整数的算法迭代的均值进行了比较。具体实验结果如表所示3。

如表所示3density-based获得的初始聚类质心算法可以有效地减少FCM的迭代。SD1特别,迭代的FCM远远小于随机选择初始聚类质心的最小迭代是24和最大迭代达到63,与不稳定的聚类结果。因此,该方法不仅可以有效地加快收敛的FCM,还获得一个稳定的聚类结果。

5.3。实验基于聚类有效性指标的聚类精度

3 UCI数据集和SubKDD聚类准确性采用测量聚类效果,定义为

在这里共现的对象的数量吗th集群和th真正的集群,在数据集对象的数量。根据这个测量、聚类精度越高,FCM聚类的结果就是越好。当,FCM聚类的结果是完全准确的。

在实验中,真正的集群的数量分配给每个数据集和density-based获得的初始聚类质心算法。然后,实验结果的聚类精度如表所示4。

显然,数据集的聚类精度酒、种子、和SubKDD很高,而虹膜数据集的相对较低的原因,两个集群是非线性可分的。

聚类结果的聚类有效性指数合成数据集如图44,描述好分区数据集SD1 SD2和略差分区在SD3 SD4因为其结构的复杂性或nonconvexity。当集群的数量设置为4,SD3分为4组,这意味着左边和右边各有两组。

5.4。实验的最优数量的集群

最后,Xie-Beni指数,Bensaid指数,Kwon指数,该指数,分别采用运行SAFCM以确定最优数量的集群。结果如表所示5。,,,代表Xie-Beni指数、Bensaid指数,Kwon指数,分别提出了指数。

这表明,合成数据集SD1和SD2结构简单,这些指标都能获得最优数量的集群。3 UCI数据集,SubKDD SD4, Bensaid指数不能获得一个准确数量的集群SD3除外。数据集的葡萄酒,Xie-Beni指数和Kwon指数可以获得准确数量的集群,而虹膜数据集,种子,SubKDD, SD3, SD4,他们只获得结果近似真实数量的集群。该指数获得正确的结果数据集葡萄酒和SD4和一个更好的结果比Xie-Beni指数和Kwon指数的数据集SubKDD SD3,虽然获得相同的结果两个指标的数据集虹膜和种子。有两个原因。首先,数据集的每个属性的重要程度是不被认为是在聚类过程中,但被认为是相同的,从而影响实验结果。第二,SAFCM弱处理重叠集群或nonconvexity数据集的能力。这些都是作者的后续研究内容。

表6- - - - - -13清单4的详细结果指标的实验数据集在每个迭代中SAFCM。数据集的酒,当集群的数量是4,5或6,结果基于Xie-Beni指数或Kwon指数收敛。然而,该指数能达到期望的结果。

6。结论

FCM在很多领域被广泛使用。但它需要预设数量的集群和深受初始聚类质心。本文研究自适应方法确定利用FCM算法的簇的数目。在这种方法中,density-based算法提出,可以估计集群的最大数量减少最优数量的搜索范围,特别是在适合的数据集经验法则是不起作用的。除此之外,它可以生成高质量的初始聚类质心,聚类的结果是稳定和FCM是快速的收敛。然后,提出了一种新的模糊聚类有效性指标基于模糊紧性和分离的聚类结果更接近全局最优。该指数是健壮和可当集群的数量往往在数据集中的对象。最后,提出了一种自适应FCM算法确定最优数量的集群运行的迭代试错过程。

的贡献是由实验结果验证。然而,在大多数情况下,每个属性聚类过程中扮演着不同的角色。换句话说,属性的重量是不一样的。这个问题将在作者的关注未来的工作。

相互竞争的利益

作者宣称没有利益冲突。

确认

这部分工作是由中国国家自然科学基金(61373148和61373148),山东省自然科学基金(ZR2014FL010),中国教育部科学基金会(14 yjc 860042),山东省杰出青年科学家奖基金(BS2013DX033),山东省社会科学项目(15 cxwj13和16 cfxj05),和项目的山东省高等教育科技计划(没有。J15LN02)。