testsomnew.c

SOM-sd 是现在国外非常流行的一个神经网络的结构自组织特征映射算法

	    for (r = 0; r < graph->numnodes; r++)
	      if (IsRoot(graph->nodes[r]))
		break;
	    if (!IsRoot(graph->nodes[r]))
	      fprintf(stderr, "No root found\n");
	    hptr->graph = graph;
	    hptr->node = node;
	    memset(buffer, 0, olen);
	    GetStructID(hptr->graph->FanOut, graph->nodes[r], buffer);
	    olen = strlen(buffer);
	    hptr->structID = (char*)memdup(buffer, olen+1);

	    memset(buffer, 0, olen);
	    GetStructID(hptr->graph->FanOut, hptr->node, buffer);
	    olen = strlen(buffer);
	    hptr->substructID =(char*)memdup(buffer, olen+1);

	    hptr->next = hits;
	    hits = hptr;
	    ni++;
	    //  printf("%d %d %d %d\n", x, y, graph->gnum, node->nnum);
	    //  fprintf(stderr, "%s\n", graph->gname);
	  }
	}
      }

      //Sort list by structID
      if (ni > 0){
	harray = malloc(ni * sizeof(struct AllHits));
	for (i = 0, hptr = hits; hptr != NULL; hptr = hptr->next, i++)
	  memcpy(&harray[i], hptr, sizeof(struct AllHits));

	qsort(harray, ni, sizeof(struct AllHits), comparStructID);

	mi = 1;
	n = 1;
	hprev = &harray[0];
	for (i = 1; i < ni; i++){
	  if (!strcmp(harray[i].structID, hprev->structID))
	    n++;
	  else{
	    if (mi < n)
	      mi = n;
	    n = 1;
	    hprev = &harray[i];
	  }
	}
	if (mi < n)
	  mi = n;
	Si += (FLOAT)mi/ni;
      }

      //Sort list by substructID
      if (ni > 0){
	qsort(harray, ni, sizeof(struct AllHits), comparsubStructID);

	mi = 1;
	n = 1;
	hprev = &harray[0];
	for (i = 1; i < ni; i++){
	  if (!strcmp(harray[i].substructID, hprev->substructID))
	    n++;
	  else{
	    if (mi < n)
	      mi = n;
	    n = 1;
	    hprev = &harray[i];
	  }
	}
	if (mi < n)
	  mi = n;
	sSi += (FLOAT)mi/ni;
	free(harray);
	harray = NULL;
      }


      //Delete list
      while(hits != NULL){
	hptr = hits->next;
	free(hits->structID);
	free(hits->substructID);
	free(hits);
	hits = hptr;
      }
      if (ni > 0)
	N++;
    } //End x-loop
  } //End y-loop
  fprintf(stdout, "Struct mapping performance (E): %f\n", Si/N);
  fprintf(stdout, "SubStruct mapping performance (e): %f\n", sSi/N);




  flag = 0;

  if (parameters.test == NULL){
    printf("Warning: No test file given. Will use training data for testing.\n");
    parameters.test = parameters.train;
    flag = 1;
  }

  map = &parameters.map;
  /* Compute the mapping of nodes in the training and the test dataset */
  if (KstepEnabled){
    if (!flag)
      K_Step_Approximation(map, parameters.test, 1);
  }
  else{
    if (!flag)
      GetNodeCoordinates(map, parameters.test);
  }

  vmap = GetHits(parameters.map.xdim, parameters.map.ydim, parameters.train, ROOT);
  GetClusterID(parameters.map, parameters.train, &vmap);
  if (!flag){
    tvmap = GetHits(parameters.map.xdim, parameters.map.ydim, parameters.test, ROOT);
    GetClusterID(parameters.map, parameters.test, &tvmap);
  }

  R = 0.0;
  C = 0;
  n = 0;
  //For (every node in the test set){
  for (gptr = parameters.test;gptr != NULL; gptr = gptr->next){
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      if (!IsRoot(node))
	continue;
      FindWinnerEucledianOnActiveOnly(map, node, gptr, &winner, &vmap);
      winnerx = map->codes[winner.codeno].x;
      winnery = map->codes[winner.codeno].y;
      n++;
      R += ComputeClassificationConfusion(winnerx, winnery, &vmap);
      if (classifyflag != 0)
	fprintf(stdout, "Graph:%s %s (%d,%s)", gptr->gname, GetLabel(vmap.winnerclass[winnery][winnerx]), node->label, GetLabel(node->label));
      if (node->label == vmap.winnerclass[winnery][winnerx]){
	C++;
      }
    }
  }
  if (flag)
    P = GetClusteringPerformance(parameters, vmap);
  else
    P = GetClusteringPerformance(parameters, tvmap);

  if (classifyflag == 0){
    printf("Retrieval performance: %f\n", 100.0*R/n);
    printf("Classification performance: %f\n", (float)100.0*C/n);
    printf("Clustering performance: %f\n", P);
  }

  ComputeConfusionMatrix(parameters.map.xdim, parameters.map.ydim, &vmap);

  if (flag)
    parameters.test = NULL;  /* Restore test pointer */
}


/******************************************************************************
Description: 

Return value: 
******************************************************************************/
void AnalyseGraphs(struct Parameters parameters)
{
  int i,j,k;
  int nnum, imin, imax, iavg, itotal, inum, inum2, fan, maxfan;
  float fmin, fmax, favg, ftotal, fval, fvar;
  int minnodes, maxnodes;
  struct Graph *gptr;
  struct Node *node;
  char *name;

  imin = INT_MAX;
  imax = 0;
  itotal = 0;
  inum = 0;
  inum2 = 0;
  maxnodes = 0;
  minnodes = INT_MAX;
  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    maxfan = 0;
    if (maxnodes < gptr->numnodes)
      maxnodes = gptr->numnodes;
    if (minnodes > gptr->numnodes)
      minnodes = gptr->numnodes;
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      fan = 0;
      for (i = 0; i < gptr->FanOut; i++)
	if (node->children[i] != NULL)
	  fan++;
      if (maxfan < fan)
	maxfan = fan;
    }
    if (maxfan > imax)
      imax = maxfan;
    if (maxfan < imin)
      imin = maxfan;
    itotal += maxfan;
    inum++;
    inum2 += gptr->numnodes;
  }
  fprintf(stderr, "Total number of graphs: %d\n", inum);
  fprintf(stderr, "Total number of nodes: %d\n", inum2);
  fprintf(stderr, "Smallest graph: %d nodes\n", minnodes);
  fprintf(stderr, "Largest  graph: %d nodes\n", maxnodes);
  favg = (float)itotal/inum;
  fvar = 0.0;
  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    fval = gptr->FanOut - favg;
    fvar += fval * fval;
  }
  fvar /= inum;
  fprintf(stderr, "Outdegree: min=%d, max=%d, avg=%E, stddev=%E\n", imin, imax, favg, sqrt(fvar));
  //  fprintf(stderr, "%s\n", name);
}

/******************************************************************************
Description: 

Return value: 
******************************************************************************/
int SelectBiased(float *array, int num, float max)
{
  int i;
  float rval, sum;

  rval = drand48() * max;
  sum = 0.0;
  for (i = 0; i < num; i++){
    sum += array[i];
    if (rval < sum)
      break;
  }
  return i;
}

/******************************************************************************
Description: 

Return value: 
******************************************************************************/
void BalanceGraphs(struct Parameters parameters)
{
  int i,j;
  int nnum, imin, imax, itotal, inum, inum2, fan, maxfan, class, starindex;
  int numlabels;
  int *labels, **outdegrees;
  float *lrel, **orel, *ocount; 
  float ftotal;
  struct Graph *gptr, *gold;
  struct Node *node;
  struct GraphSorted{
    int num;
    int idx;
    struct Graph **graphs;
  } **graphs;


  starindex = -1;
  numlabels = GetNumLabels();
  for (i = 1; i <= numlabels; i++){
    if (!strcmp(GetLabel(i), "*")){
      starindex = i;
      break;
    }
  }

  if (starindex > 0)
    fprintf(stderr, "Number of labels: %d\n", numlabels-1);
  else
    fprintf(stderr, "Number of labels: %d\n", numlabels);

  labels = (int*)MyCalloc(numlabels, sizeof(int));
  lrel = (float*)MyCalloc(numlabels, sizeof(float));
  outdegrees = (int**)MyCalloc(numlabels, sizeof(int*));
  orel = (float**)MyCalloc(numlabels, sizeof(float*));
  ocount = (float*)MyCalloc(numlabels, sizeof(float));
  graphs = (struct GraphSorted**)MyCalloc(numlabels, sizeof(struct GraphSorted*));
  for (i = 0; i < numlabels; i++){
    outdegrees[i] = (int*)MyCalloc(parameters.train->FanOut+1, sizeof(int));
    orel[i] = (float*)MyCalloc(parameters.train->FanOut+1, sizeof(float));
    graphs[i] = (struct GraphSorted*)MyCalloc(parameters.train->FanOut+1, sizeof(struct GraphSorted));
  }

  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      labels[node->label-1]++;
    }
  }
  itotal = 0;
  for (i = 0; i < numlabels; i++)
    if (i+1 != starindex)
      itotal += labels[i];

  ftotal = 0.0;
  fprintf(stderr, "Label : Frequency\n----------------\n");
  for (i = 0; i < numlabels; i++){
    if (i+1 != starindex){
      lrel[i] = (float)itotal/labels[i];
      ftotal += lrel[i];
      fprintf(stderr, "%s : %d %f %d\n", GetLabel(i+1), labels[i], lrel[i], labels[i]*100/itotal);
    }
    else
      labels[i] = 0;
  }
  fprintf(stderr, "----------------\nTotal : %d %f\n", itotal, ftotal);

  imin = INT_MAX;
  imax = 0;
  inum = 0;
  inum2 = 0;
  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    maxfan = 0;
    class = -1;
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      fan = 0;
      for (i = 0; i < gptr->FanOut+1; i++)
	if (node->children[i] != NULL)
	  fan++;
      if (maxfan < fan)
	maxfan = fan;
      if (node->label != starindex)
	class = node->label-1;
    }
    if (class >= 0 && maxfan < gptr->FanOut+1)
      outdegrees[class][maxfan]++;
    else
      fprintf(stderr, "Error: No class or fanin > max (%d: %d,%d)\n", class, maxfan, gptr->FanOut);

    inum++;
    inum2 += gptr->numnodes;
  }
  fprintf(stderr, "Outdegree : Labels...\n----------------\n    ");
  for (i = 0; i < numlabels; i++){
    if (i+1 != starindex){
      fprintf(stderr, " %4s", GetLabel(i+1));
    }
  }
  fprintf(stderr, "\n");
  for (j = 0; j < parameters.train->FanOut+1; j++){
    fprintf(stderr, "%3d :", j);
    for (i = 0; i < numlabels; i++){
      if (i+1 != starindex){
	fprintf(stderr, " %4d", outdegrees[i][j]);
	if (outdegrees[i][j] > 0){
	  orel[i][j] = (float)labels[i]/outdegrees[i][j];
	  ocount[i] += orel[i][j];
	}
      }
    }
    fprintf(stderr, "\n");
  }
  fprintf(stderr, "Total");
  for (i = 0; i < numlabels; i++){
    if (i+1 != starindex){
      fprintf(stderr, " %4d", labels[i]);
    }
  }
  fprintf(stderr, "\n");



  fprintf(stderr, "Outdegree : Labels...\n----------------\n   ");
  for (i = 0; i < numlabels; i++){
    if (i+1 != starindex){
      fprintf(stderr, " %5s", GetLabel(i+1));
    }
  }
  fprintf(stderr, "\n");
  for (j = 0; j < parameters.train->FanOut+1; j++){
    fprintf(stderr, "%3d :", j);
    for (i = 0; i < numlabels; i++){
      if (i+1 != starindex){
	if (orel[i][j] < 10)
	  fprintf(stderr, " ");
	if (orel[i][j] < 100)
	  fprintf(stderr, " ");
	fprintf(stderr, " %3.1f", orel[i][j]);
      }
    }
    fprintf(stderr, "\n");
  }
  fprintf(stderr, "Total");
  for (i = 0; i < numlabels; i++){
    if (i+1 != starindex){
      fprintf(stderr, " %3.1f", ocount[i]);
    }
  }
  fprintf(stderr, "\n");



  fprintf(stderr, "Number of graphs: %d\n", inum);
  fprintf(stderr, "Number of nodes: %d\n", inum2);

  for (i = 0; i < numlabels; i++){
    for (j = 0; j < parameters.train->FanOut+1; j++){
      if (outdegrees[i][j] > 0){
	graphs[i][j].graphs = (struct Graph **)MyCalloc(outdegrees[i][j], sizeof(struct Graph *));
      }
    }
  }
  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    maxfan = 0;
    class = -1;
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      fan = 0;
      for (i = 0; i < gptr->FanOut+1; i++)
	if (node->children[i] != NULL)
	  fan++;
      if (maxfan < fan)
	maxfan = fan;
      if (node->label != starindex)
	class = node->label-1;
    }
    graphs[class][maxfan].graphs[graphs[class][maxfan].num] = gptr;
    graphs[class][maxfan].num++;
  }
  for (gptr = parameters.train; gptr != NULL; ){
    gold = gptr;
    gptr = gptr->next;
    gold->next = NULL;
  }
  srand48(15);
  for (i = 0; i < 30000; i++){
    //    class = SelectBiased(lrel, numlabels, ftotal);
    //    fan = SelectBiased(orel[class], parameters.train->FanOut+1, ocount[class]);
    do{
      class = drand48()*numlabels;
    }while (class+1 == starindex);
    do{
      fan = drand48()*parameters.train->FanOut+1;
    }while(graphs[class][fan].num == 0);
    SaveData(stdout, graphs[class][fan].graphs[graphs[class][fan].idx]);
    graphs[class][fan].idx = (graphs[class][fan].idx+1) % graphs[class][fan].num;
    fprintf(stderr, "\r%d", i);
  }
}


/******************************************************************************
Description: 

Return value: 
******************************************************************************/