（基础数学专业论文）基于分层结构的概念格构造算法的研究.pdf

摘要 形式概念分析是一种基于格结构的数据分析方法，由w i l l e 教授于1 9 8 2 年 首次提出自形式概念分析理论被提出以来，它以其知识表示的直观、简洁、完 备等特点而受到研究者的广泛关注，已经在软件工程、图书馆和信息科学、数据 挖掘等诸多领域得到了广泛的应用 在概念格的研究和应用中，关于概念格的构造算法始终吸引着众多学者因 为在所有应用形式概念分析进行数据分析的系统中，都要面临着如何从一个给定 的形式背景得到对应概念格的问题，所以一个有效的构造概念格的算法是极其重 要的在形式概念分析中，构造概念格的算法主要分为批处理式概念格生成算法 和增量式概念格生成算法前者主要处理固定的形式背景，而后者除了可以处理 固定的形式背景，还可以处理动态的形式背景，相比而言，增量式概念格生成算 法的应用领域更广，也显得更为重要 本文主要研究基于分层的概念格的生成算法，重点做了以下几点工作： 1 讨论了基于分层的概念格的相关性质，根据这些性质构造了一种基于 分层的批处理式算法，不仅找到所有的概念，同时生成相应的h a s s e 图 2 研究了约简形式背景的相关性质，讨论了约简形式背景和分层的概念 格生成算法的关系 3 研究了动态背景对分层概念格的影响，并在l 和2 的基础上提出了一 种基于分层的增量式构造概念格生成算法，并进行了实验，与g o d i n 算法进行了 性能比较，得到了较好的结果 关键词形式概念分析，概念格，批处理算法，增量式算法，基于分层的概念格 a b s t r a c t f o r m a lc o n c e p ta n a l y s i si sat h e o r yo fd a t aa n a l y s i sw h i c hi d e n t i f i e sc o n c e p t u a l s t r u c t u r e sa m o n gd a t as e t s i ti se m e r g e df r o mw i l l e se f f o r t st or e s t r u c t u r el a t t i c e a n do r d e rt h e o r yi n19 8 2a n dh a ss i n c et h e ng r o w nr a p i d l y t h ef c am e t h o do f f o r m a ld a t aa n a l y s i sh a ss u c c e s s f u l l yb e e na p p l i e dt om a n yf i e l d s ，s u c ha ss o f t w a r e e n g i n e e r i n g ，l i b r a r ya n di n f o r m a t i o ns c i e n c e ，d a t am i n i n g ，a n do t h e r s t h eg e n e r a t i o no fc o n c e p tl a t t i c ep l a y sa ni m p o r t a n tr o l ei nt h ea p p l i c a t i o n so f c o n c e p tl a t t i c e g e n e r a l l yt h ea l g o r i t h m sf o rb u i l d i n gc o n c e p t l a t t i c ea r ed i v i d e di n t o t w om a i n c a t e g o r i e s w h i c hw ec a l l e db a t c hc o n s t r u c t i o na n di n c r e m e n t a l c o n s t r u c t i o n t h eb a t c ha l g o r i t h m sa reu s e df o rb u i l d i n gc o n c e p tl a t t i c ew h o s e f o r m a lc o n t e x th a db e e ng i v e na n dt h ea l g o r i t h m so fi n c r e m e n t a lc o n s t r u c t i o na r e m o r ec o n v e n i e n tt h a nb a t c ha l g o r i t h m sw i t hd y n a m i cd a t a t h i st h e s i sf o c u s e so nt h e a l g o r i t h m sb a s e do nt h e h i e r a r c h i c a lc o n c e p t l a t t i c e t h ef o l l o w i n gi so u rm a i nr e s e a r c hw o r k s ： 1 h i e r a r c h i c a lc o n c e p tl a t t i c ep r o p e r t i e sa r ed i s c u s s e d a c c o r d i n gt ot h e p r o p e r t i e s ，an e wb a t c ha l g o r i t h mi sp r e s e n t e dt oc o n s t r u c tt h ec o n c e p tl a t t i c ea n d c o r r e s p o n d i n gh a s s ed i a g r a m 2 w eh a v es t u d i e dc o n c e p tl a t t i c er e d u c t i o n ，g o ts o m er e s u l t sa n dd i s c u s st h e i m p a c to f t h ea l g o r i t h mb a s e do nh i e r a r c h i c a lc o n c e p tl a t t i c ew i t ht h e s er e s u l t s 3 t h ei m p a c t so fh i e r a r c h i c a lc o n c e p tl a t t i c ew i t hd y n a m i cd a t aa r ed i s c u s s e d a n dan e wi n c r e m e n t a la l g o r i t h mi sp r e s e n t e dt oc o n s t r u c tt h ec o n c e p tl a t t i c ea n d c o r r e s p o n d i n gh a s s ed i a g r a m t h ea l g o r i t h mi se x p e r i m e n t e da n dc o m p a r e dw i t h a l g o r i t h mg o d i n ，t h er e s u l ts h o w s t h a tt h ea l g o r i t h mp e r f o r m a n c ei ss u p e r i o r k e yw o r d sf o r m a l c o n c e p ta n a l y s i s ，c o n c e p tl a t t i c e s ，b a t c ha l g o r i t h m ， i n c r e m e n t a la l g o r i t h m ，h i e r a r c h i c a lc o n c e p tl a t t i c e 中央民族大学研究生学位论文作者声明 本人声明：本人呈交的学位论文是本人在导师指导下取得的 研究成果对前人及其他人员对本文的启发和贡献已在论文中作 出了明确的声明，并表示了谢意论文中除了特另j j ；d n 以标注和致 谢的地方外，不包含其他人和其它机构已经发表或者撰写过的研 究成果 本人同意学校根据中华人民共和国学位条例暂行实施办 法等有关规定将本人学位论文向国家有关部门或资料库提交， 允许论文被查阅和借阅 作者签名： 廛笪查垒日期：二堕生年互月丑日 第一节本文的研究背景 第一章引言 形式概念分析理论以数学化的概念和概念层次为基础，是格理论的一个分 支，由w i l l e 教授于1 9 8 2 年首次提出【l 】它作为一种有效的数据分析方法，已 经在面向对象设计2 1 、数据挖掘【3 4 ，5 ，6 ，7 ，8 ，9 1 、信息检索【1 0 , 1 1 】、信息过滤【12 1 、软件工 程【1 3 1 、w e b 菜单的层次结构设计f 2 l 】等方面得到了应用 在传统的哲学范畴罩，概念由其外延( e x t e n t ) 和内涵( i n t e n t ) 所确定，概念的外 延由属于该概念的所有对象构成( 例如：读者属于活着的人) ，而概念的内涵是概 念的所有对象共同分享的属性( 例如：活着的人都需要水来维持生存) 在形式概 念分析中，概念是在形式背景的基础上进行定义的一个形式背景是指一个三元 组( g ，m ，d ，其中g 代表对象的集合，m 代表属性的集合，1 c _ g x m ( 从g 到 m 的一个二元关系) 形式背景( g ，m ，d 中的概念是一个对似，b ) ，它是按以下 规则定义的：彳g ，曰m ，并且满足b 中只含有a 中全体对象所共有的那些 属性，彳中包含的恰好是分享b 中所有属性的那些对象 概念格是形式概念分析的核心数据结构，概念格具有知识表示的直观、简洁 和完备等特点，与其对应的h a s s e 图实现了对数据分析结果的可视化，并且h a s s e 图中的结点体现了概念内涵和外延的统一，非常适合于用于知识发现1 1 4 , 1 5 , 1 6 , 17 署 规则提取【博j 自从形式概念分析理论被提出以来，无论是在理论方面的研究还是在实际生 活中的应用，都取得了很大的成果在理论方面，在德国数学家r u d o l f w i l l e 在 1 9 8 2 年把它的引入的很长一段时间里，我们一般研究的都是有限的形式背景， 近年来在无限的形式背景和可逼近概念的研究也取得很多成果【1 9 ，2 0 2 1 1 在所有应用概念格方法实现数据分析的系统中，都要首先从形式背景中生成 概念格及其对应的h a s s e 图，因此概念格的构造是进行分析系统设计的基础国 2 内外研究人员已经提出了很多算法，这些算法主要分为两类：批处理算法 【2 2 2 3 ，2 4 2 5 ，2 6 2 7 ，2 8 】和增量算法【1 7 , 2 9 , 3 0 ，3 1 3 2 3 3 1 批处理式算法根据其生成格的不同方法， 可以分为自上向下算法、自下向上算法、枚举法等批处理式算法中比较著名的 有b o r d a t 算法【2 2 1 、c h e i n 算法1 2 3 】、g a n t e r 算法和n o u r i n e 算澍2 5 1 等，在此基础 上，国内外科研工作者还开发出了许多衍生改进的算法【2 7 ，2 8 1 ，但是大部分算法只 是求出了概念，并没有在找出概念的同时生成相应的h a s s e 图增量式算法主要 处理动态的形式背景，其中比较著名的是g o d i n 的算法【2 9 】、c a p i n e t o 算法【1 7 】和 t b h o 算法【3 0 】等 第二节本文的工作 本文主要研究基于分层的形式概念分析，重点做了以下三个方面的工作 1 讨论了基于分层的概念格的相关性质，根据这些性质构造了一种基于 分层的批处理式算法，不仅找到所有的概念，同时生成相应的h a s s e 图 2 研究了约简形式背景的相关性质，讨论了约简形式背景和分层的概念 格生成算法的关系 3 研究了动态背景对分层概念格的影响，并在l 和2 的基础上提出了一 种基于分层的增量式构造概念格生成算法，并进行了实验，与g o d i n 算法进行了 性能比较，得到了较好的结果 3 第二章预备知识 形式概念分析是基于序理论的，尤其是基于完备格理论的，因此本章的主要 内容就是介绍一些相关的基础知识本章分为二节，第一节概要介绍一些基本的 序和格理论方面的知识，第二节概要介绍一些形式背景、概念和概念格方面的一 些基本知识和结论，详情请参考各节中分别引用的文献 第一节序和格基本理论 在本节中，我们对于序和格理论进行了简单的回顾，这样有助于读者阅读本 文由于篇幅有限，更多知识请参考文献【1 ，3 4 ，3 5 ，3 6 定义2 1 集合m 和之间的一个二元关系尺是有序二元组( m ，以) 的集合， 其中m m ，n n ，即r m n ，( m ，n ) r ，也经常写作m r n 如果m = n ， 则称尺是m 上的二元关系例如，r f y ) = x 2 是集合欠上的一个二元关系此外， 还用厅1 表示的逆关系，即 1 1r jm 年j1 1 7rn 定义2 2 设! 是集合p 上的一个二元关系，且满足下列条件：v x ，y ，z p ， ( 1 ) x x ( 自反性) ； ( 2 ) x y ，y z 兮x5 z ( 传递性) ； ( 3 ) xsy ，y x 号x = y ( 反对称性) 则称为p 上的一个偏序( 关系) ，一个集合p 及其上的偏序形成的有序二元组 ( 户；) 称为偏序集 在不至混淆的情况下，对( p is ) 也经常简记为p 例2 3 4 ( 1 ) 设m 是任一个集合，若其上的偏序关系就是普通的相等关系，则= ) 是一个偏序集，并且是一个平凡的偏序集 ( 2 ) 设集合肘是全体自然数的集合n ，若其上的偏序关系是n l n 2 ，当且仅 当n l 整除n 2 ，则( 闲；) 是一个偏序集 定义2 4 设尸是个偏序集，x ，y p ，称x 被y 覆盖( 或者y 覆盖x ) ， 如果x y 且不存在z p 使得x z y 记为x _ y 定义2 5 设p 是一个偏序集，x ，y p ，如果有x 少或者有ysx ，称x ， y 是可比较的，否则称为是不可比较的如果p 的一个子集中任何两个元素都是 可比的，则称这个子集为链 例2 6 实数集欠在通常的s 关系下形成一个偏序集，并且这个偏序集是一 个链，因为对于所有的x ，y 欠，或者有x y 或者有y z 定义2 7 设尸是一个偏序集，工，y p ，由x 到y 的一个长度为n 的极大 链指的是序列z = x 0 x l x 2 _ 而= y ，x n p 命题2 8 如果偏序集尸有限，x y 当且仅当在x 和y 之间存在一个有限 链 有限偏序集p 都可以用一个h a s s e 图来表示p 的元素是h a s s e 图中的点， 用小圆圈代表如果x ，y m 且x y 时，则对应x 的圆圈应画在对应y 的圆圈 的下方，并用一条线段把这两点连接起来 爪vii 八v 卜 图2 14 个元素的偏序集的所有可能的h a s s e 图 h a s s e 图也可以表达无限偏序集，即仅画出一些典型的有限部分来说明偏序 的构造原理 图2 2 一个无限偏序集的h a s s e 图 定义2 6 设( 尸；) 是偏序集，则妒：s o ) 也是一个偏序集，其中对x ，y p ， x o y 牟净y 工 ( p ；o ) 称为p 的对偶，并记为尸0 ( 尸；o ) 的h a s s e 图可以由( p ；s ) 的h a s s e 图做水平反射得到 定义2 9 设( p ；) 是一个偏序集，对于x p 与x c _ p ，定义： t x = y pix y ) h 2 ( y p iy x 似= y pim 咒使得x 少)s x = y pi 丑z 使得y x ) 一个集合咒如果x = 似= 蚜) ，那么x 称之上集( 下集) 定义2 1 0 设尸和q 是偏序集，妒：p - q 是一个映射 ( 1 ) 若y x ，y p ，x y 号妒妒) ，则称妒为保序映射； ( 2 ) 如果妒还满足妒 ) 妒( y ) 兮x y ，称妒是序嵌入的，这时妒必然是单射一 个双射的序嵌入称为序同构 定义2 1 1 设p 是偏序集，么尸，x p ( 1 ) 若y a a ，a xos 口) ，则称工为么的一个上界( 下界) ( 2 ) 若v y p ，ys 石g5 力，则x 称为p 的最大元( 最小元) ( 3 ) 若集合 x 没有异于x 本身的其它上界( 下界) ，则称x 是p 中的一个极 大元( 极小元) ( 4 ) 若x 是a 的全体上界( 下界) 的集合中的最小元( 最大元) ，则称z 为彳 6 的上确界( 下确界) ；a 的上确界记为v a ，a 的下确界记为a a ( 5 ) 若y x ，y p ，工vy0a 力都存在，则称p 是v 一半格( 一半格) ( 6 ) 若p 既是v 半格又是a 一半格，则称p 是格 ( 7 ) 若p 的任何子集都有上确界和下确界，则称p 是一个完备格 定义2 1 2 设p 是偏序集，q 尸若y x p ，了s q ，使得石= v s0 = a s ) ， 则称q 在尸中是并稠密( 交稠密) 的 命题2 1 3 设p 是偏序集，彳，b p ，a f p ( i ，) 则： ( 1 ) 彳bjv a v b ，2 4 a b ： ( 2 ) v a = v ( s a ) ，a a = 人( 似) ； ( 3 ) a = uf ，彳fjv a = v f “v 彳f ) ；a = ui i a ija a = a i ，( 八爿f ) 定义2 1 4 设x 是集合，z 是x 的子集族若z 对集合的任意交封闭，即： v i i i ，a i z 毒n 佗i a f z ， 则称z 是( x 上的) 一个闭包系统集族z 中的元素称为闭集或包集若允许指 标集j 是空集，取集x 本身为空集族的交 给定任意子集彳x ，集合n i b zla b z ，易知这是z 中包含a 的最 小集合，称为彳的闭包或者包 命题2 1 5 任何闭包系统z 关于集合的包含关系称为一个完备格；反之， 每一个完备格都与一个由闭包系统的所有闭包形成的格同构 定义2 1 6 ( g a l o i s 连接) 令妒：p q ，砂：q p 是两个偏序集( 尸；) ， ( q ；) 之间的映射，如果满足： ( 1 ) p t - h e n di f e n d i f ； c i 】 - h ：l i x ( h ) i i _ i ) ； c l a s sp a i r si nb u c k e t sw i t hs a m ec a r d i n a l i t y o f t h e x s e t s ) c 【i 】 o ； i n i t i a l i z et h ec s e t s ) t r e a te a c hb u c k e ti na s c e n d i n gc a r d i n a l i t yo r d e r f o ri ：0t om a x i m u mc a r d i n a l i t yd o f o re a c hp a i r hi nc i i fx ( h ) f ( x 宰) ) t h e n m o d i f i e dp a i r ) a d dx 宰t ox ( h ) ； a d dht oc i ； i fx ( h ) = f f x 木) ) t h e ne x i ta l g o r i t h m e l s e o l dp a i r ) i n t h ： m o d i f ye d g e s f o r j ：0t ol l i n t l l 一1 f o re a c hh a c j 】 i fx ( h a ) ci n t h ai sap o t e n t i a lp a r e n to fh n ) p a r e n t h n e n di f e n di f e n d f o r e n df o r ： i fi n t = p ( x 木) ) t h e ne x i ta l g o r i t h me n di f 1 8 o 1 2 3 4 5 6 7 8 9 0 l 2 3 4 5 6 7 8 9 o l 2 f 3 4 5 6 7 8 9 o l 2 1 2 3 4 5 6 7 8 9 1 1 1 l l l 1 1 1 l 2 2 2 2 2 2 2 2 2 2 3 3 3 【3 3 3 3 3 3 3 4 4 4 4 3e n di f 4 4e n di f 4 5e n d f o r 4 6e n d f o r 4 7e n di f e n d a d d g o d i n 算法的具体内容请参阅 2 9 】 第三节基于分层的概念格生成算法的研究 文献 2 7 ，2 8 ，3 3 d ? 提出了一类基于分层的概念格生成算法，但这些算法基本 上都是两部分，生成概念的集合和画出相应的h a s s e 图是分开实现的，文献 3 3 】 的算法没有找到跨层的连线，这样没有很好的利用到分层概念之间的联系特 点本节讨论了概念格分层的相关性质，根据这些性质提出了一种新的构造概念 格的算法，不但找到所有的概念，同时生成相应的h a s s e 图，然后讨论了形式背 景约简的相关性质，并结合分层构造概念格的算法进行了探讨，在本节的最后， 讨论了如何利用分层的特点构造基于分层的增量式概念格生成算法 一、一种基于分层的构造概念格的算法 定理3 2 设 是一个概念格，取i ，b i ) ，似2 ，b 2 ) n g ， m ，d ，i ，b 1 ) 是( a 2 ，3 2 ) 的直接父节点的充分必要条件是：或者从么2 到彳i 的 极大链长度为l ，或者从b l 到占2 的极大链长度为1 定义3 3 t 2 8 】设 是一个概念格，a ，召) 劣( g ，m ，d ， 若似，b ) n 格中最小元( ，彻的最长极大链的长度为m 则称( a ，b ) 是第层 的格结点 定义3 4 t 2 8 】设似l ，b 1 ) 似，b ) ( 似l ，b 1 ) 似，b ) ) ，若似i ，b i ) 到，b ) 的最长极大链的长度为k ，则称似1 ，bz ) 是似，b ) 的第k 层父结点( 子结点) 定理3 5 设，动( ，力，似，功甄g ，m ，d ，毋) ( ，力是似，b ) 的子辈节点，则： 1 ) v j 山bcb ji ：t n j ，毋= 召； 2 ) v j j ，4c a r u j - ，4 = a 1 9 证明：由子辈节点的定义2 3 3 知，动( ，刀似，b ) ，即v j ，bc 毋， 4 c a ，因此有n ，马= 曰；而似，动( ，力，似，b ) e e 男( g ，m ，d ，所以a = ， 4 = 彰，由命题2 2 2 中( 5 ) 可得a = b 7 = ( n j ，b j ) 7 = u j ，彰= u j - ，4 ，即u ， ，彳，= a ，证毕 定理3 6 给定形式背景(