浩慶波， 高 慧， 萬曙靜

(曲阜師范大學 網(wǎng)絡信息中心， 山東 濟寧 273100)

1 局部支持向量機研究

時下，已有前期文獻成果表明，由Vapnik提出的支持向量機(SVM) 在涉及小樣本、非線性以及高維分類的研究應用方面有著突出的優(yōu)勢[1]，其基本原理是將樣本集中的樣本信息通過核函數(shù)映射到高維空間中并建立分類超平面，根據(jù)分類超平面確定測試樣本的類別。支持向量機使用訓練樣本集中的所有信息(即全局信息)構(gòu)建分類模型，但這種全局化的思想并不能夠體現(xiàn)樣本的局部信息。而局部支持向量機則能夠有效解決此類問題，充分利用樣本的局部信息，滿足算法的一致性要求，且其分類精度要高于支持向量機[2]。

局部支持向量機的本質(zhì)是在支持向量機核函數(shù)上添加2個乘子使之具有局部性，模型定義如下：

(1)

核函數(shù)的定義如下：

(2)

其中，Kwr(xi,xj)=K(xi,xj)h(|xi-wr|)h(|xj-wr|)。w1，w1，…，wt等t個元素可使得|xi-wr|能夠覆蓋訓練集的所有樣本。通過設定θr的取值來定義局部核函數(shù)，并可將其寫作如下數(shù)學形式：

(3)

這種思想是在樣本空間中計算k近鄰，卻難以適應不同分布的數(shù)據(jù)集，即數(shù)據(jù)集不同算法的精度差異將會很大。

接下來，Blanzieri與Melgani則提出了一種新的局部支持向量機(kNNSVM)，測試樣本可以通過以下決策函數(shù)得到類別標號。該函數(shù)的計算公式具體如下：

(4)

kNNSVM使用測試樣本x′的k個近鄰樣本構(gòu)建分類模型，然后使用SVM算法對樣本進行分類。若k的取值與訓練集樣本數(shù)相同，則kNNSVM與SVM算法的分類模型相同。

2 粒子群算法研究

粒子群算法是由Eberhart和Kennedy通過研究鳥群捕食行為研發(fā)提出的一種群體智能優(yōu)化算法[3]。粒子群中的粒子定義為一個N維空間的點xi=(xi1,xi2,xi3...,xin)，N維空間就是要優(yōu)化的解空間，每個粒子都有一個運動速度vi=(vi1,vi2,vi3,...,vin)，粒子在空間內(nèi)搜索飛行。粒子群算法運行時，將初始化一組隨機解，再根據(jù)粒子本身的經(jīng)驗以及群體的當前狀態(tài)更新自身的位置和飛行速度，并借助適應度函數(shù)計算得到其適應度值來評價當前解的優(yōu)劣。粒子群會根據(jù)pbest(個體最優(yōu)解)和gbest(全局最優(yōu)解)2個極值更新下一代粒子的速度和位置，通過不斷地迭代尋找最優(yōu)解。更新下一代粒子速度和位置的數(shù)學公式可見如下：

v[]=v[]+c1*rand()*(pbest[]-present[])+c2*rand()*(gbest[]-

present[])present[]=present[]+v[]

(5)

其中，v[]是粒子的速度；present[]是當前粒子的位置；pbest[]是局部最優(yōu)位置；gbest[]是全局最優(yōu)位置；rand()是介于(0,1)的隨機數(shù)；c1、c2是學習因子，c1表示粒子對自身的認知程度，c2表示粒子對群體的認知程度。

3 基于PSO特征加權(quán)的局部支持向量機

3.1 局部支持向量機設計解析

局部支持向量機在選取測試樣本的k近鄰時，通常采用歐式距離，歐式距離的數(shù)學表述如下所示：

(6)

其中，Xi表示樣本特征向量；n表示樣本的特征個數(shù)；x1i、x2i表示樣本的特征值。

選取k近鄰后，局部支持向量機利用選中的近鄰樣本構(gòu)造分類器。在構(gòu)造分類器時，局部支持向量機將樣本特征權(quán)重設為相同的值，研究推得分類的決策函數(shù)可如式(7)所示：

f(x)=W·X+b

(7)

其中，W，b決定分類超平面的位置，X是訓練集樣本的特征向量。

但在實際問題中，樣本的不同特征在分類過程中的重要程度是不同的。解決的方法是給樣本的每一個特征賦予不同的權(quán)重來體現(xiàn)其在分類過程中的重要程度，將特征權(quán)重作為分類依據(jù)參與局部支持向量機的分類，在計算k近鄰、分類超平面和核函數(shù)時引入特征權(quán)重的信息，在公式(6)的基礎(chǔ)上加入特征的權(quán)重信息，變換后的公式可表示如下：

(8)

在局部支持向量機的決策函數(shù)中加入特征的權(quán)重信息，這樣就能夠減小與分類弱相關(guān)或不相關(guān)的屬性對計算分類超平面的影響，加入特征權(quán)重信息的計算公式為:

f(x)=W·(XA)+b

(9)

其中，A是一個n階的對角矩陣，n為樣本特征的個數(shù)，此時的Aii=?i(1

(10)

核函數(shù)是影響局部支持向量機分類的關(guān)鍵因素[4]。而核函數(shù)是根據(jù)樣本的特征進行計算的，計算過程中核函數(shù)會將樣本的特征權(quán)重設為相同值，這樣就會造成分類精度降低，因此研究中引入了特征加權(quán)的核函數(shù)，即：

kp(xi,xj)=k(xiA,xjA)

(11)

3.2 粒子群算法設計解析

粒子群是利用群體中的粒子信息共享、協(xié)作，從而在問題求解空間尋求最優(yōu)解，獲得最優(yōu)的位置信息。研究中將每個粒子的位置信息歸一化后作為樣本的初始特征權(quán)重，參與局部支持向量機分類器的構(gòu)造，通過粒子群的迭代過程計算出最優(yōu)的特征權(quán)重組合。

粒子群算法中的適應度函數(shù)是根據(jù)問題環(huán)境而設定的。本文提出的算法是以提高分類精度為目的，因此算法的分類精度即是粒子群的適應度值。

粒子群中的粒子是用一個n維向量p來表示，n表示樣本的特征個數(shù)，向量p需經(jīng)過歸一化處理，以便提高分類精度。本文中，粒子位置的取值范圍為[0，3]，若超過上限則取3，超過下限則取0。

3.3 基于PSO特征加權(quán)的局部支持向量機算法研發(fā)描述

至此，研究得到的基于PSO特征加權(quán)的局部支持向量機算法的設計流程如圖1所示。該算法的總體實現(xiàn)步驟可分述如下。

(1) 對粒子群中的每個粒子的原始位置和運動速度進行初始化。

(2) 將每個粒子的位置信息進行備份，并將備份的粒子位置信息在歸一化處理后作為分類的權(quán)重。使用局部支持向量機對樣本(包含權(quán)重等信息)進行分類。

(3) 將分類精度作為粒子適應度值求得pbest、gbest的值。

(4) 計算并更新粒子群中粒子的速度。

(5) 在原有的位置信息基礎(chǔ)上更新粒子的位置。

(6) 判斷算法是否滿足結(jié)束條件(迭代次數(shù)≥N)，若滿足則輸出分類精度。否則繼續(xù)執(zhí)行步驟(2)。

圖1 基于PSO特征加權(quán)的局部支持向量機

Fig.1LocalSupportVectorMachinesbasedonPSOfeatureweighting

4 實驗結(jié)果及分析

為驗證算法的有效性，本文選取了國際標準UCI數(shù)據(jù)集進行測試。隨機選取數(shù)據(jù)集中部分數(shù)據(jù)作為測試集，剩余數(shù)據(jù)作為訓練集，詳見表1。

實驗將基于PSO特征加權(quán)的局部支持向量機(PSOkNNSVM)、支持向量機(SVM)和局部支持向量機(kNNSVM)3種算法用于相同的數(shù)據(jù)集進行測試。測試采用RBF核函數(shù)，相關(guān)參數(shù)見表2，測試結(jié)果見表3，將結(jié)果繪制成折線圖，最終結(jié)果如圖2所示。

表1 UCI測試數(shù)據(jù)集

表2 參數(shù)設置

表3 測試結(jié)果

圖2 分類精度折線圖

由表3和圖2的實驗結(jié)果可以看出，SVM在分類精度上小于kNNSVM和PSOkNNSVM。由圖2分析可知，在大部分的數(shù)據(jù)集上，PSOkNNSVM的分類精度要高于kNNSVM。需要指出，在wine數(shù)據(jù)集上PSOkNNSVM與kNNSVM的分類精度是相同的，究其原因在于wine數(shù)據(jù)集中樣本的每個特征與分類相關(guān)程度基本相同，利用粒子群進行優(yōu)化時最終得到的特征權(quán)重也是相同的，與kNNSVM相比特征權(quán)重沒有變化，故而其分類精度并未獲得提升。從其它7個數(shù)據(jù)集中可以推出在分類精度上，kNNSVM的分類精度要優(yōu)于SVM，而本文提出的PSOkNNSVM分類精度則要高于kNNSVM和SVM。

5 結(jié)束語

本文提出了一種PSOkNNSVM分類算法。經(jīng)過UCI數(shù)據(jù)集測試，結(jié)果表明該算法在分類過程中能夠較好地確定樣本點中每個特征的權(quán)重，該算法在分類精度上要優(yōu)于局部支持向量機和支持向量機算法。