近邻法总结

1.最近邻法

• 算法思想
         对于一个新样本，把它逐一与已知样本比较，找出距离新样本最近的已知样本，以该样本的类别作为新样本的类别。
• 算法描述
  
  

2.k-近邻法

3.近邻法的快速算法

4.剪辑近邻法

• 算法思想
         如果训练样本处在两类分布重合的区域，其中部分样本就会落在最优分类面错误一侧，在进行近邻法分类时，这样的训练样本会误导决策从而使分类错误。
         如果设法把图中阴影部分的已知样本去掉，决策时就不会受到那些错分样本的影响，可以使近邻法的决策面更接近最优分类面。
• 算法步骤
  ①划分
  将样本集划分为考试集$X_{NT}$和训练集$X_{NR}$两部分。
  ②剪辑
  用训练集$X_{NR}$中的样本对考试集$X_{NT}$中的样本进行近邻法分类，从$X_{NT}$中除去被错误分类的样本，剩余样本构成剪辑样本集$X_{NTE}$。
  ③分类
  用$X_{NTE}$对未来样本进行近邻法分类。
• 多重剪辑方法（MULTIEDIT）
  ①划分
  把样本集随机划分为s个子集，$X_1,X_2,...,X_s,s\ge 3$。
  ②分类
  用$X_{(i+1)mod(s)}$对$X_i$中的样本分类，$i=1,2,...,s$。比如，如果s=3，则用$X_2$对$X_1$分类，用$X_3$对$X_2$分类，用$X_1$对$X_3$分类。
  ③剪辑
  从各个子集中去掉在②中被分错的样本。
  ④混合
  把剩下的样本合在一起，形成新的样本集$X_{NE}$。
  ⑤迭代
  用新的样本集$X_{NE}$替代原样本集，转①。如果在最近的m次迭代中都没有样本被剪掉，则终止迭代，用最后的$X_{NE}$作为剪辑后的样本集。

5.压缩近邻法

• 算法思想
         根据近邻法的分类原理，可以发现，那些远离分类边界的样本对于最后的分类决策没有贡献。
         只要能够设法找出各类样本中最有利于用来区分其它类的代表性样本，就可以把很多训练样本去掉，简化决策的计算。
• 算法步骤
  ①将样本集$X_N$分为两个活动的子集$X_S$和$X_G$，前者称作储存集Storage，后者称作备选集GrabBag。
  ②算法开始时，$X_S$只有一个样本，其余样本都在$X_G$中。
  对$X_G$中的每一个样本$x$，如果用$X_S$中的样本可以对它正确分类，则该样本保留在$X_G$中；否则移到$X_S$。
  以此类推，直到没有样本再搬移为止。
  ③$X_S$中的样本作为代表样本，对未来样本进行近邻法分类。

6.错误率分析

本文内容参考：张学工教授的《模式识别》
如有错误或者不足之处，欢迎大家留言指正！