一種基于PSO特征加權的局部支持向量機

浩慶波， 高 慧， 萬曙靜

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

1 局部支持向量機研究

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

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

(1)

核函數的定義如下：

(2)

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

(3)

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

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

(4)

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

2 粒子群算法研究

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

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

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

(5)

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

3 基于PSO特征加權的局部支持向量機

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

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

(6)

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

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

f(x)=W·X+b

(7)

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

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

(8)

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

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

(9)

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

(10)

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

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

(11)

3.2 粒子群算法設計解析

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

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

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

3.3 基于PSO特征加權的局部支持向量機算法研發描述

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

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

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

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

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

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

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

圖1 基于PSO特征加權的局部支持向量機

Fig.1LocalSupportVectorMachinesbasedonPSOfeatureweighting

4 實驗結果及分析

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

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

表1 UCI測試數據集

表2 參數設置

表3 測試結果

圖2 分類精度折線圖

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

5 結束語

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