问题
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: 距离）
