模糊聚类算法（FCM）
- 格式：pdf
- 大小：184.54 KB
- 文档页数：5
模糊聚类算法（FCM）
伴随着模糊集理论的形成、发展和深化，RusPini率先提出模糊划分的概念。以此为起点和基础，模糊聚类理论和⽅法迅速蓬勃发展起来。
针对不同的应⽤，⼈们提出了很多模糊聚类算法，⽐较典型的有基于相似性关系和模糊关系的⽅法、基于模糊等价关系的传递闭包⽅法、基
于模糊图论的最⼤⽀撑树⽅法，以及基于数据集的凸分解、动态规划和难以辨别关系等⽅法。然⽽，上述⽅法均不能适⽤于⼤数据量的情
况，难以满⾜实时性要求较⾼的场合，因此实际应⽤并不⼴泛。
模糊聚类分析按照聚类过程的不同⼤致可以分为三⼤类：
(1)基于模糊关系的分类法：其中包括谱系聚类算法(⼜称系统聚类法)、基于等价关系的聚类算法、基于相似关系的聚类算法和图论聚类算法
等等。它是研究⽐较早的⼀种⽅法，但是由于它不能适⽤于⼤数据量的情况，所以在实际中的应⽤并不⼴泛。
(2)基于⽬标函数的模糊聚类算法：该⽅法把聚类分析归结成⼀个带约束的⾮线性规划问题，通过优化求解获得数据集的最优模糊划分和聚
类。该⽅法设计简单、解决问题的范围⼴，还可以转化为优化问题⽽借助经典数学的⾮线性规划理论求解，并易于计算机实现。因此，随着
计算机的应⽤和发展，基于⽬标函数的模糊聚类算法成为新的研究热点。
(3)基于神经⽹络的模糊聚类算法：它是兴起⽐较晚的⼀种算法，主要是采⽤竞争学习算法来指导⽹络的聚类过程。
在介绍算法之前，先介绍下模糊集合的知识。
HCM聚类算法
⾸先说明⾪属度函数的概念。⾪属度函数是表⽰⼀个对象x ⾪属于集合A 的程度的函数，通常记做µA(x)，其⾃变量范围是所有可能属于
集合A 的对象（即集合A 所在空间中的所有点），取值范围是[0,1]，即0<=µA(x)，µA(x)<=1。µA(x)=1 表⽰x 完全⾪属于集合A，相当于传统
集合概念上的x∈A。⼀个定义在空间X={x}上的⾪属度函数就定义了⼀个模糊集合A，或者叫定义在论域X={x}上的模糊⼦集A’。对于有限个
对象x1，x2，……，xn 模糊集合A’可以表⽰为：
有了模糊集合的概念，⼀个元素⾪属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类⽣成的簇看成模糊集合，因此，每个样
本点⾪属于簇的⾪属度就是[0，1]区间⾥⾯的值。
再接下来要讲FCM算法不得不先讲⼀下HCM算法
硬C-均值(HCM)算法是实现数据集J硬C划分的经典算法之⼀，也是最受欢迎的算法之⼀。它能够把数据集X分成C个超椭球结构的聚类。
HCM算法把传统的聚类问题归结为如下的⾮线性数学规划问题：
其中U=(uij)cxn为硬C-划分矩阵，V=(v1，v2，，，vc)为C个聚类中⼼，||·||代码欧式距离。
HCM算法的具体流程如下：
初始化：指定聚类类别数C，2<=C<=n，n是数据个数，设定迭代停⽌阈值Ɛ，初始化聚类中⼼V0，设置迭代计数器b=0；
步骤⼀：根据下⾯的公式计算或更新划分矩阵U
步骤⼆：根据下⾯公式更新聚类中⼼V（b+1）
步骤三：如果||Vb – V(b+1)||< Ɛ，则算法停⽌并输出划分矩阵和聚类中⼼V，否则令b=b+1，转向执⾏步骤⼀
FCM聚类算法
Dunn按照RusPini定义的模糊划分的概念，把HCM算法扩展到模糊划分领域。Dunn对每个样本与每个聚类中⼼的距离⽤其⾪属度平⽅加
权，从⽽把类内误差平⽅和⽬标函数J1扩展为类内加权误差平⽅和函数J2：
Bezdek⼜将Dunn的⽬标函数推⼴为更普遍的形式，给出了基于⽬标函数的模糊聚类更⼀般的描述。
其中，m∈[1,+∞)称为加权指数，⼜称作平滑参数。尽管从数学⾓度看，m的出现不⾃然，但如果不对⾪属度加权，从HCM算法到FCM算法
的推⼴将是⽆效的。
FCM算法的具体流程如下：
初始化：指定聚类类别数C，2<=C<=n，n是数据个数，设定迭代停⽌阈值Ɛ，初始化聚类中⼼V0，设置迭代计数器b=0；
步骤⼀：根据下⾯的公式计算或更新划分矩阵U步骤⼆：根据下⾯公式更新聚类中⼼V（b+1）
步骤三：如果||Vb – V(b+1)||< Ɛ，则算法停⽌并输出划分矩阵和聚类中⼼V，否则令b=b+1，转向执⾏步骤⼀
FCM算法流程图
FCM算法是⽬前⽐较流⾏的⼀种模糊聚类算法，究其原因⼤致有以下⼏个⽅⾯：⾸先，模糊C—均值泛函Jm仍是传统硬C⼀均值泛函J1的⾃
然推⼴；硬C⼀均值泛函J1是⼀个应⽤⼗分⼴泛的聚类准则，对其在理论上的研究⼰经相当完善，这就为Jm的研究提供了良好的条件；数学
上看，Jm与RS的希尔伯特空间结构(正交投影和均⽅逼近理论)有密切的关系，因此⽐其它泛函有更深厚的数学基础；最后，也是最重要的是
该⽬标函数不仅在许多领域获得了⾮常成功的应⽤，⽽且以FCM算法为基础，⼈们提出的基于其它原型的模糊聚类算法，形成了⼀⼤批
FCM类型的算法：如模糊C⼀线(FCL)、模糊C⼀⾯(FCP)等聚类算法，分别实现了对呈线状、超平⾯状结构模式⼦集(或聚类)的检测。
FCM算法应⽤到颜⾊迁移中
钱⼩燕等⼈将聚类算法应⽤到⾊彩迁移中，提出了⼀种基于图像模糊颜⾊聚类的⾃适应⾊彩迁移算法。该算法⾸先将源图像和⽬标图像
分别转换到lαβ颜⾊空间：利⽤FCM 算法把源图像和⽬标图像划分为具有不同颜⾊特征的聚类，然后分析图像中的颜⾊特征：分别算出每个
域的匹配权值，对每个⽬标图像的匹配权值，从源图像中选取⼀个最接近域作为最佳匹配域；最后根据⽬标图像各聚类域与源图像中的匹配
域之间的关系，引⼊⾪属度因⼦，两个域的处理结果分别进⾏加权平均，获得⾊彩迁移结果。使⽤FCM的思想对图像进⾏聚类域划分的思路
是：设准备处理图像I的⼤⼩是S×H，即对颜⾊聚类颜⾊分析的个数是N，N = S×H，则图像I可表⽰成集合，I={p1 ,p2 ...,pn }。图像被分
为c类，每个类的聚类中⼼为V={v1,v2 ...,vc }，⽤uik表⽰像素pk⾪属于聚类中⼼Vi的⾪属度，定义图像的⾪属度矩阵U。具体算法如下：
步骤⼀：把源图像和⽬标图像分别从RGB转换到lαβ空间。
步骤⼆：确定待处理图像聚类域个数c，然后初始化聚类中⼼。假设加权指数m=2，设定处理的最⼤迭代次数为50。
步骤三：当迭代次数T ⼩于50 时，根据初始化聚类中⼼计算⾪属度矩阵。如果pk≠vi,则对于所有的vi ( i=1,2,...,C )，利⽤下式计算⾪属度矩
阵。
其中，i =1,2,...C； j =1,2,...N
如果，pk=vi,，k =1,2,...N则
其中，dik为第k个元素到第i 个聚类中⼼的距离，定义在lαβ下的欧式距离。
步骤四：对图像聚类划分。图像的⾪属度矩阵中，从每列选择⾪属度最⼤的点作为相对应点的归属域，并重新计算聚类中⼼。
步骤五：对收敛情况进⾏检查。若||Vi – V’i||
步骤六：对聚类域进⾏匹配。使⽤FCM 后，对每⼀个聚类域分别设置⼀个匹配权值参数w，当⽬标图像是灰度图像时，w为聚类域的亮度均
值；当⽬标图像为彩⾊图像时，w 是聚类域3 个通道标准差的加权平均值。
步骤七：⾊彩迁移。为了保持通⽤性，假定⽬标图像中元素pi的归属域与源图像中聚类域h 是匹配域，利⽤下式获得各个通道的新值：
FCM算法效果图[cpp]
1. BOOL TranFCM(LPBYTE lpDIBBits, LONG lmageWidth, LONG lmageHeight,LPBYTE lpDIBBits2, LONG lmageWidth2, LONG lmageHeight2,LPBYTE lpDIBBits3)
2. {
3. int classnum=2;
4. int m=2;
5. int i,j,k,nindex;
6. double l,a,b;
7. double* belong=new double[lmageWidth*lmageHeight*classnum];
8. double* belong2=new double[lmageWidth2*lmageHeight2*classnum];
9. double* center=new double[classnum*3];
10. double* center2=new double[classnum*3];
11. int* clustermap=new int[classnum];
12. double suml,suma,sumb;
13. FCMCluster(lpDIBBits,lmageWidth,lmageHeight,belong,center,classnum,m);
14. FCMCluster(lpDIBBits2,lmageWidth2,lmageHeight2,belong2,center2,classnum,m);
15.
16. double* vl=new double[classnum];
17. double* va=new double[classnum];
18. double* vb=new double[classnum];
19. double* vl2=new double[classnum];
20. double* va2=new double[classnum];
21. double* vb2=new double[classnum];
22. for(i=0;i
23. {
24. BYTE distance=255;
25. int map=-1;
26. BYTE r,g,b,r2,g2,b2;
27. for(j=0;j
28. {
29. LabToRgb(center[i*3+0],center[i*3+1],center[i*3+2],r,g,b);
30. LabToRgb(center2[j*3+0],center2[j*3+1],center2[j*3+2],r2,g2,b2);
31. BYTE dis=abs(RgbToGray(r,g,b)-RgbToGray(r2,g2,b2));
32. if (distance>dis) {distance=dis;map=j;}
33. }
34. clustermap[i]=map;
35. }
36. //TranColor(belong,belong2,center,center2);
37. //求各聚类域的标准差
38.
39. //求结果图像的lab
40. for(j = 0;j
41. {
42. for(i = 0; i
43. {
44. nindex=((lmageHeight-j-1)*lmageWidth+i);
45. suml=suma=sumb=0;
46. RgbToLab(lpDIBBits[nindex*3+2],lpDIBBits[nindex*3+1],lpDIBBits[nindex*3+0],l,a,b);
47. for(k=0;k
48. {
49. suml += belong[lmageWidth*lmageHeight*k+nindex]*center2[clustermap[k]*3+0];
50. suma += belong[lmageWidth*lmageHeight*k+nindex]*center2[clustermap[k]*3+1];
