过去几年，我们在处理敏感数据的隐私安全方法方面取得了进展，例如，在探索人类流动性的见解时，以及通过使用RAPPOR等联合分析。2019 年，我们发布了一个开源库，使开发人员和组织能够使用提供差异隐私的技术，差异隐私是一种强大且被广泛接受的隐私数学概念。差异隐私数据分析是一种原则性方法，使组织能够从大量数据中学习和发布见解，同时提供数学保证，确保这些结果不会让任何单个用户的数据被区分或重新识别。
在这篇文章中，我们考虑以下基本问题：给定一个包含用户多项属性的数据库，如何创建有意义的用户组并了解其特征？重要的是，如果手头的数据库包含敏感的用户属性，如何在不损害个人用户隐私的情况下揭示这些群体特征？
此类任务属于聚类 的范畴，聚类是无监督机器学习的基本组成部分。聚类方法将数据点划分为组，并提供一种将任何新数据点分配到与其最相似的组的方法。K均值聚类算法就是这样一种有影响力的聚类方法。然而，在处理敏感数据集时，它可能会泄露有关单个数据点的重要信息，从而使相应用户的隐私面临风险。
今天，我们宣布在我们的差异隐私库中 添加一种新的差异隐私聚类算法，该算法基于私下生成新的代表性数据点。我们在多个数据集上评估其性能并与现有基线进行比较，以找到具有竞争力或更好的性能。
K 均值聚类
给定一组数据点，k 均值聚类的目标是识别（最多）k 个点（称为聚类中心），以最小化数据点与其最近的聚类中心的距离平方和所带来的损失。这将数据点集分成 k 个组。此外，任何新数据点都可以根据其最近的聚类中心分配到一个组。但是，发布聚类中心集可能会泄露有关特定用户的信息 - 例如，考虑这样一种情况，某个特定数据点与其他点相距甚远，因此标准 k 均值聚类算法会在此点处返回聚类中心，从而泄露有关此点的敏感信息。为了解决这个问题，我们在差异隐私框架内设计了一种以 k 均值为目标的新型聚类算法。
差分隐私算法
在ICML 2021上发表的 “一轮本地隐私 k 均值”中，我们介绍了一种用于聚类数据点的差分隐私算法。该算法的优势在于在本地模型中是隐私的，即使执行聚类的中央服务器也可以保护用户的隐私。然而，任何此类方法都必然会比使用需要信任中央服务器的隐私模型的方法造成更大的损失。1
在这里，我们提出了一种类似启发的聚类算法，该算法在差分隐私的中心模型中工作，其中中心服务器被信任可以完全访问原始数据，并且目标是计算差分隐私聚类中心，这些聚类中心不会泄露有关各个数据点的信息。中心模型是差分隐私的标准模型，并且中心模型中的算法可以更容易地取代非隐私算法，因为它们不需要更改数据收集过程。该算法首先以差分隐私方式生成一个核心集，该核心集由可以很好地“表示”数据点的加权点组成。然后在这个私密生成的核心集上 执行任何（非隐私）聚类算法（例如， k-means++ ）。
从高层次上讲，该算法首先以递归方式 使用基于随机投影的局部敏感哈希(LSH) 2将点划分为相似点的“桶”，然后用单个加权点替换每个桶，该加权点是桶中点的平均值，权重等于同一桶中的点数，从而生成私有核心集。不过，正如到目前为止所述，该算法并不是私有的。我们通过以私有方式执行每个操作，即在桶内点的计数和平均值中 添加噪声，使其私有化。
该算法满足差分隐私，因为每个点对桶计数和桶平均值的贡献都被添加的噪声掩盖，因此算法的行为不会泄露有关任何单个点的信息。这种方法有一个权衡：如果桶中的点数太大，那么核心集中的点将无法很好地表示单个点，而如果桶中的点数太少，那么与实际值相比，添加的噪声（对计数和平均值）将变得非常大，从而导致核心集的质量不佳。这种权衡是通过算法中用户提供的参数来实现的，这些参数控制桶中可以包含的点数。
算法的视觉说明。
实验评估
我们在几个基准数据集上评估了该算法，将其性能与（非私有）k-means++算法以及其他一些具有可用实现的算法（即diffprivlib和dp-clustering-icml17）进行了比较。我们使用以下基准数据集：（i）由从 64 个高斯混合中采样的 100 维中的 100,000 个数据点组成的合成数据集；（ii）通过训练LeNet 模型获得的MNIST 手写数字数据集的神经表征；（iii）加州大学欧文分校的字母识别数据集；（iv）加州大学欧文分校的燃气轮机 CO 和 NOx 排放数据集。3
我们对基准数据集中目标中心数量 (k) 的变化情况进行了归一化 k 均值损失（数据点到最近中心的均值平方距离）分析。4在我们考虑的四个数据集中的三个中，所描述的算法比其他私有算法实现了更低的损失。
不同 k = 目标簇数量的归一化损失（越低越好）。实线表示 20 次运行的平均值，阴影区域表示 25-75百分位数范围。
此外，对于具有指定真实标签（即已知分组）的数据集，我们分析了聚类标签准确度，即通过将聚类算法在每个聚类中找到的最常见真实标签分配给该聚类中的所有点而获得的标签准确度。在这里，对于我们考虑的所有具有预先指定的真实标签的数据集，所述算法的表现优于其他私有算法。
不同 k = 目标簇数量的簇标签准确度（越高越好）。实线表示 20 次运行的平均值，阴影区域表示 25-75百分位数范围。
局限性和未来方向
在使用此库或任何其他库进行私有集群时，需要考虑一些限制。
在使用隐私聚类算法之前进行的任何预处理（例如，将数据点居中或重新缩放不同的坐标）中，单独考虑隐私损失非常重要。因此，我们希望在未来为常用预处理方法的差异隐私版本提供支持，并研究变化，以便算法在处理不需要预处理的数据时表现更好。
所述算法需要用户提供的半径，以便所有数据点都位于该半径的球体内。这用于确定添加到桶平均值中的噪声量。请注意，这与diffprivlib和dp-clustering-icml17不同，它们采用不同的数据集边界概念（例如，每个坐标的最小值和最大值）。为了进行实验评估，我们为每个数据集非私密地计算了相关边界。但是，在实践中运行算法时，这些边界通常应在不了解数据集的情况下私下计算或提供（例如，使用数据的底层范围）。但是，请注意，对于所述算法，提供的半径不必完全正确；提供半径之外的任何数据点都将替换为该半径球体内的最近点。
结论
这项研究提出了一种在差分隐私框架内计算代表点（聚类中心）的新算法。随着全球收集的数据集数量的增加，我们希望我们的开源工具能够帮助组织获得并分享有关其数据集的有意义的见解，并提供差分隐私的数学保证。
致谢
我们感谢 Christoph Dibak、Badih Ghazi、Miguel Guevara、Sasha Kulankhina、Ravi Kumar、Pasin Manurangsi、Jane Shapiro、Daniel Simmons-Marengo、Yurii Sushko 和 Mirac Vuslat Basaran 的帮助。
评论