麦子学院深度学习基础 —— 机器学习 —— 最近邻规则分类 KNN 算法

最邻近规则分类（K-Nearest Neighbor）KNN 算法

1.综述：

1.1 Cover 和 Hart 在 1968 年提出了最初的近邻算法。

1.2 分类（Classification）算法。

1.3 输入基于实例的学习（instance-based learning）、懒惰学习（lazy learning）。

基于实例的学习： 是指每次学习是根据实例来进行的。
懒惰学习： 是指我们在处理训练集的时候，并没有建立任何模型，而是在对未知数据进行归类的时候才根据和已知数据的比较结果来进行归类操作。
（临时抱佛脚算法）

2.例子

电影名称	打斗次数	接吻次数	电影类型
California Man	3	104	Romance
He’s Not Really into Dudes	2	100	Romance
Beautiful Woman	1	81	Romance
Kevin Longblade	101	10	Action
Robo Slayer 3000	99	5	Action
Amped II	98	2	Action
未知	18	90	Unknown

3.算法详述

3.1步骤：

为了判断未知实例的类别，以所有已知类别的实例作为参照
选择参数K
计算未知实例与所有已知实例的距离
选择最近K个已知实例
根据少数服从多数的投票法则（majority-voting），让未知实例归类为K个最邻近样本中最多树的类别。

3.2 细节：

关于K
关于距离的衡量方法
3.2.1 Euclidean Distance 定义

$Euclidean Distance (d) = \sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$

$E(X,Y) = \sqrt{\sum_{i=0}^{n}(x_{i}-y_{i})^{2}}$

其他距离衡量：余弦值（Cos)、相关度（Correlation）、曼哈顿距离（Manhattan Distance）。

3.3 举例：

import math 
def ComputerEuclideanDistance(x1, y1, x2, y2):
  d = math.sqrt(math.pow((x1-x2),2) + math.pow((y1-y2),2))
  return d
d_ag = ComputerEuclideanDistance(3, 104, 18, 90)
d_bg = ComputerEuclideanDistance(2, 100, 18, 90)
d_cg = ComputerEuclideanDistance(1, 81, 18, 90)
d_dg = ComputerEuclideanDistance(101, 10, 18, 90)
d_eg = ComputerEuclideanDistance(99, 5, 18, 90)
d_fg = ComputerEuclideanDistance(98, 2, 18, 90)

print("d_ag: ", d_ag)
print("d_bg: ", d_bg)
print("d_cg: ", d_cg)
print("d_dg: ", d_dg)
print("d_eg: ", d_eg)
print("d_fg: ", d_fg)

根据计算结果，选择其中举例最近的三个样本(d_ag,d_bg,d_cg)作为未知样本的分类依据。

4.算法的优缺点：

4.1 算法优点：

简单、易于理解、容易实现、通过对K的选择可具备丢噪音数据的健壮性。

4.2 算法缺点：

需要大量空间储存所有已知实例
算法复杂度高（需要比较所有已知实例与要分类的实例）
当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并未接近目标样本。
（注：K通常会选择奇数，而不是偶数。因为奇数情况下的投票总会有一方会胜出。）

5.改进版本：

考虑距离，根据距离加上权重：