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

More Accurate Models of Time Complexity about the Method Constructing the Discernibility Matrix

作　　者：胡霞[1] 费鹏 杜卫锋[3] HU Xia;FEI Peng;DU Wei-feng(School of Software ＆ Service Outsourcing,Suzhou Institute of Industrial Technology,Suzhou 215104,China;Suzhou Chuangcai Software Co.,Ltd.,Suzhou 215128,China;School of Mathematics,Physics and Information Engineering,Jiaxing University,Jiaxing 314001,China)

机构地区：[1]苏州工业职业技术学院软件与服务外包学院,江苏苏州215104 [2]苏州市创采软件有限公司,江苏苏州215128 [3]嘉兴学院数理与信息工程学院,浙江嘉兴314001

出　　处：《控制工程》2018年第9期1771-1776,共6页Control Engineering of China

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

摘　　要：属性约简是粗糙集理论的核心研究内容之一,基于辨识阵的方法可以获得所有的约简,该方法的1个关键步骤是构造辨识阵,如何降低构造辨识阵的代价以及估计构造辨识阵的时间复杂度,具有重要的理论与实用价值。通过先对协调决策表,再对不协调决策表的深入研究和分析,给出了辨识阵构造方法时间复杂度更精确的上界模型。通过给出1个简单的不协调决策表实例,对该实例进行计算,并对计算结果加以说明;然后对若干中等规模的数据集进行了仿真测试,该模型给出的理论估计值与程序得到的实际测试值均十分接近,相对误差基本上都在3%之内,表明了该模型的有效性和正确性,为估计构造辨识阵的时间复杂度提供了更精确的理论模型。Attribute reduction is one of the core research contents of rough set theory. All the reducts can be obtained through the method based on the discernibility matrix, a key step of this method is to construct the discernibility matrix, how to reduce the cost of constructing the discernibility matrix and estimate accurately the time complexity of constructing the discernibility matrix has very important theoretical and practical value. Through deep study and analysis about consistent decision table, and then inconsistent decision table, more accurate upper bound models of time complexity about the algorithm of constructing the discernibility matrix are given. By giving a simple example of the inconsistent decision table, the example is calculated, and the results are illustrated, then the simulation tests are carried out on a number of medium scale data sets. The estimated value of the theory given by the model is very close to the actual test values obtained by the program, and the relative error is basically within 3 %. The results show the effectiveness and correctness of the model, and a theoretical basis for estimating the time complexity of constructing the discernibility matrix is provided.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O159[自动化与计算机技术—控制科学与工程]