算法介绍：
k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means 算法基本步骤：
（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；
（2） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（3） 重新计算每个（有变化）聚类的均值（中心对象）；
（4） 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2）。
完整代码如下：
/*简易的K-means算法：对二维整型数据进行聚类 */
#include <iostream>
#include <math.h>
#include <vector>
#define K 3 //预定义划分簇的数目
#define N 7
using namespace std;
//特征对象，表示一个元组，一个元组有两个数值属性
struct Tuple
{
int attr1;
int attr2;
};
Tuple getCentreC(vector<Tuple> e)
{
int num=e.size();
double centreX=0,centreY=0;
Tuple t;
for(int i=0;i<num;i++)
{
centreX +=e[i].attr1;
centreY +=e[i].attr2;
}
t.attr1=centreX/num;
t.attr2=centreY/num;
return t;
}//计算簇的中心点
double getE(vector<Tuple> classes[], Tuple centre[])
{
double sum = 0;
for (int i = 0; i < K; i++)
{
vector<Tuple> v = classes[i];
for (int j = 0; j< v.size(); j++)
{
sum += (v[j].attr1 -centre[i].attr1) * (v[j].attr1 - centre[i].attr1) +
(v[j].attr2 -centre[i].attr2) *(v[j].attr2 - centre[i].attr2);
}
}
cout<<"sum:"<<sum<<endl;
return sum;
}//获取算法的准则函数值，当准则函数收敛时算法停止
int searchMinC(Tuple t,Tuple centre[])
{
int c = 0;
int d = (t.attr1 -centre[0].attr1) * (t.attr1 - centre[0].attr1) +
(t.attr2 - centre[0].attr2) * (t.attr2 - centre[0].attr2);
for (int i = 1; i < K; i++)
{
int temp = (t.attr1 - centre[i].attr1) * (t.attr1 - centre[i].attr1) +
(t.attr2 - centre[i].attr2) * (t.attr2 - centre[i].attr2);
if (temp < d)
{
c = i;
d = temp;
}
}
return c;
}//对象选择距离最小的中心点
void kMeans(vector<Tuple> in)
{
vector<Tuple> classes[K];//定义簇数组，共需划分K个簇
Tuple centre[K];
double newE,oldE = -1;
for(int i=0;i<K;i++)
{
classes[i].push_back(in[i]); //把in的前k个值初始化为k个中心
centre[i]=getCentreC(classes[i]); //计算中心点
cout<<"centre["<<i<<"]:"<<centre[i].attr1<<" "<<centre[i].attr2<<endl;
}
newE=getE(classes,centre);//计算当前准则函数值
cout<<"newE:"<<newE<<" oldE:"<<oldE<<endl;
for(i=0;i<K;i++) //清空每个簇
classes[i].clear();
while(abs(newE-oldE) >= 1)
{
for(i=0;i<in.size();i++) //遍历所有特征对象，将其加入到离它最近的簇
{
int toC=searchMinC(in[i],centre);
classes[toC].push_back(in[i]);
}
cout<<"---------------------"<<endl;
for(i=0;i<K;i++) //打印每个簇的对象
{
vector<Tuple> temp=classes[i];
cout<<"簇"<<i+1<<":"<<endl;
for(int j=0;j<temp.size();j++)
{
cout<<temp[j].attr1<<" "<<temp[j].attr2<<endl;
}
}
cout<<"---------------------"<<endl;
for(i=0;i<K;i++) //更新簇中心
{
centre[i]=getCentreC(classes[i]);
cout<<"centre["<<i<<"]:"<<centre[i].attr1<<" "<<centre[i].attr2<<endl;
}
oldE=newE;
newE=getE(classes,centre);
for(i=0;i<K;i++)
classes[i].clear();
}
}
int main()
{
vector<Tuple> in;
Tuple t[N]={{2,4},{5,1},{65,22},{100,55},{12,8},{11,7},{45,5}};
for(int i=0;i<N;i++)
in.push_back(t[i]);
for(i=0;i<in.size();i++)
cout<<in[i].attr1<<" "<<in[i].attr2<<endl;
kMeans(in);
return 0;
}