作业：使用KNN识别MNIST手写数据集（手写，不使用KNeighborsClassifier）

小咪咪 2023-03-04 02:15 71阅读 0赞

[数据集][Link 1]  
提取码：mrfr

浏览本文前请先搞懂K近邻的基本原理：[最简单的分类算法之一：KNN（原理解析+代码实现）][KNN]

算法实现步骤：

1.  数据处理。每一个数字都是一个32X32维的数据，如下所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
    knn中**邻居**一词指的就是距离相近。我们要想计算两个样本之间的距离，就必须将每一个数字变成一个向量。具体做法就是将32X32的数据每一行接在一起，形成一个1X1024的数据，这样我们就可以计算欧式距离。
2.  计算测试数据到所有训练数据的距离，并按照从小到大排序，选出前K个
3.  根据距离计算前K个样本的权重
4.  将相同的训练样本的权重加起来，返回权重最大样本的标签

代码实现：

import os
    
    def load_data(path):
        check = [i for i in range(10)]
        final_data = []
        
        for i in range(10):
            final_data.append([])
            
        files = os.listdir(path)    #文件夹
        for file in files:
            data = open(path + "/" + file)
            str = ""      #将所有数据接在一起
            temp = []
            for line in data.readlines():
                str = str + line[:-1]   #去掉回车，一行接一行
            for i in str:
                temp.append(int(i))   #变成数字
            final_data[check.index(int(file[0]))].append(temp)   #根据标签放在列表相应的位置
    
        return final_data, len(files)
    
    def knn_mnist(K,test_data):
        train_data, length = load_data('manifold/digits/trainingDigits')
        distance = []     #存储测试数据到所有训练数据的距离
        
        for i in range(len(train_data)):
            for j in range(len(train_data[i])):
                res = 0
                for k in range(len(test_data)):
                    res += (test_data[k]-train_data[i][j][k]) ** 2   #欧氏距离
                distance.append([res ** 0.5, i])   #距离+训练集数据标签
    
        distance = sorted(distance, key=(lambda x: x[0]))  #按距离从小到大排序
        weight = []   #权重与序号
        sum_distance = 0.0
        for i in range(K):
            sum_distance += distance[i][0]   #计算前K个距离的和
        for i in range(K):
            weight.append([1 - distance[i][0] / sum_distance, distance[i][1]])  #权重+序号
            
        #将相同序号的加起来
        num = []   #统计有哪些序号
        for i in range(K):
            num.append(weight[i][1])
        num = list(set(num))   #去重
        
        final_res = []
        for i in range(len(num)):
            res = 0.0
            for j in range(len(weight)):
                if weight[j][1] == num[i]:   #前K个标签一样的样本权值加起来
                    res += weight[j][0]
            final_res.append([res, num[i]])
    
        final_res = sorted(final_res, key=(lambda x: x[0]),reverse=True)  # 按照权重从大到小排序
    
        return final_res[0][1]   #最终返回最大权值对应的标签
    
    def test():
        K = 5
        test_data, length = load_data('manifold/digits/testDigits')
        #测试
        for i in range(len(test_data)):
            for j in range(len(test_data[i])):
                print(knn_mnist(K, test_data[i][j]))
    
    if __name__ == '__main__':
        test()

[Link 1]: https://pan.baidu.com/s/1cTS5JF9I96a74fAU3YmLrA
[KNN]: https://blog.csdn.net/Cyril_KI/article/details/107302163
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20230208/5723f652954a494b9f05e59186726873.png