基于“兴趣集群”的空间网络最优位置的选择与查询研究

陈 伟，刘 佳，刘 琳

(1.中国环境管理干部学院，河北 秦皇岛 066004；2.秦皇岛职业技术学院，河北 秦皇岛 066004)

基于“兴趣集群”的空间网络最优位置的选择与查询研究

陈 伟1，刘 佳1，刘 琳2

(1.中国环境管理干部学院，河北 秦皇岛 066004；2.秦皇岛职业技术学院，河北 秦皇岛 066004)

针对空间网络的查询选择单一性和忽略了群集效应的缺陷，本文提出基于兴趣集群的最优位置查询方法，给出了该方法的实施策略，通过选取合理“兴趣集”，研究“兴趣集群”的查询，使得最终查询结果满足集合内部的兴趣点是高密度、集合与集合之间低耦合，降低数据重复率，从而保证查询结果的有效性，提高用户的满意度和资源的合理调配。

空间网络；兴趣集；最优位置

The Research on the Choice of the Optimal Location and Query for Spatial Network Based on the "Interest Cluster"

1.问题提出

目前，路网上的研究大多基于距离量算，如：欧氏距离和路网距离。目标对象多数集中在“点对象上”，最常见的应用主要有两种：

(1)最近目标点的查找，即要查找距离给定位置最近的加油站、救援厂、急救中心等，已有的研究成果是直接计算最短路径，查找到最近的一个。

(2)最佳位置的查找，如某一连锁店要选择最佳位置增开店铺以扩大连锁范围，已有的研究成果也是通过最短路径量算，并结合对周边同类型店铺的距离的分析来选择最佳位置。

这两种应用查找结果理论上是正确的，但由于忽视了应用中除去距离以外的其它影响因素，使得查找结果不尽人意，主要问题如下：

(1)选择的单一性：只靠距离测算，忽略其它影响因素，使结果失去了有效性。比如，逛街的时候，确定了最近的商场，可是其他商场可能都很远，而逛街往往是需要商场群体，这样下一个又要重新规划，只有第一个距离近了，而其综合距离却不一定近。

(2)忽视了群集效应：物以类聚，人以群分，任何同类事物的聚集都能产生单个点所不能创造的价值，这也给“选址分析”提供了一个重要的依据。例如：建新商场，如果是单独的一个地方，周边不是商业区，那么效益可想而知，因为不符合人们消费的习惯。

所以，本文以上述问题为出发点，提出“兴趣集群”的选择，根据查询条件，查找符合条件的“兴趣集”，进而组成集群，由用户根据需要自行选择一个“兴趣集”做起点，进一步访问“兴趣集群”。这种方式不仅能够解决目前路网查询的单一性，还具有以下两方面意义：

(1)将“点查询”与“面查询”联系到一起，为交通、资源等方面的规划、分析及综合价值计算等实际应用提供理论依据。

(2)对查询结果进行了合理性优化，使其在一些应用(如：大型商场、娱乐、餐饮等行业)中可以得到合理有效的查询结果，以提高应用价值。

2.国内外研究现状

目前，国内外关于路网信息检索及其应用主要有最近邻查询、最优位置查询、轨迹相似性查询等。

(1)最近邻查询：最近邻(Nearest Neighbors，NN)查询是计算数学中的一个传统问题，根据实际需要，通常查找一个或多个最近的目标点，以下简称(K-NearestNeighbor查询)KNN，它是典型的相似性查询方式。KNN查询方法最经典的算法是Dijktra算法，大多数的研究均是以Dijktra算法为基础，在其上优化和改进，但是当路网的数据量巨大时会造成查询和存储的代价很高以致方法不可用。

(2)最优位置查询：最优位置亦称最佳位置(Optimal Locations，OL)查询，是对空间信息资源的合理规划，在地理信息系统、城市规划和资源分配等领域均得到广泛的应用，该应用已经从欧式空间过渡到路网中，通过计算综合评价值，查找最优位置。OL查询通常会假设查询目标存在Lp空间中，未考虑空间位置之间的活动常受其实际路网情况的约束，若仍取两个位置点之间的距离是Lp空间距离，会使查询结果降低相应的实用价值。

(3)轨迹相似性查询：轨迹相似性查询是道路网络中移动对象数据管理的研究热点，它根据收集到的移动对象数据，分析移动对象的运动规律、检测异常对象。例如：它可以预测犯罪分子的逃匿轨迹，然后派遣附近警力支援。

轨迹相似性查询，也是轨迹数据应用场景中(包括拼车出行服务、行程分享与推荐服务等)的关键性技术。在实际应用中，可以根据轨迹的相似程度作出相应的决策及推荐。例如：拼车、推荐可能喜欢去的地方等。

由上述分析可知，当前的路网信息查询无论是基于欧式距离还是路径距离，求得最短路径或多个近邻，均集中在研究“点对象”中，无论是静止的，或者是移动的。但随着路网信息的增加、应用的不断深入，人们获取的信息中，一部分是需要针对“面对象”的，要从“面对象”中选择符合条件的“点对象”，所以查询结果除了满足距离最短以外，还要考虑信息应用价值和意义。

3.基于“兴趣集群”的查询方法研究

3.1 查询策略

本文主要讨论目前路网应用中的一种特殊情况，即“集群处理”。当某个查询要得到的结果是一个“面”的时候，这种“集群处理”的有效性和准确性，将直接影响是否能给用户返回的是一系列的由“点到面”的有效结果。查询方法完全可以借鉴“点对象”查询的处理，只是需要进行多个“点对象”的分组、融合，形成面、群。其查询步骤如下：

(1)评价选择的目标点

所谓目标点就是符合查询条件的结果，单个结果称之为“点对象”，多个结果组成的结果集称之为“面对象”。根据查询条件查出多个“点对象”组成的目标集合，分析相似性，根据相似性指标的大小进行分组、融合。

(2)确定相似性指标

对于选定的“点对象”组合，根据路网数据查询原理，分析其属性数据，将属性数据进行查询组合，组成相似性条件，确定满足条件的点，重新生成新的“面对象”。

(3)建立排序机制

即便是多个离散的点组成的区域，由于各个离散点的属性数据不同，所以需要对其进行分析并排序，进而能够规划出区域内部以及区域之间的最优路径。

(4)确定“面对象”中的“点集”之间的关系、“面对象”间的关联关系

由于“面对象”是由“点对象”组成的，所以“面对象”中的关系就是“点”与“点”之间的关系，根据他们的关系，进而能规划出一条行走最优路径。“面对象”间的关系亦如此，只不过是需要综合计算面内所有点的信息，再规划面—面之间的路径。

(5)建立索引结构

对于大数据的查询，没有索引几乎是完不成的。所以，根据实际应用领域数据的特点，建立索引，以便加快查询速度，提高查询效率。

3.2 查询合理性保证

为了实现查询的合理性，查询条件由传统单一选项增加到复合选项，用户可以根据选择增加，或不增加。条件精确度越高，查询结果越理想。本文提出“点查询—面查询—区域查询”，具体可分为两步执行：

(1)确定目标点的属性数据集，选择核心查询条件，确定查询符合条件的“点对象”。

(2)以某一个“点对象”为中心，按照一定的规则向外延伸，再查询条件范围内，圈住符合条件的所有“点对象”，组合成新的“面对象”，即“区域”。

(3)区域可以是一个，也可以是多个，要根据具体“点集”的位置来定，而区域内及区域间均可以根据条件形成最优路径。

(4)建立查询模型。

3.3 结果集的处理与评价

结果集的大小由查询条件、查询目标等多种因素决定，无论其大、小，均需要对其生成的集合进行处理与评价，以确保返回给用户最有效的结果。

(1)根据用户查询的具体应用背景，赋予KNN和OL不同的比重，取值在0～1之间，两个比重和等于1。

(2)将查询点及目标点获取的指标数据，按照其赋予的权值进行整合，设定计算公式，再根据KNN和OL不同的比重值进行组合计算。

4.结论

本文提出的基于兴趣集群的最优位置查询策略，从用户的实际应用出发，对兴趣点进行了分析和综合，由“点对象”扩展到“面对象”，使原来单一的查询结果更加贴近实际需求。考虑了“兴趣集群”的最佳位置及路径查询使空间网络上的查询变得更加合理化、智能化、个性化和人性化，提高了用户的满意度，使得资源的调配更加合理。

[1]Deng, K., Zhou, X., Shen, H.T., Sadiq, S., Li, X.: Instance optimal query processing in spatial networks 18(3), 675-693 (2009)

[2]Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network databases. In: Proc. of Very Large Data Bases,(VLDB), pp. 802-813 (2003)

[3]Gu Y, Guo N, Yu G. Uncertain moving range query techniques in road networks[J]. Ruan Jian Xue Bao/ Journal of Software, 2013,24(6):1243 1262.

[4]李艳红，黄群，蒋宏，李国徽.路网中空间关键字连续范围查询算法研究，计算机科学，2014，41(7)

CHEN Wei1，LIU Jia1，LIU Lin2

(1. Environmental Management College of China, Qinhuangdao 066004, China;2. Qinhuangdao Institute of Technology, Qinhuangdao 066004, China)

Aiming at the monotony and the defects of cluster effect of spatial network query, an optimal location query method based on interest cluster is proposed in this paper, and then the implementation strategy is also given. By choosing reasonable interest cluster, the query of interest cluster is studied. Therefore, the final query result can meet the conditions that the point of interest in cluster is high-density, but the clusters are low coupling. Thus, the repetition rate of data is decreased, and validity of query result is guaranteed. So the user satisfaction is increased, and resources are allocated reasonably.

spatial network; interest cluster; optimal position

2015-10-08

河北省教育厅青年基金项目(基于空间网络的“兴趣集群”的最优选择查询研究，QN2015133)。

河北省教育厅青年基金项目(基于“路网数据库”的最佳位置及路径选择研究，QN20141059)。

陈伟(1980-)，女，在读博士，中国环境管理干部学院信息工程系副教授，研究方向：数据库查询技术。

TP333

A

1671-3974(2016)01-0052-03