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

• 作者: 张宏莉 张磊 殷丽华 韩道军
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 形式概念分析 概念格 属性 渐减算法 构造
• 年，卷（期）: 2013,（2）
• 所属期刊栏目: 人工智能与模式识别
• 页码范围: 248-259
• 页数: 12页
• 分类号: TP18
• 字数: 11379字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张宏莉	哈尔滨工业大学计算机科学与技术学院	185	2778	29.0	46.0
2	张磊	哈尔滨工业大学计算机科学与技术学院	159	1265	17.0	29.0
6	殷丽华	中国科学院信息工程研究所	17	284	7.0	16.0
7	韩道军	河南大学数据与知识工程研究所	42	417	10.0	19.0