辨识阵构造方法更精确的时间复杂度模型

摘要：

属性约简是粗糙集理论的核心研究内容之一,基于辨识阵的方法可以获得所有的约简,该方法的1个关键步骤是构造辨识阵,如何降低构造辨识阵的代价以及估计构造辨识阵的时间复杂度,具有重要的理论与实用价值.通过先对协调决策表,再对不协调决策表的深入研究和分析,给出了辨识阵构造方法时间复杂度更精确的上界模型.通过给出1个简单的不协调决策表实例,对该实例进行计算,并对计算结果加以说明;然后对若干中等规模的数据集进行了仿真测试,该模型给出的理论估计值与程序得到的实际测试值均十分接近,相对误差基本上都在3％之内,表明了该模型的有效性和正确性,为估计构造辨识阵的时间复杂度提供了更精确的理论模型.

关键词：粗糙集、属性约简、辨识阵、时间复杂度

所属期刊栏目：25

分类号：TP18;O159(自动化基础理论)

资助基金：国家自然科学基金项目61202109,面向公钥密码系统的可扩展DNA生物计算模型研究与探索

在线出版日期：2018-09-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1771-1776