摘要
正区域是粗糙集理论中最重要的概念之一,求解正区域一般算法的时间复杂度为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.
出处
《计算机工程与设计》
CSCD
北大核心
2009年第7期1742-1744,1801,共4页
Computer Engineering and Design
基金
安徽省自然科学基金项目(O50420204)
安徽高校省级自然科学研究项目(KJ2008B117)
滁州学院院级自然科学研究项目(2007ky044)
关键词
粗糙集
等价类划分
正区域
rough set
equivalence partitioning
positive region
