聚类算法-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)操作,比较简洁高效。
';