clc.c

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

/*----------------------------------------------------------------------
  File    : clc.c
  Contents: probabilistic and fuzzy cluster comparison
  Author  : Christian Borgelt
  History : 28.05.2006 file created from file cle.c
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#ifdef MATVERSION
#ifndef MAT_READ
#define MAT_READ
#endif
#else   /* #ifdef MATVERSION */
#ifndef AS_RDWR
#define AS_RDWR
#endif
#ifndef AS_PARSE
#define AS_PARSE
#endif
#include "io.h"
#endif /* #ifdef MATVERSION */
#ifndef CLS_PARSE
#define CLS_PARSE
#endif
#ifndef CLS_EXTFN
#define CLS_EXTFN
#endif
#include "cluster.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define PRGNAME     "clc"
#define DESCRIPTION "probabilistic and fuzzy cluster comparison"
#define VERSION     "version 1.0 (2006.01.31)         " \
                    "(c) 2006   Christian Borgelt"

#define BLKSIZE     256         /* block size for column vectors */

/* --- conjunction functions --- */
#define PM_MIN        0         /* minimum */
#define PM_MINNP      1         /* nil-potent minimum */
#define PM_PROD       2         /* product */
#define PM_LUKA       3         /* Lukasiewicz */
#define PM_CFCNT      4         /* number of functions */

/* --- evaluation measures --- */
#define PM_DIFF       0         /* sum of squared differences */
#define PM_ACC        1         /* cross-classification accuracy */
#define PM_F1         2         /* F1 measure */
#define PM_RAND       3         /* Rand statistic */
#define PM_JACCARD    4         /* Jaccard coefficient */
#define PM_FOLKES     5         /* Folkes-Mallows index */
#define PM_HUBERT     6         /* Hubert index */

/* --- error codes --- */
#define OK            0         /* no error */
#define E_NONE        0         /* no error */
#define E_NOMEM     (-1)        /* not enough memory */
#define E_FOPEN     (-2)        /* file open failed */
#define E_FREAD     (-3)        /* file read failed */
#define E_FWRITE    (-4)        /* file write failed */
#define E_OPTION    (-5)        /* unknown option */
#define E_OPTARG    (-6)        /* missing option argument */
#define E_ARGCNT    (-7)        /* wrong number of arguments */
#define E_STDIN     (-8)        /* double assignment of stdin */
#define E_CONJFN    (-9)        /* unknown conjunction function */
#define E_PARSE    (-10)        /* parse errors on input file */
#define E_PATCNT   (-11)        /* no pattern found */
#define E_PATSIZE  (-12)        /* illegal pattern size */
#define E_DIFFCNT  (-13)        /* numbers of clusters differ */
#define E_UNKNOWN  (-18)        /* unknown error */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {                /* --- a partition matrix --- */
  int    rowcnt;                /* number of rows (clusters) */
  int    colcnt;                /* (current) number of columns */
  int    colvsz;                /* size of the column vectors */
  double *rows[1];              /* vector of rows */
} PARTMAT;                      /* (partition matrix) */

typedef struct {                /* --- mode information --- */
  int  code;                    /* code of mode */
  char *name;                   /* name of mode */
  char *desc;                   /* description */
} MODEINFO;                     /* (mode information) */

typedef double CONJFN (double a, double b);

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
static const char *errmsgs[] = {   /* error messages */
  /* E_NONE      0 */  "no error\n",
  /* E_NOMEM    -1 */  "not enough memory\n",
  /* E_FOPEN    -2 */  "cannot open file %s\n",
  /* E_FREAD    -3 */  "read error on file %s\n",
  /* E_FWRITE   -4 */  "write error on file %s\n",
  /* E_OPTION   -5 */  "unknown option -%c\n",
  /* E_OPTARG   -6 */  "missing option argument\n",
  /* E_ARGCNT   -7 */  "wrong number of arguments\n",
  /* E_STDIN    -8 */  "double assignment of standard input\n",
  /* E_PARSE    -9 */  "unknown conjunction %s\n",
  /* E_PARSE   -10 */  "parse error(s) on file %s\n",
  /* E_PATCNT  -11 */  "no pattern in file %s\n",
  /* E_PATSIZE -12 */  "illegal pattern size %d\n",
  /* E_DIFFCNT -13 */  "number of clusters differ (%d vs. %d)\n",
  /*    -13 to -15 */  NULL, NULL,
  /* E_VALUE   -16 */  "file %s, record %d: "
                         "illegal value %s in field %d\n",
  /* E_FLDCNT  -17 */  "file %s, record %d: "
                         "%s%d field(s) instead of %d\n",
  /* E_UNKNOWN -18 */  "unknown error\n",
};

static const MODEINFO conjtab[] = { /* table of conjunction functions */
  { PM_MIN,   "min",   "minimum"             },
  { PM_MINNP, "minnp", "nilpotent minimum"   },
  { PM_PROD,  "prod",  "product"             },
  { PM_LUKA,  "luka",  "Lukasiewicz t-norm"  },
  { -1,       NULL,    NULL   /* sentinel */ },
};

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
const  char    *prgname = NULL; /* program name for error messages */
static SCAN    *scan    = NULL; /* scanner for cluster set desc. */
static CLSET   *clset1  = NULL; /* first  cluster set */
static CLSET   *clset2  = NULL; /* second cluster set */
static PARTMAT *pmat1   = NULL; /* first  partition matrix */
static PARTMAT *pmat2   = NULL; /* second partition matrix */
static FILE    *in      = NULL; /* input  file */
#ifdef MATVERSION
static TFSCAN  *tfscan  = NULL; /* table file scanner */
#else
static ATTSET  *attset  = NULL; /* attribute set */
#endif

/*----------------------------------------------------------------------
  Conjunction Functions (t-norms)
----------------------------------------------------------------------*/

static double _min (double a, double b)
{ return (a <= b) ? a : b; }

static double _minnp (double a, double b)
{ return (a+b < 1) ? 0 : ((a <= b) ? a : b); }

static double _prod (double a, double b)
{ return a * b; }

static double _luka (double a, double b)
{ double t = a +b -1; return (t >= 0) ? t : 0; }

static CONJFN *cftab[] = {
  _min, _minnp, _prod, _luka, };

/*----------------------------------------------------------------------
  Partition Matrix Functions
----------------------------------------------------------------------*/

static PARTMAT* pm_create (int clscnt)
{                               /* --- create a partition matrix */
  PARTMAT *pm;                  /* created partition matrix */

  pm = (PARTMAT*)malloc(sizeof(PARTMAT) +clscnt *sizeof(double*));
  if (!pm) return NULL;         /* create the base structure */
  pm->rowcnt = clscnt;          /* store the number of rows */
  pm->colcnt = pm->colvsz = 0;  /* clear the column counter */
  while (--clscnt >= 0)         /* clear the column vectors */
    pm->rows[clscnt] = NULL;    /* (will be allocated when needed) */
  return pm;                    /* return the created matrix */
}  /* pm_create() */

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

static int pm_addcol (PARTMAT *pm, CLSET *clset)
{                               /* --- add current assig. to matrix */
  int    i, vsz;                /* loop variable, new vector size */
  double *row;                  /* buffer for (re)allocation */

  assert(pm->rowcnt == cls_clscnt(clset));
  vsz = pm->colvsz;             /* get the size of the column vectors */
  if (pm->colcnt >= vsz) {      /* if the column vectors are full */
    vsz += (vsz > BLKSIZE) ? vsz >> 1 : BLKSIZE;
    for (i = pm->rowcnt; --i >= 0; ) {
      row = (double*)realloc(pm->rows[i], vsz *sizeof(double));
      if (!row) return -1;      /* enlarge a column vector and */
      pm->rows[i] = row;        /* on success set the new vector */
    } pm->colvsz = vsz;         /* store the new vector size */
  }                             /* (only after full success) */
  for (i = pm->rowcnt; --i >= 0; )
    pm->rows[i][pm->colcnt] = cls_msdeg(clset, i);
  return pm->colcnt++;          /* store the membership degrees */
}  /* pm_addcol() */            /* and return the column index */

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

static double permute (int n, int k, int *map, double **cmp)
{                               /* --- test all column permutations */
  int    i;                     /* loop variable */
  int    t;                     /* exchange buffer */
  double e, max;                /* (maximal) evaluation */

  if      (k <= 1) {            /* if a new permutation is created */
    for (e = 0, i = n; --i >= 0; )
      e += cmp[i][map[i]];      /* sum the entries of the matrix */
    return e; }                 /* selected by the permutation */
  else if (k >= n) {            /* if in first call (initialization) */
    for (i = n; --i >= 0; )     /* set the identity mapping */
      map[i] = i;               /* as the first permutation and */
  }                             /* start with this initial ordering */
  max = permute(n, --k, map, cmp);
  for (i = k; --i >= 0; ) {     /* traverse preceding elements */
    t = map[i]; map[i] = map[k]; map[k] = t;
    e = permute(n, k, map,cmp); /* swap element to current spot, */