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))#计算正确率

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