谱聚类算法的基础上改进的高斯核函数和甲虫天线搜索与阻尼因子

文摘

有两个问题在传统的谱聚类算法。首先,当它使用高斯核函数构造相似度矩阵,不同尺度参数的高斯核函数的算法会导致不同的结果。其次,k - means算法常用的谱聚类算法的聚类阶段。它需要随机初始化聚类中心,这将导致不稳定的结果。本文提出一种改进的谱聚类算法来解决这两个问题。在构建相似性矩阵,我们提出了一种改进的高斯核函数,它是基于一些最近的邻居的距离信息,可以自适应地选择参数。在聚类阶段,甲虫天线与阻尼因子,提出了搜索算法,完成聚类来克服聚类结果不稳定的问题。在实验中,我们使用四个人工数据集和七个UCI数据集来验证算法的性能。此外,四个图像BSDS500图像数据集分割,结果表明,我们的算法比其他在图像分割算法进行比较。

1。介绍

聚类分析是数据挖掘领域的一个重要的研究问题。聚类的目的是将数据集划分为不同的簇之间的内在结构和关系数据显示,同一集群内的数据点之间的相似性较高,在不同的集群和数据点之间的相似性较低。主要聚类方法包括partitioning-based聚类、层次聚类,density-based集群、基于网格的聚类、基于理论的聚类图。不同的聚类算法也应用于不同的领域,如图像分割(1- - - - - -4),文本聚类(5,6),和社区部门(7- - - - - -9]。

谱聚类是一种基于图论的聚类算法。由谱图分区理论(10),数据集的聚类问题转化为图划分问题。在光谱聚类,每个数据点被认为是图的顶点,和数据点之间的相似性被认为是边缘的重量。图,除以重量之和边缘的子图是尽可能高,和边缘的重量之和之间不同的子图是尽可能低。

1973年,Donath和霍夫曼(10)首次提出的概念图分区基于邻接矩阵,标志着正式的谱聚类的诞生。同年,菲德勒[11)发现,双向无向图的分区是密切相关的第二个小特征值对应的特征向量对应的拉普拉斯算子矩阵,它提供了一种新方法来解决图像分区的问题。2000年,史和马利克(12)提出了标准的目标函数,也称为N-cut标准,基于光谱理论。2001年,丁等。13]提出了基于N-cut最大和最小割集的标准,这两个需求平衡的最小部门损失和最大顶点数量的子图,使部门更倾向于平衡较小的子图的割集和避免分割只有几个顶点。2002年,约旦,维斯和Ng (14]提出NJW算法,它不同于双向部门。该算法是基于k收费方法,也是目前使用最广泛的谱聚类算法。尽管谱聚类的良好发展,算法本身仍存在一些问题,比如如何选择高斯核函数的尺度参数。2004年,学者15)已经证明规模参数的选择将会影响聚类的结果。为了解决这个问题,Zhang et al。16)提出了相似矩阵的施工方法基于局部密度。Nataliani和杨17)提出了一个能量高斯核函数来解决这个问题。

甲虫天线搜索算法(BAS)是一种优化算法受甲虫的觅食原理提出的江和李182017年)。通过模拟甲虫的检测功能的触角和甲虫的机制的随机行走,一种优化机制类似于甲虫的觅食过程实现。根据食物的气味,甲虫的移动方向。当左触手强烈的气味,它将向左移动;否则,它就会向右移动。通过随机定向机制和可变步长机制,甲虫可以搜索全球范围。与其它智能算法相比,该算法不需要知道具体形式的梯度信息和功能,具有收敛速度快、低要求的参数。因此,它已经在一些领域的应用。王旭和刘刚(19)结合BAS的反向神经网络算法预测风暴灾害的损失。陈等人。20.)使用基于BAS算法的粒子群优化算法来解决投资组合模型。王,陈21]提出一种蜜蜂群天线搜索算法(bsa)。

本文的主要贡献如下:(1)提出了相似矩阵的施工方法,它使用一些最近的邻居的距离信息定义尺度参数σ为了克服人工指定尺度参数的影响σ的结果。(2)在聚类阶段,我们使用该甲虫天线与阻尼因子(dba)搜索算法,完成聚类。通过这样一种智能优化算法,我们可以克服集群中心的随机初始化的影响结果,当k - means用于传统的谱聚类。和阻尼因素克服了迭代过程中的振荡,提高了算法的稳定性。

本文的内容组织如下。节3,一种改进的谱聚类算法基于一些最近的邻居和甲虫天线的距离信息搜索算法提出了阻尼因子。部分4通过实验分析表明该算法的性能。结论将在部分5。

2。谱聚类和甲虫天线搜索算法

2.1。谱聚类

谱聚类算法使用拉普拉斯算子矩阵的特征向量对应的数据集集群。谱聚类算法,首先,一个无向图 根据数据点构造。每个顶点在图上对应于一个数据点,和体重边缘数据点之间的相似性。一般来说,我们使用高斯核函数构造相似矩阵。然后,我们可以得到一个学位矩阵 ,其主对角线元素之和等于行元素对应的相似矩阵。通常有三种方法来构造拉普拉斯算子矩阵 :(1)非正规拉普拉斯算子矩阵,(2)规范化对称拉普拉斯算子矩阵 ,和(3)规范化不对称拉普拉斯算子矩阵 。特征向量对应于第一个k拉普拉斯矩阵的特征值可以计算和设置 。然后,一个新特性矩阵通过正常化 。特征矩阵中的每一行被认为是一个样本,这是集群获得一组集群 。NJW算法(14)是最常用的谱聚类算法。NJW算法的基本步骤中显示算法1。

2.2。甲虫天线搜索算法(BAS)

基于甲虫的觅食的原则,三个优化策略可以简化:(1)的左和右天线甲虫位于两边的个体。(2)每个操作的步长比两个天线之间的距离是一个固定的常数。(3)移动后,其头部的方向是随机的。然后,我们可以建立一个优化模型(甲虫是简化为一个人):(1)为一个优化问题n维空间,用于表示左边的坐标天线的一个个体,代表正确的一个个体,天线的坐标是质心坐标。是两个天线之间的距离。由于个人的取向是随机每次运动后,向量的方向,个人的权利指向左边也是随机的。它可以表示通过规范化的随机向量 。有 。(2)最小化目标函数 , 和 。如果小于 ,然后个人旅行的方向离开天线一步,否则,个人的距离一步朝着正确的天线方向。 (3)重复第1步和第2步,直到达到最大迭代次数或个人不会改变米迭代。

3所示。改进的谱聚类算法

在本节中,我们改进高斯核函数和BAS算法,分别。后使用新的高斯核函数构造相似度矩阵,利用谱聚类算法得到一个新特性矩阵,然后,我们用改进的BAS算法集群。

3.1。一种改进的高斯核函数

在传统的谱聚类中,相似矩阵通常是根据高斯核函数构造公式的算法1,在那里尺度参数;一般来说,规模参数人工选择。2004年,学者15)证明规模参数的选择将会影响聚类的结果。为了解决这个问题,本文提出一种基于距离的相似矩阵的构建方法信息的一些最近的邻居: 在哪里 ,的平均距离最近的是哪一个点与点 。 样本总数的比例是集群的数量的平方。 ,在哪里样品和总数吗是集群的数量。

3.2。甲虫天线搜索算法和阻尼因子(dba)

就像前面提到的2.2,个人的方向是随机在每个迭代中。这导致更多的振荡过程中算法的迭代。有可能的结果米+ 1迭代比的米多次迭代。我们提出了阻尼因子添加到个人的位置更新公式,更新位置信息通过使用迭代的结果最后迭代。公式被描述为 在哪里表示位置t−1日迭代, 。

我们用阻尼因子的算法和该算法没有阻尼因子实验在Iris数据集。图1表明,阻尼因子添加到算法可以有效地克服迭代过程中的振荡问题。

3.3。SC-DBAS算法

首先,我们使用高斯核函数基于一些最近的邻居的距离信息(公式2)来构造相似矩阵,然后计算矩阵和拉普拉斯矩阵相应的学位。我们首先选择相对应的特征向量k拉普拉斯矩阵的最小特征值来构造一个特征矩阵,然后得到一个新的特征矩阵规范化。矩阵的每一行是一个样本点。对于这样一个新的数据集,我们随机初始化一群集群中心作为一个个体,然后使用dba算法集群。SC-DBAS算法流算法2。

3.4。计算复杂度

该算法的计算复杂度可以计算如下:SC-DBAS算法分为三个部分:(1)建立一个类似的图,这需要 ,(2)特征值分解,它的需求 ,和(3)集群通过使用dba算法,它需要 ,在哪里k集群中心的数量和吗l是迭代的数量。根据大的符号O,该算法的计算复杂度 。

4所示。实验结果和分析

4.1。实验设置

所有的实验都是在电脑上进行与英特尔酷睿i5 - 3230 m CPU, 8 GB RAM。实验环境是Matlab 2016 b。在实验中,我们比较该算法和k - means, NJW [14],MPSC算法[22],PGSC算法[17[],SC-NP算法23)在四个人工数据集和七个UCI数据集。该算法还将利用BSDS500数据集的图像进行图像分割。在图像分割的实验部分,比较算法k - means, NJW [14],PGSC算法[17[],SC-NP算法23]。

在实验中,参数设置如下:步骤= 0.1;一步调整系数η= 0.95;步进之间的比率是5;迭代的次数n= 100;和潮湿= 0.5。数据集的信息如表所示1。

4.2。评价指标

在实验中,我们用四个指标来评价聚类结果:准确性、阿里、F1分数,和时间。(1)准确率:准确率代表的数量的比例正确聚类样本的样本总数,V标签和分工U是真正的标签: (2)阿里:有四种情况下通过比较计算结果V与真正的标签U。党卫军包含示例对属于同一集群中V和相同的集群U。SD包含示例对属于同一集群中V但不相同的集群U。DS包含样品对不属于同一集群中V但属于同一集群中U。DD包含样品对不属于同一集群中V和不属于同一集群中U。集 ;有

阿里的价值越大,聚类结果更符合实际情况。(3)F1得分:F1得分是信息检索的常用的评估标准。这是一个基于精度和召回的加权调和平均值。它的定义如下,一个,b,c定义了在上面的内容: (4)时间:在本文中,我们使用每个算法运行100次的平均时间作为评价指标。

4.3。数据集实验结果分析

4.3.1。人工数据集的实验结果

表2显示了六种算法的实验结果在四个人工数据集。从图2,我们可以看到,我们的算法可以划分数据集的各种结构。

4.3.2。UCI数据集的实验结果

表3和图3显示六个算法的实验结果在七UCI数据集。通过比较结果,我们可以看到,本文提出的算法执行比其他五个算法和只有一个较短的运行时间。

4.4。SC-DBAS算法在图像分割中的应用

Clustering-based图像分割是基于图像像素之间的相似度;通过一些聚类算法,像素分为不同的集群,以完整的原始图像的分割。

在本节中,我们部门的一些图像BSDS500数据集。481∗321像素图像,如果我们把每个像素作为一个数据点,将会有154401数据点。因此,为了减少数据点的规模,我们首先使用SLIC算法(24)执行presegmentation (superpixel细分)的形象。每个superpixel oversegmented地区,被认为是一个数据点。然后,该算法用于分割图像。在这项实验中,superpixels的每个图像的数量是200。算法的比较实验中使用k - means, NJW [14],PGSC算法[17[],SC-NP算法23]。然后,我们可以给出图的结果4。

从实验结果中,我们可以看到,我们的算法可以分割对象和背景更好,而其他四个比较算法将错误的分割区域。分割精度结果如表所示4。

5。结论

在本文中,一种改进的谱聚类算法与改进的BAS算法相结合。该算法首先提高了建筑的相似性矩阵,它使用一些最近的邻居的距离信息的每一个点来计算相应的尺度参数。在集群的阶段,我们提出了BAS与阻尼因子聚类算法,可以克服原算法振荡的问题多次迭代过程。实验结果表明,我们的算法比其它算法在UCI数据集,人工数据集,和图像分割。然而,在图像分割中的应用,我们的结果将影响superpixel分割的影响。未来的工作是改善我们的算法,它不需要进行预处理,图像分割,可以直接分割图像,我们将使用更多的真实的图像和医学图像来验证我们的算法。

数据可用性

手动生成的四个人工数据集可以通过联系作者。七个UCI数据集的现有文献中经常使用UCI机器学习库可以在http://archive.ics.uci.edu/ml/datasets.php。四个测试图像来自伯克利计算机视觉组,伯克利分割数据集,和基准500 (BSDS500),这是可用的https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html。

的利益冲突

作者宣称没有利益冲突。

确认

本研究项目是由中国国家自然科学基金(61876101,61876101,61806114),山东省社会科学基金项目、中国(16 bglj06和11 cglj22),山东省自然科学基金项目,中国(ZR2019QF007),博士后项目,中国(2017年m612339和2018 m642695),人文社会科学青年基金的教育部,中国(19 yjczh244),和博士后特别资助项目,中国(2019 t120607)。

引用

1. 答:观测。刘,h . Hong Yan, n . f .法律,“图像分割基于自适应集群原型估计,“IEEE模糊系统,13卷,不。4、444 - 453年,2005页。视图:出版商的网站|谷歌学术搜索
2. f .东、黄a和d . a . Clausi”使可伸缩的谱聚类的图像分割,模式识别,43卷,不。12日,第4076 - 4069页,2010年。视图:出版商的网站|谷歌学术搜索
3. w .严,美国史,l .锅g . Zhang和l .王”非监督变化检测SAR图像中基于频差和改进模糊c均值聚类,“国际遥感杂志》上,39卷,不。10日,3055 - 3075年,2018页。视图:出版商的网站|谷歌学术搜索
4. l . Rada h·阿里,n . Badshah”图像分割为高噪音强度不均匀性的存在,”IEEE图像处理,27卷,不。99年,2018年。视图:出版商的网站|谷歌学术搜索
5. 崔x、t . e . Potok和p . Palathingal“文档使用粒子群优化聚类,”学报》2005年IEEE群体智慧研讨会2005年6月美国帕萨迪纳市,CA。视图:出版商的网站|谷歌学术搜索
6. r . Janani和s Vijayarani”文本文档聚类使用谱聚类算法和粒子群优化,“专家系统与应用程序卷,134年,第200 - 192页,2019年。视图:出版商的网站|谷歌学术搜索
7. h .太阳,j .黄j .汉h·邓·赵和b·冯”Density-based通过结构连接网络聚类树分裂或聚集,”诉讼IEEE国际会议上的数据挖掘2010年12月,悉尼,澳大利亚,。视图:出版商的网站|谷歌学术搜索
8. p·g .太阳、l .高和s .山汉”识别重叠与非重叠社区结构的模糊聚类在复杂网络,”信息科学,卷181,不。6,1060 - 1071年,2011页。视图:出版商的网站|谷歌学术搜索
9. y, z .壮族、w·李和x周,“有效”社区部门改进的谱聚类的基础上,Neurocomputing卷。279年,54 - 62年,2018页。视图:出版商的网站|谷歌学术搜索
10. w·e·Donath a·j·霍夫曼:“下界的分区图。”IBM杂志》上的研究和发展,17卷,不。5,420 - 425年,1973页。视图:出版商的网站|谷歌学术搜索
11. m·菲德勒,”代数连通图”,捷克斯洛伐克的数学杂志,23卷,不。23日,第305 - 298页,1973年。视图:谷歌学术搜索
12. j·史和j·马利克规范化削减和图像分割,”IEEE模式分析与机器智能,22卷,不。8,888 - 905年,2000页。视图:谷歌学术搜索
13. c .叮,x, h .咋et al .,光谱Min-Max切图分区和数据聚类伯克利,劳伦斯伯克利国家实验室、钙、美国,2001年。
14. a . y . Ng,约旦,和y . Weiss,“谱聚类:分析和算法学报》国际会议神经信息处理系统:天然和合成麻省理工学院出版社,页849 - 856年,2001年12月加拿大,温哥华。视图:谷歌学术搜索
15. l . Zelnik庄园和p . Perona一起自调优谱聚类”,先进的神经信息处理系统,17卷,第1608 - 1601页,2005年。视图:谷歌学术搜索
16. x张、j·李和h . Yu”局部密度自适应谱聚类相似度测量,”模式识别的字母,32卷,不。2、352 - 358年,2011页。视图:出版商的网站|谷歌学术搜索
17. y Nataliani M.-S。杨,”高斯内核驱动谱聚类”,神经计算和应用没有,卷。31日。S1, 557 - 572年,2019页。视图:出版商的网站|谷歌学术搜索
18. 江x和李美国,“BAS:甲虫天线搜索算法优化问题,“国际期刊的机器人和控制,1卷,不。1、1 - 5,2018页。视图:出版商的网站|谷歌学术搜索
19. t·王、刘问:“基于BAS-BP风暴潮灾害损失的评估模型,”海洋环境科学,37卷,不。170年,第146 - 140页,2018年。视图:谷歌学术搜索
20. 江h . t . Chen, h . et al .,“基于蜜蜂天线搜索的粒子群优化算法解决组合问题,“计算机系统及应用程序,28卷,不。2、171 - 176年,2019页。视图:谷歌学术搜索
21. 王j·h·陈,“蜜蜂群搜索算法优化天线问题。”国际期刊的机器人和控制,1卷,不。1,p。2018。视图:谷歌学术搜索
22. s . l . Wang叮,h·贾”的改进谱聚类通过消息传递和密度敏感的相似之处,”IEEE访问7卷,第101062 - 101054页,2019年。视图:出版商的网站|谷歌学术搜索
23. X.-Y。李和L.-J。郭”,构建关联矩阵谱基于近邻传播聚类,“Neurocomputing卷,97年,第130 - 125页,2012年。视图:出版商的网站|谷歌学术搜索
24. r . Achanta a .沙棘k . Smith, a . Lucchi p . Fua和s . Susstrunk”SLIC superpixels先进的superpixel方法相比,“IEEE模式分析与机器智能,34卷,不。11日,第2282 - 2274页,2012年。视图:出版商的网站|谷歌学术搜索

版权

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