200532590150doc.cpp

实现了二维数据的K均值算法以及ISODATA分类算法

// 200532590150Doc.cpp : implementation of the CMy200532590150Doc class
//

#include "stdafx.h"
#include "200532590150.h"

#include "200532590150Doc.h"
#include "math.h"

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

/////////////////////////////////////////////////////////////////////////////
// CMy200532590150Doc

IMPLEMENT_DYNCREATE(CMy200532590150Doc, CDocument)

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

/////////////////////////////////////////////////////////////////////////////
// CMy200532590150Doc construction/destruction

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

CMy200532590150Doc::~CMy200532590150Doc()
{
}

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

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

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CMy200532590150Doc serialization

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

/////////////////////////////////////////////////////////////////////////////
// CMy200532590150Doc diagnostics

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

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

/////////////////////////////////////////////////////////////////////////////
// CMy200532590150Doc commands
//以最小距离分类
void CMy200532590150Doc::classify1(double z[][2],int num[],int count,int C)
{
	double temp[100][20],t,min;
	//数据归零
	for(int i=0;i<C;i++)
		num[i]=0;
    for(i=0;i<count;i++)
	{
		min=10000.0;
	    //分别计算各样本到各聚类中心的距离
		for(int j=0;j<C;j++)
		{
			t=(x[i].x1-z[j][0])*(x[i].x1-z[j][0])+(x[i].x2-z[j][1])*(x[i].x2-z[j][1]);
			temp[i][j]=sqrt(t);
			//寻找样本到所有聚类中心的距离的最小值并归类
            if(temp[i][j]<min)
			{
				min=temp[i][j];
				x[i].type=j;
			}
		}
	}
	for(i=0;i<count;i++)
		for(int j=0;j<C;j++)
		{
			if(x[i].type==j)
				num[j]++;
			else 
				continue;
		}
}

//重新计算聚类中心
void CMy200532590150Doc::center1(double z[][2],int num[],int count,int C)
{
	//数据归零
	for(int i=0;i<C;i++)
		for(int j=0;j<3;j++)
		{
		     z[i][j]=0;
		}
	//分别计算各类群的均值向量
	for(i=0;i<count;i++)
	{
		for(int j=0;j<C;j++)
		{
			if(x[i].type==j)
			{
				z[j][0]+=x[i].x1;
				z[j][1]+=x[i].x2;
			}
		}
	}
	for(i=0;i<C;i++)
	{
		z[i][0]/=num[i];
		z[i][1]/=num[i];
	}
}

//取消一个子集
int CMy200532590150Doc::cancelsubset(double z[][2],int num[],int count,int C,int j)
{
	//将去掉一个聚类中心后的聚类中心数组重新排列
	for(int i=j;i<C-1;i++)
	{
		z[i][0]=z[i+1][0];
		z[i][1]=z[i+1][1];
	}
	//类别数减一
	C=C-1;
	//重新分类
    classify1(z,num,count,C);
	//返回新的类别数
    return C;
}

//计算各聚类样本到相应样本中心的距离的平均值及这些均值的平均值
double CMy200532590150Doc::distance(double z[][2],int num[],int count,int C,double d[])
{
	//将数据归零
	for(int i=0;i<C;i++)
		d[i]=0;
	double D=0;
	//计算各聚类样本到中心的平均距离
	for(int j=0;j<count;j++)
		for(i=0;i<C;i++)
			if(x[j].type==i)
			    d[i]+=sqrt(pow((x[i].x1-z[i][0]),2)+pow((x[i].x2-z[i][1]),2))/num[i];
	//计算所有样本到各中心的平均距离
	for(i=0;i<C;i++)
		D+=d[i]*num[i];
	D/=count;
	return D;
}

//计算各聚类的标准差向量及其最大分量
void CMy200532590150Doc::biaozhuncha(double z[][2],int num[],int count,int C,double d[],double Q[][2],double Qmax[])
{
	//数据归零
	for(int j=0;j<C;j++)
	{
		Q[j][0]=0;
		Q[j][1]=0;
		Qmax[j]=0;
	}
	//计算标准差向量
	for(int i=0;i<count;i++)
		for(int j=0;j<C;j++)
			if(x[i].type==j)
			{
				Q[j][0]+=pow((x[i].x1-z[j][0]),2);
				Q[j][1]+=pow((x[i].x2-z[j][1]),2);
			}
	for(j=0;j<C;j++)
	{
		Q[j][0]=sqrt(Q[j][0]/num[j]);
        Q[j][1]=sqrt(Q[j][1]/num[j]);
	}
	//计算各标准差向量的最大分量
	for(j=0;j<C;j++)
		for(i=0;i<2;i++)
	    	if(Qmax[j]<Q[j][i])
				Qmax[j]=Q[j][i];		
}

//分裂
int CMy200532590150Doc::split(double Qmax[],double Q[][2],double z[][2],int C,int j,
							  double dc[][20],int num[],int count,double qc)
{
    double m,min=100000.0;
	C=C+1;
	int count0=0;
	int NUM[20]={0};
	double DC[20][20]={0},Z[20][2]={0};
	do
	{
		//m随机取0到1的数
		m=rand()%9+1;
		m/=10.0;
		for(int i=0;i<C;i++)
		{
			NUM[i]=num[i];
            Z[i][0]=z[i][0];
            Z[i][1]=z[i][1];
		}
		for(i=0;i<C-1;i++)
			for(int j=i+1;j<C;j++)
				DC[i][j]=dc[i][j];
		for(i=0;i<2;i++)
		{
		     if(Qmax[j]==Q[j][i])
			 {
				 Z[C-1][i]=Z[j][i]-Qmax[j]*m;
			     Z[j][i]=Z[j][i]+Qmax[j]*m;
				 for(int k=0;k<2;k++)
				 {
					 if(k!=i)
						 Z[C-1][k]=Z[j][k];    
					 else 
						 continue;
				 }
			 }
		     else 
		       	continue;
		}
		classify1(Z,NUM,count,C);
        center1(Z,NUM,count,C);
        centerD(Z,DC,C);
        for(i=0;i<C-1;i++)
		    for(int k=i+1;k<C;k++)
			{
			    if(min>DC[i][k])
				     min=DC[i][k];
			}
		count0++;
	}
	while(min<qc&&count0<6);//循环结束条件：所有每两中心间距离均大于阈值qc
	for(int i=0;i<C;i++)
		{
            z[i][0]=Z[i][0];
            z[i][1]=Z[i][1];
		}
	if(count0==6)
		flagpara=1;//第十五步修改参数的条件
    return C;
}

//计算两两类群中心之间的距离
void CMy200532590150Doc::centerD(double z[][2],double dc[][20],int C)
{
	double temp;
	//数据归零
	for(int i=0;i<C;i++)
		for(int j=0;j<C;j++)
			dc[i][j]=0;
	for(i=0;i<C-1;i++)
		for(int j=i+1;j<C;j++)
		{
			temp=pow((z[i][0]-z[j][0]),2)+pow((z[i][1]-z[j][1]),2);
			dc[i][j]=sqrt(temp);
		}
}

//合并
int CMy200532590150Doc::combine(double dc[][20],int C,double qc,int L,int count,double z[][2],int num[])
{
	int k=0,i,j;
	sample temp;
	//数据归零
	for(i=0;i<C;i++)
		dc1[i].type=0;
	//找出小于阈值qc的中心间的距离
	for(i=0;i<C-1;i++)
	{
		for(j=i+1;j<C;j++)
		{
			if(dc[i][j]<qc)
			{
				dc1[k].x1=i;
				dc1[k].x2=j;
				dc1[k].type=dc[i][j];
				k++;
			}
			else
				continue;
		}
	}
	//如果没有小于阈值qc的则不合并
	if(k==0)
		return C;
	//若有小于阈值的则合并
	else
	{
		int t=k;//小于阈值的类别对数
	    //将距离按从小到大的顺序排序
	    for(i=0;i<t-1;i++)
		    for(j=i+1;j<t;j++)
			    if(dc1[i].type>dc1[j].type)
				{
				     temp=dc1[i];
				     dc1[i]=dc1[j];
				     dc1[j]=temp;
				}
	    //合并
	    for(i=0;i<L;i++)
		{
		    int t1=(int)(dc1[i].x1),t2=(int)(dc1[i].x2);
		    //将j类的样本标记改为i类
		    for(j=0;j<count;j++)
			    if(x[j].type==dc1[i].x2)
				     x[j].type=dc1[i].x1;
		    //将j类的中心去除
		    for(j=t2;j<C-1;j++)
			{
			    z[j][0]=z[j+1][0];
			    z[j][1]=z[j+1][1];
			}
		    //修改新的聚类中心
		    z[t1][0]=(num[t1]*z[t1][0]+num[t2]*z[t2][0])/(num[t1]+num[t2]);
		    z[t1][1]=(num[t1]*z[t1][1]+num[t2]*z[t2][1])/(num[t1]+num[t2]);
	    	//类别数减一
	     	C=C-1;
		}
		return C;
	}
}