第2期 吉根林，等：一种分布式隐私保护的密度聚类算法 ·139· 根据安全协议在第三方TTP上进行安全聚类，完成 2分布式隐私保护聚类算法DBPPDC 后将这些对象返回到相应站点，重新标识.此时各站 21相关协议 点所有对象聚类完毕.这就对DBDC进行改进达到 协议：A站点有私有输入(X1,X2,Xn),B站 隐私保护目的的DBPPDC算法思想.算法描述如算 点有私有输入(ya1,2,；Yn,要求判断 法2所示. {(X1-a12+(X2-ya22+…+(Xn-an2}≤ 算法2分布式隐私保护聚类算法DBPPDC epS是否成立.但是，A站点不能知道(a1,Y2, 输入：局部数据集DB1,DB2,,DBm,pS, Yn的值，B站点也不能知道(X1,X2,,Xm)的值 MinPts 为了能够进行安全计算，需要1个第三方站点TTP 输出：聚类结果 具体步骤如下： 步骤： )A站点的工作 master site P: ①产生一个加密向量rand=(mnd,mnd, rand rand Vector(); mndn),发送rand给站点B. /*随机产生加密向量*/ ②i计算(T1,T2,,Tn）={(X+and), broadcast(rand)to slave site P,:(l≤i≤p- 1)/*向从站点广播加密向量*/ (Xa+mnd),,(Xn+mndn)},发送(T1,I2 slave site P:1≤i≤m-l) Ta)给TTP rand rceive(rand); 2)B站点的工作 /*接收加密向量*/ ①接收站点A发送来的rand site P,:(1≤i≤m) ②i计算(TB1,T2,,TBn)={(Ya1+and), CorePo intSet.CorePointSet.= (Yg2+and),(Yam+mndn)},发送(Ta1,TB2, DBSCAN (DB,Eps,M inPts);/*执行DBSCAN得 ,IBn给TTP 到s个核心点集*/ 3)TTP的工作 for j=1 to s do ①计算es=f(T1-TIa1+(Ta-T2尸+…+ for each d ECorePointSet,do (Tu-Toa) if(fs|k∈CorePo intSet,ds≠d,d∈Nps ②判断es≤epS是否成立，广播给A、B. (d)'！=Nulw 上述协议是基于两方安全计算的，在多方情况 /*若某核心点集中的某一核心对象d处于 下，只需要将A的加密向量广播给从站点，从站点做 另一核心对象d的E印s领域内*/ B方工作后，发送给TTP就实现了多方安全计算 Add(fd.Eps+max{dist(d.d)to Spe- 22算法思想与描述 cial CorePo intSet,: DBDC分为2步：局部聚类和全局聚类.局部聚 /*添加核心对象4到该类的特殊核心点 类可在各站点独立完成，而全局聚类需要各站点中 集中*/ 的特殊核心点聚集到一起进行聚类，这样会泄露各 Delete(d,{d})fiom CorePointSet,;/*删除 站点特殊核心点的私有信息.通过安全协议，可使各 核心点d,及其Eps领域内的核心点fd}*/ 站点在不泄露特殊核心点私有信息的前提下，在第 Special_CorePointSet merge Special_Core- 三方TTP完成全局聚类；得到全局模型.DBDC在得 PointSet,:Special_CorePointSet.;/*合并特殊 到全局模型后，广播给各站点，使各站点根据全局模 核心点集*/ 型进行聚类.但全局模型包含各站点的相关信息，广 Special_CorePointSet'=encrypt(Special_Core- 播后每个站点都将或多或少知道其余各站点的信 PointSeti rand);/*加密特殊核心点*/ 息.本文考虑的方法是将全局模型按站点进行分解， sent(Special_CorePointSet,)oTTP;/*发送 分解后的部分全局模型发送给相应站点，各站点根 伪装后的特殊核心点集给TTP方*/ 据部分全局模型进行聚类，但得到的聚类结果是不 receive(Special_CorePo intSet,;/*接收TTP 完整的，聚类后的一些噪音和未被分类的对象很可 方更新后的特殊核心点集*/ 能在完整的全局模型中能归于某一类.本文的解决 Special CorePointSet decryption Special 方法是将这些对象和其他站点的部分全局模型再次 CorePo intSet,rand;/*对特殊核心点集解密*/ 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net2 分布式隐私保护聚类算法 DBPPDC 2. 1 相关协议 协议 :A站点有私有输入 (XA1 , XA2 , …, XAn ) , B 站 点 有 私 有 输 入 ( YB1 , YB2 , …, YB n ) , 要 求 判 断 { (XA1 - YB1 ) 2 + (XA2 - YB2 ) 2 + … + (XAn - YB n ) 2 } ≤ ep s 2是否成立. 但是, A 站点不能知道 ( YB1 , YB2 , …, YB n )的值, B 站点也不能知道 (XA1 , XA2 , …, XAn )的值. 为了能够进行安全计算,需要 1个第三方站点 TTP. 具体步骤如下 : 1) A站点的工作 ①产生一个加密向量 rand = ( rand1 , rand2 , …, randn ) ,发送 rand给站点 B. ②计算 ( TA1 , TA2 , …, TAn ) = { ( XA1 + rand1 ) , (XA2 + rand2 ) , …, ( XAn + randn ) }, 发送 ( TA1 , TA2 , …, TAn )给 TTP. 2) B 站点的工作 ①接收站点 A发送来的 rand. ②计算 ( TB 1 , TB2 , …, TB n ) = { ( YB1 + rand1 ) , ( YB 2 + rand2 ) , …, ( YB n + randn ) },发送 ( TB 1 , TB 2 , …, TB n )给 TTP. 3) TTP的工作 ①计算 res = { ( TA1 - TB1 ) 2 + (TA2 - TB2 ) 2 +… + (TAn - TB n ) 2 }. ②判断 res≤ep s 2是否成立 ,广播给 A、B. 上述协议是基于两方安全计算的,在多方情况 下,只需要将 A的加密向量广播给从站点,从站点做 B 方工作后,发送给 TTP就实现了多方安全计算. 2. 2 算法思想与描述 DBDC分为 2步 :局部聚类和全局聚类. 局部聚 类可在各站点独立完成 ,而全局聚类需要各站点中 的特殊核心点聚集到一起进行聚类 ,这样会泄露各 站点特殊核心点的私有信息. 通过安全协议 ,可使各 站点在不泄露特殊核心点私有信息的前提下 ,在第 三方 TTP完成全局聚类 ;得到全局模型. DBDC在得 到全局模型后 ,广播给各站点 ,使各站点根据全局模 型进行聚类. 但全局模型包含各站点的相关信息 ,广 播后每个站点都将或多或少知道其余各站点的信 息. 本文考虑的方法是将全局模型按站点进行分解 , 分解后的部分全局模型发送给相应站点 ,各站点根 据部分全局模型进行聚类 ,但得到的聚类结果是不 完整的 ,聚类后的一些噪音和未被分类的对象很可 能在完整的全局模型中能归于某一类. 本文的解决 方法是将这些对象和其他站点的部分全局模型再次 根据安全协议在第三方 TTP上进行安全聚类 ,完成 后将这些对象返回到相应站点 ,重新标识. 此时各站 点所有对象聚类完毕. 这就对 DBDC进行改进达到 隐私保护目的的 DBPPDC算法思想. 算法描述如算 法 2所示. 算法 2 分布式隐私保护聚类算法 DBPPDC 输入 :局部数据集 { DB1 , DB2 , …, DBm }, Ep s, M inPts. 输出 :聚类结果. 步骤 : master site Pm : rand = rand Vector(); / 3 随机产生加密向量 3 / broadcast ( rand ) to slave site Pi; ( 1≤i≤p - 1) / 3 向从站点广播加密向量 3 / slave site Pi: (1≤i≤m - 1) rand = rceive ( rand) ; /3 接收加密向量 3 / site Pi: (1≤i≤m ) { CorePointSeti1 , …, CorePointSetis } = DBSCAN (DBi , Ep s, M inPts) ; /3 执行 DBSCAN得 到 s个核心点集 3 / for j = 1 to s do for each dA ∈CorePointSetij do if ({ dB | dB ∈CorePointSetij , dB ≠dA , dA ∈NEp s ( dA ) } ! =Null) / 3 若某核心点集中的某一核心对象 dB 处于 另一核心对象 dA 的 Ep s领域内 3 / {Add ({ dA , Ep s +max{ dist( dA , dB ) } } ) to Spe2 cial_CorePointSetij; / 3 添加核心对象 dA 到该类的特殊核心点 集中 3 / Delete ( dA , { dB } ) from CorePointSetij}; / 3 删除 核心点 dA ,及其 Ep s领域内的核心点 { dB } 3 / Special _ CorePointSeti = merge ( Special _ Core2 PointSeti1 , …, Special_CorePointSetis ) ; / 3 合并特殊 核心点集 3 / Special_CorePointSet′i = encryp t ( Special_Core2 PointSeti, rand) ; /3 加密特殊核心点 3 / sent(Special_CorePointSet′i ) to TTP ; /3 发送 伪装后的特殊核心点集给 TTP方 3 / receive ( Special_CorePointSet′i ) ; / 3 接收 TTP 方更新后的特殊核心点集 3 / Special _ CorePointSeti = decryp tion ( Special _ CorePointSet′i , rand) ; / 3 对特殊核心点集解密 3 / 第 2期 吉根林 ,等 :一种分布式隐私保护的密度聚类算法 ·139·