k匿名性
在上一篇文章差分隐私进阶-去标识和重标识攻击中使用重标识攻击来获取隐私数据，这篇文章就介绍了使用k-匿名性来解决这个问题。
属性定义：令\(B(A_1, A_2, ..,A_n)\)是一个有限数据的元组（一行数据称为元组）表格，其中表格B的有限属性集为\(Q_T=\{A_1, A_2, ...,A_n\}\)。
准标识符定义：令U为一个实体集合，\(T(A_1, A_2,... ,A_n)\)为实体集合的信息表， \(f_c : U \to T， f_g: T \to U\)分别表示从实体映射到表格和表格映射到实体。准标识符\(p_i\)满足以下条件：
\[f_g(f_c(q_i)[Q_T])=p_i \]表示准标识符能够从实体集合U中映射出表格T中的数据，这些数据又能从表格T映射出实体U的实体。
K-匿名性定义：令\(RT(A_1, A_2, ..,A_n)\)是一个表格，\(QI_{RT}\)是与之相关的准标识符。当且仅当\(RT_{[QI_{RT}]}\)中的每个数值序列至少出现k次时，才能称为满足k-匿名性。
比如，一张表中，\(QI_{RT}=\{name, id\}\)， 则这个数值序列至少出现k次。
验证k-匿名性
构建一个包含年龄和两个考试分数的表格
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from pandas import DataFrame
raw_data = {
'first_name': ['Jason', 'Molly', 'Tina', 'Jake', 'Amy'],
'last_name': ['Miller', 'Jacobson', 'Ali', 'Milner', 'Cooze'],
'age': [42, 52, 36, 24, 73],
'preTestScore': [4, 24, 31, 2, 3],
'postTestScore': [25, 94, 57, 62, 70]}
#df = pd.DataFrame(raw_data, columns = ['first_name', 'last_name', 'age', 'preTestScore', 'postTestScore'])
df = pd.DataFrame(raw_data, columns = ['age', 'preTestScore', 'postTestScore'])
df
根据k-匿名性的定义，我们实现一个函数来验证该表格满足多少匿名性。
def is_k_anonymized(df:DataFrame, k):
for index, row in df.iterrows():
query = ' & '.join([f"{col} == {row[col]}" for col in df.columns])
rows = df.query(query)
if rows.shape[0] < k:
return False
return True
print(is_k_anonymized(df, 1))
print(is_k_anonymized(df, 2))
# 输出：
# True
# False
### 泛化数据来满足k-匿名性
泛化是指将数据修改为不那么特殊的数据，可以和其他数据相匹配。比如，可以对年龄的只保留十位有效数字。通过修改数据来达到满足k-匿名性。
### 引入更多的数据可以减少泛化影响吗
我们读入上一篇的数据，看看是否能够轻易的通过泛化使其满足k-匿名性
adult_data = pd.read_csv("./data/data_ch1.csv")
adult_data.head()
现在，将年龄，受教育年数作为准标识。我们只对这2个属性做泛化处理。尝试让其满足k=2的匿名性。
df = adult_data[["Age", "Education-Num"]]
df.columns = ["age", "deu"]
is_k_anonymized(df, 1)
# 输出：True
is_k_anonymized(df, 2)
# 输出：False
可以发现，该数据不满足k=2的属性,下面我们将其泛化一下，来达到满足k=2的属性
# 首先对各列的NAN值进行填充
for col in df.columns:
df[col].fillna((int(df[col].mean())))
# 定义泛化函数
def generalize(x:int):
return x%10
df=df.apply(generalize)
我将上面的数据直接泛化到0-10之间了。下面我们来看看是否符合k=2的匿名性
is_k_anonymized(df, 2)
# 输出：True
其实，当数据量也大，就越容易满足k-匿名性。上面所做的实验是采用了全局泛化技术。还有局部泛化技术。局部泛化技术是通过统计准标识符属性下的特殊数值进行泛化处理，尽量将损失降到最小。
## Datafly算法
算法的步骤：
* 对每个准标识符属性的取值进行数量统计，对取值数量最大的标识符进行层级化的泛化
* 在泛化后的表格进行k-匿名性检测，如果不合格就泛化一下一个准标识属性。
for col in df.columns:
print(f"{col}列： {df[col].value_counts().shape[0]}")
# 输出：
# age列： 69
# deu列： 16
可以看出，age的取值数量最大，下面对其进行泛化处理。
df["age"]=df["age"].apply(lambda x: x%10)
is_k_anonymized(df, 2)
# 输出 False
for index, row in df.iterrows():
query = ' & '.join([f"{col} == {row[col]}" for col in df.columns])
rows = df.query(query)
if rows.shape[0] < 2:
print(query)
# 输出：
"""
age == 2 & deu == 2
age == 9 & deu == 2
age == 9 & deu == 1
age == 2 & deu == 1
"""
然后，我们可以看到在对age进行泛化处理后的数据，依旧有4组数据不满足k-匿名性，则对edu进行泛化处理。
df["deu"]=df["deu"].apply(lambda x: x%6)
is_k_anonymized(df, 2)
# 输出
# True