Multi-Agent和关联规则挖掘的应用研究
|
摘要
关联规则挖掘是数据挖掘中成熟的技术之一,在商业管理、政府办公、科学研究和工程开发中得到了广泛应用。但其处理的目标常常是大规模的数据集,处理的是异构类型数据,另外考虑到数据挖掘的安全性、容错性等问题,为此迫切需要一种手段能够智能地、有效地、安全地挖掘出事务数据间有趣的关联规则。而分布式人工智能的前沿技术Multi-Agent具有高度智能化、易于构造分布式系统和软件复用性强等优点,这为关联规则挖掘提供了强有力支持。本文介绍了关联规则挖掘技术和Multi-Agent技术,并把它们应用到一个行为推荐原型系统当中,设计了一个基于Multi-Agent和关联规则挖掘的ARSM系统(The Action Recommendation Prototype System for User Based on Multi-Agent and Association Rule Mining),并将其应用到Web访问上。本文的主要工作如下:
利用已存在的BFP-Miner算法中改进的FP-Tree构造方法和基于位对象的频繁k-项集挖掘方法挖掘包含频繁k-项集的频繁(k+1)-项集,再根据最小置信度产生强关联规则。在ARSM系统中,将此产生强关联规则的方法应用于对用户行为日志进行挖掘,以产生行为推荐。
通过对系统推荐任务的规划和分解,设计了ARSM系统。ARSM系统由UserAgent、DProAgent、ARAgent和Action Log Data Base四部分组成,其中ARAgent负责管理DatabaseProcessAgent、BFPTreeMinerAgent和ARMAgent三个Agent。为实现每个Agent所具备的功能,设计了Agent的模型和结构、说明了Agent的工作流程及控制算法、定义了每个Agent具备的技能。通过Multi-Agent环境下Agent之间交互细节的分析,给出了ARSM系统中Multi-Agent的管理结构图。
把ARSM系统应用到Web访问上,为Web访问者进行行为推荐。实验中采用了来自于微软网站的匿名网络数据集,对它进行了预处理,然后在这个数据集上实现对Web访问者进行行为推荐的系统目标。文章说明了对Web访问者进行行为推荐的系统任务的实现过程,并对推荐过程中Agent主要技能给出实现,最后对系统的实验效果做了说明和分析。
Association rules mining is one of the most mature technology in data mining. It has been applied widely in business management, government office, scientific research and engineering development. Because the processing datasets are usually large- scale and heterogeneous ones, and considering the security and fault tolerance etc, a method which can mine interest association rules from the database intellectually, effectively, safely is needed urgently. Because of the high intelligence, effectiveness of constructing distributing system, and powerful reusable features of the Multi-Agent technology which is the top technology of distributed artificial intelligent, it provides strong support for association rule mining etc. The technology of association rule mining and the Multi-Agent are described in this paper. A system of ARSM based on association rule mining and Multi-Agent is designed, and it is applied to the action recommendation system of Web visiting. The main work is stated as follows:
Firstly, using the improved constructing method of FP-Tree (Frequent Pattern tree) and the mining method of the frequent k-item set based on bit objects in BFP-Miner(Bit Frequent Pattern Miner) algorithm that has been proposed, the frequent k+1-item set that includes the frequent k-item set is generated, then the strong association rules is obtained according to the min confidence. In the system of ARSM, the method that generates the strong association rules is applied to mine the Web log to recommend action for Web visitor.
Secondly, the system ARSM has been designed through analyzing the task of it. The architecture of ARSM is composed of four parts which are UserAgent、DProAgent、ARAgent and Action Log Data Base. ARAgent manages the three Agents which are DatabaseProcessAgent、BFPTreeMinerAgent and ARMAgent. In order to realize the function of each Agent, the model and the architecture of the Agent have been designed, the working process and control algorithm is also introduced. The skills of every Agent are defined. In the end, a manage framework of ARSM based on Multi-Agent is provided by analyzing the communication among Agents.
Finally, by pre-proceeding the anonymous Web data that comes from the Web of Microsoft, ARSM is applied to the Web visiting to recommend action for the user. The recommend process is implemented and the skills of Agent is realized. In the end, the experimental result of the system is displayed to demonstrate its effectiveness.
利用已存在的BFP-Miner算法中改进的FP-Tree构造方法和基于位对象的频繁k-项集挖掘方法挖掘包含频繁k-项集的频繁(k+1)-项集,再根据最小置信度产生强关联规则。在ARSM系统中,将此产生强关联规则的方法应用于对用户行为日志进行挖掘,以产生行为推荐。
通过对系统推荐任务的规划和分解,设计了ARSM系统。ARSM系统由UserAgent、DProAgent、ARAgent和Action Log Data Base四部分组成,其中ARAgent负责管理DatabaseProcessAgent、BFPTreeMinerAgent和ARMAgent三个Agent。为实现每个Agent所具备的功能,设计了Agent的模型和结构、说明了Agent的工作流程及控制算法、定义了每个Agent具备的技能。通过Multi-Agent环境下Agent之间交互细节的分析,给出了ARSM系统中Multi-Agent的管理结构图。
把ARSM系统应用到Web访问上,为Web访问者进行行为推荐。实验中采用了来自于微软网站的匿名网络数据集,对它进行了预处理,然后在这个数据集上实现对Web访问者进行行为推荐的系统目标。文章说明了对Web访问者进行行为推荐的系统任务的实现过程,并对推荐过程中Agent主要技能给出实现,最后对系统的实验效果做了说明和分析。
Association rules mining is one of the most mature technology in data mining. It has been applied widely in business management, government office, scientific research and engineering development. Because the processing datasets are usually large- scale and heterogeneous ones, and considering the security and fault tolerance etc, a method which can mine interest association rules from the database intellectually, effectively, safely is needed urgently. Because of the high intelligence, effectiveness of constructing distributing system, and powerful reusable features of the Multi-Agent technology which is the top technology of distributed artificial intelligent, it provides strong support for association rule mining etc. The technology of association rule mining and the Multi-Agent are described in this paper. A system of ARSM based on association rule mining and Multi-Agent is designed, and it is applied to the action recommendation system of Web visiting. The main work is stated as follows:
Firstly, using the improved constructing method of FP-Tree (Frequent Pattern tree) and the mining method of the frequent k-item set based on bit objects in BFP-Miner(Bit Frequent Pattern Miner) algorithm that has been proposed, the frequent k+1-item set that includes the frequent k-item set is generated, then the strong association rules is obtained according to the min confidence. In the system of ARSM, the method that generates the strong association rules is applied to mine the Web log to recommend action for Web visitor.
Secondly, the system ARSM has been designed through analyzing the task of it. The architecture of ARSM is composed of four parts which are UserAgent、DProAgent、ARAgent and Action Log Data Base. ARAgent manages the three Agents which are DatabaseProcessAgent、BFPTreeMinerAgent and ARMAgent. In order to realize the function of each Agent, the model and the architecture of the Agent have been designed, the working process and control algorithm is also introduced. The skills of every Agent are defined. In the end, a manage framework of ARSM based on Multi-Agent is provided by analyzing the communication among Agents.
Finally, by pre-proceeding the anonymous Web data that comes from the Web of Microsoft, ARSM is applied to the Web visiting to recommend action for the user. The recommend process is implemented and the skills of Agent is realized. In the end, the experimental result of the system is displayed to demonstrate its effectiveness.
引文
[1]沈斌.关联规则相关技术研究[D].浙江大学博士学位论文, 2007
[2]王嵩岩.基于数据挖掘的关联规则研究与应用[D].北京科技大学硕士学位论文, 2006
[3]颜雪松.关联规则的并行开采研究[D].中国地质大学硕士学位论文, 2003
[4]崔建国.基于隐私保护的关联规则挖掘研究[D].中国民航大学硕士学位论文, 2008
[5]车志军.人工智能在搜索引擎资源获取中的应用[D].浙江大学硕士学位论文, 2006
[6] Agrawal R, Imeielinski T, Swami A. Mining Association Rules between Sets of Items in Large Databases [C]. Proc of Processing of ACM SIGMOD, Washington, USA, 1993, 207~216
[7]史忠植,王文杰.人工智能[M].北京:国防工业出版社, 2007
[8] Wooldridge M, Jennings NR. Intelligent Agents Theory and Practice [J]. Knowledge Engineering Review, 1995, 10(2): 115~152
[9] Jennings NR, Sycara KP. Wooldridge M. A Road Map of Agent Research and Development [J]. Journal of Autonomous Agents and Multi-Agent Systems, 1998, 1(1): 7~15
[10] Chauhan D, JAFMAS: A Java-based Agent Framework for Multi-Agent Systems Development and Implementation [D]. ECECS Department, University of Cincinnati, Cincinnati, OH, 1997
[11] Alan G, Alan K G, Albert D B. Multi-Agent Communication in JAFMAS [C]. Proc of the Working Notes of the Workshop on Specifying and Implementing Conversation Policies, 1999, 67-70
[12]李军,张卓.多Agent系统中Agent的协作机理与模式[J].青岛大学学报(工程技术版), 2005, 20(3): 43~47
[13]王珑,章毅,吴跃. MAS环境下实现Agent交互协作的关键技术[J].电子科技大学学报, 2003, 32(2): 158~163
[14]薛宏涛,沈林成,叶媛媛,等.基于协进化方法的多智能体协作系统体系结构及其仿真框架[J].系统仿真学报, 2002, 14(3): 297~303
[15]朱智强,王惠芳,郭中,等.多Agent系统安全框架及实现[J].计算机工程与应用, 2003, 39(35): 147~151
[16]李业丽,常桂然.基于Agent的知识发现模型的设计[J].计算机工程与应用, 2001, 37(4): 80~82
[17]杨炳儒,游福成.基于Multi-Agent技术的知识发现新模型KDD的设计[J].计算机工程与应用, 2003, 39(12): 1~3
[18]杜彦华,尹晓峰,刘春煌.基于多Agent的铁路客票数据挖掘系统的研究[J].铁路计算机应用, 2004, 14(8): 5~7
[19]李俊.基于Agent的分布式中国旅游目的地营销系统的研究[D].北京工商大学硕士学位论文, 2006
[20]焦连臣.基于Agent的假日旅游数据挖掘平台的研究[D].北京工商大学硕士学位论文, 2007
[21]伍少成. Agent的强化学习与通信技术研究及应用[D].华南理工大学博士学位论文, 2006
[22]王治国,王利,刘广钟.基于Internet的Agent并行计算[J].广西师范大学学报(自然科学版), 2003, 21(1): 156~159
[23]陈卓,魏振钢.基于分布式数据挖掘的移动代理系统设计[J].计算机应用研究, 2004, (2): 192~194
[24]陈刚.基于代理的分布式数据挖掘系统设计[J].计算机工程, 2001, 27(9): 65~67.
[25]袁晓玲,赵茜,桂振梅.关联规则挖掘算法的优化处理[J].河北省科学院学报, 2005, 22(2): 14~16
[26] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules [C]. Proc of the Int’l Conf on Very Large Databases, Santiago, Chile, 1994, 487~499
[27] Srikant R, Agrawal R. Mining Generalized Association Rules [C]. Proc of the Int’l Conf on VLDB, Zurich, Switzerland, 1995, 407~419
[28] Park J S, Chen M S, Yu P S. An Effective Hash Based Algorithm for Mining Association Rules [C]. Proc of ACM SIGMOD, California, USA, 1995, 175~186
[29] Savasere A, Omiecinski E, Navathe S. An Effective Algorithm for Mining Association Rules in Large Databases [C]. Proc of the Int’l Conf on Very Large Databases, Zurich, Switzerland, 1995, 432~444
[30] Yen S J, Chen A L P. An Efficient Approach to Discovering Knowledge from Large Databeses [C]. Proc of Int’l Conf on Parallel and Distributed Information Systems, Miami Beach, Florida, 1996, 8~18
[31] Lin D-L, Kedem Z M. Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set [C]. Proc of the Int’l Conf on Extending Database Technology: Advances in Database Technology, Valencia, Spain, 1998, 105~119
[32] Roberto J, Bayardo Jr. Efficiently Mining Long Patterns from Databases [C]. Proc. of the ACM-SIGMOD Int'l Conf. on Management of Data, New York, USA, 1998, 85~93
[33] Agarwal R, Aggarwal C, Prasad V. Depth First Generation of Long Patterns [C]. Proc of the ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining , Boston, USA, 2000, 108~118
[34] Han J, Pei J, Yin Y. Mining Frequent Patterns Without Candidate Generation [C]. Proc of the ACM SIGMOD Int’l Conf on Management of Data, New York, USA, 2000, 1~12
[35]宋余庆,朱玉全,孙志辉,等.基于FP-Tree的最大频繁项集挖掘及其更新算法[J].软件学报, 2003, 14(9): 1586~1592
[36]杨君锐,张铁军,刘南艳.基于位对象的最大频繁模式挖掘算法[J].西南交通大学学报, 2008, 43(4): 488~493
[37] Li S, Ying M. Extensionality of the RCC8 Composition Table [J]. Fundamental Informatics, 2003, 55(3-4): 363~385
[38]史忠植.智能主体及其应用[M].北京:科学出版社, 2000, 12~13
[39]刘大有,杨鲲,陈建中. Agent研究现状与发展趋势[J].软件学报, 2000, 11(3): 315~321
[40]何炎样. Agent系统和多Agent系统的设计与应用[M].武汉:武汉大学出版社, 2001
[41]宁小红.基于Web日志挖掘的个性化推荐系统的研究和实现[D].浙江大学硕士学位论文, 2007
[42] Gopalan N P, Akilandeswari J. A Distributed, Fault-tolerant Multi-agent Web Mining System for Scalable Web Search [C]. Proc of the WSEAS Int. Conf. on Applied Informatics and Communications, Malta, 2005, 384~390
[43] Ruairi R M, Keane M T. An energy-efficient, multi-agent sensor network for detecting diffuse events [C]. Internatioanl Joint Conference on Artificial Intelligence, Hyderabad, India, 2007, 1390~1395
[44]曾春,邢春晓,周立柱.个性化服务技术综述[J].软件学报, 2002, 13(10): 1952~1961
[45]丁一.基于Web挖掘的个性化推荐服务研究[D].华中科技大学硕士学位论文, 2004
[46]余轶军. Web访问信息挖掘若干关键技术的研究[D].浙江大学博士学位论文, 2006
[47]李学俊,李龙澍,徐怡.基于粗糙集的Web用户行为预测研究[J].计算机工程与应用, 2008, 44(13): 134~136
[48] O'Hare G M P, Jennings N R. Foundations of Distributed Artificial Intelligence [M].New York: John Wiley & Sons, 1996, 365~400
[49] Vicente M A, Daniel B.ABC2 An Agenda Based Multi-agent Model for Robots Control and Cooperation [J]. Journal of Intelligent and Robotic Systems, 2001, 32(1): 93~114
[50]陈冠岭,樊晓聪,徐殿祥,等. Agent的通信语言-KQML [J].计算机科学, 1998, 25(6): 35~39
[51]石慧,徐从富,刘勇,等. Agent的通信语言KQML的实现及应用[J].计算机工程与应用, 2005, 41(13): 94~96
[2]王嵩岩.基于数据挖掘的关联规则研究与应用[D].北京科技大学硕士学位论文, 2006
[3]颜雪松.关联规则的并行开采研究[D].中国地质大学硕士学位论文, 2003
[4]崔建国.基于隐私保护的关联规则挖掘研究[D].中国民航大学硕士学位论文, 2008
[5]车志军.人工智能在搜索引擎资源获取中的应用[D].浙江大学硕士学位论文, 2006
[6] Agrawal R, Imeielinski T, Swami A. Mining Association Rules between Sets of Items in Large Databases [C]. Proc of Processing of ACM SIGMOD, Washington, USA, 1993, 207~216
[7]史忠植,王文杰.人工智能[M].北京:国防工业出版社, 2007
[8] Wooldridge M, Jennings NR. Intelligent Agents Theory and Practice [J]. Knowledge Engineering Review, 1995, 10(2): 115~152
[9] Jennings NR, Sycara KP. Wooldridge M. A Road Map of Agent Research and Development [J]. Journal of Autonomous Agents and Multi-Agent Systems, 1998, 1(1): 7~15
[10] Chauhan D, JAFMAS: A Java-based Agent Framework for Multi-Agent Systems Development and Implementation [D]. ECECS Department, University of Cincinnati, Cincinnati, OH, 1997
[11] Alan G, Alan K G, Albert D B. Multi-Agent Communication in JAFMAS [C]. Proc of the Working Notes of the Workshop on Specifying and Implementing Conversation Policies, 1999, 67-70
[12]李军,张卓.多Agent系统中Agent的协作机理与模式[J].青岛大学学报(工程技术版), 2005, 20(3): 43~47
[13]王珑,章毅,吴跃. MAS环境下实现Agent交互协作的关键技术[J].电子科技大学学报, 2003, 32(2): 158~163
[14]薛宏涛,沈林成,叶媛媛,等.基于协进化方法的多智能体协作系统体系结构及其仿真框架[J].系统仿真学报, 2002, 14(3): 297~303
[15]朱智强,王惠芳,郭中,等.多Agent系统安全框架及实现[J].计算机工程与应用, 2003, 39(35): 147~151
[16]李业丽,常桂然.基于Agent的知识发现模型的设计[J].计算机工程与应用, 2001, 37(4): 80~82
[17]杨炳儒,游福成.基于Multi-Agent技术的知识发现新模型KDD的设计[J].计算机工程与应用, 2003, 39(12): 1~3
[18]杜彦华,尹晓峰,刘春煌.基于多Agent的铁路客票数据挖掘系统的研究[J].铁路计算机应用, 2004, 14(8): 5~7
[19]李俊.基于Agent的分布式中国旅游目的地营销系统的研究[D].北京工商大学硕士学位论文, 2006
[20]焦连臣.基于Agent的假日旅游数据挖掘平台的研究[D].北京工商大学硕士学位论文, 2007
[21]伍少成. Agent的强化学习与通信技术研究及应用[D].华南理工大学博士学位论文, 2006
[22]王治国,王利,刘广钟.基于Internet的Agent并行计算[J].广西师范大学学报(自然科学版), 2003, 21(1): 156~159
[23]陈卓,魏振钢.基于分布式数据挖掘的移动代理系统设计[J].计算机应用研究, 2004, (2): 192~194
[24]陈刚.基于代理的分布式数据挖掘系统设计[J].计算机工程, 2001, 27(9): 65~67.
[25]袁晓玲,赵茜,桂振梅.关联规则挖掘算法的优化处理[J].河北省科学院学报, 2005, 22(2): 14~16
[26] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules [C]. Proc of the Int’l Conf on Very Large Databases, Santiago, Chile, 1994, 487~499
[27] Srikant R, Agrawal R. Mining Generalized Association Rules [C]. Proc of the Int’l Conf on VLDB, Zurich, Switzerland, 1995, 407~419
[28] Park J S, Chen M S, Yu P S. An Effective Hash Based Algorithm for Mining Association Rules [C]. Proc of ACM SIGMOD, California, USA, 1995, 175~186
[29] Savasere A, Omiecinski E, Navathe S. An Effective Algorithm for Mining Association Rules in Large Databases [C]. Proc of the Int’l Conf on Very Large Databases, Zurich, Switzerland, 1995, 432~444
[30] Yen S J, Chen A L P. An Efficient Approach to Discovering Knowledge from Large Databeses [C]. Proc of Int’l Conf on Parallel and Distributed Information Systems, Miami Beach, Florida, 1996, 8~18
[31] Lin D-L, Kedem Z M. Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set [C]. Proc of the Int’l Conf on Extending Database Technology: Advances in Database Technology, Valencia, Spain, 1998, 105~119
[32] Roberto J, Bayardo Jr. Efficiently Mining Long Patterns from Databases [C]. Proc. of the ACM-SIGMOD Int'l Conf. on Management of Data, New York, USA, 1998, 85~93
[33] Agarwal R, Aggarwal C, Prasad V. Depth First Generation of Long Patterns [C]. Proc of the ACM SIGKDD Int'l Conf on Knowledge Discovery and Data Mining , Boston, USA, 2000, 108~118
[34] Han J, Pei J, Yin Y. Mining Frequent Patterns Without Candidate Generation [C]. Proc of the ACM SIGMOD Int’l Conf on Management of Data, New York, USA, 2000, 1~12
[35]宋余庆,朱玉全,孙志辉,等.基于FP-Tree的最大频繁项集挖掘及其更新算法[J].软件学报, 2003, 14(9): 1586~1592
[36]杨君锐,张铁军,刘南艳.基于位对象的最大频繁模式挖掘算法[J].西南交通大学学报, 2008, 43(4): 488~493
[37] Li S, Ying M. Extensionality of the RCC8 Composition Table [J]. Fundamental Informatics, 2003, 55(3-4): 363~385
[38]史忠植.智能主体及其应用[M].北京:科学出版社, 2000, 12~13
[39]刘大有,杨鲲,陈建中. Agent研究现状与发展趋势[J].软件学报, 2000, 11(3): 315~321
[40]何炎样. Agent系统和多Agent系统的设计与应用[M].武汉:武汉大学出版社, 2001
[41]宁小红.基于Web日志挖掘的个性化推荐系统的研究和实现[D].浙江大学硕士学位论文, 2007
[42] Gopalan N P, Akilandeswari J. A Distributed, Fault-tolerant Multi-agent Web Mining System for Scalable Web Search [C]. Proc of the WSEAS Int. Conf. on Applied Informatics and Communications, Malta, 2005, 384~390
[43] Ruairi R M, Keane M T. An energy-efficient, multi-agent sensor network for detecting diffuse events [C]. Internatioanl Joint Conference on Artificial Intelligence, Hyderabad, India, 2007, 1390~1395
[44]曾春,邢春晓,周立柱.个性化服务技术综述[J].软件学报, 2002, 13(10): 1952~1961
[45]丁一.基于Web挖掘的个性化推荐服务研究[D].华中科技大学硕士学位论文, 2004
[46]余轶军. Web访问信息挖掘若干关键技术的研究[D].浙江大学博士学位论文, 2006
[47]李学俊,李龙澍,徐怡.基于粗糙集的Web用户行为预测研究[J].计算机工程与应用, 2008, 44(13): 134~136
[48] O'Hare G M P, Jennings N R. Foundations of Distributed Artificial Intelligence [M].New York: John Wiley & Sons, 1996, 365~400
[49] Vicente M A, Daniel B.ABC2 An Agenda Based Multi-agent Model for Robots Control and Cooperation [J]. Journal of Intelligent and Robotic Systems, 2001, 32(1): 93~114
[50]陈冠岭,樊晓聪,徐殿祥,等. Agent的通信语言-KQML [J].计算机科学, 1998, 25(6): 35~39
[51]石慧,徐从富,刘勇,等. Agent的通信语言KQML的实现及应用[J].计算机工程与应用, 2005, 41(13): 94~96