面向聚類分析的鄰域拓撲勢熵數據擾動方法

張冰，楊靜，張健沛，謝靜

(哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001)

近年來，數據的隱私保護問題越來越被人們所關注［1-3］。如何保持隱藏數據的聚類可用性，即在隱私保護和聚類分析間尋求折衷，是目前研究的熱點與難點之一。現有研究主要通過基于限制發布［4-5］和基于數據失真［6-7］2 種方式實現數據的隱私保護。基于限制發布的技術會弱化數據間的差異，切斷元組間的關聯或屬性間的關聯，基于數據失真的數據隱藏技術通過擾動實現數據的隱私保護，有利于數據特征的維持。通常采用數據失真的方式實現面向聚類分析的數據隱藏。為實現數據隱藏后的聚類可用性，文獻［8］提出一種基于Fourier變換的數據擾動方法，保證數據擾動前后元組間的距離差值在一定范圍內，以維持隱藏數據的聚類效用。文獻［9］對初始數據集聚類并生成類標簽，建立滿足聚簇結構分布的匿名數據集，以實現隱藏數據的聚類可用性。以上面向聚類分析的數據隱私保護方法主要從保距和保分布2種角度實現數據隱藏后的聚類可用性，但這2種方法都無法較好地保護數據隱私安全并維持數據的可用性。2009年，倪巍偉等［10］提出了一種保鄰域隱藏的思想，基于鄰域屬性熵維持數據集中節點的k鄰域穩定性，實現保護數據集聚類質量和數據隱私安全的目的，但其僅處理數據點的鄰域主屬性值，具有較高的隱私泄露風險。

針對現有數據擾動方法不能較好地維持原始數據的聚類可用性問題，提出一種基于節點鄰域拓撲勢熵的數據擾動方法DPTPE，該方法將數據集中節點劃分為不同類型，針對不同類型使用不同的隱私保護策略，能夠有效地保持數據集的聚類效用和隱私安全。

1 相關概念

1.1 鄰域拓撲勢熵

數據發布中的隱私保護目的是破壞數據表中個體身份信息與敏感信息的關聯，使攻擊者無法獲取個體的敏感信息。本文將具有d個準標識符屬性的數據表T看做d維空間D，表T中的每條元組都可用D中的一個節點表示。下文將表T中的元組稱為節點。

定義1 節點間的距離。節點p與q為d(d≥1)維空間D={A1，A2，…，Ad}中的任意2個節點，節點p與q在數值型屬性Ai上的距離distAi(p，q)為distAi(p，q)=，節點p與q在分類型屬性Aj上的距離distAj(p，q)定義為p與q在屬性Aj上的層次距離［3］，因此，節點p與q間的距離定義為

式中:pi和qi分別為節點p和q在屬性Ai上的值。

定義2 p的k鄰域半徑。O為空間D的節點集合，p∈O，若存在o∈O且存在k個節點p＇∈O(p＇≠ p)滿足 dist(p，p＇)≤ dist(p，o)，并且至多有 k-1 個節點 p＇∈ O，滿足 dist(p，p＇)＜ dist(p，o)，則節點p的k鄰域半徑k_rad(p)定義為

式中:dist(p，o)為節點p與o間的距離。

定義3 p的k鄰域。p的k鄰域Nk(p)為包含k個節點的集合，定義為

Nk(p)={p＇∈ D，p＇≠ p|dist(p，p＇)≤ k_rad(p)}式中:dist(p，p＇)為點p與p＇間的距離，k_rad(p)為點p的k鄰域半徑。

圖1顯示了k=10時，二維空間D中點p的k鄰域分布情況。

本文引入拓撲勢場［11］的思想描述節點p的k鄰域，將節點p的k鄰域看作一個包含k個節點及其相互作用的拓撲勢場，節點間拓撲勢的大小反映了節點間相互作用的大小。

定義4 節點間拓撲勢。p與q為d(d≥1)維空間D中的節點，節點p與q的拓撲勢定義為

式中:mq為節點q的質量，dist(p，q)為節點p與q間的距離，影響因子σ＞0為控制每個節點間相互作用的衰減速度與范圍的參數。

圖1 空間D2中點p的k(k=10)鄰域Fig.1 k(k=10)neighborhood of node p in space D2

本文假定空間D中的每個節點質量相同且為1。因此，?p、q∈D，節點p與q間拓撲勢φ(p，q) 為

定義5 p的鄰域拓撲勢。p為d(d≥1)維空間D中的節點，q∈Nk(p)，節點p的鄰域拓撲勢定義為

式中:Nk(p)為節點p的k鄰域，φ(p，q)為節點p與q間的拓撲勢。

定義6 p的鄰域拓撲勢熵。節點p為d(d≥1)維空間D中的一個節點，p的鄰域拓撲勢熵定義為

式中:φ(p，q)為節點p與q間的拓撲勢，φkp()節點p的鄰域拓撲勢。

鄰域拓撲勢熵描述了節點p的k鄰域內節點的分布情況。NTEk(p)值越大，節點p的k鄰域內節點的差異性越大、分布越分散，p的k鄰域內節點變化對p的k鄰域組成的穩定性影響越小;反之亦然。

定理1 節點p的鄰域拓撲勢熵值不超過ln k。

證明:設q∈Nk(p)，節點p與q在屬性A上的拓撲勢為φ(p，q)，則根據定義6，有

因此，

推論1 節點p的鄰域拓撲勢熵值為NTEk(p)，設pi(1≤i≤k)∈Nk(p)，節點p與pi間的拓撲勢為 φ ( p，pi)，滿足:

1)0≤NTEk(p)≤ln k;

2) 當 且 僅 當 φ(p，p1)= φ(p，p2)= …= φ(p，pk)=1/k時，NTEk(p)=ln k;

3)當且僅當?i(1≤i≤k)，使得φ(p，pi)=1且 ?j≠i(1≤j≤k)，都有φ(p，pj)=0 時，NTEk(p)=0。

2)由定理1及條件 φ(p，p1)=… =φ(p，pk)=1/k可知，NTEk(p)=-j

3)充分性:

由推論1的條件3)?i(1≤i≤n)，使得φ(p，pi)=1且 ?j≠i，都有 φ(p，pj)=0及約定0ln0=0可知，NTEk(p)=- φ(p，pi)lnφ(p，pi)=0，即充分性成立。

必要性:當NTEk(p)=0時，如果?i(1≤i≤n)，使得φ(p，p)?{0，1}，則有 -

i＞ 0，因此NTEk(p)=-＞ 0，與NTEk(p)=0矛盾。該矛盾說明?i(1≤i≤n)，都有φ(p，pi)∈ {0，1}，而由=1可知，?i(1≤i≤n)，使得φ(p，pi)=1且?j≠i，都有φ(p，pj)=0，即必要性成立。

1.2 鄰域分散度

定義7 鄰域分散度。d(d≥1)維空間D中的節點p的k鄰域為Nk(p)，p在D中的鄰域拓撲勢熵值為NTEk(p)，節點p在D中的鄰域分散度定義為

鄰域分散度描述了節點p與其k鄰域中節點在鄰域分散程度上的對比。如果節點p較其k鄰域內節點在鄰域分布上表現出較強分散性，那么節點p是鄰域分散型節點;反之，節點p是鄰域緊密型節點。

定義8 鄰域分散型節點和鄰域緊密型節點。d(d≥1)維空間D中的節點p的k鄰域為Nk(p)，如果節點p的鄰域分散度Ndisk(p)＞t，則節點p為鄰域分散型節點;如果節點 p的鄰域分散度Ndisk(p)≤t，則節點p為鄰域緊密型節點。t為用戶對節點類型劃分的個性化設置，本文在試驗中將t值設置為1。

性質1 鄰域分散型節點的位置變化后，對其k鄰域產生的影響要大于鄰域緊密型節點位置變化后對其k鄰域產生的影響。

證明:如圖2所示，設p為鄰域分散型節點，q為鄰域緊密型節點，φk( p )=φk( q)，節點p和q的k鄰域半徑相同且為r。根據p和q的鄰域分散性，有NTEk(p)＞NTEk(q)。由定義4可知，節點間距離越大，節點間拓撲勢越小;由于?t∈Nk(p)，0＜≤1及定義6節點拓撲勢熵函數，可知?t∈Nk(p)，dis(p，t)越大，越大。因此，節點p的k鄰域中大多節點呈遠離p的趨勢，節點q的k鄰域中大多節點呈靠近q的趨勢。由φk( p )=φk( q)，在q的k鄰域中必然存在少部分節點與q間距離近似于r。由于q的k鄰域中部分節點距離q較近，部分與q間距離近似于r，因此，q在小范圍內改變位置對其k鄰域內節點的鄰域影響較小;而p的k鄰域中節點大多遠離p，p的小范圍位置變化也會對其k鄰域中節點的鄰域產生較大影響。因此，鄰域分散型節點的位置變化后，對其k鄰域產生的影響要大于鄰域緊密型節點位置變化后對其k鄰域產生的影響。

圖2 不同類型節點示意圖Fig.2 Schematic diagram of different types of nodes

2 數據擾動方法

本文提出一種面向聚類分析的數據擾動方法，通過分別對鄰域分散型節點和鄰域緊密型節點進行擾動，在盡量維持節點的鄰域分布情況下，實現數據集的隱私保護。

2.1 鄰域分散型節點的擾動方法

鄰域分散型節點的鄰域分散度高，相對鄰域緊密型節點，鄰域分散型節點位置的改變對其k鄰域內節點的鄰域穩定性影響較大。

性質2 若節點p為d(d≥1)維空間D中的鄰域分散型節點，使用其k鄰域中節點位置坐標的均值替代p，能夠較好的維持p的k鄰域穩定性。

證明:設d(d≥1)維空間D中的不同屬性集合為{A1，A2，…，Ad}，則節點 p的位置坐標可表示為(p1，p2，…，pd)，則 ?q ∈ Nk(p)，p 與 q 間的距離差異可描述為dif(p，q)=

證畢。

根據性質2，本文使用鄰域分散型節點的k鄰域內節點位置坐標的均值代替其原始值，能夠更好的維持鄰域分散型節點的k鄰域穩定性。

2.2 鄰域緊密型節點的擾動方法

鄰域緊密型節點的k鄰域中節點分布相對緊密，且與其k鄰域中節點間距離較近，鄰域緊密型節點位置在小范圍內改變對其k鄰域影響較小。

文獻［12］提出了安全鄰域的概念，并證明了節點p和其替換節點p＇間的距離|pp＇|≤0.5(dist(p，pk+1)-dist(p，pk))，則在p的k鄰域保持不變的情況下，使用p＇替換p后能夠保持p的k鄰域的穩定性。據此，對于鄰域緊密型節點，本文使用在安全鄰域內隨機選擇一個節點替換其原始值，在保護節點的隱私安全同時，能夠最大程度維持原始節點的k鄰域穩定性。

設節點p在d維空間中的初始坐標為(p1，p2，…，pd)，0 ＜ r≤0.5(dist(p，pk+1)-dist(p，pk))，在p的安全鄰域內隨機選擇一個節點p＇，可轉化為求解方程組(p1-)2+(p2-)2+…+(pd-)2-r2=0的一組實數解。安全鄰域內節點隨機選取算法RSN的思想為:首先，隨機選取d個和為r2的正實數(a1，a2，…，ad);然后，對于節點 p的每一維坐標值 pi，令(pi-)2=ai，即=pi±，即可得到pi的轉換值。具體的算法如算法1所示。

算法1 安全鄰域內節點隨機選取算法RSN

輸入:屬性個數 d，節點 p，pk，pk+1

輸出:p的擾動后坐標p＇

算法步驟:

1)計算節點p的安全半徑R=0.5(dist(p，pk+1)-dist(p，pk))，隨機選擇 r∈ (0，R］;

2)隨機選取d個和為r2的正實數(a1，a2，…，ad)，對于d維空間中的每一維做如下操作:

①隨機選擇ai∈［0，r2);

②r2=r2-ai;

3)ad=r2

4)對于p的替換節點p＇的每一維坐標做如下操作:

2.3 面向聚類分析的數據擾動算法

本文提出一種面向聚類分析的數據擾動方法，對不同類型節點實行不同擾動策略。算法的思想為:對于數據集中的每個節點，首先分析該節點的k鄰域，并根據節點的鄰域拓撲勢熵判斷節點的性質;如果該節點為鄰域分散型，則使用其k鄰域節點的均值替換該節點，如果該節點為鄰域緊密型，則在其安全鄰域中隨機抽取一個節點替換該節點;最后，返回擾動后的數據。具體的算法如算法2所示。

算法2 基于節點鄰域拓撲勢熵的數據擾動算法DPTPE

輸入:原始數據表T，屬性個數d，鄰域參數k

輸出:擾動后的數據表T’

算法步驟:

1)計算表T中節點數目|T|，如果|T|＜k，則返回重新設置k值;

2)對于表T中的每個節點做如下操作:

①獲取p的k鄰域點集Nk(p)及pk+1;

②計算p的鄰域拓撲勢熵;

③計算p的鄰域分散度Ndisk(p);

④ 如果Ndisk(p)＞1，則=qi;否則，執行算法 1，RSN(d，p，pk，pk+1);

3)返回擾動表T＇。

算法的步驟1)進行初始化工作，假設表T的元組數目為n，則步驟1)判定k值的設置合理性，可在O(n)內完成。步驟2)為表T中節點坐標的替換，對每個節點首先獲取節點的k鄰域點集，至多需時間kO(n);然后計算節點的鄰域拓撲勢熵和鄰域分散度，可在時間O(n)內完成;對于鄰域分散型節點，使用其k鄰域中節點分別在每個屬性上的均值替換其原始值，需時間O(d)，對于鄰域緊密型節點，在安全鄰域中隨機選擇一個節點代替其原始值，至多需時間O(d);因此步驟2)每擾動一個節點可在時間O(n)+O(d)內完成。步驟3)為擾動表T’的發布。由于k?n且d為常數，因此，DPTPE算法可在時間O(n2)內實現數據表的擾動保護。

3 實驗結果分析

實驗采用UCI數據集中Forest fires、Magic gamma telescope和Poker hand 3個數據集作為本次實驗數據，這些數據集被廣泛應用于聚類分析的研究中。刪除這3個數據集中存在缺省值的記錄并去除分類型屬性，3個數據集的具體描述如表1所示。

表1 數據集信息描述表Table 1 Data set information description

本實驗從k鄰域的穩定性和聚類的質量兩方面進行分析，并將本文所提的 DPTPE算法與文獻［13］中所提的RBT算法、文獻［14］中所提 NeNDS算法進行比較。實驗的運行環境為:硬件環境為Inter Pentium(R)4 CPU 3.00 GHz處理器，2.00 GB內存，Micros of tWindows XP操作系統，算法均在VC++6.0與Matlab 7.0混合編程環境下實現。

3.1 k鄰域穩定性分析

本文使用k鄰域穩定性系數度量節點p在數據擾動前后的k鄰域穩定性，節點p的k鄰域穩定系數定義為

數據表T的k鄰域穩定系數定義為

式中:T為原始數據表，T＇為擾動后數據表，f(p)為應用到T上的擾動函數，Nk(p)為節點p的k鄰域。

表2給出了3種算法的k鄰域穩定性比較。表2可知使用DPTPE算法擾動后數據表的k鄰域穩定性近似于RBT算法且高于NeNDS算法。由于RBT算法基于矩陣變換以保持數據擾動前后元組間的距離，維持節點k鄰域穩定性能力最強;DPTPE算法基于節點鄰域拓撲勢熵確定節點類型并應用相應擾動策略，也能夠較好的維持節點k鄰域穩定性，;而NeNDS算法將表中元組分組并進行組內擾動，維持節點k鄰域穩定性的能力最弱。

表2 3種算法的k鄰域穩定性比較Table 2 Comparison of k neighborhood stability between three algorithms

3.2 聚類質量分析

F-measure［9］是衡量數據隱藏后聚類可用性的常用指標。對原始數據集和擾動數據集應用某種聚類算法，獲得的F-measure值越大，擾動算法維持數據聚類可用性的能力越強。分別使用DPTPE算法、RBT算法和NeNDS算法對3個數據集進行擾動處理，對擾動前后的數據集使用k-means算法和DBScan算法聚類并比較所得的F-measure值。

圖3～5分別給出了3種算法在不同數據集上的F-measure值對比。圖中可知DPTPE算法的F-measure值最高，RBT算法與 DPTPE算法的 F-measure值相近，NeNDS算法的F-measure值最低。這是由于RBT算法能夠在數據隱藏后近似保持元組間距離;NeNDS算法通過割裂屬性間關聯以維持每個屬性分組內的數據分布，但缺乏對數據集中多維屬性上分布特征的維持;而DPTPE算法對不同類型節點應用不同的擾動策略，在數據隱藏的同時，能夠較好地維持聚類的可用性。

圖3 T1上F-measure值對比Fig.3 Comparison of F-measure values in dataset T1

圖4 T2上F-measure值對比Fig.4 Comparison of F-measure values in dataset T2

圖5 T3上F-measure值對比Fig.5 Comparison of F-measure values in dataset T3

4 結束語

本文提出一種基于鄰域拓撲勢熵的節點分類方法，對不同類型節點應用不同的擾動策略，實現了隱藏數據的聚類可用性。實驗結果表明，該方法能夠有效地保持數據的隱私安全和聚類的效果。下一步的工作將優化節點間距離度量的方法和節點類型劃分方法，更好地實現數據隱私保護和聚類可用性間的平衡。

［1］FUNG B CM，WANG K，CHEN R，et al.Privacy-preserving data publishing:a survey of recent developments［J］.ACM Comput Surv，2010，42(4):1-53.

［2］楊高明，楊靜，張健沛.半監督聚類的匿名數據發布［J］.哈爾濱工程大學學報，2011，32(11):1489-1494.YANG Gaoming，YANG Jing，ZHANG Jianpei.Semi-supervised clustering-based anonymous data publishing［J］.Journal of Harbin Engineering University，2011，32(11):1489-1494.

［3］王智慧，許儉，汪衛，等.一種基于聚類的數據匿名方法［J］.軟件學報，2010，21(4):680-693.WANG Zhihui，XU Jian，WANG Wei，et al.Clusteringbased approach for data anonymization［J］.Journal of S of tware，2010，21(4):680-693.

［4］MACHANAVAJJHALA A，KIFER D，GEHRKE J，et al.L-diversity:privacy beyond k-anonymity［J］.ACM Transactions on Knowledge Discovery from Data，2007，1(1):1-52.

［5］WONG R，LIJ，FU A，et al.(α，k)-anonymous data publishing［J］.Journal of Intelligent Information Systems，2009，33(2):209-234.

［6］PARAMESWARAN R，BLOUGH D M.Privacy preserving data obfuscation for inherently clustered data［J］.Journal of Information and Computer Security，2008，2(1):1744-1765.

［7］倪巍偉，陳耿，崇志宏，等.面向聚類的數據隱藏發布研究［J］.計算機研究與發展，2012，49(5):1095-1104.NIWeiwei，CHEN Geng，CHONG Zhihong，et al.Privacypreserving data publishing for clustering［J］.Journal of Computer Research and Development，2012，49(5):1095-1104.

［8］MUKHERJEE S，CHEN Z Y，GANGOPADHYAY A.A privacy-preserving technique for Euclidean distance-based mining algorithms using Fourier-related transforms［J］.Journal on Very Large Data Bases，2006，15(4):293-315.

［9］FUNG B CM，WANG K，WANG L Y，et al.Privacy-preserving data publishing for cluster analysis［J］.Data ＆Knowledge Engineering，2009，68(6):552-575.

［10］倪巍偉，徐立臻，崇志宏，等.基于鄰域屬性熵的隱私保護數據干擾方法［J］.計算機研究與發展，2009，46(3):498-504.NIWeiwei，XU Lizhen，CHONG Zhihong，et al.A privacy preserving data perturbation algorithm based on neighborhood entropy［J］.Journal of Computer Research and Development，2009，46(3):498-504.

［11］淦文燕，赫南，李德毅，等.一種基于拓撲勢的網絡社區發現方法［J］.軟件學報，2009，20(8):2241-2254.GANWenyan，HE Nan，LIDeyi，et al.Community discovery method in networks based on topological potential［J］.Journal of S of tware，2009，20(8):2241-2254.

［12］倪巍偉，張勇，黃茂峰，等.一種向量等價置換隱私保護數據干擾方法［J］.軟件學報，2012，23(12):3198-3208.NIWeiwei，ZHANG Yong，HUANG Maofeng，et al.Vector equivalent replacing based privacy-preserving perturbing method［J］.Journal of Software，2012，23(12):3198-3208.

［13］OLIVEIRA SRM，ZAIANEO R.Achieving privacy preservation when sharing data for clustering［C］//Proceedings of the 2004 SDM Conference.Toronto，Canada，2004:67-82.

［14］RUPA P，DOUGLASM B.Privacy preserving data obfuscation for inherently clustered data［J］.International Journal of Information and Computer Security，2008，2(1):1744-1765.