（基础数学专业论文）形式概念分析中若干算法的改进与实现.pdf

摘要 形式概念分析是一种基于格结构的数据分析方法，可以作为数据 挖掘的一种算法，用于数据分析和知识处理。概念格是形式概念分析 的核心数据结构，它体现了概念内涵和外延的统一，非常适合用于提 取规则型知识概念格模型作为一种用于数据分析的形式化工具，已 经在很多领域得到广泛关注和应用 在概念格的应用中，首先要根据形式上下文建出概念格，所以开 发出高效的概念格生成算法是形式概念分析在应用中实现的首要条 件目前，国内外的概念格生成算法主要分为批处理式概念格生成算 法和增量式概念格生成算法，批处理式算法主要用于数据量较小或给 定形式上下文的概念格的构造；增量式算法可_ 以处理形式上下文是动 态的数据，即当形式上下文改变时，可以重新建格的概念格生成算法 本文主要研究批处理式概念格生成算法，重点做了以下几点工 作： 1 在简单概述前人一些算法的基础上，编程实现了文中的算法 3 ，得到概念格及相对应的 i a s s e 图 2 在分析和研究已有概念格算法的基础上，构造并实现了一种 自底向上的批处理式算法，在得到概念格后，我们又构造出一种基于 所得概念格的画h a s s e 图的算法 关键词形式概念分析，数据挖掘，概念格，h a s s e 图，批处理算法 a b s t r a c t f o n n a lc o n c e p ta i l a l y s i si sa1 a t t i c e b a s e dt o o lf o rd a c aa n a l y s i s ，i t c a l lb ec o n s i d e r e da sa na l g o r i t l l i i lo fd a t a - m 越n ga 1 1 dh a sb e e nu s e di n d a 诅a n a l y s i sa f l dk 1 1 0 w l e d g ep r o c e s s i n g c o n c 印tl a 钍i c ei st h em o s t i m p o r t a i l td a 胁q p ei nf o m a lc o n c e p ta n a l y s i s ， i t r e p r e s e n t s t h e i n t e g r a t i o no fi n t e m sa n de x t e n t si nc o n c e p t sa 1 1 di ti sv e r ys u i tf o rt h e e x t r a c t i o no fm l e s c o n c e p tl a t t i c ei saf o m a l i z e dt o o lf b rd a t aa 1 1 a l y s i s a n dh a db e e nu s e di nm a n yd i f f b r e n td i s c i p l i n e s t h eg e n e r a t i o no fc o n c e p tl a 牡i c ep l a y sa l l i n l p o r t a n tr o l ei nt h e a p p l i c a t i o n so fc o n c e p tl a t t i c e s ow es h o u l dp a ym o r ea t t e n t i o nt o 馈1 e a l g o r i 岫l f o r b u i l d i n gc o n c 印t l a 钍i c e 豇l e r ea r e m a n y d i 行e r e n t a l g o r i 廿l i i l s f b rb u i l d i n gc o n c e p tl a t t i c e ，a n dm e 8 ea l g o r i m m sc a nb e d i v i d e di n t ot w om a i nc a t e g o r i e s 、v h i c hw ec a l i e db a t c hc o n s t m c t i o na n d i n c r e m e n t a lc o n s t r l l c t i o n t h eb a t c ha l g o r i m m sa r eu s e df o rb u i l d i n g c o n c e p tl a t t i c ew h o s ef b 咖a lc o n t e x th a db e e ng i v e na i l dt h ea l g o r i m m s o fi n c r e m e n t a 王c o n s t m c t i o na r em o r ec o n v e n i e n tt 1 1 a nb a t c ha l g o r i m m s w i t l ld y n a m i cd a t a t h i st 1 1 e s i si sf o c u so nt h eb a t c ha l g o r i 廿1 m s n ef o l l o w i n gi so u r m a i nr e s e a r c hw o r 圭( s ： 1 i n t r o d u c es o m eb a s i ca l g o r i m lf o rb u i l d i n gc o n c 印tla _ t t i c e t h e n w ec a r r i e do mt h ea l g o r i t h m3 ，a n dg o tm eh a s s ed i a g r a mo ft h i s a l g o r i t l l m 2 c o m p a r et h ef e a t u r eo fs o m eb a t c ha l g 蹦m m s ，w ei n t r o d u c e da n d c a r r i e do u tan e wb a t c ha l g o r i 妇t h e nb a s e do nt 1 1 ec o n c e p tl a t t i c e ，w e c o n s t r u c t e dan e w a l g o r i t h l l lf o r 出a w i n gt h eh a s s ed i a g r a m k e yw o r d sf o 衄a lc o n c 印ta n a l y s i s ，d a t am i n i n g ，e o n c e p tl a 仕i c e s ， h a s s ed i a g r 啪，b a t c ha l g o r i t h m 第一节本文的研究背景 第一章引言 在过去的数十年中，数据库技术飞速发展，我们产生和收集数据的能力已经 迅速提高全世界每天新存入数据库的数据量超过万兆字节，多到没人有时间去 看的程度现在我们面临的问题是“数据丰富，但知识缺乏”如何能从这浩瀚 的数据海洋中得到隐藏在其后的重要信息成了我们将要解决的一个难题在这种 背景下，数据挖掘技术便应运而生 数据挖掘【1 捌是一个多学科交叉研究领域，它融合了数据库技术、人工智能、 机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据 可视化等最新技术的研究成果形象地说，数据挖掘是在“数据矿山”中找到蕴 藏的“知识金块”，帮助企业减少不必要投资的同时提高资金回报简单地说， 数据挖掘是从大量数据中提取或“挖掘”知识，是一个利用各种分析工具在海量 数据中发现模型和数据间关系的过程，这些模型和关系可以用来做出预测从技 术的角度，数据挖掘的定义是，在数据库中，对数据进行一定的处理，从大量的、 不完全的、有噪声的、模糊的、随机的数据中提取隐含的、事先未知的、但又是 潜在有用的信息和知识的过程 形式概念分析【3 棚理论以数学化的概念和概念层次为基础，是格理论【4 5 ，6 】的一 个分支，可以作为数据挖掘的一个算法，用于数据分析和知识处理形式概念分 析的核心数据结构概念格是提取规则知识【习的一个很好的平台，其概念格结 点体现了概念内涵和外延的统一，非常适合于用来发现规则型知识因此，运用 形式概念分析理论，结合数据库等相关背景，从大量数据中抽取出有用的知识， 如概念等，是切实可行并且是有意义的，其主要优点在于可以将数据中( 无论是 表面的还是隐含的) 内在逻辑和组织结构完整地图示化( h 嬲s e 图) ，从而为分析 概念数据之间的关联提供系统的可视化工具 目前，国内外已有很多专家学者从不同的领域研究形式概念分析理论及其在 数据挖掘中的应用形式概念分析的理论性研究，始于德国数学家r u d o l fw m e 在1 9 8 2 年对它的引入【耵我们一般研究的形式上下文都是在有限的情形下，文 献【5 ，9 ，l l ，1 2 ，1 3 】还研究了无限的形式上下文，并用范畴论的观点来研究形式概念 分析，构造出了一个形式上下文和上下文态射构成的范畴c x t 在应用上，国内 的一些研究主要集中在形式概念格的生成算法、概念格与关联规则1 4 1 5 ，1 q 之间的 联系、基于概念格的分类规则【1 6 】等方面国外还有研究人员开发了一些基于形 式概念格的学习系统，如r u l e a r n e r 系统，l e g a l e 系统等此外，形式概 念分析还成功应用于面向对象程序设计【m 、信息检索嘲、信息过滤【埘、软件工 型刎等领域 在应用形式概念分析的过程中，首先要从形式上下文中构造概念格，因此研 究概念格生成算法，是实现形式概念分析的首要问题国内外已提出的生成概念 格的算法一般分为批处理算法【2 1 盈，2 3 洲和增量算法磷筇2 7 2 羽批处理算法根据其 生成格的不同方法，可以分为自顶向下算法、自底向上算法、枚举法等增量算 法中比较著名的是g o 击n 的算法，他们采用渐进式算法来生成概念格，其关键在 于找出生成的子结点 第二节本文的主要内容和结构 本文主要研究批处理式概念格生成算法 本文共分为四章： 第一章主要介绍了形式概念分析的背景和本文的结构 第二章简要介绍了阅读本文所需的关于序、格、上下文、概念和概念格方面 一些基础知识 第三章是本文的重点，第一节概述了概念格的生成算法，第二节在简单概述 前人算法的基础上，编程实现了文中介绍的算法3 ，并画出了相应的 k 图第 2 三节构造并实现了一种自底向上的批处理式算法，在得到概念格后，我们又构造 出一种基于所得概念格的画h a s 图的算法 第四章简单总结了本文的研究成果 第二章预备知识 本章概要介绍本文将要用到的关于序、格、上下文、概念和概念格方面的一 些基本知识和结论，详情请参考各节中分别引用的文献 第一节序和格 形式概念分析是一种基于格结构的数据分析方法而格是一种特殊的偏序 集，本节介绍了阅读本文所需的序和格方面的基础知识，本节的参考文献有 【3 ，4 ，5 6 ，l l ，1 2 】等 定义2 1 设煲集合p 上的一个二元关系，且满足下列条件：慨，弦z 尸， ( 1 工s 工 ( 自反性) ； ( 2 ) x y ，j ，5 z j x 5 ：( 传递性) ； ( 3 ) x s y ，y s x j x = y ( 反对称性) 雯q 称为p 上的一个偏序( 关系) ，对俨；9 是一个偏序集在不至混淆的情况下， 对( p ；9 也经常简记为p 如果工s | ，且x j ，则记为善 y 例2 2 任意集合x 的所有子集的幂集p 在集合包含关系下形成一个偏序 集：实数集兄在通常的5 关系下形成一个偏序集，并且这个偏序集是一个链，因 为对于所有的x ，j ，灾，或者有x 茎j ，或者有j ，! 工( 即，灾中的任何两个元素都是 可比较的) 定义2 3 设p 是一个偏序集，x ，y p ，元素工被y 覆盖( 或者y 覆盖工) ， 如果工 y 且不存在= 尸使得z 2 ) ，记为x ( y 定义2 ，4 设| p 是一个偏序集，j ，j ，p ，由善到y 的一个长度为n 的极大链 指的是序列x = 却 x ， 勋 = 弘p 4 命题2 5 如果偏序集p 有限，工 厶容易看出，这是z 中包含4 的最小集合。称为彳的闭包 命题2 1 3 任何闭包系统z 关于集合的包含关系称为一个完备格 第二节上下文、概念和概念格 本节概要介绍了形式概念分析中上下文、概念和概念格的基本理论，详细内 容请参阅文献【3 】 6 一、概念的抽象定义 定义2 1 4 设有对象的集合g 和属性的集合m 若，g m ( 从g 到m 的 一个二元关系) ，则称三元组( g ，md 是一个( 形式) 上下文为简化描述，形 式上下文和形式概念在以下内容中，分别称为上下文和概念 若( g ，肌) l 读为对象g 有属性所，并记为g ，脚 在形式概念分析中，上下文通常列成表格的形式，称为交叉表 例2 1 5 下图是一个简化的太阳系的上下文 属拦 s i z ed i s 丘唧f 渤ns i m 啪n s m a m e d i 啪 l a r g e n e a r f 盯y e sn 0 行星 ( a ) ( b )( c )( d )( e )( f )( g ) 1 m e _ y 2 v e n 吣 3 e a r t h 4 m a 稻 5 j u p i 埘 6s a l i i m 7u 啪u s 8 n e p 山 9p l u t o 图2 也一个简化的太阳系的上下文 在这个上下文中，一个概念由表示外延和内涵的有序对 ，研构成，其中外 延是由九大行星构成的集合( 对象集合) 的一个子集，内涵占是由七种属性 构成的集合( 属性集合) 的一个子集；而且它们满足如下约束： ( 1 ) 矗中只含有中全体对象所共有的那些属性； ( ，h 一中的对象恰好是分享丑中所有属性的那些 例如，若爿= e a n l l ，m a 啦，胆 s i z e - s m a l l ，d i s 眦眦- 缸，m o o n - y e s ，则似， 西是一个概念在下面的章节中，为了叙述的方便，我们将s i z e s m a l l 记为口， 7 将s i z c m e d i 岫记为6 ，将幽簪l a r g e 记为c ，其余的属性也类似标记，同时将 m e i u r y 记为l ，将v h 璐记为2 ，将e a m l 记为3 ，其余的对象也类似标记 对于彳g ，b 弛令： 爿= ( 班磊f i 、留彳，g 歹拼 ， = g g i v 脚口，g ，删 由彳一彳和占卜+ 给出了映射：p ( g ) 一p 和：p ( 岣一矽( q ，称为关 系，的极 定义2 1 6 设一互g ，风批若4 ，- 口，= 彳，则称口，印是上下文( g m ，) 中的一个概念彳叫做概念a ，固的外延，口叫做概念似，回的内涵 上下文( g ， 厶d 中的所有概念的集合记作颈g ，md 引理2 1 7 设( g ， 以d 是一个上下文，4 g ，眶m 则： ( 1 ) 是( g ， 以d 中某个概念的外延铮4 ”= 彳； ( 2 ) 丑是( g ， 以d 中某个概念的内涵铸b ”= b 引理2 1 8 设( g ， 磊d 是一个上下文，爿，4 ( ，j ) g ，口，弓( ，廷坛则； ( 1 ) 舅”，魄：； 鼢a | 昏2 ja 胁i b 1 0 2 等b f 2 磁； ( 3 ) = 4 ”，= ”； ( 4 ) ( u ，“4 ，) ，= n ，“，( u u 动7 = n ，。j 彰； ( 5 ) 4 e ：铮爿b 对于口j ，b j ) ，a 2 ，蚴豸( g ，md ，规定： 似j ，丑，) s 2 ，助铮j 也曰，历 根据引理，关于这样定义的序，颈g ， 以d 构成一个格 = 、概念格 定义2 1 9 。k g ，j | i 磊参9 称为上下文( g ，玉厶乃的概念格 例2 2 0 生成太阳系上下文所对应的概念格如下： 8 g l2 a g m a 图2 - 3 太阳系上下文对应的概念格 b 78 在图2 - 3 中，结点上的标号有两种：数字的标号表示对象g g ，字母的标号 表示属性脚从分别对应于概念( g ，曲和咖，珊，) 例如，标号为口m 的结点表示概念 ( ，口，) = ( 1 2 3 4 9 ， 口 ) 而标号为9 g 的结点表示概念 ，9 ，) = ( 9 ) ，( 硼) 考虑集族： 毋g = = 4 e ；g 1 4 ”= 4 ， 鳓= 曰量材l = b ) 关于集合的包含关系，露g 和蔓k 成为偏序集容易证明：投影映射 研：颈g ，md 一既， 靠2 ：8 姆，m ，i ) + b 嚣， 都是序同构，而且有交换图： 9 颞g ，m d 二二二二二= = = = 础_ 鳓 图2 4 勇g 和8 嚣序同构 定理2 2 1 设( g ，md 是一个上下文，则甄g ， 厶d 是完备格且对于( 4 ， 马x “甄g ， 厶d ，( 4 ，马h 。，的上确界和下确界分别由下式给出： j 皂j 翰= j 皂j 罐nj d 釉 ，“的，呦= “化j 呦”，u j “动 三、f c a 的基本定理 设双g ，m ，d 是概念格 如下： 定义映射 y ：g _ + 颈g ，ma 、，g e g ，y ( r ) 鼍 g ) ”， g ) ，) ， v 所 厶p ( 炉= ( 所 ， 肼) 勺 引理2 2 2 设甄g ， 厶d 是概念格则v 窖g ，v 新 磊 g j 所铮y 回曼l l 伽) 定理2 2 3 ( 概念格基本定理1 ) 设( g ，j | i 厶乃是一个上下文，三= 颈g ，j i 磊 d 是对应的概念( 完备) 格，映射y ：g 江，l i ： 加工的定义如上则： ( 1 ) y ( g ) 在三中是并稠密的 ( 2 ) l l 在上中是交稠密的 1 0 ( 3 ) v g g ，锄mg ，聊耸y s p 咖) 定理2 2 4 ( 概念格基本定理i i ) 设工是完备格，g ，m 是集合，且存在单 调映射y ：g - _ + ，l l ：时j ，使得y ( g ) 在三中并稠密，i ic 岣在上中交稠密定 义关系? g 掰如下：y g g ，￥拼j j l 磊 g ，坍骨y s | l ( 哟 则同构于双g ，md 推论2 2 5 任何完备格三同构于概念格霸z ，工，9 一般地，若已知概念格的图形，x 8 ( g ，j l 以d 是一个元素( 标号) ，则根据 基本定理的证明，它对应着概念 似，翰= ( g g iy ( g ) 兰x ) ， 埘 ，i 工s u ( 脚) ) ) 例2 2 6 图2 3 太阳系的概念格中，位于中心( 没有写出标号) 的元素对应 于概念( 3 4 9 ， 研) 第三章概念格的生成算法 本章对概念格生成算法进行了一个概述，介绍了概念格的几种批处理式概念 格生成算法，并对其中的几种概念格生成算法进行了改进和实现 第一节概念格生成算法概述 生成概念格的过程实际上就是概念聚类的过程，对于同一批数据，所生成的 概念格也是唯一的也就是说，生成概念格不受数据或属性排列次序的影响，这 也是概念格的优点之一概念格的生成算法基本可以分为两类：批处理式算法和 增量式算法 批处理式概念格生成算法根据建格方式的不同可以分为三类，即，自顶向下 算法，自底向上算法和枚举法自顶向下算法首先生成格的最上层结点，然后逐 渐向下构造，比较典型的算法是b o r d a t 的算法自底向上算法则正好相反，它 首先生成格的最底层结点，然后逐渐向上扩展，典型的算法有c h e i n 的算法枚 举法是按照一定的顺序枚举概念格的所有结点，然后再生成对应的h a s 辩图，典 型的算法有q m t c f 的算法、n o 证邶的算法等 增量式算法又叫渐进式算法，它的基本思想是：将当前要加入的对象所具有 的属性集与概念格中原有概念的内涵求交，根据交集结果的不同采用不同的处理 办法典型的算法有g o d i n 算法等 第二节概念格的基本生成算法 本节介绍概念格的几种基本生成算法，其详细内容请参阅文献【3 】 性质3 1 给定上下文( g ，肘，d ，对任意a g ，能形成概念似”，4 ，) ( 或者 等价地，对任意召鸯协形成概念( ，) ) 定义3 2 设 甄g ，m ，j ) ，9 是一个概念格，取“j ，历) ，似2 ，助颈g ， m d ，当 2 ，助 “j ，b ，) 时，则称0 ，b ，) 是口2 ，历) 的父辈结点，也称? ， 助是，曰，) 的子辈结点 定义3 3 设 8 ( g ， 厶d ，9 是一个概念格，取似j ，历) ，似2 ，蚴颈g ， 以d ，当卅2 ，岛) 似j ，丑) 且不存在“，回颈g ， 磊d ，使得2 ，助 ， 动 q j ，b j ) 时，则称似j ，b j ) 是口2 ，助的直接父结点，也称似2 ，蚴是口，历) 的直接子结点对应于h 嬲s e 图上，若“2 劲是似，丑，) 的直接子结点，则他们 之间有连线 一、概念格生成算法l 算法1 利用上面的性质3 1 ，产生所有的概念，然后根据它们之间的父子 关系确定概念之问的序： 第l 步：对v 彳g ，生成所有； 第2 步；对第l 步得到的每个彳求出一”； 第3 步：根据集合父子关系画出概念格， 这种概念格的生成算法理论基础非常简单，直接根据定义就可以得出，然而 这种算法是生成概念格的最简单( 同时也是最低效) 的算法因为，如果一个上 下文有lg1 个对象，im 1 个属性，那么相应的格将可能包含2 吲或2 材个概 念，计算量相当大 二、概念格生成算法2 性质3 4 给定上下文( g ， 以d ，一g ，风批若口，回是概念，则： 4 = = ( u 。b 神= n 。口， 君= 4 = ( u 窖。苫) ，= n 弘， 算法2 根据上面的公式可以产生一个略加改进的算法如下： 第l 步：对v 所e 以生成所有m ： 第2 步；对b 做交n 。醴辨，： 第3 步：根据集合父子关系画出概念格 例3 5 根据上述算法，生成太阳系上下文所对应的概念格如下： a a d g 1 2 m a 图3 1 太阳系上下文对应的概念格 三、基于算法2 的改进的概念格生成算法 b e f 7 8 算法2 虽然对算法l 来说有了一点改进，但效率仍然是很低的，下面我们介 绍一种改进了的算法3 详细内容请参阅文献【3 】 算法3 是的理论基础是性质3 4 下面是算法3 的具体步骤： 第l 步：找出上下文( g ，md 中概念的所有外延 1 1 画出一个有两列的表，分别表示属性和外延开始时，属性的第一行 为空，外延的第一行为g 1 2 找出一个m m 使得埘极大( 不含在其它加中) 1 2 1 若集合m 不在外延列中。则将所，所7 作为新行添加到( 属性，外 延) 表中用集合彩与外延列中前面的所有集合傲交并将这 些交( 除去表中已有的) 依次加到外延列中，而属性列中相应 的位置暂时空缺 1 2 2 若集合m 已在外延列中，将加加到出现所的行所对应的属性 列上 1 3 从交叉表中删除肌下面的列 1 4 若交叉表中的最后一列已被删除，就找到了所有概念的外延( 即表中 外延列中的每个集合) ，然后跳到1 5 ；否则返回1 2 1 5 根据上下文，求得外延列中的每个集合对应的属性，停止 第2 步：画出对应的h 蜮图 根据集合父子关系画出概念格 这个算法我们已经编程实现，详细代码请参考附录l ，下面我们举个具体 的例子 例3 6 假设有如下的上下文： b r 砌瞻h a s - l 鹅 l j v 髂n 肼d d l 虻髂 m w a 懈 n 掣 b e a l 【 l i a i l c bd e l e 咖 w m g s w a 自a 邮m l i g i l t ( a ) ( b ) ( c ) ( d ) ( c ) ( o( g ) 0 0 a ) lb a t ， 2 e a 唔i c 3m k e y 4p 删6 s h 5 p g i l i n 6袖a f i 【 7l a n k l n 鼬 图3 - 2 一个给定的上下文 下图是例3 6 执行算法3 的程序得到的h 舔s e 图 图3 3 算浩3 生成概念格的h a s 辩图 第三节一种额的概念格生成算法 由对概念格生成算法的分类我们可知，算法3 属于批处理式算法的自顶向下 概念格生成算法算法3 里在求外延过程中，仍需对照上下文，操作起来很复 杂作为算法3 的对偶和改进，我们这里给出一种新的批处理式算法中自底向上 的概念格生成算法，只需要在算法开始时利用上下文得到初始数据，并且在画 h 图上进行了改进，利用求得的概念找出它们各自的直接子结点 算法分两部分：第一步，先求出上下文( g ， 矗d 的所有概念的集合甄g ， 厶d ；第二步，根据求得的顾g ， 以d 构造概念格，并画出相应的h a s 图 在介绍概念格的生成算法之前，我们先给出一些定义和记号 定义3 7 在概念格中，若概念叫，助到格中最大元的最长极大链的长度为 赫则称“，功是第层的格结点 此定义的迸一步推广，对任意概念似。切都可以定义它的父结点或子结点的 相对于似，的层数 定义3 8 设似，曰j ) 似，固( 似，b ，) s 似，助，若似，曰，) 到a ，研 的最长极大链的长度为j ( ，则称u j ，b d 是口，毋的第k 层父结点( 子结点) ， 由以上的定义，我们可以得到下面的性质： 定理3 9 设( g ， 厶d 是一个上下文， 颈g ， 厶d ，9 是( g ，麒d 的概 念格，则v g g ，g ，g ，) 是( ，岣的直接父结点，当且仅当从( ，加到g ， g ，) 极大链的长度为1 证明：根据第一节中极大链的定义和定义3 3 易得 性质3 1 0 双g ，md 和关系掣也构成一个概念格，并称烈g ，md ，! 是 颈g ， 以d ，9 的对偶 算法4 快速找出上下文( g ， 厶d 中的所有概念 第1 步：画出一个有im i + 1 行的表，记为表l ，用来存放结点 1 1 在上下文中按照行的递增顺序对每一个g g ，找出g ，依次把留，d 当成一个元素插到表l 的第l 肘i + l i i 行中，每行第一个被插 入的结点放在第一列，第二个放在第二列，依次类推，其中第行只 放结点c ， 力 1 2 检查每一行中结点是否有相同的属性，若有，把他们对象求并，只保 留相同属性里这个对象最多的结点，其他的从表中删除； 然后重新把该行的列结点重新插入； 把g ，极大的结点的集合记为d 第2 步：找出表l 中第一次出现结点的行数f ，从第f 行的第一个结点_ p f ( 户1 ) 开 始按如下方式进行遍历比较： 2 1 j ：l ，结点乃和本行后面的每个结点进行运算； 结点n 和本行下面每一行的每一个结点进行运算，直至结束，完成 n 的遍历运算； 2 2 完成乃( 1 ，c o u m ( 5 ，c 魄沪l ， ( 1 巧j l y i ) - 2 ； 对i l 膨、y i m 哪= 4 5 6 7 n 1 3 ；a ； 对f 肘、y ，i m 哪= 4 5 6 7 n 7 = 7 ) ，局= 7 ，肛 删鲥) ，c o i m t ( 7 ，卿l ， ( 1 巧l l y l ) = 2 ； 所以( 4 5 6 7 ，昭) 的直接子节点就是( 4 6 7 ，卯g ) 和( 4 5 ，c e g ) 第四章结论 本文首先对形式概念分析及其算法进行了综述，然后介绍了几种基本的概念 格生成算法，并简单比较了几种算法的优缺点 本文主要研究批处理式概念格生成算法，重点做了以下几点工作： 1 在简单概述前人一些算法的基础上，实现了文中介绍的算法3 ，得到概念 格及相对应的 i a s 图 2 在分析和研究已有概念格算法的基础上，构造并实现了一种自底向上的 批处理式算法，在得到概念格后，我们又构造出一种基于所得概念格的画h 弱 图的算法 参考文献 1 】n p a s q _ i l i y b 枷d e ，t 伽1 1 i l ，l l a l d l a l ，e 伍c i c n tm i n 吨o f a s s o c i a t i m l 船 璐i i l gd o s e d 沁m s c tl a t d c 髂，曲r m s y s 劬s2 4 ( 1 ) ( 1 9 9 9 ) 2 5 4 6 圆m 。j z 描，c 。t h o ，s c a l a b l ea l 鲥也黜f o r a s s o c i a 主i 衄玎l i n i n g ，i e 髓t 黜s k w l e d g cd a t ae n g 1 2 ( 2 ) ( 2 0 0 0 ) 3 7 2 - 3 9 0 3 】b g a l l _ 吨& w i l l e f o m a lc o n c 印t a n a l y s i s m 础锄a d c a lf o 吼d 砒i o m s p r j n g c r ，b c r l i l l ( 1 9 9 9 ) 【4 】b ad a v e y h a p r i e s t l y i 蛐刚u c t i o nt ol a n i c e s 锄do r d s e c o n de d i t i o n c 锄b f i d g cu i i i v e 瑙i t yp r e 船( 2 0 0 2 ) 【5 】郑崇友，樊磊，崔宏斌f r a m e 与连续格( 第二版) 首都师范大学出版社， 2 0 0 0 9 【6 】gb i 岫。位l 砒i i c et h e 哪a m sc o l l o 椰啪m i 删。屿v 0 1 2 5 ，1 9 4 0 【7 】& g o d i n e ta l ，l e 锄i n ga l g o d t h l 璐璐i n gg a i o i sl 雒i c es t r u c n 聪p r o c 救培o f l l l ei e e ei n t e 】m a t i o n a lc o n f 醯o nt o l sf o ra ls 缸j o ，g a ，1 9 9 l ， p p 2 2 - 2 9 嘲rw i l l e ，r e s 仃t u r i l l gl a 出n l r y ：匝a p p r _ o hb 勰c do nh i 蹦玳啦鹤o f n c 印缸h ：i ，剐v a l ( e 正) ，0 嘲即e d 孵坞j 己c i d e l ，d o r d r e c h t ，b o s t o 呜1 9 8 2 ， p p “5 - 4 7 0 【9 】p h i t z l 盯a n dg - q 。z h a n g ac 绷铭i 觚c l o s e dc a l e g o r ) ro f a p p r o x i n 嵋b l e 砌嵌叫 s 缸l l c 咖璐hk - e w b l 甄h d p f e i 自f e r ，锄dh s d e l u 韶c h ，e d i t 嘟p l 饿蟹e d i n 笋 o ft h eh l t e m a t i 如a lc 伽庙r o nc 伽c e p t u a ls 协l 曲】r 鸭h u n t s v i u e ，舢曲匝1 a u s 气k t u r e n o t 鼯i n c o m p u t e r s 西哪吗p a g e s1 7 0 1 8 5 s p 血g 瑚y 2 0 0 4 【1o 】u m f a y y a d ，gp i a t i 如h a p i m 锄dp s m y t h f r o md a t am h l i n gt o k n o w i e d g ed i o v e 哆a no v e r v i e w a d v 锄c i n 幻1 0 w l e d g ed i o v e f y 锄d d a l a m i n i l l g a a a m n p 陀嚣，c a i i 如哪i a ，1 9 9 6 ，8 3 - 1 1 5 【l l 】z l l a n 岛g - q ，s h 钒g a p p r o x i l a b l ec 唧t s ，c h us p 嘲s ，di n j b m a t i s ) ，s t e 脚hd c 跗v a 锄d p 均n ( g m s t e d i t o 舟) ，s p c c i a l i s s 衄c h us p a c e s 锄d a p p l i c 撕o ，n 珂觚da p p l i c a t i o 璐o f c 疵9 0 f i e s ，a c i 删 【1 2 】b 嘶锄i nc 。p i e r ，b 勰i cc a l e _ 9 0 r yt h t y1 o rc o m p m 盯s c i 髓吐s 奴t h em r r p 阳鹦1 9 9 1 【1 3 】a i l d r e aa ! l p e i t i ，g i l 辩p p el 肼1 9 0 c 蹴g 嘶髂1 卯嗒a n d 乳叫：t i l r 瞄1 1 1 cm i t p 佗s s 1 9 9 1 1 4 】r o i 【i am i s s a o l l i ，r o b 酿g o d i n s e a r c hf o rc o n 哪t s 觚dd e p e r 池n d 舔i n d 锄i b 弘e s r o u g hs e t s ，丘l z 巧臼，锄di m o w l e d g ed i s c o v e r y ，p r o c d i i l g so ft h e h l t c m a t i a lw o r k s h o po nr ( m 曲s e t sa n dk j l o w l e d g cd i s c i 眦r y ( r s k d 9 3 ) ， b 锄甄a l b e r t a ，c 柚a d a ，1 2 1 5o c t o b 1 9 9 3 1 6 - 2 3 【1 5 】r 0 b c r tg o d i n ，r o k o am i s s a 0 i l i a ni 删n t a ic 伽c e p tf 0 彻a t i o na p p r o a c hf o r l 既r 珏i n g 鼬nd a 协a s 瞻髓e 哦t i c a lc o m p u 眩s c i e n c e1 3 3 ( 】9 9 4 ) 3 8 7 _ 4 1 9 【1 6 】胡可云，陆玉昌，石纯一概念格及其应用进展清华大学学报( 自然科学版) ， 2 0 0 0 ，4 0 ( 9 ) 7 7 8 1 【1 7 】o o 出n m n i hm i n 删q w r m i 蝴砌d e s i 趴o f d 鹚h i e 糟r c l l i e sb a s c d o no 眦p t ( g a l o i s ) l 甜妇1 h e o r y 觚da p p l i 础0 no fo b j e c ts y s t e 吣，1 9 9 8 ， 4 ( 2 ) ，1 1 7 1 3 4 【1 8 】j c o l e ，p 抛e l ( 1 岫d a 即l i c 硝o f f o 珊a lc o n c e p ta l l a l y s i st oi i l l l b r i n a t i o n r e 嫡c c a l 璐i n gah i e 瑚c b j c a u y 跏u c t 瞰e dn e s 舢s b 翊苎垒i 监墨q 照j 邕p 翘四型璺q ! 鲤鱼鱼亚p 堕坌坌! i 鲤h 砌 1 9 】l e fe l ( 】啦d r i c h 蕊c o 】e ak n o w l e d g er 印聆s 蜥鲫自叮i n 】b m a t i 彻f i h e 曲g u s i n gf o 】皿a lc o n c e p ta n a l y s i s b 堑卫；礁錾竖i 匹：p 坠：鲤型3 2 鱼丝：照丝! 【2 0 】0 r e g o rs n e i 血1 9 s o f t w a 旭k g i l 蛾：r i l l l gb 蠲e d 蚰c c e p t l a 坻c 璐 塾蛰巳；! ! i 丝墨垒笪i 壁套墅! 四! ! f 曼垒曼i 堑娶翻丛! 墅幽醒塾! 虫! 【2 1 】j t 只b o 蛾c a i c i i lp r a 士i q 雌d i lh e i l i i sd eg a l o i sd u c o n _ e s p o n d c n c e - m a l s c i h 衄，1 9 8 6 2 4 黜咖，1 9 9 6 ，3 1 4 7 f 2 2 】m c h e 虹触g o m h m 如r e c h e r 曲6d 嚣s o l 净m a 扭i c c sp 糟m i e r 嚣d 岫em a 砸c e b i l l l m a 也s o c s i c r o l 蚰卸i e1 3 ( 6 1 ) ，1 9 6 9 ，n o 1 ，2 1 2 5 【2 3 】a g u 鲫o c h e ，c o n s t r u c t i o nd u 雠i l l i sd eg a l o i s ，m 劬，s c i ，h u i i l a 妇s1 0 9 ， 描 4 l 一5 3 【2 4 】n o 面n e l ，r 唧【觚d o a 触a 1 9 0 f i 岫l f o r 撕l d 吨l 砒i s 【a 】蛐p c 鲫p u 蛆d o r l a lg m p hn e o r y 柚dc o m b i n a t o r i c s 【c 】c t o r i a ，c a m d a m a y 1 9 9 9 【2 5 】i 乙g 0 d j n m i s 鞠o l l i ，h a l a o l l i h c r 锄c n t a lc o n 唧tf o 册撕a 1 9 0 r i t l l i m b a s e do n 删o i s n c c p t ) l a t t i 淄 c o m p i l 伽h 她l l i g a m ， 1 9 9 5 ，1 1 ( 2 ) ， 1 1 7 1 3 4 【2 6 】c c a i p i n e 峨gr o m 孤o g a l o i s ：趾o m 卅t b e o r e t i ca p p r o a c ht oc o n c e 肌l a l c l 蛐g ，i n ：p r o c e i e d i n g si c m l ，m a c h i n el 锄m 舀m o r g ml ( a u f h l 锄 p u b l i s h e r s ，1 9 9 3 ，p p 3 3 枷 【2 7 】h o t b ，a n 印p f o a c h t oc o n c e p t f o 锄a l i o n b a s e do n f o m a lc o e p t 锄a l y s i s 阴 i e i c e1 姗s ，h l f b 彻撕o n 锄ds y s t e i n s ，1 9 9 5 ，e 7 8 d ( 5 ) ：5 5 3 - 5 5 9 【2 s 】谢志鹏，剃宗田，概念格的快速渐进式构造算法计算机学报，2 0 0 2 ，2 5 ( 5 ) 4 9 0 4 9 6 【2 9 】乔胜