KNN分类算法，是理论上比较成熟的方法，也是最简单的机器学习算法之一。
该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
一个对于KNN算法解释最清楚的图如下所示：
蓝方块和红三角均是已有分类数据，当前的任务是将绿色圆块进行分类判断，判断是属于蓝方块或者红三角。
当然这里的分类还跟K值是有关的：
如果K=3(实线圈)，红三角占比2/3，则判断为红三角；
如果K=5(虚线圈)，蓝方块占比3/5，则判断为蓝方块。
由此可以看出knn算法实际上根本就不用进行训练，而是直接进行计算的，训练时间为0，计算时间为训练集规模n。
knn算法的基本要素大致有3个：
1、K 值的选择
2、距离的度量
3、分类决策规则
使用方式
1、K 值会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最有的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
2、算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别
3、距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
knn算法在分类时主要的不足是，当样本不平衡时，如果一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的 K 个邻居中大容量类的样本占多数。
KNN算法python2代码实现
from numpy import *
import operator
from os import listdir
import matplotlib
import matplotlib.pyplot as plt
def classify0(inX, dataSet, labels, k):#对每组数据进行分类，inX为用于分类的输入向量，
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet#欧式距离计算tile函数位于python模块 numpy.lib.shape_base中，他的功能是重复某个数组。比如tile(A,n)，功能是将数组A重复n次，构成一个新的数组
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)#，将classCount字典分解为元祖列表，排序k个距离值
return sortedClassCount[0][0]#返回发生频率最高的元素标签
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
def file2matrix(filename):#准备数据，文本文件解析数据，处理输入格式问题
fr = open(filename)
numberOfLines = len(fr.readlines()) #得到文件行数 get the number of lines in the file
returnMat = zeros((numberOfLines,3)) #prepare matrix to return创建返回的numpy矩阵，这里的3 可以按照实际需求去改
classLabelVector = [] #prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():#解析文件数据到列表
line = line.strip()#截取掉所有的回车字符
#print line
listFromLine = line.split('\t')#分割成元素列表
#print listFromLine
returnMat[index,:] = listFromLine[0:3]#选取前3个元素存储到特征矩阵中
#print returnMat[index,:]
classLabelVector.append(int(listFromLine[-1]))#将列表中的最后一列存储到向量classLabelVector中，这里必须是int,否则会默认字符串
index += 1
return returnMat,classLabelVector#输出为训练样本矩阵与类标签向量
def autoNorm(dataSet):#该函数可以自动将数字特征值转换为0到1的区间
minVals = dataSet.min(0)#将每列的最小值放在变量minVals中
maxVals = dataSet.max(0)#将每列的最大值放在变量maxVals中
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))#tile()函数将变量内容复制成输入矩阵同样大小的矩阵
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide#/表示具体特征值相除而不是矩阵相除
return normDataSet, ranges, minVals
def datingClassTest():#计算错误率 评估分类器准确率，该函数可以在任何时候测试分类器效果
hoRatio = 0.10 #hold out 10%
datingDataMat,datingLabels = file2matrix('C:/Users/HZF/Desktop/machinelearninginaction/Ch02/datingTestSet2.txt') #load data setfrom file
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],4)#将训练与测试数据输入到分类器函数classify0函数中
#print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): errorCount += 1.0
print "the total error rate is: %f" % (errorCount/float(numTestVecs))#改变hoRatio与k的值，检验错误率会有所不同。
print errorCount
def img2vector(filename):#在二进制存储的图像数据上使用KNN，将图像转换为测试向量
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):#循环读出文件的前32行
returnVect[0,32*i+j] = int(lineStr[j])#将32*32的二进制图像矩阵转化为1*1024的向量
return returnVect#返回数组
from os import listdir
def handwritingClassTest():#测试算法，使用knn识别手写数字
hwLabels = []
trainingFileList = listdir('C:/Users/HZF/Desktop/machinelearninginaction/Ch02/trainingDigits') #load the training set 列出给定目录的文件名
m = len(trainingFileList)
trainingMat = zeros((m,1024))#训练矩阵，该矩阵的每行数据存储一个图像
for i in range(m):#从文件名解析分类数字
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] #take off .txt
classNumStr = int(fileStr.split('_')[0])#
hwLabels.append(classNumStr)#将类编码存储在hwLabels向量中
trainingMat[i,:] = img2vector('C:/Users/HZF/Desktop/machinelearninginaction/Ch02/trainingDigits/%s' % fileNameStr)
testFileList = listdir('C:/Users/HZF/Desktop/machinelearninginaction/Ch02/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('C:/Users/HZF/Desktop/machinelearninginaction/Ch02/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))
if __name__=="__main__":
datingDataMat,datingLabels=file2matrix('C:/Users/HZF/Desktop/machinelearninginaction/Ch02/datingTestSet2.txt')
print datingDataMat
#print datingLabels[:20]
normDataSet, ranges, minVals=autoNorm(datingDataMat)
print normDataSet
errorCount=datingClassTest()
handwritingClassTest()
#print errorCount
fig=plt.figure()#创建散点图图形化数据，以辨识数据模式
ax=fig.add_subplot(111)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))#使用数据集的第2,3列数据,利用变量datingLables存储的类标签属性，绘制色彩，尺寸不同的点
plt.show()
KNN算法上篇就写这么多，欢迎评论！
参考文献
2、《机器学习实战》 （书）
