(1) 、KNN即最近邻算法，其主要过程为：
1. 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
2. 对上面所有的距离值进行排序；
3. 选前k个最小距离的样本；
4. 根据这k个样本的标签进行投票，得到最后的分类类别。
(2)、KNN算法的优点：
1. 思想简单，理论成熟，既可以用来做分类也可以用来做回归；
2. 可用于非线性分类；
3. 训练时间复杂度为O(n)；
4. 准确度高，对数据没有假设，对outlier不敏感；
缺点：
1. 计算量大；
2. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
3. 需要大量的内存；
(3)python实现：
#coding=UTF8
from numpy import *
import operatordef createDataSet():"""函数作用：构建一组训练数据（训练样本），共4个样本同时给出了这4个样本的标签，及labels"""group = array([[1.0, 1.1],[1.0, 1.0],[0. , 0. ],[0. , 0.1]])labels = ['A', 'A', 'B', 'B']return group, labelsdef classify0(inX, dataset, labels, k):"""inX 是输入的测试样本，是一个[x, y]样式的dataset 是训练样本集labels 是训练样本标签k 是top k最相近的"""# shape返回矩阵的[行数，列数]，# 那么shape[0]获取数据集的行数，# 行数就是样本的数量dataSetSize = dataset.shape[0] """下面的求距离过程就是按照欧氏距离的公式计算的。即 根号(x^2+y^2)"""# tile属于numpy模块下边的函数# tile（A, reps）返回一个shape=reps的矩阵，矩阵的每个元素是A# 比如 A=[0,1,2] 那么，tile(A, 2)= [0, 1, 2, 0, 1, 2]# tile(A,(2,2)) = [[0, 1, 2, 0, 1, 2],# [0, 1, 2, 0, 1, 2]]# tile(A,(2,1,2)) = [[[0, 1, 2, 0, 1, 2]],# [[0, 1, 2, 0, 1, 2]]] # 上边那个结果的分开理解就是：# 最外层是2个元素，即最外边的[]中包含2个元素，类似于[C,D],而此处的C=D，因为是复制出来的# 然后C包含1个元素，即C=[E],同理D=[E]# 最后E包含2个元素，即E=[F,G],此处F=G，因为是复制出来的# F就是A了，基础元素# 综合起来就是(2,1,2)= [C, C] = [[E], [E]] = [[[F, F]], [[F, F]]] = [[[A, A]], [[A, A]]]# 这个地方就是为了把输入的测试样本扩展为和dataset的shape一样，然后就可以直接做矩阵减法了。# 比如，dataset有4个样本，就是4*2的矩阵，输入测试样本肯定是一个了，就是1*2，为了计算输入样本与训练样本的距离# 那么，需要对这个数据进行作差。这是一次比较，因为训练样本有n个，那么就要进行n次比较；# 为了方便计算，把输入样本复制n次，然后直接与训练样本作矩阵差运算，就可以一次性比较了n个样本。# 比如inX = [0,1],dataset就用函数返回的结果，那么# tile(inX, (4,1))= [[ 0.0, 1.0],# [ 0.0, 1.0],# [ 0.0, 1.0],# [ 0.0, 1.0]]# 作差之后# diffMat = [[-1.0,-0.1],# [-1.0, 0.0],# [ 0.0, 1.0],# [ 0.0, 0.9]]diffMat = tile(inX, (dataSetSize, 1)) - dataset# diffMat就是输入样本与每个训练样本的差值，然后对其每个x和y的差值进行平方运算。# diffMat是一个矩阵，矩阵**2表示对矩阵中的每个元素进行**2操作，即平方。# sqDiffMat = [[1.0, 0.01],# [1.0, 0.0 ],# [0.0, 1.0 ],# [0.0, 0.81]]sqDiffMat = diffMat ** 2# axis=1表示按照横轴，sum表示累加，即按照行进行累加。# sqDistance = [[1.01],# [1.0 ],# [1.0 ],# [0.81]]sqDistance = sqDiffMat.sum(axis=1)# 对平方和进行开根号distance = sqDistance ** 0.5# 按照升序进行快速排序，返回的是原数组的下标。# 比如，x = [30, 10, 20, 40]# 升序排序后应该是[10,20,30,40],他们的原下标是[1,2,0,3]# 那么，numpy.argsort(x) = [1, 2, 0, 3]sortedDistIndicies = distance.argsort()# 存放最终的分类结果及相应的结果投票数classCount = {}# 投票过程，就是统计前k个最近的样本所属类别包含的样本个数for i in range(k):# index = sortedDistIndicies[i]是第i个最相近的样本下标# voteIlabel = labels[index]是样本index对应的分类结果('A' or 'B')voteIlabel = labels[sortedDistIndicies[i]]# classCount.get(voteIlabel, 0)返回voteIlabel的值，如果不存在，则返回0# 然后将票数增1classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1# 把分类结果进行排序，然后返回得票数最多的分类结果sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]if __name__== "__main__":# 导入数据dataset, labels = createDataSet()inX = [0.1, 0.1]# 简单分类className = classify0(inX, dataset, labels, 3)print('the class of test sample is %s' %className)