gen_subset.c

来自「vc的源代码程序的基于最小特征向量的元素的集合方法的程序源代码」· C语言 代码 · 共 229 行

#include <stdio.h>
#include <math.h>
#define no_fea 6
#define datafile "monk3.data"
#define no_ex 122
#define no_class 2/* make sure class values are starting from 0 */

FILE *fp;
int asked_no,subset[no_fea],data_ar[no_ex][no_fea],class[no_ex];
int mark[no_ex],min_fea_val[no_fea],fea_arity[no_fea],max_fea_val[no_fea];
float info;
main()
{
 struct node{
  int num;
  int beg_num;
  int max_num;
  struct node *next,*pre;
 };
  int i,j,x,final_asked_no;
  struct node *p,*start,*last,*temp_p;
  float incon_cal();
  int min_subset[no_fea];
  float min_info; 
 
  /* read data from datafile to data_ar & class */

  fp=fopen(datafile,"r");
  i=0;
  while(!feof(fp) && i<no_ex) {
    for(x=0;x<no_fea;x++) 
      fscanf(fp,"%d",&data_ar[i][x]);
    if(!feof(fp))
      fscanf(fp,"%d",&class[i]);
    i++;
  }

  /* find min_fea_val[] and fea_arity[] */

  /* initialize min_fea_val[] and fea_arity[] */
  for(i=0;i<no_fea;i++) {
    fea_arity[i]=0;min_fea_val[i]=no_fea+1;max_fea_val[i]=0;
  }

  for(i=0;i<no_ex;i++) { /* for all patterns */
    for(j=0;j<no_fea;j++) {
      if(data_ar[i][j]<min_fea_val[j])
        min_fea_val[j]=data_ar[i][j];

      if(data_ar[i][j]>max_fea_val[j])
        max_fea_val[j]=data_ar[i][j];
    }
  }
  for(i=0;i<no_fea;i++)
    fea_arity[i]=max_fea_val[i]-min_fea_val[i]+1;      

  /* Initialize the mark for all patterns to zero signifying not yet searched*/

  for(i=0;i<no_ex;i++)
    mark[i]=0;

  /* initialize min_info and min_subset and final_asked_no */

  min_info=100.0;/* an arbitrarily high value */
  for(i=0;i<asked_no;i++)
    min_subset[i]=-1;
  final_asked_no=0;

  /* for all subsets exhaustively */

  for(asked_no=1;asked_no<=no_fea;asked_no++) {
  /*   printf("asked_no=%d\n",asked_no); */

  /* generate the start node which contains no info. */
    p=(struct node *)malloc(sizeof(struct node));
    start=p;p->pre=NULL;p->num=-1;

  /* allocate for asked_no of features */
    for(i=0;i<asked_no;i++) {
      temp_p=p;
      p=(struct node *)malloc(sizeof(struct node));
      p->pre=temp_p;temp_p->next=p;p->beg_num=i;p->num=i;
      p->max_num=no_fea-asked_no+i;
    }

  /* generate the last node which contains no info. */
    temp_p=p;
    p=(struct node *)malloc(sizeof(struct node));
    p->pre=temp_p;temp_p->next=p;p->num=-1;
    last=p;p->next=NULL;p=last->pre;

    /*  output the first subset  */
    temp_p=start->next;i=0;
    while(temp_p->next!=NULL) {
      subset[i]=temp_p->num;i++;temp_p=temp_p->next;
    }
    for(i=0;i<asked_no;i++)
      printf("%d  ",subset[i]);
    printf("\n");
    
    /* call incon_cal */
    info=incon_cal();

    /* compare with min_info and replace if satisfy */
    if(info<min_info) {
      for(i=0;i<asked_no;i++) 
	min_subset[i]=subset[i];
      min_info=info;
      final_asked_no=asked_no;
    }

    /* generate exhaustively */
    while(p!=start) {
      if(p->num<p->max_num) {
        p->num++;x=p->num;
        while(p->next!=last) {
          p=p->next;
          p->num=++x;
        }

        /*  output the nest subset  */
        temp_p=start->next;i=0;
        while(temp_p->next!=NULL) {
          subset[i]=temp_p->num;i++;temp_p=temp_p->next;
        }
       
        /* call incon_cal */
        info=incon_cal();

        /* comapare with min_info and replace if satisfy */
        if(info<min_info) {
          for(i=0;i<asked_no;i++) 
            min_subset[i]=subset[i];
          min_info=info;
          final_asked_no=asked_no;
        }

        for(i=0;i<asked_no;i++)
          printf("%d  ",subset[i]);
        printf("\n");
      }
      else
        p=p->pre;
    }
  }
 printf("min_info=%f\n",min_info);
 printf("The subset is :- ");
 for(j=0;j<final_asked_no;j++)
   printf("%d  ",min_subset[j]+1);
 printf("\n");
}







/* inconsistency calculation for each subset */
/* it is log base 2 of sum of all exceptions for a subset */

float incon_cal()
{
 int i,j;
 int pattern[no_fea];/*used for searching a pattern given a subset of features*/
 int class_val[no_class];/*used for counting the no. of patterns in different
			   classes */
 int checked,match,max_class,except,sum_class;
 float info1;
 
/* initialize info to zero */
 info=0.0;

 /* initialize pattern */
 for(i=0;i<asked_no;i++)
   pattern[i]=0;
 checked=0;
 while(checked==0) {
   i=0;
   while(mark[i]==1)/* skip those patterns which are already searched */
     i++;
   
   /* check whether all patterns are considered */
   if(i>=no_ex) {
     checked=1;
     break;
   }

   for(j=0;j<asked_no;j++)/* find a pattern which is not yet searched */
     pattern[j]=data_ar[i][subset[j]];
   
   /* initialize class_val */
   for(j=0;j<no_class;j++)
     class_val[j]=0;

   for(;i<no_ex;i++) {
     match=1;
     if(mark[i]==0)
       for(j=0;j<asked_no && match==1;j++) 
         if(data_ar[i][subset[j]]!=pattern[j])
           match=0;
     
     if(match==1) {
       mark[i]=1;
       class_val[class[i]]++;
     }
   }
   /* update info */
   max_class=0;sum_class=0;
   for(j=0;j<no_class;j++) {
     sum_class+=class_val[j];
     if(class_val[j]>max_class) 
       max_class=class_val[j];
   }
   except=sum_class-max_class;
   info+=except;
 }/* while loop for all patterns */

 /* info calculation both theory and exceptions */
 info1=1.0;
 for(j=0;j<asked_no;j++) 
   info1*=fea_arity[subset[j]];
 if(info>0.0)
   info=log(info)/log(2.0);
 info+=log(info1)/log(2.0);
 return info;
}