2019, Vol. 40
面对日益激烈的市场竞争以及多变的用户需求, 如何最大程度地降低用户流失率成为电信运营商首要关注的问题.当今解决这一问题的主流方式是运用数据挖掘技术对移动用户的行为进行分析[1-5], 建立用户流失预测模型, 对用户流失情况进行预测, 并对可能流失的用户采取相应的挽留措施.
用户流失预测问题本质上是对用户分类的问题:流失和未流失.在用户流失预测领域, 主要的分类方法有逻辑回归[6]、贝叶斯网络[7]、决策树[8]、支持向量机[9], 以及神经网络等[10-12].BP神经网络(BP neural network, BPNN)是目前应用最为广泛的神经网络模型, 并具有完备的理论体系.
BPNN作为一种样本数据有标签情况下的预测和分类模型, 可以被应用于解决用户流失的预测问题, 但其存在全局搜索能力相对较弱, 对初始网络权重非常敏感等问题.为了提高BPNN的全局搜索能力, 本文提出用一种改进的遗传算法(improved genetic algorithm, IGA)来初始化BPNN的权值和阈值, 使其更靠近全局最优, 从而提高算法的准确率.IGA提出了一种自适应的交叉概率和变异概率计算策略, 提高了GA寻找全局最优解的能力.基于IGA优化的BPNN预测模型的预测准确率有了很大提高.
1 算法设计 1.1 遗传算法的改进标准GA在复杂优化问题及多峰值的函数优化求解过程中存在收敛速度慢、容易陷入局部最优的问题, 本文针对移动用户话单数据的特点以及要解决的问题, 基于标准GA, 提出一种拥有更强全搜索能力的改进GA.
1.1.1 染色体编码的设计染色体编码是GA优化BPNN的关键.具体的编码过程以一个有具体结构的BPNN为例, 图 1是一个3-3-3结构的BP网络, 其中包含了输入层、输出层以及单隐层.
|
图 1 3-3-3 BPNN结构图 Fig.1 Structure of a 3-3-3 BPNN |
染色体基因向量的分量是由该网络模型中所有权重和阈值构成的, 起初基因向量的各个分量是随机分配的值, 这些值的范围应该是在要解决问题的值域内.染色体的基因向量是由该BPNN的4个参数矩阵编码构成的, 这些矩阵具体定义如下：
|
(1) |
|
(2) |
|
(3) |
|
(4) |
式中: V和W是两个权值矩阵; th和to分别是隐含层和输出层的阈值矩阵.
这4个矩阵编码生成染色体基因向量的公式如下, 其中Xi是第i个染色体的基因向量：
|
(5) |
本文采用浮点数编码方案, 染色体向量的维度由BPNN中权值和阈值的数量决定, 而权值和阈值的数量由BPNN的结构决定.
1.1.2 适应度函数的确定BPNN的均方误差E是评价BPNN预测模型的重要指标.E值越小, 表示BPNN的预测性能越好.在GA中, 个体的适应度值是评价个体表现的重要指标, 假设第i个个体的适应度值为Fi, 其对应的BPNN的均方误差为E(Xi), 则个体的适应度函数为
|
(6) |
从上述公式可以发现, 个体的表现越好, 其适应度值就会越小; 使种群中最优个体适应度值接近0是GA不断进化的目标.
1.1.3 选择操作的设计选择操作是从父代中选出优秀的个体直接进入到子代.不同于交叉操作和变异操作, 选择操作并不会破坏染色体中的基因.在本文中, 染色体的适应度值是BPNN的输出误差, 个体表现越好, 其适应度值的绝对值就应该越接近于0, 因此标准的轮盘赌法并不适用.个体被选中概率的计算公式为
|
(7) |
式中:Fi是第i个个体的适应度值; l是调节因子, 用以控制适应度反比值的量纲, 保证计算的合理性.从式(7)中可以发现, 个体被选中的概率与其适应度值成负相关.在实际计算过程中, 样本数量比较大, 不存在个体适应度为0的情况, 因此不需要考虑适应度为0导致的计算错误.
1.1.4 交叉操作的设计在实际情况中发现, 标准GA中基因按照固定概率进行交叉操作的策略并不可取.因此, 本文提出一种自适应的交叉概率, 主要想法是根据个体适应度值及迭代次数, 对个体的交叉概率进行自适应调整:对于表现较好(适应度值较低)的个体, 适当降低交叉概率, 避免破坏优良的基因; 如果个体表现较差, 则增大该个体的交叉概率, 让其更多地进行交叉操作, 对其进行优化, 破坏其表现一般的基因结构.另外, 为了保证算法的收敛性、前期的种群多样性及后期的局部搜索能力, 这种交叉概率也应随着算法的迭代不断减小.在算法迭代的前期, 应赋予一个较大的交叉概率, 保证种群的多样性, 加快算法的搜索速度; 在算法迭代的后期, 种群的个体表现趋于稳定, 大部分的优秀基因已经被确定, 为了优秀基因的延续, 应适当降低交叉概率, 确保算法在极值点处不会出现震荡, 保证算法的收敛性.
基于上述考虑, 个体交叉概率的设定如下:
|
(8) |
式中:t是算法当前的迭代次数; T是算法的总迭代次数; pci是第i个个体在第t次进行交叉时的概率; Fi是个体的适应度值; Fmin是种群当前表现最好的个体的适应度值; pcmax是最大交叉概率, 取值为0.6;pcmin是最小交叉概率, 取值为0.3.从式(8)中可以发现, 个体的交叉概率会随着适应度值的降低而降低, 以保证优秀的基因有更大的概率延续; 个体的交叉概率也会随着迭代次数的增加而降低, 以保证算法的稳定性.
1.1.5 变异操作的设计变异操作的目的是在算法迭代前期保证算法的全局搜索能力, 在算法迭代后期保证算法的局部搜索能力和稳定性, 因此, 本文个体进行变异操作的概率和进行交叉操作的概率在设计上是相同的, 都是根据个体的适应度值及算法的迭代次数来决定概率的大小, 具体计算公式如下:
|
(9) |
式中变量t, T, Fi, Fmin都和式(8)相同; pmi是第i个个体在第t次迭代时基因发生变异的概率; pmmax是最大变异概率, 取值0.005;pmmin是最小变异概率, 取值0.001.
基于BPNN权值和阈值的特点和取值范围, 本文采用在基因取值范围内随机取值的变异操作, 当个体染色体的某个基因值要发生变异时, 在[-1, 1]之间随机选取一个实数值来替换发生变异的基因位.这种基于随机取值的小概率变异操作有时会给算法的全局搜索能力带来很大的提高.
1.1.6 种群规模和迭代次数的确定种群规模的设计和实际问题的复杂度有关.为了保证算法的效率, 一般情况下30个染色体就可以满足大部分需求, 但由于本文用GA对BPNN的权值和阈值进行初始化, 待定变量比较多, 所以本文选取的种群规模为100, 以保证复杂问题中解的全局最优性.
迭代次数往往要设定得多一些, 以保证算法收敛.根据实验观察, 算法迭代到30次之后趋于平稳, 为了保证算法的完全收敛, 本文设定GA迭代次数为100次.
1.2 遗传算法优化BPNN的基本过程首先根据问题的复杂度确定GA的种群规模、迭代次数及部分参数, 然后确定种群个体的染色体编码规则, 以后的步骤如下:
1) 将个体的基因转化成BPNN的权值和阈值, 通过BPNN的前馈传播计算种群个体的适应度值.
2) 根据适应度值对个体进行选择操作, 根据适应度值和迭代次数对个体进行交叉和变异操作, 并将保留下来的个体作为下一代.
3) 根据终止条件判断种群是否完成进化, 如未完成则回到步骤1).
IGA-BP算法的伪代码如下:
1: for each chromosome do
2: Randomly initialize chromosome vector Xi
3: end for
4: while maximum iterations or the fitness of any individual is attained do
5:Decode the chromosome vector Xi into matrices(1), (2), (3), and(4), and train the BP neural network using data samples
6:Update the fitness value of Xi by Eq.(6)
7: for i = 1 to M do //M是初始种群的个数
8: Select operation by Eq.(7)
9: end for
10: for i = 1 to M/2 do
11: Crossover operation by Eq.(8)
12: end for
13: for i = 1 to M do
14: Mutation operation by Eq.(9)
15: end for
16:end while
2 仿真实验与分析 2.1 数据样本以辽宁移动公司的真实通话记录作为数据样本.每条数据有上百个属性, 但由于大部分的属性和用户流失的相关性很低, 所以没必要将所有属性都作为样本属性.采用关联性分析算法提取样本属性, 最终选取入网时间、基本费总和、通话时长、通话次数、长途费总和、呼叫类型比例, 以及掉话比率这6个与用户流失相关性最高的属性作为BPNN的输入属性, 如表 1所示.
|
表 1 仿真实验的用户属性 Table 1 Customer features of simulation |
1) 隐层神经元数量的确定.
一个拥有S型传递函数的单隐层和线性输出层的BPNN可以近似模拟任何函数.考虑到网络结构的复杂度和整个网络的训练时间, 在设计BPNN的结构时选择单隐层.
网络的性能受隐层神经元数量的影响.在单隐层的前提下, 可以通过增加隐层神经元的数量来适当提高网络的预测准确度.采用cut-and-try方法来确定隐层神经元的数量.起初设置较少的数量, 训练网络并记录网络的预测准确度, 然后再逐渐增加隐层神经元的数量.用同样的样本数据进行训练, 能使网络输出误差最小的隐层神经元数量就是最终要确定的.
隐层神经元的数量范围可按下式计算:
|
(10) |
式中:l, n和m分别是隐层、输入层和输出层的神经元数量; a是调节因子, 通常取1到10.
隐层神经元数量与网络性能的关系通过对比实验得到(见表 2), 在确定隐层神经元数量时, BPNN的训练函数和传递函数都是统一的.从表 2中能发现, 当隐层神经元数量为8时, IGA-BP算法的网络误差最小, 即网络预测准确度最好.
|
|
表 2 隐层神经元数量对误差的影响 Table 2 Effect of the number of hidden-layer neurons on error |
2) 训练函数的选择.
在仿真实验中, BPNN, GA-BP和IGA-BP都采用相同的网络结构:单隐层, 隐层神经元的数量为8, 隐层的传递函数为S型函数; 输出层的传递函数是线性激活函数.三种算法的各层传递函数是一致的.
有多种训练算法可以用来训练BPNN, 最具代表性的有标准梯度下降法(LGD)、有动量的梯度下降法(GDM)、Fletcher-Reeves共轭梯度法(CGF), LM梯度下降法(LM)等.这些不同的训练方法针对IGA-BP算法的性能表现见图 2.
|
图 2 不同训练函数的性能 Fig.2 Performance of different training functions |
从图 2能发现, GDM算法有明显的震荡, 并在网络迭代60次之后趋于稳定, 当网络稳定时, GDM算法输出误差最大.LGD算法的曲线更平滑, 但当网络收敛时, 它的表现和GDM算法一样差.CGF算法的曲线是最陡的, 并且有着最快的收敛速率, 当迭代到10次左右时网络就收敛了, 但CGF算法的误差仍然很高, 这说明CGF算法很容易陷入局部最优且无法逃逸.LM算法无论是在准确率还是在收敛速度上都表现出了最好的性能, 因此选择LM作为网络的训练函数.
2.3 算法参数的选取由于BPNN的权值和阈值的取值范围在[-1, 1]之间, 所以GA算法中每个染色体基因向量的分量随机初始值都在[-1, 1]之间.因为已经确定BPNN输入神经元的数量为6, 隐层神经元的数量为8, 因此可得每个染色体基因向量的维度为6×8+8×1+8×1+1=65.
2.4 算法的输出误差分析将IGA-BP的性能与标准BP以及GA-BP进行对比实验.GA-BP算法中, 个体进行交叉及变异的概率都是固定的, 具体参数为:种群规模30, 进化次数100, 交叉概率0.4, 变异概率0.002.
三种算法的输出误差如图 3所示.
|
图 3 三种算法的学习误差 Fig.3 Learning error of three algorithms |
在三种算法中, BPNN的结构和传递函数都是一样的, 并且训练函数都为LM梯度下降函数.从图 3中可以发现, 标准BP输出误差最大, 这是由于其全局搜索能力差, 网络性能依赖权值和阈值的随机初始值; IGA-BP算法的输出误差最小.IGA-BP算法与GA-BP算法在前三次迭代时曲线几乎是重合的, GA-BP在之后的训练过程中平稳地进行搜索, 而IGA-BP算法曲线有一个明显的抖动, 这是因为IGA-BP摆脱局部最优的能力要强于GA-BP, 所以IGA-BP算法在用户流失预测问题上表现出了很好的性能.
从收敛速度上看, IGA-BP算法比标准BP和GA-BP算法的收敛速度都快.IGA-BP算法大约迭代10次就收敛了, 而GA-BP大约迭代17次才收敛, 标准BP算法大约迭代20次才收敛.这是因为IGA-BP的交叉和变异概率与迭代次数有关, 因此算法前期有着很强的全局搜索动力, 然后又会很快进入稳定状态.
2.5 算法的预测准确率分析算法预测准确率定义为样本数据正确分类的百分比, 即TP(true positive)值.三种算法对用户流失的预测结果见表 3、表 4.可见, IGA-BP算法针对移动用户数据集展现了很强的流失预测能力.
|
|
表 3 三种算法的预测分类矩阵 Table 3 Prediction classification matrix of three algorithms |
|
|
表 4 三种算法的预测值指标 Table 4 Prediction indexes of three algorithms |
TP是用户流失预测中最重要的指标, 基于BP, GA-BP以及IGA-BP三种算法, 用户数据6个属性对TP值的影响如图 4所示.
|
图 4 基于不同算法的不同属性对TP值的影响 Fig.4 Effect of different attributes on TP based on different algorithms |
为了消除指标之间的量纲影响, 对数据进行了min-max标准化处理以方便指标之间的对比.由图 4可以发现, 当用户的基本费总和、通话次数、通话时长以及呼叫类型比例这4个属性值很低时, 三种算法都有较高的TP值.但处理分布在两端的数据时, 三种算法的表现都相对较差.GA-BP曲线和BP曲线在很多分布区域都是重合的, 这是因为标准GA的遗传操作类似于一种随机策略, 在进行交叉和变异操作时, 没有考虑个体的适应度值, 很可能破坏了好的基因结构, 因此没有起到很好的优化作用.相比于BP和GA-BP, IGA-BP的TP值始终是最高的, 这意味着IGA-BP模型的预测准确率也是最高的.
由图 4还可以发现, 随着入网时间的变化, 3条曲线有着相同的震荡趋势; 入网时间较早和较晚的用户更有可能流失.IGA-BP算法仍然有着最高的TP值.此外, 当用户遭遇频繁掉话时, 用户流失的可能性更大.相比其他两种算法, IGA-BP有着更高的TP值.
综上, 相比BP和GA-BP, IGA-BP算法在TP指标上有显著提高.
3 结语本文提出用改进遗传算法来初始化BPNN的权值和阈值, 弥补其全局搜索能力的不足.由于BPNN待确定的权值和阈值变量较多, 并且精度要求高, 本文遗传算法的染色体采用浮点数编码, 并将网络的输出误差作为个体的适应度函数.改进遗传算法中提出一种自适应概率的交叉操作和变异操作, 根据个体的适应度值以及种群当前迭代次数来计算自适应概率.为了保证算法的稳定性, 种群发生交叉和变异的概率也会随着进化的次数逐渐变小.通过对预测准确率和网络输出误差的分析, 证明了基于改进遗传算法优化BPNN的预测模型具有良好的性能.
| [1] |
Luo C, Zeng J, Yuan M, et al.
Telco user activity level prediction with massive mobile broadband data[J]. ACM Transactions on Intelligent Systems & Technology, 2016, 7(4): 1–30.
|
| [2] |
Coussement K, Lessmann S, Verstraeten G.
A comparative analysis of data preparation algorithms for customer churn prediction:a case study in the telecommunication industry[J]. Decision Support Systems, 2017, 95: 27–36.
DOI:10.1016/j.dss.2016.11.007 |
| [3] |
Keramati A, Jafari-Marandi R, Aliannejadi M, et al.
Improved churn prediction in telecommunication industry using data mining techniques[J]. Applied Soft Computing, 2014, 24: 994–1012.
DOI:10.1016/j.asoc.2014.08.041 |
| [4] |
Kim K, Jun C H, Lee J.
Improved churn prediction in telecommunication industry by analyzing a large network[J]. Expert Systems with Applications, 2014, 41(15): 6575–6584.
DOI:10.1016/j.eswa.2014.05.014 |
| [5] |
Vafeiadis T, Diamantaras K I, Sarigiannidis G, et al.
A comparison of machine learning techniques for customer churn prediction[J]. Simulation Modelling Practice and Theory, 2015, 55: 1–9.
DOI:10.1016/j.simpat.2015.03.003 |
| [6] |
Lu N, Lin H, Lu J, et al.
A customer churn prediction model in telecom industry using boosting[J]. IEEE Transactions on Industrial Informatics, 2014, 10(2): 1659–1665.
DOI:10.1109/TII.2012.2224355 |
| [7] |
Kisioglu P, Topcu Y I.
Applying Bayesian belief network approach to customer churn analysis:a case study on the telecom industry of Turkey[J]. Expert Systems with Applications, 2011, 38(6): 7151–7157.
DOI:10.1016/j.eswa.2010.12.045 |
| [8] |
García S, Fernández A, Herrera F.
Enhancing the effectiveness and interpretability of decision tree and rule induction classifiers with evolutionary training set selection over imbalanced problems[J]. Applied Soft Computing, 2009, 9(4): 1304–1314.
DOI:10.1016/j.asoc.2009.04.004 |
| [9] |
Farquad M A H, Ravi V, Raju S B.
Churn prediction using comprehensible support vector machine:an analytical CRM application[J]. Applied Soft Computing, 2014, 19: 31–40.
DOI:10.1016/j.asoc.2014.01.031 |
| [10] |
Pendharkar P C.
Genetic algorithm based neural network approaches for predicting churn in cellular wireless network services[J]. Expert Systems with Applications, 2009, 36(3): 6714–6720.
|
| [11] |
Subramanian K, Suresh S.
A meta-cognitive sequential learning algorithm for neuro-fuzzy inference system[J]. Applied Soft Computing, 2012, 12(11): 3603–3614.
DOI:10.1016/j.asoc.2012.06.012 |
| [12] |
Oreski S, Oreski G.
Genetic algorithm-based heuristic for feature selection in credit risk assessment[J]. Expert Systems with Applications, 2014, 41(4): 2052–2064.
DOI:10.1016/j.eswa.2013.09.004 |