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

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001)

近年來(lái)，數(shù)據(jù)的隱私保護(hù)問題越來(lái)越被人們所關(guān)注［1-3］。如何保持隱藏?cái)?shù)據(jù)的聚類可用性，即在隱私保護(hù)和聚類分析間尋求折衷，是目前研究的熱點(diǎn)與難點(diǎn)之一?，F(xiàn)有研究主要通過(guò)基于限制發(fā)布［4-5］和基于數(shù)據(jù)失真［6-7］2 種方式實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)?；谙拗瓢l(fā)布的技術(shù)會(huì)弱化數(shù)據(jù)間的差異，切斷元組間的關(guān)聯(lián)或?qū)傩蚤g的關(guān)聯(lián)，基于數(shù)據(jù)失真的數(shù)據(jù)隱藏技術(shù)通過(guò)擾動(dòng)實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)，有利于數(shù)據(jù)特征的維持。通常采用數(shù)據(jù)失真的方式實(shí)現(xiàn)面向聚類分析的數(shù)據(jù)隱藏。為實(shí)現(xiàn)數(shù)據(jù)隱藏后的聚類可用性，文獻(xiàn)［8］提出一種基于Fourier變換的數(shù)據(jù)擾動(dòng)方法，保證數(shù)據(jù)擾動(dòng)前后元組間的距離差值在一定范圍內(nèi)，以維持隱藏?cái)?shù)據(jù)的聚類效用。文獻(xiàn)［9］對(duì)初始數(shù)據(jù)集聚類并生成類標(biāo)簽，建立滿足聚簇結(jié)構(gòu)分布的匿名數(shù)據(jù)集，以實(shí)現(xiàn)隱藏?cái)?shù)據(jù)的聚類可用性。以上面向聚類分析的數(shù)據(jù)隱私保護(hù)方法主要從保距和保分布2種角度實(shí)現(xiàn)數(shù)據(jù)隱藏后的聚類可用性，但這2種方法都無(wú)法較好地保護(hù)數(shù)據(jù)隱私安全并維持?jǐn)?shù)據(jù)的可用性。2009年，倪巍偉等［10］提出了一種保鄰域隱藏的思想，基于鄰域?qū)傩造鼐S持?jǐn)?shù)據(jù)集中節(jié)點(diǎn)的k鄰域穩(wěn)定性，實(shí)現(xiàn)保護(hù)數(shù)據(jù)集聚類質(zhì)量和數(shù)據(jù)隱私安全的目的，但其僅處理數(shù)據(jù)點(diǎn)的鄰域主屬性值，具有較高的隱私泄露風(fēng)險(xiǎn)。

針對(duì)現(xiàn)有數(shù)據(jù)擾動(dòng)方法不能較好地維持原始數(shù)據(jù)的聚類可用性問題，提出一種基于節(jié)點(diǎn)鄰域拓?fù)鋭?shì)熵的數(shù)據(jù)擾動(dòng)方法DPTPE，該方法將數(shù)據(jù)集中節(jié)點(diǎn)劃分為不同類型，針對(duì)不同類型使用不同的隱私保護(hù)策略，能夠有效地保持?jǐn)?shù)據(jù)集的聚類效用和隱私安全。

1 相關(guān)概念

1.1 鄰域拓?fù)鋭?shì)熵

數(shù)據(jù)發(fā)布中的隱私保護(hù)目的是破壞數(shù)據(jù)表中個(gè)體身份信息與敏感信息的關(guān)聯(lián)，使攻擊者無(wú)法獲取個(gè)體的敏感信息。本文將具有d個(gè)準(zhǔn)標(biāo)識(shí)符屬性的數(shù)據(jù)表T看做d維空間D，表T中的每條元組都可用D中的一個(gè)節(jié)點(diǎn)表示。下文將表T中的元組稱為節(jié)點(diǎn)。

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

式中:pi和qi分別為節(jié)點(diǎn)p和q在屬性Ai上的值。

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

式中:dist(p，o)為節(jié)點(diǎn)p與o間的距離。

定義3 p的k鄰域。p的k鄰域Nk(p)為包含k個(gè)節(jié)點(diǎn)的集合，定義為

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

圖1顯示了k=10時(shí)，二維空間D中點(diǎn)p的k鄰域分布情況。

本文引入拓?fù)鋭?shì)場(chǎng)［11］的思想描述節(jié)點(diǎn)p的k鄰域，將節(jié)點(diǎn)p的k鄰域看作一個(gè)包含k個(gè)節(jié)點(diǎn)及其相互作用的拓?fù)鋭?shì)場(chǎng)，節(jié)點(diǎn)間拓?fù)鋭?shì)的大小反映了節(jié)點(diǎn)間相互作用的大小。

定義4 節(jié)點(diǎn)間拓?fù)鋭?shì)。p與q為d(d≥1)維空間D中的節(jié)點(diǎn)，節(jié)點(diǎn)p與q的拓?fù)鋭?shì)定義為

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

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

本文假定空間D中的每個(gè)節(jié)點(diǎn)質(zhì)量相同且為1。因此，?p、q∈D，節(jié)點(diǎn)p與q間拓?fù)鋭?shì)φ(p，q) 為

定義5 p的鄰域拓?fù)鋭?shì)。p為d(d≥1)維空間D中的節(jié)點(diǎn)，q∈Nk(p)，節(jié)點(diǎn)p的鄰域拓?fù)鋭?shì)定義為

式中:Nk(p)為節(jié)點(diǎn)p的k鄰域，φ(p，q)為節(jié)點(diǎn)p與q間的拓?fù)鋭?shì)。

定義6 p的鄰域拓?fù)鋭?shì)熵。節(jié)點(diǎn)p為d(d≥1)維空間D中的一個(gè)節(jié)點(diǎn)，p的鄰域拓?fù)鋭?shì)熵定義為

式中:φ(p，q)為節(jié)點(diǎn)p與q間的拓?fù)鋭?shì)，φkp()節(jié)點(diǎn)p的鄰域拓?fù)鋭?shì)。

鄰域拓?fù)鋭?shì)熵描述了節(jié)點(diǎn)p的k鄰域內(nèi)節(jié)點(diǎn)的分布情況。NTEk(p)值越大，節(jié)點(diǎn)p的k鄰域內(nèi)節(jié)點(diǎn)的差異性越大、分布越分散，p的k鄰域內(nèi)節(jié)點(diǎn)變化對(duì)p的k鄰域組成的穩(wěn)定性影響越小;反之亦然。

定理1 節(jié)點(diǎn)p的鄰域拓?fù)鋭?shì)熵值不超過(guò)ln k。

證明:設(shè)q∈Nk(p)，節(jié)點(diǎn)p與q在屬性A上的拓?fù)鋭?shì)為φ(p，q)，則根據(jù)定義6，有

因此，

推論1 節(jié)點(diǎn)p的鄰域拓?fù)鋭?shì)熵值為NTEk(p)，設(shè)pi(1≤i≤k)∈Nk(p)，節(jié)點(diǎn)p與pi間的拓?fù)鋭?shì)為 φ ( p，pi)，滿足:

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

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

3)當(dāng)且僅當(dāng)?i(1≤i≤k)，使得φ(p，pi)=1且 ?j≠i(1≤j≤k)，都有φ(p，pj)=0 時(shí)，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，即充分性成立。

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

i＞ 0，因此NTEk(p)=-＞ 0，與NTEk(p)=0矛盾。該矛盾說(shuō)明?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中的節(jié)點(diǎn)p的k鄰域?yàn)镹k(p)，p在D中的鄰域拓?fù)鋭?shì)熵值為NTEk(p)，節(jié)點(diǎn)p在D中的鄰域分散度定義為

鄰域分散度描述了節(jié)點(diǎn)p與其k鄰域中節(jié)點(diǎn)在鄰域分散程度上的對(duì)比。如果節(jié)點(diǎn)p較其k鄰域內(nèi)節(jié)點(diǎn)在鄰域分布上表現(xiàn)出較強(qiáng)分散性，那么節(jié)點(diǎn)p是鄰域分散型節(jié)點(diǎn);反之，節(jié)點(diǎn)p是鄰域緊密型節(jié)點(diǎn)。

定義8 鄰域分散型節(jié)點(diǎn)和鄰域緊密型節(jié)點(diǎn)。d(d≥1)維空間D中的節(jié)點(diǎn)p的k鄰域?yàn)镹k(p)，如果節(jié)點(diǎn)p的鄰域分散度Ndisk(p)＞t，則節(jié)點(diǎn)p為鄰域分散型節(jié)點(diǎn);如果節(jié)點(diǎn) p的鄰域分散度Ndisk(p)≤t，則節(jié)點(diǎn)p為鄰域緊密型節(jié)點(diǎn)。t為用戶對(duì)節(jié)點(diǎn)類型劃分的個(gè)性化設(shè)置，本文在試驗(yàn)中將t值設(shè)置為1。

性質(zhì)1 鄰域分散型節(jié)點(diǎn)的位置變化后，對(duì)其k鄰域產(chǎn)生的影響要大于鄰域緊密型節(jié)點(diǎn)位置變化后對(duì)其k鄰域產(chǎn)生的影響。

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

圖2 不同類型節(jié)點(diǎn)示意圖Fig.2 Schematic diagram of different types of nodes

2 數(shù)據(jù)擾動(dòng)方法

本文提出一種面向聚類分析的數(shù)據(jù)擾動(dòng)方法，通過(guò)分別對(duì)鄰域分散型節(jié)點(diǎn)和鄰域緊密型節(jié)點(diǎn)進(jìn)行擾動(dòng)，在盡量維持節(jié)點(diǎn)的鄰域分布情況下，實(shí)現(xiàn)數(shù)據(jù)集的隱私保護(hù)。

2.1 鄰域分散型節(jié)點(diǎn)的擾動(dòng)方法

鄰域分散型節(jié)點(diǎn)的鄰域分散度高，相對(duì)鄰域緊密型節(jié)點(diǎn)，鄰域分散型節(jié)點(diǎn)位置的改變對(duì)其k鄰域內(nèi)節(jié)點(diǎn)的鄰域穩(wěn)定性影響較大。

性質(zhì)2 若節(jié)點(diǎn)p為d(d≥1)維空間D中的鄰域分散型節(jié)點(diǎn)，使用其k鄰域中節(jié)點(diǎn)位置坐標(biāo)的均值替代p，能夠較好的維持p的k鄰域穩(wěn)定性。

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

證畢。

根據(jù)性質(zhì)2，本文使用鄰域分散型節(jié)點(diǎn)的k鄰域內(nèi)節(jié)點(diǎn)位置坐標(biāo)的均值代替其原始值，能夠更好的維持鄰域分散型節(jié)點(diǎn)的k鄰域穩(wěn)定性。

2.2 鄰域緊密型節(jié)點(diǎn)的擾動(dòng)方法

鄰域緊密型節(jié)點(diǎn)的k鄰域中節(jié)點(diǎn)分布相對(duì)緊密，且與其k鄰域中節(jié)點(diǎn)間距離較近，鄰域緊密型節(jié)點(diǎn)位置在小范圍內(nèi)改變對(duì)其k鄰域影響較小。

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

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

算法1 安全鄰域內(nèi)節(jié)點(diǎn)隨機(jī)選取算法RSN

輸入:屬性個(gè)數(shù) d，節(jié)點(diǎn) p，pk，pk+1

輸出:p的擾動(dòng)后坐標(biāo)p＇

算法步驟:

1)計(jì)算節(jié)點(diǎn)p的安全半徑R=0.5(dist(p，pk+1)-dist(p，pk))，隨機(jī)選擇 r∈ (0，R］;

2)隨機(jī)選取d個(gè)和為r2的正實(shí)數(shù)(a1，a2，…，ad)，對(duì)于d維空間中的每一維做如下操作:

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

②r2=r2-ai;

3)ad=r2

4)對(duì)于p的替換節(jié)點(diǎn)p＇的每一維坐標(biāo)做如下操作:

2.3 面向聚類分析的數(shù)據(jù)擾動(dòng)算法

本文提出一種面向聚類分析的數(shù)據(jù)擾動(dòng)方法，對(duì)不同類型節(jié)點(diǎn)實(shí)行不同擾動(dòng)策略。算法的思想為:對(duì)于數(shù)據(jù)集中的每個(gè)節(jié)點(diǎn)，首先分析該節(jié)點(diǎn)的k鄰域，并根據(jù)節(jié)點(diǎn)的鄰域拓?fù)鋭?shì)熵判斷節(jié)點(diǎn)的性質(zhì);如果該節(jié)點(diǎn)為鄰域分散型，則使用其k鄰域節(jié)點(diǎn)的均值替換該節(jié)點(diǎn)，如果該節(jié)點(diǎn)為鄰域緊密型，則在其安全鄰域中隨機(jī)抽取一個(gè)節(jié)點(diǎn)替換該節(jié)點(diǎn);最后，返回?cái)_動(dòng)后的數(shù)據(jù)。具體的算法如算法2所示。

算法2 基于節(jié)點(diǎn)鄰域拓?fù)鋭?shì)熵的數(shù)據(jù)擾動(dòng)算法DPTPE

輸入:原始數(shù)據(jù)表T，屬性個(gè)數(shù)d，鄰域參數(shù)k

輸出:擾動(dòng)后的數(shù)據(jù)表T’

算法步驟:

1)計(jì)算表T中節(jié)點(diǎn)數(shù)目|T|，如果|T|＜k，則返回重新設(shè)置k值;

2)對(duì)于表T中的每個(gè)節(jié)點(diǎn)做如下操作:

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

②計(jì)算p的鄰域拓?fù)鋭?shì)熵;

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

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

3)返回?cái)_動(dòng)表T＇。

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

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

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

表1 數(shù)據(jù)集信息描述表Table 1 Data set information description

本實(shí)驗(yàn)從k鄰域的穩(wěn)定性和聚類的質(zhì)量?jī)煞矫孢M(jìn)行分析，并將本文所提的 DPTPE算法與文獻(xiàn)［13］中所提的RBT算法、文獻(xiàn)［14］中所提 NeNDS算法進(jìn)行比較。實(shí)驗(yàn)的運(yùn)行環(huán)境為:硬件環(huán)境為Inter Pentium(R)4 CPU 3.00 GHz處理器，2.00 GB內(nèi)存，Micros of tWindows XP操作系統(tǒng)，算法均在VC++6.0與Matlab 7.0混合編程環(huán)境下實(shí)現(xiàn)。

3.1 k鄰域穩(wěn)定性分析

本文使用k鄰域穩(wěn)定性系數(shù)度量節(jié)點(diǎn)p在數(shù)據(jù)擾動(dòng)前后的k鄰域穩(wěn)定性，節(jié)點(diǎn)p的k鄰域穩(wěn)定系數(shù)定義為

數(shù)據(jù)表T的k鄰域穩(wěn)定系數(shù)定義為

式中:T為原始數(shù)據(jù)表，T＇為擾動(dòng)后數(shù)據(jù)表，f(p)為應(yīng)用到T上的擾動(dòng)函數(shù)，Nk(p)為節(jié)點(diǎn)p的k鄰域。

表2給出了3種算法的k鄰域穩(wěn)定性比較。表2可知使用DPTPE算法擾動(dòng)后數(shù)據(jù)表的k鄰域穩(wěn)定性近似于RBT算法且高于NeNDS算法。由于RBT算法基于矩陣變換以保持?jǐn)?shù)據(jù)擾動(dòng)前后元組間的距離，維持節(jié)點(diǎn)k鄰域穩(wěn)定性能力最強(qiáng);DPTPE算法基于節(jié)點(diǎn)鄰域拓?fù)鋭?shì)熵確定節(jié)點(diǎn)類型并應(yīng)用相應(yīng)擾動(dòng)策略，也能夠較好的維持節(jié)點(diǎn)k鄰域穩(wěn)定性，;而NeNDS算法將表中元組分組并進(jìn)行組內(nèi)擾動(dòng)，維持節(jié)點(diǎn)k鄰域穩(wěn)定性的能力最弱。

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

3.2 聚類質(zhì)量分析

F-measure［9］是衡量數(shù)據(jù)隱藏后聚類可用性的常用指標(biāo)。對(duì)原始數(shù)據(jù)集和擾動(dòng)數(shù)據(jù)集應(yīng)用某種聚類算法，獲得的F-measure值越大，擾動(dòng)算法維持?jǐn)?shù)據(jù)聚類可用性的能力越強(qiáng)。分別使用DPTPE算法、RBT算法和NeNDS算法對(duì)3個(gè)數(shù)據(jù)集進(jìn)行擾動(dòng)處理，對(duì)擾動(dòng)前后的數(shù)據(jù)集使用k-means算法和DBScan算法聚類并比較所得的F-measure值。

圖3～5分別給出了3種算法在不同數(shù)據(jù)集上的F-measure值對(duì)比。圖中可知DPTPE算法的F-measure值最高，RBT算法與 DPTPE算法的 F-measure值相近，NeNDS算法的F-measure值最低。這是由于RBT算法能夠在數(shù)據(jù)隱藏后近似保持元組間距離;NeNDS算法通過(guò)割裂屬性間關(guān)聯(lián)以維持每個(gè)屬性分組內(nèi)的數(shù)據(jù)分布，但缺乏對(duì)數(shù)據(jù)集中多維屬性上分布特征的維持;而DPTPE算法對(duì)不同類型節(jié)點(diǎn)應(yīng)用不同的擾動(dòng)策略，在數(shù)據(jù)隱藏的同時(shí)，能夠較好地維持聚類的可用性。

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

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

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

4 結(jié)束語(yǔ)

本文提出一種基于鄰域拓?fù)鋭?shì)熵的節(jié)點(diǎn)分類方法，對(duì)不同類型節(jié)點(diǎn)應(yīng)用不同的擾動(dòng)策略，實(shí)現(xiàn)了隱藏?cái)?shù)據(jù)的聚類可用性。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效地保持?jǐn)?shù)據(jù)的隱私安全和聚類的效果。下一步的工作將優(yōu)化節(jié)點(diǎn)間距離度量的方法和節(jié)點(diǎn)類型劃分方法，更好地實(shí)現(xiàn)數(shù)據(jù)隱私保護(hù)和聚類可用性間的平衡。

［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］楊高明，楊靜，張健沛.半監(jiān)督聚類的匿名數(shù)據(jù)發(fā)布［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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］王智慧，許儉，汪衛(wèi)，等.一種基于聚類的數(shù)據(jù)匿名方法［J］.軟件學(xué)報(bào)，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，F(xiàn)U 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］倪巍偉，陳耿，崇志宏，等.面向聚類的數(shù)據(jù)隱藏發(fā)布研究［J］.計(jì)算機(jī)研究與發(fā)展，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］倪巍偉，徐立臻，崇志宏，等.基于鄰域?qū)傩造氐碾[私保護(hù)數(shù)據(jù)干擾方法［J］.計(jì)算機(jī)研究與發(fā)展，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］淦文燕，赫南，李德毅，等.一種基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法［J］.軟件學(xué)報(bào)，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］倪巍偉，張勇，黃茂峰，等.一種向量等價(jià)置換隱私保護(hù)數(shù)據(jù)干擾方法［J］.軟件學(xué)報(bào)，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.