计算机应用 ›› 2013, Vol. 33 ›› Issue (09): 2419-2422.DOI: 10.11772/j.issn.1001-9081.2013.09.2419

• 先进计算 • 上一篇    下一篇

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

盛开元,钱雪忠,吴秦   

  1. 江南大学 物联网工程学院,江苏 无锡 214122
  • 收稿日期:2013-04-08 修回日期:2013-04-29 出版日期:2013-09-01 发布日期:2013-10-18
  • 通讯作者: 盛开元
  • 作者简介:盛开元(1991-),男,山东临沂人,硕士研究生,主要研究方向:数据挖掘;
    钱雪忠(1967-),男,江苏无锡人,副教授,〖BP(〗硕士生导师,〖BP)〗主要研究方向:数据库、数据挖掘、网络计算;
    吴秦(1978-),女,江苏宜兴人,副教授,主要研究方向:计算机视觉、模式识别、文本聚类、数据挖掘。
  • 基金资助:

    国家自然科学基金资助项目;国家自然科学基金资助项目

Density biased sampling algorithm based on variable grid division

SHENG Kaiyuan,QIAN Xuezhong,WU Qin   

  1. School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China
  • Received:2013-04-08 Revised:2013-04-29 Online:2013-10-18 Published:2013-09-01
  • Contact: SHENG Kaiyuan

摘要: 简单随机抽样是在分析处理大规模数据集时最常用的数据约简方法,但该方法在处理内部分布不均匀的数据集时容易造成类的丢失。基于固定网格划分的密度偏差抽样算法虽能有效解决该问题,但其速度及效果易受网格划分粒度影响。为此提出了基于可变网格划分的密度偏差抽样算法,根据原始数据集每一维的分布特征确定该维相应的划分粒度,进而构建与原始数据集分布特征一致的网格空间。实验结果表明,在可变网格划分的基础上进行密度偏差抽样,样本质量明显提升,而且相对于基于固定网格划分的密度偏差抽样算法,抽样效率亦有所提高。

关键词: 密度偏差抽样, 可变网格划分, 数据挖掘, 大规模数据集, 聚类

Abstract: 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.

Key words: density biased sampling, variable grid division, data mining, large-scale dataset, clustering

中图分类号: