李詒靖 ,石 詠 ,李亞楠,郭海湘,b,c,2
(中國地質(zhì)大學(xué)1a.經(jīng)濟(jì)管理學(xué)院;1b.數(shù)字化商務(wù)管理研究中心;1c.中國礦產(chǎn)資源戰(zhàn)略與政策研究中心,武漢 430074;2.中南大學(xué) 商學(xué)院,長沙 410083)
支持向量機(jī)(Support Vector Machine,SVM)是一種泛化能力很強(qiáng)的分類器,它在解決小樣本問題方面表現(xiàn)出了許多特有的優(yōu)勢,是一種非常流行的學(xué)習(xí)方法,被廣泛應(yīng)用于文本分類[1]、臉譜識(shí)別[2]、基因方程預(yù)測[3]、機(jī)械故障診斷[4]以及預(yù)測[5]等方面。在運(yùn)用SVM解決問題時(shí),需要提前考慮的是選擇全局學(xué)習(xí)方法還是局部學(xué)習(xí)方法。全局學(xué)習(xí)方法中主要有非線性SVM(SVM直接劃分非線性分類邊界),局部學(xué)習(xí)方法中主要有線性SVM(將非線性分類邊界拆分為若干線性邊界,從而進(jìn)行線性劃分)。運(yùn)用非線性的SVM處理問題主要是通過構(gòu)造復(fù)雜的核函數(shù)實(shí)現(xiàn),其優(yōu)點(diǎn)是直接,但缺點(diǎn)是具體的非線性變換是未知的,因此容易過學(xué)習(xí),并且相關(guān)參數(shù)對具體問題有依賴性。相對而言,線性SVM魯棒性強(qiáng),但分類精度低,所以通常采用多個(gè)線性SVM來保證一定精度并同時(shí)提高泛化能力,這就是多支持向量機(jī)。由于多支持向量機(jī)只訓(xùn)練局部的訓(xùn)練集,故其也被稱為局部SVM。
現(xiàn)有的局部SVM算法很多,最簡單的方法是對每一個(gè)測試樣本用一個(gè)線性SVM來學(xué)習(xí)。Zhang等[13]提出了一種基于KNN的SVM-KNN算法,該算法首先找到測試樣本在訓(xùn)練集中的k個(gè)近鄰,將樣本與其k個(gè)近鄰的距離矩陣轉(zhuǎn)化為核矩陣,再分別用SVM進(jìn)行分類。與SVM-KNN不同,Blanzieri等[15]提出的k NNSVM直接在核空間內(nèi)尋找測試樣本的k個(gè)近鄰,相比SVM-KNN更為簡潔直觀。Cheng等[16]只采用線性核變換,通過計(jì)算測試樣本與訓(xùn)練集中每個(gè)樣本的相似度選取k個(gè)相似度最高的樣本,為測試樣本構(gòu)造SVM模型來分類,Cheng等提出的算法稱為LSVM,并有2個(gè)變種:SLSVM和HLSVM。上述3種局部支持向量機(jī)算法都需要對每一個(gè)測試樣本構(gòu)造SVM模型,當(dāng)測試樣本非常多時(shí),采用上述方法就變得不實(shí)際,缺乏實(shí)用性。為了克服該問題,許多學(xué)者提出了局部SVM的改進(jìn)算法,基本思想都是將訓(xùn)練集中的樣本依據(jù)一定的原則劃分為若干類并找到類中心,對每個(gè)類中心構(gòu)造一個(gè)SVM模型。之后,在對測試樣本進(jìn)行測試時(shí),選擇離測試樣本最近的中心所構(gòu)造的SVM進(jìn)行分類。如圖1所示。改進(jìn)的多支持向量機(jī)中每個(gè)SVM的訓(xùn)練數(shù)據(jù)都是通過聚類方法對訓(xùn)練數(shù)據(jù)進(jìn)行劃分而形成的訓(xùn)練子集,Cheng等提出的PSVM算法,利用加入了平衡正負(fù)樣本因子的Mag Kmeans聚類算法對訓(xùn)練集進(jìn)行聚類;Segate等[14]在其提出的k NNSVM的基礎(chǔ)上,提出了FaLK-SVM算法,在訓(xùn)練集上采用最小覆蓋集的方法來尋找k個(gè)中心;Gu等[12]在每個(gè)聚類中心構(gòu)造的SVM的目標(biāo)函數(shù)中加入了全局支持向量來控制每個(gè)子線性SVM的支持向量與全局支持向量保持一致,通過這種變化,他們提出的CSVM能很好地克服子SVM中的過擬合問題。
圖1 multi-SVM結(jié)構(gòu)圖
在改進(jìn)的多支持向量機(jī)算法中,聚類方法肯定能確保每一個(gè)樣本都?xì)w屬到某一簇中,但該方法無法從分段線性角度來確保最優(yōu)劃分[6]。上述一些改進(jìn)的多支持向量機(jī)算法能夠提高多支持向量機(jī)的時(shí)間復(fù)雜度,但在對訓(xùn)練集聚類時(shí),只有PSVM考慮了如何劃分子集的問題。事實(shí)上,如何劃分子集會(huì)直接關(guān)系到多支持向量機(jī)的表現(xiàn)。子集的劃分至少要考慮兩點(diǎn):①子集包含的訓(xùn)練樣本是否同時(shí)來自不同的2個(gè)類,若訓(xùn)練子集中只包含同一類的樣本,那么構(gòu)造的SVM分類器就不能很好地學(xué)習(xí)到另一類的信息,學(xué)習(xí)的效率降低。PSVM中加入的樣本平衡因子就是為了保證所構(gòu)造的子訓(xùn)練集中正負(fù)樣本的平衡性。②子集的中心盡量靠近不同類別的分離邊界,這是因?yàn)?,?dāng)子集的聚類中心越靠近邊界,子集中包含的正負(fù)樣本數(shù)會(huì)越平衡,這一點(diǎn)在不均衡數(shù)據(jù)分類時(shí)尤其重要。在不均衡數(shù)據(jù)中,少數(shù)類樣本數(shù)量本來就較少,只有子集中心靠近邊界才能盡可能更靠近少數(shù)類樣本,從而訓(xùn)練子集才能最大限度地包含較多的少數(shù)類樣本?;谶@種背景,本文提出了有導(dǎo)師學(xué)習(xí)的k-means聚類方法,即在傳統(tǒng)k-means方法的基礎(chǔ)上加入指導(dǎo)信息,從而盡量滿足子集劃分所要考慮的兩點(diǎn)。
支持向量機(jī)(SVM)是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的一種新的機(jī)器學(xué)習(xí)方法,它是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的[7-8],在解決小樣本、非線性、高維及防止過學(xué)習(xí)模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢[9]。在SVM中,有{X,yi},Xi∈Rn,i=1,2,…,N。Xi為 第i個(gè)輸入向量,yi是類別標(biāo)簽(+1或—1)。輸入的數(shù)據(jù)集分為2個(gè)不同的類別A和B,對應(yīng)的輸出為+1和—1。支持向量為A的{X∈},支持向量為B的{X∈。在非線性數(shù)據(jù)集中需要將數(shù)據(jù)從低維轉(zhuǎn)向高維。高維空間用映射函數(shù)φ(x),構(gòu)造的邊界線為
優(yōu)化邊界的問題變成一個(gè)最優(yōu)化問題:
式中:C為可以調(diào)節(jié)的參數(shù),稱為懲罰因子;ξ為松弛變量。將式(2)表示優(yōu)化問題通過拉格朗日優(yōu)化方法轉(zhuǎn)化為其對偶問題:
式中,αi為拉格朗日乘 子,這里K(Xi,Xj)=φ(Xi)T—φ(Xj)是核函數(shù)。訓(xùn)練后,得到拉格朗日乘子α。如果αi≠0,則對應(yīng)的樣本i就是一個(gè)支持向量。SVM的決策值可以定義為
式中:Xi為訓(xùn)練數(shù)據(jù)中的樣本;X為輸入向量。當(dāng)f(X)S為正值時(shí),樣本X屬于正類,反之屬于負(fù)類。SVM也可以用一種網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行表達(dá),如圖2所示。
圖2 SVM網(wǎng)絡(luò)結(jié)構(gòu)表達(dá)
k-means聚類算法是一種硬聚類方法。即在n維的歐幾里得空間將n個(gè)樣本數(shù)據(jù)分為k類。首先,由用戶確定所要聚類的準(zhǔn)確數(shù)目k,并隨機(jī)選擇k個(gè)對象(樣本),每個(gè)對象稱為一個(gè)種子,代表一個(gè)類的均值或中心,對剩余的每個(gè)對象,根據(jù)其與各類中心的距離將它賦給最近的類。然后重新計(jì)算每個(gè)類內(nèi)對象的平均值形成新的聚類中心,該過程重復(fù)進(jìn)行,直到收斂為止??紤]到n個(gè)樣本(x1,x2,…,xn),每一個(gè)樣本都是d維向量,k-means聚類的目的就是將n個(gè)樣本劃分為k個(gè)集合(k≤n)S={S1,S2,…,Sk},最小化類中距為
式中,mi為第i個(gè)聚類集合中所有樣本的平均值,即類中心。在迭代過程中考慮2個(gè)步驟:
(1)樣本分配。分配樣本到最近類中心的所屬類別,即
(2)更新。計(jì)算聚類樣本集合新的均值,即
由以上介紹可見,傳統(tǒng)的k-means聚類方法只考慮了類中距,這導(dǎo)致在SVM分類學(xué)習(xí)中,同類的樣本通常會(huì)劃到同一類別集合[10],即該類別集合里的樣本標(biāo)簽都為+1,或都為—1,如圖3所示。圖3(a)表示有2類樣本,紅色(+1),藍(lán)色(—1),圖3(b)通過傳統(tǒng)k-means聚類方法進(jìn)行的劃分,很顯然,黑色和綠色樣本點(diǎn)的劃分分別來自同一類,這種劃分導(dǎo)致SVM的學(xué)習(xí)會(huì)出現(xiàn)過學(xué)習(xí)的問題。
本文提出的有導(dǎo)師學(xué)習(xí)的k-means方法是在傳統(tǒng)k-means的基礎(chǔ)上不僅考慮類中距,而且還增加了一些指導(dǎo)信息,這些指導(dǎo)信息的引入能夠保證樣本集合的劃分盡量滿足集合中的樣本來自不同的類別(見圖3(b)中,紅色樣本點(diǎn)集合劃分所示)和劃分集合的中心盡量靠近分界線。
圖3 同類的樣本劃到同一類別集合的例子
傳統(tǒng)的k-means主要考慮類中距目標(biāo),即
式中:Xi為第i個(gè)樣本;Cj為第j個(gè)聚類的類中心;Z為樣本隸屬于各個(gè)聚類的隸屬度矩陣。本文的方法就是加入指導(dǎo)參數(shù)部分放入式(8)中,即
式中:Yi為向量Y(該向量就是對應(yīng)樣本的類別標(biāo)簽)的第i個(gè)元素;λ1>0。隸屬度矩陣Z如表1所示,向量Y如表2所示。在表1中 數(shù)字0和1表示向量Y是否屬于類別C。數(shù)字0表示向量Y不屬于類別C。反之,數(shù)字1表示向量Y屬于類別C。表2中可以看到數(shù)字—1和1,表示向量Y的類別標(biāo)簽,—1表示向量Y是負(fù)的,1表示向量Y是正的。
表1 隸屬度矩陣Z
表2 向量Y
目標(biāo)方程式(9)的第1部分
圖4 基于式(9)的k-means劃分模擬圖
由圖5可見,表示正樣本和負(fù)樣本的點(diǎn)基本相同,但是在局部區(qū)域不均衡,左邊紅色樣本點(diǎn)多于藍(lán)色樣本點(diǎn),中間基本無差,右邊藍(lán)色樣本點(diǎn)多于紅色樣本點(diǎn)。運(yùn)用有導(dǎo)師學(xué)習(xí)基于式(9)的k-means方法后,仿真圖5變?yōu)閳D6。樣本劃分為3個(gè)部分用3種不同的顏色基本上劃分正確,但是每一個(gè)子集的中心用黑點(diǎn)表示,可以清楚地發(fā)現(xiàn),左、右邊子集的中心點(diǎn)并不靠近分離邊界。導(dǎo)致這種原因就是樣本不均衡。
圖5 某區(qū)域樣本不均衡例子
為了解決該問題,需要附加另一種有導(dǎo)師信息,使得劃分的子集不僅考慮類別標(biāo)簽的信息,而且考慮中心的信息。①用標(biāo)簽均衡的改進(jìn)的k-means進(jìn)行劃分類別(即基于式(9));②測量每個(gè)子集中心和對立樣本的最短距離,然后最小化該距離。這保證每個(gè)類在最近正負(fù)樣本之間,目標(biāo)方程為
圖6 基于式(9)的k-means劃分后
式中:Dj為每個(gè)子集到最近的對立樣本的距離;λ2>0。
圖7(a)為不均衡數(shù)據(jù)分布圖,圖7(b)為運(yùn)用k-means方法對不均衡數(shù)據(jù)基于式(8)的仿真圖,圖7(c)為基于式(9)的仿真圖,圖7(d)為基于式(10)的仿真圖。
圖7 基于式(10)的k-means劃分過程圖,不均衡樣本
本文選用UCI數(shù)據(jù)庫[17]中5組不同的二分類數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),分別為Heart、Breast、Liver、Ionosphere和Tic-tac-toe數(shù)據(jù)集,各數(shù)據(jù)集的具體信息如表3所示。實(shí)驗(yàn)選用數(shù)據(jù)集中60%的樣本作為訓(xùn)練集,40%樣本作為測試集,并將本文方法所得的分類正確率與采用RBF核函數(shù)的標(biāo)準(zhǔn)SVM算法和常用的SVM-KNN[13]、Fa LKSVM[14]以 及CSVM[12]3種局部SVM算法進(jìn)行對比,結(jié)果如表4所示。
表3反映出選用的5組數(shù)據(jù)集都存在一定的正負(fù)類樣本數(shù)不均衡的情況,而由表4可以看出,4種multi-SVM算法相比SVM在對這5組數(shù)據(jù)進(jìn)行分類時(shí)分類正確率上均有不同程度的提高,說明采用muiti-SVM的思想可以在一定程度上提高SVM分類器的精度并增強(qiáng)分類器的泛化能力。在4種multi-SVM算法中,本文提出的SkSVM在5組實(shí)驗(yàn)中都能得到與其他3種算法相當(dāng)或更優(yōu)的精度,尤其是在數(shù)據(jù)集不均衡程度較高的情況下(如Breast和Tic-tac-toe數(shù)據(jù)集),SkSVM相比其他3種算法所得的分類正確率要高,說明本文采用有導(dǎo)師學(xué)習(xí)的k-means對訓(xùn)練集進(jìn)行劃分在不均衡數(shù)據(jù)分類時(shí)有很好的效果。
表3 測試數(shù)據(jù)集詳細(xì)信息
表4 5種不同SVM算法的分類正確率對比 %
收集江漢油田某區(qū)塊oilsk81井、oilsk83井及oilsk85井的測井?dāng)?shù)據(jù)如表5~7所示(只列出了部分?jǐn)?shù)據(jù),詳細(xì)數(shù)據(jù)參見文獻(xiàn)[11])。oilsk81油井?dāng)?shù)據(jù)集是江漢油田鄂深8井區(qū)的生產(chǎn)井,2001-12-19開鉆,完鉆日期2002-04-17,完鉆井深3 580 m。數(shù)據(jù)集有31個(gè)樣本,其中,非油層16個(gè)樣本,油層15個(gè)樣本。oilsk83油井?dāng)?shù)據(jù)集是鄂深8井區(qū)的生產(chǎn)井,2002-11-08開鉆,完鉆日期2003-02-11,完鉆井深3 558 m。數(shù)據(jù)集有50個(gè)樣本,其中,非油層31個(gè)樣本,油層19個(gè)樣本。Oilsk85油井?dāng)?shù)據(jù)集是鄂深8井區(qū)的開發(fā)井,數(shù)據(jù)集有65個(gè)樣本,其中,非油層48個(gè)樣本,油層17個(gè)樣本。由表中可知,儲(chǔ)層含油性識(shí)別的測井屬性集合大小為6,即聲波時(shí)差(AC)、中子(CNL)、深測向電阻率(RT)、孔隙度(POR)、含油飽和度(So)和滲透率(PERM)。在該屬性集合中到底哪個(gè)子集(核屬性或者關(guān)鍵屬性)是用來識(shí)別該油區(qū)含油性最優(yōu)且最簡單的屬性組合,運(yùn)用GA-FCM進(jìn)行屬性約簡[5],將GA和FCM進(jìn)行嵌套,GA負(fù)責(zé)遍歷各種屬性組合,而FCM根據(jù)相對應(yīng)的屬性組合進(jìn)行識(shí)別,識(shí)別結(jié)果與目標(biāo)結(jié)果進(jìn)行比較,用識(shí)別正確率來評(píng)價(jià)每個(gè)屬性組合的優(yōu)劣,從而可以得到對該油區(qū)進(jìn)行含油性識(shí)別的最核心屬性組合為聲波時(shí)差(AC)和含油飽和度(So)。本文即選擇聲波時(shí)差和含油飽和度為輸入數(shù)據(jù),輸出數(shù)據(jù)為油層(標(biāo)簽為+1)與非油層(標(biāo)簽為—1)。
表5 oilsk81井測井解釋成果表(只列出部分?jǐn)?shù)據(jù))
表6 oilsk83井測井解釋成果表(只列出部分?jǐn)?shù)據(jù))
表7 oilsk85井測井解釋成果表(只列出部分?jǐn)?shù)據(jù))
本文用有導(dǎo)師學(xué)習(xí)的k-means方法的SkSVM、k-means以及SVM分類方法對江漢油田oilsk81,oilsk83和oilsk85三口井的數(shù)據(jù)進(jìn)行油層和非油層的識(shí)別比較,其中,oilsk81井中隨機(jī)選擇20個(gè)樣本作為訓(xùn)練數(shù)據(jù),11個(gè)樣本作為測試數(shù)據(jù),oilsk83井中隨機(jī)選擇30個(gè)樣本作為訓(xùn)練數(shù)據(jù),20個(gè)樣本作為測試數(shù)據(jù),oilsk85井中隨機(jī)選擇45個(gè)樣本作為訓(xùn)練數(shù)據(jù),20個(gè)樣本作為測試數(shù)據(jù)。k-means+all采用所有屬性作為輸入進(jìn)行k-means分類,k-means+core采用核屬性(聲波時(shí)差和含油飽和度)進(jìn)行k-means分類,其余方法的表達(dá)依此類推。實(shí)驗(yàn)所有的結(jié)果均為50次重復(fù)實(shí)驗(yàn)的平均值。由表8可見,本文提出的SkSVM方法無論是在所有屬性作為輸入還是核屬性作為輸入的條件下,對三口井的油層和非油層的識(shí)別率都是100%,充分說明了Sk SVM方法的魯棒性和容錯(cuò)性比單獨(dú)使用k-means和單獨(dú)使用SVM要好,一定程度上避免了過學(xué)習(xí)的問題。
表8 對oilsk81,oilsk83,oilsk85三口油井的油層和非油層識(shí)別比較 %
本文用一種容錯(cuò)性好、具有全局優(yōu)化功能、帶有指導(dǎo)信息的有導(dǎo)師學(xué)習(xí)的k-means方法對數(shù)據(jù)樣本進(jìn)行劃分,針對每個(gè)劃分建立線性SVM,將一個(gè)復(fù)雜的非線性問題分解為若干線性子問題進(jìn)行求解,從而可以盡量避免過學(xué)習(xí)。SkSVM方法不僅拓展了SVM優(yōu)化理論,同時(shí)也豐富了SVM的應(yīng)用范疇。后續(xù)的研究將k-means的劃分替換為KNN的劃分、AP的劃分以及FCM的劃分等,然后進(jìn)行深入的分析和比較。