K近邻python

有一个带标签的数据集X，标签为y。我们想通过这个数据集预测目标点x0的所属类别。

K近邻算法是指在X的特征空间中，把x0放进去，然后找到距离x0最近的K个点。通过这K个点所属类别，一般根据少数服从多数的原则，这K个点哪个类别多，就将x0设为哪一类。

关键有三个部分：

1.距离度量：目标点与训练集中的点距离计算，一般采用欧式距离。也可以为其他距离

2.K值选择：K为超参数，所以可以通过交叉验证的方法原则K的值。K一般选比较小的值，假如K值取跟数据集一样大小，就相当于直接认定据集中哪个类的类别多，就认目标点为哪一类。所以肯定不合适。

3.分类决策规则：一般为多数表决，少数服从多数。

K近邻算法还有一个问题是，通过什么算法来选择距离目标点x0最近的K个样本点。线性扫描最简单，计算数据集中每个样本点与X0的距离，然后对这些距离排序，选择最小的几个。但这样复杂度高。还有一种方法是构造kd树，这里不在说明如何构造k-d树，下面文章解释的很清楚。

完结篇|一文搞懂k近邻（k-NN）算法（二） - 忆臻的文章 - 知乎 https://zhuanlan.zhihu.com/p/26029567

代码中选择K个样本点是通过numpy的内置函数np.argpartition（a,kth）即返回前K小个树的位置坐标。

数据集采用鸢尾花数据集，地址在下面，将鸢尾花数据集标签改为0,1,2。

鸢尾花数据集

K原则4，正确率一般在95%以上

代码：

import numpy as np

from matplotlib import pyplot as plt

from random import shuffle

import csv

def data():

    '''

    加载数据，数据集为鸢尾花数据集120个训练集，30个测试集

    :return:

    '''

    with open('iris.data')as f:

        reader = csv.reader(f)

        data_list =list(reader)

    shuffle(data_list)

    X_orign = np.array([(list(map(float,x[:4]))) for x in data_list])

    y_orign = []

    for x in data_list:

        if x[4]=='Iris-setosa':

            y_orign.append(0)

        elif x[4]=='Iris-versicolor':

            y_orign.append(1)

        else:

            y_orign.append(2)

    y_orign = np.array(y_orign)

    X_train = X_orign[:120]

    y_train = y_orign[:120]

    X_test = X_orign[120:]

    y_test = y_orign[120:]

    return X_train,y_train,X_test,y_test

def plot_data(X,y):

    '''

    绘制数据集

    :param X:

    :param y:

    :return:

    '''

    plt.scatter(X[y==0,0],X[y==0,2],s=15,c='r',marker='o')

    plt.scatter(X[y==1,0],X[y==1,2],s=15,c='b',marker='+')

    plt.scatter(X[y==2,0],X[y==2,2],s=15,c='y',marker='*')

    plt.show()

def knn(x,K,X,y):

    '''

    采用线性扫描，求得与目标点x在X中前K个最近的距离

    :param x:

    :param K:

    :param X:

    :param y:

    :return:

    '''

    y =  y[np.argpartition(np.sum((X-x)**2,axis=1),K)[:K]]#欧式距离，获得前K小个元素的索引位置

    return np.argmax([sum(y==0),sum(y==1),sum(y==2)])#返回所属类别，少数服从多数

K = 5

X_train,y_train,X_test,y_test = data()

predict = np.array([knn(i,K,X_train,y_train) for i in X_test])#预测测试集每个元素所属的类别

print('正确率为：{}%'.format(sum(predict==y_test)/len(y_test)*100))#计算正确率

参考资料：李航，统计学习方法

巴特西

K近邻python

最新文章

热门文章