形式概念分析中的对象概念与属性概念

智慧来，智东杰

河南理工大学 计算机科学与技术学院，河南 焦作 454150

形式概念分析中的对象概念与属性概念

智慧来，智东杰

河南理工大学 计算机科学与技术学院，河南 焦作 454150

1 引言

形式概念分析[1]是Ganter B和Wille R提出的，以序理论和完备格理论为基础，依据数据库中提供的基本信息建立起的一种刻画对象与属性之间关系的数学结构。形式概念分析强调以人的认知为中心，提供了一种与传统的、统计的数据分析和知识表示完全不同的方法。由于它便于概念结构的开发和讨论，在某种意义上，概念格已经变成了一种外部认知的手段[2]。概念格已经有许多比较成功的应用，例如：姜峰等利用扩展概念格在Web上进行服务关系的自动挖掘和维护[3]，丁卫平等利用形式概念分析的理论对不完备电子病历系统进行数据挖掘[4]。为了进一步提高数据表示和数据挖掘的效率，有必要对其中的特殊概念进行更深入的研究。

2 基本概念

以下的定义来源于Ganter B和Wille R的著作“Formal Concept Analysis：Mathematical Foundation”[1]。为了本文写作的需要，使用的符号和论述方式可能有所不同。

定义1设K=（G，Μ，I）是一个形式背景，A⊆G，B⊆Μ。如果A、B满足条件f（A）=B、g（B）=A，则称序对（A，B）为形式背景K的一个概念。A称为概念（A，B）的外延，B称为概念（A，B）的内涵。L（G，Μ，I）或L（K）表示K中所有概念全体构成的集合，即：L（G，Μ，I）={（A×B）∈G×Μ，f（A）=B，g（B）=A}。其中，f(A)={m∈Μ|∀g∈A,gIm}，g(B)={g∈G|∀m∈B，gIm}。

定义2设K=（G，Μ，I）是一个形式背景，(A1，B1)、(A2，B2)∈L(K)，如果A1⊆A2或B1⊇B2，称(A1，B1)是(A2，B2)的子概念，记为(A1，B1)≤(A2，B2)。显然L（K）关于“≤”构成一个格，称为概念格。

定义3在一个概念格中，如果一个概念具有形式（g（f（g）），f（g））且g∈G，则称（g（f（g）），f（g））是一个对象概念；如果一个概念具有形式（g（m），f（g（m）））且m∈Μ，则称（g（m），f（g（m）））是一个属性概念。

定义4集合Μ与N之间的二元关系R是有序二元组（m，n）的集合，其中m∈Μ，n∈N，即R⊆Μ×N，这里的×是笛卡儿积，（m，n）∈R，也常记做mRn，如果Μ=N，则称R是Μ上的二元关系。R的逆关系用R-1表示，即nR-1m⇔mRn。

定义5集合Μ上的二元关系R称为一个偏序关系，如果对所有的x，y，z∈Μ都有：①xRx；②xRy和x≠y⇒不是yRx；③xRy和yRz⇒xRz。偏序关系R常用≤来表示，当x≤y且x≠y时，写做x＜y。一个集合Μ及其上的序≤形成的有序二元组（Μ，≤）称为半序集。

定义6令（Μ，≤）是一个半序集，A是Μ的子集，Μ中的元素s满足∀a∈A都有s≤a，则称s是A的一个下界。对偶地，若Μ中的元素s满足∀a∈A都有s≥a，则称s是A的一个上界。如果A的所有下界组成的集合中有最大元素，则称这个元素为A的下确界，记infA或∧A。对偶地，上界集合的最小元素称为上确界，记supA或∨A。

定义7一个半序集（V，≤），如果V中任意两个元素x，y的上确界及下确界都存在，则称V是一个格。如果V的任何子集X的上确界及下确界都存在，则称V是一个完全格。

定义8对于完全格V的一个元素v，定义vl=∨{x∈V|x＜v}，vu=∨{x∈V|x＜v}，如果v≠vl即v不是严格小于它的那些元素的上确界，则称v是上确界不可约的，或者称v是上确界不可约元；如果v≠vu，即v不是严格大于它的那些元素的下确界，则称v是下确界不可约的，或者称v是下确界不可约元。

在不区分上确界不可约元和下确界不可约元的情况下，它们统称为不可约元。

定义9a称为b的下近邻，当a＜b，且没有c满足a＜c＜b，这时也称b是a的上近邻，并且记做a≺b。

命题1有限格的一个元素是上确界不可约的，当且仅当它有且仅有一个下近邻；一个元素是下确界不可约的，当且仅当它有且仅有一个上近邻。

在概念格中，一个概念的下近邻是它的子概念，一个概念的上近邻是它的父概念。

3 对象（属性）概念的识别

定理1对象概念是上确界不可约元，上确界不可约元一定是对象概念；对偶的，属性概念是下确界不可约元，下确界不可约元一定是属性概念。

证明如果一个概念有两个或两个以上的下近邻，则这个概念的外延缩减的势大于等于2，因此不存在唯一一个对象g∈G使得（g（f（g）），f（g））成立；如果一个概念只有一个下近邻，则这个概念的对象标签为这个概念的外延减去下近邻概念的外延。根据概念格的对偶原理，可知定理的后半部分成立。

根据定理1可以得到概念格中对象概念的识别算法，同时为对象概念贴上对象标签。

算法1概念格中对象概念的识别算法

步骤1访问概念格中的最小概念，如果其外延非空，那么这个概念是一个对象概念，标签为外延中的对象。

步骤2访问最小概念的所有父概念，若访问的概念只有最小概念作为其下近邻，那么这个概念是一个对象概念，标签为概念外延减去最小概念的概念外延。

步骤3访问步骤2中已经访问的所有概念的父概念，直到最大概念为止，若访问的概念只有一个子概念，那么这个概念是一个对象概念，标签为概念外延减去其子概念的概念外延。

对偶地，可以得到概念格中属性概念的识别算法。

4 对象（属性）的比较

定义10对于任意的g1∈G，g2∈G，如果f(g1)⊂f(g2)或者f(g2)⊂f(g1)成立，则称g1和g2是可比的，并记做g1＜g2或者g2＜g1；否则称g1和g2是不可比的，并记做g1||g2。

对偶地，对于任意的m1∈Μ，m2∈Μ，如果g(m1)⊂g(m2)或者g(m2)⊂g(m1)成立，则称m1和m2是可比的，并记做m1＜m2或者m2＜m1；否则称m1和m2是不可比的，并记做m1||m2。

定理2对于一个概念，如果概念（A，B）是一个属性概念，并且属性标签是m，那么g（m）=A，并且对于∀m′∈{B-m}有g(m)⊂g(m′)；对偶地，如果概念（A，B）是一个对象概念，并且对象标签是g，那么f（g）=B，并且对于∀g′∈{A-g}有f(g)⊂f(g′)。

证明（反证法）假设∃m′∈{B-m}有g(m′)⊂g(m)，那么g({m，m′})=g(m′)⊂g(m)=B，可知g(m)⊆g({m，m′})⊂A，产生矛盾。因此，假设不成立，定理成立。根据概念格的对偶原理，可知定理的后半部分成立。

性质1在概念格中，如果存在两个可比的对象（属性）概念，那么它们标签中的对象（属性）也是可比的。

定义11在一个对象（属性）集合中，若存在若干对象（属性）是可比的，则删除所有大于最小的对象（属性）的对象（属性），这个操作称为集合的纯化操作，记做purify。

例1一个形式背景如表1，对应的概念格如图1。

表1 形式背景K

在概念格L（K）中，对象概念有：（1）（123，127），对象标签为1；（2）（23，1278），对象标签为2；（3）（3，12378），对象标签为3；（4）（4，13789），对象标签为4；（5）（56，1246），对象标签为5；（6）（6，12346），对象标签为6。

属性概念有：（1）（123456，1），属性标签为1；（2）（12356，12），属性标签为2；（3）（346，13），属性标签为3；（4）（56，1246），属性标签为4、6；（5）（{}，Μ），属性标签为5；（6）（1234， 17），属性标签为7；（7）（234，178），属性标签为8；（8）（4，13789），属性标签为9。

图1 概念格L（K）

根据概念格的结构，对象排序为：（1＜2＜3）||4||（5＜6）。属性排序为：5＜（（4，6）＜2）||（9＜（8＜7||3））＜1。

对于上面的属性序列，一个纯化操作的例子为：purify（8＜7||3）={8，3}。

5 内涵缩减（外延缩减）的计算

内涵缩减的应用主要集中在关联规则提取[5]和概念的稳定性分析[6]这两个方面，下面来论述属性概念在计算内涵缩减中的应用。

定义12对于给定的概念C=（A，B），如果属性集合R满足g（R）=g（B）=A，且对于任意的R1⊂R有g(R1)⊃g(R)，则称R是C的一个内涵缩减。

内涵缩减的意义在于利用最少的属性识别概念，因此内涵缩减的定义包括两重内容：（1）缩减后的内涵仍然能识别这个对象；（2）缩减后的内涵包括的属性是最少的。

对偶地，可以定义外延缩减：对于给定的概念C=（A，B），如果属性集合S满足下述两个条件：（1）f(S)=f(A)=B；（2）对于任意的S1⊂S有f(S1)⊃f(S)；则称R是C的一个外延缩减。

利用内涵缩减，可以得到关联规则。如果概念C=（A，B）的内涵缩减R，如果满足R⊂B，那么每个概念C都对应一个蕴含集rules(C)={R→Intent(C)-R}。其物理意义是，如果R能表示概念C，那么就能由R得到概念C的其他属性。

定理3属性概念的内涵缩减为它的标签属性。

证明根据定理1，可知定理成立。

定理4对于一个非属性概念，它的一个近似内涵缩减为任意两个父概念内涵缩减的并。

上述定理求得的是一个近似内涵缩减，是因为Ri∪Rj中可能存在可比的属性，因此内涵缩减为Purify(Ri∪Rj)。

内涵缩减的递归计算公式：

（1）如果概念（A，B）是一个属性概念，则内涵缩减是这个概念的属性标签；

（2）如果概念（A，B）不是属性概念，并且它的父概念为(A1，B1)，(A2，B2)，…，(An，Bn)，这些概念的内涵缩减为R1，R2，…，Rn，那么内涵缩减为{Purify(Ri∪Rj)|i≠j，i，j∈1，2，…，n}。

根据上述公式，很容易得到计算全部概念内涵缩减的算法，这里不再赘述。

例2在概念格L（K）中（见图1），计算（23，1278）的内涵缩减。

（23，1278）的父概念有（123，127）和（234，178），（123，127）有两个父概念（12356，12）和（1234，17），（12356，12）是一个属性概念，其内涵缩减为标签2，（1234，17）也是一个属性概念，其内涵缩减为标签7，所以（123，127）的内涵缩减为purify({2}∪{7})={2，7}，（234，178）也是一个属性概念，其内涵缩减为标签8，因此（23，1278）的内涵缩减为purify({2，7}∪{8})={2，8}。

从上面的计算过程可以看到，如果要计算概念格中所有概念的内涵缩减，那么每计算一个概念的内涵缩减就可以通过计算它的任意两个父概念的内涵缩减的并来获得。若是采用文献[7-8]中的方法逐个计算每个概念的内涵缩减，首先要计算概念和所有父概念内涵的差集，然后计算内涵差集最小覆盖，最终转化为从合取范式到析取范式的转换[9]，并且已经证明合范式转换复杂度是指数级[10]。显然，集合并运算比首先计算差集然后实现范式转换简便得多。

在实验对比两种方法的性能时，随机生成了一个形式背景，对象数为300，属性数为30，对象和属性间存在关系的概率为0.2，生成形式背景的概念格后，随机抽取50、100、150、200、250个概念计算内涵缩减。实验结果如图2，L1是采用范式转换方法的运行时间，L2是本文的方法运行时间。

图2 算法运行时间对比

6 属性排序与关联规则提取

定义13给定关联规则r:P→Q，记supp(r)=|g(P∪Q)|/ |G|为该规则的支持度，cοnf(r)=|g(P∪Q)|/|g(P)|为该规则的置信度。

定理5若属性bi和bj是可比的，并且bi＜bj，那么一定存在置信度为1的关联规则bi→bj。

证明因为bi＜bj，所以有g(bi∪bj)=g(bi)，cοnf(bi→bj)= |g(bi∪bj)|/|g(bi)|=1。

定理6若属性bi和bj是不可比的，即bi||bj，那么关联规则bi→bj或者bj→bi的置信度一定存在小于1。

证明因为bi||bj，所以有|g(bi∪bj)|＜|g(bi)|和|g(bi∪bj)|＜|g(bj)|，根据置信度定义，易知定理成立。

根据定理5，可以直接根据属性的排序序列直接得到置信度为1的关联规则。例如，在概念格L（K）中，根据属性排序序列5＜（（（4，6）＜2）||（9＜（8＜7||3））＜1，可以得到9→3，2→1，8→1，8→7等关联规则。

用定理5获得的关联规则一定是最简的。根据内涵缩减计算得到的关联规则实际上蕴涵了这些最简规则。例如，在概念格L（K）中，（23，1278）的内涵缩减为{2，8}，因此可以得到关联规则28→17，28→17蕴涵了2→1，8→1，8→7。但是，根据序列5＜（（4，6）＜2）||（9＜（8＜7||3））＜1却无法得到28→17，而这个序列却不包含这样的信息，这样的信息只能在概念格中找到，也就是若要得到所有任意属性组合之间的关系，则需要建立概念格，而后计算内涵缩减得到关联规则。

7 结束语

本文深入研究了对象概念和属性概念，分析了对象概念和属性概念与不可约元的关系，提出了对象概念和属性概念的识别算法，进而得到了以属性概念为递归终止条件的内涵缩减计算方法，在最后研究了对象和属性的比较及其在规则提取中的应用。进一步需要研究的是对象概念和属性概念与奇异点的关系，以及对象概念和属性概念与概念稳定性的关系等内容。

[1]Ganter B，Wille R.Formal concept analysis：mathematical foundation[M].New York：Springer-Verlag，l999.

[2]Scaife M，Rogers Y.External cognition：how do graphical representations work[J].International Journal of Human Computer Studies，1996，45：185-213.

[3]姜峰，范玉顺.基于扩展概念格的Web关系挖掘[J].软件学报，2010，21（10）：2432-2444.

[4]丁卫平，顾春华.基于形式概念分析的不完备电子病历系统粗糙挖掘研究[J].计算机科学，2009，36（10）：230-233.

[5]Passquier N，Taouil R，Bastide Y，et al.Generating a condensed representation for association rules[J].Journal of Intelligent Information Systems，2005，24：29-60.

[6]Roth C，Obiedkov S，Kourie D G.Towards concise representation for taxonomies of epistemic communities[C]//Yahia S B，Nguifo E M.Proc CLA 4th International Conference on Concept Lattices and their Applications，2006，4923：240-255.

[7]智东杰，智慧来，刘宗田.概念格的内涵缩减研究[J].计算机工程与应用，2009，45（1）：42-44.

[8]谢志鹏，刘宗田.概念格节点的内涵缩减及其计算[J].计算机工程，2001，27（3）：9-11.

[9]智慧来，智东杰，刘宗田.从合取范式到析取范式的转换研究[J].计算机工程与应用，2012，48（2）：15-17.

[10]Skowron A，Rauszer C.The discernbility matrices and functions in information systems[M]//Intelligent Decision Support，Handbook of Applications and Advances of the Rough Sets Theory.The Netherlands：Kluwer，1992：331-362.

ZHI Huilai,ZHI Dongjie

School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454150,China

In order to further facilitate data representation and improve the efficiency of data mining,two kinds of special concepts,namely object concept and attribute concept are studied.This paper analyzes relationship between object concepts（or attribute concepts）and irreducible elements,and recognition algorithms of object concepts and attribute concepts are put forward.A recursive algorithm for intent reduction which has attribute concepts as termination condition is given.Attributes sequence as well as its application in association rule extraction is studied.

formal concept analysis;object concept;attribute concept;association rule

为了进一步提高数据表示和数据挖掘的效率，对两类特殊概念即对象概念和属性概念进行了研究。分析了对象概念和属性概念与不可约元的关系，提出了对象概念和属性概念的识别算法；提出了以属性概念为递归终止条件的计算内涵缩减递归算法；研究了属性排序以及属性序列在规则提取中的应用。

形式概念分析；对象概念；属性概念；关联规则

A

TP18

10.3778/j.issn.1002-8331.1112-0540

ZHI Huilai,ZHI Dongjie.Research on object concepts and attribute concepts in formal concept analysis.Computer Engineering and Applications,2013,49（18）：112-115.

国家自然科学基金（No.60975033）；上海大学创新基金（No.A.16-0108-08-002，No.SHUCX091010）；河南理工大学博士基金（No.B2011-102）。

智慧来（1981—），男，博士，讲师，研究领域：知识表示、知识管理、推理技术等；智东杰（1952—），男，高级实验师，研究领域：形式概念分析、符号计算等。

2011-12-28

2012-04-05

1002-8331（2013）18-0112-04

CNKI出版日期：2012-05-21 http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1139.016.html