cmeandoc.cpp

用cmean方法做的模式识别聚类程序.通过测量各点之间的距离来确定类别数

// CmeanDoc.cpp : implementation of the CCmeanDoc class
//

#include "stdafx.h"
#include "Cmean.h"

#include "CmeanDoc.h"
#include <VECTOR>
#include <cmath>

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




/////////////////////////////////////////////////////////////////////////////
// CCmeanDoc

IMPLEMENT_DYNCREATE(CCmeanDoc, CDocument)

BEGIN_MESSAGE_MAP(CCmeanDoc, CDocument)
	//{{AFX_MSG_MAP(CCmeanDoc)
		// 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()

/////////////////////////////////////////////////////////////////////////////
// CCmeanDoc construction/destruction

CCmeanDoc::CCmeanDoc()
{
	// TODO: add one-time construction code here

}

CCmeanDoc::~CCmeanDoc()
{
}

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

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

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CCmeanDoc serialization

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

/////////////////////////////////////////////////////////////////////////////
// CCmeanDoc diagnostics

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

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

/////////////////////////////////////////////////////////////////////////////
// CCmeanDoc commands

pSample CCmeanDoc::GetSample(int i)
{
	return &vData[i];
}

void CCmeanDoc::SetSample(pSample SampleData)
{
	vData.push_back(*SampleData);
}

BOOL CCmeanDoc::mlmsDistance()
{
	//最大最小距离，用以确定初始聚类中心和聚类数目
	//mlmsDistance refers to most large most small Distance
	int c=2;//初始类别为两类
	int	cpre=c;
	double theta=0.3;

	int LENGTH=vData.size();
	if(!LENGTH)
	{
		MessageBox(NULL,"请用鼠标点击窗口采集数据",NULL,MB_OK);
		return FALSE;
	}
	if(LENGTH==1)
	{
		MessageBox(NULL,"只有一个点，无需分类！",NULL,MB_OK);
		return FALSE;
	}

	int i,j;
	long int max_Distance1;
	long int max_Distance2;
	POINT max_pt;
	POINT max_pt2;
	POINT min_pt;

	long int ** distance;
	distance=new long int*[LENGTH];
	if(!distance)
	{
		MessageBox(NULL,"分配内存失败",NULL,MB_OK);
		return FALSE;
	}
	for(i=0;i<LENGTH;i++)
	{
		distance[i]=new long int[LENGTH];
		if(!distance[i])
		{
			MessageBox(NULL,"分配内存失败",NULL,MB_OK);
			return FALSE;
		}
	}

	max_Distance1=0;
	for(i=0;i<LENGTH;i++)
	{
		for(j=i;j<LENGTH;j++)
		{
			distance[i][j]=sqrt(pow(vData[i].point.x-vData[j].point.x , 2) + 
				pow(vData[i].point.y-vData[j].point.y , 2));
			distance[j][i]=distance[i][j];
			if(distance[i][j]>max_Distance1) 
			{
				max_Distance1=distance[i][j];
				max_pt.x=i; max_pt.y=j;
			}
		}
	}
	//得到相距最远的两个点
	vData[max_pt.x].pattern=1;
	vData[max_pt.y].pattern=2;
	vData[max_pt.x].centerflag=1;
	vData[max_pt.y].centerflag=1;
	vCenterList.push_back(max_pt.x);
	vCenterList.push_back(max_pt.y);

	long int min_Distance=distance[max_pt.x][max_pt.y];
	max_Distance2=0;

	do {
		max_Distance2=0;
		for(i=0;i<LENGTH;i++)
		{
			int flag=vData[i].centerflag;
			if(!vData[i].centerflag)
			{
			
				min_Distance=distance[max_pt.x][max_pt.y];
				min_pt.x=i;min_pt.y=i;
				for(j=0;j<c;j++)
				{	
					int k=vCenterList[j];
				
					if(i!=k && distance[i][vCenterList[j]]<min_Distance)
					{
					
						min_Distance=distance[i][vCenterList[j]];
						min_pt.x=i;min_pt.y=vCenterList[j];
						vData[i].pattern=vData[vCenterList[j]].pattern;//归类
					}
				}

				if(distance[min_pt.x][min_pt.y]>max_Distance2)
				{
					//选出所有最小距离里面的最大距离
					max_Distance2=distance[min_pt.x][min_pt.y];
					max_pt2.x=min_pt.x;max_pt2.y=min_pt.y;
				}
			}
		}

		//判别是否应该生成新的聚类中心
		if(max_Distance2>theta*max_Distance1)
		{
			//产生新的聚类中心
			vData[max_pt2.x].centerflag=1;
			vData[max_pt2.x].pattern=c+1;
			vCenterList.push_back(max_pt2.x);
			cpre=c;
			c++;
		}
		else
		{
			break;
		}
	}while(c<=LENGTH);
	
	CString str;
	str.Format("共有类别数：%d",c);
	MessageBox(NULL,str,NULL,MB_OK);

	for(i=0;i<c;i++)
	{
		if(distance[i])
		{
			delete[] distance[i];
			distance[i]=NULL;
		}
	}
	if(distance)
	{
		delete[] distance;
		distance=NULL;
	}

	if(c>LENGTH)
	{
		return FALSE;
	}

	return TRUE;
}

BOOL CCmeanDoc::cmean()
{
	int c=vCenterList.size();
	int LENGTH=vData.size();
	int i,j,flag,looptimes;
	double distance,mindistance;
	//首先根据前面最大最小聚类的结果，计算新的聚类中心
	POINT * MeanCenter;
	MeanCenter=new POINT[c];//存储c个聚类中心
	if (!MeanCenter) {
		MessageBox(NULL,"内存分配失败",NULL,MB_OK);
		return FALSE;
	}

	POINT * MeanCenter_pre=new POINT[c];//存储c个聚类中心
	if (!MeanCenter_pre) {
		MessageBox(NULL,"内存分配失败",NULL,MB_OK);
		return FALSE;
	}

	int * catogory;
	catogory=new int[c];//每个类别有多少个样本
	if (!catogory) {
		MessageBox(NULL,"内存分配失败",NULL,MB_OK);
		return FALSE;
	}
	
	looptimes=0;
	do{
		looptimes++;
		//求新的聚类中心
		for(i=0;i<c;i++)
		{
			MeanCenter[i].x=0;
			MeanCenter[i].y=0;
			catogory[i]=0;
		}

		for(i=0;i<LENGTH;i++)
		{
			for(j=0;j<c;j++)
			{
				if(vData[i].pattern==j+1)
				{
					MeanCenter[j].x+=vData[i].point.x;
					MeanCenter[j].y+=vData[i].point.y;
					catogory[j]++;
				}
			}
		}

		for(i=0;i<c;i++)
		{
			MeanCenter[i].x=MeanCenter[i].x/catogory[i];
			MeanCenter[i].y=MeanCenter[i].y/catogory[i];
		}

		//按新的聚类中心聚类
		for(i=0;i<LENGTH;i++)
		{
			mindistance=9999999;
			for(j=0;j<c;j++)
			{
				distance=sqrt(pow(vData[i].point.x-MeanCenter[j].x,2)+
					pow(vData[i].point.y-MeanCenter[j].y,2));
				if (distance<mindistance) 
				{
					mindistance=distance;
					vData[i].pattern=j+1;
				}
			}
		}

		flag=0;//flag=0表示不需要继续循环了
		for(i=0;i<c;i++)
		{
			if (MeanCenter[i].x != MeanCenter_pre[i].x 
				|| MeanCenter[i].y != MeanCenter_pre[i].y)
			{
				flag=1;
				MeanCenter_pre[i]=MeanCenter[i];
			}
		}

	}while (flag && looptimes<50);

	if(looptimes>=50)
	{
		MessageBox(NULL,"分类结果不正常！",NULL,MB_OK);
		return FALSE;
	}

	if(MeanCenter)
	{
		delete[] MeanCenter;
		MeanCenter=NULL;
	}
	if(MeanCenter_pre)
	{
		delete[] MeanCenter_pre;
		MeanCenter=NULL;
	}
	if(catogory)
	{
		delete[] catogory;
		MeanCenter=NULL;
	}

	return TRUE;
}

int CCmeanDoc::GetDataLength()
{
	return vData.size();
}

int CCmeanDoc::GetCenterListNum()
{
	return vCenterList.size();
}