CN118153100A - 面向边缘计算的本地化差分隐私混合数据迭代聚类算法 - Google Patents

Abstract

本发明涉及一种基于边缘计算下的本地化差分隐私数据保护方案。包括：用户端编码模块、用户端扰动模块、服务端选取聚类中心模块、服务端循环迭代聚类优化模块、更新聚类中心点集模块等五个模块。本发明涉及一种基于本地化差分隐私的迭代聚类算法(LDPIA)。该算法实现本地化差分隐私为用户数据提供隐私保护，同时确保数据在上传到聚类中心的可用性。此外，本发明为了应对混合型数据中数值类型的不确定性，对用户数据分属性类别进行随机化扰动，服务端对数据进行聚类。在聚类过程中，本发明使用轮盘赌选举方法确定初始聚类中心，降低聚类点集的随机性对聚类结果的影响。在聚类迭代过程中，本发明引入扰动概率并结合属性权重重新定义新的距离计算公式。经实验结果检验，本发明对数据集的隐私保护效果更优，数据的可用性更好。

Description

面向边缘计算的本地化差分隐私混合数据迭代聚类算法

技术领域

本发明涉及边缘计算下数据的聚类发布领，特别是涉及边缘计算下的本地化差分隐私混合数据迭代聚类方案。

背景技术

随着物联网在各个领域中的迅猛发展和广泛应用，其在全球各地普及程度不断增加，越来越多的城市基础设施和移动智能设备产生了计算需求。随着嵌入式智能设备越来越多，仅仅依靠云计算这种集中计算的处理方式，已经很难处理运行在物联网上的应用和海量数据处理。针对云数据中心负载压力、数据隐私保护等问题，目前的云计算模式并不能有效克服这些问题。因此，边缘计算应运而生。边缘计算在智能设备种类繁多以及海量处理数据的背景下，可以有效解决云数据中心的负载以及网络通信效率问题。相比于传统的云计算模型，边缘计算将服务中心的计算任务交给边缘节点处理，使得在边缘终端上传数据之后，边缘节点可以实时处理和分析数据。此外，边缘计算减轻了云服务中心的负载压力和计算开销，具有数据安全性高、隐私性强、位置感知及低流量的优势。以医疗数据为例，在边缘计算中我们做出两个假设：(1)边缘设备愿意主动为数据收集着提供自己的数据信息；(2)数据收集者是真实的，不会恶意出售收据或者向第三方泄露数据。然而我们知道在实际的边缘环境当中，这两种假设在大多数情况下是不成立的，因此如果不对医疗数据进行处理而直接发布或是收集这些数据，可能会造成个人隐私信息的泄露问题，对个人的利益造成损害，甚至危及个人的安全。由此可知，隐私保护问题是边缘计算过程中的重要性不言而喻。要确保边缘计算中的隐私安全.就要对边缘设备上传的数据进行隐私保护，确保指定数据在第三方不可信的情况下依然可以保护数据的敏感信息，防止非法用户获得这些数据。本地化差分隐私技术随即响应等机制对数据扰动，确保了敏感信息的安全，同时将对数据的隐私保护处理交由边缘终端设备，因此非常适用于边缘计算中。

为此，本文设计了一种面向边缘计算下的本地化差分隐私混合数据迭代聚类方案。

发明内容

本发明旨在解决以上现有技术的问题。提出了一种面向边缘计算下的本地化差分隐私混合数据迭代聚类方案。本发明的技术方案如下：

一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，包括：用户端编码模块、用户端扰动模块、服务端选取聚类中心模块、服务端循环迭代聚类优化模块、更新聚类中心点集模块等五个模块，其中，

所述用户编码模块用于边缘计算中用户终端的数据编码；

所述用户端扰动模块用于边缘计算中用户终端数据的随机扰动；

所述服务端选取聚类中心模块用于为服务端生成初始的聚类中心，负责为边缘服务器提供非随机性的初始聚类点集；

所述服务端循环迭代聚类优化模块用于服务端聚类过程中聚类中心点的迭代优化，迭代过程中关联聚类的属性距离，聚类的数据个数以及聚类的密度阈值；

所述更新聚类中心点集模块用于服务端在获得用户上传的数据之后，根据聚类优化后的结果，重新计算聚类中心点；

进一步的，所述用户端编码模块，用于边缘计算中用户终端的数据编码工作，具体包括：

根据权利要求1所述的一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，所述用户端编码模块，用于边缘计算中用户终端的数据编码工作，具体包括：

针对于数值型数据，用户终端选择一个系数来缩放特征值，并将他们截断为整数，以考虑通信效率和隐私预算的节省。对于每个用户的数值型特征，将其转换为一个二进制的字符串B_ij＝{b₁,b₂,...,b_h}，其中h＝|B_ij|是字符串的长度，具体如下，

x_ij＝λ*(b₁*2^h-1+b₂*2^h-2+...+b_h-1*2¹+b_h)

其中λ是决定B_ij长度的系数，他提供了数据的准确性，隐私损失以及通信成本之间的度量。假设x_ij∈[0,1]，如果只需要一个位的字符串，那么选择λ＝1的情况下，B_ij只能表示为′0′或者′1′，这样就会丢失太多的信息。但是如果选择λ＝2^-10，h＝|B_ij|＝10，这样就保留了更多的信息。很明显h的值越大，转换后的数据精度越高，数据的可用性就高一些。每个数据X_i的总长度L＝∑h。

对于分类型数据，用户终端改进用户特征的二进制字符串。借鉴Pure-LDP方法中的Support函数，该函数被称作映射函数，Support将每一个可能的输出值y_i映射到一组输入x_i中，注意是每一个输出可能y可以映射到多个x_i。即，

Support(T)＝{i|T[i]＝1}

其中T为一个输入实例的二进制版本。

假设分类型特征x_ij的值域范围是x_ij＝{a₁,a₂,...,a_k}，将分类特征的k种输入代入到Support函数当中得到输出选择y。将x_ij的每一个取值映射到二进制字符串s中，对于任意x_ij属于y_i，那么就只有第k位被设置成1，其余位置被设置成0。(对分类型特征的值进行标号排序，将序号位k设置为1，其余位置设置成0)根据上述推导，同理当二进制字符串s中的每一位受到满足∈-LDP的随即响应机制的扰动。

对于任一输入的分类型特征值x_ij，生成其二进制字符串t，t满足，

t＝{t₁＝0,t₂＝0,...,t_k＝1,...,t_K＝0}

|t|＝K。K为字符串长度

进一步的，所述用户端扰动模块，用于边缘计算中用户终端数据的随机扰动，具体包括：

编码工作完成之后，针对数值型数据的特征，用户终端利用LDP的随即响应机制实现本地化的差分隐私保护，已知B_ij，则扰动之后的二进制字符串为则B_ij中的每一个比特位受到以下方式的扰动，

其中f为[0,1]之间的任意随机数，从这个扰动法则可以看出LDP是如何用随机响应机制来进行数据扰动的，其中每个比特位扰动为“1”或“0”的概率都是同时以1-f的概率回答真实值，从而当服务器获取用户数据后也无法知晓确切的真实值。f的选择和意义可以等价于∈，f越大隐私保护效果越强，但同时意味着数据可用性越低。

根据本地化差分隐私的定义，对于随即相应的两种回答t和t′以及查询函数Q，有，

Pr[Q(t)∈R]≤exp(∈)Pr[Q(t′)∈R]

其中R为输出结果集，代入概率p可以得到∈满足

针对分类型数据，对于任意x_ij属于y_i，那么就只有第k位被设置成1，其余位置被设置成0，s当中的每一位都受到满足∈-LDP的随即响应机制的扰动，则此时的最大敏感度Δ＝2。

考虑用一种新的方法进行扰动以减少从0扰动到1的概率，保证隐私的同时确保数据的可用性。

定理假设t当中的每一位都受到随即响应的扰动，则当扰动概率满足，

对于隐私预算∈，如果∈满足，

该方案是满足∈-LDP的。

根据改良的算法，我们将这种扰动机制应用到分类型数据上。

举例说明：假设患有某种疾病的患者的身体状况是数据当中的一个分类属性，那么有{正常，较度，中度，严重}四个等级，那么对于任意原始数据的输入，就会有四种情况，分别为：

{1,0,0,0} {0,1,0,0} {0,0,1,0} {0,0,0,1}

对每一位进行满足上述定理和∈-LDP的扰动即可。

进一步的，所述服务端选取聚类中心模块，用于为服务端生成初始的聚类中心，负责为边缘服务器提供非随机性的初始聚类点集，具体包括：

边缘服务端选择轮盘赌技术进行聚类中心的选取。轮盘赌技术的原理是将每一个个体的概率视为自适应度，通过产生一个在[0,1]之间的随机数判断其落在的区域，进而选择聚类中心。直观解释就是自适应度越大被选择的概率也就是越大。

首先设置初始参数然后从数据集当中随机选取一个记录作为聚类中心G_k，G＝G∪G_k，将G_k从中剔除，记录个数n＝n-1，k++。接下来计算每一个非中心点到已有中心点的最短距离d(X,G)，利用轮盘赌技术从中抽取下一个中心点G_k。如果k<K，则循环重复上述步骤直至满足条件。最短距离d可以表示为，

d(X,G)＝r(x,g)+c(x,g)

其中r(x,g)为数值型特征的距离，c(x,g)表示分类型特征的距离。

对于数值型特征，采用欧式距离进行距离的度量，则数据记录X到聚类中心的距离为：

其中j∈[1,j]，表示的是数值型属性的个数。同理针对分类型特征，由于无法通过具体的数值进行计算，距离的度量需要进行分类的讨论：

其中

其中γ是分类特征的权重，用来调节两种不同类型数据在对总体距离贡献度的比重，从而避免聚类结果值偏向分类型特征或者数值型特征。

进一步的，所述服务端循环迭代聚类优化模块，用于服务端聚类过程中聚类中心点的迭代优化，迭代过程中关联聚类的属性距离，聚类的数据个数以及聚类的密度阈值，具体包括：

在服务端进行初始聚类中心点集的选择之后，初始聚类中心点集是从用户扰动数据当中直接选择，随着数据量的增大，代表性不足，可能会出现一定的偏差，因此对聚类中心进行优化并更新中心点集，使得聚类所反映的结果更加精准，同时加强了中心点集的隐私性。在每一次的迭代过程当中执行下述聚类优化，通过该算法设置的密度阈值，降低数量较少的聚簇在选取聚类中心时产生的随机性，提升数量较大的聚簇针对聚簇边界的记录值的聚类效果。

聚类优化过程选取聚类密度最大阈值ρ_max以及聚类密度最小阈值ρ_min，flag代表迭代次数，目的是输出聚类集合G(G₁,G₂,...,G_k)。设置迭代次数必须大于0，此时进入循环的流程，针对聚类集合当中的每一个用户记录进行二进制编码操作，统计每一个聚类集合中数据记录的条数，记为count(G_i)，该值用于和聚类的密度阈值进行比较。如果count(G_i)小于最小的密度阈值ρ_min，该方法涉及到合并聚类集合的操作，首先根据编码后的数据记录计算聚类之间的欧式距离，目的是找出和当前聚类欧氏距离值最小的聚类集合，即，

G_k＝Math.min(d(G_i,G_k))

得到G_k之后，调用MergeCluster(G_i,G_k)函数进行聚类合并，然后更新聚类个数K减一；如果count(G_i)大于最大的密度阈值ρ_max，将该聚类分割成两个粒度更小的聚类，即，

X_i(X_i∈G_k)＝Math.max(d(X_i,G_k))

此时新的聚类中心点G_k+1＝X_i，聚类个数K加一。

进一步的，所述更新聚类中心点集模块，用于服务端在获得用户上传的数据之后，根据聚类优化后的结果，重新计算聚类中心点，具体包括：

服务提供者得到了用户上传的扰动数据集和类簇划分之后，将每一个类簇的用户记录的l个特征转换为的二进制形式通过属性权重更新聚类中心点。

服务端更新数值型属性值，该方法需要得到属于类簇O_k中数值型属性每一个二进制比特位的和，记为，

其中j表示数据记录当中的第j个特征值，h表示其二进制形式的第h位。对于服务器来说，服务提供端需要根据扰动数据来估计数据的真实价值，上述表达式所反映的仅仅是扰动价值，所以这就需要借助上文所提到的f。

我们设置f的值为用户端和服务端所共享的数据。根据随机响应的机制，分析在真值为1的情况下的回答为：Pr[b_h＝1|1]＝A*(1-q)+B*p，代入上述表达式为，

其中|O_k|表示类簇的大小，所以类簇中每一位的和表示为，

服务器根据上述表达式更新每个类簇的聚类中心的数值型属性，有，

服务端更新分类型属性值，具体流程如下，

服务器根据上述表达式更新每个类簇的聚类中心的分类型属性，有，

综上所述，更新之后的聚类中心点为o_k，在计算出新的质心之后，服务提供者发布新的聚类中心点集给用户端，重新根据d(X,G)度量最短距离并进行用户数据的聚类更新。

进一步的，根据上述模块，进行隐私性分析如下：

针对数值性数据，原始数据为t＝{t₁,t₂,...,t_h}，扰动后的字符串为 假设t当中的每一位都受到满足算法2的随机响应扰动，则当f满足

时，该方案是满足∈-LDP的。

根据本地化差分隐私的扰动机制，我们知道当的时候满足∈-LDP。

设置扰动的字符串为 原始数据为t＝{t₁,t₂,...,t_h}

假设和是同一特征的两个不同特征值，每一位的扰动版本设为t′，为了保证不同数据的隐私条件，结合本地化差分隐私的定理，代入上述结果我们可以得到如下表达式：

其中对于任意一个比特位，有：

则扰动每一个比特位的结果为：

所以代入上述结果，可以得到

结合证明开始时所提及的∈，证得以及扰动字符串是满足∈-LDP的。

针对分类型数据，假设t当中的每一位都受到随即响应的扰动，则当扰动概率满足

对于隐私预算∈，如果∈满足：

时，该方案是满足∈-LDP的。

我们设定一个隐私预算系数α，α为概率的选择方面提供了更大的灵活性，通过增加α，可以增加0比特位传输原始状态的概率。因此重新设定扰动概率，

根据本地化差分隐私的扰动机制，我们知道当的时候满足∈-LDP。

设置受扰动的字符串为 原始数据为t＝{t₁,t₂,...,t_h}

假设和是同一特征的两个不同特征值，每一位的扰动版本设为t′，为了保证不同数据的隐私条件，则有如下表达式：

结合本地化差分隐私的定理，代入上述结果我们可以得到：

由于(p and q<1)为确定参数，并且当两个值和互不相同时，敏感度取最大值为Δ＝2。

代入上式可以得到

所以结合证明开头所提到的∈，证得当

扰动字符串是满足∈-LDP的。

经过分析可以得知数值型属性和分类型属性均满足本地化差分隐私∈-LDP。

一种基于任一项所述系统的车联网数据共享方法，其包括以下步骤：

用户端编码步骤：聚类系统中用户端数据记录编码初始化，产生二进制字符串：B_ij＝{b₁,b₂,...,b_h}，数值型属性特征值编码：x_ij＝λ*(b₁*2^h-1+n₂*2^h-2+...+b_h-1*2¹+b_h)，分类型属性的特征值编码：将x_ij的每一个取值映射到二进制字符串s中，任意x_ij属于y_i，第k位被设置成1，其余位置被设置成0；

用户端扰动步骤：针对不同数据类型的用户记录进行随机化扰动，生成满足表达式Pr[Q(t)∈R]≤exp(∈)Pr[Q(t′)∈R]的二进制编码数据；

服务端选取聚类中心步骤：选择轮盘赌技术作为初始聚类中心点的选取办法，计算数值型属性和分类型属性的欧氏距离：d(X,G)＝r(x,g)+c(x,g)，将欧氏距离作为轮盘赌的自适应度选取下一个聚类中心点；

服务端循环迭代聚类优化步骤：对服务端的每一个用户数据记录进行二进制编码，计算聚类之间的欧氏距离，根据聚类密度阈值和count(G_i)值的对比结果进行合并或者差分聚类；

更新聚类中心点集步骤：结合随机扰动参数生成每一个数据记录属性的二进制比特位的和，根据属性权重公式 获得新的属性值，生成聚类中心点为o_k，重新根据d(X,G)度量最短距离并进行用户数据的聚类更新。

本发明的优点及有益效果如下：

本发明与现有技术相比，本发明的创新点和有益效果在于以下四个方面：

(1)本发明采用了一种保护云平台用户隐私数据的数据聚合算法LDPIA，实现了LDP机制，保证了在第三方云中心或者第三方聚合服务器无法通过聚类过程推断用户的隐私记录。中心服务器和边缘结点共享扰动概率，从而确保云服务器的隐私保护由边缘节点自行控制；

(2)较传统聚类中心选取办法相比，本发明采用轮盘赌算法，通过数据的自适应度选取初始的聚类中心点，消除了传统聚类方案中初始聚类中心点集选取的随机性，避免个别数据记录影响最终的聚类效果；

(3)本发明提出了C/S聚类迭代机制对聚类中心点集进行更新，该算法更适用于处理数据记录和聚类数量较大的环境，能够更加灵活使用在不同的边缘场景中；

(4)本发明在数据集上对本文所提出的聚类算法进行了广泛的实验，并与其他的聚类算法进行数据可用性和聚类效用性进行对比，结果表明，该算法在保证数据可用性的前提下具有更好的聚类效果。

附图说明

图1是本发明提供边缘环境聚类方案的系统模型图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。

本发明解决上述技术问题的技术方案是：

参照图1，本发明具体实施方式如下：

一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，包括：用户端编码模块、用户端扰动模块、服务端选取聚类中心模块、服务端循环迭代聚类优化模块、更新聚类中心点集模块等五个模块，其中，

所述用户编码模块用于边缘计算中用户终端的数据编码；

所述用户端扰动模块用于边缘计算中用户终端数据的随机扰动；

所述服务端选取聚类中心模块用于为服务端生成初始的聚类中心，负责为边缘服务器提供非随机性的初始聚类点集；

所述服务端循环迭代聚类优化模块用于服务端聚类过程中聚类中心点的迭代优化，迭代过程中关联聚类的属性距离，聚类的数据个数以及聚类的密度阈值；

所述更新聚类中心点集模块用于服务端在获得用户上传的数据之后，根据聚类优化后的结果，重新计算聚类中心点。

1、在用户终端最初编码阶段，对于每个用户的数值型特征，将其转换为一个二进制的字符串B_ij＝{b₁,b₂,...,b_h}，其中h＝|B_ij|是字符串的长度，具体如下，

x_ij＝λ*(b₁*2^h-1+b₂*2^h-2+...+b_h-1*2¹+b_h)

其中λ是决定B_ij长度的系数，他提供了数据的准确性，隐私损失以及通信成本之间的度量。对于分类型数据，用户终端改进用户特征的二进制字符串。借鉴Pure-LDP方法中的Support函数，该函数被称作映射函数，Support将每一个可能的输出值y_i映射到一组输入x_i中，注意是每一个输出可能y可以映射到多个x_i。即，

Support(T)＝{i|T[i]＝1}

其中T为一个输入实例的二进制版本。假设分类型特征x_ij的值域范围是x_ij＝{a₁,a₂,...,a_k}，将分类特征的k种输入代入到Support函数当中得到输出选择y。将x_ij的每一个取值映射到二进制字符串s中，对于任意x_ij属于y_i，那么就只有第k位被设置成1，其余位置被设置成0。根据上述推导，二进制字符串s中的每一位受到满足∈-LDP的随即响应机制的扰动。

2、编码工作完成之后，针对数值型数据的特征，用户终端利用LDP的随即响应机制实现本地化的差分隐私保护，已知B_ij，则扰动之后的二进制字符串为则B_ij中的每一个比特位受到以下方式的扰动，

其中f为[0,1]之间的任意随机数，从这个扰动法则可以看出LDP是如何用随机响应机制来进行数据扰动的，其中每个比特位扰动为“1”或“0”的概率都是同时以1-f的概率回答真实值，从而当服务器获取用户数据后也无法知晓确切的真实值。针对分类型数据，对于任意x_ij属于y_i，那么就只有第k位被设置成1，其余位置被设置成0，s当中的每一位都受到满足∈-LDP的随即响应机制的扰动，则此时的最大敏感度Δ＝2。

假设t当中的每一位都受到随即响应的扰动，则当扰动概率满足

对于隐私预算∈，如果∈满足，

该方案是满足∈-LDP的。

3、服务端在轮盘赌技术进行聚类中心的选取时，将每一个个体的概率视为自适应度，通过产生一个在[0,1]之间的随机数判断其落在的区域，进而选择聚类中心首先设置初始参数k＝1，然后从数据集当中随机选取一个记录作为聚类中心G_k，G＝G∪G_k，将G_k从中剔除，记录个数n＝n-1，k++。接下来计算每一个非中心点到已有中心点的最短距离d(X,G)，利用轮盘赌技术从中抽取下一个中心点G_k。如果k<K，则循环重复上述步骤直至满足条件。

4、在服务端循环迭代聚类优化阶段，聚类优化过程选取聚类密度最大阈值ρ_max以及聚类密度最小阈值ρ_min，flag代表迭代次数，目的是输出聚类集合G(G₁,G₂,...,G_k)。设置迭代次数必须大于0，此时进入循环的流程，针对聚类集合当中的每一个用户记录进行二进制编码操作，统计每一个聚类集合中数据记录的条数，记为cound(G_i)，该值用于和聚类的密度阈值进行比较。如果count(G_i)小于最小的密度阈值ρ_min，该方法涉及到合并聚类集合的操作，首先根据编码后的数据记录计算聚类之间的欧式距离，目的是找出和当前聚类欧氏距离值最小的聚类集合，即，

G_k＝Math.min(d(G_i,G_k))

得到G_k之后，调用MergeCluster(G_i,G_k)函数进行聚类合并，然后更新聚类个数K减一；如果count(G_i)大于最大的密度阈值ρ_max，将该聚类分割成两个粒度更小的聚类，即，

X_i(X_i∈G_k)＝Math.max(d(X_i,G_k))

此时新的聚类中心点G_k+1＝X_i，聚类个数K加一。

5、在服务端更新聚类中心点集的这个阶段，服务提供者得到了用户上传的扰动数据集和类簇划分之后，将每一个类簇的用户记录的l个特征转换为的二进制形式通过属性权重更新聚类中心点。

服务端更新数值型属性值，该方法需要得到属于类簇O_k中数值型属性每一个二进制比特位的和，记为，

其中j表示数据记录当中的第j个特征值，h表示其二进制形式的第h位。对于服务器来说，服务提供端需要根据扰动数据来估计数据的真实价值，上述表达式所反映的仅仅是扰动价值，所以这就需要借助上文所提到的f。

设置f的值为用户端和服务端所共享的数据。根据随机响应的机制，分析在真值为1的情况下的回答为：Pr[b_h＝1|1]＝A*(1-q)+B*p，服务器根据上述表达式更新每个类簇的聚类中心的数值型属性，有，

服务器根据上述表达式更新每个类簇的聚类中心的分类型属性，有，

综上所述，更新之后的聚类中心点为o_k，在计算出新的质心之后，服务提供者发布新的聚类中心点集给用户端，重新根据d(X,G)度量最短距离并进行用户数据的聚类更新。

上述实施例阐明的系统、装置、模块或单元，具体可以由计算机芯片或实体实现，或者由具有某种功能的产品来实现。一种典型的实现设备为计算机。具体的，计算机例如可以为个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、电子邮件设备、游戏控制台、平板计算机、可穿戴设备或者这些设备中的任何设备的组合。

术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。

Claims (7)

1.一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，包括：用户端编码模块、用户端扰动模块、服务端选取聚类中心模块、服务端循环迭代聚类优化模块、更新聚类中心点集模块等五个模块，其中，

所述用户编码模块用于边缘计算中用户终端的数据编码；

所述用户端扰动模块用于边缘计算中用户终端数据的随机扰动；

所述服务端选取聚类中心模块用于为服务端生成初始的聚类中心，负责为边缘服务器提供非随机性的初始聚类点集；

所述服务端循环迭代聚类优化模块用于服务端聚类过程中聚类中心点的迭代优化，迭代过程中关联聚类的属性距离，聚类的数据个数以及聚类的密度阈值；

所述更新聚类中心点集模块用于服务端在获得用户上传的数据之后，根据聚类优化后的结果，重新计算聚类中心点。

2.根据权利要求1所述的一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，所述用户端编码模块，用于边缘计算中用户终端的数据编码工作，具体包括：

针对于数值型数据，用户终端选择一个系数来缩放特征值，并将他们截断为整数，以考虑通信效率和隐私预算的节省。对于每个用户的数值型特征，将其转换为一个二进制的字符串B_ij＝{b₁,b₂,...,b_h}，其中h＝|B_ij|是字符串的长度，具体如下，

x_ij＝λ*(b₁*2^h-1+b₂*2^h-2+...+b_h-1*2¹+b_h)

其中λ是决定B_ij长度的系数，他提供了数据的准确性，隐私损失以及通信成本之间的度量。

对于分类型数据，用户终端改进用户特征的二进制字符串。借鉴Pure-LDP方法中的Support函数，该函数被称作映射函数，Support将每一个可能的输出值y_i映射到一组输入x_i中，注意是每一个输出可能y可以映射到多个x_i。即，

Support(T)＝{i|T[i]＝1}

其中T为一个输入实例的二进制版本。

假设分类型特征x_ij的值域范围是x_ij＝{a₁,a₂,...,a_k}，将分类特征的k种输入代入到Support函数当中得到输出选择y。将x_ij的每一个取值映射到二进制字符串s中，对于任意x_ij属于y_i，那么就只有第k位被设置成1，其余位置被设置成0。(对分类型特征的值进行标号排序，将序号位k设置为1，其余位置设置成0)根据上述推导，同理当二进制字符串s中的每一位受到满足∈-LDP的随即响应机制的扰动。

对于任一输入的分类型特征值x_ij，生成其二进制字符串t，t满足，

t＝{t₁＝0,t₂＝0,...,t_k＝1,...,t_K＝0}

|t|＝K。K为字符串长度。

3.根据权利要求2所述的一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，所述用户端扰动模块，用于边缘计算中用户终端数据的随机扰动，具体包括：

编码工作完成之后，针对数值型数据的特征，用户终端利用LDP的随即响应机制实现本地化的差分隐私保护，已知B_ij，则扰动之后的二进制字符串为则B_ij中的每一个比特位受到以下方式的扰动，

其中f为[0,1]之间的任意随机数，从这个扰动法则可以看出LDP是如何用随机响应机制来进行数据扰动的，其中每个比特位扰动为“1”或“0”的概率都是同时以1-f的概率回答真实值，从而当服务器获取用户数据后也无法知晓确切的真实值。f的选择和意义可以等价于∈，f越大隐私保护效果越强，但同时意味着数据可用性越低。

根据本地化差分隐私的定义，对于随即相应的两种回答t和t′以及查询函数Q，有，

Pr[Q(t)∈R]≤exp(∈)Pr[Q(t′)∈R]

其中R为输出结果集，代入概率p可以得到∈满足

针对分类型数据，对于任意x_ij属于y_i，那么就只有第k位被设置成1，其余位置被设置成0，s当中的每一位都受到满足∈-LDP的随即响应机制的扰动，则此时的最大敏感度Δ＝2。

定理假设t当中的每一位都受到随即响应的扰动，则当扰动概率满足

对于隐私预算∈，如果∈满足，

该方案是满足∈-LDP的。

根据改良的算法，我们将这种扰动机制应用到分类型数据上。

4.根据权利要求3所述的一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，所述服务端选取聚类中心模块，用于为服务端生成初始的聚类中心，负责为边缘服务器提供非随机性的初始聚类点集，具体包括：

边缘服务端选择轮盘赌技术进行聚类中心的选取。轮盘赌技术的原理是将每一个个体的概率视为自适应度，通过产生一个在[0,1]之间的随机数判断其落在的区域，进而选择聚类中心。直观解释就是自适应度越大被选择的概率也就是越大。

首先设置初始参数k＝1，然后从数据集当中随机选取一个记录作为聚类中心G_k，G＝G∪G_k，将G_k从中剔除，记录个数n＝n-1，k++。接下来计算每一个非中心点到已有中心点的最短距离d(X,G)，利用轮盘赌技术从中抽取下一个中心点G_k。如果k<K，则循环重复上述步骤直至满足条件。

5.根据权利要求4所述的一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，所述服务端循环迭代聚类优化模块，用于服务端聚类过程中聚类中心点的迭代优化，迭代过程中关联聚类的属性距离，聚类的数据个数以及聚类的密度阈值，具体包括：

聚类优化过程选取聚类密度最大阈值ρ_max以及聚类密度最小阈值ρ_min，flag代表迭代次数，目的是输出聚类集合G(G₁,G₂,...,G_k)。设置迭代次数必须大于0，此时进入循环的流程，针对聚类集合当中的每一个用户记录进行二进制编码操作，统计每一个聚类集合中数据记录的条数，记为count(G_i)，该值用于和聚类的密度阈值进行比较。如果count(G_i)小于最小的密度阈值ρ_min，该方法涉及到合并聚类集合的操作，首先根据编码后的数据记录计算聚类之间的欧式距离，目的是找出和当前聚类欧氏距离值最小的聚类集合，即，

G_k＝Math.min(d(G_i,G_k))

得到G_k之后，调用MergeCluster(G_i,G_k)函数进行聚类合并，然后更新聚类个数K减一；如果count(G_i)大于最大的密度阈值ρ_max，将该聚类分割成两个粒度更小的聚类，即，

X_i(X_i∈G_k)＝Math.max(d(X_i,G_k))

此时新的聚类中心点G_k+1＝X_i，聚类个数K加一。

6.根据权利要求5所述的一种基于边缘计算下的本地化差分隐私数据保护方案，其特征在于，所述更新聚类中心点集模块，用于服务端在获得用户上传的数据之后，根据聚类优化后的结果，重新计算聚类中心点，具体包括：

服务提供者得到了用户上传的扰动数据集和类簇划分之后，将每一个类簇的用户记录的l个特征转换为的二进制形式通过属性权重更新聚类中心点。

服务端更新数值型属性值，该方法需要得到属于类簇O_k中数值型属性每一个二进制比特位的和，记为，

其中j表示数据记录当中的第j个特征值，h表示其二进制形式的第h位。对于服务器来说，服务提供端需要根据扰动数据来估计数据的真实价值，上述表达式所反映的仅仅是扰动价值，所以这就需要借助上文所提到的f。

设置f的值为用户端和服务端所共享的数据。根据随机响应的机制，分析在真值为1的情况下的回答为：Pr[b_h＝1|1]＝A*(1-q)+B*p，服务器根据上述表达式更新每个类簇的聚类中心的数值型属性，有，

服务器根据上述表达式更新每个类簇的聚类中心的分类型属性，有，

综上所述，更新之后的聚类中心点为o_k，在计算出新的质心之后，服务提供者发布新的聚类中心点集给用户端，重新根据d(X,G)度量最短距离并进行用户数据的聚类更新。

7.一种基于权利要求1-6任一项所述方案的基于边缘计算下的本地化差分隐私数据保护方法，其特征在于，包括以下步骤：

用户端编码步骤：聚类系统中用户端数据记录编码初始化，产生二进制字符串：B_ij＝{b₁,b₂,...,b_h}，数值型属性特征值编码：x_ij＝λ*(b₁*2^h-1+b₂*2^h-2+...+b_h-1*2¹+b_h)，分类型属性的特征值编码：将x_ij的每一个取值映射到二进制字符串s中，任意x_ij属于y_i，第k位被设置成1，其余位置被设置成0；

用户端扰动步骤：针对不同数据类型的用户记录进行随机化扰动，生成满足表达式Pr[Q(t)∈R]≤exp(∈)Pr[Q(t′)∈R]的二进制编码数据；

服务端选取聚类中心步骤：选择轮盘赌技术作为初始聚类中心点的选取办法，计算数值型属性和分类型属性的欧氏距离：d(X,G)＝r(x,g)+c(x,g)，将欧氏距离作为轮盘赌的自适应度选取下一个聚类中心点；

服务端循环迭代聚类优化步骤：对服务端的每一个用户数据记录进行二进制编码，计算聚类之间的欧氏距离，根据聚类密度阈值和count(G_i)值的对比结果进行合并或者差分聚类；

更新聚类中心点集步骤：结合随机扰动参数生成每一个数据记录属性的二进制比特位的和，根据属性权重公式 获得新的属性值，生成聚类中心点为o_k，重新根据d(X,G)度量最短距离并进行用户数据的聚类更新。