基于聚類的差分隱私民航旅客數據發布算法

丁建立，杜天天

(中國民航大學 計算機科學與技術學院，天津 300300)

0 引 言

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

1 研究現狀

1.1 聚類的研究現狀

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

文獻[7]中有幾種算法可以對混合數據進行聚類。但是，所有這些算法都需要預先直接或間接指定聚類數。本文提出確定混合數據集中簇數的有效方法。該方法由經過改進的k-prototype組成。

1.2 隱私保護的研究現狀

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

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

現階段，在非交互式場景下，針對差分隱私數據發布基本方法是基于直方圖發布。這種方法可以很直觀地看出數據的分布并可以近似計算數據和、差、方差以及平均數等統計信息。然而，當數據中的屬性數量增加時，這種方法則會表現出嚴重的局限性，現在我們可以得到的數據量增大，其數據類型也在不斷的增加，我們如果想要更加全方位的收集信息，信息中的屬性相應的也會增加。這使得計算效率大大降低。除此之外，直方圖發布方法僅僅提供了分區數據的計數，比如年齡為20～30的旅客有2000個，卻無法提供具體數據，這使得我們僅僅可以看到經過統計處理的數據，數據的可用性降低。本文提出滿足差分隱私的數據集發布，這將克服數據屬性數量及無具體數據值的限制。為進一步提高數據集的可用性，本文提出利用聚類算法先對數據進行聚類，將一個大數據集聚類為幾個子集，查詢敏感度由一分化為多，使整個數據集的查詢敏感度降低，進而減少噪聲添加量。

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

2 差分隱私定義及噪音機制

2.1 差分隱私定義

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

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

(1)

式中：參數ε是隱私預算，由公式可得出ε越小，隨機算法R隱私保護程度越高。

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

定義2 敏感度：對于輸入數據集上的任何查詢f，對于任何兩個相鄰的數據集D1和D2，f的敏感度為

(2)

敏感度較低的查詢所需的噪聲較小。差分隱私保護技術即向查詢結果的數據添加噪聲，對數據擾動，最終達到隱私保護的目的。

對于滿足差分隱私的數據發布來說，需要多次應用差分隱私算法，差分隱私的兩個組合性質可以將隱私預算合理的分配到整個差分隱私中。

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

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

2.2 噪音機制

噪聲量會影響數據安全性和可用性，Laplace機制與指數機制為現有常用的噪音機制。拉普拉斯機制對數值型數據進行處理，是實現差分隱私最常用的機制。本文使用拉普拉斯機制和指數機制滿足差分隱私。

定理1Laplace機制:對于任意數據集D和函數f，若滿足

(3)

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

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

(4)

則K滿足ε-差分隱私。

指數機制的關鍵是可用性函數u(D,r)，u評估輸出值r，指數機制是用指數級更高的概率選擇評分更高的元素，u(D,r) 越大，r被輸出的概率越大。

3 基于k-prototype聚類的差分隱私民航旅客數據發布算法

3.1 改進k-prototype算法

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

(5)

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

(6)

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

(7)

(8)

3.2 算法及差分隱私證明

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

算法流程如圖1所示。

步驟：

步驟1 選擇民航數據中敏感信息屬性，數據清洗，并分析屬性之間相關性。

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

步驟3 隨機選擇k個初始中心點，計算每個元組至初始中心點距離，元組中的數值型屬性計算方法為每個點到k個中心點的歐氏距離，其中的分類型屬性計算方法為每個點

表1 基于聚類的差分隱私數據發布算法

圖1 算法流程

到k個中心點的漢明距離，最后將其分至最近的中心點。

步驟4 計算損失函數，若結果不為0，則重新選擇中心點，迭代至損失函數結果為0。

步驟5 將聚類結果進行有效性評估，選擇聚類效果最好的k值。得到聚類結果。

步驟6 對于數值型屬性，采用Laplace機制加噪。

步驟7 對于分類型屬性，生成每個簇的屬性值集合，每個簇分別根據各自屬性值使用指數機制選擇輸出值。

步驟8 生成滿足差分隱私的數據集。

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

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

根據差分隱私組合性質分析并證明：

(9)

(10)

4 實驗結果及分析

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

表2 數據集介紹

為方便實驗，選取其中400條記錄實現聚類，以及滿足差分隱私的算法。每個屬性之間的相關性越低，聚類效果越好，以票號為主屬性，計算其與另外14個屬性的相關性，如圖2所示。

圖2 屬性之間的相關性

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

做好以上數據預處理工作后，進行聚類實驗。

4.1 實驗過程

實驗時的參數設置，其中聚類實驗設置k最小值為2，最大值為9，因為如果k值太大，則會造成聚類結果的實際意義不大，由于實驗數據集總共有400條記錄，所以將聚類簇數控制在10以內，實驗結果如圖3所示。

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

圖3顯示了k值與聚類指標的關系，有效性指標越小，則聚類效果越好，可以看出本文改進的聚類算法比開源包的聚類算法效果要好。觀察改進的聚類算法，可以明顯看出k=3時，達到最低點，聚類效果最好。所以選取k=3，將數據集聚類，并按照聚類結果對數據集中的每個簇分別進行加噪。其中數值型數值進行拉普拉斯機制加噪，分類型數值進行指數機制加噪。

選擇隱私預算ε為0.1時的滿足差分隱私的數據集與原數據集及進行對比，表3展示了部分記錄中的4個屬性之間的對比。

4.2 實驗評價指標

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

(11)

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

表3 加噪前后數據集之間對比

(12)

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

(13)

將本文提出的算法在民航旅客信息數據集上進行實驗。確定聚類算法中的k值為3，將隱私參數ε設置為 {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}， 根據以上數據進行數據信息損失與信息泄露對比實驗，信息損失SSE與敏感度的關系結果如圖4所示。

圖4 ε不同時的信息損失

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

圖5 ε不同時的信息披露

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

5 結束語

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