论文导读：一个形式背景K=(G,M,I)由集合G、M以及它们之间的关系I组成，G的元素称为对象(Objects)，M的元素称为属性(Attributes)。2.批生成算法(BatchAlgorithm)为了批生成概念格，主要要完成两项任务：一是要生成所有的格节点(即形式概念的集合)。Titanic算法采用一种自顶向下的次序来逐层地生成所有概念节点，利用数据挖掘中计算频繁项集的技术来对概念节点的生成过程进行优化。
关键词：形式背景，概念格，算法
0.引言概念格结构模型是形式概念分析理论中的核心数据结构[1]，它本质上描述了对象和特征之间的联系，概念格模型是根据二元关系建立起来的概念层次结构，反映的是对象和属性之间的联系以及概念之间的泛化和例化关系，在概念层次结构上容易建立数据之间的依赖或因果关系模型。并以其良好的数学性质已成功的应用于知识发现、数据挖掘等诸多领域。
概念格已经在许多领域得到了广泛的应用，并且在某些方面表现出了其特有的优越性。建格的过程实际上是概念聚类的过程。因此，在概念格中，建格算法具有很重要的地位。国内外学者和研究人员对此进行了深入的研究，提出了一些有效的算法来生成概念格，这些算法主要分为两类：批处理算法（Batch Algorithm）如：Chein算法[2]、Titanic算法[3]、Bordat算法[4]、Lindig算法[5]和Ganter算法[6]。、渐进式生成算法（Incremental Algorithm）如Godin算法[7]：。本文就对概念格构格的一些经典算法进行分析和比较，并对基于分布式构建概念格的算法进行探讨。
1.相关背景知识形式概念分析Formal Concept Analysis (FCA)[8]是由德国的Rudolf Wille教授于1982年提出的一种建立在数论（尤其是完备格）基础上的技术。它是一种可被用于数据分析、知识表示和信息管理的方法，目前己在信息科学中取得了很多成功的应用。目前，形式概念分析的应用范围己扩大到知识发现、软件工程、信息检索、语义学和经济学等领域。
一个形式背景K=(G,M,I)由集合G、M以及它们之间的关系I组成，G的元素称为对象(Objects)，M的元素称为属性(Attributes)。为了表示一个对象g和一个属性m在关系I中，可以写成gIm或(g,m) ∈I，读成“对象g有属性m”。
形式背景的对象集A P(G)，属性集BP(M)之间可以定义两个映射f 和g如下：
 。
称从形式背景中得到的每一个满足A=g(B)且B=f(A)的二元组(A,B)为一个形式概念(Formal Concept)，简称概念。其中A称为概念(A,B)的外延(Extent)，B称为概念(A,B)的内涵(Intent)。
对于给定的形式背景K= (G,M,I)，若概念C1=(A1,B1)和C2=(A2,B2)，满足A1 A2，或B2B1，则称(A1,B1)为子概念(或亚概念)，(A2,B2)为父概念(或超概念)，记为：(A1,B1)≤(A2,B2)。若不存在C3=(A3,B3)，满足(A1,B1)<(A3,B3)<(A2,B2)，则称(A1,B1)为直接子概念，(A2,B2)为直接父概念。这种由形式背景中所有形式概念的超概念－子概念的偏序关系(也称泛化－例化关系)所构成的格称为概念格(Concept Lattice)，记为L(K)。
2.批生成算法(Batch Algorithm)为了批生成概念格，主要要完成两项任务：一是要生成所有的格节点(即形式概念的集合)；二是要建立这些格节点间直接前驱与直接后继关系。因此按照这两项任务完成次序的不同，我们可以采用两种不同的途径来完成：一种是首先生成全部的概念集合，然后再找出这些概念之间的直接前驱与直接后继关系；另一种是每次生成少量的概念，并将这些概念链接到节点集合中。
Chein算法是自底向上逐层构格，算法先从构造只含有一个属性的概念集合L1开始，然后由含有k个属性的概念集合Lk迭代产生含有k+1个属性的概念集合Lk+1。但Chein 算法只产生相应的概念(格节点)的集合，并不产生概念之间的父概念－子概念关系。
Titanic算法采用一种自顶向下的次序来逐层地生成所有概念节点，利用数据挖掘中计算频繁项集的技术来对概念节点的生成过程进行优化。为了提高检索速度，Nourine算法中采用了字典树对概念进行组织索引的方法。免费论文网。Nourine算法首先生成了所有的概念节点，接着通过算法计算出所有的父概念和子概念关系。
在Bordat算法中主要有两个过程，一是对于每个节点生成它的所有子节点；二是对于每个生成的子节点判断它是否已经存在。它们都是比较耗时的。Lindig算法针对上述的两个过程，利用类似Ganter算法的方法来为概念格中的每个节点生成它的所有子节点；将所有已经生成的概念节点通过字典树组织，这样可以快速地判断某个节点是否已经生成。因此，Lindig算法是比Bordat算法更加高效的算法。
对于形式背景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。免费论文网。
3.渐进式生成算法(Incremental Algorithm)从静态的形式背景中采用批生成算法来构造概念格是很有效的，但当形式背景发生变化时，构格的过程要重新做一次，也就是说批生成算法不适应于动态形式背景的处理要求。实际上，形式背景总是动态变化的，如交易数据库(形式背景)总是随着交易的发生而不断的增加。概念格的渐进式生成算法就是为了满足形式背景的渐增更新而发展起来的。
渐进式构造算法基本思想是将当前要插入的对象和格中所有的概念交，根据交的结果采取不同的行动。其中最典型的算法是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) 重复(2)到(5)，直至形式背景中的对象处理结束；
(6) 输出概念格L。免费论文网。
概念格的渐进式生成算法在产生所有概念节点的同时，还产生了概念之间的父概念－子概念连接关系，同时它非常适合于处理动态数据库，被认为是一种生命力很强的概念格生成算法。
人们对Godin算法的改进也没有停止过。谢志鹏等提出了一种利用字典索引树的快速概念格渐进式构造算法，该算法利用一个辅助索引树来快速判断概念节点的类型，并根据概念节点的类型来决定概念格的渐进修改策略。
4.分布概念格构造利用高性能并行计算机的计算与存储能力来构造和存储是有效地解决这一问题的根本途径。但就数据分布式存储与并行处理本身来说，如何合理有效地组织数据的分布式存储与并行处理无论在理论上还是在技术上都有许多问题需要研究。由于概念格有良好的数学性质和适合批处理等特点，我们认为分布式概念格[8]是解决此问题非常理想的工具。
而概念格的分布处理思想就是通过形式背景的拆分，形成分布存储的多个子背景，然后构造相应的子概念格，再由子概念格的合并得到所需的概念格。这种把构造概念格的任务分成多个子任务，每个子任务构造部分概念格，再由部分概念格合并形成形式背景所对应的概念格的方案称为概念格分布处理模型或分布式概念格模型。
5.结论尽管概念格已在知识发现、软件工程、信息检索等诸多领域取得广泛的使用，但是时间复杂性和空间复杂性问题一直是困扰其进一步应用的一大难题。利用高性能并行计算机的计算与存储能力来构造和存储是有效地解决这一问题的根本途径。
概念格的分布处理能够降低构造复杂度，减少其构造的时间，但是最终的目的是提取有用的关联规则。如果能够分布提取出关联规则，进而直接得到全局的关联规则，将为实际应用提供极大的方便，应考虑直接的关联规则分布处理将概念格的分布并行处理应用到新的领域，如网络数据挖掘，为新兴研究领域开辟思路。
参考文献
[1]R.Wille,Concept lattices andconceptual knowledge systems.Computers and Math. Applications,Vol.23,1992.pp:5-9.
[2]Chein.M.Algorithme de recherchédes sous matrices premieres d’une matrice, Bull.Math.R.S. 13,1969.
[3]Nourine L,and Raynaud O.Afast algorithm for building lattices. Information Processing Letters,1999,71: pp:199-204.
[4]Bordat.J.Calcul pratique du treillisde galois d’une correspondence, Mathematique, Informatique et Science Humaines24(94),31.1986.
[5]Lindig C.Fast conceptanalysis.In Stumme G (Eds.), Working with Conceptual Structures Contributionsto ICCS 2000, Shaker Verlag, Aachen, Germany.2000.
[6]B.Ganter,Formal ConceptAnalysis:algorithmic aspects.TU Dersden.2002.
[7]R.Godin, H.Mil, G.Mineau, R.Missaou,A.Ar, T.Chau, Design of class hierarchies based on conceptGalois lattices, TAINF 4(2), 1998, pp:117-134.
[8]程伟,李云,陈崚等, 基于消息传递的概念格并行构造, 计算机应用与软件,2006, Vol123,No. 8.
|
