局部關注支持向量機算法

周于皓,張紅玲,李芳菲,祁 鵬

(1.中國石油大學(北京) 石油工程學院,北京 102249; 2.武漢紡織大學 傳媒學院,武漢 430000)(*通信作者電子郵箱951113598@qq.com)

0 引言

數據集的不均衡性是機器學習的一個重要問題,傳統的機器學習算法雖然有效,但僅限于數據集相差不多的情形,一旦出現大比例的失衡,算法便會失效。而且在現實生活中，數據集不均衡的情形是更常見的,比如某一類數據較難采集、獲取周期較長、獲取成本較大等問題都會使訓練數據產生非均衡性。以二分類為例,當數據集均衡時,即正負樣本基本一致時,傳統的機器學習算法效果已經非常好,這說明傳統機器學習算法在理論上是成功的,如支持向量機(Support Vector Machine, SVM)算法、決策樹、DBSCAN(Density-Based Spatial Clustering of Applications with Noise)等；但當正樣本遠大于負樣本時,再直接使用傳統的機器學習方法就變得基本無效了,所以解決這種訓練集的不均衡問題顯得格外重要。

在處理這類不均衡問題上,主流可分為兩類：

第二類是算法層面的，包括基于集成[6]的或基于代價敏感[7]的學習改進方法。集成算法方面如基于Boosting思想的兩個最著名的算法AdaBoost[8-9]和GBDT(Gradient Boosting Decision Tree),通過集成弱學習分類器達到強學習目的,雖然這類方法的主要目的并不是針對非平衡數據集,但其集成效果遠好于基礎的單一算法。代價敏感學習主要是基于調整代價矩陣,其基本思想是對于代價高的誤分類樣本大大地提高其權重,而對于代價高的正確分類樣本適當地降低其權重,使其權重降低相對較小。這類方法可大致劃分為兩小類：第一類方法是直接構建代價敏感學習模型,如為決策樹提出的代價敏感的剪枝方法、通過改進上述集成方法中的AdaBoost而產生的代價敏感的Boosting算法AdaCost[10]、Geibel等[11]為SVM提出的基于Perceptron分類算法的代價敏感的學習方法等。第二類方法如Domingos等[12]提出的MetaCost,這是一種將一般分類模型轉換成代價敏感模型的方法。它通過一個“元學習”過程,根據最小期望代價修改訓練樣本的類標記,并使用修改過的訓練集重新學習新的模型。

通過研究,本文提出了一種結合了數據層面和算法層面的新型集成算法。與AdaBoost、AdaCost等這類典型的算法不同,這兩者的數據層面對于多類數據的劃分是被動的,是根據上一輪次算法試算的效果進行的；而本文的集成方法是一種主動的數據集劃分策略,通過對多類數據集的內部聚類,不僅解決了數據平衡問題,還精確地刻畫了數據集間的相對特征。另外在主動劃分多類數據集方面,如文獻[13-15]方法,與其多層次的數據劃分方法不同,本文提出的是一種建立在集成算法上的數據集主動劃分方法,在數據集的劃分方法上僅使用原始的聚類方法,且基本不存在問題針對性的超參數選擇,此外該方法可以進一步泛化成一種集成算法,除以SVM為基本算法[16]外,也可以選用其他基礎機器學習算法來實現。

1 算法基本原理

本文提出的集成算法是一種雙層的SVM集成算法,類似于神經網絡中的多層感知機,底層擁有數個傳統SVM分類器,這一結構相當于把非均衡數據集映射到一個特殊的特征空間。每一個底層SVM的作用就是只關注訓練數據集中數據集的一部分特征,使得其只對特定的數據敏感,而對其他特征的數據基本無效果。最后在底層SVM群上連接一個集成SVM,將每一個底層SVM對數據的判斷進行匯總,作出最后判斷。這一集成算法的拓撲結構如圖1所示。

圖1 集成方法拓撲結構示意圖

在面對非均衡數據集問題時總是失敗的一個重要原因就是,規模大的集合在訓練時會湮滅小規模的集合,所以一個簡單自然的想法就是將規模大的集合進行劃分,使得每一子集數量與小規模集合數量相當,這樣一來,每個底層的SVM在訓練過程中既不會出現數據集不均衡的問題,又擁有了局部特征關注的能力。

為了使底層SVM有局部特征感知能力,且不存在數據不平衡現象,本文提出先對數據進行特征聚類。在子集合的劃分上采用K-means聚類方法,預先提供超參數K,即應事先將大規模的集合分解成多少分子集合。選取K-means方法的原因有兩個:1)K-means聚類子集類數量可人為規定,方便控制每個SVM接收到的正負樣本數量比例維持在一定的水平上;2)K-means計算簡單,耗時低,對整個集成算法的計算復雜度增加少。

在利用K-means完成聚類后,如圖2所示,不同的符號代表不同的聚類后子集,每一子集代表著原集合的一部分特征,將這些子集與負樣本集合分別組成訓練集,用于訓練出相同數量的SVM分類器。每一個分類器即代表著對一個特定特征的識別器。

圖2 局部關注SVM示意圖

最后頂層的集成SVM匯總每個底層SVM,相當于集成了一個特征分類器群,從而可以逐特征進行分類判斷。

2 算法流程

設有二分類問題,集合A代表大規模集合,集合B代表小規模集合,數量比約為n=[A/B]。為了使底層SVM不再具有數據集不均衡的問題,先對集合A進行K-means聚類,K值取n(下文有對該超參數的優化與討論),共隨機聚出n類,簡記為Ai(i=1,2,…,n),共組成n個子訓練集,簡記為Si(i=1,2,…,n),在n個子訓練集上訓練n個SVM,以線性SVM為例作n次優化,即使得方程組(1)共同達到最大值。

(1)

其中:ωi表示每個SVM的系數矩陣,bi為偏置系數,yij與xij分別表示樣本的標簽和屬性。直觀上理解,每一個底層SVM相當于一個線性分類器,在最優化完成后產生了n條最大間隔分割超平面如圖3所示。每一個分隔超平面只關注集合A的一部分特征,最終n條分割超平面以集合B為中心將集合B包圍,形成包絡面。可以很清楚地看到,無論數量相差多么懸殊,包絡面都可以精確切分。

優化完成后,即所有底層SVM訓練完畢,得到分類器簇SVMi(i=1,2,…,n)。然后開始訓練頂層SVM,對于頂層SVM來說,實際上等價于普通SVM訓練,不同的是原本訓練數據是兩維(為了方便討論假設原始數據集是兩維的),即底層SVM接收的訓練數據是兩維的,而經過底層SVM群映射后,每個SVMi給出一個得分,所以原本的兩維數據映射成n維數據,頂層接收的訓練數據為n維數據,最后正常訓練一個頂層SVM即可。這種內置的映射方式,決定了集成SVM算法最終良好的分類效果,因為每一維度代表著一個特征判斷的結果,從而這個n維空間與原數據空間相比,大小數據集中每一部分都得到了分離,實現了類間分隔最大化。這一集成過程,使得頂層SVM在訓練時,訓練數據集從不均衡的集合變成不存在不均衡問題的特征空間,不存在任何樣本、特征湮滅問題。

圖3 線性SVM理解圖示

3 仿真實驗

為了檢測本文提出的集成算法的有效性,本文以基礎SVM算法、K-SOMTE方法、AdaCost、GTB(Gradient Tree Boosting)四種算法為基準進行對比。在UCI數據庫中選取五個常用的不均衡分類數據集進行算法測評，數據集如表1所示。

表1 實驗中使用的UCI數據集

在測評指標上,本文以gmean值為基礎對分類結果進行評價,根據部分相關文獻[17]介紹,將二類問題中混淆矩陣等價改為如表2所示。

表2 混淆矩陣

表2中：TP表示預測正確的樣本中少類的數目；FP表示預測錯誤的樣本中少類的數目；TN表示預測正確的樣本中多類的數目；FN表示預測錯誤的樣本中多類的數目。

(2)

其中:

為了使實驗結果更加平滑,不具偶然性,實驗采用5折交叉驗證方法,在最終的5次結果中取平均值作為算法在該數據集上的最終得分。測評結果如表3所示。

表3 gmean 測評結果匯總

從表3可以看出：本文提出的局部關注SVM算法大體表現優良,無論與基于采樣的K-SOMTE，還是基于集成、代價敏感的AdaCost和GTB,都表現出了一定程度的優勢,尤其是在Abal這個不平衡問題嚴重的數據集上,本文方法表現突出,gmean分數可以達到0.825 5。主要是因為當數據集不平衡性達到一定程度后,基于采樣的方法和基于代價敏感的方法的機制不能從根本上跨越不平衡性問題,大量的過采樣和較大的代價敏感反而會產生過擬合等問題；而本文提出的局部關注SVM算法以簡單的方式繞過了不平衡性,且保持了原有數據集的數據利用率,使得預測效果優于其他算法。

4 算法的優化與討論

4.1 關于SVM核函數

通過大量的實驗發現,一般頂層SVM選用徑向基核函數(Radial Basis Function, RBF)為佳,底層SVM視情況而定。比如對Segm數據集,采用線性核時gmean評分可達到0.989 0的效果；如果將線性核改為高斯核,效果卻只能達到0.919 9左右,這說明底層特征分類器不一定越復雜越好。從圖3可以看出，對于這種數據分布較為簡單的集合,線性核就可以起到很好的效果,如果使用高斯核可能會出現過擬合等現象,反而影響效果。

4.2 關于聚類超參數K的選取

由于本文選取的K-means聚類方法迭代起始點的選擇為任意選擇,所以理論上講即使使用同一訓練集合,因為底層特征集合的劃分結果略有不同,每次訓練結果也會不同,但結果相差不大,相對偏差經計算只有1%左右。在此基礎上本文對超參數K進行優化,如圖4所示,以Glass、Car、Abal三個數據集為例,均從K=2開始,循環訓練并檢測gmean得分。

從圖4可看出，曲線局部震蕩得比較厲害,主要原因就是上面提到的聚類有一定的隨機性,從數值上可以看出,這一震蕩相對范圍很小,可以忽略。從圖4(a)可以看出,對于這種非均衡性差別不是很大的分類問題(不均衡比例為6.38),只要K值不是過小(在小于6時,gmean得分顯著下降),最終結果基本穩定在0.95上下,正負誤差不超過0.005,且只要超過6.38這一原本不均衡比例,表現都不錯。圖4(b)與圖4(a)情形差不多,Car數據集的不平衡比例為24.04,K小于10時gmean得分顯著下降,當K在80附近,得分最高。Abal實驗如圖4(c)所示,相對于其他實驗而言,Abal數據集最難,不平衡度為129.53。可以看出,隨著K的增大,gmean得分持續提高,在K=120處,取得最大gmean得分為0.825 5,基本也和不平衡度吻合,但經后續實驗觀測,隨著K繼續增加到200左右,gmean得分依然有輕微提升,但模型訓練及整體算法的計算復雜度則大大提升。所以實際應用中可先選取一個大于原始數據集的不平衡度的值作為初始K值,隨后可適當增大K來提升效果。

圖4 超參數K對分類結果影響曲線

4.3 改進工作

正如前文所述局部關注SVM算法的效果得益于這種數據集的局部聚類劃分和訓練,這種結構賦予了局部關注SVM算法局部精細的能力。基于此啟發,本文提出一個計算框架,框架分為數據聚合層、局部分類器層、集成層三部分。數據聚合層可使用K最近鄰(K-Nearest Neighbors, KNN)、基于密度的聚類(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)等基礎無監督聚類算法,而局部分類器層和集成層兩部分可以使用SVM、多層感知機、決策樹等一系列基礎算法,底層和頂層算法可以相同也可以不同。

5 結語

針對非均衡數據集的分類問題。本文提出了一種新型集成算法,以SVM為基礎算法建立了兩步集成的拓撲結構,先將訓練數據集按KNN進行非監督聚類,然后用得到的K個集合分別訓練K個底層SVM,這樣一來每一個底層SVM只關注特定的數據特征,從而有效避免了大規模數據集湮滅小規模數據集特征的問題。在五組實驗中局部關注SVM算法效果較傳統SVM算法顯著提升,對比流行的一些集成算法也略占優勢,可以說在一定程度上提升了訓練數據集非均衡的問題下分類的準確度。

參考文獻(References)

[1] BLAGUS R, LUSA L. SMOTE for high-dimensional class-imbalanced data[J]. Bmc Bioinformatics, 2013, 14(1): 106.

[2] ZIEBA M, TOMCZAK J M, GONCZAREK A. RBM-SMOTE: restricted Boltzmann machines for synthetic minority oversampling technique[M]// ACIIDS 2015: Proceedings of the 7th Asian Conference on Intelligent Information and Database Systems. Berlin: Springer, 2015: 377-386.

[3] 張永, 李卓然, 劉小丹. 基于主動學習SMOTE的非均衡數據分類[J]. 計算機應用與軟件, 2012, 29(3): 91-93.(ZHANG Y, LI Z R, LIU X D. Active learning SMOTE based imbalanced data classification[J]. Computer Applications and Software, 2012, 29(3): 91-93.)

[4] 楊智明, 喬立巖, 彭喜元. 基于改進SMOTE的不平衡數據挖掘方法研究[J]. 電子學報, 2007, 35(增刊2): 22-26.(YANG Z M, QIAO L Y, PENG X Y. Research on datamining method for imbalanced dataset based on i mproved SMOTE[J]. Acta Electronica Sinica, 2007, 35(S2): 22-26.)

[5] 曾志強, 吳群, 廖備水, 等. 一種基于核SMOTE的非平衡數據集分類方法[J]. 電子學報, 2009, 37(11): 2489-2495.(ZENG Z Q, WU Q, LIAO B S, et al. A classfication method for imbalance data set based on kernel SMOTE[J]. Acta Electronica Sinica, 2009, 37(11): 2489-2495.)

[6] 大勇. 基于非平衡數據的適應性采樣集成分類器的研究[D]. 長沙: 中南大學, 2010: 1-42.(DA Y. An adaptive sampling ensemble classifier for learning from imbalanced data sets[D]. Changsha: Central South University, 2010: 1-42.)

[7] 谷瓊, 袁磊, 熊啟軍, 等. 基于非均衡數據集的代價敏感學習算法比較研究[J]. 微電子學與計算機, 2011, 28(8): 146-149.(GU Q, YUAN L, XIONG Q J, et al. A comparative study of cost-sensitive learning algorithm based on imbalanced data sets[J]. Microelectronics and Computer, 2011, 28(8): 146-149.)

[8] ZHU J, ZOU H, ROSSET S, et al. Multi-class AdaBoost[J]. Statistics & its Interface, 2006, 2(3): 349-360.

[9] 李正欣, 趙林度. 基于SMOTEBoost的非均衡數據集SVM分類器[J]. 系統工程, 2008, 26(5): 116-119.(LI Z X, ZHAO L D. A SVM classifier for imbalanced datasets based on SMOTEBoost[J]. Systems Engineering, 2008, 26(5): 116-119.)

[10] ZHANG J. AdaCost: misclassification cost-sensitive boosting[EB/OL]. [2017- 05- 10]. https: //pdfs.semanticscholar.org/9ddf/bc2cc5c1b13b80a1a487b9caa57e80edd863.pdf.

[11] GEIBEL P, BREFELD U, WYSOTZKI F. Perceptron and SVM learning with generalized cost models[J]. Intelligent Data Analysis, 2004, 8(5): 439-455.

[12] DOMINGOS P. MetaCost: a general method for making classifiers cost-sensitive[C]// KDD 1999: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 1999: 155-164.

[13] 王金婉. 面向在線不均衡數據分類的極限學習機算法研究[D]. 新鄉: 河南師范大學, 2016: 13-25.(WANG J W. Research on extreme learning machine for online swquential imbalanced data classification[D]. Xinxiang: Henan Normal University, 2016: 13-25.)

[14] 毛文濤, 王金婉, 何玲, 等. 面向貫序不均衡數據的混合采樣極限學習機[J]. 計算機應用, 2015, 35(8): 2221-2226.(MAO W T, WANG J W, HE L, et al. Hybrid sampling extreme learning machine for sequential imbalanced data[J]. Journal of Computer Applications, 2015, 35(8): 2221-2226.)

[15] 毛文濤, 田楊陽, 王金婉, 等. 面向貫序不均衡分類的粒度極限學習機[J]. 控制與決策, 2016, 31(12): 2147-2154.(MAO W T, TIAN Y Y, WANG J W, et al. Granular extreme learning machine for sequential imbalanced data[J]. Control and Decision, 2016, 31(12): 2147-2154.)

[16] ADANKON M M, CHERIET M. Support vector machine[J]. Computer Science, 2002, 1(4): 1-28.

[17] 谷瓊, 袁磊, 寧彬, 等. 一種基于混合重取樣策略的非均衡數據集分類算法[J]. 計算機工程與科學, 2012, 34(10): 128-134.(GU Q, YUAN L, NING B, et al. A noval classification algorithm for imbalanced datasets based on hybrid resampling strategy[J]. Computer Engineering and Science, 2012, 34(10): 128-134.)