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

近几十年来,随着数据库技术迅速发展和广泛应用,数据库中存储的数据量急剧增大.在数据挖掘领域中,除了研究时空有效性不断提高的挖掘算法外,还必须采取相应的技术方法降低所处理的数据规模.特别是近年来数据流广泛出现在众多领域,例如网络监测、通信数据管理、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.

图