PDF《第27 卷第 9 期》

b) 通信问题,节点间的消息传递会造成大量的通信开销. 为解决这两个问题,本文提出了一种 P2P 网络中最大频 繁项集的挖掘算法. 首先,只挖掘远少于全体频繁项集的最大 频繁项集 [8] 来解决结果过多的问题. 其次,网络节点只需与 其直接相邻的邻居节点进行数据交换,从而节省了大量网络通 信开销,解决了第二个问题. 为适应 P2P 网络的动态性,还讨 论了算法的调整策略. 实验结果表明,本文所提出的算法是快 速和有效的.

1 问题描述 1畅1最大频繁项集 设IS = {i1 , i2 ,…, im }为一组由 m 个不同的项(item)组成 的集合. 集合 X彻IS 称做项集(itemset),将含有 k 个项的项集 称为 k唱 项集. 记TDB 为事务(transaction)T 的集合,这里事务 T 是项集,且 T彻IS. 定义

1 若非空事务数据库 TDB 的总事务数为 N,TDB 中 包含项集 X 的事务数为 S,则X的支持度为 S/ N,记为 sup (X). 如果 sup(X)≥min_sup,其中 min_sup 为给定的最小支 持度阈值,则X是频繁项集. 定义

2 对项集 M,若不存在项集 X 使得 M炒X,且sup (X)≥min_sup,则频繁项集 M 是最大频繁项集. 性质

1 Apriori 性质 [1] . 频繁项集的所有非空子集也是 频繁的;

非频繁项集的所有超集也是非频繁的. 第27 卷第

9 期2010 年9月计算机应用研究Application Research of Computers Vol.

27 No.

9 Sep.2010 1畅2P2P 网络 令Ni (1≤i≤n) 为P2P 网络中的节点,Ni 上的数据 Xi 彻X,称做 Ni 上的局部数据;

其中,X 为整个 P2P 网络中所有数据 的集合,称做全局数据. 局部数据 Xi (1≤i≤n)与整个 P2P 网 络上的全局数据 X 满足如下两个条件:a)X1 ∪X2 ∪…∪Xn =X;

b)对橙i≠j,Xi ∩Xj = W. 每个与节点 Ni 直接相连的节点称做 Ni 的邻居节点,记做 δ(Ni ). 这样整个 P2P 网络可以看做是一个具有 n 个节点的 无向连接图,每个节点都有一个 ID,通过一条边与它的邻居节 点相连. 为方便讨论,作如下假定: a)在任意时刻,每个节点 Ni 的邻居节点的集合 δ(Ni )是 已知的. b)网络中的消息传递是可靠的. Ni 向Nj (Nj ∈δ(Ni ))所 传递的消息均能确保到达,除非节点 Nj 已被删除,或者不再是 Ni 的邻居. 本文所提出的 P2PMaxSet 算法旨在高效地从分布于不同 节点的局部数据中发现最大频繁项集,最大程度地达到与在单 一计算机上对全局数据挖掘最大频繁项集相同的效果.

2 P2P 网络中最大频繁项集挖掘算法 2畅1最大频繁项集挖掘算法 为方便说明,本节给出每个节点内部挖掘最大频繁项集的 算法. 算法

1 maxSet(C,MFI) if ((sup(C∪tail(C))≥min_sup) and MFI 中不存在 C∪tail(C)的 超集) then C∪tail(C)→MFI;

return for tail(C)中的每个 1唱 频繁项集 i do Cn = C∪i;

if (sup(Cn )≥min_sup) then maxSet(Cn ,MFI) if (tail(C) = =饱)then C→MFI;

说明:算法

1 中tail(C)表示按照某种顺序排在项集 C 后 面的 1唱 频繁项集的集合;

MFI 为最大频繁项集集合;

C 和MFI 的初始值均为空集. 2畅2静态网络环境下的最大频繁项集挖掘算法 静态 P2P 网络环境下,最大频繁项集的挖掘如算法

2 所示. 因为 P2P 网络中所有节点的地位相同,故只给出某个节 点Ni 的运行情况,其他节点类似. 算法

2 静态网络环境中的 P2PMaxSet 算法 (1)用算法

1 得到节点 Ni 内的最大频繁项集 MFIi ;

(2)for Ni 邻居节点集合 δ(Ni )中的每个节点 Nj do (3) 发送 MFIi ;