概述
KNN算法是一种基本分类与回归方法，采用不同的特征值之间的距离方法进行分类。
- 优点：精度高、对异常值不敏感、无数据输入假定。
- 缺点：计算复杂度高、空间复杂度高。
- 适用数据范围：数值型和标称型。
原理
1.假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
2.输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
a. 计算新数据与样本数据集中每条数据的距离。
b. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
c. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
3.求 k 个数据中出现次数最多的分类标签作为新数据的分类。
开发流程
收集数据：任何方法
准备数据：距离计算所需要的数值，最好是结构化的数据格式
分析数据：任何方法
训练算法：此步骤不适用于 k-近邻算法
测试算法：计算错误率
使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判
断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理
kNN算法伪代码
对未知类别的属性的数据集中的每个点进行以下操作：
1.计算已知类别数据集中的点与当前点之间的距离;
2.按照距离的递增次序排序;
3.选取与当前点距离最小的k个点;
4.确定前k个点所在类别的出现频率；
5.返回前k个点出现的频率最高的类别作为当前点的预测分类。
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
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
例一：约会对象配对预测
分类配对对象：
类别：
- 不喜欢的人
- 魅力一般的人
- 极具魅力的人
reload(kNN)
datingDataMat,datingLabels = kNN.file2matrix('datingTestSet2.txt')
使用Matplotlib创建散点图
import matplotlib
import matplotlib .pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2])
plt.show()
import matplotlib
from numpy import *
import matplotlib .pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()
测试结果执行：
kNN.datingClassTest()
训练预测函数：
kNN.datingClassTest()
约会预测函数：
kNN.classifyPerson()
例二：手写体识别
- 构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。
- 需要识别的数字是存储在文本文件中的具有相同的色彩和大小：宽高是 32 像素 * 32 像素的黑白图像。
流程
收集数据：提供文本文件。
准备数据：编写函数 img2vector(), 将图像格式转换为分类器使用的向量格式
分析数据：在 Python 命令提示符中检查数据，确保它符合要求
训练算法：此步骤不适用于 KNN
测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统
def handwritingClassTest():
# 1. 导入训练数据
hwLabels = []
trainingFileList = listdir('input/2.KNN/trainingDigits') # load the training set
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
# hwLabels存储0～9对应的index位置， trainingMat存放的每个位置对应的图片向量
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
# 将 32*32的矩阵->1*1024的矩阵
trainingMat[i, :] = img2vector('input/2.KNN/trainingDigits/%s' % fileNameStr)
# 2. 导入测试数据
testFileList = listdir('input/2.KNN/testDigits') # iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0] # take off .txt
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('input/2.KNN/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))
执行：kNN.handwritingClassTest()
KNN 小结
经过上面的介绍我们可以知道， k 近邻算法有 三个基本的要素：
- k 值的选择
- k 值的选择会对 k 近邻算法的结果产生重大的影响。
- 如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
- 如果选择较大的 k 值，就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。
- 近似误差和估计误差，请看这里：https://www.zhihu.com/question/60793482
- 距离度量
- 特征空间中两个实例点的距离是两个实例点相似程度的反映。
-
k 近邻模型的特征空间一般是 n 维实数向量空间 。使用的距离是欧氏距离，但也可以是其他距离，如更一般的距离，或者 Minkowski 距离。
- 分类决策规则
- k 近邻算法中的分类决策规则往往是多数表决，即由输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类。
源于 ApacheCN
- k 近邻算法中的分类决策规则往往是多数表决，即由输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类。
