数据流中带权值频繁项挖掘方法和系统

摘要

本发明提供一种数据流中带权值频繁项挖掘方法，数据流中的带权值频繁项动态存储在部分排序的流概要数据结构中；部分排序的流概要数据结构包括多个按开始值顺序排列的桶，桶还包括有由条目通过双向循环链表所构成的组；桶中的条目包括数据项名称、计数器值以及计数器的最大可能误差，条目的计数器值大于所在桶的开始值而小于或等于所在桶的开始值与桶范围系数之和；包括：从所接收到的数据流中依次取出数据项；根据所取出的数据项的名称和权值在部分排序的流概要数据结构中找出合适的桶以及合适的条目，并为所述条目赋值；根据用户的命令按序遍历所述的部分排序的流概要数据结构，所得到的计数器值大于一阈值的条目为所要挖掘的带权值频繁项。

说明书

技术领域

本发明涉及数据挖掘领域，特别涉及一种数据流中带权值频繁项挖掘方法和系统。

背景技术

数据流是一个随时间演化的无穷的数据序列，在日常生活的各个方面都有广泛的应用，而带权值频繁项挖掘则是数据流的其中一种典型应用。所谓的带权值频繁项是指在数据集合中超过一定阈值的数据项，假设一个数据集合中所有数据项的权值总和N，给定支持度s∈(0，1)，则所有权值超过sN的数据项被称为频繁项。带权值频繁项挖掘则是指从某一数据集合(如数据流)的诸多数据项中找出满足一定条件的带权值频繁项。在数据流中实现带权值频繁项挖掘具有广泛的应用前景，尤其用于解决有限计算资源条件下频繁项的近似统计和挖掘问题。例如，传感器网络中监测信号、互联网中IP数据包流量、Web服务器上用户点击记录、电信公司通话记录等的统计与挖掘。

与传统的数据库不同，数据流具有数据无穷性的特点。数据流的这一特点导致其数据无法得到全部保存，因此对数据流数据的处理只能一次完成，无法反复进行。这也为带权值频繁项挖掘在数据流中的实现较在传统数据库环境的实现带来了更大的挑战。近年来，研究者对数据流中带权值频繁项挖掘技术展开了大量研究工作，并取得了积极成果。

在参考文献1“Approximate frequency counts over data streams.In：Proceedings of the 28th international conference on Very Large Data Bases.Hong Kong，China，2002.346-357”中，G.Manku等人提出了一种被称为Lossy Counting的频繁项挖掘算法。该算法把数据流分成若干个连续到来的、且数据项个数相等的数据块，并根据数据项所属数据类型的不同进行分别统计。数据项到来时，首先查询是否有计数器监视该数据项所属数据类型，有则相应计数器值加1，没有就创建新的计数器来监视该数据项所属数据类型；然后判断是否到达数据块边界，到达边界则释放部分计数器，这些计数器满足计数值与计数器创建时所在数据块编号之和小于当前数据块编号的限制条件。因为需要线性扫描一遍所有的计数器，因此，参考文献1所披露方法对单数据项的最坏更新时间将会达到当误差ε较小时，更新时间会较长，影响处理性能。

在参考文献2“An integrated efficient solution for computing frequent andtop-k elements in data streams.ACM Transactions on Database Systems(TODS)，2006，31(3)：1095-1133”中，A.Metwally等人提出了一种被称为SpaceSaving的频繁项挖掘算法。在该算法中，对于数据流中到达的每个数据项，若有相应的计数器，则更新计数值；否则若没有空闲的计数器，则代替计数估计值最小(min)的数据项，并设其计数值为min+1，误差为min。在Stream-Summary中，所有具有相同计数值的项组成一个链表，这些项指向共同的桶(parentBueket)，且parentBucket的值为指向它的所有项的计数值的和，并按值排序。该方法始终需要维护计数值最小的数据项以便替换，即便采用最快的数据结构heap，每来一个数据项需要次操作，因此，虽然该方法较参考文献1方法对单数据项的最坏更新时间有所降低，可以达到但当误差ε较小时，更新时间仍然会较长，依然会对处理性能产生影响。

发明内容

本发明的目的是克服现有的带权值频繁项挖掘方法对单数据项的最坏更新时间较长，处理性能较低的缺陷，从而提供一种对单数据项的最坏更新时间较短、处理性能较高的带权值频繁项挖掘方法。

为了实现上述目的，本发明提供了一种数据流中带权值频繁项挖掘方法，数据流中的带权值频繁项动态存储在部分排序的流概要数据结构中；所述部分排序的流概要数据结构包括多个按开始值顺序排列的桶，所述桶还包括有由条目通过双向循环链表所构成的组；所述桶中的条目包括数据项名称、计数器值以及计数器的最大可能误差，所述条目的计数器值大于所在桶的开始值而小于或等于所在桶的开始值与桶范围系数之和；该方法包括：

步骤1)、从所接收到的数据流中依次取出数据项，所述数据项包括数据项名称和数据项权值；

步骤2)、根据所取出的数据项的数据项名称和数据项权值在所述的部分排序的流概要数据结构中找出合适的桶以及合适的条目，并为所述条目中的数据项名称、计数器值以及计数器的最大可能误差赋值；

步骤3)、根据用户的命令按序遍历所述的部分排序的流概要数据结构，所得到的计数器值大于一阈值的条目为所要挖掘的带权值频繁项。

上述技术方案中，在所述的步骤2)和步骤3)之间还包括对部分排序的流概要数据结构的剪枝操作步骤。

上述技术方案中，数据项与条目间映射关系存放在哈希表中，空闲条目池用于维护空闲条目；所述的步骤2)包括：

步骤2-1)、判断所取出数据项的数据项名称是否在所述哈希表中，若不存在，执行下一步，否则，执行步骤2-4)；

步骤2-2)、从所述空闲条目池中取出一空闲条目，然后判断该空闲条目是否已经存在于所述哈希表中，若存在，则从哈希表中删除该空闲条目后，对该空闲条目赋值，否则，直接对该空闲条目赋值；

步骤2-3)、将赋值后的空闲条目的信息插入到所述哈希表，将赋值后的空闲条目插入到所述的部分排序的流概要数据结构，然后执行步骤3)；

步骤2-4)、若所取出数据项所对应的条目在空闲节点池中，将该条目从空闲节点池中删除，然后为数据项所对应的条目赋值，将赋值后的条目插入到所述的部分排序的流概要数据结构；

步骤2-5)、若所取出数据项所对应的条目不在空闲节点池中，从部分排序的流概要数据结构中找出所取出数据项所对应的条目，修改所述条目中的计数器值，并在修改后的计数器值超出所在桶的数值范围的前提下，将该条目转移到新的桶中，然后执行步骤3)。

上述技术方案中，在所述的步骤2-2)和步骤2-4)中，对条目赋值包括：

令ID＝i，count_i＝ε_i+c；

其中，所述的ID表示空闲条目的数据项名称，所述的i表示所取出数据项的数据项名称，所述的ε_i代表所取出数据项i的条目的计数器的最大可能误差，j代表当前窗口的标识的变量，s代表窗口大小系数，r表示所述的桶范围系数，表示向下取整，count_i代表所取出数据项i的条目的计数器值，c代表所取出数据项的数据项权值。

上述技术方案中，在所述的步骤2-3)和步骤2-4)中，将赋值后的条目插入到所述的部分排序的流概要数据结构包括：

步骤2-3-1)、判断所述的部分排序的流概要数据结构是否为空，若为空，创建一个新桶作为该部分排序的流概要数据结构的第一个桶，并将所述赋值后的空闲条目插入到新创建桶的组内；若不为空，执行下一步；

所述新桶的开始值为其中，svalue代表桶的开始值，r表示所述的桶范围系数，表示向下取整，count_i代表所取出数据项i的条目的计数器值；

步骤2-3-2)、从部分排序的流概要数据结构的第一个桶开始向后遍历，如果能够找到一个满足条件svalue＜count_i≤svalue+r的桶，则将赋值后的空闲条目插入到该桶的组内，如果不能找到满足前述条件的桶，则创建一个新桶，然后将新桶插入到桶列表的正确位置，并将该条目插入新桶的组内；所述新桶的开始值为

上述技术方案中，在所述的步骤2-5)中，将条目转移到新的桶包括：

步骤2-5-1)、从所要移动条目当前所在的桶开始向后遍历，判断是否能找到一个桶满足svalue＜count_i≤svalue+r，若能，则执行下一步，否则，执行步骤2-5-4)；其中，svalue代表桶的开始值，r表示所述的桶范围系数，count_i代表所取出数据项i的条目的计数器值；

步骤2-5-2)、将所要转移条目移动到满足前述条件的桶中，并将该条目从原先的桶中删除；

步骤2-5-3)、若所要转移条目原先所在的桶在删除该条目后变为空，则将该桶从桶列表中删除，结束条目转移操作；

步骤2-5-4)、创建一个新桶，然后将所创建的新桶插入到桶列表的正确位置；所述新桶的开始值为

步骤2-5-5)、将所要转移的条目移到到新创建桶的组内，并将该条目从原先的桶中删除；

步骤2-5-6)、若所要转移条目原先所在的桶在删除该条目后变为空，则将该桶从桶列表中删除，结束条目转移操作。

上述技术方案中，在所述的步骤3)中，按照反向遍历的方式遍历所述的部分排序的流概要数据结构。

上述技术方案中，在所述的步骤3)中，所述阈值为用户支持度门限φ与所有数据项的权值总和N的乘积。

上述技术方案中，所述剪枝操作包括：

步骤a)、改变所有数据项的权值总和N的值，令N＝N+c，其中c表示所取出的数据项的数据项权值；

步骤b)、判断所述的部分排序的流概要数据结构是否到达了窗口边界，若到达窗口边界，则执行下一步，否则，结束剪枝操作；

步骤c)、递增系统中用于表示当前窗口标识的变量j，对所述部分排序的流概要数据结构中所有开始值为的桶，释放桶组内所有的条目到空闲条目池，然后将这些桶从桶列表中删除；其中，svalue表示桶的开始值，r表示桶范围系数，表示向下取整，s代表窗口大小系数。

本发明还提供了一种数据流中带权值频繁项挖掘系统，包括用于存储数据流中的带权值频繁项的部分排序的流概要数据结构、数据项读取模块、条目查找模块以及带权值频繁项挖掘模块；其中，

所述部分排序的流概要数据结构包括多个按开始值顺序排列的桶，所述桶还包括有由条目通过双向循环链表所构成的组；所述桶中的条目包括数据项名称、计数器值以及计数器的最大可能误差，所述条目的计数器值大于所在桶的开始值而小于或等于所在桶的开始值与桶范围系数之和；

所述的数据项读取模块用于从所接收到的数据流中依次取出数据项，所述数据项包括数据项名称和数据项权值；

所述的条目查找模块根据所取出的数据项的数据项名称和数据项权值在所述的部分排序的流概要数据结构中找出合适的桶以及合适的条目，并为所述条目中的数据项名称、计数器值以及计数器的最大可能误差赋值；

所述的带权值频繁项挖掘模块用于根据用户的命令按序遍历所述的部分排序的流概要数据结构，所得到的计数器值大于一阈值的条目为所要挖掘的带权值频繁项。

上述技术方案中，还包括对部分排序的流概要数据结构做剪枝操作的剪枝模块。

本发明提供的方法能够提供单数据项最坏更新时间为O(1)的处理速度，使得本发明具有更好的处理性能，更高的吞吐量。

附图说明

图1为本发明中所涉及的POSS的一个示例图；

图2本发明方法的流程图；

图3为本发明方法与现有技术中的Space Saving方法、Lossy Counting方法的实验效果比较图；其中，

图3(a)为三种方法在CERNET测试数据集上的实验效果比较图；

图3(b)为三种方法在CAIDA-OC48测试数据集上的实验效果比较图；

图3(c)为三种方法在CAIDA-OC192测试数据集上的实验效果比较图。

具体实施方式

下面结合附图和具体实施方式对本发明进行说明。

在对本发明的方法进行详细说明前，首先对方法中所涉及到的数据结构进行说明，以方便理解。

部分排序的流概要数据结构(Partial-Ordered-Stream-Summary，POSS)：部分排序的流概要数据结构用于动态存储数据流上的频繁项，该数据结构包括多个按序排列的桶，每个桶包括有一个开始值(svalue)和一个由条目通过双向循环链表所构成的组。桶中的每个条目都指向代表桶头的数据结构，桶头也会指向本桶内的任意一个条目。所述条目包含有3个数据域，分别为数据项名称(ID)、计数器值(count_ID)以及计数器的最大可能误差(ε_ID)。每个桶内的条目应当满足svalue＜count_ID≤svalue+r，其中的svalue代表条目所在桶的开始值，r代表桶范围系数。

在图1中给出了所述部分排序的流概要数据结构的一个范例，在该范例中，包括有三个桶，第一个桶的开始值为0，桶范围系数r的大小为1500，因此第二个桶的开始值为1500，第三个桶的开始值为3000。由于在该数据结构中，桶之间按序排列，因此，根据桶的开始值，第一个桶、第二个桶、第三个桶之间采用双向链表依次连接。位于桶内的条目只要求其计数器值满足前述的svalue＜count_ID≤svalue+r，并不要求其在桶内按序排列。虽然在图1中，计数器值为700的条目位于计数器值为600的条目之后，且位于计数器值为1500的条目之前，但在实际操作中，计数器值为700的条目同样可以位于计数器值为600的条目之前。

空闲条目池：用于维护系统中的空闲条目的双向循环链表，在本实施例中，空闲条目池用P表示。空闲条目池一般保存在内存中，空闲条目池中的各个条目的组成与前述部分排序的流概要数据结构中的条目相同。

哈希表：用于实现通过数据项快速访问数据项所在条目的表结构，在本实施例中，哈希表可以用H表示。虽然在下面的实施例中用哈希表来实现数据的快速访问，但本领域技术人员也可以采用具有类似功能的其它数据结构。

流数据缓存队列：用于缓存数据流中数据的队列。虽然在下面的实施例中用流数据缓存队列来保存数据流中的数据，但本领域技术人员也可以采用具有类似功能的其它数据结构。

在对本发明中所采用的数据结构做上述说明的基础上，参考图2，下面对本发明方法的实现过程进行说明。

用户在采用本发明方法从数据流中挖掘带权值频繁项前，需要先设定有关的输入参数。所设定的输入参数包括用户支持度门限φ，用户许可误差ε，窗口大小系数s和桶范围系数r。其中的用户支持度门限φ以及用户许可误差ε与用户所要挖掘的带权值频繁项的范围有关，一般来说，用户所要挖掘的带权值频繁项应当大于“φ×N”(其中N代表到目前为止所有数据项的权值的总和)。由于在实际应用中输出值是估计值，因此需要保证输出的精度。实际应用把满足下面三个条件的输出叫做ε-近似输出：1)所有真实值大于“φ×N”的项目都必须输出；2)所有真实值小于“(φ-ε)×N”的项目都不能输出；3)所有输出项目的估计值和其真实值之间的误差小于“ε×N”。本发明能够满足ε-近似输出。在本实施例中，φ的取值范围为(0，1)，ε的取值范围为(0，φ)。窗口大小系数s与流数据窗口的大小有关。流数据窗口反映了在接收多少流量的数据后，要对前述POSS做剪枝操作，而剪枝操作是指去除POSS中不符合条件的数据项。流数据窗口大小用w表示，其中表示向上取整，s常取正整数。桶范围系数r在前面的说明中已经提到，因此不做重复说明。此外，用户还需要初始化系统变量j、N，令j＝0、N＝0。其中j为非负整数，代表当前窗口的ID，N的含义在前面已经说明。

在完成上面的准备工作以后，就可以开始对数据流的处理。在接收数据流后，将数据流中的数据按照到达的顺序缓存到流数据缓存队列中。在对数据做与频繁项挖掘有关的操作时，首先从流数据缓存队列的头部取出一个数据项，数据项中包括数据项的名称和数据项的权值。为了描述的方便，用v表示数据项，用i表示数据项的名称，用c表示数据项的权值。

从流缓存队列中取出数据项后，就要考虑如何将该数据项存放到POSS中以及存放到POSS的哪个位置。

首先，判断数据项名称i是否在哈希表H中，如果存在则表明该数据项在先前已经出现过，如果不在哈希表H中，则说明该数据项先前没有出现过，或虽然出现过但已经从哈希表中删除。对数据项是否在哈希表中的后续处理过程具有明显的不同，因此在下文中分别加以说明。

当数据项名称i不在哈希表H中时，先从空闲节点池P中取出一个空闲条目。然后对该空闲条目是否已经存在于哈希表H中进行判断，如果是的话，将该空闲条目从哈希表中删除，以避免同一个条目被两个不同的数据项同时使用，然后对该空闲条目进行赋值，如果否的话，就直接对该空闲条目进行赋值。在对空闲条目进行赋值的过程中，令ID＝i，(表示向下取整)，count_i＝ε_i+c，然后将该赋值后的条目的信息插入到哈希表H，将赋值后的条目插入到所述的部分排序的流概要数据结构POSS中。

在将赋值后的条目插入到POSS中时，首先判断POSS是否为空，如果为空，则创建一个新桶作为POSS的第一个桶，并将该条目插入到新创建桶的组内，新创建桶的开始值为如果POSS不为空，则从POSS的第一个桶开始向后遍历，如果能够找到一个满足条件svalue＜count_i≤svalue+r的桶，则将该条目插入到该桶的组内。如果不能找到满足前述条件的桶，则创建一个新桶，然后将新桶插入到桶列表的正确位置，并将该条目插入新桶的组内。新桶的开始值为在上述插入过程中，由于桶内条目间不做排序，因此在将条目插入到桶内时，无需遍历，有效地节省了运行时间。

当数据项名称i在哈希表H中时，该数据项名称所代表的数据项可能存在于空闲节点池中，也可能已经存在于POSS中。如果有则代表该数据项在空闲节点池中，需要将包含数据项i的条目从空闲节点池中删除，并对该条目进行赋值，令ID＝i，count_i＝ε_i+c，然后将赋值后的条目插入到POSS中。关于如何将赋值后的条目插入到POSS的具体实现已经在前文中做了详细说明，不再此处重复。如果不存在则代表该数据项已经在POSS中，通过哈希表可以快速地找到数据项所在条目，由于条目有指向其所在桶的指针，因此也能快速地找到数据项所在桶。在找到数据项所在的桶以及条目后，对条目中的值进行修改，令count_i＝count_i+c。由于在修改条目中的值以后，条目的数值可能已经超出了所在桶的数值范围，在此情况下，需要将条目转移到新的桶中。如果i当前所在桶的开始值为svalue，而count_i＞svalue+r，那么需要在POSS中将数据项i所在条目转移到其他桶中。

在POSS中将条目转移到其他桶中时，首先从条目当前所在的桶开始向后遍历，如果找到一个桶满足svalue＜count_i≤svalue+r，则将所要转移的条目移动到满足前述条件的桶中，并将该条目从原先的桶中删除。如果原先的桶在删除条目后变为空，还要将该桶从桶列表中删除。如果不能从POSS中找到满足前述条件的桶，则要创建一个新桶，然后将新桶插入到桶列表的正确位置，将所要转移的条目移动到新桶的组内，并将该条目从原先的桶中删除。新创建桶的开始值为如果原先的桶在删除条目后变为空，还要将该桶从桶列表中删除。

以上是对数据项i如何在POSS中存放的说明。虽然在上述实施例中，以数据流中的一个数据项为例，对其存放过程做了说明，但对于数据流中的其他数据项，在POSS中的存放过程也与之类似，可参照上述说明实现各个数据项在POSS中的存放。

作为一种优选实现方式，本实施例在不断地将数据流中的数据项存放到POSS中的同时，还可以对POSS做剪枝操作，去除POSS中那些不可能成为频繁项的条目，以节省资源、加快查询速度。在剪枝操作前，先改变系统中的N值，令N＝N+c，然后判断POSS是否达到了窗口边界，若达到窗口边界表示需要做具体的剪枝操作，否则，就结束剪枝操作。如果N≥(j+1)w，那就表示POSS已经达到了窗口边界。在做具体的剪枝操作时，首先令j＝j+1，然后对部分排序的流概要数据结构POSS中所有开始值为的桶作如下操作：首先将该桶的组内所有的条目释放到空闲条目池P中，然后将该桶从桶列表中删除。

在上述的流程中，用户可以根据自己的需要随时查找、显示所要挖掘的带权值频繁项。在查找所要挖掘的带权值频繁项时，遍历部分排序的流概要数据结构POSS，输出其中所有count≥φN的条目。考虑到POSS中的桶按照升序依次排列，因此，为了提高查找速度，在一种优选实现方式中，在遍历部分排序的流概要数据结构POSS时，采用反向遍历的方法。

本发明的方法由于采用了部分排序的数据结构POSS，使得单数据项最坏更新时间可以提高到O(1)，从而具有更高的吞吐量。

本发明还提供了一种与上述方法相对应的系统，该系统包括用于存储数据流中的带权值频繁项的部分排序的流概要数据结构、数据项读取模块、条目查找模块以及带权值频繁项挖掘模块；其中，

所述部分排序的流概要数据结构包括多个按开始值顺序排列的桶，所述桶还包括有由条目通过双向循环链表所构成的组；所述桶中的条目包括数据项名称、计数器值以及计数器的最大可能误差，所述条目的计数器值大于所在桶的开始值而小于或等于所在桶的开始值与桶范围系数之和；

所述的数据项读取模块用于从所接收到的数据流中依次取出数据项，所述数据项包括数据项名称和数据项权值；

所述的条目查找模块根据所取出的数据项的数据项名称和数据项权值在所述的部分排序的流概要数据结构中找出合适的桶以及合适的条目，并为所述条目中的数据项名称、计数器值以及计数器的最大可能误差赋值；

所述的带权值频繁项挖掘模块用于根据用户的命令按序遍历所述的部分排序的流概要数据结构，所得到的计数器值大于一阈值的条目为所要挖掘的带权值频繁项。

本发明的系统还包括对部分排序的流概要数据结构做剪枝操作的剪枝模块。

为进一步验证本发明方法和系统较现有研究工作在处理性能上的优势，做如下实验。

实验环境描述：数据集CERNET是于2007年在中国教育和科研计算机网(CERNET)的OC48骨干网链路上采集的，包含双向的TCP头部数据。数据集CAIDA-OC48和CAIDA-OC192分别是CAIDA组织于2002年和2008年在美国某ISP的OC48和OC192骨干网链路上采集的，包含匿名化处理之后的TCP和UDP数据。

实验计算机为英特尔至强4核服务器(主频2.00GHZ，内存4GB)，操作系统为CentOS 5.2Linux，编译器版本为g++4.1.2。

采用上述真实的骨干网数据进行对比实验，结果如图3所示。从图中可以看出，本发明提供的方法(在图中用WLC表示，Weighted LossyCounting)在图3(a)所示的CERNET测试数据集、图3(b)所示的CAIDA-OC48测试数据集和图3(c)所示的CAIDA-OC192测试数据集上的吞吐量(约7000Updates/ms)均显著高于Space Saving方法(约3000Updates/ms)和Lossy Counting方法(约200Updates/ms)。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同替换，都不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求范围当中。