LBS連續查詢的匿名序列規則挖掘方法研究

陳澤偉，張海濤

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003； 2.南京郵電大學 地理與生物信息學院，江蘇 南京 210046)

LBS連續查詢的匿名序列規則挖掘方法研究

陳澤偉1，張海濤2

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003； 2.南京郵電大學 地理與生物信息學院，江蘇 南京 210046)

隨著LBS的深入發展與廣泛應用，隱私保護成為LBS深入發展中亟待解決的關鍵技術問題。時空K-匿名是LBS隱私保護的主要類型，當前研究尚未涉及匿名集數據的可用性和隱私保護的安全性。針對上述問題，基于匿名集數據具有時空序列的特性，提出了一種基于雙向不可逆擴展的匿名集序列規則挖掘算法。該算法在掃描序列數據庫的過程中，對相應的項集進行位置標記，從而保證了對序列數據庫一次掃描即能挖掘出用戶移動的序列規則。通過對頻繁模式進行擴展并發現用戶的移動規律、行為模式，對所提出的算法進行了驗證實驗及其結果分析。實驗結果表明，所提出算法的挖掘結果會涉及到敏感區域，如軍事領域等，因此對于實現LBS位置隱私保護具有重要的實踐意義，對于豐富隱私保護數據挖掘領域的研究具有一定的理論價值。

位置服務；位置隱私保護；時空K-匿名；序列規則

0 引 言

隨著LBS的深入發展與廣泛應用[1]，因LBS引發的隱私泄漏問題日益嚴重。一些位置隱私泄露事件(例如惡意的手機軟件、手機定位廣告等)引起了公眾的廣泛關注。隱私保護也成為LBS發展過程中亟待解決的關鍵問題[2]。

2003年，由Gruteser等提出的基于時空K-匿名的LBS隱私保護方法[3](簡稱時空K-匿名)，以匿名數據的真實可用、方法實現簡潔靈活以及更適合LBS移動計算環境等特點，成為近年來研究的主流方向。時空K-匿名的性能優化主要在快照查詢與連續查詢兩個方面展開。快照查詢包括4個方面：

(1)靈活設定隱私保護級別。文獻[4]提出了動態感知移動用戶時空分布設定K值的Clique-Cloak方法；文獻[5]提出了時空區域Footprint的概念，并基于Footprint設計了動態設置更人性化的隱私級別的保護方法。

(2)增強型查詢標識保護。時空K-匿名的匿名集與匿名查詢請求為1∶1關系，而Clique-Cloak方法要求匿名集的用戶均應提出查詢請求，但Clique-Cloak方法采用無向圖結構生成匿名集會產生計算量過大的問題，只適合較小K值的匿名保護。

(3)多模式查詢的隱私保護。文獻[6]改變時空K-匿名方法，同時進行查詢隱私與位置隱私保護。

(4)空間網絡與分布式傳感網的應用，設計了適合道路網絡的時空K-匿名[7]。

上述時空K-匿名及優化方法均沒有考慮針對匿名集敏感信息模式的隱私攻擊問題。這一類攻擊確實有存在的可能性：在實際LBS的應用中，LBS服務提供商以及應用第三方，通常會逐漸累積形成具有較大時空跨度的大量匿名集數據。同時，也發現了針對此類數據的關聯分析，可能對LBS用戶產生更具威脅性的隱私推理攻擊：發現用戶的行為模式，并基于行為模式進行隱私推理攻擊?，F有方法沒有對大量匿名集數據進行分析，沒有對匿名集數據的可用性以及隱私保護安全性進行深入研究。

為此，基于對匿名數據特性以及傳統的序列規則挖掘方法的分析，提出了一種基于雙向不可逆擴展的匿名集序列規則挖掘方法，詳細描述了算法步驟。實驗首先模擬生成匿名集序列數據，使用基于雙向不可逆擴展方法的匿名集序列規則挖掘方法進行數據挖掘，驗證算法的有效性。通過結合實際地理環境數據的應用效果，對實驗結果的分析，發現傳統的時空K-匿名方法存在隱私保護安全漏洞問題，挖掘結果涉及多處軍事敏感區域，因此該算法對于分析隱私攻擊推理和用戶隱私安全保護研究領域有重要的意義。

1 時空K-匿名集序列數據

1.1 時空K-匿名

時空K-匿名方法的基本思想是：計算當前圖幅網格中的用戶數，如果大于等于K，則匿名成功，生成匿名集；否則，進一步搜尋時空臨近的圖幅網格。搜尋方法為：依照順時針方向，依次搜尋空間臨近的圖幅網格(搜索方向為順時針，空間最大擴展范圍為8個鄰近的網格)。累加所有圖幅網格所包含的用戶數，直到總的用戶數大于等于K，則匿名成功，生成匿名集。否則，進一步進行時間鄰近范圍的搜尋(最大時間超前/延遲1個時段，每個時段的分辨率為2個小時)，累加前后時段的當前以及空間臨近的圖幅網格中的用戶數，如果大于等于K，則匿名成功，生成匿名集。否則匿名失敗。

1.2 連續查詢生成匿名集序列數據

連續查詢[8]是由同一用戶連續兩次或多次提出的查詢內容相同或高度相關的位置服務查詢。直接將快照查詢的匿名保護方法應用于連續查詢，會引起位置標識與查詢標識隱私的泄露[9-15]。文獻[5,10]分別提出了利用初始匿名集作為整個連續查詢匿名集的Memorization方法與Plain KAA方法。但隨著匿名集中移動對象的運動，匿名集的時空區域會擴展或收縮，使得位置服務QoS下降與位置隱私暴露。

具體的生成序列匿名集數據的方法如下：首先，從匿名用戶集AUS={u1,u2,…,um}中隨機選擇用戶uk，并將結果保存到數據庫中的AUS中；然后，每個用戶在每個網格均提出一次請求查詢，將該網格存儲到CR中，構成連續查詢的網格序列CR={Cell1,Cell2,…,Cellm}，服務器上保留該用戶提出請求時延TD={T1,T2,…,Tm}，存儲到時間延遲(TD)中；第三，對用戶uk參與生成的所有匿名集，按時段先后順序進行無重復采樣，生成相應的匿名集序列，并將結果保存到數據庫的序列匿名集表S中，S={S1,S2,…,Si,…,Sn}。生成匿名集序列的單一序列Si的數據結構如圖1所示。

圖1 連續查詢生成匿名集數據的單一數據結構

2 序列規則

序列規則挖掘任務是從給定數據庫中發現一個屬性的集合，在一定時間段上的一些對象都具有這些屬性。例如，有一個會員制文具店的銷售數據庫，其中對象表示顧客，屬性表示商品類別或品牌。該數據庫記錄了在一定時期內被每個顧客買走商品的信息。序列規則挖掘任務就是發現在一定時期內頻繁被顧客所購買商品的序列?！胺彩琴I了鉛筆刀的顧客中70%的人在一個月之內又購買了鉛筆”就是一個非常有代表性的序列規則。文具店可以利用這些模式安排促銷活動、商品訂貨周期等。

序列模式只包括“支持度”一個度量指標[13-15]，因此，基于序列模式的事件預測并不能對預測的準確性進行充分估計。關聯規則雖然有支持度和置信度兩個度量指標的約束，但是不考慮時間的先后順序。而序列規則克服了序列模式和關聯規則各自的缺點，擁有支持度和置信度兩個度量指標，并且考慮時間的先后順序。

現有的序列規則算法不能反映匿名集不確定的特性，因此現有的序列規則挖掘方法不能直接應用于匿名集序列數據。由此，提出基于雙向不可逆擴展的匿名集序列規則挖掘算法，解決上述兩個問題，以更好地應用于匿名集序列數據，為以后的推理攻擊分析打下基礎，以實現用戶的隱私安全保護。

3 基于雙向不可逆擴展的匿名集序列規則挖掘方法

3.1 基本定義

定義1(匿名集)：AS(Anonymous Set)主要包括匿名區域CR、匿名用戶集(UIDS)、查詢時間P，其中，AS={CR,UIDS,P}，CR={Cell1,Cell2,…,Cellm}，UIDS={U1,U2,…,Uk}。

定義2(匿名集序列)：SAS是由一系列AS組成的序列，可以表示為：SAS={AS1,AS2,…,ASm}，其中AS1,AS2,…,ASm按時間的先后順序發生。

定義3(匿名集序列規則)：匿名集序列規則表示為A?B，其中A,B代表兩個匿名集集合，且A∩B=?，A,B?I，且A或B中的匿名集不分先后順序，即同時發生。

(1)

定義5(匿名集序列規則的置信度)：匿名集序列規則的置信度是描述一個匿名集序列規則的有效性或“值得信賴性”的確定性度量。對于匿名集序列規則“{i}?{j}”，其置信度定義為：

(2)

3.2 算法描述

基于雙向不可逆擴展方法對匿名集數據進行挖掘，其中主算法是雙向不可逆擴展算法，同時，主算法中調用了兩個子算法。

3.2.1 主算法

在掃描匿名集序列數據庫時，將包含c項的序列編號(sid)記錄為sids_c，c項第一次在匿名集序列出現的位置記錄為firstOccurences_c，c項最后一次在匿名集序列出現的位置記錄為lastOccurences_c。sidsi:j和sidsj:i，分別表示匿名集序列規則{i}?{j}和規則{j}?{i}所在的序列編號集合。所以，不需要再次掃描數據庫，就可以生成所有大小為1*1的匿名集序列。

主算法：雙向不可逆擴展方法(Bidirectional Irreversible Growth)

輸入：序列中item的數據庫D。

輸出：經過雙向不可逆擴展算法得到的所有規則，以及每條規則對應的支持度和置信度。

子程序：規則生長左擴展(LEFTGROWTH)，規則生長右擴展(RIGHTGROWTH)。

參數：匿名集序列數據庫D，最小支持度閾值minsup，最小置信度閾值minconf。

(1)掃描匿名集序列數據庫D一次，計算每個項的支持度計數。生成所有滿足條件大小1*1、support(r)≥minsup的規則，并計算各規則的支持度。選擇項i和j，分別記錄i和j的firstOccurence和lastOccurence。

(2)在包含i和j的sid中循環，檢查i的firstOccurence是否在j的lastOccurence之前(由于在掃描數據庫時，所有item的firstOccurence和lastOccurence均被記錄過，所以該步驟運行速度很快，花費時間較少)。

(3)如果firstOccurence_i在lastOccurence_j之前，則當前的sid被添加到sidsi:j中。如果firstOccurence_j在lastOccurence_i之前，則當前的sid被添加到sidsj:i中。

(6)計算sup({i}?{j})/sup({i})，得到規則{i}?{j}的置信度。

(7)若sup({i}?{j})/sup({i})≥minconf，則輸出該規則{i}?{j}的支持度和置信度。

3.2.2 子算法1

子算法1：左擴展(LEFTGROWTH)。

輸入：待擴展的匿名集序列規則I?J(ruleIJ)。

輸出：經過左擴展后的匿名集序列規則。

參數：待擴展的匿名集序列規則ruleIJ，包含項集I的序列列表，包含I:J的序列列表(sidsI:J)，每個序列中項集J最后一次出現的位置結構(lastOccurences_J)。

(1)在sidsI:J中循環所有序列，每條匿名集序列中，從第一個項集開始掃描，直到項集J最后一次出現位置之前的一個項集。找到發生時間早于或等于項集I的項集中的所有項，用c表示。

(2)將項c添加到規則左邊，構成規則I∪{c}?J。

(4)對左擴展得到的規則，檢查該規則的左邊項集能否再次進行左擴展。若能，則調用LEFTGROWTH算法，進行左擴展。調用LEFTGROWTH算法，參數設置為規則I∪{c}?J、包含I∪{c}的序列列表(sidsIc)、包含I:J的序列列表(sidsI:J)、每個序列中J最后一次出現的位置(lastOccurences_J)。若不能，則進行步驟(5)。

(5)計算sup(I∪{c}?J)/sup(I)，得到規則I∪{c}?J的置信度。

(6)若sup(I∪{c}?J)/sup(I)≥minconf，那么輸出該規則。

3.2.3 子算法2

RIGHTGROWTH與LEFTGROWTH程序十分相似。但是，RIGHTGROWTH程序中，操作步驟多，有更多的參數，因為同時調用了RIGHTGROWTH與LEFTGROWTH。

子算法2：右擴展(RIGHTGROWTH)。

輸入：待擴展的匿名集序列規則I?J(ruleIJ)。

輸出：經過右擴展后的匿名集序列規則。

參數：待擴展的匿名集序列規則ruleIJ，包含項集I的匿名集序列(sidsI)，包含項集J的匿名集序列(sidsJ)，包含I:J的匿名集序列列表(sidsI:J)，每個匿名集序列中I第一次出現的位置(firstOccurences_I)，每個匿名集序列中J最后一次出現的位置(lastOccurences_J)。

(1)在sidsI:J中循環所有序列，每條序列中，從項集I第一次出現位置的后一個項集開始掃描，直到序列的最后一個項集。找到發生時間晚于或等于項集J的項集中的所有項c。

(2)將項c添加到規則右邊，構成規則I?J∪{c}。

(5)計算sup(I?J∪{c})/sup(I)，得到規則I?J∪{c}的置信度。

(6)若sup(I?J∪{c})/sup(I)≥minconf，那么輸出該規則。

4 實驗及結果分析

4.1 模擬生成實驗數據

根據2 612輛出租車上采集的具有時空屬性的GPS軌跡數據，以數秒為間隔連續采樣得到用戶軌跡信息，包含了每個用戶在每個采樣時刻的位置序列編號(VT_ID)、經緯度坐標值(經度：VT_LONG，緯度：VT_LAT)、速度(VT_SPEED)、當前時刻(VT_DATE)及狀態(VT_STATE)。

為了便于利用數據的時空特性進行模擬查詢的匿名集數據生成，需要對數據進行預處理，具體步驟如下：

(1)將EXCEL表格批量導入SQL數據庫；

(2)按時段分離整合數據，存儲在12個時段信息表中；

(3)空間隨機，即對用戶相同時段的不同軌跡點，只選取其中一個作為軌跡信息進行存儲，保存在12個空間隨機時段信息表中；

(4)劃分網格，將研究區域劃分為250*250個標準正方形空間網格；

(5)用戶隨機、時段隨機，生成匿名集數據，部分匿名集數據示例：56*55 56*54 -1 56*50 56*49 -1 58*55 58*54 -1 55*49 55*48 -1 57*51,57*50 -1 -2。

4.2 雙向不可逆擴展的序列規則挖掘

4.2.1 挖掘結果

根據雙向不可逆擴展的匿名集序列規則挖掘算法，對SPMF開源框架中的RULEGROWTH進行改造后，對4.1節中模擬生成的匿名集序列數據進行數據挖掘，并設置最小支持度閾值和最小置信度閾值分別為100和0.7。經過挖掘算法得到的17條匿名集序列規則及其支持度、置信度，如表1所示。

表1 挖掘出的匿名集序列規則

17條匿名集序列規則實際地圖表達如圖2和圖3所示。

圖2 17個匿名集序列規則與地理背景數據的疊加顯示(1)

圖3 17個匿名集序列規則與地理背景數據的疊加顯示(2)

4.2.2 隱私安全分析

根據表1，并結合圖2和圖3，可以發現LBS匿名查詢的運動規律。具體分析如下：

(1)LBS匿名查詢分布在兩個相互獨立的區域內。一個由漢府街與長白街交接處向洪武南路運動，另一個在中山東路、解放路和黃埔路交界處運動。

(2)匿名集序列規則1～7，由漢府街與長白街交界處106*184、106*185、106*186、105*184、105*185五個網格，向洪武南路的101*153和100*153網格運動。運動跨度較大，規律比較明顯。

(3)從圖2中可以看出，匿名集序列規則1～7涉及的網格，主要分布在新街口商業繁華區(東起漢府街、長白街，西至洪武南路；北起中山東路，南至淮海路)，該區域是南京市交通密集、人口密度最大的區域之一。因此上述規律可為該區域在交通高峰時的交通疏導提供一定的參考。

(4)從圖3中可以看出，基于匿名集序列規則的預測特性，也給用戶的位置隱私帶來更大風險：攻擊者可對進入或離開敏感時空區域的用戶進行時空推理分析，以實現更具威脅性的用戶隱私攻擊。

(5)圖2和圖3涉及的新街口商業圈位于南京市的中心區，是中國著名的商業中心，擁有近百年歷史，近百家世界五百強分支機構入駐。其中，涉及的隱私敏感區繁多，攻擊者可對進入或離開該區域的用戶進行更具威脅性的推理攻擊。

5 結束語

現有的隱私保護方法，沒有對大量匿名集數據進行分析，沒有對匿名集數據的可用性以及隱私保護安全性進行深入研究。因此，通過對匿名數據特性以及傳統序列規則挖掘方法的分析，提出了一種基于雙向不可逆擴展的匿名集序列規則挖掘方法，對挖掘出的序列規則涉及位置隱私的部分結合地圖進行了綜合分析。驗證實驗結果表明，所提算法可行有效，對于隱私保護的未來方向具有重要意義。下一步將對算法進行改進以更好適應匿名集數據，并重點研究基于匿名集數據的隱私推理攻擊以及相應的隱私保護算法。

[1] 趙文斌,張登榮.移動計算環境中的地理信息系統[J].地理與地理信息科學,2003,19(2):19-23．

[2] 彭志宇,李善平.移動環境下LBS位置隱私保護[J].電子與信息學報,2011,33(5):1211-1216.

[3] 張海濤,高莎莎,徐 亮.空時K-匿名數據的關聯規則挖掘研究[J].地理與地理信息科學,2012,28(6):13-16.

[4] Gedik B,Liu L.Location privacy in mobile systems:a personalized anonymization model[C]//Proceedings of ICDCS.[s.l.]:[s.n.],2005:620-629.

[5] Xu T,Cai Y.Feeling-based location privacy protection for location-based services[C]//ACM conference on computer and communications security.[s.l.]:ACM,2009:348-357.

[6] Mokbel M F,Chow C,Aref W G.The new casper:query processing for location services without compromising privacy[C]//Proceedings of VLDB.[s.l.]:[s.n.],2006:763-774.

[7] Ku Wei-Shinn,Zimmermann R,Peng Wen-Chih,et al.Privacy protected query processing on spatial networks[C]//Proceedings of ICDE workshops.[s.l.]:[s.n.],2007:215-220.

[8] 林 欣,李善平,楊朝暉.LBS中連續查詢攻擊算法及匿名性度量[J].軟件學報,2009,20(4):1058-1068.

[9] Xu T,Cai Y.Location anonymity in continuous location-based services[C]//Proceedings of the 15th annual ACM international symposium on advances in geographic information systems.[s.l.]:ACM,2007:39.

[10] Chow C Y,Mokbel M F.Enabling private continuous queries for revealed user locations[C]//Proceedings of SSTD.[s.l.]:[s.n.],2007:258-275.

[11] Chen J, Cheng R, Mokbel M,et al.Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data[J].The VLDB Journal,2009,18(5):1219-1240.

[12] Wang Yiming,Wang Lingyu,Fung B C M.Preserving privacy for location-based services with continuous queries[C]//Proceedings of ICC.[s.l.]:[s.n.],2009:1-5.

[13] 王 虎,丁世飛.序列模式挖掘研究與發展[J].計算機科學,2009,36(12):14-17.

[14] 汪林林,范 軍.基于Prefixspan的序列模式挖掘改進算法[J].計算機工程,2009,35(23):56-58.

[15] 常 鵬,陳 耿,朱玉全.一種分布式序列模式挖掘算法[J].計算機應用,2008,28(11):2964-2966.

Investigation on Anonymous Sequential Rules Mining Method with LBS Continuous Query

CHEN Ze-wei1,ZHANG Hai-tao2

(1.College of Telecommunications and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.College of Geographic and Biologic Information,Nanjing University of Posts and Telecommunications, Nanjing 210046,China)

With the deep development and wide use of Location-Based Services (LBS),privacy protection has become the key technology to be solved urgently in LBS.The temporal and spatialK-anonymity is the main type of LBS privacy protection,in which the availability of anonymous datasets and the security of privacy protection have not been involved so far.Aimed at this problem and found on a characteristic of spatial-temporal sequences in anonymous dataset,a mining algorithm of anonymity dataset sequence rules has been presented with bidirectional irreversible expansion,which has marked the position of item sets in the process of scanning the sequence database to guarantee mining mobile sequential rules at just one scan of sequence database.Experiments of data mining and result validation have been conducted.Result mined by the algorithm covers sensitive regions like military possessions,which has been proved to have important practical value for realizing LBS privacy protection and certain theoretical value for enriching the study in privacy protection data mining area.

location based service;location privacy protection;spatial temporalK-anonymity;sequence rules

2016-06-06

2016-09-15 網絡出版時間：2017-04-28

國家自然科學基金資助項目(41201465)

陳澤偉(1993-),女,碩士生,研究方向為移動大數據技術;張海濤,副教授,研究方向為移動智能地理信息系統。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.020.html

TP301

A

1673-629X(2017)06-0124-06

10.3969/j.issn.1673-629X.2017.06.026