K近邻：KNN-（k-nearest neighbor classification）
是有监督学习、属于判别模型 、支持多分类以及回归、非线性、有预测函数、无优化目标、无优化求解算法。（算法地图）
对应每个训练数据xi有对应的标签yi--监督学习；
优缺点：
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
简单描述预测过程：
假定其中的K值已经选定好，也即是模型已经确定
对于给定的训练数据点和输入数据点，确定输入点的k个最近邻训练点，利用k个训练点的类的多数预测输入点的类
1.算法的抽象解释如下：
以上描述的三个要素：
距离度量、K值选择、分类决策规则
1、距离度量
距离度量方式有：欧氏距离、曼哈顿距离等
2、K值选择
K值的选择一般采取交叉验证方法，也即是需要调参的地方【4】
k值过小（近似误差小，估计误差大）容易发生过拟合，k值增大（近似误差大，估计误差小）则整体模型变简单
3、分类决策规则
多数表决
2.明确的概念：
最近邻 、 K -最近邻 、 近似误差和估计误差 、交叉验证
（最近邻）相当于k=1，在所有的训练数据集中找出距离目标B最近距离的一个值A，并将它B归类为这个最近距离的值A的类别。
（K-近邻）是找到距离目标B最近的某一个范围内，例如k的范围内；判断k范围内的类别数，选择个数最多的某一个类别A作为目标B的类。
近似误差：理解为对现有训练集的训练误差； 估计误差：理解为对测试集的测试误差
交叉验证：简单交叉验证、k折交叉验证、留一交叉验证
3.算法实现：
1）创建简单的数据集：
import numpy as np from collections import Counter from draw import draw class KNN: def __init__(self,X_train,y_train,k=3): # 所需参数初始化 self.k=k #所取k值 self.X_train=X_train self.y_train=y_train def predict(self,X_new): # 计算欧氏距离 dist_list=[(np.linalg.norm(X_new-self.X_train[i],ord=2),self.y_train[i]) for i in range(self.X_train.shape[0])] #[(d0,-1),(d1,1)...] # 对所有距离进行排序 dist_list.sort(key=lambda x: x[0])#以第0个元素升序排序 # 取前k个最小距离对应的类别（也就是y值） y_list=[dist_list[i][-1] for i in range(self.k)] # [-1,1,1,-1...] # 对上述k个点的分类进行统计 y_count=Counter(y_list).most_common()#提取每个元素出现的次数 # [(-1, 3), (1, 2)] return y_count[0][0]#返回最大的次数 def main(): # 训练数据 X_train=np.array([[5,4], [9,6], [4,7], [2,3], [8,1], [7,2]]) y_train=np.array([1,1,1,-1,-1,-1]) # 测试数据 X_new = np.array([[5, 3]]) #目标值 # 绘图 draw(X_train, y_train, X_new) # 不同的k(取奇数）对分类结果的影响 for k in range(1,6,2):#步长为2 也即是：1，3，5 #构建KNN实例 clf=KNN(X_train,y_train,k=k) #对测试数据进行分类预测 y_predict=clf.predict(X_new) print("k={},被分类为：{}".format(k,y_predict)) if __name__=="__main__": main()
SKlearn实现：
import numpy as np from sklearn.neighbors import KNeighborsClassifier def main(): # 训练数据 X_train=np.array([[5,4], [9,6], [4,7], [2,3], [8,1], [7,2]]) y_train=np.array([1,1,1,-1,-1,-1]) # 待预测数据 X_new = np.array([[5, 3]]) # 不同k值对结果的影响 for k in range(1,6,2): # 构建实例 clf = KNeighborsClassifier(n_neighbors=k,n_jobs=-1) # 选择合适算法 clf.fit(X_train, y_train) # print(clf.kneighbors(X_new)) # 预测 y_predict=clf.predict(X_new) #print(clf.predict_proba(X_new)) print("预测正确率:{:.0%}".format(clf.score([[5,3]],[[1]]))) print("k={},被分类为：{}".format(k,y_predict)) if __name__=="__main__": main()
2）.使用 k近邻算法改进网站的配对效果-代码理解
见github：https://github.com/codehgq/ML-note/blob/master/Date_KNN.ipynb
分为以下步骤：
1）文件到矩阵转换（准备数据）
#导入矩阵运算模块 import numpy as np import operator #数据集文件datingTestSet2.txt保存在当前目录下，也即是把txt拷贝到本地的用户文件夹下（我的） 输入：文件 输出：数据集的特征矩阵returnMat和标签向量classLabelVector def file2matrix(filename): love_dictionary = {'largeDoses':3, 'smallDoses':2, 'didntLike':1} # 三个类别 fr = open(filename) # 打开文件 arrayOLines = fr.readlines() # 逐行打开 numberOfLines = len(arrayOLines) #得到文件的行数 returnMat = np.zeros((numberOfLines, 3)) #初始化特征矩阵 classLabelVector = [] #初始化输出标签向量 index = 0 for line in arrayOLines:#循环处理文件中的每行数据 line = line.strip() # 删去字符串首部尾部空字符 listFromLine = line.split('\t') # 按'\t'对字符串进行分割，得到列表 returnMat[index, :] = listFromLine[0:3] # listFromLine的0,1,2元素是特征，赋值给returnMat的当前行 if(listFromLine[-1].isdigit()): # 如果listFromLine最后一个元素是数字 classLabelVector.append(int(listFromLine[-1])) # append 的作用是在列表的末尾添加元素，直接赋值给classLabelVector else: # 如果listFromLine最后一个元素不是数字，而是字符串 classLabelVector.append(love_dictionary.get(listFromLine[-1])) # 根据字典love_dictionary转化为数字 index += 1 return returnMat, classLabelVector # 返回的类别标签classLabelVector是1,2,3
2）数据归一化
#输入：数据矩阵 输出：归一化的数据矩阵normDataSet 范围 ranges 有3列 最小值minVals 3列 def autoNorm(dataSet): minVals = dataSet.min(0)#从列中选择最小值 maxVals = dataSet.max(0)#从列中选择最大值 ranges = maxVals - minVals normDataSet = np.zeros(np.shape(dataSet))#shape返回矩阵中维度 此句相当于创建一个同等规模的0矩阵 m = dataSet.shape[0]#取矩阵的行数 normDataSet = dataSet - np.tile(minVals, (m, 1))#函数title用于扩充minVals成m行1列 normDataSet = normDataSet/np.tile(ranges, (m, 1)) # normDataSet值被限定在[0,1]之间 return normDataSet, ranges, minVals
3）对数据分析
import matplotlib import matplotlib.pyplot as plt import numpy as np import operator import logging datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') fig=plt.figure() ax=fig.add_subplot(131)#1*3的第一个 ax.scatter(datingDataMat[:,1],datingDataMat[:,2])#第二列和第三列数据 #plt.show() ax=fig.add_subplot(132) ax.scatter(datingDataMat[:,1],datingDataMat[:,2],10.0*np.array(datingLabels),10.0*np.array(datingLabels)) ax=fig.add_subplot(133) #datingLabels的值为1、2、3 每个数据点的大小不一样 ax.scatter(datingDataMat[:,0],datingDataMat[:,1],10.0*np.array(datingLabels),10.0*np.array(datingLabels)) fig=plt.figure() ax=fig.add_subplot(111) #datingLabels=array(datingLabels) idx_1=np.where(np.array(datingLabels)==1) p1=ax.scatter(datingDataMat[idx_1,0],datingDataMat[idx_1,1],marker = '*',color ='xkcd:purple',label='1',s=20) idx_2=np.where(np.array(datingLabels)==2) p2=ax.scatter(datingDataMat[idx_2,0],datingDataMat[idx_2,1],marker = 'o',color ='xkcd:teal',label='2',s=10) idx_3=np.where(np.array(datingLabels)==3) p3=ax.scatter(datingDataMat[idx_3,0],datingDataMat[idx_3,1],marker = '+',color ='y',label='3',s=30) plt.legend(loc = 'upper right') plt.show()#最后显示即可 #scatter函数参考 https://www.cnblogs.com/shanlizi/p/6850318.html #matplot 官方教程 https://matplotlib.org/tutorials/colors/colors.html#sphx-glr-tutorials-colors-colors-py #最后一张图参考 http://blog.sina.com.cn/s/blog_8d249b140102wf3m.html 并修改其中的错误
4）KNN分类器
#输入：测试集inX，训练集dataSet，训练样本标签lebels，取的最近邻个数k 输出：返回K近邻中所属类别最多的一类 参考：https://www.cnblogs.com/vrfighters/articles/4715527.html 写的不错 def classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0]#得到行数 diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet#title 相当于将inX扩充为dataSeetSize行目的是为了和后面的训练集求距离 sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1)#求和axis=1表示对所在行的全部列求和 distances = sqDistances**0.5 sortedDistIndicies = distances.argsort()#从小到大排序并找到索引值可参考：https://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html和https://www.cnblogs.com/yyxf1413/p/6253995.html classCount = {}#创建字典，用于存储各标签出现的次数 for i in range(k):#从上述的k个排序好的点，统计类别次数 voteIlabel = labels[sortedDistIndicies[i]]#解释 距离最小的数据样本的标签参考 #：https://blog.csdn.net/zengxyuyu/article/details/54382182 classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1#获取键值voteIlabel对应的值（次数），若不存在则为0 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)#将字典分解为元组列表，并按照第二个元素（次数）排序 true 为降序排列 默认升序 #参考：http://www.runoob.com/python/python-func-sorted.html return sortedClassCount[0][0]#得到k近邻中所属类别最多的类
5）测试算法
输入：样本，输出：分类结果和实际类别 ，错误率，错误个数 def datingClassTest(): hoRatio = 0.10 #整个数据集的10%用来测试 datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') #导入数据集 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], 3) #输出分类结果和实际的类别 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))) # 打印错误率 print(errorCount) # 打印错误个数
6）使用算法（构建完整可用系统）
#依据用户输入3个参数，输出：判断结果类别 详细注释;参考：https://blog.csdn.net/quincuntial/article/details/50471423 def classifyPerson(): resultList = ['not at all', 'in small doses', 'in large doses']#定义分类结果类别 #读取输入的数据 percentTats ffMiles iceCream percentTats = float(input(\ "percentage of time spent playing video games?")) ffMiles = float(input("frequent flier miles earned per year?")) iceCream = float(input("liters of ice cream consumed per year?")) #从文件datingTestSet2.txt中读取已有数据 datingDataMat, datingLabels = file2matrix('datingTestSet2.txt') normMat, ranges, minVals = autoNorm(datingDataMat)#归一化 #将单个数据定义为一条数据 inArr = np.array([ffMiles, percentTats, iceCream, ]) #对输入数据分类 classifierResult = classify0((inArr - \ minVals)/ranges, normMat, datingLabels, 3) #输出预测的分类结果 print("You will probably like this person: %s" % resultList[classifierResult - 1])
3）手写识别系统 -代码的理解
见github：https://github.com/codehgq/ML-note/tree/master/KNN
欢迎
1）加载数据 2）图像转换为向量 3）分类
#图像转化为向量 def img2vector(filename): returnVect = np.zeros((1, 1024)) # 存储图片像素的向量维度是1x1024 fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32): returnVect[0, 32*i+j] = int(lineStr[j]) # 图片尺寸是32x32，将其依次放入向量returnVect中 return returnVect
4、如何对训练数据进行快速K近邻搜索
分为两过程：构造KD树（二叉树）和搜索KD树
KD树表示为对K维空间的划分，其每个结点对应于k维空间划分中的一个超矩形区域
优势：省去大部分数据点搜索，减少搜索计算量
其中的KD树适用于训练实例数远大于空间维数的K近邻搜索
参考资料
【1】机器学习之深入理解K-means、与KNN算法区别及其代码实现https://blog.csdn.net/sinat_35512245/article/details/55051306
【2】https://blog.csdn.net/gzj_1101/article/details/77774524
【3】近似误差和估计误差 https://blog.csdn.net/qq_35664774/article/details/79448076
【4】 一文搞懂k近邻（k-NN）算法
【5】最近邻法和k-近邻法 KD树https://blog.csdn.net/u012422446/article/details/56486342
【6】李航《统计学习方法》k近邻法
【7】KNN算法理解 https://blog.csdn.net/jmydream/article/details/8644004
【8】https://blog.csdn.net/qq_35082030/article/details/60965320 有问题
【9】kmeans和knn的区别 机器学习之深入理解K-means、与KNN算法区别及其代码实现
https://blog.csdn.net/sinat_35512245/article/details/55051306
【10】一文搞懂k近邻（k-NN）算法二 https://mp.weixin.qq.com/s/qfHBn7YydSOOnM43Be8aTg
【11】 机器学习实战
