轨迹数据采集是一项在我们的日常生活中有着众多应用的常见任务。通过分析轨迹数据，服务提供商能够提升其服务质量并最终惠及用户。然而，直接收集轨迹数据可能会引发不容忽视的隐私问题。本地差分隐私（LDP）作为分布式环境中的实际隐私保护标准，使用户能够在本地扰动其轨迹并提供可证明的隐私保证。现有的本地轨迹数据采集的隐私保护方法通常采用LDP的简化版本，这无法提供严格的隐私保证，或者需要一些不切实际的外部知识。本地差分隐私保护是一种新型的隐私保护技术，它在数据收集阶段保护用户的隐私数据。在轨迹数据采集过程中使用本地差分隐私保护可以有效地防止敏感信息的泄露。本次为大家带来时空数据领域的顶级会议VLDB2023的文章《Trajectory Data
Collection with Local Differential Privacy》，本文介绍了一种基于本地差分隐私保护的轨迹数据采集方法TP。该方法在保证用户隐私的同时，能够收集到足够多的轨迹数据，以便进行后续的分析和应用。
在数字化时代，移动设备和应用程序的广泛使用使得个人位置数据的收集变得日益普遍。这些数据不仅能够反映个人的日常活动模式，还对城市规划、交通管理、公共卫生等领域具有重要价值。然而，位置数据的敏感性也使得隐私保护成为公众和研究者关注的焦点。如何在收集和利用这些数据的同时，确保个人隐私不被泄露，是一个亟待解决的问题。传统的隐私保护方法，如k-匿名性和l-多样性，虽然在一定程度上能够保护用户隐私，但它们通常依赖于数据的特定假设，并且在实际应用中可能难以满足严格的隐私保护要求。差分隐私（DP）作为一种新兴的隐私保护技术，通过在数据发布过程中引入随机性来保护个体信息，已被证明能够在不泄露个体数据的情况下，允许对数据集进行统计分析。然而，DP的实现通常需要一个可信的第三方来添加噪声，这在实际应用中可能并不总是可行的。局部差分隐私（LDP）作为DP的一种形式，允许用户在本地对数据进行扰动，然后将扰动后的数据发送给不可信的服务器，更适合分布式和去中心化的场景。LDP不需要依赖可信的第三方，降低了对中心化数据收集和管理的需求。但是，LDP在实际应用中也面临挑战，尤其是在轨迹数据的隐私保护方面。由于轨迹数据的连续性和空间分布特性，直接应用LDP可能会导致数据的实用性大幅下降。为了克服这些挑战，本文提出了多种轨迹数据的隐私保护方法，包括基于地理空间数据的扰动技术、利用方向信息的隐私保护策略等。这些方法在提高隐私保护水平的同时，也试图减少对数据实用性的影响。然而，大多数现有方法要么依赖于外部知识，要么在隐私保护和数据实用性之间难以取得平衡。本文针对现有方法的局限性，提出了一种新颖的轨迹数据收集机制，旨在实现严格的隐私保护，同时最大限度地保持数据的实用性。通过引入方向信息和自适应的轨迹区域限制，本文的机制能够在不依赖外部知识的情况下，为轨迹数据的隐私保护提供一种有效的解决方案。二. 前置知识
2.1 隐私保护在数据分析和数据发布领域一直是一个重要议题：随着大数据时代的到来，如何在保障个人隐私的同时充分利用数据价值，成为一个亟待解决的问题。近年来，差分隐私（Differential Privacy，DP）作为一项保护数据隐私的前沿技术，受到了学术界和工业界的广泛关注。
2.1.1 差分隐私（DP）：DP是一种在数据分析中保护个体隐私的数学框架，通过在数据结果中引入随机性来保护个体信息不被识别。DP的核心思想是在数据集中增加噪声，以确保任何单个数据项对分析结果的影响都是受限的。这样，攻击者就无法从发布的统计结果中精确地推断出任何个体的真实信息。
2.1.2 局部差分隐私（LDP）：LDP是DP的一个变种，它不需要依赖于中心化的可信服务器来添加噪声，而是允许用户在本地对自己的数据进行扰动。这种去中心化的特性使得LDP在移动设备和分布式系统中特别有用，因为这些场景中用户可能不愿意或无法将原始数据上传到中心服务器。
2.2 地理空间数据隐私：地理空间数据，如用户的位置信息和轨迹数据，是一类特殊的数据，具有明显的空间分布特征。保护这类数据的隐私尤为重要，因为它们与个人的日常活动紧密相关。地理空间数据的隐私保护通常需要考虑位置信息的连续性和空间关联性。
2.3 现有方法的局限性：尽管已有多种隐私保护技术被提出，但它们在实际应用中仍面临一些挑战。例如，一些方法可能需要依赖于外部知识或假设，这些知识或假设在现实世界中可能难以满足。此外，一些方法可能在隐私保护和数据实用性之间难以取得平衡，尤其是在处理复杂的地理空间数据时。
3.1 问题：本文面临的主要挑战是如何设计一个既满足LDP标准，又能在不依赖外部知识的情况下，保持高数据实用性的轨迹扰动机制。考虑到轨迹数据的空间连续性和方向性，需要一种新的方法，能够在保护用户隐私的同时，有效利用轨迹数据中的内在信息，如方向信息，以增强数据的实用性。3.2 本文提出了一种新颖的轨迹数据收集机制，称为基于枢轴的采样机制（Pivot Sampling, TP）：该机制首先识别轨迹中每个点的相邻方向信息，并将其用于点的扰动过程中。通过这种方式，不仅能够保持轨迹数据的连贯性，还能够限制扰动点的可能区域，从而在不牺牲隐私的前提下提高数据的实用性。如图1所示：
3.2.1 阶段一：机制识别出轨迹中每个点的相邻点，这些点被称为“枢轴”（pivots）。枢轴点被用作参照点，以确定与目标点的相对方向。这一步骤利用了用户移动时的方向信息，这是现有LDP方法中未被充分利用的资源。3.2.2 阶段二：在该区域内对目标点进行独立扰动。为了进一步增强性能，作者提出了基于锚点的方法，该方法能够自适应地限制整个轨迹的空间区域，然后在此受限区域内应用枢轴采样进行轨迹扰动。
3.3 优势：本文提出的TP机制为局部差分隐私在轨迹数据收集中的应用提供了一种新的视角，通过创新地利用方向信息和自适应区域限制，实现了隐私保护和数据实用性的双重目标。3.3.1 方向信息的利用：本文认识到，用户在移动时通常会有一个预定的方向，这一方向信息是连接轨迹中相邻点的关键线索。因此，本文的机制在扰动过程中考虑了这一方向性，从而提高了数据的实用性。与传统的基于网格的方法相比，本文的方法不需要依赖于外部知识或假设，而是直接利用了轨迹数据本身的内在特性。3.3.2 自适应区域限制：为了进一步提升机制的性能，本文提出了一种基于锚点的自适应区域限制策略。这一策略首先计算轨迹的“锚点”，并将其作为区域中心。然后，根据锚点和轨迹中点的距离，动态地确定一个合适的区域大小，以限制轨迹的扰动范围。这种自适应方法不仅避免了固定区域大小可能带来的信息损失，还能够根据轨迹的实际分布情况，有效地减少噪声的影响。3.3.3 隐私与实用性的平衡：在设计TP机制时，本文充分考虑了隐私保护和数据实用性之间的平衡。通过精心设计的扰动策略和区域限制，本文的机制能够在保护用户隐私的同时，为数据分析提供高质量的轨迹数据。此外，本文还提供了方向粒度选择的指导原则，帮助在不同的隐私预算下选择最合适的方向信息粒度。四．实验
为了验证本文提出的基于枢轴的采样机制（TP）和基于锚点的枢轴采样机制（ATP）的有效性，作者设计了一系列实验，这些实验在真实世界和合成数据集上进行，以评估所提方法的实用性和隐私保护能力。
4.1 实验设置
4.1.1 数据集：本文使用了包括NYC、CHI、CLE和CPS在内的四个数据集。NYC数据集包含了纽约市的签到轨迹，CHI和CLE数据集包含了芝加哥和克利夫兰的签到轨迹，而CPS是一个在不列颠哥伦比亚大学校园内生成的合成数据集。
4.1.2 基线方法：作者选择了几种基线方法进行比较，包括NGRAM机制、指数机制（EXP）和CGM机制。这些方法代表了不同的隐私保护技术和数据收集方法。
4.1.3 参数设置：所有机制均使用Haversine距离作为度量标准。对于ATP机制，作者根据隐私预算的不同部分进行了参数的分配和设置。
4.2 评估指标
4.2.1 平均归一化误差（NE）：衡量扰动轨迹与原始轨迹之间的归一化距离。
4.2.2 保留范围查询（PRQ）：评估扰动轨迹的每个点是否在原始真实点的特定范围内。
图5 保留范围查询 （PRQ）与在不同范围下δ的隐私预算ε
4.3 实验结果
4.3.1 NE结果：TP机制在真实世界数据集上的表现优于基线方法。尽管在隐私预算较小时，TP机制在接近原始点的选择上存在困难，但通过使用方向约束有效提升了实用性。
4.3.2 PRQ结果：TP机制在真实世界数据集上的PRQ值均优于基线方法，表明其在保持数据实用性方面的优势。
4.4 参数影响分析
4.4.1 固定半径值：作者研究了不同固定半径值对TP机制性能的影响。实验结果表明，随着隐私预算的增加，适当增加半径值可以提高性能。
4.4.2 方向信息的双向性：TP机制使用双向方向信息，相较于单向信息，可以更准确地限制轨迹区域，从而提升性能。
4.4.3 方向粒度：作者分析了不同方向粒度对性能的影响。实验表明，当隐私预算较小时，较粗的方向粒度可以更好地减少方向扰动噪声。
4.5 实用性评估
热点保留：作者还考虑了热点保留作为实际应用之一，以展示本文机制相对于现有工作的优势。实验结果显示（见图8），TP机制在所有数据集上实现了显著低于NGRAM和CGM的ACD值，证明了本文方法的优越性。
表1 不同方法的平均计数差异（ACD）比较（ε=4）
通过广泛的实验评估，本文证明了TP机制在不同方面的有效性。这些机制不仅在理论上满足LDP的要求，而且在实际应用中也展现出了良好的性能。实验结果揭示了位置点的底层分布与方向粒度选择过程之间的相关性，为未来研究提供了有价值的见解。本文介绍了一种创新的轨迹数据收集机制，名为TP（Trajectory Perturbation），旨在实现严格的隐私保护，同时最大化数据的实用性。通过引入基于枢轴的采样方法和自适应的轨迹区域限制，TP机制在不依赖外部知识的情况下，满足了纯LDP（Local Differential Privacy）标准。TP是首个在LDP框架下结合方向信息进行轨迹扰动的机制。这种结合不仅提高了数据的实用性，而且增强了隐私保护的严格性。自适应区域限制：通过基于锚点的方法，TP能够自适应地限制轨迹的扰动区域，这在处理具有不同区域大小的轨迹时尤为重要。总体而言，TP机制的提出，不仅在理论上推动了隐私保护技术的发展，而且在实际应用中具有广泛的应用前景。随着数据隐私问题日益受到重视，TP机制有望成为数据收集和分析领域的一个重要工具。| 重庆大学计算机科学与技术专业(弘深)2023级本科生，重庆大学Start Lab团队成员。
| 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜洪程璁
编辑｜徐小龙
审核｜李瑞远
审核｜杨广超
