概念格的属性约简及建格算法的研究

论文摘要

概念格是根据二元关系建立的一种概念层次结构,它在本质上描述了对象与属性之间的联系,体现了概念内涵和外延的统一,是数据分析与规则提取的一种有效的工具。粗糙集理论是一种处理不精确、不确定和模糊数据的新型数学工具,它已能有效地从数据本身提供的信息中发现有效的、潜在的知识。而概念格与粗糙集之间的关系也是近年来许多学者关注的焦点,它们的有效结合使得一些算法得到了简化与改进。本文共分五部分内容,第一部分介绍了研究问题的背景、发展现状,本文的相关工作及组织结构。第二部分给出了概念格和粗糙集的基本理论以及它们之间的关系,为概念格的属性约简方法和建格算法的研究奠定了基础。第三部分对基于可辨识矩阵的概念格属性约简方法进行了分析,给出相应的算法,并提出了一种只依赖于形式背景本身的属性约简的方法及算法。此算法可以作为建格前的预处理算法。第四部分提出了基于粗糙集中等价关系的理论来构造概念格的算法,共有三个算法：基于等价类求概念节点的算法；求概念格中其它节点的算法；构造概念格的算法。在这种算法中由于等价类的引入节省了寻找概念节点的时间,提高了算法的效率。第五部分对本文的研究进行总结,并指出了概念格进一步的研究方向。本文对提出的算法进行了实验测试,并与其它相关算法进行了比较,多次实验表明本文提出的算法是可行,有效的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究问题的背景及现状
• 1.2 本文研究的主要工作
• 1.3 本文的组织结构
• 第2章 预备知识
• 2.1 概念格的基本理论
• 2.1.1 概念格的基本定义
• 2.1.2 概念格的基本性质
• 2.1.3 概念格的几种类型
• 2.2 粗糙集的基本概念
• 2.3 概念格与粗糙集的关系
• 2.4 小结
• 第3章 概念格的属性约简
• 3.1 概念格属性约简的基本概念
• 3.2 概念格属性约简的方法
• 3.2.1 基于可辨识矩阵的属性约简方法
• 3.2.2 基于形式背景的属性约简的方法
• 3.3 小结
• 第4章 概念格的构造算法
• 4.1 经典构造算法的简单描述
• 4.1.1 批处理算法
• 4.1.2 渐进式算法
• 4.1.3 领域知识的添加算法
• 4.2 基于等价类的概念格构造算法
• 4.2.1 基于等价类的概念格构造算法
• 4.2.2 应用实例
• 4.2.3 算法的空间复杂度分析
• 4.3 实验测试
• 4.4 小结
• 第5章 结论与展望
• 参考文献
• 致谢
• 作者攻读硕士学位期间主要成果