50计算机研究与发展 2011,48(1)

如果数据的选择性(selectivity)很低时,基于均匀取样的近似查询处理结果会出现较大偏差.在流数据挖掘中,zipf[26]分布(高偏斜数据分布)反映了现实中存在的大量自然现象,如存在于对不同Web域进行存取的引用分布中.

空间中产生的含插入P删除操作的点序列数据流中动态维护一个取样集.文献[37]采用AdaptiveSampling方法进行无线传感网时序分析,能减少24%~49%的取样尺寸.

Chaudhuri等人为以前所提出的StratifiedSampling作了进一步的拓展研究.而用于网络流监测的文献[39]采用的是AdaptiveSampling和StratifiedSampling方法的综合运用.

Two-PhaseSampling的目的是节约取样成本.算法思想如下:计算对象集N的某目标值y的代价很高,但获取与y相关的辅助变量x的代价小.设yWtx.阶段1:从N中抽取一个尺寸相对较大的Sc,从Sc中获取x,x的分布和精确度较高的比率估值t^;阶段2:从Sc中再抽取子取样集S,取样过程利用了阶段1获取的信息,并最终获得精确度较高的

^.Chen等人利用Two目标估算值y-PhaseSampling策略来提高关联规则频繁项挖掘性能,提出了一个

用于大型数据库的FAST算法[40].阶段1:初始的大取样集用来快速地评估每个项目的支持度;阶段2:这些评估后的支持度或者用于裁剪离群事务或者用于从原取样集中选取更具代表性的事务,最终生成一个更小些的取样集,能更正确地反映原数据集的统计特性.Bronnimann等人[41-42]在FAST算法的基础上提出E近似取样算法EA和EASE,提高了取样正确性,且更适用于数据流模型的.而Hwang等人[43]也对FAST算法进行了改良.2.3 数据流管理和挖掘中的取样技术数据流中的取样技术反映在数据流管理数据流挖掘[45]两方面.

[44]

[38]

2 数据挖掘取样技术的应用与发展

取样方法在统计评估、数据挖掘、数据流处理和

[18]

机器学习中被普遍使用.具体应用包括生成概要数据结构、数据预处理[27]、数据流近似聚集查询、流数据分析与挖掘等,在知识发现领域中扮演着不可或缺的重要角色.2.1 成功案例

在数据挖掘中应用取样技术的成功案例包括:1)在商业统计与数据分析软件(如SAS,SPSS等)中均使用均匀抽样技术来处理大数据集;2)构建其他概要方法的基础方法,应用实例如BackingSample算法;3)数据挖掘算法中的应用:无论是划分聚类方法CURE还是层次聚类方法CLARANS都采用均匀抽样技术进行数据预处理,从而实现算法的可扩展性.Toivonen

[28]

和Li等人

[29]

也将取样技术应用

于关联规则频繁项挖掘和分类挖掘中以提高挖掘性能.

2.2 若干传统取样技术在数据挖掘领域的拓展

在统计学领域,ProgressiveSampling,AdaptiveSampling,StratifiedSampling和Two-PhaseSampling均是传统经典的取样技术.目前,这些技术在数据挖掘和数据流应用领域得到新的拓展.

文献[30-31]是ProgressiveSampling在关联规则挖掘的应用.文献[32]采用ProgressiveSampling框架在大型图形库中进行聚类挖掘.

传统的AdaptiveSampling是一种用来评估有穷非负整数数列和的通用方法.在数据挖掘领域,AdaptiveSampling方法的取样大小不是预先固定的,能自适应地调整取样大小,从而在可接受的误差界内用更小的取样尺寸就能解决问题.例如,Domingo等人的AdaptiveSampling算法是应对取样复杂性难题的一种解决方法,该方法以一种在线方式连续获得取样,并且从已经获得的取样中判断目前的取样元素是否足够,能自适应地调整取样尺寸,从而可能用比最糟情形下所需的尺寸更小的取样尺寸就能达到目标.文献[35]的应用背景是数[[34]

[33]

和

1)数据流处理模型中生成概要数据结构.应用实例包括水库取样、精确取样、计数取样和链式取样算法等.

2)数据流近似聚集查询.应用实例包括CongressionalSamples和DV-Sampling类算法.

3)流上挖掘频繁元素(frequentitems)和分位点(quantile)

¹在流上挖掘频繁元素:根据用户定义的门槛参数sI(0,1),输出在整个数据流中所占比重大于s的所有元素.很多应用需要用到这个信息,例如,冰山查询需要计算目标属性的聚集信息,获得超过预定门槛值的聚集值.在关联规则挖掘中,需要计算频繁项集,应用需求包括网络监测比例高于门槛值的IP包,防止DOS攻击等.应用实例包括Stick.