模糊C均值聚类算法的C++实现代码

1、模糊C均值聚类算法的实现研究背景聚类分析是多元统计分析的一种，也是无监督模式识别的一个重要分支，在 模式分类图像处理和模糊规则处理等众多领域中获得最广泛的应用。它把一个 没有类别标记的样本按照某种准则划分为若干子集，使相似的样本尽可能归丁一 类，而把不相似的样本划分到不同的类中。 硬聚类把每个待识别的对象严格的划 分某类中，具有非此即彼的性质，而模糊聚类建立了样本对类别的不确定描述， 更能客观的反应客观世界，从而成为聚类分析的主流。模糊聚类算法是一种基丁函数最优方法的聚类算法，使用微积分计算技术求 最优代价函数，在基丁概率算法的聚类方法中将使用概率密度函数，为此要假定合适的模型，模糊聚类算法的

2、向量可以同时届丁多个聚类，从而摆脱上述问题。模糊聚类分析算法大致可分为三类1） 分类数不定，根据不同要求对事物进行动态聚类，此类方法是基丁模糊等价 矩阵聚类的，称为模糊等价矩阵动态聚类分析法。2）分类数给定，寻找出对事物的最佳分析方案， 此类方法是基丁目标函数聚类 的，称为模糊C均值聚类。3）在摄动有意义的情况下，根据模糊相似矩阵聚类，此类方法称为基丁摄动的 模糊聚类分析法我所学习的是模糊C均值聚类算法，要学习模糊C均值聚类算法要先了解虑 届度的含义，隶届度函数是表示一个对象x隶届丁集合A的程度的函数，通常记 做V a（x），其自变量范围是所有可能届丁集合 A的对象（即集合A所在空间中的 所有

3、点），取值范围是0,1，即0<=卜A（x）<=1。A（x）=1表示x完全隶届丁集合 A,相当丁传统集合概念上的x A。一个定义在空间X=x上的隶届度函数就定 义了一个模糊集合A,或者叫定义在论域X=x上的模糊子集A。对丁有限个对 象x1, x2,，xn模糊集合A可以表示为:A=（七（用,用|为 X（6.1）有了模糊集合的概念，一个元素隶届丁模糊集合就不是硬性的了，在聚类的 问题中，可以把聚类生成的簇看成模糊集合， 因此，每个样本点隶届丁簇的隶届 度就是0 , 1区间里面的值。FC相法需要两个参数一个是聚类数目 C,另一个是参数 m 一般来讲C要 远远小丁聚类样本的总个数，同时要保证

4、 C>1。对丁 m它是一个控制算法的柔 性的参数，如果 m过大，则聚类效果会很次，而如果 m过小则算法会接近HCM 聚类算法。算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵，这个矩阵表 示的是每个样本点届丁每个类的隶届度。根据这个划分矩阵按照模糊集合中的最 大隶届原则就能够确定每个样本点归为哪个类。 聚类中心表示的是每个类的平均 特征，可以认为是这个类的代表点。从算法的推导过程中我们不难看出，算法对丁满足正态分布的数据聚类效果会很好，另外，算法对孤立点是敏感的。聚类算法是一种比较新的技术，基丁曾次的聚类算法文献中最早出现的 Single-Linkage 层次聚类算法是1957年

5、在Lloyd的文章中最早出现的，之后 MacQuee迥立提出了经典的模糊C均值聚类算法，FCMT法中模糊划分的概念最 早起源丁 Ruspini的文章中，但关丁 FCM勺算法的详细的分析与改进则是由 Dunn 和Bezdek完成的。模糊c均值聚类算法因算法简单收敛速度快且能处理大数据集，解决问题范围广，易丁应用计算机实现等特点受到了越来越多人的关注，并应用丁各个领域。算法描述模糊C均值聚类算法的步骤还是比较简单的，模糊C均值聚类（FCM,即众所周知的模糊ISODATA是用隶届度确定每个数据点届丁某个聚类的程度的一种 聚类算法。1973年，Bezdek提出了该算法，作为早期硬 C均值聚类（HCM方

6、法 的一种改进。FC诚巴n个向量Xi （i=1,2，,n ）分为c个模糊组，并求每组的聚类中心， 使得非相似性指标的价值函数达到最小。FC输HCM勺主要区别在丁 FCMffl模糊 划分，使得每个给定数据点用值在0, 1问的隶届度来确定其届丁各个组的程度。 与引入模糊划分相适应，隶届矩阵 U允许有取值在0, 1问的元素。不过，加上 归一化规定，一个数据集的隶届度的和总等丁 1:c- Uj = 1,-j = 1,., n（6.9）i 1那么，FCM勺价值函数（或目标函数）就是式（6.2）的一般化形式：cc nJ（U ,c1,.,cc） =£ JiUdi2 ,（6.10）i Ai A j这

7、里Uij介丁 0, 1间；ci为模糊组I的聚类中心，dij =|c i-Xj|为第I个聚类中 心与第j个数据点问的欧几里德距离；且 m 1,8）是一个加权指数。构造如下新的目标函数，可求得使（6.10）式达到最小值的必要条件:cn(6.11)J(U,c1,.,cc,1,., n) = J(U,c1,.,cc)"(' Uij -1)c nnc=f ('、Uj -1)i d jj 20这里扃,j=1到n,是（6.9 ）式的n个约束式的拉格朗日乘子。对所有输入参量 求导，使式（6.10）达到最小的必要条件为：nmUij Xj(6.12)j 4n mUijj日1(6.13)由

8、上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCMffl下列步骤确定聚类中心Ci和隶届矩阵U1:步骤1:用值在0, 1间的随机数初始化隶届矩阵 U,使其满足式（6.9）中 的约束条件步骤2:用式（6.12）计算c个聚类中心Ci, i=1,c。步骤3:根据式（6.10）计算价值函数。如果它小丁某个确定的阀值，或它 相对上次价值函数值的改变量小丁某个阀值，则算法停止。步骤4:用（6.13 ）计算新的U矩阵。返回步骤2。上述算法也可以先初始化聚类中心，然后再执行迭代过程。由丁不能确保FCM 收敛丁一个最优解。算法的性能依赖丁初始聚类中心。因此，我们要么用另外的快速算

9、法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM模糊c均值聚类算法如下：Reapeat for l=1 2 3Step 1:compute the cluseter prototypes（means）:Pi眼/TVStep 2:compete the distance:(dj*)2- (x* -产)以3 -Pi), i W i W J1 w & w 此Step 3:Update the partition matrix:For 1 < & < /VIf (心)z >0 for all i = l,2,"法=再(应/蜘)Oth

10、erwise= 0 if /*丸 > 0, and E 0,1 withUntil | /- "T)| <算法改进1) 在模糊聚类的目标函数中 Bezdek引入了加权指数 m使Dum的聚类 准则变成m=2时候的特例，从数学上说 m的出现不自然且没有必要， 但如果不给以虑届度乘以权值，那么从硬聚类准则函数到软聚类目标 函数的推广准则是无效的，参数m乂称为平滑因子，控制着模式早模 糊类间的分享程度，因此，要实现模糊 c聚类就要选择一适合的m 然而最佳的m的选取目前还缺乏理论，监管存在一些经验值或经验范 围，但没有面向问题的优选方法，也缺少参数 m的有效性评价准则2) 尽管模糊

11、聚类是一种无监督的分类，但现在的聚类算法却=需要应用 聚类原型的先验条件，否则算法会产生误导，从未破坏算法的无监督 性和自动化。3) 因为模糊聚类目标是非凸的，而模糊C均值聚类算法的计算过程乂是迭代爬山，一次很容易陷入局部极值点，从而得不到最优解或满意解， 同时，大数据量下算法耗时也是困扰人们的一大难题，这2个问题目前还不能得到全面的解决。4) FCM型的聚类算法届于划份方法，对于 1组给定的样本集，不管数 据中有无聚类结构，也不问分类结果是否有效，总把数据划分到C个 子类中，换言之，现有的聚类分析与聚类趋势，以及有效分析是隔离 的分离得。5) FCMM勺聚类算法是针对特征空间中的点集设计的，

12、对于特殊类型的数 据，比如在样本每维特征的赋值不是一个数，而是一个区问。集合和 模糊数时,FCMK型的算法无法直接处理模糊C均值聚类算法存在上述缺点，改进的算法正确率能达到更高。Fcm算法在处理小数据集的时候是有效的，但随着数据容量和维数的增加，迭代 步骤会显著增加，而且在迭代的每一步都要对整个数据集进行操作，无法满 足数据挖掘时的需要。改进算法的思想是首先采用随机抽样的办法， 从数据集中选取多个样本， 对每个样本应用FCMT法，将得到的结果作为初始群体，然后再利用遗传算 法对聚类结果进行优化，选取其中的最优解做为问题的输出，由于采样技术 显著的压缩了问题的规模，而遗传乂可以对结果进行全局最优

13、化处理，因此 在时间性能和聚类质量上都能获得较满意的结果。遗传算法是美国Michigon大学的John Holland研究机器学习时创立的 一种新型的优化算法，它的主要优点是：遗传算法是从一系列点的群体开始 搜索而不是从单个样本点进行搜索，遗传算法利用适应值的相关信息，无需 连续可导或其他辅助信息，遗传算法利用转移概率规则，而非确定性规则进 行迭代，遗传算法搜索过程中，以对群体进行分化以实现并行运算，遗传算 法经过遗传变异和杂交算子的作用， 以保证算法以概率1收敛到全局最优解 一具有较好的全局特性，其次遗传算法占用计算机的内存小，尤其适用计算 复杂的非线性问题。遗传算法的设计部分(1) 种群中

14、个体的确定聚类的关键问题是聚类中心的确定，因此可以选取聚类中心作为种群的个体，由丁共有C个聚类中心，而每个聚类中心是一个 S维的实数 向量，因此每个个体的初始值是一个 c*s维的市届向量。(2) 编码常用的编码方式有二进制与实数编码，由丁二进制编码的方式搜索 能力最强，且交义变异操作简单高效，因此采用二进制的编码方式，同 时防止在进行交义操作时对优良个体造成较大的破坏，在二进制编码的 方式中采用格$码的编码形式。每个染色体含c*s个基因链，每个基因链代表一维的数据，由丁原 始数据中各个届性的取值可能相差很大，因此需首先对数据进行交换以 统一基因链的长度，可以有以下两种变换方式。1扫描整个数据集

15、，确定每维数据的取值范围，然后将其变换到同 一量级，在保留一定有效位的基础上取整，根据有效位的个数动态的计 算出基因链的长度。2对数据进行正规化处理，即将各维数据都变换到相同的区间，可 以算出此时的基因链长度为10。(3) 适应度函数由丁在算法中只使用了聚类中心 V,而未使用虑届矩阵u,因此需要 对FCM聚类算法的目标函数进行改进，以适用算法的要求，和目标函数是等价的，由丁遗传算法的适用度一般取值极大，因此可取上式的倒数作为算法的使用度函数。(4) 初始种群的确定初始种群的一般个体由通过采样后运行 FCM算法得到的结果给出， 另外的一般个体通过随机指定的方法给出，这样既保证了遗传算法在运 算之

16、初就利用背景知识对初始群体的个体进行了优化，使算法能在一个 较好的基础上进行，乂使得个体不至丁过分集中在某一取值空间，保证 了种群的多样性。(5) 遗传操作选择操作采用保持最优的锦标赛法， 锦标赛规模为2,即每次随机取 2个个体，比较其适应度，较大的作为父个体，并保留每代的最优个体 作为下一代，交义方式一般采用单点交义或多点交义法进行，经过试验 表明单点交义效果较好，因此采用单点交义法，同时在交义操作中，应 该对每维数据分开进行，以保证较大的搜索空间和结果的有效性，变异 操作采用基本位变异法。(6) 终止条件的确定遗传算法在以下二种情况下终止a最佳个体保持不变的代数达到设定的阈值b遗传操作以到

17、达给定的最大世代数算法具体步骤如下1确定参数，如聚类个数样本集大小种群规模最大世代数交义概率 和变异概率等。2对数据集进行多次采样并运行 FCMK法，得到初始种群的一般个体, 通过随机制定产生另一半个体。3对数据集进行正规化处理并编码。4计算初始种群中个体的适应度。5对种群进行遗传操作产生下一代，在操作的过程中，应该排除产生的 无效个体。6计算个体的适应度，如果满足终止条件，则算法结束，否则转到5继续在理论上讲进行遗传操作的样本容量越大，聚类的误差越小，由 于采样技术显著压缩了问题规模，而遗传算法乂可以对全局进行最优化 处理，因此改进的算法在时间与性能上都能获得较满意的结果，此算法 利用采样技

18、术来提高算法的运行速度，利用遗传算法对聚类进行优化， 避免陷入局部最优解，在性能上相比于传统的模糊 C均值聚类算法获得 较大提高。算法实现米用VC+4行编写文档的读取#include "data.h"/函数定义double *DataRead(char*name,int row,int col)double *p=new double* row;ifstream infile;infile.open(name,ios:in);for(int i=0;i<row;i+)pi=new doublecol;for(int j=0;j<col;j+)infile>

19、>pij;infile.close();cout<<"成功读取数据文件："<<name<<"!n"return p;/释放内存for(i=0;i<row;i+)(deletepi;deletep;文档的保存#include "data.h"void DataSave(double*data,int row,int col,char*name)(int i,j;ofstream outfile;/打开文件，输出数据outfile.open(name,ios:out);outfile.set

20、f(ios:fixed);outfile.precision(4);for(i=0;i<row;i+)(for(j=0;j<col;j+)(outfile<<dataij<<""outfile<<endl;outfile<<endl<<endl;outfile.close();数据标准化处理#include "data.h"double *Standardize(double *data,int row,int col)(矩阵每列的最大值int i,j;double* a=new d

21、oublecol; /double* b=new doublecol; /矩阵每歹U 的最小值double* c=new doublerow; /矩阵歹U元素for(i=0;i<col;i+)(/取出数据矩阵的各列元素for(j=0;j<row;j+)(cj=Dataji;ai=c0,bi=c0;for(j=0;j<row;j+)(/取出该列的最大值if(cj>ai)(ai=cj;/取出该列的最小值if(cj<bi)(bi=cj;/数据标准化for(i=0;i<row;i+)(for(j=0;j<col;j+)(dataij=(dataij-bj)/(

22、aj-bj);cout<<"完成数据极差标准化处理！n”;deletea;deleteb;deletec;return data;生成样本虑届矩阵#include "data.h"void Initialize(double *u, int k, int row)(int i,j;/初始化样本隶届度矩阵srand(time(0);for(i=0;i<k;i+)(for(j=0;j<row;j+)(uij=(double)rand()/RAND_MAX;/得到一个小于 1 的小数隶届度/rand()函数返回0和RAND_MAX问的一个伪随机数

23、数据归一化处理#include "data.h"void Normalize(double *u,int k,int col)(int i,j;double *sum=new doublecol;/矩阵U的各列元素之和for(j=0;j<col;j+)(double dj=0;for(i=0;i<k;i+)(dj=dj+Uij;sumj=dj;/隶届度各列之和for(i=0;i<k;i+)(for(j=0;j<col;j+)(uij=Uij/sumj;/规一化处理(每列隶届度之和为1)迭代过程#include "data.h"#i

24、nclude "func.h"/ 对模糊C均值进行迭代运算，并返回有效性评价函数的值double Update(double*u,double*data,double*center,introw,int col,int k)(int i,j,t;double *p=NULL;for(i=0;i<k;i+)(for(j=0;j<row;j+)(/模糊指数取2uij=pow(uij,2);/根据隶届度矩阵计算聚类中心p=MatrixMul(u,k,row,data,row,col);for(i=0;i<k;i+)(/计算隶届度矩阵每行之和double si=0

25、;for(j=0;j<row;j+)(si+=uij;for(t=0;t<col;t+)(centerit=pit/si; /类中心/计算各个聚类中心i分别到所有点j的距离矩阵dis(i,j)double* a=new doublecol;/第一个样本点double* b=new doublecol;/第二个样本点double*dis=new double*k; /中心与样本之间距离矩阵for(i=0;i<k;i+)(disi=new doublerow;for(i=0; i<k; i+)(/聚类中心for(t=0; t<col; t+)( at=centerit

26、; /暂存类中心/ 数据样本for(j=0; j<row; j+)(for(t=0; t<col; t+)( bt=datajt;/暂存一样本double d=0;/中心与样本之间距离的计算for(t=0; t<col; t+) ( d+=(at-bt)*(at-bt); /d为一中心与所有样本的距离的平方和disij=sqrt(d);/ 距离/根据距离矩阵计算隶届度矩阵for(i=0;i<k;i+)(for(j=0;j<row;j+)(double temp=0;for(t=0;t<k;t+)(/disij依次除以所在列的各元素，加和；一个类中心和/模糊指

27、数为2.0temp+=pow(disij/distj,2/(2.0-1);/一个元素的距离平方与uij=1/temp;/所有类与该元素距离平方的和的商/计算聚类有效性评价函数double func1=0;for(i=0;i<k;i+)(double func2=0;for(j=0;j<row;j+)(func2+=pow(uij,2.0)*pow(disij,2);func1+=func2;double obj_fcn=1/(1+func1);return obj_fcn;/内存释放deletea;deleteb;for(i=0;i<k;i+)(deletedisi;dele

28、tedis;详细过程#include "data.h"#include "func.h"#include "max.h"/全局变量定义double *Data;/数据矩阵double *Center;/聚类中心矩阵double *U;/样本隶届度矩阵int m;/样本总数int n;/样本届性数int k;/设定的划分类别数int main() (int Lab;/int num;/数据文件标号算法运行次数/ cout<<"模糊C均值聚类算法:"<<endl;3-ASD_12_2.txt;c

29、out<<"1-iris.txt;2-wine.txt;4-ASD_14_2.txt"<<endl;cout<<"请选择数据集：Lab="cin>>Lab;cout<<"设定运行次数:mum="cin>>num;/各次运行结束后的目标函数double* Index=new doublenum;/各次运行结束后的聚类正确率double* R=new double num;/num次运行的平均目标函数及平均正确率 double M_Index=0;double M_R

30、=0;/FCM聚类算法运行num次，并保存记录与结果for(int i=0;i<num;i+)(int j;double epsilon=1e-4;int e=0;int nx=0;/记录连续无改进次数int E200=0;if(i>0)cout<<endl<<endl;cout<<setfill('#')<<setw(10)<<endl;cout<<"第"<<i+1<<"次运行记录:"<<endl;读取数据文件if(L

31、ab=1)m=150;n=4;k=3;Data=DataRead("datasetiris.txt”,m,n);else if(Lab=2)m=178;n=13;k=3;Data=DataRead("datasetwine.txt”,m,n);else if(Lab=3)m=535;n=2;k=12;Data=DataRead("datasetASD_12_2.txt”,m,n);else if(Lab=4)(m=685;n=2;k=14;Data=DataRead("datasetASD_14_2.txt",m,n);/数据极差标准化处理Da

32、ta=Standardize(Data,m,n);/聚类中心及隶届度矩阵，内存分配Center=new double*k;U=new double *k;for(j=0;j<k;j+)(Centerj=new doublen;Uj=new doublem;/隶届度矩阵的初始化Initialize(U, k, m);/对隶届度矩阵进行归一化 Normalize(U,k,m);/历次迭代过程中的目标函数double Objfcn100=0;cout<<"第"<<i+1<<"次运行记录:"<<endl; c

33、out<<"开始迭代过程!"<<endl;cout<<"*"<<endl输出精度为小数点后5位 cout.precision(5);/固定格式cout.setf(ios:fixed);/目标函数连续20代无改进，停止该次聚类迭代过程while(e<20)(nx+;/聚类迭代过程Objfcnnx=Update(U,Data,Center,m,n,k);/统计目标函数连续无改进次数eif(nx>0 && Objfcnnx-Objfcnnx-1<epsilon )(e+;else

34、(e=0;Enx=e;输出结果到文件，保存ofstream outfile（" 运行记录.txt”,ios:app）;outfile<<" 第"<<i+1<<”次运行记录:"<<endl;outfile<<"开始迭代过程!"<<endl;outfile<<H*"<<endl;outfile.precision(5);outfile.setf(ios:fixed);for(int n1=1;n1<=nx;n1+)(cout&l

35、t;<"e"<<setw (2) <<n1<<"="<<setw (2) <<En1<<” Objfcn"<<setw (2) <<n1<<"="<<Objfcnn1<<" n"/保存数据文件outfile<<"e"<<setw (2) <<n1<<"="<<setw (

36、2) <<En1<<” Objfcn"<<setw (2) <<n1<<"="<<Objfcnn1<<" n"cout<<endl;outfile<<endl;outfile.close();/本次运行的最大目标函数Indexi=Objfcnnx;/保存聚类正确率，输出聚类结果：Ri=Result(Lab, U, k, m, i);/内存释放for(j=0;j<k;j+)deleteCenterj;deleteUj;deleteCe

37、nter;deleteU;/统计平均/double temp1=0, temp2=0;for(i=0;i<num;i+)temp1+=Indexi;temp2+=Ri;/计算各次结果的统计平均M_Index=(double)temp1/num;M_R=(double)temp2/num;cout<<"/ /"<<endl;cout<<num<<'次运行，平均聚类正确率：”<<100*M_R<<”<<endl;输出精度为小数点后6位cout.precision(6);/固定格式c

38、out.setf(ios：fixed);cout<<"平均目标函数："<<M_Index<<endl;/统计结果文件保存ofstream resultfile(" 聚类结果.txt",ios:app);resultfile<<"/"<<endl;resultfile<<num<<" 次运行，平均聚类正确率：”<<100*M_R<<”<<endl;输出精度为小数点后6位resultfile.precision

39、(6);/固定格式resultfile.setf(ios:fixed);resultfile<<"平均目标函数："<<M_Index<<endl;return 0;-|n|x|采用著名的iris数据集对程序进行测试,四d: I我的文档 '.桌面L综合实习，£em耸法''i.Rel e aseaai n. ex e牒糊吟值聚类算法二l-iris.txt; 2-wine.txt;3-ASD_12_2.txt; 4-ASD_14_2.txt情选择数据集二Lab=l设定怎行夜数:皿运算次数输入10次输出第1政运行

40、的聚类结果：第法样本：00000090000000000000000000000000000000000000000 0 0 0正俩样本数：right0=50错误样本数：0聚美类别号：sx=o第1类样本：21211111111111111111111111121111111121111111 111111正确样本数：rightfl=46错误样本数：4聚类类别号：=1第2类样本：212222122222212222212121221222222112221222122 2 2 2 2 1正确样本数：right牛38错误样本数：12聚类类别号：sx=2聚类正确率：893333% IIIIHIHIIIIIIIHHIIIIIIIHHIIIIIIHHHIHHHHIHIIIIIII10次运行,平均聚类正确事：89.3H我 平均目标函数：0.160435能对数组实现分类，但是分类正确率不是很理想，没达到预期的90咖上总结这次综合实习，首先我学会了模糊C均值聚类算法，以前没接触过，也不知 道何为数据集，数据集是做啥用的，增加了自己的见解，其次增强了自我学习能 力，平时学习的学习都是老师已经安排好得内容，看啥知识都已经知道，只需要 安心的看就能学会，都是书本上的知识，没有联系实际，一般都