Abstract:

Formal concept analysis (FCA) has been proven to be a very effective method for data analysis, rule extraction and clustering, but how to build a formal concept lattice efficiently is a difficult and hot topic. This paper proposes an efficient incremental concept lattices construction algorithm. The algorithm is called FastAddExtent, a modification of AddIntent in which two fundamental procedures including covering relation fixing and canonical generator search are improved. The proposed algorithm can locate quickly the concept by the way of Hash and adding four fields to every concept. Thus, it makes enormous breakthrough with the increase in the number of formal concept when building concept lattices. Experimental results show that the FastAddExtent algorithm can improve the efficiency obviously compared with the primitive AddIntent algorithm.

Key words: concept lattice, data analysis, formal concept analysis, clustering algorithm

摘要：

形式概念分析（formal concept analysis，FCA）已经被证明是数据分析、规则提取和聚类的一种非常有效的方法，但如何有效地构建形式化概念格是一个困难且至今热门的课题。提出了一种高效的增量式构建概念格的算法——FastAddExtent。基于已有的AddIntent算法构建概念格的基本流程，设计了修复概念间关系与寻找标准生成器的方法。提出的FastAddExtent算法通过增加四个字段有效地避免了概念之间不必要的比较，通过Hash查找快速定位概念，从而使构建概念格的效率随着概念数量的增加有了突破性的进展。实验结果表明相比AddIntent算法，FastAddExtent算法明显提高了算法的效率。

关键词: 概念格, 数据分析, 形式概念分析, 聚类算法