1，Different Privacy形式定义
Differential Privacy：A randomized algorithm M with domain N，|X| is (ε, δ)-differentially private if for all S ⊆ Range(M) andfor all x, y ∈ N|X| such that ∥x − y∥1 ≤ 1:
Pr[M(x) ∈ S] ≤ exp(ε) Pr[M(y) ∈ S] + δ, 理解：也就是说对于一个数据库，个人数据对整个查询影响在预算内，在算式里面 δ是微不足道的 对于差别只有一条记录的两个数据集，查询它们获得相同值的概率非常非常的接近
2，实现机制：
目前常用的有两种方法，一个是Laplace机制，在查询结果里加入Laplace分布的噪音，适用于数值型输出，另外一个是指数机制，在查询结果里用指数分布来调整概率，适用于非数值型输出
2.1，Laplace机制
对数值型计算（numerical function），使用Laplace 机制就可以实现DP，函数 f 是一个提供 ϵ-DP 的查询函数，f (n) = count (i) + noise，其中noise 是服从某种随机分布的噪声。添加的noise就是就是概率服从拉普拉斯分布函数
我们在其中加入噪音要使其数学期望为0，即u=0，我们令x=df/E，则
拉普拉斯机制图示
当f 噪声为0时，即输出count 时，Pr 概率是最高的；当f(D) 以Pr 概率产生噪声noise，f(D') 以Pr' 概率产生噪声noise'，两者输出值相同为count' 时， Pr 与 Pr' 的比值控制在exp( ϵ ) 内。
证明：
记d = count (D) - count (D')，，D和D'为兄弟集合，那么对于
2.2，指数机制
我们记O 为候选项目集合，o 为候选项目，函数q(D, o) 输出条目o 在D 中的出现次数，一个算法
输出 o∈O 的概率正比于exp（E*q(D,r)）/2 dq，则说M 是满足 ϵ-DP 的指数机制。其中
dq称为敏感度。
3,注意
敏感度（sensitivity): 敏感度分为全局敏感度和局部敏感度，通常情况下采用全局敏感度会加入过大的噪音，使数据失真，但弱使用局部敏感度，在一定程度上就会泄露数据分布信息，这个时候就有了 平滑敏感度
其他知识
差分隐私可以通过向聚合查询结果添加随机化"噪声"来实现，以保护个人的条目，而不会显著改变查询结果。 1.0聚合查询：一种查询（SQL语句,它通过包含一个聚合函数（如Sum或 Avg ）来汇总来自多个行的信息 1.1聚合函数：聚合函数对一组值(数据库中行)执行计算并返回单一的值。除了COUNT以外，聚合函数忽略空值。聚合函数经常与SELECT语句的 GROUP BY 子句一同使用。
常用范数 这里以Cn空间为例，Rn空间类似。
最常用的范数就是p-范数。若
那么
可以验证p-范数确实满足范数的定义。其中三角不等式的证明不是平凡的，这个结论通常称为闵可夫斯基(Minkowski）不等式。
当p取1,2.......N
1-范数：║x║1=│x1│+│x2│+…+│xn│
2-范数：║x║2=（│x1│2+│x2│2+…+│xn│2）1/2
∞-范数：║x║∞=max（│x1│，│x2│，…，│xn│）
网友评论