6-第四章 1 最近邻法.doc

6-第四章_1 最近邻法§1 最小距离分类器
1] 单中心点情况
决策函数:是x的线性函数。
分界面:
2] 多中心点情况
:个中心,
到的距离
3] 最近邻分类器(NNC)
非参数分类器
【结论】当样本数趋近于无穷大的时候,X的最近邻将无限趋近于X,即:,有:
证明:当时,X的最近邻落在以X为中心的球Ps内的概率为:
一个样本在球Ps外的概率为:
N个独立样本在球Ps外的概率为:
当N时,则
则结论成立。
NCC错误率
其中:为最小错误率Bayes分类器的平均错误率;
P为最近邻分类器的平均错误率;
M为类别数。
证明:(1) Bayes分类器的平均错误率:
对于单个样本X,若P(ωb |X)=max P(ωi |X) i=1,2,…,m 则xωb
则:P*(e |X)=1- P(ωb|X)
P*=
最近邻分类器的平均错误率:

最近邻分类器的平均错误率一定大于Bayes分类器的平均错误率,但有相等的时候。即:PP*
“=”” [A最容易的情况]
当P(ωb |x)=1 P(ωi |x)=0 i≠b
Bayes P*=
NNC P=
[B最难的情况]
当P(ωi |x)=
Bayes P*=
NNC P=
最容易和最困难的情况,用Bayes分类器和NNC分类器具有相同的结果。
证明
即:
约束条件
当时
得到:
4] K近邻法(KNNC,qNNC)
K个最近邻,K个近邻中距哪一类样本多,就把X分到哪一类
5]最近邻点的改进
缺点:存贮量大,计算量大
剪辑(Editing)
(1)
(2) 以中样本为标准,对中样本进行测试,得到。
(3) 以为样本做NNC
好处:(1)
(2)
2. 凝聚(Condensing)