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

举报
nimo的小舔狗 发表于 2022/05/11 00:01:18 2022/05/11
【摘要】 一: K近邻算法描述         k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。K近邻可能是机器学习最容易理解的算法,事实上它根本就没有进行学习。它的工作原理是:存在...

一: K近邻算法描述

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

  1. 计算已知类别数据集中的点与当前点之间的距离;
  2. 按照距离递增次序排序;
  3. 选取与当前点距离最小的k个点;
  4. 确定前k个点所在类别的出现频率;
  5. 返回前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中其他两个特征-玩视频游戏所耗时间占比和每周消费冰淇淋公斤数的影响。而产生这种现象的唯一原因,仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的,因此作为三个等权重的特征之一,飞行常客里程数并不应该如此严重地影响到计算结果。

       在处理这种不同取值范围的特征值时,我们通常采用的方法是将数值归一化,如将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。