第9卷第2期 智能系统学报 Vol.9 No.2 2014年4月 CAAI Transactions on Intelligent Systems Apr.2014 D0I:10.3969/j.issn.1673-4785.201307019 网络出版地址：http://www.cmki.net/kcms/doi/10.3969/j.issn.1673-4785.2013.html 基于不可约元下集格的概念获取 石慧，何苗，魏玲 （西北大学数学系，陕西西安710127) 摘要：形式概念分析是知识获取的一种有效工具，已被广泛应用于许多领域.文章从形式背景出发，首先利用箭 头关系找到相应概念格的并不可约元（交不可约元），对并不可约元（交不可约元）的外延集（内涵集）求其下集格： 进而对下集格中的元素定义相应的运算，可证明其结果是概念格的内涵集（外延集）；最后将该内涵集（外延集）扩 充成为概念，并将此方法应用于不完备形式背景的完备化该完备化将格论与形式概念分析结合，体现出不可约元 的重要性且方法直观明了，简化了概念格的构造 关键词：形式背景：下集格：概念格：不可约元：形式概念分析：概念获取 中图分类号：TP18:029文献标志码：A文章编号：1673-4785(2014)02-0244-07 中文引用格式：石慧，何苗，魏玲.基于不可约元下集格的概念获取[J].智能系统学报，2014,9(2)：244-250. 英文引用格式：SHⅢHui,HE Miao,WEI Ling.Concept acquisition based on the down-set lattice of irreducible elements[J].CAAI Transactions on Intelligent Systems,2014,9(2):244-250. Concept acquisition based on the down-set lattice of irreducible elements SHI Hui,HE Miao,WEI Ling (Department of Mathematics,Northwest University,Xi'an 710127,China) Abstract:As an efficient tool for knowledge acquisition,formal concept analysis has been applied to many fields. Based on a formal context,the arrow operator proposed by Wille is used to find the join-irreducible elements (meet- irreducible elements)of a concept lattice firstly,and then the down-set lattice of the extents (intents)of the join- irreducible elements (meet-irreducible elements)can be obtained;then an operation is defined on the down-set lattice,and the intents (extents)of the concept lattice can be obtained,which can be expanded to the concepts; finally,this method is used to complete an incomplete formal context.The completion method combines the lattice theory and the formal concept analysis,reflects the importance of irreducible elements which simplifies the structure of the concept lattice,and the method is visual and clear. Keywords:formal context;down-set lattice;concept lattice;irreducible element;formal concept analysis;concept acquisition 德国数学家R.Wle于1982年首先提出了形式构，即概念格，概念格的构造[21是形式概念分析理 概念分析理论山，用于概念的发现、排序和显示。 论的主要研究内容之一。目前，已提出的概念格构 形式背景与形式概念是形式概念分析的基本概念，造方法主要有2种，增量算法与批处理算法。增量 形式概念是由形式背景中的对象集和属性集组成的 算法是在数据信息不确定或不完整的情况下，当有 统一体，形式概念之间可形成一种有序的层次结 少量数据变动时，对已经构造的概念格进行更新和 维护[3,6)：批处理算法是在数据比较完整的情况下， 收稿日期：2013-10-15.网络出版日期：2014-03-31. 基金项目：国家自然科学基金资助项目(60703117,61005042). 依据形式背景初次构造概念格的一种更有效的方 通信作者：魏玲.E-mail:wl@nwu.cdu.cn
第 ９ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．２ ２０１４ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０７０１９ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｏｉ ／ １０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３．ｈｔｍｌ 基于不可约元下集格的概念获取 石慧，何苗，魏玲 （西北大学 数学系，陕西 西安 ７１０１２７） 摘 要：形式概念分析是知识获取的一种有效工具， 已被广泛应用于许多领域． 文章从形式背景出发， 首先利用箭 头关系找到相应概念格的并不可约元（交不可约元）， 对并不可约元（交不可约元）的外延集（内涵集）求其下集格； 进而对下集格中的元素定义相应的运算， 可证明其结果是概念格的内涵集（外延集）； 最后将该内涵集（外延集）扩 充成为概念， 并将此方法应用于不完备形式背景的完备化．该完备化将格论与形式概念分析结合， 体现出不可约元 的重要性且方法直观明了， 简化了概念格的构造． 关键词：形式背景； 下集格； 概念格； 不可约元；形式概念分析；概念获取 中图分类号： ＴＰ１８；Ｏ２９ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０２⁃０２４４⁃０７ 中文引用格式：石慧，何苗，魏玲． 基于不可约元下集格的概念获取［Ｊ］． 智能系统学报， ２０１４， ９（２）： ２４４⁃２５０． 英文引用格式：ＳＨＩ Ｈｕｉ， ＨＥ Ｍｉａｏ， ＷＥＩ Ｌｉｎｇ ． Ｃｏｎｃｅｐｔ ａｃｑｕｉｓｉｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｏｗｎ⁃ｓｅｔ ｌａｔｔｉｃｅ ｏｆ ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（２）： ２４４⁃２５０． Ｃｏｎｃｅｐｔ ａｃｑｕｉｓｉｔｉｏｎ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｏｗｎ⁃ｓｅｔ ｌａｔｔｉｃｅ ｏｆ ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ ＳＨＩ Ｈｕｉ， ＨＥ Ｍｉａｏ， ＷＥＩ Ｌｉｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ， Ｎｏｒｔｈｗｅｓｔ Ｕｎｉｖｅｒｓｉｔｙ， Ｘｉ’ａｎ ７１０１２７， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ： Ａｓ ａｎ ｅｆｆｉｃｉｅｎｔ ｔｏｏｌ ｆｏｒ ｋｎｏｗｌｅｄｇｅ ａｃｑｕｉｓｉｔｉｏｎ， ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ｈａｓ ｂｅｅｎ ａｐｐｌｉｅｄ ｔｏ ｍａｎｙ ｆｉｅｌｄｓ． Ｂａｓｅｄ ｏｎ ａ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ， ｔｈｅ ａｒｒｏｗ ｏｐｅｒａｔｏｒ ｐｒｏｐｏｓｅｄ ｂｙ Ｗｉｌｌｅ ｉｓ ｕｓｅｄ ｔｏ ｆｉｎｄ ｔｈｅ ｊｏｉｎ⁃ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ （ｍｅｅｔ⁃ ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ） ｏｆ ａ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｆｉｒｓｔｌｙ， ａｎｄ ｔｈｅｎ ｔｈｅ ｄｏｗｎ⁃ｓｅｔ ｌａｔｔｉｃｅ ｏｆ ｔｈｅ ｅｘｔｅｎｔｓ （ｉｎｔｅｎｔｓ） ｏｆ ｔｈｅ ｊｏｉｎ⁃ ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ （ｍｅｅｔ⁃ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ） ｃａｎ ｂｅ ｏｂｔａｉｎｅｄ； ｔｈｅｎ ａｎ ｏｐｅｒａｔｉｏｎ ｉｓ ｄｅｆｉｎｅｄ ｏｎ ｔｈｅ ｄｏｗｎ⁃ｓｅｔ ｌａｔｔｉｃｅ， ａｎｄ ｔｈｅ ｉｎｔｅｎｔｓ （ｅｘｔｅｎｔｓ） ｏｆ ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｃａｎ ｂｅ ｏｂｔａｉｎｅｄ， ｗｈｉｃｈ ｃａｎ ｂｅ ｅｘｐａｎｄｅｄ ｔｏ ｔｈｅ ｃｏｎｃｅｐｔｓ； ｆｉｎａｌｌｙ， ｔｈｉｓ ｍｅｔｈｏｄ ｉｓ ｕｓｅｄ ｔｏ ｃｏｍｐｌｅｔｅ ａｎ ｉｎｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ． Ｔｈｅ ｃｏｍｐｌｅｔｉｏｎ ｍｅｔｈｏｄ ｃｏｍｂｉｎｅｓ ｔｈｅ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ ａｎｄ ｔｈｅ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ， ｒｅｆｌｅｃｔｓ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔｓ ｗｈｉｃｈ ｓｉｍｐｌｉｆｉｅｓ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ， ａｎｄ ｔｈｅ ｍｅｔｈｏｄ ｉｓ ｖｉｓｕａｌ ａｎｄ ｃｌｅａｒ． Ｋｅｙｗｏｒｄｓ：ｆｏｒｍａｌ ｃｏｎｔｅｘｔ； ｄｏｗｎ⁃ｓｅｔ ｌａｔｔｉｃｅ； ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ； ｉｒｒｅｄｕｃｉｂｌｅ ｅｌｅｍｅｎｔ； ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ； ｃｏｎｃｅｐｔ ａｃｑｕｉｓｉｔｉｏｎ 收稿日期：２０１３⁃１０⁃１５． 网络出版日期：２０１４⁃０３⁃３１． 基金项目：国家自然科学基金资助项目（６０７０３１１７， ６１００５０４２）． 通信作者：魏玲． Ｅ⁃ｍａｉｌ： ｗｌ＠ ｎｗｕ．ｅｄｕ．ｃｎ． 德国数学家 Ｒ．Ｗｉｌｌｅ 于 １９８２ 年首先提出了形式 概念分析理论［１］ ， 用于概念的发现、排序和显示。 形式背景与形式概念是形式概念分析的基本概念， 形式概念是由形式背景中的对象集和属性集组成的 统一体， 形式概念之间可形成一种有序的层次结 构，即概念格， 概念格的构造［２⁃５］是形式概念分析理 论的主要研究内容之一。 目前， 已提出的概念格构 造方法主要有 ２ 种， 增量算法与批处理算法。 增量 算法是在数据信息不确定或不完整的情况下， 当有 少量数据变动时， 对已经构造的概念格进行更新和 维护［３，６］ ； 批处理算法是在数据比较完整的情况下， 依据形式背景初次构造概念格的一种更有效的方
第2期 石慧，等：基于不可约元下集格的概念获取 ·245· 法，它主要分为枚举、自顶向下和自底向上3种算 体并不可约元记为J(L),交不可约元记为M(L)。 法[)。此外，还有将大背景横向拆分为若干小形 定义5)设P为一个偏序集，Q二P,如果H 式背景，再将各小形式背景的概念格进行横向合 x∈Q,y∈P且y≤x时有y∈Q,则称Q为下集。记P 并，从而构建出相应的原形式背景概念格的方 的所有下集为o(P),称o(P)为P的下集格。 法[)；以及从对象集的每一个等价类所拥有的属性 定理12)]设L为有限格，L中的任意元素可 子集之间的包含关系出发，构造相应的Hasse图，从 表示成某些并不可约元（交不可约元）的并（交）。 而得到概念格[0的方法。本文对并不可约元（交不 定义6四设(G,M,I)为形式背景，g∈G, 可约元)下集格中的元素定义运算，得到相应概念 m∈M:gm一gm,并且，若g≤h且g≠h,则 格的内涵集（外延集），进而扩充为概念。 有hm;gm一gm,并且，若m'Cn'且m'≠n',则 1理论基础 有gln;gm→gkm并且gm。 定理2)下面断言对每个背景都成立： 定义1山称(G,M,)为一个形式背景，其中 1)对象概念(g”,g)是并不可约元一存在一 G={81,82,…,g,}为对象集，每个g:(i≤t)称为一 个m∈M,使gm: 个对象；M=m1,m2,·,m,}为属性集，每个m(≤ 2)属性概念(m',m*)是交不可约元→存在一 s)称为一个属性；I为G和M之间的二元关系IC 个g∈G,使gm; GxM。若(g,m)∈I,则称g具有属性m,用glm表 下面断言对每个有限背景都成立： 示；否则，记为gm。 3)对象概念(g',g)是并不可约元存在一 对于形式背景(G,M,I),在对象集XCG和属 个m∈M,使gm; 性集B二M上分别定义运算： 4)属性概念(m',m)是交不可约元一存在一 X={mlm∈M,Hg∈X,glm 个g∈G,使gmo B'={glg∈G,Hm∈B,glm} 记：L(G,M,I)={XI(X,B)∈L(G,M,I)}是概 VgeG,记{g}*为g;Hm∈M,记{m}'为m'。若 念格L(G,M,I)所有外延构成的集合； Hg∈G,g≠⑦，g≠M,且Hm∈M,m'≠0， Lw(G,M,I)={BI(X,B)∈L(G,M,I)}是概念 m'≠G,则称形式背景(G,M,I)是正则的。本文提 格L(G,M,I)所有内涵构成的集合； 到的形式背景都是正则的。 Jc(L)={XI(X,B)∈J(L)}为概念格L(G,M, 定义2)设(G,M,)是形式背景，对X二G, )的并不可约元的外延集； BCM,若满足X=B且X=B',则称(X,B)是一个 M(L)={BI(X,B)∈M(L)}为概念格L(G, 形式概念，简称概念；其中X称为概念的外延，B M,I)的交不可约元的内涵集。 称为概念的内涵。形式背景(G,M,I)的全体概念记 2 基于不可约元下集格的概念获取 为L(G,M,I)。 Y(X,B),(X2,B2)EL(G,M,I), 本节主要给出通过不可约元做下集格，再定义 定义： 映射找到全部概念的方法。首先，根据定义6确定 (X,B)A (X2,B2)=(X nX2,(BUB2)") 形式背景中的箭头关系，根据定理2找到该形式背 (X,B)V(X2,B2)=(XUX2)',B1∩B2) 景所对应概念格的并不可约元，其次对并不可约元 则L(G,M,I)是完备格，称为概念格。 的外延集做下集格，再对下集格中的元素定义映 定义3山设(G,M,)为形式背景，Vg∈G, 射，从而得到概念格的全部内涵集，进一步得到全 m∈M,称(g',g)为对象概念，(m',m")为属性概 部概念。利用对偶性，对交不可约元的内涵集做下 念。 集格，定义相应的映射，得到概念格的全部外延 定义42)]设L是格，若满足下列条件，则称 集，进而得到所有概念。 x∈L是并不可约元： 定义映射fi:o(Je(L))→Lw(Jc(L))如下：H 1)x≠0（如果L有零元）： X∈o(Jc(L)),f(X)=∩X=(UX)',X∈X,且将 2)x=aVb→x=a或x=b(a,b∈L)。 o(J(L))中所有元素的像集记为L,(J(L))。 对偶地，可得到交不可约元的定义。格L的全 性质1映射f:o(Jc(L))→L(J(L))具有以
法，它主要分为枚举、自顶向下和自底向上 ３ 种算 法［７⁃８］ 。 此外， 还有将大背景横向拆分为若干小形 式背景， 再将各小形式背景的概念格进行横向合 并， 从而构建出相应的原形式背景概念格的方 法［９］ ； 以及从对象集的每一个等价类所拥有的属性 子集之间的包含关系出发，构造相应的 Ｈａｓｓｅ 图，从 而得到概念格［１０］的方法。 本文对并不可约元（交不 可约元）下集格中的元素定义运算， 得到相应概念 格的内涵集（外延集）， 进而扩充为概念。 １ 理论基础 定义 １ ［１１］ 称（Ｇ，Ｍ，Ｉ）为一个形式背景， 其中 Ｇ ＝ ｛ｇ１ ，ｇ２ ，．．．，ｇｔ｝为对象集， 每个 ｇｉ（ ｉ≤ｔ） 称为一 个对象； Ｍ＝ ｛ｍ１ ，ｍ２ ，…，ｍｓ｝为属性集， 每个 ｍｊ（ｊ≤ ｓ）称为一个属性； Ｉ 为 Ｇ 和 Ｍ 之间的二元关系 Ｉ⊆ Ｇ×Ｍ。 若（ｇ，ｍ）∈Ｉ， 则称 ｇ 具有属性 ｍ， 用 ｇＩｍ 表 示； 否则， 记为 ｇɫｍ。 对于形式背景（Ｇ，Ｍ，Ｉ）， 在对象集 Ｘ⊆Ｇ 和属 性集 Ｂ⊆Ｍ 上分别定义运算： Ｘ * ＝ ｛ｍ |ｍ ∈ Ｍ， ∀ｇ ∈ Ｘ， ｇＩｍ｝ Ｂ ¢＝ ｛ｇ |ｇ ∈ Ｇ， ∀ｍ ∈ Ｂ，ｇＩｍ｝ ∀ｇ∈Ｇ， 记｛ｇ｝ *为 ｇ * ； ∀ｍ∈Ｍ， 记｛ｍ｝¢为 ｍ ¢。 若 ∀ｇ∈Ｇ， ｇ * ≠Æ， ｇ * ≠Ｍ， 且∀ｍ∈Ｍ， ｍ ¢≠Æ， ｍ ¢≠Ｇ， 则称形式背景（Ｇ，Ｍ，Ｉ）是正则的。 本文提 到的形式背景都是正则的。 定义 ２ ［１１］ 设（Ｇ，Ｍ，Ｉ）是形式背景， 对 Ｘ⊆Ｇ， Ｂ⊆Ｍ， 若满足 Ｘ * ＝ Ｂ 且 Ｘ ＝ Ｂ′， 则称（Ｘ，Ｂ）是一个 形式概念， 简称概念； 其中 Ｘ 称为概念的外延， Ｂ 称为概念的内涵。 形式背景（Ｇ，Ｍ，Ｉ）的全体概念记 为 Ｌ（Ｇ，Ｍ，Ｉ）。 ∀ （Ｘ１ ，Ｂ１ ）， （Ｘ２ ，Ｂ２ ）∈Ｌ（Ｇ，Ｍ，Ｉ）， 定义： （Ｘ１， Ｂ１） ∧ （Ｘ２， Ｂ２） ＝ （Ｘ１ ∩ Ｘ２， （Ｂ１ ∪ Ｂ２）′ * ） （Ｘ１， Ｂ１） ∨ （Ｘ２， Ｂ２） ＝ （（Ｘ１ ∪ Ｘ２） * ′， Ｂ１ ∩ Ｂ２） 则 Ｌ（Ｇ，Ｍ，Ｉ）是完备格， 称为概念格。 定义 ３ ［１１］ 设（Ｇ，Ｍ，Ｉ） 为形式背景，∀ｇ∈Ｇ， ｍ∈Ｍ， 称（ｇ * ′， ｇ * ）为对象概念， （ｍ′， ｍ′ * ）为属性概 念。 定义 ４ ［１２］ 设 Ｌ 是格， 若满足下列条件， 则称 ｘ∈Ｌ 是并不可约元： １） ｘ≠０（如果 Ｌ 有零元）； ２） ｘ ＝ ａ ∨ ｂ⇒ｘ ＝ ａ 或 ｘ ＝ ｂ （ａ， ｂ ∈ Ｌ）。 对偶地， 可得到交不可约元的定义。 格 Ｌ 的全 体并不可约元记为 Ｊ（Ｌ）， 交不可约元记为 Ｍ（Ｌ）。 定义 ５ ［１２］ 设 Ｐ 为一个偏序集， Ｑ⊆Ｐ， 如果∀ ｘ∈Ｑ， ｙ∈Ｐ 且 ｙ≤ｘ 时有 ｙ∈Ｑ， 则称 Ｑ 为下集。 记 Ｐ 的所有下集为 ο（Ｐ）， 称 ο（Ｐ）为 Ｐ 的下集格。 定理 １ ［１２］ 设 Ｌ 为有限格， Ｌ 中的任意元素可 表示成某些并不可约元（交不可约元）的并（交）。 定义 ６ ［１１］ 设（Ｇ，Ｍ，Ｉ）为形式背景， ∀ｇ∈Ｇ， ｍ∈Ｍ：ｇ↙ｍ⇌ｇɫｍ， 并且， 若 ｇ *⊆ ｈ * 且 ｇ *≠ ｈ * ， 则 有 ｈＩｍ；ｇ↗ｍ⇌ｇɫｍ， 并且， 若 ｍ′⊆ｎ′且ｍ′≠ ｎ′， 则 有 ｇＩｎ；ｇ \ｍ⇌ ｇ↙ｍ 并且 ｇ↗ｍ。 定理 ２ ［１１］ 下面断言对每个背景都成立： １） 对象概念（ｇ * ′， ｇ * ）是并不可约元⇌存在一 个 ｍ∈Ｍ，使 ｇ↙ｍ； ２） 属性概念（ｍ′，ｍ′ * ）是交不可约元⇌存在一 个 ｇ∈Ｇ，使 ｇ↗ｍ； 下面断言对每个有限背景都成立： ３） 对象概念（ ｇ * ′，ｇ * ）是并不可约元⇌存在一 个 ｍ∈Ｍ，使 ｇ \ｍ； ４） 属性概念（ｍ′， ｍ′ * ）是交不可约元⇌存在一 个 ｇ∈Ｇ，使 ｇ \ｍ。 记：ＬＧ（Ｇ，Ｍ，Ｉ）＝ ｛Ｘ |（Ｘ，Ｂ）∈Ｌ（Ｇ，Ｍ，Ｉ）｝是概 念格 Ｌ（Ｇ，Ｍ，Ｉ）所有外延构成的集合； ＬＭ（Ｇ，Ｍ，Ｉ）＝ ｛Ｂ |（Ｘ，Ｂ）∈Ｌ（Ｇ，Ｍ，Ｉ）｝是概念 格 Ｌ（Ｇ，Ｍ，Ｉ）所有内涵构成的集合； ＪＧ（Ｌ）＝ ｛Ｘ |（Ｘ，Ｂ）∈Ｊ（ Ｌ）｝为概念格 Ｌ（Ｇ，Ｍ， Ｉ）的并不可约元的外延集； ＭＭ（Ｌ）＝ ｛Ｂ |（Ｘ，Ｂ） ∈Ｍ（ Ｌ）｝ 为概念格 Ｌ（Ｇ， Ｍ，Ｉ）的交不可约元的内涵集。 ２ 基于不可约元下集格的概念获取 本节主要给出通过不可约元做下集格， 再定义 映射找到全部概念的方法。 首先， 根据定义 ６ 确定 形式背景中的箭头关系， 根据定理 ２ 找到该形式背 景所对应概念格的并不可约元， 其次对并不可约元 的外延集做下集格， 再对下集格中的元素定义映 射， 从而得到概念格的全部内涵集， 进一步得到全 部概念。 利用对偶性， 对交不可约元的内涵集做下 集格， 定义相应的映射， 得到概念格的全部外延 集， 进而得到所有概念。 定义映射 ｆ １ ： ο（ＪＧ（Ｌ））→ＬＭ（ＪＧ（Ｌ））如下： ∀ χ∈ο（ＪＧ（Ｌ））， ｆ １（χ）＝ ∩Ｘｉ * ＝ （∪Ｘｉ） * ， Ｘｉ∈χ， 且将 ο（ＪＧ（Ｌ））中所有元素的像集记为 ＬＭ（ＪＧ（Ｌ））。 性质 １ 映射 ｆ １ ： ο（ＪＧ（Ｌ））→ＬＭ（ＪＧ（Ｌ））具有以 第 ２ 期 石慧，等：基于不可约元下集格的概念获取 ·２４５·
·246 智能系统学报 第9卷 下性质：1)是满射；2)f1具有逆序性，即HX1,X2∈ o(M(L),使X=A'。所以有X∈Lc(G,M,I)。 o(J(L)),若X,CX2,则f(X2)二f(X)。 另一方面：VYELG(G,M,I),设C=,显然有 证明1)根据f的定义，L,(Jc(L)中的元素 (Y,C)∈L(G,M,I)。由于概念格中的每一对概念都 均是由o(J(L))中元素的元素取并然后做*运算 可以由交不可约元的交得到。从而3C∈o(M(L)), 得到的。即VB∈L(Jc(L)),3X∈o(Jc(L))使f C=UC,(C:∈C)。又由于Y∈Le(G,M,I),C'= (X)=B; Y'=Y,因此YeLe(Mw(L),得证。 2)当X,≤X2时有UCX CUX,X,∈X,X∈ 该结论表明：交不可约元属性集的下集格经∫映 X2。由于f(X)=(UX)(X∈X),且*算子有逆序 射后得到的集合为相应概念格的外延集。进一步，可对 性，即对X,CX2,有X2*二X,从而有：(X2)二 所有外延做算子得到相应的内涵，进而得到概念。 f(X)。 例1形式背景(G,M,I)如表1所示，其中G= 定理3Lw(Je(L)=Lm(G,M,I)。 {1,2,3,4,5},M={a,b,c,d,e}。 证明一方面：HB∈Lw(Je(L),3x∈ 表1形式背景(G,M,) o(Jc(L)),使f(X)=B,令X=UX,(X:eX)。即 Table 1 Formal context (G,M,/) 有X=B。又根据*算子的性质知道X=X,即] 序号a 1 X∈o(Jc(L)),使B=X。所以有B∈Lw(G,M,I)。 另一方面：HA∈Lw(G,M,I),设y=A',显然 3 有(y,A)∈L(G,M,I)。由于概念格中的每一对概 5 念都可以由并不可约元的并得到。从而了y∈ 首先，根据定义2.6给出该形式背景的箭头关 o(Jc(L),y=UY,(Y:∈y)。又A∈Lw(G,M,I), 系，如表2所示。 X*=A=A,因此A∈L(J(L),得证。 表2箭头关系下的形式背景(G,M,I) 该结论表明：并不可约元外延集的下集格经f Table 2 Formal context (G,M,/)with the arrow relations 映射后得到的集合为相应概念格的内涵集。进一 序号a b c 步，可对所有内涵做'算子得到相应的外延，进而得 1 × 到概念。对偶地，下面给出从交不可约元出发获取 其下集格及所有概念的过程。 4 定义映射f2:o(Mw(L))→Le(Mw(L))如下： 由表2的箭头关系以及定理2，得到L(G,M,I) VA∈o(M(L),f3(X)=∩A;'=(UA)',A∈A, 且将o(Mv(L))中的所有元素的像集记为Le(Mw 的并不可约元为(1“，1)，(2'，2)，(3”，3*)， (L)) (4',4),(5',5)。即J(L)={(1,ace),(2, 性质2：o(Mu(L)一→Lc(M(L)具有以下 abde),(23,abe),(45,bcd)}。因此，Jc(L)=1{1}, 性质：1)2是满射：2)f具有逆序性，即HA1,A2∈o {2},2,3},{4,5}}。其Hasse图如图1所示： 23 (M(L)),若A,CA2,则f(A2)Cf(A1)。 证明1)根据方，的定义，Le(M,(L))中的元 素均是由o(M,(L)中元素的元素取并再做'运算 得到的。即HX∈Lc(M,(L)),3A∈o(Mw(L)使 f(A)=X。 图1Jc(L)的Hasse图 2)当ACA,时有UA:CUA,A:∈A1,A∈A20 Fig.1 Hasse of Jc(L) 由于f(A)=(UA)'且'算子有逆序性，即对A,二A2, 有A2'CA,',从而有：f(A2)∫(A1)。 根据Hasse图可得：o(Jc(L)={⑦，{1}}， 定理4Le(M(L))=Lc(G,M,I)。 {2},{4,5},{11},{2},{{1},{4,5},1{2}, 证明一方面：HX∈Le(Mw(L)),3A∈o {2,3}},{{2},14,5}},1{1},{2},{4,5}},112}, (Mv(L)),使f,(A)=X。令X=UA:,(A:∈X)。即有 {2,3},{4,5}},{1},{2},12,3}},{1},{2},{2, A'=X。又根据算子的性质，知道A'=A',即了A∈ 3},{4,5}}
下性质：１） ｆ １是满射；２） ｆ １具有逆序性， 即∀χ １ ， χ ２∈ ο（ＪＧ（Ｌ））， 若 χ １⊆χ ２ ， 则 ｆ １（χ ２ ）⊆ ｆ １（χ １ ）。 证明 １） 根据 ｆ １的定义， ＬＭ（ＪＧ（Ｌ））中的元素 均是由 ο（ＪＧ（Ｌ））中元素的元素取并然后做∗运算 得到的。 即 ∀Ｂ∈ＬＭ（ＪＧ（Ｌ））， ∃χ ∈ο（ＪＧ（Ｌ））使 ｆ １ （χ）＝ Ｂ； ２） 当 χ １⊆χ ２时有∪⊆Ｘｉ⊆∪Ｘｊ， Ｘｉ∈χ １ ， Ｘｊ∈ χ ２ 。 由于 ｆ １（χ） ＝ （∪Ｘ） * （Ｘ∈χ）， 且∗算子有逆序 性， 即对 Ｘ１⊆Ｘ２ ， 有 Ｘ２ *⊆ Ｘ１ * ， 从而有： ｆ １（ χ ２ ）⊆ ｆ １（χ １ ）。 定理 ３ ＬＭ（ＪＧ（Ｌ））＝ ＬＭ（Ｇ，Ｍ，Ｉ）。 证明 一 方 面： ∀Ｂ ∈ ＬＭ （ ＪＧ （ Ｌ ））， ∃χ ∈ ο（ＪＧ（Ｌ））， 使 ｆ １（χ）＝ Ｂ， 令 χ ＝ ∪Ｘｉ， （Ｘｉ∈χ）。 即 有 χ * ＝Ｂ。 又根据∗算子的性质知道 χ * ＝ χ * ′ * ， 即∃ χ∈ο（ＪＧ（Ｌ））， 使 Ｂ ＝ χ * ′ * 。 所以有 Ｂ∈ＬＭ（Ｇ，Ｍ，Ｉ）。 另一方面： ∀Ａ∈ＬＭ（Ｇ，Ｍ，Ｉ）， 设 ｙ ＝ Ａ′， 显然 有（ｙ，Ａ）∈ Ｌ（Ｇ，Ｍ，Ｉ）。 由于概念格中的每一对概 念都 可 以 由 并 不 可 约 元 的 并 得 到。 从 而 ∃ｙ ∈ ο（ＪＧ（Ｌ））， ｙ ＝∪Ｙｉ， （Ｙｉ∈ｙ）。 又 Ａ∈ＬＭ（Ｇ，Ｍ，Ｉ）， χ * ＝ Ａ′ * ＝ Ａ， 因此 Ａ∈ＬＭ（ＪＧ（Ｌ））， 得证。 该结论表明： 并不可约元外延集的下集格经 ｆ １ 映射后得到的集合为相应概念格的内涵集。 进一 步， 可对所有内涵做′算子得到相应的外延， 进而得 到概念。 对偶地， 下面给出从交不可约元出发获取 其下集格及所有概念的过程。 定义映射 ｆ ２ ：ο （ ＭＭ （ Ｌ）） →ＬＧ （ ＭＭ （ Ｌ）） 如下： ∀А∈ο（ＭＭ（ Ｌ））， ｆ ２（ χ） ＝ ∩Ａｊ ′ ＝ （∪Ａｊ ）′， Ａｊ∈Ａ， 且将 ο（ＭＭ （ Ｌ）） 中的所有元素的像集记为 ＬＧ （ＭＭ （Ｌ））。 性质 ２ ｆ ２ ： ο（ＭＭ（Ｌ））→ＬＧ（ＭＭ（Ｌ））具有以下 性质：１） ｆ ２是满射；２） ｆ ２具有逆序性， 即∀Ａ１ ， Ａ２∈ο （ＭＭ（Ｌ））， 若 Ａ１⊆Ａ２ ， 则 ｆ ２（Ａ２ ）⊆ｆ ２（Ａ１ ）。 证明 １） 根据 ｆ ２的定义， ＬＧ（ＭＭ（ Ｌ）） 中的元 素均是由 ο（ＭＭ（ Ｌ））中元素的元素取并再做′运算 得到的。 即∀Ｘ∈ＬＧ（ＭＭ（Ｌ））， ∃Ａ∈ο（ＭＭ（ Ｌ））使 ｆ ２（Ａ）＝ Ｘ。 ２）当 Ａ１⊆Ａ２时有∪Ａｉ⊆∪Ａｊ， Ａｉ∈Ａ１ ， Ａｊ∈Ａ２ 。 由于 ｆ ２（Ａ）＝ （∪Ａ）′且′算子有逆序性， 即对Ａ１⊆Ａ２ ， 有 Ａ２ ′⊆Ａ１ ′， 从而有： ｆ ２（Ａ２ ）⊆ｆ ２（Ａ１ ）。 定理 ４ ＬＧ（ＭＭ（Ｌ））＝ ＬＧ（Ｇ，Ｍ，Ｉ）。 证明 一方面： ∀Ｘ∈ＬＧ （ ＭＭ （ Ｌ））， ∃Ａ∈ο （ＭＭ（Ｌ））， 使 ｆ ２（Ａ）＝ Ｘ。 令 χ ＝∪Ａｉ， （Ａｉ∈χ）。 即有 Ａ′＝Ｘ。 又根据′算子的性质，知道 Ａ′＝ Ａ′ * ′， 即∃Ａ∈ ο（ＭＭ（Ｌ））， 使 Ｘ ＝ Ａ ′ * ′。 所以有 Ｘ∈ＬＧ（Ｇ，Ｍ，Ｉ）。 另一方面： ∀Ｙ∈ＬＧ（Ｇ，Ｍ，Ｉ）， 设 Ｃ ＝Ｙ * ， 显然有 （Ｙ，Ｃ）∈ Ｌ（Ｇ，Ｍ，Ｉ）。 由于概念格中的每一对概念都 可以由交不可约元的交得到。 从而∃Ｃ∈ο（ＭＭ（Ｌ））， Ｃ ＝ ∪Ｃｉ， （Ｃｉ ∈Ｃ）。 又由于 Ｙ∈ ＬＧ（Ｇ，Ｍ，Ｉ）， Ｃ′ ＝ Ｙ * ′＝Ｙ， 因此 Ｙ∈ＬＧ（ＭＭ（Ｌ））， 得证。 该结论表明： 交不可约元属性集的下集格经 ｆ ２映 射后得到的集合为相应概念格的外延集。 进一步，可对 所有外延做*算子得到相应的内涵， 进而得到概念。 例 １ 形式背景（Ｇ，Ｍ，Ｉ）如表 １ 所示， 其中 Ｇ ＝ ｛１，２，３，４，５｝， Ｍ＝ ｛ａ，ｂ，ｃ，ｄ，ｅ｝。 表 １ 形式背景（Ｇ，Ｍ，Ｉ） Ｔａｂｌｅ １ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （ Ｇ，Ｍ，Ｉ ） 序号 ａ ｂ ｃ ｄ ｅ １ × × × ２ × × × × ３ × × × ４ × × × ５ × × × 首先， 根据定义 ２．６ 给出该形式背景的箭头关 系， 如表 ２ 所示。 表 ２ 箭头关系下的形式背景（ Ｇ，Ｍ，Ｉ ） Ｔａｂｌｅ ２ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （ Ｇ，Ｍ，Ｉ ） ｗｉｔｈ ｔｈｅ ａｒｒｏｗ ｒｅｌａｔｉｏｎｓ 序号 ａ ｂ ｃ ｄ ｅ １ × \ × ↙ × ２ × × \ × × ３ × × ↗ \ × ４ \ × × × \ ５ \ × × × \ 由表 ２ 的箭头关系以及定理 ２， 得到 Ｌ（Ｇ，Ｍ，Ｉ） 的并不可约元为 （１ * ′， １ * ）， （２ * ′， ２ * ）， （３ * ′， ３ * ）， （４ * ′， ４ * ）， （５ * ′， ５ * ）。 即 Ｊ（ Ｌ） ＝ ｛（１， ａｃｅ）， （２， ａｂｄｅ）， （２３， ａｂｅ）， （４５， ｂｃｄ）｝。 因此， ＪＧ（Ｌ）＝ ｛｛１｝， ｛２｝， ｛２， ３｝， ｛４， ５｝｝。 其 Ｈａｓｓｅ 图如图 １ 所示： 图 １ ＪＧ（Ｌ）的 Ｈａｓｓｅ 图 Ｆｉｇ．１ Ｈａｓｓｅ ｏｆ ＪＧ（Ｌ） 根据 Ｈａｓｓｅ 图可得：ο （ ＪＧ （ Ｌ）） ＝ ｛ Æ，｛｛１｝｝， ｛｛２｝｝，｛｛４，５｝｝，｛｛１｝，｛２｝｝，｛｛１｝， ｛４，５｝｝，｛｛２｝， ｛２，３｝｝，｛｛２｝，｛４，５｝｝，｛｛１｝，｛２｝，｛４，５｝｝， ｛｛２｝， ｛２，３｝，｛４，５｝｝，｛｛１｝，｛２｝，｛２，３｝｝，｛｛１｝，｛２｝，｛２， ３｝，｛４，５｝｝｝。 ·２４６· 智 能 系 统 学 报 第 ９ 卷
第2期 石慧，等：基于不可约元下集格的概念获取 .247. X∈o(Je(L)),计算f(X),得到： 3不完备形式背景的完备化 Lu(Jc(L))=M,a,c,el,a,b,d,el,b,c, dl,la,el,Icl,la,b,el,ib,d,6,1. 在实际问题中，由于受到各种原因的影响，有 由定理3可知该属性集合为L(G,M,I)的全部内 可能导致形式背景的部分对象与属性之间出现关系 涵，扩充为概念后可得：L(G,M,I)={(O,M),(1, 缺失的现象，即这部分对象与属性之间是否存在关 ace),(2,abde),(45,bcd),(23,abe),(245,bd), 系无法获知，在概念格理论中，将这种含有缺失值 (145,c),(123,ae),(2345,b),(G,☑)}。 的形式背景称为不完备形式背景。针对不完备形式 概念格如图2所示： 背景，可以根据不完备形式背景的决策信息对缺失 的信息进行预测，从而将其补全为完备的形式背 (G,a) 景[)；也可以利用模糊关系的多划分技术，得到其 123ae)(2345,b)①45.c 完备化模型。本节给出基于前文方法的不完备 (1.ace) 形式背景的完备化。 (23abe)(245.bd0 (2,abde) (45,bcd) (G,3) (g,M) (123ae) (2345b)①45，c 图2L(G,M,I) (1,ace) (23.abe)(245.bd) Fig.2 L(G,M,1) (2 abde) (45,bcd) 对偶地，由表2的箭头关系以及定理2，得到L (G,M,I)的交不可约元为(a',a),(b',b*),(c', (0.M) c),(d',d"),(e',e"),即M(L)={(l23,ae), 图4L(G,M,) (2345,b),(145,c),(245,bd)}。因此，Mw(L)= Fig.4 L(G,M,1) {{a,e},{b},{c,{b,d{。其Hase图如图3所示： 在本节中，不完备形式背景的缺失信息用#表 bd 达。将#全部替换为0，得到的形式背景记为(G,M, I1),相应的概念格记为L；将#全部替换为1，得到 的形式背景记为(G,M,12),相应的概念格记为L2 本节借用上节概念获取的方法，对不完备形式 背景的缺失信息进行补全。首先，分析形式背景 图3Mv(L)的Hasse图 (G,M,I1)与(G,M,2),由于其概念个数不同，概 念个数较多的信息系统所包含的信息要相对完整一 Fig.3 Mu(L) 些，因而选择从概念个数较多的形式背景出发对其 根据Hasse图，可得 完备化；然后，找到选择出形式背景并不可约元外 o(Mw(L))={⑦，{{a,e}},{{b}},{{c}}, 延集的下集格，并对其中的元素在另一个形式背景 {a,e,{b}f,{{a,e},{c},{{b},{c},{{b, 上做映射f,得到象集后构造新集合；最后定义映 d,{b}},{a,e},{b,d},{b}},{a,e},{b}, 射将#映射为1或0。对偶地，找到其交不可约元的 {c},{b,d},{b},{c},{{a,e},1b,d,{b}, 内涵集，利用相似方法对其进行完备化。 {c}}。 定义集合P,={AIA∈Lw(Jc(L1)),X∈L1w(G, HA∈o(M(L),计算f,(A)得到 M,I1)且Hm∈M,A≠m*或A∈Lw(Jc(L,),A∈ Lc(M(L))=G,{1},{2},{4,5},{2,3},{2, L1w(G,M,I)且Hm∈M,A≠m“}。其中，L1(G, 4,5},{1,4,5},{1,2,3},{2,3,4,5},0}。 M,1)为L,的内涵集；m*为(G,M,I2)的属性概念 由定理4可知该对象集合为L(G,M,I)的全部 的内涵。 定义7映射h1:#→{0,1}如下： 外延。扩充为概念后可得：L(G,M,I)={(⑦，M), h1u(#)= (1,ace),(2,abde),(45,bcd),(23,abe),(245, (1,3x∈G,m∈E,E∈P1且I(x,m)=# bd),(145,c),(123,ae),(2345,b),(G,0)}。 (0,否则 概念格如图4所示
∀χ∈ο（ＪＧ（Ｌ））， 计算 ｆ １（χ）， 得到： ＬＭ（ＪＧ（Ｌ））＝ ｛Ｍ， ｛ａ，ｃ，ｅ｝， ｛ａ，ｂ，ｄ，ｅ｝， ｛ｂ，ｃ， ｄ｝， ｛ａ，ｅ｝， ｛ｃ｝， ｛ａ，ｂ，ｅ｝， ｛ｂ，ｄ｝， ｛ｂ｝， Æ｝。 由定理３ 可知该属性集合为 Ｌ（Ｇ，Ｍ，Ｉ）的全部内 涵，扩充为概念后可得：Ｌ（Ｇ，Ｍ，Ｉ）＝ ｛（Æ， Ｍ）， （１， ａｃｅ）， （２， ａｂｄｅ）， （４５， ｂｃｄ）， （２３， ａｂｅ）， （２４５， ｂｄ）， （１４５， ｃ）， （１２３， ａｅ）， （２３４５， ｂ）， （Ｇ， Æ）｝。 概念格如图 ２ 所示： 图 ２ Ｌ（Ｇ，Ｍ，Ｉ） Ｆｉｇ．２ Ｌ（Ｇ，Ｍ，Ｉ） 对偶地， 由表 ２ 的箭头关系以及定理 ２， 得到 Ｌ （Ｇ，Ｍ，Ｉ）的交不可约元为（ａ′， ａ′ * ）， （ｂ′，ｂ′ * ）， （ｃ′， ｃ′ * ）， （ｄ′，ｄ′ * ）， （ｅ′， ｅ′ * ）， 即 Ｍ（Ｌ） ＝ ｛（１２３， ａｅ）， （２３４５， ｂ）， （１４５， ｃ）， （２４５， ｂｄ）｝。 因此， ＭＭ（Ｌ）＝ ｛｛ａ，ｅ｝，｛ｂ｝，｛ｃ｝，｛ｂ，ｄ｝｝。 其 Ｈａｓｓｅ 图如图 ３ 所示： 图 ３ ＭＭ（Ｌ）的 Ｈａｓｓｅ 图 Ｆｉｇ．３ ＭＭ（Ｌ） 根据 Ｈａｓｓｅ 图， 可得 ο（ＭＭ （ Ｌ）） ＝ ｛ Æ， ｛｛ ａ， ｅ｝｝， ｛｛ ｂ｝｝， ｛｛ ｃ｝｝， ｛｛ａ，ｅ｝，｛ ｂ｝｝， ｛｛ ａ，ｅ｝，｛ ｃ｝｝，｛｛ ｂ｝，｛ ｃ｝｝，｛｛ ｂ， ｄ｝，｛ ｂ｝｝， ｛｛ ａ， ｅ｝， ｛ ｂ， ｄ｝， ｛ ｂ｝｝， ｛｛ ａ， ｅ｝， ｛ ｂ｝， ｛ｃ｝｝，｛｛ ｂ， ｄ｝， ｛ ｂ｝， ｛ ｃ｝｝， ｛｛ ａ， ｅ｝， ｛ ｂ， ｄ｝， ｛ ｂ｝， ｛ｃ｝｝｝。 ∀Ａ∈ο（ＭＭ（Ｌ））， 计算 ｆ ２（Ａ）得到 ＬＧ（ＭＭ（Ｌ））＝ ｛Ｇ，｛１｝，｛２｝，｛４，５｝，｛２，３｝，｛２， ４，５｝，｛１，４，５｝， ｛１，２，３｝，｛２，３，４，５｝，Æ｝。 由定理 ４ 可知该对象集合为 Ｌ（Ｇ，Ｍ，Ｉ）的全部 外延。 扩充为概念后可得：Ｌ（Ｇ，Ｍ，Ｉ） ＝ ｛（ Æ，Ｍ）， （１，ａｃｅ）， （ ２， ａｂｄｅ）， （ ４５， ｂｃｄ）， （ ２３， ａｂｅ）， （ ２４５， ｂｄ）， （ １４５， ｃ）， （ １２３， ａｅ）， （ ２３４５， ｂ）， （Ｇ， Æ）｝。 概念格如图 ４ 所示。 ３ 不完备形式背景的完备化 在实际问题中， 由于受到各种原因的影响， 有 可能导致形式背景的部分对象与属性之间出现关系 缺失的现象， 即这部分对象与属性之间是否存在关 系无法获知， 在概念格理论中， 将这种含有缺失值 的形式背景称为不完备形式背景。 针对不完备形式 背景， 可以根据不完备形式背景的决策信息对缺失 的信息进行预测， 从而将其补全为完备的形式背 景［１３］ ； 也可以利用模糊关系的多划分技术， 得到其 完备化模型［１４］ 。 本节给出基于前文方法的不完备 形式背景的完备化。 图 ４ Ｌ（Ｇ，Ｍ，Ｉ） Ｆｉｇ．４ Ｌ（Ｇ，Ｍ，Ｉ） 在本节中， 不完备形式背景的缺失信息用＃表 达。 将＃全部替换为 ０， 得到的形式背景记为（Ｇ，Ｍ， Ｉ１ ）， 相应的概念格记为 Ｌ１ ； 将＃全部替换为 １， 得到 的形式背景记为（Ｇ，Ｍ，Ｉ２ ）， 相应的概念格记为 Ｌ２ 。 本节借用上节概念获取的方法， 对不完备形式 背景的缺失信息进行补全。 首先， 分析形式背景 （Ｇ，Ｍ，Ｉ１ ）与（Ｇ，Ｍ，Ｉ２ ）， 由于其概念个数不同， 概 念个数较多的信息系统所包含的信息要相对完整一 些， 因而选择从概念个数较多的形式背景出发对其 完备化； 然后， 找到选择出形式背景并不可约元外 延集的下集格， 并对其中的元素在另一个形式背景 上做映射 ｆ １ ，得到象集后构造新集合； 最后定义映 射将＃映射为 １ 或 ０。 对偶地， 找到其交不可约元的 内涵集， 利用相似方法对其进行完备化。 定义集合 Ｐ１ ＝ ｛Ａ ｜ Ａ∈ＬＭ（ＪＧ（Ｌ１ ）），Ｘ∈Ｌ１ Ｍ（Ｇ， Ｍ，Ｉ１ ）且∀ ｍ∈Ｍ，Ａ≠ｍ′ *或 Ａ∈ＬＭ（ ＪＧ（ Ｌ１ ））， Ａ∈ Ｌ１ Ｍ（Ｇ，Ｍ，Ｉ１ ）且∀ ｍ∈Ｍ，Ａ≠ｍ′ * ｝。 其中， Ｌ１ Ｍ（Ｇ， Ｍ，Ｉ１ ）为 Ｌ１的内涵集； ｍ′ *为（Ｇ，Ｍ，Ｉ２ ）的属性概念 的内涵。 定义 ７ 映射 ｈ１１ ： ＃ → ｛０，１｝如下： ｈ１１（＃） ＝ １，∃ｘ ∈ Ｇ，ｍ ∈ Ｅ，Ｅ ∈ Ｐ１ 且 Ｉ（ｘ，ｍ） ＝ ＃ {０，否则 第 ２ 期 石慧，等：基于不可约元下集格的概念获取 ·２４７·
·248 智能系统学报 第9卷 定义集合Q,={XIX∈Le(Mw(L,),X年Lc 从形式背景(G,M,2)出发，对不完备形式背景(G, (G,M,I)且Hg∈G,X≠g'或X年Le(M(L,), M,I,#)完备化。 X∈L1c(G,M,I1)且Hg∈G,X≠g"。其中，L1c 3)概念格L,的并不可约元如下： (G,M,1)为L,的外延集；g为(G,M,12)的对象概 J(L2)={(1,acd),(2,bd),(3,ace),(4, 念的外延。 abe)}。 定义8映射h12:#一{0,1}如下： 4)将所有并不可约元的外延构成集合： h12(#)= Jc(L2)={{1},{2},{3},{4}。其Hasse图如图7 1,3m∈M,x∈F,F∈Q1且I(x,m)=# 所示。 (0,否则 表4(G,M,I) 相应地，定义集合P2={AIAEL(Jc(L2)),XL2w Table 4 Complete formal context(G,M,/) (G,M,L2)且Vm∈M,A≠m*或A生Lw(Jc(L2)), 序号a b c d e 1 001 0 A∈L2w(G,M,2)且Hm∈M,A≠m}。其中，L2M 2 0 1 0 0 0 (G,M,I2)为概念格L,的内涵集；m“为(G,M,I1)的 1 0 1 0 1 4 1001 属性概念的内涵。 表5(G,M,2) 定义9映射h21:#一{0,1}如下： Table 5 Complete formal context(G,M,/2) h21(#)= 序号 a b d e (0,3x∈G,m∈E,E∈P2且I(x,m)=# 1 0 1 0 1,否则 0 0 1 0 0 1 0 1 定义集合Q2={XIX∈Le(M(L2)),XL2c(G,M, 1 0 0 1 2)且Vg∈G,X≠g'或X生Lc(Mw(L2),X∈L2G (G②) (G,M,12)且Hg∈G,X≠g'}。其中，L2c(G,M, (134,a) I2)为概念格L,的外延集；g'为(G,M,11)的对象概 (24,b) 念的外延。 (1,ad0 (34.ae） 定义10映射h22:#→{0,1}如下： h2(#)= (3.ace) (4,abe) (0,3m∈M,x∈F,F∈Q2且I(x,m)=# 1,否则 (g.M0 例2表3给出了一个不完备形式背景(G,M, 图5概念格L, I,#),其中G={1,2,3,4},M={a,b,c,d,e。 Fig.5 L(G,M,1) 表3不完备形式背景(G,M,I,#) (G,⑦) Table 3 Incomplete formal context(G,M,/,#) (134,a)(12.d (24.b) 序号ab e 0#10 (34,ae)(13,ac) (2.bd0 2 0 1 0#0 3 10 10 1 (3.aee)(I.acd)/ (4,abe) 41100 1 (©，M) 表3中第1行的“#”符号，表示对象1是否拥 图6概念格L2 有属性c是不确定的：该表中第2行的“#”符号，表 Fig.6 L(G,M,1) 示对象2是否拥有属性d是不确定的。 下面将其完备化： 1)将不完备形式背景(G,M,I,#)中的#全部替 1234 换为0，得到形式背景(G,M,I1),如表4所示。将 图7Jc(L2)的Hasse图 不完备形式背景(G,M,I,#)中的#全部替换为1，得 Fig.7 Hasse of Jc(L2) 到形式背景(G,M,2),如表5所示。 5)Jc(L2)的下集格如下： 2)概念格L如图5所示，概念格L如图6所示： o(Je(L2))={0,{{1}},1{2}},1{3}, 显然，L,的概念多，所表达的信息更加完整，下面 {4}},1{1},{2}},{1},{3}},1{1},{4}
定义集合 Ｑ１ ＝ ｛Ｘ ｜ Ｘ∈ＬＧ （ＭＭ （ Ｌ１ ））， Ｘ∉Ｌ１ Ｇ （Ｇ，Ｍ，Ｉ１ ） 且∀ｇ∈Ｇ， Ｘ≠ｇ * ′或 Ｘ∉ＬＧ （ＭＭ （ Ｌ１ ））， Ｘ∈Ｌ１ Ｇ（Ｇ，Ｍ，Ｉ１ ） 且∀ ｇ∈Ｇ， Ｘ≠ｇ * ′｝。 其中， Ｌ１ Ｇ （Ｇ，Ｍ，Ｉ１ ）为 Ｌ１的外延集； ｇ * ′为（Ｇ，Ｍ，Ｉ２ ）的对象概 念的外延。 定义 ８ 映射 ｈ１ ２ ： ＃ → ｛０，１｝如下： ｈ１ ２ (＃) ＝ １，∃ｍ ∈ Ｍ，ｘ ∈ Ｆ，Ｆ ∈ Ｑ１ 且 Ｉ（ｘ，ｍ） ＝ ＃ {０，否则 相应地， 定义集合 Ｐ２ ＝ ｛Ａ ｜ Ａ∈ＬＭ（ＪＧ（Ｌ２ ））， Ｘ∉Ｌ２ Ｍ （Ｇ，Ｍ，Ｉ２ ）且∀ｍ∈Ｍ， Ａ≠ｍ′ *或 Ａ∉ＬＭ（ ＪＧ（ Ｌ２ ））， Ａ∈Ｌ２ Ｍ（Ｇ，Ｍ，Ｉ２ ）且∀ ｍ∈Ｍ， Ａ≠ｍ′ * ｝。 其中， Ｌ２ Ｍ （Ｇ，Ｍ，Ｉ２ ）为概念格 Ｌ２的内涵集； ｍ′ *为（Ｇ，Ｍ，Ｉ１ ）的 属性概念的内涵。 定义 ９ 映射 ｈ２１ ： ＃ → ｛０，１｝如下： ｈ２１ (＃) ＝ ０，∃ｘ ∈ Ｇ，ｍ ∈ Ｅ，Ｅ ∈ Ｐ２ 且 Ｉ(ｘ，ｍ) ＝ ＃ {１，否则 定义集合 Ｑ２ ＝ ｛Ｘ ｜ Ｘ∈ＬＧ（ＭＭ（Ｌ２ ））， Ｘ∉Ｌ２ Ｇ（Ｇ，Ｍ， Ｉ２ ）且∀ｇ∈Ｇ， Ｘ≠ｇ * ′或 Ｘ∉ＬＧ（ＭＭ（ Ｌ２ ））， Ｘ∈Ｌ２ Ｇ （Ｇ，Ｍ，Ｉ２ ）且∀ ｇ∈Ｇ， Ｘ≠ｇ * ′｝。 其中， Ｌ２ Ｇ （Ｇ，Ｍ， Ｉ２ ）为概念格 Ｌ２的外延集； ｇ * ′为（Ｇ，Ｍ，Ｉ１ ）的对象概 念的外延。 定义 １０ 映射 ｈ２２ ： ＃ → ｛０，１｝如下： ｈ２２ (＃) ＝ ０，∃ｍ ∈ Ｍ，ｘ ∈ Ｆ，Ｆ ∈ Ｑ２ 且 Ｉ(ｘ，ｍ) ＝ ＃ {１，否则 例 ２ 表 ３ 给出了一个不完备形式背景（Ｇ，Ｍ， Ｉ，＃）， 其中 Ｇ ＝ ｛１，２，３，４｝， Ｍ＝ ｛ａ，ｂ，ｃ，ｄ，ｅ｝。 表 ３ 不完备形式背景（Ｇ，Ｍ，Ｉ，＃） Ｔａｂｌｅ ３ Ｉｎｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （Ｇ，Ｍ，Ｉ，＃） 序号 ａ ｂ ｃ ｄ ｅ １ １ ０ ＃ １ ０ ２ ０ １ ０ ＃ ０ ３ １ ０ １ ０ １ ４ １ １ ０ ０ １ 表 ３ 中第 １ 行的“ ＃”符号， 表示对象 １ 是否拥 有属性 ｃ 是不确定的；该表中第 ２ 行的“＃”符号， 表 示对象 ２ 是否拥有属性 ｄ 是不确定的。 下面将其完备化： １）将不完备形式背景（Ｇ，Ｍ，Ｉ，＃）中的＃全部替 换为 ０，得到形式背景（Ｇ，Ｍ，Ｉ１ ）， 如表 ４ 所示。 将 不完备形式背景（Ｇ，Ｍ，Ｉ，＃）中的＃全部替换为 １，得 到形式背景（Ｇ，Ｍ，Ｉ２ ）， 如表 ５ 所示。 ２）概念格 Ｌ１如图５ 所示，概念格 Ｌ２如图６ 所示： 显然， Ｌ２的概念多， 所表达的信息更加完整， 下面 从形式背景（Ｇ，Ｍ，Ｉ２ ）出发， 对不完备形式背景（Ｇ， Ｍ，Ｉ，＃）完备化。 ３）概念格 Ｌ２的并不可约元如下： Ｊ（ Ｌ２ ） ＝ ｛（ １， ａｃｄ）， （ ２， ｂｄ）， （ ３， ａｃｅ）， （ ４， ａｂｅ）｝。 ４） 将 所 有 并 不 可 约 元 的 外 延 构 成 集 合： ＪＧ（Ｌ２ ）＝ ｛｛１｝，｛２｝，｛３｝，｛４｝｝。 其 Ｈａｓｓｅ 图如图 ７ 所示。 表 ４ （Ｇ，Ｍ，Ｉ１ ） Ｔａｂｌｅ ４ Ｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （Ｇ，Ｍ，Ｉ１ ） 序号 ａ ｂ ｃ ｄ ｅ １ １ ０ ０ １ ０ ２ ０ １ ０ ０ ０ ３ １ ０ １ ０ １ ４ １ １ ０ ０ １ 表 ５ （Ｇ，Ｍ，Ｉ２ ） Ｔａｂｌｅ ５ Ｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （Ｇ，Ｍ，Ｉ２ ） 序号 ａ ｂ ｃ ｄ ｅ １ １ ０ １ １ ０ ２ ０ １ ０ １ ０ ３ １ ０ １ ０ １ ４ １ １ ０ ０ １ 图 ５ 概念格 Ｌ １ Ｆｉｇ．５ Ｌ（Ｇ，Ｍ，Ｉ） 图 ６ 概念格 Ｌ２ Ｆｉｇ．６ Ｌ（Ｇ，Ｍ，Ｉ） 图 ７ ＪＧ（Ｌ２ ） 的 Ｈａｓｓｅ 图 Ｆｉｇ．７ Ｈａｓｓｅ ｏｆ ＪＧ（Ｌ２ ） ５） ＪＧ（Ｌ２ ） 的下集格如下： ο（ ＪＧ （ Ｌ２ ）） ＝ ｛ Æ ， ｛｛ １ ｝｝， ｛｛ ２ ｝｝， ｛｛ ３ ｝｝， ｛｛４｝｝， ｛｛ １｝， ｛ ２｝｝， ｛｛ １｝， ｛ ３｝｝， ｛｛ １｝， ｛ ４｝｝， ·２４８· 智 能 系 统 学 报 第 ９ 卷
第2期 石慧，等：基于不可约元下集格的概念获取 .249. {12},{3}},1{2},{4}},{{3},{4},{{1},{2}, {1,3},{2}} {3},{{1},{2},{4}},11},{3},{4}},1{2}, 根据映射h22得到(1，c)=0,I(2,d)=0。从而得 13},{4}1,{1},{2,{3},{4}}}。 到补全后的完备的形式背景(G,M,,),如表7。 6)X∈o(J(L2),在形式背景(G,M,1)上 表7完备形式背景(G,M,山) 计算f(X),可得Lw(Jc(L2))={M,{a},{b},{a, Table 7 Complete formal context(G,M,) dl,la,el,la,c,el,la,b,ef,o 序号a 1 0 0 1 0 7)根据集合P2的定义，可得：P2={d,{a, 2 0 1 0 0 0 c},{b,d,{a,c,d}} 1 010 1 4 1 1 00 8)根据映射h2,得到1(1，c)=0,1(2,d)=0。从而 得到补全后的完备的形式背景(G,M,13)如表6所示： 最后，以看出基于2种不可约元的下集格完备 表6完备形式背景(G,M,) 化得到的形式背景相同。因而，将其作为最终完备 Table 6 Complete formal context (G,M,/) 化的结果。 序号a b c d e 001 0 4结束语 1 1 2 0 1 0 0 0 3 1 0 1 0 1 本文提出了一种通过并不可约元（交不可约 0 0 1 元)的下集格获取概念的方法。首先利用箭头关系 对偶地，从L,交不可约元出发对不完备形式背 找到该背景对应概念格的并不可约元（交不可约 景完备化。 元)，对并不可约元（交不可约元）的外延集（内涵 1)概念格L的交不可约元如下： 集)做下集格：其次对下集格中的元素做相应的运 M(L2)={{134,a},{12,d},{24,b},134, 算，得到的属性集合（对象集合）可证明就是概念格 ae},{13,ac}} 的内涵集（外延集）：最后将其扩充成为概念。此外， 2)将所有交不可约元的内涵构成集合：M(L2)= 根据这种概念获取的方法利用下集格已经将并不可 {a,{d,{b},{a,e},{a,c}。其Hasse图如图8所示： 约元（交不可约元）的并（交）经行了初步筛选，所 以对于不完备形式背景来说从概念较多的形式背景 (G,M,I1)或(G,M,I2)的并不可约元出发，在另 个形式背景上进行特定的映射，最后根据定义的映 射将其完备化。同样可以从交不可约元出发，对不 完备形式背景进行扩充。并且基于2种不可约元扩 图8Mw(L2)的Hasse图 充后的结果相同。 Fig.8 Hasse of Mu(L2) 3)Mw(L,)的下集格如下： 参考文献： o(Mw(L2))={②，{{a},{{b},{{d}}, [1]WILLE R.Restructuring lattices theory:an approach on hi- {{a},{b},{{b},{d},{{a},{d}},{a,e}, erarchies of concepts [M].Dordrecht,Holland:Springer, {ef},{a,c,{a},{a,{b},{d,{{a,e}, 1982:445-470. [2]CARPINETO C,ROMANO G.Concept data analysis:theo- {a},{b}},{{a,e},{a},{d},{a,c},{a}, ry and application[M].[S.I.]:John Wiley Sons,2004: {bl},{a,c,{a,{d}},{a,e},{a,c},{a}}, 21-35. {{b},{d,{a,e,{a}},{b},{d,{a,c},{a}}, [3]GODIN R.Incremental concept formation algorithm based on {{b},{a,e},{a,c},{a}},{{d},{a,e},{a,c}, Galois lattices []]Computational Intelligence,1995,11 (2)：246-267. {a},{{a},{b},{a,c},{d},{a,e}}} [4]HO T B.Discovering and using knowledge from unsuper- 4)HA∈o(M(L2)),在形式背景(G,M,I1)上 vised data [J].Decision Support System,1997,21(1): 计算f(A)可得：Lc(Mw(L2))={⑦，{1}，{3}，{4}， 29.42. {2,4},{3,4},{1,3,4},G [5]BELOHLAVEK R.fuzzy closure operators [J].Joumal of Mathematical Analysis and Applications,2001(262):473- 5)根据集合Q2的定义，可得：Q2={{1,2}, 489
｛｛２｝，｛３｝｝，｛｛２｝，｛４｝｝，｛｛３｝，｛４｝｝，｛｛１｝，｛２｝， ｛３｝｝，｛｛１｝，｛２｝，｛４｝｝，｛｛１｝，｛３｝，｛４｝｝， ｛｛２｝， ｛３｝，｛４｝｝， ｛｛１｝，｛２｝，｛３｝， ｛４｝｝｝。 ６）∀χ∈ο（ＪＧ（ Ｌ２ ））， 在形式背景（Ｇ，Ｍ，Ｉ１ ）上 计算 ｆ １（χ）， 可得 ＬＭ（ＪＧ（Ｌ２ ）） ＝ ｛Ｍ，｛ａ｝，｛ｂ｝，｛ ａ， ｄ｝，｛ａ，ｅ｝，｛ａ，ｃ，ｅ｝，｛ａ，ｂ，ｅ｝，Æ｝ ７）根据集合 Ｐ２ 的定义， 可得：Ｐ２ ＝ ｛｛ ｄ｝，｛ ａ， ｃ｝，｛ｂ，ｄ｝，｛ａ，ｃ，ｄ｝｝ ８）根据映射 ｈ２１得到 Ｉ（１，ｃ）＝ ０， Ｉ（２，ｄ）＝ ０。 从而 得到补全后的完备的形式背景（Ｇ，Ｍ，Ｉ３）如表 ６ 所示： 表 ６ 完备形式背景（Ｇ，Ｍ，Ｉ３ ） Ｔａｂｌｅ ６ Ｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （Ｇ，Ｍ，Ｉ３ ） 序号 ａ ｂ ｃ ｄ ｅ １ １ ０ ０ １ ０ ２ ０ １ ０ ０ ０ ３ １ ０ １ ０ １ ４ １ １ ０ ０ １ 对偶地， 从 Ｌ２交不可约元出发对不完备形式背 景完备化。 １）概念格 Ｌ２的交不可约元如下： Ｍ （ Ｌ２ ） ＝ ｛｛ １３４， ａ｝， ｛ １２， ｄ｝， ｛ ２４， ｂ｝， ｛ ３４， ａｅ｝，｛１３，ａｃ｝｝ ２）将所有交不可约元的内涵构成集合：ＭＭ （Ｌ２ ）＝ ｛｛ａ｝，｛ｄ｝，｛ｂ｝，｛ａ，ｅ｝，｛ａ，ｃ｝｝。 其Ｈａｓｓｅ 图如图８所示： 图 ８ ＭＭ（Ｌ２ ）的 Ｈａｓｓｅ 图 Ｆｉｇ．８ Ｈａｓｓｅ ｏｆ ＭＭ（Ｌ２ ） ３）ＭＭ（Ｌ２ ）的下集格如下： ο（ ＭＭ （ Ｌ２ ）） ＝ ｛ Æ， ｛｛ ａ｝｝， ｛｛ ｂ｝｝， ｛｛ ｄ｝｝， ｛｛ａ｝，｛ ｂ｝｝， ｛｛ ｂ｝，｛ ｄ｝｝，｛｛ ａ｝，｛ ｄ｝｝，｛｛ ａ，ｅ｝， ｛ｅ｝｝，｛｛ ａ，ｃ｝，｛ ａ｝｝，｛｛ ａ｝， ｛ ｂ｝，｛ ｄ｝｝，｛｛ ａ，ｅ｝， ｛ａ｝， ｛ ｂ｝｝， ｛｛ ａ， ｅ｝， ｛ ａ｝， ｛ ｄ｝｝， ｛｛ ａ， ｃ｝， ｛ ａ｝， ｛ｂ｝｝，｛｛ａ，ｃ｝，｛ ａ｝，｛ ｄ｝｝，｛｛ ａ，ｅ｝，｛ ａ，ｃ｝，｛ ａ｝｝， ｛｛ｂ｝，｛ｄ｝， ｛ａ，ｅ｝，｛ａ｝｝，｛｛ｂ｝，｛ｄ｝，｛ａ，ｃ｝，｛ａ｝｝， ｛｛ｂ｝，｛ａ，ｅ｝，｛ ａ，ｃ｝， ｛ ａ｝｝，｛｛ ｄ｝，｛ ａ，ｅ｝，｛ ａ，ｃ｝， ｛ａ｝｝，｛｛ａ｝，｛ｂ｝，｛ａ，ｃ｝，｛ｄ｝，｛ａ， ｅ｝｝｝ ４）∀Ａ∈ο（ＭＭ（Ｌ２ ））， 在形式背景（Ｇ，Ｍ，Ｉ１ ）上 计算 ｆ ２（Ａ）可得：ＬＧ（ＭＭ（Ｌ２ ））＝ ｛ Æ，｛１｝，｛３｝，｛４｝， ｛２，４｝，｛３，４｝，｛１，３，４｝， Ｇ｝ ５）根据集合 Ｑ２ 的定义， 可得： Ｑ２ ＝ ｛｛ １，２｝， ｛１，３｝，｛２｝｝ 根据映射 ｈ２２得到 Ｉ（１，ｃ）＝ ０， Ｉ（２，ｄ）＝ ０。 从而得 到补全后的完备的形式背景（Ｇ，Ｍ，Ｉ４），如表 ７。 表 ７ 完备形式背景（Ｇ，Ｍ，Ｉ４ ） Ｔａｂｌｅ ７ Ｃｏｍｐｌｅｔｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （Ｇ，Ｍ，Ｉ４ ） 序号 ａ ｂ ｃ ｄ ｅ １ １ ０ ０ １ ０ ２ ０ １ ０ ０ ０ ３ １ ０ １ ０ １ ４ １ １ ０ ０ １ 最后， 以看出基于 ２ 种不可约元的下集格完备 化得到的形式背景相同。 因而， 将其作为最终完备 化的结果。 ４ 结束语 本文提出了一种通过并不可约元（ 交不可约 元）的下集格获取概念的方法。 首先利用箭头关系 找到该背景对应概念格的并不可约元（交不可约 元）， 对并不可约元（交不可约元）的外延集（内涵 集）做下集格； 其次对下集格中的元素做相应的运 算， 得到的属性集合（对象集合）可证明就是概念格 的内涵集（外延集）；最后将其扩充成为概念。 此外， 根据这种概念获取的方法利用下集格已经将并不可 约元（交不可约元）的并（交）经行了初步筛选， 所 以对于不完备形式背景来说从概念较多的形式背景 （Ｇ，Ｍ，Ｉ１ ）或（Ｇ，Ｍ，Ｉ２ ）的并不可约元出发， 在另一 个形式背景上进行特定的映射，最后根据定义的映 射将其完备化。 同样可以从交不可约元出发，对不 完备形式背景进行扩充。 并且基于 ２ 种不可约元扩 充后的结果相同。 参考文献： ［１］ＷＩＬＬＥ Ｒ． Ｒｅｓｔｒｕｃｔｕｒｉｎｇ ｌａｔｔｉｃｅｓ ｔｈｅｏｒｙ： ａｎ ａｐｐｒｏａｃｈ ｏｎ ｈｉ⁃ ｅｒａｒｃｈｉｅｓ ｏｆ ｃｏｎｃｅｐｔｓ ［Ｍ］． Ｄｏｒｄｒｅｃｈｔ， Ｈｏｌｌａｎｄ： Ｓｐｒｉｎｇｅｒ， １９８２： ４４５⁃４７０． ［２］ＣＡＲＰＩＮＥＴＯ Ｃ， ＲＯＭＡＮＯ Ｇ． Ｃｏｎｃｅｐｔ ｄａｔａ ａｎａｌｙｓｉｓ： ｔｈｅｏ⁃ ｒｙ ａｎｄ ａｐｐｌｉｃａｔｉｏｎ［Ｍ］． ［Ｓ．ｌ．］：Ｊｏｈｎ Ｗｉｌｅｙ ＆ Ｓｏｎｓ， ２００４： ２１⁃３５． ［ ３］ＧＯＤＩＮ Ｒ． Ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｃｅｐｔ ｆｏｒｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｇａｌｏｉｓ ｌａｔｔｉｃｅｓ ［ Ｊ］． Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９５， １１ （２）： ２４６⁃２６７． ［４］ ＨＯ Ｔ Ｂ ． Ｄｉｓｃｏｖｅｒｉｎｇ ａｎｄ ｕｓｉｎｇ ｋｎｏｗｌｅｄｇｅ ｆｒｏｍ ｕｎｓｕｐｅｒ⁃ ｖｉｓｅｄ ｄａｔａ ［ Ｊ］． Ｄｅｃｉｓｉｏｎ Ｓｕｐｐｏｒｔ Ｓｙｓｔｅｍ， １９９７， ２１（ １）： ２９⁃４２． ［５］ ＢＥＬＯＨＬＡＶＥＫ Ｒ． ｆｕｚｚｙ ｃｌｏｓｕｒｅ ｏｐｅｒａｔｏｒｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｍａｔｈｅｍａｔｉｃａｌ Ａｎａｌｙｓｉｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００１（２６２）： ４７３⁃ ４８９． 第 ２ 期 石慧，等：基于不可约元下集格的概念获取 ·２４９·
·250 智能系统学报 第9卷 [6]NOURINE L,RAYNAUD O.A fast algorithm for building [14]康向平，李德玉，李瑞萍.基于多划分的不完备信息系 lattices [J].Information Processing Letters,1999,47: 统的完备化模型[J].计算机工程与设计，2011(9)： 111-112 3131-3134 [7]BODAT J P.Calcul pratique du treillis de galois d'ume cor- KANG Xiangping,LI Deyu,LI Ruiping.Completion model respondence [J].Math Sci Hum,1986,96:31-47. of incomplete information system based on multiple-parti- [8]HO T B.Incremental conceptual clustering in the framework tions[J].Computer Engineering and Design,2011(9): of galois lattice[C]//Proceedings of First Pacific-Asia Con- 3131.3134 ference.Knowledge Discovery and Data Mining:Techniques 作者简介： and Applications.[S.1.],1997:49-64. 石慧，女，1990年生，硕士研究生， [9]李云，刘宗田，陈鲮，等.多概念格的横向合并算法[J] 主要研究方向为形式概念分析、粗糙 电子学报，2004,32(11)：1847-1854. 集。 LI Yun,LIU Zongtian,CHEN Ling.Horizontal union algo- rithm of multiple concept lattices[J].Acta Electronica Sini- ca,2004,32(11):1847-1854. [10]万青，魏玲，李涛.一种基于并不可约元的建格新方法 [J].西北大学学报，2013,43(1)：10-14 何苗，女，1987年生，硕士研究生 WAN Qing,WEI Ling,LI Tao.A new method of building 主要研究方向为形式概念分析、粗糙 lattice based on join-irreducible[J].Journal of Northwest 集。 University:Natural Science Edition,2013,43(1):10- 14. [11]GANTER B,WILLE R.Formal Concept Analysis M]. Mathematical Foundations.SpringerVerlag,New York, 1999:21-24. 魏玲，女，1972年生，教授，博士生 [12]DAVEY B A,PRIESTLEY H A.Introduction to lattices 导师，主要研究方向为形式概念分析、 and order[M].Cambridge:Cambridge University Press, 粗糙集，概率论等。主持和参与国家自 2002. 然科学基金、陕西省教育厅自然科学专 [13]李金海.面向规则提取的概念格约简方法及其算法实现 项基金等多项。 [D].西安：西安交通大学，2012：45-63. LI Jinhai.Acquisition oriented reduction methods for con- cept lattices and their implementation algorithms D]. Xi'an:Xi'an Jiao Tong University,2012:45-63
［６］ ＮＯＵＲＩＮＥ Ｌ， ＲＡＹＮＡＵＤ Ｏ． Ａ ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｕｉｌｄｉｎｇ ｌａｔｔｉｃｅｓ ［ Ｊ ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｌｅｔｔｅｒｓ， １９９９， ４７： １１１⁃１１２． ［７］ＢＯＤＡＴ Ｊ Ｐ． Ｃａｌｃｕｌ ｐｒａｔｉｑｕｅ ｄｕ ｔｒｅｉｌｌｉｓ ｄｅ ｇａｌｏｉｓ ｄ’ｕｍｅ ｃｏｒ⁃ ｒｅｓｐｏｎｄｅｎｃｅ ［Ｊ］． Ｍａｔｈ Ｓｃｉ Ｈｕｍ， １９８６， ９６： ３１⁃４７． ［８］ＨＯ Ｔ Ｂ． Ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｃｅｐｔｕａｌ ｃｌｕｓｔｅｒｉｎｇ ｉｎ ｔｈｅ ｆｒａｍｅｗｏｒｋ ｏｆ ｇａｌｏｉｓ ｌａｔｔｉｃｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｆｉｒｓｔ Ｐａｃｉｆｉｃ⁃Ａｓｉａ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ． Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ： Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ． ［Ｓ．ｌ．］， １９９７： ４９⁃６４． ［９］李云， 刘宗田， 陈崚， 等． 多概念格的横向合并算法［Ｊ］． 电子学报， ２００４， ３２ （１１） ： １８４７⁃１８５４． ＬＩ Ｙｕｎ， ＬＩＵ Ｚｏｎｇｔｉａｎ， ＣＨＥＮ Ｌｉｎｇ． Ｈｏｒｉｚｏｎｔａｌ ｕｎｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｏｆ ｍｕｌｔｉｐｌｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｓ［Ｊ］． Ａｃｔａ Ｅｌｅｃｔｒｏｎｉｃａ Ｓｉｎｉ⁃ ｃａ， ２００４， ３２ （１１） ： １８４７⁃１８５４． ［１０］万青， 魏玲， 李涛． 一种基于并不可约元的建格新方法 ［Ｊ］． 西北大学学报， ２０１３， ４３ （１） ： １０⁃１４． ＷＡＮ Ｑｉｎｇ， ＷＥＩ Ｌｉｎｇ， ＬＩ Ｔａｏ． Ａ ｎｅｗ ｍｅｔｈｏｄ ｏｆ ｂｕｉｌｄｉｎｇ ｌａｔｔｉｃｅ ｂａｓｅｄ ｏｎ ｊｏｉｎ－ｉｒｒｅｄｕｃｉｂｌｅ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｎｏｒｔｈｗｅｓｔ Ｕｎｉｖｅｒｓｉｔｙ： Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ， ２０１３， ４３ （１） ： １０⁃ １４． ［１１］ＧＡＮＴＥＲ Ｂ， ＷＩＬＬＥ Ｒ． Ｆｏｒｍａｌ Ｃｏｎｃｅｐｔ Ａｎａｌｙｓｉｓ ［ Ｍ］． Ｍａｔｈｅｍａｔｉｃａｌ Ｆｏｕｎｄａｔｉｏｎｓ． ＳｐｒｉｎｇｅｒＶｅｒｌａｇ， Ｎｅｗ Ｙｏｒｋ， １９９９：２１⁃２４． ［１２］ ＤＡＶＥＹ Ｂ Ａ， ＰＲＩＥＳＴＬＥＹ Ｈ Ａ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｌａｔｔｉｃｅｓ ａｎｄ ｏｒｄｅｒ［ Ｍ］． Ｃａｍｂｒｉｄｇｅ： Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， ２００２． ［１３］李金海．面向规则提取的概念格约简方法及其算法实现 ［Ｄ］． 西安： 西安交通大学， ２０１２： ４５⁃６３． ＬＩ Ｊｉｎｈａｉ． Ａｃｑｕｉｓｉｔｉｏｎ ｏｒｉｅｎｔｅｄ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ ｃｏｎ⁃ ｃｅｐｔ ｌａｔｔｉｃｅｓ ａｎｄ ｔｈｅｉｒ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ［ Ｄ ］． Ｘｉ＇ａｎ： Ｘｉ＇ａｎ Ｊｉａｏ Ｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２０１２： ４５⁃６３． ［１４］康向平， 李德玉， 李瑞萍． 基于多划分的不完备信息系 统的完备化模型［ Ｊ］． 计算机工程与设计， ２０１１（ ９）： ３１３１⁃３１３４． ＫＡＮＧ Ｘｉａｎｇｐｉｎｇ， ＬＩ Ｄｅｙｕ， ＬＩ Ｒｕｉｐｉｎｇ． Ｃｏｍｐｌｅｔｉｏｎ ｍｏｄｅｌ ｏｆ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｍｕｌｔｉｐｌｅ－ｐａｒｔｉ⁃ ｔｉｏｎｓ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｄｅｓｉｇｎ， ２０１１ （ ９）： ３１３１⁃３１３４． 作者简介： 石慧，女，１９９０ 年生，硕士研究生， 主要研究方向为形式概念分析、粗糙 集。 何苗，女，１９８７ 年生，硕士研究生， 主要研究方向为形式概念分析、粗糙 集。 魏玲，女，１９７２ 年生，教授，博士生 导师，主要研究方向为形式概念分析、 粗糙集，概率论等。 主持和参与国家自 然科学基金、陕西省教育厅自然科学专 项基金等多项。 ·２５０· 智 能 系 统 学 报 第 ９ 卷