[發(fā)明專(zhuān)利]一種使用圖差分隱私模型的敏感標(biāo)簽軌跡數(shù)據(jù)發(fā)布方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010164862.3
• 申請(qǐng)日: 2020-03-11
• 公開(kāi)（公告）號(hào): CN111353173B
• 公開(kāi)（公告）日: 2022-09-20
• 發(fā)明（設(shè)計(jì)）人: 姚琳;陳振宇;孫云棟;吳國(guó)偉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 大連理工大學(xué)
• 主分類(lèi)號(hào): G06F21/62
• 分類(lèi)號(hào): G06F21/62
• 代理公司: 大連理工大學(xué)專(zhuān)利中心 21200
• 代理人: 溫福雪;隋秀文

1.一種基于圖差分隱私模型的敏感標(biāo)簽軌跡數(shù)據(jù)發(fā)布方法，其特征在于，具體步驟如下：

(1)軌跡的聚類(lèi)和泛化

(1.1)首先獲取原始軌跡數(shù)據(jù)集D，然后采用DBSCAN算法查找包含熱點(diǎn)位置和異常值的候選位置區(qū)域；熱點(diǎn)位置是時(shí)空點(diǎn)相對(duì)密集的區(qū)域，異常值是與其他數(shù)據(jù)集中的時(shí)空點(diǎn)相差甚遠(yuǎn)或在某些衡量度量下不一致的時(shí)空點(diǎn)；

(1.2)獲得異常值集合O和當(dāng)做熱點(diǎn)位置的聚類(lèi)集合C，將原始軌跡數(shù)據(jù)中時(shí)空點(diǎn)的位置替換為對(duì)應(yīng)熱點(diǎn)位置的中心，來(lái)泛化軌跡數(shù)據(jù)中的每個(gè)具體位置；

(1.3)獲得泛化后的軌跡數(shù)據(jù)集D′＝{C,O}；

(2)基于圖的時(shí)空點(diǎn)差分隱私

(2.1)建立一個(gè)噪聲圖，將熱點(diǎn)、異常值以及隱私標(biāo)簽SA映射到有向加權(quán)圖；將D′中所有不同的SA值映射到G中的頭頂點(diǎn)，G為由D′映射而來(lái)的圖；頭頂點(diǎn)被視為每條記錄的開(kāi)始，每個(gè)頭頂點(diǎn)的頂點(diǎn)權(quán)重是原始數(shù)據(jù)中具有該SA值的軌跡的數(shù)量；

(2.2)將D′中所有軌跡中的每個(gè)位置映射到軌跡頂點(diǎn)；

(2.3)為不同的頂點(diǎn)設(shè)置不同的隱私預(yù)算ε值；根據(jù)SA值的隱私程度設(shè)定每個(gè)頭頂點(diǎn)的ε，隱私程度根據(jù)數(shù)據(jù)擁有者自身的要求設(shè)定，針對(duì)不同的SA值設(shè)定不同的ε值；

對(duì)于每個(gè)軌跡頂點(diǎn)v，設(shè)置一種通過(guò)這些數(shù)據(jù)擁有者{v₁,v₂,v₃,...v_n}的投票來(lái)確定ε，具體方法如下：

其中，表示υ_i和v之間的邊權(quán)重，是υ_i的頂點(diǎn)權(quán)重，是υ_i的隱私預(yù)算；

(2.4)生成一個(gè)噪聲圖G′，分別將每個(gè)拉普拉斯噪聲加到對(duì)應(yīng)υ_i的頂點(diǎn)權(quán)重上，υ_i的加噪后頂點(diǎn)權(quán)重計(jì)算如下所示：

(3)發(fā)布帶隱私標(biāo)簽的軌跡數(shù)據(jù)

(3.1)還原D′中的每一條軌跡：針對(duì)D′中的每條軌跡，以頭結(jié)點(diǎn)即SA節(jié)點(diǎn)為開(kāi)始，也就確定了每一條記錄的SA，然后通過(guò)在G′中的邊遍歷其他頂點(diǎn)，直到到達(dá)沒(méi)有出邊的頂點(diǎn)，則這條軌跡確定完畢；在生成軌跡時(shí)，如果該頂點(diǎn)的頂點(diǎn)權(quán)重大于0，遍歷過(guò)程中所經(jīng)過(guò)的頂點(diǎn)的權(quán)重減1，而邊的權(quán)值不變，生成的軌跡具有與原D′中的軌跡相同的SA值和時(shí)空點(diǎn)；如果由于加噪時(shí)的負(fù)噪聲造成頂點(diǎn)權(quán)重減小，在軌跡逐條生成過(guò)程中，路徑上存在頂點(diǎn)的頂點(diǎn)權(quán)重為0，則將在生成與原D′中的相同軌跡時(shí)刪除這些頂點(diǎn)；

(3.2)根據(jù)啟發(fā)式生成軌跡數(shù)據(jù)：首先，獲取到所有頂點(diǎn)權(quán)重不為零的頭頂點(diǎn)為備選集合S，基于備選集合S的啟發(fā)式，選擇在S中具有最大頂點(diǎn)權(quán)重的υ_i，然后選擇υ_i的鄰居頂點(diǎn)到υ_i中具有最大邊權(quán)重的頂點(diǎn)；一旦選擇了這樣的頂點(diǎn)，則該頂點(diǎn)的頂點(diǎn)權(quán)重減少1；重復(fù)選擇，直到當(dāng)前所選頂點(diǎn)沒(méi)有出邊，然后刪除具有零權(quán)重的所選頂點(diǎn)，生成整條軌跡；重復(fù)軌跡生成過(guò)程，直到G′中沒(méi)有剩余頂點(diǎn)；

(3.3)得到匿名后的數(shù)據(jù)。