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

机取样方法虽然正确率较低但构建速度更快,无需扫描整个数据集就能构建,且一个取样集就能应付任意目标属性值的DV值评估,而DV-Sampling要针对不同的目标属性值单独构建取样集,要求预先知道目标属性.如果需要维护较多的DV-Sampling集会加大更新成本.但同样的内存空间DV-Sampling可以维护的目标属性多,且正确率远超过简单随机取样法,查询响应时间也不慢.

8.Chain-Sampling(链式取样)

链式取样方法能够从滑动窗口上获得一个固定尺寸的随机均匀取样集.设窗口大小为W,则在任何时间点n,流中的元素以概率1Pmin(n,W)被添加到样本集合中去.当元素被选择到样本集合中去时,必须同时决定一个备选元素,当这个元素过期时,将利用备选元素代替该元素.由于在数据流中不能够预测将来的数据,因此,实际上仅从[n+1,n+W]中随机选取一个数作为备选元素的时间戳t.当到达时间点t时,这个备选元素才最终被确定.备选元素以后也会过期,因此也需要为它选择一个备选元素,方法同上.可以看出,样本集合中的任一元素均有一个备选元素的/链0,元素过期后马上用/链0上的下一个元素取代它.

9.StickSampling

StickSampling算法有3个用户指定的参数:支持度s、误差E和失效概率D.数据结构S是二元组(e,f)的集合,其中f为元素e在数据流中的估计频度计数.初始S为空,采样率r设为1.对元素以r进行采样意为以概率1Pr选中该元素.对于每个新到达的元素e,若e已经在S中存在,则增加相应的频度计数,否则对e以r进行采样.StickSampling像一块磁铁一样扫过数据流,不断吸收S中已存在的元素,因此而得名.采样率在数据流的生命期中不断变化.当采样率变化时,StickSampling对S中的各元组进行一次扫描并作如下更新:对每个元组(e,f),不断抛一枚密度均匀的硬币,直到硬币正面朝上为止,此时对f减1.若f在这一过程中被减为0,则从S中删除该元组.当查询到达时,StickSampling输出S中所有频度计数大于等于(s-E)N的元组.

StickSampling满足如下结论:能以至少1-D的概率计算出一个近似概要,其内存界为2PElog(s

-1

-1

支持度s和误差E.LossyCounting把到达的数据流从概念上划分为若干个长度为w=

-1PE的桶.各

-

桶有一个桶ID,桶ID从1开始.当前桶记为bcurrent,其ID为NPw.对任意一个元素e,它从流开始

到现在的实际频度记作fe.注意到E,w都是定值,而N,bcurrent和fe都是随着流的运行不断变化的量.算法的数据结构为三元组(e,f,$)的集合D,其中e为流中一个元素,f为估计的频度,$为f可能的最大误差.D初始为空,每当有一个新元素e到达时,若D中已存在包含e的元组,则对该元组的f加1,否则创建一个新的元组(e,1,bcurrent-1).每当到达桶边界时,即对D中的元组进行修剪.修剪规则如下:若某元组(e,f,$)的f+$[bcurrent,则删除该元组.当查询到达时,输出D中所有f\(s-E)N的元组.

LossyCounting满足如下结论:1)若元素e不出现在D中,则fe[EN;2)若(e,f,$)ID,则f[fe[f+EN;3)LossyCounting维护一个E误差的概要,其内存界为1PE(log(EN)).1.2.2 偏倚取样与均匀取样

数据挖掘中偏倚取样的产生是由于均匀取样有其局限性.均匀随机取样适用于数据呈均匀概率分布的情形,尤其是数据对用户的作用主要取决于取样能否反映数据分布情况的场合.因此,当数据对用户的用处主要与数据的尺寸更相关时,查询的准确性就不足了.占小比例的数据虽然代表性不够,但有时对用户来说其重要性一点不输于占大比例的数据.相反的情形是不同逻辑部分的数据有相等的代表性,但它们对用户的作用却是偏斜的.例如,在大多数数据仓库中,数据的有用性是随时间递减的.比如在DV查询中,如果采用简单随机取样从关系表中均匀取样行,将可能遗漏关系表中稀少出现的属性值.Babcock等人[19]指出:对于许多查询,适当地构造偏倚取样能比均匀取样提供更准确的近似,并具体提出了一个通过动态构造偏倚取样并结合预处理阶段已经构造的一些非均匀取样进行近似查询处理的方法,能获得更准确的近似处理结果.Palmer等人[24]指出了基于密度的偏倚取样(densitybiasedsampling)方法对于提高基于取样的数据挖掘算法精度的重要作用.Kollios等人[25]的研究结论是:当数据分布是严重偏斜时,密度偏倚取样作为聚类方法的预处理或一种数据约减技术,能加速多维大数据集中聚类和离群检测等挖掘任务的执行并解决取.D).由于该内存界与数据流的长度无关,因而具有

较低的理论空间复杂度.

10.LossyCounting

: