k匿名（k-Anonymity）
k匿名技术参考论文：L.Sweeney. Achieving k-anonymity privacy protection using generalization and suppression. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems,10(5), 2002; 571-588.
其中对于k匿名的定义如下：
对于一个数据集的不同属性，或者说，不同列。可以根据其作用粗略划分为三种，标识符，准标识符，与隐私数据。
标识符能够唯一确定一项数据，而不同准标识符的组合也可能可以确定一项数据。而隐私数据顾名思义，是隐私保护的对象。
| 身份证号 | 性别 | 家庭住址 | 所得疾病 |
| 123456789 | 男 | xx市xx街道xx小区 | 某传染病 |
例如上表，身份证号即是标识符，而性别和家庭住址可以作为准标识符，他们具备一定的信息，并且组合在一起之后有可能可以确定这一条数据的所有者。而所得疾病即是我们需要保护的隐私信息。
k匿名需要满足的条件就是，对于准标识符的任意组合，搜索出来的结果都需要至少有k条。
例如，上表中以（性别，家庭住址）为准标识符，那么以（男，xx市xx街道xx小区）为条件，去数据集中搜索，最终得到至少k条数据，类似的，用其他任何可能的条件去搜索，最终得到的数据条数都大于等于k，那么就说这个数据集满足k匿名。
精确度的计算
论文中对于精确度的定义如下：
我个人认为这个公式应当翻译成：
prec=1-（各个准标识符的泛化程度（当前高度h/总泛化树高度）之和）/（准标识符个数）
adult数据集
数据集官方网址：UCI Machine Learning Repository: Adult Data Set
对于数据集的介绍引用自
云隐雾匿 的 Adult数据集分析（一）
Adult数据集（即“人口普查收入”数据集），由美国人口普查数据集库 抽取而来，其中共包含48842条记录，年收入大于50k美元的占比23.93%，年收入小于50k美元的占比76.07%，并且已经划分为训练数据32561条和测试数据16281条。 该数据集类变量为年收入是否超过50k美元，属性变量包括年龄、工种、学历、职业等 14类重要信息，其中有8类属于类别离散型变量，另外6类属于数值连续型变量。该数据集是一个分类数据集，用来预测年收入是否超过50k美元。
该数据集总共15列，包括14个属性与一个结论。
结论的取值为字符串，仅有两个：’ >50K’和’ <=50K’。
注意，该数据集中的每个字符串前面都有一个空格。
全部属性标签如下：
#属性标签
attributeLabels =["age", #0年龄 int64
"workclass", #1工作类型 object
"fnlwgt", #2人口特征权重 int64
"education", #3学历 object
"education_num", #4受教育时间 int64
"marital_status", #5婚姻状态 object
"occupation", #6职业 object
"relationship", #7关系 object
"race", #8种族 object
"sex", #9性别 object
"capital_gain", #10资本收益 int64
"capital_loss", #11资本损失 int64
"hours_per_week", #12每周工作小时数 int64
"native_country", #13原籍 object
"wage_class"] #14收入类别 object
对于第三个属性‘fnlwgt’，网上众说纷纭，有说是什么信息录入员编号的（然而实际数据长短不一，不太可能），又说代表这条数据真正的人数的（计算之后大概60多亿，也不太可能）。
感觉都不对，不过官方文档adult.names中有给出解释：
根据最后一段可以看出这个所谓“最终权重”应当包含了人口特征信息，具体包含哪些信息则可以参考上文给出的 3 sets of controls。
但是最后一句话有说，这个权重数据尽在州内适用，然而这个数据集中汇聚了全部51个州的数据，所以如果我没有翻译错的话，这个人口特征权重（fnlwgt）实际上不具备参考价值。
代码实现
1.导入包与导入一些字符串配置
import numpy as np
import pandas as pd
#配置信息
#数据集文件路径
censusData_FilePath='data/adult.data'
#属性标签
attributeLabels =["age", #0年龄 int64
"workclass", #1工作类型 object
"fnlwgt", #2人口特征权重 int64
"education", #3学历 object
"education_num", #4受教育时间 int64
"marital_status", #5婚姻状态 object
"occupation", #6职业 object
"relationship", #7关系 object
"race", #8种族 object
"sex", #9性别 object
"capital_gain", #10资本收益 int64
"capital_loss", #11资本损失 int64
"hours_per_week", #12每周工作小时数 int64
"native_country", #13原籍 object
"wage_class"] #14收入类别 object
#准标识符
quasi_identifier_list=[]
quasi_identifier_DGH_list=[]
quasi_identifier_VGH_list=[]
quasi_identifier_height_list=[]2.引入准标识符信息
泛化树通过父母节点表示法存储在数组中，这样就能够快速地找到每个节点的父母节点，同时为了方便计算，增加高度项，代表当前节点在泛化树中的高度。
例如，工作类型的泛化树如下：
由于后续使用了replace这个函数，所以标签的字符串不能一致，加上了hx作为后缀，x为层高。
#marital-status属性标签
marital_attributeLabels=['***', #0抑制标签
'Married-h2', #1已婚
'Alone', #2独自一人
'Married-h1', #3已婚
'Single', #4单身
'Widowhood', #5鳏寡
'Married-civ-spouse', #已婚-公民-配偶
'Married-AF-spouse', #已婚-无房-配偶
'Separated', #分居
'Divorced', #离婚
'Never-married', #未婚
'Widowed', #寡居
'Married-spouse-absent' #已婚-配偶-不在
]
#marital-status的泛化树
vgh_marital=pd.DataFrame({'value': marital_attributeLabels,
'parent':[-1,0,0,1,2,2,3,3,3,4,4,5,5],
'height':[3,2,2,1,1,1,0,0,0,0,0,0,0]})
quasi_identifier_list.append(attributeLabels[5]) #将marital-status设置为准标识符
quasi_identifier_DGH_list.append(3)
quasi_identifier_VGH_list.append(vgh_marital)
quasi_identifier_height_list.append(0)
print(vgh_marital)另外再加两个准标识符，种族与婚姻状况。
#race属性标签
race_attributeLabels =[ '***', #0抑制标签
'White-h1', #1白人
'Non-White', #2非白人
'White', #3白人
'Asian-Pac-Islander', #亚洲-太平洋-伊斯兰人
'Amer-Indian-Eskimo', #美洲-印第安人-爱斯基摩人
'Other', #其他
'Black' #黑人
]
#workclass的泛化树
vgh_race=pd.DataFrame({'value': race_attributeLabels,
'parent':[-1,0,0,1,2,2,2,2],
'height':[2,1,1,0,0,0,0,0]})
quasi_identifier_list.append(attributeLabels[8]) #将workclass设置为准标识符
quasi_identifier_DGH_list.append(2)
quasi_identifier_VGH_list.append(vgh_race)
quasi_identifier_height_list.append(0)
print (vgh_race)#marital-status属性标签
marital_attributeLabels=['***', #0抑制标签
'Married-h2', #1已婚
'Alone', #2独自一人
'Married-h1', #3已婚
'Single', #4单身
'Widowhood', #5鳏寡
'Married-civ-spouse', #已婚-公民-配偶
'Married-AF-spouse', #已婚-无房-配偶
'Separated', #分居
'Divorced', #离婚
'Never-married', #未婚
'Widowed', #寡居
'Married-spouse-absent' #已婚-配偶-不在
]
#marital-status的泛化树
vgh_marital=pd.DataFrame({'value': marital_attributeLabels,
'parent':[-1,0,0,1,2,2,3,3,3,4,4,5,5],
'height':[3,2,2,1,1,1,0,0,0,0,0,0,0]})
quasi_identifier_list.append(attributeLabels[5]) #将marital-status设置为准标识符
quasi_identifier_DGH_list.append(3)
quasi_identifier_VGH_list.append(vgh_marital)
quasi_identifier_height_list.append(0)
print(vgh_marital)如果还要增加其他准标识符的话，以类似的格式加上就可以了。但是数值型属性需要先分段，不能直接使用。
3.导入数据集与初步处理
这个数据集有2个要处理的地方，首先是缺失值表示为‘ ?’，需要转化为NAN以便处理，然后是字符串的前端会有一个空格，需要去除。
对于有缺失值的数据，由于个数不多，大概2000+条，所以直接删去。
#导入数据集
censusData_Set=pd.read_csv(censusData_FilePath,names=attributeLabels)
# 将缺失值部分的“ ？” 置为空，即 np.NaN，便于使用pandas来处理缺失值
censusData_Set = censusData_Set.replace(" ?", np.NaN)
#类型为字符串的标签
attributeLabels_str=["workclass","education", "marital_status","occupation",
"relationship","race","sex","native_country","wage_class"]
#删除数据值前的空格
for label in attributeLabels_str:
censusData_Set[label] = censusData_Set[label].str.strip()
#删除包含缺失值的行
censusData_Set.dropna(inplace=True)
#重置索引
censusData_Set.reset_index(drop=True, inplace=True)
4.检查数据集是否满足k匿名
将所有出现过的准标识符组合存入字典并计数，最后字典中个数最小的项如果数量大于等于k，显然就满足k匿名。
#检验是否满足k匿名
#将所有准标识符的组合存入字典，值为出现次数。
def group_data(testedSet):
quasiDict = {}
for item in testedSet.itertuples():
#--------------------------------------------------------------
#将准标识符转化为字符串
item_statement=''
for label in quasi_identifier_list:
item_statement=item_statement+getattr(item,label)+' '
#--------------------------------------------------------------
#如果该准标识符组合已经出现过了，则计数+1
if item_statement in quasiDict.keys():
quasiDict[item_statement] += 1
#如果该准标识符组合没有出现过，则新建记录
else:
quasiDict[item_statement]=1
#返回字典
return quasiDict
#判断数据集testedSet是否满足k匿名，是则返回true，否则返回false
def if_k(testedSet,k):
#对数据集进行分组，获得组合数量
ans_dict=group_data(testedSet)
#-----------------------------------------------------------------
#展示准标识符组合
print('')
print (ans_dict)
print('')
#-----------------------------------------------------------------
min_k=None
#遍历分组字典，取出最小的重复个数，赋值给min_k
for i in ans_dict:
if min_k is None or ans_dict[i]<min_k :
min_k=ans_dict[i];
#如果字典的最小k值大于等于给定的k值，则满足k匿名
if min_k>=k:
return True
else:
return False5.泛化
父母节点数组存储的泛化树容易得到节点的父母节点，因此泛化的代码比较容易。用节点的父母节点替换本节点即可。
#对数据集tempDataSet（dataframe）的属性列attr（String）进行泛化
#vgh（dataframe）是泛化树
def Generalization_attr(tempDataSet, attr, vgh, h):
for index,row in vgh.iterrows():
if row.height==h:
tempDataSet.replace({attr:row.value},vgh.loc[row.parent].value,inplace=True)
6.运行主函数
输入为：数据集censusData_Set；k匿名需要满足的k值k_Anonymity；
输出为：泛化后满足k匿名的数据集censusData_Set；精确度prec；
#演示取值：16000；2；15；140
k_Anonymity=15
#泛化次数计数，初始化为所有准标识符泛化次数之和
gen_count=0
for index in range(len(quasi_identifier_DGH_list)):
gen_count+=quasi_identifier_DGH_list[index]
while if_k(censusData_Set,k_Anonymity) is False:
for index in range(len(quasi_identifier_list)):
#如果已经到达了泛化顶点
if quasi_identifier_height_list[index]>=quasi_identifier_DGH_list[index]:
continue
#-----------------------------------------------------------------
#泛化
Generalization_attr(censusData_Set,
quasi_identifier_list[index],
quasi_identifier_VGH_list[index],
quasi_identifier_height_list[index])
#-----------------------------------------------------------------
#泛化次数-1
gen_count-=1
#泛化高度+1
quasi_identifier_height_list[index]+=1
if if_k(censusData_Set,k_Anonymity):
break
print ('当前泛化高度：')
for index in range(len(quasi_identifier_list)):
print(quasi_identifier_list[index]+':'+str(quasi_identifier_height_list[index]))
#直至无法泛化
if gen_count==0:
print('泛化失败')
break
print ('当前泛化高度：')
for index in range(len(quasi_identifier_list)):
print(quasi_identifier_list[index]+':'+str(quasi_identifier_height_list[index]))
print('当前k值为：')
print(k_Anonymity)
print ('精确度为：')
prec=0
for index in range(len(quasi_identifier_list)):
prec+=(quasi_identifier_height_list[index])/(quasi_identifier_DGH_list[index])
prec=1-(prec/len(quasi_identifier_list))
print (prec)文章出处登录后可见！
