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→∞时接近最优
- 近邻法的主要缺点是
- 对计算机的存储量和计算量的要求很大，耗费大量测试时间
- 没有考虑决策的风险。
- 对其错误率的分析都是建立在渐进理论基础上的。
