C言語:階層的クラスタリング、階層的クラスター分析(未完)
C言語で階層的クラスタリングを書いてます。そもそも「Rを使え」って話なんでしょうけど、使ったことないからわからないんですがベクトルの要素が10000くらいで500個くらいのデータをクラスター分析しようと思ったらとてつもなく時間がかかってしまうような気がします。この前の記事で紹介した集合知プログラミンを少し書き換えて実行してみましたが、終わらない気がしたのでスクリプト言語は諦めました。
今はテスト段階ですが、最終的な仕様として(data1~3.txtの中身は空白で区切ったベクトルの要素が書いてある。注意:要素数は等しいとする。)
./a.out data1.txt data2.txt data3.txt
にするつもりです。メモリの開放とかはとりあえず気にしてません。
#include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX 500 struct clust{ int num; double length; double vec[2]; struct clust *right; struct clust *left; }; struct line{ int point; struct line *next; }; struct clust *clustalloc(void); struct line *linealloc(void); struct clust *makeclust(struct clust **root,int i,int j,double length,int num); double length(struct clust *c1,struct clust *c2); void printclust(struct clust *root); void append(struct line *end,int point); void del(struct line *head,int point); //------------------------------ int main(void){ int num,i; struct clust *mat[MAX],*root,*head,*newc; struct line *lp,*rootline,*headline,*end,*lp2,*lp3,*start,*p; double min,d; int minpair[2]; root=clustalloc(); rootline=linealloc(); headline=NULL; for(num=0;num<10;num++){ mat[num]=clustalloc(); mat[num]->num=num; mat[num]->length=0; mat[num]->vec[0]=rand()%10; mat[num]->vec[1]=rand()%10; mat[num]->right=mat[num]->left=NULL; lp=linealloc(); lp->next=headline; lp->point=num; headline=lp; } end=lp; while(lp!=NULL){ lp=lp->next; } lp=end; while(lp->next->next!=NULL){ min=length(mat[lp->point],mat[lp->next->point]); minpair[0]=lp->point; minpair[1]=lp->next->point; lp2=lp; while(lp2!=NULL){ lp3=lp2->next; while(lp3!=NULL){ d=length(mat[lp2->point],mat[lp3->point]); if(d<=min){ minpair[0]=lp2->point; minpair[1]=lp3->point; newc=makeclust(mat,minpair[0],minpair[1],d,num); min=d; } lp3=lp3->next; } lp2=lp2->next; } del(lp,minpair[0]); del(lp,minpair[1]); append(lp,num); mat[num]=newc; num++; p=end; while(p!=NULL){ p=p->next; } } p=end; root=makeclust(mat,p->point,p->next->point,length(mat[p->point],mat[p->next->point]),num); printclust(root); while(p!=NULL){ p=p->next; } return 0; } //------------------------------// //------------------------------// //------------------------------// //------------------------------// //------------------------------// void printclust(struct clust *root){ static int num=0; int i; struct clust *p; p=root; printf("%d:%lf\n",p->num,p->length); if(p->right!=NULL){ for(i=0;i<num;i++)printf(" "); printf("right->"); printclust(p->right); num++; } if(p->left!=NULL){ for(i=0;i<num;i++)printf(" "); printf("left->"); printclust(p->left); num++; } return; } double length(struct clust *c1,struct clust *c2) { int i; int len=0; for(i=0;i<2;i++) len+=pow((c1->vec[i]-c2->vec[i]),2); return sqrt(len); } void append(struct line *end,int point) { struct line *lp,*new,*lp2; new=linealloc(); new->point=point; lp=end; while(lp!=NULL){ lp2=lp; lp=lp->next; } lp2->next=new; } void del(struct line *head,int point){ struct line *p,*end,*old,*tp,*p2,*p3; p=head; while(p!=NULL){ if(p->point==point){ if(p==head){ p2=head; while(p2->next!=NULL){ p2->point=p2->next->point; p3=p2; p2=p2->next; } free(p3->next); p3->next=NULL; return ; } end=old->next; old->next=end->next; return; } old=p; p=p->next; } } struct clust *makeclust(struct clust **root,int i,int j,double length,int num){ struct clust *newclust; newclust=clustalloc(); newclust->num=num; newclust->right=root[i]; newclust->left=root[j]; newclust->vec[0]=(root[i]->vec[0]+root[j]->vec[0])/2.0; newclust->vec[1]=(root[i]->vec[1]+root[j]->vec[1])/2.0; newclust->length=length; return newclust; } struct clust *clustalloc(void) { return (struct clust *)malloc(sizeof(struct clust)); } struct line *linealloc(void) { return (struct line *)malloc(sizeof(struct line)); }