《基于概念格的规则提取算法研究及改进_赵凯 (1).pdf》由会员分享，可在线阅读，更多相关《基于概念格的规则提取算法研究及改进_赵凯 (1).pdf（3页珍藏版）》请在三一文库上搜索。
1、收稿日期：2011-10-26 作者简介：赵凯（1981-），硕士，助教，研究方向：网络数据库。 基于概念格的规则提取算法研究及改进 赵凯 （淄博职业学院，山东 淄博255314） 摘要：提出了一个基于概念格的规则算法的改进算法。 该算法可以大大提高数据挖掘的效率，提高查 找时的速度。 关键词：数据挖掘；概念格；算法 中图分类号：TP399文献标识码：A文章编号：1001-7119（2012）02-0123-03 Concept Lattice based Rule Extraction Algorithm Research and Improvement ZHAO Kai （Zibo Voc
2、ational Institute, Zibo 255314，China） Abstract：This paper presents a rules based on concept lattice algorithm to improve the algorithm, this algorithm can greatly improve the efficiency of data mining, improve the search speed. Key words：data mining；concept lattice 1关联规则挖掘 关联规则挖掘就是从数据库中挖掘出所有的强关 联规则和
3、数据。 它可以分为以下几个问题： （1） 在事务数据库中找出所有的相关频繁数据项 目集。即找出用户指定的最小关联频繁数据项，而且要 不小于指定的项目集。 （2） 在事务数据库找出的频繁数据项目集， 经过 一系列动作，产生相关的强关联规则。 2算法改进 2.1算法的提出 新的算法相对以前的规则产生集来说， 大大减少 了规模，并且大大提高了相应的数据挖掘的效率。为了 和以前的传统规则的产生集相区别， 我们把这个新的 产生集称为组规则产生集。 它和传统的提取规则算法 相比，由于产生集的规模大大减少了，由此，用户可以 很好地理解相应的规则，更容易推导出其他的新规则， 避免了大量的对用户来说无用的新规则
4、的产生， 对于 大型的数据库来说，也避免了产生大量的规则产生集。 但是该算法相对传统规则集来说也有不足， 比如新的 算法对每个规则的支持度和信任度不能很好地支持， 只支持满足本身支持度和信任度的相关规则。 2.2算法的描述 S是一个规则集合，F=Xi是闭合集合S中的大部分 规则闭合子集中的集合。 MaYjmalOenerators(Y,S); Omax(Y)=； J=Y-Yj；/集合X中的新项目集 For all jJ /每一个子集项目作为最大生成器 Omax(Y)= Omax(Y)j； O1=j|jY-J；/剩余的项目集 t=1； Whjle OT FOR ALL OOT JF O U Yj
5、FOR ALL YjS Omax(Y)= Omax(Y)O； Ot= OtO； /做为下一轮的候选最大生成器 Ot+1=O=j1jtjt+1|A1jt+1,EOjOt,Oj=j1jj-1jj+1jt+1 t=t+1； 创建一个新的概念格，从中取出相应的规则。设定 支持度的最小值为A，信任度的最小值为B。 第28卷 第2期 2012年2月 科 技 通 报 BULLETIN OF SCIENCE AND TECHNOLOGY Vol.28 No.2 Feb. 2012 科技通报科技通报第28卷 通过取出的规则，创建一个规则的最小集合C。 步骤一：初始化C=0。 根据获取的规则数计算求出 所需要的事
6、务节点总数D， 把事务节点总数D=n+1，并 且把事务节点数存储在创建的最小集合H中。 步骤二：经过计算，求出H中所有的根节点和子节 点的上级和下级节点中的指针数， 然后求出最小指针 数Fmin和最大指针数Fmax。 步骤三：如果Fmin=0，此计算直接结束，转到最后 一步。 否则，把Fmax中的数值放入到最小集合H中。 经过计算求出子节点D的外延指数，自定义为q。 根据子节点D的外延指数， 直接求出相应的上级 和下级节点的数量，然后存储在最小集合H中。 根据规则生成一个产生集合相应的节点K和Kn， 他们之间的支持度和信任度都设置为最小， 放入集合 H中。 对于节点K和Kn， 去掉相应的上级和
7、下级的外延 数对应的节点。 如果kn0，执行步骤三；否则将kn中每一个节点 和其直接上级节点配对求最小规则，并入集合H中；在 kn中去掉k1中节点的直接上级。 如在k1中的集合H没有下级或上级的节点， 转步 骤三；否则，转向步骤二。 步骤四：如果Fmin=Fmax，那么直接转向转步骤 一。 步骤五：算法结束，计算完毕。 3由组规则产生集的理论证明 3.1理论证明 由组规则产生集推算出来的算法应该是要在规则 集里找到一组节点数，例如：A1,A2,A3,A4,，其中 A1=Ai=An(1in)。 在这一组节点数中，所有节点之 间的规则和所有相邻节点之间支持度要求必须是最简 规则，信任度为10%的最
8、小规则。 所有的组节点之间的规则都可以由（A1,An）(1i n)的规则来推导出来，因此产生集也必须有（A1,An）的 规则来推导出来。 A=minterion(Bn)+C 节点对（A2，An）之间的规则产生集是： C=minterion(An)-A1 已有节点对(A1，A2)之间的信任度为10%的最小 规则： A2=A1这意味着num(A2+A1)=num(A) 对A2=A1利用第一个性质A=minterion (Bn)+S， 可得到下面的公式： A2= minterion(An)+C 因为num (A2+A1)=num (A)， 所以说故A2=A1与 C=minterion(An)-A1的
9、支持度是一样的，但是信任度 是不一样的。 因此由A=minterion(Bn)+C 可导出C=minterion (An)-A1， 用A2=A1和A2= minterion(An)+C就可导出num(A2+A1)=num(A)。 通过上面的理论证明，同理可得，(A2=Ai=An(2 in)以及其他的组节点之间的规则都可以由上面的证 明来推导出来。通过对所有组节点的理论证明，我们都 可以推导出来相应的组节点规则。 3.2实例描述 把信任度设置为40%，支持度设置为5，创建一个 根节点0#，自定义3组数据，例如：（1）4，6，8，2，4，9；（2） 0，5，3，6，8，4；（3）5，7，8，3，5
10、，1。 从第一组数据开始搜 索计算，根据算法可以产生一个规则集，如下： （1）46之间的节点信任度可以为20%，支持度为5； （2）68之间的节点信任度可以为40%，支持度为5； （3）82之间的节点信任度可以为60%，支持度为5； （4）24之间的节点信任度可以为80%，支持度为5； （5）49之间的节点信任度可以为100%，支持度为5； 由（1）可以看出各个数据之间的关系，由信任度可 以看出各个数据之间的对应关系 ， 可以推导 出A （4，6），B（6，8），C（8，2），D（2，4），E（4，9）的信任度是一 个逐级递增的。 由（1）可以看出各组数据之间的关系，由信任度可 以看出各个数据
11、之间的对应关系 ， 可以推导 出A （4，6），B（6，8），C（8，2），D（2，4），E（4，9）的信任度是一 个逐级递增的。 由（2）可以看出各组数据之间的关系，由支持度可 以看出各个数据之间的对应关系 ， 可以推导 出A （4，6），B（6，8），C（8，2），D（2，4），E（4，9）的支持度是不 变的。 由（3）（5）可以看出各个数据之间的关系，由信任 度和支持度可以看出各个数据之间的对应关系， 可以 推导出A：4，B：6，C：8，D：2，E：4，F：9之间是没有关系 的。 经过第一组数据的演算，同理，我们也可以在第二 组和第三组数据中推算出相同的规则算法。 获取组节点中的上级或下
12、级节点， 取出他们的存 储的规则，如果这个节点不为空，那么就继续查询，直 到找到不为空的节点为止， 把所有不为空的节点都存 储起来，并记录这些节点的数量。 如果这些节点中的规则的前部分和后部分都一样 的话，就转向第一个节点。 将规则的前部分和后部分存储的数据进行合并， 求出并集。 并把计算出来的并集输出到集合A中。 然后将规则的前部分和后部分存储的数据进行相 124 第2期 代入方程（11），得到： n= lcos1 sin1 -r（17） 至此， 垃圾摆振筛检机构在有约束条件下的参数 设计问题得到彻底解决。 3结论 本文讨论的垃圾分类筛检机构中的摆振系统可以 抽象为四连杆机构加以分析。 为了
13、获得本文所讨论问 题的解， 建立四连杆机构的几何模型并且推导出摇杆 与连杆参数方程， 使其垃圾摆振筛检机构在有约束条 件下的参数设计问题得到彻底解决。 参考文献： 1申永胜 机械原理教程（第2版）M北京：清华大学出版 社，2005. 2何品晶,冯肃伟,邵立明.城市固体废物管理M.北京： 科学出版社, 2003. 3王勇，宋德朝.基于Matlab/simulink的四杆机构连杆点轨 迹仿真J机械研究与应用，2007. 4羊有道.平面四杆机构运动性能研究D.上海：东南大 学，2005. 5赵云鹏.平面连杆机构自调机构分析与综合D.重庆：重 庆大学，2006. (上接第75页) 交，求出交集。 并把
14、计算出来的并集输出到集合B中。 用A减去规则的前部分，得到集合C。 用B加上规则的后部分，得到集合D。 假如A=B，说明规则的推导正确。 3.3从一般产生集的算法推算到组规则产生集的 算法 用规则集合信任度和默认度为100%的满足的所 有子节点来推算之间的算法： 所有子选节点之间要产生的产生集B。 已经创建好的组规则产生集合A。 步骤一：初始化B=h。 步骤二： 将A指向的规则链表中的根节点输出到 规则指向的存储列表中。 步骤三：从集合B中取出一个规则数，创建第一个 连接表，把最后的指针J指向集合L中。 步骤四：集合F中存储的根节点和子节点之间的规 则创建K=a。 步骤五：如果开头子节点的上级
15、节点数目不为零， 则转到步骤三。 步骤六：如果集合B不为空，则从集合B中取出一 个指针T，指向上一个链接表。 否则将集合F中的根节 点和子节点之间存储的产生集的前半部分求交集S和 差集D。 步骤七：算法结束，计算完毕。 4总结 （1）本文在传统概念格的基础上进行了创新，提出 了一个新的关联规则的算法。 该算法与传统的提取规 则的算法相比，数据挖掘的效率大大提高，规模大大减 少。 （2）对大型的数据库来说，支持度和信任度大大提 升，规模进行了精简，极大地减少了数据在储存空间中 的容量。 用户使用起来可以提高数据库数据的查找速 度，可以更好地推导出用户所需要的规则，极大地避免 了多余规则的产生。 而且新的算法不能对所有的规则 进行提取，所以成为组规则产生集。 参考文献： 1简宋全,胡学钢,蒋美华.扩展概念格的渐进式构造J.计 算机工程与应用,2009,15:132- 134. 2赵文兵,简宋全,王浩，等.约简概念格的纵向维护算法 J.计算机工程与应用，2009(7):209- 211. 3王德兴,胡学钢,王浩.基于量化概念格的关联规则挖掘 J.合肥工业大学学报,2009,25(5): 678-682. 赵凯.基于概念格的规则提取算法研究及改进125