K 近邻算法 (KNN)

K近邻算法（KNN，K-NearestNeighbor）是一种十分简单的分类方法，也是“懒惰学习”的代表。

KNN 没有训练阶段，或者说训练成本为 0。KNN 只需要将已知的样本拿过来与需要测试的样本做一个简单的比较就能将未分类的样本分类。

KNN 的算法流程也十分简单，大致的思路就是，计算待测点与已知点的距离，选取与待测点距离最近的 k 个已知点，统计这 k 个已知点的类别，哪个类别最多那么这个待测点的类别就属于这个类。

代码的简单实现(以鸢尾花数据集为例)：

import numpy as np
from sklearn import datasets
import matplotlib.pyplot as plt
from sklearn import datasets

def Data():
    #载入鸢尾花数据集
    X=datasets.load_iris()
    #从第一类中随机选取5个样本作为训练集
    train_index=np.random.randint(0,50,5)
    #从第二类第三类随机选出10个样本作为训练集(每个样本取5个)
    train_index=np.hstack((train_index,train_index+50,train_index+100))
    trainX=X.data[train_index]
    trainY=X.target[train_index]
    #数据中其他样本点皆为测试集
    test_index=np.delete(np.arange(150),train_index)
    testX=X.data[test_index]
    return trainX,trainY,testX
    
def kNN(k,trainX,trainY,testX):
    testY=[]   #测试的结果集合
    if k>len(trainY): 
        return 0
    for i in testX:
        #计算距离
        dis=np.linalg.norm(trainX-i,axis=1)
        #将距离和训练集的标签用矩阵绑定
        S=np.vstack((dis,trainY))
        #将矩阵按从小到大排好序
        S=S[:,np.argsort(S[0,:])]
        #取前k个已知标签
        label=S[1,0:k]
        #统计最多出现的标签并将其放入结果集合作为第i个样本的分类结果
        testY.append(np.argmax(np.bincount(label.astype(int))))
    return testY

def plot(trainX,trainY,testX,testY):
    plt.scatter(trainX[:,0],trainX[:,1],c=trainY,marker='x')
    plt.scatter(testX[:,0],testX[:,1],c=testY)
    plt.show()

if __name__ == '__main__':
    trainX,trainY,testX=Data()
    testY=kNN(5,trainX,trainY,testX)
    plot(trainX,trainY,testX,testY)
​

测试结果(只绘制数据集的前两维)：