#include #include #include #include #include // by shenjian 20140620 // qq 396009594 using namespace std; class IElement { public: virtual void PrintSelf() = 0; // 需要业务定义两个样本之间的距离 virtual uint32_t GetDistance(IElement* b) = 0; // 语言要求,无参数构造函数 IElement() { } // 语言要求,虚析构函数 virtual ~IElement() { } // 语言要求,运算符重载 IElement& operator=(const IElement& in); }; class CPoint : public IElement { public: // 必须实现默认无参数构造函数 CPoint() { this->x = 0; this->y = 0; } // 也可以定义自己的构造函数 CPoint(uint32_t x, uint32_t y) { this->x = x; this->y = y; } // 必须定义虚构造函数 virtual ~CPoint() { } // 为了配合测试,必须实现PrintSelf void PrintSelf() { printf("(%u,%u)",x,y); } // 业务的核心,必须实现如何求两个样本之间的距离 uint32_t GetDistance(IElement* b) { CPoint* p = dynamic_cast(b); int32_t xDif = x - p->x; int32_t yDif = y - p->y; return xDif*xDif + yDif*yDif; } // 必须重载运算符 CPoint& operator=(const CPoint& in) { this->x = in.x; this->y = in.y; return *this; } private: // 二维平面上的点 uint32_t x; uint32_t y; }; template class CK_means { public: // 步骤一:初始化 int32_t Init(uint32_t k, const vector& data) { // K过小,或者样本集过小 if(k==0 || k==1 || k>=data.size()) { return -1; } // 初始化K m_k = k; m_result.resize(k); m_center.resize(k); // 初始化质心 for(uint32_t i=0; i& t = m_result[i]; uint32_t tSize = t.size(); // (1.1)遍历每一个样本,保存它作为质心时,该类距离的方差 vector variance; variance.resize(tSize); uint32_t dis = 0; for(uint32_t j=0; j > newResult; newResult.resize(m_k); uint32_t newClass = 0; for(uint32_t i=0; i& t = m_result[i]; uint32_t tSize = t.size(); for(uint32_t j=0; j& t = newResult[i]; uint32_t tSize = t.size(); for(uint32_t j=0; j& t = m_result[i]; uint32_t tSize = t.size(); for(uint32_t j=0; j > m_result; // 保存K个质心 vector m_center; private: // 内部函数:计算两个样本的距离,具体的实现方法是业务方定义的 uint32_t GetDistance(CElement a, CElement b) { return a.GetDistance(&b); } // 内部函数:计算某个样本离哪个质心最近,即找到它所属的分类 uint32_t GetElementNearestCenter(CElement a) { uint32_t minDistance = (uint32_t)(-1); uint32_t minCenter = 0; uint32_t nowDistance = 0; for(uint32_t i=0; i points; points.push_back(CPoint(0,0)); #define NUM (5) #define DEF (50) uint32_t x=0; uint32_t y=0; srand((unsigned)time(NULL)); for(uint32_t i=0;i kmeans; kmeans.Init(3, points); kmeans.Run(); kmeans.PrintResult(); return 0; }