实现K-匿名Topdown Greedy算法
这是大数据安全与隐私学校课程的实验之一，实现k-匿名。
--
0、背景
代码是从下面仓库找到的：
k-匿名最先由这篇论文提出：[Samarati, Pierangela, and Latanya Sweeney. "Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression." (1998).]
里面就有一种实现的算法。随后还有好多种算法。我这里实现的是Topdown Greedy，因为做作业的时候最简单。
Topdown Greedy算法来自这篇论文:[J. Xu, W. Wang, J. Pei, X. Wang, B. Shi, A. W.-C. Fu. Utility-based anonymization using local recoding. Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2006, 785-790]
其中，NCP用于度量每次泛化操作带来的不准确性：[Xu, Jian, et al. "Utility-based anonymization for privacy preservation with less information loss." ACM Sigkdd Explorations Newsletter 8.2 (2006): 21-30].
1、实现
1.数据输入
输入的数据中需要有一个hierarchy文件夹，里面包含预先定义好的各个QI的泛化层次。
比如adult，需要为其中每一个准标识符预先定义好泛化层次比如adult，需要为其中每一个准标识符预先定义好泛化层次。
2.数据结构：GenTree，NumRange和Partition
代码中定义了一个名为GenTree的类，存储了树节点的相关信息，用于表示泛化层次结构中的逻辑树。类中的属性包括：
-
value：节点的值。
-
level：树的层级（从顶部开始，顶部为0）。
-
leaf_num：当前节点覆盖的叶节点数目。
-
parent：祖先节点列表。
-
child：直接后继节点列表。
-
cover：当前节点覆盖的所有节点。
-
isleaf：表示当前节点是否为叶节点。
-
leaf_list：当前节点所覆盖的叶节点值列表。
在构造函数中，对各个属性进行初始化，包括赋值、添加父子节点关系、更新层级和覆盖关系等。
1def __init__(self, value=None, parent=None, isleaf=False):
2 self.value = ''
3 self.level = 0
4 self.leaf_num = 0
5 self.parent = []
6 self.child = []
7 self.cover = {}
8 self.isleaf = isleaf
9 self.leaf_list = []
10 if value is not None:
11 self.value = value
12 self.cover[value] = self
13 if parent is not None:
14 self.parent = parent.parent[:]
15 self.parent.insert(0, parent)
16 parent.child.append(self)
17 self.level = parent.level + 1
18 for t in self.parent:
19 t.cover[self.value] = self
20 if isleaf:
21 t.leaf_num += 1
22 t.leaf_list.append(self.value)
另外类中包含node(self, value)方法，用于搜索具有特定值的节点，并返回对应的GenTree节点，若节点不存在则返回None。__len__(self)方法返回当前节点覆盖的叶节点数目。get_leaves_names(self) 方法返回当前节点所覆盖的叶节点值列表。
NumRange类用于表示数值类型的范围。sort_value：排序后的值列表，可以用于计算标准化宽度。value：节点的值，例如10,20。support：所有值的支持度（频率），以字典形式存储。range：最大值和最小值之差，用于计算标准化宽度。cover：当前节点的叶节点。在构造函数中，根据传入的值列表和支持度进行初始化，包括计算最大值和最小值之差、构建值和索引的字典等。另外还有__len__(self) 方法，返回节点的范围（即最大值和最小值之差）的绝对值。
1def __init__(self, sort_value, support):
2 self.sort_value = list(sort_value)
3 self.support = support.copy()
4 # sometimes the values may be str
5 self.range = float(sort_value[-1]) - float(sort_value[0])
6 self.dict = {}
7 for i, v in enumerate(sort_value):
8 self.dict[v] = i
9 self.value = sort_value[0] + ',' + sort_value[-1]
Partition类用于记录一个分组。其中，member：一个列表，保存着该分组中的记录。middle：保存该分组的泛化结果。构造函数几首两个参数，data是一个列表，是该分组中的记录，midlle也是一个列表，保存泛化结果。
1def __init__(self, data, middle):
2 """
3 initialize with data and middle
4 """
5 self.can_split = True
6 self.member = data[:]
7 self.middle = middle[:]
3.算法
以下从主要算法分枝出去按照“树型结构”介绍，主要算法如下：
1def Top_Down_Greedy_Anonymization(att_trees, data, k, QI_num, SA_num):
2 """
3 Top Down Greedy Anonymization is a heuristic algorithm
4 for relational dataset with numeric and categorical attbitues
5 """
6 init(att_trees, data, k, QI_num, SA_num)
7 result = []
8 middle = []
9 for i in tqdm(range(QI_LEN)):
10 if IS_CAT[i] is False:
11 QI_RANGE.append(ATT_TREES[i].range)
12 middle.append(ATT_TREES[i].value)
13 else:
14 QI_RANGE.append(len(ATT_TREES[i]['*']))
15 middle.append('*')
16 whole_partition = Partition(data, middle)
17 start_time = time.time()
18 anonymize(whole_partition)
19 rtime = float(time.time() - start_time)
20 dp = 0.0
21 for sub_partition in tqdm(RESULT):
22 gen_result = sub_partition.middle
23
24 for i in range(len(sub_partition)):
25 temp_for_SA = []
26 for s in range(len(sub_partition.member[i]) - len(SA_INDEX), len(sub_partition.member[i])):
27 temp_for_SA = temp_for_SA + [sub_partition.member[i][s]]
28 result.append(gen_result[:] + temp_for_SA)
29 dp += len(sub_partition) ** 2
30
31 return (result, rtime)
1. 其中init用于重置一些全局变量的值，包括 GL_K、RESULT、QI_LEN、ATT_TREES、QI_RANGE、IS_CAT 和 SA_INDEX。函数中将传入的 att_trees 赋值给全局变量 ATT_TREES。对于 att_trees 中的每个元素 t，判断其是否是 NumRange 类型的实例，若是则将 False 添加到 IS_CAT 中，否则将 True 添加到 IS_CAT 中。该步骤根据属性类型判断是否为分类属性。然后将传入的 QI_num 赋值给全局变量 QI_LEN。再然后将传入的 SA_num 赋值给全局变量 SA_INDEX。最后将传入的 k 赋值给全局变量 GL_K，将全局变量 RESULT、QI_RANGE 清空。
1def init(att_trees, data, k, QI_num, SA_num):
2 """
3 reset all gloabl variables
4 """
5 global GL_K, RESULT, QI_LEN, ATT_TREES, QI_RANGE, IS_CAT, SA_INDEX
6 ATT_TREES = att_trees
7 for t in att_trees:
8 if isinstance(t, NumRange):
9 IS_CAT.append(False)
10 else:
11 IS_CAT.append(True)
12 QI_LEN = QI_num
13 SA_INDEX = SA_num
14 GL_K = k
15 RESULT = []
16 QI_RANGE = []
2. result用于存储最终结果的列表。
3. middle用于存储属性泛化的中间值。
4. 然后迭代每个属性集合，对于每个属性：
-
判断是否为分类属性，如果不是，就将属性的范围(ATT_TREE[i].range)添加到QI_RANGE中，并将属性的值添加到middle
-
否则，就将分类属性的范围长度(len(ATT_TREE[i][ ''])添加到QI_RANGE中，并将’’添加到middle中
5. 创建一个whole_partition对象，该对象是一个包含所有数和middle的分区，调用anonymize(whole_partition)进行匿名化处理。其中anonymize递归地将分组进行分组，直到不满足某个条件为止，代码如下：
1def anonymize(partition):
2 """
3 Main procedure of top_down_greedy_anonymization.
4 recursively partition groups until not allowable.
5 """
6 if can_split(partition) is False:
7 RESULT.append(partition)
8 return
9 u, v = get_pair(partition)
10 sub_partitions = distribute_record(u, v, partition)
11 if len(sub_partitions[0]) < GL_K:
12 balance(sub_partitions, 0)
13 elif len(sub_partitions[1]) < GL_K:
14 balance(sub_partitions, 1)
15 # watch dog
16 p_sum = len(partition)
17 c_sum = 0
18 for sub_partition in sub_partitions:
19 c_sum += len(sub_partition)
20 if p_sum != c_sum:
21 pdb.set_trace()
22 for sub_partition in sub_partitions:
23 anonymize(sub_partition)
5.1 - 由can_split(partition)判断是否能对分组进行分割，无法对分组进行分割，则将分组添加到结果RESULT中，并返回
5.2 - 使用get_pair函数获取一个分组中最大距离对，代码如下:
1def get_pair(partition):
2 """
3 To get max distance pair in partition, we need O(n^2) running time.
4 The author proposed a heuristic method: random pick u and get max_dis(u, v)
5 with O(n) running tiem; then pick max(v, u2)...after run ROUNDS times.
6 the dis(u, v) is nearly max.
7 """
8 len_partition = len(partition)
9 for i in range(ROUNDS):
10 if i == 0:
11 u = random.randrange(len_partition)
12 else:
13 u = v
14 max_dis = -1
15 max_index = 0
16 for i in range(len_partition):
17 if i != u:
18 rncp, _ = NCP_dis(partition.member[i], partition.member[u])
19 if rncp > max_dis:
20 max_dis = rncp
21 max_index = i
22 v = max_index
23 return (u, v)
-
首先计算分组的长度，接着计算若干轮迭代，由全局变量ROUNDS控制
-
在第一轮迭代中，随机选择一个索引u，对于之后的每一轮迭代，将u的值设置为上一轮迭代中得到的v的值
-
max_dis用于存储当前最大的距离值，初始化为-1.
-
遍历分区中每一个索引i。如果i不等于u，则计算partition.member[i]和partition.member[u]之间距离，距离的计算使用NCP_dis(record1, record2) 函数使用将 record1 和 record2 泛化后的记录的 Certainty Penalty 作为它们之间的距离。如果计算的距离大于max_dis就更新
-
最后返回这个最大距离对元组(u,v)
6. 然后使用distribute_record(u, v, partition)将分组进行分配，得到子分组列表sub_partition。distribute_record代码如下：
1def distribute_record(u, v, partition):
2 """
3 Distribute records based on NCP distance.
4 records will be assigned to nearer group.
5 """
6 record_u = partition.member[u][:]
7 record_v = partition.member[v][:]
8 u_partition = [record_u]
9 v_partition = [record_v]
10 remain_records = [item for index, item in enumerate(partition.member) if index not in set([u, v])]
11 for record in remain_records:
12 u_dis, _ = NCP_dis(record_u, record)
13 v_dis, _ = NCP_dis(record_v, record)
14 if u_dis > v_dis:
15 v_partition.append(record)
16 else:
17 u_partition.append(record)
18 return [Partition(u_partition, middle_group(u_partition)),
19 Partition(v_partition, middle_group(v_partition))]
-
首先，通过 partition.member[u][:] 和 partition.member[v][:] 分别获取记录 u 和记录 v。然后，初始化 u_partition 和 v_partition 列表，分别将 record_u 和 record_v 加入到对应的列表中。
-
再对remain_records列表中的每个记录，分别计算record_u与record的距离和record_v与record的距离，再比较二者的结果，并根据比较结果，将record加入u_partition列表或者v_partition列表中，最后将u_partition和v_partition分别作为参数创建两个新的分组Partition对象，并作为列表返回。
7. 如果sub_partition中第一个子分组的长度小于全局的k GL_K，则使用balance(sub_partition, 0)进行平衡处理；否则，如果sub_partition第二个子分组的长度小于GL_K，则使用balance(sub_partition, 1)进行平衡处理：
1def balance(sub_partitions, index):
2 less = sub_partitions.pop(index)
3 more = sub_partitions.pop()
4 all_length = len(less) + len(more)
5 require = GL_K - len(less)
6 # First method
7 dist = {}
8 for i, record in enumerate(more.member):
9 dist[i], _ = NCP_dis(less.middle, record)
10
11 sorted_dist = sorted(dist.items(),
12 key=operator.itemgetter(1))
13 nearest_index = [t[0] for t in sorted_dist[:require]]
14 addition_set = [t for i, t in enumerate(more.member) if i in set(nearest_index)]
15 remain_set = [t for i, t in enumerate(more.member) if i not in set(nearest_index)]
16 first_ncp, first_mid = NCP_dis_merge(less, addition_set)
17 r_middle = middle_group(remain_set)
18 first_ncp += len(remain_set) * NCP(r_middle)
19 # Second method
20 second_ncp, second_mid = NCP_dis(less.middle, more.middle)
21 second_ncp *= all_length
22 if first_ncp <= second_ncp:
23 less.member.extend(addition_set)
24 less.middle = first_mid
25 more.member = remain_set
26 more.middle = r_middle
27 sub_partitions.append(more)
28 else:
29 less.member.extend(more.member)
30 less.middle = second_mid
31 less.can_split = False
32 sub_partitions.append(less)
7.1 其中index是需要进行平衡处理的子分组的索引，首先从sub_partitions中取出记录数量小于k的子分组，并将其存储在less中，同时取出记录多的放在more中
7.2 计算总记录数和需要补充的记录数
7.3 有两种平衡方法，首先尝试第一种平衡方法，创建一个空字典dist，用于存储more子分组中每条记录与less子分组的NCP距离，再对这个距离字典进行排序，选取距离最小的若干条记录，这个数量为require，将选取的记录添加到less.member中，并使用NCP_dis_merge来讲addition_set合并到less中，这个NCP_dis_merge的代码如下：
1def NCP_dis_merge(partition, addition_set):
2 mid = middle_group(addition_set)
3 mid = middle_record(mid, partition.middle)
4 return (len(addition_set) + len(partition)) * NCP(mid), mid
- 首先，使用 middle_group(addition_set) 计算 addition_set 的泛化结果，将结果赋给 mid。然后，使用 middle_record(mid, partition.middle) 将 mid 与当前分组的泛化结果 partition.middle 进行合并，将结果再次赋给 mid。最后，将结果（NCP值，泛化结果）作为元组返回。
7.4 对于剩余的记录，计算其r_middle和NCP值，并累加进去。
7.5 第二种平衡方法，计算less分组泛化值与more的之间的NCP距离
7.6 然后比较第一种方法与第二种方法得到的NCP值，选择较小的那种方法进行操作。
7.7 操作完最后，将更新后的less子分组添加回sub_partition列表中。
- 最后接着对于每个子分组，继续递归调用anonymize(sub_partition)进行进一步分组。
4.总结
运行起来还是很爽的。运行前：
运行中：
运行后：
就k匿名好了。
写得像shi一样，可能一个星期后看都看不懂了，anyway.....