【摘要】：差分隱私(Differential Privacy(DP))已經(jīng)成為目前最流行的隱私保護(hù)技術(shù)之一,它對(duì)隱私泄露能夠提供數(shù)學(xué)上嚴(yán)格的定量控制。近些年來關(guān)于差分隱私大量的研究不斷被提出,其主要作用是保護(hù)數(shù)據(jù)或者模型。其中以差分隱私為基礎(chǔ)的數(shù)據(jù)發(fā)布式算法,能夠?qū)⒃紨?shù)據(jù)集轉(zhuǎn)化為具有類似性質(zhì)的人工數(shù)據(jù)集,從而保護(hù)原始數(shù)據(jù)。另外,許多研究目的是提高在差分隱私保護(hù)下的數(shù)據(jù)挖掘模型效果。然而實(shí)現(xiàn)差分隱私需要引入噪聲,這會(huì)導(dǎo)致數(shù)據(jù)的分布損失或模型的精度損失,而這些損失對(duì)于對(duì)數(shù)據(jù)或模型有嚴(yán)格要求的工業(yè)界來說是不可接受的。為了提高差分隱私保護(hù)下模型的精度,以及嘗試實(shí)現(xiàn)差分隱私在工業(yè)系統(tǒng)中的應(yīng)用,本文分別從定量挖掘與定性分析的角度來研究差分隱私技術(shù)。定量挖掘方面,我們研究的是差分隱私用于保護(hù)決策樹模型,前人采取嵌入一層數(shù)據(jù)挖掘計(jì)算的方式將差分隱私應(yīng)用在決策樹模型上(每次操作生成兩層子樹),從而保護(hù)模型,防止模型的結(jié)構(gòu)被使用者逆推出來。我們采取嵌入兩層或兩層以上數(shù)據(jù)挖掘計(jì)算的方式實(shí)現(xiàn)帶有差分隱私保護(hù)的決策樹模型(每次操作生成三層或三層以上的子樹),當(dāng)子樹解空間過大時(shí)使用馬爾科夫鏈(Markov Chain Monte Carlo(MCMC))來模擬解空間的分布。定性分析方面,前人均是從定量挖掘的角度來研究差分隱私,即關(guān)注于提高模型的效果,本文從另一個(gè)新的角度定性分析出發(fā),研究差分隱私數(shù)據(jù)發(fā)布式算法對(duì)原始數(shù)據(jù)集屬性關(guān)系的影響。定性分析目的是研究數(shù)據(jù)的排行、模式或重要集合等,天然對(duì)噪聲有著更好的容納能力。我們設(shè)計(jì)了一個(gè)差分隱私定性分析框架,使用兩個(gè)典型的定性分析任務(wù)作為樣例,讓數(shù)據(jù)購買者能夠更加深入地了解原始數(shù)據(jù)集的屬性關(guān)系,從而更好地利用購買到的人工數(shù)據(jù)集,在這整個(gè)過程中原始數(shù)據(jù)的隱私不被泄露。本文的主要工作與貢獻(xiàn)如下:·前人將差分隱私以一層深度嵌入到?jīng)Q策樹模型中,我們提出了一個(gè)新的想法,將差分隱私以不同的深度嵌入到?jīng)Q策樹中,以提高模型的預(yù)測效果。·我們提出了使用窮舉搜索與馬爾科夫鏈的算法,能夠時(shí)間上有效率地將差分隱私以任意的深度地嵌入到?jīng)Q策樹模型中。·實(shí)驗(yàn)證明,隨著差分隱私嵌入深度的增加,決策樹模型的表現(xiàn)效果提高了,深度結(jié)合差分隱私與決策樹確實(shí)能夠提高模型預(yù)測準(zhǔn)確度。·與定量挖掘相比,定性分析天然地對(duì)噪聲有著更好的容納能力。我們首次進(jìn)行了差分隱私定性分析的研究,嘗試找到一種方式,將差分隱私應(yīng)用在工業(yè)系統(tǒng)中�！の覀兲岢隽艘圆罘蛛[私為基礎(chǔ)的定性分析框架,用于幫助數(shù)據(jù)購買者實(shí)現(xiàn)定性分析任務(wù),并得到結(jié)果的置信度。我們使用了兩個(gè)典型的定性分析任務(wù)(兩個(gè)分類器)作為樣例,來演示這個(gè)框架的應(yīng)用。·在公開與私有工業(yè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示,使用定性分析的框架,即使隱私預(yù)算ε很小(例如0.05),定性分析任務(wù)仍然能夠以很高的置信度來完成,差分隱私的定性分析有著更大的潛能去實(shí)現(xiàn)差分隱私在工業(yè)系統(tǒng)中的應(yīng)用。差分隱私是十分有效的隱私保護(hù)技術(shù),越來越受到人們的重視。本文選取定量挖掘中差分隱私與決策樹模型的結(jié)合,進(jìn)行算法上的改進(jìn)。另外從一個(gè)新的角度,定性分析來研究差分隱私在工業(yè)系統(tǒng)中應(yīng)用的可能性。希望本文的工作能夠?yàn)椴罘蛛[私在提高模型效果或工業(yè)應(yīng)用上帶來新的思路,為差分隱私技術(shù)的發(fā)展做出貢獻(xiàn)。
【學(xué)位授予單位】：上海交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP309
【圖文】：

作[21, 27]如何對(duì)決策樹實(shí)現(xiàn)差分隱私的，這種實(shí)現(xiàn)方式如圖3 1(a)所示。Stopping condition checkingInner splittingLeaf node label generationDatabaseCounting querywithOne layer structurequery withCounting querywith'max(no. of calculations in each branch) ' ' '(a) 前人工作Inner splitting with different depthsDatabase?Has inner node to split?YesSubtree queryStructure selectionIf leaf nodelabel generation'max(no. of calculations in each branch)''(b) 當(dāng)前工作圖 3 1 決策樹的差分隱私實(shí)現(xiàn)架構(gòu)Fig 3 1 DP implementation skeleton of decision tree在本次研究中，我們在前人工作的基礎(chǔ)上，對(duì)算法進(jìn)行了改進(jìn)。生成決策樹的過程中，分裂一個(gè)內(nèi)部節(jié)點(diǎn)時(shí)有著不同的選擇�？梢詢H僅分裂一個(gè)內(nèi)部節(jié)點(diǎn)來實(shí)現(xiàn)差分隱私(one-step computation)，也就是前人的工作。同樣的，可以考慮在這個(gè)內(nèi)部節(jié)點(diǎn)下生成一個(gè)三層子樹 (樹的生成算法每次分裂兩層)，更深層次的，還可以生成一個(gè)?

分隱私定量與定性保護(hù)研究 上海交通大學(xué)碩士學(xué)位論文等。直到，一顆樹在根節(jié)點(diǎn)下以最大深度直接生成，在一次生成整棵樹的過程中實(shí)現(xiàn)差分隱私 (所有的內(nèi)部分裂計(jì)算被視為一次計(jì)算)，這些新的分裂設(shè)想如圖3 2所示。這些新的算法被用來和前人的工作[21](one-step computation) 進(jìn)行比較，隱藏在數(shù)據(jù)庫的接口后面，所有的計(jì)算，包括內(nèi)部分裂和葉子節(jié)點(diǎn)的操作，被結(jié)合起來視為一次計(jì)算，設(shè)計(jì)的結(jié)構(gòu)如圖3 1(b)所示。因?yàn)檫@項(xiàng)工作關(guān)注于研究如何以不同的深度結(jié)合差分隱私和決策樹模型，不同于前人的工作[21, 27]，本次算法設(shè)計(jì)中并沒有做樹的剪枝。在接下來的章節(jié)中，將介紹這些過程細(xì)節(jié)上的實(shí)現(xiàn)。!(a) 一層嵌入 (前人工作)...... ...... ...... ...... ...............12(b) 兩層嵌入...... ...... ...... ...... ...............1(c) 三層嵌入...... ...... ...... ...... ...............1(d) 整棵樹嵌入圖 3 2 以不同的深度嵌入差分隱私到?jīng)Q策樹模型Fig 3 2 Embedding DP in DT with different depths3.2.2 打分函數(shù)在決策樹生成算法中，打分函數(shù) (Quality Function) 扮演著重要的角色，被用來作為選擇劃分屬性的衡量方法。它一般是基于幾種純度的衡量方法的

通大學(xué)碩士學(xué)位論文 第四章 定性而非定量: 實(shí)現(xiàn)差分隱私的工p-K(BTK) 和 Be Larger(BL) 分類器。穩(wěn)定意味著分類器處于一個(gè)收斂的狀態(tài)在后面的章節(jié)討論這個(gè)方面的細(xì)節(jié)。兩個(gè)分類器都被數(shù)據(jù)提供者構(gòu)建，并將數(shù)據(jù)購買者。對(duì)于 BTK 來說，人工數(shù)據(jù)集中某個(gè)屬性 的一些參數(shù) (例如息增益等) 作為輸入，分類器返回的是屬性 屬于原始數(shù)據(jù)集 top 個(gè)重要。另一方面，對(duì)于 BL 分類器來說，屬性 和 的相關(guān)參數(shù)作為輸入，分類屬性 對(duì)類標(biāo)簽的影響程度比屬性 大的概率。例如，在 BTK 中，一個(gè)相 (>0.5) 意味著，對(duì)于屬性 ，屬于原始數(shù)據(jù)集中 top 屬性的概率大于不屬性的概率，而不是 確定屬于 top 個(gè)重要屬性。這些概率 (置信度) 有助者判斷原始數(shù)據(jù)集屬性的重要性程度，從而能夠更好地利用購買到的人工4 1顯示了本次工作中相關(guān)名詞的簡稱。

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 熊平;朱天清;金大衛(wèi);;一種面向決策樹構(gòu)建的差分隱私保護(hù)算法[J];計(jì)算機(jī)應(yīng)用研究;2014年10期

2 張嘯劍;孟小峰;;面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J];計(jì)算機(jī)學(xué)報(bào);2014年04期

3 熊平;朱天清;王曉峰;;差分隱私保護(hù)及其應(yīng)用[J];計(jì)算機(jī)學(xué)報(bào);2014年01期

4 李欣海;;隨機(jī)森林模型在分類與回歸分析中的應(yīng)用[J];應(yīng)用昆蟲學(xué)報(bào);2013年04期

5 李楊;郝志峰;溫雯;謝光強(qiáng);;差分隱私保護(hù)k-means聚類方法研究[J];計(jì)算機(jī)科學(xué);2013年03期

6 李楊;溫雯;謝光強(qiáng);;差分隱私保護(hù)研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2012年09期

7 朱紹文,胡宏銀,王泉德,張大斌,黃浩,陸玉昌;決策樹采掘技術(shù)及發(fā)展趨勢[J];計(jì)算機(jī)工程;2000年10期

8 劉小虎,李生;決策樹的優(yōu)化算法[J];軟件學(xué)報(bào);1998年10期

本文編號(hào)：2763766