唐印滸，鐘 誠

（廣西大學 計算機與電子信息學院，廣西 南寧530004）

0 引 言

平衡隱私保護和數(shù)據(jù)可用性之間的矛盾是數(shù)據(jù)發(fā)布中隱私保護研究的一個關鍵問題。文獻 ［1］改進傳統(tǒng)k－匿名（k－anonymity）算法以抵御同質(zhì)性攻擊、提高數(shù)據(jù)集安全性，加速了匿名過程。文獻 ［2］提出p＋－敏感k－匿名模型，使得除了滿足k－匿名之外，每個等價類內(nèi)敏感屬性的不同種類數(shù)至少為p，但該模型仍然存在k－匿名本身具有的不足。文獻 ［3］對l－多樣性 （l－diversity）模型進行改進，提出了 （l，α）－多樣性模型，該模型除了要求滿足l－多樣性外，還要求每個等價類中敏感屬性值的權值之和至少為α。文獻 ［4］提出一種基于聚類的敏感屬性l－多樣性匿名化算法，該算法生成的每個聚類至少有l(wèi)個不同的敏感屬性值，每個聚類的大小介于l和2l－1之間，以達到優(yōu)化劃分并提高數(shù)據(jù)安全性。然而，l－多樣性模型并沒有解決背景知識攻擊問題。

為了解決上述方法存在的不足，一些學者將統(tǒng)計泄露控制 （statistical disclosure control）技術中的微聚集［5，6］方法引入到數(shù)據(jù)表的k－匿名化中。針對數(shù)值型數(shù)據(jù)集，文獻［7］提出了一個基于聚類的定長微聚集算法。在保證組內(nèi)方差之和最小的前提下，文獻 ［8］提出了聚類時間短的微聚集算法。文獻 ［9］提出了概率k－匿名模型，該模型在確保能獲得與k－匿名一樣匿名效果的前提下，不要求類內(nèi)必須至少有k個相同的準標識符屬性值。

本文在文獻 ［9］的基礎上，引入記錄的權重值，建立了依據(jù)距離和權值選擇聚類種子的模型，設計實現(xiàn)基于變長聚類的概率k－匿名算法，在不降低隱私保護程度的前提下，以提高匿名數(shù)據(jù)集的可用性；設計實現(xiàn)融合k－means與變長聚類算法的概率k－匿名算法，以解決算法在處理大數(shù)據(jù)集時耗時長的問題。

1 基于改進變長聚類的概率k－匿名算法

1.1 聚類種子選取模型

在基于聚類的k－匿名算法中，聚類種子記錄的選擇對于聚類結果數(shù)據(jù)的質(zhì)量、數(shù)據(jù)可用性的影響是非常大的。聚類種子記錄的選擇方式的不同，將會產(chǎn)生不同的聚類效果。

在變長聚類V－MDAV 算法中，每次循環(huán)聚類時V－MDAV算法選擇的都是距離整個數(shù)據(jù)集質(zhì)心最遠的記錄作為下一個類的種子記錄進行聚類。該算法在選擇種子時只考慮了記錄與質(zhì)心之間的距離這個因素，它將所有記錄平等地看待，最后聚類完成后剩余記錄中很可能存在一些用戶期望優(yōu)先得到發(fā)布但沒有被發(fā)布的記錄，這對于用戶來說，發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)可用性必然低于其期望值。

為此，除了考慮距離之外，本文在選擇聚類種子的時候，還綜合考慮了種子記錄的權重值這個因素。我們定義了選擇因子概念，作為變長聚類算法選擇種子記錄的依據(jù)，選擇因子的計算

其中，選擇因子表示某個記錄在被選擇作為種子進行聚類時的決定參數(shù)，距離表示該記錄距數(shù)據(jù)集質(zhì)心的距離，權重值 （取值范圍：0～1）表示用戶期望該記錄被優(yōu)先發(fā)布出來的程度，權重值越大，表明用戶對該記錄被優(yōu)先發(fā)布的期望值越大。

1.2 匿名化算法

本文提出的基于改進變長聚類的概率k－匿名算法W－VMDAV 的主要思想是：給定一個有n個記錄的數(shù)據(jù)集D 及其權重值集W 和匿名參數(shù)k，首先計算所有記錄的選擇因子并據(jù)此選取一個選擇因子最大的記錄作為第一個類的聚類種子，在剩余記錄中選取k－1個距離該種子記錄最近的記錄加入該類，并對這個類進行擴展，直到該類大小在［k，2k－1）范圍內(nèi)或者沒有記錄能加入這個類時結束。以此類推，重復上述步驟建立下一個聚類。聚類過程結束后，對于剩余記錄，將它們加入到距離最近的類中。最后，對所有類實施交換操作以實現(xiàn)匿名化。

匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量采用文獻 ［9］所定義的聚類前后數(shù)據(jù)集內(nèi)各自相關系數(shù)之間差值的絕對值的平均值來衡量。聚類前后數(shù)據(jù)集內(nèi)各自相關系數(shù)之間差值的絕對值的平均值越接近于零，說明聚類后匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量越高，數(shù)據(jù)可用性越高。

算法1：W－V－MDAV 算法

輸入：原始數(shù)據(jù)集D，權重值集W，匿名參數(shù)k

輸出：匿名數(shù)據(jù)集T

Begin

（1）計算距離矩陣，存儲數(shù)據(jù)集D 中兩兩記錄之間的距離；

（2）計算原始數(shù)據(jù)集D 的質(zhì)心；

（3）計算所有記錄的選擇因子；

（4）while剩余記錄數(shù)remaining＞k－1do

Begin

1）根據(jù)剩余記錄的選擇因子選取一個記錄作為聚類種子；

2）從剩余記錄中選擇距離聚類種子最近的k－1個記錄，生成類cluster；

3）若剩余記錄中某條記錄r 到類cluster 質(zhì)心的距離d1與它到其它剩余記錄的最近距離d2滿足關系［11］：d1＜γ＊d2，且cluster的大小在 ［k，2k－1）內(nèi)，則將r添加到類cluster 中；

End while

（5）若remaining＞0且類cluster的大小在 ［k，2k－1）之內(nèi)，加入剩余記錄后不會破壞類的k－匿名效果，則將剩余記錄加入到距離最近的類；

（6）按照隨機策略對生成的所有類實施交換操作，實現(xiàn)匿名化；

（7）將不能加入到任何類的記錄隱匿；

（8）將匿名數(shù)據(jù)集發(fā)布；

End

W－V－MDAV 算法在選取聚類種子時充分考慮了距離以及權重值這2 個因素的影響，使得聚類種子的選取更優(yōu)，聚類結果更加符合用戶的期望度。然而該算法也還存在著聚類算法本身存在的比較耗時的問題，尤其是對大數(shù)據(jù)集進行聚類時，該問題較為突出。

為此，本文在W－V－MDAV 算法的基礎上，進一步提出融合k－means和W－V－MDAV 算法的概率k－匿名方法，以實現(xiàn)對大數(shù)據(jù)集快速聚類，其主要思想是：給定原始數(shù)據(jù)集D 及其權重值集W 和匿名參數(shù)k，首先使用k－means算法快速地對D 進行初次聚類，得到k 個類；然后建立k個線程，分別對這k 個類并行地使用W－V－MDAV 算法進行再次聚類并對剩余記錄進行處理；最后實施交換操作實現(xiàn)匿名化。

為了與k－匿名中的參數(shù)k 區(qū)分開，下面將k－means算法表述成c－means算法。

算法2：融合c－means與W－V－MDAV 算法的概率k－匿名算法

輸入：原始數(shù)據(jù)集D，權重值集W，匿名參數(shù)k；

輸出：匿名數(shù)據(jù)集T

Begin

（1）計算參數(shù)c：c＝f（n），n 為原始數(shù)據(jù)集D 的記錄數(shù)，函數(shù)f（n）可由用戶定義，如：f（n）＝n／1000×0.6［12］；

（2）使用c－means算法對D 進行初步聚類，得到c個類：C1，C2，...，Cc；

（3）for i＝1to c do in parallel

使用W－V－MDAV 算法對類Ci進行再次聚類并匿名化處理，得到局部聚類結果；

（4）若剩余記錄數(shù)大于0，且有類的大小在 ［k，2k－1）之內(nèi)，加入剩余記錄后不會破壞類的k－匿名效果，則將剩余記錄加入到距離最近的類中；

（5）按照隨機策略對生成的所有類實施交換操作，實現(xiàn)匿名化；

（6）將不能加入到任何類的記錄隱匿；

（7）將匿名數(shù)據(jù)集發(fā)布；

End

算法2將聚類算法c－means和W－V－MDAV 算法有效結合在一起，既實現(xiàn)了聚類和對敏感數(shù)據(jù)匿名化處理，又解決了算法在處理大數(shù)據(jù)集時耗時的問題。

2 實驗結果與分析

實驗硬件環(huán)境為AMD Athlon II X4 645 3.09 GHz CPU、4.0GB RAM，操作系統(tǒng)是Microsoft Windows XP，開發(fā)環(huán)境是Microsoft Visual Studio 2008，采用C＋＋語言以及多線程并行技術編程實現(xiàn)算法。本文采用的數(shù)據(jù)集是EIA 和Forest CoverType，采用與文獻 ［13］一樣的方法對Forest CoverType進行預處理，從其54個屬性中選取10個有意義的數(shù)值型屬性；并分別隨機選取了10000、50000和100000條記錄作為3個子數(shù)據(jù)集。

我們使用算法1表示本文給出的基于改進變長聚類的概率k－匿名算法W－V－MDAV，算法2表示本文給出的融合c－means與W－V－MDAV 算法的概率k－匿名算法。下列實驗結果圖中的數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)集3和數(shù)據(jù)集4分別表示數(shù)據(jù)集EIA （4092條記錄）、數(shù)據(jù)集Forest CoverType（10010條記錄）、數(shù)據(jù)集Forest CoverType（50010條記錄）和數(shù)據(jù)集Forest CoverType（100010條記錄）。

圖1和圖2的實驗結果給出了參數(shù)k 變化時，本文算法1 和文獻 ［9］算法經(jīng)過聚類之后匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量。

圖1 相關系數(shù)之間差值的絕對值的平均值

圖2 相關系數(shù)之間差值的絕對值的平均值

從圖1和圖2中可以看出，一方面，對于不同規(guī)模的數(shù)據(jù)集，本文算法1、文獻 ［9］算法的平均值均隨著k 值的增大呈緩慢增長趨勢，這是因為隨著參數(shù)k 值的增大，由于每個類的大小變大，原來在k 較小時不在同一個類的記錄可能被聚類到一個類中，這必然會相對降低類內(nèi)記錄的相似性，使差異變大，相關系數(shù)之間差值的絕對值變大，平均值也相應增大；另一方面，當k 較小時，本文算法1的匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量略低于文獻 ［9］算法；當k較大時，本文算法1 的匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量略優(yōu)于文獻［9］算法。

圖3和圖4的實驗結果給出了聚類后本文算法1和文獻 ［9］算法產(chǎn)生的信息損失度，對于不同規(guī)模的數(shù)據(jù)集，隨著k值的增大，算法1、文獻 ［9］算法產(chǎn)生的信息損失總體上均逐漸地增大，當k值較小時，文獻 ［9］算法的信息損失度要略小于本文算法1；而當k 值增大到一定值時，算法1產(chǎn)生的信息損失幾乎與文獻 ［9］算法一樣，有些還比文獻 ［9］算法低一些。

使用聚類算法對數(shù)據(jù)集進行聚類之后，會剩下一些無法加入到任何類的記錄，也就是剩余記錄。剩余記錄的選擇因子的平均值大小反映了聚類時對聚類種子記錄選擇的好壞程度。剩余記錄選擇因子的平均值越大，說明剩余記錄中本應該優(yōu)先被選擇做聚類種子進行聚類的記錄沒有被選中，本應優(yōu)先被選中發(fā)布的記錄沒有得到發(fā)布，從而在一定程度上降低了匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量和數(shù)據(jù)可用性。

圖3 信息損失度

圖4 信息損失度

圖5和圖6的實驗結果描述了本文算法1和文獻 ［9］算法聚類后剩余記錄的選擇因子的平均值大小。

圖5的實驗結果表明，當k 值較小時，本文算法1 的剩余記錄選擇因子的平均值略大于文獻 ［9］算法；而當k值增大到一定值時，本文算法1的剩余記錄選擇因子的平均值均明顯地小于文獻 ［9］算法。

圖6 剩余記錄選擇因子的平均值

圖6的實驗結果表明，當k＝5時由于數(shù)據(jù)集大小剛好被k整除，文獻 ［9］算法聚類之后沒有剩余記錄，所以剩余記錄選擇因子的平均值為0；對于其它k值，本文算法1的剩余記錄選擇因子的平均值總體上均明顯地小于文獻［9］算法。這是因為文獻 ［9］算法在選擇記錄做聚類種子的時候只考慮了距離這個因素，它選擇的是距離數(shù)據(jù)集質(zhì)心最遠的記錄作為種子記錄進行聚類，最后的剩余記錄中很可能存在本應優(yōu)先被發(fā)布的記錄但沒有被選取。本文算法1不僅考慮到記錄距離質(zhì)心的距離，還考慮了記錄本身的權重值，根據(jù)這2個因素綜合去選擇更優(yōu)的種子記錄進行聚類。

綜合圖1～圖6的實驗結果分析可知，與文獻 ［9］算法相比，本文算法1沒有使信息損失度明顯上升，也沒有明顯降低聚類前后數(shù)據(jù)集內(nèi)各自相關系數(shù)之間差值的絕對值的平均值，從而沒有降低匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量。本文算法1的剩余記錄選擇因子的平均值總體上均明顯地小于文獻 ［9］算法的平均值；聚類之后，本文算法1發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)可用性高于文獻 ［9］算法。

圖7給出了對于不同規(guī)模的數(shù)據(jù)集，參數(shù)k 變化時，本文算法1和算法2在信息損失度方面的對比。

圖7 信息損失度

圖7的實驗結果表明，對于不同規(guī)模的數(shù)據(jù)集、不同的k 值，本文算法2產(chǎn)生的信息損失度與本文算法1相比沒有明顯地增大，當k值較大時，2個算法產(chǎn)生的信息損失度幾乎一樣。

圖8給出了對于不同規(guī)模的數(shù)據(jù)集，參數(shù)k變化時，本文算法1和算法2聚類后剩余記錄選擇因子的平均值的對比。

圖8 剩余記錄選擇因子的平均值

從圖8的實驗結果中我們可以看到，對于不同規(guī)模的數(shù)據(jù)集和不同的k 值，本文算法2的剩余記錄選擇因子的平均值與本文算法1相差不大，聚類之后，算法2發(fā)布的匿名數(shù)據(jù)集的數(shù)據(jù)質(zhì)量、數(shù)據(jù)可用性均與算法1基本相同。

對于不同規(guī)模的數(shù)據(jù)集和不同的k 值，表1給出了本文算法1與算法2所需的運行時間。

從表1 可知，對于不同規(guī)模的數(shù)據(jù)集、不同的k 值，算法2的運行時間均比算法1要少很多，且當數(shù)據(jù)集的記錄數(shù)越多，算法2的優(yōu)勢越明顯。這是因為c－means算法本身能快速地對大規(guī)模數(shù)據(jù)進行初步的聚類，而對經(jīng)過cmeans算法處理后得到的c個類進行二次聚類、匿名化處理時，由于各個類之間并沒有明顯的關聯(lián)，所以可以并行地進行聚類，從而可以顯著加速算法的執(zhí)行，大大減少算法所需的時間開銷。

表1 本文算法1與算法2的運行時間對比／s

綜上所述，與文獻 ［9］算法相比，在獲得相同的隱私保護程度的基礎上，本文給出的算法1提高了匿名數(shù)據(jù)集的可用性；與本文算法1相比，在獲得相同的隱私保護程度和匿名數(shù)據(jù)集可用性的基礎上，本文給出的算法2很大程度地減少了運行時間，更適用于處理大數(shù)據(jù)集的基于聚類的多敏感屬性數(shù)據(jù)匿名化。

3 結束語

本文綜合考慮了記錄之間的距離與記錄本身權重值對聚類種子記錄選取的影響，建立了聚類種子選擇因子模型，提出了基于改進變長聚類的概率k－匿名算法，在選擇聚類種子時考慮了用戶對記錄得到發(fā)布的期望值，從而使得發(fā)布的匿名數(shù)據(jù)集具有更高的數(shù)據(jù)可用性；同時，針對聚類算法在處理大規(guī)模數(shù)據(jù)時耗時長的問題，采用多線程技術并行聚類，使得融合k－means與W－V－MDAV 算法的概率k－匿名算法在不降低數(shù)據(jù)質(zhì)量、不增加信息損失度的前提下，大大減少了處理大數(shù)據(jù)集所需的時間開銷。下一步工作將研究基于混合型數(shù)據(jù)的聚類算法以及多敏感屬性l－多樣性匿名化算法。

［1］Wang Qian，Xu Zhiwei，Qu Shengzhi.An enhanced k－ano－nymity model against homogeneity attack ［J］.Journal of Software，2011，6 （10）：1945－1952.

［2］Sun Xiaoxun，Sun Lili，Wang Hua.Extended k－anonymity models against sensitive attribute disclosure ［J］.Computer Communications，2011，34 （4）：526－535.

［3］Sun Xiaoxun.A family of enhanced（L，α）－diversity models for privacy preserving data publishing ［J］.Future Generation Computer Systems，2011，27 （3）：348－356.

［4］TENG Jinfang，ZHONG Cheng.Clustering－based sensitive attribute l－diversity anonymization algorithms ［J］.Computer Engineering and Design，2010，31 （20）：4378－4381 （in Chinese）.［滕金芳，鐘誠.基于聚類的敏感屬性l－多樣性匿名化算法 ［J］.計算機工程與設計，2010，31 （20）：4378－4381.］

［5］HAN Jianmin，CEN Tingting，YU Huiqun.Research in Microaggregation Algorithms for k－anonymity ［J］.Acta Electronica Sinica，2008，36 （10）：2021－2029 （in Chinese）.［韓建民，岑婷婷，虞慧群.數(shù)據(jù)表k－匿名化的微聚集算法研究［J］.電子學報，2008，36 （10）：2021－2029.］

［6］YANG Gaoming，YANG Jing，ZHANG Jianpei.Research on data publishing of privacy preserving ［J］.Computer Science，2011，38 （9）：11－17 （in Chinese）. ［楊高明，楊靜，張健沛.隱私保護的數(shù)據(jù)發(fā)布研究 ［J］.計算機科學，2011，38（9）：11－17.］

［7］Md Enamul Kabir，Wang Hua.Systematic clustering－based microaggregation for statistical disclosure control［C］／／Proc of 4th International Conference on Network and System Security，2010：435－441.

［8］Panagiotakis Costas，Tziritas Georgios.Successive group selection for microaggregation ［J］.IEEE Transactions on Knowledge and Data Engineering，2013，25 （5）：1191－1195.

［9］Soria－Comas J，Domingo－Ferrer J.Probabilistic k－anonymity through microaggregation and data swapping ［C］／／Proc of IEEE International Conference on Fuzzy Systems，2012：1－8.

［10］Chettri S K，Borah B.An efficient microaggregation method for protecting mixed data ［C］／／Proc of the Fourth International Conference on Networks ＆ Communications，2013：551－561.

［11］Han Jianmin，Cen Tingting，Yu Huiqun.An improved V－MDAV algorithm for l－Diversity ［C］／／Proc of International Symposiums on Information Processing，2008：733－739.

［12］Han Jianmin，Yu Juan，Yu Huiqun，et al.An efficient kanonymization algorithm combining C－modes with MDAV［C］／／Proc of IEEE International Confe－rence on Granular Computing，2008：257－260.

［13］Marc Solé，Victor Muntés－Mulero，Jordi Nin.Efficient microaggregation techniques for large numerical data volumes［J］.International Journal of Information Security，2012，11（4）：253－267.