信息系统的数据库指标多维度异常发现算法分析

郝成亮 刘超 刘洪波 臧洪睿 王宇

摘要：当今，信息化建设快速发展，数据库作为信息系统的重要组成部分，是信息系统稳定运行的重要保障条件之一。随着数据库种类和数量的不断增加以及IT架构越来越复杂，也直接增加了信息系统运维人员的工作量和工作难度，同时提出了更高的运维要求，从而使得数据库的故障处理难度急剧增长。为了提升数据库缺陷分析能力，故障处置，本文将分析比较五种数据库指标多维度异常的相关算法，并在这些算法的基础上提出更加适合电力信息系统的数据库指标多维度异常发现的算法。

关键词：信息系统;数据库;多维度异常;检测算法

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2020）35-0018-03

开放科学（资源服务）标识码（OSID）：

随着社会信息化的高速发展建设，信息系统所承接的业务也越来越多，种类也越来越复杂多样。大量的业务数据都需要信息系统中的数据库来进行存储。因此，数据库作为信息系统的“仓库”，是能够支撑系统健康稳定运行的重要保障。然而为了存储海量数据，数据库的数量是不断增加的，种类也更加多元化，再加上IT架构复杂性的增长，运维人员疲于应付巡检和故障检修，从而使得数据库的故障处理难度急剧增长。

由于数据库关联分析的指标较为固定，因此关联分析方法主要从频繁模式的生成和筛选上有所改变，这其中还涉及数据中心数据类型与传统关联分析的数据类型有所差异的问题，例如运维系统产生的告警数据往往包含事件描述，事件发生的时间，这在传统关联分析中都是不曾出现的。

1 五种算法介绍

1.1 Apriori算法

Apriori算法是最早也是最经典的频繁项集挖掘算法，它作为一种先验算法可以在一堆数据集中寻找数据之间的某种联系，即从大量数据中找出不同项的关联规则。因此可应用的领域相对广泛。例如，商业活动中顾客的消费数据挖掘;网络中入侵攻击检测;高校学生信息数据管理及移动通信中用户特征推荐等。以便商场掌握顾客的消费情况，然后商场可通过这些有价值的数据来提升自己的服务，如促销活动、库存商品管理、消费者关系维护等。通过数据关联性分析和挖掘，作为决策制定的重要参考价值。

（1）商业活动数据挖掘

在商业活动中，企业利用Apriori算法处理日常运营中所积累的消费者海量交易数据。通过对这些数据进行深度挖掘和分析，能够获得不同产品之间的价格关系，从而企业可根据数据掌握顾客的消费习惯及趋势，进而企业可进行定向的推广服务和活动，从而节约了成本预算并可带来更大的收益。

（2）网络安全检测

在网络安全中，可利用Apriori算法通过自学习的方式对网络用户的行为进行检测，以发现网络入侵攻击行为，并快速锁定攻击者。因此提高了网络安全地检测效率，提高了网络的安全性。

（3）高校学生数据管理

在高校中，由于学生数量众多，个人信息各不相同，如籍贯、专业、家庭情况等，因此增加了学校管理部门的工作难度。因此学校管理部门在工作当中可利用Apriori算法来进行学生相关数据的管理工作，并可对学生数据信息进行快速挖掘，从而辅助高校管理部门快速获得需求数据，准确获得相关信息，提高了工作效率。

（4）移动通信

随着移动网络的快速发展，移动通信领域的服务也越来越多样化。通常运营商利用Apriori算法，对电信增值服务中的数据进行深度挖掘来回去用户特征和用户习惯，从而间接地反映了市场特点和趋势。这些数据也可以为运营商提供辅助参考，方便其在业务运营和业务方面做出合适的决策。

Apriori算法作为基于关联规则的频繁项集算法，其通过在候选项集合是扫描检测中进行递推计算。在这种算法中，频繁项集是指其中所有支持度大于最小支持度的项集。

Apriori算法采用的是层次搜索的迭代方法，因此避免了复杂的理论推导过程，只需简单的处理即可实现。但因为层次搜索迭代方法，也带来了一定的缺点，如：

需要对数据库进行多次扫描;

会导致在数据挖掘过程中产生较多的中间项集合;

仅使用唯一支持度;

算法的适应面广度不够。

1.2 FP-growth算法

FP-Growth算法是一种基于Apriori原理的关联结构分析算法，其通过将数据存储在一种叫模式树（Frequent Pattern Tree）的数据结构上来发现频繁项集。其中，FP-tree是一种由频繁项头表和前缀树构成的。FP-Growth算法则基于以上的结构加快了挖掘过程。

FP-Growth算法的作用是用于发现数据集中频繁模式，因为其利用了Apriori算法的原理，并只对数据集进行两次扫描，因此加快了数据的挖掘过程，运行速率更快。在FP-Growth算法中，数据集都集中存储在频繁模式树中，随后可通过查找元素项的条件基和构建条件频繁模式树来发现频繁项集，重复执行该动作后，最终在频繁模式树中只包含了一个元素，其包含以下步骤：

（1）为每个频繁项构建条件投影数据库和投影频繁模式树;

（2）对每个新构建的频繁模式树重复（1）中的工作，最终新构建的频繁模式树为空或只包含一条路径;

（3）若最终获得的频繁模式树为空，则其前缀可视为FP。若其只包含一条路径，则通过列举出所有可能的组合并与此树的前缀连接即可得到FP。

与Apriori算法是通过生成候选项集再进行频繁检测相比，FP-Growth算法是将数據集都存储在频繁模式树中来发现频繁项集或频繁相对。因此，FP-Growth算法的执行速度要比Apriori算法快两个数量级以上。

1.3 DLG算法

DLG（Directed Link Graph）算法即引入了关联图结构，采用的是邻接表存储方式。它的原理是当k>=3时，则对频繁k-1项集进行扫描，并将这些候选集在关联图中连接生成，当k<3时，候选集仍需要由Apriori算法生成。

与Apriori算法相比，DLG算法的优点是可以通过关联图连接各节点，从而快速找出候选集，进行反复使用，但是它的缺点依然明显，即在判定频繁集扩展节点的过程时，仍然需要对数据库进行反复的扫描，并且在项集小于3时仍是采用Apriori的连接方法，因此中间的工作量并没有减少，效率并没有提高。

1.4 FUP算法

增量关联规则挖掘（Fast Update Pattern）算法的提出同样是基于关联规则的概念，并且根据了Apriori算法以及实际情况中数据集不断增大的情况。因此，FUP算法在创建候选集的步骤中也使用了Apriori算法连接步骤。

而与Apriori算法不同之处在于FUP算法同时将数据集增量的情况考虑了进去。当数据库更新时，利用FUP算法无须再对原有数据集进行重新执行动作，在原有数据集上已发现的频繁集基础上进行更新。因此，避免了重复扫描的过程，提高了工作效率。

1）FUP算法的定义

假设DB为原数据集，db为新增数据集，[Lk]为DB的k项集，[Ck]为DB和db中的候选k项集。

2）算法步骤：

（1）对于原始数据集DB进行支持度计数，得到初始频繁1项集;

（2）在产生候选k项集合[Ck]时，对于新增数据集db，重新计算频繁k项集的[Lk]，并指出其中不满足支持度的项目;

（3）迭代進行步骤（2）， 直至算法不再产生新的候选集合。

1.5 FIUA2算法

快速增量更新算法（Fast Incremental Update Algorithm）是基于树结构的关联规则，针对增量项集提出的更新算法，即在最小支持度不变的情况下，将新增数据集db添加到原数据集DB中时，增量更新的挖掘。

FIUA2算法的原理是基于树结构算法，并保留了树结构算法在原数据集DB中的频繁项集，无须再产生新的候选项集，在挖掘过程中只需要获取新增数据集db中的新增频繁项集k，因此新的结果为原数据集中的频繁项集与新增数据集中的新增频繁项集的并集。

FIUA2算法与前文提到的树结构算法类似，因而同样会面临因为树的子节点过多导致的算法效率低的问题。

2 五种算法的比较

2.1 Apriori算法

Apriori算法使用了其本身的性质来生产候选项集，虽然在产生候选项目集时循环产生的组合过多，但很大程度上压缩了频繁集的大小，提升了检测的性能和相关异常指标的监测精度。在解决复杂环境下，问题的快速发现和提前预判方面，提供了有价值的参考决策，显著降低了故障对业务运行的影响。虽然Apriori算法不能较大程度地提高工作人员的工作效率，但在工作质量方面却提供了有力保证。因此，通过使用Apriori算法可实现故障的快速诊断和精确定位，并能够最大限度降低故障对业务运行的影响，提升运维能力的自动化、智能化技术水平，实现信息系统运维工作从“事后堵漏式补救”向“事先主动式管理”的运维模式转变。

2.2 Fp-growth算法

Fp-growth算法是利用树形结构，省去了产生候选频繁集的过程，直接得到频繁集，一定程度上减了少数据库的扫描次数，从而提高了算法的效率。但是算法扩展性相对于其他算法来说不够优秀，在解决复杂环境下的问题或者故障的快速诊断和定位方面，无法做到高精准应对。

2.3 DLG算法

与Apriori算法和Fp-growth算法相比较，DLG算法实际上并没有减少候选集合生成的数量，仍需要对数据库进行多次扫描，因此并未正在提高工作效率。此外，在数据库智能化运维方面进行应用时，在异常指标监测和故障快速定位方面的精度并没有显著的提高，在日常运行的效率方面仍然与Arpior算法有不小的差距。

2.4 FUP算法

FUP算法的支持度计数操作除了通过对数据库的记录执行字符串比较函数进行逐行扫描外，还对其进行了修剪操作，候选集的生成由Apriori算法连接来获得，FUP算法与Apriori算法的作用一样，在提高工作人员工作质量，以及降低故障对业务运行的影响方面都具有比较优异的性能。但是与Apriori算法相比较，FUP算法又增加了修剪操作等一些额外的操作，因此在运行效率方面没有Apriori算法更加高效。

2.5 FIUA2算法

FIUA2算法在运行效率方面要强于其他算法，但是实现比较困难，在某些数据集上性能会下降。因此不满足数据库智能运维技术普遍应用的具体需求，并且较大的实现难度使得工作质量难以得到有效的保障。

3 MADA算法

基于前文的五种算法的介绍和比较可以发现，在数据库智能化运维方面，Apriori算法相对于Fp-growth算法、DLG算法、FUP算法、FIUA2算法不仅能够最大限度地降低故障对业务运转的影响，提升运维人员工作质量，并且能够提升信息系统运维能力的自动化、智能化技术水平，在对运维人员工作效率的提升方面相对于其他算法也没有显著降低，具备着最好的综合性能。

因此，在Apriori算法基础上本文提出改进后的MADA数据库指标多维度异常发现算法（Multi-dimensional anomaly detection algorithm for database indicators）。与Apriori算法类似，MADA算法是通过对数据库的每个项进行扫描，并抓取其中满足最小支持度条件的项，在其中挖掘频繁a项集的集合，并将该集合标记为La;然后，在La中找出频繁b项集的集合Lb，接着利用Lb找出Lc，以此类推，直到不能再找到频繁n项集。其中，每找出一个Ln需要对数据库进行一次扫描。

3.1 MADA算法概念

1）定义[item_k（k=1，2，...，m）]为一个项，[（itemset）]为项集，则项的集合称为[itemset={item_1，item_2，...，item_m}]，其中，k指项集中包含的项的数量。

2）在[（itemset）]项集中，某一个事物T被称为该项集的一个子集，且每个事务有且只有一个标识符Tid。因此，所有的事物T组合起来形成了事物集不，从而形成了关联规则发现的事务数据库。

3）支持度（support）：

[support（A?B）=P（A?B）]

4）置信度（confidence）：

[confidence（A?B）=P（B|A）]

[P（B|A）=support（A?B）support（A）=support（A?B）support_count（A）]

5）强关联规则是指在被发现的频繁项集所产生的强关联规则。强关联规则包含以下流程：

（1）在[itemset]项集中，产生[itemset]的所有非空子集s是频繁项集;

（2）对于[itemset]的每个非空子集s，如果[support_count（l）support_count（s）≥min_conf]，则输出[s?（l-s）]，其中[min_conf]为最小置信度阈值。

3.2 MADA算法实现步骤

MADA算法实现包含以下过程：

1）首先通过算法对所有事务进行扫描，获得候选1项，并最终生成所有候选项集合C1。然后根据最小支持度条件，对候选项集中每个候选项项进行计数，并去除不满足条件的项，最终生成由频繁1构成的频繁项集L1;

2）基于（1）中的步骤，对L1中进行扫描获得候选2项，并生成集合C2。同样根据最小支持度条件，然后对C2中每个候选项进行计数，从C2中删除不满足的项，从而获得频繁2项集L2;

3）以此类推，基于以上步骤可得到，对Lk-1中进行扫描获得候选k项。并生成Ck。然后对Ck中的每个候选项进行计数，从Ck中删除不满足的项，最终获得频繁k项集Lk。

4 总结

本文通过介绍五种数据库多维度指标研究相关的算法，并对这五种算法的原理、流程及适合的应用领域进行了详细说明。结合现行数据库智能化运维过程中碰到的实际问题，在原先Apriori算法的基础上进行了细微的调整，提出了MADA算法。该算法能够更好地契合自身系统的需求，达到降低数据库运维工作人员工作量，提高工作效率的要求。

参考文献：

[1] 文芳，黄慧玲，李腾达，等.基于FP-growth关联规则的图书馆数据快速挖掘算法研究[J].重庆理工大学学报（自然科学版），2020，34（6）：189-194.

[2] 沈慧娟，曹晓丽.基于频集的Apriori关联规则算法的应用研究[J].物联网技术，2020，10（10）：57-61.

[3] 王凤肆.一种基于知识点逻辑关系模型的改进的Apriori算法[J].信息系统工程，2020（1）：47-48.

[4] 陈寅.基于FP-GROWTH算法的关联规则挖掘算法研究[J].无线互联科技，2017（19）：118-121，124.

[5] 翁进，陈亚凯，张禾裕.基于DLG精细化DEM的内插算法及其精度评价[J].国土资源导刊，2015，12（4）：79-84.

[6] 欧阳猛.基于矩阵压缩的FUP算法优化研究[D].长春：东北师范大学，2019.

[7] 朱玉全，孙志挥，季小俊.基于频繁模式树的关联规则增量式更新算法[J].计算机学报，2003，26（1）：91-96.

[8] 张雅琴.关联规则挖掘算法的设计[J].山西电子技术，2005（3）：10-12.

[9] Lasmedi Afuan，Ahmad Ashari，Yohanes Suyanto. Query Expansion in Information Retrieval using Frequent Pattern （FP） Growth Algorithm for Frequent Itemset Search and Association Rules Mining[J]. International Journal of Advanced Computer Science and Applications （IJACSA），2019（10）.

【通聯编辑：光文玲】