·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.netrelable (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卷