基于顺序表的启发式属性约简算法  

Heuristic Attribute Reduction Algorithm Based on Order Table

作　　者：梁宝华[1] 汪世义[1] 蔡敏[1] 

机构地区：[1]巢湖学院计算机科学与技术系,安徽巢湖238000

出　　处：《计算机工程》2012年第2期51-53,共3页Computer Engineering

基　　金：安徽省高校重点自然科学研究计划基金资助项目(KJ2008A35ZC)

摘　　要：利用顺序表存储数据集对象,并借助基数排序按关键字"分配"思想,求解U/C的时间复杂度为O(|P||U|)、空间复杂度为O(U)。在求属性约简集时,为避免存储差别矩阵所需的大量空间,利用差别矩阵的直观性,给出一种计算差别对象个数公式,并以此为启发信息,设计2种动态约简算法,其时间/空间复杂度分别为O(|C|2|U/C|)、max(O(|U/Ci|))。理论分析与实验结果表明该算法是有效可行的。Using order list to store data set objects and borrowing the idea of allocation by keys in radix sorting,its time and space complexity for U/C is and O（U） respectively.To avoid large space to store discernibility matrix and use the intuition of it,a expressions to compute the number of discernibility objects is presented when computing attribute reduction sets.Two algorithms are designed with time and space complexity only and max（）.Theoretical analysis and experimental results show that the algorithm is effective and feasible.

关 键 词：粗糙集 属性重要性 差别矩阵 顺序表 启发式 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]