ptree3.c

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

        t = ((*--bc < bp) ? *bc : bp) -*--c; pdiff += *c *fabs(t); }
    else if (e == 2)            /* if exponent for difference is 2, */
      while (--i >= 0) {        /* sum weighted squared differences */
        t = ((*--bc < bp) ? *bc : bp) -*--c; pdiff += *c *t *t; }
    else {                      /* if any other exponent, */
      while (--i >= 0) {        /* raise differences to given power */
        t = ((*--bc < bp) ? *bc : bp) -*--c;
        pdiff += *c *pow(fabs(t), *params);
      }                         /* (a call to the function pow() */
    }                           /* is costly, so it is avoided for */
  }                             /* the simple exponents 1 and 2) */
  return pdiff /lvl[1].total;   /* return the weighted difference */
}  /* _pdiff() */

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

static double _pchi2 (PTNODE *node, PTLVL *lvl,
                      int measure, double *params)
{                               /* --- possibilistic chi^2 measure */
  int    i, j;                  /* loop variables */
  PTNODE **p;                   /* to traverse the child vector */
  float  bp, *bc, *c;           /* to traverse the buffers/counters */
  double chi2 = 0, n, x, y;     /* chi^2 measure, buffers */

  assert(node && lvl);          /* check the function arguments */
  n = lvl[0].total;             /* get the total frequency */
  for (p = node->children +(i = lvl[0].cnt); --i >= 0; ) {
    if (!*--p) continue;        /* traverse the existing children */
    bp = lvl[0].buf[i];         /* get the parent frequency */
    bc = lvl[1].buf +lvl[1].cnt;
    for (c = ((PTLEAF*)*p)->cnts +(j = lvl[1].cnt); --j >= 0; ) {
      --c; y = (*--bc < bp) ? *bc : bp;
      if (y <= 0) continue;     /* traverse the child frequencies, */
      x = y - *c *n;            /* compute the denominator and the */
      chi2 += x*x /y;           /* numerator of the next term */
    }                           /* and sum these quotients */
  }
  return chi2 /lvl[1].total;    /* return the poss. chi^2 measure */
}  /* _pchi2() */

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

static double _mutspc (PTNODE *node, PTLVL *lvl,
                       int measure, double *params)
{                               /* --- mutual specificity */
  int    i, j;                  /* loop variables */
  PTNODE **p;                   /* to traverse the child vector */
  float  bp, *bc, *c;           /* to traverse the buffers */
  double mutspc = 0, n;         /* mutual specificity, buffers */

  assert(node && lvl);          /* check the function arguments */
  n = lvl[0].total;             /* get the total frequency */
  for (p = node->children +(j = lvl[0].cnt); --j >= 0; ) {
    if (!*--p) continue;        /* traverse the existing children */
    bp = lvl[0].buf[j];         /* get the parent frequency */
    bc = lvl[1].buf +lvl[1].cnt -1;
    for (c = ((PTLEAF*)*p)->cnts +(i = lvl[1].cnt); --i >= 0; bc--) {
      if (*--c <= 0) continue;  /* traverse the existing children */
      mutspc -= *c *log(*c / ((*bc < bp) ? *bc : bp));
    }                           /* traverse the child frequencies */
  }                             /* and compute the mutual specificity */
  return mutspc /lvl[1].total;  /* return the mutual specificity */
}  /* _mutspc() */

/*----------------------------------------------------------------------
  Tables of Evaluation Functions
----------------------------------------------------------------------*/
static DEPFN *dep_prob[PT_UNKNOWN+1] = {
  /* PT_NONE     0 */  (DEPFN*)0,
  /* PT_INFGAIN  1 */  _info,
  /* PT_INFGBAL  2 */  (DEPFN*)0,
  /* PT_INFGR    3 */  (DEPFN*)0,
  /* PT_INFSGR1  4 */  _info,
  /* PT_INFSGR2  5 */  _info,
  /* PT_QIGAIN   6 */  _quad,
  /* PT_QIGBAL   7 */  (DEPFN*)0,
  /* PT_QIGR     8 */  (DEPFN*)0,
  /* PT_QISGR1   9 */  _quad,
  /* PT_QISGR2  10 */  _quad,
  /* PT_GINI    11 */  (DEPFN*)0,
  /* PT_GINISYM 12 */  _gini,
  /* PT_GINI2   13 */  (DEPFN*)0,
  /* PT_RELIEF  14 */  (DEPFN*)0,
  /* PT_WDIFF   15 */  _wdiff,
  /* PT_CHI2    16 */  _chi2,
  /* PT_CHI2NRM 17 */  _chi2,
  /* PT_WOEVID  18 */  (DEPFN*)0,
  /* PT_RELEV   19 */  (DEPFN*)0,
  /* PT_BDM     20 */  (DEPFN*)0,
  /* PT_BDMOD   21 */  (DEPFN*)0,
  /* PT_RDLEN1  22 */  (DEPFN*)0,
  /* PT_RDLEN2  23 */  (DEPFN*)0,
  /* PT_STOCO   24 */  (DEPFN*)0,
  /* PT_UNKNOWN 25 */  (DEPFN*)0
};

static DEPFN *dep_poss[PT_UNKNOWN+1] = {
  /* PT_NONE     0 */  (DEPFN*)0,
  /* PT_SPCGAIN  1 */  _spec,
  /* PT_SPCGBAL  2 */  (DEPFN*)0,
  /* PT_SPCGR    3 */  (DEPFN*)0,
  /* PT_SPCSGR1  4 */  _spec,
  /* PT_SPCSGR2  5 */  _spec,
  /*             6 */  (DEPFN*)0,
  /*             7 */  (DEPFN*)0,
  /*             8 */  (DEPFN*)0,
  /*             9 */  (DEPFN*)0,
  /*            10 */  (DEPFN*)0,
  /*            11 */  (DEPFN*)0,
  /*            12 */  (DEPFN*)0,
  /*            13 */  (DEPFN*)0,
  /*            14 */  (DEPFN*)0,
  /* PT_WDIFF   15 */  _pdiff,
  /* PT_PCHI2   16 */  _pchi2,
  /*            17 */  (DEPFN*)0,
  /*            18 */  (DEPFN*)0,
  /*            19 */  (DEPFN*)0,
  /* PT_MUTSPC  20 */  _mutspc,
  /*            21 */  (DEPFN*)0,
  /*            22 */  (DEPFN*)0,
  /*            23 */  (DEPFN*)0,
  /*            24 */  (DEPFN*)0,
  /* PT_UNKNOWN 25 */  (DEPFN*)0
};

/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

double pt_depend (PTREE *pt, int measure, double *params)
{                               /* --- measure cond. independence */
  PTNODE *node;                 /* to traverse the nodes */
  PTLVL  *lvl;                  /* leaf level */
  MARGFN *margfn;               /* marginalization function */
  DEPFN  *depfn;                /* dependence measurement function */
  double n, sum;                /* weight of distribs. and their sum */
  double res;                   /* evaluation result */

  assert(pt);                   /* check the function arguments */
  if ((pt->concnt <= 0)         /* check the tree height */
  ||  (measure < PT_NONE) || (measure >= PT_UNKNOWN))
    return PT_ERROR;            /* check the measure identifier */
  if (pt->type == PT_PROB) {    /* if probability tree */
    margfn = _marg_sum; depfn = dep_prob[measure]; }
  else {                        /* if possibility tree */
    margfn = _marg_max; depfn = dep_poss[measure]; }
  if (!depfn) return PT_ERROR;  /* get marg. and meas. functions */
  lvl = pt->levels +pt->concnt -1;
  res = sum = n = 0;            /* get the level above the leaves */
  if (pt->type == PT_POSS)      /* note the normalization factor */
    lvl[1].total = (pt->tplcnt > 0) ? pt->tplcnt : 1;
  for (node = lvl->list; node; node = node->succ) {
    n = margfn(node, lvl);      /* marginalize the cond. distribution */
    if (n <= 0) continue;       /* skip empty distributions */
    sum += n;                   /* sum the distribution weight */
    res += n * depfn(node, lvl, measure, params);
  }                             /* check for cond. (in)dependence */
  return (sum > 0) ? res/sum : 0; /* return the evaluation result */
}  /* pt_depend() */

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

const char* pt_mname (int type, int measure)
{                               /* --- get name of evaluation measure */
  if ((measure < PT_NONE) || (measure > PT_UNKNOWN))
    measure = PT_UNKNOWN;       /* check the measure index */
  return ((type == PT_PROB) ? mi_prob : mi_poss)[measure].name;
}  /* pt_mname() */             /* return the measure name */

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

int pt_minfo (int type, int measure)
{                               /* --- get info about eval. measure */
  if ((measure < PT_NONE) || (measure > PT_UNKNOWN))
    measure = PT_UNKNOWN;       /* check the measure index */
  return ((type == PT_PROB) ? mi_prob : mi_poss)[measure].flags;
}  /* pt_minfo() */             /* return the measure information */

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

double pt_nsp (float *dist, int n)
{                               /* --- compute nonspecificity */
  double nsp  = 0;              /* nonspecificity */
  float  prec = 0;              /* preceding frequency */
  float  t;                     /* temporary buffer */

  assert(dist && (n >= 0));     /* check the function arguments */
  v_fltsort(dist, n);           /* sort the frequencies and */
  for ( ; n > 1; n--) {         /* then traverse them */
    t = *dist -prec; prec = *dist++;
    if (t > 0) nsp += t *log(n);
  }                             /* compute the nonspecificity of */
  return nsp;                   /* the distribution and return it */
}  /* pt_nsp() */

/*----------------------------------------------------------------------
The above auxiliary function is placed here, because it is needed in
ptree3.c, ptree4.c, and ptree5.c to compute the specificity measures.
----------------------------------------------------------------------*/