金 鑫 葛國青 陸 旭 趙永彬

1(中央財經大學 北京 100081) 2(國網內蒙古東部電力有限公司 內蒙古 赤峰 024000) 3(國網遼寧省電力有限公司信息通信分公司 遼寧 沈陽 110006)

0 引 言

隨著網絡與企業(yè)信息化建設的發(fā)展，電力、醫(yī)療、金融等行業(yè)往往積累了海量的大數(shù)據(jù)，為實現(xiàn)海量數(shù)據(jù)的核心價值，發(fā)現(xiàn)海量信息中的隱藏線索，基于大數(shù)據(jù)的全量數(shù)據(jù)挖掘技術得到快速發(fā)展。但在實際數(shù)據(jù)分析中，不平衡數(shù)據(jù)的分類問題普遍存在，如電力通信故障診斷、網絡入侵診斷和信用卡欺詐等。傳統(tǒng)分類問題中，最大化分類準確率往往基于兩個假設：1) 訓練數(shù)據(jù)集中各類別樣本數(shù)目大致相等；2) 各類樣本的分類錯誤代價大致相等[1]。但在大數(shù)據(jù)背景下，原先的簡化假設不再成立，采集全量數(shù)據(jù)成為現(xiàn)實，各個類別數(shù)據(jù)量不再人為選定，而需在更高的層級全貌看待分類問題。若使用傳統(tǒng)的預測方法會使海量數(shù)據(jù)中的多數(shù)類數(shù)據(jù)信息淹沒少數(shù)類，致使少數(shù)類數(shù)據(jù)的分類精度非常低。且在多數(shù)情況下，企業(yè)關注的是不平衡數(shù)據(jù)集中少數(shù)類數(shù)據(jù)及其被誤分帶來的損失。

少數(shù)類樣本被錯分的代價要遠遠大于對多數(shù)類樣本的錯分代價。以信用卡欺詐為例，在學習過程中即使判定整個樣本均為良好信用客戶，準確率也能高達90%，但這樣的分類毫無意義和價值[2]。針對該問題，如何設計精確的分類器，提高少數(shù)類的分類性能極具現(xiàn)實意義。

1 相關工作及存在的問題

不平衡數(shù)據(jù)最主要特征是少數(shù)類過少，對不平衡數(shù)據(jù)進行分類時，如何更高精度地對少數(shù)類進行分類成為評價分類算法模型的關鍵指標。目前不平衡數(shù)據(jù)主要從數(shù)據(jù)層面、模型評價準則層面與算法層面三個層面進行研究。

1.1 數(shù)據(jù)層面解決方案

目前，在數(shù)據(jù)層面解決數(shù)據(jù)不平衡問題主要有三類技術：過抽樣、欠抽樣、混合抽樣。其中最具代表性的過抽樣算法是Chawla提出的SMOTE(Synthetic Minority Oversampling Technique)，通過改進采樣技術，提高了過抽樣的性能[3]。欠抽樣技術旨在去除部分負類樣本以達到平衡數(shù)據(jù)類的目的。混合抽樣采用了將欠抽樣與過抽樣技術結合的思想。事實已經表明，三種技術均有重大缺陷：欠抽樣算法存在很大的盲目性，會導致多數(shù)類樣本有效信息丟失；而過采樣由于插值的隨機性并不能保證新合成的樣本為少數(shù)類，而且有可能導致過適應[4]。三類技術都因為改變了原始數(shù)據(jù)的分布特征而備受爭議。

1.2 模型評價準則

在傳統(tǒng)的分類學習中，分類精度往往傾向于多數(shù)類。但對于不平衡數(shù)據(jù)而言，分類準確率卻因傾向于多數(shù)類的準確率而無法準確評價對少數(shù)類的分類性能[5-6]。已有學者研究出新的評價標準，如F-Score、G-mean等。Brefeld等(2005)使用ROC(Receiver Operating Characteristic)曲線的AUC(Area Under Curve)面積作為分類評價標準，科學準確地評價了分類器性能[7]。模型評價準則的研究有助于更科學地評判分類器分類精度，但不能從根本上解決不平衡數(shù)據(jù)的分類問題。因此從算法角度解決不平衡數(shù)據(jù)分類問題尤為重要。

1.3 算法層面解決方案

算法層面不平衡數(shù)據(jù)處理的方法主要有代價敏感性學習、單類學習和集成學習算法等[8]。代價敏感學習基于對少數(shù)類正確分類的價值高于對多數(shù)類正確分類的價值的假設，通過改進分類器模型的內部構造，使基于最小錯誤率的分類器轉化為代價敏感分類器。在數(shù)據(jù)嚴重不平衡時，單類學習通過只采用感興趣的目標類進行學習來預防多數(shù)類對少數(shù)類的淹沒問題。集成學習通過增加錯誤樣本分類的權值進一步改善分類器針對少數(shù)類的分類性能。KSVM是目前比較經典的分類器，該算法充分利用機器學習算法SVM，同時有效結合了KNN算法。但該分類器閾值的固定導致過多噪聲的引入是亟待解決的問題。本文研究的重點就是通過對KSVM分類器優(yōu)化改進來提升對不平衡數(shù)據(jù)的分類預測性能。

2 KSVM算法改進

2.1 KSVM分類器

李蓉等[9]首次提出了定理：SVM可以看做每類只有一個代表點的1NN分類器。并在該定理的基礎之上提出了KSVM算法，主要思想是：由于SVM對每一類只取一個代表點，但往往該點不能很好地代表該類提供充足的有效分類信息，此時引入KNN分類器，將所有的支持向量作為代表點，從中選取近鄰的K(K=2n+1，n=1,2,3,…)個代表點增加有效分類信息進而成功預測樣本類別。王超學等指出了KSVM算法的缺陷，并提出了改進型算法EDSVM[10]：SVM學習訓練得出各類別的支持向量，由支持向量數(shù)目確定KNN的K近鄰參數(shù)，在特征空間采用KNN算法進行分類。

上述KSVM系列算法均建立在閾值ε固定的前提下，忽視了非平衡數(shù)據(jù)下兩類數(shù)據(jù)信息量的差異性，忽略了不同數(shù)據(jù)集的兩類支持向量(SVs+、SVs-)的數(shù)量、分布特征的差異[11]。因此，固定的閾值使得KSVM分類性能受到了限制。本文首先闡述了KSVM系列算法閾值尋優(yōu)的重要性，并在前人基礎之上，利用遺傳算法進行閾值尋優(yōu)提出了ε-KSVM算法。通過實驗進一步論證了閾值尋優(yōu)應用于分類器KSVM是科學的、有實踐意義的。

2.2 閾值尋優(yōu)的必要性

定義1清晰類(ClearData)數(shù)據(jù)集是由到分類超平面的距離大于等于閾值ε的待測樣本點組成。如圖1空間I、II所示。

圖1 超平面與代表點

定義2模糊類(BlurData)數(shù)據(jù)集是由到分類超平面的距離小于閾值ε的待測樣本點組成。如圖1空間III所示。

損失函數(shù)(Loss Function)是用來估量模型預測值f(x)與真實值Y的不一致程度的非負實值函數(shù)。

SVM分類器的損失函數(shù)可表示為：

(1)

KNN的損失函數(shù)可表示為：

(2)

式中：分類器SVM的y值應為分類器決策函數(shù)的“原始”輸出，而不是最終的類標，即y=w·x+b。對于可能的輸出t=±1，若t與y有相同的符號(意味著y分類預測正確)，則max{0,1-t·y}=0。對于分類器KNN，xi表示待測樣本的真實類別，ci=f(x)為預測類別。由此不難得出分類器KSVM的損失函數(shù)為：

Loss=Loss,svm+a·Loss，knn=

(3)

KSVM分類器通過增加易錯樣本點的有效分類信息進一步提升了分類準確率。對到分類超平面的距離小于閾值ε的模糊類樣本采用KNN分類器進行分類，到分類超平面的距離大于閾值ε時采用SVM分類器。但閾值選取是否恰當，對分類超平面附近樣本點(尤其是少數(shù)類樣本)的分類準確率有很大的影響。

一方面，對于確定的待分類數(shù)據(jù)集，少數(shù)類特征向量數(shù)量少且分布密集時(見圖2(b))容易發(fā)生分類結果向多數(shù)類傾斜的情況，即樣本點位于少數(shù)類的支持向量面附近時，SVM以1NN的方式計算該點最近鄰支持向量，卻因少數(shù)類的支持向量分布過于集中，極易造成負類噪聲的引入，導致該點的最近近鄰反而是多數(shù)類中的支持向量(SVs-)，若此時將該點歸為ClearData數(shù)據(jù)集并用SVM分類器進行分類，致使錯分導致Losssvm增大。針對此種情況，需智能地增大閾值ε，將該樣本點歸為BlurData數(shù)據(jù)集采用KNN分類器來獲取更多有效分類信息[12]。

圖2 少數(shù)類分類錯誤情形

另一方面，在少數(shù)類支持向量的個數(shù)明顯低于多數(shù)類支持向量且少數(shù)類支持向量分布稀疏的情況下(見圖2(b))，多數(shù)類支持向量提供的信息量足以淹沒少數(shù)支持量提供的分類信息，此時若將圖中待測樣本點歸為BlurData采用KNN進行分類，由于引入過多噪聲導致錯分，造成Lossknn增大。在該情形下，需智能地減小閾值ε，將該樣本點歸為ClearData數(shù)據(jù)集并采SVM分類器來最大限度地降低噪聲的影響。

因此，對分類超平面附近的樣本進行分類時，往往需要增加有效分類信息提高分類精度，但增加有效分類信息的同時往往伴隨著引入更大的噪聲，智能地確定ClearData與BlurData的邊界(即閾值ε)，成為進一步降低分類“損失”的關鍵。閾值的選擇應該適用于數(shù)據(jù)集以及具體支持向量的數(shù)量與分布特征，而并非采取統(tǒng)一的經驗閾值。

2.3 ε-KSVM算法的提出

本文針對KSVM算法應用于不平衡數(shù)據(jù)時的閾值固定的缺陷，提出一種改進的隨數(shù)據(jù)集不同動態(tài)調整閾值的ε-KSVM算法。主要思想是：利用分類器KSVM對待測樣本進行分類預測之前，采用遺傳算法尋找最優(yōu)閾值ε*。對于到分類超平面的距離distance≥ε*的待測樣本，歸為清晰類(ClearData)；對于distance<ε*的樣本，歸為模糊類(BlurData)。對于清晰類樣本，采用SVM分類器進行分類，對于模糊類樣本，需增加有效分類信息，采用KNN分類器進行分類，從而提高了分類器樣本的分類精度。ε-KSVM算法具體如下：

Input：訓練數(shù)據(jù)集TrainData；測試數(shù)據(jù)集TestData

Output：測試數(shù)據(jù)集中樣本的類別j*(x′)=f(x′)

BEGIN：

Step1：初始化數(shù)據(jù)集ClearData=Φ，BlurData=Φ；

Step2：經過對訓練集TrainData的學習得到SVM的分類超平面g(x)=∑i∈SVαiyik(xi,x)+b*以及支持向量SVs；

Step3：通過遺傳算法尋找最優(yōu)閾值ε*；

Step4：對于測試樣本x′∈TestData，計算

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*(x′)=f(x′)；

Step6.2：對于x′∈BlurData，則以所有的支持向量SVs作為x′近鄰樣本，采用KNN對x′進行分類。

END

其中，通過遺傳算法進行閾值尋優(yōu)過程見2.4節(jié)。

2.4 閾值尋優(yōu)過程

采用遺傳算法進行閾值尋優(yōu)。遺傳算法具有隱含的并行性和強大的全局搜索能力，可以在較短的時間內搜索到全局最優(yōu)點。由于遺傳算子、交叉算子的引入，理論上遺傳算法搜索到全局最優(yōu)解的概率為1[13]。

遺傳算法閾值尋優(yōu)過程中，適應度函數(shù)指導搜索方向。本文的目的是提高KSVM算法的分類精度，因而采用分類精度(Accuracy，ACC)作為樣本的適應度函數(shù)Fitness，表示如下：

(4)

將遺傳算法應用于KSVM閾值優(yōu)化過程，算法的基本步驟如下：

BEGIN：

Step1：初始化種群，隨機選擇種群個體P(ε)；

Step2：將種群中各個體P(ε)代入適應度函數(shù)Fitness(ε)，以訓練數(shù)據(jù)和測試數(shù)據(jù)對其進行訓練和測試[14]；

Step3：依據(jù)適應度計算準則，計算個體適應度函數(shù)值；

Step4：若種群中最優(yōu)個體所對應的適應度函數(shù)值足夠大或者算法已連續(xù)運行多代，且個體的最佳適應度無明顯改進則退出循環(huán)，得到優(yōu)化閾值ε*；否則，繼續(xù)下一步Step5；

Step5：應用輪盤賭方式的選擇算子[15]，按照最優(yōu)保存、最差取代的原則，從P(ε)中選擇出下一代；

Step6：執(zhí)行交叉算子和變異算子，交叉概率取0.7，變異算子取0.1，形成新個體；

END

2.5 支持向量機參數(shù)優(yōu)化

為了在不平衡數(shù)據(jù)的分類中更好地發(fā)揮支持向量機(SVM)的學習能力，選取粒子群優(yōu)化算法PSO(Particle Swarm Optimization)對SVM的懲罰參數(shù)C以及RBF核函數(shù)的參數(shù)gamma進行優(yōu)化。粒子群算法PSO是一種基于群智能啟發(fā)式全局隨機優(yōu)化算法，通過信息共享機制模擬鳥群的捕食行為來尋找最優(yōu)解。粒子群算法尋優(yōu)參數(shù)C、gamma流程如圖3所示。

圖3 PSO尋優(yōu)C、gamma過程

3 實驗及數(shù)據(jù)分析

3.1 數(shù)據(jù)來源

為驗證算法的有效性，從UCI機器學習數(shù)據(jù)庫選取了不平衡程度、屬性維度、樣本數(shù)量互不相同的8組數(shù)據(jù)集進行實驗，并且數(shù)據(jù)來源于電信、能源、醫(yī)療三個不同行業(yè)，數(shù)據(jù)集基本信息如表1所示。本文使用綜合考慮查準率、查全率的F-Score、GMean作為分類評價指標，F(xiàn)-Score衡量分類器對少數(shù)類的分類性能，GMean衡量數(shù)據(jù)集整體的分類性能[16]。

表1 數(shù)據(jù)集基本信息

續(xù)表1

F-Score、GMean推導過程如下：

(5)

(6)

(7)

(8)

式中：TPR為真“正類”率，TNR為真“負類”率。Precision與Recall分別為查準率、查全率。F-Score是綜合查全率和查準率的分類評價指標，GMean是保證多數(shù)類、少數(shù)類精度平衡的情況下最大化兩類精度的評價指標。F-Score、GMean二者在對不平衡數(shù)據(jù)分類的評價上更加科學。

3.2 實驗結果分析

實驗在Windows環(huán)境下的MATLAB軟件上運行，通過編寫分類器ε-KSVM與遺傳算法來進行閾值尋優(yōu)。為了保證實驗不受SVM核函數(shù)選擇上的影響，統(tǒng)一選擇徑向基函數(shù)(RBF kernel)。通過10折交叉驗

證(10-fold cross validation)重復實驗。本文對比了KNN、SVM、KSVM、ε-KSVM幾種算法在評價準則F-score、GMean上的優(yōu)劣程度。其中KNN算法采用了K=3、K=5兩種，KSVM算法使用的是前人固定的經驗值ε=0.8。得到了8組不平衡數(shù)據(jù)的最優(yōu)閾值ε以及6種算法的F-Score、GMean。

從表2可知，8組數(shù)據(jù)的最優(yōu)閾值沒有統(tǒng)一的規(guī)律可尋，沒有采用前人所采取的經驗閾值0.8附近，而是針對不同的數(shù)據(jù)集獲取不同的最優(yōu)閾值。實驗驗證了ε-KSVM閾值尋優(yōu)思想的正確性。

表2 8組數(shù)據(jù)的最優(yōu)閾值

表3、表4給出了評價結果值(括號內為多次交叉驗證的標準差)，結果顯示KNN(K=3)與KNN(K=5)的分類效果相差不大，KSVM系列算法(包括KSVM、BDKSVM算法在內)分類效果好于KNN、SVM算法。ε-KSVM的分類效果要優(yōu)于KNN、KSVM、BDKSVM。從F-Score、G-Mean的實驗結果不難看出，改進的分類器ε-KSVM整體分類精度優(yōu)于其他幾種算法。

表3 F-Score對比值

表4 G-Mean對比值

綜合上述結果，通過遺傳算法進行閾值優(yōu)化來提高對不平衡數(shù)據(jù)的分類精度是有效的。本文提出的閾值尋優(yōu)ε-KSVM分類器，對提高不平衡數(shù)據(jù)樣本尤其是少數(shù)類的分類精度有顯著效果。

4 結 語

在對電力、能源、醫(yī)療等行業(yè)數(shù)據(jù)分析的過程中，普遍存在數(shù)據(jù)分類不平衡問題，本文針對具體不同的不平衡數(shù)據(jù)集，提出了一種動態(tài)適應不同數(shù)據(jù)集的ε-KSVM分類器。該分類器利用遺傳算法尋找分類器最優(yōu)閾值ε*，調整SVM、KNN算法對待測數(shù)據(jù)集的應用范圍，降低了對少數(shù)類分類時易被多數(shù)類覆蓋的風險，改善少數(shù)類樣本的分類預測精度的同時也降低了對多數(shù)類的錯分。與前人的KSVM系列分類器相比，本文提出的ε-KSVM算法在處理不平衡分類問題時性能更加優(yōu)越。實驗進一步驗證了該算法的有效性，也為不平衡二分類問題提供了一個嶄新的視角，該思想可以應用在電力通信故障檢測、疾病診斷、信用卡欺詐等諸多實際問題中。

[1] 王瑞.針對類別不平衡和代價敏感分類問題的特征選擇和分類算法[D].中國科學技術大學,2013.

[2] 曾瑾.信用卡欺詐風險的防控[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].計算機科學,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的文本自動分類技術[J].計算機應用與軟件,2016,33(2):38-41.

[9] 李蓉,葉世偉,史忠植.SVM-KNN分類器-一種提高SVM分類精度的新方法[J].電子學報,2002,30(5):745-748.

[10] 王超學,張濤,馬春森.改進SVM-KNN的不平衡數(shù)據(jù)分類[J].計算機工程與應用,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在短期風速預測中的應用[J].電力系統(tǒng)保護與控制,2016,44(9):38-42.

[14] 萬源,童恒慶,朱映映.基于遺傳算法的多核支持向量機的參數(shù)優(yōu)化[J].武漢大學學報,2012,58(3):255-259.

[15] 楊平,鄭金華.遺傳選擇算子的比較與研究[J].計算機工程與應用,2007,43(15):59-64.

[16] 林志勇,郝志峰,楊曉偉.若干評價準則對不平衡數(shù)據(jù)學習的影響[J].華南理工大學學報,2010,38(4):147-154.