前言

随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容——k近邻算法及python的实现。

提示：以下是本篇文章正文内容，下面案例可供参考

一、k近邻算法是什么？

????????K最近邻（k—Nearest Neighborhood，KNN）分类算法，是1967年由Cover T和Hart P提出的一种基本分类与回归方法，也是最简单的机器学习算法之一。该方法的思路是：在特征空间中，如果一个样本附近的k个最近(即特征空间中最邻近)样本的大多数属于某一个类别，则该样本也属于这个类别。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。（近朱者赤近墨者黑）

????????

二、k-近邻算法实战之sklearn手写数字识别

1.k-近邻算法的一般流程

（1）收集数据：可以使用爬虫进行数据的收集，也可以使用第三方提供的免费或收费的数据。一般来讲，数据放在txt文本文件中，按照一定的格式进行存储，便于解析及处理。
（2）准备数据：使用Python解析、预处理数据。
（3）分析数据：可以使用很多方法对数据进行分析，例如使用Matplotlib将数据可视化。
（4）测试算法：计算错误率。
（5）使用算法：错误率在可接受范围内，就可以运行k-近邻算法进行分类。

2.实战背景?? ?

本节我们一步步地构造使用 K 近邻分类器的手写识别系统。为了简单起见，这里构造的系统只能识别数字 0 到 9，参见图 1-1。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小 1：宽高是 32 像素 x 32 像素的黑白图像。

尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 图1-1? ?手写数字数字数据集的例子

?????????为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个 32x32 的二进制图像矩阵转换为 1x1024 的向量，这样前两节使用的分类器就可以处理数字图像信息了。

3.准备数据：将图像转换为测试向量

下载数据集：
http://labfile.oss.aliyuncs.com/courses/777/digits.zip（来源网络）
digits 目录下有两个文件夹，分别是:
trainingDigits：训练数据，1934 个文件，每个数字大约 200 个文件。
testDigits：测试数据，946 个文件，每个数字大约 100 个文件。
每个文件中存储一个手写的数字，文件的命名类似 0_7.txt，第一个数字 0 表示文件中的手写数字是 0，后面的 7 是个序号。

????????我们首先编写一段函数 img2vector，将图像转换为向量：该函数创建 1x1024 的 NumPy 数组，然后打开给定的文件，循环读出文件的前 32 行，并将每行的头 32 个字符值存储在 NumPy 数组中，最后返回数组。????????

def img2vector(filename):
? ? returnVect = zeros((1,1024))
? ? fr = open(filename)
? ? for i in range(32):
? ? ? ? lineStr = fr.readline()
? ? ? ? for j in range(32):
? ? ? ? ? ? returnVect[0,32*i+j] = int(lineStr[j])
? ? return returnVect
然后在Python命令行中输入下列命令测试img2vector函数，然后与文本编辑器打开的文件进行比较：
>>> testVector = kNN.img2vector('testDigits/0_13.txt')
>>> testVector[0,0:31]
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])
>>> testVector[0,31:63]
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])

4.测试算法

我们已经将数据处理成分类器可以识别的格式。接下来，我们将这些数据输入到分类器，检测分类器的执行效果。在写入这些代码之前，我们必须确保将 from os import listdir 写入文件的起始部分，这段代码的主要功能是从 os 模块中导入函数 listdir，它可以列出给定目录的文件名。

测试的步骤：

（1）读取训练数据到向量（手写图片数据），从数据文件名中提取类别标签列表（每个向量对应的真实的数字）
（2）读取测试数据到向量，从数据文件名中提取类别标签
（3）执行K 近邻算法对测试数据进行测试，得到分类结果
（4）与实际的类别标签进行对比，记录分类错误率
（5）打印每个数据文件的分类数据及错误率作为最终的结果

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('digits/trainingDigits')
    m = len(trainingFileList)
    trainingMat = np.zeros((m, 1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i, :] = img2vector(
            'digits/trainingDigits/%s' % fileNameStr)
    testFileList = listdir('digits/testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('digits/testDigits/%s' % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("测试样本 %d, 分类器预测: %d, 真实类别: %d" %
              (i+1, classifierResult, classNumStr))

        # 判断K 近邻算法结果是否准确
        if (classifierResult != classNumStr):
            errorCount += 1.0

    # 打印错误率
    print("\n错误分类计数: %d" % errorCount)
    print("\n错误分类比例: %f" % (errorCount/float(mTest)))

?最后，输入 handwritingClassTest()，测试该函数的输出结果：

kNN.handwritingClassTest()
the classifier came back with:6, the real answer is: 0
the classifier came back with:4, the real answer is: 0
………………
the classifier came back with:1, the real answer is: 7
the classifier came back with:1, the real answer is: 7
the classifier came back with:7, the real answer is: 7
the classifier came back with:0, the real answer is: 8

………………
the classifier came back with:7, the real answer is: 9
the classifier came back with:9, the real answer is: 9


the total number of errors is: 11

the total error rate is: 0.011628

k-近邻算法识别手写数字数据集，错误率为1.2%。改变k的值、修改函数handwritingClassTest随机选取训练样本、改变训练样本的数目，都会对k-近邻算法的错误率产生影响。