一种数据流频繁项挖掘方法和装置

摘要

本发明提供了一种数据流频繁项挖掘方法和装置。该方法包括：初始化样本表和历史信息表；根据数据流中数据项出现的频率更新样本表和历史信息表，其中，根据历史信息表中数据项的频率信息确定该数据项在样本表中的频率信息；根据样本表中数据项的频率信息确定数据流频繁项；其中，在样本表中存储的信息包括：在数据流中出现的频率信息满足预定条件的数据项的信息、以及在该数据流的当前分片中出现的数据项的信息，历史信息表中存储的信息包括：在所述数据流中出现过、且其频率信息不满足所述预定条件的数据项的信息，所述数据项的信息包括数据项的频率信息和数据项标识。应用本发明能够提高挖掘数据流频繁项的准确性。

说明书

技术领域

本发明涉及数据业务技术领域，尤其涉及一种数据流频繁项挖掘方法和 装置。

背景技术

网络数据流是有序到达的数据包集合。它的无限性、连续性和速度快等 特点使得网络流量监控系统要同时统计所有的数据流信息是不现实的。已有 对网络数据流性质的研究表明，数据流分布具有重尾分布特征(heavy-tailed  distribution)，即少量的IP流占据大部分的网络流量。此少量的IP流称为大 流(heavy hitters)或频繁项(frequent entry)。假定当前数据流长度为N，给定支 持度s∈(0，1)，则所有频率计数超过sN的数据项即为频繁项。事实上，许多应 用，如网络计费，负载均衡，拒绝服务攻击检测等仅需要频繁项流量信息， 丢弃小流信息。近年来，数据流频繁项挖掘已成为一个研究热点，并取得了 一些研究成果。

Manku和Motwani在文献“Approximate frequency counts over data  streams.In Proceedings of the 28th International conference on Very Large Data  Base，August 2002”中提出基于确定区间的ε近似数据流频繁项挖掘算法-损 耗计数(Lossy Counting，LC)算法。该算法在内存中维护一个数据流表，记录 数据流的频率估计值和误差边界。具体地，该算法将数据流均匀分片，某数 据包到达时，查询数据流表中是否存在相应的数据项，有则相应频率计数值 加1，否则在流表中插入新数据项，初始频率计数值为1，误差边界为上个分 片结束时记录的误差边界。当到达分片末尾时，LC算法删除频率估计值和 误差边界小于当前分片索引的流，并记录新的误差边界为当前分片索引。LC 算法对各个分片的处理方法相同。当用户发出数据频繁项查询时，LC算法 返回其频率估计值和误差边界大于等于选定门限sN的数据项。

LC算法实现简单，可快速检测数据流频繁项。但LC算法指定误差边界 为当前分片索引，即数据流表中出现过的数据项的最大频率计数值。LC算 法的误差边界过大地估计了数据流大小，使算法具有较高的误报率。

Dimitropoulos和Hurley在文献“Probabilistic lossy counting：An efficient  algorithm for finding heavy hitters.ACM SIGCOMM Computer  Communications Review，2008”中改进了LC算法中的误差边界估计方法，提 出基于概率误差区间的ε近似算法一概率损耗计数(Probabilistic Lossy  Counting，PLC)算法。该算法源于数据流分布具有重尾分布特征，其基本思 想是利用重尾分布特征估计满足P(X＞Δ)≤δ的误差边界Δ。

PLC算法在每个分片的结束，用pareto分布(最简单的重尾分布模型)模 拟重尾分布，计算新的误差边界值。当网络流量分布完全模拟重尾分布时， PLC算法估计的误差边界反映了网络流量的统计特性，小于LC算法估计的 误差边界，降低误报率，提高算法准确率。且由于网络流量中90-98％的流均 为小流，PLC算法对误差边界的估计使它更大胆的移除小流，从而极大地减 小空间消耗。但重尾分布变量具有高可变性和强烈的局部突发，且与重尾分 布的尾部指数密切相关。当尾部指数变化时，网络流量分布背离重尾分布， 不再适合用pareto分布模拟。因此，PLC算法估计的误差边界出现偏差，对 数据流大小的估计会极不准确，误报率和漏报率增加，算法准确率下降。

可见，如何提高挖掘数据流频繁项的准确率，是当前亟待解决的技术问 题。

发明内容

有鉴于此，本发明提供了一种数据流频繁项挖掘方法和装置，以便提高 挖掘数据流频繁项的准确性。

本发明采用的技术方案具体是这样实现的：

一种数据流频繁项挖掘方法，该方法包括：

初始化样本表和历史信息表；

根据数据流中数据项出现的频率更新样本表和历史信息表，其中，根据历史 信息表中数据项的频率信息确定该数据项在样本表中的频率信息；

根据样本表中数据项的频率信息确定数据流频繁项；

其中，在样本表中存储的信息包括：在数据流中出现的频率信息满足预定条 件的数据项的信息、以及在该数据流的当前分片中出现的数据项的信息，

历史信息表中存储的信息包括：在所述数据流中出现过、且其频率信息不满 足所述预定条件的数据项的信息，

所述数据项的信息包括数据项的频率信息和数据项标识。

一种数据流频繁项挖掘装置，该装置包括存储模块、更新模块和确定模块；

所述存储模块，用于存储样本表和历史信息表；其中，在样本表中存储的信 息包括：在数据流中出现的频率信息满足预定条件的数据项的信息、以及在该 数据流的当前分片中出现的数据项的信息；历史信息表中存储的信息包括：在 所述数据流中出现过、且其频率信息不满足所述预定条件的数据项的信息；所 述数据项的信息包括数据项的频率信息和数据项标识；

所述更新模块，用于根据数据流中数据项出现的频率更新样本表和历史信息 表，其中，根据历史信息表中数据项的频率信息确定该数据项在样本表中的频 率信息；

所述确定模块，用于根据样本表中数据项的频率信息确定数据流频繁 项。

由上述技术方案可见，本发明存储有样本表和历史信息表，根据数据流 中数据项出现的频率更新样本表和历史信息表，特别地，可以根据历史信息 表中数据项的频率信息确定该数据项在样本表中的频率信息，使得在估计数 据项在数据流中出现的频率时，可以综合考虑该数据项以往出现的频率信息 对当前分片中出现的频率信息的影响，从而使得样本表中记录的数据项频率 信息能够更加真实地反映数据项在数据流中实际出现的频率，因此使得根据 样本表中的频率信息确定数据流频繁项时，其准确性能够得到提高。

附图说明

图1是本发明提供的数据流频繁项挖掘方法流程图。

图2是本发明进行数据流频繁项挖掘时的数据流处理流程图。

图3是本发明根据当前分片中的数据项信息对样本表和历史信息表进行 更新的方法流程图。

图4是本发明提供的查询数据流频繁项的方法流程图。

图5是本发明实验的误报率对比图。

图6是本发明实验的漏报率对比图。

图7是本发明实验的空间消耗对比图。

图8是本发明提供的数据流频繁项挖掘装置的结构图。

具体实施方式

图1是本发明提供的数据流频繁项挖掘方法流程图。

如图1所示，该方法包括：

步骤101，初始化样本表和历史信息表。

本步骤中，可以将样本表和历史信息表初始化为空。

步骤102，根据数据流中数据项出现的频率更新样本表和历史信息表， 其中，根据历史信息表中数据项的频率信息确定该数据项在样本表中的频率 信息。

本步骤中，通过更新样本表和历史信息表，使得样本表中存储的信息包 括：在数据流中出现的频率信息满足预定条件的数据项的信息、以及在该数 据流的当前分片中出现的数据项的信息；使得历史信息表中存储的信息包括： 在所述数据流中出现过、且其频率信息不满足所述预定条件的数据项的信息。 其中，所述数据项的信息包括数据项的频率信息和数据项标识。

步骤103，根据样本表中数据项的频率信息确定数据流频繁项。

本发明图1所述方法通过引入数据项的历史信息增强记忆性，以预保护 候选的数据流频繁项，从而提高检测准确度。

图1所示方法需要维护两个数据流表：一，样本表，用于保存最近出现 的数据项信息；二，历史信息表，用于记录候选的数据流频繁项的信息，即 记录可能成为数据流频繁项的数据项。在对图1所示方法进行进一步地详细 阐述前，先对后续将要用到的术语定义如下：

样本表，用于存储最近出现的数据项的信息，一般包括频率信息满足预 定条件的数据项的信息，以及在数据流当前分片中出现的数据项的信息。样 本表中数据项的信息具体包括数据项的流标识e、频率估计值和误差边界值 Δ，其数据存储结构可以为

历史信息表，用于存储候选的数据流频繁项的信息，一般包括在所述数 据流中出现过、且其频率信息不满足所述预定条件的数据项的信息。历史信 息表中数据项的信息具体包括：数据项的流标识e、该数据项的信息被存入 历史信息表时该数据项所在的数据流分片索引i′、该数据项的信息被从样本 表中删除时该数据项在样本表中的频率估计值与误差边界值之和f，其数据 存储结构可以为(e，i′，f)。

误差参数ε，是用户许可的误差，可由用户设置。ε的取值范围是0＜ε＜1， 一般地，ε＜＜s。其中，s是设定的支持度，0＜s＜1，s用于指定频率估计值 占数据流总长度多大比例的数据项为频繁项。

分片，用于将数据流分成多个数据片，分片的大小与误差参数ε有关， 一般每个分片包含w个数据元素，其中，表示向上取整，其中 的数据元素一般为数据包。

平滑常数q，用于表示历史信息表中的频率信息对样本表中的误差边界 产生影响的权重值。平滑常数q反映了网络流量的动态性，q的值越接近1， 表示历史信息表中的频率信息对样本表中的误差边界值影响越大，q的值越 接近0，表示历史信息表中的频率信息对样本表中的误差边界值影响越小， 即之前处理的分片对当前分片的影响越小。经总结，本发明中q的取值可以 为：

下面举具体的例子，对图1所示方法进行详细介绍，具体请参见图2-图。

图2是本发明进行数据流频繁项挖掘时的数据流处理流程图。

步骤201，进行参数初始化。

本步骤中，设定误差参数ε和支持度s，所述误差参数ε和支持度s与用户 想要选择的频繁项的范围有关，一般由用户设定。当用户指定误差参数ε的具 体取值后，本发明根据样本表中的数据项信息返回的频繁项满足ε近似输出， 即：所有真实频率计数大于sN的数据项必须输出为频繁项；所有真实频率计 数小于(s-ε)N的数据项必须不能输出为频繁项；所有输出的频繁项的估计频 率计数和真实频率计数之差小于εN。

在内存中建立样本表和历史信息表，均初始化为空。样本表的每一项保 存一个三元组记录：历史信息表的条目也用三元组记录标识：(e，i′，f)。 对数据流均匀分片，每片包含个元素。分片被连续处理，分片索引由 1开始递增。当前误差边界初始化为Δ＝0。

步骤202，根据数据流当前分片中的数据项信息对样本表和历史信息表 进行更新。

关于本步骤的具体更新方法，请参见图3。

步骤203，判断当前分片是否结束，如果结束，执行步骤204，否则返 回步骤202。

步骤204，从样本表中删除频率信息不满足预定条件的数据项的信息。

本步骤中，从样本表中删除的数据项的信息。

步骤205，利用从样本表中删除的数据项信息更新历史信息表中的数据 项信息。

本步骤中，从样本表中删除的数据项信息中，如果其则可以将相 应的数据项信息插入到历史信息表中作为候选数据流频繁项，之所以选择 的数据项作为候选数据流频繁项，是因为，如果数据项在每个分片中仅 出现一次，可经验地认为该数据项不可能为数据流频繁项。这样做即节省了 空间消耗，又不会降低频繁项挖掘的准确度。

由于历史信息表的空间有限，因此当历史信息表当前的数据项个数与当前 从样本表中删除的数据项个数之和大于历史信息表最大能够存储的数据项个数 时，只能从历史信息表中已有的数据项和当前从样本表中删除的数据项中选择 部分数据项进行删除，而将其余的数据项存储在历史信息表中。

为了尽可能地在历史信息表中存储成为频繁项的概率较大的数据项，可以在 历史信息表当前的数据项信息和当前从样本表中删除的数据项信息中选择q^i-i′f 最小的n个数据项信息进行删除，以便把样本表中最近的候选数据流频繁项保 存到历史信息表中，并删除历史信息表中的老化候选数据流频繁项。这是一个 动态的更新过程，使历史信息表中记录的永远是最近的，最有可能成为候选数 据流频繁项。

其中，n是本次更新前历史信息表中的数据项个数与当前从样本表中删 除的数据项个数之和减去历史信息表最大能够存储的数据项个数所得的差。

在每一分片结束后，还可以计算下一分片的误差边界值Δ′，该误差边界 值Δ′用于在步骤202中更新样本表和历史信息表时，估计在样本表和历史信 息表中均没有出现的数据项的误差边界Δ，具体估计方法参见图3的说明。

具体地，在每一分片结束后，需要更新历史信息表，假设分片结束更新 历史信息表时删除了q^i-i′f最小的n个数据项信息，则该分片的误差边界值Δ′ 为这n个数据项信息中最大的q^i-i′f，即Δ′＝max((q^i-i′f)1，......，(q^i-i′f)_n)。

关于历史信息表所占用的空间大小，可以有多种确定方法，下面仅举两 个例子进行示例性说明：其一，利用系统可使用的内存资源指定合适的历史 信息表大小，此方法简单且在内存消耗上提供了很强的保证，但是内存资源 不能得到合理利用。其二，在目标环境下使用训练数据集估计历史信息表大 小，即在每个分片结束时，利用从样本表中筛选出的候选数据流频繁项的数 目的最大值确定历史信息表大小。

步骤206，判断数据流是否处理完毕，如果是，结束本流程，如果否， 返回步骤202。

图3是本发明根据当前分片中的数据项信息对样本表和历史信息表进行 更新的方法流程图。

如图3所示，该方法包括：

步骤301，从当前分片中取出一数据项。

步骤302，查找样本表中是否存在该数据项的信息，如果是，执行步骤 303，否则执行步骤304。

步骤303，将该数据项在样本表中的频率估计值加1，进入步骤307。

步骤304，查找历史信息表中是否存在该数据项的信息，如果是，执行 步骤305，否则执行步骤306。

步骤305，将该数据项的信息从历史信息表中删除，并插入样本表中， 进入步骤307。

本步骤中，如果该数据项在历史信息表中的信息为(e，i′，f)，则将该数据 项插入样本表中后，其在样本表中的信息为(e，1，q^i-i′f)，即将该数据项在样本 表中的频率估计值记为1，误差边界值Δ记为q^i-i′f。

步骤306，将该数据项的信息记录在样本表中，其中，该数据项的频率 估计值记为1，误差边界值Δ记为上一分片结束时计算的误差边界值Δ′。

步骤307，判断当前分片是否已结束，如果是，结束本流程，否则返回 步骤301。

在图2所示方法中，任何时刻如果用户想要查询数据流频繁项，则遍历 样本表，根据用户输入的支持度s查询出相应的频繁项，具体请参见图4。

图4是本发明提供的查询数据流频繁项的方法流程图。

如图4所示，该方法包括：

步骤401，接收用户输入的支持度s。

步骤402，从样本表中取出一数据项。

步骤403，判断该数据项在样本表中的频率估计值与误差边界值Δ之和 是否大于sN，如果是，执行步骤404，如果否，执行步骤405。

其中，N是截止到当前时刻已处理的数据流的长度。

步骤404，将该数据项输出为频繁项。

步骤405，判断该样本表是否已遍历结束，如果是，结束本流程，如果 否，返回步骤402。

图4所示方法输出的频繁项包括两类：第一类是真实频率大于sN的数据 项，第二类是真实频率在(s-ε)N之间的数据项。其中的第二类是误报项，即 将本不是频繁项的数据项误报为频繁项。

为了验证本发明提供的数据项挖掘方法的性能优势，本申请人特做如下 实验：

从MAWI网络中采集的15个数据集以及中国科学院校园网络骨干网络 出口采集的200多个数据集中分别选择1个有代表性的数据集Trance I和 Trance II进行实验，数据集的统计信息参见表一。

表一

本申请人采用表一真实的网络数据进行实验，在实验中采用的误差参数 ε＝0.001％，即每个分片处理的数据包个数为100000，支持度s选取三个值， 分别为s＝1％，s＝0.1％和s＝0.05％。

本申请人根据实验结果，从误报率、漏报率、空间消耗和计算复杂度四 个方面对本发明的频繁项挖掘方法与LC算法和PLC算法进行验证，具体请 参见图5-图7以及表二。

其中，误报率指的是周期性的进行数据流频繁项查询，频繁项挖掘系统 误报的频繁项在返回的频繁项总数中所占的比例。漏报率指的是周期性的进 行数据流频繁项查询，频繁项挖掘系统漏报的频繁项在返回的频繁项总数中 所占的比例。空间消耗是通过监测频繁项挖掘系统使用的数据结构保存的数 据流条目数进行比较。计算复杂度是通过在相同环境下单数据项的更新时间 进行比较。

图5是本发明实验的误报率对比图。

图6是本发明实验的漏报率对比图。

图7是本发明实验的空间消耗对比图。

图5至图7中，MLC代表本发明的方法。

表二是本发明的计算复杂度对比表。

表二

由图5-图7以及表二可见，本发明在误报率上改善了LC算法，在算法 效率上明显快于PLC算法。在空间消耗上，三种算法的最大空间消耗基本一 致，本发明和PLC算法的空间消耗随着时间增长空间消耗逐步下降。在漏报 率上，本发明和LC算法基本无漏报，PLC算法在最坏情况下最大漏报率为 0.044。因此，综合误报率、漏报率、空间消耗和计算复杂度这四项指标，本 发明进行数据挖掘的整体性能较高。

下面结合理论分析，对本发明的优点进一步阐述：

误报率的大小与误差边界Δ的取值密切相关。本发明通过适当的保存历 史信息，即在历史信息表中存储候选频繁项的信息，利用历史信息对不同的 分片中出现的新数据项指定最佳的误差界限，从而降低了误报率。

本发明虽然需要在样本表外再保存一个历史信息表，但是由于限定了历 史信息表的大小，因此其空间消耗与LC算法和PLC算法相比并没有明显增 加。

根据本发明提供的上述方法，本发明还提供了相应的数据流频繁项挖掘 装置，具体请参见图8。

图8是本发明提供的数据流频繁项挖掘装置的结构图。

如图8所示，该装置包括存储模块801、更新模块802和确定模块803。

存储模块801，用于存储样本表和历史信息表；其中，在样本表中存储的信 息包括：在数据流中出现的频率信息满足预定条件的数据项的信息、以及在该 数据流的当前分片中出现的数据项的信息；历史信息表中存储的信息包括：在 所述数据流中出现过、且其频率信息不满足所述预定条件的数据项的信息；所 述数据项的信息包括数据项的频率信息和数据项标识。

更新模块802，用于根据数据流中数据项出现的频率更新样本表和历史信息 表，其中，根据历史信息表中数据项的频率信息确定该数据项在样本表中的频 率信息。

确定模块803，用于根据样本表中数据项的频率信息确定数据流频繁项。

更新模块802，用于在每一分片结束时，从样本表中删除频率信息不满足所 述预定条件的数据项的信息，利用从样本表中删除的数据项信息更新历史信息 表中的数据项信息。

样本表中存储的数据项信息包括：该数据项的流标识e、频率估计值和误 差边界值Δ。

历史信息表中存储的数据项信息包括：该数据项的流标识e、该数据项的信 息被存入历史信息表时该数据项所在的数据流分片索引i′、该数据项的信息被从 样本表中删除时该数据项在样本表中的频率估计值与误差边界值之和f。

更新模块802，用于在当前分片中的数据项未出现在样本表中，但是出现在 历史信息表中时，将该数据项在样本表中的频率估计值记为1，误差边界值Δ记 为q^i-i′f，其中，i是当前数据流分片的索引号，q是根据数据流分片之间的联系 紧密程度预先设定的平滑参数，0≤q＜1。

更新模块802，用于在历史信息表当前的数据项个数与当前从样本表中删除 的数据项个数之和大于历史信息表最大能够存储的数据项个数时，在历史信息 表当前的数据项信息和当前从样本表中删除的数据项信息中选择q^i-i′f最小的n 个数据项信息，删除所述n个数据项信息。

其中，n是本次更新前历史信息表中的数据项个数与当前从样本表中删除的 数据项个数之和减去历史信息表最大能够存储的数据项个数所得的差。

更新模块802，用于在每一分片结束时，从所述n个数据项信息中选择最大 的q^i-i′f作为下一分片的误差边界值，在当前分片中的数据项未出现在样本表中， 且未出现在历史信息表中时，将样本表中该数据项的频率估计值记为1，误差 边界值Δ记为上一分片结束时计算的误差边界值。

更新模块802，用于在当前分片的数据项出现在样本表中时，将样本表中该 数据项的频率估计值加1。

确定模块803，用于将样本表中的频率信息满足的数据项确定 为数据流频繁项，其中，s是指定的支持度，0＜s＜1，N是所述数据流的长 度。

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本 发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在 本发明保护的范围之内。