📄 mcamda.cpp
字号:
for(i=1;i<=k;i++)
{
if(dis[label][i]<midmin) midmin=dis[label][i];
}
dis[label][0]=midmin; //对一个点，用dis[label][0]记录它到各个聚类中心距离的最小值
if(dis[label][0]>distance_max)
{
distance_max=dis[label][0];
distance_max_label=label;
}
}
k++;
z1[k].x=center_collect[distance_max_label].x;
z1[k].y=center_collect[distance_max_label].y;
z1[k].f=k;
for(i=1;i<k-1;i++)
{
midsum=midsum+sqrt(pow((z1[i].x-z1[i+1].x),2)+pow((z1[i].y-z1[i+1].y),2));
}
average=midsum/(k-2);
}while( distance_max>0.34*average); //结束条件有待改进
k=k-1; //循环条件结束则最后一个聚类中心不符合要求
CN=k;
printf("合并前的聚类个数=%d\n",CN);
long Time2=GetTickCount();
k_means_progress();
/////////////////////////求得每个聚类中心包含的数据点个数
for(i=1;i<=CN;i++)
{
count=0;
for(j=1;j<=label_trace;j++)
{
if(s[j].f==i) count++;
}
z1[i].num=count;
}
for(i=1;i<=CN;i++)
{
z1[i].num=z1[i].num;
}
////////////////////////
long TimeMergebefor=GetTickCount();
////////////////////////////////////首先计算类间平均距离averageD
double sumD=0,averageD=0;
int num=0;
for(i=1;i<=CN;i++)
for(j=i+1;j<=CN;j++){
sumD=sumD+sqrt(pow((z1[i].x-z1[j].x),2)+pow((z1[i].y-z1[j].y),2));
num++;
}
averageD=sumD*pow(num,-1);
//printf("averageD=%lf\n",averageD);
distance=0;
Q=(Linklist)malloc(sizeof (LNode));
Q->next=NULL; //先建立一个带头结点的单链表
Q->prior=NULL;
Q->distance=-1;
Q->cluster1=-1;
Q->cluster2=-1;
Linklist Qend;
Linklist Qsearch;
Linklist Qnew;
for(i=1;i<=CN;i++)
for(j=i+1;j<=CN;j++){ //定义小类合并队列Q,链表,便于插入删除操作
distance=sqrt(pow((z1[i].x-z1[j].x),2)+pow((z1[i].y-z1[j].y),2));
if(distance<averageD){
Qnew=(Linklist)malloc(sizeof (LNode)); //生成一个新的结点
Qnew->distance=distance;
if(z1[i].num<z1[j].num){
Qnew->cluster1=i;
Qnew->cluster2=j;
}else{
Qnew->cluster1=j;
Qnew->cluster2=i;
}
Qnew->next=NULL;
Qnew->prior=NULL;
if(Q->next==NULL){ //插入第一个时
Qend=Qnew;
Q->next=Qend;
Qend->prior=Q;
}else{ //第二个以后,Qend为指向最后一个结点的指针
if((Qnew->distance)>=(Qend->distance)){ //直接向后插入
Qend->next=Qnew;
Qnew->prior=Qend;
Qend=Qnew;
}else{
Qsearch=Qend->prior;
while((Qsearch->distance > Qnew->distance)&&(Qsearch->prior!=NULL)){//向前查找第一个比p->distance小的结点
Qsearch=Qsearch->prior;
}
Qnew->next=Qsearch->next;
Qsearch->next->prior=Qnew;
Qsearch->next=Qnew;
Qnew->prior=Qsearch;
}
}
}
}
Qsearch=Q->next;
printf("需要判断合并的小类对:");
while(Qsearch!=NULL){
printf("%d,%d ",Qsearch->cluster1,Qsearch->cluster2);
Qsearch=Qsearch->next;
}
printf("\n");
//////////////////////////////////////////////////////一些结构的定义
Span=(Linklist2)malloc(sizeof (LNode2));
Span->next=NULL;
Span->prior=NULL;
Span->label=-1;
Span->possition_mergeaera=-1;
Span->x=-1;
Span->y=-1;
/////////////////////////////////////////////////对队列Q中的所有小类对进行合并判断
Qsearch=Q->next; //取出Q中的一对小类对
while(Qsearch!=NULL){
Qsearch->cluster1=Qsearch->cluster1;
Qsearch->cluster2=Qsearch->cluster2;
for(i=1;i<=N;i++){
mergeaera[i].label=0;
mergeaera[i].x=0;
mergeaera[i].y=0;
mergeaera[i].inspecttag=-1;
}
coreseed.x=z1[Qsearch->cluster1].x;
coreseed.y=z1[Qsearch->cluster1].y;
coreseed.label=-1;
mergeaera[1].x=z1[Qsearch->cluster2].x; //目标对象
mergeaera[1].y=z1[Qsearch->cluster2].y;
mergeaera[1].label=-2;
j=1;
R=sqrt(pow((coreseed.x-mergeaera[1].x),2)+pow((coreseed.y-mergeaera[1].y),2));
for(i=1;i<=label_trace;i++){
if(s[i].f==Qsearch->cluster1){ //将属于该小类对的点存放在数组mergeaera[]中
distance=sqrt(pow((s[i].x-mergeaera[1].x),2)+pow((s[i].y-mergeaera[1].y),2));;
if(distance<=R){
j++;
mergeaera[j].label=i;
mergeaera[j].x=s[i].x;
mergeaera[j].y=s[i].y;
}
}else if(s[i].f==Qsearch->cluster2){
distance=sqrt(pow((s[i].x-coreseed.x),2)+pow((s[i].y-coreseed.y),2));;
if(distance<=R){
j++;
mergeaera[j].label=i;
mergeaera[j].x=s[i].x;
mergeaera[j].y=s[i].y;
}
}
}
j++;
mergeaera[j].label=-10000; //用这个特殊的字符来表示数组结束
i=1;
j=0;
distance=0;
while(mergeaera[i].label!=-10000){
if(coreseed.label!=mergeaera[i].label){
distance=sqrt(pow((coreseed.x-mergeaera[i].x),2)+pow((coreseed.y-mergeaera[i].y),2));
if(distance<=Eps){
if(j==0){
temp=(Linklist3)malloc(sizeof (LNode3));
temp->next=NULL;
temp->label=mergeaera[i].label;
temp->possition_mergeaera=i;
temp->x=mergeaera[i].x;
temp->y=mergeaera[i].y;
tempsearch=temp;
j++;
}else{
tempnew=(Linklist3)malloc(sizeof (LNode3));
tempnew->next=NULL;
tempnew->label=mergeaera[i].label;
tempnew->possition_mergeaera=i;
tempnew->x=mergeaera[i].x;
tempnew->y=mergeaera[i].y;
tempsearch->next=tempnew;
tempsearch=tempnew;
j++; //j表示temp数组中对象的个数
}
}
}
i++;
}
//////////////////////
path=NULL;
path=(Linklist4)malloc(sizeof (LNode4)); //////////////
path->next=NULL;
path->label=-1;
path->x=coreseed.x;
path->y=coreseed.y;
pathsearch=path;
///////////////
tempsearch=temp;
while(tempsearch->next!=NULL){ //将临时数组中的点放入扩展队列Span中,作为考察对象
possition=tempsearch->possition_mergeaera;
mergeaera[possition].inspecttag=1; //把临时数组中考察对象在mergeaera[]中标记出来
Linklist2 Spanp;
Spanp=(Linklist2)malloc(sizeof (LNode2));
Spanp->next=NULL;
Spanp->prior=NULL;
Spanp->label=tempsearch->label;
Spanp->possition_mergeaera=tempsearch->possition_mergeaera;
Spanp->x=tempsearch->x;
Spanp->y=tempsearch->y;
if(Span->next==NULL){
Spanpend=Spanp;
Span->next=Spanpend;
Spanpend->prior=Span;
}else{
Spanpend->next=Spanp;
Spanp->prior=Spanpend;
Spanpend=Spanp;
}
tempsearch=tempsearch->next;
}
free(temp);//将temp删除
temp=NULL;
////////////////////////////////////////////////开始扩展了
Spanp=Span->next;
while((Spanp!=NULL)&&(mergesuccess!=1)){
i=1;
j=0;
while(mergeaera[i].label!=-10000){
if(Spanp->label!=mergeaera[i].label){
distance=sqrt(pow((Spanp->x-mergeaera[i].x),2)+pow((Spanp->y-mergeaera[i].y),2));
if(distance<=Eps){
if(j==0){
temp=(Linklist3)malloc(sizeof (LNode3));
temp->next=NULL;
temp->label=mergeaera[i].label;
temp->possition_mergeaera=i;
temp->x=mergeaera[i].x;
temp->y=mergeaera[i].y;
tempsearch=temp;
j++;
}else{
tempnew=(Linklist3)malloc(sizeof (LNode3));
tempnew->next=NULL;
tempnew->label=mergeaera[i].label;
tempnew->possition_mergeaera=i;
tempnew->x=mergeaera[i].x;
tempnew->y=mergeaera[i].y;
tempsearch->next=tempnew;
tempsearch=tempnew;
j++; //j表示temp数组中对象的个数
} //end of if(j==0)
}//end of if(distance<=Eps)
}
i++;
} //end of while(mergeaera[i].label!=-10000)
////////////////////////////
pathnew=(Linklist4)malloc(sizeof (LNode4));
pathnew->next=NULL;
pathnew->label=Spanp->label;
pathnew->x=Spanp->x;
pathnew->y=Spanp->y;
pathsearch->next=pathnew;
pathsearch=pathnew;
/////////////////////////////////
tempsearch=temp;
if(j>=Minpts){ //Span链表的第一个结点为核心点
while((tempsearch->next!=NULL)&&(mergesuccess!=1)){
if(tempsearch->label!=mergeaera[1].label){
possition=tempsearch->possition_mergeaera;
if(mergeaera[possition].inspecttag!=1){ //说明还不是考察对象
mergeaera[possition].inspecttag=1;
Linklist2 Spanp2; //插入扩展链表Span
Spanp2=(Linklist2)malloc(sizeof (LNode2));
Spanp2->next=NULL;
Spanp2->prior=NULL;
Spanp2->label=tempsearch->label;
Spanp2->possition_mergeaera=tempsearch->possition_mergeaera;
Spanp2->x=tempsearch->x;
Spanp2->y=tempsearch->y;
Spanpend->next=Spanp2;
Spanp2->prior=Spanpend;
Spanpend=Spanp2;
}
}else{
mergesuccess=1; //算法结束
}
tempsearch=tempsearch->next;
}
} //end of if
//再将第一个结点删除
if(Spanp->next!=NULL){
Spanp->prior->next=Spanp->next;
Spanp->next->prior=Spanp->prior;
free(Spanp);
Spanp=NULL;
Spanp=Span->next;
}else{
Spanp->prior->next=Spanp->next;
free(Spanp);
Spanp=NULL;
Spanp=Span->next;
}
free(temp);//将temp删除
temp=NULL;
} //end of while((Spanp->next!=NULL)&&(mergesuccess!=1))
if(mergesuccess==1){
Qsearch->mergesuccess=1;
}else{
Qsearch->mergesuccess=-1;
}
Qsearch=Qsearch->next; //指针往后移
mergesuccess=0;
} //end of while(Qsearch!=NULL)
///////////////打印最终所有小类对的合并结果
flag=0;
printf("These clusters can be merged successfully:\n");
Qsearch=Q->next;
while(Qsearch!=NULL){
if(Qsearch->mergesuccess==1){
flag=1;
}
Qsearch=Qsearch->next;
}
if(flag!=1){
printf("none.\n");
}
long TimeMergeafter=GetTickCount();
printf("初值优化算法时间: %0.3f s\n",(float)(Time2-TimeStart)/1000);
printf("K-MEANS算法时间: %0.3f s\n",(float)(TimeMergebefor-Time2)/1000);
printf("小类合并算法时间: %0.3f s\n",(float)(TimeMergeafter-TimeMergebefor)/1000);
printf("总的运行时间: %0.3f s\n",(float)(TimeMergeafter-TimeStart)/1000);
////////////////////////////////// 聚类结果的可视化及文档保存
outfp=fopen(filename2,"w");
HDC hdc;
hdc=CreateDC("DISPLAY",NULL,NULL,NULL);
int xx,yy;
for(yy=500;yy>30;yy--)
for(xx=100;xx<600;xx++) SetPixel(hdc,xx,yy,0xffffff); //以（300，300）为坐标原点
for(i=1;i<=CN;i++)
{
fprintf(outfp,"the %d class center is: ",i);
fprintf(outfp,"%f,",z1[i].x);
fprintf(outfp,"%f.\n",z1[i].y);
if(i==1) rgbColor=RGB(255,0,0); //大红
if(i==2) rgbColor=0x000000; //黑色
if(i==3) rgbColor=RGB(0,132,0); //绿色
if(i==4) rgbColor=0x00ffff; //鲜黄色
if(i==5) rgbColor=RGB(0,128,255); //蓝色
if(i==6) rgbColor=RGB(255,100,26); //橙色
if(i==7) rgbColor=RGB(255,0,255); //水红色
if(i==8) rgbColor=RGB(4,190,244); //亮蓝色
if(i==9) rgbColor=0x88ff33; //鲜绿
if(i==10) rgbColor=0x3493af; //土黄
if(i==11) rgbColor=0x005555; //棕绿
if(i==12) rgbColor=RGB(4,190,244); //亮蓝色
SetPixel(hdc,300+z1[i].x*100,300-z1[i].y*100,rgbColor);
SetPixel(hdc,300+z1[i].x*100-1,300-z1[i].y*100,rgbColor);
SetPixel(hdc,300+z1[i].x*100+1,300-z1[i].y*100,rgbColor);
SetPixel(hdc,300+z1[i].x*100,300-z1[i].y*100-1,rgbColor);
SetPixel(hdc,300+z1[i].x*100,300-z1[i].y*100+1,rgbColor);
count=0;
for(l=1;l<=label_trace;l++)
{
if(s[l].f==i)
{
count++;//print each class data
fprintf(outfp,"%f,",s[l].x);
fprintf(outfp,"%f\n",s[l].y);
SetPixel(hdc,300+s[l].x*100,300-s[l].y*100,rgbColor);
}
}
fprintf(outfp,"该类有%d个点.\n",count);
}
fclose(outfp);
}//end of main
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -