Mondrian算法与差分隐私
K匿名保证存储在发布数据集中的每条个体记录对于敏感属性不能与其他的K-1个个体相区分，通俗的说就是同一个准标识符集至少要有K条记录，因此观察者无法通过准标识符集链接记录。差分隐私需要做到的就是攻击者的知识不会因为新样本的出现或消失而发生变化。
传送门：开源仓库
K匿名算法
标识符：可以直接确定一个个体，如身份证号、姓名等。
准标识符集：可以和外部表链接来识别个体的最小属性集，如邮编、生日、性别等。
敏感数据：用户不希望被人知道的数据，如薪水、疾病历史、购买偏好等。
K-匿名技术可以保证存储在发布数据集中的每条个体记录对于敏感属性不能与其他的K-1个个体相区分，通俗的说就是同一个准标识符集至少要有K条记录，因此观察者无法通过准标识符集链接记录。
K-匿名实施通常是通过概括和隐匿。概括指对数据进一步抽象描述，比如把年龄概括成年龄段。隐匿指隐藏数据的部分信息，比如邮政编码隐藏后几位。这么处理降低了数据的精度，使得每条记录与其他K-1条记录有完全相同的准标识符集，降低了链接攻击所导致的隐私泄露风险。
K-匿名技术保证了：
- 无法得知特定的人是否在公开的数据中
- 无法确定特定的人是否有某项敏感属性
- 无法确认某条数据对应哪个人
K-匿名的缺陷：虽然可以阻止身份信息的公开，但无法防止属性信息的公开，导致无法抵抗同质攻击、背景知识攻击、补充数据攻击等。
- 同质攻击：K-匿名的敏感数据一样，则只要知道一个用户的准标识符集，就能知道该用户具有这个敏感数据。
- 背景攻击：通过用户的准标识符集确定用户所在的等价信息表，同时观察者通过背景知识了解到用户没有某一敏感数据，就可以用排除法得到用户的敏感数据。
- 补充数据攻击：当公开的数据有多种类型，若这些数据的K-匿名方法不同，那么攻击者可以通过关联多种数据推测用户信息。
差分隐私
差分隐私需要做到的就是 攻击者的知识不会因为新样本的出现或消失而发生变化。
比如说一群人出去聚餐，已知总共10个人，有8个是现充，2个是单身狗，然后聚会到一半张三有事情走了，这时还剩下8个现充和1个单身狗，这样就暴露了张三是单身狗的事实。就没有做到差分隐私保护。
相邻数据集：两个数据集有且仅有一条数据不一样，则二者互为相邻数据集。
差分隐私的形式化定义：对于一个随机化算法，其分别作用于两个相邻数据集得到的两个输出分布难以区分。
通俗来说就是，如果该算法作用于任何相邻数据集，得到一个特定输出O的概率差不多，那么我们就说这个算法能达到差分隐私效果。观察者通过观察输出结果很难察觉出数据集的微小变化。
一般做法：从一个不满足差分隐私的算法出发，往算法里适当加入一定噪声，使其输出满足差分隐私的要求。
拉普拉斯机制
假设发布一个数据集D中糖尿病患者的数目，修改D中任意一个病患的数据，查询结果最多会改变1。直观地说，如果能用噪声“掩盖”这种不大于1的改变，就能满足差分隐私。
可以向查询结果中加入一个服从拉普拉斯分布的噪声：
噪声参数 lambda 决定拉普拉斯分布的方差，噪声越大方差越大。
噪声参数取决于修改一个人的数据时，查询结果最大会改变多少(敏感度)。
Mondrian
等价类：表T由多组元组组成。 T关于属性x1，…，xd的等价类是T中所有包含x1，…，xd的相同值(x1，…，xd)的元组的集合。 在SQL中，这类似于x1，…，xd上的group by查询。
Partitioning
整个数据集分区肯定是符合K-匿名的。
算法过程就是不断将符合K-匿名的分区再进行细分，直到分区不能按列中值划分成更小的K-匿名分区为止。
算法如下：
- 初始化结果集为空集。
- 初始化工作集为一个原数据集的分区。
- 当工作集非空时，从工作集中取出一个分区：
- 计算该分区中所有列的相对跨度（就是有多少种取值再除以总的规模）
- 对分区中的列按相对跨度降序排序，然后遍历这些列。对遍历到的那一列：
- 用该列的中值的位置将分区划分为两个新分区。
- 判断新的分区是否符合K-匿名要求：
- 若符合，将两个新分区加入工作集中，退出循环。
- 若不符合，继续遍历下一个列。
- 如果没有一个列能有效划分(符合K-匿名)，就不再细分该分区，将该分区加入结果集中。
- 返回结果集。
Data Aggregation
获得分区后，还要对数据进行聚合。可以将数值聚合为它们的范围或平均值，将分类属性聚合为它们的联合。