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

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