基于相容矩阵的改进属性约简算法  

Improved Attribute Reduction Algorithm Based on Tolerance Matrix

作　　者：韩智东[1,2] 王志良[1,2] 高静[3] 徐章艳[4] 

机构地区：[1]北京科技大学信息工程学院,北京100083 [2]北京科技大学钢铁流程先进控制教育部重点实验室,北京100083 [3]首都经济贸易大学信息学院,北京100070 [4]广西师范大学计算机系,广西桂林541004

出　　处：《计算机工程》2010年第20期25-27,31,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60573059);北京市重点学科建设基金资助项目(XK100080537);广西教育厅基金资助项目(200807MS015)

摘　　要：原属性约简算法在计算相容关系时,存在大量重复计算,从而导致时间复杂度为O(|C|3|U|2)。针对该问题,基于不完备决策表,提出时间复杂度为O(|U|2)的高效相容矩阵计算算法,在此基础上,设计改进的基于相容矩阵的属性约简算法。通过实例证明,当空间复杂度相同时,改进算法的时间复杂度从原有O(|C|3|U|2)降为O(|C|2|U|2)。When original attribute reduction algorithm calculates tolerance relation,there is much repeatedly calculating consumption.And this leads to O（｜C｜3｜U｜2） time complexity.Aiming at this problem,based on incomplete decision table,this paper presents a high efficient tolerance matrix computational algorithm whose time complexity is O（｜U｜2）.On that basis,it designs an improved attribute reduction algorithm based on tolerance matrix.Test proves that the time complexity of improved algorithm is reduced from O（｜C｜3｜U｜2） to O（｜C｜2｜U｜2） with the same space complexity.

关 键 词：粗糙集 属性约简 相容关系矩阵 不完备决策表 

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