基于可变网格划分的密度偏差抽样算法

摘要

As the most commonly used method of reducing large-scale datasets,simple random sampling usually causes the loss of some clusters when dealing with unevenly distributed dataset.A density biased sampling algorithm based on grid can solve these defects,but both the efficiency and effect of sampling can be affected by the granularity of grid division.To overcome the shortcoming,a density biased sampling algorithm based on variable grid division was proposed.Every dimension of original dataset was divided according to the corresponding distribution,and the structure of the constructed grid was matched with the distribution of original dataset.The experimental results show that density biased sampling based on variable grid division can achieve higher quality of sample dataset and uses less execution time of sampling compared with the density biased sampling algorithm based on fixed grid division.%简单随机抽样是在分析处理大规模数据集时最常用的数据约简方法,但该方法在处理内部分布不均匀的数据集时容易造成类的丢失.基于固定网格划分的密度偏差抽样算法虽能有效解决该问题,但其速度及效果易受网格划分粒度影响.为此提出了基于可变网格划分的密度偏差抽样算法,根据原始数据集每一维的分布特征确定该维相应的划分粒度,进而构建与原始数据集分布特征一致的网格空间.实验结果表明,在可变网格划分的基础上进行密度偏差抽样,样本质量明显提升,而且相对于基于固定网格划分的密度偏差抽样算法,抽样效率亦有所提高.