流数据上的频繁项挖掘算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇流数据上的频繁项挖掘算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：
提出了一种流数据上的频繁项挖掘算法（SWCOUNT）。该算法通过数据采样技术挖掘滑动窗口下的数据流频繁项。给定的误差Е牛SWCOUNT可以在O(ε-1)空间复杂度下，检测误差在εn内的数据流频繁项，对每个数据项的平均处理时间为O(1)。大量的实验证明，该算法比其他类似算法具有较好的精度质量以及时间和空间效率。
ス丶词：
数据流；频繁项；滑动窗口；采样技术；数据挖掘
ブ型挤掷嗪牛TP301.6
文献标志码：A
英文标题
Mining frequent items on stream data
び⑽淖髡呙
TU Li1, CHEN Ling2,3
び⑽牡刂(
1. Department of Computer Science, Jiangyin Polytechnic Institute, Jiangyin Jiangsu 214405, China;
2. Department of Computer Science, Yangzhou University, Yangzhou Jiangsu 225009, China;
3. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing Jiangsu 210093, China
英文摘要
)
Abstract:
A frequent items mining algorithm of stream data (SWCOUNT) was proposed, which used data sampling technique to mine frequent items of data flow under sliding windows. Given an error threshold ε, SWCOUNT can detect εapproximate frequent items of a data stream using O(ε-1) memory space and the processing time for each data item was O(1). A lot of experiments show that SWCOUNT outperforms other methods in terms of the accuracy, memory requirement, and time and space efficiency.
英文关键词
Key words:
data stream; frequent item; sliding window; sampling technology; data mining
0 引言
随着计算机技术的快速发展,数据流广泛出现在众多应用领域。例如, Web服务器上的用户点击记录流、互联网中传递的IP数据包、电信公司的通话记录、传感器网络中的监测信号、股票价格波动的数据等。与传统的数据库不同, 数据流产生的数据无法全部保存在内存中, 并且数据流上的查询具有很强的实时性要求。因此对在线数据分析和挖掘提出了新的挑战。数据流上的频繁项挖掘已经成为数据挖掘领域中的一个研究热点。
Manku等人［1］提出了Lossy Counting算法挖掘数据流中的频繁项，许多频繁项的挖掘算法使用随机样本。Flajolet和Martin［2］提出了概率算法通过一次扫描来估算大型数据集中不同项的数目。Gibbons和Matias［3］提出了一个抽样算法来解决topk查询。Liu等人［4］提出了误差自适应和给定时间的数据流频繁值计算的维护算法，许多算法使用哈希技术将数据流中的数据项映射到可以存放在主存的哈希表。Estan和Varghese［5］提出了基于哈希计数的采样算法来检测频繁项。Jin等人［6］提出了hCount算法，需要O(ε-1log(-M/log Е莫))内存空间以及每个数据项O(log (-M/log Е莫))的时间代价。算法可以在1-Е牡母怕氏拢检测到ε步似的结果。Lin等人［7］提出了一种自适应的频度计算算法来处理数据流中突发数据。使用一种反馈机制，动态调整挖掘速度，以应付不断变化的到达率。王伟平等人［8］提出了一个算法挖掘数据流中ε近似频繁项，动态地维护1/ε个样本，其空间复杂度为O(ε-1)，平均每个数据项的处理时间为O(1)。此外，算法返回的结果频率误差界限为ε(1-s+ε)N，通过滑动窗口技术发现频繁项［9-11］。Lee和Ting［11］ 提出了一种算法，实现空间复杂度为O(ε-1)，而更新和查询的处理时间为O(ε-1)。此外，同时也出现了一些流数据上的频繁项集挖掘算法［12-14 ］。
实际应用中,人们往往比较关心最近一段时间内数据流中的频繁项。滑动窗口技术能够针对数据流上当前窗口内的数据进行挖掘,不会受到以前挖掘结果的影响。提出了一种基于滑动窗口的流数据频繁项挖掘算法(Sliding WindowCOUNT, SWCOUNT)算法，可以对于给定的允许误差区间ε，检测数据流中ε步似频繁项，而对数据流中的频繁项分布不作任何假设。算法采用了采样技术以及双向链表队列来处理并存储数据项，可以在O(ε-1)空间复杂度下，实现处理每个数据项的平均时间复杂度为O(1)。
1 基本概念和相关术语
定义1 滑动窗口和Е霜Э椤
假设xi表示数据流S在时间点i上的取值，用［i: j］表流数据的子序列xi,xi+1,…,xj(i
定义2 λ取样。
设有流数据S={x1,x2,x3,…}，数据项集合I，对于某一数据项x∈I，若其中依次有x1′,x2′,x3′,…的关键字等于x，设定一个正整数λ是λ块的宽度，称xλ′,x2λ′,x3λ′,…为x的λ取样，在相邻两个λ取样之间有λ－1个x值。
定义3 取样块。
对于数据项x∈I，如果λ块Wb在滑动窗口Wp中，满足：1）Wb与Wp有重叠部分,2）Wb中有一个对于x的λ取样，则称Wb在滑动窗口Wp中是x的取样块。
定义4 快照。
对于数据项x1∈I，它在Wp中的λ快照Sx1p用一个二元组(Q(x1),l(x1))表示，其中Q(x1)为Wp中x1的取样块集合，l(x1)是Wp中最后一个x1的λ取样后的x1的个数，由于这些取值数的数据个数不足一个λ块，显然有l(x1)
如表1所示，窗口W19中数据项x1的快照Sx119=(Q(x1),l(x1))=(〈1,2,4〉,3)，x2的快照Sx219=(Q(x2),l(x2))=(〈5〉,0)；窗口W20中数据项x1的快照Sx120=(Q(x1),l(x1))=(〈2,4,5〉,0)，x2的快照Sx220=(Q,l)=(〈5〉,0)。它们的取值分别为vx1,19=15, vx2,19=4, vx1,20=12, vx2,20=4。
图片
2 流数据上的频繁项挖掘算法SWCOUNT
2.1 SWCOUNT算法框架
定义5 SWCOUNT算法中的特征向量。
数据项x的特征向量是一个三元组C(x)=［x, Q(x), l(x)］，其中：Q(x)是数据项x在当前窗口Wp下的取样块集合队列，l(x)是Wp中最后一个λ取样后的x的个数。
SWCOUNT算法依次处理数据流中到来的数据，它使用一个数据表D来保存候选频繁数据项。为了减少D表对内存空间的使用，算法动态更新其中的数据。D中的每个条目就是一个候选频繁数据项x的特征向量C(x)=［x, Q(x), l(x)］。D是一个队列结构，其最大长度为L=2/ε。D表中的条目根据它们特征向量中的Q(x)值升序排列。Q(x)值最小的条目被放在队头，而Q(x)值最大的条目则会沉到队尾。当算法从数据流中接收到一个新的数据项x时，算法检查D表中的条目是否存在x的条目，如果D中不存在x的特征向量，且D不满，算法会为x创建一个新的条目并把它插入到D的队头。一旦D的长度超过L时，位于D的队头的条目将会被删去，且更新其他条目。如果D中已经存在x的特征向量，算法会更新它的Q(x)和l(x)值，然后把它与下一个元素y比较，如果快照值v(Sxp)大于v(Syp)，则将条目x和y交换，即频繁值大的下沉。 オ
SWCOUNT算法。
输入：数据流S。
输出：D，频繁数据项集合。
程序前
begin
1
t=0，D=null，curr_λblock=1；
2
while 数据流未停止 do
3
从数据流中接收到一个新数据项x； お
4
t=t+1；
5
if (t mod Е霜)==0 then
6
curr_λblock ++；
7
if 集合Q(x)Ф恿兄械亩油啡块过期 then 删除队头；
8
end if
9
if D中没有与x相关的条目 then
10
创建一个新条目 ［x, 〈null〉, 1］；
11
if D满了 then
12
删除D的队头条目C(x1)В
13
其他条目C(xi)的快照值减掉C(x1)У目煺罩担空的删除；
14
end if
15
将新条目插入到DУ亩油罚
16
else
17
l(x)=(l(x)+1) mod Е耍华お
18
if l(x)==0 then
19
将相关条目［x, Q(x),l(x)В萏婊怀桑郦x, Q(x)+{curr_λblock},l(x)В荩
20
end if
21
if (Q(x)>Q(y))或(Q(x)=Q(y) and
l(x)>l(y)) then
22
将C(x)与C(y)Ы换唬//y是D中xУ南乱桓鲈素
23
end if
24
end if
25
end while
end
引理1 设Sxp=(Q(x),l(x))为数据项x在Wp中的λ快照，快照值v(Sxp)=λQ(x)+l(x)。设在Wp下 x的真实个数为NRxp，那么快照值和真实值之间误差NRxp≤v(Sxp)≤NRxp+λ。
证明 如果Q(x)=0，则v(Sxp)=l=NRxp≤NRxp+λ；如果Q(x)=1，若该取样块不完全在Wp中，设其中有λ1在Wp之外，有λ2在Wp之内，则有λ1+λ2=λ， λ2+l=NRxp。此时v(Sxp)=λ+l=λ1+λ2+l=λ1+NRxp≤NRxp+λ；若该取样块完全在Wp中，即λ1=0，此时v(Sxp)=NRxp≤NRxp+λ；如果Q(x)>1，设最早的取样块为Wb1，该取样块中有λ1在Wp之外，有λ2在Wp之内，则有λ1+λ2=λ，v(Sxp)=λ1+λ2+(Q(x)－1)λ+l=λ1+NRxp≤NRxp+λ。证毕。
┑2期
屠莉等：流数据上的频繁项挖掘算法
┆扑慊应用 ┑31卷
引理2 算法在数据表D中所保存的数据项为在Wp中最频繁的2/ε个数据项。
证明 反证法。假设引理2不成立，数据项x和y在Wp中的真实频繁值满足NRxp>NRyp，但是数据项x不在表中，而y在表中。当NRxp个x数据项到达时，全部进行“减值”操作（因为x不在表中），即y数据项要被减去NRxp；但由于NRxp>NRyp，因而y数据项也不可能出现在表中，所以假设不成立，因此，表中所列出的必是Wp中最频繁的2/ε个数据项。证毕。
2.2 数据结构D
在每个时间步，算法处理到来的数据，并更新统计结构D。D中每个条目就是一个数据项的特征向量C(x)=［x, Q(x), l(x)］。Q(x)为Wp中x的取样块集合队列，按照取样块号的升序排列；l∈［0,λ－1］；D的最大长度L=2/ε。为了加速更新D的处理，利用一个哈希函数H(x)将D存储在一个哈希表中。即对于数据项x，它的地址是H(x)；同时，D中的条目按照值Q的大小升序存放在一个队列结构中，队列由一个双向链表构成，如图1所示。
图片
图1
数据结构Dオ
在此数据结构下，算法SWCOUNT中对表D的一些操作的具体实现如下。オ
1）第12行，删除一个条目：总是删除队列的头元素。
2）第15行，插入一个条目：总是将条目插入队头。
3）第22行，将条目与下一个条目交换，这个操作可由以下3个操作代替：
① 将该条目保存到缓冲区；
② 将下一个条目上移一个；
③ 将保存于缓冲区中的该条目插入到下一个条目位置。
2.3查询算法
Query(Wp) 算法オ
输入：Wp窗口下数据表D中数据项集合I(Wp)。
输出：ε步似频繁项集F。
程序前
begin
F=И;
for 所有x∈I(Wp) do
if v(Sxp)－λ≥(s－ε)n then F=F∪{x}
end for
输出F
end
程序后
2.4 算法分析
SWCOUNT算法的空间复杂度由数据表D决定，在算法中，D最大长度为2/ε，即最多可以存储2/ε个数据项，因此算法的内存空间不超过O(ε-1)。而在每一个时间步，算法处理一个数据项的操作有：通过哈希表定位数据项，可以在O(1)时间内完成；插入一个新的数据项；修改并移动一个数据项，删除一个数据项，都可以在O(1)时间内执行。因此，算法处理每个数据项的时间复杂度为O(1)。D队列链表的最大长度为L=2/ε，显然，响应每个查询的计算时间为O(ε-1)，而查询每个数据项频繁值的时间则为O(1)。オ
3 实验结果与分析
为了验证算法的性能，通过大量实验，将算法SWCOUNT与文献［8］中的EC算法、文献［11］中的算法（设称为Lee & Ting）进行了比较。所有的实验在内存为512@MB、CPU 1.7@GHz的PC上运行，运行的操作系统为Windows XP，使用VC++6.0编程。在实验中，设定Е=0.1S, S=0.01。实验数据是用多篇文章中采用的gzipf数据产生器所产生的具有不同的Zipf参数（0.4，0.6，0.8，1）的数据集,数据集的大小为100B000~1B000B000,重点比较了算法计算时间、内存需求以及处理结果的精度。
3.1 理论分析
表2列出了3种算法的各项指标的比较。EC算法没有强调近期数据的重要性，是对整个数据流上的数据项进行累计挖掘。而Lee & Ting算法[11]和本文算法都采用了滑动窗口技术来强调近期数据，是对数据流中滑动窗口内的数据项进行频繁挖掘，这在现实生活中有更为广泛的应用。这两类算法在实际中有不同的应用范围。由表2可以看出，3种算法都是确定Е弄步似频繁项挖掘算法，且空间复杂度均为O(ε-1)，只和误差阈值εв泄兀坏由于各自算法所采用的保留数据项列表长度和存储单元的不同，在实际挖掘过程中所消耗的存储空间也会有所不同。EC算法和SWCOUNT算法的处理每个数据项的时间复杂度均为O(1)，ФLee & Ting算法则是O(ε-1)，显然EC算法和SWCOUNT算法的处理速度要更快一些。因此，本文算法在强调近期数据的基础上，与其他两种算法相比，时空复杂度都可以达到相对最优。
表2 3种算法的各项指标比较
算法频繁度或
密度界限随机せ蛉范空间じ丛佣让肯畲Κだ硎奔淝康鹘期な据(方法)
EC［8］Е(1-s+ε)N确定O(ε-1)O(1)Х
Lee & Ting［11］ЕN确定O(ε-1)O(ε-1)是(滑动窗口)
SWCOUNTЕN确定O(ε-1)O(1)是(滑动窗口)
3.2 性能分析
下面通过各项实验来比较3种算法的各项性能，并验证以上的理论分析。
首先，对3种算法的空间性能做了测试，图2显示了SWCOUNT和EC算法、Lee & Ting算法在各长度数据集上运行所消耗的空间性能比较。从图2中可以看出随着数据集的增加，3种算法的空间开销基本保持不变，这是因为3种算法的空间复杂度都是O(ε-1)。然而，由于SWCOUNT和EC算法、Lee & Ting算法所保留的数据项列表的长度分别是2/εА1/εА8/εВ因此，处理相同的数据，Lee & Ting算法所需的内存空间最高。随着数据集从100B000增加到1B000B000，SWCOUNT算法和EC算法所消耗的空间代价都不超过0.1@MB。
图片
图2
SWCOUNT和EC、Lee & Ting算法的空间性能
图3比较了3种算法的时间性能。由图3可以看出随着数据集的增加，Lee&Ting算法所需的时间开销呈线性增加。而SWCOUNT算法和EC算法所需的时间比Lee & Ting算法要少得多，增加的幅度也要小得多。当数据集从100B000增加到1B000B000，EC算法所用的时间是从0.82Bs增加到7.89@s；而SWCOUNT算法所用时间只是从0.35@s增加到3.45@s，具有最好的时间性能。这是因为SWCOUNT算法和EC算法处理每个数据项的平均时间代价为O(1)，ФLee & Ting算法则需要O(ε-1)。オ
图4、5比较了3种算法的精度。图4列出了3种算法在不同规模数据集上的精度比较，在给定支持度S=0.01У那榭鱿拢3种算法在处理不同长度的数据集的精度都在99%以上，甚至可以达到100%，说明3种算法的准确率都很高。由图5可以看出，随着zipf参数从0.4增加到1，3种算法的正确率也会随之增高逐渐接近到100%，随着zipf 参数的增大，数据集的偏斜度也增大，因而3种算法的误差变小，正确率变大。实验结果与理论分析的结果是一致的。而SW_COUNT算法和EC算法的精度则要略高于Lee & Ting算法。
图片
图3
SWCOUNT和EC、Lee & Ting算法的时间性能
图片
图4
SWCOUNT和EC、Lee & Ting算法在不同规模数据集上的精度
图片
图5
SWCOUNT和EC、Lee & Ting算法在不同zipf参数上的精度
4 结语
提出了一种有效的流数据频繁项挖掘算法――SWCOUNT。算法在给定阈值下计算滑动窗口中的数据流上的频繁值。采用了数据项采样技术，并使用了双向链表队列D存储数据项的快照，可以在O(ε-1)空间复杂度下，检测确定误差在εn内的数据流频繁项，对每个数据项的平均处理时间达到O(1)。通过实验证明，算法在时空效率以及精度方面都有较好的性能。 オ
参考文献:
[1]
MANKU G S, MOTWANI R. Approximate frequency counts overdata streams［C］// Proceedings of 28th International Conference on Very Large Data Bases. Hong Kong:Morgan Kaufmann, 2002:346-357.
［2］
FLAJOLET P, MARTIN G N. Probabilistic counting algorithms for data base applications［J］. Journal of Computer and System Sciences, 1985, 31(2):182-209.
［3］
GIBBONS P B, MATIAS Y. New samplingbased summary statistics for improving approximate query answers［C］// Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1998: 331-342.
［4］
LIU HONGYAN, LU YING, HAN J W, et al.Erroradaptive and timeaware maintenance of frequency counts over data streams［C］// Proceedings of WAIN 2006, LNCS 4016. Berlin: SpringerVerlag, 2006: 484-495.
［5］
ESTAN C, VARGHESE G. New directions in traffic measurement and accounting: focusing on the elephants, ignoring the mice［J］. ACM Transactions on Computer System, 2003, 21(3):270-313.