摘要
渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖L‖·‖G‖·‖M‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.
学科与关键词
关键词
形式概念分析概念格属性渐减算法构造 formal concept analysis (FCA)concept latticeattributedecremental algorithmconstruction
- 变精度对象概念格的构造及其性质宋笑雪; 张文修; 李红计算机科学, 2010, (12): 197.
- 粗糙概念格分层建格算法及应用刘保相; 陈焕焕; 柳洁冰计算机科学, 2013, (04): 214-216.
- A Quick Attribute Reduction Algorithm with Complexity of max(O(|C||U|),O(|C|2|U/C|))XU Zhang Yan; LIU Zuo Peng; YANG Bing Ru; SONG Wei2006.
