基于遗传算法的轨迹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.