【基于图聚类的FCM算法及MATLAB仿真探析6700字（论文）】

基于图聚类的FCM算法及MATLAB仿真分析摘要聚类分析是当前研究的一个重要方向， 其目的是将数据集进行拆分，形成多个有意义的簇，进一步来实现对数据的识别。图聚类是一种比较新的聚类方法，它一般先将数据表达成为图，然后再将聚类的问题转化成为图划分的问题。图聚类方法可以对任意的数据信息进行聚类分析，改善了传统聚类分析的不足。本文通过分析图聚类算法的相关理论，实现一种基于噪声点消除的图聚类算法。首先，本次研究利用自然邻居的概念构造自然邻居图，构图时将输入的数据集表示为自然邻居图;其次使用模糊C均值聚类算法（FCM算法，FuzzyC-Means）将数据集分为多个组，对数据集中的样本点之间的距离进行计算，将每个组中距离其他样本点较远的点视为噪声点并为其分配较低的隶属度，根据隶属度计算聚类中心，将隶属度低的点删除以达到去除噪声的目的;最后计算非相似性指标的目标函数，根据聚类中心再返回计算隶属度，经过多次迭代后使得目标函数最小则完成聚类分析，输出聚类的结果。本文通过Matlab工具对基于噪声消除的图聚类算法进行实现，以Matlab绘图函数构建的图为输入数据集，实验结果显示可以较好地完成图数据集的聚类划分。关键词：图聚类算法图像分割噪声MATLAB目录1绪论 11.1研究背景及意义 11.2国内外研究现状 11.3论文主要研究内容 22相关理论概述 32.1图论 32.1.1图的基本概念 32.1.2图的邻接矩阵 32.1.3自然邻居图 52.2聚类概述 52.2.1聚类分析 62.2.2主要聚类方法 63基于图聚类的FCM算法 73.1FCM算法概述 73.1.1FCM算法的一般步骤 73.1.2隶属度函数 83.2FCM算法的去噪原理 84基于MATLAB的图聚类算法仿真模拟 94.1基于MATLAB的图聚类算法仿真 94.2仿真结果 10总结与展望 15参考文献 161绪论1.1研究背景及意义聚类分析是一种在没有监督学习的环境中对簇的研究，其将不同簇之间数据的区别进行扩大，缩小相同簇数据之间的区别。聚类分析具有悠久的历史，并且随着社会的进步该分析方法也得到了不断的创新。该研究是模式识别和机器学习领域中关键的一个研究方向，作为一个重要的数据分析工具，聚类的重要作用被广泛认可。当前有关聚类分析的研究推陈出新，多种聚类方法被提出，查阅现有的相关文献可以发现，尽管每个研究人员所用到的技术不同，但各个研究背景重叠交叉，缺少一种判断准则对这些方法进行归类总结。以往聚类方法在处理局部和非线性数据模式时有很大的局限性，研究人员对于该问题经过不断分析并提出基于图的聚类算法。该算法是在图划分理论基础上，可以对各种不同形状的聚类图识别，在各个方面广泛运用，基于图的聚类方法中谱聚类方法运用最多，但易受到噪声和异常值的影响。为了弥补这一不足，本文研究将设计出一种基于噪声移除的图聚类算法。1.2国内外研究现状下列是国外专家学者研究聚类算法的主要内容：(1)提出有关聚类算法的多种最具代表性的算法，算法在应用时依据各种结构将一个数据集分为多个不同簇。(2)提出层次式聚类算法，该算法基于基本原则多次合并，即可获得结构图。(3)提出基于密度聚类算法，此类算法可以划分低密度与高密度两个不同区域。以上的两种基于层次的聚类算法和基于密度的聚类算法将在本文第二章详细介绍。我国专家学者研究聚类算法取得的成果：(1)郑浩原等人对聚类算法改进，挖掘网络社区时使用层次聚类算法，要对每个点间的相似性求解，在分析角色时引入ego(中心节点）处理。(2)重点研究网络簇结构，基于此结构制定一个多个粒子群组成的聚类网络簇结构法，该算法在使用时是将一个粒子群优化运用实现。(3)传统聚类算法在处理时对于噪声敏感性较差，难以找到其中主要噪声源，导致达到的结果受到噪声干扰不精准。对于该问题提出一个k-中心点算法（K-Medidos算法），该算法充分运用蜂群算法理念，利用对步长调节的方式增强聚类算法精度，使得本算法运行非常稳定。1.3论文主要研究内容本文主要研究图聚类算法，并设计实现基于噪声去除的图聚类算法，该算法首先构建图，本文利用自然邻居的概念构造自然邻居图，因为基于自然近邻稳定结构的自然邻居图的整个计算过程可以在没有任何参数的情况下自动完成。其次是对基于噪声移除的图聚类算法的研究，对于噪声的移除本文使用的是改进的FCM算法，该算法对数据做统计峰值检测，通过数据领域平滑来去除噪声。将FCM算法和自然邻居图结合起来，可以减少时间复杂度，避免参数的影响并且可以去除噪声，使聚类的结果更加准确。2相关理论概述2.1图论图论涉及的理论知识、内容较多，如今计算水平的快速发展，图论与数学理论相结合，使得图论成为人们生产生活的主要技术之一，用来对网络间的关系分析。通常网络可看作多个节点以某种固定方式相互连接形成的图，以点对网络上的不同节点表示，利用连接点的边对网络上各节点间的关系进行表示。如今人们的思维模式发生变化，图论在各个领域全面应用，将图作为工具可精准、迅速的处理问题。同时在交通运输、管理、计算机科学、社交科学等多个方面均体现出图论的价值。2.1.1图的基本概念图分为有向图和无向图，以(V,E)有序二元组进行表示，E与V分别为图的边、顶点。定义图为G=(V,E)，e=(u,v)一条边表示顶点u与e，两点相互关联，可表示u,v是e上的端点，而u,v为相邻点。若e有方向，将其称之为有向边，相反是无向边。图G上若一条边关联的两个顶点是重合的则会形成一个环，如果图G没有环，将其称作简单图。顶点的度用于对顶点v边的数量表示，即d(v)，在实际问题中，如果图上的边均设定一个有关的数，考虑两地间最短距离的问题，这时需要引入赋权图。w(e)表为边e的权，即可由G=(V,E,w)来表示赋权图，假如使用W、E点对一个城市表示，而边是连接各城市间的通信线路，在该城市构建一个通信网络，根据连线上的权对线路信息流量与长度直观反映。图2-1无向无权图和有向有权图2.1.2图的邻接矩阵令G=(V,E)为一个无向图，V的取值区间为[V1,V2,...,VN]。顶点I与J间的边数由A[I,J]直接表示。G邻接矩阵的基本性质如下，该矩阵属于n阶方阵，对其综合分析即可获得，下图2-2为邻接矩阵，图2-3为基于网络结构的邻接矩阵图。图邻接矩阵: （2-1） （2-2）上述公式能够由下图表示：图2-2图表示邻接矩阵网络的邻接矩阵： （2-3）其中Wij为权值，的表示允许范围内大于权值的数。 （2-4）上述公式可由下图表示： 图2-3网络表示邻接矩阵2.1.3自然邻居图将数据集表示为图对于聚类局部和非线性模式很有用。从给定的数据集构造图有许多方法:完全连通图、ε-连通图和k-最近邻图。在完全连通图中，任意两点之间都有一条边，所有边的权值都是用高斯核函数统一计算的。然而，这种方法不仅增加了时间复杂度，而且需要人工确定高斯核的方差参数δ。ε-连通图连接成对距离小于ε的所有点。显然，合适的ε值很难确定。k-最近邻图，若一个对象是另外对象的最近邻集，需要在该对象间建立一条边，然而，k必须手动确定。考虑到以上方法的不足，本次研究将利用自然邻居的概念构造自然邻居图。自然邻居稳定结构是一个来自客观现实的新概念，它受到人类社会人际关系的启发，即一个人真正的朋友的数量应该是把他/她作为朋友并同时被他/她视为朋友的人数。自然邻居稳定结构的关键思想是位于稀疏区域的物体具有低能量，而位于密集区域的物体具有高能量。基于以上陈述，数据对象的自然邻居稳定结构可以表述如下:(∀xi)(∃xj)(k∈N)∧(i=j)→(xi∈NNk(xj))∧(xj∈NNk(xi))其中NNk(xi)是物体xi的第k个最近邻居。xi点的k个最近邻是D中d(xi，x)≤d(xi，o)的一组点x。自然邻居稳定结构的形成是这样实现的:不断扩大邻居搜索范围k，同时计算每个对象的反向邻居数。迭代的停止标准是所有对象均存在反向邻居，这时k搜索区间是自然邻居上的λ特征值。对于每个对象x，自然邻居是k个最近的邻居，k等于自然特征λ，表示为NaN(x)。自然近邻不同于传统的k近邻，自然近邻稳定结构的整个计算过程可以在没有任何参数的情况下自动完成。2.2聚类概述聚类基于一定标准分割一个完整的数据集为多个簇或者类，导致相同簇中的数据对象存在较大相似性，且未在相同簇内的对象之间也具有较大差别，也就是最大限度的聚集经过聚类操作后的相同类型数据，分离类型不同的数据。聚类是机器学习中的一种无监督学习方法。2.2.1聚类分析近几年数据挖掘中应用较多的算法为聚类分析，也受到社会各界的广泛关注，推动聚类分析在各个领域广泛应用，如今主要在地理学、模式识别、机器学习、研究气候等方面运用聚类分析方法。运用以往的聚类算法聚类研究多维、离散及多种类型的数据，取得的效果不尽人意，而马氏距离、欧式距离算法，或者对各点簇间距离计算的方式，经过计算取得的结果均会造成聚类结果出现一定偏差。由于传统聚类算法存在缺陷，在聚类分析离散数据时应用最多的分析方式为基于图的聚类算法。2.2.2主要聚类方法聚类分析的研究有很长的历史，形成多种计算方式，常见的有基于层次、基于划分、及基于密度等多种聚类方法。1、基于划分的聚类方法基于划分的聚类方式在应用时要结合目标函数将全部数据分为一个聚类数量固定的分组，目前应用最多是的K均值聚类算法，简称K-means算法，该算法操作简单、高效成为各领域应用的首选REF_Ref13775\r\h[7]。但是K-means算法有两个致命的缺陷。首先，集群的数量需要提前手动确定。第二，由于初始聚类中心是随机选择的，很容易陷入局部最优解。2、基于层次的聚类方法基于层次的聚类方法是以数据集分解成树为主要的研究形式，该方法中的数据点采用节点进行表示的，其中的叶子节点是数据点，采用相似的程度对中间节点进行表示，将不相同的层次数分割，实现理想的聚类效果，该方法为聚类结构进行了直观的展示。根据该算法运用树结构有效处理数据集，并将一个聚类保存在叶节点，以半径与中心进行直接表示，并依照一定次序对全部对象处理，将其划分到距离最短的节点上，此类算法可当作其他聚类算法上的预处理流程，然而也存在不足之处，主要是得到的高维数据具有不理想的特征效果，同时有较高的时间复杂性。3、基于密度的聚类方法基于密度的聚类方法在各种算法中最典型，算法中数据点与其最近的邻居聚集在一起，孤立在低密度区域的数据点被称为离群点。典型的基于密度的聚类方法DBSCAN算法虽然可以检测任意形状的聚类和离群点，但DBSCAN的性能取决于用户确定的扫描半径Eps和密度阈值MinPts。3基于图聚类的FCM算法1981年Bezdek与Dunn两位学者第一次提出模糊C均值聚类算法，即FCM算法，本算法正式发布后专家学者争相研究，也获得诸多显著成果，如今在数据挖掘等领域中应用较多。3.1FCM算法概述通过量模拟聚类的理念引入C均值算法在改进后形成模糊C均值算法，即FCM算法，本方法可将C均值算法的数据硬性划分转化柔性的模糊划分。FCM算法运行期间会缩短各聚类数据间的相似性，一直到目标函数达到条件后停止。FCM算法可以更好的处理像素分类准确性差问题，在市场上应用较多，然而初始化聚类中心会直接影响聚类效果。3.1.1FCM算法的实现步骤本文研究先将数据集xj(j=1,2,...,n)划分为子集Gi(i=1,2,...,c)，并计算聚类中心c，依据相似性准则对子集再次划分，经过多次操作与划分后得到一个非相似性指标的目标函数，该目标函数达到最小值则算法停止。下列公式(3-1)计算目标函数。 （3-1）FCM算法的一般步骤为：

第一步：确定分类数，确定迭代次数；

第二步：初始化一个隶属度（和为1）；

第三步：根据隶属度计算聚类中心；

第四步：计算目标函数；

第五步：根据求出的聚类中心返回去计算隶属度，回到第三步，一直循环直到求得的目标函数达到最小值。FCM算法应用时并非一次就可以实现，要经过多次迭代与重复运行后才能得到想要的结果，但是该方法难以确保获得的结果即为最优解，同时所选的c初始聚类中心也会影响最后算法的性能与结果，因而要多次对比运算才能取得较为理想的运算结果，选用效果理想的值当作聚类中心。3.1.2隶属度函数概述隶属度函数可以对对象x隶属于集合A实际状态反映，也是一种表现真实程度的函数，即A(x)，集合A上的所有对象均属于自变量，其取值区间为[0,1]，0≤U（X）≤I。A(x)隶属度结果十分趋近于1的情况下，x是集合A中内容的隶属度更高。A(x)隶属度值逐渐趋于0，表达的意思是x是集合A内容的可能性越小。针对有限元对象(x1,x2,...,xn)，模糊集合可以表示为式（3-2）所示。 （3-2）在式(3-3)中，多次迭代运算之后成功划分聚类。[0,1]区间内的值，一个元素x作为集合A上的元素的非硬性规定，聚类过程中元素x经过多次计算后会向隶属度较高的模糊集合上划分，计算得出的全部样本元素x存于集合A的隶属度，究其根本是x的取值范围。在本次研究中，用值在[0,1]区间内的随机数初始化隶属矩阵，使其满足条件和为1。3.2算法对噪声的处理对于模糊聚类算法来说，对各数据簇中心拉扯力较大的是离群的噪声点，它们会使得各数据簇中心发生偏移。在现有的模糊聚类算法研究中，很多聚类算法都是利用对隶属度约束条件的放宽，去达到该目标。实际情况下针对噪声界定属于无监督学习领域的重大难题，该情况下的样本点无标签信息，仅仅能经过其间距来判断样本点间的关联性。若某个样本点附近有大量的邻近样本点存在时，可以识别出其与附近的样本点具有一定的相似性。当这一样本点被当作噪声，则附近样本点也会被当作噪声。而运用聚类算法，那么这群样本点就会形成新的数据簇，在算法中这群样本点就不会被当作噪声，造成了数据集中部分信息的缺失，综上所述模糊的聚类算法在解决这类问题上主要时降低数据簇的隶属度值，进而将这些噪声数据的影响降低。本次研究通过计算数据集中样本点之间的距离，为噪声点分配较低的隶属度，在自然邻居图中将低隶属度的样本点视为噪声点，把噪声点和连接到该点的边都从自然邻居图中移除以达到检测和去除噪声的目的。下列为带有噪声去除的FCM算法基本流程:第一步:在初始聚类中心ci上随机选取一个值，i的取值区间为1,,c；第二步:根据自然邻居图用欧式距离算法计算每组数据中的样本点之间的距离，将与其他样本点的距离远大于距离平均值的样本点标为噪声样本点；第三步:初始化隶属度矩阵U，为噪声点分配最低的隶属度值，基于该矩阵重新分列数据；第四步:从自然邻居图中把噪声点和连接到该点的边移除；第五步:求出精准的目标函数，假如取得的结果显示收敛需要停止使用本方法；第六步:使用同一个聚类中的数据加权均值作为本次求解的聚类中心，明确后即可跳转到以上第二步。4基于MATLAB的图聚类算法仿真模拟4.1基于MATLAB的图聚类算法仿真Matlab的图聚类算法具有工作和编程效率高，其作为目前一种先进的计算语言，能够实现数学形式的编程。在这些优点的基础之上，Matlab有着高效的编写速度和很好的工作效率。同时对于用户也有着较好的使用体验，其中的库函数和用户信息具有一致性，使得用户文件可以很方便的被调用。本次仿真的实验环境是MatlabR2016a。实验数据是如图所示的加噪声数据和不含噪声数据：图4-1实验数据算法流程图如下：数据载入数据载入转化成自然邻居图完成数据切割与噪声的去除图聚类算法处理结果分析图4-2图聚类算法流程图数据经过自然邻居图的转化，然后进行数据分割，产生的图像再经过图聚类算法的处理，最终完成数据分析。4.2仿真结果图4-3原始数据加载图4-4形成自然邻居图图4-5进行数据切割前设置参数不同的数据切割参数得出的切割结果是不同的，这里选择的参数为0.1和0.2。图4-6数据切割参数0.1结果图4-7切割参数为0.2时的结果图4-8无噪声数据的图聚类结果图4-9有噪声数据的图聚类结果总结与展望通过对实验结果的分析，我们可以得出：聚类分析效果可得，本算法再多次合并、删除聚类中心数据后，保留聚类中心上关联像素数量较多的部分，且该聚类中心大部分来源于像素灰度值非常集中的区域，导致此后图像分割期间出现各种误分割、噪声点数量较多等问题，造成许多与特征值相应的像素难以在同一个区域划分，同时严重影响图像成像效果、灰度值集中度较高的区域也无最佳的聚类中心。但是对于对比度较高的噪声还是有明显的滤除效果。参考文献贺贵明，吴元保，蔡朝晖.基于内容的视频编码与传输控制技术[M].武汉大学出版社，2005.侯叶.基于图论的图像分割技术研究[D].西安电子科技大学，2011.林瑶，田捷.医学图像分割方法综述[J].模式识别与人工智能，2002,15(2):192一204.秦蝉蝉.基于随机游走算法的图像分割方法研究[D].华中师范大学，2014.AzzouzEE,NandiAK.Automaticidentificationofdigitalmodulationtypes[J].SignalProcessing,1995,47:55-69.NandiAK,AzzouzEE.Automaticanaloguemodulationrecognition[J].SignalProcessing,1995,46:211-222.叶敏超，钱沄涛，沈言浩.基于聚类的图像稀疏去噪方法[J].信号处理,2011(10):1593-1598.袁小军，周涛，李琛.基于稀疏先验的非局域聚类图像去噪算法研究[J].计算机工程与应用,2020,56(18):177-186.NazliTekin，VehbiCagriGungor，Theimpactoferrorcontrolschemesonlifetimeofenergyharvestingwirelesssensornetworksinindustrialenvironments，P198-113，2010.TheodoreS.Rappaport.Wirelesscommunicationsprinciplesandpractice[M].Beijing:PublishingHouseofElectronicsIndustry.1998.张忠培，魏宁，史治平编著.协同无线通信导论[M].北京:电子工业出版社，20-31.SendonarisA.,ErkipE.,andAazhangB.,Usercooperationdiversity-partI:Systemdescription[J],IEEETransactionsCo