数据挖掘取样方法研究

作者/邢馨心，河北衡水中学

数据挖掘取样方法研究

作者/邢馨心，河北衡水中学

取样方法这种有效的近似技术在现在的数据挖掘研究中能够最大限度的减小数据集的处理规模，将大规模数据集及数据流数据上以数据挖掘算法进行处理。取样法具有通用有效的特点。本文化通过对数据挖掘领域的取样方法分类以及影响取样方法选择的因素等问题进行分析研究，着重探讨了数据挖掘领域的代表性取样方选用以及应用发展。

数据挖掘；取样方法；均匀取样；偏倚取样

如今数据库技术发展迅速、应用广泛，数据库中存储的数据量也在急剧增长。数据挖掘就是把信息模式或未知和潜在有用的数据从海量数据存储的数据库中提取出来的一种方法。在数据挖掘领域中,采用一些有效的技术方法来处理数据，来减少和降低数据规模是有效准确提取数据的一种重要手段。取样这种近似技术在处理数据集的规模上应用广泛，它可以在的数据挖掘研究中能够最大限度的减小数据集的处理规模，将大规模数据集及数据流数据上以数据挖掘算法进行处理。因此，这种通用的技术被广泛应用到数据挖掘、统计评估、查询优化、数据流处理和机器处理学习中。

1.数据挖掘的取样方法

作为一种经典的统计技术，抽样长时间被广泛应用于多个领域，当然也包括现在的数据管理领域。在数据管理中，通常我们会在大数据集中抽取具有数据基本特征的小部分数据子集来作为代表性样本, 再根据该样本进行数据挖掘来获得近似的查询结果。目前取样技术中的诸多方法在数据管理中被广泛运用。

■1.1 取样方法的类别

取样方法根据各数据项被选中概率的相同与否，主要可以分为均匀取样和偏倚取样两大类，均匀取样是指数据项被选中的概率相同，偏倚取样是指数据项被选中的概率不同。在取样过程中，均匀取样设计这种所有以相同的取样概率产生的相同尺寸且相互雷同的取样，一般主要分为伯努利取样和水库取样两种经典的取样设计，这两种取样设计是其他各类取样方法的基础。伯努利取样具有取样过程简单、时间成本低和取样均匀的特点。水库取样是一种随机均匀取样法，它通过单遍扫描数据集的方法生成均匀取样集，它有效降低了时间复杂度，而且由于空间大小比较固定,所以很适合在数据库领域应用。取样技术的关键环节是如何确保取样质量，传统的取样策略通常为三大类，分别是通过逐渐加大取样尺寸或取样率来使模型的正确性达到不再随取样进行改善的渐进取样；以一个尺寸小的实验样本集进行数据集的预评估的如采用分层取样、Two–Phase Sampling、luster Sampling等算法进行取样的策略；第三类策略是以频繁项误差概要、近似查询和查询尺寸评估应用为方法来具体的应用抽取特定的数据特征的取样策略。

■1.2 取样方法的分析研究

1.2.1 最具代表性的取样法

（1）A/R Sampling

A/R Sampling是一种应用于关系数据库B+ 树或空间数据库的随机取样算法。它的主要流程是首先先选取某一种算法，随机在数据集中均匀抽取一个候选元素与选择条件进行对比，将经筛选后的所有与条件相符的元素放入样本集中，拒绝条件不相符的元素，然后继续第一步循环。

（2）精确取样

精确取样方法对于样本集中只出现一次的元素依然采用水库取样的方式，以元素代码表示，而对于于多次出现的元素则进行了一定的改进采用value, count结构来表示，value即意味着元素代码，count表示样本集中的元素数量。这种将各元素以初始值为1的概率参数T加入到样本集合，当元素在样本集中时则在计数器加1，如果样本集溢出，就需要更改参数T，将样本集中各个元素按照原参数与新参数之比进行删除，以获得存放新数据的空间的方法就是我们所说的精确取样算法。它有效实现数据流上的均匀取样，节约了内存。

（3）计数取样

作为精确取样方法变种的计数取样是一种在处理样本集溢出时所采取的一种变化性的方法。当样本集溢出时,改变参数T，用原数据参数与新数据参数的比值来判断是否进行减去，当计数器值下降为0时就停止对该元素数据进行操作。

（4）国会取样

这种取样方法一般主要应用于分组近似查询，在每个分组内通过进行取样率不同的独立的水库取样，对分组属性集中子集可能的组合情况进行综合考虑。这种方法是一种对各分组属性采用不同取样概率来达到最佳查询质量的取样方法，是均匀取样和偏倚取样的综合，它有效突破了均匀取样的局限性，将不同分组大小数据的影响力和利益都考虑到取样过程中。

（5） Stratif i ed Sampling

Stratif i ed Sampling是一种分层的取样，它主要通过数据分布的历史经验来实现对数据进行取样，在取样过程中，对重要层分配的取样点相对较多，然后采用随机均匀取样法对每一层进行取样。这样有效提高了评估的正确性，在取样过程中要合理的对层数进行选择并将数据分配到各个层中，从而使查询处理结果达到偏差最小的状态。

（6）加权取样

在近似聚集查询处理中，加权取样有效的克服了均匀取样的局限性，并且将更大的权重赋予使用率高的小数据集中的元组，借助工作负载信息获得权值，是一种带权值的偏倚取样方法。

（7）Distinct Sampling

Distinct Sampling是一种对流查询中的唯一值进行聚集的取样技术的统称。这种取样方法使关系表更为精确，不至于遗漏关系表中稀少出现的属性值，能够通过对数据中的唯一值进行单遍扫描取样，正确的评估唯一值的数目并对数据的插入和删除进行增量维护。

1.2.2 均匀取样与偏倚取样

由于均匀取样具有一定的局限性，所以在数据挖掘中出现了偏倚取样法，它成功弥补了均匀取样的弱点，使数据挖掘算法更为精确。均匀随机取样主要应用于数据分布概率比较均匀时，而当数据的尺寸决定样本准确性时，应用均匀取样就使查询的精准度降低了。有时候占小比例的数据对用户来说要比占大比例的数据重要的多。当数据的代表性都相同时，不同逻辑部分的数据就对用户产生了偏斜的作用。当数据分布存在较大偏斜时，为了加速多维大数据集中聚类和离群检测等挖掘任务的执行，主要应用数据约减技术的密度偏倚取样法，因为它能有效解决取样过程中的偏斜、噪声和高维问题能。

2.数据挖掘取样技术的发展

取样方法主要包括生成概要数据结构、数据预处理 、数据流近似聚集查询、流数据分析与挖掘等，它目前广泛应用于数据领域中。

■2.1 传统取样技术在数据挖掘领域的拓展

Adaptive Sampling, Stratif i ed Sampling等统计学领域中的传统取样技术目前正广泛应用于数据挖掘和数据流领域。Adaptive Sampling 能够有效评估有穷非负整数数列的通用方法，在数据挖掘领域中有着广泛的应用。它是一种能够有效调节取样大小，以最小取样尺寸解决误差的一种自适应取样方法。

■2.2 数据流中管理和挖掘中的取样技术

数据流管理和数据流挖掘是数据流取样技术的两种基本表现方法。计数取样、链式取样、水库取样、精确取样等算法主要是用于数据流处理模型中生成概要数据结构时。而在数据流近似聚集查询时主要应用国会取样和DV Sampling 类算法。对于数据流的查询、分类、评估以及在线相关性分析我们一般主要采用偏倚取样技术。

■2.3 取样技术发展前景

传统的取样技术在数据挖掘领域中取得了重大的发展在数据库的查询优化、数据挖掘算法的数据预处理等方面，对取样技术的研究相对较多，而且成果显著，但由于取样算法中对于任意顺序的差异与删除和滑动窗口模型中应用的取样技术、如何以最小化的样本集中取得结果精确的最大化、如何设计偏倚取样的算法等研究还比较较少，所以传统取样技术在数据挖掘领域的应用依旧面临着很大的研究挑战。以数据流管理领域最为突出。

3.结束语

通过研究发现，传统取样技术在数据挖掘领域得到了深远的发展，有了新的生命力和内涵。但取样技术的研究空间和研究挑战性依然很大，人们期待更多新的取样技术能做出更多的突破性发展。

＊ [1]胡臻龙.基于数据挖掘的高效取样方法对手机用户的周期运动模式的研究[J].科技通报,2013,(11):134-139+156.

＊ [2]胡文瑜,刘建华,张柏礼.近似聚集查询中Congress onal Samples 算法的优化研究[J].数学的实践与认识，2013,(08):160-169.