ptree5.c

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

  /* PT_INFGBAL  2 */ { _info,      MRG_LOCAL  },
  /* PT_INFGR    3 */ { _info,      MRG_LOCAL  },
  /* PT_INFSGR1  4 */ { _info,      MRG_LOCAL  },
  /* PT_INFSGR2  5 */ { _info,      MRG_LOCAL  },
  /* PT_QIGAIN   6 */ { _quad,      MRG_INDEP  },
  /* PT_QIGBAL   7 */ { _quad,      MRG_LOCAL  },
  /* PT_QIGR     8 */ { _quad,      MRG_LOCAL  },
  /* PT_QISGR1   9 */ { _quad,      MRG_LOCAL  },
  /* PT_QISGR2  10 */ { _quad,      MRG_LOCAL  },
  /* PT_GINI    11 */ { _gini1,     MRG_INDEP  },
  /* PT_GINISYM 12 */ { _gini2,     MRG_LOCAL  },
  /* PT_GINIMOD 13 */ { _gini1,     MRG_LOCAL  },
  /* PT_RELIEF  14 */ { _gini1,     MRG_LOCAL  },
  /* PT_WDIFF   15 */ { _wdiff,     MRG_INDEP  },
  /* PT_CHI2    16 */ { _chi2,      MRG_INDEP  },
  /* PT_CHI2NRM 17 */ { _chi2,      MRG_LOCAL  },
  /* PT_WOEVID  18 */ { _evid,      MRG_INDEP  },
  /* PT_RELEV   19 */ { _relev,     MRG_INDEP  },
  /* PT_BDM     20 */ { _bdm,       MRG_INDEP  },
  /* PT_BDMOD   21 */ { _bdmod,     MRG_INDEP  },
  /* PT_RDLREL  22 */ { _dlrel,     MRG_INDEP  },
  /* PT_RDLABS  23 */ { _dlabs,     MRG_INDEP  },
  /* PT_STOCO   24 */ { _stoco,     MRG_LOCAL  },
  /* PT_UNKNOWN 25 */ { (EVALFN*)0, MRG_INDEP  },
};                              /* functions for probability trees */

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

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/

static PTLEAF** _collect (PTLVL *lvl, PTNODE *node, PTLEAF **leaves)
{                               /* --- collect leaves in a subtree */
  int    i, k;                  /* loop variable */
  PTNODE *child;                /* to traverse the child nodes */

  assert(lvl && node && leaves);/* check the function arguments */
  if (lvl->index < 0) {         /* if at the leaf level */
    if (((PTLEAF*)node)->total <= 0)
      return leaves;            /* check whether leaf is mergable */
    *leaves = (PTLEAF*)node;    /* add the leaf to the vector */
    return ++leaves;            /* and return the new end */
  }                             /* of the leaf vector */
  for (k = (lvl++)->cnt, i = 0; i < k; i++) {
    child = node->children[i];  /* traverse the children */
    if (child && (child->parent == node) && (child->index == i))
      leaves = _collect(lvl, child, leaves);
  }                             /* collect the leaves recursively and */
  return leaves;                /* return the new end of the vector */
}  /* _collect() */

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

static double _local (PTREE *pt, MRGTAB *tab)
{                               /* --- do local structure learning */
  int    i, k;                  /* loop variables, leaf counter */
  PTLEAF *m1, *m2;              /* leaves to be merged */
  double curr, best, t;         /* buffers for merger evaluation */
  float  *s, *d;                /* to traverse the counters */
  int    r1, r2 = 0;            /* merge table row indices */

  assert(pt && tab);            /* check the function arguments */

  /* --- initialize the merge table --- */
  curr = pt->eval;              /* get the current evaluation */
  if (tab->evals) {             /* if merge gains are independent */
    for (i = tab->rowcnt; --i > 0; ) {
      best = -DBL_MAX;          /* traverse the table rows */
      for (k = i; --k >= 0; ) { /* traverse the preceding rows */
        tab->evalfn(pt, tab->leaves[i], tab->leaves[k]);
        tab->evals[i][k] = t = pt_reeval(pt) -curr;
        if (t >= best) { best = t; tab->bids[i] = k; }
      }                         /* note the gain that results from */
    }                           /* a merger and find the best merger */
  }                             /* in each table row */

  while (1) {                   /* leaf merge loop */

    /* --- evaluate the mergers --- */
    best = -DBL_MAX; r1 = -1;   /* initialize the best evaluation */
    if (!tab->evals) {          /* -- if there is no evaluation part */
      for (i = tab->rowcnt; --i > 0; ) {
        m1 = tab->leaves[i];    /* traverse the mergable leaves */
        if (!m1) continue;      /* (not yet merged to another) */
        for (k = i; --k >= 0; ) {
          m2 = tab->leaves[k];  /* traverse the remaining leaves and */
          if (!m2) continue;    /* evaluate the possible mergers */
          tab->evalfn(pt, m1, m2);
          t = pt_reeval(pt) -curr;
          if (t >= best) { best = t; r1 = k; r2 = i; }
        }                       /* determine the pair of leaves */
      } }                       /* that yield the best evaluation */
    else {                      /* -- if there is an evaluation part */
      for (i = tab->rowcnt; --i > 0; ) { 
        k = tab->bids[i];       /* traverse the rows of the table */
        if (k < 0) continue;    /* that contain valid mergers and */
        t = tab->evals[i][k];   /* get the best merger in the row */
        if (t >= best) { best = t; r1 = k; r2 = i; }
      }                         /* find the best leaf merger */
    }                           /* in the whole table */
    if ((r1   < 0)              /* if there is no leaf merger */
    ||  (best < tab->minimp))   /* or the best merger is not */
      break;                    /* good enough, abort the loop */
    assert(r1 < r2);            /* check the leaf indices */

    /* --- execute the best merger --- */
    m1 = tab->leaves[r1];       /* get the two leaves to be merged, */
    m2 = tab->leaves[r2];       /* check whether they are valid, and */
    assert(m1 && m2);           /* compute the new evaluation term */
    m1->eval = tab->evalfn(pt, m1, m2);
    curr     = pt_reeval(pt);   /* update the current evaluation */
    for (i = 5; --i >= 0; )     /* and copy the evaluation buffers */
      pt->res0[i] = pt->res1[i];/* from which it is computed */
    m1->pathcnt += m2->pathcnt; /* sum the paths to the leaves */
    s = m2->cnts +(i = pt->levels[pt->concnt].cnt);
    d = m1->cnts + i;           /* merge the counters of the leaves */
    if (pt->type & PT_POSS) {   /* in poss. mode by taking the maximum */
      while (--i >= 0) { if (*--s > *--d) *d = *s; }
      if (m2->total > m1->total) m1->total = m2->total; }
    else {                      /* in prob. mode merge by summing */
      while (--i >= 0) *--d += *--s;
      m1->total += m2->total;   /* merge also the leaf totals */
    }
    m2->total   = 0;            /* mark the source leaf as merged */
    m2->pathcnt = 0;            /* (it cannot be deleted immediately) */
    m2->parent  = (PTNODE*)m1;  /* and note the destination leaf */
    if (--tab->leafcnt <= 2)    /* decrement the leaf counter and */
      break;                    /* abort if there are only two leaves */

    /* --- update the merge table --- */
    tab->leaves[r2] = NULL;     /* invalidate the second leaf */
    if (!tab->evals) continue;  /* check for a leaf merge table */
    tab->bids[r2] = -1;         /* invalidate the indices of */
    tab->bids[r1] = -1;         /* the best leaf mergers */
    for (best = -DBL_MAX, k = r1; --k >= 0; ) {
      if (!tab->leaves[k])      /* traverse the unmerged leaves */
        continue;               /* in the first leaf's row */
      tab->evalfn(pt, m1, tab->leaves[k]);
      tab->evals[r1][k] = t = pt_reeval(pt) -curr;
      if (t >= best) { best = t; tab->bids[r1] = k; }
    }                           /* update the merger evaluations */
    for (i = tab->rowcnt; --i > r1; ) {
      if (!tab->leaves[i])      /* traverse the following rows */
        continue;               /* that contain unmerged leaves */
      tab->evalfn(pt, m1, tab->leaves[i]);
      tab->evals[i][r1] = t = pt_reeval(pt) -curr;
      k = tab->bids[i];         /* reevaluate mergers with first leaf */
      if ((k != r1) && (k != r2)        /* check whether a search */
      &&  (t > tab->evals[i][k])) {     /* for the index of the */
        tab->bids[i] = r1; continue; }  /* best merger is necessary */
      for (best = -DBL_MAX, k = i; --k >= 0; ) {
        if (!tab->leaves[k]) continue;
        t = tab->evals[i][k];   /* traverse the unmerged leaves */
        if (t >= best) { best = t; tab->bids[i] = k; }
      }                         /* find the best merger among */
    }                           /* those represented in this row */

  }  /* while (1) */

  return pt->eval = curr;       /* return the current evaluation */
}  /* _local() */

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

double pt_local (PTREE *pt, int lwise, double minimp)
{                               /* --- do local structure learning */
  int    i, k, n = 0;           /* loop variables, leaf counter */
  PTLVL  *lvl;                  /* leaf level description */
  PTLEAF *leaf, *dest, **p;     /* to traverse the leaves */
  PTNODE *node;                 /* to traverse the nodes one level up */
  double *e;                    /* to organize the merge table */
  FTE    *fte;                  /* function table element */
  MRGTAB *tab;                  /* leaf merge table */

  assert(pt);                   /* check the function arguments */
  if ((pt->concnt <= 0)         /* if there are no conditions */
  ||  (pt->total  <= 0))        /* or all counters are zero, */
    return pt->eval;            /* return the existing evaluation */

  /* --- create a merge table --- */
  lvl = pt->levels +pt->concnt; /* traverse the leaf level */
  for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ)
    if (leaf->total > 0) n++;   /* count the mergable leaves */
  if (n <= 2) return pt->eval;  /* there must be more than two leaves */
  tab = (MRGTAB*)malloc(sizeof(MRGTAB) +(n-1) *sizeof(PTLEAF*));
  if (!tab) return PT_ERROR;    /* create a leaf merge table */
  tab->leafcnt = n;             /* and initialize it */
  tab->minimp  = minimp;
  fte = ((pt->type == PT_PROB) ? fn_prob : fn_poss) +pt->measure;
  if (!fte->evalfn) return PT_ERROR;
  tab->evalfn = fte->evalfn;    /* get the evaluation function */
  if (fte->type != MRG_INDEP)   /* if merge gains are dependent */
    tab->evals = NULL;          /* do not create table elements */
  else {                        /* if merge gains are independent */
    tab->bids  = (int*)malloc(n *sizeof(int));
    if (!tab->bids) { free(tab); }
    tab->evals = (double**)malloc(n *sizeof(double*));
    if (!tab->evals) { free(tab->bids); free(tab); }
    e = (double*)malloc((n *(n-1)) /2 *sizeof(double));
    if (!e) { free(tab->evals); free(tab->bids); free(tab); }
    for (i = 0; i < n; i++) { tab->evals[i] = e; e += i; }
  }                             /* create evaluation part of table */

  /* --- do local structure learning --- */
  i   = (lwise > 0) ? pt->concnt +1 : 1;
  lvl = pt->levels +i;          /* get the number of levels and */
  while (--i >= 0) {            /* traverse the tree levels */
    for (node = (--lvl)->list; node; node = node->succ) {
      tab->rowcnt = _collect(lvl, lvl->list, tab->leaves) -tab->leaves;
      _local(pt, tab);          /* collect all mergable leaves */
    }                           /* and do local structure learning */
  }                             /* on each tree level */

  /* --- delete the merge table --- */
  if (tab->evals) {             /* delete the evaluation entries */
    free(tab->bids); free(tab->evals[0]); free(tab->evals); }
  free(tab);                    /* delete the leaf merge table */

  /* --- finalize the mergers --- */
  lvl = pt->levels +pt->concnt; /* traverse the leaf level */
  for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ) {
    if (leaf->pathcnt > 0) continue; /* traverse the merged leaves */
    dest = (PTLEAF*)leaf->parent;    /* follow references to dests. */
    while (dest->pathcnt <= 0) dest = (PTLEAF*)dest->parent;
    leaf->parent = (PTNODE*)dest;    /* find the final destination */
  }                                  /* and set the reference to it */
  k = (lvl-1)->cnt;             /* traverse level above the leaves */
  for (node = (lvl-1)->list; node; node = node->succ) {
    for (p = (PTLEAF**)node->children +(i = k); --i >= 0; ) {
      if (!*--p) continue;      /* traverse the children of each node */
      if ((*p)->pathcnt <= 0) *p = (PTLEAF*)(*p)->parent;
    }                           /* if a child has been merged, */
  }                             /* set the link to the destination */
  for (p = (PTLEAF**)&lvl->list; *p; ) {
    leaf = *p;                  /* traverse the leaf nodes again */
    if (leaf->pathcnt > 0)      /* if a leaf has not been merged, */
      p = (PTLEAF**)&leaf->succ;/* just go to the next leaf */
    else {                      /* if a leaf has been merged */
      *p = (PTLEAF*)leaf->succ; free(leaf); }
  }                             /* delete the leaf */
  return pt_eval(pt, pt->measure, pt->params);
}  /* pt_local() */             /* return the new tree evaluation */