ptree4.c

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

  float  *b, *c;                /* to traverse the buffer/counters */
  double sum = 0, max = 0, t;   /* sum/maximum of terms, buffers */

  assert(pt && lvl && leaf);    /* check the function arguments */
  b = lvl->buf +lvl->cnt;       /* traverse marginal and joint dist. */
  for (c = leaf->cnts +(i = lvl->cnt); --i >= 0; ) {
    --c; if (*--b <= 0) continue;   /* skip empty counters */
    t = (double)*c / *b;        /* compute frequency ratio */
    if (t <= max) sum += t;     /* and sum these ratios */
    else        { sum += max; max = t; }
  }                             /* exclude the/one maximal ratio */
  return sum;                   /* return the computed sum */
}  /* _l_relev() */

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

static double _wdiff (PTREE *pt)
{ double t = pt->total;         /* --- weighted differences */
  return pt->res1[0] /pow(t, 2*pt->params[0] +1);
}  /* _wdiff() */

static double _chi2 (PTREE *pt)
{ double t = pt->total;         /* --- chi^2 measure */
  return pt->res1[0] /(t *t);
}  /* _chi2() */

static double _chi2nrm (PTREE *pt)
{ double t    = pt->total;      /* --- normalized chi^2 measure */
  PTLVL  *lvl = pt->levels +pt->concnt;
  if ((lvl->cnt < 2) || (pt->res1[1] <= 0)) return 0;
  return pt->res1[0] /(t *t *(lvl->cnt-1) *pt->res1[1]);
}  /* _chi2nrm() */

static double _evid (PTREE *pt)
{ double t = pt->total;         /* --- weight of evidence */
  return pt->res1[0] /(t *t *M_LN2);
}  /* _evid() */

static double _relev (PTREE *pt)
{                               /* --- relevance */
  return 1 -pt->res1[0] /pt->levels[pt->concnt].cnt;
}  /* _relev() */

/*----------------------------------------------------------------------
  Possibilistic Leaf Functions
----------------------------------------------------------------------*/

static double _l_pdiff (PTREE *pt, PTLVL *lvl, PTLEAF *leaf)
{                               /* --- weighted differences */
  int    i;                     /* loop variable */
  float  *b, *c;                /* to traverse the buffer/counters */
  double sum = 0, t;            /* sum of difference terms, buffer */

  assert(pt && lvl && leaf);    /* check the function arguments */
  b = lvl->buf +(i = lvl->cnt); /* traverse marginal distribution */
  c = leaf->cnts +i;            /* and joint distribution */
  if      (pt->params[0] == 1) {
    while (--i >= 0) {          /* if the exponent is 1 */
      t = ((*--b < leaf->total) ? *b : leaf->total) - *--c;
      sum += *c *fabs(t);       /* sum the weighted absolute */
    } }                         /* differences */
  else if (pt->params[0] == 2) {
    while (--i >= 0) {          /* if the exponent is 2 */
      t = ((*--b < leaf->total) ? *b : leaf->total) - *--c;
      sum += *c *t *t;          /* sum the weighted squared */
    } }                         /* differences */
  else {                        /* if the exponent is anything */
    while (--i >= 0) {          /* other than 1 or 2 */
      t = ((*--b < leaf->total) ? *b : leaf->total) - *--c;
      sum += *c *pow(fabs(t), pt->params[0]);
    }                           /* sum the weighted differences */
  }                             /* raised to the given power */
  return sum;                   /* return the computed sum */
}  /* _l_pdiff() */

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

static double _l_pchi2 (PTREE *pt, PTLVL *lvl, PTLEAF *leaf)
{                               /* --- possibilistic chi^2 measure */
  int    i;                     /* loop variable */
  float  *b, *c;                /* to traverse the buffer/counters */
  double sum = 0, t, p;         /* sum of difference terms, buffers */

  assert(pt && lvl && leaf);    /* check the function arguments */
  b = lvl->buf +lvl->cnt;       /* traverse marginal and joint dist. */
  for (c = leaf->cnts +(i = lvl->cnt); --i >= 0; ) {
    --c; p = (*--b < leaf->total) ? *b : leaf->total;
    if (p <= 0) continue;       /* compute minimum of marginals */
    t = p - *c;                 /* and difference to joint poss. */
    sum += t *t /p;             /* sum the chi^2 terms */
  }                             /* (modified squared differences) */
  return sum;                   /* and return this sum */
}  /* _l_pchi2() */

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

static double _l_mutspc (PTREE *pt, PTLVL *lvl, PTLEAF *leaf)
{                               /* --- mutual specificity */
  int    i;                     /* loop variable */
  float  *b, *c;                /* to traverse the buffer/counters */
  double sum = 0, t;            /* sum of difference terms, buffer */

  assert(pt && lvl && leaf);    /* check the function arguments */
  b = lvl->buf +lvl->cnt;       /* traverse marginal and joint dist. */
  for (c = leaf->cnts +(i = lvl->cnt); --i >= 0; ) {
    t = (*--b < leaf->total) ? *b : leaf->total;
    if ((*--c > 0) && (t > 0)) sum += *c *log(t / *c);
  }                             /* sum weighted logs of quotients */
  return sum;                   /* and return this sum */
}  /* _l_mutspc() */

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

static double _pdiff (PTREE *pt)
{                               /* --- weighted differences */
  return pt->res1[0]
       / ((pt->tplcnt > 0) ? pow(pt->tplcnt, pt->params[0]+1) : 1);
}  /* _pdiff() */

static double _pchi2 (PTREE *pt)
{                               /* --- poss. chi^2 measure */
  return pt->res1[0] /((pt->tplcnt > 0) ? pt->tplcnt : 1);
}  /* _pchi2() */

static double _mutspc (PTREE *pt)
{                               /* --- mutual specificity */
  return pt->res1[0] /((pt->tplcnt > 0) ? pt->tplcnt : 1);
}  /* _mutspc() */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static int _generic (PTREE *pt);

static FTE fn_prob[PT_UNKNOWN+1] = {
  /* PT_NONE     0 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /* PT_INFGAIN  1 */ { _info,      _gain,      (LEAFFN*)0 },
  /* PT_INFGBAL  2 */ { _info,      _gbal,      (LEAFFN*)0 },
  /* PT_INFGR    3 */ { _info,      _gratio,    (LEAFFN*)0 },
  /* PT_INFSGR1  4 */ { _info,      _sgr1,      (LEAFFN*)0 },
  /* PT_INFSGR2  5 */ { _info,      _sgr2,      (LEAFFN*)0 },
  /* PT_QIGAIN   6 */ { _quad,      _gain,      (LEAFFN*)0 },
  /* PT_QIGBAL   7 */ { _quad,      _gbal,      (LEAFFN*)0 },
  /* PT_QIGR     8 */ { _quad,      _gratio,    (LEAFFN*)0 },
  /* PT_QISGR1   9 */ { _quad,      _sgr1,      (LEAFFN*)0 },
  /* PT_QISGR2  10 */ { _quad,      _sgr2,      (LEAFFN*)0 },
  /* PT_GINI    11 */ { _ginit1,    _gini,      (LEAFFN*)0 },
  /* PT_GINISYM 12 */ { _ginit2,    _ginisym,   (LEAFFN*)0 },
  /* PT_GINIMOD 13 */ { _ginit1,    _ginimod,   (LEAFFN*)0 },
  /* PT_RELIEF  14 */ { _ginit1,    _relief,    (LEAFFN*)0 },
  /* PT_WDIFF   15 */ { _generic,   _wdiff,     _l_wdiff   },
  /* PT_CHI2    16 */ { _generic,   _chi2,      _l_chi2    },
  /* PT_CHI2NRM 17 */ { _generic,   _chi2nrm,   _l_chi2    },
  /* PT_WOEVID  18 */ { _generic,   _evid,      _l_evid    },
  /* PT_RELEV   19 */ { _generic,   _relev,     _l_relev   },
  /* PT_BDM     20 */ { _bdm,       _bfactor,   (LEAFFN*)0 },
  /* PT_BDMOD   21 */ { _bdmod,     _bfactor,   (LEAFFN*)0 },
  /* PT_RDLREL  22 */ { _dlrel,     _rdlen,     (LEAFFN*)0 },
  /* PT_RDLABS  23 */ { _dlabs,     _rdlen,     (LEAFFN*)0 },
  /* PT_STOCO   24 */ { _scinit,    _stoco,     (LEAFFN*)0 },
  /* PT_UNKNOWN 25 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
};                              /* functions for probability trees */

static FTE fn_poss[PT_UNKNOWN+1] = {
  /* PT_NONE     0 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /* PT_SPCGAIN  1 */ { _spec,      _gain,      (LEAFFN*)0 },
  /* PT_SPCGBAL  2 */ { _spec,      _gbal,      (LEAFFN*)0 },
  /* PT_SPCGR    3 */ { _spec,      _gratio,    (LEAFFN*)0 },
  /* PT_SPCSGR1  4 */ { _spec,      _sgr1,      (LEAFFN*)0 },
  /* PT_SPCGR2   5 */ { _spec,      _sgr2,      (LEAFFN*)0 },
  /*             6 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*             7 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*             8 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*             9 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            10 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            11 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            12 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            13 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            14 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /* PT_WDIFF   15 */ { _generic,   _pdiff,     _l_pdiff   },
  /* PT_CHI2    16 */ { _generic,   _pchi2,     _l_pchi2   },
  /*            17 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            18 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            19 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /* PT_MUTSPC  20 */ { _generic,   _mutspc,    _l_mutspc  },
  /*            21 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            22 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            23 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            24 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
  /*            25 */ { (INITFN*)0, (EVALFN*)0, (LEAFFN*)0 },
};                              /* functions for possibility trees */

/*----------------------------------------------------------------------
  Generic Initialization Function
----------------------------------------------------------------------*/

static int _generic (PTREE *pt)
{                               /* --- generic init. function */
  PTLVL  *lvl;                  /* leaf level description */
  PTLEAF *leaf;                 /* to traverse the leaves */
  LEAFFN *fn;                   /* function to process a leaf */
  double sum = 0;               /* sum of leaf terms */

  assert(pt && (pt->total > 0));/* check the function arguments */
  fn  = ((pt->type == PT_PROB) ? fn_prob : fn_poss)[pt->measure].leaffn;
  lvl = pt->levels +pt->concnt; /* get the leaf level */
  for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ)
    sum += leaf->eval = fn(pt, lvl, leaf);
  pt->res0[0] = sum;            /* sum the difference terms */
  pt->res0[1] = pt->leafcnt-1;  /* and note the sum */
  return 0;                     /* return 'ok' */
}  /* _generic() */

/*----------------------------------------------------------------------
  Main Function
----------------------------------------------------------------------*/

double pt_eval (PTREE *pt, int measure, double *params)
{                               /* --- evaluate condition tree */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* to traverse the levels */
  PTLEAF *leaf;                 /* to traverse the leaves */
  float  *b, *c;                /* to traverse the buffers/counters */
  FTE    *fte;                  /* function table element */
  double r;                     /* evaluation result */

  assert(pt);                   /* check the function arguments */
  pt_total(pt);                 /* compute the counter totals and */
  pt->parcnt = 0;               /* the number of parameters/leaves */
  pt_parcnt(pt);                /* (and set the path counters) */
  if ((measure < PT_NONE) || (measure >= PT_UNKNOWN))
    return PT_ERROR;            /* check the measure identifier */
  if ((measure == PT_NONE)      /* if no measure is selected */
  ||  (pt->concnt <= 0)         /* or there are no conditions */
  ||  (pt->total  <= 0))        /* or all counters are zero, */
    return 0;                   /* abort the function */
  pt->measure = measure;        /* note the evaluation measure */
  pt->params[0] = (params) ? params[0] : 0;  /* as well as the */
  pt->params[1] = (params) ? params[1] : 1;  /* parameters */
  lvl = pt->levels +pt->concnt; /* get the leaf level and */
  lvl->list = NULL;             /* sort the leaf nodes */
  _sort(pt->levels, pt->levels->list);
  for (b = lvl->buf +(i = lvl->cnt); --i >= 0; )
    *--b = 0;                   /* clear the leaf marginals */
  for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ) {
    b += i = lvl->cnt;          /* traverse the leaf level and */
    c  = leaf->cnts +i;         /* the counters of each leaf */
    if (pt->type == PT_PROB) {  /* probability tree: sum */
      while (--i >= 0) *--b += *--c; }
    else {                      /* possibility tree: maximum */
      while (--i >= 0) if (*--c > *--b) *b = *c; }
  }                             /* compute marginal distribution */
  fte = ((pt->type == PT_PROB) ? fn_prob : fn_poss) +measure;
  if (fte->initfn(pt) != 0)     /* initialize the evaluation */
    return PT_ERROR;            /* (may fail due to memory alloc.) */
  for (i = sizeof(pt->res0)/sizeof(double); --i >= 0; )
    pt->res1[i] = pt->res0[i];  /* copy the intermediate results */
  r = fte->evalfn(pt);          /* evaluate the prob./poss. tree */
  return pt->eval = (fabs(r) < DBL_EPSILON) ? 0 : r;
}  /* pt_eval() */              /* return the evaluation result */

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

double pt_reeval (PTREE *pt)
{                               /* --- reevaluate condition tree */
  FTE    *fte;                  /* function table element */
  double r;                     /* evaluation result */

  assert(pt);                   /* check the function arguments */
  if ((pt->measure == PT_NONE)  /* if no measure was selected */
  ||  (pt->concnt  <= 0)        /* or there are no conditions */
  ||  (pt->total   <= 0))       /* or all counters are zero, */
    return 0;                   /* abort the function */
  fte = ((pt->type == PT_PROB) ? fn_prob : fn_poss) +pt->measure;
  r   = fte->evalfn(pt);        /* reevaluate the prob./poss. tree */
  return pt->eval = (fabs(r) < DBL_EPSILON) ? 0 : r;
}  /* pt_reeval() */            /* return the evaluation result */