Artifact of #4

Code

// Forest-RI (Breiman 2001, random input selection) on UCI Breast Cancer Wisconsin (Original), 699 cases (16 with a
// missing Bare Nuclei value). Protocol of the 'Selection' column of Table 2: 10% random hold-out (N/10 test cases),
// two forests of 100 fully grown trees (F=1 and F=int(log2 9)+1=4), test error of the forest with the lower
// out-of-bag error (ties -> F=1), 100 repetitions averaged. One such average = one 'seed'.
// mode drop: the 16 incomplete cases are removed (683 left). mode median: the missing value is replaced by the
// column median (=1) (699 cases). Own xorshift64 RNG, majority vote, Gini splits on integer thresholds.
// Data are embedded: 9 features (1..9, A=10, X=missing) then class (1 = malignant).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#define D 9
static const char*DATA="5111213110;54457A3210;3111223110;6881343710;4113213110;8AA87A9711;11112A3110;2121213110;2111211150;4211212110;1111113110;2111212110;5333234411;1111233110;875A795541;7464614311;4111212110;4111213110;A7764A4121;6111213110;732A5A5441;A553677A11;3111212110;84512X7311;1111213110;5234273611;3211112110;5111212110;2111212110;1131211110;3111112110;2111213110;A773857431;2112213110;3121212110;2111212110;AAA8618911;6211117110;54492A5611;2533677511;66696X7810;A431336521;6AA28A7331;5656A13111;AAA4818A11;1111212120;3774494811;1111212110;4113213110;7872483821;9581232151;5334243411;A362354A21;5558A87371;A556887111;A663453611;8AA1363911;8241515441;52316A5111;9552225111;5355334A11;1111222110;9AA1A83311;6341523911;1111212110;A4213243A1;4111213110;53418A4911;8383498981;1111213210;5131212110;6A28A278A1;1332217210;945A6A4811;A641343231;1121224210;1141212110;5312212110;3111233110;2111312110;2221117110;4112212110;5211213110;3111227110;3578897A71;5A61A44AA1;3364584411;36665A6831;4111213110;2112312110;1111213110;3112211110;4111213110;1111212110;2111213110;1111213110;2112211110;5111213110;9692A629A1;756A5A7941;A351A53A21;2344252511;4121213110;8231637111;AAAAA18881;7344333271;AAA82A4111;168A8A5711;1111212310;6544397831;1312225320;8643593111;A33A2A7331;AAA3A88111;3321233110;1111251110;8331223210;455A4A7581;1111431110;3211223110;1122213110;4211223110;AAA2AA5331;53518A5311;5467978A11;1111212110;75374A7551;3111213110;83545A1621;1111A11110;5131212110;2111213110;5A8A8A3631;3111212210;3111312110;5111223310;4111212110;3111211110;4121212110;11111X2110;3111211110;2111211110;9554454331;1111251110;2111212110;11312X2110;3452684111;1111322110;3113815810;8874AA7871;1111113110;72416A5431;AA86458A11;4111231110;1111211110;55563A3111;1221212110;2111213110;11213X1110;99A36A7A61;A7745A5721;4111213210;3111213110;1112131170;51112X3110;4111223210;56788A3A31;A8AA6131A1;3111213110;1112111110;3111211110;1111213110;1111212110;6AAA8AAA71;86543A6111;5877AA5711;2111213110;5AA3815A31;4111213110;53336A3111;1111113110;1111211110;6111213110;58885A7811;87644A5111;2111113110;1586587A11;A56A6A77A1;584A589A11;1231213110;AAA8687A11;75AAAA4A31;5111212110;1111213110;3111213110;4111213110;8445477820;5114213110;1111211110;3111212110;97755A7831;A884AA8111;1111213110;5111213110;1111213110;5AA96A7A51;AA93753511;1111113110;1111113110;5111113110;8AAA5A8A61;8A88487711;1111213110;AAAA7A7A41;AAAA3AA611;8787555A21;1111212110;1111213110;6A77648A21;6131213110;1112213110;A643AA9A11;4113152111;7563387411;A5563A7921;1111212110;A5744A8911;8995357711;1111113110;AAA3AA9A11;7474377611;6875688921;8463314310;A4555A4111;3321313610;31412X3110;A8828A48A1;9885624A41;8AA8693AA1;A4323A5321;5133222310;3113113110;2111213110;1111255110;1111213110;5112223110;8AA85A7811;8441293311;4111213610;31112X3110;1221211110;A44A2A5331;63353A3530;6AA28A7331;9AA1A83311;56624A3611;3111211110;3111212110;3111213110;5771583410;A58A3A5131;5AA6AAA651;88945A7811;A44A6A5511;794AA35331;5141213210;AA633A4321;33523A7111;A882348781;1111213110;84713A3921;5111213110;33523A7111;7241343311;3111213210;31312X2110;3111212110;1111212110;1111213110;A573373381;3111213110;2112213110;143A4A5611;A4612A5311;745A2A3821;8AAA8AA731;AAAAAA4AA1;3111312110;6131455A11;56686A4A41;1111211110;1111213110;88812X6A11;A4462A2311;11112X2110;55786A7411;5343454710;54312X2310;8211511110;91264A7721;84A5447A11;1111213110;AAA79A7AA1;1111213110;83493A3311;A8444A3A41;1111213110;1111213110;7876438841;3111255110;2111312110;1111211110;864AA13511;1111211110;1111112110;46567X4910;55525A4311;6878688911;1111513110;4444657310;76325A7461;31112X3110;3111213110;546A2A4111;1111213110;3221212310;A1112A5411;1111212110;8A32643A11;A4645A7111;A472286111;5111213120;5222212210;54664A4311;86733A3421;1111211110;65584A3411;1111213110;1111112110;85552A4311;A3312A7611;1111213110;2111211110;1111211110;7648AA9531;1111211110;5222311310;1111111310;344A513311;4235387611;5113211110;2111213110;3453734610;27AA7A4941;1111212110;4111312210;5331333331;8AA7AA7381;8A53844A31;A354373531;6AAAAA8AA1;3A3A6A5141;3221432110;4442232110;2111213110;2111212110;6AAA8A7A71;588A5A8A31;1131211110;1131112110;4321312110;1131211110;4121212110;5112212110;3121212110;1111211110;1111212110;1111112110;3114312210;5341413110;1111211110;A6364A7841;3222213210;2111211110;2111211110;3322311230;76632A7111;5332313110;2111212210;5111322210;1112212110;A8743A7911;3111212110;1111111110;1231212110;3111212110;3111213110;4111211110;3211212210;1231211110;3A87699381;3111211110;5331212110;3111241110;1213211210;1111212110;4221212110;1111212110;2322223110;3121212110;1111212110;11111X2110;AAA6848511;5121213110;85623A6611;3326333510;8785AA7211;1111212110;5222223220;2311511110;3223233110;AAA7AA8211;4331213310;5131212110;3111211110;9AAAAAAA11;5361211110;8782425A11;1111212110;2111212110;1311212210;5113413210;5111212210;3223211110;6975584210;A8A13A5111;AAA1612811;4111211110;4133211110;5111211110;A43A4AA111;5224241110;1113231110;1111221110;5116312110;2111211110;1111211110;5111211110;1111111110;57986A8A11;4113112110;5111211110;3113211110;45586AA711;2311311110;A221261121;A6585A8611;889663AA11;5121211110;5131211110;5113211110;3111251110;6113211110;4111211210;4111211110;A987647A31;A6624A9711;66654A7621;4111211110;1121212110;3111112110;6113211110;6111111110;4111211110;5111211110;3111211110;4121211110;4111211110;5211211110;487A4A7511;5111111110;5324211110;9AAAA5AAA1;87855A9A11;5121211110;1113131110;3111112110;AAAA6A8151;364A333411;6321344111;1111211110;58943A7111;4111112110;5AAA6A6521;512A452110;3111112110;1111111110;4211211110;4111212110;4111212110;6111213110;4111212110;4112212110;4111213110;1111211110;3311211110;8AAA754871;1111241110;5111211110;2111211110;1111211110;5111212110;5111211110;3111112110;667A3A8A21;4A473A9A11;1111111110;1111112110;3122211110;47834A9111;1111311110;4111311110;A454357311;756A4A5311;3111212110;3112211110;4111211110;4111213110;6132211110;4111112110;74434A6911;4221212110;1111113110;3111212110;2111212110;1132213110;5111213110;5121213110;4111212110;6111212110;5111222110;3111211110;5311211110;4111212110;2132212110;5111212110;6AAA4A7A11;2111111110;3111111110;7837457821;3111212110;1111213110;3222214210;4421252120;3111211110;4311214810;5222112110;5113211110;2111212110;5111212110;5111213110;5111213110;1111213110;3111212110;4111213210;57AA5AAA11;3121213110;4111232110;84416A2521;AA8A65A311;8A448A8211;76A53A9A21;3111212110;1111212110;A973427711;5121213110;5111212110;1111212110;1111212110;1111213110;5121212110;57A65A7511;6A554A6A11;3111211110;5116311110;1111211110;8AAA6AAA11;5111212210;9889634111;5111211110;4A8541A111;25764A7611;A3453A4111;5121211110;48634A7111;5111212110;4121212110;5131213110;3111212110;5241111110;3111212110;1111112110;4111212110;5468418A11;53285A8121;A5A3587831;4112211110;1111211110;5AAAAAA111;5111211110;A43A3A7121;5AAA528511;8AAA6AAAA1;2311212110;2111112110;4131212110;3111212110;11111X1110;4111212110;5111212110;3111212110;6333326110;7123212110;1111211110;5112112110;3131341110;4665767731;2111251110;2111211110;4111211110;6231211110;5111212110;1111211110;8744535A11;3111211110;3141211110;AA7871AA31;4243222110;4111211110;5113211110;4113211110;3111212110;3111212110;1111211110;2111211110;3111212110;1221211110;1113211110;5AAAA2AAA1;3111212110;3112341110;1213212110;5111212210;4111212110;3111213110;3111212110;5111212110;5451813610;78873A7231;1111211110;1111212110;4111213110;1131212110;1131212110;3113212110;1111211110;5222211120;3111213110;5741617A31;5AA8557A11;3A78587411;3212213110;2111213110;5321311110;1111212110;4141211110;1121212110;5111211110;1111211110;2111211110;AAAA5AAA71;5AAA4A5631;5111213210;1111211110;1111211110;1111211110;1111211110;3111212310;4111211110;1111211180;1113211110;5AA5454411;3111211110;3111212120;3111321110;2111211110;5AA3738A21;486434A611;488545A411";
#define MAXN 700
#define NT 100
static int X[MAXN][D], Y[MAXN], N;
static uint64_t s;
static uint64_t rnd(){ s^=s<<13; s^=s>>7; s^=s<<17; return s; }
static int below(int k){ return (int)(rnd()%(uint64_t)k); }
typedef struct { int f, thr, l, r, leaf; } Node;
typedef struct { Node *nd; int n, cap; } Tree;
static int newnode(Tree*t){ if(t->n==t->cap){ t->cap*=2; t->nd=realloc(t->nd,t->cap*sizeof(Node)); } return t->n++; }
static int grow(Tree*t,int*idx,int m,int F){
  int me=newnode(t); int c1=0; for(int i=0;i<m;i++) c1+=Y[idx[i]];
  if(c1==0||c1==m){ t->nd[me].leaf=(c1==m); t->nd[me].f=-1; return me; }
  int cand[D]; int nc=D; for(int i=0;i<D;i++) cand[i]=i;
  int bf=-1,bt=0; double bs=1e300;
  while(nc>0 && bf<0){
    int pool[D]; memcpy(pool,cand,nc*sizeof(int)); int np=nc; int feats[D]; int nfe=0;
    int take=F<np?F:np;
    for(int q=0;q<take;q++){ int j=below(np); feats[nfe++]=pool[j]; pool[j]=pool[--np]; }
    for(int a=0;a<nfe;a++){
      int f=feats[a]; int c[11][2]; memset(c,0,sizeof c);
      for(int i=0;i<m;i++) c[X[idx[i]][f]][Y[idx[i]]]++;
      int nvals=0; for(int v=1;v<=10;v++) if(c[v][0]+c[v][1]) nvals++;
      if(nvals<2) continue;
      int t0=0,t1=0; for(int v=1;v<=10;v++){t0+=c[v][0];t1+=c[v][1];}
      int l0=0,l1=0; int seen=0;
      for(int v=1;v<=10;v++){
        if(!(c[v][0]+c[v][1])) continue;
        seen++; if(seen==nvals) break;
        l0+=c[v][0]; l1+=c[v][1]; int L=l0+l1,R=m-L; int r0=t0-l0,r1=t1-l1;
        double sc=L*(1-((double)l0/L)*((double)l0/L)-((double)l1/L)*((double)l1/L))+R*(1-((double)r0/R)*((double)r0/R)-((double)r1/R)*((double)r1/R));
        if(sc<bs-1e-12){bs=sc;bf=f;bt=v;}
      }
    }
    if(bf<0){ // none could split: drop tried features
      int nn=0; for(int i=0;i<nc;i++){int in=0; for(int a=0;a<nfe;a++) if(feats[a]==cand[i]) in=1; if(!in) cand[nn++]=cand[i];} nc=nn;
    }
  }
  if(bf<0){ t->nd[me].leaf=(c1*2>m); t->nd[me].f=-1; return me; }
  int lo=0; int *tmp=malloc(m*sizeof(int)); int hi=m;
  for(int i=0;i<m;i++){ if(X[idx[i]][bf]<=bt) tmp[lo++]=idx[i]; else tmp[--hi]=idx[i]; }
  memcpy(idx,tmp,m*sizeof(int)); free(tmp);
  t->nd[me].f=bf; t->nd[me].thr=bt;
  int l=grow(t,idx,lo,F); int r=grow(t,idx+lo,m-lo,F);
  t->nd[me].l=l; t->nd[me].r=r; return me;
}
static int pred(Tree*t,int*x){ int k=0; while(t->nd[k].f>=0) k=(x[t->nd[k].f]<=t->nd[k].thr)?t->nd[k].l:t->nd[k].r; return t->nd[k].leaf; }
int main(int argc,char**argv){
  int median=!strcmp(argv[1],"median"); int seed0=0,ns=atoi(argv[2]);
  int N0=0; int tmpX[MAXN][D],tmpY[MAXN],mm[MAXN];
  { const char*q=DATA; while(*q){ int has=0; for(int j=0;j<D;j++,q++){ if(*q=='X'){tmpX[N0][j]=-1;has=1;} else if(*q=='A') tmpX[N0][j]=10; else tmpX[N0][j]=*q-'0'; } tmpY[N0]=*q-'0'; q++; if(*q==';') q++; mm[N0]=has; N0++; } }
  N=N0;
  // median of Bare Nuclei (col 5)
  int cnt[11]={0},tot=0; for(int i=0;i<N;i++) if(tmpX[i][5]>0){cnt[tmpX[i][5]]++;tot++;}
  int acc=0,med=0; for(int v=1;v<=10;v++){acc+=cnt[v]; if(acc*2>=tot){med=v;break;}}
  int n=0; for(int i=0;i<N;i++){
    if(mm[i]&&!median) continue;
    for(int j=0;j<D;j++) X[n][j]=tmpX[i][j]<0?med:tmpX[i][j];
    Y[n]=tmpY[i]; n++;
  }
  N=n; 
  double acc1=0,acc2=0;
  for(int sd=seed0;sd<seed0+ns;sd++){
    s=0x9E3779B97F4A7C15ULL*(sd+1); for(int i=0;i<20;i++) rnd();
    double sum=0; int pick1=0; int R=100;
    for(int r=0;r<R;r++){
      int order[MAXN]; for(int i=0;i<N;i++) order[i]=i;
      for(int i=N-1;i>0;i--){int j=below(i+1);int t=order[i];order[i]=order[j];order[j]=t;}
      int k=N/10; int *test=order,*train=order+k; int ntr=N-k;
      double oob[2],te[2]; int Fs[2]={1,(int)(__builtin_log2(D))+1};
      for(int fi=0;fi<2;fi++){
        int F=Fs[fi]; int tv[MAXN]={0}; int ov[MAXN]={0},oc[MAXN]={0};
        for(int t=0;t<NT;t++){
          int boot[MAXN]; char in[MAXN]={0};
          for(int i=0;i<ntr;i++){int b=train[below(ntr)]; boot[i]=b; in[b]=1;}
          Tree tr; tr.cap=64; tr.n=0; tr.nd=malloc(tr.cap*sizeof(Node));
          grow(&tr,boot,ntr,F);
          for(int a=0;a<k;a++) tv[a]+=pred(&tr,X[test[a]]);
          for(int i=0;i<ntr;i++){int c=train[i]; if(!in[c]){ov[c]+=pred(&tr,X[c]);oc[c]++;}}
          free(tr.nd);
        }
        int eo=0,no=0; for(int i=0;i<ntr;i++){int c=train[i]; if(oc[c]){no++; if((ov[c]*2>oc[c])!=Y[c]) eo++;}}
        int et=0; for(int a=0;a<k;a++) if((tv[a]*2>NT)!=Y[test[a]]) et++;
        oob[fi]=(double)eo/no; te[fi]=(double)et/k;
      }
      int pick=(oob[1]<oob[0]); pick1+=pick; sum+=te[pick];
    }
    printf("%s seed %d mean test error %.3f%% (F=4 selected in %d of %d reps)\n",argv[1],sd,100*sum/R,pick1,R); acc1+=100*sum/R; acc2+=(100*sum/R)*(100*sum/R);
  }
  { double m=acc1/ns, v=(acc2-ns*m*m)/(ns-1); printf("%s: n=%d cases, %d seeds, mean %.3f%%, sd over seeds %.3f\n",argv[1],N,ns,m,v>0?__builtin_sqrt(v):0); }
}

Expected output

drop seed 0 mean test error 2.706% (F=4 selected in 17 of 100 reps)
drop seed 1 mean test error 2.574% (F=4 selected in 5 of 100 reps)
drop seed 2 mean test error 2.279% (F=4 selected in 7 of 100 reps)
drop seed 3 mean test error 2.382% (F=4 selected in 22 of 100 reps)
drop seed 4 mean test error 2.191% (F=4 selected in 15 of 100 reps)
drop seed 5 mean test error 2.618% (F=4 selected in 12 of 100 reps)
drop seed 6 mean test error 2.838% (F=4 selected in 13 of 100 reps)
drop seed 7 mean test error 2.574% (F=4 selected in 15 of 100 reps)
drop seed 8 mean test error 2.574% (F=4 selected in 13 of 100 reps)
drop seed 9 mean test error 2.779% (F=4 selected in 10 of 100 reps)
drop seed 10 mean test error 2.691% (F=4 selected in 7 of 100 reps)
drop seed 11 mean test error 2.544% (F=4 selected in 8 of 100 reps)
drop seed 12 mean test error 2.529% (F=4 selected in 12 of 100 reps)
drop seed 13 mean test error 2.985% (F=4 selected in 14 of 100 reps)
drop seed 14 mean test error 2.574% (F=4 selected in 18 of 100 reps)
drop seed 15 mean test error 2.338% (F=4 selected in 11 of 100 reps)
drop seed 16 mean test error 2.618% (F=4 selected in 12 of 100 reps)
drop seed 17 mean test error 2.647% (F=4 selected in 17 of 100 reps)
drop seed 18 mean test error 2.662% (F=4 selected in 17 of 100 reps)
drop seed 19 mean test error 2.941% (F=4 selected in 14 of 100 reps)
drop seed 20 mean test error 2.868% (F=4 selected in 15 of 100 reps)
drop seed 21 mean test error 3.176% (F=4 selected in 23 of 100 reps)
drop seed 22 mean test error 2.838% (F=4 selected in 13 of 100 reps)
drop seed 23 mean test error 2.824% (F=4 selected in 20 of 100 reps)
drop seed 24 mean test error 2.985% (F=4 selected in 15 of 100 reps)
drop seed 25 mean test error 2.632% (F=4 selected in 11 of 100 reps)
drop seed 26 mean test error 2.603% (F=4 selected in 15 of 100 reps)
drop seed 27 mean test error 2.647% (F=4 selected in 12 of 100 reps)
drop seed 28 mean test error 2.721% (F=4 selected in 17 of 100 reps)
drop seed 29 mean test error 2.618% (F=4 selected in 11 of 100 reps)
drop seed 30 mean test error 2.412% (F=4 selected in 15 of 100 reps)
drop seed 31 mean test error 2.588% (F=4 selected in 19 of 100 reps)
drop seed 32 mean test error 2.529% (F=4 selected in 15 of 100 reps)
drop seed 33 mean test error 2.721% (F=4 selected in 12 of 100 reps)
drop seed 34 mean test error 2.956% (F=4 selected in 17 of 100 reps)
drop seed 35 mean test error 2.662% (F=4 selected in 16 of 100 reps)
drop seed 36 mean test error 2.676% (F=4 selected in 14 of 100 reps)
drop seed 37 mean test error 2.926% (F=4 selected in 12 of 100 reps)
drop seed 38 mean test error 2.500% (F=4 selected in 14 of 100 reps)
drop seed 39 mean test error 2.529% (F=4 selected in 10 of 100 reps)
drop: n=683 cases, 40 seeds, mean 2.661%, sd over seeds 0.204
median seed 0 mean test error 2.870% (F=4 selected in 2 of 100 reps)
median seed 1 mean test error 3.116% (F=4 selected in 5 of 100 reps)
median seed 2 mean test error 2.551% (F=4 selected in 7 of 100 reps)
median seed 3 mean test error 2.957% (F=4 selected in 8 of 100 reps)
median seed 4 mean test error 2.783% (F=4 selected in 6 of 100 reps)
median seed 5 mean test error 3.087% (F=4 selected in 5 of 100 reps)
median seed 6 mean test error 2.725% (F=4 selected in 3 of 100 reps)
median seed 7 mean test error 2.841% (F=4 selected in 7 of 100 reps)
median seed 8 mean test error 3.145% (F=4 selected in 4 of 100 reps)
median seed 9 mean test error 3.014% (F=4 selected in 6 of 100 reps)
median seed 10 mean test error 2.942% (F=4 selected in 2 of 100 reps)
median seed 11 mean test error 2.812% (F=4 selected in 4 of 100 reps)
median seed 12 mean test error 3.014% (F=4 selected in 10 of 100 reps)
median seed 13 mean test error 2.754% (F=4 selected in 2 of 100 reps)
median seed 14 mean test error 2.971% (F=4 selected in 7 of 100 reps)
median seed 15 mean test error 3.232% (F=4 selected in 5 of 100 reps)
median seed 16 mean test error 2.855% (F=4 selected in 4 of 100 reps)
median seed 17 mean test error 2.957% (F=4 selected in 7 of 100 reps)
median seed 18 mean test error 3.072% (F=4 selected in 3 of 100 reps)
median seed 19 mean test error 2.710% (F=4 selected in 5 of 100 reps)
median seed 20 mean test error 2.667% (F=4 selected in 2 of 100 reps)
median seed 21 mean test error 2.913% (F=4 selected in 4 of 100 reps)
median seed 22 mean test error 2.783% (F=4 selected in 4 of 100 reps)
median seed 23 mean test error 3.217% (F=4 selected in 5 of 100 reps)
median seed 24 mean test error 2.710% (F=4 selected in 5 of 100 reps)
median seed 25 mean test error 3.101% (F=4 selected in 8 of 100 reps)
median seed 26 mean test error 2.783% (F=4 selected in 4 of 100 reps)
median seed 27 mean test error 2.942% (F=4 selected in 4 of 100 reps)
median seed 28 mean test error 2.638% (F=4 selected in 4 of 100 reps)
median seed 29 mean test error 2.957% (F=4 selected in 5 of 100 reps)
median seed 30 mean test error 2.841% (F=4 selected in 8 of 100 reps)
median seed 31 mean test error 2.783% (F=4 selected in 5 of 100 reps)
median seed 32 mean test error 2.768% (F=4 selected in 6 of 100 reps)
median seed 33 mean test error 3.130% (F=4 selected in 10 of 100 reps)
median seed 34 mean test error 2.710% (F=4 selected in 6 of 100 reps)
median seed 35 mean test error 3.072% (F=4 selected in 5 of 100 reps)
median seed 36 mean test error 2.551% (F=4 selected in 2 of 100 reps)
median seed 37 mean test error 2.797% (F=4 selected in 4 of 100 reps)
median seed 38 mean test error 2.826% (F=4 selected in 7 of 100 reps)
median seed 39 mean test error 2.783% (F=4 selected in 7 of 100 reps)
median: n=699 cases, 40 seeds, mean 2.884%, sd over seeds 0.175

Verifications (0)

Nobody has run it yet.