第6期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1083· 3.1增量式属性约简算法 表1弱标记不完备决策系统 算法2弱标记不完备决策系统的增量式约 Table 1 Incomplete decision system with weak labeling 简算法(WIDIAR算法) U C1 C2 C3 D b 0.71 1 输入弱标记不完备决策系统WDS=<U, 1 X b 0.58 CUD,V,f>,U=LUM,删除的实例△Ue=△MaeU 0 b a 0.80 △Lue,增加的实例△Ud=△MaU△Lad,原属性约简 X4 b 0.65 结果red; b 0.72 输出属性约简结果red。 6 0.72 l)计算删除实例△U后存在的区分对Pairde; a a 0.77 2)对于Yc.∈red',red=red,如果满足条件： RSig(ck,red-c,Pair)=0,则根据定义7逆向剔除 根据表1详细描述算法1属性约简的具体 冗余属性，red'=red'-ck; 步骤：算法1中的1)变量初始化；2)计算关于属 3)计算增加的区分对△Pairad, 性集C的区分对，确定算法的搜索空间Pairo= 4)j=0,C'=red,C=C-C'; {Kx1,>,<2,X>,<x4>,<,7>,<67>};在 算法1的3)中第一次迭代时red=O、RSig(c1,red, △Paird=△Pairad; Pairo)=3 RSig(c2,red,Pairo)=2 RSig(ca,red,Pairo)= while(△Paird≠O): 2、RSig(c4,red,Pairo)=2,第一次迭代结束后，Pair1= {Vck E Cj,if(RSig(ck,red,Pairj)=0),C'=C'UC; {<,为>，<2，x>,red={clo由于此时Pair≠0， ck=argmax(RSig(ck,red',△Paird)lc∈Cj-C"i 因此需进行第二次迭代，red={c},RSig(c2,red, red'=red'Uck.C'=C'Uck; Pair)=0,RSig(c3,red,Pair)=0,RSig(ca,red,Pair)=2, Pair'=Dis(c,APair); C=C-C,APair=APair -Pair'; 第2轮迭代结束后，Pair=0、red={c1,c4}循环结 束：算法1在4)中未发现冗余属性，最后输出属 j=j+1} 性约简结果red={c,ca}。 5)对可能存在的冗余属性进行逆向剔除，计 为进一步详细说明算法2针对不同实例变化 算Pair=Dis(red',(U-△Uae)U△Ua));Yc∈red',如果 后对原属性约简结果产生的影响，下面首先分析 RSig(ck,red'-ck.Pair)=0,red'=red'-c&; 算法2的2)中实例动态删除情况。在数据中删 6)输出新的属性约简结果red。 除实例将存在6种情况：1)只删除有标记的实 3.2时间复杂度分析 例{x},对于Yc.∈red={c1,ca}有RSig(ck,red-Ck, 算法2中：1)计算删除实例后属性集red的 Pair)≠0，属性约简集保持不变red'={c,c:2)只 区分对，其时间复杂度为O(U-△Uae)red);2)对 删除有标记的实例{，有RSig(ca,red-c4,Pair)=0, 可能存在的冗余属性逆向删除，其时间复杂度为 此时c4相对于c为冗余属性，属性约简集更新为 O(U-△U)2red);3)计算由于增加实例△Uu而 red={c;3)只删除无标记的实例{x4,对Yc∈ 增加的区分对，其时间复杂度为OU-△U△U red={c,cal,RSig(c,red-ck,Pair)≠0，属性约简集保 IC):4)若原属性约简集red'无法维持最大区分 持不变red'={c1,ca:4)只删除无标记的实例{， 度，则需要在属性集C-C'中筛选属性加入属性 有RSig(ca,red-c4,Pair)=0,此时c4相对于c1为冗 余属性，属性约简集更新为red={c;5)同时删 约简集，其时间复杂度为O∑APairC:5)对 除有标记的实例{x}和无标记的实例{x},对 =0 可能存在的冗余属性进行别除，时间复杂度为 Yck∈red={c1,ca},RSig(ck,red-c,Pair)≠0，属性约 O(PairllredP)。 简集维持不变red={c1,ca;6)同时删除有标记的 实例{x}和无标记的实例{xl,有RSig(c,red-c, 4实例分析 Pair)=0,此时c1相对于c4为冗余属性，属性约简 集更新为red={ca}。 为进一步详细说明算法的流程。以表1中的 由于在许多现实动态场景中不仅存在数据删 弱标记不完备数据为例，进行分析说明。其中共 除还有数据动态增加的情况，为了进一步分析算 有6个实例和4个属性，U={1,2,3,x45,x6,x}为 法2的3)和4)的计算流程，在上述实例中若在原 实例集，C={c1,c2,c3,c4}为条件属性集，D为决策 始数据集中删除实例U={x,x,删除实例后属 属性，“*”表示缺失值，阈值6=01。 性约简集为red={ca},在此基础上，在数据中增3.1 增量式属性约简算法 算法 2 弱标记不完备决策系统的增量式约 简算法 (WIDIAR 算法) WIDS =< U, C ∪ D,V, f > U = L∪ M ∆Ude = ∆Mde∪ ∆Lde ∆Uad = ∆Mad ∪∆Lad red 输入 弱标记不完备决策系统 ， ，删除的实例 ，增加的实例 ，原属性约简 结果 ； red 输出 属性约简结果 ′。 1) 计算删除实例 ∆Ude 后存在的区分对 Pairde； ∀ck ∈ red′ red′ = red RSig(ck ,red′ −ck ,Pairde) = 0 red′ = red′ −ck 2) 对于 ， ，如果满足条件： ，则根据定义 7 逆向剔除 冗余属性， ; 3) 计算增加的区分对 ∆Pairad; j = 0 C ′ = red′ Cj = C −C ′ 4) , , ; ∆Pairj ad = ∆Pairad; while(∆Pairj ad , 0) : ∀ck ∈ Cj if(RSig(ck ,red,Pairj) = 0) C ′=C ′ { ， ， ∪ck； ck= argmax{RSig(ck ,red′ ,∆Pairj ad)|ck ∈ Cj −C ′ }; red′ = red′ ∪ck ,C ′ = C ′ ∪ck ; Pair′ = Dis(ck ,∆Pairj ad); Cj+1 = C −C ′ ,∆Pairj+1 ad = ∆Pairj ad −Pair′ ; j = j+1 ;} Pair = Dis(red′ ,((U −∆Ude)∪∆Uad) 2 ) ∀ck ∈ red′ RSig(ck ,red′ −ck ,Pair) = 0 red′ = red′ −ck 5) 对可能存在的冗余属性进行逆向剔除，计 算 ; ,如果 ， ; red′ 6) 输出新的属性约简结果 。 3.2 时间复杂度分析 red O((U −∆Ude) 2 |red|) O((U −∆Ude) 2 |red| 2 ) ∆Ude O(|U −∆Ude||∆Uad| |C|) red′ C −C ′ O (∑ j i=0 |∆Pairi ad||Ci | ) O(|Pair||red′ | 2 ) 算法 2 中：1) 计算删除实例后属性集 的 区分对，其时间复杂度为 ；2) 对 可能存在的冗余属性逆向删除，其时间复杂度为 ；3) 计算由于增加实例 而 增加的区分对，其时间复杂度为 ；4) 若原属性约简集 无法维持最大区分 度，则需要在属性集 中筛选属性加入属性 约简集，其时间复杂度为 ；5) 对 可能存在的冗余属性进行剔除，时间复杂度为 。 4 实例分析 U = {x1, x2, x3, x4 x5, x6, x7} C = {c1, c2, c3, c4} D δ = 0.1 为进一步详细说明算法的流程。以表 1 中的 弱标记不完备数据为例，进行分析说明。其中共 有 6 个实例和 4 个属性， 为 实例集， 为条件属性集， 为决策 属性，“*”表示缺失值，阈值 。 表 1 弱标记不完备决策系统 Table 1 Incomplete decision system with weak labeling U c1 c2 c3 c4 D x1 a b * 0.71 1 x2 a * b 0.58 0 x3 a b a 0.80 1 x4 b a * 0.65 * x5 b a b 0.72 * x6 b * b 0.72 * x7 a b a 0.77 * C Pair0 = {< x1, x2 >,< x2, x3 >,< x4, x7 >,< x5, x7 >,< x6, x7 >} red = Ø RSig(c1,red, Pair0) = 3 RSig(c2,red,Pair0) = 2 RSig(c3,red,Pair0) = 2 RSig(c4,red,Pair0) = 2 Pair1 = { < x1, x2 >,< x2, x3 > } red = {c1} |Pair1| , 0 red = {c1} RSig(c2,red, Pair1) = 0 RSig(c3,red,Pair1) = 0 RSig(c4,red,Pair1) = 2 Pair2 = Ø red = {c1, c4} red = {c1, c4} 根据表 1 详细描述算法 1 属性约简的具体 步骤：算法 1 中的 1) 变量初始化；2) 计算关于属 性集 的区分对，确定算法的搜索空间 ； 在 算法 1 的 3) 中第一次迭代时 、 、 、 、 ，第一次迭代结束后， ， 。由于此时 ， 因此需进行第二次迭代， ， 、 、 ， 第 2 轮迭代结束后， 、 循环结 束；算法 1 在 4) 中未发现冗余属性，最后输出属 性约简结果 。 {x1} ∀ck ∈ red = {c1, c4} RSig(ck ,red−ck , Pair) , 0 red′ = {c1, c4} {x2} RSig(c4,red−c4,Pair) = 0 c4 c1 red′ = {c1} {x4} ∀ck ∈ red = {c1, c4} RSig(ck ,red−ck ,Pair) , 0 red′ = {c1, c4} {x7} RSig(c4,red−c4,Pair) = 0 c4 c1 red′ = {c1} {x1} {x4} ∀ck ∈ red = {c1, c4} RSig(ck ,red−ck ,Pair) , 0 red′ = {c1, c4} {x1} {x7} RSig(c1,red−c1, Pair) = 0 c1 c4 red′ = {c4} 为进一步详细说明算法 2 针对不同实例变化 后对原属性约简结果产生的影响，下面首先分析 算法 2 的 2) 中实例动态删除情况。在数据中删 除实例将存在 6 种情况：1) 只删除有标记的实 例 ，对于 有 ，属性约简集保持不变 ；2) 只 删除有标记的实例 ，有 ， 此时 相对于 为冗余属性，属性约简集更新为 ； 3) 只删除无标记的实例 ，对 ， ，属性约简集保 持不变 ；4) 只删除无标记的实例 ， 有 ，此时 相对于 为冗 余属性，属性约简集更新为 ；5) 同时删 除有标记的实例 和无标记的实例 ，对 ， ，属性约 简集维持不变 ；6) 同时删除有标记的 实例 和无标记的实例 ，有 ，此时 相对于 为冗余属性，属性约简 集更新为 。 Ude = {x1, x7} red′ = {c4} 由于在许多现实动态场景中不仅存在数据删 除还有数据动态增加的情况，为了进一步分析算 法 2 的 3) 和 4) 的计算流程，在上述实例中若在原 始数据集中删除实例 ，删除实例后属 性约简集为 ，在此基础上，在数据中增 第 6 期 程龙，等：弱标记不完备决策系统的增量式属性约简算法 ·1083·