[發明專利]一種社交媒體用戶行為時間模式的自適應隱私保護方法

有效

• 申請號: 201710706006.4
• 申請日: 2017-08-17
• 公開（公告）號: CN107688751B
• 公開（公告）日: 2021-02-26
• 發明（設計）人: 曾劍平;張澤文
• 申請（專利權）人: 復旦大學
• 主分類號: G06F21/62
• 分類號: G06F21/62
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

1.一種社交媒體用戶行為時間模式的自適應隱私保護方法，其特征在于，先定義所需處理的用戶行為、行為模式元信息、行為模式的元信息集：

定義1，用戶行為，是指用戶在網絡社交媒體中留下附帶有時間標簽的痕跡的行為，包括發貼行為、評論行為、簽到行為；在面向以時間點數據為主的應用中，時間模式是導致隱私泄露的主要數據源，將這種原始的用戶行為表示為：

U(u,d)＝(t₁,t₂,…t_m)

其中，u表示某個用戶，d表示某個時間段，t表示行為在時間標簽上的數值，m是在d時間段內的時間標簽數；

定義2，行為模式元信息，一定時間范圍內的用戶行為對應一個二維結構，將該時間范圍按特定粒度切分成時間段，構成第一個維度，每個時間段上用戶行為的頻次作為第二個維度，連續的n個時間段上用戶行為的頻次稱為行為模式元信息；時間段是元信息的屬性，記作A₁,A₂,…,A_n，時間段上用戶行為的頻次是元信息的值，記作a₁,a₂,…,a_n，從而元信息可以表示為連續n個時間段屬性上的投影，記投影映射為T：

(a₁,a₂,…,a_n)＝T[(A₁,A₂,…,A_n)]；

定義3，行為模式的元信息集，把行為模式元信息看作空間中的數據點，由社交媒體中所有用戶對應的K個數據點所構成的點集稱為行為模式的元信息集，形式定義如下：

其中，M_i＝{a₁,a₂,…,a_n}，i＝1,2,…,K；

自適應隱私保護方法分為預處理流程和隱私保護流程兩個步驟：

(一)預處理流程包括：獲取原始數據，按最小時間分割粒度，擴大時間段，生成行為模式元信息集；

(1)獲取原始數據

原始數據是指社交媒體上與用戶行為有關的數據，可以通過各種網絡爬蟲或社交媒體自身提供的應用程序接口調用得到，將用戶標識和行為的時間戳提取出來，原始數據集包括若干個用戶在一定時間內的行為數據，符合定義1的要求；

(2)按最小時間段分割

先設定一個最小時間段，其原則是優先保證數據可用性；分割過程就是對原始數據集的時間跨度按照最小時間段進行平均分割；

(3)擴大時間段

擴大時間段的目的是為了提升數據的隱私度，同時減小原始數據的數據量，以保證后續的自適應微聚集算法在處理這些數據時不需要太多的計算資源消耗；擴大時間段的過程為：依次掃描每個最小時間段上的用戶行為數量，當該數量小于匿名度時，表明這種時間段無法保證k個不同用戶的隱私；將其與后續的時間段進行合并，直到滿足行為數量大于匿名度為止，得到了一系列時間段A₁,A₂,…,A_n；

(4)生成行為模式元信息集

生成行為模式的元信息集就是統計每個用戶在每個時間段分割區間上的行為數量，并構造成為一個大小為用戶數量*時間段數的矩陣；

對于已經獲得的一系列時間段A₁,A₂,…,A_n，按照順序分別形成分割區間，即[0,A₁],[A₁,A₂],…,[A_n-1,A_n]；

最終所形成的矩陣形式上為：

其中，每個元素M_ij表示第i個用戶在第j個區間上的行為次數，K為用戶數；

(二)隱私保護流程，包括：設定匿名度k，執行微聚集隱私保護算法的處理流程，產生隱私保護數據集

(1)設定匿名度k

匿名度是用于控制一個數據集中相同記錄的個數；對于一個含有k個用戶的數據集，如果這些用戶的行為數據都相同，那么攻擊者成功推斷其中任何一個用戶的概率為1/k；

(2)微聚集隱私保護算法的處理，具體步驟如下：

對于用戶行為模式的元信息集匿名度k；

1)計算元信息集的整體質心，找出離整體質心最遠的點作為離心點，并找出距離離心點最近的2k-1個點；依距離從小到大排序，取前k-1個與離心點組成一個既有類，而剩余的k個點構成一個候選點隊列；

2)對于候選點隊列中的每一個候選點，循環執行步驟3)-5)的自適應判斷條件，決定是否將候選點加入到既有類中；

3)構建第一假想類、第二假想類、第三假想類，既有類與候選點共同形成的類作為第一假想類，除第一假想類之外的k個距離候選點最鄰近的點形成的類作為第二假想類，候選點與除既有類之外的k個最近鄰點形成的類作為第三假想類；

構造完假想類后，分別計算既有類、第一假想類、第二假想類以及第三假想類這四個類的信息損失；如果既有類與第三假想類的信息損失之和大于第一假想類與第二假想類的信息損失之和，則執行步驟4)；反之，執行步驟5)；

4)將候選點加入既有類之中，并從候選點隊列中刪除，繼續處理下一個候選點；

5)只將候選點從候選點隊列中刪除，不加入既有類之中，繼續處理下一個候選點；

6)記錄既有類信息，并將該既有類中的點從元信息集中刪除，若元信息集剩余點的個數不少于2k，則回到步驟1)繼續執行；否則，依照信息損失最小原則，將剩余點分配到相應的既有類之中；

7)生成隱私保護后的數據集，對每一個既有類中的每個點用該既有類的質心代替，從而將原始行為模式的元信息集轉換成為新的具備保護隱私能力的數據集；

最后得到隱私保護后的數據集。

2.根據權利要求1所述的社交媒體用戶行為時間模式的自適應隱私保護方法，其特征在于，步驟3)-5)中的自適應判斷條件，具體如下：

判斷候選點是否加入既有類時，需要構造三個假想類；既有類與第三假想類的信息損失之和大于第一、第二假想類的信息損失之和，就是候選點加入既有類后減小整體信息損失的充要條件；該判斷條件的具體計算方法如下：

首先，既有類的信息損失記為IL₁，信息損失采用SSE度量方法，即誤差項的平方和，由此，可以計算既有類的信息損失IL₁：

上式中，x_i為既有類中的數據點，為既有類的質心；

在構造的第一假想類中，候選點被分配到了既有類中，因而對既有類的質心造成了擾動，記第一假想類的質心為則第一假想類的信息損失IL′₁的計算方法如下：

同理，第二假想類的信息損失IL₂和第三假想類的信息損失IL′₂分別表示為：

上式中，x_j為第二假想類和第三假想類中的數據點，為第二假想類的質心，為第三假想類的質心；

如果把候選點分配到既有類中，則整體的信息損失IL_a為第一假想類和第二假想類的信息損失之和，即：

IL_a＝IL′₁+IL₂

如果把候選點分配到第二假想類中，則整體的信息損失IL_b為既有類和第三假想類的信息損失之和，即：

IL_b＝IL₁+IL′₂

將兩種情況下的信息損失相減，得到它們的差值ΔIL：

ΔIL＝IL_a-IL_b＝ΔIL₁-ΔIL₂

其中，ΔIL₁為第一假想類相對于既有類的信息損失增量，ΔIL₂為第三假想類相對于第二假想類的信息損失增量，ΔIL表示候選點分配到既有類中相對于候選點分配到第二假想類中的整體信息損失的增量；

判斷條件為ΔIL≤0，這一條件的滿足，說明候選點分配到既有類中造成的整體信息損失更小，把候選點加入既有類中；反之，說明候選點分配到第二假想類中造成的整體信息損失更小，不把候選點加入既有類中。