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

李創創，盧光躍，王航龍

（西安郵電大學無線網絡安全技術國家工程實驗室，陜西 西安 710121）

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

李創創，盧光躍，王航龍

（西安郵電大學無線網絡安全技術國家工程實驗室，陜西 西安 710121）

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

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

1 引言

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

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

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

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

2 SVM理論

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

其中，C為懲罰因子，用于平衡結構風險和經驗風險， ξi為松弛變量。

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

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

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

最終得到分類決策函數為：

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

圖1 數據樣本比例為50∶1時的分類平面

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

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

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

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

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

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

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

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

對于多數類樣本而言，當γi≤0時表示樣本落入少數類一側，該樣本被錯分，γi＞1樣本在多

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

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

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

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

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

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

步驟5 將刪除后剩余的多數類樣本和少數類樣本進行重組構建新的訓練集。

步驟6 根據訓練得到新的分類器進行分類。

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

4 實驗分析及對比

4.1 不均衡數據分類效果指標

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

少數類樣本的檢測精度為：

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

多數類樣本的檢測精度為：

總體分類性能評估：

SE側重于考量少數類的正確率，SP側重于考量多數類的正確率，GM綜合了兩個指標體現分類器的整體分類性能。

4.2 實驗數據

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

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

6個實驗數據集特征信息見表2。

4.3 不同算法的性能比較

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

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

表2 不平衡數據集描述

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

表3 仿真結果對比

5 結束語

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

[1] 渠瑜. 基于 SVM 的高不平衡分類技術研究及其在電信業的應用[D]. 杭州: 浙江大學, 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] 陶新民, 張冬雪, 郝思媛, 等. 基于譜聚類下采樣失衡數據下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]. 控制與決策, 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] 李航. 統計學習方法[M]. 北京: 清華大學出版社, 2012. LI H. Statistical learning method[M]. Beijing: Tsinghua University Press, 2012.

[14] 包志強, 崔妍. 電信客戶欠費模型評估[J]. 西安郵電大學學報, 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

李創創（1991-），男，西安郵電大學無線網絡安全技術國家工程實驗室碩士生，主要研究方向為數據挖掘。

盧光躍（1971-），男，西安郵電大學無線網絡安全技術國家工程實驗室教授，主要研究方向為信號與信息處理、認知無線電和大數據分析。

王航龍（1989-），男，西安郵電大學無線網絡安全技術國家工程實驗室碩士生，主要研究方向為數據挖掘。

2017-04-14；

：2017-07-06