李創(chuàng)創(chuàng)，盧光躍，王航龍

（西安郵電大學(xué)無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室，陜西 西安 710121）

基于邊界樣本欠取樣支持向量機(jī)的電信用戶欠費分類算法

李創(chuàng)創(chuàng)，盧光躍，王航龍

（西安郵電大學(xué)無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室，陜西 西安 710121）

電信用戶欠費預(yù)測是一個不平衡數(shù)據(jù)集分類問題。針對傳統(tǒng)支持向量機(jī)（SVM）對不均衡數(shù)據(jù)集中少數(shù)類檢測精度低的問題，基于分類平面由邊界樣本的位置決定，提出了一種通過刪除部分多數(shù)類邊界樣本的方法來改善傳統(tǒng)SVM算法的不足，將該算法和其他幾種算法在電信數(shù)據(jù)和多個不平衡UCI數(shù)據(jù)集上的實驗結(jié)果進(jìn)行對比，驗證所提算法對少數(shù)類的檢測精度和總體評價指標(biāo)都有所提高。

欠費；不均衡；SVM；邊界；欠取樣

1 引言

近年來，隨著電信運營商之間的競爭日益激烈，我國電信運營商在推出大量新業(yè)務(wù)的同時也降低了用戶的開戶門檻，使得拖欠、拒交話費用戶的比例不斷增加[1]，對電信企業(yè)正常運營造成很大影響。為了減少壞賬，增加公司利潤，越來越多的運營商通過建立用戶欠費預(yù)測模型，提前預(yù)測可能出現(xiàn)欠費的用戶并對該類用戶采取相應(yīng)的措施。支持向量機(jī)（support vector machine，SVM）是以統(tǒng)計學(xué)為基礎(chǔ)的一種經(jīng)典機(jī)器學(xué)習(xí)方法[2]，它在解決高維非線性數(shù)據(jù)集中的分類問題中表現(xiàn)出了良好的性能[3]，因此被越來越多的學(xué)者所關(guān)注，現(xiàn)已廣泛應(yīng)用于許多領(lǐng)域的分類問題中。

傳統(tǒng) SVM 分類算法在均衡數(shù)據(jù)集上可以得到良好的分類效果，當(dāng)數(shù)據(jù)集不均衡時，分類平面會偏向于少數(shù)類[4-8]，導(dǎo)致少數(shù)類的漏檢率增大。在生活領(lǐng)域中人們需要面對很多非平衡數(shù)據(jù)集上的分類問題，例如電信欠費用戶預(yù)測。由于電信用戶中欠費用戶數(shù)量遠(yuǎn)遠(yuǎn)少于正常用戶，并且對少數(shù)類的檢測精度的要求要高于多數(shù)類，因此必須改進(jìn)SVM來提高對少數(shù)類的檢測精度。

針對傳統(tǒng)SVM固有的缺點，已提出了兩類改進(jìn)算法。一類是基于算法層面的，通過改進(jìn)算法模型來使其適應(yīng)不均衡數(shù)據(jù)集，比如模糊支持向量機(jī)[9]（fuzzy support vector machine，F(xiàn)SVM）就是根據(jù)每一個樣本離樣本中心的距離賦予每一個樣本不同的權(quán)值來改善SVM分類平面偏移問題。另一類為數(shù)據(jù)層面上的，其通過對訓(xùn)練集的數(shù)據(jù)進(jìn)行處理，使其多數(shù)類樣本和少數(shù)類樣本保持基本均衡，最具代表性的算法有隨機(jī)過取樣（over SVM）算法和隨機(jī)欠取樣（under SVM）算法。隨機(jī)過取樣算法采用隨機(jī)復(fù)制訓(xùn)練集中少數(shù)類樣本，使新的訓(xùn)練集數(shù)據(jù)集中兩類樣本保持平衡[10]。然而，增多樣本不僅使計算復(fù)雜度增高，并使分類間隔減小，容易產(chǎn)生過擬合。而隨機(jī)欠取樣算法采用隨機(jī)去除訓(xùn)練集中的多數(shù)類部分樣本使多數(shù)類和少數(shù)類樣本數(shù)相等[11]。由于欠取樣算法只是選取原來多數(shù)類樣本的一個隨機(jī)子集，并不能夠代表原多數(shù)類樣本的全部信息，當(dāng)選擇的子集遠(yuǎn)離邊分類邊界，會導(dǎo)致SVM分類平面過偏移，使得多數(shù)類檢測精度損失過大。

本文提出一種基于邊界樣本的欠取樣 SVM（boundary samples-based under-sampling support vector machine，B-SVM）算法，該算法首先對不平衡數(shù)據(jù)集進(jìn)行仿真得到初步的分類平面，計算多數(shù)類樣本到平面的距離，根據(jù)計算結(jié)果刪除部分多數(shù)類邊界樣本，從而使分類平面向多數(shù)類方向偏移。實驗中將本文所提算法應(yīng)用于某省的電信數(shù)據(jù)和標(biāo)準(zhǔn)的UCI數(shù)據(jù)集[12]中，并與已有算法進(jìn)行了對比，實驗結(jié)果表明本文算法對少數(shù)類的分類精度有了明顯的改善。

2 SVM理論

支持向量機(jī)的基本想法是求解幾何間隔最大的分類平面[13]。以二分類為例，設(shè)給定的訓(xùn)練集樣本為代表代表l維樣本，代表樣本類別。為了能更好地將樣本分為兩類，首先將樣本通過映射函數(shù)Φ(x)映射到高維空間，在高維映射空間中尋找分類平面；然后通過優(yōu)化分類平面的權(quán)向量w和截距b，尋找最大分類間隔平面，即優(yōu)化如下目標(biāo)函數(shù)：

其中，C為懲罰因子，用于平衡結(jié)構(gòu)風(fēng)險和經(jīng)驗風(fēng)險， ξi為松弛變量。

上述問題是一個凸二次規(guī)劃問題，利用拉格朗日乘子法可以將其轉(zhuǎn)化為如下對偶問題：

其中，αi是拉格朗日乘子，必須滿足Karush-Kuhn-Tucker（KKT）條件：

求解式（3）和式（4）得：

最終得到分類決策函數(shù)為：

圖1是測試數(shù)據(jù)集不均衡時SVM分類性能的示例。選用高斯函數(shù)生成了一個多數(shù)類與少數(shù)類之比為50∶1的二維不平衡數(shù)據(jù)集，十字型的為多數(shù)類樣本；圖1中以等高線的形式給出了分類平面，分類平面是等高線為零的線。從圖1中可以看到，分類超平面向著少數(shù)類偏移，部分少數(shù)類樣本被錯分?？梢姡?dāng)數(shù)據(jù)集不均衡時，多數(shù)類樣本在投影空間的密度遠(yuǎn)大于少數(shù)類；SVM為了使總體正確率最大化，分類平面會向少數(shù)類方向偏移，導(dǎo)致少數(shù)類的檢測精度低。

圖1 數(shù)據(jù)樣本比例為50∶1時的分類平面

3 針對非平衡樣本的基于邊界樣本欠取樣SVM

提高少數(shù)類的檢測精度，就必須使分類平面向多數(shù)類方向偏移，傳統(tǒng)的欠取樣算法沒有考慮到樣本在投影空間的分布特性，導(dǎo)致在測試集中分類效果差，因此必須充分考慮樣本的分布特性。由于在投影空間中邊界樣本占該類樣本的比例都很小，刪除掉部分多數(shù)類邊界樣本使分類平面偏移對多數(shù)類分類正確率影響很小，因此可以刪除部分多數(shù)類邊界樣本來使超平面向多數(shù)類方向偏移。

本文首先在原始數(shù)據(jù)集上運用傳統(tǒng) SVM 得到邊界樣本，再計算邊界樣本距分類平面的距離，根據(jù)計算結(jié)果，有選擇地刪除部分多數(shù)類邊界樣本。邊界樣本跟拉格朗日乘子αi和核寬度σ的值有密切的關(guān)系。根據(jù)式（3）和式（4）可求解得到αi，αi的值有3種可能，即：

· αi=0，根據(jù)式（6）可得ξi=0，則樣本xi被正確分類，并遠(yuǎn)離分類平面；

· 0＜αi＜C，根據(jù)式（5）得yi(w?Φ(xi)+ b)-1-ξi=0，根據(jù)式（6）得ξi=0，yi(w?Φ(xi)+b)=1，則樣本 xi是標(biāo)準(zhǔn)的支持向量，恰好落在最大間隔平面上；

· αi=C，根據(jù)式（5）和式（6）得。如果樣本xi被正確分類，并且處于分類平面和最大間隔平面之間。如果ξi≥1，樣本xi被錯分。

由上可知，αi＞0對應(yīng)的樣本為支持向量，與分類平面距離較近，決定了分類平面的位置和分類間隔的大小。

一旦分類平面得到后，可以計算每一個樣本與分類平面的距離。 γi表示樣本xi與分類平面的函數(shù)間隔，也表示該點離分類平面的“距離”：為對應(yīng)支持向量的拉格朗日乘子。

對于多數(shù)類樣本而言，當(dāng)γi≤0時表示樣本落入少數(shù)類一側(cè)，該樣本被錯分，γi＞1樣本在多

其中，J為總體的支持向量數(shù)數(shù)類一側(cè)，該樣本分類正確并遠(yuǎn)離分類平面，表示樣本在分類超平面和最大間隔平面之間，對應(yīng)的樣本為邊界樣本，可以根據(jù) γi的值刪除掉部分多數(shù)類樣本。

然而對于某些稀疏數(shù)據(jù)集（如電信數(shù)據(jù)集），存在很多屬性值為零的情況，在投影空間中邊界樣本密度較大，在這種情況下刪除邊界多數(shù)類樣本會導(dǎo)致多數(shù)類樣本的檢測精度損失過大。徑向基核函數(shù)的參數(shù)σ決定著邊界樣本密度。σ越小邊界樣本越多，σ越大邊界樣本越少。當(dāng)σ很小時，由于多數(shù)類邊界很多，刪除全部多數(shù)類邊界樣本會使分類平面向多數(shù)類過偏移，導(dǎo)致整體分類性能下降。所以在刪除邊界樣本時，為了不使分類平面過偏移，邊界樣本的數(shù)量不宜大于該類的5%。

基于邊界樣本的欠取樣SVM（B-SVM）具體算法步驟如下。

步驟 2 計算邊界樣本占多數(shù)類的樣本比例r，如果r＞0.05，則增大σ并返回步驟1重新計算α。

步驟3 根據(jù)式（9）計算多數(shù)類樣與分類平面的函數(shù)間隔 γi。

步驟4 刪除掉 γi＜d的多數(shù)類樣本（d為人為設(shè)置的閾值）。

步驟5 將刪除后剩余的多數(shù)類樣本和少數(shù)類樣本進(jìn)行重組構(gòu)建新的訓(xùn)練集。

步驟6 根據(jù)訓(xùn)練得到新的分類器進(jìn)行分類。

圖2是刪除γi＜1的多數(shù)類邊界樣本后分類平面效果，與圖1對比，少數(shù)類分類全部正確，少數(shù)類的分類精度明顯提高，這是由于多數(shù)類邊界樣本遠(yuǎn)離少數(shù)類樣本，從而使分類平面向多數(shù)類方向偏移。

4 實驗分析及對比

4.1 不均衡數(shù)據(jù)分類效果指標(biāo)

對于電信欠費用戶分類問題，關(guān)注更多的是欠費用戶的檢測精度，傳統(tǒng)SVM的評價指標(biāo)不能很好地反映實際需求。近年來許多學(xué)者提出一些用于評價不均衡數(shù)據(jù)分類效果的指標(biāo)。最常用的有以下幾種（首先定義少數(shù)類（正例樣本）為P，多數(shù)類樣本（負(fù)例樣本）為 N）。FP是指將多數(shù)類錯分成少數(shù)類的樣本總數(shù)，F(xiàn)N是指將少數(shù)類錯分成多數(shù)類總數(shù)，TN和TP分別表示正確分類的多數(shù)類和少數(shù)類樣本數(shù)。

少數(shù)類樣本的檢測精度為：

圖2 去掉部分多數(shù)類邊界樣本后的分類平面的變化

多數(shù)類樣本的檢測精度為：

總體分類性能評估：

SE側(cè)重于考量少數(shù)類的正確率，SP側(cè)重于考量多數(shù)類的正確率，GM綜合了兩個指標(biāo)體現(xiàn)分類器的整體分類性能。

4.2 實驗數(shù)據(jù)

為了驗證本文算法在不均衡數(shù)據(jù)上的有效性，本文選取了5個不平衡UCI數(shù)據(jù)集[13]和某省的電信客戶欠費數(shù)據(jù)[14]，電信數(shù)據(jù)屬性有是否為VIP、付費方式、是否主動離網(wǎng)、是否被動離網(wǎng)和通話時長等92維。其中數(shù)值屬性可以直接使用，二值屬性、類別屬性經(jīng)過整數(shù)編碼可以使用。用戶屬性取值為：公眾（0）、集團(tuán)（1）。付費方式取值為：后付費（0）、預(yù)付費（1）。是否離網(wǎng)、是否主動離網(wǎng)、是否被動離網(wǎng)、是否主動停機(jī)和是否被動停機(jī)取值為：是（1）、否（0）。套餐月費用取值為：46元（0）、66元（1）、96元（2）、126元（3）、156元（4）、186元（5）、226元（6）、286元（7）、386元（8）、586元（9），取欠費金額作為目標(biāo)屬性，整數(shù)編碼后取值為：未欠費（0）、欠費（1）。處理后的樣本部分屬性見表1。

表1 電信客戶消費部分信息

6個實驗數(shù)據(jù)集特征信息見表2。

4.3 不同算法的性能比較

為了驗證本文所提算法在不均衡數(shù)據(jù)集上的有效性，應(yīng)用本文所提算法（B-SVM）和標(biāo)準(zhǔn)SVM算法、模糊SVM算法、隨機(jī)欠取樣SVM算法和隨機(jī)過取樣SVM算法對表1所給的6個不平衡數(shù)據(jù)集進(jìn)行了分類實驗。在進(jìn)行數(shù)據(jù)實驗之前，對數(shù)據(jù)集都進(jìn)行歸一化處理以降低每一個屬性值之間的差異。本文使用的仿真工具是 LIBSVM 和MATLAB。

本文使用五折交叉驗證獲得最佳的懲罰參數(shù)C和核寬度σ。由于隨機(jī)欠取樣和過取樣算法的不穩(wěn)定性，仿真結(jié)果為仿真10次的平均值，見表3。由表3可知，本文所提算法在前4個數(shù)據(jù)集對少數(shù)類的檢測精度（SE）和整體分類性能（GM）明顯優(yōu)于其他算法。傳統(tǒng)的SVM和FSVM在第5個數(shù)據(jù)集上的少數(shù)類檢測精度為0，表明第5個數(shù)據(jù)集中少數(shù)類和多數(shù)類在特征空間中分類間隔小，不易分辨。本文通過刪除掉與少數(shù)類易混淆的多數(shù)類使分類平面向多數(shù)類偏移，在該數(shù)據(jù)集上欠采樣SVM分類效果更好。

表2 不平衡數(shù)據(jù)集描述

由于電信數(shù)據(jù)為稀疏數(shù)據(jù)集，投影空間中的多數(shù)類邊界樣本密度很大，通過調(diào)整σ的取值范圍來使邊界樣本減少，使算法免于過擬合。本文通過變量d來調(diào)節(jié)刪除邊界樣本的數(shù)量。d越大，對少數(shù)類的檢測精度越高，多數(shù)類的正確率越低。本文取d= 1，實際應(yīng)用中可以根據(jù)對少數(shù)類的檢測精度的要求與對多數(shù)類錯誤的容忍率來動態(tài)調(diào)整。

表3 仿真結(jié)果對比

5 結(jié)束語

本文針對傳統(tǒng) SVM 對電信欠費用戶分類精度低的問題，提出了一種基于邊界樣本的欠取樣SVM算法，該算法通過刪除部分多數(shù)類邊界樣本使分類超平面向多數(shù)類偏移，提高對欠費用戶的檢測精度。并解決了當(dāng)邊界樣本過多時通過調(diào)節(jié)σ的取值范圍來解決過偏移的問題。與其他算法在5個不平衡UCI數(shù)據(jù)集和電信數(shù)據(jù)集上的仿真結(jié)果對比，表明所提算法能有效提高欠費用戶的檢測精度。

[1] 渠瑜. 基于 SVM 的高不平衡分類技術(shù)研究及其在電信業(yè)的應(yīng)用[D]. 杭州: 浙江大學(xué), 2010. QU Y. Research on SVM-based highly imbalanced classification and its application in telecommunications[D]. Hangzhou: Zhejiang University, 2010.

[2] VAPNIK V N. The nature of statistical learning theory[M]. Berlin: Springer, 2000: 138-167.

[3] JAMIL S, KHAN A. Churn comprehension analysis for telecommunication industry using ALBA[C]//ICET, IEEE, October 18-19, 2016, Islamabad, Pakistan. New Jersey: IEEE Press, 2016.

[4] RASKUTTI B. Extreme re-balancing for SVMs: a case study[J]. ACM Sigkdd Explorations Newsletter, 2004, 6(1):60-69.

[5] KANG P, CHO S. EUS SVMs: ensemble of under-sampled SVMs for data imbalance problems[M]. Berlin: Springer, 2006: 837-846.

[6] 陶新民, 張冬雪, 郝思媛, 等. 基于譜聚類下采樣失衡數(shù)據(jù)下SVM故障檢測[J]. 振動與沖擊, 2013, 32(16): 30-36. TAO X M, ZHANG D X, HAO S Y, et al. Fault detection based on spectral clustering combined with under-sampling SVM under unbalanced datasets[J]. Journal of Vibration and Shock, 2013, 32(16): 30-36.

[7] HE H B, EDWARDO A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(8): 1263-1284.

[8] LIU X Y, ZHOU Z H. Exploratory under-sampling for class-imbalance learning[J]. IEEE Transactions on Systems,Man and Cybernetics, 2009, 39(2): 539-550.

[9] LIN C F, WANG S D. Fuzzy support vector machines[J]. IEEE Transactions on Neural Networks, 2002, 13(2):464-71.

[10] HE H, GARCIA E A. Learning from imbalanced data[J]. IEEE Transactions on Knowledge & Data Engineering, 2009, 21(9):1263-1284.

[11] 陶新民, 郝思媛, 張冬雪, 等. 基于樣本特性欠取樣的不均衡支持向量機(jī)[J]. 控制與決策, 2013(7):978-984. TAO X M, HAO S Y, ZHANG D X, et al. Support vector machine for unbalanced data based on sample properties under-sampling approaches[J]. Control and Decision, 2013(7): 978-984.

[12] BATUWITA R, PALADE V. FSVM-CIL: fuzzy support vector machines for class imbalance learning[J]. IEEE Transactions on Fuzzy Systems, 2010, 18(3):558-571.

[13] 李航. 統(tǒng)計學(xué)習(xí)方法[M]. 北京: 清華大學(xué)出版社, 2012. LI H. Statistical learning method[M]. Beijing: Tsinghua University Press, 2012.

[14] 包志強, 崔妍. 電信客戶欠費模型評估[J]. 西安郵電大學(xué)學(xué)報, 2015(4):97-101. BAO Z Q, CUI Y. Telecom customer arrearages model evaluation[J]. Journal of Xi’an University of Posts and Telecommunications, 2015(4):97-101.

SVM classifier for telecom user arrears based on boundary samples-based under-sampling approaches

LI Chuangchuang, LU Guangyue, WANG Hanglong
National Engineering Laboratory for Wireless Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China

Telecom users’ arrears forecasting is a classification problem of unbalanced data set. To deal with the problem that the traditional SVM on the unbalanced date set had a low detection accuracy of minority class, a novel method was proposed. Based on the fact that the position of classification plane was determined by the boundary samples, the proposed method was implemented via removing some of samples closed to the classification plane to avoid the deficiency of the traditional SVM algorithm. Finally, the proposed method was compared with other approaches on unbalanced data sets. The simulation results show that the proposed method can not only increase the detection accuracy of minority but also improve the overall classification performance.

arrear, unbalance, support vector machine, boundary, under-sampling

TP181

：A

10.11959/j.issn.1000-0801.2017208

李創(chuàng)創(chuàng)（1991-），男，西安郵電大學(xué)無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室碩士生，主要研究方向為數(shù)據(jù)挖掘。

盧光躍（1971-），男，西安郵電大學(xué)無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室教授，主要研究方向為信號與信息處理、認(rèn)知無線電和大數(shù)據(jù)分析。

王航龍（1989-），男，西安郵電大學(xué)無線網(wǎng)絡(luò)安全技術(shù)國家工程實驗室碩士生，主要研究方向為數(shù)據(jù)挖掘。

2017-04-14；

：2017-07-06