陳紅松，孟彩霞，劉書雨

（1.北京科技大學 計算機與通信工程學院，北京100083；2.鐵道警察學院，河南 鄭州450053）

致病基因關聯(lián)分析是全基因組關聯(lián)研究[1]（Genome-wide Association Studies，GWAS）中的一項分析DNA序列集以發(fā)現(xiàn)疾病遺傳基礎的流行方法，這項研究主要檢查特定患者群體的基因中數(shù)千個單核苷酸多態(tài)性位點（SNP）與疾病之間的相關度，對SNP進行評分，并根據(jù)這個評分對相關度較高的SNP排序.但對于GWAS發(fā)布的數(shù)據(jù)而言，即使是只發(fā)布統(tǒng)計數(shù)據(jù)，患者的疾病狀態(tài)也可以從每個SNP與疾病相關聯(lián)的統(tǒng)計檢驗中推斷出來，這使得患者的隱私面臨著泄露的風險.

目前已有許多研究人員研究使用差分隱私技術來解決這一問題，差分隱私保護技術是當前數(shù)據(jù)發(fā)布中最主要的隱私保護方法，它通過向查詢數(shù)據(jù)中添加噪聲來干擾攻擊者泄露原始數(shù)據(jù)的目的，從而達到隱私保護效果.差分隱私保護技術的應用使得數(shù)據(jù)發(fā)布的效率得到了很大的提高，但為了滿足差分隱私保護要求需要注入過高的噪聲，影響數(shù)據(jù)的正確性和可用性，最終導致數(shù)據(jù)效用降低.為了解決這一問題，本文提出了一種基于EWT變換的差分隱私保護方法，不僅依賴于注入噪聲，還通過適當過濾部分噪聲實現(xiàn)隱私保護與數(shù)據(jù)可用性的合理折中，由于只是針對噪聲的注入、變換和過濾，所以不會還原出用戶隱私信息.主要研究目的是在致病基因相關度研究中，使用差分隱私保護患者隱私的同時，降低由于添加差分隱私噪聲帶來的誤差.

1 相關技術

1.1 差分隱私

1.1.1 定義

差分隱私的主要思想是給數(shù)據(jù)集中的每條記錄都添加一個噪聲，使在一個數(shù)據(jù)集上計算的給定統(tǒng)計量的結果類似于在另一個任意的數(shù)據(jù)集上計算的相同的統(tǒng)計量，以此來把數(shù)據(jù)泄露的概率控制在一定的范圍內(nèi)，從而達到隱私保護的目的.滿足以上兩個數(shù)據(jù)集中最多只有一條記錄不同，即如果一個數(shù)據(jù)庫是另一個數(shù)據(jù)庫的正確子集，那么較大的數(shù)據(jù)庫只比另一個多包含一行數(shù)據(jù).

本文專注于保護表型數(shù)據(jù)，因此對差分隱私的定義進行略微修改，如定義1.

定義1[1]設F是一個隨機函數(shù)，它接受一個n×m的基因型矩陣D和一個n維表型向量y，并輸出結果F（D，y），Ω表示隨機函數(shù)F的輸出范圍，那么隨機函數(shù)F對于任意的ε＞0，滿足ε-表型差分隱私.對于任意的基因型矩陣D，任意的表型向量y，y′∈{0，1}n（y與y′僅有一個坐標不同）以及任意的輸出集合S?Ω，我們規(guī)定了ε-表型差分隱私：

ε為隱私保護預算，由數(shù)據(jù)擁有者公開定制，ε的值越接近0表示差分隱私保護級別越高，但同時這也意味著F的輸出越不準確.

這與差分隱私的通常定義不同，因為在差分隱私中D通常不是固定的，而我們假設基因型矩陣D是固定的.直觀地，以上定義表明，當一個人患有疾病時，F(xiàn)返回的結果在統(tǒng)計上與他們沒有疾病時返回的結果沒有區(qū)別.

1.1.2 差分隱私強度影響參數(shù)

1）隱私保護預算[2].隱私保護預算ε一般體現(xiàn)了F所能提供的隱私保護程度.因為ε取值越小，隱私保護程度就越高，反之亦然，因此選取多大隱私保護預算，ε是一項非常重要的參數(shù)，需要根據(jù)具體需求定義ε的取值范圍.

2）敏感度[3].敏感度是一個衡量加入噪聲量的參數(shù)信息，指的是對數(shù)據(jù)集中任意刪除操作對結果所造成的最大改變力度.

定義2全局敏感度（Global Sensitivity）.設有函數(shù)f：D→Rd，輸入為一數(shù)據(jù)集，輸出為一d維實數(shù)向量.對于任意的鄰近數(shù)據(jù)集D和D′，若滿足公式（2），

則GSf稱為函數(shù)f的全局敏感度，全局敏感度用于量化表示對原始數(shù)據(jù)集D增加或刪除一條記錄時，對于整個算法f輸出結果的最大影響.其中，‖f（D）-f（D′）‖1是f（D）和f（D′）之間的1階范數(shù)距離.函數(shù)本身決定了全局敏感度的選取，函數(shù)不同，全局敏感度也不相同.

1.1.3 實現(xiàn)機制

面向致病基因相關度研究分析中，差分隱私的實現(xiàn)主要采用3種實現(xiàn)機制，包括拉普拉斯機制、指數(shù)機制以及高斯機制.

1）拉普拉斯機制.

定義3拉普拉斯機制（Laplace Mechanism）[4].給定數(shù)據(jù)集D，設有函數(shù)f：D→Rd，其敏感度為Δf，那么隨機算法K（D）=f（D）+Y提供ε-差分隱私保護，其中Y～Lap（Δf/ε）為隨機噪聲，服從尺度參數(shù)為Δf/ε的Laplace分布，其中Lap（Δf/ε）概率密度函數(shù)為：

根據(jù)公式（3）可得Laplace分布的期望值為0，方差為2λ2.

2）指數(shù)機制.

定義4指數(shù)機制（Exponential Mechanism）[5].設隨機算法K輸入為數(shù)據(jù)集D，輸出為一實體對象r∈Range，q（D，r）為可用性估價函數(shù)，Δq為函數(shù)q（D，r）的敏感度.若算法K滿足輸出為r的概率與exp（εq（T，r）/2S（q））成比例關系，那么算法K滿足服從指數(shù)機制的ε-差分隱私.

3）高斯機制（Gauss Mechanism）.與拉普拉斯機制相類似，同樣是通過向查詢請求結果f（T）中添加服從高斯分布的噪聲η，得到f（T）+η來實現(xiàn)ε-差分隱私保護，其概率密度函數(shù)為：

根據(jù)公式（4）可得高斯分布的期望值為μ，方差為2λ2，其中λ由全局敏感度和隱私預算ε決定，λ體現(xiàn)了添加噪聲的幅度大小以及隱私保護的強度大小，與隱私保護強度成正比.

1.1.4 質(zhì)量評估指標

1）數(shù)據(jù)查詢準確度.一個具有敏感信息的數(shù)據(jù)集在經(jīng)過隱私保護算法處理后，除了要保證敏感信息不外泄，還要保證處理過的數(shù)據(jù)集中的信息還能夠用于研究分析，所以要充分保證數(shù)據(jù)的可用性.因此，數(shù)據(jù)查詢準確度是衡量隱私保護方法的一個重要指標.本文通過將隱私保護方法得到的數(shù)據(jù)表與原數(shù)據(jù)計算重合比，來檢驗數(shù)據(jù)查詢準確度.

2）隱私保護強度表示在所設計的方法中滿足差分隱私的同時，確保隱私信息不被泄露，通常采用差分隱私的定義方法來評價算法是否滿足差分隱私的要求.由于差分隱私算法的隱私保護強度目前沒有一種定量的測量機制，本文在對隱私保護強度進行評估的時候使用ε以及噪聲的方差來近似表示.

3）時間復雜度.本文使用時間復雜度這項指標對所設計的算法進行評價，具體方法是通過計算各個實驗的運行時間來進行比較分析.

1.2 經(jīng)驗小波變換

經(jīng)驗小波變換（Empirical Wavelet Transform，EWT）[6]是Gilles提出的一種構建適合處理信號小波族的方法.為清楚起見，只考慮實際信號（它們的頻譜相對于頻率對稱，ω=0），但通過在正負頻率中構建不同的濾波器，可以很容易地將以下推理擴展到復雜信號.

把傅里葉頻譜劃分N份，每個分割的區(qū)間定義為Λn=[ωn-1，ωn]，n=1，2，…，N.其中，圍繞每個ωn都定義一個過渡段Tn（寬度是2n），這樣就需要N+1個邊界，除去已知的0和π兩個邊界，還需要N-1個邊界，如圖1所示.

考慮到歸一化的傅里葉軸具有2π周期性，為了遵守Shannon標準，將信號的頻譜變化范圍限制在ω∈[0，π]，首先假設傅里葉支持[0，π]被分割成N個連續(xù)的段.將ωn表示為每個段之間的界限（其中ω0=0、ωN=π），參見圖1.每個段表示為Λn=[ωn-1，ωn]，則很容易看出以每個ωn為中心，在ωn周圍定義了一個灰色陰影過渡區(qū)域Tn，寬度為2τn.

圖1 EWT頻譜的分割示例Fig.1 Example of EWT spectrum segmentation

EWT算法自適應性的好壞，很大程度上取決于信號頻譜中的有用信息能否被包含在相應的過渡區(qū)間內(nèi).因此，分段數(shù)N及其邊界點ωn的選取至關重要.分段數(shù)N選取的具體流程如圖2所示，其中α值取0.3～0.4.確定分段數(shù)N后，取M個極大值點中前N個最大值點，即{Mi}Ni=1，找出它們在頻譜中的具體位置，取相鄰兩極大值點所對應頻率的中值，記為邊界點ω（n=1，2，…，N-1）.經(jīng)驗小波就被定義為每個Λn上的帶通濾波器.為此，利用Littlewood-Paley和Meyer的小波構造中使用的思想，對于?n＞0，分別通過方程（5）和（6）定義經(jīng)驗尺度函數(shù)和經(jīng)驗小波.

圖2 EWT算法中分段數(shù)N的計算方法Fig.2 Calculation method of segment number N in EWT algorithm

其中：函數(shù)β（x）是任意的Ck（[0，1]）函數(shù)，許多函數(shù)滿足這些屬性，比如式（5）.

關于τn的選擇，有幾種選擇是可能的.最簡單的是選擇與τn成比例的ωn∶τn=γωn，其中0＜γ＜1.

EWT的構建.根據(jù)經(jīng)典小波變換理論構建經(jīng)驗小波，細節(jié)系數(shù)和逼近系數(shù)由待測信號與經(jīng)驗小波函數(shù)和經(jīng)驗尺度函數(shù)分別做內(nèi)積得到，如式（8）和式（9）所示：

公式（10）中：*表示卷積.根據(jù)重構公式，信號f（t）可以由公式（11）得到：

通過經(jīng)驗小波變換將信號分解，獲取一系列的調(diào)頻調(diào)幅分量，然后對這些分量處理獲取瞬時頻率和瞬時幅值.

1.3 致病基因關聯(lián)分析概述

致病基因相關度分析是本文的研究基礎，該技術來源于全基因組關聯(lián)研究（Genome-wide Association Studies，GWAS），目的是確定群體中哪些常見的單核苷酸多態(tài)性（SNP）與給定疾病相關.這是通過采集大量個體，在常見的SNP上對它們進行基因分型，并且對于每個SNP，進行統(tǒng)計測試來檢查該SNP是否與所述疾病相關，然后計算每個SNP的相關度并根據(jù)相關度進行排序來完成[7].

本文基于差分隱私的GWAS主要集中在對致病基因相關度排序并返回高度相關的SNP這一任務，為了保護私人表型信息（疾病狀態(tài)）在做致病基因相關度排序以及返回高度相關的SNP算法研究時不被泄露，以隱私保護的方式選擇相關度較高的SNP.首先需要使用基于噪聲的差分隱私方法進行隱私保護，然后對SNP的疾病相關性進行一系列的計算并評分，最終保證具有隱私保護的同時返回m個相關度較高的SNP，其中m是用戶定義的可變參數(shù).

1.4 基于小波變換的差分隱私

為了在滿足差分隱私的條件下，提高數(shù)據(jù)可用性，目前已有實現(xiàn)基于小波變換的差分隱私保護方法[8].該方法需要將數(shù)據(jù)以及參數(shù)λ作為輸入，其中參數(shù)λ是由不同的噪聲機制來確定的[9].圖3為基于小波變換的差分隱私實現(xiàn)步驟，其中最主要的有3個步驟.首先要對原數(shù)據(jù)進行小波變換處理，一般來說，小波變換是一個可逆線性函數(shù)，即它將數(shù)據(jù)集M映射到另一個矩陣C，這樣C中的每個數(shù)據(jù)項都是M中數(shù)據(jù)項的線性組合，且M也可以從C中無損地重建.C中數(shù)據(jù)項是由小波變換得到的小波系數(shù)，小波系數(shù)包含細節(jié)系數(shù)和近似系數(shù)（即高頻系數(shù)和低頻系數(shù)）.為了達到更好的降噪效果，經(jīng)多次實驗得出，將低頻系數(shù)添加差分隱私噪聲會得到更好的效果，算法的準確度會比較高.本節(jié)中C1為小波的低頻系數(shù)，C2為小波的高頻系數(shù).

圖3 基于小波變換的差分隱私實現(xiàn)步驟Fig.3 Differential privacy implementation steps based on wavelet transform

其次，在小波變換之后，為了保證實現(xiàn)差分隱私保護，需要為C1中的小波低頻系數(shù)添加獨立的噪聲（拉普拉斯噪聲、指數(shù)分布噪聲或者是高斯噪聲），這一步將得到具有噪聲系數(shù)的新矩陣C1′.

最后，將矩陣C1′使用小波變換的逆變換映射成具有差分隱私保護效用的矩陣M1，并將該矩陣作為經(jīng)過基于小波變換的差分隱私算法處理過的結果輸出返回.

1.5 基因關聯(lián)分析中的其他隱私保護技術

文獻[10]采用同態(tài)加密和Intel軟件保護擴展技術實現(xiàn)全基因組關聯(lián)分析中的隱私保護.文獻[11]采用博弈論的方法實現(xiàn)大規(guī)?；驍?shù)據(jù)有效、定量的隱私保護.文獻[12]提出一種分析全基因組上位性的新方法，該方法采用二階段框架的上位性分析方法，它包含特征過濾階段以及上位性組合優(yōu)化階段，在上位性組合優(yōu)化階段采用貪婪算法啟發(fā)式地搜索組合空間.

2 基于EWT的差分隱私

2.1 基于EWT的差分隱私的實現(xiàn)

本文是在滿足差分隱私保護的前提下，對數(shù)據(jù)添加的噪聲量進行一個降噪處理，最終得到較高可用性的數(shù)據(jù)集.為了實現(xiàn)以上方法，本文提出將EWT變換應用到差分隱私的噪聲處理中.該方法的具體步驟如圖4所示，首先使用差分隱私對數(shù)據(jù)進行處理，得到已滿足差分隱私的數(shù)據(jù)集，然后對該數(shù)據(jù)集進行相關EWT的處理.對于EWT的處理，首先，對數(shù)據(jù)集進行EWT分解，得到N個分段，并根據(jù)N個分段中信號的峭度值進行篩選并重構信號，得到最終降噪后的數(shù)據(jù)集.實驗最后使用該數(shù)據(jù)集來實現(xiàn)致病基因相關度排序，并對實驗的隱私保護強度以及算法性能進行評估.

圖4中根據(jù)峭度值篩選算法的具體步驟如下：

1）計算信號x（t）經(jīng)EWT分解后各分量的峭度值μn：

式中：N為采樣點數(shù)；cnk為EWT分解之后的分量.

2）根據(jù)μn得到各分量峭度值的集合μ：

3）定義信號的調(diào)頻調(diào)幅分量的峭度因子Zn：

圖4 基于EWT變換的差分隱私實現(xiàn)步驟Fig.4 Differential privacy implementation steps based on EWT transform

4）根據(jù)峭度因子選擇峭度分量.按照峭度因子從大到小的順序?qū)⑺姓{(diào)頻調(diào)幅分量進行重新排序，得到新的序列為排序后的峭度因子.

5）求出相鄰兩個調(diào)頻調(diào)幅分量的峭度因子之差，之后找出最大差值dn.

2.2 EWT降噪實例

根據(jù)2.1節(jié)描述的基于EWT的差分隱私實現(xiàn)方式，對差分隱私的3種噪聲機制進行實驗對比，得出結果如圖5所示.由圖5可以看出，基于Gauss噪聲機制的差分隱私準確度較高，因此本文后續(xù)的差分隱私保護實驗均以Gauss噪聲機制為例.

圖5 基于不同噪聲機制的差分隱私算法準確度Fig.5 Accuracy of differential privacy algorithm based on different noise mechanisms

在本文致病基因相關度研究實驗中，使用差分隱私添加Gauss噪聲進行EWT降噪.首先添加Gauss噪聲，然后采用EWT算法進行濾波仿真，最后將重構的數(shù)據(jù)提取后進行致病基因相關度排序?qū)嶒灢⒎祷叵嚓P度最高的m個SNP.

在使用EWT算法進行濾波仿真時，首先對包含Gauss噪聲的數(shù)據(jù)做傅里葉變換，提取傅里葉分段的邊界，根據(jù)對含噪聲的信號進行有效估計，確定濾波器組的邊界頻率.所得頻譜分割結果如圖6所示.

圖6 EWT頻譜分割Fig.6 EWT spectrum segmentation

提取邊界之后，通過鏡像來擴展信號以處理邊界，并建立相應的濾波器庫，通過過濾信號來提取每個子帶.劃分的頻帶共有50組，因此仿真信號的經(jīng)驗小波變換分解（EWT）的信號共有50組，用F1～F50表示.圖7為分解的50組EWT分量中的7組分量信號，從上到下依次表示為F1～F6.

圖7 經(jīng)EWT算法分解后的分量示例Fig.7 Example of component decomposed by EWT algorithm

對于EWT分解得到的分量，根據(jù)2.1節(jié)中的篩選算法計算出峭度因子，并對其進行排序，排序前后的對比如圖8所示.根據(jù)進一步計算可得，排序后兩個峭度因子之差的最大值位于F1和F23之間，最大差值為0.976 6，依據(jù)3.1節(jié)中根據(jù)峭度值篩選重構信號的算法可以得出，F(xiàn)1以及F24～F50為噪聲成分，而F2和F23之間包含主要的峭度成分，作為信號x（t）的有效特征分量.接下來，對F2～F23個分量進行重構，形成重構信號.圖9為原信號、添加Gauss噪聲后的信號以及重構信號的結果對比，縱軸相關度參數(shù)為致病基因相關度排序算法中計算疾病與基因相關度的實驗數(shù)據(jù).從圖9的對比結果可以看出，添加Gauss噪聲后的信號分布較為雜亂，而重構之后的信號相關度系數(shù)均勻分布在-0.15～0.15內(nèi)，沒有較大或者較小的信號.

圖8 排序前后的峭度因子Fig.8 Kurtosis factor before and after sorting

圖9 采用EWT算法對Gauss噪聲的降噪結果對比Fig.9 Comparison of noise reduction results of Gauss noise using EWT algorithm

3 實驗與結果分析

本節(jié)對ε-差分隱私、基于EWT變換以及基于小波變換的3種差分隱私的保護效果進行實驗對比分析.具體實驗中的差分隱私分別使用拉普拉斯機制、指數(shù)機制以及高斯機制3種實現(xiàn)機制，并設置不同的隱私參數(shù)ε，以及返回前m個與疾病具有高相關度的SNP來對實驗結果的影響進行測試.

3.1 數(shù)據(jù)集及實驗環(huán)境

實驗平臺為Intel（R）Core（TM）i7-6700HQ 2.60 GHz處理器，8 G內(nèi)存，操作系統(tǒng)為Windows10，編程環(huán)境為MATLAB R2014a以及Pycharm 2016.3（64）.

主要的測試數(shù)據(jù)來自某一類風濕性關節(jié)炎（RA）數(shù)據(jù)集NARAC-1，這組數(shù)據(jù)由Plink工具生成，該數(shù)據(jù)集及其生成代碼（基于Plink工具）可在線獲取.它包含2個種群，對于每一組，首先使用plink為10 000個SNP選擇MAF（Minor Allele Frequency），在某些條件下，最小等位基因頻率可以使用統(tǒng)計方法來準確和穩(wěn)健地解析在已知只有MAF的DNA樣本混合物中存在已知基因型的個體，每個SNP從[0.05，0.5]中隨機均勻選取.然后，從每個人群中生成了5 000人，有2 500個病例和2 500個對照病例.結果為每個樣本有10 000個SNP，9 900個無效，100個引起疾?。ㄆ鏀?shù)比率1.1）.然后將這2個群體組合起來生成模擬數(shù)據(jù)集，該模擬數(shù)據(jù)集是一個1×10 000的矩陣.

3.2 實驗步驟

本文中實驗的主要步驟如圖10所示.分別使用基本的ε-差分隱私（DP）、基于小波變換（WT-DP）以及基于EWT變換（EWT-DP）這3種差分隱私算法來進行實驗，并對這3種算法的實驗結果進行對比分析.在這3種算法的對比實驗中，選擇使用表現(xiàn)較好的Gauss機制來實現(xiàn)基本的差分隱私.另外，對基于EWT變換的差分隱私噪聲實現(xiàn)機制進行評估實驗，該實驗中分別使用Laplace、Exponential以及Gauss機制來實現(xiàn)基本的差分隱私.

圖10 實驗步驟Fig.10 Experimental procedure

3.3 隱私保護強度評估

本節(jié)對各種差分隱私算法的保護強度進行比較評估.由于差分隱私算法的隱私保護強度目前沒有一種定量的測量機制，但是噪聲參數(shù)λ體現(xiàn)了添加噪聲的幅度大小以及隱私保護強度的大小.因此，本文在對隱私保護強度進行評估的時候，通過計算噪聲參數(shù)λ以及噪聲分布的方差來近似表示.

圖11的實驗結果是對ε-差分隱私（DP）、基于小波變換（WT-DP）以及基于EWT變換（EWT-DP）的差分隱私算法的保護強度的比較，這3種方法中使用到的差分隱私均使用Gauss噪聲機制來實現(xiàn).本文中隱私保護強度是根據(jù)噪聲的方差來進行計算的.圖11結果表明，3種方法中ε-差分隱私算法的隱私保護強度相對較高，基于EWT變換的差分隱私算法的隱私保護強度相對較低，但差距并不大，這表明使用EWT變換可以保證一定量的隱私保護效用.

圖11 3種差分隱私算法的隱私保護強度對比Fig.11 Comparison of privacy protection strength of three differential privacy algorithms

圖12的實驗結果是基于EWT變換的3種差分隱私噪聲實現(xiàn)機制的隱私保護強度的比較，實驗中分別使用Laplace、Exponential以及Gauss機制來實現(xiàn)基本的差分隱私，橫坐標為ε的值.實驗結果表明，差分隱私的保護強度與ε負相關，ε的值越大，差分隱私所添加的噪聲越小，噪聲方差也越小，因此差分隱私的保護強度也越小.

圖12 基于EWT變換的差分隱私實現(xiàn)機制的隱私保護強度對比Fig.12 Comparison of privacy protection strength of differential privacy implementation mechanism based on EWT transform

3.4 算法時間復雜度

基于EWT變換的差分隱私算法時間復雜度主要由以下幾步?jīng)Q定：1）對數(shù)據(jù)表進行差分隱私加噪處理，將數(shù)據(jù)表映射成便于計算的序列M；2）對序列M進行EWT變換分解得到一系列的EWT分量；3）計算峭度值并根據(jù)峭度值來篩選重構信號；4）對信號進行重構，并提取降噪數(shù)據(jù)；5）使用降噪數(shù)據(jù)進行致病基因相關度排序算法，返回m個與疾病高度相關的SNP.總的時間復雜度近似為以上5個主要步驟的時間復雜度相加.

由于本文提出的基于EWT變換的差分隱私保護算法包括以上所列5個步驟，而ε-差分隱私（DP）理論上只包括步驟1）、步驟5）；而基于小波變換（WT-DP）的差分隱私算法理論上雖然包括步驟1）～步驟5），但是與本文所提的變換方法和降噪方法不同；所以，在運行時間上存在一定差異.

依據(jù)3.2節(jié)中的實驗步驟進行實驗并計算算法時間復雜度，對3種算法的運行時間計算20次并取平均值作為實驗結果.

圖13中的3種差分隱私算法均使用Gauss機制實現(xiàn)，可以看出基于EWT變換的差分隱私相較于其他2種差分隱私算法來說所花費的運行時間較長，性能比較低，這是因為EWT變換的過程相對于其他2種方法所花費的時間比較長.

圖13 3種差分隱私算法的運行時間對比Fig.13 Comparison of run time of three differential privacy algorithms

圖14的結果是基于EWT變換的3種差分隱私噪聲實現(xiàn)機制的運行時間對比，可以看出基于Gauss機制的運行時間最短，性能最佳.

圖14 基于EWT變換的差分隱私實現(xiàn)機制的運行時間對比Fig.14 Comparison of run time of differential privacy implementation mechanism based on EWT transform

3.5 致病基因相關度排序準確度評估

本文通過計算致病基因相關度排序的準確度來對經(jīng)差分隱私處理過的數(shù)據(jù)的數(shù)據(jù)質(zhì)量進行評估，具體做法是計算每次實驗返回結果與真實結果重合的百分比，作為算法準確度的度量.

依據(jù)3.2節(jié)中的實驗步驟進行實驗并計算算法時間復雜度，得出結果分別如圖15、圖16所示，這些結果均在20次迭代中取平均值.

圖15中的3種差分隱私算法均使用Gauss機制實現(xiàn)，可以看出，經(jīng)EWT變換后的差分隱私所得的致病基因相關度排序的準確度相對于其他2種方法比較高，也就是說使用該種方法處理數(shù)據(jù)的數(shù)據(jù)質(zhì)量比較好.

圖16中基于EWT變換的3種差分隱私噪聲實現(xiàn)機制中Gauss機制的準確度較高.

用戶可以根據(jù)其實際需求，采用本文所提方法設置相應的噪聲注入量和過濾量，實現(xiàn)合理的隱私保護效果.

本文所提方法基于經(jīng)驗小波變換，假設需要隱私保護的基因數(shù)據(jù)規(guī)模為N，經(jīng)驗小波變換的時間復雜度是O（N log（N））[6]，整數(shù)全同態(tài)加密算法時間復雜度是O（N3）[13]，本文所提方法與同態(tài)加密隱私保護技術相比，具有較低的計算時間復雜度.

圖15 3種差分隱私算法的準確度對比Fig.15 Comparison of accuracy of three differential privacy algorithms

圖16 基于EWT變換的差分隱私實現(xiàn)機制的準確度對比Fig.16 Comparison of accuracy of differential privacy implementation mechanism based on EWT transform

4 結論

針對在致病基因相關度排序?qū)嶒炛袛?shù)據(jù)因添加差分隱私噪聲而導致的數(shù)據(jù)可用性較低這一問題，本文提出了一種基于EWT變換的差分隱私保護方法，設計了實現(xiàn)步驟并通過實驗驗證了該方法的可行性和正確性.實驗結果表明，該方法在保證了差分隱私保護強度的條件下，能夠較為顯著地提高致病基因相關度排序數(shù)據(jù)的可用性和準確度，實現(xiàn)了數(shù)據(jù)隱私保護強度與可用性的有效權衡.下一步將繼續(xù)研究如何在保證算法準確度的情況下降低隱私保護算法的時間復雜度.