离散数学ch7[e1]概念格.pptVIP

离 散 数 学 第二部分 集合论 关系论 概念格 主要内容 形式概念分析的基本概念和特点 概念格的基本概念和特点 建格基本算法简介（流程和策略层面） 概念格和模糊聚类之间的关系（简介） 形式概念分析的基本概念和特点 形式概念分析简介 R. Wille教授于1982年首先提出了形式概念分析(Formal Concept Analysis)。 FCA以序论(Order Theory)尤其是以完全格理论(the Theory of Complete Lattice)为基础 概念被理解为由外延和内涵两个部分所组成的思想单元。 FCA中的一种重要关系：超概念和子概念 形式概念间通过泛化/例化关系相互关联构成了一种层次结构，就是概念格。 概念格通过Hasse图生动和简洁地体现了这些概念之间的泛化和特化关系。 在机器学习、信息检索、数字图书馆、软件工程和知识发现等方面得到了广泛应用。 形式背景基本概念 定义1: 形式背景定义为一个三元组 K = (G, M, I)，其中，G 是对象集合(Objects)，M是属性集合(Attributes)，I 　G × M 是 G 与 M 之间的一个二元关系。若(g, m) ∈ I，读作“对象 g 具有属性 m”。 概念格的基本概念和特点 定义2： 对对象集合的每个子集 A G，定义导出算子φ(A)求出集合 A 中所有对象的共有属性: 对称地，对属性集合的每个子集 B M，定义导出算子ψ (B)求出具有集合 B 中所有属性的对象的集合： 通常，为书写方便，这两个导出算子小加区分地写为A’和B’ 。 定义3： 形式背景 K = (G, M, I)上的一个形式概念(Formal Concept) （简称概念Concept）定义为一个二元组(A, B)，满足：A G, B M, A’ = B, B’ = A 其中，A 称为概念(A, B)的外延，B 称为概念(A, B)的内涵。 偏序集合 定义偏序集合 全部概念构成一个集合 定义集合上的偏序关系 (L,≤)构成一个偏序集合 定义4： 对某形式背景的任何两个形式概念(A1, B1)和(A2, B2)， 定义(A1, B1)和(A2, B2)的最大公共子概念： (A1, B1) ∧ (A2, B2): = (A1 ∩ A2, (B1 ∪ B2)’’) 定义(A1, B1)和(A2, B2)的最小公共超概念： (A1, B1) ∨ (A2, B2): = ((A1 ∪ A2)’’, B1 ∩ B2) 通常，将“最小公共超概念”称为上确界，将“最大公共子概念”称为下确界。 每个概念集合都有一个上确界和一个下确界。因此，概念格是一个完备格。 Hasse图 Hasse图既是通过描述概念之间的泛化/例化关系，形象表示出概念格，是概念格的一种可视化。 一个形式背景的例子 建格基本算法简介 生成概念格的算法可以被分两类: 批处理算法(Batch Algorithm) 渐进式生成算法(Incremental Algorithm ) 批处理算法(Batch Algorithm) 批处理概念格生成算法大多都是先生成出形式背景所对应的所有概念，然后再决定概念之间的子概念——超概念连接关系。 目前主要的批处理算法有:Chein算法[Che69], Ganter算法[Gan84] ,Alaoui算法[A1a92]. Titanic算法[Stu00] , Nourine算法[Nou99]以及Bordat算法[Bor86]和Lindig算法[Lin00]等。 一般概念格的批生成算法: 对于形式背景K= (G, M, I): (1)初始化格L={(G),f(G))}; (2)队列F={(G ,f(G))} ; (3)对于队列F中的一个概念C，产生出它的每个 子概念Cc; (4)如果某个子概念Cc以前没有产生过，则加入到L中; (5)增加概念C和其子概念Cc的链接关系; (6)反复(3)~(5)，直至队列F为空; (7)输出概念格L。 渐进式生成算法(Incremental Algorithm ) 概念格的渐进式生成算法，从空格开始，通过不断的渐增形式背景中的对象来实现对概念格的渐进式构造。 目前主要的渐进式算法有：Godin算法，Capinato算法 一般概念格的渐进式生成算法: 对于形式背景K= (G, M, I): (1)初始化格L为一个空格; (2)从G中取一个对象g: (3)对于格L中的每个概念C1=(A1, B1)，如果B1 f(g)，则把g并到A1中; (4)如果同时满足:B1∩f(g)≠?; B1∩f(g)≠ B1和不存在 (A1, B1)的某个父节