数据挖掘取样方法研究_胡文瑜

计算机研究与发展

ISSN1000-1239PCN11-1777PTP

数据挖掘取样方法研究

胡文瑜

123

1,2

孙志挥 吴英杰

11,3

(东南大学计算机科学与工程学院 南京 210096)(福建工程学院计算机与信息科学系 福州 350108)(福州大学数学与计算机科学学院 福州 350108)(huwenyu@)

StudyofSamplingMethodsonDataMiningandStreamMining

HuWenyu1,2,SunZhihui1,WuYingjie1,3

123

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing210096)

(DepartmentofComputerandInformationScience,FujianUniversityofTechnology,Fuzhou350108)(CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350108)

Abstract Samplingisanefficientandmostwidely-usedapproximationtechnique.Itenableslotsof

algorithmstobeappliedtohugedatasetbyuseofscalingdowndramaticallydatasetfordataminingandstreamingmining.Throughoutthedetailedreview,akindoftaxonomicframeofsamplingalgorithmsbasedonuniformsamplingandbiasedsamplingispresented;meanwhile,analysis,comparisonsandevaluationsofrepresentativesamplingalgorithmssuchasreservoirsampling,concisesampling,countsampling,chain-sampling,DVsamplingandsoonareperformed.Duetothelimitationsofuniformsamplinginsomeapplications)querieswithrelativelylowselectivity,outlierdetectioninlargemultidimensionaldatasets,andclusteringoverdatastreamswithskewedZipfdistribution,theimportanceofneedforusingbiasedsamplingmethodsinthesescenariosisfullydissertated.Inadditiontolistingsuccessfulapplicationsofsamplingtechniquesindatamining,statisticsestimatingandstreammininguptonow,wesurveytheapplicationanddevelopmentofsamplingtechniques,especiallythosetraditionalclassicsamplingtechniquessuchasprogressivesampling,adaptivesampling,stratifiedsamplingandtwo-phasesamplingetc.Finally,futurechallengesanddirectionswithrespecttodatastreamsamplingarefurtherdiscussed.

Keywords datamining;uniformsampling;biasedsampling;datastream;synopsisdatastructure

摘 要

取样是一种通用有效的近似技术.在数据挖掘研究中,取样方法可显著减小所处理数据集的规

模,使得众多数据挖掘算法得以应用到大规模数据集以及数据流数据上.通过对应用于数据挖掘领域的代表性取样方法的比较研究和分析总结,提出了一个取样算法分类框架.在指出了均匀取样局限性的基础上阐述了某些应用场景中选用偏倚取样方法的必要性,综述了取样技术在数据挖掘领域的应用研究与应用发展,最后对数据流挖掘取样方法面临的挑战和发展方向进行了展望.

关键词

数据挖掘;均匀取样;偏倚取样;数据流;概要数据结构

中图法分类号 TP311.13;TP391

收稿日期:2009-12-15;修回日期:2010-05-24

(;(

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

近几十年来,随着数据库技术迅速发展和广泛应用,数据库中存储的数据量急剧增大.在数据挖掘领域中,除了研究时空有效性不断提高的挖掘算法外,还必须采取相应的技术方法降低所处理的数据规模.特别是近年来数据流广泛出现在众多领域,例如网络监测、通信数据管理、Web应用、金融服务等,这些数据流以极大量、快速、时变的形式持续到达,要求单遍扫描,且一经处理不能被再次提取或者再次提取代价昂贵.由此产生了一些基础性的新研究问题,如概要数据结构的设计和动态维护、数据流挖掘取样技术研究等.

取样是最通用有效的近似技术,以其在处理大规模数据集中表现出的良好性能而得到了广泛深入的研究[1-17].在保证一定精确度的前提下,取样方法显著减小了所处理数据集的规模,使得众多数据挖掘算法得以应用到大数据集以及数据流数据上.目前数据流挖掘技术的研究核心是概要结构设计,常用的概要结构设计方法有Hash方法、直方图方法、取样方法和小波方法等.由于取样方法良好的伸缩性和灵活性使其成为构建数据流概要的一个非常重要的方法

.

年从VLDB,SIGKDD,SIGMOD和ICDE中出现的论文[14,18-20]均采用了取样技术,验证了取样技术应用的流行.

1.1 取样方法的分类

图1是数据挖掘领域中代表性取样方法的分类图.

根据各数据项被选中的概率是否相同,取样方法可以分成均匀取样和偏倚取样两种.顾名思义,在均匀取样中各数据项以相同的概率被选中,而在偏倚取样中,不同元素的入选概率可能不同.

一个取样设计被称为均匀取样设计,如果在这个取样设计内由数据集D产生的任一取样集S的概率为 (S;D),当S,ScAD,|S|=|Sc|时,会满足 (S;D)= (Sc;D).也就是说,所有相同尺寸的取样能以相同的取样概率产生并且是相互雷同的.均匀取样方法有两种经典的取样设计:伯努利取样(Bernoullisampling)[3,21]和水库取样(reservoirsampling)

[1]

,它们是所有其他取样方法的基础.

在Bernoulli取样设计过程中,用概率qI(0,1]包含每个到达的数据元素,用概率1-q独立排除其他的数据元素.在这类Bernoulli设计中的相关取样概率为 (S;D)=q|S|(1-q)|D|-|S|,可见伯努利取样是均匀的,其主要优点是取样过程简单和时间成本低.

水库取样单遍扫描数据集,生成均匀取样集.令样本集大小为K,当第n个元素到达时(n>K),数据流中的元素都以KPn的概率被选取.如果样本集大小超出K,则从中随机去除一个样本,各元素的入选概率相同.Vitter[1]推荐了一个技巧来提高算法效率.在原算法中,对于流中的每个元素都需要/扔骰子0,判断该元素是否以KPn概率被选中,改

1 数据挖掘取样方法

抽样是一种经典的统计技术,已被研究了过百年的历史,尤其是随机抽样技术,已有许多基本原理(诸如中心极限定理、Chernoff、Hoeffding和Chebyshev界等[2-3])描述了随机抽样的有效性.在数据管理领域,取样通过抽取能捕捉数据基本特征的小部分数据子集来代表总数据集,并根据该样本集获得近似查询结果,或基于该样本集进行数据挖掘等工作.近

Fig.1 Classificationofrepresentativesamplingmethodsondataming.

图

胡文瑜等:数据挖掘取样方法研究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]

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

6.WeightedSampling(加权取样)

在近似聚集查询处理中,当聚集属性的分布是偏斜的(skewed)以及低选择性时,加权取样能克服

均匀取样的局限性.加权取样是带权值的偏倚取样方法,使用率高的小数据集中的元组权重更大.权值的获得需借助工作负载信息.

Table1 ComparisonandCharacterizationofRepresentativeSamplingMethods

表1 代表性取样方法特性比较

RefYear[1]1985

Whether

AlgorithmsReservoirSampling

K

UniformBiasedK

Characteristics

One-passalgorithm.Itworkswellwhentheincomingdatacontainsonlyinsertsandupdatesbutrunsintodifficultiesifthedatacontainsdeletions.

BasedonBernoulliSchemes,itcanbeusedtoconstructweightedsamples.

Yes

Yes

SupportDeletionNo

WhethertheErrorBoundedYes

UsedtoStreamModel?Yes

[5]1989[6]1995[7]1998[7]1998[8]2000

APRSampling

ConciseSamplingCountSamplingCongressionalSamples

K

K

K

K

Theconcisesamplinghasloweroverheadsbutthecountsamplingismoreaccurate.Bothconciseandcountingsamplesprovidemoreaccurateestimationsforthesamefootprintthanreservoirsamples.Theirapplicationbackgroundishotlistqueries.

Overcomethelimitationsofuniformsamplingwhichleadstopooraccuracyofgroup-byqueriesforgroupswithveryfewdataitems.

No Few No

Yes No Yes

Yes Yes Yes

[21]2001[9]2001[10]2001[11]2002

StratifiedSamplingWeightedSamplingDVSamplingBackingSample

KKK

AkindoftechniqueofapproximatequeryprocessingapplicabletotraditionalDB.

Beingabletoextendthisideaevenfurthertostreamqueryprocessing.

Caneasilybedeployedforstreamanalysisorstreamminingininversedistributionsondatastreams.Fortheuseofincrementalmaintenanceofapproximatehistograms.Thebackingsampleresideonthediskandisaccessedveryrarely.

Thesamplecanptdirectlyhandlearbitrarysequenceofinsertionsanddeletions.

Randomizedalgorithm,miningfrequentitemsoverstream.

Deterministicalgorithm.

Thisalgorithmperforms

No

No

KK

FewYesYes

FewYes

[12]2002[13]2002[13]2002

Chain-SamplingStickSamplingLossyCounting

KKK

FewYes

NoYesYes

NoYesYes

betterthanStickySamplinginpracticealthough

theoretically,itsworst-casespacecomplexityisworse.

K

ADV-samplingalgorithmwhichcanhandlearbitrarysequenceofinsertionsanddeletions.

Yes

Yes

[14]2005DynamicInverseSampling

7.DistinctSampling(DV-sampling)

一类能对流查询中的唯一值(distinctvalue)进行聚集的取样技术的统称.Gibbons等人在单遍扫描中对数据中的DV值进行取样,与其他取样方法相比,DV-Sampling不容易遗漏关系表中稀少出现的属性值,在一定情况下,能更正确地评估唯一值

[11]

的数目并增量维护对数据的插入和删除.此外,一个已构建并存储好的DV-Sampling能被用于正确评估范围查询中唯一值的数目,或者用于带谓词查询

的唯一值数目估计.取样是基于掷硬币的随机过程,使用Hash函数来映射项目值所属级别,达到一定级别的元组才被取样.相较于DV-Sampling,简单随

胡文瑜等:数据挖掘取样方法研究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

:

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.

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

-2-1

样且只需Elog(D)内存,其用于滑动窗口模型的算法是基于变异的链式取样方法.

º在流上挖掘分位点:令集合大小为N,参数<I(0,1),分位点元素就是数据集排序之后第<N位置的元素.分位点是数据集合的一个重要统计量.获得分位点有助于优化查询计划,提高数据库系统的性能.流上挖掘分位点的应用实例见Manku

-1

2

[46]

3 取样算法面临的挑战和研究展望

通过研究可以发现,传统取样技术在数据挖掘领域得到了深远的发展,有了新的内涵和生命力.取样技术在数据库的查询优化和近似处理、数据挖掘算法的数据预处理、流频繁元素挖掘和流分位点挖掘等方面的研究是比较充分和成熟的,但是取样技术的研究空间和研究挑战性仍然很大,尤其体现在数据流管理领域,具体包括:1)如何在尽可能小的样本集上获取尽可能精确的结果,即在一定的空间局限下和一定的精确性要求下,如何确定合适的样本大小(也称为取样复杂性问题);2)相对而言,适用于界标模型的取样技术比较成熟,而应用于滑动窗口模型的取样技术近年来虽有不少研究,但存在着内存上界不确定、附加成本较高和滑动窗口较小等诸多限制;3)目前的算法大多局限于处理只插入或少量删除的情形,需要进一步研究能处理带任意顺序的插入和删除操作或存在频繁增删情况的数据取样问题,这也是数据流概要动态维护问题;4)目前一些诸如IP流量监测这样的应用依靠或取决于逆向分布挖掘技术的发展,研究能在数据流中进行动态逆向取样和概要维护的算法也是有待充分研究的一个分支方向;5)当数据分布是严重偏斜或流查询中选择性很低时,将均匀取样方法应用于流聚类或流聚集查询中会出现不良结果,解决的办法是偏倚取样,如何设计好的偏倚取样算法,尤其是基于密度的偏倚取样算法仍是未来的研究方向之一.

文献[55]的数据流特征保持取样法和文献[56]的关联规则挖掘取样误差量化模型和快速估计算法是对问题1)的研究成果.文献[57]是问题2)的突破,能将一些原先无法用于滑动窗口模型的取样技

-53]术[52拓展到滑动窗口模型.文献[14,36]对3)的问题均有研究,但文献[36]应用背景局限于空间几

,空

间需求是O(Elog(EN)),能保证误差范围,但不支持删除操作.

4)数据流偏倚取样技术的应用

Palmer等人提出了保持原数据密度的加权偏倚取样方法,单遍扫描数据集能用于流数据聚类,与CongressSampling方法相反,它是组越小取样率越高,确保不会漏失小的聚类,适合于离群点分析.但其采用的输入点与组尺寸的映射方法是Hash方法,Hash冲突有可能降低取样质量,另外一个缺点是不能有效区分噪声和小尺寸聚类.文献[47]是基于偏倚取样算法的流挖掘频繁元素应用,空间需

-1

求是O(E),能保证误差范围,但不支持删除操作.文献[48]的偏倚取样方法可应用于演化数据流的查询评估和分类中,采取在水库取样的基础上添加时间偏倚函数来提高动态概要结构的时间相关性.文献[49]在高维数据流的在线相关性分析中利用了偏倚取样技术.

2.4 取样方法在数据挖掘中的应用发展

目前,不断创新的取样技术在数据挖掘领域的新应用持续呈现.Brown等人[20]提出的均匀取样算法是一个能并行处理经划分后的数据流并最终进行取样合并的近似查询算法.该算法不能处理带任意顺序的插入和删除.Jermaine等人[50]讨论了在线维护基于磁盘存储的随机取样方法,提出了一种样本文件存储方式,克服了无法在内存中维护大尺寸取样集的局限,并着重于解决高效存储、读取问题,可操作性强.Dash等人[51]提出了一个适用于大数据集和含噪声数据环境的单遍扫描算法,类似于StickSampling和LossyCounting算法,但应用范围可扩展到关联规则挖掘、分类和聚类,算法不足之处在于要求数据离散格式化.

取样技术的拓展应用包括在数据流环境中处理图形问题.任意顺序的流元素代表了图形的边,常见的问题有图形流中三角形数的评估.文献[52]是这类应用的代表.

近来,熵对网络监测应用的重要性得到了认识[53].网络流量分布熵的计算可用于网络流量的聚类、分类和异常侦测,Chakrabarti等人[54]提出了一[24]

何数据流,且空间有效性偏低,计算成本大,降低了

实用性.文献[10]对4)作了研究并提出了一种在逆向分布数据流中进行动态逆向取样的方法.文献[58]的流挖掘取样算法能应对在进化数据集中增量维护有界均匀取样集的挑战,无需昂贵的基数据存取,解决了3)4)的问题.但应该看出,应对这些挑战的研究不够充分和成熟,应用领域局限,留下了研究空间.人们期待更多新的取样技术能作出更多的突.

52

[16]

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

JinCheqing,QianWeining,ZhouAoying.Analysisandmanagementofstreamingdata:Asurvey[J].JournalofSoftware,2004,15(8):1172-1181(inChinese)

参

[1]

考文献

VitterJS.Randomsamplingwithareservoir[J].ACMTransonMathematicalSoftware,1985,11(1):37-57

[17]

(金澈清,钱卫宁,周傲英.流数据分析与管理综述[J].软件学报,2004,15(8):1172-1181)

HaasPJ,SwamiAN.Sequentialsamplingproceduresforquerysizeestimation[C]PPProcoftheACMSIGMOD1992.NewYork:ACM,1992:341-350

[18]

LastM.

Improvingdataminingutilitywithprojective

[2]CochranWG.SamplingTechniques[M].3rded.NewYork:JohnWiley&Sons,1977

[3]LevyPS,LemeshowS.SamplingofPopulations:MethodsandApplications[M].NewYork:JohnWiley&Sons,1991

[4]LohrSL.Sampling:DesignandAnalysis[M].PacificGrove,CA:DuxburyPress,1999

[19]

sampling[C]PPProcofthe15thACMSIGKDDIntConfonKDD.NewYork:ACM,2009:487-496

BabcockB,ChaudhuriS,DasG.Dynamicdampledelectionforspproximatewueryprocessing[C]PPProcofACMSIGMOD2003.NewYork:ACM,2003:539-550

[20]

BrownPG,HaasPJ.Techniquesforwarehousingofsampledata[C]PPProcofthe22ndICDE.LosAlamitos,CA:IEEEComputerSociety,2006:6

[21]

ChaudhuriS,DasG,NarasayyaV,etal.Optimization-basedapproachforapproximateansweringofaggregatequeries[C]PPProcofACMSIGMOD2001.NewYork:ACM,2001:295-306

[22]

ThompsonStevenK,SeberGeorgeAF.AdaptiveSampling[M].NewYork:JohnWiley&Sons,1996

[23]

OlkenF.Randomsamplingfromdatabase[D].Berkeley:UniversityofCalifornia,2005

[24]

PalmerC,

FaloutsosC.

Densitybiasedsampling:

An

[5]OlkenF,RotemD.RandomsamplingfromB+trees[C]PPProcofthe15thIntConfonVLDB.SanFrancisco:MorganKaufmann,1989:269-277

[6]OlkenF,RotemD.Samplingfromspatialdatabases[J].StatisticsandComputing,1995,5(1):43-57

[7]GibbonsPB,MatiasY.Newsampling-basedsummarystatisticsforimprovingapproximatequeryanswers[C]PPProcofACMSIGMOD1998.NewYork:ACM,1998:331-342

[8]AcharyaS,GibbonsPB,PoosalaV.Congressionalsamplesforapproximateansweringofgroup-byqueries[C]PPProcoftheACMSIGMODonManagementofData.NewYork:ACM,2000:487-498

[9]ChaudhuriS,DasG,DatarM,etal.Overcominglimitationsofsamplingforaggregationqueries[C]PPProcofICDE2001.LosAlamitos,CA:IEEEComputerSociety,2001:534-542

improvedmethodfordataminingandclustering[C]PPProcofACMSIGMOD2000.NewYork:ACM,2000:82-92

[25]

KolliosG,GunopoulosD,KoudasN,etal.Efficientbiasedsamplingforapproximateclusteringandoutlierdetectioninlargedatasets[J].IEEETransonKnowledgeandDataEngineering,2003,15(5):1170-1187

[26]

CormodeG,MuthukrishnanS.Summarizingandminingskeweddatastreams[C]PPProcofthe5thSIAMIntConfonDataMining.NewportBeach,USA:SocietyforIndustrialandApplied,2005:12

[27]

ZhouShuigeng,ZhouAoying,etal.Afastdensity-basedclusteringalgorithm[J].JournalofComputerResearchandDevelopment,2000,37(11):1287-1292(inChinese)(周水庚,周傲英,等.一种基于密度的快速聚类算法[J].计算机研究与发展,2000,37(11):1287-1292)

[28]

ToivonenH.Samplinglargedatabasesforassociationrules[C]PPProcofthe22ndVLDB.SanFrancisco:MorganKaufmann,1996:134-145

[29]

LiW,

GaoX,

ZhuY,

etal.

Onthesmallsample

[10]GibbonsPB.Distinctsamplingforhighly-accurateanswerstodistinctvaluesqueriesandeventreports[C]PPProcofVLDB2001.SanFrancisco:MorganKaufmann,2001:541-550

[11]GibbonsPB,MatiasY,PoosalaV.Fastincremental

maintenanceofapproximatehistograms[J]ACMTransonDatabaseSystems,2002,27(3):261-298

[12]

BabcockB,DatarM,MotwaniR.Samplingfromamovingwindowoverstreamingdata[C]PPProcofthe13thAnnualACM-SIAMSymponDiscreteAlgorithms.SanFrancisco,California:SocietyforIndustrialandAppliedMathematics,2002:633-634

[13]

MankuGS,MotwaniR.Approximatefrequencycountsoverstreamingdata[C]PPProcofthe28th

VLDBConf.

Trondheim,Norway:VLDBEndowment,2002:346-357

[14]

CormodeG,MuthukrishnanS,RozenbaumI.Summarizingandmininginversedistributionsondatastreamsviadynamicinversesampling[C]PPProcofthe31stIntConfonVLDB.Trondheim,Norway:VLDBEndowment,2005:25-36

[15]

ProvostF,

JensenD,

OatesT.

Efficient

progressive

performanceofboostedclassifiers[C]PPProcoftheIEEEComputerSocietyConfonCVPR.LosAlamitos,CA:IEEESsampling[C]PPProcofthe15thACMSIGKDD.NewYork:,

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

[30]

Parthasarathy

S.

Efficient

progressive

sampling

for

[44]

53

BabcockB,BabuS,DatarM,etal.Modelsandissuesindatastreamsystems[C]PPProcofthe21stACMSIGACT-SIGMOD-SIGARTSymponPrinciplesofDatabaseSystems.NewYork:ACM,2002:1-16

[45]

GaberMM,ZaslavskyA,KrishnaswamyS.Miningdatastreams:Areview[J].ACMSIGMODRecord,2005,34(2):18-26

[46]

MankuGS,RajagopalanS,LindsayBG.Approximatemediansandotherquantilesinonepassandwithlimitedmemory[C]PPProcoftheACMSIGMOD.NewYork:ACM,1998:426-435

[47]

DemaineED,

Lopez-OrtizA,

MunroJI.

Frequency

associationrules[C]PPProcoftheIEEEIntConfonDataMining.LosAlamitos,CA:IEEEComputerSociety,2002:354-361

[31]

ChuangKT,ChenMS,YangWC.Progressivesamplingforassociationrulesbasedonsamplingerrorestimation[C]PPProcofthePacific-AsiaConfonAdvancesinKDD.Berlin:Springer,2005:505-515

[32]

BezdekJC,HathawayRJ.Progressivesamplingschemesforapproximateclusteringinverylargedatasets[C]PPProcofAnnualIEEEIntConfonFuzzySystems.Piscataway,NJ:IEEE,2004:VOLS1-3,15-21

[33]

LynchJF.Analysisandapplicationofadaptivesampling[C]PPProcofthe19thACMSIGMOD-SIGACT-SIGARTSymponPrinciplesofDatabaseSystems.NewYork:ACM,2000:260-267

[34]

DomingoC,GavaldaR,WatanabeO.Adaptivesamplingmethodsforscalingupknowledgediscoveryalgorithms[G]PPLNAI1721:ProcofDSp99.Berlin:Springer,1999:172-183

[35]

ChoiBY,ParkJ,ZhangZL.Adaptiverandomsamplingforloadchangedetection[C]PPProcofACMSigmetricsonMeasurementandModelingofComputerSystems.York:ACM,2002:272-273

[36]

FrahlingG,IndykP,SohlerC.Samplingindynamicdatastreamsandapplications[C]PPProcofthe21stAnnSymponComputationalGeometry.NewYork:ACM,2005:142-149

[37]

LawYW,ChatterjeaS,JinJ,etal,Energy-efficientdataacquisitionbyadaptivesamplingforwirelesssensornetworks[C]PPProcofthe2009IntConfonWirelessCommunicationsandMobileComputing.NewYork:ACM,2009:1146-1151

[38]

ChaudhuriS,DasG,NarasayyAV.Optimizedstratifiedsamplingforapproximatequeryprocessing[J].ACMTransonDatabaseSystems.2007,32(2)

[39]

ChoiBY,ParkJ,ZhangZL.Adaptivepacketsamplingforflowvolumemeasurement,TR-02-040[R].MinneapolisandStPaul:UniversityofMinnesota,2002

[40]

ChenB,

HaasP,

ScheuermannP.

Anewtwo-phase

samplingbasedalgorithmfordiscoveringassociationrules[C]PPProcoftheACMSIGKDDp02.NewYork:ACM,2002:462-468

[41]

BronnimannH,ChenB,DashM,etal,Efficientdatareductionmethodsforon-lineassociationrulediscovery[C]PPTheNSFWorkshoponNGDMp02.Cambridge,MA:MITPress,2002:190-208

[42]

BronnimannH,ChenB,DashM,etal.EfficientdatareductionwithEASE[C]PPProcoftheACMSIGKDDp03.NewYork:ACM,2003:59-68

[43]

HwangW,KimD.Improvedassociationruleminingbymodifiedtrimming[C]PPProcofthe6thIEEEIntConfonCITp06.LosAlamitos,CA:IEEEComputerSociety,2006:[56][55][54][53][52][51][50]

New

[49][48]

estimationofinternetpacketstreamswithlimitedspace[C]PPProcofthe10thAnnualEuropeanSymponAlgorithms.Berlin:Springer,2002:348-360

AggarwalCC.Onbiasedreservoirsamplinginthepresenceofstreamevolution[C]PPProcofthe32ndIntConfonVLDB.Trondheim,Norway:VLDBEndowment,2006:607-618

YangXuemei,DongYisheng,etal.Onlinecorrelationanalysisformultipledimensionsdatastreams[J].JournalofComputerResearchandDevelopment,2006,43(10):1744-1750(inChinese)

(杨雪梅,董逸生,等.高维数据流的在线相关性分析[J].计算机研究与发展,2006,43(10):1744-1750

JermaineC,PolA,ArumugamS.Onlinemaintenanceofverylargerandomsamples[C]PPProcACMSIGMODConf.NewYork:ACM,2004:299-310

DashM,SinghaniaA.Mininginlargenoisydomains[J].JournalofDataandInformationQuality(JDIQ),2009,1(2)BuriolLS,FrahlingG,LeonardiS,etal.Countingtrianglesindatastreams[C]PPProcofthe25thACMSIGMOD-SIGACT-SIGARTSymponPrinciplesofdatabasesystems.NewYork:ACM,2006:253-262

ChakrabartiA,DoBaK,MuthukrishnanS.Estimatingentropyandentropynormondatastreams[J].InternetMathematics,2006,3(1):63-78

ChakrabartiA,CormodeG,McGregorA.Anear-optimalalgorithmforcomputingtheentropyofastream[C]PPProcofthe18thAnnACM-SIAMSymponDiscreteAlgorithms.NewOrleans,Louisiana:SocietyforIndustrialandAppliedMathematics,2007:328-335ChuangKun-T,

ChenHung-L,ChenMing-S.

Feature-

preservedsamplingoverstreamingdata[J].ACMTKDD,2009,2(4):1-45JiaCaiyan,

LuRuqian.

Quantitativemodel

andfast

estimationalgorithmofsamplingerrorforassociationrulemining[J].ChineseJournalofComputers,2006,29(4):(

54

(贾彩燕,陆汝钤.关联规则挖掘的取样误差量化模型和快速估计算法[J].计算机学报,2006,29(4):625-634)

[57]

BravermanV,OstrovskyR,ZanioloC.Optimalsamplingfromslidingwindows[C]PPProcofthe28thACMSIGMOD-SIGACT-SIGARTSymponPrinciplesofDatabaseSystems.NewYork:ACM,2009:147-156

[58]

GemullaR,LehnerW,HaasPJ.Adipinthereservoirmaintainingsamplesynopsesofevolvingdatasets[C]PPProcofthe32ndIntConfonVLDB.Trondheim,Norway:VLDBEndowment,2006:595-

606

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

SunZhihui,bornin1941.ProfessorandPhDinclude

supervisordata

of

theand

Southeastcomplicated

University.Hismainresearchinterests

mining

informationsystemintegration.WuYingjie,bornin1979.

Lecturerof

FuzhouUniversity.HehasbeenaPhDcandidatefromtheSoutheastUniversity,Nanjing,Chinasince2007.Hiscurrentresearchinterestsincludedataminingand

dataprivacypreserving.

HuWenyu,professor

of

bornin1963.Fujian

Associate

of

University

Technologysince2002.ShehasbeenaPhDcandidateincomputingsciencefromtheSoutheastUniversity,Nanjing,China

since2006.Hercurrentresearchinterestsincludedatabasetheoryanddatamining.

5智能系统学报6征订启事

5智能系统学报6(CAAITransactionsonIntelligentSystems)是中国人工智能学会会刊,由中国人工智能学会和哈尔滨工程大学联合主办,并且被/中国科技论文统计源期刊0(中国科技核心期刊)、英国5科学文摘6、波兰5哥白尼索引6数据库收录.读者对象主要为国内外各研究机构的科研人员、相关企业工程技术人员及高等院校相关专业广大师生.所刊内容包括人工智能与计算智能、智能控制与决策、智能信息处理、专家系统与知识工程、机器学习与知识发现、人工心理与机器情感,以及智能技术在各领域的应用.

/构建智能平台,打造精品期刊0的高起点办刊理念,为期刊的快速发展奠定了良好的基础.该刊自创办以来,刊发了大量高水平学术论文以及具有自主创新理论研究的科研成果,并以较强的专业性和学术影响力,受到了人工智能领域专家和学者的广泛关注,目前已成为智能科学领域颇具影响的学术期刊.

该刊创刊于2006年,为双月刊,连续出版物号:ISSN1673-4785,CN23-1538PTP,国内邮发代号:14-190,国外邮发代号:BM4940,定价15元P期,90元P年.

可在当地邮局订阅,也可直接联系期刊编辑部办理.

通信地址:哈尔滨市南岗区南通大街145号1号楼5智能系统学报6编辑部邮政编码:150001联系电话:0451-82518134

网 址:http:http:

本文来源：https://www.bwwdw.com/article/udmm.html