开发者学堂课程【高校精品课-北京理工大学-大数据技术导论：大数据隐私保护（四）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/857/detail/15596
大数据隐私保护（四）
内容介绍：
一、蒙德里安算法
二、同质性攻击
三、I-多样性
一、蒙德里安算法
这一小节将要介绍蒙德里安算法。蒙德里安算法是一个按照顺序来处理所有属性，然后通过选择泛化的边界，不断划分元组，从而达到 K 匿名。在这里首先介绍K匿名的一个效用的指标。
第一个效应指标称之为可分辨。可分辨指的是组的大小的一个平方和。因为把数据进行的一个隐私保护之后，数据就会分成若干个组，每一组满足K匿名明规则的话，每一组必须等于一个元素。这样可以通过把每一组当中的元组的个数做一个平方和，把它加起来，这个平方和越大的话，就意味着划分是不均匀的。不均匀意味着它的一个可分辨的能力是比较差的。如果说划分是很均匀，那么，它的隐私的效果肯定是更好的。然后其次是规划的平均数的大小。这些指标它是等于所有元组的个数除以所有组的个数，然后再除以一个 K。根据这两个效应指标。
通常要优化这两个指标的话，这个问题它是 NP 难的。在这里将介绍的蒙德里安算法，它会是一个 nlogn 的算法，它是一个贪心的一个算法。而我们之前讲起来的基于我们自己向上的一个格搜索的一个算法，该算法是精确的，所以我们这里讲的蒙德里安算法，它是一个近似的一个算法。
他的近似保证可以得到常数因子的一个近似保证。具体的这个算法它是使用了一个类似于 kd 树构造的一个算法。他是假设 QI 元组是假设为一个低维空间中的一个点。然后选择通过一些边界可以设置成一些矩形状的边界，把这些节点进行一个划分。划分完了之后，就可以生成不同的组，然后用这些矩形的边界去进行一个泛化。怎么来生产这个矩形的边界？这里面就是采用了 kd 树算法的一个思想，每次通过选择一个属性，它的一个宗旨，然后进行划分，因为这样的话可以大概把这个数据分成相等的两半。
比如说左边这个表。首先可以采用性别属性进行划分，因为性别只有男和女，可以男的把它分成一组，女的分成一组，通过一个这样的划分。然后除此之外，
接下来可以按照生日进行划分，比如说有七六年的，也有八六年的，可以把七六年的就归为一组，八六年的归为一组，类似这么一个划分。那么这样的不断的进行，就可以得到一个矩形的边界，然后就可以用这个矩形的一个区域可以做一个泛化。
比如说假设有一个人，他的出生年份是七九年的，那么呢可能存在一个这样的区间，比如说七六到七九，那么这个七九年的人，就可以用这个区间来进行泛化，也就是说他的生日本来在原始的数据中是七九年，那么泛化后的数据就会变成一个区间，七六到七九，这样从而实现了一个隐私的保护，通过不断的这样的划分，每次泛化之后，来检查泛化后的那个分组，是否所有的分组都满足了这个K匿名的属性，如果都满足了，算法就结束了，因为得到的所有的分组都是 K 匿名的。如果没有满足，那么继续沿着这个属性，按照宗旨进行划分，直到结束为止。
二、同质性攻击
但是 K 匿名的技术仍然是存在缺陷，虽然可以保护一定程度上的隐私，但是容易受到同质性的攻击。什么叫同质性？因为 K 匿名技术并不关心敏感信息，比如说刚刚说的工资信息，他不关心，他只关心那个 QI，也就是那个准标志符，比如说刚刚提到的身热，邮编以及性别这三个，对我们的敏感信息，工资它是没有任何修改的，这样的话会存在一个问题，
假设得到的那个分组，分组里面的所有记录，他的工资信息是一样的。这样的话会有什么问题？如果定位到了这个分组，就可以知道，这个分组里面所有人的工资都是一样的，其实就失去了隐私。因为我只要知道你这个人属于这个分组，就知道你的工资是多少。所以这是他的一个缺陷，造成这个的缺陷的原因，其实并不是数据本身，而是在于分组的一个选择。
因为对于一些参数，它其实并不丢失隐私信息。但是有些分组会使得隐私被侵犯，比如说看左边这张表。可以看到把左边这张表通过K匿名，可以得到一个二匿名的表在右边，那右边这张表可以发现，比如说黄色的这两条记录，他的工资信息都是55000。然后这两条信息其实是一样的，所以这样的话，我们只需要定位到一个用户，他是属于自己组当中，就知道他的工资信息了。所以这是一个比较差的一个情况。当然如果采用另外一种划分方式，比如说现在右边这个表，会发现他的任何一个组当中，那个敏感的信息，他的那个工资信息，它是不一样的，所以这样的话，这个效果是比刚刚那个K匿名的效果是好的。所以说会发现，如果这个敏感信息，缺乏多样性的话，就会导致K匿名算法其实就会失去隐私保护的效果。
比如刚刚举的例子。通过这样的K匿名，我们发现这个76年1月21日出生的这个人，其实他的工资信息是可以被鉴别出来的。
三、I-多样性
为了解决这些问题，有很多学者就提出了一种称之为 L 多样性的一个隐私方法。L 多样性指的是什么？
如果每个 QI 组当中包含了至少一个良好表示的敏感值。就称之为该表是多样的。这里面的良好表示是定义的一个核心。这里面有熵I多样性。它的一个定义是指对每一个 QI 组 g，它的一个计算，它的一个熵，它的熵如果大于L，就称之为它是一个熵I多样性的一个组。这里面熵是通过下面这个公式来计算的，它是信息论里头的一个概念，我们知道如果一个元组中的熵。熵值越大的话，证明这个数据越均匀越随机。
如果你这个熵值越小，那么证明这个数据越确定，而隐私保护的目的就是希望这个数据越不确定越好，越均匀，越随机越好，所以就使得用户就无法猜测，如果这个数据是确定性的，那就失去了隐私了。
所以希望这个熵值它是大于 logL 的，满足这样的条件称之为它是满足熵 I 多样性。除了这些定义，也有另外一个定义，称之为递归 CL 多样性。它是对于每个具有 M 个敏感词的 QI 组 g。ri 为出现次数第i高的敏感值的频次。会有出现频次最高的。必须要 r1小于 C 乘以 R L 加到 M。也就是说出现最不平凡的那个 M 减 L 加一个。乘以C 必须要大于那个出现最频繁的。
这样其实就是保证了一定的均匀性，也就是说使得一个组里头不能说有一些元素出现的非常频繁。要大家出现的频次都差不多。这个就是 L 多样性的一个原理，也就是使得这个分组里头多样性要更强。而我们可以发现，与 QI中较不频繁的敏感值相比。最常见的敏感值不会显得太过于频繁了，
比如说我们来看基于熵I多样性的一个例子。假设我们的每个 QI 组 g，我们可以计算一下它的一个熵。可以发现两条蓝色的部分它的熵等于多少，我们可以计算一下，通过刚才那个公式，发现他的工资值都是5万，其实是不具备多样性的。通过计算呢它的熵值等于零的，因为它其实是确定性的。也不管你，只要我定位到你这条记录属于这个组，我就可以识别你的工资就等于5万。所以可以发现L多样性的在一定程度上是可以解决K匿名的一个缺陷的。那么如何来计算 L 多样性？这里面其实有个非常关键的性质。跟K匿名类似，L 多样性也满足子集属性和方法属性这两个性质。这里面可以简单证明一下，比如说熵I 多样性，为什么熵满足？
其实最主要的原因就是熵是一个凹函数。因为他这个凹函数可以代入进去计算一下就可以，就可以知道他是满足这个子集的一个性质的。那么有了这个性质其实就可以采用K匿名的算法来计算这个L多样性，我们可以首先采用一个K匿名算法。
计算过程中可以通过对这个分组，进行一个 L 多样性的一个测试，如果满足L多样性，算法就停止，结果就是一个L多样性的隐私。保护的一个方法。然后这里面怎么进行一个多样性测试？我们其实可以计算 QI 组中的敏感值的一个计算，就是我们可以计算它的熵的话，来判断这个熵是否大于 L，如果大于 L 的话，那么就可以停止了，这样不断的进行。可以采用类似于刚刚说的一个蒙德里安算法，也可以采用刚刚那个自底向上的格搜索算法，这个算法都可以用类似的方法来计算我们的 L 多样性。但是 L 多样性也有它的一个缺点，他虽然能够保证每一个分组里面的多样性，但是无法保证这个分组之间那个敏感词之间的差距。
比如说一个人的工资是5万，那么一个人的工资是50001块，这其实差距不大的，但是 L 多样性认为它是不同的。其实他有些敏感词，他虽然不相同，但是在语义上是一样的，对于那个攻击者来说，5万跟50001是没有任何区别的。
所以这样的话，L 多样性其实在这个程度上讲，他也是无法保护我们的这一类的隐私。所以为此有些学者提出来了一个叫T相近的一个方法。T相近指的是在每个 QI 组中，如果祖宗的敏感值分布于整个表中的敏感词分布之间的距离不超过阈值t，则称该表为T相近的表。这个就是说每一个分组当中，这些记录之间的敏感值它是一个分布的。他说他的分布跟在原始整个数据当中，他敏感值的分布差距不大。也就差距要小于等于那个阈值，这样的话意味着它其实就反映了整个原始原始数据的一个分布，所以在一定程度上是要比L多样性是要更好的。
然后接下来来介绍一下，当我们处理完了，得到K匿名的表以后，怎么来做我们后面的数据分析，也就是我们这里所谓的方法表的一个泛化处理，因为我们知道泛化如果发的不好的话，会丢失很多信息，导致我们的后面的统计分析等等这些后续的操作都不精确，这里可能会得到一些不准确的具体分析，比如说来看这些例子。
比如说左边这个表格。通过泛化以后可以得到右边那个表格，它是满足三匿名的。因为分成两组，每组都有三个元素，这三个元素它的准身份标识符是一样的。假设我们要查询1976年有多少人出生。这时候会发现，通过这个泛化表，我们可以查出来，有六条记录都满足七六年，因为是七六到八六的一个区间。
所以这样的话，我们可能只知道一个范围是一到六，当我们实际中这个真实的数据是四。其实可以得到你得到的结果并不准确，我们或许可以猜一或者二等等。我们再来看一个例子，1976年出生的人的平均工资是多少？
通过这个泛化表其实也可以得到一个范围，我们这里是叫50K 到75K 之间。所以其实只能得到一个大概。所以，我们其实只能得到一个大概。
总结：
在本次课中，我们首先介绍了 K 匿名的一个算法以及概念，以及介绍了他的一个局限性，也就是他易受同质性攻击，同质性攻击就是指他的分组当中，如果他的敏感值是一样的话，就失去了隐私保护的效果。为了解决这些问题？有学者提出了一种称之为 L 多样性的算法。L 多样性可以克服同质性攻击的缺点，但是也容易受到我们称之为相似性攻击。
也就是说他虽然敏感值，它满足 L 多样性，就他的敏感值在某一个分组当中，他是有多样性的，但是它的差距不大，差相差不大的数据，虽然说他们并不一样，但是，它相差不大，语义上是相似的，所以这样的话对于攻击者来说是没有意义的，所以同样也可以也会失去隐私。t 相近的概念就解决了上面这两种的缺陷，它是通过一个概率分布的方法，它使得了 K 匿名分组后的数据，必须数据的分布和原数据相差不大，这样，原始的数据的分布基本上就能够在这个分组后的数据在分布上反映出来，这样的话他的隐私的信息就可以得到很大程度的一个保护。
