bangyongdoc.cpp

K均值和ISODATA分类两种算法

// BangYongDoc.cpp : implementation of the CBangYongDoc class
//

#include "stdafx.h"
#include "BangYong.h"
#include "math.h"

#include "BangYongDoc.h"
#include "ISODCanShuDlg.h"
#include "ISODTiShiDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CBangYongDoc

IMPLEMENT_DYNCREATE(CBangYongDoc, CDocument)

BEGIN_MESSAGE_MAP(CBangYongDoc, CDocument)
	//{{AFX_MSG_MAP(CBangYongDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBangYongDoc construction/destruction

CBangYongDoc::CBangYongDoc()
{
	// TODO: add one-time construction code here
	m_flag=0;

}

CBangYongDoc::~CBangYongDoc()
{
}

BOOL CBangYongDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CBangYongDoc serialization

void CBangYongDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CBangYongDoc diagnostics

#ifdef _DEBUG
void CBangYongDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CBangYongDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
// CBangYongDoc commands

//从文件中读取数据

void CBangYongDoc::ReadFile()
{
	CFileDialog MyFileDlg(TRUE,NULL,NULL,0,
		"文本文件(*.txt)|*.txt|dat文件(*.dat)|*.dat|所有文件(*.*)|*.*|");
	if(MyFileDlg.DoModal()==IDOK)
	{
		CString strFileName=MyFileDlg.GetFileName();
		FILE *fp;
		fp=fopen(strFileName,"r");
		char f0=NULL;
		int f1=0,f2=0;
		
		//跳过首行字符
		do {
			fscanf(fp,"%c",&f0);
		} while(f0!='\n');
		
		//读取样本参数信息
		fscanf(fp,"%d",&f1);//读取维数
		if(f1!=2){
			MessageBox(NULL,"维数不正确,请修改样本文件!","提示消息",MB_OK);
			return;
		}

		fscanf(fp,"%d",&f1);//读取样本总数
		if(f1<4){
			MessageBox(NULL,"样本太少,请添加样本!","提示消息",MB_OK);
			return;
		}
		
		//跳过第2行末的转行符及第3行字符
		fscanf(fp,"%c",&f0);
		do {
			fscanf(fp,"%c",&f0);
		} while(f0!='\n');
		
		//按顺序读取样本点信息
		for(int i=0;i<f1;i++){
			fscanf(fp,"%d",&f2);
			if(f2!=(i+1)){
				MessageBox(NULL,"样本号排序不正确或样本数目与所给参数不符!",
					"提示消息",MB_OK);
				return;
			}
			
			fscanf(fp,"%d",&m_point[i].x);
			fscanf(fp,"%d",&m_point[i].y);	
		}
		m_pointnum=f1;
		
		fclose (fp);
		m_flag=1;//m_flag用于控制显示
	}

}


////////////////////////////////////////////
//计算p点所属类别

int CBangYongDoc::JiSuan(CPoint p)
{
	int i,k;
	double min,result;
	
	//min用于存放最小距离,把min初始化为p点到第一个聚类中心的距离
    min=((p.x-m_kindcentre[0][0])*(p.x-m_kindcentre[0][0])
		+(p.y-m_kindcentre[0][1])*(p.y-m_kindcentre[0][1]));
	k=0;
	
	//计算p点到每一聚类中心的距离,并记录距离最近的类的类别号
	for(i=1;i<m_kindnum;i++){
		result=((p.x-m_kindcentre[i][0])*(p.x-m_kindcentre[i][0])
			+(p.y-m_kindcentre[i][1])*(p.y-m_kindcentre[i][1]));
		if(result<min){
			min=result;
            k=i;
		}
	}
	return k;
	
}


///////////////////////////////////////////
//对样本进行K均值分类

void CBangYongDoc::K_FenLei()
{
	int i,j,k;

	//判断输入是否合法
	if(m_pointnum<m_kindnum){
		MessageBox(NULL,"类别数超过了样本数!","错误报告",MB_OK);
		m_flag=1;
		UpdateAllViews(NULL);
		return;
	}
	
	//动态申请空间用于存放上一次聚类中心坐标
	double *Oldcentre;
	Oldcentre=new double[m_kindnum*2];
	
	//初始化聚类中心点
	j=m_pointnum/m_kindnum;
	for(i=0;i<m_kindnum;i++){
		m_kindcentre[i][0]=m_point[i*j].x;
		m_kindcentre[i][1]=m_point[i*j].y;
		*(Oldcentre+2*i)=m_kindcentre[i][0];
		*(Oldcentre+2*i+1)=m_kindcentre[i][1];
	}
	
	//shoulianflag用于标记前后两次聚类中心是否相同
	//是则令shoulianflag为1,否则为0
	int shoulianflag=0;
	for(i=0;i<m_I&&(shoulianflag==0);i++){
		shoulianflag=1;
		
        //初始化每一类别的点数为0
		for(j=0;j<m_kindnum;j++){
			m_inkindnum[j]=0;
		}
		
		//逐点进行分类,并用数组存放属于每一类的点的序号
		for(j=0;j<m_pointnum;j++){
			k=JiSuan(m_point[j]);
			m_kind[k][(m_inkindnum[k])++]=j;
		}
		
		//分别为每一类计算新的聚类中心
		for(j=0;j<m_kindnum;j++){
			m_kindcentre[j][0]=0;
			m_kindcentre[j][1]=0;
			
			//判断第j类是否为空
			if(m_inkindnum[j]==0){
				MessageBox(NULL,"有类别样本数为空\n\n请调整样本数据的排列顺序!",
					"提示消息!",MB_OK);
			}
			if(m_inkindnum[j]!=0){
				for(k=0;k<m_inkindnum[j];k++){
					m_kindcentre[j][0]+=(m_point[(m_kind[j][k])].x);
					m_kindcentre[j][1]+=(m_point[(m_kind[j][k])].y);
				}
				m_kindcentre[j][0]/=m_inkindnum[j];
				m_kindcentre[j][1]/=m_inkindnum[j];
			}
			
			//判断前后两次聚类中心是否相同,如果不同:设置标记overflag为0
			if(m_kindcentre[j][0]!=*(Oldcentre+2*j)||
				m_kindcentre[j][1]!=*(Oldcentre+2*j+1)){
				shoulianflag=0;
			}
			*(Oldcentre+2*j)=m_kindcentre[j][0];
			*(Oldcentre+2*j+1)=m_kindcentre[j][1];
		}
	}

	//改变屏幕显示标志并刷新
	m_flag=2;
	UpdateAllViews(NULL);

	//判断是否收敛
	if(shoulianflag==1){
		MessageBox(NULL,"聚类中心收敛,分类已完成!","提示信息",NULL);
	}
	
	//释放内存空间
	delete Oldcentre;

}


////////////////////////////////////////////
//对样本类别中心进行初始化

void CBangYongDoc::ISOD_ChuShiHua()
{
	int i,k;
	//按规定类别确定初始类别并对聚类中心初始化
 	if(m_pointnum>=m_K){
 		k=m_pointnum/m_K;
 		for(i=0;i<m_K;i++){
 			m_kindcentre[i][0]=m_point[i*k].x;
 			m_kindcentre[i][1]=m_point[i*k].y;
 		}
 		m_kindnum=m_K;
 	}
 	else {
 		MessageBox(NULL,"样本数小于分类数,无法进行","错误报告",MB_OK);
 		return;
 	}
// 	//按样本数多少确定初始类别并对聚类中心初始化
//  	m_kindnum=m_pointnum/3;
//  	if(m_kindnum<3){
//  		for(i=0;i<3;i++){
//  			m_kindcentre[i][0]=m_point[i].x;
//  			m_kindcentre[i][1]=m_point[i].y;
//  		}
//  		m_kindnum=3;
//  	}
//      else if(m_kindnum>6){
//  		for(i=0;i<6;i++){
//  			m_kindcentre[i][0]=m_point[3*i].x;
//  			m_kindcentre[i][1]=m_point[3*i].y;
//  		}
//  		m_kindnum=6;
//  	}
//  	else{
//  		for(i=0;i<m_kindnum;i++){
//  			m_kindcentre[i][0]=m_point[3*i].x;
//  			m_kindcentre[i][1]=m_point[3*i].y;
//  		}
//  	}
// 

	ISOD_FenLei();
}



////////////////////////////////////////////
//对样本进行ISODATA分类

void CBangYongDoc::ISOD_FenLei()
{
	int i,j,k,cancelflag;
	
	m_iterativetime++;

	//do while循环,用于分类
	//并消除样本数目小于规定值的类别
	do{
		cancelflag=0;
		
		//初始化每一类的样本数
		for(i=0;i<m_kindnum;i++){