目录
1.1 KNN算法的简介
1.2 KNN算法的工作原理
1.3 创建数据集并导入数据
1.4 从文本文件中解析数据
1.5 示例：手写识别系统
1.5.1 准备数据：将图像转换为测试向量
1.5.1 测试算法：使用k-近邻算法识别手写数字
1.1 KNN算法的简介
KNN（K- Nearest Neighbor）法即K最邻近法，最初由 Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据集合中每一个记录进行分类的方法该方法的思路非常简单直观：如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。
1.2 KNN算法的工作原理
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
1.3 创建数据集并导入数据
kNN.py
from numpy import *
import operator
def createDataSet():
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
之后在kNN.py的目录下打开cmd，输入python.exe进入Python交互式开发环境。接着输入下列命令导入上面编辑的程序模块：
import kNN
为了确保输入相同的数据集，kNN模块中定义了函数createDataSet，在Python命令提示符下输入下属命令：
group,labels = kNN.createDataSet()
上述命令创建了变量group和labels，在Python命令提示符下，输入变量的名字以检验是否正确的定义变量。接下来我们将使用这些方法完成分类任务。
1.4 从文本文件中解析数据
将下面代码增加到kNN.py中。
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis = 1)
distances = sqDistances ** 0.5 #距离计算
sortedDistIndicies = distances.argsort()
classCount = {}
for i in range (k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #选择距离最小的k个点
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True) #排序
return sortedClassCount[0] [0]
classify0()函数有4个输入参数：用于分类的输入向量是inX，输入的训练样本集为dataSet，标签向量为labels，最后的参数k表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵dataSet的行数相同。
为了预测数据所在分类，在Python提示符中输入下列命令：
kNN.classify0([0,0], group, labels, 3)
输出结果应该是B，我们可以改变输入[0,0]为其他值，测试运行结果。
1.5 示例：手写识别系统
1.5.1 准备数据：将图像转换为测试向量
我们使用了两个数据集，其中目录trainingDigits中包含了大约2000个例子，每个例子的内容如下图所示，每个数字大约有200个样本；目录testDigits中包含了大约900个测试数据。我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果，两组数据没有覆盖。
我们首先编写一段函数img2vector，将图像转换为向量：该函数创建1 × 1024的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
将上述代码输入到kNN.py中，在Python命令行中输入下列命令测试img2vector函数，然后与文本编辑器打开的文件进行比较：
testVector = kNN.img2vector('testDigits/0_13.txt')
1.5.1 测试算法：使用k-近邻算法识别手写数字
下面程序包含函数handwritingClassTest（）是测试分类器的代码，将其写入kNN.py文件中。在写入这些代码之前，我们必须确保from os import listdir写入文件的起始部分。
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') #获取目录内容
m = len(trainingFileList)
trainingMat = 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('trainingDigits/%s' % fileNameStr)
testFileList = 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])
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 error rate is: %f" % (errorCount/float(mTest)))(mTest)))
之后在Python命令提示符中输入kNN.handwritingClassTest()，测试该函数的输出结果。
