概念格的属性渐减原理与算法研究

摘要：

渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖ L ‖·G ‖·‖M ‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.

关键词：形式概念分析、概念格、属性、渐减算法、构造

所属期刊栏目：50

分类号：TP18(自动化基础理论)

资助基金：国家"九七三"重点基础研究发展计划基金项目2007CB311101,2011CB302605;国家"八六三"高技术研究发展计划基金项目2010AA012504,2011AA010705;国家自然科学基金项目61070186,6110018,61173144

在线出版日期：2013-04-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：248-259