lassification.cpp

分级聚类算法：包括k-mean max-dist min-dist 程序使用方法： 程序中打开文件“.dat”-》选择聚类方法-》显示数据 .dat文件格式： 分成几类 输入样本维数 样本

// lassification.cpp: implementation of the Classification class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "GCluser.h"
#include "lassification.h"

#include <fstream>
#include <iostream>
using namespace std;

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Classification::Classification(const char * lpszPathName)
{
	ifstream fin;
	fin.open(lpszPathName, ios::in);
	if (!fin)
	{
		cerr << "cannot open data file" << endl;
		exit(1);
	}
	
	fin >> NumClass >> NumDimension >> NumSample;
	NumDimension += 1;
	pSample = new int[NumDimension * NumSample];
	int i, j;
	for (i = 0; i < NumSample; i++)
	{
		for (j = 0; j < NumDimension-1; j++)
		{
			fin >> pSample[i * NumDimension + j];
		}
		pSample[i * NumDimension + NumDimension - 1] = i;
	}

	counterClass = NumSample;
	tableDist = NULL;
	ComputeDist();

	pClassList = NULL;
}

Classification::~Classification()
{
	if (pSample != NULL)
	{
		delete[] pSample;
	}
	if (tableDist != NULL)
	{
		delete tableDist;
	}
}

void Classification::ComputeDist()
{
	int i, j, d;
	tableDist = new TriMat<int>(NumSample);
	for (i = 0; i < NumSample; i++)
	{
		for (j = i+1; j < NumSample; j++)
		{
			d = (pSample[i * NumDimension + 0] - pSample[j * NumDimension + 0]) * (pSample[i * NumDimension + 0] - pSample[j * NumDimension + 0])
				+ (pSample[i * NumDimension + 1] - pSample[j * NumDimension + 1]) * (pSample[i * NumDimension + 1] - pSample[j * NumDimension + 1]);
			tableDist->SetElement(d, i, j);
		}
	}
}



void Classification::Cluser(CLUSER_METHOD method)
{
	int i, j;
	DWORD start = GetTickCount();
	while (counterClass > NumClass)
	{
		InitClassList();
		FindClass(i, j, method);
		CombineClass(i, j);
		counterClass--;
	}
	DWORD end = GetTickCount();
	CString s;
	s.Format("计算时间：%ld", end-start);
	AfxMessageBox(s);

	OutputResult();
	ShellExecute(NULL,"open","data.dat",NULL,NULL,SW_SHOWNORMAL);
	return;
}

void Classification::ReleaseList()
{
	if (pClassList)
	{
		for (int i = 0; i < counterClass; i++)
		{
			if (pClassList[i].empty())
			{
				pClassList[i].clear();
			}
		}
		pClassList = NULL;
	}
}

void Classification::InitClassList()
{
	int i;
	ReleaseList();
	pClassList = new ClassList[counterClass];
	for (i = 0; i < NumSample; i++)
	{
		pClassList[pSample[i*NumDimension+NumDimension-1]].push_back(i);
	}
}

void Classification::FindClass(int &ci, int &cj, CLUSER_METHOD method)
{
	int i, j, dist, temp;
	
	TriMat<int> classDist(counterClass);
	//对类循环
	for (i = 0; i < counterClass; i++)
	{
		for (j = i+1; j < counterClass; j++)
		{
			//获得类间距离
			switch (method)
			{
			case MAX_DIST: dist = GetMaxDist(i, j);
				break;
			case MIN_DIST: dist = GetMinDist(i, j);
				break;
			case MEAN_DIST: dist = GetMeanDist(i, j);
				break;
			default: break;
			}
			classDist.SetElement(dist, i, j);
		}
	}
	classDist.FindAbsMin(temp, ci, cj);
/*
	CString s;
	s.Format("%d, %d, %d", temp, ci, cj);
	AfxMessageBox(s);
*/
	return;
}

// distance between class i and class j
int Classification::GetMaxDist(int i, int j)
{
	int dist, max = 0;
	itClassList m, n;

	//两类中的元素比较
	for (m = pClassList[i].begin(); m != pClassList[i].end(); m++)
	{
		for (n = pClassList[j].begin(); n != pClassList[j].end(); n++)
		{
			dist = tableDist->GetElement(*m, *n);
			if (dist > max)
			{
				max = dist;
			}
		}
	}
	return max;
}

int Classification::GetMinDist(int i, int j)
{
	int dist, min = 32767;
	itClassList m, n;
	
	//两类中的元素比较
	for (m = pClassList[i].begin(); m != pClassList[i].end(); m++)
	{
		for (n = pClassList[j].begin(); n != pClassList[j].end(); n++)
		{
			dist = tableDist->GetElement(*m, *n);
			if (dist < min)
			{
				min = dist;
			}
		}
	}
	return min;
}

int Classification::GetMeanDist(int i, int j)
{
	int k;
	double mean = 0;
	itClassList m, n;
	double x1=0, y1=0, x2=0, y2=0;
	
	//两类中的元素比较
	for (k = 0, m = pClassList[i].begin(); m != pClassList[i].end(); m++, k++)
	{
		x1 += pSample[*m * NumDimension + 0];
		y1 += pSample[*m * NumDimension + 1];
	}
	x1 /= k;
	y1 /= k;
	for (n = pClassList[j].begin(); n != pClassList[j].end(); n++)
	{
		x2 += pSample[*n * NumDimension + 0];
		y2 += pSample[*n * NumDimension + 1];
	}
	mean = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
	return (int)mean;
}

void Classification::CombineClass(int i, int j)
{
	pClassList[i].merge(pClassList[j]);
	pClassList[j].clear();
	UpdateSample();
	return;
}

void Classification::UpdateSample()
{
	int i, j = 0;
	itClassList m;
	for (i = 0; i < counterClass; i++)
	{
		while (pClassList[i].empty() && i < counterClass-1)
		{
			i++;
		}
		if (i >= counterClass)
		{
			break;
		}
		for (m = pClassList[i].begin(); m != pClassList[i].end(); m++)
		{
			pSample[*m * NumDimension + NumDimension -1] = j;
		}
		j++;
	}
}

void Classification::OutputResult()
{
	ofstream fout("data.dat");
	int i, j;
	fout << setw(5) << "序号" << setw(5) << "X" << setw(5) << "Y" << setw(8) << "类别" << endl << setw(5);
	for (i = 0; i < NumSample; i++)
	{
		fout << i+1 << setw(5);
		for (j = 0; j < NumDimension-1; j++)
		{
			fout << pSample[i * NumDimension + j] << setw(5);
		}
		fout << pSample[i * NumDimension + NumDimension - 1]+1 << setw(5);
		fout << endl;
	}
}