1、kNN算法(K 最近邻(k-Nearest Neighbors))描述

简单地说,k-近邻算法采用测量不同特征值之间的距离方法进行分类。

k-近邻算法是一种基本分类与回归方法;它是是监督学习中分类方法的一种,属于懒散学习法(惰性学习方法)。


给定一个训练集D和一个测试对象z,该测试对象是一个由属性值和一个未知的类别标签组成的向量,该算法需要计算z和每个训练对象之间的距离(或相似度),这样就可以确定最近邻的列表。然后将最近邻中实例数量占优的类别赋给z。(主要思想是如果一个样本在特征空间中的k个最近的样本中的大多数都属于某个类别,则该样本属于这个类别,并具有这个类别上的特性
)。

 

注释: (1)所谓监督学习与非监督学习,是指训练数据是否有标柱类别,若有则为监督学习,否则为非监督学习。
监督学习是指根据训练数据学习一个模型,然后能对后来的输入做预测。在监督学习中,输入变量和输出变量可以是连续的,也可以是离散的。若输入变量和输出变量均为连续变量,则称为回归;输出变量为有限个离散变量,则称为分类。


(2)懒散学习法在训练过程中不需要做许多处理。只有当新的未被分类的数据输入时,这类算法才会去做分类。积极学习法则会在训练中建立一个分类模型,当新的未分类数据输入时,这类学习器会把新数据也提供给这个分类模型。

2.KNN算法的工作原理:


存在一个样本数据集合,也称作为训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后,将新的数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。

3、KNN算法的一般流程

(1)收集数据:可以使用任何方法。

(2)准备数据:距离计算所需要的数值,最好是结构化的数据格式。

(3)分析数据:可以使用任何方法。

(4)训练算法:此步骤不适用于k-近邻算法。

(5)测试算法:计算错误率。

(6)使用算法:首先需要输入样本数据和结构化的输出结果,然后运行KNN算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续处理

 

注释:
距离度量公式有:欧几里得距离,明可夫斯基距离,曼哈顿距离,切比雪夫距离,马氏距离等;相似度的度量公式有:余弦相似度,皮尔森相关系数,Jaccard相似系数。 补充:欧几里得距离度量会受特征不同单位刻度的影响,所以一般需要先进行标准化处理。

类别的判断方法:(1)投票决定:少数服从多数,近邻中哪个类别的点最多就分为该类。

(2)加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大。 knn还可用于回归,目标样本的属性值是k个邻居属性值的平均值。

4、KNN算法的优点和缺点

优点: 

简单,易于理解,易于实现,无需估计参数,无需训练(不需要花费任何时间做模型的构造), 特别适合多分类问题,适合对稀有事件进行分类,精度高,对异常值不敏感,
无数据输入假定。

缺点:

消极学习法, 需要大量的存储空间(需要保存全部数据集),
耗时(需计算目标样本与训练集中每个样本的值),可解释性差;即该算法的存储复杂度是O(n),其中n为训练对象的数量,时间复杂度也是O(n)(
计算复杂度高,空间复杂度高)

注释:

积极学习法:先根据训练集构造出分类模型,根据分类模型对测试集分类。

消极学习法(基于实例的学习法):推迟建模,当给定训练元组时,简单地存储训练数据,一直等到给定一个测试样本。


适用数据范围:数值型和标称型。(标称型:一般在有限的数据中取,而且只存在‘是’和‘否’两种不同的结果(一般用于分类);数值型:可以在无限的数据中取,而且数值比较具体化,例如4.02,6.23这种值(一般用于回归分析))

5、应用KNN的常见问题

(1)k值设定为多大? 

k太小,分类结果易受噪声的影响;k太大,近邻中又可能包含太多的其它类别的点。(对距离加权,可以降低k值设定的影响)。

k值通常是采用交叉检验来确定(以k=1为基准)。

经验规则:k一般低于训练样本数的平方根

(2)类别如何判定最合适?

投票法没有考虑近邻的距离的远近,距离更近的近邻也许更应该决定最终的分类,所以加权投票法更恰当一些。

(3)如何选择合适的距离衡量?

高维度对距离衡量的影响:众所周知当变量数越多,欧式距离的区分能力就越差。

变量值域对距离的影响:值域越大的变量常常会在距离计算中占据主导作用,因此应先对变量进行标准化。

(4)训练样本是否要一视同仁? 

在训练集中,有些样本可能是更值得依赖的。 

可以给不同的样本施加不同的权重,加强依赖样本的权重,降低不可信赖样本的影响。(如何判断样本可信不可信)

(5)能否大幅减少训练样本量,同时又保持分类精度? 

浓缩技术(condensing) 

编辑技术(editing)

6、KNN与推荐系统

利用KNN进行推荐的方法分为:

(1)user-based: 先利用KNN算法找到与目标用户兴趣相似的k个用户,再根据这些相似用户的兴趣为目标用户进行推荐。

(2)item-based: 利用KNN计算与目标用户喜欢的物品相似的k个物品,然后推荐给目标用户

7、KNN算法的应用领域

字符识别、文本分类、图像识别、改进约会网站、手写识别系统、电影分类

 

 

 

KNN算法简单实战:简单的电影分类

需要模块:numpy(科学计算包),operator(运算符模块);

欧式距离公式:



 

环境:python3.6 ,Pycharm

 

kNN.py
import numpy as np import operator ''' 函数说明: 创建数据集 Returns: group - 数据集 labels
- 分类标签 ''' def createDataSet():
group=np.array([[1,101],[5,89],[108,5],[115,8]]) #数据集,四组二维特征
labels=['爱情片','爱情片','动作片','动作片'] #分类标签,四组特征的标签 return group,labels """
函数说明:kNN算法,分类器 Parameters: inX - 用于分类的数据(测试集) dataSet - 用于训练的数据(训练集) labes -
分类标签 k - kNN算法参数,选择距离最小的k个点 Returns: sortedClassCount[0][0] - 分类结果 """ def
classify0(inX, dataSet, labels, k): # numpy函数shape[0]返回dataSet的行数 dataSetSize =
dataSet.shape[0] # b =
tile(a,(m,n)):即是把a数组里面的元素复制n次放进一个数组c中,然后再把数组c复制m次放进一个数组b中 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) #
返回次数最多的类别,即所要分类的类别 return sortedClassCount[0][0] if __name__ == '__main__': #
创建数据集 group, labels = createDataSet() # 测试集 test = [101, 20] # kNN分类 test_class
= classify0(test, group, labels, 3) # 打印分类结果 print(test_class)
结果为:



 

注意:numpy函数shape[0]、tile()的用法、sum(axis=1)、argsort()

 

 

 

参考资料:《机器学习实战》

博客:https://blog.csdn.net/c406495762/article/category/7029976
<https://blog.csdn.net/c406495762/article/category/7029976>

博客网站:http://cuijiahua.com/ <http://cuijiahua.com/>

 

 

 

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信