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

问题

image.png

当我们知道一个未知电影的两个特征,怎么判断出电影的类型呢?

概念

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别.

• Cover和Hart在1968年提出最初的临近算法
• 邻近算法属于分类（classification）算法
• 输入基于实例的学习（instance-based learing）,懒惰学习（lazy learing）——处理训练集时并没有建造任何的模型，当对一个未知的实例进行归类时才进行归类

算法

• 为了判断未知实例的类别，以所有已知类别的实例作为参照
• 选择参数K
• 计算未知实例与所有已知实例的距离
• 选择最近K个已知实例

• 根据少数服从多数的投票法则(majority-voting)，让未知实例归类为K个最邻近样本中最多数的类别

  
  image.png

计算结果

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
print d_bg
print d_cg
print d_dg
print d_eg
print d_fg

20.5182845287
18.8679622641
19.2353840617
115.277925033
117.413798167
118.928549979

我们发现最近的3个点

image.png

的电影都是爱情片,因此预测该未知电影属于爱情片

结论

优点:

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

---

缺点:

image.png

• 我们看到Y点明显属于红色类别,但根据少数服从多数原则,算法将Y点归属为蓝色; 当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本
• 需要大量空间储存所有已知实例
• 算法复杂度高（需要比较所有已知实例与要分类的实例）

---

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