·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卷