数据挖掘取样方法研究

Study of Sampling Methods on Data Mining and Stream Mining

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

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.