概念格属性约简算法研究

论文摘要

概念格理论，亦称形式概念分析，是德国数学家R.Wille于1982年提出的一种用于概念发现、排序和显示的数据分析方法。概念格理论作为有效的、具有极大潜力的知识发现工具，备受人工智能工作者的关注，目前广泛应用于机器学习、模式识别、专家系统、计算机网络、决策分析和数据挖掘等领域。知识发现的一个重要方面是知识约简。概念格属性约简为基于概念格理论的人工智能、知识发现和数据挖掘等提供了有力的知识、数据约简方法。本文介绍了概念格及其约简的一般性理论，主要研究了六个典型的概念格属性约简方法：基于属性特征的、差别矩阵的、新差别矩阵的、交不可约元的、并不可约元的和粒的概念格约简方法。从约简方法的实际约简效率方面考虑，给出了以上约简方法的具体算法设计和实现，分析了算法时间复杂度和空间复杂度，并进行了实际约简实验测试和对比分析研究。实验分析表明，基于属性特征的约简方法具有很高的约简效率，比其他方法快了上千倍，基于新差别矩阵的约简方法比基于差别矩阵的方法快约6倍，比基于粒的概念格约简方法快约0.25倍，而基于不可约元的两方法具有相同的约简效率。对约简算法的定量对比分析为概念格属性约简的应用和研究起到了实际的参考作用。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景与意义
• 1.2 概念格及其约简研究现状
• 1.3 本文研究内容
• 1.4 本文组织结构
• 第二章 概念格理论基础
• 2.1 概念格基本概念和理论
• 2.2 概念格的建立
• 2.3 本章小结
• 第三章 概念格属性约简算法设计
• 3.1 基于属性特征的概念格约简算法
• 3.2 基于差别矩阵的概念格约简算法
• 3.3 基于新差别矩阵的概念格约简算法
• 3.4 基于粒的概念格约简算法
• 3.5 基于交不可约元的概念格约简算法
• 3.6 基于并不可约元的概念格约简算法
• 3.7 本章小结
• 第四章 概念格属性约简算法实现
• 4.1 算法实现
• 4.2 本章小结
• 第五章 概念格属性约简算法实验和分析
• 5.1 基于差别矩阵的概念格约简算法实验和分析
• 5.2 基于不可约元的概念格约简算法实验和分析
• 5.3 六种概念格约简算法的实验和分析
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 论文工作总结
• 6.2 研究工作展望
• 致谢
• 参考文献
• 攻读硕士期间参与的科研工作