概念格.ppt

概念格的理论研究方向与现状 概念是人类进行知识表达的一种手段，知识是人类认识客观世界的结果，同时也是人们指导自己行为的准则，人们可以从不同的途径获取知识和发现知识。 概念格是知识的一种表达模型，依据知识体在内涵和外延上的依赖或者因果关系，建立概念层次模型。 在哲学中，概念被理解为由外延和内涵所组成的思想单元。基于概念的这一哲学理解，德国数学家Wille R.于1982年首先提出了形式概念分析用于概念的发现，排序和显示。形式概念分析，也称为概念格。形式概念分析理论是一种基于概念和概念层次的数学化表达。 形式概念分析的基础是形式背景(U,A,I)，一个由对象集U，属性集A，以及U与A间的二元关系I构成的三元组。在形式背景的基础上，获得形式概念(X,B)，其中X称为概念的外延，是属于这个概念的所有对象的集合；B称为内涵，是所有这些对象所具有的属性（特征）集。概念是外延与内涵的统一体。这种实现了对概念的哲学理解的形式化。 所有的概念同它们之间的泛化/例化关系构成一个概念格。概念格的每一个节点是一个形式概念。概念格结构模型是形式概念分析理论中的核心数据结构。它本质上描述了对象和特征之间的联系，表明了概念之间的泛化关系和例化关系，对应的Hasse图实现了对数据的可视化。因此，概念格被认为是进行数据分析的有力工具。 知识发现是从数据集中识别正确、新颖、有潜在应用价值以及最终可以为人们理解的模式的方法，数据库知识发现的过程就是将数据库中蕴含的知识形式化成有用概念的过程，是人工智能的核心问题。概念格作为一种具有极大潜力的有效的知识发现工具，因此备受关注。 概念格主要用于机器学习，模式识别，专家系统，计算机网络，数据分析，决策分析，数据挖掘，信息检索等领域。 研究概念格的价值在于解决知识发现领域中所涉及的关联规则、蕴含规则、分类规则的提取，和实现对信息的有机组织，减少冗余度，简化信息表等。 概念格理论的研究主要集中在一下几个方面： (1) 概念格的建造。 从数据集（在概念格中称为形式背景）中生成概念格的过程实质上是一种概念聚类过程。对于同一批数据，所生成的格是唯一的。 建格算法可以分为：批处理算法、渐进式算法（或称增量算法）、并行算法。 对于给定的形式背景(U,A,I) (其中对象集U，属性集A，以及U与A间的二元关系I)，存在唯一一个偏序集合与之相对应。由偏序集构成一种格结构，并且此偏序集满足自反性，反对称性和传递性。若u∈U,a∈A,uIa表示对象U具有a属性。格中的每一个节点称之为概念，记作C(X,Y)，X∈U是概念C(X,Y)的外延，Y∈A是概念中对象的共有属性（内涵）。 节点概念与节点概念之间存在着偏序关系，若有概念C1=(X1,Y1)，C2=(X2,Y2)，并且X1＞X2＜=＞Y1Y2,称C1为C2的父节点。概念格的实行背景通常是由如下表所示的二维数组来表示，横向维表示属性，纵向维表示对象，第i行j列的数值为一表示存在改属性，为0表示不存在该属性。 批处理算法根据去构造格的不同方式，可以分为三类：从顶向下算法，自底向上算法，枚举算法。 从顶向下算法是先构造全概念，也就是最上层的节点，然后依次生成该节点的所有可能的子节点，并且对每个子节点做上述操作，最后将所有存在父子关系的节点相连，算法的关键在于如何生成子节点，虽然简洁直观且较易实现，但存在生成许多冗余节点的问题。 自底而上算法关键在于如何完成下一个层次的对个序对到上一个层次的合并，并且要对生成的节点进行重复性判断。如果在上层中出现过，要予以标记并在完成此层操作之前删除该节点。问题是：合并过程中会产生大量的重复性节点，效率不高，不能生成相应的Hasse图，不具备直观性。 枚举算法则按照一定的顺序枚举出格内的节点，在生成Hasse图的同时，表达出各个节点之间的关系。 增量算法或者说是渐进算法的主要思想是将待插入的对象与格内已存在的概念节点进行交运算，根据结果的不同使用相应的处理办法。 对于新插入的实例，对格内的节点会产生以下三种不同的影响：（1）：更新节点，该类节点内涵包含在新的对象内涵之中，仅仅需要将新对象的外延加入到外延中即可；（2）：不变节点，这种借点的内涵与新对象的内涵关系，没有任何交集，不做任何修改；（3）：新增节点，新节点对象的内涵与格内节点内涵的交集首次出现，即原格内所没有的新概念需要添加的节点。 渐进式生成概念格的求解过程中，要着重解决三类问题：如何生成新节点、如何避免重复节点的产生和如何更新连接节点的边。对于上述三类问题，谢志鹏等较为详尽的论述了如何快速构造概念格。 下面是一个渐进式算法建造概念格的简要过程 基本思想是先求属性(对象)基本概念，再由基本概念生成其它概念，由于在生成新的概念进行集合的交运算