基于属性值集合链的粗糙集快速属性约简算法  

Fast attribute reduction algorithm of rough set based on attribute value collection chain

作　　者：武友新[1] 李文晶[1] 钟子岳 WU You-xin LI Wen-jing ZHONG Zi-yue(School of Information Engineering, Nanchang University, Nanchang 330031, China Department of Computer Science, University of Montana, Missoula 59801, USA)

机构地区：[1]南昌大学信息工程学院,江西南昌330031 [2]蒙大拿大学计算机系,蒙大拿州米苏拉59801

出　　处：《计算机工程与设计》2016年第11期2967-2970,3021,共5页Computer Engineering and Design

摘　　要：在属性约简的过程中需要耗费大量的时间和计算机资源,针对如何提高粗糙集属性约简算法的运行效率问题,提出一种基于属性值集合链的快速属性约简算法。其时间复杂度为O（｜ C｜｜U/C｜）,相对于分明矩阵的粗糙集属性约简算法的时间复杂度O（｜U｜2｜C｜）,运行效率在理论上得到明显提高。具体实验分析对比结果表明,在不同数据量的数据集上,该算法的实际时间效率比传统分明矩阵算法更优。Attribute reduction algorithms require high time consumption and computer resources in the process of attribute reduction.To improve the operation efficiency of rough set attribute reduction algorithm,a fast algorithm of attribute reduction algorithm based on the chain of attribute values was proposed,and the time complexity of the algorithm was O（｜ C｜｜U/C｜）,relative to the rough set attribute reduction algorithm based on discernibility matrix of which time complexity was O（｜U｜2｜C｜）,the efficiency of the algorithm was significantly improved.Through concrete experiment analyzing,on datasets with different data volumes,the real time efficiency of the algorithm is better than traditional distinct matrix algorithm.

关 键 词：粗糙集 属性约简 分明矩阵 属性值集合链 算法时间复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]