knn是k-nearest neighbors的缩写，k最邻近算法。常常用来做分类。

    k最邻近算法示意图：

     原理说明：
    1、蓝色正方形，红色三角形代表已分类的训练数据。
    2、绿色圆形，代表待分类的新样本。
    3、实线圆圈，圈出距离新样本最近的k个邻居。
    4、分类规则：k个邻居中，多数投票->三红一蓝，新样本被判定为红色三角形类。
    另外，受k值的影响，结果可能会发生改变：

    这个示例中，当k=1的时候，只有蓝色正方形，结果判定为蓝色正方形类别，当k=3的时候，红色类别有2个，蓝色类别还是1个，通过投票法，这时候类别判定为红色三角形。

knn算法核心步骤：

      1、存数据：KNN 是 “懒惰算法”，训练时只存数据不建模

      2、算距离：新点与所有训练点算距离（常用欧氏距离）

      3、选邻居：取距离最小的 k 个

      4、投票 / 平均：

                 分类：多数表决

                 回归：取 k 邻均值

     其中，欧式距离计算公式：

    就是计算(x1,y1)到坐标点(x2,y2)的距离。

    本例子，训练集使用手写数字识别常用的数据集，测试集因为本来就是官方自带的例子，所以用这个来测试，意义并不是很大，我们就直接用我们手写的数字来进行测试。
     常用数字识别自带的数据集，是一个文本形式，把数字通过0，1来组成一个32*32的矩阵，数字显示部分用1填充，空白使用0来填充。

  如上图所示，这是一个训练集文本，以及文本内容，展示的是数字0的形状。

   我们手写数字是图片形式，要变为文本格式，中间需要做一个转换，先加载图片，然后根据像素点的color来展示1或者0，通常我们如果是黑白照片，那么黑色部分像素点通常是000000，数字表示就是(0,0,0)，用一维表示就是0，而白色部分是ffffff，用数字表示本来是(255,255,255)，但是这个用一维表示，我们就简单用1表示。
       我自己准备的手写数字0-9：  

    手写数字，我们采用的是32*32像素，通过windows自带的paint画图工具书写的。

    完整代码示例：

import numpy as np
import operator
import os
from PIL import Image


def img2vector(filename):
    res = np.zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        line_str = fr.readline()
        for j in range(32):
            res[0, i * 32 + j] = int(line_str[j])
    fr.close()
    return res

def img2array(filename):
    res = np.zeros((1, 1024))
    img = Image.open(filename)
    for i in range(32):
        for j in range(32):
            color = img.getpixel((j, i))
            pixel = color[0]+color[1]+color[2]
            if pixel > 170:
                res[0, i * 32 + j] = 0
            else:
                res[0, i * 32 + j] = 1
    img.close()
    return res



def classify(in_x, data_set, labels, k):
    data_set_size = data_set.shape[0]
    diff_mat = np.tile(in_x, (data_set_size, 1)) - data_set
    sq_diff_mat = diff_mat ** 2
    sq_distances = sq_diff_mat.sum(axis=1)
    distances = sq_distances ** 0.5
    sorted_distance = distances.argsort()
    class_count = {}
    for i in range(k):
        vote = labels[sorted_distance[i]]
        class_count[vote] = class_count.get(vote, 0) + 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]


def class_test():
    labels = []
    train_file_list = os.listdir("trainingDigits")
    m_train = len(train_file_list)
    train_mat = np.zeros((m_train, 1024))
    for i in range(m_train):
        file_str = train_file_list[i]
        file_name = file_str.split(".")[0]
        class_num = file_name.split("_")[0]
        labels.append(class_num)
        train_mat[i, :] = img2vector("trainingDigits/" + file_str)
    '''
    test_file_list = os.listdir("testDigits")
    error_count = 0
    m_test = len(test_file_list)
    for i in range(m_test):
        file_str = test_file_list[i]
        file_name = file_str.split(".")[0]
        class_num = file_name.split("_")[0]
        vector_under_test = img2vector("testDigits/" + file_str)
        classified_vector = classify(vector_under_test, train_mat, labels, 3)
        print("the classifier came back with: %d,the real answer is : %d" % (int(classified_vector), int(class_num)))
        if classified_vector != class_num: error_count += 1

    print('\n the total number of errors is : %d' % error_count)
    print('\n the total error rate is :%f' % (error_count / float(m_test)))
    '''
    error_count = 0
    test_file_list = os.listdir("images")
    len_test_file = len(test_file_list)
    for i in range(len_test_file):
        file_str = test_file_list[i]
        file_name = file_str.split(".")[0]
        array_predict = img2array("images/" + file_str)
        classified_vector = classify(array_predict, train_mat, labels, 3)
        print("real number is %d, predicted number is %d" % (int(file_name), int(classified_vector)))
        if classified_vector != file_name: error_count +=1
    print('\n the total number of errors is : %d' % error_count)

if __name__ == '__main__':
    class_test()

      运行结果：

real number is 0, predicted number is 0
real number is 1, predicted number is 1
real number is 2, predicted number is 2
real number is 3, predicted number is 3
real number is 4, predicted number is 4
real number is 5, predicted number is 5
real number is 6, predicted number is 6
real number is 7, predicted number is 7
real number is 8, predicted number is 8
real number is 9, predicted number is 9

 the total number of errors is : 0

 

   看似全部识别，其实，我这是改进了手写数字，刚开始，只识别了6个，4个错误，然后把错误的数字重新书写，逐渐让它识别了所有的数字。

    knn可以说是最直观的做数字识别的方法，手写数字，它不比打印体，同样的数字可能就有些许差别，每个人写出来不一样，所以它采用一种近似的计算，找到最接近的数字。所以在我们的手写中，经常会出现0识别成1，3识别成8，5识别成6，8识别成9。

    代码和资源位置：https://gitee.com/buejee/machinelearning01.git