K近邻（KNN，k-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。 所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特征。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少数的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或者重叠较多的待分样本集来说，kNN方法较其他方法更为适合。
众所周知，电影可以按照题材分类，然而题材本身是如何定义的？由谁来判断某部电影属于哪个题材？也就是说同一题材的电影具有哪些公共特征？这些都是在进行电影分类时必须要考虑的问题。没有哪个电影人会说自己制作的电影和以前的某部电影类似，但是我们确实知道每部电影在风格上的确有可能会和同题材的电影相近。那么动作片具有哪些共有特征，使得动作片之间非常类似，而与爱情片存在着明显的差距呢？动作片中也会存在接吻镜头，爱情片中也会存在打斗场景，我们不能单纯依靠是否存在打斗或者亲吻来判断影片的类型，但是爱情片中的接吻镜头更多，动作片中的打斗场景也更为频繁，基于此类场景在某部电影中出现的次数可以用来进行电影分类。本文基于电影中出现的亲吻，打斗出现的次数，使用 K-近邻算法构造程序，自动划分电影的题材类型。我们首先使用电影分类讲解 K-近邻算法的基础概念，然后学习如何在其他系统上使用 K-近邻算法。
那么本次首先探讨 K-近邻算法的基础理论，以及如何使用距离测量的方法分类物品；其次我们使用Python从文本文件中导入并解析数据，再次，本文学习了当存在许多数据来源时，如何避免计算距离时可能会碰到的一些错误，最后利用实际的例子讲解如何使用 K-近邻算法改进约会网站和手写数字识别系统，而且实战中将使用自己编写代码和使用sklearn两种方式编写。
简单来说 K-近邻算法采用测量不同特征值之间的距离方法进行分类。
K最近邻(k-Nearest Neighbor，KNN)，是一种常用于分类的算法，是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是：如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的大多数属于某一个类别，则该样本也属于这个类别，即近朱者赤，近墨者黑。显然，对当前待分类样本的分类，需要大量已知分类的样本的支持，其中k通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最近邻的一个或者几个样本的类别来决定待分样本所属的类别。因此KNN是一种有监督学习算法。
最简单最初级的分类器时将全部的训练数据所对应的类别都记录下来，当测试对象的属性和某个训练对象的属性完全匹配时，便可以对其进行分类，但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢，其次就是存在一个测试对象同时与多个训练对象匹配，导致一个训练对象被分到了多个类的问题，基于这些问题呢，就产生了KNN。
下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形？还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形所属的类，如果K = 5 ,由于蓝色四边形比例为3/5，因此绿色圆被赋予蓝色四边形类。
由此也说明了KNN算法的结果很大程序取决于K的选择。
在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧式距离或者曼哈顿距离：
同时，KNN通过依据k个对象中占优的类别进行决策，而不是单一的对象类别决策。这两点算是KNN算法的优势。
接下来对KNN算法的思想总结一下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该册数数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述如下：
（1）：计算测试数据与各个训练数据之间的距离
（2）：按照距离的递增关系进行排序
（3）：选取距离最小的K个点
（4）：确定前K个点所在类别的出现频率
（5）：返回前K个点中出现频率最高的类别作为测试数据的预测分类
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入每一标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是 K-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
现在我们回到前面电影分类的例子，使用 K-近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头。假设有一部未看过的电影，如何确定它是爱情片还是动作片呢？我们可以使用KNN来解决这个问题。
首先我们需要知道这个未知电影存在多少个打斗镜头和接吻镜头，具体数字参见表2-1。
表1.1 就是我们已有的数据集合，也就是训练样本集。这个数据集有两个特征，即打斗镜头数和接吻镜头数。除此之外，我们也知道每个电影的所属类型，即分类标签。用肉眼粗略地观察，接吻镜头多的，是爱情片。打斗镜头多的，是动作片。以我们多年的看片经验，这个分类还算合理。如果现在给我一部电影，你告诉我这个电影打斗镜头数和接吻镜头数。不告诉我这个电影类型，我可以根据你给我的信息进行判断，这个电影是属于爱情片还是动作片。而k-近邻算法也可以像我们人一样做到这一点，不同的地方在于，我们的经验更"牛逼"，而k-近邻算法是靠已有的数据。比如，你告诉我这个电影打斗镜头数为2，接吻镜头数为102，我的经验会告诉你这个是爱情片，k-近邻算法也会告诉你这个是爱情片。你又告诉我另一个电影打斗镜头数为49，接吻镜头数为51，我"邪恶"的经验可能会告诉你，这有可能是个"爱情动作片"，但是k-近邻算法不会告诉你这些，因为在它的眼里，电影类型只有爱情片和动作片，它会提取样本集中特征最相似数据(最邻近)的分类标签，得到的结果可能是爱情片，也可能是动作片，但绝不会是"爱情动作片"。当然，这些取决于数据集的大小以及最近邻的判断标准等因素。
我们已经知道k-近邻算法根据特征比较，然后提取样本集中特征最相似数据（最邻近）的分类标签。那么如何进行比较呢？比如我们以下表为例，怎么判断红色圆点标记的电影所属类别呢？
我们从散点图大致推断，这个红色圆点标记的电影可能属于动作片，因为距离已知的那两个动作片的圆点更近，那么k-近邻算法用什么方法进行判断呢？没错，就是距离度量，这个电影分类的例子有两个特征，也就是二维实数向量空间，可以使用我们学过的两点距离公式计算距离（欧式距离），如下图：
通过计算，我们可以得到如下结果：
通过计算可知，红色圆点标记的电影到动作片 (108,5)的距离最近，为16.55。如果算法直接根据这个结果，判断该红色圆点标记的电影为动作片，这个算法就是最近邻算法，而非k-近邻算法。那么k-近邻算法是什么呢？下面我们学习一下k-近邻算法步骤
（1）收集数据：可以使用任何方法。包括爬虫，或者第三方提供的免费或收费数据
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式（计算测试数据与各个训练数据之间的距离）
（3）分析数据：可以使用任何方法。此处使用Python解析，预处理数据
（4）训练算法：此步骤不适用于k-近邻算法
（5）测试算法：计算错误率
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判断输入数据分别属于哪个类别，最后应用对计算出的分类执行后续的处理
比如我这里取k值为3，那么在电影例子中，按照距离依次排序的三个点分别是动作片(108,5)、动作片(115,8)、爱情片(5,89)。在这三个点中，动作片出现的频率为三分之二，爱情片出现的频率为三分之一，所以该红色圆点标记的电影为动作片。这个判别过程就是k-近邻算法
我们已经知道了k-近邻算法的原理，下面使用Python实现算法，前面学习了Python导入数据，后面使用约会网站配对效果判断的例子进行学习。
首先，导入数据
#_*_coding:utf-8_*_
from numpy import *
# 获取数据
import operator
def creataDataSet():
'''
labels中 A代表爱情片 B代表动作片
:return:
'''
group = array([[1,101],[5,89],[108,5],[115,8]])
labels = ['A','A','B','B']
return group,labels
if __name__ == '__main__':
group,labels = creataDataSet()
print(group)
print(labels)
测试输出结果如下：
[[ 1 101]
[ 5 89]
[108 5]
[115 8]]
['A', 'A', 'B', 'B']
首先我们给出了k-近邻算法的伪代码和实际的Python代码，然后详细的解释其含义，该函数的功能是使用k-近邻算法将每组数据划分到某个类中，其伪代码如下：
对未知类别属性的数据集中的每个点依次执行以下操作：
（1） 计算已知类别数据集中的点与当前点之间的距离
（2） 按照距离递增次序排序
（3） 选取与当前点距离最小的k个点
（4） 确定前k个点所在类别的出现频率
（5） 返回前k个点出现频率最高的类别作为当前点的预测分类
其Python函数classify0()的程序代码如下：
# k-近邻算法
def classify0(inX,dataSet,labels,k):
# shape读取数据矩阵第一维度的长度
dataSetSize = dataSet.shape[0]
# tile重复数组inX，有dataSet行 1个dataSet列，减法计算差值
diffMat = tile(inX,(dataSetSize,1)) - dataSet
# **是幂运算的意思，这里用的欧式距离
sqDiffMat = diffMat ** 2
# 普通sum默认参数为axis=0为普通相加，axis=1为一行的行向量相加
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# argsort返回数值从小到大的索引值（数组索引0,1,2,3）
sortedDistIndicies = distances.argsort()
# 选择距离最小的k个点
classCount = {}
for i in range(k):
# 根据排序结果的索引值返回靠近的前k个标签
voteLabel = labels[sortedDistIndicies[i]]
# 各个标签出现频率
classCount[voteLabel] = classCount.get(voteLabel,0) +1
##!!!!! classCount.iteritems()修改为classCount.items()
#sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list。
# reverse默认升序 key关键字排序itemgetter（1）按照第一维度排序(0,1,2,3)
sortedClassCount = sorted(classCount.items(),
key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
classify0()函数有4个输入参数：用于分类的输入向量是inX，输入的训练样本集为dataSet，标签向量为labels，最后的参数k表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵dataSet的行数相同，上面程式使用欧式距离公式。
计算完所有点之间的距离后，可以对数据按照从小到大的次序排序。然后，确定前k个距离最小元素所在的主要分类，输入k总是正整数；最后，将classCount字典分解为元组列表，然后使用程序第二行导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序。此处的排序是逆序，即按照从最大到最小次序排序，最后返回发生频率最高的元素标签。
为了预测数据所在分类，我们输入如下代码：
if __name__ == '__main__':
group,labels = creataDataSet()
knn = classify0([0,0],group,labels,3)
print(knn)
'''
B
'''
输出结果应该是B，也就是动作片。
到目前为止，我们已经构造了第一个分类器，使用这个分类器可以完成很多分类任务。从这个实例出发，构造使用分类算法将会更加容易。
上面我们已经使用k-近邻算法构造了第一个分类器，也可以检验分类器给出的答案是否符合我们的预期，大家可能会问：“分类器何种情况下会出错？”或者“答案是否总是正确的？” 答案是否定的，分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。此外分类器的性能也受到多种因素的影响，如分类器设置和数据集等。不同的算法在不同数据集上的表现可能完全不同。
为了测试分类器的效果，我们可以使用已知答案的数据，当然答案不能告诉分类器，检验分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率——分类器给出的错误结果的次数除了测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为0，最差分类器的错误率是1.0，在这种情况下，分类器根本就无法找到一个正确答案。所以我们不难发现，k-近邻算法没有进行数据的训练，直接使用未知的数据与已知的数据进行比较，得到结果。因此，可以说k-近邻算法不具有显式公式。
上面介绍的例子可以正确运转，但是并没有太大的实际用处，下面我们将在现实世界中使用k-近邻算法。首先，我们将使用k-近邻算法改进约会网站的效果，然后使用k-近邻算法改进手写识别系统。
K太小，分类结果易受噪声点影响；K太大，近邻中又可能包含太多的其他类别的点。（对距离加权，可以降低K值设定的影响）
K值通常是采用交叉检验来确定
经验规则：K一般低于训练样本数的平方根
投票法没有考虑近邻的距离远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更加恰当一些。
高维度对距离衡量的影响：众所周知当变量数越多，欧氏距离的区分能力就越差。
变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应当对变量进行标准化。
在训练集中 ，有些样本可能是更值得依赖的
可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。
KNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时找k个近邻）。
懒惰的后果：构造模型很简单，但是对测试样本分类的系统开销很大，因为要扫描全部训练样本并计算距离。
已经有一些方法提高计算的效率，例如压缩训练样本量等。
浓缩技术（condensing）
编辑技术（editing）
James一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但是他从来没有选中喜欢的人，经过一番总结，他发现曾交往过三种类型的人：
尽管发现了上述归类，但是他依然无法将约会网站推荐的匹配对象归入恰当的分类。他觉得可以在周一到周五约会哪些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。James希望分类软件可以更好地帮助他将匹配对象划分到确切的分类中，此外他还收集了一些约会网站未曾记录的数据信息，他认为这些数据更有助于匹配对象的归类。
（1）收集数据：提供文本文件
（2）准备数据：使用Python解析文本文件
（3）分析数据：使用Matplotlib画二维扩散图
（4）训练算法：此步骤不适用于k-近邻算法
（5）测试算法：使用James提供的部分数据作为测试样本
测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
（6）使用算法：产生简单的命令程序，然后James可以输入一些特征数据以判断对方是否为自己喜欢的类型。
James收集的数据有一段时间了，她将这些数据放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行，James的样本主要包括以下三种特征：
在将数据特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式，我们首先处理输入格式问题，该函数的输入问文件名字符串，输出为训练样本矩阵和类标签向量。
将文本记录到转换Numpy的解析程序代码如下：
# 将文本记录到转换Numpy的解析程序
def file2Matrix(filename):
fr = open(filename)
arrayOLines = fr.readlines()
# 得到文件行数
numberOfLines = len(arrayOLines)
# 创建返回的Numpy矩阵
returnMat = zeros((numberOfLines,3))
classLabelVector = []
index = 0
# 解析文件数据到列表
for line in arrayOLines:
# 删除空白行
line = line.strip()
listFromLine = line.split('\t')
# 选取前3个元素（特征）存储在返回矩阵中
returnMat[index,:] = listFromLine[0:3]
# -1索引表示最后一列元素,位label信息存储在classLabelVector
classLabelVector.append(int(listFromLine[-1]))
index += 1
return returnMat,classLabelVector
从上面代码可以看到，处理文本文件非常容易，下面我们测试一下，Python输出的结果。
if __name__ == '__main__':
filename = 'datingTestSet2.txt'
datingDataMat,datingLabels = file2Matrix(filename)
print(datingDataMat)
print(datingLabels)
'''
[[4.0920000e+04 8.3269760e+00 9.5395200e-01]
[1.4488000e+04 7.1534690e+00 1.6739040e+00]
[2.6052000e+04 1.4418710e+00 8.0512400e-01]
...
[2.6575000e+04 1.0650102e+01 8.6662700e-01]
[4.8111000e+04 9.1345280e+00 7.2804500e-01]
[4.3757000e+04 7.8826010e+00 1.3324460e+00]]
[3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 2, 3, 2, 3, 2, 3, 2, 1, 3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 1, 2, 3, 3, 3, 1, 1, 1, 1, 2, 2, 1, 3, 2, 2, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 2, 3, 2, 3, 1, 2, 3, 2, 2, 1, 3, 1, 1, 3, 3, 1, 2, 3, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 2, 1, 3, 3, 2, 1, 1, 3, 1, 2, 3, 3, 2, 3, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 1, 2, 3, 2, 3, 2, 3, 2, 1, 3, 3, 3, 1, 3, 2, 2, 3, 1, 3, 3, 3, 1, 3, 1, 1, 3, 3, 2, 3, 3, 1, 2, 3, 2, 2, 3, 3, 3, 1, 2, 2, 1, 1, 3, 2, 3, 3, 1, 2, 1, 3, 1, 2, 3, 2, 3, 1, 1, 1, 3, 2, 3, 1, 3, 2, 1, 3, 2, 2, 3, 2, 3, 2, 1, 1, 3, 1, 3, 2, 2, 2, 3, 2, 2, 1, 2, 2, 3, 1, 3, 3, 2, 1, 1, 1, 2, 1, 3, 3, 3, 3, 2, 1, 1, 1, 2, 3, 2, 1, 3, 1, 3, 2, 2, 3, 1, 3, 1, 1, 2, 1, 2, 2, 1, 3, 1, 3, 2, 3, 1, 2, 3, 1, 1, 1, 1, 2, 3, 2, 2, 3, 1, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2, 3, 3, 3, 3, 1, 2, 3, 1, 1, 1, 3, 1, 3, 2, 2, 1, 3, 1, 3, 2, 2, 1, 2, 2, 3, 1, 3, 2, 1, 1, 3, 3, 2, 3, 3, 2, 3, 1, 3, 1, 3, 3, 1, 3, 2, 1, 3, 1, 3, 2, 1, 2, 2, 1, 3, 1, 1, 3, 3, 2, 2, 3, 1, 2, 3, 3, 2, 2, 1, 1, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3, 3, 3, 2, 3, 2, 1, 1, 1, 1, 1, 3, 2, 2, 1, 2, 1, 3, 2, 1, 3, 2, 1, 3, 1, 1, 3, 3, 3, 3, 2, 1, 1, 2, 1, 3, 3, 2, 1, 2, 3, 2, 1, 2, 2, 2, 1, 1, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 3, 1, 1, 2, 2, 1, 2, 2, 2, 3, 1, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 1, 3, 2, 3, 3, 2, 2, 1, 1, 1, 2, 1, 2, 2, 3, 3, 3, 1, 1, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 1, 2, 3, 2, 1, 1, 1, 1, 3, 3, 3, 3, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 2, 2, 2, 3, 2, 1, 3, 2, 3, 2, 3, 2, 1, 1, 2, 3, 1, 3, 3, 3, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 1, 3, 3, 2, 2, 2, 3, 1, 2, 1, 1, 3, 2, 3, 2, 3, 2, 3, 3, 2, 2, 1, 3, 1, 2, 1, 3, 1, 1, 1, 3, 1, 1, 3, 3, 2, 2, 1, 3, 1, 1, 3, 2, 3, 1, 1, 3, 1, 3, 3, 1, 2, 3, 1, 3, 1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 3, 1, 3, 1, 1, 2, 2, 2, 3, 2, 2, 1, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 1, 3, 2, 3, 2, 1, 2, 1, 1, 1, 2, 3, 2, 2, 1, 2, 2, 1, 3, 1, 3, 3, 3, 2, 2, 3, 3, 1, 2, 2, 2, 3, 1, 2, 1, 3, 1, 2, 3, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 2, 2, 3, 1, 3, 1, 2, 3, 2, 2, 3, 1, 2, 3, 2, 3, 1, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 3, 3, 3, 1, 1, 3, 1, 2, 3, 3, 2, 2, 2, 1, 2, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 1, 3, 2, 1, 3, 3, 1, 2, 3, 2, 1, 3, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 1, 1, 2, 1, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 2, 2, 1, 2, 2, 1, 3, 1, 3, 1, 3, 3, 1, 1, 2, 3, 2, 2, 3, 1, 1, 1, 1, 3, 2, 2, 1, 3, 1, 2, 3, 1, 3, 1, 3, 1, 1, 3, 2, 3, 1, 1, 3, 3, 3, 3, 1, 3, 2, 2, 1, 1, 3, 3, 2, 2, 2, 1, 2, 1, 2, 1, 3, 2, 1, 2, 2, 3, 1, 2, 2, 2, 3, 2, 1, 2, 1, 2, 3, 3, 2, 3, 1, 1, 3, 3, 1, 2, 2, 2, 2, 2, 2, 1, 3, 3, 3, 3, 3, 1, 1, 3, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 1, 2, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 1, 3, 3, 2, 3, 2, 3, 3, 2, 2, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 2, 3, 2, 2, 1, 3, 1, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 3, 1, 2, 1, 2, 3, 1, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 1, 3, 3, 3]
'''
现在我们已经从文本文件中导入了数据，并将其格式化为想要的格式，接着我们需要了解数据的真实含义，当然我们可以直接浏览文本文件，但是这种方式并不友好，一般来说，我们会采用图形化的方式直观的展示数据，下面使用Python工具来图形化展示数据内容，以便辨识出一些数据模式。
首先我们使用Matplotlib制作原始数据的散点图，代码如下：
由于没有使用样本分类的特征值，我们很难从上面看到任何有用的数据模式信息。一般来说，我们会采用色彩或其他的记号来标记不同样本分类，以便更好地理解数据信息，Matplotlib库提供的scatter函数支持个性化标记散点图上的点，重新输入上面代码，调用scatter函数时使用下列参数。
if __name__ == '__main__':
filename = 'datingTestSet2.txt'
datingDataMat,datingLabels = file2Matrix(filename)
print(datingDataMat)
print(datingLabels)
# 使用Matplotlib创建散点图
import matplotlib.pyplot as plt
from pylab import mpl
# 指定默认字体
mpl.rcParams['font.sans-serif'] = ['FangSong']
# 解决保存图像是负号- 显示为方块的问题
mpl.rcParams['axes.unicode_minus'] = False
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2],
15.0*array(datingLabels),15.0*array(datingLabels))
plt.xlabel("玩视频游戏所耗时间百分比")
plt.ylabel("每周消费的冰淇淋公升数")
plt.show()
上面代码利用了变量datingLabels存储的类标签属性，在散点图绘制了色彩不等，尺寸不等的点，你可以看到与上面类似的散点图，从上图中我们很难看到有用的信息，然而由下图的颜色及尺寸标识了数据点的属性类别，因此我们可以看到所属三个样本分类的区域轮廓。
上图可以区别，但是下图采用不同的属性值可以得到更好的结果，图中清晰的标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同。
表给出了提取的四组数据，如果想要计算样本3和样本4之间的距离，可以使用下面的方法：
计算的公式如下：
我们很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响远远大于下标中其他两个特征——玩视频游戏的和每周消费冰淇淋公升数的影响。而产生这种现象的唯一原因仅仅是飞行常客里程数远大于其他特征数值。但是James认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重的影响到计算结果。
在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为0
到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化到0到1区间内的值：
newValue = (oldValue - min)/(max-min)
其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但是为了得到准确结果，我们必须这样做，所以我们新增一个函数autoNorm() ，该函数可以自动将数字特征转化为0到1的区间。
归一化特征值代码如下：
# 归一化特征值
# 归一化公式 ： （当前值 - 最小值） / range
def autoNorm(dataSet):
# 存放每列最小值，参数0使得可以从列中选取最小值，而不是当前行
minVals = dataSet.min(0)
# 存放每列最大值
maxVals = dataSet.max(0)
ranges = maxVals - minVals
# 初始化归一化矩阵为读取的dataSet
normDataSet = zeros(shape(dataSet))
# 保留第一行
m = dataSet.shape[0]
# 特征值相除，特征矩阵是3*1000 min max range是1*3
# 因此采用tile将变量内容复制成输入矩阵同大小
normDataSet = dataSet - tile(minVals , (m,1))
normDataSet = normDataSet/tile(ranges,(m,1))
return normDataSet,ranges,minVals
那么执行命令行，得到结果如下：
if __name__ == '__main__':
filename = 'datingTestSet2.txt'
datingDataMat,datingLabels = file2Matrix(filename)
print(datingDataMat)
print(datingLabels)
normMat,ranges,minVals = autoNorm(datingDataMat)
print(normMat)
print(ranges)
print(minVals)
'''
[[0.44832535 0.39805139 0.56233353]
[0.15873259 0.34195467 0.98724416]
[0.28542943 0.06892523 0.47449629]
...
[0.29115949 0.50910294 0.51079493]
[0.52711097 0.43665451 0.4290048 ]
[0.47940793 0.3768091 0.78571804]]
[9.1273000e+04 2.0919349e+01 1.6943610e+00]
[0. 0. 0.001156]
'''
上面我们已经将数据按照需求做了处理，本节我们将测试分类器的效果，如果分类器的正确率满足要求，James就可以使用这个软件来处理约会网站提供的约会名单了。机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据来测试分类器，检测分类器的正确率。值得注意的是，10%的测试数据应该是随机选择的，由于James提供的数据并没有按照特定目的来排序，所以我们可以随意选择10%数据而不影响其随机性。
前面我们已经提到可以使用错误率来检测分类器的性能。对于分类器来说，错误率就是分类器给出的错误结果的次数除以测试数据的总数。代码里我们定义一个计算器变量，每次分类器错误地分类数据，计数器就加1，程序执行完成之后计数器的结果除以数据点总数即是错误率。
为了测试分类器效果，我们创建了datingClassTest，该函数时自包含的，代码如下：
分类器针对约会网站的测试代码：
# 分类器针对约会网站的测试代码
def datingClassTest():
hoRatio = 0.10
datingDataMat,datingLabels = file2Matrix('datingTestSet2.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m * hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],
datingLabels[numTestVecs:m],3)
print('the classifier came back with:%d,the read answer is :%d '
%(classifierResult,datingLabels[i]))
if (classifierResult != datingLabels[i]):
errorCount +=1.0
print("the total error rate is :%f"%(errorCount/float(numTestVecs)))
测试结果如下：
if __name__ == '__main__':
datingClassTest()
'''
the classifier came back with:3,the read answer is :3
the classifier came back with:2,the read answer is :2
the classifier came back with:1,the read answer is :1
...
the classifier came back with:1,the read answer is :1
the classifier came back with:3,the read answer is :1
the total error rate is :0.050000
'''
分类器处理越活数据集的错误率是5%，这是一个相当不错的结果，我们可以改变函数datingClassTest内变量hoRatio和变量k的值，检测错误率是否随着变量值的变化而增加，依赖于分类算法，数据集和程序设置，分类器的输出结果可能有很大的不同。
这个例子表明我们可以正确的预测分类，错误率仅仅是5%。James完全可以输入未知对象的属性信息，由分类软件来帮助他判定某一对象的可交往程度：讨厌，一般喜欢，非常喜欢。
上面我们已经在数据上对分类器进行了测试，现在我们可以使用这个分类器为James来对人们分类，我们会给James给一小段程序，通过该程序会在约会网站上找到某个人并输入他的信息，程序会给出他对对方喜欢程序的预测值。
约会网站预测函数代码：
# 约会网站预测函数
def classifyPerson():
resultList = ['not at all','in small','in large doses']
percentTats = float(input("percentage of time spent playing video games ?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters od ice cream consumed per year?"))
dataingDataMat,datingLabels = file2Matrix('datingTestSet2.txt')
normMat,ranges,minVals = autoNorm(datingDataMat)
inArr = array([ffMiles,percentTats,iceCream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
print("You will probably like this person ",resultList[classifierResult-1])
测试结果如下：
if __name__ == '__main__':
# datingClassTest()
filename = 'datingTestSet2.txt'
datingDataMat,datingLabels = file2Matrix(filename)
classifyPerson()
'''
percentage of time spent playing video games ?10
frequent flier miles earned per year?10000
liters od ice cream consumed per year?0.5
You will probably like this person in small
'''
这里我们一步步的构造使用k-近邻分类器的手写识别系统，为了简单起见，这里构造的系统只能识别数字0到9，参考图2-6，需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素*32像素的黑白图形。尽管采用文本格式存储图形不能有效地利用内存空间，但是为了方便理解，我们还是将图像转化为文本格式。
（1）收集数据：提供文本文件
（2）准备数据：编写函数classify0()，将图像格式转换为分类器使用的list格式
（3）分析数据：在Python命令提示符中检查数据，确保它符合要求
（4）训练算法：此步骤不适用与k-近邻算法
（5）测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
（6）使用算法：本例没有完成此步骤，如果感兴趣的话，可以构建完整的应用程序，从图形中提取数字，并完成数字识别
实际图形存储在源码的两个子目录中：目标trainingDigits中包含了大约2000个例子，每个例子如图2-6所示，每个数字大约有200个样本；目录testDigits中包含了大约900个测试数据，我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果，两组数据没有覆盖，你可以检查一下这些文件夹的文件是否符合要求。
为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量，我们将把一个32*32的二进制图像矩阵转化为1*1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。
我们首先编写一段函数img2vector，将图像转化为向量：该函数创建1*1024的Numpy数组，然后打开给定的问价，循环读出文件的前32行，并将每行的头32个字符串存储在Numpy数组中，最后返回数组。
def img2vector(filename):
# 每个手写识别为32*32大小的二进制图像矩阵，转换为1*1024 numpy向量数组returenVect
returnVect = zeros((1,1024))
fr = open(filename)
# 循环读出前32行
for i in range(32):
lineStr = fr.readline()
for j in range(32):
# 将每行的32个字符值存储在numpy数组中
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
测试代码，结果如下：
if __name__ == '__main__':
res = img2vector('testDigits/0_13.txt')
print(res[0,0:31])
print(res[0,32:63])
'''
[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.]
[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.]
'''
上面我们已经将数据处理成分类器可以识别的格式，本小节我们将这些数据输入到分类器，检测分类器的执行效果，下面程序是测试分类器的代码。
手写数字识别系统的测试代码：
# 测试算法
def handwritingClassTest():
hwLabels = []
trainingFileList = os.listdir('trainingDigits')
m = len(trainingFileList)
# 定义文件数 x 每个向量的训练集
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0]
# 解析文件名
classNumStr = int(fileStr.split('_')[0])
# 存储类别
hwLabels.append(classNumStr)
# 访问第i个文件内的数据
trainingMat[i,:] = img2vector('trainingDigits/%s'%fileNameStr)
# 测试数据集
testFileList = os.listdir('testDigits')
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
# 从文件名中分离出数字作为基准
classNumStr = int(fileStr.split('_')[0])
# 访问第i个文件内的测试数据，不存储类 直接测试
vectorUnderTest = img2vector('testDigits/%s'%fileNameStr)
classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)
print("the classifier came back with: %d,the real answer is: %d" %(classifierResult,classNumStr))
if(classifierResult!=classNumStr):
errorCount+=1.0
print("\nthe total number of errors is: %d" % errorCount)
print("\nthe total rate is:%f"% (errorCount/float(mTest)))
测试代码，结果如下：
the classifier came back with: 0,the real answer is: 0
the total number of errors is: 0
the total rate is:0.000000
... ...
the total number of errors is: 4
the total rate is:0.004228
... ...
the classifier came back with: 9,the real answer is: 9
the total number of errors is: 9
the total rate is:0.009514
the classifier came back with: 9,the real answer is: 9
the total number of errors is: 10
the total rate is:0.010571
k-近邻算法识别手写数字集，错误率为1.2%，改变变量k的值，修改函数handwritingClassTest随机选取训练样本，改变训练样本的数目，都会对k-近邻算法的错误率产生影响，感兴趣的话可以改变这些变量值，观察错误率的变化。
实际使用这个算法的时候，算法的执行效率并不高，因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点计算，总计要执行900次。此外，我们还需要为测试向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢？k决策树就是k-近邻算法的优化版，可以节省大量的计算开销。
import os ,sys
from numpy import *
import operator
# k-近邻算法
def classify0(inX,dataSet,labels,k):
# shape读取数据矩阵第一维度的长度
dataSetSize = dataSet.shape[0]
# tile重复数组inX，有dataSet行 1个dataSet列，减法计算差值
diffMat = tile(inX,(dataSetSize,1)) - dataSet
# **是幂运算的意思，这里用的欧式距离
sqDiffMat = diffMat ** 2
# 普通sum默认参数为axis=0为普通相加，axis=1为一行的行向量相加
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# argsort返回数值从小到大的索引值（数组索引0,1,2,3）
sortedDistIndicies = distances.argsort()
# 选择距离最小的k个点
classCount = {}
for i in range(k):
# 根据排序结果的索引值返回靠近的前k个标签
voteLabel = labels[sortedDistIndicies[i]]
# 各个标签出现频率
classCount[voteLabel] = classCount.get(voteLabel,0) +1
##!!!!! classCount.iteritems()修改为classCount.items()
#sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list。
# reverse默认升序 key关键字排序itemgetter（1）按照第一维度排序(0,1,2,3)
sortedClassCount = sorted(classCount.items(),
key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
def img2vector(filename):
# 每个手写识别为32*32大小的二进制图像矩阵，转换为1*1024 numpy向量数组returenVect
returnVect = zeros((1,1024))
fr = open(filename)
# 循环读出前32行
for i in range(32):
lineStr = fr.readline()
for j in range(32):
# 将每行的32个字符值存储在numpy数组中
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
# 测试算法
def handwritingClassTest():
hwLabels = []
trainingFileList = os.listdir('trainingDigits')
m = len(trainingFileList)
# 定义文件数 x 每个向量的训练集
trainingMat = zeros((m,1024))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0]
# 解析文件名
classNumStr = int(fileStr.split('_')[0])
# 存储类别
hwLabels.append(classNumStr)
# 访问第i个文件内的数据
trainingMat[i,:] = img2vector('trainingDigits/%s'%fileNameStr)
# 测试数据集
testFileList = os.listdir('testDigits')
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
# 从文件名中分离出数字作为基准
classNumStr = int(fileStr.split('_')[0])
# 访问第i个文件内的测试数据，不存储类 直接测试
vectorUnderTest = img2vector('testDigits/%s'%fileNameStr)
classifierResult = classify0(vectorUnderTest,trainingMat,hwLabels,3)
print("the classifier came back with: %d,the real answer is: %d" %(classifierResult,classNumStr))
if(classifierResult!=classNumStr):
errorCount+=1.0
print("\nthe total number of errors is: %d" % errorCount)
print("\nthe total rate is:%f"% (errorCount/float(mTest)))
if __name__ == '__main__':
handwritingClassTest()
# res = img2vector('testDigits/0_13.txt')
# print(res[0,0:31])
# print(res[0,32:63])
k-近邻算法是分类数据最简单最有效的算法，本文通过两个例子讲述了如何使用k-近邻算法构造分类器，k-近邻算法是基于实例的学习，使用算法时我们必须有接近实际数据的训练样本数据，k-近邻算法必须保存全部的数据集，如果训练数据集的很大，必须使用大量的存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。
k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。
上面已经说明了，将图片转换为文本格式，这里不再累赘，我们使用同样的方法处理。接下来我们使用强大的第三方Python科学计算库Sklearn构建手写数字系统。
关于sklearn的英文官方文档地址：点我查看
sklearn.neighbors模块实现了k-近邻算法，内容如下图：
我们使用sklearn.neighbors.KNeighborsClassifier就可以是实现上小结，我们实现的k-近邻算法。KNeighborsClassifier函数一共有8个参数，如图所示：
KNneighborsClassifier参数说明：
我们知道数字图片是32x32的二进制图像，为了方便计算，我们可以将32x32的二进制图像转换为1x1024的向量。对于sklearn的KNeighborsClassifier输入可以是矩阵，不用一定转换为向量，不过为了跟自己写的k-近邻算法分类器对应上，这里也做了向量化处理。然后构建kNN分类器，利用分类器做预测。创建kNN_test04.py文件，编写代码如下：
#_*_coding:utf-8_*_
import numpy as np
import operator
import os
from sklearn.neighbors import KNeighborsClassifier as KNN
def img2vector(filename):
# 创建1*1024零向量
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])
# 返回转换后的1*1024向量
return returnVect
# 手写数字分类测试
def handwritingClassTest():
# 测试集的Labels
hwLabels = []
# 返回trainingDigts目录下的文件名
trainingFileList = os.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)
# 将每一个文件的1*1024数据存储到trainingMat矩阵中
trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr))
# 构建KNN分类器
neigh = KNN(n_neighbors=3,algorithm='auto')
# 拟合模型，trainingMat为训练矩阵，hwLabels为对应的标签
neigh.fit(trainingMat,hwLabels)
# 返回testDigits目录下的文件列表
testFileList = os.listdir('testDigits')
# 错误检测计数
errorCount = 0.0
# 测试数据的数量
mTest = len(testFileList)
# 从文件中解析出测试集的类别并进行分类测试
for i in range(mTest):
# 获取文件的名字
fileNameStr = testFileList[i]
# 获取分类的数字
classNumber = int(fileNameStr.split('_')[0])
# 获得测试集的1*1024向量，用于训练
vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))
# 获得预测结果
# classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
classifierResult = neigh.predict(vectorUnderTest)
print("分类返回结果为%d\t真实结果为%d" % (classifierResult, classNumber))
if (classifierResult != classNumber):
errorCount += 1.0
print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount / mTest * 100))
if __name__ == '__main__':
handwritingClassTest()
测试结果如下：
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
分类返回结果为0 真实结果为0
... ...
分类返回结果为9 真实结果为9
总共错了12个数据
错误率为1.268499%
上述代码使用的algorithm参数是auto，更改algorithm参数为brute，使用暴力搜索，你会发现，运行时间变长了，变为10s+。更改n_neighbors参数，你会发现，不同的值，检测精度也是不同的。自己可以尝试更改这些参数的设置，加深对其函数的理解。
代码及其运行结果：
# 引入数据集，sklearn包含众多数据集
from sklearn import datasets
# 将数据分为测试集和训练集
from sklearn.model_selection import train_test_split
# 利用邻近点方式训练数据
from sklearn.neighbors import KNeighborsClassifier
# 引入数据,本次导入鸢尾花数据，iris数据包含4个特征变量
iris = datasets.load_iris()
# 特征变量
iris_X = iris.data
# print(iris_X)
print('特征变量的长度',len(iris_X))
# 目标值
iris_y = iris.target
print('鸢尾花的目标值',iris_y)
# 利用train_test_split进行训练集和测试机进行分开，test_size占30%
X_train,X_test,y_train,y_test=train_test_split(iris_X,iris_y,test_size=0.3)
# 我们看到训练数据的特征值分为3类
# print(y_train)
'''
[1 1 0 2 0 0 0 2 2 2 1 0 2 0 2 1 0 1 0 2 0 1 0 0 2 1 2 0 0 1 0 0 1 0 0 0 0
2 2 2 1 1 1 2 0 2 0 1 1 1 1 2 2 1 2 2 2 0 2 2 2 0 1 0 1 0 0 1 2 2 2 1 1 1
2 0 0 1 0 2 1 2 0 1 2 2 2 1 2 1 0 0 1 0 0 1 1 1 0 2 1 1 0 2 2]
'''
# 训练数据
# 引入训练方法
knn = KNeighborsClassifier()
# 进行填充测试数据进行训练
knn.fit(X_train,y_train)
params = knn.get_params()
print(params)
'''
{'algorithm': 'auto', 'leaf_size': 30, 'metric': 'minkowski',
'metric_params': None, 'n_jobs': None, 'n_neighbors': 5,
'p': 2, 'weights': 'uniform'}
'''
score = knn.score(X_test,y_test)
print("预测得分为：%s"%score)
'''
预测得分为：0.9555555555555556
[1 2 1 1 2 2 1 0 0 0 0 1 2 0 1 0 2 0 0 0 2 2 0 2 2 2 2 1 2 2 2 1 2 2 1 2 0
2 1 2 1 1 0 2 1]
[1 2 1 1 2 2 1 0 0 0 0 1 2 0 1 0 2 0 0 0 1 2 0 2 2 2 2 1 1 2 2 1 2 2 1 2 0
2 1 2 1 1 0 2 1]
'''
# 预测数据，预测特征值
print(knn.predict(X_test))
'''
[0 2 2 2 2 0 0 0 0 2 2 0 2 0 2 1 2 0 2 1 0 2 1 0 1 2 2 0 2 1 0 2 1 1 2 0 2
1 2 0 2 1 0 1 2]
'''
# 打印真实特征值
print(y_test)
'''
[1 2 2 2 2 1 1 1 1 2 1 1 1 1 2 1 1 0 2 1 1 1 0 2 0 2 0 0 2 0 2 0 2 0 2 2 0
2 2 0 1 0 2 0 0]
'''
参考文献：https://www.jianshu.com/p/1ded78d92e68
转载于:https://www.cnblogs.com/wj-1314/p/10291284.html