定义1^[41] 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

属性集合

C={a₁, a₂, …, a_m},

对于∀ x∈ U, y∈ U, 在条件属性集合C下, 不同样本间的闵可夫斯基距离定义如下:

Δ (x, y)=[ ∑i=1n|f(x, a_i)-f(y, a_i)|^P] 1P,

其中, ∀ a_i∈ C, f(x, a_i)表示样本x在条件属性a_i上的取值.距离的度量常采用欧氏距离函数, 即P=2.

定义2^[33] 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

对于∀ x∈ U, 样本x对应的邻域

δ (x)={y∈ U|Δ (x, y)≤ δ },

其中δ 表示邻域半径.

在构建邻域分类器模型过程中, 为了将NRS进一步适用于分类任务, Hu等^[33]定义δ 作为邻域半径, 通过邻域决策完成样本分类.

定义3^[33] 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

对于测试样本x∈ U, 样本x的邻域半径为

δ =min(Δ (x, y_i))+ω (max(Δ (x, yi₎)-min(Δ (x, yi₎)).

其中:ω ∈ (0, 1], 表示一个随机参数; min(Δ (x, y_i))表示距离x最短的训练样本y_i与x之间的距离; max(Δ (x, y_i))表示距离x最长的训练样本y_i与x之间的距离.

邻域半径δ 决定邻域分类器分类性能优劣.然而, 传统邻域分类器在构建δ 时采用带有人工参数ω 的动态调节方式, 具有一定程度上的不确定性和主观性.随着δ 逐渐增大, 邻域δ (x)也越大, 即落到x的邻域空间中的样本越多.如图1所示, 在邻域分类器中存在3个不同的邻域半径, 相应存在3个不同大小的邻域, 分别使用实线、虚线和点线表示.因此在邻域分类器中, 邻域半径设定偏大或偏小时都会直接影响测试样本标签的预测.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 邻域决策图示例Fig.1 Example of neighborhood decision

定义4^[31] 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

对于测试样本x∈ U, 利用邻域δ (x)得出x属于每种决策类D_j的邻域粗糙隶属度, 邻域粗糙隶属函数为

P(d_j|δ (x))= |Dj⋂δ(x)||δ(x)|,

其中, D_j∈ U/IND(D), 表示论域U根据决策属性D划分并诱导生成的决策类.

以定义4中的邻域粗糙隶属度为依据, 邻域分类器进一步通过多数投票原则, 为测试集中的样本完成最终的邻域决策:当决策类D_j对应的决策标签d_j满足

d_j=arg maxdk∈DP(D_k|δ (x))

时, 测试样本x的标签被预测为d_j.

如图1所示, 邻域分类器中δ ₁> δ ₂> δ ₃.当邻域半径为δ ₃时, 根据多数投票规则测试样本将被预测为黑色标签; 当邻域半径增加到δ ₂时, 测试样本将被预测为邻域粗糙隶属度最大的灰色标签; 当邻域半径继续增加到δ ₁时, 测试样本会被标注为白色标签.由此可见, 邻域半径的构建会直接干扰邻域分类器对测试样本的邻域决策.因此, 邻域半径作为决定预测样本标签过程的关键因素还需要进一步优化.

KNN分类算法是模式识别中简单有效的经典算法之一, 基本原理如下:给定一组已知类别的训练样本和待分类样本, 找到训练样本中距离待分类样本最近的K个最近邻居, 进而将K个近邻中最多个数的标签分配给待分类样本.

对于待分类样本x^te∈ U^Te, KNN的分类过程如下.首先, 为待分类样本x^te定义一组超过K个相似的目标邻居, 即按照x^te与训练样本之间的欧氏距离递增排序, 取排名前K个训练样本.再利用多数投票原则, 根据K个最近邻居的标签, 预测得出待分类样本x^te的标签.重复上述步骤, 直到所有待分类样本预测结束.

已有的邻域分类器模型仅涉及测试阶段, 对于已知标签的训练样本, 不需要计算邻域半径, 也未构建邻域进行邻域决策, 只考虑其与待测样本之间的距离作为待测试样本邻域决策的依据.为了进一步利用训练样本的有效信息, NNC-AR结合KNN, 为训练样本定义训练邻域半径, 增添邻域半径的训练阶段, 为提升待测试样本的预测精度提供有效根据.

训练邻域半径的构建过程如下:结合KNN, 对每个已知标签的训练样本x^tr, 选取距离x^tr最近的K个样本, 进而根据这K个样本的标签值, 基于多数表决原则预测得到x^tr的标签, 依次取K=1, 2, …, 10直至x^tr被预测正确.最后得到x^tr被预测成功时的值, 选取距离x^tr排名的第K个近邻点与x^tr之间的距离, 作为训练样本x^tr的邻域半径, 即训练邻域半径.

如图2所示, 当K=4时, 训练样本x^tr的标签能被正确预测为白色, 继而将距离x^tr排名的第4个近邻点与x^tr之间的距离作为x^tr的训练邻域半径.

图2

Fig.2

	Figure Option ViewDownloadNew Window
	图2 训练邻域半径构建图Fig.2 Training neighborhood radius construction

定义5 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

其中

U=U^Tr∪ U^Te.

对于训练样本x^tr∈ U^Tr, 训练邻域半径为:

δ ^tr=Δ (x^tr, NN_k(x^tr)),

其中, NN_k(x^tr)表示与当前训练样本x^tr距离排名第K个的近邻点, 也是使x^tr能被正确分类的最近邻, K=1, 2, …, 10.另外若依次取K=1, 2, …, 10, 训练样本x^tr都无法被分类, 即只有K> 10时, 训练样本x^tr才能被正确预测为已知标签, 这表明训练样本x^tr显然偏离其它同类训练样本的正常分布范围, 因此将样本x^tr归为噪声点并删除, 不参与NNC-AR本轮训练阶段和测试阶段的构建.

NNC-AR通过KNN计算已知标签的训练样本能被正确预测时的训练邻域半径, 为邻域半径的构建增添训练阶段, 充分挖掘训练样本条件属性与决策属性之间的有效关联性信息, 有利于构建预测精度较高、分类性能较强的NNC-AR.

在已有分类器模型的预测阶段中, 动态调节人工参数以构建待测样本的邻域半径, 具有一定程度上的主观性和不确定性.因此, 在NNC-AR的测试阶段, 考虑待测试样本与训练样本之间的相似性以解决待测试样本标签的预测问题.基于近邻思想, 选取距离待测试样本最近的训练样本, 并以训练邻域半径为根据, 为待测试样本构建新的近邻邻域半径, 有效克服传统邻域半径中的动态调节方式带来的不确定性问题.

近邻邻域半径的构建过程如下:结合训练邻域半径和近邻思想, 根据定义5得到每个训练样本被预测成功的邻域半径δ ^tr.进而求取距离待测试样本x^te最近的训练样本, 将其对应的训练邻域半径作为该待测样本x^te的邻域半径, 即近邻邻域半径.

如图3所示, 先计算距离待测试样本x^te最近的训练样本 xmintr, 再基于定义5得到 xmintr的训练邻域半径 δmintr, 最后将 δmintr值作为x^te的近邻邻域半径δ ^te.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 近邻邻域半径构建图Fig.3 Near neighborhood radius construction

定义6 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

其中

U=U^Tr∪ U^Te.

对于测试样本x^te∈ U^Te, 近邻邻域半径δ ^te= δmintr.其中:

δmintr=Δ ( xmintr, NN_k( xmintr)),

表示 xmintr对应的训练邻域半径;

xmintr=arg minxtr∈UTrΔ (x^te, x^tr),

表示与当前测试样本x^te距离最近的训练样本.

由于训练邻域半径的构建是基于已知标签的训练样本能被正确预测, NNC-AR将其进一步融入测试阶段.结合近邻思想选取距离待测试样本最近的训练样本构建近邻邻域半径, 不仅考虑测试样本与训练样本之间的关联性, 还能极大程度以训练阶段的有效信息为根据准确预测待测试样本的标签, 克服以往邻域分类器模型选取邻域半径参数时的不确定性问题, 一定程度上提升邻域半径的合理性和自适应性, 有效提升NNC-AR的分类性能.

在待测试样本的标签预测阶段中, 通过近邻邻域半径构建邻域能完成大多数测试样本标签的正确预测.然而, 对于少数分布不均匀的待测试样本, 采用近邻邻域半径构造的邻域可能会出现无样本的情况, 导致分类器失效而无法预测样本标签.为了进一步提升分类器模型的泛化能力, NNC-AR结合近邻思想, 为少数分类器失效的待测试样本构建新的近似邻域半径, 解决部分样本邻域中无样本的情况.

近似邻域半径的构建过程如下:根据定义6先求取待测试样本x^te的近邻邻域半径, 用于划分x^te的邻域.若发现邻域内没有样本, 表示分类器失效, 进而将距离x^te最近的训练样本与x^te之间的距离作为x^te的邻域半径, 即近似邻域半径.

如图4所示, xmintr表示距离待测试样本x^te最近的训练样本, 利用 xmintr的训练邻域半径 δmintr构建x^te的近邻邻域半径δ ^tr, 构建后发现x^te的邻域无样本, 即分类器失效.进而求取x^te的近似邻域半径.如图5所示, 将离x^te最近的训练样本 xmintr与x^te之间的距离Δ (x^te, xmintr)作为x^te的近似邻域半径δ ^sim, 划分得到x^te的邻域.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 分类器失效图Fig.4 Classifier failure

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 近似邻域半径构建图Fig.5 Approximate neighborhood radius construction

定义7 给定一个决策信息系统

S=< U, C∪ D, V, f > ,

其中

U=U^Tr∪ U^Te.

对于测试样本x^te∈ U^Te, 近似邻域半径为:

δ ^sim=Δ (x^te, xmintr),

其中

xmintr=arg minxtr∈UTrΔ (x^te, x^tr),

表示与当前测试样本距离最近的训练样本.

综上所述, NNC-AR结合近邻思想, 对于少数分布不均匀、出现空邻域的待测试样本, 利用其与距离最近的训练样本构建近似邻域半径, 完成对标签信息的有效预测, 有效解决测试阶段中的分类器失效问题, 提升NNC-AR的泛化性能.

最终, 得到NNC-AR步骤如算法1所示.

算法1 NNC-AR

输入 决策信息系统< U^Tr∪ U^Te, C∪ D, V, f > ,

待测试样本x^te∈ U^Te

输出 输出测试样本x^te的标签d_j

#计算所有训练样本的半径及删除噪点样本

for x^tr∈ U^Tr:

计算δ ^tr=Δ (x^tr, NN_k(x^tr));

if i> 10 then:

从U^Tr剔除样本x^tr;

end if

end for

#计算测试样本的半径并对测试样本预测

计算δ ^te= δmintr;

计算d_j=arg maxdk∈DP(D_k|δ (x^te)),

δ (x^te)={x^tr∈ U^Tr|Δ (x^te, x^tr)≤ δ ^te};

if d_j=Ø then:

计算δ ^sim=Δ (x^te, xmintr);

计算d_j=arg maxdk∈DP(D_k|δ (x^te)),

δ (x^te)={x^tr∈ U^Tr|Δ (x^te, x^tr)≤ δ ^sim};

end if

return d_j

为了清晰分析NNC-AR的时间复杂度, 假设训练集中样本个数为n₁, 删除噪声点样本后的样本总数为n₂.因此, 算法第1阶段主要计算所有训练样本的半径并删除噪声点样本点, 时间复杂度为O( n12).在第2阶段, 对于单个测试样本, 时间复杂度为O(n₂).因此NNC-AR的时间复杂度为O( n12+n₂).

NNC-AR的流程图如图6所示.

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 NNC-AR流程图Fig.6 Flowchart of NNC-AR