伴隨著智能終端的不斷革新,基于位置數(shù)據(jù)的應(yīng)用通過分析收集到的位置數(shù)據(jù)可以提高服務(wù)質(zhì)量,但這些數(shù)據(jù)中往往涉及到敏感的個(gè)人信息。因此,位置數(shù)據(jù)在發(fā)布給第三方機(jī)構(gòu)之前需要進(jìn)行隱私保護(hù)。差分隱私技術(shù)不依賴于攻擊者所具有的相關(guān)背景知識(shí),能夠?yàn)槊舾袛?shù)據(jù)提供嚴(yán)格的隱私保證,更適宜應(yīng)用在數(shù)據(jù)的發(fā)布與查詢過程中。目前應(yīng)用差分隱私的位置數(shù)據(jù)發(fā)布算法盡管滿足了隱私保護(hù)要求,但由于過多的噪聲累加導(dǎo)致數(shù)據(jù)的可用性不高。為了解決此問題,本文提出兩種改進(jìn)方案。針對(duì)數(shù)據(jù)量小且數(shù)據(jù)分布較均勻的數(shù)據(jù)集,本文提出了基于閾值的位置數(shù)據(jù)發(fā)布算法。該算法在每層網(wǎng)格劃分結(jié)束后,隨機(jī)選取一個(gè)網(wǎng)格單元并查找其相鄰網(wǎng)格單元,計(jì)算當(dāng)前聚簇與每個(gè)相鄰網(wǎng)格單元之間的計(jì)數(shù)值方差。對(duì)方差小于指定閾值的網(wǎng)格單元進(jìn)行聚類,并向每個(gè)聚簇內(nèi)添加噪聲,然后將結(jié)果平均分配給聚簇內(nèi)的每個(gè)網(wǎng)格單元,借此減少了由噪聲累加產(chǎn)生的噪聲誤差問題。同時(shí),根據(jù)噪聲誤差與均勻假設(shè)誤差之間的關(guān)系給定了閾值的選取范圍。針對(duì)數(shù)據(jù)量大且均勻性較差的數(shù)據(jù)集,本文提出了基于平方和誤差的位置數(shù)據(jù)發(fā)布算法。該算法在每層網(wǎng)格劃分結(jié)束后,先向每個(gè)網(wǎng)格單元中添加噪聲并保留噪聲結(jié)果。然后,再根據(jù)每個(gè)... 

【文章來源】：大連海事大學(xué)遼寧省 211工程院校

【文章頁數(shù)】：61 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１．?１差分隱私技術(shù)對(duì)數(shù)據(jù)的處理過程??Ｆｉ．?１．１?Ｄｉｆｆｅｒｅｎｔｉａｌｒｉｖａｃｔｅｃｈｎｏｌｏｆｏｒ?ｄａｔａｒｏｃｅｓｓｉｎ

據(jù)發(fā)布??基于數(shù)據(jù)依賴的樹結(jié)構(gòu)劃分方法采用的代表性數(shù)據(jù)結(jié)構(gòu)是ＫＤ－樹，該結(jié)構(gòu)內(nèi)每個(gè)節(jié)??點(diǎn)都是一個(gè)基于Ａ維點(diǎn)的二叉樹結(jié)構(gòu)。數(shù)據(jù)劃分時(shí)，在維位置數(shù)據(jù)的集合中選擇具有??最大方差的維度ｔ然后選擇各區(qū)域內(nèi)數(shù)據(jù)計(jì)數(shù)的中值數(shù)ｍ作為劃分標(biāo)準(zhǔn)對(duì)集合進(jìn)行劃??分。得到兩個(gè)子集合后再創(chuàng)建一個(gè)節(jié)點(diǎn)用于存儲(chǔ)該區(qū)域內(nèi)位置數(shù)據(jù)點(diǎn)的計(jì)數(shù)值，并對(duì)子??集合遞歸的進(jìn)行劃分操作，直到所有子集合都不能再劃分為止。??圓／ｆｔ??０?２?４?６?８?１０?Ｖ＾７??（ａ）原始數(shù)據(jù)分布?（ｂ）選擇中位數(shù)進(jìn)行構(gòu)建??圖２．３?ＫＤ－樹構(gòu)建過程圖??Ｆｉｇ．?２．３?Ｃｏｎｓｔｒｕｃｔｉｏｎ?ｐｒｏｃｅｓｓ?ｄｉａｇｒａｍ?ｏｆ?ＫＤ－ｔｒｅｅ??圖２．３表示針對(duì)某二維空間（Ａ－２）中的位置數(shù)據(jù)構(gòu)建ＫＤ－樹的過程。對(duì)于６個(gè)二維??位置數(shù)據(jù)點(diǎn)：（２，?３）、（５，?４）、（９，?６）、（４，?７）、（８，?１）及（７，?２），分別計(jì)算所有數(shù)據(jù)點(diǎn)在??ｘ維和＾維上的方差，分別得到３９和２８．６３。由于ｘ維方差更大，按照ｘ維進(jìn)行劃分并??選出所有數(shù)據(jù)點(diǎn)在ｘ維上的中位數(shù)７，將數(shù)據(jù)點(diǎn)（７，?２）作為根節(jié)點(diǎn)。其次，按ｘ＝７可將??其余的數(shù)據(jù)分成左子樹和右子樹，左子樹中包含數(shù)據(jù)點(diǎn)（２，?３）、（５，?４）和（４，?７），右子樹??則是（９，?６）和（８，?１）。然后分別對(duì)左右子樹進(jìn)行遞歸操作，直到葉子節(jié)點(diǎn)。??采用ＫＤ－樹進(jìn)行劃分的經(jīng)典差分隱私算法為ＫＤ－ＳｔａｎｄａｒｄＰｌ。該算法中將隱私預(yù)算ｅ??分為兩部分和用于確定劃分的中位數(shù)，用于為各層節(jié)點(diǎn)添加??噪聲。由于葉子節(jié)點(diǎn)是查詢函數(shù)能訪問到的最小單位，釆用各層節(jié)點(diǎn)平均分配隱私預(yù)算??－１２－??

?大連海事大學(xué)碩士學(xué)位論文???４７．Ｓ－??４２．５?－??４０．０?－??３５?０??３２?５?－??－１２５?－１２０?－１１５?－１１０?－１０５??（ｃ）?Ｔｉｇｅｒ數(shù)據(jù)集??圖４．１數(shù)據(jù)集可視化??Ｆｉｇ．?４．１?Ｖｉｓｕａｌｉｚａｔｉｏｎ?ｏｆ?ｄａｔａｓｅｔｓ??４．?１．３評(píng)估度量??采用差分隱私技術(shù)進(jìn)行位置數(shù)據(jù)的發(fā)布，最終的發(fā)布結(jié)果是一組經(jīng)過噪聲擾動(dòng)后的??數(shù)據(jù)。由于噪聲具有隨機(jī)性，極有可能造成擾動(dòng)過度，從而降低數(shù)據(jù)的可用性，使數(shù)據(jù)??失去原本的研究意義。為了在隱私性與保護(hù)性之間進(jìn)行合理的權(quán)衡，需要為各個(gè)滿足差??分隱私的算法確定一個(gè)通用的準(zhǔn)則以便進(jìn)行有效性評(píng)估。??基于劃分的位置數(shù)據(jù)隱私保護(hù)算法，通常都是利用查詢結(jié)果的相對(duì)誤差對(duì)數(shù)據(jù)結(jié)果??的準(zhǔn)確性進(jìn)行衡量。對(duì)于一個(gè)查詢使用ＣＷ（０代表查詢結(jié)果的真實(shí)計(jì)數(shù)值，并使用??ＡＷ（０代表采用某種方法建立索引結(jié)構(gòu)來回答查詢的噪聲計(jì)數(shù)值，得出如下的相對(duì)誤差??公式：??ＲｅｌＥｒｒＪ＾〇ｔ２ｒＭ?ａｎ??ｍ＆ｘ｛〇ｒｉ（Ｑ＼ｐ］??其中，參數(shù)Ｐ的值為ｐ＝０．００ｉｘ網(wǎng)，ｉＶ代表數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)個(gè)數(shù)。此外，分母取兩??者的最大值是避免真實(shí)的計(jì)數(shù)查詢結(jié)果為０的情況。??在本文的實(shí)驗(yàn)過程中采用了三種查詢大�。�，込和込來模擬真實(shí)的使用情況，其??中查詢大小是通過原始數(shù)據(jù)來進(jìn)行表示。由于１度約等于７０英里，所以實(shí)驗(yàn)結(jié)果圖中??的（１，１），?（２，２）和（３，?３）分別表示?７０Ｘ７０?英里、１４０Ｘ?１４０?英里和?２１０Ｘ２１０??英里的査詢。對(duì)于三種查詢大小，均隨機(jī)生成６００個(gè)查詢區(qū)域，每次査詢結(jié)束計(jì)算相對(duì)??誤差，�。叮埃按蔚�


本文編號(hào)：3458747