DCKPDP：改進k-prototype聚類的差分隱私混合屬性數據發布方法

摘 要： 當前混合屬性數據發布中隱私保護方法大多存在隱私保護效果不佳或數據效用較差的問題，采用差分隱私與優化的k-prototype聚類方法相結合，提出改進k-prototype聚類的差分隱私混合屬性數據發布方法（DCKPDP）。為解決傳統k-prototype聚類算法沒有考慮不同數值型屬性對聚類結果有較大影響的問題，利用信息熵為每個數值型屬性添加屬性權重；為解決聚類初始中心點人為規定或者由隨機算法隨機確定，導致聚類結果精確度不高的問題，結合數據對象的局部密度和高密度對聚類過程中初始中心點進行自適應選擇；為解決數據信息泄露風險較高的問題，對聚類中心值進行差分隱私保護。實驗結果表明，DCKPDP算法滿足差分隱私保護所需的噪聲量更小，數據的可用性更好。

關鍵詞： 差分隱私； 混合屬性數據； k-prototype聚類； 密度優化； 信息熵

中圖分類號： TP309.2"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-044-0249-05

doi：10.19734/j.issn.1001-3695.2021.06.0257

Differential privacy mixed attribute data publishing method for improved k-prototype clustering

Zhang Xing， Zhang Xing

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

Abstract： Most of the current privacy protection methods in mixed attribute data publishing have problems of poor privacy protection effect or poor data utility.This paper proposed a differential privacy mixed attribute data publishing method（DCKPDP） based on improved k-prototype clustering.In order to solve the problem that the traditional k-prototype clustering algorithm did not consider the great influence of different numerical attributes on clustering results，using the information entropy added weight for each numerical attribute.In order to solve the problem of low accuracy of clustering results caused by artificial initial center points or randomly determined by random algorithm，combining the local density and high density of data objects carried out an adaptive selection of initial center points in the process of clustering.In order to solve the problem of high risk of data information leakage，using differential privacy protected the clustering center value.The experimental results show that the DCKPDP algorithm satisfies the requirement of differential privacy protection with less noise and better data availability.

Key words： differential privacy； mixed attribute data； k-prototype clustering； density optimization； information entropy

0 引言

信息化、智能化時代的到來，使得數據爆炸式增長，發布這些數據能夠提供科學決策、預測市場趨勢及促進社會發展等，真正意義上促進數據價值流動。然而，這些數據中通常包含著大量的敏感信息，直接發布勢必會導致用戶隱私泄露。因此，如何在數據發布的過程中保護用戶敏感信息，使得發布數據的可用性最大化，成為數據發布中亟待解決的問題。近年來，針對數據發布當中的隱私保護問題，已有一些方法被提出，這些方法主要是基于數據匿名的發布方法和基于數據失真的發布方法。k-anonymity［1］及其改進方法是數據匿名方法的典型代表，該類方法通過對數據表的準標志符屬性進行泛化［2］、抑制等操作，使每條記錄與至少k-1條其他記錄無法區分，從而保護數據隱私。雖然利用這類方法能夠在一定程度上保護數據中的敏感信息，但是這類方法需要假設攻擊者不具備背景知識，因此無法抵御背景知識攻擊和組合攻擊。差分隱私［3］作為基于數據失真的發布方法，是當前新型的隱私保護方法，其不對攻擊者所具備的背景知識作任何假設，通過添加一定量的噪聲對數據進行擾動，從而提供強大的隱私保證，因此，能夠克服無法抵御任意知識背景攻擊和組合攻擊等缺點，但是差分隱私模型為保護數據的隱私，犧牲了數據的可用性。

現有研究對單一屬性數據［4］發布當中的隱私保護問題提出了諸多解決方法，但實際中，數據中通常包含數值、分類等混合屬性，單一屬性數據發布方法無法處理混合屬性數據發布，因此，需要對混合數據發布當中隱私保護問題進行深入研究。目前，針對差分隱私混合數據發布的研究成果較少，且提出的方法大多引入了大量噪聲，致使數據效用較低。為了克服當前混合數據發布中數據可用性與隱私保護程度不平衡問題［5］，本文提出了一種改進k-prototype聚類的差分隱私混合屬性數據發布方法DCKPDP。針對傳統k-prototype聚類算法未考慮不同數值型屬性對聚類結果產生影響的問題，對其進行改進，引入信息熵為數值型屬性添加屬性權重，優化分類屬性的相異度度量公式；k-prototype聚類算法中人為或者隨機選擇聚類初始中心點，導致聚類結果的精確度和穩定性較低，利用數據對象的局部密度和高密度對聚類過程中的初始中心點進行自適應選擇，提升聚類精度和穩定性。為減小數據信息泄露風險，對聚類中心值進行差分隱私保護。針對數值型屬性對其聚類中心值添加Laplace噪聲；針對分類型屬性根據聚類屬性值集合使用指數機制選擇輸出屬性值作為該分類屬性的聚類中心值，最后生成滿足差分隱私保護的待發布數據集，在保護數據隱私的同時，提升數據的可用性。

1 相關工作和預備知識

1.1 相關工作

聚類［6］作為數據挖掘中一種重要的算法，可以將相似性較高的數據記錄劃分到一個特定的簇中，文獻［7］將聚類和匿名結合起來，以此來提升數據的可用性，此后陸續可見一些聚類匿名的研究成果，但通過匿名化的方法無法抵御擁有強大背景知識攻擊者的攻擊。差分隱私因其強大的保護作用而被廣泛應用到數據發布中，利用聚類算法在對數據記錄進行預處理后可以降低查詢敏感度減少差分隱私噪聲的加入，提高數據可用性。當前，基于聚類的差分隱私數據發布方法已有一些研究成果，但是這些方法都存在一定的問題。

文獻［8］提出了基于K-means聚類的差分隱私保護方法，利用聚類中心點代替原始記錄中的隱私，但是該方法在處理較大數據集時存在效率不高的問題，而且聚類結果的可用性非常依賴隱私預算的大小。文獻［9］提出了一種把差分隱私與k-modes聚類方法結合的數據發布算法，但是該算法存在計算效率的問題，而且該方法只針對分類型屬性數據的發布。文獻［10］提出了一種基于DBSCAN聚類的差分隱私數據發布方法，但該方法同樣適用于數值屬性數據的發布。文獻［11］針對基于OPTICS聚類的差分隱私保護方法提出了DP-OPTICS方法，尋求了隱私保護能力與數據效用之間的平衡，提升數據的可用性，但該方法同樣僅適用于數值型數據集。

針對包含混合屬性數據的發布，文獻［12］提出一種結合差分隱私的數據保護方法，但該方法將數據表進行匿名化后，再進行差分隱私保護，使得數據的可用性大大降低；文獻［13］提出一種基于k-prototype聚類的差分隱私混合數據發布算法，但是該方法中的聚類算法采用隨機選取初始中心點，并且沒有對各個數值屬性的重要程度進行權重的量化，使得聚類結果的準確度和穩定性不高，導致發布數據的可用性降低。

基于以上問題，提出了改進k-prototype聚類的差分隱私混合屬性數據發布方法（DCKPDP），在滿足數據發布隱私性保護的同時，提高數據的可用性。DCKPDP算法在利用k-prototype聚類的時候，不再人為或者隨機地確定初始聚類中心點，引入數據對象的局部密度和高密度，自適應地選取初始聚類中心點。利用信息熵為每個數值型屬性添加屬性權重，減小不同數值型屬性對聚類結果。在完成聚類后，對數據集進行加噪處理，避免數據隱私信息泄露。

4 實驗結果分析

4.1 實驗環境與數據集

為驗證DCKPDP算法的有效性，本文采用Python 3.8開發環境，IntelCoreTM i5-1135G7@2.40 GHz CPU，16 GB內存，操作系統為Microsoft Windows 10。實驗數據集采用UCI機器學習數據庫中的adult數據集，共包含48 842條數據記錄，刪除其中具有缺失屬性的記錄后，共有30 158條記錄，因本文是針對混合屬性數據集發布的，所以從adult數據集中選取了三個數值型屬性和五個分類型屬性作為實驗屬性，adult數據集如表1所示。

4.2 算法性能評價標準

本文通過改進k-prototype聚類算法，使原始數據集能夠得到更好的聚類效果，從而在利用差分隱私對其進行保護時，能加入更小的噪聲，提高數據的可用性，因此本章實驗主要在于證明文中算法能在保證數據泄露風險較低的情況下，提升數據可用性。

針對數據的可用性衡量，采用距離誤差平方和（SSE）作為評價指標，將其用做計算原始數據元組與差分隱私數據集中對應元組之間距離的平方和，SSE值越小，表明原始記錄與差分隱私保護后的記錄距離越小，數據信息損失越少。其計算公式為

SSE=∑ni=1 ∑mj=1（d（oi（oij），o′（oij）））（16）

其中：d（oi（oij），oi′（oij））第j個數值型屬性的距離采用標準歐氏距離計算，第j個分類型屬性之間的距離采用式（7）進行計算。

數據被泄露的風險利用記錄關聯（RL）來衡量，即與利用差分隱私處理過的數據集正確匹配原始數據記錄的百分比，其計算公式為

RL=∑o∈OPr（O′）n×100（17）

設O′為經過差分隱私保護后的數據記錄，M為采用式（7）計算后距離O′最近的原始記錄的集合，如果真正的原始記錄o在M中，則Pr（o′）表示在M中猜測到原始記錄o的概率為1/|M|，其中|M|為設定的M中包含記錄的個數；如果不在，

Pr（o′）=0。原始記錄與經過差分隱私保護的記錄匹配率越高，則證明數據信息越容易被泄露，即RL越大，數據信息泄露的可能性越大。

4.3 實驗結果與分析

針對DCKPDP算法，將隱私預算ε取值設定為{0.01，0.1，1，5}，將屬性個數q分別取4和8進行對比實驗，其中當q取4時取兩個數值型屬性（年齡、年齡每周工作時長）和兩個分類型屬性（原國籍、教育程度），則DCKPDP算法造成的信息損失SSE如圖1所示。

由圖1可知，當q=4時SSE的值遠遠小于q=8時，這是因為隨著屬性個數的增加，原始數據中加入的噪聲越來越多，導致數據的信息損失也越多，相應的SSE值就越大。當ε取0.01的時候，SSE雖然呈下降趨勢，但是變化不明顯，這是因為隱私預算過小的情況下，加入了大量的噪聲。使用本文改進過的k-prototype聚類算法對原始數據集進行處理，數據的可用性也非常低；ε取0.1的時候，SSE的變化最為明顯；當ε取1和5時，兩者SSE值較低，且相差較小，這是因為當ε取較大值時，加入的噪聲小，對數據SSE值影響不大。

隨著k值的增大，聚類簇的數目增多，相異度較低的數據記錄劃分在同了一個簇中，聚類效果接近最佳，加入的噪聲越少，所以SSE總體的趨勢是減小的，也證明了本文算法的可行性。

為了驗證本文算法對發布數據可用性的提升以及抵御數據信息泄露風險能力的保證，將本文DCKPDP算法與同類算法在adult數據集上進行信息損失大小對比和數據泄露風險對比。將DCKPDP算法和文獻［12］的ICMD-DP算法及文獻［13］的DP-k-prototype算法進行實驗對比，并利用標準差分隱私作為實驗效果衡量標準。實驗設置q取值為8，隱私預算ε的取值為{0.01，0.1，1，5}，分別對比DCKPDP、ICMD-DP和DP-k-prototype算法的RL值，結果如圖2所示。

由圖2可知，隱私預算ε取不同值時，ICMD-DP相較于DCKPDP和DP-k-prototype的RL值更低，即隱私泄露風險越低。這是因為ICMD-DP對數據集進行了匿名化處理，再對匿名后的數據集進行了差分隱私保護，勢必會讓數據得到更強的保護。DCKPDP和DP-k-prototype的RL值相差不大，差值維持在2%左右，但從實驗結果圖來看，即使ICMD-DP采用了匿名化手段和差分隱私對原始數據集進行處理，其RL值與DCKPDP相差也控制在6%以內。因此單從數據泄露風險方面分析，通過本文DCKPDP處理后的數據集仍能滿足保證數據隱私不被泄露的需求。當隱私預算ε的取值為0.01，RL的值最小，即隱私泄露的風險最小，這是因為對數據中加入了大量的噪聲，此時的數據可用性也是最低的；當隱私預算ε的取值為0.1和1時，可以看出無論是本文DCKPDP還是DP-k-prototype的RL值相差不大，差值維持在3%左右，與ICMD-DP差值維持在6%；當隱私預算ε的取值為5時，隨著k值變大，RL值大幅上升，數據泄露的風險也越大。因此綜合考慮本文DCKPDP在ε取1時算法性能最優。

實驗設置q取值為4和8、ε取值為1時，對比DCKPDP、ICMD-DP和DP-k-prototype算法以及標準差分隱私算法在adult數據集上信息損失的變化，實驗結果如圖3所示。

由圖3可知，當ε取1時，隨著k值的增大，聚類結果趨向最優，DCKPDP、ICMD-DP和DP-k-prototype算法的信息損失都逐漸減小，而且信息損失遠遠低于標準差分隱私算法，驗證了通過對原始數據聚類能夠減小噪聲加入，但是ICMD-DP對原始數據集進行了匿名化處理，所以造成的信息損失遠遠高于DCKPDP和DP-k-prototype算法。本文提出的聚類算法相較于DP-k-prototype算法自適應地選擇初始中心點，并改進了相異度計算公式，聚類效果較之有所提升，通過差分隱私對其加噪產生的信息損失也隨之變小，數據的可用性得到了提升。因此，從實驗結果得出，本文DCKPDP相較于ICMD-DP和DP-k-prototype算法，能夠在保證信息泄露風險較小的同時，減少數據的信息損失，較大幅度提升數據的可用性，證明了DCKPDP算法的優越性。

5 結束語

本文研究了混合屬性數據發布的隱私保護問題，并提出了一種新的數據發布保護方法。針對所研究的問題，首先對傳統的k-prototype聚類算法的相異度計算方法進行了改進，并提出了一種能自適應選擇初始聚類中心點的方法，提升了聚類的準確性和穩定性，最后對分類的數據集進行差分隱私保證數據隱私不被泄露。通過實驗驗證，本文DCKPDP算法與同類算法相比，能在保證數據泄露風險較小的情況下，提高數據的可用性。但是本文在進行實驗時采用的數據維度較低，在對高維數據進行發布時可能會存在效率問題；并且文中針對隱私預算的分配采用了均分原則，這樣可能會造成隱私預算的浪費和數據信息的缺失，降低數據的效用性。因此，下一階段的主要研究工作應該考慮如何合理地劃分隱私預算以及如何解決較高維度數據的發布效率問題。

參考文獻：

［1］Latanya S.k-anonymity：a model for protecting privacy［J］.International Journal of Uncertainty，Fuzziness and Knowledge-Based Systems，2002，10（5）：557-570.

［2］王明月，張興，李萬杰，等.面向數據發布的隱私保護技術研究綜述［J］.小型微型計算機系統，2020，41（12）：2657-2667. （Wang Mingyue，Zhang Xing，Li Wanjie，et al.Review of research on privacy protection technology for data publication［J］.Journal of Chinese Computer Systems，2020，41（12）：2657-2667.）

［3］Dwork C.Differential privacy［C］//Proc of the 33rd International Colloquium on Automata，Languages and Programming.Berlin：Springer，2006：1-12.

［4］Wang Rong，Fung B C M.Heterogeneous data release for cluster ana-lysis with differential privacy［J］.Knowledge-Based Systems，2020，201-202：106047.

［5］陳性元，高元照，唐慧林，等.大數據安全技術研究進展［J］.中國科學：信息科學，2020，50（1）：25-66. （Chen Xingyuan，Gao Yuanzhao，Tang Huilin，et al.Progress in research on big data security technology［J］.Scientia Sinica Informationis，2020，50（1）：25-66.）

［6］韓勝寶，伊華偉，李曉會，等.基于融合相似度和層次聚類的冷啟動推薦算法［J/OL］.小型微型計算機系統. （2021-05-17）.http：//kns.cnki.net/kcms/detail/21.1106.TP.20210517.1243.006.html. （Han Shengbao，Yi Huawei，Li Xiaohui，et al.Cold start recommendation algorithm based on fusion similarity and hierarchical clustering［J/OL］.Journal of Chinese Computer Systems.（2021-05-17）.http：//kns.cnki.net/kcms/detail/21.1106.TP.20210517.1243.006.html.）

［7］Rodriguez A，Laio A.Clustering by fast search and find of density peaks［J］.Science，2014，344（6191）：1492-1496.

［8］趙興旺，梁吉業.一種基于信息熵的混合數據屬性加權聚類算法［J］.計算機研究與發展，2016，53（5）：1018-1028. （Zhao Xingwang，Liang Jiye.An attribute weighted clustering algorithm for mixed data based on information entropy［J］.Journal of Computer Research and Development，2016，53（5）：1018-1028.）

［9］Nguyen H H.Privacy-preserving mechanisms for k-modes clustering［J］.Computers amp; Security，2018，78：60-75.

［10］劉曉遷，李千目.基于聚類匿名化的差分隱私保護數據發布方法［J］.通信學報，2016，37（5）：125-129. （Liu Xiaoqian，Li Qianmu.Differentially private data release based on clustering anonymization［J］.Journal on Communications，2016，37（5）：125-129.）

［11］王紅，葛麗娜，王蘇青，等.基于OPTICS聚類的差分隱私保護算法的改進［J］.計算機應用，2018，38（1）：73-78. （Wang Hong，Ge Lina，Wang Suqing.Improvement of differential privacy protection algorithm based on OPTICS clustering［J］.Journal of Computer Applications，2018，38（1）：73-78.）

［12］丁永善，李立新.對混合屬性數據表可行的差分隱私保護方法［J］.計算機應用研究，2019，36（2）：515-518. （ Ding Yongshan，Li Lixin.Differential privacy protection method for mixed data［J］.Application Research of Computers，2019，36（2）：515-518.）

［13］屈晶晶，蔡英，范艷芳，等.基于k-prototype聚類的差分隱私混合數據發布算法［J］.計算機科學與探索，2021，15（1）：109-118. （Qu Jingjing，Cai Ying，Fan Yanfang，et al.Differentially private mixed data release algorithm based on k-prototype clustering［J］.Journal of Frontiers of Computer Science and Technology，2021，15（1）：109-118.）

［14］付鈺，俞藝涵，吳曉平.大數據環境下差分隱私保護技術及應用［J］.通信學報，2019，40（10）：157-168. （Fu Yu，Yu Yihan，Wu Xiaoping.Differential privacy protection technology and its application in big data environment［J］.Journal on Communications，2019，40（10）：157-168.）

［15］孫志冉，蘇航，梁毅.一種改進的k-prototypes聚類算法［J］.計算機工程與應用，2020，56（21）：54-59. （Sun Zhiran，Su Hang，Liang Yi.Improved k-prototypes clustering algorithm［J］.Computer Engineering and Applications，2020，56（21）：54-59.）