您的位置:新葡亰496net > 奥门新萄京娱乐场 > k近邻算法,KNN算法完毕及其交叉验证

k近邻算法,KNN算法完毕及其交叉验证

发布时间:2019-06-21 12:39编辑:奥门新萄京娱乐场浏览(103)

      近些日子在看knn算法,顺便敲敲代码。

    k近邻算法(knn)的c语言达成,近邻knn

      这段日子在看knn算法,顺便敲敲代码。

     

      knn属于数据开掘的归类算法。基本牵挂是在离开空间里,借使一个样本的最周围的k个邻居里,绝大多数属于有些项目,则该样本也属于那个项目。俗话叫,“随大流”。

      轻易的话,KNN能够用作:有那么一群你早已清楚分类的数额,然后当一个新的多少进入的时候,就起来跟教练里的每种点求距离,然后挑出离这几个数额以来的K个点,看看那K个点属于怎么类型,然后用少数遵从好多的条件,给新数据归类。

      该算法的暗意图,轻易明了:

      图片 1

        上面包车型客车算法步骤取自于百度文库(文库是叁个好东西),代码是参照他事他说加以侦察这一个思路完结的:

       图片 2

     

      code:

      1 #include<stdio.h>
      2 #include<math.h>
      3 #include<stdlib.h>
      4 
      5 #define K 3 //近邻数k
      6 typedef float type;
      7 
      8 //动态创建二维数组
      9 type **createarray(int n,int m)
     10 {
     11     int i;
     12     type **array;
     13     array=(type **)malloc(n*sizeof(type *));
     14     array[0]=(type *)malloc(n*m*sizeof(type));
     15     for(i=1;i<n;i  ) array[i]=array[i-1] m;
     16     return array;
     17 }
     18 //读取数据,要求首行格式为 N=数据量,D=维数
     19 void loaddata(int *n,int *d,type ***array,type ***karray)
     20 {
     21     int i,j;
     22     FILE *fp;
     23     if((fp=fopen("data.txt","r"))==NULL)    fprintf(stderr,"can not open data.txt!n");
     24     if(fscanf(fp,"N=%d,D=%d",n,d)!=2)    fprintf(stderr,"reading error!n");
     25     *array=createarray(*n,*d);
     26     *karray=createarray(2,K);
     27 
     28     for(i=0;i<*n;i  )
     29         for(j=0;j<*d;j  )
     30             fscanf(fp,"%f",&(*array)[i][j]);    //读取数据
     31 
     32     for(i=0;i<2;i  )
     33         for(j=0;j<K;j  )
     34             (*karray)[i][j]=9999.0;    //默认的最大值
     35     if(fclose(fp))    fprintf(stderr,"can not close data.txt");
     36 }
     37 //计算欧氏距离
     38 type computedistance(int n,type *avector,type *bvector)
     39 {
     40     int i;
     41     type dist=0.0;
     42     for(i=0;i<n;i  )
     43         dist =pow(avector[i]-bvector[i],2);
     44     return sqrt(dist);
     45 }
     46 //冒泡排序
     47 void bublesort(int n,type **a,int choice)
     48 {
     49     int i,j;
     50     type k;
     51     for(j=0;j<n;j  )
     52         for(i=0;i<n-j-1;i  ){
     53             if(0==choice){
     54                 if(a[0][i]>a[0][i 1]){
     55                     k=a[0][i];
     56                     a[0][i]=a[0][i 1];
     57                     a[0][i 1]=k;
     58                     k=a[1][i];
     59                     a[1][i]=a[1][i 1];
     60                     a[1][i 1]=k;
     61                 }
     62             }
     63             else if(1==choice){
     64                 if(a[1][i]>a[1][i 1]){
     65                     k=a[0][i];
     66                     a[0][i]=a[0][i 1];
     67                     a[0][i 1]=k;
     68                     k=a[1][i];
     69                     a[1][i]=a[1][i 1];
     70                     a[1][i 1]=k;
     71                 }
     72             }
     73         }
     74 }
     75 //统计有序表中的元素个数
     76 type orderedlist(int n,type *list)
     77 {
     78     int i,count=1,maxcount=1;
     79     type value;
     80     for(i=0;i<(n-1);i  ) {
     81         if(list[i]!=list[i 1]) {
     82             //printf("count of %d is value %dn",list[i],count);
     83             if(count>maxcount){
     84                 maxcount=count;
     85                 value=list[i];
     86                 count=1;
     87             }
     88         }
     89         else
     90             count  ;
     91     }
     92     if(count>maxcount){
     93             maxcount=count;
     94             value=list[n-1];
     95     }
     96     //printf("value %f has a Maxcount:%dn",value,maxcount);
     97     return value;
     98 }
     99 
    100 int main()
    101 {
    102     int i,j,k;
    103     int D,N;    //维度,数据量,标签
    104     type **array=NULL;  //数据数组
    105     type **karray=NULL; //  K近邻点的距离及其标签
    106     type *testdata; //测试数据
    107     type dist,maxdist;
    108 
    109     loaddata(&N,&D,&array,&karray);
    110     testdata=(type *)malloc((D-1)*sizeof(type));
    111     printf("input test data containing %d numbers:n",D-1);
    112     for(i=0;i<(D-1);i  )    scanf("%f",&testdata[i]);
    113 
    114     while(1){
    115     for(i=0;i<K;i  ){
    116         if(K>N) exit(-1);
    117         karray[0][i]=computedistance(D-1,testdata,array[i]);
    118         karray[1][i]=array[i][D-1];
    119         //printf("first karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    120     }
    121 
    122     bublesort(K,karray,0);
    123     //for(i=0;i<K;i  )    printf("after bublesort in first karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    124     maxdist=karray[0][K-1]; //初始化k近邻数组的距离最大值
    125 
    126     for(i=K;i<N;i  ){
    127         dist=computedistance(D-1,testdata,array[i]);
    128         if(dist<maxdist)
    129             for(j=0;j<K;j  ){
    130                 if(dist<karray[0][j]){
    131                     for(k=K-1;k>j;k--){ //j后元素复制到后一位,为插入做准备
    132                         karray[0][k]=karray[0][k-1];
    133                         karray[1][k]=karray[1][k-1];
    134                     }
    135                     karray[0][j]=dist;  //插入到j位置
    136                     karray[1][j]=array[i][D-1];
    137                     //printf("i:%d  karray:%6.2f %6.0fn",i,karray[0][j],karray[1][j]);
    138                     break;  //不比较karray后续元素
    139                 }
    140             }
    141         maxdist=karray[0][K-1];
    142         //printf("i:%d  maxdist:%6.2fn",i,maxdist);
    143     }
    144     //for(i=0;i<K;i  )    printf("karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    145     bublesort(K,karray,1);
    146     //for(i=0;i<K;i  )    printf("after bublesort in karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    147     printf("nThe data has a tag: %.0fnn",orderedlist(K,karray[1]));
    148 
    149     printf("input test data containing %d numbers:n",D-1);
    150     for(i=0;i<(D-1);i  )    scanf("%f",&testdata[i]);
    151     }
    152     return 0;
    153 }
    

     

      实验:

      磨炼多少data.txt:

      N=6,D=9
      1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5 1
      1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8 1
      1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2 1
      1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5 0
      1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5 1
      1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 0

      预测数据:

      1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5

      1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8

      1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2

      1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5

      1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5

      1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 

       

      程序测试的结果:

      1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5 类别为: 1

      1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8 类别为: 1

      1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2 类别为: 1

      1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5 类别为: 0

      1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5 类别为: 1

      1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 类别为: 0

      实验截图:

      图片 3

     

    前段时间在看knn算法,顺便敲敲代码。 knn属于数据开掘的归类算法。基本观念是 在距离空间里,要是三个样...

    凑近算法,大概说K近年来邻(kNN,k-NearestNeighbor)分类算法是数码发现分类技艺中最简便的法子之一。所谓K近期邻,正是k个方今的近邻的乐趣,说的是种种样本都可以用它最周边的k个邻居来表示。
    kNN算法的核激情想是只要叁个样本在特点空间中的k个最相邻的样本中的大诸多属于某三个种类,则该样本也属于这几个类型,并兼有那一个类型上样本的表征。

    KNN算法

    用NumPy库达成K-nearest neighbors回归或分类。

    knn

    走近算法,可能说K方今邻(kNN,k-NearestNeighbor)分类算法是数码发现分类本领中最轻巧易行的艺术之一。所谓K近些日子邻,正是k个近些日子的近邻的意趣,说的是每种样本都能够用它最临近的k个邻居来表示。

    kNN算法的主题情想是一旦贰个样本在特色空间中的k个最相邻的范本中的大好些个属于某三个类别,则该样本也属于这些项目,并具有这么些体系上样本的特征。该措施在规定分类核定上只依照最贴近的一个要么多少个样本的品种来支配待分样本所属的品种。 kNN方法在项目决策时,只与极少许的隔壁样本有关。由于kNN方法重要靠周围有限的近乎的样本,而不是靠剖断类域的措施来规定所属连串的,由此对此类域的穿插或重叠较多的待分样本集来讲,kNN方法较别的格局特别适合。

    粗略的知道,我有一组数据,比方每一种数据都以n维向量,那么大家得以在n维上空表示那么些数额,这几个数量都有相应的标签值,也正是大家感兴趣的前瞻变量。那么当我们接受贰个新的数目标时候,大家能够测算那些新数据和大家已知的教练多少里面包车型客车离开,寻觅在那之中近日的k个数据,对这k个数据对应的竹签值取平均值就是我们得出的预测值。轻巧暴虐,何人离作者近,就认为何人能代表自己,作者就用你们的质量作为作者的品质。具体的粗略代码落成如下。

     


    1. 数据

    这里例子来自《集体智慧编制程序》给的利口酒的价钱模型。烧酒的标价一旦由酒的级差与储藏时期共同决定,给定rating与age之后,就能够给出酒的价位。

    def wineprice(rating,age):
        """
        Input rating & age of wine and Output it's price.
        Example:
        ------
        input = [80.,20.] ===> output = 140.0
        """
        peak_age = rating - 50 # year before peak year will be more expensive
        price = rating/2.
        if age > peak_age:
            price = price*(5 -(age-peak_age))
        else:
            price = price*(5*((age 1)/peak_age))
    
        if price < 0: price=0
        return price
    
    a = wineprice(80.,20.)
    a
    
    140.0
    

    根据上述的价位模型,大家发出n=500瓶酒及价格,同一时间为价格随机加减了六成来反映随机性,相同的时候扩张预测的难度。注意基本数据都以numpy里的ndarray,为了方便向量化计算,同期又有强有力的broadcast功效,总括主要推荐。

    def wineset(n=500):
        """
        Input wineset size n and return feature array and target array.
        Example:
        ------
        n = 3
        X = np.array([[80,20],[95,30],[100,15]])
        y = np.array([140.0,163.6,80.0])
        """
        X,y  = [], []
        for i in range(n):
            rating = np.random.random()*50   50
            age = np.random.random()*50
            # get reference price
            price = wineprice(rating,age)
            # add some noise
            price = price*(np.random.random()*0.4   0.8) #[0.8,1.2]
            X.append([rating,age])
            y.append(price)
        return np.array(X), np.array(y)
    
    X,y = wineset(500)
    
    X[:3]
    
    array([[ 88.89511317,  11.63751282],
           [ 91.57171713,  39.76279923],
           [ 98.38870877,  14.07015414]])
    

      knn属于数据发掘的分类算法。基本思维是在相距空间里,假若三个样本的最附近的k个邻居里,绝大好多属于有些项目,则该样本也属于那一个项目。俗话叫,“随大流”。

    数量策画,这里运用random函数生成10*2的矩阵作为两列特征值,1个12个因素数组作为项目值

    2. 相似度:欧氏距离

    knn的名字叫K近邻,如何叫“近”,咱们要求一个数学上的定义,最广大的是用欧式距离,二维三个维度的时候对应平面或空中中远距离。

    算法实现里供给的是给定八个新的数量,需求计算其与演练数据组之间全数一点之间的相距,注意是例外的维度,给定的新数据只是二个sample,而教练多少是n组,n个sample,总括的时候需求专注,可是numpy能够活动broadcat,能够很好地take care of it。

    def euclidean(arr1,arr2):
        """
        Input two array and output theie distance list.
        Example:
        ------
        arr1 = np.array([[3,20],[2,30],[2,15]])
        arr2 = np.array([[2,20],[2,20],[2,20]]) # broadcasted, np.array([2,20]) and [2,20] also work.
        d    = np.array([1,20,5])
        """
        ds = np.sum((arr1 - arr2)**2,axis=1)
        return np.sqrt(ds)
    
    arr1 = np.array([[3,20],[2,30],[2,15]])
    arr2 = np.array([[2,20],[2,20],[2,20]])
    euclidean(arr1,arr2)
    
    array([  1.,  10.,   5.])
    

    提供贰个简洁的接口,给定练习数据X和新sample v,然后回来排序好的距离,以及相应的index(大家要以此索引近邻们对应的标签值)。

    def getdistance(X,v):
        """
        Input train data set X and a sample, output the distance between each other with index.
        Example:
        ------
        X = np.array([[3,20],[2,30],[2,15]])
        v = np.array([2,20]) # to be broadcasted
        Output dlist = np.array([1,5,10]), index = np.array([0,2,1])
        """
        dlist = euclidean(X,np.array(v))
        index = np.argsort(dlist)
        dlist.sort()
        # dlist_with_index = np.stack((dlist,index),axis=1)
        return dlist, index  
    
    dlist, index = getdistance(X,[80.,20.])
    

      一言以蔽之,KNN能够当做:有那么一批你已经清楚分类的多少,然后当二个新的多少进入的时候,就起来跟教练里的各类点求距离,然后挑出离这一个数据以来的K个点,看看那K个点属于怎么类型,然后用少数遵循多数的尺度,给新数据归类。

    import numpy as np
    import matplotlib.pyplot as plt
    
    x_train = np.random.rand(10,2)*8
    y_train = np.random.randint(0,2,10)
    x = np.array([3,4])
    k=3
    plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color="red")
    plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color="green")
    plt.scatter(x[0],x[1],marker=' ',color="blue")
    plt.show()
    

    3. KNN算法

    knn算法具体贯彻的时候很简短,调用前边的函数,总括出排序好的相距列表,然后对其前k项对应的标签值取均值就可以。能够用该knn算法与事实上的标价模型对照,开掘精度还能够。

    def knn(X,y,v,kn=3):
        """
        Input train data and train target, output the average price of new sample.
        X = X_train; y = y_train
        k: number of neighbors
        """
        dlist, index = getdistance(X,v)
        avg = 0.0
        for i in range(kn):
            avg = avg   y[index[i]]
        avg = avg / kn
        return avg
    
    knn(X,y,[95.0,5.0],kn=3)
    
    32.043042600537092
    
    wineprice(95.0,5.0)
    
    31.666666666666664
    

      该算法的暗意图,简单明了:

    图片 4

    4. 加权KNN

    上述是KNN的基本算法,有一个主题材料正是该算法给全体的左邻右舍分配相等的权重,那几个还是能够如此改正,就是给更近的邻家分配更加大的权重(你离自身更近,这自身就感到你跟自家更相像,就给你分配越来越大的权重),而较远的近邻的权重相应地缩减,取其加权平均。须求多少个能把距离调换为权重的函数,gaussian函数是四个相比较宽泛的取舍,下图能够见到gaussian函数的衰减趋势。从上边包车型地铁单例能够看出其职能要比knn算法的效应自个儿,可是只是单个例子,不负有说服力,前面给出更可相信的褒贬。

    def gaussian(dist,sigma=10.0):
        """Input a distance and return it's weight"""
        weight = np.exp(-dist**2/(2*sigma**2))
        return weight
    
    x1 = np.arange(0,30,0.1)
    y1 = gaussian(x1)
    plt.title('gaussian function')
    plt.plot(x1,y1);
    

    图片 5

    def knn_weight(X,y,v,kn=3):
        dlist, index = getdistance(X,v)
        avg = 0.0
        total_weight = 0
        for i in range(kn):
            weight = gaussian(dlist[i])
            avg = avg   weight*y[index[i]]
            total_weight = total_weight   weight
        avg = avg/total_weight
        return avg
    
    knn_weight(X,y,[95.0,5.0],kn=3)
    
    32.063929602836012
    

      图片 6

    绿点为体系0,红点为品种1

    时有时无验证

    写三个函数,达成交叉验证效用,不能够用sklearn库。

    接力验证(克罗丝-Validation): 不时亦称循环估算, 是一种总计学元帅数据样本切割成相当小子集的实用方法。于是能够先在贰个子集上做深入分析, 而其余子集则用来做继续对此深入分析的认同及表明。 一从头的子集被叫做演练集。而其余的子集则被叫作验证集或测试集。常见交叉验证格局如下:

    Holdout Method(保留)

    • 艺术:将原有数据随机分为两组,一组做为陶冶集,一组做为验证集,利用练习集中练习练分类器,然后利用验证集验证模型,记录最终的归类正确率为此Hold-OutMethod下分类器的习性指标.。Holdout Method相对于K-fold Cross Validation 又称Double cross-validation ,或相对K-CV称 2-fold cross-validation(2-CV)
    • 可取:好处的处理大概,只需随机把本来数据分为两组就能够
    • 症结:严谨意义来讲Holdout Method并无法算是CV,因为这种方法未有达到交叉的商讨,由于是随机的将原来数据分组,所以最后验证集分类准确率的音量与原本数据的分组有异常的大的涉嫌,所以这种艺术赢得的结果其实并不负有说服性.(主因是 练习集样本数太少,平日不足以代表母体样本的遍及,导致 test 阶段辨识率轻易出现鲜明落差。别的,2-CV 中一分为二的积极分子集格局的变异度大,往往不可能达到「实验进度必须能够被复制」的渴求。)

    K-fold Cross Validation(k折叠)

    • 艺术:作为Holdout Methon的演进,将原始数据分为K组(一般是均分),将种种子集数据分别做三遍验证集,别的的K-1组子集数据作为锻练集,那样会收获K个模型,用那K个模型末了的验证集的归类准确率的平平均数量作为此K-CV下分类器的属性指标.K一般当先等于2,实操时相似从3开首取,唯有在本来数据集合数据量小的时候才会尝试取2. 而K-CV 的尝试共必要树立 k 个models,并妄图 k 次 test sets 的平均辨识率。在实作上,k 要够大本领使各回合中的 陶冶样本数够多,一般来说 k=10 (作为一个经历参数)算是非常充足了。
    • 优点:K-CV能够有效的防止过学习以及欠学习境况的产生,最终获得的结果也正如具有说服性.
    • 缺陷:K值选取上

    Leave-One-Out Cross Validation(留一)

    • 形式:若是设原始数占领N个样本,那么留一就是N-CV,即每一个样本单独作为验证集,其他的N-1个样本作为磨练集,所以留一会收获N个模型,用那N个模型最后的验证集的归类正确率的平平均数量作为此下LOO-CV分类器的属性目标.
    • 可取:相比于前方的K-CV,留一有五个分明的亮点:
      • a.每二次合中差不离具备的样本皆用于磨练模型,因此最临近原始样本的遍及,这样评估所得的结果比较可信赖。
      • b. 实验进度中一向不随机因素会影响实验数据,确定保证实验进度是足以被复制的.
    • 症结:计算开销高,因为必要建设构造的模型数量与原来数据样本数量同样,当原始数据样本数量诸多时,LOO-CV在实作上便有多数不便差非常的少正是不展现,除非每便练习分类器得到模型的快慢神速,或是能够用并行化计算收缩计算机手艺研商所需的年华。

    Holdout method方法的主见很简单,给一个train_size,然后算法就能够在钦命的比重(train_size)处把数据分为两局地,然后再次来到。

    # Holdout method
    def my_train_test_split(X,y,train_size=0.95,shuffle=True):
        """
        Input X,y, split them and out put X_train, X_test; y_train, y_test.
        Example:
        ------
        X = np.array([[0, 1],[2, 3],[4, 5],[6, 7],[8, 9]])
        y = np.array([0, 1, 2, 3, 4])
        Then
        X_train = np.array([[4, 5],[0, 1],[6, 7]])
        X_test = np.array([[2, 3],[8, 9]])
        y_train = np.array([2, 0, 3])
        y_test = np.array([1, 4])
        """
        order = np.arange(len(y))
        if shuffle:
            order = np.random.permutation(order)
        border = int(train_size*len(y))
        X_train, X_test = X[:border], X[border:]
        y_train, y_test = y[:border], y[border:]
        return X_train, X_test, y_train, y_test
    

    K folds算法是把数据分为k份,进行k此循环,每一趟不等的份k近邻算法,KNN算法完毕及其交叉验证。分别来充当测试组数据。可是注意,该算法不直接操作数据,而是爆发三个迭代器,再次回到磨练和测试数据的目录。看docstring里的例子应该很了解。

    # k folds 产生一个迭代器
    def my_KFold(n,n_folds=5,shuffe=False):
        """
        K-Folds cross validation iterator.
        Provides train/test indices to split data in train test sets. Split dataset 
        into k consecutive folds (without shuffling by default).
        Each fold is then used a validation set once while the k - 1 remaining fold form the training set.
        Example:
        ------
        X = np.array([[1, 2], [3, 4], [1, 2], [3, 4]])
        y = np.array([1, 2, 3, 4])
        kf = KFold(4, n_folds=2)
        for train_index, test_index in kf:
            X_train, X_test = X[train_index], X[test_index]
            y_train, y_test = y[train_index], y[test_index]
            print("TRAIN:", train_index, "TEST:", test_index)
        TRAIN: [2 3] TEST: [0 1]
        TRAIN: [0 1] TEST: [2 3]
        """
        idx = np.arange(n)
        if shuffe:
            idx = np.random.permutation(idx)
        fold_sizes = (n // n_folds) * np.ones(n_folds, dtype=np.int) # folds have size n // n_folds
        fold_sizes[:n % n_folds]  = 1 # The first n % n_folds folds have size n // n_folds   1
        current = 0
        for fold_size in fold_sizes:
            start, stop = current, current   fold_size
            train_index = list(np.concatenate((idx[:start], idx[stop:])))
            test_index = list(idx[start:stop])
            yield train_index, test_index
            current = stop # move one step forward
    
    X1 = np.array([[1, 2], [3, 4], [1, 2], [3, 4]])
    y1 = np.array([1, 2, 3, 4])
    kf = my_KFold(4, n_folds=2)
    
    for train_index, test_index in kf:
        X_train, X_test = X1[train_index], X1[test_index]
        y_train, y_test = y1[train_index], y1[test_index]
        print("TRAIN:", train_index, "TEST:", test_index)
    
    ('TRAIN:', [2, 3], 'TEST:', [0, 1])
    ('TRAIN:', [0, 1], 'TEST:', [2, 3])
    

        上边包车型地铁算法步骤取自于百度文库(文库是三个好东西),代码是参照这一个思路实现的:

    X_train = np.array(x_train)
    
    Y_train = np.array(y_train)
    
    from math import sqrt
    distances = []
    for x_train in X_train:
        d = sqrt(np.sum((x-x_train)**2))
        distances.append(d)
    
    distances = [sqrt(np.sum((x-x_train)**2)) for x_train in X_train]
    argindex = np.argsort(distances)
    
    from collections import Counter
    
    topK_Y = [Y_train[i] for i in argindex[:k]]
    
    votes = Counter(topK_Y)
    votes.most_common(1)[0][0]
    

    KNN算法交叉验证

    齐全只欠东风,已经完结了KNN算法以及交叉验证成效,我们就足以应用交叉验证的沉思为大家的算法选拔妥帖的参数,那也是交叉验证首要目的之一。

       图片 7

    实行结果为决断x点差不离率为体系0(绿点)

    批评算法

    先是我们用三个函数评价算法,给定磨练多少与测试数据,总结平均的乘除标称误差,那是评价算法好坏的重中之重指标。

    def test_algo(alg,X_train,X_test,y_train,y_test,kn=3):
        error = 0.0
        for i in range(len(y_test)):
            guess = alg(X_train,y_train,X_test[i],kn=kn)
            error  = (y_test[i] - guess)**2
        return error/len(y_test)
    
    X_train,X_test,y_train,y_test = my_train_test_split(X,y,train_size=0.8)
    
    test_algo(knn,X_train,X_test,y_train,y_test,kn=3)
    
    783.80937472673656
    

     


    交叉验证

    收获平均引用误差,注意这里KFold 生成器的利用。

    def my_cross_validate(alg,X,y,n_folds=100,kn=3):
        error = 0.0
        kf = my_KFold(len(y), n_folds=n_folds)
        for train_index, test_index in kf:
            X_train, X_test = X[train_index], X[test_index]
            y_train, y_test = y[train_index], y[test_index]
            error  = test_algo(alg,X_train,X_test,y_train,y_test,kn=kn)
        return error/n_folds
    

      code:

    运用sklearn中封装的knn算法

    from sklearn.neighbors import KNeighborsClassifier
    
    knn_clf = KNeighborsClassifier(n_neighbors=3)
    
    knn_clf.fit(X_train,Y_train)
    
    knn_clf.predict(x.reshape(1,-1))[0]
    

    选最棒的k值

    从下图能够看出,模型表现随k值的扭转呈现三个折现型,当为1时,表现较差;当取2,3的时候,模型表现还行;但当k继续增添的时候,模型表现小幅度下落。同期knn_weight算法要略优于knn算法,有一丝丝立异。

    errors1, errors2 = [], []
    for i in range(20):
        error1 = my_cross_validate(knn,X,y,kn=i 1)
        error2 = my_cross_validate(knn_weight,X,y,kn=i 1)
        errors1.append(error1)
        errors2.append(error2)
    
    xs = np.arange(len(errors1))   1
    plt.plot(xs,errors1,color='c')
    plt.plot(xs,errors2,color='r')
    plt.xlabel('K')
    plt.ylabel('Error')
    plt.title('Error vs K');
    

    图片 8

      1 #include<stdio.h>
      2 #include<math.h>
      3 #include<stdlib.h>
      4 
      5 #define K 3 //近邻数k
      6 typedef float type;
      7 
      8 //动态创建二维数组
      9 type **createarray(int n,int m)
     10 {
     11     int i;
     12     type **array;
     13     array=(type **)malloc(n*sizeof(type *));
     14     array[0]=(type *)malloc(n*m*sizeof(type));
     15     for(i=1;i<n;i  ) array[i]=array[i-1] m;
     16     return array;
     17 }
     18 //读取数据,要求首行格式为 N=数据量,D=维数
     19 void loaddata(int *n,int *d,type ***array,type ***karray)
     20 {
     21     int i,j;
     22     FILE *fp;
     23     if((fp=fopen("data.txt","r"))==NULL)    fprintf(stderr,"can not open data.txt!n");
     24     if(fscanf(fp,"N=%d,D=%d",n,d)!=2)    fprintf(stderr,"reading error!n");
     25     *array=createarray(*n,*d);
     26     *karray=createarray(2,K);
     27 
     28     for(i=0;i<*n;i  )
     29         for(j=0;j<*d;j  )
     30             fscanf(fp,"%f",&(*array)[i][j]);    //读取数据
     31 
     32     for(i=0;i<2;i  )
     33         for(j=0;j<K;j  )
     34             (*karray)[i][j]=9999.0;    //默认的最大值
     35     if(fclose(fp))    fprintf(stderr,"can not close data.txt");
     36 }
     37 //计算欧氏距离
     38 type computedistance(int n,type *avector,type *bvector)
     39 {
     40     int i;
     41     type dist=0.0;
     42     for(i=0;i<n;i  )
     43         dist =pow(avector[i]-bvector[i],2);
     44     return sqrt(dist);
     45 }
     46 //冒泡排序
     47 void bublesort(int n,type **a,int choice)
     48 {
     49     int i,j;
     50     type k;
     51     for(j=0;j<n;j  )
     52         for(i=0;i<n-j-1;i  ){
     53             if(0==choice){
     54                 if(a[0][i]>a[0][i 1]){
     55                     k=a[0][i];
     56                     a[0][i]=a[0][i 1];
     57                     a[0][i 1]=k;
     58                     k=a[1][i];
     59                     a[1][i]=a[1][i 1];
     60                     a[1][i 1]=k;
     61                 }
     62             }
     63             else if(1==choice){
     64                 if(a[1][i]>a[1][i 1]){
     65                     k=a[0][i];
     66                     a[0][i]=a[0][i 1];
     67                     a[0][i 1]=k;
     68                     k=a[1][i];
     69                     a[1][i]=a[1][i 1];
     70                     a[1][i 1]=k;
     71                 }
     72             }
     73         }
     74 }
     75 //统计有序表中的元素个数
     76 type orderedlist(int n,type *list)
     77 {
     78     int i,count=1,maxcount=1;
     79     type value;
     80     for(i=0;i<(n-1);i  ) {
     81         if(list[i]!=list[i 1]) {
     82             //printf("count of %d is value %dn",list[i],count);
     83             if(count>maxcount){
     84                 maxcount=count;
     85                 value=list[i];
     86                 count=1;
     87             }
     88         }
     89         else
     90             count  ;
     91     }
     92     if(count>maxcount){
     93             maxcount=count;
     94             value=list[n-1];
     95     }
     96     //printf("value %f has a Maxcount:%dn",value,maxcount);
     97     return value;
     98 }
     99 
    100 int main()
    101 {
    102     int i,j,k;
    103     int D,N;    //维度,数据量
    104     type **array=NULL;  //数据数组
    105     type **karray=NULL; //  K近邻点的距离及其标签
    106     type *testdata; //测试数据
    107     type dist,maxdist;
    108 
    109     loaddata(&N,&D,&array,&karray);
    110     testdata=(type *)malloc((D-1)*sizeof(type));
    111     printf("input test data containing %d numbers:n",D-1);
    112     for(i=0;i<(D-1);i  )    scanf("%f",&testdata[i]);
    113 
    114     while(1){
    115     for(i=0;i<K;i  ){
    116         if(K>N) exit(-1);
    117         karray[0][i]=computedistance(D-1,testdata,array[i]);
    118         karray[1][i]=array[i][D-1];
    119         //printf("first karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    120     }
    121 
    122     bublesort(K,karray,0);
    123     //for(i=0;i<K;i  )    printf("after bublesort in first karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    124     maxdist=karray[0][K-1]; //初始化k近邻数组的距离最大值
    125 
    126     for(i=K;i<N;i  ){
    127         dist=computedistance(D-1,testdata,array[i]);
    128         if(dist<maxdist)
    129             for(j=0;j<K;j  ){
    130                 if(dist<karray[0][j]){
    131                     for(k=K-1;k>j;k--){ //j后元素复制到后一位,为插入做准备
    132                         karray[0][k]=karray[0][k-1];
    133                         karray[1][k]=karray[1][k-1];
    134                     }
    135                     karray[0][j]=dist;  //插入到j位置
    136                     karray[1][j]=array[i][D-1];
    137                     //printf("i:%d  karray:%6.2f %6.0fn",i,karray[0][j],karray[1][j]);
    138                     break;  //不比较karray后续元素
    139                 }
    140             }
    141         maxdist=karray[0][K-1];
    142         //printf("i:%d  maxdist:%6.2fn",i,maxdist);
    143     }
    144     //for(i=0;i<K;i  )    printf("karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    145     bublesort(K,karray,1);
    146     //for(i=0;i<K;i  )    printf("after bublesort in karray:%6.2f  %6.0fn",karray[0][i],karray[1][i]);
    147     printf("nThe data has a tag: %.0fnn",orderedlist(K,karray[1]));
    148 
    149     printf("input test data containing %d numbers:n",D-1);
    150     for(i=0;i<(D-1);i  )    scanf("%f",&testdata[i]);
    151     }
    152     return 0;
    153 }
    

    打包自身的knn算法

    # _*_ encoding:utf-8 _*_
    import numpy as np
    from math import sqrt
    from collections import Counter
    
    class KNNClassifier:
        def __init__(self,k):
            assert k>=1, "k must be valid"
            self.k = k
            self._X_train = None
            self._Y_train = None
    
        def fit(self,X_train,Y_train):
            assert X_train.shape[0] == Y_train.shape[0],
                                                         "The size of X_train must be equals to the size of Y-Train"
            assert self.k <= X_train.shape[0]
            self._X_train = X_train
            self._Y_train = Y_train
            return self
    
        def predict(self,x_predict):
            return np.array([self._predict(x) for x in x_predict])
    
        def _predict(self,x):
            distances = [ sqrt(np.sum((x_train-x)**2)) for x_train in self._X_train]
            nearest = np.argsort(distances)
            votes = [i for i in self._Y_train[nearest[:self.k]]]
            return Counter(votes).most_common(1)[0][0]
    
        def __repr__(self):
            return "knn(k=%d)" %self.k
    

     

    测试与教练多少集分类

    为了能够料定模型的准头,大家须要将已有数量集按自然比重分类为测试数据集和磨炼数据集

    # _*_ encoding:utf-8 _*_
    import numpy as np
    
    def train_test_split(X,y,test_radio=0.2,seed=None):
        assert X.shape[0]==y.shape[0],"The size of X and y must be equal"
        assert 0.0<=test_radio<=1.0,"test radio must be valid"
        if(seed):
            np.random.seed(seed)
    
        shuffled_indexes = np.random.permutation(len(X))
        test_size = int(X.shape[0]*test_radio)
        test_indexes = shuffled_indexes[:test_size]
        train_indexes = shuffled_indexes[test_size:]
    
        X_test = X[test_indexes]
        y_test = y[test_indexes]
        X_train = X[train_indexes]
        y_train = y[train_indexes]
        return X_train,X_test,y_train,y_test
    

      实验:

    利用knn算法测试数据集digits

    import numpy as np
    from sklearn import datasets
    import matplotlib.pyplot as plt
    import matplotlib
    %run MyScripts/KNN.py
    %run MyScripts/metrics.py
    %run MyScripts/model_selection.py
    
    digits = datasets.load_digits()
    X = digits.data
    y = digits.target
    
    some_digit = X[666]
    some_digit_image = some_digit.reshape(8,8)
    plt.imshow(some_digit_image,cmap=matplotlib.cm.binary)
    

    图片 9

    画出第6六拾陆个数据对应的数字图片

    knn_clf = KNNClassifier(k=6)
    X_train,X_test,y_train,y_test = train_test_split(X,y)
    knn_clf.fit(X_train,y_train)
    knn_clf.score(X_test,y_test)
    

      陶冶多少data.txt:

    超参数

    超参数是模型运营前必须求调整的参数,举个例子k近邻算法中的k值和离开
    明确超参数一般选取的办法:

    天地知识
    经历数值
    尝试研究

      N=6,D=9
      1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5 1
      1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8 1
      1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2 1
      1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5 0
      1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5 1
      1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 0

    鲜明knn算法用于digits数据集的一流超参数

    //使用网格搜索法确定weights和k超参数
    best_k = -1
    best_score = -1
    methods = ["uniform","distance"]
    best_method = ""
    for method in methods:
        for k in range(1,11):
            knn_clf = KNeighborsClassifier(n_neighbors=k,weights=method)
            knn_clf.fit(X_train,y_train)
            score = knn_clf.score(X_test,y_test)
            if(score>best_score):
                best_k = k
                best_score = score
                best_method = method
    print("best_k = ",best_k)
    print("best_score = ",best_score)
    print("best_method = ",best_method)
    

    best_k = 3
    best_score = 0.9888888888888889
    best_method = uniform

    best_k = -1
    best_score = -1
    best_p=-1
    for p in range(1,6):
        for k in range(1,11):
            knn_clf = KNeighborsClassifier(n_neighbors=k,weights="distance",p=p)
            knn_clf.fit(X_train,y_train)
            score = knn_clf.score(X_test,y_test)
            if(score>best_score):
                best_k = k
                best_score = score
                best_p = p
    print("best_k = ",best_k)
    print("best_score = ",best_score)
    print("best_p = ",best_p)
    

    best_k = 3
    best_score = 0.9888888888888889
    best_p = 2

      预测数据:

      1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5

      1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8

      1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2

      1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5

      1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5

      1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 

       

      程序测试的结果:

      1.0 1.1 1.2 2.1 0.3 2.3 1.4 0.5 类别为: 1

      1.7 1.2 1.4 2.0 0.2 2.5 1.2 0.8 类别为: 1

      1.2 1.8 1.6 2.5 0.1 2.2 1.8 0.2 类别为: 1

      1.9 2.1 6.2 1.1 0.9 3.3 2.4 5.5 类别为: 0

      1.0 0.8 1.6 2.1 0.2 2.3 1.6 0.5 类别为: 1

      1.6 2.1 5.2 1.1 0.8 3.6 2.4 4.5 类别为: 0

      实验截图:

      图片 10

     

    本文由新葡亰496net发布于奥门新萄京娱乐场,转载请注明出处:k近邻算法,KNN算法完毕及其交叉验证

    关键词: