lecture06

Heilongjiang University

Sunzhigang,2191313 1

第六章 其他分类方法

Heilongjiang University

Sunzhigang,2191313 2 回顾：

最简单的分段线性分类器：把各类划分为若干子类，以子类中心作为类别代表点，考查新样本到各代表点的距离并将它分到最近的代表点所代表的类。

极端情况，将所有样本都作为代表点 

近邻法（Nearest-Neighbor method）

Heilongjiang University

Sunzhigang,2191313 3 6.1 近邻法（Nearest-Neighbor Method）

6.1.1 最近邻法

样本集 ),(,),,(),,(2211NNNxxxS

ix：样本，1：类别标号，ci,,2,1

样本ix与jx之间的距离),(jixx：比如欧氏距离jixx

对未知样本x，求NS中与之距离最近的样本x，（类别为）

),(min),(,,1jNjxxxx

则将x分到类，即 )(ˆx（或记作)(ˆ1x）

—— 最近邻决策（一近邻决策） Heilongjiang University

Sunzhigang,2191313 4

另一种表达方法：

i类判别函数 kikixxxgmin)(，ikix，iNk,,1

决策规则： if )(min)(,,1xgxgicij， then jX

 最近邻法的错误率（渐近分析）

结论： **1*12PccPPP

其中：*P：贝叶斯错误率

1P：样本无穷多时最近邻法的错误率（渐近平均错误率）

前提：样本集独立同分布 Heilongjiang University

Sunzhigang,2191313 5 6.1.2 k-近邻法（kNN）

最近邻法（一近邻法）的推广：

找出x的k个近邻，看其中多数属于哪一类，则把x分到哪一类。

一般表示： c类i，ci,,1，N个样本。

ik，ci,,1为x的k个近邻中属于i的样本数

判别函数： iikxg)(，ci,,1

决策规则： if icijkxg,,1max)(，then jx

Heilongjiang University

Sunzhigang,2191313 6

渐近平均错误率的界：

N无穷大时，k越大，kP的上限越低（越靠近下限）。但k应始终是N中的一小部分，保证k个近邻均充分接近x。否则这一关系不成立。

一般来说，总有

***12PccPPPk

或者简化为 **2PPPkHeilongjiang University

Sunzhigang,2191313 7 问题

① 存储量和计算量

② 票数接近时风险较大，有噪声时风险加大

③ 有限样本下性能如何？

改进：

① 减少计算量和存储量

② 引入拒绝机制

③ 根据实际问题修正投票方式

如加权投票，否决票等

如距离加权，考虑样本比例及先验概率等

Heilongjiang University

Sunzhigang,2191313 8 6.1.3 近邻法的快速算法

近邻法在计算上的问题：

快速算法基本思想：

把样本集分级分成多个子集（树状结构）

每个子集（结点）可用较少几个量代表

通过将新样本与各结点比较排除大量候选样本

只有最后的结点（子集）中逐个样本比较，找出近邻

比较新样本需与每个样本做需存储所有训练样本Heilongjiang University

Sunzhigang,2191313 9 基本算法：分支定界算法（Branch-Bound Algorithm）

符号约定：

pX：结点p对应的样本子集

pN：pX中的样本数

pM：子集pX中的样本均值（中心点）

),(maxpixpMxDrpiX：pX中离中心点最远的距离

B：当前搜索到的最近邻距离

Heilongjiang University

Sunzhigang,2191313 10 规则：1. 对新样本x，结点pX

若 pprBMxD),(

则x的近邻不可能在pX中

2. 对新样本x，结点p中的样本pixX

若 ),(),(pipMxDBMxD

则ix不是x的最近邻

两大步：

1. 事先把样本子集划分好（比如用聚类算法），

计算并存储pX的pM，pr及),(piMxD

2. 用分支定界算法搜索x的最近邻 Heilongjiang University

Sunzhigang,2191313 11 搜索算法：（最近邻）

1 （初始化）

置0,0,pLB（当前结点）。

2 （当前结点展开）

把当前结点的直接子结点放入（当前水平的）一个目录表（活动表）中，对它们计算并存储),(pMxD。

（注意：活动表在每个水平上一个，下文均指当前水平的活动表）

3 （检验）

对活动表中每个结点，若pprBMxD),(，则从表中去掉。

（规则1） Heilongjiang University

Sunzhigang,2191313 12 4 （回溯）

若活动表中已无结点，则回到上一级，置1LL

如0L，则算法终止；

如0L，则转3；

若活动表中有结点，则继续5。

5 （选择最近结点）

在目录表中选择最近结点（),(pMxD最小），记为p，以它为当前结点，若当前水平L为最终水平，则转6。

否则，置1LL，转2。

Heilongjiang University

Sunzhigang,2191313 13 6 （检验）

对当前结点p中的每个ix，

若BMxDMxDpip),(),(，则非最近邻； （规则2）

否则，计算),(ixxD，

若BxxDi),(，则置iNN，),(ixxDB

p中所有ix被检验过之后，转3。

算法终止时，输出x的最近邻NNx和BxxDNN),(

（K-近邻时只须修正上述算法的第6步）

Heilongjiang University

Sunzhigang,2191313 14 6.1.4 剪辑近邻法

基本理解：

处在两类交界处或分布重合区的样本可能误导近邻法决策。

应将它们从样本集中去掉。

基本思路：

考查样本是否为可能的误导样本，

若是则从样本集中去掉——剪辑。

考查方法是通过试分类，认为错分样本为误导样本。

Heilongjiang University

Sunzhigang,2191313 15 基本做法：

将样本集分为考试集NTX和参考集NRX： NRNTNXXX，NRNTXX

剪辑：用NRX中的样本对NTX中的样本进行近邻法分类

剪掉NTX中被错分的样本，NTX中剩余样本构成剪辑样本集NTEX

分类：利用NTEX和近邻法对未知样本x分类。

思考：

将样本集分为考试集和参考集是为了剪辑的独立性，但既然样本都是独立的，可否考虑下面的做法？（借鉴LOOCV）

即：对NX中每个ix，用所有其他样本对它分类，若分错则剪掉。

Heilongjiang University

Sunzhigang,2191313 16 错误率分析（渐近错误率）

1. 若用最近邻剪辑，用最近邻分类，则错误率

)]|(1[2)|()|(1xePxePxePE

即 )()(1ePePE （P(e|x)、P(e)是近邻法的错误率）

当)(eP很小时，如1.0)(eP，则有)(21)(1ePPeE

而*2)(PeP （*P为贝叶斯错误率）。

故此时)(1ePE接近*P。

Heilongjiang University

Sunzhigang,2191313 17 2. 若用k近邻剪辑，用最近邻分类，则

)|()]|(1[2)|()|(1xePxePxePxePEkEk

当k时)(ePEk收敛于*P（N应更快地趋向）

3. 多类情况，多类剪辑近邻错误率)|(xePEkc小于两类情况

4. 重复剪辑

样本足够多时，可多次重复剪辑，效果更好。

Heilongjiang University

Sunzhigang,2191313 18 一种重复剪辑算法——MULTIEDIT：

（1）(散开) 把NX随机划分为s个子集，xXX,.1，3s

（2）（分类）用)()1(smadiX对iX中的样本分类，si,,1

（3）（剪辑）去掉(2)中错分的样本

（4）（混合）将剩下的样本合在一起，形成新的NX（NEX）

（5）（终止）如果最后k次迭代都没有样本被剪掉，则停止；

否则用新的NX转（1）。

算法停止后，用最后的NEX作为分类的样本集