基于缺失數(shù)據(jù)BN參數(shù)學(xué)習(xí)的電信流失客戶預(yù)測算法

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

?

基于缺失數(shù)據(jù)BN參數(shù)學(xué)習(xí)的電信流失客戶預(yù)測算法

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

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

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

貝葉斯網(wǎng)絡(luò)；參數(shù)學(xué)習(xí)；數(shù)據(jù)缺失；最近鄰算法；定性約束

1 引言

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

貝葉斯網(wǎng)絡(luò)由有向無環(huán)圖和條件概率表兩部分組成[2]，經(jīng)過大約30年的發(fā)展，BN已經(jīng)廣泛應(yīng)用于人工智能與數(shù)據(jù)挖掘等熱門領(lǐng)域[3-5]。本文在電信客戶流失網(wǎng)絡(luò)結(jié)構(gòu)已知情況下，研究離散貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)的問題。

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

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

2 相關(guān)理論

2.1 貝葉斯網(wǎng)絡(luò)

本文將網(wǎng)絡(luò)中的所有參數(shù)分為兩類：第一類是父節(jié)點組合狀態(tài)相同而子節(jié)點狀態(tài)不同的參數(shù)；第二類是子節(jié)點狀態(tài)相同而父節(jié)點組合狀態(tài)不同的參數(shù)，如圖1所示。

圖1 BN節(jié)點參數(shù)分類示意

2.2 定性約束

根據(jù)被約束參數(shù)父節(jié)點的不同狀態(tài)，參數(shù)約束可以分為內(nèi)部約束和外部約束[11]。內(nèi)部約束是限制父節(jié)點組合狀態(tài)相同而子節(jié)點狀態(tài)不同時參數(shù)之間的關(guān)系；外部約束則是限制子節(jié)點狀態(tài)相同而父節(jié)點組合狀態(tài)不同時參數(shù)之間的關(guān)系。

圖2 兩節(jié)點貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)

3 含缺失數(shù)據(jù)的BN參數(shù)學(xué)習(xí)算法

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

3.1 缺失數(shù)據(jù)填充

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

下面給出NN算法填補缺失數(shù)據(jù)步驟。

步驟1 數(shù)據(jù)預(yù)處理，將初始數(shù)據(jù)分為完整數(shù)據(jù)與缺失數(shù)據(jù)兩部分，同時把缺失數(shù)據(jù)作為目標(biāo)數(shù)據(jù)。

步驟2 根據(jù)式（4）計算目標(biāo)數(shù)據(jù)與完整數(shù)據(jù)中每個樣本的馬氏距離。

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

步驟4 取個近鄰中對應(yīng)缺失屬性出現(xiàn)最多的值來填補缺失處。

步驟5 重復(fù)步驟2~4，直到所有數(shù)據(jù)完整。

3.2 內(nèi)部約束學(xué)習(xí)

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

獲得修正后的參數(shù)。內(nèi)部約束學(xué)習(xí)方法步驟如下。

步驟1 根據(jù)先驗知識判斷是否內(nèi)部約束滿足單調(diào)性，如果滿足單調(diào)性，則轉(zhuǎn)入步驟2。

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

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

3.3 外部約束學(xué)習(xí)

當(dāng)明確父節(jié)點對子節(jié)點的定性影響時，即知道網(wǎng)絡(luò)中不同父節(jié)點組合狀態(tài)值優(yōu)先順序滿足：

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

步驟1 根據(jù)先驗知識確定不同父節(jié)點組合狀態(tài)值的優(yōu)先順序并構(gòu)造出所有的下限集合。

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

3.4 新算法流程

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

步驟1 將樣本數(shù)據(jù)分為完整數(shù)據(jù)和缺失數(shù)據(jù)兩部分。

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

步驟3 統(tǒng)計樣本，獲得樣本統(tǒng)計值并根據(jù)式（3）求出初始參數(shù)。

步驟4 用內(nèi)部約束學(xué)習(xí)方法修正父節(jié)點組合狀態(tài)相同而子節(jié)點狀態(tài)不同的參數(shù)。

步驟5 用外部約束學(xué)習(xí)方法方法校正父節(jié)點組合狀態(tài)不同而子節(jié)點組合狀態(tài)相同的參數(shù)。

4 算法仿真

本次仿真試驗平臺為MATLAB R2010b，運行環(huán)境為Windows 7。仿真實驗由2部分組成：第4.1節(jié)從理論層面驗證本文算法的優(yōu)勢；第4.2節(jié)將該參數(shù)學(xué)習(xí)算法應(yīng)用到電信客戶流失預(yù)測中，用真實數(shù)據(jù)證實算法的可行性。

4.1 經(jīng)典模型仿真

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

圖3 草坪濕潤BN模型

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

表1 試驗約束

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

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

4.2 電信客戶流失預(yù)測

4.2.1 前期工作

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

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

圖7 電信客戶流失預(yù)測貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)

4.2.2 預(yù)測結(jié)果

試驗用550個樣本構(gòu)成訓(xùn)練集，樣本缺失率（missing completely at random，MCAR）為25%,應(yīng)用NN-DCE算法學(xué)習(xí)電信客戶流失預(yù)測網(wǎng)絡(luò)的參數(shù)。為了驗證算法的有效性，用561個測試樣本來檢驗該網(wǎng)絡(luò)的預(yù)測精度，貝葉斯網(wǎng)絡(luò)推理采用聯(lián)合樹算法[16]。電信客戶流失預(yù)測是一個不平衡數(shù)據(jù)集分類問題，一般定義少數(shù)類為，多數(shù)類為，F(xiàn)P是指將多數(shù)類錯分成少數(shù)類的樣本總數(shù)，F(xiàn)N是指將少數(shù)類錯分成多數(shù)類總數(shù)，TN表示分類正確的多數(shù)類樣本數(shù)，TP表示分類正確的少數(shù)類樣本數(shù)。用以下指標(biāo)來評價預(yù)測精度：

少數(shù)類預(yù)測精度：

多數(shù)類預(yù)測精度：

總體分類精度：

表4 客戶流失預(yù)測參數(shù)約束條件

仿真結(jié)果由表5給出。從表5中可以看出，應(yīng)用本文算法總體的預(yù)測精度略高于EM算法和qirEM算法，最為關(guān)注的潛在流失客戶的預(yù)測精度明顯高于EM算法及qirEM算法，所以本文算法能夠很好地應(yīng)用到電信數(shù)據(jù)貝葉斯網(wǎng)絡(luò)中進行參數(shù)學(xué)習(xí)。

表5 電信客戶流失預(yù)測仿真結(jié)果

5 結(jié)束語

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

[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] 張連文. 貝葉斯網(wǎng)引論[M]. 北京: 科學(xué)出版社, 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]. 計算機應(yīng)用, 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] 楊宇, 高曉光, 郭志高. 小數(shù)據(jù)集條件下基于數(shù)據(jù)再利用的BN參數(shù)學(xué)習(xí)[J]. 自動化學(xué)報, 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

陜西省工業(yè)科技攻關(guān)項目（No.2015GY-013）；陜西省工業(yè)科技攻關(guān)項目（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?），男，西安郵電大學(xué)陜西省信息通信網(wǎng)絡(luò)及安全重點實驗室碩士生，主要研究方向為數(shù)據(jù)挖掘。

盧光躍（1971?），男，博士，西安郵電大學(xué)陜西省信息通信網(wǎng)絡(luò)及安全重點實驗室教授，主要研究方向為信號與信息處理、認(rèn)知無線電和大數(shù)據(jù)分析。

王航龍（1989?），男，西安郵電大學(xué)陜西省信息通信網(wǎng)絡(luò)及安全重點實驗室碩士生，主要研究方向為數(shù)據(jù)挖掘。

李四維（1989?），男，西安郵電大學(xué)陜西省信息通信網(wǎng)絡(luò)及安全重點實驗室碩士生，主要研究方向為數(shù)據(jù)挖掘。