网站导航
> 文档中心 > 一文带你搞懂K近邻算法——kNN

一文带你搞懂K近邻算法——kNN

网友: 文档中心 2022-04-05 09:00:36

一： K近邻算法描述

        k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。K近邻可能是机器学习最容易理解的算法，事实上它根本就没有进行学习。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。如果有非常多的特征，通过学习得到的假设可能能够非常好地适应训练集（代价函数可能几乎为0），但是可能会不能推广到新的数据。总结一下步骤就是：

  1. 计算已知类别数据集中的点与当前点之间的距离；
  3. 按照距离递增次序排序；
  4. 选取与当前点距离最小的k个点；
  5. 确定前k个点所在类别的出现频率；
  6. 返回前k个点所出现频率最高的类别作为当前点的预测分类。

        存在的问题，如下图。考虑一个简单的二分类问题，如果我们选取k=3的情况，里面会包含两个类别2的样本，和一个类别一的样本，我们就可以根据简单的投票法，即少数服从多数原则，将新样本判定为类别2。但我们要注意到，虽然k=3时，包含了三个样本，但三个样本与我们的新样本的距离并不一致，而距离越近的样本相似度会更高，所以我们还可以对不同距离的样本赋予不同的权重，比如我们可以取距离的倒数作为权重，来使得距离越近的样本对我们的判断贡献越大。在实际问题中，可以选择不同的K来作为超参数。

二：例子1 —— 简单kNN —— 电影类型判断

情景描述：下图给出4个电影的打斗镜头和接吻镜头的数量，然后给出一个电影（打斗镜头10，接吻镜头101）来确定是什么类型的电影。

import tensorflow.compat.v1 as tftf.disable_v2_behavior()import numpy as npimport matplotlib.pyplot as pltimport pandas as pdimport seaborn as snsimport scipy.optimize as optdata01 = pd.read_csv('knn_data1.txt', names=['kiss','fight','type'])data01
lovetype = data01[data01.type=='love']actiontype = data01[data01.type=='action']fig, ax = plt.subplots(figsize=(12,8))ax.scatter(lovetype['kiss'], lovetype['fight'], s=50, c='b', marker='o', label='love')ax.scatter(actiontype['kiss'], actiontype['fight'], s=50, c='r', marker='x', label='action')ax.legend()ax.set_xlabel('kiss number')ax.set_ylabel('fight number')input = [101,10]ax.scatter(input[0],input[1],s=50,c='g',marker='.', label='test')plt.show()

 

def classify_1(input, data, K):    #[101,20]    datax = data.iloc[:, :-1].as_matrix()   #取前两列数据    dataSize = datax.shape[0]     # dataSize = 4    #计算欧式距离    diff = np.tile(input,(dataSize,1)) - datax  #diff = array([[11, 7], [13,5], [94,-91], [92,-78]])    sqdiff = diff  2  #sqdiff = array([[121,49], [169, 25],[8836, 8281], [8464, 6084]])    squareDist = np.sum(sqdiff,axis = 1)行向量分别相加，[  170,   194, 17117, 14548]dist = squareDist  0.5  #[ 13.03840481,  13.92838828, 130.83195328, 120.61509027]    #对距离进行排序    sortedDistIndex = np.argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标,{0,1,3,2}    #计数    classCount={}    for i in range(K): voteLabel = data.type[sortedDistIndex[i]] 对选取的K个样本所属的类别个数进行统计 classCount[voteLabel] = classCount.get(voteLabel,0) + 1 # classCount = {'action': 1, 'love': 2}    #取出最大的数据    maxCount = 0    for key,value in classCount.items(): if value > maxCount:     maxCount = value     classes = key    return classestest01 = [101,20]test_class = classify_1(test01, data01, 3)print(test_class)#love

三：例子2 —— 复杂kNN（超2维数据+归一化） —— 网站交友判断

上个例子比较简单，因此有所省略。这次给出更加普通的步骤：

  1. 收集数据：可以使用爬虫进行数据的收集，也可以使用第三方提供的免费或收费的数据。一般来讲，数据放在txt文本文件中，按照一定的格式进行存储，便于解析及处理。
  2. 准备数据：使用Python解析、预处理数据。
  3. 分析数据：可以使用很多方法对数据进行分析，例如使用Matplotlib将数据可视化。
  4. 测试算法：计算错误率。
  5. 使用算法：错误率在可接受范围内，就可以运行k-近邻算法进行分类。

之后是一个更加复杂的例子：

情景描述：

        海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选，但她并不是喜欢每一个人。经过一番总结，她发现自己交往过的人可以分为：不喜欢、有点喜欢和很喜欢三类。使用的维度包括：

        每年获得的飞行常客里程数、玩视频游戏所消耗时间百分比和每周消费的冰淇淋公升数。（紧接着上面的代码）

#（1）inputfr = open('ex3data2.txt','r')arrayOLines = fr.readlines()  #读取文件所有内容     numberOfLines = len(arrayOLines)   #得到文件行数returnMat = np.zeros((numberOfLines,3))#返回的NumPy矩阵,解析完成的数据:numberOfLines行,3列classLabelVector = []#返回的分类标签向量index = 0 #行的索引值for line in arrayOLines:    line = line.strip()#s.strip(rm)，当rm空时,默认删除空白符(包括'\n','\r','\t',' ')    listFromLine = line.split('\t')#使用s.split(str="",num=string,cout(str))将字符串根据'\t'分隔符进行切片。     returnMat[index,:] = listFromLine[0:3]#将数据前三列提取出来,存放到returnMat矩阵中,也就是特征矩阵    #根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力      if listFromLine[-1] == 'didntLike': classLabelVector.append(1)    elif listFromLine[-1] == 'smallDoses': classLabelVector.append(2)    elif listFromLine[-1] == 'largeDoses': classLabelVector.append(3)    index += 1
#（2）picturefig, axs = plt.subplots(nrows=2, ncols=2,sharex=False, sharey=False, figsize=(13,8))numberOfLabels = len(classLabelVector)LabelsColors = []for i in classLabelVector:if i == 1: LabelsColors.append('black') #didntLikeif i == 2:LabelsColors.append('orange') #smallDosesif i == 3:LabelsColors.append('red') #largeDoses#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第二列(玩游戏)数据画散点数据,散点大小为15,透明度为0.5axs[0][0].scatter(x=returnMat[:,0], y=returnMat[:,1], color=LabelsColors,s=15, alpha=.5)#设置标题,x轴label,y轴labelaxs0_xlabel_text = axs[0][0].set_xlabel(u'fly distance')axs0_ylabel_text = axs[0][0].set_ylabel(u'game time')#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5axs[0][1].scatter(x=returnMat[:,0], y=returnMat[:,2], color=LabelsColors,s=15, alpha=.5)#设置标题,x轴label,y轴labelaxs1_xlabel_text = axs[0][1].set_xlabel(u'fly distance')axs1_ylabel_text = axs[0][1].set_ylabel(u'icecream mount')#画出散点图,以datingDataMat矩阵的第二(玩游戏)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5axs[1][0].scatter(x=returnMat[:,1], y=returnMat[:,2], color=LabelsColors,s=15, alpha=.5)#设置标题,x轴label,y轴labelaxs2_xlabel_text = axs[1][0].set_xlabel(u'game time')axs2_ylabel_text = axs[1][0].set_ylabel(u'icecream mount')plt.show()

 

#（3）构架kNNdef classify_2(inX, dataSet, labels, k):#numpy函数shape[0]返回dataSet的行数dataSetSize = dataSet.shape[0]#在列向量方向上重复inX共1次(横向),行向量方向上重复inX共dataSetSize次(纵向)diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet#二维特征相减后平方sqDiffMat = diffMat2#sum()所有元素相加,sum(0)列相加,sum(1)行相加sqDistances = sqDiffMat.sum(axis=1)#开方,计算出距离distances = sqDistances0.5#返回distances中元素从小到大排序后的索引值sortedDistIndices = distances.argsort()#定一个记录类别次数的字典classCount = {}for i in range(k):#取出前k个元素的类别voteIlabel = labels[sortedDistIndices[i]]#dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。#计算类别次数classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#python3中用items()替换python2中的iteritems()#key=operator.itemgetter(1)根据字典的值进行排序#key=operator.itemgetter(0)根据字典的键进行排序#reverse降序排序字典sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)print(sortedClassCount)#返回次数最多的类别,即所要分类的类别return sortedClassCount[0][0]

之后进行数据归一化，如果按照之前的公式：

根号下（（0-67）²+（20000-32000）²+（1.1-0.1）²）

        很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于表2.1中其他两个特征-玩视频游戏所耗时间占比和每周消费冰淇淋公斤数的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

       在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为０到１或者-１到１之间。下面的公式可以将任意取值范围的特征值转化为０到１区间内的值：

newValue = (oldValue - min) / (max - min)

#归一化def autoNorm(dataSet):#获得数据的最小值minVals = dataSet.min(0)maxVals = dataSet.max(0)#最大值和最小值的范围ranges = maxVals - minVals#shape(dataSet)返回dataSet的矩阵行列数normDataSet = np.zeros(np.shape(dataSet))#返回dataSet的行数m = dataSet.shape[0]#原始值减去最小值normDataSet = dataSet - np.tile(minVals, (m, 1))#除以最大和最小值的差,得到归一化数据normDataSet = normDataSet / np.tile(ranges, (m, 1))#返回归一化数据结果,数据范围,最小值return normDataSet, ranges, minVals
#测试准确率def datingClassTest():#取所有数据的百分之十hoRatio = 0.10#数据归一化,返回归一化后的矩阵,数据范围,数据最小值normMat, ranges, minVals = autoNorm(returnMat)#获得normMat的行数m = normMat.shape[0]#百分之十的测试数据的个数numTestVecs = int(m * hoRatio)#分类错误计数errorCount = 0.0for i in range(numTestVecs):#前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集classifierResult = classify_2(normMat[i,:], normMat[numTestVecs:m,:], classLabelVector[numTestVecs:m], 5)if classifierResult != classLabelVector[i]:errorCount += 1.0print("compute result:%s\t real result:%d" % (numTestVecs-errorCount, numTestVecs))
#testresultList = ['tired of','a little like','very like']#三维特征用户输入precentTats = 15ffMiles = 100iceCream = 1#训练集归一化normMat, ranges, minVals = autoNorm(returnMat)#生成NumPy数组,测试集inArr = np.array([ffMiles, precentTats, iceCream])#测试集归一化norminArr = (inArr - minVals) / ranges#返回分类结果classifierResult = classify_2(norminArr, normMat, classLabelVector, 3)#打印结果print("You may %s this man." % (resultList[classifierResult-1]))print(datingClassTest())

输入数据 15,100,1

得到如下结果：

可以看出

 结果不错，测试准确率里面我用的K=5，如果K=4，那么准确率还可以提升到97%！ 

总结1：KNN的优点（精度高，对异常值不敏感，无数据输入假定）/缺点（计算和空间复杂度）。

总结2：KNN的数据范围（数值型和标称型），K一般是不大于20的整数。

本文数据源自课堂，如有雷同私信立改！

小故事网

网络标签：

相关问题