陳紅松，孟彩霞，劉書雨

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

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

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

1 相關(guān)技術(shù)

1.1 差分隱私

1.1.1 定義

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

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

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

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

這與差分隱私的通常定義不同，因?yàn)樵诓罘蛛[私中D通常不是固定的，而我們假設(shè)基因型矩陣D是固定的.直觀地，以上定義表明，當(dāng)一個(gè)人患有疾病時(shí)，F(xiàn)返回的結(jié)果在統(tǒng)計(jì)上與他們沒有疾病時(shí)返回的結(jié)果沒有區(qū)別.

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

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

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

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

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

1.1.3 實(shí)現(xiàn)機(jī)制

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

1）拉普拉斯機(jī)制.

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

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

2）指數(shù)機(jī)制.

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

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

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

1.1.4 質(zhì)量評(píng)估指標(biāo)

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

2）隱私保護(hù)強(qiáng)度表示在所設(shè)計(jì)的方法中滿足差分隱私的同時(shí)，確保隱私信息不被泄露，通常采用差分隱私的定義方法來(lái)評(píng)價(jià)算法是否滿足差分隱私的要求.由于差分隱私算法的隱私保護(hù)強(qiáng)度目前沒有一種定量的測(cè)量機(jī)制，本文在對(duì)隱私保護(hù)強(qiáng)度進(jìn)行評(píng)估的時(shí)候使用ε以及噪聲的方差來(lái)近似表示.

3）時(shí)間復(fù)雜度.本文使用時(shí)間復(fù)雜度這項(xiàng)指標(biāo)對(duì)所設(shè)計(jì)的算法進(jìn)行評(píng)價(jià)，具體方法是通過計(jì)算各個(gè)實(shí)驗(yàn)的運(yùn)行時(shí)間來(lái)進(jìn)行比較分析.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 基于EWT的差分隱私

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

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

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

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

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

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

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

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

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

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

2.2 EWT降噪實(shí)例

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

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

在本文致病基因相關(guān)度研究實(shí)驗(yàn)中，使用差分隱私添加Gauss噪聲進(jìn)行EWT降噪.首先添加Gauss噪聲，然后采用EWT算法進(jìn)行濾波仿真，最后將重構(gòu)的數(shù)據(jù)提取后進(jìn)行致病基因相關(guān)度排序?qū)嶒?yàn)并返回相關(guān)度最高的m個(gè)SNP.

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

3.2 實(shí)驗(yàn)步驟

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

圖10 實(shí)驗(yàn)步驟Fig.10 Experimental procedure

3.3 隱私保護(hù)強(qiáng)度評(píng)估

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

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

圖11 3種差分隱私算法的隱私保護(hù)強(qiáng)度對(duì)比Fig.11 Comparison of privacy protection strength of three differential privacy algorithms

圖12的實(shí)驗(yàn)結(jié)果是基于EWT變換的3種差分隱私噪聲實(shí)現(xiàn)機(jī)制的隱私保護(hù)強(qiáng)度的比較，實(shí)驗(yàn)中分別使用Laplace、Exponential以及Gauss機(jī)制來(lái)實(shí)現(xiàn)基本的差分隱私，橫坐標(biāo)為ε的值.實(shí)驗(yàn)結(jié)果表明，差分隱私的保護(hù)強(qiáng)度與ε負(fù)相關(guān)，ε的值越大，差分隱私所添加的噪聲越小，噪聲方差也越小，因此差分隱私的保護(hù)強(qiáng)度也越小.

圖12 基于EWT變換的差分隱私實(shí)現(xiàn)機(jī)制的隱私保護(hù)強(qiáng)度對(duì)比Fig.12 Comparison of privacy protection strength of differential privacy implementation mechanism based on EWT transform

3.4 算法時(shí)間復(fù)雜度

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

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

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

圖13中的3種差分隱私算法均使用Gauss機(jī)制實(shí)現(xiàn)，可以看出基于EWT變換的差分隱私相較于其他2種差分隱私算法來(lái)說(shuō)所花費(fèi)的運(yùn)行時(shí)間較長(zhǎng)，性能比較低，這是因?yàn)镋WT變換的過程相對(duì)于其他2種方法所花費(fèi)的時(shí)間比較長(zhǎng).

圖13 3種差分隱私算法的運(yùn)行時(shí)間對(duì)比Fig.13 Comparison of run time of three differential privacy algorithms

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

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

3.5 致病基因相關(guān)度排序準(zhǔn)確度評(píng)估

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

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

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

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

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

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

圖15 3種差分隱私算法的準(zhǔn)確度對(duì)比Fig.15 Comparison of accuracy of three differential privacy algorithms

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

4 結(jié)論

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