模式识别大作业--模糊C均值算法实现

模式识别大作业--C均值算法模糊C均值算法算法简述：C均值聚类算法：C-均值算法属于动态聚类算法，动态聚类算法有以下三个要点：1.选定某种距离度量作为样本间的相似性度量。2.确定某个评价聚类结果质量的准则函数。3.给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果。C均值算法的基础是误差平方和准则。若将N个样本{x1,…,xN}划分到k个类{C1,…,Ck}中，k为一正整数，目标：使得各个数据与其对应聚类中心点的误差平方和最小。设mi是这些样本的均值。设Ji为第i类聚类的目标函数，且满足下列条件：k为聚类个数x是划分到类Ci的样本m1,…,mk是类C1,…,Ck的质心（均值向量），那么有：J是误差平方和聚类准则，它是样本集和类别集的函数。J度量了用k个聚类中心代表的k个样本子集所产生的总的误差平方。C均值聚类算法流程：1.初始化：随机选择k个样本点，并将其视为各聚类的初始中心m1,…,mk；2.按照最小距离法则逐个将样本x划分到以聚类中心m1,…,mk为代表的k个类C1,…,Ck中；3.计算聚类准则函数J，重新计算k个类的聚类中心m1,…,mk；4.重复Step2和3直到聚类中心m1,…,mk无改变或目标函数J不减小。模糊C均值算法：C均值算法的目的是把n个样本划分到c个类别中的一个中，使各个样本与其所在类均值的误差平方和最小。而将这种硬分类变为模糊分类，就可得到模糊c均值算法。设μj(xi)是第i个样本xi属于第j类Gj的隶属度,利用隶属度定义的准则函数为211||||ikkiiiixCJJxm(2)1iiixCmxN211()CNbfjiijjiJxxm其中,b1是一个可以控制聚类结果的模糊程度的常数。进一步,要求一个样本属于各个聚类的隶属度之和为1,即其中,λi(i=1,2,…,N)为拉格朗日乘子。分别求L对mi、λi和μj(xi)的梯度(或偏导),并置为0,可得必要条件:模糊C均值算法采用迭代方法求解式(8-62)和式(8-63),其步骤如下(1)设定聚类数目C、参数b和一个适当的小数ε0,通常取1b≤5(2)设置初始模糊分类矩阵U(0),令s=0(3)根据式(8-62)计算U(s)的聚类中心{m(s)j,j=1,2,…,C}。(4)按下面的方法更新U(s)为U(s+1)①计算Ii和，（i=1,2,…,N）②计算xi的新隶属度。如果Ii为空集,则按式(8-63)计算隶属度;否则,并取(5)选取一个适当的矩阵范数,如果‖U(s)－U(s+1)‖ε,则停止迭代,否则s=s+1,返回(3)。当模糊C均值算法收敛时,就得到了各类的聚类中心和各个样本属于各类的隶属度,也就完成了模糊聚类。进一步,可以将模糊聚类结果去模糊化,把模1()1(1,2,,)CjijiNx11()(1,2,,)()NbjiiijNbjiijCxxmx1(1)21(1)211()(1,2,,;1,2,,)1bijjiCbilliNjCxmxxm(){|0,1,2,,}siijIjjKxm{1,2,,}\iiIKIiijIj,0)(x1()1CjijxiI源代码及测试结果：C均值算法：#includeiostream#includefstream#includemath.husingnamespacestd;voidCmeans(double**Date);doubleDistance(double*,double*);intmain(){inti,j;double**IrisDate=newdouble*[150];for(i=0;i150;i++){IrisDate[i]=newdouble[4];}ifstreamfile;file.open(Iris.txt);if(file.fail()){coutFiledoesn'texist!endl;file.close();cin.get();}else{for(i=0;i150;i++){for(j=0;j4;j++){fileIrisDate[i][j];}}file.close();}return0;}voidCmeans(double**Date){inti,j;intN;//分类数coutInputhowmanygroupyouwanttodivide：\n;cinN;intequl=0;int*count=newint[N];//每类样本数for(i=0;iN;i++){count[i]=0;}double**dist=newdouble*[150];for(i=0;i150;i++){dist[i]=newdouble[N];}double**C=newdouble*[N];for(i=0;iN;i++){C[i]=newdouble[4];}//初始化聚类中心for(i=0;iN;i++){for(j=0;j4;j++){C[i][j]=Date[i][j];//以前N个样本作为聚类中心}}double**NC=newdouble*[N];for(i=0;iN;i++){NC[i]=newdouble[4];}for(i=0;iN;i++){for(j=0;j4;j++){NC[i][j]=C[i][j];//初始化}}intI=1;//迭代次数while(equl!=4*N&&I200){for(i=0;iN;i++){count[i]=0;//迭代前每类样本数清0}for(i=0;i150;i++){doublemin=999.9;intw;//记录第i个样本的类别for(j=0;jN;j++){dist[i][j]=Distance(Date[i],C[j]);//计算第i个样本到第j个聚类中心的距离}for(j=0;jN;j++){if(dist[i][j]min){min=dist[i][j];w=j;}}count[w]++;for(j=0;j4;j++){NC[w][j]+=Date[i][j];}}for(i=0;iN;i++){for(j=0;j4;j++){NC[i][j]=NC[i][j]/(double)count[i];//计算新的聚类中心}}for(i=0;iN;i++){for(j=0;j4;j++){if(NC[i][j]!=C[i][j]){C[i][j]=NC[i][j];}else{equl++;}}}I++;}coutendl;coutTheresultis：endl;coutendl;for(i=0;iN;i++){coutGroupi+1icudecount[i]samples，thecentervectoris：(;for(j=0;j4;j++){coutC[i][j];}cout)endl;coutendl;}}doubleDistance(double*A,double*B){doublesum=0.0;for(inti=0;i4;i++){sum+=pow((A[i]-B[i]),2.0);}returnsum;}（使用的IDE为Codeblocks+GNCGCCComplier）模糊C均值算法：//读取数据（同Cmeans）inti,j;double**IrisDate=newdouble*[150];for(i=0;i150;i++){IrisDate[i]=newdouble[4];}ifstreamfile;file.open(Iris.txt);if(file.fail()){coutFiledoesn'texist!endl;file.close();cin.get();}else{for(i=0;i150;i++){for(j=0;j4;j++){fileIrisDate[i][j];}}file.close();}//读取Iris数据FuzzyC(IrisDate);return0;}//构造矩阵（同Cmeans）//构造距离矩阵150*Ndouble**dist=newdouble*[150];for(i=0;i150;i++){dist[i]=newdouble[N];}//构造聚类中心矩阵N*4double**C=newdouble*[N];for(i=0;iN;i++){C[i]=newdouble[4];}//初始化聚类中心for(i=0;iN;i++){for(j=0;j4;j++){C[i][j]=Date[i][j];}}//隶属度函数inti,j;double*sum=newdouble[4];for(j=0;j4;j++){doubledj=0;for(i=0;ik;i++){dj=dj+U[i][j];sum[j]=dj;}}for(i=0;i150;i++){for(j=0;j4;j++){u[i][j]=U[i][j]/sum[j];})}//迭代过程inti,j,t;double**p=NULL;for(i=0;i150;i++){for(j=0;j4;j++){u[i][j]=pow(u[i][j],2);}}//根据隶属度矩阵计算聚类中心p=MatrixMul(u,k,row,data,row,col);for(i=0;i150;i++){doublesi=0;for(j=0;j4;j++){si+=u[i][j];}for(t=0;t4;t++){center[i][t]=p[i][t]/si;}}double*a=newdouble[4];double*b=newdouble[4];double**dis=newdouble*[150];for(i=0;i150;i++){dis[i]=newdouble[row];}for(i=0;i150;i++){for(t=0;t4;t++){a[t]=center[i][t];}for(j=0;j4;j++){for(t=0;t4;t++){b[t]=data[j][t];}doubled=0;for(t=0;t4;t++){d+=(a[t]-b[t])*(a[t]-b[t]);/}dis[i][j]=sqrt(d);}}