面向醫(yī)療數(shù)據(jù)的AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法

摘 要：隨著醫(yī)學(xué)技術(shù)的進(jìn)步和大數(shù)據(jù)時(shí)代的到來，在數(shù)據(jù)發(fā)布時(shí)如何對(duì)患者就診記錄中的敏感信息進(jìn)行隱私保護(hù)成為當(dāng)前的研究熱點(diǎn)。針對(duì)醫(yī)療大數(shù)據(jù)在發(fā)布過程中隱私保護(hù)問題，提出了基于屬性效用值排序法AUR-Tree（attribute utility value ranking-tree）差分隱私數(shù)據(jù)發(fā)布算法。該算法用屬性效用值排序法衡量準(zhǔn)標(biāo)識(shí)屬性對(duì)敏感屬性的影響程度，以此作為迭代分割的度量依據(jù)，采用基于泛化的自頂向下迭代分割分類樹技術(shù)，通過類等差法合理地分配隱私預(yù)算從而實(shí)現(xiàn)在醫(yī)療數(shù)據(jù)發(fā)布過程中的隱私保護(hù)。實(shí)驗(yàn)結(jié)果表明：該算法在極大地提高了數(shù)據(jù)的安全性、有效性和可用性的前提下，還保留了后續(xù)數(shù)據(jù)挖掘的價(jià)值。

關(guān)鍵詞：屬性效用值排序法；屬性層次泛化樹；差分隱私

中圖分類號(hào)：TP309.2 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）07-039-2162-05

doi：10.19734/j.issn.1001-3695.2021.10.0658

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61802161）；遼寧省教育廳科學(xué)研究經(jīng)費(fèi)資助項(xiàng)目（JZL202015402）；遼寧省自然科學(xué)基金資助項(xiàng)目（2020-MS-292）

作者簡(jiǎn)介：張思琪（1998-），女，山東臨沂人，碩士研究生，主要研究方向?yàn)榇髷?shù)據(jù)安全、隱私保護(hù)；李曉會(huì)（1978-），女（通信作者），遼寧盤錦人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、 信任管理、隱私保護(hù)（lhxlxh@163.com）；江欣俞（1999-），男，遼寧丹東人，碩士研究生，主要研究方向?yàn)榇髷?shù)據(jù)安全、隱私保護(hù)；李波（1977-），男，教授，碩導(dǎo)，博士，主要研究方向?yàn)楝F(xiàn)代信息處理、現(xiàn)代移動(dòng)通信、多源信息融合．

AUR-Tree differential privacy data publishing algorithm for medical data

Zhang Siqi，Li Xiaohui?，Jiang Xinyu，Li Bo

（School of Electronics amp; Information Engineering，Liaoning University of Technology，Jinzhou Liaoning 121000，China）

Abstract：With the advancement of medical technology and big data era，how to protect the privacy of sensitive information in patients’ medical records has become a current research focus issue.In order to protect the privacy of medical big data in the publishing process，this paper proposed an AUR-Tree differential privacy data publishing algorithm.The algorithm used the attribute utility value ranking method to measure the influence degree of the quasi-identity attributes on the sensitive attributes，which was as the measurement basis for iterative segmentation.Then it adopted top-down iterative segmentation classification tree technology based on generalization，

and reasonably allocated the privacy budget through the class arithmetic method to realize the privacy protection in the medical data release process.The experimental results show that the algorithm retains the value of subsequent data mining and greatly improves the security，effectiveness and usability of the data.

Key words：attribute utility value ranking method；attribute hierarchy generalization tree；differential privacy

0 引言

互聯(lián)網(wǎng)的發(fā)展和大數(shù)據(jù)時(shí)代的到來改變了人們的生活方式，電子化醫(yī)療信息逐漸取代傳統(tǒng)紙質(zhì)版醫(yī)療信息，促使各類醫(yī)療信息被大量存儲(chǔ)在互聯(lián)網(wǎng)和云平臺(tái)上。醫(yī)療信息的共享和更深層次的醫(yī)學(xué)研究要求數(shù)據(jù)采集者發(fā)布收集到的相關(guān)醫(yī)療信息，然而醫(yī)療信息中往往含有許多患者的個(gè)人敏感信息，如果直接將采集到的數(shù)據(jù)進(jìn)行發(fā)布必然會(huì)造成患者隱私信息的泄露，給患者帶來不必要的困擾。據(jù)調(diào)查顯示，2019年7月，在某論壇以每條3元的價(jià)格售賣某醫(yī)院的實(shí)時(shí)就診掛號(hào)數(shù)據(jù)，數(shù)據(jù)中包含姓名、手機(jī)號(hào)、就診科室等患者的相關(guān)敏感信息，泄露的患者就診信息是犯罪分子實(shí)施醫(yī)療詐騙和精準(zhǔn)營(yíng)銷的核心數(shù)據(jù)；2020年4月，青島膠州中心醫(yī)院的六千多條就診人員名單在微信朋友圈中流傳，其中泄露的個(gè)人信息已然嚴(yán)重影響了個(gè)人生活，曾一度謠傳他們感染了新冠肺炎，造成社會(huì)恐慌。因此，在數(shù)據(jù)發(fā)布的過程中保護(hù)患者隱私不泄露勢(shì)在必行。

從大數(shù)據(jù)的角度出發(fā)，醫(yī)療大數(shù)據(jù)不僅具有規(guī)模大、增長(zhǎng)快、種類多、價(jià)值大的特點(diǎn)，還具有多態(tài)性、不完整性、時(shí)效性、冗余性和高度敏感性的特點(diǎn)^[1]。

科技的進(jìn)步促進(jìn)了醫(yī)療診斷手段的不斷發(fā)展，為更好地幫助病人進(jìn)行診斷，各種先進(jìn)的醫(yī)療設(shè)備和診斷手段被應(yīng)用在日常就診過程中，形成了醫(yī)療數(shù)據(jù)模態(tài)多樣性的特點(diǎn)。有患者的個(gè)人就診信息、醫(yī)生診斷結(jié)果、患者癥狀描述等文本型信息；X光、CT等各類成片醫(yī)學(xué)影像等圖片型信息；心電圖、血壓圖等類信號(hào)譜型信息；B超、超聲、手術(shù)記錄等視頻型信息等。這些數(shù)據(jù)隨著時(shí)間和患者生命體征的改變?cè)诓粩嗟馗伦兓蚨t(yī)療數(shù)據(jù)具有較高的時(shí)效性和連續(xù)性。在新冠疫情中對(duì)感染者的搶救，醫(yī)療數(shù)據(jù)的時(shí)效性體現(xiàn)得淋漓盡致。除此之外，醫(yī)療大數(shù)據(jù)還具有冗余性，大量相同或類似的信息存儲(chǔ)在醫(yī)療數(shù)據(jù)中，如患者個(gè)人信息、病理特征、癥狀描述等，數(shù)據(jù)的冗余增加了預(yù)處理的時(shí)間，浪費(fèi)大量的存儲(chǔ)空間，降低了數(shù)據(jù)的可利用性。醫(yī)療大數(shù)據(jù)的不完整性通常體現(xiàn)在數(shù)據(jù)的收集和處理過程中，就診過程中患者對(duì)自身癥狀的描述不清、醫(yī)生的主觀判斷的不完整和診斷手段的不同等相關(guān)因素都會(huì)造成數(shù)據(jù)的不完整性，無法達(dá)成數(shù)據(jù)的一致性。醫(yī)療大數(shù)據(jù)中承載著大量公民的個(gè)人信息，相比于其他大數(shù)據(jù)具有高度敏感性，醫(yī)療就診信息中主要包含身份證號(hào)、社保號(hào)、年齡、所患疾病、藥物劑量、主治醫(yī)生等敏感信息，稍有不慎造成醫(yī)療數(shù)據(jù)的泄露使得公民的個(gè)人信息公之于眾，給犯罪分子可乘之機(jī)。如今，若僅依靠國(guó)家出臺(tái)的法律法規(guī)等相關(guān)政策已不能滿足數(shù)據(jù)發(fā)布中的隱私保護(hù)需求，必須運(yùn)用科學(xué)技術(shù)手段對(duì)患者的醫(yī)療信息進(jìn)行隱私保護(hù)。因此，在數(shù)據(jù)發(fā)布過程中，如何在保證數(shù)據(jù)可用性和有效性的同時(shí)保護(hù)患者的隱私信息不被泄露是當(dāng)前的一個(gè)研究熱點(diǎn)。

數(shù)據(jù)發(fā)布作為數(shù)據(jù)查詢、數(shù)據(jù)挖掘和數(shù)據(jù)分析的基礎(chǔ)，在數(shù)據(jù)發(fā)布之前對(duì)數(shù)據(jù)信息進(jìn)行隱私保護(hù)可以有效地防止數(shù)據(jù)泄露帶來的危害。傳統(tǒng)的數(shù)據(jù)發(fā)布隱私保護(hù)模型多采用k-anonymity^[2]、l-diversity^[3]、t-closeness ^[4]等匿名模型及其變體^[5]對(duì)數(shù)據(jù)進(jìn)行匿名處理，以達(dá)到隱私保護(hù)的效果。匿名模型的基本思想是通過對(duì)數(shù)據(jù)進(jìn)行泛化處理（即用一個(gè)模糊的范圍取代一個(gè)準(zhǔn)確的值）達(dá)到數(shù)據(jù)不可區(qū)分的效果，進(jìn)而實(shí)現(xiàn)隱私保護(hù)。因匿名模型的局限性，無法抵御復(fù)雜的背景知識(shí)攻擊。針對(duì)這一問題，2006年Dwork提出了差分隱私模型，作為一種隱私模型，該模型不取決于攻擊者對(duì)背景知識(shí)的了解程度，而是基于嚴(yán)格的數(shù)學(xué)基礎(chǔ)，對(duì)查詢結(jié)果或者分析結(jié)果添加噪聲使數(shù)據(jù)失真，從而達(dá)到隱私保護(hù)的效果。

為解決醫(yī)療數(shù)據(jù)在發(fā)布過程中隱私泄露的問題，史漢發(fā)等人^[6]提出了AHPK-匿名算法，該算法利用層次分析法計(jì)算不同準(zhǔn)標(biāo)識(shí)符屬性對(duì)敏感屬性的效用權(quán)值并進(jìn)行排序，根據(jù)排序按照概化樹對(duì)屬性進(jìn)行概化并依次遞歸判斷概化后的數(shù)據(jù)集是否滿足k-匿名約束；林國(guó)濱^[7]提出了基于KD樹的電子病歷數(shù)據(jù)發(fā)布方法，該方法通過計(jì)算WordNet語(yǔ)義相似度構(gòu)造患者屬性分類樹，利用KD樹的性質(zhì)對(duì)數(shù)據(jù)集進(jìn)行分解，每次分解時(shí)只對(duì)一個(gè)屬性進(jìn)行分解，最終使葉子節(jié)點(diǎn)的記錄滿足（k，l）多樣性，彌補(bǔ)了k-匿名模型和l-多樣性模型的不足；丁有偉等人^[8]提出了一種基于聚類的個(gè)性化k-匿名算法，該算法首先將原始數(shù)據(jù)集中的準(zhǔn)標(biāo)識(shí)符屬性按照用戶自定義的個(gè)性化泛化樹進(jìn)行泛化，然后將泛化后的數(shù)據(jù)映射到歐幾里德空間進(jìn)行聚類成滿足k-匿名約束的等價(jià)類，最后對(duì)滿足k-匿名約束的匿名數(shù)據(jù)表進(jìn)行發(fā)布；結(jié)合差分隱私的優(yōu)勢(shì)，曹惠瑞^[9]提出了基于隨機(jī)森林的差分隱私醫(yī)療數(shù)據(jù)發(fā)布方法，該方法利用隨機(jī)森林和標(biāo)準(zhǔn)矩陣分別完成數(shù)據(jù)集的分類識(shí)別和屬性間關(guān)聯(lián)強(qiáng)弱程度的計(jì)算，隨后根據(jù)隨機(jī)森林的識(shí)別正確率和屬性間的關(guān)聯(lián)性合理地分配隱私預(yù)算，并對(duì)查詢計(jì)數(shù)結(jié)果添加Laplace噪聲，最后將處理好的數(shù)據(jù)保存在本地的隱私數(shù)據(jù)庫(kù)中，以統(tǒng)計(jì)表或直方圖的方式進(jìn)行發(fā)布。

基于以上方法的討論可以發(fā)現(xiàn)，現(xiàn)有的醫(yī)療數(shù)據(jù)發(fā)布方法多數(shù)以匿名模型作為隱私保護(hù)模型，無法有效地保證醫(yī)療數(shù)據(jù)免受背景知識(shí)的攻擊導(dǎo)致患者隱私信息的泄露。為此，本文提出了一種針對(duì)醫(yī)療大數(shù)據(jù)基于屬性效用值排序法AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法，其創(chuàng)新點(diǎn)有：

a）對(duì)于屬性的分割采用屬性效用值排序法依次確定每次迭代分割的屬性，若為離散型屬性，則按照屬性層次泛化樹進(jìn)行迭代分割；若為連續(xù)型屬性，則利用指數(shù)機(jī)制選擇最佳分裂點(diǎn)進(jìn)行迭代分割，減少調(diào)用指數(shù)機(jī)制的次數(shù)。

b）對(duì)于隱私預(yù)算的分配采用類等差法，先將隱私預(yù)算二等分，其中ε/2用于對(duì)葉子節(jié)點(diǎn)計(jì)數(shù)加拉普拉斯噪聲用于發(fā)布，另外ε/2按照類等差法分配給分類樹的每一層，在構(gòu)建分類樹分割屬性時(shí)滿足差分隱私的要求。

1 相關(guān)工作原理

1.1 表的屬性

假設(shè)一個(gè)表格數(shù)據(jù)集T，其中包含t條記錄（表1中t為9），每條記錄對(duì)應(yīng)一個(gè)實(shí)體，將實(shí)體中的屬性主要分為以下三類：

a）標(biāo)識(shí)符屬性^[10]。能唯一識(shí)別個(gè)人身份（如身份證號(hào)等）。

b）準(zhǔn)標(biāo)識(shí)屬性。不可單獨(dú)作為識(shí)別個(gè)人身份的屬性字段，需要和其他字段聯(lián)合以達(dá)到唯一識(shí)別的目的（如表1{age}、{zipcode}、{job}、性別、郵政編碼等）。

c）敏感屬性。存放個(gè)人/敏感信息字段，是攻擊者想要獲取的字段（如表1{disease}、收入等）。

1.2 差分隱私相關(guān)概念

Dwork^[11]在2006年提出了差分隱私保護(hù)模型，該模型具有嚴(yán)格的隱私定義，且可以抵御任何背景知識(shí)的攻擊。差分隱私保護(hù)模型基于數(shù)據(jù)失真技術(shù)，該模型的基本原理是對(duì)精確的查詢或分析結(jié)果中添加合適的噪聲值對(duì)結(jié)果進(jìn)行擾動(dòng)，從而實(shí)現(xiàn)保護(hù)隱私數(shù)據(jù)的效果。該模型保證了數(shù)據(jù)集中任一記錄的改變不會(huì)影響查詢的輸出結(jié)果，因此，差分隱私保護(hù)模型被研究者們廣泛地應(yīng)用在各種場(chǎng)景中以達(dá)到保護(hù)數(shù)據(jù)的作用。下面對(duì)差分隱私進(jìn)行詳細(xì)的介紹。

定義1 ε-差分隱私^[12，13]。對(duì)于兩個(gè)完全相同或記錄相差一條的數(shù)據(jù)集D1和D2，A為隨機(jī)算法，算法A對(duì)數(shù)據(jù)集Di的輸出值域用range（A）表示，S表示range（A）的子集，若算法滿足式（1），則稱算法A滿足隱私預(yù)算為ε的差分隱私算法：

其中：Pr（·）表示算法A輸出的概率；ε為隱私預(yù)算，用于衡量算法A的隱私保護(hù)程度，ε的大小與隱私保護(hù)程度成反比，算法A的隱私保護(hù)程度隨著ε取值的增大而逐漸變小。

定義2 全局敏感度^[14]。敏感度通常用來衡量隨機(jī)刪除數(shù)據(jù)集中的一條記錄對(duì)查詢結(jié)果造成的影響，表示為Δf。設(shè)函數(shù)有如下映射關(guān)系：f：D→Rd，該函數(shù)輸入為一數(shù)據(jù)集，以d維實(shí)數(shù)向量作為輸出結(jié)果。對(duì)于任意的鄰近數(shù)據(jù)集D1和D2，全局敏感度表示為

其中：‖maxD1，D2f（D1）-f（D2）‖1表示為1-范式。

定義3 隱私保護(hù)機(jī)制^[15]。Laplace機(jī)制和指數(shù)機(jī)制是差分隱私保護(hù)模型最具有代表性的兩種隱私保護(hù)實(shí)現(xiàn)機(jī)制。

在精確的查詢結(jié)果中加入服從Laplace分布的隨機(jī)噪聲是Laplace機(jī)制實(shí)現(xiàn)的基本原理，從而實(shí)現(xiàn)滿足隱私預(yù)算為ε的差分隱私保護(hù)，設(shè)Laplace分布的位置參數(shù)Lap（b）為0，則概率密度函數(shù)表示為

定理1 Laplace機(jī)制^[16]。對(duì)某一數(shù)據(jù)集D，若函數(shù)f：D→Rd，且函數(shù)f的全局敏感度用Δf表示，有隨機(jī)算法M（D）=f（D）+Y提供ε-隱私保護(hù)，其中Y服從參數(shù)為Δf/ε的Laplace分布，記為Y～Lap（Δf/ε）。

鑒于Laplace機(jī)制只適用于數(shù)值型查詢結(jié)果，而在很多實(shí)際的應(yīng)用情況下，僅有數(shù)值型查詢結(jié)果往往是不足以滿足需求的，因此提出指數(shù)機(jī)制彌補(bǔ)Laplace機(jī)制的不足，適用于非數(shù)值型查詢結(jié)果。該機(jī)制通過可用性函數(shù)q來評(píng)估輸出值r的優(yōu)劣程度。

1.3 隱私保護(hù)相關(guān)概念

定義4 屬性層次泛化樹^[7]。對(duì)于給定屬性的屬性域D，其中D為有限集，S用于表示一棵樹的所有節(jié)點(diǎn)的集合，則S={T，v1，v2，…，vn，s1，s2，…，sn}（其中T為屬性層次泛化樹的根節(jié)點(diǎn)，si為樹中的葉子節(jié)點(diǎn)，vi為非根、非葉子節(jié)點(diǎn)的其他中間節(jié)點(diǎn)），設(shè)函數(shù)f為S到D的映射關(guān)系，節(jié)點(diǎn)a和b為S中存在父子關(guān)系的兩個(gè)節(jié)點(diǎn)，則有f（b）f（a），對(duì)根節(jié)點(diǎn)和葉子節(jié)點(diǎn)有fs｜i｜=1（1≤i≤n），f（s1）∪f(wàn)（s2）∪…∪f(wàn)（sn）=f（T）且f（T）D。例如，圖1為表1中{job}的一棵屬性層次泛化樹。

定義5 屬性效用值排序法（rank method of attribute utility value，AUR）。層次分析法^[7]作為一個(gè)處理復(fù)雜多目標(biāo)決策問題的系統(tǒng)，將復(fù)雜的目標(biāo)問題進(jìn)行分解，得到多個(gè)目標(biāo)或準(zhǔn)則，進(jìn)而分解成對(duì)應(yīng)的多個(gè)層次，通過定性指標(biāo)的模糊定量方法計(jì)算層次階數(shù)和總階數(shù)，并進(jìn)行目標(biāo)多方案優(yōu)化決策。傳統(tǒng)的層次分析法對(duì)屬性進(jìn)行等級(jí)評(píng)定時(shí)采用九級(jí)評(píng)定，對(duì)醫(yī)療大數(shù)據(jù)而言，傳統(tǒng)的層次分析會(huì)加大計(jì)算量，增加了計(jì)算的復(fù)雜性和繁瑣性。針對(duì)醫(yī)療大數(shù)據(jù)的特點(diǎn)，對(duì)傳統(tǒng)的層次分析法進(jìn)行改進(jìn)，將九級(jí)評(píng)定簡(jiǎn)化為三級(jí)評(píng)定，將改進(jìn)后的層次分析法命名為屬性效用值排序法，如表2所示，以下幾個(gè)步驟用于該方法計(jì)算：

a）建立層次結(jié)構(gòu)模型。利用決策目標(biāo)、決策準(zhǔn)則和決策對(duì)象這三者之間的相互作用影響，將其依次對(duì)應(yīng)為最高層、中層和最低層的層次關(guān)系，并繪制其層次結(jié)構(gòu)圖。

b）構(gòu)造判斷矩陣。將屬性集D中的屬性兩兩依次進(jìn)行比較，等級(jí)需按照屬性層次泛化樹的高度進(jìn)行評(píng)定，aij表示為屬性i與屬性j重要性比較結(jié)果，判斷矩陣由兩兩屬性按屬性層次泛化樹高度比較量化后的結(jié)果組成，記兩屬性層次泛化樹高度中較小者的高度為h。若hlt;3，則記為稍微重要，量化值為1；若h≥6，則記為強(qiáng)烈重要，量化值為3；若h處于兩者中間，則記為較強(qiáng)重要，量化值為2。aij=1/aji是判斷矩陣的性質(zhì)之一。

c）層次單排序及其一致性檢驗(yàn)。λmax為判斷矩陣最大的特征根，W表示為λmax對(duì)應(yīng)特征向量歸一化的結(jié)果向量，同一層次因素對(duì)于上一層因素某因素相對(duì)重要性的排序權(quán)值用W中的元素表示，這一過程稱為層次單排序。一致性檢驗(yàn)被定義為

其中：λ為最大特征根；n為判斷矩陣的階數(shù)。

CI越趨向0，一致性效果越好，當(dāng)CI=0，一致性效果最好。隨機(jī)一致性指標(biāo)RI被用于衡量CI的大小：

式（5）表明，判斷矩陣的階數(shù)n影響隨機(jī)一致性指標(biāo)RI的取值。一般情況下，隨著矩陣階數(shù)的增大，一致性隨機(jī)偏離的概率也就越大，為此引入了檢驗(yàn)系數(shù)CR概念來檢驗(yàn)一致性的偏離是否由隨機(jī)原因造成的。

d）層次總排序及一致性檢驗(yàn)。對(duì)所有層次依次計(jì)算所有因素對(duì)于最高層次相對(duì)重要的權(quán)值，并進(jìn)行一致性檢驗(yàn)。

1.4 度量標(biāo)準(zhǔn)

定義6 泛化信息損失度。屬性層次泛化樹葉子節(jié)點(diǎn)的總數(shù)為XST，設(shè)節(jié)點(diǎn)n*為一子樹的根節(jié)點(diǎn)，該子樹的葉子節(jié)點(diǎn)總數(shù)為XST-n*，則泛化信息損失度（從屬性n到n*）GLoss（n*）公式如下所示。

定義7 絕對(duì)誤差^[19]。用來度量隱私保護(hù)后的發(fā)布值偏離查詢結(jié)果的真實(shí)值的絕對(duì)大小，公式如下：

其中：xi表示查詢結(jié)果的真實(shí)值；xj表示隱私保護(hù)后的發(fā)布值。

2 AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法

2.1 算法設(shè)計(jì)思路

首先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，刪除數(shù)據(jù)集中的標(biāo)識(shí)屬性，對(duì)每個(gè)準(zhǔn)標(biāo)識(shí)屬性進(jìn)行泛化，構(gòu)建屬性層次泛化樹，并記樹高度hi；其次利用AUR獲得準(zhǔn)標(biāo)識(shí)屬性對(duì)敏感屬性的效用排序（即準(zhǔn)標(biāo)識(shí)屬性對(duì)敏感屬性的重要程度），效用排序作為屬性分裂點(diǎn)的度量依據(jù)，重要的準(zhǔn)標(biāo)識(shí)屬性最后進(jìn)行分割，分配的隱私預(yù)算越小，隱私保護(hù)程度越高；對(duì)于數(shù)據(jù)集中的離散型數(shù)據(jù)，按照屬性層次泛化樹進(jìn)行迭代分割，當(dāng)屬性劃分到泛化樹的次高層時(shí)迭代分割結(jié)束；對(duì)于連續(xù)型數(shù)據(jù)利用指數(shù)機(jī)制找到最佳分裂點(diǎn)將值域一分為二，逐次進(jìn)行迭代劃分，當(dāng)分割區(qū)間長(zhǎng)度lt;m（某個(gè)定值）后分割結(jié)束。

對(duì)于隱私預(yù)算的分配，首先將隱私預(yù)算ε進(jìn)行二等分，一部分隱私預(yù)算采用類等差法將隱私預(yù)算合理地分配到AUR-Tree的每一層，構(gòu)建符合差分隱私特性的樹模型；另一部分隱私預(yù)算用于Laplace機(jī)制，對(duì)分割完成后的葉子節(jié)點(diǎn)計(jì)數(shù)添加Laplace噪聲，并對(duì)添加完噪聲后的葉子節(jié)點(diǎn)進(jìn)行發(fā)布。

2.2 算法描述

算法1 構(gòu)建屬性層次泛化樹

輸入：預(yù)處理后的數(shù)據(jù)表NT，準(zhǔn)標(biāo)識(shí)屬性Q的所包含的屬性值Q={t1，t2，t3，…，tn}。

輸出：屬性層次泛化樹QI_Tree。

begin

構(gòu)建一顆空樹GT0；

定義GT0的根節(jié)點(diǎn)NT=t1；

for i：=1 to n do：

NT=GNT_Insert（ti，NT）；

end for

end

算法1主要實(shí)現(xiàn)預(yù)處理后的數(shù)據(jù)表中的準(zhǔn)標(biāo)識(shí)符屬性Q的層次泛化樹的構(gòu)建。首先，構(gòu)建一個(gè)樹狀結(jié)構(gòu)，將屬性集合Q的第一個(gè)值作為樹的根節(jié)點(diǎn)；然后，調(diào)用算法2中的GNT_Insert（）依次插入屬性集合中下一個(gè)元素屬性值，形成新的樹的父節(jié)點(diǎn)；最后，將屬性集合的元素全部遍歷完成即插入成功，構(gòu)建出一棵屬性層次泛化樹。

算法2 將屬性泛化樹插入新的GNT_Insert（ti，NT）（在算法1中實(shí)現(xiàn)）

算法2作為算法1中的一部分，其主要功能在于遍歷屬性值時(shí)如何將屬性值作為新的節(jié)點(diǎn)插入到樹結(jié)構(gòu)中，從而完成屬性層次泛化樹的構(gòu)建。該算法是在基于泛化樹結(jié)構(gòu)的基礎(chǔ)上構(gòu)建新的節(jié)點(diǎn)，如果待插入的數(shù)據(jù)與根節(jié)點(diǎn)的數(shù)據(jù)相等，則不進(jìn)行插入操作；當(dāng)待插入的數(shù)據(jù)包含根節(jié)點(diǎn)的數(shù)據(jù)，將待插入的數(shù)據(jù)作為新的根節(jié)點(diǎn)；相反地，如果都不相互包含，則將待插入的數(shù)據(jù)和舊根節(jié)點(diǎn)作為新的根節(jié)點(diǎn)的子節(jié)點(diǎn)；如果根節(jié)點(diǎn)數(shù)據(jù)包含待插入節(jié)點(diǎn)的數(shù)據(jù)同時(shí)又不在其中任何一個(gè)子節(jié)點(diǎn)的數(shù)據(jù)，則將待插入的數(shù)據(jù)插入待根節(jié)點(diǎn)的新的子節(jié)點(diǎn)的位置；當(dāng)根節(jié)點(diǎn)的子節(jié)點(diǎn)包含待插入的數(shù)據(jù)時(shí)，此時(shí)采用遞歸的方式將待插入的數(shù)據(jù)插入到根節(jié)點(diǎn)的子樹其中一個(gè)位置，其他插入的節(jié)點(diǎn)方式按照此遞歸方式依次遞歸下去，直到所有的數(shù)據(jù)插入進(jìn)去。

算法3 AUR-Tree算法

輸入：預(yù)處理后數(shù)據(jù)表NT，樹高度為h，給定總的隱私預(yù)算ε，屬性層次泛化樹GT_Create（Nt），等差距離d。

輸出：AUR-Tree。

停止條件：隱私預(yù)算ε耗盡或?qū)傩詫哟畏夯瘶浔闅v完成。

begin

t1←root；

GT_Create（Nt）←Qi={t1，t2，t3，…，tn}；

Sort；

用AUR計(jì)算準(zhǔn)標(biāo)識(shí)屬性對(duì)敏感屬性的效用值，并得到效用排序表；

ε′=ε/2；

for i：=1 to n：

H[QI_Tree（i）]←QI（i）；

H-1[QI（i）]←QI_Tree（i）；

εi←ε；

for ilt;h+1：

ε′=ε/（h+1）+（h/2-i）d；

GetNoise（εi）；

end for

if（root！ =Null）：

count′=count+Noise；

for each root→child：

AddLaplace（root→child，lap（2/ε′））；

end for

end if

output εi

end

算法3實(shí)現(xiàn)了準(zhǔn)標(biāo)識(shí)符屬性對(duì)敏感屬性效用值排序的計(jì)算，按照類等差法對(duì)分類樹分配隱私預(yù)算以及對(duì)葉子節(jié)點(diǎn)計(jì)數(shù)添加Laplace噪聲，并將加噪后的數(shù)據(jù)進(jìn)行發(fā)布的功能。該算法是在算法1和2的基礎(chǔ)上構(gòu)建AUR-Tree：首先，將總的預(yù)算分成兩部分，同時(shí)通過AUR計(jì)算準(zhǔn)標(biāo)識(shí)屬性對(duì)敏感屬性的效用值，并得到效用排序表；然后，根據(jù)排序后的結(jié)果對(duì)屬性分配隱私預(yù)算用于構(gòu)建符合差分隱私的分類樹，調(diào)節(jié)參數(shù)d值，可以改變等差預(yù)算方式分配方式，當(dāng)d=0時(shí)，分類樹每層分配的隱私預(yù)算相同，如果0lt;dlt;[h（h+1）]，則根節(jié)點(diǎn)到葉子節(jié)點(diǎn)分配隱私預(yù)算的差值為d；最后將形成分類樹后剩下的1/2隱私預(yù)算依次分配給葉子節(jié)點(diǎn)的計(jì)數(shù)值，為其添加Laplace噪聲，并將隱私保護(hù)后的數(shù)據(jù)進(jìn)行發(fā)布。

2.3 算法分析

2.3.1 時(shí)間復(fù)雜度分析

本文所提到的AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法首先需要根據(jù)AUR計(jì)算出準(zhǔn)標(biāo)識(shí)屬性對(duì)敏感屬性的效用值，并對(duì)效用值進(jìn)行一個(gè)排序，在整個(gè)算法中，效用值只需要計(jì)算一次，得到效用值排序后便不需要再進(jìn)行計(jì)算，因此，在該步驟中的時(shí)間復(fù)雜度為O（1）；其次需要?jiǎng)?chuàng)建屬性層次泛化樹，假設(shè)有M個(gè)準(zhǔn)標(biāo)識(shí)屬性，每個(gè)準(zhǔn)標(biāo)識(shí)屬性有n個(gè)取值，建立一個(gè)屬性層次泛化樹所需要的時(shí)間復(fù)雜度為O（n log n），對(duì)應(yīng)M個(gè)準(zhǔn)標(biāo)識(shí)屬性，需要的總時(shí)間為M×O（n log n）；最后建立分類樹，將所有記錄壓縮到根節(jié)點(diǎn)，根據(jù)屬性效用值排序按照從小到達(dá)依次對(duì)屬性進(jìn)行自頂向下的分割，若數(shù)據(jù)記錄有N條，建立分類樹的時(shí)間復(fù)雜度為O（N log N）。

2.3.2 空間復(fù)雜度分析

基于本文所提出的算法，首先申請(qǐng)一個(gè)長(zhǎng)度為M的集合，用于存放按照效用值排序后的準(zhǔn)標(biāo)識(shí)屬性，其所需要的空間復(fù)雜度為O（1）；其次，樹結(jié)構(gòu)需要的空間復(fù)雜度取決于該棵樹的節(jié)點(diǎn)個(gè)數(shù)，其有M個(gè)準(zhǔn)標(biāo)識(shí)屬性，每個(gè)準(zhǔn)標(biāo)識(shí)屬性有n個(gè)值，對(duì)于屬性層次泛化樹所需要的空間復(fù)雜度為M×O（n）；最后，對(duì)于用于數(shù)據(jù)發(fā)布的分類樹，總共N條記錄，所需要的空間復(fù)雜度為O（N）。

3 實(shí)驗(yàn)數(shù)據(jù)分析

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

實(shí)驗(yàn)采用MIMIC-Ⅲ（medical information mart for intensive care）^[20]數(shù)據(jù)集，該數(shù)據(jù)集是一個(gè)重癥醫(yī)學(xué)數(shù)據(jù)庫(kù)，包含大型三級(jí)護(hù)理醫(yī)院重癥監(jiān)護(hù)病房住院患者的相關(guān)信息。數(shù)據(jù)包括生命體征、藥物、實(shí)驗(yàn)室測(cè)量、觀察結(jié)果和由護(hù)理人員繪制的記錄、流體平衡、程序代碼、診斷代碼、成像報(bào)告、住院時(shí)間、生存數(shù)據(jù)等。該數(shù)據(jù)集自2016年發(fā)布以來，已被引用1 400余次，對(duì)于研究醫(yī)療數(shù)據(jù)相關(guān)方向人員而言是個(gè)優(yōu)質(zhì)的數(shù)據(jù)集。該數(shù)據(jù)集包含近6萬(wàn)條ICU住院記錄，按照記錄內(nèi)容不同，共包含26個(gè)數(shù)據(jù)表，有病人登記表（patients）、處方信息表（prescriptions）、住院表（admissions）、醫(yī)務(wù)人員信息表（caregivers）等。本實(shí)驗(yàn)選取病人登記表、住院表和處方信息表中的部分屬性作為實(shí)驗(yàn)數(shù)據(jù)。其中，選取病人登記表中的患者編號(hào)、性別、出生日期，住院表中的患者編號(hào)、病案號(hào)、入院時(shí)間、語(yǔ)種、宗教信仰、婚姻狀況、種族，處方信息表中的患者編號(hào)、藥物說明作為準(zhǔn)標(biāo)識(shí)符屬性；選取處方信息表中的藥物類型作為敏感屬性，這三個(gè)表通過主鍵患者編號(hào)連接成一個(gè)表，方便數(shù)據(jù)處理。

本文算法由Python編程語(yǔ)言編寫，利用PyCharm集成環(huán)境開發(fā)實(shí)現(xiàn)。實(shí)驗(yàn)的硬件環(huán)境為AMD Ryzen 5 4600H with Radeon Graphics 3.00 GHz處理器，16 GB內(nèi)存，Windows操作系統(tǒng)。

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

本節(jié)將本文所提出的AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法與傅繼彬等人^[21]提出的MAXGDDP（最大值索引屬性選擇數(shù)據(jù)發(fā)布）算法和曹惠瑞^[9]提出的RF-based DP算法分別從不同的衡量標(biāo)準(zhǔn)進(jìn)行對(duì)比實(shí)驗(yàn)，利用控制變量法分別從以下幾個(gè)方面進(jìn)行對(duì)比：

a）分類準(zhǔn)確度。圖2中給出了在相同隱私預(yù)算下本文算法與MAXGDDP算法在分類準(zhǔn)確率上的比較。從圖中不難看出，在隱私預(yù)算取值相同的情況下，本文算法在分類準(zhǔn)確率上略優(yōu)于MAXGDDP算法，并且隨著隱私預(yù)算的增加，兩種算法在分類準(zhǔn)確率上都有所提高。

b）執(zhí)行時(shí)間。圖3中給出了兩個(gè)算法的執(zhí)行時(shí)間隨數(shù)據(jù)量的變化。從圖3所知，隨著數(shù)據(jù)量的增大，MAXGDDP 算法所需要的時(shí)間比本文算法需要的時(shí)間更多。因?yàn)殡S著數(shù)據(jù)量的增大，MAXGDDP算法需要更多的時(shí)間計(jì)算最大記錄數(shù)作為分割點(diǎn)的度量值，從而導(dǎo)致消耗了較多的時(shí)間。由此可看出，隨著數(shù)據(jù)量的增加，兩種算法的執(zhí)行效率都有所下降，但MAXGDDP算法的效率下降得更加明顯，因?yàn)樵谙嗤瑪?shù)據(jù)增量的情況下，MAXGDDP的時(shí)間變化更快（斜率較大），所以效率下降得更明顯。

c）泛化信息損失度。本文通過泛化信息損失度衡量算法的隱私保護(hù)程度。圖4中給出了在相同的隱私預(yù)算不同的細(xì)分層次下信息損失度的變化。由圖可以看出，隨著細(xì)分層次的逐漸增加，兩種算法的泛化信息損失度也在不斷增加，但從整體來看，本文算法的損失度優(yōu)于MAXGDDP算法。

d）絕對(duì)誤差。本文引入絕對(duì)誤差衡量算法的有效性。圖5（a）～（c）分別是隱私預(yù)算ε取值為1、0.5、0.1的情況下，AUR-Tree算法和RF-based DP算法的絕對(duì)誤差大小的變化。文獻(xiàn)[9]將RF-based DP與經(jīng)典的LP算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)論證明RF-based DP算法的絕對(duì)誤差均小于LP算法，因此本文選取RF-based DP算法進(jìn)行對(duì)比實(shí)驗(yàn)。針對(duì)查詢區(qū)間的間隔，本文選擇50作為查詢范圍間隔。由圖中的絕對(duì)誤差大小可以看出，隨著查詢區(qū)間的逐漸增加，RF-based DP和本文的AUR-Tree算法的絕對(duì)誤差都在增加，但是在查詢區(qū)間和隱私預(yù)算相同的情況下，本文算法的絕對(duì)誤差都比RF-based DP算法的值小。由此可以看出，本文算法可以有效地提高數(shù)據(jù)發(fā)布的準(zhǔn)確性和有效性，可以降低Laplace噪聲對(duì)數(shù)據(jù)發(fā)布的影響。進(jìn)一步觀察可以得出隨著隱私預(yù)算的減少，這種影響在逐漸降低。通過對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，相比于RF-based DP算法，AUR-Tree算法能更好地保證數(shù)據(jù)的有效性和可用性。

4 結(jié)束語(yǔ)

醫(yī)療數(shù)據(jù)在數(shù)據(jù)發(fā)布與共享過程中容易泄露患者隱私與敏感信息，給患者造成精神困擾，嚴(yán)重的會(huì)造成社會(huì)恐慌。針對(duì)上述問題，本文提出了AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法， AUR-Tree將差分隱私及樹模型的優(yōu)勢(shì)完美地結(jié)合，采用自頂向下迭代分割的思想，對(duì)每個(gè)準(zhǔn)標(biāo)識(shí)屬性構(gòu)建屬性層次泛化樹。在此基礎(chǔ)上，利用AUR選擇最佳的分裂屬性進(jìn)行迭代分割構(gòu)造分類樹，然后利用類等差法為樹的每一層分配相應(yīng)的隱私預(yù)算使其滿足差分隱私的序列組合性和并行組合性，最后將葉子節(jié)點(diǎn)添加了Laplace噪聲并進(jìn)行數(shù)據(jù)發(fā)布。通過對(duì)比實(shí)驗(yàn)可以看出，AUR-Tree差分隱私數(shù)據(jù)發(fā)布算法有分類上較為準(zhǔn)確、程序執(zhí)行時(shí)間消耗短以及泛化信息損失度小的優(yōu)勢(shì)。

參考文獻(xiàn)：

［1］侯夢(mèng)薇，衛(wèi)榮，蘭欣，等.基于差分隱私的醫(yī)療大數(shù)據(jù)隱私保護(hù)模型應(yīng)用研究[J].中國(guó)數(shù)字醫(yī)學(xué)，2019，14（12）：86-88.（Hou Mengwei，Wei Rong，Lan Xin，et al.Research on privacy protection model and application of medical big data based on differential privacy[J].China Digital Medicine，2019，14（12）：86-88.）

[2]Sweeney L.k-anonymity：a model for protecting privacy[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems，2002，10（5）：557-570.

[3]Machanavajjhala A，Kifer D，Gehrke J，et al.l-diversity：privacy beyond k-anonymity[J].ACM Trans on Knowledge Discovery from Data，2007，1（1）：3-es.

[4]Rebollo-Monedero D，F(xiàn)orne J，Domingo-Ferrer J.From t-closeness-like privacy to post randomization via information theory[J].IEEE Trans on Knowledge and Data Engineering，2009，22（11）：1623-1636.

[5]鄒勁松，李芳.基于可伸縮l-多樣性的大數(shù)據(jù)發(fā)布隱私保護(hù)[J].計(jì)算機(jī)應(yīng)用研究，2021，38（2）：564-566，571.（Zou Jinsong，Li Fang.Big data publishing privacy protection based on scalable l-diversity[J].Application Research of Computers，2021，38（2）：564-566，571.）

[6]史漢發(fā)，王俊峰，陳建，等.醫(yī)療數(shù)據(jù)發(fā)布中多敏感屬性隱私保護(hù)算法[J].四川大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，51（4）：731-737.（Shi Hanfa，Wang Junfeng，Chen Jian，et al.Privacy protecting algorithm for multiple sensitive properties in medical data publishing[J].Journal of Sichuan University：Natural Science Edition，2014，51（4）：731-737）

[7]林國(guó)濱.面向電子病例數(shù)據(jù)發(fā)布的隱私保護(hù)算法研究[D].福州：福建師范大學(xué)，2017.（Lin Guobin.Research on privacy protection algorithm for electronic medical record data publishing[D].Fuzhou：Fujian Normal University，2017.）

[8]丁有偉，王鵬，胡孔法，等.一種面向中醫(yī)藥臨床數(shù)據(jù)發(fā)布的隱私保護(hù)算法[J].世界科學(xué)技術(shù)：中醫(yī)藥現(xiàn)代化，2021，23（7）：2393-2401.（Ding Youwei，Wang Peng，Hu Kongfa，et al.A privacy preserving algorithm for traditional Chinese medicine clinical data releasing[J].Modernization of Traditional Chinese Medicine and Mate-rial Medica：World Science and Technology，2021，23（7）：2393-2401.）

[9]曹惠瑞.醫(yī)療數(shù)據(jù)發(fā)布共享中的隱私保護(hù)研究[D].石家莊：石家莊鐵道大學(xué)，2020.（Cao Huirui.Research on privacy protection in medical data publishing and sharing[D].Shijiazhuang：Shijiazhuang Tiedao University，2020.）

[10]陳虹云，王杰華，胡兆鵬，等.面向醫(yī)療數(shù)據(jù)發(fā)布的動(dòng)態(tài)更新隱私保護(hù)算法[J].計(jì)算機(jī)科學(xué)，2019，46（1）：206-211.（Chen Hongyun，Wang Jiehua，Hu Zhaopeng，et al.Privacy preserving algorithm based on dynamic update in medical data publishing[J].Computer Science，2019，46（1）：206-211.）

[11]Dwork C.Differential privacy[C]//Proc of the 33rd International Colloquium on Automata，Languages and Programming.Boston：Springer ，2006：1-12.

[12]Hardt M，Ligett K，McSherry F.A simple and practical algorithm for differentially private data release[EB/OL].（2012-03-15）.http：//doi.org/10.48550/arxiv.1012.4763.

[13]Dwork C，Roth A.The algorithmic foundations of differential privacy[J].Foundations and Trends in Theoretical Computer Science，2014，9（3-4）：211-407.

[14]唐海霞，楊庚，白云璐.自適應(yīng)差分隱私預(yù)算分配策略的直方圖發(fā)布算法[J].計(jì)算機(jī)應(yīng)用研究，2020，37（7）：1952-1957，1963.（Tang Haixia，Yang Geng，Bai Yunlu.Histogram publishing algorithm based on adaptive privacy budget allocation strategy under differential privacy[J].Application Research of Computers，2020，37（7）：1952-1957，1963.）

[15]李遠(yuǎn)航，陳先來，劉莉，等.面向差分隱私保護(hù)的隨機(jī)森林算法[J].計(jì)算機(jī)工程，2020，46（1）：93-101.（Li Yuanhang，Chen Xianlai，Liu Li，et al.Random forest algorithm for differential privacy protection[J].Computer Engineering，2020，46（1）：93-101.）

[16]白云璐.醫(yī)療大數(shù)據(jù)中應(yīng)用差分隱私保護(hù)[J].電子技術(shù)與軟件工程，2017（24）：196-197.（Bai Yunlu.Application of differential privacy protection in medical big data[J].Electronic Technology and Software Engineering，2017（24）：196-197.）

[17]熊平，朱天清，王曉峰.差分隱私保護(hù)及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（1）：101-122.（Xiong Ping，Zhu Tianqing，Wang Xiaofeng.A survey on differential privacy and applications[J].Chinese Journal of Computers，2014，37（1）：101-122.）

[18]鄧蔚，陳秀婷，張清華，等.基于樹模型的差分隱私保護(hù)算法[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2020，32（5）：848-856.（Deng Wei，Chen Xiuting，Zhang Qinghua，et al.Differential privacy protection algorithm based on tree model[J].Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition，2020，32（5）：848-856.）

[19]Piao Chunhui，Shi Yaijuan，Yan Jiaqi，et al.Privacy-preserving go-vernmental data publishing：a fog-computing-based differential privacy approach[J].Future Generation Computer Systems，2019，90：158-174.

[20]Johnson Alistair E W，Pollard Tom J，Shen Lu，et al.MIMIC-Ⅲ，a freely accessible critical care database.[J].Scientific Data，2016，3（1）：article No.160035.

[21]傅繼彬，張嘯劍，丁麗萍.MAXGDDP：基于差分隱私的決策數(shù)據(jù)發(fā)布算法[J].通信學(xué)報(bào)，2018，39（3）：136-146.（Fu Jibin，Zhang Xiaojian，Ding Liping.MAXGDDP：decision data release with differential privacy[J].Journal on Communications，2018，39（3）：136-146.）