基于近鄰傳輸?shù)牧６萐VM算法*

程鳳偉，王文劍

1.太原學(xué)院 計(jì)算機(jī)工程系，太原030032

2.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006

3.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原030006

1 引言

支持向量機(jī)（support vector machine，SVM）是Vapnik等人提出的一類通用有效的學(xué)習(xí)方法[1]，在處理小規(guī)模二分類問題時(shí)表現(xiàn)出較好的性能，并在很多領(lǐng)域如手寫數(shù)字識別[2]、人臉識別[3]、時(shí)間序列預(yù)測[4]得到成功應(yīng)用。SVM 在處理小樣本數(shù)據(jù)集時(shí)比較有效，但實(shí)際應(yīng)用中往往要處理一些大規(guī)模數(shù)據(jù)集，由于算法需要利用整個Hessian矩陣，受計(jì)算機(jī)內(nèi)存容量的限制，SVM在處理大規(guī)模數(shù)據(jù)集時(shí)效率低下。為了提高SVM的學(xué)習(xí)效率，許多學(xué)者提出了一些方法，其中，Tang等人于2004年提出了一種新的機(jī)器學(xué)習(xí)模型[5]——粒度支持向量機(jī)（granular support vector machine，GSVM）。其主要思想是首先構(gòu)建粒度空間獲得一系列信息粒，然后在每個信息粒上進(jìn)行SVM學(xué)習(xí)，最后通過聚合信息粒上的信息獲得最終的決策函數(shù)。粒度支持向量機(jī)學(xué)習(xí)算法用重要信息粒代替?zhèn)鹘y(tǒng)的數(shù)據(jù)點(diǎn)進(jìn)行訓(xùn)練，可大大提高支持向量機(jī)的訓(xùn)練效率，同時(shí)獲得滿意的泛化能力[6-7]。目前典型的GSVM模型主要是SVM與關(guān)聯(lián)規(guī)則[8-9]、聚類[10]、粗糙集[11]、決策樹[12]、商空間以及神經(jīng)網(wǎng)絡(luò)[13-14]等相結(jié)合的模型，這些GSVM算法在解決實(shí)際問題時(shí)取得了不錯的效果，尤其是對一些分布較為均勻的大規(guī)模數(shù)據(jù)集，大大提高了SVM的學(xué)習(xí)效率，但在處理一些分布不均勻的數(shù)據(jù)集時(shí)難以奏效。后來提出的動態(tài)粒度SVM 算法（dynamic granular support vector machine learning algorithm，DGSVM）[15]和層次粒度SVM 算法（hierarchical granular support vector machine algorithm，HGSVM）[16]采用多層次粒度劃分的方法可在一定程度上緩解粒劃過程帶來的模型誤差。

本文將近鄰傳輸思想[17]、粒度計(jì)算理論和傳統(tǒng)的SVM 分類方法進(jìn)行有效的融合，提出一種基于近鄰傳輸?shù)牧６萐VM算法——APG_SVM（affinity propagation based granular support vector machine）。APG_SVM 算法選取的粒中心不是求和平均得到的，而是所有數(shù)據(jù)點(diǎn)通過競爭得到的粒中心；APG_SVM算法經(jīng)過初次訓(xùn)練后，找到那些重要的信息粒，用Kmeans聚類算法對它們進(jìn)行繼續(xù)粒劃，提取粒中心加入到訓(xùn)練集；采用此粒劃模型對樣本集進(jìn)行篩選，提取重要的分類信息加入到訓(xùn)練集進(jìn)行訓(xùn)練，可以獲得較好的泛化能力。

2 APG_SVM算法模型

GSVM在很大程度上可以提高傳統(tǒng)SVM的分類效率，但是目前大多數(shù)GSVM 算法在劃分粒的時(shí)候采用的K-means聚類算法，即劃分粒的個數(shù)是由用戶給定的初始粒劃參數(shù)指定的，粒中代表點(diǎn)（粒中心）的選定也是通過求和計(jì)算平均值得到的，這樣得到的粒中心作為粒中的代表點(diǎn)往往不能真正地去表達(dá)一個粒。本文采用一個新的算法：將所有的數(shù)據(jù)點(diǎn)看成潛在的粒中心，計(jì)算數(shù)據(jù)點(diǎn)之間的相似性，再通過迭代計(jì)算出數(shù)據(jù)點(diǎn)之間的親和度與適用度，通過親和度與適用度兩個參數(shù)來確定數(shù)據(jù)點(diǎn)是否可以成為粒的代表點(diǎn)（粒中心）。

APG_SVM 算法考慮到不同粒度之間的分布差異對分類結(jié)果的影響，在經(jīng)過初次SVM訓(xùn)練后，計(jì)算每個粒到分類邊界的距離和粒的混合程度（即粒中正負(fù)樣本的混合程度，混合程度越低的粒越純，純粒是只包含正類或負(fù)類樣本的粒）。對于靠近分類邊界和混合程度較高的粒，由于它們包含相對較多的分類信息，需要對這些粒進(jìn)行細(xì)化，再次粒劃分，得到更多的子粒，取子粒的粒中心代替父粒加入到訓(xùn)練集進(jìn)行再次訓(xùn)練。

首先定義幾個概念。給出一個訓(xùn)練集X={(xi,yi)}，其中xi∈Rd，yi∈{+1,-1}。s(xi,xk)表示數(shù)據(jù)點(diǎn)xi與數(shù)據(jù)點(diǎn)xk之間的相似性，s(xi,xk)=-||xi-xk||2。除了相似性，每個數(shù)據(jù)點(diǎn)還有兩個屬性：數(shù)據(jù)點(diǎn)與其他潛在粒中心的親和度r(xi,xk) 和適用度a(xi,xk) 。r(xi,xk)表示從數(shù)據(jù)點(diǎn)xi角度出發(fā)，與其他潛在粒中心相比，xk作為其代表點(diǎn)（粒中心）的合適程度；a(xi,xk)表示從候選粒中心xk角度出發(fā)，選擇成為數(shù)據(jù)點(diǎn)xi的粒中心的合適程度，而不是作為其他點(diǎn)的粒中心。在第一次迭代中a(xi,xk)初始化為0。親和度r(xi,xk)的計(jì)算方法如下：

在第一次迭代中，因?yàn)檫m用度為0，r(xi,xk)的值就等于數(shù)據(jù)點(diǎn)xi與xk的相似性減去數(shù)據(jù)點(diǎn)xi與其他候選粒中心的相似性的最大值。當(dāng)k=i時(shí)，r(xk,xk)的值就等于s(xk,xk)減去數(shù)據(jù)點(diǎn)xi與其他候選粒中心的相似性的最大值，r(xk,xk)反映了數(shù)據(jù)點(diǎn)xk如果不作為一個粒中心而是從屬于另外一個粒的不合適程度。若r(xk,xk)的值為正，則表示xk適合作為一個粒中心；若r(xk,xk)的值為負(fù)，則表示xk不適合作為粒中心，而應(yīng)該從屬于另外一個粒。在后面的迭代過程中，如果有一些數(shù)據(jù)點(diǎn)被分配給其他的粒，根據(jù)式（2），它們的適用度的值就會下降到負(fù)數(shù)，同樣根據(jù)式（1），負(fù)的適用度又會降低一些點(diǎn)的相似性s(xi,xk)的有效值，這樣就把相應(yīng)的候選粒中心從競爭中刪除。

從上述公式可以看出，如果其他點(diǎn)xi對于xk有正的親和度，那么xk點(diǎn)作為粒中心的適用度就會增加，為了限制正的親和度的影響，給出一個閾值，使它不超過0，如式（3）：

用近鄰傳輸思想求解粒中心的每一次迭代過程包括：（1）更新親和度給出適用度；（2）更新適用度給出親和度；（3）結(jié)合親和度與適用度來監(jiān)控算法并決定是否終止迭代過程。

上述更新規(guī)則簡單且易于計(jì)算，信息（親和度與適用度）只需要在已知相似性的點(diǎn)之間進(jìn)行交換更新，在迭代過程的任意時(shí)刻都可以用適用度與親和度來識別粒中心。當(dāng)算法執(zhí)行到指定的迭代次數(shù)后或者在數(shù)次迭代過程中信息保持穩(wěn)定的狀態(tài)時(shí)終止迭代過程。

根據(jù)以上迭代過程獲取一組粒E=及其粒中心C=，粒ei的半徑反映一個粒的大小，其定義如下：

其中，H(ei)∈[0,1]，H(ei)值越大，表示粒ei的混合度越高；H(ei)值越小，表示粒ei的混合度越低，粒越純；當(dāng)H(ei)=0時(shí)，表示粒ei是純粒。

用T(ei)表示粒ei需要再次劃分粒的個數(shù)，稱之為粒劃因子，一般靠近決策邊界或者混合度較大的粒包含更多的分類信息，也最有可能成為支持向量；本文選擇靠近決策邊界或者混合度較大的粒進(jìn)行再次劃分，從而使樣本空間中得到的信息粒數(shù)目更多。這樣定義的優(yōu)點(diǎn)是能夠?qū)ο鄬χ匾膮^(qū)域提取出更細(xì)更多的分類信息參與訓(xùn)練，而對相對不重要的區(qū)域中只抽取少量代表點(diǎn)加入訓(xùn)練集，因此提取有用信息并剔除冗余信息來構(gòu)造訓(xùn)練集可以獲得更優(yōu)的超平面。T(ei)由粒的混合度和粒到超平面的距離共同決定，其定義如下：

其中，para是一個調(diào)和參數(shù)，用于確定一個粒是否需要再次劃分的重要程度，Yi表示粒ei的中心到超平面的距離。

經(jīng)過SVM 初次訓(xùn)練的粒，有些需要再次粒劃，有些無需再次粒劃。若一個粒滿足Yi＜1+ci或者H(ei)＞δ，則這個粒需要再次粒劃（其中δ是用戶定義的一個置信度，是粒混合度的一個界值，可由統(tǒng)計(jì)實(shí)驗(yàn)得出），即距離分類超平面較近或混合度較高的粒需要再次劃分。

綜上所述，本文提出的APG_SVM算法的主要步驟總結(jié)如下：

步驟1根據(jù)給定的數(shù)據(jù)點(diǎn)的s(xk,xk)值，分別用式（1）和式（2）計(jì)算每個數(shù)據(jù)點(diǎn)的親和度與適用度，然后結(jié)合式（3）進(jìn)行迭代計(jì)算，直到親和度與適用度保持一個相對穩(wěn)定的狀態(tài)，完成了數(shù)據(jù)集進(jìn)行初始粒劃分，得到一系列的初始粒及其粒中心。

步驟2取粒中心放到訓(xùn)練集中進(jìn)行SVM 訓(xùn)練，得到一個分類超平面。

步驟3根據(jù)式（4）和式（5）計(jì)算出每個粒的半徑及混合程度，根據(jù)粒半徑、混合度及粒到超平面的距離找出需要再次劃分的粒，根據(jù)式（6）計(jì)算出需要劃分的粒的粒劃因子，用K-means算法對它們進(jìn)行再次粒劃，得到一組子粒。

步驟4取子粒的粒中心代替原來的粒中心加入到訓(xùn)練數(shù)據(jù)進(jìn)行再次訓(xùn)練，得到分類超平面：

f(x)=sgn(W*φ(x)+b)

步驟5算法結(jié)束。

相對于傳統(tǒng)GSVM分類器，APG_SVM是采用近鄰傳輸思想的競爭機(jī)制求解粒中代表點(diǎn)，這些代表點(diǎn)能夠更加有效地去表達(dá)一個粒，用這些代表點(diǎn)代替一個粒加入到訓(xùn)練集進(jìn)行訓(xùn)練，可大大提高SVM的分類效率。同時(shí)經(jīng)過初次SVM 訓(xùn)練，采用粒到分類超平面的距離和混合度兩個指標(biāo)來判斷粒的重要程度，細(xì)劃重要的分類信息，使包含更多分類信息的樣本加入到訓(xùn)練集，進(jìn)而獲得更好的泛化能力。

3 實(shí)驗(yàn)結(jié)果及相關(guān)分析

將本文提出的APG_SVM 算法與傳統(tǒng)GSVM 算法、HGSVM 算法[16]和DGSVM 算法[15]進(jìn)行比較。本文在6 個典型的UCI 數(shù)據(jù)集（見表1）上進(jìn)行了測試。實(shí)驗(yàn)中采用高斯核函數(shù)，其中正則參數(shù)C取1 000，核參數(shù)d取1.0。調(diào)和參數(shù)para由網(wǎng)格搜索算法計(jì)算取為0.2，δ=0.55。

Table 1 Datasets used in experiment表1 實(shí)驗(yàn)采用的數(shù)據(jù)集

圖1給出了APG_GSVM算法與其他3種算法在初始粒劃參數(shù)取值為100時(shí)的正確率。

從圖1 可以看出，APG_SVM 算法的正確率在幾個數(shù)據(jù)集上都非常高，與GSVM 算法相比，APG_SVM 算法正確率相對穩(wěn)定且算法效率較好；與HGSVM相比，在以上6個數(shù)據(jù)集上，APG_SVM算法的正確率都要高于HGSVM算法；與DGSVM算法相比，APG_SVM算法的正確率除了在Breast_cancer數(shù)據(jù)集上略低于DGSVM算法以外，在其他5個數(shù)據(jù)集上都高于DGSVM 算法。這是因?yàn)楸疚牟扇×私弬鬏斔枷脒x取了更有代表性的粒中心，用這些粒中心進(jìn)行SVM訓(xùn)練，取得了更好的分類效果。

為了測試APG_SVM 算法在訓(xùn)練過程中粒劃分程度的高低，實(shí)驗(yàn)還對最終參加SVM 訓(xùn)練的樣本的個數(shù)進(jìn)行了統(tǒng)計(jì)。圖2給出了APG_SVM算法與GSVM算法、HGSVM算法和DGSVM算法的統(tǒng)計(jì)結(jié)果。

Fig.1 Comparison among APG_SVM and GSVM，HGSVM，DGSVM圖1 APG_SVM算法與GSVM、HGSVM、DGSVM 算法比較

Table 2 Comparison of experimental results by several algorithms表2 幾種方法測試結(jié)果的比較

Fig.2 The number of samples in SVM training of several algorithms圖2 幾種算法中參與SVM訓(xùn)練的樣本個數(shù)

從圖2 可以看出，在幾個數(shù)據(jù)集上，傳統(tǒng)GSVM算法的訓(xùn)練樣本為100，因?yàn)槌跏剂潊?shù)的值設(shè)置為100，而GSVM 只進(jìn)行一次粒劃分；APG_SVM 算法與HGSVM、DGSVM 算法相比，參加SVM 訓(xùn)練的樣本個數(shù)更少，因此訓(xùn)練集的規(guī)模也更小，特別是在數(shù)據(jù)集Thyroid、Heart、Image上最終參加訓(xùn)練集樣本的個數(shù)占整個訓(xùn)練集的比例都在5%以下，在其他數(shù)據(jù)集上最高也不到15%。由于訓(xùn)練規(guī)模的減小，會在很大程度上減少訓(xùn)練時(shí)間，進(jìn)而提高算法的效率。

表2 是APG_SVM 和HGSVM、DGSVM、傳統(tǒng)GSVM 以及經(jīng)典SVM 測試結(jié)果的比較，從實(shí)驗(yàn)結(jié)果中可以看出，在6個數(shù)據(jù)集上APG_SVM訓(xùn)練效率比經(jīng)典SVM 算法有上千倍的提高。APG_SVM 與SVM 相比分類正確率雖有所下降，但仍有較高的分類準(zhǔn)確率。與GSVM 相比，APG_SVM 具有更好的泛化性能。與DGSVM 相比，在6 個數(shù)據(jù)集上APG_SVM的分類效率都有所提高，在其中5個數(shù)據(jù)集上，APG_SVM算法表現(xiàn)出更好的分類性能。與HGSVM相比，在其中3個數(shù)據(jù)集上，分類效率雖有所下降，但APG_SVM算法表現(xiàn)出更好的泛化能力。

上述實(shí)驗(yàn)結(jié)果表明，APG_SVM算法采用近鄰傳輸思想能有效提取支持向量信息，減少模型誤差，獲得了更好的分類性能。與SVM 相比，APG_SVM 算法提取出含有分類信息較多的代表點(diǎn)在數(shù)據(jù)集上進(jìn)行訓(xùn)練，大大壓縮了訓(xùn)練集，在正確率幾乎沒有太大變化的情況下，速度有了很大提高，而且在初次粒劃分之后對重要分類信息進(jìn)行細(xì)劃，使得實(shí)驗(yàn)結(jié)果非常穩(wěn)定。與上述幾個算法相比，APG_SVM仍然保持非常高的分類水平。

4 結(jié)束語

本文提出了一種基于近鄰傳輸?shù)牧６戎С窒蛄繖C(jī)學(xué)習(xí)算法，通過競爭機(jī)制更有效地提取重要的分類信息進(jìn)行SVM訓(xùn)練。同時(shí)，根據(jù)樣本分布特點(diǎn)，細(xì)劃重要分類信息，獲得了很好的泛化性能和訓(xùn)練效率。本文對二分類問題進(jìn)行了實(shí)驗(yàn)驗(yàn)證，在未來的工作中，考慮將算法擴(kuò)展到多類分布不均勻數(shù)據(jù)的分類問題中。另外，可以將本文的方法應(yīng)用于網(wǎng)頁分類、疾病監(jiān)測等大規(guī)模分布不均勻的實(shí)際問題中。