基于不均匀数据的密度偏差抽样改进算法

吕丹+龙华+高杰+邵玉斌+杜庆治

摘 要：针对不均匀数据集的抽样问题，已有隨机抽样算法、基于固定网格划分的单维度算法、基于可变网格划分的单维度算法，但仍无法更好地反映数据分布特征问题。在数据挖掘的实际应用中，数据规模越来越大，数据类型也越来越复杂，存在系统整体开销大、时间运行成本高等问题。提出并实现了基于不均匀数据的密度偏差抽样改进算法（IDDS），通过引入网格单元密度和三角函数，从而达到较好的密度偏差抽样效果。实验结果发现，IDDS算法抽样效果更好，提取的样本质量更高，有效保证了不均匀数据的分布特征。与原始的密度偏差抽样算法（DDS）相比，应用IDDS算法的效率更高。

关键词：密度偏差抽样算法（DDS）；POI信息；数据挖掘；三角函数

DOIDOI：10.11907/rjdk.172395

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）002-0077-03

0 引言

在大数据挖掘过程中，数据挖掘效率是评估数据挖掘技术的关键因素之一，而效率的提高涉及到许多方面。面对海量数据，合理有效地利用采样技术可以在丢失少量数据的同时，提高整体挖掘效率[1]。密度偏差抽样方法（DDS）是一种新的抽样方法[2]，具有良好的抽样效果。它是根据原始数据的分布特征来确定样本数据[3]，所建立的样本较好地实现了样本数据和原始数据一致的分布特征，样本质量高，抗噪声能力强[4-5]。它能够自由切换高密度区或低密度区，比随机抽样算法具有更好的约简效果。目前，划分原始数据集组时，从网格类型角度看[6]，可以分为固定网格和可变网格两种类型。固定网格划分技术比较简单，随着数据维度和数量的增加，系统开销增加，可用性也因此减少；可变网格划分技术非常灵活[7]，在划分过程中，可以根据各维数据的分布特征进行自动划分，不仅能有效地减少网格数，还能代表原始数据的分布特征[8]。鉴于此，本文在DDS算法基础上，提出了一种基于可变网格改进的密度偏差抽样算法（IDDS），通过引入网格单元密度和三角函数，从而达到较好的密度偏差抽样效果。仿真实验结果表明，IDDS算法抽样效果更好，提取的样本质量更高，有效保证了不均匀数据的分布特征。

1 密度偏差抽样（DDS）原理

DDS算法[9]将原始数据集T分为不同的组Di，每个组Di中的数据个数为该组的密度，然后根据以下原理抽样：划分后的同一组内各数据点被等概率抽取；不同小组的抽样概率由各组密度决定；样本集的分布特征与原始数据集一致；预先设定样本数量大小。

2 算法介绍

2.1 随机抽样算法（RS）

随机抽样算法是对调查对象的每个部分进行同等概率的抽样，这是一种基于机会平等原则的抽样调查，称为“等概率”[10]。其有4种形式，包括简单随机抽样算法、等距抽样算法、类型抽样算法和整群抽样算法。一般而言，如果一个总体包含N个个体，通过逐个抽取的方法从每个样本中提取样本，并且每次提取时每个个体被抽到的概率相等，则将这种方法称为简单随机抽样算法[11]。

2.2 固定网格划分的密度偏差抽样方法（FMDDS）

固定网格划分是将原始数据集T中的各个维度划分成等长且互不相交的D个区间段，每个维度上划分的区间数D相同（等长度网格划分）。一般情况下，根据实验结果或用户经验设置D的大小。

2.3 可变网格划分的密度偏差抽样方法（VDDS）

可变网格比固定网格划分更为灵活[12]，划分后的网格更能代表原始数据的分布特性。其基本思想是，首先根据数值大小对原始数据集T中每个维度的数据进行排序（降序或升序），其次是等深度划分排序后的数据，划分成多个网格单元，然后计算网格单元的密度信息，并通过比较合并各维度上相似密度的相邻网格单元[13]。在此基础上，使最后形成的网格空间中的网格个数有很大不同。

3 基于可变网格改进的密度偏差抽样算法（IDDS）

3.1 算法思想

在DDS原理中，参数k是控制全局的参数，其数值对最后采样结果有着重要影响。根据现有相关文献的研究结果来看，参数k通常默认为固定值0.5。参数k的固定设置有很大的局限性，主要体现在难以适应于各类数据集的固定参数。在本文中，通过引入网格密度和三角函数来优化参数k，与固定值参数k相比，改进后的参数k具有更好的抽样效果。通过设置相应函数，在s、t不变的情况下，根据网格密度mi来调整参数k大小，即网格单元密度越大，网格采样样本越多，修改的参数k如下：

3.2 算法实现

4 实验过程及结果

4.1 实验数据与实验环境

为了验证提出的IDDS算法的优越性，基于Matlab2009b仿真工具对不均匀数据集进行实验和分析，实现密度偏差抽样的计算。实验环境为一台Windows 8.0操作系统的PC机，1.6GHz的Intel Core i5处理器和4GB的RAM。

实验中的不均匀数据集是通过Matlab中相关函数随机产生的，产生了3组数据集，包括6 000条矩形数据集，9 000条三角形数据集，5 000条椭圆形数据集，总共20 000条数据，各数据集间密度都有差异。

4.2 实验过程

本文选取了随机抽样算法（RS）、基于可变网格划分的单维密度偏差抽样算法（VDDS）以及基于可变网格划分改进的单维密度偏差抽样算法（IDDS）进行实验分析，通过算法的运行时间和抽样结果比较，验证IDDS算法的有效性。除RS算法外，其余两种算法在网格划分前各维度都根据式（14）～（16）进行归一化处理，然后计算归一化后的均方差，最后选取最小均方差维度划分可变网格。根据改进算法，通过仿真测试分析，本文中的s、t分别设置为0.5、0.8，改进后的参数k为：ki=0.5-0.8cos（miπ2m），在VDDS算法中k设置为0.5。endprint

4.3 实验结果及分析

為了保证实验结果的公正性，对50次抽样结果进行平均值计算，实验结果如表1、图2所示。

表1显示了3种算法的抽样结果，图2则显示了3种算法的运行时间。由表1可知，IDDS算法的抽样效果明显比VDDS算法、RS算法好，抽取样本质量更高，有效保持了原始数据集的分布特征，且抗噪声能力更强。由图2可知，RS算法相比于其它算法，运算量最小，所以运行时间最短。另外，IDDS算法运行时间大于VDDS算法。由此可见，改进后的算法运算量相对于未改进前略大，运算时间也略多。综上述，本文提出的IDDS算法虽然在运行时间上存在一定劣势，但从样本质量看，仍具有一定的合理性和可行性。

5 结语

本文基于不均匀数据探索一种改进的密度偏差抽样算法（IDDS），使用Matlab中的相关函数随机产生不均匀数据集，对其进行归一化处理，计算均方差，选取最小均方差维度划分可变网格。在保证数据间关联性不被破坏的同时，确保了样本数据和原始数据的一致性分布特征，解决了不均匀数据集的抽样问题，最后通过仿真实验验证并分析了算法的合理性。

参考文献：

[1] 何苗.一种基于DBS的聚类算法[J].重庆电子工程职业学院学报，2009，18（3）：83-85.

[2] 余建桥，葛继科，李娅.一种基于密度偏差抽样的孤立点检测算法[J].计算机科学，2004，31（10）：206-208.

[3] XIAO-BO CHI，XIN-CHUN JIA，QING-LONG HAN.Sampled-data stabilization for takagi-sugeno fuzzy systems using membership function deviations[C].IECON 2012-38th Annual Conference on IEEE Industrial Electronics Society，2012：2476-2481.

[4] PEIGUO FU，XIAOHUI HU.Biased-sampling of density-based local outlier detection algorithm[J].2016 12th International Conference on Natural Computation，Fuzzy Systems and Knowledge Discovery （ICNC-FSKD），2016：1246-1253.

[5] KITTISAK KERDPRASOP，NITTAYA KERDPRASOP，JUNPING SUN.Density biased reservoir sampling for clustering[J].Artificial Intelligence and Applications，2005：95-100.

[6] 邓杰.聚类算法在大规模高维数据集上的应用研究[D].无锡：江南大学，2015.

[7] 盛开元，钱雪忠，吴秦.基于可变网格划分的密度偏差抽样算法[J].计算机应用，2013，33（9）：2419-2422.

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

[9] 熊开玲，彭俊杰，杨晓飞，等.基于核密度估计的K-means聚类优化[J].计算机技术与发展，2017，27（2）：1-5.

[10] 周庆元.PPS和简单随机抽样估计效率的实证检验[J].统计与决策，2014（1）：14-17.

[11] 刘爱芹.随机抽样中样本容量确定的影响因素分析[J].山东财政学院学报，2006（5）：60-64.

[12] 潘春燕，吴有富，李方.一种基于可变网格划分的密度偏差抽样技术及其在聚类中的应用研究[J].凯里学院学报，2017，35（3）：16-20.

[13] 胡志冬，任永功，杨雪.基于滑动窗口密度聚类的数据流偏倚采样算法[J].计算机科学，2013，40（9）：254-256.

[14] 纪良浩.基于密度偏差抽样的聚类算法研究[J].重庆邮电大学学报：自然科学版，2007，19（6）：729-732.endprint