金 鑫 葛國青 陸 旭 趙永彬
1(中央財(cái)經(jīng)大學(xué) 北京 100081) 2(國網(wǎng)內(nèi)蒙古東部電力有限公司 內(nèi)蒙古 赤峰 024000) 3(國網(wǎng)遼寧省電力有限公司信息通信分公司 遼寧 沈陽 110006)
隨著網(wǎng)絡(luò)與企業(yè)信息化建設(shè)的發(fā)展,電力、醫(yī)療、金融等行業(yè)往往積累了海量的大數(shù)據(jù),為實(shí)現(xiàn)海量數(shù)據(jù)的核心價(jià)值,發(fā)現(xiàn)海量信息中的隱藏線索,基于大數(shù)據(jù)的全量數(shù)據(jù)挖掘技術(shù)得到快速發(fā)展。但在實(shí)際數(shù)據(jù)分析中,不平衡數(shù)據(jù)的分類問題普遍存在,如電力通信故障診斷、網(wǎng)絡(luò)入侵診斷和信用卡欺詐等。傳統(tǒng)分類問題中,最大化分類準(zhǔn)確率往往基于兩個(gè)假設(shè):1) 訓(xùn)練數(shù)據(jù)集中各類別樣本數(shù)目大致相等;2) 各類樣本的分類錯(cuò)誤代價(jià)大致相等[1]。但在大數(shù)據(jù)背景下,原先的簡化假設(shè)不再成立,采集全量數(shù)據(jù)成為現(xiàn)實(shí),各個(gè)類別數(shù)據(jù)量不再人為選定,而需在更高的層級全貌看待分類問題。若使用傳統(tǒng)的預(yù)測方法會(huì)使海量數(shù)據(jù)中的多數(shù)類數(shù)據(jù)信息淹沒少數(shù)類,致使少數(shù)類數(shù)據(jù)的分類精度非常低。且在多數(shù)情況下,企業(yè)關(guān)注的是不平衡數(shù)據(jù)集中少數(shù)類數(shù)據(jù)及其被誤分帶來的損失。
少數(shù)類樣本被錯(cuò)分的代價(jià)要遠(yuǎn)遠(yuǎn)大于對多數(shù)類樣本的錯(cuò)分代價(jià)。以信用卡欺詐為例,在學(xué)習(xí)過程中即使判定整個(gè)樣本均為良好信用客戶,準(zhǔn)確率也能高達(dá)90%,但這樣的分類毫無意義和價(jià)值[2]。針對該問題,如何設(shè)計(jì)精確的分類器,提高少數(shù)類的分類性能極具現(xiàn)實(shí)意義。
不平衡數(shù)據(jù)最主要特征是少數(shù)類過少,對不平衡數(shù)據(jù)進(jìn)行分類時(shí),如何更高精度地對少數(shù)類進(jìn)行分類成為評價(jià)分類算法模型的關(guān)鍵指標(biāo)。目前不平衡數(shù)據(jù)主要從數(shù)據(jù)層面、模型評價(jià)準(zhǔn)則層面與算法層面三個(gè)層面進(jìn)行研究。
目前,在數(shù)據(jù)層面解決數(shù)據(jù)不平衡問題主要有三類技術(shù):過抽樣、欠抽樣、混合抽樣。其中最具代表性的過抽樣算法是Chawla提出的SMOTE(Synthetic Minority Oversampling Technique),通過改進(jìn)采樣技術(shù),提高了過抽樣的性能[3]。欠抽樣技術(shù)旨在去除部分負(fù)類樣本以達(dá)到平衡數(shù)據(jù)類的目的?;旌铣闃硬捎昧藢⑶烦闃优c過抽樣技術(shù)結(jié)合的思想。事實(shí)已經(jīng)表明,三種技術(shù)均有重大缺陷:欠抽樣算法存在很大的盲目性,會(huì)導(dǎo)致多數(shù)類樣本有效信息丟失;而過采樣由于插值的隨機(jī)性并不能保證新合成的樣本為少數(shù)類,而且有可能導(dǎo)致過適應(yīng)[4]。三類技術(shù)都因?yàn)楦淖兞嗽紨?shù)據(jù)的分布特征而備受爭議。
在傳統(tǒng)的分類學(xué)習(xí)中,分類精度往往傾向于多數(shù)類。但對于不平衡數(shù)據(jù)而言,分類準(zhǔn)確率卻因傾向于多數(shù)類的準(zhǔn)確率而無法準(zhǔn)確評價(jià)對少數(shù)類的分類性能[5-6]。已有學(xué)者研究出新的評價(jià)標(biāo)準(zhǔn),如F-Score、G-mean等。Brefeld等(2005)使用ROC(Receiver Operating Characteristic)曲線的AUC(Area Under Curve)面積作為分類評價(jià)標(biāo)準(zhǔn),科學(xué)準(zhǔn)確地評價(jià)了分類器性能[7]。模型評價(jià)準(zhǔn)則的研究有助于更科學(xué)地評判分類器分類精度,但不能從根本上解決不平衡數(shù)據(jù)的分類問題。因此從算法角度解決不平衡數(shù)據(jù)分類問題尤為重要。
算法層面不平衡數(shù)據(jù)處理的方法主要有代價(jià)敏感性學(xué)習(xí)、單類學(xué)習(xí)和集成學(xué)習(xí)算法等[8]。代價(jià)敏感學(xué)習(xí)基于對少數(shù)類正確分類的價(jià)值高于對多數(shù)類正確分類的價(jià)值的假設(shè),通過改進(jìn)分類器模型的內(nèi)部構(gòu)造,使基于最小錯(cuò)誤率的分類器轉(zhuǎn)化為代價(jià)敏感分類器。在數(shù)據(jù)嚴(yán)重不平衡時(shí),單類學(xué)習(xí)通過只采用感興趣的目標(biāo)類進(jìn)行學(xué)習(xí)來預(yù)防多數(shù)類對少數(shù)類的淹沒問題。集成學(xué)習(xí)通過增加錯(cuò)誤樣本分類的權(quán)值進(jìn)一步改善分類器針對少數(shù)類的分類性能。KSVM是目前比較經(jīng)典的分類器,該算法充分利用機(jī)器學(xué)習(xí)算法SVM,同時(shí)有效結(jié)合了KNN算法。但該分類器閾值的固定導(dǎo)致過多噪聲的引入是亟待解決的問題。本文研究的重點(diǎn)就是通過對KSVM分類器優(yōu)化改進(jìn)來提升對不平衡數(shù)據(jù)的分類預(yù)測性能。
李蓉等[9]首次提出了定理:SVM可以看做每類只有一個(gè)代表點(diǎn)的1NN分類器。并在該定理的基礎(chǔ)之上提出了KSVM算法,主要思想是:由于SVM對每一類只取一個(gè)代表點(diǎn),但往往該點(diǎn)不能很好地代表該類提供充足的有效分類信息,此時(shí)引入KNN分類器,將所有的支持向量作為代表點(diǎn),從中選取近鄰的K(K=2n+1,n=1,2,3,…)個(gè)代表點(diǎn)增加有效分類信息進(jìn)而成功預(yù)測樣本類別。王超學(xué)等指出了KSVM算法的缺陷,并提出了改進(jìn)型算法EDSVM[10]:SVM學(xué)習(xí)訓(xùn)練得出各類別的支持向量,由支持向量數(shù)目確定KNN的K近鄰參數(shù),在特征空間采用KNN算法進(jìn)行分類。
上述KSVM系列算法均建立在閾值ε固定的前提下,忽視了非平衡數(shù)據(jù)下兩類數(shù)據(jù)信息量的差異性,忽略了不同數(shù)據(jù)集的兩類支持向量(SVs+、SVs-)的數(shù)量、分布特征的差異[11]。因此,固定的閾值使得KSVM分類性能受到了限制。本文首先闡述了KSVM系列算法閾值尋優(yōu)的重要性,并在前人基礎(chǔ)之上,利用遺傳算法進(jìn)行閾值尋優(yōu)提出了ε-KSVM算法。通過實(shí)驗(yàn)進(jìn)一步論證了閾值尋優(yōu)應(yīng)用于分類器KSVM是科學(xué)的、有實(shí)踐意義的。
定義1清晰類(ClearData)數(shù)據(jù)集是由到分類超平面的距離大于等于閾值ε的待測樣本點(diǎn)組成。如圖1空間I、II所示。
圖1 超平面與代表點(diǎn)
定義2模糊類(BlurData)數(shù)據(jù)集是由到分類超平面的距離小于閾值ε的待測樣本點(diǎn)組成。如圖1空間III所示。
損失函數(shù)(Loss Function)是用來估量模型預(yù)測值f(x)與真實(shí)值Y的不一致程度的非負(fù)實(shí)值函數(shù)。
SVM分類器的損失函數(shù)可表示為:
(1)
KNN的損失函數(shù)可表示為:
(2)
式中:分類器SVM的y值應(yīng)為分類器決策函數(shù)的“原始”輸出,而不是最終的類標(biāo),即y=w·x+b。對于可能的輸出t=±1,若t與y有相同的符號(意味著y分類預(yù)測正確),則max{0,1-t·y}=0。對于分類器KNN,xi表示待測樣本的真實(shí)類別,ci=f(x)為預(yù)測類別。由此不難得出分類器KSVM的損失函數(shù)為:
Loss=Loss,svm+a·Loss,knn=
(3)
KSVM分類器通過增加易錯(cuò)樣本點(diǎn)的有效分類信息進(jìn)一步提升了分類準(zhǔn)確率。對到分類超平面的距離小于閾值ε的模糊類樣本采用KNN分類器進(jìn)行分類,到分類超平面的距離大于閾值ε時(shí)采用SVM分類器。但閾值選取是否恰當(dāng),對分類超平面附近樣本點(diǎn)(尤其是少數(shù)類樣本)的分類準(zhǔn)確率有很大的影響。
一方面,對于確定的待分類數(shù)據(jù)集,少數(shù)類特征向量數(shù)量少且分布密集時(shí)(見圖2(b))容易發(fā)生分類結(jié)果向多數(shù)類傾斜的情況,即樣本點(diǎn)位于少數(shù)類的支持向量面附近時(shí),SVM以1NN的方式計(jì)算該點(diǎn)最近鄰支持向量,卻因少數(shù)類的支持向量分布過于集中,極易造成負(fù)類噪聲的引入,導(dǎo)致該點(diǎn)的最近近鄰反而是多數(shù)類中的支持向量(SVs-),若此時(shí)將該點(diǎn)歸為ClearData數(shù)據(jù)集并用SVM分類器進(jìn)行分類,致使錯(cuò)分導(dǎo)致Losssvm增大。針對此種情況,需智能地增大閾值ε,將該樣本點(diǎn)歸為BlurData數(shù)據(jù)集采用KNN分類器來獲取更多有效分類信息[12]。
圖2 少數(shù)類分類錯(cuò)誤情形
另一方面,在少數(shù)類支持向量的個(gè)數(shù)明顯低于多數(shù)類支持向量且少數(shù)類支持向量分布稀疏的情況下(見圖2(b)),多數(shù)類支持向量提供的信息量足以淹沒少數(shù)支持量提供的分類信息,此時(shí)若將圖中待測樣本點(diǎn)歸為BlurData采用KNN進(jìn)行分類,由于引入過多噪聲導(dǎo)致錯(cuò)分,造成Lossknn增大。在該情形下,需智能地減小閾值ε,將該樣本點(diǎn)歸為ClearData數(shù)據(jù)集并采SVM分類器來最大限度地降低噪聲的影響。
因此,對分類超平面附近的樣本進(jìn)行分類時(shí),往往需要增加有效分類信息提高分類精度,但增加有效分類信息的同時(shí)往往伴隨著引入更大的噪聲,智能地確定ClearData與BlurData的邊界(即閾值ε),成為進(jìn)一步降低分類“損失”的關(guān)鍵。閾值的選擇應(yīng)該適用于數(shù)據(jù)集以及具體支持向量的數(shù)量與分布特征,而并非采取統(tǒng)一的經(jīng)驗(yàn)閾值。
本文針對KSVM算法應(yīng)用于不平衡數(shù)據(jù)時(shí)的閾值固定的缺陷,提出一種改進(jìn)的隨數(shù)據(jù)集不同動(dòng)態(tài)調(diào)整閾值的ε-KSVM算法。主要思想是:利用分類器KSVM對待測樣本進(jìn)行分類預(yù)測之前,采用遺傳算法尋找最優(yōu)閾值ε*。對于到分類超平面的距離distance≥ε*的待測樣本,歸為清晰類(ClearData);對于distance<ε*的樣本,歸為模糊類(BlurData)。對于清晰類樣本,采用SVM分類器進(jìn)行分類,對于模糊類樣本,需增加有效分類信息,采用KNN分類器進(jìn)行分類,從而提高了分類器樣本的分類精度。ε-KSVM算法具體如下:
Input:訓(xùn)練數(shù)據(jù)集TrainData;測試數(shù)據(jù)集TestData
Output:測試數(shù)據(jù)集中樣本的類別j*(x′)=f(x′)
BEGIN:
Step1:初始化數(shù)據(jù)集ClearData=Φ,BlurData=Φ;
Step2:經(jīng)過對訓(xùn)練集TrainData的學(xué)習(xí)得到SVM的分類超平面g(x)=∑i∈SVαiyik(xi,x)+b*以及支持向量SVs;
Step3:通過遺傳算法尋找最優(yōu)閾值ε*;
Step4:對于測試樣本x′∈TestData,計(jì)算
g(x′)=∑i∈SVαiyik(xi,x′)+b*;
Step4.1:如果|g(x′)|≥ε*,則ClearData=ClearData∪{x′};
Step4.2:如果|g(x′)|<ε*,則BlurData=BlurData∪{x′}
Step5:TestData=TestData-x′;
If (TestData≠Φ),取x′∈TestData,goto Step4; Else goto (Step6)
Step6:
Step6.1:對于x′∈ClearData,利用SVM分類器進(jìn)行分類,得到分類j*(x′)=f(x′);
Step6.2:對于x′∈BlurData,則以所有的支持向量SVs作為x′近鄰樣本,采用KNN對x′進(jìn)行分類。
END
其中,通過遺傳算法進(jìn)行閾值尋優(yōu)過程見2.4節(jié)。
采用遺傳算法進(jìn)行閾值尋優(yōu)。遺傳算法具有隱含的并行性和強(qiáng)大的全局搜索能力,可以在較短的時(shí)間內(nèi)搜索到全局最優(yōu)點(diǎn)。由于遺傳算子、交叉算子的引入,理論上遺傳算法搜索到全局最優(yōu)解的概率為1[13]。
遺傳算法閾值尋優(yōu)過程中,適應(yīng)度函數(shù)指導(dǎo)搜索方向。本文的目的是提高KSVM算法的分類精度,因而采用分類精度(Accuracy,ACC)作為樣本的適應(yīng)度函數(shù)Fitness,表示如下:
(4)
將遺傳算法應(yīng)用于KSVM閾值優(yōu)化過程,算法的基本步驟如下:
BEGIN:
Step1:初始化種群,隨機(jī)選擇種群個(gè)體P(ε);
Step2:將種群中各個(gè)體P(ε)代入適應(yīng)度函數(shù)Fitness(ε),以訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)對其進(jìn)行訓(xùn)練和測試[14];
Step3:依據(jù)適應(yīng)度計(jì)算準(zhǔn)則,計(jì)算個(gè)體適應(yīng)度函數(shù)值;
Step4:若種群中最優(yōu)個(gè)體所對應(yīng)的適應(yīng)度函數(shù)值足夠大或者算法已連續(xù)運(yùn)行多代,且個(gè)體的最佳適應(yīng)度無明顯改進(jìn)則退出循環(huán),得到優(yōu)化閾值ε*;否則,繼續(xù)下一步Step5;
Step5:應(yīng)用輪盤賭方式的選擇算子[15],按照最優(yōu)保存、最差取代的原則,從P(ε)中選擇出下一代;
Step6:執(zhí)行交叉算子和變異算子,交叉概率取0.7,變異算子取0.1,形成新個(gè)體;
END
為了在不平衡數(shù)據(jù)的分類中更好地發(fā)揮支持向量機(jī)(SVM)的學(xué)習(xí)能力,選取粒子群優(yōu)化算法PSO(Particle Swarm Optimization)對SVM的懲罰參數(shù)C以及RBF核函數(shù)的參數(shù)gamma進(jìn)行優(yōu)化。粒子群算法PSO是一種基于群智能啟發(fā)式全局隨機(jī)優(yōu)化算法,通過信息共享機(jī)制模擬鳥群的捕食行為來尋找最優(yōu)解。粒子群算法尋優(yōu)參數(shù)C、gamma流程如圖3所示。
圖3 PSO尋優(yōu)C、gamma過程
為驗(yàn)證算法的有效性,從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫選取了不平衡程度、屬性維度、樣本數(shù)量互不相同的8組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),并且數(shù)據(jù)來源于電信、能源、醫(yī)療三個(gè)不同行業(yè),數(shù)據(jù)集基本信息如表1所示。本文使用綜合考慮查準(zhǔn)率、查全率的F-Score、GMean作為分類評價(jià)指標(biāo),F(xiàn)-Score衡量分類器對少數(shù)類的分類性能,GMean衡量數(shù)據(jù)集整體的分類性能[16]。
表1 數(shù)據(jù)集基本信息
續(xù)表1
F-Score、GMean推導(dǎo)過程如下:
(5)
(6)
(7)
(8)
式中:TPR為真“正類”率,TNR為真“負(fù)類”率。Precision與Recall分別為查準(zhǔn)率、查全率。F-Score是綜合查全率和查準(zhǔn)率的分類評價(jià)指標(biāo),GMean是保證多數(shù)類、少數(shù)類精度平衡的情況下最大化兩類精度的評價(jià)指標(biāo)。F-Score、GMean二者在對不平衡數(shù)據(jù)分類的評價(jià)上更加科學(xué)。
實(shí)驗(yàn)在Windows環(huán)境下的MATLAB軟件上運(yùn)行,通過編寫分類器ε-KSVM與遺傳算法來進(jìn)行閾值尋優(yōu)。為了保證實(shí)驗(yàn)不受SVM核函數(shù)選擇上的影響,統(tǒng)一選擇徑向基函數(shù)(RBF kernel)。通過10折交叉驗(yàn)
證(10-fold cross validation)重復(fù)實(shí)驗(yàn)。本文對比了KNN、SVM、KSVM、ε-KSVM幾種算法在評價(jià)準(zhǔn)則F-score、GMean上的優(yōu)劣程度。其中KNN算法采用了K=3、K=5兩種,KSVM算法使用的是前人固定的經(jīng)驗(yàn)值ε=0.8。得到了8組不平衡數(shù)據(jù)的最優(yōu)閾值ε以及6種算法的F-Score、GMean。
從表2可知,8組數(shù)據(jù)的最優(yōu)閾值沒有統(tǒng)一的規(guī)律可尋,沒有采用前人所采取的經(jīng)驗(yàn)閾值0.8附近,而是針對不同的數(shù)據(jù)集獲取不同的最優(yōu)閾值。實(shí)驗(yàn)驗(yàn)證了ε-KSVM閾值尋優(yōu)思想的正確性。
表2 8組數(shù)據(jù)的最優(yōu)閾值
表3、表4給出了評價(jià)結(jié)果值(括號內(nèi)為多次交叉驗(yàn)證的標(biāo)準(zhǔn)差),結(jié)果顯示KNN(K=3)與KNN(K=5)的分類效果相差不大,KSVM系列算法(包括KSVM、BDKSVM算法在內(nèi))分類效果好于KNN、SVM算法。ε-KSVM的分類效果要優(yōu)于KNN、KSVM、BDKSVM。從F-Score、G-Mean的實(shí)驗(yàn)結(jié)果不難看出,改進(jìn)的分類器ε-KSVM整體分類精度優(yōu)于其他幾種算法。
表3 F-Score對比值
表4 G-Mean對比值
綜合上述結(jié)果,通過遺傳算法進(jìn)行閾值優(yōu)化來提高對不平衡數(shù)據(jù)的分類精度是有效的。本文提出的閾值尋優(yōu)ε-KSVM分類器,對提高不平衡數(shù)據(jù)樣本尤其是少數(shù)類的分類精度有顯著效果。
在對電力、能源、醫(yī)療等行業(yè)數(shù)據(jù)分析的過程中,普遍存在數(shù)據(jù)分類不平衡問題,本文針對具體不同的不平衡數(shù)據(jù)集,提出了一種動(dòng)態(tài)適應(yīng)不同數(shù)據(jù)集的ε-KSVM分類器。該分類器利用遺傳算法尋找分類器最優(yōu)閾值ε*,調(diào)整SVM、KNN算法對待測數(shù)據(jù)集的應(yīng)用范圍,降低了對少數(shù)類分類時(shí)易被多數(shù)類覆蓋的風(fēng)險(xiǎn),改善少數(shù)類樣本的分類預(yù)測精度的同時(shí)也降低了對多數(shù)類的錯(cuò)分。與前人的KSVM系列分類器相比,本文提出的ε-KSVM算法在處理不平衡分類問題時(shí)性能更加優(yōu)越。實(shí)驗(yàn)進(jìn)一步驗(yàn)證了該算法的有效性,也為不平衡二分類問題提供了一個(gè)嶄新的視角,該思想可以應(yīng)用在電力通信故障檢測、疾病診斷、信用卡欺詐等諸多實(shí)際問題中。
[1] 王瑞.針對類別不平衡和代價(jià)敏感分類問題的特征選擇和分類算法[D].中國科學(xué)技術(shù)大學(xué),2013.
[2] 曾瑾.信用卡欺詐風(fēng)險(xiǎn)的防控[J].國際金融,2012(11):26-33.
[3] Chawla N V,Hall L O,Bowyer K W,et al.SMOTE:Synthetic minority oversampling technique[J].Journal of Artificial Intelligence Research,2002,16:321-357.
[4] Barandela R.Restricted decontamination for the imbalance training sample problem[C]//Proceeding of the 8th Ibero-american Congress on pattern Recognition,Havana,2003:424-431.
[5] Van Hulse J,Khoshgoftaar T M.Knowledge discovery from imbalanced and noisy data[J].Data & Knowledge Engineering,2009(68):1513-1542.
[6] 翟云,楊炳儒,曲武.不平衡類數(shù)據(jù)挖掘研究綜述[J].計(jì)算機(jī)科學(xué),2010,37(10):27-32.
[7] Brefeld U,Scheffer T.AUC maximizing support vector learning[C]//Proceedings of 22nd International Conference on Machine Learning Workshop on ROC Analysis in Machine Learning,2005.
[8] 王金華,喻輝.基于KNN+層次SVM的文本自動(dòng)分類技術(shù)[J].計(jì)算機(jī)應(yīng)用與軟件,2016,33(2):38-41.
[9] 李蓉,葉世偉,史忠植.SVM-KNN分類器-一種提高SVM分類精度的新方法[J].電子學(xué)報(bào),2002,30(5):745-748.
[10] 王超學(xué),張濤,馬春森.改進(jìn)SVM-KNN的不平衡數(shù)據(jù)分類[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(4):51-55.
[11] Ganganwar V.An overview of classification algorithms for imbalanced datasets[J].International Journal of Emerging Technology and Advanced Engineering,2012(4):42-47.
[12] Geng X,Arnold A,Qin T,et al.Query dependent ranking using K-nearest neighbor[C]//Annual ACM Conference on Research and Development in Information Retrieval,Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,2008:115-122.
[13] 顏曉娟,龔仁喜,張千鋒.優(yōu)化遺傳算法尋優(yōu)的SVM在短期風(fēng)速預(yù)測中的應(yīng)用[J].電力系統(tǒng)保護(hù)與控制,2016,44(9):38-42.
[14] 萬源,童恒慶,朱映映.基于遺傳算法的多核支持向量機(jī)的參數(shù)優(yōu)化[J].武漢大學(xué)學(xué)報(bào),2012,58(3):255-259.
[15] 楊平,鄭金華.遺傳選擇算子的比較與研究[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(15):59-64.
[16] 林志勇,郝志峰,楊曉偉.若干評價(jià)準(zhǔn)則對不平衡數(shù)據(jù)學(xué)習(xí)的影響[J].華南理工大學(xué)學(xué)報(bào),2010,38(4):147-154.