K -近邻算法（kNN)（一）
K -近邻算法（kNN)（一）
用户6021899
发布于 2019-08-14 16:41:01
发布于 2019-08-14 16:41:01
大多数人都喜欢看电影，电影是如何分类呢？为了简化问题，假设所有的电影要么是爱情片，要么是动作片。如果我们已知一些电影的分类结果和电影中打斗镜头及亲吻镜头的次数，如下：
现有一部新电影，打斗镜头及亲吻镜头的次数已知，我们如何来预测这部新电影的类型呢？
我们可以把电影样本的特征值看做是在欧氏空间的坐标（特征值可能需要归一化处理使得各个特征的权重相等），再依次计算未知电影与已知电影的欧氏距离（也可以是其它距离）：
我们按照距离从小到大排序，可以找到k个距离最近的电影。假定k=3，则k个已知样本的类型里最多的类型是爱情片，因此我们预测未知电影也是爱情片。以上预测电影分类的算法就是 k -近邻算法（kNN)。
k -近邻算法的基本原理是：存在一个训练数据（每个样本都有特征和分类标签的样本集），输入没有分类标签的新样本后，依次计算新样本和各个训练样本的距离，找出最相似（最近邻）的k个已知样本，提取它们的分类标签。最后，选择这k个分类标签中出现次数最多的分类，做为新样本的分类。
假设训练数据保存在csv文件中（格式见本篇第一张图片去掉最后一行），下面的代码可以读出特征数据和分类标签。
import numpy as np
def get_trainSet(path):
data = np.loadtxt(path, delimiter =",", skiprows =1, usecols =(1,2))
labels = np.loadtxt(path, delimiter =",", skiprows =1, usecols = -1,dtype = str)
return data, labels
dataset, labels = get_trainSet("电影分类训练集.csv")>>> dataset
array([[ 3., 104.],
[ 2., 100.],
[ 1., 81.],
[101., 10.],
[ 99., 5.],
[ 98., 2.]])
>>> labels
array(['爱情片', '爱情片', '爱情片', '动作片', '动作片', '动作片'], dtype='<U3')下面实现kNN算法：
先对训练数据归一化处理：
def autoNorm(dataSet):
'''归一化, 将所有特征值转换到【0~1】区间的值'''
minVals = dataSet.min(axis =0) #每种特征取一个最小值
maxVals = dataSet.max(axis =0) #每种特征取一个最大值
ranges = maxVals - minVals # 最大值 - 最小值
#满足使用广播的条件，shape不同也能运算
normDataSet = dataSet -minVals
normDataSet = normDataSet / ranges
return normDataSet, ranges, minVals下面是算法的核心部分：
def classify(X, dataSet, labels, k=3):
#n = dataSet.shape[0] #训练集样本个数
diff = dataSet - X #使用广播，shape不同也能运算
sqr_diff = diff**2
sqrDistance = sqr_diff.sum(axis = 1) #每行所有列求和
distance = sqrDistance**0.5 #计算出了X与每个样本的欧氏距离
#print(distance)
sortedDistIndicies = distance.argsort() # 按值的大小（值从小到大）返回对应的索引
classCount = {} #分类计数字典
for i in range(k):
voteLabel = labels[ sortedDistIndicies[i] ] #k个距离最小样本对应的标签
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 #有则加1，则设为（0+1）
#print(classCount)
#字典转列表，按列表的第2个元素 从大到小排序
import operator
sortedClassCount = sorted(classCount.items() , key = operator.itemgetter(1), reverse = True)
#print(sortedClassCount)
return sortedClassCount[0][0]算法的输入输出：
dataSet, labels = get_trainSet("电影分类训练集.csv") #读取训练数据和分类标签
normDataSet, ranges, minVals = autoNorm(dataSet) #归一化
X = np.array([18,90]) #输入的未知样本数据 原始值
normX= (X- minVals) / ranges #未知样本数据 归一化
X_label = classify(normX, normDataSet, labels, k=4)
print("预测的分类是:", X_label)kNN算法的优点是：精度高，对异常值不敏感（与异常值的距离较远），无数据输入假定。缺点是计算的时间复杂度和空间复杂度较高。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-09，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 Python可视化编程机器学习OpenCV 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读