机器学习总结（三）：最近邻规则KNN算法（K-Nearest Neighbor）

1、综述

是一种分类算法，输入基于实例的学习，是要输入已知的实例进行训练学习。又称懒惰学习。

2、举例

如下图，进行电影题材分类，前面题材都是已知的对最后一个电影是什么题材进行预测。

如下图，将电影名称不同的点，打斗次数看成X轴，接吻次数看成Y轴，将结果看成点类型 可以看成豆子分类，以实例为参照，根据位置实例到已知实例的距离进行判断。

3、算法详述

3.1步骤：

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

3.2细节：

K的取值：选取何是方法 距离的计算方法：余弦值，相关度，曼哈顿距离（计算方法下图），以及勾股定理。

3.2实例：

1、电影类型分类： 先计算G点到其他点的距离：

import math # 定义函数，计算距离 # pow是求几次方,pow（x，2）是求x的平方，sqrt（）是开方。 def ComputeEuclideanDistance(x1, y1, x2, y2): d = math.sqrt(math.pow((x1-x2), 2) + math.pow((y1-y2), 2)) return d # 求A点到G点的距离 d_ag = ComputeEuclideanDistance(3, 104, 18, 90) # 求B点到G点的距离 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.518284528683193 18.867962264113206 19.235384061671343 115.27792503337315 117.41379816699569 118.92854997854805

根据距离可以看出，G点属于浪漫类电影，

4、算法优缺点

优点：简单，易于理解，容易实现 缺点：需要大量空间储存已知实例。 改进：在距离上加上权重。

5、应用

python中调用neighbors,datasets(数据集)。