基于缺失數據BN參數學習的電信流失客戶預測算法

趙宇翔，盧光躍，王航龍，李四維

?

基于缺失數據BN參數學習的電信流失客戶預測算法

趙宇翔，盧光躍，王航龍，李四維

（西安郵電大學陜西省信息通信網絡及安全重點實驗室，陜西 西安 710121）

針對電信客戶流失預測問題，在數據缺失情況下，基于貝葉斯網絡（Bayesian network，BN），用最近鄰算法填補缺失數據，并將兩類定性約束融入貝葉斯網絡參數學習過程，用以提高流失客戶預測精度。仿真及實際數據分析結果表明，所提算法較經典的期望最大化（expectation maximization，EM）算法有明顯優勢，在犧牲代價較小的忠誠客戶預測精度的情況下，得到了更高的流失客戶預測精度。

貝葉斯網絡；參數學習；數據缺失；最近鄰算法；定性約束

1 引言

隨著移動網絡的快速發展，手機成為人與人溝通的重要方式。與此同時，未入網的新用戶數量也在急劇下降。據估計，吸引一個新用戶所花費的成本是挽留一個老客戶所花費成本的5~6倍。所以，為了獲取更大的利潤，電信企業越來越重視潛在流失客戶[1]。企業希望盡早發現這部分人群，及時做出有針對性的調整并成功挽留這部分客戶。為了準確預測流失客戶，很多學者采用貝葉斯網絡（Bayesian network，BN）進行分類。

貝葉斯網絡由有向無環圖和條件概率表兩部分組成[2]，經過大約30年的發展，BN已經廣泛應用于人工智能與數據挖掘等熱門領域[3-5]。本文在電信客戶流失網絡結構已知情況下，研究離散貝葉斯網絡參數學習的問題。

傳統電信客戶流失參數學習采用最大似然估計（maximum likelihood estimation，MLE）方法，但由于電信數據時常伴隨有信息缺失，無法直接利用MLE方法逼近BN真實參數。對缺失數據進行參數估計的經典算法是期望最大化（expectation maximization，EM）算法[6]，但EM算法對初始點的選取較為敏感、容易陷入局部最優解，而且在數據量較小時參數學習精度低。目前，很多學者通過引入先驗知識來提高含缺失數據的BN參數學習精度。例如，參考文獻[7]提出將EM算法與定性約束相結合，用定性的先驗知識構造懲罰函數、用樣本數據構造似然函數；然后將懲罰函數與似然函數結合構造出目標函數；最后利用CEM（constrained EM）算法求解BN參數。參考文獻[8]則將保序回歸算法融入EM算法每次迭代的步中，并在此基礎上，提出一種復雜度更低的快速保序最大期望（qirEM）算法。參考文獻[9]將參數學習問題視為凸優化模型，把最大熵函數與EM算法相結合構造凸優化問題。通過分析上述參考文獻發現：參考文獻[7]方法中懲罰函數隨約束類型的變化而改變，并且其權重是人為賦予的，故該方法結果受人為影響；參考文獻[8]的方法并不能保證在有限的參數空間中收斂到局部最優解；參考文獻[9]方法可行域比較精確，但估計參數大多分布在可行域邊緣位置，這樣便浪費了不等式約束中所包含的信息。因此，如何在有缺失數據的樣本中進行參數學習，仍然值得探討。

本文首先用改進的近鄰算法解決缺失數據的填充問題，然后在此基礎上將先驗知識融入BN參數學習過程中，用兩類定性約束來調整估計參數。實驗結果表明：在樣本缺失率不同時，與傳統的EM算法相比，本文算法學習得到精度更高的BN參數。

2 相關理論

2.1 貝葉斯網絡

本文將網絡中的所有參數分為兩類：第一類是父節點組合狀態相同而子節點狀態不同的參數；第二類是子節點狀態相同而父節點組合狀態不同的參數，如圖1所示。

圖1 BN節點參數分類示意

2.2 定性約束

根據被約束參數父節點的不同狀態，參數約束可以分為內部約束和外部約束[11]。內部約束是限制父節點組合狀態相同而子節點狀態不同時參數之間的關系；外部約束則是限制子節點狀態相同而父節點組合狀態不同時參數之間的關系。

圖2 兩節點貝葉斯網絡結構

3 含缺失數據的BN參數學習算法

在電信數據中，由于機械或人為原因會造成部分屬性缺失，若直接用這類數據集進行BN參數學習將難以保證參數的精度。為此，本節首先利用最近鄰（-nearest neighbor，NN）算法填補缺失數據；接著用貝葉斯MAP思想進行參數的內部約束學習；最后用保序回歸模型[12]進行參數的外部約束學習。

3.1 缺失數據填充

NN算法起初是用于解決分類問題，它為了找到與目標樣本相似度最高的個樣本，也就是距離目標樣本最近的個樣本，因此距離的表示形式很重要。當屬性之間具有聯系或量綱不同時，馬氏距離比歐氏距離更適合度量鄰近性，所以本文選取馬氏距離作為NN算法中的距離度量形式[13]。

下面給出NN算法填補缺失數據步驟。

步驟1 數據預處理，將初始數據分為完整數據與缺失數據兩部分，同時把缺失數據作為目標數據。

步驟2 根據式（4）計算目標數據與完整數據中每個樣本的馬氏距離。

步驟3 對所有進行排序，選取其中個馬氏距離最小的樣本作為目標數據的近鄰。

步驟4 取個近鄰中對應缺失屬性出現最多的值來填補缺失處。

步驟5 重復步驟2~4，直到所有數據完整。

3.2 內部約束學習

采用二階矩法擬合，計算過程如下：

獲得修正后的參數。內部約束學習方法步驟如下。

步驟1 根據先驗知識判斷是否內部約束滿足單調性，如果滿足單調性，則轉入步驟2。

步驟2 根據依據式（6）求出各個參數取值的上下界，然后用Monte Carlo法基于均勻分布進行抽樣。

步驟4 利用式（12）得到校正后的參數。

3.3 外部約束學習

當明確父節點對子節點的定性影響時，即知道網絡中不同父節點組合狀態值優先順序滿足：

然后刪除所有下限集合中與集合相交的部分，并從節點的全部父節點組合狀態中刪除集合中的組合狀態，即：

步驟1 根據先驗知識確定不同父節點組合狀態值的優先順序并構造出所有的下限集合。

步驟3 依據式（17）和式（18）進行處理。

3.4 新算法流程

鑒于新算法用到了最近鄰算法以及內、外部約束條件，本文稱之為基于最近鄰—雙重約束的參數估計（-nearest neighbor-dual constrained estimation，NN-DCE）方法?？偨Y前文的參數求解過程，新算法的總流程如下。

步驟1 將樣本數據分為完整數據和缺失數據兩部分。

步驟2 應用最近鄰算法找出與缺失數據相似度高的完整數據，并填補對應的缺失屬性。

步驟3 統計樣本，獲得樣本統計值并根據式（3）求出初始參數。

步驟4 用內部約束學習方法修正父節點組合狀態相同而子節點狀態不同的參數。

步驟5 用外部約束學習方法方法校正父節點組合狀態不同而子節點組合狀態相同的參數。

4 算法仿真

本次仿真試驗平臺為MATLAB R2010b，運行環境為Windows 7。仿真實驗由2部分組成：第4.1節從理論層面驗證本文算法的優勢；第4.2節將該參數學習算法應用到電信客戶流失預測中，用真實數據證實算法的可行性。

4.1 經典模型仿真

采用草坪濕潤模型（如圖3所示），該模型已被廣泛應用于BN參數學習算法的評估[14]，先驗知識見表1。

圖3 草坪濕潤BN模型

首先依原始網絡真實參數隨機生成一個數據集；然后使完整樣本數據隨機缺失，分別構造樣本缺失率為20%、30%、40% 3種情況；最后采用KL散度[15]衡量算法準確性。KL散度值越小，表明估計參數與真實參數越接近，其計算式如下：

表1 試驗約束

實驗結果如圖4~圖6所示，圖4~圖6中給出了KL散度值隨樣本大小的變化情況。從結果可以看出：在樣本量相同時，傳統的EM算法KL散度小于NN-MLE算法，qirEM算法KL散度小于傳統的EM算法,NN-DCE算法KL散度小于qirEM算法。反映出數據缺失情況下EM算法比簡單地進行數據填補然后求參數的最大似然估計要更加優越，融入單一約束的qirEM算法比EM算法性能更好，而融入雙重約束的NN-DCE算法性能最好。綜上所述，應用NN-DCE算法可以很好地將先驗知識融入參數學習，獲得精度更高的參數。

圖4 樣本缺失20%時算法KL散度

4.2 電信客戶流失預測

4.2.1 前期工作

圖5 樣本缺失30%時算法KL散度

圖6 樣本缺失40%時算法KL散度

圖7 電信客戶流失預測貝葉斯網絡結構

4.2.2 預測結果

試驗用550個樣本構成訓練集，樣本缺失率（missing completely at random，MCAR）為25%,應用NN-DCE算法學習電信客戶流失預測網絡的參數。為了驗證算法的有效性，用561個測試樣本來檢驗該網絡的預測精度，貝葉斯網絡推理采用聯合樹算法[16]。電信客戶流失預測是一個不平衡數據集分類問題，一般定義少數類為，多數類為，FP是指將多數類錯分成少數類的樣本總數，FN是指將少數類錯分成多數類總數，TN表示分類正確的多數類樣本數，TP表示分類正確的少數類樣本數。用以下指標來評價預測精度：

少數類預測精度：

多數類預測精度：

總體分類精度：

表4 客戶流失預測參數約束條件

仿真結果由表5給出。從表5中可以看出，應用本文算法總體的預測精度略高于EM算法和qirEM算法，最為關注的潛在流失客戶的預測精度明顯高于EM算法及qirEM算法，所以本文算法能夠很好地應用到電信數據貝葉斯網絡中進行參數學習。

表5 電信客戶流失預測仿真結果

5 結束語

圍繞電信流失客戶預測中BN參數學習問題，本文提出NN-DCE參數學習算法。本文采用改進的NN算法填充缺失數據，然后在完整的數據基礎上融入兩類約束條件完成BN參數學習。仿真結果表明：所提算法性能優于EM算法，能有效提高電信流失客戶預測精度。由于先驗知識是否可靠會直接影響約束的正確性，進而影響參數學習的結果。在今后的工作中，將考慮先驗知識的不確定性，研究如何緩解錯誤的先驗知識對參數學習結果造成的負面影響。

[1] JAMIL S, KHAN A. Churn comprehension analysis for telecommunication industry using ALBA[C]//International Conference on Emerging Technologies(ICET 2016), Oct 1, 2016, Islamabad, Pakistan. Piscataway: IEEE Press, 2016.

[2] PEARL J. Probabilistic reasoning in intelligent systems: networks of plausible inference[J]. Computer Science Artificial Intelligence, 1988, 70(2): 1022-1027.

[3] WAGNER S. A Bayesian network approach to assess and predict software quality using activity-based quality models[J]. Information and Software Technology, 2016, 52(11): 1230-1241.

[4] PENDHARKAR P C, KHOSROWPOUR M, RODGER J A. Application of Bayesian network classifiers and data envelopment analysis for mining breast cancer patterns[J]. Journal of Computer Information Systems, 2016, 40(4): 127-131.

[5] COOK J, LEWANDOWSKY S. Rational irrationality: modeling climate change belief polarization using Bayesian networks[J]. Topics in Cognitive Science, 2016, 8(1): 160-179.

[6] LAURITZEN S L. The EM algorithm for graphical association models with missing data[J]. Computational Statistics & Data Analysis, 1995, 19(2): 191-201.

[7] LIAO W, JI Q. Learning Bayesian network parameters under incomplete data with domain knowledge[J]. Pattern Recognition, 2009, 42(11): 3046-3056.

[8] MASEGOSA A R, FEELDERS A J, GAAG L C V D. Learning from incomplete data in Bayesian networks with qualitative influences[J]. International Journal of Approximate Reasoning, 2015, 69(C): 18-34.

[9] CORANI G, CAMPOS C P D. A maximum entropy approach to learn Bayesian networks from incomplete data[M]// Interdisciplinary Bayesian Statistics. Berlin: Springer International Publishing, 2015: 69-82.

[10] 張連文. 貝葉斯網引論[M]. 北京: 科學出版社, 2006.

Zhang L W. Introduction of Bayesian network[M]. Beijing: Science Press, 2006.

[11] ZHOU Y, FENTON N, ZHU C. An empirical study of Bayesian network parameter learning with monotonic influence constraints[J]. Decision Support Systems, 2016, 87(C): 69-79.

[12] FEELDERS A, VAN D G L C. Learning Bayesian network parameters under order constraints[J]. International Journal of Approximate Reasoning, 2005, 42(1-2): 37-53.

[13] 劉星毅. 基于馬氏距離和灰色分析的缺失值填充算法[J]. 計算機應用, 2009, 29(9): 2502-2504.

LIU X Y. ImprovedNN algorithm based on Mahalanobis distance and gray analysis[J]. Journal of Computer Applications, 2009, 29(9): 2502-2504.

[14] 楊宇, 高曉光, 郭志高. 小數據集條件下基于數據再利用的BN參數學習[J]. 自動化學報, 2015, 41(12): 2058-2071.

YANG Y, GAO X G, GUO Z G. Learning BN parameters with small data sets based reutilization[J]. Acta Automatica Sinica, 2015, 41(12): 2058-2071.

[15] KULLBACK S, LEIBLER R A. On Information and Sufficiency[J]. Annals of Mathematical Statistics, 1951, 22(22): 79-86.

[16] HU X J, YANG S L, MA X J. Inference structure and construction algorithms of Bayesian network based on junction tree[J]. Acta Simulata Systematica Sinica, 2004, 16(11): 2559-2558.

A prediction algorithm of telecom customer churn based on Bayesian network parameters learning under incomplete data

ZHAO Yuxiang, LU Guangyue, WANG Hanglong, LI Siwei

Shaanxi Key Laboratory of Information Communication Network and Security, Xi’an University of Posts and Telecommunications, Xi’an 710121,China

Aiming at prediction of telecom customer churn, a novel method was proposed to increase the prediction accuracy with the missing data based on the Bayesian network. This method used-nearest neighbor algorithm to fill the missing data and adds two types of monotonic influence constraints into the process of learning Bayesian network parameter. Simulations and actual data analysis demonstrate that the proposed algorithm obtains higher prediction accuracy of churn customers with the loss of less cost prediction accuracy of loyal customers, outperforms the classic expectation maximization algorithm.

Bayesian network, parameter learning, data missing, nearest neighbor algorithm, qualitative constraint

TP181

A

10.11959/j.issn.1000?0801.2018018

2017?07?11；

2017?09?26

陜西省工業科技攻關項目（No.2015GY-013）；陜西省工業科技攻關項目（No.2016GY-113）

Industrial Research Project of Science and Technology Department of Shaanxi Province（No.2015GY-013), Industrial Research Project of Science and Technology Department of Shaanxi Province (No.2016GY-113)

趙宇翔（1993?），男，西安郵電大學陜西省信息通信網絡及安全重點實驗室碩士生，主要研究方向為數據挖掘。

盧光躍（1971?），男，博士，西安郵電大學陜西省信息通信網絡及安全重點實驗室教授，主要研究方向為信號與信息處理、認知無線電和大數據分析。

王航龍（1989?），男，西安郵電大學陜西省信息通信網絡及安全重點實驗室碩士生，主要研究方向為數據挖掘。

李四維（1989?），男，西安郵電大學陜西省信息通信網絡及安全重點實驗室碩士生，主要研究方向為數據挖掘。