第四章：k-匿名性（k-Anonymity）笔记

4.1 k-匿名性的定义

  • 非正式：数据集中每个个体都属于一个至少包含 k 个人的组，且组内所有成员在“准标识符”（QI）上取值相同，从而“融入人群”。攻击者只能把个体缩小到某个组，但无法确定具体是哪一个人。
  • 形式化定义：对每一行 (r_1)，至少存在 (k-1) 行 (r_2,\dots,r_k)，使得它们在准标识符列上的投影完全相同。
  • 准标识符（QI）：必须事先固定，因为攻击者会利用这些属性进行链接攻击。QI 是能组合起来识别个体的属性，如年龄、邮编、性别。

4.2 检查 k-匿名性

  • 简单实现：遍历每一行，查询数据框中与其 QI 值匹配的行数；若任一组少于 k，则返回 False。
  • 注意：简单实现将所有列都视为 QI；若只想检查子集，需替换 df.columns。
  • 复杂度：朴素算法 (O(n^2))，效率很低。实际应用应使用 groupby 等向量化操作。
  • 示例：小数据集不满足 k=2，但满足 k=1（每行自成一組）。

4.3 通过泛化满足 k-匿名性

  • 泛化：修改数据使其更不具体，更可能匹配其他个体。例如年龄四舍五入到最近的 10 岁，邮编右位补零。
  • 实现：使用 generalize 函数和 depths 字典控制每列替换几位数字。
  • 示例：5 行数据泛化后仍不满足 k=2；继续泛化会导致所有数据变成相同值，信息几乎全部丢失。
  • 关键挑战：达到有意义的 k 往往需要从数据中移除大量信息。

4.4 更多数据是否改善泛化？

  • 更多数据通常有助于形成更大的组，减少泛化需求。
  • 但离群点会严重阻碍：即使有 32,000 行，泛化后仍可能不满足 k=2。
  • 最优泛化是 NP-hard（Meyerson & Williams, 2004）：找到信息损失最小的泛化方案在计算上不可行。

4.5 移除离群点

  • 方法：裁剪（clipping）极端值，如年龄限制在 10–60，教育至少 5th–6th 年级。
  • 效果：在 500 行数据上，裁剪后再泛化可达到 k=7。
  • Clipping vs. Bucketing：
    • Clipping：把超出上下界的值截断到边界，用于限制极值、控制敏感度。
    • Bucketing：把值映射到区间/类别，用于创建有意义的类别、泛化数据。

4.6 同质性攻击（Homogeneity Attack）

  • 定义：即使组大小满足 k，若组内敏感属性（如诊断）全都相同，攻击者仍可推断个体敏感信息。
  • 例子：一个 3-匿名组中所有人诊断都是“流感”，攻击者知道目标在组内，就能推断其诊断也是流感。
  • 说明：匿名集够大，但敏感属性缺乏多样性，隐私仍然泄露。
  • 缓解：ℓ-多样性、t-接近性，但仍有局限，尤其是在高维数据或强背景知识下。

总结

  • k-匿名性是数据属性，而非算法属性。
  • 计算昂贵：朴素检查 (O(n^2))，最优泛化 NP-hard。
  • 离群点、同质性攻击、背景知识都会破坏其保护效果。
  • 因此引出差分隐私：不依赖分组，不假设攻击者背景知识，提供更稳健的隐私保证。

Q&A

差分隐私算不算k等于数据集规模时的k匿名

不算。差分隐私和k匿名是两个不同范畴的隐私定义。

而且当K等于数据集的规模时意味着该数据集已经被泛化到可用性极差。

词汇表

术语 说明
k-匿名性 每个个体属于至少 k 人的组，组内 QI 相同
准标识符（QI） 能组合起来识别个体的属性，如年龄、邮编、性别
泛化 将具体值改为更笼统的值，如年龄 34 → 30–39
裁剪（Clipping） 将超出上下界的值截断到边界
分桶（Bucketing） 将值映射到区间/类别
同质性攻击 利用组内敏感属性缺乏多样性推断个体敏感信息
NP-hard 计算复杂性理论中的难解问题类
ℓ-多样性 要求每个匿名组内敏感属性至少有 ℓ 个不同取值
t-接近性 要求组内敏感属性分布接近整体分布