testsom.c

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

  }
  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);
  }

  //  for (n = 0; n < vmap.numclasses; n++)
  //    fprintf(stdout, "%s\n", GetLabel(n+1));

  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: 
******************************************************************************/
void MarkSubtreeNodes(struct Node *node, struct Graph *gptr, int *nodeflags)
{
  int i;

  nodeflags[node->nnum]++;
  for (i = 0; i < gptr->FanOut; i++){
    if (node->children[i] != NULL && nodeflags[node->children[i]->nnum] == 0)
      MarkSubtreeNodes(node->children[i], gptr, nodeflags);
  }
}

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

Return value: 
******************************************************************************/
void UnmarkSubtreeNodes(struct Node *node, struct Graph *gptr, int maxout, int *nodeflags)
{
  int i;

  nodeflags[node->nnum] = 0;
  for (i = 0; i < maxout && i < gptr->FanOut; i++){
    if (node->children[i] != NULL)
      UnmarkSubtreeNodes(node->children[i], gptr, maxout, nodeflags);
  }
}

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

Return value: 
******************************************************************************/
void MarkExceedingOutdegree(struct Graph *gptr, int maxout, int *nodeflags)
{
  int nnum, i;
  struct Node *node;

  if (gptr->FanOut <= maxout)
    return;

  for (nnum = 0; nnum < gptr->numnodes; nnum++){
    node = gptr->nodes[nnum];

    if (node == NULL)
      continue;

    for (i = maxout; i < gptr->FanOut; i++){
      if (node->children[i] != NULL)
	MarkSubtreeNodes(node->children[i], gptr, nodeflags);
    }
  }
}

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

Return value: 
******************************************************************************/
void UnmarkNeededNodes(struct Graph *gptr, int maxout, int *nodeflags)
{
  int i, nnum;
  struct Node *node;

  for (nnum = 0; nnum < gptr->numnodes; nnum++){
    node = gptr->nodes[nnum];

    if (node == NULL)
      continue;

    if (nodeflags[node->nnum] != 0)
      continue;

    for (i = 0; i < maxout && i < gptr->FanOut; i++){
      if (node->children[i] != NULL)
	UnmarkSubtreeNodes(node->children[i], gptr, maxout, nodeflags);
    }
  }
}

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

Return value: 
******************************************************************************/
void Truncate(struct Parameters parameters, int maxout)
{
  int i, idx;
  int nnum, inum, fan, maxfan;
  struct Graph *gptr;
  struct Node *node, **nodearray;
  int numexceed, maxnodes;
  int *childflags, *nodeflags = NULL;


  fprintf(stderr, "Analysing data...");
  fflush(stderr);

  maxfan = 0;
  maxnodes = 0;
  /* Obtain max outdegree and max number of nodes of a graph */
  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    if (maxfan < gptr->FanOut)
      maxfan = gptr->FanOut;
    if (maxnodes < gptr->numnodes)
      maxnodes = gptr->numnodes;
  }
  /* Flags indicating actually existing slots where children are found */
  childflags = (int*)MyCalloc(maxfan, sizeof(int));
  nodearray = (struct Node **)MyCalloc(maxnodes, sizeof(struct Node *));

  /* Computing the actual max out-degree */
  numexceed = 0;
  inum = 0;
  for (gptr = parameters.train; gptr != NULL; gptr = gptr->next){
    if (gptr->FanOut > maxout)
      inum++;
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      fan = 0;
      node = gptr->nodes[nnum];
      for (i = 0; i < gptr->FanOut; i++){
	if (node->children[i] != NULL){
	  childflags[i]++;
	  fan++;
	}
      }
      if (fan > maxout)
	numexceed++;
    }
  }
  fan = 0;
  for (i = 0; i < maxfan; i++)
    if (childflags[i] > 0)
      fan++;
  fprintf(stderr, "done\n");

  if (numexceed)
    fprintf(stderr, "%d nodes seem to exceed the max outdegree of %d\n", nu