信息系统中正区域快速求解算法研究  

Research on fast algorithm for computing positive region in information systems

作　　者：葛浩[1] 杨传健[2] 李龙澍[3] 

机构地区：[1]滁州学院电子信息工程系,安徽滁州239012 [2]滁州学院计算机系,安徽滁州239012 [3]安徽大学计算机学院,安徽合肥230039

出　　处：《计算机工程与设计》2009年第7期1742-1744,1801,共4页Computer Engineering and Design

基　　金：安徽省自然科学基金项目(O50420204);安徽高校省级自然科学研究项目(KJ2008B117);滁州学院院级自然科学研究项目(2007ky044)

摘　　要：正区域是粗糙集理论中最重要的概念之一,求解正区域一般算法的时间复杂度为O(|C||U|2)。为了提高正区域求解效率,提出一种快速等价类划分算法,并应用于正区域求解过程中,使求正区域算法的时间复杂度降低为O(|C||U|)。然后,提出负区域的概念,证明了在负区域中求解正区域的性质,并给出改进后的算法,使求解正区域的时间复杂度进一步降低为max{O(|C||U-POS{a1}(D)|),O(|U|)。理论分析和实验结果表明,该算法是正确的、高效的。Positive region is one of the most important concepts in rough sets theory. Generally, the time complexity of the algorithm for positive region is O （｜C｜ ｜U｜^2）. For improving the efficiency of computing the positive region, a quick algorithm of the equivalence partitioning is presented. In the basic, the algorithm for computing positive region is designed, and its time complexity is O （｜C｜ ｜U｜）. Then, the negative region definition is put forward, and it is proven to be correct to compute positive region in the negative region. The method improves the efficiency of computing positive region further, the time complexity of the algorithm is cut down to max {O （｜C｜ ｜U｜- POS {a}, （D） ｜）, 0 （｜U｜）}. Its theoretical analysis and experimental result show the algorithm is correct and efficient.

关 键 词：粗糙集 等价类划分 正区域 

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