去匿名化

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

去匿名化（De-anonymization）

　　去匿名化是指一種數據挖掘策略，其中的匿名數據和其它數據來源相互對照來重新識別匿名的數據來源。區別一個數據來源和另一個數據來源的任一信息都能用於去匿名化。

　　Netflix在2006年為改善電影推薦服務，公佈了部分用戶評分的數據集，其中包括用戶對電影的打分和打分日期。可以將數據集看成一個矩陣的形式，每一列都代表一部電影，每一行代表一個用戶對電影的打分情況。數據集中包含約500000個用戶，每個用戶看過的電影以及評分都不盡相同，打分的電影相似程度都很低，因此，又可以把這個數據集看作稀疏矩陣。

　　因為電影的數量很多，數據集維度太高，並不存在準標識符，K匿名化在這個數據集上並不適用。在這個數據集中，假定攻擊者知道一個人看過的幾部電影，希望可以找到他看過的所有電影記錄，即識別出這個人，而我們也希望知道最少需要知道幾部電影就可以有較高的正確率。

　　攻擊者首先通過計算自己的信息和數據集中每一個用戶信息的相似度，然後選擇相似度最高的作為結果。相似度的計算其實是通過分別比較每一部電影的相似程度而得出，如果攻擊者想識別的用戶和數據集中的一位用戶對同一部電影的評分和日期相差在一定的範圍內，比如日期相差不到14天，評分相等，則認為兩者相似。為使演算法更加健壯，規定相似度最大的值必須遠高於相似度第二大的值，這樣不但更好區分候選的用戶，也能更好地判斷攻擊者知道的用戶是否在數據集中。另外可以區分電影的冷熱程度，如果一部電影看的人很多，則這部電影對相似度的權重就會小一點，反之冷門電影對相似度起到的作用會大一些。

　　最後的實驗結果表明，通過8部電影的評分，和誤差允許14天的評分日期，就可以唯一標識數據集中99%的用戶;通過2部電影，68%的用戶可以被標識出來。即僅通過2到8部電影，就可以識別出這個用戶。而一個人8部的電影記錄很容易獲得，通過與其聊天或者查看博客就有可能得到。

　　社會網路在近幾年非常流行，其中的數據也是另一類被研究很多的數據。與矩陣不同，它首先包括一個有向圖或者無向圖，圖中節點表示網路中的實體，邊表示實體間的關係，圖的點和邊也會有不同的屬性。社會網路的數據除了組織機構公開在網上的，還可以通過社交網站提供的應用程式介面(API)自己進行爬取。匿名化的方法主要有隨機的刪除邊和增加邊，還有對點和邊的屬性進行K匿名化等。

　　社會網路的去匿名化主要針對的是節點的去匿名化，識別一個節點就是獲得一個人的真實信息。對於社會網路的去匿名化方法可以分為兩類，一類是基於映射的方法，另一類是基於猜測的方法。基於映射的方法是將攻擊者瞭解的或爬取得到的真實網路結構與公開的經過匿名化的網路結構數據做節點匹配。基於猜測的方法則是利用攻擊者已知的背景知識在公開數據中找到符合的一個或多個節點。

　　在映射的方法中攻擊者假定瞭解少量用戶的詳細信息，而且通過爬蟲等方法也得到了網路中大量的用戶和關係，最終希望能把公開網路中與自己獲取的網路中節點一一對應起來。根據攻擊者的方式可以將其分為主動攻擊和被動攻擊，主動攻擊的方法是在數據發佈之前攻擊者就創建一定數量的賬號並使他們各自成為好友關係，這樣形成一種很容易分辨出來的形式，在數據匿名發佈後，首先找到這些點的映射，之後以此為中心對其他節點進行去匿名化也比較容易。被動攻擊則是需要獲取其他相關信息，比如其他熱門社交網路的數據，來幫助實現映射的過程。

　　而是通過一種基於反饋的自增強方式進行匹配的，進行去匿名化。具體

　　演算法分為兩步。

　　1、種子的識別。首先攻擊者利用少量用戶的詳細信息，包括每個節點的度、每對節點公共鄰居的數量等，在公開網路中尋找相似的結構，完成對這些少量節點的映射。

　　2、擴散。利用第一步中得到的映射關係，不斷找出新的節點映射關係，並加入到原有的關係中。

　　以博客為例，網路上的文章大部分是匿名的，每個人寫作風格不同，可以使用機器學習的方法判斷出一篇匿名文章來自哪個博客，也可以將同一個人寫的不同博客識別出來。

　　首先要對文章進行預處理，只保留用英文寫的較長的文章。有些作者喜歡在每篇文章開頭或結尾留下簽名或者代表自己的一段話，由於文章研究是利用文法對匿名文章分類，為了實驗準確，這種前尾碼也需要去掉。然後通過對文章進行自然語言處理，將文章抽象為包含文章特征的高維特征向量，其中包括文章長度、單詞長度、不同類型詞出現的頻率以及一些文法的特征。

　　再使用機器學習的方法，用不同的分類器識別出文章的作者或他的博客，除了使用一個分類器進行分類，還可以將兩個不同的分類器結合，對比兩者的結果，得出最終答案。