采用劃分融合雙向控制的粒度支持向量機(jī)

趙帥群，郭虎升,，王文劍

（1.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006; 2.山西大學(xué) 計算智能與中文信息處理重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006）

支持向量機(jī)(support vector machine，SVM)是由Vapnik 等[1]提出的基于統(tǒng)計學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險最小化準(zhǔn)則的一種學(xué)習(xí)策略，在小樣本多維度的數(shù)據(jù)分類和回歸問題方面表現(xiàn)出了優(yōu)良的泛化性能，廣泛應(yīng)用于機(jī)器學(xué)習(xí)、模式識別、模式分類、圖像處理等領(lǐng)域[2-8]。目前在大規(guī)模數(shù)據(jù)處理方面，SVM 仍存在一些不足。主要問題是當(dāng)樣本數(shù)n較大時，會消耗大量的內(nèi)存空間和運(yùn)算時間，嚴(yán)重降低了SVM 的學(xué)習(xí)效率，限制了SVM 在大規(guī)模數(shù)據(jù)集上的應(yīng)用。

粒度支持向量機(jī)的含義最早由Tang 等[9]提出，其主要思想是首先構(gòu)建粒度空間獲得一系列信息粒，然后在每個信息粒上進(jìn)行SVM 學(xué)習(xí)，最后聚合信息粒上的信息獲得最終的決策函數(shù)。依據(jù)粒劃分方式的不同，衍生出了基于聚類的GSVM、基于分類的GSVM 以及基于關(guān)聯(lián)規(guī)則的GSVM 等方法[10-19]。GSVM 采用?；姆绞綁嚎s數(shù)據(jù)集的規(guī)模，以提高SVM 的學(xué)習(xí)效率，而目前的GSVM 大都在靜態(tài)層級進(jìn)行劃分，即只對信息粒進(jìn)行有限次的淺層次劃分，丟失了大量對分類起關(guān)鍵作用的樣本信息，且冗余信息較多，降低了模型的性能。盡管已經(jīng)提出的動態(tài)粒度支持向量機(jī)(dynamic granular support vector machine，DGSVM)[20]，以及動態(tài)支持向量回歸機(jī)(dynamic granular support vector regression，DGSVR)[21]，采用動態(tài)的方式對重要信息粒深層次劃分，對無關(guān)信息粒則進(jìn)行淺層次劃分，但DGSVM 隨著粒劃分過程會使數(shù)據(jù)規(guī)模不斷增加，使得SVM 的效率有所降低。

為了進(jìn)一步提升SVM 在大規(guī)模數(shù)據(jù)集上的應(yīng)用能力，本文提出了采用劃分融合雙向控制的粒度支持向量機(jī)方法。在SVM 分類過程中，對分類起關(guān)鍵重要的信息分布于超平面附近，稱為強(qiáng)信息區(qū)，超平面遠(yuǎn)端的信息對分類影響較小，稱為弱信息區(qū)，本文提出的方法通過對強(qiáng)信息區(qū)的強(qiáng)信息粒進(jìn)行深度劃分，同時融合弱信息區(qū)的弱信息粒，使訓(xùn)練數(shù)據(jù)始終動態(tài)保持在較小規(guī)模。該方法分為兩個階段，首先通過聚類算法對原始數(shù)據(jù)集進(jìn)行初始粒劃分，挑選粒中代表信息組成新的訓(xùn)練集訓(xùn)練得到初始分類超平面，然后通過迭代劃分融合的方式深度劃分強(qiáng)信息粒，同時融合遠(yuǎn)端弱信息粒。實(shí)驗(yàn)表明，該方法能夠在保證模型精度的條件下顯著提升SVM 的學(xué)習(xí)效率。

1 粒度支持向量機(jī)

粒度支持向量機(jī)引入粒計算的概念，對復(fù)雜問題進(jìn)行抽象和簡化，以較低的代價來得到問題的滿意近似解。在多種的粒劃分方式中，基于聚類的粒度支持向量機(jī)(clustering-based granular support vector machine, CGSVM)是當(dāng)前研究的熱點(diǎn)之一[22-25]。CGSVM 通過聚類算法將大規(guī)模數(shù)據(jù)集分解成多個小規(guī)模數(shù)據(jù)簇，簇內(nèi)信息具有高度相似性，而簇間信息相似度較低，挑選出每個簇中具有代表性的樣本信息作為新的訓(xùn)練樣本，整合所有挑選出的樣本訓(xùn)練得到新的模型。

CGSVM 只采用了少量代表樣本作為訓(xùn)練集，有效地加速了SVM 學(xué)習(xí)過程。但CGSVM 本身也存在一些不足，在SVM 學(xué)習(xí)過程中，距離分類超平面較近的信息對分類起關(guān)鍵作用，而距離超平面較遠(yuǎn)的信息幾乎不影響模型訓(xùn)練過程。CGSVM 在數(shù)據(jù)處理過程中沒有區(qū)分不同信息粒對分類的影響程度，對所有信息粒都進(jìn)行同等層次的劃分，導(dǎo)致對重要信息提取不足且仍存在過多的冗余信息。如圖1 中，距離超平面較近的中包含較多支持向量信息，對分類起到了關(guān)鍵作用，距離超平面較遠(yuǎn)的對分類影響較小。盡管DGSVM 通過對超平面附近重要信息粒深度劃分，但遠(yuǎn)端的冗余信息仍然被保留，在動態(tài)劃分過程中數(shù)據(jù)規(guī)模會不斷增加，導(dǎo)致訓(xùn)練時間也不斷地提高。

圖1 CGSVM 粒度劃分Fig.1 CGSVM granular division

2 DFSVM 模型

現(xiàn)階段CGSVM 通過靜態(tài)的、淺層次的方式，對粒劃后的信息粒進(jìn)行無差別的信息提取，導(dǎo)致對分類起關(guān)鍵作用的信息提取不足且還保留了大量對分類影響較小的冗余信息。本文提出的方法采用多層次的劃分策略，由于超平面附近的樣本信息有較大概率成為支持向量，距離超平面較遠(yuǎn)的樣本信息對分類幾乎沒有影響，因此，DFS-

VM 采取動態(tài)迭代劃分的方式，對超平面附近可能成為支持向量的信息粒深度劃分，同時融合距離超平面較遠(yuǎn)的冗余信息，不斷更新超平面以獲得更多潛在有效的分類信息，該方法能夠?qū)⒂?xùn)練集始終固定在一個較小的規(guī)模，加速了SVM 的訓(xùn)練過程。

2.1 初始粒劃分

給定原始數(shù)據(jù)集D={X,y}={(x1,y1)，(x2,y2), ···,(xe,ye)}，ye∈{1,-1}，xe∈Rl，DFSVM 首先通過聚類算法將數(shù)據(jù)集中的正類與負(fù)類樣本分別劃分為k個粒，通過初始粒劃分方式得到新的信息粒集：

式中：Gk表示通過劃分得到的信息粒。SVM 通過核函數(shù)K(x,y)=φ(x)φ(y) 將數(shù)據(jù)映射到N維核空間，將數(shù)據(jù)集經(jīng)過初次劃分在N維空間形成的粒稱為超粒，第i個超粒的中心ui和半徑 γi為

式中： φ (xl) 和 φ (xm) 代表核空間上下邊界，超粒半徑通過其平均值衡量，樣本 φ(xs) 到任意超粒Gi中心 μi的距離可表示為

通過初始粒劃分將原始數(shù)據(jù)集劃分為G1、G2、 · ··Gk個粒，提取每個粒中的代表信息以訓(xùn)練獲得初始分類超平面。

2.2 動態(tài)劃分融合方法

通過初始粒劃過程獲得超平面y=WT·φ(x) +b，在SVM 模型分類過程中，對分類起關(guān)鍵作用的樣本信息主要分布在最大間隔內(nèi)部以及間隔線附近，該區(qū)域的樣本在模型訓(xùn)練過程中會被多次遍歷，而位于超平面相對較遠(yuǎn)的樣本無需過多的遍歷即可將其分類正確。因此，基于以上條件將樣本劃分為強(qiáng)信息區(qū)與弱信息區(qū)。給出兩個參數(shù)β+和 β-， 其中 β+＞β-。當(dāng)樣本與超平面之間的距離滿足D′≤ γ/2+β-時，樣本點(diǎn)對分類超平面具有重要影響，劃分為強(qiáng)信息區(qū)。同理，樣本與超平面之間的距離D′≥γ/2+β+時，認(rèn)為樣本點(diǎn)對分類超平面影響較小，劃分為弱信息區(qū)。其中 β-可在0 至 γ /2 之間選取， β+可在 γ /2 至 γ 間選取。強(qiáng)信息區(qū)的信息有較大可能在迭代融合劃分過程中成為支持向量，弱信息區(qū)的數(shù)據(jù)則對分類影響較小，對強(qiáng)信息粒區(qū)域采用劃分方式提取分類信息，對弱信息區(qū)采用融合方式減少冗余信息。其中，超平面最大間隔 γ 為

針對每個劃分好的信息粒，選擇中心點(diǎn) μi作為代表點(diǎn)計算該粒到超平面之間的距離，公式如下：

動態(tài)劃分過程通過衡量粒與超平面之間距離來選取候選粒進(jìn)行深度劃分。但由于不同粒的大小、粒內(nèi)部數(shù)據(jù)分布等差異，密度較大的粒中信息分布集中、重疊度大，含有更多潛在成為支持向量的信息；密度較小的粒中信息分布稀疏，包含的支持向量信息少。因此，對超平面附近密度較大的信息粒優(yōu)先選擇在當(dāng)前迭代過程中劃分，密度相對較小的信息?？赡艹蔀楹罄m(xù)劃分過程中的候選粒。為了衡量每個粒的差異程度，給出粒密度的定義：

式中：ni為第i個粒 中 的 樣本數(shù)； γi為第i個粒的半徑。

圖2 表示DFSVM 動態(tài)粒劃過程，其中G1+、G2-被選為當(dāng)前最優(yōu)分類信息粒，G1+被劃分為Gd1+、Gd2+，G2-被劃分為Gd1-、Gd2-。同時將G4-和G5-融合為Gm-，G4+和G5+融合為Gm+

2.3 DFSVM 算法

DFSVM 模型的數(shù)據(jù)處理過程分為兩個階段：1) 對原始數(shù)據(jù)進(jìn)行初始粒劃分，然后通過式(1)計算得到每個粒的粒心，將所有粒心作為訓(xùn)練集訓(xùn)練得到初始分類超平面；2)利用動態(tài)劃分融合的思想，對信息粒不斷迭代處理以獲得最優(yōu)分類超平面。首先通過式(4)與參數(shù) β+、 β-劃分強(qiáng)信息區(qū)與弱信息區(qū)，利用式(5)、(6)計算這兩個區(qū)域內(nèi)每個粒與超平面的距離和自身的粒密度，挑選強(qiáng)信息區(qū)距超平面較近且粒密度大的粒在當(dāng)前迭代過程進(jìn)行劃分，挑選弱信息區(qū)距超平面較遠(yuǎn)且粒密度小的粒在當(dāng)前迭代過程進(jìn)行融合，用劃分后的超粒代替原始超粒。在該方式下，數(shù)據(jù)規(guī)模能夠保持在較低水平，SVM 的學(xué)習(xí)效率也得到有效的提升。

圖2 動態(tài)劃分融合過程Fig.2 Dynamic division and fusion process

本文提出的DFSVM 針對傳統(tǒng)SVM 無法高效的處理大規(guī)模數(shù)據(jù)以及CGSVM 靜態(tài)劃分的不足進(jìn)行了改進(jìn)，探討的目標(biāo)是DFSVM 是否能夠在保證精度損失較少的情況下有效提升SVM 的學(xué)習(xí)效率。本文在不同的參數(shù)下做了大量實(shí)驗(yàn)，基本算法描述如下：

算法采用劃分融合雙向控制的粒度支持向量機(jī)

輸入原始數(shù)據(jù)集D，初始?；瘏?shù)k，動態(tài)?；瘏?shù)m，迭代粒化參數(shù)d，停止條件t(預(yù)先設(shè)定的模型迭代次數(shù))；

輸出劃分融合過程得到的模型測試結(jié)果集。

1)用聚類算法將數(shù)據(jù)集D中每一類劃分為k個粒G1,G2,···,Gk；

2)將劃分后的每個粒中心加入到訓(xùn)練集中訓(xùn)練得到初始分類超平面f′；

3)通過式(4)和式(6)計算強(qiáng)信息區(qū)的信息粒與超平面的距離Di以及粒密度 ρi，挑選當(dāng)前需要劃分的d個信息粒，并將這些信息粒分別深度劃分為m個子粒；

4)通過式(4)和式(6)計算弱信息區(qū)信息粒、超平面的距離Di與粒密度 ρi，挑選出當(dāng)前需要融合的d×m個弱信息粒；

5)將更新后的信息粒代替原信息加入到訓(xùn)練集并更新分類超平面，同時記錄模型測試結(jié)果；

6)重復(fù)4)～6)，直到滿足停止條件t；

7)記錄模型結(jié)果集，算法結(jié)束。

傳統(tǒng)SVM 模型訓(xùn)練的時間復(fù)雜度和空間復(fù)雜度分別為o(n3) 和o(n2)， 其中n為數(shù)據(jù)的規(guī)模。SVM 在模型訓(xùn)練過程中，需要存儲和計算大規(guī)模的核矩陣，隨著數(shù)據(jù)規(guī)模的增長，效率會大大降低。DFSVM 算法采用動態(tài)劃分融合雙向控制的方式對數(shù)據(jù)集進(jìn)行迭代劃分，始終將訓(xùn)練集維持在較小的規(guī)模，提高了模型的學(xué)習(xí)效率。盡管DFSVM 在劃分過程中會多次訓(xùn)練超平面，但訓(xùn)練總耗時仍然較少，并進(jìn)一步改進(jìn)了CGSVM 靜態(tài)單層劃分對重要信息提取不足的缺點(diǎn)，針對于強(qiáng)信息粒進(jìn)行信息提取，同時融合冗余的弱信息粒，降低訓(xùn)練規(guī)模的同時提升CGSVM 的訓(xùn)練精度。DFSVM 模型在保證較高分類精度的條件下，有效地提升了模型的學(xué)習(xí)效率。

3 實(shí)驗(yàn)和分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文實(shí)驗(yàn)在多個UCI 數(shù)據(jù)集和標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，見表1，SVM 選用高斯核函數(shù)，在多種參數(shù)下進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)在一臺CPU 為2.50 GHz，內(nèi)存8 GB 計算機(jī)上運(yùn)行，實(shí)驗(yàn)平臺為Matlab2016a。

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental data sets

3.2 動態(tài)粒劃分結(jié)果分析

本文提出的采用劃分融合雙向控制的粒度支持向量機(jī)模型，在粒劃分過程中逐步提取潛在的支持向量信息，通過信息融合清除掉過多的冗余信息，提升SVM 的學(xué)習(xí)效率。本小節(jié)實(shí)驗(yàn)驗(yàn)證DFSVM粒劃分融合過程中對SVM 泛化能力的影響。

由于初始參數(shù)k決定了動態(tài)劃分融合階段的數(shù)據(jù)規(guī)模，k值過小會導(dǎo)致學(xué)習(xí)性能的下降，過大會增加時間消耗，因此對于不同數(shù)據(jù)集需要選擇合適的參數(shù)值，在3.4.3 節(jié)中有相關(guān)參數(shù)討論。為了盡可能觀測粒劃過程中預(yù)測準(zhǔn)確率的變化，本節(jié)實(shí)驗(yàn)設(shè)定迭代粒劃參數(shù)d=1， 動態(tài)?；瘏?shù)m=2，既每次將一個強(qiáng)信息粒劃分為2 個子粒，同時將遠(yuǎn)端的兩個弱信息粒進(jìn)行融合，圖中初始結(jié)果即為CGSVM 結(jié)果，SVM 懲罰因子c=1，高斯核參數(shù)g=1/k′(k′為特征數(shù))。

從圖3 中可以看出，在對數(shù)據(jù)集迭代劃分融合過程中，SVM 的分類準(zhǔn)確率逐步提高，但不同數(shù)據(jù)集的變化情況也存在差異。

實(shí)驗(yàn)結(jié)果表明本文提出的方法能夠充分提取數(shù)據(jù)集中的關(guān)鍵信息，有效地提升了模型的學(xué)習(xí)效率。在有限次的數(shù)據(jù)處理過程中，數(shù)據(jù)分布增強(qiáng)了對SVM 的適應(yīng)性，但隨著劃分次數(shù)增加，數(shù)據(jù)分布的改變可能導(dǎo)致SVM 過擬合化，降低模型性能，如spambase 數(shù)據(jù)顯示出迭代次數(shù)大于20 時，準(zhǔn)確率有明顯下降趨勢。實(shí)驗(yàn)表明采用劃分融合雙向控制的粒度劃分方法在一定程度上具有普適性。

圖3 粒劃分過程中精度變化Fig.3 Accuracy change during granules division process

3.3 模型精度與時間結(jié)果分析

針對在迭代過程中模型預(yù)測準(zhǔn)確率和時間變化與傳統(tǒng)SVM、CGSVM、DGSVM 進(jìn)行對比，參數(shù)選取與4.2 節(jié)中實(shí)驗(yàn)相同，DGSVM 平均每次劃分?jǐn)?shù)據(jù)增量為4，圖4 為時間對比圖，圖5 為準(zhǔn)確率對比圖。

圖4 中的實(shí)驗(yàn)結(jié)果表明，隨著迭代次數(shù)的增加，DGSVM 的訓(xùn)練時間增加率快于DFSVM。實(shí)驗(yàn)在german、thyroid、spambase 數(shù)據(jù)集上的預(yù)測準(zhǔn)確率沒有在有效粒劃次數(shù)內(nèi)達(dá)到最優(yōu)，在其他數(shù)據(jù)集上都達(dá)到了最優(yōu)值。圖5 中結(jié)果表明DGSVM的精度達(dá)到的峰值要高于DFSVM，但時間消耗上要接近DFSVM 的兩倍，且高于傳統(tǒng)SVM 的訓(xùn)練時間。DGSVM 與DFSVM 在傳統(tǒng)SVM 基礎(chǔ)上通過數(shù)據(jù)壓縮的方式降低了數(shù)據(jù)規(guī)模，提升了模型效率，而迭代次數(shù)會影響DGSVM 與DFSVM 的學(xué)習(xí)效率。DFSVM 通過劃分融合的方式動態(tài)保持了數(shù)據(jù)規(guī)模的穩(wěn)定，而DGSVM 的數(shù)據(jù)規(guī)模在劃分的過程中不斷增大，導(dǎo)致訓(xùn)練時間增加。DFSVM 在時間上有明顯的提升，與DGSVM 相比仍然損失了一些精度。

圖4 不同方法模型訓(xùn)練時間對比Fig.4 Comparison of model training time on different methods

3.4 參數(shù)對DFSVM 的影響

3.4.1 迭代參數(shù)與粒劃分參數(shù)分析

DFSVM 迭代過程中參數(shù)d控制每次劃分的粒數(shù)目，參數(shù)m控制每個粒進(jìn)行深度劃分的數(shù)目，其他參數(shù)與3.2 節(jié)中設(shè)置相同。實(shí)驗(yàn)中準(zhǔn)確率、時間和迭代次數(shù)分別采用模型訓(xùn)練結(jié)果達(dá)到穩(wěn)定時的平均水平進(jìn)行對比，見表2，其中acc 表示模型準(zhǔn)確率，t表示所用時間，h表示動態(tài)迭代劃分次數(shù)。

由表2 中數(shù)據(jù)可以看出，隨著參數(shù)d、m的增大，每次參與劃分和融合的數(shù)據(jù)增多，模型能夠在較少的迭代次數(shù)內(nèi)收斂到最優(yōu)值。由于數(shù)據(jù)集規(guī)模與分布的不同，結(jié)果存在一定的差異，預(yù)測結(jié)果波動范圍較小，表明參數(shù)d、m在取值較大時能夠降低算法迭代次數(shù)，有效縮短模型訓(xùn)練時間。

圖5 不同方法測試精度對比Fig.5 Accuracy comparison on different methods

3.4.2 SVM 模型參數(shù)分析

本實(shí)驗(yàn)中主要調(diào)節(jié)SVM 中參數(shù)懲罰因子c以及高斯核參數(shù)g。實(shí)驗(yàn)選取不同c、g參數(shù)值進(jìn)行實(shí)驗(yàn)，討論懲罰因子及核參數(shù)對實(shí)驗(yàn)結(jié)果的影響，其余參數(shù)與3.2 節(jié)中設(shè)置相同，模型預(yù)測結(jié)果見圖6，c、g參數(shù)取值見表3。如圖6，參數(shù)c、g的變化影響數(shù)據(jù)的最優(yōu)性能，所有數(shù)據(jù)集都能夠通過懲罰參數(shù)和核參數(shù)的調(diào)節(jié)來提高DFSVM 的性能，而且大部分?jǐn)?shù)據(jù)集在迭代過程中都表現(xiàn)出較好的穩(wěn)定性，thyroid、spambase 數(shù)據(jù)集出現(xiàn)了一些離群點(diǎn)，但不影響總體結(jié)果。

3.4.3 初始聚類參數(shù)k

動態(tài)劃分首先要通過初始聚類參數(shù)k對數(shù)據(jù)進(jìn)行壓縮，壓縮過小會因欠擬合而降低模型精度，壓縮過大則可能造成數(shù)據(jù)冗余而降低模型效率，因此，本節(jié)實(shí)驗(yàn)選取不同的參數(shù)k進(jìn)行了實(shí)驗(yàn)分析，其他參數(shù)與3.2 節(jié)中設(shè)置相同，測試結(jié)果見圖7。

表2 迭代參數(shù) d 與粒劃參數(shù) m 實(shí)驗(yàn)結(jié)果Table 2 The result on iteration parameter d and dividing parameter m

由于不同數(shù)據(jù)集規(guī)模和分布差異，參數(shù)k的選取也不同。從圖7 中可以看出，k值在一定范圍內(nèi)增加會使模型準(zhǔn)確率有所提升，在splice 和german 數(shù)據(jù)結(jié)果中，不同的參數(shù)k對應(yīng)的曲線具有明顯差異性，但對于diabetis 和image 數(shù)據(jù)集，參數(shù)k存在相對最優(yōu)值，即k高于某一值后對模型結(jié)果提升不明顯。當(dāng)k值較小時，甚至?xí)@著降低模型性能，如german 數(shù)據(jù)集在k取100 時，結(jié)果變差。實(shí)驗(yàn)表明，k值的選取對模型結(jié)果有一定的影響。

圖6 懲罰因子 c 與高斯核參數(shù) g 的影響Fig.6 The effect of cost parameter c and RBF kernel parameterg

表3 SVM 模型參數(shù)取值Table 3 The value of the SVM model parameters

圖7 初始聚類參數(shù) k 對測試結(jié)果的影響Fig.7 The effect of initial clustering parameter k on the experiment

4 結(jié)束語

本文在動態(tài)粒度支持向量機(jī)的基礎(chǔ)上結(jié)合劃分與融合的思想，擴(kuò)展了SVM 在大規(guī)模數(shù)據(jù)集上應(yīng)用的能力，通過多種參數(shù)共同調(diào)節(jié)，能夠保證在精度損失較小的情況下，提升SVM 的學(xué)習(xí)效率。但在采用劃分與融合的思想在數(shù)據(jù)處理過程中可能會改變數(shù)據(jù)集的分布，限制了數(shù)據(jù)迭代劃分次數(shù)，參數(shù)調(diào)節(jié)也增加了模型的復(fù)雜度。在未來的工作中，會繼續(xù)針對該模型在實(shí)際應(yīng)用問題中進(jìn)行探討，在簡化模型的同時保證模型的泛化性能。