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

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

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

【學位級別】：碩士

【部分圖文】：

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

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

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


本文編號：3458747