注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

行走的馒头

Stay Hungry, Stay Foolish

 
 
 

日志

 
 

十一、Prototype Methods and KNN  

2012-09-24 23:59:08|  分类: 统计学习初探索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这里主要讨论一些model free的方法,这些方法就像一个黑盒子一样,很难说清楚这些方法中自变量和因变量之间存在某种特定的关系,但是通常他们非常有效。但是这些方法本身的variance比较大,在特征的维度非常高的时候往往表现较差。

 

Prototype Methods

Prototype Methods可用于分类,其要在特征空间中为每个类找到一些具有代表性的点,注意这些选出的prototype不一定是样本中的点。选出的每个prototype都会label为某一特定的类,对于一个新来的样本点,找到和距离最近的那个prototype,然后用这个prototype的类去标记。对于特征的取值空间是连续的情况,通常使用欧拉距离作为距离的度量标准。当然对于离散变量等可以使用其他适合特定问题的距离标准。为了使每个特征在计算距离时会得到公平的待遇,我们需要对每个特征进行标准化(是其均值为0,标准差为1)。如果我们选出的这些prototype能够很好地反映每个类的分布情况,那么这种方法会是非常简洁和高效的,然而怎么去选择这些prototype确实一件难办的事情,下面是一些heuristic的方法。

K-means

K-means是一种常用的聚类算法,我们可以用它来寻找prototypes,方法如下

  1. 对于训练集中的每个类 ,我们用K-means找出R个prototypes,然后这些prototypes所属的类标记为 。一共找到 个prototypes。
  2. 对于一个新的样本点,找到距离最近的prototype,用这个prototype的类标记

这种方法有一个明显的缺点就是,在训练集中的某个样本和离它最近的那个prototype都可能会在不同的类里面,换言之,就是训练误差可能会比较大。

 

Learning Vector Quantization

LVQ在一定程度上避免了K-means的问题,它使训练集中的样本点尽量和这个类里面的那些prototypes的距离较近,同时尽量和其他类中的prototypes距离较远。LVQ的算法表示如下

  1. 对于每个类k,选择R个初始的prototypes:。这里可以使随机选择,也可以用K-means的方法选择。
  2. 随机选择一个训练样本点 ,找到离 最近的那个prototype为 。

    如果 ,说明它们在同一类中,此时让这个prototype朝着靠近 的方向移动一点,表示为 。这里 是learning rate。

    如果,让这个prototype朝着远离 的方向移动一点,表示为

  3. 重复step-2,每次迭代过程中逐步减小,是其最终趋近于0。

可以看出,LVQ是一种on-line的算法,每新来一个样本点,我们都可以更新这些prototypes的位置。

 

 

k-Nearest-Neighbor Classifiers

这类分类器被称之为memory-based,因为没有一个带有有限个参数的模型去刻画数据的整体情况,对于新来的一个样本点 ,我们只需要遍历训练集,找到离它最近的k个训练集中的样本点,然后用这些样本点的类去标记(比如用这k个样本点所属的类的进行投票,用票数最多的那个类去标记 )。

可以看到,当k很小的时候,特别的1-nearest-neighbor clasifier的bias非常小,但是明显这时的overfitting非常严重,所以variance通常会很大。Cover和Hart证明了1-nearest-neighbor clasifier的误差从来不会超过贝叶斯误差的两倍。

 表示样本x属于第k类的概率。令 ,

那么可以看到

这里1-nearest-neighbor error是这样计算的,如果样本点属于类k, 那么他的nearest-neighbor需要刚好同时属于类k才不会产生误分类,所以x属于类k时的error为,所以总的error就是 。当K=2时, ,满足上面1-nearest-neighbor classifier的误差从来不会超过贝叶斯误差的两倍的结论。更一般的存在下面的结论

因此,我们可以根据1-nearest-neighbor classifier的误差来估计贝叶斯误差。

 

Adaptive Nearest-Neighbor Methods

    当数据的维数很高的时候,我们将看到Nearest Neighbor方法的效率会下降的非常厉害。考虑这样的情形,有N个数据点均匀的分布在一个p维的cube  中,令R表示原点到它的1-nearest-neighbor的距离,可以证明

这里 , 表示伽玛函数。下面是一个示意图

从上面的讨论可以看出,在高维空间上数据非常的稀疏,这时对于nearest neighbor方法来说,我们需要采取一些特殊的策略。比如其实只是在特征空间的某个子空间上, 数据所属的类的分布比较分散,在这个子空间上不同类之间的数据点比较有区分性,而其他的那些特征则作用不大。如下图所示,这两个类在竖直方向上的分布差别不明显,但是在水平方向上的分布就要明显的多,所以这时定义距离标准时明显应该减小水平方向的权重,找到更多水平距离比较近的点。

 

Discriminant Adaptive Nearest-Neighbor

    一种叫做discriminant adaptive nearest-neighbor(DANN)的方法就是用来改变在计算距离时不同方向上的权重的,这种方法是一种local的非参数的方法,它针对每个样本点计算其与临近点的距离在各个方向上的权重。对于每个样本点 ,临近点到 的距离可以表示为

其中 是这这些最临近点的within-class covariance矩阵,可表示为 。是between-class covariance矩阵,可表示为

    DANN首先在特征空间上用普通的欧拉距离标准即 来找到个最临近点,然后用这个点计算 ,得到新的距离标准,来重新计算这个点到 的距离,找出最终的 个临近点。下面是一个示意图

Global Dimension Reduction for Nearest-Neighbors

    可以看到DANN是一种local降维的策略,当然,我们也可以使用一种global的策略。对训练集中的每个点,计算between-class covariance ,然后把这些矩阵average一下就得到。设是矩阵的特征向量,其对应的特征值依次减小。我们的目标是要找到一个rank为L的矩阵使得,并且使得

。(11.1)

这里每个包括了样本点局部的降维信息,这里通过(11.1)把数据从p维降到L维上,然后把数据投影在这L个特征向量构成的新的空间上,在新空间上做KNN。


  评论这张
 
阅读(730)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017