第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·