基于rnn双模型的数据流频率估计方法及应用
技术领域
1.本发明属于流数据处理领域，涉及一种基于rnn双模型的数据流频率估计方法及应用。
背景技术：2.数据流的频率估计是流数据处理领域最主要的方法之一，应用非常广泛，如机器学习中的特征选择、网络流量监测、检测dos攻击和搜索引擎热点排行等。conservative-update sketch
1.是应用比较广泛的方法之一，该方法的基本思想是通过牺牲部分估计精度的情况下使用较小的空间存储大数据量的频率，属于sketch一类方法中比较经典的方法。但是，基于sketch的现有方法在处理大数据量时都存在由于哈希冲突导致估计精度下降的现象。
技术实现要素：3.本发明提供一种基于rnn双模型的数据流频率估计方法及应用，该估计方法结合当下流行的循环神经网络模型，将频率估计和神经网络结合在一起，基于rnn(循环神经网络)和conservative-updatesketch
1.实现了更好的误差控制和更加精确的频率估计。该方法对数据流中数据项的频率进行估计，通过两个rnn神经网络模型对数据流进行分类，将高频数据和低频数据分开存储，降低高频数据和低频数据之间的哈希冲突，从而提高数据流频率估计的精度，由于高频数据单独存储，可以减少高频数据哈希计算的次数，在一定程度上提高了数据流的处理效率。该估计方法应用在网络流量监测中，能够监测网络的突发情况，提高监测的精度和效率。
4.为实现上述目的，本发明的技术方案是：
5.第一方面，本发明提供一种基于rnn双模型的数据流频率估计方法，该估计方法的流程是：
6.1)数据获取单元：获得历史数据流，确定历史数据流频率估计的目标，对历史数据流中的数据进行打标，打标的标签分别为低频数据、全局高频数据和局部高频数据，建立数据集；
7.2)构建rnn双模型
8.所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，两个rnn模型都采用n-to-one结构，rnn-global模型用于判断数据是否为全局高频数据，rnn-local模型用于继续对通过rnn-global模型判断不是全局高频数据的数据进行预测，判断是否为局部高频数据；如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为局部高频数据；
9.利用步骤1)的数据集训练rnn双模型，获得训练好的rnn双模型，待估计的数据流经过训练好的rnn双模型被分类为低频、全局高频和局部高频三个类型的数据；
10.3)数据存储更新
11.rnn双模型判定一个数据为低频数据，该数据以保守更新的方式存入低频数据区；
12.rnn双模型判定一个数据为局部高频数据，该数据会被放入高频数据区的局部桶内，如果该数据和局部桶内的数据相同则桶内的频率累加1；如果局部桶为空或该数据和局部桶内数据相异，将该数据存入局部桶内，频率值为1，计时器t重新计时；
13.rnn双模型判定为全局高频数据，则遍历高频数据区内的所有全局桶，寻找该数据对应的桶并且记录频率最小的桶b，如果找到了对应的桶则频率+1；如果没有找到对应的桶，则该数据先保守更新到低频数据区，估计出该数据的频率g，当有空全局桶存在的情况下，就申请一个全局桶把该数据和估计出的频率值g存储在桶上，当没有空的全局桶时，则需要将桶b上的频率与g做比较，判断是否满足末轮淘汰的触发条件，如果不满足则之前的保守更新就属于次轮淘汰；
14.4)当需要估计某个数据的频率时，先遍历高频数据区的所有桶，如果与之相匹配桶是全局桶就返回桶中频率；如果匹配的局部桶，则进入低频数据区通过哈希计算从映射的桶中返回桶中最小值和局部桶中值的和；如果不在高频数据区则从低频数据区中通过计算获取桶中的最小值，进而实现数据流频率估计。
15.所述末轮淘汰的数据类型有两种，一种是局部高频数据，另外一种是全局高频数据；
16.所述全局高频数据被末轮淘汰需要同时满足以下条件：
17.①
全局桶没有空桶；
18.②
需要存入高频数据区的这个全局高频数据不在全局桶中；
19.③
在
②
中的这个全局高频数据的频率大于全局桶中频率的最小值。
20.在满足条件的情况下触发末轮淘汰——全局桶中频率最小的那个桶对应的全局高频数据会从高频数据区淘汰后存入低频数据区，淘汰后空出来的全局桶分配给需要的全局高频数据；
21.所述末轮淘汰下来的全局高频数据，首先在低频数据区经过哈希映射到conservative-updatesketch的某些桶上，然后依次判断每个桶中存储的频率值和末轮淘汰下来的被淘汰数据的频率大小关系，二者的最大值作为桶上的最终结果；如果末轮淘汰下来的全局高频数据经过哈希计算映射到多个桶上，其中有两个以上桶内的数据的频率值都小于末轮淘汰下来的全局高频数据的频率值，则将这两个以上桶内的数据的频率值都换成末轮淘汰下来的全局高频数据的频率值；
22.所述局部高频数据被末轮淘汰的触发条件为：当局部桶中的计时器归零时触发局部高频数据的末轮淘汰；
23.当局部桶的计时器归零的时候淘汰已有局部高频数据并存入低频数据区；
24.末轮淘汰下来的局部高频数据，假设被淘汰的局部桶数据为data，频率为f，首先被淘汰的数据data在低频数据区经过哈希映射到conservative-updatesketch的某些桶上，然后估计出data在低频数据区的估计值d，最后将d+f的值和经过哈希映射的每个桶上的值进行比较，如果桶上的值小于d+f，就用d+f替换桶上的值，否则不做更新。
25.所述次轮淘汰的触发条件是数据虽然被判定为全局高频数据进入高频数据区，但是由于全局桶的数量有限，而且该数据的频率比高频数据区中所有全局高频数据的频率
小，对比全局高频数据末轮淘汰条件，次轮淘汰需要满足
①②
不满足条件
③
；次轮淘汰下来的数据会以保守更新的方式存入低频数据区。
26.第二方面，本发明提供一种上述的基于rnn双模型的数据流频率估计方法的应用，该估计方法用于网络流量监测，监测网络的突发情况。
27.第三方面，本发明提供一种用于网络流量监测的数据流频率估计方法，其特征在于，该方法的步骤是：
28.1)数据集预处理：数据集中数据元组的格式设置为《目标主机地址、目标端口号、数据包大小(单位：字节)、标签(0表示全局高频，1表示局部高频，2表示低频数据)》，首先，统计出历史网络流量监测数据中不同大小的数据包出现的频率，然后，根据频率进行从大到小排序，取排序后的前百分之十数据包作为全局高频数据；最后，依据这些高频数据的数据包大小给匹配的元组打上值为0的标签，至此全局高频数据的标签添加完毕；
29.接下来对数据集中局部高频数据进行添加标签，首先，在数据流上取一个大小为10的滑动窗口，沿着数据流依次向后滑动，当某大小的数据包在窗口中出现的频率大于等于7的时候，如果匹配的元组没有被打上0的标签就给该元组打上值为1的标签，至此局部高频数据的标签添加完毕；
30.最后对那些没有标签的元组打上值为2的标签，表示该元组属于低频数据，最终标签值0、1、2表示全局高频、局部高频和低频；至此完成数据集打标的工作；
31.2)建rnn双模型
32.所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，两个rnn模型都采用n-to-one结构，rnn-global模型用于判断数据是否为全局高频数据，rnn-local模型用于继续对通过rnn-global模型判断不是全局高频数据的数据进行判断，是否为局部高频数据；如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为局部高频数据；
33.数据集打标完成后，对rnn双模型进行训练，取元组的前两项作为训练输入的基本单元，rnn双模型的输出形式表示对标签值0、1和2的预测打分，值越大表示对应的预测结果可能性越大，经过多轮的训练和评估之后获得训练好的rnn双模型并保存；
34.3)数据存储区域划分：将数据存储区域划分为高频数据区和低频数据区，高频数据区桶的类型有两种，一种是存储全局高频数据的全局桶，另外一种是存储局部高频数据的局部桶，全局桶以数组的方式排列，全局桶中有多个桶，全局桶中的桶的遍历方式是顺序遍历，全局桶中存储一个数据和数据对应的频率；局部桶的数量为1，桶内存储了数据、计时值t和频率；低频数据区存储的是被rnn双模型判定为低频的数据和从高频数据区淘汰下来的“高频数据”，低频数据区的存储结构基于conservative-updatesketch——多个哈希函数对应多个桶序列，哈希函数的值域就是桶序列的长度；
35.4)接下来使用训练好的rnn双模型对具体的数据流进行处理，取出数据包的主机地址和端口号作为rnn双模型的输入，数据包的大小作为框架中数据data；通过rnn双模型判定为低频的数据包，对数据data进行哈希计算，以保守更新的方式存入低频数据区；
36.通过rnn双模型判定为局部高频的数据data，首先检查data是否在局部桶中，如果存在就对局部桶的频率+1，如果不存在且桶为空的情况下就在局部桶内存储data值和频率
值1并且开始新的计时，当一个不同于局部桶内已有的局部高频数据的新局部高频数据进来时先前的局部高频数据将从高频数据区淘汰，此时计时器被动置为零，执行局部高频数据的末轮淘汰，新的局部高频数据放入局部桶内，频率值1，并且开始新的计时；
37.通过rnn双模型判定为全局高频数据data，则遍历高频数据区内的所有全局桶，寻找该数据对应的桶并且记录频率最小的桶b，如果找到了对应的桶则频率+1；如果没有找到对应的桶，则该数据先保守更新到低频数据区，估计出该数据的频率g，当有空全局桶存在的情况下，就申请一个全局桶把该数据和频率值f存储在桶上，当没有空的全局桶时，则需要将桶b上的频率和g做比较，判断是否满足末轮淘汰的触发条件，如果不满足则之前的保守更新就属于次轮淘汰；
38.5)经过一段时间的数据处理，所有数据包的统计信息被存放在高频数据区和低频数据区，查询目标大小数据包的频率时先到高频数据区遍历所有的桶，如果找到目标大小数据包对应的桶是全局桶则返回桶中的频率；如果是局部桶，则进入低频数据区通过哈希计算从映射的桶中返回桶中最小值和局部桶中值的和；否则进入低频数据区通过哈希计算从映射的桶中返回最小值，这个最小值就是目标大小数据包的估计频率。
39.第四方面，本发明提供一种计算机可读存储介质，所述存储介质中存储有计算机程序，所述计算机程序适用于被计算机加载时执行上述的基于rnn双模型的数据流频率估计方法或上述的用于网络流量监测的数据流频率估计方法。
40.第五方面，本发明提供一种装置，包括：
41.数据获取单元，用于获取标注了低频、全局高频、局部高频的数据流；
42.分类模型，用于对数据流进行低频、全局高频、局部高频的分类；
43.存储单元，用于将高频数据区和低频数据区分开存储，高频数据区中存储全局高频数据和局部高频数据，低频数据区用于存储低频数据和淘汰下来的数据；
44.更新单元，采用首轮、次轮和末轮淘汰机制对高频数据区和低频数据区进行更新；
45.查询单元，用于估计目标数据的频率。
46.与现有技术相比，本发明的有益效果是：
47.本发明将rnn双模型和conservative-updatesketch
1.结合，通过rnn双模型对数据进行分类，然后将高频数据和低频数据分开存储，降低高低频数据冲突，从而提高频率估计的精度。
48.使用rnn双模型对于数据流进行预测能够准确的对数据进行分类，将高低频数据分开存储可以在很大程度上避免高低频数据的哈希碰撞。而conservative-updatesketch
1.方法中的保守更新策略又进一步降低了低频数据哈希冲突造成的影响。数据流中频率最高的数据几乎存储在高频数据区，在处理高频数据的时候减少了哈希计算的次数，加快了数据流的处理效率。高频数据的末轮淘汰机制是本发明的核心之一，对误差进一步控制使得频率估计更加准确。
49.本发明方法的目标就是尽可能的降低由于数据之间的哈希碰撞导致频率高估带来的影响，划分高低频数据意在减少高频数据和低频数据之间的碰撞，保守更新和淘汰机制则是减弱低频数据之间发生碰撞后造成的影响，通过以上各种方式对碰撞的抑制和控制使频率估计的精度更高，将本发明方法应用于网络流量监测中，所估计的频率精度高、效率更快，提高了网络流量监测的准确性。
附图说明
50.图1为本发明基于rnn双模型的数据流频率估计方法的基本框架结构示意图。
51.图2为rnn模型的结构示意图。
52.图3为高频数据区的数据结构示意图。
53.图4为低频数据区的数据结构示意图。
54.图5为全局高频数据末轮淘汰过程示意图。
55.图6为末轮淘汰数据data3放入低频数据区的处理过程示意图。
56.图7为局部高频数据末轮淘汰过程示意图。
57.图8为末轮淘汰数据data4放入低频数据区的示意图。
58.图9为保守更新过程示意图。
具体实施方式
59.下面结合实施例及附图进一步解释本发明，但并不以此作为对本技术保护范围的限定。
60.本发明技术方案的要点主要有三点：通过rnn双模型将数据流分类为低频数据、全局高频数据和局部高频数据；高频数据和低频数据分开存储，将存储数据的区域划分为存储高频数据的高频数据区和存储低频数据的低频数据区；数据的淘汰机制。以下对这三个要点内容进行详细阐述。
61.1.rnn双模型：
62.rnn(循环神经网络)模型在处理数据流中的应用非常广泛，因为rnn对于带有时序属性数据流的预测具有很好效果，本技术采用rnn模型来对数据流进行预测。在方案中使用了两个rnn模型，分别对数据流中的全局高频数据和局部高频数据进行预测，将数据流分类为低频数据、全局高频数据和局部高频数据。
63.所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为局部高频数据。
64.rnn-global模型用于预测数据流中全局高频数据——在某一段数据流中该数据出现的频率很高，而且对于数据流整体而言该数据出现的频率依然很高。
65.rnn-local模型则是用于预测数据流中局部高频数据——在某一段数据流中该数据出现的频率很高，但是对于数据流整体而言该数据出现的频率却很低。
66.rnn-global模型和rnn-local模型的作用都是对数据流进行分类，这两个rnn模型都采用n-to-one结构，具体的结构如图2所示。
67.2.高频数据区和低频数据区：
68.由rnn双模型判定为高频的数据会被存入高频数据区，高频数据区会为每个高频数据单独分配一个桶，高频数据区桶的类型有两种，一种是存储全局高频数据的全局桶，另外一种是存储局部高频数据的局部桶。虽然两种桶都存储了数据的频率，但是全局桶内存储的是全局高频数据的真实频率，而局部桶内存储的频率仅仅是计时器清零所需时间段内的频率。全局桶以数组的方式排列，全局桶的数量不应设太多，因为桶的遍历方式是顺序遍
历，如果桶的数量太多会对性能有影响，所以数量一般在20-30个左右，全局桶中的每个桶存储一个数据和数据对应的频率。局部桶的个数为1，桶内存储了数据、计时值t和频率。高频数据区的形式如下图3所示。
69.低频数据区存储的是被rnn双模型判定为低频数据和从高频数据区淘汰下来的“高频数据”，低频数据区的存储结构基于conservative-updatesketch
1.——多个哈希函数对应多个桶序列，哈希函数的值域就是桶序列的长度。低频数据区的结构如下图4所示，h为哈希函数名称。
70.3.淘汰机制：
71.rnn双模型把数据判定为低频数据的过程称作首轮淘汰；虽然被rnn双模型判定为高频数据，但是进入高频数据区后却没有被分配到桶而被淘汰的过程叫做次轮淘汰(次轮淘汰的对象是全局高频数据)；进入高频数据区分配到桶后一段时间后被替换的过程叫做末轮淘汰(末轮淘汰的对象包括全局高频数据和局部高频数据)。
72.末轮淘汰机制：
73.末轮淘汰的数据类型有两种，一种是局部高频数据，另外一种是全局高频数据。全局高频数据被淘汰需要满足以下条件：
74.①
全局桶没有空桶；
75.②
需要存入高频数据区的这个全局高频数据不在全局桶中；
76.③
在
②
中的这个全局高频数据的频率大于全局桶中所有频率的最小值。
77.在满足以上3个条件的情况下触发末轮淘汰——全局桶中频率最小的那个桶对应的全局高频数据会从高频数据区淘汰后存入低频数据区，淘汰后空出来的全局桶分配给需要的全局高频数据。如示例图5所示，全局高频数据data不在全局桶中且没有空的全局桶，因为data的频率为9比全局桶中所有频率的最小值data3的频率大，所以data3被淘汰。
78.末轮淘汰下来的全局高频数据，首先在低频数据区经过哈希映射到conservative-updatesketch
1.的某些桶上，然后依次判断每个桶中存储的频率值和末轮淘汰下来的被淘汰数据的频率大小关系，二者的最大值作为桶上的最终结果。具体示例如图6所示，data3经过哈希计算映射到三个桶上，三个桶上存储频率的值分别为《5,8,7》，这些值中只有5比data3中的频率值7小，最终值为5的桶结果被改为7，其它桶的值不变。如果末轮淘汰下来的全局高频数据经过哈希计算映射到多个桶上，其中有两个以上桶内的数据的频率值都小于末轮淘汰下来的全局高频数据的频率值，则将这两个以上桶内的数据的频率值都换成末轮淘汰下来的全局高频数据的频率值。
79.局部高频数据被淘汰的触发条件比较简单，当局部桶中的计时器归零时触发局部高频数据的末轮淘汰，计时器归零方式有两种：第一种，计时器计时结束归零；第二种，计时器未计时结束(说明局部桶不为空)，当与局部桶内的数据相异的新局部高频数据进来的时候，计时器被动置为零。如图7所示，当局部桶的计时器t归零时淘汰data4存入低频数据区。
80.末轮淘汰下来的局部高频数据(假设被淘汰的局部桶数据为data，频率为f)，首先被淘汰的数据data在低频数据区经过哈希映射到conservative-updatesketch的某些桶上，然后估计出data在低频数据区的估计值d，最后将d+f的值和经过哈希映射的每个桶上的值进行比较，如果桶上的值小于d+f，就用d+f替换桶上的值，否则不做更新。具体的示例如图8所示，首先从低频数据区估计出data4的估计频率为1，即d＝1，然后将4(1+3，3为被淘
汰时候局部桶内数据data4的频率f)与每个桶上的值进行比较，如果小于4就用4替换桶上的值。
81.首轮淘汰和次轮淘汰：
82.首轮淘汰由rnn双模型主动触发。次轮淘汰的触发条件是数据被判定为全局高频数据进入高频数据区，但是由于全局桶的数量有限，而且该数据的频率比高频数据区中所有全局高频数据的频率小(保证了数据流中频率最高的数据都存储在高频数据区)，对比全局高频数据末轮淘汰条件，次轮淘汰需要满足
①②
不满足条件
③
。首轮淘汰和次轮淘汰下来的数据会以保守更新的方式存入低频数据区，如图9所示。
83.保守更新是基于conservative-updatesketch
1.，当数据data经过哈希计算映射到conservative-updatesketch
1.的一些桶上，然后对所映射到的所有桶中值最小的那些桶进行+1操作，所映射到的所有桶中值最小的那些桶可以是只有一个桶，也可以是有多个桶，多个桶时值都是相等的。如图9，data是经过哈希计算映射到三个桶上，桶上的值分别为《4,7,2》，然后对最小值2的那个桶进行+1操作，更新最小值2所在的那个桶的值为3。
84.综上所述，全局高频数据和局部高频数据在末轮淘汰机制下对低频数据区的更新方式有所不同，主要原因是全局桶中存储了数据的“真实频率”，而局部桶只是存储了数据的部分频率(计时器清零所需时间段内的频率)。这样做的目的是全局桶的数量比局部桶数量多得多，所以全局高频数据的末轮淘汰并不会像局部高频数据那样频繁，如果局部桶存储的是“真实频率”，每次新的局部高频数据进入高频数据区的时候都去低频数据区获取估计频率对数据流的处理性能影响太大。
85.本发明基于rnn双模型的数据流频率估计方法的流程是：
86.1)数据获取单元：获得历史数据流，确定历史数据流频率估计的目标，对历史数据流中的数据进行打标，打标的标签分别为低频数据、全局高频数据和局部高频数据，建立数据集；
87.历史数据为已经产生的一些数据，比如该方法要用于处理将来10月份的数据流，则以前8、9月份已产生的数据流就是历史数据。
88.2)构建rnn双模型
89.所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，两个rnn模型都采用n-to-one结构，rnn-global模型用于判断数据是否为全局高频数据，rnn-local模型用于继续对通过rnn-global模型判断不是全局高频数据的数据进行预测，判断是否为局部高频数据；如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为局部高频数据。
90.利用步骤1)的数据集训练rnn双模型，获得训练好的rnn双模型，待估计的数据流经过训练好的rnn双模型被分类为低频、全局高频和局部高频三个类型的数据；
91.实施例中将ip和端口号作为rnn双模型的输入特征向量，输出为低频、全局高频和局部高频这三个类型的预测结果。如果数据被rnn-global模型判定为全局高频数据就跳出模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型再进一步判定。两个模型联合起来进行处理，只会得到当前数据的一个预测结果，即一个数据如果被rnn-global模型判定为高频数据，那么该数据就是全局高频数据；如果被判定为低频数据，
则该数据还有可能被rnn-local模型判定为局部高频数据；否则就是低频数据。
92.6)数据存储更新
93.rnn双模型判定一个数据为低频数据，该数据以保守更新的方式存入低频数据区；
94.rnn双模型判定一个数据为局部高频数据，该数据会被放入高频数据区的局部桶内，如果该数据和局部桶内的数据相同则桶内的频率累加1；如果局部桶为空或该数据和局部桶内数据相异(则不为空的情况下计时器被动置为0后触发末轮淘汰)，将该数据存入局部桶内，频率值为1，计时器t重新计时(计时器t比较短，一般依据数据流的处理速度设定，以10个数据处理时间为基准进行设置，如果一秒处理1000个数据，则t设为10ms)；
95.rnn双模型判定为全局高频数据，则遍历高频数据区内的所有全局桶，寻找该数据对应的桶并且记录频率最小的桶b，如果找到了对应的桶则频率+1；如果没有找到对应的桶，则该数据先保守更新到低频数据区，估计出该数据的频率g，当有空全局桶存在的情况下，就申请一个全局桶把该数据和估计出的频率值g存储在桶上，当没有空的全局桶时，则需要将桶b上的频率与g做比较，判断是否满足末轮淘汰的触发条件，如果不满足则之前的保守更新就属于次轮淘汰；
96.这里提到的保守更新是+1操作。
97.4)当需要估计某个数据的频率时，先遍历高频数据区的所有桶，如果与之相匹配桶是全局桶就返回桶中频率；如果匹配的局部桶，则进入低频数据区通过哈希计算从映射的桶中返回桶中最小值和局部桶中值的和；如果不在高频数据区则从低频数据区中通过计算获取桶中的最小值，进而实现数据流频率估计。
98.实施例：
99.本实施例数据流频率估计方法用于网络流量监测，监测网络的突发情况，监测各种大小数据包转发的数量，以网络中某个isp(网络服务提供商)关于两个链路a到b的数据包转发为例。目标是统计出1天内由链路a转发到链路b不同大小数据包的频率，然后可以从统计中估计出不同大小数据包的频率，如查询1天内转发大小为1m的数据包的个数是多少？
100.基于历史的包转发数据，每个数据包中包括源ip、目标ip(ip包括主机地址和端口号)和包的大小等，训练出rnn双模型，一般isp的两个链路的数据流特征在短期内是不会有太大变化的，于是可以使用以往的历史数据训练出rnn双模型，在实施例中使用目标ip(如某一个包的主机地址：127.33.46.88，端口号：8080)作为训练的特征向量。
101.具体实施步骤：
102.1)数据集预处理：数据集中数据元组的格式设置为《目标主机地址、目标端口号、数据包大小(单位：字节)、标签(0表示全局高频，1表示局部高频，2表示低频数据)》,如《127.33.46.88、8080、512、0》。首先，统计出历史网络流量监测数据中不同大小的数据包出现的频率，如(512、9931)表示数据集中大小为512字节的数据包有9931个；然后，根据频率进行从大到小排序，取排序后的前百分之十数据包作为全局高频数据；最后，依据这些高频数据的数据包大小给匹配的元组打上值为0的标签，至此全局高频数据的标签添加完毕；
103.接下来对数据集中局部高频数据进行添加标签，首先，在数据流上取一个大小为10的滑动窗口，沿着数据流依次向后滑动，当某大小的数据包在窗口中出现的频率大于等于7的时候，如果匹配的元组没有被打上0的标签就给该元组打上值为1的标签，至此局部高频数据的标签添加完毕；
104.最后对那些没有标签的元组打上值为2的标签，表示该元组属于低频数据，最终标签值0、1、2表示全局高频、局部高频和低频；至此完成数据集打标的工作。
105.2)建rnn双模型
106.所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，两个rnn模型都采用n-to-one结构，rnn-global模型用于判断数据是否为全局高频数据，rnn-local模型用于继续对通过rnn-global模型判断不是全局高频数据的数据进行判断，是否为局部高频数据；如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为局部高频数据。
107.数据集打标完成后，对rnn双模型进行训练，取元组的前两项作为训练输入的基本单元如元组《127.33.46.88、8080、512、0》的输入形式为[[127、33、46、88、8080]]，假设对应的输出形式[0.7、0.3、0.5]——0.7、0.3和0.5分别表示对标签值0、1和2的预测打分，值越大表示对应的预测结果可能性越大。经过多轮的训练和评估之后获得训练好的rnn双模型并保存。
[0108]
3)数据存储区域划分：将数据存储区域划分为高频数据区和低频数据区，高频数据区桶的类型有两种，一种是存储全局高频数据的全局桶，另外一种是存储局部高频数据的局部桶，全局桶以数组的方式排列，全局桶中有多个桶，全局桶中每个桶存储一个数据和数据对应的频率；局部桶的数量为1，桶内存储了数据、计时器值t和频率；低频数据区存储的是被rnn双模型判定为低频和从高频数据区淘汰下来的“高频数据”，低频数据区的存储结构基于conservative-updatesketch
1.——多个哈希函数对应多个桶序列，哈希函数的值域就是桶序列的长度。
[0109]
4)接下来使用训练好的rnn双模型对具体的数据流进行处理，取出数据包的主机地址和端口号作为rnn双模型的输入，数据包的大小作为框架中数据data。通过rnn双模型判定为低频的数据包，对数据data进行哈希计算，以保守更新的方式存入低频数据区；
[0110]
通过rnn双模型判定为局部高频的数据data，首先检查data是否在局部桶中，如果存在就对局部桶的频率+1，如果不存在且桶为空的情况下就在局部桶内存储data值和频率值1并且开始新的计时，当一个不同于局部桶内已有的局部高频数据的新局部高频数据进来时先前的局部高频数据将从高频数据区淘汰，此时计时器被动置为零，执行局部高频数据的末轮淘汰，新的局部高频数据放入局部桶内，频率值1，并且开始新的计时；
[0111]
通过rnn双模型判定为全局高频数据data，则遍历高频数据区内的所有全局桶，寻找该数据对应的桶并且记录频率最小的桶b，如果找到了对应的桶则频率+1；如果没有找到对应的桶，则该数据先保守更新到低频数据区，估计出该数据的频率g，当有空全局桶存在的情况下，就申请一个全局桶把该数据和频率值f存储在桶上，当没有空的全局桶时，则需要将桶b上的频率和g做比较，判断是否满足末轮淘汰的触发条件，如果不满足则之前的保守更新就属于次轮淘汰；
[0112]
5)经过1天的数据处理，所有数据包的统计信息被存放在高频数据区和低频数据区，如果查询大小1m数据包的频率时先到高频数据区遍历所有的桶，如果找到1m(1m＝1048576字节)对应的桶是全局桶则返回桶中的频率；如果是局部桶，则进入低频数据区通过哈希计算从映射的桶中返回桶中最小值和局部桶中值的和；否则进入低频数据区通过哈
希计算从映射的桶中返回最小值，这个最小值就是1m大小数据包的估计频率。
[0113]
本发明中rnn和conservative-updatesketch均属于现有的概念和方法，其中保守更新方式是conservative-updatesketch方法中成熟的更新方式，rnn模型是神经网络中的一种。
[0114]
本发明未述及之处适用于现有技术。
[0115]
[1]estanc,vargheseg.newdirectionsintrafficmeasurementandaccounting[j].acm sigcommcomputercommunicationreview,2002,32(1):75.
技术特征：1.一种基于rnn双模型的数据流频率估计方法，其特征在于，该估计方法的流程是：1)数据获取单元：获得历史数据流，确定历史数据流频率估计的目标，对历史数据流中的数据进行打标，打标的标签分别为低频数据、全局高频数据和局部高频数据，建立数据集；2)构建rnn双模型所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，两个rnn模型都采用n-to-one结构，rnn-global模型用于判断数据是否为全局高频数据，rnn-local模型用于继续对通过rnn-global模型判断不是全局高频数据的数据进行预测，判断是否为局部高频数据；如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为局部高频数据；利用步骤1)的数据集训练rnn双模型，获得训练好的rnn双模型，待估计的数据流经过训练好的rnn双模型被分类为低频、全局高频和局部高频三个类型的数据；3)数据存储更新rnn双模型判定一个数据为低频数据，该数据以保守更新的方式存入低频数据区；rnn双模型判定一个数据为局部高频数据，该数据会被放入高频数据区的局部桶内，如果该数据和局部桶内的数据相同则桶内的频率累加1；如果局部桶为空或该数据和局部桶内数据相异，将该数据存入局部桶内，频率值为1，计时器t重新计时；rnn双模型判定为全局高频数据，则遍历高频数据区内的所有全局桶，寻找该数据对应的桶并且记录频率最小的桶b，如果找到了对应的桶则频率+1；如果没有找到对应的桶，则该数据先保守更新到低频数据区，估计出该数据的频率g，当有空全局桶存在的情况下，就申请一个全局桶把该数据和估计出的频率值g存储在桶上，当没有空的全局桶时，则需要将桶b上的频率与g做比较，判断是否满足末轮淘汰的触发条件，如果不满足则之前的保守更新就属于次轮淘汰；4)当需要估计某个数据的频率时，先遍历高频数据区的所有桶，如果与之相匹配桶是全局桶就返回桶中频率；如果匹配的局部桶，则进入低频数据区通过哈希计算从映射的桶中返回桶中最小值和局部桶中值的和；如果不在高频数据区则从低频数据区中通过计算获取桶中的最小值，进而实现数据流频率估计。2.根据权利要求1所述的基于rnn双模型的数据流频率估计方法，其特征在于，所述末轮淘汰的数据类型有两种，一种是局部高频数据，另外一种是全局高频数据；所述全局高频数据被末轮淘汰需要同时满足以下条件：
①
全局桶没有空桶；
②
需要存入高频数据区的这个全局高频数据不在全局桶中；
③
在
②
中的这个全局高频数据的频率大于全局桶中频率的最小值。在满足条件的情况下触发末轮淘汰——全局桶中频率最小的那个桶对应的全局高频数据会从高频数据区淘汰后存入低频数据区，淘汰后空出来的全局桶分配给需要的全局高频数据；所述末轮淘汰下来的全局高频数据，首先在低频数据区经过哈希映射到conservative-update sketch的某些桶上，然后依次判断每个桶中存储的频率值和末轮淘
汰下来的被淘汰数据的频率大小关系，二者的最大值作为桶上的最终结果；如果末轮淘汰下来的全局高频数据经过哈希计算映射到多个桶上，其中有两个以上桶内的数据的频率值都小于末轮淘汰下来的全局高频数据的频率值，则将这两个以上桶内的数据的频率值都换成末轮淘汰下来的全局高频数据的频率值；所述局部高频数据被末轮淘汰的触发条件为：当局部桶中的计时器归零时触发局部高频数据的末轮淘汰；当局部桶的计时器归零的时候淘汰已有局部高频数据并存入低频数据区；末轮淘汰下来的局部高频数据，假设被淘汰的局部桶数据为data，频率为f，首先被淘汰的数据data在低频数据区经过哈希映射到conservative-update sketch的某些桶上，然后估计出data在低频数据区的估计值d，最后将d+f的值和经过哈希映射的每个桶上的值进行比较，如果桶上的值小于d+f，就用d+f替换桶上的值，否则不做更新。3.根据权利要求2所述的基于rnn双模型的数据流频率估计方法，其特征在于，所述次轮淘汰的触发条件是数据虽然被判定为全局高频数据进入高频数据区，但是由于全局桶的数量有限，而且该数据的频率比高频数据区中所有全局高频数据的频率小，对比全局高频数据末轮淘汰条件，次轮淘汰需要满足
①②
不满足条件
③
；次轮淘汰下来的数据会以保守更新的方式存入低频数据区。4.根据权利要求2所述的基于rnn双模型的数据流频率估计方法，其特征在于，所述计时器归零方式有两种：第一种，计时器计时结束归零；第二种，计时器未计时结束，说明局部桶不为空，当与局部桶内的数据相异的新局部高频数据进来的时候，计时器被动置为零。5.一种权利要求1-4任一所述的基于rnn双模型的数据流频率估计方法的应用，该估计方法用于网络流量监测，监测网络的突发情况。6.一种用于网络流量监测的数据流频率估计方法，其特征在于，该方法的步骤是：1)数据集预处理：数据集中数据元组的格式设置为<目标主机地址、目标端口号、数据包大小(单位：字节)、标签(0表示全局高频，1表示局部高频，2表示低频数据)>，首先，统计出历史网络流量监测数据中不同大小的数据包出现的频率，然后，根据频率进行从大到小排序，取排序后的前百分之十数据包作为全局高频数据；最后，依据这些高频数据的数据包大小给匹配的元组打上值为0的标签，至此全局高频数据的标签添加完毕；接下来对数据集中局部高频数据进行添加标签，首先，在数据流上取一个大小为10的滑动窗口，沿着数据流依次向后滑动，当某大小的数据包在窗口中出现的频率大于等于7的时候，如果匹配的元组没有被打上0的标签就给该元组打上值为1的标签，至此局部高频数据的标签添加完毕；最后对那些没有标签的元组打上值为2的标签，表示该元组属于低频数据，最终标签值0、1、2表示全局高频、局部高频和低频；至此完成数据集打标的工作；2)建rnn双模型所述rnn双模型包括rnn-global模型和rnn-local模型，rnn-global模型和rnn-local模型串联，两个rnn模型都采用n-to-one结构，rnn-global模型用于判断数据是否为全局高频数据，rnn-local模型用于继续对通过rnn-global模型判断不是全局高频数据的数据进行判断，是否为局部高频数据；如果数据被rnn-global模型判定为全局高频数据就跳出rnn双模型；如果被rnn-global模型判定为低频数据，那么还会经过rnn-local模型判定是否为
局部高频数据；数据集打标完成后，对rnn双模型进行训练，取元组的前两项作为训练输入的基本单元，rnn双模型的输出形式表示对标签值0、1和2的预测打分，值越大表示对应的预测结果可能性越大，经过多轮的训练和评估之后获得训练好的rnn双模型并保存；3)数据存储区域划分：将数据存储区域划分为高频数据区和低频数据区，高频数据区桶的类型有两种，一种是存储全局高频数据的全局桶，另外一种是存储局部高频数据的局部桶，全局桶以数组的方式排列，全局桶中有多个桶，全局桶中的桶的遍历方式是顺序遍历，全局桶中存储一个数据和数据对应的频率；局部桶的数量为1，桶内存储了数据、计时值t和频率；低频数据区存储的是被rnn双模型判定为低频的数据和从高频数据区淘汰下来的“高频数据”，低频数据区的存储结构基于conservative-update sketch——多个哈希函数对应多个桶序列，哈希函数的值域就是桶序列的长度；4)接下来使用训练好的rnn双模型对具体的数据流进行处理，取出数据包的主机地址和端口号作为rnn双模型的输入，数据包的大小作为框架中数据data；通过rnn双模型判定为低频的数据包，对数据data进行哈希计算，以保守更新的方式存入低频数据区；通过rnn双模型判定为局部高频的数据data，首先检查data是否在局部桶中，如果存在就对局部桶的频率+1，如果不存在且桶为空的情况下就在局部桶内存储data值和频率值1并且开始新的计时，当一个不同于局部桶内已有的局部高频数据的新局部高频数据进来时先前的局部高频数据将从高频数据区淘汰，此时计时器被动置为零，执行局部高频数据的末轮淘汰，新的局部高频数据放入局部桶内，频率值1，并且开始新的计时；通过rnn双模型判定为全局高频数据data，则遍历高频数据区内的所有全局桶，寻找该数据对应的桶并且记录频率最小的桶b，如果找到了对应的桶则频率+1；如果没有找到对应的桶，则该数据先保守更新到低频数据区，估计出该数据的频率g，当有空全局桶存在的情况下，就申请一个全局桶把该数据和频率值f存储在桶上，当没有空的全局桶时，则需要将桶b上的频率和g做比较，判断是否满足末轮淘汰的触发条件，如果不满足则之前的保守更新就属于次轮淘汰；5)经过一段时间的数据处理，所有数据包的统计信息被存放在高频数据区和低频数据区，查询目标大小数据包的频率时先到高频数据区遍历所有的桶，如果找到目标大小数据包对应的桶是全局桶则返回桶中的频率；如果是局部桶，则进入低频数据区通过哈希计算从映射的桶中返回桶中最小值和局部桶中值的和；否则进入低频数据区通过哈希计算从映射的桶中返回最小值，这个最小值就是目标大小数据包的估计频率。7.一种计算机可读存储介质，所述存储介质中存储有计算机程序，所述计算机程序适用于被计算机加载时执行权利要求1-4所述的基于rnn双模型的数据流频率估计方法或权利要求5所述的用于网络流量监测的数据流频率估计方法。8.一种装置，包括：数据获取单元，用于获取标注了低频、全局高频、局部高频的数据流；分类模型，用于对数据流进行低频、全局高频、局部高频的分类；存储单元，用于将高频数据区和低频数据区分开存储，高频数据区中存储全局高频数据和局部高频数据，低频数据区用于存储低频数据和淘汰下来的数据；更新单元，采用首轮、次轮和末轮淘汰机制对高频数据区和低频数据区进行更新；
查询单元，用于估计目标数据的频率。
技术总结本发明为基于RNN双模型的数据流频率估计方法，该估计方法结合当下流行的循环神经网络模型，将频率估计和神经网络结合在一起，基于RNN和Conservative-Update Sketch实现了更好的误差控制和更加精确的频率估计。该方法对数据流中数据项的频率进行估计，通过两个RNN神经网络模型对数据流进行分类，将高频数据和低频数据分开存储，降低高频数据和低频数据之间的哈希冲突，从而提高数据流频率估计的精度，由于高频数据单独存储，可以减少高频数据哈希计算的次数，在一定程度上提高了数据流的处理效率。该估计方法应用在网络流量监测中，能够监测网络的突发情况，提高监测的精度和效率。提高监测的精度和效率。提高监测的精度和效率。
技术研发人员：杨亮 何政波 张亚娟 许晓笛 温先斌
受保护的技术使用者：河北工业大学
技术研发日：2022.07.25
技术公布日：2022/11/1
