王慧婷，陳燕俐，彭春春

(南京郵電大學(xué) 計算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院， 江蘇 南京 210023)

數(shù)據(jù)挖掘技術(shù)利用算法能夠從海量信息中提取潛在的有效信息和知識，目前已被應(yīng)用到各行業(yè)中，例如：疫情監(jiān)測、天氣預(yù)報、股票交易、智慧城市構(gòu)建等。 但與此同時，大量敏感信息的披露將給用戶帶來無法估量的威脅和損失，因此在進(jìn)行數(shù)據(jù)挖掘和分析的同時，需要對用戶個人提供的數(shù)據(jù)進(jìn)行隱私保護(hù)。 當(dāng)前主流的隱私保護(hù)技術(shù)主要分為3 類［1］：基于加密的隱私保護(hù)技術(shù)、基于匿名的隱私保護(hù)技術(shù)以及基于失真的隱私保護(hù)技術(shù)。 由于大數(shù)據(jù)的大規(guī)模、多樣性和高速性的特點(diǎn)，加密技術(shù)在加解密和驗證環(huán)節(jié)中會帶來較大的計算開銷代價和通信代價；而匿名發(fā)布的方法存在數(shù)據(jù)損失和數(shù)據(jù)可用性較低的弊端，不利于數(shù)據(jù)的挖掘和分析。 基于失真的隱私保護(hù)技術(shù)通過擾動原始數(shù)據(jù)，使攻擊者無法進(jìn)行重構(gòu)，典型的方法即差分隱私技術(shù)（Differential Privacy，DP）［2］。 差分隱私技術(shù)完全獨(dú)立于攻擊者的背景知識，通過集中收集后添加隨機(jī)噪聲使敏感數(shù)據(jù)失真后再發(fā)布，添加噪聲后的某些數(shù)據(jù)仍然保持原有數(shù)據(jù)的某些統(tǒng)計特性，因而更適合大數(shù)據(jù)下對數(shù)據(jù)進(jìn)行隱私保護(hù)。

傳統(tǒng)的差分隱私技術(shù)（中心化差分隱私）需要可信的第三方數(shù)據(jù)收集者集中收集數(shù)據(jù)，再進(jìn)行隱私保護(hù)，然而在實際應(yīng)用中，即使第三方數(shù)據(jù)收集者宣稱不會竊取和泄露用戶的敏感信息，用戶的隱私依舊得不到保障。 2011 年，Kasiviswanatha 等［3］提出的本地化差分隱私（Local Differential Privacy，LDP）技術(shù)，將數(shù)據(jù)的隱私化處理過程從第三方數(shù)據(jù)收集者轉(zhuǎn)移到每個用戶上，可以在不需要信任第三方數(shù)據(jù)收集者的情況下，在本地環(huán)境下對個人敏感數(shù)據(jù)加噪實現(xiàn)隱私保護(hù)，同時從宏觀角度保證數(shù)據(jù)收集者可正確地推斷出群體統(tǒng)計信息。 這既保證了群體統(tǒng)計信息的相對準(zhǔn)確性，又保護(hù)了個人的原始數(shù)據(jù)，解決了用戶隱私數(shù)據(jù)被不可信第三方外包管理的問題，因而LDP 適用場景更廣，實用程度更高，被廣泛應(yīng)用在數(shù)據(jù)收集、統(tǒng)計和分析的領(lǐng)域。

根據(jù)挖掘的模式，數(shù)據(jù)挖掘技術(shù)可分為：分類、聚類、關(guān)聯(lián)分析和異常檢測等，其中分類算法是數(shù)據(jù)挖掘研究領(lǐng)域中基礎(chǔ)和核心技術(shù)之一［4］。 在分類算法中，首先是學(xué)習(xí)階段，通過分析一個訓(xùn)練數(shù)據(jù)集，找到一個描述并區(qū)分?jǐn)?shù)據(jù)集的分類模型即分類器；其次是使用該分類模型對未知類標(biāo)記的樣本，即新的數(shù)據(jù)集進(jìn)行預(yù)測分類。 常用的分類算法包括決策樹、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)、邏輯回歸、貝葉斯分類器等。 其中的樸素貝葉斯分類（Naive Bayes Classifier，NBC）是一種基于概率，對未標(biāo)記的數(shù)據(jù)進(jìn)行分類的簡單、高效有監(jiān)督的學(xué)習(xí)方法［5］。 NBC假定了模型的變量遵循某種概率分布，并根據(jù)概率分布和觀察數(shù)據(jù)推理，從而得出最優(yōu)決策。 相較于其他分類算法，由于其核心是貝葉斯定理，因此有著扎實的數(shù)學(xué)基礎(chǔ)和較穩(wěn)定的分類能力。 由于在訓(xùn)練階段無需迭代，時間復(fù)雜度相對較低；并且由于屬性條件獨(dú)立性的假設(shè)，建模過程中運(yùn)算速度較高，處理數(shù)據(jù)量較大時更為簡單高效，因此NBC 被廣泛應(yīng)用在計算機(jī)視覺、模式識別、自然語言處理等領(lǐng)域。 為了使數(shù)據(jù)的分析結(jié)果更加準(zhǔn)確，NBC 通常需要足夠多的數(shù)據(jù)用于訓(xùn)練，然而訓(xùn)練數(shù)據(jù)的收集涉及了用戶的隱私信息，可能帶來隱私安全問題，因此針對樸素貝葉斯分類的差分隱私保護(hù)相關(guān)方案陸續(xù)被提出，但大部分都集中在中心化環(huán)境，即第三方服務(wù)器可信的情況［6－11］。 2020 年，Yilmaz 等［12］首次設(shè)計了基于本地差分隱私保護(hù)的貝葉斯分類算法，算法能支持離散和連續(xù)屬性數(shù)據(jù)，在訓(xùn)練分類器的同時保護(hù)了用戶數(shù)據(jù)隱私，但時間開銷較高。 2021 年，Xue 等［13］也利用本地差分隱私設(shè)計了訓(xùn)練貝葉斯分類器的方案，使用聯(lián)合分布來計算條件概率，由于每次計算中隨機(jī)采樣原始用戶數(shù)據(jù)的單個屬性值，因此能夠有效降低通信代價，然而當(dāng)屬性較多時，方案存在采樣率過低，統(tǒng)計結(jié)果會產(chǎn)生較大采樣誤差的問題。

針對目前基于本地化差分隱私的貝葉斯分類算法存在時間開銷和通信代價較高，以及采樣率過低引起采樣誤差的問題，本文設(shè)計了一個高效的基于本地差分隱私的頻數(shù)預(yù)測算法，并在此基礎(chǔ)上，構(gòu)建了準(zhǔn)確率高并可有效保護(hù)用戶個體隱私數(shù)據(jù)的樸素貝葉斯分類器。 本文的主要貢獻(xiàn)如下：

（1） 設(shè)計了一種基于本地差分隱私的頻數(shù)預(yù)測算法LDPbayes?FO。 算法的用戶端擾動機(jī)制基于指數(shù)機(jī)制設(shè)計，將效用函數(shù)定義為輸入和輸出集合之間是否有交集，擾動輸出的概率由效用函數(shù)決定。服務(wù)器端對數(shù)據(jù)聚合后還原出各編碼值相應(yīng)的頻數(shù)。 LDPbayes?FO 算法能夠在對用戶提供的訓(xùn)練數(shù)據(jù)進(jìn)行隱私保護(hù)的同時，很好地保證訓(xùn)練數(shù)據(jù)統(tǒng)計的質(zhì)量，并有效提高數(shù)據(jù)統(tǒng)計結(jié)果的效用。

（2） 將LDPbayes?FO 與貝葉斯分類算法相結(jié)合，提出一種基于本地化差分隱私的貝葉斯分類方案——LDPBayes。 服務(wù)器端根據(jù)聚合后統(tǒng)計的各編碼值頻數(shù)，計算出條件概率和類標(biāo)簽概率，構(gòu)建出一個有效安全的樸素貝葉斯分類器。 該分類器根據(jù)最大似然推理原則對待分類的數(shù)據(jù)進(jìn)行分類預(yù)測。LDPBayes 方案相較于其他基于差分隱私的貝葉斯分類方案，將隱私化處理從服務(wù)器端轉(zhuǎn)移到了本地，因此隱私保護(hù)的程度更高；同時相較于基于本地差分隱私的貝葉斯分類方案，分類準(zhǔn)確率更高，且時間性能更優(yōu)。

（3） 在多個真實的數(shù)據(jù)集上對LDPBayes 方案進(jìn)行實驗和評估，結(jié)果表明LDPBayes 方案相比與其他方案在分類準(zhǔn)確率上均有不同程度的提高，同時避免了由于采樣帶來的統(tǒng)計結(jié)果誤差。 在相同大小的訓(xùn)練集上，由于頻數(shù)預(yù)測算法對數(shù)據(jù)隱私處理的時間效率更高，可縮短構(gòu)建貝葉斯分類器的時間，并且通信代價更小。

1 相關(guān)工作

2006 年， Dwork 首次提出了差分隱私（Differential Privacy，DP）的保護(hù)框架［2］，作為一種可嚴(yán)格證明的隱私保護(hù)模型，嚴(yán)格定義了隱私保護(hù)的強(qiáng)度，任意一條記錄的添加或刪除都不會影響最終的查詢結(jié)果。 2009 年，Mcsherry 等［14］提出一套提供差分隱私保護(hù)的應(yīng)用框架 PINQ （Privacy Integrated Queries）。 差分隱私在假設(shè)攻擊者具有任意背景知識和計算能力的前提下仍提供可證明的隱私保護(hù)，從而解決了層出不窮的新型攻擊方式所帶來的隱患；同時建立了隱私保護(hù)的嚴(yán)格證明框架和屬性定量關(guān)系。 由于這些優(yōu)勢，專家們將差分隱私擴(kuò)展到數(shù)據(jù)挖掘領(lǐng)域，從而避免隱私數(shù)據(jù)的泄露，主要的應(yīng)用場景有回歸、分類、聚類分析和頻繁項挖掘等［15］。 其中，分類器作為分類分析中一個具體實現(xiàn)，引入差分隱私算法后在實現(xiàn)分類任務(wù)的同時為保護(hù)數(shù)據(jù)提供者的隱私提供了解決方案。 Zhang等［16］提出了一種滿足差分隱私的邏輯回歸方案，將損失函數(shù)的各項系數(shù)加入噪聲從而保證其滿足差分隱私。 Jagannathan 等［17］應(yīng)用隨機(jī)決策樹算法，提出了完全訪問模式下的差分隱私保護(hù)隨機(jī)決策樹分類器構(gòu)建方法。 Rubinstein 等［18］探討了在保護(hù)訓(xùn)練數(shù)據(jù)隱私的同時發(fā)布支持向量機(jī)（SVM）分類器。

2013 年，Vaidya 等［6］首次將差分隱私的保護(hù)機(jī)制引入到樸素貝葉斯分類算法，通過計算分類器的全局靈敏度來添加拉普拉斯噪聲［19］，從而保證分類器滿足差分隱私，然而該算法僅僅假設(shè)了連續(xù)屬性服從高斯分布的條件，同時采用全局靈敏度可能存在的數(shù)據(jù)集中個人對結(jié)果的影響較大導(dǎo)致添加到輸出中噪聲較高的問題。 2015 年，Huai 等［7］將加密技術(shù)和差分隱私相結(jié)合，在分布式環(huán)境下能夠以較低的計算成本和通信代價對貝葉斯分類器進(jìn)行隱私保護(hù)。 2018 年，Li 等［8］提出了一種多數(shù)據(jù)源差分隱私貝葉斯分類算法，使得訓(xùn)練者在不同數(shù)據(jù)所有者共同提供的數(shù)據(jù)集上訓(xùn)練樸素貝葉斯分類器，因此無需一個可信的收集器。 2019 年，Tang 等［9］對離散屬性的頻數(shù)中加入拉普拉斯噪聲，對連續(xù)屬性假設(shè)了其遵循高斯分布、拉普拉斯分布和對數(shù)正態(tài)分布的情況下，將均值和標(biāo)準(zhǔn)差參數(shù)加入拉普拉斯噪聲，計算先驗概率和條件概率，從而構(gòu)建滿足差分隱私的貝葉斯分類器。 2020 年，Tang 等［10］提出了基于小波變換的差分隱私保護(hù)貝葉斯分類方案，對原始數(shù)據(jù)進(jìn)行小波變換，得到指定分解層的非零近似系數(shù)，從而達(dá)到數(shù)據(jù)降維的目的，再將拉普拉斯噪聲添加到降維數(shù)據(jù)集中，對噪聲數(shù)據(jù)集執(zhí)行貝葉斯分類。2021 年，Zafarani 等［11］針對文獻(xiàn)［6］可能帶來過高噪聲的問題，將連續(xù)屬性采用了平滑靈敏度，離散屬性仍然采用了全局靈敏度，并使用柯西分布的噪聲對參數(shù)擾動后再構(gòu)建貝葉斯分類器，相較于文獻(xiàn)［6］能夠顯著提高分類準(zhǔn)確率，但也帶來了更高的計算成本。

2011 年，本地化差分隱私（Local Differential Privacy，LDP）［3］在中心化差分隱私的基礎(chǔ)上首次提出，將數(shù)據(jù)的擾動處理從服務(wù)器端轉(zhuǎn)移到了客戶端，從而消除了不可信第三方服務(wù)器帶來的隱私泄露威脅。 在中心化差分隱私中，用戶之間通常不存在交互關(guān)系，而收集用戶數(shù)據(jù)的聚合器要求對于用戶是可信任的，這使得在實際應(yīng)用場景中難以落地。 而本地化差分隱私中，用戶的隱私化處理從服務(wù)器端轉(zhuǎn)移到了客戶端，用戶將數(shù)據(jù)編碼成特定的格式，經(jīng)過正向或負(fù)向的擾動，再發(fā)送給不可信任的聚合器，聚合器收到的每條用戶信息幾乎是全噪聲的，這保證了用戶數(shù)據(jù)在服務(wù)器端不會被泄露。 擾動后的大量用戶信息通過聚合后解碼估計和校正，從而收集到一個有效、無偏的統(tǒng)計結(jié)果，通常是頻數(shù)或者均值。

2020 年，Yilmaz 等［12］首次將本地差分隱私和樸素貝葉斯分類算法相結(jié)合，應(yīng)用了多個頻率預(yù)測算法收集擾動數(shù)據(jù)，將擾動數(shù)據(jù)聚合后根據(jù)統(tǒng)計信息計算出先驗概率和條件概率從而構(gòu)建分類器；算法適用于離散和連續(xù)屬性，但擾動算法帶來的計算開銷 較 高。 2021 年，Xue 等［13］基 于k?Subset 算法［20］設(shè)計了LDP 下的聯(lián)合分布算法，將該算法應(yīng)用于計算貝葉斯分類中的條件概率，該方案能有效降低通信代價，但當(dāng)屬性數(shù)據(jù)較多時則會帶來采樣誤差。

2 預(yù)備知識

2.1 本地化差分隱私

定義1ε?本地差分隱私［3］：給定一個隱私算法M，定義域Dom（M）和值域Ran（M），在算法M中任 意 兩 條 記 錄x和x′， （x∈Dom（M），x′ ∈Dom（M）），得到相同的輸出結(jié)果y（y∈Ran（M））滿足以下不等式，則算法M滿足ε?本地差分隱私。

Pr［M（x）＝y(tǒng)］ ≤eε× Pr［M（x′）＝y(tǒng)］ （1）

式中，Pr［·］ 表示事件發(fā)生的概率，參數(shù)ε表示隱私預(yù)算，隱私預(yù)算ε越小，輸出相同結(jié)果的概率越大，說明算法M的隱私保護(hù)程度越高。

定理1 和定理2 給出了本地差分隱私的兩個組合特性。

2.2 貝葉斯分類的相關(guān)理論

貝葉斯分類算法是基于統(tǒng)計學(xué)原理的一個分類算法。 采用了屬性條件獨(dú)立性假設(shè)，即對于已知類別，假設(shè)所有屬性之間相互獨(dú)立。

式中，N表示訓(xùn)練集D中所有可能的標(biāo)簽類別數(shù)，Nt表示第t個屬性可能的取值數(shù)。

3 基于本地差分隱私的貝葉斯分類方案LDPBayes

3.1 方案概述

本系統(tǒng)包含一個第三方服務(wù)器和m個用戶，即數(shù)據(jù)提供者，用戶集U＝｛u1，u2，…，um｝。 設(shè)系統(tǒng)屬性集A＝｛A0，A1，…，Ah－1｝，其中屬性數(shù)量｜A ｜＝h，每種屬性Aj對應(yīng)的屬性值數(shù)為nj。 類標(biāo)簽集C，其中類標(biāo)簽數(shù)量｜C ｜＝k。 每個用戶ui向服務(wù)器提供個人數(shù)據(jù)，用于分類器的訓(xùn)練。ui的個人數(shù)據(jù)包括了h個屬性值的集合｛Ri，0，Ri，1，…，Ri，h－1｝ 和1個類標(biāo)簽Ci。 本文主要考慮屬性值是離散的情況，對于連續(xù)屬性，可使用對連續(xù)數(shù)據(jù)離散化處理中常規(guī)的等寬法，將取值范圍劃分成等寬的多個區(qū)間，為每個區(qū)間設(shè)置一個對應(yīng)的屬性值，從而將連續(xù)變量轉(zhuǎn)換成多個離散值。

圖1 LDPBayes 分類方案的框架

3.2 LDPbayes?FO 頻數(shù)預(yù)測算法

LDPbayes?FO 頻數(shù)預(yù)測算法共分為編碼、擾動、聚合3 個步驟。 其中，用戶端執(zhí)行前兩個步驟，將數(shù)據(jù)完成編碼后利用隨機(jī)化響應(yīng)機(jī)制擾動，擾動后的數(shù)據(jù)發(fā)送給服務(wù)器。 服務(wù)器執(zhí)行第三個步驟，對擾動的數(shù)據(jù)估計和校正還原。

3.2.1 編碼

用戶首先將向服務(wù)器提供用于分類器訓(xùn)練的個人數(shù)據(jù)，包括了類標(biāo)簽和屬性值，并編碼成整數(shù)，目的是減少通信代價并降低算法耦合性。 具體編碼方式如下：

定理4 得證。

聚合后，估計值c～（v） 中可能會出現(xiàn)負(fù)數(shù)的情況，為滿足非負(fù)性，將這些值置為0，并對所有的頻數(shù)預(yù)測做歸一化處理即可［23］。

3.3 LDPBayes 貝葉斯分類方案

LDPBayes 貝葉斯分類方案包括訓(xùn)練和測試兩個部分。 訓(xùn)練階段通過計算類標(biāo)簽的概率和屬性的條件概率來構(gòu)建分類器；在測試階段，可對已知屬性值但未知類別的數(shù)據(jù)分類和預(yù)測。

（1） 訓(xùn)練階段

①計算類標(biāo)簽的概率

4 性能分析和實驗仿真

4.1 方案性能比較

本方案與其他基于差分隱私的貝葉斯分類方案性能比較結(jié)果如表1 所示。 其中文獻(xiàn)［6－8］方案是采用傳統(tǒng)的差分隱私技術(shù)，即中心化差分隱私，需要可信的第三方數(shù)據(jù)收集者集中收集數(shù)據(jù)，再進(jìn)行隱私保護(hù)。 其中，文獻(xiàn)［6］的方案在假設(shè)連續(xù)屬性滿足高斯分布的情況下，通過計算全局敏感度來添加拉普拉斯噪聲，使其滿足差分隱私模型；然而該方案面向單一數(shù)據(jù)源，如果沒有可信任的聚合器，則不能在分布式環(huán)境中直接使用它。 文獻(xiàn)［7］的方案中考慮到來自多個數(shù)據(jù)源的訓(xùn)練樣本，各參與方首先對自己的數(shù)據(jù)添加適當(dāng)?shù)脑肼暎缓蠡诎踩喾接嬎悖⊿ecure Multi?Party Computation，SMPC）理論設(shè)計安全求和協(xié)議，得到所有參與方的噪聲數(shù)據(jù)的全局統(tǒng)計求和查詢結(jié)果；該方案能夠抵御不安全的通信信道造成的竊聽攻擊，在分布式的場景中保證了多個參與方的數(shù)據(jù)安全；然而方案將數(shù)據(jù)的統(tǒng)計信息設(shè)置為公開，因此內(nèi)部攻擊者很容易知道所持有的樣本是否包含特定的值。 文獻(xiàn)［8］的方案中，使用同 態(tài) 加 密（Homomorphic Encryption， HE） 中 的Paillier 算法對提供者的數(shù)據(jù)進(jìn)行隱私保護(hù)，在服務(wù)器端的聚合器中通過拉普拉斯機(jī)制對數(shù)據(jù)集添加噪聲使得模型滿足差分隱私的定義，能夠保證數(shù)據(jù)統(tǒng)計信息既不被外部對手泄露，也不對內(nèi)部對手泄露；然而同態(tài)加密所帶來的計算開銷較高。 與文獻(xiàn)［6－8］相比，本方案LDPBayes 是基于本地化差分隱私技術(shù)，將隱私化的處理從服務(wù)器端轉(zhuǎn)移到了用戶本地，服務(wù)器端收集到的每條用戶信息幾乎是全噪聲的，這保證了用戶數(shù)據(jù)不會在服務(wù)器端被泄露，因此隱私保護(hù)的程度更高。

表1 方案性能對比

文獻(xiàn)［12］方案和本方案LDPBayes 都是基于本地化差分隱私技術(shù)，可以在不需要信任第三方數(shù)據(jù)收集者的情況下，在本地環(huán)境下對個人敏感數(shù)據(jù)加噪實現(xiàn)隱私保護(hù)。 其中文獻(xiàn)［13］提出一個滿足本地差分隱私的計算聯(lián)合分布算法JESS，并將其應(yīng)用于NBC 條件概率的計算，該方案在每次計算中需隨機(jī)采樣原始用戶數(shù)據(jù)的一個屬性值，當(dāng)屬性較多時，采樣率過低可能導(dǎo)致統(tǒng)計結(jié)果帶來較大的采樣誤差。 相比之下LDPBayes 無需采樣，從而減少了采樣帶來了統(tǒng)計效率低下和估計誤差較高的問題。

文獻(xiàn)［12］ 利 用DE（Direct Encoding）、OUE（Optimized Unary Encoding）等LDP 的頻數(shù)預(yù)測算法［24］與NBC 相結(jié)合進(jìn)行設(shè)計。 在DE 算法中，對于含有n個元素的輸入集合si， 隱私預(yù)算ε將平均分成n份，每一份隱私預(yù)算ε／n作用到集合si中的每一個元素。 而現(xiàn)有的研究工作［25－27］表明，簡單地將隱私預(yù)算均分的方法不能完全利用好隱私預(yù)算，可能會在擾動過程中帶來大量的噪聲，從而降低數(shù)據(jù)統(tǒng)計的精確度。 而在LDPbayes?FO 算法中，當(dāng)給定隱私預(yù)算ε，將待擾動的集合si作為一個整體，經(jīng)過基于指數(shù)機(jī)制設(shè)計的擾動算法后輸出集合ti， 通過設(shè)定的效用函數(shù)決定集合ti的輸出概率，不再將隱私預(yù)算ε簡單地均分給集合ti中的單個元素，相較于直接均分隱私預(yù)算的方法降低了擾動過程中帶來的噪聲，從而提高了在數(shù)據(jù)統(tǒng)計中的效用。

在OUE 算法中，需將隱私數(shù)據(jù)v∈D（D為輸入集，輸入集中共有l(wèi)種不同的輸入值）構(gòu)建成長度為l，第v位為1，其余位為0 的二進(jìn)制的向量V＝［0，…，1，…，0］，需對向量中每一位進(jìn)行隨機(jī)擾動，因此會帶來較高的通信代價。 相比之下，LDPBayes 無需對輸入集的元素重新構(gòu)建成二進(jìn)制向量，因此能夠有效降低通信代價，算法的時間開銷也會相應(yīng)減少。

4.2 方案實驗結(jié)果及分析

（1） 實驗配置和數(shù)據(jù)集

實驗環(huán)境為Intel（R） Core（TM） i7?4770HQ，2.20 GHz、16 GB 內(nèi)存、Windows 10 操作系統(tǒng)。 采用了UCI （University of California， Irvine）提供的機(jī)器學(xué)習(xí)庫中的Nursery、Adult、Bank 數(shù)據(jù)集。 其中，Nursery 中包含了托兒所信息，用于預(yù)測托兒所的排名等級；Adult 中包含了1994 年美國人口普查的個體信息，用于預(yù)測個人的年收入情況；Bank 中記錄了葡萄牙銀行機(jī)構(gòu)的電話營銷活動，用于預(yù)測客戶是否會訂閱定期存款。 數(shù)據(jù)集的參數(shù)如表2 所示。

表2 數(shù)據(jù)集的信息描述

實驗中，Adult 數(shù)據(jù)集樣本中存在缺失數(shù)據(jù)，由于缺失數(shù)據(jù)占總樣本的比例極小，因此直接采用刪除法［28］處理。 為防止零概率問題，即某個量x在訓(xùn)練集中沒有出現(xiàn)過，會導(dǎo)致整個實例的概率結(jié)果為0，因此，在實驗中需要引入拉普拉斯平滑機(jī)制解決零概率問題。

（2） 分類效用的比較

目前和本方案相同，采用本地化差分隱私的貝葉斯方案有文獻(xiàn)［12－13］方案。 其中文獻(xiàn)［13］當(dāng)屬性較多時，采樣率過低可能導(dǎo)致統(tǒng)計結(jié)果帶來較大的采樣誤差。 相比之下LDPBayes 無需采樣，從而減少了采樣帶來了統(tǒng)計效率低下和估計誤差較高的問題。 因此，本文在實驗部分沒有與文獻(xiàn)［13］方案進(jìn)行比較，只與文獻(xiàn)［12］?DE、文獻(xiàn)［12］?OUE 進(jìn)行比較。

圖2 展示了實驗中在3 個數(shù)據(jù)集上不同ε取值的情況下各擾動方案的準(zhǔn)確率，ε取值分別為0.2、0.4、0.6、0.8、1、1.5、2、3。

圖2 SNB、［12］?DE、［12］?OUE 和LDPBayes在Adult、Nursery 和Bank 數(shù)據(jù)集上的分類準(zhǔn)確率，其中ε ＝｛0.2，0.4，0.6，0.8，1，1.5，2，3｝

圖2 中水平線SNB 表示基準(zhǔn)正確率，即分類器在沒有擾動情況下的準(zhǔn)確率。 在相同ε取值的情況下，LDPBayes 相較于［12］?DE 和［12］?OUE 的分類準(zhǔn)確率更高。 隨著ε的增大，隱私保護(hù)程度降低，同時數(shù)據(jù)可用性也提高，使得分類準(zhǔn)確率也逐步提高。例如將隱私預(yù)算設(shè)置成ε＝3 時，在3 個數(shù)據(jù)集上均有良好的分類效應(yīng)，分類準(zhǔn)確率的結(jié)果更加接近SNB。 本文的方案LDPBayes 相較于文獻(xiàn)［12］?DE和文獻(xiàn)［12］?OUE 能在分類效用上得到提高，得益于頻數(shù)預(yù)測算法LDPbayes?FO 的設(shè)計，在擾動機(jī)制中，擾動后的輸出概率由指數(shù)機(jī)制的效用函數(shù)決定，設(shè)定的效用函數(shù)對每一種輸出結(jié)果計算出一個效用分值，效用分值越高則輸出概率越高，從而保證數(shù)據(jù)統(tǒng)計的質(zhì)量，有效提高數(shù)據(jù)統(tǒng)計結(jié)果的可用性，體現(xiàn)在貝葉斯分類中能使得分類準(zhǔn)確率提高。 同時，在Bank 數(shù) 據(jù) 集 上 采 用［12］?DE、 ［12］?OUE 和LDPBayes 方案的準(zhǔn)確率都接近SNB，得益于Bank數(shù)據(jù)集的規(guī)模較大，因此統(tǒng)計結(jié)果更接近真實值，算法的實用性也越高。

（3） 隱私保護(hù)程度的比較

差分隱私建立了隱私保護(hù)的嚴(yán)格證明框架和數(shù)學(xué)定量關(guān)系，不同參數(shù)處理下的數(shù)據(jù)集所提供的隱私保護(hù)程度可通過隱私預(yù)算ε量化。 當(dāng)隱私預(yù)算ε一致時，LDPBayes 與文獻(xiàn)［12－13］的方案所達(dá)到的隱私保護(hù)程度也一致。 隱私預(yù)算ε越小，隱私保護(hù)的程度越高，而數(shù)據(jù)的可用性越低。

而相較于中心化差分隱私需要一個可信的第三方數(shù)據(jù)收集者，需要更為苛刻的安全假設(shè)前提，本地化差分隱私將隱私化處理轉(zhuǎn)移到了每個用戶的終端，從而消除了不可信第三方服務(wù)器帶來的隱私泄露的威脅。 在實驗中將LDPBayes 與文獻(xiàn)［6］?DPNBC 方案進(jìn)行了對比。 文獻(xiàn)［6］?DPNBC 采用了傳統(tǒng)的中心化差分隱私的技術(shù)，敏感度依賴于訓(xùn)練樣本的總數(shù)，因此在實驗中以Adult 數(shù)據(jù)集為例，對該數(shù)據(jù)集重新進(jìn)行了整合，訓(xùn)練樣本數(shù)m設(shè)定為5 000、10 000、50 000 和100 000，同時隱私預(yù)算ε取值分別選擇了0.005、0.01、0.05、0.1、0.5、1。

圖3 展示了在不同訓(xùn)練樣本數(shù)下，不同的ε取值下兩種方案的準(zhǔn)確率。 在隱私預(yù)算ε較小的情況下，由于隱私保護(hù)的程度較高，數(shù)據(jù)可用性較低，因此LDPBayes 和文獻(xiàn)［6］?DPNBC 的準(zhǔn)確率均較低，并且LDPBayes 的準(zhǔn)確率相比文獻(xiàn)［6］?DPNBC 更低，這是由于文獻(xiàn)［6］?DPNBC 采用了傳統(tǒng)的中心化差分隱私的技術(shù)，而LDPBayes 是基于本地化差分隱私，無需一個可信的第三方收集器，因此為達(dá)到和中心化差分隱私相似級別的隱私保護(hù)程度則需要引入更大的噪聲。 而隨著隱私預(yù)算ε的增加，LDPBayes 和 文 獻(xiàn)［6］?DPNBC 的 準(zhǔn) 確 率 均 接 近SNB，這是隱私保護(hù)的程度降低，數(shù)據(jù)的可用性提高，因此準(zhǔn)確率逐漸增加并趨于穩(wěn)定，分類結(jié)果更加接近真實結(jié)果。 當(dāng)給定隱私預(yù)算較高時，LDPBayes方案的分類效用較高，在實用性和安全性上能夠取得較好的平衡。

圖3 LDPBayes 和文獻(xiàn)［6］?DPNBC 在訓(xùn)練數(shù)據(jù)集大小m ＝｛100 000，50 000，10 000，5 000｝ 上的分類準(zhǔn)確率，其中ε ＝｛0.005，0.01，0.05，0.1，0.5，1｝

（4） 時間性能比較

相較于普通的數(shù)據(jù)挖掘算法，基于本地差分隱私保護(hù)下的數(shù)據(jù)挖掘算法更為復(fù)雜，因此在關(guān)注數(shù)據(jù)挖掘任務(wù)性能的同時，也需關(guān)注帶來的時間與空間的代價。

實驗中，在隱私保護(hù)參數(shù)一致的情況下，將Adult 訓(xùn)練集大小分別取4 000、8 000、12 000、16 000、20 000、24 000、28 000 和32 000 訓(xùn)練，并用相同大小的測試集測試。 由于運(yùn)行時間具有不確定性，取運(yùn)行30 次的時間累加和。 在LDPBayes 中， LDPbayes?FO 算法僅需調(diào)用一次即可得到一組擾動的輸出數(shù)據(jù)。 當(dāng)應(yīng)用DE 算法擾動時，集合數(shù)據(jù)中的每一個元素都需調(diào)用一次算法后才能得到全部的擾動數(shù)據(jù)。 對于OUE 算法，由于編碼方式需將每一個數(shù)轉(zhuǎn)換成二進(jìn)制向量，而向量的每一位都需擾動，因此帶來的時間和空間開銷都隨著編碼個數(shù)的增大而劇增。 圖4為對比結(jié)果，在不同訓(xùn)練集大小下，LDPBayes 方案 的 運(yùn) 行 時 間 均 小 于 文 獻(xiàn)［12］?DE 和 文獻(xiàn)［12］?OUE 的方案，時間開銷小于其他方案。

圖4 在不同大小數(shù)據(jù)集上的時間性能

5 結(jié)束語

本文基于本地差分隱私設(shè)計了一個頻數(shù)預(yù)測算法LDPbayes?FO，并設(shè)計了滿足本地差分隱私的樸素貝葉斯分類算法LDPBayes。 在頻數(shù)預(yù)測算法LDPbayes?FO 中，編碼時保留了屬性值和類標(biāo)簽之間的相關(guān)性，將原始數(shù)據(jù)編碼進(jìn)一個有序定長的集合。 擾動算法基于指數(shù)機(jī)制設(shè)計，其中效用函數(shù)被定義為輸入集合和輸出集合之間是否有交集，擾動輸出的概率由效用函數(shù)決定，能有效提高數(shù)據(jù)收集的效用。 服務(wù)器端對編碼值的頻數(shù)聚合后可計算得到類標(biāo)簽概率和條件概率，從而訓(xùn)練成貝葉斯分類器。 實驗結(jié)果表明，本文的算法在隱私保護(hù)水平一致的情況下，能夠提升發(fā)布數(shù)據(jù)的可用性，同時相較于已有的相關(guān)工作，該算法的時間性能更優(yōu)。 受樸素貝葉斯分類算法的影響，只能處理屬性之間相互獨(dú)立的分類數(shù)據(jù)，今后將研究支持更復(fù)雜的本地差分隱私的分類方案。