黃恒秋，翁世洲

（1.廣西民族師范學(xué)院數(shù)理與電子信息工程學(xué)院，崇左 532200；2.廣西民族師范學(xué)院經(jīng)濟(jì)管理學(xué)院，崇左 532200）

0 引言

支持向量機(jī)由Cortes 等［1］提出，是機(jī)器學(xué)習(xí)領(lǐng)域中非常重要的一種分類(lèi)方法，它基于統(tǒng)計(jì)學(xué)習(xí)理論，具有結(jié)構(gòu)風(fēng)險(xiǎn)最小化、魯棒性強(qiáng)、泛化能力佳等優(yōu)點(diǎn)［2］，已經(jīng)在模式識(shí)別、信號(hào)處理、數(shù)據(jù)挖掘等諸多現(xiàn)實(shí)問(wèn)題中得到廣泛的應(yīng)用［3-4］。

支持向量機(jī)訓(xùn)練本質(zhì)上是求解一個(gè)二次規(guī)劃問(wèn)題［5］，對(duì)于小規(guī)模問(wèn)題已有成熟的優(yōu)化算法及軟件工具可以使用，對(duì)于大規(guī)模問(wèn)題也有諸如序列最小優(yōu)化算法（SMO）［6］等優(yōu)秀的研究成果，但是針對(duì)現(xiàn)實(shí)應(yīng)用中廣泛存在的混合不完備數(shù)據(jù)集則不能直接處理。所謂混合不完備數(shù)據(jù)集是指含分類(lèi)型和連續(xù)型缺失屬性值的數(shù)據(jù)集。目前，利用支持向量機(jī)處理該類(lèi)數(shù)據(jù)集的方法主要有：①填充支持向量機(jī)分類(lèi)方法。對(duì)缺失值進(jìn)行填充處理后再進(jìn)行分類(lèi)，比如利用均值和主成分分析［7］、最近鄰［7-8］、貝葉斯［8-9］、多項(xiàng)式回歸［9］、期望最大化（EM）［10］、多層期望最大化和決策樹(shù)［11］、粗糙集相容關(guān)系［12］、典型實(shí)例選擇［13］、基于聚類(lèi)的多重插值［14］等方法進(jìn)行填充后再利用支持向量機(jī)進(jìn)行分類(lèi)。文獻(xiàn)［11,15］還研究了將分類(lèi)效果與填充方法相結(jié)合的選擇-融合集成分類(lèi)方法。②混合距離支持向量機(jī)分類(lèi)方法?；诨旌暇嚯x函數(shù)（Heteroge?neous Euclidean Overlap Metric，HEOM）［16］，用極端值代替缺失值后再進(jìn)行分類(lèi)，比如文獻(xiàn)［17-20］。③風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法。對(duì)含有缺失值的對(duì)象，重新定義預(yù)測(cè)風(fēng)險(xiǎn)函數(shù)，通過(guò)最小化結(jié)構(gòu)風(fēng)險(xiǎn)和預(yù)測(cè)風(fēng)險(xiǎn)，構(gòu)建能處理缺失數(shù)據(jù)的支持向量機(jī)模型［21］。

基于填充的支持向量機(jī)分類(lèi)方法，其研究成果最為豐富。然而，文獻(xiàn)［22］指出，找到合適的填充方法，保證其分類(lèi)效果，需要對(duì)不同的缺失類(lèi)型、插值填充方法做多次交互操作才能實(shí)現(xiàn)。對(duì)于混合距離支持向量機(jī)分類(lèi)方法，其關(guān)鍵在距離度量函數(shù)，正如文獻(xiàn)［23］指出，HEOM距離將缺失屬性值取作最大值或者最小值，如果屬性較多且樣本屬性值缺失比例較大，會(huì)造成系統(tǒng)信息失真。這兩種方法均需要對(duì)缺失數(shù)據(jù)進(jìn)行填充處理，改變了數(shù)據(jù)集的原貌，其分類(lèi)效果也不是原始數(shù)據(jù)集的真實(shí)反映。風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法則不需要對(duì)缺失數(shù)據(jù)進(jìn)行填充處理，但是由于重構(gòu)了風(fēng)險(xiǎn)目標(biāo)函數(shù)及不完備對(duì)象的約束條件，增加了應(yīng)用的復(fù)雜性。

為了避免對(duì)缺失數(shù)據(jù)進(jìn)行填充或者取極端值而造成系統(tǒng)信息失真，同時(shí)又能充分度量不確定對(duì)象之間的相似性關(guān)系，文獻(xiàn)［24-27］給出了同一度、對(duì)立度、差異度、勢(shì)函數(shù)和集對(duì)距離的概念，文獻(xiàn)［28］給出了鄰域聯(lián)系度距離函數(shù)的定義。本文首先基于文獻(xiàn)［28］給出的鄰域聯(lián)系度距離函數(shù)，對(duì)高斯核進(jìn)行拓展定義，使其能夠直接處理混合不完備數(shù)據(jù)集；其次給出基于二次函數(shù)逼近的不確定高斯核支持向量機(jī)SMO訓(xùn)練算法和分類(lèi)算法。

為了檢驗(yàn)本文分類(lèi)算法的有效性，取多個(gè)UCI 數(shù)據(jù)集進(jìn)行了對(duì)比實(shí)驗(yàn)分析。首先，與決策樹(shù)、單層期望最大化、多層期望最大化、選擇-融合集成等經(jīng)典插值填充支持向量機(jī)分類(lèi)方法進(jìn)行對(duì)比；其次與取極端值的混合距離支持向量機(jī)分類(lèi)方法進(jìn)行對(duì)比；最后，與文獻(xiàn)［21］的風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果顯示，本文的分類(lèi)方法獲得了優(yōu)異的分類(lèi)效果。

1 支持向量機(jī)相關(guān)概念

1.1 支持向量機(jī)模型

對(duì)于兩類(lèi)問(wèn)題，給定樣本集(xt,yt)；xt∈Rn,yt=±1,t=1,2,…,l和核函數(shù)K(xt,xs)。K 對(duì)應(yīng)特征空間的內(nèi)積K(xt,xs)=(xt,xs)=(?(xt),?(xs))，?為非線(xiàn)性函數(shù)。訓(xùn)練支持向量機(jī)分類(lèi)器就是在特征空間中尋找使得兩類(lèi)間隔最大的超平面H。支持向量機(jī)的訓(xùn)練過(guò)程，本質(zhì)上是解決以下二次規(guī)劃問(wèn)題：

其中α為拉格朗日乘子，Q為Hessian 矩陣，Qts=ytysK(xt,xs)，e為全1 向量，C為懲罰因子。應(yīng)用拉格朗日乘數(shù)法并滿(mǎn)足KKT 條件：

最后可得到上述最優(yōu)化問(wèn)題的最優(yōu)分類(lèi)函數(shù)：

其中α?為問(wèn)題（1）的最優(yōu)解，由（2）式知非支持向量=0，故

其中k為支持向量（α?>0）的個(gè)數(shù)，即本文中最優(yōu)分類(lèi)超平面的偏置量b?取支持超平面偏置量的平均值。

1.2 基于二次函數(shù)逼近的支持向量機(jī)SMO訓(xùn)練算法

訓(xùn)練支持向量機(jī)本質(zhì)上是求解最優(yōu)化問(wèn)題（1），這是一個(gè)二次規(guī)劃問(wèn)題，變量個(gè)數(shù)與樣本個(gè)數(shù)l相同，而矩陣Q的規(guī)模則是l×l。當(dāng)樣本個(gè)數(shù)較少的時(shí)候，利用目前成熟的二次規(guī)劃問(wèn)題求解方法即可。隨著樣本規(guī)模的增大，傳統(tǒng)的二次規(guī)劃問(wèn)題求解方法不再適用，為了克服以上問(wèn)題，不少研究者設(shè)計(jì)了基于分解的求解方法，文獻(xiàn)［6］將分解方法推向極致，即每次只更新兩個(gè)元素，稱(chēng)為序列最小化方法（SMO），文獻(xiàn)［5］給出了二次函數(shù)逼近的SMO快速訓(xùn)練算法。

2 混合不完備數(shù)據(jù)的拓展高斯核-支持向量機(jī)分類(lèi)方法

2.1 鄰域聯(lián)系度距離函數(shù)

定義1［20］混合距離函數(shù)（簡(jiǎn)稱(chēng)HEOM）定義如下：

其中,

定義2［24］給定混合值不完備數(shù)據(jù)集I=(U,A∪D,V,f),|A|=N,Δ 為絕對(duì)值距離函數(shù)，（xi,xj）∈U2為集對(duì)。記ε為屬性值相容的鄰域半徑，設(shè)M={a∈A|Δa(xi,xj)≤ε}為集對(duì)取值在相容鄰域范圍之內(nèi)的屬性集；H={a∈A|Δa(xi,xj)>ε}為集對(duì)取值在相容鄰域范圍之外的屬性集；G={a∈A|f(xi,a)=?∨f(xj,a)=?}為集對(duì)取值不明確的屬性集。記，則集對(duì)（xi,xj）的鄰域聯(lián)系度定義為

其中m,g,h記作同一度、差異度和對(duì)立度，i*、j*為差異度和對(duì)立度標(biāo)記，起到與同一度區(qū)別的作用。

從定義1可以看出，HEOM 距離缺失值取極端值1代替，文獻(xiàn)［29］則是以另一個(gè)極端值0 來(lái)代替。正如文獻(xiàn)［23］所指出，當(dāng)缺失值比例較大時(shí)這兩種情況會(huì)造成系統(tǒng)信息失真。文獻(xiàn)［24］從比較屬性的相同部分、相異部分和不確定部分，即同一度、對(duì)立度、差異度三方面進(jìn)行系統(tǒng)分析，且不需要對(duì)缺失值進(jìn)行填充處理，不失為一種有效的不確定對(duì)象相似性度量方法。但是，如何將這種度量方法有效地應(yīng)用于實(shí)際計(jì)算問(wèn)題，閾值怎樣設(shè)置等，文獻(xiàn)沒(méi)有給出進(jìn)一步的討論。從定義2可以看出，同一度反映了兩個(gè)樣本的相同或者相容部分，最理想情況為1。因此，將兩個(gè)樣本的同一度與最理想情況作比較，可獲得其同一度的差異，而對(duì)立度和差異度，本身就反映了兩個(gè)對(duì)象之間的差異。將它們的差異通過(guò)加權(quán)的方式計(jì)算出來(lái)，就是聯(lián)系度距離。

定義3［28］給定樣本x,y的鄰域聯(lián)系度μ(x,y)=m+gi*+hj*，則它們的鄰域聯(lián)系度距離定義為

其中，w1,w2,w3為同一度、差異度和對(duì)立度的懲罰系數(shù)，且要求w1+w2+w3=1。

從定義可以看出，該距離函數(shù)繼承了同一度、對(duì)立度和差異度在度量不確定樣本相似性方面的優(yōu)勢(shì)，且利用的信息更加全面，同時(shí)避免了相關(guān)聯(lián)系度閾值的選擇問(wèn)題，也避免了對(duì)缺失屬性值人為干預(yù)填充或者取極端值的情形。

關(guān)于懲罰系數(shù)w1,w2,w3，事實(shí)上，兩個(gè)樣本屬性取值不相同或者相異，最能反映樣本之間的差異，體現(xiàn)為對(duì)立度，因此懲罰系數(shù)應(yīng)該最大；差異度是由于樣本屬性值缺失造成的，缺失值有可能與比較樣本相異，其懲罰系數(shù)次之；同一度，反映比較樣本明確不相異部分，懲罰系數(shù)應(yīng)該最小。

2.2 基于鄰域聯(lián)系度距離擴(kuò)展高斯核函數(shù)的定義

高斯核函數(shù)是支持向量機(jī)分類(lèi)問(wèn)題中應(yīng)用非常廣泛的一類(lèi)核函數(shù)。本文在傳統(tǒng)的高斯核函數(shù)基礎(chǔ)上，給出拓展定義的高斯核函數(shù)，用于對(duì)混合不完備數(shù)據(jù)進(jìn)行處理。

定義4［5］高斯核函數(shù)定義如下：

其中，γ為核函數(shù)寬度調(diào)整參數(shù)。從定義可以看出，高斯核函數(shù)是關(guān)于兩個(gè)對(duì)象之間距離的函數(shù)，其距離為確定距離。下面將給出基于不確定距離——聯(lián)系度距離的不確定高斯核函數(shù)定義。

定義5基于鄰域聯(lián)系度距離拓展定義的高斯核函數(shù)如下：

其中，γ 的含義同定義4，而CDD(xi，xj)則為對(duì)象xi,xj的聯(lián)系度距離。

2.3 基于二次函數(shù)逼近的拓展高斯核-支持向量機(jī)SMO訓(xùn)練算法

算法3 沒(méi)有改變二次規(guī)劃問(wèn)題（1）的模型結(jié)構(gòu)和約束條件，還充分利用了文獻(xiàn)［5，6］SMO訓(xùn)練算法的研究成果，本質(zhì)上沒(méi)有增加求解的復(fù)雜性，從而更好地推廣應(yīng)用到實(shí)際問(wèn)題當(dāng)中。

2.4 混合不完備數(shù)據(jù)的拓展高斯核-支持向量機(jī)分類(lèi)方法

傳統(tǒng)支持向量機(jī)模型是基于二分類(lèi)問(wèn)題，而實(shí)際應(yīng)用中的數(shù)據(jù)集不僅包括二類(lèi)，還可能存在多類(lèi)。下面給出多類(lèi)（包括二類(lèi)）混合不完備數(shù)據(jù)集的支持向量機(jī)分類(lèi)算法。

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

從http://archive.ics.uci.edu/ml/下載6 個(gè)UCI數(shù)據(jù)集，其中iris、pima-indians-diabetes（下表用pima表示）、wine為完備數(shù)據(jù)集，其他數(shù)據(jù)集為不完備數(shù)據(jù)集，具體信息見(jiàn)表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集基本信息表

實(shí)驗(yàn)采用MATLAB2011b 進(jìn)行編程，數(shù)值屬性值采用極差法全部規(guī)范化為［0，1］之間。取支持向量機(jī)模型中的懲罰系數(shù)C=1，不確定高斯核函數(shù)寬度調(diào)整參數(shù)r=1/N，其中N為數(shù)據(jù)集的屬性個(gè)數(shù)。聯(lián)系度距離中的懲罰系數(shù)，根據(jù)2.2的分析，取w1=0.1，w2=0.2，w3=0.7。關(guān)于相容鄰域半徑ε的選擇，不同數(shù)據(jù)集，其屬性取值相容程度是不同的，但是由于數(shù)值屬性都規(guī)范化到［0，1］之間，因此取ε介于［0.05，0.3］（間隔0.05），并通過(guò)實(shí)驗(yàn)從中選擇最優(yōu)分類(lèi)精度對(duì)應(yīng)的ε，即為該數(shù)據(jù)集最佳相容鄰域半徑。

下面分別討論本文的分類(lèi)方法（ISVM）與填充支持向量機(jī)分類(lèi)方法、混合距離支持向量機(jī)分類(lèi)方法、風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法的對(duì)比實(shí)驗(yàn)分析。

（1）ISVM 與填充支持向量機(jī)分類(lèi)方法對(duì)比實(shí)驗(yàn)分析。選擇與文獻(xiàn)［11］相一致的數(shù)據(jù)集Breast-cancer、vote、pima 進(jìn)行對(duì)比實(shí)驗(yàn)分析。對(duì)每個(gè)數(shù)據(jù)集依次隨機(jī)增加0%（原始數(shù)據(jù)集）、10%、20%、30%的缺失比例，利用ISVM 進(jìn)行分類(lèi)，以6次交叉檢驗(yàn)獲得的平均精度作為分類(lèi)精度。為了保證結(jié)果的穩(wěn)定性，重復(fù)以上實(shí)驗(yàn)5 次，取其平均值作為最終的分類(lèi)精度，并與文獻(xiàn)［11］基于決策樹(shù)、單層期望最大化、多層期望最大化、基于隨機(jī)投票的選擇-融合集成、基于CVI 的選擇-融合集成的填充支持向量機(jī)分類(lèi)方法獲得的分類(lèi)精度（依次記為T(mén)JD1、TJD2、TJD3、TJD4 和TJD5）進(jìn)行對(duì)比。實(shí)驗(yàn)對(duì)比結(jié)果如表2所示。

表2 ISVM與填充支持向量機(jī)分類(lèi)方法對(duì)比實(shí)驗(yàn)

從表2 結(jié)果可以看出，Breast-cancer 數(shù)據(jù)集缺失比例從0%增加到30%，ISVM 均獲得了最佳的分類(lèi)精度。Votes 數(shù)據(jù)集的缺失比例從0%增加到10%，ISVM 分類(lèi)精度稍差，但是正確率也在90%以上；缺失比例從20%增加到30%，其優(yōu)勢(shì)則明顯體現(xiàn)出來(lái)。Pima 數(shù)據(jù)集在缺失比例從0%增加到20%時(shí)，ISVM 與填充支持向量機(jī)分類(lèi)方法的分類(lèi)效果差別不大，而缺失比例增加到30%時(shí)，ISVM的優(yōu)勢(shì)也體現(xiàn)出來(lái)。

（2）ISVM 與混合距離支持向量機(jī)分類(lèi)方法對(duì)比實(shí)驗(yàn)分析。選擇表2 中的6 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，對(duì)每個(gè)數(shù)據(jù)集依次隨機(jī)增加0%（原始數(shù)據(jù)集）、10%、20%、30% 的缺失比例，利用ISVM 與缺失值取屬性最小值0 和最大值1 的混合距離支持向量機(jī)分類(lèi)方法進(jìn)行分類(lèi)，以6次交叉檢驗(yàn)獲得的平均精度作為分類(lèi)精度。為了保證結(jié)果的穩(wěn)定性，重復(fù)以上實(shí)驗(yàn)5 次，取其平均值作為最終的分類(lèi)精度進(jìn)行比較。具體對(duì)比結(jié)果見(jiàn)圖1，其中橫軸表示缺失比例，縱軸表示分類(lèi)精度，星號(hào)連線(xiàn)表示ISVM 獲得的結(jié)果，三角形和圓圈連線(xiàn)分別表示缺失值取屬性最小值0和最大值1的混合距離支持向量機(jī)分類(lèi)方法。

圖1 ISVM與混合距離支持向量機(jī)分類(lèi)方法對(duì)比實(shí)驗(yàn)

從圖1 可以看出，實(shí)驗(yàn)的6 個(gè)數(shù)據(jù)集在缺失比例從0%增加到30%過(guò)程中，ISVM 與取極端值的混合距離支持向量機(jī)分類(lèi)效果總體上差別不大，也均保持在相對(duì)較高的分類(lèi)精度。

（3）ISVM 與風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法對(duì)比實(shí)驗(yàn)分析。文獻(xiàn)［21］選擇了一個(gè)公共測(cè)試數(shù)據(jù)集heaptitis，對(duì)經(jīng)典的SVM、CSVM、LS-SVM、CLS-SVM 進(jìn)行風(fēng)險(xiǎn)重構(gòu)，并進(jìn)行分類(lèi)。利用ISVM 進(jìn)行分類(lèi)，以10次交叉檢驗(yàn)獲得的平均分類(lèi)精度作為比較，具體對(duì)比結(jié)果見(jiàn)圖2，其中橫軸方法1-5 依次對(duì)應(yīng)SVM、CSVM、LS-SVM、CLS-SVM風(fēng)險(xiǎn)重構(gòu)方法和ISVM。

圖2 ISVM與風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法對(duì)比實(shí)驗(yàn)

從圖2 可以看出，ISVM 對(duì)比風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法，具有顯著的優(yōu)勢(shì)。

綜上可以看出，本文的分類(lèi)方法是有效的，而且對(duì)比填充支持向量機(jī)分類(lèi)方法、混合距離支持向量機(jī)分類(lèi)方法和風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法，均獲得了優(yōu)異的分類(lèi)效果。值得說(shuō)明的是，本文的分類(lèi)方法沒(méi)有對(duì)缺失值做任何填充處理，也沒(méi)有取極端值或特殊值進(jìn)行代替，完全保證了分類(lèi)數(shù)據(jù)集的客觀真實(shí)性，其分類(lèi)效果也是真實(shí)數(shù)據(jù)集的反映。同時(shí)，本文的分類(lèi)方法沒(méi)有改變經(jīng)典支持向量機(jī)模型的結(jié)構(gòu)和約束條件，可以充分利用現(xiàn)有的支持向量機(jī)研究成果，從而避免了增加應(yīng)用的復(fù)雜性。

4 結(jié)語(yǔ)

本文針對(duì)混合不完備數(shù)據(jù)集，首先給出基于鄰域聯(lián)系度距離拓展定義的高斯核函數(shù)；其次，給出基于二次函數(shù)逼近的支持向量機(jī)SMO訓(xùn)練算法和分類(lèi)算法；最后，取多個(gè)UCI 數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)分析。通過(guò)與填充支持向量機(jī)分類(lèi)方法、取極端值的混合距離支持向量機(jī)分類(lèi)方法和風(fēng)險(xiǎn)重構(gòu)支持向量機(jī)分類(lèi)方法獲得的分類(lèi)精度進(jìn)行比較，實(shí)驗(yàn)結(jié)果顯示本文分類(lèi)方法均獲得了優(yōu)異的分類(lèi)效果。值得說(shuō)明的是，本文的分類(lèi)算法不需要對(duì)缺失值做任何填充處理，也不需要取極端值或特殊值進(jìn)行代替，完全保證了分類(lèi)數(shù)據(jù)集的客觀真實(shí)性，而且沒(méi)有改變經(jīng)典支持向量機(jī)的模型結(jié)構(gòu)和約束條件，避免了增加應(yīng)用的復(fù)雜性，這是對(duì)比的分類(lèi)方法所不具備的優(yōu)勢(shì)。將鄰域聯(lián)系度距離函數(shù)應(yīng)用于更多的核函數(shù)與分類(lèi)、聚類(lèi)模型，以更好地對(duì)不完備數(shù)據(jù)進(jìn)行處理、研究及應(yīng)用，將是我們下一步的主要研究工作。