基于遺傳算法的軌跡K匿名模型優化

秦海濤

摘? 要：常用軌跡隱私保護方法的得來離不開基于虛假軌跡的匿名研究，軌跡匿名方法生成虛假軌跡的不確定性及軌跡信息與背景知識之間的關聯性，導致用戶的真實軌跡隱私信息極易被識別。為此，文章提出基于遺傳算法的軌跡k匿名模型優化算法。在用戶真實軌跡的基礎上，采用深度學習中有監督學習原理及冪律-對數函數解決分布函數中長尾數據問題，改進遺傳算法中的變異操作和適應度函數，通過改進后的遺傳算法來優化軌跡K匿名模型生成虛假軌跡的方法，并利用皮爾遜相關性計算軌跡相似性，調整軌跡中個體的位置，構建具有相同用戶行為模式的k匿名軌跡集合。實驗結果表明，該算法具有更好的適用性和隱匿性，降低了用戶隱私披露風險。

關鍵詞：軌跡匿名；軌跡k匿名；遺傳算法；虛假軌跡；用戶行為模式

中圖分類號：TP18? 文獻標識碼：A? 文章編號：2096-4706（2023）15-0063-06

Anonymity Model Optimization of Trajectory K Based on Genetic Algorithm

QIN Haitao

（School of Information Engineering， Gansu Vocational and Technical College of Communications， Lanzhou? 730070， China）

Abstract： The development of commonly used trajectory privacy protection methods cannot be separated from anonymous research based on false trajectories. The uncertainty of false trajectory generated by trajectory anonymity methods and the correlation between trajectory information and background knowledge result in users' real trajectory privacy information being easily recognized. Therefore， this paper proposes a genetic algorithm-based trajectory k-anonymity model optimization algorithm. On the basis of the user's real trajectory， the principle of Supervised learning in deep learning and the power law logarithmic function are used to solve the problem of long tail data in the distribution function， the mutation operation and fitness function in the genetic algorithm are improved， and the improved genetic algorithm is used to optimize the method of generating false trajectory by the trajectory K anonymous model， and Pearson correlation is used to calculate the trajectory similarity and adjust the position of individuals in the trajectory， construct k anonymous trajectories set with the same user behavior patterns. The experimental results show that the algorithm has better applicability and concealment， reducing the risk of user privacy disclosure.

Keywords： trajectory anonymity; trajectory k anonymous; genetic algorithm; false trajectory; user behavior pattern

0? 引? 言

軌跡匿名研究是用戶隱私保護問題中的一個重要分支，涉及用戶的興趣愛好及生活習性等多個方面的內容。一般將軌跡匿名問題描述為：通過算法生成滿足匿名需求的若干虛假軌跡，使得以真實用戶軌跡為自變量的虛假軌跡生成算法生成的虛假軌跡數目達到最優，從而保護用戶的隱私信息[1]。一個好的軌跡匿名算法（如基于移動終端的虛假軌跡生成方法[2]、軌跡K-匿名隱私保護方法[3-5]、基于用戶真實軌跡的虛假軌跡生成方法[6]、基于歷史軌跡預測攻擊的動態K-匿名算法[7]等）可以提高軌跡匿名的效率，降低背景知識和同質攻擊對軌跡匿名的影響，提高所生成虛假軌跡的有效性。軌跡匿名算法生成虛假軌跡具有以下兩個特點：軌跡隨機性和軌跡異常性。針對軌跡匿名的兩個特點本文做出如下研究：

1）根據軌跡匿名算法生成虛假軌跡的隨機性以及虛假軌跡與背景知識的關聯性，提出通過遺傳算法將特定區域內的用戶真實軌跡信息生成虛假軌跡。

2）為確保真實軌跡在虛假軌跡中的隱匿性以及避免生成的虛假軌跡中異常點、敏感位置點、重合點的出現，通過改進遺傳算法中的變異操作和適應度函數來調整虛假軌跡中的位置點。

3）為進一步提高遺傳算法生成的虛假軌跡的有效性，提出基于遺傳算法的用戶行為模式構建方法。

1? 相關技術

1.1? 軌跡k匿名

軌跡k匿名可以生成滿足匿名需求的若干虛假軌跡，以保護真實軌跡不被識別出來。與傳統軌跡匿名相比，軌跡k匿名[3-5，8，9]僅考慮位置之間的關聯性，能夠防御針對單個位置的攻擊，但是虛假軌跡的生成總是存在一定的隨機性，通過背景知識與軌跡之間的關聯性，依然可以剔除部分不合理的虛假軌跡，影響隱私保護的效果。

1.2? 遺傳算法

遺傳算法是模擬自然界生物遺傳進化過程，基于適者生存思想搜索最優解的算法[10]。算法維護一個代表問題潛在解的群體，對于群體的進化，算法引入了類似自然進化中選擇、交叉以及變異等算子。遺傳算法搜索全局最優解的過程是一個不斷迭代的過程，每一次迭代相當于生物進化中的一次循環，直至滿足算法的終止條件。

2? 基于遺傳算法的軌跡匿名

標準軌跡匿名算法生成的虛假軌跡存在隨機性，攻擊者通過背景知識與軌跡信息之間的關聯性可以迅速地將部分不符合要求的虛假軌跡剔除出來，導致軌跡匿名失敗。針對軌跡匿名中出現的問題，本文遺傳算法流程如下：

1）將匿名用戶和其他用戶的軌跡位置點進行編碼和用戶ID標記，以位置點為基因，隨機生成初始種群。

2）計算基因的適應度函數值。

3）通過選擇算子選擇群體中滿足適應度函數的父代基因，形成子代基因，將不滿足適應度函數的父代基因進行交叉標記。

4）將有交叉標記的父代基因進行兩點交叉操作，生成子代基因，通過步驟2）和3）選擇滿足適應度函數的子代基因，以半徑R的最大選擇區域取代子代基因。

5）根據步驟4）選出群體中與匿名用戶軌跡位置點重合或相似度較高的基因位置點進行變異操作。

6）重復步驟3）、4）和5），直至滿足匿名條件，從位置點集合中選出具有同一用戶ID標記的基因，生成染色體個體，每個個體對應一條軌跡，由此生成滿足條件的軌跡k匿名集合。

2.1? 模型建立

2.1.1? 變異區間

標準遺傳算法的變異操作是采取隨機數的方法來設置個體基因的變異位置[8]。為避免變異操作生成不符合現實環境的個體基因、異常點、敏感位置點以及與匿名用戶重合的軌跡點，本文根據自監督變異函數[9]通過遺傳算法對生成的虛假軌跡進行改進，生成變異區間。自監督變異函數基于深度學習中的有監督學習原理，通過讀取的用戶匿名模式，設定個體中基因變異的區間位置以及區間內各個位置變異的概率，將傳統的隨機變異位置設定為一個變異區間，根據遺傳算法中的選擇算子和適應度計算函數選擇滿足匿名條件的基因。自監督變異函數如式（1）所示：

其中，x表示種群中的個體基因，μ表示基因在種群中的適應度值，α表示基因產生基因變異的概率，f （x）表示基因種群的平均適應度。

為了選擇滿足變異區間的子代個體基因，給出變異子代基因選擇條件：

F（X）≥f（x）（2）

F（X）

滿足式（2）條件，則由子代個體基因直接繼承；否則以半徑R的最大隱匿區域覆蓋基因（位置點），采用遺傳算法選擇區域內滿足匿名條件的基因來代替子代基因。

2.1.2? 適應度函數

傳統軌跡匿名算法生成的虛假軌跡一定程度上會出現一些長尾數據[11]，這些長尾數據中可能會包含用戶的敏感位置、與真實軌跡極為相似的位置以及重合位置，攻擊程序通過已掌握的背景知識可以迅速地從這些長尾數據中讀出用戶的一些隱私信息甚至能夠識別出用戶的真實軌跡，從而泄露用戶的隱私信息。

基于遺傳算法生成軌跡具有的表現型是虛假軌跡的最優表現形式[1]。為提高遺傳算法生成虛假軌跡的有效性，避免傳統軌跡匿名算法生成虛假軌跡的隨機性，本文結合冪律標定函數和對數標定函數[12，13]，構造冪律-對數函數進行適應度計算：

1）根據冪律標定函數計算種群中個體基因適應度：

基于冪律標定函數解決分布函數中長尾數值的原理，將軌跡集合中的個體基因進行冪律數值分布。式（4）中，a表示染色體適應度，f （x）表示種群平均適應度值，Dx表示個體基因適應度值，C表示軌跡信息中一個基因重復出現的次數，δ為表示個體基因變異概率。當a＞1時，表示當前選中軌跡中每個基因的適應度均滿足軌跡匿名所需的適應度，a＜1時，則表示當前選中的軌跡中存在長尾數據。

2）根據對數標定函數擬合不滿足種群適應度的個體基因：

根據冪律分布產生的長尾數據，通過自監督變異函數改變其個體基因分布，利用對數標定函數擬合出符合軌跡匿名的位置點。式（5）主要用來縮小目標數值之間的差異，擬合不滿足種群適應度的基因。a表示通過式（4）得到的軌跡中基因的冪律分布值，b表示軌跡中個體基因的適應度值由初始值i到n的最大變動范圍。

依據冪律-對數適應度函數計算個體基因適應度準則，將不滿足匿名條件的基因重復進行選擇、交叉、變異操作，經過遺傳算法操作的軌跡種群逐漸會出現一定的表現型。

3）基于遺傳算法的用戶行為模式構建。

文獻[6]認為用戶行為模式通過分析用戶真實軌跡信息的軌跡模式，使得生成的虛假軌跡與真實軌跡具有相似的模式，在保證與用戶真實軌跡相似性的同時應對背景信息的攻擊。本文利用皮爾遜相關性[14]計算特定區域內每條軌跡與真實軌跡的相似性，根據遺傳算法搜索局部最優解的特性，選擇與用戶真實軌跡相似性高的其他軌跡，基于遺傳算法的生物進化原理改變其他軌跡中的部分位置點，使得虛假軌跡與真實軌跡具有相似的運動模式，生成代替真實軌跡的虛假軌跡，進一步提高軌跡匿名的有效性。

用戶行為模式數學模型如式（6）所示：

其中，F（X ）表示基于位置點集合X的用戶行為模式所生成的虛假軌跡，i表示軌跡中的起始位置，n表示軌跡中的終止位置，W a表示匿名用戶a的行為模式，W b表示其他用戶的行為模式，∫a表示匿名用戶a的個體適應度，δa / δb表示對用戶b進行用戶行為模式重建，使得用戶b與匿名用戶a具有相同的用戶行為模式。

2.2? 算法概述

基于遺傳算法的軌跡匿名包含以下兩個部分：

1）虛假軌跡生成。采用適應度函數對軌跡集合中的個體基因進行冪律分布，針對不滿足種群適應度的個體基因，通過自監督變異函數改變其位置分布，利用對數標定函數和遺傳算法中的交叉、選擇、變異操作擬合出符合匿名條件的虛假軌跡。

2）用戶行為模式構建。選擇虛假軌跡集合中具有與真實軌跡相似閾值的虛假軌跡，通過遺傳算法對不滿足閾值的軌跡進行選擇、交叉和變異等操作改變其位置點，生成滿足匿名條件的虛假軌跡來代替真實軌跡，提高遺傳算法生成虛假軌跡的有效性，降低虛假軌跡與背景知識之間的關聯性。

2.2.1? 虛假軌跡生成算法

算法1：虛假軌跡生成算法

輸入：軌跡信息集合F

輸出：通過遺傳算法生成的軌跡匿名集合E

1）WHILE F！=NULL

2）{通過遺傳算法對F的位置點進行編碼形成初始種群Fi

3）對Fi中的基因計算適應度值

4）IF（Fi中的基因適應度值滿足種群適應度值）

5）遺傳給子代個體

6）? ? ELSE

7）進行選擇、交叉、變異操作，生成子代個體基因Fi1

8）? ? ? IF（Fi1的適應度值滿足種群適應度值）

9）Fi1遺傳給子代個體

10）? ? ?ELSE

11）以Fi1為圓心，以隱匿區域R為半徑，通過遺傳算法選擇區域內個體基因代替Fi1

12）i++; }

13）通過遺傳算法生成虛假軌跡

14）PUT E

2.2.2? 用戶行為模式構建

算法2：用戶行為模式構建

輸入：算法1生成的虛假軌跡集合E

輸出：具有相同用戶行為模式的虛假軌跡集合V

1）WHILEE！=NULL

2）{讀取真實用戶軌跡中的每一個位置點

3）FOR（Ei to En）

4）{利用皮爾遜相關性計算每條軌跡與真實軌跡的相似性

5）IF（相似性滿足閾值）

6）V=V+1

7）ELSE

8）通過遺傳算法進行位置變換，生成滿足閾值條件的虛假軌跡}

9）i++

10）}

11）PUTV

在算法1中，算法遍歷所有軌跡生成虛假軌跡，對于虛假軌跡集合中的每條軌跡信息，算法需要計算虛假軌跡與真實軌跡之間的相似性，保證所生成軌跡K匿名集合中的每一條虛假軌跡都可以代替真實軌跡，降低軌跡隱私泄露的風險。同時考慮虛假軌跡信息與背景知識之間的關聯性，為保證生成虛假軌跡的有效性，要求匿名集內的軌跡具有同一行為模式，與傳統軌跡k匿名相比，算法可以有效抵制軌跡相似性攻擊，增強隱私保護。

3? 實驗驗證與分析

3.1? 實驗參數設置

實驗采用的用戶軌跡由Thomas Brinkhoffs生成器模擬生成。本文選取50 km×50 km區域內1 000個時間片內的16 400條軌跡構成實驗數據集。如表1所示為實驗數據集參數。

實驗環境為Intel i5（3.4 GHz），4 GB內存，Windows 64操作系統，算法由eclipse 8.1和MATLAB 2016a編寫。

3.2? 實驗結果與分析

為驗證本文算法的有效性和高效性，從以下幾方面進行驗證：

1）用戶隱私保護度對比。

2）隱匿區域與背景知識之間的關聯性對用戶隱私信息泄露的概率。參與比較的方法包括：基于用戶真實軌跡的虛假軌跡生成方法[6]、軌跡替換法[15]及隨機行走方法[16]。

3.2.1? 用戶隱私保護度對比

為評估不同算法生成的虛假軌跡對用戶隱私保護的影響，本文根據文獻[17]提出的LBS隱私保護度量標準，引入軌跡信息熵指標，分析不同算法生成虛假軌跡的有效性。信息熵度量標準如式（7）所示：

其中，n表示真實軌跡數據集中的軌跡數目，H（s）表示軌跡信息熵， 表示用戶的真實軌跡， 表示所生成的用戶虛假軌跡。

隱私保護度如式（8）所示：

其中，H（Su）表示真實軌跡信息熵，H（S′ ）表示虛假軌跡信息熵，ε1表示軌跡隱私保護度，ε1值越小用戶隱私保護度越高，虛假軌跡泄露用戶隱私概率越低。

實驗選取真實軌跡數據集中的10 000條軌跡作為軌跡信息集合，用戶行為模式閾值δ = 0.65，軌跡適應度閾值δ1 = 0.95，軌跡K匿名閾值K = 8，隱匿區域R = 6 km。驗證相同匿名條件下不同算法生成的虛假軌跡對用戶隱私保護的影響，實驗結果如圖1所示。

3.2.2? 隱匿區域和背景知識對軌跡匿名的影響

考慮到隨著隱匿區域的不斷增大，通過算法生成的虛假軌跡攜帶的背景知識也越來越多，因此，引入區域信息熵指標，計算隱匿區域對虛假軌跡泄露用戶隱私信息的概率。隱匿區域對虛假軌跡泄露用戶隱私信息的信息熵由式（9）表示：

其中，H（s）表示在隱匿區域內生成的虛假軌跡泄露用戶隱私信息的信息熵，r表示隱匿區域的半徑，T表示隱匿區域內的真實軌跡，E表示隱匿區域內不同算法生成的虛假軌跡。

用戶隱私泄露的概率如式（10）所示：

其中，H（ST）表示真實軌跡在隱匿區域內的泄露用戶隱私概率的信息熵，H（S′ ）表示其他算法生成虛假軌跡泄露用戶隱私信息概率的信息熵，ε2表示用戶隱私泄露的概率，ε值越小用戶隱私保護度越高，虛假軌跡泄露用戶隱私概率越低。

隨著隱匿區域的不斷擴大，攻擊者可獲得的背景知識越來越多，軌跡隱私保護方法的有效性體現在通過背景信息與軌跡匿名之間的關聯性判斷出用戶隱私信息的概率。實驗設定軌跡數目為10 000條，用戶行為模式相似度閾值δ = 0.45，軌跡適應度閾值δ1 = 0.6，軌跡K匿名閾值K = 9時，分別從隱匿區域R為1 km、3 km和5 km的范圍內驗證隱匿區域增大對軌跡隱匿的影響，實驗結果如圖2所示。

在圖2中，（a）表示在隱匿區域和軌跡數目不斷增加的情況下，各個算法對用戶隱私泄露概率的影響呈現出不同的變化；（b）表示在不同的匿名區域內，不同算法生成的虛假軌跡的數目泄露用戶隱私信息的概率；（c）表示在相同的真實隱匿區域內，不同算法生成的虛假軌跡的數目泄露用戶隱私信息的概率。圖2的實驗結果表明，在設定相同匿名條件下，隨著匿名區域的不斷增大，四種軌跡匿名算法生成的虛假軌跡對用戶隱私信息泄露的概率也呈現出一定的劣勢。這是因為軌跡信息是一個多元化變量，隨著隱匿區域的不斷擴大，軌跡中的變量也在逐漸增加，同時軌跡信息所附帶的背景信息也逐漸增多，而本文和其他對比算法只考慮軌跡信息中的時間、空間及用戶行為模式這三個元素，未考慮軌跡的其他附帶信息，生成的虛假軌跡在匿名效率上逐漸出現劣勢，但相比于其他幾種算法，本文算法在保護用戶隱私信息方面還是顯現出一定的優勢。

4? 結? 論

本文針對軌跡匿名算法生成虛假軌跡的隨機性、背景信息與軌跡信息之間的關聯性以及軌跡匿名算法所生成的虛假軌跡中存在異常點、敏感位置及重合點的問題，提出在用戶真實軌跡的基礎上基于遺傳算法的虛假軌跡生成方法用來保護用戶的隱私信息。該方法通過改進遺傳算法中的變異操作和適應度選擇函數來優化軌跡K匿名算法。為進一步提高遺傳算法生成虛假軌跡的有效性，提出基于遺傳算法的用戶行為模式構建方法，使得生成的虛假軌跡與真實軌跡具有相同的行為模式。實驗結果表明，本文算法有效解決了軌跡匿名算法的隨機性以及所生成的虛假軌跡中存在異常點的問題，但初始種群的選擇和背景知識對軌跡信息的影響仍是接下來的主要研究工作。

參考文獻：

[1] 鄒貴祥，張飛舟.針對選址問題的一種遺傳算法改進探究 [J].計算機工程與科學，2018，40（4）：712-722.

[2] PHAN T N，K?NG J，DANG T K. KUR-Algorithm： From Position to Trajectory Privacy Protection in Location-Based Applications [EB/OL].[2023-03-26].https：//www.researchgate.net/publication/281063652_Trong_Nhan_Phan_Josef_Kung_Tran_Khanh_Dang_KUR-Algorithm_From_Position_to_Trajectory_Privacy_Protection_in_Location-Based_Applications_In_Proceedings_of_the_26th_International_Conference_on_Database_a.

[3] PALANISAMY B，LIU L. Attack-Resilient Mix-zones over Road Networks： Architecture and Algorithms [J].IEEE Transactions on Mobile Computing，2015，14（3）：495-508.

[4] YE Y M，PAN C C，YANG G K. An Improved Location-Based Service Authentication Algorithm with Personalized K –Anonymity [EB/OL].[2023-04-02].https：//kns.cnki.net/KCMS/detail/detail.aspx？dbcode=IPFD&filename=WXDH201605012004.

[5] LEE H，CHANG J W. Density-Based K-Anonymization Scheme for Preserving Users' Privacy in Location-Based Services [EB/OL].[2023-03-16].https：//link.springer.com/chapter/10.1007/978-3-642-38027-3_57.

[6] 林鄧偉，王云峰.基于用戶真實軌跡的虛假軌跡生成方法 [J].計算機工程，2018，44（8）：142-150.

[7] 李成龍，呂鑫，李鑫.抗基于歷史軌跡預測攻擊的動態K-匿名算法 [J].計算機工程與應用，2018，54（2）：119-124.

[8] SAMARATI P，SWEENEY L. Generalizing data to provide anonymity when disclosing information （abstract） [EB/OL].[2023-03-20].https：//dl.acm.org/doi/10.1145/275487.275508.

[9] LATANYA SWEENEY. K-Anonymity： A Model For Protecting Privacy [J].International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems，2002，10（5）：557-570.

[10] XU A G，XU T，ZHANG M Y，et al. GPS real time point positioning based on genetic algorithm [EB/OL].[2023-03-16].http：//en.cnki.com.cn/article_en/cjfdtotal-chkd2009s2008.htm.

[11] 張軍，詹志輝，等.計算智能 [M].北京：清華大學出版社，2009.

[12] 胡海波，王林.冪律分布研究簡史 [J].物理，2005，34（12）：889-896.

[13] 史加榮，馬媛媛.深度學習的研究進展與發展 [J].計算機工程與應用，2018，54（10）：1-10.

[14] 陳希孺.數理統計學簡史 [M].長沙：湖南教育出版社，2002.

[15] BINDSCHAEDLER V，SHOKRI R. Synthesizing Plausible Privacy-Preserving Location Traces [C]//2016 IEEE Symposium on Security and Privacy （SP）. San Jose：IEEE，2016：546-563.

[16] KATO R，IWATA M，HARA T，et al. A dummy-based anonymization method based on user trajectory with pauses [EB/OL].[2023-03-09].https：//dl.acm.org/doi/pdf/10.1145/2424321.2424354.

[17] 康海燕，朱萬祥.位置服務隱私保護 [J].山東大學學報：理學版，2018，53（11）：35-50.