第10卷第6期 智能系统学报 Vol.10 No.6 2015年12月 CAAI Transactions on Intelligent Systems Dee.2015 D0L:10.11992/is.201507063 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.024.html 一种基于最大满矩阵生成概念格的算法 郭伦众，宋振明 (西南交通大学数学学院，四川成都610097) 摘要：形式概念分析的核心是概念格，它在本质上描述了对象和属性之间的联系，表明了概念之间的泛化和 例化关系，因此概念格的构造就显得尤为的重要。从形式背景的关系矩阵出发，扫描形式背景的行和列找出 属性值为1的全部满矩阵，定义了最大满矩阵的概念，证明了最大满矩阵是概念矩阵的充要条件。并在此理 论上提出了一种基于最大满矩阵生成概念格的算法，并对所提出的算法进行了理论论证。通过实例的运算， 验证了该算法的有效性。 关键词：概念：形式概念分析：矩阵：算法 中图分类号：TP18文献标志码：A文章编号：1673-4785(2015)06-0838-05 中文引用格式：郭伦众，宋振明.一种基于最大满矩阵生成概念格的算法[J].智能系统学报，2015,10(6)：838-842. 英文引用格式：GUO Lunzhong,SONG Zhenming.A novel concept-lattice acquisition approach based on the greatest full matri本of formal context[J].CAAI Transactions on Intelligent Systems,2015,10(6):838-842. A novel concept-lattice acquisition approach based on the greatest full matrix of formal context GUO Lunzhong,SONG Zhenming School of Mathematics,Southwest Jiaotong University,Chengdu 610097,China) Abstract:The concept lattice plays a crucial role in formal concept analysis,which describes essential object rela- tions and attributes and illustrates the relation between generalization and specialization.Therefore,the development of effective methods for generating a concept lattice has been an important research topic.Based on the relational matrix of formal context,the rows and columns of the formal context are scanned to identify the full matrix.In this study,we define the concept of the greatest full matrix,and we prove that the greatest full matrix is a necessary and sufficient condition for the concept matrix.We also propose and theoretically demonstrate a concept-lattice genera- tion algorithm based on the greatest full matrix.Finally,we provide an example to illustrate the rationality and ef- fectiveness of the proposed algorithm. Keywords:concept;formal concept analysis;matrix;algorithm 20世纪80年代初，德国的Wille授提出了形 念格的构造效率就成为人们一直关注的焦点，提出 式概念分析理论)。到目前，概念格作为形式概念 了许多的构造算法。例如：Godin)提出了概念格的 分析的核心数据结构，已经成为一种用于数据组织 渐进生成算法：T.B.Ho)提出了基于概念格的概念 和数据分析的形式化工具，在数字图书馆及文献检 聚类算法：刘宗田等s)对Godin算法进行了改进：林 索、软件工程、数据挖掘等许多领域得到了广泛应 春杰等[6提出了基于不完备信息的近似概念格改 用2)]。概念格的构造是应用概念格的前提，因此概 进的概念格增量构造算法：李海霞]提出了基于概 念格Hasse图的一种对象渐减式构造算法；崔芳婷 收稿日期：2015-06-30.网络出版日期：2015-11-10 基金项目：国家自然科学基金资助项目(61175055). 等[]根据用户的需求，把用户感兴趣的背景知识定 通信作者：郭伦众.E-mail:18380106827@163.com. 义为约束，提出一种基于约束的模糊概念格构造算
第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０７０６３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１０．１３５４．０２４．ｈｔｍｌ 一种基于最大满矩阵生成概念格的算法 郭伦众，宋振明 （西南交通大学 数学学院，四川 成都 ６１００９７） 摘 要：形式概念分析的核心是概念格，它在本质上描述了对象和属性之间的联系，表明了概念之间的泛化和 例化关系，因此概念格的构造就显得尤为的重要。 从形式背景的关系矩阵出发，扫描形式背景的行和列找出 属性值为 １ 的全部满矩阵，定义了最大满矩阵的概念，证明了最大满矩阵是概念矩阵的充要条件。 并在此理 论上提出了一种基于最大满矩阵生成概念格的算法，并对所提出的算法进行了理论论证。 通过实例的运算， 验证了该算法的有效性。 关键词：概念；形式概念分析；矩阵；算法 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０８３８⁃０５ 中文引用格式：郭伦众，宋振明． 一种基于最大满矩阵生成概念格的算法［Ｊ］． 智能系统学报， ２０１５， １０（６）： ８３８⁃８４２． 英文引用格式：ＧＵＯ Ｌｕｎｚｈｏｎｇ， ＳＯＮＧ Ｚｈｅｎｍｉｎｇ． Ａ ｎｏｖｅｌ ｃｏｎｃｅｐｔ⁃ｌａｔｔｉｃｅ ａｃｑｕｉｓｉｔｉｏｎ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｒｅａｔｅｓｔ ｆｕｌｌ ｍａｔｒｉｘ ｏｆ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ８３８⁃８４２． Ａ ｎｏｖｅｌ ｃｏｎｃｅｐｔ⁃ｌａｔｔｉｃｅ ａｃｑｕｉｓｉｔｉｏｎ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｒｅａｔｅｓｔ ｆｕｌｌ ｍａｔｒｉｘ ｏｆ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ＧＵＯ Ｌｕｎｚｈｏｎｇ， ＳＯＮＧ Ｚｈｅｎｍｉｎｇ （ Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ， Ｓｏｕｔｈｗｅｓｔ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｃｈｅｎｇｄｕ ６１００９７， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｐｌａｙｓ ａ ｃｒｕｃｉａｌ ｒｏｌｅ ｉｎ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ， ｗｈｉｃｈ ｄｅｓｃｒｉｂｅｓ ｅｓｓｅｎｔｉａｌ ｏｂｊｅｃｔ ｒｅｌａ⁃ ｔｉｏｎｓ ａｎｄ ａｔｔｒｉｂｕｔｅｓ ａｎｄ ｉｌｌｕｓｔｒａｔｅｓ ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ａｎｄ ｓｐｅｃｉａｌｉｚａｔｉｏｎ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｅｆｆｅｃｔｉｖｅ ｍｅｔｈｏｄｓ ｆｏｒ ｇｅｎｅｒａｔｉｎｇ ａ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｈａｓ ｂｅｅｎ ａｎ ｉｍｐｏｒｔａｎｔ ｒｅｓｅａｒｃｈ ｔｏｐｉｃ． Ｂａｓｅｄ ｏｎ ｔｈｅ ｒｅｌａｔｉｏｎａｌ ｍａｔｒｉｘ ｏｆ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ， ｔｈｅ ｒｏｗｓ ａｎｄ ｃｏｌｕｍｎｓ ｏｆ ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ａｒｅ ｓｃａｎｎｅｄ ｔｏ ｉｄｅｎｔｉｆｙ ｔｈｅ ｆｕｌｌ ｍａｔｒｉｘ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｗｅ ｄｅｆｉｎｅ ｔｈｅ ｃｏｎｃｅｐｔ ｏｆ ｔｈｅ ｇｒｅａｔｅｓｔ ｆｕｌｌ ｍａｔｒｉｘ， ａｎｄ ｗｅ ｐｒｏｖｅ ｔｈａｔ ｔｈｅ ｇｒｅａｔｅｓｔ ｆｕｌｌ ｍａｔｒｉｘ ｉｓ ａ ｎｅｃｅｓｓａｒｙ ａｎｄ ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎ ｆｏｒ ｔｈｅ ｃｏｎｃｅｐｔ ｍａｔｒｉｘ． Ｗｅ ａｌｓｏ ｐｒｏｐｏｓｅ ａｎｄ ｔｈｅｏｒｅｔｉｃａｌｌｙ ｄｅｍｏｎｓｔｒａｔｅ ａ ｃｏｎｃｅｐｔ－ｌａｔｔｉｃｅ ｇｅｎｅｒａ⁃ ｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｇｒｅａｔｅｓｔ ｆｕｌｌ ｍａｔｒｉｘ． Ｆｉｎａｌｌｙ， ｗｅ ｐｒｏｖｉｄｅ ａｎ ｅｘａｍｐｌｅ ｔｏ ｉｌｌｕｓｔｒａｔｅ ｔｈｅ ｒａｔｉｏｎａｌｉｔｙ ａｎｄ ｅｆ⁃ ｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ： ｃｏｎｃｅｐｔ； ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ； ｍａｔｒｉｘ； ａｌｇｏｒｉｔｈｍ 收稿日期：２０１５⁃０６⁃３０． 网络出版日期：２０１５⁃１１⁃１０． 基金项目：国家自然科学基金资助项目（６１１７５０５５）． 通信作者：郭伦众． Ｅ⁃ｍａｉｌ：１８３８０１０６８２７＠ １６３．ｃｏｍ． ２０ 世纪 ８０ 年代初， 德国的 Ｗｉｌｌｅ 授提出了形 式概念分析理论［１］ 。 到目前， 概念格作为形式概念 分析的核心数据结构， 已经成为一种用于数据组织 和数据分析的形式化工具， 在数字图书馆及文献检 索、软件工程、数据挖掘等许多领域得到了广泛应 用［２］ 。 概念格的构造是应用概念格的前提，因此概 念格的构造效率就成为人们一直关注的焦点，提出 了许多的构造算法。 例如：Ｇｏｄｉｎ ［３］提出了概念格的 渐进生成算法；Ｔ．Ｂ．Ｈｏ ［４］ 提出了基于概念格的概念 聚类算法；刘宗田等［５］对 Ｇｏｄｉｎ 算法进行了改进；林 春杰等［６］提出了基于不完备信息的近似概念格改 进的概念格增量构造算法；李海霞［７］ 提出了基于概 念格 Ｈａｓｓｅ 图的一种对象渐减式构造算法；崔芳婷 等［８］根据用户的需求，把用户感兴趣的背景知识定 义为约束，提出一种基于约束的模糊概念格构造算
第6期 郭伦众，等：一种基于最大满矩阵生成概念格的算法 ·839- 法：刘宏英等基于对多维序列的理解，提出一种 (A1,B),H2=(A2,B2)是K的2个概念，在概念集 新的多维概念格并给出了渐进式构造算法。本文首 L(U,M,I)上定义关系： 先将形式背景看成一个0、1的关系矩阵，然后将形 H1≤H2曰A,CA,(或B2CB,) 式背景化为既约的[o],最后提出了一种基于最大满 在概念集L(U,M,)上定义交并运算分别为 矩阵来获取概念格的算法。 (A1,B1)A(A2,B2)=(A1∩A2f(g(B,UB2)))） 1基本概念 (A1,B1)V(42,B2)=(g(fA1UA2)),B1∩B2) 可以证明L(U,M,)对此运算构成完备格，称 下面给出形式背景的相关概念。 定义1【o)设U是对象集合，M是属性的集 L(U,M,I)为概念格。 合，1是2个集合U与M之间的关系，则称三元组 为了让形式背景尽可能的简单，下面给出净化 K=(U,M,)为一个形式背景（简称背景）。 背景的定义。 对于u∈U,m∈M,(u,m)∈I(或写作lm) 定义3o!如果任意满足f(u)=fh)的2个 表示对象u具有属性m。 元素u,h∈U都有u=h,且对任意满足g(m)= 定义2o设K=(U,M,I)是一个背景。对 g(n)的元素m,n∈M,都有m=n,则称背景 于ASU,BSM。令 (U,M,)是净化的。 fA)={m∈M|Hu∈A,lm} 例1把表1净化后，得到形式背景K2,如表2。 g(B)={u∈U|HmeB,m} 表2形式背景K 如果A、B满足f(A)=B,g(B)=A,则称二元组 Table 2 The formal context K, (A,B)是一个概念。A是概念(4，B)的外延，B是 U a b c,g d e f 概念(A,B)的内涵。 4:101001 用L(U,M,I)表示背景K=(U,M,I)上的所有 u2111011 概念集合。 u3010011 形式背景K,如表1所示，其中对象集U= {u1,2,3,u4},属性集M={a,b,c,d,e,f,g},1表 4001111 示所对应的对象和属性具有关系【，0表示所对应 为了方便，给具有某种特点的对象或属性一个 的对象和属性不具有关系1。 统一的名称。 表1形式背景K 定义4【o当mX,但g(m)=g(X),称m Table 1 The formal context K 为可约属性，称m产生的属性概念 a bc d e fg (g(m),f(g(m)))为A可约的属性概念。 41010011 对应地，当u生H,但f(u)=f(H)时，称u为可 421110111 约对象，称u产生的对象概念(g(f(u)),f(u))为 430100110 V可约的对象概念。 440011111 显然∧可约的属性与V可约的对象是可以删 实际上，该形式背景完全由矩阵 除的。如果所有对象都具有某个属性m,则称m为 「10100117 “满列属性”；对应地，如果有某个对象具有所有 1110111 属性，则称山为“满行对象”。由定义可得“满列属 0100110 性”与“满行对象”都是可约的。 0011111 如果一个净化背景的每个对象概念都是V不 刻画，称此矩阵为形式背景矩阵。 可约的，则称这个背景为行既约的。如果一个净化 可以验证这个背景的全部概念是： 背景的每个属性概念都是∧不可约的，则称这个背 （u14243山4，f)、（u142,acfg）、（u2u34,ef）、 景为列既约的。既是行既约的又是列既约的，则称 （42u4,cfg)、(u2u4,cefg）、（243,bef)、(42, 其是既约的。 abcefg）、(ua,edefg)、(Φ，abedefg)。 例2把表2化成既约的，得形式背景K3,如 设K=(U,M,)是一个形式背景，H1= 表3所示
法；刘宏英等［９］ 基于对多维序列的理解，提出一种 新的多维概念格并给出了渐进式构造算法。 本文首 先将形式背景看成一个 ０、１ 的关系矩阵，然后将形 式背景化为既约的［１０］ ，最后提出了一种基于最大满 矩阵来获取概念格的算法。 １ 基本概念 下面给出形式背景的相关概念。 定义 １ ［１０］ 设 Ｕ 是对象集合， Ｍ 是属性的集 合， Ｉ 是 ２ 个集合 Ｕ 与 Ｍ 之间的关系，则称三元组 Ｋ ＝（Ｕ，Ｍ，Ｉ） 为一个形式背景（简称背景）。 对于 ｕ ∈ Ｕ，ｍ ∈ Ｍ，（ｕ，ｍ） ∈ Ｉ （或写作 ｕＩｍ ） 表示对象 ｕ 具有属性 ｍ 。 定义 ２ ［１０］ 设 Ｋ ＝ （Ｕ，Ｍ，Ｉ） 是一个背景。 对 于 Ａ ⊆ Ｕ，Ｂ ⊆ Ｍ 。 令 ｆ(Ａ) ＝ {ｍ ∈ Ｍ ∀ｕ ∈ Ａ，ｕＩｍ} ｇ(Ｂ) ＝ {ｕ ∈ Ｕ ∀ｍ ∈ Ｂ，ｕＩｍ} 如果 Ａ、Ｂ 满足 ｆ(Ａ) ＝ Ｂ，ｇ(Ｂ) ＝ Ａ， 则称二元组 (Ａ，Ｂ) 是一个概念。 Ａ 是概念 (Ａ，Ｂ) 的外延， Ｂ 是 概念 (Ａ，Ｂ) 的内涵。 用 Ｌ(Ｕ，Ｍ，Ｉ) 表示背景 Ｋ ＝ （Ｕ，Ｍ，Ｉ） 上的所有 概念集合。 形式背景 Ｋ１ 如表 １ 所示， 其中对象集 Ｕ ＝ ｕ１ ，ｕ２ ，ｕ３ ，ｕ４ { } ，属性集 Ｍ ＝ {ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ} ，１ 表 示所对应的对象和属性具有关系 Ｉ ，０ 表示所对应 的对象和属性不具有关系 Ｉ 。 表 １ 形式背景 Ｋ１ Ｔａｂｌｅ １ Ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｋ１ Ｕ ａ ｂ ｃ ｄ ｅ ｆ ｇ ｕ１ １ ０ １ ０ ０ １ １ ｕ２ １ １ １ ０ １ １ １ ｕ３ ０ １ ０ ０ １ １ ０ ｕ４ ０ ０ １ １ １ １ １ 实际上，该形式背景完全由矩阵 １ ０ １ ０ ０ １ １ １ １ １ ０ １ １ １ ０ １ ０ ０ １ １ ０ ０ ０ １ １ １ １ １ é ë ê ê ê ê ê ù û ú ú ú ú ú 刻画，称此矩阵为形式背景矩阵。 可以验证这个背景的全部概念是： （ ｕ１ ｕ２ ｕ３ ｕ４ ， ｆ ）、（ ｕ１ ｕ２ ， ａｃｆｇ ）、（ ｕ２ ｕ３ ｕ４ ， ｅｆ ）、 （ ｕ１ ｕ２ ｕ４ ， ｃｆｇ ）、 （ ｕ２ ｕ４ ， ｃｅｆｇ ）、 （ ｕ２ ｕ３ ， ｂｅｆ ）、 （ ｕ２ ， ａｂｃｅｆｇ ）、（ ｕ４ ， ｃｄｅｆｇ ）、（Φ， ａｂｃｄｅｆｇ ）。 设 Ｋ ＝ （Ｕ，Ｍ，Ｉ） 是 一 个 形 式 背 景， Ｈ１ ＝ Ａ１ ，Ｂ１ ( ) ，Ｈ２ ＝ Ａ２ ，Ｂ２ ( ) 是 Ｋ 的 ２ 个概念，在概念集 Ｌ(Ｕ，Ｍ，Ｉ) 上定义关系： Ｈ１ ≤ Ｈ２⇔Ａ１ ⊆ Ａ２（或 Ｂ２ ⊆ Ｂ１ ） 在概念集 Ｌ(Ｕ，Ｍ，Ｉ) 上定义交并运算分别为 Ａ１ ，Ｂ１ ( ) ∧ Ａ２ ，Ｂ２ ( ) ＝ Ａ１ ∩ Ａ２ ，ｆ ｇ Ｂ１ ∪ Ｂ２ ( ( ( ) ) ) Ａ１ ，Ｂ１ ( ) ∨ Ａ２ ，Ｂ２ ( ) ＝ ｇ ｆ Ａ１ ∪ Ａ２ ( ( ) ) ，Ｂ１ ∩ Ｂ２ ( ) 可以证明 Ｌ(Ｕ，Ｍ，Ｉ) 对此运算构成完备格，称 Ｌ(Ｕ，Ｍ，Ｉ) 为概念格。 为了让形式背景尽可能的简单，下面给出净化 背景的定义。 定义 ３ ［１０］ 如果任意满足 ｆ(ｕ) ＝ ｆ(ｈ) 的 ２ 个 元素 ｕ，ｈ ∈ Ｕ 都有 ｕ ＝ ｈ ，且对任意满足 ｇ(ｍ) ＝ ｇ(ｎ) 的元素 ｍ，ｎ ∈ Ｍ， 都有 ｍ ＝ ｎ ， 则称背景 (Ｕ，Ｍ，Ｉ) 是净化的。 例 １ 把表 １ 净化后，得到形式背景 Ｋ２ ，如表 ２。 表 ２ 形式背景 Ｋ２ Ｔａｂｌｅ ２ Ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｋ２ Ｕ ａ ｂ ｃ，ｇ ｄ ｅ ｆ ｕ１ １ ０ １ ０ ０ １ ｕ２ １ １ １ ０ １ １ ｕ３ ０ １ ０ ０ １ １ ｕ４ ０ ０ １ １ １ １ 为了方便，给具有某种特点的对象或属性一个 统一的名称。 定义 ４ ［１０］ 当 ｍ ∉ Ｘ，但 ｇ(ｍ) ＝ ｇ(Ｘ) ， 称 ｍ 为 可 约 属 性， 称 ｍ 产 生 的 属 性 概 念 (ｇ(ｍ) ，ｆ(ｇ(ｍ) ) ) 为 ∧ 可约的属性概念。 对应地，当 ｕ ∉ Ｈ，但 ｆ(ｕ) ＝ ｆ(Ｈ) 时，称 ｕ 为可 约对象，称 ｕ 产生的对象概念 (ｇ(ｆ(ｕ) ) ，ｆ(ｕ) ) 为 ∨ 可约的对象概念。 显然 ∧ 可约的属性与 ∨ 可约的对象是可以删 除的。 如果所有对象都具有某个属性 ｍ ，则称 ｍ 为 “满列属性”；对应地，如果有某个对象 ｕ 具有所有 属性，则称 ｕ 为“满行对象”。 由定义可得“满列属 性”与“满行对象”都是可约的。 如果一个净化背景的每个对象概念都是 ∨ 不 可约的，则称这个背景为行既约的。 如果一个净化 背景的每个属性概念都是 ∧ 不可约的，则称这个背 景为列既约的。 既是行既约的又是列既约的，则称 其是既约的。 例 ２ 把表 ２ 化成既约的，得形式背景 Ｋ３ ， 如 表 ３ 所示。 第 ６ 期 郭伦众，等：一种基于最大满矩阵生成概念格的算法 ·８３９·
·840. 智能系统学报 第10卷 表3形式背景K 的共同属性不会多于其子集所具有的共同属性。所 Table 3 The formal context K; 以对象集A,具有的共同属性应该小于或等于其子 U a b c.g d e 集A,具有的共同的属性。 4110 100 性质2设(U,M,I)为一形式背景，对任意的 u,1110 1 属性集B,CB,CM,有 01001 l1(M:)≤l(M) 4400 11 1 成立，M,M:分别为B,、B2的最大对象满矩阵。 这里把属性f删除，将属性c与g合并成一个属 说明：该性质的依据就是具有的共同属性越多，则 性也不会影响概念格的结构。 其对象集的个数不会增多。所以具有属性集B,的对 由于对具有相同内涵的对象和具有相同外延的 象个数应该小于或等于具有属性集B,的对象个数。 属性的各自合并所得的概念格与原概念格同构。所 定义7若(A,B)为形式概念，则称由对象集 以在生成概念之前可以先把形式背景化为既约的， A所在的行和属性集B所在的列组成的矩阵M为 这样就会使形式背景变得简单些。 概念矩阵。 定理1概念矩阵一定是最大属性满矩阵和最 2满矩阵与概念 大对象满矩阵。 定义5设（U,M,I)为一形式背景，在其对应 证明：由定义5~7可直接得到结论。反之，定 的形式背景矩阵中，取出对象集A二U对应的任意 理1不一定成立，即最大属性满矩阵，最大对象满矩 行和属性集BCM对应的任意列组成新的矩阵 阵不一定是概念矩阵。如在例1中，对象u1与属性 M,则称M为形式背景矩阵的子矩阵。 acg组成的子矩阵为最大属性满矩阵，但由概念的 若子矩阵M的每个元素都为1，则称子矩阵 定义知(u,acfg)不是形式概念，又对象u1山2和属 性α组成的子矩阵为最大对象满矩阵，但由概念的 M为满矩阵。 定义知(u山2，α)不是形式概念，即可得出定理1的 在满矩阵M中，规定矩阵的列数即 逆不成立。 |B|为矩阵的属性秩，记为r(M)=|B|:矩阵MA 下面给出满矩阵是概念矩阵的一个充分条件： 的行数即|A为矩阵的对象秩，记为l(M)=A|, 定理2若满矩阵M攻，既是对象集A的最大 其中1·表示集合中元素的个数。 属性满矩阵，且是属性集B的最大对象满矩阵，则 定义6在形式背景矩阵中，对于对象集A二 满矩阵M是概念矩阵。 U,如果属性集BCM有 证明反证，假设满矩阵M不是概念矩阵，说 r(M)≤r(Mi),HYCM 明(A,B)不是概念即f(A)≠B或g(B)≠A成立。 成立，则称M为对象集A对应的最大属性满矩阵。 若f4)≠B,则存在对象集A2A,使f4')=B成 对偶地，可以定义最大对象满矩阵： 立，也就是说属性集B有更大的对象满矩阵，与满 在形式背景矩阵中，对于属性集B二M,如果 矩阵M是属性集B的最大对象满矩阵矛盾：同理 对象集ACU有 可证，若g(B)≠A,则存在属性集B2B,使 l(M)≤l(M),HX≤U g(B)=A成立，也就是说对象集A有更大的属性满 成立，则称M为属性集B对应的最大对象满矩阵。 矩阵，与满矩阵M是对象集A的最大属性满矩阵 说明：给定对象集，则其对应的最大属性满矩阵 矛盾，即假设不成立，得证。 是唯一的：给定属性集，则其对应的最大对象满矩阵 为了找出形式背景中所有的概念，根据定理1， 是唯一的。 可以先找出它的所有最大属性满矩阵或最大对象满 性质1设(U,M,I)为一形式背景，对任意的 矩阵，进而根据定理2判断那些满矩阵为概念矩阵， 对象集ACA2二U,有 最后得到所有的概念。 r(M:)≤r(M) 成立，MM分别为A1、A2的最大属性满矩阵。 3方法 说明：该性质的依据就是对象集越大，则其具有 设(U,M,)是一形式背景，显然，它可以看作
表 ３ 形式背景 Ｋ３ Ｔａｂｌｅ ３ Ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｋ３ Ｕ ａ ｂ ｃ，ｇ ｄ ｅ ｕ１ １ ０ １ ０ ０ ｕ２ １ １ １ ０ １ ｕ３ ０ １ ０ ０ １ ｕ４ ０ ０ １ １ １ 这里把属性 ｆ 删除，将属性 ｃ 与 ｇ 合并成一个属 性也不会影响概念格的结构。 由于对具有相同内涵的对象和具有相同外延的 属性的各自合并所得的概念格与原概念格同构。 所 以在生成概念之前可以先把形式背景化为既约的， 这样就会使形式背景变得简单些。 ２ 满矩阵与概念 定义 ５ 设 （ Ｕ，Ｍ，Ｉ ）为一形式背景，在其对应 的形式背景矩阵中，取出对象集 Ａ ⊆ Ｕ 对应的任意 行和属性集 Ｂ ⊆ Ｍ 对应的任意列组成新的矩阵 Ｍ Ｂ Ａ ， 则称 Ｍ Ｂ Ａ 为形式背景矩阵的子矩阵。 若子矩阵 Ｍ Ｂ Ａ 的每个元素都为 １，则称子矩阵 Ｍ Ｂ Ａ 为满矩阵。 在满 矩 阵 Ｍ Ｂ Ａ 中， 规 定 矩 阵 Ｍ Ｂ Ａ 的 列 数 即 Ｂ 为矩阵的属性秩，记为 ｒ Ｍ Ｂ Ａ ( ) ＝ Ｂ ；矩阵 Ｍ Ｂ Ａ 的行数即 Ａ 为矩阵的对象秩，记为 ｌ Ｍ Ｂ Ａ ( ) ＝ Ａ ， 其中｜·｜表示集合中元素的个数。 定义 ６ 在形式背景矩阵中，对于对象集 Ａ ⊆ Ｕ， 如果属性集 Ｂ ⊆ Ｍ 有 ｒ Ｍ Ｙ Ａ ( ) ≤ ｒ Ｍ Ｂ Ａ ( ) ，∀Ｙ ⊆ Ｍ 成立，则称 Ｍ Ｂ Ａ 为对象集 Ａ 对应的最大属性满矩阵。 对偶地，可以定义最大对象满矩阵： 在形式背景矩阵中，对于属性集 Ｂ ⊆ Ｍ ，如果 对象集 Ａ ⊆ Ｕ 有 ｌ Ｍ Ｂ Ｘ ( ) ≤ ｌ Ｍ Ｂ Ａ ( ) ，∀Ｘ ⊆ Ｕ 成立，则称 Ｍ Ｂ Ａ 为属性集 Ｂ 对应的最大对象满矩阵。 说明：给定对象集，则其对应的最大属性满矩阵 是唯一的；给定属性集，则其对应的最大对象满矩阵 是唯一的。 性质 １ 设（ Ｕ，Ｍ，Ｉ ）为一形式背景，对任意的 对象集 Ａ１ ⊆ Ａ２ ⊆ Ｕ ，有 ｒ Ｍ Ｂ２ Ａ２ ( ) ≤ ｒ Ｍ Ｂ１ Ａ１ ( ) 成立， Ｍ Ｂ１ Ａ１ 、Ｍ Ｂ２ Ａ２ 分别为 Ａ１ 、Ａ２ 的最大属性满矩阵。 说明：该性质的依据就是对象集越大，则其具有 的共同属性不会多于其子集所具有的共同属性。 所 以对象集 Ａ２ 具有的共同属性应该小于或等于其子 集 Ａ１ 具有的共同的属性。 性质 ２ 设（ Ｕ，Ｍ，Ｉ ）为一形式背景，对任意的 属性集 Ｂ１ ⊆ Ｂ２ ⊆ Ｍ， 有 ｌ Ｍ Ｂ２ Ａ２ ( ) ≤ ｌ Ｍ Ｂ１ Ａ１ ( ) 成立， Ｍ Ｂ１ Ａ１ ，Ｍ Ｂ２ Ａ２ 分别为 Ｂ１ 、Ｂ２ 的最大对象满矩阵。 说明：该性质的依据就是具有的共同属性越多，则 其对象集的个数不会增多。 所以具有属性集 Ｂ２ 的对 象个数应该小于或等于具有属性集 Ｂ１ 的对象个数。 定义 ７ 若 (Ａ，Ｂ) 为形式概念，则称由对象集 Ａ 所在的行和属性集 Ｂ 所在的列组成的矩阵 Ｍ Ｂ Ａ 为 概念矩阵。 定理 １ 概念矩阵一定是最大属性满矩阵和最 大对象满矩阵。 证明：由定义 ５ ～ ７ 可直接得到结论。 反之，定 理 １ 不一定成立，即最大属性满矩阵，最大对象满矩 阵不一定是概念矩阵。 如在例 １ 中，对象 ｕ１ 与属性 ａｃｆｇ 组成的子矩阵为最大属性满矩阵，但由概念的 定义知 (ｕ１ ，ａｃｆｇ) 不是形式概念，又对象 ｕ１ ｕ２ 和属 性 ａ 组成的子矩阵为最大对象满矩阵，但由概念的 定义知 (ｕ１ ｕ２ ，ａ) 不是形式概念，即可得出定理 １ 的 逆不成立。 下面给出满矩阵是概念矩阵的一个充分条件： 定理 ２ 若满矩阵 Ｍ Ｂ Ａ ，既是对象集 Ａ 的最大 属性满矩阵，且是属性集 Ｂ 的最大对象满矩阵，则 满矩阵 Ｍ Ｂ Ａ 是概念矩阵。 证明 反证，假设满矩阵 Ｍ Ｂ Ａ 不是概念矩阵，说 明 (Ａ，Ｂ) 不是概念即 ｆ(Ａ) ≠ Ｂ 或 ｇ(Ｂ) ≠ Ａ 成立。 若 ｆ(Ａ) ≠ Ｂ ，则存在对象集 Ａ ′ ⊇ Ａ， 使 ｆ Ａ ′ ( ) ＝ Ｂ 成 立，也就是说属性集 Ｂ 有更大的对象满矩阵，与满 矩阵 Ｍ Ｂ Ａ 是属性集 Ｂ 的最大对象满矩阵矛盾；同理 可证， 若 ｇ(Ｂ) ≠ Ａ ， 则存在属性 集 Ｂ ′ ⊇ Ｂ， 使 ｇ Ｂ ′ ( ) ＝ Ａ 成立，也就是说对象集 Ａ 有更大的属性满 矩阵，与满矩阵 Ｍ Ｂ Ａ 是对象集 Ａ 的最大属性满矩阵 矛盾，即假设不成立，得证。 为了找出形式背景中所有的概念，根据定理 １， 可以先找出它的所有最大属性满矩阵或最大对象满 矩阵，进而根据定理 ２ 判断那些满矩阵为概念矩阵， 最后得到所有的概念。 ３ 方法 设 (Ｕ，Ｍ，Ｉ) 是一形式背景，显然，它可以看作 ·８４０· 智 能 系 统 学 报 第 １０ 卷
第6期 郭伦众，等：一种基于最大满矩阵生成概念格的算法 ·841- 是一个由0、1表示的矩阵。利用矩阵获得概念的生 利用相关的分析器可以分析出每个项目在每一个过 成算法： 程中的使用情况(“1”表示使用)，如表5所示。用 1)将形式背景化为既约背景。首先净化背景， 上面算法构造出对应的概念。 及合并具有相同内涵的对象和具有相同外延的属 根据上文给出的定义，删除可约对象B,合并 性，然后删除其内涵等于其他对象内涵交的那些对 相同对象后，可以写出表4对应的既约背景如表5。 象，对应地删除其外延等于其他属性外延的交的那 表49个项目与6个特征的对应关系 些属性，得到的就是既约背景。 Table 4 The relation of nine projects and six characteristics 2)根据定理1，先找出各形式背景矩阵对应 参数 P P2 P3 Pa Ps Po 的非零矩阵的最大属性满矩阵或最大对象满矩 NAME:a 1 0 0 0 0 1 阵，然后根据定理2判断那些满矩阵是概念矩 TITLE:8 1 0 0 0 0 0 阵，最后，在概念矩阵中加上矩阵M与Mg即为 INTTIAL:y 1 0 0 所有的概念矩阵。 PREFIX:8 1 0 0 0 下面用具体例子说明该算法的过程。 NUMBER:e 0 0 0 1 0 1 例3表3是表1给出的形式背景 NUMBER-EXT:0 0 0 1 0 1 (U,M,)的既约背景，它可以表示为一个0,1的关 ZIPCD:0 0 0 0 0 1 系矩阵，如下所示，现在用给出的概念格生成算法来 SIREFT: 0 0 1 1 0 0 找出它的概念格： CITY:K 0 1 0 1 0 0 10100 表5既约背景 111 0 1 Table 5 Reducible formal context 01001 参数 P1 P2 P3 Pa Ps P6 L00111 NAME:@ 100001 通过上面的矩阵可以计算表3的概念层次如下： INTTIAL:Yy 1)形式背景矩阵对应的非零矩阵的最大属性 PREFIX:8 100010 满矩阵有： NUMBER: MMMMM NUMBER-EXT: 000101 MMMMM ZIPCD:0 这里，ac代表集合{a,c},余同。 SIREFT: 001100 2)由定理2得出概念矩阵有： CITY:K 010100 MMMM 下面写出它既约背景对应的关系矩阵： M.M 「1000017 最后，得到概念所有的概念： 100010 (uabce),(u,cde),(uuz,ac),(uzu3,be), 000101 (u2L4,ce)(u1u2u4,c）,(u2u34,e）, 001100 (u1u2u3u4,Φ)，（Φ，abede) 010100 另外，可以先找出所有的最大对象满矩阵，再根 通过上面的矩阵可以计算表5的概念层次如下： 据定理2得到概念矩阵，进而得到所有的概念。 1)形式背景矩阵对应的非零矩阵的最大属性 为了进一步说明该算法的有效性，给出实例： 满矩阵有： 例4【]软件的结构设计主要是针对软件的 MMMMMM 数据结构模式，在需求分析的基础上，通过合理化组 Ms,M,MM,M 织，加以分析设计，从而得出设计的方法。下面假设 2)由定理2得出概念矩阵有： 一个系统，这个系统包括6个过程（分别假设为P, M,M,M46,M4,M, P2,P,P4,P,P6)以及一个包含9个字段的记录。 MMMMM
是一个由 ０、１ 表示的矩阵。 利用矩阵获得概念的生 成算法： １）将形式背景化为既约背景。 首先净化背景， 及合并具有相同内涵的对象和具有相同外延的属 性，然后删除其内涵等于其他对象内涵交的那些对 象，对应地删除其外延等于其他属性外延的交的那 些属性，得到的就是既约背景。 ２）根据定理 １，先找出各形式背景矩阵对应 的非零矩阵的最大属性满矩阵或最大对象满矩 阵，然后根据定理 ２ 判断那些满 矩 阵 是 概 念 矩 阵，最后，在概念矩阵中加上矩阵 Ｍ Φ Ｇ 与 Ｍ Ｍ Φ 即为 所有的概念矩阵。 下面用具体例子说明该算法的过程。 例 ３ 表 ３ 是 表 １ 给 出 的 形 式 背 景 (Ｕ，Ｍ，Ｉ) 的既约背景，它可以表示为一个 ０，１ 的关 系矩阵，如下所示，现在用给出的概念格生成算法来 找出它的概念格： １ ０ １ ０ ０ １ １ １ ０ １ ０ １ ０ ０ １ ０ ０ １ １ １ é ë ê ê ê ê ê ù û ú ú ú ú ú 通过上面的矩阵可以计算表 ３ 的概念层次如下： １）形式背景矩阵对应的非零矩阵的最大属性 满矩阵有： Ｍ ａｃ ｕ１ ，Ｍ ａｂｃｅ ｕ２ ，Ｍ ｂｅ ｕ３ ，Ｍ ｃｄｅ ｕ４ ，Ｍ ａｃ ｕ１ ｕ２ ， Ｍ ｂｅ ｕ２ ｕ３ ，Ｍ ｃｅ ｕ２ ｕ４ ，Ｍ ｅ ｕ３ ｕ４ ，Ｍ ｃ ｕ１ ｕ２ ｕ４ ，Ｍ ｅ ｕ２ ｕ３ ｕ４ 这里， ａｃ 代表集合 {ａ，ｃ} ，余同。 ２）由定理 ２ 得出概念矩阵有： Ｍ ａｂｃｅ ｕ２ ，Ｍ ｃｄｅ ｕ４ ，Ｍ ａｃ ｕ１ ｕ２ ，Ｍ ｂｅ ｕ２ ｕ３ ，Ｍ ｃｅ ｕ２ ｕ４ ， Ｍ ｃ ｕ１ ｕ２ ｕ４ ，Ｍ ｅ ｕ２ ｕ３ ｕ４ ，Ｍ φ ｕ１ ｕ２ ｕ３ ｕ４ ，Ｍ ａｂｃｄｅ φ 最后，得到概念所有的概念： (ｕ２ ａｂｃｅ) ，(ｕ４ ，ｃｄｅ) ，(ｕ１ ｕ２ ，ａｃ) ，(ｕ２ ｕ３ ，ｂｅ) ， (ｕ２ ｕ４ ，ｃｅ) (ｕ１ ｕ２ ｕ４ ，ｃ) ，(ｕ２ ｕ３ ｕ４ ，ｅ) ， (ｕ１ ｕ２ ｕ３ ｕ４ ，Φ) ，(Φ，ａｂｃｄｅ) 另外，可以先找出所有的最大对象满矩阵，再根 据定理 ２ 得到概念矩阵，进而得到所有的概念。 为了进一步说明该算法的有效性，给出实例： 例 ４ [１１ ] 软件的结构设计主要是针对软件的 数据结构模式，在需求分析的基础上，通过合理化组 织，加以分析设计，从而得出设计的方法。 下面假设 一个系统，这个系统包括 ６ 个过程（分别假设为 Ｐ１ ， Ｐ２ ，Ｐ３ ，Ｐ４ ，Ｐ５ ，Ｐ６ ）以及一个包含 ９ 个字段的记录。 利用相关的分析器可以分析出每个项目在每一个过 程中的使用情况（“１”表示使用），如表 ５ 所示。 用 上面算法构造出对应的概念。 根据上文给出的定义，删除可约对象 β ，合并 相同对象后，可以写出表 ４ 对应的既约背景如表 ５。 表 ４ ９ 个项目与 ６ 个特征的对应关系 Ｔａｂｌｅ ４ Ｔｈｅ ｒｅｌａｔｉｏｎ ｏｆ ｎｉｎｅ ｐｒｏｊｅｃｔｓ ａｎｄ ｓｉｘ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ 参数 Ｐ１ Ｐ２ Ｐ３ Ｐ４ Ｐ５ Ｐ６ ＮＡＭＥ： α １ ０ ０ ０ ０ １ ＴＩＴＬＥ： β １ ０ ０ ０ ０ ０ ＩＮＴＴＩＡＬ： γ １ ０ ０ ０ １ ０ ＰＲＥＦＩＸ： δ １ ０ ０ ０ １ ０ ＮＵＭＢＥＲ： ε ０ ０ ０ １ ０ １ ＮＵＭＢＥＲ⁃ＥＸＴ： ζ ０ ０ ０ １ ０ １ ＺＩＰＣＤ： θ ０ ０ ０ １ ０ １ ＳＩＲＥＦＴ： ι ０ ０ １ １ ０ ０ ＣＩＴＹ： κ ０ １ ０ １ ０ ０ 表 ５ 既约背景 Ｔａｂｌｅ ５ Ｒｅｄｕｃｉｂｌｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ 参数 Ｐ１ Ｐ２ Ｐ３ Ｐ４ Ｐ５ Ｐ６ ＮＡＭＥ：α １ ０ ０ ０ ０ １ ＩＮＴＴＩＡＬ： γ ＰＲＥＦＩＸ： δ １ ０ ０ ０ １ ０ ＮＵＭＢＥＲ： ε ＮＵＭＢＥＲ⁃ＥＸＴ： ζ ０ ０ ０ １ ０ １ ＺＩＰＣＤ： θ ＳＩＲＥＦＴ：ι ０ ０ １ １ ０ ０ ＣＩＴＹ： κ ０ １ ０ １ ０ ０ 下面写出它既约背景对应的关系矩阵： １ ０ ０ ０ ０ １ １ ０ ０ ０ １ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ ０ ０ ０ １ ０ １ ０ ０ é ë ê ê ê ê ê ê ê ù û ú ú ú ú ú ú ú 通过上面的矩阵可以计算表 ５ 的概念层次如下： １）形式背景矩阵对应的非零矩阵的最大属性 满矩阵有： Ｍ Ｐ１Ｐ６ α ，Ｍ Ｐ１Ｐ５ γ ，Ｍ Ｐ４Ｐ６ ε ，Ｍ Ｐ３Ｐ４ ι ，Ｍ Ｐ２Ｐ４ κ ，Ｍ Ｐ１ αγ ， Ｍ Ｐ６ αε ，Ｍ Ｐ４ ει ，Ｍ Ｐ４ εκ ，Ｍ Ｐ４ ικ ，Ｍ Ｐ４ εικ ２）由定理 ２ 得出概念矩阵有： Ｍ Ｐ１Ｐ６ α ，Ｍ Ｐ１Ｐ５ γ ，Ｍ Ｐ４Ｐ６ ε ，Ｍ Ｐ３Ｐ４ ι ，Ｍ Ｐ２Ｐ４ κ ， Ｍ Ｐ１ αγ ，Ｍ Ｐ６ αε ，Ｍ Ｐ４ εικ ，Ｍ Ｐ１Ｐ２Ｐ３Ｐ４Ｐ５Ｐ６ Φ ，Ｍ Φ αγεικ 第 ６ 期 郭伦众，等：一种基于最大满矩阵生成概念格的算法 ·８４１·
.842. 智能系统学报 第10卷 3)最后，得到概念所有的概念： [7]李海霞.基于Hasse图的概念格的一种渐减式构造算法 (a,P P6),(y,P Ps),(s,PP6),(t,P:P), [].河南科技学院学报，2015,43(3)：57-60,66. (K,P2P4),(ay,P),(aE,P6),(eK,P), LI Haixia.A decreasing algorithm of concept lattice based (④，PP2P3PPP6),(ayeK,Φ) on Hasse diagram[J].Journal of Henan Institute of Science and Technology,2015,43(3):57-60,66. 5结束语 [8]崔芳婷，王黎明，张卓.基于约束的模糊概念格构造算 法[J】.计算机科学，2015,42(8)：288-293,318. 目前，已有不少概念格的建格算法，本文从矩阵 CUI Fangting,WANG Liming,ZHANG Zhuo.Construction 的角度出发，利用矩阵与概念之间的联系，定义了一 algorithm of fuzzy concept lattice based on constraints[J]. 种新的基于概念的矩阵一最大满矩阵，找出了最 Computer Science,2015,42(8):288-293,318. 大满矩阵与概念之间的联系，进而得出了一种基于 [9]刘宏英，郭显娥，胡小珍.多维概念格及其构造算法 矩阵的概念格生成算法，具体例子说明该算法是有 [J].计算机工程与应用，2012,48(12)：96-99,111. 效的。 LIU Hongying,GUO Xian'e,HU Xiaozhen.Multidimen- sional concept lattice and constructing algorithm[J].Com- 参考文献： puter Engineering and Applications,2012,48(12):96- [1]WILLE R.Restructuring lattice theory:an approach based 99,111. on hierarchies of concepts[M]//RIVAL I.Ordered Sets. [10]马垣，曾子维，迟呈英，等.形式概念及其新进展[M] Berlin Heidelberg:Springer,1982:445-470. 北京：科学出版社，2010：11-24. [2]00STHULZEN G D.The application of concept lattice to [11]蒋平，任胜兵，林鹃.形式概念分析在软件工程中的应 machine learning[R].South Africa:University of Pretoria, 用J].计算机技术与发展，2008,18(4)：127-129， 1996. 213. [3]GODIN R,MISSAOUI R,ALAOUI H.Incremental concept JIANG Ping,REN Shengbing,LIN Juan.Using formal formation algorithms based on Galois (concept)lattices[J]. concept analysis for software engineering [J].Computer Computational Intelligence,1995,11(2):246-267. Technology and development,2008,18(4):127-129, [4]HO T B.Incremental conceptual clustering in the framework 213. of Galois lattice[C]//LU H,LIU H,MOTODA H.KDD: 作者简介： 宋振明，男，教授，硕士生导师，主 Techniques and Applications.Singapore:World Scientific, 1997:49-64. 要研究方向为智能信息处理、运筹与控 [5]谢志鹏，刘宗田.概念格的快速渐进式构造算法[J刀].计 制、不确定性推理。 算机学报，2002,25(5)：490-496. XIE Zhipeng,LIU Zongtian.A fast incremental algorithm for building concept lattice[J].Chinese Journal of Computers, 2002,25(5):490-496. 郭伦众，女，1992年生，硕士研究 [6]林春杰，普杰信，张瑞玲.近似概念格及其增量构造算 生，主要研究方向为智能信息处理。 法研究[].计算机应用研究，2012,29(1)：25-27. LIN Chunjie,PU Jinxin,ZHANG Ruilin.Approximation concept lattice and incremental constructing algorithm[]. Application Research of Computers,2012,29(1):25-27
３）最后，得到概念所有的概念： α，Ｐ１Ｐ６ ( ) ， γ，Ｐ１Ｐ５ ( ) ， ε，Ｐ４Ｐ６ ( ) ， ι，Ｐ３Ｐ４ ( ) ， κ，Ｐ２Ｐ４ ( ) ， αγ，Ｐ１ ( ) ， αε，Ｐ６ ( ) ， εικ，Ｐ４ ( ) ， Φ，Ｐ１Ｐ２Ｐ３Ｐ４Ｐ５Ｐ６ ( ) ，(αγεικ，Φ) ５ 结束语 目前，已有不少概念格的建格算法，本文从矩阵 的角度出发，利用矩阵与概念之间的联系，定义了一 种新的基于概念的矩阵———最大满矩阵，找出了最 大满矩阵与概念之间的联系，进而得出了一种基于 矩阵的概念格生成算法，具体例子说明该算法是有 效的。 参考文献： ［１］ＷＩＬＬＥ Ｒ． Ｒｅｓｔｒｕｃｔｕｒｉｎｇ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ： ａｎ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｅｓ ｏｆ ｃｏｎｃｅｐｔｓ ［ Ｍ］ ／ ／ ＲＩＶＡＬ Ｉ． Ｏｒｄｅｒｅｄ Ｓｅｔｓ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， １９８２： ４４５⁃４７０． ［２］ ＯＯＳＴＨＵＬＺＥＮ Ｇ Ｄ． Ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｔｏ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ［Ｒ］． Ｓｏｕｔｈ Ａｆｒｉｃａ： Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｒｅｔｏｒｉａ， １９９６． ［３］ＧＯＤＩＮ Ｒ， ＭＩＳＳＡＯＵＩ Ｒ， ＡＬＡＯＵＩ Ｈ． Ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｃｅｐｔ ｆｏｒｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄ ｏｎ Ｇａｌｏｉｓ （ｃｏｎｃｅｐｔ） ｌａｔｔｉｃｅｓ［Ｊ］． Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９５， １１（２）： ２４６⁃２６７． ［４］ＨＯ Ｔ Ｂ． Ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｃｅｐｔｕａｌ ｃｌｕｓｔｅｒｉｎｇ ｉｎ ｔｈｅ ｆｒａｍｅｗｏｒｋ ｏｆ Ｇａｌｏｉｓ ｌａｔｔｉｃｅ［Ｃ］ ／ ／ ＬＵ Ｈ， ＬＩＵ Ｈ， ＭＯＴＯＤＡ Ｈ． ＫＤＤ： Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｓｉｎｇａｐｏｒｅ： Ｗｏｒｌｄ Ｓｃｉｅｎｔｉｆｉｃ， １９９７： ４９⁃６４． ［５］谢志鹏， 刘宗田． 概念格的快速渐进式构造算法［ Ｊ］． 计 算机学报， ２００２， ２５（５）： ４９０⁃４９６． ＸＩＥ Ｚｈｉｐｅｎｇ， ＬＩＵ Ｚｏｎｇｔｉａｎ． Ａ ｆａｓｔ ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｂｕｉｌｄｉｎｇ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ［ Ｊ］． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２００２， ２５（５）： ４９０⁃４９６． ［６］林春杰， 普杰信， 张瑞玲． 近似概念格及其增量构造算 法研究［Ｊ］． 计算机应用研究， ２０１２， ２９（１）： ２５⁃２７． ＬＩＮ Ｃｈｕｎｊｉｅ， ＰＵ Ｊｉｎｘｉｎ， ＺＨＡＮＧ Ｒｕｉｌｉｎ． Ａｐｐｒｏｘｉｍａｔｉｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ａｎｄ ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｓｔｒｕｃｔｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２０１２， ２９（１）： ２５⁃２７． ［７］李海霞． 基于 Ｈａｓｓｅ 图的概念格的一种渐减式构造算法 ［Ｊ］． 河南科技学院学报， ２０１５， ４３（３）： ５７⁃６０， ６６． ＬＩ Ｈａｉｘｉａ． Ａ ｄｅｃｒｅａｓｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｂａｓｅｄ ｏｎ Ｈａｓｓｅ ｄｉａｇｒａｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｈｅｎａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２０１５， ４３（３）： ５７⁃６０， ６６． ［８］ 崔芳婷， 王黎明， 张卓． 基于约束的模糊概念格构造算 法［Ｊ］． 计算机科学， ２０１５， ４２（８）： ２８８⁃２９３， ３１８． ＣＵＩ Ｆａｎｇｔｉｎｇ， ＷＡＮＧ Ｌｉｍｉｎｇ， ＺＨＡＮＧ Ｚｈｕｏ． Ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｆｕｚｚｙ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｂａｓｅｄ ｏｎ ｃｏｎｓｔｒａｉｎｔｓ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２０１５， ４２（８）： ２８８⁃２９３， ３１８． ［９］刘宏英， 郭显娥， 胡小珍． 多维概念格及其构造算法 ［Ｊ］． 计算机工程与应用， ２０１２， ４８（１２）： ９６⁃９９， １１１． ＬＩＵ Ｈｏｎｇｙｉｎｇ， ＧＵＯ Ｘｉａｎ ＇ ｅ， ＨＵ Ｘｉａｏｚｈｅｎ． Ｍｕｌｔｉｄｉｍｅｎ⁃ ｓｉｏｎａｌ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ａｎｄ ｃｏｎｓｔｒｕｃｔｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｃｏｍ⁃ ｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１２， ４８ （ １２）： ９６⁃ ９９， １１１． ［１０］马垣， 曾子维， 迟呈英， 等． 形式概念及其新进展［Ｍ］． 北京： 科学出版社， ２０１０： １１⁃２４． ［１１］蒋平， 任胜兵， 林鹃． 形式概念分析在软件工程中的应 用［Ｊ］． 计算机技术与发展， ２００８， １８ （ ４）： １２７⁃１２９， ２１３． ＪＩＡＮＧ Ｐｉｎｇ， ＲＥＮ Ｓｈｅｎｇｂｉｎｇ， ＬＩＮ Ｊｕａｎ． Ｕｓｉｎｇ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ｆｏｒ ｓｏｆｔｗａｒｅ ｅｎｇｉｎｅｅｒｉｎｇ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， ２００８， １８ （ ４）： １２７⁃１２９， ２１３． 作者简介： 宋振明，男，教授，硕士生导师，主 要研究方向为智能信息处理、运筹与控 制、不确定性推理。 郭伦众，女， １９９２ 年生，硕士研究 生，主要研究方向为智能信息处理。 ·８４２· 智 能 系 统 学 报 第 １０ 卷
