基于布谷鸟搜索优化马尔可夫的文件热度预测

王 彪,王克俭+，何振学，高万豪，魏雪川

(1.河北农业大学 信息科学与技术学院，河北 保定 071001；2.天津城建大学 控制与机械工程学院，天津 300384；3.国网河北省电力公司 石家庄供电公司，河北 石家庄 050052)

0 引 言

云计算平台搭建在大规模服务器之上，通过系统中存储的大量数据提取有价值的信息[1]。在对分布式文件系统的研究中，如何有效提高系统的可靠性和访问效率成为当今的研究热点[2]。现有分布式文件系统副本管理机制分为静态管理和动态管理[3]。静态管理因副本数目固定，难以确保高热度文件的访问效率[4]。动态管理根据资源环境的动态变化动态调整副本的数目，可提升文件访问效率和存储空间利用率[5]。

文献[6]针对静态副本策略的缺点，提出基于灰色模型的预测模型，根据文件最近的访问特征预测数据未来访问热度。文献[7,8]依据时间局部性原理，最近访问的文件短时间内会被再次访问。文献[9,10]采用组合预测模型应对单一预测模型的局限性。文献[11]神经网络模型在建立过程中需要设置准确的层次和大量的样本空间进行训练，文件热度预测效率低。文献[12]采用了灰色马尔可夫模型，利用C均值聚类法分析仪器设备信号数据频谱轮廓峰值幅值序列残差状态，对残差预测值进行修正，但效果不是很好。

综上，目前已有的文件热度预测方法都存在一些缺点，本文采用布谷鸟搜索(cuckoo search，CS)优化的马尔可夫模型修正无偏灰色预测文件热度，消除灰色预测的固有偏差，提高预测精度。此方法首先采集文件历史访问热度，通过优化算法利用新陈代谢思想，对文件热度序列进行预测更新，利用最新的热度数据对未来热度进行预测。

1 CS无偏灰色马尔可夫模型理论

1.1 灰色预测模型

灰色模型主要用于具有不确定因素的灰色系统进行预测。其优点是可以利用少量不完整信息，通过建立数学模型并对数据未来的发展趋势做出预测的一种模型。灰色预测模型定义请参见文献[13]。本文采用灰色预测模型应用于文件热度预测，将文件历史访问热度作为预测数据序列，通过对预测序列进行简单变换，从中寻找数据变动规律并对文件未来的热度发展趋势进行预测。

1.2 马尔可夫模型

马尔可夫模型根据在不同状态之间转移的概率对未来的发展趋势进行预测。系统在状态转换过程中第n次转换后的状态决定于前一次(第n-1次)结果状态。马科夫模型定义请参见文献[14]。本文关于文件热度预测，因用户访问的随机性和数据热度变化的突发性是两个不可避免的因素，导致灰色预测可能会产生较大的误差，故采用马尔可夫模型预测未来一段时间内文件访问量所在的状态区间，对文件热度预测偏差进行修正，提升模型预测准确性。

1.3 布谷鸟搜索算法

布谷鸟搜索(CS)算法最早由杨新社和S.戴布提出，是一种自然启发式算法。具有收敛速度快、效率高、调节参数少等优点[15,16]。该方法基于布谷鸟的寄生性育雏和Lévy飞行。

这个算法的灵感来自布谷鸟的寄生繁殖行为。在自然界中，布谷鸟在寄主鸟的巢中产卵，被识破后破坏或干脆放弃巢。为了降低蛋被破坏或遗弃的可能性，一些布谷鸟模仿寄主鸟蛋的颜色和图案；一些布谷鸟选择合适的时间孵化蛋，通常比寄主鸟早，拿走一些寄主鸟的蛋，以增加后代获得更多食物的机会。寻巢过程可以看作Lévy飞行，一个Lévy飞行是一种随机行走。

该算法的实现将所有的寄主巢看作是一代，每个巢穴都携带鸟蛋作为解决方案。目标就是通过不断地迭代寻找潜在的最优解来取代现有的方案。本文用到的是对多目标优化的布谷鸟搜索算法。基于以下3个准则：

(1)每只布谷鸟一次产下k枚蛋(代表k个目标的解决方案)，将它们放在随机选择的某个寄主巢穴中；

(2)每一代中有高质量蛋(解决方案)的最佳巢穴被带到下一代；

(3)可用的寄主巢数量是固定的，寄主发现布谷鸟放的蛋概率为pa∈(0,1)。 发现后，寄主可以消灭该蛋或放弃旧巢另建新巢。

本文运用CS搜索算法对马尔可夫状态区间与实际值和预测值之间的关系进行发掘，寻找该区间最合适的值对预测值进行修正。

2 CS动态无偏灰色马尔可夫模型建模

灰色马尔可夫模型在针对小样本和指数分布样本数据预测方面应用广泛，但是该模型仍然存在不足。本章主要从灰色模型参数、马尔可夫修正值计算、预测数据序列更新3个方面对该模型进行优化并对该模型进行建模。

2.1 无偏灰色预测

本文利用无偏灰色预测模型对文件访问量序列进行处理并预测未来文件热度。该模型通过对灰色发展系数a和灰作用量u的优化，解决了灰色预测固有偏差，达到减小预测误差的目的。借助灰色模型的灰色发展系数a和灰作用量u确定无偏灰色预测模型的原始数据序列拟合模型，对文件未来热度进行预测。

无偏灰色模型的原始数据序列为某文件在前m个相等时间段内的文件访问量。建模过程如下：

(2)对该文件历史访问量序列进行累加处理：累加序列的首个数据直接获取原始序列的第一个数据，从第二个数据开始将原始序列的第n个数据与第n+1个数据相加作为新序列的第n个数据。根据式(1)得到累加序列

(1)

(3)准指数检验与光滑性检验

准指数检验，级比表示见式(2)

(2)

光滑性检验，时间序列光滑比表示见式(3)

(3)

(4)累加序列的变化趋势我们可以近似使用式(4)白化微分方程来描述

(4)

该微分方程中参数a和u为待识别常量，其中a称为发展系数，u为灰作用量。

(5)模型求解：采用最小二乘法求待识别常量的估计值。

(5)

模型表示见式(6)

(6)

(6)求解白化微分方程，得到无偏灰色预测的离散时间响应函数，见式(7)

(7)

(7)基于灰色模型中参数估计值a、u得到无偏灰色预测模型中的参数b、A，消除固有偏差，见式(8)

(8)

(8)无偏灰色预测模型的原始数据的拟合模型见式(9)

(9)

通过对灰色预测模型参数的更新，无偏灰色预测模型无需在进行预测数据累减还原，简化了建模步骤同时还提升了系统的运算效率。

2.2 CS优化的马尔可夫对预测值修正

在马尔可夫模型中，选取灰色预测值所处状态区间的中心值对其进行误差修正。但仅考虑状态区间的中心值可能会忽略其它误差分布信息的影响，状态区间的中心值并不能适当代表误差状态。因此，为马尔可夫模型对灰色预测值进行更加准确地修正，本文借助布谷鸟搜索算法更深入地挖掘状态区间信息，以识别更具代表性的修正值，而不是状态区间的中心值。CS优化马尔可夫模型具体建模过程如下。

2.2.1 马尔可夫模型

马尔可夫模型见式(10)所示

X(m)=X(t)P(m-t),t=1,2,3,…,m-1

(10)

其中，状态X(m)为初始状态概率向量X(t)经过(m-t)个时刻之后的状态概率向量，向量P为一步状态转移概率矩阵。

2.2.2 状态区间划分

本文由相对精度来确定状态区间的划分，相对精度为实际值和预测值差值，即残差。每个数据根据自己的相对精度区分所处状态。为了适应不同数据序列预测，首尾状态的区间的边界值选取相对精度的最值。状态个数一般取3个～5个，将目标区间等分。

2.2.3 状态转移概率矩阵构造

这里采用频率近似等于概率的思想，利用式(11)计算状态转移概率

(11)

假设划分了n个状态区间，nij(k) 表示热度预测值所在状态区间Ei经k步转移到状态区间Ej的次数，ni为所在状态区间Ei的数据个数。按照上述方法计算即可得到k步状态转移概率矩阵，如式(12)所示

(12)

2.2.4 CS优化马尔可夫修正值

假设状态区间i为 [ai,bi]， 经布谷鸟搜索算法优化后的修正值计算见式(13)

vi=αiai+(1-αi)bi,i=1,2,…,n

(13)

本小节优化的目标就是对每个状态区间寻找合适的马尔可夫修正值，前提就是寻找到每个区间的参数α。当α=0.5时，修正值就是状态区间中心值。下文介绍布谷鸟搜索算法寻找状态区间决策系数α=(α1,α2,…,αn)。

(1)布谷鸟搜索区间决策系数

CS搜索方式是基于Lévy飞行的直接搜索和基于宿主鸟在巢中发现外来蛋的概率的随机搜索。

如下方法实现局部随机搜索，计算方式见式(14)

(14)

本文借助Lévy飞行实现全局随机搜索，由于方向的选择是随机的，各方向的概率都是一样的，服从均匀分布。还要确定需要搜索范围，Lévy分布要求大概率落在值比较小的地方，于是借助Mantegna算法可以近似满足这样的情况，具体建模过程见式(15)、式(16)、式(17)

(15)

(16)

(17)

(2)迭代过程中最优方案判定

(18)

(3)修正值计算

由第一步搜索出的最优决策区间系数α=(α1,α2,…,αn)， 计算每个状态区间的修正值。根据式(13)，得到修正值v1,v2,…,vn

(19)

2.2.5 马尔可夫对预测值修正

通过k步状态转移概率矩阵和当前数据所处状态Ei及其初始向量X(0)， 可以对下一时刻预测值所处状态进行预测。假设max(Pij)=Pik， 则认为下一时刻数据最有可能由状态Ei转向Ek。

本文根据相对精度划分每个状态区间，根据此相对精度来对无偏灰色预测对预测值进行修正，减小误差，增加预测的准确度，如式(20)所示

(20)

2.3 数据更新

数据更新是对灰色预测模型的预测序列进行优化。本文采用的是基于灰色预测模型对文件热度进行预测，该模型特点就是针对小样本对数据预测。数据访问有时间局部性特征，当前被频繁访问的文件在未来的一定段时间内存在较高的概率会被再次访问，因此较旧的数据不能很好地反映当前的趋势变化。

分布式系统中的文件每时每刻都在被访问，随时会产生最新的文件访问量数据。为了能够更加准确地利用历史热度对未来的文件热度进行预测，根据文献[8]新数据权重高的思想，采用新陈代谢思想对原始数据序列进行等维处理。更新数据序列时，将最新的文件热度加入原始序列中，剔除陈旧的热度数据，如式(21)。根据文件统计周期循环以上操作，即可更新文件热度预测序列。这样能更好地反映文件最近热度的变化趋势，更准确地预测文件未来热度

(21)

3 实验与结果分析

3.1 原始数据及预处理

为达到真实模拟用户对文件访问量的变化，本文数据来源于某社交通讯软件实时数据，如表1所示。表中数据是每隔10 min收集一次用户对某文件的访问量(文件热度)，以此作为处理前的原始数据序列。以此数据序列来验证几种预测模型的拟合效果，做出分析比对。

表1 某社交通讯平台用户对热点新闻实时访问量

首先对原数列进行累加得到新的数列，对新数列进行光滑和指数规律检测。通过式(2)、式(3)以及检验标准，验证该累加序列为光滑序列，并且具有指数规律，可以采用灰色模型对未来数据进行预测。

3.2 实验设置及实验评价

3.2.1 实验参数设置

经过多次实验对CS算法的参数进行调整，最终确定综合考虑算法效率和准确度对参数进行了设定。见表2。

表2 CS算法各项参数设置

3.2.2 实验相关评价

本文对预测模型的拟合程度评价指标为相对误差绝对值的平均值(MAPE)，如式(18)所示。根据MAPE既可以判定模型预测效果是否良好，又可以作为模型之间效果比较的参考。

3.3 实验过程及实验结果分析

3.3.1 状态区间划分

根据灰色模型和马尔可夫模型基本原理，代码实现相关功能，并对数据进行了处理。实现了几种模型依据原始数据序列对未来文件访问量的预测。其中灰色预测模型发展系数a=0.0061，灰作用量u=385.1279。无偏灰色预测模型参数b=-0.0061，A=383.9498。根据各模型对原始数据序列的预测拟合结果，通过计算残差我们取残差的两个最值作为状态区间的边界，并将其等分为3个区间，对应E1，E2，E3这3个状态。此处的状态个数与CS算法参数宿巢容量数值相同。如表3、表4分别给出了状态区间的具体划分和无偏灰色马尔可夫模型的残差。

表3 马尔可夫修正状态区间划分

表4 无偏灰色模型预测值与实际值的残差和具体状态

根据表4数据显示每个数据所处状态，在这里给出一步状态转移概率矩阵。状态转移概率矩阵用于对未来访问量的预测，以提前应对文件访问量突增，及时对文件副本进行动态调整

3.3.2 马尔可夫修正值

默认的马尔可夫修正值为区间中值，状态区间的中心值并不能适当代表误差状态。借助布谷鸟搜索算法更深入地挖掘状态区间信息，以识别更具代表性的修正值。经过布谷鸟算法优化的修正值由式(19)计算。

通过CS算法迭代寻优，当迭代次数为100次的时候已经可以显示出预期效果。综合考虑实验准确性和计算效率，本文将迭代200次，得到α=(α1,α2,α3)=(0.9883,0.4183,0.4889)， 得到优化马尔可夫修正值。v=(-84.81，-4.56,42.93)。 这里有一点需要注意的是得到的马尔可夫修正值仅适合该预测序列的预测值残差修正。当预测序列经过新陈代谢思想更新后，还需要再次预测α最优解，才能达到优化预测残差的最优效果。

3.3.3 CS优化的无偏灰色预测模型分析

表5展示了本文预测修正模型与默认情况下的拟合效果对比，以此评判该预测模型的优化效果。残差由实际值减去拟合值得到。相对残差为残差绝对值与实际值的比值，最后采用MAPE对3种模型拟合度进行评测。

表5 3种灰色预测模型修正后拟合效果对比

如图1所示，给出了灰色模型(grey model)、无偏灰色模型(unbiased grey model)、灰色马尔可夫模型(grey Markov)、无偏灰色马尔可夫模型(unbiased grey Markov)、CS无偏灰色马尔可夫模型(CS unbiased grey Markov)与实际值之间的拟合效果。其中1个～8个周期是拟合值，第9个周期是预测值。

图1 5种灰色模型拟合效果对比

实验结果表明，灰色马尔可夫模型和无偏灰色马尔可夫模型的MAPE都在4.4%左右，说明马尔可夫修正模型对缩小灰色模型的误差有很好的效果。而经过CS算法优化后的马尔可夫模型对误差的修正又有所提升，MAPE仅为3.08%。

为了进一步说明CS无偏灰色马尔可夫模型在小样本预测情景下，能够有效的对下一时刻数据进行快速、准确的实时预测。我们采用同一组的数据进行实验，对未来的几个时刻访问量进行预测，将其与BP神经网络和文献[17]中灰色神经网络模型进行对比，以MAPE作评价指标。

实验将本文方法与几种常见预测方法通过预测值的MAPE进行比较，预测值拟合程度如表6所示。得出结论：灰色模型和无偏灰色模型在预测准确性方面几乎相同，但是无偏灰色预测模型预测结果就是预测值，无需进行累减操作，计算效率会略高。CS无偏灰色马尔可夫模型在小样本的情景下，MAPE要小于其它模型，比其它几种模型MAPE平均值降低了2.26%。对数据预测准确度更高。说明该模型可以更好地利用少量数据预测短期内未来时刻的数据变化，对提前应对未来环境变化，采取相应措施提供有力依据。

表6 几种模型的预测结果拟合度汇总/%

4 结束语

本文采用CS优化的马尔可夫模型修正无偏灰色模型预测值，采用新陈代谢思想更新数据，使预测序列保持最新文件热度值，对预测文件下一时刻热度起到重要作用。马尔可夫模型修正可以有效降低灰色预测模型因数据波动而产生的误差，提高了预测数据的准确度，经过CS优化的马尔可夫模型可以更好缩小误差值。通过与几种预测模型对比，CS优化的灰色马尔可夫模型平均相对残差最小，说明该模型在数据量少的情况下，能够对文件热度预测达到较好效果。接下来的研究会根据文件热度进行副本个数的调整，降低热点文件访问冲突和执行时间，提升系统效率和资源利用率。