（控制理论与控制工程专业论文）概念格分布处理及其框架下的知识发现研究.pdf

上海大学博士学位论文 摘要 概念格以其良好的数学性质己成功地应用于知识发现等诸多领域，但由于概 念格自身的完备性，构造概念格的时间复杂度一直是影响形式概念分析应用的主 要障碍。概念格应用的前提是概念格的构造。现在概念格的渐进式构造算法表现 出了更强的生命力和适应性。但目前基本上都是属于基于对象的渐进式算法，而 基于属性的构造算法未见报告。实际上，形式背景中数据的变化应该包括两个方 面：一是对象的增减，二是属性的增减。增加属性可能使原来不能区分的对象能 够区分，删除属性就可能使原来属于不同类的对象变为同一类。通过对概念格中 概念之间的相互关系的了解，和对象和属性之间相互关系的研究，本文提出并实 现了基于属性的概念格构造算法，特别是基于属性的渐进式生成算法。它不仅为 概念格的生成提供了一种新的方法，而且解决了在己构造好概念格的前提下，增 加属性所带来的概念格更新问题，另外，它也为分布式存储的形式背景的概念格 横向合并提供了基础。 随着处理的形式背景的增大，构造概念格的时空复杂度也会随着急剧增大。 研究采用新的方法和手段来构造概念格，就成为概念格研究的主要内容之。现 在已经提出的构造概念格的多种算法基本上是针对单个概念格的。采用分治策略 来构造概念格是解决这一问题的有效途径。概念格的分布处理就是通过形式背景 的拆分，形成分布存储的多个子背景，然后同时构造相应的子概念格，荐由子概 念格的合并得到所需的概念格。 由于概念格是其形式背景中的概念间关系的表现形式，它和对应的形式背景 是一一对应的。因此，对概念格的分布处理必然涉及到形式背景的拆分、合并等 处理。本文从形式背景的并置和叠置出发，定义了两种类型的形式背景和概念格； 并对不一致背景的处理进行了研究：证明了横向合并的子形式背景的概念格和子 背景所对应的子概念格的横向并是同构的；结合子概念格中概念间固有的泛化一 特化关系，继承已有的概念格渐进式构造的算法，并对其进行改造，形成能满足 多个子概念格合并处理要求的算法。 数据挖掘是自动从数据中提取出人们感兴趣的潜在的可用信息和知识，并将 提取出来的信息和知识表示成概念、规则和模式。关联规则是发现知识的主要形 式。提取关联规则的主要步骤是频繁项集的获取，而一个事务数据库中频繁项集 的数量往往很庞大，从频繁项集中提取的规则就会很多，且存在大量的冗余。为 了缩减频繁项集的数目同时也不丢失有用信息，现在采用用频繁封闭项集来提取 最小无冗余的关联规则。 v 上海大学博士学位论文 本文通过对现有利用频繁封闭项提取规则算法的仔细研究和分析，结合概念 格的特点，对基于概念格提取最小无冗余关联规则进行了较深入的研究。为了便 于提取最小无冗余关联规则，定义了量化封闭项集格，发现了提取最小无冗余关 联规则的关键是找出格中每个节点的项集所对应的同交易的频繁项集集合中的 最小项集的集合，并给出采用幂集和差集两种方案分别获取该最小项集的集合 s l i t 的算法；给出了从量化封闭项集格直接提取最小无冗余的关联规则的算法。 为了进一步减少所提取规则的数量，以满足用户的特定需要，本文还提出了全局 简洁关联规则的概念，并给出了利用概念格提取全局简洁关联规则的算法。 目前研究关联规则提取的工作很多，但研究规则的更新的工作相对较少。实 际上，规则的更新问题和规则的提取问题一样，也是知识发现研究的重要环节。 本文为了实现对最小无冗余的关联规则的更新，对量化封闭项集格的结构作了进 一步的扩充，提出了量化规则格，实现了在概念格更新的同时，对最小无冗余关 联规则所对应的最小项集集合s l i t 的更新。由于量化规则格和格节点对应的具 有相同交易集的最小项集是渐进生成的，因此，它非常适合于从动态数据库中提 取最小无冗余的关联规则弗且可方便地实现规则的渐增更新。 利用概念格的分布处理，把形式背景进行拆分，分别构造相应的部分概念格， 然后进行部分概念格合并，得到完整概念格，再提取出相应的关联规则是从概念 格中获取知识的一种有效手段：同样，先从部分概念格中分别提取出规则，然后 直接进行规则的合并处理，也是获取知识的一种更直接更有效的手段。本文也在 这方面做了一定的探索，分别给出了其框架图，并对部分规则集如何核查其在全 局数据库中的有效性和最终有效规则的集成等问题做了一定的研究，并给出了简 单实例以验证其正确性。 关键词：概念格，形式背景，部分格，并置和叠置，分治策略，频繁封闭项集， 同交易项集，最小无冗余规则，简洁规则，量化封闭项集格，量化规则格，部分 有效规则，最终有效规则 v 1 上海大学博士学位论文 a b s t r a c t t h ec o n c e p tl a t t i c e sw i t ht h ef a v o r a b l em a t h e m a t i c p r o p e r t i e s h a v e b e e n s u c c e s s f u l l ya p p l i e di nal o to ff i e l d ss u c ha sk n o w l e d g ed i s c o v e r y , b u tt h et i m e c o m p l e x i t yo fb u i l d i n gc o n c e p tl a t t i c ei s af a c t o rr e s t r i c t i n gt h ea p p l i c a t i o no ff o r m a l c o n c e p ta n a l y s i sf o rt h ec o m p l e t e n e s so fc o n c e p tl a t t i c e t h ec o n c e p tl a t t i c e c o n s t r u c t i o ni sap r e m i s eo ft h ea p p l i c a t i o no ff o r m a lc o n c e p ta n a l y s i s ( f c a ) a t p r e s e n t ，t h ei n c r e m e n t a lf o r m a t i o na l g o r i t h mo fc o n c e p tl a t t i c eh a sb e h a v e ds t r o n g v i t a l i t ya n df l e x i b i l i t y m o s to f s u c ha l g o r i t h mi so b j e c t b a s e da p p r o a c h i n g a l g o r i t h m ， w h i c hi sb a s e do na d d i n go b j e c t sg r a d u a l l yi n t ot h el a t t i c eb e i n gf o r m e d ，b u tt h e a t t r i b u t e b a s e da l g o r i t h mh a sn o tb e e nr e p o r t e d h o w e v e r ，t h ec o n t e x tv a r i e si nt w o d i r e c t i o n s ：o n ei si no b j e c t s ，t h eo t h e ri si na t t r i b u t e s t h eu n d i s t i n g u i s h a b l eo b j e c t s c a nb ed i s t i n g u i s h e da st h ei n c r e a s i n ga t t r i b u t e s a n dt h ed i s t i n g u i s h a b l e o b j e c t s b e c o m et h es r n l ec a t e g o r ya st h ed e c r e a s i n ga t t r i b u t e s t h i sd i s s e r t a t i o ns u g g e s t sa d i f f e r e n ti n c r e m e n t a l a l g o r i t h m o f c o n c e p t l a t t i c e c o n s t r u c t i o n ，w h i c hi s a t t r i b u t e b a s e d ，i e ，t h ea l g o r i t h mi sb a s e do ni n c r e a s i n ga t t r i b u t e s d u r i n gt h e c o n s t r u c t i o np r o c e s s i tn o to n l yp r o v i d e san e wa p p r o a c hf o rb u i l d i n gc o n c e p tl a t t i c e ， b u ta l s or e s o l v e st h ep r o b l e mo fc o n c e p tl a t t i c eu p d a t ec a u s e db ya p p e n d i n gn e w a t t r i b u t e si n t oa ne x i s t i n gc o n t e x to ft h el a t t i c e ，i na d d i t i o ne s t a b l i s h e st h ef o u n d a t i o n f o rt h eh o r i z o n t a lu n i o no f c o n c e p tl a t t i c e so f d i s t r i b u t e dc o n t e x t s w i t ht h ei n c r e a s eo ff o r m a lc o n t e x t s ，t h et i m ea n ds p a c ec o m p l e x i t yo fb u i l d i n g c o n c e p tl a t t i c ew i l ls h a r p l yi n c r e a s e i ti so n eo ft h em o s ti m p o r t a n tc o n t e n t sf o rt h e c o n c e p tl a t t i c et e c h n i q u et or e s e a r c ht h en e wm e t h o d sa n dt e c h n i q u e so fc o n c e p t l a t t i c ec o n s t r u c t i o n t h em a n ya l g o r i t h m so fb u i l d i n gc o n c e p tl a t t i c ea r ea i m e da t s i n g l ec o n c e p tl a t t i c e t h ed i v i d e - a n d c o n q u e rs t r a t e g yi st h ee f f e c t i v ea p p r o a c ho f f o r m i n gc o n c e p tl a t t i c e t h ea p p r o a c ho fd i s t r i b u t e dc o n s t r u c t i o no fc o n c e p tl a t t i c ei s a sf o l l o w s ：f i r s td e c o m p o s et h ef o r m a lc o n t e x ti n t om a n ys u b - c o n t e x t sa n dc o n s t r u c t c o r r e s p o n d i n gs u b l a t t i c e ，t h e n o b t a i nt h e c o n c e p tl a t t i c eb yc o m b i n i n gt h e s e s u b 1 a t t i c e s c o n c e p tl a t t i c ei sar e p r e s e n t a t i o no fr e l a t i o n s h i pb e t w e e nc o n c e p t si nf o r m a l c o n t e x t ，a n di t i sc o r r e s p o n d i n go n eb yo n ew i t ht h ef o r m a lc o n t e x t ，s ot h ed i s t r i b u t e d v l i 上海大学博士学位论文 t r e a t m e n to fc o n c e p tl a t t i c ec e r t a i n l yr e l a t e st os o m et r e a t m e n t sa n do p e r a t i o n ss u c ha s t h ed e c o m p o s i t i o na n dc o m b i n a t i o no fc o n t e x t b a s e do nt h eh o r i z o n t a la n dv e r t i c a l c o m b i n a t i o no ra p p o s i t i o na n ds u b p o s i t i o ni nf o r m a lc o n t e x t s ，t h i sd i s s e r t a t i o nd e f i n e s t w ok i n d so fc o n t e x t sa n d1 a r i c e s ，a n dr e s e a r c h e st h em e t h o do fi n c o n s i s t e n tc o n t e x t s t r e a t m e n t ，a n da l s op r o v e st h a tt h ec o n c e p tl a t t i c eo fs u b c o n t e x t sh o r i z o n t a l l y c o m b i n e di si s o m o r p h i ct ot h eh o r i z o n t a lu n i o no fs u b l a r i c e so ft h e s es u b c o n t e x t s u s i n gt h ei n h e r e n tg e n e r a l s p e c i a lr e l a t i o n b e t w e e nc o n c e p t si ns u b l a t t i c ea n d i n h e r i t i n gt h ee x i s t e di n c r e m e n t a la l g o r i t h mo fc o n c e p tl a t t i c ec o n s t r u c t i o na n d m o d i f y i n gt h ea l g o r i t h m ，t h eh o r i z o n t a lu n i o na l g o r i t h mo fm u l t i p l ec o n c e p tl a t t i c e st o c o n s t r u c tt h ec o n c e p tl a t t i c ei sp r e s e n t e d ，w h i c hi sv e r ys u i t a b l ef o rc o m b i n i n gm a n y s u b 1 a t t i c e s d a t am i n i n gi st oe x t r a c ta u t o m a t i c a l l yt h eu s a b l ep o t e n t i a li n f o r m a t i o na n d k n o w l e d g ef r o md a t a ，a n dt h e s ei n f o r m a t i o na n dk n o w l e d g ee x p r e s sa sc o n c e p t ，r u l e o rp a r e m t h ea s s o c i a t i o nr u l ei st h em a i nf o r mo fk n o w l e d g ee x t r a c t e df r o mt h e d a t a b a s e a n dw h i c hi so n eo f t h em a j o rg o a l si nt h ed a t am i n i n g 1 1 1 er u l e sa r eu s u a l l y e x t r a c t e df r o m 丹e q u e n ti t e m s e t s ，b u tt h en u m b e ro ff r e q u e n ti t e m s e t si se n o r m o u s t h e r ee x i s tm a n yr e d u n d a n tr u l e sd u r i n gr u l e sa r ee x t r a c t e df r o m 丘e q u e n ti t e m s e t s i n o r d e rt or e d u c et h en u m b e ro ff r e q u e n ti t e m s e t sw i t h o u tl o s sa n yu s e f u li n f o r m a t i o n ， f r e q u e n tc l o s e di t e m s e t sa r ea d o p t e dt oe x t r a c tt h em i n i m a ln o n r e d u n d a n ta s s o c i a t i o h r u l e s b a s e do nc a r e f u ls t u d y i n ga n da n a l y z i n gt h ea l g o r i t h m sf o rm i n i n gr u l e sf r o mt h e f r e q u e n tc l o s e di t e m s e t sa n dt h ei n h e r e n tc l o s u r ep r o p e r t i e si nc o n c e p tl a t t i c e ，t h i s d i s s e r t a t i o nc a r r i e s t h r o u g ht h ed e e p l y r e s e a r c ho n e x t r a c t i n g t h em i n i m a l n o n - r e d u n d a n tr o l e so nt h e c o n c e p t l a t t i c e i no r d e rt oe x t r a c tt h em i n i m a l n o n - r e d u n d a n tr u l e s c o n v e n i e n t l y , w ed e f i n e t h eq u a n t i t a t i v ec l o s e dl t e m s e t l a t t i c e ( q c i l ) a n df i n do u tt h ek e yo fe x t r a c t i n gs u c hr u l ei st oo b t a i nt h el e a s t i t e m s e t si nt h es e to ff r e q u e n ti t e m s e t sw i t ht h es a m et i d s e tw h i c hc o r r e s p o n d st ot h e n o d e si ns u c hl a t t i c e ，a n dp r o v i d et h em e t h o d so fc o m p u t i n gt h es e to ft h el e a s t i t e m s e t s ( s l i t ) b ya d o p t i n gp o w e rs e ta n dd i f f e r e n c es e t ，a n dp r e s e n ta ni n n o v a t i v e a l g o r i t h mo fe x t r a c t i n gt h ea s s o c i a t i o nr u l e ，w h i c hc a nd i r e c t l ye x t r a c tm i n i m a l n o n - r e d u n d a n ta s s o c i a t i o nr u l e sf r o mt h eq c i l f o rt h es a k eo fm o r er e d u c i n gt h e n u m b e ro fr u l e st os a t i s f ys p e c i a lr e q u i r e m e n to fu s e r , t h i sd i s s e r t a t i o nb r i n g sf o r w a r d t h eg l o b a ls u c c i n c ta s s o c i a t i o nr u l e ，a n dp r e s e n t st h ea l g o r i t h mo f e x t r a c t i n gs u c hr u l e u s i n gc o n c e p tl a t t i c e a tp r e s e n t ，t h e r ea r eal o to fr e s e a r c h e so ne x t r a c t i n ga s s o c i a t er u l e sb u taf e wo f v 1 1 1 上海大学博士学位论文 r e s e a r c h e so nu p d a t i n ga s s o c i a t er u l e s i nf a c t ，i ti sa l s ot h es a m ei m p o r t a n tp a r ta st h e e x t r a c t i n gr u l e st ou p d a t i n gr u l e si nk n o w l e d g ed i s c o v e r y f o ru p d a t i n gm i n i m a l n o n - r e d u n d a n tr u l e s ，t h i sd i s s e r t a t i o ne x p a n d st h es t r u c t u r eo ft h eq u a n t i t a t i v ec l o s e d i t e m s e tl a t t i c e ，a n dp r e s e n t st h eq u a n t i t a t i v er u l el a t t i c e ( q r l ) ，a n dr e a l i z e st h es l i t u p d a t e dw h i c hc o r r e s p o n d st os u c hr u l e sa tt h es a m et i m eo fu p d a t i n gt h eq r l b e c a u s eo f i n c r e m e n t a lf o r m a t i o no f q r la n dt h es e to f t h el e a s ti t e m s e t s ，t h eq r li s v e r ys u i t a b l en o to n l y f o re x t r a c t i n gt h em i n i m a ln o n r e d u n d a n tr u l e sf r o mt h e d y n a m i cd a t a b a s eb u t a l s of o rr e a l i z i n gt h er u l eu p d a t e di n c r e m e n t a l l y a c c o r d i n gt ot h ed i s t r i b u t e dt r e a t m e n to fc o n c e p tl a t t i c e ，af o r m a lc o n t e x ti ss p l i t i n t om a n yp a r t i a lc o n t e x t sa n dc o r r e s p o n d i n gp a r t i a ll a t t i c e sa r ec o n s t r u c t e d ，t h e nt h e c o m p l e t ec o n c e p tl a t t i c ei so b t a i n e db yc o m b i n i n gt h e s ep a r t i a ll a t t i c e s t h e r e f o r e ，i t i sa ne f f e c t i v em e a n so fa c q u i r i n gk n o w l e d g et oe x t r a c tc o r r e s p o n d i n ga s s o c i a t i o n r u l e sf r o mt h ec o m p l e t ec o n c e p tl a t t i c e s t h e r ei sam o r ed i r e c ta n de f f e c t u a lm e a n st o o b t a i nt h ef i n a lr u l e sb yc o m b i n i n gt h ep a r t i a lr u l e sm i n e df r o mt h ep a r t i a ll a t t i c e s t h i sd i s s e r t a t i o nm a k e ss o m ei n v e s t i g a t i o n so nt h i sa s p e c t ，a n dp r e s e n t si t sf r a m e w o r k ， m a dr e s e a r c h e so nh o wt ov e r i f yt h ev a l i d i t yo f p a r t i a lr u l es e ti nf u l ld a t a b a s ea n dt o i n t e g r a t et h ep a r t i a lr u l e si n t ot h ef i n a lv a l i dr u l e s f i n a l l y , as i m p l ee x a m p l ei s c o n d u c t e dt oi l l u s t r a t et h ec o r r e c t n e s so fo u rs o l u t i o n k e y w o r d s ：c o n c e p tl a t t i c e ，f o r m a lc o n t e x t ，p a r t i a ll a t t i c e ，a p p o s i t i o na n ds u b p o s i t i o n ， d i v i d e 。a n d 。c o n q u e rs t r a t e g y , f r e q u e n tc l o s e di t e m s e t ，i t e m s e tw i t ht h es a m et i d s e t ， m i n i m a ln o n r e d u n d a n t r u l e ，s u c c i n c tr u l e ，q u a n t i t a t i v ec l o s e di t e m s e t l a t t i c e ， q u a n t i t a t i v er u l el a t t i c e ，p a r t i a lv a l i dr u l e ，f i n a lv a l i dr u l e i x 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解i 二海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交 论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名 上海大学博士学位论文 第一章绪论 1 1 研究的背景与意义 在形式概念分析 g a n 9 9 】中，概念的外延被理解为属于这个概念的所有对象 的集合，而内涵则被认为是所有这些对象所共有的特征( 或属性) 集合，这实现 了对概念的哲学理解的形式化。而概念格作为形式概念分析中核心的数据结构， 本质上描述了对象和特征之间的联系，表明了概念之间的泛化与例化关系，其相 应的h a s s e 图则实现了对数据的可视化。作为序论和格论与实际应用结合的产 物，概念格模型的研究具有重要的理论意义。目前国际国内对概念格的数学性质、 与模糊集合和粗糙集合之间的关联等方面做了大量研究，取得了一系列重要成果 【f e r 9 8 l i u 0 0 ，并已在数据分析、信息检索和知识发现等方面得到了广泛的应 用 f e r 9 8 k r 0 9 9 k u z 0 1 a 。 但是，概念格构造的时间复杂性和空间复杂性问题始终是困扰其应用的大 难题。国内外的研究人员虽然已经提出了一系列概念格构造算法，但现有的算法 大多都是考虑数据库对象方向的渐增更新问题，而对属性方向的渐增更新问题未 见报道。也就是说现有的算法不适应于形式背景在属性方向上的更新需要。因此， 研究基于属性的概念格构造算法是有意义的。 概念格构造算法 k u z 0 1 b 】【k u z 0 1 c 可以分为两类：渐进式算法和批处理算 法。渐进式算法表现出了更强的生命力 g o d 9 5 a 【x i e 0 2 】，但其结果仍然不能令 人满意，其原因就在于这些算法基本上都是串行的，而生成的概念格所采用的都 是集中式存储模式。 采用分治策略来构造和存储概念格是有效地解决这一问题的主要途径。由于 概念格有良好的数学性质和层次结构等特点，因此，概念格的分布处理模式，是 解决上述问题是非常理想的工具。通过对形式背景( c o n t e x t ) n 分割，形成多个子 背景，然后再对子背景分布构造其子格，最后再进行子格的合并形成完整概念格， 在这方面国际上只有r v a l t c h e v 等作了一些尝试 v a l 0 1 】【v a l 0 2 a ，通过枚举两个 子格概念之间的组合，计算出其对应的全局格概念。但由于一个部分格的概念对 另一部分格的概念是遍历计算，会产生较大的重复，从而影响了r v a l t c h e v 所提 算法的效率。研究如何进行有效概念格的分布处理具有现实的意义。 从数据库中提取规则是知识发现的主要内容，现已出现了大量提取规则的算 上海大学博士学位论文 法 a g r 9 4 1 h a r t 0 0 。规则一般都是从频繁项集中提取的，而频繁项集的数量是很 庞大的，且从中提取的规则还存在着大量的冗余规则。为了缩减频繁项集的数目， 减小提取规则的搜索空间同时也不丢失有用信息，现在提出了用频繁封闭项集来 提取关联规则。从事务数据库中提取频繁封闭项集的方法有c l o s e p a s 9 9 】、 c h a r m z a k 9 9 、c l o s e t 【p e i 0 0 等多种。其中c l o s e 、c h a r m 算法需多次扫 描原事务数据库，且需产生候选项集，但数据库增加事务时就需重新处理。 c l o s e t 虽只对数据库扫描一次，也无需产生候选集，但它也不适应数据库更 新的要求。而基于概念格的关联规则提取算法与传统的算法相比也具有相当的优 点 w a n 9 9 9 】 w a i 0 0 x i e 0 0 。从格中提取无冗余规则的最小集合，对用户获取有 用的知识，降低所需的时空复杂度是有益的 z a k 0 0 1 b a s 0 0 】 g a 0 0 1 ，但这方面 还很不完善。而如何和概念格分布处理相结合，目前未见有相关的研究报告。 研究概念格分布处理的相关算法，将为实际应用提供有效方法；研究把概念 格的分布处理和规则提取相结合，利用概念格和对应的最小无冗余规则的关系， 并且利用多概念格韵合并直接得到完整格及其对应的规则集合，将极大她降低规 则提取所需的时间和空间开销。因此，研究概念格分布处理及其在概念格分布处 理框架下的获取有用的知识，具有重要的理论意义和实用价值。 1 2 论文概要与主要贡献 概念格应用的前提是概念格的构造。自从g o d i n 提出概念格的渐进式构造 g o d 9 4 以来，概念格构造方面的研究得到了新的发展。渐进式算法表现出了更 强的生命力和适应性。但现有的算法基本上都是属于基于对象的渐进式生成概念 格的算法，而基于属性的构格算法还没见报告。实际上，形式背景中数据的变化 应该包括两个方面：一是对象( 实例) 的增减，二是属性( 特征) 的增减。增加 属性可能使原来不能区分的对象能够区分，删除属性就可能使原来属于不同类的 对象变为同一类。对于已经构造好的概念格，发生属性的增删时，就需对概念格 进行基于属性的更新，这时若采用传统的基于对象的渐进式算法就需重新构造整 个概念格。通过对概念格中概念对象和属性之间相互关系的研究，本文提出并实 现了基于属性的渐进式生成算法 l i 0 4 a 。它不仅为概念格的生成提供了一种新 的方法，而且解决了在己构造好概念格的前提下，增加属性所带来的概念格更新 闻题，另外，它也为分布式存储的形式背景及其概念格的横向合并( 属性合并) 提供了基础。若把该算法和基于对象的渐进式概念格生成算法相结合，就可以灵 活地处理不同情况下对概念格的更新问题。 由于概念格自身的完备性，构造概念格的时空复杂度一直是影响形式概念分 析应用的主要障碍。随着处理的形式背景的增大，概念格的时空复杂度也会随着 上海大学博士学位论文 急剧增大。研究采用新的方法和手段来构造概念格，就成为概念格研究的主要内 容之一。现在已经提出了构造概念格的多种算法，取得了一系列重要成果，但是 这些研究基本上是针对单个概念格的。概念格的分布处n u 0 3 是解决该问题的 有效手段。它就是通过形式背景的拆分，形成分布存储的多个子背景，然后同时 并行构造相应的子概念格，再由子概念格的合并得到所需的概念格。 由于概念格是其形式背景中的概念间关系的表现形式，它和对应的形式背景 是一一对应的。因此，对概念格的分布处理必然涉及到形式背景的拆分、合并等 处理。形式背景的横向、纵向合并称为形式背景的并置( a p p o s i t i o n ) 和叠置 ( s u b p o s i t i o n ) g a n 9 9 】。因而，多概念格的合并就有横向合并和纵向合并两种。继 承已有的概念格渐进式构造的算法，并对其进行改造，形成能满足多个子概念格 合并处理要求的算法 l i 0 4 b 1 ，是很有意义的。 数据挖掘【h a n 0 0 1 是随着k d d ( k n o w l e d g ed i s c o v e r yi nd a t a d a s e ) 的研究雨 发展起来的，是一种从大型的数据库中发现和提取掩藏在其中的信息的一种新技 术。数据挖掘在于自动从数据中提取出入们感兴趣的潜在的可用信息和知识，并 将提取出来的信息和知识表示成概念、规则和模式。 而一个事务数据库中频繁项集的数量往往很庞大，从频繁项集中提取的规则 就会很多，且存在大量的冗余。为了缩减频繁项集的数目同时也不丢失有用信息， 现在提出了用频繁封闭项集 p a s 9 9 【z a k 9 9 1 p e i 0 0 来提取最小无冗余的关联规 则。 在挖掘规则知识过程中，规则本身是用内涵( 特征、属性) 集之间的关系来 描述的，而体现于相应外延( 对象) 集之间的包含关系。概念格节点正好反跌了 概念内涵和外延的统一，节点间关系体现了概念之间的泛化和例化关系，另外由 于概念格中概念对象和属性问固有的封闭性，它也很适合于表示封闭项集间的关 系。因此概念格非常适合作为规则发现的基础性数据结构。 本文通过对现有利用频繁封闭项集( f r e q u e n tc l o s e di t e m s e t ) 提取规则算法的 仔细研究和分析，结合概念格的特点，对基于概念格提取最小无冗余的关联规则 进行了较深入的研究。为了便于提取最小无冗余的关联规则，定义了量化封闭项 集格( q u a n t i t a t i v ec l o s e di t e m s e tl a t t i c e ，简记为q c i l ) ，发现了提取最小无冗余 关联规则的关键是是找出格中每个节点的项集所对应的同交易的频繁项集集合 ( s f i s t ) 中的最小项集的集合( t h es e to f t h el e a s ti t e m s e t s ) ，简记为s l i t 。并采 用幂集和差集两种方案分别获取s l i t ，从q c i l 直接提取最小无冗余的精确规 则和近似规贝j l i 0 4 c l i 0 4 d i l i 0 4 e 。 研究概念格应用于无冗余的关联规则挖掘，将会充分发挥概念格自身的信息 完备性，为减少规则提取所需的时间和空间复杂度提供的基础和保证。目前研究 关联规则的提取工作很多，但研究规则的更新工作相对较少【y a i l 9 0 0 1 。实际上， 上海大学博士学位论文 规则的更新问题和规则的提取问题一样，也是知识发现研究的重要环节。本文为 了实现对最小无冗余的关联规则的更新，对q c i l 的结构作了进一步的扩充，提 出了量化规则格i l l 0 5 】，实现了在概念格更新的同时，对最小无冗余的关联规则 所对应的s l i t 的更新。 利用概念格的分布处理，把形式背景进行拆分，分别构造相应的部分概念格， 然后再进行部分概念格合并，得到完整概念格，再提取出相应的关联规则是从概 念格中获取知识的一种有效手段：同样，先从部分概念格中分别提取出规则，然 后直接进行规则的合并，也是获取知识的一种更直接更有效的手段。本文也在这 方面做了一定的探索。 本文各章节的详细设置情况如下： 论文第二章首先对形式概念分析及其概念格模型进行简单的介绍，然后简述 了多值形式背景的处理和几种概念格的扩展模型，最后，对形式概念分析和概念 格在数据挖掘、软件工程、信息检索等方面的应用进行了综述和总结。 论文第三章主要讲述概念格的生成和维护方面的算法和技术。首先对现有的 概念格生成算法进行了一定的总结，然后重点讲述了两个基于属性的概念格生成 算法，并对概念格在对象和属性两个方向上的删除维护技术作了简述。 论文第四章主要讲述通过对形式背景的拆分来构造子概念格，再由子格的合 并形成完整概念格的分布处理技术及其算法，详细讲述了概念格的横向合并算法 及其实现。 论文第五章主要讲述把概念格应用于规则提取所涉及的有关的项集、封闭项 集、封闭项集格等概念，并定义了同交易的频繁项集集合。对同交易的频繁项集 中的最小项集集合的计算进行了详细的描述，为第六章把概念格应用于规则提 取，特别是最小无冗余关联规则的提取奠定了基础。 论文第六章讲述如何把概念格应用于关联规则的提取的技术，重点讲述对最 小无冗余关联规则的提取。并以提取最小无冗余关联规则的思想为前提，提出简 洁规则的概念及其提取技术。由于同交易的频繁项集集合中的最小项集集合是提 取最小无冗余关联规则的关键，为了实现对最小无冗余关联规则的更新，提出了 量化规则格的概念，实现了在概念格更新的同时，更新最小项集集合的算法和技 术。 论文第七章讲述利用概念格的分布处理，采用两种方案来提取关联规则。第 一种方案是利用概念格的分布处理，然后通过子格的合并形成完整概念格，再提 取出相应的关联规则；第