1、概念格构造算法分析论文导读：一个形式背景K=(G,M,I)由集合G、M以及它们之间的关系I组成，G的元素称为对象(Objects)，M的元素称为属性(Attributes)。2.批生成算法(BatchAlgorithm)为了批生成概念格，主要要完成两项任务：一是要生成所有的格节点(即形式概念的集合)。Titanic算法采用一种自顶向下的次序来逐层地生成所有概念节点，利用数据挖掘中计算频繁项集的技术来对概念节点的生成过程进行优化。关键词：形式背景，概念格，算法0.引言概念格结构模型是形式概念分析理论中的核心数据结构1，它本质上描述了对象和特征之间的联系，概念格模型是根据二元关系建立起来的概念层次
2、结构，反映的是对象和属性之间的联系以及概念之间的泛化和例化关系，在概念层次结构上容易建立数据之间的依赖或因果关系模型。并以其良好的数学性质已成功的应用于知识发现、数据挖掘等诸多领域。概念格已经在许多领域得到了广泛的应用，并且在某些方面表现出了其特有的优越性。建格的过程实际上是概念聚类的过程。因此，在概念格中，建格算法具有很重要的地位。国内外学者和研究人员对此进行了深入的研究，提出了一些有效的算法来生成概念格，这些算法主要分为两类：批处理算法（BatchAlgorithm）如：Chein算法2、Titanic算法3、Bordat算法4、Lindig算法5和Ganter算法6。、渐进式生成算法（
4、为对象(Objects)，M的元素称为属性(Attributes)。为了表示一个对象g和一个属性m在关系I中，可以写成gIm或(g,m)I，读成“对象g有属性m”。形式背景的对象集AP(G)，属性集BP(M)之间可以定义两个映射f和g如下：。称从形式背景中得到的每一个满足A=g(B)且B=f(A)的二元组(A,B)为一个形式概念(FormalConcept)，简称概念。其中A称为概念(A,B)的外延(Extent)，B称为概念(A,B)的内涵(Intent)。对于给定的形式背景K=(G,M,I)，若概念C1=(A1,B1)和C2=(A2,B2)，满足A1A2，或B2B1，则称(A1,B
5、1)为子概念(或亚概念)，(A2,B2)为父概念(或超概念)，记为：(A1,B1)(A2,B2)。若不存在C3=(A3,B3)，满足(A1,B1)(A3,B3)(A2,B2)，则称(A1,B1)为直接子概念，(A2,B2)为直接父概念。这种由形式背景中所有形式概念的超概念子概念的偏序关系(也称泛化例化关系)所构成的格称为概念格(ConceptLattice)，记为L(K)。2.批生成算法(BatchAlgorithm)为了批生成概念格，主要要完成两项任务：一是要生成所有的格节点(即形式概念的集合)；二是要建立这些格节点间直接前驱与直接后继关系。因此按照这两项任务完成次序的不同，我们可以采用
6、两种不同的途径来完成：一种是首先生成全部的概念集合，然后再找出这些概念之间的直接前驱与直接后继关系；另一种是每次生成少量的概念，并将这些概念链接到节点集合中。Chein算法是自底向上逐层构格，算法先从构造只含有一个属性的概念集合L1开始，然后由含有k个属性的概念集合Lk迭代产生含有k+1个属性的概念集合Lk+1。但Chein算法只产生相应的概念(格节点)的集合，并不产生概念之间的父概念子概念关系。Titanic算法采用一种自顶向下的次序来逐层地生成所有概念节点，利用数据挖掘中计算频繁项集的技术来对概念节点的生成过程进行优化。为了提高检索速度，Nourine算法中采用了字典树对概念进行组织索引
7、的方法。免费论文网。Nourine算法首先生成了所有的概念节点，接着通过算法计算出所有的父概念和子概念关系。在Bordat算法中主要有两个过程，一是对于每个节点生成它的所有子节点；二是对于每个生成的子节点判断它是否已经存在。它们都是比较耗时的。Lindig算法针对上述的两个过程，利用类似Ganter算法的方法来为概念格中的每个节点生成它的所有子节点；将所有已经生成的概念节点通过字典树组织，这样可以快速地判断某个节点是否已经生成。因此，Lindig算法是比Bordat算法更加高效的算法。对于形式背景K=(G,M,I)，其概念格的批生成算法的一般框架如下所示：(1)初始化格L(G,f(G)；(2
8、)队列F(G,f(G)；(3)对于队列F中的一个概念C，产生出它的每个子概念Cc；(4)如果某个子概念Cc以前没有产生过，则加入到L中；(5)增加概念C和其子概念Cc的链接关系；(6)反复(3)(5)，直至队列F为空；(7)输出概念格L。免费论文网。3.渐进式生成算法(IncrementalAlgorithm)从静态的形式背景中采用批生成算法来构造概念格是很有效的，但当形式背景发生变化时，构格的过程要重新做一次，也就是说批生成算法不适应于动态形式背景的处理要求。实际上，形式背景总是动态变化的，如交易数据库(形式背景)总是随着交易的发生而不断的增加。概念格的渐进式生成算法就是为了满
9、足形式背景的渐增更新而发展起来的。渐进式构造算法基本思想是将当前要插入的对象和格中所有的概念交，根据交的结果采取不同的行动。其中最典型的算法是Godin.R等在1995年提出的概念格的渐进式生成算法，通常称为Godin算法。下面将简单介绍Godin算法的基本思想，Godin的完整算法过程如下：(1)初始化格L为一个空格；(2)从G中取一个对象g；(3)对于概念格L中的每个概念C1=(A1,B1)，如果B1f(g)，则把g并到中如果同时满足：，和不存在(A1,B1)的某个父节点(A2,B2)满足，则要产生一个新节点；(4)把新产生的节点加入到L中，同时调整节点之间的链接关系；(5)
10、重复(2)到(5)，直至形式背景中的对象处理结束；(6)输出概念格L。免费论文网。概念格的渐进式生成算法在产生所有概念节点的同时，还产生了概念之间的父概念子概念连接关系，同时它非常适合于处理动态数据库，被认为是一种生命力很强的概念格生成算法。人们对Godin算法的改进也没有停止过。谢志鹏等提出了一种利用字典索引树的快速概念格渐进式构造算法，该算法利用一个辅助索引树来快速判断概念节点的类型，并根据概念节点的类型来决定概念格的渐进修改策略。4.分布概念格构造利用高性能并行计算机的计算与存储能力来构造和存储是有效地解决这一问题的根本途径。但就数据分布式存储与并行处理本身来说，如何合理有效地组织数据
13、lgorithmederecherchdessousmatricespremieresdunematrice,Bull.Math.R.S.13,1969.3NourineL,andRaynaudO.Afastalgorithmforbuildinglattices.InformationProcessingLetters,1999,71:pp:199-204.4Bordat.J.Calculpratiquedutreillisdegaloisdunecorrespondence,Mathematique,InformatiqueetScienceHumaines24(94),31.1986.5LindigC.Fastconceptanalysis.InStummeG(Eds.),WorkingwithConceptualStructuresContributionstoICCS2000,ShakerVerlag,Aachen,Germany.2000.6B.Ganter,FormalConceptAnalysis:algorithmicaspe