机器学习之KNN（k近邻）算法详解
机器学习之KNN（k近邻）算法详解
文章目录
1-1 机器学习算法分类
一、基本分类：
①监督学习（Supervised learning）
②无监督学习
③半监督学习
④强化学习
小结：
2-1 KNN基本流程
一、概念：
2-2 K值的选择
2-3 kd树
一、原理：
二、构造方法：
1-1 机器学习算法分类
一、基本分类：
①监督学习（Supervised learning）
数据集中的每个样本有相应的“正确答案”， 根据这些样本做出
预测， 分有两类： 回归问题和分类问题。
步骤1： 数据集的创建和分类
步骤2： 训练
步骤3： 验证
步骤4： 使用
（ 1） 回归问题举例
例如： 预测房价， 根据样本集拟合出一条连续曲线。
（ 2） 分类问题举例
例如： 根据肿瘤特征判断良性还是恶性，得到的是结果是“良性”或者“恶性”， 是离散的。
监督学习：从给定的训练数据集中学习出一个函数（模型参数）， 当新的数据到来时，可以根据这个函数预测结果。监督学习的训练集要求包括输入输出，也可以说是特征和目标。训练集中的目标是由人标注的。
PCA和很多deep learning算法都属于无监督学习
②无监督学习
无监督学习：输入数据没有被标记，也没有确定的结果。样本数据类别未知， 需要根据样本间的相似性对样本集进行分类（聚类， clustering）试图使类内差距最小化，类间差距最大化。
实际应用中， 不少情况下无法预先知道样本的标签，也就是说没有训练样本对应的类别，因而只能从原先没有样本标签的样本集开始学习分器设计
有监督学习 无监督学习
样本 必须要有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律。 没有训练集，只有一组数据，在该组数据集内寻找规律。
目标 方法是识别事物，识别的结果表现在给待识别数据加上了标签。 因此训练样本集必须由带标签的样本组成。 方法只有要分析的数据集的本身，预先没有什么标签。如果发现数据集呈现某种聚集性， 则可按自然的聚集性分类，但不予以某种预先分类标签对上号为目的。
③半监督学习
半监督学习： 即训练集同时包含有标记样本数据和未标记样本数据。
④强化学习
实质是： make decisions问题，即自动进行决策，并且可以做连续决策。
主要包含四个元素： agent， 环境状态， 行动， 奖励；
强化学习的目标就是获得最多的累计奖励。
小结：
监督学习：
In：有标签
Out：有反馈
目的：预测结果
案例：学认字
算法：分类（类别），回归（数字）
无监督学习：
In：无标签
Out：无反馈
目的：发现潜在结构
案例：自动聚类
算法：聚类，降维
半监督学习:
已知：训练样本Data和待分类的类别
未知：训练样本有无标签均可
应用：训练数据量过时，
监督学习效果不能满足需求，因此用来增强效果。
强化学习：
In：决策流程及激励系统
Out：一系列行动
目的：长期利益最大化，回报函数（只会提示你是否在朝着目标方向前进的延迟反映）
案例：学下棋
算法：马尔科夫决策，动态规划
2-1 KNN基本流程
一、概念：
KNN（K Near Neighbor）：k个最近的邻居，即每个样本都可以用它最接近的k个邻居来代表。
最近邻 (k-Nearest Neighbors， KNN) 算法是一种分类算法， 1968年由 Cover和 Hart 提出， 应用场景有字符识别、 文本分类、 图像识别等领域。
该算法的思想是： 一个样本与数据集中的k个样本最相似， 如果这k个样本中的大多数属于某一个类别， 则该样本也属于这个类别。
二、距离度量
https://blog.csdn.net/sinat_30353259/article/details/80901746
K最近邻 (k-Nearest Neighbors，KNN) 算法是一种分类算法，也是最简单易懂的机器学习算法，没有之一。1968年由 Cover 和 Hart 提出，应用场景有字符识别、文本分类、图像识别等领域。该算法的思想是：一个样本与数据集中的k个样本最相似，如果这k个样本中的大多数属于某一个类别，则该样本也属于这个类别。还是直接讲例子最好懂，一直没找到好的例子，就改造了下Peter Harrington的《机器学习实战》中电影分类的例子，当然实际情况不可能这么简单，这里只是为了说明该算法的用法。
先准备下电影分类数据集（电影名称与分类来自于优酷网；镜头数量则纯属虚构）：
序号
电影名称
搞笑镜头
拥抱镜头
打斗镜头
电影类型
1.
宝贝当家
45
2
9
喜剧片
2.
美人鱼
21
17
5
喜剧片
3.
澳门风云3
54
9
11
喜剧片
4.
功夫熊猫3
39
0
31
喜剧片
5.
谍影重重
5
2
57
动作片
6.
叶问3
3
2
65
动作片
7.
伦敦陷落
2
3
55
动作片
8.
我的特工爷爷
6
4
21
动作片
9.
奔爱
7
46
4
爱情片
10.
夜孔雀
9
39
8
爱情片
11.
代理情人
9
38
2
爱情片
12.
新步步惊心
8
34
17
爱情片
13.
唐人街探案
23
3
17
？
上面数据集中序号1-12为已知的电影分类，分为喜剧片、动作片、爱情片三个种类，使用的特征值分别为搞笑镜头、打斗镜头、拥抱镜头的数量。那么来了一部新电影《唐人街探案》，它属于上述3个电影分类中的哪个类型？用KNN是怎么做的呢？
首先，我们构建一个已分好类的数据集。
对于一个规模巨大的数据集，显然数据库是更好的选择。这里为了方便验证，使用Python的字典dict构造数据集。
movie_data = {"宝贝当家": [45, 2, 9, "喜剧片"],
"美人鱼": [21, 17, 5, "喜剧片"],
"澳门风云3": [54, 9, 11, "喜剧片"],
"功夫熊猫3": [39, 0, 31, "喜剧片"],
"谍影重重": [5, 2, 57, "动作片"],
"叶问3": [3, 2, 65, "动作片"],
"伦敦陷落": [2, 3, 55, "动作片"],
"我的特工爷爷": [6, 4, 21, "动作片"],
"奔爱": [7, 46, 4, "爱情片"],
"夜孔雀": [9, 39, 8, "爱情片"],
"代理情人": [9, 38, 2, "爱情片"],
"新步步惊心": [8, 34, 17, "爱情片"]}
第二步：计算一个新样本与数据集中所有数据的距离。
这里的新样本就是："唐人街探案": [23, 3, 17, "？片"]。欧式距离是一个非常简单又最常用的距离计算方法。
其中x,y为2个样本，n为维度，xi，yi为x，y第i个维度上的特征值。如x为："唐人街探案": [23, 3, 17, "？片"]，y为："伦敦陷落": [2, 3, 55, "动作片"]，则两者之间的距离为：=43.42。
下面为求与数据集中所有数据的距离代码：
x = [23, 3, 17]
KNN = []
for key, v in movie_data.items():
d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2)
KNN.append([key, round(d, 2)])
print(KNN)
输出结果：
[['谍影重重', 43.87], ['伦敦陷落', 43.42], ['澳门风云3', 32.14], ['叶问3', 52.01], ['我的特工爷爷', 17.49], ['新步步惊心', 34.44], ['宝贝当家', 23.43], ['功夫熊猫3', 21.47], ['奔爱', 47.69], ['美人鱼', 18.55], ['夜孔雀', 39.66], ['代理情人', 40.57]]
第三步：按照距离大小进行递增排序。
KNN.sort(key=lambda dis: dis[1])
输出结果：
[['我的特工爷爷', 17.49], ['美人鱼', 18.55], ['功夫熊猫3', 21.47], ['宝贝当家', 23.43], ['澳门风云3', 32.14], ['新步步惊心', 34.44], ['夜孔雀', 39.66], ['代理情人', 40.57], ['伦敦陷落', 43.42], ['谍影重重', 43.87], ['奔爱', 47.69], ['叶问3', 52.01]]
第四步：选取距离最小的k个样本。
这里取k=5；
KNN=KNN[:5]
输出：[['我的特工爷爷', 17.49], ['美人鱼', 18.55], ['功夫熊猫3', 21.47], ['宝贝当家', 23.43], ['澳门风云3', 32.14]]
第五步：确定前k个样本所在类别出现的频率，并输出出现频率最高的类别。
labels = {"喜剧片":0,"动作片":0,"爱情片":0}
for sin KNN:
label = movie_data[s[0]]
labels[label[3]] += 1
labels =sorted(labels.items(),key=lambdal: l[1],reverse=True)
print(labels,labels[0][0],sep='\n')
输出结果：
[('喜剧片', 4), ('动作片', 1), ('爱情片', 0)]
喜剧片
KNN有几个特点：
（1）KNN属于惰性学习（lazy-learning）
这是与急切学习（eager learning）相对应的，因为KNN没有显式的学习过程！也就是说没有训练阶段，从上面的例子就可以看出，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。
（2）KNN的计算复杂度较高
我们从上面的例子可以看到，新样本需要与数据集中每个数据进行距离计算，计算复杂度和数据集中的数据数目n成正比，也就是说，KNN的时间复杂度为O(n)，因此KNN一般适用于样本数较少的数据集。
（3）k取不同值时，分类结果可能会有显著不同。
上例中，如果k取值为k=1，那么分类就是动作片，而不是喜剧片。一般k的取值不超过20，上限是n的开方。
————————————————
版权声明：本文为CSDN博主「saltriver」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/saltriver/article/details/52502253