·1082· 智能系统学报 第15卷 C-R,假设RSig(c,R,U)≠0，根据定义6有Dis(R, red=redUce,Pair'=Dis(ce,Pair,); U=Dis(C,U),根据定义7可知： C=C'Uck; RSig(c,R,U2)=Dis(c,U2)-Dis(c,U2)Dis(R,U2) Pair#1=Pair,-Pair∥别除当前属性集已经能区 =Dis(C.U)-Dis(C.U2)nDis(C.U)=0 分的区分对 与假设矛盾。证明了1)的必要性，同理可证2)。 C#1=C,-C/别除已加入属性约简集的属性 和相对冗余的属性 2弱标记不完备决策系统的属性约简 j=j+1} 基于属性重要度设计启发式属性约简算法， 4)对可能存在的冗余属性进行逆向剔除 被广泛地用于粗糙集理论的属性约简，传统的启 计算Pair=Dis(red,UP) 发式算法每次迭代时，每次将最重要的属性增加 对于Yck∈red,如果RSig(ck,red-ck,Pair)=0, 到属性约简集中，但是在迭代过程中无法剔除相 red red-cx 对冗余的属性。本文提出一种基于区分对的向前 5)输出属性约简集red 启发式属性约简算法，在每次迭代中，将相对于 2.2时间复杂度分析 当前属性约简集最重要的属性加入属性约简集 算法1的1)初始化变量：2)根据定义2和定 中，并剔除相对冗余属性和当前属性集已经能够 义4计算实例在属性集C上的区分对，其时间复 区分的实例对，快速缩减算法的搜索空间。 杂度为OU1C):3)是在性质2的基础上，采用相 对重要度为标准设计启发式算法，在迭代过程中 2.1属性约简算法 不断缩减算法的搜索空间，其时间复杂度为 算法1弱标记不完备决策系统属性约简算 法(WIDAR算法) oPair C小)对可能存在的冗余属性进行剔 输入弱标记不完备决策系统WIDS=<U, 除，时间复杂度为O(IPairllredl)。 C,V.f>; 输出属性约简集red。 3弱标记不完备决策系统的增量式 1)j=0,Pairj=0,Cj=C,C=0,Pair'=0, 属性约简 red=0; 在动态数据中使用传统的属性约简方法，往往 2)计算属性集C的区分对Pair=Dis(C,UP) 无法快速获取约简结果，而增量式属性约简算法能 3)while(Pair,l≠O) 有效地利用原约简结果，避免大量的重复计算。针 {对ck∈C,计算RSig(ck,red,Pair 对数据动态变化的情况，本节分析了数据动态变化 当RSig(c,red,Pair)=0,ck相对red为冗余属 对实例区分对的影响，图2给出了属性约简的增量 性，C'=C'Uc; 式更新机制，并针对动态数据中的实例变化情况， C=argmax(RSig(ce,red,Pair )ICk EC-C); 算法2设计了属性约简增量式更新算法。 原不完备信息系统 U,属性约简集：red 删除实例 新增实例 更新Dis,(C) 更新Disw(C 更新Dis,(C 更新Disw(C 存在冗余属性 维持最大区分度 Y 更新约简结 维持原约简 更新原约简 果：redd 结果：red 结果：reda 图2属性约简的增量式更新机制 Fig.2 Incremental updating mechanism of attribute reductionC −R RSig(c,R,U 2 ) , 0 Dis(R, U 2 ) = Dis(C,U 2 ) ，假设 ，根据定义 6 有 ，根据定义 7 可知： RSig(c,R,U 2 )= |Dis(c,U 2 )−Dis(c,U 2 )∩Dis(R,U 2 )| = |Dis(c,U 2 )−Dis(c,U 2 )∩Dis(C,U 2 )| = 0 与假设矛盾。证明了 1) 的必要性，同理可证 2)。 2 弱标记不完备决策系统的属性约简 基于属性重要度设计启发式属性约简算法， 被广泛地用于粗糙集理论的属性约简，传统的启 发式算法每次迭代时，每次将最重要的属性增加 到属性约简集中，但是在迭代过程中无法剔除相 对冗余的属性。本文提出一种基于区分对的向前 启发式属性约简算法，在每次迭代中，将相对于 当前属性约简集最重要的属性加入属性约简集 中，并剔除相对冗余属性和当前属性集已经能够 区分的实例对，快速缩减算法的搜索空间。 2.1 属性约简算法 算法 1 弱标记不完备决策系统属性约简算 法 (WIDAR 算法) WIDS =< U, C,V, f > 输入 弱标记不完备决策系统 ； 输出 属性约简集 red。 j = 0 Pairj = Ø Cj = C C ′ = Ø Pair′ = Ø red = Ø 1 ) ， ， ， ， ， ； C Pairj = Dis(C,U 2 2) 计算属性集 的区分对 ) ; while(|Pairj 3) | , 0) ck ∈ Cj RSig(ck {对 ,计算 ,red,Pairj) : RSig(ck ,red,Pairj) = 0 ck red C ′=C ′ ∪ck 当 ， 相对 为冗余属 性， ; ck= argmax{RSig(ck ,red,Pairj )|ck ∈ Cj −C ′ }; red = red∪ck Pair′ = Dis(ck ,Pairj , ) ; C ′ = C ′ ∪ck ; Pairj+1 = Pairj −Pair′ //剔除当前属性集已经能区 分的区分对 Cj+1 = Cj −C ′ //剔除已加入属性约简集的属性 和相对冗余的属性 j = j+1 ;} 4) 对可能存在的冗余属性进行逆向剔除 Pair = Dis(red,U 2 计算 ) ∀ck ∈ red RSig(ck ,red−ck ,Pair) = 0 red = red−ck 对 于 , 如 果 ， ; 5) 输出属性约简集 red 2.2 时间复杂度分析 C O(|U| 2 |C|) O (∑ |red| j=0 |Pairj ||Cj | ) O(|Pair||red| 2 ) 算法 1 的 1) 初始化变量；2) 根据定义 2 和定 义 4 计算实例在属性集 上的区分对，其时间复 杂度为 ；3) 是在性质 2 的基础上，采用相 对重要度为标准设计启发式算法，在迭代过程中 不断缩减算法的搜索空间，其时间复杂度为 ；4) 对可能存在的冗余属性进行剔 除，时间复杂度为 。 3 弱标记不完备决策系统的增量式 属性约简 在动态数据中使用传统的属性约简方法，往往 无法快速获取约简结果，而增量式属性约简算法能 有效地利用原约简结果，避免大量的重复计算。针 对数据动态变化的情况，本节分析了数据动态变化 对实例区分对的影响，图 2 给出了属性约简的增量 式更新机制，并针对动态数据中的实例变化情况， 算法 2 设计了属性约简增量式更新算法。 删除实例 新增实例 存在冗余属性 维持最大区分度 原不完备信息系统 U，属性约简集：red 更新 DisL (C) 更新 DisM (C) 更新 Dis 更新 DisM (C) L (C) 维持原约简 结果：red N Y Y N 更新约简结 果：reddel 更新原约简 结果：redad 图 2 属性约简的增量式更新机制 Fig. 2 Incremental updating mechanism of attribute reduction ·1082· 智 能 系 统 学 报 第 15 卷