基于近鄰傳輸的粒度SVM算法*

程鳳偉，王文劍

1.太原學院 計算機工程系，太原030032

2.山西大學 計算機與信息技術學院，太原030006

3.山西大學 計算智能與中文信息處理教育部重點實驗室，太原030006

1 引言

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

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

2 APG_SVM算法模型

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

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

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

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

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

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

上述更新規則簡單且易于計算，信息（親和度與適用度）只需要在已知相似性的點之間進行交換更新，在迭代過程的任意時刻都可以用適用度與親和度來識別粒中心。當算法執行到指定的迭代次數后或者在數次迭代過程中信息保持穩定的狀態時終止迭代過程。

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

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

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

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

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

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

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

步驟2取粒中心放到訓練集中進行SVM 訓練，得到一個分類超平面。

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

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

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

步驟5算法結束。

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

3 實驗結果及相關分析

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

Table 1 Datasets used in experiment表1 實驗采用的數據集

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

從圖1 可以看出，APG_SVM 算法的正確率在幾個數據集上都非常高，與GSVM 算法相比，APG_SVM 算法正確率相對穩定且算法效率較好；與HGSVM相比，在以上6個數據集上，APG_SVM算法的正確率都要高于HGSVM算法；與DGSVM算法相比，APG_SVM算法的正確率除了在Breast_cancer數據集上略低于DGSVM算法以外，在其他5個數據集上都高于DGSVM 算法。這是因為本文采取了近鄰傳輸思想選取了更有代表性的粒中心，用這些粒中心進行SVM訓練，取得了更好的分類效果。

為了測試APG_SVM 算法在訓練過程中粒劃分程度的高低，實驗還對最終參加SVM 訓練的樣本的個數進行了統計。圖2給出了APG_SVM算法與GSVM算法、HGSVM算法和DGSVM算法的統計結果。

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 幾種方法測試結果的比較

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

從圖2 可以看出，在幾個數據集上，傳統GSVM算法的訓練樣本為100，因為初始粒劃參數的值設置為100，而GSVM 只進行一次粒劃分；APG_SVM 算法與HGSVM、DGSVM 算法相比，參加SVM 訓練的樣本個數更少，因此訓練集的規模也更小，特別是在數據集Thyroid、Heart、Image上最終參加訓練集樣本的個數占整個訓練集的比例都在5%以下，在其他數據集上最高也不到15%。由于訓練規模的減小，會在很大程度上減少訓練時間，進而提高算法的效率。

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

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

4 結束語

本文提出了一種基于近鄰傳輸的粒度支持向量機學習算法，通過競爭機制更有效地提取重要的分類信息進行SVM訓練。同時，根據樣本分布特點，細劃重要分類信息，獲得了很好的泛化性能和訓練效率。本文對二分類問題進行了實驗驗證，在未來的工作中，考慮將算法擴展到多類分布不均勻數據的分類問題中。另外，可以將本文的方法應用于網頁分類、疾病監測等大規模分布不均勻的實際問題中。