/*----------------------------------------------------------------------  File    : cluster1.c  Contents: cluster and cluster set management (basic functions)  Author  : Christian Borgelt  History : 05.09.2001 file created            11.09.2001 functions cls_range, cls_reg, cls_expand added            15.09.2001 first version of fuzzy c-means completed            07.08.2002 parsing function completed            30.01.2003 data normalization code added            01.02.2003 extended functions (for tuples) added            02.02.2003 extended parse function added            07.02.2003 reinitialization added to function cls_range            09.03.2003 some initialization moved to separate routines            13.03.2003 membership degree normalization made optional            10.04.2003 matrix initialization bug in _params fixed            15.05.2003 membership normalization modes added            16.05.2003 noise clustering added            06.08.2003 bug in mapping binary attributes fixed            11.08.2003 adapted to new module attmap            12.08.2003 adapted to new module nstats            14.08.2003 bug in _params fixed (covariance matrix reading)            15.08.2003 adapted to new module radfn            16.02.2004 bug in _params for vector of variances fixed            23.02.2004 bug in function _params fixed            25.02.2004 adapted to changed radfn, bug in cls_exec fixed            27.02.2004 function cls_deletex added            01.03.2004 update functions moved to a separate file            17.03.2004 missing evaluation of cluster weight added            18.03.2004 normalization parameters added            25.04.2004 bug in function cls_unscale fixed            21.06.2004 reading covariances made more robust            28.07.2004 bug in function _params (cls_parse) fixed            12.08.2004 adapted to new module parse----------------------------------------------------------------------*/#include <stdlib.h>#include <limits.h>#include <float.h>#include <string.h>#include <assert.h>#include "cluster.h"/*----------------------------------------------------------------------  Preprocessor Definitions----------------------------------------------------------------------*/#define BLKSIZE      16         /* block size for cluster vector */#define MINVAR       1e-12      /* minimal variance */#define MAXVAR       1e+12      /* maximal variance */#define MINDET       1e-48      /* minimal determinant */#define MAXDET       1e+48      /* maximal determinant *//*----------------------------------------------------------------------  Constants----------------------------------------------------------------------*/static char *nrmnames[] =       /* names of normalization modes */  { "none", "sum1", "max1", "hard" };/*----------------------------------------------------------------------  Auxiliary Functions----------------------------------------------------------------------*/static void _init (CLSET *clset, int incnt, int clscnt){                               /* --- initialize some variables */  clset->type     = CLS_CENTER; /* prototypes consist of centers only */  clset->incnt    = incnt;  clset->clscnt   = clscnt;  clset->radfn    = rf_cauchy;  /* default radial function: */  clset->rfnps[0] = 2;          /* \mu(x) = 1/d^2(\vec{x},\vec{c}) */  clset->rfnps[1] = 0;          /* (standard fuzzy clustering) */  clset->norm     = rf_cauchy(-incnt, clset->rfnps);  clset->noise    = clset->msd[0] = clset->msd[1] = 0;  clset->nrmps[0] = 1;          /* default normalization: */  clset->nrmps[1] = 0;          /* u_ij = u_ij^* /sum_k u_{kj}^* */  clset->mode     = CLS_SUM1;  clset->method   = CLS_ALTOPT|CLS_NONE;  clset->msexp    = 2;          /* exponent: std. fuzzy clustering */  clset->regps[0] = 0;          /* regularization parameters */  clset->regps[1] = 1;          /* (b, a, s, h, w) */  clset->regps[2] = 1;  clset->regps[3] = 0;  clset->regps[4] = 0;  clset->moment   = 0;  clset->growth   = 1.2;  clset->shrink   = 0.5;  clset->maxchg   = 1;  clset->cls      = NULL;       /* initialize pointers, */  clset->vec      = NULL;       /* so that deletion */  clset->mat      = NULL;       /* with cls_delete works */  clset->nst      = NULL;  clset->init     = clset->steps = 0;}  /* _init() *//*--------------------------------------------------------------------*/static int _cluster (CLUSTER *c, int dim){                               /* --- init. a cluster prototype */  c->cov = mat_create(dim, dim);  c->inv = mat_create(dim, dim);  c->smp = mat_create(dim, dim);  c->chv = mat_create(dim, dim);  c->bfv = mat_create(dim, dim);  if (!c->cov || !c->inv || !c->smp || !c->chv || !c->bfv)    return -1;                  /* create cluster-specific matrices */  c->ctr = mat_buf(c->cov);     /* and get their buffer vectors */  c->dif = mat_buf(c->inv);     /* for easier access */  c->sum = mat_buf(c->smp);  c->chc = mat_buf(c->chv);  c->bfc = mat_buf(c->bfv);  c->var = c->wgt = c->scl = 1;  return 0;                     /* return 'ok' */}  /* _cluster() *//*----------------------------------------------------------------------  Cluster Set Functions----------------------------------------------------------------------*/CLSET* cls_create (int incnt, int clscnt){                               /* --- create a set of clusters */  int     i;                    /* loop variable */  CLSET   *clset;               /* created set of clusters */  CLUSTER *c;                   /* to traverse the clusters */  assert((incnt > 0) && (clscnt > 0));/* check the function arguments */  clset = (CLSET*)malloc(sizeof(CLSET));  if (!clset) return NULL;      /* create the base structure */  _init(clset, incnt, clscnt);  /* and initialize the variables */  clset->cls = c = (CLUSTER*)malloc(clscnt *sizeof(CLUSTER));  if (!clset->cls) { cls_delete(clset); return NULL; }  for (c += i = clscnt; --i >= 0; ) { /* clear pointers for cleanup */    --c; c->cov = c->inv = c->smp = c->chv = c->bfv = NULL; }  for (c += i = clscnt; --i >= 0; )   /* initialize the clusters */    if (_cluster(--c, incnt) != 0) { cls_delete(clset); return NULL; }  clset->vec = (double*)malloc(3 *incnt *sizeof(double));  if (!clset->vec) { cls_delete(clset); return NULL; }  clset->buf = clset->vec +incnt;  /* create the numeric vectors */  clset->mat = mat_create(incnt, incnt);  clset->nst = nst_create(incnt);  /* create the numerical statistics */  if (!clset->mat || !clset->nst) { cls_delete(clset); return NULL; }  #ifdef CLS_EXTFN              /* if extended function set, */  clset->attset = NULL;         /* clear the attribute set and */  clset->attmap = NULL;         /* attribute map pointers as a flag */  #endif                        /* for a normal cluster set */  return clset;                 /* return created set of clusters */}  /* cls_create() *//*--------------------------------------------------------------------*/void cls_delete (CLSET *clset){                               /* --- delete a set of clusters */  int     i;                    /* loop variable */  CLUSTER *c;                   /* to traverse the clusters */  assert(clset);                /* check the function argument */  #ifdef CLS_EXTFN              /* if to compile extended functions, */  if (clset->attmap) free(clset->attmap);     /* delete the att. map */  #endif  if (clset->nst) nst_delete(clset->nst);  if (clset->mat) mat_delete(clset->mat);  if (clset->vec) free(clset->vec);  if (clset->cls) {             /* if there is a cluster vector */    for (c = clset->cls +(i = clset->clscnt); --i >= 0; ) {      --c;                      /* traverse the clusters */      if (c->cov) mat_delete(c->cov);      if (c->inv) mat_delete(c->inv);      if (c->smp) mat_delete(c->smp);      if (c->chv) mat_delete(c->chv);      if (c->bfv) mat_delete(c->bfv);    }                           /* delete all matrices */    free(clset->cls);           /* and the cluster vector */  }  free(clset);                  /* delete the base structure */}  /* cls_delete() *//*--------------------------------------------------------------------*/#ifdef CLS_EXTFNCLSET* cls_createx (ATTSET *attset, int marked, int clscnt){                               /* --- create a cluster set */  CLSET  *clset;                /* created cluster set */  ATTMAP *attmap;               /* created attribute map */  assert(attset && (clscnt > 0));  /* check the function arguments */  attmap = am_create(attset, marked, -1);  if (!attmap) return NULL;     /* create an attribute map */  clset  = cls_create(am_incnt(attmap), clscnt);  if (!clset) { am_delete(attmap); return NULL; }  clset->attset = attset;       /* create a cluster set and */  clset->attmap = attmap;       /* note the attribute set and map */  return clset;                 /* return the created cluster set */}  /* cls_cr4sup() *//*--------------------------------------------------------------------*/CLSET* cls_cr4sup (ATTMAP *attmap, int clscnt){                               /* --- create a cluster set */  CLSET *clset;                 /* created cluster set */  assert(attmap && (clscnt > 0));  /* check the function arguments */  clset  = cls_create(am_incnt(attmap), clscnt);  if (!clset) return NULL;      /* create a cluster set */  clset->attset = am_attset(attmap);  clset->attmap = attmap;       /* note the attribute set and map */  return clset;                 /* return the created cluster set */}  /* cls_cr4sup() *//*--------------------------------------------------------------------*/void cls_deletex (CLSET *clset, int delas){                               /* --- delete a set of clusters */  if (delas) as_delete(clset->attset);  cls_delete(clset);            /* delete attribute set */}  /* cls_deletex() */          /* and cluster set */#endif/*--------------------------------------------------------------------*/void cls_reg (CLSET *clset, const double *vec, double weight){                               /* --- register a data point */  #ifdef CLS_EXTFN              /* if to compile extended functions */  int i, k, off;                /* loop variables, offset */  #endif  assert(clset);                /* check the function argument */  nst_reg(clset->nst, vec, weight);  #ifdef CLS_EXTFN              /* if to compile extended functions */  if (vec || !clset->attmap)    /* if not termination or normal */    return;                     /* clustering, abort the function */  for (i = am_attcnt(clset->attmap); --i >= 0; ) {    if (am_type(clset->attmap, i) < 0) continue;    off = am_off(clset->attmap, i);    k   = am_cnt(clset->attmap, i) +off;    while (--k >= off) nst_scale(clset->nst, k, 0, 1);  }                             /* set identity for symbolic attribs. */  #endif                        /* (prevent distortion by scaling) */}  /* cls_reg() *//*--------------------------------------------------------------------*/void cls_value (CLSET *clset, int index, double value){                               /* --- set an input value */  clset->vec[index] = (value -nst_offset(clset->nst, index))                             *nst_factor(clset->nst, index);}  /* cls_value() *//*--------------------------------------------------------------------*/#ifdef CLS_EXTFNvoid cls_regx (CLSET *clset, const TUPLE *tpl){                               /* --- register a training tuple */