少有人走的路一、KNN算法概述：
1.KNN算法的工作原理是：
（1）存在一个训练样本集，并且知道样本集中每一数据与所属分类的对应关系，即每个数据都存在分类标签。
（2）若此时输入不带标签的新数据之后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后用算法提取出样本集中特征最相似数据的分类标签。
（3）最后，选择K个（可根据实际情况自由选择不大于20的整数）最相似数据中出现次数最多的分类，作为新数据的分类。
2.KNN算法优缺点：
（1）优点：精度高、对异常值不敏感、无数据输入假定。
（2）缺点：计算复杂度高、空间复杂度高。
适用范围：数值型和标称型数据。
二、KNN算法实战1：以电影分类为例
1.数据预处理
为了便于测试，在给原始数据贴标签时，只分为两类。具体python代码如下所示：
from numpy import *import operatordef createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group,labels
2.对未知类别属性的数据集中的每个点依次执行以下操作：
（1）计算已知类别数据集中的点与当前点之间的距离；
（2）按照距离递增次序排序；
（3）选取与当前点距离最小的K个点；
（4）确定前K个点所在类别出现的频率；
（5）返回前K个点出现频率最高的类别作为当前点的预测分类。
3.KNN算法实现：
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]测试：
三、KNN算法实战2：手写识别数字
1.数据预处理
本次构建基于KNN算法的手写识别系统需要两个数据集trainingDigits 和 testDigits，其中trainingDigits数据集包含约2000个样本，用来训练分类器；testDigits数据集包含约900个样本，用来测试分类器的效果。
实现代码如下所示：
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
2.用KNN算法识别手写数字
def handwritingClassTest():
llLabels = []
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])
llLabels.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,llLabels,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 " % errorCountprint "\nThe total error rate is : %f " % (errorCount/float(mTest))测试结果：
四、小结
KNN算法是分类数据最简单有效的算法，是基于实例的学习，但在使用算法时必须有接近实际数据的训练样本数据。
如果训练数据集较大时，必须要使用大量的存储空间和计算时间。
本文出自勇哥的网站《少有人走的路》wwww.skcircle.com，转载请注明出处！讨论可扫码加群：
