一种基于差别矩阵的属性约简完备算法  

A Complete Algorithm for Attribute Reduction Based on Discernibility Matrix

作　　者：王兵[1] 陈善本[1] 

机构地区：[1]上海交通大学材料科学与工程学院,上海200030

出　　处：《上海交通大学学报》2004年第1期43-46,共4页Journal of Shanghai Jiaotong University

基　　金：上海市科学技术委员会资助项目(021111116);教育部高校博士点基金资助项目(20020248015)

摘　　要：提出了一种基于差别矩阵的粗糙集属性约简完备算法,算法的求解策略是在每次迭代过程中只选择必要的条件属性,如果在某次迭代过程中找不到这样的条件属性,则任意排除一条件属性,为下一次迭代中找到必要的条件属性做准备.分析了算法在最坏情况下的时间复杂性,给出了该算法相对Pawlak约简的完备性的证明.同已有的同类约简算法相比,该算法在最坏情况下具有更小的时间复杂性.A complete algorithm for attribute reduction in rough set theory based on discernibility matrix was introduced. The strategy of the algorithm is to select those indispensable condition attributes. If in some iteration the algorithm can not find such attributes it will eliminate one condition attribute preparing for finding indispensable condition attributes in the next iteration. The time complexity of the algorithm in the worst case was analyzed and the proof of its completeness was given. The time complexity of the algorithm is lower than other presented complete algorithms.

关 键 词：粗糙集 差别矩阵 属性约简 完备算法 

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