ptree1.c

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

/*----------------------------------------------------------------------
  File    : ptree1.c
  Contents: probability/possibility tree management
            base functions
  Author  : Christian Borgelt
  History : 22.10.1995 file created as ptree.c
            29.10.1995 function pt_conadd added
            02.11.1995 function pt_conrem added
            15.03.1996 number of levels restricted to PT_MAXCON+1
            16.04.1996 buffers for marginal distributions added
            06.05.1996 modified to sparse tree construction
            27.11.1996 type of counters changed to floating point
            28.02.1997 tree mode (PT_PROB/PT_POSS) added, redesign
            05.03.1997 automatic invalidation of aggregates added
            13.02.1998 links between nodes made possible (pt_link)
            18.02.1998 function pt_leafcnt added
            10.06.1998 semantics of function pt_down changed
            20.02.1999 adapted to structure changes, assertions added
            24.02.1999 module based on attribute set management
            25.04.1999 function pt_concopy added
            30.04.1999 some assertions added, pt_rand simplified
            20.10.1999 bug in function _aggr fixed (_aggr(lvl+1, ..))
            22.01.2002 major redesign completed
            24.02.2002 function pt_getcntx added, pt_exec redesigned
            11.03.2002 number of tuples added for poss. normalization
            10.04.2002 parameter flags of function pt_parse removed
            01.07.2002 function pt_parcnt redesigned
            03.07.2002 function pt_occur added (was a #define)
            16.07.2002 parameter 'delnodes' added to function pt_clear
            17.07.2002 bug in function pt_link fixed (lvl increment)
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include "vecops.h"
#include "ptree.h"
#ifdef STORAGE
#include "storage.h"
#endif

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

static PTNODE* _child (PTLVL *lvl, PTNODE *parent, int index)
{                               /* --- get/create a child node */
  int    s;                     /* size of created node */
  PTNODE *child;                /* retrieved/created child node */

  assert(lvl && (index >= 0));  /* check the function arguments */
  if (parent) child = parent->children[index];
  else        child = lvl->list;/* if a child already exists, */
  if (child) return child;      /* simply return it */
  if (lvl->index < 0) s = sizeof(PTLEAF) +(lvl->cnt-1) *sizeof(float);
  else                s = sizeof(PTNODE) +(lvl->cnt-1) *sizeof(PTNODE*);
  child = (PTNODE*)calloc(1,s); /* compute the size of the node, */
  if (!child) return NULL;      /* create a new node, and */
  child->parent = parent;       /* initialize its fields */
  child->index  = index;
  child->succ   = lvl->list;    /* add the new node at the head */
  lvl->list     = child;        /* of the level list */
  if (parent)                   /* store the node in the parent */
    parent->children[index] = child;
  return child;                 /* return the created node */
}  /* _child() */

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

static int _path (PTREE *pt)
{                               /* --- create path to current node */
  int   i, k;                   /* loop variable, buffer */
  PTLVL *lvl;                   /* to traverse the tree levels */

  assert(pt && !pt->curr);      /* check the function argument */
  for (lvl = pt->levels +(i = pt->pathlen); --i >= 0; )
    if ((--lvl)->node) break;   /* go up on the path to the node and */
  pt->curr = lvl->node;         /* find the deepest existing node */
  k = (pt->curr) ? (lvl++)->index : 0;
  for (i = pt->pathlen-i; --i >= 0; ) {
    pt->curr = _child(lvl, pt->curr, k);
    if (!pt->curr) return -1;   /* go to the child node, */
    k = (lvl++)->index;         /* creating it if necessary, */
  }                             /* and note the next index */
  return 0;                     /* return 'ok' */
}  /* _path() */

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

PTREE* pt_create (ATT *att, int type)
{                               /* --- create a prob./poss. tree */
  PTREE *pt;                    /* created prob./poss. tree */
  PTLVL *lvl;                   /* root level description */

  assert(att                    /* check the function argument */
     && (att_type(att) == AT_SYM));
  pt = (PTREE*)malloc(sizeof(PTREE));
  if (!pt) return NULL;         /* allocate memory and */
  pt->att     = att;            /* initialize fields */
  pt->type    = type & PT_POSS;
  pt->concnt  = pt->pathlen = 0;
  pt->fullcnt = pt->leafcnt = 1;
  pt->parcnt  = att_valcnt(att) -((pt->type & PT_POSS) ? 0 : 1);
  pt->curr    = NULL;
  pt->tplcnt  = -1;
  pt->total   = pt->lcorr = 0;
  pt->occur   = -1;
  pt->measure = PT_NONE;
  pt->eval    = 0;
  pt->buf     = NULL;
  lvl         = pt->levels;     /* get a pointer to the root level */
  lvl->att    = att;            /* and initialize the fields */
  lvl->cnt    = att_valcnt(att);
  lvl->index  = (type & PT_POSS)/* use the index for the leaf level */
              ? -2 : -1;        /* as an additional type indicator */
  lvl->list   = lvl->node = NULL;
  lvl->buf    = (float*)malloc(lvl->cnt *2 *sizeof(float));
  if (!lvl->buf) { free(pt); return NULL; }
  return pt;                    /* return the created tree */
}  /* pt_create() */

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

void pt_delete (PTREE *pt, int delatts)
{                               /* --- delete prob./poss. tree */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* to traverse the tree levels */
  PTNODE *n, *t;                /* to traverse the nodes */

  assert(pt);                   /* check the function argument */
  for (lvl = pt->levels +(i = pt->concnt +1); --i >= 0; ) {
    free((--lvl)->buf);         /* delete the buffer and */
    for (n = lvl->list; n; ) {  /* traverse the node list */
      t = n; n = n->succ; free(t); }
    if (delatts) att_delete(lvl->att);
  }                             /* delete all nodes of the tree, */
  if (pt->buf) free(pt->buf);   /* the attributes, the buffer, */
  free(pt);                     /* and the base structure */
}  /* pt_delete() */

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

void pt_clear (PTREE *pt, int delnodes)
{                               /* --- clear prob./poss. tree */
  int    i;                     /* loop variable */
  PTLVL  *lvl;                  /* to traverse the tree levels */
  PTNODE *n, *t;                /* to traverse the nodes */
  PTLEAF *leaf;                 /* to traverse the leaves */

  assert(pt);                   /* check the function argument */
  if (!pt->levels->list) return;/* if the tree is empty, abort */
  if (pt->buf) {                /* delete an evaluation buffer */
    free(pt->buf); pt->buf = NULL; }
  pt->total = 0;                /* clear the counter total */
  if (delnodes) {               /* if to delete the nodes */
    pt->curr    = NULL;         /* the current node and */
    pt->pathlen =  0;           /* the path to it are invalid */
    pt->occur   = -1;           /* occurrence flags are valid */
    pt->parcnt  =  0;           /* number of parameters is invalid */
    for (lvl = pt->levels +(i = pt->concnt +1); --i >= 0; ) {
      for (n = (--lvl)->list; n; ) {
        t = n; n = n->succ; free(t); }
      lvl->list = NULL;         /* delete all nodes of the tree and */
    } }                         /* clear the level list pointers */
  else {                        /* if only to clear the counters */
    pt->occur = 0;              /* occurrence flags are invalid */
    lvl = pt->levels +pt->concnt;
    for (leaf = (PTLEAF*)lvl->list; leaf; leaf = leaf->succ) {
      leaf->total = 0;          /* traverse the leaf nodes */
      for (i = lvl->cnt; --i >= 0; ) leaf->cnts[i] = 0;
    }                           /* clear all leaf counters */
  }                             /* (but keep the nodes) */
}  /* pt_clear() */

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

int pt_conadd (PTREE *pt, int lvlid, ATT *att)
{                               /* --- add a condition to a tree */
  int   i, k;                   /* loop variable, buffer */
  PTLVL *lvl;                   /* to traverse the tree levels */
  float *buf;                   /* buffer for new level */

  assert(pt                     /* check the function arguments */
      && (lvlid >= 0) && (lvlid <= pt->concnt)
      && att && (att_type(att) == AT_SYM));
  if (pt->concnt >= PT_MAXCON)  /* check the current tree height */
    return -2;                  /* against the maximum height */
  k   = att_valcnt(att);        /* get the number of values/children */
  buf = (float*)malloc(k *sizeof(float));
  if (!buf) return -1;          /* allocate a buffer for the level */
  pt_clear(pt, 1);              /* delete all nodes of the tree */
  for (lvl = pt->levels +(i = ++pt->concnt); --i >= lvlid; ) {
    --lvl; lvl[1] = lvl[0]; }   /* shift down the tree levels */
  lvl->cnt   = k;               /* initialize the description */
  lvl->att   = att;             /* of the inserted level */
  lvl->list  = NULL;
  lvl->index = 0;
  lvl->buf   = buf;
  return 0;                     /* return 'ok' */
}  /* pt_conadd() */

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

void pt_conrem (PTREE *pt, int lvlid, int delatt)
{                               /* --- remove a condition from a tree */
  int   i;                      /* loop variable */
  PTLVL *lvl;                   /* to traverse the tree levels */

  assert(pt && (lvlid < pt->concnt));    /* check the arguments */
  pt_clear(pt, 1);              /* delete all nodes of the tree */
  if (lvlid < 0) {              /* if to remove all conditions */
    for (lvl = pt->levels +(i = pt->concnt); --i >= 0; ) {
      free((--lvl)->buf);       /* delete the level buffer */
      if (delatt) att_delete(lvl->att);
    }                           /* delete the condition attribute */
    lvl[0] = lvl[pt->concnt];   /* move the leaf level to the root */
    pt->concnt = 0; }           /* there are no conditions anymore */
  else {                        /* if to remove only one level */
    lvl = pt->levels +lvlid;    /* get the level to remove and */
    free(lvl->buf);             /* delete buffer and attribute */
    if (delatt) att_delete(lvl->att);
    for (i = pt->concnt -lvlid; --i >= 0; lvl++)
      lvl[0] = lvl[1];          /* shift up the deeper tree levels */
    pt->concnt--;               /* there is now one condition less */