cluster1.c

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

  assert(clset);                /* check the function arguments */
  if (!tpl) {                   /* if to terminate registration */
    nst_reg(clset->nst, NULL, 0); return; }
  am_exec(clset->attmap, tpl, AM_INPUTS, clset->vec);
  nst_reg(clset->nst, clset->vec, tpl_getwgt(tpl));
}  /* cls_regx() */             /* set the data values and register */

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

void cls_valuex (CLSET *clset, const TUPLE *tpl)
{                               /* --- register a training tuple */
  assert(clset);                /* check the function arguments */
  am_exec(clset->attmap, tpl, AM_INPUTS, clset->vec);
  nst_norm(clset->nst, clset->vec, clset->vec);
}  /* cls_valuex() */           /* normalize the input values */

#endif
/*--------------------------------------------------------------------*/

void cls_type (CLSET *clset, int type, double var)
{                               /* --- set the cluster type */
  int     i;                    /* loop variable */
  CLUSTER *p;                   /* to traverse the clusters */
  double  t;                    /* temporary buffer */

  assert(clset);                /* check the function arguments */
  clset->type = type & CLS_ALL; /* note the cluster type */
  if (var <= 0) return;         /* check the initial variance */
  for (p = clset->cls +(i = clset->clscnt); --i >= 0; ) {
    t = var /(--p)->var;        /* compute the adaptation factor */
    p->var = var;               /* set initial isotropic variance */
    if      (clset->type & CLS_COVARS) {
      mat_muls(p->cov, p->cov, t);
      mat_muls(p->inv, p->inv, 1/t); }
    else if (clset->type & CLS_VARS) {
      mat_diamuls(p->cov, t);
      mat_diamuls(p->inv, 1/t);
    }                           /* adapt the covariance matrix */
  }                             /* and its inverse matrix */
}  /* cls_type() */

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

void cls_radfn (CLSET *clset, RADFN radfn, const double *params)
{                               /* --- set the membership function */
  assert(clset && radfn && params);  /* check the function arguments */
  clset->radfn    = radfn;      /* note the radial function */
  clset->rfnps[0] = params[0];  /* and its parameters and */
  clset->rfnps[1] = params[1];  /* compute the normalization factor */
  clset->norm     = radfn(-clset->incnt, params);
}  /* cls_radfn() */

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

void cls_norm (CLSET *clset, int mode,
               const double *params, double noise)
{                               /* --- set normalization mode */
  assert(clset);                /* check the function arguments */
  if (mode >= 0)                /* if the norm. mode is valid, */
    clset->mode = mode;         /* note the normalization mode */
  if (params) {                 /* if parameters are given */
    clset->nrmps[0] = params[0];
    clset->nrmps[1] = params[1];
  }                             /* note the normalization parameters */
  clset->noise    = noise;      /* and the noise cluster parameter */
  clset->msd[0]   = (noise >= 0) ? noise
                  : clset->radfn(noise*noise, clset->rfnps);
}  /* cls_norm() */             /* compute the membership degree */

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

int cls_exec (CLSET *clset, const double *vec, double *msdegs)
{                               /* --- compute degrees of membership */
  int     i, k, best;           /* loop variables, cluster index */
  int     type;                 /* cluster type flags */
  CLUSTER *p;                   /* to traverse the clusters */
  double  *c, *b;               /* to access the center and buffer */
  double  d;                    /* squared distance to cluster center */
  double  sum, max;             /* sum/maximum of membership degrees */

  assert(clset);                /* check the function arguments */
  if (vec) nst_norm(clset->nst, vec, clset->vec);
  vec = clset->vec;             /* scale given vector to the buffer */

  /* --- compute unnormalized degrees of membership --- */
  type = clset->type;           /* get the cluster type and */
  best = 0; sum = 0; max = -DBL_MAX;     /* init. variables */
  for (p = clset->cls +(k = clset->clscnt); --k >= 0; ) {
    c = (--p)->ctr; b = p->dif; /* traverse the clusters */
    for (i = clset->incnt; --i >= 0; )
      b[i] = vec[i] -c[i];      /* compute diff. vector to center */
    if      (type & CLS_COVARS) /* -- if to use covariances */
      d = mat_mulvmv(p->inv,b); /* compute Mahalanobis distance */
    else if (type & CLS_VARS)   /* -- if to use variances */
      d = mat_mulvdv(p->inv,b); /* compute coord. weighted distance */
    else                        /* -- if to use isotropic variance */
      d = vec_sqrlen(b, clset->incnt) /p->var;
    if      (  d <  0 ) d = 0;  /* check the computed distance */  
    else if (!(d >= 0)) d = 1/MINVAR;
    p->d2  = d;                 /* and store it (for eval. measures) */
    p->msd = clset->radfn(d, clset->rfnps);
    if ((type & CLS_NORM) && (clset->norm > 0)) {
      d = sqrt(pow(p->var, clset->incnt));
      p->msd *= (d > 0) ? clset->norm /d : 0;
    }                           /* normalize for probability dist. */
    if (type & CLS_WEIGHT)      /* if to use adaptable weights, */
      p->msd *= p->wgt;         /* incorporate the weight/prior */
    d = clset->nrmps[0];        /* raise m.s. degree to given power */
    if      (d == 2) p->msd *= p->msd;
    else if (d != 1) p->msd  = pow(p->msd, d);
    if (!(p->msd >= 0)) p->msd = 0;
    sum += p->msd;              /* check and sum membership degree */
    if (p->msd >= max) { max = p->msd; best = k; }
  }                             /* determine max. membership degree */

  /* --- reduce unnormalized membership degrees --- */
  d = clset->nrmps[1];          /* get the offset parameter */
  if (d > 0) {                  /* if actually to use an offset */
    d *= max; max -= d;         /* compute (relative) offset */
    for (sum = 0, p += k = clset->clscnt; --k >= 0; ) {
      if (p->msd <= d) p->msd  = 0;
      else      sum += p->msd -= d;
    }                           /* traverse the membership degrees */
  }                             /* and reduce and (re)sum them */

  /* --- normalize degrees of membership --- */
  if      (clset->mode == CLS_HARD) {  /* if to do hard clustering */
    for (p += k = clset->clscnt; --k >= 0; )
      (--p)->msd = 0;           /* clear all membership degrees */
    if (max < clset->msd[0])    /* if the maximum is not high enough, */
      clset->msd[1] = 1;        /* assign pattern to noise cluster */
    else {                      /* if the maximum is high enough */
      clset->msd[1] = 0; p[best].msd = 1;
    } }                         /* assign pattern to best cluster */
  else if (clset->mode == CLS_MAX1) {  /* if to normalize to max. 1 */
    if (clset->msd[0] > max)    /* compare to membership degree */
      max = clset->msd[0];      /* to noise cluster */
    max = (max > 0) ? 1/max :1; /* compute the normalization factor */
    for (p += k = clset->clscnt; --k >= 0; )
      (--p)->msd *= max;        /* compute rel. membership degrees */
    clset->msd[1] = clset->msd[0] *max; }
  else if (clset->mode == CLS_SUM1) {  /* if to normalize to sum 1 */
    sum += clset->msd[0];       /* add m.s. degree to noise cluster */
    sum = (sum > 0) ? 1/sum :1; /* compute the normalization factor */
    for (p += k = clset->clscnt; --k >= 0; )
      (--p)->msd *= sum;        /* compute rel. membership degrees */
    clset->msd[1] = clset->msd[0] *sum;
  }                             /* set m.s. degree to noise cluster */

  /* --- set the result --- */
  if (msdegs) {                 /* if a result vector is given */
    for (p += i = clset->clscnt; --i >= 0; )
      msdegs[i] = (--p)->msd;   /* copy the normalized m.s. degrees */
  }                             /* to the given vector */
  return best;                  /* return index of best cluster */
}  /* cls_exec() */

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

void cls_unscale (CLSET *clset)
{                               /* --- remove attribute scaling */
  int     i, k, n;              /* loop variables */
  CLUSTER *p;                   /* to traverse the clusters */
  double  *c;                   /* cluster center */
  double  t;                    /* temporary buffer */

  assert(clset);                /* check the function argument */
  if (!(clset->type & (CLS_VARS|CLS_COVARS))) {
    t = nst_factor(clset->nst, 0); /* if sized spherical clusters */
    for (n = clset->incnt; --n > 0; )
      if (nst_factor(clset->nst, n) != t)
        break;                  /* check for different scales */
    if (n > 0) {                /* if there are different factors, */
      clset->type |= CLS_VARS;  /* use attribute specific variances */
      for (p = clset->cls +(i = clset->clscnt); --i >= 0; ) {
        t = 1/(--p)->var;       /* compute inverse variance */
        for (n = clset->incnt; --n >= 0; ) {
          mat_set(p->cov, n, n, p->var);
          mat_set(p->inv, n, n, t);
        }                       /* fill the covariance matrix and */
      } }                       /* its inverse with isotropic values */
    else {                      /* if all scaling factors are equal */
      t *= t;                   /* compute the scaling factor */
      for (p = clset->cls +(i = clset->clscnt); --i >= 0; )
        (--p)->var /= t;        /* unscale the isotropic variance */
    }                           /* of all clusters */
  }
  for (p = clset->cls +(i = clset->clscnt); --i >= 0; ) {
    c = (--p)->ctr;             /* traverse the clusters */
    nst_inorm(clset->nst, c,c); /* unscale the center coordinates */
    for (n = clset->incnt; --n >= 0; ) { /* traverse the dimensions */
      if (!(clset->type & (CLS_VARS|CLS_COVARS)))
        continue;               /* if there is no shape information */
      k = (clset->type & CLS_COVARS) ? 0 : n;
      for ( ; k <= n; k++) {    /* traverse the matrix row */
        t = nst_factor(clset->nst, k)   /* compute the */
          * nst_factor(clset->nst, n);  /* scaling factor */
        mat_set(p->cov, k, n, mat_get(p->cov, k, n) /t);
        mat_set(p->inv, k, n, mat_get(p->inv, k, n) *t);
      }                         /* unscale the elements */
    }                           /* of the covariance matrix */
    mat_tr2sym(p->cov, p->cov, MAT_UPPER);
    mat_tr2sym(p->inv, p->inv, MAT_UPPER);
  }                             /* complete the matrices */
  nst_scale(clset->nst, -1, 0, 1);
}  /* cls_unscale() */          /* set scaling to identity */

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

int cls_desc (CLSET *clset, FILE *file, int mode, int maxlen)
{                               /* --- describe a set of clusters */
  int     i, k, n;              /* loop variables */
  CLUSTER *p;                   /* to traverse the clusters */
  char    *indent = "";         /* indentation string */
 
  assert(clset && file);        /* check the function arguments */

  /* --- print a header (as a comment) --- */
  if (mode & CLS_TITLE) {       /* if the title flag is set */
    i = k = (maxlen > 0) ? maxlen -2 : 70;
    fputs("/*", file); while (--i >= 0) fputc('-', file);
    fputs("\n  cluster set\n", file);
    while (--k >= 0) fputc('-', file); fputs("*/\n", file);
  }                             /* print a title header */
  if (maxlen <= 0) maxlen = INT_MAX;

  #ifdef CLS_EXTFN              /* if to compile extended functions */
  if (clset->attmap && !(mode & CLS_RBFNET)) {
    fputs("clset = {\n", file); /* if based on an attribute set, */
    indent = "  ";              /* start the cluster set description */
  }                             /* and indent the description itself */
  #endif
  if (mode & CLS_RBFNET) indent = "  ";

  /* --- print scaling parameters --- */
  nst_desc(clset->nst, file, indent, maxlen);

  /* --- print the function description --- */
  fputs(indent,        file);   /* write the indentation */
  fputs("function = ", file);   /* and the function name */
  fputs((clset->radfn == rf_gauss) ? "gauss" : "cauchy", file);
  fprintf(file, "(%g,%g)",      /* write the function parameters */
          clset->rfnps[0], clset->rfnps[1]);
  if (clset->type & CLS_NORM) fputs(", normalized", file);
  fputs(";\n", file);           /* write a normalization flag */

  /* --- print the initial radius --- */
  if (!(clset->type & (CLS_SIZE|CLS_VARS|CLS_COVARS))