概念格[1]作为形式概念分析核心数据结构被广泛应用的应用于软件工程、知识工程、数据挖掘和信息检索等许多领域。概念格的每个节点是一个形式概念, 由外延和内涵两部分组成。外延指形式概念所覆盖的实例, 内涵表示该概念所覆盖实例的共同特征[2], 其本质上描述了对象和特征之间的联系, 表明了概念之间的泛化与例化关系, 而这种关系可以通过Hasse图生动、简洁的描述出来。
概念格的构造算法主要分为两大类:批处理算法和渐进式算法。批处理算法的基本思想:一次生成所有的概念格结点, 再根据结点间的前驱—后继关系生成边, 完成概念格的构造。根据生成概念格的方式不同又分为三类, 即自顶向下算法, 自底向上算法和枚举算法。渐进式建格算法又分为基于属性和基于对象的两类, 其主要思想是:将当前要插入的对象或属性与格中所有概念进行交运算, 根据交运算的结果不同, 从而采取不同的行动。
本文重点研究了Chein[5]、Godin[3]、Bordat[4]三种典型的算法, 阐述了各种算法的思想, 给出了在理论上最坏情况下的时间复杂度, 并通过实验分析了当形式背景中的属性数固定、疏密度不同时随着对象数增加, 各种算法的时间复杂度如何变化。
1 算法思想描述
1.1 Chein算法
Chein算法是一个自底向上的算法。算法从第一层L1开始, 它包含了O中所有对象x所对应的配对 ({x}, f{x}) 的集合。它通过系统地合并Lk的两对来建立Lk+1层的新对。合并的过程就是对Lk层的每两个概念进行外延的并运算和内涵的交运算。将结果分别作为新生成概念的外延和内涵。若新生成的概念之前从未出现过, 则保留该概念, 并将生成它的下层结点作为它的子结点。若已经出现过, 则抛弃该概念。在理论上, 最坏情况下的复杂度为O (|G|3|M|)
1.2 Bordat算法
在该算法中, 格L的建造是从最小上界 (O, f (O) ) 开始, 接着生成该结点的所有子结点并连接到它的父结点。然后对每个子结点重复该过程。该算法的关键在于生成子节点的过程。该过程的基本思想是:设 (A, B) 是当前节点, M是属性集。找出属性子集P⊆M-B, 使得P在A上是最大扩展的, 则P∪B是当前节点的一个子节点的内涵。该算法在求P时采取对属性两两组合进行测试的方法。在理论上, 最坏情况下的复杂度为O (|G||M|2) 。
1.3 Godin算法
Godin算法是一种基于对象的渐进式构造算法, 渐进式构造概念格就是在给定原始背景K= (G, M, I) 所对应的原始概念格L以及新增对象g的情况下, 求解背景K*= (G∪{g}, M, I) 所对应的概念格L*[4]。在渐进式生成概念格的求解过程中, 要解决的问题主要有三个: (1) 所有新结点的生成: (2) 避免已有格结点的重复生成; (3) 边的更新。Godin算法在理论上, 最坏情况下的复杂度为O (|G|2|M|) 。
2 实验分析
为了测试上述三种算法在参数发生变化时的时间复杂度的变化趋势, 做了三组实验。实验环境是Pentium (R) D、3.0GHz CPU、512MB内存, Windows XP操作系统, 数据库管理系统为MS SQL Server 2000, 用C++实现了Bordat、Chein、Godin算法。在此实验中, 用h'表示疏密度, 即每个对象所具有的属性个数。
实验一:M=100, h'=4
随机生成10个背景, 每个背景属性数固定为100, 每个对象所具有的属性个数为4, 对象数由0逐步增加为900, 实验结果如图1所示。
实验二:M=100, h'=25
随机生成10个背景, 每个背景属性数固定为100, 每个对象所具有的属性数为25, 对象数由10逐步增加为100, 结果如图2所示。
实验三:M=100, h'=50
随机生成5个背景, 每个背景属性数固定为100, 每个对象所具有的属性数为50, 对象数由0逐步增加为40, 结果如图3所示。
综合分析上述三组实验的结果, 形式背景的属性个数固定, 当疏密度比较小时, 随着对象数的增加Bordat算法表现出了较好的性能, 而Godin算法时间复杂度上升最快, 这与Godin算法的本质有关 (逐步添加对象) 。当疏密度比较大时, 随着对象数的增加Chein算法表现出了较好的性能。实验结果与理论分析所得的时间复杂度不完全相符, 这是因为我们理论分析的是最坏情况下的时间复杂度, 而实验中随机获得的形式背景不一定都是最坏情况。
3 结语
本文在理论上分析了在最坏情况下三种算法的时间复杂度, 并通过实验分析了各种算法当参数变化时时间复杂度的变化趋势。并得出结论:形式背景的属性个数固定, 当疏密度比较小时, 随着对象数的增加Bordat算法表现出了较好的性能, 当疏密度比较大时, 随着对象数的增加Chein算法表现出了较好的性能。
摘要：概念格作为形式概念分析理论中的核心数据结构, 已经在很多领域得到了广泛的应用, 国内外的研究人员已经提出一系列的构造概念格的算法。本文给出了三种算法的构造思想及理论上最坏情况下的时间复杂度, 并通过实验分析了各种算法当参数变化时它们的时间复杂度的变化趋势。
关键词：概念格,形式背景,时间复杂度,形式概念分析
参考文献
[1] Ganter B, Wille R.Formal concept Analysis[M].Mathematical Foundation, Berlin:Springer Verlag, 1999.
[2] 金梁.概念格Chein构造算法的改进[D].开封:河南大学, 2008.
[3] 沈夏炯.概念格同构生成方法研究及IsoFCA系统实现[D].上海:上海大学, 2005.
[4] Bordat J P.Calcul pratique du treillis de Galois d'une correspondence.[J]Match.Sci.Hum.1986, 96:31～47.
[5] Nourine L, Raynau O.A Fast Algo-rithm for Building Lattices.Workshop on Computational Graph Theory and Combinatorics.Victoria, Canada, May, 1999.