data.c

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

    UpdateOffspringStates = UpdateChildrensLocation;    /* Use coordinates */
  }

  for (;gptr != NULL; gptr = gptr->next){
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      UpdateOffspringStates(gptr, node);
      FindWinner(map, node, gptr, &winner);

      if (map->topology == TOPOL_VQ)
	node->winner = winner.codeno;
      else{
	node->x = map->codes[winner.codeno].x;
	node->y = map->codes[winner.codeno].y;
      }
      qerror += winner.diff;
      n++;
    }
  }
  return qerror/n;
}




/*****************************************************************************
Description: Returns the number of offsprings a given node has.

Return value: Number of offsprings of given node which can be any value from
              0 to FanOut.
*****************************************************************************/
UNSIGNED GetNumChildren(struct Node *node, UNSIGNED FanOut)
{
  UNSIGNED i, num = 0;

  for (i = 0; i < FanOut; i++)
    if (node->children[i] != NULL)
      num++;

  return num;
}

/*****************************************************************************
Description: Check if a given node is a root node.

Return value: 1 if the node is a root node, 0 otherwise.
*****************************************************************************/
UNSIGNED IsRoot(struct Node *node)
{
  if (node->numparents == 0) /* Root nodes have no parent nodes */
    return 1;
  else
    return 0;                /* It is not a root node */
}

/*****************************************************************************
Description: Check if a given node is a leaf node.

Return value: 1 if the node is a leaf node, 0 otherwise.
*****************************************************************************/
UNSIGNED IsLeaf(struct Node *node)
{
  if (node->depth == 0)      /* Leaf nodes are located at depth 0 */
    return 1;
  else
    return 0;                /* It is not a leaf node */
}

/*****************************************************************************
Description: Check if a given node is a intermediate node (not leaf nor root).

Return value: 1 if the node is a intermediate node, 0 otherwise.
*****************************************************************************/
UNSIGNED IsIntermediate(struct Node *node)
{
  if (node->depth > 0 && node->numparents > 0) /* Intermediate node */
    return 1;
  else
    return 0;                      /* It is not a intermediate node */
}

/*****************************************************************************
Description: Returns the type of a given node which can be either ROOT, LEAF,
             or INTERMEDIATE.

Return value: Returns the constant value ROOT, LEAF, or INTERMEDIATE depending
              on whether the node is a root node, a leaf node, or neither leaf
              nor root.
*****************************************************************************/
UNSIGNED GetNodeType(struct Node *node)
{
  if (node->numparents == 0) /* Root nodes have no parent nodes */
    return ROOT;
  else if (node->depth == 0) /* Leaf nodes are of depth 0       */
    return LEAF;
  else
    return INTERMEDIATE;   /* Not root or leaf so it must be an intermediate */
}

/*****************************************************************************
Description: Computes the longest path from a given node to a leaf node.

Return value: The length of the longest path from the given node to the
              furthest leaf node.
*****************************************************************************/
UNSIGNED GetMaxPathLength(struct Node *node, UNSIGNED FanOut, int maxiter)
{
  UNSIGNED i, maxlen, len;

  /* If depth is already known, or we are at a leaf node */
  if (node->depth != 0 || GetNumChildren(node, FanOut) == 0)
    return node->depth;

  /* Graph appears to have a endless loop */
  if (--maxiter <= 0)
    return 0;

  maxlen = 0;
  for (i = 0; i < FanOut; i++){
    if (node->children[i] != NULL){
      len = GetMaxPathLength(node->children[i], FanOut, maxiter)+1;
      if (len > maxlen)
	maxlen = len;
    }
  }
  return maxlen;
}

/*****************************************************************************
Description: Set the depth value of all nodes in all graphs. This works well
             on small graphs. NOTE: This function will fail for very deep
             graph structures (~100000 nodes of more) due to a stack overflow.

Return value: The function does not return a value.
*****************************************************************************/
void SetNodeDepthRecursively(struct Graph *gptr)
{
  UNSIGNED n, max;
  struct Node *node;

  for (; gptr != NULL; gptr = gptr->next){
    if (gptr->numnodes <= 1) /* No nodes or only one node */
      continue;
    max = 0;
    for (n = 0u; n < gptr->numnodes; n++){
      node = gptr->nodes[n];
      node->depth = GetMaxPathLength(node, gptr->FanOut, gptr->numnodes);
      if (max < node->depth)
	max = node->depth;
    }
    gptr->depth = max;
  }
}

/*****************************************************************************
Description: Set the depth value of all nodes in all graphs using an iterative
             approach. This function works best on shallow graphs.

Return value: The function does not return a value.
*****************************************************************************/
void SetNodeDepthIteratively(struct Graph *gptr)
{
  UNSIGNED i, n, depth, max;
  UNSIGNED changes;
  struct Node *node;
  UNSIGNED *flags;

  for (; gptr != NULL; gptr = gptr->next){
    if (gptr->numnodes <= 1) /* No nodes or only one node */
      continue;

    flags = (UNSIGNED*)MyMalloc(gptr->numnodes * sizeof(UNSIGNED));
    memset(flags, 1, gptr->numnodes * sizeof(UNSIGNED));
    max = 0;
    do{
      changes = 0;
      for (n = 0u; n < gptr->numnodes; n++){
	if (flags[n] == 0)
	  continue;

	flags[n] = 0;
	node = gptr->nodes[n];
	if (GetNumChildren(node, gptr->FanOut)==0){ //Leaf nodes are of depth 0
	  node->depth = 0;
	  continue;
	}

	depth = 0;
	for (i = 0; i < gptr->FanOut; i++){
	  if (node->children[i] != NULL){
	    if (node->children[i]->depth > depth)
	      depth = node->children[i]->depth;
	  }
	}
	if (node->depth != depth + 1){
	  node->depth = depth + 1;
	  max = depth + 1;
	  flags[n] = 1;
	  changes++;
	}
      }
    }while(changes > 0);
    free(flags);
    gptr->depth = max;
  }
}

/*****************************************************************************
Description: Set the depth value of all nodes in all graphs by using a reverse
             breadth first approach. This works best on large narrow graphs.

Return value: The function does not return a value.
*****************************************************************************/
void SetNodeDepth_UsingReverseTrace(struct Graph *gptr)
{
  UNSIGNED n, p, nlevel, num, newnum;
  UNSIGNED depth, newlevelsize;
  struct Node **onlevel, **newlevel;

  for (; gptr != NULL; gptr = gptr->next){
    gptr->depth = 0;  /* Initialize graph's depth with a known value */
    num = 0;
    for (n = 0u; n < gptr->numnodes; n++){
      if (GetNumChildren(gptr->nodes[n], gptr->FanOut)==0){
	num++;        /* Count number of leafs in a graph */
      }
    }
    onlevel = (struct Node **)MyMalloc(num * sizeof(struct Node *));
    nlevel = num;
    num = 0;
    for (n = 0u; n < gptr->numnodes; n++){
      if (GetNumChildren(gptr->nodes[n], gptr->FanOut)==0){
	onlevel[num++] = gptr->nodes[n];
      }
    }

    /* Starting from leaf nodes, traverse graph layer by layer towards root */
    depth = 1;
    newlevel = NULL;
    while(num > 0){
      newnum = 0;
      newlevelsize = 16;
      newlevel = (struct Node **)MyMalloc(16 * sizeof(struct Node *));
      for (n = 0; n < num; n++){
	for (p = 0; p < onlevel[n]->numparents; p++){
	  onlevel[n]->parents[p]->depth = depth;
	  if (newlevelsize <= newnum){
	    newlevelsize += 16;
	    newlevel = (struct Node **)MyRealloc(newlevel, newlevelsize * sizeof(struct Node *));
	  }
	  newlevel[newnum] = onlevel[n]->parents[p];
	  newnum++;
	}
      }
      num = newnum;
      free(onlevel);
      onlevel = newlevel;
      depth++;
    }
    free(onlevel);
    gptr->depth = depth - 1;
  }
}

/*****************************************************************************
Description: Set the depth value of all nodes in all graphs.

Return value: The function does not return a value.
*****************************************************************************/
void SetNodeDepth(struct Graph *graph)
{
  UNSIGNED maxFanOut, maxNumNodes;
  struct Graph *gptr;

  if (graph == NULL) /* Sanity check */
    return;

  /* Determine some dataset properties... */
  maxFanOut = 0;
  maxNumNodes = 0;
  for (gptr = graph; gptr != NULL; gptr = gptr->next){
    if (gptr->FanOut > maxFanOut)
      maxFanOut = gptr->FanOut;
    if (gptr->numnodes > maxNumNodes)
      maxNumNodes = gptr->numnodes;
  }

  /* ...chose fastest routine for the task */
  if (maxNumNodes < 1000)
    SetNodeDepthRecursively(graph); /* Fastest but requires lots of memory */
  else if (maxFanOut < 5)
    SetNodeDepth_UsingReverseTrace(graph); /* Fast if FanOut is small   */
  else
    SetNodeDepthIteratively(graph); /* Slowest but needs little memory  */
}

/*****************************************************************************
Description: Increase the size of a given vector component for every node in
             a given graph.

Return value: The function does not return a value.
*****************************************************************************/
void IncreaseDimension(struct Graph *gptr, int newdim, int component)
{
  UNSIGNED n, dimension, dimincrease;

  /* Compute the actual increase of the vector dimension */
  dimincrease = 0;
  switch (component){
  case DATALABEL:
    dimincrease = newdim - gptr->ldim;
    break;
  case CHILDSTATES:
    dimincrease = 2 * (newdim - gptr->FanOut);
    break;
  case PARENTSTATES:
    dimincrease = 2 * (newdim - gptr->FanIn);
    break;
  case TARGETS:
    dimincrease = newdim - gptr->tdim;
    break;
  }
  if (dimincrease <= 0)  /* Leave unchanged if dimension is not increasing */
    return;

  fprintf(stderr, "WARNING: Increasing vector dimension without increasing dimension of codebook vectors. Implementation is incomplete!\n");

  /* Compute old vector dimension */
  dimension = gptr->ldim + 2*(gptr->FanOut + gptr->FanIn) + gptr->tdim;

  for (n = 0; n < gptr->numnodes; n++){
    gptr->nodes[n]->points = (FLOAT*)MyRealloc(gptr->nodes[n]->points, (dimension + dimincrease) * sizeof(FLOAT));

    /* Move old vector components back into the right place, and initialize
       newly allocated space with zero values. */
    switch (component){
    case DATALABEL:
      memmove(&gptr->nodes[n]->points[gptr->ldim+dimincrease], &gptr->nodes[n]->points[gptr->ldim], (2*(gptr->FanOut+gptr->FanIn)+gptr->tdim) * sizeof(FLOAT));
      memset(&gptr->nodes[n]->points[gptr->ldim], 0, dimincrease * sizeof(FLOAT));
      break;
    case CHILDSTATES:
      memmove(&gptr->nodes[n]->points[gptr->ldim+2*gptr->FanOut+dimincrease], &gptr->nodes[n]->points[gptr->ldim+2*gptr->FanOut], (2*gptr->FanIn+gptr->tdim) * sizeof(FLOAT));
      memset(&gptr->nodes[n]->points[gptr->ldim+2*gptr->FanOut], 0, dimincrease * sizeof(FLOAT));
      break;
    case PARENTSTATES:
      memmove(&gptr->nodes[n]->points[gptr->ldim+2*(gptr->FanOut+gptr->FanIn)+dimincrease], &gptr->nodes[n]->points[gptr->ldim+2*(gptr->FanOut+gptr->FanIn)], gptr->tdim * sizeof(FLOAT));
      memset(&gptr->nodes[n]->points[gptr->ldim+2*(gptr->FanOut+gptr->FanIn)], 0, dimincrease * sizeof(FLOAT));
      break;
    case TARGETS:
      /* nothing to be moved here. */
      memset(&gptr->nodes[n]->points[gptr->ldim+2*(gptr->FanOut+gptr->FanIn)+gptr->tdim], 0, dimincrease * sizeof(FLOAT));
      break;
    }
  }
}

/*****************************************************************************
Description: Perform padding on all nodes to ensure consistent size.

Return value: The function does not return a value.
*****************************************************************************/
void Padding(struct Parameters param)
{
  UNSIGNED mindim, maxdim;
  struct Graph *gptr;
  struct Graph *graphs;

  graphs = param.train;
  mindim = MAX_UNSIGNED;
  maxdim = 0;
  for (gptr = graphs; gptr != NULL; gptr = gptr->next){
    if (mindim > gptr->dimension)
      mindim = gptr->dimension;
    if (maxdim < gptr->dimension)
      maxdim = gptr->dimension;
  }
  if (mindim == maxdim)
    return; /* No padding required */

  /* Check if data label component requires padding */
  mindim = MAX_UNSIGNED;
  maxdim = 0;
  for (gptr = graphs; gptr != NULL; gptr = gptr->next){
    if (mindim > gptr->ldim)
      mindim = gptr->ldim;
    if (maxdim < gptr->ldim)