SFFS_Search.rar_SFFS_SFFS matlab_subset selection

This is a C++ listing of Classical Floating Search Method (both forward and backward) ----------------------------------------------------------------------------------- (taken from the Feature Selection Toolbox package programmed by Petr Somol) - the code is written basically in ANSI C, the only C++ specialities used are commentary marks // and blocks described later, C++ was used later for programming the user interface (using Powersoft Optima++ 1.5 under Win32), not included here - to use the code you would probably have to rewrite/modify following parts: * criterion procedure "Criterion()" should be replaced by calling of your criterion function, together with possible parameter passing * memory allocation procedure "SafeAlloc()" does nothing special, it only tests if there is enough memory available before allocation * memory deallocation macro's "FREE()" second argument is informational only and may be replaced without harm * functions and types "time()", "ctime()", "time_t", "TimeString()", "difftime()" serve for measuring computational time and are not needed for the algorithm to work properly * "printtext()", "printint()", "printdouble()", etc. serve for outputting its parameter's value and may be discarded or replaced by printf() (or any other output procedures) * information about current algorithm state (percentages, current dimension etc.) is stored to "ProcessText" string. This uses also "GetStopFlag()", "SetProcessFlag()" procedures and "ProcessTextCS" semaphore. In our package the procedure runs as a thread, while another low-priority thread keeps the user informed about current procedure state. That's why this compiler-dependent block of code is included into the procedure. This block of code may be discarded. - meaning of constants and some identifiers you may need to set for calling the procedure (local variables are described inside the procedure): * int n - full feature set size * int d - desired feature subset size * int delta - floating search stopping constraint 0 - full search (the procedure will not stop after reaching dimension d; SFFS will reach n, SFBS will reach 0) delta>0 - SFFS will float until dimension d+delta is reached, SFBS will float until d-delta is reached -1 - the value of delta limit is computed during the course of the algorithm by averaging the length of backtracking -2 - the value of delta limit is set during the course of the algorithm as the maximum length of backtracking * int r - generalization level and direction of search +1 - classical SFFS -1 - classical SFBS r>1 - generalized SFFS with r as generalization level r<-1 - generalized SFBS with -r as generalization level * TSubset *bset - pointer to a structure for storing results (see its definition later) * int detail - textual output detail level (use NOTHING=0 or STANDARD=2) definitions (not all of them are probably needed, this is a copy of a part of F.S.Toolbox header file) // how often should the informational percentage be estimated #define PERCENTDETAIL 5 #define SECONDS 2 // output types #define NOTHING 0 #define PERCENT 1 #define STANDARD 2 #define FULL 6 #define GRAPHICS 8 #define DELTAMUL 1.0 // a multiplier of estimated delta #define DELTAADD 1 // a constant to be added to estimated delta #define SAFEUP 5e300 /* double overflow limit */ #define SAFEDOWN 5e-300 /* double underflow limit */ #define SAFEXP 1000 /* double exponent limit */ #define FREE(x,p) { free( x ); x = NULL; } typedef struct { int subsetsize; int *featureset; double critvalue; char dobavypoctu[10];} TSubset; /* after the procedure ends, this contains: subsetsize - final subset size featureset - a field containing indexes of selected features (begins by 0) critvalue - criterion value corresponding to the selected subset dobavypoctu - a string containing length of computation (in form "hh:mm:ss") */ - in fact the TSubset structure is filled only once at the end of floating search algorithm. Note that after the full search (when delta=0) you may find best subsets and corresponding criterion values for all dimensions stored in local structures "globalbestset" and "globalbestvalue" /************************* HERE STARTS THE CODE *******************************/ int FloatSearch(int n, int d, int delta, int r, TSubset *bset, int detail) { /* a non-redundand coding of subset configurations is used. For easier understanding imagine our goal is to find a subset by exhaustive search, when d=5 and n=12 - initial configuration is 111110000000 (actually stored in "bin" field) - in every step: a) find the leftmost block of 1's b) shift its rightmost 1 to the right c) shift the rest of this block to the left boundary (if it is not there) - this algorithm generates increasingly all binary representations of subsets - in context of floating search this algorithm is used for computation of generalized steps (in case of simple SFFS and simple SFBS only single-feature configurations are tested) - for purposes of floating search more identifiers than 0 and 1 are used to identify temporarily freezed features etc. (2,-1) - because of possibility to exchange meanings of 0 and 1 it was suitable to incorporate both forward and backward versions of floating search into one procedure */ int *bin; /* of size n, stores 0/1 information on currently selected features */ int *index; /* of size d, it is computed from bin, stores indexes of selected features */ int *bestset; double bestvalue; /* best subset */ int *globalbestset; double *globalbestvalue; /* so-far best subsets in all dimensions */ int wasthebest; /* indicates, if a better subset has been found during last step*/ double value; int sumrint; int i; int sumr; /* current subset size */ int zmenasumr; /* how to change sumr (when changing direction of search): -2,-1,+1,+2 steps */ int rr; int pom; int beg,piv; /* beg - beginning of block of identifiers, piv - "pivot" - last identifier in a block */ int stopex; /* identifies end of internal exhaustive search */ int stopfloat; /* identifies end of it all */ int stopfloatmez; /* identifies the dimension, for which the algorithm should end */ int id0=0,id2=2; /* these identifiers (0 and 2) are exchanged in case of backward search */ int sbs=0; /* 0=sfs, 1=sbs current search direction*/ int vykyv=0; // stores current backtracking depth (+forward,-backward) float vykyvmez=0.0; // predicted delta estimate int vykyvcount=0; // number of direction changes (needed for delta averaging) int sfbs=0; /* 0=sffs, 1=sfbs main search direction */ int error=0; long globcit/*,cit*/,kombcit; int timcet=false; time_t tbegin,telp,tact,tlast; /* for measuring computational time only */ tbegin=time(NULL); tlast=tbegin; if(r<0) { /* indicates SFBS, first stage will be SBS */ sfbs=1; sbs=1; id0=2; id2=0; r=-r; if(delta==0) stopfloatmez=1; else if(delta>0) {stopfloatmez=d-delta; if(stopfloatmez<1) stopfloatmez=1;} // for delta -1 and -2, stopfloatmez will be set later } else { /* indicates SFFS, first stage will be SFS */ if(delta==0) stopfloatmez=n; else if(delta>0) {stopfloatmez=d+delta; if(stopfloatmez>n) stopfloatmez=n;} // for delta -1 and -2, stopfloatmez will be set later } vykyv=0; vykyvmez=0.0; vykyvcount=0; if((d<1)||(d>n)){return(24);} /* nothing to search for */ if((r<1)||(r>=n)||((!sfbs)&&(r>=d))||((sfbs)&&(r>=n-d))){return(25);} /* no sense */ if(n<2){return(30);} if((bin=(int *)SafeAlloc((long)(n+1)*(long)sizeof(int),1,"bin","FloatSearch"))==NULL) {return(3);} if((index=(int *)SafeAlloc((long)n*(long)sizeof(int),1,"index","FloatSearch"))==NULL) {FREE(bin,FloatSearch) return(3);} i