【知识工程】基于权值最大圈的概念格构造算法

第11卷第4期 智能系统学报 Vol.11 No.4 2016年8月 CAAI Transactions on Intelligent Systems Aug.2016 D0I:10.11992/is.201606006 网络出版地址：http://www.cnki.net/kcms/detail,/23.1538.TP.20160808.0830.014.html 基于权值最大圈的概念格构造算法 毛华，刘祎超 (河北大学数学与信息科学学院，河北保定071002) 摘要：概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用。寻找形式背景下的所有 概念是概念格理论研究的一个基本问题。对于一个给定的形式背景，在属性拓扑图的基础上，结合图论的思想，给 出了一种概念格的构造算法。算法过程如下：首先，构造弱化的属性拓扑图：其次，通过寻找弱化的属性拓扑图中的 每个权值最大圈方法来生成概念，形式背景的所有概念被生成：最后，构造出概念格。通过分析说明此算法复杂度 比以往的一些算法复杂度低。此外，用一个实例验证了这一算法的有效性与正确性。为知识获取提供了有益的思 路与方法。 关键词：形式背景：概念格：概念：权值：最大圈：属性拓扑：数据处理 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)04-0519-07 中文引用格式：毛华，刘祎超.基于权值最大圈的概念格构造算法[J].智能系统学报，2016,11(4)：519-525. 英文引用格式：MAO Hua,LIU Yichao..An algorithm for concept lattice construction based on maximum cycles of weight values [J].CAAI Transactions on Intelligent Systems,2016,11(4):519-525. An algorithm for concept lattice construction based on maximum cycles of weight values MAO Hua,LIU Yichao (School of Mathematics and Information Science,Hebei University,Baoding 071002,China) Abstract:As an effective tool for knowledge discovery and data processing,the concept lattice has been widely ap- plied in many fields.Searching all concepts in a formal context is a basic problem for research into concept lattice theory.On the basis of attribute topology and combined with the idea of graph theory,an algorithm to construct a concept lattice in a fixed formal context is given.The process is as follows:firstly,a weakened attribute topology was built up;then,by applying the method of searching the maximum cycle with a weight in the above weakened attribute topology,all of the formal context concepts were obtained;finally the concept lattice was established.Sub- sequent analysis illustrated that the algorithm can reduce complexity compared with some existing algorithms.In ad- dition,using an example,the accuracy and validity of the algorithm was verified.The result presents a useful idea and method for knowledge acquisition. Keywords:formal context;concept lattice;concept;weight value;maximum cycle;attributes topology;data pro- cessing 概念格是对背景中属性、对象及其关系进行 识处理的数学工具2-)引。目前，概念格已经广泛应 分析研究的理论。它提供了一种支持数据分析和知用于数据挖掘)]、信息处理)、软件工程6和其他 方面-】。概念格理论的研究不仅能用于解决知识 收稿日期：2016-06-02.网络出版日期：2016-08-08. 发现领域中所涉及的关联规则、蕴含规则、分类规则 基金项目：国家自然科学基金项目(61572011)：河北省自然科学基金项 目(A2013201119). 的提取，还能够实现对信息的有机组织、减少冗余 通信作者：刘袆超.E-mail:1026074348@q4-com 度、简化信息表，所以对概念格理论及其算法的研究

第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６００６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３０．０１４．ｈｔｍｌ 基于权值最大圈的概念格构造算法 毛华，刘祎超 （河北大学 数学与信息科学学院，河北 保定 ０７１００２） 摘 要：概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用。 寻找形式背景下的所有 概念是概念格理论研究的一个基本问题。 对于一个给定的形式背景，在属性拓扑图的基础上，结合图论的思想，给 出了一种概念格的构造算法。 算法过程如下：首先，构造弱化的属性拓扑图；其次，通过寻找弱化的属性拓扑图中的 每个权值最大圈方法来生成概念，形式背景的所有概念被生成；最后，构造出概念格。 通过分析说明此算法复杂度 比以往的一些算法复杂度低。 此外，用一个实例验证了这一算法的有效性与正确性。 为知识获取提供了有益的思 路与方法。 关键词：形式背景；概念格；概念；权值；最大圈；属性拓扑；数据处理 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０５１９－０７ 中文引用格式：毛华，刘祎超． 基于权值最大圈的概念格构造算法［Ｊ］． 智能系统学报， ２０１６， １１（４）： ５１９－５２５． 英文引用格式：ＭＡＯ Ｈｕａ， ＬＩＵ Ｙｉｃｈａｏ． Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｍａｘｉｍｕｍ ｃｙｃｌｅｓ ｏｆ ｗｅｉｇｈｔ ｖａｌｕｅｓ ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ５１９－５２５． Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｍａｘｉｍｕｍ ｃｙｃｌｅｓ ｏｆ ｗｅｉｇｈｔ ｖａｌｕｅｓ ＭＡＯ Ｈｕａ， ＬＩＵ Ｙｉｃｈａｏ （Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ， Ｈｅｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｂａｏｄｉｎｇ ０７１００２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓ ａｎ ｅｆｆｅｃｔｉｖｅ ｔｏｏｌ ｆｏｒ ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒｙ ａｎｄ ｄａｔａ ｐｒｏｃｅｓｓｉｎｇ， ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｈａｓ ｂｅｅｎ ｗｉｄｅｌｙ ａｐ⁃ ｐｌｉｅｄ ｉｎ ｍａｎｙ ｆｉｅｌｄｓ． Ｓｅａｒｃｈｉｎｇ ａｌｌ ｃｏｎｃｅｐｔｓ ｉｎ ａ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｉｓ ａ ｂａｓｉｃ ｐｒｏｂｌｅｍ ｆｏｒ ｒｅｓｅａｒｃｈ ｉｎｔｏ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ． Ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ａｔｔｒｉｂｕｔｅ ｔｏｐｏｌｏｇｙ ａｎｄ ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｉｄｅａ ｏｆ ｇｒａｐｈ ｔｈｅｏｒｙ， ａｎ ａｌｇｏｒｉｔｈｍ ｔｏ ｃｏｎｓｔｒｕｃｔ ａ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｉｎ ａ ｆｉｘｅｄ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｉｓ ｇｉｖｅｎ． Ｔｈｅ ｐｒｏｃｅｓｓ ｉｓ ａｓ ｆｏｌｌｏｗｓ： ｆｉｒｓｔｌｙ， ａ ｗｅａｋｅｎｅｄ ａｔｔｒｉｂｕｔｅ ｔｏｐｏｌｏｇｙ ｗａｓ ｂｕｉｌｔ ｕｐ； ｔｈｅｎ， ｂｙ ａｐｐｌｙｉｎｇ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｓｅａｒｃｈｉｎｇ ｔｈｅ ｍａｘｉｍｕｍ ｃｙｃｌｅ ｗｉｔｈ ａ ｗｅｉｇｈｔ ｉｎ ｔｈｅ ａｂｏｖｅ ｗｅａｋｅｎｅｄ ａｔｔｒｉｂｕｔｅ ｔｏｐｏｌｏｇｙ， ａｌｌ ｏｆ ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｃｏｎｃｅｐｔｓ ｗｅｒｅ ｏｂｔａｉｎｅｄ； ｆｉｎａｌｌｙ ｔｈｅ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｗａｓ ｅｓｔａｂｌｉｓｈｅｄ． Ｓｕｂ⁃ ｓｅｑｕｅｎｔ ａｎａｌｙｓｉｓ ｉｌｌｕｓｔｒａｔｅｄ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｒｅｄｕｃｅ ｃｏｍｐｌｅｘｉｔｙ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｓｏｍｅ ｅｘｉｓｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ． Ｉｎ ａｄ⁃ ｄｉｔｉｏｎ， ｕｓｉｎｇ ａｎ ｅｘａｍｐｌｅ， ｔｈｅ ａｃｃｕｒａｃｙ ａｎｄ ｖａｌｉｄｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗａｓ ｖｅｒｉｆｉｅｄ． Ｔｈｅ ｒｅｓｕｌｔ ｐｒｅｓｅｎｔｓ ａ ｕｓｅｆｕｌ ｉｄｅａ ａｎｄ ｍｅｔｈｏｄ ｆｏｒ ｋｎｏｗｌｅｄｇｅ ａｃｑｕｉｓｉｔｉｏｎ． Ｋｅｙｗｏｒｄｓ： ｆｏｒｍａｌ ｃｏｎｔｅｘｔ； ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ； ｃｏｎｃｅｐｔ； ｗｅｉｇｈｔ ｖａｌｕｅ； ｍａｘｉｍｕｍ ｃｙｃｌｅ； ａｔｔｒｉｂｕｔｅｓ ｔｏｐｏｌｏｇｙ； ｄａｔａ ｐｒｏ⁃ ｃｅｓｓｉｎｇ 收稿日期：２０１６－０６－０２． 网络出版日期：２０１６－０８－０８． 基金项目：国家自然科学基金项目（６１５７２０１１）；河北省自然科学基金项 目（Ａ２０１３２０１１１９）． 通信作者：刘祎超．Ｅ⁃ｍａｉｌ：１０２６０７４３４８＠ ｑｑ．ｃｏｍ． 概念格［１］是对背景中属性、对象及其关系进行 分析研究的理论。 它提供了一种支持数据分析和知 识处理的数学工具［２－３］ 。 目前，概念格已经广泛应 用于数据挖掘［４］ 、信息处理［５］ 、软件工程［６］ 和其他 方面［７－８］ 。 概念格理论的研究不仅能用于解决知识 发现领域中所涉及的关联规则、蕴含规则、分类规则 的提取，还能够实现对信息的有机组织、减少冗余 度、简化信息表，所以对概念格理论及其算法的研究

520 智能系统学报 第11卷 具有重要的意义。 表1形式背景(O,M,) 概念是人类进行知识表达的一种手段，数据 Table 1 Formal context(O,M,I) 库知识发现的过程就是将数据库中蕴含的知识 对像a b c d e f 形式化成有用的概念的过程。对形式背景的表 示及寻找背景下的所有概念是概念格理论研究 2 3 的基本问题。近年来许多学者从图论的方面对 4 概念格进行研究，例如，张涛等[9提出用属性拓 5 扑图来表示形式背景，并在此属性拓扑图的基础 6 上进行概念计算：A.Bery等[io将形式背景构造 表1对应的形式背景的概念格见图1。 成二部图，利用团的思想生成概念：此外，李立峰 等[口利用弦二部图对概念格进行表示，其中判 (123456,) 断弦二部图中是否有圈，是判断弦二部图的关 (123,b)124.a）(24.d34,e)135.c) 键。这也证实图论特别是图中的圈，在概念格的 (12.ab)(13.bc)(24,adg 研究中之重要。 (1,abe)(2.abdg)(3,bce)(4.adeg)(5.cf) 本文结合图论的知识，将形式背景以属性拓扑 图表示出来，通过构造弱化的属性拓扑图，然后寻找 (d,abcdefgh) 弱化的属性拓扑图中的权值地之最大圈，用以生成 图1B(0,M,) 概念，从而构造出概念格，并结合实例分析了这一算 Fig.1 B(O,M,I) 法的有效性。 说明1本文所讨论的形式背景中不含有满足 1基本概念 以下条件的属性和对象，m∈M,m'=0或m'=②； g∈0，g=M或g'=☑。 本节将回顾概念格与图论的一些性质和定 1.2图论 义，关于概念格的更多内容参见文献[12]，有关 定义21)称数学结构G={V(G),E(G), 图论详细内容参见文献[13]，并且简单描述形式 山。为一个图，其中V(G)为非空集合，中c是从集合 背景的属性拓扑图表示方法，更多详细内容参见 E(G)到V(G)xV(G)的一个映射，则称G是一个以 文献[9,14]。 V(G)为顶集合，以E(G)为边集合的有向图，V(G) 1.1概念格 中的元素称为G的顶点。E(G)中的元素称为G的 定义1 边，中c称为G的关联函数。若中e(e)=(u,v),e∈ 1)形式背景(0，M,)是一个三元组，其中0是 E(G),(u,v)eV(G)xV(G),简写成e=w,称u是有 对象集，M是属性集，I c0 xM。O和M中的元素分 向边e的尾，v是有向边e的头。擦掉有向图中的箭 别称为对象和属性。 头，则得到无向图。 2)设ACO且BCM,定义 2)在顶边交错链P=oe11e2…ez中，e:∈ A'={m∈Ml(VgeA),glm} E(G),i=1,2,…,k,yeV(G),j=1,2,…,k,且e,= B'={g∈0l(meB),glm}; 若A'=B且B'=A,则元素对(A,B)是一个 -1:,则称P是G的一条道路，其中允许u,=心，或 e:=e,i有。称o是p的起点，是p的终点。各顶相 概念。A为概念(A,B)的外延，B为概念(A,B) 异的道路称为轨道：起点与终点重合的轨道称为圈。 的内涵。形式背景(O,M,)的所有概念的集合 3)在一个无向图中，只有一个顶的圈叫做自 用B(0,M,I)表示，称B(0,M,I)为(0，M,I) 环；c(e1)=中c(e2)=(u,v),则称e,与e2是重边。 的概念格。 说明2由上述定义可知自环、重边均为圈。 3)对于B(O,M,I)中的概念(A1,B,)和 1.3属性拓扑图 (A2,B2),如果A,二A2,我们写作(A1,B,)≤ 定义3设(O,M,I)是一个形式背景。按如下 (A2,B2)。很容易看到(B(0,M,I);≤)是一 个完备格。 规则构造属性拓扑图(A(O,M,I),o): 例1形式背景(0，M,I),其中0={1,2,3,4， 1)设m1,m2∈M且m1≠m2o 5,6},M={a,b,c,d,e,fg{,关系I如表1所示。 ①若m'1正m'2,m'2立m',且m',∩m'2≠0，则用 “←→”连接m,和m2;

具有重要的意义。 概念是人类进行知识表达的一种手段，数据 库知识发现的过程就是将数据库中蕴含的知识 形式化成有用的概念的过程。 对形式背景的表 示及寻找背景下的所有概念是概念格理论研究 的基本问题。 近年来许多学者从图论的方面对 概念格进行研究，例如，张涛等［ ９］ 提出用属性拓 扑图来表示形式背景，并在此属性拓扑图的基础 上进行概念计算；Ａ． Ｂｅｒｒｙ 等［ １０］ 将形式背景构造 成二部图，利用团的思想生成概念；此外，李立峰 等［ １１］ 利用弦二部图对概念格进行表示，其中判 断弦二部图中是否有圈，是判断弦 二 部 图 的 关 键。 这也证实图论特别是图中的圈，在概念格的 研究中之重要。 本文结合图论的知识，将形式背景以属性拓扑 图表示出来，通过构造弱化的属性拓扑图，然后寻找 弱化的属性拓扑图中的权值 ｗ 之最大圈，用以生成 概念，从而构造出概念格，并结合实例分析了这一算 法的有效性。 １ 基本概念 本节将回顾概念格与图论的一些性质和定 义，关于概念格的更多内容参见文献［ １２］ ，有关 图论详细内容参见文献［ １３］ ，并且简单描述形式 背景的属性拓扑图表示方法，更多详细内容参见 文献［ ９，１４］ 。 １．１ 概念格 定义 １ １）形式背景（Ｏ，Ｍ，Ｉ）是一个三元组，其中 Ｏ 是 对象集，Ｍ 是属性集，Ｉ ÍＯ ´Ｍ。 Ｏ 和 Ｍ 中的元素分 别称为对象和属性。 ２）设 Ａ⊆Ｏ 且 Ｂ⊆Ｍ， 定义 Ａ′ ＝ ｛ｍ ÎＭ ｜ （"ｇ ÎＡ），ｇＩｍ｝ Ｂ′ ＝ ｛ｇ ÎＯ ｜ （"ｍ ÎＢ），ｇＩｍ｝； 若 Ａ′ ＝ Ｂ 且 Ｂ′ ＝ Ａ，则元素对（ Ａ，Ｂ） 是一个 概念。 Ａ 为概念（ Ａ，Ｂ） 的外延，Ｂ 为概念（ Ａ，Ｂ） 的内涵。 形式背景（ Ｏ，Ｍ，Ｉ） 的所有概念的集合 用 β （ Ｏ，Ｍ，Ｉ） 表示，称 β （ Ｏ，Ｍ，Ｉ） 为（ Ｏ，Ｍ， Ｉ） 的概念格。 ３）对 于 β （ Ｏ， Ｍ， Ｉ） 中 的 概 念 （ Ａ１ ， Ｂ１ ） 和 （ Ａ２ ， Ｂ２ ） ， 如 果 Ａ１ ÍＡ２ ， 我 们 写 作 （ Ａ１ ， Ｂ１ ） ≤ （ Ａ２ ，Ｂ２ ） 。 很容易看到（ β （ Ｏ，Ｍ， Ｉ） ；≤） 是 一 个完备格。 例 １ 形式背景（Ｏ，Ｍ，Ｉ），其中 Ｏ ＝ ｛１，２，３，４， ５，６｝，Ｍ＝ ｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ｝，关系 Ｉ 如表 １ 所示。 表 １ 形式背景（Ｏ，Ｍ，Ｉ） Ｔａｂｌｅ １ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ（Ｏ，Ｍ，Ｉ） 对像 ａ ｂ ｃ ｄ ｅ ｆ ｇ １ ´ ´ ´ ２ ´ ´ ´ ´ ３ ´ ´ ´ ４ ´ ´ ´ ´ ５ ´ ´ ６ ´ 表 １ 对应的形式背景的概念格见图 １。 图 １ β （Ｏ， Ｍ， Ｉ） Ｆｉｇ．１ β （Ｏ， Ｍ， Ｉ） 说明 １ 本文所讨论的形式背景中不含有满足 以下条件的属性和对象，ｍ ÎＭ， ｍ′ ＝ Ｏ 或 ｍ′ ＝ Æ； ｇ ÎＯ， ｇ′＝Ｍ 或 ｇ′＝ Æ。 １．２ 图论 定义 ２ １） 称数学结构 Ｇ ＝ ｛ Ｖ （ Ｇ）， Ｅ （ Ｇ）， ψＧ ｝为一个图，其中 Ｖ（Ｇ）为非空集合，ψＧ是从集合 Ｅ（Ｇ）到 Ｖ（Ｇ）´Ｖ（Ｇ）的一个映射， 则称 Ｇ 是一个以 Ｖ（Ｇ）为顶集合，以 Ｅ（Ｇ）为边集合的有向图，Ｖ（Ｇ） 中的元素称为 Ｇ 的顶点。 Ｅ（Ｇ）中的元素称为 Ｇ 的 边， ψＧ 称为 Ｇ 的关联函数。 若 ψＧ （ ｅ）＝ （ ｕ，ｖ），ｅ Î Ｅ（Ｇ），（ｕ，ｖ）ÎＶ（Ｇ）´Ｖ（Ｇ），简写成 ｅ ＝ ｕｖ，称 ｕ 是有 向边 ｅ 的尾，ｖ 是有向边 ｅ 的头。 擦掉有向图中的箭 头，则得到无向图。 ２）在顶边交错链 Ｐ ＝ ｖ０ ｅ１ ｖ１ ｅ２ … ｖｋ ｅｋ 中， ｅｉ Î Ｅ（Ｇ），ｉ ＝ １，２，…，ｋ，ｖｊ ÎＶ（Ｇ），ｊ ＝ １，２，…，ｋ，且 ｅｉ ＝ ｖｉ －１ ｖｉ，则称 Ｐ 是 Ｇ 的一条道路，其中允许 ｖｉ ＝ ｖｊ或 ｅｉ ＝ ｅｊ，ｉ ¹ｊ。 称 ｖ０是 ｐ 的起点，ｖｋ是 ｐ 的终点。 各顶相 异的道路称为轨道；起点与终点重合的轨道称为圈。 ３）在一个无向图中，只有一个顶的圈叫做自 环； ψＧ （ｅ１ ）＝ ψＧ （ｅ２ ）＝ （ｕ，ｖ），则称 ｅ１与 ｅ２是重边。 说明 ２ 由上述定义可知自环、重边均为圈。 １．３ 属性拓扑图 定义 ３ 设（Ｏ，Ｍ，Ｉ）是一个形式背景。 按如下 规则构造属性拓扑图（Ａ（Ｏ，Ｍ，Ｉ），ｗ）： １） 设 ｍ１ ，ｍ２ÎＭ 且 ｍ１≠ｍ２ 。 ①若 ｍ′１ Ëｍ′２ ，ｍ′２ Ëｍ′１ 且 ｍ′１ ∩ｍ′２ ¹Æ，则用 “«”连接 ｍ１和 ｍ２ ； ·５２０· 智 能 系 统 学 报 第 １１ 卷

第4期 毛华，等：基于权值最大圈的概念格构造算法 ·521. ②若m'1cm'2且m',∩m'2≠0，则用“→”连接 之间再添加一条边e,(图中用虚线表示)，并且令 m,和m2表示为m2→m1; e1的权值也为o(u,v)。 ③若m',∩m'2=g,则m,和m2没有边连接。 完成1)~3)后得到的加权无向图称为弱化的 2)设(A(0,M,I),w)为(0，M,I)的属性拓扑 属性拓扑图，用(R(O,M,I),w)表示。 图，e(m,m)∈E(A(0,M,I),o)),E(A(0,M,I), 此外，显然，在上述3)中的e与e,是重边。 w)为(A(0,M,I),w)的边集，e(m:,m)上的权值用 例3下面图3为图2所对应的(A(O,M,I), (m,m)表示，心(m,m)为属性m:和m之间的公 心)之弱化的属性拓扑图。 共对象{g1,g2,…,gn}的集合，称w(m:,m）为m:和 m之间的权值。 24 4,6 3)设m∈M,b∈M,若与m连接的边均为非单 {1,2,4} 24} 2.45 向入边，即与m连接的边均为m→b或m←b,则称 2) {4 m为顶层属性，顶层属性的集合用T表示。 例2图2为表1形式背景(0，M,I)对应的属 多 4124 3 性拓扑图。 h 3,4 {2,4} 123 3 2.4号 {2,41 5 (2 {4 {13.5 4得 图3(R(O,M,I),w) {4 1,2 3 Fig3(R(O,M,I),w】 1,3 定义4设(0，M,I)是一个形式背景，(R(0, {3 M,),心)是(O,M,I)对应的弱化的属性拓扑图， 5 {m1,m2,…,m,}cM且{m1,m2,…,mw}'≠，若不存 f 在任意m。∈M,m.是{m1,m2,…,m.},使得{m1, 图2(A(0,M,I),w) m2,…,m}'={m1,m2,…,m4,m。}',则称Y={m1, Fig.2 (A(O,M,I),w) m2,…,ma}为权值w({m1,m2,…,m%})的最大圈。 引理1设(0，M,)是一个形式背景，(A(0, 例如图3中，Y={bdga}为权值{2}的最大圈。 M,I),w)为(O,M,I)的属性拓扑图，若m∈T,则 说明3为了描述方便，有时将w(m,m)简写 (m',m)∈β(0，M,I)。 为W。 2.2算法过程 2概念格的构造 对于给定的形式背景(O,M,I),构造概念格的 在搜索概念的过程中，为了不受方向的限制，首 过程如下： 先进行属性拓扑图弱化，将有向图变为无向图，实际 输入形式背景(O,M,I)以及W(R(O,M,I), 上目前结合图论生成概念格的算法，都是在无向图 0)={w1,02,…,0n},0,≠0，T,s,n=1,2,…, 的基础上进行的。其次，给出弱化后属性拓扑图关 MI 于某个权值的最大圈的定义。最后，给出利用权值 2o 的最大圈构造概念算法，并进行算法分析。 输出所有概念B(0,M,I)1{(0,0),(0,M)}。 2.1弱化的属性拓扑图 1)对于(O,M,I),绘制属性拓扑图，根据属性 设(O,M,)是一个形式背景，按照如下规则对 拓扑图中的箭头指向，确定顶层属性集合T。 属性拓扑图进行弱化： 2)将属性拓扑图转化为弱化的属性拓扑图。 1)去掉属性拓扑图中的方向，得一无向图。 3)①初始将W(R(O,M,I),0)赋值给W,对任 2)若m在(A(0,M,I),w)中为顶层属性，则在 1)中的无向图中，加一个以m为顶点的自环。 意两，求n,=1,2,1。者 3)若在1)中的无向图中，包含权值w(u,v)的 0,∩w,=⑦或0：∩w=0,此处w:,0,地，∈W(R(0, 只有一条边e,其中，u、u为e的两个端点，则在u与

②若 ｍ′１Ìｍ′２且 ｍ′１∩ｍ′２¹Æ，则用“®” 连接 ｍ１和 ｍ２表示为 ｍ２®ｍ１ ； ③若 ｍ′１∩ｍ′２ ＝ Æ， 则 ｍ１和 ｍ２没有边连接。 ２） 设（Ａ（Ｏ，Ｍ，Ｉ），ｗ）为（Ｏ，Ｍ，Ｉ）的属性拓扑 图，ｅ（ｍｉ，ｍｊ）ÎＥ（ Ａ（Ｏ，Ｍ，Ｉ），ｗ）），Ｅ（ Ａ（Ｏ，Ｍ，Ｉ）， ｗ）为（Ａ（Ｏ，Ｍ，Ｉ），ｗ）的边集，ｅ（ｍｉ，ｍｊ）上的权值用 ｗ（ｍｉ，ｍｊ）表示，ｗ（ｍｉ，ｍｊ）为属性 ｍｉ和 ｍｊ之间的公 共对象｛ｇ１ ， ｇ２ ，…，ｇｎ ｝的集合，称 ｗ（ｍｉ，ｍｊ）为 ｍｉ和 ｍｊ之间的权值。 ３）设 ｍ ÎＭ，ｂ ÎＭ，若与 ｍ 连接的边均为非单 向入边，即与 ｍ 连接的边均为 ｍ ®ｂ 或 ｍ «ｂ，则称 ｍ 为顶层属性，顶层属性的集合用 Ｔ 表示。 例 ２ 图 ２ 为表 １ 形式背景（Ｏ，Ｍ，Ｉ）对应的属 性拓扑图。 图 ２ （Ａ（Ｏ，Ｍ，Ｉ），ｗ） Ｆｉｇ．２ （Ａ（Ｏ，Ｍ，Ｉ），ｗ） 引理 １ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ａ（Ｏ， Ｍ，Ｉ），ｗ） 为（Ｏ，Ｍ，Ｉ） 的属性拓扑图，若 ｍ ÎＴ，则 （ｍ′， ｍ）Îβ（Ｏ，Ｍ，Ｉ）。 ２ 概念格的构造 在搜索概念的过程中，为了不受方向的限制，首 先进行属性拓扑图弱化，将有向图变为无向图，实际 上目前结合图论生成概念格的算法，都是在无向图 的基础上进行的。 其次，给出弱化后属性拓扑图关 于某个权值的最大圈的定义。 最后，给出利用权值 的最大圈构造概念算法，并进行算法分析。 ２．１ 弱化的属性拓扑图 设（Ｏ，Ｍ，Ｉ）是一个形式背景，按照如下规则对 属性拓扑图进行弱化： １）去掉属性拓扑图中的方向，得一无向图。 ２）若 ｍ 在（Ａ（Ｏ，Ｍ，Ｉ），ｗ）中为顶层属性，则在 １）中的无向图中，加一个以 ｍ 为顶点的自环。 ３）若在 １）中的无向图中，包含权值 ｗ（ｕ，ｖ）的 只有一条边 ｅ，其中，ｕ、ｖ 为 ｅ 的两个端点，则在 ｕ 与 ｖ 之间再添加一条边 ｅ１（图中用虚线表示），并且令 ｅ１ 的权值也为 ｗ（ｕ，ｖ）。 完成 １） ～ ３）后得到的加权无向图称为弱化的 属性拓扑图，用（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）表示。 此外，显然，在上述 ３）中的 ｅ 与 ｅ１ 是重边。 例 ３ 下面图 ３ 为图 ２ 所对应的（Ａ（Ｏ，Ｍ，Ｉ）， ｗ）之弱化的属性拓扑图。 图 ３ （Ｒ（Ｏ，Ｍ，Ｉ），ｗ） Ｆｉｇ．３ （Ｒ（Ｏ，Ｍ，Ｉ），ｗ） 定义 ４ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ｒ（Ｏ， Ｍ，Ｉ），ｗ） 是（Ｏ，Ｍ，Ｉ） 对应的弱化的属性拓扑图， ｛ｍ１ ，ｍ２ ，…，ｍｈ ｝ÍＭ 且｛ｍ１ ，ｍ２ ，…，ｍｈ ｝¢¹Æ，若不存 在任意 ｍａ ÎＭ， ｍａ Ï｛ ｍ１ ，ｍ２ ，…，ｍｈ ｝， 使得｛ ｍ１ ， ｍ２ ，…，ｍｈ ｝¢＝ ｛ｍ１ ，ｍ２ ，…，ｍｈ ， ｍａ ｝ ¢，则称 Ｙ ＝ ｛ｍ１ ， ｍ２ ，…，ｍｈ ｝为权值 ｗ（｛ｍ１ ，ｍ２ ，…，ｍｈ ｝¢）的最大圈。 例如图 ３ 中，Ｙ ＝ ｛ｂｄｇａ｝为权值｛２｝的最大圈。 说明 ３ 为了描述方便，有时将 ｗ（ｍｉ，ｍｊ）简写 为 ｗ。 ２．２ 算法过程 对于给定的形式背景（Ｏ，Ｍ，Ｉ），构造概念格的 过程如下： 输入 形式背景（Ｏ，Ｍ，Ｉ）以及 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ）， ｗ） ＝ ｛ ｗ１ ， ｗ２ ， …， ｗｎ ｝， ｗｒ ¹ｗｓ， ｒ， ｓ， ｎ ＝ １， ２， …， Ｍ ２ ２ 。 输出 所有概念 β （Ｏ，Ｍ，Ｉ） ＼｛（Ｏ，Æ），（Æ，Ｍ）｝。 １）对于（Ｏ，Ｍ，Ｉ），绘制属性拓扑图，根据属性 拓扑图中的箭头指向，确定顶层属性集合 Ｔ。 ２）将属性拓扑图转化为弱化的属性拓扑图。 ３）①初始将 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）赋值给 Ｗｒ，对任 意 ｗｉ，ｗｊ ÎＷｒ，求 ｗｉ ∩ｗｊ， ｉ，ｊ ＝ １，２，…， Ｍ ２ ２ 。 若 ｗｉ∩ｗｊ ＝ Æ或 ｗｉ∩ｗｊ ＝ ｗｔ，此处 ｗｉ， ｗｊ， ｗｔÎＷ（Ｒ（Ｏ， 第 ４ 期 毛华，等：基于权值最大圈的概念格构造算法 ·５２１·

.522. 智能系统学报 第11卷 1)由一条边构成，也即自环： M,I),w),ij,t=1,2,…, ，。则进行4)。 2)由两条边构成，也即重边： ②若：∩0=w,0,W(R(0,M,),0),i,j,t= 3)由3条或3条以上的边构成，也即非自环非 ,则将W,={,,∩0，=，e,,6 1,2,…,2 重边的圈。 证明由定义2中3)可知，自环是只有一个顶 W(R(O,M,I),o),0,EW(R(0,M,I),e)}添加到 点的圈；重边是由两个顶点的圈：由定义2中3)可 W(R(O,M,I),w)中。将W,赋值给W,执行①。 知，非自环非重边的圈之顶点个数大于2。 4)取maxw,,开始寻找边上权值包含w,的最 当圈只有一个顶点时，根据定义2中3)可知， 大圈，记录权值心，最大圈的顶点为Y,对应概念为 此时的圈为一个自环： C={(A,B):A=w,B=Y}。 当圈有两个顶点时，根据定义2中3)可知，此 5)①根据4)的原则，若W中存在0+1，s=1,2, 时的圈为重边； …,|MP,则选定0+1，重复4)。 当圈的顶点个数大于2时，符合定义2中2)。 ②若W中不存在0+1，则停止。 因此，圈有且仅有自环、重边、非自环非重边的 若W(R(0,M,I),w)中的元素满足3)中的①， 圈3种情况。 若心，∩心，=0，或0：∩心=0，此处0：，0,0，∈W(R 定理1设(0，M,I)是一个形式背景，(R(0, M,I),w)是(O,M,I)对应的弱化的属性拓扑图，权 (0,M,),w),i,j,t=1,2,…, 1M2I 2 ,则能够进行 值最大圈一定能够生成一个概念。 4)、5),又因为W(R(0,M,I),w)是有限的，因此 证明由引理2可知，弱化的属性拓扑图的权 有限步后算法可以停止。 值w最大圈有且仅有3种情况，下面关于这3种情 若W(R(0,M,I),w)中的元素满足w:∩心= 况分别说明。 M,此 1)当圈为自环时 ,0,gW(R(0,M,),0),i,t=1,2,…, 2 m∈M,圈Y={m},由弱化的属性拓扑图的构造 时会将新生成的w,添加到W(R(O,M,I),0)中，由 1)可知，有meT。根据引理1，(m',m)∈β(0，M, 于w,地，心，c0,0为有限的，因此经过有限步后 I)。而m'=w(m,m),因此，((m,m),m)∈β(0， 一定可以进行3)中①，因此有限步后算法可停止。 M,I)。 2.3算法分析 2)当圈为重边时 根据文献[9]，可以看出1)的复杂度为 m1,m2∈M,圈Y={m1,m2},由弱化的属性拓扑 0门：步骤2将属性拓扑图弱化，首先判断每 图的构造2)可知，不存在其他权值为w(m1,m2)的 边，即不存在其他顶m,m∈M,使w(m1,m2)∈ 个属性是否为顶层属性，其复杂度为O(|M),其 0(m,m),i有，i≥3，j≥1。这就是说，除m1,m2 次需要判断是否为不能构成权值心的最大圈，其复 外，不存在其他属性所拥有的对象集包含w(m, 杂度为0 (MP (MP 2 ,所以2)的复杂度为02)： m2),所以(w(m1,m2),Y)eβ(0，M,)。 3)=当圈的顶点个数大于等于3时 若是3)中①，首先对W中任意两元素取交，有 m1,m2,…,m:∈M,i≥3，若圈Y={m1,m2,… orD个元素，进行og 次，若是3)中②， m},证明过程与第2种情况类似，易证(0(m1, m2),Y)∈β(0，M,I)。 对新生成的集合W,重复次3)，最多重复0次，所 引理3设W(R(0,M,I),0)是一个集族，则 以3)的复杂度为0 (01Wn12 ,其中W,伪元素 任意的其中0：，0，0，∈W(R(0,M,I),0),0.生W 2 IM2| 最多的集合；4)中，每到一个属性节点最多需要判 ((0,M,),0),,u=1,2,,2,它们之间 断M1次该节点是否在当前权值w的最大圈中， 的关系有且仅有以下3种情况之一发生： 最多判断M饮，所以4)的复杂度为0(|M2):5) 1)0:∩w:=0; 的复杂度为0(|OW.)。 2)0:∩0；=0， 因此，整个算法的复杂度为O(2wK10)。 3)0:∩0；=10u9 引理2圈有且仅有以下3种情况： 证明根据文献[15]，可得若W(R(0,M,I)

Ｍ，Ｉ），ｗ）， ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ 。 则进行 ４）。 ②若 ｗｉ∩ｗｊ ＝ｗｔ，ｗｔÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ ，则将 Ｗｒ ｒ ＝ ｛ｗｔ：ｗｉ∩ｗｊ ＝ｗｔ，ｗｉ， ｗｊ，Î Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｗｔ ÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）｝添加到 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中。 将 Ｗｒ ｒ赋值给 Ｗｒ，执行①。 ４）取 ｍａｘ êｗｓ ú，开始寻找边上权值包含 ｗｓ的最 大圈，记录权值 ｗｓ 最大圈的顶点为 Ｙ，对应概念为 Ｃ ＝ ｛（Ａ，Ｂ）： Ａ ＝ｗｓ， Ｂ ＝ Ｙ｝。 ５）①根据 ４）的原则，若 Ｗ 中存在 ｗｓ ＋１ ，ｓ ＝ １，２， …， êＭ ú ２ ，则选定 ｗｓ ＋１ ，重复 ４）。 ②若 Ｗ 中不存在 ｗｓ ＋１ ，则停止。 若 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中的元素满足 ３）中的①， 若 ｗｉ∩ｗｊ ＝ Æ，或 ｗｉ∩ｗｊ ＝ ｗｔ，此处 ｗｉ， ｗｊ，ｗｔ ÎＷ（Ｒ （Ｏ，Ｍ，Ｉ），ｗ）， ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ ，则能够进行 ４）、５），又因为êＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ） ú是有限的，因此 有限步后算法可以停止。 若 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ） 中的元素满足 ｗｉ ∩ｗｊ ＝ ｗｔ，ｗｔÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ ＝ １，２，…， Ｍ ２ ２ ，此 时会将新生成的 ｗｔ添加到 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中，由 于 ｗｒ¹ｗｓ，ｗｔ ÍＯ，êＯ ú为有限的，因此经过有限步后 一定可以进行 ３）中①，因此有限步后算法可停止。 ２．３ 算法分析 根据 文 献 ［ ９ ］， 可 以 看 出 １ ） 的 复 杂 度 为 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ ；步骤 ２ 将属性拓扑图弱化，首先判断每 个属性是否为顶层属性，其复杂度为 Ｏ( Ｍ ) ，其 次需要判断是否为不能构成权值 ｗ 的最大圈，其复 杂度为 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ ，所以 ２）的复杂度为 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ ； 若是 ３） 中 ①， 首先对 Ｗ 中任意两元素取交， 有 Ｏ( Ｗ ) 个元素，进行 Ｏ Ｗ ２ ２ æ è ç ö ø ÷ 次，若是 ３） 中②， 对新生成的集合 Ｗｒ ｒ重复次 ３），最多重复êＯ ú次，所 以 ３）的复杂度为 Ｏ Ｏ Ｗｒｒ ２ ２ æ è ç ö ø ÷ ，其中êＷｒ ｒ ú为元素 最多的集合；４） 中，每到一个属性节点最多需要判 断êＭ ú－１ 次该节点是否在当前权值 ｗ 的最大圈中， 最多判断êＭ ú次，所以 ４）的复杂度为 Ｏ Ｍ ２ ( ) ；５） 的复杂度为 Ｏ Ｏ Ｗｒｒ ( ) 。 因此，整个算法的复杂度为 Ｏ ２ Ｍ × Ｏ ( ) 。 引理 ２ 圈有且仅有以下 ３ 种情况： １）由一条边构成，也即自环； ２）由两条边构成，也即重边； ３）由 ３ 条或 ３ 条以上的边构成，也即非自环非 重边的圈。 证明 由定义 ２ 中 ３）可知，自环是只有一个顶 点的圈；重边是由两个顶点的圈；由定义 ２ 中 ３）可 知，非自环非重边的圈之顶点个数大于 ２。 当圈只有一个顶点时，根据定义 ２ 中 ３）可知， 此时的圈为一个自环； 当圈有两个顶点时，根据定义 ２ 中 ３）可知，此 时的圈为重边； 当圈的顶点个数大于 ２ 时，符合定义 ２ 中 ２）。 因此，圈有且仅有自环、重边、非自环非重边的 圈 ３ 种情况。 定理 １ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ｒ（Ｏ， Ｍ，Ｉ），ｗ）是（Ｏ，Ｍ，Ｉ）对应的弱化的属性拓扑图，权 值最大圈一定能够生成一个概念。 证明 由引理 ２ 可知，弱化的属性拓扑图的权 值 ｗ 最大圈有且仅有 ３ 种情况，下面关于这 ３ 种情 况分别说明。 １）当圈为自环时 ｍ ÎＭ，圈 Ｙ ＝ ｛ｍ｝，由弱化的属性拓扑图的构造 １）可知，有 ｍ ÎＴ。 根据引理 １，（ｍ′， ｍ） Îβ（Ｏ，Ｍ， Ｉ）。 而 ｍ′ ＝ ｗ（ｍ，ｍ），因此，（ｗ（ｍ，ｍ）， ｍ）Îβ（Ｏ， Ｍ，Ｉ）。 ２）当圈为重边时 ｍ１ ，ｍ２ÎＭ，圈 Ｙ ＝ ｛ｍ１ ，ｍ２ ｝，由弱化的属性拓扑 图的构造 ２）可知，不存在其他权值为 ｗ（ｍ１ ，ｍ２ ）的 边，即不存在其他顶 ｍｉ， ｍｊ ÎＭ，使 ｗ （ ｍ１ ， ｍ２ ） Í ｗ（ｍｉ， ｍｊ）， ｉ ¹ｊ， ｉ≥３， ｊ≥１。 这就是说，除 ｍ１ ， ｍ２ 外，不存在其他属性所拥有的对象集包含 ｗ（ ｍ１ ， ｍ２ ），所以（ｗ（ｍ１ ，ｍ２ ），Ｙ）Îβ（Ｏ，Ｍ，Ｉ）。 ３）＝ 当圈的顶点个数大于等于 ３ 时 ｍ１ ，ｍ２ ， … ，ｍｉÎＭ，ｉ≥３，若圈 Ｙ ＝ ｛ ｍ１ ，ｍ２ ， … ｍｉ｝，证明过程与第 ２ 种情况类似，易证 （ ｗ （ ｍ１ ， ｍ２ ），Ｙ）Îβ（Ｏ，Ｍ，Ｉ）。 引理 ３ 设 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）是一个集族，则 任意的其中 ｗｉ， ｗｊ， ｗｔ ÎＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｗｕ ÏＷ （Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ，ｕ ＝ １，２，…， Ｍ ２ ２ ，它们之间 的关系有且仅有以下 ３ 种情况之一发生： １）ｗｉ∩ｗｊ ＝ Æ； ２）ｗｉ∩ｗｊ ＝ｗｔ； ３）ｗｉ∩ｗｊ ＝ｗｕ 。 证明 根据文献［１５］，可得若 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ）， ·５２２· 智 能 系 统 学 报 第 １１ 卷

第4期 毛华，等：基于权值最大圈的概念格构造算法 ·523· w)是一个集族，则对于任意的0：，0,0，∈W(R(0, 余概念的产生必然导致算法的储存空间的增加，引 M,I),o),0.eW(R(0,M,I),0),i,j,t,u=1,2,…, 发空间复杂度的加大 11有且仅有，n,=⑦，n=,或w,n,9 本文算法用图论中的权值与最大圈结合来寻找 2 概念，由于不会重复对同一权值寻找其相应的最大 w.,3种情况之一发生： 圈，因此不会有冗余概念的产生。从而，必然在概念 定理2设(0，M,)是一个形式背景，(R(O, 寻找中，降低数据的储存空间，空间复杂度较张涛等 M,I),w)是(O,M,1)对应的弱化的属性拓扑图，通 的方法减少成为显然之事。 过权值0最大圈算法一定能够得到B(O,M,I)1 2)Bemy等[o]将形式背景构造成二部图，利用 {(0,0),(0,M)}。 团的思想生成概念，其计算每个概念的复杂度为 证明由引理3可知集族W(R(O,M,I),o)中 0(|M2)。 的权值之间有且仅有3种情况，对于任意的0：，心， 对于弱化的属性拓扑图产生概念有： w,∈W(R(O,M,I),w),0.W(R(O,M,I),e）,i,j, 1)对于只含有一个顶点属性的情况，由引理1 t,u=1,2,…, r以下对引理3中的3种情况分 可知，属性m为某个概念的内涵。在弱化的属性拓 2 扑图中属性m构成一个自环时，本文计算每个概念 别说明。 的复杂度 (1M2) 1)w:∩w,=0 2 说明任意3个属性之间没有公共对象，根据属 2)对于至少含有两个顶点属性的情况，本文计 性拓扑图的构造过程，其弱化的属性拓扑图为定理 算每个概念的算法复杂度O(|MP)。 1的第2种情况，得到的W(R(0,M,I),0)能够包 以上两种情形说明，当情形1)时，本文算法的 括所有概念的外延，因此，依次搜索W(R(O,M,I), 复杂度小于Bey等的：当情形2)时，本文算法的复 o)中的每一个权值w最大圈，即可得到B(O,M,)\ 杂度与Bemy等的相同。这说明，对于情形1)，本文 {(0,0),(0,M)}。 的算法优于Bery等的，虽然在其他情况（也就是情 2)0:∩0=0，w,∈W(R(0,M,I),0),i,j,t=1, 形2))，本文的算法与Be四等的具有相同的时间复 2,…,IMP,说明得到的W(R(O,M,I),w)能够包 杂度。 括所有概念的外延，符合定理的第2、3种情况。因 再有，由图论知识可知，每一个团必包含至少一 此，依次搜索W(R(O,M,I),o)中的每一个权值e 个圈，所以在判断团的过程中必然存在对圈的判断 最大圈，即可得到B(0,M,I)1{(0,⑦)，(0，M)}。 过程，当一个团中含有两个以上圈时，此时对团的判 3)若0：∩w=0,0,W(R(0,M,I),0）,i,j, 定过程会重复圈的判断过程。因此，Berry等的方法 t=1,2,…,MP,则说明当前W(R(O,M,),o) 会造成数据存储量过大。而本文算法，不会对相同 中不能包含所有概念的外延，将W,={w,:心：∩0 权值的圈进行重复判断与存储，因此，降低了数据存 =0,w,是W(R(O,M,I),0)}添加到W中，只需 储空间复杂度。 对W,中的任意两个元素取交集即可，由于引0是 3)李立峰等仅是从理论方面指出弦二部图 有限的，因此一定会有0：∩w,=0,0,∈W(R(0, 的概念格表示，并没有给出算法过程。所以他们的 M,I),0),i,j,t=1,2,…,|MP,此时说明得到的 方法只是理论过程，而无法直接实现。 W(R(O,M,I),0)能够包括所有概念的外延，并 本文中不仅给出了理论分析，并且将理论的内 且W(R(O,M,I),w)中的元素对应的最大圈符 容通过一个可行的算法加以实现，故此，本文的思想 合定理1的第2、3种情况。因此，依次搜索W(R 和方法可操作性强，易于直接理解与实现。 (O,M,),0)中的每一个权值w最大圈，即可得 由以上1)~3)的分析可以看出，本文给出的算 到B(0,M,I)1{(0,0),(0,M)}。 法与已有算法相比，计算出全部概念的时间复杂度 以上说明了本算法的正确性。下面将通过与已 并不低于以往的算法，基本相同。在数据存储空间 有的图论方法构造概念格的相关著名算法或方法的 方面，本文给出的算法与已有算法相比，空间复杂度 比较，分析得出本算法的优势。 降低。这样必然使得本算法在整个计算过程能在占 1)张涛等14)在属性拓扑的基础上给出概念计 用更小内存的情况下完成，同时也就对计算机器系 算方法，实际上是将图论中已有的深度优先算法应 统的运行空间降低了要求。因此本文算法要优于其 用于概念的寻找，如此可能导致产生冗余概念。冗 他一些已有算法或方法

ｗ）是一个集族，则对于任意的 ｗｉ， ｗｊ， ｗｔÎＷ（Ｒ（Ｏ， Ｍ，Ｉ），ｗ），ｗｕÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ，ｕ ＝ １，２，…， Ｍ ２ ２ 有且仅有 ｗｉ ∩ｗｊ ＝ Æ、ｗｉ ∩ｗｊ ＝ ｗｔ 或 ｗｉ ∩ｗｊ ＝ ｗｕ ，３ 种情况之一发生： 定理 ２ 设（Ｏ，Ｍ，Ｉ）是一个形式背景，（Ｒ（Ｏ， Ｍ，Ｉ），ｗ）是（Ｏ，Ｍ，Ｉ）对应的弱化的属性拓扑图，通 过权值 ｗ 最大圈算法一定能够得到 β （Ｏ，Ｍ，Ｉ） ＼ ｛（Ｏ，Æ），（Æ，Ｍ）｝。 证明 由引理 ３ 可知集族 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中 的权值之间有且仅有 ３ 种情况，对于任意的 ｗｉ， ｗｊ， ｗｔÎＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｗｕÏＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ， ｔ，ｕ ＝ １，２，…， Ｍ ２ ２ 以下对引理 ３ 中的 ３ 种情况分 别说明。 １）ｗｉ∩ｗｊ ＝ Æ 说明任意 ３ 个属性之间没有公共对象，根据属 性拓扑图的构造过程，其弱化的属性拓扑图为定理 １ 的第 ２ 种情况，得到的 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）能够包 括所有概念的外延，因此，依次搜索 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ）， ｗ）中的每一个权值 ｗ 最大圈，即可得到β（Ｏ，Ｍ，Ｉ） ＼ ｛（Ｏ，Æ），（Æ，Ｍ）｝。 ２）ｗｉ∩ｗｊ ＝ｗｔ，ｗｔÎＷ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ），ｉ，ｊ，ｔ ＝ １， ２，…， êＭ ú ２ ，说明得到的 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）能够包 括所有概念的外延，符合定理的第 ２、３ 种情况。 因 此，依次搜索 Ｗ（Ｒ（Ｏ，Ｍ，Ｉ），ｗ）中的每一个权值 ｗ 最大圈，即可得到 β（Ｏ，Ｍ，Ｉ） ＼｛（Ｏ，Æ），（Æ，Ｍ）｝。 ３）若 ｗｉ∩ｗｊ ＝ ｗｔ，ｗｔÏＷ（ Ｒ（Ｏ，Ｍ，Ｉ） ，ｗ） ，ｉ，ｊ， ｔ ＝ １，２，…， êＭ ú ２ ，则说明当前 Ｗ（ Ｒ（Ｏ，Ｍ，Ｉ） ，ｗ） 中不能包含所有概念的外延，将 Ｗｒ ＝ ｛ ｗｔ：ｗｉ∩ｗｊ ＝ ｗｔ，ｗｔ ÏＷ（ Ｒ（ Ｏ，Ｍ，Ｉ） ，ｗ） ｝ 添加到 Ｗ 中，只需 对 Ｗｒ中的任意两个元素取交集即可，由于êＯ ú是 有限的，因此一定会有 ｗｉ∩ｗｊ ＝ ｗｔ，ｗｔ ÎＷ（ Ｒ（ Ｏ， Ｍ，Ｉ） ，ｗ） ，ｉ，ｊ，ｔ ＝ １，２，…， êＭ ú ２ ，此时说明得到的 Ｗ（ Ｒ（Ｏ，Ｍ，Ｉ） ，ｗ） 能够包括所有概念的外延，并 且 Ｗ（ Ｒ（Ｏ，Ｍ，Ｉ） ，ｗ） 中的元素对应的最大圈符 合定理 １ 的第 ２、３ 种情况。 因此，依次搜索 Ｗ（ Ｒ （Ｏ，Ｍ，Ｉ） ，ｗ）中的每一个权值 ｗ 最大圈，即可得 到 β（Ｏ，Ｍ，Ｉ） ＼ ｛ （Ｏ，Æ） ，（ Æ，Ｍ） ｝ 。 以上说明了本算法的正确性。 下面将通过与已 有的图论方法构造概念格的相关著名算法或方法的 比较，分析得出本算法的优势。 １）张涛等［１４］在属性拓扑的基础上给出概念计 算方法，实际上是将图论中已有的深度优先算法应 用于概念的寻找，如此可能导致产生冗余概念。 冗 余概念的产生必然导致算法的储存空间的增加，引 发空间复杂度的加大。 本文算法用图论中的权值与最大圈结合来寻找 概念，由于不会重复对同一权值寻找其相应的最大 圈，因此不会有冗余概念的产生。 从而，必然在概念 寻找中，降低数据的储存空间，空间复杂度较张涛等 的方法减少成为显然之事。 ２）Ｂｅｒｒｙ 等［１０］ 将形式背景构造成二部图，利用 团的思想生成概念，其计算每个概念的复杂度为 Ｏ Ｍ ２ ( ) 。 对于弱化的属性拓扑图产生概念有： １）对于只含有一个顶点属性的情况，由引理 １ 可知，属性 ｍ 为某个概念的内涵。 在弱化的属性拓 扑图中属性 ｍ 构成一个自环时，本文计算每个概念 的复杂度 Ｏ Ｍ ２ ２ æ è ç ö ø ÷ 。 ２）对于至少含有两个顶点属性的情况，本文计 算每个概念的算法复杂度 Ｏ Ｍ ２ ( ) 。 以上两种情形说明，当情形 １）时，本文算法的 复杂度小于 Ｂｅｒｒｙ 等的；当情形 ２）时，本文算法的复 杂度与 Ｂｅｒｒｙ 等的相同。 这说明，对于情形 １），本文 的算法优于 Ｂｅｒｒｙ 等的，虽然在其他情况（也就是情 形 ２）），本文的算法与 Ｂｅｒｒｙ 等的具有相同的时间复 杂度。 再有，由图论知识可知，每一个团必包含至少一 个圈，所以在判断团的过程中必然存在对圈的判断 过程，当一个团中含有两个以上圈时，此时对团的判 定过程会重复圈的判断过程。 因此，Ｂｅｒｒｙ 等的方法 会造成数据存储量过大。 而本文算法，不会对相同 权值的圈进行重复判断与存储，因此，降低了数据存 储空间复杂度。 ３）李立峰等［１１］ 仅是从理论方面指出弦二部图 的概念格表示，并没有给出算法过程。 所以他们的 方法只是理论过程，而无法直接实现。 本文中不仅给出了理论分析，并且将理论的内 容通过一个可行的算法加以实现，故此，本文的思想 和方法可操作性强，易于直接理解与实现。 由以上 １） ～３）的分析可以看出，本文给出的算 法与已有算法相比，计算出全部概念的时间复杂度 并不低于以往的算法，基本相同。 在数据存储空间 方面，本文给出的算法与已有算法相比，空间复杂度 降低。 这样必然使得本算法在整个计算过程能在占 用更小内存的情况下完成，同时也就对计算机器系 统的运行空间降低了要求。 因此本文算法要优于其 他一些已有算法或方法。 第 ４ 期 毛华，等：基于权值最大圈的概念格构造算法 ·５２３·

.524. 智能系统学报 第11卷 3实例 a)=w(a1,a4)∩w(a4,a,)=…={1}及w(a1,a1) ∩w(a6,a7)=0(a1,a2)∩w(a6,a7）=…={3}, 结合实例，说明第2.2节中的算法有效性。以 {1},{3}W,将{1}与{3}添加到W,重复3)。 表2为形式背景(O,M1,11),进行概念的搜索，该 对{{1}，{3}}进行步骤3)中②，{1}∩{3}=0 背景从UCI机器学习数据库中，随机选取BLOG ,进行4)。 GER数据集的前40个对象进行试验，整理后得到 2.45,10 {5} 、{1.5.89y 如表2所示的形式背景。 1,92 {2,10 表2(0，M,41) {1379 L9 4.5p②.0 Table 2 Formal context (0,M,I) 1.3} 2 387 a. 对像a142a3a4a;。a 4}3y (8} {37}3 13,4118 {61 a3{68} 6) 3 3,4,67,八/ 4 图5(R(0,M,),o) 5 Fig5（R(O,M1,l),w) 6 7 根据4)，W={w(a1,a1),w(a2,a2）,0(a3, 8 a3),w(a4,a4),w(a6,a6),(a,a,),w(a1,a4), 9 o(a1,a6）,n(a1,a,),0(a2,a4),0(a2,a5),0 10 (a2,a6）,0(a2,a）,0(a3,a4）,0(a3,a6),0(a4, 其中，a,代表博主高学历，a,代表博主中等学 a),w(a5,a2),w(a6,a,),{1},{3}。 历，a,代表博主低学历，a,代表政治立场为左派，a 因为6=w(a7,a7)l≥4=|w(a1,a1)=|w(a2, 代表政治立场中立，a。代表政治立场为右派，a,代表 a2)=|w(a4,aa)=|w(a6,a6)l≥3=|w(a2,a,)l= 博客被当地媒体转载。 Iw(a,a)2 Iw(a,a)Iw(a,a)=Iw 根据1)，按照定义3中1)得到以表2为形式背 (a1,a,)l=lo(2,a5)=|0(a,a3）= 景的属性拓扑图，如图4。根据2)，按照定义4，构 lw(a6,a,)l≥1=o(a2,a6)=|w(a2,a4)l=|w 造出弱化的属性拓扑图(R(O1,M1,11),0),如图5。 (a3,aa)=|w(a3,a6)=|w(a5,a,)=|{1}= {3}1,所首先寻找包含w(a,a)={1,2,3,4,5,8引 {5 的最大圈，Y,={a,},对应的概念为(123458， a1)。 {1,9} {2,10 {2,4,5} /115,8} 根据5)中①，依次选择W中的其他元素重复 9L,3y 2} 4),概念分别为(1379，a),(24510,02),(158 4 9,a4),(3467,a6),(245,a2a),(158,a4a), 8} 3,7} (19,a1a4),(37,a1a6),(13,a1a),(210,a2 13,4} 8 a5),(68,a3),(34,a6a),(4,a2a6a),(5,a2a4 f6; a）,(8,a3a4a）,(6,a3a6）,(2,a2a5a),(1,a1 图4(A(01,M1,L1),w) a4a),(3,a1a6a)。 Fig.4 (A(O,M,I),w) 根据5)中②，停止。 最后添加(12345678910，⑦)和（⑦，a1a2 根据3)，W={w(a1,a1),(a2,a2）,0(a3, a3a4a5a6a,)后，得到概念格B(01,M1,l1)={(12 a3）,w(a4,aa),0(a6,a6）,w(a,a),0(a1,a4), 345678910,⑦)，(123458，a),(1379, w(a1,a6),0(a1,a7),o(a2,a4）,0(a2,as）, a1),(24510,a2),(1589,a4),(3467,a6),(2 (a2,a6),w(a2,a),(a3,a),(a3,6),0(a4,45,a2a,),(158,a4a),(19,a1a4),(37,a1a6), a),10(a5,a）,w(a6,a)}。 (13,a1a),(210,42a5),(68,a3),(34,a6a), 对于任意两个w(a,a)求交集，ij=1,2,…,7,(4,a2a6),(5,a2a41),(8,a3a4a1),(6,a 根据3)中②，可以发现存在w(a1,a1)∩w(a4, a6),(2,a2a5a7),(1,a1a4a),(3,a1a6a,）,(☑

３ 实例 结合实例，说明第 ２．２ 节中的算法有效性。 以 表 ２ 为形式背景（Ｏ１ ，Ｍ１ ，Ｉ１ ），进行概念的搜索，该 背景从 ＵＣＩ 机器学习数据库中，随机选取 ＢＬＯＧ⁃ ＧＥＲ 数据集的前 ４０ 个对象进行试验，整理后得到 如表 ２ 所示的形式背景。 表 ２ （Ｏ１ ，Ｍ１ ，Ｉ１ ） Ｔａｂｌｅ ２ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ （Ｏ１ ，Ｍ１ ，Ｉ１ ） 对像 ａ１ ａ２ ａ３ ａ４ ａ５ ａ６ ａ７ １ ´ ´ ´ ２ ´ ´ ´ ３ ´ ´ ´ ４ ´ ´ ´ ５ ´ ´ ´ ６ ´ ´ ７ ´ ´ ８ ´ ´ ´ ９ ´ ´ １０ ´ ´ 其中，ａ１ 代表博主高学历，ａ２ 代表博主中等学 历，ａ３代表博主低学历，ａ４代表政治立场为左派，ａ５ 代表政治立场中立，ａ６代表政治立场为右派，ａ７代表 博客被当地媒体转载。 根据 １），按照定义 ３ 中 １）得到以表 ２ 为形式背 景的属性拓扑图，如图 ４。 根据 ２），按照定义 ４，构 造出弱化的属性拓扑图（Ｒ（Ｏ１ ，Ｍ１ ，Ｉ１ ），ｗ），如图 ５。 图 ４ （Ａ（Ｏ１ ，Ｍ１ ，Ｉ１ ），ｗ） Ｆｉｇ．４ （Ａ（Ｏ１ ，Ｍ１ ，Ｉ１ ），ｗ） 根据 ３），Ｗ ＝ ｛ｗ（ ａ１ ，ａ１ ）， ｗ（ ａ２ ，ａ２ ）， ｗ（ ａ３ ， ａ３ ）， ｗ（ａ４ ，ａ４ ）， ｗ（ ａ６ ，ａ６ ）， ｗ（ ａ７ ，ａ７ ），ｗ（ ａ１ ，ａ４ ）， ｗ（ａ１ ，ａ６ ）， ｗ（ ａ１ ，ａ７ ）， ｗ（ ａ２ ，ａ４ ）， ｗ（ ａ２ ，ａ５ ）， ｗ （ａ２ ，ａ６ ）， ｗ（ａ２ ，ａ７ ）， ｗ（ａ３ ，ａ４ ）， ｗ（ａ３ ，ａ６ ）， ｗ（ａ４ ， ａ７ ）， ｗ（ａ５ ，ａ７ ）， ｗ（ａ６ ，ａ７ ）｝。 对于任意两个 ｗ（ａｉ，ａｊ）求交集，ｉ，ｊ ＝ １，２，…，７， 根据 ３）中②，可以发现存在 ｗ（ａ１ ，ａ１ ）∩ ｗ（ａ４ ， ａ７ ）＝ ｗ（ａ１ ，ａ４ ）∩ ｗ（ａ４ ，ａ７ ）＝ …＝ ｛１｝及 ｗ（ａ１ ，ａ１ ） ∩ ｗ（ ａ６ ，ａ７ ） ＝ ｗ（ ａ１ ，ａ７ ） ∩ ｗ（ ａ６ ，ａ７ ） ＝ … ＝ ｛３｝， ｛１｝，｛３｝ÏＷ，将｛１｝与｛３｝添加到 Ｗ，重复 ３）。 对｛｛１｝，｛３｝｝进行步骤 ３）中②，｛１｝∩｛３｝ ＝ Æ ，进行 ４）。 图 ５ （Ｒ（Ｏ１ ，Ｍ１ ，Ｉ１ ），ｗ） Ｆｉｇ．５ （Ｒ（Ｏ１ ，Ｍ１ ，Ｉ１ ），ｗ） 根据 ４），Ｗ ＝ ｛ｗ（ ａ１ ，ａ１ ）， ｗ（ ａ２ ，ａ２ ）， ｗ（ ａ３ ， ａ３ ）， ｗ（ａ４ ，ａ４ ）， ｗ（ ａ６ ，ａ６ ）， ｗ（ ａ７ ，ａ７ ），ｗ（ ａ１ ，ａ４ ）， ｗ（ａ１ ，ａ６ ）， ｗ（ ａ１ ，ａ７ ）， ｗ（ ａ２ ，ａ４ ）， ｗ（ ａ２ ，ａ５ ）， ｗ （ａ２ ，ａ６ ）， ｗ（ａ２ ，ａ７ ）， ｗ（ａ３ ，ａ４ ）， ｗ（ａ３ ，ａ６ ）， ｗ（ａ４ ， ａ７ ）， ｗ（ａ５ ，ａ７ ）， ｗ（ａ６ ，ａ７ ）， ｛１｝，｛３｝｝。 因为 ６ ＝ êｗ（ａ７ ，ａ７ ）ú≥４ ＝ êｗ（ａ１ ，ａ１ ）ú＝ êｗ（ａ２ ， ａ２ ）ú＝ êｗ（ａ４ ，ａ４ ）ú＝ êｗ（ａ６ ，ａ６ ）ú≥３ ＝ êｗ（ａ２ ，ａ７ ）ú＝ êｗ（ａ４ ，ａ７ ） ú≥２ êｗ（ ａ１ ，ａ４ ） ú ＝ êｗ（ ａ１ ，ａ６ ） ú ＝ êｗ （ａ１ ， ａ７ ） ú ＝ êｗ （ ａ２ ， ａ５ ） ú ＝ êｗ （ ａ３ ， ａ３ ） ú ＝ êｗ（ａ６ ，ａ７ ）ú≥１ ＝ êｗ（ ａ２ ，ａ６ ） ú ＝ êｗ （ ａ２ ， ａ４ ） ú ＝ êｗ （ａ３ ，ａ４ ） ú＝ êｗ（ ａ３ ，ａ６ ） ú＝ êｗ（ ａ５ ，ａ７ ） ú ＝ ê｛１｝ ú ＝ ê ｛３｝ú，所首先寻找包含 ｗ（ ａ７ ，ａ７ ） ＝ ｛１，２，３，４，５，８｝ 的最大圈，Ｙ１ ＝ ｛ ａ７ ｝，对应的概念为（１ ２ ３ ４ ５ ８， ａ７ ）。 根据 ５） 中①，依次选择 Ｗ 中的其他元素重复 ４），概念分别为（１ ３ ７ ９，ａ１ ），（２ ４ ５ １０，ａ２ ），（１ ５ ８ ９，ａ４ ），（３ ４ ６ ７，ａ６ ）， （２ ４ ５，ａ２ ａ７ ），（１ ５ ８，ａ４ ａ７ ）， （１ ９，ａ１ ａ４ ），（ ３ ７，ａ１ ａ６ ），（ １ ３，ａ１ ａ７ ）， （ ２ １０， ａ２ ａ５ ）， （６ ８，ａ３ ），（３ ４，ａ６ ａ７ ），（４，ａ２ ａ６ ａ７ ），（５，ａ２ ａ４ ａ７ ），（８， ａ３ ａ４ ａ７ ），（６，ａ３ ａ６ ），（２， ａ２ ａ５ ａ７ ），（１， ａ１ ａ４ ａ７ ），（３， ａ１ ａ６ ａ７ ）。 根据 ５）中②，停止。 最后添加（１ ２ ３ ４ ５ ６ ７ ８ ９ １０，Æ）和（Æ，ａ１ ａ２ ａ３ ａ４ ａ５ ａ６ ａ７ ）后，得到概念格 β （Ｏ１ ，Ｍ１ ，Ｉ１ ）＝ ｛（１ ２ ３ ４ ５ ６ ７ ８ ９ １０，Æ），（１ ２ ３ ４ ５ ８，ａ７ ），（１ ３ ７ ９， ａ１ ），（２ ４ ５ １０，ａ２ ），（１ ５ ８ ９，ａ４ ），（３ ４ ６ ７，ａ６ ）， （２ ４ ５，ａ２ ａ７ ），（１ ５ ８，ａ４ ａ７ ），（１ ９，ａ１ ａ４ ），（３ ７，ａ１ ａ６ ）， （１ ３，ａ１ ａ７ ），（２ １０，ａ２ ａ５ ）， （６ ８，ａ３ ），（３ ４，ａ６ ａ７ ）， （４，ａ２ ａ６ ａ７ ），（５，ａ２ ａ４ ａ７ ），（ ８， ａ３ ａ４ ａ７ ），（ ６，ａ３ ａ６ ），（２， ａ２ ａ５ ａ７ ），（１， ａ１ ａ４ ａ７ ），（３， ａ１ ａ６ ａ７ ） ，（Æ， ·５２４· 智 能 系 统 学 报 第 １１ 卷

第4期 毛华，等：基于权值最大圈的概念格构造算法 .525. a1a2a3a4a5a6a7)}。 WANG Xuyang,LI Ming.Method of data mining based on 在本实例中，步骤2)，弱化属性拓扑图，以 concept lattice[J].Computer applications,2005,25(4): w(a1,a1)为例进行复杂度计算，判断是否有w(a1, 827-829. a1)c0(a,a),其中i,j=1,2,…,16,对于w(a1,a1) [5]SIFF M,REPS T.Identifying modules via concept analysis 进行16次比较可得a,为顶层属性。对每个0∈W [C]//Proceedings of International Conference on Software Maintenance.Washington,DC.USA:IEEE Computer Soci- 重复上述比较过程，可得到弱化的属性拓扑图。 ety,1997:170-179. 3)对任意两个元素心，w∈W,i,j=1,2,…,16, [6]FERJANI F,ELLOUMI S,JAOUA A,et al.Formal context 取交集，此过程需要进行18义1”次，得到WU1U coverage based on isolated labels:an efficient solution for 2 text feature extraction J].Information sciences,2012, {3},对{{1}，{3}}执行步骤3)中②，此过程进行1 188：198-214. 次，可以看出符合3)中①，可转4)。 [7]邓君，马晓君，张巨峰，等.基于概念格的实体档案馆用 户行为研究[].图书情报工作，2014,58(12)：109-117. 4)取W中的元素w(a7,a,),判断w(a,a7)sw DENG Jun,MA Xiaojun,ZHANG Jufeng,et al.Study on (a:,4)其中i,j=1,2,…,20,每个元素比较20次， entity archives'user behavior based on concept lattice[J]. 寻找最大圈，得到概念(123458，a,)。 Library and information service,2014,58(12):109-117. 5)依次取W中的其他元素，重复4)，在此例W [8]张晓，龙伟，卢斌.基于概念格的关联规则在排产管理 中的18个元素，4)需要重复18次。 的应用[J].计算机工程与应用，2014,50(9)：264 在复杂度上，本文算法与张涛等的算法相同。 270.v ZHANG Xiao,LONG Wei,LU Bin.Application of 并且利用张涛等的算法对(O,M,I1)进行概念的 association rule based on concept lattice for scheduling man- 计算，得到的概念格与本文算法的结果相同。从而 agement[J].Computer engineering and applications,2014, 50(9):264-270. 说明了本文算法的有效性与正确性。 [9]张涛，任宏面.形式背景的属性拓扑表示[J刀.小型微型 4结束语 计算机系统，2014,35(3)：590-593. ZHANG Tao,REN Honglei.Attribute topology of formal 本文结合图论的知识，将形式背景对应的属性 context[J].Journal of Chinese computer systems,2014,35 拓扑图弱化，提出了一种利用权值最大圈寻找概念 (3):590-593. 的算法。与现有的算法比较，本文提出一种新的思 [10]BERRY A,SIGAYRET A.Representing a concept lattice 路来搜索概念，此外通过弱化的属性拓扑图，对于概 by a graph[J].Discrete applied mathematics,2004,144 (1/2):27-42. 念的可视化也得到了很好的体现：通过实例可知，该 [11]李立峰，刘三阳，罗清君.弦二部图的概念格表示[J]: 方法能够有效地构造概念格，为知识获取和数据处 电子学报，2013,41(7)：1384-1388. 理提供了一种有益的思想。通过分析可知，虽然本 LI Lifeng,LIU Sanyang,LUO Qingjun.Representing chor- 文提出的算法产生全部概念的空间复杂度降低，但由 dal bipartite graph using concept lattice theory[J].Acta 于其时间复杂度仍为指数级，因此对于数据量较大的 electronica sinica,2013,41(7):1384-1388. 情况，计算时间方面需要进一步研究，以便提高应用 [12]DAVEY B A,PRIESTLEY H A.Introduction to lattices 其进行数据分析的效率。 and order[M].2nd ed.New York:Cambridge University Press,2002:66-69 参考文献： [13]王树禾.图论[M].北京：科学出版社，2009 [14]ZHANG Tao,REN Honglei,WANG Xiaomin.A calcula- [1]WILLE R.Restructuring lattice theory:an approach based tion of formal concept by attribute topology[J].ICIC ex- on hierarchies of concepts[M]//RIVAL I.Ordered Sets. press letters part B:applications,2013,4(3):793-800. Dordrecht:Springer,1982. [15]方嘉琳集合论[M].长春：吉林人民出版社，1982. [2]BELOHLAVEK R,SIGMUND E,ZACPAL J.Evaluation of 作者简介： IPAQ questionnaires supported by formal concept analysis 毛华，女，1963年生，教授，博士，主 [J].Information sciences,2011,181(10):1774-1786. 要研究方向为计算机数学及其应用、拟 [3]NGUYEN TT,HUI S C,CHANG Kuiyu.A lattice-based 阵理论、离散数学。发表学术论文90 approach for mathematical search using formal concept anal- 余篇，其中被SCIEI检索20余篇。 ysis[J].Expert systems with applications,2012,39(5): 5820-5828. [4]王旭杨，李明.基于概念格的数据挖掘方法研究[J].计 算机应用.2005,25(4)：827-829

ａ１ ａ２ ａ３ ａ４ ａ５ ａ６ ａ７ ）｝。 在本实例中， 步骤 ２）， 弱化属性拓扑图， 以 ｗ（ａ１ ，ａ１ ）为例进行复杂度计算，判断是否有 ｗ（ ａ１ ， ａ１ ）Íｗ（ａｉ，ａｊ），其中 ｉ，ｊ ＝ １，２，…，１６，对于 ｗ（ａ１ ，ａ１ ） 进行 １６ 次比较可得 ａ１为顶层属性。 对每个 ｗ ÎＷ 重复上述比较过程，可得到弱化的属性拓扑图。 ３）对任意两个元素 ｗｉ，ｗｊÎＷ，ｉ，ｊ ＝ １，２，…，１６， 取交集，此过程需要进行 １８ × １７ ２ 次，得到Ｗ È｛１｝È ｛３｝，对｛｛１｝，｛３｝｝执行步骤 ３）中②，此过程进行 １ 次，可以看出符合 ３）中①，可转 ４）。 ４）取 Ｗ 中的元素 ｗ（ａ７ ，ａ７ ），判断 ｗ（ａ７ ，ａ７ ）Íｗ （ａｉ，ａｊ） 其中 ｉ，ｊ ＝ １，２，…，２０，每个元素比较 ２０ 次， 寻找最大圈，得到概念（１ ２ ３ ４ ５ ８，ａ７ ）。 ５）依次取 Ｗ 中的其他元素，重复 ４），在此例 Ｗ 中的 １８ 个元素，４）需要重复 １８ 次。 在复杂度上，本文算法与张涛等的算法相同。 并且利用张涛等的算法对（Ｏ１ ，Ｍ１ ，Ｉ１ ） 进行概念的 计算，得到的概念格与本文算法的结果相同。 从而 说明了本文算法的有效性与正确性。 ４ 结束语 本文结合图论的知识，将形式背景对应的属性 拓扑图弱化，提出了一种利用权值最大圈寻找概念 的算法。 与现有的算法比较，本文提出一种新的思 路来搜索概念，此外通过弱化的属性拓扑图，对于概 念的可视化也得到了很好的体现；通过实例可知，该 方法能够有效地构造概念格，为知识获取和数据处 理提供了一种有益的思想。 通过分析可知，虽然本 文提出的算法产生全部概念的空间复杂度降低，但由 于其时间复杂度仍为指数级，因此对于数据量较大的 情况，计算时间方面需要进一步研究，以便提高应用 其进行数据分析的效率。 参考文献： ［１］ＷＩＬＬＥ Ｒ． Ｒｅｓｔｒｕｃｔｕｒｉｎｇ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ： ａｎ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｅｓ ｏｆ ｃｏｎｃｅｐｔｓ ［ Ｍ］ ／ ／ ＲＩＶＡＬ Ｉ． Ｏｒｄｅｒｅｄ Ｓｅｔｓ． Ｄｏｒｄｒｅｃｈｔ： Ｓｐｒｉｎｇｅｒ， １９８２． ［２］ＢＥＬＯＨＬＡＶＥＫ Ｒ， ＳＩＧＭＵＮＤ Ｅ， ＺＡＣＰＡＬ Ｊ． Ｅｖａｌｕａｔｉｏｎ ｏｆ ＩＰＡＱ ｑｕｅｓｔｉｏｎｎａｉｒｅｓ ｓｕｐｐｏｒｔｅｄ ｂｙ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１１， １８１（１０）： １７７４－１７８６． ［３］ＮＧＵＹＥＮ Ｔ Ｔ， ＨＵＩ Ｓ Ｃ， ＣＨＡＮＧ Ｋｕｉｙｕ． Ａ ｌａｔｔｉｃｅ－ｂａｓｅｄ ａｐｐｒｏａｃｈ ｆｏｒ ｍａｔｈｅｍａｔｉｃａｌ ｓｅａｒｃｈ ｕｓｉｎｇ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌ⁃ ｙｓｉｓ［ Ｊ］． Ｅｘｐｅｒｔ ｓｙｓｔｅｍｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１２， ３９（５）： ５８２０－５８２８． ［４］王旭杨， 李明． 基于概念格的数据挖掘方法研究［ Ｊ］． 计 算机应用， ２００５， ２５（４）： ８２７－８２９． ＷＡＮＧ Ｘｕｙａｎｇ， ＬＩ Ｍｉｎｇ． Ｍｅｔｈｏｄ ｏｆ ｄａｔａ ｍｉｎｉｎｇ ｂａｓｅｄ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２００５， ２５（ ４）： ８２７－８２９． ［５］ＳＩＦＦ Ｍ， ＲＥＰＳ Ｔ． Ｉｄｅｎｔｉｆｙｉｎｇ ｍｏｄｕｌｅｓ ｖｉａ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｏｆｔｗａｒｅ Ｍａｉｎｔｅｎａｎｃｅ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉ⁃ ｅｔｙ， １９９７： １７０－１７９． ［６］ＦＥＲＪＡＮＩ Ｆ， ＥＬＬＯＵＭＩ Ｓ， ＪＡＯＵＡ Ａ， ｅｔ ａｌ． Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｃｏｖｅｒａｇｅ ｂａｓｅｄ ｏｎ ｉｓｏｌａｔｅｄ ｌａｂｅｌｓ： ａｎ ｅｆｆｉｃｉｅｎｔ ｓｏｌｕｔｉｏｎ ｆｏｒ ｔｅｘｔ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ［ Ｊ ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１２， １８８： １９８－２１４． ［７］邓君， 马晓君， 张巨峰， 等． 基于概念格的实体档案馆用 户行为研究［Ｊ］． 图书情报工作， ２０１４， ５８（１２）： １０９－１１７． ＤＥＮＧ Ｊｕｎ， ＭＡ Ｘｉａｏｊｕｎ， ＺＨＡＮＧ Ｊｕｆｅｎｇ， ｅｔ ａｌ． Ｓｔｕｄｙ ｏｎ ｅｎｔｉｔｙ ａｒｃｈｉｖｅｓ’ ｕｓｅｒ ｂｅｈａｖｉｏｒ ｂａｓｅｄ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ［ Ｊ］． Ｌｉｂｒａｒｙ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｅｒｖｉｃｅ， ２０１４， ５８（１２）： １０９－１１７． ［８］张晓， 龙伟， 卢斌． 基于概念格的关联规则在排产管理 的应用［ Ｊ］． 计算机工程与应用， ２０１４， ５０ （ ９）： ２６４ － ２７０． ｖ ＺＨＡＮＧ Ｘｉａｏ， ＬＯＮＧ Ｗｅｉ， ＬＵ Ｂｉｎ． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅ ｂａｓｅｄ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｆｏｒ ｓｃｈｅｄｕｌｉｎｇ ｍａｎ⁃ ａｇｅｍｅｎｔ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ５０（９）： ２６４－２７０． ［９］张涛， 任宏雷． 形式背景的属性拓扑表示［ Ｊ］． 小型微型 计算机系统， ２０１４， ３５（３）： ５９０－５９３． ＺＨＡＮＧ Ｔａｏ， ＲＥＮ Ｈｏｎｇｌｅｉ． Ａｔｔｒｉｂｕｔｅ ｔｏｐｏｌｏｇｙ ｏｆ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１４， ３５ （３）： ５９０－５９３． ［１０］ＢＥＲＲＹ Ａ， ＳＩＧＡＹＲＥＴ Ａ． Ｒｅｐｒｅｓｅｎｔｉｎｇ ａ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｂｙ ａ ｇｒａｐｈ［ Ｊ］． Ｄｉｓｃｒｅｔｅ ａｐｐｌｉｅｄ ｍａｔｈｅｍａｔｉｃｓ， ２００４， １４４ （１ ／ ２）： ２７－４２． ［１１］李立峰， 刘三阳， 罗清君． 弦二部图的概念格表示［ Ｊ］． 电子学报， ２０１３， ４１（７）： １３８４－１３８８． ＬＩ Ｌｉｆｅｎｇ， ＬＩＵ Ｓａｎｙａｎｇ， ＬＵＯ Ｑｉｎｇｊｕｎ． Ｒｅｐｒｅｓｅｎｔｉｎｇ ｃｈｏｒ⁃ ｄａｌ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｕｓｉｎｇ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ ［ Ｊ］． Ａｃｔａ ｅｌｅｃｔｒｏｎｉｃａ ｓｉｎｉｃａ， ２０１３， ４１（７）： １３８４－１３８８． ［１２］ ＤＡＶＥＹ Ｂ Ａ， ＰＲＩＥＳＴＬＥＹ Ｈ Ａ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｌａｔｔｉｃｅｓ ａｎｄ ｏｒｄｅｒ［Ｍ］． ２ｎｄ ｅｄ． Ｎｅｗ Ｙｏｒｋ： Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， ２００２： ６６－６９． ［１３］王树禾． 图论［Ｍ］． 北京： 科学出版社， ２００９． ［１４］ＺＨＡＮＧ Ｔａｏ， ＲＥＮ Ｈｏｎｇｌｅｉ， ＷＡＮＧ Ｘｉａｏｍｉｎ． Ａ ｃａｌｃｕｌａ⁃ ｔｉｏｎ ｏｆ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ｂｙ ａｔｔｒｉｂｕｔｅ ｔｏｐｏｌｏｇｙ［ Ｊ］． ＩＣＩＣ ｅｘ⁃ ｐｒｅｓｓ ｌｅｔｔｅｒｓ ｐａｒｔ Ｂ： ａｐｐｌｉｃａｔｉｏｎｓ， ２０１３， ４（３）： ７９３－８００． ［１５］方嘉琳． 集合论［Ｍ］． 长春： 吉林人民出版社， １９８２． 作者简介： 毛华，女，１９６３ 年生，教授，博士，主 要研究方向为计算机数学及其应用、拟 阵理论、离散数学。 发表学术论文 ９０ 余篇，其中被 ＳＣＩ、ＥＩ 检索 ２０ 余篇。 第 ４ 期 毛华，等：基于权值最大圈的概念格构造算法 ·５２５·