混合不完備數據的拓展高斯核-支持向量機分類方法

黃恒秋，翁世洲

（1.廣西民族師范學院數理與電子信息工程學院，崇左 532200；2.廣西民族師范學院經濟管理學院，崇左 532200）

0 引言

支持向量機由Cortes 等［1］提出，是機器學習領域中非常重要的一種分類方法，它基于統計學習理論，具有結構風險最小化、魯棒性強、泛化能力佳等優點［2］，已經在模式識別、信號處理、數據挖掘等諸多現實問題中得到廣泛的應用［3-4］。

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

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

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

為了檢驗本文分類算法的有效性，取多個UCI 數據集進行了對比實驗分析。首先，與決策樹、單層期望最大化、多層期望最大化、選擇-融合集成等經典插值填充支持向量機分類方法進行對比；其次與取極端值的混合距離支持向量機分類方法進行對比；最后，與文獻［21］的風險重構支持向量機分類方法進行對比。實驗結果顯示，本文的分類方法獲得了優異的分類效果。

1 支持向量機相關概念

1.1 支持向量機模型

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

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

最后可得到上述最優化問題的最優分類函數：

其中α?為問題（1）的最優解，由（2）式知非支持向量=0，故

其中k為支持向量（α?>0）的個數，即本文中最優分類超平面的偏置量b?取支持超平面偏置量的平均值。

1.2 基于二次函數逼近的支持向量機SMO訓練算法

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

2 混合不完備數據的拓展高斯核-支持向量機分類方法

2.1 鄰域聯系度距離函數

定義1［20］混合距離函數（簡稱HEOM）定義如下：

其中,

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

其中m,g,h記作同一度、差異度和對立度，i*、j*為差異度和對立度標記，起到與同一度區別的作用。

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

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

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

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

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

2.2 基于鄰域聯系度距離擴展高斯核函數的定義

高斯核函數是支持向量機分類問題中應用非常廣泛的一類核函數。本文在傳統的高斯核函數基礎上，給出拓展定義的高斯核函數，用于對混合不完備數據進行處理。

定義4［5］高斯核函數定義如下：

其中，γ為核函數寬度調整參數。從定義可以看出，高斯核函數是關于兩個對象之間距離的函數，其距離為確定距離。下面將給出基于不確定距離——聯系度距離的不確定高斯核函數定義。

定義5基于鄰域聯系度距離拓展定義的高斯核函數如下：

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

2.3 基于二次函數逼近的拓展高斯核-支持向量機SMO訓練算法

算法3 沒有改變二次規劃問題（1）的模型結構和約束條件，還充分利用了文獻［5，6］SMO訓練算法的研究成果，本質上沒有增加求解的復雜性，從而更好地推廣應用到實際問題當中。

2.4 混合不完備數據的拓展高斯核-支持向量機分類方法

傳統支持向量機模型是基于二分類問題，而實際應用中的數據集不僅包括二類，還可能存在多類。下面給出多類（包括二類）混合不完備數據集的支持向量機分類算法。

3 實驗分析

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

表1 實驗數據集基本信息表

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

下面分別討論本文的分類方法（ISVM）與填充支持向量機分類方法、混合距離支持向量機分類方法、風險重構支持向量機分類方法的對比實驗分析。

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

表2 ISVM與填充支持向量機分類方法對比實驗

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

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

圖1 ISVM與混合距離支持向量機分類方法對比實驗

從圖1 可以看出，實驗的6 個數據集在缺失比例從0%增加到30%過程中，ISVM 與取極端值的混合距離支持向量機分類效果總體上差別不大，也均保持在相對較高的分類精度。

（3）ISVM 與風險重構支持向量機分類方法對比實驗分析。文獻［21］選擇了一個公共測試數據集heaptitis，對經典的SVM、CSVM、LS-SVM、CLS-SVM 進行風險重構，并進行分類。利用ISVM 進行分類，以10次交叉檢驗獲得的平均分類精度作為比較，具體對比結果見圖2，其中橫軸方法1-5 依次對應SVM、CSVM、LS-SVM、CLS-SVM風險重構方法和ISVM。

圖2 ISVM與風險重構支持向量機分類方法對比實驗

從圖2 可以看出，ISVM 對比風險重構支持向量機分類方法，具有顯著的優勢。

綜上可以看出，本文的分類方法是有效的，而且對比填充支持向量機分類方法、混合距離支持向量機分類方法和風險重構支持向量機分類方法，均獲得了優異的分類效果。值得說明的是，本文的分類方法沒有對缺失值做任何填充處理，也沒有取極端值或特殊值進行代替，完全保證了分類數據集的客觀真實性，其分類效果也是真實數據集的反映。同時，本文的分類方法沒有改變經典支持向量機模型的結構和約束條件，可以充分利用現有的支持向量機研究成果，從而避免了增加應用的復雜性。

4 結語

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