第4卷第2期 智能系统学报 Vol 4 Ng 2 2009年4月 CAA I Transactions on Intelligent Systems Apr 2009 一种分布式隐私保护的密度聚类算法 吉根林，姚瑶 (南京师范大学数学与计算机科学学院，江苏南京210097) 摘要：对基于密度的分布式聚类算法DBDC进行改进，提出了一种基于密度的分布式隐私保护聚类算法DBPPDC 在由局部模型确定全局模型时，通过相关安全协议有效地保护了局部模型，同时不影响全局聚类在利用全局模型 更新局部模型时，通过改进算法、应用安全协议保护隐私信息最终使各站点分布的数据能够安全聚类.理论分析和 实验结果表明，DBPPDC算法是有效的. 关键词：隐私保护：分布式聚类：DBDC,DBPPDC 中图分类号：TP3111文献标识码：A文章编号：1673-4785(2009)02-0137-05 Density-ba sed privacy preserving distr ibuted clustering a lgor ithm JI Gen-lin,YAO Yao (School ofMathematics and Computer Science,Nanjing Nomal University,Nanjing 210097,China Abstract:A density-based privacy preserving distributed clustering algorithm (DBPPDC)was proposed follwing the mprovements to the density-based distributed clustering DBDC algorithm.When a glbal model is detem ined from a bcal model,(DBPPDC)effectively protects the bcal model without obstructing global clustering On the contrary,when the bcal model is updated with the glbalmodel,DBPPDC makes all the data in local sites cluster safely by mproving the previous algorithm and appling a secure protocol Expermental results showed that DBPP- DC is effective and efficient Keywords:privacy preserving distributed clustering DBDC;DBPPDC 分布式聚类算法1在聚类过程中将本站点有 划分的分布式数据库环境下，对基于密度的分布式 关真实数据传送给其他站点，从而导致信息泄露.在 聚类算法I(density based distributed clustering,DB- 实际分布式聚类应用中，有时候需要保护本站点的 DC)进行改进，提出了一种基于密度的分布式隐私 真实信息不被传送给其他站点，即需要进行隐私保 保护聚类算法(density based privacy preserving dis- 护，为此，需要研究基于隐私保护的分布式聚类算 tributed clustering,DBPPDC).在由局部模型确定全 法.聚类过程中的隐私保护方法可大致分为数据扰 局模型时，通过相关安全协议有效地保护局部模型， 乱和安全多方计算2种.基于数据扰乱的隐私保护 同时不影响全局聚类.在利用全局模型更新局部模 聚类思想是通过转换数据使得真实的敏感数据不为 型时，通过改进算法、应用安全协议保护隐私信息， 人知，然后再进行聚类分析.而基于安全多方计算的 最终使各站点分布的数据能够安全聚类， 隐私保护聚类主要通过构造安全多方协议，使得一 组站点在仅仅拥有自己私有信息的情况下能最终获 1问题描述 知全局聚类信息.后者主要应用于分布式聚类分析. 11相关定义 针对水平划分的分布式数据库，文献[56提出 定义1全局数据集.分布式系统中有m个站 基于隐私保护的分布式聚类算法，本文同样在水平 点，各站点相应的d维局部数据集分别为DB, DB2,DBm,各局部数据集的大小分别为N, 收稿日期：2008-12-16 基金项目：国家自然科学基金资助项目(40771163). 通信作者：姚瑶.Emai让cindy yaoyao@homail oom N2,,Nm,DB=UDB称为全局数据集 1a1 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net
第 4卷第 2期 智 能 系 统 学 报 Vol. 4 №. 2 2009年 4月 CAA I Transactions on Intelligent System s Ap r. 2009 一种分布式隐私保护的密度聚类算法 吉根林 ,姚 瑶 (南京师范大学 数学与计算机科学学院 ,江苏 南京 210097) 摘 要 :对基于密度的分布式聚类算法 DBDC进行改进 ,提出了一种基于密度的分布式隐私保护聚类算法 DBPPDC. 在由局部模型确定全局模型时 ,通过相关安全协议有效地保护了局部模型 ,同时不影响全局聚类. 在利用全局模型 更新局部模型时 ,通过改进算法、应用安全协议保护隐私信息 ,最终使各站点分布的数据能够安全聚类. 理论分析和 实验结果表明 ,DBPPDC算法是有效的. 关键词 :隐私保护 ;分布式聚类 ; DBDC; DBPPDC 中图分类号 : TP311. 1 文献标识码 : A 文章编号 : 167324785 (2009) 0220137205 Density2based pr ivacy preserving distr ibuted cluster ing algor ithm J I Gen2lin, YAO Yao ( School ofMathematics and Computer Science, Nanjing Normal University, Nanjing 210097, China ) Abstract:A density2based p rivacy p reserving distributed clustering algorithm (DBPPDC) was p roposed following the imp rovements to the density2based distributed clustering DBDC algorithm. W hen a global model is determ ined from a local model, (DBPPDC) effectively p rotects the local model without obstructing global clustering. On the contrary, when the local model is updated with the globalmodel, DBPPDC makes all the data in local sites cluster safely by imp roving the p revious algorithm and app ling a secure p rotocol. Experimental results showed that DBPP2 DC is effective and efficient. Keywords: p rivacy p reserving; distributed clustering; DBDC; DBPPDC 收稿日期 : 2008212216. 基金项目 :国家自然科学基金资助项目 (40771163). 通信作者 :姚 瑶. E2mail: cindy_yaoyao@hotmail. com. 分布式聚类算法 [ 124 ]在聚类过程中将本站点有 关真实数据传送给其他站点 ,从而导致信息泄露. 在 实际分布式聚类应用中 ,有时候需要保护本站点的 真实信息不被传送给其他站点 ,即需要进行隐私保 护 ,为此 ,需要研究基于隐私保护的分布式聚类算 法. 聚类过程中的隐私保护方法可大致分为数据扰 乱和安全多方计算 2种. 基于数据扰乱的隐私保护 聚类思想是通过转换数据使得真实的敏感数据不为 人知 ,然后再进行聚类分析. 而基于安全多方计算的 隐私保护聚类主要通过构造安全多方协议 ,使得一 组站点在仅仅拥有自己私有信息的情况下能最终获 知全局聚类信息. 后者主要应用于分布式聚类分析. 针对水平划分的分布式数据库 ,文献 [ 526 ]提出 基于隐私保护的分布式聚类算法 ,本文同样在水平 划分的分布式数据库环境下 ,对基于密度的分布式 聚类算法 [ 7 ] ( density based distributed clustering, DB2 DC)进行改进 ,提出了一种基于密度的分布式隐私 保护聚类算法 ( density based p rivacy p reserving dis2 tributed clustering, DBPPDC). 在由局部模型确定全 局模型时 ,通过相关安全协议有效地保护局部模型 , 同时不影响全局聚类. 在利用全局模型更新局部模 型时 ,通过改进算法、应用安全协议保护隐私信息 , 最终使各站点分布的数据能够安全聚类. 1 问题描述 1. 1 相关定义 定义 1 全局数据集. 分布式系统中有 m 个站 点 ,各站点相应的 d 维局部数据集分别为 { DB1 , DB2 , …, DBm }, 各局部数据集的大小分别为 N1 , N2 , …, Nm , DB = ∪ m i = 1 DBi称为全局数据集
·138· 智能系统学报 第4卷 定义2核心点.给定邻域半径印s和最小密 Special CorePo intSet,: 度M inPts若对象q的Eps邻域Nps(g到包含的对象 /*添加核心对象d到该类的特殊核心点集 个数Wps(g|MinPts则称g为核心点.在上述条 中*/ 件下对全局数据集执行DB SCAN聚类，可划分为J Delete(d,fd})from CorePointSet,:/*删除 个聚簇w1,,w,各类的核心点集分别为Coe- 核心点d,及其E印s领域内的核心点{山}*/ PointSet,CorePointSet,CorePointSet. 定义3特殊核心点集.类的特殊核心点集 Special_CorePointSet merge Special_Core- Special_CorePointSet,是该类核心点集CorePo intSet PointSet,,Special_CorePointSet,;/*合并特殊 的一个子集(1≤≤，满足以下条件： 核心点集*/ 1)pecial CorePo intSet CorePointSet: send Special CorePo intSet)to master site P: 2)廿d,d,∈Special_CorePointSet,.若d≠d.则 )/*向主站点传送局部代表信息*/ d,年N甲s(d: receive(Global CorePointSet); 3)dk∈CorePo intSet,3d∈Special CorePoint- /*接收全局模型*/ Set且d∈Npsd relabel(DB,.Gbbal CorePo intSet; 12分布式聚类算法DBDC /*根据全局特殊核心点重新标识所有对象*/ 分布式聚类算法DBDC是基于密度的聚类算法 master site P: (DB SCAN)在分布式环境下的扩展.该算法设分布 CorePointSet,CorePo intSet.,=DBSCAN 式系统中有m个站点，从中任意选定一个站点P (DBm,Eps,M inPts);/*执行DBSCAN得到s个 为主站点，其余m·1个站点为从站点.它按2步进 核心点集*/ 行聚类：局部聚类和全局聚类.首先，各站点在给定 for j=1 to s do 邻域半径Eps和最小密度M inPts的前提下分别执 for each d ECorePointSet,do 行DBSCAN进行局部聚类，得到局部核心点集；然 if({d|k∈CorePo in tSet,k≠d,dh∈ 后从中选择能够反映数据分布特征的特殊核心点集 Nps(d)}！=NulW 作为局部代表对象，同时将这些特殊核心点及其邻 /*若某核心点集中的某一核心对象处于 域半径发送到主站点；主站点对所有的特殊核心点 另一核心对象d,的E印s领域内*/ 再次执行DBSCAN聚类得到全局聚类结果，并将其 (Add(d.Eps+max{dist(d.ds))to Spe- 广播到各从站点，各站点根据全局信息重新标识局 cial_CorePointSet:/*添加核心对象d到特殊核心 部数据集.算法描述如算法1所示 点集中*/ 算法1分布式聚类算法DBDC Delete(d,fd})from CorePointSet:/*删除 输入：局部数据集{DB1,DB2,DBm,pS, 核心点d,及其E即s领域内的核心点/山}*/ MinPts 输出：聚类结果 receive(Special_CorePointSet).;/*主站点接收 步骤： 从站点的代表信息，得到全局代表信息*/ slave site P:(im-1) Special_CorePointSet=merge(Special_CorePoint- CorePointSet,.CorePointSet.= Set,,Special_CorePointSet): DBSCAN (DB,Ens,M inPts/;/*执行DBSCAN得 /*合并各站点的特殊核心点集*/ 到s个核心点集*/ Glbal CorePointSet =DBSCAN Special Core for j=1 to s do PointSet,2Eps,MinPts); for each d ECorePointSet,do /*主站点对所有特殊核心点再次执行 ifr{d|4∈CorePointSet,,d4≠d DBSCAN得到全局模型*/ 4∈Nps(d)}!=Nul山/*若某核心点集 broadeast(Glbal CorePointSet;/*向从站点 中的某一核心对象处于另一 广播全局模型*/ 核心对象d,的E印s领域内*/ relabel (DB,Global_CorePointSet;/*根据全 Add (d.Eps +max{dist(d.d))to 局模型重新标识所有对象*/ 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
定义 2 核心点. 给定邻域半径 Ep s和最小密 度 M inPts,若对象 q的 Ep s邻域 NEp s ( q)包含的对象 个数 |NEp s ( q) | ≥M inPts,则称 q为核心点. 在上述条 件下对全局数据集执行 DBSCAN 聚类 ,可划分为 s 个聚簇 w1 , …, ws , 各类的核心点集分别为 Core2 PointSet1 , CorePointSet2 , …, CorePointSets . 定义 3 特殊核心点集. 类 i的特殊核心点集 Special_CorePointSeti 是该类核心点集 CorePointSeti 的一个子集 (1≤i≤s) ,满足以下条件 : 1) pecial_CorePointSeti Α CorePointSeti ; 2) Π dh , dj∈Special_CorePointSeti ,若 dh ≠dj ,则 dh | NEp s ( dj ) ; 3) dB ∈CorePointSeti , ϖ dA ∈Special_CorePoint2 Seti 且 dB ∈NEp s ( dA ). 1. 2 分布式聚类算法 DBDC 分布式聚类算法 DBDC是基于密度的聚类算法 (DBSCAN)在分布式环境下的扩展. 该算法设分布 式系统中有 m 个站点 ,从中任意选定一个站点 Pm 为主站点 ,其余 m - 1个站点为从站点. 它按 2步进 行聚类 :局部聚类和全局聚类. 首先 ,各站点在给定 邻域半径 Ep s和最小密度 M inPts的前提下分别执 行 DBSCAN进行局部聚类 ,得到局部核心点集;然 后从中选择能够反映数据分布特征的特殊核心点集 作为局部代表对象 ,同时 ,将这些特殊核心点及其邻 域半径发送到主站点;主站点对所有的特殊核心点 再次执行 DBSCAN聚类得到全局聚类结果 ,并将其 广播到各从站点 ,各站点根据全局信息重新标识局 部数据集. 算法描述如算法 1所示. 算法 1 分布式聚类算法 DBDC 输入 :局部数据集 { DB1 , DB2 , …, DBm }, Ep s, M inPts. 输出 :聚类结果. 步骤 : slave site Pi: (1≤i≤m - 1) { 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 , dB ∈NEp s ( dA ) } ! =Null) / 3 若某核心点集 中的某一核心对象 dB 处于另一 核心对象 dA 的 Ep s领域内 3 / { Add ({ dA , Ep s + max{ dist( dA , dB ) } } ) to Special_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 / send (Special_CorePointSeti ) to master site Pm ; / 3 向主站点传送局部代表信息 3 / receive ( Global_CorePointSet) ; / 3 接收全局模型 3 / relabel(DBi , Global_CorePointSet) ; / 3 根据全局特殊核心点重新标识所有对象 3 / master site Pm : { CorePointSetm 1 , …, CorePointSetm s } = DBSCAN (DBm , Ep s, M inPts) ; /3 执行 DBSCAN 得到 s个 核心点集 3 / for j = 1 to s do for each dA ∈CorePointSetm j do if ({ dB | dB ∈ CorePointSetm j , dB ≠ dA , dB ∈ NEp s ( dA ) } ! =Null) / 3 若某核心点集中的某一核心对象 dB 处于 另一核心对象 dA 的 Ep s领域内 3 / {Add ({ dA , Ep s +max{ dist( dA , dB ) } } ) to Spe2 cial_CorePointSetm j; / 3 添加核心对象 dA 到特殊核心 点集中 3 / Delete ( dA , { dB } ) from CorePointSetm j; / 3 删除 核心点 dA ,及其 Ep s领域内的核心点 { dB } 3 / } receive (Special_CorePointSeti ) ; / 3 主站点接收 从站点 i的代表信息 ,得到全局代表信息 3 / Special_CorePointSet =merge (Special_CorePoint2 Set1 , …, Special_CorePointSetp ) ; / 3 合并各站点的特殊核心点集 3 / Global_CorePointSet = DBSCAN (Special_Core2 PointSet, 2Ep s, M inPts) ; / 3 主站点对所有特殊核心点再次执行 DBSCAN得到全局模型 3 / broadcast ( Global_CorePointSet) ; / 3 向从站点 广播全局模型 3 / relabel (DBm , Global_CorePointSet) ; / 3 根据全 局模型重新标识所有对象 3 / ·138· 智 能 系 统 学 报 第 4卷
第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.net
2 分布式隐私保护聚类算法 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·
·140 智能系统学报 第4卷 relable(DB,Special_CorePo intSet;/*根据特 于非TTP的站点. 殊核心点集重新对DB,聚类* 表1实验数据集 noie,=getnoise(DB,;/*找出聚类后DB,中 Table 1 Experi ent data sets 的噪音和未分类的对象oise,*/ 数据集 对象个数属性维数 noise=encrypt(noise,,rand): Iris 150 4 /*加密no ise,*/ KDD-Cup-99 800 800 34 sent(noise o TTP: ①DD-Cup998000 8000 34 /*发送no ise给TTP*/ 31聚类精度 receive (noise: Modha和Spangle利用了数据的分类信息来 decryption (noise.rand); 评价聚类结果的好坏，即当数据有分类信息时，可认 site TTP: 为该分类信息在一定程度上表达了数据的一些内部 rceive (Special_CorePointSet): 分布特性.如果该分类信息没被聚类算法利用，则可 /*接收各站点加密后的特殊核心点集*/ 以用它来评价聚类性能，其度量标准Micop rec ision Special CorePointSet'=merge Special_Core- 定义如下： PointSet,…,Special_CorePointSet;/*合并特殊 Microprecision =1∑a 核心点集*/ n, Global_CorePointSet =DBSCAN Special_Core- 式中：n为数据集样本总数，k为聚类的类数，a,为 PointSet',2Eps,MinPts); 聚类的类与已知数据集类别对应后，类中被正确 /*主站点对所有特殊核心点再次执行 归为相应类别的样本个数.M icroprecision的值越 DBSCAN得到全局模型*/ 大，表示在该数据集上聚类效果越好.这种度量方法 update(Special_CorePointSet): 适合聚类时产生固定类数的算法，如Kmeans等，因 ?*根据全局模型更新各站点的特殊核心点集信息*/ 此实验中采用该标准对各算法的精度进行比较，实 验结果取10次实验的平均值，聚类精度如图1所 sent(Special_CorePointSet to site P,: /*发送更新后的特殊核心点集信息给相应站点*/ 示.实验结果表明DBPPDC与DBDC在聚类精度上 rceive (noise); 是相当的，经过隐私保护进行的分布式聚类并没有 /*接收各站点加密后的噪音和未分类的对象*/ 改变聚类的结果.由于算法DBPPDC与DBDC在全 relabel(noise,Gbbal_CorePo intSet);/*根据 局聚类时采用2E即s进行邻域查询，会导致了一些 全局特殊核心点集重新对noise,聚类*/ 类间的错误合并，所以精度比DBSCAN稍低， 100 sent((noise,)to site p:/*发送更新后的 DBSCAN DBDC DBPPDC noise',给相应站点P,*/ 3实验结果与性能分析 为了研究算法DBPPDC的性能，使用3台微机 器 构成100MB的局域网，其中一台作为第三方TTP 微机配置为Intel Pentium IV293GHz/5l2MB,开 Iris KDD 800 KDD 8000 发环境为JBuilder2006 Enterprise利用Java实现了 数据集 DBPPDC、DBDC和DB SCAN.实验数据源如表I所 图1聚类算法精度比较 示，其中，is1是植物样本数据库，①D-CUP-99800 和DD-CUP-998000是从①DCUP-99中分别随 Fig 1 Comparison of the accuracy of clusters 32聚类效率 机抽取800个记录和8000个记录构成的数据库， 算法的执行时间如图2所示.其结果取10次实 实验中选择了其中的34个连续值属性维.集中式聚 验平均值.分布式隐私保护聚类算法DBPPDC和分 类算法DB SCAN运行在一台PC机上，采用表1所 布式聚类算法DBDC时间代价分为2部分：1)站点 列测试数据集.分布式聚类算法DBPPDC、DBDC运 间通信代价，2)站点内计算代价.从图2可以看出， 行在处于同一局域网的3台P℃机上，表1所示的每 当测试数据集较小时（如：is),分布式算法DBPP- 个数据集被随机分成2个不相交的子数据集，存放 1994-2009 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net
relable (DB i , Special_CorePointSeti ) ; / 3 根据特 殊核心点集重新对 DB i 聚类 3 noisei = getnoise (DBi ) ; / 3 找出聚类后 DBi中 的噪音和未分类的对象 noisei 3 / noise′i = encryp t( noisei , rand) ; / 3 加密 noisei 3 / sent( noise′i ) to TTP; / 3 发送 noisei给 TTP 3 / receive ( noise′i ) ; decryp tion ( noise′i , rand) ; site TTP: rceive (Special_CorePointSet′i ) ; / 3 接收各站点加密后的特殊核心点集 3 / Special _CorePointSet′= merge ( Special _ Core2 PointSet′1 , …, Special_CorePointSet′p ) ; / 3 合并特殊 核心点集 3 / Global_CorePointSet = DBSCAN ( Special_Core2 PointSet′, 2Ep s, M inPts) ; / 3 主站点对所有特殊核心点再次执行 DBSCAN得到全局模型 3 / update (Special_CorePointSet′i ) ; / 3 根据全局模型更新各站点的特殊核心点集信息 3 / sent(Special_CorePointSet′i ) to site Pi; / 3 发送更新后的特殊核心点集信息给相应站点 3 / rceive ( noise′i ) ; / 3 接收各站点加密后的噪音和未分类的对象 3 / relabel ( noise′i , Global_CorePointSet) ; /3 根据 全局特殊核心点集重新对 noise′i 聚类 3 / sent ( ( noise′i ) to site Pi; / 3 发送更新后的 noise’′i 给相应站点 Pi 3 / 3 实验结果与性能分析 为了研究算法 DBPPDC的性能 ,使用 3台微机 构成 100 MB的局域网 ,其中一台作为第三方 TTP. 微机配置为 Intel Pentium Ⅳ 2. 93 GHz/512 MB,开 发环境为 JBuilder 2006 Enterp rise. 利用 Java实现了 DBPPDC、DBDC和 DBSCAN. 实验数据源如表 1所 示 ,其中 , Iris [ 8 ]是植物样本数据库 , KDD2CUP299 800 和 KDD2CUP299 8000是从 KDD2CUP299 [ 9 ]中分别随 机抽取 800个记录和 8 000个记录构成的数据库 , 实验中选择了其中的 34个连续值属性维. 集中式聚 类算法 DBSCAN运行在一台 PC机上 ,采用表 1所 列测试数据集. 分布式聚类算法 DBPPDC、DBDC运 行在处于同一局域网的 3台 PC机上 ,表 1所示的每 个数据集被随机分成 2个不相交的子数据集 ,存放 于非 TTP的站点. 表 1 实验数据集 Table 1 Exper im en t da ta sets 数据集 对象个数 属性维数 Iris 150 4 KDD2Cup299 800 800 34 KDD2Cup299 8000 8 000 34 3. 1 聚类精度 Modha和 Spangler [ 10 ]利用了数据的分类信息来 评价聚类结果的好坏 ,即当数据有分类信息时 ,可认 为该分类信息在一定程度上表达了数据的一些内部 分布特性. 如果该分类信息没被聚类算法利用 ,则可 以用它来评价聚类性能 ,其度量标准 M icro2p recision 定义如下 : M icro2p recision = 1 n ∑ k i =1 αi . 式中 : n为数据集样本总数 , k为聚类的类数 ,αi 为 聚类的类 i与已知数据集类别对应后 ,类 i中被正确 归为相应类别的样本个数. M icro2p recision的值越 大 ,表示在该数据集上聚类效果越好. 这种度量方法 适合聚类时产生固定类数的算法 ,如 K2means等 ,因 此实验中采用该标准对各算法的精度进行比较 ,实 验结果取 10次实验的平均值 ,聚类精度如图 1所 示. 实验结果表明 DBPPDC与 DBDC在聚类精度上 是相当的 ,经过隐私保护进行的分布式聚类并没有 改变聚类的结果. 由于算法 DBPPDC与 DBDC在全 局聚类时采用 2 ×Ep s进行邻域查询 ,会导致了一些 类间的错误合并 ,所以精度比 DBSCAN稍低. 图 1 聚类算法精度比较 Fig. 1 Comparison of the accuracy of clusters 3. 2 聚类效率 算法的执行时间如图 2所示. 其结果取 10次实 验平均值. 分布式隐私保护聚类算法 DBPPDC和分 布式聚类算法 DBDC时间代价分为 2部分 : 1)站点 间通信代价 , 2)站点内计算代价. 从图 2可以看出 , 当测试数据集较小时 (如 : Iris) ,分布式算法 DBPP2 ·140· 智 能 系 统 学 报 第 4卷
第2期 吉根林，等：一种分布式隐私保护的密度聚类算法 141 DC与DBDC的执行时间多于集中式DB SCAN聚类 是一项非常重要的研究工作 计算时间，这是由于此时站点间的通信代价大于计 算代价.因此，当数据源较小时不宜使用分布式聚类 参考文献： 算法.但随着数据集规模不断变大（如：①D-Cup~ [1 ]KANTABUTRA S,COUCH A L.Parallel kmeans clustering 99子集1，子集2)，DBPPDC与DBDC的时间代价 algorithm on Nows[J ]NECTEC Technical Joumal,2000, 1(6):243-247. 增长速度明显低于DB SCAN.同时，由于在DBPPDC [2]PROD D H,LAWRENCE H Scalable clustering a distribu- 算法过程中运用协议，增加了第三方的通信，相比较 ted approach [C]//Proc IEEE Int'1 Conf Fuzzy Systems DBDC通信代价增加，执行时间稍长 Budapest,Hungary:ETATSUUN IS,2004:143-148 煞辑董 [3 ]JANUZAJ E,KR IEGEL H P,PFE IFLEM.Scalable density KDD 800 K DD based distributed clustering [C]//Poc the 8th Eur Conf Princ ples and Practice of Knowledge D iscovery in Databas es Paris,2004:231-244. [4李锁花，孙志挥，周晓云，基于特征向量的分布式聚类算 法[J]计算机应用，2006,26(2)：379-382 L I Suohua,SUN Zhihui,ZHOU Xiaoyun Distributed cluste- 凝 ▣DBbbDC ring algorithm based on feature vector[J].Joumal of Com- ■DBDC puter Applications,2006,26(2):379-382 D B 2 C 7/ [5]NAN A,SAYGN Y Privacy preserving clustering on hori- ×10, zontally partitioned data C]//Proc the 22nd Intemational 图2聚类算法效率比较 Conference on Data Engineering Atlanta,GA:IEEE Press, 2006:95-103 Fig 2 Comparison of the efficiency of algorithms [6 ]JAGANNATHAN G,PLLA IPA KKAMNATT K,WR IGHT 3.3安全性分析 R N.A new privacypreserving distributed k-clustering al DBDC算法分为2步：局部聚类和全局聚类.在 gorithm [C]//Proc Sixth SAM Intel ConfDataMining Be- thesda,MD,USA,2006:492-496 局部聚类过程中，各站点进行聚类确定局部模型，此 [7]JANUZAJ E,KR IEGEL H P,PFE IFLEM.DBDC:density 时各站点不进行相互通信，所以不涉及到隐私暴露 based distributed clustering[C]//Proc the 9th Int'I Conf 问题.在全局聚类过程中又可分为2步：1)根据所 Extending Database Technobgy Heraklion,Greece,2004: 有局部模型确定全局模型；2)根据全局模型更新局 88-105. [8 ]DA TASET[EB /OL ][1999-10-28 ]http://www.ics uci 部模型.这2步都需要进行站点间的通信，所以需要 edu/~m leam/databases/iris/. 保护各站点的私有信息.在确定全局模型时，通过相 [9 ]The third intemational knowledge discovery and data m ining 关安全协议有效地保护局部模型，同时不影响全局 bols competition dataset[EB/OL ][1999-10-28].htp:// 聚类.在更新局部模型时，是将全局模型按站点进行 kdd ics uci edu/databases/kddcup99/kddcup99 hmI [10 MODHA D S,SPANGLER W S Feature weighting in k- 分解，分解后的部分全局模型发送给相应站点，各站 means clustering [J]Machine Leaming.2003,52(3): 点根据部分全局模型进行聚类，也没有泄露其余站 217-223 点在全局模型的信息.聚类后的一些噪音和未被分 作者简介： 吉根林，男，1964年生，教授，博士生 类的对象与其他站点的部分全局模型再次根据协议 导师，博士，主要研究方向为数据库、数 在第三方TTP上进行安全聚类，完成后将这些对象 据挖掘、ML技术入侵检测技术.主 返回到相应站点.这样同时保护了本站点的对象和 持或参加多项国家自然科学基金项目 江苏省自然科学基金项目和江苏省高校 其余站点的部分全局模型.通过对DBDC算法各个 自然科学基金项目，主持研制的“分布式 环节的保护，保证了整个算法的安全性 数据挖掘原型系统DDM NER通过了 江苏省科技成果鉴定.发表学术论文80余篇，其中被E1 4结束语 STP收录16篇」 本文对分布式聚类算法DBDC改进，应用相关 姚瑶，女，1984年生，硕士研究 安全协议，提出了一种基于密度的分布式隐私保护 生，主要研究方向为分布式聚类。 聚类算法DBPPDC,有效保护了算法过程中的私有 信息.同时，与DBDC相比，算法DBPPDC没有降低 算法聚类精度.在数据挖掘过程中增加隐私保护技 术，使其在发现知识的同时，又保护了数据安全，这 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
导师 ,博士 ,主要研究方向为数据库、数 据挖掘、XML技术、入侵检测技术. 主 持或参加多项国家自然科学基金项目、 江苏省自然科学基金项目和江苏省高校 自然科学基金项目 ,主持研制的“分布式 数据挖掘原型系统 DDM INER”通过了 DC与 DBDC的执行时间多于集中式 DBSCAN聚类 计算时间 ,这是由于此时站点间的通信代价大于计 算代价. 因此 ,当数据源较小时不宜使用分布式聚类 算法. 但随着数据集规模不断变大 (如 : KDD2Cup2 99子集 1,子集 2) , DBPPDC与 DBDC的时间代价 增长速度明显低于 DBSCAN. 同时 ,由于在 DBPPDC 算法过程中运用协议 ,增加了第三方的通信 ,相比较 DBDC通信代价增加 ,执行时间稍长. 图 2 聚类算法效率比较 Fig. 2 Comparison of the efficiency of algorithm s 3. 3 安全性分析 DBDC算法分为 2步 :局部聚类和全局聚类. 在 局部聚类过程中 ,各站点进行聚类确定局部模型 ,此 时各站点不进行相互通信 ,所以不涉及到隐私暴露 问题. 在全局聚类过程中又可分为 2步 : 1) 根据所 有局部模型确定全局模型 ; 2)根据全局模型更新局 部模型. 这 2步都需要进行站点间的通信 ,所以需要 保护各站点的私有信息. 在确定全局模型时 ,通过相 关安全协议有效地保护局部模型 ,同时不影响全局 聚类. 在更新局部模型时 ,是将全局模型按站点进行 分解 ,分解后的部分全局模型发送给相应站点 ,各站 点根据部分全局模型进行聚类 ,也没有泄露其余站 点在全局模型的信息. 聚类后的一些噪音和未被分 类的对象与其他站点的部分全局模型再次根据协议 在第三方 TTP上进行安全聚类 ,完成后将这些对象 返回到相应站点. 这样同时保护了本站点的对象和 其余站点的部分全局模型. 通过对 DBDC算法各个 环节的保护 ,保证了整个算法的安全性. 4 结束语 本文对分布式聚类算法 DBDC改进 ,应用相关 安全协议 ,提出了一种基于密度的分布式隐私保护 聚类算法 DBPPDC,有效保护了算法过程中的私有 信息. 同时 ,与 DBDC相比 ,算法 DBPPDC没有降低 算法聚类精度. 在数据挖掘过程中增加隐私保护技 术 ,使其在发现知识的同时 ,又保护了数据安全 ,这 是一项非常重要的研究工作. 参考文献 : [ 1 ] KANTABUTRA S, COUCH A L. Parallel k2means clustering algorithm on Nows[J ]. NECTEC Technical Journal, 2000, 1 (6) : 2432247. [ 2 ] PROD IO H,LAWRENCE H. Scalable clustering: a distribu2 ted app roach [ C ] / /Proc IEEE Int’l Conf Fuzzy Systems. Budapest, Hungary: ETATS2UN IS, 2004: 1432148. [ 3 ]JANUZAJ E, KR IEGEL H P, PFEIFLEM. Scalable density based distributed clustering [ C ] / /Proc the 8 th Eur Conf Princip les and Practice of Knowledge D iscovery in Databas2 es. Paris, 2004: 2312244. [ 4 ]李锁花 ,孙志挥 ,周晓云. 基于特征向量的分布式聚类算 法 [J ]. 计算机应用 , 2006, 26 (2) : 3792382. L I Suohua, SUN Zhihui, ZHOU Xiaoyun. D istributed cluste2 ring algorithm based on feature vector[J ]. Journal of Com2 puter App lications, 2006, 26 (2) : 3792382. [ 5 ] INAN A, SAYGIN Y. Privacy p reserving clustering on hori2 zontally partitioned data [ C ] / /Proc the 22nd International Conference on Data Engineering. A tlanta, GA: IEEE Press, 2006: 952103. [ 6 ]JAGANNATHAN G, P ILLA IPAKKAMNATT K, WR IGHT R N. A new p rivacy2p reserving distributed k2clustering al2 gorithm [C ] / /Proc Sixth SIAM Intel Conf DataM ining. Be2 thesda, MD, USA, 2006: 4922496. [ 7 ]JANUZAJ E, KR IEGEL H P, PFEIFLEM. DBDC: density based distributed clustering [ C ] / /Proc the 9 th Int’l Conf Extending Database Technology. Heraklion, Greece, 2004: 882105. [ 8 ]DATASET[ EB /OL ]. [ 1999210228 ]. http: / /www. ics. uci. edu /～m learn /databases/ iris/. [ 9 ] The third international knowledge discovery and data mining tools competition dataset[ EB /OL ]. [ 1999210228 ]. http: / / kdd. ics. uci. edu /databases/kddcup99 /kddcup99. html. [ 10 ]MODHA D S, SPANGLER W S. Feature weighting in k2 means clustering [ J ]. Machine Learning, 2003, 52 ( 3 ) : 2172223. 作者简介 : 吉根林 ,男 , 1964年生 ,教授 ,博士生 江苏省科技成果鉴定. 发表学术论文 80余篇 ,其中被 E I、 ISTP收录 16篇. 姚 瑶 ,女 , 1984年生 ,硕士研究 生 ,主要研究方向为分布式聚类. 第 2期 吉根林 ,等 :一种分布式隐私保护的密度聚类算法 ·141· KDD 800 KDD 8000 2 3 寸 ×I0, □DBbbDC ■DBDC DB2C7 煞辑董 0 I 5 凝毕国国