第2期 鞠恒荣，等：不完备信息系统中测试代价敏感的可变精度分类粗糙集 .221. 令TCSIIDS为测试代价敏感决策系统，ae[0, 2)red←-g 1],VACAT,aeA,a,的重要度为 3)Ha:eA7,计算属性a:的重要度TCSLSigin(a:, LSigin (ai,A,D)=y(A,a,D)-y(A-a;,a,D) ArD); 可以看出，LSign(a,B,D)反映了a,从当前条 4)TCSLSigin (a;,Ar,D)=max TCSISigin (a:, 件属性集A中删除后近似质量的变化，相应地也可 Ar,D):a:eA,},则red←-a,计算y(red,a,D): 定义 5)若y(ed,a,D)y(Az,a,D),则重复以下循 ISig(a;,A,D)=y(A U a;,a,D)-y(A,a,D) 环，否则转6)； 式中：a,∈A,-A,LSig(a:,A,D)用以度量向属性集A ①Va,eA,-red,计算TCSLSig(a:,red,D); 增加属性α，后近似质量的变化。根据上述属性的重要 ②若TCSLSig,(a:,B,D)=max{TCSLSigou(a:, 度可以设计启发式属性约简算法。Min等在文献[11] B,D):a,∈A,-red},则red←-a:; 中设计了传统的启发式算法（记为算法1）。其算法复 6)a:∈red,若y(red-a:,a,D)=y(Ar,a,D), 14 杂度为0(1A,IU1+∑1U1(1A,1-i+1)。 red red-a:,tmp =c'(red); 7)c'(red)=minc'(red),tmp Min等从获取约简的测试代价最小出发设计出 8)若0大于给定阈值，则0=0-6（此处8为步 新的约简算法，即回溯算法（记为算法2）。其算法 长，6>0)且重复2)~7)，否则转9)： 复杂度为0(2r-1)。详细算法见文献[11]。 9)输出red及c·(red)。 3.1考虑属性测试代价的启发式算法 3.2实验分析 由上文可知回溯算法的时间复杂度为O(24- 本节将通过实验，对比算法1、算法2和算法 1)。考虑到现实生活中存在着大量高维属性的数据， 3。表1列出了实验中使用的4组测试数据的基本 这样一种机制将会大大制约属性约简的时间。为解 信息，所有数据集均下载于UCI数据集。由于UCI 决这一问题，本文依然从启发式算法的角度出发，将 数据集中的大部分数据不含有测试代价，所以在本 属性的测试代价考虑到属性重要度定义中。为此，给 组实验中为每个数据集的属性随机增加了取值在 出如下的属性融合重要度定义。 [10,100]之间的测试代价。 TCSLSigin(a:,Ar,D)= 表1实验数据基本信息 0.1×LSigi(a,A7,D)+0.9×(c·(a:))° Table 1 Data sets descriptions TCSLSig (a:,Ar,D)= Decision 0.1 xLSig.(a,A7,D)+0.9×(c(a))° Data ID Data sets Samples Attributes Classes 式中：0≤0。可以看出，TCSLSig..(a:,A7,D)是LSig 1 Bridges 108 12 1 2 Credit Approval 263 3 (a:,A,D)与(c(a:)”之和。当9=0时，无论属性 3 Heart-Disease 303 14 的测试代价取何值，都有TCSLSigin(a:,Ar,D)=0.1× 4 Hepatitis 155 19 2 LSig(a:,A,D)+1,这说明TCSLSig.(a:,A7,D)的大 由于基于测试代价敏感的可变精度分类粗糙集 小与属性测试代价的大小无关，仅与LSig.(a:,Ar, 模型的下、上近似集由阈值α控制，因此，在实验 D)的值有关。随着0值的不断减小，(c(a:))°的值 中选取了10组不同的α值分别对比3个算法的测 也不断减小（本文随机产生测试代价在[10,100]）， 试代价，在算法3的第8步中，给定阈值设为-5， 此时(c(a:)°在TCSLSig.(a:,A7,D)中所占的比重 步长δ为0.5，即重复求得10次约简，取其中的最 也越来越小，表明属性测试代价在属性的重要度中 小测试代价作为输出。具体的实验结果见图1。 的影响作用越来越小。根据新的属性融合重要度， ×109 7 不难设计出综合考虑了测试代价的启发式算法，具 算法1 6 算法2 体算法流程见算法1。 ★ 24 算法3 算法1基于测试代价敏感不完备决策系统 TCSIIDS综合考虑测试代价的启发式算法 输入：测试代价敏感不完备决策系统TCSIIDS,a; 0 0.10.20.30.40.50.60.70.80.91.0 输出：约简red及约简的测试代价c·(red)。 1)计算y(4,a,D):令=0，c(d)=c(4): (a)Bridges令 ＴＣＳＩＩＤＳ 为测试代价敏感决策系统， α Î［０， １］， "Ａ ÍＡＴ， "ａｉÎＡ， ａｉ的重要度为 ＬＳｉｇｉｎ（ａｉ， Ａ， Ｄ） ＝ γ（Ａ， α， Ｄ） -γ（Ａ -ａｉ， α， Ｄ） 可以看出， ＬＳｉｇｉｎ（ａｉ， Ｂ， Ｄ）反映了 ａｉ从当前条 件属性集 Ａ 中删除后近似质量的变化， 相应地也可 定义 ＬＳｉｇｏｕｔ（ａｉ， Ａ， Ｄ） ＝ γ（Ａ ∪ ａｉ， α， Ｄ） -γ（Ａ， α， Ｄ） 式中：ａｉÎＡＴ -Ａ， ＬＳｉｇｏｕｔ（ａｉ，Ａ， Ｄ）用以度量向属性集 Ａ 增加属性 ａｉ后近似质量的变化。 根据上述属性的重要 度可以设计启发式属性约简算法。 Ｍｉｎ 等在文献［１１］ 中设计了传统的启发式算法（记为算法 １）。 其算法复 杂度为 Ｏ（ ｜ＡＴ ｜ ｜Ｕ｜ ＋∑ ｜ ＡＴ ｜ ｉ ＝ １ ｜Ｕ｜（ ｜ＡＴ ｜ -ｉ＋１））。 Ｍｉｎ 等从获取约简的测试代价最小出发设计出 新的约简算法， 即回溯算法（记为算法 ２）。 其算法 复杂度为 Ｏ（２ ｜ ＡＴ ｜ -１）。 详细算法见文献［１１］。 ３．１ 考虑属性测试代价的启发式算法 由上文可知回溯算法的时间复杂度为 Ｏ（２ ｜ ＡＴ ｜ - １）。 考虑到现实生活中存在着大量高维属性的数据， 这样一种机制将会大大制约属性约简的时间。 为解 决这一问题， 本文依然从启发式算法的角度出发， 将 属性的测试代价考虑到属性重要度定义中。 为此， 给 出如下的属性融合重要度定义。 ＴＣＳＬＳｉｇｉｎ（ａｉ， ＡＴ ， Ｄ） ＝ ０．１ ´ＬＳｉｇｉｎ（ａｉ， ＡＴ ， Ｄ） ＋ ０．９ ´（ｃ ∗ （ａｉ）） θ ＴＣＳＬＳｉｇｏｕｔ（ａｉ， ＡＴ ， Ｄ） ＝ ０．１ ´ＬＳｉｇｏｕｔ（ａｉ， ＡＴ ， Ｄ） ＋ ０．９ ´（ｃ ∗ （ａｉ）） θ 式中：θ≤ ０。 可以看出， ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）是 ＬＳｉｇｉｎ （ａｉ， ＡＴ， Ｄ）与（ｃ ∗ （ａｉ）） θ 之和。 当 θ＝ ０ 时， 无论属性 的测试代价取何值， 都有 ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）＝ ０．１ ´ ＬＳｉｇｉｎ （ａｉ，ＡＴ，Ｄ）＋１， 这说明 ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）的大 小与属性测试代价的大小无关， 仅与 ＬＳｉｇｉｎ （ａｉ，ＡＴ， Ｄ）的值有关。 随着 θ 值的不断减小， （ｃ ∗ （ａｉ）） θ 的值 也不断减小（本文随机产生测试代价在［１０， １００］）， 此时（ｃ ∗ （ａｉ）） θ 在 ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）中所占的比重 也越来越小， 表明属性测试代价在属性的重要度中 的影响作用越来越小。 根据新的属性融合重要度， 不难设计出综合考虑了测试代价的启发式算法， 具 体算法流程见算法 １。 算法 １ 基于测试代价敏感不完备决策系统 ＴＣＳＩＩＤＳ 综合考虑测试代价的启发式算法 输入：测试代价敏感不完备决策系统 ＴＣＳＩＩＤＳ， α； 输出：约简 ｒｅｄ 及约简的测试代价 ｃ ∗ （ｒｅｄ）。 １）计算 γ（ＡＴ， α， Ｄ）； 令θ＝０， ｃ ∗ （ｒｅｄ）＝ ｃ ∗ （ＡＴ）； ２） ｒｅｄ ¬Æ； ３）"ａｉÎＡＴ ， 计算属性 ａｉ的重要度 ＴＣＳＬＳｉｇｉｎ（ａｉ， ＡＴ ，Ｄ）； ４）若 ＴＣＳＬＳｉｇｉｎ（ａｊ，ＡＴ，Ｄ） ＝ ｍａｘ｛ＴＣＳＬＳｉｇｉｎ（ａｉ， ＡＴ，Ｄ）： ａｉÎＡＴ｝， 则 ｒｅｄ ¬ａｊ，计算 γ（ｒｅｄ，α，Ｄ）； ５）若 γ（ｒｅｄ，α，Ｄ）¹γ（ＡＴ ，α，Ｄ）， 则重复以下循 环， 否则转 ６）； ①"ａｉÎＡＴ -ｒｅｄ，计算 ＴＣＳＬＳｉｇｏｕｔ（ａｉ，ｒｅｄ，Ｄ）； ②若 ＴＣＳＬＳｉｇｏｕｔ（ａｉ，Ｂ，Ｄ） ＝ ｍａｘ｛ＴＣＳＬＳｉｇｏｕｔ（ ａｉ， Ｂ，Ｄ）： ａｉÎＡＴ -ｒｅｄ｝，则 ｒｅｄ ¬ａｉ； ６）"ａｉÎｒｅｄ， 若 γ（ｒｅｄ -ａｉ，α，Ｄ）＝ γ（ＡＴ ，α，Ｄ）， 则 ｒｅｄ ＝ ｒｅｄ -ａｉ， ｔｍｐ ＝ ｃ ∗ （ｒｅｄ）； ７）ｃ ∗ （ｒｅｄ）＝ ｍｉｎ｛ｃ ∗ （ｒｅｄ）， ｔｍｐ｝； ８）若 θ 大于给定阈值， 则 θ ＝ θ -δ（此处 δ 为步 长，δ＞０）且重复 ２） ～７），否则转 ９）； ９）输出 ｒｅｄ 及 ｃ ∗ （ｒｅｄ）。 ３．２ 实验分析 本节将通过实验， 对比算法 １、算法 ２ 和算法 ３。 表 １ 列出了实验中使用的 ４ 组测试数据的基本 信息， 所有数据集均下载于 ＵＣＩ 数据集。 由于 ＵＣＩ 数据集中的大部分数据不含有测试代价， 所以在本 组实验中为每个数据集的属性随机增加了取值在 ［１０， １００］之间的测试代价。 表 １ 实验数据基本信息 Ｔａｂｌｅ １ Ｄａｔａ ｓｅｔｓ ｄｅｓｃｒｉｐｔｉｏｎｓ Ｄａｔａ ＩＤ Ｄａｔａ ｓｅｔｓ Ｓａｍｐｌｅｓ Ａｔｔｒｉｂｕｔｅｓ Ｄｅｃｉｓｉｏｎ Ｃｌａｓｓｅｓ １ Ｂｒｉｄｇｅｓ １０８ １２ ７ ２ Ｃｒｅｄｉｔ Ａｐｐｒｏｖａｌ ２６３ １５ ３ ３ Ｈｅａｒｔ⁃Ｄｉｓｅａｓｅ ３０３ １４ ５ ４ Ｈｅｐａｔｉｔｉｓ １５５ １９ ２ 由于基于测试代价敏感的可变精度分类粗糙集 模型的下、上近似集由阈值 α 控制， 因此， 在实验 中选取了 １０ 组不同的 α 值分别对比 ３ 个算法的测 试代价， 在算法 ３ 的第 ８ 步中， 给定阈值设为－５， 步长 δ 为 ０．５， 即重复求得 １０ 次约简， 取其中的最 小测试代价作为输出。 具体的实验结果见图 １。 （ａ）Ｂｒｉｄｇｅｓ 第 ２ 期 鞠恒荣，等：不完备信息系统中测试代价敏感的可变精度分类粗糙集 ·２２１·