法律状态公告日
法律状态信息
法律状态
2019-12-20
授权
授权
2017-06-06
实质审查的生效 IPC(主分类):G06F17/30 申请日:20161230
实质审查的生效
2017-05-10
公开
公开
技术领域
本发明属于数据挖掘领域，涉及一种基于多样性的地理空间兴趣点检索方法。
背景技术
近年来，由于移动设备(如智能手机)上全球定位系统GPS的普及，基于位置的服务(LBS)得到了学术界和工业界的广泛关注。很多基于位置的服务都得到了普及和应用，带给了用户位置相关的检索体验。
现有的LBS系统采用关键词检索的方式帮助用户从空间数据库中找到位置相关的结果。具体来说，假设空间数据库中有一组兴趣点(POI点)，其中每个POI点都包含位置信息和一定的文本信息。给定用户的位置和一组查询关键词，LBS系统返回从空间和文本上都与查询相关的POI点。但是现在大多数的LBS系统只是从数据库中直接抽取分数排名前k条的信息，为了弥补没有全面的考虑空间位置的不足，本发明提出一种对文本和空间都进行削弱的算法，使得到最终结果尽可能的包含每一个方向上。
该技术引入了元组集合(Object Summaries，缩写为OS)，它是在包含位置信息和一定的文本信息的空间数据库中生成的基于空间位置和文本的信息元组的集合。一个OS可以是以包含给定文本信息和空间位置的数据元组为根，以空间位置和文本的信息的相邻节点为它的子孙节点的树形结构。为了生成OS，一是要拥有关于查询数据主体(DataSubjects，缩写为DS)信息的关系，把这个关系简写为RDS，即是树形结构的根；另一个需要与RDS链接的关系，也就是生成RDS的子孙。对于每个RDS来说都能够形成一个DS模式图，也就是GDS。此技术是根据生成的OS来不断地进行剪枝优化最终得出重要的信息。
一个完整的OS中可能有成千上万条元组信息，将这些信息全部列举出来不但会消耗更多的时间，而且对用户在其中选取对自己来说有用的信息也是非常困难的，所以选择选取k条最有用的元组信息；对输入的自然数k，将在整个的OS中运用算法(详见步骤3.3)得到k条较全面的信息，为了避免多条相似的信息重复出现，使这k条信息能够在最大限度上呈现给用户更多样化的信息，使用户能够更全面的了解信息，本发明引入空间多样性和文本与空间所占权重两种权衡信息重要性的方法。这种方法不仅能够大大减少时间的消耗，提高返回信息的效率，而且能够满足用户对搜索信息的多样化需求，使得到的空间位置点不仅仅只偏向某一方位。
发明内容
本发明的目的在于提供一种基于多样性的地理空间兴趣点检索方法，对用户所输入的位置点或位置点与关键词的组合，运用算法得到前k个空间位置，再根据文本与空间位置所占的权重返回给用户k条最全面的信息。
为实现上述目的，本发明采用的技术方案为基于多样性的地理空间兴趣点检索方法，以期要得到前k个空间位置，方法的实现步骤如下：
步骤一：对于给定的位置点或位置点与关键词的组合进行初始化排序；
步骤1.1：收集并整理数据集，构建数据关系。这时定义有向图G(V,E)，其中V(v1,...,vn)是节点(顶点)集，这里的节点代表各类信息，E是代表边(弧)的集合，E＝{<vi,vj>|vi,vj∈V}，<vi,vj>表示从vi到vj的一条边(弧)，v1,...,vn代表有向图中的任意节点，这里n为自然数；
步骤1.2：通过以下公式来计算R中每个节点vi的分数：
DF(vi)＝[fs(vi)*ds(vi)]as*[ft(vi)*dt(vi)]at*[fg(vi)*dg(vi)]ag>
其中fs(.)，ft(.)，fg(.)分别为社会(social)参数，文本(textual)参数以及地理(geographical)参数的分数，ds(.)，dt(.)，dg(.)分别为对应的多样性分数，as、at、ag的和为1，用于控制每个参数影响。
通过以下公式来计算多样性分数：
其中ss(vi,vj)是vi和vjsocial参数的不同，使用Jaccard距离计算
综上，迭代计算出数据集中各个节点的分数，并且选择节点中分数最高的节点v0。
步骤二：根据选择的分数最高的节点所在的地理位置对其他节点进行地理空间的削弱；
步骤2.1：根据步骤一中选择的分数最高的节点对其他顶点进行关联关系的削弱的同时也进行地理空间的削弱，假设分数最高节点v0的位置点到初始位置点p的距离为d(p,v0)，初始位置点到其他节点的距离为d(p,vi)，v0到其他节点的距离为d(v0,vi)，则通过以下公式来计算地理空间值：
从公式3中可知，d(v0,vi)即v0到其他节点的距离越大，所求的地理空间值越大，说明节点vi与已选择的节点距离越大，两个节点在空间上的方向也就不同。
综上，依次计算出所选节点到其余剩余节点的地理空间值di。
步骤三：当不满足结束条件时，选择新节点；
步骤3.1：假设对关联关系削弱后的结果为a，文本所占权重为α，则剩余节点削弱后的文本值为a×α；
步骤3.2：假设对空间所占权重为β，其中α+β＝1，则剩余节点削弱后的空间值为d×β；
步骤3.3：通过以下公式来计算剩余节点对文本和空间进行削弱后的分数：
DF′(vi)＝DF(vi)×(a×α+d×β)>
综上，计算出R中剩余节点通过对文本和空间的削弱后的新的分数，再从中选出分数最高的节点。所以选出k个结果的过程为：
1.)初始化队列Hk为空，输入位置点或位置点与关键词的组合；
2.)根据输入信息，构建数据关系；
3.)计算每一个节点的分数；
4.)得到分数最高的节点加入Hk中，l＝1；
5.)当l<k时转6.)，否则转9.)；
6.)根据已所选的节点进行关联关系的削弱，并计算di值；
7.)根据文本和空间的削弱和所占权重，计算新的分数；
8.)得到分数最高的节点加入Hk中，l++，转5.)；
9.)返回队列Hk；
此时返回的Hk即所需的将要检索到的k条信息。
经实验结果证明，本方法得到的实验效果显著。
附图说明
图1为本发明方法的实施流程图。
图2为检索结果信息的空间位置示意图
具体实施方式
下面结合相关附图1-2对本发明所涉及的方法进行解释和阐述：
步骤一：对于给定的位置点或位置点与关键词的组合进行初始化排序；
根据公式(1)计算数据集各个节点的初始值。
假设给定位置点为“天安门广场”，关键词为“大学”，k＝5，根据公式计算初始分数，结果如表1所示：
表1 13个节点的初始化分数
步骤二：根据选择的分数最高的节点所在的地理位置对其他节点进行地理空间的削弱；
步骤2.1：根据步骤一中选择的分数最高的节点对其他顶点进行关联关系的削弱；
选取分数最高的节点“中央戏剧学院”，根据“中央戏剧学院”与其他节点的关联关系进行削弱，结果如表2所示。
步骤2.2：计算出各节点的空间值；
根据“天安门广场”到各节点的距离(如表3所示)和“中央戏剧学院”到剩余节点的距离(如表4所示)可以计算出各节点的空间值，其中
表2 根据“中央戏剧学院”与其他节点的关联关系削弱结果
表3 “天安门广场”到节点的距离
表4 “中央戏剧学院”到剩余节点的距离
步骤三：当不满足结束条件时，选择新节点
假设文本和空间所占的权重值α＝β＝0.5，所以根据式(1)、(2)、(3)求得新的分数，例如DF’(中央音乐学院)＝9×(0.5×0.255+0.5×0.729)＝4.428，DF’(北京财贸职业学院)＝8.7×(0.5×0.538+0.5×0.331)＝3.780结果如表5所示：
表5 选择“中央戏剧学院”节点后新的分数结果
根据表5的结果得到分数最高的节点“中国佛学院”，现在得到了两个节点“中央戏剧学院”和“中国佛学院”，因为2<k＝5，继续根据算法求得4个节点。
在选择“中国佛学院”后剩余节点的新的分数结果如表6所示：
表6 选择“中国佛学院”节点后新的分数结果
根据表6的结果得到分数最高的节点“中国协和医科大学护理学院”，剩余节点的新的分数结果如表7所示：
表7 选择“中国协和医科大学护理学院”节点后新的分数结果
根据表7的结果得到分数最高的节点“北京工业大学”，剩余节点的新的分数结果如表8所示：
表8 选择“北京工业大学”节点后新的分数结果
根据表8的结果得到分数最高的节点“中央财经大学”，现在l＝5＝k，即得到5条信息，“中央戏剧学院”，“中国佛学院”，“中国协和医科大学护理学院”，“北京工业大学”，“中央财经大学”其具体空间位置如图2所示：图2为检索结果信息的空间位置示意图。根据图2可以看出检索到的5条信息覆盖了“天安门广场”周边的各方向，没有局限某一个方向。
机译： 地理记录和兴趣点检索的关键值数据库
机译： 提供基于互联网和移动的社交/地理/促销链接促销和优惠券数据集的系统和方法，以供最终用户显示基于交互式位置的广告，基于位置的交易和优惠以及基于位置的服务，广告链接，促销，移动优惠，促销和销售的消费品，商业，政府，体育或教育相关产品，商品，游戏或服务，并与3D空间地理定位，移动映射，公司和本地信息集成在一起，以供选定的全球性地理位置以及社会购物和社交网络使用
机译： 用于解决与非地理空间域空间协调一致的基于地理空间域空间的网络标识符的方法，系统和计算机程序产品
