實現軌跡km-匿名的最小變形度算法

郭 會，韓建民，魯劍鋒，彭 浩，鄭路倩

（浙江師范大學數理與信息工程學院，浙江金華321004）

實現軌跡km-匿名的最小變形度算法

郭 會，韓建民，魯劍鋒，彭 浩，鄭路倩

（浙江師范大學數理與信息工程學院，浙江金華321004）

km-匿名可以抵制長度為m的背景知識攻擊，然而現有的匿名化算法在泛化處理時，優先選擇支持度最小的位置點進行處理，未考慮泛化造成的變形度。隨著m值的增大，軌跡變形度會變大。針對該問題，提出2種匿名化算法：最小變形度貪心算法和基于先驗原則的最小變形度貪心算法，2種算法優先選擇變形度最小的位置點進行泛化，使得泛化所造成的變形度更小，并給出匿名軌跡可用性度量方法，對數據可用性和算法效率進行分析。實驗結果表明，與現有的匿名化算法相比，2種算法均可生成可用性更高的匿名軌跡。

隱私保護；km-匿名；軌跡；背景知識攻擊；點泛化變形度

1 概述

時空背景知識攻擊是匿名軌跡的主要攻擊形式。所謂時空背景知識攻擊是指攻擊者基于擁有的移動對象的部分時空信息，在發布的軌跡數據庫中推斷出該移動對象的軌跡信息。針對時空背景知識攻擊，目前常用的匿名模型是軌跡k-匿名［1-3］，其思想是使軌跡數據庫中任意一條軌跡至少與其他k-1條軌跡無法區分，這樣即使攻擊者擁有用戶軌跡全部的時空背景知識，能夠在發布軌跡數據庫中推導出該用戶的真實軌跡的概率也不超過1/k，從而保護了用戶隱私［4-6］。然而軌跡k-匿名要求k條軌跡所有時空點都不可區分，約束過強，匿名化過程會造成較大的信息損失。實際中，攻擊者擁有軌跡的全部時空知識是相當困難的，通常攻擊者只擁有了用戶的部分時空背景知識，匿名軌跡只要能夠抵制部分時空背景知識攻擊就可以了。基于該思想，文獻［7］提出了km-匿名模型，該匿名模型要求匿名軌跡數據庫中，對于每個長度不大于m的子軌跡，都存在至少k條軌跡包含這樣的子軌跡。文獻［7］也提出了基于距離的泛化算法，然而該算法只考慮點的支持度，忽略了點泛化對整個軌跡數據庫可用性的影響。為此，本文提出實現km-匿名模型的最小變形度的匿名化算法。

2 定義與符號

定義1（泛化區域） 設li，li+1，…，lv均為軌跡數據庫中的位置點，由2個或2個以上位置點所組成的區域稱為這些位置點的泛化區域，用｛li，li+1，…，lv｝表示。

定義2（位置集） 位置集是指軌跡數據庫中所有的移動對象所經過的位置點（或泛化區域）的集合，用L表示。

定義3（軌跡） 移動對象的軌跡是指移動對象按照時間順序所經過的位置點（或泛化區域）的有序序列，用t=（l1，l2，…，ln）表示。其中，li∈L，L為位置集。

定義4（子軌跡）移動對象的子軌跡是指移動對象按照時間順序所經過的位置點（或泛化區域）的有序序列的任一子序列，設s為軌跡t的子軌跡，s=（li，li+1，…，lv），t=（l1，l2，…，ln），則。

子軌跡中位置點（或泛化區域）的順序應該與軌跡中位置點（或泛化區域）的順序一致。例如，軌跡（a，e）是軌跡（d，a，c，e）的一個子軌跡。

定義5（子軌跡支持度） 設T為一軌跡數據庫，s為任一子軌跡，子軌跡s的支持度是指T中所包含子軌跡s的軌跡數，用sup（s，T）表示。例如，表1軌跡數據庫中sup（（a，e），T）=3。

表1 原始軌跡數據庫

定義6（位置點泛化平均距離） 設｛li，li+1，…，lv｝為一泛化區域，l為其中一個原始位置點，則l與泛化區域｛li，li+1，…，lv｝之間的泛化距離Dloc（l，｛li，li+1，…，lv｝）定義為l與｛li，li+1，…，lv｝中每個位置點的歐氏距離的平均值，見式（1）。

例如，表1為原始軌跡數據庫，圖1為表1中各個位置點的物理坐標，當位置點a，b泛化成｛a，b｝區域時，那么有Dloc（a，｛a，b｝）=（0+1）/2=0.5，Dloc（b，｛a，b｝）=（1+0）/2=0.5。

圖1 位置點的物理坐標

定義7（點泛化變形度） 軌跡數據庫中所有的位置點l泛化為｛li，li+1，…，lv｝區域后，整個數據庫由該位置點泛化所造成的變形度Distortionp（l，｛li，li+1，…，lv｝）定義為式（2）。

例如，當表1軌跡數據庫中所有的位置點a，b泛化為｛a，b｝時，Distortionp（a，｛a，b｝）=3×0.5= 1.5，Distortionp（b，｛a，b｝）=2×0.5=1。

定義8（軌跡數據庫變形度） 軌跡數據庫T中所有不滿足匿名約束的位置點l都泛化成區域｛li，li+1，…，lv｝后，生成的匿名軌跡數據庫T′與原始軌跡數據庫T之間的變形度DistortionT（T，T′）定義為式（3）。

例如，當表1軌跡數據庫T中所有位置點a，b都泛化成｛a，b｝區域時，匿名軌跡數據庫T′與軌跡數據庫T變形度DistortionT（T，T′）=1.5+1=2.5。

定義9（軌跡km-匿名） 設T為一軌跡數據庫，若其中任一長度不大于m的子軌跡s的支持度均不小于k，即?s，，都有sup（s，T）≥k，則稱T是軌跡km-匿名的。

例如，表1軌跡數據庫滿足21-匿名，但是它不滿足22-匿名，因為sup（（d，a），T）=1＜2。

為了實現軌跡km-匿名，需要把軌跡數據庫T中不滿足km-匿名的位置點跟其他位置點（或泛化區域）泛化，構成較大的泛化區域，使泛化后的匿名軌跡數據庫滿足km-匿名。為提高匿名軌跡數據的可用性，泛化過程要使軌跡數據庫變形度盡可能小。

3 軌跡匿名算法

3.1 GREANON算法

GREANON算法基于貪心的思想，首先找出所有不滿足km-匿名約束的子軌跡，即找出所有長度不大于m且支持度小于k的子軌跡。計算出這些子軌跡中所有位置點與其他位置點（或泛化區域）泛化將產生的軌跡數據庫變形度，選擇形變度最小的泛化，新的泛化區域替換軌跡數據庫中所有出現在新的泛化區域的位置點。重復上述過程，直到所有的長度不大于m的子軌跡都滿足km-匿名約束條件。具體描述見算法1。

算法1 GREANON算法

輸入 數據集T，參數k和m

輸出 km-匿名數據集T′

3.2 ACGREANON算法

ACGREANON算法是GREANON算法的改進，它在貪心算法的基礎上，結合文獻［7］的先驗原則。首先找出所有不滿足km-匿名約束的子軌跡并計算其支持度，然后在不滿足km-匿名約束的子軌跡中找出支持度最小的子軌跡，并找出該子軌跡中支持度最小的位置點（或泛化區域），計算該支持度最小的位置點（或泛化區域）跟其他位置點（或泛化區域）泛化后將產生的軌跡數據庫的變形度，選擇其中變形度最小的泛化，并用該泛化區域替換軌跡數據庫中所有出現在該泛化區域的位置點。重復上述泛化過程，直到所有長度不大于m的子軌跡都滿足km-匿名約束條件。具體描述見算法2。

算法2 ACGREANON算法

輸入 數據集T，參數k和m

輸出 km-匿名數據集T′

例如，表2為表1中所有不同位置點的支持度。表3為子軌跡長度為2且支持度小于2的子軌跡，由表2、表3可知，原始軌跡數據庫滿足21-匿名，但不滿足22-匿名（sup（d，a）=1）。以表1原始軌跡數據庫為實例，分別用GREANON算法和ACGREANON算法實現22-匿名。

表2 單個位置點的支持度

表3 不滿足22-匿名的子軌跡支持度

GREANON算法首先計算表3中所有位置點跟其他位置點泛化后將產生軌跡數據庫的變形度，并找到其中使得軌跡數據庫變形度最小的兩位置點l1，l2。通過計算可知l1=a，l2=b時軌跡數據庫變形度最小，此時Distortionp（a，｛a，b｝）=3×（1/2）= 1.5，Distortionp（b，｛a，b｝）=2×（1/2）=1，DistortionT（T，T1′）=1.5+1=2.5。用泛化區域｛a，b｝替換T，s中所有位置點a，b，得到表4軌跡數據庫T1′。表4軌跡數據庫還不滿足22-匿名，需要進一步泛化，重復上述過程，通過計算此時當l1=c，l2=d，軌跡數據庫變形度最小，DistortionT（T，T1′）=2.5+ 2+2.5=7，用泛化區域｛c，d｝替換T1′，s中所有位置點c，d，得到表5軌跡數據庫T1″，軌跡數據庫T1″滿足22-匿名。

表4 匿名軌跡數據庫T1′

表5 匿名軌跡數據庫T1″

用ACGREANON算法，實現k=2，m=2匿名。首先計算表3中子軌跡的支持度，找到支持度最小的子軌跡，然后計算支持度最小的子軌跡中位置點的支持度，并找出其中最小支持度的位置點l1，此時l1=b，然后計算b與其他位置點泛化后軌跡變形度，找出其中與b泛化產生軌跡變形度最小的位置點l2。通過計算，此時l2=a，DistortionT（T，T2′）=1.5+ 1=2.5，用泛化區域｛b，a｝替換軌跡數據庫T，s中所有的位置點a，b得到表6數據庫T2′。T2′還不滿足22-匿名，需重復上述泛化過程，通過計算此時l1=c，l2=d時軌跡變形度最小，DistortionT（T，T2″）= 2.5+2+2.5=7，用泛化區域｛c，d｝更新T2′，s中所有的c，d，得表7軌跡數據庫T2″，軌跡數據庫T2″滿足22-匿名。

表6 匿名軌跡數據庫T2′

表7 匿名軌跡數據庫T2″

GREANON算法和ACGREANON算法的思想一樣，步驟類似，兩算法具有相同的時間復雜度。算法中for為外循環，設位置集為L，那么不同的位置點（或泛化區域）數為，需要迭代的最大值為m。因為sup（s，T′）＜k的子軌跡數量跟k，m相關，為了便于度量，用p（m，k，T）表示子軌跡長度為m且sup（s，T′）＜k的一個概率，那么for外循環的時間復雜度為O（p（m，k，T）×m）。其中，w hile為內循環，最壞的情況下時間復雜度為O（m），所以整個程序的算法時間復雜度為O（m×p（m，k，T）×m），一般m的值比較小時，m×p（m，k，T）的值比較小，所以算法時間復雜度近似于O（m）。

4 匿名軌跡的評估模型

匿名軌跡的質量一般從2個方面進行評估，即匿名軌跡的安全性和可用性。

對于km-匿名的軌跡數據庫，其安全性一般可通過參數k和m來評估。m越大，攻擊者所具有的時空背景知識越多，km-匿名越安全，當m等于軌跡的長度時，此時的km-匿名就相當于k-匿名。k值越大攻擊者推導出用戶的軌跡概率（1/k）越小，匿名軌跡數據越安全。

數據可用性可從以下2方面來評估，即發布原始位置點的數量（ON）［7］和軌跡數據庫平均變形度（D）進行度量。

定義10（發布原始位置點的數量） 發布原始位置點的數量是指軌跡數據庫匿名過程中不需要被泛化的位置點的數量，用ON表示，見式（4）：

對于匿名軌跡數據庫而言，ON值越大，匿名軌跡數據庫保留了越多原始軌跡數據庫的信息，數據的可用性越好。

定義11（軌跡數據庫平均變形度） 軌跡數據庫平均變形度是指數據庫T與匿名數據庫T′之間變形度的平均值，用D表示，見式（5）：

軌跡數據庫平均變形度D反映了原始軌跡數據庫與匿名軌跡數據庫之間的差異，軌跡數據庫平均變形度越小說明匿名數據庫的可用性越好。

5 實驗結果與分析

5.1 實驗環境及參數配置

實驗運行環境為：3.0 GHz Intel Pentium（R）Dual-Core P7350處理器，2 GB內存，W indow s XP操作系統，算法采用C++實現，實驗軌跡數據由Brinkhoff［8］合成器合成，很多研究工作［9-11］都采用Brinkhoff合成器合成軌跡數據庫。合成軌跡所選的地理位置是Oldenburg City。實驗采用文獻［7］中的方法對軌跡進行初始化。首先將軌跡數據規范在103×103的網格中，然后把網格均勻地劃分為100個不同的網格區域，移動對象以一定的順序經過不同的網格區域，其中每個網格區域的中心坐標代表經過該網格區域的位置點的坐標，實驗中軌跡數據庫的平均長度為4.94，共100個位置點和18 143條軌跡。實驗將所本文所提出的ACGREANON算法和ACGREANO算法跟文獻［7］提出的SEQANON算法進行了比較。

5.2 數據的可用性分析

圖2 原始位置的點數量1

圖3 軌跡數據庫平均變形度1

由圖2、圖3可看出3種匿名算法生成的匿名軌跡數據庫中ON值都隨k值的增加而減小，D值隨k值增加而增加。因為隨著k值的增加，不滿足km-匿名的位置點增加，需要被泛化的位置點數量增加，所以數據的可用性變差。

圖4 原始位置點的數量2

圖5 軌跡數據庫平均變形度2

由圖4、圖5可以看出，3種匿名算法生成的匿名軌跡數據庫中ON值隨m值的增加而減小，D值隨m值增加而增加，因為隨著m值的增加，不滿足km-匿名的位置點增加，需要被泛化的位置點數量增加，所以數據的可用性變差。

圖6 原始位置的點數量3

圖7 軌跡數據庫平均變形度3

從圖2～圖7可以看出，隨著k和m值的增大，GREANON，ACGREANON算法總體上比SEQANON算法生成的匿名軌跡數據庫T′具有更高的數據可用性。這是因為GREANON，ACGREANON算法采用貪心思想每一次泛化都考慮了位置點（或泛化區域）泛化對整個軌跡數據形變度的影響，貪心算法能夠使得每一步都具有一個最優的效果。而SEQANON算法采用的是先驗原則的思想，每一次泛化考慮sup值最小的位置點（或泛化區域）泛化，準確定位泛化點，避免了算法的盲目性，但是sup值最小的位置點（或泛化區域）泛化并不能保證整個數據庫的變形度最小。

5.3 算法效率分析

由圖8～圖10可知，隨著k，m，|T|的增大運行時間呈上升的趨勢，且GREANON算法總體上比ACGREANON算法和SEQANON算法運行時間更短。而ACGREANON算法和SEQANON算法運行時間相近。因為ACGREANON，GREANON都基于先驗原則思想，需要反復計算位置點（或泛化區域）的支持度。

圖8 運行時間1

圖9 運行時間2

圖10 運行時間3

6 結束語

本文針對部分時空背景知識的軌跡攻擊，提出基于點泛化變形度的軌跡變形度的度量方法，設計了2個實現km-匿名模型的最小軌跡變形度匿名化算法：GREANON算法和ACGREANON算法，實驗結果表明本文提出的GREANON算法和ACGREANON算法相對現有算法SEQANON在實現km-匿名時能產生可用性更高的匿名軌跡。

下一步將開展對于具有敏感屬性的軌跡保護方法的研究；另外，本文所實現的km-匿名模型只能抵制身份鏈接攻擊，需要研究對于其他類型攻擊的保護模型。

［1］ Abul O，Bonchi F，Nanni M.Never Walk A lone：Uncertainty for Anonymity in Moving Objects Databases［C］// Proceedings of the 24th International Conference on Data Engineering.Washington D.C.，USA：IEEE Computing Society，2008：720-733.

［2］ Abul O，Bonchi F，Nanni M.Anonymization of Moving Objects Databases by Clustering and Perturbation［J］. Information Systems，2010，35（8）：884-910.

［3］ Mohammed N，Fung B C M，Debbabi M.Walking in the Crowd：Anonymizing Trajectory Data for Pattern Analysis［C］//Proceedings of the 18th ACM Conference on Information and Know ledge Management.Hong Kong，China：Association for Computing Machinery，2009：1441-1444.

［4］ Nergiz M E，A tzori M，Saygin Y.Towards Trajectory Anonymization：A Generalization-based Approach［J］. Transactions on Data Privacy，2009，2（1）：47-75.

［5］ M ohamm ed N，Chen Rui，Fung B C，et al.Privacypreserving Trajectory Data Publishing by Local Suppression［J］.Information Science，2013，231（1）：83-97.

［6］ M onreale A，Andrienko G，Andrienko N，et al.Movement Data Anonym ity Through Generalization［J］. Transactions on Data Privacy，2010，3（2）：91-121.

［7］ Poulis G，Skiadopoulos S，Loukides G，et al.Distancebased km-anonymization of Trajectory Data［C］//Proceedings of the 14th International Conference on Mobile Data Management.Milan，Italy：［s.n.］，2013：57-62.

［8］ 霍 崢，孟小峰.軌跡隱私保護技術研究［J］.計算機學報，2011，34（10）：1829-1830.

［9］ Brinkhoff T.A Framework for Generating Network-based Moving Objects［J］.Geo Informatica，2002，6（2）：153-180.

［10］ Yarovoy R，Bonchi F，Lakshmanan L V S，et al.Anonymizing Moving Objects：How to Hide a Mob in a Crowd？［C］//Proceedings of the 12th International Conference on Extending Database Technology.Saint Petersburg，Russia：［s.n.］，2009：72-83.

［11］ 趙 婧，張 淵，李 興，等.基于軌跡頻率抑制的軌跡隱私保護方法［J］計算機學報，2014，37（10）：2096-2106.

編輯 顧逸斐

Minimum Distortion Degree Algorithm of Trajectory km-anonymity Implementation

GUO Hui，HAN Jianm in，LU Jianfeng，PENG Hao，ZHENG Luqian
（College of Mathematics Physics and Information Engineering，Zhejiang Normal University，Jinhua 321004，China）

km-anonymity can resist background know ledge attacks of m-length subjectory.However，the existing anonymized algorithms select them inimum support point，not them inimum distortion point to generalize.Therefore，w ith increasing of m，the distortion of the trajectory tends to be larger.To address the problem，this paper proposes two kinds of anonym ized algorithms：one is them inimum distortion greedy anonym ized algorithm，the other is them inimum distortion greedy anonymized algorithm with apriori principles.These two algorithms both take consideration of the effect of the generalizing distortion，and choose the minimum distortion point to generalize，which can cause less distortion.It also proposes a method to measure the anonymous trajectory utility.It analyses the data availability and algorithm efficiency. Experimental results show that the proposed algorithm s can generate anonymous trajectory with higher trajectory utility than existing anonymized algorithm s.

privacy preservation；km-anonymity；trajectory；background know ledge attack；point generalized distortion degree

郭 會，韓建民，魯劍鋒，等.實現軌跡km-匿名的最小變形度算法［J］.計算機工程，2015，41（11）：180-185，201.

英文引用格式：Guo Hui，Han Jianm in，Lu Jianfeng，et al.Minimum Distortion Degree Algorithm of Trajectory km-anonym ity Implementation［J］.Computer Engineering，2015，41（11）：180-185，201.

1000-3428（2015）11-0180-06

A

TP301.6

10.3969/j.issn.1000-3428.2015.11.031

國家自然科學基金資助項目（61170108，61402418）；教育部人文社科研究基金資助項目（12YJCZH142）；浙江省自然科學基金資助項目（LQ13F020007）；上海市信息安全綜合管理技術研究重點實驗室開放基金資助項目（AGK2013003）。

郭 會（1990-），女，碩士研究生，主研方向：信息安全，隱私保護；韓建民，教授、博士；魯劍鋒、彭 浩，副教授、博士；鄭路倩，碩士研究生。

2014-10-13

2014-12-18 E-m ail：hanjm@zjnu.cn