第 32 卷第 5 期 2012 年 5 月中南林业科技大学学报 Journal of Central South University of Forestry & Technology Vol. 32 No. 5 May 2012 Apriori 算法在园林信息系统中的应用

Size: px

Start display at page:

Download "第 32 卷第 5 期 2012 年 5 月中南林业科技大学学报 Journal of Central South University of Forestry & Technology Vol. 32 No. 5 May 2012 Apriori 算法在园林信息系统中的应用"

伟资计
4 years ago
Views:

1 第 32 卷第 5 期 2012 年 5 月 Journal of Central South University of Forestry & Technology Vol. 32 No. 5 May 2012 Apriori 算法在园林信息系统中的应用周铁军张浩谭立志 ( 中南林业科技大学计算机与信息工程学院湖南摘长沙 ) 要近年来, 关联规则挖掘己经成为数据挖掘技术中的一个研究热点根据长沙市园林信息管理系统的发展要求并结合长沙市园林业的实际情况构架设计了园林管理信息系统分析了数据挖掘在园林行业中的应用用 Apriori 算法对园林病虫害数据库中的病虫数据进行了关联分析找出各种病虫害在相关属性中的分布规律为决策者提供有参考价值的信息关键字数据挖掘关联规则园林信息系统中图分类号 S73 TP393 文献标志码 A 文章编号 X (2012) Application of Apriori algorithm on garden information system ZHOU Tie-jun, ZHANG Hao, TAN Li-zhi (School of Computer and Information Engineering, Central South University of Forestry and Technology, Changsha , Hunan, China) Abstract: In recent years, the mining of association rules technique has became a research hotspot. According to the requirements of the development of Changsha city landscape information management system, and taking into account Changsha city garden industry actual situation, the structural design of landscape management information system was set up, the application of data mining in the landscape industry was analyzed. By using traditional Apriori algorithm, the data of plant diseases and insect pests in the ornamental diseases and pests database were connectedly analyzed, the distribution law of the relevant attribute of diseases and insect pests was found out, the results provided some valuable information for decision- makeing. Key words: data mining; association rules; garden information system 关联规则挖掘是数据挖掘技术中一个非常重要的研究内容它是 Agrawal 等人首先提出的关联规则挖掘是找出同一个事件中不同项之间的相关性即找出事件中频繁出现的项集或该项集的所有子集以及这些项集之间的相互关联性然后从这些项集中找出关联知识近年来国内外众多的学者对关联规则挖掘问题进行了大量的研究他们的工作涉及到关联规则挖掘理论的探索原有关联规则挖掘算法的改进 [1] 新关联规则挖掘算法的设计, 并行关联规则挖掘算法设计以及增量关联规则挖掘算法设计等问题另外在关联规则挖掘算法的可扩展性以及应用方面许多学者也进行了研究 1 关联规则Apriori算法概述关联规则挖掘 (Association Rules Mining) 是发现数据库中数据项之间蕴含规则的一种技术最初是针对购物篮分析 [2] 提出的, 数据分析人员从交易数据库中顾客购买的不同商品记录, 找到顾客的购买行为, 然后经营者利用这些购买行为指导商品货架设计货存安排以及根据购买行为对客户进行分类虽然关联规则挖掘是伴随零售业的决速发展而产生的但是关联规则挖掘的应用绝不仅仅体现在零售业上它还体现在金融业电信业制造业保险业等所以展开关联规则算法的研究具有重要的理论意义和应用价值 [3] Apriori 算法是一种挖掘关联规则的算法是 Agrawal 等设计的一个基本算法这是一个采用两收稿日期作者简介周铁军 (1956-) 男湖南益阳人教授硕士生导师, 主要从事网络安全数据挖掘的研究

2 182 周铁军等 Apriori 算法在园林信息系统中的应用阶段挖掘的思想并且基于多次扫描事务数据库来执行的 Apriori 算法的设计可以分解为两步骤来执行挖掘 a. 从事务数据库 D 中挖掘出所有频繁项集支持度大于最小支持度 minsup 的项集 Itemset 称为频集 Frequent Itemset) 首先需要挖掘出频繁 1- 项集然后继续采用递推的方式来挖掘频繁 k- 项集 k>1 具体做法是在挖掘出候选频繁 k- 项集 Ck 之后根据最小置信度 minsup 来筛选得到频繁 k- 项集最后合并全部的频繁 k- 项集 k>0 挖掘频繁项集的算法描述如下 [4] 1 L1 = find_frequent_1-itemsets(d); // 挖掘频繁 1- 项集比较容易 2 for (k = 2;Lk-1 Φ ;k++) { 3 Ck = apriori_gen(lk-1,min_sup); // 调用 apriori_gen 方法生成候选频繁 k- 项集 4 for each transaction t D { // 扫描事务数据库D 5 Ct = subset(ck,t); 6 for each candidate c Ct 7 c.count++; // 统计候选频繁 k- 项集的计数 8 9 Lk ={c Ck c.count min_sup // 满足最小支持度的 k- 项集即为频繁 k- 项集 return L= k Lk; // 合并频繁 k- 项集 k>0 b. 基于第 1 步挖掘到的频繁项集继续挖掘出全部的频繁关联规则置信度大于给定最小置信度的关联规则称为频繁关联规则 Frequent Association Rule 在这一步首先需要从频繁项集入手首先挖掘出全第5期部的关联规则或者称候选关联规则然后根据最小置信度来得到频繁关联规则挖掘频繁关联规则的算法描述如下 1 初始状态 L 是频繁项集集合 AR 是频繁关联规则集合 2 for all λk λk 是 L 的元素是一个 k- 频繁项集大小为 n { 3 for all αk αk 是 λk 的非空真子集 { 4 if(αk βm 的置信度 >= minconf) { // 这里 m + k = n 其中 αk βm 是一个关联规则 5 AR = AR (αk βm); return AR; 2 园林数据管理系统长沙市园林信息系统是在基于局政务网络和 PC SERVER 模式下为了加强全市园林绿化行业管理和行政管理的有效管理按照规范化集约化电子化的管理要求提高管理效能实现园林绿化专业信息的无纸化科学管理拟对全市园林绿化专业信息进行编辑整合开发构建专业信息基础数据库管理系统同时利用该应用系统平台使各种专业信息数据能共享使用减少信息孤岛充分发挥信息化带来的实际作用从而在更大的程度上提高工作效率实现电子政府推动政府行政职能优化 2.1 系统架构设计系统架构设计如图 1 所示图 1 园林信息系统构架设计 Fig. 1 Architecture design of garden information system

3 第 32 卷 2.2 主要技术采用的技术架构设计以先进成熟的 J2EE 关系型数据库 MS SQL Server 标准 B/S 应用模式 XML Web Services EAI 等技术为基础以开放性标准化为准则采用组件式分层次服务提供者 / 使用者间定义接口 Service Provider Interface 容错等设计思想保证整个应用系统的稳定性可靠性和可扩展性同时在数据交换格式上支持 XML 标准使系统功能最优化同时将整体系统 183 内部在技术上的相互依赖性减至最低实现应用系统和数据库系统分离系统支持内网部署并可扩展政务外网应用网络拓扑结构如图 2 所示基于园林绿化管理业务发展需要和系统前瞻性的设计思路系统采用通用的 Browser/Web Server/GIS Server 多层结构由分布在各客户端的浏览器 WEB 服务器和 GIS 服务器组成这样一方面可以通过园林的内部局域网可以实现集中办公统一管理另一方面城市居民可以通过 Internet 查询园林信息 [5] 图 2 网络拓扑结构 Fig. 2 Network topological structure 3 Apriori算法在园林系统中的应用这是一个应用于病虫害防治的一个挖掘实例, 用于预测某段时间发生虫害的可能性, 以及可能发生的其他种类的虫害的可能性, 为病虫害防治提供决策支持 3.1 设计模型主要采用现在普遍应用的三层架构模式表示层逻辑层数据层其中表示层负责直接跟用户进行交互一般是指系统的界面用于数据录入数据显示等用于做一些有效性验证的工作以更好地保证程序运行的健壮性如完成数据添加修改和查询业务等不允许指定的文本框中输入空字符串数据格式是否正确及数据类型验证用户的权限的合法性判断等等通过以上的诸多判断以决定是否将操作继续向后传递尽量保证程序的正常运行数据访问层顾名思义就是专门用于进行交互执行数据的添加删除修改和显示等需要强调的是所有的数据对象只在这一层被引用除数据层之外的任何地方都不应该出现这样的引用表示层设计在 web 服务器的 asp 页面被客户浏览器访问响应后在 shuru.asp 页面中用户输入霜霉病或 ID 然后再输入叶斑病或 ID 确认进入数据挖掘后的页面并通过浏览器返回给客户最后客户就会知道霜霉病发病的比例以及霜霉病发病时伴同叶斑病发病的几率逻辑层设计系统架构中体现核心价值的部分它的关注点主要集中在业务规则的制定业务流程的实现等与业务需求有关的系统设计也就是说它是与系统所应对的领域 Domain 逻辑有关很多时候也将业务逻辑层称为领域层数据访问层设计把系统所需要的数据统统建成数据库便于

4 184 周铁军等 Apriori 算法在园林信息系统中的应用第5期数据分析以及数据显示对应数据库服务器它 Set<String> set = itr.next(); 的任务是接受 Web 服务器对数据库操纵的请求 identicalset.retainall(set); // identicalset 中剩下实现对数据库的操作后把运行结果提交给 Web 服的元素是 identicalset 与 set 集合中公有的元素 [6] if(identicalset.size() == m-1) { // (k-1)- 项集中务器 3.2 部分系统实现 Apriori 算法实现扫描事务数据库计算频繁 1- 项集 k-2 个相同 Set<String> differentset = new HashSet<String>(); // 两个项集不同元素的集合 ( 集合的差运算 ) differentset.addall(originalitemset); public Map<Set<String>, Float> getfreq1itemset() { differentset.removeall(set); // 因为有 k-2 个 Map<Set<String>, Float> freq1itemsetmap = new HashMap<Set<String>, Float>(); Map<Set<String>,Integer>candFreq1ItemSet = 相同则 differentset 中一定剩下一个元素即 differentset 大小为 1 differentset.addall(set); // 构造候选 k- 项集的 this.getcandfreq1itemset(); Iterator<Map.Entry<Set<String>,Integer>>it=ca 一个元素 (set 大小为 k-1,differentset 大小为 k) candfreqkitemset.add(differentset); // 加入候 ndfreq1itemset.entryset().iterator(); while(it.hasnext()) { 选 k- 项集集合 Map.Entry<Set<String>, Integer> entry = it.next();// 计算支持度 Float supported = new Float(entry.getValue(). return candfreqkitemset; tostring())/new Float(txDatabaseCount); if(supported>=minsup) { freq1itemsetmap.put(entry.getkey(), supported); // 获取挖掘到的全部的频繁关联规则的集合 public Map<Set<String>, Set<Set<String>>> getassiciationrules() { return freq1itemsetmap; return assiciationrules; // 根据频繁 (k-1)- 项集计算候选频繁 k- 项集 public Set<Set<String>> apriorigen(int m, 打开长沙市园林管理信息系统客户端如图 3 Set<Set<String>> freqmitemset) { Set<Set<String>> candfreqkitemset = new HashSet<Set<String>>(); Iterator<Set<String>> it = freqmitemset. iterator(); Set<String> originalitemset = null; while(it.hasnext()) { originalitemset = it.next(); Iterator<Set<String>> itr = this. getiterator(originalitemset, freqmitemset); while(itr.hasnext()) { Set<String> identicalset = new HashSet<String>(); // 两个项集相同元素的集合 ( 集合的交运算 ) identicalset.addall(originalitemset); 系统运行截图图 4 所示根据提示在输入界面输入指定信息后, 点击确认后会调用 Apriori 算法进行关联规则挖掘扫描数据库已存信息并给出预测信息为园林管理人员决策提供分析 4 总结数据挖掘技术在园林信息系统中的应用无论在理论上还是在实际中都有大量的工作要做本文所做的工作为今后的进一步研究奠定了基础但仍有许多问题需要解决 1 关联规则数据挖掘算法的改进以提高效率 2 更好地利用数据库园林信息本身属于现存行业中数据量复杂度最高的信之一因此对

中国水利水电出版社 2003,8 步提高园林管理的自动化 3 目前还有其它很多数据挖掘方法比如刘同明. 数据挖掘技术及其应用 [M]. 北京 : 国防工业出版社 [4] 张莉数据挖掘技术及应用现状 [J].

5 第 32 卷 185 图3 园林信息系统输入界面 Fig.3 Input interface of garden information system 图4 园林信息系统查询结果界面 Fig.4 Query interface of garden information system 于园林数据影像数据的挖掘工作还有待进一步 [2] 2005:234: 开展将数据挖掘与信息系统界面有机结合集成在一起并采用可视化界面直观显示出来进一 [3] [7] 邵峰晶, 于忠清编著. 数据挖掘原理与算法 [M]. 中国水利水电出版社 2003,8 步提高园林管理的自动化 3 目前还有其它很多数据挖掘方法比如刘同明. 数据挖掘技术及其应用 [M]. 北京 : 国防工业出版社 [4] 张莉数据挖掘技术及应用现状 [J]. 中国石油大学胜利学院学报 2008,6:34-35 人工神经网络决策树支持向量机等今后应当继续进行这些方面的研究以便于更好的为园 [5] 张斌. 计算机技术在园林环境设计中的应用探索 [J].2007 林信息系统服务给园林管理部门更高效的决策 [6] 卢圣. 计算机辅助园林设计 [M]. 北京气象出版社.2009 支持 [7] 方骏方参考文献 [1] 李清峰. 数据挖掘中关联规则的一种高效 Ariori 算法 [J]. 计算机应用与软件, (12):84-86 云肖杰数据挖掘的工业标准的现状和展望 [J] 计算机应用研究 (6) [ 本文编校欧阳钦 ]

第 05 期董房等 : 一种卫星遥测在线状态监测及分析系统的设计 WEB 1 2 总体功能及组成 2.1 总体功能 1 2 3Web 2.2 结构组成 Web WEB WEB 2.3 系统各模块接口关系

第 05 期董房等 : 一种卫星遥测在线状态监测及分析系统的设计 WEB 1 2 总体功能及组成 2.1 总体功能 1 2 3Web 2.2 结构组成 Web WEB WEB 2.3 系统各模块接口关系电子科学技术 Electronic Science & Technology 电子科学技术第 02 卷第 05 期 2015 年 9 月 Electronic Science & Technology Vol.02 No.05 Sep.2015 年一种卫星遥测在线状态监测及分析系统的设计董房 1,2, 刘洋 2, 王储 2 2, 刘赞 (1. 上海交通大学, 上海,200240; 2. 上海卫星工程研究所,

第 32 卷 第 5 期 2012 年 5 月 中 南 林 业 科 技 大 学 学 报 Journal of Central South University of Forestry & Technology Vol. 32 No. 5 May 2012 Apriori 算法在园林信息系统中的应用

第 32 卷第 5 期 2012 年 5 月中南林业科技大学学报 Journal of Central South University of Forestry & Technology Vol. 32 No. 5 May 2012 Apriori 算法在园林信息系统中的应用