kmeansvview.cpp

实现聚类算法中的K-MEANS算法

// KMeansVView.cpp : implementation of the CKMeansVView class
//

#include "stdafx.h"
#include "KMeansV.h"
#include <stdlib.h>
#include <time.h>
#include <math.h>

#include "KMeansVDoc.h"
#include "KMeansVView.h"
#include "SortDlg.h"

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

/////////////////////////////////////////////////////////////////////////////
// CKMeansVView

IMPLEMENT_DYNCREATE(CKMeansVView, CView)

BEGIN_MESSAGE_MAP(CKMeansVView, CView)
	//{{AFX_MSG_MAP(CKMeansVView)
	ON_WM_LBUTTONDOWN()
	ON_COMMAND(ID_KMEANS_SORT, OnKmeansSort)
	ON_COMMAND(ID_KMEANS_ADD, OnKmeansAdd)
	ON_COMMAND(ID_KMEANS_CLEAR, OnKmeansClear)
	ON_WM_SETCURSOR()
	ON_WM_MOUSEMOVE()
	ON_WM_CONTEXTMENU()
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CKMeansVView construction/destruction

CKMeansVView::CKMeansVView()
{
	// TODO: add construction code here

}

CKMeansVView::~CKMeansVView()
{
}

BOOL CKMeansVView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs
	m_bSorted=FALSE;
	m_bShowCenter=FALSE;
	m_pCenter=NULL;
	m_pRadius=NULL;
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CKMeansVView drawing

void CKMeansVView::OnDraw(CDC* pDC)
{
	CKMeansVDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	CRect Rect;
	::GetClientRect(this->m_hWnd,&Rect);
	pDC->MoveTo(0,Rect.bottom/2);
	pDC->LineTo(Rect.right,Rect.bottom/2);
	pDC->MoveTo(Rect.right/2,0);
	pDC->LineTo(Rect.right/2,Rect.bottom);
	pDC->MoveTo(Rect.right/2,0);
	pDC->LineTo(Rect.right/2-5,5);
	pDC->MoveTo(Rect.right/2,0);
	pDC->LineTo(Rect.right/2+5,5);
	pDC->MoveTo(Rect.right,Rect.bottom/2);
	pDC->LineTo(Rect.right-5,Rect.bottom/2-5);
	pDC->MoveTo(Rect.right,Rect.bottom/2);
	pDC->LineTo(Rect.right-5,Rect.bottom/2+5);

	pDC->SetBkMode(TRANSPARENT);
	pDC->TextOut(Rect.right/2-10,Rect.bottom/2,"O");
	pDC->TextOut(Rect.right-15,Rect.bottom/2,"X");
	pDC->TextOut(Rect.right/2-15,0,"Y");
	int nIndex=GetPointNum();
	if(m_bSorted)
	{
		COLORREF colPnt[]={
			RGB(255,0,0),RGB(0,255,0),RGB(0,0,255),
			RGB(128,128,0),RGB(0,128,128),RGB(128,0,128),
			RGB(128,0,0),RGB(0,128,0),RGB(0,0,128),
			RGB(255,255,0),RGB(0,255,255),RGB(255,0,255)};
		while(nIndex--)
		{
			if(GetPoint(nIndex)->m_nGroupTag<12)
			{
				CPen *pPenOld,PenNew;
				PenNew.CreatePen(PS_SOLID,1,colPnt[GetPoint(nIndex)->m_nGroupTag]);
				pPenOld=pDC->SelectObject(&PenNew);
				pDC->SetTextColor(colPnt[GetPoint(nIndex)->m_nGroupTag]);
				GetPoint(nIndex)->ShowPointWithGroup(pDC);
				pDC->SelectObject(pPenOld);
				PenNew.DeleteObject();
			}
			else
			{
				pDC->SetTextColor(RGB(0,0,0));
				GetPoint(nIndex)->ShowPointWithGroup(pDC);
			}
		}
		if(m_bShowCenter)
		{
			CPen *pPenOld,PenNew;
			CBrush *pBrhOld,BrhNew;
			PenNew.CreatePen(PS_SOLID,1,RGB(255,0,0));
			pPenOld=pDC->SelectObject(&PenNew);
			pBrhOld=(CBrush*)pDC->SelectStockObject(NULL_BRUSH);
			for(int k=0;k<m_nGroupNum;k++)
			{
				pDC->Ellipse(m_pCenter[k].x+Rect.right/2-2,Rect.bottom/2-m_pCenter[k].y-2,m_pCenter[k].x+Rect.right/2+2,Rect.bottom/2-m_pCenter[k].y+2);
				pDC->Ellipse(m_pCenter[k].x+Rect.right/2-m_pRadius[k]-2,Rect.bottom/2-m_pCenter[k].y-m_pRadius[k]-2,m_pCenter[k].x+Rect.right/2+m_pRadius[k]+2,Rect.bottom/2-m_pCenter[k].y+m_pRadius[k]+2);
			}
			pDC->SelectObject(pPenOld);
			pDC->SelectObject(pBrhOld);
			PenNew.DeleteObject();
			BrhNew.DeleteObject();
		}
	}
	else
	{
		while(nIndex--)
			GetPoint(nIndex)->ShowPoint(pDC);
	}
	// TODO: add draw code for native data here
}

/////////////////////////////////////////////////////////////////////////////
// CKMeansVView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CKMeansVView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CKMeansVView message handlers

CPoint CKMeansVView::XYConvert(CPoint point)
{
	CRect Rect;
	::GetClientRect(this->m_hWnd,&Rect);
	CPoint pt;
	pt.x=point.x-Rect.right/2;
	pt.y=Rect.bottom/2-point.y;
	return pt;
}

void CKMeansVView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if(!m_bSorted)
	{
		CClientDC dc(this);
		dc.Ellipse(point.x-1,point.y-1,point.x+1,point.y+1);
		CPoint pt;
		pt=XYConvert(point);
		CString sXY;
		sXY.Format("(%d,%d)",pt.x,pt.y);
		dc.SetBkMode(TRANSPARENT);
		dc.TextOut(point.x,point.y,sXY);
		AddPoint(pt);
		CStatusBar* pStatus=(CStatusBar*)AfxGetApp()->m_pMainWnd->GetDescendantWindow(ID_VIEW_STATUS_BAR);
		CString strN;
		strN.Format("已添加数据点数:%d",GetPointNum());
		pStatus->SetPaneText(0,strN);
	}
	CView::OnLButtonDown(nFlags, point);
}

CDataPoint* CKMeansVView::GetPoint(int nIndex)
{
	if(nIndex<0||nIndex>m_PointArray.GetUpperBound())
		return NULL;
	return m_PointArray.GetAt(nIndex);
}

void CKMeansVView::AddPoint(CPoint pt)
{
	CDataPoint* pPoint=new CDataPoint(pt);
	m_PointArray.Add(pPoint);
}

int CKMeansVView::GetPointNum()
{
	return m_PointArray.GetSize();
}

void CKMeansVView::OnKmeansSort() 
{
	// TODO: Add your command handler code here
	if(GetPointNum()==0)
	{
		MessageBox("没有发现任何数据点!","无法聚类",MB_ICONINFORMATION);
		return;
	}
	CSortDlg SortDlg;
	SortDlg.m_nGroupNum=1;
	SortDlg.m_nParam=10;
	if(SortDlg.DoModal()==IDOK)
	{
		if(SortDlg.m_nGroupNum>GetPointNum())
		{
			MessageBox("分类组数不能超过当前数据点数!","无法聚类",MB_ICONINFORMATION);
			return;
		}
		m_nGroupNum=SortDlg.m_nGroupNum;
		m_bShowCenter=SortDlg.m_bShowCenter;
		//K-MEANS
		int i,j,k,MinTag,MinDistance,Distance,count,sumX,sumY,Gap,Radius,MaxRadius;
		CPoint* pCenterPre=new CPoint[SortDlg.m_nGroupNum];
		m_pCenter=new CPoint[SortDlg.m_nGroupNum];
		m_pRadius=new int[SortDlg.m_nGroupNum];
		srand((unsigned)time(NULL));
		i=GetPointNum();
		for(k=0;k<SortDlg.m_nGroupNum;k++)
		{
			j=rand()%GetPointNum();
			while(j==i)
				j=rand()%GetPointNum();
			m_pCenter[k]=GetPoint(j)->m_ptPoint;
			i=j;
		}
		do
		{
			for(j=0;j<GetPointNum();j++)
			{
				MinTag=0;
				MinDistance=(GetPoint(j)->m_ptPoint.x-m_pCenter->x)*(GetPoint(j)->m_ptPoint.x-m_pCenter->x)+(GetPoint(j)->m_ptPoint.y-m_pCenter->y)*(GetPoint(j)->m_ptPoint.y-m_pCenter->y);
				for(k=1;k<SortDlg.m_nGroupNum;k++)
				{
					Distance=(GetPoint(j)->m_ptPoint.x-(m_pCenter+k)->x)*(GetPoint(j)->m_ptPoint.x-(m_pCenter+k)->x)+(GetPoint(j)->m_ptPoint.y-(m_pCenter+k)->y)*(GetPoint(j)->m_ptPoint.y-(m_pCenter+k)->y);
					if(Distance<MinDistance)
					{
						MinTag=k;
						MinDistance=Distance;
					}
				}
				GetPoint(j)->m_nGroupTag=MinTag;
			}
			Gap=0;
			for(k=0;k<SortDlg.m_nGroupNum;k++)
			{
				pCenterPre[k]=m_pCenter[k];
				count=0;
				sumX=0;
				sumY=0;
				for(j=0;j<GetPointNum();j++)
				{
					if(GetPoint(j)->m_nGroupTag==k)
					{
						count++;
						sumX=sumX+GetPoint(j)->m_ptPoint.x;
						sumY=sumY+GetPoint(j)->m_ptPoint.y;
					}
				}
				if(count>0)
				{
					(m_pCenter+k)->x=sumX/count;
					(m_pCenter+k)->y=sumY/count;
				}
				Gap=Gap+(((m_pCenter+k)->x-(pCenterPre+k)->x)*((m_pCenter+k)->x-(pCenterPre+k)->x)+((m_pCenter+k)->y-(pCenterPre+k)->y)*((m_pCenter+k)->y-(pCenterPre+k)->y));
			}
		}while(Gap>SortDlg.m_nParam);
		delete [] pCenterPre;
		//K-MEANS
		for(k=0;k<SortDlg.m_nGroupNum;k++)
		{
			MaxRadius=0;
			for(j=0;j<GetPointNum();j++)
			{
				if(GetPoint(j)->m_nGroupTag==k)
				{
					Radius=(int)sqrt(((m_pCenter+k)->x-GetPoint(j)->m_ptPoint.x)*((m_pCenter+k)->x-GetPoint(j)->m_ptPoint.x)+((m_pCenter+k)->y-GetPoint(j)->m_ptPoint.y)*((m_pCenter+k)->y-GetPoint(j)->m_ptPoint.y));
					if(Radius>MaxRadius)
						MaxRadius=Radius;
				}
			}
			m_pRadius[k]=MaxRadius;
		}
		m_bSorted=TRUE;
		Invalidate();
		//Count Groups
		int nGroupNumInFact=0;
		CString strResult;
		for(k=0;k<SortDlg.m_nGroupNum;k++)
		{
			for(j=0;j<GetPointNum();j++)
			{
				if(GetPoint(j)->m_nGroupTag==k)
				{
					nGroupNumInFact++;
					break;
				}
			}
		}
		strResult.Format("完成聚类!聚类组数为 %d 组.",nGroupNumInFact);
		MessageBox(strResult,"聚类结果",MB_ICONINFORMATION);
	}
}

void CKMeansVView::OnKmeansAdd() 
{
	// TODO: Add your command handler code here
	m_bSorted=FALSE;
	m_bShowCenter=FALSE;
	Invalidate();
}

void CKMeansVView::OnKmeansClear() 
{
	// TODO: Add your command handler code here
	m_PointArray.RemoveAll();
	m_bSorted=FALSE;
	m_bShowCenter=FALSE;
	Invalidate();
	CStatusBar* pStatus=(CStatusBar*)AfxGetApp()->m_pMainWnd->GetDescendantWindow(ID_VIEW_STATUS_BAR);
	pStatus->SetPaneText(0,"已添加数据点数:0");
}

BOOL CKMeansVView::OnSetCursor(CWnd* pWnd, UINT nHitTest, UINT message) 
{
	// TODO: Add your message handler code here and/or call default
	if(!m_bSorted)
	{
		HCURSOR hcursor;
		hcursor=AfxGetApp()->LoadStandardCursor(IDC_CROSS);
		SetCursor(hcursor);
		return TRUE;
	}
	else
		return CView::OnSetCursor(pWnd, nHitTest, message);
}

void CKMeansVView::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	CString strXY;
	CStatusBar* pStatus=(CStatusBar*)AfxGetApp()->m_pMainWnd->GetDescendantWindow(ID_VIEW_STATUS_BAR);
	if(pStatus)
	{
		CPoint pt;
		pt=XYConvert(point);
		strXY.Format("%d,%d",pt.x,pt.y);
		pStatus->SetPaneText(1,strXY);
	}
	CView::OnMouseMove(nFlags, point);
}

void CKMeansVView::OnContextMenu(CWnd* pWnd, CPoint point) 
{
	// TODO: Add your message handler code here
	CMenu menuPopup;
	BOOL bState;
	bState=m_bSorted;
	if(menuPopup.CreatePopupMenu())
	{
		m_bSorted=TRUE;
		menuPopup.AppendMenu(MF_STRING,ID_KMEANS_SORT,"聚类...");
		menuPopup.AppendMenu(MF_STRING,ID_KMEANS_ADD,"添加数据点");
		menuPopup.AppendMenu(MF_STRING,ID_KMEANS_CLEAR,"清除数据点");
		menuPopup.TrackPopupMenu(TPM_LEFTALIGN,point.x,point.y,this);
	}
	m_bSorted=bState;
}