第4期 钱进，等：面向成组对象集的增量式属性约简算法 .497. 策表中，一般不希望将原有的决策表和新产生的增 IND(R)表示，简记为U/R。U/R中的任何元素 量数据整合成一个新的决策表进行属性约简，因为 [x]R={ylHa∈R,f(x,a)=f(y,a)}称为等价 这样会对原有数据不断地进行重复的计算。因此， 类。不失一般性，假设决策表$仅有一个决策属性 如何利用原决策表中所含的信息并结合增量数据来 D={d},其决策属性值映射为1,2，…，k,由D导 进行属性约简成为粗糙集理论新的挑战。 出的U上划分记为U/D={D,D2,…,D},其 数据的动态变化主要有3种情况：1)属性集保 中，D={x∈Ulf(x,D)=i},i=1,2,…,k。 持不变而对象不断增加5$】：2)对象集保持不变而 定义2在决策表S=〈U,CUD,V)中，对 属性集不断增加：3)对象集和属性集同时增 于每个决策类D:∈U/D和不可区分关系ACC,D: 加。本文着重研究第1种情况的增量式属性约 的下近似集与上近似集分别可以由A的基本集定义 简问题，尤其研究适合大规模数据集的约简问题。 如下： 文献[5]提出了基于正区域的属性约简增量式更新 apra(D:)=UxUI [x]D 算法，提高了属性约简算法效率；文献[6]提出了基 apr(D:)=U{x∈U1[x]A∩D:≠☑} 于差别矩阵的属性约简增量式更新算法；文献[7] 定义3在决策表S=〈U,C,D,V)中， 提出了不使用可辨识矩阵的增量式核更新算法以及 HACC,正区域POS,(D)和边界域BND,(D)定 属性约简算法；文献[8]针对现有增量式属性约简 义为 算法中存在的约简传承性差以及不完备现象，提出 PoS,(D)=apr(D.) 了基于标记可辨识矩阵的增量式属性约简算法。然 而，这些算法不适宜解决每次增加批量对象的问题。 BND(D)=U (apr(D:)apr(D))= 文献[11]提出了面向成组对象集的3种增量式信 U-POS (D) 息嫡属性约简算法：文献[12]充分利用先前约简中 定义4 在决策表S中，一个属性集Red C 信息和计数排序算法快速更新批量对象的约简，降 是C的D-约简，如果 低计算复杂度；文献[13-14]探讨了混合属性约简 1)POSRed(D)=POSc(D); 算法以及利用MapReduce进行面向大规模数据集 2)Ha∈Red,POSRed-lai(D)≠POSR(D)。 的属性约简方法。 定义5在决策表S中，ACC,Hc∈A,在正 为提高增量式学习算法效率5]和约简传承性， 区域下属性c重要性定义为 本文构建了面向成组对象的增量式属性约简算法， Sigi(c,A,D)=Y(D)-YA-ic(D) 利用原始决策表的一个候选约简来快速地更新新增 I POS (D)I 式中：ya(D)= 决策表的约简，这样既提高了约简的传承性，又有效 U川 地利用了原有知识，提高了增量式学习算法效率。 定义6在决策表S中，A二C,Hc∈C-A, 在正区域下属性c重要性定义为 1粗糙集概念 Sig"(c,A,D)=YAul(D)-Y(D) 下面简要介绍本文主要用到的一些Rough集的 定义7设Red为决策表S的候选属性约简， 基本概念1,9，，1-14 NewRed为新增样本之后的新约简，则单次增量式 定义1四元组S=〈U,CUD,V,f是一个决 约简的传承率(inheritance rate,IR)定义为 策表，其中U={x1,x2,…,xn}表示对象的非空有限 IRed∩NewRed I IR = min(I Red I,I NewRed I) 集合，称为论域：C表示条件属性的非空有限集，D 假设进行了地次增量式约简，则平均传承率 表示决策属性的非空有限集，C∩D=☑；V=U acCUD (inheritance rate average,IRA)定义为 V。,V。是属性a的值域；f:U×(CUD)→V是一个 IR 信息函数，它为每个对象赋予一个信息值，即Ha∈ IRA= CUD,x∈U,有fx,a)∈'。；每一个属性子集 在约简过程中，传承率越高则约简集的变化越 R二CUD决定了一个二元不可区分关系 小，对原始规则集的影响将越小。如果传承率为1， IND(R): 说明新增的对象不影响原始的规则集：如果传承率 IND(R)= 为0，则新的约简集与原来的约简集完全不同，这时 {(x,y）∈U×U|a∈Rf(x,a)=fy,a)} 需全部更新所有规则。 关系IND(R)构成了U的一个划分，用U/策表中，一般不希望将原有的决策表和新产生的增 量数据整合成一个新的决策表进行属性约简，因为 这样会对原有数据不断地进行重复的计算。 因此， 如何利用原决策表中所含的信息并结合增量数据来 进行属性约简成为粗糙集理论新的挑战。 数据的动态变化主要有 ３ 种情况：１）属性集保 持不变而对象不断增加［５－８ ］ ；２）对象集保持不变而 属性集不断增加［９］ ； ３） 对象集和属性集同时增 加［１０］ 。 本文着重研究第 １ 种情况的增量式属性约 简问题，尤其研究适合大规模数据集的约简问题。 文献［５］提出了基于正区域的属性约简增量式更新 算法，提高了属性约简算法效率；文献［６］提出了基 于差别矩阵的属性约简增量式更新算法；文献［７］ 提出了不使用可辨识矩阵的增量式核更新算法以及 属性约简算法；文献［８］针对现有增量式属性约简 算法中存在的约简传承性差以及不完备现象，提出 了基于标记可辨识矩阵的增量式属性约简算法。 然 而，这些算法不适宜解决每次增加批量对象的问题。 文献［１１］提出了面向成组对象集的 ３ 种增量式信 息熵属性约简算法；文献［１２］充分利用先前约简中 信息和计数排序算法快速更新批量对象的约简，降 低计算复杂度；文献［１３－１４］探讨了混合属性约简 算法以及利用 ＭａｐＲｅｄｕｃｅ 进行面向大规模数据集 的属性约简方法。 为提高增量式学习算法效率［１５］ 和约简传承性， 本文构建了面向成组对象的增量式属性约简算法， 利用原始决策表的一个候选约简来快速地更新新增 决策表的约简，这样既提高了约简的传承性，又有效 地利用了原有知识，提高了增量式学习算法效率。 １ 粗糙集概念 下面简要介绍本文主要用到的一些 Ｒｏｕｇｈ 集的 基本概念［１，９，１１，１３－１４］ 。 定义 １ 四元组 Ｓ ＝ 􀎮Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ􀎯 是一个决 策表，其中 Ｕ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｎ ｝表示对象的非空有限 集合，称为论域； Ｃ 表示条件属性的非空有限集， Ｄ 表示决策属性的非空有限集， Ｃ ∩ Ｄ ＝ ⌀ ； Ｖ ＝ ∪ａ∈Ｃ∪Ｄ Ｖａ ， Ｖａ 是属性 ａ 的值域； ｆ：Ｕ × （Ｃ ∪ Ｄ） → Ｖ 是一个 信息函数，它为每个对象赋予一个信息值，即 ∀ａ ∈ Ｃ ∪ Ｄ ， ｘ ∈ Ｕ ，有 ｆ（ｘ， ａ） ∈ Ｖａ ；每一个属性子集 Ｒ ⊆ Ｃ ∪ Ｄ 决 定 了 一 个 二 元 不 可 区 分 关 系 ＩＮＤ（Ｒ） ： ＩＮＤ（Ｒ） ＝ ｛（ｘ，ｙ） ∈ Ｕ × Ｕ ｜ ∀ａ ∈ Ｒ，ｆ（ｘ，ａ） ＝ ｆ（ｙ，ａ）｝ 关系 ＩＮＤ（ Ｒ ） 构成了 Ｕ 的一个划分， 用 Ｕ ／ ＩＮＤ（ Ｒ ） 表示， 简记为 Ｕ／ Ｒ 。 Ｕ／ Ｒ 中的任何元素 ［ｘ］ Ｒ ＝ ｛ ｙ ｜ ∀ａ ∈ Ｒ ， ｆ（ｘ，ａ） ＝ ｆ（ｙ，ａ） ｝称为等价 类。 不失一般性， 假设决策表 Ｓ 仅有一个决策属性 Ｄ ＝ ｛ｄ｝， 其决策属性值映射为 １， ２，…， ｋ ，由 Ｄ 导 出的 Ｕ 上划分记为 Ｕ／ Ｄ ＝ ｛ Ｄ１ ， Ｄ２ ， …，Ｄｋ ｝，其 中， Ｄｉ ＝ ｛ ｘ ∈ Ｕ ｜ ｆ（ｘ，Ｄ） ＝ ｉ ｝， ｉ ＝ １， ２， …， ｋ。 定义 ２ 在决策表 Ｓ ＝ 􀎮Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ􀎯 中，对 于每个决策类 Ｄｉ ∈ Ｕ／ Ｄ 和不可区分关系 Ａ ⊆ Ｃ， Ｄｉ 的下近似集与上近似集分别可以由 Ａ 的基本集定义 如下： ａｐｒＡ（Ｄｉ） ＝∪ ｛ｘ ∈ Ｕ ｜ ［ｘ］ Ａ ⊆ Ｄｉ｝ ａｐｒＡ（Ｄｉ） ＝∪ ｛ｘ ∈ Ｕ ｜ ［ｘ］ Ａ ∩ Ｄｉ ≠ ⌀｝ 定 义 ３ 在 决 策 表 Ｓ ＝ 􀎮Ｕ，Ｃ，Ｄ，Ｖ，ｆ􀎯 中， ∀Ａ ⊆Ｃ， 正区域 ＰＯＳＡ（Ｄ） 和边界域 ＢＮＤＡ（Ｄ） 定 义为 ＰＯＳＡ（Ｄ） ＝ ∪１≤ｉ≤ｋ ａｐｒＡ（Ｄｉ） ＢＮＤＡ（Ｄ） ＝ ∪１≤ｉ≤ｋ （ａｐｒＡ（Ｄｉ） － ａｐｒＡ（Ｄｉ）） ＝ Ｕ － ＰＯＳＡ（Ｄ） 定义 ４ 在决策表 Ｓ 中，一个属性集 Ｒｅｄ ⊆ Ｃ 是 Ｃ 的 Ｄ⁃ 约简， 如果 １） ＰＯＳＲｅｄ（Ｄ） ＝ ＰＯＳＣ（Ｄ） ； ２） ∀ａ ∈ Ｒｅｄ ， ＰＯＳＲｅｄ－｛ａ｝（Ｄ） ≠ ＰＯＳＲｅｄ（Ｄ） 。 定义 ５ 在决策表 Ｓ 中， Ａ⊆Ｃ ， ∀ｃ∈Ａ ，在正 区域下属性 ｃ 重要性定义为 Ｓｉｇ ｉｎｎｅｒ （ｃ，Ａ，Ｄ） ＝ γＡ（Ｄ） – γＡ－｛ｃ｝（Ｄ） 式中： γＡ（Ｄ） ＝ ｜ ＰＯＳＡ（Ｄ） ｜ Ｕ 。 定义 ６ 在决策表 Ｓ 中， Ａ ⊆ Ｃ ， ∀ｃ ∈ Ｃ － Ａ ， 在正区域下属性 ｃ 重要性定义为 Ｓｉｇ ｏｕｔｅｒ （ｃ，Ａ，Ｄ） ＝ γＡ∪｛ｃ｝（Ｄ） – γＡ（Ｄ） 定义 ７ 设Ｒｅｄ为决策表 Ｓ 的候选属性约简， ＮｅｗＲｅｄ 为新增样本之后的新约简，则单次增量式 约简的传承率（ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ， ＩＲ）定义为 ＩＲ ＝ ｜ Ｒｅｄ ∩ ＮｅｗＲｅｄ ｜ ｍｉｎ（｜ Ｒｅｄ ｜ ， ｜ ＮｅｗＲｅｄ ｜ ） 假设进行了 ｗ 次增量式约简，则平均传承率 （ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ａｖｅｒａｇｅ，ＩＲＡ）定义为 ＩＲＡ ＝ ∑ ｗ ｉ ＝ １ ＩＲｉ ｗ 在约简过程中，传承率越高则约简集的变化越 小，对原始规则集的影响将越小。 如果传承率为 １， 说明新增的对象不影响原始的规则集；如果传承率 为 ０，则新的约简集与原来的约简集完全不同，这时 需全部更新所有规则。 第 ４ 期 钱进，等：面向成组对象集的增量式属性约简算法 ·４９７·