CN117034057A - 一种基于Spark的支持差分隐私的聚类方法 - Google Patents

Abstract

本发明公开了一种基于Spark的支持差分隐私的聚类方法，该算法通过内存计算引擎Spark，创建弹性分布式数据集，利用转换算子及行动算子操作数据进行运算，并在选取初始化中心点及迭代更新中心点的过程中，通过综合利用指数机制和拉普拉斯机制，以解决初始聚类中心敏感及隐私泄漏问题，同时减少计算过程中对数据实施的扰动。本发明能够处理大规模数据集并满足海量数据聚类的需求。相比于传统算法，该算法具有更好的可扩展性和分布式计算能力。在聚类过程中，该算法采取指数机制和Laplace机制相结合的方法，从而有效降低隐私预算开销，进而缓解海量数据聚类过程中隐私性和可用性之间的矛盾问题。

Description

一种基于Spark的支持差分隐私的聚类方法

技术领域

本发明涉及数据挖掘、差分隐私和分布式计算等领域，具体涉及一种基于Spark的支持差分隐私的聚类方法。

背景技术

近年来，由于大数据的快速发展，聚类算法作为一种典型的无监督算法受到越来越多的关注。然而，数据聚类分析的结果在提供有价值信息的同时也存在着一些隐私安全性的问题。为保护隐私而探索的许多现有解决方案要么承受计算开销，要么对涉及的各方有严格的假设，例如安全多方计算方案或同态加密方案，这与大多数现实的场景不符。因此支持差分隐私保护的聚类方法应运而生。

k-means算法作为最常用的聚类算法，其原理简单易懂，易于实现，广泛应用于数据挖掘和模式识别等领域。但是由于k-means算法通常需要将所有数据点都传输至服务器进行计算，因此很容易导致用户数据的泄露。特别是当用户数据包含敏感信息时，一旦泄露会给用户带来严重的隐私风险。为了解决k-means算法的隐私泄露问题，研究者们提出了许多改进算法。其中最常用的方法是差分隐私技术。Dwork等人在论文《A firm foundationfor priv-ate data analysis》中详细分析了差分隐私k-means算法，并给出了设置隐私保护预算ε的方法。

另一方面，针对海量数据聚类的效率问题也是当前需要解决的重要难题。由于海量数据的规模庞大，传统的聚类方法往往无法胜任，导致计算速度缓慢、内存使用过高等问题。为了应对这一挑战，李洪成等人在论文《Differe-ntial Privacy-Preserving k-meansClustering Method in the MapReduce Framework》中基于MapReduce框架实现了分布式环境下支持差分隐私保护的k-means聚类方法，利用MapReduce计算框架提高聚类分析的效率，并通过添加噪声使聚类的输出满足差分隐私，给出了具体的计算流程。

但是MapReduce是一个基于磁盘的批处理框架，在每次计算期间存在Shuffle操作需要重复磁盘存储、读取和其他操作。因此MapReduce操作在处理海量数据的过程中会消耗大量时间，且不适合迭代计算。2022年毛伊敏等人在论文《基于Spark框架和ASPSO的并行划分聚类算法》中实现了基于Spark框架和ASPSO的并行划分聚类算法，利用Spark框架并行实现聚类算法，极大提升了聚类算法的效率但是没有考虑数据聚类过程中存在的隐私泄露问题。

此外，k-means聚类算法的效果很大程度上依赖于初始质心的选择。如果初始质心的选取不当，可能会导致算法陷入局部极小值而得不到最优解。k-means++算法可以解决k-means算法其准确度受其初始中心点选取的影响较大的问题，但是在初始质心选择以及迭代更新质心时计算每个样本点到已选初始化随机中心点最短距离过程中会同样泄露隐私。2019年傅彦铭等人在文献《基于拉普拉斯机制的差分隐私保护k-means++聚类算法研究》中在k-mean++算法的基础上通过拉普拉斯机制实现了满足差分隐私的k-means++算法，在选取初始质心的过程中，采用拉普拉斯机制对数据实施扰动，解决了k-means++聚类算法选取初始化中心点时隐私泄露的问题。

然而，在面对海量高维数据聚类任务时，如果要在保证隐私的前提下实现良好的聚类效果，往往需要花费高额的隐私预算。这是由于数据规模增大和维数增多所带来的计算量也随之增加，导致隐私保护所需要的噪声扰动也随之增多，从而加大了隐私预算的开销，运行效率也随之大幅降低。

综上所述，为了提高海量数据聚类分析算法的隐私保护能力及运行效率，提出了一种Spark框架下支持差分隐私保护的聚类算法，综合利用指数机制及拉普拉斯机制对差分隐私聚类算法进行优化，以减少计算过程中隐私预算的花费，并使聚类算法的输出结果满足差分隐私，同时利用Spark计算框架将其拓展到分布式环境下执行以提高聚类分析的效率，实现算法的可拓展性，在解决分布式环境下海量数据的安全聚类问题上会有一定的帮助。

发明内容

本发明的目的是提出一种基于Spark框架下支持差分隐私聚类的方法，以解决上述技术问题。

为实现上述目的，本发明提供了如下方案：

本发明的基于Spark框架下支持差分隐私聚类的方法为一种分布式环境下支持差分隐私的k-means++聚类算法。该算法通过内存计算引擎Spark，创建弹性分布式数据集(RDD)，利用转换算子及行动算子操作数据进行运算，并在选取初始化中心点及迭代更新中心点的过程中，通过综合利用指数机制和拉普拉斯机制，以解决初始聚类中心敏感及隐私泄漏问题，同时减少计算过程中对数据实施的扰动。

算法的基本思路是先计算初始化中心点，其中使用指数机制对数据进行ε₁-差分隐私保护，选取初始化中心点之后进行迭代求均值对中心点进行更新，并采用拉普拉斯机制对数据进行ε₂-差分隐私保护，使得聚类算法的结果满足ε-差分隐私保护。

本发明的一个方面，针对其在计算样本点到已选初始化随机中心点最短距离过程中会泄露隐私的问题，采用指数机制进行优化，以减少对数据实施的扰动。为了使选取的中心点在数据中分布尽量离散，效用函数需满足如下要求：设已有的初始中心点集合为C，各记录与集合C中已选取的各中心点之间的最短距离越大，效用值就越大。为了使效用函数满足此要求。采用非中心点Vi与中心点集合C之间的最短欧氏距离来构造效用函数，如下所示。

算法步骤如下所示：

1)设数据集中的记录数为n，每条记录均为d维的向量v_i(1≤i≤n)，聚类目标数为k，各聚类的中心点记为C_j(1≤j≤k)。

2)从HDFS读入数据集创建RDD，将数据切片后读入至不同分区。

3)随机选取第一个中心点C₁，计算每条记录距已选中心点的最短距离dist_i(1≤i≤n)，利用mapToPair将RDD转变成PairRDD，并将记录处理成key-value键值对形式，其中key即为最短距离。

4)dist经由全局敏感度为Δu的评分函数u(dist,r)处理输出r，计算exp(ε×r/2Δu)作为效用值Pr_i。

5)利用EnumeratedDistribution类对Pr_i进行归一化操作，作为抽样的概率进而选取下一个中心点。

作为进一步的优选方案，重复执行上述步骤直至选出k个初始聚类中心。

另一方面，选出k个初始聚类中心后，在各分区内并行计算，迭代求取均值，并对结果进行拉普拉斯机制保护，最后对簇类中心进行更新。算法步骤如下所示：

1)计算每条记录距已选中心点{C₁,C₂,…C_k}的最短距离dist_i(1≤i≤n)，同样将RDD转变成PairRDD，将记录处理成key-value键值对形式，其中key的值为该记录距离最近的中心点C_j(1≤j≤k)。

2)利用行动算子reduceByKey对不同分区的记录按照其所属最近的中心点进行聚合，共k个分区。

3)各分区内分别统计记录总数num_j,以及各记录属性向量之和sum_j，分别加入拉普拉斯噪声得到num'_j，sum'_j。

4)重新计算该分区内的中心点

需要说明的是，算法的迭代条件设置为新一轮的中心点与上一轮中心点距离的变化，当两者距离小于设定的阈值时或者当隐私预算花费完时结束循环，否则继续进入下一轮迭代。

在一些实施例中，生成初始化中心点过程中，采用记录与中心点之间的最短欧式距离构造评分函数，尽可能地保证每个质心点之间的距离相对较远，从而能够更快、更准确地收敛到局部最优解。计算dist的过程等同于对空间[0,1]^d进行划分的直方图查询，故评分函数的全局敏感度Δu＝1。设此过程消耗隐私预算为ε₁，则每次选取初始中心点所消耗的隐私预算为ε₁/k。

进一步的，迭代更新中心点的过程中，分区内的记录数num其全局敏感度为1，sum其全局敏感度为记录的维数大小d。由性质1可知，整个查询序列的全局敏感度Δf＝d+1，设此过程隐私预算为ε₂，总迭代次数为T,第t次迭代的隐私预算即为ε₂/2^t，故算法在第t轮迭代时针对num_j,sum_j分别加入随机噪声Lap(d+1)2^t+1/ε₂，可以保证Spark框架下迭代更新过程中满足ε₂-差分隐私保护。令ε＝ε₁+ε₂，由性质1可知，整个聚类过程满足ε-差分隐私。

与现有技术相比，本发明首次将指数机制与拉普拉斯机制进行结合，分别运用在初始化质心选择的优化上以及各簇质心迭代更新的过程中，以减少隐私预算的开销。指数机制针对随机化算法f输入数据集D，输出一个实体对象r∈R，μ(D,R)为效用函数，Δμ为函数μ(D,R)的敏感度，若以正比于exp(ε·μ(D,r)/2Δμ)的概率从输入中选择并输出r，则f满足ε-差分隐私。利用指数机制以更高的概率选择效用得分更高的输出这一特性，将效用函数设置为计算记录与质心的距离，进行概率抽样，每次仅释放一个最大噪声分数的值作为新的质心。相比于使用拉普拉斯机制对数据扰动后选择距离最大的值作为质心，可以减少隐私预算的开销，从而提升差分隐私聚类算法的可用性。

另一方面，利用Spark计算框架实现算法的并行化，创建弹性分布式数据集RDD，利用transformation转换算子及action行动算子操作数据进行运算，提高算法的效率及灵活性，相比于Mapreduce需要将每次计算的结果写入磁盘，然后再从磁盘读取数据，导致频繁的磁盘IO，Spark得益于RDD和DAG，除Shuffle过程以外通常不需要将计算的结果写入磁盘，可以在内存中进行迭代计算。基于Spark将算法由单机运行拓展至集群运行，以实现海量数据的高效安全聚类。

综上所述，本发明具有如下有益效果：本发明提出了一种采用Spark分布式计算框架来实现聚类分析，从而能够处理大规模数据集并满足海量数据聚类的需求。相比于传统算法，该算法具有更好的可扩展性和分布式计算能力。在聚类过程中，该算法采取指数机制和Laplace机制相结合的方法，从而有效降低隐私预算开销，进而缓解海量数据聚类过程中隐私性和可用性之间的矛盾问题。

附图说明

图1为本发明的计算流程图；

图2为本发明的任务执行流图。

具体实施方式

以下将结合附图对本发明的较佳实施例进行详细说明，以便更清楚理解本发明的目的、特点和优点。应理解的是，附图所示的实施例并不是对本发明范围的限制，而只是为了说明本发明技术方案的实质精神。

在下文的描述中，出于说明各种公开的实施例的目的阐述了某些具体细节以提供对各种公开实施例的透彻理解。但是，相关领域技术人员将认识到可在无这些具体细节中的一个或多个细节的情况下来实践实施例。在其它情形下，与本申请相关联的熟知的装置、结构和技术可能并未详细地示出或描述从而避免不必要地混淆实施例的描述。

在整个说明书中对“一个实施例”或“一实施例”的提及表示结合实施例所描述的特定特点、结构或特征包括于至少一个实施例中。因此，在整个说明书的各个位置“在一个实施例中”或“在一实施例”中的出现无需全都指相同实施例。另外，特定特点、结构或特征可在一个或多个实施例中以任何方式组合。

在以下描述中，为了清楚展示本发明的结构及工作方式，将借助诸多方向性词语进行描述，但是应当将“前”、“后”、“左”、“右”、“外”、“内”、“向外”、“向内”、“上”、“下”等词语理解为方便用语，而不应当理解为限定性词语。

实施例1：

本实施例的计算流程如图1所示。在Spark集群上通过submit命令指定聚类簇数k以及最大迭代次数itr。随机选取第一个初始质心C₁，计算其余记录到质心的距离dist_i(1≤i≤n)，效用函数设为两者之间的最短欧式距离，计算得到效用值后，进行归一化操作，按照概率权重选取下一个质心作为中心点。重复上述步骤直至选出k个初始质心。根据其余记录距质心的最短距离进行划分，归为k个簇后，分别计算各簇中各维度的数值总和以及记录数，采用拉普拉斯机制进行处理，通过添加添加Lap(d+1)2^t+1/ε₂噪声进行扰动，求取噪声均值更新为新一轮的簇类中心，由循环条件判断是否进入下一轮迭代，达到终止条件后得到最终聚类结果。

本实施例的任务流图如图2所示，当通过客户端发起job任务后，由yarn进行任务的调度，当Driver线程执行到reduceByKey行动算子后，通过血缘关系查找宽依赖切分Stage，将task分发至各节点进行计算，完成计算后聚合汇总后存储至HDFS。

具体步骤如下：

(1)生成初始化中心点保护阶段

采用该方法生成初始化中心点的步骤分为：随机选取第一个初始中心点、距离计算、指数机制、归一化后进行抽样、重复上诉步骤直至选出目标数量的中心点；具体过程如下：

(1.1)随机选取第一个中心点

将数据集由HDFS读入后，针对大型数据集，切片后创建弹性分布式数据集(RDD)，通过Random类随机抽取一条记录作为第一个中心点。

(1.2)距离计算

选取出一个中心点后，计算剩余记录与中心点的欧式距离。

(1.3)指数机制

根据效用函数进行计算，得到各记录与已选取的中心点之间的最短欧式距离，再经由exp(ε×r/2Δu)计算得到每条记录的效用值。

(1.4)概率抽样

利用EnumeratedDistribution类对各记录的效用值进行归一化操作，进而作为抽样的概率，利用sample方法按权重进行抽样得到下一个初始中心点。

(1.5)迭代执行

重复上述步骤直至选出k个初始聚类中心。

(2)迭代更新中心点保护阶段

采用该方法的步骤分为：均值计算、拉普拉斯机制、迭代优化；具体过程如下：

(2.1)各分区均值计算

计算每条记录距已选中心点{C₁,C₂,…C_k}的最短距离dist_i(1≤i≤n)，同样将RDD转变成PairRDD，将记录处理成key-value键值对形式，其中key的值作为该记录距离最近的中心点C_j(1≤j≤k)。

(2.2)拉普拉斯机制

利用行动算子reduceByKey对不同分区的记录按照其所属最近的中心点进行分区。各分区内分别统计记录总数num_j,以及各记录属性向量之和sum_j，分别加入拉普拉斯噪声进行干扰得到噪声值num'_j，sum'_j，重新计算该分区内的中心点作为下一次迭代计算的簇类中心点。

(2.3)循环优化

算法的迭代条件设置为新一轮的中心点与上一轮中心点距离的变化，当两者距离小于设定的阈值时结束算法或者当算法花费的隐私预算达到设定的初始值时结束循环，否则继续进入下一轮迭代。

以上显示和描述了本发明的基本原理和主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。

Claims (10)

1.一种基于Spark的支持差分隐私的聚类方法，其特征在于：该算法通过内存计算引擎Spark，创建弹性分布式数据集，利用转换算子及行动算子操作数据进行运算，并在选取初始化中心点及迭代更新中心点的过程中，通过综合利用指数机制和拉普拉斯机制，以解决初始聚类中心敏感及隐私泄漏问题，同时减少计算过程中对数据实施的扰动。

2.根据权利要求1所述的基于Spark的支持差分隐私的聚类方法，其特征在于包括如下步骤：先计算初始化中心点，使用指数机制对数据进行ε₁-差分隐私保护，选取初始化中心点之后进行迭代求均值对中心点进行更新，并采用拉普拉斯机制对数据进行ε₂-差分隐私保护，使得聚类算法的结果满足ε-差分隐私保护。

3.根据权利要求1或2所述的基于Spark的支持差分隐私的聚类方法，其特征在于：该方法为分布式环境下支持差分隐私的k-means++聚类算法。

4.根据权利要求3所述的基于Spark的支持差分隐私的聚类方法，其特征在于：选取初始化中心点及迭代更新中心点的过程中，采用非中心点Vi与中心点集合C之间的最短欧氏距离来构造效用函数，如下所示：

5.根据权利要求1或2所述的基于Spark的支持差分隐私的聚类方法，其特征在于该方法包括如下步骤：

1)设数据集中的记录数为n，每条记录均为d维的向量v_i(1≤i≤n)，聚类目标数为k，各聚类的中心点记为C_j(1≤j≤k)；

2)从HDFS读入数据集创建RDD，将数据切片后读入至不同分区；

3)随机选取第一个中心点C₁，计算每条记录距已选中心点的最短距离dist_i(1≤i≤n)，利用mapToPair将RDD转变成PairRDD，并将记录处理成key-value键值对形式，其中key即为最短距离；

4)dist经由全局敏感度为Δu的评分函数u(dist,r)处理输出r，计算exp(ε×r/2Δu)作为效用值Pr_i；

5)利用EnumeratedDistribution类对Pr_i进行归一化操作，作为抽样的概率进而选取下一个中心点。

6.根据权利要求5所述的基于Spark的支持差分隐私的聚类方法，其特征在于：还包括重复执行步骤1)-步骤5)直至选出k个初始聚类中心。

7.根据权利要求6所述的基于Spark的支持差分隐私的聚类方法，其特征在于：选出k个初始聚类中心后，在各分区内并行计算，迭代求取均值，并对结果进行拉普拉斯机制保护，最后对簇类中心进行更新；算法步骤如下所示：

1)计算每条记录距已选中心点{C₁,C₂,…C_k}的最短距离dist_i(1≤i≤n)，同样将RDD转变成PairRDD，将记录处理成key-value键值对形式，其中key的值为该记录距离最近的中心点C_j(1≤j≤k)；

2)利用行动算子reduceByKey对不同分区的记录按照其所属最近的中心点进行聚合，共k个分区；

3)各分区内分别统计记录总数num_j，以及各记录属性向量之和sum_j，分别加入拉普拉斯噪声得到num'_j，sum'_j；

4)重新计算该分区内的中心点

8.根据权利要求7所述的基于Spark的支持差分隐私的聚类方法，其特征在于：算法的迭代条件设置为新一轮的中心点与上一轮中心点距离的变化，当两者距离小于设定的阈值时或者当隐私预算花费完时结束循环，否则继续进入下一轮迭代。

9.根据权利要求5所述的基于Spark的支持差分隐私的聚类方法，其特征在于：生成初始化中心点过程中，采用记录与中心点之间的最短欧式距离构造评分函数，保证每个质心点之间的距离相对较远，以快速准确收敛到局部最优解；计算dist的过程等同于对空间[0,1]^d进行划分的直方图查询，故评分函数的全局敏感度Δu＝1；设此过程消耗隐私预算为ε₁，则每次选取初始中心点所消耗的隐私预算为ε₁/k。

10.根据权利要求5所述的基于Spark的支持差分隐私的聚类方法，其特征在于：迭代更新中心点的过程中，分区内的记录数num其全局敏感度为1，sum其全局敏感度为记录的维数大小d；整个查询序列的全局敏感度Δf＝d+1，设此过程隐私预算为ε₂，总迭代次数为T，第t次迭代的隐私预算即为ε₂/2^t，故算法在第t轮迭代时针对num_j,sum_j分别加入随机噪声Lap(d+1)2^t+1/ε₂，保证Spark框架下迭代更新过程中满足ε₂-差分隐私保护；令ε＝ε₁+ε₂，整个聚类过程满足ε-差分隐私。