Page 167 - 201903
P. 167
第 38 卷 第 3 期 严良涛等： 基于核的 k-最近邻在水下目标识别中的应用 449
应将多种特征加以组合，但这会造成数据维数过高， 假定将 x 和 y 映射至高维特征空间中，那么此
识别速率下降。为此，本文提出了基于核 (Kernel) 时高维空间特征样本 ψ (x) 和 ψ (y) 之间的距离二
的 k 近邻 [6] (k-nearest neighbor, k-NN) 水下目标 范数为
识别方法。该方法利用主成分分析 [7] (Principal 2 2
d (ψ (x) , ψ (y)) = ∥ψ (x) − ψ (y)∥
components analysis, PCA) 对高维的特征矩阵进
= ⟨(ψ (x) − ψ (y)) , (ψ (x) − ψ (y))⟩ . (4)
行降维，解决目标识别速率低的问题；利用 Kernel
技巧将降维后的非线性特征映射到高维空间并在 式(4)中存在内积项⟨(ψ(x)−ψ(y)), (ψ(x)−ψ(y))⟩，
该空间进行 k-NN 分类识别，能够有效减小非线性 根据 1.1 节可知，利用 Kernel 可实现对该内积的直
特征在低维度空间距离度量误差，提高识别正确率。 接计算。此时：
实际实验数据的验证结果表明：与k-NN 相比，基于 d (ψ (x) , ψ (y))
2
核的 k-NN 的目标识别速率略低，但目标的识别正
= K (x, x) − 2K (x, y) + K (y, y) . (5)
确率得到较大提高；与BP 神经网络分类器相比，基
由式 (5) 可知，高维特征空间样本 ψ (x) 和 ψ (y) 之
于核的 k-NN 的目标识别正确率略低，但目标的识
间的距离可通过 Kernel 在原始空间中直接计算，而
别速率得到较大提高。
不受维度和映射ψ 的限制。
1 基于核的k-NN基本原理 1.3 基于核的k-NN的算法实现
基于核的 k-NN 的实现过程如下：给定一个用
1.1 空间映射及核函数
于训练的特征数据集，将其映射到高维特征空间，对
给定特征样本 x，将其从 n 维特征空间映射到
新的输入实例，利用 Kernel计算其在高维特征空间
m维特征空间：
中最邻近的 k 个实例，若这 k 个实例的大多数属于
特征映射ψ
x = (x 1 , · · · , x n ) −−−−−−→ ψ(x) 某个类，就把该新实例划分为这个类。本文选择高
= (φ 1 (x) , · · · , φ m (x)) , 斯核函数进行运算，具体过程如表1所示。
x ∈ S 1 , ψ (x) ∈ S 2 , (1)
表 1 基于核的 k-NN 的算法实现过程
其中，S 1 为原始 n 维特征空间，S 2 为 m 维映射特征 Table 1 The algorithm of k-NN based on
空间。x 为 S 1 中的特征样本，ψ (x) 为对应 S 2 中的 Kernel
特征样本。ψ 为将S 1 映射到S 2 的非线性映射，φ i 为 输入 (1) 训 练 数 据 集 X = {(x 1 , y 1 ), (x 2 , y 2 ), · · · ,
特征映射函数，i = 1, · · · , m。 (x m, y m)}，x i ∈ S 1 ⊆ R 为实例的特征向量，y i ∈
n
F = {c 1 , c 2 , · · · , c α} 为实例的类别，i = 1, 2, · · · , m；
对x, y ∈ S 1 ，其核函数(Kernel)表示形式为
(2) 待分类实例特征向量 x。
T
K (x, y) = ⟨ψ (x) , ψ (y)⟩ = (ψ (x)) ψ (y) , (2) 过程 (1) 选定 Kernel 及其参数 C； (2) 选定合适的 k 值；
(3) 根据
式 (2) 中，⟨ψ (x) , ψ (y)⟩ 表示 ψ (x) 和 ψ (y) 的内积， d(ψ(x), ψ(x i ))= √ K(x, x)−2K(x, x i )+K(x i , x i )
K (x, y) 为 x 和 y 的函数。通过核函数 K (x, y) 直 找出在训练集中与 x 最邻近的 k 个点，涵盖这 k 个点的
x 的邻域记为 N k (x)；
接计算高维特征空间的内积 ⟨ψ (x) , ψ (y)⟩，使其计
(4) 在 N k (x) 中根据多数表决原则决出 x 的类别 y：
算复杂度不受维度和映射ψ 的影响。常用的 Kernel y =arg max ∑ I(y i =c i ),
p
有多项式核函数 K (x, y) = (x · y + 1) 、高斯核函 c j x i ∈N k (x)
i=1, 2, · · · , m; j =1, 2, · · · , α,
2
数K (x, y) = exp(− ∥x − y∥ /C)等。
其中，I 为指示函数，当 y i = c i 时 I 为 1，否则 I 为 0。
1.2 k-NN的核化 输出 实例特征向量 x 的类别 y。
在 k-NN 中，原始空间特征样本 x 和 y 之间的
在上述实现过程中选择的高斯核函数灵活度
距离二范数为
高，不同的核参数 C 可以将原始空间映射到任意维
2
2
d (x, y) = ∥x − y∥ . (3)
空间。在对核参数C 的优化过程中，C 值过大，高次
