訓(xùn)練支持向量機的二次規(guī)劃問題研究

訓(xùn)練支持向量機的二次規(guī)劃問題研究

目前，svm支持向量機（svm）基于最小結(jié)構(gòu)風(fēng)險原則，將最大界面分類器的概念與基于核心的方法相結(jié)合，表現(xiàn)出良好的泛化能力，已成為機械學(xué)習(xí)領(lǐng)域的研究熱點。給定訓(xùn)練樣本{x此時分類間隔為2/w,因此使間隔最大等價于使‖w‖利用Lagrange優(yōu)化方法可以把上述最優(yōu)分類面問題轉(zhuǎn)化為其對偶問題,即求解如下的QP問題:α若令α={α由于矩陣Q是非負(fù)定的,所以QP問題是一個凸最優(yōu)化問題,則SVM的解是唯一的,也是全局最優(yōu)的。同時KuhnTucker條件對于凸規(guī)劃問題存在唯一的最優(yōu)點,所以K-T點一定是最優(yōu)點,即:有對偶問題的任一解αf(x2合作與競爭搜索全局最優(yōu)值粒子群優(yōu)化算法(PSO)是一種進化計算技術(shù),是一種基于迭代的優(yōu)化工具。該算法通過群體之間的合作與競爭來搜索全局最優(yōu)點。系統(tǒng)初始化為一組隨機解,通過迭代搜尋整個群體的最優(yōu)值。每個粒子I的當(dāng)前位置為x另一個極值是整個種群目前找到的最優(yōu)解gbest。每個粒子是按以下兩個公式進行動態(tài)進化,調(diào)整粒子的位置:這里w是慣性權(quán)重,動態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度。c3qpso算法Sun等人從量子力學(xué)的角度,通過對粒子收斂行為的研究,基于粒子群算法(PSO),提出了一種新的算法模型———量子粒子群算法(QPSO)QPSO算法參數(shù)個數(shù)少,進化方程的形式更加簡單,更容易控制。在QPSO算法中,每一個粒子必須收斂于各自的隨機點p這里mbest是粒子群pbest的中間位置,P具體a取值視情況而定,其中MAXTIME是迭代的最大次數(shù)。QPSO的算法流程為:1)迭代次數(shù)t=0,對種群的每個粒子的位置向量進行初始化;2)根據(jù)目標(biāo)函數(shù)計算每個粒子的目標(biāo)函數(shù)值;3)更新每個粒子的新局部最優(yōu)位置P4)更新全局最優(yōu)位置P5)根據(jù)公式(10)計算mbest;6)根據(jù)公式(11)計算每個粒子隨機點PP7)根據(jù)公式(12)(以一定的概率取加和減)更新每個粒子的新位置;8)令t=t+1,返回到第2)步,重新計算,直到終止條件滿足。4svm的最優(yōu)設(shè)計—QPSO訓(xùn)練SVM從上述算法中,可以看到在普通的PSO算法中粒子是通過向pbest和gbest靠近來實現(xiàn)尋優(yōu)的,因此對于一些最優(yōu)點遠(yuǎn)離pbest和gbest的問題,用普通的PSO算法就難以找到最優(yōu)解。而QPSO算法是一種不確定搜索算法,能更大可能地搜索到最優(yōu)點不在pbest和gbest附近的最優(yōu)點,具有較好的全局收斂性,所以QPSO算法訓(xùn)練支持向量機的結(jié)果會更優(yōu)越。工作集的選擇策略,最優(yōu)性Kuhn-Tucker條件,用QPSO算法優(yōu)化SVM子問題構(gòu)成了實現(xiàn)支持向量分類的主體框架。SVM訓(xùn)練算法最核心,最主要的問題是求解二次規(guī)劃問題。優(yōu)化二次規(guī)劃問題的Lagrange乘子要使得所有樣本都滿足如下Kuhn-Tucker條件,SVM的解是唯一的,也是全局最優(yōu)的。將QP問題分解為若干個規(guī)模一定的子QP問題,用QPSO優(yōu)化SVM子問題。分解QP問題即選擇一個工作集,作為優(yōu)化的對象。從L個訓(xùn)練樣本點中選擇q(q<l)個樣本點所對應(yīng)的Lagrange乘子α1)當(dāng)存在樣本點在精度范圍內(nèi)不滿足Kuhn-Tucker條件時:a)選擇q個Lagrange乘子作為工作集αb)用QPSO算法求解問題式(2)～式(4),得解αc)返回α2)由近似最優(yōu)解α工作集的選取策略是基于ZOUTENDIJK可行方向法,即為目標(biāo)函數(shù)式(2)選擇一個下降速度最快的方向d得到本次迭代所需的q個Lagrange乘子,即求解一個如下問題:其中g(shù)(aα分成兩部分:工作集和非工作集,對應(yīng)的下標(biāo)分別為B和N。H陣是對稱的,H在可行域里初始化所有樣本點,使所有的樣本點對應(yīng)的Lagrange乘子滿足約束表達(dá)式(3)～(4)。為了滿足約束條件,初始化時可采用如下方法:在[0,C]范圍內(nèi)隨機選取一個數(shù)值c,隨機選取一定數(shù)量的支持向量,從訓(xùn)練集中選擇正負(fù)樣本點各γ(γ自定義,但比訓(xùn)練樣本數(shù)小得多)個,使2γ個樣本點所對應(yīng)的Lagrange乘子的值c,其余的樣本點所對應(yīng)的Lagrange乘子均為0,則初始時定義了2γ個支持向量,該支持向量為隨機選取。用分解算法選擇出工作集和非工作集,對工作集在可行域里用QPSO算法對QP問題求解最優(yōu)值。粒子數(shù)一般選擇在20和40之間,使所有的粒子初始化時都滿足α1)初始化粒子群,對每個粒子初始化一個滿足約束條件α2)計算粒子的目標(biāo)函數(shù)值;3)更新每個粒子α4)更新α5)根據(jù)公式(10)計算mbest;6)根據(jù)公式(11)計算每個粒子隨機點PP7)公式(12)更新每個粒子的α8)返回第2)步,直到滿足迭代的次數(shù)。5qpso算法求解qp問題本實驗采用了檢驗分類算法性能的標(biāo)準(zhǔn)數(shù)據(jù)集尾屬植物數(shù)據(jù)集(Irisdataset)。該數(shù)據(jù)集共150個樣本點,分為3類,每類樣本集各50個樣本點.每個樣本有4個特征值。用Iris數(shù)據(jù)集訓(xùn)練支持向量機,按花瓣長度把樣本分為2類,花瓣長度在之間樣本點的作為正樣本其余的樣本點作為負(fù)樣本,每個訓(xùn)練樣本點為4維的向量。圖1給出了QPSO算法對Iris數(shù)據(jù)集的花辨長度和花辨寬度兩個屬性進行分類的情況,核函數(shù)為多項式核函數(shù)。由此可看出QPSO算法求解QP問題可對支持向量進行很好的分類。實驗中,分別采用PSO算法和QPSO算法優(yōu)化訓(xùn)練樣本集的二次規(guī)劃問題。隨機選取20個初始化支持向量,懲罰參數(shù)C統(tǒng)一設(shè)為100。訓(xùn)練采用徑向基核函數(shù)由前面敘述中知道,QPSO算法最大可能的搜索不在pbest和gbest附近的最優(yōu)點,尋求全局最優(yōu)解。圖2給出PSO算法和QPSO算法在工作集B上求解QP問題W(α從PSO算法和QPSO算法比較中可以看到,QPSO算法參數(shù)設(shè)置簡單,操作容易,在訓(xùn)練SVM應(yīng)用中有很好的效果。在實驗中也觀察到,核函數(shù)的選取和懲罰參數(shù)C的選擇同樣對實驗結(jié)果有重要的影響SVM已廣泛應(yīng)用于文本識別、人臉檢測、三維圖像檢測、生物信息學(xué)等多個方面,但應(yīng)用研究還較少。訓(xùn)練支持向量機的實質(zhì)是求解二次規(guī)劃(QuadraticProgramming,QP)問題,但在實際問題中,訓(xùn)練樣本規(guī)模較大,給求解QP問題帶來了很大的困難,甚至不能解決。近年來,很多研究者將進化算法用于優(yōu)化二次規(guī)劃問題,以期加深和擴大SVM應(yīng)用領(lǐng)域的研究。量子粒子群優(yōu)化(QPSO)算法,是在原始的粒子群優(yōu)化算法(PSO)基礎(chǔ)上提出的一種新型的具有高效率全局搜索能力的進化算法。QPSO算法調(diào)整參數(shù)少,容易實現(xiàn),收斂能力強,實現(xiàn)時間短。本文將QPSO算法應(yīng)用于訓(xùn)練支持向量機,解決二次規(guī)劃問題。實驗證明,QPSO的性能優(yōu)于傳統(tǒng)的PSO算法。1尋求個滿足要求的分割平面支持向量機主要解決的是一個二分類問題,該理論最初來源于數(shù)據(jù)分類問題的處理,SV