ghkss.c

时间序列工具

/*
 *   This file is part of TISEAN
 *
 *   Copyright (c) 1998-2007 Rainer Hegger, Holger Kantz, Thomas Schreiber
 *
 *   TISEAN is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   TISEAN is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with TISEAN; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
/*Author: Rainer Hegger Last modified: Jun 10, 2006 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include "routines/tsa.h"

#define WID_STR "Multivariate noise reduction using the GHKSS algorithm"


#define BOX (unsigned int)1024

unsigned long length=ULONG_MAX,exclude=0;
unsigned int dim,qdim=2,delay=1,minn=50,iterations=1,comp=1,embed=5;
unsigned int verbosity=0xff;
double mineps,epsfac;
char *column=NULL;
char eps_set=0,euclidean=0,dimset=0,resize_eps;
char *outfile=NULL,stdo=1;
char *infile=NULL;

double *d_min,*d_max,d_max_max;
double **series,**delta,**corr;
double *metric,trace;
long **box,*list;
unsigned long *flist;
int emb_offset;
unsigned int ibox=BOX-1;
unsigned int *index_comp,*index_embed;

/*these are global to save time*/
int *sorted;
double *av,**mat,*matarray,*eig;

void show_options(char *progname)
{
  what_i_do(progname,WID_STR);
  fprintf(stderr,"Usage: %s [options]\n",progname);
  fprintf(stderr,"Options:\n");
  fprintf(stderr,"Everything not being a valid option will be interpreted"
          " as a possible"
          " datafile.\nIf no datafile is given stdin is read. Just - also"
          " means stdin\n");
  fprintf(stderr,"\t-l # of data to use [Default: whole file]\n");
  fprintf(stderr,"\t-x # of lines to be ignored [Default: 0]\n");
  fprintf(stderr,"\t-c column to read [Default: 1,..,# of components]\n");
  fprintf(stderr,"\t-m # of components,embedding dimension [Default: 1,5]\n");
  fprintf(stderr,"\t-d delay [Default: 1]\n");
  fprintf(stderr,"\t-q dimension to project to [Default: 2]\n");
  fprintf(stderr,"\t-k minimal number of neighbours [Default: 50]\n");
  fprintf(stderr,"\t-r minimal neighbourhood size \n\t\t"
	  "[Default: (interval of data)/1000]\n");
  fprintf(stderr,"\t-i # of iterations [Default: 1]\n");
  fprintf(stderr,"\t-2 use euklidean metric [Default: non euklidean]\n");
  fprintf(stderr,"\t-o name of output file \n\t\t"
	  "[Default: 'datafile'.opt.n, where n is the iteration.\n\t\t"
	  " If no -o is given, the last iteration is also"
	  " written to stdout]\n");
  fprintf(stderr,"\t-V verbosity level [Default: 7]\n\t\t"
          "0='only panic messages'\n\t\t"
          "1='+ input/output messages'\n\t\t"
          "2='+ average correction and trend'\n\t\t"
	  "4='+ how many points for which epsilon'\n");
  fprintf(stderr,"\t-h show these options\n");
  exit(0);
}

void scan_options(int n,char **in)
{
  char *out;

  if ((out=check_option(in,n,'l','u')) != NULL)
    sscanf(out,"%lu",&length);
  if ((out=check_option(in,n,'x','u')) != NULL)
    sscanf(out,"%lu",&exclude);
  if ((out=check_option(in,n,'c','s')) != NULL) {
    column=out;
    dimset=1;
  }
  if ((out=check_option(in,n,'m','2')) != NULL)
    sscanf(out,"%u,%u",&comp,&embed);
  if ((out=check_option(in,n,'d','u')) != NULL)
    sscanf(out,"%u",&delay);
  if ((out=check_option(in,n,'q','u')) != NULL)
    sscanf(out,"%u",&qdim);
  if ((out=check_option(in,n,'k','u')) != NULL)
    sscanf(out,"%u",&minn);
  if ((out=check_option(in,n,'r','f')) != NULL) {
    eps_set=1;
    sscanf(out,"%lf",&mineps);
  }
  if ((out=check_option(in,n,'i','u')) != NULL)
    sscanf(out,"%u",&iterations);
  if ((out=check_option(in,n,'V','u')) != NULL)
    sscanf(out,"%u",&verbosity);
  if ((out=check_option(in,n,'2','n')) != NULL)
    euclidean=1;
  if ((out=check_option(in,n,'o','o')) != NULL) {
    stdo=0;
    if (strlen(out) > 0)
      outfile=out;
  }
}

void sort(double *x,int *n)
{
  long i,j,iswap;
  double dswap;
  
  for (i=0;i<dim;i++)
    n[i]=i;
  
  for (i=0;i<dim-1;i++)
    for (j=i+1;j<dim;j++)
      if (x[j] > x[i]) {
	dswap=x[i];
	x[i]=x[j];
	x[j]=dswap;
	iswap=n[i];
	n[i]=n[j];
	n[j]=iswap;
      }
}

void mmb(double eps)
{
  long i,x,y;
  double ieps=1.0/eps;

  for (x=0;x<BOX;x++)
    for (y=0;y<BOX;y++)
      box[x][y] = -1;
  
  for (i=emb_offset;i<length;i++) {
    x=(int)(series[0][i]*ieps)&ibox;
    y=(int)(series[comp-1][i-emb_offset]*ieps)&ibox;
    list[i]=box[x][y];
    box[x][y]=i;
  }
}

unsigned long fmn(long which,double eps)
{
  unsigned long nf=0;
  long i,i1,i2,j,j1,k,k1,li;
  long element;
  double dx=0.0;
  
  i=(int)(series[0][which]/eps)&ibox;
  j=(int)(series[comp-1][which-emb_offset]/eps)&ibox;
  
  for (i1=i-1;i1<=i+1;i1++) {
    i2=i1&ibox;
    for (j1=j-1;j1<=j+1;j1++) {
      element=box[i2][j1&ibox];
      while (element != -1) {
	for (k=0;k<embed;k++) {
	  k1= -k*(int)delay;
	  for (li=0;li<comp;li++) {
	    dx=fabs(series[li][which+k1]-series[li][element+k1]);
	    if (dx > eps)
	      break;
	  }
	  if (dx > eps)
	    break;
	}
	if (dx <= eps)
	  flist[nf++]=element;
	element=list[element];
      }
    }
  }
  return nf;
}

void make_correction(unsigned long n,unsigned long nf)
{
  long i,i1,i2,j,j1,j2,k,k1,k2,hs;
  double help;
  
  for (i=0;i<dim;i++) {
    i1=index_comp[i];
    i2=index_embed[i];
    help=0.0;
    for (j=0;j<nf;j++)
      help += series[i1][flist[j]-i2];
    av[i]=help/nf;
  }

  for (i=0;i<dim;i++) {
    i1=index_comp[i];
    i2=index_embed[i];
    for (j=i;j<dim;j++) {
      help=0.0;
      j1=index_comp[j];
      j2=index_embed[j];
      for (k=0;k<nf;k++) {
	hs=flist[k];
	help += series[i1][hs-i2]*series[j1][hs-j2];
      }
      mat[i][j]=(help/nf-av[i]*av[j])*metric[i]*metric[j];
      mat[j][i]=mat[i][j];
    }
  }

  eigen(mat,(unsigned long)dim,eig);
  sort(eig,sorted);

  for (i=0;i<dim;i++) {
    help=0.0;
    for (j=qdim;j<dim;j++) {
      hs=sorted[j];
      for (k=0;k<dim;k++) {
	k1=index_comp[k];
	k2=index_embed[k];
	help += (series[k1][n-k2]-av[k])*mat[k][hs]*mat[i][hs]*metric[k];
      }
    }
    corr[n][i]=help/metric[i];
  }
}

void handle_trend(unsigned long n,unsigned long nf)
{
  long i,i1,i2,j;
  double help;
  
  for (i=0;i<dim;i++) {
    help=0.0;
    for (j=0;j<nf;j++)
      help += corr[flist[j]][i];
    av[i]=help/nf;
  }

  for (i=0;i<dim;i++) {
    i1=index_comp[i];
    i2=index_embed[i];
    delta[i1][n-i2] += (corr[n][i]-av[i])/(trace*metric[i]);
  }
}

void set_correction(void)
{
  long i,j;
  double *hav,*hsigma,help;

  check_alloc(hav=(double*)malloc(sizeof(double)*comp));
  check_alloc(hsigma=(double*)malloc(sizeof(double)*comp));
  for (j=0;j<comp;j++)
    hav[j]=hsigma[j]=0.0;

  for (i=0;i<length;i++)
    for (j=0;j<comp;j++) {
      hav[j] += (help=delta[j][i]);
      hsigma[j] += help*help;
    }

  for (j=0;j<comp;j++) {
    hav[j] /= length;
    hsigma[j]=sqrt(fabs(hsigma[j]/length-hav[j]*hav[j]));
  }
  if (verbosity&(VER_USR1|VER_USR2)) {
    for (i=0;i<comp;i++) {
      fprintf(stderr,"Average shift of component %ld = %e\n",i+1,
	      hav[i]*d_max[i]);
      fprintf(stderr,"Average rms correction of comp. %ld = %e\n\n",
	      i+1,hsigma[i]*d_max[i]);
    }
  }
  for (i=0;i<length;i++)
    for (j=0;j<comp;j++)
      series[j][i] -= delta[j][i];

  if (resize_eps) {
    mineps /= epsfac;
    if (verbosity&VER_USR2)
      fprintf(stderr,"Reset minimal neighbourhood size to %e\n",
	      mineps*d_max_max);
  }

  resize_eps=0;
  free(hav);
  free(hsigma);
}

int main(int argc,char **argv)
{
  char stdi=0;
  int iter,epscount,*ok;
  long i,j;
  char all_done;
  char *ofname;
  unsigned long nfound,n,allfound;
  double epsilon;
  double **hser;
  FILE *file;

  if (scan_help(argc,argv))
    show_options(argv[0]);
  
  scan_options(argc,argv);
#ifndef OMIT_WHAT_I_DO
  if (verbosity&VER_INPUT)
    what_i_do(argv[0],WID_STR);
#endif

  dim=comp*embed;
  emb_offset=(embed-1)*delay;

  infile=search_datafile(argc,argv,NULL,verbosity);
  if (infile == NULL)
    stdi=1;

  if (outfile == NULL) {
    if (!stdi) {
      check_alloc(outfile=(char*)calloc(strlen(infile)+5,(size_t)1));
      check_alloc(ofname=(char*)calloc(strlen(infile)+9,(size_t)1));
      sprintf(outfile,"%s.opt",infile);
    }
    else {
      check_alloc(outfile=(char*)calloc((size_t)10,(size_t)1));
      check_alloc(ofname=(char*)calloc((size_t)14,(size_t)1));
      sprintf(outfile,"stdin.opt");
    }
  }
  else
    check_alloc(ofname=(char*)calloc(strlen(outfile)+10,(size_t)1));
  
  if (column == NULL)
    series=(double**)get_multi_series(infile,&length,exclude,&comp,"",
				     dimset,verbosity);
  else 
    series=(double**)get_multi_series(infile,&length,exclude,&comp,column,
				      dimset,verbosity);

  if (length < minn) {
    fprintf(stderr,"With %lu data you will never find %u neighbors."
	    " Exiting!\n",length,minn);
    exit(GHKSS__TOO_MANY_NEIGHBORS);
  }

  check_alloc(d_min=(double*)malloc(sizeof(double)*comp));
  check_alloc(d_max=(double*)malloc(sizeof(double)*comp));
  d_max_max=0.0;
  for (i=0;i<comp;i++) {
    rescale_data(series[i],length,&d_min[i],&d_max[i]);
    if (d_max[i] > d_max_max)
      d_max_max=d_max[i];
  }

  if (!eps_set)
    mineps=1./1000.;
  else
    mineps /= d_max_max;
  epsfac=sqrt(2.0);

  check_alloc(box=(long**)malloc(sizeof(long*)*BOX));
  for (i=0;i<BOX;i++)
    check_alloc(box[i]=(long*)malloc(sizeof(long)*BOX));

  check_alloc(list=(long*)malloc(sizeof(long)*length));
  check_alloc(flist=(unsigned long*)malloc(sizeof(long)*length));

  check_alloc(metric=(double*)malloc(sizeof(double)*dim));
  trace=0.0;
  if (euclidean) {
    for (i=0;i<dim;i++) {
      metric[i]=1.0;
      trace += 1./metric[i];
    }
  }
  else {
    for (i=0;i<dim;i++) {
      if ((i >= comp) && (i < ((long)dim-(long)comp))) 
	metric[i]=1.0;
      else 
	metric[i]=1.0e3;
      trace += 1./metric[i];
    }
  }

  check_alloc(corr=(double**)malloc(sizeof(double*)*length));
  for (i=0;i<length;i++)
    check_alloc(corr[i]=(double*)malloc(sizeof(double)*dim));
  check_alloc(ok=(int*)malloc(sizeof(int)*length));
  check_alloc(delta=(double**)malloc(sizeof(double*)*comp));
  for (i=0;i<comp;i++)
    check_alloc(delta[i]=(double*)malloc(sizeof(double)*length));
  check_alloc(index_comp=(unsigned int*)malloc(sizeof(int)*dim));
  check_alloc(index_embed=(unsigned int*)malloc(sizeof(int)*dim));
  check_alloc(av=(double*)malloc(sizeof(double)*dim));
  check_alloc(sorted=(int*)malloc(sizeof(int)*dim));
  check_alloc(eig=(double*)malloc(sizeof(double)*dim));
  check_alloc(matarray=(double*)malloc(sizeof(double)*dim*dim));
  check_alloc(mat=(double**)malloc(sizeof(double*)*dim));
  for (i=0;i<dim;i++)
    mat[i]=(double*)(matarray+dim*i);
  check_alloc(hser=(double**)malloc(sizeof(double*)*comp));

  for (i=0;i<dim;i++) {
    index_comp[i]=i%comp;
    index_embed[i]=(i/comp)*delay;
  }

  resize_eps=0;
  for (iter=1;iter<=iterations;iter++) {
    for (i=0;i<length;i++) {
      ok[i]=0;
      for (j=0;j<dim;j++)
	corr[i][j]=0.0;
      for (j=0;j<comp;j++)
	delta[j][i]=0.0;
    }
    epsilon=mineps;
    all_done=0;
    epscount=1;
    allfound=0;
    if (verbosity&(VER_USR1|VER_USR2))
      fprintf(stderr,"Starting iteration %d\n",iter);
    while(!all_done) {
      mmb(epsilon);
      all_done=1;
      for (n=emb_offset;n<length;n++)
	if (!ok[n]) {
	  nfound=fmn(n,epsilon);
	  if (nfound >= minn) {
	    make_correction(n,nfound);
	    ok[n]=epscount;
	    if (epscount == 1)
	      resize_eps=1;
	    allfound++;
	  }
	  else
	    all_done=0;
	}
      if (verbosity&VER_USR2)
	fprintf(stderr,"Corrected %ld points with epsilon= %e\n",allfound,
		epsilon*d_max_max);
      epsilon *= epsfac;
      epscount++;
    }
    if (verbosity&VER_USR2)
      fprintf(stderr,"Start evaluating the trend\n");

    epsilon=mineps;
    allfound=0;
    for (i=1;i<epscount;i++) {
      mmb(epsilon);
      for (n=emb_offset;n<length;n++)
	if (ok[n] == i) {
	  nfound=fmn(n,epsilon);
	  handle_trend(n,nfound);
	  allfound++;
	}
      if (verbosity&VER_USR2)
	fprintf(stderr,"Trend subtracted for %ld points with epsilon= %e\n",
		allfound,epsilon*d_max_max);
      epsilon *= epsfac;
    }
    set_correction();
    
    sprintf(ofname,"%s.%d",outfile,iter);
    test_outfile(ofname);

    file=fopen(ofname,"w");
    if (verbosity&VER_INPUT)
      fprintf(stderr,"Opened %s for writing\n\n",ofname);
    for (i=0;i<length;i++) {
      for (j=0;j<comp;j++) {
	fprintf(file,"%e ",series[j][i]*d_max[j]+d_min[j]);
      }
      fprintf(file,"\n");
      if (stdo && (iter == iterations)) {
	for (j=0;j<comp;j++)
	  fprintf(stdout,"%e ",series[j][i]*d_max[j]+d_min[j]);
	fprintf(stdout,"\n");
      }
    }
    fclose(file);
  }

  return 0;
}