论文研究-一种改进的网格搜索闪电定位算法.pdf

所需积分/C币:9 2019-09-13 12:38:48 583KB .PDF
0
收藏 收藏
举报

闪电定位具有较高的实时性和定位精度要求,网格搜索算法存在计算量大的问题。提出了一种基于网格搜索的闪电定位算法优化方法。该方法采用多维空间数据索引快速搜索候选目标区域,通过对比存储在各候选目标区域上的SVM(Support Vector Machine)分类器的分类误差进行闪电定位。实验表明,该方法具有较好的定位精度和可靠性,且能满足实时闪电定位要求。
曹海鹏,谢兴生,祝宝友:一种改进的网格搜索闪电定位算法 2016,52(16) 式分类和预测回归等方面具有良好的性能 要保证目标格点必须在备选网格之内,又要保证选岀来 考虑到闪电到达时间差定位向量的低维非线性特点,的备选网格数量不至于太多。通过多重实验验证,本文 本文分类器核函数选用RBF。对每一个网格选取属于该的ξ取值为5.716×10°,能够较好满足上述要求。表2 网格的400个点和不属于该网格的600个点作为训练集,给出了使用KD树索引与全表扫描和一维索引对于同 训练出一个sVM分类器模型;再随机选取100个属于次备选网格查询耗时对比,可见KD树索引与表分区 该网格的点和100个不属于该网格的点作为测试集,测能够大幅提高查询速度。 试该分类器的正确率;最后通过十折交叉验证,选取合适 表2备选网格查询时间对比 的核函数参数,不断优化分类结果仗其达到系统要求的网格数KD树索引一维索引s全表扫描/s 分类正确率为止。实验表明所有网格分类器的平均分 16 0.051 类正确率在94.39%左右,能够实现较准确的分类判别。 0.195 每个网格点上训练的SVM分类器参数单独存在磁 ).072 盘的文件中,文件路径伴随存入对应的网格数据记录中。 3.3多维空间数据索引设计 73 0.575 3.98 11.23 当定位精度要求较高,网格单元记录会很多,采用 常规数据库一维索引或多个一维索引组合检索的时间34联合定位算法设计 性能很差。考虑到网格分布的典型空间区域特性,本文 本文提出的基于多维空间数据索引技术与支持向 引入了空间索引来组织网格记录在数据库中的存储。量机融合的闪电定位算法,针对网格搜索算法,作了较 常用的多维空间索引数据结构主要有R树和KD树。大改进。首先通过先验条件计算出每个网格的时间差 K冂树搜索速度更快,而R树对于插入、删除支持更好。定位向量等信息,存储在数据厍中;当闪电发生时,由探 由于网格信息相对固定,只要求查询性能好,故选用KD测站接收到的信号到达时间可以计算出同样格式的时 树作为索引结构。 差定位向量,利用多维室间索引技术,快速选出闪电 本文多维KD树索引的具体设计如下:根据时问差发生位置可能落在哪些备选网格中,大大节省了计算量 定位向量的前3个维度作为三维空间矢量,将数据划分然后通过训练好的网格SVM分类器判断该向量是否属 为10×10×10个子区域(即分区)进行存储,每个分区仅于本网格;为了诚少因误判造成的定位误差,引入了误 存储子区域内的树格单元对应的数据记录。多维KD 差目标函数优化分类器识别结果,选取误差最小的网格 树索引工作的主要目标是快速检索相关分区对应的编点作为最终闪电发牛的位置。具体算法伪代码如下 号。为此,需要额外建立一张独立于网格记录数据表的 算法1闪电联合定位算法 专门KD树索引表。KD树索引表中每条记录存储一个 Input:探测站t的大地坐标(B,L,)与闪电到达时间 节点,其中,非叶结点仅包含数据分割点sl.范围空间=12.3.4 左右子树和父节点;而叶节点仅包含数据记录所 function LIGHT LOCATION MAIN(t) range b 在分区的名称。KD树在每一层针对一个维度选取该维 根据到达时间t求出时间差定位向量time,(i∈{1,2,3,4}, 度数据范围内的适当值V将数据分为大于等于V和小 j∈{1,2,3,4},i< 于V的两个区域,循环切分,直到每个区域仅包含一个 PositionIimes=SEARCH BY TIME (time, ) 最小外包长方体(即一个分区的数据)。因此。数据库 查询数据库得到备选网格 Position times 的100个分区需要树的深度是12,即最多只需要12次 初始化 resultlist用于存放分类器判别属于该类的格点 比较就可以确定一个分区。由于KD树索引表中的记 for each positiontime a Position Times do 录数并不多,索引时间可以忽略不计 Model-Load Model( positiontime) H前主流商业数据库系统都提倛∫支持分区存储 j从磁盘中选取训练好的网格SVM分类器 功能,当存取指定的分区时,可以不涉及其他分区的数 if(SvM Predict( time, Model))then 据记录。由于每个分区中存储的记录大大少于总记录 用模型识别定位向量是否属于该网格 数,因而可以显著提高网格数据记录检索的时间性能。 将当前网格加入 resultlist; 闪电发生后,首先根据探测站接收到闪电信号的精 endif end for 确时间,计算出一个时间差定位向量,并对其三维空间 矢量选取一个阈值半径ξ,得到室间点集的范围区域 if( resultlist为空)then resultlist= position Times (最大外包球形);然后查询KD树索引得到最小外包长 endif 方体与最大外包球形区域相交的一个或多个分区名称; 如果分类器没有选择到格点,就用最小误差目标函数 最后利用近邻条件查询数据库得到三维空间欠量在最 初始化 minDif, result;/最小误差,闪电发生位置的格点 大外包球形内的所有格,作为备选格。阈值ξ,既 for each positiontime E resultList do 10 016,52(16) Computer Engineering and Applications计算机工程与应用 diff-Deviation( time, positiontime eturn可; /求解输入向量和网格格点之间的误差值 d be ift diff< min Diff)then 3.5算法复杂度分析 result=positiontime; 算法主要分为三步,第一步利用多维空间索引检索 minDiff-dift 备选网格,通过建立KD树多维空间索引优化奎询效率, endif 其时间复杂度为杏询索引的时间与数据库查询时间之 end for 和,即12×O(1)+O(bN),其中N为分区内网格总数;第 return result. min diff 二步利用SVM分类器判别时间差向量是香属于岗格内 end begin 算法2备选网格查询算法 和第三步适应函数求值,其时间复杂度均为O(1)。因此 nput时间差定位向time,(∈{1.2,3,4}∈{,2,3、4},<j 算法的总复杂度为12×0(+O(bN)+2×M×O(),其 中M为备选网格数,值远小于N。 function SEARCH BY TIME( time, 该算法需要将每个网格的时间差向量等信息存储 begin 对于输入向量me选取一个阙值5,得到待查询网格在数据库中并且还要存储每个网格的SvM分类器 因此算法的空间复杂度为2×O(R),R为网格总数。随 的最大外包球形; 对于國值的选取通过多次实验得到的 着网格划分密度增大,算法的空间复杂度会明显增高 利用KD-Tree索引查询数据库得到与最大外包球形相 父的分区; 实验及结果 利用条件查询在分区中查找mime,在最大外包球形内 本文实验采用蒙特卡洛法,在闪电可能发生的区域 的网格作为备选网格 内,随机选取n个点作为闪电发生的实际位置,计算出 return查询得到的备选网格集合 Position times 该点到达各个探测站的时间差定位向量。以此作为输 nd begin 入,由上文给出的內电联合定位算法,求解出相应的网 算法3目标误差函数求值算法 格格点,作为闪电发生位置的求解值。通过测试算法平 Input时间差定位间ime,(∈{1,2,3,4}∈{1,2,3,4}<j均运行时间,平均计算误差,定位准确率来评价算法的 和格点时间差向量 tune'(i∈{,2,3,4},={1,2,3,4},i<) 复杂度和稳定性。 function Deviation(lime, time, 算法第一步需要根据时间差向量在所有网格中查 LnI 询出有限个备选网格,不需要对每一个网格进行分类判 Epp=timey time 别,降低了算法的复杂度。通过多次实验,得到在上文 给出的阈值下几种典型的搜索网格如图1所示。其中 灰色代表备选网格,黑色代表目标网格。可见,该算法 287 27.7 27.6 28.4 113.6113.7113.8113.9114.0114.1 116.31164116.5116.6116.7116.8 经度() 经度(") 33.8 31.0 33.7 30.7 33.4 30.6 118.6118.7118.8118.9119.0119.1 118.81189119.0119.11192119.3 经度 经度() 图1儿种典型的备选网格分布 曹海鹏,谢兴生,祝宝友:一种改进的网格搜索闪电定位算法 2016,52(16) 能够有效地选择出目标网格及与目标网格相近邻的几 个网格作为备选网格 为了研究不同数量的测试数据对于实验结果的影 85 响,故开始以10个点作为测试集计算出结果后,再选川 SVM+目标函数 50个点一直到500个点作为测试数据集,结束实验。得 仅SⅤM 仅目标函数 到的结果在表3中给出。 65 表3实验结果 测试平均备选单次定位定位准平均搜 点数格点数 时间/s确率(%)索误差 100200300500 272 实验点个数 0.298 92.00 图3算法准确率对比 l00 0.335 0.444 200 20.14 0.354 91.50 使用相同的测试数据对本文算法与传统网格搜索 300 18.68 513 算法和采用三级网格优化的方法进行对比,得到其单次 500 19.2 0.324 94.94 0488 平均定位时间变化曲线如图4所示。 图2给出了实验结果的图形展示 512.00 30 256.00 128.0 2( 64.00 木文算法 =32.00 传统网格搜索算法 在 三级网络优化网格搜索算法 10 5 4.00 1050100 00300 500 实验点个数 1.00 0.50 0.25 96 100 2 300 实验点个数 图4算法单次平均定位时间对比 5结東语 86 00200300500 实验表明本文讨论的闪电联合定位算法,在多维空 实验点个数 索引查找备选网格方面命中率高,能够快逑精确地匹 0.4 配到目标网格及其邻近网格,单次闪屯定位吋间较短符 回0.3 合系统实时性要求。算法的平均定位误差在600m范 ≈0.2 围之内,能够保证系统的误差要求。通过与单纯的使用 SVM或者目标函数判定闪电位置的算法对比,可以得 出将两者结合,用目标两数优化SVM分类判别结果能 50100200300500 够大大提高算法的整体准确率ε然而该算法仍然存在 实验点个数 们.6 空间占川大的问题,而且SVM训练参数选择对于分类 器分类结果影响较大,如何选取合适的参数进一步提高 0.4 SVM的分类正确率还有待进一步研究。 平 参考文献 [张义军,周秀骥雷电研究的回顾和进展门应用气象学报 200 301)50 实验点个数 2006,17(6):829-834 图2实验结果图形展示 2 Cummins K L, Murphy M J, Bardo E A, et al. A combined TOA/MDF technology upgrade of the U.s. National Lightning 使用相同的测试数据对本文算法与仅使用误差目 Detection Network[J]Journal of Geophysical Research 标函数定位和仅使用SVM定位相比较,得到其准确率 1998,103(D8):9035-90 变化曲线如图3所示。 (下转40页)

...展开详情
试读 5P 论文研究-一种改进的网格搜索闪电定位算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744270 你的留言是对我莫大的支持
2019-09-13
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-一种改进的网格搜索闪电定位算法.pdf 9积分/C币 立即下载
    1/5
    论文研究-一种改进的网格搜索闪电定位算法.pdf第1页

    试读结束, 可继续读1页

    9积分/C币 立即下载 >