程序流程圖：  Hierarchical(MIN)核心功能函數，采用vector<vector<float> >::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 <iostream> #include <sstream> #include <fstream> #include <vector> #include <iterator> #include <cmath> #include <stack> #include <limits> 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<node> 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<<i; sf>>score; return score; } vector<point> openFile(const char* dataset){ fstream file; file.open(dataset,ios::in); if(!file) { cout <<"Open File Failed!" <<endl; vector<point> a; return a; } vector<point> 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!"<<endl; return data; } float squareDistance(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void HierarchicalClustering(vector<point> dataset,int clusters){ //Similarity table：distance table vector<vector<float> > dTable; for(int i=0;i<dataset.size();i++){ vector<float> temp; for(int j=0;j<dataset.size();j++){ if(j>i) temp.push_back(squareDistance(dataset[i],dataset[j])); else if(j<i) temp.push_back(dTable[j][i]); else temp.push_back(0); } dTable.push_back(temp); } int len = dataset.size(); cout<<"len:"<<len<<endl; while(dataset.size()>clusters){ //Merge two closest clusters float minDt =INT_MAX; int mi,mj; for(int i=0;i<dTable.size();i++){ for(int j=i+1;j<dTable[i].size();j++){ if(dTable[i][j]<minDt){ minDt = dTable[i][j]; mi = i; mj = j; } } } for(int i=0;i<dataset[mj].nds.size();i++){ dataset[mi].nds.push_back(dataset[mj].nds[i]); } //rm vector<point>::iterator imj = dataset.begin(); imj += mj; dataset.erase(imj); //Update the dTable for(int j=0;j<dTable.size();j++){ if(j==mi||j==mj) continue; if(dTable[mi][j]>dTable[mj][j]){ dTable[mi][j] = dTable[mj][j]; dTable[j][mi] = dTable[mi][j]; } } //rm vector<vector<float> >::iterator ii = dTable.begin(); ii += mj; dTable.erase(ii); for(int i=0;i<dTable.size();i++){ vector<float>::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.size();i++){ for(int j=0;j<dataset[i].nds.size();j++) clustering<<dataset[i].nds[j].x<<","<<dataset[i].nds[j].y<<","<<i+1<<"\n"; } cout<<dataset.size(); clustering.close(); } int main(int argc, char** argv) { vector<point> dataset = openFile("dataset3.txt"); HierarchicalClustering(dataset,15); return 0; } ~~~ 數據文件格式：（x，y） 運行結果格式：（x，y，cluster） 具體文件格式見DBSCAN篇：http://blog.csdn.net/k76853/article/details/50440182 圖形化展現：  總結： Hierarchical(MIN)算法能夠很好處理非圓形狀的數據。但對于噪音和離群點，Hierarchical(MIN)算法具有局限性。由于層次聚類具有不可恢復性，一旦聚類，就難以撤銷聚類操作，剛開始編碼的時候走了不少彎路，后來果斷決定用數組存儲node信息，方便cluster合并。對于近鄰表的更新，也遇到一點小麻煩，由于二級指針對于行列的刪除比較復雜，果斷采用動態數組vector來存儲距離信息，二級vector對于行的刪除非常直接簡單，對于列的刪除也只需O(n)操作，比較簡潔高效。