临近取样算法(K-Nearest-Neighbor)

1.综述
  1.1Cover和Hart1968年提出了最初的邻近算法
  1.2分类(classification)算法
  1.3基于实例的学习(instance-based learning),分类之前并不创建数据模型,因此叫做懒惰学习(lazy learning)
2.例子:
电影名称
打斗次数 接吻次数 电影类型
Califomia Man 3 104 Romance
He’s Not Really into Duckes 2 100 Romance
Beautiful Woman 1 81 Romance
Kevin Longbiade 101 10 Action
Robo Slayer 3000 99 5 Action
Amped LL 98 2 Action
未知 18 90 Unknown
未知电影属于什么类型?
将上述例子抽象成以下数据模型:
x坐标 y坐标 点类型
A点 3 104 Romance
B点 2 100 Romance
C点 1 81 Romance
D点 101 10 Action
E点 99 5 Action
F点 98 2 Action
G点 18 90 Unknown
3.算法详述
  3.1步骤:
  为了判断未知实例的类别,以所有已知实例作为参照
  选择参数K
  计算未知实例与所有已知实例的距离(计算出G点到其它所有实例点的距离)
  选择最近k个已知实例
  根据少数服从多数的投票法则(majority-voting),让未知实例归类为k个最邻近样本中最多数的类别
  3.2 细节:
  关于k
  关于距离的衡量方法:
    3.2.1Educlidean Distance定义
            
           如果计算多维空间距离,公式如下:
                
         其他距离衡量算法:余弦值(cos),相关度(correlation),曼哈顿距离(Manhattan distance)
       计算“G点”到其它各点的距离(python实现):
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:”+str(d_ag))
print(“d_bg:”+str(d_bg))
print(“d_cg:”+str(d_cg))
print(“d_dg:”+str(d_dg))
print(“d_eg:”+str(d_eg))
print(“d_fg:”+str(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
当k=3时(k值尽量取奇数),取距离最近的三个实例
d_ag:20.518284528683193
d_bg:18.867962264113206
d_cg:19.235384061671343
       由于这三个实例所属类型”Romance “占比较大,所以”G点”类型为”Romance”
 
  4.算法优缺点
     4.1算法优点
          简单
          易于理解
          容易实现
          通过对k值的增大可降低噪音数据干扰
          
          
     4.2算法缺点
           
           4.2.1需要大量空间储存所有已知的实例
           4.2.2算法复杂度高(需要比较所有已知实例与要分类的实例距离)
           4.2.3当其样本分布不平衡时,比如其中一类样本过大(实例数量过多)占主导的时候,新的未知实例容易被归类为这个主导样本,因为这类样本实例数量过大,但这个新的未知实例实际并未接近目标样本(图例2中的Y点属于此情况)
 5.改进版本
     当k个最近距离样本占比分析时考虑距离,根据距离加上权重值
     比如:1/d(d:距离)

About the Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注