data.c

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

/*
  Contents: Functions used for data handling and data verification.

  Author: Markus Hagenbuchner

  Comments and questions concerning this program package may be send
  to '[e-mail]'
 */


/************/
/* Includes */
/************/
#include <ctype.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "common.h"
#include "train.h"
#include "utils.h"


/********************/
/* Global variables */
/********************/
UNSIGNED Number_Labels  = 0;
char **Data_Labels = NULL;
struct LabelArray {
  char *label;
  int pos;
};


/* Begin functions... */

/*****************************************************************************
Description: Add label to an array of labels if the label is not already in
             the array.

Return value: The index (when starting to count from 1) of where the label
              is stored in the array.
*****************************************************************************/
UNSIGNED AddLabel(char *label)
{
  UNSIGNED i;

  if (label == NULL)
    return MAX_UNSIGNED;

  for (i = 0; i < Number_Labels; i++)
    if (!strcmp(Data_Labels[i], label))
      return i+1;

  Number_Labels++;
  Data_Labels = MyRealloc(Data_Labels, Number_Labels * sizeof(char*));
  Data_Labels[Number_Labels-1] = strdup(label);
  return Number_Labels;
}

/*****************************************************************************
Description: Return a pointer to a data label which corresponds to a given
             index value.

Return value: A pointer to a data label, or NULL if the index is undefined.
*****************************************************************************/
char* GetLabel(UNSIGNED index)
{
  if (index == 0 || index > Number_Labels)
    return NULL;
  return Data_Labels[index-1];
}

/*****************************************************************************
Description: Return the number of labels currently stored in the array
             Data_Labels.

Return value: The number of labels in Data_Labels.
*****************************************************************************/
UNSIGNED GetNumLabels()
{
  return Number_Labels;
}

int LabelSorter(const void *arg1, const void *arg2)
{
  return strcmp(((struct LabelArray*)arg1)->label, ((struct LabelArray*)arg2)->label);
}

/*****************************************************************************
Description: Return a list of label indexes which alphabetically sorts the
             labels.

Return value: An integer array of the same length as the number of labels.
*****************************************************************************/
int *GetSortedLabelIndex()
{
  static int *sindex = NULL;
  static int len = 0;
  int i;
  struct LabelArray *tmparray;

  if (sindex)
    free(sindex);
  sindex = calloc(Number_Labels, sizeof(int));
  tmparray = (struct LabelArray*)calloc(Number_Labels, sizeof(struct LabelArray));
  for (i = 0; i < Number_Labels; i++){
    tmparray[i].label = Data_Labels[i];
    tmparray[i].pos = i;
  }

  qsort(tmparray, Number_Labels, sizeof(struct LabelArray), LabelSorter);
  for (i = 0; i < Number_Labels; i++)
    sindex[i] = tmparray[i].pos+1;
  free(tmparray);
  len = Number_Labels;

  return sindex;
}


/*****************************************************************************
Description: Clear all labels from the list of data labels.

Return value: The function does not return a value.
*****************************************************************************/
void ClearLabels()
{
  UNSIGNED i;

  for (i = 0; i < Number_Labels; i++)
    free(Data_Labels[i]);
  Number_Labels = 0;
}

/*****************************************************************************
Description: Find the children of the current node, and assign the position of
             the childrens' winner neuron to the current node.

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

  offset = gptr->ldim;
  for (i = 0; i < gptr->FanOut; i++){
    if (node->children[i] != NULL){
      node->points[offset+i*2] =  (FLOAT)node->children[i]->x;
      node->points[offset+i*2+1]= (FLOAT)node->children[i]->y;
    }
  }
}

/*****************************************************************************
Description: In VQ mode, find the children of the current node, and assign the
             ID of the childrens' winner neuron to the current node.

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

  offset = gptr->ldim;
  for (i = 0u; i < gptr->FanOut; i++){
    if (node->children[i] != NULL){
      node->points[offset+i*2] =  node->children[i]->winner;
    }
  }
}

/*****************************************************************************
Description: Find the children and parents of the current node, and assign the
             position of the childrens' winner neuron to the current node.

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

  offset = gptr->ldim;
  for (i = 0u; i < gptr->FanOut; i++){
    if (node->children[i] != NULL){
      node->points[offset+i*2] =  node->children[i]->x;
      node->points[offset+i*2+1]= node->children[i]->y;
    }
  }
  offset = gptr->ldim + 2 * gptr->FanOut;
  for (i = 0u; i < node->numparents; i++){
    if (node->parents[i] != NULL){
      node->points[offset+i*2] =  node->parents[i]->x;
      node->points[offset+i*2+1]= node->parents[i]->y;
    }
  }
}

/*****************************************************************************
Description: Use with caution!! May be very slow

Return value: The quantization error.
*****************************************************************************/
/*
FLOAT ComputeStablePointOBSOLETE(struct Map *map, struct Graph *graph)
{
  UNSIGNED nnum, n, statechanges, oldstatechanges;
  FLOAT qerror;
  struct Node *node;
  struct Graph *gptr;
  struct Winner winner;
  void (*FindWinner)(struct Map *map, struct Node *node,struct Graph *gptr,struct Winner *winner);
  void (*UpdateStates)(struct Graph *gptr, struct Node *node);

  if (map == NULL && graph == NULL)
    return 0.0;

  if (map->topology == TOPOL_VQ){      
    fprintf(stderr, "Error: VQ in contextual mode not fully implemented");
    exit(0);
    FindWinner = VQFindWinnerEucledian; 
    UpdateStates = UpdateChildrensLocationVQ; 
  }
  else{
    FindWinner = FindWinnerEucledian;
    UpdateStates = UpdateChildrenAndParentLocation;
  }

  oldstatechanges = MAX_UNSIGNED;
  while (1){
    qerror = 0.0;
    statechanges = 0;
    n = 0;
    for (gptr = graph; gptr != NULL; gptr = gptr->next){
      for (nnum = 0; nnum < gptr->numnodes; nnum++){
	node = gptr->nodes[nnum];
	UpdateStates(gptr, node);
	FindWinner(map, node, gptr, &winner);
	
	if (map->topology == TOPOL_VQ)
	  node->winner = winner.codeno;
	else{
	  if (node->x != map->codes[winner.codeno].x){
	    node->x = map->codes[winner.codeno].x;
	    statechanges++;
	  }
	  if (node->y != map->codes[winner.codeno].y){
	    node->y = map->codes[winner.codeno].y;
	    statechanges++;
	  }
	}
	qerror += winner.diff;
	n++;
      }
    }
    if (statechanges == 0 || oldstatechanges <= statechanges)
      break;
    oldstatechanges = statechanges;
  }
  return qerror/n;
}
*/
/*****************************************************************************
Description: Compute the states of every node in the dataset using K-step
             approximation. 
             Use with caution!! May be very slow

Return value: The quantization error normalized with respect to the total
              number of nodes in the dataset.
*****************************************************************************/
FLOAT K_Step_Approximation(struct Map *map, struct Graph *graph, int mode)
{
  UNSIGNED nnum, n, nmax, iter, statechanges;
  FLOAT gpr_qerror, qerror;
  struct Node *node;
  struct Graph *gptr;
  struct Winner winner;
  void (*FindWinner)(struct Map *map, struct Node *node,struct Graph *gptr,struct Winner *winner);
  void (*UpdateStates)(struct Graph *gptr, struct Node *node);

  if (map == NULL && graph == NULL)
    return 0.0;

  if (map->topology == TOPOL_VQ){            /* In VQ mode...   */
    fprintf(stderr, "Error: VQ in contextual mode not fully implemented");
    exit(0);
    FindWinner = VQFindWinnerEucledian; /* Use Eucledian distance VQ mode  */
    UpdateStates = UpdateChildrensLocationVQ; /* use ID value    */
  }
  else if (mode == 1){
    FindWinner = FindWinnerEucledian;   /* Use standard Eucledian distance */
    UpdateStates = UpdateChildrenAndParentLocation;    /* Use coordinates */
  }
  else{
    FindWinner = FindWinnerEucledian;   /* Use standard Eucledian distance */
    UpdateStates = UpdateChildrensLocation;  /* Update neighbors only */
  }

  /* Compute the total number of nodes in given dataset, and the maximum
     number of nodes in a single graph */
  n = 0;
  nmax = 0;
  for (gptr = graph; gptr != NULL; gptr = gptr->next){
    n += gptr->numnodes;
    if (nmax < gptr->numnodes)
      nmax = gptr->numnodes;
  }

  qerror = 0.0;
  gpr_qerror = 0.0;
  int *xstates, *ystates;
  xstates = (int*)MyMalloc(nmax * sizeof(int));
  ystates = (int*)MyMalloc(nmax * sizeof(int));
  for (gptr = graph; gptr != NULL; gptr = gptr->next){

    iter = 0;
    for(iter = 0; iter <= gptr->depth; iter++){
      gpr_qerror = 0.0;
      statechanges = 0;

      /* Compute the state of every node in the graph */
      for (nnum = 0; nnum < gptr->numnodes; nnum++){
	node = gptr->nodes[nnum];
	UpdateStates(gptr, node);
	FindWinner(map, node, gptr, &winner);
	gpr_qerror += winner.diff;

	if (map->topology == TOPOL_VQ){
	  /* Inclomplete implementation for VQ mode: Need to update
	     node->winner in batch mode. Perhaps we can abuse xstates
	     for this task. */
	  node->winner = winner.codeno;
	}
	else{
	  xstates[nnum] = map->codes[winner.codeno].x;
	  ystates[nnum] = map->codes[winner.codeno].y;
	}
      }

      /* Update state of every node in the graph */
      for (nnum = 0; nnum < gptr->numnodes; nnum++){
	node = gptr->nodes[nnum];
	node->x = xstates[nnum];
	node->y = ystates[nnum];
      }
    }

    /* Update point-vector of every node */
    for (nnum = 0; nnum < gptr->numnodes; nnum++){
      node = gptr->nodes[nnum];
      UpdateStates(gptr, node);
    }
    qerror += gpr_qerror;
  }
  free(xstates);
  free(ystates);

  return qerror/n;
}


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

Return value: The quantization error.
*****************************************************************************/
FLOAT GetNodeCoordinates(struct Map *map, struct Graph *gptr)
{
  UNSIGNED nnum, n;
  FLOAT qerror;
  struct Node *node;
  struct Winner winner;
  void (*FindWinner)(struct Map *map, struct Node *node,struct Graph *gptr,struct Winner *winner);
  void (*UpdateOffspringStates)(struct Graph *gptr, struct Node *node);

  if (map == NULL && gptr == NULL)
    return 0.0;

  n = 0;
  qerror = 0.0;
  if (map->topology == TOPOL_VQ){            /* In VQ mode...   */
    FindWinner = VQFindWinnerEucledian; /* Use Eucledian distance VQ mode  */
    UpdateOffspringStates = UpdateChildrensLocationVQ; /* use ID value    */
  }
  else{
    FindWinner = FindWinnerEucledian;   /* Use standart Eucledian distance */