PDF《第27 卷第 9 期》

收稿日期: 2010唱02唱04;

修回日期: 2010唱03唱29 基金项目: 国家

863 计划资助项目(2007AA012474);

北京市优秀人才培养资助项目 (2009D005002000009) 作者简介:邓忠军(1963唱),男,内蒙古赤峰人,高级工程师,博士,主要研究方向为网络安全、数据挖掘(deng.

zj@163. com);

宋威(1980唱),男,讲师,博士,主要研究方向为数据挖掘;

郑雪峰(1951唱),男,教授,博导,主要研究方向为计算机网络、信息安全;

王少杰(1976唱),男,工程师,博士,主要研 究方向为计算机网络. P2P 网络 中最 大频 繁项 集挖 掘算 法研 究倡邓忠军

1 , 宋威2,郑雪峰

1 , 王少杰

3 (1. 北京科技大学 信息工程学院, 北京 100083;

2. 北方工业大学 信息工程学院, 北京 100144;

3. 国家信息技术 安全研究中心, 北京 100094) 摘要: 为解决 P2P 网络频繁项集挖掘中存在的全体频繁项集数量过多和网络通信开销较大这两个问题,提出 了一种在 P2P 网络中挖掘最大频繁项集的算法 P2PMaxSet. 首先,该算法只挖掘最大频繁项集,减少了结果的数 量;

其次,每个节点只需与邻居节点进行结果交互,节省了大量的通信开销;

最后,讨论了网络动态变化时算法的 调整策略. 实验结果表明,算法 P2PMaxSet 具有较高的准确率和较少的通信开销. 关键词: 数据挖掘;

P2P 网络;

最大频繁项集;

关联规则 中图分类号: TP311 文献标志码: A 文章编号: 1001唱3695(2010)09唱3490唱03 doi:10.

3969 / j. issn. 1001唱3695. 2010. 09.

078 Research on maximal frequent itemset mining algorithm over P2P network DENG Zhong唱jun

1 , SONG Wei

2 , ZHENG Xue唱feng

1 , WANG Shao唱jie

3 (1.School of Information Engineering, University of Science &

Technology Beijing, Beijing 100083, China;

2.College of Information Engi唱neering, North China University of Technology, Beijing 100144, China;

3.National Research Center for Information Technology Security, Bei唱jing 100094, China) Abstract: The obstacles mainly lie in numerous frequent itemsets and huge communication cost.To solve the two problems, this paper proposed a maximal itemset mining algorithm P2PMaxSet. Firstly, only considered maximal itemset, which reduced the number of itemsets greatly. Secondly, only interchanged mining results between neighbor nodes, which saved communica唱tion cost. Finally, discussed adjust strategies for dynamic environment. Experimental results show P2PMaxSet is not only accu唱rate but also with lower communication cost. Key words: data mining;

P2P network;

maximal frequent itemset;

association rule 频繁项集(模式) 挖掘是数据挖掘研究中的一个重要内 容,在关联规则、序列模式等方面有着广泛的应用 [1] . 随着网 络技术的发展,数据趋向于以分布式的方式进行存储. 特别是 大规模 P2P 网络的兴起 [2] ,为传统的频繁项集挖掘提出了新 的挑战. 目前 P2P 网络中数据挖掘的主要工作集中于聚类算 法[3,4] ,而P2P 网络中频繁项集的挖掘则鲜有研究. Wolff 等人[5] 最先提出了 P2P 网络中的关联规则挖掘算法,然而,他们 的方法基于多数投票策略直接挖掘关联规则,省去了频繁项集 挖掘的过程. 与分布式频繁项集挖掘 [6, 7] 不同,P2P 网络下的 挖掘往往需要考虑成百上千个分布于不同节点的数据库. 因此,在P2P 网络中挖掘频繁项集就难免要考虑如下两个关键 因素:a)挖掘什么样的项集,众所周知,传统的频繁项集挖掘 最主要的问题之一就是结果过多,在P2P 网络中更是如此;