姜 姗，高 远，许玉龙

(河南中医药大学，河南 郑州 450046)

1 引言

互联网空间数据库是存储数据、管理数据的主要方式[1]。但随着信息技术的迅速发展，海量信息呈现爆炸式增长趋势，导致空间数据库出现数据冗余等现象[2，3]。因此，为了保证空间数据库位置冗余数据能够得到有效查看，需要对空间数据库位置冗余数据进行查询。

文献[4]提出 基于差分隐私的社交网络位置近邻查询方法 ，通过网格化分割空间区域，依据用户位置访问量对隐私预算进行分配。采用组合增量近邻查询算法，扩大空间检索范围，实现过滤冗余数据查询。该方法的查询命中率较高，但存在查询冗余数据时间消耗率高的问题。文献[5]提出一种海量空间数据云存储与查询算法方法，该方法通过空间数据操作的主要特征，利用空间四叉树模型组织存储云平台中的空间数据，并构建空间索引，采用两步查询法，完成对空间数据的查询。该方法的大数据集空间查询响应具有较好的实时性，但存在查询数据后空间占用率高的问题。针对上述问题，提出基于果蝇算法的空间数据库位置冗余数据查询方法。

2 填补空间数据

由于空间数据库中的数据数量繁多，且容易出现冗余数据，因此为了实现对空间数据库位置冗余数据的查询，首先要对空间数据库中的缺失数据进行填补。空间数据库中的数据在缺失时，首先构建一个BP神经网络模型，利用BP神经网络对缺失数据进行估算，如图1所示。

图1 BP神经网络模型

图1中，将空间数据库中不具有缺失数据属性的样本数据当作网络的输入，而具有缺失数据属性的数值当作网络的输出。当样本数据中的已知数据训练网络满足这些要求后，应将具有缺失数据的已知数据输入到网络中，待网络输出后，这些数值就是缺失数据的估计值[6]。

通过三层BP神经网络，假设输入层节点数目由m描述，输出层节点数目由n代表，u描述的是隐含层节点数目，那么通过输出层输出的节点函数用方程定义如下

(1)

式中，经隐含层到输出层的连接权值由Vrj表示，隐含层节点值通过br描述，输出层内节点阈值通过θj代表，Cj就是输出层的节点值。

节点在隐含层中输出时，用方程定义为

(2)

式中，Wir描述的是从输入层到隐含层的连接权值，输入层的节点值为ai，隐含层节点的阈值代表Tr。

神经网络在学习过程中的算法过程如下：

1)在(0，1)之间设置Wir、Tr、Vrj、θj的最小值。

3)在输出层中，对节点输出值和期望值进行计算，其误差用dj来表示

(3)

4)将误差er逆向分配到隐含层节点，则误差er定义为

(4)

5)为了降低神经网络在学习时产生振荡，需要通过添加惯性冲量技术对权值和阈值进行调整[7]。利用添加惯性冲量技术消除高频振荡，从而获取学习率的最大值，从而提升了学习速度[8]。因此，被调整后的权值Vrj和Wir分别表示为

(5)

被调整后的阈值表示为

(6)

式(5)和式(6)中，λ、β分别表示为取(0，1)范围内值的学习率，η、δ分别表示为动量因子。那么整个训练集的误差平方和E用方程表示如下

(7)

6)反复进行步骤2)到步骤5)，当误差dj满足网络要求或变成零时，就可以停止训练，经过上述步骤的反复迭代，直到满足要求才可以获取与之相匹配的神经网络模型。

7)测试集中，将已知数据中存在缺失数据的输送到训练完成的网络内，其中输出值就是缺失数据的估计值。将估计值填补到空间数据库中，从而实现空间数据库的插补。

2.1 位置冗余数据分类

通过填补空间数据库中的缺失数据，从而获得完整的空间数据。根据空间数据库位置冗余的数据，采用粒子群优化算法[9]进行数据挖掘和分类。

在非线性可行情形中，假设x和y是两个向量，那么非线性函数φ对特征空间H进行映射时，它们之间的欧氏距离用方程定义为

(8)

粒子群优化算法属于智能优化算法[12]，假设在D维空间中，有粒子种群n个，它们会构建成种群X={x1，x2，…，xn}，那么位于第i个粒子的位置为Xi={xi1，xi2，…，xin}，目前为止粒子的速度为：Vi={vi1，vi2，…，vin}，其中粒子i经过的最好位置由Pi={pi1，pi2，…，pin}表示，那么所有粒子所经过的最好位置就是：Pg={pg1，pg2，…，pgn}。那么第i个粒子在t+1时刻为

(9)

式中，r1和r2描述的是在(0，1)区间的随机数；c1和c2分别表示学习因子，一般来说，c1=c2=2。

在粒子群优化算法中，每个粒子描述的都是一个解，将此算法放入模糊支持向量机中，通过FSVM训练获取l个支持向量的粒子维数，利用方程(9)对这些样本进行隶属度计算。

(10)

假设初始化粒子的位置范围为[umin，umax]，在初始化粒子群空间内有l个样本权重向量，其中每个粒子都有自身的位置和速度，这些位置就是样本的隶属度，而速度会对隶属度值进行改变。完成对阈值的设定，当粒子输出时，它的隶属度要保持原值，但它的样本隶属度值要比设定的阈值大，否则其隶属度值为0，说明该样本不被选择。

利用训练FSVM取得支持向量集并对训练样本集进行处理，从而获取适应度函数，这时适应度函数表示如下

(11)

式中，M描述的是测试集中的样本数目，fi代表的是预测值，yi代表的是实际值。因此，粒子的适应值越小越优质，从而实现对冗余数据的挖掘和分类。

3 位置冗余数据查询

果蝇算法属于一种觅食行为，通过自身较好的嗅觉对空间数据库中的不同数据进行搜索，距离出现冗余位置的数据较近时，它敏锐的视觉会迅速发现冗余数据的位置或种群其它个体聚集处，在基于果蝇算法的基础上建立了CQAFF连续查询攻击算法，主要流程如下：

1)首先将果蝇种群参数在T时刻进行初始化，其中：M表示种群规模，(x，y)描述的是种群初始随机位置，Tmax代表最大迭代次数。

2)设置f(H)为查询匿名度量，将其作为空间数据集合，i(x，y)代表果蝇个体，利用果蝇嗅觉确定式(12)和随机距离d的位置冗余数据方向和距离，该公式如下

(12)

式中，rand()描述的是0到1之间的随机数。

5)将上述步骤进行反复操作，直到获得果蝇的适应度，并找到果蝇适应度中的最大适应度个体Φmax(xmax，ymax)及最小适应度个体Φmin(xmin，ymin)。

6)种群位置向最大适应度进行随机移动

(13)

式中，xmax和ymax分别表示最大适应度。

7)将T=T+1，并判断最大迭代次数Tmax是否大于T=T+1，若是，就要返回到步骤2)重复执行操作，直到迭代结束或获取到最佳适应度。

8)把实际查询匿名度量f(H)输出，即实际查询匿名度量就是最优解。通过上述步骤，实现基于果蝇算法的空间数据库位置冗余数据查询。

4 实验与分析

为了验证基于果蝇算法的空间数据库位置冗余数据查询方法的有效性，在MATLAB软件平台上进行对比实验。实验在空间数据库中共选取8组冗余数据，数量分别为1000kB、2000kB、3000kB、4000kB、5000kB、6000kB、7000kB和8000kB。分别采用所提方法、文献[4]方法和文献[5]方法对查询冗余数据的时间消耗率进行对比，对比结果如图2所示。

图2 查询冗余数据的时间消耗率对比结果

由图2可知，随着冗余数据数量的增加，不同方法的查询冗余数据的时间消耗率随之增大。所提方法在8组测试中，时间消耗率均在15%以下，说明在查询冗余数据时用时较短，时间消耗较小。而文献[4]方法的最高时间消耗率达到35%，最低时间消耗率达到17%；文献[5]方法的时间消耗率的最高值为30%，最低值为13%。由此可知，文献[4]方法与文献[5]方法的时间消耗率要高于所提方法，表明时间消耗大，冗余数据查询较慢。进一步验证所提方法的空间占用率，选取空间数据8000kB，采用三种方法对查询后的空间数据占用率进行对比，对比结果如图3所示。

图3 空间位置数据查询后空间占用率对比结果

根据图3可知，所提方法从1000kB数据到8000kB数据的空间占用率一直保持在15%以下，而文献[4]方法的初始空间占用率为22%，到8000kB数据时空间占用率达到29%；文献[5]方法在空间数据数量为2000kB时，最低空间占用率为23%，最高空间占用率为34%。由此可知，所提方法的空间占用率要小于文献[4]方法和文献[5]方法，从而节省了空间数据库的空间。

通过图2和图3的对比分析可知，所用方法能够快速实现冗余数据的查询且在空间数据库中的空间占用率较低，这是因为该方法采用粒子群优化算法对冗余数据进行挖掘和分类，使空间数据库中的训练样本数据减少，以此提升了训练速度，进而减少了时间的消耗和降低了空间占用率。

在此基础上，选择5组冗余数据，分别采用三种方法对冗余数据查询效率进行对比分析，对比结果如表1所示。

表1 不同方法的冗余数据查询效率测试

分析表1中的数据可知，当冗余数据数量为5000kB时，所提方法的平均冗余数据查询效率为99%，而文献[4]方法和文献[5]方法的平均冗余数据查询效率分别为66.2%和82%。由此可知，所提方法的查询效率要优于文献[4]方法和文献[5]方法，说明所提方法在数据查询时空间数据库运行较快，进而提升了查询效果。

5 结束语

为了降低冗余数据查询时间消耗率和空间占用率，提高冗余数据查询效率，提出基于果蝇算法的空间数据库位置冗余数据查询方法，首先利用BP神经网络模型，估算空间数据库中的缺失数据，完成对空间数据库的插补。然后使用粒子群优化算法，对空间数据库进行挖掘和分类，获取粒子的最优位置。最后采用果蝇算法对分类后的空间数据进行位置冗余数据查询，提高了空间数据库位置冗余数据查询的整体有效性，解决了传统方法中存在的问题，为今后的信息领域提供了重要基础。