形式概念分析

形式概念分析

刘宗田

上海大学计算机学院,200072

ztliu@第1节基本理论人类在认知过程中，把所感觉到的具有共同特点的事物抽取出来，加以概括，称为概念。在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概念的这一哲学思想，德国的R.Wille教授于1982年首先提出了形式概念分析理论。第1节基本理论定义1.1（形式背景）一个形式背景K=(G,M,I)由集合G、M以及它们之间的关系组成I，G的元素称为对象(Objects)，M的元素称为属性(Attributes)。为了表示一个对象o和一个属性m在关系I中，可以写成oIm或(o,m)∈I，读成“对象o有属性m”。第1节基本理论第1节基本理论定义1.2（概念）对于形式背景K，在G的幂集和M的幂集之间可以定义两个映射f和g如下：

O

G:f(O)={d|

x

O:(xId)}

D

M:g(D)={x|

d

D:(xId)}来自P(G)

P(M)的二元组(O,D)如果满足两个条件：O=g(D)及D=f(O)，则它被称为是形式背景K的一个形式概念，简称概念，,记为C=(O,D)，其中D和O分别被称为概念C的内涵和外延．K的所有形式概念的集合被标记为CS(K)．第1节基本理论定义1.3（概念格）对于概念(O1,D1)和(O2,D2)．如果D2

D1，则形式概念(O1,D1)是形式概念(O2,D2)的亚概念，记为(O1,D1)

(O2,D2)．通过这个关系，我们得到一个有序集CS(K)=(CS(K),

)，这是一个完全格，被称为形式背景K的概念格,记为L(K)．第1节基本理论第2节概念格的生成与运算

概念格的构造问题是形式概念分析应用的前提。由于概念格的时空复杂度随着形式背景的增大而可能指数性的增大，有关概念格的生成问题一直是形式概念分析应用研究的一个重点。国内外的学者和研究人员对此进行了深入的研究，提出了一些有效的算法来生成概念格，这些算法一般可分为两类：批生成算法(BatchAlgorithm)和渐进式生成算法(IncrementalAlgorithm)。。第2节概念格的生成与运算2.1批生成方法现有的批处理概念格生成算法大多都是先生成形式背景所对应的所有概念，然后再决定概念之间的亚概念－超概念连接关系。有的算法只生成所有的概念，有的算法用来产生其Hasse图，也有的算法既生成所有的概念，又同时形成其Hasse图。第2节概念格的生成与运算算法2.1概念格的批生成算法：输入：形式背景输出：概念格L步骤1、初始化格；步骤2、初始化队列；步骤3、取出队列F中的一个概念C，产生出它的每个子概念Cc；步骤4、如果某个子概念Cc以前没有产生过，则加入到L中，加入队列F；第2节概念格的生成与运算步骤5、增加概念C和其子概念Cc的链接关系；步骤6、反复步骤3~步骤5，直至队列F为空；步骤7、输出概念格L。第2节概念格的生成与运算2.2渐进式生成方法GodinR.等在1995年提出的概念格生成算法是最经典的一个渐进式生成算法，通常称为Godin算法。该算法从空概念格开始，通过将形式背景中的对象逐个插入概念格来实现对概念格的渐进式构造。第2节概念格的生成与运算对于每次新增一个对象，都需和已生成概念格中的概念进行比较，这时已有的概念节点和新增的对象之间可以存在三种关系：无关概念(OldConcept)、更新概念(ModifiedConcept)和新增概念的产生子概念(GeneratorConcept)。渐进式构造主要是对更新概念和新增概念进行不同处理后，再调整概念之间的相互关系。第2节概念格的生成与运算算法11.2概念格的渐进式生成算法：输入：形式背景输出：概念格L步骤1、初始化格L为{({},M)}；步骤2、从G中取一个对象g；步骤3、对于格L中的每个概念，如果，则把g并到A1

中；第2节概念格的生成与运算步骤4、如果同时满足：；和不存在(A1,B1)的某个父节点满足，则要产生一个新节点；步骤5、对新产生的节点加入到L中，同时调整节点之间的链接关系；步骤6、反复步骤2到步骤5，直至形式背景中的对象处理结束；步骤7、输出概念格L。第2节概念格的生成与运算2.3概念格并运算定义2.1

如果形式背景K1=(U1,A1,I1)和K2=(U2,A2,I2)满足U1

U,U2

U,A1

A,A2

A,则称K1和K2是同域形式背景,L(K1)和L(K2)是同域概念格.，如果K1和K2满足U1∩U2=ф,则称K1和K2、L(K1)和L(K2)分别是外延独立的,简称独立的。第2节概念格的生成与运算定义2.2

如果..K1=(U1,A1,I1)和K2=(U2,A2,I2)是同域且独立的,则K1+K2=(U1∪U2,,A1∪A2,,I1∪,I2)第2节概念格的生成与运算定义2.3

对于C1=(O1,D1)和C2=(O2,D2)，如果D1=D2，则称C1内涵等于C2，简称C1等于C2第2节概念格的生成与运算定义2.4对于C1=(O1,D1)和C2=(O2,D2)，如果D1

D2，则称C1内涵小于C2，简称C1大于C2，或称C2小于C1

第2节概念格的生成与运算定义2.5对于C1=(O1,D1),C2=(O2,D2)和C3=(O3,D3)，定义C1+C2等于C3,,如果O3=O1∪O2,,D3=D1∩D2.

第2节概念格的生成与运算定义2.6

如果L(K1)和L(K2)是两个同域且独立的概念格，则定义L(K1)∪L(K2)是概念格L满足:1对于L(K1)中的任意概念C1=(O1,D1)和L(K2)中的任意概念C2=(O2,D2)，令D1∩D2=D3，如果在L(K1)中大于C1的任意概念C’1=(O’1,D’1)不存D3

D’1并且在L(K2)中大于C2的任意概念C’2=(O’2,D’2)不存D3

D’2，则C1+C2

L;2对于L(K1)中的任意概念C1,如果在L(K2)中不存在等于或小于C1的概念,则C1

L;3对于L(k2)中的任意概念C2,如果在L(K1)中不存在等于或小于C2的概念,则C2

L;4上述3种情况之外的概念不属于L。

第2节概念格的生成与运算K1第2节概念格的生成与运算K2。

第2节概念格的生成与运算定理2.1

如果L(K1)和L(K2)是同域且独立的概念格，则L(K1)∪L(K2)=L(K1+K2)。证明：略

第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算这里U1={123456}和U2={(1)(2)}

第2节概念格的生成与运算算法2.1

两个同域一致概念格的纵向合并算法输入：两个概念格L(K1)和L(K2)

输出：L(K1)∪L(K2)

BEGIN

FORL(K2)中每个概念按内涵的势的升序

DO

采用概念插入算法插入到L(K1)

ENDFOR

更新的L(K1)就是L(K1)∪L(K2)

END

第2节概念格的生成与运算2.5概念格交运算

第2节概念格的生成与运算

第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算第2节概念格的生成与运算2.6概念格的运算定律第2节概念格的生成与运算第3节概念格上的关联规则提取概念的内涵与事务数据库中的项目集非常类似，而且有更严格的限制，因此可以在概念格上提取关联规则，而且比直接在事务数据库上提取有更多的优势。第3节概念格上的关联规则提取1基于先辈晚辈节点对的关联规则提取

第3节概念格上的关联规则提取在概念格上提取规则，我们可以只关心那些外延对象数大于等于支持度阈值的节点，并且只关心晚辈外延对象个数与先辈外延对象个数的比值大于等于可信度阈值的节点对。第3节概念格上的关联规则提取当支持度阈值

和可信度阈值

确定之后，如果它们对于任何节点都是统一的，则有下面定理。第3节概念格上的关联规则提取第3节概念格上的关联规则提取第3节概念格上的关联规则提取例1.3

对于下图中的形式背景和概念格，规定支持度阈值

=0.4和可信度阈值

=0.66，则符合阈值条件的节点序列#2#4#8、#5#8和#6#8,只考虑每个序列两端的节点对，即考虑#2#8、#5#8和#6#8，得规则第3节概念格上的关联规则提取第3节概念格上的关联规则提取2基于内涵缩减的蕴含规则提取定义1.16（内涵缩减）对于给定的概念C=(A,B)，如果属性集合R满足下述两个条件则它R被称为是C的一个内涵缩减。如果。则称是真内涵缩减。第3节概念格上的关联规则提取如果概念C有真内涵缩减R，则它对应的蕴含规则集为第3节概念格上的关联规则提取例4在例3中形式背景所对应的概念格中，对于每个概念，我们将以此计算出其蕴含集：概念#2的内涵为{be)，它具有2个真内涵缩减{b}和{e}，因此。概念#3的内涵为，其内涵缩减也是，这并非真内涵缩减，因此无规则需要生成。概念#4的内涵为{bce}，它具有2个真内涵缩减{bc}和{ce}，因此。第4节模糊概念格在这方面，国外已有了一些研究成果。例如Wolff(1998)提出了一种基于模糊信息的表示法，将传统的形式背景中的属性用模糊语言变量值表示，依据标度分类形式背景的对象，构造基于标度的格。Burusco和Fuentes(1994)讨论了L-模糊概念集合的格结构，并给出了一个计算这种格的方法。第4节模糊概念格1一种模糊概念格模型第4节模糊概念格第4节模糊概念格第4节模糊概念格第4节模糊概念格第4节模糊概念格第4节模糊概念格第4节模糊概念格2模糊概念格渐进式生成为了能够用渐进式方法计算模糊参数σ和λ，在格的构造算法中，分别引进中间参数kd和hd。第4节模糊概念格第4节模糊概念格算法1.5模糊概念格的渐进式生成算法：输入：模糊形式背景输出：模糊概念格L步骤1、初始化格L为{({},M)}，初始节点中kd=0,hd=0；步骤2、从G中取一个对象g；步骤3、对于格L的每个概念，如果，则把g并到A1

中；对Ｂ1中的每个d第4节模糊概念格步骤4、如果Ｃ1同时满足：；和不存在(A1,B1)的