vlambda博客
学习文章列表

class point{ public: float x; //x坐标 float y; //y坐标 point() { x = 0;      y = 0; }};

float cal_cluster_distance(vector<point> p1, vector<point> p2){ point m1; for(int i = 0; i < p1.size(); i++) { m1.x += p1[i].x;    m1.y += p1[i].y; }
 m1.x /= p1.size();  m1.y /= p1.size();
 point m2; for(int i = 0; i < p2.size(); i++) { m2.x += p2[i].x;    m2.y += p2[i].y; }
 m2.x /= p2.size();  m2.y /= p2.size();
  float d = sqrt((m1.x-m2.x)*(m1.x-m2.x) + (m1.y-m2.y)*(m1.y-m2.y)); return d;}

/*例如： (A,B) (C,D) (E,F)(A,B) 0 d1 d2(C,D) d3 0 d4(E,F) d5 d6 0*/vector<vector<float>> cal_distance_array(vector<vector<point>> p){ vector<vector<float>> d;
 for(int i = 0; i < p.size(); i++) //计算类集合中所有簇的两两之间的簇距离，组成距离矩阵 { vector<float> tmp; for(int j = 0; j < p.size(); j++) { //如果不是同一个类，则计算不同两个类的中心点的距离作为类的距离 { float dd = cal_cluster_distance(p[i], p[j]); tmp.push_back(dd); } else //如果是同一个类，则距离为0  { tmp.push_back(0); } } d.push_back(tmp); }
 return d;}

void get_min_point(vector<vector<float>> M, int &idx_i, int &idx_j){ float min = 999999999.9999;
 for(int i = 0; i < M.size(); i++) //求距离矩阵中的非零最小值 { for(int j = 0; j < M[i].size(); j++) { if(min > M[i][j] && M[i][j] != 0) min = M[i][j]; } }
 for(int i = 0; i < M.size(); i++) //求非零最小值的两个簇的索引 { for(int j = 0; j < M[i].size(); j++) { if(min == M[i][j]) { if(i < j) //索引较小的簇在簇集合中位于较前面的位置，把索引较大的簇合并到索引较小的簇，当删除索引较大的簇之后，并不影响索引较小簇的索引值，方便重新计算合并后簇的距离 { idx_i = i; idx_j = j; } else { idx_i = j; idx_j = i; } return; }  } }}

void delete_row_col(vector<vector<float>> &d, int idx){ d.erase(d.begin()+idx); //删除第idx行 for(int i = 0; i < d.size(); i++) //删除第idx列 { d[i].erase(d[i].begin()+idx); }}

void combine_cluster(vector<vector<point>> &p, int A_idx, int B_idx){ p[A_idx].insert(p[A_idx].end(), p[B_idx].begin(), p[B_idx].end()); //将簇B合并到簇A  p.erase(p.begin()+B_idx);     //删除类B}

vector<vector<point>> Agnes(vector<point> p, int cluster_num){ vector<vector<point>> pp;  for(int i = 0; i < p.size(); i++)    //初始化每一个点为一个类 { vector<point> tmp; tmp.push_back(p[i]); pp.push_back(tmp); }
  vector<vector<float>> M = cal_distance_array(pp);   //计算类集合的距离矩阵
 int cnt = p.size(); int ii, jj; while(cnt > cluster_num) {    get_min_point(M, ii, jj);  //获取距离矩阵中距离为非零最小值的两个类的索引，ii为较小索引，jj为较大索引    combine_cluster(pp, ii, jj);  //将索引为jj的类合并到索引为ii的类，并删除索引为jj的类    cnt = pp.size();   //经过上一步之后，总类数减1，所以需要更新类计数器cnt的值
 #if 0
 M = cal_distance_array(pp); //重新计算距离矩阵
    #else   //这里完全重新计算距离矩阵也是可以的；或者先删除被合并类所在的行列，然后仅重新计算合并类与其它类的距离也是OK的，理论上后者的效率会更高一点
 delete_row_col(M, jj); //删除jj行与jj列    for(int i = 0; i < cnt; i++)   //合并类的索引号仍为ii，更新在距离矩阵中合并类所在的ii行与ii列 { if(ii == i) { M[ii][i] = 0; } else { float d = cal_cluster_distance(pp[ii], pp[i]); M[ii][i] = d; M[i][ii] = d; }  }
 #endif  }
 return pp;}

int main(void){ float dat[][2]= {{1,1}, {6,5}, {1,1.5}, {11,9.5}, {1.5,1}, {6,5.5}, {10.5,10}, {1.5,1.5}, {1.5,2}                  ,{6,6}, {10,9.5}, {6.5,5}, {10.5,9}, {6.5,5.5}, {2,1.5}, {6.5,6}, {11,10}, {7,6}                  ,{10,9}, {7,5}, {10,10}, {2,2}, {10.5,9.5}, {7,5.5}, {2,1}, {11,9}, {1,2}};  int len = sizeof(dat)/sizeof(dat[0]); vector<point> p;
 for(int i = 0; i < len; i++)  { point tmp; //新建一个类 tmp.x = dat[i][0]; //将数据集写入类中 tmp.y = dat[i][1];  p.push_back(tmp); //将类加入到点集中 }  vector<vector<point>> Clusters = Agnes(p, 3); //设置期望的类总数为3 
 printf("Clusters.size()= %d\n", Clusters.size());
 for(int i = 0; i < Clusters.size(); i++) //打印分类结果 { cout<<"第"<<i+1<<"簇包含的点："<<endl; for(int j = 0; j < Clusters[i].size(); j++) { cout<<" ("<<Clusters[i][j].x<<","<<Clusters[i][j].y<<")"; } cout<<endl; }  return 0;}