模式识别c语言ISODATA算法.doc

c语言编写的ISODATA程序#include#include#include#include#include#include#define MAXNUM 100 /最大模式个数#define MAXDIM 10 /最大模式维数#define K 0.5 /分裂时使用的比值#define MAXDOUBLE 1.0e20 /最大双精度值#define N 10 /实际模式个数#define DIM 2 /实际模式维数struct Pattern /模式结构体int n; /模式序号float sMAXDIM; /模式数据;struct Cluster /类结构体 struct Pattern z; /类中心int n; /类中包含的模式数目 float avg_d; /模式到类心的平均距离struct Pattern yMAXNUM; /模式 float sigmaMAXDIM; /分量的标准差int max; /用于记录类内距离标准差矢量最大的分量下标float sigma_max; /类内分量距离标准差最大值;struct Pattern InitPattern(int i,float a,float b) /对样本模式进行初始化struct Pattern temp;temp.n=i;temp.s0=a;temp.s1=b;return temp;/以下为各参数声明int c=3; /预期的类数int Nc=1; /初始聚类中心个数int ON=1; /每一类中允许的最少模式数（小于此数不可单独成类）float OS=1; /类内分量分布的标准差上限（大于此数就分裂）float OC=4; /两类中心间的最小距离下限（小于此数两类合并）int L=1; /在每次迭代中可以合并的类的最大对数int I=8; /最多迭代次数struct Pattern xN; /全部模式struct Cluster wN; /全部类float DMAXNUMMAXNUM; /各类对中心间的距离float dis; /总体平均距离int iter=1; /记录迭代次数int i,j; /循环变量/以下为程序用到的调用函数void Init();void ISODATA();void InitCenter();void Clustering();float Distance(struct Pattern x1,struct Pattern x2);struct Cluster Insert(struct Pattern a,struct Cluster b);int CheckAndUnion();void CalParameter();struct Pattern CalCenter(struct Cluster a);float Cal_D(int i);void CalSigma();int divide();void CalCenterDis();int UnionByOC();void Union(int a,int b);void PrintCluster();void main()Init();printf(n* ISODATA 算法程序 *n); printf(本实验使用样本集如下：n);x0=InitPattern(0,0,0);x1=InitPattern(1,3,8); x2=InitPattern(2,2,2);x3=InitPattern(3,1,1);x4=InitPattern(4,5,3);x5=InitPattern(5,4,8);x6=InitPattern(6,6,3);x7=InitPattern(7,5,4);x8=InitPattern(8,6,4);x9=InitPattern(9,7,5);for(i=0;iN;i+) /打印本程序所使用样本printf(tX (%d): (,xi.n);for(j=0;jDIM-1;j+)printf(%3.2f,xi.sj);printf(%3.2f);n,xi.sj); ISODATA(); /ISODATA聚类程序system(pause);void Init() /对两结构体变量初始化（赋零值）int i,j,k,l;for(i=0;iN;i+)xi.n=0;wi.n=0;wi.avg_d=0;wi.max=0;wi.sigma_max=0;wi.z.n=0;for(j=0;jMAXDIM;j+)xi.sj=0;wi.sigmaj=0;wi.z.sj=0;for(k=0;kMAXNUM;k+)wi.yk.n=0;for(l=0;lMAXDIM;l+)wi.yk.sl=0;for(i=0;iMAXNUM;i+)for(j=0;jMAXNUM;j+)Dij=0;void InitCenter() /按序号选定初始聚类中心int i,j,k,l;for(j=0;jNc;j+)wj.z=xj;wj.z.n=0;void Clustering() /依最小距离原则将全部模式归类float temp=0.0,min=MAXDOUBLE;int i,j,l=0;for(j=0;jNc;j+)wj.n=0;wj.z.n=0;for(i=0;iN;i+)min=MAXDOUBLE;l=0;for(j=0;jtemp)min=temp;l=j;wl=Insert(xi,wl);float Distance(struct Pattern x1,struct Pattern x2) /计算两个模式距离的函数int i;float temp=0.0;for(i=0;iDIM;i+)temp+=(x1.si-x2.si)*(x1.si-x2.si);return sqrt(temp);struct Cluster Insert(struct Pattern a,struct Cluster b) /将某模式插入对应类b.n+;b.yb.n-1=a;return b;int CheckAndUnion() /依据ON判断合并，若类wj中模式数小于ON，取消类心，Nc=Nc-1,转至step2:int j=0,k;doif(wj.nON)for(k=j;kNc;k+)wk.z=wk+1.z;Nc-;return 1; j+;while(jNc);return 0;struct Pattern CalCenter(struct Cluster a) /计算类心int i,j;struct Pattern temp;for(j=0;jDIM;j+)temp.sj=0;temp.n=0;for(i=0;ia.n;i+)for(j=0;jDIM;j+)temp.sj+=a.yi.sj;for(i=0;iDIM;i+)temp.si/=a.n;return temp;float Cal_D(int j) /计算各模式到类心的平均距离int i; float avg_d=0.0;for(i=0;iwj.n;i+)avg_d+=Distance(wj.yi,wj.z);avg_d/=wj.n;wj.avg_d=avg_d;return avg_d;void CalParameter() /计算分类后参数：各类中心、类内平均距离以及总体平均距离int i;struct Pattern temp;dis=0.0;for(i=0;iNc;i+)dis+=wi.n*Cal_D(i); dis/=N;void CalSigma() /计算各类类内距离的标准差矢量int i,j,k;for(j=0;jNc;j+)for(k=0;kDIM;k+)float temp=0.0;for(i=0;iwj.n;i+)struct Pattern z;/z=CalCenter(wj);temp+=(wj.yi.sk-wj.z.sk)*(wj.yi.sk-wj.z.sk);wj.sigmak=sqrt(temp/wj.n);if(wj.sigma_maxwj.sigmak)wj.sigma_max=wj.sigmak;wj.max=k;int divide() /判断分裂int i,j,l;for(j=0;jdis)&(wj.n2*(ON+1)|(Ncj;l-)wl.z=wl-1.z;wj+1.z.si-=K*sigma_temp;wj.z.si+=K*sigma_temp;Nc+;return 1;return 0;void CalCenterDis() /计算各类对中心间的距离int i,j;for(i=0;iNc-1;i+)for(j=i+1;jNc;j+)Dij=Distance(wi.z,wj.z);void Union(int a,int b) /当两类未合并过时，进行合并int i;if(wa.z.n0)|(wb.z.n0)return ;for(i=0;iDIM;i+)wa.z.si=(1/(wa.n+wb.n)*(wa.z.si*wa.n+wb.n*wb.z.si);wa.z.n=-1;wb.z.n=-2;int UnionByOC() /依据OC判断合并int i,j,k,l;int num=0; int flag=0;structfloat d;int i;int j;DminN;for(i=0;iL;i+)Dmini.d=OC;Dmini.i=-1;Dmini.j=-1;for(i=0;iNc-1;i+)for(j=i+1;jNc;j+)if(DijOC)for(k=0;kL;k+)if(Dijk;l-)Dminl=Dminl-1;Dmink.d=Dij;Dmink.i=i;Dmink.j=j;break;for(i=0;i-1&Dmini.j-1)Union(Dmini.i,Dmini.j);flag=1;for(j=0;jNc;j+)if(wj.z.n=-2)for(k=j;kNc;k+)wk.z=wk+1.z;Nc-;return flag;void PrintCluster() /打印当前模式分类情况int i,j,k;printf(-总共分为 %d 类-n,Nc);for(i=0;iNc;i+)printf(t第 %d 类 类心为：(,i+1); for(j=0;jDIM-1;j+)printf(%3.2f,wi.z.sj);printf(%3.2f )n,wi.z.sDIM-1);printf(包含的模式为：n);for(k=0;kwi.n;k+)printf(tX (%d):(,wi.yk.n);for(j=0;jDIM-1;j+)printf(%3.2f,wi.yk.sj);printf(%3.2f)n,wi.yk.sDIM-1);printf(n);void ISODATA()int changed=1;int i;start: /读入参数printf(n设定聚类分析控制参数：n);printf(预期的类数 c：);scanf(%d,&c);printf(初始聚类中心个数Nc（可不等于c）：);scanf(%d,&Nc);printf(每一类中允许的最少模式数目ON（小于此数不可单独成类）：);scanf(%d,&ON);printf(类内各分量分布的标准差上限OS（大于此数就分裂）：);scanf(%4f,&OS);printf(两类中心间的最小距离下限OC（小于此数两类合并）：);scanf(%4f,&OC);printf(在每次迭代中可以合并的类的最多对数L： );scanf(%d,&L);printf(最多迭代次数I： );scanf(%d,&I);printf(n);step1: InitCenter();step2:changed=0; Clustering();if(iter=0)printf(n-选取初始聚类中心-n);elseprintf(-第 %d 次迭代-n ,iter);PrintCluster();step3:if(CheckAndUnion()goto step2;step4:for(i=0;iNc;i+)wi.z=CalCenter(wi); /计算聚类中心CalParameter(); /每个聚类的样本离开其中心的平均距离以及所有样本离开其相应聚类中心的平均距离step5: /依据iter,Nc判断停止、分裂还是合并if(iter=I)OC=0; goto step8;if (Nc=2*c)|iter%2=0)goto step8;step6:CalSigma();step7:if(divide()iter+;goto