bangyongdoc.cpp

K均值和ISODATA分类两种算法

			m_inkindnum[i]=0;
		}
		
		//对所有点依次分类
		for(i=0;i<m_pointnum;i++){

			//调用距离分类函数,返回该点所属类别号
			k=JiSuan(m_point[i]);
			
			//把该点归类
			m_kind[k][(m_inkindnum[k])]=i;
			m_inkindnum[k]++;
			
		}
		
		//遍历每一类别,如果样本数小于m_N则取消该类
		for(i=0;i<m_kindnum;i++){
			if(m_inkindnum[i]<m_N){
				cancelflag=1;
				for(j=i+1;j<m_kindnum;j++){
					m_kindcentre[j-1][0]=m_kindcentre[j][0];
					m_kindcentre[j-1][1]=m_kindcentre[j][1];
				}
				m_kindnum--;
				break;
				
			}
		}
		
	}
	while(cancelflag!=0);
	//如果本次循环有类别被取消,则重新分类
	
	
	//修正各聚类中心值
	for(i=0;i<m_kindnum;i++){
		m_kindcentre[i][0]=0;
		m_kindcentre[i][1]=0;
		for(j=0;j<m_inkindnum[i];j++){
			m_kindcentre[i][0]+=m_point[(m_kind[i][j])].x;
			m_kindcentre[i][1]+=m_point[(m_kind[i][j])].y;
		}
		m_kindcentre[i][0]/=m_inkindnum[i];
		m_kindcentre[i][1]/=m_inkindnum[i];
	}
	
	
	//判断迭代是否结束
	if(m_iterativetime>=m_I){
		m_C=0;
		ISOD_HeBing();
	}
	else{
		if(m_kindnum<=m_K/2){
			ISOD_FenLie();
		}
		else if(m_kindnum>2*m_K){
			ISOD_HeBing();
		}
		else{
			if(m_iterativetime%2==1){
				ISOD_FenLie();
			}
			else{
				ISOD_HeBing();
			}
		}
	}

}


///////////////////////////////////////////
//对类别进行分裂

void CBangYongDoc::ISOD_FenLie()
{
	int i,j,k;
	int *dim_smax;//dimension维数
		//指针*s用于指向每一类的标准差向量值
		//指针*inkinddis用于指向每一类样本到聚类中心的平均距离
		//allkindsdis是所有样本点到其对应聚类中心的距离的平均值
	double *s,*inkinddis,allkindsdis=0;
    dim_smax=new int[m_kindnum];
	s=new double[m_kindnum*2];
	inkinddis=new double[m_kindnum];
	
	//计算类内平均距离和
	//所有样本到其相应的聚类中心的距离的平均值
	for(i=0;i<m_kindnum;i++){
		*(inkinddis+i)=0;
		for(j=0;j<m_inkindnum[i];j++){
			k=m_kind[i][j];
			*(inkinddis+i)+=sqrt((m_point[k].x-m_kindcentre[i][0])
				*(m_point[k].x-m_kindcentre[i][0])+(m_point[k].y-m_kindcentre[i][1])
				*(m_point[k].y-m_kindcentre[i][1]));
		}
		allkindsdis+=*(inkinddis+i);
		*(inkinddis+i)/=m_inkindnum[i];
	}
	allkindsdis/=m_pointnum;
	
	//计算每一类别中样本与聚类中心距离的标准差向量
	for(i=0;i<m_kindnum;i++){
		*(s+2*i)=0;
		*(s+2*i+1)=0;
		for(j=0;j<m_inkindnum[i];j++){
			k=m_kind[i][j];
			*(s+2*i)+=(m_point[k].x-m_kindcentre[i][0])*(m_point[k].x-m_kindcentre[i][0]);
			*(s+2*i+1)+=(m_point[k].y-m_kindcentre[i][1])*(m_point[k].y-m_kindcentre[i][1]);
		}
		*(s+2*i)=sqrt(*(s+2*i)/m_inkindnum[i]);
		*(s+2*i+1)=sqrt(*(s+2*i+1)/m_inkindnum[i]);
	}
	
	//求每一个标准差向量的最大分量并记录它所对应的维数
	for(i=0;i<m_kindnum;i++){
		if( *(s+2*i) >= *(s+2*i+1) ){
			*(dim_smax+i)=0;
		}
		else{
			*(dim_smax+i)=1;
		}
	}
	
	//判断条件,进行分裂
	int divideflag=0;
	const double m=0.5;//m用于分裂时聚类中心改变值的系数
	k=m_kindnum;
	for(i=0;i<k;i++){
		//如果第i类的标准差向量最大分量大于限差
		if(*(s+2*i+(*(dim_smax+i)))>m_S){
			if(((inkinddis[i]>allkindsdis)&&(m_inkindnum[i]>2*(m_N+1)))
				||(m_kindnum<=(m_K/2))){

				if(m_kindnum==KINDMAX){
					MessageBox(NULL,"类别数超限,请修改宏定义KINDMAX","错误报告",MB_OK);
					delete s;	//释放动态内存
					delete dim_smax;
					delete inkinddis;
					return;
				}

				m_kindcentre[m_kindnum][0]=m_kindcentre[i][0];
				m_kindcentre[m_kindnum][1]=m_kindcentre[i][1];
				m_kindcentre[i][*(dim_smax+i)]+=*(s+2*i+(*(dim_smax+i)))*m;
				m_kindcentre[m_kindnum][*(dim_smax+i)]-=*(s+2*i+(*(dim_smax+i)))*m;
				m_kindnum++;
				divideflag=1;
			}
		}
	}
	
	//释放动态内存
	delete s;
	delete dim_smax;
	delete inkinddis;
	
	//判断是否进行了分裂,是则调用分类函数重新分类,否则,调用合并函数
	if(divideflag==1){
		ISOD_FenLei();
	}
	else{
		ISOD_HeBing();
	}
	

}

/////////////////////////////////////////////
//对类别进行合并

void CBangYongDoc::ISOD_HeBing()
{
	int i,j,k;
	ET  *dis;
	dis=new ET[m_kindnum*(m_kindnum-1)/2];

	//依次计算不同类的聚类中心距离
	for(i=0,k=0;i<m_kindnum-1;i++){
		for(j=i+1;j<m_kindnum;j++){
			(*(dis+k)).k1=i;
			(*(dis+k)).k2=j;
			(*(dis+k)).distance=(m_kindcentre[i][0]-m_kindcentre[j][0])
				*(m_kindcentre[i][0]-m_kindcentre[j][0])
				+(m_kindcentre[i][1]-m_kindcentre[j][1])
				*(m_kindcentre[i][1]-m_kindcentre[j][1]);
		}
		k++;
	}
	
	//对中心距离排序
	ET instead;
	for(i=0;i<m_L;i++){
		for(j=k-1;j>i;j--){
			if((*(dis+j)).distance<(*(dis+j-1)).distance){
				instead.k1=(*(dis+j-1)).k1;
				instead.k2=(*(dis+j-1)).k2;
				instead.distance=(*(dis+j-1)).distance;
				(*(dis+j-1)).k1=(*(dis+j)).k1;
				(*(dis+j-1)).k2=(*(dis+j)).k2;
				(*(dis+j-1)).distance=(*(dis+j)).distance;
                (*(dis+j)).k1=instead.k1;
                (*(dis+j)).k2=instead.k2;
                (*(dis+j)).distance=instead.distance;
			}
		}
	}
	
	//取满足要求的前m_L个距离
	int s=0;//s用于记录归并的对数
	double cc;
	cc=m_C*m_C;

	for(s=0;((*(dis+s)).distance<cc)&&(s<m_L)&&(s<k);s++){
			//寻找满足要求的归并对数
	};
	
	//进行合并,把所有类的合并标志都赋为－1
	int *hbflag=new int[m_kindnum];
	for(i=0;i<m_kindnum;i++){
		*(hbflag+i)=-1;
	}
	int kindnum=m_kindnum;//记录合并前的类别数
	for(i=0;i<s;i++){
		//p和q记录待合并的两个类别的类别号
		int p=(*(dis+i)).k1;
		int q=(*(dis+i)).k2;
		if((*(hbflag+p)==-1)&&(*(hbflag+q)==-1)){
			
			//将合并的类别的类别号付给其合并标志
			*(hbflag+p)=p;
			*(hbflag+q)=q;
			//创建一个新的类别,用于记录合并后的类信息
			if(m_kindnum==KINDMAX){
				MessageBox(NULL,"占用类别数已超限,请修改宏定义KINDMAX","错误报告",MB_OK);
				delete dis;	//释放动态内存
				delete hbflag;
				return;
			}
			//为新的类别赋值
			m_inkindnum[m_kindnum]=m_inkindnum[p]+m_inkindnum[q];
			m_kindcentre[m_kindnum][0]=(m_inkindnum[p]*m_kindcentre[p][0]
				+m_inkindnum[q]*m_kindcentre[q][0])/(m_inkindnum[m_kindnum]);
			m_kindcentre[m_kindnum][1]=(m_inkindnum[p]*m_kindcentre[p][1]
				+m_inkindnum[q]*m_kindcentre[q][1])/(m_inkindnum[m_kindnum]);
			for(j=0;j<m_inkindnum[p];j++){
				m_kind[m_kindnum][j]=m_kind[p][j];
			}
			for(k=0;k<m_inkindnum[q];k++){
				m_kind[m_kindnum][j+k]=m_kind[q][k];
			}
			m_kindnum++;
			
		}
	}
	
	//取消已经合并完成的类
	for(i=0;i<kindnum;i++){
		if((*(hbflag+i))>-1){
			for(j=i+1;j<kindnum;j++){
				(*(hbflag+j))--;
			}
			for(j=i+1;j<m_kindnum;j++){
				m_kindcentre[j-1][0]=m_kindcentre[j][0];
				m_kindcentre[j-1][1]=m_kindcentre[j][1];
				m_inkindnum[j-1]=m_inkindnum[j];
				if(j<kindnum){
					*(hbflag+j-1)=*(hbflag+j);
				}
				for(k=0;k<m_inkindnum[j];k++){
					m_kind[j-1][k]=m_kind[j][k];
				}
				
			}
			m_kindnum--;
			kindnum--;
			
		}
	}
	//释放动态内存
	delete dis;
	delete hbflag;
	
	//刷新视图
	m_flag=2;
	UpdateAllViews(NULL);
	
	//判断是否迭代结束
	if(m_iterativetime>=m_I){
		
		MessageBox(NULL,"迭代结束,这是最终结果!","提示消息",MB_OK);
		m_flag=2;
		UpdateAllViews(NULL);
	}
	else {
		CISODTiShiDlg dlg1;
		if(dlg1.DoModal()==IDOK){
			CISODCanShuDlg dlg2;
			
			//剩余迭代次数
			dlg2.m_i=m_I-m_iterativetime;
			dlg2.m_k=m_K;
			dlg2.m_n=m_N;
			dlg2.m_s=m_S;
			dlg2.m_c=m_C;
			dlg2.m_l=m_L;
			if(dlg2.DoModal()==IDOK){
				m_I=dlg2.m_i+m_iterativetime;
				m_K=dlg2.m_k;
				m_N=dlg2.m_n;
				m_S=dlg2.m_s;
				m_C=dlg2.m_c;
				m_L=dlg2.m_l;
			}
			ISOD_FenLei();
			
		}
		else{
			ISOD_FenLei();
		}
	}
	
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//the end