开发者学堂课程【高校精品课-北京理工大学-大数据技术导论：大数据隐私保护（三）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/857/detail/15595
大数据隐私保护（三）
内容介绍：
一、K-匿名
二、K-匿名和不确定性
三、计算 K-匿名
一、K-匿名：
这一小节将讲解 K 匿名算法，K 匿名命名规则指的是当且仅当每个元组在一个多集 T 中至少出现了 K 次。
则称该表 T 满足关于准标识符 QI 的 K 匿名。K 匿名的目的就是为了防止刚刚所提到的链接攻击。
从上一节讲解的内容会发现，单从一些简单的匿名技术是很难实现防止链接的攻击的。
刚刚看到通过泛化或者说抑制都只能实现一部分的隐私保护，仍然可能可以鉴别出一个或者几个用户的一些具体的信息。
今天介绍的 K 匿名技术在一定程度上可以缓解这些问题。K 匿名是如果T'是 T 的一个泛化或者抑制，并且 T'满足K匿名规则，那么我们称T'就是 T 的一个 K 匿名。
我们来看右边这一张表，通过刚刚的一个抑制以及方法的一个泛化操作，发现右边这张表它的任意的一种元素可以分成三种，任意一种元素都包含了至少两个元素。
二、K-匿名和不确定性
这样我们就可以看出，任何一组元组当中，他至少大于两个，右边这张表是满足二匿名。根据我们的一个直观经验，一个可以匿名的表 T'，它代表了所有的可能表Ti的一个集合，使得 T'是 Ti 的一个 K 匿名，也就是说 K 匿名的表，他其实代表了很多可能的表，因为我们K匿名表当中有些原主信息，有些属性信息等等，他们是泛化和抑制就变成一个星号，这样画星号的取值可以是有多种多样的，所以他其实代表了很多种可能的表。并且我们知道最初推导T'的表T是所有可能表中的一个，就是K匿名的表是由一个具体的表推导出来的。通过泛化抑制的一些操作，可以推导出我们的目标，我们会发现K匿名表由它推导出来那张原始的表，他是K匿名表中的一个可能的表。
我们来看这个例子，左边这一张是一个 K 匿名表，这里 K 匿名就等于二，右边这张是它原始的表，刚刚就是通过右边这张表推导出了左边这个 K 匿名表，发现右边这张表其实是科 K 匿名表的一个实例，也就是说它是一个可能的表。
并且这种可能的表他可能有很多，因为刚刚提到，我们的 K 匿名表有很多星号的部分，这些星号的地方都可以取不同的值，这样的话，它其实可以实例化很多张表出来。比如说右边这张表其实就是左边这个 K 匿名表的一个可能表。右边这张表跟我们之前原始的那张表是不一样的。所以会发现如果没有背景知识的话，所有可能的表其实是等概率的，这样其实就达到了一定的隐私保护的效果，因为你无法推测出到底是哪一张具体的表，从而你就无法推测用户的具体信息。假设我们有了一张K匿名表，希望从这张统计表当中得到一些统计的信息，所以会有一些查询的应答，我们需要去查询这张匿名表，从而得到我们想要的统计信息。通常需要这个查询的范围应该要覆盖所有可能的表。比如说要查询某人76年1月21日出生的男性，并且邮编是53715的，要查询这个人的工资是多少。这个时候我们可以通过查询这张K匿名表，从而得到工资的一个范围。这里可以通过一个范围可以推测出他的工资大概是57500。此外再看另外一个例子，比如说53706这名女性的，想查询这名女性的最高工资，因为知道K匿名表其实是没有53706的，我们是537**，这个时候如何来查询他的一个最高工资，我们只有通过一个猜测。因为可以看到537**这么一个记录啊.，所有的这些记录当中，他有一个工资的一个范围，我们可以使用这个范围当中的最高的工资，可以作为一个估计，作为53706这名女性的最高工资，有了K匿名这个规则，如何来计算可以匿名的表。在文件中有大量的算法用于计算肯定表，其中包括通过泛化以及抑制技术等，以及通过全局和局部记录了，这里的全局包括我们所说的像全域的一个概念，局部，比如说我们的一个多维度的一个概念。
三、计算 K-匿名
还有基于层次与基于划分的区域划分，主要是针对我们的数值的数据。首先我们来看第一类算法，第一类算法是一个精确的，它能够算出所有的K匿名的一个方法，这里面比较有代表性的是最后一个算法，它是一个字体向上的一个计算的一个方法，类似于我们数据挖掘当中的关联规则的一个挖掘算法。
但是我们会发现所有这些精确的算法都需要指数时间的复杂度。所以在实际中只能在小数据当中进行运行。
除此之外还有一类叫启发式的算法。这类启发式算法的特点它是复杂度是不确定性，但是往往在实际中也能得到一定的比较好的一个效果，这个算法比较有代表性的是零五年的一篇一篇论文，他提出来的一个启发式的自顶向下的一个计算方法。该方法是一种基于全局的以及全域的一个基于划分的一个算法。
此外还有一类是一个近似方法，之前我们讲到的第一类是精确的，第二类是启发式的，还有第三类是一个近似的一个算法。这类算法通常运行时间比较快，复杂度比较低，但是可以得到一个有理论保证的，有近似比保证的一个效果。
这里比较知名的是最后一个算法，它可以得到一个常数因子的近似，在大数据当中是可以使用的。
接下来来介绍第一类算法中的一个比较有代表性的隐名算法，该算法可以计算出所有所有的极小权益方法，该算法是利用了数据立方体的一个思想，以及关联规则的一个思想。什么叫极小的全域泛化？我们知道如果把所有的属性进行方法，肯定是可以得到一个比较好的一个隐私的效果，但是会导致数据变的有用性不高，数据的价值不高。因为如果把很多值变了很多*的话，数据就失去了它的意义，所以呢很多时候需要找到最小或者称之为极小的这么一个概念，比如说想希望通过泛化非常少的一个几个属性，就能够实现K匿名。这样的话称之为叫极小全泛化法。那么这个极小全域泛化能够高效计算的一个原因是什么？
主要是 K 匿名有两个非常好的性质，第一个性质称之为子集属性。子集属性指的是如果表 T 是关于一组属性 Q的K匿名，那么 T 也是关于 Q 的任何子属性的K匿名。也就是如果一个表是关于一个大一点集合的一个 K 匿名，那么这张表同样也是关于这个大的集合当中的任何子集的一个K匿名。举个比较简单的例子，假设我们有一张表，它是三个属性的K匿名，比如说三个属性是我们生日邮编性别，那么这张表肯定也是生日和性别这两个属性的一个K匿名。这是为什么呢？因为既然是三个属性的K匿名的，证明这张表他这个任何的三个属性在一起的话，他都至少会存在K个相同的元素。所以如果去掉其中几个属性，这条性质是仍然成立的，这样就意味着它是满足这么一个子集属性的。
除此之外，他还满足一个泛化属性。泛化属性指的是，如果表T2是表 T1的泛法，且 T1是 K 匿名，那么 T2也是K匿名。相当于是我们假设一张表 T1，他已经是一个满足的K匿名，我们如果再把 T1这张表再匿名一下，就相当于是在把里头的一些数据再模糊化一些，这样可以得到另外一张，另外一张表肯定也是满足 K 匿名的，因为它的数据的值比之前的更泛化了，所以更加不可能能够推导出它的精确的信息出来。正是因为有这两个属性，可以在计算这个K匿名的时候，可以通过一个自顶向上的方式，先计算子属性的一个肯定，如果直属性满足的肯定，那么就没有必要再去计算一个更大的那个属性的 K 匿名。这些性质除了对 K 匿名有效以外，他还对其他的更强的隐私概念也是非常有效的，比如说我们后面会讲到的 L 多样性以及T相近。
再来看任何的一个全域泛法，其实可以用一个域向量来表示。比如说刚刚提到的那个例子。B0假设等于我们这些生日，刚刚那张表格是有三个生日的。然后这三个生日其实我们可以泛化一下，我们可以只考虑它的年份，泛化到七六年到八六年的一个区间，然后性别可以泛化成一个不确定的*。以及我们的邮编可以泛化成5371*，5370*，这是第一层 Z1泛法，也可以再进一步泛化更模糊一点，Z2就变成了537**，显然可以看出 Z1比 Z2更模糊一些。可以看到左边这个例子，通过 B0 S1和 Z2方法之后可以得到右边这张表。我们举个例子，看第一行记录。
第一行记录中可以发现采用 B0方法的话呢，我们是不改变它的深入的信息的。采用 Z2方法的时候是把他的性别信息进行了一个抑制，变成一个*。采用这样的方法把他的邮编信息统一变成了537*，同样道理，如果采用 B1S0 Z2的方法？
又可以得到右边一张新的表。这张表可以发现通过这个方法B1S0Z2，可以得到一个三匿名。
大家可以看到蓝色部分和黄色部分，它这三个可以分成两组，六个数据可以分成两组，每组数据的准标识符是一样的，并且个数是有三个，所以是满足三匿名，回过头来看看之前那个 B0S1Z2泛化，发现这里面其实是分成了三组，三组中的每一组是包含了两个元素，包含了两条记录，其实满足二匿名，发 现 B0S1Z2泛化是没有 DS02泛法那么强，因为 B0S1Z2可以得到一个三匿名，之前那个是二匿名。所以通过这个例子其实可以发现所有的泛法规则其实可以得到一个这样的格的结构，我们称之为域向量格。格是理想数学里面的一个概念，它其实就是一个偏序集的一个关系。在刚刚那个例子中，其实可以发现，比如说我们这里的。
B1S1Z0，这个泛法是可以得到一个K匿名的，刚刚看到的 B1S0Z2，它是得到了3匿名，还有 B0S0Z2是得到了一个案例，如果条件是二匿名的话，这几个都是可以满足要求的，并且是没有必要在网上层在走，比如说在网上是 B1S1Z2，因为在网上传肯定也是满足K匿名的，根据刚刚的那个 K 匿名属性，知道它是满足子集属性和泛化属性的。所以其实是没有必要再进一步泛法就可以满足K匿名。所以这样的 B1S0Z2，或者说 B0S0Z2，我们称之为叫极小的，因为没有必要再往上走，所以到到此刚好满足了K匿名，那么这个状态我们称之为极小。所以这里再回顾一下刚刚两个属性，一个是子集，一个泛化，有了这两个属性，计算的时候通过一个自顶向上的方式，先把单个属性的泛法，然后计算一下，看看是否满足K匿名，如果满足，就停止了，因为当前状态就是极小，如果不满足，那么沿着这个格进行搜索。然后直到当前满足了，就可以停止了。所有的极小全域泛化，在集合形成一个叫反链的结构，反链指的是偏序集中的任意两个元素不可比较的。也就是说任意的两个极小全域泛化是不能比较的，也就是说不存在一个比另外一个更模糊，更泛化，就泛化程度更高，就不存在这样的关系，就是说不可比较。并且可以使用任何一个效用的指标，或者说一个度量，然后来个度量极小全域泛化，看看哪个到底是最优的。
比如我们可以通过一些属性的加权等等一些方式来计算一个分数，通过这个分数来对我们的全部极小全域泛化进行一个排序的话，就可以其实就可以找到一个最优的极小全域泛化。由于我们的极小全域泛化它并不是唯一的，可能有很多种，甚至100上千种，这样的话，其实可以通过定义一个效用指标，或者说称之为效用度量，来衡量极小全域泛化的一个有效性。
同样，可以得到一个分数，对所有的极小全域泛化进行一个排序，从而可以得到一个最优的极小全域泛化。
在本小节当中我们介绍了几种K匿名的一个实现的一种算法，以及相关的技术概念，以及K匿名的两种属性，子集属性和泛化属性，有了这两种属性就可以进行快速的K匿名计算。
