胡文瑜等:数据挖掘取样方法研究47

进的算法转而判断一次可略过多少个后续元素,减少了扔骰子次数,降低了时间复杂度.水库取样是重要的随机均匀取样方法,使传统的取样技术拓展到了数据库领域,其时间复杂度仅为/(n(1+log(NPn))),空间大小固定,尤其适合于数据流挖掘环境.确保取样质量通常被认为是取样技术成功的关键(Levy[3]).从提高取样质量的角度,传统的取样策略一般可分为3类:第1类是ProgressiveSampling(渐进取样),办法是从一个小的取样开始,逐渐加大取样尺寸或取样率直到模型的正确性不再随之改善为止;第2类的取样策略是先从一个实验样本集(通常尺寸较小)中获取数据集的预评估或特征假定,然后在此基础上进行取样.采用这种策略的取样算法包括StratifiedSampling(分层取样[21]),ClusterSampling,Two-PhaseSampling

[22][4]

[4]

[15]

2.ConciseSampling(精确取样Gibbons[7])在水库取样方法中,样本集中各个元素单独占据一个位置,即使它们具有相同的数值,因而表达效率不高.精确取样方法作了改进.对于仅出现一次的元素,类似于水库取样,仍然用元素代码表示,而对于多次出现的元素,则利用结构òvalue,countó表示,value代表元素代码,count表示样本集中该元素的数目.精确取样算法维护一个初始值为1的概率参数T,各元素以概率1PT加入到样本集合中去.如果该元素已经存在于样本集中,则相应的计数器加1.否则,将该元素添加到样本集中去.一旦样本集溢出,改变参数T到Tc,Tc>T.样本集中的各个元素均以概率TPTc被删除,从而腾出空间以便存放新数据.精确取样方法通过逐步提高参数T的值,实现数据流上的均匀取样.对于存在有较多重复元素的数据分布情况,该方法比水库取样节约内存,或在同样的内存上界里能抽取更多的取样点.

3.CountingSampling(计数取样)

计数取样方法是精确取样方法的一个变种,二者的区别在于样本集溢出时如何处理.在计数取样算法中,当样本集溢出时,首先将参数T提高到Tc.对于其中的任意一个元素,都是首先以概率TPTc,之后以概率1PTc判断是否减去1.一旦该计数器值已经降为0,或者某一次随机判断之后计数器的值并没有减小,则结束对该元素的操作.

4.CongressionalSamples(国会取样)

应用背景是分组(group-by)近似查询,它在每个分组内进行独立的水库取样(类比为house议院选取),但不同组的取样率是不同的(类比为senate参议院选取),是均匀取样和偏倚取样的综合(故名为国会取样).其主要思想是综合考虑分组属性集中子集可能的组合情况,决定对各分组属性采用何种取样概率,目标是达到综合最佳的查询质量.总的来说,大组数据的取样率比小组数据的高,但又兼顾了小组数据的影响力和利益,克服了均匀取样的局限.

5.StratifiedSampling

利用数据分布的历史经验对数据分层,重要的层(如高方差层)被抽取更多的取样点,以提高评估的正确性,每层的取样方法仍然采用随机均匀取样法.实现的关键在于如何选择层数,如何分配所有的数据到各层中,如何在所有层中分配总值为k的取样点以致使方差最小化,获得偏差更小的查询处理和Adaptive

Sampling;第3类策略是为具体的应用抽取特定的数据特征,而不是产生一个能用于多种应用的取样集,这类应用包括频繁项E-误差概要(Manku[13])、近似查询(Gibbons[7,10])和查询尺寸评估(Haas[17]).数据流处理模型根据不同的时序范围可以划分成多种子模型,包括界标模型、滑动窗口模型和快照模型.界标模型的查询范围从某一个已知的初始时间点到当前时间点为止.滑动窗口模型仅关心数据流中最新的W个数据.快照模型则将操作限制在两个预定义的时间戳之间.滑动窗口模型不仅有新数据不断到达,而且旧数据会过期,如何处理过期数据并使得查询结果一直可靠是一个比界标模型更具挑战性的问题.

1.2 取样方法的分析与比较

1.2.1 代表性取样方法的分析与比较

表1是代表性取样方法的特性比较.此表分别从取样算法所属是均匀还是偏倚分类、性能特点、是否支持删除操作、是否保证误差确界、能否应用于数据流挖掘等方面进行比较分析.任何能采集和维护一个概要数据结构的单遍扫描算法均能用于数据流挖掘中.下面简要介绍几种代表性取样方法的算法思想.

1.APRSamplingAPRSampling的思想是:1)利用某种算法从数据集中随机均匀地抽取一个候选元素;2)如果这个候选元素满足选择条件就放入样本集(acceptance).否则拒绝(rejection),并重新开始1).算法被用于关系数据库B+树的随机取样,也用于空间数据库的[23]