第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0L:10.11992tis.201903033 空间关键字个性化语义近似查询方法 李盼，张霄雁，孟祥福，赵路路，齐雪月 (辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛125105) 摘要：现有的空间关键字查询处理模式大都仅支持位置相近和文本相似匹配，但不能将语义相近但形式上不 匹配的对象提供给用户：并且，当前的空间-文本索引结构也不能对空间对象中的数值属性进行处理。针对上 述问题，本文提出了一种支持语义近似查询的空间关键字查询方法。首先，利用词嵌入技术对用户原始查询进 行扩展，生成一系列与原始查询关键字语义相关的查询关键字：然后，提出了一种能够同时支持文本和语义匹 配，并利用Skyline方法对数值属性进行处理的混合索引结构AIR-Tree:最后，利用AIR-Tree进行查询匹配，返 回to-k个与查询条件最为相关的有序空间对象。实验分析和结果表明，与现有同类方法相比，本文方法具有 较高的执行效率和较好的用户满意度；基于AIR-Tree索引的查询效率较IRS-Tree索引提高了3.6%.在查询结 果准确率上较IR-Tree和IRS-Tree索引分别提高了10.14%和16.15%。 关键词：空间关键字查询：词嵌入：语义近似查询：文本；数值属性：索引结构：查询匹配 中图分类号：TP311文献标志码：A文章编号：1673-4785(2020)06-1163-12 中文引用格式：李盼，张霄雁，孟样福，等.空间关键字个性化语义近似查询方法从.智能系统学报，2020,15(6)：1163-1174. 英文引用格式：LI Pan,.ZHANG Xiaoyan,.MENG Xiangfu,etal.Spatial keyword personalized and semantic approximate query approachJ CAAI transactions on intelligent systems,2020,15(6):1163-1174. Spatial keyword personalized and semantic approximate query approach LI Pan,ZHANG Xiaoyan,MENG Xiangfu,ZHAO Lulu,QI Xueyue (School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China) Abstract:Most spatial keyword query processing models only support the location proximity and text similarity match- ing.However,in terms of text information processing,spatial objects with similar semantics but mismatched forms can- not be filtered out and provided to query users.Furthermore,the current spatial-text index structure cannot process the numerical attributes.To solve the above problem,this paper proposes a spatial keyword query method that can support the semantic approximate query processing.Word embedding technology is used to expand the users'original queries and generate a series of query keywords semantically related to the original query keywords.Then,a hybrid index struc- ture AlR-tree that can support text and semantic matching and use the Skyline method to process numerical attributes is proposed.Finally,AIR-tree is used for query matching to return the top-k ordered spatial objects most closely related to the query conditions.Experimental analysis and results show that compared with similar methods,this method has a higher execution efficiency and better user satisfaction.The query efficiency based on the AIR-tree index is 3.6%high- er than that of the IRS-tree index.In terms of accuracy,IR-tree and IRS-tree are increased by 10.14%and 16.15%,re- spectively,compared with AIR-tree. Keywords:spatial keyword query;word embedding;semantic approximate query;text;numerical attribute;index struc- ture;query matching 移动网络的普遍应用和空间Web对象的大 range query)和top-kk近邻查询(top-k kNN query), 量出现，使得空间关键字查询成为LBS(location- 这两类查询处理模式主要是根据空间对象与空间 based system)的重要支撑技术。现有的空间关键 关键字查询之间的文本相似度和位置相近度构建 字查询处理模式主要有top-k范围查询(top-k 结果评分函数，进而利用文本和空间混合索引技 术提高查询效率。现有的空间数据和文本信息相 收稿日期：2019-03-25 基金项目：国家自然科学基金面上项目(61772249). 混合的空间-文本索引技术主要有R-Tree、IR2 通信作者：孟祥福.E-mail:marxi(@I26.com Tree、QuadTree、R*.Tree、S2i等；文本搜索
DOI: 10.11992/tis.201903033 空间关键字个性化语义近似查询方法 李盼，张霄雁，孟祥福，赵路路，齐雪月 （辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105） 摘 要：现有的空间关键字查询处理模式大都仅支持位置相近和文本相似匹配，但不能将语义相近但形式上不 匹配的对象提供给用户；并且，当前的空间−文本索引结构也不能对空间对象中的数值属性进行处理。针对上 述问题，本文提出了一种支持语义近似查询的空间关键字查询方法。首先，利用词嵌入技术对用户原始查询进 行扩展，生成一系列与原始查询关键字语义相关的查询关键字；然后，提出了一种能够同时支持文本和语义匹 配，并利用 Skyline 方法对数值属性进行处理的混合索引结构 AIR-Tree；最后，利用 AIR-Tree 进行查询匹配，返 回 top-k 个与查询条件最为相关的有序空间对象。实验分析和结果表明，与现有同类方法相比，本文方法具有 较高的执行效率和较好的用户满意度；基于 AIR-Tree 索引的查询效率较 IRS-Tree 索引提高了 3.6%，在查询结 果准确率上较 IR-Tree 和 IRS-Tree 索引分别提高了 10.14% 和 16.15%。 关键词：空间关键字查询；词嵌入；语义近似查询；文本；数值属性；索引结构；查询匹配 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2020)06−1163−12 中文引用格式：李盼, 张霄雁, 孟祥福, 等. 空间关键字个性化语义近似查询方法 [J]. 智能系统学报, 2020, 15(6): 1163–1174. 英文引用格式：LI Pan, ZHANG Xiaoyan, MENG Xiangfu, et al. Spatial keyword personalized and semantic approximate query approach[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1163–1174. Spatial keyword personalized and semantic approximate query approach LI Pan，ZHANG Xiaoyan，MENG Xiangfu，ZHAO Lulu，QI Xueyue (School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China) Abstract: Most spatial keyword query processing models only support the location proximity and text similarity matching. However, in terms of text information processing, spatial objects with similar semantics but mismatched forms cannot be filtered out and provided to query users. Furthermore, the current spatial-text index structure cannot process the numerical attributes. To solve the above problem, this paper proposes a spatial keyword query method that can support the semantic approximate query processing. Word embedding technology is used to expand the users’ original queries and generate a series of query keywords semantically related to the original query keywords. Then, a hybrid index structure AIR-tree that can support text and semantic matching and use the Skyline method to process numerical attributes is proposed. Finally, AIR-tree is used for query matching to return the top-k ordered spatial objects most closely related to the query conditions. Experimental analysis and results show that compared with similar methods, this method has a higher execution efficiency and better user satisfaction. The query efficiency based on the AIR-tree index is 3.6% higher than that of the IRS-tree index. In terms of accuracy, IR-tree and IRS-tree are increased by 10.14% and 16.15%, respectively, compared with AIR-tree. Keywords: spatial keyword query; word embedding; semantic approximate query; text; numerical attribute; index structure; query matching 移动网络的普遍应用和空间 Web 对象的大 量出现，使得空间关键字查询成为 LBS(locationbased system) 的重要支撑技术。现有的空间关键 字查询处理模式主要有 top-k 范围查询 (top-k range query) 和 top-k k 近邻查询 (top-k kNN query)， 这两类查询处理模式主要是根据空间对象与空间 关键字查询之间的文本相似度和位置相近度构建 结果评分函数，进而利用文本和空间混合索引技 术提高查询效率。现有的空间数据和文本信息相 混合的空间−文本索引技术主要有 IR-Tree[1] 、IR2 - Tree[2] 、QuadTree[3] 、R*-Tree[4] 、S2I[5] 等；文本搜索 收稿日期：2019−03−25. 基金项目：国家自然科学基金面上项目 (61772249). 通信作者：孟祥福. E-mail：marxi@126.com. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020
·1164· 智能系统学报 第15卷 的索引技术主要有倒排文件(inverted file)、签名 1相关工作 文件(signature file)和位图索引(bitmap)等。上述 文本索引以及空间-文本索引主要适用于查询关 随着移动网络的普遍应用，网络上出现了越 键字的严格形式匹配，但由于现实中文本表达形 来越多的空间Web对象(spatial web object)。一个 式多样，如果采用关键字严格形式匹配，可能导 空间对象通常包含位置信息（如经纬度）、文本信 致返回的查询结果太少或没有结果。针对上述问 息（如空间对象的名称、设施、类别等）以及数值 题，相关研究如文献[6-8]中提出了一些新的索引 信息（如价格、用户评分等），数值信息有时也归为 技术以处理文本中的拼写错误，然而这些方法并 文本信息。现有工作将数值信息作为文本关键字 没有考虑文本之间的语义相似/相关度。尽管最 来进行处理，但实际上数值信息的处理方法与文 近有少数工作研究了空间关键字查询的语义匹配， 本信息匹配的处理方法有本质区别（如文本信息 但空间对象除包含位置信息和文本信息外，还包 的主要处理方法是统计和字符串匹配，而数值信 含了价格、用户评分等数值数据。目前还没有相 息可以进行数值大小比较、数值计算等操作)。 关工作同时考虑空间对象与空间关键字查询在位 现有的空间关键字查询处理模式主要可以分 置、文本、语义和数值上的综合相关度，进而也就 为4类：布尔范围查询、布尔k近邻(kNN)查询、 没有同时支持上述综合查询的混合索引结构。 top-k范围查询以及top-kk近邻查询。上述四类 针对上述问题，本文工作的重点是建立一种 方法呈递进式发展，后者是对前者的改进。布尔 同时融合位置信息、文本信息、语义信息和数值 范围查询的缺点是不能控制查询结果规模，且没 信息的空间关键字查询处理模式，并提出一种有 有对查询结果进行排序；布尔k近邻查询是通过 效的混合索引结构来提高查询效率。 兴趣点与查询点之间的距离对查询结果排序，排 本文的主要贡献如下： 序前后与距离大小成反比。布尔范围查询和布 l)提出了基于Word Embedding技术对初始 尔k近邻查询方法都需要兴趣点的文本描述中包 查询关键字进行语义扩展的方法，能够为用户提 含所有查询关键字，这很可能导致查询不到结果 供语义相关的近似查询结果； 或只有少量查询结果，或是得到的查询结果距离 2)在文本信息匹配方面，考虑了查询关键字 查询点的位置很远。top-k范围查询和top-k近邻 可能会出现拼写错误情况，提出了基于编辑距离 查询模式不要求兴趣点的描述信息包含所有的查 的字符串相似度度量方法，尽量避免因查询关键 询关键字，查询结果也可以是仅包含部分关键字 字拼写错误而导致没有匹配结果的情况： 的查询结果。然而，top-k范围查询的排序方法仅 3)提出了基于Skyline的数值属性处理方法， 考虑了兴趣点的文本相关性而没有考虑位置相近 使得空间关键字查询处理模式能够处理数值属 性，top-kk近邻查询同时考虑了兴趣点与查询的 性，令查寻结果更能满足用户的个性化需求。 位置相近性和文本相关性，但没考虑语义相关性。 4)构建了一种新型的混合索引结构AIR 空间关键字查询o1山通常需要将空间索引和 Tree,该索引结构能够直接从每个节点中获取该 文本索引相结合起来构建混合索引结构，从而达 节点对应的数值属性的Skyline集合，并能同时对 到高效地检索空间对象的目的。当前主要的空间 位置信息、文本信息和语义信息进行索引。 数据混合索引结构可归结为表1所示的几类。 表1混合索引结构 Table 1 Hybrid index structure 索引名称 组合模式 优点 缺点 两阶段索引阿 R-tree,Inverted file 结构简单 存储代价高，无法确定第一阶段产生的 候选对象个数 IR'-tree R-tree+Signature 存储代价低、搜索效率高 查询关键字必须严格匹配 IR-tree R-tree+Inverted file存储空间小，提高了搜索效率，允许查询 未考虑查询的语义相关性 关键字部分匹配 bR*-tree间 R*-tree+Bitmap 存储空间小，关键字匹配效率高 关键字多，I/O代价高 Light--Weighted索lW R*-tree和Inverted 可扩展性较强，搜索效率高 存储代价高，频繁插入操作 fle分开存储 的计算代价过高 Quadtree索引 Quadtree+Inverted file 区域搜索效率高 树结构不平衡，存储代价较高 G--index索 聚类标准+聚类操作 通用性强 存储代价高，泛化计算代价高
的索引技术主要有倒排文件 (inverted file)、签名 文件 (signature file) 和位图索引 (bitmap) 等。上述 文本索引以及空间−文本索引主要适用于查询关 键字的严格形式匹配，但由于现实中文本表达形 式多样，如果采用关键字严格形式匹配，可能导 致返回的查询结果太少或没有结果。针对上述问 题，相关研究如文献 [6-8] 中提出了一些新的索引 技术以处理文本中的拼写错误，然而这些方法并 没有考虑文本之间的语义相似/相关度。尽管最 近有少数工作研究了空间关键字查询的语义匹配[9] ， 但空间对象除包含位置信息和文本信息外，还包 含了价格、用户评分等数值数据。目前还没有相 关工作同时考虑空间对象与空间关键字查询在位 置、文本、语义和数值上的综合相关度，进而也就 没有同时支持上述综合查询的混合索引结构。 针对上述问题，本文工作的重点是建立一种 同时融合位置信息、文本信息、语义信息和数值 信息的空间关键字查询处理模式，并提出一种有 效的混合索引结构来提高查询效率。 本文的主要贡献如下： 1) 提出了基于 Word Embedding 技术对初始 查询关键字进行语义扩展的方法，能够为用户提 供语义相关的近似查询结果； 2) 在文本信息匹配方面，考虑了查询关键字 可能会出现拼写错误情况，提出了基于编辑距离 的字符串相似度度量方法，尽量避免因查询关键 字拼写错误而导致没有匹配结果的情况； 3) 提出了基于 Skyline 的数值属性处理方法， 使得空间关键字查询处理模式能够处理数值属 性，令查寻结果更能满足用户的个性化需求。 4) 构建了一种新型的混合索引结构 AIRTree，该索引结构能够直接从每个节点中获取该 节点对应的数值属性的 Skyline 集合，并能同时对 位置信息、文本信息和语义信息进行索引。 1 相关工作 随着移动网络的普遍应用，网络上出现了越 来越多的空间 Web 对象 (spatial web object)。一个 空间对象通常包含位置信息 (如经纬度)、文本信 息 (如空间对象的名称、设施、类别等) 以及数值 信息 (如价格、用户评分等)，数值信息有时也归为 文本信息。现有工作将数值信息作为文本关键字 来进行处理，但实际上数值信息的处理方法与文 本信息匹配的处理方法有本质区别 (如文本信息 的主要处理方法是统计和字符串匹配，而数值信 息可以进行数值大小比较、数值计算等操作)。 现有的空间关键字查询处理模式主要可以分 为 4 类：布尔范围查询、布尔 k 近邻 (kNN) 查询、 top-k 范围查询以及 top-k k 近邻查询。上述四类 方法呈递进式发展，后者是对前者的改进。布尔 范围查询的缺点是不能控制查询结果规模，且没 有对查询结果进行排序；布尔 k 近邻查询是通过 兴趣点与查询点之间的距离对查询结果排序，排 序前后与距离大小成反比。布尔范围查询和布 尔 k 近邻查询方法都需要兴趣点的文本描述中包 含所有查询关键字，这很可能导致查询不到结果 或只有少量查询结果，或是得到的查询结果距离 查询点的位置很远。top-k 范围查询和 top-k 近邻 查询模式不要求兴趣点的描述信息包含所有的查 询关键字，查询结果也可以是仅包含部分关键字 的查询结果。然而，top-k 范围查询的排序方法仅 考虑了兴趣点的文本相关性而没有考虑位置相近 性，top-k k 近邻查询同时考虑了兴趣点与查询的 位置相近性和文本相关性，但没考虑语义相关性。 空间关键字查询[10-11] 通常需要将空间索引和 文本索引相结合起来构建混合索引结构，从而达 到高效地检索空间对象的目的。当前主要的空间 数据混合索引结构可归结为表 1 所示的几类。 表 1 混合索引结构 Table 1 Hybrid index structure 索引名称 组合模式 优点 缺点 两阶段索引[12] R-tree，Inverted file 结构简单 存储代价高，无法确定第一阶段产生的 候选对象个数 IR2 -tree R-tree+Signature 存储代价低、搜索效率高 查询关键字必须严格匹配 IR-tree R-tree+Inverted file 存储空间小，提高了搜索效率，允许查询 关键字部分匹配 未考虑查询的语义相关性 bR*-tree[13] R*-tree+Bitmap 存储空间小，关键字匹配效率高 关键字多，I/O代价高 Light-Weighted索引[14] R*-tree和Inverted file分开存储 可扩展性较强，搜索效率高 存储代价高，频繁插入操作 的计算代价过高 Quadtree索引 Quadtree+Inverted file 区域搜索效率高 树结构不平衡，存储代价较高 G-index索引[15] 聚类标准+聚类操作 通用性强 存储代价高，泛化计算代价高 ·1164· 智 能 系 统 学 报 第 15 卷
第6期 李盼，等：空间关键字个性化语义近似查询方法 ·1165· 近年来，AirBnB、TripAdvisor、hotels.com、 Skyline查询技术是一种典型的偏好查询方 Craigslist、Yelp以及Zillow等LBS系统，都存在 法，由于它具有从多维数据集中提取用户感兴趣 布尔或分类属性，也包括大量数值属性。但是在 信息的能力，因此受到了广泛研究。Skyline在涉 大多数情况下，这些数值属性一般被离散化和转 及多准则决策的应用中被广泛使用2，进一步应 换为分类属性6，然而这样的处理并不能满足用 用到top-k查询2829、偏好收集和最近邻搜索Bo0。 户的查询需求。Liu等m提出的IRS-Tree是一种 Skyline是指在数据集中不受任何其他元组支配 拥有Synopses的倒排R-Tree的混合索引结构，能 的元组集合图。如果q在至少一个维度上优于P, 够有效处理一组位置敏感等级查询。然而，基于 并且在所有其他维度上不比p差，则称q支配p。 IRS-Tree的查询算法要求提供数值属性的精确范 此外，如果一对元组p和q都不支配彼此，则元 围，故数值属性的精确匹配也可能会导致过少甚 组p和g都应该在Skyline中。例如，一个客户想 至没有查询结果返回。针对IRS-Tree存在的问 要寻找一个度假村，假设他综合考虑3个条件：价 题，本文利用Skyline方法，对兴趣点的数值属 格、酒店级别和停车位数量。价格低，级别高，停 性进行处理，将处于被支配地位的元组从Skyline 车位多无疑是更好的选择。因此，如果p在Sky- 中删除，使查询结果更满足用户的个性化需求。 Iine中，则没有其他的不在Skyline中的g都比p 文本之间的语义相关性度量方法可大致分为 拥有更高的价格、更低的级别、更少的停车位。因 3类：第一类是通过使用本体来定义术语/概念之间 此Skyline方法在对查询结果进行个性化处理方 的距离，进而定义拓扑相似性估计语义相似性；第 面具有很大的优势。然而，Skyline方法只能对数 二类是使用如向量空间模型等统计手段估计语言 值属性进行计算，并不能对文本信息等其他非数 单元（例如单词、句子）之间的语义相关性：第三类 值属性进行处理。故本文在处理查询结果的过程 是采用概率主题模型对文本信息进行语义近似处 中利用Skyline方法来对数值属性进行处理，从而 理。词嵌入方法是近年来自然语言理解领域出现 实现个性化查询的目标，使其更加满足用户的需求。 的新方法，该方法是自然语言处理NLP)中的一组 语言建模和特征学习技术的集合名称，其中词汇表 2问题定义和解决方案 中的单词或短语映射到实数向量。从概念上讲，它 涉及从每个单词具有多个维度的空间到具有更低 2.1问题定义 维度的连续向量空间的数学嵌入。生成这种映射 本文先通过一个例子说明要解决的问题。 的方法包括神经网络、单词共现矩阵上的降 图2给出了9个空间对象，空心圆代表空间对象， 维2、概率模型2四、可解释知识库方法21以及单 每个空间对象包含的文本关键字和数值属性信息 词出现上下文的显式表示2，单词和短语嵌入作为 如表2所示。 底层的输入表示。该方法已经被证明可以提高 NLP任务的性能，比如语法分析和情感分析。本 04 文通过Skip-gram模型2的Word Embedding技术 8 对查询条件进行语义近似扩展，即根据查询关键 字，利用Skip-gram技术生成与其语义相关的关键 0,○ 字信息。Skip-gram模型的训练目标是找到对预测 句子或文档中的周围单词有用的单词表示。给定 8 系列训练单词w,w2,,w,Skip-gram模型可以 预测出这些单词的上下文关系，从而实现语义近似 图2空间对象的地理位置信急 查询，Skip-gram结构如图1所示。 Fig.2 Geographic location information for spatial objects 输人 映射 输出 对于一个给定的空间关键字查询q(图2中的 三角形表示)，目的是寻找距离查询位置最近，提 供“chicken”食品，具有“价格低”、“噪声小”且“不 拥挤”等特点的“KFC”店。如果进行严格的文本 +1】 匹配，则没有满足条件的对象。但实际上，KFC 与McDonald语义相似，故o2、o、o,可作为考虑对 P(什2) 象；进而，这三者相比，04距查询位置最近，0，在 图1 Skip-gram模型架构 数值属性上优于04,0，在价格属性上优于02，但 Fig.1 Skip-gram model architecture 02在噪声和拥挤度上明显优于0，。在这种情况
近年来，AirBnB、TripAdvisor、hotels.com、 Craigslist、Yelp 以及 Zillow 等 LBS 系统，都存在 布尔或分类属性，也包括大量数值属性。但是在 大多数情况下，这些数值属性一般被离散化和转 换为分类属性[16] ，然而这样的处理并不能满足用 户的查询需求。Liu 等 [17] 提出的 IRS-Tree 是一种 拥有 Synopses 的倒排 R-Tree 的混合索引结构，能 够有效处理一组位置敏感等级查询。然而，基于 IRS-Tree 的查询算法要求提供数值属性的精确范 围，故数值属性的精确匹配也可能会导致过少甚 至没有查询结果返回。针对 IRS-Tree 存在的问 题，本文利用 Skyline 方法[18] ，对兴趣点的数值属 性进行处理，将处于被支配地位的元组从 Skyline 中删除，使查询结果更满足用户的个性化需求。 文本之间的语义相关性度量方法可大致分为 3 类：第一类是通过使用本体来定义术语/概念之间 的距离，进而定义拓扑相似性估计语义相似性；第 二类是使用如向量空间模型等统计手段估计语言 单元 (例如单词、句子) 之间的语义相关性；第三类 是采用概率主题模型对文本信息进行语义近似处 理。词嵌入方法是近年来自然语言理解领域出现 的新方法，该方法是自然语言处理 (NLP) 中的一组 语言建模和特征学习技术的集合名称，其中词汇表 中的单词或短语映射到实数向量。从概念上讲，它 涉及从每个单词具有多个维度的空间到具有更低 维度的连续向量空间的数学嵌入。生成这种映射 的方法包括神经网络、单词共现矩阵上的降 维 [19-21] 、概率模型[22] 、可解释知识库方法[23] 以及单 词出现上下文的显式表示[24] ，单词和短语嵌入作为 底层的输入表示。该方法已经被证明可以提高 NLP 任务的性能，比如语法分析和情感分析[25]。本 文通过 Skip-gram 模型[26] 的 Word Embedding 技术 对查询条件进行语义近似扩展，即根据查询关键 字，利用 Skip-gram 技术生成与其语义相关的关键 字信息。Skip-gram 模型的训练目标是找到对预测 句子或文档中的周围单词有用的单词表示。给定 一系列训练单词 w1，w2，···，wT，Skip-gram 模型可以 预测出这些单词的上下文关系，从而实现语义近似 查询，Skip-gram 结构如图 1 所示。 Skyline 查询技术是一种典型的偏好查询方 法，由于它具有从多维数据集中提取用户感兴趣 信息的能力，因此受到了广泛研究。Skyline 在涉 及多准则决策的应用中被广泛使用[27] ，进一步应 用到 top-k 查询[28-29] 、偏好收集和最近邻搜索[30]。 Skyline 是指在数据集中不受任何其他元组支配 的元组集合[18]。如果 q 在至少一个维度上优于 p， 并且在所有其他维度上不比 p 差，则称 q 支配 p。 此外，如果一对元组 p 和 q 都不支配彼此，则元 组 p 和 q 都应该在 Skyline 中。例如，一个客户想 要寻找一个度假村，假设他综合考虑 3 个条件：价 格、酒店级别和停车位数量。价格低，级别高，停 车位多无疑是更好的选择。因此，如果 p 在 Skyline 中，则没有其他的不在 Skyline 中的 q 都比 p 拥有更高的价格、更低的级别、更少的停车位。因 此 Skyline 方法在对查询结果进行个性化处理方 面具有很大的优势。然而，Skyline 方法只能对数 值属性进行计算，并不能对文本信息等其他非数 值属性进行处理。故本文在处理查询结果的过程 中利用 Skyline 方法来对数值属性进行处理，从而 实现个性化查询的目标，使其更加满足用户的需求。 2 问题定义和解决方案 2.1 问题定义 本文先通过一个例子说明要解决的问题。 图 2 给出了 9 个空间对象，空心圆代表空间对象， 每个空间对象包含的文本关键字和数值属性信息 如表 2 所示。 q o1 o4 o5 o2 o8 o9 o3 o7 o6 图 2 空间对象的地理位置信息 Fig. 2 Geographic location information for spatial objects 对于一个给定的空间关键字查询 q(图 2 中的 三角形表示)，目的是寻找距离查询位置最近，提 供“chicken”食品，具有“价格低”、“噪声小”且“不 拥挤”等特点的“KFC”店。如果进行严格的文本 匹配，则没有满足条件的对象。但实际上，KFC 与 McDonald 语义相似，故 o2、o4、o7 可作为考虑对 象；进而，这三者相比，o4 距查询位置最近，o7 在 数值属性上优于 o4，o7 在价格属性上优于 o2，但 o2 在噪声和拥挤度上明显优于 o7。在这种情况 输入 映射 输出 w (t) w (t−2) w (t−1) w (t+1) w (t+2) 图 1 Skip-gram 模型架构 Fig. 1 Skip-gram model architecture 第 6 期 李盼，等：空间关键字个性化语义近似查询方法 ·1165·
·1166· 智能系统学报 第15卷 下，如果用户对价格的在意程度较低，则三者中 信息以及用户对数值信息的重视程度，对于空间 最优的查询结果应该是02，反之，最优的查询结 关键字查询也至关重要，并且其处理方法与文本 果应该是。由此可见，空间对象中包含的数值 关键字的匹配处理方法完全不同。 表2空间对象的文本和数值属性信息 Table 2 Text and numerical attribute information for spatial objects 空间对象 数值属性 位置信息(latitude,longitude) 文本属性keywords 噪声 价格 拥挤度 01 (33.3306902,-111.9785992) pizza,steak 0.3 0.5 0.7 0% (41.1195346.-81.4756898) chicken,McDonald 0.2 0.6 0.4 03 (33.5249025,-112.1153098) tea,coffee 0.3 0.4 0.5 04 (40.2916853,-80.1048999) chicken,McDonald 0.5 0.3 0.6 05 (33.3831468,-111.9647254) shopping,market 0.8 0.7 0.9 06 (48.7272.9.14795) bar.beer.chicken 0.9 0.7 0.9 9 (40.6151022445,-80.0913487465) chicken,McDonald 0.3 0.3 0.5 08 (36.1974844.-115.2496601) bread,sandwich 0.4 0.3 0.4 (36.20743,-115.26846) movie,drink 0.2 0.4 0.3 9 (34.2.-81.839) chicken,KFC low low low 给定一个空间数据集O={0,02,…,0},0中的 值属性赋权重而不是限定属性的精确查询范围， 每个对象0，由一个三元组(1，K,A)表示，其中 目的是为了实现数值属性上的模糊查询。 0,1是对象o,的位置信息，0K是o,中的文本关键 2.2解决方案 字集合，0A是0，中的数值属性集合，0，.A中的 本文提出的解决方案如图3所示，可分为 o.4,标准化到[0,1]之间。假设这些数值属性的值 2步： 越小越好，如：噪声低、价格低等。如果数值属性 1)对于用户发起的查询q=(2,K,,根据离 值越高越好，例如：环境氛围、评分等信息，则可 线阶段计算的语义相关性和字符串相似度，将满 以通过a=l-a,将其转换。查询q由三元组（亿，K, 足条件的关键字拓展到查询关键字的集合中； W表示，其中q.1是查询条件的位置信息，qK是 2)构建AR-Tree混合索引结构，对查询条件 查询关键字集合，9W是不同数值属性的权重的 集合和用户对于这些数值属性的偏好，q:w∈qW, 与数据库中的空间对象进行位置相近性、文本相 w≥0（口1,2，，.m并且∑9w=1,为每个 似度和数值接近度的计算，根据最终得分筛选出 最符合用户需求的top-k个结果。 计算字符串相似度 离线预处理阶段 计算语义相关性 发起一个查询 AIR-Tree 位置信息 计算位置相近度 查询 关键字 数据库 十算文本相似度 属性权重 扩展查询 十算数值接近度 关键字 Top-k相关查询 OOOOO 返回相关查询结果 计算综合得分 在线处理阶段 图3解决方案框图 Fig.3 Solution block diagram
下，如果用户对价格的在意程度较低，则三者中 最优的查询结果应该是 o2，反之，最优的查询结 果应该是 o7。由此可见，空间对象中包含的数值 信息以及用户对数值信息的重视程度，对于空间 关键字查询也至关重要，并且其处理方法与文本 关键字的匹配处理方法完全不同。 表 2 空间对象的文本和数值属性信息 Table 2 Text and numerical attribute information for spatial objects 空间对象 位置信息(latitude, longitude) 文本属性keywords 数值属性 噪声 价格 拥挤度 o1 (33.330690 2, −111.978599 2) pizza, steak 0.3 0.5 0.7 o2 (41.119534 6, −81.475689 8) chicken, McDonald 0.2 0.6 0.4 o3 (33.524902 5, −112.115309 8) tea, coffee 0.3 0.4 0.5 o4 (40.291685 3, −80.104899 9) chicken, McDonald 0.5 0.3 0.6 o5 (33.383146 8, −111.964725 4) shopping, market 0.8 0.7 0.9 o6 (48.7272, 9.147 95) bar, beer, chicken 0.9 0.7 0.9 o7 (40.615 102244 5, −80.091348 7465) chicken, McDonald 0.3 0.3 0.5 o8 (36.197484 4, −115.249660 1) bread, sandwich 0.4 0.3 0.4 o9 (36.207 43, −115.26846) movie, drink 0.2 0.4 0.3 q (34.2, −81.839) chicken, KFC low low low ∑ |q.W| i=1 q.wi = 1 给定一个空间数据集 O={o1 , o2 ,…,on}，O 中的 每个对象 oi 由一个三元组 (λ, K, A) 表示，其中 oi .λ 是对象 oi 的位置信息，oi .K 是 oi 中的文本关键 字集合，oi .A 是 oi 中的数值属性集合，oi .A 中的 o.ai 标准化到 [0,1] 之间。假设这些数值属性的值 越小越好，如：噪声低、价格低等。如果数值属性 值越高越好，例如：环境氛围、评分等信息，则可 以通过 ai=1−ai 将其转换。查询 q 由三元组 (λ, K, W) 表示，其中 q.λ 是查询条件的位置信息，q.K 是 查询关键字集合，q.W 是不同数值属性的权重的 集合和用户对于这些数值属性的偏好，q.w∈q.W, q.w≥0 (i=1,2,···,|q.W|) 并且 。为每个数 值属性赋权重而不是限定属性的精确查询范围， 目的是为了实现数值属性上的模糊查询。 2.2 解决方案 本文提出的解决方案如图 3 所示，可分为 2 步： 1) 对于用户发起的查询 q=(λ, K, W)，根据离 线阶段计算的语义相关性和字符串相似度，将满 足条件的关键字拓展到查询关键字的集合中； 2) 构建 AIR-Tree 混合索引结构，对查询条件 与数据库中的空间对象进行位置相近性、文本相 似度和数值接近度的计算，根据最终得分筛选出 最符合用户需求的 top-k 个结果。 数据库 返回相关查询结果 位置信息 查询 关键字 属性权重 发起一个查询 计算语义相关性 计算字符串相似度 计算综合得分 计算文本相似度 计算数值接近度 计算位置相近度 离线预处理阶段 在线处理阶段 Top-k 相关查询 扩展查询 关键字 AIR-Tree 图 3 解决方案框图 Fig. 3 Solution block diagram ·1166· 智 能 系 统 学 报 第 15 卷
第6期 李盼，等：空间关键字个性化语义近似查询方法 ·1167· 3查询与结果的相关性评估 ation,NCE)可近似地最大化softmax的对数概率， 但是Skip-gram模型只关心学习高质量的向量表 查询条件与空间对象的相关性，主要包括位 示，因此只要向量表示保持其质量，就可以自由 置相近度、字符串相似度、语义相关性、文本相似 地简化NCE。负采样NEG)的目标函数为 度和数值接近度。 3.1位置相近度 logo(w)+∑B-llogo(-,月 (5) 给定一个查询g与空间对象0，它们的位置相 NCE和NEG均将噪声分布P(w)作为一个随 近度计算方法如下： So(q,o)=1- dist(g.入，o.) 机参数。文献[26]研究了P.(w)的多种选择，发 (1) 现unigram分布U(w)提高到U(w)3/Z时在 式中：dist(q.,0.)为空间对象o与查询q的欧氏 NCE和NEG的每个任务上都明显优于unigram 距离；Dax为所有对象集合O中的最大距离。 和均匀分布。因此本文也采用该值作为P(w)的 对于表2中的空间对象，可以计算出对象集合O 默认值。 中的最大距离Ds为92.1394，故查询位置与所有空 为了解决罕见词和频繁词之间的不平衡，本 间对象之间的距离分别为：0.6728、0.9248、0.6713、 文采用了一种简单的下采样方法：将训练集中的 0.9313、0.6729、0.0000、0.9278、0.6367、0.6365. 每个单词w,丢弃，丢弃概率的计算公式为 3.2字符串相似度 t 查询g与空间对象o中文本信息的字符串相 Pw）=1-√f0w (6) 似度可通过式(2)计算： 式中：w)为单词w,的频率；1为所选阈值，一般 SF=1- ld(q.s.o.s) (2) 在10左右。该下采样公式能够对频率大于1的 max(len(g.s),len(o.s)) 式中：ld(g.s,o.s)为q与o对应关键字之间的编辑 单词进行下采样，同时保留频率的排序。 距离；len()是求字符长度的函数；max(len(q.s), 对于图2中的例子，利用词嵌入技术得到的 len(o.s)为g与o对应关键字长度的最大值。 扩展关键字查询为{Chicken,KFC,McDonald;。 进而，如果空间对象的文本中也包含了Chicken 对于查询条件KFC,chicken'”,假设用户输入的 或McDonald,.其在语义上也与初始查询关键字十 是“KCF,chicken'”,则其字符串相似度为0.8182。 分相关，因此也可能是候选查询结果。 3.3语义相关度 3.4文本相似度 首先通过Skip-gram模型的Word Embed- 空间对象0与查询q的文本相似度评估的基 ding技术对查询关键字进行扩展。Skip-gram模 本思想是，先将空间对象文本和查询关键字进行 型的训练目标是找到对预测句子或文档中的周围 向量化处理，分别用V。和V,表示，再利用Cosine 单词有用的单词表示。给定一系列训练单词， 相似度方法计算文本相似性，计算方法为 w2,,wr,Skip-gram模型的目标是最大化平均对 数概率，即 ∑v.v,0 ST(o,g)= (7) 、log p(w+lw) (3) I=I -csjc.j 式中c是训练上下文的大小（可以是中心词w,的 -V 函数)。较大的c导致更多训练示例，因此可以以 现有的空间关键字查询仅在形式上匹配关键 训练时间为代价来获得更高的准确性。基本的 字，通常仅考虑文本相似度而未考虑查询与文本 Skip-gram公式使用softmax函数定义p(wlw,), 的语义相关度和拼写错误的情况。 其中softmax函数为 对于表2中的空间对象，可以分别计算出查 exp(vT) 询关键字与其文本相似性为：0.0000、0.4082、0.0000 p(wolw)= (4) ∑exp(vTv.) 0.4082、0.0000、0.3333、0.4082、0.0000、0.0000。 3.5 Skyline 式中：”，和v是w的向量表示的输入和输出向 假设关系D有n个元组和m+1个数值，令 量；W是词汇表中的单词个数。由于其计算代价 A={A,A2,,Am},[A】为属性A,上元组1的值。 71gp(wow)正比于W,该数一般情况下很大 假设对于每一个属性，在支配关系dominate中的 (10-10)。 值有一个关于偏好的总的排序（例如，>b表明值 虽然噪声对比度估计(noise comparison evalu- a优于值b)。一个元组1∈D支配另一个元组
3 查询与结果的相关性评估 查询条件与空间对象的相关性，主要包括位 置相近度、字符串相似度、语义相关性、文本相似 度和数值接近度。 3.1 位置相近度 给定一个查询 q 与空间对象 o，它们的位置相 近度计算方法如下： S D (q,o) = 1− dist(q.λ,o.λ) DMax (1) 式中：dist(q.λ,o.λ) 为空间对象 o 与查询 q 的欧氏 距离；DMax 为所有对象集合 O 中的最大距离。 对于表 2 中的空间对象，可以计算出对象集合 O 中的最大距离 DMax 为 92.1394，故查询位置与所有空 间对象之间的距离分别为：0.6728、0.9248、0.6713、 0.9313、0.6729、0.0000、0.9278、0.6367、0.6365。 3.2 字符串相似度 查询 q 与空间对象 o 中文本信息的字符串相 似度可通过式 (2) 计算： S F = 1− ld(q.s,o.s) max(len(q.s),len(o.s)) (2) 式中：ld(q.s,o.s) 为 q 与 o 对应关键字之间的编辑 距离；len() 是求字符长度的函数；max(len(q.s), len(o.s)) 为 q 与 o 对应关键字长度的最大值。 对于查询条件“KFC, chicken”，假设用户输入的 是“KCF, chicken”，则其字符串相似度为 0.818 2。 3.3 语义相关度 首先通过 Skip-gram 模型的 Word Embedding 技术对查询关键字进行扩展。Skip-gram 模 型的训练目标是找到对预测句子或文档中的周围 单词有用的单词表示。给定一系列训练单词 w1， w2，···，wT，Skip-gram 模型的目标是最大化平均对 数概率，即 1 T ∑T t=1 ∑ −c⩽j⩽c, j,0 log p(wt+j |wt) (3) 式中 c 是训练上下文的大小 (可以是中心词 wt 的 函数)。较大的 c 导致更多训练示例，因此可以以 训练时间为代价来获得更高的准确性。基本的 Skip-gram 公式使用 softmax 函数定义 p(wt+j |wt )， 其中 softmax 函数为 p(wO|wI) = exp(v ′T wO vwI ) ∑W w=1 exp(v ′T w vwI ) (4) vwI 式中： 和 vwO是 w 的向量表示的输入和输出向 量；W 是词汇表中的单词个数。由于其计算代价 ▽lg p(w O |wI ) 正比于 W，该数一般情况下很大 (105 ~107 )。 虽然噪声对比度估计 (noise comparison evaluation, NCE) 可近似地最大化 softmax 的对数概率， 但是 Skip-gram 模型只关心学习高质量的向量表 示，因此只要向量表示保持其质量，就可以自由 地简化 NCE。负采样 (NEG) 的目标函数为 logσ(v ′T wO vwI )+ ∑k i=1 Ewi∼Pn (w)[logσ(−v ′T wi vwI )] (5) NCE 和 NEG 均将噪声分布 Pn (w) 作为一个随 机参数。文献 [26] 研究了 Pn (w) 的多种选择，发 现 unigram 分 布 U(w) 提 高 到 U(w) 3/4 /Z 时 在 NCE 和 NEG 的每个任务上都明显优于 unigram 和均匀分布。因此本文也采用该值作为 Pn (w) 的 默认值。 为了解决罕见词和频繁词之间的不平衡，本 文采用了一种简单的下采样方法：将训练集中的 每个单词 wi 丢弃，丢弃概率的计算公式为 P(wi) = 1− √ t f(wi) (6) 式中：f(wi ) 为单词 wi 的频率；t 为所选阈值，一般 在 10−5 左右。该下采样公式能够对频率大于 t 的 单词进行下采样，同时保留频率的排序。 对于图 2 中的例子，利用词嵌入技术得到的 扩展关键字查询为{Chicken，KFC，McDonald}。 进而，如果空间对象的文本中也包含了 Chicken 或 McDonald，其在语义上也与初始查询关键字十 分相关，因此也可能是候选查询结果。 3.4 文本相似度 空间对象 o 与查询 q 的文本相似度评估的基 本思想是，先将空间对象文本和查询关键字进行 向量化处理，分别用 Vo 和 Vq 表示，再利用 Cosine 相似度方法计算文本相似性，计算方法为 S T (o,q) = ∑n i=1 Vo[i]·Vq[i] √∑n i=1 Vo[i] 2 · √∑n i=1 Vq[i] 2 (7) 现有的空间关键字查询仅在形式上匹配关键 字，通常仅考虑文本相似度而未考虑查询与文本 的语义相关度和拼写错误的情况。 对于表 2 中的空间对象，可以分别计算出查 询关键字与其文本相似性为：0.0000、0.4082、0.0000、 0.4082、0.0000、0.3333、0.4082、0.0000、0.000 0。 3.5 Skyline 假设关系 D 有 n 个元组和 m+1 个数值，令 Α={A1 , A2 ,···, Am}，t[Ai ] 为属性 Ai 上元组 t 的值。 假设对于每一个属性，在支配关系 dominate 中的 值有一个关于偏好的总的排序 (例如，a>b 表明值 a 优于值 b)。一个元组 t∈D 支配另一个元组 第 6 期 李盼，等：空间关键字个性化语义近似查询方法 ·1167·
·1168· 智能系统学报 第15卷 1'∈D,由t>t表示，当且仅当HA∈A,t[A]≥ S(g,o)=B-S1+(1--S2 (10) 1'[A)和A∈A,[A]>[A]。另外，如果一个元组 式中B为调节参数，本文设置为0.85。 1∈D与另一个元组'∈D是不可比的，则表示为 ,当且仅当t￥r且1￥t。 4查询匹配算法 Skyline S是D中不被其他元组支配的元组集 4.1索引结构 合。对于图2中的对象02、04、01，其数值属性可 本文提出的索引结构主要分为语义层、AR 分别表示为{0.2,0.6,0.4}，{0.5,0.3,0.6}，{0.3， Tree索引层。语义层首先使用式(2)计算查询 0.3,0.5}。若属性值越小越好，则由于o,的第一、 g与空间对象关联文档集合中的关键字之间的字 三个属性优于04，第二个属性与o4的相等，可判 符串相似度，如果文档中的关键字与查询关键字 断01支配04，再比较02、01，可知02的第一、三个 的字符串相似度高于给定阈值，则对查询关键字 属性优于01，第二个属性次于01，故02和0，是不 进行扩展。然后，语义层首先通过Word Embed- 可比的，故都应该加入S中。 ding技术，找到语义相关的关键字，然后对查询 3.6评价函数 关键字进行语义扩展。扩展的查询关键字同时包 本文首先使用式(2)对查询条件与空间对象 含了字符串相似和语义相关的关键字。 关联的文档中的关键字进行字符串相似度计算， 在AIR-Tree索引层中，构建了一种新的索引 若查询关键字与文档中的关键字高于给定的字符 结构(AIR-Tree),即在R-Tree的基础上为每个节 串相似度阈值τ，则将该关键字扩展到查询关键 点增加了AttrFile文件，见图4。AIR-Tree的每个 字的集合中。字符串相似度计算的目的是解决由 节点记录了以该节点为根的子树中所有对象的空 于查询关键字拼写错误而导致空查询结果的情况。 间信息、文本信息概要（从节点文本信息中抽取 其次，根据离线阶段计算的语义相关性将满 的关键字集合)、数值属性元组信息及指针，如图4 足给定阈值的关键字拓展到查询关键字的集合 所示。AIR-Tree中每个节点的信息分为3个部 中，从而进行语义近似扩展。目前，普遍采用的 分：前两部分是两个指针，分别指向包含该节点 空间对象0与查询q的相关度计算方法为 所有关键字的倒排文件(InvFile)和数值属性文件 S(q.o)=a.Sp(g.o)+(1-a).Sr(q.o) (8) (AttrFile),第三部分是该节点中的实体集合 式中α为调节参数。为了不失一般性，本文将其 (Entries)。每个非叶子节点和叶子节点都可能包 设置为0.5。 含多个条目，对于叶子节点，它当中的每一个条 本文在此基础上加上了数值属性对查询结果 目由一个四元组构成，形式为,其中 的影响，所采用的空间对象0与查询g之间数值 O代表空间对象，R代表该对象的最小外接矩形 属性的相关度计算方法为 (MBR),1是该对象的文本信息标识符，a是该对 象的数值属性元组的标识符；对于非叶子节点， S2(q,o)=1- (9) 它当中的每一项也由一个四元组构成，形式为 =0 ,其中，Pw是该节点中孩子节点N的 式中：权重数组q.W,是查询g对空间对象o的数 地址，R是指能够包含该节点下所有孩子节点的 值属性的看重程度；q.W是权重个数（也就是数 MBR,P是该节点的文档标识符，文档包含了该节 值属性个数)：0.a,是空间对象o的数值属性值。 点下所有子节点的信息概要，a是该节点的数值 最后使用评价函数，即用式(10)来计算最后 属性标识符，包含了该节点下所有子节点的数值 的综合得分： 属性元组的Skyline集合。 N AttrFile AttrFile N AttrFile nvFile AttrFil nvFile AttrFile InvFile N AttrFile 01 nvFil AttrFile 05 0. 图4AR-Tree索引结构 Fig.4 AIR-Tree index structure
t > t ′ ∀A ∈ A ∃A ∈ A t ≯ t ′ t ′ ≯ t t '∈D， 由 表示，当且仅当 , t[A]≥ t'[A] 和 , t[A]>t′[A]。另外，如果一个元组 t∈D 与另一个元组 t′∈D 是不可比的，则表示为 t~t'，当且仅当 且 。 Skyline S 是 D 中不被其他元组支配的元组集 合。对于图 2 中的对象 o2、o4、o7，其数值属性可 分别表示为{0.2，0.6，0.4}，{0.5，0.3，0.6}，{0.3， 0.3，0.5}。若属性值越小越好，则由于 o7 的第一、 三个属性优于 o4，第二个属性与 o4 的相等，可判 断 o7 支配 o4，再比较 o2、o7，可知 o2 的第一、三个 属性优于 o7，第二个属性次于 o7，故 o2 和 o7 是不 可比的，故都应该加入 S 中。 3.6 评价函数 本文首先使用式 (2) 对查询条件与空间对象 关联的文档中的关键字进行字符串相似度计算， 若查询关键字与文档中的关键字高于给定的字符 串相似度阈值 τ，则将该关键字扩展到查询关键 字的集合中。字符串相似度计算的目的是解决由 于查询关键字拼写错误而导致空查询结果的情况。 其次，根据离线阶段计算的语义相关性将满 足给定阈值的关键字拓展到查询关键字的集合 中，从而进行语义近似扩展。目前，普遍采用的 空间对象 o 与查询 q 的相关度计算方法为 S 1 (q,o) = α· S D (q,o)+(1−α)· S T (q,o) (8) 式中 α 为调节参数。为了不失一般性，本文将其 设置为 0.5。 本文在此基础上加上了数值属性对查询结果 的影响，所采用的空间对象 o 与查询 q 之间数值 属性的相关度计算方法为 S 2 (q,o) = 1− |q.Wi ∑ | i=0 (q.Wi · o.ai) (9) 式中：权重数组 q.Wi 是查询 q 对空间对象 o 的数 值属性的看重程度；|q.Wi |是权重个数 (也就是数 值属性个数)；o.ai 是空间对象 o 的数值属性值。 最后使用评价函数，即用式 (10) 来计算最后 的综合得分： S (q,o) = β · S 1+(1−β)· S 2 (10) 式中 β 为调节参数，本文设置为 0.85。 4 查询匹配算法 4.1 索引结构 本文提出的索引结构主要分为语义层、AIRTree 索引层。语义层首先使用式 (2) 计算查询 q 与空间对象关联文档集合中的关键字之间的字 符串相似度，如果文档中的关键字与查询关键字 的字符串相似度高于给定阈值，则对查询关键字 进行扩展。然后，语义层首先通过 Word Embedding 技术，找到语义相关的关键字，然后对查询 关键字进行语义扩展。扩展的查询关键字同时包 含了字符串相似和语义相关的关键字。 在 AIR-Tree 索引层中，构建了一种新的索引 结构 (AIR-Tree)，即在 IR-Tree 的基础上为每个节 点增加了 AttrFile 文件，见图 4。AIR-Tree 的每个 节点记录了以该节点为根的子树中所有对象的空 间信息、文本信息概要 (从节点文本信息中抽取 的关键字集合)、数值属性元组信息及指针，如图 4 所示。AIR-Tree 中每个节点的信息分为 3 个部 分：前两部分是两个指针，分别指向包含该节点 所有关键字的倒排文件 (InvFile) 和数值属性文件 (AttrFile)，第三部分是该节点中的实体集 合 (Entries)。每个非叶子节点和叶子节点都可能包 含多个条目，对于叶子节点，它当中的每一个条 目由一个四元组构成，形式为，其中 O 代表空间对象，R 代表该对象的最小外接矩形 (MBR)，t 是该对象的文本信息标识符，a 是该对 象的数值属性元组的标识符；对于非叶子节点， 它当中的每一项也由一个四元组构成，形式为 ，其中，pN 是该节点中孩子节点 N 的 地址，R 是指能够包含该节点下所有孩子节点的 MBR，p 是该节点的文档标识符，文档包含了该节 点下所有子节点的信息概要，a 是该节点的数值 属性标识符，包含了该节点下所有子节点的数值 属性元组的 Skyline 集合。 InvFile InvFile InvFile InvFile InvFile InvFile InvFile AttrFile AttrFile AttrFile AttrFile AttrFile AttrFile AttrFile N7 N5 N6 N5 N1 N2 N6 N3 N4 N4 O7 O8 N2 O3 O4 N1 O1 O2 N3 O5 O6 图 4 AIR-Tree 索引结构 Fig. 4 AIR-Tree index structure ·1168· 智 能 系 统 学 报 第 15 卷
第6期 李盼，等：空间关键字个性化语义近似查询方法 ·1169· 在查询过程中，利用算法1中AIR-Tree索引 4)N=H.poll() 结构对POI兴趣点的位置信息、文本信息以及数 5)if N is an object then 值属性进行top-k查询。首先使用式（⑧）计算出与 6)R.add(N) 查询条件中位置信息以及关键字信息的相关度， 7)S=1 其次使用式(9)计算出数值属性相关性，再使用 8)else 式(10)计算出最后综合分数，最后按照综合得分 9)for entry e in N 对查询结果进行排序，使其筛选出最符合用户需 10)hg.add(e) 求的前k个结果，从而使得查询结果更个性化。 ll)ifg.K中包含hs.getId().getKeyword()then 4.2相关算法 12)用式(8)计算位置信息与关键字信息之间 本节给出AIR-Tree索引中用到的函数以及算 的耦合相关度的分数S, 法。首先，需要在离线阶段计算AIR-Tree每个节 13)for每个hs.getId(0 点所对应的Skyline集合，实现方法如算法1所示。 14)根据节点的AttrFile,.将其数值属性的元 算法1 skyline(L) 组信息添加到候选元组列表c,列表中 输入数值属性列表L; l5)s,←-skyline(c,)/*计算skyline元组列表 输出数值属性列表L。 s,的Skyline集合*/ 1)对L按照第一个属性的值从小到大排序 l6)for每个在S,中的元素t 2)令i=0 17)S,g.o)=1-wWm 3)for每个在L列表中的元素元组t 4)while i<t.size()do 18)利用式(10)计算出S 5)if[i门<=[)then/体将[d与L中其他元组 19)H.add(hE)/*H按照S排序*/ 4的第i个元素1[相比*/ 20)return R 6)L.remove()/体将其他元组t1从列表中移除*/ 算法2用于查找top-k个最符合用户需求的 7)i+=1 候选集。首先，使用离线阶段训练好的Word Em- 8)else bedding技术和字符串相似度计算方法对查询关 9)L.remove(t) 键字进行扩展，然后使用离线阶段构建好的AR- 10)return L tree来查找与查询条件最接近的空间对象。首 算法1可以为用户提供独立于其他数据项的 先，根节点”被添加到最大堆H中，如果该节点是 数据项。在查询过程中，数值接近度S,由Sky- 空间对象（即叶子节点），则将其添加到R中，S设 line和用户指定的权重决定，从而决定着哪个分 置为1。否则，即为中间节点，然后中序遍历该 支被选中而加快查找速度。对于一个给定的数值 树，将其孩子节点添加到h中。如果he中的叶子 属性列表L,根据其第一个属性的大小正序排 节点包含扩展后的查询关键字，则使用式(8)计 序。L中的每一个元组的值都会被逐列比较，如 算S,根据其AttrFile,将其数值属性的元组信息 果一个元组的每一列都比其他元组的该列大，则 添加到候选元组列表s,中，计算s,的Skyline集 将该元组从L中移除，直到不再存在这样的元组 合，对于每个在s,中的元素1，使用式(9)计算S2。 为止。 最后使用式(I0)计算最终得分S。最后，将hs添 对于一个给定的空间关键字查询，利用AIR 加到H中，并且迭代，直到H为空或者R中元素 Tree索引结构获取候选查询结果的实现算法如算 个数大于k。 法2所示。 算法1的复杂度分析：令n=H.size(),m= 算法2候选集结果生成算法search(g,k,a, s.size(O,则由以上算法分析可得其时间复杂度为 B,) O(kmn),其中k表示查询结果个数。 输入数据集D,扩展后的查询条件g,返回 5效果与性能实验评价 结果个数k,调节参数a,B,权重数组W: 输出候选集列表R。 本节主要通过在真实数据集上进行实验来验 l)R←-中，最大堆H←-，h- 证本文所提出算法的性能。 2)H.add(r)/*r为根节点*/ 5.1实验设置 3)while H+φ并且R.size0kdo 本实验通过Pytorch实现Word Embedding,其
在查询过程中，利用算法 1 中 AIR-Tree 索引 结构对 POI 兴趣点的位置信息、文本信息以及数 值属性进行 top-k 查询。首先使用式 (8) 计算出与 查询条件中位置信息以及关键字信息的相关度， 其次使用式 (9) 计算出数值属性相关性，再使用 式 (10) 计算出最后综合分数，最后按照综合得分 对查询结果进行排序，使其筛选出最符合用户需 求的前 k 个结果，从而使得查询结果更个性化。 4.2 相关算法 本节给出 AIR-Tree 索引中用到的函数以及算 法。首先，需要在离线阶段计算 AIR-Tree 每个节 点所对应的 Skyline 集合，实现方法如算法 1 所示。 算法 1 skyline(L) 输入 数值属性列表 L； 输出 数值属性列表 L。 1) 对 L 按照第一个属性的值从小到大排序 2) 令 i = 0 3) for 每个在 L 列表中的元素元组 t 4) while i<t.size() do 5) if t[i]<=t1 [i] then /*将 t[i] 与 L 中其他元组 t1 的第 i 个元素 t1 [i] 相比*/ 6) L.remove(t1 ) /*将其他元组 t1 从列表中移除*/ 7) i += 1 8) else 9) L.remove(t) 10) return L 算法 1 可以为用户提供独立于其他数据项的 数据项。在查询过程中，数值接近度 S2 由 Skyline 和用户指定的权重决定，从而决定着哪个分 支被选中而加快查找速度。对于一个给定的数值 属性列表 L，根据其第一个属性的大小正序排 序。L 中的每一个元组的值都会被逐列比较，如 果一个元组的每一列都比其他元组的该列大，则 将该元组从 L 中移除，直到不再存在这样的元组 为止。 对于一个给定的空间关键字查询，利用 AIRTree 索引结构获取候选查询结果的实现算法如算 法 2 所示。 算法 2 候选集结果生成算法 search(q, k, α, β, W[i]) 输入 数据集 D，扩展后的查询条件 q，返回 结果个数 k，调节参数 α，β，权重数组 W[i]； 输出 候选集列表 R。 1) R←ϕ，最大堆 H←ϕ，hE←ϕ 2) H.add(r) /*r 为根节点*/ 3) while H≠ϕ 并且 R.size()<k do 4) N=H.poll() 5) if N is an object then 6) R.add(N) 7) S = 1 8) else 9) for entry e in N 10) hE.add(e) 11) if q.K 中包含 hE.getId().getKeyword() then 12) 用式 (8) 计算位置信息与关键字信息之间 的耦合相关度的分数 S1 13) for 每个 hE.getId() 14) 根据节点的 AttrFile，将其数值属性的元 组信息添加到候选元组列表 ct 列表中 15) st←skyline(ct ) /*计算 skyline 元组列表 st 的 Skyline 集合*/ 16) for 每个在 st 中的元素 t S 2 (q,o) = 1− ∑n i=0 17) (W[i] ∗ t[i]) 18) 利用式 (10) 计算出 S 19) H.add(hE)/*H 按照 S 排序*/ 20) return R 算法 2 用于查找 top-k 个最符合用户需求的 候选集。首先，使用离线阶段训练好的 Word Embedding 技术和字符串相似度计算方法对查询关 键字进行扩展，然后使用离线阶段构建好的 AIRtree 来查找与查询条件最接近的空间对象。首 先，根节点 r 被添加到最大堆 H 中，如果该节点是 空间对象 (即叶子节点)，则将其添加到 R 中，S 设 置为 1。否则，即为中间节点，然后中序遍历该 树，将其孩子节点添加到 hE 中。如果 hE 中的叶子 节点包含扩展后的查询关键字，则使用式 (8) 计 算 S1，根据其 AttrFile，将其数值属性的元组信息 添加到候选元组列表 st 中，计算 st 的 Skyline 集 合，对于每个在 st 中的元素 t，使用式 (9) 计算 S2。 最后使用式 (10) 计算最终得分 S。最后，将 hE 添 加到 H 中，并且迭代，直到 H 为空或者 R 中元素 个数大于 k。 算法 1 的复杂度分析：令 n=H.size()， m= st .size()，则由以上算法分析可得其时间复杂度为 O(kmn)，其中 k 表示查询结果个数。 5 效果与性能实验评价 本节主要通过在真实数据集上进行实验来验 证本文所提出算法的性能。 5.1 实验设置 本实验通过 Pytorch 实现 Word Embedding，其 第 6 期 李盼，等：空间关键字个性化语义近似查询方法 ·1169·
·1170· 智能系统学报 第15卷 中负采样随机采样数量K为100，指定周围单词 故只选取最常见的30000个单词，同时添加一 数C为3进行预测，迭代轮数为2，每轮迭代1个 个单词表示最不常见的单词。本文使用 batch的数量为128，词汇表的大小设置为30000， Adam作为优化器来优化模型。 学习率为0.0001，词向量维度为100作为超参 本文利用Skip-gram模型的词嵌入技术在 数。从文本文件中读取所有的文字，通过这些文 Ylp数据集上进行训练，可以得到查询关键字与 本创建一个vocabulary,由于单词数量可能太大， 其语义相关的关键字，如表3所示。 表3词嵌入技术对查询关键字的语义扩展效果 Table 3 Effect of word embedding technology for query expansion 查询关键字 与查询关键字语义相关的关键字 arts entertainment shopping,beauty spas,home services,health medical,automotive charlotter restaurants,shopping,beauty spa,home service,health medical beauty spas las vegas,food,phoenix,home services,nightlife tea rooms beauty&shopping,beauty spas,home services,local services,active life coffee tea shopping,beauty spas,home services,health medical,local services breakfast brunch home services,health medical,active life,hair salons,home garden food restaurants,food,nightlife,bars,sandwiches 根据表3的结果可以判定Word Embedding技 第2个数据集来自基于位置的服务平台 术有较好的语义近似处理能力。 Foursquare。.数据清理后，数据集包含215614个 本实验所使用的第1个数据集为从Yelp商 与地理位置相关的对象、关键字列表以及数值属 户点评网站上抓取的真实的POI数据集，Yelp是 性的标准化值。每个空间对象包含经纬度信息 美国著名商户点评网站，其网站包含了各地餐 关键字信息，如牛排、披萨、咖啡等，以及4个数 馆、购物中心、酒店等各个领域的商户信息以及 值属性，即价格、环境、服务和评级。 用户评价和签到时间等信息。将这些真实POI 参数的默认值在表4中给出。在实验过程 数据处理成174567个兴趣点，使得每个P0I兴 中，通过改变一个参数的值，固定其他参数的值 趣点都有一个D、位置信息（以经纬度的形式表 来研究该参数对实验结果的影响。所有实验都采 示)、文本信息、数值属性。将位置信息作为空间 用Java实现，电脑配置为CPUi7-8700K3.7GHz. 信息，用户评论信息和category作为文本信息， 32GB内存，Ubuntu18.04.1操作系统。 随机产生的5个0~1之间的随机数作为数值属性。 表4参数的默认值 Table 4 Default values for parameters 参数 默认值 描述信息 0 top-结果集个数 a 0.5 空间相近性与文本相关性的调节参数 B 0.85 空间相近性和文本相关性之间的耦合相关性与数值属性的调节参数 1b.4 ? 数值属性数量 lg.Kl > 查询关键字的数量 II 所有空间对象的数量 0.55 字符串相似度的阈值 5.2 实验结果与分析 观测查询结果个数对系统响应时间的影响。从 本节主要研究在相同数据集上，表4中各参 图5可知，在相同的数据集上无论哪种算法，k值 数分别对AIR-Tree、IR-Tree以及IRS-Tree在查询 越大，系统响应时间越久。这是因为k值越大，越 效率和查询效果上的评估。“索引(YF)”表示该 多的候选对象被索引，返回越多条与查询条件相 索引结构在Yclp/Foursquare数据集上进行的实验。 近的POI空间对象，因此查询时间越久。此外， 5.2.1查询效率方面的实验 IR-Tree的查询响应时间最短，因为它既没有考虑 )k对查询响应时间的影响 数值属性，也没考虑拼写错误的情况，更无需考 该实验的目的是通过设置k的值为10~60来 虑与查询关键字语义相关的关键字查询，因此查
中负采样随机采样数量 K 为 100，指定周围单词 数 C 为 3 进行预测，迭代轮数为 2，每轮迭代 1 个 batch 的数量为 128，词汇表的大小设置为 30 000， 学习率为 0.000 1，词向量维度为 100 作为超参 数。从文本文件中读取所有的文字，通过这些文 本创建一个 vocabulary，由于单词数量可能太大， 故只选取最常见的 30 000 个单词，同时添加一 个单词表示最不常见的单词。本文使用 Adam 作为优化器来优化模型。 本文利用 Skip-gram 模型的词嵌入技术在 Yelp 数据集上进行训练，可以得到查询关键字与 其语义相关的关键字，如表 3 所示。 表 3 词嵌入技术对查询关键字的语义扩展效果 Table 3 Effect of word embedding technology for query expansion 查询关键字 与查询关键字语义相关的关键字 arts entertainment shopping, beauty & spas, home services, health & medical, automotive charlotter restaurants, shopping, beauty & spa, home service, health & medical beauty & spas las vegas, food, phoenix, home services, nightlife tea rooms beauty & shopping, beauty & spas, home services, local services, active life coffee & tea shopping, beauty & spas, home services, health & medical, local services breakfast & brunch home services, health & medical, active life, hair salons, home & garden food restaurants, food, nightlife, bars, sandwiches 根据表 3 的结果可以判定 Word Embedding 技 术有较好的语义近似处理能力。 本实验所使用的第 1 个数据集为从 Yelp 商 户点评网站上抓取的真实的 POI 数据集，Yelp 是 美国著名商户点评网站，其网站包含了各地餐 馆、购物中心、酒店等各个领域的商户信息以及 用户评价和签到时间等信息。将这些真实 POI 数据处理成 174 567 个兴趣点，使得每个 POI 兴 趣点都有一个 ID、位置信息 (以经纬度的形式表 示)、文本信息、数值属性。将位置信息作为空间 信息，用户评论信息和 category 作为文本信息， 随机产生的 5 个 0~1 之间的随机数作为数值属性。 第 2 个数据集来自基于位置的服务平 台 Foursquare。数据清理后，数据集包含 215 614 个 与地理位置相关的对象、关键字列表以及数值属 性的标准化值。每个空间对象包含经纬度信息、 关键字信息，如牛排、披萨、咖啡等，以及 4 个数 值属性，即价格、环境、服务和评级。 参数的默认值在表 4 中给出。在实验过程 中，通过改变一个参数的值，固定其他参数的值 来研究该参数对实验结果的影响。所有实验都采 用 Java 实现，电脑配置为 CPU i7-8700K3.7 GHz， 32 GB 内存，Ubuntu 18.04.1 操作系统。 表 4 参数的默认值 Table 4 Default values for parameters 参数 默认值 描述信息 k 10 top-k结果集个数 α 0.5 空间相近性与文本相关性的调节参数 β 0.85 空间相近性和文本相关性之间的耦合相关性与数值属性的调节参数 |o.A| 4 数值属性数量 |q.K| 7 查询关键字的数量 |D| 1 所有空间对象的数量 τ 0.55 字符串相似度的阈值 5.2 实验结果与分析 本节主要研究在相同数据集上，表 4 中各参 数分别对 AIR-Tree、IR-Tree 以及 IRS-Tree 在查询 效率和查询效果上的评估。“索引 (Y/F)”表示该 索引结构在 Yelp/Foursquare 数据集上进行的实验。 5.2.1 查询效率方面的实验 1) k 对查询响应时间的影响 该实验的目的是通过设置 k 的值为 10~60 来 观测查询结果个数对系统响应时间的影响。从 图 5 可知，在相同的数据集上无论哪种算法，k 值 越大，系统响应时间越久。这是因为 k 值越大，越 多的候选对象被索引，返回越多条与查询条件相 近的 POI 空间对象，因此查询时间越久。此外， IR-Tree 的查询响应时间最短，因为它既没有考虑 数值属性，也没考虑拼写错误的情况，更无需考 虑与查询关键字语义相关的关键字查询，因此查 ·1170· 智 能 系 统 学 报 第 15 卷
第6期 李盼，等：空间关键字个性化语义近似查询方法 ·1171· 询时间最短；其次是AIR-Tree,原因是它需要利 量从1~7来观测其对查询响应时间的影响。由 用Skyline查询方法对数值属性进行处理；耗时最 图7可知，查询响应时间与查询关键字的个数成 久的是IRS-Tree,因为它要求数值属性的精确范 正比增长。因为无论哪种索引结构，当查询关键 围来完成查询匹配，增加了查询成本，故耗时最 字增多时，则索引到的包含查询关键字的对象越 久。综上所述，当k值增大时，AIR-Tree索引的查 多，因此查询时间会增加。 询效率较高，相比于RS-Tree提高了3.6%。 550r 700r R 2500 650 TR 600 Y 450 IRS C 550 xIR(Y 400 500 350 450 300 400 4567 350 lg.KI 015202530354045505560 图74对查询响应时间的影响 Fig.7 Effect of q.K]on the query execution time 图5k对查询响应时间的影响 Fig.5 Effect of k on the query execution time 4)D对查询时间的影响 由于在Foursquare和Yelp上的实验结果相差 该实验的目的是通过设置数据集大小从1， 甚微，故本节剩余部分只展示在Yelp数据集上的 2,,200000来观测数据集大小对查询响应时间 实验结果。 的影响。从图8可知，查询响应时间随着数据集 2)1oA对查询响应时间的影响 的增加而增加。这是因为数据集越大，需要索引 该实验的目的是通过改变数值属性的个数来 的对象越多，并且在处理数值属性的过程中可能 验证其对查询响应时间的影响。本文通过改变 需要耗费更多的时间。 o.A的值从1~5来观测其对查询响应时间的影 750 AIR 响，如图6。实验结果表明，随着数值属性个数的 700 IR 增加，查询时间也逐渐增加。这是由于AIR-Tree 650 600 在查询结果中需要对数值属性的元组进行Sky- 550 line计算，在最坏情况下，Skyline方法几乎会将每 500 个元组中的每个元素进行比较，因此数值属性个 数越多，越耗费时间。IRS-Tree比AIR-Tree耗时， 400 0 2468101214161820 因为IRS-Tree在处理数值属性时，考虑数值属性 D万 的精确范围，若范围设置过大，则会非常耗时。 图8D对查询响应时间的影响 综上可见，当数值属性的个数增多时，AIR-Tree Fig.8 Effect of D on the query execution time 查询效率最佳。 5.2.2效果方面的实验 700 ·AIR 1)D与构建索引时间的关系 650 -IRS 该实验的目的是测试在相同数据集上，通过 600 改变数据集的大小，从1,2，，200000来比较以 550 上几种算法构建索引所用时间，以评价其性能。由 500 图9可知，索引构建时间与数据集的大小成正 450 比。其中构建IR-Tree所用时间最少，这是因为 40 1.01.52.02.53.03.54.04.55.0 IR-Tree与AIR-Tree、IRS-Tree相比，不需要构建 o.A] AttrFile文件和synopses,.因此其索引构建时间最 图6lo4对查询响应时间的影响 短。而IRS-Tree需要将synopses Tree与其他索引 Fig.6 Effect of o.Al on the query execution time 结合来完成查询，故其索引构建时间最长。 3)1q.K对查询时间的影响 2)π与查询准确率的关系 该实验的目的是通过设置查询关键字的数 AIR-Tree是一个高维近似查询索引，对于一
询时间最短；其次是 AIR-Tree，原因是它需要利 用 Skyline 查询方法对数值属性进行处理；耗时最 久的是 IRS-Tree，因为它要求数值属性的精确范 围来完成查询匹配，增加了查询成本，故耗时最 久。综上所述，当 k 值增大时，AIR-Tree 索引的查 询效率较高，相比于 IRS-Tree 提高了 3.6%。 10 15 20 25 30 35 40 45 50 55 60 650 700 600 550 500 450 400 350 AIR (F) IRS (F) IR (F) AIR (Y) IRS (Y) IR (Y) k 查询响应时间/ms 图 5 k 对查询响应时间的影响 Fig. 5 Effect of k on the query execution time 由于在 Foursquare 和 Yelp 上的实验结果相差 甚微，故本节剩余部分只展示在 Yelp 数据集上的 实验结果。 2) |o.A|对查询响应时间的影响 该实验的目的是通过改变数值属性的个数来 验证其对查询响应时间的影响。本文通过改变 |o.A|的值从 1~5 来观测其对查询响应时间的影 响，如图 6。实验结果表明，随着数值属性个数的 增加，查询时间也逐渐增加。这是由于 AIR-Tree 在查询结果中需要对数值属性的元组进行 Skyline 计算，在最坏情况下，Skyline 方法几乎会将每 个元组中的每个元素进行比较，因此数值属性个 数越多，越耗费时间。IRS-Tree 比 AIR-Tree 耗时， 因为 IRS-Tree 在处理数值属性时，考虑数值属性 的精确范围，若范围设置过大，则会非常耗时。 综上可见，当数值属性的个数增多时，AIR-Tree 查询效率最佳。 650 700 600 550 500 450 400 |o.A| 查询响应时间/ms 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 AIR IRS 图 6 |o.A|对查询响应时间的影响 Fig. 6 Effect of |o.A| on the query execution time 3) |q.K|对查询时间的影响 该实验的目的是通过设置查询关键字的数 量从 1~7 来观测其对查询响应时间的影响。由 图 7 可知，查询响应时间与查询关键字的个数成 正比增长。因为无论哪种索引结构，当查询关键 字增多时，则索引到的包含查询关键字的对象越 多，因此查询时间会增加。 550 500 450 400 350 300 |q.K| 查询响应时间/ms AIR IRS IR 1 2 3 4 5 6 7 图 7 |q.K|对查询响应时间的影响 Fig. 7 Effect of |q.K| on the query execution time 4) |D|对查询时间的影响 该实验的目的是通过设置数据集大小从 1, 2,···, 200 000 来观测数据集大小对查询响应时间 的影响。从图 8 可知，查询响应时间随着数据集 的增加而增加。这是因为数据集越大，需要索引 的对象越多，并且在处理数值属性的过程中可能 需要耗费更多的时间。 750 700 600 650 550 500 450 400 |D|/万 查询响应时间/ms AIR IRS IR 0 2 4 6 8 10 12 14 16 18 20 图 8 |D|对查询响应时间的影响 Fig. 8 Effect of |D| on the query execution time 5.2.2 效果方面的实验 1) |D|与构建索引时间的关系 该实验的目的是测试在相同数据集上，通过 改变数据集的大小，从 1, 2,···, 200 000 来比较以 上几种算法构建索引所用时间，以评价其性能。由 图 9 可知，索引构建时间与数据集的大小成正 比。其中构建 IR-Tree 所用时间最少，这是因为 IR-Tree 与 AIR-Tree、IRS-Tree 相比，不需要构建 AttrFile 文件和 synopses，因此其索引构建时间最 短。而 IRS-Tree 需要将 synopses Tree 与其他索引 结合来完成查询，故其索引构建时间最长。 2) τ 与查询准确率的关系 AIR-Tree 是一个高维近似查询索引，对于一 第 6 期 李盼，等：空间关键字个性化语义近似查询方法 ·1171·
·1172· 智能系统学报 第15卷 些给定的查询g可以得到一些语义相关结果。 6结束语 本文使用准确率P来评估查询效果，计算公式为 P=H(OOR(O) 针对现有空间关键字查询处理模式仅支持位 (11) Vol 置相近和文本匹配，但未考虑语义信息，且不能 式中：I(q)是距离查询q最近的top-k个对象的理 处理数值属性的问题，提出了一种支持语义近似 想集合；R(q)是本文提出算法所返回的结果集。 查询处理的空间关键字查询方法。本文研究了通 这里，为了获取更具有鲁棒性的准确率，将返回 过Word Embedding中的Skip-gram模型来实现空 结果数设置为100。由图10可知：当x<0.55时， 间对象的语义近似查询的方法，并且利用Sky- 准确率随着字符串相似度的增大而增大；当τ≥ Iine查询方法实现了查询结果的个性化。实验结 0.55时，准确率不再发生改变并保持在85%左右。 果表明，本文提出的算法不仅支持空间关键字的 精确匹配，支持语义近似查询和形式上的近似匹 6500 6000 配，且能处理文本信息中的数值属性，这样更符 5500 合用户查询要求，在一定程度上提高了用户体验 4500 以及满意度。 400 在未来的工作中，将会利用深度学习的方法 23500 3000 研究路网上的移动对象的集合关键字查询。 2500 2000 2 468101214161820 参考文献： 0 IDW万 [1]LU Ying,LU Jiacheng,CONG Gao,et al.Efficient al- 图9D与构建索引所用时间的关系 gorithms and cost models for reverse spatial-keyword k- Fig.9 Relationship between D and the time taken to build nearest neighbor search[J.ACM transactions on database the index systems..2014,39(2:13 1.00·AR [2]DE FELIPE I.HRISTIDIS V,RISHE N.Keyword search 0.95 on spatial databases[C]//Proceedings of 2008 IEEE 24th 0.90 International Conference on Data Engineering.Cancun, 是085 Mexico:IEEE,2008:656-665. 0.80 [3]ZHANG Chengyuan,ZHANG Ying,ZHANG Wenjie,et 0.75 al.Inverted linear quadtree:efficient top K spatial keyword search[J].IEEE transactions on knowledge and data engin- 0.700002030.4050.60.7080.91.0 eering,2016,28(7):1706-1721. [4]BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al. 图10π与查询准确率的关系 The R*-tree:an efficient and robust access method for Fig.10 Effect of r on the query accuracy points and rectangles[J].ACM SIGMOD record,1990, 3)k与查询准确率的关系 19(2):322-331 通过设置k来查看其对查询准确率的影响， [5]ZHANG Dongxiang,OOI B C,TUNG A K H.Locating 本文设置k区间为[10,100]，步长为10。由图11 mapped resources in web 2.0[C]//Proceedings of 2010 可知，本文所提算法AIR-Tree较IR-Tree、IRS- IEEE 26th International Conference on Data Engineering Tree分别在准确率上提高了10.14%和16.15%。 (ICDE 2010).Long Beach,USA:IEEE,2010:521-532. [6]LI Feifei,YAO Bin,TANG Mingwang,et al.Spatial ap- 100 -A proximate string search[J].IEEE transactions on know- 90 RS ledge and data engineering,2013,25(6):1394-1409. [7]ROCHA-JUNIOR J B,VLACHOU A,DOULKERIDIS C, 70 et al.Efficient processing of top-k spatial preference quer- 60 ies[J].Proceedings of the VLDB endowment,2010,4(2): 50 93-104. 401 102030405060708090100 [8]YAO Bao,LI Feifei,HADJIELEFTHERIOU M,et al.Ap- proximate string search in spatial databases[Cl//Proceed- 图11k与查询准确率的关系 ings of 2010 IEEE 26th International Conference on Data Fig.11 Effect of k on the query accuracy Engineering.Long Beach,CA,USA:IEEE,2010:
些给定的查询 q 可以得到一些语义相关结果。 本文使用准确率 P 来评估查询效果，计算公式为 P = |I(q)∩R(q)| |I(q)| (11) 式中：I(q) 是距离查询 q 最近的 top-k 个对象的理 想集合；R(q) 是本文提出算法所返回的结果集。 这里，为了获取更具有鲁棒性的准确率，将返回 结果数设置为 100。由图 10 可知：当 τ<0.55 时， 准确率随着字符串相似度的增大而增大；当 τ≥ 0.55 时，准确率不再发生改变并保持在 85% 左右。 |D|/万 构建时间/ms AIR IRS IR 2 4 6 8 10 12 14 16 18 20 6 500 6 000 5 500 5 000 4 500 4 000 3 500 3 000 2 500 2 000 0 图 9 |D|与构建索引所用时间的关系 Fig. 9 Relationship between |D| and the time taken to build the index τ 准确率 AIR 1.00 0.95 0.90 0.85 0.80 0.75 0.70 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 图 10 τ 与查询准确率的关系 Fig. 10 Effect of τ on the query accuracy 3) k 与查询准确率的关系 通过设置 k 来查看其对查询准确率的影响， 本文设置 k 区间为 [10, 100]，步长为 10。由图 11 可知，本文所提算法 AIR-Tree 较 IR-Tree、IRSTree 分别在准确率上提高了 10.14% 和 16.15%。 k 准确度 AIR IRS IR 100 90 80 70 60 50 40 10 20 30 40 50 60 70 80 90 100 图 11 k 与查询准确率的关系 Fig. 11 Effect of k on the query accuracy 6 结束语 针对现有空间关键字查询处理模式仅支持位 置相近和文本匹配，但未考虑语义信息，且不能 处理数值属性的问题，提出了一种支持语义近似 查询处理的空间关键字查询方法。本文研究了通 过 Word Embedding 中的 Skip-gram 模型来实现空 间对象的语义近似查询的方法，并且利用 Skyline 查询方法实现了查询结果的个性化。实验结 果表明，本文提出的算法不仅支持空间关键字的 精确匹配，支持语义近似查询和形式上的近似匹 配，且能处理文本信息中的数值属性，这样更符 合用户查询要求，在一定程度上提高了用户体验 以及满意度。 在未来的工作中，将会利用深度学习的方法 研究路网上的移动对象的集合关键字查询。 参考文献： LU Ying, LU Jiacheng, CONG Gao, et al. Efficient algorithms and cost models for reverse spatial-keyword knearest neighbor search[J]. ACM transactions on database systems, 2014, 39(2): 13. [1] DE FELIPE I, HRISTIDIS V, RISHE N. Keyword search on spatial databases[C]//Proceedings of 2008 IEEE 24th International Conference on Data Engineering. Cancun, Mexico: IEEE, 2008: 656−665. [2] ZHANG Chengyuan, ZHANG Ying, ZHANG Wenjie, et al. Inverted linear quadtree: efficient top K spatial keyword search[J]. IEEE transactions on knowledge and data engineering, 2016, 28(7): 1706–1721. [3] BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R*-tree: an efficient and robust access method for points and rectangles[J]. ACM SIGMOD record, 1990, 19(2): 322–331. [4] ZHANG Dongxiang, OOI B C, TUNG A K H. Locating mapped resources in web 2.0[C]//Proceedings of 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010). Long Beach, USA: IEEE, 2010: 521−532. [5] LI Feifei, YAO Bin, TANG Mingwang, et al. Spatial approximate string search[J]. IEEE transactions on knowledge and data engineering, 2013, 25(6): 1394–1409. [6] ROCHA-JUNIOR J B, VLACHOU A, DOULKERIDIS C, et al. Efficient processing of top-k spatial preference queries[J]. Proceedings of the VLDB endowment, 2010, 4(2): 93–104. [7] YAO Bao, LI Feifei, HADJIELEFTHERIOU M, et al. Approximate string search in spatial databases[C]//Proceedings of 2010 IEEE 26th International Conference on Data Engineering. Long Beach, CA, USA: IEEE, 2010: [8] ·1172· 智 能 系 统 学 报 第 15 卷