概念格的属性渐减原理与算法研究

Theory and Algorithms of Attribute Decrement for Concept Lattice

渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖L‖·‖G‖·‖M‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.

Incremental algorithms for the construction of concept lattices are of key importance. But most of them focus on the case of the addition of objects or attributes in formal context. When the attributes in formal context are deleted, reconstructing concept lattice by these algorithms is needed. It is very time consuming. The theory and algorithms of incrementally obtaining new concept lattice by updating the old one after attributes being deleted are investigated in this paper. At first, the mapping relation between concepts of the old and new concept-lattice is explained and the changes of edges from the old concept lattice to the new one are analyzed. Based on this, two decremental algorithms called top-down and bottom-up algorithms are proposed, by which the original concept lattice can be directly modified to obtain the new one, and reconstructing the whole structure from scratch is avoided. Relying on the structure of concept lattice, the algorithms only explore limited parts of the lattice for modifying. Thus, its time complexity is reduced to O（｜L｜-｜G｜-｜M｜） Experimental results show that the algorithms presented can save considerable time compared with the traditional algorithms.