聚类算法-Hierarchical(MIN)-C++

最后更新于:2022-04-01 20:31:28

程序流程图: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-04-21_57187d6e43044.jpg) Hierarchical(MIN)核心功能函数,采用vector >::dTable存储两点之间的距离。计算每两个point间的距离并保存到distance table中;判断是否达到需要聚类的cluster数量,若是,将point信息写入clustering文件,程序结束。否则,合并两个具有最小距离的point,将两个point中的所有node全部加入到一个point中,删除拷贝node数组后的多余point,跟新dataset数组。然后更新distance table,删除被合并point对应的distance table中行与列,进入下一步循环。 ~~~ /* K-means Algorithm 15S103182 Ethan */ #include #include #include #include #include #include #include #include using namespace std; class node{ public: float x; float y; node(float a,float b){ x = a; y = b; } }; class point{ public: float x; float y; vector nds; point (float a,float b){ x = a; y = b; node t(a,b); nds.push_back(t); } }; float stringToFloat(string i){ stringstream sf; float score=0; sf<>score; return score; } vector openFile(const char* dataset){ fstream file; file.open(dataset,ios::in); if(!file) { cout <<"Open File Failed!" < a; return a; } vector data; while(!file.eof()){ string temp; file>>temp; int split = temp.find(',',0); point p(stringToFloat(temp.substr(0,split)),stringToFloat(temp.substr(split+1,temp.length()-1))); data.push_back(p); } file.close(); cout<<"Read data successfully!"< dataset,int clusters){ //Similarity table:distance table vector > dTable; for(int i=0;i temp; for(int j=0;ji) temp.push_back(squareDistance(dataset[i],dataset[j])); else if(jclusters){ //Merge two closest clusters float minDt =INT_MAX; int mi,mj; for(int i=0;i::iterator imj = dataset.begin(); imj += mj; dataset.erase(imj); //Update the dTable for(int j=0;jdTable[mj][j]){ dTable[mi][j] = dTable[mj][j]; dTable[j][mi] = dTable[mi][j]; } } //rm vector >::iterator ii = dTable.begin(); ii += mj; dTable.erase(ii); for(int i=0;i::iterator ij = dTable[i].begin(); ij += mj; dTable[i].erase(ij); } } fstream clustering; clustering.open("clustering.txt",ios::out); for(int i=0;i dataset = openFile("dataset3.txt"); HierarchicalClustering(dataset,15); return 0; } ~~~ 数据文件格式:(x,y) 运行结果格式:(x,y,cluster) 具体文件格式见DBSCAN篇:http://blog.csdn.net/k76853/article/details/50440182 图形化展现: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-04-21_57187d6e5a775.jpg) 总结: Hierarchical(MIN)算法能够很好处理非圆形状的数据。但对于噪音和离群点,Hierarchical(MIN)算法具有局限性。由于层次聚类具有不可恢复性,一旦聚类,就难以撤销聚类操作,刚开始编码的时候走了不少弯路,后来果断决定用数组存储node信息,方便cluster合并。对于近邻表的更新,也遇到一点小麻烦,由于二级指针对于行列的删除比较复杂,果断采用动态数组vector来存储距离信息,二级vector对于行的删除非常直接简单,对于列的删除也只需O(n)操作,比较简洁高效。
';