基于聚類的差分隱私民航旅客數(shù)據(jù)發(fā)布算法

丁建立，杜天天

(中國民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

隱私安全問題通常會(huì)阻礙用戶數(shù)據(jù)分享，甚至阻礙分析從數(shù)據(jù)挖掘的價(jià)值信息[1]。數(shù)據(jù)挖掘在生活中有許多應(yīng)用，聚類是一種廣泛使用的數(shù)據(jù)挖掘方法之一，應(yīng)用數(shù)據(jù)挖掘通常都假定可以自由訪問數(shù)據(jù)集，但這是不現(xiàn)實(shí)的。因此需要做好隱私保護(hù)，解決由于數(shù)據(jù)發(fā)布導(dǎo)致的個(gè)人隱私泄露這一問題。隱私保護(hù)的數(shù)據(jù)發(fā)布已有多種方法。其中差分隱私技術(shù)可以保證在兩個(gè)僅相差一條記錄的數(shù)據(jù)集上運(yùn)行算法能夠產(chǎn)生相似的輸出。本文目標(biāo)是實(shí)現(xiàn)發(fā)布民航旅客數(shù)據(jù)的同時(shí)最大程度地保護(hù)隱私。差分隱私提供強(qiáng)大的隱私保證。大數(shù)據(jù)時(shí)代，數(shù)據(jù)無處不在，大量有價(jià)值的信息隱藏在數(shù)據(jù)中等待著研究者挖掘。數(shù)據(jù)分析者可通過對(duì)數(shù)據(jù)整理分析[2]提取有價(jià)值信息，使人們生活更加便利美好。然而在增加人民幸福感的同時(shí)，其中的問題也相應(yīng)暴露出，在搜集數(shù)據(jù)的同時(shí)會(huì)攜帶大量隱私信息，比如，在分析不文明旅客時(shí)，會(huì)收集其身份信息、聯(lián)系方式等等。如果向公眾直接發(fā)布這些信息，有可能對(duì)用戶構(gòu)成相當(dāng)大的威脅。因此，數(shù)據(jù)發(fā)布隱私保護(hù)[3]的重難點(diǎn)為保證發(fā)布的數(shù)據(jù)可用的同時(shí)不會(huì)泄露隱私信息。

1 研究現(xiàn)狀

1.1 聚類的研究現(xiàn)狀

聚類是數(shù)據(jù)挖掘中的重要工具，在數(shù)據(jù)分析、信息檢索和文本挖掘等領(lǐng)域具有許多應(yīng)用。它旨在將有限的、未標(biāo)記的數(shù)據(jù)集劃分為幾個(gè)自然子集，同一簇內(nèi)的數(shù)據(jù)相近，而來自不同簇的數(shù)據(jù)互不相同。為了實(shí)現(xiàn)該目的，現(xiàn)在已經(jīng)提出了許多聚類算法，例如：基于劃分、基于網(wǎng)絡(luò)以及基于模型的聚類等等。這些聚類算法中的大多數(shù)都需要事先指定集群的數(shù)量或隱式集群的數(shù)量控制參數(shù)。對(duì)于某些應(yīng)用，可以根據(jù)用戶的專業(yè)知識(shí)來估計(jì)集群的數(shù)量。但是，在許多情況下，不能確定數(shù)據(jù)集的簇?cái)?shù)。然而，聚類數(shù)量會(huì)大大影響聚類結(jié)果的好壞。因此，確定數(shù)據(jù)集中的簇?cái)?shù)(通常標(biāo)記為k)是聚類分析中的一個(gè)基本問題?，F(xiàn)有很多估計(jì)k值的研究[4]?；跀?shù)據(jù)類型的差異，這些方法通常可以歸類為用于數(shù)值數(shù)據(jù)、分類數(shù)據(jù)和混合數(shù)據(jù)的聚類算法。在數(shù)值領(lǐng)域，文獻(xiàn)[5]提出了針對(duì)海量數(shù)據(jù)的k-means問題的有效近似方法。將整個(gè)數(shù)據(jù)集遞歸地劃分為少量子集，每個(gè)子集均以其代表(質(zhì)心)和權(quán)重(基數(shù))為特征，然后將k-means算法的加權(quán)版本應(yīng)用于此類局部表示，這樣可以大大減少計(jì)算出的距離數(shù)。對(duì)于分類數(shù)據(jù)，文獻(xiàn)[6]提出k-modes聚類的性能對(duì)初始聚類中心的選擇特別敏感。從離群值檢測(cè)的角度考慮了k-modes聚類的初始化。通過使用基于傳統(tǒng)的基于距離的離群值檢測(cè)技術(shù)和基于分區(qū)熵的離群值檢測(cè)技術(shù)來計(jì)算每個(gè)對(duì)象的離群度。在初始化過程中，采用了新的距離度量標(biāo)準(zhǔn)-加權(quán)匹配距離度量標(biāo)準(zhǔn)。

文獻(xiàn)[7]中有幾種算法可以對(duì)混合數(shù)據(jù)進(jìn)行聚類。但是，所有這些算法都需要預(yù)先直接或間接指定聚類數(shù)。本文提出確定混合數(shù)據(jù)集中簇?cái)?shù)的有效方法。該方法由經(jīng)過改進(jìn)的k-prototype組成。

1.2 隱私保護(hù)的研究現(xiàn)狀

隱私數(shù)據(jù)保護(hù)自隱私出現(xiàn)一直被人們所研究，并提出了很多保護(hù)方法，k-anonymity及其改進(jìn)的算法[8]是其中較早且經(jīng)典的研究成果。k-anonymity保護(hù)數(shù)據(jù)中的隱私是通過保證每個(gè)記錄與至少k-1個(gè)其它記錄無法區(qū)分。但是在攻擊者可能獲得背景知識(shí)的前提下，很容易受到攻擊，之后提出的l-diversity和t-closeness，可以預(yù)防多樣性攻擊，但仍會(huì)受到其它攻擊。差分隱私模型通過向數(shù)據(jù)中添加一定量的噪聲，保證發(fā)布的數(shù)據(jù)不會(huì)泄露隱私信息，無需考慮攻擊者的背景知識(shí)，因此差分隱私有更加強(qiáng)大的隱私保證。

近年來，差分隱私保護(hù)技術(shù)已經(jīng)成為了一個(gè)備受關(guān)注的研究熱點(diǎn)。差分隱私[9]被越來越多地用作數(shù)據(jù)分析選擇的隱私保護(hù)技術(shù)，使數(shù)據(jù)既能被挖掘有價(jià)值信息的同時(shí)又保護(hù)了用戶個(gè)人隱私。差分隱私數(shù)據(jù)發(fā)布有交互式框架和非交互式框架兩種方式，在差分隱私初期，被應(yīng)用于研究者在數(shù)據(jù)庫上查詢數(shù)據(jù)時(shí)，返回的查詢數(shù)據(jù)滿足差分隱私，然而這種形式的差分隱私應(yīng)用對(duì)數(shù)據(jù)有嚴(yán)格的限制，交互式場(chǎng)景下，隨著查詢次數(shù)增多，所得的數(shù)據(jù)偏差會(huì)越來越大，最后所查詢數(shù)據(jù)甚至完全沒有參考價(jià)值，這導(dǎo)致它只能接受有限數(shù)量的查詢。在此弊端的影響下人們研究出了非交互式場(chǎng)景下的差分隱私數(shù)據(jù)發(fā)布，這里的數(shù)據(jù)可對(duì)整個(gè)數(shù)據(jù)集進(jìn)行差分隱私處理，使得可以發(fā)布滿足差分隱私的數(shù)據(jù)集，這些數(shù)據(jù)集保證了基本的數(shù)據(jù)統(tǒng)計(jì)特征，研究者可以利用這些統(tǒng)計(jì)結(jié)果進(jìn)行分析和處理，然而如果想要進(jìn)一步分析，可能使用這些數(shù)據(jù)集不能夠得出精確的分析結(jié)果，這是由于差分隱私需要在數(shù)據(jù)集中加入大量噪聲所造成的，這些噪聲既保護(hù)了數(shù)據(jù)，相應(yīng)的又破壞了數(shù)據(jù)，使得數(shù)據(jù)的可用性降低，其分析價(jià)值降低。而后研究表明，合理分配隱私預(yù)算，在實(shí)現(xiàn)保護(hù)隱私的前提下，適當(dāng)降低查詢敏感度可以大大提高差分隱私數(shù)據(jù)的可用性。目前對(duì)于混合型數(shù)據(jù)發(fā)布的研究相對(duì)較少，而在實(shí)際生活中大部分?jǐn)?shù)據(jù)集為混合型數(shù)據(jù)集。因此，研究針對(duì)混合型(數(shù)據(jù)類型和分類類型)數(shù)據(jù)集的差分隱私數(shù)據(jù)發(fā)布方法更加具有現(xiàn)實(shí)意義，可實(shí)現(xiàn)人們對(duì)于隱私保護(hù)的需求。文獻(xiàn)[10]研究了兩種方法在差分隱私k-means聚類中的有效性。提出了一種非交互式方法EUGkM，該方法發(fā)布了k-means聚類的差分隱私模型，驗(yàn)證了EUGkM算法的有效性。文獻(xiàn)[11]中介紹了最廣泛使用的聚類k-means容易陷入局部最優(yōu)。并提出傳統(tǒng)的聚類方法直接在隱私數(shù)據(jù)上執(zhí)行，但是無法應(yīng)對(duì)針對(duì)攻擊者任意背景知識(shí)的大規(guī)模數(shù)據(jù)挖掘任務(wù)中的惡意攻擊。這將導(dǎo)致侵犯?jìng)€(gè)人隱私，以及通過系統(tǒng)資源和聚類輸出造成泄漏。

現(xiàn)階段，在非交互式場(chǎng)景下，針對(duì)差分隱私數(shù)據(jù)發(fā)布基本方法是基于直方圖發(fā)布。這種方法可以很直觀地看出數(shù)據(jù)的分布并可以近似計(jì)算數(shù)據(jù)和、差、方差以及平均數(shù)等統(tǒng)計(jì)信息。然而，當(dāng)數(shù)據(jù)中的屬性數(shù)量增加時(shí)，這種方法則會(huì)表現(xiàn)出嚴(yán)重的局限性，現(xiàn)在我們可以得到的數(shù)據(jù)量增大，其數(shù)據(jù)類型也在不斷的增加，我們?nèi)绻胍尤轿坏氖占畔?，信息中的屬性相?yīng)的也會(huì)增加。這使得計(jì)算效率大大降低。除此之外，直方圖發(fā)布方法僅僅提供了分區(qū)數(shù)據(jù)的計(jì)數(shù)，比如年齡為20～30的旅客有2000個(gè)，卻無法提供具體數(shù)據(jù)，這使得我們僅僅可以看到經(jīng)過統(tǒng)計(jì)處理的數(shù)據(jù)，數(shù)據(jù)的可用性降低。本文提出滿足差分隱私的數(shù)據(jù)集發(fā)布，這將克服數(shù)據(jù)屬性數(shù)量及無具體數(shù)據(jù)值的限制。為進(jìn)一步提高數(shù)據(jù)集的可用性，本文提出利用聚類算法先對(duì)數(shù)據(jù)進(jìn)行聚類，將一個(gè)大數(shù)據(jù)集聚類為幾個(gè)子集，查詢敏感度由一分化為多，使整個(gè)數(shù)據(jù)集的查詢敏感度降低，進(jìn)而減少噪聲添加量。

針對(duì)于此，本文提出了一種基于聚類滿足差分隱私的數(shù)據(jù)發(fā)布算法，可以對(duì)民航旅客信息數(shù)據(jù)集進(jìn)行差分隱私保護(hù)。分析民航旅客數(shù)據(jù)，從中發(fā)現(xiàn)數(shù)據(jù)包括數(shù)值屬性和分類屬性，k-prototype可對(duì)混合數(shù)據(jù)集聚類，因此使用k-prototype聚類算法，該算法是處理混合數(shù)據(jù)類型的典型聚類算法。根據(jù)民航旅客數(shù)據(jù)集特有的性質(zhì)改進(jìn)了k-prototype算法中分類屬性的距離計(jì)算，能夠更好的對(duì)混合屬性數(shù)據(jù)進(jìn)行聚類，最后通過聚類算法的分組，由單一數(shù)據(jù)集分成多組數(shù)據(jù)集，降低差分隱私的敏感度，從而減少需要添加的噪聲量，因此大大提高數(shù)據(jù)的可用性。

2 差分隱私定義及噪音機(jī)制

2.1 差分隱私定義

差分隱私要求數(shù)據(jù)的輸出應(yīng)該大致相同，即使在輸入數(shù)據(jù)庫中任意添加或刪除任何一個(gè)元組也是如此。

定義1ε-差分隱私：設(shè)有隨機(jī)算法R滿足ε-差分隱私，以及任意兩個(gè)相鄰數(shù)據(jù)集D1和D2(在一條記錄中有所不同)輸出S∈Range(R)。 有

(1)

式中：參數(shù)ε是隱私預(yù)算，由公式可得出ε越小，隨機(jī)算法R隱私保護(hù)程度越高。

差分隱私提供了正式且可量化的隱私保證，而不受對(duì)手的背景知識(shí)和可用的計(jì)算能力的影響。如果對(duì)于整個(gè)輸出空間，對(duì)于任何一對(duì)相鄰輸入，生成相同輸出的概率彼此之間的較小倍數(shù)內(nèi)，則認(rèn)為隨機(jī)算法是差分隱私的。這意味著對(duì)于彼此接近的任何兩個(gè)數(shù)據(jù)集，差分隱私算法在兩個(gè)數(shù)據(jù)集上的表現(xiàn)大致相同。無論對(duì)手是否擁有先驗(yàn)知識(shí)，該概念都為用戶提供了足夠的隱私保護(hù)。在本文中，當(dāng)且僅當(dāng)數(shù)據(jù)集D1和D2僅相差一條記錄時(shí)，我們才將兩個(gè)數(shù)據(jù)集D1和D2視為鄰居，D1+t表示將元組t與數(shù)據(jù)集D1相加而得的數(shù)據(jù)集，我們用D1?D2來表示。這可以保護(hù)任何單個(gè)元組的隱私。

定義2 敏感度：對(duì)于輸入數(shù)據(jù)集上的任何查詢f，對(duì)于任何兩個(gè)相鄰的數(shù)據(jù)集D1和D2，f的敏感度為

(2)

敏感度較低的查詢所需的噪聲較小。差分隱私保護(hù)技術(shù)即向查詢結(jié)果的數(shù)據(jù)添加噪聲，對(duì)數(shù)據(jù)擾動(dòng)，最終達(dá)到隱私保護(hù)的目的。

對(duì)于滿足差分隱私的數(shù)據(jù)發(fā)布來說，需要多次應(yīng)用差分隱私算法，差分隱私的兩個(gè)組合性質(zhì)可以將隱私預(yù)算合理的分配到整個(gè)差分隱私中。

性質(zhì)1 序列組合性：設(shè)存在n個(gè)隨機(jī)算法K，數(shù)據(jù)集D， {ki(D)|1≤i≤n} 滿足εi-差分隱私，則K在D上整體滿足∑εi-差分隱私。

性質(zhì)2 并行組合性：設(shè)存在n個(gè)隨機(jī)算法K，作用在互不相交的一組數(shù)據(jù)集 {Di|1≤i≤n}， {ki(Di)|1≤i≤n} 滿足εi-差分隱私，則K在D上整體滿足max(εi)-差分隱私。

2.2 噪音機(jī)制

噪聲量會(huì)影響數(shù)據(jù)安全性和可用性，Laplace機(jī)制與指數(shù)機(jī)制為現(xiàn)有常用的噪音機(jī)制。拉普拉斯機(jī)制對(duì)數(shù)值型數(shù)據(jù)進(jìn)行處理，是實(shí)現(xiàn)差分隱私最常用的機(jī)制。本文使用拉普拉斯機(jī)制和指數(shù)機(jī)制滿足差分隱私。

定理1Laplace機(jī)制:對(duì)于任意數(shù)據(jù)集D和函數(shù)f，若滿足

(3)

則算法K滿足ε-差分隱私保護(hù)。其中，Δf為全局敏感度，lap(Δf/ε) 代表添加的噪聲量，根據(jù)以上公式可知，查詢函數(shù)f的全局敏感度越大，所需添加的噪聲量越大。

定理2 指數(shù)機(jī)制:給定一個(gè)可用性函數(shù)u(D,r)， Δu為u(D,r) 的全局敏感度，O表示輸出域，r表示從O中所選取一個(gè)元素，若算法K滿足

(4)

則K滿足ε-差分隱私。

指數(shù)機(jī)制的關(guān)鍵是可用性函數(shù)u(D,r)，u評(píng)估輸出值r，指數(shù)機(jī)制是用指數(shù)級(jí)更高的概率選擇評(píng)分更高的元素，u(D,r) 越大，r被輸出的概率越大。

3 基于k-prototype聚類的差分隱私民航旅客數(shù)據(jù)發(fā)布算法

3.1 改進(jìn)k-prototype算法

k-prototype是聚類中常用的模型，該算法從代表k個(gè)組的k個(gè)隨機(jī)選擇的點(diǎn)開始，計(jì)算每個(gè)記錄到初始點(diǎn)的距離，然后將樣本迭代地聚類到最近的簇，并通過聚類到這些點(diǎn)的樣本的眾值來更新這些點(diǎn)。直至所有的記錄全部分到最近的簇。本文根據(jù)民航旅客數(shù)據(jù)的特點(diǎn)，改進(jìn)k-prototype聚類算法。首先確定最小k值和最大k值，依次對(duì)每個(gè)k值進(jìn)行實(shí)驗(yàn)，隨機(jī)選擇k個(gè)初始類中心點(diǎn)，根據(jù)元組間距離計(jì)算方法得到一條記錄到每個(gè)中心點(diǎn)距離，迭代對(duì)數(shù)據(jù)集進(jìn)行計(jì)算，選取距離最小的簇，得到初步聚類結(jié)果。進(jìn)而選取每個(gè)簇中出現(xiàn)最多的元組作類中心，進(jìn)行距離計(jì)算，再次選取距離最小的簇，迭代至每個(gè)元組跟上一次的簇?cái)?shù)一樣，然后計(jì)算聚類有效值，選擇具有最小有效值評(píng)價(jià)的k值，輸出最佳聚類結(jié)果。

(5)

分類型屬性通過漢明距離計(jì)算屬性差異度

(6)

針對(duì)分類型數(shù)據(jù)距離計(jì)算結(jié)果對(duì)聚類結(jié)果的影響程度，設(shè)置其在算法中的權(quán)重，以達(dá)到提高聚類精度的目的。綜上所述，最終元組至中心點(diǎn)的距離計(jì)算公式為上述兩個(gè)公式(式(5)、式(6))相加。k-prototype聚類中的損失函數(shù)計(jì)算數(shù)值型和分類性到每簇聚類中心點(diǎn)的距離，因此選擇一個(gè)合適的損失函數(shù)y。假定設(shè)定數(shù)據(jù)集的簇為k個(gè)，使用0和1表示第m(1≤m≤k) 個(gè)聚類中是否存在元組i，0則表示存在，反之，1表示不存在。綜上損失函數(shù)可以定義為

(7)

(8)

3.2 算法及差分隱私證明

將訓(xùn)練集隨機(jī)分為多個(gè)子集，對(duì)每個(gè)子集運(yùn)行聚類算法以獲取輸出，然后使用差分隱私對(duì)每個(gè)元組加噪，具體做法為遍歷每一個(gè)元組并確定其所在簇，形成不同簇之后，總結(jié)每個(gè)簇的分類屬性中的屬性值集合，利用屬性值集合使用指數(shù)機(jī)制對(duì)分類型屬性干擾，數(shù)值型采用拉普拉斯機(jī)制方法加噪，生成滿足差分隱私的數(shù)據(jù)集。此方法將查詢函數(shù)的靈敏度由一整個(gè)數(shù)據(jù)集的所有記錄分散至多個(gè)子集的k個(gè)記錄中，一定程度上減少了數(shù)據(jù)中的噪音量，更接近于原始數(shù)據(jù)，加噪后的數(shù)據(jù)可用性大大提高。具體算法見表1。

算法流程如圖1所示。

步驟：

步驟1 選擇民航數(shù)據(jù)中敏感信息屬性，數(shù)據(jù)清洗，并分析屬性之間相關(guān)性。

步驟2 選擇k最小值以及最大值。

步驟3 隨機(jī)選擇k個(gè)初始中心點(diǎn)，計(jì)算每個(gè)元組至初始中心點(diǎn)距離，元組中的數(shù)值型屬性計(jì)算方法為每個(gè)點(diǎn)到k個(gè)中心點(diǎn)的歐氏距離，其中的分類型屬性計(jì)算方法為每個(gè)點(diǎn)

表1 基于聚類的差分隱私數(shù)據(jù)發(fā)布算法

圖1 算法流程

到k個(gè)中心點(diǎn)的漢明距離，最后將其分至最近的中心點(diǎn)。

步驟4 計(jì)算損失函數(shù)，若結(jié)果不為0，則重新選擇中心點(diǎn)，迭代至損失函數(shù)結(jié)果為0。

步驟5 將聚類結(jié)果進(jìn)行有效性評(píng)估，選擇聚類效果最好的k值。得到聚類結(jié)果。

步驟6 對(duì)于數(shù)值型屬性，采用Laplace機(jī)制加噪。

步驟7 對(duì)于分類型屬性，生成每個(gè)簇的屬性值集合，每個(gè)簇分別根據(jù)各自屬性值使用指數(shù)機(jī)制選擇輸出值。

步驟8 生成滿足差分隱私的數(shù)據(jù)集。

本文算法分為聚類分組階段和數(shù)據(jù)發(fā)布階段，簇的數(shù)量從k在一定范圍，這導(dǎo)致了一系列連續(xù)的聚類結(jié)果。具體而言，在每個(gè)循環(huán)中，該方法的基本步驟包括：①使用改進(jìn)的k-prototype算法和距離度量，將輸入數(shù)據(jù)集劃分為所需的聚類；②根據(jù)聚類評(píng)估聚類結(jié)果有效性指數(shù)；③最后，繪制了給定數(shù)據(jù)的聚類有效性指數(shù)與聚類數(shù)量的關(guān)系圖。根據(jù)該圖，可以目測(cè)為給定的混合數(shù)據(jù)集提供最佳的聚類數(shù)。民航旅客數(shù)據(jù)集都是混合數(shù)據(jù)集，它包含數(shù)值屬性和分類屬性。如果要以統(tǒng)一的方式處理混合數(shù)據(jù)，一般是將分類屬性轉(zhuǎn)換為數(shù)值屬性，或者將數(shù)字屬性轉(zhuǎn)換為分類屬性。但是，將分類屬性轉(zhuǎn)換為數(shù)值屬性，很難將合適的數(shù)值分配給分類值。例如，如果color屬性采用集合{red，blue，green}中的值，將該集合轉(zhuǎn)換為{1、2、3}。在這種情況下，計(jì)算任何編碼值之間的距離都是不合適的。將數(shù)值屬性轉(zhuǎn)換為分類屬性，需要使用離散算法將實(shí)值變量的值域劃分為幾個(gè)區(qū)間，并為同一區(qū)間中的所有值分配一個(gè)符號(hào)。但是由于沒有考慮這些值對(duì)離散值的隸屬度，所以通常會(huì)導(dǎo)致信息丟失。因此，本文直接對(duì)混合數(shù)據(jù)進(jìn)行聚類。完成聚類后，進(jìn)行第二個(gè)階段，數(shù)據(jù)中的數(shù)值型采用Laplace機(jī)制以一定概率添加噪聲，通過指數(shù)機(jī)制對(duì)分類型數(shù)據(jù)實(shí)現(xiàn)差分隱私，從一個(gè)簇中獲取屬性值，以簇中每個(gè)屬性值出現(xiàn)的概率選擇值，根據(jù)輸入數(shù)據(jù)，差分隱私參數(shù)和概率選擇值，選擇隨出現(xiàn)概率呈指數(shù)增長(zhǎng)。

定理3 DP-k-prototype算法滿足ε-差分隱私。

根據(jù)差分隱私組合性質(zhì)分析并證明：

(9)

(10)

4 實(shí)驗(yàn)結(jié)果及分析

本文選取民航數(shù)據(jù)中的PNR數(shù)據(jù)和離港數(shù)據(jù)。在其中選定了15個(gè)屬性，包括身份、航班、位置、時(shí)間等信息組成實(shí)驗(yàn)所需要的數(shù)據(jù)集(表2)，并考慮異構(gòu)屬性類型，由48 842個(gè)記錄組成。對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)清洗，刪除數(shù)據(jù)集中包含空屬性以及有明顯錯(cuò)誤(如不合常規(guī)的年齡以及不存在的日期或者機(jī)場(chǎng)三字代碼等等)的整條記錄，對(duì)所有完整記錄規(guī)范其中的數(shù)據(jù)，如上清洗后共有30 160個(gè)數(shù)據(jù)記錄。本節(jié)仿真實(shí)驗(yàn)環(huán)境如下：Intel(R) Core(TM)i5-4590 CPU，4 GB內(nèi)存，Windows8操作系統(tǒng)，在pycharm環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。

表2 數(shù)據(jù)集介紹

為方便實(shí)驗(yàn)，選取其中400條記錄實(shí)現(xiàn)聚類，以及滿足差分隱私的算法。每個(gè)屬性之間的相關(guān)性越低，聚類效果越好，以票號(hào)為主屬性，計(jì)算其與另外14個(gè)屬性的相關(guān)性，如圖2所示。

圖2 屬性之間的相關(guān)性

從圖2中可看到只有兩個(gè)屬性之間的相關(guān)度達(dá)到了0.6，其余各個(gè)屬性之間的相關(guān)度大都低于0.1，由此可見，屬性之間的相關(guān)性差，依賴低，可以較好地聚類。

做好以上數(shù)據(jù)預(yù)處理工作后，進(jìn)行聚類實(shí)驗(yàn)。

4.1 實(shí)驗(yàn)過程

實(shí)驗(yàn)時(shí)的參數(shù)設(shè)置，其中聚類實(shí)驗(yàn)設(shè)置k最小值為2，最大值為9，因?yàn)槿绻鹝值太大，則會(huì)造成聚類結(jié)果的實(shí)際意義不大，由于實(shí)驗(yàn)數(shù)據(jù)集總共有400條記錄，所以將聚類簇?cái)?shù)控制在10以內(nèi)，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同k值下的聚類效果(指標(biāo)越低越好)

圖3顯示了k值與聚類指標(biāo)的關(guān)系，有效性指標(biāo)越小，則聚類效果越好，可以看出本文改進(jìn)的聚類算法比開源包的聚類算法效果要好。觀察改進(jìn)的聚類算法，可以明顯看出k=3時(shí)，達(dá)到最低點(diǎn)，聚類效果最好。所以選取k=3，將數(shù)據(jù)集聚類，并按照聚類結(jié)果對(duì)數(shù)據(jù)集中的每個(gè)簇分別進(jìn)行加噪。其中數(shù)值型數(shù)值進(jìn)行拉普拉斯機(jī)制加噪，分類型數(shù)值進(jìn)行指數(shù)機(jī)制加噪。

選擇隱私預(yù)算ε為0.1時(shí)的滿足差分隱私的數(shù)據(jù)集與原數(shù)據(jù)集及進(jìn)行對(duì)比，表3展示了部分記錄中的4個(gè)屬性之間的對(duì)比。

4.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

數(shù)據(jù)可用性是通過采用差分隱私技術(shù)所產(chǎn)生的信息損失來測(cè)量。信息損失可以通過誤差平方和(SSE)量化，計(jì)算方法為滿足差分隱私數(shù)據(jù)集的記錄與其相對(duì)應(yīng)原始數(shù)據(jù)集中的記錄之間距離的平方和，誤差平方和(SSE)的計(jì)算公式如下

(11)

計(jì)算數(shù)據(jù)度量時(shí)，對(duì)于數(shù)據(jù)中的數(shù)值使用標(biāo)準(zhǔn)歐幾里德距離；對(duì)于字符采用漢明距離。數(shù)據(jù)隱私受到保護(hù)的標(biāo)準(zhǔn)通過信息披露來衡量。信息披露的計(jì)算方法在本文中采用計(jì)算滿足差分隱私數(shù)據(jù)集正確匹配的原數(shù)據(jù)記錄的百分比，即記錄關(guān)聯(lián)(RL)

表3 加噪前后數(shù)據(jù)集之間對(duì)比

(12)

式中：n表示原數(shù)據(jù)集的總記錄數(shù)，差分隱私干擾后的數(shù)據(jù)集記錄t′的RL概率Pr(t′) 為

(13)

將本文提出的算法在民航旅客信息數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。確定聚類算法中的k值為3，將隱私參數(shù)ε設(shè)置為 {0.001,0.002,0.003,0.004,0.005,0.006,0.007,0.008,0.009,0.01,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.09,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1,2,3,4,5,6,7,8,9,10}， 根據(jù)以上數(shù)據(jù)進(jìn)行數(shù)據(jù)信息損失與信息泄露對(duì)比實(shí)驗(yàn)，信息損失SSE與敏感度的關(guān)系結(jié)果如圖4所示。

圖4 ε不同時(shí)的信息損失

當(dāng)ε為0.001到0.01時(shí)，SSE較大，即使使用聚類算法分簇后再加噪，信息損失仍較高，數(shù)據(jù)可用性低，當(dāng)ε大于0.01時(shí)，SSE較小，并逐漸減小后更趨于保持穩(wěn)定，信息損失較低，可用性高。信息披露RL對(duì)比分析如圖5所示。

圖5 ε不同時(shí)的信息披露

當(dāng)ε為0.001至0.1時(shí)，RL值的變化幅度較小，且RL值趨于低水平；當(dāng)ε為0.1至1時(shí)，RL值的變化幅度較大且處于上升的趨勢(shì)；當(dāng)ε為1至10時(shí)，RL值的變化幅度最大且近乎呈直線上升。圖中的這些變化是因?yàn)楫?dāng)ε越大時(shí)，數(shù)據(jù)中添加的噪聲就越少，當(dāng)數(shù)據(jù)中添加的噪聲不能對(duì)數(shù)據(jù)集進(jìn)行保護(hù)時(shí)，將會(huì)出現(xiàn)信息披露的情況。噪聲越小，風(fēng)險(xiǎn)就越高，導(dǎo)致隱私保護(hù)能力就越弱。圖4和圖5結(jié)合可以看出，當(dāng)ε=0.1至10時(shí)，其數(shù)據(jù)可用性差距不大，而信息披露風(fēng)險(xiǎn)會(huì)越來越高，相應(yīng)隱私保護(hù)能力越來越低；當(dāng)ε小于0.1時(shí)，其數(shù)據(jù)可用性越來越低，而信息披露風(fēng)險(xiǎn)則差距不大。因此當(dāng)ε=0.1獲得最佳效果。

5 結(jié)束語

本文提出了一種基于聚類滿足差分隱私的數(shù)據(jù)發(fā)布方法，目的是在數(shù)據(jù)發(fā)布做好隱私保護(hù)的同時(shí)最大限度提高數(shù)據(jù)的可用性，對(duì)于實(shí)驗(yàn)輸出的數(shù)據(jù)集滿足差分隱私保護(hù)模型要求已在本文做出完整的數(shù)學(xué)證明。對(duì)于此方法，我們改進(jìn)了k-prototype聚類算法，在原有k-prototype聚類的基礎(chǔ)上，針對(duì)特定的數(shù)據(jù)集特點(diǎn)(本文采用民航旅客信息數(shù)據(jù)集)，總結(jié)出民航數(shù)據(jù)分為數(shù)值屬性(比如年齡、證件號(hào)等)和分類屬性(航班號(hào)、飛機(jī)場(chǎng)三字代碼等)，對(duì)此采用不同的計(jì)算方法得出屬性差異度。將差異度較小的記錄分為一組，數(shù)據(jù)集經(jīng)過聚類從單一數(shù)據(jù)集變?yōu)槎嘟M數(shù)據(jù)集，且每組數(shù)據(jù)集中的數(shù)據(jù)都是相似的，對(duì)這些原始數(shù)據(jù)采用差分隱私，針對(duì)數(shù)值型使用Laplace機(jī)制，對(duì)數(shù)值進(jìn)行干擾，分類型使用指數(shù)機(jī)制，利用概率對(duì)分類屬性進(jìn)行干擾，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，該方法可以在信息披露較小的情況下盡量使信息損失量最小，從而在提供隱私保護(hù)的同時(shí)提高數(shù)據(jù)可用性。