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

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于可变网格划分的密度偏差抽样算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：

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

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

中图分类号：TP181；TP301.6

文献标志码：A

0引言

聚类分析是数据挖掘领域内的重要研究方向之一，但经典的聚类算法仅能在小规模数据集上高效运行，当处理海量、高维的数据集时，运行速度及效果将受影响。解决该问题最有效的方法是对原始数据集进行抽样，即通过对样本数据集聚类分析来推测原始数据集的相关信息[1]。

简单随机抽样（Simple Random Sampling，SRS）是数据挖掘领域内最常用的抽样方法，该方法操作简单且效率较高，但当数据分布不均匀时抽样误差较大[2]。针对这一问题，Palmer等[3]于2000年提出了密度偏差抽样（Density Biased Sampling，DBS）算法，该算法首先将原始数据集划分为不同的组，进而通过建立哈希函数将各组映射到哈希表中，根据各组之间的密度偏差确定各组的抽样概率。相对于SRS算法，DBS算法在处理不均匀数据集时可得到能准确反映原始数据集分布特征的样本数据集，但易受哈希冲突的影响[4]。

近年来针对DBS算法的改进主要围绕数据分组方法展开，如文献[5]中提出的基于树结构的密度偏差抽样算法以及文献[6]中提出的基于网格与树结构的密度偏差抽样算法。以上两种算法虽能有效避免哈希冲突并保证样本质量，但抽样效率较低。2012年，有学者提出了一种基于网格的密度偏差抽样（Grid Density Biased Sampling，G_DBS）算法[7]，该算法利用固定的网格结构对原始数据集进行分组，能在相对较短的时间内获得高质量的样本数据集。但如果网格划分粒度过细，抽样效率将降低；如果网格划分粒度过粗，样本质量将受影响。鉴于此，本文在G_DBS算法的基础上，提出了一种基于可变网格划分的密度偏差抽样（Variable Grid Density Biased Sampling，VG_DBS）算法，首先根据原始数据集的分布特征构建特定的网格空间，进而在其基础上执行密度偏差抽样。实验结果表明，相对于G_DBS算法，VG_DBS算法能进一步提高抽样效率并提升样本质量。

1密度偏差抽样

数据挖掘领域内，密度偏差抽样是一种相对较新的抽样策略，其核心思想是根据原始数据集的分布特征生成样本数据集。实际应用中，首先将原始数据集分成不同的组，各组大小（所含数据点的数量）表示该组的密度，然后按以下原则进行抽样：

1）同一组内各数据点被抽取的概率相等；

2）样本数据集的分布特征与原始数据集一致；

3）各组抽样概率的偏差依据各组大小（密度）的偏差；

4）样本量期望值已知。

当各组大小（密度）之间没有偏差时，密度偏差抽样与简单随机抽样的抽样结果是一致的，因此，简单随机抽样可视为密度偏差抽样的特例。相对于简单随机抽样，密度偏差抽样的优势主要体现在以下两个方面：

1）适应性强。密度偏差抽样过程中，可根据需要确定抽样的核心区域。以对大规模数据集的聚类分析为例，为在包含噪声的数据中发现聚类，可仅对高密度区域抽样；为发现所有聚类，需要既对高密度区域抽样又对低密度区域抽样；为发现离群数据，则需对极低密度区域抽样[8]。

2）约简效果好。由于简单随机抽样是一种等概率抽样方法，因此在高密度区域内会抽取较多的数据点。但在实际应用中，高密度区域内仅需要相对较少的数据点就可以计算出正确结果，对剩余部分继续计算并不会对最终结果有太大影响。密度偏差抽样过程中，不同区域的抽样比例不同，在各区域内单独抽样可产生更为合适的样本。这种抽样方式既保证了样本质量，又在最大限度上缩减了样本实际规模，提高了抽样效率[9]。

3.2样本质量对比分析

样本质量包括样本完整性和样本正确性两个方面，样本完整性是指样本数据集中包含的聚类个数是否与原始数据集一致，样本正确性是指在样本数据集上进行聚类分析的结果是否正确。为保证实验结果的客观性，各实验中VG_DBS算法在对原始数据集进行可变网格划分时，每一维初始划分的区间段个数与G_DBS算法在每一维所划分的区间段个数一致。

3.3执行时间对比分析

首先对各抽样算法在人工数据集Dataset上的执行时间进行对比分析。通过改变Dataset的数据量，分别测试VG_DBS算法、G_DBS算法和SRS算法抽取1%样本所需时间以及样本聚类时间，实验结果如表4所示。

表4中的实验数据表明：针对人工数据集Dataset，在获得等量样本时，SRS算法执行时间最少，VG_DBS算法执行时间明显少于G_DBS算法；在对样本进行聚类时，VG_DBS算法所抽取样本的执行时间普遍低于另外两种算法；而且随着样本量的逐渐增加，三种算法在执行时间上的差异也逐渐增大。

其次对各抽样算法在UCI标准数据集上的执行时间进行对比分析，在保证三种抽样算法均不丢失类的前提下，分别测试VG_DBS算法、G_DBS算法和SRS算法抽取相同数量的样本所需时间以及样本聚类时间，抽样比例同表3，实验结果如表5所示。

4结语

本文提出了一种基于可变网格划分的密度偏差抽样算法，相对于已有的基于网格的密度偏差抽样算法，该算法最大的特点是能够针对特定数据集构建一个符合该数据集分布特征的网格，较好地解决了大规模不均匀数据集的抽样问题。相对于简单随机抽样算法，该算法所抽取样本的质量有显著提升；而相对于基于固定网格划分的密度偏差抽样算法，该算法在保证样本质量的同时降低了抽样过程的执行时间。但是，本文的研究工作还有待进一步深入和扩展，如对海量高维数据集的处理时间有待进一步缩短等。

参考文献：

[1]张春阳，周继恩，钱权，等.抽样在数据挖掘中的应用研究[J].计算机科学，2004，31（2）：126-128.

[2]GU B H， HU F F， LIU H. Sampling and its application in data mining： a survey[R]. Singapore： National University of Singapore， 2000.

[3]PALMER C R， FALOUTSOS C. Density biased sampling： an improved method for data mining and clustering[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York： ACM Press， 2000：82-92.

[4]胡文瑜，孙志辉，吴英杰.数据挖掘取样方法研究[J].计算机研究与发展，2011，48（1）：45-54.

[5]NANOPOULOS A， THEODORIDS Y， MANOLOPOULOS Y. Indexedbased density biased sampling for clustering applications[J]. Data & Knowledge Engineering， 2006， 57（1）：37-63.

[6]APPEL A P， PATERLINI A A， de SOUSA E P M， et al. A densitybiased sampling technique to improve cluster representativeness[C]// Proceedings of PKDD 2007.Berlin： Springer， 2007：366-373.

[7]HUANG J B， SUN H L， KANG J M， et al. ESC： an efficient synchronizationbased clustering algorithm [J].KnowledgeBased Systems， 2013， 40：111-122.

[8]唐成龙，邢长征.基于数据分区和网格的离群点挖掘算法[J].计算机应用，2012，32（8）：2193-2197.

[9]余波，朱东华，刘嵩，等.密度偏差抽样技术在聚类算法中的应用研究[J].计算机科学，2009，36（2）：207-209.

[10]ZHAO Y C， CAO J， ZHANG C Q， et al. Enhancing griddensity based clustering for high dimensional data[J]. Journal of Systems and Software，2011，84（9）：1524-1539.

[11]PILEVAR A H， SUKUMAR M. GCHL： a gridclustering algorithm for highdimensional very large spatial data bases [J]. Pattern Recognition Letters， 2005， 26（7）：999-1010.

[12]张建锦，吴渝，刘小霞.一种改进的密度偏差抽样算法[J].计算机应用，2007，27（7）：1695-1698.

[13]贺玲，蔡益朝，杨征.高维数据的相似性度量研究[J].计算机科学，2010，37（5）：155-156.

[14]贺玲，蔡益朝，杨征.高维数据空间的一种网格划分方法[J].计算机工程与应用，2011，47（5）：152-153.

[15]赵卓真.一种基于密度与网格的聚类算法[D].广州：中山大学，2012.