毕业论文-一种多概念格横向合并算法的分析与实现.docx

山西大学论文 编号：2002241125论文题目 一种多概念格横向合并算法的分析与实现姓 名 毛博韬 院系、专业 计算机与信息技术学院、软件工程 学习年限 2009 年 9 月至 2013年 7 月指导教师 王俊红 学位级别 学 士 2013年5月1日一种多概念格横向合并算法的分析与实现计算机与信息技术学院 毛博韬指 导 教 师 王俊红内容摘要 概念格是数据分析和规则提取的一种有效工具，已经广泛应用于机器学习、模式识别、数据挖掘等领域。然而，构造概念格的时间复杂度一直是影响形式概念分析应用的主要因素. 本文设计和实现了一种多概念格横向合并算法，该算法先进行形式背景的横向拆分. 为简单起见, 可以采用均等拆分, 把原背景拆分为多个小的子形式背景, 然后采用相应的概念格生成算法构造相应的子概念格, 再通过子概念格的横向并运算就可得到形式背景的概念格.实验表明, 该算法和直接用形式背景来构造概念格的算法相比, 其时间复杂度有显著改善.关键词: 概念格; 形式背景; 子格; 子背景; 横向合并1引言概念格是由德国Wille1教授在20世纪80年代提出的，是数据分析和规则提取的一种有效工具，它的每一个节点是一个形式概念，由两部分组成：外延，即概念所覆盖的实例；内涵，即概念的描述，该概念所覆盖的实例的共同特征。概念格及其Hasse图正好体现了一种概念层次结构，在这种层次结构上更有利于进行规则提取、分类、检索等。目前概念格正在广泛应用于机器学习、模式识别、专家系统、计算机网络、数据分析、决策分析、数据挖掘等领域2,3。目前概念格理论的主要成果有：一系列生成算法，目前已有的生成算法大致分为两类，一类是批处理算法，另一类是渐进式算法；概念格上分类规则和关联规则挖掘算法，和其他分类器相比，概念格上的规则提取具有相当好的效果；在许多领域的广泛应用，例如数字图书馆、词典的调整等等。其中本文中的多概念格横向合并算法先是对形式背景进行横向拆分，把原背景拆分为多个小的子形式背景，然后采用相应的概念格生成算法构造相应的子概念格，再通过子概念格的横向合并运算就可得到形式背景的概念格。2 概念格的基本定义 本节我们介绍了有关概念格理论的基本概念，关于概念格的详细描述请参见1。在形式概念分析中，形式背景通常被定义为一个三元组，其中是对象(实体)的集合，是描述符(属性)的集合，是与之间的一个二元关系，即。表示“对象具有特征”。在形式背景中，在的幂集和的幂集之间可以定义两个映射和1如下：，。它们被称为的幂集和的幂集之间的Galois联系。来自的二元组如果满足两个条件：及，则它被称为是形式背景的一个形式概念，其中和被称为概念的内涵和外延。所有形式概念的集合被标记为。上最重要的结构是由亚概念-超概念关系产生的，其定义如下：两个概念和，如果，则是的亚概念，记为。通过这个关系，我们可以得到有序集，这是一个完全格，被称为形式背景的概念格。概念格中每个结点都是一个形式概念。对于概念格中两个不同的结点和，如果是的亚概念且不存在其他结点满足，则称为是的子结点（直接后继），而是的父结点（直接前驱）。3 概念格的渐进式构造算法概念格的建造是研究多概念格横向合并的基础和前提，目前已有的概念格生成算法大致分为两类：批处理算法和渐进式算法。本文主要分析和实现了Godin2算法，即动态生成概念格算法。概念格的渐进式构造就是在给定的原始的形式背景下所对应的初始的概念格 以及新增的对象的情况下，求解形式背景所对应的概念格。在渐进式生成概念格的求解过程中，要解决的问题有个：所有新结点的生成；避免已有格结点重复生成；边的更新。为了有效地解决这个问题，对于初始概念格中的每个结点，根据它和新增对象的特征集之间的关系，可以定义它们的不同类型。定义12.如果一个格节点C满足，则被称为是一个更新格节点。显然，如果是一个更新格结点，则在中被更新为。定义2.如果某个格节点满足：令，而在L中不存在某个节点满足；对于中任意满足的节点，都有被称为是一个产生子格节点。定义3 在同项形式背景K 1 和K 2 中, 若M1H M2= U, 则称K 1 和K 2、L (K 1 ) 和L (K 2 ) 分别是内涵独立的; 若M1 H M2X U, 对于任意g I G 和任意m I M1 H M2 满足gI 1m Z gI 2m, 则称K 1 和K 2、L (K 1) 和L( K2 ) 分别是内涵一致的. 显然, 内涵独立的是内涵一致的特例, 内涵独立的一定也是内涵一致的.定义4 如果K1= ( G, M1, I 1) , K2= ( G, M2, I 2 ) 是两个内涵一致的形式背景, 则: K 1K 2= ( G, M1G M2, I 1G I 2) 称为两个形式背景的横向加运算, 用加横线的加操作符( ) 表示.定义5 对于K = ( G, M, I ) 中的形式概念Ci= ( Ai, Bi ) 、Cj = (Aj , Bj ) ( i X j ) ：( 1) 如果Ai = Aj , 则称Ci = Cj , 即概念相等.( 2) 如果Ai = Aj , 则称Ci 大于Cj .( 3) 如果Ak = Ai H Aj , Bk = Bi G Bj , 则Ck = ( Ak, Bk ) = Ci有了上述的定义, 就可以进行概念格的横向合并运算.定义6 如果L (K 1) 和L( K2 ) 是两个内涵一致的概念格, 它们的横向并运算L( K1) -G L (K 2) 等于概念格L, 那么对于设L (K 1) 中的某个概念C1 和L (K 2) 中的某个概念C2, 令C3= C1C2, 如果在L ( K 1) 中的所有小于C1 的概念中不存在等于或大于C3 的概念, 并且在L( K 2) 中的小于C2 的所有概念中不存在等于或大于C3 的概念, 则C3 I L .性质2.设是产生子格节点，如果满足，则必然有成立。对于中的任何一个节点，如果在中不存在某个节点满足，则被称为新生格节点。对于产生子格节点，节点显然是属于的新生格节点，被称为由生成的新生格节点。新生格节点和产生子格节点之间是一一对应的，所以生成所有新生格节点的关键是找出所有产生子格节点，而不同的产生子格节点所对应产生的新生格节点是互不相同的，这种对应关系的建立就解决了格更新的前两个问题。更新格节点的基本思想是将每个新生格节点插入格中并维护父子节点之间边的关系：设是表示概念节点集合的变量，它被初始化为。对于每个生成的新生格节点，必须确定它在中的所有父节点集合()和所有子节点集合()。对于任意的()，添加边；对于任意的()，添加边；并且去除所有满足()和()的边。最后将加入到中，当所有的新节点均添加到中后，便完成了对概念格的更新操作，得到的概念集合以及所有的边便是更新后的概念格。4 多概念格横向合并算法4.1概念格的横向合并由于概念格是其形式背景中的概念间关系的表现形式, 它和对应的形式背景是一一对应的. 因此, 对概念格的分布处理必然涉及到形式背景的拆分、合并等处理.定义14. 如果组件对于输入示例的执行，产生该示例的输出，那么我们说示例关于组件是有效的。如果代码组件是一个纯函数，则示例包括论据值和返回值；如果代码组件是一个过程，则示例包括论据值以及执行以后的论据值。数据库中的组件的示例是由组件的开发者提供的，这是因为开发者能更好的了解组件及提供更好的示例来描述组件。用户可以通过选择所期望的示例来检索组件。例如：定义一个表示数据库形成的一个形式背景，定义为数据库中所有组件的集合：=(,)，定义为数据库中所有示例的集合：=(,)。在集合中，基于示例对组件有效的二元关系： =(,)|对是有效的且X 且D。定理1 如果L (K 1) 和L (K 2) 是内涵一致的概念格, 则L( K1) -G L (K 2) = L( K1 K2) .证明:( 1) 证明在L( K1 ) -G L ( K 2) 中的概念一定在L (K 1 K 2)中:假定C3= (A3 , B3) I L (K 1 ) -G L ( K2 ) , 如果C3 由定义6生成的, 则有C1= (A3G Ax, B1 ) I L (K 1) 和C2= ( A3G Ay , B2)I L (K 2) , 且Ax H Ay = U和B1 G B 2= B3 . 那么在K 1 中有B 1使得g( B1) = A3G Ax , f (A3 ) Bf ( A3G Ax ) = B1, 这时若Ax =U, 则f ( A3)= f ( A3G Ax ) = B1; 若Ax X U, 由于任何小于C1 的概念中不存在等于或大于C3 的概念, 所以只能有f ( A3) = f(A3 G Ax ) = B1, 这时(A3 , B1 ) 不是一个概念, 因为A3 X g ( f(A3 ) ) . 同理在K 2 中有B2 使得g ( B2 ) = A3 G Ay 和f (A3 ) =B2, 因此在K 1K2 中有B1 G B2= B3 满足g ( B3) = A3 和f( A3)= B3, 即C3= (A3, B3 ) I L (K 1K 2) ;( 2) 证明在L (K 1，K 2) 中的概念一定在L ( K1 ) -G L ( K 2) 中:假定C3= ( A3, B3 ) I L ( K1 K 2) , 如果B3= B1 G B2, 且B1 在K 1 中和B 2 在K2 中, 则在K1 中有g ( B 1) = A3 G Ax , f( A3G Ax ) = B1 和在K 2 中有g( B2) = A3G Ay , f (A3G Ay) = B2且Ax H Ay = U, 即有C1= (A3 G Ax , B 1) I L (K 1) 和C2= ( A3GAy , B 2) I L (K 2) . 并且由于在K1 K 2 中有f ( A3) = B3= B1GB2, 则在K1 中有f ( A3) = B1= f ( A3 G Ax ) , 而( A3 , B1) 不是L( K1 ) 中的一个概念, 因为A3 X g ( f ( A3) ) , 也就是说在L (K 1 )小于C1 的概念中不存在等于或大于C3 的概念; 同理在K 2中有f (A3) = B2= f ( A3 G Ay ) , 并且在L ( K2 ) 小于C2 的概念中不存在等于或大于C3 的概念. 则C3 能由L (K 1) 中的C1 和L( K2) 中的C2 根据定义6 生成, 因此C3= (A3 , B3) I L (K 1 )-G L( K2 ) . 至此, 就为多概念格的横向合并提供了依据. 也就是说,若要构造一个形式背景的概念格, 可先进行形式背景的横向拆分. 为简单起见, 可以采用均等拆分, 把原背景拆分为多个小的子形式背景, 然后采用相应的概念格生成算法构造相应的子概念格, 再通过子概念格的横向并运算就可得到形式背景的概念格.4. 概念格的构造我们使用形式概念分析对组件和示例之间的二元关系建造一个概念格，考虑任意两个集合和：是形式概念的外延，是形式概念的内涵，（,）称为一个形式概念。对于给定的形式背景的两个概念（,）和（,），有（,）（,）或者（,）（,）。两个概念最大下界定义为它们外延的交集和这些外延具有的内涵：。两个概念的最小上界定义为它们内涵的交集和具有这些内涵的所有外延：。4.3多概念格的横向合并算法4.3.1 基本原理若要构造一个形式背景的概念格, 可先进行形式背景的横向拆分. 为简单起见, 可以采用均等拆分, 把原背景拆分为多个小的子形式背景, 然后采用相应的概念格生成算法构造相应的子概念格, 再通过子概念格的横向并运算就可得到形式背景的概念格.4.3.2简单多概念格横向合并算法多概念格的横向合并算法(Horizontal Union Algorithm of Multiple Concept Lattices, 简记为HUMCL 算法) 的伪码描述如下:INPUT: 概念格L( K 1) 和概念 A, B OUTPUT: 新的概念格L (K 1)BEGINFOR 每个概念节点( A1, B1) I L ( K 1) , 按照| A1| 的升序排列IF 节点(A1 , B1) 的更新或新增标志THEN CONTINUE ENDIF( * )IF A1A A THEN; 更新概念将B 加到B1 中, B1= B1 G B ;将(A1, B1) 加入到VISITED- CS 中;置(A1, B1) 节点的更新或新增标志; ( * )IF A1= A THEN exit ENDIFELSENewextent= A1H A; 可能是产生子概念IF 不存在某个( Ac1, Bc1 ) I VISITED- CS 满足Ac1 =Newextent THEN 创建一个新节点Cnew = (Newextent, B1G B) ) ;增加边(A1, B1 ) y Cnew;FOR VISITED- CS 中的每个节点Ca DOIF child THENIF Ca 是( A1, B1 ) 的孩子节点THEN 删除边( A1, B1 ) y Ca ; ENDIF增加边Cnew y Ca ; Ca 是新增节点的直接孩子概念ENDIFENDIF4.4.1 多概念格横向合并算法初始化： 对于(Al，B1)L(K1)、c2(A2，B2)L(K2)，按照内涵的势升序比较概念的内涵；步骤1 对于待合并概念，即cl(Al，B1)L(K1)、C2(A2，B2)L(K2)，Bl=B2=B，合并为(Al U A2，B)，若A1A2，则更新c1(A1，B1)、c2(A2，B2)各自的前辈概念；若概念格中任意两个合并后的概念由父子关系直接相连，并且存在其它的概念使得这两个概念间接相连成为祖孙关系，则删除这两个概念之间的直接相连的父子关系；步骤2 对于产生子概念对，即c1(Al，B1)L(K1)、c2(A2，B2)L(K2)，B1B2，生成概念c3(AlUA2，B。nB：)(如果内涵为空或者等于某个已经产生的生成概念的内涵，则放弃这个概念)，并更新c1(A1，B1)、C2(A2，B2)各自的前辈概念；假如B1 n B2=Bi或Bl =B2，转步骤4；否则，执行步骤3；步骤3 若c，、c：有共同的前辈概念，c3调整为c1、c2的共同前辈概念的子概念，c3成为cl、c2的直接父概念。步骤4 删除已经生成的c3；如果B1 n B2=Bl，cl调整为cl(AIUA2，B1)，建立父子关系使cl成为c2的父概念，若c：的内涵包含于c，原有子概念的内涵，则删除cl与原有子概念的父子关系；如果B1 n B2=B2，c2调整为c2(Al U A2，B2)，建立父子关系使。2成为c1的父概念，若c。的内涵包含于c：原有子概念的内涵，则并删除c：与原有子概念的父子关系；步骤5 结束并返回结果更新前辈概念：若一个概念(A，B)的外延增大，增加的对象集为A。，即(A，B)更新为(A U A。，B)，则概念(A，B)的前辈概念(A。，)的外延都需要增大，(A。，)更新为(A。U A。，瓦)；x,J-于合并或者生成得到的一个概念，若其前辈概念也是合并或者生成得到的一个概念，那么就不再对这个前辈概念进行更新，也不再对这个前辈概念的前辈概念进行更新4.4.2 多概念格横向合并流程图开始 设置i的值，把形式背景均等拆分为i份,保存到数组str中m|i生成strm所对应的概念格，并保存到str1中m=m+1m=0否是n=0n|i依次合并子概念格str1nn=n+1是结束图4-3 多概念格横向合并流程图 5一个具体的实例 abcd1xxx2xx3xx4xxx5x 表1 形式背景示例 #4(1,2,3,4,5,) #2(1,2,4,5,a) #3(1,3,4,b) #1(1,4,a,b) 图(a) 由属性a、b生成的概念格 #41,2,3,4,5, #22,3,c #31,4,d #1(,c,d) 图 (b) 由属性c、d生成的概念格 设把表1 所示的形式背景横向分成两个子背景K 1=( G, M1, I 1 ) 和K2 = ( G, M2,I 2 ) , 其中M1= a, b 和M2= c, d . 其对应的子格为L(K 1) 和L ( K2 ) , 分别如图2 中的( a)、( b) 所示.两个子格中的节点按其外延的势的大小从小到大按序进行处理, 其序号标注在节点旁. 现在把L (K 2 ) 中的节点依次加入到L( K1 ) 中.图3 加入L ( K 2) 中的节点时L ( K 1) 的变化示意 加入节点# 1c: 首先和# 1 运算, H 1, 4 = , a, b G c, d = a, b, c, d , 得到节点# 5( , a, b, c, d ) , 而在L ( K 1) 和L ( K 2) 中都不存在小于# 1 和# 1c节点, 所以节点# 5( , a, b , c, d ) 是新增节点, 其产生子是# 1; 而# 1c和# 1 的后续节点都产生外延和#5 相同的节点, 所以不会产生新增节点. 加入# 1c后的格如图3( a) 所示, 其中加粗的节点是新增节点, 加粗的实线表示它和其产生子节点之间的连接线.加入节点# 2c: 由于它是节点# 1c 的后加入节点, 所以无需考虑它和新增节点# 5 间的运算. 和# 1 运算, 由于 1, 4 H 2,3= , 不会产生新节点;和# 2 运算, 1, 2, 4, 5 H 2, 3 = 2 , a G c = a, c , 得到节点# 6( 2 , a, c ) , 由于在L ( K1 ) 和L (K 2) 中小于# 2 和# 2c的节点都没有等于或大于#6, 所以节点# 6 ( 2 , a, c ) 为新增节点, 其产生子是# 2; 同理, 和节点# 3 运算产生新增节点# 7( 3 , b , c ) , 和节点# 4 运算产生新增节点# 8( 2, 3 , c ) , 这里的新增是指新增到L ( K1 ) 中的节点. 加入# 2c 后的格如图3( b ) 所示, 其中加粗的节点是新增节点, 加粗的实线表示它和其产生子节点之间的连接线, 加粗的虚线表示它和其直接孩子节点之间的连接线.加入节点# 3c: 由于无需考虑和新增节点间的运算, 它首先和# 1 运算, 因为 1, 4 A 1, 4 , 所以节点# 1 需要更新, 形成更新节点( 1, 4 , a, b G d ) = ( 1, 4 , a, b, d ) ; #3c和后面# 2、# 3、# 4 节点运算都形成外延 1, 4 , 所以不需要再进行处理. 加入# 3c后的格实际上已经和图1 相同.加入节点# 4c: 只需考虑它和节点# 2、# 3、# 4 运算,明显地, 节点# 2、# 3、# 4 需更新, 但由于节点# 4c的内涵为 , 所以这些节点不变.下图是我做的系统运行效果图：6 系统测试性能与分析为了验证上述多概念格的横向合并算法的有效性, 我们在windows 2000 下用Java 2 编程实现了该算法, 在P4 1. 7G 的计算机上对随机产生的数据采用不同的拆分方案进行了测试,。试验中, 形式背景的对象个数、属性个数及其对象属性间存在关系的概率由程序随机产生.对形式背景的拆分方案即可采用均等拆分也可采用随机拆分. 明显地, 采用均等拆分虽然简单, 但不一定是最佳方案.拆分个数不同其效果也不相同, 但并不是拆分越细效果越好.一种极端的情况, 对于n 个属性的形式背景如果拆分为n 个子形式背景, 则HUMCL 算法实际上就退化为CLIF- A 算法. 7 总结概念格作为形式概念分析的核心数据结构，已经引起了人们的广泛关注，并且已经在知识发现、软件工程、信息检索等诸多领域得到了一定的应用。由于概念格自身的完备性，概念格的时间复杂度一直是影响形式概念分析的主要障碍。本文中多概念格横向合并算法先是对形式背景进行横向拆分，把原背景拆分为多个小的子形式背景，然后采用相应的概念格生成算法构造相应的子概念格，再通过子概念格的横向合并运算就可得到形式背景的概念格。实验结果证明，我们所证明的算法切实可行的减少了概念格生成所用的时间。通过一个学期的毕业实习，我对概念格的基本知识有了粗浅的了解。切实领悟到了理论联系实际的重要性。由于实践经验的缺乏，使得在系统的开发、设计与实现上还有很多欠缺之处，在后期的系统完善中，我们将不断完善系统的功能，使其真正实现自身的价值。本文从选题、修改到定稿无不得益于我的导师王俊红老师的精心指导，在她耐心细致的指导下使得我在这次实习中学到了很多知识。我也要感谢答辩组的组长张霞老师在百忙之中评阅了我的系统和论文，并提出了许多合理的建议。在此我还要感谢计算机与信息技术学院所有关心和指导过我的各位老师，他们不仅教会了我丰富的计算机专业知识，更重要的是使我明白了许多做人处事的道理。参考文献1 Wille R. Restructuring lattice theory: An approach based on hierarchies of concepts. Rival I eds. Ordered Sets, Dordrecht: Reidel, 1982, 445-470.2 Godin R et al. Incremental concept formation algorithms based on Galoie (concept) lattices. Computational Intelligence, 1995, 11(2), 246-267.3 Mineau G W, Godin R. Automatic structuring of knowledge bases by conceptual clustering. IEEE Trans on Knowledge and Data Engineering, 1995, 7(5): 824-828.4 Young P. Software retrieval by samples using concept analysis. The Journal of Systems and Software, 2000, 54, 179-1835 谢志鹏 ,刘宗田.概念格的快速渐进式构造算法.计算机学报，2002，25(5)：490-495.6 Lindig C. Concept_based component retrieval. Proceedings of the IJCAI Workshop on Formal Approaches to the Reuse of Plan, Proofs and Programs, 1995.7 Lindig C, Snelting G. Assessing modular structure of legacy code based on mathematical concept analysis. Proceedings of the International Conference on Software Engineering, 1997, 349-359.8 吴忠植. 知识发现. 北京: 清华大学出版社, 2002. 9 Yun Li, Zongtian Liu, et al. Theoretical research on the distribut ed con construction of concept lattices A . Proceedings of the Second Internat ional Conference on Machine Learning and Cybernet ics C . Xian: Inst-itude of Electrical and El ectronics, 2003. 474- 479. 10 Zongtian Liu, Liangsheng Li, Qing Zhang. Research on a union algorithm of multiple concept latt ices A . RSFDGrC 2003, LNAI 2639 C . Berlin: Springer-Verlag Heidelberg, 2003. 533- 540.11 李云, 刘宗田, 陈等. 基于属性的概念格渐进式生成算法 J .小型微型计算机系统, 2004, 2 5( 10) : 1768- 1771.12 Gant er B,Wille R. Formal Concept Analysis:Mathematical FoundationsM . Berlin: Springer-Verlag, 1999.13 Baltasar Fernandez-Manjon, Alfredo Fernandez-Valmayor. Building educational tools based on formal concept analysis J .Educat ion and Information Technologies, 1998, 3(3- 4) : 187- 201. 14 U Krohn, N J Davies, R Weeks. Concept lattices f or knowl edge management J . BT Technol J, 1999, 17( 4) : 108- 113.15 S O Kuznetsov. Machine learning on the basis of formal concept analysis J .Automation and Remote Control, 2001, 62( 10) : 1543- 1564. 16 Godin R, Missaoui R, Alaoui H. Increment al concept formation algorithmsbased on Galois ( concept ) lattices J . Comput ational Int ell-igence, 1995, 11( 2) : 246- 267.Analysis and Implementation of a multi-concept lattice of horizontal mergers algorithmSchool of computer and information techno