劉英華

(中國(guó)青年政治學(xué)院，北京 100089)

1 引言

自1995年提出隱私保護(hù)數(shù)據(jù)挖掘以來(lái)，隱私保護(hù)數(shù)據(jù)挖掘就成為了數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)和難點(diǎn)。隱私保護(hù)技術(shù)主要有數(shù)據(jù)擾動(dòng)技術(shù)、匿名化技術(shù)和安全多方計(jì)算技術(shù)[1]。數(shù)據(jù)擾動(dòng)技術(shù)隱藏了真實(shí)數(shù)據(jù)，挖掘者只能在被擾動(dòng)的數(shù)據(jù)上挖掘知識(shí)(如添加了噪聲、數(shù)據(jù)交換等)；匿名化技術(shù)則是泛化和抑制操作微調(diào)了原始數(shù)據(jù)對(duì)象屬性值，數(shù)據(jù)擾動(dòng)技術(shù)、匿名化技術(shù)都改變了原始數(shù)據(jù)，即在被修改了的數(shù)據(jù)上完成挖掘任務(wù)。

聚類分析是數(shù)據(jù)挖掘研究的一個(gè)重要部分，是實(shí)現(xiàn)數(shù)據(jù)深層使用價(jià)值的一個(gè)重要步驟，也是其他挖掘任務(wù)的基礎(chǔ)，聚類分析在數(shù)據(jù)挖掘領(lǐng)域得到了廣泛的研究和應(yīng)用[2]?？梢詫⒕垲惙治鲎鳛閱为?dú)的工具使用，分析、發(fā)現(xiàn)數(shù)據(jù)庫(kù)中存在的知識(shí)和信息，并且對(duì)聚類分析的每一類總結(jié)其特點(diǎn)。針對(duì)聚類分析的某個(gè)類，還可以聚類二次分析出更深層次的知識(shí)和信息，并以此類推，進(jìn)行聚類的n次分析，所以也可以認(rèn)為聚類分析是其他數(shù)據(jù)挖掘模型中的一個(gè)預(yù)先處理過(guò)程[3]。

聚類分析是根據(jù)數(shù)據(jù)對(duì)象的相似度劃分為若干個(gè)群組(簇)，而隱私保護(hù)中的數(shù)據(jù)擾動(dòng)技術(shù)、匿名化技術(shù)微調(diào)了原始數(shù)據(jù)對(duì)象屬性值，這種操作將導(dǎo)致相似度計(jì)算值的誤差，從而引起數(shù)據(jù)分布、密度特征的改變，進(jìn)而影響群組的劃分結(jié)果[4]。只有隱私保護(hù)中的安全多方計(jì)算技術(shù)，沒(méi)有改變?cè)紨?shù)據(jù)集，而是加密后傳輸，確保參與方信息的獨(dú)立性和計(jì)算的正確性，同時(shí)又可以保護(hù)各參與方的信息不泄露給其他參與方或第三方。在基于安全多方計(jì)算技術(shù)隱私保護(hù)的數(shù)據(jù)集上完成聚類分析才能保證劃分的群組與在原始數(shù)據(jù)上聚類分析劃分的群組是完全一致的[5]。

本文提出的FHE-DBIRCH(Fully Homomorphism Encryption-Distribute Balanced Herative Reducing and Clustering using Hierarchies)模型是針對(duì)水平分布式數(shù)據(jù)存放模式，將各從數(shù)據(jù)集通過(guò)完全同態(tài)加密算法加密后發(fā)送到主數(shù)據(jù)集，并對(duì)主數(shù)據(jù)集的數(shù)據(jù)計(jì)算后解密，所有的計(jì)算對(duì)象均為加密后的數(shù)據(jù)。所以，半可信第三方數(shù)據(jù)挖掘者的聚類挖掘?qū)ο笠彩羌用軘?shù)據(jù)，無(wú)法重構(gòu)原始數(shù)據(jù)，避免了原始數(shù)據(jù)的隱私泄露。理論證明了FHE-DBIRCH模型在聚類挖掘時(shí)對(duì)隱私的保護(hù)是可行的，并通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證。

2 問(wèn)題描述

3 FHE-DBIRCH模型

為實(shí)現(xiàn)水平分布式數(shù)據(jù)集的隱私保護(hù)聚類挖掘，首先要實(shí)現(xiàn)各終端Ti到主數(shù)據(jù)集的隱私保護(hù)，首選的方法是加密技術(shù)[6～8]。

3.1 完全同態(tài)加密技術(shù)

完全同態(tài)加密FHE(Fully Homomorphism Encryption)技術(shù)是2009年由IBM研究員Gentry C首次提出的[9]。

定義1加密算法α，解密算法β，明文mi，運(yùn)算符⊕和?。若存在公式α(β(m1)⊕β(m2)⊕…⊕β(mi))=α(β(m1+m2+…+mi))，即單個(gè)從數(shù)據(jù)集加密后進(jìn)行的某種“加”計(jì)算后解密得到的結(jié)果，與單個(gè)從數(shù)據(jù)集“加”計(jì)算后加密后再解密得到的結(jié)果是相同的，則加密算法α和解密算法β基于運(yùn)算符⊕滿足同態(tài)加密。若存在公式α(β(m1)?β(m2)?…?β(mi))=α(β(m1×m2×…×mi))，則加密算法α和解密算法β基于運(yùn)算符?滿足同態(tài)加密。若兩個(gè)公式均存在，則加密算法α和解密算法β基于運(yùn)算符⊕和?滿足完全同態(tài)加密。

算法1加密數(shù)據(jù)為m，密鑰是大數(shù)p(一個(gè)大數(shù))，大數(shù)k(隨機(jī)生成，且k符合條件m<

加密算法：E(m)=qp+kr+m;

解密算法：D(E(m))=(E(m) modp)modk。

則算法1是一個(gè)符合完全同態(tài)加密的算法。

證明假設(shè)E(mi)=qip+kri+mi,則有：

E(m1)+E(m2)+…+E(mi)= (q1+q2+…+qi)p+(r1+r2+…+ri)k+(m1+m2+…+mi)

因?yàn)?r1+r2+…+ri)k+(m1+m2+…+mi)<

D(E(m1)+E(m2)+…+E(mi))=((E(m1)+E(m2)+…+E(mi)) modp) modk=(k(r1+r2+…+ri)+(m1+m2+…+mi)) modk=m1+m2+…+mi

則有E(m1)×E(m2)×…×E(mi)= (γ)p+(δ)k+(m1×m2×…×mi)，

其中(γ)p表示p的倍數(shù)，(δ)k表示k的倍數(shù)，

因?yàn)?δ)k+(m1×m2×…×mi) <

D(E(m1) ×E(m2)× …×E(mi))=((E(m1)×E(m2)×…×E(mi))modp) modk=((δ)k+(m1×m2×…×mi)) modk=m1×m2×…×mi得證。

□

加密算法E(m)的時(shí)間復(fù)雜度為O(1)，解密算法D(E(m))的時(shí)間復(fù)雜度為O(1)。

3.2 分布式BIRCH模型

分布式BIRCH(DBIRCH) 模型針對(duì)主數(shù)據(jù)集、從數(shù)據(jù)集分布式存儲(chǔ)結(jié)構(gòu)，將各從數(shù)據(jù)集Di(i=1,2,…,n;n≥3)計(jì)算出CFi樹后發(fā)送到主數(shù)據(jù)集，主數(shù)據(jù)集聯(lián)合從數(shù)據(jù)集發(fā)來(lái)的CFi樹構(gòu)建聯(lián)合數(shù)據(jù)集CF樹(即主CF樹)。然后,采用PAM算法對(duì)主CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，刪除離群點(diǎn)(即稀疏的簇)，合并稠密簇。

算法2分布式BIRCH算法

輸入：各站點(diǎn)數(shù)據(jù)集Di，每個(gè)Di對(duì)象個(gè)數(shù)mi(i=1,…,n;n≥3)，B值(任何的非葉節(jié)點(diǎn)可以擁有的孩子數(shù)目)，L值(葉子節(jié)點(diǎn)最多擁有的元組數(shù)目)，聚簇個(gè)數(shù)k。

輸出：k個(gè)聚簇。

分布式BIRCH算法——主數(shù)據(jù)集：

(1)fori=1 ton

(2)接收各站點(diǎn)發(fā)來(lái)的CFi樹

(3)end for

(4)構(gòu)建主CF樹

①設(shè)CF1的根節(jié)點(diǎn)是主CF樹的根節(jié)點(diǎn)，非葉子節(jié)點(diǎn)根據(jù)root(CF1)逐級(jí)確定最近的子節(jié)點(diǎn)；

②葉子節(jié)點(diǎn)則計(jì)算最接近的元組Li可否吸收；

i.是，更新CF值；

ii.否，判定是否增加新元組;

a)是，增加新元組；

b)否，分裂距離最遠(yuǎn)的元組，并將其作為種子分配給距離最近的元組；

③更新每一個(gè)非葉子節(jié)點(diǎn)的CF值，若分裂此節(jié)點(diǎn)node，則在parent(node)插入新元組直至分裂到根節(jié)點(diǎn)；

④合并：若在Nj節(jié)點(diǎn)(非葉子節(jié)點(diǎn))不再分裂，則將離Nj最近的兩個(gè)節(jié)點(diǎn)的元組合并。

⑤輸出主CF樹；

(5)在CF樹中任選k個(gè)葉子節(jié)點(diǎn)；

(6)repeat

(7)分配剩余葉子到最近的代表對(duì)象所代表的簇；

(8)遞歸修改CF樹中非葉子節(jié)點(diǎn)的CF值；

(9)隨機(jī)選擇對(duì)象O并計(jì)算O交換Oj的代價(jià)；

(10)若代價(jià)<0，則Oj=O；

(11)until 不再發(fā)生變化;

分布式BIRCH算法——從數(shù)據(jù)集：

(1)fori=1 ton

(2)從根節(jié)點(diǎn)開始逐級(jí)確定非葉子節(jié)點(diǎn)最近的子節(jié)點(diǎn)；

(3)若是葉子節(jié)點(diǎn)，則計(jì)算最接近的元組Li可否吸收；

①是，更新CF值；

②否，再次判定可否增加一個(gè)新元組；

i.是，更新CF值；

ii.否，分裂距離最遠(yuǎn)的元組,并將其作為種子分配給距離最近的元組；

(4)更新除葉子節(jié)點(diǎn)外的其他節(jié)點(diǎn)的CF值，若分裂此節(jié)點(diǎn)node，則為parent(node)插入新元組,直至分裂到根節(jié)點(diǎn)；

(5)合并：若在Nj節(jié)點(diǎn)(非葉子節(jié)點(diǎn))不再分裂，則將離Nj最近的兩個(gè)節(jié)點(diǎn)的元組合并；

(6)發(fā)送CFi樹到主站點(diǎn)；

(7)end for

3.3 隱私保護(hù)FHE-DBIRCH模型

FHE-DBIRCH算法的基本思想是在從數(shù)據(jù)集計(jì)算CFi值，然后加密傳輸?shù)街鲾?shù)據(jù)集;主數(shù)據(jù)集對(duì)密文進(jìn)行某種計(jì)算后，解密后再構(gòu)建聯(lián)合數(shù)據(jù)集CF樹(即主CF樹)。然后，采用PAM算法對(duì)主CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，刪除離群點(diǎn)(即稀疏的簇)，合并稠密簇。最后，將主站點(diǎn)計(jì)算的k個(gè)簇的集合廣播給各從站點(diǎn)Si。

模型中傳輸?shù)臄?shù)據(jù)均為加密數(shù)據(jù)，保證了原始數(shù)據(jù)的隱私性，但因?yàn)榧用?、解密操作增加了額外開銷，必然導(dǎo)致FHE-DBIRCH模型的運(yùn)行時(shí)間高于DBIRCH模型。

算法3FHE-DBIRCH算法

輸入：各站點(diǎn)數(shù)據(jù)集Di，每個(gè)Di對(duì)象個(gè)數(shù)mi(i=1，…，n;n≥3)，B值(任何的非葉節(jié)點(diǎn)可以擁有的孩子數(shù)目)，L值(葉子節(jié)點(diǎn)最多擁有的元組數(shù)目)，聚簇個(gè)數(shù)k。

輸出：k個(gè)聚簇。

FHE-DBIRCH算法——主數(shù)據(jù)集：

(1)fori=1 ton

(2)接收各站點(diǎn)發(fā)來(lái)的加密CFi樹，根據(jù)解密算法得到CFi樹;

(3)end for

(4)構(gòu)建主CF樹;

①設(shè)CF1的根節(jié)點(diǎn)是主CF樹的根節(jié)點(diǎn)，非葉子節(jié)點(diǎn)根據(jù)root(CF1)逐級(jí)確定最近的子節(jié)點(diǎn)；

②葉子節(jié)點(diǎn)則計(jì)算最接近的元組Li可否吸收；

i.是，更新CF值；

ii.否，判定是否增加新元組；

a)是，增加新元組；

b)否，分裂距離最遠(yuǎn)的元組,并將其作為種子分配給距離最近的元組；

③更新除葉子節(jié)點(diǎn)外的其他節(jié)點(diǎn)的CF值，若分裂此節(jié)點(diǎn)node，則為parent(node)插入新元組直至分裂到根節(jié)點(diǎn)；

④合并：若在Nj節(jié)點(diǎn)(非葉子節(jié)點(diǎn))處不再分裂，則將離Nj最近的兩個(gè)節(jié)點(diǎn)的元組合并;

⑤輸出主CF樹；

(5)在CF樹中任選k個(gè)葉子節(jié)點(diǎn)；

(6)repeat

(7)分配剩余葉子到最近的代表對(duì)象所代表的簇；

(8)遞歸修改CF樹中非葉子節(jié)點(diǎn)的CF值；

(9)隨機(jī)選擇對(duì)象O，計(jì)算O交換Oj的代價(jià)；

(10)若代價(jià)<0，則Oj=O；

(11)until 不再發(fā)生變化;

FHE-DBIRCH算法——從數(shù)據(jù)集：

(1)fori=1 ton

(2)從根節(jié)點(diǎn)開始逐級(jí)確定非葉子節(jié)點(diǎn)最近的子節(jié)點(diǎn)；

(3)葉子節(jié)點(diǎn)則計(jì)算最接近的元組Li可否吸收；

①是，更新CF值；

②否，再次判定可否增加一個(gè)新元組；

a)是，更新CF值；

b)否，分裂距離最遠(yuǎn)的元組,并將其作為種子分配給距離最近的元組；

(4)更新除葉子節(jié)點(diǎn)外的其他節(jié)點(diǎn)的CF值，若分裂此節(jié)點(diǎn)node，則為parent(node)插入新元組直至分裂到根節(jié)點(diǎn)；

(5)合并：若在Nj節(jié)點(diǎn)(非葉子節(jié)點(diǎn))處不再分裂，則將離Nj最近的兩個(gè)節(jié)點(diǎn)的元組合并；

(7)end for

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

實(shí)驗(yàn)平臺(tái)是具有以下參數(shù)的PC機(jī)：賽揚(yáng)2.6 GHz CPU,4 GB內(nèi)存，1 TB硬盤,Windows XP操作系統(tǒng)。本實(shí)驗(yàn)隨機(jī)挑選了UCI中的三個(gè)數(shù)據(jù)集，在Weka平臺(tái)下封裝了FHE-DBIRCH算法，對(duì)三個(gè)數(shù)據(jù)集分別實(shí)現(xiàn)BIRCH算法和FHE-DBIRCH算法的對(duì)比實(shí)驗(yàn)。

評(píng)價(jià)聚類挖掘結(jié)果的重要指標(biāo)之一是聚類精度，聚類精度是用有明確的分類結(jié)構(gòu)的數(shù)據(jù)作為輸入樣本，對(duì)比聚類結(jié)果和數(shù)據(jù)原來(lái)的分類結(jié)構(gòu)，以評(píng)價(jià)聚類算法的優(yōu)劣[10]。

因?yàn)椴捎肍HE-DBIRCH算法的從數(shù)據(jù)集傳輸時(shí)均為加密后的數(shù)據(jù)，其他數(shù)據(jù)集都不能獲取其他從數(shù)據(jù)集的明文數(shù)據(jù)，所以FHE-DBIRCH算法避免了從數(shù)據(jù)集的隱私泄露。本文的FHE-DBIRCH算法符合完全同態(tài)加密，因此FHE-DBIRCH算法與不加隱私保護(hù)的聚類算法得到的聚類結(jié)果完全一致，即聚類精度一致。實(shí)驗(yàn)結(jié)果如圖1所示。

Figure 1 Comparison of clustering accuracy圖1 聚類精度比較

FHE-DBIRCH算法需要加密解密過(guò)程，因此時(shí)間成本增加，相對(duì)不加隱私保護(hù)的BIRCH算法成本增加小于15%，如圖2所示。

Figure 2 Comparison of execution time圖2 執(zhí)行時(shí)間比較

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

本文針對(duì)水平分布式環(huán)境中聚類數(shù)據(jù)挖掘算法中存在的隱私泄露問(wèn)題，提出了一種完全同態(tài)加密FHE-DBIRCH模型。該模型將水平分布式數(shù)據(jù)分為主、從兩個(gè)數(shù)據(jù)集，采用完全同態(tài)加密算法對(duì)從數(shù)據(jù)集的數(shù)據(jù)進(jìn)行加密，加密后的從數(shù)據(jù)集傳送到主數(shù)據(jù)集，主數(shù)據(jù)集對(duì)加密后的從數(shù)據(jù)集計(jì)算后得到結(jié)果再解密。 這樣的結(jié)果與各從數(shù)據(jù)集直接計(jì)算得到的結(jié)果是一致的。通過(guò)理論證明和實(shí)驗(yàn)數(shù)據(jù)的分析均確認(rèn)該模型可以保護(hù)水平分布式數(shù)據(jù)的隱私，在加密的同時(shí)實(shí)現(xiàn)聚類挖掘。

[1] Zhou Shui-geng, Li Feng, Tao Yu-fei, et al. Privacy preservation in database applications:A survey[J]. Chinese Journal of Computers, 2009, 32(5):847-860.(in Chinese)

[2] Han Jia-wei. Data mining concepts and techniques[M]. Beijing:China Machine Press, 2001.(in Chinese)

[3] Chong Zhi-hong, Ni Wei-wei, Liu Teng-teng, et al. A privacy-preserving data publishing algorithm for clustering application[J]. Journal of Computer Research and Development, 2010,47(12):2083-2089.(in Chinese)

[4] Gentry C. Fully homomorphic encryption using ideal lattices[C]∥Proc of the 41st Annual ACM Symposium on Theory of Computing (STOC’09), 2009:169-178.

[5] Kamakshi P, Babu A V. Preserving privacy and sharing the data in distributed environment using cryptographic technique on perturbed data[J]. Journal of Computing, 2010, 2(4):115-119.

[6] Vaidya J, Clifton C W, Zhu Y M. Privacy preserving data mining[M]. Purdue:Springer, 2006.

[7] Vaidya J, Clifton C. Privacy-preserving K-means clustering over vertically partitioned data[C]∥Proc of the SIGKDD’

03, 2003:24-27.

[8] Kumar K A, Rangan C P. Privacy preserving DBSCAN algorithm for clustering [J].Advanced Data Mining and Applications, 2007, 4632:57-68.

[9] Gentry C. Fully homomorphic encryption using ideal lattices[C]∥Proc of Symposium on the Theory of Computing (STOC), 2009:169-178.

[10] Halkidi M, Vazirgiannis M, Batistakis Y. Quality scheme assessment in the clustering process[C]∥Proc of PKDD Conference, 2000:265-276.

附中文參考文獻(xiàn):

[1] 周水庚,李豐,陶宇飛,等. 面向數(shù)據(jù)庫(kù)應(yīng)用的隱私保護(hù)研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào),2009, 32(5):847-860.

[2] 韓家煒．?dāng)?shù)據(jù)挖掘概念與技術(shù)[M]．北京:機(jī)械工業(yè)出版社,2001.

[3] 崇志宏,倪巍偉,劉騰騰,等. 一種面向聚類的隱私保護(hù)數(shù)據(jù)發(fā)布方法[J]. 計(jì)算機(jī)研究與發(fā)展,2010,47(12):2083-2089.