摘要
为了避免构建概念格时的繁琐过程,提高概念格构建的效率,提出了一种基于内涵亏值通过查找顶元素来快速渐进式生成概念格的新方法。首先,形式化地定义了顶元素、旧概念、产生概念、新概念、产生子概念、内涵亏值集合、剩留父概念、超集删除与正则队列;提出了概念格元素是否为顶元素的判定定理并给出了其证明;其次,在原概念格的正则队列中依次取概念元素,经超集删除后得到剩留父概念;最后,从剩留父概念查找其所在等价类的顶元素,逐步生成新概念格的正则队列。理论分析时间复杂度较基于属性的渐进式概念格生成(CLIF_A)算法与FastAddIntent算法有效降低,在实验例证对比中,概念数目大于150时,所用时间远少于对比算法。实验结果表明该算法方法简单,构建效率较对比算法明显提高。
Concerning the tedious process during the construction of concept lattice, to improve the efficiency of building concept lattices, a new incremental method of constructing concept lattice based on intent waned value by seeking top elements was proposed. Firstly, top element, original concept, produced concept, new concept, producer concept, the set of intent waned values, reminded parent concept, superset delete and regular queue were formally defined; the judging theorem and proof whether the concept elements were top elements were given. Secondly, the elements were extracted from the regular queue of the original lattice in due order and the reminded parent concepts were got after superset delete. Finally, the top elements were found from the equivalent classes of the reminded parent concepts and the regular queue of the new lattice was gradually generated. Time complexity was effectively reduced compared with the Attribute-based Concept Lattice Incremental Formation (CLIF-A) algorithm and the FastAddIntent algorithm by theory analysis. In comparison with simulated experiments, the time consumption of the proposed algorithm was far less than the comparative approaches in large size of population. The simulation results show that the proposed algorithm is simple, and can effectively improve the time performance, meanwhile provides better performance in construction efficiency.
出处
《计算机应用》
CSCD
北大核心
2017年第1期222-227,共6页
journal of Computer Applications
基金
国家自然科学基金资助项目(61273019)
辽宁科技大学青年基金资助项目(2014QN21)~~
关键词
概念格
内涵亏值
顶元素
超集删除
正则队列
concept lattice
intent waned value
top element
superset delete
regular queue