#include?
#include?
#include?
#include?
#include?

using?namespace?std;
//?數(shù)據(jù)對象，size為維度
struct?Vector
{
??double*?coords;?//?所有維度的數(shù)值
??int?????size;//數(shù)據(jù)維度
??Vector（）?:??coords（0）?size（0）?{}
??Vector（int?d）?{?create（d）;?}
??//?創(chuàng)建維度為d的數(shù)據(jù)，并將各維度初始化為0
??void?create（int?d）
??{
????size?=?d;
????coords?=?new?double[size];//size維，每一維用double類型表示值
????for?（int?i=0;?i??????coords[i]?=?0.0;
??}
??//?復(fù)制一個數(shù)據(jù)
??void?copy（const?Vector&?other）
??{
????if?（size?==?0）?//?如果原來沒有數(shù)據(jù)，創(chuàng)建之
??????create（other.size）;
?????????
????for?（int?i=0;?i??????coords[i]?=?other.coords[i];
??}
??//?將另一個數(shù)據(jù)的各個維度加在自身的維度上
??void?add（const?Vector&?other）
??{
????for?（int?i=0;?i??????coords[i]?+=?other.coords[i];
??}
??//?釋放數(shù)值的空間
??~Vector（）
??{
????if（coords）
??????delete[]?coords;
????size?=?0;
??}
};
//?聚類結(jié)構(gòu)
struct?Cluster
{
??Vector?center;????//?中心/引力數(shù)據(jù)對象
??int*???member;????//?該聚類中各個數(shù)據(jù)的索引
??int????memberNum;?//?數(shù)據(jù)的數(shù)量
};
?????
//?KMeans算法類
class?KMeans
{
private:
??int??????num;??????????//?輸入數(shù)據(jù)的數(shù)量
??int??????dimen;????????//?數(shù)據(jù)的維數(shù)
??int??????clusterNum;???//?數(shù)據(jù)的聚類數(shù)
??Vector*??observations;?//?所有數(shù)據(jù)存放在這個數(shù)組中
??Cluster*?clusters;?????//?聚類數(shù)組
??int??????passNum;??????//?迭代的趟數(shù)
public:
??//?初始化參數(shù)和動態(tài)分配內(nèi)存
??KMeans（int?n?int?d?int?k?Vector*?ob）
????:?num（n）
?????dimen（d）
?????clusterNum（k）
?????observations（ob）
?????clusters（new?Cluster[k]）
??{
????for?（int?j=0;?j??????clusters[j].member?=?new?int[n];//這里為什么每個聚類的數(shù)據(jù)索引被分配n個指針而不是Cluster.memberNum個？
??}
??//?釋放內(nèi)存
??~KMeans（）
??{
????for?（int?k=0;?k??????delete?[]?clusters[k].member;
????delete?[]?clusters;
??}
?????
??void?initClusters（）
??{
????//?由于初始數(shù)據(jù)中心是任意的，
????//?所以直接把前個數(shù)據(jù)作為NumClusters個聚類的數(shù)據(jù)中心
????for?（int?i=0;?i????{
??????clusters[i].member[0]?=?i;????????????????//?記錄這個數(shù)據(jù)的索引到第i個聚類中
??????clusters[i].center.copy（observations[i]）;?//?把這個數(shù)據(jù)作為數(shù)據(jù)中心
????}
??}
??void?run（）
??{
????bool?converged?=?false;?//?是否收斂
????passNum?=?0;
????while?（!converged?&&?passNum?????????????????????????????????????????//?正常情況下總是會收斂，passNum?????{
??????distribute（）;?????????????????????//?將數(shù)據(jù)分配到聚中心最近的聚類
??????converged?=?recalculateCenters（）;?//?計算新的聚類中心，如果計算結(jié)果和上次相同，認為已經(jīng)收斂
??????passNum++;
????}
??}
??void?distribute（）
??{
????//?將上次的記錄的該聚類中的數(shù)據(jù)數(shù)量清0，重新開始分配數(shù)據(jù)
????for（int?k=0;?k??????getCluster（k）.memberNum?=?0;
????//?找出每個數(shù)據(jù)的最近聚類數(shù)據(jù)中心，并將該數(shù)據(jù)分配到該聚類
????for（int?i=0;?i????{
??????Cluster&?cluster?=?getCluster（closestCluster（i））;?//?找出最接近的其中心的聚類
??????int?memID?=?cluster.memberNum;?//?memberNum是當前記錄的數(shù)據(jù)數(shù)量，也是新加入數(shù)據(jù)在member數(shù)組中的位置
??????cluster.member[memID]?=?i;?????//?將數(shù)據(jù)索引加入Member數(shù)組
??????cluster.memberNum++;???????????//?聚類中的數(shù)據(jù)數(shù)量加1
????}
??}
??int?closestCluster（int?id）
??{
????int?clusterID?=?0;???????????????//?暫時假定索引為id的數(shù)據(jù)最接近第一個聚類
????d