kmeansview.cpp

这是我帮一个本科生做的毕业设计

// kmeansView.cpp : implementation of the CKmeansView class
//

#include "stdafx.h"
#include "kmeans.h"

#include "kmeansDoc.h"
#include "kmeansView.h"
#include "ParamDlg.h"

#include "fstream.h"
#include "math.h"
#include "assert.h"

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

/////////////////////////////////////////////////////////////////////////////
// CKmeansView

IMPLEMENT_DYNCREATE(CKmeansView, CView)

BEGIN_MESSAGE_MAP(CKmeansView, CView)
	//{{AFX_MSG_MAP(CKmeansView)
	ON_COMMAND(ID_EXEC_PROGRAM, OnExecProgram)
	ON_COMMAND(ID_EXEC_PROGRAM1, OnExecProgram1)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CKmeansView construction/destruction

CKmeansView::CKmeansView()
{
	// TODO: add construction code here
	m_numOfPoint = 0;
	m_tRand = 0;
}

CKmeansView::~CKmeansView()
{
}

BOOL CKmeansView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CKmeansView drawing

void CKmeansView::OnDraw(CDC* pDC)
{
	CKmeansDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	COLORREF color[10] = {RGB(255,0,0),RGB(100,60,0),RGB(0,80,30),RGB(0,0,255),RGB(121,0,37),RGB(46,48,146),RGB(128,128,0),RGB(128,0,128),RGB(0,128,128),RGB(128,128,128)};
	for(int i=0;i<m_numOfPoint;i++)
	{
		pDC->SetPixel((int)(m_AllPoint[i].DimData[0]*500),(int)(m_AllPoint[i].DimData[1]*500),color[m_AllPoint[i].flag]);
	}
	for(i=0;i<m_CorePoint.GetSize();i++)
	{
		float f1=m_CorePoint[i].DimData[0];
		float f2=m_CorePoint[i].DimData[1];
		CBrush brush;
		CBrush *pBrushOld; 
		brush.CreateSolidBrush(RGB(0,0,0));
		pBrushOld= pDC->SelectObject(&brush);
		int x,y;
		x = (int)(m_CorePoint[i].DimData[0]*500);
		y = (int)(m_CorePoint[i].DimData[1]*500);
		pDC->Ellipse(CRect(x-3,y-3,x+3,y+3));
		brush.DeleteObject();
	}
}

/////////////////////////////////////////////////////////////////////////////
// CKmeansView printing

BOOL CKmeansView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CKmeansView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CKmeansView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CKmeansView diagnostics

#ifdef _DEBUG
void CKmeansView::AssertValid() const
{
	CView::AssertValid();
}

void CKmeansView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CKmeansDoc* CKmeansView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CKmeansDoc)));
	return (CKmeansDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CKmeansView message handlers
void CKmeansView::GetAllPoint()
{
	m_AllPoint.RemoveAll();
	m_CorePoint.RemoveAll();

	CParamDlg dlg;
	if(dlg.DoModal()==IDOK)
	{
		m_FileName = dlg.m_FileName;
		m_Param = dlg.m_param;
		m_numOfPoint = dlg.m_numOfPoint;
		m_dim = dlg.m_dim;
		m_CheckError = dlg.m_CheckError;
	}
	else
		return;

	if (m_FileName.IsEmpty())
	{
		MessageBox("Please input Filename!");
		return;
	}

	ifstream dataSet(m_FileName);
	assert(dataSet);
	float *pnt=new float[m_dim];
	char buffer[300];
	int index;
	int i,j;

	for(i=0;i<m_numOfPoint;i++)
	{
		dataSet.getline(buffer,200);
		char *sCoord;
		float dCoord;
		sCoord = strtok(buffer," ");
		index = 0;
		Point pt;
		while ( (sCoord != NULL)&&(index < m_dim) )
		{
			dCoord = (float)(atof(sCoord));
			pt.DimData[index]=dCoord;
			pt.flag = 0;
			index++;
			sCoord = strtok( NULL, " " );
		}
		m_AllPoint.Add(pt);
	}
}

void CKmeansView::OnExecProgram() 
{
	// TODO: Add your command handler code here
	GetAllPoint();

	int i,j;
	//确立第一次核心点
	int flag = (int)(m_numOfPoint/(m_Param+1));
	for(i=0;i<m_Param;i++)
	{
		m_CorePoint.Add(m_AllPoint[flag*(i+1)]);
		iFlag.Add(flag*(i+1));
		m_AllPoint[flag*(i+1)].flag = i+1;
	}

	float E = 0.0;
	float PreE;

	do
	{
		PreE = E;
		E = 0.0;
		float temp[10][10];
		int itemp[10];
		for(i=0;i<m_Param;i++)
		{
			itemp[i]=0;
			for(j=0;j<m_dim;j++)
				temp[i][j]=0.0;
		}

		for(i=0;i<m_numOfPoint;i++)
		{
			float MinDis;
			float Distance;
			for(j=0;j<m_Param;j++)
			{
				Distance = GetDistance(m_AllPoint[i],m_CorePoint[j]);
				if(j==0)
					MinDis = Distance;
				if(Distance<=MinDis)
				{
					m_AllPoint[i].flag = j;
					MinDis = Distance;
				}
			}
			int ij=m_AllPoint[i].flag;
			for(j=0;j<m_dim;j++)
				temp[m_AllPoint[i].flag][j]+=m_AllPoint[i].DimData[j];
			itemp[m_AllPoint[i].flag]++;
		}

		for(i=0;i<m_Param;i++)
			for(j=0;j<m_dim;j++)
			{
				float ff = temp[i][j]/(float)itemp[i];
				m_CorePoint[i].DimData[j]=temp[i][j]/(float)itemp[i];
			}
		for(i=0;i<m_numOfPoint;i++)
		{
			int sign = m_AllPoint[i].flag;
			for(j=0;j<m_dim;j++)
				E = E + (m_AllPoint[i].DimData[j]-m_CorePoint[sign].DimData[j])*(m_AllPoint[i].DimData[j]-m_CorePoint[sign].DimData[j]);
		}
		DrawPoint();
		Sleep(2000);
	}
	while(abs(PreE - E) > m_CheckError);
	this->Invalidate();
}

float CKmeansView::GetDistance(Point pt1,Point pt2)
{
	float distance = 0.0;
	for(int i=0;i<m_dim;i++)
		distance = distance + (pt1.DimData[i]-pt2.DimData[i])*(pt1.DimData[i]-pt2.DimData[i]);
	return(sqrt(distance));
}

void CKmeansView::DrawPoint()
{
	CClientDC dc(this);
	dc.FillSolidRect(0,0,500,500,RGB(255,255,255));
	COLORREF color[10] = {RGB(255,0,0),RGB(100,60,0),RGB(0,80,30),RGB(0,0,255),RGB(121,0,37),RGB(46,48,146),RGB(128,128,0),RGB(128,0,128),RGB(0,128,128),RGB(128,128,128)};
	for(int i=0;i<m_numOfPoint;i++)
	{
		dc.SetPixel((int)(m_AllPoint[i].DimData[0]*500),(int)(m_AllPoint[i].DimData[1]*500),color[m_AllPoint[i].flag]);
	}
	for(i=0;i<m_CorePoint.GetSize();i++)
	{
		float f1=m_CorePoint[i].DimData[0];
		float f2=m_CorePoint[i].DimData[1];
		CBrush brush;
		CBrush *pBrushOld; 
		brush.CreateSolidBrush(RGB(0,0,0));
		pBrushOld= dc.SelectObject(&brush);
		int x,y;
		x = (int)(m_CorePoint[i].DimData[0]*500);
		y = (int)(m_CorePoint[i].DimData[1]*500);
		dc.Ellipse(CRect(x-3,y-3,x+3,y+3));
		brush.DeleteObject();
	}
}

void CKmeansView::OnExecProgram1() 
{
	// TODO: Add your command handler code here
	GetAllPoint();
	//随机选取对象
	randEx(m_numOfPoint,m_Param,1);
	int flag = 1;
	float tempE,E = 0.0;
	int i,j;
	E = GetFirEValue();
	for(i=0;i<m_numOfPoint;i++)
	{
		m_Rand = i;
		E = GetEValue(E);
		DrawPoint();
	//	Sleep(2000);
	}
	DrawPoint();
}

void CKmeansView::randEx(int MAX,int NUM,int FLAG) 
{
	int k=0;
	int j=0;
	time_t t;
	srand((unsigned) time(&t));//设置rand函数所用的启始种子值，以期每次产生的随机数序列均不相同。
	if(FLAG)
	{
		for (k=0;k<NUM;k++)//定制随机数数量。
		{
			m_FirRand.Add(rand()%MAX);//定制随机数在0至最大值之间。
			int ii = m_FirRand[k];
			do  
			{
				for (j=0;j<k;j++) 
					if (m_FirRand[j]==m_FirRand[k])//一次随机数序列中有相同随机数则再产生一个，直至一次随机数序列中随机数全不相同。
					{
						m_FirRand[k]=rand()%MAX;
						break;
					}
			}while(j<k);
			m_AllPoint[m_FirRand[k]].flag=k+1;
			m_CorePoint.Add(m_AllPoint[m_FirRand[k]]);
		}
	}
	else
	{
		do
		{
			m_Rand = rand()%MAX;
			m_Rand = (m_Rand+m_tRand)%MAX;
			for(j=0;j<m_Param;j++)
				if(m_Rand == m_FirRand[j])
					break;
		}while(j<m_Param);
	}
}



float CKmeansView::GetFirEValue()
{
	float E = 0.0;
	int i,j;
	float temp[10][10];
		int itemp[10];
		for(i=0;i<m_Param;i++)
		{
			itemp[i]=0;
			for(j=0;j<m_dim;j++)
				temp[i][j]=0.0;
		}
		for(i=0;i<m_numOfPoint;i++)
		{
			float MinDis;
			float Distance;
			for(j=0;j<m_Param;j++)
			{
				Distance = GetDistance(m_AllPoint[i],m_CorePoint[j]);
				if(j==0)
					MinDis = Distance;
				if(Distance<=MinDis)
				{
					m_AllPoint[i].flag = j;
					m_AllPoint[i].tflag = j;
					MinDis = Distance;
				}
			}

			for(j=0;j<m_dim;j++)
				temp[m_AllPoint[i].flag][j]+=m_AllPoint[i].DimData[j];
			itemp[m_AllPoint[i].flag]++;
		}
		
		for(i=0;i<m_numOfPoint;i++)
		{
			int sign = m_AllPoint[i].flag;
			for(j=0;j<m_dim;j++)
				E = E + (m_AllPoint[i].DimData[j]-m_CorePoint[sign].DimData[j])*(m_AllPoint[i].DimData[j]-m_CorePoint[sign].DimData[j]);
		}
		return E;
}

float CKmeansView::GetEValue(float E)
{
	float *tempE = new float[m_Param];
	float MinE;
	int iflag;
	int i,j,k;
	float temp[10][10];
	int itemp[10];
	for(i=0;i<m_Param;i++)
	{
		itemp[i]=0;
		for(j=0;j<m_dim;j++)
			temp[i][j]=0.0;
	}
	for(i=0;i<m_Param;i++)
	{
		tempE[i] = 0.0;
		Point pt;
		pt = m_CorePoint[i];
		m_CorePoint[i] = m_AllPoint[m_Rand];
		for(j=0;j<m_numOfPoint;j++)
		{
			int sign = m_AllPoint[j].flag;
			//四种情况
			//和替换后的中心点比较
			for(k=0;k<m_Param;k++)
			{
				float MinDis;
				float Distance;
				Distance = GetDistance(m_AllPoint[j],m_CorePoint[k]);
				if(k==0)
					MinDis = Distance;
				if(Distance<=MinDis)
				{
					m_AllPoint[j].flag = k;
					MinDis = Distance;
				}
			}
			for(k=0;k<m_dim;k++)
				temp[m_AllPoint[j].flag][k]+=m_AllPoint[j].DimData[k];
			itemp[m_AllPoint[j].flag]++;
		}
		
		for(k=0;k<m_numOfPoint;k++)
		{
			int sign = m_AllPoint[k].flag;
			for(j=0;j<m_dim;j++)
				tempE[i] = tempE[i] + (m_AllPoint[k].DimData[j]-m_CorePoint[sign].DimData[j])*(m_AllPoint[k].DimData[j]-m_CorePoint[sign].DimData[j]);
		}
		
		//取得最小E值
		if(i == 0)
		{
			iflag = 0;
			MinE = tempE[i];
		}
		else if(tempE[i]<MinE)
		{
			iflag = i;
			MinE = tempE[i];
		}
		m_CorePoint[i]=pt;
		for(k=0;k<m_numOfPoint;k++)
			m_AllPoint[j].flag = m_AllPoint[j].tflag;
	}
	if(MinE > E)
		return E;
	else
	{
		m_CorePoint[iflag] = m_AllPoint[m_Rand];
		for(j=0;j<m_numOfPoint;j++)
		{
			//四种情况
			//和替换后的中心点比较
			for(k=0;k<m_Param;k++)
			{
				float MinDis;
				float Distance;
				Distance = GetDistance(m_AllPoint[j],m_CorePoint[k]);
				if(k==0)
					MinDis = Distance;
				if(Distance<=MinDis)
				{
					m_AllPoint[j].flag = k;
					m_AllPoint[j].tflag = k;
					MinDis = Distance;
				}
			}
		}
		return MinE;
	}
}