这篇博客是用python实现k近邻算法，没有调用已有的knn库中的函数，根据伪代码实现算法的每个部分，初学python，可能代码部分写的不够规范。但是最终在数据集上测试效果还是不错的，准确率可以达到98.5%以上。

1.k近邻（knn）算法

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。举例来说，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。
python实现k近邻（knn）算法在minst数据集上验证
我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：
如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形。
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。
那么给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中，这样就可以实现数分类功能了。下面就在minst数据集进行验证。

2.inst数据集

MNIST数据集是一个手写体数据集，简单说就是一堆这样东西
python实现k近邻（knn）算法在minst数据集上验证
每张图片大小为28x28，每个像素点用一个灰度值表示，这里是将28x28的像素展开为一个一维的行向量（每行 784个值）,标签为0-9。加载数据集的方式为：

# 导入数据集
from sklearn.datasets import fetch_mldata 
mnist = fetch_mldata('MNIST original') 
X = mnist.data #行向量
y = mnist.target #标签

这种方式加载的是完整的数据集，即共7000个样本，包括60000张训练样本和10000张测试样本。考虑到电脑实际，也没开gpu加速，只能加载缩小的数据集。加载数据集的方式为：

from sklearn.datasets import fetch_mldata
#mnist = fetch_mldata('MNIST original')
mnist = load_digits()
X = mnist.data
lable = mnist.target # 标签

这是缩小的数据集图片像素和总样本数量都减少了，缩减很大的计算量，但是在测试的时候感觉效果还是很不错的。

3.伪代码

计算已知类别数据集中的点与当前点之间的距离；
按照距离递增次序排序；
选取与当前点距离最小的k个点；
确定呢前k个点所在类别的出现概率；
返回前k个点出现频率最高的类别作为当前点的预测分类。

4.代码部分

4.1 模块1

将数据集预处理的部分写成 ex1.py，即分出训练集（其实也没有训练的过程）和测试集。

from sklearn.datasets import load_digits
import numpy as np
from sklearn.datasets import fetch_mldata
#mnist = fetch_mldata('MNIST original')
mnist = load_digits()
x = mnist.data
lable = mnist.target # 标签

#数据集预处理
def random(lable,fenlei):
    b =set()#产生的测试集合不重复
    while(len(b)<fenlei):
        b.add(np.random.randint(0,len(lable)))
    return b

def shujuji(x,b,lable):
	#图片划分
    train_x = [x[i] for i in range(len(lable)) if (i not in b)]
    ceshi_x = [x[i] for i in range(len(lable)) if (i in b)]
    #标签划分
    train_lable = [lable[i] for i in range(len(lable)) if (i not in b)]
    ceshi_lable = [lable[i] for i in range(len(lable)) if (i in b)]
    return train_x,train_lable,ceshi_x,ceshi_lable

4.2 模块2

将测试集的每一个向量与训练集的每一个求欧式距离，保存在列表距离列表中，分别写了原始数据的距离和归一化之后距离的函数（其实数据尺度相近，归一化没什么效果，但是为了验证归一化算法，写了试一下），模块命名为 ex2.py

import numpy as np
from sklearn.datasets import load_digits
from sklearn.datasets import fetch_mldata
#mnist = fetch_mldata('MNIST original')
mnist = load_digits()
x = mnist.data
lable = mnist.target # 标签

#所有距离
def juli(x,x0,b):
    ds = [[]for i in range(len(b))]
    i = 0
    j = 0
    while i < len(b):
        while j < len(x):
            M = np.linalg.norm(x[j] - x0[i])
            #M = round(M,1)
            j = j + 1
            ds[i].append(M)
        j = 0
        i = i + 1
    return ds
#print(ds)
#归一化处理
def youhuajuli(x,x0,b):
	#用的最简单的归一化算法
    minx = [[]for i in range(len(x))]
    maxx = [[]for i in range(len(x))]
    maxx0 = [[]for i in range(len(b))]
    minx0 = [[]for i in range(len(b))]
    m = 0
    n = 0
    while m < len(x):
        minx[m] = min(x[m])
        maxx[m] = max(x[m])
        x[m] = (x[m] - minx[m])/(maxx[m] - minx[m])
        m = m + 1
    while n < len(b):
        maxx0[n]= max(x0[n])
        minx0[n] = min(x0[n])
        x0[n] = (x0[n] - minx0[n])/(maxx0[n] - minx0[n])
        n = n + 1
#print(x,y,x0,y0)
    youhuads = [[]for i in range(len(b))]
    i = 0
    j = 0
    while i < len(b):
        while j < len(x):
            M = np.linalg.norm(x[j] - x0[i])
            j = j + 1
            youhuads[i].append(M)
        j = 0
        i = i + 1
    return youhuads
    #一定要注意此处代码的缩进

4.3模块3

这是主要的部分

import ex1
import ex2
import numpy as np
from sklearn.datasets import load_digits
from sklearn.metrics import accuracy_score
from sklearn.datasets import fetch_mldata
#mnist = fetch_mldata('MNIST original')
mnist = load_digits()
X = mnist.data
lable = mnist.target # 标签
#产生测试集个数，默认500
fenlei = 500
#fenlei = 300
#fenlei = 100
print('请输入k值')
k = input('>')
k = int(k)
#产生500个随机索引，划分数据集
def suijib(fenlei,lable):
    b =set()
    while(len(b)<fenlei):
        b.add(np.random.randint(0,len(lable)))
    return b
#b = suijib(fenlei,lable)
#找出K个最小值，每次找到一个，用999999替换相应元素
def mintemp(k,b,ds):
    k = k
    b = b
    ds = ds
    m = 0
    n = 0
    Inf = 999999
    temp = [[]for i in range(len(b))]
    while m < len(b):
        while n < k:
            juli = ds[m]
            temp[m].append(juli.index(min(juli)))
            juli[juli.index(min(juli))] = Inf
            n = n + 1
            #print(juli)
        n = 0
        m = m + 1
    return temp
#print(temp)#调试用
#确定K个对应元素距离最小的标签
def minlable(temp,train_lable,b):
    temp = temp
    train_lable = train_lable
    b = b
    i = 0
    lable_train = [[]for i in range(len(b))]
    while i < len(b):
        lable_train[i] = [train_lable[la] for la in range(len(train_lable)) if (la in temp[i])]
        i = i + 1
    return lable_train
#print(lable_train)
#找出K个标签的相同元素最多的作为计算标签
def max_list(lt):
    temp = 0
    for i in lt:
        if lt.count(i) > temp:
            max_str = i
            temp = lt.count(i)
    return max_str
#调用函数实现k近邻
n = 1
accuracy1 = 0
accuracy2 = 0
while n < 21:
    b = ex1.random(lable,fenlei)
    x = X
    train_x,train_lable,ceshi_x,ceshi_lable=ex1.shujuji(x,b,lable)
    x = train_x
    x0 = ceshi_x
    ds1 = ex2.juli(x,x0,b)
    temp1 = mintemp(k,b,ds1)
    #print(temp1)
    lable_train1 = minlable(temp1,train_lable,b)
    lable_test1 = []
    j = 0
    while j < len(b):
        #print(lable_train[j])
        lable_test1.append(max_list(lable_train1[j]))
        j = j + 1

    youhuads2 = ex2.youhuajuli(x,x0,b)
    temp2 = mintemp(k,b,youhuads2)
    #print(temp2)
    lable_train2 = minlable(temp2,train_lable,b)
    #lable_train = np.array(lable_train)
    lable_test2 = []
    j = 0
    while j < len(b):
        #print(lable_train[j])
        lable_test2.append(max_list(lable_train2[j]))
        j = j + 1
    #print("正确标签：")
    #print(ceshi_lable)
    #print("归一化后K近邻计算标签：")
    #print(lable_test2)
    lable_test2 = np.array(lable_test2)
    ceshi_lable = np.array(ceshi_lable)
    a2 = sum(lable_test2==ceshi_lable)
    print("次数")
    print(n)
    print("归一化后""第"+ str(n) +"次准确率")
    print(a2 / float(len(ceshi_lable)))
    accuracy2 = accuracy2 + a2 / float(len(ceshi_lable))
    #print("正确标签：")
    #print(lable_test1)
    lable_test1 = np.array(lable_test1)
    ceshi_lable = np.array(ceshi_lable)
    a1 = sum(lable_test1==ceshi_lable)
    print("归一化前""第"+ str(n) +"次准确率")
    print(a1 / float(len(ceshi_lable)))
    accuracy1 = accuracy1 + a1 / float(len(ceshi_lable))
    print("################################################")
    n = n + 1
accuracy1 = accuracy1 / 20
accuracy2 = accuracy2 / 20
print("归一化前20次平均准确率:")
print(accuracy1)
print("归一化后20次平均准确率:")
print(accuracy2)

代码写的挺多的，有很多地方还是可以简化的，为了方便调试，留了很多输出的部分。
下面就是验证一下
直接运行最后一个模块，分别验证了一下参数
测试集100 k=3
测试集100 k=5
测试集100 k=10
测试集300 k=3
测试集300 k=5
测试集300 k=10
测试集500 k=3
测试集500 k=5
测试集500 k=10
结果如图（部分图）
python实现k近邻（knn）算法在minst数据集上验证
从结果可以看出20次的平均准确率都在98%以上，效果是很不错的。
参考
百度百科：https://baike.baidu.com/item/k近邻算法/9512781?fr=aladdin
详解 MNIST 数据集：
https://blog.****.net/simple_the_best/article/details/75267863

python实现k近邻（knn）算法在minst数据集上验证