机器学习实例---1.3、k-近邻算法（数字识别）
一、总结
一句话总结：
原理非常简单，这里的每个数字都是1024维的向量，由0和1组成，【求解的时候就是求测试的点（那个1024维数据）和所有训练数据（也是一个个1024维数据）的距离】，然后根据【最近的k个】来确定分类即可
相比于简单knn和海伦约会的例子，只不过是数据维数变多了，以及训练数据量变多了而已，其它完全无区别，甚至核心函数都是一模一样，都是classify0：classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
其实直观也很好想：因为这些数字都由0和1组成，【相同的数字，0和1的位置也接近，自然距离就小】，这里求距离就只用到了0和1，不过这个和深度学习比起来太麻烦了，因为这里有【特征提取】
def handwritingClassTest(): #测试集的Labels hwLabels = [] #返回trainingDigits目录下的文件名 trainingFileList = listdir('trainingDigits') #返回文件夹下文件的个数 m = len(trainingFileList) #初始化训练的Mat矩阵,测试集 trainingMat = np.zeros((m, 1024)) #从文件名中解析出训练集的类别 for i in range(m): #获得文件的名字 fileNameStr = trainingFileList[i] #获得分类的数字 classNumber = int(fileNameStr.split('_')[0]) #将获得的类别添加到hwLabels中 hwLabels.append(classNumber) #将每一个文件的1x1024数据存储到trainingMat矩阵中 trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr)) #返回testDigits目录下的文件名 testFileList = listdir('testDigits') #错误检测计数 errorCount = 0.0 #测试数据的数量 mTest = len(testFileList) #从文件中解析出测试集的类别并进行分类测试 for i in range(mTest): #获得文件的名字 fileNameStr = testFileList[i] #获得分类的数字 classNumber = int(fileNameStr.split('_')[0]) #获得测试集的1x1024向量,用于训练 vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr)) #获得预测结果 classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print("分类返回结果为%d 真实结果为%d" % (classifierResult, classNumber)) if(classifierResult != classNumber): errorCount += 1.0 print("总共错了%d个数据 错误率为%f%%" % (errorCount, errorCount/mTest))
1、KNN缩写？
k-nearest neighbor，也就是最近的邻居
2、KNN的Sklearn库实现？
neigh = kNN(n_neighbors = 3, algorithm = 'auto') #构建kNN分类器
neigh.fit(trainingMat, hwLabels) #拟合模型, trainingMat为训练矩阵,hwLabels为对应的标签
classifierResult = neigh.predict(vectorUnderTest) #获得预测结果
def handwritingClassTest(): #测试集的Labels hwLabels = [] #返回trainingDigits目录下的文件名 trainingFileList = listdir('trainingDigits') #返回文件夹下文件的个数 m = len(trainingFileList) #初始化训练的Mat矩阵,测试集 trainingMat = np.zeros((m, 1024)) #从文件名中解析出训练集的类别 for i in range(m): #获得文件的名字 fileNameStr = trainingFileList[i] #获得分类的数字 classNumber = int(fileNameStr.split('_')[0]) #将获得的类别添加到hwLabels中 hwLabels.append(classNumber) #将每一个文件的1x1024数据存储到trainingMat矩阵中 trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr)) #构建kNN分类器 neigh = kNN(n_neighbors = 3, algorithm = 'auto') #拟合模型, trainingMat为训练矩阵,hwLabels为对应的标签 neigh.fit(trainingMat, hwLabels) #返回testDigits目录下的文件列表 testFileList = listdir('testDigits') #错误检测计数 errorCount = 0.0 #测试数据的数量 mTest = len(testFileList) #从文件中解析出测试集的类别并进行分类测试 for i in range(mTest): #获得文件的名字 fileNameStr = testFileList[i] #获得分类的数字 classNumber = int(fileNameStr.split('_')[0]) #获得测试集的1x1024向量,用于训练 vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr)) #获得预测结果 # classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) classifierResult = neigh.predict(vectorUnderTest) print("分类返回结果为%d 真实结果为%d" % (classifierResult, classNumber)) if(classifierResult != classNumber): errorCount += 1.0 print("总共错了%d个数据 错误率为%f%%" % (errorCount, errorCount/mTest * 100))
3、kNN算法的优点？
【简单】好用，容易理解，【精度高】，理论成熟，既可以用来做【分类】也可以用来做【回归】；
可用于【数值型数据】和【离散型数据】；
训练时间复杂度为O(n)；【无数据输入假定】；
对【异常值不敏感】。
4、kNN算法的缺点？
【计算复杂性高；空间复杂性高】；
【样本不平衡问题】（即有些类别的样本数量很多，而其它样本的数量很少）；
一般数值很大的时候不用这个，【计算量太大】。但是单个样本又不能太少，否则容易发生误分。
最大的缺点是【无法给出数据的内在含义】。
二、1.3、k-近邻算法（数字识别）
转自：Python3《机器学习实战》学习笔记（一）：k-近邻算法(史诗级干货长文)_Jack-Cui-CSDN博客_python3机器学习实战
https://blog.csdn.net/c406495762/article/details/75172850
#三 k-近邻算法实战之sklearn手写数字识别
##3.1 实战背景
对于需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素x32像素。尽管采用本文格式存储图像不能有效地利用内存空间，但是为了方便理解，我们将图片转换为文本格式，数字的文本格式如图3.1所示。
图3.1 数字的文本格式
与此同时，这些文本格式存储的数字的文件命名也很有特点，格式为：数字的值_该数字的样本序号，如图3.2所示。
图3.2 文本数字的存储格式
对于这样已经整理好的文本，我们可以直接使用Python处理，进行数字预测。数据集分为训练集和测试集，使用上小结的方法，自己设计k-近邻算法分类器，可以实现分类。
这里不再讲解自己用Python写的k-邻域分类器的方法，因为这不是本小节的重点。接下来，我们将使用强大的第三方Python科学计算库Sklearn构建手写数字系统。
##3.2 Sklearn简介
Scikit learn 也简称sklearn，是机器学习领域当中最知名的python模块之一。sklearn包含了很多机器学习的方式：
- Classification 分类
- Regression 回归
- Clustering 非监督分类
- Dimensionality reduction 数据降维
- Model Selection 模型选择
- Preprocessing 数据与处理
使用sklearn可以很方便地让我们实现一个机器学习算法。一个复杂度算法的实现，使用sklearn可能只需要调用几行API即可。所以学习sklearn，可以有效减少我们特定任务的实现周期。
##3.3 Sklearn安装
在安装sklearn之前，需要安装两个库，即numpy+mkl和scipy。不要使用pip3直接进行安装，因为pip3默安装的是numpy，而不是numpy+mkl。第三方库下载地址：http://www.lfd.uci.edu/~gohlke/pythonlibs/
这个网站的使用方法，我在之前的文章里有讲过：http://blog.csdn.net/c406495762/article/details/60156205
找到对应python版本的numpy+mkl和scipy，下载安装即可，如图3.1和图3.2所示。
图3.1 numpy+mkl
图3.2 scipy
使用pip3安装好这两个whl文件后，使用如下指令安装sklearn。
pip3 install -U scikit-learn
##3.4 Sklearn实现k-近邻算法简介
sklearn.neighbors模块实现了k-近邻算法，内容如图3.3所示。
图3.3 sklearn.neighbors
我们使用sklearn.neighbors.KNeighborsClassifier就可以是实现上小结，我们实现的k-近邻算法。KNeighborsClassifier函数一共有8个参数，如图3.4所示。
图3.4 KNeighborsClassifier
KNneighborsClassifier参数说明：
- n_neighbors：默认为5，就是k-NN的k的值，选取最近的k个点。
- weights：默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。
- algorithm：快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。ball tree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。
- leaf_size：默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
- metric：用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。
- p：距离度量公式。在上小结，我们使用欧氏距离公式进行距离度量。除此之外，还有其他的度量方法，例如曼哈顿距离。这个参数默认为2，也就是默认使用欧式距离公式进行距离度量。也可以设置为1，使用曼哈顿距离公式进行距离度量。
- metric_params：距离公式的其他关键参数，这个可以不管，使用默认的None即可。
- n_jobs：并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。
KNeighborsClassifier提供了以一些方法供我们使用，如图3.5所示。
图3.5 KNeighborsClassifier的方法
由于篇幅原因，每个函数的怎么用，就不具体讲解了。官方手册已经讲解的很详细了，各位可以查看这个手册进行学习，我们直接讲手写数字识别系统的实现。
##3.5 Sklearn小试牛刀
我们知道数字图片是32x32的二进制图像，为了方便计算，我们可以将32x32的二进制图像转换为1x1024的向量。对于sklearn的KNeighborsClassifier输入可以是矩阵，不用一定转换为向量，不过为了跟自己写的k-近邻算法分类器对应上，这里也做了向量化处理。然后构建kNN分类器，利用分类器做预测。创建kNN_test04.py文件，编写代码如下：
# -*- coding: UTF-8 -*-
import numpy as np
import operator
from os import listdir
from sklearn.neighbors import KNeighborsClassifier as kNN
"""
函数说明:将32x32的二进制图像转换为1x1024向量。
Parameters:
filename - 文件名
Returns:
returnVect - 返回的二进制图像的1x1024向量
Modify:
2017-07-15
"""
def img2vector(filename):
#创建1x1024零向量
returnVect = np.zeros((1, 1024))
#打开文件
fr = open(filename)
#按行读取
for i in range(32):
#读一行数据
lineStr = fr.readline()
#每一行的前32个元素依次添加到returnVect中
for j in range(32):
returnVect[0, 32*i+j] = int(lineStr[j])
#返回转换后的1x1024向量
return returnVect
"""
函数说明:手写数字分类测试
Parameters:
无
Returns:
无
Modify:
2017-07-15
"""
def handwritingClassTest():
#测试集的Labels
hwLabels = []
#返回trainingDigits目录下的文件名
trainingFileList = listdir('trainingDigits')
#返回文件夹下文件的个数
m = len(trainingFileList)
#初始化训练的Mat矩阵,测试集
trainingMat = np.zeros((m, 1024))
#从文件名中解析出训练集的类别
for i in range(m):
#获得文件的名字
fileNameStr = trainingFileList[i]
#获得分类的数字
classNumber = int(fileNameStr.split('_')[0])
#将获得的类别添加到hwLabels中
hwLabels.append(classNumber)
#将每一个文件的1x1024数据存储到trainingMat矩阵中
trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr))
#构建kNN分类器
neigh = kNN(n_neighbors = 3, algorithm = 'auto')
#拟合模型, trainingMat为测试矩阵,hwLabels为对应的标签
neigh.fit(trainingMat, hwLabels)
#返回testDigits目录下的文件列表
testFileList = listdir('testDigits')
#错误检测计数
errorCount = 0.0
#测试数据的数量
mTest = len(testFileList)
#从文件中解析出测试集的类别并进行分类测试
for i in range(mTest):
#获得文件的名字
fileNameStr = testFileList[i]
#获得分类的数字
classNumber = int(fileNameStr.split('_')[0])
#获得测试集的1x1024向量,用于训练
vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))
#获得预测结果
# classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
classifierResult = neigh.predict(vectorUnderTest)
print("分类返回结果为%d 真实结果为%d" % (classifierResult, classNumber))
if(classifierResult != classNumber):
errorCount += 1.0
print("总共错了%d个数据
错误率为%f%%" % (errorCount, errorCount/mTest * 100))
"""
函数说明:main函数
Parameters:
无
Returns:
无
Modify:
2017-07-15
"""
if __name__ == '__main__':
handwritingClassTest()
运行上述代码，得到如图3.6所示的结果。
图3.6 sklearn运行结果
上述代码使用的algorithm参数是auto，更改algorithm参数为brute，使用暴力搜索，你会发现，运行时间变长了，变为10s+。更改n_neighbors参数，你会发现，不同的值，检测精度也是不同的。自己可以尝试更改这些参数的设置，加深对其函数的理解。
#四 总结
##4.1 kNN算法的优缺点
优点
- 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
- 可用于数值型数据和离散型数据；
- 训练时间复杂度为O(n)；无数据输入假定；
- 对异常值不敏感。
缺点：
- 计算复杂性高；空间复杂性高；
- 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
- 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
- 最大的缺点是无法给出数据的内在含义。
##4.2 其他
- 关于algorithm参数kd_tree的原理，可以查看《统计学方法 李航》书中的讲解；
- 关于距离度量的方法还有切比雪夫距离、马氏距离、巴氏距离等；
- 下篇文章将讲解决策树，欢迎各位届时捧场！
- 如有问题，请留言。如有错误，还望指正，谢谢！