【基于LB某的位置隱私保護(hù)分析11000字（論文）】

--第1章緒論1.1研究背景及意義眾所周知，現(xiàn)實(shí)世界是動(dòng)態(tài)變化的，存在大量的運(yùn)動(dòng)實(shí)體，如運(yùn)動(dòng)的飛機(jī)、車輛與行人，這些隨著時(shí)間演變的空間對象通常被稱為移動(dòng)對象。而隨著移動(dòng)定位技術(shù)和通信技術(shù)的不斷融合，以及位置相關(guān)服務(wù)、物聯(lián)網(wǎng)和智慧城市等應(yīng)用的不斷發(fā)展，移動(dòng)對象的軌跡數(shù)據(jù)獲取越來越簡單，這也造成了LBS技術(shù)的蓬勃發(fā)展。例如1989—1994年所部署的GPS系統(tǒng)在今天已經(jīng)在日常生活中被廣泛利用。用戶位置的可用性促使過去的種種設(shè)想成為現(xiàn)實(shí)，如基于數(shù)字地理地圖的自動(dòng)導(dǎo)航、地理社交網(wǎng)絡(luò)、根據(jù)給定的需求搜索位置等。各類軟件也迅速崛起，美團(tuán)、大眾點(diǎn)評、去哪兒網(wǎng)等可以幫助人們搜索出特定地點(diǎn)附近的酒店、電影院、景點(diǎn)門票等；滴滴打車、高德地圖、花小豬打車等可以幫助人們規(guī)劃適合自己的出行路線，同時(shí)幫助選擇出行使用的交通工具；微信、qq、新浪微博等都可以讓人們根據(jù)自己的當(dāng)前位置查看自己附近的人的狀態(tài)，包括發(fā)現(xiàn)周圍的用戶、自己與用戶間的距離、查看周圍人所發(fā)布的公開信息等；而悅跑圈、Keep、動(dòng)動(dòng)等都可以記錄人們的運(yùn)動(dòng)路徑、運(yùn)動(dòng)距離及運(yùn)動(dòng)時(shí)間等信息，同時(shí)可以幫助人們自己查看自己的健康情況。在這其中移動(dòng)用戶的位置、軌跡信息作為基于位置服務(wù)產(chǎn)生的數(shù)據(jù)信息，不僅能反映出移動(dòng)用戶的活動(dòng)軌跡，同時(shí)也能間接地體現(xiàn)出用戶自身的活動(dòng)路徑與自己所處環(huán)境中的交互關(guān)系。例如，出租車在一天中的行駛路徑，除了可以記錄這輛車在一天當(dāng)中的行駛路線，同時(shí)其中也蘊(yùn)含著一些隱秘的行為信息（比如加油地點(diǎn)、就餐地點(diǎn)及時(shí)間、乘客上下車位置等），使其區(qū)別于私家車，還能在很大程度上客觀反映較大范圍的城市路況，這也可見軌跡數(shù)據(jù)的重要性。但是，即使LBS在為人們的衣食住行帶來了極大好處，難道就沒有任何風(fēng)險(xiǎn)嗎？答案當(dāng)然是否定的，任何技術(shù)都是一把雙刃劍。LBS技術(shù)有好的一面，當(dāng)然也有不利的一面，因?yàn)樵谑褂肔BS過程中我們每個(gè)人的隱私信息都有被泄露的風(fēng)險(xiǎn)。具體而言，在LBS應(yīng)用中，用戶把自己的位置發(fā)送給LSP，LSP就會(huì)收集甚至非法使用用戶所提供的位置信息，也就可以輕松地得到用戶的隱私。對所有使用LBS服務(wù)的客戶來說，公開自己的所處地點(diǎn)都有自身隱私被披露的風(fēng)險(xiǎn)。在每個(gè)人的所處位置中都可以分析出目標(biāo)用戶的住址、工作位置、生活習(xí)慣等。并且根據(jù)科學(xué)調(diào)查后也看到了每個(gè)人日常行動(dòng)中都有著自身的規(guī)律。正因如此獲取用戶的地點(diǎn)坐標(biāo)不但是讓不法分子有掌握用戶當(dāng)前環(huán)境的風(fēng)險(xiǎn)，更重要的是有未來自身行動(dòng)軌跡被掌握的概率。并且由于移動(dòng)設(shè)備中的LBS應(yīng)用需要獲取用戶的實(shí)時(shí)位置，從而向其提供相應(yīng)的線上服務(wù)。比如，用戶需要尋找距當(dāng)前位置最近的商場，但是在這個(gè)過程中用戶所公布的地點(diǎn)信息就有被不法分子截獲的可能性，進(jìn)而暴露自己的行蹤。同時(shí)，有些用戶也不希望服務(wù)器知曉自己的確切位置，只要服務(wù)器能夠根據(jù)自己的大致位置提供相應(yīng)服務(wù)即可。為此，針對在線查詢這一方面出現(xiàn)了大量的隱私保護(hù)技術(shù)研究，這些技術(shù)的主要目的是保證攻擊者不會(huì)通過用戶的連續(xù)LBS查詢獲取用戶的行蹤。1.2國內(nèi)外研究現(xiàn)狀目前所說的隱私保護(hù)是指在用戶使用位置服務(wù)時(shí)，通過技術(shù)手段確保用戶的位置隱私信息不被泄露出去。自2003年，beresford首先提出了位置隱私的概念，自此對LBS隱私保護(hù)的研究開始提上日程。Ghinita從私有查詢和軌跡匿名兩個(gè)方面對位置隱私進(jìn)行了綜述，但沒有涉及隱私度量和查詢隱私；Krumm著重評述了匿名、模糊化隱私保護(hù)技術(shù)和一些利用位置數(shù)據(jù)幾何性質(zhì)的隱私侵犯算法，但沒有涉及系統(tǒng)結(jié)構(gòu)和查詢隱私；張學(xué)軍對位置隱私保護(hù)研究現(xiàn)狀與進(jìn)展進(jìn)行了綜述，闡述了當(dāng)前幾種典型的隱私保護(hù)技術(shù)的優(yōu)缺點(diǎn)；Kim通過一種kNN查詢處理算法優(yōu)化了隱私技術(shù)，有效保護(hù)數(shù)據(jù)隱私同時(shí)降低系統(tǒng)開銷?；魨槒膫鹘y(tǒng)關(guān)系數(shù)據(jù)隱私保護(hù)向時(shí)空方向拓展的角度對數(shù)據(jù)發(fā)布中的軌跡隱私保護(hù)和LBS中的軌跡隱私保護(hù)關(guān)鍵技術(shù)進(jìn)行了分析和比較，但沒有涉及查詢隱私；周長利等研究了LBS務(wù)器文體建構(gòu)隱私保護(hù)問題，對查詢服務(wù)質(zhì)量和安全性進(jìn)行了分析，提出了基于路網(wǎng)的近鄰查詢隱私保護(hù)方法；閆光輝在K匿名隱私保護(hù)法基礎(chǔ)上，針對推理攻擊位置熵的選取進(jìn)行量化研究，提高了隱私保護(hù)效果。關(guān)于位置隱私保護(hù)研究至今，國內(nèi)外的專家學(xué)者不斷提出各種技術(shù)方法，基于多個(gè)隱私保護(hù)手段，對位置隱私服務(wù)的復(fù)雜度、保密性、安全性、抗干擾性和準(zhǔn)確性等多方面的安全性能都有了極大的改善。同時(shí)采用多種保護(hù)技術(shù)，不僅有效的保護(hù)了數(shù)據(jù)隱私，降低系統(tǒng)開銷，提高了服務(wù)質(zhì)量，還拓寬了其應(yīng)用場景，尤其是在位置移動(dòng)終端上的應(yīng)用使位置隱私服務(wù)得以面向大眾，服務(wù)大眾。但是在面對當(dāng)今各種復(fù)雜環(huán)境，各種應(yīng)用服務(wù)需求，以及各種用戶種類，位置服務(wù)的安全性，保密性以及復(fù)雜度還無法完全滿足。尤其是在面對LBS系統(tǒng)時(shí)，其安全性和復(fù)雜度方面就存在明顯不足。宋成等[9]差分隱私法指的是抵御差分攻擊所采取的方法，近年來在國內(nèi)成為大家關(guān)注的熱點(diǎn)。差分隱私方法最早是Dwork在2006年針對隱私破壞提出的基于概率的隱私模型。LiuLing等人提出使用中值長度估計(jì)方法來估計(jì)用戶的軌跡長度，并生成既保護(hù)差異隱私又具有高效用的合成軌跡。HuaJingyu等人針對軌跡的差分隱私泛化算法，利用指數(shù)機(jī)制，根據(jù)不同點(diǎn)的距離來合并節(jié)點(diǎn)。之后他們提出了另一種不同的方式釋放泛化后的軌跡。Muhammad等人將差分隱私與軌跡泛化方法相結(jié)合，以保護(hù)敏感車輛軌跡的隱私，這不僅為車輛軌跡提供了不同的隱私預(yù)算，同時(shí)也為不同的軌跡提供了不等的保護(hù)程度。在軌跡隱私保護(hù)的幾種方法中，差分隱私法是目前研究最廣的方法，這種方法不需要對攻擊者所掌握的攻擊背景做出嚴(yán)格限制，允許攻擊者了解部分攻擊背景，但是差分隱私方法也存在一定缺陷：近年來對差分隱私的研究過于看重最終的保護(hù)效果，但忽視了為了保護(hù)所添加的噪聲強(qiáng)度過大導(dǎo)致數(shù)據(jù)可用性不足，導(dǎo)致失去保護(hù)的意義得不償失；此外現(xiàn)在的大部分研究追求保護(hù)效果但往往造成計(jì)算復(fù)雜度過大、時(shí)間相應(yīng)長，忽視了時(shí)間成本，這樣雖然加大了隱私保護(hù)程度但是卻造成了時(shí)間上的浪費(fèi)，因此，如何平衡隱私保護(hù)程度和數(shù)據(jù)可用性是本文的研究重點(diǎn)。第2章相關(guān)基本理論2.1隱私的概念隱私的意思就是我們自己、他人或者是公司或企業(yè)等希望對他人保密的秘密信息，這其中包括個(gè)人信息和公共信息。個(gè)人信息包括自己的家庭住址、工作地點(diǎn)、薪資水平、出行的交通工具等等。公共信息則包括一個(gè)公司的經(jīng)營狀況、年度計(jì)劃、財(cái)務(wù)報(bào)表等等。而無論是個(gè)人隱私還是公共隱私都是需要被保護(hù)的。2.1.1隱私的獲取獲取隱私信息主要有以下幾種方式：（1）通過視頻監(jiān)控：這種方式是日常生活中出現(xiàn)最多的一種，現(xiàn)在所有公共場所幾乎都裝有監(jiān)控?cái)z像頭，比如學(xué)校、銀行、醫(yī)院、路口等等，這些攝像頭在很大程度上能保護(hù)人們的隱私安全，但是這種方式的弊端就是當(dāng)監(jiān)控所錄下的影像資料被不法分子所截獲后，將會(huì)給政府和人民帶來無法挽回的損失。（2）通過信息攔截：在當(dāng)今社會(huì)，人們之間溝通交流一般都會(huì)采用打電話，收發(fā)信息、郵件等方式，因此如果這些信息被攔截將給人們造成巨大的損失和傷害。（3）通過信息匯集：現(xiàn)在很多人都會(huì)通過爬蟲等方式對信息進(jìn)行收集匯總，之后對這些信息分析得出所需要的隱私信息，匯總的信息越多越有可能得到自己想要的秘密信息。（4）通過信息分析：現(xiàn)在很多公司都有體量很大的用戶，這些用戶往往會(huì)給公司帶來巨大的價(jià)值，所以諸多公司都對用戶的信息進(jìn)行分析，從而可以制定出符合公司發(fā)展的戰(zhàn)略規(guī)劃。（5）通過信息跟蹤：在以前如果想知道一個(gè)人的行動(dòng)軌跡最簡單的辦法就是跟蹤這個(gè)人，在現(xiàn)在我們每個(gè)人每天在上網(wǎng)了解信息的過程中也會(huì)留下自己的痕跡，這有時(shí)也會(huì)被有心之人利用，跟蹤到我們自身的隱私信息。2.1.2隱私泄露的類型攻擊者可以獲取到我們的隱私信息原因就是我們在不經(jīng)意間泄露了自己的全部或部分隱私信息，這主要包括以下幾種：（1）精確泄露：精準(zhǔn)泄露隱私是所有泄露類型中危害最大的，這會(huì)讓攻擊者完全掌握他們所需的隱私信息因此這是我們最不愿看到的情況。（2）范圍泄露：這種泄露方式所產(chǎn)生的危害性要小于精確泄露，這種是攻擊者掌握用戶的一定隱私信息范圍，根據(jù)范圍推斷用戶的隱私信息，范圍越小所得出的信息越精確。（3）模糊猜測：模糊猜測指的是攻擊者掌握一條或兩條用戶的其他信息，從而猜測想要得到的信息。比如攻擊者知道了用戶每天都做129路公交車，就可以猜測用戶家住在129線路上的A、B或C小區(qū)。這種猜測方法準(zhǔn)確性比較低，有價(jià)值的隱私信息暴露概率較小。（4）逆向分析：逆向分析是指通過結(jié)果反向推斷，從而得到信息的范圍。比如攻擊者了解到用戶每天上下班都不會(huì)做地鐵2號線，那么可以反向推測出用戶不住在地鐵2號線附近的樓盤。2.2位置隱私保護(hù)的基本概念2.2.1LBS技術(shù)在這里舉兩個(gè)例子。第一個(gè)例子是國外的Foursquare應(yīng)用程序。Foursquare希望用戶可以積極分享自己的位置、自己所處的環(huán)境等基本信息。到了后期Foursquare發(fā)展成了一個(gè)應(yīng)用程序，其根據(jù)用戶的歷史瀏覽記錄和歷史登記記錄，提供圍繞用戶當(dāng)前位置的個(gè)性化推薦，如圖2.1所示。圖2.1Foursquare中圍繞用戶當(dāng)前位置的個(gè)性化推薦可以被看作是一個(gè)基于現(xiàn)實(shí)生活的大富翁，每一個(gè)置身其中的用戶都通過手機(jī)網(wǎng)絡(luò)記錄自己的足跡。當(dāng)用戶經(jīng)常光顧某家酒店，并且每次都簽到，就有可能獲得星級用戶的稱號，或者用戶經(jīng)常四處游歷，也許就可以得到一個(gè)“冒險(xiǎn)家”的勛章。Foursquare不是僅僅可以簽到，它對于用戶而言更為重要的作用是幫助用戶找到自己的朋友，并且了解他們在干什么。第二個(gè)例子是在我國使用率非常高的高德地圖，它在我國的地圖導(dǎo)航方面始終處于領(lǐng)先的地位。同時(shí)高德地圖提供了地圖瀏覽、在線導(dǎo)航、出行查詢等基本功能，如圖2.2所示。圖2.2高德地圖的基本功能展示對一個(gè)地圖應(yīng)用，位置查詢和導(dǎo)航服務(wù)應(yīng)該是其最基本、也是用戶最在意的功能，我們可以直接在高德地圖應(yīng)用程序的首頁輸入最想去的地點(diǎn)，然后其會(huì)基于用戶的位置提供出行選項(xiàng)和出行路線。目前，高德地圖還集成了打車、公交、騎行、步行等多種選項(xiàng)，為用戶提供更好的使用體驗(yàn)。以上是LBS應(yīng)用的兩個(gè)直觀例子，下面介紹LBS技術(shù)的組成。圖2.3顯示了LBS技術(shù)的組成。圖2.3LBS技術(shù)的組成該技術(shù)使用先進(jìn)的移動(dòng)設(shè)備接入互聯(lián)網(wǎng)和地理信息系統(tǒng)使得互聯(lián)網(wǎng)和移動(dòng)地理信息系統(tǒng)成為可能。同時(shí)，空間數(shù)據(jù)庫在網(wǎng)絡(luò)上的應(yīng)用，促成了網(wǎng)頁地理信息系統(tǒng)。這些技術(shù)的結(jié)合形成了LBS，其基本系統(tǒng)架構(gòu)如圖2.4所示，包括移動(dòng)設(shè)備、定位系統(tǒng)、位置提供服務(wù)商和通信網(wǎng)絡(luò)。下面將詳細(xì)地描述每個(gè)組件。圖2.4LBS的基本系統(tǒng)架構(gòu)（1）移動(dòng)設(shè)備：它是移動(dòng)用戶攜帶的移動(dòng)對象，可以用來請求各種服務(wù)并向移動(dòng)服務(wù)提供商發(fā)送所需的信息。如今，被廣大用戶使用最多的就是自身可以導(dǎo)航定位的智能手機(jī)。（2）定位系統(tǒng)：該系統(tǒng)允許移動(dòng)設(shè)備在本地自動(dòng)確定其位置。確定位置的方法有很多，如可以通過導(dǎo)航定位系統(tǒng)或移動(dòng)無線電系統(tǒng)完成定位，其中移動(dòng)無線電系統(tǒng)能確定移動(dòng)用戶所在的蜂窩網(wǎng)絡(luò)，從而知曉移動(dòng)用戶的所在位置。（3）LSP：可以利用用戶在移動(dòng)設(shè)備上所提交的所處地點(diǎn)，從而幫助用戶進(jìn)行位置查詢以及休閑娛樂等多項(xiàng)服務(wù)，包括但不限于信息咨詢、出行規(guī)劃、美食尋找、實(shí)時(shí)公交信息等。（4）通信網(wǎng)絡(luò)：最后需要在系統(tǒng)組件之間建立一個(gè)通信網(wǎng)絡(luò)，以便實(shí)現(xiàn)它們之間的信息交換。2.2.2位置服務(wù)的應(yīng)用場景目前，LBS幾乎覆蓋了人們的生活的方方面面。這里介紹幾種典型的應(yīng)用場景，分別是基于位置的興趣點(diǎn)檢索服務(wù)、基于位置的導(dǎo)航服務(wù)、基于位置的社交網(wǎng)絡(luò)服務(wù)和基于位置的運(yùn)動(dòng)服務(wù)。（1）基于位置的興趣點(diǎn)檢索服務(wù)：一些主流的信息檢索類軟件，如美團(tuán)、攜程旅行、去哪兒旅行等眾多軟件都是基于位置的興趣點(diǎn)檢索服務(wù)。每個(gè)用戶都可以在這些軟件上找到固定區(qū)域內(nèi)的自己想查詢的內(nèi)容，如美食、住宿和娛樂場所等。除了能看到相關(guān)的推薦內(nèi)容外，還可以檢測到其他用戶的使用內(nèi)容，如用戶評價(jià)、使用體驗(yàn)等。（2）基于位置的導(dǎo)航服務(wù)：現(xiàn)在人們開始越來越依賴一些出行類軟件，如谷歌地圖、哈啰出行、嘀嘀打車等軟件。當(dāng)用戶在利用這些服務(wù)時(shí)，必須不斷地向服務(wù)商報(bào)告自身準(zhǔn)確的位置，而服務(wù)商便根據(jù)所搜集到的信息為用戶規(guī)劃出行路線及出行所需的交通工具等。（3）基于位置的社交網(wǎng)絡(luò)服務(wù)：現(xiàn)在人們每時(shí)每刻都在使用一些社交軟件，如微信、陌陌、soul等都是幫助人們建立社交圈子提供平臺。附近區(qū)域檢索服務(wù)是指用戶可以基于自身的實(shí)時(shí)位置查看周圍的地理社交信息，如看到自己周圍的用戶，方便用戶建立新的朋友圈；而簽到服務(wù)則是用戶可以在任何一個(gè)有實(shí)際意義的地點(diǎn)簽到，服務(wù)商為用戶提供自己所簽到地點(diǎn)附近的其他相關(guān)信息，并將該位置信息通知其朋友。通過這類軟件，好友之間可以相互了解對方最近的生活狀態(tài)，從中發(fā)現(xiàn)共同愛好。（4）基于位置的運(yùn)動(dòng)服務(wù)：現(xiàn)在一些運(yùn)動(dòng)達(dá)人都會(huì)使用一些運(yùn)動(dòng)軟件，如Keep、悅跑圈等都是廣大運(yùn)動(dòng)愛好者的選擇。用戶在開啟這些app后，這些app便可以實(shí)時(shí)記錄已經(jīng)運(yùn)動(dòng)的步數(shù)和距離（部分軟件需配合運(yùn)動(dòng)手環(huán)使用），同時(shí)可以建立每日步數(shù)目標(biāo)，督促用戶進(jìn)行運(yùn)動(dòng)，并且有些app中帶有步數(shù)排行榜，可以讓用戶看到自己朋友的運(yùn)動(dòng)狀態(tài)，從而幫助用戶建立運(yùn)動(dòng)友誼。在此類服務(wù)中，服務(wù)商可以獲得用戶完整的運(yùn)動(dòng)軌跡。以上四類基于位置服務(wù)的應(yīng)用已經(jīng)深入到了人們的日常生活中，為人們的衣食住行提供了極大的便利。除此之外，還有一些基于位置服務(wù)的應(yīng)用場景，如基于位置的廣告推送服務(wù)、基于位置服務(wù)的游戲等。第3章基于LBS的位置隱私保護(hù)方法3.1差分隱私保護(hù)模型3.1.1差分隱私概念差分隱私的保護(hù)模型在2006年被首次提出，差分隱私的提出主要目的是針對數(shù)據(jù)庫發(fā)布數(shù)據(jù)所產(chǎn)生的數(shù)據(jù)泄露問題。經(jīng)過差分隱私保護(hù)方法處理得到的數(shù)據(jù)集對單個(gè)數(shù)據(jù)的屬性應(yīng)該是不敏感的，這可以幫助我們抵御差分攻擊。例如我們共發(fā)布了100條軌跡，但是即使攻擊者掌握了其中的99條，但是依然無法用做差的形式推測出最后一條軌跡。差分隱私的保護(hù)方法依賴于臨近數(shù)據(jù)庫，因此在這里我們先給出臨近數(shù)據(jù)庫的基本定義。定義3.1鄰近數(shù)據(jù)集：已知數(shù)據(jù)集和，如果向中添加或刪除一條記錄獲得數(shù)據(jù)集，即或，則和被認(rèn)為是一對鄰近數(shù)據(jù)集，如表3.1和表3.2中的兩個(gè)數(shù)據(jù)集就是臨近數(shù)據(jù)集。表3.1用戶的購買行為U1{A、B、C、D}U2{A、C、F}U3{B、F、G}U4{B、C}表3.2用戶的購買行為U1{A、B、C、D}U2{A、C、F}U3{B、F、G}接下來我們給出差分隱私的定義：定義3.2差分隱私：隨機(jī)算法滿足差分隱私的條件，同時(shí)也存在隨意一組鄰近數(shù)據(jù)集和，對于隨意一個(gè)輸出，都有這一約束： (3.1)其中表示隱私泄露的風(fēng)險(xiǎn)，叫做隱私預(yù)算參數(shù)，用來衡量隱私保護(hù)水平，越小，保護(hù)效果越好。定義3.3-差分隱私：對于任意一對數(shù)據(jù)集和，如果這一組數(shù)據(jù)集中最多只差一個(gè)元素，并且滿足： (3.2)那么對于滿足差分隱私，當(dāng)時(shí)，為差分隱私。若想讓數(shù)據(jù)得到差分隱私保護(hù)通常是通過向數(shù)據(jù)集中添加噪聲，但是如果加入噪聲量過大，就會(huì)導(dǎo)致數(shù)據(jù)的可用性較差；同樣如果所加的噪聲量太小，則無法起到保護(hù)效果，因此為了分辨加入噪聲量的多少，于是在這里我們引入全局敏感度的概念：定義3.4全局敏感度：對一個(gè)函數(shù)，，其中是數(shù)據(jù)集，是一個(gè)維的實(shí)數(shù)向量，表示查詢結(jié)果。然后查詢函數(shù)對一對臨近數(shù)據(jù)集和的全局敏感度是，記為，那么 (3.3)其中是和的1-階范數(shù)距離。全局敏感度由函數(shù)自身的特性決定，其表示的是函數(shù)的輸入數(shù)據(jù)集中任意刪除一條數(shù)據(jù)時(shí)，算法的輸出結(jié)果的變化大小。3.1.2加噪機(jī)制對于數(shù)據(jù)進(jìn)行差分隱私保護(hù)的基本原理就是向原始數(shù)據(jù)集中加入噪聲，通過噪聲讓改變數(shù)據(jù)，最終達(dá)到保護(hù)數(shù)據(jù)的目的。在差分隱私方法中最常使用的分別為Laplace加噪機(jī)制和指數(shù)加噪機(jī)制。（1）Laplace機(jī)制Laplace機(jī)制指向原始數(shù)據(jù)中添加服從Laplace分布的隨機(jī)噪聲，選取任意數(shù)據(jù)處理函數(shù)，當(dāng)隱私保護(hù)方法經(jīng)過隱私處理步驟后的所得到最終集合滿足如下約束時(shí)： (3.4)該處理過程中的保護(hù)算法符合差分隱私約束，每個(gè)之間不存在交叉關(guān)系。拉普拉斯機(jī)制多適用于數(shù)值型的輸出，例如假設(shè)醫(yī)院中存在三種疾病的病人，現(xiàn)在已知這三種疾病病人的平均年齡，現(xiàn)利用拉普拉斯機(jī)制對平均年齡加噪，如表3.3所示表3.3差分隱私機(jī)制病癥平均年齡糖尿病50.05852.58649.03150.105高血壓50.08654.70551.00550.250癌癥65.41462.94366.85265.243（2）指數(shù)機(jī)制與拉普拉斯噪聲機(jī)制不同的是，指數(shù)機(jī)制一般來說針對一個(gè)概率值的查詢，這里有一個(gè)函數(shù)將數(shù)據(jù)集作為基準(zhǔn)集，最終所得到的結(jié)果為，體現(xiàn)出了判斷數(shù)據(jù)的精度大小。如果函數(shù)QUOTEA采用滿足分布的方法進(jìn)行隱私處理后的輸出為，可以得到經(jīng)過該隱私處理函數(shù)加工后的服從于差分隱私約束。例如現(xiàn)在要查詢中國最好的大學(xué)是哪一所，以清華、東大和藍(lán)翔舉例，如表3.4所示。表3.4指數(shù)機(jī)制學(xué)校概率清華0.9990.3330.6280.993東大0.000040.3330.2710.006藍(lán)翔3*10^-70.3330.1010.0013.1.3組合定理但是在實(shí)際情況中，有許多問題都不會(huì)特別簡單，因此如果僅做一次差分隱私保護(hù)還無法解決問題，這時(shí)就必須多次利用差分隱私的保護(hù)方法。但是又由于隱私預(yù)算總是有限的，所以若想在所要求的隱私預(yù)算下便可以保護(hù)好需要保護(hù)的數(shù)據(jù)，就只能通過運(yùn)用組合性質(zhì)分配隱私預(yù)算，讓隱私預(yù)算可以更有效地發(fā)揮作用。組合定理又分為序列組合以及并行組合。定義3.5序列組合性質(zhì)：當(dāng)前在這里一共有個(gè)互不相同的差分隱私算法則為隱私預(yù)算，而由這個(gè)不同的算法經(jīng)過組合，最終成為新算法，提供差分隱私保護(hù)。利用序列組合性質(zhì)，我們便能在保護(hù)數(shù)據(jù)的隱私時(shí)更為靈活，可以將一個(gè)大的隱私算法劃分為多個(gè)子算法，進(jìn)而可以在所規(guī)定的隱私預(yù)算下更好地保護(hù)數(shù)據(jù)的隱私。例如，如果我們現(xiàn)在要對一個(gè)數(shù)據(jù)集進(jìn)行隱私保護(hù)，而這時(shí)能提供的隱私預(yù)算的強(qiáng)度為，在保護(hù)過程中所應(yīng)用的算法需要為，這時(shí)我們便能夠?qū)⑦@個(gè)算法分為兩個(gè)子算法，子算法分別是和，與此同時(shí)設(shè)定子算法與的隱私預(yù)算是與，同時(shí)應(yīng)該讓，這時(shí)兩個(gè)算法與如果分別為保護(hù)隱私提供了和的隱私預(yù)算，便能夠認(rèn)為算法符合差分隱私保護(hù)模型。定義3.6并行組合性質(zhì)[65-66]：當(dāng)前在這里一共有個(gè)互不相同的差分隱私算法，分別為隱私預(yù)算，當(dāng)將其分為個(gè)不相交的子集后，由這些算法和子集組合形成的新算法提供差分隱私保護(hù)。并行組合性質(zhì)所表達(dá)的意思是，若在差分隱私保護(hù)中需要處理的數(shù)據(jù)集間沒有交集，由這些子算法組合而成的新算法，便可以提供差分隱私保護(hù)，而這一算法所提供的保護(hù)水平是所有子算法中隱私預(yù)算最大的，如果一個(gè)算法所設(shè)定的隱私預(yù)算越大，證明所加入的噪聲越小，因此如果利用這一機(jī)制那么所提供的保護(hù)的隱私水平為所有算法中保護(hù)程度最差的一個(gè)。在對軌跡隱私保護(hù)的應(yīng)用中，我們所用到的通常是laplace機(jī)制。3.2清洗漂移點(diǎn)并選定停留點(diǎn)由于我們在日常生活中，需要被保護(hù)的隱私通常都是我們在某地做了某事，而做一件事情通常都需要我們在某地停留一段時(shí)間，因此在軌跡中無速度的點(diǎn)，也就是停留點(diǎn)就是我們所應(yīng)該重點(diǎn)關(guān)注的位置點(diǎn)。停留點(diǎn)的意思是用戶在某個(gè)區(qū)域內(nèi)沒有運(yùn)動(dòng)，停留了一段時(shí)間的坐標(biāo)點(diǎn)。停留點(diǎn)并不是單指軌跡中的某個(gè)點(diǎn)，而是由一組GPS點(diǎn)所構(gòu)成，同時(shí)具有一定的語義。用戶的停留點(diǎn)蘊(yùn)含著活動(dòng)信息，只有花一定時(shí)間用戶才能做一些有意義的事。同時(shí)因?yàn)閱为?dú)一個(gè)GPS點(diǎn)無法蘊(yùn)含任何信息，只有多個(gè)點(diǎn)共同組成一個(gè)集合才能具備某種意義。其次我們根據(jù)對軌跡數(shù)據(jù)分析后我們發(fā)現(xiàn)，在一條軌跡中當(dāng)用戶的運(yùn)動(dòng)速度較快時(shí)通常這段軌跡不需要被保護(hù)，而當(dāng)用戶的運(yùn)動(dòng)速度較慢時(shí)，往往在運(yùn)動(dòng)過程中會(huì)產(chǎn)生一些比較重要的軌跡點(diǎn)，而這部分軌跡點(diǎn)才是需要我們保護(hù)的。因此我們應(yīng)該將重點(diǎn)放在用戶的停留點(diǎn)上。定義3.7停留點(diǎn)[71]：停留點(diǎn)所表達(dá)的是在一個(gè)區(qū)域范圍內(nèi)，用戶所停留的時(shí)間超出了我們所定義的時(shí)間閾值。點(diǎn)集便是一個(gè)符合該定義的停留點(diǎn)，，，且其中，，。如圖3.2所示，表示一條GPS軌跡，其中且，則分別為停留點(diǎn)。圖3.2軌跡中的停留點(diǎn)但是由于在不同的應(yīng)用場景下，采集到的軌跡信息是不同的，同樣在不同場景下軌跡中位置信息的特點(diǎn)也是不同的。例如在開車過程中由于車載GPS不需要考慮電量的問題，同時(shí)由于駕車過程中始終在戶外，所以GPS信號始終都會(huì)存在。但是我們利用移動(dòng)設(shè)備所得到的行人步行便會(huì)出現(xiàn)不同情況，有時(shí)會(huì)出現(xiàn)信號丟失的情況，從而導(dǎo)致軌跡的采樣時(shí)間間隔不一，軌跡路線不準(zhǔn)確等問題。造成這些問題主要是因?yàn)椋菏紫热绻腥瞬叫羞M(jìn)入到一個(gè)建筑物內(nèi)時(shí)，有可能導(dǎo)致GPS信號較弱，所以會(huì)出現(xiàn)一些軌跡中的位置信息獲取不到的現(xiàn)象，因此導(dǎo)致一條軌跡的相鄰點(diǎn)時(shí)間間隔不一致；同時(shí)假如用戶自身所在建筑物與外界的交界點(diǎn)，也會(huì)導(dǎo)致用戶的位置信息不準(zhǔn)確，容易導(dǎo)致位置漂移的現(xiàn)象。第二由于移動(dòng)設(shè)備自身電量的要求，一些手機(jī)會(huì)關(guān)閉正在使用用戶位置的軟件，同時(shí)部分用戶出于各種原因也會(huì)主動(dòng)關(guān)閉軟件中的位置服務(wù)，這也會(huì)導(dǎo)致步行的位置點(diǎn)中容易造成部分點(diǎn)出現(xiàn)位置偏差。因此我們采取先清洗軌跡中偏離正常軌跡較多的點(diǎn)。由歷史經(jīng)驗(yàn)可知在日常生活中由于GPS信號的不穩(wěn)定造成的偏離點(diǎn)通常呈現(xiàn)角度小于15度的銳角，且時(shí)間較為短暫。同時(shí)為了避免一些軌跡中的用戶由于正常運(yùn)動(dòng)造成角度較小的軌跡的情況，我們決定引入時(shí)間閾值來界定。即假設(shè)在實(shí)際軌跡中下，用戶很難在3s之內(nèi)以某種交通方式造成角度較小的銳角軌跡。所以我們將角度和時(shí)間同時(shí)作為判定標(biāo)準(zhǔn)，將角度小于15度同時(shí)運(yùn)動(dòng)時(shí)間小于3s的位置點(diǎn)剔除，從而得到清洗后的新軌跡。如圖3.3所示為清洗偏移點(diǎn)前后的軌跡圖，可見在最上方的位置點(diǎn)由于角度較小，停留時(shí)間較短而被濾除，從圖中可以看出軌跡在經(jīng)過清洗之后所得到的軌跡更符合實(shí)際情況。圖3.3清洗偏移點(diǎn)前后軌跡圖3.3隱私約束加擾本文所提出SCSDP算法，在數(shù)據(jù)稀疏壓縮的基礎(chǔ)上利用差分隱私保護(hù)軌跡隱私。如圖3.4所示，這一算法主要分為五個(gè)部分，軌跡數(shù)據(jù)的清洗，停留點(diǎn)的判定，測量矩陣的構(gòu)建，差分隱私保護(hù)和重構(gòu)算法。與傳統(tǒng)算法有區(qū)別的是，本文提出的SCSDP算法目的不是全部重構(gòu)出數(shù)據(jù)矩陣，而是利用壓縮采樣后的數(shù)據(jù)集，設(shè)計(jì)一個(gè)差分隱私保護(hù)的模型。圖3.4SCSDP模型處理過程3.4.1測量矩陣的構(gòu)建根據(jù)對壓縮感知重構(gòu)算法的持續(xù)研究，Candes等人提出可以選擇高斯隨機(jī)矩陣，理由是高斯矩陣既有好的列獨(dú)立特征，滿足RIP條件，同時(shí)可以提升重構(gòu)數(shù)據(jù)的精確度。因此本文同樣利用高斯隨機(jī)測量和基于矩陣分解的方法相結(jié)合設(shè)計(jì)觀測向量，設(shè)計(jì)出既有比較高的重構(gòu)精度又能保證有較高可用性的觀測向量。假設(shè)為有著行和列的一個(gè)數(shù)據(jù)集，根據(jù)矩陣降維的辦法將變換成2個(gè)實(shí)數(shù)的集合與，。數(shù)據(jù)矩陣中的真實(shí)數(shù)據(jù)與行矩陣和列矩陣的關(guān)系為公式（3.7） (3.7)是該數(shù)據(jù)集中的真實(shí)數(shù)據(jù)，是重構(gòu)出的數(shù)據(jù)。為潛在壓縮空間的維度。為了將原始數(shù)據(jù)與之間的誤差損失降到最低，我們算出和恢復(fù)值間的差值，也就是公式（3.8）： (3.8)同時(shí)利用隨機(jī)梯度下降法讓誤差最小，即 (3.9)這時(shí)我們便可以算出局部最小值。同時(shí)保證和間誤差最小的同時(shí)，也能保證對數(shù)據(jù)的恢復(fù)值與真實(shí)數(shù)據(jù)基本相同，這就意味著我們可以保證有較高的信息精度。因此我們能夠?qū)⒃嫉木仃噳嚎s成潛在的特征向量，同時(shí)也能減少數(shù)據(jù)的損失，這樣也就可以得到更精確的值。同時(shí)由于我們要對恢復(fù)的值與實(shí)際的值間的損失度進(jìn)行評估，因此要根據(jù)正則化避免過擬合現(xiàn)象，本文建立下面的目標(biāo)優(yōu)化函數(shù)： (3.10)其中，表示的是正則化程度，為了防止過擬合測量數(shù)據(jù)，最后得到測量矩陣。3.3.2算法描述算法1軌跡數(shù)據(jù)清洗輸入：原始軌跡數(shù)據(jù)；輸出：清洗后軌跡數(shù)據(jù)；whiledofortodobeginifthenifthendelifthen;elseendendendend算法2判定停留點(diǎn)輸入：清洗后軌跡數(shù)據(jù)，時(shí)間閾值，距離閾值輸出：判定后軌跡數(shù)據(jù)；，whiledofortodobegin；；ifthenifthenfortodostay；endend；returnend算法3軌跡數(shù)據(jù)分解輸入：分組后軌跡數(shù)據(jù)，正則化參數(shù)，學(xué)習(xí)速率，測量維度；輸出：行潛在特征矩陣；//矩陣分解獲取最優(yōu)化while(abs(Optcur-Optlast)>epsilon)//接近最小閾，停止訓(xùn)練獲得最優(yōu)化foriinrange:forjinrange:;forin://在測量維度內(nèi)，對向量和進(jìn)行迭代更新;;endforendforendforendwhile算法4測量矩陣構(gòu)建輸入：分組后軌跡數(shù)據(jù)，正則化參數(shù)，學(xué)習(xí)速率，行特征矩陣，隨機(jī)高斯矩陣，測量維度；輸出：測量矩陣;//迭代訓(xùn)練獲得測量矩陣while(abs(Optcur-Optlast)>epsilon)//迭代終止獲得測量矩陣foriinrange:forjinrange:;forin:;endforendforendforendwhile算法5差分隱私數(shù)據(jù)發(fā)布輸入：分組后軌跡數(shù)據(jù)，測量矩陣，測量維度，差分隱私參數(shù);輸出：重構(gòu)數(shù)據(jù)集;隨機(jī)測量forinrange:forinrange:;;//最大投影系數(shù)對應(yīng)的位置;//根據(jù)最小二乘求得;//殘差迭代公式;endfor;//稀疏系數(shù)矩陣endfor3.5隱私數(shù)據(jù)發(fā)布可用性分析為了評價(jià)我們所提出的新算法對軌跡隱私的保護(hù)效果，在數(shù)據(jù)集的選取中選擇了Geolife項(xiàng)目中所發(fā)布的軌跡數(shù)據(jù)集。該數(shù)據(jù)集中共有18670條真實(shí)的用戶軌跡，也是目前所被應(yīng)用最多的數(shù)據(jù)集。因?yàn)樵谶@一數(shù)據(jù)集中部分軌跡數(shù)據(jù)的相鄰點(diǎn)時(shí)間過短，導(dǎo)致數(shù)據(jù)采樣點(diǎn)過多，相鄰軌跡點(diǎn)之間間距過小，因此本文提出在清洗軌跡數(shù)據(jù)后，每過5min記錄一次位置點(diǎn)從而構(gòu)造出用戶的行動(dòng)路徑。實(shí)驗(yàn)1SCSDP算法對軌跡的保護(hù)效果本組實(shí)驗(yàn)的目的是通過利用我們所提出的新算法對原始軌跡進(jìn)行加擾，進(jìn)而比較原始軌跡與進(jìn)行保護(hù)后所得到的新軌跡，從而可以直觀體會(huì)到SCSDP算法對軌跡的保護(hù)效果。圖3.5不同軌跡保護(hù)前與保護(hù)后的路徑我們設(shè)定為0.1，迭代次數(shù)為50次，在圖3.5中顯示出了對軌跡保護(hù)前后的軌跡路徑之間的差別，我們可以看出通過利用SCSDP算法可以讓原始軌跡的路徑做出一定改變，從而可以有效地隱藏需要被保護(hù)的軌跡隱私信息，對原始軌跡起到良好的保護(hù)效果。實(shí)驗(yàn)2不同的隱私約束方法對數(shù)據(jù)發(fā)布精確度的影響本組實(shí)驗(yàn)的目的是考察在滿足差分隱私的前提下，將本文提出的SCSDP算法與采用壓縮感知對恢復(fù)結(jié)果集進(jìn)行差分隱私加擾方法（LCSDP）、對軌跡進(jìn)行聚類后利用差分隱私保護(hù)的方法（DPK-up）和利用差分隱私對混合位置隱私保護(hù)方法（LPPDP）進(jìn)行對比，并分別對步行、騎自行車及開車的軌跡各取6組比較現(xiàn)軌跡與原始軌跡間的誤差及可用性。(a)步行軌跡(b)騎自行車軌跡(c)開車軌跡圖3.6不同算法對不同組別軌跡隱私保護(hù)度的比較4.結(jié)論本文通過清洗軌跡中的某些偏移軌跡點(diǎn)來提升軌跡的可用性，讓軌跡更能反映實(shí)際情況，同時(shí)選定軌跡的停留點(diǎn)，在加噪過程中重點(diǎn)對停留點(diǎn)進(jìn)行加噪，避免過度保護(hù)降低軌跡數(shù)據(jù)的可用性，并分別對不同交通方式分別測試，分析測試結(jié)果。針對差分隱私保護(hù)軌跡數(shù)據(jù)隱私時(shí)出現(xiàn)的查詢結(jié)果不理想、計(jì)算復(fù)雜度高等問題，提出了將壓縮感知與差分隱私相結(jié)合的算法，從而可以緩解數(shù)據(jù)稀疏性的問題；然后向其中加入拉普拉斯噪聲從而實(shí)現(xiàn)差分隱私；最后應(yīng)用基于正交匹配追蹤的重構(gòu)算法恢復(fù)重建數(shù)據(jù)矩陣。通過實(shí)驗(yàn)我們證明了所提算法可以在保護(hù)過程中提供好的保護(hù)效果，可以在不損害軌跡可用性的同時(shí)保護(hù)用戶隱私。參考文獻(xiàn)唐留朋,夏清國,王黎明.LBS的一種隱私保護(hù)模型[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(016):4159-4161.代仕芳,李燕,海凜.多因素融合的個(gè)性化位置推薦算法[J].計(jì)算機(jī)工程,2018,v.44;No.488(06):306-310+316.LiuC.ResearchandDevelopmentStatusofLBSPositioningTechnology[J].JournalofNavigationandPositioning,2013.KumarG,GamePS.SmartSecurityModelbyPredictingFutureCrimewithGISandLBSTechnology