去匿名化

出自 MBA智库百科(https://wiki.mbalib.com/)

去匿名化（De-anonymization）

　　去匿名化是指一种数据挖掘策略，其中的匿名数据和其它数据来源相互对照来重新识别匿名的数据来源。区别一个数据来源和另一个数据来源的任一信息都能用于去匿名化。

　　Netflix在2006年为改善电影推荐服务，公布了部分用户评分的数据集，其中包括用户对电影的打分和打分日期。可以将数据集看成一个矩阵的形式，每一列都代表一部电影，每一行代表一个用户对电影的打分情况。数据集中包含约500000个用户，每个用户看过的电影以及评分都不尽相同，打分的电影相似程度都很低，因此，又可以把这个数据集看作稀疏矩阵。

　　因为电影的数量很多，数据集维度太高，并不存在准标识符，K匿名化在这个数据集上并不适用。在这个数据集中，假定攻击者知道一个人看过的几部电影，希望可以找到他看过的所有电影记录，即识别出这个人，而我们也希望知道最少需要知道几部电影就可以有较高的正确率。

　　攻击者首先通过计算自己的信息和数据集中每一个用户信息的相似度，然后选择相似度最高的作为结果。相似度的计算其实是通过分别比较每一部电影的相似程度而得出，如果攻击者想识别的用户和数据集中的一位用户对同一部电影的评分和日期相差在一定的范围内，比如日期相差不到14天，评分相等，则认为两者相似。为使算法更加健壮，规定相似度最大的值必须远高于相似度第二大的值，这样不但更好区分候选的用户，也能更好地判断攻击者知道的用户是否在数据集中。另外可以区分电影的冷热程度，如果一部电影看的人很多，则这部电影对相似度的权重就会小一点，反之冷门电影对相似度起到的作用会大一些。

　　最后的实验结果表明，通过8部电影的评分，和误差允许14天的评分日期，就可以唯一标识数据集中99%的用户;通过2部电影，68%的用户可以被标识出来。即仅通过2到8部电影，就可以识别出这个用户。而一个人8部的电影记录很容易获得，通过与其聊天或者查看博客就有可能得到。

　　社会网络在近几年非常流行，其中的数据也是另一类被研究很多的数据。与矩阵不同，它首先包括一个有向图或者无向图，图中节点表示网络中的实体，边表示实体间的关系，图的点和边也会有不同的属性。社会网络的数据除了组织机构公开在网上的，还可以通过社交网站提供的应用程序接口(API)自己进行爬取。匿名化的方法主要有随机的删除边和增加边，还有对点和边的属性进行K匿名化等。

　　社会网络的去匿名化主要针对的是节点的去匿名化，识别一个节点就是获得一个人的真实信息。对于社会网络的去匿名化方法可以分为两类，一类是基于映射的方法，另一类是基于猜测的方法。基于映射的方法是将攻击者了解的或爬取得到的真实网络结构与公开的经过匿名化的网络结构数据做节点匹配。基于猜测的方法则是利用攻击者已知的背景知识在公开数据中找到符合的一个或多个节点。

　　在映射的方法中攻击者假定了解少量用户的详细信息，而且通过爬虫等方法也得到了网络中大量的用户和关系，最终希望能把公开网络中与自己获取的网络中节点一一对应起来。根据攻击者的方式可以将其分为主动攻击和被动攻击，主动攻击的方法是在数据发布之前攻击者就创建一定数量的账号并使他们各自成为好友关系，这样形成一种很容易分辨出来的形式，在数据匿名发布后，首先找到这些点的映射，之后以此为中心对其他节点进行去匿名化也比较容易。被动攻击则是需要获取其他相关信息，比如其他热门社交网络的数据，来帮助实现映射的过程。

　　而是通过一种基于反馈的自增强方式进行匹配的，进行去匿名化。具体

　　算法分为两步。

　　1、种子的识别。首先攻击者利用少量用户的详细信息，包括每个节点的度、每对节点公共邻居的数量等，在公开网络中寻找相似的结构，完成对这些少量节点的映射。

　　2、扩散。利用第一步中得到的映射关系，不断找出新的节点映射关系，并加入到原有的关系中。

　　以博客为例，网络上的文章大部分是匿名的，每个人写作风格不同，可以使用机器学习的方法判断出一篇匿名文章来自哪个博客，也可以将同一个人写的不同博客识别出来。

　　首先要对文章进行预处理，只保留用英文写的较长的文章。有些作者喜欢在每篇文章开头或结尾留下签名或者代表自己的一段话，由于文章研究是利用文法对匿名文章分类，为了实验准确，这种前后缀也需要去掉。然后通过对文章进行自然语言处理，将文章抽象为包含文章特征的高维特征向量，其中包括文章长度、单词长度、不同类型词出现的频率以及一些文法的特征。

　　再使用机器学习的方法，用不同的分类器识别出文章的作者或他的博客，除了使用一个分类器进行分类，还可以将两个不同的分类器结合，对比两者的结果，得出最终答案。