摘要
形式概念分析(formal concept analysis,FCA)已经被证明是数据分析、规则提取和聚类的一种非常有效的方法,但如何有效地构建形式化概念格是一个困难且至今热门的课题。提出了一种高效的增量式构建概念格的算法——FastAddExtent。基于已有的AddIntent算法构建概念格的基本流程,设计了修复概念间关系与寻找标准生成器的方法。提出的FastAddExtent算法通过增加四个字段有效地避免了概念之间不必要的比较,通过Hash查找快速定位概念,从而使构建概念格的效率随着概念数量的增加有了突破性的进展。实验结果表明相比AddIntent算法,FastAddExtent算法明显提高了算法的效率。
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.
作者
曾利程
张祖平
邹力耕
ZENG Licheng;ZHANG Zuping;ZOU Ligeng(School of Information Science and Engineering,Central South University,Changsha 410012,China)
出处
《计算机科学与探索》
CSCD
北大核心
2018年第11期1862-1870,共9页
Journal of Frontiers of Computer Science and Technology
基金
国家自然科学基金No.61379109
中南大学中央高校基本科研业务费专项资金No.2017zzts511~~
关键词
概念格
数据分析
形式概念分析
聚类算法
concept lattice
data analysis
formal concept analysis
clustering algorithm
