cluster1.c

聚类算法全集以及内附数据集

/*----------------------------------------------------------------------
  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_EXTFN

CLSET* 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_EXTFN

void cls_regx (CLSET *clset, const TUPLE *tpl)
{                               /* --- register a training tuple */