在基于位置的应用中, 检索相似的空间文本对象是一个重要的研究课题, 如街旁、Foursquare服务等, 这里与位置信息有关的内容得到利用。在某个地图上, 对于一个查询Q, 检索系统需要找到与之最相关的空间文本对象集合, 对于集合中的每一个元素, 要同时考虑空间最相近并且语义最相似。在最近的研究中, 有很多研究致力于检索空间文本对象。总的说来, 空间对象的索引方式可以归纳为以下几类: 1) 基于R-tree的策略^[1-4]; 2) 基于网格的策略^[5]; 3) 基于空间填充曲线的策略^[6-7]。对于文本信息, 主要使用基于倒排文件的策略^[1-2]和基于签名文件的策略^[8]。为了检索相似的空间文本对象, 一种直接的方法就是融合空间索引以及文本索引。根据融合策略的不同, 大体上可以分为面向空间索引的策略^[6]和面向文本索引的策略^[9]。然而, 这些策略是一种松散的策略, 只是把空间索引和文本索引简单地融合在一起, 空间消耗比较大, 检索的效率也不高。为了克服松散融合的不足, 文献[1, 2, 7]提出紧密融合的策略。

由于紧密融合策略能够无缝地将两种不同的索引(空间索引和文本索引)组合到一个统一的框架中, 因此在这个框架中, 每个顶点是两种相似度的组合(空间相似度与文本相似度)。文献[2]中引入一个新型的索引结构, 称为IR-tree, 每个R-tree的顶点n与n的子树对象内容的概要相关联。然而, 对于空间文本对象来说, 这种文本描述往往很短, 并且有时几乎没有相同词存在。对于空间文本对象来说, 文本信息比较短, 若使用传统的词频计算的方式来计算文本之间的相似度, 不能得到精确的结果^[1-2], 因此传统的基于词频计算策略^[10-13]不大适用于计算文本之间的相似度。考虑到空间文本对象的实际情况, 本文提出一种基于语义相似的文本相似度计算策略来融合相应的空间信息, 从而得到比较精确的检索结果。

本文提出一种快速有效地检索相似空间文本对象的策略, 其中心思想在于建立一个完整的结构, 能无缝地融合空间索引和文本索引。实验结果表明, 由于考虑了空间文本对象文本的属性, 本文提出的策略能有效地提高空间文本对象的检索精度, 并且能保持较高的速度。

1 问题的提出 1.1 准备知识

假设O为一空间文本数据集合。每个空间对象o∈O被定义为一个对象对(o.ρ, o.φ), 其中o.ρ是一个二维的地理位置(可以用经度和维度表示), o.φ是一个文本描述, 也就是用户在某个地理位置的文本表达。算法要解决的问题是, 检索出与查询最相似的top-k个空间文本对象。对于一个查询Q=〈Q.ρ, Q.φ, k〉, 在给定的空间文本对象集合O中寻找k个对象P, 这些对象按照相似度进行排序(这里的相似度同时考虑了空间相似度和文本相似度), 即∀o∈P和∀o∈(O-P)满足Sim_dist(Q, o)≤Sim_dist(Q, r)。具体地, 对于某查询, 对象P的排序值可以用下式计算:

$ {\rm{Si}}{{\rm{m}}_{{\rm{dist}}}}(o,\;Q) = \alpha \cdot {S_{\rm{S}}}(o.\rho ,\;Q.\rho ) + (1 - \alpha ) \cdot {S_{\rm{T}}}(o.\varphi ,\;Q.\varphi ), $

其中, S_S(o.ρ, Q.ρ)是对象o.ρ与Q.ρ之间的欧氏距离, S_T(o.φ, Q.φ)是这两个对象之间的文本距离, α∈[0, 1]。

1.2 空间临近与文本相似

空间临近S_S被定义为标准化的欧氏距离, 即

$ {S_{\rm{S}}} = \frac{{{\rm{dist}}(o.\rho ,\;Q.\rho )}}{{{\rm{dis}}{{\rm{t}}_{\max }}}}, $

dist(o.ρ, Q.ρ)是查询对象与所有数据集中对象的欧氏距离。文本之间的相似度计算可以使用现有方法, 如语言模型^[1], 余弦策略^[9]或BM25^[1]。因此, 文本之间的距离可以定义为

$ {S_{\rm{T}}} = 1 - {\rm{Sim}}(o.\varphi ,Q.\varphi ). $

从前面的分析可以得知, 现有的基于词频以及共现的模式需要有很多相同的词出现在相似的文本中, 这种方式不适合计算两个短文本之间的相似度, 因为两个短文本之间虽然语义相似, 但往往只有很少的共同的词^[10-13]。为了克服短句的不足, 很多研究致力于解决短文本相似度的计算问题, 总的来说可以分为基于知识的策略^[12]、基于语料库的策略^[10-11]、基于语法的策略^[11]以及混合策略^{[10, 13]}。

为了计算文本之间的相似度S_T(o.φ, Q.φ), 我们使用最新的短文本相似度计算方法来组合不同的相似度计算策略^{[10, 13]}。需要强调的是, 短文本由词组成, 因此计算短文本间的相似度归根到底是计算词与词之间的相似度^{[10, 13]}。

1.3 通用框架模型

有很多工作致力于研究快速检索top-k空间文本对象, 本文在其中选取一个最具代表性的工作^[1]作为研究对象。文献[1]中使用一个混合索引结构IR-tree, 融合了空间信息以及文本信息。IR-tree本质上是一棵R-tree, 每个顶点关联一个倒排文件索引, 这个索引包含此顶点所有子树的信息。IR-tree的每个顶点能总结此顶点所有子节点的文本信息, 即此顶点能描述子节点的所有信息。同时, 此顶点能估计出查询与所有在子树中对象的相关程度, 并给出边界。因此, top-k检索的结果使用最佳优先搜索和优先队列来实现。

2 本文提出的策略

考虑到文本的语义相似性, 本文提出一种快速有效的空间文本对象的检索方法。在介绍本文的策略之前, 首先讨论现有的集中空间文本对象的检索方法。

2.1 基准策略

若要快速有效地得到top-k的空间文本对象, 主要的挑战在于如何对空间信息以及文本信息进行索引。一种简单的方法就是利用R-tree来计算对象的空间相近程度, 利用倒排文件的方式来计算文本的相似性^[14]。然后, 把两种索引结合起来, 得到top-k的空间文本对象。但是, 计算数据集中所有的候选对象是非常耗时的。另一种解决方法是基于倒排文件和R-tree来计算空间相近度以及文本相似度, 最终生成一个top候选对象的集合。然而, 这种方式也比较耗时, 因为在预先不知道查询的情况下, 不能在第一步确定需要计算多少个候选对象来满足最终的top-k结果, 即不能保证第一步查找的对象能满足后面的k值。

因此, 对于检索空间文本对象, 一种统一的索引结构就显得非常必要^[1-2]。据我们所知, 目前大部分研究使用基于词频的方式, 即根据词语出现的频度以及共现来衡量两个文本对象之间的相似程度。从前面的分析中得知, 由于空间文本对象的文本信息比较短, 上述方法不适合两个短文本的计算。本文第一次将语义信息融合到检索空间文本对象中, 以解决短文本相似度计算不准确的问题。另外, 本文选取一些具有代表性的方法^[1]作为基准策略。

2.2 基于语义的策略

本文的主要目的是将语义信息融合到索引结构中, 并能很好地融合空间相近性与语义相似性。在文献[1]中, 由于紧密融合了倒排文件索引以及R-tree, 在文本信息与空间信息的融合上取得较好的效果。对于给定的两个短文本S和P, Sim(S, P)与短文本中代表性的词对有关。设t₁^S, t₂^S, …, t_n^S和t₁^P, t₂^P, …, t_m^P是S和P的词。如果n≤m, 则相似度值可以表示为

$ {\rm{Sim}}(S,P) = \mathop {\sum \;}\limits_i^n {\rm{Si}}{{\rm{m}}_r}(t_i^S,\;P), $

这里Sim_r表示代表性词对之间的相似度, 其值可以从代表性的词对之间获得。因此, 为文本信息建立的倒排表必须满足以下条件: 1) 所有词都必须定义; 2) 接续列表必须与词相关。然而, 如果一个查询Q包含多个词t₁^Q, t₂^Q, …, t_n^Q, 如何从中获取相关词? 由于本文提出的策略是从倒排表中获取排序列表, 每个词t_i^Q(i∈n)与排序列表有关, 因此很容易应用阈值算法^[15]来获得与查询Q最相关的文本。文献[1]中将空间索引与文本索引融合在同一索引结构中。根据索引建立的方式, 本文中融合文本的语义信息。

2.2.1 索引建立

IRS策略 IRS策略是将语义信息融合到IR-tree中(即使用了语义相似度的IR-tree)。IRS的建立利用了在R-tree中普遍使用的插入操作^[16]。此操作包含选择叶节点和分裂节点, 并保证节点的子节点包含节点中所有的文本信息。每个节点包含一个指向倒排表的指针。在IRS的索引结构中, 叶子节点包含一组实体, 记为(O, R, O.φ), 这里O为数据集中的空间文本对象, R为对象O的矩形边界, O.φ是对象O的文本描述。在子节点中, 存储指向倒排表的指针。非叶节点R包含一组实体, 记为(D, R, D.φ), 这里D为子节点R的地址, R为包含所有矩形的最小边界矩形, D.φ为此矩形的文本描述。本文融合了每个空间文本对象的语义信息, 所以在倒排表中, 每个词对应一组文本列表对象, 这些对象按照词语文本之间相似度的倒序排列。在IRS中, 文本信息总结了所有子节点中的文本内容, 所以能预估与查询相关的范围。

DIRS策略 从IRS策略可以看出, 索引建立时只考虑空间信息, 即最小矩形是否与空间位置有关。在实际情况中, 对于一个查询, 距离查询最近的不一定是用户最终想得到的结果, 因此在索引建立时需要同时考虑空间信息和文本信息。与IRS策略相似的是, 非叶节点R包含一组实体, 记为(D, R, D.φ)。与R-tree操作相同, 对于一个新的空间文本对象, 为了选择合适的插入路径, DIRS同时考虑了空间信息和文本信息。记每个节点的条目为En₁, En₂, …, En_k。令O_new是新插入的空间文本对象, 在R-tree中, En_i的面积由于新空间文本对象O_new的加入而变大。本文使用一个衡量指标EnlargeRec(En_k)来描述面积的增加值:

$ {\rm{EnlargeRec}}({\rm{E}}{{\rm{n}}_k}) = {\rm{Rec}}\left( {{\rm{E}}{{\rm{n}}_k}^{{\rm{new}}}.R} \right) - {\rm{Rec}}({\rm{E}}{{\rm{n}}_k}), $

其中, Rec(En_k^new. R)是En_k融入了新空间文本对象O_new后的新实体。考虑了文本信息后, 面积增加可以用下式表示:

$ {\rm{EnlargeRe}}{{\rm{c}}_{\rho \varphi }}({\rm{E}}{{\rm{n}}_k}) = \left( {1 - \delta } \right) \cdot \frac{{{\rm{RecE}}{{\rm{n}}_k}}}{{{\rm{Re}}{{\rm{c}}_{\max }}}}{\rm{ + }}\delta \cdot {S_T}({\rm{E}}{{\rm{n}}_k},O.\varphi ), $

其中, δ是调节空间信息与文本信息的参数, Rec_max是包含所有空间文本对象的最小边界矩形。

不同于R-tree, 在建立DIR索引的插入操作中, 选取子树时要考虑文本信息, 使EnlargeRec_ρφ(En_k)的值最小。同样, 在分裂操作中也需要考虑文本的信息, 即在建立索引的整个过程中同时考虑到空间信息与文本信息。

2.2.2 查询过程

最佳优先遍历算法^[17]和优先队列用于存储访问过的顶点和空间文本对象。我们用min_ρφ(Q, R)表示查询Q与矩形R之间的边界, Sim_dist(Q, o)表示Q与每个空间文本对象o之间的距离, 详细说明见表1。需要说明的是, Sim_dist(Q, o)算法仅计算查询Q与算法遍历过的对象或矩形。我们用一个例子来说明DIRS与IRS策略的不同, 具体过程见表2和3。

从表2可以看出, 为了得到top-2对象o₂, o₁, IRS策略的检索过程遍历R₅, R₆, R₁, R₂, R₃, R₄, 也就是遍历整棵树中大部分的节点。这是因为IRS策略在建立索引的时只考虑空间信息, 忽视了文本的语义信息。

从表3可以看出, DIRS策略的检索过程仅需遍历R₅, R₁, R₃就能得到最终的top结果。这是因为DIRS在索引建立时考虑了文本的语义信息, 使得索引结构更加准确, 查询的过程只需要遍历很少的节点, 即只需要5步, 少于IRS策略的7步。

3 实验分析

我们通过实验, 从效率和有效性两个方面检验本文提出的策略。实验在16-core Intel® Xeon® E5530服务器上进行, 操作系统为Debian 2.6.26-2, 所有程序使用C语言编写, 利用GNU gcc编译器编译。

本文使用文献[18]中使用的数据集。此数据集共有225098个用户, 22506721个唯一的空间文本对象(这里的对象既含有空间信息, 又含有文本信息)。为了检验本文所提策略的有效性, 将IR-tree没有融入语义信息作为基准策略, 记为baseline, 将IR-tree使用了语义信息记为IRS, 将文本信息索引加上语义融合记为DIRS。本文所用数据集的统计信息见表4。

3.1 有效性实验结果

在有效性试验中, 我们随机选择5个查询, 分别计算在基准策略、IRS以及DIRS三种策略下的精度。从前面的分析可以看出, 影响有效性的因素有两个。一个影响因素是在计算过程中调节融合空间相近程度与文本相近程度的参数α, 这个参数的作用主要是调节空间相近与文本相似这两个因素的权重。这是由于在实际的系统中, 人们对空间相似度与文本相似的关心程度不同, 因此需要调节这个权重来计算出更加精确的结果。另一个影响因素是索引建立时, 用来调节文本加强程度的参数δ。由于本文所提策略在索引建立初期就考虑文本因素对于整个索引建立的影响, 因此δ就是为了调节文本因素对索引建立影响程度的参数。我们通过交叉验证实验, 选测α和δ的最佳值。

α和δ的取值都在0.1~0.9之间。从实验结果得到: 对于IRS, α=0.68; 对于DIRS, α=0.68, δ=0.2。有效性实验结果如表5所示, 可以看出, IRS策略和DIRS策略由于考虑了语义信息, 所以明显优于基准策略。

3.2 不同参数下实验结果

由于本文的实验结果与两个重要的参数α和δ有关, 因此我们分别选取 α和δ在0.1~0.9区间, 按照粒度0.1来验证, 结果如表6和7所示。可以看到, 相比于IRS策略, 由于DIRS策略在索引建立时已经考虑了文本之间的信息, 所以能大幅度减少访问时间。从表6和7还可以看出, 不同的α和δ值对效率的影响主要表现在节点访问的顺序以及在某个节点访问的时间长短上, 所以α和δ这两个参数对基准策略的影响不大, 而对IRS策略和DIRS策略有一定的影响。因此, 为了平衡有效性与效率之间的关系, 如何选取α和δ参数值也是一个重要的研究课题。

3.3 效率实验结果

效率的比较使用有效性试验中最佳的参数配置, 通过以下的实验来检验: 不同的数据集大小以及不同的k值。本文从数据集中随机抽取10个对象作为查询, 实验结果包括平均查询时间, 结果如图1和2所示。可以看出, 由于DIRS在索引建立时考虑了文本信息, 使得查询访问较少的节点就能得到最终的结果, 所以在性能上DIRS比IRS具优势。

4 总结

本文针对传统空间文本检索策略中的有效性问题, 对如何从给定的空间文本对象集合中快速有效地检索出top-k个近似结果进行研究, 主要贡献如下。

1) 以空间文本对象检索为研究对象, 提出一种基于语义的策略, 在空间文本兑现检索过程中考虑到语义信息, 通过建立综合的索引来无缝融合空间索引与文本索引。

2) 提出一种快速有效的空间文本对象的检索算法, 这种算法对于实际应用系统非常重要, 因为用户更加倾向于找到语义相似的对象。

3) 对实际数据的实验表明, 与现有策略相比较, 本文提出的策略在速度以及有效性方面有较大优势。