数据挖掘取样方法研究

　　摘要取样即从目标事物中选择有代表性的样本，具有通用有效的特点。通过取样的方法能够有效地将处理数据集的规模减小，这使得在大规模数据集及数据流数据中能够应用数据挖掘算法。本文主要阐述了数据挖掘领域中取样技术应用的研究与发展，分析和阐述了数据挖掘领域取样方法面临的挑战与发展方向。
　　【关键词】数据挖掘 取样方法 均匀取样 偏倚取样
　　数据库技术的发展与应用使数据库中数据量不断增大。数据挖掘领域中需要对所处理的数据规模进行降低。作为最通用的近似技术，取样由于其处理大规模数据中的优势而得到了广泛使用。取样方法能够将需要处理的数据集的规模明显缩小，这就导致了在数据挖掘中的很多大数据集及数据流数据中都开始广泛应用取样方法。概要结构设计时当前数据挖掘技术的研究核心。取样方法由于其独特的、突出的伸缩性和灵活性而成为了这些方法中非常重要的一种数据流概要构建的方法。
　　1 数据挖掘的取样方法
　　1.1 取样方法分类
　　取样方法依据各数据项被选中的概率进行分类可以分为两类，被选中的概率相同就是均匀取样，被选中的概率不同就是偏倚取样。
　　1.2 取样方法对比与分析
　　1.2.1 代表性取样方法
　　（1）A/R Sampling。A/R Sampling第一步从数据集中利用某种算法随机均匀抽取一个候选元素，第二步是将该候选元素与选择的条件相对比，符合条件的放入样本集(acceptance)，不符合条件的进行拒绝(rejection)，然后重新开始第一步。
　　（2）精确取样。在样本集中仅仅出现一次的元素用元素代码表示，而多次出现的元素用value,countó来进行表示，其中value是元素代码，而countó则表示数量。元素加入到样本集中的时候，如果元素不存在就加到样本集中，如果已经存在就在数目上加1。当样本集溢出之后，将样本集中的各个元素按照原参数与新参数之比进行删除，使新的数据能够有空间存放。
　　（3）计数取样。计数取样是精确取样方法的变种，主要的变化是处理样本集溢出的方法。在删除数据方面，要对数据先用原参数与新参数之比，之后通过新参数分之一来判断数据是否要减去1，当某个数据的计数器的数值降到0之后就不再对该数据进行操作。
　　（4）国会取样。近似查询是国会取样的应用背景，国会取样实际上就是均匀取样和偏倚取样的综合，每个分组内都会独立的水库取样，但取样率并不相同。利用这种方法，分组较大的数据取样率就高，分组较小的数据取样率就低，将分组较小的数据的因素也兼顾在内，能够突破均匀取样的局限性。
　　（5）分层取样。将数据分布的历史经验作为依据来对数据进行分层，比较重要的层就会分配较多的取样点，这样就能够将评估的准确性提高，在每一层中采用随机均匀取样的方法来进行取样。
　　（6）Distinct Sampling。Distinct Sampling属于一种取样技术的统称，所指的取样技术的类型为聚集流查询中的唯一值的取样技术。对数据中的唯一值通过单遍扫描的方式来进行取样，能够实现唯一值数目的正确评估。
　　1.2.2 均匀取样与偏倚取样
　　在数据挖掘中，均匀取样存在的局限性是偏倚取样出现的原因。在数据均匀概率分布时较适合采用均匀随机取样，尤其是在对于用户而言取样主要是对数据的分布情况进行反映时。在数据中，占比例较小的数据代表性是不够的，但并不说明它对用户来说不重要。反过来说也就是，当数据的代表性都相同时，数据对于用户的作用是偏倚的。Palmer指出偏倚取样的放能够能够使数据挖掘算法的精度得到提高。
　　2 数据挖掘取样技术的发展
　　2.1 数据挖掘领域中传统取样技术的拓展
　　自适应取样是一种对于有穷非负数数列和进行评估的方法，自适应取样的取样大小在数据挖掘领域是能够进行调节的，能够实现在用更加小的取样尺寸在误差界内解决问题。
　　两阶段取样能够实现取样成本的节约。例如在对象集A中，要取样M需要较高的代价，因此通过辅助变量N的取样来降低取样的代价。具体的取样过程为，第一步，在A 中需要抽取的尺寸较大的Q'，在Q'中获得N；第二步，利用第一步中N的信息来在Q'中得到Q，最终获得的目标值M~的精确度就会较高。
　　2.2 数据流中的取样技术
　　取样技术在数据流中主要反映在数据流管理和数据流挖掘方面。一是在数据流的处理模型中概要数据结构的生成需要用到水库取样、计数取样等取样技术；二是在数据流的近似聚集查询中需要用到国会取样、Distinct Sampling等；三是数据流中采用偏倚取样技术，偏倚取样技术能够应用于数据流的查询、评估、分类、在线相关性分析等方面。
　　3 取样技术面临的挑战
　　在数据挖掘领域中，传统的取样技术有着深远的发展，并且被赋予了新的内涵和活力。在数据库的查询优化、数据挖掘算法的数据预处理等方面有着比较充分和比较成熟的研究，但是依旧面临着研究的挑战，这些挑战主要包括：最小化的样本集中如何取得结果精确的最大化；滑动窗口模型中应用的取样技术研究较少，存在上界不确定、附加成本高、滑动窗口小等限制；取样算法中对于任意顺序的差异与删除方面的研究较少；在选择偏倚取样时，如何设计偏倚取样的算法。
　　4 总结
　　本文对数据挖掘中取样技术的分类及传统取样技术进行了阐述，在了解取样技术的基础上，通过实例应用说明了数据挖掘中取样技术的重要性和可行性。通过对数据挖掘中取样技术的发展的论述，看到了取样技术的进步与发展机遇，结合取样技术面临的挑战，确定取样技术发的方向。
　　
　　参考文献
　　[1]胡臻龙.基于数据挖掘的高效取样方法对手机用户的周期运动模式的研究[J].科技通报,2010,03(09):19-24.
　　[2]胡文瑜,刘建华,张柏礼.近似聚集查询中Congressional Samples算法的优化研究[J].数学的实践与认识,2010,12(11):11-13.
　　[3]沈勇，颜建军，王忆勤，许朝霞，刘国萍.于数据挖掘的中医信息处理方法研究概述[J].中华中医药学会中医诊断学分会第十次学术研讨会论文集,2011,23(14):19-26.
　　
　　作者单位
　　河西学院信息技术与传媒学院甘肃省张掖市 734000