clc.c

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

    if (e > max) max = e;       /* evaluate permutations recursively, */
    map[k] = map[i]; map[i] = t;/* permute remainder recursively, */
  }                             /* and swap element back */
  return max;                   /* return value of best permutation */
}  /* permute() */

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

static double pm_cmp (PARTMAT *pm1, PARTMAT *pm2, int cfc1, int cfc2,
                      double *eval)
{                               /* --- compare partition matrices */
  int    i, k, n;               /* loop variables */
  double *r1, *r2;              /* rows of the partition matrices */
  double **cmp, *buf, *p;       /* comparison matrix and buffers */
  int    *map;                  /* map for permutations */
  double n00, n01, n10, n11;    /* contingency table entries */
  double c1, c2;                /* coincidence matrix entries */
  double t1, t2;                /* temporary buffers */
  CONJFN *conj1, *conj2;        /* conjunction functions (t-norms) */

  assert((pm1->rowcnt == pm2->rowcnt)
      && (pm1->colcnt == pm2->colcnt));
  cmp = (double**)malloc(pm1->rowcnt *sizeof(double*));
  if (!cmp) return -1;          /* create a comparison matrix */
  buf = (double*)malloc(pm1->rowcnt *pm1->rowcnt *sizeof(double));
  if (!buf) { free(cmp); return -1; }
  for (p = buf, i = pm1->rowcnt; --i >= 0; ) {
    cmp[i] = p; p += pm1->rowcnt; }
  map = (int*)malloc(pm1->rowcnt *sizeof(int));
  if (!map) {                   /* create a permutation map */
    free(buf); free(cmp); return -1; }
  conj1 = cftab[cfc1];          /* get the conjunction functions for */
  conj2 = cftab[cfc2];          /* combining the membership degrees */

  /* --- sum of squared differences --- */
  for (i = pm1->rowcnt; --i >= 0; ) {
    r1 = pm1->rows[i];          /* traverse rows of first matrix */
    for (k = pm1->rowcnt; --k >= 0; ) {
      r2 = pm2->rows[k];        /* traverse rows of second matrix */
      t1 = 0;                   /* init. sum of squared differences */
      for (n = pm1->colcnt; --n >= 0; ) {
        t2 = r1[n] -r2[n]; t1 += t2*t2; }
      cmp[i][k] = -t1;          /* compute the sum of squared diffs. */
    }                           /* and store them in the matrix, */
  }                             /* evaluate all permutations */
  eval[PM_DIFF] = -permute(pm1->rowcnt, pm1->rowcnt, map, cmp)
                / pm1->colcnt /pm1->rowcnt;

  /* --- cross-classification accuracy --- */
  for (i = pm1->rowcnt; --i >= 0; ) {
    r1 = pm1->rows[i];          /* traverse rows of first matrix */
    for (k = pm1->rowcnt; --k >= 0; ) {
      r2 = pm2->rows[k];        /* traverse rows of second matrix */
      n11 = n00 = 0;            /* init. contingency table elements */
      for (n = pm1->colcnt; --n >= 0; ) {
        n11 += conj1(  r1[n],   r2[n]);
        n00 += conj1(1-r1[n], 1-r2[n]);
      }                         /* sum conjunction of assignments */
      cmp[i][k] = n11 +n00;     /* compute cross-class. accuracies */
    }                           /* and store them in the matrix, */
  }                             /* then evaluate all permutations */
  eval[PM_ACC] = permute(pm1->rowcnt, pm1->rowcnt, map, cmp)
               / pm1->colcnt /pm1->rowcnt;

  /* --- F1 measure --- */
  for (i = pm1->rowcnt; --i >= 0; ) {
    r1 = pm1->rows[i];          /* traverse rows of first matrix */
    for (k = pm1->rowcnt; --k >= 0; ) {
      r2 = pm2->rows[k];        /* traverse rows of second matrix */
      n11 = n01 = n10 = 0;      /* init. contingency table elements */
      for (n = pm1->colcnt; --n >= 0; ) {
        n11 += conj1(  r1[n],   r2[n]);
        n01 += conj1(1-r1[n],   r2[n]);
        n10 += conj1(  r1[n], 1-r2[n]);
      }                         /* compute contingency table entries */
      cmp[i][k] = 2*n11 /(n10 +n01 +2*n11);
    }                           /* compute the F1 measures */
  }                             /* and store them in the matrix */
  eval[PM_F1] = permute(pm1->rowcnt, pm1->rowcnt, map, cmp)
              / pm1->rowcnt;    /* evaluate all permutations */

  /* --- coincidence matrix measures --- */
  n11 = n10 = n01 = n00 = 0;    /* clear the contingency table */
  for (i = pm1->colcnt; --i > 0; ) {
    for (k = i; --k >= 0; ) {   /* traverse all pairs of tuples */
      c1 = c2 = 0;              /* init. coincidence matrix elements */
      for (n = pm1->rowcnt; --n >= 0; ) {
        c1 += conj1(pm1->rows[n][i], pm1->rows[n][k]);
        c2 += conj1(pm2->rows[n][i], pm2->rows[n][k]);
      }                         /* compute coincidence matrix entries */
      n11 += conj2(  c1,   c2); /* and from it the four entries */
      n10 += conj2(  c1, 1-c2); /* of the contingency table */
      n01 += conj2(1-c1,   c2); /* (assignment of data points */
      n00 += conj2(1-c1, 1-c2); /* to same or different clusters) */
    }
  }
  t1 = (n11 +n10) *(n11 +n01);  /* compute some useful values that */
  t2 = (n00 +n10) *(n00 +n01);  /* appear in more than one measure */
  c1 = (n11 +n10 +n01 +n00);    /* and compute the measures */
  eval[PM_RAND]    = (n11 +n00) / c1;
  eval[PM_JACCARD] = n11 / (n11 +n10 +n01);
  eval[PM_FOLKES]  = n11 / sqrt(t1);
  eval[PM_HUBERT]  = (c1*n11 -t1) /sqrt(t1 *t2);

  free(map); free(buf); free(cmp);
  return 0;                     /* delete working memory and return */
}  /* pm_cmp() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

static void pm_delete (PARTMAT *pm)
{                               /* --- add current assig. to matrix */
  int i;                        /* loop variable */
  for (i = pm->rowcnt; --i >= 0; )
    free(pm->rows[i]);          /* delete the matrix rows */
  free(pm);                     /* and the base structure */
}  /* pm_delete() */

#endif
/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print error message */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print the error message */
    va_end(args);               /* end argument evaluation */
  }
  #ifndef NDEBUG                /* clean up memory */
  if (clset1) cls_delete(clset1);
  if (clset2) cls_delete(clset2);
  if (pmat1)  pm_delete(pmat1);
  if (pmat2)  pm_delete(pmat2);
  #ifdef MATVERSION
  if (tfscan) tfs_delete(tfscan);
  #else
  if (attset) as_delete(attset);
  #endif
  if (scan)   sc_delete(scan);  /* and close files */
  if (in && (in != stdin)) fclose(in);
  #endif
  exit(code);                   /* abort the program */
}  /* error() */

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

static void help (void)
{                               /* --- print help on init. modes */
  int i;                        /* loop variable */

  fprintf(stderr, "\n");        /* terminate startup message */
  printf("list of conjunction functions (options -m# and -c#):\n");
  printf("  name        conjunction function\n");
  for (i = 0; conjtab[i].name; i++) /* list of conjunction functions */
    printf("  %-10s  %s\n", conjtab[i].name, conjtab[i].desc);
  exit(0);                      /* abort the program */
}  /* help() */

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

static int code (const MODEINFO *tab, const char *name)
{                               /* --- get code of processing mode */
  for ( ; tab->name; tab++)     /* look up name in table */
    if (strcmp(tab->name, name) == 0)
      return tab->code;         /* return the code of the init. mode */
  return -1;                    /* or an error indicator */
}  /* code() */

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

int main (int argc, char *argv[])
{                               /* --- main function */
  int    i, k = 0;              /* loop variables, counters */
  char   *s;                    /* to traverse options */
  char   **optarg = NULL;       /* option argument */
  char   *fn_cls1 = NULL;       /* name of first  cluster set file */
  char   *fn_cls2 = NULL;       /* name of second cluster set file */
  #ifndef MATVERSION
  char   *fn_hdr  = NULL;       /* name of table header file */
  #endif
  char   *fn_in   = NULL;       /* name of table file */
  char   *blanks  = NULL;       /* blanks */
  char   *fldseps = NULL;       /* field  separators */
  char   *recseps = NULL;       /* record separators */
  char   *conjfn1 = "prod";     /* conjunction functions for */
  char   *conjfn2 = "prod";     /* combining membership degrees */
  #ifdef MATVERSION
  int    patcnt   = 0;          /* number of test patterns */
  double *pat;                  /* to traverse the patterns */
  #else
  ATTSET *dummy   = NULL;       /* attribute set (dummy for reading) */
  int    flags    = 0, f;       /* table file read flags */
  int    tplcnt   = 0;          /* number of tuples */
  double tplwgt   = 0.0, w;     /* weight of tuples */
  #endif
  int    cfc1, cfc2;            /* conjunction function codes */
  int    attcnt;                /* number of values in a pattern */
  int    clscnt;                /* number of clusters */
  double eval[8];               /* result of comparison */
  TFSERR *err;                  /* error information */

  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print startup/usage message --- */
  if (argc > 1) {               /* if arguments are given */
    fprintf(stderr, "%s - %s\n", argv[0], DESCRIPTION);
    fprintf(stderr, VERSION); } /* print a startup message */
  else {                        /* if no argument is given */
    #ifdef MATVERSION
    printf("usage: %s [options] clsfile1 clsfile2 patfile\n", argv[0]);
    #else
    printf("usage: %s [options] clsfile1 clsfile2 "
                     "[-d|-h hdrfile] tabfile\n", argv[0]);