KNN算法

2018-01-17  本文已影响30人  foochane

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

1. 综述

2. 算法详述

2.1 步骤:

3.2 细节:

3.21 关于K

3.2.2 关于距离的衡量方法:

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 算法优点

5.2 算法缺点

6. 算法改进

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





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

上一篇 下一篇

猜你喜欢

热点阅读