摘要
取样是一种通用有效的近似技术.在数据挖掘研究中,取样方法可显著减小所处理数据集的规模,使得众多数据挖掘算法得以应用到大规模数据集以及数据流数据上.通过对应用于数据挖掘领域的代表性取样方法的比较研究和分析总结,提出了一个取样算法分类框架.在指出了均匀取样局限性的基础上阐述了某些应用场景中选用偏倚取样方法的必要性,综述了取样技术在数据挖掘领域的应用研究与应用发展,最后对数据流挖掘取样方法面临的挑战和发展方向进行了展望.
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2011年第1期45-54,共10页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60873176)
福建省教育厅科技项目(JA08161)
关键词
数据挖掘
均匀取样
偏倚取样
数据流
概要数据结构
data mining
uniform sampling
biased sampling
data stream
synopsis data structure