3.2 传感器和设施部署

在城市感知程序中，我们需要在收集数据之前在静态位置或移动对象上部署传感器和设施。在哪里部署这些传感器和设施成为我们需要解决的首要问题。本节介绍了四种传感器和设施部署模型，可用于解决不同应用的问题。

3.2.1 寻找最佳汇合点

寻找最佳汇合点也称为 设施定位问题 ，已经在运筹学和数据库社区中得到广泛研究。根据目标函数，为解决这一问题提出的模型可以分为两类：最小和（minsum） ^[3] 以及最小最大（minmax） ^[11] 模型。最小和模型旨在定位 k 个设施，使到达所有客户的平均成本最小，最小最大模型则旨在最小化到达这些客户的最高成本。

给定两个数据集： C ={ c ₁ ， c ₂ ，…， c _n }表示客户， F ={ f ₁ ， f ₂ ，…， f _m }表示设施。设施定位问题是要从 F 中找到一个由 k 个位置组成的集合 R ，使得

其中cost（ c _i ， R′ ）表示客户 c _i 与集合 R ′中任何设施 f 之间的最小成本。成本可以是旅行时间、距离或费用。当使用距离作为成本时，有两种主要的度量方式：欧几里得距离和网络距离。

图3.3分别为这两种模型提供了示例，用欧几里得距离作为成本度量。当设置 k =1（即寻找最佳地点）时，最小和模型会选择 f ₁ 作为四个客户 c ₁ 、 c ₂ 、 c ₃ 和 c ₄ 的最佳汇合点。然而，最小最大模型会选择 f ₂ ，因为 f ₁ 和 c ₄ 之间的距离大于 f ₂ 和客户之间的距离。这两个模型有不同的应用场景。例如，政府希望在选举中为 k 个投票站选址，使得选民到最近投票站的平均距离最小。这个问题应该由最小和模型来解决。另一个例子是使用最小最大模型在城市中设置消防站，以使到达火灾现场的最大时间最小。

无论使用哪种模型来解决设施定位问题，该问题都是NP困难的。为此，开辟了一个研究分支，例如局部搜索启发式方法 ^[3] 、伪近似方法 ^[36] 和最远点聚类启发式方法 ^[21] ，以近似解决这一问题，并确保性能。

3.2.1.1 局部搜索启发式方法和伪近似方法

关于最小和模型，局部搜索启发式方法 ^[3] 是一个广泛使用的解决方案，它提供了一个在最优值5倍以内的近似。给定一个初始位置集 R _ini ，局部搜索启发式方法尝试用集合{ F-R _ini }中的每个候选设施 f 替换 R _ini 中的每个当前位置，并估计这种替换的距离减少量。在所有这些尝试性替换中，距离减少量最大的那个将得到执行。局部搜索启发式方法的一个著名实现是围绕中位数的分割（PAM） ^[14] 。

图3.4通过一个例子说明了PAM方法，该例子旨在从三个候选设施{ f ₁ ， f ₂ ， f ₃ }中选择两个最优位置，服务四个客户{ c ₁ ， c ₂ ， c ₃ ， c ₄ }。初始位置集是{ f ₁ ， f ₂ }，总距离为17。如果我们用 f ₃ 替换 f ₁ ，如图3.4b所示，总距离将减少到13。同样，如果我们用 f ₃ 替换 f ₂ ，如图3.4c所示，总距离将减少到12。也就是说，后者的替换更有效。因此，{ f ₁ ， f ₃ }被选为最优的2位置集。如果可以同时交换 p 个位置，近似保证可以进一步提高到3+2/ p 。实际的差距通常远小于这些上限。伪近似方法将近似保证从3+2/ p 提高到 ，尽管运行时间更长 ^[36] 。

3.2.1.2 最远点聚类启发式方法

对于最小最大模型，最远点聚类启发式方法 ^[21] 是一个广泛使用的算法，可以提供最优值2倍以内的近似。使用这个算法寻找 k 最优位置集也被称为 k 中心问题 。图3.5展示了最远点聚类启发式的一个例子，它从四个候选位置中为五个客户找到三最优位置集。算法首先任意选择 f ₁ 加入结果集 R 。然后，由于 f ₄ 与 R ={ f ₁ }的距离最远，将其加入结果集。最后，由于当 R ={ f ₁ ， f ₄ }时， d （ f ₃ ， R ）最大，将 f ₃ 加入 R ，其中 d （ f ₃ ， R ）表示 f ₃ 与 R 中任何设施的最小距离。显然，dist（ f ₃ ， f ₄ ）大于dist（ f ₁ ， f ₂ ）。因此，最终结果集 R ={ f ₁ ， f ₃ ， f ₄ }。

正式地，算法的过程可以定义如下：

1.从 F 中任意选择一个位置 f 并将其添加到结果集 R 中。

2.计算位置 f 与 F-R 中每个设施 f ′之间的距离，并选择最小距离来表示 d （ f′ ， R ）。

3.将 f =arg max _{f′ ⊂ F-R} d （ f′ ， R ）与 R 相加，直到| R |= k 。

尽管前述的近似解决方案显著减少了解决设施定位问题的时间，但在面对大数据时，它们仍然非常耗时。为了在欧几里得空间中加速局部搜索启发式方法，参考文献 ^[14] 提出了几种数据库技术（例如候选分组和最佳优先搜索）来有效地修剪不具前景的候选位置。参考文献 ^[50] 提出了一个高效的框架，该框架同时考虑了欧几里得距离和网络距离。然而，这个框架只能解决 k =1的设施定位问题。

在某些应用场景中，已经部署一些设施，我们尝试添加额外的设施或将一些现有设施移动到新位置，以最小化成本函数 ^{[11，43，49]} 。可以简单地修改PAM和最远点聚类启发式方法来解决这两个问题，分别使用最小和模型和最小最大模型。

最近，Li等人 ^[38] 建议在城市中重新定位救护站，试图基于一个三步法最小化到达整个城市中紧急请求发生处的平均行程时间。与之前的研究不同，在考虑欧几里得和网络距离的同时，Li和Zheng的解决方案使用救护车的实际行程时间作为成本衡量标准。图3.6通过一个有十个客户和六个候选位置{ f ₁ ， f ₂ ， f ₃ ， f ₄ ， f ₅ ， f ₆ }的例子说明了这种方法。

第一步如图3.6a所示，该方法对客户端应用 k 中心聚类 算法（本例中 k =2），选择靠近 k 个簇的中心的候选位置（即 f ₁ 和 f ₆ ）作为最小和模型的初始点。良好的初始点可以显著减少进一步替换计算的负载。

第二步如图3.6b所示，该方法将候选位置分组，计算客户端与一组候选位置（例如 f ₂ 和 f ₃ ）之间的行程时间的下界。实际上，每个客户端与候选位置之间的行程时间可以预先计算，因为将在替换过程中重复使用多次。

第三步进行多次迭代，每次迭代旨在用其他候选位置替换前几轮中选定的位置，如 f ₁ 。每次迭代进一步由许多替换组成，每次替换都尝试找到一组候选位置来替换 f ₁ 。例如，我们尝试用一组候选位置 f ₂ 和 f ₃ 替换 f ₁ 。对候选组可以进行修剪，也就是说，如果候选组的行程时间下界大于 f ₁ ，就不需要用组中的每个单独元素来替换 f ₁ 。这样的分组和修剪策略可以减少每次迭代中的替换次数，特别是在一个组中有许多候选位置的情况下。当一个候选组（例如 f ₄ 和 f ₅ ）不能被修剪时，我们将进一步检查组中每个元素的替换可能性。如果 f ₁ 无法被替换，那么我们将在另一次迭代中尝试替换 f ₆ 。

3.2.2 最大化覆盖范围

3.2.2.1 最大覆盖问题

最大覆盖问题也称为最大 k 覆盖问题，近几十年来获得了广泛研究。一个典型的例子是从图中选择 k 个节点，使这些节点的单跳邻接集合最大。另一个例子是找到包含最多主题数的 k 篇文章。这个问题的形式化定义如下：给定一个整数 k 、一个全集 E 和一个子集集合 S =（ s ₁ ， s ₂ ，…， s _m ），从 S 中选择 k 个子集来组成一个并集 s ′，使得 最大，其中 y _j 表示是否有元素 e _j ∈ E 被 s ′覆盖，如果 e _j 被覆盖则 y _j =1，否则 y _j =0。

问题也可以表示为整数线性规划（ILP），如下所示：

其中 x _i 表示是否选择了 s _i 。如果 s _i 被选入结果集，则 x _i =1，否则 x _i =0。

例如，如图3.7所示，有三个子集{ s ₁ ， s ₂ ， s ₃ }覆盖了 E ={ e ₁ ， e ₂ ， e ₃ ，…， e ₈ }中的八个元素。{ s ₂ ， s ₃ }是最大2覆盖集合，因为它包含所有元素，而{ s ₁ ， s ₃ }缺少了 e ₆ ，{ s ₁ ， s ₂ }缺少了{ e ₇ ， e ₈ }。

最大覆盖问题是NP困难的，因此计算量很大。文献 ^[15] 中提出的贪婪启发式算法具有最佳的多项式时间解，并带有（1-1/e）的近似保证。贪婪算法执行以下两个阶段的 k 次迭代：

1. 选择阶段 。在这个阶段，贪婪启发式算法将具有最大覆盖增加的子集 s _i 插入当前迭代的结果集中。

2. 更新阶段 。在这个阶段，从未选择的子集中移除已经被 s _i 覆盖的元素。

我们以图3.7b为例说明了贪婪启发式算法。在第一次迭代中，贪婪算法将子集 s ₁ 添加到结果集中，因为它覆盖了最多的元素（即5个）。然后在更新阶段，从未选择的子集{ s ₂ ， s ₃ }中移除被 s ₁ 覆盖的元素{ e ₁ ， e ₂ ， e ₃ ， e ₄ ， e ₅ }。假设 k =2，在第二次迭代中，贪婪算法将添加覆盖另外两个元素的 s ₃ 到结果集中，因为 s ₂ 只覆盖了一个新元素。因此，最终解是{ s ₁ ， s ₃ }，覆盖了七个元素。显然，这不是最优解，最优解应该是{ s ₂ ， s ₃ }。

3.2.2.2 加权最大覆盖问题

在加权版本中，通用集合 E 中的每个元素 e _j 都与一个权重 w （ e _j ）相关联。目标是选择 k 个子集，这些子集具有最大的覆盖权重。加权版本的正式定义如下：

贪婪启发式算法也可以用来解决加权最大覆盖问题，在选择阶段选择权重最大的子集，而不是覆盖元素最多的子集。经过轻微修改，贪婪算法也能达到（1-1/e）的近似比。

3.2.2.3 预算约束最大覆盖问题

在一些应用场景中，当每个子集 s _i 与一个成本 c （ s _i ）相关联时，会指定一个预算约束 B 。例如，在设施定位问题中，不同地点可能需要不同的设立成本。我们正式定义预算约束最大覆盖问题如下：

为了解决预算约束最大覆盖问题，参考文献 ^[31] 提出了一个算法，当固定整数 k ≥3时，该算法具有（1-1/e）的近似比。尽管 k 表示要选择的子集数量，但它并不是问题的约束。这个算法的伪代码在图3.8中给出。

正如第1行所示，这个解决方案首先探索所有基数小于 k 且成本小于 B 的 S 的子集，找到权重最大的子集 G 。然后算法搜索每个基数等于 δ 且成本小于 B 的 S 的子集，用 R 表示，如第3行所示。对于每个 R ，算法从 S 的剩余部分（即 U ）中选择一个元素 s _i ，如果更新后的成本仍然小于 B ，则将 s _i 添加到 R 中。这里提出了一种启发式方法来选择 s _i ，计算方法为 w′ （ s _i ） /c （ s _i ），其中 w′ （ s _i ）是添加 s _i 后的增量权重。上述操作（第6～9行）重复迭代，直到 U 中的所有元素都被测试过。在测试迭代之后，我们找到对应 R 的近似最优解。算法尝试所有可能的满足第3行所示标准的 R ，选择最佳的 H ₂ 。最后，返回 H ₁ 和 H ₂ 中权重较大的一个作为最终结果（第12行）。

3.2.2.4 最具影响力的 k 位置集问题

最近，Li等人 ^[37] 提出了挖掘有最多辆车穿过的最具影响力的 k 位置集的问题。该问题的正式定义如下：给定一个用户指定的空间区域 R 、一个 k 值、一组轨迹Tr，以及 R 中的空间网络表示 G _s =（ V _s ， E _s ）， R 中最具影响力的 k 位置集，在 V _s 中找到 k 个位置（顶点），使得被这 k 个位置覆盖的唯一轨迹的总数最大。

挖掘最具影响力的 k 位置集可以映射为带有两个额外挑战的最大 k 覆盖问题。第一个挑战是不同的用户可能对在不同空间区域内挖掘 k 个位置感兴趣。例如，如图3.9a所示，两个当地商家希望在两个不同区域放置不同数量的广告牌，这就要求分别计算两个区域内最具影响力的 k 位置集。感兴趣的空间区域的变化导致新一轮的计算。第二个挑战是用户（例如，领域专家）可能需要多次与挖掘系统交互，将他们的领域知识融入挖掘过程中。例如，如图3.9b所示，{ c ₂ ， c ₄ }是覆盖迁徙鸟类轨迹最多的2位置集。但是，由于 c ₄ 位于一个湖中，我们无法找到土地来放置观察站，因此需要将其从结果集中移除。最终，{ c ₂ ， c ₄ }成为备选结果。

图3.10展示了挖掘最具影响力的 k 位置集的框架，它包括两个主要模块：预处理和位置集挖掘。如图3.10左侧所示，第一个模块通过三个步骤处理轨迹数据集：

1. 空间网络映射 将原始轨迹投影到一个空间网络上，这个空间网络可以是道路网络、网格划分或者停留点的集群。

2. 建立倒置轨迹索引 为每个顶点生成两种类型的索引。一种是顶点-轨迹索引，用于管理穿过顶点的轨迹。另一种是顶点-顶点索引，用于管理两个顶点之间共享的轨迹ID。

3. 空间索引 根据顶点的空间坐标使用空间索引结构（如四叉树或R树）对顶点进行组织。

如图3.10右侧所示，位置集挖掘模块接收用户查询参数，包括空间范围 R 、 k 值和一组预先标记的顶点作为输入，并通过迭代选择和更新这两个步骤找到 k 个位置。在选择阶段，算法选择在当前迭代中具有最大轨迹覆盖的顶点，并将其放入结果集。在更新阶段，算法通过从它们的覆盖中移除新覆盖的轨迹来更新所有未选择顶点的覆盖值。然而，当轨迹数据集非常大时，移除新覆盖的轨迹是耗时的。基于预处理模块中构建的索引，更新阶段的效率显著提高。

3.2.3 学习排序候选位置

在城市规划中，我们可以对一组位置进行排序，选择前 k 个最佳候选位置来部署资源或设施。例如，为了开设一个盈利的购物中心，我们通常需要根据多个因素对一组候选位置进行排序，如根据周围的POI、交通设施、交通状况和邻里人气。不同因素的排序函数可以根据现有购物中心及其历史收入学习得到。

这类模型最初是为了信息检索而提出的，通过学习历史来根据一组候选位置的性质对它们进行排序。近年来，机器学习技术已成功应用于排序，产生了三种“学习排序”算法：逐点、逐对和逐列表方法 ^[9，48] 。以下，我们将使用图3.11所示的例子来介绍这三种方法。

在这个例子中，我们的目标是根据一系列特征对房地产位置{ r ₁ ， r ₂ ，…， r _i ，…， r _j }进行排序。 X _i 表示房地产 r _i 的特征，例如 r _i 周围的公交站和购物中心数量。图3.11a中第三列代表过去一年内房地产的价格增长率，我们可以据此对这些位置进行排序，并将排序结果进一步离散化为三个级别，其中一级是最高级别，三级是最低级别。有时，区分由一些小差距（例如，0.35和0.34）引起的顺序并没有真正的意义。此外，这样的细粒度排序会导致沉重的计算负载，甚至影响排序模型的性能。

3.2.3.1 逐点方法

这种方法（例如参考文献 ^[41] ）将排序转换为针对单个对象的回归或分类问题。关于这个例子，我们可以训练一个线性回归模型，如公式（3.6）所示，以预测一块房地产某属性的增长率。一旦预测出每块房地产的此增长率，我们就可以对它们进行排序。

另一种针对这个例子的逐点方法是训练一个分类模型（如决策树）来预测每块房地产的离散化排序{1，2，3}。一旦预测出排序值，我们就可以对这些房地产进行排序。由于回归和分类模型只考虑单个属性的信息，它们是逐点方法。

3.2.3.2 逐对方法

这类方法（如参考文献 ^[5，23] ）将排序转换为针对对象对的分类。也就是说，它最终将对象对分类为两类：正确排序的和错误排序的。按照前述例子，逐对方法首先将每两个属性组成一对，如（ X _i ， X _j ），并为每对标记1或-1，其中1表示 X _i 排在 X _j 之前，-1表示 X _i 排在 X _j 之后。使用<特征对，标签>，如 f （ X _i ， X _j ）→1、 f （ X _i ， X ₁ ）→-1、 f （ X _j ， X ₁ ）→-1和 f （ X ₂ ， X _i ）→1，我们可以训练一个分类模型来根据两个属性的特征预测它们的排序。一旦任意两个对象之间的排序都确定了，那么这些对象的最终排序就可以推导出来。

朝着这个研究方向，Herbrich等人 ^[23] 提出了Ranking SVM，它使用SVM技术构建一个分类模型。Burges等人 ^[5] 提出了RankNet，使用交叉熵作为损失函数来训练神经网络模型。RankNet已经被应用于Bing搜索引擎。Fu等人 ^[16-18] 提出了一种学习排序的方法，目标函数同时考虑了对实例自己的预测（即属性的增长率）和两个实例之间的逐对顺序。图3.11b展示了图3.11a中显示的属性的图形表示，使用有向边表示两个实例之间的降序关系。例如， r _i → r _j 表示 r _i 排在 r _j 之前。目标函数呈现在公式（3.7）中。这个方程的第一部分 用于最大化每个实例自己的预测准确性。第二部分确保了正确的顺序（每个实例对之间），该顺序由图3.11b中显示的有向边表示。

更具体地说，逐对顺序是通过一个Sigmoid函数来建模的，该函数将两个属性的个体预测之间的差距（即 y _i -y _j ）转换为一个（0，1）之间的实数值。

对于公式（3.8），如果 r _i 确实排在 r _j 之前，并且为其预测的增长率高于 r _j （即保持正确顺序的正确推断），那么 P （ r _i → r _j ）趋向于一个相对较大的值。根据Sigmoid曲线的分布，当 y _i -y _j >0时，Sigmoid（ y _i -y _j ）的值很快接近1。这给保持正确顺序的正确个体预测提供了正奖励。相反，如果 r _i 确实排在 r _j 之前，但 r _i 的预测增长率小于 r _j ，也就是说这两个属性的预测可能不准确，那么 P （ r _i → r _j ）将会非常小。当 y _i -y _j >0时，Sigmoid（ y _i -y _j ）很快接近0，从而惩罚这种不准确的预测。

3.2.3.3 逐列表方法

这类方法（如ListNet ^[9] 和RankCosine ^[44] ）将对象的排序列表（如文档的排序列表）作为实例，并通过最小化根据预测列表和真实列表定义的列表损失函数来训练排序函数。人们称列表方法比以前的工作 ^[9，44] 在概念上更能自然地表达排序问题。与其他方法相比，列表方法具有更高的计算负载，但它基于一些数据集测试展示了自身的优势。

3.2.4 最小化不确定性

在某些类型的传感器部署中，很难明确建模选择最佳部署位置的标准。例如，我们希望找到一些地方部署更多的空气质量传感器，以显著提高现有系统的空气质量监测能力。然而，由于我们不知道在部署传感器之前该地点的空气质量，因此很难建模这样的标准。在部署用于监测水质、气象、矿物等的传感器时，我们面临着同样的挑战。

解决这个问题的通用方法是首先根据现有传感器生成的数据训练一个推理模型，然后用该模型推断没有传感器的位置的值。直观上，对于那些模型可以自信地推断出值的位置，没有必要部署传感器，而应该在模型无法处理的位置部署传感器。推理的置信度（也可以称之为不确定性）可以通过熵或概率来衡量。例如，如果一个推理模型可以预测一个位置的空气质量，并且不同类别的概率分布为<良好：0.85，中等：0.1，不健康：0.05>，那么不确定性非常低，置信度非常高。请注意，置信度不是由推理模型在无须知道该位置空气质量的真实值的情况下得出的准确性。

图3.12展示了一个通过最小化推理不确定性来部署空气质量传感器的示例 ^[25] 。在这个例子中，首先根据现有传感器（如 G 、 H 、 M 和 N ）的数据训练一个推理模型，并用该模型预测没有传感器的位置（如 A 、 B 和 C ）的空气质量。该模型可以是决策树或贝叶斯网络。推理结果是不同标签类别（如良好、中等、不健康等）的概率分布。然后我们可以根据这些推理结果的熵以递减的方式对位置进行排序。最直接的方法是选择熵最高的位置，即最不确定的推理。然而，有许多轮次的推理（如每小时）。不同轮次中位置的排序可能发生变化。此外，这些不确定的位置可能相互关联并且彼此靠近。在较小的地理区域内部署多个传感器是相当浪费的。

为了达到这个目的，有文献提出选择熵最小的位置（例如 B ）作为带标签的位置，将该位置添加到带标签的数据集中。在下一轮预测中，根据增强的带标签的数据集重新训练推理模型，然后用它推断其他位置（如 A 、 C 、 D 和 E ）的空气质量。同样，选择熵最小的位置（例如 E ）添加到带标签的数据集中。在迭代进行多轮推理后，我们汇总每个位置的排名，选择排名前 k 的位置部署新传感器。 6y7TKrrNO6fv63TA5oPZPq7XGNu82+NoTJnKhQiO6Qal8iOEEhLOsAxDEBx4jsKj