基于改進的K近鄰和支持向量機客戶流失預測

盧光躍,王航龍,李創(chuàng)創(chuàng),趙宇翔,李四維

(西安郵電大學 陜西省信息通信網(wǎng)絡(luò)及安全重點實驗室， 陜西 西安 710121)

有效預測客戶流失情況，可以提升客戶挽留率。電信客戶流失預測是一個典型的不平衡數(shù)據(jù)二分類問題[1]，客戶流失數(shù)據(jù)集的主要特點有：數(shù)據(jù)集存在極度的非均衡性；兩類樣本錯分代價之間的差異性大，可以用非均衡代價來刻畫；數(shù)據(jù)量大，維數(shù)高等[2]。

K近鄰(K-nearest neighbor,KNN)算法是一種簡單易行的數(shù)據(jù)挖掘分類方法、其基于類比思想的學習算法，每個類別都要具有相當數(shù)量及代表性的訓練樣本才能確保分類的精確度[3]，所以對平衡數(shù)據(jù)的分類效果好。由于分類時需要計算測試樣本到所有訓練集樣本之間的距離，所以計算量與存儲量都比較大，經(jīng)典的KNN算法很難在大數(shù)據(jù)樣本集上得以良好應用[4]。當數(shù)據(jù)集里兩類樣本數(shù)量不均衡時，會導致判決規(guī)則傾斜于多數(shù)類樣本，從而會降低少數(shù)類的檢測精度[5-6]。

支持向量機(support vector machine,SVM)是數(shù)據(jù)挖掘領(lǐng)域比較經(jīng)典的分類器，在1995年由Vapnik提出[7]，是一種基于統(tǒng)計學習理論和結(jié)構(gòu)風險最小化理論的機器學習方法[8]，它在解決高維非線性數(shù)據(jù)集的分類問題時表現(xiàn)出了優(yōu)良的分類性能[9]。SVM算法在樣本均衡的數(shù)據(jù)集上有較好的分類效果，當數(shù)據(jù)集樣本不均衡時，分類效果較差，分類的結(jié)果偏向于多數(shù)類樣本[10]，從而使少數(shù)類樣本的漏檢概率增大。通過進一步對傳統(tǒng)SVM錯分樣本的具體分布進行分析，發(fā)現(xiàn)其錯分的樣本點基本聚集在分類平面附近[11]。

電信客戶流失預測模型中流失客戶的檢測精度是人們關(guān)注的焦點，然而流失客戶數(shù)目遠遠少于非流失客戶數(shù)目。針對這類樣本非均衡的問題，數(shù)據(jù)方面常見的解決方法為隨機過取樣算法(Over SVM)和隨機欠取樣算法(Under SVM)[12]。隨機過取樣算法采用隨機復制訓練集中少數(shù)類樣本，從而使采樣后的訓練集中兩類樣本數(shù)目保持均衡[13]。然而，隨機增加樣本不僅使計算量增加，而且使分類間隔減小，難以正確檢測，泛化能力變差。隨機欠取樣算法采用隨機去除訓練集中的多數(shù)類部分樣本，從而使兩類樣本數(shù)量基本相當[14]。由于欠取樣算法并不能夠代表原多數(shù)類樣本的完備信息，所以有可能使得多數(shù)類檢測精度極度降低，算法的穩(wěn)定性欠佳。改進的SVM-KNN組合算法EDKSVM(euclidean distance nearest neighbor and support vector machine)[15],雖然減少了KNN的鄰域樣本數(shù)量，但是支持向量中仍存在噪聲點，這些噪聲點作為鄰域樣本同樣會降低少數(shù)類的分類精度，雖然降低了KNN算法對近鄰參數(shù)的依賴，但由于鄰域樣本本身的不均衡性和噪聲點的存在，少數(shù)類的精度同樣會降低。

針對KNN、SVM、Under SVM、Over SVM和EDKSVM算法的不足，本文將給出一種基于加權(quán)K近鄰和支持向量機(weighted K-nearest neighbor and support vector machine,W-KSVM)的電信客戶流失預測算法，先利用SVM刪除支持向量集中多數(shù)類錯分的支持向量，然后將剩余的全部支持向量作為加權(quán)KNN的鄰域樣本，融合二者的優(yōu)勢進行分類。

1　KNN和SVM算法

1.1　KNN算法

KNN算法是非參數(shù)學習中一種簡單而有效的方法，為最近鄰算法的拓展。它以N個訓練樣本作為鄰域樣本，計算測試集中每個點到鄰域樣本的距離，對距離進行排序，找出距離最近的K個訓練樣本，即K個最近鄰，然后對選出的兩類樣本進行統(tǒng)計，哪個類別近鄰數(shù)目多，則該樣本點就會判定為該類。

1.2　SVM算法

支持向量機的核心是求解最優(yōu)分類超平面。假設(shè)訓練樣本為(xi,yi)(i=1,2,…,n),其中，xi∈l代表l維樣本，yi∈{-1,+1}代表類標簽。通常將樣本通過映射函數(shù)Φ(x)從原始的空間映射到高維特征空間，來提高分類精度。在高維映射空間中尋找分類超平面wΦ(x)+b=0,然后利用結(jié)構(gòu)風險最小化理論通過優(yōu)化分類平面的權(quán)向量w和b，得到最大分類間隔平面。

問題的核心是在以下約束條件下求解目標函數(shù)的最小值，其本質(zhì)是一個凸二次規(guī)劃問題

(1)

其中，C為懲罰系數(shù)，C越大錯分數(shù)目越少，但泛化能力下降，通過調(diào)節(jié)C能平衡泛化能力和訓練誤差[16]，能控制對錯分的樣本的懲罰程度。ξi為松弛因子，表示訓練樣本不滿足約束的容忍程度。Φ(x)為映射函數(shù)。

利用拉格朗日乘子法將問題轉(zhuǎn)化為其對偶問題進行求解，即

(2)

其中αi為拉格朗日乘子，滿足KKT(Karush-Kuhn- Tucker)條件

αi{yi[wΦ(xi)+b]-1-ξi}=0,(C-αi)ξi=0。

(3)

求解式(2)，可得

且分類超平面為

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

(4)

2　針對非平衡樣本的W-KSVM算法

W-KSVM算法基于刪除多數(shù)類錯分支持向量后剩余的支持向量作為加權(quán)KNN的鄰域樣本，在特征空間用SVM和加權(quán)KNN組合算法進行分類，充分地利用了二者的優(yōu)勢對非均衡數(shù)據(jù)進行分類。

在訓練數(shù)據(jù)集上運用標準的SVM得到支持向量集J。由式(2)求得αi,若0<αi

yi[wΦ(xi)+b]-1-ξi=0，
ξi=0,

所以

yi[wΦ(xi)+b]=1，

于是，樣本xi是標準的支持向量。

得到多數(shù)類和少數(shù)類的支持向量后，計算支持向量樣本點到分類超平面的距離

(5)

對于多數(shù)類支持向量而言，當γi≤0時，樣本落入到少數(shù)類一側(cè)，故該樣本被錯分。可以刪除掉γi≤0的多數(shù)類樣本點，但分類超平面會發(fā)生偏移。為了防止分類平面的過度偏移，影響整體分類性能，對于稀疏數(shù)據(jù)集刪除的多數(shù)類個數(shù)控制在該類的5%以內(nèi)。少數(shù)類精度提升的同時也達到去掉噪聲點的目的。將除去噪聲點后的支持向量集記為J′,其元素作為加權(quán)KNN的鄰域樣本，不僅能提升少數(shù)類的檢測精度，還能提升KNN的運算效率。

計算測試集中各樣本到分類平面的距離

(6)

其中n為測試集樣本個數(shù)。為了降低分類超平面附近樣本點的錯分率，當其距離大于閾值ε時，用SVM算法對樣本點進行分類；當其距離小于閾值ε時，用加權(quán)KNN進行分類。當用加權(quán)KNN進行分類時，計算測試集里各樣本點xi到J′中各樣本點的距離

d(x,xi)=‖Φ(x)-Φ(xi)‖2=
K(x,x)-2K(x,xi)+K(xi,xi)。

(7)

其中,高斯核函數(shù)

K(x,xi)=e-σ‖x-xi‖2，

σ為核寬度，控制函數(shù)的徑向作用范圍，可與SVM算法保持一致。

將距離排序，取出最近的K個樣本點對類別進行統(tǒng)計。KNN判決方式為少數(shù)服從多數(shù)，由于鄰域樣本的不均衡，現(xiàn)將KNN判決方式進行改進加權(quán)，即少數(shù)類的個數(shù)達到

就可判別為少數(shù)類，反之判為多數(shù)類。其中,β由支持向量中兩類樣本的比例決定，K為近鄰參數(shù)。

W-KSVM算法具體步驟如下。

步驟1將數(shù)據(jù)集劃分為訓練集Dtrain和測試集Dtest。

步驟2計算Dtrain中樣本距分類平面的距離，得出支持向量機集J。

步驟3根據(jù)式(7)計算出的距離，刪除錯分為多數(shù)類支持向量的點(γi≤0)，將剩余支持向量記入集合J′,作為加權(quán)KNN的鄰域樣本。

步驟4當Dtest=?時，此算法結(jié)束；否則，記xi∈Dtest。

步驟5根據(jù)式(6)計算xi到超平面的距離di。人為給定ε，如果|di|≥ε，則根據(jù)式(4)得到xi的類別f(xi);否則，在特征空間根據(jù)式(7)計算距離d(x,xi)，使用加權(quán)KNN對xi進行分類。

步驟6從Dtest中刪除xi,返回步驟4。

3　實驗分析

3.1　不均衡數(shù)據(jù)分類效果評判指標

針對電信客戶流失的問題，錯誤判斷一個流失客戶的代價遠遠大于不流失客戶的代價，因此更加關(guān)注的是客戶流失的檢測精度(少數(shù)類的檢測精度)。假定少數(shù)類樣本為正例樣本，多數(shù)類樣本為負例樣本，以TP表示將正例樣本判斷正確的數(shù)目，TN表示將負例樣本判斷正確的數(shù)目，F(xiàn)P表示將負例樣本判斷錯誤的數(shù)目，F(xiàn)N表示將正例樣本判斷錯誤的數(shù)目，混淆矩陣如表1所示。

表1　二分類問題的混淆矩陣

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

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

整體性能評估指標

GM綜合了兩個指標，只有當多數(shù)類樣本和少數(shù)類樣本的分類精度都比較高的情況下，GM的值才會達到最大。所以,GM指標可以動態(tài)調(diào)整多數(shù)類和少數(shù)類之間的精確率，在可以接受的范圍內(nèi)通過降低多數(shù)類的精確度來提升少數(shù)類的精確度，有利于解決類似于客戶流失、客戶欠費和信用卡欺詐等實際問題。

3.2　實驗數(shù)據(jù)描述及準備

實驗數(shù)據(jù)分別為5個UCI不平衡數(shù)據(jù)集[17]Churn、Wine、Haberman、Pima-Indians、Waveform和某省的電信數(shù)據(jù)集[18]。其中數(shù)據(jù)集Churn定義客戶不享有電信企業(yè)提供的全部服務即為流失客戶。電信客戶消費數(shù)據(jù)的基本屬性包括是否VIP、用戶屬性、付費方式、是否主動停機等，其中數(shù)值屬性可以直接使用，對非數(shù)值屬性進行one-hot編碼。某省電信原始數(shù)據(jù)集處理后的部分樣本如表2 所示。

表2　某省電信用戶部分樣本

原始數(shù)據(jù)集屬性之間存在較大差異，這會降低算法的學習速度和精確度，故需對數(shù)據(jù)進行歸一化處理，即取

所用實驗數(shù)據(jù)集具體特征如表3所示。

表3　數(shù)據(jù)集描述

3.3　不同算法的性能比較

為了驗證所提算法在不均衡數(shù)據(jù)集上的可行性、有效性，分別與Normol SVM、Under SVM、Over SVM、EDKSVM、KNN算法在所提數(shù)據(jù)集上進行比較試驗。為了保證算法的公平性，在每次實驗中對所有算法選用相同的訓練集和測試集，每次實驗的訓練集和測試集分別占總體樣本的80%和20%。仿真環(huán)境和工具分別為Windows 8.1 、MATLAB R2013a和LIBSVM。

仿真結(jié)果如表4所示。對比可知，Over SVM在Churn數(shù)據(jù)集上少數(shù)類的精度為0.010 0，原因是過采樣造成少數(shù)類的分類間隔變小，導致算法泛化能力變差,精確度下降。但所提算法W-KSVM在實驗數(shù)據(jù)集上的少數(shù)類和整體精確度均有不同程度的提升，克服了其他算法在不平衡數(shù)據(jù)集上的不足，完全融合了SVM和KNN算法的優(yōu)勢。

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

4　結(jié)語

針對SVM、KNN對電信客戶流失預測精度低的問題，給出了W-KSVM算法。在5個UCI不平衡數(shù)據(jù)集和某省電信數(shù)據(jù)集上的仿真結(jié)果顯示，所給算法在對少數(shù)類的檢測精度和整體分類性能明顯優(yōu)于其他算法。不均衡數(shù)據(jù)中少數(shù)類數(shù)目太少，分類器很難區(qū)分出少數(shù)類樣本和噪聲樣本，今后研究的重心將是如何更精確更有效地去除噪聲樣本，進一步提升算法的精確度。