ptree2.c

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

/*----------------------------------------------------------------------
  File    : ptree2.c
  Contents: probability/possibility tree management
            description and parsing functions
  Author  : Christian Borgelt
  History : 22.10.1995 file created as ptree.c
            06.05.1996 modified to sparse tree construction
            27.11.1996 type of counters changed to floating point
            28.02.1997 tree type (PT_PROB/PT_POSS) added, redesign
            20.02.1999 adapted to structure changes, assertions added
            24.02.1999 module based on attribute set management
            05.04.1999 network output changed to absolute frequencies
            26.05.2001 adapted to changed module scan
            11.10.2001 adapted to changed module scan
            01.11.2001 parse error recovery corrected/improved
            20.01.2002 major redesign completed
            05.03.2002 output of additional information added
            08.07.2002 bug in function linkout (~PT_OCCUR) fixed
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include "ptree.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {                /* --- tree output information --- */
  FILE   *file;                 /* output file */
  int    mode;                  /* description mode, e.g. PT_FULL */
  float  total;                 /* global total of counters */
  float  lcorr;                 /* Laplace correction */
  char   *base;                 /* string for base indentation */
  int    ind;                   /* indentation (in characters) */
  int    pos;                   /* position in output line */
  int    max;                   /* maximal output line length */
  char   buf[4*AS_MAXLEN+68];   /* output buffer */
} PTOUT;                        /* (tree output information) */

/*----------------------------------------------------------------------
  Description Functions
----------------------------------------------------------------------*/

static void _indent (PTOUT *out, int newline)
{                               /* --- indent output line */
  int i;                        /* loop variable */

  assert(out);                  /* check the function argument */
  if (newline) {                /* terminate line */
    fputc('\n', out->file); fputs(out->base, out->file); out->pos = 0; }
  for (i = out->pos; i < out->ind; i++)
    fputc(' ',  out->file);     /* indent next line */
  if (out->ind > out->pos) out->pos = out->ind;
}  /* _indent() */              /* note new position */

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

static void _distout (PTOUT *out, PTLVL *lvl, PTLEAF *leaf)
{                               /* -- print prob./poss. distribution */
  int   i;                      /* loop variable */
  int   len;                    /* length of a value name */
  float frq, norm;              /* frequency and normalization factor */

  assert(out && lvl);           /* check the function arguments */
  if (out->total >= 0)          /* for a possibility tree */
    norm = out->total;          /* use the global total */
  else {                        /* for a probability tree */
    norm = lvl->cnt *out->lcorr;/* get a node specific total */
    if (leaf) norm += leaf->total;
  }                             /* compute the normalization factor */
  norm = (norm > 0) ? 100/norm : 1;
  for (i = 0; i < lvl->cnt; i++) { /* traverse the values */
    if (i > 0) {                /* print a separator if necessary */
      fputc(',', out->file); out->pos++; }
    len  = sc_format(out->buf, att_valname(lvl->att, i), 0);
    frq  = (leaf) ? leaf->cnts[i] : 0; /* format the value name */
    len += sprintf(out->buf +len, ": %g", frq);
    if (out->mode & PT_REL) {   /* add the absolute frequency */
      frq = (frq +out->lcorr) *norm;
      len += sprintf(out->buf +len, " (%.1f%%)", frq);
    }                           /* add the relative frequency */
    if ((out->pos +len > out->max -4)   /* if the current line */
    &&  (out->pos      > out->ind))     /* would get too long, */
      _indent(out, 1);          /* start a new line and indent */
    else if (i > 0) {           /* otherwise only print a blank */
      fputc(' ', out->file ); out->pos++; }
    fputs(out->buf, out->file); /* print the value information */
    out->pos += len;            /* update the output position */
  }
  fputc(' ', out->file);        /* add a blank at the end and */
  out->pos++;                   /* update the output position */
}  /* _distout() */

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

static void _linkout (PTOUT *out, PTLVL *lvl, PTNODE *node)
{                               /* --- print a link to another node */
  int i;                        /* loop variable */
  int len;                      /* length of a value name */

  assert(out && lvl && node);   /* check the function arguments */
  fputs("->(", out->file);      /* start a link to another node */
  out->pos = out->ind += 3;     /* and update the output position */
  for (i = 0; node->parent; i++) {
    (--lvl)->link = node->index & ~PT_OCCUR;
    node = node->parent;        /* climb up in the tree and */
  }                             /* build a path to the linked node */
  for (len = -1; --i >= 0; lvl++) {  /* traverse the path */
    if (len >= 0) {             /* print a separator if necessary */
      fputc(',', out->file); out->pos++; }
    len = sc_format(out->buf, att_valname(lvl->att, lvl->link), 0);
    if ((out->pos +len > out->max -4)   /* if the current line */
    &&  (out->pos      > out->ind))     /* would get too long, */
      _indent(out, 1);          /* start a new line and indent */
    fputs(out->buf, out->file); /* print the value name and */
    out->pos += len;            /* update the output position */
  }
  fputc(')', out->file);        /* terminate the link and */
  out->pos += 1; out->ind -= 3; /* update the output position */
}  /* _linkout() */

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

static void _treeout (PTOUT *out, PTLVL *lvl, PTNODE *node)
{                               /* -- recursive output of tree */
  int    i;                     /* loop variable */
  PTNODE *child;                /* to traverse the children */
  int    len;                   /* length of a value name */
  int    wd;                    /* width of attribute values */

  assert(out && lvl);           /* check the function arguments */
  fputs("{ ", out->file);       /* start a tree branch/distribution */
  out->pos = out->ind += 2;     /* and update the output position */
  if (lvl->index < 0) {         /* if the node is on the leaf level */
    if (node || (out->mode & PT_FULL))
      _distout(out, lvl, (PTLEAF*)node); }
  else {                        /* if the node is an inner node */
    wd = att_valwd(lvl->att,1); /* get the value width for indenting */
    for (len = -1, i = 0; i < lvl->cnt; i++) {
      child = (node) ? node->children[i] : NULL;
      if (!(out->mode & PT_FULL)/* if not to show a full tree */
      &&  (!child               /* and the subtree is empty */
      ||  !(child->index & PT_OCCUR)))
        continue;               /* ignore the current child */
      if (len >= 0) {           /* print a separator if necessary */
        fputc(',', out->file); _indent(out, 1); }
      len = sc_format(out->buf, att_valname(lvl->att, i), 0);
      fputs(out->buf,out->file);/* print the name of the value */
      out->pos += len; out->ind += wd;
      _indent(out, 0);          /* update output position and indent */
      fputc(':', out->file); out->pos++; out->ind++;
      if (child                 /* if the child reference is a link */
      && ((child->parent != node) || ((child->index & ~PT_OCCUR) != i)))
        _linkout(out, lvl+1, child); /* print the link description */
      else                      /* if the child reference is genuine */
        _treeout(out, lvl+1, child); /* print the subtree */
      out->ind -= wd +1;        /* recursively print the subtree */
    }                           /* and reset the indentation */
    if ((out->pos >= out->max)  /* if the line would get too long */
    || ((out->ind <= 0) && (out->pos >= out->max -1)))
      _indent(out, 1);          /* start a new line */
  }
  fputc('}', out->file);        /* terminate the tree branch and */
  out->pos++; out->ind -= 2;    /* update the output position */
}  /* _treeout() */

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

int pt_desc (PTREE *pt, FILE *file, int mode, int maxlen)
{                               /* --- describe a prob./poss. tree */
  int    i, k;                  /* loop variables */
  PTLVL  *lvl;                  /* to traverse the tree levels */
  PTNODE *root;                 /* the root node of the tree */
  PTOUT  out;                   /* tree output information */
  int    len;                   /* length of attribute name */

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

  /* --- print header (as a comment) --- */
  if (mode & PT_TITLE) {        /* if the title flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("/*", file); while (--i >= 0) putc('-', file);
    fprintf(file, (pt->type == PT_PROB) ? "\n  probability tree\n"
                                        : "\n  possibility tree\n");
    while (--k >= 0) putc('-', file); fputs("*/\n", file);
  }                             /* print a title header */

  /* --- initialize --- */
  out.file  = file;             /* note the output file, the desc. */
  out.mode  = mode;             /* mode, and the output line length */
  out.max   = (maxlen <= 0) ? INT_MAX : maxlen;
  out.lcorr = pt->lcorr;        /* note the Laplace correction and */
  if (pt->lcorr > 0) out.mode |= PT_FULL;/* set the full tree flag */
  pt_occur(pt);                 /* compute totals and set occ. flags */
  out.total = (pt->type == PT_PROB)
            ? -1 : pt->total +out.lcorr +FLT_MIN;
  out.base  = (mode & PT_INDENT) ? "  " : "";

  /* --- print attribute list --- */
  fputs(out.base, file);        /* indent the line */
  fputs((pt->type == PT_PROB) ? "prob(" : "poss(", file);
  out.pos = out.ind = 5;        /* start the condition tree output */
  i   = pt->concnt;             /* get the number of conditions */
  lvl = pt->levels;             /* and the tree level descriptions */
  len = sc_format(out.buf, att_name(lvl[i].att), 0);
  fputs(out.buf, file);         /* print the attribute name */
  out.pos = out.ind += len;     /* and the condition indicator */
  if (i > 0) { fputc('|', file); out.pos = ++out.ind; }
  for (len = -1; --i >= 0; lvl++) { /* traverse the conditions */
    if (len >= 0) {             /* print a separator if necessary */
      fputc(',', file); out.pos++; }
    len = sc_format(out.buf, att_name(lvl->att), 0);
    if ((out.pos +len > out.max -3)     /* if the current line */
    &&  (out.pos      > out.ind))       /* would get too long, */
      _indent(&out, 1);         /* start a new line and indent */
    fputs(out.buf, file);       /* print the name of the condition */
    out.pos += len;             /* compute the new output position */
  }
  fputs(") =", file);           /* terminate the attribute list */