电子产品世界

2 GDTW-SVM算法
2．1 支持向量机
假设线性分类器对输入的特征向量x={x1，x2，…xn}(n是样本数目)，输出Y={y1，y2，…，yn}其中，xi，I RN，N是特征向量的维数：yi∈{-1，1}， yi=-1表示样本(xi，yi)属于第一类，yi=1表示样本(xi，yi)属于另一类。该线性分类器的分类决策为
y(w·x>+b)≥1 (2)
式(2)中(w,b)确定分类超平面w·x>+b=0。
SVM以最小化结构风险为目标，计算使得训练样本集到分类超平面的距离最大化的最优分类超平面。其等价于对式(2)求解凸二次规划问题。

式(4)中ai是拉格朗日乘子，靠近超平面的点对应的ai非零，其它所有点对应的ai为零。因此，最优分类决策的对偶表示

只包含ai非零的点。这些点称为支持向量(Support Vector，SV)，支持向量决定了最优分类超平面，且其数目越多，分类判决的计算时间越长。
对于非线性可分样本，SVM使用满足Mercer定理的核函数K(x，z)，代替式(5)中的内积计算，将输入的特征向量映射到高维线性可分的特征空间。Merce定理保证了核函数的正定对称性和式(4)最优化问题求解过程的收敛性。一个比较常用的核函数是高斯核函数(GRBF)
KGRBF(X，Z)=exp(-y·‖X-Z‖p)，p=1，2，… (6)
2．2 GDTW核函数
假设T=(t1，…，tNT)和R=(r1，…，rNR)是长度分别为NT和NR的特征向量序列。对齐路径f=(f(1)，…，f(L))是对齐序列T和R的索引序列，其中，L是路径长度，

即寻找使平均距离最小的最优对齐路径。DTW距离越小，T和R所代表的样本越相似。可以使用动态规划(Dynamic Programming)算法计算最优对齐路径和DTW距离。
图1给出了最优对齐路径和DTW距离的示例，其中，上半部分是字符样本的绘图，顺次是“oocae”；下半部分是各个字符样本与第一个字符样本的最优对齐路径和DTW距离。

Bahlmann等人使用DTW距离代替高斯核函数(6)中的欧几里德距离‖X-Z‖p的计算(取p=2)，构造了GDTW核函数
KGRBF(X，Z)=exp(-y·DTW(X，Z)) (8)
他们的联机手写识别实验的结果和Bothe等人的实验结果表明，GDTW-SVM取得了比GDTW-SVM和k近邻算法(k-Nearest Neighbor，kNN)更高的识别率，而且在不同联机手写识别数据库子集的识别实验中，与基于其它弹性距离计算的核函数的SVM相比，各有优劣且识别率的差值在0．3％以内。

1 2 3 4

关键词： GDTW-SVM 算法 联机 识别