文献类型：期刊文章

作　　者：张磊[1,2] 张宏莉[1] 殷丽华[3] 韩道军[2]

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]河南大学数据与知识工程研究所,河南开封475004 [3]中国科学院信息工程研究所,北京100093

出　　处：《计算机研究与发展》

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

年　　份：2013

卷　　号：50

期　　号：2

起止页码：248-259

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSA-PROQEUST、CSCD、CSCD2013_2014、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

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

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

分 类 号：TP18]