一种基于计数的数据流频繁项挖掘算法的改进

吴媚　高玲

摘 要：查找数据流中的频繁项是数据流挖掘中的热点问题之一。挖掘数据流频繁项在网络流量监测、金融服务等多个领域有着广泛的应用。本文首先概述经典算法Space Saving的思想并分析其性能，提出一种基于计数的改进算法维护样本集。实验表明，改进的算法能一定程度上提高准确率，避免对频繁项的错误判断。

关键词：数据挖掘；数据流；频繁项；频数统计

近年来，随着数据量以每天数以百万计甚至无上限的速度增长，如何在复杂的资料中获取有用的信息成为数据时代的我们所要面对的新考验。数据流挖掘作为数据挖掘的一个分支方向，其中的挖掘数据流频繁项作为热点问题，所研究领域所涉及的应用广泛，存在于商业金融，网络流量监控，入侵检测等多个方面。

数据流挖掘技术大致分为四类：聚类、分类、频数统计和时间序列分析。频数统计包括在单个或多个数据流上提取出现频率超过指定阈值的频繁项或者项集，是研究的重点。频数统计主要涉及：频繁项或频繁项集挖掘、Top-K数据项及数据项集挖掘等。本文在Space Saving算法基础上，提出维护两个样本集的思路以期挖掘出的Top-K频繁项集的结果能减少对数据项的错误判断并一定程度上提高算法的效率。

1 概述

1.1 基本定义

數据流DS为：随着时间到来的有序无限的数据项集合，表示成DS={a1，a2…an}，其中任何数据项ai都来源于集合{1，2，…，Z}，Z代表数据项的分布范围；fi代表数据项ai出现的频数；F=f1+f2+…+fn，F为到达的n个数据项的频数之和。

Top-K数据项的定义如下：时间t1-t2内对于所有数据项，按照它们出现的真实或估算频数排序，其中频数最高的K个数据项就是真实或估算的Top-K数据项，K为任意数值。由于挖掘算法仅保存数据流中部分的数据，数据分布又随时间变化，准确挖掘频繁项通常是不可能的，故文中涉及的算法都是基于抽样的近似算法，挖掘出的Top-K也为近似结果。

实验中我们参考其他文献用个数准确率、错误偏差率描述各个算法的优劣。个数准确率：算法挖掘出的Top-K数据项中属于真实数据项的个数之和与K的比率。错误偏差率：算法挖掘出的Top-K所有数据项的估算频数之和与这些数据项真实频数之和的比与标准单位1的绝对偏差率。

1.2 Space Saving算法描述

文献[1]认为Space Saving算法[2]是当前在数据流上做频繁项挖掘最好的算法。令t1到t2内每个经过的数据项形式为{（a1，1），（a2，1），…（an，1）}，样本集为S，统计频数的计数器为（ai，fi）。初始时，算法依次扫描到来的数据项，若ai存在在样本集S中，在其数据项对应的计数器上加1；若ai不在S中且样本集不满，将（ai，fi）加入到样本集S中；否则ai不在S中且S已满，首先做删除频数最小的数据项am的操作，后把fi+fm作为新数据项ai的初始频数插入到样本集S中。

分析算法可知若某数据项ai的频数超过F/S的值，则它必然出现在最后的缓冲区中，并且实验发现在数据分布较平缓时，SS算法估算数据项频率时也不够准确。

2 新算法描述

2.1 关键思想

针对SS算法若某数据项ai的频数超过数据项频率F/样本集S时，则它必然出现在最后的缓冲区中这一问题。在新算法内，增加一个样本集S2，即将样本集S分成S1和S2两个样本集来存储，判定阈值m即为F/S的值，若频数大于m则将对应数据项存入S2进行下一轮计数，当随着计数小于m时，则从S2将对应的数据退回到S1中。

2.2 改进算法

更新操作用来根据阈值更新并维护样本集内的数据，描述如下：

输入：数据流DS 输出：样本集S1，S2

⑴F=F+fi；m=F/S

⑵IF ai在S1中；ai对应的计数器fi ++

⑶IF fi

⑷ELSE ai保留在S1

⑸ELSE IF ai在S2中；ai对应的计数器fi ++

⑹IF fi>m将ai移入S1中，并删除S2中ai

⑺ELSE ai保留在S2

⑻ELSE IF S2不满；将加到S2中

⑼ELSE 选取S2中计数值fm最小的数据项am；将加入S2中；删除数据项am

⑽END

查询操作即是在维护的样本集中挖掘Top-k频繁项的具体结果，描述如下：

输入：样本集合S1、S2，K。输出：Top-k频繁项。

⑴合并样本集S1，S2为S

⑵遍历样本集S中数据项并按照频次从大到小排序

⑶输出所有Top-k频繁数据项。

3 实验对比分析

为了说明新算法在挖掘Top-k频繁项时体现的效率，我们选取与Lossy Counting[3]算法、SS算法以及Efficient Count[4]一同比较。算法均在Visual Studio 2010开发使用C++语言编写，实验在Intel Core i7 CPU、主频2.4G、内存8G的PC上运行。实现数据采用matlab随机生成的模拟数据，各算法的个数准确率、错误偏差率和运行时间结果如下所示：

分析上述实验结果，图1中一开始数据量较小的情况下，LC和SS算法准确率较高，随着数据量增大，四种算法的准确性都一定程度上下降，但LC和新算法的优势就凸显出来。图2中可以明显看出EC、SS算法的的错误偏差率很高，而新算法在能否准确的搜索频繁项方面优于LC和SS算法。综合考虑时空效率及实验结果，新算法在一定程度上能提高搜索频繁项的准确率。

4 结束语

数据流频繁项集挖掘是一个具有挑战性的问题，因数据流的特点，算法只能对数据进行一次扫描且存储空间有限。本文在挖掘数据流上的频繁项时，采用的模型仅考虑如何维护样本集中的数据项，这是基于计数方法的模型框架，还可以尝试其他的模型架构。本文在经典算法的基础上提出对样本集维护策略的改变。实验表明，改进的算法能一定程度上提高挖掘频繁项的准确率，减少对数据项的错误判断。

[参考文献]

[1]Liu H，Lin Y，Han J.Methods for mining frequent items in data streams：an overview[J].Knowledge and information systems，2011，26（1）：1-30.

[2]Metwally A，Agrawal D，El Abbadi A.Efficient computation of frequent and top-k elements in data streams[M].Database Theory-ICDT 2005.Springer Berlin Heidelberg，2005：398-412.

[3]Manku G S，Motwani R.Approximate frequency counts over data streams[C].Proceedings of the 28th international conference on Very Large Data Bases.VLDB Endowment，2002： 346-357.

[4]王伟平，李建中，张冬冬，等.一种有效的挖掘数据流近似频繁项算法 [J].软件学报，2007，18（4）：884-892.