基于改进的差别矩阵的快速属性约简算法  

Fast attribute reduction algorithm based on improved discernibilty matrices

作　　者：钱进 叶飞跃[1] 徐亚平[1] 

机构地区：[1]江苏技术师范学院计算机科学与工程学院,江苏常州213001

出　　处：《计算机工程与应用》2008年第21期102-105,共4页Computer Engineering and Applications

基　　金：江苏技术师范学院青年项目资金( No.KYY07030)

摘　　要：为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i<j≤K|Di||Dj|),O(|C||U|))和max(O(|C|Σ0≤i<j≤k|Di||Dj|),O(|U|))。最后,实例分析与实验结果表明了新算法具有高效性。In order to solve the efficiency problem of calculating the attribute reduction based on discernibility matrices,a new algorithm based on counting sorting for computing U/C is provided,and its complexity is cut down to O（｜C｜｜U｜）.Then,the shortcomings of attribution reduction algorithm are analyzed based on discernibility matrices, and the definition of the improved discernibility matrices is presented.Furthermore,core attribute computed by a fast computing core algorithm and an attribute with more frequencies can be used to generate smaller class feature matrices.So a new algorithm based on the improved class feature math ces is proposed,whose worst time complexity and space complexity are cut down to max（O（｜C｜2∑0≤i〈j≤k｜Di｜｜Dj｜）,O（｜C｜｜U｜））and max（O（｜C｜∑0≤i〈j≤k｜Di｜｜Dj｜）,O（｜U｜）） respectively.An example is used to illustrate the efficiency of the new algorithm.Experiments show that the new algorithm is efficient for various kinds of data sets.

关 键 词：粗糙集 属性约简 差别矩阵 核属性 

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