ptree1.c

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

  lvl = pt->levels +pt->concnt; /* get the number of params. per leaf */
  n   = lvl->cnt -((pt->type & PT_POSS) ? 0 : 1);
  return pt->parcnt = pt->leafcnt *n;
}  /* pt_parcnt() */            /* return the number of parameters */

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

float pt_total (PTREE *pt)
{                               /* --- compute totals of counters */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* to traverse the levels */
  PTLEAF *leaf;                 /* to traverse the leaves */
  float  *c;                    /* to traverse the counters */
  float  s = 0, t;              /* buffers for totals */

  assert(pt);                   /* check the function argument */
  if (pt->total >= 0)           /* if the total is valid, */
    return pt->total;           /* simply return it */
  lvl = pt->levels +pt->concnt; /* traverse the leaf nodes */
  for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ) {
    c = leaf->cnts +(i = lvl->cnt);
    t = 0;                      /* traverse the counters */
    if (pt->type & PT_POSS) {   /* if possibility tree */
      while (--i >= 0) if (*--c > t) t = *c;
      if (t > s) s = t; }       /* find leaf maximum and global max. */
    else {                      /* if probability tree */
      while (--i >= 0) t += *--c;
      s += t;                   /* sum the counters in the leaf */
    }                           /* and all counters in the tree */
    leaf->total = t;            /* store the leaf total */
  }
  return pt->total = s;         /* return the computed total */
}  /* pt_total() */

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

static int _aggr (PTLVL *lvl, PTNODE *node, float wgt, int type)
{                               /* --- recursively aggregate weight */
  int    i;                     /* loop variable, buffer for instance */
  PTNODE *child;                /* to traverse the children */
  float  *c;                    /* to traverse the counters */

  assert(lvl && node);          /* check the function arguments */
  i = att_inst(lvl->att)->i;    /* get the attribute instance */
  assert(i < lvl->cnt);         /* and check its value */
  if (lvl->index < 0) {         /* --- if the node is a leaf node */
    if (i >= 0) {               /* if the attribute value is known, */
      c = ((PTLEAF*)node)->cnts +i;  /* update the corresp. counter */
      if (type == PT_PROB) *c += wgt;
      else if (wgt > *c)   *c  = wgt; }
    else {                      /* if the attribute value is unknown */
      c = ((PTLEAF*)node)->cnts +(i = lvl->cnt);
      if (type & PT_POSS) {     /* if possibility tree */
        while (--i >= 0) if (wgt > *--c) *c = wgt; }
      else {                    /* if probability tree */
        ((PTLEAF*)node)->total += wgt; wgt /= lvl->cnt;
        while (--i >= 0) *c += wgt;
      }                         /* update all counters of the leaf */
    } }                         /* and the leaf total */
  else {                        /* --- if the node is an inner node */
    if (i >= 0) {               /* if the attribute value is known */
      node = _child(++lvl, node, i);
      if (!node) return -1;     /* get the corresponding child node */ 
      _aggr(lvl, node, wgt, type); }   /* and aggregate recursively */
    else {                      /* if the attribute value is unknown */
      if (type == PT_PROB)      /* for probability trees distribute */
        wgt /= lvl->cnt;        /* the weight equally on all values */
      for (i = (lvl++)->cnt; --i >= 0; ) {
        child = _child(lvl, node, i);
        if (!child) return -1;  /* traverse the child nodes */
        _aggr(lvl, child, wgt, type);
      }                         /* aggregate recursively */
    }                           /* for all children */
  }
  return 0;                     /* return 'ok' */
}  /* _aggr() */

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

int pt_aggr (PTREE *pt, float wgt, int distuv)
{                               /* --- aggregate weight of an inst. */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* to traverse the levels */
  PTNODE *node;                 /* to traverse the nodes */

  assert(pt);                   /* check the function argument */
  lvl  = pt->levels;            /* get the level vector */
  node = _child(lvl, NULL, 0);  /* get the root node or */
  if (!node) return -1;         /* create it if necessary */
  if (distuv                    /* if to distribute for unknowns */
  || (pt->type & PT_POSS)) {    /* of this is a possibility tree */
    i = _aggr(lvl, node, wgt, pt->type);
    if (i == 0) {               /* aggregate recursively */
      if (pt->type & PT_POSS) pt->total = -1;
      else pt->total += wgt;    /* on success invalidate or */
      pt->occur = 0;            /* update the counter total */
    }                           /* and clear the occurrence flag */
    return i;                   /* return a success indicator */
  }
  while (1) {                   /* traverse the tree levels */
    i = att_inst(lvl->att)->i;  /* get the value of the condition */
    assert(i < lvl->cnt);       /* check for a valid value identifier */
    if (i < 0) return 1;        /* check for an unknown value */
    if (lvl->index < 0) break;  /* abort loop on the leaf level */
    node = _child(++lvl, node, i);
    if (!node) return -1;       /* go to the child node or */
  }                             /* create it if necessary */
  ((PTLEAF*)node)->cnts[i] += wgt;
  ((PTLEAF*)node)->total   += wgt;
  pt->total += wgt;             /* aggregate the value */
  return pt->occur = 0;         /* return 'ok' */
}  /* pt_aggr() */

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

int pt_rand (PTREE *pt, double randfn(void))
{                               /* --- compute a random value index */
  int    i, k, m;               /* loop variables, buffers */
  PTLVL  *lvl;                  /* to traverse the tree levels */
  PTNODE *node;                 /* to traverse the prob./poss. tree */
  float  *c;                    /* to traverse the counters */
  float  *buf;                  /* to access the counter buffer */
  double sum;                   /* sum of counters/random value */

  assert(pt                     /* check the function arguments */
     && (pt->type == PT_PROB) && randfn);
  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 value of the condition */
    assert(i < lvl->cnt);       /* and check its validity */
    if (i < 0) return -1;       /* check for an unknown value */
    node = node->children[i];   /* get the corresponding child node */
    if (!node) return  0;       /* if it does not exist, abort */
  }
  sum = 0; c = ((PTLEAF*)node)->cnts;
  buf = lvl->buf; k = lvl->cnt; /* traverse the counter vector and */
  for (i = 0; i < k; i++)       /* build a distribution function */
    buf[i] = (float)(sum += c[i] +pt->lcorr);
  sum *= randfn();              /* generate a random value and */
  for (i = 0; i < k; ) {        /* do a binary search in the */
    m = (i+k) >> 1;             /* distribution function to find */
    if (sum >= buf[m]) i = m+1; /* the corresponding value index */
    else               k = m;   /* after this search it is */
  }                             /* buf[i-1] <= sum < buf[i], */
  return i;                     /* so return the index i */
}  /* pt_rand() */

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

float pt_exec (PTREE *pt)
{                               /* --- execute a prob./poss. tree */
  int    i, k;                  /* loop variable, buffer */
  PTLVL  *lvl;                  /* to traverse the levels */
  PTNODE *node;                 /* to traverse the nodes */
  float  t;                     /* temporary buffer */

  assert(pt);                   /* check the function arguments */
  if (pt->total < 0)            /* if the totals are not valid, */
    pt_total(pt);               /* compute them (for normalization) */
  lvl  = pt->levels;            /* get the tree levels and */
  node = lvl->list;             /* traverse the conditions */
  for (k = pt->concnt; node && (--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 the attribute value */
  if (!node) {                  /* if no leaf could be reached, */
    if (pt->type & PT_POSS)     /* return a default value */
      t = ((pt->tplcnt >= 0) ? pt->tplcnt : pt->total) +pt->lcorr;
    else t = pt->levels[pt->concnt].cnt *pt->lcorr;
    return pt->lcorr / (t +FLT_MIN);
  }
  i = att_inst(lvl->att)->i;    /* get the attribute instance */
  assert(i < lvl->cnt);         /* and check the attribute value */
  if (i < 0) return -1;         /* if the value is unknown, abort */
  if (pt->type & PT_POSS)       /* get the normalization value */
    t = ((pt->tplcnt >= 0) ? pt->tplcnt : pt->total) +pt->lcorr;
  else t = ((PTLEAF*)node)->total +lvl->cnt *pt->lcorr;
  return (((PTLEAF*)node)->cnts[i] +pt->lcorr) / (t +FLT_MIN);
}  /* pt_exec() */              /* return rel. freq./deg. of poss. */

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

static float _poss (PTLVL *lvl, PTNODE *node)
{                               /* --- recursively det. poss. degree */
  int    i;                     /* loop variable, buffer for instance */
  PTNODE **p;                   /* to traverse the vector of children */
  float  *c;                    /* to traverse the counters */
  float  max, t;                /* degree of possibility, buffer */

  assert(lvl);                  /* check the function argument */
  if (!node) return 0;          /* if there is no node, abort */
  i = att_inst(lvl->att)->i;    /* get the attribute instance */
  assert(i < lvl->cnt);         /* and check the value */
  if (lvl->index < 0) {         /* --- if the node is a leaf */
    if (i >= 0)                 /* if the attribute value is known, */
      return ((PTLEAF*)node)->cnts[i];  /* return the corr. counter */
    max = 0;                    /* otherwise traverse the counters */
    for (c = ((PTLEAF*)node)->cnts +(i = lvl->cnt); --i >= 0; ) {
      if (*--c > max) max = *c; /* determine the maximum */
    } }                         /* of all counters in the leaf */
  else {                        /* --- if the node is an inner node */
    if (i >= 0)                 /* if the attribute value is known, */
      return _poss(lvl+1, node->children[i]);    /* go to the child */
    max = 0;                    /* otherwise traverse the children */
    for (p = node->children +(i = (lvl++)->cnt); --i >= 0; ) {
      t = _poss(lvl, *--p);     /* recursively process each child */
      if (t > max) max = t;     /* determine the maximum over */
    }                           /* all children of the node */
  }
  return max;                   /* return the computed maximum */
}  /* _poss() */

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

float pt_poss (PTREE *pt)
{                               /* --- det. degree of possibility */
  assert(pt);                   /* check the function argument */
  return (_poss(pt->levels, pt->levels[0].list) +pt->lcorr)
       / (((pt->tplcnt >= 0) ? pt->tplcnt : pt->total)
          + pt->lcorr +FLT_MIN);
}  /* pt_poss() */              /* determine maximum recursively */