Kaggle Digit-recognizer

3/3/2017来源:C/C++教程人气:1628

寒假读了读统计学习方法,去Kaggle上试了一下Digit-recognizer,发现python用的还是不够熟,写到一半就炸毛了= =还是换成C++实现了。。。更一篇纪念ML入门第一个cpp吧

题目是给出一大坨0~9图像的灰度图,然后识别下会有图里面的数字是多少。图片有784个像素点。

第一次上手,所以用了最简单的KNN,听信了网上的谣言,写了个KD-Tree,然后跑一次要3个多小时(黑人???.jpg)那我写个毛线的KD-Tree啊,想了想数据感觉这就是在逗我,和直接暴力跑没什么区别。 瞎调调参K=13时候效果比较好,识别率0.96414。

#include <bits/stdc++.h> using namespace std; const int N = 42000; const int M = 785; const int maxn = 28000; int n=N; int m=M-1; int k=13; struct Point { int v[M]; int dis; Point(){} Point(const Point& p) { for(int i=0;i<M;i++)v[i]=p.v[i]; dis=p.dis; } }tre[N],ar[maxn]; bool Operator<(Point a,Point b) { return a.dis<b.dis; } int label[maxn]; int sq(int x) { return x*x; } int dis(Point a,Point b) { int re=0; for(int i=1;i<=m;i++) re+=sq(a.v[i]-b.v[i]); return re; } int than; bool cmp(Point a,Point b) { return a.v[than]<b.v[than]; } void build(int l,int r,int split) { if(l>r)return; int mid=(l+r)/2; if(split>m)split-=m; than=split; nth_element(tre+l,tre+mid,tre+r+1,cmp); build(l,mid-1,split+1); build(mid+1,r,split+1); } PRiority_queue<Point> q; void que(int l,int r,Point p,int split) { if(l>r)return; if(split>m)split-=m; int mid=(l+r)/2; int d=dis(tre[mid],p); tre[mid].dis=d; if(l==r) { if(q.size()<k || q.top().dis>d) { q.push(tre[mid]); if(q.size()>k)q.pop(); } return; } int t=p.v[split]-tre[mid].v[split]; if(t<0) { que(l,mid-1,p,split+1); if(q.size()<k || q.top().dis>=t*t) { if(q.size()<k || q.top().dis>d) { q.push(tre[mid]); if(q.size()>k)q.pop(); } que(mid+1,r,p,split+1); } } else { que(mid+1,r,p,split+1); if(q.size()<k || q.top().dis>=t*t) { if(q.size()<k || q.top().dis>d) { q.push(tre[mid]); if(q.size()>k)q.pop(); } que(l,mid-1,p,split+1); } } } int work(int x) { que(0,n-1,ar[x],1); int c[10]={0}; while(!q.empty()) { c[q.top().v[0]]++; //printf("%d %d\n",q.top().dis,q.top().v[0]); q.pop(); } int now=0; for(int i=1;i<10;i++) if(c[i]>c[now]) now=i; return now; } int main() { long long be=time(0); FILE *fe=fopen("train.csv","r"); while(fgetc(fe)!='\n'); for(int i=0;i<n;i++) for(int j=0;j<m+1;j++) { char c; fscanf(fe,"%d%c",&tre[i].v[j],&c); //if(j>0)tre[i].v[j]=(tre[i].v[j]!=0); //printf("%d ",tre[i].v[j]); } build(0,n-1,1); fclose(fe); fe=fopen("test.csv","r"); while(fgetc(fe)!='\n'); FILE *fo=fopen("result13.csv","w"); int n=28000; for(int i=0;i<n;i++) for(int j=1;j<=m;j++) { char c; fscanf(fe,"%d%c",&ar[i].v[j],&c); //if(j>0)ar[i].v[j]=(ar[i].v[j]!=0); } fclose(fe); for(int i=0;i<n;i++) { label[i]=work(i); //printf("%d,%d %d\n",i+1,label[i],ar[i].v[0]); } fputs("ImageId,Label\n",fo); for(int i=0;i<n;i++) fprintf(fo,"%d,%d\n",i+1,label[i]); fclose(fo); long long en=time(0); printf("run time:%lld\n",en-be); return 0; }

时间有点久了= =都记不得自己写得什么了。。。然后我可能是极少数用C++写的奇葩?ACM后遗症啊,今年零散时间准备拿来捡一捡概率论,搞一搞python。