cluster1.c

it is the Data Mining Algorithm source code.

  /* --- finalize setup --- */
  clset->type = clset->tnew;    /* set the new cluster type */
  if ((clset->tnew & CLS_COVARS)/* if covariances have been added */
  && !(k           & CLS_COVARS)) {
    for (c += i = n; --i >= 0; ) { --c;
      mat_crop(c->cov, MAT_DIAG);
      mat_crop(c->inv, MAT_DIAG);
    }                           /* clear the covariances and compute */
    clset->type &= ~CLS_COVARS; /* feature weights/inverse matrices */
  }                             /* as for only variances */
  cls_ftwgts(clset);            /* compute the feature weights */
  cls_invert(clset);            /* and the inverse matrices */
  clset->type = clset->tnew;    /* set the new cluster type again */
  if (clset->type & CLS_JOINT)  /* if joint (co)variances, */
    cls_distrib(clset);         /* distribute joint (co)variances */
  cls_reinit(clset);            /* reinit. aggregation matrices */
  clset->setup = 1;             /* cluster set has been set up */
  return 0;                     /* return 'ok' */
}  /* cls_setup() */

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

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

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

  /* --- compute raw degrees of membership --- */
  for (c = clset->cls +(k = clset->clscnt); --k >= 0; ) {
    z = (--c)->ctr; b = c->dif; /* traverse the clusters */
    for (i = clset->incnt; --i >= 0; )
      b[i] = vec[i] -z[i];      /* compute diff. vector to center */
    if      (clset->type & CLS_COVARS) /* -- if to use covariances */
      d = mat_mulvmv(c->inv,b); /* compute Mahalanobis distance */
    else if (clset->type & CLS_VARS)   /* -- if to use variances */
      d = mat_mulvdv(c->inv,b); /* compute coord. weighted distance */
    else                        /* -- if to use isotropic variance */
      d = vec_sqrlen(b, clset->incnt) *mat_get(c->inv, 0, 0);
    if      (  d <  0 ) d = 0;  /* check the computed distance */  
    else if (!(d >= 0)) d = MAXVAR;
    /* Here d contains the squared and scaled distance between */
    /* the data point and the center of the current cluster c. */
    c->d2  = d;                 /* note distance (for eval. measures) */
    c->msd = clset->radfn(d, clset->rfnps);
    if ((clset->type & CLS_NORM) && (clset->unit > 0)) {
      d = sqrt(pow(c->var, clset->incnt));
      if (d > 0) c->msd *= clset->unit /d;
      else       c->msd  = 0;   /* normalize membership degree */
    }                           /* for a probability distribution */
    if (clset->type & CLS_WEIGHT)   /* if to use adaptable weights, */
      c->msd *= mat_getwgt(c->cov); /* incorporate the weight/prior */
    if (!(c->msd >= 0))         /* ensure a valid membership degree */
      c->msd = 0;               /* (note that !(x >= 0) is true */
  }                             /* even if x is not a valid number) */

  /* --- transform degrees of membership --- */
  if (clset->norm != CLS_HARD){ /* if not hard/crisp clustering */
    d = clset->nrmps[1];        /* get the transformation parameters */
    x = clset->nrmps[0];        /* (offset and exponent) */
    if (x == 0) {               /* if to use corresponding value */
      if      (clset->msexp >= 1) x = 1 /(clset->msexp -1);
      else if (clset->msexp >  0) x =     clset->msexp;
      else                        x = 1;
    }                           /* compute the corresponding value */
    if (x <  1) {               /* -- if alternative fuzzifier */
      for (c += k = clset->clscnt; --k >= 0; )
        clset->buf[k] = (--c)->msd;
      v_dblsort(clset->buf, k = clset->clscnt);
      v_dblrev (clset->buf, k); /* sort m.s. degrees descendingly */
      for (sum = d = clset->buf[i = 0]; ++i < k; ) {
        d = clset->buf[i];      /* traverse the membership degrees */
        if (d *(1 +x*i) <= x *(sum +d)) break;
        sum += d;               /* find number of clusters with */
      }                         /* a positive degree of membership */
      /* Note that if two (or more) feature weights are equal, then */
      /* either all or none of them satisfy the above condition for */
      /* a non-zero transformed feature weight. */
      if (sum <= 0) sum = 1;    /* make sure sum does not vanish */
      d = x *(max = 1/(1-x));   /* compute transformation parameters */
      x = (1 +x *(i-1)) *max /sum;
      for (c += k = clset->clscnt; --k >= 0; ) {
        --c; c->msd = x *c->msd -d;
      } }                       /* transform the membership degrees */
    else {                      /* -- if heuristic transformation */
      if (x != 1) {             /* if not unit exponent */
        c += k = clset->clscnt; /* traverse the clusters */
        if (x == 2) while (--k >= 0) { --c; c->msd *= c->msd; }
        else        while (--k >= 0) { --c; c->msd  = pow(c->msd, x); }
      }                         /* raise ms. degrees to given power */
      if (d > 0) {              /* if to use an offset */
        max = -DBL_MAX;         /* find maximal degree of membership */
        for (c += k = clset->clscnt; --k >= 0; )
          if ((--c)->msd > max) max = c->msd;
        d *= max;               /* compute (relative) offset */
        for (c += k = clset->clscnt; --k >= 0; )
          (--c)->msd -= d;      /* subtract the computed offset */
      }                         /* from all membership degrees */
    }
  }  /* if (clset->norm != CLS_HARD) .. */

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

  /* --- set the result --- */
  if (msdegs) {                 /* if a result array is given */
    for (c += k = clset->clscnt; --k >= 0; )
      msdegs[k] = (--c)->msd;   /* copy the normalized membership */
  }                             /* degrees to the given array */
  return best;                  /* return index of best cluster */
}  /* cls_exec() */             /* (highest degree of membership) */

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

void cls_sclcov (CLSET *clset)
{                               /* --- scale (co)variances */
  int     i, m;                 /* loop variables, buffer */
  CLUSTER *c;                   /* to traverse the clusters */

  assert(clset);                /* check the function argument */
  if (!(clset->type & (CLS_COVARS|CLS_VARS|CLS_SIZE)))
    return;                     /* check whether scaling is needed */
  m = (clset->type & CLS_COVARS) ? MAT_UPPER : MAT_DIAG;
  for (c = clset->cls +(i = clset->clscnt); --i >= 0; ) {
    --c; mat_mulsx(c->cov, c->cov, c->scale, m);
    c->var  *= c->scale;        /* rescale the covariance matrices, */
    c->size *= c->scale;        /* the isotropic variance, */
    c->scale = 1;               /* and the cluster size and */
  }                             /* finally set a unit scale */
}  /* cls_sclcov() */

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

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

  assert(clset);                /* check the function argument */
  if (!(clset->type & CLS_SIZE)) {
    if (!clset->setup) {        /* if cluster set is not set up */
      cls_vars  (clset, 0);     /* compute the isotropic variances, */
      cls_gauge (clset);        /* measure the cluster sizes, */
      cls_resize(clset, 0);     /* and resize the clusters */
    }
    cls_sclcov(clset);          /* scale the covariance matrices */
  }
  for (c = clset->cls +(i = clset->clscnt); --i >= 0; ) {
    --c;                        /* traverse the clusters */
    nst_inorm(clset->nst, c->ctr, c->ctr);
  }                             /* unscale the center coordinates */
  t = nst_factor(clset->nst, 0);
  for (k = clset->incnt; --k > 0; )
    if (nst_factor(clset->nst, k) != t)
      break;                    /* check for different scales */
  if (k >= 0) {                 /* if there are different scales */
    if (clset->type & (CLS_COVARS|CLS_VARS)) {
      clset->type |= CLS_SIZE;  /* size are no longer uniform */
      clset->tnew |= CLS_SIZE;  /* (since the dimensions */
    }                           /* are scaled differently) */
    if (!(clset->type & (CLS_COVARS|CLS_VARS))) {
      clset->type |= CLS_VARS;  /* set the flag for variances */
      clset->tnew |= CLS_VARS;  /* (both old and new type) */
      i = (clset->type & CLS_JOINT) ? 1 : clset->clscnt;
      for (c = clset->cls +i; --i >= 0; ) {
        --c; mat_diasetx(c->cov, mat_get(c->cov, 0, 0)); }
    }                           /* set attribute specific variances */
  }                             /* (as they will differ afterwards) */
  if (clset->type & (CLS_COVARS|CLS_VARS|CLS_SIZE)) {
    m = (clset->type & (CLS_COVARS|CLS_VARS)) ? clset->incnt : 1;
    n = (clset->type &  CLS_JOINT) ? 1 : clset->clscnt;
    for (c = clset->cls +n; --n >= 0; ) {
      (--c)->size = -1;         /* traverse the clusters */
      for (i = m; --i >= 0; ) { /* traverse the matrix rows */
        k = (clset->type & CLS_COVARS) ? clset->incnt : i+1;
        while (--k >= i) {      /* traverse the matrix columns */
          t = nst_factor(clset->nst, i) * nst_factor(clset->nst, k);
          mat_set(c->cov, i, k, mat_get(c->cov, i, k) /t);
        }                       /* compute the scaling factor */
      }                         /* and unscale the elements */
    }                           /* of the covariance matrix */
  }                             /* finally set scaling to identity */
  nst_scale(clset->nst, -1, 0, 1);
  clset->setup = 0;             /* cluster set needs to be set up */
}  /* cls_unscale() */

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

static void _descov (CLSET *clset, CLUSTER *c, char *indent, FILE *file)
{                               /* --- describe shape and size */
  int i, k, n;                  /* loop variables, number of dims. */

  n = clset->incnt;             /* get the number of dimensions */
  if (clset->type & CLS_COVARS){/* if full covariance matrix */
    for (k = 0; k < n; k++) {   /* traverse the matrix rows */
      fprintf(file, ",\n%s            ", indent);
      fprintf(file, "  [% g", mat_get(c->cov, 0, k));
      for (i = 0; ++i <= k; )   /* start a new line for each row */
        fprintf(file, ", % g", mat_get(c->cov, i, k));
      fputc(']', file);         /* print the covariances */
    }                           /* row by row (lower triangle) */
    if (clset->fwexp > 0) {     /* if to print feature weights */
      fprintf(file, "\n%s              /*", indent);
      for (k = 0; k < n; k++) { /* traverse the matrix rows */
        if (c->dif[k] <= 0) break;
        if (k > 0) fprintf(file, "\n%s                ", indent);
        fprintf(file, " %g:", c->dif[k]);
        for (i = 0; i < n; i++) /* start a new line for each row */
          fprintf(file, " % g", mat_get(c->inv, i, k));
      }                         /* print the eigenvalues (weights) */
      fputs(" */", file);       /* and the corresponding eigenvectors */
    } }                         /* finally terminate the comment */
  else if (clset->type & CLS_VARS) { /* if only variances */
    fprintf(file, ",\n%s            ", indent);
    fprintf(file, "  [%g", mat_get(c->cov, 0, 0));
    for (i = 0; ++i < n; )      /* traverse the dimensions */
      fprintf(file, ", %g", mat_get(c->cov, i, i));
    fputc(']', file);           /* print a list of variances */
    if (clset->fwexp > 0) {     /* if to print feature weights */
      fprintf(file, "\n%s              /*", indent);