KNN算法

最邻近规则分类(K-Nearest Neighbor)

1. 综述

• Cover和Hart在1968年提出了最初的邻近算法
• 分类(classification)算法
• 输入基于实例的学习(instance-based learning), 懒惰学习(lazy learning)

2. 算法详述

2.1 步骤：

• 为了判断未知实例的类别，以所有已知类别的实例作为参照
• 选择参数K,对任意一个未知实例选取最近的K个已知实例进行归类，通常K的值不会太大，选取1,3,5,7等等的奇数
• 计算未知实例与所有已知实例的距离
• 选择最近K个已知实例
• 根据少数服从多数的投票法则(majority-voting)，让未知实例归类为K个最邻近样本中最多数的类别

3.2 细节:

3.21 关于K

• 根据实践来进行规划

3.2.2 关于距离的衡量方法:

• 欧氏距离( Euclidean distance)也称欧几里得距离

• 其他距离衡量： 余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）

4 举例

问题：估计未知电影属于什么类型？

4.1 步骤一：

建立平面坐标，将7部电影转化为7个坐标，X坐标，X坐标 及类型如如下图所示，通过A~F点，估计G点的类型。

4.2 步骤二：计算距离

计算代码如下：

import math

def ComputeEuclideanDistance(x1,y1,x2,y2):
    d = math.sqrt(math.pow((x1-x2),2)+math.pow((y1-y2),2))
    return d

d_ag = ComputeEuclideanDistance(3,104,18,90)
d_bg = ComputeEuclideanDistance(2,100,18,90)
d_cg = ComputeEuclideanDistance(1,81,18,90)
d_dg = ComputeEuclideanDistance(101,10,18,90)
d_eg = ComputeEuclideanDistance(99,5,18,90)
d_fg = ComputeEuclideanDistance(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: 20.518284528683193
d_bg: 18.867962264113206
d_cg: 19.235384061671343
d_dg: 115.27792503337315
d_eg: 117.41379816699569
d_fg: 118.92854997854805

4.3 步骤三：估计

比较以上的计算出的6个欧氏距离，选取最近的3个距离对应的点A,B,C三个点，由于这三个点都属于Romance类型，则未知数据G点根据最近邻规则分类（KNN）也属于Romance类型。 若选取的点中两个类型都存在，则遵从少数服从多数的原则，选取类别数目多的作为未知点的类别。

5. 算法优缺点：

上图有两个不同类别的点分别为红色和蓝色，绿色的点为新的实例，问这个点的归类？

假设取K=1，只看距离绿色最近的一个点，应该和蓝色分类到一起；假设K=4，包含3个红色与1个蓝色，根据少数服从多数原则，应该归类为红色；假设K=9，应该归类为红色。

所以KNN算法对于K的选择非诚敏感，K=1时，不能够防止噪音，通常会增大K，以增加对噪音的健壮性

5.1 算法优点

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

5.2 算法缺点

• 需要大量空间储存所有已知实例
• 算法复杂度高（需要比较所有已知实例与要分类的实例）
• 当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本

6. 算法改进

考虑距离，根据距离加上权重 比如: 1/d (d: 距离）

            【注】：本文为麦子学院机器学习课程的学习笔记