cluster.h

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

/*----------------------------------------------------------------------
  File    : cluster.h
  Contents: cluster and cluster set management
  Author  : Christian Borgelt
  History : 17.08.2001 file created
            05.09.2001 cluster size added
            11.09.2001 functions cls_range, cls_reg, cls_expand added
            08.11.2001 functions cls_center, cls_covmat etc. added
            07.08.2002 parsing function completed
            30.01.2003 data normalization variables added
            11.03.2003 weight parameter added to function cls_reg
            15.05.2003 functions combined to cls_factors and cls_limits
            15.05.2003 membership normalization modes added
            18.05.2003 cls_norm made a real function, cls_var added
            07.06.2003 function cls_scale added
            08.06.2003 parameter radius added to function cls_type
            11.08.2003 adapted to new module attmap
            12.08.2003 adapted to new module nstats
            15.08.2003 adapted to new module radfn
            27.02.2004 function cls_deletex added
            28.02.2004 size and shape regularization added
            18.03.2004 normalization parameters added
            23.04.2004 field CLUSTER.det removed (var is sufficient)
            13.07.2004 definition of CLS_UNIT added
            28.07.2004 parameter 'conly' added to function cls_update
            12.08.2004 adapted to new module parse
            18.08.2004 backpropagation functions added
----------------------------------------------------------------------*/
#ifndef __CLUSTER__
#define __CLUSTER__
#include <stdio.h>
#include "matrix.h"
#include "radfn.h"
#ifdef CLS_PARSE
#ifndef NST_PARSE
#define NST_PARSE
#endif
#endif
#include "nstats.h"
#ifdef CLS_EXTFN
#include "attmap.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
/* --- prototype flags --- */
#define CLS_CENTER       0x00   /* use cluster center (mandatory) */
#define CLS_SIZE         0x01   /* use cluster size */
#define CLS_VARS         0x02   /* use variances (independent dims.) */
#define CLS_COVARS       0x04   /* use covariance matrix */
#define CLS_WEIGHT       0x08   /* use relative cluster weight */
#define CLS_NORM         0x10   /* normalize membership function */
#define CLS_ALL          0x1f   /* all prototype flags */

/* --- initialization modes --- */
/*      CLS_CENTER          0 *//* center of the data space */
#define CLS_UNIFORM         1   /* samples from uniform distribution */
#define CLS_DIAG            2   /* diagonal of data space */
#define CLS_LATIN           3   /* latin hypercube sampling */
#define CLS_POINTS          4   /* given points in data space */
#define CLS_MODE         0x0f   /* mask for initialization method */

/* --- normalization modes --- */
#define CLS_NONE            0   /* no normalization */
#define CLS_SUM1            1   /* normalize to sum 1 */
#define CLS_MAX1            2   /* normalize to maximum 1 */
#define CLS_HARD            3   /* hard assignment (winner takes all) */

/* --- update methods --- */
#define CLS_GRADIENT        0   /* gradient descent/ascent */
#define CLS_ALTOPT          1   /* alternating optimization */
#define CLS_COMPLRN         2   /* competitive learning */
#define CLS_BACKPROP        3   /* error backpropagation */
#define CLS_METHOD       0x0f   /* mask for update method */

/* --- update modifiers --- */
/*      CLS_NONE         0x00 *//* standard update */
#define CLS_EXPAND       0x10   /* expand change by a factor */
#define CLS_MOMENTUM     0x20   /* update with momentum term */
#define CLS_ADAPTIVE     0x30   /* self-adaptive change factor */
#define CLS_RESILIENT    0x40   /* resilient update */
#define CLS_QUICK        0x50   /* quickprop analog */
#define CLS_MODIFIER     0xf0   /* mask for update modifier */

/* --- extended update modifiers --- */
#define CLS_UNIT        0x100   /* unit length center vectors */
#define CLS_ORIGIN      0x200   /* fix center vectors at origin */
#define CLS_EXTMOD      0xf00   /* mask for extended update modifier */

/* --- validity measures --- */
#define CLS_OBJFN           0   /* objective function */
#define CLS_COVERAGE        1   /* coverage of data points */
#define CLS_FDBIDX          2   /* fuzzy Davies-Bouldin index */
#define CLS_PCOEFF          3   /* partition coefficient */
#define CLS_PCNORM          4   /* normalized partition coefficient */
#define CLS_PENTROPY        5   /* partition entropy */
#define CLS_FHYPVOL         6   /* fuzzy hyper-volume */
#define CLS_PRPEXP          7   /* proportion exponent */
#define CLS_SEPDEG          8   /* separation (degree) */
#define CLS_PARTDENS        9   /* partition density */
#define CLS_PDAVG          10   /* average partition density */
#define CLS_NOISE          11   /* membership sum to noise cluster */
#define CLS_VMCNT          12   /* number of validity measures */

/* --- description modes --- */
#define CLS_TITLE      0x0001   /* print a title (as a comment) */
#define CLS_RBFNET     0x0002   /* describe as part of RBF network */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {                /* --- a cluster --- */
  double  *ctr;                 /* cluster center */
  MATRIX  *cov;                 /* covariance matrix */
  double  *dif;                 /* difference vector to center */
  MATRIX  *inv;                 /* inverse covariance matrix */
  double  *sum;                 /* weighted sum of data vectors */
  MATRIX  *smp;                 /* weighted sum of matrix products */
  double  *chc;                 /* change of center coordinates */
  MATRIX  *chv;                 /* change of (co)variances */
  double  *bfc;                 /* buffer for center gradient */
  MATRIX  *bfv;                 /* buffer for (co)variance gradient */
  double  var;                  /* equivalent isotropic variance */
  double  wgt;                  /* (relative) cluster weight */
  double  d2;                   /* squared distance of data point */
  double  msd;                  /* degree of membership of data point */
  double  scl;                  /* scaling factor for update */
  double  nw;                   /* cluster weight for update */
  double  val[4];               /* validity measure terms */
} CLUSTER;                      /* (cluster) */

typedef struct {                /* --- cluster evaluation data --- */
  int     flags;                /* flags for configured measures */
  double  rad;                  /* radius for partition density */
  double  cnt;                  /* number of processed patterns */
  double  sum;                  /* sum of membership degrees */
  double  sqr;                  /* sum of squared membership degrees */
  double  ent;                  /* entropy sum of membership degrees */
  double  pxp;                  /* proportion exponent */
  double  noise;                /* membership sum to noise cluster */
} CLSEVAL;                      /* (cluster evaluation data) */

typedef struct {                /* --- a set of clusters --- */
  int     type;                 /* type of cluster prototypes */
  int     incnt;                /* number of input attributes */
  int     clscnt;               /* number of clusters */
  CLUSTER *cls;                 /* vector of clusters */
  RADFN   *radfn;               /* radial function (Cauchy or Gauss) */
  DERIVFN *drvfn;               /* derivative of radial function */
  double  rfnps[2];             /* parameters of the radial function */
  double  norm;                 /* normalization factor (integral 1) */
  double  noise;                /* noise cluster parameter */
  double  msd[2];               /* membership degree to noise cluster */
  double  nrmps[2];             /* membership normalization params. */
  int     mode;                 /* membership normalization mode */
  int     method;               /* parameter update method + modifier */
  double  msexp;                /* membership exponent for adaptation */
  double  lrates[3];            /* learning rates */
  double  decays[3];            /* learning rate decay parameters */
  double  regps[5];             /* regularization parameters */
  double  moment;               /* momentum term */
  double  growth;               /* growth    factor */
  double  shrink;               /* shrinkage factor */
  double  minchg;               /* minimal change (resilient update) */
  double  maxchg;               /* maximal change (resilient update) */
  int     init;                 /* number of initialized clusters */
  int     steps;                /* number of update steps */
  NSTATS  *nst;                 /* normalization statistics */
  double  *vec;                 /* buffer for a data vector */
  double  *buf;                 /* buffer for eigenvalues */
  MATRIX  *mat;                 /* buffer for eigenvalue computation */
  CLSEVAL eval;                 /* cluster evaluation data */
  #ifdef CLS_EXTFN
  ATTSET  *attset;              /* underlying attribute set */
  ATTMAP  *attmap;              /* attribute map for numeric coding */
  #endif
} CLSET;                        /* (cluster set) */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/
extern CLSET*  cls_create  (int incnt, int clscnt);
extern void    cls_delete  (CLSET *clset);
#ifdef CLS_EXTFN
extern CLSET*  cls_createx (ATTSET *attset, int marked, int clscnt);
extern CLSET*  cls_cr4sup  (ATTMAP *attmap, int clscnt);
extern void    cls_deletex (CLSET *clset, int delas);
extern ATTSET* cls_attset  (CLSET *clset);
extern ATTMAP* cls_attmap  (CLSET *clset);
#endif
extern int     cls_incnt   (CLSET *clset);
extern int     cls_clscnt  (CLSET *clset);
extern NSTATS* cls_nstats  (CLSET *clset);

extern void    cls_reg     (CLSET *clset, const double *vec,
                            double weight);
extern void    cls_value   (CLSET *clset, int index, double value);
#ifdef CLS_EXTFN
extern void    cls_regx    (CLSET *clset, const TUPLE *tpl);
extern void    cls_valuex  (CLSET *clset, const TUPLE *tpl);
#endif

extern void    cls_type    (CLSET *clset, int type, double var);
extern void    cls_radfn   (CLSET *clset, RADFN radfn,
                            const double *params);
extern void    cls_derivfn (CLSET *clset, DERIVFN drvfn);
extern void    cls_norm    (CLSET *clset, int mode,
                            const double *params, double noise);
extern void    cls_init    (CLSET *clset, int mode, double range,
                            double randfn(void), const double *vec);

extern void    cls_method  (CLSET *clset, int    method);
extern void    cls_msexp   (CLSET *clset, double msexp);
extern void    cls_regular (CLSET *clset, const double *params);
extern void    cls_lrate   (CLSET *clset, const double *lrates,
                                          const double *decays);
extern void    cls_moment  (CLSET *clset, double moment);
extern void    cls_factors (CLSET *clset, double growth, double shrink);
extern void    cls_limits  (CLSET *clset, double minchg, double maxchg);
extern void    cls_reset   (CLSET *clset);

extern int     cls_exec    (CLSET *clset, const double *vec,
                            double *outs);
extern int     cls_aggr    (CLSET *clset, const double *vec,
                            double weight);
extern void    cls_bkprop  (CLSET *clset, const double *errs);
extern double  cls_update  (CLSET *clset, int conly);

extern double* cls_center  (CLSET *clset, int clid);
extern MATRIX* cls_covmat  (CLSET *clset, int clid);
extern MATRIX* cls_invmat  (CLSET *clset, int clid);
extern double  cls_isovar  (CLSET *clset, int clid);
extern double  cls_weight  (CLSET *clset, int clid);
extern double  cls_msdeg   (CLSET *clset, int clid);

extern void    cls_evcfg   (CLSET *clset, int measure, double param);
extern void    cls_evaggr  (CLSET *clset, const double *vec,
                            double weight);
extern double  cls_eval    (CLSET *clset, int measure);

extern void    cls_unscale (CLSET *clset);
extern int     cls_desc    (CLSET *clset, FILE *file,
                            int mode, int maxlen);
#ifdef CLS_PARSE
extern CLSET*  cls_parse   (SCAN *scan);
#ifdef CLS_EXTFN
extern CLSET*  cls_parsex  (SCAN *scan, ATTSET *attset, int marked);
extern CLSET*  cls_pa4sup  (SCAN *scan, ATTMAP *attmap, int hdr);
#endif
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#ifdef CLS_EXTFN
#define cls_attset(s)      ((s)->attset)
#define cls_attmap(s)      ((s)->attmap)
#endif
#define cls_incnt(s)       ((s)->incnt)
#define cls_clscnt(s)      ((s)->clscnt)
#define cls_nstats(s)      ((s)->nst)

#define cls_derivfn(s,f)   ((s)->drvfn  = (f))
#define cls_msexp(s,e)     ((s)->msexp  = (e))
#define cls_moment(s,m)    ((s)->moment = (m))
#define cls_factors(s,g,k) ((s)->growth = (g), (s)->shrink = (k))
#define cls_limits(s,a,b)  ((s)->minchg = (a), (s)->maxchg = (b))
#define cls_reset(s)       ((s)->steps  = 0)

#define cls_center(s,i)    ((s)->cls[i].ctr)
#define cls_covmat(s,i)    (((s)->type & (CLS_VARS|CLS_COVARS)) \
                           ? (s)->cls[i].cov : NULL)
#define cls_invmat(s,i)    (((s)->type & (CLS_VARS|CLS_COVARS)) \
                           ? (s)->cls[i].inv : NULL)
#define cls_isovar(s,i)    ((s)->cls[i].var)
#define cls_weight(s,i)    ((s)->cls[i].wgt)
#define cls_msdeg(s,i)     ((s)->cls[i].msd)

#endif