一种基于互联网主动迭代探测的未知位置估算方法

摘要

本发明涉及一种基于互联网主动迭代探测的未知位置估算方法。包括以下步骤：1）检查用户输入位置，若数据库查询失败，则利用网络引擎获取位置相关的网页集合；2）提取网页中的位置描述并进行分类；3）计算搜索结果的可信率

说明书

技术领域

本发明涉及一种未知位置估算方法，尤其是涉及一种基于互联网主动 迭代探测的未知位置估算方法。

背景技术

随着GPS等定位技术的不断发展和完善，基于位置的服务LBS （Location-Based Service）的应用领域不断扩充，例如各种电子地图服 务平台（百度地图、谷歌地图、Bing地图等）、旅游信息查询系统、日常生 活兴趣点查询系统、交通查询系统、社交网络等。这些位置服务平台或系 统提供位置信息查询的方法主要有两种：一种是利用GPS定位、地图操作 等获取较为精确的位置坐标进行查询；另一种是利用自然语言位置描述进 行查询，这种定性或者半定量的位置描述存在多种不确定度，但是比较符 合人类的表达习惯和认知。面向自然语言位置查询，位置数据库需要存储 位置名称与地理范围之间的映射关系，而现有位置数据库由于建设成本高、 耗时长、规模受限、更新困难等原因，难以存储所有的位置名称，而是主 要集中于主要地名、地址、显著性POI等重要位置的采集与保存。因此， 对生活中数量庞大、显著性小、重要性相对较低的位置进行查询变得无法 实现，从而与全方位、多层次、多粒度的位置服务需求相矛盾。（参考文献： 古静,基于位置的信息服务应用系统研究与开发[D].西安电子科技大学, 2004;夏保国,基于GIS的武汉市旅游信息查询系统的设计与实现[D].华 中科技大学,2006;高威斯,基于位置的服务与城市交通导航系统的设计 [D].云南大学,2011;杨煜尧等,一种基于地理位置信息的移动互联网社 交模型[J].计算机研究与发展,2011;）

互联网作为大型知识库提供了丰富的地理知识，可以作为位置服务的扩 展数据源。网络搜索的位置参考信息，需要利用自然语言理解从大量文本 信息中提取位置描述。自然语言理解是能够实现人与计算机之间用自然语 言进行有效通信的各种理论和方法，位置描述的自然语言理解主要是对位 置名称和位置关系的识别。关于位置名称的识别，已有研究侧重于提取地 理命名实体或地名，主要有两种方法：一种是基于规则的方法，建立地理 命名实体或地名的语料库和构造规则，采用规则匹配的方式进行识别，这 种方法对概念构造规则要求严格，能够提高抽取结果的准确率，但是使查 全率下降很多，难以解决模糊位置和新位置识别的问题；另一种是基于统 计的方法，由于不考虑句法、语义上的信息，不可避免地对一些低频数语 的获取和邻接高频词引入的噪声上存在一些问题。关于位置关系的识别， 已有研究主要侧重于提取基本空间关系（拓扑关系、度量关系、方位关系 等），主要有两种方法：一种是基于语句分析的方法，这种方法需要彻底理 解句法结构以及句子语义，存在脆弱性和多歧义问题；一种是基于模式的 方法，可以避免对语句进行彻底分析，但是由于自然语言表达的丰富性， 同一信息存在多种表达方式，会使模式的数量急剧膨胀。（参考文献：乐小 虬等,基于空间语义角色的自然语言空间概念提取[J].武汉大学学报·信 息科学版,2005;姜琳等,地理实体概念及其位置关系的获取和验证[J]. 计算机科学,2007;李丽双等,基于支持向量机的中文文本中地名识别[J]. 大连理工学报,2007;李晗静,基于自然语言处理的空间概念建模研究[D]. 哈尔滨工业大学,2007;李玉森,面向GIS的地理命名实体识别研究[J].重 庆邮电大学学报(自然科学版),2008;马龙,基于条件随机域模型的中文 地名识别的研究[D].大连理工大学,2009;唐旭日等,基于篇章的中文地 名识别研究[J].中文信息学报,2010;蒋文明，面向中文文本的空间方位 关系抽取方法研究[D].南京师范大学,2010;申琪君,中文文本空间关系 标注方法研究[D].南京师范大学,2010;张雪英等,基于规则的中文地址 要素解析方法[J].地球信息科学学报,2010;李海光,基于位置和语义特 征的中文命名实体关系抽取研究[D].合肥工业大学,2011;杜萍等,中文 地名识别与歧义消除——以中国县级以上行政区划地名为例[J].遥感技术 与应用,2011.）

位置数据库存在规模受限、更新困难的问题，基于位置数据库的地理 位置信息查询（尤其是模糊位置查询）会出现位置名称难以识别或者覆盖 范围缺失的情况，不足以满足用户需求。互联网中蕴含了丰富的地理知识， 能够提供大量感兴趣位置的描述信息用于估算“未知”位置覆盖范围。而 如何从互联网中搜索位置相关的信息，并从中获取“未知”位置的近似地 理范围，是本发明的主要工作。

发明内容

本发明主要是解决现有技术所存在的技术问题；提供了一种能够充分 利用互联网中数量丰富、动态变化的地理知识资源，实现对目标位置的近 似范围估算。

本发明的上述技术问题主要是通过下述技术方案得以解决的：

一种基于互联网主动迭代探测的未知位置估算方法，其特征在于，包括 以下步骤：

步骤1，检查用户输入位置查询词；若位置无法从空间数据库获取地理 覆盖，则主动开始互联网迭代探测，即以目标位置为主题利用网络搜索引 擎从互联网爬取目标位置相关信息；

步骤2，以位置查询词为主题进行初始探测，利用网络引擎从互联网中 获取包含目标位置描述的网页集合；

步骤3，针对步骤2得到的目标位置描述的网络文档进行地理位置解析， 即从网络文档中提取自然语言位置描述，所述自然语言位置描述包括参考 位置和空间关系；

步骤4，采用步骤3得到的自然语言位置描述进行位置描述分类；如果 位置描述的参考位置能够从位置数据库获取地理覆盖，位置描述存入精确 描述集合P，否则存入模糊描述集合A；

步骤5，评估当前搜索可信率C_s；若C_s小于搜索可信阈值C_min，以模糊描 述集合A中的参考位置为主题进行新一轮互联网文本搜索;若Cs大于或者等 于搜索可信阈值C_min，则跳至步骤7；

步骤6，重复步骤1至步骤5，直至每轮搜索结果可信率满足阈值或者 达到搜索次数限制为止；

步骤7，计算所有位置描述的近似地理范围及其可信度；

步骤8，集成和提炼多个位置描述地理覆盖，获取目标位置的地理范围；

在上述的一种基于互联网主动迭代探测的未知位置估算方法所述步骤 3中，自然语言位置描述识别主要包括位置名称识别和空间关系的识别，采 用基于语义的多尺度提取方法抽取自然语言位置描述，具体包括以下子步 骤：

步骤3.1，建立位置描述的语料库，语料库中存储表达位置名称和空间 关系的特征词汇以及位置描述的句法模式；这里，建立语料库可以通过人 工归纳和机器学习的方式建立。

步骤3.2，在语料库的支持下，对网络文本进行模式匹配，获取位置描 述；

步骤3.3，基于地理的和非地理的语义消除地名歧义。

在上述的一种基于互联网主动迭代探测的未知位置估算方法所述的步 骤4中，利用参考位置和空间关系估算目标位置的前提是参考位置能够从 位置数据库中获取精确的地理范围，设定单个位置描述按照式一进行表达， RO为参考位置名称，SR为位置空间关系，T为位置描述的发生时间，C为位 置描述具有的可信度，S为参考对象RO的搜索参考；抽取结果中前K个位置 描述Loc_i，并依据前提条件进行分类，当Loc_i.RO满足前提条件时，Loc_i存入 精确描述集合P，否则存入模糊描述集合A；

Loc＝{RO，SR，T，C，S}  式一

在上述的一种基于互联网主动迭代探测的未知位置估算方法所述的步 骤5，评估当前搜索可信率C_s的具体方法是：定义搜索可信率C_s作为评价指 标，搜索可信率是P中所有位置描述的可信度之和与位置描述总数之比，如 式二所示，m是P中位置描述个数，K是位置描述总数，Loc_i.C是某个位置描 述的可信度。

$C_s=\frac{\underset{i=0}{\overset{m-1}{\Sigma }}{\mathrm{Loc}}_i.C}{K}$式二

位置描述的可信度按照式三进行计算，其中ε是衰减参数，n是搜索 次数，设定位置描述可信度在首次搜索时为1，并随着搜索次数的增加而衰 减；

Loc_i.C=1*(ε)ⁿ    式三

当C_s满足最低可信阈值C_min时，直接输出精确描述集合P进行目标位置估 算；当C_s不满足条件时，采用基于互联网多次迭代搜索的方法来保证搜索可 信率，即取A中的模糊参考位置进行新一轮互联网搜索，通过网络资源先估 算参考位置地理范围，进而利用参考位置估算目标位置。

在上述的一种基于互联网主动迭代探测的未知位置估算方法所述的步 骤6即为模糊参考位置迭代搜索；依据步骤4和步骤5的处理，设定搜索 结果采用式四表达，n是搜索次数，m是当次搜索的位置序号,P是精确描述 集合，A是模糊描述集合，C_s是搜索可信率。

WS[n][m]={P，A，C_s}     式四

所述的迭代搜索过程包括以下子步骤：

步骤6.1，将目标位置搜索结果的模糊位置描述WS[0][0].A存入搜索 集合Ｑ，设n=0，m=0；

步骤6.2，取Q中模糊描述集合WS[n][m].A，判断n+1是否达到搜索 次数限制，如果是则退出搜索；

步骤6.3，依次取WS[n][m].A中位置描述Loc_i进行第n+1次搜索，获取 搜索结果WS[n+1][i]，并关联到位置描述的参考对象RO搜索引用，即 Loc_i.S＝WS[n+1][i]；

步骤6.4，从Q中去掉完成搜索的模糊描述集合WS[n][m].A，检查

WS[n+1][i].C_s是否满足阈值C_min，若不满足则将WS[n+1][i].A放入搜 索集合Q中；

步骤6.5，检查Q中是否存在模糊描述集合，如果有则重复步骤6.2至 步骤6.4进行迭代搜索。

在上述的一种基于互联网主动迭代探测的未知位置估算方法所述的步 骤7，由于第k搜索结果的模糊位置描述需要参考第k+1次搜索结果，采用 逆序计算的方式，即从最后一次搜索开始进行地理范围计算，具体包括以 下子步骤：

步骤7.1，定义搜索结果WS中搜索次数为n，第n次搜索位置个数为m， m=WS[n-1].size；定义地理范围集合FC存储每次搜索结果的地理范围；

步骤7.2，取第n次搜索第m个位置的搜索结果WS[n-1][m-1]；

步骤7.3，依次取WS[n-1][m-1].P中的位置Loc_y，基于位置数据库查 询参考位置坐标，利用Point-Radius算法计算地理覆盖FP(y)及其可信度 CP(y);

步骤7.4，依次取WS[n-1][m-1].A中的位置Loc_x,利用Loc_x.S在地理 范围集合FC中查询参考位置坐标，若成功获取坐标，则利用Point-Radius 算法计算地理覆盖FA(y)及其可信度CA(y);

步骤7.5，融合P和A中所有位置的地理范围，获取当次搜索结果的地 理范围FC(WS[n-1][m-1]);

步骤7.6，判断m-1是否大于0；若大于0，则进行下一个搜索结果的 位置计算，令m=m-1，跳至步骤b）；若小于或等于0，则进行下一步；

步骤7.7，判断n-1是否大于0；若大于0，则进行前一次搜索结果的 位置计算，令n=n-1，m=WS[n-1].size，跳至步骤b）；若小于或等于0， 则进行下一步；

步骤7.8，输出FC(WS[0][0])。

因此，本发明具有如下优点：能够充分利用互联网中数量丰富、动态 变化的地理知识资源，实现对目标位置的近似范围估算。由于互联网中位 置信息与非位置信息关联复杂，并且信息表达形式多样化，本发明针对互 联网中的自然语言文本信息，采用基于语义的多尺度提取方法从网页文本 中抽取位置描述，并利用Point-Radius算法计算目标位置的近似地理范 围。。

附图说明

图1是互联网主动搜索方法的流程图。

图2基于互联网搜索结果的位置计算的流程图。

具体实施方式

下面通过实施例，并结合附图，对本发明的技术方案作进一步具体的 说明。

实施例：

1、理论基础。

1.1、地理信息检索（Geographic Information Retrieval，GIR）。

地理信息检索是根据地理查询范围的限制，返回与地理信息查询相关 的文档。基本思路是利用网络爬虫从互联网上搜索网页集合，通过命名实 体识别与分类以及语法分析识别网页中的地名，从而确定查询词和文档的 地理范围，最后计算文档与查询词之间的关联度（包括文本关联和空间关 联）返回和排序检索结果。目前大部分地理信息检索主要是采用关键词匹 配算法，检索词和网络文档中的地名都需要具有明确地理覆盖范围进行关 联技术，这种方式难以适应模糊地名（例如长江中下游）的情况，因而无 法直接用于基于网络搜索的未知位置估算。本发明参考地理信息检索的思 路，提出了一种多尺度的迭代搜索算法（如图1），基于互联网获取未知位 置相关的网络文档，并提取包含未知位置的位置描述，进而利用位置描述 中的参考位置和空间关系计算出未知位置的近似地理范围。主要流程是通 过元搜索从互联网上获取网页集合后，基于语义提取网页中的包含查询词 的位置描述，如果位置描述不满足可信率进行查询词位置估算，则对识别 的模糊位置进行新一轮的互联网检索，这个过程是一个迭代的过程，只要 可信率条件不满足或者没有达到搜索限制，就不断进行网络搜索获取能够 估算模糊位置地理范围的参考信息。

1.2、位置描述地理配准（Georeferencing Locality Descriptions， GLD）。

位置描述地理配准是将位置从文本描述转换成某个坐标系统下的 数值描述。理想的位置描述地理配准过程是将文本描述转成数字描述能 够并映射到地图上，并且表达位置的空间范围以及位置分布的不确定 度，目前比较流行的算法是Point-Radius算法和Probability算法。 Point-Radius方法利用一个点以及最大误差来描述位置及其不确定度， 主要考虑的不确定度来源包括参考位置（参考位置的空间范围、大地基 准、坐标精度、地图比例尺）和空间关系（距离关系不确定度以及方向 关系的不确定度），所有不确定度度量投影到一个维度作为目标位置的 最大误差，以点和最大误差作为半径构成的圆形区域表达目标位置。 Probability方法采用不确定度概率密度表面来表达目标位置及其不确 定度，主要考虑不确定度来源包括目标对象的空间分布、空间关系的不 精确和模糊性、参考对象的不完整性、以及位置描述本身的不确定度。 Point-Radius方法属于量化方式的位置计算，能够获取目标位置所有 可能存在点的地理覆盖，适用于半定量的文本位置描述；Probability 方法无法定量计算目标位置的地理覆盖，但是能够给出目标位置的概率 分布，适用于定性的文本位置描述。

2、实现过程。

（1）、检查用户输入目标位置查询词；在位置数据库中搜索查询词， 如果位置不存在或者位置地理覆盖缺失，则主动进行基于网络搜索模式的 查询，即以目标位置为主题利用网络搜索引擎从互联网爬取目标位置相关 信息；

（2）、识别和提取网络文档中的自然语言位置描述（包括参考位置和 空间关系）；自然语言位置描述识别主要包括位置名称识别和空间关系的识 别，本发明采用基于语义的多尺度提取方法抽取自然语言位置描述。首先， 通过人工归纳和机器学习的方式建立位置描述的语料库，语料库中存储表 达位置名称和空间关系的特征词汇以及位置描述的句法模式；然后，在语 料库的支持下，对网络文本进行模式匹配，获取位置描述；最后，基于地 理的和非地理的语义消除地名歧义；

（3）、位置描述分类；利用参考位置和空间关系估算目标位置的前提 是参考位置能够从位置数据库中获取精确的地理范围，设定单个位置描述 按照公式（1）进行表达，RO为参考位置名称，SR为位置空间关系，T为位 置描述的发生时间，C为位置描述具有的可信度，S为参考对象RO的搜索参 考。抽取结果中前K个位置描述Loc_i，并依据前提条件进行分类，当Loc_i.RO 满足前提条件时，Loc_i存入精确描述集合P，否则存入模糊描述集合A；

Loc＝{RO，SR，T，C，S}     （1）

（4）、计算搜索可信率C_s；搜索结果中位置描述的可信度必须达到一定 水平才能用于估算目标位置，本发明提出搜索可信率C_s作为评价指标，搜索 可信率是P中所有位置描述的可信度之和与位置描述总数之比，如公式（2） 所示，m是P中位置描述个数，K是位置描述总数，Loc_i.C是某个位置描述的 可信度。

$C_s=\frac{\underset{i=0}{\overset{m-1}{\Sigma }}{\mathrm{Loc}}_i.C}{K}---\left(2\right)$

位置描述的可信度按照公式（3）进行计算，其中ε是衰减参数，n是 搜索次数，设定位置描述可信度在首次搜索时为1，并随着搜索次数的增加 而衰减。

Loc_i.C=1*(ε)ⁿ    （3）

当C_s满足最低可信阈值C_min时，直接输出精确描述集合P进行目标位置估 算；当C_s不满足条件时，本发明采用基于互联网多次迭代搜索的方法来保证 搜索可信率，即取A中的模糊参考位置进行新一轮互联网搜索，通过网络资 源先估算参考位置地理范围，进而利用参考位置估算目标位置；

（5）、模糊参考位置迭代搜索；依据步骤三和步骤四的处理，设定搜 索结果采用公式（4）表达，n是搜索次数，m是当次搜索的位置序号,P是 精确描述集合，A是模糊描述集合，C_s是搜索可信率。

WS[n][m]={P，A，C_s}    （4）

迭代搜索过程如下：

a）.将目标位置搜索结果的模糊位置描述WS[0][0].A存入搜索集合Ｑ， 设n=0，m=0；

b）.取Q中模糊描述集合WS[n][m].A，判断n+1是否达到搜索次数限 制，如果是则退出搜索；

c）.依次取WS[n][m].A中位置描述Loc_i进行第n+1次搜索，获取搜索 结果WS[n+1][i]，并关联到位置描述的参考对象RO搜索引用，即 Loc_i.S＝WS[n+1][i]；

d）.从Q中去掉完成搜索的模糊描述集合WS[n][m].A，检查

WS[n+1][i].C_s是否满足阈值C_min，若不满足则将WS[n+1][i].A放入 搜索集合Q中；

e）.检查Q中是否存在模糊描述集合，如果有则重复步骤b)至步骤d) 进行迭代搜索；

（6）、计算所有位置描述的近似地理范围及其可信度；由于第k搜索 结果的模糊位置描述需要参考第k+1次搜索结果，因此本发明采用逆序计 算的方式，即从最后一次搜索开始进行地理范围计算。如图2所示，计算 过程如下：

a）.定义搜索结果WS中搜索次数为n，第n次搜索位置个数为m，

m=WS[n-1].size；定义地理范围集合FC存储每次搜索结果的地理范 围；

b）.取第n次搜索第m个位置的搜索结果WS[n-1][m-1]；

c）.依次取WS[n-1][m-1].P中的位置Loc_y，基于位置数据库查询参考 位置坐标，利用Point-Radius算法计算地理覆盖FP(y)及其可信度CP(y);

d）.依次取WS[n-1][m-1].A中的位置Loc_x,利用Loc_x.S在地理范围集 合FC中查询参考位置坐标，若成功获取坐标，则利用Point-Radius算法计 算地理覆盖FA(y)及其可信度CA(y);

e）.融合P和A中所有位置的地理范围，获取当次搜索结果的地理范 围FC(WS[n-1][m-1]);

f）.判断m-1是否大于0；若大于0，则进行下一个搜索结果的位置 计算，令m=m-1，跳至步骤b）；若小于或等于0，则进行下一步；

g）.判断n-1是否大于0；若大于0，则进行前一次搜索结果的位置 计算，令n=n-1，m=WS[n-1].size，跳至步骤b）；若小于或等于0，则 进行下一步；

h）.输出FC(WS[0][0])；

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明 所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或 补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权 利要求书所定义的范围。