DBscan算法C++实现
#include<bits/stdc++.h> #define dimense 10 //10维数据 #define N 5005 #define MAX 0xffffff #define clr(a) memset(a,0,sizeof(a)) using namespace std; double radius=60; int min_num=400; int num=5000;//数据量 int k; int now=0;//当前是第几个簇 int ans=0;//不是离群点的簇的数目 struct Point{ int id; double dir[dimense]; int belong; bool iskey; bool vis; int rec;//统计多少个点在其区域内 vector<int>area; }; Point center[15]; vector<Point>data; vector<int>save[15]; double dis(Point a,Point b){ double ret=0; for(int ii=0;ii<dimense;ii++){ ret+=(a.dir[ii]-b.dir[ii])*(a.dir[ii]-b.dir[ii]); } return sqrt(ret); } int cnt=0;//已访问过的总数 void DBscan(int cur){ int i,j; if(data[cur].vis)return; data[cur].vis=true; data[cur].belong=now; cnt++; for(i=0;i<num;i++){ if(data[i].vis)continue; if(dis(data[i],data[cur])<radius){ data[cur].area.push_back(i); data[i].belong=now; data[cur].rec++; } } if(data[cur].rec>min_num){ data[cur].iskey=true; for(i=0;i<data[cur].rec;i++){ DBscan(data[cur].area[i]); } }else data[cur].iskey=false; } set<int>tot; int vis2[N]; void dfs(int a){ if(vis2[a])return; vis2[a]=1; save[now].push_back(a); for(int i=0;i<data[a].rec;i++) dfs(data[a].area[i]); } int main(){ clr(vis2); int i,j; freopen("In.txt","r",stdin); freopen("Out2.txt","w",stdout); for(i=0;i<num;i++){ Point t; t.vis=false; t.id=i; t.rec=0; for(j=0;j<dimense;j++) scanf("%lf",&t.dir[j]); data.push_back(t); } for(i=0;i<num;i++) if(!data[i].vis){ DBscan(i); now++; } now=0; for(i=0;i<num;i++){ if(!vis2[i]){ dfs(i); now++; } } ans=0; int tmp_rec[N]; for(i=0;i<now;i++){ if(save[i].size()>min_num)tmp_rec[ans++]=i; } printf("一共%d个簇\n共:%d点\n",ans,cnt); for(i=0;i<ans;i++){ int len=save[tmp_rec[i]].size(); printf("第%d个簇有%d个点",i+1,len); for(j=0;j<len;j++){ printf("%d%c",save[tmp_rec[i]][j],j==len-1?'\n':' '); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。