[發明專利]基于度優先的K-Anonymity匿名算法的數據處理方法

有效

• 申請號: 201010176282.2
• 申請日: 2010-05-19
• 公開（公告）號: CN101834872A
• 公開（公告）日: 2010-09-15
• 發明（設計）人: 胡翔天;宮秀軍;陳海亮;趙菲菲;劉新覓
• 申請（專利權）人: 天津大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;G06F21/00
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 李素蘭

技術領域

本發明涉及數據挖掘領域，尤其是涉及一種利用K-Anonymity(K-匿名)算法對隱私數據進行處理的方法。

背景技術

隱私數據匿名化的常用處理手段源于統計數據庫中的數據處理方法，主要是通過以發布數據中的屬性值的信息損失為代價，換取通過這些屬性值再標識某些個體的準確性，同時盡可能保證發布數據的可用性，在發布數據的準確性和隱私保護之間達到一種平衡。與傳統的保證發布數據整體趨勢而犧牲單個數據記錄準確性的隱私保護方法相比，為發布數據提供更好的可用性。常用的兩種隱私數據匿名化算法包括：

1.K-Anonymity(K-匿名算法)：

K-匿名(K-Anonymity)模型是不同于傳統的訪問控制等基于目標的隱私保護技術，將一個典型的微數據發布模型(微數據定義為一條表達和描述個體信息的數據記錄作為個體信息的載體)。這些個體信息包括個體的標識信息(如姓名、身份證號等)、敏感信息(如病史等)、以及一些非敏感信息(如性別)。每個個體信息都是以個體屬性和相應的屬性值匹配的方式作為微數據(記錄)的某個分量。該算法要求首先對原始數據進行預處理以滿足匿名要求，然后將處理的數據予以發布；并且不限制對已發布數據的訪問，相反盡可能的保持數據的可統計性。因而需要在該算法采用數據泛化(泛化是對于數據的一個屬性，用概括值代替原來的值，使其意義更為抽象)這一常用的數據預處理手段。

K匿名就是要求在一個集合中(這里是指廣義集合，即允許包含相同元素，類似于包(Bag)或簇(Cluster)的概念)中只能以不大于1/k(k是一個常數)的概率確定任何一個元素，即要求任何一個元素在集合中至少存在k-1個相同的副本元素。

用形式化的語言表述K匿名的概念，一般是將發布數據表中的個體記錄的屬性分為標識符、準標識符、敏感屬性三類。以下是相關定義：

標識符(Identifiers)：標識符屬性是指能夠直接標識出個體身份的屬性，如姓名、身份證號碼、社會保險號碼等屬性，通過這些屬性值能夠直接確定具體的個體。

準標識符(Quasi-Indentifiers，QI)：給定實體集合U、實體表T(A₁，A₂，…A_n)，f_c：U→T以及f_g：T→U′。其中實體表T的準標識符QI為屬性組(A₁，A₂，…A_j)，其中且滿足f_g(f_c(p_i[QI]))＝p_i。換言之，同時存在于發布數據表和外部數據源表中，利用此兩種數據表進行連接的推演來表示個人隱私信息的一組屬性稱為準標識符屬性。準標識符屬性Quasi-Identifiers也叫做類標識符屬性。不同的發布數據表可以根據不同的情況劃分不同的準標識符屬性，一般情況下準標識符由專家選擇，而非用戶隨便選取。一般情況下可以以年齡、教育程度、性別作為準標識符。

敏感屬性(Sensitive-Attributes，SA)，個人隱私屬性。發布數據中，個體不希望其他用戶知道的信息屬性。比如說個人的工資水平、患者的就診記錄中的所患疾病。發布數據時，為了防止個人敏感信息的泄露，標識符必須被刪除，發布的數據記錄只保留準表示副屬性和敏感屬性，稱為匿名化處理。

等價組：在準標識符上的投影完全相同的記錄組成的等價組，即：等價組中所有的記錄在準標識符上的屬性值完全相同，其他的屬性值可以不同。

K-匿名描述：給定數據表T(A₁，A₂，…A_n)，QI是與T相關聯的準標識符，當且僅當在T[QI]中出現的每個值序列至少在T[QI]中出現K次，則T滿足K-匿名。T[QI]表示T表元組在QI上的投影。

現實生活中，將醫療、投票、求職等信息公開的同時又要保證隱藏相關患者、投票人、和求職人等的個體標識信息并確保這些公布的數據不能用來推到出這些標識信息時，K匿名就是非常好的可選模型。當數據發布到公共數據庫，數據的擁有者不再繼續控制數據的使用方式和范圍時，在這種情況下為了不暴露數據主體的身份移出所有涉及到個體標識的數據項信息De-Identification(即去標識)就是一種常用的方法。

2.OLA(Optimal?Lattice?Anonymization)算法(最優泛化格匿名化算法)