数据挖掘取样方法研究  

Study of Sampling Methods on Data Mining and Stream Mining

作　　者：胡文瑜[1,2] 孙志挥[1] 吴英杰[1,3] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]福建工程学院计算机与信息科学系,福州350108 [3]福州大学数学与计算机科学学院,福州350108

出　　处：《计算机研究与发展》2011年第1期45-54,共10页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60873176);福建省教育厅科技项目(JA08161)

摘　　要：取样是一种通用有效的近似技术.在数据挖掘研究中,取样方法可显著减小所处理数据集的规模,使得众多数据挖掘算法得以应用到大规模数据集以及数据流数据上.通过对应用于数据挖掘领域的代表性取样方法的比较研究和分析总结,提出了一个取样算法分类框架.在指出了均匀取样局限性的基础上阐述了某些应用场景中选用偏倚取样方法的必要性,综述了取样技术在数据挖掘领域的应用研究与应用发展,最后对数据流挖掘取样方法面临的挑战和发展方向进行了展望.Sampling is an efficient and most widely-used approximation technique.It enables lots of algorithms to be applied to huge dataset by use of scaling down dramatically dataset for data mining and streaming mining.Throughout the detailed review,a kind of taxonomic frame of sampling algorithms based on uniform sampling and biased sampling is presented;meanwhile,analysis,comparisons and evaluations of representative sampling algorithms such as reservoir sampling,concise sampling,count sampling,chain-sampling,DV sampling and so on are performed.Due to the limitations of uniform sampling in some applications—queries with relatively low selectivity,outlier detection in large multidimensional data sets,and clustering over data streams with skewed Zipf distribution,the importance of need for using biased sampling methods in these scenarios is fully dissertated.In addition to listing successful applications of sampling techniques in data mining,statistics estimating and stream mining up to now,we survey the application and development of sampling techniques,especially those traditional classic sampling techniques such as progressive sampling,adaptive sampling,stratified sampling and two-phase sampling etc.Finally,future challenges and directions with respect to data stream sampling are further discussed.

关 键 词：数据挖掘 均匀取样 偏倚取样 数据流 概要数据结构 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP391[自动化与计算机技术—计算机科学与技术]