基于最大频繁项的数据流异常检测

摘要：为了解决网络异常数据检测由于数据流的高速和无限范围的特点而无法构建模型的问题，文章设计了一种基于最大频繁项（MFI） 的数据流异常检测算法，构建了数据挖掘的异常数据检测模型，基于多维数据的最大频繁模式挖掘算法（Max FP-Tree算法） ，提出了Max FP-Tree NDS算法，根据其定义和性质，对上述提出的算法进行了改进，最后验证了Max F P-Tree算法和Max FP-Tree NDS算法对异常数据的检出率。该研究分析了多维Max FP-Tree NDS算法的异常数据处理时间和节点维护情况。结果表明，该研究改进的Max FP-Tree算法能够有效提高异常入侵数据的检测率，未知异常预警率从17.6%提高到21.9%，异常误报率从9.42%降低到 7.6%。Max FP-Tree NDS算法对异常数据的处理时间随着数据集的增加而变慢，维护的节点数随着数据集的增加先增加后减少。

关键词：最大频繁项; 数据流; 异常检测; 检测率; 数据挖掘

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

文章编号：1009-3044（2022）25-0118-03

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

随着大数据时代的到来，大数据挖掘技术应运而生，数据流的高效处理成为数据库领域的研究热点。数据流是一种大规模、连续到达、高速、不可预测的数据序列，广泛应用于通信、金融、互联网信息安全等现实生活和工业数据领域[1]。与传统数据不同，数据流的数据实时到达，每条数据只能访问一次，数据到达顺序独立，不受系统控制，这些特点给数据处理带来了新的挑战。作为数据挖掘研究领域的一个重要分支，异常检测技术受到了学术界的广泛关注[2]。

异常是指数据集中存在独特的数据，而数据流的异常检测就是找出这些明显远离其他数据点的数据。欺诈检查、医疗处理、图像处理等多方面使用异常检测的算法。传统的异常检测算法主要分为基于统计学、基于聚类、基于分类以及基于近邻性[3]。现在随着对数据流分析处理研究的深入，数据流异常检测算法也在不断更新和完善。一般来说，数据流的异常检测可以分为两种类型，即检测数据对象的行为变化和发展趋势的变化[4]。数据流异常检测已应用于各个领域，如网络入侵检测、异常天气检测、金融分析检测等。为了研究异常检测技术，一些研究利用领域知识来提高异常检测模型的准确性，一些学者将模糊理论与关联挖掘技术相结合，提出了网络用户挖掘模型。这些技术极大地改进了异常数据的检查技术[5-6]。然而，由于其自身具有不确定性和数据量大等特点，数据流面临着许多挑战。例如，数据流不能存储在有限的内存中，随机访问数据流中的数据对象的机会很小[7]。最大频繁挖掘是对数据进行分类和压缩，可以更好地节省数据的存储空间[8]。因此，研究基于MFI的数据异常检测具有重要意义。

综上所述，本研究采用MFI算法对数据流进行异常检测。本文首先构建了基于数据挖掘的异常数据入侵检测模型，设计了一种基于MFI的多维频率模式挖掘算法，并对MFI算法的更新方法进行了说明，最后对异常数据的检测率、异常数据的处理时间、异常数据的节点维护结果进行分析。本研究旨在为利用挖掘数据技术构建网络异常入侵数据检测模型提供良好的理论依据。

1 基于数据挖掘的异常入侵检测模型的建立

数据流是一个动态的数据序列，具有持久性和快速形成的特点，常用来表征动态网络的访问量。本研究探索的数据集是：收集一段时间内的网络访问量，将其定义为一个数据流，分析其特征，找出异常数据和正常数据的特征，从而构建相应的网络访问数据模型库。算法基于数据集进行分析，实现对未来网络访问数据的异常检测和分析。

传统的异常检测方法可以快速识别未知攻击访问，但误报率较高。本研究设计的异常检测模型将误用检测和异常检测相结合，强化优势，改善劣势。图1显示了基本架构。

图1中的模型由两个主要模块组成，即前端检测模块和后端学习模块。检测模块主要在异常检测模型的基础上结合误用检测;学习模块用于生成知识模式的特征，包括正常规则和异常规则的学习模块。异常检测模块将网络范围的访问数据与正常模式和已知异常模式库进行匹配。前者通过检查是否完美匹配来判断是否为正常数据，后者通过与已知异常数据库的匹配来判断是否为异常数据，否则将转移到普通正常训练集和异常训练集。后端学习模块包括正常规则学习模块和异常规则学习模块，旨在增量学习新增的正常训练集和异常训练集，更新正常和异常模式库。

2 基于MFI的数据流最大频繁模式挖掘算法设计

2.1 相关定义

最大频繁模式是本研究中要解决的一个场景。 该场景是指由许多属性组成的网络访问。 本研究将公共数据集 KDD99 中的一个数据段按照连接类型、服务类型、连接标识、连接时长和字节数列出，如表1所示，选择属性作为问题的焦点来挖掘最大频繁模式。

定义1：频繁模式。假设数据集为M，维度属性集为B，则可以得到[B={B1，B2，…，Bm}]。假设离散化属性B1的值为A，可以得到[A={ai1，ai2，…，anpn}]，M中基于B的n维项集用L表示，可以得到[L={ai1，ai2，…，amn}]，其中[amn∈Ai（i=1，2，…，m;pn=1，2，…，m）]。因此，项集在数据集M中所占的百分比可以称为它的支持度;通常如果项集的支持度不小于用户定义的最小支持度，则可以称为频繁模式。

定义2：超集（频繁模式的包含关系） 。假设有给定的数据集 M 和给定的维度属性集[B={B1，B2，…，Bm}]，对应的取值范围可以表示为[A={ai1，ai2，…，anpn}]。对于任意两个基于 B （[L={ai1，ai2，…，amn}]和[Q={Qi1，Qi2，…，Qmn}]） 的 n 维项集，如果[ai1=Qi1（i=1，2，…，m）]中所有维属性都为真，则可以称为 [L⊆Q] 。如果[L⊆Q] ， 并且其中一个维度属性j符合[Qmn≠*]而不是[anpn≠*] ，则 L 真正包含在 Q 中，可以表示为[L⊂Q] 。

定义3：最大频繁模式。频繁模式L的所有超集都是非频繁项集， 那么称L 为最大频繁模式， 记为MFI （Maximal Frequent Itemset）。

定义4：遍历第一个根。 在树[PC={R，P1，…，Pi，…Pv}]中，C 表示树的根节点，[PC]表示以节点[i（1⩽i⩽c）]为根的子树。遍历时，应遵循“根优先遍历”的原则。得到节点顺序后，对节点进行编号并递归生成。

本研究利用最大频繁模式（MFI）对数据流进行高效挖掘，设计了MFI的模式树。 首先根据表1设计内存中的Max FP-Tree。Max FP-Tree树具有三个特点：父节点必须包含子节点;子节点的支持数必须小于父节点的支持数;存储过程中只存储最大频繁项集。

2.2 最大频繁模式数的更新方法

随着数据流的变化，每条新生成的训练记录都需要相应地修改。现有的Max P-tree及其对应的支持度被计入 Max FP-Tree 的更新。

算法1的流程如下：使用Max FP-Tree进行更新，更新后的算法记为Update-MaxFP-tree。 输入当前处理的多维数据流记录i，当前节点“node”被更新，最后输出更新后的Max FP-Tree。

为了减少使用数据流解决网络入侵异常检测时的窗口模型问题，基于衰减窗口机制设计了一种网络访问数据流最大频繁模式的挖掘算法，称为Max FP-Tree NDS算法。算法过程如下：输入网络数据流M、衰减率、最小支持minSupport、MaxFP-Tree，然后输出入侵异常数据ID-Pattern的检测模式。

上述两种算法的运行过程必须在数据流每次到达一次访问时记录下来。 总共有四个步骤：记录评估、窗口估计、最大 FP-Tree 维护和模式输出。

3 结果与讨论

本研究使用的实验数据来源于 KDD99 数据集。 该数据集有 41个基本属性。根据本研究的实验环境条件，仅选取21个关键属性进行实验。训练集中有 520，000 条记录，测试集中有 10，000 条记录。在测试集中，正常数据占72.9%，异常入侵数据占16.76%，未知类型异常入侵数据占10.34%。

3.1 异常数据检出率结果分析

本研究算法的目标是优化数据流中异常检测的准确率。比较模型基于异常检测算法和本研究提出的Max FP-Tree NDS算法，将误用检测和异常检测相结合。设计的评价指标包括未知异常预警率，即现有数据集中无法验证的异常数据占所有数据集的比例;异常误报率，即系统误判为异常数据的记录在总数据集中的比例.

本研究分析了不同数据集下的异常数据检测结果，两组算法模型的未知异常预警率和异常误报率随着数据容量的增加而变化，如图2所示。本研究的Max FP-Tree NDS算法融合了误用检测的思想，因此检测更加准确，减少了非完全匹配数据集的比例。结果表明，无论数据集大小，优化后的算法在未知异常预警率和异常误报率方面均具有优势。Max FP-Tree算法的未知异常预警率和异常误报率均低于基本异常检测算法，并且随着数据集的增加，优越性越来越高，说明改进算法后异常检测准确率提升。

3.2 异常数据处理时间结果分析

图3给出了数据集增加时检测算法总处理时间的变化。由此可以看出，本实验的衰减率为0.994。 在不同程度的支持下，随着数据流容量的增加，Max FP-Tree NDS算法的处理时间增加，但是这两者的增加并没有呈现出线性变化。 当数据量超过90，000条记录时，处理时间增长缓慢，说明处理用户在正常行为模式下逐渐完善。

3.3 Max FP-Tree NDS算法节点维护结果分析

如图4所示是Max FP-Tree算法维护的节点数随数据集节点增加的变化情况。本研究实验中的衰减率为0.994。从图4中可以看出，在学习阶段初期，系统模型库存在一定缺陷，Max FP-Tree NDS算法会进入并移动大量节点。经过一段时间后，被维护的节点会达到最高峰。后来随着数据集节点的增加，模式库和用户行为逐渐趋于稳定，Max FP-Tree NDS维护的节点数逐渐减少，稳定在80，000左右的合理范围内。

4 总结

针对网络数据流中无法构建异常数据检测模型的问题，本研究提出了一种基于最大频繁项（MFI） 的数据流异常检测算法，即Max FP-Tree NDS算法，并对其进行了改进，使Max FP-Tree NDS算法实现多维条件下异常数据的检测。根据实验结果发现，在异常入侵数据的检测中，Max FP-Tree NDS算法能够很好地提高异常数据的预警率和误报率。 此外，Max FP-Tree NDS算法在总处理时间上表现出明显的优势。本研究为多维频繁模式下的异常入侵数据检测提供了良好的理论基础，但也存在一定的局限性。本研究仅选择了两种支持模式，后续研究可以在更丰富的支持基础上进行。

参考文献：

[1] Jie X C，Wang H K，Fei M R，et al.Anomaly behavior detection and reliability assessment of control systems based on association rules[J].International Journal of Critical Infrastructure Protection，2018，22：90-99.

[2] Li B，Zhao S J，Zhang R Q，et al.Anomaly detection for cellular networks using big data analytics[J].IET Communications，2019，13（20）：3351-3359.

[3] Jiawei Han，Micheline Kamber，Jian Pei..数据挖掘：概念与技术[M]. 范明，孟小峰，译北京：机械工业出版社，2012：186-188.

[4] Kong X J，Song X M，Xia F，et al.LoTAD：long-term traffic anomaly detection based on crowdsourced bus trajectory data[J].World Wide Web，2018，21（3）：825-847.

[5] Islam R U，Hossain M S，Andersson K.A novel anomaly detection algorithm for sensor data under uncertainty[J].Soft Computing，2018，22（5）：1623-1639.

[6] 唐锐.基于频繁模式的离群点挖掘在入侵检测中的应用[D].重庆：重庆大学，2013.

[7] Liu D T，Pang J Y，Song G，et al.Fragment anomaly detection with prediction and statistical analysis for satellite telemetry[J].IEEE Access， 2017，5：19269-19281.

[8] Su S，Sun Y B，Gao X S，et al.A correlation-change based feature selection method for IoT equipment anomaly detection[J].Applied Sciences，2019，9（3）：437.

【通联编辑：代影】