基于谱分解的冗余模糊C均值聚类算法

1、基于谱分解的冗余模糊C均值聚类算法在图像粗大项目来源：研究生创新基金 作者简介：白俊（1992-），男，主要研究方向：机器学习。轮廓提取中的应用白 俊（武汉纺织大学 数学与计算机学院）摘要：本文对传统的模糊C均值聚类算法（FCM)进行了改进，根据类间分离度和类内紧缩度实现了对样本特征的加权，提升了FCM算法的聚类性能；通过引入冗余聚类的思想，突破了FCM算法对“凸”形数据集聚类的限制；采用贴近度来表征冗余类之间的特征，通过对贴近度的谱分解，选取了合适的谱特征再次采用FCM算法来完成冗余类的合并。图像粗大轮廓的提取是图像处理研究领域的一个重要中间环节，针对基于区域边缘检测的图像轮廓提取原理，本文

2、首次采用基于谱分解的冗余FCM算法完成了对图像区域的分割，进而运用Canny边缘算子提取到图像的粗大轮廓。通过实验表明，本文算法能够较好的去除一般边缘算法检测到的伪边缘和弱边缘，提取到图像目标的粗大轮廓。关键词：模糊C均值聚类算法(FCM)；冗余聚类；谱分解；粗大轮廓提取0 引言图像的边缘像素是指局部图像范围内灰度急剧变化的奇异点，在图像中表现为图像的非连续性，而粗大轮廓为图像中不同材质所形成的显著边缘，即图像中对象间的显著边缘特征，描述了图像中显著的轮廓信息。目标图像的粗大轮廓包含了目标的形状、方位等众多信息，是图像处理和模式识别的重要中间环节。早期文献1就提出了一种基于图像轮廓提取的模板匹

3、配算法，并应用于机器人视觉技术中；文献2提出了基于蚁群模糊聚类算法的粗大轮廓提取方法，接着文献3又提出了基于核空间的PFCM聚类算法的粗大边缘提取方法，并都较好的应用于异源图像的匹配中；文献4基于力场转换理论对灰度值分布集中且噪声较大的红外（IR）图像进行了粗大边缘的检测，并应用于导航制导领域。本文基于粗大轮廓提取的原理，并在前人的基础上将改进的基于谱分解的冗余模糊C均值聚类算法应用到图像粗大轮廓的提取中，通过运用改进的FCM算法对反应图像目标主轮廓的特征信息聚类，实现图像的分割，并利用边缘检测Canny算子对分割后的区域图像进行了图像粗大轮廓的提取。接下来部分将按照如下安排：第一部分将详细介

4、绍改进的基于谱分解的冗余模糊C均值聚类算法的原理及实现步骤；第二部分给出了实验测试结果及分析；第三部分对全文做出了总结，并给出了将来研究的方向。1 基于谱分解的冗余模糊C均值聚类算法1.1 聚类分析 聚类分析是数据挖掘的一种重要方法，它们根据“物以类聚”的道理，对样本数据进行分类的一种 HYPERLINK /w/index.php?title=%E5%A4%9A%E5%85%83%E7%BB%9F%E8%AE%A1%E5%88%86%E6%9E%90&action=edit o 多元统计分析 多元统计分析方法，要求能合理地按各自的特性来对大量的样本进行合理的分类，没有任何模式可供参考。虽然聚类

5、也可起到分类的作用，但和大多数分类不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中，确定事物的分类准则或各类别的标准或多或少带有主观色彩。聚类分析的目标就是在相似的基础上对一个给定的数据集进行划分，这种划分应满足以下两个特性：（1）类内相似性：属于同一类的数据应尽可能相似。（2）类间相异性：属于不同类的数据应尽可能相异。图1是一个简单聚类分析的例子。 图1 聚类分析的简单图例聚类分析实现的一般步骤为：（1）选择聚类的某种方法，例如最短距离法；（2）选择度量距离，比如欧氏距离，并计算出初始距离矩阵

6、；（3）在距离矩阵中找出最小数，并把此数所在行的类与所在列的类归为一类，得到新的一类。（4）计算新的一类与其他旧的几类的距离，把距离最短的再归为一类，形成新类，依次继续下去，直到把所有的样本归为一类，然后根据需要，再选取分类结果。1.2 模糊C均值聚类算法（FCM）在模糊聚类算法中最常见的是模糊C均值聚类算法（FCM）5，模糊C均值算法是普通C均值算法的改进，普通C均值算法对于数据的划分是硬性的，而FCM则是一种柔性的模糊划分。在FCM中，每个待分配的数据对象并不完全属于某个特定的类，而是对某个特定的类有个隶属程度，这更符合实际应用。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善

7、、应用最为广泛的一种算法，FCM 算法把聚类归结为一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。其基本思想是通过反复修改聚类中心V和分类矩阵U来实现动态的迭代聚类，使得被划分到同一类的对象之间相似度最大，而不同类之间的相似度最小。让X是一个N个数据对象的集合，每个数据对象是一个P维特征矢量，其中。N个特征矢量的集合就可以被看做是一个PxN数据矩阵。模糊聚类算法将数据X划分进C模糊类，在X中形成一个模糊划分。一个模糊划分可以方便的用一个矩阵U来表示，其中U中的元素表示数据对象对于类j的相关度。因此，U中的第j行包含着在模糊划分中第j个从属函数的值。模糊C均值算法基于下边目标

8、函数的最小化，对于U即一个数据集合的模糊C划分，对于V即一个C个聚类中心的集合： ， （1） 其中是一个P维的聚类中心，是决定群模糊性的一个模糊索引，是任一个内部乘积度量（和之间的距离）。为了避免平凡解，U必须满足下面的约束： 和 （2）模糊聚类通过方程（1）的一个迭代最优化来实现，的值越小说明聚类的效果越好。联合方程（1）和（2），利用拉格朗日乘数法可解得： （3） （4）FCM聚类算法的实现过程如下：Step1: 设置最大迭代次数和划分精度；Step2: 初始化聚类中心，j=1,.,C；Step3: 根据公式（3）计算划分矩阵U；Step4: 根据公式（4）计算聚类中心；Step5: 根据

9、公式（3）更新相关度为，如果或迭代次数t则停止，否则转向步骤4，t-t+1,其中是一个终止条件。1.3 改进的模糊C均值聚类算法1.3.1 基于类间分离度和类内紧缩的特征加权FCM算法传统的FCM算法对于原始样本特征数据是平等对待的，即它们对于最终的聚类原型的贡献作用是一样的，但现实的样本数据必定对于聚类原型有远有近，特别是对于样本特征维数很高的情况下，对于对每维特征加以区别对待，以此来提高传统的FCM算法的分类性能。为此我们从两方面来考虑对样本特征的加权。类间分离度特征贡献平衡原则:基于一般的分类方法，各个特征对分类的贡献基本上是同等重要的;若某个特征比其它特征贡献大，则需要对原始数据处理，

10、将这种不平衡性改造，使改造后的特征平衡。由于样本特征的每维特征采用的统计单位不一样，其大小对应了样本在该方面的特点，我们首先根据特征平衡原则，让每维特征对于分类的贡献作用基本保持平等，需要为每维特征添加一个平衡系数。假设粗分类的c个聚类中中心为,其中，设平衡系数为，则可由式（5）计算得来： （5）类间分离度最大原则:对类间分离度贡献的大小体现了各个特征的差异性，对分离度贡献越大，则权重应越大，从而得到新的类间分离度越大，可分性就越强。在数理统计中，标准差代表了数据的集中和分散程度，为此我们可以根据聚类原型的标准差来衡量类间的分离度，其计算公式如下： （6）综上所述，我们可以按照如下步骤来得到加

11、权系数：首先用传统的FCM算法得到初始聚类中心，然后对初始聚类中心各维特征进行归一化得到各维特征的平衡系数r，再求出归一化后的类间分离度，从而求出特征加权为： （7）类内紧缩度一般情况下聚类中心出现在样本密集区域的概率较大，所以我们采用点密度加权来衡量类内紧缩度。点密度度量的方法很多，本文采用样本点与数据集中所有其他样本点之间的贴近度的和来表示该点的密度，根据文献6我们建立了相似相近贴进度来度量样本点的密度，对于样本X、Y的相似相近的贴近度为： （8）式中，、分别为样本X、Y的特征。采用式计算每个样本之间的相似相近贴近度，便可到基于贴近度的相关矩阵，并求出相关矩阵各列的和作为每个样本的点密度权

12、重。综合（1）和（2），我们可以得到基于类间分离度和类内紧缩度的特征加权FCM算法，加权后的目标函数如下： （9）在约束条件下，采用拉格朗日乘子法，可以得到： （10） （11）1.3.2 基于普分解的冗余FCM算法传统的FCM算法只能对“凸”形数据样本进行分类，对于“非凸”分布的分类效果就不佳，且对初始聚类中心的选取比较敏感，需要预先确定聚类数目。针对这些问题，我们可以先将待分样本采用FCM算法分割为许多小类（冗余类）7，然后再将分类问题转化为冗余类的合并问题。因为每个冗余类含有样本相对数量少，所以其分类数对于最后的分类影响不大，这样我们也可以不用考虑数据分布是否为“凸”形分布的问题。接下来

13、就是冗余类的合并问题，冗余类的合并需要依据表征各冗余类的特征，本文采用所有样本隶属于某个冗余类的隶属度值作为该冗余类的特征值，根据类间分离度和类内紧缩度原则计算出冗余类之间的贴近度矩阵，以此来表征各冗余类之间的远近程度。为了简化冗余类的表征特征，我们引入了基于图论的谱分析，将冗余类之间的贴近度矩阵作为谱分析的相似矩阵，为此我们采用下式构建了Laplacian矩阵： （12）式中，为贴近度矩阵，为对角矩阵，其中，然后对Laplacian矩阵进行奇异值分解，选取合适的特征向量作为谱特征，再次采用FCM算法对选取的普特征进行聚类来完成对冗余类的合并。基于谱分解的冗余FCM算法步骤如下：Step1:初

14、始化冗余聚类中心数(默认值选取或),模糊因子m和迭代终止条件；Step2:采用FCM算法对原始数据集进行冗余聚类，得到数据集的冗余划分；Step3:将冗余聚类得到的隶属度划分矩阵的每一行作为各冗余类的类特征，采用式（8）计算得到相似相近性贴近度矩阵;Step4:将贴近度矩阵作为谱分解的相似矩阵，利用式（12）建立Laplacian举证，并对进行谱分解得到谱特征；Step5:对谱特征进行选取（一般选取的第二小特征值对应的特征向量），得到新的特征，然后再次采用FCM算法进行聚类，得到冗余类的合并，进而完成对数据样本的分类。2 实验与分析对于图像中不同材质的对象之间在灰度、对比度、纹理特征等方面都有

15、所不同，因而本实验对图像的每个像素提取了分别反应纹理平均亮度的灰度均值、纹理平均对比度的灰度方差和纹理复杂度的Shannon熵三个纹理特征，其计算公式如式（13）、（14）和（15）： （13） （14） （15）本文选取了经典的Lena图像和Berkely图像库的4幅图像作为实验用图，实验首先根据市（13）（14）（15）建立图像的三维特征空间，然后用本文的改进算法进行聚类分割，得到图像的区域划分，最后用经典的边缘检测Canny算子进行粗大轮廓的提取。同时实验还给出了两种边缘检测算子Canny算子和Sobel算子的边缘检测图作为对比图，如图2所示：r1: r2: r3: r4: r5: 图2

16、 实验结果图，r1、r2、r3、r4和r5行从左到右分别给出了原灰度图像、本文算法分割图、本文算法粗大轮廓提取图、Canny算子边缘检测图和Sobel算子边缘检测图，其中对r1行图像聚类分割类数为2，其余为3从实验结果图来看，本文提出的基于谱分解的冗余模糊C均值聚类提取粗大轮廓的算法相比于传统的边缘检测算子Canny和Sobel算子，能够在去除伪边缘、弱边缘等冗余细小边缘取到较好的效果，最明显的实例就是针对r5图像头发部分粗大轮廓的提取，几乎能够完全消除头发内部的细小边缘，提取完整的头发主轮廓。3 结论本文详细介绍了改进的基于谱分解的冗余模糊C均值聚类算法，并将其成功运用到图像的区域分割中，通

17、过Canny边缘检测算子，较好的提取到了图像目标的粗大轮廓。通过实验发现，一般的边缘检测算子往往能够检测到许多噪声边缘、伪边缘或弱边缘等冗余细小边缘，而本文提出的算法能够在一定程度上消除这些细小边缘，提取到图像目标的粗大轮廓，能够为图像匹配或模式识别等方向研究提供前期的图像处理。通过实验发现，在改进的FCM聚类算法中，表征冗余类特征的贴进度矩阵的选取、谱分解中Laplacian矩阵构造及谱特征的选取都会影响最后的聚类效果，因此怎样在影响最终聚类效果的地方提出一种鲁棒性强且具有泛化的选取准则是今后的研究方向。参考文献1 邓秀娟, 赵亮. 基于图像轮廓提取的模板匹配方法在机器人视觉中的应用J. 机

18、器人技术与应用. 2002, 5:27-29.2 冯东武. 基于粗大轮廓的异源视觉图像匹配技术研究D. 南京：南京航空航天大学. 2013:1-28.3 赵妍. 基于粗大轮廓的异源图像匹配技术研究D. 南京：南京航空航天大学. 2014:15-29.4 曹传东, 徐贵力, 陈欣等. 基于力场转换理论的图像粗大边缘检测方法J. 航空学报, 2011,32(5):891-899.5 Bezdek J C,Hathaway R J.Convergence and theory for fuzzy C-means cluster -ing:counterexamples and repairsj.IEEE Transactions Pattem Analysis and Machine Inteligence,1987,17(5):873-877.6 Tong Xiaojun, Zhang Shemin. Similarity and nearness of fuzzy sets. In: Procceedin