最邻近规则分类(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: 距离）
【注】：本文为麦子学院机器学习课程的学习笔记
