澳门新萄京官方网站-www.8455.com-澳门新萄京赌场网址

澳门新萄京官方网站KNN算法实现及其交叉验证,

2019-06-22 作者:www.8455.com   |   浏览(114)

  近年来在看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:

澳门新萄京官方网站KNN算法实现及其交叉验证,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

  预测数据:

  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

澳门新萄京官方网站KNN算法实现及其交叉验证,k近邻算法。  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个拾三个要素数组作为项目值

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 克Rose 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此循环,每回不相同的份独家来肩负测试组数据。不过注意,该算法不间接操作数据,而是发生三个迭代器,重返磨练和测试数据的目录。看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六14个数据对应的数字图片

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

 

本文由澳门新萄京官方网站发布于www.8455.com,转载请注明出处:澳门新萄京官方网站KNN算法实现及其交叉验证,

关键词: