simplekmeans.cpp

K-Means C++实现 带演示程序 K-Means C++实现 带演示程序

#include <iostream>
#include <list>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include "SimpleKMeans.h"

using namespace std;

#define RANDMAX 100
#define random(x) (rand()%x)
#define INFINITE_DISTANCE 1.0 / 1.0e-12
#define DOUBLE_MINIMUM 0.0/1.0
#define DOUBLE_MAXIMUM INFINITE_DISTANCE

typedef struct Dot
{
	double x;
	double y;
	bool isMean;	//是否聚类中心
	bool isVirtual;	//是否虚拟聚类中心
} Dot2D, *Ptr_Dot2D;

void ForeachHandler(const Dot2D& currdot)
{
	cout << currdot.x << "," << currdot.y << endl;
}

bool CountifHandler(const Dot2D& currdot)
{
	return currdot.x <= 20 && currdot.y <= 20;
}

//数据预处理函数
vector<Dot2D> PreProcessor(double* rawData, int count)
{
	int i;
	vector<Dot2D> tmpList;

	for (i = 0; i < count; i++)
	{
		Dot2D dot;

		dot.x = *(rawData + i);
		dot.y = *(rawData + i + count);
		dot.isMean = false;
		dot.isVirtual = false;
		tmpList.push_back(dot);
	}
	return tmpList;
}

/*
* 计算两点间距离
*/
double Distance(Dot2D dot1, Dot2D dot2)
{
	return sqrt(pow(fabs(dot1.x - dot2.x),2.0) + pow(fabs(dot1.y - dot2.y), 2.0));
}

bool CountifHandler(Dot2D dot)
{
	return !dot.isVirtual;
}

/*
* dots:原始数据
* indexed:聚类数据点的索引值
*/
vector<double> FindMaxMinValues(const vector<Dot2D> dots, const vector<int> indexes)
{
	int i;
	vector<double> maxmin;

	if (indexes.size() == 0)
	{
		maxmin.push_back(0);	//max_x
		maxmin.push_back(0);	//max_y
		maxmin.push_back(0);	//min_x
		maxmin.push_back(0);	//min_y
	}
	else
	{
		maxmin.push_back(DOUBLE_MINIMUM);	//max_x
		maxmin.push_back(DOUBLE_MINIMUM);	//max_y
		maxmin.push_back(DOUBLE_MAXIMUM);	//min_x
		maxmin.push_back(DOUBLE_MAXIMUM);	//min_y

		for (i = 0; i < indexes.size(); i++)
		{
			maxmin[0] = dots[indexes[i]].x > maxmin[0] ? dots[indexes[i]].x : maxmin[0];
			maxmin[1] = dots[indexes[i]].y > maxmin[1] ? dots[indexes[i]].y : maxmin[1];
			maxmin[2] = dots[indexes[i]].x < maxmin[2] ? dots[indexes[i]].x : maxmin[2];
			maxmin[3] = dots[indexes[i]].y < maxmin[3] ? dots[indexes[i]].y : maxmin[3];
		}
	}

	return maxmin;
}

/*
* @Author:YinPSoft
* @param:
* raw: 原始数据
* count: 数据点个数
* K: 聚类中心个数
* means: 初始聚类中心,将初始聚类中心作为参数的目的在于可以通过另外的方法选择初始聚类中心，初始聚类中心的选择对处理过程有很大影响
* minOffset: 聚类中心的最小偏移量，用于控制聚类处理的精度。
* times: 最大迭代次数
*/
void DataMining_KMeans(double* raw, 
					   int count, 
					   int K, 
					   int* means, 
					   double minOffset, 
					   int times, 
					   int* retValues, 
					   int* clustersSize, 
					   double* finalMeans)
{
	int i,j;
	int c;
	double dist,term;
	bool flag = true;
	int amount = 0;
	
	//对原始数据进行预处理，将双精度的一维数组转换成分析处理需要的结构数组
	vector<Dot2D> dots = PreProcessor(raw, count);
	vector<vector<int>> clusters;	//聚类容器，用于存放某聚类数据点的索引值
	vector<int> meanIndex;	//用于存放聚类中心的索引值
	vector<double> maxminvalues;
	Dot2D newMean;

	for (i = 0; i < K; i++)
	{
		//初始化聚类容器
		vector<int> cluster;
		clusters.push_back(cluster);

		meanIndex.push_back(*(means + i));		//从参数设置初始聚类中心
		dots.at(*(means+i)).isMean = true;
		dots.at(*(means+i)).isVirtual = false;
	}
	
	while((flag && times == -1) || (flag && times != -1 && (++amount) <= times))
	{
		flag = false;

		for (i = 0; i < K; i++)
		{
			clusters.at(i).clear();
		}

		for (i = 0; i < count; i++)
		{
			if (!dots.at(i).isMean && !dots.at(i).isVirtual)
			{
				dist = INFINITE_DISTANCE;
				for (j = 0; j < K; j++)
				{
					//计算数据点与聚类中心的逻辑距离
					term = Distance(dots[i], dots[meanIndex[j]]);
					if (term < dist)
					{
						dist = term;

						//用于存放与聚类中心有最小距离的那个数据点的索引值
						//这里没有直接将这个值存入clusters对象，目的在于提高效率，
						//因为与直接将这个索引值存入一个间接变量比较起来
						//对向量对象的索引赋值要花费更多的时间
						c = j;
					}
				}

				clusters.at(c).push_back(i);	//将第i个数据点放入第j个聚类
			}
		}

		for (i = 0; i < K; i++)
		{
			//FindMaxMinValues函数通过一次循环将两个维度的最大值和最小值都求出来，可以提高效率
			//但对于任意多维的情况要另行处理
			maxminvalues = FindMaxMinValues(dots, clusters.at(i));			
			newMean.x = (maxminvalues.at(0) + maxminvalues.at(2)) / 2.0;
			newMean.y = (maxminvalues.at(1) + maxminvalues.at(3)) / 2.0;
			newMean.isMean = true;
			newMean.isVirtual = true;
			term = Distance(newMean, dots[meanIndex[i]]);
			flag = (term > minOffset) ? true : flag;

			//这里如果不将聚类中心点标识设置为false的话，会导致最后的结果中缺少数据点，而且缺少的数据点的个数等于聚类个数
			dots.at(meanIndex.at(i)).isMean = false;
			dots.push_back(newMean);
			
			*(finalMeans+i) = newMean.x;
			*(finalMeans+i+K) = newMean.y;
			
			meanIndex.at(i) = dots.size() - 1;
		}		
	}

	amount = 0;
	for (i = 0; i < K; i++)
	{
		for (j = 0; j < clusters.at(i).size(); j++)
		{
			*(retValues+amount)=clusters.at(i).at(j);
			amount++;
		}

		*(clustersSize+i) = clusters.at(i).size();
	}
}

//
int main()
{
	vector<Dot2D> dots;
	Dot2D dot;
	dot.x = 1; dot.y = 2;
	dots.push_back(dot);
	cout << dots[0].x << " " << dots[0].y<<endl;
	cout << dots.size() << " " << dots.capacity()<<endl;
	system("PAUSE");
	return 0;
}