空间大数据是带有位置信息的大规模数据, 对其进行分析和利用能够为企业、政府和个人提供非常有价值的信息服务, 辅助做出更明智的空间决策. 推动空间大数据技术的发展, 对我国建设智慧城市、发展智能交通与优化城市资源配置具有重大意义. 空间选址是空间大数据领域的基本应用, 旨在根据用户与设施的空间数据从给定的候选位置集合中选择最优的一个或一组位置, 使得决策最优化或用户收益最大化. 随着GPS定位技术、移动网络技术的兴起, 以及智能设备的普及, 基于位置的服务(location-based service, LBS)迅速发展并得到广泛的应用, 网络上积累了大量带有位置和文本信息的空间文本数据. 近年来, 空间关键字查询^[1]在时空数据领域得到了广泛的关注. 具体地, 给定空间位置和一系列关键字, 空间关键字查询将返回满足特定查询条件的一个或多个空间文本对象. 例如, 检索国家图书馆1 km内具有关键字“咖啡”“烤鸡”“意大利面”的所有餐厅(即空间文本对象).

Choudhury等人^[2]进一步借鉴反向最近邻思想提出面向空间文本对象的选址问题MaxBRSTkNN, 即从候选位置中选出最优的位置, 能够影响最多空间文本对象. 其中影响是由空间邻近程度和文本相似程度共同决定, 愈接近且越相似影响力越大. 例如打算从候选位置集合里选最优位置开一家意大利餐厅(“意大利”和“餐厅”为文本), 上述选址方法可以挖掘出附近喜欢意大利菜顾客最多的候选位置.

空间文本选址问题应用领域十分广泛. 针对个人用户推荐服务设施, 比如为推荐最称心的餐厅就餐或最舒适的酒店入住等; 针对企业和组织提供合理的决策, 在商业领域, 能够为超市选择具有最多潜在客户的店址, 为物流企业选择交通便利的最佳仓储位置等; 在交通领域, 可以帮助组织规划更加合理的公交站或地铁站位置等; 在城市规划领域, 能够帮助城市管理者优化城市布局, 提高土地利用率等.

空间文本选址问题应用领域十分广泛. 针对个人用户推荐服务设施^[3], 比如为推荐最称心的餐厅就餐或最舒适的酒店入住等; 针对企业和组织提供合理的决策, 在商业领域^[4], 能够为超市选择具有最多潜在客户的店址, 为物流企业选择交通便利的最佳仓储位置等; 在交通领域^[5], 可以帮助组织规划更加合理的公交站或地铁站位置等; 在城市规划领域^[6], 能够帮助城市管理者优化城市布局, 提高土地利用率等.

尽管现有方法一定程度解决了空间文本选址问题, 但仍存在以下3方面局限. 首先, 在线消费平台的迅速发展积累了大量用户评价数据(如Yelp、大众点评等). 用户通过这些平台选择服务设施时往往会根据过往用户评价等级(通常表示为1–5星)进行筛选, 比如通过Yelp优先选择用户评级高的酒店住宿(或餐厅就餐). 显然, 空间文本选址问题应当考虑服务设施的用户评级. 其次, 传统空间文本选址中用户只会被对其影响力最大的服务设施影响, 当设施间影响力相差不大时, 该模型与真实世界中用户可能同时受到多个设施影响^[7]的情况并不一致. 最后, 位置影响力的计算未考虑周边其他同类服务设施的竞争. 比如当设施A和设施B都能服务顾客时, 二者必然产生同行竞争^[8]. 传统方法非此即彼的影响模式并不完全符合现实情况.

为更合理地在同行竞争环境中结合用户评级因素做出选址决策, 本文提出了新的空间文本竞争选址问题CoSTUR (competitive spatio-textual location selection based on user rating), 首次同时将用户评级和同行竞争因素纳入空间文本选址的考虑范围, 用于从候选位置集合中选择最优的前k个, 使它们相比剩余候选, 综合文本相关性、距离远近、评级高低等因素, 在设施竞争环境中能够影响更多的用户. 其中, 现有设施和候选位置均具备位置、文本和用户评级属性, 每个用户具有位置和文本信息. CoSTUR问题所选择的最优k个位置可用于企业和组织进一步决策.

为了解决CoSTUR问题: 首先, 借鉴Liu等人^[8]对同类竞争设施间均分影响力的思想, 在此基础上结合用户评级完善竞争影响力的定义. 其次, 利用可权衡的影响力阈值摆脱了顾客只能受单个设施影响的假设局限. 阈值越大时, 设施对潜在顾客的影响估计就越准确; 反之, 设施可能影响的潜在顾客数量则越大. 最后, 构建了基于aR-tree^[9]的索引结构TaR-tree, 其通过文本相似性将树节点的信息向父节点聚合, 进而实现空间性与文本的共同检索. 利用阈值设计了一个基于用户受影响范围的新剪枝策略, 结合TaR-tree结构建立基于范围查询和空间联合思想的两种解决方案. 相比基线算法, 所设计的方法能够提升近一个量级的计算效率.

本文的贡献总结如下.

• 提出了一个新的空间文本选址问题CoSTUR, 首次将设施的同行竞争和用户对设施的评级因素融入到空间文本选址问题当中.

• 设计了一个基于用户受影响的空间范围剪枝策略, 结合文本信息构建新的类似aR-tree的索引结构实现范围查询和空间联合两种解决方案.

• 在真实和合成数据集上的实验结果表明, 所提出的优化算法能够显著提高计算效率.

1 问题定义 1.1 基本概念

空间文本数据由空间位置$loc = {\text{(}}lon, lat{\text{)}}$和文本描述$des$组成, 其中$lon$和$lat$分别为地理经度和纬度, $des$为描述数据的多个词语组合, 如标签、特征、偏好等. 对于特定的用户集合$U = \left\{ {{u_1}, {u_2}, \cdots,{u_m}} \right\}$, 其中${u_i} = \left( {des, loc} \right)\;\left( {{u_i} \in U \wedge i \in \left[ {1, m} \right]} \right)$, ${u_i}.des$和${u_i}.loc$分别为用户的文本描述和空间位置. 现有设施集表示为$F = \left\{ {{f_1}, {f_2}, \cdots,{f_n}} \right\}$, 其中${f_j} = \left( {des, loc, rat} \right)\left( {{f_j} \in F \wedge j \in \left[ {1, n} \right]} \right)$, 其中${f_j}.des$描述设施的服务内容、特色或职能等, ${f_j}.loc$和${f_j}.rat$分别为设施的空间位置和用户评级. 候选位置的集合表示为$C = \left\{ {{c_1}, {c_2}, \cdots,{c_r}} \right\}$, 其中${c_k}.loc\;( {c_k} \in C \wedge k \in \left[ {1, r} \right] )$为候选位置的经纬度. 由于将要在候选位置建设的设施具有明确的目标, 即文本描述和预期评级, 因此, 可以认为${c_k}.des$和${c_k}.rat$对于所有候选位置均相同. 考虑到设施${f_j}$和将要建设设施的候选位置${c_k}$在竞争环境中均可能影响用户, 下文用对象$o$表示抽象的设施或候选位置.

定义1 (空间相关性$S\left( {u, o} \right)$). 给定一个用户$u$和一个对象$o$, 二者之间的空间相关性定义如式(1):

$S\left( {u, o} \right) = 1 - \frac{{d\left( {u.loc, o.loc} \right)}}{{{D_{\max }}}}$

(1)

其中, $d\left( {u.loc, o.loc} \right)$表示用户$u$和对象$o$之间的欧氏距离, ${D_{\max }}$表示整个问题域空间内各设施/候选位置与用户之间的最大距离.

定义2 (文本相关性$T\left( {u, o} \right)$). 给定一个用户$u$和一个对象$o$, 二者之间的文本相关性定义如式(2). 本文使用Jaccard相关度, 其他度量方式也适用.

$T\left( {u, o} \right) = \frac{{|u.des \cap o.des|}}{{|u.des \cup o.des|}}$

(2)

定义3 (空间文本相关性$P\left( {u, o} \right)$). 给定用户$u$和对象$o$, 二者之间的空间文本相关性定义如式(3):

$P\left( {u, o} \right) = \alpha S\left( {u, o} \right) + \left( {1 - \alpha } \right)T\left( {u, o} \right)$

(3)

其中, $\alpha$是一个空间-文本调节参数, 取值$\alpha \in \left[ {0, 1} \right]$, 用于平衡空间相关性和文本相关性二者在影响力中的重要程度, 显然$P\left( {u, o} \right) \in \left[ {0, 1} \right]$.

1.2 综合竞争影响模型

真实世界中用户可能同时受多个设施影响, 因此, 为摆脱传统空间文本选址问题中顾客只受单个设施影响假设的局限, 本文引入影响阈值$\tau$, 以适应用户可以同时被多个设施影响的情况. 由于定义3中空间文本相关性取值范围是$\left[ {0, 1} \right]$, 因此影响阈值的取值范围也与之相一致.

定义4 (对象影响用户). 给定一个用户$u$和对象$o$, 以及一个期望影响阈值$\tau \in \left[ {0, 1} \right]$, 当$P\left( {u, o} \right) > \tau$时, 认定对象$o$会影响用户$u$.

值得一提的是, 阈值$\tau$的设置不仅用于评价影响与否, 还能够用作权衡对象$o$影响用户的程度: $\tau$越大, $o$对潜在用户的影响估计就越准确; 反之, 对象$o$可能影响的潜在顾客数量就越大.

定义5 (对象影响力$inf \left( o \right)$). 给定一个对象$o$、影响阈值$\tau$和特定用户集合$U = \left\{ {{u_1}, {u_2}, \cdots,{u_m}} \right\}$, 则对象$o$影响的用户构成的集合为${S_{inf }}\left( o \right) = \left\{ {{u_i}|P\left( {{u_i}, o} \right) > \tau \wedge {u_i} \in U} \right\}$, 将对象$o$影响的用户数量定义为其影响力, 即$inf \left( o \right) = |{S_{inf }}\left( o \right)|$.

基于定义4可定义对象间是否存在竞争关系.

定义6 (对象间竞争关系). 两个对象${o_a}$和${o_b}$, 对于用户$u$, 若$P\left( {u, {o_a}} \right) > \tau \wedge P\left( {u, {o_b}} \right) > \tau$, 则${o_a}$和${o_b}$都独立地影响用户$u$, 意味着对象${o_a}$和${o_b}$之间存在竞争.

定义7 (用户竞争集${S_{{{comp}}}}\left( {u, o} \right)$). 给定一个用户$u$和由设施或候选位置构成的对象集合$O = \left\{ {{o_1}, {o_2},\cdots,{o_m}} \right\}$, 则影响用户$u$的竞争对象集表示为${S_{{{comp}}}}\left( {u, o} \right) = \{ {o_i}|P\left( {u, {o_i}} \right) > \tau \wedge {o_i} \in O \}$.

基于对象间竞争关系, 借鉴文献对同类竞争设施间均分影响力的思想, 定义影响平分模型.

定义8 (平分影响力$\overline {score} \left( o \right)$). 若多个对象影响同一用户$u$, 且这些对象属于集合$O$, 则这些对象将平分用户$u$的影响力, 则对于$o \in O \wedge P\left( {u, o} \right) > \tau$, 对象$o$平分影响力$\overline {score} \left( o \right) = \displaystyle\sum\nolimits_{u \in {S_{inf }}\left( o \right)} {\dfrac{1}{{|{S_{{{comp}}}}\left( {u, O} \right)|}}}$, 其中分子1表示每个用户对影响值的贡献为1, 由于$u \in {S_{inf }}\left( o \right)$, 则至少存在$o$影响$u$, 故分母${S_{{{comp}}}}\left( {u, O} \right)$必然不为0.

此时想建立新的设施获利, 就需要考虑与现有设施集$F$的竞争. 若候选位置$c$与用户$u$的空间文本相关性大于阈值$\tau$, 则$c$会影响用户$u$, 如果存在现有设施同样也影响$u$, 则候选$c$将与影响用户$u$的已有设施竞争, 则计算$c$的影响力就需要计入平分影响力, 根据定义8可得$\overline {score} \left( o \right) = \displaystyle\sum\nolimits_{u \in {S_{inf }}\left( c \right)} {\dfrac{1}{{|{S_{{{comp}}}}\left( {u, F} \right)| + 1}}}$, 其中|S_comp(u,F)|+1表示$c$带来的影响.

进一步考虑在竞争的基础上增加用户评级给影响力计算带来的变化. 由于每个用户对影响值的贡献为1, 换句话说, 一个用户受到的总影响值表征为1, 考虑到用户评级通常以1–5星进行从劣到优的评价, 故将对象的用户评级$o.rat$设置为一组离散值(也可采用更细粒度的量化标准, 不会影响本文结论), 如1–5星分别对应0.2, 0.4, 0.6, 0.8和1. 直觉上, 设施的用户评级越高, 其在竞争中越有利. 因此, 由于用户评级的存在, 影响显然无法用平分来表示. 考虑到评级能够反映整个用户群体对设施的平均偏好程度, 借鉴时空偏好查询的线性累加质量原则^[10], 本文采用归一化加权平分影响力度量竞争.

定义9 (竞争尺度${{comp}}\left( {u, O} \right)$). 给定用户$u$和其竞争集${S_{{{comp}}}}\left( {u, O} \right)$, 若$o \in {S_{{{comp}}}}\left( {u, O} \right)$, 则$o$针对$u$的归一化加权竞争值可由$\dfrac{{o.rat}}{{comp\left( {u, O} \right)}}$计算得出, 其中分母$comp \left( {u, O} \right) = \displaystyle\sum\nolimits_{{o_i} \in {S_{comp}}\left( {u, O} \right)} {{o_i}.rat = {o_1}.rat + \cdots + {o_i}.rat} + \cdots +$ ${o_m}.rat\left( {{o_i} \in {S_{comp}}\left( {u, O} \right)} \right)$, 称为集合${S_{comp}}\left( {u, O} \right)$在$u$上的竞争尺度, 简称$u$上的竞争尺度.

此时, 可以定义结合设施间竞争和设施用户评级的综合竞争影响值.

定义10 (综合竞争影响值$score\left( {o, O} \right)$). 给定对象集合$O$和特定用户集合$U$, 则对象$o \in O$在考虑$O$中其他对象竞争和各自用户评级的共同作用下, 针对所有用户的综合竞争影响值定义如式(4):

$score\left( {o, O} \right) = \sum\nolimits_{u \in {S_{inf }}\left( o \right)} {\frac{{o.rat}}{{comp\left( {u, O} \right)}}}$

(4)

其中, $u \in {S_{inf }}\left( o \right)$表示对象$o$影响$U$中用户的集合, $o.rat$表示对象$o$的用户评级. 根据定义10, 当给定任意候选$c$, 则其综合竞争影响值可计算为:

$score\left( {c, O \cup \left\{ c \right\}} \right) = \sum\nolimits_{u \in {S_{inf }}\left( c \right)} {\frac{{c.rat}}{{comp\left( {u, O \cup \left\{ c \right\}} \right)}}}$

(5)

其中, $comp\left( {u, O \cup \left\{ c \right\}} \right) = comp\left( {u, O} \right) + c.rat$.

定义11 (CoSTUR). 给定具有空间位置、文本描述和评级的已有设施集合$F$, 具有空间位置和文本描述的用户集合$U$, 空间-文本调节参数$\alpha$和影响力阈值$\tau$. 根据输入的预期建设设施文本描述$des$和评级$rat$, 基于用户评级的空间文本竞争选址问题CoSTUR (competitive spatio-textual location selection based on user rating) 将从候选位置集合$C$中选择输出$k$个最优的候选位置构成子集${C_{opt}} \subseteq C \wedge |{C_{opt}}| = k$, 使得对于$\forall {c_k} \in {C_{opt}} \wedge \forall {c'} \in c\backslash {C_{opt}}$有$score\left( {{c_k}} \right) > score\left( {{c'}} \right)$. 具体来说, 给定已有设施集合作为己方企业的竞争对手, 根据初步选定的建址候选位置集合, 以在竞争环境中吸引更多用户为优化目标, 通过计算各候选综合竞争影响值, 从中选择最优的$k$个候选位置, 以供己方企业进一步决策.

2 策略设计

本研究通过影响阈值的设置, 不仅解决了现有方案中用户只能被唯一设施影响的局限, 也可以帮助选址决策者在更高质量的用户影响估计和更多可能的潜在用户间做出权衡. 针对同类设施间竞争影响力的公式化定义, 完善了融入用户评级对竞争的影响. 接下来, 本文将着力解决在给定用户集合和候选位置集合基数较大时计算代价升高的问题. 本文实验中的用户、已有设施和候选位置等数据集取自New York真实数据集和基于London的合成数据集.

2.1 基线方法

根据前文中问题的公式化定义, 解决CoSTUR最直接的方法是检索所有的用户和现有设施, 找到影响每个用户的用户竞争集, 然后再同样扫描并利用式(5)判断每个候选位置的综合竞争影响值. 过程中需要根据$\alpha$计算设施或候选位置与用户间的空间文本相关性, 若其值大于阈值$\tau$, 则表明影响该用户. 最终, 根据候选位置集合的综合竞争影响值排序, 取出最优的$k$个供决策使用, 称为基线算法Baseline, 具体流程如算法1所示.

基线算法使用HashMap $comp$记录用户$u$上的竞争尺度, 其中键为$u$的id, 值为$u$竞争尺度. 使用大顶堆${\textit{canScore}}$存放按照的综合竞争影响值排序的候选位置, 根据候选位置${c_k}$的id索引. 算法首先初始化$comp$和${\textit{canScore}}$ (第1行). 然后遍历所有用户$U$和现有设施$F$, 找到每个用户的竞争集(第2–9行). 遍历用户集$U$和候选$C$, 过程中根据影响用户与否来决定是否采用式(5)计算某个候选位置的综合竞争影响值(第10–17行), 其中${\textit{canScore}}$通过迭代不断累加每个用户对竞争影响值的贡献(第14行). 最后返回top-$k$个最优候选位置.

算法1. Baseline

输入: $\scriptstyle F, U, C, \tau , \alpha , k$.

输出: top-$\scriptstyle k$ $\scriptstyle c$.

1 Initialize $\scriptstyle comp$, $\scriptstyle {\textit{canScore}}$

2 for $\scriptstyle u \in U$ do

3　 for $\scriptstyle f \in F$ do

4　　 Calculate $\scriptstyle P\left( {u, f} \right)$

5 　　if $\scriptstyle P\left( {u, f} \right) > \tau$ then

6　　　 $\scriptstyle comp\left[ u \right] + = f.rat$

7 　　end if

8 　end for

9 end for

10 for $\scriptstyle u \in U$ do

11 　for $\scriptstyle {c_k} \in C$ do

12 　　Calculate $\scriptstyle P\left( {u, {c_k}} \right)$

13 　　if $\scriptstyle P\left( {u, {c_k}} \right) > \tau$ then

14　　　 $\scriptstyle {\textit{canScore}}\left[ {{c_k}} \right] + = \frac{{{c_k}.rat}}{{comp\left[ u \right] + {c_k}.rat}}$

15　　 end if

16 　end for

17 end for

18 return top-k c in $\scriptstyle {\textit{canScore}}$

2.2 优化方法

为降低基线算法线性扫描的复杂度, 本节分别提出基于范围查询(range query)和空间连接(spatial join)思想的两个优化算法, 结合索引结构和剪枝策略提升计算效率.

空间范围聚集索引结构aR-tree能将节点空间和附带属性进行聚合, 以提升联合检索效率, 该优点适于CoSTUR问题. 图1显示了基于aR-tree构建的索引结构TaR-tree, 它融合了空间和文本属性. 其中, TaR-tree每个节点由聚合空间信息的MBR (minimum bounding rectangle)及聚合文本信息的并集(便于计算Jaccard相似性)组成. 叶子节点的父节点将所包含子节点的位置构造成MBR; 非叶子节点的父节点则将所包含子节点的多个MBR囊括为更大的MBR. TaR-tree将子节点的文本属性逐级向父节点并集聚合, 直至根节点. 遍历TaR-tree的过程中, 可以同时处理空间和文本信息.

2.2.1 基于range query方法

影响阈值$\tau$使得用户可以同时被多个对象影响, 而随着阈值$\tau$的改变, 用户受到对象的影响范围也随之改变. 根据定义1–定义4, 容易反推用户受影响的范围半径, 如式(6)所示:

$d = {D_{\max }}\left[ {1 - \frac{{\tau - \left( {1 - \alpha } \right)T}}{\alpha }} \right]$

(6)

式(6)的具体推导如下(为便于理解, 此处用户与设施之间的距离、空间和文本相关性分别简写为$d$、$S$和$T$: 当$\alpha S + \left( {1 - \alpha } \right)T > \tau$时, $S > \dfrac{{\tau - \left( {1 - \alpha } \right)T}}{\alpha }$, 带入定义1可得$1 - \dfrac{d}{{{D_{\max }}}} > \dfrac{{\tau - \left( {1 - \alpha } \right)T}}{\alpha }$, 即用户和设施间距离$d < {D_{\max }}\left[ {1 - \dfrac{{\tau - \left( {1 - \alpha } \right)T}}{\alpha }} \right]$. 考虑$T \in \left[ {0, 1} \right]$, 当$T$取最大值$1$时, 距离$d$将取其最大值${d_{\max }}$, 若设施与用户间距离超过${d_{\max }}$, 在给定$\tau$和$\alpha$, 该设施必然不会影响用户; 反之, 当$T$取最小值$0$时, 距离$d$将取其最小值${d_{\min }}$, 若设施位于用户${d_{\min }}$范围内, 则必然影响用户. 而对于与用户间距离在$\left( {{d_{\min }}, {d_{\max }}} \right)$范围的设施, 需要根据定义4进一步判断是否影响用户. 用户受与不受影响的范围如图2所示.

根据上述用户必然受影响和必然不受影响区域, 可以结合TaR-tree索引结构进行范围查询. 在用户必然受影响区域内的设施将参与竞争, 而在必然不影响范围内的设施可以直接剪枝. 在上述两个范围间(圆环区域)的设施, 仍需通过定义4进行计算, 若大于阈值$\tau$则参与竞争, 反之则舍弃.

鉴于此, 提出基于范围查询(range query)的解决方案. 由于现有设施$F$事先已知, 因此可以用TaR-tree索引. 当输入特定用户集、候选集和参数$\tau$和$\alpha$后, 利用索引范围查询的性能优势提升效率. 算法2的RangeQuery展示了方法的流程细节.

算法2. RangeQuery

输入: $\scriptstyle U, F, C, \tau , \alpha , k$, TaR-tree $\scriptstyle FT$ of $\scriptstyle F$.

输出: top-$\scriptstyle k$ $\scriptstyle c$.

1 Initialize $\scriptstyle comp,\;{\textit{canScore}}$

2 for $\scriptstyle u \in U$ do

3 　Calculate $\scriptstyle {d_{\max }}$ and $\scriptstyle {d_{\min }}$

4　 Build $\scriptstyle u.rect\_out$ and $\scriptstyle u.rect\_in$

5　 $\scriptstyle S_{comp} \leftarrow rq\left( {u.rect\_out, FT.mbr} \right)$

6　 for $\scriptstyle f \in S_{comp}$ do

7　　 if $\scriptstyle f$ intersects $\scriptstyle u.rect\_in$ or $\scriptstyle P\left( {u, f} \right) > \tau$

8　　　 $\scriptstyle comp\left[ u \right] + = f.rat$

9　　 end if

10　 end for

11 end for

12 for $\scriptstyle u \in U$ do

13　 Build TaR-tree $\scriptstyle CT$ of $\scriptstyle C$

14　 $\scriptstyle S_{comp} \leftarrow rq\left( {u.rect\_out, CT.mbr} \right)$

15　 for $\scriptstyle c \in S_{comp}$ do

16　　 if $\scriptstyle c$ intersects $\scriptstyle u.rect\_in$ or $\scriptstyle P\left( {u, c} \right) > \tau$

17　　　 $\scriptstyle {\textit{canScore}}\left[ c \right] + = \frac{{c.rat}}{{comp\left[ u \right] + c.rat}}$

18　　 end if

19 　end for

20 end for

21 return top-k c in $\scriptstyle {\textit{canScore}}$

RangeQuery算法基线算法使用HashMap $comp$记录用户$u$上的竞争尺度, 其中键为$u$的id, 值为$u$竞争尺度. 使用大顶堆${\textit{canScore}}$存放按照的综合竞争影响值排序的候选位置, 根据候选位置的id索引. 算法首先初始化$comp$和${\textit{canScore}}$ (第1行). 对于每一个用户$u \in U$, 可以根据式(6)计算得到${d_{\max }}$和${d_{\min }}$. 以$u$为圆心, ${d_{\max }}$和${d_{\min }}$为半径, 构造两个MBR范围$u.rect\_out$和$u.rect\_in$ (第2–4行). 然后, 通过在$F$的TaR-tree $FT$上对$u.rect\_out$进行范围查询(算法中用函数$rq$表示), 剔除不参与$u$竞争的设施, 将影响的设施存储在集合$S_{comp}$中(第5行). 然后, 遍历$S_{comp}$中的设施$f$, 对于与$u.rect\_in$相交的设施, 将其用户评级加入用户$u$上的竞争尺度$comp\left[ u \right]$中; 而对于在$\left( {{d_{\min }}, {d_{\max }}} \right)$范围内的设施, 需要根据定义4进一步判断是否影响用户, 若影响则更新用户$u$上的竞争尺度(第6–10行). 然后按照和处理现有设施$F$类似的方式计算$C$中每个候选的综合竞争影响值(第12–20行). 唯一的两处区别在于: 1) 需要先构建$C$的TaR-tree $CT$, 用于进行${d_{\max }}$和${d_{\min }}$的MBR范围查询(第13行); 2) 利用式(5)迭代地计算候选综合竞争影响值(第17行). 基于$CT$的范围查询结束后返回top-$k$个最优候选位置.

2.2.2 基于spatial join方法

空间连接(spatial join)^[11]的核心思想是在不同空间数据集间根据空间谓词进行“连接”操作, 即当两个空间对象间存在如相交(intersect)、包围(enclose)等谓词关系时, 可以进行join匹配.

根据空间连接思想, 可以将设施集(候选集)和用户集视为要进行连接的双方, 参照范围查询思路, 可以使用定义4的阈值判定作为谓词进行匹配. 为更有效地进行数据集空间连接遍历, 用户集也构建为TaR-tree, 利用树的剪枝过程优化计算性能. 该方法将从设施集(候选集)和用户集两棵TaR-tree的根结点开始同时执行深度优先遍历. 若两树中间节点的聚合空间文本相关性大于阈值$\tau$, 即节点间的空间MBR和文本并集满足阈值$\tau$, 递归地进入子一级节点; 反之, 则遍历TaR-tree树的兄弟节点. 此过程直到两树满足条件的节点全部访问结束为止.

按照空间连接阈值判定遍历的逻辑, 遍历结束后可以得到所有对象$o \in O$的${S_{inf }}\left( o \right)$集合, 即对于候选集而言, 每个候选能影响的用户数量可知. 那么能否利用该影响用户数量减少综合竞争影响值的计算和存储结构的读写呢? 前述Baseline和RangeQuery算法均需通过迭代计算所有候选位置的真实综合竞争影响值进行排序, 下面提出一个新的数值上界简化计算过程.

引理1 (综合竞争影响值上界). 对于$\forall u \in {S_{inf }}\left( c \right)$, 在用户评级1–5星离散归一化到对应值$0.2, \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }0.4, \mathrm{ }0.6, \mathrm{ }0.8$和$1$的情况下, $c$的综合竞争影响值上界为$\dfrac{5}{6}$倍的$|{S_{inf }}\left( c \right)|$, 用$scor{e_{\max }}\left( {c, F \cup \left\{ c \right\}} \right) = \dfrac{5}{6}|{S_{inf }}\left( c \right)|$表示.

证明: 当$\exists f \in F \wedge {u_i} \in {S_{inf }}\left( f \right)$时, 若${S_{comp}}\left( {{u_i}, F} \right) = \left\{ F \right\}$, 即此时仅有$f$影响${u_i}$时, ${u_i}$对$comp\left( {f, F} \right)$的贡献值为1, 即$f$独享对${u_i}$的影响. 此时若${u_i} \in {S_{inf }}\left( c \right)$, 根据式(5), 针对${u_i}$有:

$score\left( {c, F \cup \left\{ c \right\}} \right) = \frac{{c.rat}}{{f.rat + c.rat}}$

(7)

由于$0.2 \leqslant c.rat = f.rat \leqslant 1$, 则必有$\dfrac{{0.2}}{{0.2 + 1}} \leqslant \dfrac{{c.rat}}{{f.rat + c.rat}} \leqslant \dfrac{1}{{0.2 + 1}}$, 即 $\dfrac{1}{6} \leqslant \dfrac{{c.rat}}{{f.rat + c.rat}} \leqslant \dfrac{5}{6}$.

当$\exists f, {f'} \in F \wedge {u_i} \in {S_{inf }}\left( f \right) \wedge {u_i} \in {S_{inf }}\left( {{f'}} \right)$时, 即有两个设施$f$和${f'}$同时影响${u_i}$. 若${u_i} \in {S_{inf }}\left( c \right)$, 根据式(7), 有$\dfrac{{0.2}}{{0.2 + 1 \times 2}} \leqslant \dfrac{{c.rat}}{{f.rat + {f^{'}}.rat + c.rat}} \leqslant \dfrac{1}{{0.2 \times 2 + 1}}$, 即$\dfrac{{0.2}}{{2.2}} \leqslant \dfrac{{c.rat}}{{f.rat + {f'}.rat + c.rat}} \leqslant \dfrac{1}{{1.4}}$, 显然$\dfrac{1}{{1.4}} < \dfrac{5}{6}$.

以此类推, 当有更多设施影响${u_i}$时, 必有$score \left( {c, F \cup \left\{ c \right\}} \right) \leqslant \dfrac{1}{{|{S_{comp}}\left( {{u_i}, F} \right)| \times 0.2 + 1}}$. 考虑到$|{S_{comp}}( {u_i}, F )| \geqslant 1$, 因此$score\left( {c, F \cup \left\{ c \right\}} \right) \leqslant \dfrac{5}{6}$. 即$\displaystyle\sum\nolimits_{{u_i} \in {S_{inf }}\left( c \right)} score( c, F \cup \left\{ c \right\} ) \leqslant \dfrac{5}{6}|{S_{inf }}\left( c \right)|$. 证明完毕.

结合空间连接思想和引理1设计了SpatialJoin算法, 具体流程如算法3所示. 与前文两种算法类似, SpatialJoin算法也使用HashMap $comp$记录用户${u_i}$上的竞争尺度, 使用大顶堆${\textit{canScore}}$根据竞争影响值存放排序后的候选位置, 并同样先初始化它们(第2行). 不同点在于算法首先为空间连接构造用户集$U$和候选集$C$的两棵TaR-tree (第1行), 并初始化一个根据候选综合竞争影响值存放的小顶堆$HC$, 且该小顶堆最多存放k个候选(第2行). 算法开始时先利用阈值判定谓词的空间连接函数$sj$处理用户集和设施集两个TaR-tree树的根节点. 遍历将得到影响每个用户${u_i} \in U$的已有设施, 并根据定义9计算${u_i}$上的竞争尺度$comp$ (第3行).

算法3. SpatialJoin

输入: $\scriptstyle U, F, C, \tau , \alpha , k$$\scriptstyle ,$TaR-tree $\scriptstyle FT$ of $\scriptstyle F$.

输出: $\scriptstyle HC$.

1 Build TaR-trees $\scriptstyle UT$ of $\scriptstyle U$, $\scriptstyle CT$of $\scriptstyle C$

2 Initialize $\scriptstyle comp,\; {\textit{canScore}}, \;HC$

3 $\scriptstyle comp \leftarrow sj\left( {UT.root, FT.root} \right)$

4 $\scriptstyle {\textit{canScore}} \leftarrow sj\left( {UT.root, CT.root} \right)$

5 for pop $\scriptstyle c\_top$ from $\scriptstyle {\textit{canScore}}$ do

6 　if $\scriptstyle scor{e_{\max }}\left( {c\_top, F \cup c\_top} \right) < HC\_top$

7 　　break

8 　Calculate $\scriptstyle score\left( {c\_top, F \cup \left\{ {c\_top} \right\}} \right)$

9 　if $\scriptstyle |HC| \geqslant k$

10　　 if $\scriptstyle score\left( {c\_top, F \cup \left\{ {c\_top} \right\}} \right) > HC\_top$

11　　　　 pop $\scriptstyle HC$

12 　　　insert $\scriptstyle \left\langle {c\_top, score\left( {c\_top, F \cup \left\{ {c\_top} \right\}} \right)} \right\rangle$ to $\scriptstyle HC$

13　　 end if

14　 else insert $\scriptstyle \left\langle {c\_top, score\left( {c\_top, F \cup \left\{ {c\_top} \right\}} \right)} \right\rangle$ to $\scriptstyle HC$

15 　end if

16 return $\scriptstyle HC$

接下来利用空间连接函数$sj$处理用户集和候选位置集两个TaR-tree树的根节点. 根据引理1, 直接计算每个候选位置的综合竞争影响值上界$scor{e_{\max }}\left( {c, F \cup \left\{ c \right\}} \right)$并存储到大顶堆${\textit{canScore}}$当中. 此时${\textit{canScore}}$堆顶是所有候选位置综合竞争影响值上界的最大值(第4行). 考虑到上界更大的候选, 其计算出的综合竞争影响值$score\left( {c, F \cup \left\{ c \right\}} \right)$也可能较大, 因此, 从${\textit{canScore}}$堆顶中逐一弹出候选, 并计算实际综合竞争影响值(第8行). top-$k$候选位置的实际综合竞争影响值存放在小顶堆$HC$中. 当$HC$堆中数据量少于$k$时, 可以直接压入$HC$; 反之, 需要将候选$c$的$score\left( {c, F \cup \left\{ c \right\}} \right)$和$HC$堆顶的候选进行比较, 如果$HC$堆顶值较小, 则弹出堆顶并压入候选$c$的值, 否则处理下一个${\textit{canScore}}$堆顶元素(第9–14行). 当发现$HC$堆顶候选的综合竞争影响值大于${\textit{canScore}}$堆顶中候选的上界时, 意味着此时${\textit{canScore}}$堆中不可能再有候选的实际综合竞争影响值大于当前$HC$堆中的top-$k$候选位置, 此时针对${\textit{canScore}}$堆的遍历结束(第6, 7行). $HC$堆中的top-$k$候选位置即为结果(第16行).

2.3 算法复杂度分析

本节对前述各解决方案的计算复杂度进行理论分析, 其中定义4的计算作为原子操作.

基线方法Baseline采用线性扫描方法遍历用户集、候选位置集和已有设施集, 方法的时间复杂度为${\mathrm{O}}\left( {|F| \cdot |U| + |C| \cdot |U|} \right)$.

在结合TaR-tree、${d_{\max }}$和${d_{\min }}$的RangeQuery算法中, 假定TaR-tree每个节点有$n$个子节点. 对于用户集合与设施该TaR-tree的范围查找, 其时间复杂度为${\mathrm{O}}\left( {|U|{{\log }_n}|F|} \right)$. 对于用户集与候选集间的计算, 首先需要构建候选TaR-tree, 时间复杂度为${\mathrm{O}}\left( {|C|{{\log }_n}|C|} \right)$; 然后进行范围查找, 时间复杂度为${\mathrm{O}}\left( {|U|{{\log }_n}|C|} \right)$. 考虑到${d_{\max }}$和${d_{\min }}$的作用, 则整个算法的时间复杂度为${\mathrm{O}}( |U|{{\log }_n}|{F'}| + {\mathrm{O}}\left( {|C|{{\log }_n}|C|} \right) + {\mathrm{O}}\left( {|U|{{\log }_n}|{C'}|} \right) )$, 其中$|{F'}| < |F| \wedge |{C'}| < |C|$.

SpatialJoin算法利用TaR-tree之间的空间连接思想. 首先构建用户集与候选集TaR-tree需要${\mathrm{O}}( |U|{{\log }_n}|U| + {\mathrm{O}}\left( {|C|{{\log }_n}|C|} \right) )$复杂度. 空间连接遍历过程理论时间复杂度为${\mathrm{O}}\left( {{{\log }_n}|F|{{\log }_n}|U| + {{\log }_n}|U|{{\log }_n}|C|} \right)$. 最终根据引理1的上界, 遍历大顶堆的计算复杂度可以认为接近${\mathrm{O}}\left(1\right)$. 算法最终时间复杂度为${\mathrm{O}}(\left(\left|U\right|+{\mathrm{log}}_{n}\left|F\right|\right){\mathrm{log}}_{n}\left|U\right|+ \left(\left|C\right|+{\mathrm{log}}_{n}\left|U\right|\right){\mathrm{log}}_{n}\left|C\right|).$

容易看出RangeQuery算法和SpatialJoin算法的时间复杂度明显低于基线方法.

3 实验论证与分析 3.1 实验设置 3.1.1 实验数据集

本文实验中的用户、已有设施和候选位置等数据集取自New York真实数据集和基于London的合成数据集. 其中后者是由真实POI设施位置随机捕获一组POI文本数据的方式合成, 数据特征如表1所示. 所选数据集为不同国家区域的开源数据集, 有助于体现本文研究方法和实验结果的普适性.

经数据抽样, 用户和设施间空间相关性和文本相关性均值分别在0.7和0.1附近, 差距较大. 为使空间相关性和文本相关性的$\alpha$权衡参数具有可比性, 利用高斯函数归一化方法将文本相关性归一化到均值0.7, 则用户和设施间空间文本相关性均值接近0.8. 实验若无明确说明, 将采用如下默认实验参数: 影响阈值$\tau = 0.9$, $k = 10$, 平衡参数$\alpha = 0.6$, 候选位置数量$|C| = 200$, 在London和New York数据集中用户数量$|U|$默认分别设为5.5k和5k. 其中$\tau$设为0.9是为了更准确地估计设施对潜在用户的影响; $\alpha$设为0.6是使该参数更接近数据样本均值, 以得到更有意义的实验结果.

3.1.2 实验环境与评估算法

以下解决方案将在本节进行评估, 实验采用Python语言编码, 环境为Windows 10 (64位), Intel(R) i5-13600KF 3.5 GHz, 内存16 GB.

实验分别评估本文第2.1节Baseline算法, 第2.2.1 RangeQuery算法, 第2.2.2节SpatialJoin算法.

3.2 实验结果 3.2.1 阈值$\tau$的影响

验证影响阈值$\tau$变化对性能产生的影响, $\tau$的取值分别为0.8、0.85、0.9和0.95. 由图3展示的实验结果可知, 3种算法中Baseline效率最差, 影响阈值$\tau$的变化对其影响不大, 而RangeQuery和SpatialJoin性能随影响阈值$\tau$的增大相比基线算法的优势愈发显著. 这意味着$\tau$越大时, 可能影响的潜在顾客越准确, 用户数量也越少, 剪枝效果越明显; 反之, 可能影响的顾客越多, 剪枝收益随之下降.

如图3(a)所示, SpatialJoin性能在London数据集上提升更理想, 这很大程度上取决于其计算复杂度优势. 图3(b)中New York数据集上情况则相对复杂. 当影响阈值$\tau$较小时RangeQuery效果更优, 反之SpatialJoin性能稍好. 其原因在于New York和London数据集空间范围相近(分别是59 km和56 km), 但前者竞争设施更密集, 当影响阈值$\tau$变小时${d_{\max }}$和${d_{\min }}$对剪枝的贡献更明显.

3.2.2 用户数量$|U|$的影响

接下来针对输入用户数据集规模$|U|$, 验证不同方法影响的情况. 对于London和New York数据集, $|U|$的取值分别为{1000, 2500, 4000, 5500, 7000}和{1250, 2500, 5000, 10000, 20000}. 从图4可以观察到, Baseline方法的时间开销随$|U|$呈线性增长, 这与两个数据集中$|U|$数量增长方式一致. 而SpatialJoin和RangeQuery算法时间开销同样随着$|U|$的增加而提高, 但相比Baseline方法均能提升一个量级的性能, 其中SpatialJoin提升更优. 这说明实验结果和理论分析是一致的, 即文中提出的索引结构结合剪枝及综合竞争影响值上界均起到了作用.

3.2.3 候选位置$|C|$的影响

将候选位置$|C|$数量分别设置为200、400、600、800和1000时, 分析3种算法对效率的影响. 如图5所示, 实验结果在数量上和$|U|$对结果的影响十分类似, 3种算法中同样是SpatialJoin算法效率最优, RangeQuery次之, 二者均能提供超过Baseline一个量级的性能提升. 对比图5(a)和图5(b), 可以发现在London数据集上性能随$|C|$的增长下降的更快, 说明现有设施越多, 候选位置$|C|$由于竞争的原因, 对性能的影响越不明显, 算法的效果也相对更稳定.

3.2.4 $k$值变化

本部分的实验着眼于验证$k$变化对算法影响, 其中$k$取值为10–50的离散值. 如图6(a)和图6(b)所示, 3种算法中SpatialJoin算法效率最优, RangeQuery次之, 这两种方法均能提供超过Baseline近一个量级的性能提升. 注意到$k$值的变化对所有算法的效率几乎都不会产生影响, 这一点从第2.3节理论分析就可以看出, 即$k$值并不影响算法的时间复杂度.

4 相关研究

空间文本位置选择问题: Ahmed等人^[12]提出反向空间top-k关键字查询(RSK), 并采用网格索引划分数据集, 其中每个网格存储关键字频率表, 本文的索引结构设计也借鉴了其思想. Choudhury等人^[2]提出了MaxBRSTkNN查询的经典空间文本选址模型, 为本研究的选址模型提供了理论支撑. 文献[13]是对Choudhury等人^[2]研究的扩展, 提出了一种最大化双色反向空间文本最近邻查询(MaxST), 并在有阻碍和无阻碍空间中, 为对象寻找最佳位置和一组关键字. Chen等人^[14]将研究扩展至路网环境, 其反向top-k关键字的位置查询(RTkKL)旨在找到最大空间区域, 以便将查询对象包含在任何top-k空间关键字查询的结果中. 该研究的路网场景与本文模型不相符, 但可考虑作为未来的研究方向. 上述研究解决了各自应用场景中的问题, 然而均未考虑设施之间的竞争因素, 难以直接用于应对CoSTUR问题的挑战.

设施竞争位置选择问题: 传统的竞争性选址问题^[15]假设一家新公司将入驻存在现有公司运营的市场, 其最佳选址期望在竞争中争夺最大的市场份额. Revelle^[16]引入新的竞争选址问题, 它在现有设施的基础上增加了新设施, 使新设施群的影响力最大化扩展. 其中若两个设施捕获同一对象, 则会平分对它的影响, 这与CoSTUR依据的经典竞争影响模型相同, 但该模型其未考虑设施评级. Huang等人^[17]基于最大影响力模型考虑现有设施对选址的影响, 影响关系的定义以最近邻为基础. Liu等人^[8]将竞争问题扩展到运动对象, 使用影响关系剪枝规则和影响值剪枝规则来加速查询过程. 现有竞争选址研究尽管有些也采用和本文相同的竞争影响模型, 但均未考虑设施和对象的文本因素, 也缺少对设施评级的应对, 方法不适用CoSTUR问题.

5 结束语

本文引入一个称为CoSTUR的新型空间文本位置选择问题, 并提供了两种有效且高效的解决方案. 相比于经典空间文本选址问题, CoSTUR问题综合考虑了用户可以同时被多个设施影响、同类设施间存在竞争, 及用户评级对竞争的影响等因素. 该问题在现实世界中应用广泛, 如城市规划、市场营销、LBS等. 提出的其中一种算法基于范围查询思想, 通过构建必然影响/不影响的两个新剪枝距离范围, 结合空间文本索引TaR-tree, 能够有效解决问题. 另一种方法建立在空间连接思想上, 利用一个新的分值上界简化计算过程. 在真实及合成数据集上的大量实验证明了所提方法的有效性和高效性.