陳澤偉，張海濤

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

LBS連續(xù)查詢的匿名序列規(guī)則挖掘方法研究

陳澤偉1，張海濤2

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

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

位置服務(wù)；位置隱私保護(hù)；時(shí)空K-匿名；序列規(guī)則

0 引 言

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

2003年，由Gruteser等提出的基于時(shí)空K-匿名的LBS隱私保護(hù)方法[3](簡(jiǎn)稱時(shí)空K-匿名)，以匿名數(shù)據(jù)的真實(shí)可用、方法實(shí)現(xiàn)簡(jiǎn)潔靈活以及更適合LBS移動(dòng)計(jì)算環(huán)境等特點(diǎn)，成為近年來研究的主流方向。時(shí)空K-匿名的性能優(yōu)化主要在快照查詢與連續(xù)查詢兩個(gè)方面展開?？煺詹樵儼?個(gè)方面：

(1)靈活設(shè)定隱私保護(hù)級(jí)別。文獻(xiàn)[4]提出了動(dòng)態(tài)感知移動(dòng)用戶時(shí)空分布設(shè)定K值的Clique-Cloak方法；文獻(xiàn)[5]提出了時(shí)空區(qū)域Footprint的概念，并基于Footprint設(shè)計(jì)了動(dòng)態(tài)設(shè)置更人性化的隱私級(jí)別的保護(hù)方法。

(2)增強(qiáng)型查詢標(biāo)識(shí)保護(hù)。時(shí)空K-匿名的匿名集與匿名查詢請(qǐng)求為1∶1關(guān)系，而Clique-Cloak方法要求匿名集的用戶均應(yīng)提出查詢請(qǐng)求，但Clique-Cloak方法采用無向圖結(jié)構(gòu)生成匿名集會(huì)產(chǎn)生計(jì)算量過大的問題，只適合較小K值的匿名保護(hù)。

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

(4)空間網(wǎng)絡(luò)與分布式傳感網(wǎng)的應(yīng)用，設(shè)計(jì)了適合道路網(wǎng)絡(luò)的時(shí)空K-匿名[7]。

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

為此，基于對(duì)匿名數(shù)據(jù)特性以及傳統(tǒng)的序列規(guī)則挖掘方法的分析，提出了一種基于雙向不可逆擴(kuò)展的匿名集序列規(guī)則挖掘方法，詳細(xì)描述了算法步驟。實(shí)驗(yàn)首先模擬生成匿名集序列數(shù)據(jù)，使用基于雙向不可逆擴(kuò)展方法的匿名集序列規(guī)則挖掘方法進(jìn)行數(shù)據(jù)挖掘，驗(yàn)證算法的有效性。通過結(jié)合實(shí)際地理環(huán)境數(shù)據(jù)的應(yīng)用效果，對(duì)實(shí)驗(yàn)結(jié)果的分析，發(fā)現(xiàn)傳統(tǒng)的時(shí)空K-匿名方法存在隱私保護(hù)安全漏洞問題，挖掘結(jié)果涉及多處軍事敏感區(qū)域，因此該算法對(duì)于分析隱私攻擊推理和用戶隱私安全保護(hù)研究領(lǐng)域有重要的意義。

1 時(shí)空K-匿名集序列數(shù)據(jù)

1.1 時(shí)空K-匿名

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

1.2 連續(xù)查詢生成匿名集序列數(shù)據(jù)

連續(xù)查詢[8]是由同一用戶連續(xù)兩次或多次提出的查詢內(nèi)容相同或高度相關(guān)的位置服務(wù)查詢。直接將快照查詢的匿名保護(hù)方法應(yīng)用于連續(xù)查詢，會(huì)引起位置標(biāo)識(shí)與查詢標(biāo)識(shí)隱私的泄露[9-15]。文獻(xiàn)[5,10]分別提出了利用初始匿名集作為整個(gè)連續(xù)查詢匿名集的Memorization方法與Plain KAA方法。但隨著匿名集中移動(dòng)對(duì)象的運(yùn)動(dòng)，匿名集的時(shí)空區(qū)域會(huì)擴(kuò)展或收縮，使得位置服務(wù)QoS下降與位置隱私暴露。

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

圖1 連續(xù)查詢生成匿名集數(shù)據(jù)的單一數(shù)據(jù)結(jié)構(gòu)

2 序列規(guī)則

序列規(guī)則挖掘任務(wù)是從給定數(shù)據(jù)庫(kù)中發(fā)現(xiàn)一個(gè)屬性的集合，在一定時(shí)間段上的一些對(duì)象都具有這些屬性。例如，有一個(gè)會(huì)員制文具店的銷售數(shù)據(jù)庫(kù)，其中對(duì)象表示顧客，屬性表示商品類別或品牌。該數(shù)據(jù)庫(kù)記錄了在一定時(shí)期內(nèi)被每個(gè)顧客買走商品的信息。序列規(guī)則挖掘任務(wù)就是發(fā)現(xiàn)在一定時(shí)期內(nèi)頻繁被顧客所購(gòu)買商品的序列。“凡是買了鉛筆刀的顧客中70%的人在一個(gè)月之內(nèi)又購(gòu)買了鉛筆”就是一個(gè)非常有代表性的序列規(guī)則。文具店可以利用這些模式安排促銷活動(dòng)、商品訂貨周期等。

序列模式只包括“支持度”一個(gè)度量指標(biāo)[13-15]，因此，基于序列模式的事件預(yù)測(cè)并不能對(duì)預(yù)測(cè)的準(zhǔn)確性進(jìn)行充分估計(jì)。關(guān)聯(lián)規(guī)則雖然有支持度和置信度兩個(gè)度量指標(biāo)的約束，但是不考慮時(shí)間的先后順序。而序列規(guī)則克服了序列模式和關(guān)聯(lián)規(guī)則各自的缺點(diǎn)，擁有支持度和置信度兩個(gè)度量指標(biāo)，并且考慮時(shí)間的先后順序。

現(xiàn)有的序列規(guī)則算法不能反映匿名集不確定的特性，因此現(xiàn)有的序列規(guī)則挖掘方法不能直接應(yīng)用于匿名集序列數(shù)據(jù)。由此，提出基于雙向不可逆擴(kuò)展的匿名集序列規(guī)則挖掘算法，解決上述兩個(gè)問題，以更好地應(yīng)用于匿名集序列數(shù)據(jù)，為以后的推理攻擊分析打下基礎(chǔ)，以實(shí)現(xiàn)用戶的隱私安全保護(hù)。

3 基于雙向不可逆擴(kuò)展的匿名集序列規(guī)則挖掘方法

3.1 基本定義

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

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

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

(1)

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

(2)

3.2 算法描述

基于雙向不可逆擴(kuò)展方法對(duì)匿名集數(shù)據(jù)進(jìn)行挖掘，其中主算法是雙向不可逆擴(kuò)展算法，同時(shí)，主算法中調(diào)用了兩個(gè)子算法。

3.2.1 主算法

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

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

輸入：序列中item的數(shù)據(jù)庫(kù)D。

輸出：經(jīng)過雙向不可逆擴(kuò)展算法得到的所有規(guī)則，以及每條規(guī)則對(duì)應(yīng)的支持度和置信度。

子程序：規(guī)則生長(zhǎng)左擴(kuò)展(LEFTGROWTH)，規(guī)則生長(zhǎng)右擴(kuò)展(RIGHTGROWTH)。

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

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

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

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

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

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

3.2.2 子算法1

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

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

輸出：經(jīng)過左擴(kuò)展后的匿名集序列規(guī)則。

參數(shù)：待擴(kuò)展的匿名集序列規(guī)則ruleIJ，包含項(xiàng)集I的序列列表，包含I:J的序列列表(sidsI:J)，每個(gè)序列中項(xiàng)集J最后一次出現(xiàn)的位置結(jié)構(gòu)(lastOccurences_J)。

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

(2)將項(xiàng)c添加到規(guī)則左邊，構(gòu)成規(guī)則I∪{c}?J。

(4)對(duì)左擴(kuò)展得到的規(guī)則，檢查該規(guī)則的左邊項(xiàng)集能否再次進(jìn)行左擴(kuò)展。若能，則調(diào)用LEFTGROWTH算法，進(jìn)行左擴(kuò)展。調(diào)用LEFTGROWTH算法，參數(shù)設(shè)置為規(guī)則I∪{c}?J、包含I∪{c}的序列列表(sidsIc)、包含I:J的序列列表(sidsI:J)、每個(gè)序列中J最后一次出現(xiàn)的位置(lastOccurences_J)。若不能，則進(jìn)行步驟(5)。

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

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

3.2.3 子算法2

RIGHTGROWTH與LEFTGROWTH程序十分相似。但是，RIGHTGROWTH程序中，操作步驟多，有更多的參數(shù)，因?yàn)橥瑫r(shí)調(diào)用了RIGHTGROWTH與LEFTGROWTH。

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

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

輸出：經(jīng)過右擴(kuò)展后的匿名集序列規(guī)則。

參數(shù)：待擴(kuò)展的匿名集序列規(guī)則ruleIJ，包含項(xiàng)集I的匿名集序列(sidsI)，包含項(xiàng)集J的匿名集序列(sidsJ)，包含I:J的匿名集序列列表(sidsI:J)，每個(gè)匿名集序列中I第一次出現(xiàn)的位置(firstOccurences_I)，每個(gè)匿名集序列中J最后一次出現(xiàn)的位置(lastOccurences_J)。

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

(2)將項(xiàng)c添加到規(guī)則右邊，構(gòu)成規(guī)則I?J∪{c}。

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

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 模擬生成實(shí)驗(yàn)數(shù)據(jù)

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

為了便于利用數(shù)據(jù)的時(shí)空特性進(jìn)行模擬查詢的匿名集數(shù)據(jù)生成，需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，具體步驟如下：

(1)將EXCEL表格批量導(dǎo)入SQL數(shù)據(jù)庫(kù)；

(2)按時(shí)段分離整合數(shù)據(jù)，存儲(chǔ)在12個(gè)時(shí)段信息表中；

(3)空間隨機(jī)，即對(duì)用戶相同時(shí)段的不同軌跡點(diǎn)，只選取其中一個(gè)作為軌跡信息進(jìn)行存儲(chǔ)，保存在12個(gè)空間隨機(jī)時(shí)段信息表中；

(4)劃分網(wǎng)格，將研究區(qū)域劃分為250*250個(gè)標(biāo)準(zhǔn)正方形空間網(wǎng)格；

(5)用戶隨機(jī)、時(shí)段隨機(jī)，生成匿名集數(shù)據(jù)，部分匿名集數(shù)據(jù)示例：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 雙向不可逆擴(kuò)展的序列規(guī)則挖掘

4.2.1 挖掘結(jié)果

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

表1 挖掘出的匿名集序列規(guī)則

17條匿名集序列規(guī)則實(shí)際地圖表達(dá)如圖2和圖3所示。

圖2 17個(gè)匿名集序列規(guī)則與地理背景數(shù)據(jù)的疊加顯示(1)

圖3 17個(gè)匿名集序列規(guī)則與地理背景數(shù)據(jù)的疊加顯示(2)

4.2.2 隱私安全分析

根據(jù)表1，并結(jié)合圖2和圖3，可以發(fā)現(xiàn)LBS匿名查詢的運(yùn)動(dòng)規(guī)律。具體分析如下：

(1)LBS匿名查詢分布在兩個(gè)相互獨(dú)立的區(qū)域內(nèi)。一個(gè)由漢府街與長(zhǎng)白街交接處向洪武南路運(yùn)動(dòng)，另一個(gè)在中山東路、解放路和黃埔路交界處運(yùn)動(dòng)。

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

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

(4)從圖3中可以看出，基于匿名集序列規(guī)則的預(yù)測(cè)特性，也給用戶的位置隱私帶來更大風(fēng)險(xiǎn)：攻擊者可對(duì)進(jìn)入或離開敏感時(shí)空區(qū)域的用戶進(jìn)行時(shí)空推理分析，以實(shí)現(xiàn)更具威脅性的用戶隱私攻擊。

(5)圖2和圖3涉及的新街口商業(yè)圈位于南京市的中心區(qū)，是中國(guó)著名的商業(yè)中心，擁有近百年歷史，近百家世界五百?gòu)?qiáng)分支機(jī)構(gòu)入駐。其中，涉及的隱私敏感區(qū)繁多，攻擊者可對(duì)進(jìn)入或離開該區(qū)域的用戶進(jìn)行更具威脅性的推理攻擊。

5 結(jié)束語

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

[1] 趙文斌,張登榮.移動(dòng)計(jì)算環(huán)境中的地理信息系統(tǒng)[J].地理與地理信息科學(xué),2003,19(2):19-23．

[2] 彭志宇,李善平.移動(dòng)環(huán)境下LBS位置隱私保護(hù)[J].電子與信息學(xué)報(bào),2011,33(5):1211-1216.

[3] 張海濤,高莎莎,徐 亮.空時(shí)K-匿名數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘研究[J].地理與地理信息科學(xué),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中連續(xù)查詢攻擊算法及匿名性度量[J].軟件學(xué)報(bào),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] 王 虎,丁世飛.序列模式挖掘研究與發(fā)展[J].計(jì)算機(jī)科學(xué),2009,36(12):14-17.

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

[15] 常 鵬,陳 耿,朱玉全.一種分布式序列模式挖掘算法[J].計(jì)算機(jī)應(yīng)用,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 網(wǎng)絡(luò)出版時(shí)間：2017-04-28

國(guó)家自然科學(xué)基金資助項(xiàng)目(41201465)

陳澤偉(1993-),女,碩士生,研究方向?yàn)橐苿?dòng)大數(shù)據(jù)技術(shù);張海濤,副教授,研究方向?yàn)橐苿?dòng)智能地理信息系統(tǒng)。

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