基于優(yōu)化GDTW-SVM算法的聯(lián)機(jī)手寫識(shí)別
加入技術(shù)交流群
2 GDTW-SVM算法
2．1 支持向量機(jī)
假設(shè)線性分類器對(duì)輸入的特征向量x={x1，x2，…xn}(n是樣本數(shù)目)，輸出Y={y1，y2，…，yn}其中，xi，I RN，N是特征向量的維數(shù)：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以最小化結(jié)構(gòu)風(fēng)險(xiǎn)為目標(biāo)，計(jì)算使得訓(xùn)練樣本集到分類超平面的距離最大化的最優(yōu)分類超平面。其等價(jià)于對(duì)式(2)求解凸二次規(guī)劃問(wèn)題。
式(4)中ai是拉格朗日乘子，靠近超平面的點(diǎn)對(duì)應(yīng)的ai非零，其它所有點(diǎn)對(duì)應(yīng)的ai為零。因此，最優(yōu)分類決策的對(duì)偶表示
只包含ai非零的點(diǎn)。這些點(diǎn)稱為支持向量(Support Vector，SV)，支持向量決定了最優(yōu)分類超平面，且其數(shù)目越多，分類判決的計(jì)算時(shí)間越長(zhǎng)。
對(duì)于非線性可分樣本，SVM使用滿足Mercer定理的核函數(shù)K(x，z)，代替式(5)中的內(nèi)積計(jì)算，將輸入的特征向量映射到高維線性可分的特征空間。Merce定理保證了核函數(shù)的正定對(duì)稱性和式(4)最優(yōu)化問(wèn)題求解過(guò)程的收斂性。一個(gè)比較常用的核函數(shù)是高斯核函數(shù)(GRBF)
KGRBF(X，Z)=exp(-y·‖X-Z‖p)，p=1，2，… (6)
2．2 GDTW核函數(shù)
假設(shè)T=(t1，…，tNT)和R=(r1，…，rNR)
是長(zhǎng)度分別為NT和NR的特征向量序列。對(duì)齊路徑f=(f(1)，…，f(L))是對(duì)齊序列T和R的索引序列，其中，L是路徑長(zhǎng)度，
即尋找使平均距離最小的最優(yōu)對(duì)齊路徑。DTW距離越小，T和R所代表的樣本越相似?？梢允褂脛?dòng)態(tài)規(guī)劃(Dynamic Programming)算法計(jì)算最優(yōu)對(duì)齊路徑和DTW距離。
圖1給出了最優(yōu)對(duì)齊路徑和DTW距離的示例，其中，上半部分是字符樣本的繪圖，順次是“oocae”；下半部分是各個(gè)字符樣本與第一個(gè)字符樣本的最優(yōu)對(duì)齊路徑和DTW距離。本文引用地址：http://butianyuan.cn/article/193871.htm
Bahlmann等人使用DTW距離代替高斯核函數(shù)(6)中的歐幾里德距離‖X-Z‖p的計(jì)算(取p=2)，構(gòu)造了GDTW核函數(shù)
KGRBF(X，Z)=exp(-y·DTW(X，Z)) (8)
他們的聯(lián)機(jī)手寫識(shí)別實(shí)驗(yàn)的結(jié)果和Bothe等人的實(shí)驗(yàn)結(jié)果表明，GDTW-SVM取得了比GDTW-SVM和k近鄰算法(k-Nearest Neighbor，kNN)更高的識(shí)別率，而且在不同聯(lián)機(jī)手寫識(shí)別數(shù)據(jù)庫(kù)子集的識(shí)別實(shí)驗(yàn)中，與基于其它彈性距離計(jì)算的核函數(shù)的SVM相比，各有優(yōu)劣且識(shí)別率的差值在0．3％以內(nèi)。
評(píng)論