梁禮明， 郭 凱， 盛校棋

(江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院， 贛州 341000)

支持向量機(jī)(support vector machine，SVM)作為機(jī)器學(xué)習(xí)的重要組成部分，它通過(guò)利用數(shù)據(jù)間的角度與距離來(lái)表示映射到高維空間的數(shù)據(jù)，避免了“維數(shù)災(zāi)難”的問(wèn)題，同時(shí)它還兼?zhèn)湎∈杈仃嚨奶匦?。但核函?shù)所具備的稀疏矩陣的特性較為簡(jiǎn)單，在處理重疊子空間[1]問(wèn)題時(shí)仍顯不足。當(dāng)下核函數(shù)的研究主要在尋找更多適合不同特征關(guān)系的核函數(shù)，這樣的方法并沒(méi)有改變交叉空間數(shù)據(jù)點(diǎn)之間的關(guān)系。

文獻(xiàn)[2]將隨機(jī)核函數(shù)與線性核函數(shù)進(jìn)行結(jié)合，研究出了線性隨機(jī)核大大提高了運(yùn)算速度，同時(shí)使得核函數(shù)可以滿足訓(xùn)練樣本遠(yuǎn)遠(yuǎn)小于樣本量。該文還指出特征在運(yùn)算中的重要性，但是并沒(méi)有對(duì)特征的權(quán)重進(jìn)行研究。文獻(xiàn)[3-4]分別提出了模糊相似度量的核函數(shù)的構(gòu)造與孿生核函數(shù)的研究，這兩種方法只是對(duì)特征集合的描述進(jìn)行了改變，只是增大或減小了每?jī)蓚€(gè)數(shù)據(jù)點(diǎn)間關(guān)系并沒(méi)有根據(jù)數(shù)據(jù)特征的特性對(duì)數(shù)據(jù)進(jìn)行優(yōu)化改變。

基于以上核函數(shù)優(yōu)化的不足，提出一種將聚類算法與分類算法結(jié)合的方法來(lái)優(yōu)化核函數(shù)。該方法引入了對(duì)特征子空間加權(quán)處理的方法，針對(duì)不同類別、不同特征的區(qū)分度，對(duì)樣本數(shù)據(jù)進(jìn)行特征子空間加權(quán)處理，改變部分?jǐn)?shù)據(jù)點(diǎn)間的關(guān)系，縮小了數(shù)據(jù)點(diǎn)之間的重疊空間。同時(shí)利用優(yōu)化的稀疏條件下的重疊子空間聚類算法[1]，將數(shù)據(jù)集中同類數(shù)據(jù)間隔稠密化和不同類別數(shù)據(jù)間隔稀疏化以達(dá)到提高核函數(shù)泛化能力和學(xué)習(xí)能力。該方法融合稀疏矩陣的數(shù)據(jù)稀疏化特性、子空間[5-6]的不同類別以及不同數(shù)據(jù)特征空間的規(guī)劃能力，對(duì)各種核函數(shù)的學(xué)習(xí)能力與泛化能力得到顯著提升，能夠獲得較好的分類效果。

1 理論基礎(chǔ)

1.1 核函數(shù)

核函數(shù)的構(gòu)造需要滿足Mercer定理[7]，而Mercer定理主要是通過(guò)核函數(shù)確定核矩陣的要求。

定理1(Mercer定理)要保證Frobenius范數(shù)下的對(duì)稱函數(shù)K(xi,xj)為正數(shù)ak>0，將對(duì)稱函數(shù)展開(kāi)為

(1)

SVM在獲得分類標(biāo)簽時(shí)，使用的決策函數(shù)為

(2)

式(2)中：αi、b是通過(guò)求解式(3)最優(yōu)化問(wèn)題獲取的；yi表示數(shù)據(jù)xi的對(duì)應(yīng)標(biāo)簽。

(3)

由式(1)可知，φ(xi)φ(xj)描述的是將低維空間映射到高維空間數(shù)據(jù)點(diǎn)間的表達(dá)方式，進(jìn)一步可以轉(zhuǎn)化為K(xi,xj)，利用數(shù)據(jù)特征空間數(shù)據(jù)間內(nèi)積或者距離關(guān)系通過(guò)函數(shù)的關(guān)系達(dá)到能夠反映高維數(shù)據(jù)空間關(guān)系的形式。常用核函數(shù)類型有：①以距離為衡量標(biāo)準(zhǔn)的核函數(shù),如高斯核函數(shù)、二次有理核、多元二次核和逆多元二次核等；②以內(nèi)積為衡量標(biāo)準(zhǔn)的核函數(shù)，如線性核函數(shù)、多項(xiàng)式核函數(shù)等。

研究表明以距離為主的核函數(shù)實(shí)用性相較于以內(nèi)積為主的核函數(shù)在現(xiàn)實(shí)生活中泛化性和學(xué)習(xí)性更強(qiáng)[8]。以距離為主的核函數(shù)與聚類算法相似，依靠計(jì)算數(shù)據(jù)點(diǎn)間的距離的遠(yuǎn)近來(lái)進(jìn)行預(yù)測(cè)分類，因此將兩者結(jié)合在一起是可行的。

1.2 加權(quán)特征子空間

1.2.1 特征子空間重疊率描述

對(duì)于一組數(shù)據(jù)集每一個(gè)類別空間可以看作一個(gè)子空間，每一個(gè)數(shù)據(jù)的特征也可以看作一個(gè)特征子空間。利用超球體的思想將不同類別、不同特征的數(shù)據(jù)建立超球體模型，以最小超球體間的交叉范圍來(lái)計(jì)算空間的重疊率[9]。

超球體描述的目標(biāo)函數(shù)為

(4)

式(4)中：a為球心；R為超球體半徑；C為懲罰參數(shù)；ζi為松弛變量。

利用建立的不同類別及特征超球體的球心及半徑計(jì)算相同特征下不同類別的超球體的交叉體積與公共體積。其空間重疊描述為[10]

(5)

式(5)中：Q為重疊率；L1,i為類別1在缺少特征i中所占空間；L2,i為標(biāo)簽2在缺少特征i空間中所占空間；FC為L(zhǎng)1,i與L2,i的交叉空間；FA為L(zhǎng)1,i的空間；FB為L(zhǎng)2,i的空間長(zhǎng)度。式(2)與文獻(xiàn)[11]文本特征重要度相似，是利用特征的重疊率初步評(píng)估特征的重要程度的度量。

1.2.2 特征子空間信息熵描述

對(duì)于任意數(shù)據(jù)集(x1,x2,…,xn)T，其用每一列特征可以表示為(T1,T2,…,Tn)， 經(jīng)過(guò)對(duì)每一列特征加權(quán)可以表示為(ω1T1,ω2T2,…,ωnTn)。確定每一特征的加權(quán)系數(shù)是特征加權(quán)的重中之重，采用空間重疊率與信息熵的結(jié)合使用。

信息熵H的大小決定數(shù)據(jù)的有序程度，信息熵H的數(shù)值越接近0說(shuō)明數(shù)據(jù)的有序程度越高，相反信息熵的數(shù)值越大說(shuō)明數(shù)據(jù)的有序程度越低[12]，因此通過(guò)信息熵的大小判斷數(shù)據(jù)的有序程度可以進(jìn)一步說(shuō)明該組數(shù)據(jù)在分類中占的重要性。信息熵H的計(jì)算公式如式(6)所示：

(6)

式(6)中：pi為數(shù)據(jù)(x1,x2,…,xn)T的輸出概率函數(shù)。

1.2.3 特征子空間加權(quán)

對(duì)數(shù)據(jù)集的樣本特征Ti設(shè)置權(quán)值：

(7)

最后，對(duì)所有所有的特征子空間權(quán)值歸一化，即

(8)

1.3 加權(quán)混合范數(shù)的距離空間模型

1.3.1 距離模型

數(shù)據(jù)點(diǎn)間距離的表達(dá)方式來(lái)作為衡量分類的一類重要標(biāo)準(zhǔn)，在分類實(shí)驗(yàn)中常用的是明可夫斯基距離(Minkowski distance)[13]。設(shè)數(shù)據(jù)點(diǎn)P(x1,x2,…,xn)T和Q(y1,y2,…,yn)T∈Rn那么，明可夫斯基距離可以表示為

(9)

式(9)中：d為數(shù)據(jù)點(diǎn)P、Q間的明科夫斯基距離。

在傳統(tǒng)的核函數(shù)中對(duì)數(shù)據(jù)點(diǎn)間的描述主要以Frobenius范數(shù)與數(shù)據(jù)點(diǎn)間的內(nèi)積為主，結(jié)合SVM與稀疏矩陣的思想，提出一種混合范數(shù)的特征子空間模型，目的是在保障類間間距稀疏性的同時(shí)增加類內(nèi)間距的緊密性。對(duì)于一個(gè)訓(xùn)練樣本數(shù)據(jù)，其中包含N個(gè)特征，M個(gè)數(shù)據(jù)點(diǎn)，利用核函數(shù)在表示數(shù)據(jù)點(diǎn)之間的關(guān)系時(shí)組成一個(gè)M×M矩陣，該矩陣為一個(gè)對(duì)稱矩陣同時(shí)也是個(gè)正定矩陣。引入L1范數(shù)來(lái)增加矩陣間的稀疏性，具體距離表示模型可表示為

(10)

1.3.2 加權(quán)方式

在處理數(shù)據(jù)問(wèn)題時(shí)，由于數(shù)據(jù)的復(fù)雜多樣化的問(wèn)題，只是引入L1正則化來(lái)保障核矩陣的稀疏性其效果并不是很理想。文獻(xiàn)[14-15]提出對(duì)L1正則化加權(quán)的方法，通過(guò)迭代更新的方法對(duì)L1范數(shù)進(jìn)行改變，并且通過(guò)大量實(shí)驗(yàn)證明了該方法優(yōu)于單獨(dú)使用L1范數(shù)的效果，能夠得到更具有稀疏性的核矩陣，使得L1更逼近L0。通過(guò)式(11)進(jìn)行求解[16]:

(11)

式(11)中：δ為控制參數(shù)；A為由已知數(shù)據(jù)求向量平均值確定的向量矩陣；c為給定的限制參數(shù)。

其加權(quán)方式為

(12)

式(10)可以表示為

(13)

2 實(shí)驗(yàn)仿真與分析

支持向量機(jī)核函數(shù)分類算法流程如圖1所示。實(shí)驗(yàn)仿真數(shù)據(jù)均來(lái)自UCI(UC Irvine machine learning repository)數(shù)據(jù)庫(kù)，并且每組數(shù)據(jù)均帶標(biāo)簽。SVM分類器應(yīng)用Lib-SVM工具箱，仿真環(huán)境運(yùn)用MATLAB R2018a，運(yùn)行于Intel (R) Core (TM) i5-7200U/2.50 GHz、8 GB內(nèi)存的計(jì)算機(jī)。實(shí)驗(yàn)隨機(jī)選取每組樣本的80%為訓(xùn)練樣本，其余20%為測(cè)試樣本。

圖1 支持向量機(jī)核函數(shù)分類流程圖Fig.1 Support vector machine kernel function classification flow chart

2.1 建立加權(quán)特征子空間

在UCI數(shù)據(jù)庫(kù)中隨機(jī)抽取一組數(shù)據(jù)實(shí)驗(yàn)，該數(shù)據(jù)為User Knowledge Modeling Data Set，即學(xué)生對(duì)直流電機(jī)的知識(shí)水平數(shù)據(jù)集，數(shù)據(jù)集STG表示目標(biāo)對(duì)象素材的學(xué)習(xí)時(shí)間輸入值，SCG表示目標(biāo)對(duì)象用戶重復(fù)次數(shù)輸入值，STR表示與目標(biāo)對(duì)象相關(guān)的用戶學(xué)習(xí)時(shí)間輸入值，LPR表示與目標(biāo)對(duì)象相關(guān)的用戶考試成績(jī)輸入值，PEG表示用戶對(duì)目標(biāo)對(duì)象的考試成績(jī)輸入值，UNS表示用戶知識(shí)水平目標(biāo)值。

首先對(duì)樣本數(shù)據(jù)進(jìn)行歸一化處理，使得各個(gè)數(shù)據(jù)點(diǎn)的各特征值小于1，并保證各特征間的相對(duì)關(guān)系；然后利用式(4)、式(5)對(duì)各特征進(jìn)行重疊空間描述；再根據(jù)式(6)～式(8)與各特征重疊空間的關(guān)系對(duì)樣本數(shù)據(jù)進(jìn)行加權(quán)處理；最后通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析建立加權(quán)特征子空間的必要性與可行性，具體的實(shí)驗(yàn)內(nèi)容及數(shù)據(jù)如表1所示。

表1 數(shù)據(jù)集各特征空間的重疊率、方差和加權(quán)比例Table 1 Overlap rate, variance and weighted ratio of each feature space of the data set

從表1可知，無(wú)論是信息熵還是空間重疊率特征PEG的數(shù)值最低，即特征PEG在數(shù)據(jù)分類的過(guò)程起到了比較重要的作用。

2.2 距離矩陣的建立與仿真測(cè)試

該實(shí)驗(yàn)以評(píng)估對(duì)稱距離矩陣內(nèi)的重復(fù)率進(jìn)行評(píng)估對(duì)核函數(shù)的影響。通過(guò)引入L1范數(shù)減少了矩陣內(nèi)部元素的重復(fù)率，同時(shí)增加數(shù)據(jù)點(diǎn)間的距離，進(jìn)一步增加了核矩陣的稀疏性，使得大部分?jǐn)?shù)據(jù)更接近0，增大了數(shù)據(jù)間的區(qū)分度。在UCI中隨機(jī)抽取四組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析。各數(shù)據(jù)集分類結(jié)果對(duì)比如表2所示。

表2 各數(shù)據(jù)集分類結(jié)果對(duì)比Table 2 Comparison of classification results of each data set

通過(guò)實(shí)驗(yàn)仿真可知，對(duì)于核函數(shù)中引入L1范數(shù)可以減少距離數(shù)據(jù)的重復(fù)率，同時(shí)可以增加類內(nèi)間距的緊密型和類間間距的稀疏性，以達(dá)到更好的泛化效果。為了更好地闡釋核函數(shù)通過(guò)引入L1范數(shù)能夠更好地增強(qiáng)核函數(shù)的泛化性，通過(guò)對(duì)部分以距離為衡量標(biāo)準(zhǔn)的核函數(shù)進(jìn)行研究，同時(shí)對(duì)引入L1范數(shù)的輸入距離矩陣進(jìn)行分析，來(lái)說(shuō)明該方法的可行性與有效性。

從圖2分析可知，以距離為主要評(píng)判方式的核函數(shù)(如高斯核函數(shù)、二次有理核核函數(shù)和逆多元二次核函數(shù)等)，隨著距離的增加該距離所對(duì)應(yīng)的核矩陣的數(shù)值越接近0。

圖2 核函數(shù)特性比較Fig.2 Kernel property comparison

圖3 引入L1范數(shù)距離變化Fig.3 Introducing L1 norm distance variation

圖3(a)、圖3(b)分別為同一數(shù)據(jù)集同類標(biāo)簽類內(nèi)特征距離和不同類標(biāo)簽特征距離經(jīng)過(guò)引入L1范數(shù)距離變化的情況分析圖。由圖3可知，通過(guò)引入L1范數(shù)使得類內(nèi)、類間距離均得到提高，但是類內(nèi)間距提升的幅度較小，而類間間距變化較大。所以通過(guò)引入L1范數(shù)能夠有效地提升數(shù)據(jù)類內(nèi)緊密型和類間稀疏性的特點(diǎn)。再與以距離為分類手段的核函數(shù)，該類核函數(shù)可以通過(guò)增大距離的方式來(lái)達(dá)到核矩陣稀疏化的目的，進(jìn)而達(dá)到拉大同類數(shù)據(jù)與異類數(shù)據(jù)的距離關(guān)系，從而可以提高核函數(shù)的學(xué)習(xí)能力與泛化能力。

2.3 樣本數(shù)據(jù)對(duì)比分析

隨機(jī)選取文獻(xiàn)[5，17]中所用的數(shù)據(jù)集進(jìn)行對(duì)比試驗(yàn)，數(shù)據(jù)集包括：Breast Cancer Wisconsin、Fisheriris Data Set、Wine Data Set、Heart Disease Data Set、Indian Liver Patient Data Set、Australian Credit Approval Data Set六組，對(duì)六組數(shù)據(jù)分別進(jìn)行特征子空間的加權(quán)處理與引入L1范數(shù)的稀疏化處理。分類結(jié)果采用5次實(shí)驗(yàn)取平均值的方式與文獻(xiàn)[5,17]的分類結(jié)果進(jìn)行對(duì)比，結(jié)果如表3所示。

通過(guò)與其他文獻(xiàn)的分類效果以及利用經(jīng)過(guò)優(yōu)化與非優(yōu)化的二次有理核的分類結(jié)果對(duì)比分析。從核函數(shù)的角度分析，RBF核函數(shù)相對(duì)于二次有理核函數(shù)有較大的優(yōu)勢(shì)，如何選擇正確的核函數(shù)對(duì)實(shí)驗(yàn)的結(jié)果起到一定作用；從核函數(shù)內(nèi)部間分析，經(jīng)過(guò)本文算法優(yōu)化過(guò)的核函數(shù)能夠顯著地提高核函數(shù)的分類效果，無(wú)論是在RBF核函數(shù)間的對(duì)比，還是在二次有理核函數(shù)間的對(duì)比，本文算法在一定程度上提高了核函數(shù)的分類準(zhǔn)確率。從理論上分析，對(duì)一組數(shù)據(jù)中的各個(gè)特征進(jìn)行了挖掘，利用科學(xué)的手段對(duì)不同特征對(duì)分類結(jié)果的影響進(jìn)行了分析，更進(jìn)一步使得核函數(shù)挖掘出數(shù)據(jù)潛在的信息，進(jìn)而提高分類準(zhǔn)確率。同時(shí)，還引入了L1范數(shù)，使得同類數(shù)據(jù)間更加緊密，異類數(shù)據(jù)間更加稀疏，增大了數(shù)據(jù)間的可區(qū)分性，進(jìn)而提高了分類效果，增強(qiáng)了核函數(shù)的學(xué)習(xí)能力與泛化能力。

表3 本文算法與其他文獻(xiàn)分類效果對(duì)比Table 3 Comparison of the classification effect between the proposed algorithm and other documents

3 結(jié)論

利用特征子空間加權(quán)的方式，較好地解決了特征對(duì)分類決策的影響不明確的問(wèn)題，使得核函數(shù)能夠更好地挖掘數(shù)據(jù)集一些潛在的關(guān)系。為充分發(fā)揮數(shù)據(jù)本身的價(jià)值屬性，針對(duì)一些以距離為主要衡量標(biāo)準(zhǔn)的核函數(shù)進(jìn)行的優(yōu)化與改進(jìn)，通過(guò)引入L1范數(shù)使得數(shù)據(jù)輸入空間距離得到一定程度的擴(kuò)大。同時(shí)由于類內(nèi)間距與類間間距不同的變化效果達(dá)到稀疏化核矩陣的目的，使得類內(nèi)間距與類間間距的重合率更小，同時(shí)類間部分核矩陣數(shù)值更接近0。通過(guò)仿真實(shí)驗(yàn)證明該方法的可行性和有效性。本文算法融合核函數(shù)、稀疏矩陣與特征加權(quán)等有效地提升核函數(shù)的學(xué)習(xí)能力與泛化能力，但是在一些數(shù)據(jù)集中仍存在不小的交叉空間距離，這樣的交叉空間是優(yōu)化核函數(shù)的主要矛盾之一，故下一步主要研究如何減少距離空間的重疊率。