决策蕴含简化算法研究

随着形式背景中数据的增多，概念数量会急剧增加，会使决策的过程变得复杂。大多数参考文献的研究主要集中于给定决策背景的条件下，决策规则的提取，本文首次以决策蕴含简化方法为研究重点，利用计算机模拟人的思维过程，通过计算对象的覆盖，进而计算出决策背景，并在此基础上生成非冗余限制决策蕴含，与非冗余决策规则相比，其形式更简化，更有利于决策者进行决策；其次，为使决策过程简单，提出了决策背景的生成定理及非冗余限制决策蕴含的处理定理并予以证明；随后提出了算法并讨论了算法的时间复杂度。通过实例分析，对比了其它决策规则提取算法的运行效率和分类能力，证明本文提出的算法具有可行性和正确性。最后进行了总结并讨论了开放性问题。

形式概念分析[1]最早由德国教授Wille R.提出，以形式背景和形式背景下生成的概念为基础，开创了概念格理论与应用研究的先河。随后作为数据分析和处理的重要工具，形式概念分析已被广泛应用于计算机推理、知识发现及机器学习等领域。国外学者的研究主要包括：形式背景的分解、概念格的图形表示[2]及属性选取方法等。

形式背景中数据量的增多，相应的概念数量会急剧增长，每一个概念都代表一种分类，对象的分类众多，会给决策者制定决策时带来巨大的挑战。属性约简可以将研究问题进行简化，Skowron 教授[3]提出了基于区分矩阵的求核算法， 利用合取、析取运算对区分矩阵进行求解， 奠定了属性约简的研究基础； Sabita Mahapatra [4]等针对粗糙集理论，利用不可辨识矩阵进行属性提取并生成了决策规则，与统计方法进行对比说明了算法的有效性；李进金等人[5]，引入交式可约元的概念，扩展了属性约简的研究方法；张文修等人[6]提出了概念格约简的判定定理，将可辨识属性矩阵作为属性约简的方法；王霞等人[7]针对不可约元的属性约简问题构造了属性约简集，丰富了属性约简方法；Wenbin Qian [8]等人针对不完全序的模糊决策信息系统，提出基于优势的粗糙集与α-割集相结合的属性约简方法，在一致和不一致的信息系统中利用了布尔推理的方法，设计了向前和向后属性约简算法求解近似最优属性约简；Hua Mao [9]提出利用有向图进行属性约简和概念格构造，借助图论的上下文中的概念，定义属性集上的相关图，进一步，定义一个预先加权的相关图，进而，提出在有向图中删除顶点的方法，扩展了概念格的研究方法；Jiaqing Zhou [10]等人讨论了覆盖相关族及其简化的概念，并给出覆盖相关族的计算方法，然后从简化覆盖计算所有属性约简，最后提出了一种启发式的属性约简方法；Nguyen Ngoc Thuy [11]等人提出了基于商集的属性重要性度量方法，设计了计算核和约简的有效算法，还给出与有效计算属性重要性和在计算过程中显著减少数据大小直接相关的属性。