ptree1.c

数据挖掘中的一算法 ines算法 c下实现的。适合初学习数据挖掘者借鉴

  }
}  /* pt_conrem() */

/*--------------------------------------------------------------------*/

int pt_concopy (PTREE *dst, PTREE *src)
{                               /* --- copy conditions of a tree */
  int i;                        /* loop variable */

  assert(dst && src);           /* check the function arguments */
  for (i = 0; i < src->concnt; i++)
    if (pt_conadd(dst, i, src->levels[i].att) != 0)
      return -1;                /* add all conditions from source */
  return 0;                     /* return 'ok' */
}  /* pt_concopy() */

/*--------------------------------------------------------------------*/

void pt_down (PTREE *pt, int index)
{                               /* --- go down in prob./poss. tree */
  PTLVL *lvl;                   /* the current tree level */

  assert(pt && !pt_atleaf(pt)   /* check the function arguments */
      && (index >= 0) && (index <= pt->levels[pt->pathlen].cnt));
  lvl = pt->levels +pt->pathlen++; /* get the current level and */
  lvl->index = index;              /* note the child index used */
  if (pt->curr)                 /* get the corresponding child node */
    pt->curr = pt->curr->children[index];
  (++lvl)->node = pt->curr;     /* note the node on the next level */
}  /* pt_down() */

/*--------------------------------------------------------------------*/

void pt_up (PTREE *pt, int mode)
{                               /* --- go up in prob./poss. tree */
  PTLVL  *lvl;                  /* the current tree level */
  PTNODE *node;                 /* to traverse the ancestor nodes */

  assert(pt);                   /* check the function argument */
  lvl = pt->levels;             /* get the level descriptions */
  if ((mode == PT_ROOT)         /* if to go to the root node */
  ||  (pt->pathlen <= 0)) {     /* or if there is no path, */
    pt->curr = lvl->list;       /* make the root node the */
    pt->pathlen = 0; return;    /* current node and clear the path */
  }
  lvl += --pt->pathlen;         /* get the parent level */
  if ((mode != PT_PARENT)       /* if not to go to the true parent */
  ||  !pt->curr)                /* or if there is no current node, */
    pt->curr = lvl->node;       /* go to the node from the path */
  else {                        /* if to go to the true parent, */
    pt->curr = node = pt->curr->parent;  /* get the true parent */
    while (node != lvl->node) { /* if not descended from the parent, */
      lvl->node      = node;    /* build a new path with true parent */
      (--lvl)->index = node->index & ~PT_OCCUR;
      node = node->parent;      /* and the index in the parent, */
    }                           /* then go up in the tree */
  }                             /* (loop must terminate at root) */
}  /* pt_up() */

/*--------------------------------------------------------------------*/

int pt_setcnt (PTREE *pt, int index, float cnt)
{                               /* --- set a counter in current node */
  PTLEAF *leaf;                 /* leaf to modify */
  float  old;                   /* buffer for the old value */

  assert(pt && pt_atleaf(pt)    /* check the function arguments */
     && (index >= 0) && (index < pt->levels[pt->pathlen].cnt)
     && (cnt   >= 0));
  if (!pt->curr && (_path(pt) != 0))
    return -1;                  /* create missing nodes if necessary */
  leaf = (PTLEAF*)pt->curr;     /* get the leaf to modify */
  if (pt->type & PT_POSS) {     /* if possibility tree, */
    leaf->cnts[index] = cnt;    /* set the new value and */
    pt->total = -1; }           /* invalidate the total */
  else {                        /* if probability tree, */
    old = leaf->cnts[index];    /* note the old counter value */
    leaf->cnts[index] = cnt;    /* and set the new value */
    leaf->total += cnt -= old;  /* adapt the totals of the leaf */
    pt->total   += cnt;         /* and of the whole tree */
  }
  return pt->occur = 0;         /* clear occ. flag and return 'ok' */
}  /* pt_setcnt() */

/*--------------------------------------------------------------------*/

float pt_getcntx (PTREE *pt)
{                               /* --- get counter of current inst. */
  int    i, k;                  /* loop variable, buffer */
  PTLVL  *lvl;                  /* to traverse the levels */
  PTNODE *node;                 /* to traverse the nodes */
  
  assert(pt);                   /* check the function arguments */
  lvl  = pt->levels;            /* get the level vector */
  node = lvl->list;             /* and the root node and */
  if (!node) return 0;          /* traverse the conditions */
  for (k = pt->concnt; --k >= 0; lvl++) {
    i = att_inst(lvl->att)->i;  /* get the instance of the condition */
    assert(i < lvl->cnt);       /* and check the attribute value */
    if (i < 0) return -1;       /* if the value is unknown, abort */
    node = node->children[i];   /* get the child corresponding to */
    if (!node) return 0;        /* the attribute value and */
  }                             /* if it is missing, abort */
  i = att_inst(lvl->att)->i;    /* get the attribute instance and */
  assert(i < lvl->cnt);         /* return the corresponding counter */
  return (i >= 0) ? ((PTLEAF*)node)->cnts[i] : -1;
}  /* pt_getcntx() */

/*--------------------------------------------------------------------*/

float pt_gettot (PTREE *pt)
{                               /* --- get aggregate of counters */
  assert(pt && pt_atleaf(pt));  /* check the function argument */
  if (!pt->curr)                /* if there is no current node, */
    return 0;                   /* all counters are zero (default) */
  if (pt->total < 0)            /* if the totals are invalid, */
    pt_total(pt);               /* compute the counter totals */
  return ((PTLEAF*)pt->curr)->total;
}  /* pt_gettot() */            /* return the leaf total */

/*--------------------------------------------------------------------*/

int pt_occur (PTREE *pt)
{                               /* --- check for nonzero counters */
  int    i, k;                  /* loop variables */
  PTLVL  *lvl;                  /* to traverse the levels */
  PTNODE *node;                 /* to traverse the inner nodes */
  PTNODE **p;                   /* to traverse the child vectors */
  PTLEAF *leaf;                 /* to traverse the leaves */

  assert(pt);                   /* check the function argument */
  if (!pt->occur) {             /* if the flags are not set */
    if (pt->total < 0)          /* if the leaf totals are not valid, */
      pt_total(pt);             /* compute them first */
    lvl = pt->levels+pt->concnt;/* traverse the leaf nodes */
    for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ) {
      if (leaf->total <= 0) leaf->index &= ~PT_OCCUR;
      else                  leaf->index |=  PT_OCCUR;
    }                           /* clear/set the node occurrence flag */
    for (k = pt->concnt; --k >= 0; ) {
      for (node = (--lvl)->list; node; node = node->succ) {
        for (p = node->children +(i = lvl->cnt); --i >= 0; )
          if (*--p && ((*p)->index & PT_OCCUR)) break;
        if (i < 0) node->index &= ~PT_OCCUR;
        else       node->index |=  PT_OCCUR;
      }                         /* traverse the other tree levels */
    }                           /* and set the occurrence flags */
    pt->occur = -1;             /* set the global flag */
  }
  return (pt->curr) ? pt->curr->index & PT_OCCUR : 0;
}  /* pt_occur() */             /* return the occurrence flag */

/*--------------------------------------------------------------------*/

int pt_path (PTREE *pt, int *path)
{                               /* --- get path to current node */
  int    i;                     /* loop variable */
  PTNODE *node;                 /* to traverse the parent nodes */
  PTLVL  *lvl;                  /* to traverse the path to the node */

  assert(pt && path);           /* check the function arguments */
  node = pt->curr;              /* start at the current node, */
  lvl  = pt->levels+pt->pathlen;/* which is the last on the path */
  for (path += (i = pt->pathlen); --i >= 0; ) {
    if (!node) {                /* if there is no current node, */
      *--path = (--lvl)->index; /* get the child index and the */
      node    = lvl->node; }    /* parent node from the path */
    else {                      /* if there is a current node, */
      *--path = node->index & ~PT_OCCUR;
      node    = node->parent;   /* note index in parent node */
    }                           /* and go to the parent node */
  }
  return pt->pathlen;           /* return the length of the path */
}  /* pt_path() */

/*--------------------------------------------------------------------*/

int pt_link (PTREE *pt, int index, const int *path)
{                               /* --- set a link to another node */
  int    i, k;                  /* loop variable, buffer */
  PTLVL  *lvl;                  /* to traverse the level descriptions */
  PTNODE *node;                 /* to traverse the nodes on the path */

  assert(pt && !pt_atleaf(pt)   /* check the function arguments */
     && (index >= 0) && (index <= pt->levels[pt->pathlen].cnt));
  if (!pt->curr && (_path(pt) != 0))
    return -1;                  /* create missing nodes if necessary */
  lvl  = pt->levels;            /* start at the root node and */
  node = lvl->list;             /* traverse the path to link to */
  for (i = pt->pathlen +1; --i >= 0; ) {
    k = (path) ? *path++ : lvl->link;
    assert(k < lvl->cnt);       /* get and check the child index */
    node = _child(++lvl, node, k);
    if (!node) return -1;       /* go to the child node and */
  }                             /* create it if necessary */
  pt->curr->children[index] = node;
  return pt->parcnt = 0;        /* install the link and return 'ok' */
}  /* pt_link() */

/*--------------------------------------------------------------------*/

int pt_parcnt (PTREE *pt)
{                               /* --- get the number of parameters */
  int    i, k, n;               /* loop variables, number od leaves */
  PTLVL  *lvl;                  /* to traverse the level descriptions */
  PTNODE *node, **p;            /* to traverse the nodes/children */

  assert(pt);                   /* check the function argument */
  if (pt->parcnt > 0)           /* if the number of parameters */
    return pt->parcnt;          /* is valid, simply return it */
  lvl = pt->levels +pt->concnt; /* traverse the tree levels */
  for (n = 1, i = pt->concnt; --i >= 0; )
    n *= (--lvl)->cnt;          /* compute full number of leaves */
  pt->fullcnt = n; n = 0;       /* note the full number of leaves */
  if (lvl->list) {              /* if the tree is not empty, */
    lvl->list->pathcnt = 1;     /* start with one path at the root */
    for (i = pt->concnt; --i >= 0; lvl++) { /* traverse the levels */
      for (node = (lvl+1)->list; node; node = node->succ)
        node->pathcnt = 0;      /* clear all path counters */
      for (node = lvl->list; node; node = node->succ)
        for (p = node->children +(k = lvl->cnt); --k >= 0; )
          if (*--p) (*p)->pathcnt += node->pathcnt;
    }                           /* sum the number of paths to a node */
    for (node = lvl->list; node; node = node->succ)
      n += node->pathcnt -1;    /* count the number of leaves */
  }                             /* that are merged to other leaves */
  pt->leafcnt = pt->fullcnt -n; /* compute the number of leaves and */