一种快速的不完备决策表属性约简算法

被引：16

作者：

舒文豪 ^{[1
]}

徐章艳 ^{[1
]}

钱文彬 ^{[2
]}

杨炳儒 ^{[2
]}

机构：

[1] 广西师范大学计算机科学与信息工程学院

[2] 北京科技大学信息工程学院

来源：

小型微型计算机系统 | 2011年 / 32卷 / 09期

关键词：

粗糙集; 不完备决策表; 正区域; 差别矩阵; 属性约简; 算法复杂度;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

目前,关于不完备决策表的属性约简算法已有不少,其中在很多算法中,其时间复杂度为O(|C|3|U|2).为有效地降低算法的时间复杂度,给出一个差别矩阵的定义和基于差别矩阵属性约简的定义,并证明了该属性约简与基于正区域的属性约简是等价的.生成的差别矩阵无需比较Uneg之间的对象,使差别矩阵得到有效地简化,进一步降低算法的存储空间.在此基础上,利用简化的差别矩阵设计一个快速计算不完备决策表的属性约简的算法,其时间复杂度降为max{O(|C|2|Upos||U|),O(K|C||U|)}.(其中K=max{|TC(xi)|,xi∈U}).最后用实例仿真说明了新算法的有效性.

引用

页码：1867 / 1871

页数：5

共 7 条

[1] 一种基于知识粒度的不完备信息系统的属性约简算法 [J].