未分类 - 悲催的科学匠人 - 冷水's blog

KNN算法的实现

具体描述见machine learning in action

knn.h

/* knn.c */
struct KNN *KNNInit(int nvectors, int dim, int ngroup, int *ierr);
void KNNFree(struct KNN *knn, int *ierr);
double *KNNGetdata(struct KNN *knn, int ivec, int *ierr);
double KNNGetCoord(struct KNN *knn, int ivec, int icoord, int *ierr);
void KNNSetGroup(struct KNN *knn, int ivec, int group, int *ierr);
void KNNSetDataGroup(struct KNN *knn, int ivec, double *data, int group, int *ierr);
void KNNCalcScale(struct KNN *knn, int *ierr);
double KNNCalcDistance(struct KNN *knn, int ivec, double *mydata, int *ierr);
int KNNCalcGroup(struct KNN *knn, double *mydata, int k, int *ierr);

knn.c

#include <stdlib.h>
#include <math.h>
#include <stdlib.h>

struct KNN{
  int nvec;
  int dim;
  double *data;
  double *scale;
  int ngroups;
  int *group;   /* group ID (0,1,..., ngroups-1) for each vec*/
};



inline int KNNGetDataOffset(struct KNN *knn, int ivec)
{
  return ivec*knn->dim;
}

inline int KNNCheckIvec(struct KNN* knn, int ivec)
{
    if( ivec<0 || 1+ivec>knn->nvec) 
      return 1;
    else
      return 0;
}


struct KNN*  KNNInit(int nvectors, int dim, int ngroup, int *ierr)
{
  double  *data, *scale;
  int *group,  i;

  if(nvectors<1) {*ierr = 1; puts("KNNInit, error, nvectors<1");  return NULL; }
  if(dim<1) {*ierr= 2; puts("KNNInit, error, dim<1"); return NULL; }
  if(ngroup<2) {*ierr=4; puts("KNNInit, error, ngroup<2"); return;  } 

  data = (double*) calloc(nvectors*dim, sizeof(double));
  if (data==NULL) {*ierr = 5; puts("KNNInit, error, calloc knn->data fail"); return; }

  group = (int*) calloc(nvectors, sizeof(int));
  if(group==NULL) {*ierr=6; puts("KNNInit, error, calloc knn->group fail"); return;}
  for(i=0;i<nvectors;i++) group[i] = -1;

  scale = (double*) calloc(dim, sizeof(double));
  if(scale==NULL) {*ierr=7; puts("KNNInit, error, calloc knn->scale fail"); return;}
  
  
  struct KNN* knn = (struct KNN*)calloc(1,sizeof(struct KNN));
  if(knn==NULL) {*ierr=999; puts("KNNInit, error, calloc KNN fail"); return NULL;}

  knn->data = data;
  knn->group = group;
  knn->scale = scale;

  knn->nvec= nvectors;
  knn->dim = dim;
  knn->ngroups = ngroup;

  ierr = 0;
  return knn;
}

void KNNFree(struct KNN* knn, int* ierr)
{
  if(knn==NULL) return;
  if(knn->data) free(knn->data);
  if(knn->group) free(knn->group);
  free(knn);
}



double* KNNGetdata(struct KNN *knn, int ivec, int *ierr)
{
   *ierr = KNNCheckIvec(knn,ivec);
   if(*ierr) {puts("KNNGetData, irror, Wrong ivec");  return;}

   return knn->data + KNNGetDataOffset(knn, ivec);
}


double KNNGetCoord(struct KNN* knn, int ivec, int icoord, int* ierr)
{
  double *data;
  data = KNNGetdata(knn, ivec, ierr);
  if(*ierr) return 0;
  if(icoord<0 || icoord>=knn->dim) {
     puts("KNNGetCoord, error, wrong icoord"); *ierr= 2; return 0;
  }
  *ierr = 0;
  return data[icoord];
}



void KNNSetGroup(struct KNN* knn, int ivec, int group, int* ierr)
{
  *ierr =  KNNCheckIvec(knn,ivec);  if(*ierr) {puts("KNNSetGroup, error, Wrong ivec");  return;}
  *ierr = group<0 || group>=knn->ngroups;   if(*ierr) {puts("KNNSetGroup, error, Wrong group ID (should be [0,..,ngroups-1])");  return;}

  knn->group[ivec] = group;
  *ierr = 0;
  return; 
}


void KNNSetDataGroup(struct KNN *knn,int ivec, double *data, int group, int* ierr)
{
   int i;
   double *knndata = KNNGetdata(knn, ivec, ierr);
   if(*ierr) return;

   for(i=0; i<knn->dim; i++)  knndata[i] = data[i];

   KNNSetGroup(knn, ivec, group, ierr);
   if(*ierr) return;

   *ierr = 0;
   return;
}

static int KNNIsDataFilled(struct KNN* knn)
{
   int i;
   for(i=0; i<knn->nvec; i++) if(knn->group[i]==-1)  return 0;
   return 1;
}

void KNNCalcScale(struct KNN* knn, int *ierr)
{
   int i,d;
   if(!KNNIsDataFilled(knn)) {  puts("KNNCalcScale, error, data is not filled");  return; }

   for(d=0;d<knn->dim;d++){
     double xmax,xmin;
     xmin = KNNGetCoord(knn, 0, d, ierr);
     xmax = xmin;
     for(i=1; i<knn->nvec; i++){
       double f;
       f = KNNGetCoord(knn, i, d, ierr);
       if(xmax<f) xmax = f;
       if(xmin>f) xmin = f;
     }
     if(xmax!=xmin) 
        knn->scale[d] = 1./((xmax-xmin)*(xmax-xmin));
     else
        knn->scale[d] = 1.0;
   }
}


double KNNCalcDistance(struct KNN *knn, int ivec, double *mydata, int *ierr)
{
  double *data=NULL, dist=0.0;
  int i;

  data = KNNGetdata(knn, ivec, ierr);  if(*ierr) {puts("KNNCalcDistance, error, KNNGetData fail"); return;}
  
  for(i=0;i<knn->dim;i++){
    dist += (mydata[i]-data[i]) * (mydata[i]-data[i]) * knn->scale[i];
  }
  *ierr = 0;
  return sqrt(dist);
}


static void make_list(double *dlist, int* idlist, int n,  int cid, double cdist)
{
   double dmax;
   int imax, i;
   dmax = dlist[0]; imax=0;

   for(i=1;i<n;i++){
     if(dlist[i]>dmax) {dmax=dlist[i]; imax=i;}
   }
   if(cdist>dmax) 
     return;
   else{
     dlist[imax] = cdist;
     idlist[imax]= cid;
   }
}


static int vote(struct KNN* knn, int *groups, int k)
{
   int *votes;
   int i, max=0;
   votes = (int*) calloc(knn->ngroups, sizeof(int));
   for(i=0;i<knn->ngroups;i++)  votes[i]=0;

   for(i=0; i<k; i++)
     votes[ groups[i] ] ++;
     
   for(i=1; i<knn->ngroups; i++) {
     if(votes[i]>votes[max]) max=i;
   }

   return max;
}


int KNNCalcGroup(struct KNN* knn, double *mydata, int k, int* ierr)
{
  double* dists;
  int*    vecid;
  int n;
  double dmax,dmin;
  int    imax,imin;
  dists = (double*) calloc(k, sizeof(double));
  if(dists==NULL) {*ierr=-1; puts("KNNCalcGroup, error, cannot allocate space for dists"); return;}
  
  vecid = (int*) calloc(k, sizeof(int));
  if(vecid==NULL) {*ierr=-1; puts("KNNCalcGroup, error, cannot allocate space for vecid"); return;}
  for(n=0;n<k;n++){
    dists[n] = -1.;
    vecid[n] = -1;
  }
  for(n=0;n<knn->nvec;n++){
    double cdist;
    cdist = KNNCalcDistance(knn, n, mydata, ierr);
    
    if(n==0){
      int l;
      for(l=0;l<k;l++) {
         dists[l] = cdist; dmax=cdist;dmin=cdist;
         vecid[l] = n;     imax=n;    imin=n;
      }
    }
    else{ 
      make_list(dists, vecid, k,  n, cdist);
    }
  }
  free(dists);
  
  for(n=0;n<k;n++) vecid[n] = knn->group[vecid[n]];
  n = vote(knn, vecid,k);
  free(vecid);
  return n;
}

测试手写数字识别的程序 digits.c

#include <stdio.h>

#include "knn.h"

#define NVEC 1934
#define DIM  1024
#define NGROUP 10
#define K 3

void InputData(struct KNN *knn)
{
  FILE* fp;
  int id=0, i, ndata[10]={188, 197, 194, 198, 185, 186, 194, 200, 179, 203};
  double mydata[DIM];
  int g, n, ierr;
  char fname[32];
  
  for(g=0;g<10;g++)
  for(n=0;n<=ndata[g];n++){
  
    double mydata[1024];
    sprintf(fname,"trainingDigits/%d_%d.txt", g,n);
    //puts(fname);
    fp = fopen(fname,"r"); 
    for(i=0;i<1024;i++){
      int d;
      fscanf(fp,"%1d",&d);
      mydata[i] = d;
    }
    
    KNNSetDataGroup(knn, id, mydata, g, &ierr);
    if(ierr!=0) puts("ERROR!!");
    id ++;
    fclose(fp);
  }
  printf("Read %d training data\n",id);
  
}


void Test(struct KNN *knn)
{

  FILE* fp;
  int id=0, i, ndata[10]={86, 96, 91, 84, 99, 99, 86, 95, 90, 88};
  double mydata[DIM];
  int g, n, ierr,score;
  char fname[32];
  
  for(g=0;g<10;g++)
  {
    score = 0;
    for(n=0;n<=ndata[g];n++){
  
      double mydata[1024];
      int ans;
      
      sprintf(fname,"testDigits/%d_%d.txt", g,n);
      fp = fopen(fname,"r");       
      for(i=0;i<1024;i++){
        int d;
        fscanf(fp,"%1d",&d);
        mydata[i] = d;
      }          
      fclose(fp);
    
      ans = KNNCalcGroup(knn, mydata, K, &ierr);
      if(ans==g) score ++;
      else{
         printf("                                 fail for %s\n",fname);
      }
    }
    
    printf("Digit %1d  score=%3d/%3d = %6.2f%%\n",
       g, score, ndata[g]+1,  100.*score/(ndata[g]+1.));
  }
   
}



int main(void)
{
   int ierr;
   struct KNN* knn;
   knn = KNNInit(NVEC,DIM,NGROUP, &ierr);
   if(ierr) {puts("can not KNNInit"); return; }

   InputData(knn);
   KNNCalcScale(knn, &ierr);

   Test(knn);
   KNNFree(knn, &ierr);
}

 

未分类 机器学习 knn Comments(5) 2014年7月06日 19:22

天津超级计算中心天河-1A在linux下登录VPN的方法解释

原文见此链接

https://vpn.nscc-tj.cn/svpn/cn/support/OperationGuide%28Chinese%29.htm

 

在ubuntu下设置时，遇到几个问题

1 jre6的安装。ubuntu不再首选支持sun java，而推荐使用openjdk，因此软件库中没有sun java。为了保证兼容，还是选sun java吧。安装方法参考 https://help.ubuntu.com/community/Java 中关于Orancle(Sun) Java 6的部分

 

2 Firefox中设置JNLP文件打开方式。初始Firefox中没有JNLP文件选项，没法设置。方法是，自己建立一个空文件，后缀名为jnlp。把它拖到firefox中，firefox会提示打开方法，选择javaws。然后到首选项的application中就可以看到JNLP了，把它按照说明设置即可。

 

3 22端口问题。vpn客户端要占用22端口，只好把本机的ssh服务停了 

4 root身份的问题。vpn客户端必须用root身份，但是在root环境下工作有风险。解决方法是，登录一个root桌面，登录好vpn之后，再切换登录一个普通用户桌面，就可以ssh到th-1a的三个登录节点了。

 

 

 

未分类 Comments(2) 2012年10月11日 20:30

一个有用的网页注释工具

http://webklipper.com

可以指定一个URL，它生成一个拷贝。然后可以在页面上做各种标记和注释。可以把注释版分享给别人浏览或者合作添加注释。这玩意还可以支持自行上载文件(pdf、图形和txt)进行注释。

缺点：

1 似乎标记的位置不是根据文本的内容来定位，而是根据网页区域的坐标。因此改变窗口大小后，标记位置就错了

2 pdf会被转成图片格式，不清楚。

 

不论如何，这玩意还是很好的。非常适合多人剖析源代码之类的活。

未分类 Comments(2) 2012年9月02日 20:14

Latex Listings Package 使用方法[ZZ]

转自 http://xavier.yo2.cn/articles/latex-listings-package-%E4%BD%BF%E7%94%A8%E6%96%B9%E6%B3%95.html

 

这里就不班门弄斧了，直接转载过来备忘好了。

转载自http://blog.linuxgem.org/lyanry/show/319.html

listings 是专用于代码排版的 LaTeX 宏包，可对关键词、注释和字符串等使用不同的字体和颜色或颜色，也可以为代码添加边框、背景等风格。

1 基本用法

下面给出一份用于排版 C 语言 HelloWorld 程序代码的完整的 LaTeX 文档：

\documentclass{article}
\usepackage{listings}
\begin{document}
\begin{lstlisting}[language=C]
int main(int argc, char ** argv)
{
printf("Hello world!\n");
return 0;
}
\end{lstlisting}
\end{document}

注意，要使用 listings 宏包提供的语法高亮，需要 xcolor 宏包支持。

4 添加边框

listings 宏包为代码边框提供了很多风格，大体可分为带有阴影的边框与圆角边框。这里仅仅给出一个阴影边框的示例，至于其它边框风格，可查阅 listings 宏包文档，里面给出了一些示例。

下面 LaTeX 源文档将为代码添加阴影边框，并将阴影设置为浅灰色：

\begin{lstlisting}[language={[ANSI]C}, keywordstyle=\color{blue!70}, commentstyle=\color{red!50!green!50!blue!50}, frame=shadowbox, rulesepcolor=\color{red!20!green!20!blue!20}]
int main(int argc, char ** argv)
{
printf("Hello world!\n") ;
return 0;
}
\end{lstlisting}
5 添加行号

很多时候需要对文档中的代码进行解释，只有带有行号的代码才可以让解释更清晰，因为你只需要说第 x 行代码有什么作用即可。如果没有行号，那对读者而言就太残忍了，他们不得不从你的文字叙述中得知行号信息，然后去一行一行的查到相应代码行。

listings 宏包通过参数 numbers 来设定行号，该参数的值有两个，分别是 left 与 right，表示行号显示在代码的左侧还是右侧。下面为带有边框的代码添加行号，并设置行号字体为 \tiny：

\begin{lstlisting}[language={[ANSI]C}, numbers=left, numberstyle=\tiny, keywordstyle=\color{blue!70}, commentstyle=\color{red!50!green!50!blue!50}, frame=shadowbox, rulesepcolor=\color{red!20!green!20!blue!20}]
int main(int argc, char ** argv)
{
printf("Hello world!\n") ;
return 0;
}
\end{lstlisting}
6 全局设置

上面所给的各个示例中，lstlisting 环境后面尾随了很多参数，要是每使用一次 lstlisting 环境就要设置这么多参数，那就没什么意思了。

可以使用 \lstset 命令在 LaTeX 源文档的导言区设定好 lstlisting 环境所用的公共参数，如下：

\documentclass{article}
\usepackage{listings}
\usepackage{xcolor}
\begin{document}
\lstset{numbers=left,
numberstyle=\tiny,
keywordstyle=\color{blue!70}, commentstyle=\color{red!50!green!50!blue!50},
frame=shadowbox,
rulesepcolor=\color{red!20!green!20!blue!20}
}
\begin{lstlisting}[language={[ANSI]C}]
int main(int argc, char ** argv)
{
printf("Hello world!\n") ;
return 0;
}
\end{lstlisting}
\end{document}

 

7 显示中文

listings 宏包默认是不支持包含中文字串的代码显示的，但是可以使用 “逃逸” 字串来显示中文。

在 \lstset 命令中设置逃逸字串的开始符号与终止符号，推荐使用的符号是左引号，即 “ `”

\lstset{numbers=left,
numberstyle=\tiny, keywordstyle=\color{blue!70}, commentstyle=\color{red!50!green!50!blue!50},
frame=shadowbox, rulesepcolor=\color{red!20!green!20!blue!20},
escapeinside=``}
……
\begin{lstlisting}[language={[ANSI]C}]
int main(int argc, char ** argv)
{
printf("`我爱中文`!\n") ;
return 0;
}
\end{lstlisting}

 

8 调整一下边距

listings 的代码框的宽度默认是与页芯等宽的，其上边距也过于小，可根据自己的审美观念适度调整一下。我通常是将代码框的左右边距设置为 2em，上边距为 1em，下边距采用默认值即可，所作设定如下：

\lstset{numbers=left, numberstyle=\tiny, 
keywordstyle=\color{blue!70}, 
commentstyle=\color{red!50!green!50!blue!50}, 
frame=shadowbox, 
rulesepcolor=\color{red!20!green!20!blue!20},escapeinside=``, 
xleftmargin=2em,xrightmargin=2em, aboveskip=1em}

未分类 latex Comments(1) 2012年5月06日 22:46




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee