Programming Differential Privacy 阅读参考（part 1）

ch2 De-identification

去标识（De-identification），是指从数据集中删除标识信息的过程，有时会把去标识与匿名（Anonymization）和假名（Pseudonymization）看作同义词

个人标识信息PII，一般与标识信息同义，理解为在日常生活中可以唯一标识特定个人的信息

对信息进行去标识，直接将包含标识信息的列移除即可（e.g. 删去姓名列）

关联攻击（Linkage Attack）：如果去标识的数据集，与攻击者拥有的辅助信息之间存在重叠列（overlapping column），攻击者就可以关联（JOIN）这两个表，如果只能检索到一行数据，就实现了对特定个体的定位，也就是重识别（re-identify）

在实际应用中，很可能一个数据点就可以重新标识一行数据，常见信息的组合使用（e.g. 生日+邮政编码）也可以获得很高的重识别概率

聚合：只发布聚合数据（e.g. 平均值，求和），这个方法主要面临两个问题：

• 小群组问题：聚合统计结果无法隐藏小分组的个体信息（e.g.只包含一个个体的分组）
• 差分攻击：对相同的数据，获取多个聚合统计结果，从而推出隐私信息，如下例所示：

第一次查询：adult['Age'].sum()
第二次查询：adult[adult['Name'] != 'Karrie']['Age'].sum()
用第一次查询结果-第二次查询结果，即可得到Karrie的年龄

因此，发布可用性很高的数据会提高隐私保护的难度，同时，我们很难区分恶意和非恶意问询

ch3 k-匿名性

k-匿名性是一个正式的隐私定义。我们的直觉是，一条辅助信息不应该“过多地”缩小个人possible records的范围，k-匿名性的定义可以形式化这个直觉，也就是说，k-匿名性的设计是为了确保每个人都可以“融入人群”。

准标识符（quasi-identifier）：与直接标识符（例如身份证号）不同，单独使用时无法确定一个人，但结合其他信息可唯一确定个人的标识符（例如年龄、工作地点、性别、受教育水平等）

虽然k-匿名性的数学定义看上去较复杂，但主要思想是，通过发布精度较低的数据，使得每条记录至少与数据表中其他k-1条记录具有完全相同的准标识符属性值，从而减少链接攻击所导致的隐私泄露

任意一个数据集都天然地满足k=1的k匿名性

验证是否满足k-匿名性：

# 循环访问行，对于每一行，我们查询数据记录,查看有多少行与准标识符的值匹配
# 关于join方法：https://www.runoob.com/python/att-string-join.html
def isKAnonymized(df, k):
     # df.iterrows( )函数：可以返回所有的行索引，以及该行的所有内容
	for index, row in df.iterrows(): 
        # df.columns：表中的所有列
		query = ' & '.join([f'{col} == {row[col]}' for col in df.columns])
        # df.query()：查询函数
		rows = df.query(query)
		if rows.shape[0] < k: # shape[0]：行数
			return False
	return True

检查数据集是否满足k-匿名性的计算开销很大，朴素算法的复杂度是O(n²)，更快的算法需要相当大的存储空间

泛化数据以满足k-匿名性

泛化（Generalization）：将数据修改为不那么特殊的数据，使其更可能与其他个体的数据相匹配

数值型的数据容易进行泛化（e.g.将年龄的个位数替换成0），但通常需要从数据中移除相当多的信息，才能使数据集满足合理k取值下的k-匿名性，而且即使增加数据的数量，也很难降低满足k-匿名性的难度

异常值（Outlier）：与其他个体差异非常大的个体，即使经过泛化处理也很难融入任何分组中

异常值使得实现k-匿名性变得非常具有挑战性，即使对于较大的数据集也是如此。实现满足k-匿名性的最优泛化方法是一个NP-hard问题

移除异常值

完全消除异常值的方法：将数据集中每个个体的数据（e.g. 年龄）限制在一个特定范围内