Abstract: Aiming at the problems during construction process of increment concept lattices such as low efficiency of nodes updating and generation element judgement, this paper presents an increment construction algorithm for concept lattice based on maximal concept which reduces the judgement process of generation element by tracking the largest concept with same connotations of concepts in concept lattice. The algorithm limits the search space while searching the father node of a new generated node, avoids judging unnecessary borders of generation element and improves the speed of concept lattice construction. Complexity analysis results demonstrate that this algorithm has better time performance than other kindred algorithms.

Key words: formal context, concept lattice, increment algorithm, object intension

摘要： 针对增量概念格构造过程中，节点更新和生成元判定效率较低、边更新阶段的复杂度较高等问题，提出基于最大概念的概念格增量构造算法，通过跟踪与概念格中的概念具有相同真实内涵的最大概念，简化生成元的判断过程。该算法缩小了寻找新生节点父节点时的搜索范围，避免对生成元非必要边的判断，提高构造概念格的速度。复杂度分析结果表明，该算法的时间性能优于其他同类算法。

关键词: 形式背景, 概念格, 增量算法, 对象内涵

CLC Number: 

• TP311.12