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