模式识别 第六章 近邻法则

---

title: 模式识别 第六章 近邻法则
date: 2017-03-26 18:47:51
categories: ML/卢晓春 模式识别引论
mathjax: true
tags: [Machine Learning]

---

第六章 其他分类方法 近邻法则

最近邻法

算法：新样本属于 最近的训练样本所属的类别

Paste_Image.png

缺点：偶然性真大

K近邻法

最近邻法的推广。k Nearest Neighbor Classification Rule
算法：最近的k个训练样本，所属的类别最多的类，即新样本的类。因此k一般选奇数

模拟k近邻法

k近邻法当样本不均衡时，远离测试样本的样本点会产生很大干扰。
算法：可以采用模糊分类的思想，引入隶属度函数的概念，对K个近邻的样本点的贡献加权，来进行分类判决。

改进的近邻法

• 快速搜索近邻法

• 剪辑近邻法
  利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。

  • 两分剪辑近邻法算法：把原样本集分为样本集和测试集，用测试机的数据来筛选样本集。

  Paste_Image.png
  Paste_Image.png
  Paste_Image.png

  • 重复剪辑近邻法算法：

  Paste_Image.png

• 压缩近邻法
  剪辑近邻的结果只是去掉了两类边界附近的样本，而靠近两类中心的样本几乎没有被去掉。在剪辑的基础上，再去掉一部分这样的样本，有助于进一步缩短计算时间和降低存储要求。这类方法叫作压缩近邻法。

  • 算法：
    • 压缩近邻法中定义了两个存储器，一个用来存放即将生成的样本集，Store；另一个存放原样本集，Grabbag。
    • 初始化。随机挑选一个样本放在Store中，其它样本放入Grabbag。
    • 用当前的Store中的样本按最近邻法对Grabbag中的样本分类。假如分类正确，该样本放回Grabbag；否则放入Store。
    • 重复上述过程，直到在执行中没有一个样本从Grabbag转到Store或者Grabbag为空。
  • Paste_Image.png

优缺点

• 近邻法是典型的非参数法，其优点是
  • 实现简单
  • 分类结果比较好，在训练样本N→∞时接近最优
• 近邻法的主要缺点是
  • 对计算机的存储量和计算量的要求很大，耗费大量测试时间
  • 没有考虑决策的风险。
  • 对其错误率的分析都是建立在渐进理论基础上的。