新的LBS系统

Abstract

1. 现有LBS基于单一POI，而现实里用户需要多POI的LBS
2. 本文将单一POI的LBS扩展为使用单个查询请求多个POI的LBS

Introduction

1. 场景：用户希望同时查询某地点附近的多个兴趣点（例如饭店和KTV都需要）
2. 和单兴趣点推荐的差别：要综合考虑多个兴趣点的评价和距离以及用户需求，例如吃完饭去KTV这种场景就需要推荐的饭店和KTV近一些
3. 本文实现的功能：
   1. Ranking mode（排序模式）：根据每个兴趣点的评价和兴趣点之间的距离，提供一个按评分排序的列表中的前K个兴趣点组合
   2. Service area mode（服务区模式）：找出一个包含了最多兴趣点的矩形区域
4. 挑战性：
   1. 受限于兴趣点之间的距离，实现”N-in-One”与单纯找N个相互独立的兴趣点并不同；
   2. 服务区模式可能会有木桶效应问题：返回的聚类结果可能因为有一个或多个热门兴趣点被排除。
5. 本文提出：
   1. 排序模式：基于平面扫描算法，垂直线从右往左扫描兴趣点区域，遇到兴趣点时回溯和已经记录的兴趣点匹配，以查找最优K聚类；为实现回溯过程中的POI匹配，引入“可查看网络”；
   2. 服务区模式：引入“瓶颈值”来描述 POI 的重复使用数，使用计算几何来识别给定大小的矩形，该矩形可以覆盖尽可能多的最佳Q群集，同时减少木桶效应。
6. 本文组织结构：
   1. 第二部分、第三部分分别介绍排序模式和服务区模式
   2. 第四部分仿真实验
   3. 第五部分相关研究
   4. 第六部分总结

“N-IN-ONE” LBS IN THE RANKING MODE

Metric to Evaluate a POI Cluster

POI聚类$\Pi=\{p_1,…,p_N\}$，其中$p_j$是第$j$个兴趣点位置

定义1 POI聚类的直径：覆盖该聚类所有兴趣点的最小圆直径

定义2 POI聚类的中心：覆盖该聚类所有兴趣点的最小圆圆心

最小圆问题：直径取决于聚类中距离最远的两点之间的距离上限

评估函数：

$$R(\Pi)=\sum_{j=1}^{N}\alpha_je_j-\beta D(\Pi)-\gamma d(\Pi,c)$$

其中，$e_j$是对该聚类内第$j$个兴趣点的评估值，$\alpha_j$是对应的权重；$D(\Pi)$是聚类的直径，体现了聚类的离散程度，$\beta$是对应的权重；$d(\Pi,c)$是当前位置$c$到聚类中心的距离，$\gamma$是对应权重。所有权重由用户自己决定。

Overview of Our Algorithm for the Ranking Mode

用户兴趣区域内有$n$个POI，集合表示为$\Omega$，$||\Omega||=n$

算法流程：

1. 所有POI根据x坐标升序排列（即标号大的POI出现在右边）
2. 垂直线从右向左扫描兴趣区域
3. 当垂直线扫到了某个POI，算法会检查之前找到的POI聚类，并将该POI加到之前的聚类中形成新聚类，聚类中所有元素的POI类型在任何时刻都不同
4. 基于新聚类，更新最优K结果
5. 当兴趣区域内的POI都被扫描过时，上述过程结束，最终的最优K结果被推送给用户

关键问题：扫描到一个POI时，如何从之前的POI集合中高效识别那些需要被回溯的

解决方法：引入可视网络的概念，$N=(\Omega,E)$，$\Omega$是兴趣点集合，E是可视线集合

可视线：由扫描到的POI及其可视点之一决定。当扫描到某个POI $P_i$时，算法根据其可视线回溯L层邻近POI

L层邻近POI：可视网络中，比$P_i$扫描得早、且从$P_i$出发可通过最多L个可视线到达的POI

采用递归方法，整体分为两步：

1. 构建可视网络
2. 移动和回溯

Constructing the Viewable Network

构建可视网络的思路大致是：从右向左扫描点（也就是从最后一个点开始），每扫描到一个点就看它右边是否有没被挡住可以直接相连的点，如果有就连起来，这样一直扫到最左边的点（也就是第一个点），网络就构建好了。

实际上这个网络扫描的方向并不一定要这样，也可以从左往右。

时间复杂度的分析和证明省略。

该算法的具体流程如下：

​ 输入：POI集合根据x坐标升序排列

1. 扫描线自右向左扫描
2. 当扫描到$P_n$、$P_{n-1}$、$P_{n-2}$的时候：
   1. $P_n$、$P_{n-1}$、$P_{n-2}$加到集合V里，集合V用来存放已经扫描过的点；
   2. 如果$P_i$是集合V的凸包的顶点，就把$P_i$加到集合$C^P(V)$里；
   3. 如果$L_i$是集合V的凸包的边，就把$L_i$加到集合$C^E(V)$里；
   4. 把集合$C^E(V)$加到集合E里，集合E用来存放可视线；
3. 令$i=n-2$
4. 重复循环一下流程：
   1. 令$i=i-1$
   2. 遍历集合$C^P(V)$中的点记作$P_k$，如果点$P_i$、$P_k$之间的连线与集合$C^E(V)$的交集是点$P_k$，则把$P_k$加入集合$A_i$，集合$A_i$用来存放点$P_i$的可视点
   3. 遍历集合$A_i$中的所有$P_k$，把点$P_i$、$P_k$之间的连线加入到之前的边集合E中
   4. 把$P_i$加入集合V中
   5. 按之前的规则更新集合$C^P(V)$和$C^E(V)$
5. $i=0$时结束循环，集合E就是所有可视边

Searching Heterogeneous POIs

1. 总共有$n$个兴趣点
2. 兴趣点异构，总共有$j$个类型
3. 有$j$个异构兴趣点的聚类的集合记作$G_j$，而$G_1$是有$n$个聚类的集合，其中每个聚类都包含一个兴趣点
4. 垂直线从第$n-j+1$个点开始扫描，L层邻接POI集合最多有$j$个POI，这也是构建包含j-1个异构兴趣点的聚类的最小兴趣点编号
5. 整个算法递归地根据$G_{j-1}$计算$G_j$，具体过程如下：
   1. 每当扫描到一个兴趣点$P_i$时，遍历$G_{j-1}$中的聚类，如果某个聚类属于$P_i$的L层邻接POI集合，则把该聚类加到一个新集合$S_{i,j-1}$中
   2. 第一步中的聚类遍历结束后，遍历得到的集合$S_{i,j-1}$中的聚类，如果$P_i$和这个聚类异构，则把$P_i$和这个聚类组成的集合加到集合$G_j$中
   3. 继续用同样的思路扫描兴趣点$P_{i-1}$，这样循环直到$P_1$被扫描完
   4. 最终得到$G_j$作为异构兴趣点聚类

复杂度分析省略。

Searching the Best K Results in the Ranking Mode

算法1构建可视网络得到的可视线记作$E$；算法2寻找异构兴趣点聚类的集合记作$G_{N-1}$（它包括所有具有N-1个异构兴趣点的聚类）；兴趣点$P_i$的L层邻接兴趣点记作$L_i$。

1. 从第$i=n-N+1$个兴趣点开始，从右向左扫描所有兴趣点
2. 遍历$G_{N-1}$中的聚类，如果聚类属于$L_i$，则把聚类加到一个新集合$S_{i,N-1}$中
3. 遍历新集合$S_{i,N-1}$中的聚类，如果$P_i$和聚类异构，则把$P_i$和这个聚类组成的集合插入到列表B中，插入顺序按聚类的评价降序
4. 如果列表B中的元素个数大于K，则删去最后一个元素
5. 继续扫描第$i-1$个兴趣点，执行相同的操作，直到扫描到$P_1$

复杂度分析省略。

“N-IN-ONE” LBS IN THE SERVICE AREA MODE

服务区：给定长宽的矩形区域，该区域内的兴趣点密度最大，且所有兴趣点都属于最优Q聚类

矩形区域的权重受三个因素影响：

1. 矩形覆盖的最优兴趣点聚类个数
2. 矩形内的兴趣点聚类评分
3. 兴趣点聚类的分布

定义3.1 如果一个兴趣点聚类$\Pi$的中心在某区域$\Gamma$内，则称该聚类在该区域内。

就此将聚类视作其中心点，将该问题转变为maximizing range sum（最大子序列？）

当一个兴趣点属于多个聚类时，我们称它被多个聚类复用了。这种情况如果该兴趣点不可用，则会导致区域内大量聚类都不可用，这不好。

定义3.2 一个矩形区域内聚类集合的瓶颈值$B$是指，该区域内被复用次数最多的兴趣点所对应的复用次数。

定义3.3 矩形的权重由该区域内聚类的评分和该区域的瓶颈值决定，计算公式如下：

$$W(C)=\varepsilon\sum_{\Pi\in C}R(\Pi)-\eta B$$

其中，$\varepsilon$和$\eta$都是常数系数。

找服务区的算法流程：

复杂度分析省略。

PERFORMANCE EVALUATION

Performance Evaluation Based on Synthetic Data

Performance Evaluation Based on Real-World Data

实验部分不看了，省略。

RELATED WORK

当前LBS领域的热点研究：基于位置信息的推荐系统，尤其是兴趣点推荐

1. 潜在Dirichlet分配（LDA）
2. 朴素贝叶斯
3. 地理概率分析框架，策略性地考虑多个因素
4. 动态聚类算法识别运动轨迹

路线推荐同样热门

1. 分析用户交通路线来得到两地之间最受欢迎的路线
2. 基于集体知识的路线推荐框架
3. 候选-生成-验证策略得到K近邻轨迹
4. KNN+更多因素的分析
5. LIT前缀挖掘算法
6. 网络优化问题
7. 轨迹大数据

本文和上述内容的共同点：给用户返回多个POI

不同点：本文侧重查询，是LBS的基础服务；上述侧重推荐，是LBS的衍生服务

本文的创新性：现有LBS的基础服务不涉及多POI查询，本文针对基础服务进行了改进

CONCLUSION AND FUTURE WORK