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

一： K近邻算法描述

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

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

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

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

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

import tensorflow.compat.v1 as tf
tf.disable_v2_behavior()
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns
import scipy.optimize as opt
data01 = 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 classes
test01 = [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）input
fr = 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）picture
fig, 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') #didntLike
	if i == 2:
		LabelsColors.append('orange') #smallDoses
	if i == 3:
		LabelsColors.append('red') #largeDoses

#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第二列(玩游戏)数据画散点数据,散点大小为15,透明度为0.5
axs[0][0].scatter(x=returnMat[:,0], y=returnMat[:,1], color=LabelsColors,s=15, alpha=.5)
#设置标题,x轴label,y轴label
axs0_xlabel_text = axs[0][0].set_xlabel(u'fly distance')
axs0_ylabel_text = axs[0][0].set_ylabel(u'game time')

#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
axs[0][1].scatter(x=returnMat[:,0], y=returnMat[:,2], color=LabelsColors,s=15, alpha=.5)
#设置标题,x轴label,y轴label
axs1_xlabel_text = axs[0][1].set_xlabel(u'fly distance')
axs1_ylabel_text = axs[0][1].set_ylabel(u'icecream mount')

#画出散点图,以datingDataMat矩阵的第二(玩游戏)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
axs[1][0].scatter(x=returnMat[:,1], y=returnMat[:,2], color=LabelsColors,s=15, alpha=.5)
#设置标题,x轴label,y轴label
axs2_xlabel_text = axs[1][0].set_xlabel(u'game time')
axs2_ylabel_text = axs[1][0].set_ylabel(u'icecream mount')

plt.show()

#（3）构架kNN
def 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 = diffMat**2
	#sum()所有元素相加,sum(0)列相加,sum(1)行相加
	sqDistances = sqDiffMat.sum(axis=1)
	#开方,计算出距离
	distances = sqDistances**0.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.0

	for 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.0
	print("compute result:%s\t real result:%d" % (numTestVecs-errorCount, numTestVecs))

#test
resultList = ['tired of','a little like','very like']
#三维特征用户输入
precentTats = 15
ffMiles = 100
iceCream = 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的整数。

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

文章来源: blog.csdn.net，作者：渣渣ye，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/yyfloveqcw/article/details/123964223