基于FP-Growth改进算法的云服务器故障数据分析*

何 望，林果园

(1.中国矿业大学计算机科学与技术学院，江苏 徐州 221000;2.矿山数字化教育部工程研究中心，江苏 徐州 221000)

1 引言

近年来，由于本地化服务器的种种限制，越来越多的企业更倾向于将数据存储和业务部署等任务安放于云平台上。由于云平台服务种类多样，集群数量过大并且结构复杂，发生故障则是在所难免。商业云平台在实际使用时采取了容错备份机制以及紧急恢复机制[1]，主要目的在于用户使用云平台服务器时，即使发生了故障也可以保证云服务器的正常运行。但是，容错以及紧急恢复并不能保证云服务器完全可靠。因此，我们还需对云服务器运行时的数据指标进行关联性分析挖掘，协助云平台精准预测可能发生的云服务器故障。

FP-Growth算法是由频繁模式树FP-Tree生成频繁项集，将所扫描得到的数据库分成众多条件数据集，再从中挖掘关联规则[2]。针对该算法挖掘过程中的时空消耗问题，研究人员提出了许多算法，如 Agrawal 等人[3]提出的树-投影算法，Bhandari等人[4]提出的基于频繁模式树的改进Apriori算法,Rathee等人[5]提出的基于分布式Spark平台的FP-Growth算法改进研究。此类相关改进算法较多的优化改进策略在于如何在生成条件FP-tree的过程中降低时空消耗，在一定程度上有效地提高了算法的实际效率。但是，面临较大规模数据集时，条件FP-tree的生成过程本身就是最大的时空消耗，因此本文引入数组标记策略，对条件FP-tree在生成FP-tree之前进行剪枝降维，在实际挖掘过程中无需生成条件FP-tree，减少了时空消耗，提升了实际使用效率，使其适用于云服务器故障数据分析。

2 云服务器故障数据分析

对云服务器供应商而言，保障云服务器的正常运行是极为关键的[6 - 9]。而如何在用户使用云服务器的过程中尽可能早地检测出潜在的云服务器故障错误，是云平台企业面临的难题。在用户租用云服务器的过程中，云服务器供应商采集了大量的云服务器运行数据以及实时监控数据。本文的主要思想在于如何利用改进的FP-Growth关联规则对云服务器运行数据进行数据挖掘，找出云服务器运行数据与云服务器故障类型引发原因之间的关联规则，根据关联规则对云服务器运行调整作出合理推荐。

2.1 云服务器相关数据的获取与整合

云服务器运行数据是用户在租用云服务器时产生的相关数据，包括硬件资源状态，如CPU、内存以及网络带宽等使用量，其中资源状态以时间节点作为区分与云服务器实际运行状态相关联。如某一时刻下某一云服务器的运行状态对应该服务器资源的使用情况。其中云服务器的运行状态为历史数据中对云服务器过去某个时段的实际使用情况记录，在本文研究中，算法模型即以云服务器各个时间节点的运行状态为数据，挖掘数据与云服务器故障类型之间的关联规则。具体数据从操作系统层面、云服务器连接层面和请求响应层面3个维度进行采集。操作系统层面数据包括CPU利用率、内存利用率、云服务器端口占用情况、云服务器监听状态和I/O速率；云服务器连接层面数据包括云服务器连接的使用情况以及假死状态连接的比例；请求响应层面数据包括请求数/响应数、请求响应成功率和最近的请求在队列中等待时间。具体挖掘指标参数和指标符号如表1所示。

Table 1 Mining index parameters

2.2 云服务器数据分析方法

云服务器使用过程中产生的各种数据存储在云服务商对应的各类数据存储系统中，这些多源异构数据需要集中获取并整合为结构化数据，从而用于数据挖掘。同时我们根据云服务器的运行时特征，将云服务器运行状态分别预分类为响应异常RE(Response Exception)、系统异常SE(System Exception)和正常运行ON(Operation Normal)。其中，ON状态为云服务器正常运行，RE与SE为运行异常，运行异常类别为表1中指标参数的挖掘目标；SE按级别层面分为3类目标，即操作系统层面SEO、Web连接层面和请求响应层面SEA。具体相关检测指标如下所示：

(1)RE:响应异常是系统处于非健康状态情况中的一种，有异常行为的特征，不能正常响应用户的请求，根据云服务器运行时的特征及请求响应过程，将云服务器端口占用情况以及云服务器监听状态抽象为RE异常中的聚类指标，即定义RE={〈P,L〉}。

(2)SE:系统异常是危险信号，说明系统存在异常的可能性较高。将云服务器的这种运行状态记为SE状态。其中对应的聚类指标有：CPU利用率、内存利用率、I/O 速率、Web连接的使用情况、假死状态连接的比例、请求响应比、请求响应成功率及最近请求等待时间，即SE={〈C,M,I,N,B,RR,RS,RW〉}。但是，在云服务器正常使用过程中需要考虑各指标之间的相互影响问题，如当CPU和内存的占用率都同时过高超出阈值范围时，那么此时的最近请求等待时间同样较大可能也会超过阈值。对SE错误再按级别层面划分为3类，其中操作系统层面SEO={〈C,M,I〉}，Web连接层面SEW={〈N,B〉}，请求响应层面SEA={〈RP,RS,RW〉}，此时重新定义SE下3种错误指标聚类方法如式(1)所示。

(1)

(2)

(1)以毫秒为单位采集n个时刻的运行状态数据，每个时刻包含有对应的m个属性参数，attri=(P1,P2,…,Pm),0

(2)用n个时刻的属性均值作为每个属性的正常水平，记为avg。

(3)用式(2)中的Tj衡量某时刻中第j个属性的异常程度。

(3)ON:安全信号，表示当前云服务器正常安全运行的可能性较高，无异常信号发生，对应信号集为空，系统处于健康状态。定义ON={ }，即ON为空集。

3 FP-Growth改进算法

3.1 FP-Growth以及关联规则介绍

FP-Growth最早将频繁模式树(FP-Tree)这种树状结构引入频繁项挖掘[10]，树状图中的每个节点都对应频繁项集中的一个项， 同时，频繁事务集中的某一条事务对应树中由根到其子孙节点的某条路径，又因为其中部分路径会出现重叠，那么FP-Tree可以生成共享节点，由同一节点延伸来减少数据保存所需空间。FP-Tree本身的数据结构包含3个部分：原始数据、项头表(Htable)和节点链表。项头表分为2个域：项目名称(Item-Name)和项目支持数(Item-Pointer)[11]。项头表的生成能极大地帮助建立节点链表，节点链表本身由4个部分组成：节点名称(NodeName)、节点计数(NodeCount)、节点链(NodeLink)(用于指向树中具有相同节点名称的下一个节点)和根节点指针(RootNode)。给定原始云服务器故障数据集D以及所设定的最小支持度阈值mt，那么我们可以通过2次遍历生成所需要的FP-Tree。主要步骤为：(1)第1次扫描原始云服务器故障数据集D,得到所有频繁1-项集，同时删除低于最小支持度阈值的项，根据支持度计数降序排列后存入项头表，并记为Ld。(2)创建根节点“NULL”并第2次扫描原始云服务器故障数据集D,对应每项事务按支持度计数降序创建对应分支，若考虑为某个事务增加分支时，可以在其父节点上将其节点计数加1，再按左右子树处理相同根节点的子树创建问题。

3.2 基本概念

设基本指标参数项i为云服务器运行数据集的单条数据，DS={i1,i2,…,im}为m个不同参数项的集合。设事务X为DS的项目子集，即X⊆DS，则称X为一条事务集。事务集X中项的个数称为事务集X的维数或长度，若其长度为k，则称为k-项事务集。

定义1对于给定的最小支持度min_sup，若所求项集支持度大于或等于最小支持度min_sup，则称该项集满足最小支持度min_sup；同时，如果所求项集满足最小支持度，那么称其为频繁项集。记所得频繁k-项集为Lk。

定义2对于给定的云服务器故障数据集D={T1,T2,…，Tn}，Ti即为数据集中的某一条数据，1-项集L1={i1，i2，…，im},如果{i1，i2}是频繁2-项集，那么称i2是i1的频繁延伸项，所有i1的频繁延伸项组成的集合称为i1的频繁延伸项集。

定义3在给定的FP-Tree中，取根节点的子树中最靠前且可能存在频繁延伸项集的子树，记作第1棵子树。

定义4设有in<…

定义5给定已生成的索引FP-Tree，假设存在对应的约束子树，取约束子路径所对应的树节点，那么统计该节点在树中的出现频度之和即为约束子路径的支出度计数，记支持度计数为sup。

性质1由频繁项集所得的子集必是频繁的，反之，若项集的子集为频繁的，那么它所对应的所有超集未必频繁，若子集为非频繁，那么其所对应的所有超集都必定不频繁。

证明取任一频繁k-项集Lk:

(1)由Lk剪枝所得的直接子集Lk-1仍为频繁项集。且重复剪枝，得其所有子集都为频繁项集。

(2)由于剪枝所得子树对应的项集Li为频繁项集，无法推断其延伸树仍为频繁项集。设存在频繁项集项头表为{1，2，…，n}，如果存在频繁m-项集L={1，2，…，m}，那么以m为结尾生成的不包括L的所有项集必为非最大频繁项集，即其超集未必频繁。而若Li不频繁，那由其所得的延伸树必有这一段不频繁，故其本身不频繁，证毕。

□

性质2最大频繁项集必定为边界频繁项集。

1.2.1 对照组实施传统健康教育 对照组采用传统健康教育，具体如下：①入院宣教：向家属介绍患儿病情及注意事项。②饮食指导：根据患儿的年龄、饮食习惯制定个性化饮食方案，避免偏食。③运动指导：合理安排运动时间，掌握好适宜的运动量。④出院指导：真确监测血糖，并记录血糖值及胰岛素用量，为调整治疗方案提供依据。

证明给定一个项集为频繁项集，若其所有超集都为非频繁项集，那么由性质1可得，该项集必为边界频繁项集。

□

性质3假设k-项集Lk中存在非频繁t-项集Nt，则由Lk生成的频繁项集必在以Nt分割后的n个(k-1)-项集子集中。

证明给定k-项集{a1,a2,…,ak}，若{a1,a2}为频繁集，那么频繁集可能会在{a1,a2,…,ak}或{a2,a3,…,ak}中，若不存在，则与性质1矛盾。

□

3.3 改进的FP-Growth算法

相对于经典的FP-Growth算法而言，在直接挖掘时是通过循环遍历，将产生的各个新候选项集加入条件中，在此不仅仅是对于维数较高的项集，同时对于维数较低但其遍历过程中的最大频繁项集过多的项集，经典算法都会产生大量的候选项集。如若在较低维数数据集长度|DP|=10,Dmax(MFS)=2，那么由此产生的候选项集量接近10!，这样对于计算的时间和空间消耗都是极大的。

本文算法在生成FP-Tree的同时，以云服务器故障运行数据为事务集，先挖掘第1棵子树，然后将第1棵子树的所有子树与其他分支合并，同时删除第1棵子树，继续对新的逆向FP-tree递归调用挖掘过程，直至树只有1棵子树，且已经挖掘完该子树。同时，在逆向挖掘匹配中，可以很直观地看到，在删除剩余子树的同时，仍旧需要递归生成过多的条件树，而这一部分也是算法所占用时空最多的部分，那么可以将FP-tree的生成过程改为单向并且只保留指向对应父节点的指针，舍弃了生成树空间的同时引入约束子树的模式，可以节省1/3的空间占用，而同时减少了生成树的冗余结构，这样可以大大提升挖掘效率。FP-tree的基本数据结构包括原始数据，节点链表和FP-tree 3个部分。设in<…

3.4 算法流程

算法1逆向子树挖掘最大频繁项集算法

输入：原始云服务器故障数据集D的频繁模式树HFP,项头表Header(记项头表为HLd={1,2,…,t},t=|HLd|)，最小支持度阈值mt。

输出:原始云服务器故障数据集D中的最大频繁项集MLS,边界频繁延伸项集BLS。

1.MLS=∅,BLS=∅,BULS={1,2,…,endItem};/*BULS中可能为边界频繁项集，加入endItem保证其完备性*/

2.R为MLS的子集,设有非空集CLS;

3.root=find(fptree);/*找到第1棵子树的根节点Root,挖掘子树中所有的分支*/

4.for(allRinMLS) do{

5.CLS=CLS∪{R};/*根据性质1，遍历合并频繁子树*/

6.MLSi={k|k∈MLS&k的最后一项为i};

7.MLS=MLS-MLSi;/*连接剪枝寻找非频繁项集步骤*/

8. DELETER/*删除合并后的剩余子树,计算项集在原始数据中的支持度计数*/

9. for alln∈MLSdo{

10. ifn.supinD

11.MLS=MLS∪{n}

12. }

13. else{

14. ifn.sup==1 then{

15.BLS=BLS∪{n}

16. for(h=nmax;h≤t;h++)do{

17. ifh+n∉MLS的子集 then{

18.MLS=MLSU{h+n};

19. }

20. }

21. }

22. }

23. }

24.}

4 FP-Growth改进算法在云服务器故障数据中的分析应用

4.1 改进FP-Growth算法实验

为了评估改进后的FP-Growth算法的性能，与同为高效模式挖掘的改进的BICA算法[12]进行对比。改进BICA算法是一种快速可扩展的ADTree构建算法。利用以上算法在云服务器运行分析数据集上进行实验，根据实验结果对改进的FP-Growth算法进行时间评估，同时对改进前后的FP-Growth规则数进行对比实验。实验环境CPU为Intel Xeon E5，内存为64 GB，操作系统为 Windows Server 2012。

图1为FP-Growth算法改进前后和改进BICA算法随着最小支持度的变化，3个算法所用时间的对比结果图。通过实验结果可以看出，随着最小支持度的不断增大，改进FP-Growth算法的时间性能总体优于改进的BICA算法，经计算，改进FP-Growth算法运行时间相比改进的BICA算法平均少了12.5 s，相比于原FP-Growth算法运行时间平均节省24.4 s。使用改进BICA算法进行数据分析时，最终只能得到一个二分树，利用该二分树的每一个节点与分支进行分析，才能得出云服务器运行状态相关的一些结论，有时改进的BICA得出的二叉树并不能包含全部结果，会遗漏部分参数的影响。而FP-Growth算法挖掘给出的是一条条关联规则，只要给出确定的支持度与置信度，就能得到符合要求的全部规则，没有遗漏。通过关联规则能够更加直观与清晰地看出参数间的关联关系，对进一步的分析也更加方便。

Figure 1 Running time comparison of three algorithms图1 3个算法运行时间对比图

Figure 2 Rule numbers of two algorithms图2 2个算法的规则数变化图

图2给出了FP-Growth算法改进前后生成的规则数。通过实验结果可以看出，随着最小支持度的不断增大，规则数不断减少， 经实验计算可知，改进后的FP-Growth算法对无效规则的消除率最高可达37%。在实际应用分析时，用户往往需要耗费不小的精力去剔除这些无效规则，而利用本文算法，不仅可以避免用户在无效规则上的时间浪费，同时还极大地降低了用户对结果分析的难度。

4.2 挖掘结果分析

通过FP-Growth算法得出的关联规则能够帮助我们进行云服务器运行故障检测数据分析。以表1中数据为参数指标采集对应云服务器运行状态数据，该数据集可用样本数为308 880，其中，状态标记为ON的数据量为306 471，出现RE或SE状态的数据量为2 409，异常率约为0.78%。根据4.1节中性能评估结果可以看出，若支持度选择较小会导致算法运行时间过长，而支持度选择较大则虽然算法运行时间缩短，但是结果对应的有效关联规则数则会过少。为此在对支持度阈值进行选择时既要保证得到一定数量的关联规则，又要生成的关联规则便于进行针对性分析，因此实验设置支持度为0.25，置信度为0.35。根据改进FP-Growth算法的挖掘结果，对数据进行回查，查询挖掘出的关联规则中的频繁项对云服务器运行故障的影响。得到的关联规则结果如图3所示。

Figure 3 Association rule results(partial)图3 关联规则结果图(部分)

图3中结果采用[items(前项)，items(后项)，置信度]的输出形式对关联规则进行效用性分析。对结果进行粗略分析可以看出，所发生的错误情况较多是由RP故障引起的，而引起的故障类型较多是SEA故障。对各个关联规则如“RP+RS+RW→SEA”的置信度为0.62进行分析，可得出若针对SEA问题解决请求访问堵塞的情况，则可更好地保障云服务器高效安全地运行。

通过对结果的综合分析， 此时段云服务器运行数据故障较多是由于RW、RS和RP的请求响应层面问题引起的，请求堵塞的同时增加了服务器运行压力，引起CPU以及内容使用率的增大，导致服务器无法正常使用，此时则应更好地采取如增加带宽的措施来解决云服务器请求响应层面的问题。

限于篇幅，若对实验结果进一步讨论可继续追踪故障源，缩小数据集目标，引入服务器故障发生时间作为参数比较，同时对周期性服务器故障进行不同时间的数据对比。根据时间点查看服务器对应运行日志，还可更明确地找出引起云服务器故障问题的软件所在或是哪些访问目标及访问来源引发的访问激增从而导致访问请求阻塞，再解决目标程序的具体问题。

5 结束语

本文针对经典FP-Growth算法在构建以及挖掘过程所涉及的问题提出了改进优化策略，优化了FP-Growth在生成FP-Tree时的树状结构，引入数组约束标记，提升了算法的实际挖掘效率。改进后的FP-Growth算法有效提升了对云服务器运行时各项异常数据的关联分析效率，并且适用于大数据量的数据挖掘。该算法通过关联分析产生的频繁项集，能够较为准确地预测出云服务器运行状态的变化可能性情况，帮助云服务供应商提高服务质量，减少用户在使用时可能发生的云服务器故障。