PDF《第27 卷第 9 期》

(4)for δ(Ni )中每个节点 Nj 发送来的最大频繁项集 MFIj do (5) for MFIi 中每个项集 i do (6) for MFIj 中每个项集 j do (7) if i炒j then (8) MFIi = MFIi \ i;

(9) if j炒i then (10) MFIj =MFIj \ j;

(11) MFIi = MFIi ∪MFIj ;

(12) if MFIi 发生了变化 then (13) goto (2);

(14)else 节点 Ni 进入终止状态;

2畅3动态网络环境下算法的调整 由于 P2P 网络是动态变化的,本节分如下三种情况对算 法2进行调整. 1)节点失效 若一个节点 Nj 离开网络,其邻居节点 δ(Nj ) 将会发现这 一变化;

同样,若某一条边出现故障,则与该边相连的两个节点 将检测到这一变化. 具体处理步骤如下:a)若Ni 与某节点 Nj 之间相连的链路需要拆除,则这两者之间的邻居关系就不存在 了,Ni 需要把 Nj 从δ(Ni )中删除,Nj 也把 Ni 从δ(Nj )中删除;

b)若某节点 Nj 离开网络时,其直接邻居节点 Ni 通过查看 δ (Ni )发现;

c)若节点 Nj ∈δ(Ni )离开网络,则Nj 的邻居节点 δ (Nj )成为 Ni 新的邻居节点,并把各自的局部最大频繁项集发 给节点 Ni . 2)增加节点 若网络中增加了一个节点 Nj ,其处理过程如下:a)Nj 内的 数据执行算法

1 得到局部最大频繁项集 MFIj ;

b)按照算法

2 执行以下的流程. 3)节点数据发生变化 当网络中某个节点 Ni 的数据发生变化时,其处理过程如 下:a)若Ni 处于非终止状态,则不需要改变方法;

b)若Ni 处于 终止状态,则需要把 Ni 重新激活,并执行算法

1 重新计算 MFIi ;

c)若Ni 的邻居节点处于终止状态,则需要激活并且按照 增加节点的过程进行相应的处理.

3 性能评测 3畅1模拟器 本文使用了 Internet 拓扑生成器 BRITE(www. cs. bu. edu/ brite)来模拟产生 P2P 网络结构,BRITE 可生成图来代表网络 拓扑结构,图中边的权重代表通信延时. 本文使用 BRITE 中 扁平层自治系统(autonomous system,AS)及Waxman 模型来模 拟P2P 网络. 在模拟网络中,两个节点 u 和v互连的概率由式 (1)计算: P(u,v) = α e - d(u,v) / β L (1) 其中:0 <

α<

1,0 <

β <

1;

d(u,v)表示连接节点 u 和v的边的权 重;

L 表示网络内两个节点间的最大距离. 在网络拓扑结构的构造阶段使用了增量式的 Waxman 模型,每个步骤中所产生的新节点按照式(1)与两个已存在的节 点相连,其中 α= 0. 15,β = 0. 2,用该模型所产生的网络的半径与 网络中的节点数量满足对数关系. BRITE 中其他参数的设置 为HS =

1 000,LS = 100,这两个参数的含义是网络平面的大小;

最大带宽和最小带宽分别为 maxBW =

1 024,minBW = 10. 本文所使用的数据是 T10I4D100K,该数据集可由 FIMI 资 源库(http:/ / fimi. cs. helsinki. fi)下载. 数据集有

870 个项目,

100 000 条事务,每条事务的平均长度为 11. 为检验算法性 能,把数据平均分布于 P2P 网络的节点中. 3畅2准确率验证 本文把 P2PMaxSet 挖掘得到的最大频繁项集与集中挖掘 所得到的结果进行比较,从而来考察算法的准确率,其结果如 图1所示. 这一实验使用了两个参数 α和β.其中,α表示在 ・

1 9

4 3 ・ 第9期邓忠军,等:P2P 网络中最大频繁项集挖掘算法研究 集中挖掘时是最大频繁项集,而在 P2PMaxSet 的结果中也是最 大频繁项集的百分比;

β 表示在 P2PMaxSet 的结果中是最大频 繁项集,而在集中挖掘时也是最大频繁项集的百分比. 由图

1 可以看出,参数 α一直保持着较高的百分比. 也就 是说,在集中式挖掘下被认为是最大频繁项集,在P2PMaxSet 挖掘时也往往被认为是最大频繁项集. 而β参数随节点数量 的增加有所下降. 也就是说,随着网络中节点数量的增加,在P2PMaxSet 的结果中是最大频繁项集,而在集中挖掘时也是最 大频繁项集的百分比有所下降. 3畅3通信效率验证 本文分别在含有不同节点数量的情况下进行实验,比较了 本文提出的算法 P2PMaxSet 与文献[5]提出的 Majority唱Rule 的 通信总量(图2)和平均通信量(图3). 通过图