基于权值最大圈的概念格构造算法

摘要

概念格作为一种有效的知识发现与数据处理的工具，在许多领域得到了广泛应用。寻找形式背景下的所有概念是概念格理论研究的一个基本问题。对于一个给定的形式背景，在属性拓扑图的基础上，结合图论的思想，给出了一种概念格的构造算法。算法过程如下：首先，构造弱化的属性拓扑图；其次，通过寻找弱化的属性拓扑图中的每个权值最大圈方法来生成概念，形式背景的所有概念被生成；最后，构造出概念格。通过分析说明此算法复杂度比以往的一些算法复杂度低。此外，用一个实例验证了这一算法的有效性与正确性。为知识获取提供了有益的思路与方法。%As an effective tool for knowledge discovery and data processing, the concept lattice has been widely ap⁃plied in many fields. Searching all concepts in a formal context is a basic problem for research into concept lattice theory. On the basis of attribute topology and combined with the idea of graph theory, an algorithm to construct a concept lattice in a fixed formal context is given. The process is as follows: firstly, a weakened attribute topology was built up;then, by applying the method of searching the maximum cycle with a weight in the above weakened attribute topology, all of the formal context concepts were obtained;finally the concept lattice was established. Sub⁃sequent analysis illustrated that the algorithm can reduce complexity compared with some existing algorithms. In ad⁃dition, using an example, the accuracy and validity of the algorithm was verified. The result presents a useful idea and method for knowledge acquisition.